Blame view
fs/hfsplus/btree.c
8.81 KB
1da177e4c Linux-2.6.12-rc2 |
1 2 3 4 5 6 7 8 9 10 11 12 |
/* * linux/fs/hfsplus/btree.c * * Copyright (C) 2001 * Brad Boyer (flar@allandria.com) * (C) 2003 Ardis Technologies <roman@ardistech.com> * * Handle opening/closing btree */ #include <linux/slab.h> #include <linux/pagemap.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 "hfsplus_fs.h" #include "hfsplus_raw.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) { struct hfs_btree *tree; struct hfs_btree_header_rec *head; struct address_space *mapping; |
635253915 iget: stop HFSPLU... |
25 |
struct inode *inode; |
1da177e4c Linux-2.6.12-rc2 |
26 27 |
struct page *page; unsigned int size; |
f8314dc60 [PATCH] fs: Conve... |
28 |
tree = kzalloc(sizeof(*tree), GFP_KERNEL); |
1da177e4c Linux-2.6.12-rc2 |
29 30 |
if (!tree) return NULL; |
1da177e4c Linux-2.6.12-rc2 |
31 |
|
467c3d9cd hfsplus: convert ... |
32 |
mutex_init(&tree->tree_lock); |
1da177e4c Linux-2.6.12-rc2 |
33 |
spin_lock_init(&tree->hash_lock); |
1da177e4c Linux-2.6.12-rc2 |
34 35 |
tree->sb = sb; tree->cnid = id; |
635253915 iget: stop HFSPLU... |
36 37 |
inode = hfsplus_iget(sb, id); if (IS_ERR(inode)) |
1da177e4c Linux-2.6.12-rc2 |
38 |
goto free_tree; |
635253915 iget: stop HFSPLU... |
39 |
tree->inode = inode; |
1da177e4c Linux-2.6.12-rc2 |
40 |
|
ee5271624 hfsplus: fix oops... |
41 42 43 44 45 46 |
if (!HFSPLUS_I(tree->inode)->first_blocks) { printk(KERN_ERR "hfs: invalid btree extent records (0 size). "); goto free_inode; } |
1da177e4c Linux-2.6.12-rc2 |
47 |
mapping = tree->inode->i_mapping; |
090d2b185 [PATCH] read_mapp... |
48 |
page = read_mapping_page(mapping, 0, NULL); |
1da177e4c Linux-2.6.12-rc2 |
49 |
if (IS_ERR(page)) |
ee5271624 hfsplus: fix oops... |
50 |
goto free_inode; |
1da177e4c Linux-2.6.12-rc2 |
51 52 |
/* Load the header */ |
2753cc281 hfsplus: over 80 ... |
53 54 |
head = (struct hfs_btree_header_rec *)(kmap(page) + sizeof(struct hfs_bnode_desc)); |
1da177e4c Linux-2.6.12-rc2 |
55 56 57 58 59 60 61 62 63 64 |
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); |
9250f9259 hfsplus: handle m... |
65 66 67 68 69 70 71 72 73 |
/* Verify the tree and set the correct compare function */ switch (id) { case HFSPLUS_EXT_CNID: if (tree->max_key_len != HFSPLUS_EXT_KEYLEN - sizeof(u16)) { printk(KERN_ERR "hfs: invalid extent max_key_len %d ", tree->max_key_len); goto fail_page; } |
13571a697 hfsplus: validate... |
74 75 76 77 78 |
if (tree->attributes & HFS_TREE_VARIDXKEYS) { printk(KERN_ERR "hfs: invalid extent btree flag "); goto fail_page; } |
2179d372d [PATCH] hfs: add ... |
79 |
tree->keycmp = hfsplus_ext_cmp_key; |
9250f9259 hfsplus: handle m... |
80 81 82 83 84 85 86 87 |
break; case HFSPLUS_CAT_CNID: if (tree->max_key_len != HFSPLUS_CAT_KEYLEN - sizeof(u16)) { printk(KERN_ERR "hfs: invalid catalog max_key_len %d ", tree->max_key_len); goto fail_page; } |
13571a697 hfsplus: validate... |
88 89 90 91 92 |
if (!(tree->attributes & HFS_TREE_VARIDXKEYS)) { printk(KERN_ERR "hfs: invalid catalog btree flag "); goto fail_page; } |
9250f9259 hfsplus: handle m... |
93 |
|
84adede31 hfsplus: use atom... |
94 |
if (test_bit(HFSPLUS_SB_HFSX, &HFSPLUS_SB(sb)->flags) && |
2179d372d [PATCH] hfs: add ... |
95 96 |
(head->key_type == HFSPLUS_KEY_BINARY)) tree->keycmp = hfsplus_cat_bin_cmp_key; |
d45bce8fa HFS+: add custom ... |
97 |
else { |
2179d372d [PATCH] hfs: add ... |
98 |
tree->keycmp = hfsplus_cat_case_cmp_key; |
84adede31 hfsplus: use atom... |
99 |
set_bit(HFSPLUS_SB_CASEFOLD, &HFSPLUS_SB(sb)->flags); |
d45bce8fa HFS+: add custom ... |
100 |
} |
9250f9259 hfsplus: handle m... |
101 102 |
break; default: |
2179d372d [PATCH] hfs: add ... |
103 104 105 106 |
printk(KERN_ERR "hfs: unknown B*Tree requested "); goto fail_page; } |
13571a697 hfsplus: validate... |
107 108 109 110 111 |
if (!(tree->attributes & HFS_TREE_BIGKEYS)) { printk(KERN_ERR "hfs: invalid btree flag "); goto fail_page; } |
1da177e4c Linux-2.6.12-rc2 |
112 |
size = tree->node_size; |
e1b5c1d3d is_power_of_2 in ... |
113 |
if (!is_power_of_2(size)) |
1da177e4c Linux-2.6.12-rc2 |
114 115 116 |
goto fail_page; if (!tree->node_count) goto fail_page; |
9250f9259 hfsplus: handle m... |
117 |
|
1da177e4c Linux-2.6.12-rc2 |
118 |
tree->node_size_shift = ffs(size) - 1; |
2753cc281 hfsplus: over 80 ... |
119 120 121 |
tree->pages_per_bnode = (tree->node_size + PAGE_CACHE_SIZE - 1) >> PAGE_CACHE_SHIFT; |
1da177e4c Linux-2.6.12-rc2 |
122 123 124 125 126 127 |
kunmap(page); page_cache_release(page); return tree; fail_page: |
1da177e4c Linux-2.6.12-rc2 |
128 |
page_cache_release(page); |
ee5271624 hfsplus: fix oops... |
129 |
free_inode: |
9250f9259 hfsplus: handle m... |
130 |
tree->inode->i_mapping->a_ops = &hfsplus_aops; |
1da177e4c Linux-2.6.12-rc2 |
131 |
iput(tree->inode); |
ee5271624 hfsplus: fix oops... |
132 |
free_tree: |
1da177e4c Linux-2.6.12-rc2 |
133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 |
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)) |
2753cc281 hfsplus: over 80 ... |
150 151 152 153 154 |
printk(KERN_CRIT "hfs: node %d:%d " "still has %d user(s)! ", node->tree->cnid, node->this, atomic_read(&node->refcnt)); |
1da177e4c Linux-2.6.12-rc2 |
155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 |
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]; |
2753cc281 hfsplus: over 80 ... |
175 176 |
head = (struct hfs_btree_header_rec *)(kmap(page) + sizeof(struct hfs_bnode_desc)); |
1da177e4c Linux-2.6.12-rc2 |
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 227 228 229 |
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; 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; |
487798df6 hfsplus: fix warn... |
230 231 232 |
unsigned off; u16 off16; u16 len; |
1da177e4c Linux-2.6.12-rc2 |
233 234 235 236 237 |
u8 *data, byte, m; int i; while (!tree->free_nodes) { struct inode *inode = tree->inode; |
6af502de2 hfsplus: fix HFSP... |
238 |
struct hfsplus_inode_info *hip = HFSPLUS_I(inode); |
1da177e4c Linux-2.6.12-rc2 |
239 240 241 242 243 244 |
u32 count; int res; res = hfsplus_file_extend(inode); if (res) return ERR_PTR(res); |
6af502de2 hfsplus: fix HFSP... |
245 246 |
hip->phys_size = inode->i_size = (loff_t)hip->alloc_blocks << |
dd73a01a3 hfsplus: fix HFSP... |
247 |
HFSPLUS_SB(tree->sb)->alloc_blksz_shift; |
6af502de2 hfsplus: fix HFSP... |
248 249 |
hip->fs_blocks = hip->alloc_blocks << HFSPLUS_SB(tree->sb)->fs_shift; |
1da177e4c Linux-2.6.12-rc2 |
250 251 252 253 254 255 256 257 258 259 |
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; |
487798df6 hfsplus: fix warn... |
260 261 |
len = hfs_brec_lenoff(node, 2, &off16); off = off16; |
1da177e4c Linux-2.6.12-rc2 |
262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 |
off += node->page_offset; pagep = node->page + (off >> PAGE_CACHE_SHIFT); data = kmap(*pagep); off &= ~PAGE_CACHE_MASK; 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); |
2753cc281 hfsplus: over 80 ... |
282 283 |
return hfs_bnode_create(tree, idx); |
1da177e4c Linux-2.6.12-rc2 |
284 285 286 287 288 289 290 291 292 293 294 295 296 297 |
} } } if (++off >= PAGE_CACHE_SIZE) { kunmap(*pagep); data = kmap(*++pagep); off = 0; } idx += 8; len--; } kunmap(*pagep); nidx = node->next; if (!nidx) { |
6d1bbfc4c hfsplus: silence ... |
298 299 |
dprint(DBG_BNODE_MOD, "hfs: create new bmap node. "); |
1da177e4c Linux-2.6.12-rc2 |
300 301 302 303 304 305 306 |
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; |
487798df6 hfsplus: fix warn... |
307 308 |
len = hfs_brec_lenoff(node, 0, &off16); off = off16; |
1da177e4c Linux-2.6.12-rc2 |
309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 |
off += node->page_offset; pagep = node->page + (off >> PAGE_CACHE_SHIFT); data = kmap(*pagep); off &= ~PAGE_CACHE_MASK; } } void hfs_bmap_free(struct hfs_bnode *node) { struct hfs_btree *tree; struct page *page; u16 off, len; u32 nidx; u8 *data, byte, m; dprint(DBG_BNODE_MOD, "btree_free_node: %u ", node->this); |
0bf3ba538 BUG_ON() Conversi... |
326 |
BUG_ON(!node->this); |
1da177e4c Linux-2.6.12-rc2 |
327 328 329 330 331 332 333 334 335 336 337 338 339 340 |
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 */; |
2753cc281 hfsplus: over 80 ... |
341 342 343 344 |
printk(KERN_CRIT "hfs: unable to free bnode %u. " "bmap not found! ", node->this); |
1da177e4c Linux-2.6.12-rc2 |
345 346 347 348 349 350 351 |
return; } node = hfs_bnode_find(tree, i); if (IS_ERR(node)) return; if (node->type != HFS_NODE_MAP) { /* panic */; |
2753cc281 hfsplus: over 80 ... |
352 353 354 355 |
printk(KERN_CRIT "hfs: invalid bmap found! " "(%u,%d) ", node->this, node->type); |
1da177e4c Linux-2.6.12-rc2 |
356 357 358 359 360 361 362 363 364 365 366 367 |
hfs_bnode_put(node); return; } len = hfs_brec_lenoff(node, 0, &off); } off += node->page_offset + nidx / 8; page = node->page[off >> PAGE_CACHE_SHIFT]; data = kmap(page); off &= ~PAGE_CACHE_MASK; m = 1 << (~nidx & 7); byte = data[off]; if (!(byte & m)) { |
2753cc281 hfsplus: over 80 ... |
368 369 370 371 |
printk(KERN_CRIT "hfs: trying to free free bnode " "%u(%d) ", node->this, node->type); |
1da177e4c Linux-2.6.12-rc2 |
372 373 374 375 376 377 378 379 380 381 382 |
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); } |