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