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