1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * linux/fs/hfsplus/btree.c 4 * 5 * Copyright (C) 2001 6 * Brad Boyer (flar@allandria.com) 7 * (C) 2003 Ardis Technologies <roman@ardistech.com> 8 * 9 * Handle opening/closing btree 10 */ 11 12 #include <linux/slab.h> 13 #include <linux/pagemap.h> 14 #include <linux/log2.h> 15 16 #include "hfsplus_fs.h" 17 #include "hfsplus_raw.h" 18 19 /* 20 * Initial source code of clump size calculation is gotten 21 * from http://opensource.apple.com/tarballs/diskdev_cmds/ 22 */ 23 #define CLUMP_ENTRIES 15 24 25 static short clumptbl[CLUMP_ENTRIES * 3] = { 26 /* 27 * Volume Attributes Catalog Extents 28 * Size Clump (MB) Clump (MB) Clump (MB) 29 */ 30 /* 1GB */ 4, 4, 4, 31 /* 2GB */ 6, 6, 4, 32 /* 4GB */ 8, 8, 4, 33 /* 8GB */ 11, 11, 5, 34 /* 35 * For volumes 16GB and larger, we want to make sure that a full OS 36 * install won't require fragmentation of the Catalog or Attributes 37 * B-trees. We do this by making the clump sizes sufficiently large, 38 * and by leaving a gap after the B-trees for them to grow into. 39 * 40 * For SnowLeopard 10A298, a FullNetInstall with all packages selected 41 * results in: 42 * Catalog B-tree Header 43 * nodeSize: 8192 44 * totalNodes: 31616 45 * freeNodes: 1978 46 * (used = 231.55 MB) 47 * Attributes B-tree Header 48 * nodeSize: 8192 49 * totalNodes: 63232 50 * freeNodes: 958 51 * (used = 486.52 MB) 52 * 53 * We also want Time Machine backup volumes to have a sufficiently 54 * large clump size to reduce fragmentation. 55 * 56 * The series of numbers for Catalog and Attribute form a geometric 57 * series. For Catalog (16GB to 512GB), each term is 8**(1/5) times 58 * the previous term. For Attributes (16GB to 512GB), each term is 59 * 4**(1/5) times the previous term. For 1TB to 16TB, each term is 60 * 2**(1/5) times the previous term. 61 */ 62 /* 16GB */ 64, 32, 5, 63 /* 32GB */ 84, 49, 6, 64 /* 64GB */ 111, 74, 7, 65 /* 128GB */ 147, 111, 8, 66 /* 256GB */ 194, 169, 9, 67 /* 512GB */ 256, 256, 11, 68 /* 1TB */ 294, 294, 14, 69 /* 2TB */ 338, 338, 16, 70 /* 4TB */ 388, 388, 20, 71 /* 8TB */ 446, 446, 25, 72 /* 16TB */ 512, 512, 32 73 }; 74 75 u32 hfsplus_calc_btree_clump_size(u32 block_size, u32 node_size, 76 u64 sectors, int file_id) 77 { 78 u32 mod = max(node_size, block_size); 79 u32 clump_size; 80 int column; 81 int i; 82 83 /* Figure out which column of the above table to use for this file. */ 84 switch (file_id) { 85 case HFSPLUS_ATTR_CNID: 86 column = 0; 87 break; 88 case HFSPLUS_CAT_CNID: 89 column = 1; 90 break; 91 default: 92 column = 2; 93 break; 94 } 95 96 /* 97 * The default clump size is 0.8% of the volume size. And 98 * it must also be a multiple of the node and block size. 99 */ 100 if (sectors < 0x200000) { 101 clump_size = sectors << 2; /* 0.8 % */ 102 if (clump_size < (8 * node_size)) 103 clump_size = 8 * node_size; 104 } else { 105 /* turn exponent into table index... */ 106 for (i = 0, sectors = sectors >> 22; 107 sectors && (i < CLUMP_ENTRIES - 1); 108 ++i, sectors = sectors >> 1) { 109 /* empty body */ 110 } 111 112 clump_size = clumptbl[column + (i) * 3] * 1024 * 1024; 113 } 114 115 /* 116 * Round the clump size to a multiple of node and block size. 117 * NOTE: This rounds down. 118 */ 119 clump_size /= mod; 120 clump_size *= mod; 121 122 /* 123 * Rounding down could have rounded down to 0 if the block size was 124 * greater than the clump size. If so, just use one block or node. 125 */ 126 if (clump_size == 0) 127 clump_size = mod; 128 129 return clump_size; 130 } 131 132 /* Get a reference to a B*Tree and do some initial checks */ 133 struct hfs_btree *hfs_btree_open(struct super_block *sb, u32 id) 134 { 135 struct hfs_btree *tree; 136 struct hfs_btree_header_rec *head; 137 struct address_space *mapping; 138 struct inode *inode; 139 struct page *page; 140 unsigned int size; 141 142 tree = kzalloc(sizeof(*tree), GFP_KERNEL); 143 if (!tree) 144 return NULL; 145 146 mutex_init(&tree->tree_lock); 147 spin_lock_init(&tree->hash_lock); 148 tree->sb = sb; 149 tree->cnid = id; 150 inode = hfsplus_iget(sb, id); 151 if (IS_ERR(inode)) 152 goto free_tree; 153 tree->inode = inode; 154 155 if (!HFSPLUS_I(tree->inode)->first_blocks) { 156 pr_err("invalid btree extent records (0 size)\n"); 157 goto free_inode; 158 } 159 160 mapping = tree->inode->i_mapping; 161 page = read_mapping_page(mapping, 0, NULL); 162 if (IS_ERR(page)) 163 goto free_inode; 164 165 /* Load the header */ 166 head = (struct hfs_btree_header_rec *)(kmap(page) + 167 sizeof(struct hfs_bnode_desc)); 168 tree->root = be32_to_cpu(head->root); 169 tree->leaf_count = be32_to_cpu(head->leaf_count); 170 tree->leaf_head = be32_to_cpu(head->leaf_head); 171 tree->leaf_tail = be32_to_cpu(head->leaf_tail); 172 tree->node_count = be32_to_cpu(head->node_count); 173 tree->free_nodes = be32_to_cpu(head->free_nodes); 174 tree->attributes = be32_to_cpu(head->attributes); 175 tree->node_size = be16_to_cpu(head->node_size); 176 tree->max_key_len = be16_to_cpu(head->max_key_len); 177 tree->depth = be16_to_cpu(head->depth); 178 179 /* Verify the tree and set the correct compare function */ 180 switch (id) { 181 case HFSPLUS_EXT_CNID: 182 if (tree->max_key_len != HFSPLUS_EXT_KEYLEN - sizeof(u16)) { 183 pr_err("invalid extent max_key_len %d\n", 184 tree->max_key_len); 185 goto fail_page; 186 } 187 if (tree->attributes & HFS_TREE_VARIDXKEYS) { 188 pr_err("invalid extent btree flag\n"); 189 goto fail_page; 190 } 191 192 tree->keycmp = hfsplus_ext_cmp_key; 193 break; 194 case HFSPLUS_CAT_CNID: 195 if (tree->max_key_len != HFSPLUS_CAT_KEYLEN - sizeof(u16)) { 196 pr_err("invalid catalog max_key_len %d\n", 197 tree->max_key_len); 198 goto fail_page; 199 } 200 if (!(tree->attributes & HFS_TREE_VARIDXKEYS)) { 201 pr_err("invalid catalog btree flag\n"); 202 goto fail_page; 203 } 204 205 if (test_bit(HFSPLUS_SB_HFSX, &HFSPLUS_SB(sb)->flags) && 206 (head->key_type == HFSPLUS_KEY_BINARY)) 207 tree->keycmp = hfsplus_cat_bin_cmp_key; 208 else { 209 tree->keycmp = hfsplus_cat_case_cmp_key; 210 set_bit(HFSPLUS_SB_CASEFOLD, &HFSPLUS_SB(sb)->flags); 211 } 212 break; 213 case HFSPLUS_ATTR_CNID: 214 if (tree->max_key_len != HFSPLUS_ATTR_KEYLEN - sizeof(u16)) { 215 pr_err("invalid attributes max_key_len %d\n", 216 tree->max_key_len); 217 goto fail_page; 218 } 219 tree->keycmp = hfsplus_attr_bin_cmp_key; 220 break; 221 default: 222 pr_err("unknown B*Tree requested\n"); 223 goto fail_page; 224 } 225 226 if (!(tree->attributes & HFS_TREE_BIGKEYS)) { 227 pr_err("invalid btree flag\n"); 228 goto fail_page; 229 } 230 231 size = tree->node_size; 232 if (!is_power_of_2(size)) 233 goto fail_page; 234 if (!tree->node_count) 235 goto fail_page; 236 237 tree->node_size_shift = ffs(size) - 1; 238 239 tree->pages_per_bnode = 240 (tree->node_size + PAGE_SIZE - 1) >> 241 PAGE_SHIFT; 242 243 kunmap(page); 244 put_page(page); 245 return tree; 246 247 fail_page: 248 put_page(page); 249 free_inode: 250 tree->inode->i_mapping->a_ops = &hfsplus_aops; 251 iput(tree->inode); 252 free_tree: 253 kfree(tree); 254 return NULL; 255 } 256 257 /* Release resources used by a btree */ 258 void hfs_btree_close(struct hfs_btree *tree) 259 { 260 struct hfs_bnode *node; 261 int i; 262 263 if (!tree) 264 return; 265 266 for (i = 0; i < NODE_HASH_SIZE; i++) { 267 while ((node = tree->node_hash[i])) { 268 tree->node_hash[i] = node->next_hash; 269 if (atomic_read(&node->refcnt)) 270 pr_crit("node %d:%d " 271 "still has %d user(s)!\n", 272 node->tree->cnid, node->this, 273 atomic_read(&node->refcnt)); 274 hfs_bnode_free(node); 275 tree->node_hash_cnt--; 276 } 277 } 278 iput(tree->inode); 279 kfree(tree); 280 } 281 282 int hfs_btree_write(struct hfs_btree *tree) 283 { 284 struct hfs_btree_header_rec *head; 285 struct hfs_bnode *node; 286 struct page *page; 287 288 node = hfs_bnode_find(tree, 0); 289 if (IS_ERR(node)) 290 /* panic? */ 291 return -EIO; 292 /* Load the header */ 293 page = node->page[0]; 294 head = (struct hfs_btree_header_rec *)(kmap(page) + 295 sizeof(struct hfs_bnode_desc)); 296 297 head->root = cpu_to_be32(tree->root); 298 head->leaf_count = cpu_to_be32(tree->leaf_count); 299 head->leaf_head = cpu_to_be32(tree->leaf_head); 300 head->leaf_tail = cpu_to_be32(tree->leaf_tail); 301 head->node_count = cpu_to_be32(tree->node_count); 302 head->free_nodes = cpu_to_be32(tree->free_nodes); 303 head->attributes = cpu_to_be32(tree->attributes); 304 head->depth = cpu_to_be16(tree->depth); 305 306 kunmap(page); 307 set_page_dirty(page); 308 hfs_bnode_put(node); 309 return 0; 310 } 311 312 static struct hfs_bnode *hfs_bmap_new_bmap(struct hfs_bnode *prev, u32 idx) 313 { 314 struct hfs_btree *tree = prev->tree; 315 struct hfs_bnode *node; 316 struct hfs_bnode_desc desc; 317 __be32 cnid; 318 319 node = hfs_bnode_create(tree, idx); 320 if (IS_ERR(node)) 321 return node; 322 323 tree->free_nodes--; 324 prev->next = idx; 325 cnid = cpu_to_be32(idx); 326 hfs_bnode_write(prev, &cnid, offsetof(struct hfs_bnode_desc, next), 4); 327 328 node->type = HFS_NODE_MAP; 329 node->num_recs = 1; 330 hfs_bnode_clear(node, 0, tree->node_size); 331 desc.next = 0; 332 desc.prev = 0; 333 desc.type = HFS_NODE_MAP; 334 desc.height = 0; 335 desc.num_recs = cpu_to_be16(1); 336 desc.reserved = 0; 337 hfs_bnode_write(node, &desc, 0, sizeof(desc)); 338 hfs_bnode_write_u16(node, 14, 0x8000); 339 hfs_bnode_write_u16(node, tree->node_size - 2, 14); 340 hfs_bnode_write_u16(node, tree->node_size - 4, tree->node_size - 6); 341 342 return node; 343 } 344 345 struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree) 346 { 347 struct hfs_bnode *node, *next_node; 348 struct page **pagep; 349 u32 nidx, idx; 350 unsigned off; 351 u16 off16; 352 u16 len; 353 u8 *data, byte, m; 354 int i; 355 356 while (!tree->free_nodes) { 357 struct inode *inode = tree->inode; 358 struct hfsplus_inode_info *hip = HFSPLUS_I(inode); 359 u32 count; 360 int res; 361 362 res = hfsplus_file_extend(inode, hfs_bnode_need_zeroout(tree)); 363 if (res) 364 return ERR_PTR(res); 365 hip->phys_size = inode->i_size = 366 (loff_t)hip->alloc_blocks << 367 HFSPLUS_SB(tree->sb)->alloc_blksz_shift; 368 hip->fs_blocks = 369 hip->alloc_blocks << HFSPLUS_SB(tree->sb)->fs_shift; 370 inode_set_bytes(inode, inode->i_size); 371 count = inode->i_size >> tree->node_size_shift; 372 tree->free_nodes = count - tree->node_count; 373 tree->node_count = count; 374 } 375 376 nidx = 0; 377 node = hfs_bnode_find(tree, nidx); 378 if (IS_ERR(node)) 379 return node; 380 len = hfs_brec_lenoff(node, 2, &off16); 381 off = off16; 382 383 off += node->page_offset; 384 pagep = node->page + (off >> PAGE_SHIFT); 385 data = kmap(*pagep); 386 off &= ~PAGE_MASK; 387 idx = 0; 388 389 for (;;) { 390 while (len) { 391 byte = data[off]; 392 if (byte != 0xff) { 393 for (m = 0x80, i = 0; i < 8; m >>= 1, i++) { 394 if (!(byte & m)) { 395 idx += i; 396 data[off] |= m; 397 set_page_dirty(*pagep); 398 kunmap(*pagep); 399 tree->free_nodes--; 400 mark_inode_dirty(tree->inode); 401 hfs_bnode_put(node); 402 return hfs_bnode_create(tree, 403 idx); 404 } 405 } 406 } 407 if (++off >= PAGE_SIZE) { 408 kunmap(*pagep); 409 data = kmap(*++pagep); 410 off = 0; 411 } 412 idx += 8; 413 len--; 414 } 415 kunmap(*pagep); 416 nidx = node->next; 417 if (!nidx) { 418 hfs_dbg(BNODE_MOD, "create new bmap node\n"); 419 next_node = hfs_bmap_new_bmap(node, idx); 420 } else 421 next_node = hfs_bnode_find(tree, nidx); 422 hfs_bnode_put(node); 423 if (IS_ERR(next_node)) 424 return next_node; 425 node = next_node; 426 427 len = hfs_brec_lenoff(node, 0, &off16); 428 off = off16; 429 off += node->page_offset; 430 pagep = node->page + (off >> PAGE_SHIFT); 431 data = kmap(*pagep); 432 off &= ~PAGE_MASK; 433 } 434 } 435 436 void hfs_bmap_free(struct hfs_bnode *node) 437 { 438 struct hfs_btree *tree; 439 struct page *page; 440 u16 off, len; 441 u32 nidx; 442 u8 *data, byte, m; 443 444 hfs_dbg(BNODE_MOD, "btree_free_node: %u\n", node->this); 445 BUG_ON(!node->this); 446 tree = node->tree; 447 nidx = node->this; 448 node = hfs_bnode_find(tree, 0); 449 if (IS_ERR(node)) 450 return; 451 len = hfs_brec_lenoff(node, 2, &off); 452 while (nidx >= len * 8) { 453 u32 i; 454 455 nidx -= len * 8; 456 i = node->next; 457 hfs_bnode_put(node); 458 if (!i) { 459 /* panic */; 460 pr_crit("unable to free bnode %u. " 461 "bmap not found!\n", 462 node->this); 463 return; 464 } 465 node = hfs_bnode_find(tree, i); 466 if (IS_ERR(node)) 467 return; 468 if (node->type != HFS_NODE_MAP) { 469 /* panic */; 470 pr_crit("invalid bmap found! " 471 "(%u,%d)\n", 472 node->this, node->type); 473 hfs_bnode_put(node); 474 return; 475 } 476 len = hfs_brec_lenoff(node, 0, &off); 477 } 478 off += node->page_offset + nidx / 8; 479 page = node->page[off >> PAGE_SHIFT]; 480 data = kmap(page); 481 off &= ~PAGE_MASK; 482 m = 1 << (~nidx & 7); 483 byte = data[off]; 484 if (!(byte & m)) { 485 pr_crit("trying to free free bnode " 486 "%u(%d)\n", 487 node->this, node->type); 488 kunmap(page); 489 hfs_bnode_put(node); 490 return; 491 } 492 data[off] = byte & ~m; 493 set_page_dirty(page); 494 kunmap(page); 495 hfs_bnode_put(node); 496 tree->free_nodes++; 497 mark_inode_dirty(tree->inode); 498 } 499