summaryrefslogtreecommitdiffstats
path: root/fs/hfsplus
diff options
context:
space:
mode:
Diffstat (limited to 'fs/hfsplus')
-rw-r--r--fs/hfsplus/btree.c112
-rw-r--r--fs/hfsplus/hfsplus_fs.h10
-rw-r--r--fs/hfsplus/hfsplus_raw.h11
-rw-r--r--fs/hfsplus/super.c2
-rw-r--r--fs/hfsplus/xattr.c207
5 files changed, 336 insertions, 6 deletions
diff --git a/fs/hfsplus/btree.c b/fs/hfsplus/btree.c
index 0c6540c91167..0fcec8b2a90b 100644
--- a/fs/hfsplus/btree.c
+++ b/fs/hfsplus/btree.c
@@ -15,6 +15,118 @@
#include "hfsplus_fs.h"
#include "hfsplus_raw.h"
+/*
+ * Initial source code of clump size calculation is gotten
+ * from http://opensource.apple.com/tarballs/diskdev_cmds/
+ */
+#define CLUMP_ENTRIES 15
+
+static short clumptbl[CLUMP_ENTRIES * 3] = {
+/*
+ * Volume Attributes Catalog Extents
+ * Size Clump (MB) Clump (MB) Clump (MB)
+ */
+ /* 1GB */ 4, 4, 4,
+ /* 2GB */ 6, 6, 4,
+ /* 4GB */ 8, 8, 4,
+ /* 8GB */ 11, 11, 5,
+ /*
+ * For volumes 16GB and larger, we want to make sure that a full OS
+ * install won't require fragmentation of the Catalog or Attributes
+ * B-trees. We do this by making the clump sizes sufficiently large,
+ * and by leaving a gap after the B-trees for them to grow into.
+ *
+ * For SnowLeopard 10A298, a FullNetInstall with all packages selected
+ * results in:
+ * Catalog B-tree Header
+ * nodeSize: 8192
+ * totalNodes: 31616
+ * freeNodes: 1978
+ * (used = 231.55 MB)
+ * Attributes B-tree Header
+ * nodeSize: 8192
+ * totalNodes: 63232
+ * freeNodes: 958
+ * (used = 486.52 MB)
+ *
+ * We also want Time Machine backup volumes to have a sufficiently
+ * large clump size to reduce fragmentation.
+ *
+ * The series of numbers for Catalog and Attribute form a geometric
+ * series. For Catalog (16GB to 512GB), each term is 8**(1/5) times
+ * the previous term. For Attributes (16GB to 512GB), each term is
+ * 4**(1/5) times the previous term. For 1TB to 16TB, each term is
+ * 2**(1/5) times the previous term.
+ */
+ /* 16GB */ 64, 32, 5,
+ /* 32GB */ 84, 49, 6,
+ /* 64GB */ 111, 74, 7,
+ /* 128GB */ 147, 111, 8,
+ /* 256GB */ 194, 169, 9,
+ /* 512GB */ 256, 256, 11,
+ /* 1TB */ 294, 294, 14,
+ /* 2TB */ 338, 338, 16,
+ /* 4TB */ 388, 388, 20,
+ /* 8TB */ 446, 446, 25,
+ /* 16TB */ 512, 512, 32
+};
+
+u32 hfsplus_calc_btree_clump_size(u32 block_size, u32 node_size,
+ u64 sectors, int file_id)
+{
+ u32 mod = max(node_size, block_size);
+ u32 clump_size;
+ int column;
+ int i;
+
+ /* Figure out which column of the above table to use for this file. */
+ switch (file_id) {
+ case HFSPLUS_ATTR_CNID:
+ column = 0;
+ break;
+ case HFSPLUS_CAT_CNID:
+ column = 1;
+ break;
+ default:
+ column = 2;
+ break;
+ }
+
+ /*
+ * The default clump size is 0.8% of the volume size. And
+ * it must also be a multiple of the node and block size.
+ */
+ if (sectors < 0x200000) {
+ clump_size = sectors << 2; /* 0.8 % */
+ if (clump_size < (8 * node_size))
+ clump_size = 8 * node_size;
+ } else {
+ /* turn exponent into table index... */
+ for (i = 0, sectors = sectors >> 22;
+ sectors && (i < CLUMP_ENTRIES - 1);
+ ++i, sectors = sectors >> 1) {
+ /* empty body */
+ }
+
+ clump_size = clumptbl[column + (i) * 3] * 1024 * 1024;
+ }
+
+ /*
+ * Round the clump size to a multiple of node and block size.
+ * NOTE: This rounds down.
+ */
+ clump_size /= mod;
+ clump_size *= mod;
+
+ /*
+ * Rounding down could have rounded down to 0 if the block size was
+ * greater than the clump size. If so, just use one block or node.
+ */
+ if (clump_size == 0)
+ clump_size = mod;
+
+ return clump_size;
+}
/* Get a reference to a B*Tree and do some initial checks */
struct hfs_btree *hfs_btree_open(struct super_block *sb, u32 id)
diff --git a/fs/hfsplus/hfsplus_fs.h b/fs/hfsplus/hfsplus_fs.h
index 2b9cd01696e2..08846425b67f 100644
--- a/fs/hfsplus/hfsplus_fs.h
+++ b/fs/hfsplus/hfsplus_fs.h
@@ -127,6 +127,14 @@ struct hfs_bnode {
#define HFS_BNODE_DELETED 4
/*
+ * Attributes file states
+ */
+#define HFSPLUS_EMPTY_ATTR_TREE 0
+#define HFSPLUS_CREATING_ATTR_TREE 1
+#define HFSPLUS_VALID_ATTR_TREE 2
+#define HFSPLUS_FAILED_ATTR_TREE 3
+
+/*
* HFS+ superblock info (built from Volume Header on disk)
*/
@@ -141,6 +149,7 @@ struct hfsplus_sb_info {
struct hfs_btree *ext_tree;
struct hfs_btree *cat_tree;
struct hfs_btree *attr_tree;
+ atomic_t attr_tree_state;
struct inode *alloc_file;
struct inode *hidden_dir;
struct nls_table *nls;
@@ -380,6 +389,7 @@ int hfsplus_block_allocate(struct super_block *, u32, u32, u32 *);
int hfsplus_block_free(struct super_block *, u32, u32);
/* btree.c */
+u32 hfsplus_calc_btree_clump_size(u32, u32, u64, int);
struct hfs_btree *hfs_btree_open(struct super_block *, u32);
void hfs_btree_close(struct hfs_btree *);
int hfs_btree_write(struct hfs_btree *);
diff --git a/fs/hfsplus/hfsplus_raw.h b/fs/hfsplus/hfsplus_raw.h
index 452ede01b036..8ffb3a8ffe75 100644
--- a/fs/hfsplus/hfsplus_raw.h
+++ b/fs/hfsplus/hfsplus_raw.h
@@ -156,10 +156,10 @@ struct hfs_bnode_desc {
} __packed;
/* HFS+ BTree node types */
-#define HFS_NODE_INDEX 0x00
-#define HFS_NODE_HEADER 0x01
-#define HFS_NODE_MAP 0x02
-#define HFS_NODE_LEAF 0xFF
+#define HFS_NODE_INDEX 0x00 /* An internal (index) node */
+#define HFS_NODE_HEADER 0x01 /* The tree header node (node 0) */
+#define HFS_NODE_MAP 0x02 /* Holds part of the bitmap of used nodes */
+#define HFS_NODE_LEAF 0xFF /* A leaf (ndNHeight==1) node */
/* HFS+ BTree header */
struct hfs_btree_header_rec {
@@ -187,6 +187,9 @@ struct hfs_btree_header_rec {
/* HFS+ BTree misc info */
#define HFSPLUS_TREE_HEAD 0
#define HFSPLUS_NODE_MXSZ 32768
+#define HFSPLUS_ATTR_TREE_NODE_SIZE 8192
+#define HFSPLUS_BTREE_HDR_NODE_RECS_COUNT 3
+#define HFSPLUS_BTREE_HDR_USER_BYTES 128
/* Some special File ID numbers (stolen from hfs.h) */
#define HFSPLUS_POR_CNID 1 /* Parent Of the Root */
diff --git a/fs/hfsplus/super.c b/fs/hfsplus/super.c
index 4c4d142cf890..80875aa640ef 100644
--- a/fs/hfsplus/super.c
+++ b/fs/hfsplus/super.c
@@ -474,12 +474,14 @@ static int hfsplus_fill_super(struct super_block *sb, void *data, int silent)
pr_err("failed to load catalog file\n");
goto out_close_ext_tree;
}
+ atomic_set(&sbi->attr_tree_state, HFSPLUS_EMPTY_ATTR_TREE);
if (vhdr->attr_file.total_blocks != 0) {
sbi->attr_tree = hfs_btree_open(sb, HFSPLUS_ATTR_CNID);
if (!sbi->attr_tree) {
pr_err("failed to load attributes file\n");
goto out_close_cat_tree;
}
+ atomic_set(&sbi->attr_tree_state, HFSPLUS_VALID_ATTR_TREE);
}
sb->s_xattr = hfsplus_xattr_handlers;
diff --git a/fs/hfsplus/xattr.c b/fs/hfsplus/xattr.c
index bd8471fb9a6a..efc85b1377cc 100644
--- a/fs/hfsplus/xattr.c
+++ b/fs/hfsplus/xattr.c
@@ -127,6 +127,208 @@ static int can_set_xattr(struct inode *inode, const char *name,
return 0;
}
+static void hfsplus_init_header_node(struct inode *attr_file,
+ u32 clump_size,
+ char *buf, size_t node_size)
+{
+ struct hfs_bnode_desc *desc;
+ struct hfs_btree_header_rec *head;
+ u16 offset;
+ __be16 *rec_offsets;
+ u32 hdr_node_map_rec_bits;
+ char *bmp;
+ u32 used_nodes;
+ u32 used_bmp_bytes;
+
+ hfs_dbg(ATTR_MOD, "init_hdr_attr_file: clump %u, node_size %zu\n",
+ clump_size, node_size);
+
+ /* The end of the node contains list of record offsets */
+ rec_offsets = (__be16 *)(buf + node_size);
+
+ desc = (struct hfs_bnode_desc *)buf;
+ desc->type = HFS_NODE_HEADER;
+ desc->num_recs = cpu_to_be16(HFSPLUS_BTREE_HDR_NODE_RECS_COUNT);
+ offset = sizeof(struct hfs_bnode_desc);
+ *--rec_offsets = cpu_to_be16(offset);
+
+ head = (struct hfs_btree_header_rec *)(buf + offset);
+ head->node_size = cpu_to_be16(node_size);
+ head->node_count = cpu_to_be32(i_size_read(attr_file) / node_size);
+ head->free_nodes = cpu_to_be32(be32_to_cpu(head->node_count) - 1);
+ head->clump_size = cpu_to_be32(clump_size);
+ head->attributes |= cpu_to_be32(HFS_TREE_BIGKEYS | HFS_TREE_VARIDXKEYS);
+ head->max_key_len = cpu_to_be16(HFSPLUS_ATTR_KEYLEN - sizeof(u16));
+ offset += sizeof(struct hfs_btree_header_rec);
+ *--rec_offsets = cpu_to_be16(offset);
+ offset += HFSPLUS_BTREE_HDR_USER_BYTES;
+ *--rec_offsets = cpu_to_be16(offset);
+
+ hdr_node_map_rec_bits = 8 * (node_size - offset - (4 * sizeof(u16)));
+ if (be32_to_cpu(head->node_count) > hdr_node_map_rec_bits) {
+ u32 map_node_bits;
+ u32 map_nodes;
+
+ desc->next = cpu_to_be32(be32_to_cpu(head->leaf_tail) + 1);
+ map_node_bits = 8 * (node_size - sizeof(struct hfs_bnode_desc) -
+ (2 * sizeof(u16)) - 2);
+ map_nodes = (be32_to_cpu(head->node_count) -
+ hdr_node_map_rec_bits +
+ (map_node_bits - 1)) / map_node_bits;
+ be32_add_cpu(&head->free_nodes, 0 - map_nodes);
+ }
+
+ bmp = buf + offset;
+ used_nodes =
+ be32_to_cpu(head->node_count) - be32_to_cpu(head->free_nodes);
+ used_bmp_bytes = used_nodes / 8;
+ if (used_bmp_bytes) {
+ memset(bmp, 0xFF, used_bmp_bytes);
+ bmp += used_bmp_bytes;
+ used_nodes %= 8;
+ }
+ *bmp = ~(0xFF >> used_nodes);
+ offset += hdr_node_map_rec_bits / 8;
+ *--rec_offsets = cpu_to_be16(offset);
+}
+
+static int hfsplus_create_attributes_file(struct super_block *sb)
+{
+ int err = 0;
+ struct hfsplus_sb_info *sbi = HFSPLUS_SB(sb);
+ struct inode *attr_file;
+ struct hfsplus_inode_info *hip;
+ u32 clump_size;
+ u16 node_size = HFSPLUS_ATTR_TREE_NODE_SIZE;
+ char *buf;
+ int index, written;
+ struct address_space *mapping;
+ struct page *page;
+ int old_state = HFSPLUS_EMPTY_ATTR_TREE;
+
+ hfs_dbg(ATTR_MOD, "create_attr_file: ino %d\n", HFSPLUS_ATTR_CNID);
+
+check_attr_tree_state_again:
+ switch (atomic_read(&sbi->attr_tree_state)) {
+ case HFSPLUS_EMPTY_ATTR_TREE:
+ if (old_state != atomic_cmpxchg(&sbi->attr_tree_state,
+ old_state,
+ HFSPLUS_CREATING_ATTR_TREE))
+ goto check_attr_tree_state_again;
+ break;
+ case HFSPLUS_CREATING_ATTR_TREE:
+ /*
+ * This state means that another thread is in process
+ * of AttributesFile creation. Theoretically, it is
+ * possible to be here. But really __setxattr() method
+ * first of all calls hfs_find_init() for lookup in
+ * B-tree of CatalogFile. This method locks mutex of
+ * CatalogFile's B-tree. As a result, if some thread
+ * is inside AttributedFile creation operation then
+ * another threads will be waiting unlocking of
+ * CatalogFile's B-tree's mutex. However, if code will
+ * change then we will return error code (-EAGAIN) from
+ * here. Really, it means that first try to set of xattr
+ * fails with error but second attempt will have success.
+ */
+ return -EAGAIN;
+ case HFSPLUS_VALID_ATTR_TREE:
+ return 0;
+ case HFSPLUS_FAILED_ATTR_TREE:
+ return -EOPNOTSUPP;
+ default:
+ BUG();
+ }
+
+ attr_file = hfsplus_iget(sb, HFSPLUS_ATTR_CNID);
+ if (IS_ERR(attr_file)) {
+ pr_err("failed to load attributes file\n");
+ return PTR_ERR(attr_file);
+ }
+
+ BUG_ON(i_size_read(attr_file) != 0);
+
+ hip = HFSPLUS_I(attr_file);
+
+ clump_size = hfsplus_calc_btree_clump_size(sb->s_blocksize,
+ node_size,
+ sbi->sect_count,
+ HFSPLUS_ATTR_CNID);
+
+ mutex_lock(&hip->extents_lock);
+ hip->clump_blocks = clump_size >> sbi->alloc_blksz_shift;
+ mutex_unlock(&hip->extents_lock);
+
+ if (sbi->free_blocks <= (hip->clump_blocks << 1)) {
+ err = -ENOSPC;
+ goto end_attr_file_creation;
+ }
+
+ while (hip->alloc_blocks < hip->clump_blocks) {
+ err = hfsplus_file_extend(attr_file);
+ if (unlikely(err)) {
+ pr_err("failed to extend attributes file\n");
+ goto end_attr_file_creation;
+ }
+ hip->phys_size = attr_file->i_size =
+ (loff_t)hip->alloc_blocks << sbi->alloc_blksz_shift;
+ hip->fs_blocks = hip->alloc_blocks << sbi->fs_shift;
+ inode_set_bytes(attr_file, attr_file->i_size);
+ }
+
+ buf = kzalloc(node_size, GFP_NOFS);
+ if (!buf) {
+ pr_err("failed to allocate memory for header node\n");
+ err = -ENOMEM;
+ goto end_attr_file_creation;
+ }
+
+ hfsplus_init_header_node(attr_file, clump_size, buf, node_size);
+
+ mapping = attr_file->i_mapping;
+
+ index = 0;
+ written = 0;
+ for (; written < node_size; index++, written += PAGE_CACHE_SIZE) {
+ void *kaddr;
+
+ page = read_mapping_page(mapping, index, NULL);
+ if (IS_ERR(page)) {
+ err = PTR_ERR(page);
+ goto failed_header_node_init;
+ }
+
+ kaddr = kmap_atomic(page);
+ memcpy(kaddr, buf + written,
+ min_t(size_t, PAGE_CACHE_SIZE, node_size - written));
+ kunmap_atomic(kaddr);
+
+ set_page_dirty(page);
+ page_cache_release(page);
+ }
+
+ hfsplus_mark_inode_dirty(attr_file, HFSPLUS_I_ATTR_DIRTY);
+
+ sbi->attr_tree = hfs_btree_open(sb, HFSPLUS_ATTR_CNID);
+ if (!sbi->attr_tree)
+ pr_err("failed to load attributes file\n");
+
+failed_header_node_init:
+ kfree(buf);
+
+end_attr_file_creation:
+ iput(attr_file);
+
+ if (!err)
+ atomic_set(&sbi->attr_tree_state, HFSPLUS_VALID_ATTR_TREE);
+ else if (err == -ENOSPC)
+ atomic_set(&sbi->attr_tree_state, HFSPLUS_EMPTY_ATTR_TREE);
+ else
+ atomic_set(&sbi->attr_tree_state, HFSPLUS_FAILED_ATTR_TREE);
+
+ return err;
+}
+
int __hfsplus_setxattr(struct inode *inode, const char *name,
const void *value, size_t size, int flags)
{
@@ -211,8 +413,9 @@ int __hfsplus_setxattr(struct inode *inode, const char *name,
}
if (!HFSPLUS_SB(inode->i_sb)->attr_tree) {
- err = -EOPNOTSUPP;
- goto end_setxattr;
+ err = hfsplus_create_attributes_file(inode->i_sb);
+ if (unlikely(err))
+ goto end_setxattr;
}
if (hfsplus_attr_exists(inode, name)) {
OpenPOWER on IntegriCloud