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