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