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/log2.h>
16 /* Get a reference to a B*Tree and do some initial checks */
17 struct hfs_btree
*hfs_btree_open(struct super_block
*sb
, u32 id
, btree_keycmp keycmp
)
19 struct hfs_btree
*tree
;
20 struct hfs_btree_header_rec
*head
;
21 struct address_space
*mapping
;
25 tree
= kzalloc(sizeof(*tree
), GFP_KERNEL
);
29 init_MUTEX(&tree
->tree_lock
);
30 spin_lock_init(&tree
->hash_lock
);
31 /* Set the correct compare function */
34 tree
->keycmp
= keycmp
;
36 tree
->inode
= iget_locked(sb
, id
);
39 BUG_ON(!(tree
->inode
->i_state
& I_NEW
));
41 struct hfs_mdb
*mdb
= HFS_SB(sb
)->mdb
;
42 HFS_I(tree
->inode
)->flags
= 0;
43 init_MUTEX(&HFS_I(tree
->inode
)->extents_lock
);
46 hfs_inode_read_fork(tree
->inode
, mdb
->drXTExtRec
, mdb
->drXTFlSize
,
47 mdb
->drXTFlSize
, be32_to_cpu(mdb
->drXTClpSiz
));
48 tree
->inode
->i_mapping
->a_ops
= &hfs_btree_aops
;
51 hfs_inode_read_fork(tree
->inode
, mdb
->drCTExtRec
, mdb
->drCTFlSize
,
52 mdb
->drCTFlSize
, be32_to_cpu(mdb
->drCTClpSiz
));
53 tree
->inode
->i_mapping
->a_ops
= &hfs_btree_aops
;
59 unlock_new_inode(tree
->inode
);
61 mapping
= tree
->inode
->i_mapping
;
62 page
= read_mapping_page(mapping
, 0, NULL
);
67 head
= (struct hfs_btree_header_rec
*)(kmap(page
) + sizeof(struct hfs_bnode_desc
));
68 tree
->root
= be32_to_cpu(head
->root
);
69 tree
->leaf_count
= be32_to_cpu(head
->leaf_count
);
70 tree
->leaf_head
= be32_to_cpu(head
->leaf_head
);
71 tree
->leaf_tail
= be32_to_cpu(head
->leaf_tail
);
72 tree
->node_count
= be32_to_cpu(head
->node_count
);
73 tree
->free_nodes
= be32_to_cpu(head
->free_nodes
);
74 tree
->attributes
= be32_to_cpu(head
->attributes
);
75 tree
->node_size
= be16_to_cpu(head
->node_size
);
76 tree
->max_key_len
= be16_to_cpu(head
->max_key_len
);
77 tree
->depth
= be16_to_cpu(head
->depth
);
79 size
= tree
->node_size
;
80 if (!is_power_of_2(size
))
82 if (!tree
->node_count
)
84 if ((id
== HFS_EXT_CNID
) && (tree
->max_key_len
!= HFS_MAX_EXT_KEYLEN
)) {
85 printk(KERN_ERR
"hfs: invalid extent max_key_len %d\n",
89 if ((id
== HFS_CAT_CNID
) && (tree
->max_key_len
!= HFS_MAX_CAT_KEYLEN
)) {
90 printk(KERN_ERR
"hfs: invalid catalog max_key_len %d\n",
95 tree
->node_size_shift
= ffs(size
) - 1;
96 tree
->pages_per_bnode
= (tree
->node_size
+ PAGE_CACHE_SIZE
- 1) >> PAGE_CACHE_SHIFT
;
99 page_cache_release(page
);
103 page_cache_release(page
);
105 tree
->inode
->i_mapping
->a_ops
= &hfs_aops
;
111 /* Release resources used by a btree */
112 void hfs_btree_close(struct hfs_btree
*tree
)
114 struct hfs_bnode
*node
;
120 for (i
= 0; i
< NODE_HASH_SIZE
; i
++) {
121 while ((node
= tree
->node_hash
[i
])) {
122 tree
->node_hash
[i
] = node
->next_hash
;
123 if (atomic_read(&node
->refcnt
))
124 printk(KERN_ERR
"hfs: node %d:%d still has %d user(s)!\n",
125 node
->tree
->cnid
, node
->this, atomic_read(&node
->refcnt
));
126 hfs_bnode_free(node
);
127 tree
->node_hash_cnt
--;
134 void hfs_btree_write(struct hfs_btree
*tree
)
136 struct hfs_btree_header_rec
*head
;
137 struct hfs_bnode
*node
;
140 node
= hfs_bnode_find(tree
, 0);
144 /* Load the header */
145 page
= node
->page
[0];
146 head
= (struct hfs_btree_header_rec
*)(kmap(page
) + sizeof(struct hfs_bnode_desc
));
148 head
->root
= cpu_to_be32(tree
->root
);
149 head
->leaf_count
= cpu_to_be32(tree
->leaf_count
);
150 head
->leaf_head
= cpu_to_be32(tree
->leaf_head
);
151 head
->leaf_tail
= cpu_to_be32(tree
->leaf_tail
);
152 head
->node_count
= cpu_to_be32(tree
->node_count
);
153 head
->free_nodes
= cpu_to_be32(tree
->free_nodes
);
154 head
->attributes
= cpu_to_be32(tree
->attributes
);
155 head
->depth
= cpu_to_be16(tree
->depth
);
158 set_page_dirty(page
);
162 static struct hfs_bnode
*hfs_bmap_new_bmap(struct hfs_bnode
*prev
, u32 idx
)
164 struct hfs_btree
*tree
= prev
->tree
;
165 struct hfs_bnode
*node
;
166 struct hfs_bnode_desc desc
;
169 node
= hfs_bnode_create(tree
, idx
);
173 if (!tree
->free_nodes
)
177 cnid
= cpu_to_be32(idx
);
178 hfs_bnode_write(prev
, &cnid
, offsetof(struct hfs_bnode_desc
, next
), 4);
180 node
->type
= HFS_NODE_MAP
;
182 hfs_bnode_clear(node
, 0, tree
->node_size
);
185 desc
.type
= HFS_NODE_MAP
;
187 desc
.num_recs
= cpu_to_be16(1);
189 hfs_bnode_write(node
, &desc
, 0, sizeof(desc
));
190 hfs_bnode_write_u16(node
, 14, 0x8000);
191 hfs_bnode_write_u16(node
, tree
->node_size
- 2, 14);
192 hfs_bnode_write_u16(node
, tree
->node_size
- 4, tree
->node_size
- 6);
197 struct hfs_bnode
*hfs_bmap_alloc(struct hfs_btree
*tree
)
199 struct hfs_bnode
*node
, *next_node
;
206 while (!tree
->free_nodes
) {
207 struct inode
*inode
= tree
->inode
;
211 res
= hfs_extend_file(inode
);
214 HFS_I(inode
)->phys_size
= inode
->i_size
=
215 (loff_t
)HFS_I(inode
)->alloc_blocks
*
216 HFS_SB(tree
->sb
)->alloc_blksz
;
217 HFS_I(inode
)->fs_blocks
= inode
->i_size
>>
218 tree
->sb
->s_blocksize_bits
;
219 inode_set_bytes(inode
, inode
->i_size
);
220 count
= inode
->i_size
>> tree
->node_size_shift
;
221 tree
->free_nodes
= count
- tree
->node_count
;
222 tree
->node_count
= count
;
226 node
= hfs_bnode_find(tree
, nidx
);
229 len
= hfs_brec_lenoff(node
, 2, &off
);
231 off
+= node
->page_offset
;
232 pagep
= node
->page
+ (off
>> PAGE_CACHE_SHIFT
);
234 off
&= ~PAGE_CACHE_MASK
;
241 for (m
= 0x80, i
= 0; i
< 8; m
>>= 1, i
++) {
245 set_page_dirty(*pagep
);
248 mark_inode_dirty(tree
->inode
);
250 return hfs_bnode_create(tree
, idx
);
254 if (++off
>= PAGE_CACHE_SIZE
) {
256 data
= kmap(*++pagep
);
265 printk(KERN_DEBUG
"hfs: create new bmap node...\n");
266 next_node
= hfs_bmap_new_bmap(node
, idx
);
268 next_node
= hfs_bnode_find(tree
, nidx
);
270 if (IS_ERR(next_node
))
274 len
= hfs_brec_lenoff(node
, 0, &off
);
275 off
+= node
->page_offset
;
276 pagep
= node
->page
+ (off
>> PAGE_CACHE_SHIFT
);
278 off
&= ~PAGE_CACHE_MASK
;
282 void hfs_bmap_free(struct hfs_bnode
*node
)
284 struct hfs_btree
*tree
;
290 dprint(DBG_BNODE_MOD
, "btree_free_node: %u\n", node
->this);
293 node
= hfs_bnode_find(tree
, 0);
296 len
= hfs_brec_lenoff(node
, 2, &off
);
297 while (nidx
>= len
* 8) {
305 printk(KERN_CRIT
"hfs: unable to free bnode %u. bmap not found!\n", node
->this);
308 node
= hfs_bnode_find(tree
, i
);
311 if (node
->type
!= HFS_NODE_MAP
) {
313 printk(KERN_CRIT
"hfs: invalid bmap found! (%u,%d)\n", node
->this, node
->type
);
317 len
= hfs_brec_lenoff(node
, 0, &off
);
319 off
+= node
->page_offset
+ nidx
/ 8;
320 page
= node
->page
[off
>> PAGE_CACHE_SHIFT
];
322 off
&= ~PAGE_CACHE_MASK
;
323 m
= 1 << (~nidx
& 7);
326 printk(KERN_CRIT
"hfs: trying to free free bnode %u(%d)\n", node
->this, node
->type
);
331 data
[off
] = byte
& ~m
;
332 set_page_dirty(page
);
336 mark_inode_dirty(tree
->inode
);