2 * linux/fs/hfs/balloc.c
4 * Copyright (C) 1995-1997 Paul H. Hargrove
5 * This file may be distributed under the terms of the GNU Public License.
7 * hfs_bnode_alloc() and hfs_bnode_bitop() are based on GPLed code
8 * Copyright (C) 1995 Michael Dreher
10 * This file contains the code to create and destroy nodes
11 * in the B-tree structure.
13 * "XXX" in a comment is a note to myself to consider changing something.
15 * In function preconditions the term "valid" applied to a pointer to
16 * a structure means that the pointer is non-NULL and the structure it
17 * points to has all fields initialized to consistent values.
19 * The code in this file initializes some structures which contain
20 * pointers by calling memset(&foo, 0, sizeof(foo)).
21 * This produces the desired behavior only due to the non-ANSI
22 * assumption that the machine representation of NULL is all zeros.
25 #include "hfs_btree.h"
27 /*================ File-local functions ================*/
32 * Get a buffer for a new node with out reading it from disk.
34 static hfs_buffer
get_new_node(struct hfs_btree
*tree
, hfs_u32 node
)
37 hfs_buffer retval
= HFS_BAD_BUFFER
;
39 tmp
= hfs_extent_map(&tree
->entry
.u
.file
.data_fork
, node
, 0);
41 retval
= hfs_buffer_get(tree
->sys_mdb
, tmp
, 0);
50 * Initialize a newly allocated bnode.
52 * struct hfs_btree *tree: Pointer to a B-tree
53 * hfs_u32 node: the node number to allocate
57 * struct hfs_bnode_ref for the new node
59 * 'tree' points to a "valid" (struct hfs_btree)
60 * 'node' exists and has been allocated in the bitmap of bnodes.
63 * The node is not read from disk, nor added to the bnode cache.
64 * The 'sticky' and locking-related fields are all zero/NULL.
65 * The bnode's nd{[FB]Link, Type, NHeight} fields are uninitialized.
66 * The bnode's ndNRecs field and offsets table indicate an empty bnode.
68 * The node is deallocated.
70 static struct hfs_bnode_ref
hfs_bnode_init(struct hfs_btree
* tree
,
73 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
74 extern int bnode_count
;
76 struct hfs_bnode_ref retval
;
78 retval
.lock_type
= HFS_LOCK_NONE
;
79 if (!HFS_NEW(retval
.bn
)) {
80 hfs_warn("hfs_bnode_init: out of memory.\n");
84 /* Partially initialize the in-core structure */
85 memset(retval
.bn
, 0, sizeof(*retval
.bn
));
86 retval
.bn
->magic
= HFS_BNODE_MAGIC
;
87 retval
.bn
->tree
= tree
;
88 retval
.bn
->node
= node
;
89 hfs_bnode_lock(&retval
, HFS_LOCK_WRITE
);
91 retval
.bn
->buf
= get_new_node(tree
, node
);
92 if (!hfs_buffer_ok(retval
.bn
->buf
)) {
96 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
100 /* Partially initialize the on-disk structure */
101 memset(hfs_buffer_data(retval
.bn
->buf
), 0, HFS_SECTOR_SIZE
);
102 hfs_put_hs(sizeof(struct NodeDescriptor
), RECTBL(retval
.bn
, 1));
107 HFS_DELETE(retval
.bn
);
109 /* clear the bit in the bitmap */
110 hfs_bnode_bitop(tree
, node
, 0);
118 * Initializes a given node as a mapnode in the given tree.
120 * struct hfs_bnode *bn: the node to add the mapnode after.
121 * hfs_u32: the node to use as a mapnode.
122 * Output Variable(s):
125 * struct hfs_bnode *: the new mapnode or NULL
127 * 'tree' is a valid (struct hfs_btree).
128 * 'node' is the number of the first node in 'tree' that is not
129 * represented by a bit in the existing mapnodes.
131 * On failure 'tree' is unchanged and NULL is returned.
132 * On success the node given by 'node' has been added to the linked
133 * list of mapnodes attached to 'tree', and has been initialized as
134 * a valid mapnode with its first bit set to indicate itself as
137 static struct hfs_bnode
*init_mapnode(struct hfs_bnode
*bn
, hfs_u32 node
)
139 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
140 extern int bnode_count
;
142 struct hfs_bnode
*retval
;
144 if (!HFS_NEW(retval
)) {
145 hfs_warn("hfs_bnode_add: out of memory.\n");
149 memset(retval
, 0, sizeof(*retval
));
150 retval
->magic
= HFS_BNODE_MAGIC
;
151 retval
->tree
= bn
->tree
;
153 retval
->sticky
= HFS_STICKY
;
154 retval
->buf
= get_new_node(bn
->tree
, node
);
155 if (!hfs_buffer_ok(retval
->buf
)) {
160 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
164 /* Initialize the bnode data structure */
165 memset(hfs_buffer_data(retval
->buf
), 0, HFS_SECTOR_SIZE
);
167 retval
->ndBLink
= bn
->node
;
168 retval
->ndType
= ndMapNode
;
169 retval
->ndNHeight
= 0;
171 hfs_put_hs(sizeof(struct NodeDescriptor
), RECTBL(retval
, 1));
172 hfs_put_hs(0x1fa, RECTBL(retval
, 2));
173 *((hfs_u8
*)bnode_key(retval
, 1)) = 0x80; /* set first bit of bitmap */
175 hfs_bnode_commit(retval
);
179 hfs_bnode_commit(bn
);
184 /*================ Global functions ================*/
190 * Allocate/free the requested node of a B-tree of the hfs filesystem
191 * by setting/clearing the corresponding bit in the B-tree bitmap.
192 * The size of the B-tree will not be changed.
194 * struct hfs_btree *tree: Pointer to a B-tree
195 * hfs_u32 bitnr: The node number to free
196 * int set: 0 to clear the bit, non-zero to set it.
197 * Output Variable(s):
201 * -1: The node was already allocated/free, nothing has been done.
202 * -2: The node is out of range of the B-tree.
203 * -4: not enough map nodes to hold all the bits
205 * 'tree' points to a "valid" (struct hfs_btree)
206 * 'bitnr' is a node number within the range of the btree, which is
207 * currently free/allocated.
209 * The bit number 'bitnr' of the node bitmap is set/cleared and the
210 * number of free nodes in the btree is decremented/incremented by one.
212 int hfs_bnode_bitop(struct hfs_btree
*tree
, hfs_u32 bitnr
, int set
)
214 struct hfs_bnode
*bn
; /* the current bnode */
215 hfs_u16 start
; /* the start (in bits) of the bitmap in node */
216 hfs_u16 len
; /* the len (in bits) of the bitmap in node */
217 hfs_u32
*u32
; /* address of the u32 containing the bit */
219 if (bitnr
>= tree
->bthNNodes
) {
220 hfs_warn("hfs_bnode_bitop: node number out of range.\n");
226 start
= bnode_offset(bn
, bn
->ndNRecs
) << 3;
227 len
= (bnode_offset(bn
, bn
->ndNRecs
+ 1) << 3) - start
;
233 /* continue on to next map node if available */
234 if (!(bn
= bn
->next
)) {
235 hfs_warn("hfs_bnode_bitop: too few map nodes.\n");
241 /* Change the correct bit */
243 u32
= (hfs_u32
*)hfs_buffer_data(bn
->buf
) + (bitnr
>> 5);
245 if ((set
&& hfs_set_bit(bitnr
, u32
)) ||
246 (!set
&& !hfs_clear_bit(bitnr
, u32
))) {
247 hfs_warn("hfs_bnode_bitop: bitmap corruption.\n");
250 hfs_buffer_dirty(bn
->buf
);
252 /* adjust the free count */
253 tree
->bthFree
+= (set
? -1 : 1);
263 * Find a cleared bit in the B-tree node bitmap of the hfs filesystem,
264 * set it and return the corresponding bnode, with its contents zeroed.
265 * When there is no free bnode in the tree, an error is returned, no
266 * new nodes will be added by this function!
268 * struct hfs_btree *tree: Pointer to a B-tree
269 * Output Variable(s):
272 * struct hfs_bnode_ref for the new bnode
274 * 'tree' points to a "valid" (struct hfs_btree)
275 * There is at least one free bnode.
278 * The corresponding bit in the btree bitmap is set.
279 * The number of free nodes in the btree is decremented by one.
280 * The node is not read from disk, nor added to the bnode cache.
281 * The 'sticky' field is uninitialized.
283 struct hfs_bnode_ref
hfs_bnode_alloc(struct hfs_btree
*tree
)
285 struct hfs_bnode
*bn
; /* the current bnode */
286 hfs_u32 bitnr
= 0; /* which bit are we examining */
287 hfs_u16 first
; /* the first clear bit in this bnode */
288 hfs_u16 start
; /* the start (in bits) of the bitmap in node */
289 hfs_u16 end
; /* the end (in bits) of the bitmap in node */
290 hfs_u32
*data
; /* address of the data in this bnode */
294 start
= bnode_offset(bn
, bn
->ndNRecs
) << 3;
295 end
= bnode_offset(bn
, bn
->ndNRecs
+ 1) << 3;
296 data
= (hfs_u32
*)hfs_buffer_data(bn
->buf
);
298 /* search the current node */
299 first
= hfs_find_zero_bit(data
, end
, start
);
304 /* continue search in next map node */
308 hfs_warn("hfs_bnode_alloc: too few map nodes.\n");
311 bitnr
+= (end
- start
);
314 if ((bitnr
+= (first
- start
)) >= tree
->bthNNodes
) {
315 hfs_warn("hfs_bnode_alloc: no free nodes found, "
320 if (hfs_set_bit(first
% 32, data
+ (first
>>5))) {
321 hfs_warn("hfs_bnode_alloc: bitmap corruption.\n");
324 hfs_buffer_dirty(bn
->buf
);
326 /* decrement the free count */
330 return hfs_bnode_init(tree
, bitnr
);
333 return (struct hfs_bnode_ref
){NULL
, HFS_LOCK_NONE
};
340 * Adds nodes to a B*-tree if possible.
342 * struct hfs_btree *tree: the btree to add nodes to.
343 * Output Variable(s):
348 * 'tree' is a valid (struct hfs_btree *).
350 * If possible the number of nodes indicated by the tree's clumpsize
351 * have been added to the tree, updating all in-core and on-disk
352 * allocation information.
353 * If insufficient disk-space was available then fewer nodes may have
354 * been added than would be expected based on the clumpsize.
355 * In the case of the extents B*-tree this function will add fewer
356 * nodes than expected if adding more would result in an extent
357 * record for the extents tree being added to the extents tree.
358 * The situation could be dealt with, but doing so confuses Macs.
360 void hfs_btree_extend(struct hfs_btree
*tree
)
362 struct hfs_bnode_ref head
;
363 struct hfs_bnode
*bn
, *tmp
;
364 struct hfs_cat_entry
*entry
= &tree
->entry
;
365 struct hfs_mdb
*mdb
= entry
->mdb
;
366 hfs_u32 old_nodes
, new_nodes
, total_nodes
, new_mapnodes
, seen
;
368 old_nodes
= entry
->u
.file
.data_fork
.psize
;
370 entry
->u
.file
.data_fork
.lsize
+= 1; /* rounded up to clumpsize */
371 hfs_extent_adj(&entry
->u
.file
.data_fork
);
373 total_nodes
= entry
->u
.file
.data_fork
.psize
;
374 entry
->u
.file
.data_fork
.lsize
= total_nodes
<< HFS_SECTOR_SIZE_BITS
;
375 new_nodes
= total_nodes
- old_nodes
;
380 head
= hfs_bnode_find(tree
, 0, HFS_LOCK_WRITE
);
381 if (!(bn
= head
.bn
)) {
382 hfs_warn("hfs_btree_extend: header node not found.\n");
389 seen
+= bnode_rsize(bn
, bn
->ndNRecs
) << 3;
391 if (seen
>= total_nodes
) {
396 tmp
= init_mapnode(bn
, seen
);
398 hfs_warn("hfs_btree_extend: "
399 "can't build mapnode.\n");
400 hfs_bnode_relse(&head
);
407 hfs_bnode_relse(&head
);
409 tree
->bthNNodes
= total_nodes
;
410 tree
->bthFree
+= (new_nodes
- new_mapnodes
);
413 /* write the backup MDB, not returning until it is written */
414 hfs_mdb_commit(mdb
, 1);
422 * Remove a node from the cache and mark it free in the bitmap.
424 int hfs_bnode_free(struct hfs_bnode_ref
*bnr
)
426 hfs_u32 node
= bnr
->bn
->node
;
427 struct hfs_btree
*tree
= bnr
->bn
->tree
;
429 if (bnr
->bn
->count
!= 1) {
430 hfs_warn("hfs_bnode_free: count != 1.\n");
434 hfs_bnode_relse(bnr
);
435 hfs_bnode_bitop(tree
, node
, 0);