2 * linux/fs/hfsplus/btree.c
5 * Brad Boyer (flar@allandria.com)
6 * (C) 2003 Ardis Technologies <roman@ardistech.com>
8 * Handle opening/closing btree
11 #include <linux/slab.h>
12 #include <linux/pagemap.h>
13 #include <linux/log2.h>
15 #include "hfsplus_fs.h"
16 #include "hfsplus_raw.h"
19 /* Get a reference to a B*Tree and do some initial checks */
20 struct hfs_btree
*hfs_btree_open(struct super_block
*sb
, u32 id
)
22 struct hfs_btree
*tree
;
23 struct hfs_btree_header_rec
*head
;
24 struct address_space
*mapping
;
29 tree
= kzalloc(sizeof(*tree
), GFP_KERNEL
);
33 init_MUTEX(&tree
->tree_lock
);
34 spin_lock_init(&tree
->hash_lock
);
37 inode
= hfsplus_iget(sb
, id
);
42 mapping
= tree
->inode
->i_mapping
;
43 page
= read_mapping_page(mapping
, 0, NULL
);
48 head
= (struct hfs_btree_header_rec
*)(kmap(page
) + sizeof(struct hfs_bnode_desc
));
49 tree
->root
= be32_to_cpu(head
->root
);
50 tree
->leaf_count
= be32_to_cpu(head
->leaf_count
);
51 tree
->leaf_head
= be32_to_cpu(head
->leaf_head
);
52 tree
->leaf_tail
= be32_to_cpu(head
->leaf_tail
);
53 tree
->node_count
= be32_to_cpu(head
->node_count
);
54 tree
->free_nodes
= be32_to_cpu(head
->free_nodes
);
55 tree
->attributes
= be32_to_cpu(head
->attributes
);
56 tree
->node_size
= be16_to_cpu(head
->node_size
);
57 tree
->max_key_len
= be16_to_cpu(head
->max_key_len
);
58 tree
->depth
= be16_to_cpu(head
->depth
);
60 /* Set the correct compare function */
61 if (id
== HFSPLUS_EXT_CNID
) {
62 tree
->keycmp
= hfsplus_ext_cmp_key
;
63 } else if (id
== HFSPLUS_CAT_CNID
) {
64 if ((HFSPLUS_SB(sb
).flags
& HFSPLUS_SB_HFSX
) &&
65 (head
->key_type
== HFSPLUS_KEY_BINARY
))
66 tree
->keycmp
= hfsplus_cat_bin_cmp_key
;
68 tree
->keycmp
= hfsplus_cat_case_cmp_key
;
69 HFSPLUS_SB(sb
).flags
|= HFSPLUS_SB_CASEFOLD
;
72 printk(KERN_ERR
"hfs: unknown B*Tree requested\n");
76 size
= tree
->node_size
;
77 if (!is_power_of_2(size
))
79 if (!tree
->node_count
)
81 tree
->node_size_shift
= ffs(size
) - 1;
83 tree
->pages_per_bnode
= (tree
->node_size
+ PAGE_CACHE_SIZE
- 1) >> PAGE_CACHE_SHIFT
;
86 page_cache_release(page
);
90 tree
->inode
->i_mapping
->a_ops
= &hfsplus_aops
;
91 page_cache_release(page
);
98 /* Release resources used by a btree */
99 void hfs_btree_close(struct hfs_btree
*tree
)
101 struct hfs_bnode
*node
;
107 for (i
= 0; i
< NODE_HASH_SIZE
; i
++) {
108 while ((node
= tree
->node_hash
[i
])) {
109 tree
->node_hash
[i
] = node
->next_hash
;
110 if (atomic_read(&node
->refcnt
))
111 printk(KERN_CRIT
"hfs: node %d:%d still has %d user(s)!\n",
112 node
->tree
->cnid
, node
->this, atomic_read(&node
->refcnt
));
113 hfs_bnode_free(node
);
114 tree
->node_hash_cnt
--;
121 void hfs_btree_write(struct hfs_btree
*tree
)
123 struct hfs_btree_header_rec
*head
;
124 struct hfs_bnode
*node
;
127 node
= hfs_bnode_find(tree
, 0);
131 /* Load the header */
132 page
= node
->page
[0];
133 head
= (struct hfs_btree_header_rec
*)(kmap(page
) + sizeof(struct hfs_bnode_desc
));
135 head
->root
= cpu_to_be32(tree
->root
);
136 head
->leaf_count
= cpu_to_be32(tree
->leaf_count
);
137 head
->leaf_head
= cpu_to_be32(tree
->leaf_head
);
138 head
->leaf_tail
= cpu_to_be32(tree
->leaf_tail
);
139 head
->node_count
= cpu_to_be32(tree
->node_count
);
140 head
->free_nodes
= cpu_to_be32(tree
->free_nodes
);
141 head
->attributes
= cpu_to_be32(tree
->attributes
);
142 head
->depth
= cpu_to_be16(tree
->depth
);
145 set_page_dirty(page
);
149 static struct hfs_bnode
*hfs_bmap_new_bmap(struct hfs_bnode
*prev
, u32 idx
)
151 struct hfs_btree
*tree
= prev
->tree
;
152 struct hfs_bnode
*node
;
153 struct hfs_bnode_desc desc
;
156 node
= hfs_bnode_create(tree
, idx
);
162 cnid
= cpu_to_be32(idx
);
163 hfs_bnode_write(prev
, &cnid
, offsetof(struct hfs_bnode_desc
, next
), 4);
165 node
->type
= HFS_NODE_MAP
;
167 hfs_bnode_clear(node
, 0, tree
->node_size
);
170 desc
.type
= HFS_NODE_MAP
;
172 desc
.num_recs
= cpu_to_be16(1);
174 hfs_bnode_write(node
, &desc
, 0, sizeof(desc
));
175 hfs_bnode_write_u16(node
, 14, 0x8000);
176 hfs_bnode_write_u16(node
, tree
->node_size
- 2, 14);
177 hfs_bnode_write_u16(node
, tree
->node_size
- 4, tree
->node_size
- 6);
182 struct hfs_bnode
*hfs_bmap_alloc(struct hfs_btree
*tree
)
184 struct hfs_bnode
*node
, *next_node
;
193 while (!tree
->free_nodes
) {
194 struct inode
*inode
= tree
->inode
;
198 res
= hfsplus_file_extend(inode
);
201 HFSPLUS_I(inode
).phys_size
= inode
->i_size
=
202 (loff_t
)HFSPLUS_I(inode
).alloc_blocks
<<
203 HFSPLUS_SB(tree
->sb
).alloc_blksz_shift
;
204 HFSPLUS_I(inode
).fs_blocks
= HFSPLUS_I(inode
).alloc_blocks
<<
205 HFSPLUS_SB(tree
->sb
).fs_shift
;
206 inode_set_bytes(inode
, inode
->i_size
);
207 count
= inode
->i_size
>> tree
->node_size_shift
;
208 tree
->free_nodes
= count
- tree
->node_count
;
209 tree
->node_count
= count
;
213 node
= hfs_bnode_find(tree
, nidx
);
216 len
= hfs_brec_lenoff(node
, 2, &off16
);
219 off
+= node
->page_offset
;
220 pagep
= node
->page
+ (off
>> PAGE_CACHE_SHIFT
);
222 off
&= ~PAGE_CACHE_MASK
;
229 for (m
= 0x80, i
= 0; i
< 8; m
>>= 1, i
++) {
233 set_page_dirty(*pagep
);
236 mark_inode_dirty(tree
->inode
);
238 return hfs_bnode_create(tree
, idx
);
242 if (++off
>= PAGE_CACHE_SIZE
) {
244 data
= kmap(*++pagep
);
253 printk(KERN_DEBUG
"hfs: create new bmap node...\n");
254 next_node
= hfs_bmap_new_bmap(node
, idx
);
256 next_node
= hfs_bnode_find(tree
, nidx
);
258 if (IS_ERR(next_node
))
262 len
= hfs_brec_lenoff(node
, 0, &off16
);
264 off
+= node
->page_offset
;
265 pagep
= node
->page
+ (off
>> PAGE_CACHE_SHIFT
);
267 off
&= ~PAGE_CACHE_MASK
;
271 void hfs_bmap_free(struct hfs_bnode
*node
)
273 struct hfs_btree
*tree
;
279 dprint(DBG_BNODE_MOD
, "btree_free_node: %u\n", node
->this);
283 node
= hfs_bnode_find(tree
, 0);
286 len
= hfs_brec_lenoff(node
, 2, &off
);
287 while (nidx
>= len
* 8) {
295 printk(KERN_CRIT
"hfs: unable to free bnode %u. bmap not found!\n", node
->this);
298 node
= hfs_bnode_find(tree
, i
);
301 if (node
->type
!= HFS_NODE_MAP
) {
303 printk(KERN_CRIT
"hfs: invalid bmap found! (%u,%d)\n", node
->this, node
->type
);
307 len
= hfs_brec_lenoff(node
, 0, &off
);
309 off
+= node
->page_offset
+ nidx
/ 8;
310 page
= node
->page
[off
>> PAGE_CACHE_SHIFT
];
312 off
&= ~PAGE_CACHE_MASK
;
313 m
= 1 << (~nidx
& 7);
316 printk(KERN_CRIT
"hfs: trying to free free bnode %u(%d)\n", node
->this, node
->type
);
321 data
[off
] = byte
& ~m
;
322 set_page_dirty(page
);
326 mark_inode_dirty(tree
->inode
);
This page took 0.03974 seconds and 5 git commands to generate.