1 /*
2 * linux/fs/hfs/bnode.c
3 *
4 * Copyright (C) 1995-1997 Paul H. Hargrove
5 * This file may be distributed under the terms of the GNU General Public License.
6 *
7 * This file contains the code to access nodes in the B-tree structure.
8 *
9 * "XXX" in a comment is a note to myself to consider changing something.
10 *
11 * In function preconditions the term "valid" applied to a pointer to
12 * a structure means that the pointer is non-NULL and the structure it
13 * points to has all fields initialized to consistent values.
14 *
15 * The code in this file initializes some structures which contain
16 * pointers by calling memset(&foo, 0, sizeof(foo)).
17 * This produces the desired behavior only due to the non-ANSI
18 * assumption that the machine representation of NULL is all zeros.
19 */
20
21 #include "hfs_btree.h"
22
23 /*================ File-local variables ================*/
24
25 /* debugging statistics */
26 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
27 int bnode_count = 0;
28 #endif
29
30 /*================ Global functions ================*/
31
32 /*
33 * hfs_bnode_delete()
34 *
35 * Description:
36 * This function is called to remove a bnode from the cache and
37 * release its resources.
38 * Input Variable(s):
39 * struct hfs_bnode *bn: Pointer to the (struct hfs_bnode) to be
40 * removed from the cache.
41 * Output Variable(s):
42 * NONE
43 * Returns:
44 * void
45 * Preconditions:
46 * 'bn' points to a "valid" (struct hfs_bnode).
47 * Postconditions:
48 * The node 'bn' is removed from the cache, its memory freed and its
49 * buffer (if any) released.
50 */
hfs_bnode_delete(struct hfs_bnode * bn)51 void hfs_bnode_delete(struct hfs_bnode *bn)
52 {
53 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
54 --bnode_count;
55 #endif
56 /* join neighbors */
57 if (bn->next) {
58 bn->next->prev = bn->prev;
59 }
60 if (bn->prev) {
61 bn->prev->next = bn->next;
62 }
63 /* fix cache slot if necessary */
64 if (bhash(bn->tree, bn->node) == bn) {
65 bhash(bn->tree, bn->node) = bn->next;
66 }
67 /* release resources */
68 hfs_buffer_put(bn->buf); /* safe: checks for NULL argument */
69 HFS_DELETE(bn);
70 }
71
72
73 /*
74 * hfs_bnode_read()
75 *
76 * Description:
77 * This function creates a (struct hfs_bnode) and, if appropriate,
78 * inserts it in the cache.
79 * Input Variable(s):
80 * struct hfs_bnode *bnode: pointer to the new bnode.
81 * struct hfs_btree *tree: pointer to the (struct hfs_btree)
82 * containing the desired node
83 * hfs_u32 node: the number of the desired node.
84 * int sticky: the value to assign to the 'sticky' field.
85 * Output Variable(s):
86 * NONE
87 * Returns:
88 * (struct hfs_bnode *) pointing to the newly created bnode or NULL.
89 * Preconditions:
90 * 'bnode' points to a "valid" (struct hfs_bnode).
91 * 'tree' points to a "valid" (struct hfs_btree).
92 * 'node' is an existing node number in the B-tree.
93 * Postconditions:
94 * The following are true of 'bnode' upon return:
95 * The 'magic' field is set to indicate a valid (struct hfs_bnode).
96 * The 'sticky', 'tree' and 'node' fields are initialized to the
97 * values of the of the corresponding arguments.
98 * If the 'sticky' argument is zero then the fields 'prev' and
99 * 'next' are initialized by inserting the (struct hfs_bnode) in the
100 * linked list of the appropriate cache slot; otherwise they are
101 * initialized to NULL.
102 * The data is read from disk (or buffer cache) and the 'buf' field
103 * points to the buffer for that data.
104 * If no other processes tried to access this node while this
105 * process was waiting on disk I/O (if necessary) then the
106 * remaining fields are zero ('count', 'resrv', 'lock') or NULL
107 * ('wqueue', 'rqueue') corresponding to no accesses.
108 * If there were access attempts during I/O then they were blocked
109 * until the I/O was complete, and the fields 'count', 'resrv',
110 * 'lock', 'wqueue' and 'rqueue' reflect the results of unblocking
111 * those processes when the I/O was completed.
112 */
hfs_bnode_read(struct hfs_bnode * bnode,struct hfs_btree * tree,hfs_u32 node,int sticky)113 void hfs_bnode_read(struct hfs_bnode *bnode, struct hfs_btree *tree,
114 hfs_u32 node, int sticky)
115 {
116 struct NodeDescriptor *nd;
117 int block, lcv;
118 hfs_u16 curr, prev, limit;
119
120 /* Initialize the structure */
121 memset(bnode, 0, sizeof(*bnode));
122 bnode->magic = HFS_BNODE_MAGIC;
123 bnode->tree = tree;
124 bnode->node = node;
125 bnode->sticky = sticky;
126 hfs_init_waitqueue(&bnode->rqueue);
127 hfs_init_waitqueue(&bnode->wqueue);
128
129 if (sticky == HFS_NOT_STICKY) {
130 /* Insert it in the cache if appropriate */
131 if ((bnode->next = bhash(tree, node))) {
132 bnode->next->prev = bnode;
133 }
134 bhash(tree, node) = bnode;
135 }
136
137 /* Make the bnode look like it is being
138 modified so other processes will wait for
139 the I/O to complete */
140 bnode->count = bnode->resrv = bnode->lock = 1;
141
142 /* Read in the node, possibly causing a schedule()
143 call. If the I/O fails then emit a warning. Each
144 process that was waiting on the bnode (including
145 the current one) will notice the failure and
146 hfs_bnode_relse() the node. The last hfs_bnode_relse()
147 will call hfs_bnode_delete() and discard the bnode. */
148
149 block = hfs_extent_map(&tree->entry.u.file.data_fork, node, 0);
150 if (!block) {
151 hfs_warn("hfs_bnode_read: bad node number 0x%08x\n", node);
152 } else if (hfs_buffer_ok(bnode->buf =
153 hfs_buffer_get(tree->sys_mdb, block, 1))) {
154 /* read in the NodeDescriptor */
155 nd = (struct NodeDescriptor *)hfs_buffer_data(bnode->buf);
156 bnode->ndFLink = hfs_get_hl(nd->ndFLink);
157 bnode->ndBLink = hfs_get_hl(nd->ndBLink);
158 bnode->ndType = nd->ndType;
159 bnode->ndNHeight = nd->ndNHeight;
160 bnode->ndNRecs = hfs_get_hs(nd->ndNRecs);
161
162 /* verify the integrity of the node */
163 prev = sizeof(struct NodeDescriptor);
164 limit = HFS_SECTOR_SIZE - sizeof(hfs_u16)*(bnode->ndNRecs + 1);
165 for (lcv=1; lcv <= (bnode->ndNRecs + 1); ++lcv) {
166 curr = hfs_get_hs(RECTBL(bnode, lcv));
167 if ((curr < prev) || (curr > limit)) {
168 hfs_warn("hfs_bnode_read: corrupt node "
169 "number 0x%08x\n", node);
170 hfs_buffer_put(bnode->buf);
171 bnode->buf = NULL;
172 break;
173 }
174 prev = curr;
175 }
176 }
177
178 /* Undo our fakery with the lock state and
179 hfs_wake_up() anyone who we managed to trick */
180 --bnode->count;
181 bnode->resrv = bnode->lock = 0;
182 hfs_wake_up(&bnode->rqueue);
183 }
184
185 /*
186 * hfs_bnode_lock()
187 *
188 * Description:
189 * This function does the locking of a bnode.
190 * Input Variable(s):
191 * struct hfs_bnode *bn: pointer to the (struct hfs_bnode) to lock
192 * int lock_type: the type of lock desired
193 * Output Variable(s):
194 * NONE
195 * Returns:
196 * void
197 * Preconditions:
198 * 'bn' points to a "valid" (struct hfs_bnode).
199 * 'lock_type' is a valid hfs_lock_t
200 * Postconditions:
201 * The 'count' field of 'bn' is incremented by one. If 'lock_type'
202 * is HFS_LOCK_RESRV the 'resrv' field is also incremented.
203 */
hfs_bnode_lock(struct hfs_bnode_ref * bnr,int lock_type)204 void hfs_bnode_lock(struct hfs_bnode_ref *bnr, int lock_type)
205 {
206 struct hfs_bnode *bn = bnr->bn;
207
208 if ((lock_type == bnr->lock_type) || !bn) {
209 return;
210 }
211
212 if (bnr->lock_type == HFS_LOCK_WRITE) {
213 hfs_bnode_commit(bnr->bn);
214 }
215
216 switch (lock_type) {
217 default:
218 goto bail;
219 break;
220
221 case HFS_LOCK_READ:
222 /* We may not obtain read access if any process is
223 currently modifying or waiting to modify this node.
224 If we can't obtain access we wait on the rqueue
225 wait queue to be woken up by the modifying process
226 when it relinquishes its lock. */
227 switch (bnr->lock_type) {
228 default:
229 goto bail;
230 break;
231
232 case HFS_LOCK_NONE:
233 while (bn->lock || waitqueue_active(&bn->wqueue)) {
234 hfs_sleep_on(&bn->rqueue);
235 }
236 ++bn->count;
237 break;
238 }
239 break;
240
241 case HFS_LOCK_RESRV:
242 /* We may not obtain a reservation (read access with
243 an option to write later), if any process currently
244 holds a reservation on this node. That includes
245 any process which is currently modifying this node.
246 If we can't obtain access, then we wait on the
247 rqueue wait queue to e woken up by the
248 reservation-holder when it calls hfs_bnode_relse. */
249 switch (bnr->lock_type) {
250 default:
251 goto bail;
252 break;
253
254 case HFS_LOCK_NONE:
255 while (bn->resrv) {
256 hfs_sleep_on(&bn->rqueue);
257 }
258 bn->resrv = 1;
259 ++bn->count;
260 break;
261
262 case HFS_LOCK_WRITE:
263 bn->lock = 0;
264 hfs_wake_up(&bn->rqueue);
265 break;
266 }
267 break;
268
269 case HFS_LOCK_WRITE:
270 switch (bnr->lock_type) {
271 default:
272 goto bail;
273 break;
274
275 case HFS_LOCK_NONE:
276 while (bn->resrv) {
277 hfs_sleep_on(&bn->rqueue);
278 }
279 bn->resrv = 1;
280 ++bn->count;
281 case HFS_LOCK_RESRV:
282 while (bn->count > 1) {
283 hfs_sleep_on(&bn->wqueue);
284 }
285 bn->lock = 1;
286 break;
287 }
288 break;
289
290 case HFS_LOCK_NONE:
291 switch (bnr->lock_type) {
292 default:
293 goto bail;
294 break;
295
296 case HFS_LOCK_READ:
297 /* This process was reading this node. If
298 there is now exactly one other process using
299 the node then hfs_wake_up() a (potentially
300 nonexistent) waiting process. Note that I
301 refer to "a" process since the reservation
302 system ensures that only one process can
303 get itself on the wait queue. */
304 if (bn->count == 2) {
305 hfs_wake_up(&bn->wqueue);
306 }
307 break;
308
309 case HFS_LOCK_WRITE:
310 /* This process was modifying this node.
311 Unlock the node and fall-through to the
312 HFS_LOCK_RESRV case, since a 'reservation'
313 is a prerequisite for HFS_LOCK_WRITE. */
314 bn->lock = 0;
315 case HFS_LOCK_RESRV:
316 /* This process had placed a 'reservation' on
317 this node, indicating an intention to
318 possibly modify the node. We can get to
319 this spot directly (if the 'reservation'
320 not converted to a HFS_LOCK_WRITE), or by
321 falling through from the above case if the
322 reservation was converted.
323 Since HFS_LOCK_RESRV and HFS_LOCK_WRITE
324 both block processes that want access
325 (HFS_LOCK_RESRV blocks other processes that
326 want reservations but allow HFS_LOCK_READ
327 accesses, while HFS_LOCK_WRITE must have
328 exclusive access and thus blocks both
329 types) we hfs_wake_up() any processes that
330 might be waiting for access. If multiple
331 processes are waiting for a reservation
332 then the magic of process scheduling will
333 settle the dispute. */
334 bn->resrv = 0;
335 hfs_wake_up(&bn->rqueue);
336 break;
337 }
338 --bn->count;
339 break;
340 }
341 bnr->lock_type = lock_type;
342 return;
343
344 bail:
345 hfs_warn("hfs_bnode_lock: invalid lock change: %d->%d.\n",
346 bnr->lock_type, lock_type);
347 return;
348 }
349
350 /*
351 * hfs_bnode_relse()
352 *
353 * Description:
354 * This function is called when a process is done using a bnode. If
355 * the proper conditions are met then we call hfs_bnode_delete() to remove
356 * it from the cache. If it is not deleted then we update its state
357 * to reflect one less process using it.
358 * Input Variable(s):
359 * struct hfs_bnode *bn: pointer to the (struct hfs_bnode) to release.
360 * int lock_type: The type of lock held by the process releasing this node.
361 * Output Variable(s):
362 * NONE
363 * Returns:
364 * void
365 * Preconditions:
366 * 'bn' is NULL or points to a "valid" (struct hfs_bnode).
367 * Postconditions:
368 * If 'bn' meets the appropriate conditions (see below) then it is
369 * kept in the cache and all fields are set to consistent values
370 * which reflect one less process using the node than upon entry.
371 * If 'bn' does not meet the conditions then it is deleted (see
372 * hfs_bnode_delete() for postconditions).
373 * In either case, if 'lock_type' is HFS_LOCK_WRITE
374 * then the corresponding buffer is dirtied.
375 */
hfs_bnode_relse(struct hfs_bnode_ref * bnr)376 void hfs_bnode_relse(struct hfs_bnode_ref *bnr)
377 {
378 struct hfs_bnode *bn;
379
380 if (!bnr || !(bn = bnr->bn)) {
381 return;
382 }
383
384 /* We update the lock state of the node if it is still in use
385 or if it is "sticky" (such as the B-tree head and root).
386 Otherwise we just delete it. */
387 if ((bn->count > 1) || (waitqueue_active(&bn->rqueue)) || (bn->sticky != HFS_NOT_STICKY)) {
388 hfs_bnode_lock(bnr, HFS_LOCK_NONE);
389 } else {
390 /* dirty buffer if we (might) have modified it */
391 if (bnr->lock_type == HFS_LOCK_WRITE) {
392 hfs_bnode_commit(bn);
393 }
394 hfs_bnode_delete(bn);
395 bnr->lock_type = HFS_LOCK_NONE;
396 }
397 bnr->bn = NULL;
398 }
399
400 /*
401 * hfs_bnode_find()
402 *
403 * Description:
404 * This function is called to obtain a bnode. The cache is
405 * searched for the node. If it not found there it is added to
406 * the cache by hfs_bnode_read(). There are two special cases node=0
407 * (the header node) and node='tree'->bthRoot (the root node), in
408 * which the nodes are obtained from fields of 'tree' without
409 * consulting or modifying the cache.
410 * Input Variable(s):
411 * struct hfs_tree *tree: pointer to the (struct hfs_btree) from
412 * which to get a node.
413 * int node: the node number to get from 'tree'.
414 * int lock_type: The kind of access (HFS_LOCK_READ, or
415 * HFS_LOCK_RESRV) to obtain to the node
416 * Output Variable(s):
417 * NONE
418 * Returns:
419 * (struct hfs_bnode_ref) Reference to the requested node.
420 * Preconditions:
421 * 'tree' points to a "valid" (struct hfs_btree).
422 * Postconditions:
423 * If 'node' refers to a valid node in 'tree' and 'lock_type' has
424 * one of the values listed above and no I/O errors occur then the
425 * value returned refers to a valid (struct hfs_bnode) corresponding
426 * to the requested node with the requested access type. The node
427 * is also added to the cache if not previously present and not the
428 * root or header.
429 * If the conditions given above are not met, the bnode in the
430 * returned reference is NULL.
431 */
hfs_bnode_find(struct hfs_btree * tree,hfs_u32 node,int lock_type)432 struct hfs_bnode_ref hfs_bnode_find(struct hfs_btree *tree,
433 hfs_u32 node, int lock_type)
434 {
435 struct hfs_bnode *bn;
436 struct hfs_bnode *empty = NULL;
437 struct hfs_bnode_ref bnr;
438
439 bnr.lock_type = HFS_LOCK_NONE;
440 bnr.bn = NULL;
441
442 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
443 hfs_warn("hfs_bnode_find: %c %d:%d\n",
444 lock_type==HFS_LOCK_READ?'R':
445 (lock_type==HFS_LOCK_RESRV?'V':'W'),
446 (int)ntohl(tree->entry.cnid), node);
447 #endif
448
449 /* check special cases */
450 if (!node) {
451 bn = &tree->head;
452 goto return_it;
453 } else if (node == tree->bthRoot) {
454 bn = tree->root;
455 goto return_it;
456 }
457
458 restart:
459 /* look for the node in the cache. */
460 bn = bhash(tree, node);
461 while (bn && (bn->magic == HFS_BNODE_MAGIC)) {
462 if (bn->node == node) {
463 goto found_it;
464 }
465 bn = bn->next;
466 }
467
468 if (!empty) {
469 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
470 ++bnode_count;
471 #endif
472 if (HFS_NEW(empty)) {
473 goto restart;
474 }
475 return bnr;
476 }
477 bn = empty;
478 hfs_bnode_read(bn, tree, node, HFS_NOT_STICKY);
479 goto return_it;
480
481 found_it:
482 /* check validity */
483 if (bn->magic != HFS_BNODE_MAGIC) {
484 /* If we find a corrupt bnode then we return
485 NULL. However, we don't try to remove it
486 from the cache or release its resources
487 since we have no idea what kind of trouble
488 we could get into that way. */
489 hfs_warn("hfs_bnode_find: bnode cache is corrupt.\n");
490 return bnr;
491 }
492 if (empty) {
493 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
494 --bnode_count;
495 #endif
496 HFS_DELETE(empty);
497 }
498
499 return_it:
500 /* Wait our turn */
501 bnr.bn = bn;
502 hfs_bnode_lock(&bnr, lock_type);
503
504 /* Check for failure to read the node from disk */
505 if (!hfs_buffer_ok(bn->buf)) {
506 hfs_bnode_relse(&bnr);
507 }
508
509 #if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
510 if (!bnr.bn) {
511 hfs_warn("hfs_bnode_find: failed\n");
512 } else {
513 hfs_warn("hfs_bnode_find: use %d(%d) lvl %d [%d]\n", bn->count,
514 bn->buf->b_count, bn->ndNHeight, bnode_count);
515 hfs_warn("hfs_bnode_find: blnk %u flnk %u recs %u\n",
516 bn->ndBLink, bn->ndFLink, bn->ndNRecs);
517 }
518 #endif
519
520 return bnr;
521 }
522
523 /*
524 * hfs_bnode_commit()
525 *
526 * Called to write a possibly dirty bnode back to disk.
527 */
hfs_bnode_commit(struct hfs_bnode * bn)528 void hfs_bnode_commit(struct hfs_bnode *bn)
529 {
530 if (hfs_buffer_ok(bn->buf)) {
531 struct NodeDescriptor *nd;
532 nd = (struct NodeDescriptor *)hfs_buffer_data(bn->buf);
533
534 hfs_put_hl(bn->ndFLink, nd->ndFLink);
535 hfs_put_hl(bn->ndBLink, nd->ndBLink);
536 nd->ndType = bn->ndType;
537 nd->ndNHeight = bn->ndNHeight;
538 hfs_put_hs(bn->ndNRecs, nd->ndNRecs);
539 hfs_buffer_dirty(bn->buf);
540
541 /* increment write count */
542 hfs_mdb_dirty(bn->tree->sys_mdb);
543 }
544 }
545