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 /* Get a reference to a B*Tree and do some initial checks */ 19 struct hfs_btree *hfs_btree_open(struct super_block *sb, u32 id, btree_keycmp keycmp) 20 { 21 struct hfs_btree *tree; 22 struct hfs_btree_header_rec *head; 23 struct address_space *mapping; 24 struct folio *folio; 25 struct buffer_head *bh; 26 unsigned int size; 27 u16 dblock; 28 sector_t start_block; 29 loff_t offset; 30 31 tree = kzalloc(sizeof(*tree), GFP_KERNEL); 32 if (!tree) 33 return NULL; 34 35 mutex_init(&tree->tree_lock); 36 spin_lock_init(&tree->hash_lock); 37 /* Set the correct compare function */ 38 tree->sb = sb; 39 tree->cnid = id; 40 tree->keycmp = keycmp; 41 42 tree->inode = iget_locked(sb, id); 43 if (!tree->inode) 44 goto free_tree; 45 BUG_ON(!(tree->inode->i_state & I_NEW)); 46 { 47 struct hfs_mdb *mdb = HFS_SB(sb)->mdb; 48 HFS_I(tree->inode)->flags = 0; 49 mutex_init(&HFS_I(tree->inode)->extents_lock); 50 switch (id) { 51 case HFS_EXT_CNID: 52 hfs_inode_read_fork(tree->inode, mdb->drXTExtRec, mdb->drXTFlSize, 53 mdb->drXTFlSize, be32_to_cpu(mdb->drXTClpSiz)); 54 if (HFS_I(tree->inode)->alloc_blocks > 55 HFS_I(tree->inode)->first_blocks) { 56 pr_err("invalid btree extent records\n"); 57 unlock_new_inode(tree->inode); 58 goto free_inode; 59 } 60 61 tree->inode->i_mapping->a_ops = &hfs_btree_aops; 62 break; 63 case HFS_CAT_CNID: 64 hfs_inode_read_fork(tree->inode, mdb->drCTExtRec, mdb->drCTFlSize, 65 mdb->drCTFlSize, be32_to_cpu(mdb->drCTClpSiz)); 66 67 if (!HFS_I(tree->inode)->first_blocks) { 68 pr_err("invalid btree extent records (0 size)\n"); 69 unlock_new_inode(tree->inode); 70 goto free_inode; 71 } 72 73 tree->inode->i_mapping->a_ops = &hfs_btree_aops; 74 break; 75 default: 76 BUG(); 77 } 78 } 79 unlock_new_inode(tree->inode); 80 81 mapping = tree->inode->i_mapping; 82 folio = filemap_grab_folio(mapping, 0); 83 if (IS_ERR(folio)) 84 goto free_inode; 85 86 folio_zero_range(folio, 0, folio_size(folio)); 87 88 dblock = hfs_ext_find_block(HFS_I(tree->inode)->first_extents, 0); 89 start_block = HFS_SB(sb)->fs_start + (dblock * HFS_SB(sb)->fs_div); 90 91 size = folio_size(folio); 92 offset = 0; 93 while (size > 0) { 94 size_t len; 95 96 bh = sb_bread(sb, start_block); 97 if (!bh) { 98 pr_err("unable to read tree header\n"); 99 goto put_folio; 100 } 101 102 len = min_t(size_t, folio_size(folio), sb->s_blocksize); 103 memcpy_to_folio(folio, offset, bh->b_data, sb->s_blocksize); 104 105 brelse(bh); 106 107 start_block++; 108 offset += len; 109 size -= len; 110 } 111 112 folio_mark_uptodate(folio); 113 114 /* Load the header */ 115 head = (struct hfs_btree_header_rec *)(kmap_local_folio(folio, 0) + 116 sizeof(struct hfs_bnode_desc)); 117 tree->root = be32_to_cpu(head->root); 118 tree->leaf_count = be32_to_cpu(head->leaf_count); 119 tree->leaf_head = be32_to_cpu(head->leaf_head); 120 tree->leaf_tail = be32_to_cpu(head->leaf_tail); 121 tree->node_count = be32_to_cpu(head->node_count); 122 tree->free_nodes = be32_to_cpu(head->free_nodes); 123 tree->attributes = be32_to_cpu(head->attributes); 124 tree->node_size = be16_to_cpu(head->node_size); 125 tree->max_key_len = be16_to_cpu(head->max_key_len); 126 tree->depth = be16_to_cpu(head->depth); 127 128 size = tree->node_size; 129 if (!is_power_of_2(size)) 130 goto fail_folio; 131 if (!tree->node_count) 132 goto fail_folio; 133 switch (id) { 134 case HFS_EXT_CNID: 135 if (tree->max_key_len != HFS_MAX_EXT_KEYLEN) { 136 pr_err("invalid extent max_key_len %d\n", 137 tree->max_key_len); 138 goto fail_folio; 139 } 140 break; 141 case HFS_CAT_CNID: 142 if (tree->max_key_len != HFS_MAX_CAT_KEYLEN) { 143 pr_err("invalid catalog max_key_len %d\n", 144 tree->max_key_len); 145 goto fail_folio; 146 } 147 break; 148 default: 149 BUG(); 150 } 151 152 tree->node_size_shift = ffs(size) - 1; 153 tree->pages_per_bnode = (tree->node_size + PAGE_SIZE - 1) >> PAGE_SHIFT; 154 155 kunmap_local(head); 156 folio_unlock(folio); 157 folio_put(folio); 158 return tree; 159 160 fail_folio: 161 kunmap_local(head); 162 put_folio: 163 folio_unlock(folio); 164 folio_put(folio); 165 free_inode: 166 tree->inode->i_mapping->a_ops = &hfs_aops; 167 iput(tree->inode); 168 free_tree: 169 kfree(tree); 170 return NULL; 171 } 172 173 /* Release resources used by a btree */ 174 void hfs_btree_close(struct hfs_btree *tree) 175 { 176 struct hfs_bnode *node; 177 int i; 178 179 if (!tree) 180 return; 181 182 for (i = 0; i < NODE_HASH_SIZE; i++) { 183 while ((node = tree->node_hash[i])) { 184 tree->node_hash[i] = node->next_hash; 185 if (atomic_read(&node->refcnt)) 186 pr_err("node %d:%d still has %d user(s)!\n", 187 node->tree->cnid, node->this, 188 atomic_read(&node->refcnt)); 189 hfs_bnode_free(node); 190 tree->node_hash_cnt--; 191 } 192 } 193 iput(tree->inode); 194 kfree(tree); 195 } 196 197 void hfs_btree_write(struct hfs_btree *tree) 198 { 199 struct hfs_btree_header_rec *head; 200 struct hfs_bnode *node; 201 struct page *page; 202 203 node = hfs_bnode_find(tree, 0); 204 if (IS_ERR(node)) 205 /* panic? */ 206 return; 207 /* Load the header */ 208 page = node->page[0]; 209 head = (struct hfs_btree_header_rec *)(kmap_local_page(page) + 210 sizeof(struct hfs_bnode_desc)); 211 212 head->root = cpu_to_be32(tree->root); 213 head->leaf_count = cpu_to_be32(tree->leaf_count); 214 head->leaf_head = cpu_to_be32(tree->leaf_head); 215 head->leaf_tail = cpu_to_be32(tree->leaf_tail); 216 head->node_count = cpu_to_be32(tree->node_count); 217 head->free_nodes = cpu_to_be32(tree->free_nodes); 218 head->attributes = cpu_to_be32(tree->attributes); 219 head->depth = cpu_to_be16(tree->depth); 220 221 kunmap_local(head); 222 set_page_dirty(page); 223 hfs_bnode_put(node); 224 } 225 226 static struct hfs_bnode *hfs_bmap_new_bmap(struct hfs_bnode *prev, u32 idx) 227 { 228 struct hfs_btree *tree = prev->tree; 229 struct hfs_bnode *node; 230 struct hfs_bnode_desc desc; 231 __be32 cnid; 232 233 node = hfs_bnode_create(tree, idx); 234 if (IS_ERR(node)) 235 return node; 236 237 if (!tree->free_nodes) 238 panic("FIXME!!!"); 239 tree->free_nodes--; 240 prev->next = idx; 241 cnid = cpu_to_be32(idx); 242 hfs_bnode_write(prev, &cnid, offsetof(struct hfs_bnode_desc, next), 4); 243 244 node->type = HFS_NODE_MAP; 245 node->num_recs = 1; 246 hfs_bnode_clear(node, 0, tree->node_size); 247 desc.next = 0; 248 desc.prev = 0; 249 desc.type = HFS_NODE_MAP; 250 desc.height = 0; 251 desc.num_recs = cpu_to_be16(1); 252 desc.reserved = 0; 253 hfs_bnode_write(node, &desc, 0, sizeof(desc)); 254 hfs_bnode_write_u16(node, 14, 0x8000); 255 hfs_bnode_write_u16(node, tree->node_size - 2, 14); 256 hfs_bnode_write_u16(node, tree->node_size - 4, tree->node_size - 6); 257 258 return node; 259 } 260 261 /* Make sure @tree has enough space for the @rsvd_nodes */ 262 int hfs_bmap_reserve(struct hfs_btree *tree, int rsvd_nodes) 263 { 264 struct inode *inode = tree->inode; 265 u32 count; 266 int res; 267 268 while (tree->free_nodes < rsvd_nodes) { 269 res = hfs_extend_file(inode); 270 if (res) 271 return res; 272 HFS_I(inode)->phys_size = inode->i_size = 273 (loff_t)HFS_I(inode)->alloc_blocks * 274 HFS_SB(tree->sb)->alloc_blksz; 275 HFS_I(inode)->fs_blocks = inode->i_size >> 276 tree->sb->s_blocksize_bits; 277 inode_set_bytes(inode, inode->i_size); 278 count = inode->i_size >> tree->node_size_shift; 279 tree->free_nodes += count - tree->node_count; 280 tree->node_count = count; 281 } 282 return 0; 283 } 284 285 struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree) 286 { 287 struct hfs_bnode *node, *next_node; 288 struct page **pagep; 289 u32 nidx, idx; 290 unsigned off; 291 u16 off16; 292 u16 len; 293 u8 *data, byte, m; 294 int i, res; 295 296 res = hfs_bmap_reserve(tree, 1); 297 if (res) 298 return ERR_PTR(res); 299 300 nidx = 0; 301 node = hfs_bnode_find(tree, nidx); 302 if (IS_ERR(node)) 303 return node; 304 len = hfs_brec_lenoff(node, 2, &off16); 305 off = off16; 306 307 off += node->page_offset; 308 pagep = node->page + (off >> PAGE_SHIFT); 309 data = kmap_local_page(*pagep); 310 off &= ~PAGE_MASK; 311 idx = 0; 312 313 for (;;) { 314 while (len) { 315 byte = data[off]; 316 if (byte != 0xff) { 317 for (m = 0x80, i = 0; i < 8; m >>= 1, i++) { 318 if (!(byte & m)) { 319 idx += i; 320 data[off] |= m; 321 set_page_dirty(*pagep); 322 kunmap_local(data); 323 tree->free_nodes--; 324 mark_inode_dirty(tree->inode); 325 hfs_bnode_put(node); 326 return hfs_bnode_create(tree, idx); 327 } 328 } 329 } 330 if (++off >= PAGE_SIZE) { 331 kunmap_local(data); 332 data = kmap_local_page(*++pagep); 333 off = 0; 334 } 335 idx += 8; 336 len--; 337 } 338 kunmap_local(data); 339 nidx = node->next; 340 if (!nidx) { 341 printk(KERN_DEBUG "create new bmap node...\n"); 342 next_node = hfs_bmap_new_bmap(node, idx); 343 } else 344 next_node = hfs_bnode_find(tree, nidx); 345 hfs_bnode_put(node); 346 if (IS_ERR(next_node)) 347 return next_node; 348 node = next_node; 349 350 len = hfs_brec_lenoff(node, 0, &off16); 351 off = off16; 352 off += node->page_offset; 353 pagep = node->page + (off >> PAGE_SHIFT); 354 data = kmap_local_page(*pagep); 355 off &= ~PAGE_MASK; 356 } 357 } 358 359 void hfs_bmap_free(struct hfs_bnode *node) 360 { 361 struct hfs_btree *tree; 362 struct page *page; 363 u16 off, len; 364 u32 nidx; 365 u8 *data, byte, m; 366 367 hfs_dbg(BNODE_MOD, "btree_free_node: %u\n", node->this); 368 tree = node->tree; 369 nidx = node->this; 370 node = hfs_bnode_find(tree, 0); 371 if (IS_ERR(node)) 372 return; 373 len = hfs_brec_lenoff(node, 2, &off); 374 while (nidx >= len * 8) { 375 u32 i; 376 377 nidx -= len * 8; 378 i = node->next; 379 if (!i) { 380 /* panic */; 381 pr_crit("unable to free bnode %u. bmap not found!\n", 382 node->this); 383 hfs_bnode_put(node); 384 return; 385 } 386 hfs_bnode_put(node); 387 node = hfs_bnode_find(tree, i); 388 if (IS_ERR(node)) 389 return; 390 if (node->type != HFS_NODE_MAP) { 391 /* panic */; 392 pr_crit("invalid bmap found! (%u,%d)\n", 393 node->this, node->type); 394 hfs_bnode_put(node); 395 return; 396 } 397 len = hfs_brec_lenoff(node, 0, &off); 398 } 399 off += node->page_offset + nidx / 8; 400 page = node->page[off >> PAGE_SHIFT]; 401 data = kmap_local_page(page); 402 off &= ~PAGE_MASK; 403 m = 1 << (~nidx & 7); 404 byte = data[off]; 405 if (!(byte & m)) { 406 pr_crit("trying to free free bnode %u(%d)\n", 407 node->this, node->type); 408 kunmap_local(data); 409 hfs_bnode_put(node); 410 return; 411 } 412 data[off] = byte & ~m; 413 set_page_dirty(page); 414 kunmap_local(data); 415 hfs_bnode_put(node); 416 tree->free_nodes++; 417 mark_inode_dirty(tree->inode); 418 } 419