1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * linux/fs/hfs/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/pagemap.h> 13 #include <linux/slab.h> 14 #include <linux/log2.h> 15 16 #include "btree.h" 17 18 /* Context for iterating b-tree map pages 19 * @page_idx: The index of the page within the b-node's page array 20 * @off: The byte offset within the mapped page 21 * @len: The remaining length of the map record 22 */ 23 struct hfs_bmap_ctx { 24 unsigned int page_idx; 25 unsigned int off; 26 u16 len; 27 }; 28 29 /* 30 * Finds the specific page containing the requested byte offset within the map 31 * record. Automatically handles the difference between header and map nodes. 32 * Returns the struct page pointer, or an ERR_PTR on failure. 33 * Note: The caller is responsible for mapping/unmapping the returned page. 34 */ 35 static struct page *hfs_bmap_get_map_page(struct hfs_bnode *node, 36 struct hfs_bmap_ctx *ctx, 37 u32 byte_offset) 38 { 39 u16 rec_idx, off16; 40 unsigned int page_off; 41 42 if (node->this == HFS_TREE_HEAD) { 43 if (node->type != HFS_NODE_HEADER) { 44 pr_err("hfs: invalid btree header node\n"); 45 return ERR_PTR(-EIO); 46 } 47 rec_idx = HFS_BTREE_HDR_MAP_REC_INDEX; 48 } else { 49 if (node->type != HFS_NODE_MAP) { 50 pr_err("hfs: invalid btree map node\n"); 51 return ERR_PTR(-EIO); 52 } 53 rec_idx = HFS_BTREE_MAP_NODE_REC_INDEX; 54 } 55 56 ctx->len = hfs_brec_lenoff(node, rec_idx, &off16); 57 if (!ctx->len) 58 return ERR_PTR(-ENOENT); 59 60 if (!is_bnode_offset_valid(node, off16)) 61 return ERR_PTR(-EIO); 62 63 ctx->len = check_and_correct_requested_length(node, off16, ctx->len); 64 65 if (byte_offset >= ctx->len) 66 return ERR_PTR(-EINVAL); 67 68 page_off = (u32)off16 + node->page_offset + byte_offset; 69 ctx->page_idx = page_off >> PAGE_SHIFT; 70 ctx->off = page_off & ~PAGE_MASK; 71 72 return node->page[ctx->page_idx]; 73 } 74 75 /** 76 * hfs_bmap_test_bit - test a bit in the b-tree map 77 * @node: the b-tree node containing the map record 78 * @node_bit_idx: the relative bit index within the node's map record 79 * 80 * Returns true if set, false if clear or on failure. 81 */ 82 static bool hfs_bmap_test_bit(struct hfs_bnode *node, u32 node_bit_idx) 83 { 84 struct hfs_bmap_ctx ctx; 85 struct page *page; 86 u8 *bmap, byte, mask; 87 88 page = hfs_bmap_get_map_page(node, &ctx, node_bit_idx / BITS_PER_BYTE); 89 if (IS_ERR(page)) 90 return false; 91 92 bmap = kmap_local_page(page); 93 byte = bmap[ctx.off]; 94 kunmap_local(bmap); 95 96 mask = 1 << (7 - (node_bit_idx % BITS_PER_BYTE)); 97 return (byte & mask) != 0; 98 } 99 100 /** 101 * hfs_bmap_clear_bit - clear a bit in the b-tree map 102 * @node: the b-tree node containing the map record 103 * @node_bit_idx: the relative bit index within the node's map record 104 * 105 * Returns 0 on success, -EINVAL if already clear, or negative error code. 106 */ 107 static int hfs_bmap_clear_bit(struct hfs_bnode *node, u32 node_bit_idx) 108 { 109 struct hfs_bmap_ctx ctx; 110 struct page *page; 111 u8 *bmap, mask; 112 113 page = hfs_bmap_get_map_page(node, &ctx, node_bit_idx / BITS_PER_BYTE); 114 if (IS_ERR(page)) 115 return PTR_ERR(page); 116 117 bmap = kmap_local_page(page); 118 119 mask = 1 << (7 - (node_bit_idx % BITS_PER_BYTE)); 120 121 if (!(bmap[ctx.off] & mask)) { 122 kunmap_local(bmap); 123 return -EINVAL; 124 } 125 126 bmap[ctx.off] &= ~mask; 127 set_page_dirty(page); 128 kunmap_local(bmap); 129 130 return 0; 131 } 132 133 /* Get a reference to a B*Tree and do some initial checks */ 134 struct hfs_btree *hfs_btree_open(struct super_block *sb, u32 id, btree_keycmp keycmp) 135 { 136 struct hfs_btree *tree; 137 struct hfs_btree_header_rec *head; 138 struct address_space *mapping; 139 struct folio *folio; 140 struct buffer_head *bh; 141 struct hfs_bnode *node; 142 unsigned int size; 143 u16 dblock; 144 sector_t start_block; 145 loff_t offset; 146 147 tree = kzalloc_obj(*tree); 148 if (!tree) 149 return NULL; 150 151 mutex_init(&tree->tree_lock); 152 spin_lock_init(&tree->hash_lock); 153 /* Set the correct compare function */ 154 tree->sb = sb; 155 tree->cnid = id; 156 tree->keycmp = keycmp; 157 158 tree->inode = iget_locked(sb, id); 159 if (!tree->inode) 160 goto free_tree; 161 BUG_ON(!(inode_state_read_once(tree->inode) & I_NEW)); 162 { 163 struct hfs_mdb *mdb = HFS_SB(sb)->mdb; 164 HFS_I(tree->inode)->flags = 0; 165 mutex_init(&HFS_I(tree->inode)->extents_lock); 166 switch (id) { 167 case HFS_EXT_CNID: 168 hfs_inode_read_fork(tree->inode, mdb->drXTExtRec, mdb->drXTFlSize, 169 mdb->drXTFlSize, be32_to_cpu(mdb->drXTClpSiz)); 170 if (HFS_I(tree->inode)->alloc_blocks > 171 HFS_I(tree->inode)->first_blocks) { 172 pr_err("invalid btree extent records\n"); 173 unlock_new_inode(tree->inode); 174 goto free_inode; 175 } 176 177 tree->inode->i_mapping->a_ops = &hfs_btree_aops; 178 break; 179 case HFS_CAT_CNID: 180 hfs_inode_read_fork(tree->inode, mdb->drCTExtRec, mdb->drCTFlSize, 181 mdb->drCTFlSize, be32_to_cpu(mdb->drCTClpSiz)); 182 183 if (!HFS_I(tree->inode)->first_blocks) { 184 pr_err("invalid btree extent records (0 size)\n"); 185 unlock_new_inode(tree->inode); 186 goto free_inode; 187 } 188 189 tree->inode->i_mapping->a_ops = &hfs_btree_aops; 190 break; 191 default: 192 BUG(); 193 } 194 } 195 unlock_new_inode(tree->inode); 196 197 mapping = tree->inode->i_mapping; 198 folio = filemap_grab_folio(mapping, 0); 199 if (IS_ERR(folio)) 200 goto free_inode; 201 202 folio_zero_range(folio, 0, folio_size(folio)); 203 204 dblock = hfs_ext_find_block(HFS_I(tree->inode)->first_extents, 0); 205 start_block = HFS_SB(sb)->fs_start + (dblock * HFS_SB(sb)->fs_div); 206 207 size = folio_size(folio); 208 offset = 0; 209 while (size > 0) { 210 size_t len; 211 212 bh = sb_bread(sb, start_block); 213 if (!bh) { 214 pr_err("unable to read tree header\n"); 215 goto put_folio; 216 } 217 218 len = min_t(size_t, folio_size(folio), sb->s_blocksize); 219 memcpy_to_folio(folio, offset, bh->b_data, sb->s_blocksize); 220 221 brelse(bh); 222 223 start_block++; 224 offset += len; 225 size -= len; 226 } 227 228 folio_mark_uptodate(folio); 229 230 /* Load the header */ 231 head = (struct hfs_btree_header_rec *)(kmap_local_folio(folio, 0) + 232 sizeof(struct hfs_bnode_desc)); 233 tree->root = be32_to_cpu(head->root); 234 tree->leaf_count = be32_to_cpu(head->leaf_count); 235 tree->leaf_head = be32_to_cpu(head->leaf_head); 236 tree->leaf_tail = be32_to_cpu(head->leaf_tail); 237 tree->node_count = be32_to_cpu(head->node_count); 238 tree->free_nodes = be32_to_cpu(head->free_nodes); 239 tree->attributes = be32_to_cpu(head->attributes); 240 tree->node_size = be16_to_cpu(head->node_size); 241 tree->max_key_len = be16_to_cpu(head->max_key_len); 242 tree->depth = be16_to_cpu(head->depth); 243 244 size = tree->node_size; 245 if (!is_power_of_2(size)) 246 goto fail_folio; 247 if (!tree->node_count) 248 goto fail_folio; 249 switch (id) { 250 case HFS_EXT_CNID: 251 if (tree->max_key_len != HFS_MAX_EXT_KEYLEN) { 252 pr_err("invalid extent max_key_len %d\n", 253 tree->max_key_len); 254 goto fail_folio; 255 } 256 break; 257 case HFS_CAT_CNID: 258 if (tree->max_key_len != HFS_MAX_CAT_KEYLEN) { 259 pr_err("invalid catalog max_key_len %d\n", 260 tree->max_key_len); 261 goto fail_folio; 262 } 263 break; 264 default: 265 BUG(); 266 } 267 268 tree->node_size_shift = ffs(size) - 1; 269 tree->pages_per_bnode = (tree->node_size + PAGE_SIZE - 1) >> PAGE_SHIFT; 270 271 kunmap_local(head); 272 folio_unlock(folio); 273 folio_put(folio); 274 275 node = hfs_bnode_find(tree, HFS_TREE_HEAD); 276 if (IS_ERR(node)) 277 goto free_inode; 278 279 if (!hfs_bmap_test_bit(node, HFS_TREE_HEAD)) { 280 pr_warn("(%s): %s (cnid 0x%x) bitmap corrupted, forcing rdonly\n", 281 sb->s_id, id == HFS_EXT_CNID ? "extents" : "catalog", id); 282 pr_warn("Run fsck.hfs to repair.\n"); 283 sb->s_flags |= SB_RDONLY; 284 } 285 286 hfs_bnode_put(node); 287 288 return tree; 289 290 fail_folio: 291 kunmap_local(head); 292 put_folio: 293 folio_unlock(folio); 294 folio_put(folio); 295 free_inode: 296 tree->inode->i_mapping->a_ops = &hfs_aops; 297 iput(tree->inode); 298 free_tree: 299 kfree(tree); 300 return NULL; 301 } 302 303 /* Release resources used by a btree */ 304 void hfs_btree_close(struct hfs_btree *tree) 305 { 306 struct hfs_bnode *node; 307 int i; 308 309 if (!tree) 310 return; 311 312 for (i = 0; i < NODE_HASH_SIZE; i++) { 313 while ((node = tree->node_hash[i])) { 314 tree->node_hash[i] = node->next_hash; 315 if (atomic_read(&node->refcnt)) 316 pr_err("node %d:%d still has %d user(s)!\n", 317 node->tree->cnid, node->this, 318 atomic_read(&node->refcnt)); 319 hfs_bnode_free(node); 320 tree->node_hash_cnt--; 321 } 322 } 323 iput(tree->inode); 324 kfree(tree); 325 } 326 327 void hfs_btree_write(struct hfs_btree *tree) 328 { 329 struct hfs_btree_header_rec *head; 330 struct hfs_bnode *node; 331 struct page *page; 332 333 node = hfs_bnode_find(tree, 0); 334 if (IS_ERR(node)) 335 /* panic? */ 336 return; 337 /* Load the header */ 338 page = node->page[0]; 339 head = (struct hfs_btree_header_rec *)(kmap_local_page(page) + 340 sizeof(struct hfs_bnode_desc)); 341 342 head->root = cpu_to_be32(tree->root); 343 head->leaf_count = cpu_to_be32(tree->leaf_count); 344 head->leaf_head = cpu_to_be32(tree->leaf_head); 345 head->leaf_tail = cpu_to_be32(tree->leaf_tail); 346 head->node_count = cpu_to_be32(tree->node_count); 347 head->free_nodes = cpu_to_be32(tree->free_nodes); 348 head->attributes = cpu_to_be32(tree->attributes); 349 head->depth = cpu_to_be16(tree->depth); 350 351 kunmap_local(head); 352 set_page_dirty(page); 353 hfs_bnode_put(node); 354 } 355 356 static struct hfs_bnode *hfs_bmap_new_bmap(struct hfs_bnode *prev, u32 idx) 357 { 358 struct hfs_btree *tree = prev->tree; 359 struct hfs_bnode *node; 360 struct hfs_bnode_desc desc; 361 __be32 cnid; 362 363 node = hfs_bnode_create(tree, idx); 364 if (IS_ERR(node)) 365 return node; 366 367 if (!tree->free_nodes) 368 panic("FIXME!!!"); 369 tree->free_nodes--; 370 prev->next = idx; 371 cnid = cpu_to_be32(idx); 372 hfs_bnode_write(prev, &cnid, offsetof(struct hfs_bnode_desc, next), 4); 373 374 node->type = HFS_NODE_MAP; 375 node->num_recs = 1; 376 hfs_bnode_clear(node, 0, tree->node_size); 377 desc.next = 0; 378 desc.prev = 0; 379 desc.type = HFS_NODE_MAP; 380 desc.height = 0; 381 desc.num_recs = cpu_to_be16(1); 382 desc.reserved = 0; 383 hfs_bnode_write(node, &desc, 0, sizeof(desc)); 384 hfs_bnode_write_u16(node, 14, 0x8000); 385 hfs_bnode_write_u16(node, tree->node_size - 2, 14); 386 hfs_bnode_write_u16(node, tree->node_size - 4, tree->node_size - 6); 387 388 return node; 389 } 390 391 /* Make sure @tree has enough space for the @rsvd_nodes */ 392 int hfs_bmap_reserve(struct hfs_btree *tree, u32 rsvd_nodes) 393 { 394 struct inode *inode = tree->inode; 395 u32 count; 396 int res; 397 398 while (tree->free_nodes < rsvd_nodes) { 399 res = hfs_extend_file(inode); 400 if (res) 401 return res; 402 HFS_I(inode)->phys_size = inode->i_size = 403 (loff_t)HFS_I(inode)->alloc_blocks * 404 HFS_SB(tree->sb)->alloc_blksz; 405 HFS_I(inode)->fs_blocks = inode->i_size >> 406 tree->sb->s_blocksize_bits; 407 inode_set_bytes(inode, inode->i_size); 408 count = inode->i_size >> tree->node_size_shift; 409 tree->free_nodes += count - tree->node_count; 410 tree->node_count = count; 411 } 412 return 0; 413 } 414 415 struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree) 416 { 417 struct hfs_bnode *node, *next_node; 418 struct hfs_bmap_ctx ctx; 419 struct page *page; 420 u32 nidx, idx; 421 u8 *data, byte, m; 422 int i, res; 423 424 res = hfs_bmap_reserve(tree, 1); 425 if (res) 426 return ERR_PTR(res); 427 428 nidx = 0; 429 node = hfs_bnode_find(tree, nidx); 430 if (IS_ERR(node)) 431 return node; 432 433 page = hfs_bmap_get_map_page(node, &ctx, 0); 434 if (IS_ERR(page)) { 435 res = PTR_ERR(page); 436 hfs_bnode_put(node); 437 return ERR_PTR(res); 438 } 439 440 data = kmap_local_page(page); 441 idx = 0; 442 443 for (;;) { 444 while (ctx.len) { 445 byte = data[ctx.off]; 446 if (byte != 0xff) { 447 for (m = 0x80, i = 0; i < 8; m >>= 1, i++) { 448 if (!(byte & m)) { 449 idx += i; 450 data[ctx.off] |= m; 451 set_page_dirty(page); 452 kunmap_local(data); 453 tree->free_nodes--; 454 mark_inode_dirty(tree->inode); 455 hfs_bnode_put(node); 456 return hfs_bnode_create(tree, idx); 457 } 458 } 459 } 460 if (++ctx.off >= PAGE_SIZE) { 461 kunmap_local(data); 462 page = node->page[++ctx.page_idx]; 463 data = kmap_local_page(page); 464 ctx.off = 0; 465 } 466 idx += 8; 467 ctx.len--; 468 } 469 kunmap_local(data); 470 nidx = node->next; 471 if (!nidx) { 472 printk(KERN_DEBUG "create new bmap node...\n"); 473 next_node = hfs_bmap_new_bmap(node, idx); 474 } else 475 next_node = hfs_bnode_find(tree, nidx); 476 hfs_bnode_put(node); 477 if (IS_ERR(next_node)) 478 return next_node; 479 node = next_node; 480 481 page = hfs_bmap_get_map_page(node, &ctx, 0); 482 if (IS_ERR(page)) { 483 res = PTR_ERR(page); 484 hfs_bnode_put(node); 485 return ERR_PTR(res); 486 } 487 data = kmap_local_page(page); 488 } 489 } 490 491 void hfs_bmap_free(struct hfs_bnode *node) 492 { 493 struct hfs_btree *tree; 494 u16 off, len; 495 u32 nidx; 496 int res; 497 498 hfs_dbg("node %u\n", node->this); 499 tree = node->tree; 500 nidx = node->this; 501 node = hfs_bnode_find(tree, 0); 502 if (IS_ERR(node)) 503 return; 504 len = hfs_brec_lenoff(node, 2, &off); 505 while (nidx >= len * 8) { 506 u32 i; 507 508 nidx -= len * 8; 509 i = node->next; 510 if (!i) { 511 /* panic */; 512 pr_crit("unable to free bnode %u. bmap not found!\n", 513 node->this); 514 hfs_bnode_put(node); 515 return; 516 } 517 hfs_bnode_put(node); 518 node = hfs_bnode_find(tree, i); 519 if (IS_ERR(node)) 520 return; 521 if (node->type != HFS_NODE_MAP) { 522 /* panic */; 523 pr_crit("invalid bmap found! (%u,%d)\n", 524 node->this, node->type); 525 hfs_bnode_put(node); 526 return; 527 } 528 len = hfs_brec_lenoff(node, 0, &off); 529 } 530 531 res = hfs_bmap_clear_bit(node, nidx); 532 if (res == -EINVAL) { 533 pr_crit("trying to free free bnode %u(%d)\n", 534 nidx, node->type); 535 } else if (res) { 536 pr_crit("fail to free bnode %u(%d)\n", 537 nidx, node->type); 538 } else { 539 tree->free_nodes++; 540 mark_inode_dirty(tree->inode); 541 } 542 543 hfs_bnode_put(node); 544 } 545