1 /*
2 * linux/fs/hfs/balloc.c
3 *
4 * Copyright (C) 1995-1997 Paul H. Hargrove
5 * This file may be distributed under the terms of the GNU Public License.
6 *
7 * hfs_bnode_alloc() and hfs_bnode_bitop() are based on GPLed code
8 * Copyright (C) 1995 Michael Dreher
9 *
10 * This file contains the code to create and destroy nodes
11 * in the B-tree structure.
12 *
13 * "XXX" in a comment is a note to myself to consider changing something.
14 *
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.
18 *
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.
23 */
24
25 #include "hfs_btree.h"
26
27 /*================ File-local functions ================*/
28
29 /*
30 * get_new_node()
31 *
32 * Get a buffer for a new node with out reading it from disk.
33 */
34 static hfs_buffer get_new_node(struct hfs_btree *tree, hfs_u32 node)
35 {
36 int tmp;
37 hfs_buffer retval = HFS_BAD_BUFFER;
38
39 tmp = hfs_extent_map(&tree->entry.u.file.data_fork, node, 0);
40 if (tmp) {
41 retval = hfs_buffer_get(tree->sys_mdb, tmp, 0);
42 }
43 return retval;
44 }
45
46 /*
47 * hfs_bnode_init()
48 *
49 * Description:
50 * Initialize a newly allocated bnode.
51 * Input Variable(s):
52 * struct hfs_btree *tree: Pointer to a B-tree
53 * hfs_u32 node: the node number to allocate
54 * Output Variable(s):
55 * NONE
56 * Returns:
57 * struct hfs_bnode_ref for the new node
58 * Preconditions:
59 * 'tree' points to a "valid" (struct hfs_btree)
60 * 'node' exists and has been allocated in the bitmap of bnodes.
61 * Postconditions:
62 * On success:
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.
67 * On failure:
68 * The node is deallocated.
69 */
70 static struct hfs_bnode_ref hfs_bnode_init(struct hfs_btree * tree,
71 hfs_u32 node)
72 {
73 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
74 extern int bnode_count;
75 #endif
76 struct hfs_bnode_ref retval;
77
78 retval.lock_type = HFS_LOCK_NONE;
79 if (!HFS_NEW(retval.bn)) {
80 hfs_warn("hfs_bnode_init: out of memory.\n");
81 goto bail2;
82 }
83
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_init_waitqueue(&retval.bn->wqueue);
90 hfs_init_waitqueue(&retval.bn->rqueue);
91 hfs_bnode_lock(&retval, HFS_LOCK_WRITE);
92
93 retval.bn->buf = get_new_node(tree, node);
94 if (!hfs_buffer_ok(retval.bn->buf)) {
95 goto bail1;
96 }
97
98 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
99 ++bnode_count;
100 #endif
101
102 /* Partially initialize the on-disk structure */
103 memset(hfs_buffer_data(retval.bn->buf), 0, HFS_SECTOR_SIZE);
104 hfs_put_hs(sizeof(struct NodeDescriptor), RECTBL(retval.bn, 1));
105
106 return retval;
107
108 bail1:
109 HFS_DELETE(retval.bn);
110 bail2:
111 /* clear the bit in the bitmap */
112 hfs_bnode_bitop(tree, node, 0);
113 return retval;
114 }
115
116 /*
117 * init_mapnode()
118 *
119 * Description:
120 * Initializes a given node as a mapnode in the given tree.
121 * Input Variable(s):
122 * struct hfs_bnode *bn: the node to add the mapnode after.
123 * hfs_u32: the node to use as a mapnode.
124 * Output Variable(s):
125 * NONE
126 * Returns:
127 * struct hfs_bnode *: the new mapnode or NULL
128 * Preconditions:
129 * 'tree' is a valid (struct hfs_btree).
130 * 'node' is the number of the first node in 'tree' that is not
131 * represented by a bit in the existing mapnodes.
132 * Postconditions:
133 * On failure 'tree' is unchanged and NULL is returned.
134 * On success the node given by 'node' has been added to the linked
135 * list of mapnodes attached to 'tree', and has been initialized as
136 * a valid mapnode with its first bit set to indicate itself as
137 * allocated.
138 */
139 static struct hfs_bnode *init_mapnode(struct hfs_bnode *bn, hfs_u32 node)
140 {
141 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
142 extern int bnode_count;
143 #endif
144 struct hfs_bnode *retval;
145
146 if (!HFS_NEW(retval)) {
147 hfs_warn("hfs_bnode_add: out of memory.\n");
148 return NULL;
149 }
150
151 memset(retval, 0, sizeof(*retval));
152 retval->magic = HFS_BNODE_MAGIC;
153 retval->tree = bn->tree;
154 retval->node = node;
155 retval->sticky = HFS_STICKY;
156 retval->buf = get_new_node(bn->tree, node);
157 if (!hfs_buffer_ok(retval->buf)) {
158 HFS_DELETE(retval);
159 return NULL;
160 }
161
162 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
163 ++bnode_count;
164 #endif
165
166 /* Initialize the bnode data structure */
167 memset(hfs_buffer_data(retval->buf), 0, HFS_SECTOR_SIZE);
168 retval->ndFLink = 0;
169 retval->ndBLink = bn->node;
170 retval->ndType = ndMapNode;
171 retval->ndNHeight = 0;
172 retval->ndNRecs = 1;
173 hfs_put_hs(sizeof(struct NodeDescriptor), RECTBL(retval, 1));
174 hfs_put_hs(0x1fa, RECTBL(retval, 2));
175 *((hfs_u8 *)bnode_key(retval, 1)) = 0x80; /* set first bit of bitmap */
176 retval->prev = bn;
177 hfs_bnode_commit(retval);
178
179 bn->ndFLink = node;
180 bn->next = retval;
181 hfs_bnode_commit(bn);
182
183 return retval;
184 }
185
186 /*================ Global functions ================*/
187
188 /*
189 * hfs_bnode_bitop()
190 *
191 * Description:
192 * Allocate/free the requested node of a B-tree of the hfs filesystem
193 * by setting/clearing the corresponding bit in the B-tree bitmap.
194 * The size of the B-tree will not be changed.
195 * Input Variable(s):
196 * struct hfs_btree *tree: Pointer to a B-tree
197 * hfs_u32 bitnr: The node number to free
198 * int set: 0 to clear the bit, non-zero to set it.
199 * Output Variable(s):
200 * None
201 * Returns:
202 * 0: no error
203 * -1: The node was already allocated/free, nothing has been done.
204 * -2: The node is out of range of the B-tree.
205 * -4: not enough map nodes to hold all the bits
206 * Preconditions:
207 * 'tree' points to a "valid" (struct hfs_btree)
208 * 'bitnr' is a node number within the range of the btree, which is
209 * currently free/allocated.
210 * Postconditions:
211 * The bit number 'bitnr' of the node bitmap is set/cleared and the
212 * number of free nodes in the btree is decremented/incremented by one.
213 */
214 int hfs_bnode_bitop(struct hfs_btree *tree, hfs_u32 bitnr, int set)
215 {
216 struct hfs_bnode *bn; /* the current bnode */
217 hfs_u16 start; /* the start (in bits) of the bitmap in node */
218 hfs_u16 len; /* the len (in bits) of the bitmap in node */
219 hfs_u32 *u32; /* address of the u32 containing the bit */
220
221 if (bitnr >= tree->bthNNodes) {
222 hfs_warn("hfs_bnode_bitop: node number out of range.\n");
223 return -2;
224 }
225
226 bn = &tree->head;
227 for (;;) {
228 start = bnode_offset(bn, bn->ndNRecs) << 3;
229 len = (bnode_offset(bn, bn->ndNRecs + 1) << 3) - start;
230
231 if (bitnr < len) {
232 break;
233 }
234
235 /* continue on to next map node if available */
236 if (!(bn = bn->next)) {
237 hfs_warn("hfs_bnode_bitop: too few map nodes.\n");
238 return -4;
239 }
240 bitnr -= len;
241 }
242
243 /* Change the correct bit */
244 bitnr += start;
245 u32 = (hfs_u32 *)hfs_buffer_data(bn->buf) + (bitnr >> 5);
246 bitnr %= 32;
247 if ((set && hfs_set_bit(bitnr, u32)) ||
248 (!set && !hfs_clear_bit(bitnr, u32))) {
249 hfs_warn("hfs_bnode_bitop: bitmap corruption.\n");
250 return -1;
251 }
252 hfs_buffer_dirty(bn->buf);
253
254 /* adjust the free count */
255 tree->bthFree += (set ? -1 : 1);
256 tree->dirt = 1;
257
258 return 0;
259 }
260
261 /*
262 * hfs_bnode_alloc()
263 *
264 * Description:
265 * Find a cleared bit in the B-tree node bitmap of the hfs filesystem,
266 * set it and return the corresponding bnode, with its contents zeroed.
267 * When there is no free bnode in the tree, an error is returned, no
268 * new nodes will be added by this function!
269 * Input Variable(s):
270 * struct hfs_btree *tree: Pointer to a B-tree
271 * Output Variable(s):
272 * NONE
273 * Returns:
274 * struct hfs_bnode_ref for the new bnode
275 * Preconditions:
276 * 'tree' points to a "valid" (struct hfs_btree)
277 * There is at least one free bnode.
278 * Postconditions:
279 * On success:
280 * The corresponding bit in the btree bitmap is set.
281 * The number of free nodes in the btree is decremented by one.
282 * The node is not read from disk, nor added to the bnode cache.
283 * The 'sticky' field is uninitialized.
284 */
285 struct hfs_bnode_ref hfs_bnode_alloc(struct hfs_btree *tree)
286 {
287 struct hfs_bnode *bn; /* the current bnode */
288 hfs_u32 bitnr = 0; /* which bit are we examining */
289 hfs_u16 first; /* the first clear bit in this bnode */
290 hfs_u16 start; /* the start (in bits) of the bitmap in node */
291 hfs_u16 end; /* the end (in bits) of the bitmap in node */
292 hfs_u32 *data; /* address of the data in this bnode */
293
294 bn = &tree->head;
295 for (;;) {
296 start = bnode_offset(bn, bn->ndNRecs) << 3;
297 end = bnode_offset(bn, bn->ndNRecs + 1) << 3;
298 data = (hfs_u32 *)hfs_buffer_data(bn->buf);
299
300 /* search the current node */
301 first = hfs_find_zero_bit(data, end, start);
302 if (first < end) {
303 break;
304 }
305
306 /* continue search in next map node */
307 bn = bn->next;
308
309 if (!bn) {
310 hfs_warn("hfs_bnode_alloc: too few map nodes.\n");
311 goto bail;
312 }
313 bitnr += (end - start);
314 }
315
316 if ((bitnr += (first - start)) >= tree->bthNNodes) {
317 hfs_warn("hfs_bnode_alloc: no free nodes found, "
318 "count wrong?\n");
319 goto bail;
320 }
321
322 if (hfs_set_bit(first % 32, data + (first>>5))) {
323 hfs_warn("hfs_bnode_alloc: bitmap corruption.\n");
324 goto bail;
325 }
326 hfs_buffer_dirty(bn->buf);
327
328 /* decrement the free count */
329 --tree->bthFree;
330 tree->dirt = 1;
331
332 return hfs_bnode_init(tree, bitnr);
333
334 bail:
335 return (struct hfs_bnode_ref){NULL, HFS_LOCK_NONE};
336 }
337
338 /*
339 * hfs_btree_extend()
340 *
341 * Description:
342 * Adds nodes to a B*-tree if possible.
343 * Input Variable(s):
344 * struct hfs_btree *tree: the btree to add nodes to.
345 * Output Variable(s):
346 * NONE
347 * Returns:
348 * void
349 * Preconditions:
350 * 'tree' is a valid (struct hfs_btree *).
351 * Postconditions:
352 * If possible the number of nodes indicated by the tree's clumpsize
353 * have been added to the tree, updating all in-core and on-disk
354 * allocation information.
355 * If insufficient disk-space was available then fewer nodes may have
356 * been added than would be expected based on the clumpsize.
357 * In the case of the extents B*-tree this function will add fewer
358 * nodes than expected if adding more would result in an extent
359 * record for the extents tree being added to the extents tree.
360 * The situation could be dealt with, but doing so confuses Macs.
361 */
362 void hfs_btree_extend(struct hfs_btree *tree)
363 {
364 struct hfs_bnode_ref head;
365 struct hfs_bnode *bn, *tmp;
366 struct hfs_cat_entry *entry = &tree->entry;
367 struct hfs_mdb *mdb = entry->mdb;
368 hfs_u32 old_nodes, new_nodes, total_nodes, new_mapnodes, seen;
369
370 old_nodes = entry->u.file.data_fork.psize;
371
372 entry->u.file.data_fork.lsize += 1; /* rounded up to clumpsize */
373 hfs_extent_adj(&entry->u.file.data_fork);
374
375 total_nodes = entry->u.file.data_fork.psize;
376 entry->u.file.data_fork.lsize = total_nodes << HFS_SECTOR_SIZE_BITS;
377 new_nodes = total_nodes - old_nodes;
378 if (!new_nodes) {
379 return;
380 }
381
382 head = hfs_bnode_find(tree, 0, HFS_LOCK_WRITE);
383 if (!(bn = head.bn)) {
384 hfs_warn("hfs_btree_extend: header node not found.\n");
385 return;
386 }
387
388 seen = 0;
389 new_mapnodes = 0;
390 for (;;) {
391 seen += bnode_rsize(bn, bn->ndNRecs) << 3;
392
393 if (seen >= total_nodes) {
394 break;
395 }
396
397 if (!bn->next) {
398 tmp = init_mapnode(bn, seen);
399 if (!tmp) {
400 hfs_warn("hfs_btree_extend: "
401 "can't build mapnode.\n");
402 hfs_bnode_relse(&head);
403 return;
404 }
405 ++new_mapnodes;
406 }
407 bn = bn->next;
408 }
409 hfs_bnode_relse(&head);
410
411 tree->bthNNodes = total_nodes;
412 tree->bthFree += (new_nodes - new_mapnodes);
413 tree->dirt = 1;
414
415 /* write the backup MDB, not returning until it is written */
416 hfs_mdb_commit(mdb, 1);
417
418 return;
419 }
420
421 /*
422 * hfs_bnode_free()
423 *
424 * Remove a node from the cache and mark it free in the bitmap.
425 */
426 int hfs_bnode_free(struct hfs_bnode_ref *bnr)
427 {
428 hfs_u32 node = bnr->bn->node;
429 struct hfs_btree *tree = bnr->bn->tree;
430
431 if (bnr->bn->count != 1) {
432 hfs_warn("hfs_bnode_free: count != 1.\n");
433 return -EIO;
434 }
435
436 hfs_bnode_relse(bnr);
437 hfs_bnode_bitop(tree, node, 0);
438 return 0;
439 }
440
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.