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