5 * Brad Boyer (flar@allandria.com)
6 * (C) 2003 Ardis Technologies <roman@ardistech.com>
8 * Handle opening/closing btree
11 #include <linux/pagemap.h>
12 #include <linux/slab.h>
13 #include <linux/log2.h>
17 /* Get a reference to a B*Tree and do some initial checks */
18 struct hfs_btree
*hfs_btree_open(struct super_block
*sb
, u32 id
, btree_keycmp keycmp
)
20 struct hfs_btree
*tree
;
21 struct hfs_btree_header_rec
*head
;
22 struct address_space
*mapping
;
26 tree
= kzalloc(sizeof(*tree
), GFP_KERNEL
);
30 mutex_init(&tree
->tree_lock
);
31 spin_lock_init(&tree
->hash_lock
);
32 /* Set the correct compare function */
35 tree
->keycmp
= keycmp
;
37 tree
->inode
= iget_locked(sb
, id
);
40 BUG_ON(!(tree
->inode
->i_state
& I_NEW
));
42 struct hfs_mdb
*mdb
= HFS_SB(sb
)->mdb
;
43 HFS_I(tree
->inode
)->flags
= 0;
44 mutex_init(&HFS_I(tree
->inode
)->extents_lock
);
47 hfs_inode_read_fork(tree
->inode
, mdb
->drXTExtRec
, mdb
->drXTFlSize
,
48 mdb
->drXTFlSize
, be32_to_cpu(mdb
->drXTClpSiz
));
49 if (HFS_I(tree
->inode
)->alloc_blocks
>
50 HFS_I(tree
->inode
)->first_blocks
) {
51 pr_err("invalid btree extent records\n");
52 unlock_new_inode(tree
->inode
);
56 tree
->inode
->i_mapping
->a_ops
= &hfs_btree_aops
;
59 hfs_inode_read_fork(tree
->inode
, mdb
->drCTExtRec
, mdb
->drCTFlSize
,
60 mdb
->drCTFlSize
, be32_to_cpu(mdb
->drCTClpSiz
));
62 if (!HFS_I(tree
->inode
)->first_blocks
) {
63 pr_err("invalid btree extent records (0 size)\n");
64 unlock_new_inode(tree
->inode
);
68 tree
->inode
->i_mapping
->a_ops
= &hfs_btree_aops
;
74 unlock_new_inode(tree
->inode
);
76 mapping
= tree
->inode
->i_mapping
;
77 page
= read_mapping_page(mapping
, 0, NULL
);
82 head
= (struct hfs_btree_header_rec
*)(kmap(page
) + sizeof(struct hfs_bnode_desc
));
83 tree
->root
= be32_to_cpu(head
->root
);
84 tree
->leaf_count
= be32_to_cpu(head
->leaf_count
);
85 tree
->leaf_head
= be32_to_cpu(head
->leaf_head
);
86 tree
->leaf_tail
= be32_to_cpu(head
->leaf_tail
);
87 tree
->node_count
= be32_to_cpu(head
->node_count
);
88 tree
->free_nodes
= be32_to_cpu(head
->free_nodes
);
89 tree
->attributes
= be32_to_cpu(head
->attributes
);
90 tree
->node_size
= be16_to_cpu(head
->node_size
);
91 tree
->max_key_len
= be16_to_cpu(head
->max_key_len
);
92 tree
->depth
= be16_to_cpu(head
->depth
);
94 size
= tree
->node_size
;
95 if (!is_power_of_2(size
))
97 if (!tree
->node_count
)
101 if (tree
->max_key_len
!= HFS_MAX_EXT_KEYLEN
) {
102 pr_err("invalid extent max_key_len %d\n",
108 if (tree
->max_key_len
!= HFS_MAX_CAT_KEYLEN
) {
109 pr_err("invalid catalog max_key_len %d\n",
118 tree
->node_size_shift
= ffs(size
) - 1;
119 tree
->pages_per_bnode
= (tree
->node_size
+ PAGE_SIZE
- 1) >> PAGE_SHIFT
;
128 tree
->inode
->i_mapping
->a_ops
= &hfs_aops
;
135 /* Release resources used by a btree */
136 void hfs_btree_close(struct hfs_btree
*tree
)
138 struct hfs_bnode
*node
;
144 for (i
= 0; i
< NODE_HASH_SIZE
; i
++) {
145 while ((node
= tree
->node_hash
[i
])) {
146 tree
->node_hash
[i
] = node
->next_hash
;
147 if (atomic_read(&node
->refcnt
))
148 pr_err("node %d:%d still has %d user(s)!\n",
149 node
->tree
->cnid
, node
->this,
150 atomic_read(&node
->refcnt
));
151 hfs_bnode_free(node
);
152 tree
->node_hash_cnt
--;
159 void hfs_btree_write(struct hfs_btree
*tree
)
161 struct hfs_btree_header_rec
*head
;
162 struct hfs_bnode
*node
;
165 node
= hfs_bnode_find(tree
, 0);
169 /* Load the header */
170 page
= node
->page
[0];
171 head
= (struct hfs_btree_header_rec
*)(kmap(page
) + sizeof(struct hfs_bnode_desc
));
173 head
->root
= cpu_to_be32(tree
->root
);
174 head
->leaf_count
= cpu_to_be32(tree
->leaf_count
);
175 head
->leaf_head
= cpu_to_be32(tree
->leaf_head
);
176 head
->leaf_tail
= cpu_to_be32(tree
->leaf_tail
);
177 head
->node_count
= cpu_to_be32(tree
->node_count
);
178 head
->free_nodes
= cpu_to_be32(tree
->free_nodes
);
179 head
->attributes
= cpu_to_be32(tree
->attributes
);
180 head
->depth
= cpu_to_be16(tree
->depth
);
183 set_page_dirty(page
);
187 static struct hfs_bnode
*hfs_bmap_new_bmap(struct hfs_bnode
*prev
, u32 idx
)
189 struct hfs_btree
*tree
= prev
->tree
;
190 struct hfs_bnode
*node
;
191 struct hfs_bnode_desc desc
;
194 node
= hfs_bnode_create(tree
, idx
);
198 if (!tree
->free_nodes
)
202 cnid
= cpu_to_be32(idx
);
203 hfs_bnode_write(prev
, &cnid
, offsetof(struct hfs_bnode_desc
, next
), 4);
205 node
->type
= HFS_NODE_MAP
;
207 hfs_bnode_clear(node
, 0, tree
->node_size
);
210 desc
.type
= HFS_NODE_MAP
;
212 desc
.num_recs
= cpu_to_be16(1);
214 hfs_bnode_write(node
, &desc
, 0, sizeof(desc
));
215 hfs_bnode_write_u16(node
, 14, 0x8000);
216 hfs_bnode_write_u16(node
, tree
->node_size
- 2, 14);
217 hfs_bnode_write_u16(node
, tree
->node_size
- 4, tree
->node_size
- 6);
222 struct hfs_bnode
*hfs_bmap_alloc(struct hfs_btree
*tree
)
224 struct hfs_bnode
*node
, *next_node
;
233 while (!tree
->free_nodes
) {
234 struct inode
*inode
= tree
->inode
;
238 res
= hfs_extend_file(inode
);
241 HFS_I(inode
)->phys_size
= inode
->i_size
=
242 (loff_t
)HFS_I(inode
)->alloc_blocks
*
243 HFS_SB(tree
->sb
)->alloc_blksz
;
244 HFS_I(inode
)->fs_blocks
= inode
->i_size
>>
245 tree
->sb
->s_blocksize_bits
;
246 inode_set_bytes(inode
, inode
->i_size
);
247 count
= inode
->i_size
>> tree
->node_size_shift
;
248 tree
->free_nodes
= count
- tree
->node_count
;
249 tree
->node_count
= count
;
253 node
= hfs_bnode_find(tree
, nidx
);
256 len
= hfs_brec_lenoff(node
, 2, &off16
);
259 off
+= node
->page_offset
;
260 pagep
= node
->page
+ (off
>> PAGE_SHIFT
);
269 for (m
= 0x80, i
= 0; i
< 8; m
>>= 1, i
++) {
273 set_page_dirty(*pagep
);
276 mark_inode_dirty(tree
->inode
);
278 return hfs_bnode_create(tree
, idx
);
282 if (++off
>= PAGE_SIZE
) {
284 data
= kmap(*++pagep
);
293 printk(KERN_DEBUG
"create new bmap node...\n");
294 next_node
= hfs_bmap_new_bmap(node
, idx
);
296 next_node
= hfs_bnode_find(tree
, nidx
);
298 if (IS_ERR(next_node
))
302 len
= hfs_brec_lenoff(node
, 0, &off16
);
304 off
+= node
->page_offset
;
305 pagep
= node
->page
+ (off
>> PAGE_SHIFT
);
311 void hfs_bmap_free(struct hfs_bnode
*node
)
313 struct hfs_btree
*tree
;
319 hfs_dbg(BNODE_MOD
, "btree_free_node: %u\n", node
->this);
322 node
= hfs_bnode_find(tree
, 0);
325 len
= hfs_brec_lenoff(node
, 2, &off
);
326 while (nidx
>= len
* 8) {
334 pr_crit("unable to free bnode %u. bmap not found!\n",
338 node
= hfs_bnode_find(tree
, i
);
341 if (node
->type
!= HFS_NODE_MAP
) {
343 pr_crit("invalid bmap found! (%u,%d)\n",
344 node
->this, node
->type
);
348 len
= hfs_brec_lenoff(node
, 0, &off
);
350 off
+= node
->page_offset
+ nidx
/ 8;
351 page
= node
->page
[off
>> PAGE_SHIFT
];
354 m
= 1 << (~nidx
& 7);
357 pr_crit("trying to free free bnode %u(%d)\n",
358 node
->this, node
->type
);
363 data
[off
] = byte
& ~m
;
364 set_page_dirty(page
);
368 mark_inode_dirty(tree
->inode
);
This page took 0.040176 seconds and 6 git commands to generate.