]>
git.proxmox.com Git - mirror_ubuntu-bionic-kernel.git/blob - fs/hfsplus/btree.c
2 * linux/fs/hfsplus/btree.c
5 * Brad Boyer (flar@allandria.com)
6 * (C) 2003 Ardis Technologies <roman@ardistech.com>
8 * Handle opening/closing btree
11 #include <linux/slab.h>
12 #include <linux/pagemap.h>
13 #include <linux/log2.h>
15 #include "hfsplus_fs.h"
16 #include "hfsplus_raw.h"
19 * Initial source code of clump size calculation is gotten
20 * from http://opensource.apple.com/tarballs/diskdev_cmds/
22 #define CLUMP_ENTRIES 15
24 static short clumptbl
[CLUMP_ENTRIES
* 3] = {
26 * Volume Attributes Catalog Extents
27 * Size Clump (MB) Clump (MB) Clump (MB)
34 * For volumes 16GB and larger, we want to make sure that a full OS
35 * install won't require fragmentation of the Catalog or Attributes
36 * B-trees. We do this by making the clump sizes sufficiently large,
37 * and by leaving a gap after the B-trees for them to grow into.
39 * For SnowLeopard 10A298, a FullNetInstall with all packages selected
41 * Catalog B-tree Header
46 * Attributes B-tree Header
52 * We also want Time Machine backup volumes to have a sufficiently
53 * large clump size to reduce fragmentation.
55 * The series of numbers for Catalog and Attribute form a geometric
56 * series. For Catalog (16GB to 512GB), each term is 8**(1/5) times
57 * the previous term. For Attributes (16GB to 512GB), each term is
58 * 4**(1/5) times the previous term. For 1TB to 16TB, each term is
59 * 2**(1/5) times the previous term.
63 /* 64GB */ 111, 74, 7,
64 /* 128GB */ 147, 111, 8,
65 /* 256GB */ 194, 169, 9,
66 /* 512GB */ 256, 256, 11,
67 /* 1TB */ 294, 294, 14,
68 /* 2TB */ 338, 338, 16,
69 /* 4TB */ 388, 388, 20,
70 /* 8TB */ 446, 446, 25,
71 /* 16TB */ 512, 512, 32
74 u32
hfsplus_calc_btree_clump_size(u32 block_size
, u32 node_size
,
75 u64 sectors
, int file_id
)
77 u32 mod
= max(node_size
, block_size
);
82 /* Figure out which column of the above table to use for this file. */
84 case HFSPLUS_ATTR_CNID
:
87 case HFSPLUS_CAT_CNID
:
96 * The default clump size is 0.8% of the volume size. And
97 * it must also be a multiple of the node and block size.
99 if (sectors
< 0x200000) {
100 clump_size
= sectors
<< 2; /* 0.8 % */
101 if (clump_size
< (8 * node_size
))
102 clump_size
= 8 * node_size
;
104 /* turn exponent into table index... */
105 for (i
= 0, sectors
= sectors
>> 22;
106 sectors
&& (i
< CLUMP_ENTRIES
- 1);
107 ++i
, sectors
= sectors
>> 1) {
111 clump_size
= clumptbl
[column
+ (i
) * 3] * 1024 * 1024;
115 * Round the clump size to a multiple of node and block size.
116 * NOTE: This rounds down.
122 * Rounding down could have rounded down to 0 if the block size was
123 * greater than the clump size. If so, just use one block or node.
131 /* Get a reference to a B*Tree and do some initial checks */
132 struct hfs_btree
*hfs_btree_open(struct super_block
*sb
, u32 id
)
134 struct hfs_btree
*tree
;
135 struct hfs_btree_header_rec
*head
;
136 struct address_space
*mapping
;
141 tree
= kzalloc(sizeof(*tree
), GFP_KERNEL
);
145 mutex_init(&tree
->tree_lock
);
146 spin_lock_init(&tree
->hash_lock
);
149 inode
= hfsplus_iget(sb
, id
);
154 if (!HFSPLUS_I(tree
->inode
)->first_blocks
) {
155 pr_err("invalid btree extent records (0 size)\n");
159 mapping
= tree
->inode
->i_mapping
;
160 page
= read_mapping_page(mapping
, 0, NULL
);
164 /* Load the header */
165 head
= (struct hfs_btree_header_rec
*)(kmap(page
) +
166 sizeof(struct hfs_bnode_desc
));
167 tree
->root
= be32_to_cpu(head
->root
);
168 tree
->leaf_count
= be32_to_cpu(head
->leaf_count
);
169 tree
->leaf_head
= be32_to_cpu(head
->leaf_head
);
170 tree
->leaf_tail
= be32_to_cpu(head
->leaf_tail
);
171 tree
->node_count
= be32_to_cpu(head
->node_count
);
172 tree
->free_nodes
= be32_to_cpu(head
->free_nodes
);
173 tree
->attributes
= be32_to_cpu(head
->attributes
);
174 tree
->node_size
= be16_to_cpu(head
->node_size
);
175 tree
->max_key_len
= be16_to_cpu(head
->max_key_len
);
176 tree
->depth
= be16_to_cpu(head
->depth
);
178 /* Verify the tree and set the correct compare function */
180 case HFSPLUS_EXT_CNID
:
181 if (tree
->max_key_len
!= HFSPLUS_EXT_KEYLEN
- sizeof(u16
)) {
182 pr_err("invalid extent max_key_len %d\n",
186 if (tree
->attributes
& HFS_TREE_VARIDXKEYS
) {
187 pr_err("invalid extent btree flag\n");
191 tree
->keycmp
= hfsplus_ext_cmp_key
;
193 case HFSPLUS_CAT_CNID
:
194 if (tree
->max_key_len
!= HFSPLUS_CAT_KEYLEN
- sizeof(u16
)) {
195 pr_err("invalid catalog max_key_len %d\n",
199 if (!(tree
->attributes
& HFS_TREE_VARIDXKEYS
)) {
200 pr_err("invalid catalog btree flag\n");
204 if (test_bit(HFSPLUS_SB_HFSX
, &HFSPLUS_SB(sb
)->flags
) &&
205 (head
->key_type
== HFSPLUS_KEY_BINARY
))
206 tree
->keycmp
= hfsplus_cat_bin_cmp_key
;
208 tree
->keycmp
= hfsplus_cat_case_cmp_key
;
209 set_bit(HFSPLUS_SB_CASEFOLD
, &HFSPLUS_SB(sb
)->flags
);
212 case HFSPLUS_ATTR_CNID
:
213 if (tree
->max_key_len
!= HFSPLUS_ATTR_KEYLEN
- sizeof(u16
)) {
214 pr_err("invalid attributes max_key_len %d\n",
218 tree
->keycmp
= hfsplus_attr_bin_cmp_key
;
221 pr_err("unknown B*Tree requested\n");
225 if (!(tree
->attributes
& HFS_TREE_BIGKEYS
)) {
226 pr_err("invalid btree flag\n");
230 size
= tree
->node_size
;
231 if (!is_power_of_2(size
))
233 if (!tree
->node_count
)
236 tree
->node_size_shift
= ffs(size
) - 1;
238 tree
->pages_per_bnode
=
239 (tree
->node_size
+ PAGE_SIZE
- 1) >>
249 tree
->inode
->i_mapping
->a_ops
= &hfsplus_aops
;
256 /* Release resources used by a btree */
257 void hfs_btree_close(struct hfs_btree
*tree
)
259 struct hfs_bnode
*node
;
265 for (i
= 0; i
< NODE_HASH_SIZE
; i
++) {
266 while ((node
= tree
->node_hash
[i
])) {
267 tree
->node_hash
[i
] = node
->next_hash
;
268 if (atomic_read(&node
->refcnt
))
269 pr_crit("node %d:%d "
270 "still has %d user(s)!\n",
271 node
->tree
->cnid
, node
->this,
272 atomic_read(&node
->refcnt
));
273 hfs_bnode_free(node
);
274 tree
->node_hash_cnt
--;
281 int hfs_btree_write(struct hfs_btree
*tree
)
283 struct hfs_btree_header_rec
*head
;
284 struct hfs_bnode
*node
;
287 node
= hfs_bnode_find(tree
, 0);
291 /* Load the header */
292 page
= node
->page
[0];
293 head
= (struct hfs_btree_header_rec
*)(kmap(page
) +
294 sizeof(struct hfs_bnode_desc
));
296 head
->root
= cpu_to_be32(tree
->root
);
297 head
->leaf_count
= cpu_to_be32(tree
->leaf_count
);
298 head
->leaf_head
= cpu_to_be32(tree
->leaf_head
);
299 head
->leaf_tail
= cpu_to_be32(tree
->leaf_tail
);
300 head
->node_count
= cpu_to_be32(tree
->node_count
);
301 head
->free_nodes
= cpu_to_be32(tree
->free_nodes
);
302 head
->attributes
= cpu_to_be32(tree
->attributes
);
303 head
->depth
= cpu_to_be16(tree
->depth
);
306 set_page_dirty(page
);
311 static struct hfs_bnode
*hfs_bmap_new_bmap(struct hfs_bnode
*prev
, u32 idx
)
313 struct hfs_btree
*tree
= prev
->tree
;
314 struct hfs_bnode
*node
;
315 struct hfs_bnode_desc desc
;
318 node
= hfs_bnode_create(tree
, idx
);
324 cnid
= cpu_to_be32(idx
);
325 hfs_bnode_write(prev
, &cnid
, offsetof(struct hfs_bnode_desc
, next
), 4);
327 node
->type
= HFS_NODE_MAP
;
329 hfs_bnode_clear(node
, 0, tree
->node_size
);
332 desc
.type
= HFS_NODE_MAP
;
334 desc
.num_recs
= cpu_to_be16(1);
336 hfs_bnode_write(node
, &desc
, 0, sizeof(desc
));
337 hfs_bnode_write_u16(node
, 14, 0x8000);
338 hfs_bnode_write_u16(node
, tree
->node_size
- 2, 14);
339 hfs_bnode_write_u16(node
, tree
->node_size
- 4, tree
->node_size
- 6);
344 struct hfs_bnode
*hfs_bmap_alloc(struct hfs_btree
*tree
)
346 struct hfs_bnode
*node
, *next_node
;
355 while (!tree
->free_nodes
) {
356 struct inode
*inode
= tree
->inode
;
357 struct hfsplus_inode_info
*hip
= HFSPLUS_I(inode
);
361 res
= hfsplus_file_extend(inode
, hfs_bnode_need_zeroout(tree
));
364 hip
->phys_size
= inode
->i_size
=
365 (loff_t
)hip
->alloc_blocks
<<
366 HFSPLUS_SB(tree
->sb
)->alloc_blksz_shift
;
368 hip
->alloc_blocks
<< HFSPLUS_SB(tree
->sb
)->fs_shift
;
369 inode_set_bytes(inode
, inode
->i_size
);
370 count
= inode
->i_size
>> tree
->node_size_shift
;
371 tree
->free_nodes
= count
- tree
->node_count
;
372 tree
->node_count
= count
;
376 node
= hfs_bnode_find(tree
, nidx
);
379 len
= hfs_brec_lenoff(node
, 2, &off16
);
382 off
+= node
->page_offset
;
383 pagep
= node
->page
+ (off
>> PAGE_SHIFT
);
392 for (m
= 0x80, i
= 0; i
< 8; m
>>= 1, i
++) {
396 set_page_dirty(*pagep
);
399 mark_inode_dirty(tree
->inode
);
401 return hfs_bnode_create(tree
,
406 if (++off
>= PAGE_SIZE
) {
408 data
= kmap(*++pagep
);
417 hfs_dbg(BNODE_MOD
, "create new bmap node\n");
418 next_node
= hfs_bmap_new_bmap(node
, idx
);
420 next_node
= hfs_bnode_find(tree
, nidx
);
422 if (IS_ERR(next_node
))
426 len
= hfs_brec_lenoff(node
, 0, &off16
);
428 off
+= node
->page_offset
;
429 pagep
= node
->page
+ (off
>> PAGE_SHIFT
);
435 void hfs_bmap_free(struct hfs_bnode
*node
)
437 struct hfs_btree
*tree
;
443 hfs_dbg(BNODE_MOD
, "btree_free_node: %u\n", node
->this);
447 node
= hfs_bnode_find(tree
, 0);
450 len
= hfs_brec_lenoff(node
, 2, &off
);
451 while (nidx
>= len
* 8) {
459 pr_crit("unable to free bnode %u. "
464 node
= hfs_bnode_find(tree
, i
);
467 if (node
->type
!= HFS_NODE_MAP
) {
469 pr_crit("invalid bmap found! "
471 node
->this, node
->type
);
475 len
= hfs_brec_lenoff(node
, 0, &off
);
477 off
+= node
->page_offset
+ nidx
/ 8;
478 page
= node
->page
[off
>> PAGE_SHIFT
];
481 m
= 1 << (~nidx
& 7);
484 pr_crit("trying to free free bnode "
486 node
->this, node
->type
);
491 data
[off
] = byte
& ~m
;
492 set_page_dirty(page
);
496 mark_inode_dirty(tree
->inode
);