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