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 spin_lock(&tree->hash_lock); 314 while ((node = tree->node_hash[i])) { 315 hfs_bnode_unhash(node); 316 spin_unlock(&tree->hash_lock); 317 if (atomic_read(&node->refcnt)) 318 pr_err("node %d:%d still has %d user(s)!\n", 319 node->tree->cnid, node->this, 320 atomic_read(&node->refcnt)); 321 hfs_bnode_free(node); 322 spin_lock(&tree->hash_lock); 323 } 324 spin_unlock(&tree->hash_lock); 325 } 326 iput(tree->inode); 327 kfree(tree); 328 } 329 330 void hfs_btree_write(struct hfs_btree *tree) 331 { 332 struct hfs_btree_header_rec *head; 333 struct hfs_bnode *node; 334 struct page *page; 335 336 node = hfs_bnode_find(tree, 0); 337 if (IS_ERR(node)) 338 /* panic? */ 339 return; 340 /* Load the header */ 341 page = node->page[0]; 342 head = (struct hfs_btree_header_rec *)(kmap_local_page(page) + 343 sizeof(struct hfs_bnode_desc)); 344 345 head->root = cpu_to_be32(tree->root); 346 head->leaf_count = cpu_to_be32(tree->leaf_count); 347 head->leaf_head = cpu_to_be32(tree->leaf_head); 348 head->leaf_tail = cpu_to_be32(tree->leaf_tail); 349 head->node_count = cpu_to_be32(tree->node_count); 350 head->free_nodes = cpu_to_be32(tree->free_nodes); 351 head->attributes = cpu_to_be32(tree->attributes); 352 head->depth = cpu_to_be16(tree->depth); 353 354 kunmap_local(head); 355 set_page_dirty(page); 356 hfs_bnode_put(node); 357 } 358 359 static struct hfs_bnode *hfs_bmap_new_bmap(struct hfs_bnode *prev, u32 idx) 360 { 361 struct hfs_btree *tree = prev->tree; 362 struct hfs_bnode *node; 363 struct hfs_bnode_desc desc; 364 __be32 cnid; 365 366 node = hfs_bnode_create(tree, idx); 367 if (IS_ERR(node)) 368 return node; 369 370 if (!tree->free_nodes) 371 panic("FIXME!!!"); 372 tree->free_nodes--; 373 prev->next = idx; 374 cnid = cpu_to_be32(idx); 375 hfs_bnode_write(prev, &cnid, offsetof(struct hfs_bnode_desc, next), 4); 376 377 node->type = HFS_NODE_MAP; 378 node->num_recs = 1; 379 hfs_bnode_clear(node, 0, tree->node_size); 380 desc.next = 0; 381 desc.prev = 0; 382 desc.type = HFS_NODE_MAP; 383 desc.height = 0; 384 desc.num_recs = cpu_to_be16(1); 385 desc.reserved = 0; 386 hfs_bnode_write(node, &desc, 0, sizeof(desc)); 387 hfs_bnode_write_u16(node, 14, 0x8000); 388 hfs_bnode_write_u16(node, tree->node_size - 2, 14); 389 hfs_bnode_write_u16(node, tree->node_size - 4, tree->node_size - 6); 390 391 return node; 392 } 393 394 /* Make sure @tree has enough space for the @rsvd_nodes */ 395 int hfs_bmap_reserve(struct hfs_btree *tree, u32 rsvd_nodes) 396 { 397 struct inode *inode = tree->inode; 398 u32 count; 399 int res; 400 401 while (tree->free_nodes < rsvd_nodes) { 402 res = hfs_extend_file(inode); 403 if (res) 404 return res; 405 HFS_I(inode)->phys_size = inode->i_size = 406 (loff_t)HFS_I(inode)->alloc_blocks * 407 HFS_SB(tree->sb)->alloc_blksz; 408 HFS_I(inode)->fs_blocks = inode->i_size >> 409 tree->sb->s_blocksize_bits; 410 inode_set_bytes(inode, inode->i_size); 411 count = inode->i_size >> tree->node_size_shift; 412 tree->free_nodes += count - tree->node_count; 413 tree->node_count = count; 414 } 415 return 0; 416 } 417 418 struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree) 419 { 420 struct hfs_bnode *node, *next_node; 421 struct hfs_bmap_ctx ctx; 422 struct page *page; 423 u32 nidx, idx; 424 u8 *data, byte, m; 425 int i, res; 426 427 res = hfs_bmap_reserve(tree, 1); 428 if (res) 429 return ERR_PTR(res); 430 431 nidx = 0; 432 node = hfs_bnode_find(tree, nidx); 433 if (IS_ERR(node)) 434 return node; 435 436 page = hfs_bmap_get_map_page(node, &ctx, 0); 437 if (IS_ERR(page)) { 438 res = PTR_ERR(page); 439 hfs_bnode_put(node); 440 return ERR_PTR(res); 441 } 442 443 data = kmap_local_page(page); 444 idx = 0; 445 446 for (;;) { 447 while (ctx.len) { 448 byte = data[ctx.off]; 449 if (byte != 0xff) { 450 for (m = 0x80, i = 0; i < 8; m >>= 1, i++) { 451 if (!(byte & m)) { 452 idx += i; 453 data[ctx.off] |= m; 454 set_page_dirty(page); 455 kunmap_local(data); 456 tree->free_nodes--; 457 mark_inode_dirty(tree->inode); 458 hfs_bnode_put(node); 459 return hfs_bnode_create(tree, idx); 460 } 461 } 462 } 463 if (++ctx.off >= PAGE_SIZE) { 464 kunmap_local(data); 465 page = node->page[++ctx.page_idx]; 466 data = kmap_local_page(page); 467 ctx.off = 0; 468 } 469 idx += 8; 470 ctx.len--; 471 } 472 kunmap_local(data); 473 nidx = node->next; 474 if (!nidx) { 475 printk(KERN_DEBUG "create new bmap node...\n"); 476 next_node = hfs_bmap_new_bmap(node, idx); 477 } else 478 next_node = hfs_bnode_find(tree, nidx); 479 hfs_bnode_put(node); 480 if (IS_ERR(next_node)) 481 return next_node; 482 node = next_node; 483 484 page = hfs_bmap_get_map_page(node, &ctx, 0); 485 if (IS_ERR(page)) { 486 res = PTR_ERR(page); 487 hfs_bnode_put(node); 488 return ERR_PTR(res); 489 } 490 data = kmap_local_page(page); 491 } 492 } 493 494 void hfs_bmap_free(struct hfs_bnode *node) 495 { 496 struct hfs_btree *tree; 497 u16 off, len; 498 u32 nidx; 499 int res; 500 501 hfs_dbg("node %u\n", node->this); 502 tree = node->tree; 503 nidx = node->this; 504 node = hfs_bnode_find(tree, 0); 505 if (IS_ERR(node)) 506 return; 507 len = hfs_brec_lenoff(node, 2, &off); 508 while (nidx >= len * 8) { 509 u32 i; 510 511 nidx -= len * 8; 512 i = node->next; 513 if (!i) { 514 /* panic */; 515 pr_crit("unable to free bnode %u. bmap not found!\n", 516 node->this); 517 hfs_bnode_put(node); 518 return; 519 } 520 hfs_bnode_put(node); 521 node = hfs_bnode_find(tree, i); 522 if (IS_ERR(node)) 523 return; 524 if (node->type != HFS_NODE_MAP) { 525 /* panic */; 526 pr_crit("invalid bmap found! (%u,%d)\n", 527 node->this, node->type); 528 hfs_bnode_put(node); 529 return; 530 } 531 len = hfs_brec_lenoff(node, 0, &off); 532 } 533 534 res = hfs_bmap_clear_bit(node, nidx); 535 if (res == -EINVAL) { 536 pr_crit("trying to free free bnode %u(%d)\n", 537 nidx, node->type); 538 } else if (res) { 539 pr_crit("fail to free bnode %u(%d)\n", 540 nidx, node->type); 541 } else { 542 tree->free_nodes++; 543 mark_inode_dirty(tree->inode); 544 } 545 546 hfs_bnode_put(node); 547 } 548