summaryrefslogtreecommitdiffstats
path: root/fs/hfs/bnode.c
diff options
context:
space:
mode:
Diffstat (limited to 'fs/hfs/bnode.c')
-rw-r--r--fs/hfs/bnode.c540
1 files changed, 540 insertions, 0 deletions
diff --git a/fs/hfs/bnode.c b/fs/hfs/bnode.c
new file mode 100644
index 000000000..762278667
--- /dev/null
+++ b/fs/hfs/bnode.c
@@ -0,0 +1,540 @@
+/*
+ * linux/fs/hfs/bnode.c
+ *
+ * Copyright (C) 1995-1997 Paul H. Hargrove
+ * This file may be distributed under the terms of the GNU Public License.
+ *
+ * This file contains the code to access nodes in the B-tree structure.
+ *
+ * "XXX" in a comment is a note to myself to consider changing something.
+ *
+ * In function preconditions the term "valid" applied to a pointer to
+ * a structure means that the pointer is non-NULL and the structure it
+ * points to has all fields initialized to consistent values.
+ *
+ * The code in this file initializes some structures which contain
+ * pointers by calling memset(&foo, 0, sizeof(foo)).
+ * This produces the desired behavior only due to the non-ANSI
+ * assumption that the machine representation of NULL is all zeros.
+ */
+
+#include "hfs_btree.h"
+
+/*================ File-local variables ================*/
+
+/* debugging statistics */
+#if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
+int bnode_count = 0;
+#endif
+
+/*================ Global functions ================*/
+
+/*
+ * hfs_bnode_delete()
+ *
+ * Description:
+ * This function is called to remove a bnode from the cache and
+ * release its resources.
+ * Input Variable(s):
+ * struct hfs_bnode *bn: Pointer to the (struct hfs_bnode) to be
+ * removed from the cache.
+ * Output Variable(s):
+ * NONE
+ * Returns:
+ * void
+ * Preconditions:
+ * 'bn' points to a "valid" (struct hfs_bnode).
+ * Postconditions:
+ * The node 'bn' is removed from the cache, its memory freed and its
+ * buffer (if any) released.
+ */
+void hfs_bnode_delete(struct hfs_bnode *bn)
+{
+#if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
+ --bnode_count;
+#endif
+ /* join neighbors */
+ if (bn->next) {
+ bn->next->prev = bn->prev;
+ }
+ if (bn->prev) {
+ bn->prev->next = bn->next;
+ }
+ /* fix cache slot if necessary */
+ if (bhash(bn->tree, bn->node) == bn) {
+ bhash(bn->tree, bn->node) = bn->next;
+ }
+ /* release resources */
+ hfs_buffer_put(bn->buf); /* safe: checks for NULL argument */
+ HFS_DELETE(bn);
+}
+
+
+/*
+ * hfs_bnode_read()
+ *
+ * Description:
+ * This function creates a (struct hfs_bnode) and, if appropriate,
+ * inserts it in the cache.
+ * Input Variable(s):
+ * struct hfs_bnode *bnode: pointer to the new bnode.
+ * struct hfs_btree *tree: pointer to the (struct hfs_btree)
+ * containing the desired node
+ * hfs_u32 node: the number of the desired node.
+ * int sticky: the value to assign to the 'sticky' field.
+ * Output Variable(s):
+ * NONE
+ * Returns:
+ * (struct hfs_bnode *) pointing to the newly created bnode or NULL.
+ * Preconditions:
+ * 'bnode' points to a "valid" (struct hfs_bnode).
+ * 'tree' points to a "valid" (struct hfs_btree).
+ * 'node' is an existing node number in the B-tree.
+ * Postconditions:
+ * The following are true of 'bnode' upon return:
+ * The 'magic' field is set to indicate a valid (struct hfs_bnode).
+ * The 'sticky', 'tree' and 'node' fields are initialized to the
+ * values of the of the corresponding arguments.
+ * If the 'sticky' argument is zero then the fields 'prev' and
+ * 'next' are initialized by inserting the (struct hfs_bnode) in the
+ * linked list of the appropriate cache slot; otherwise they are
+ * initialized to NULL.
+ * The data is read from disk (or buffer cache) and the 'buf' field
+ * points to the buffer for that data.
+ * If no other processes tried to access this node while this
+ * process was waiting on disk I/O (if necessary) then the
+ * remaining fields are zero ('count', 'resrv', 'lock') or NULL
+ * ('wqueue', 'rqueue') corresponding to no accesses.
+ * If there were access attempts during I/O then they were blocked
+ * until the I/O was complete, and the fields 'count', 'resrv',
+ * 'lock', 'wqueue' and 'rqueue' reflect the results of unblocking
+ * those processes when the I/O was completed.
+ */
+void hfs_bnode_read(struct hfs_bnode *bnode, struct hfs_btree *tree,
+ hfs_u32 node, int sticky)
+{
+ struct NodeDescriptor *nd;
+ int block, lcv;
+ hfs_u16 curr, prev, limit;
+
+ /* Initialize the structure */
+ memset(bnode, 0, sizeof(*bnode));
+ bnode->magic = HFS_BNODE_MAGIC;
+ bnode->tree = tree;
+ bnode->node = node;
+ bnode->sticky = sticky;
+
+ if (sticky == HFS_NOT_STICKY) {
+ /* Insert it in the cache if appropriate */
+ if ((bnode->next = bhash(tree, node))) {
+ bnode->next->prev = bnode;
+ }
+ bhash(tree, node) = bnode;
+ }
+
+ /* Make the bnode look like it is being
+ modified so other processes will wait for
+ the I/O to complete */
+ bnode->count = bnode->resrv = bnode->lock = 1;
+
+ /* Read in the node, possibly causing a schedule()
+ call. If the I/O fails then emit a warning. Each
+ process that was waiting on the bnode (including
+ the current one) will notice the failure and
+ hfs_bnode_relse() the node. The last hfs_bnode_relse()
+ will call hfs_bnode_delete() and discard the bnode. */
+
+ block = hfs_extent_map(&tree->entry.u.file.data_fork, node, 0);
+ if (!block) {
+ hfs_warn("hfs_bnode_read: bad node number 0x%08x\n", node);
+ } else if (hfs_buffer_ok(bnode->buf =
+ hfs_buffer_get(tree->sys_mdb, block, 1))) {
+ /* read in the NodeDescriptor */
+ nd = (struct NodeDescriptor *)hfs_buffer_data(bnode->buf);
+ bnode->ndFLink = hfs_get_hl(nd->ndFLink);
+ bnode->ndBLink = hfs_get_hl(nd->ndBLink);
+ bnode->ndType = nd->ndType;
+ bnode->ndNHeight = nd->ndNHeight;
+ bnode->ndNRecs = hfs_get_hs(nd->ndNRecs);
+
+ /* verify the integrity of the node */
+ prev = sizeof(struct NodeDescriptor);
+ limit = HFS_SECTOR_SIZE - sizeof(hfs_u16)*(bnode->ndNRecs + 1);
+ for (lcv=1; lcv <= (bnode->ndNRecs + 1); ++lcv) {
+ curr = hfs_get_hs(RECTBL(bnode, lcv));
+ if ((curr < prev) || (curr > limit)) {
+ hfs_warn("hfs_bnode_read: corrupt node "
+ "number 0x%08x\n", node);
+ hfs_buffer_put(bnode->buf);
+ bnode->buf = NULL;
+ break;
+ }
+ prev = curr;
+ }
+ }
+
+ /* Undo our fakery with the lock state and
+ hfs_wake_up() anyone who we managed to trick */
+ --bnode->count;
+ bnode->resrv = bnode->lock = 0;
+ hfs_wake_up(&bnode->rqueue);
+}
+
+/*
+ * hfs_bnode_lock()
+ *
+ * Description:
+ * This function does the locking of a bnode.
+ * Input Variable(s):
+ * struct hfs_bnode *bn: pointer to the (struct hfs_bnode) to lock
+ * int lock_type: the type of lock desired
+ * Output Variable(s):
+ * NONE
+ * Returns:
+ * void
+ * Preconditions:
+ * 'bn' points to a "valid" (struct hfs_bnode).
+ * 'lock_type' is a valid hfs_lock_t
+ * Postconditions:
+ * The 'count' field of 'bn' is incremented by one. If 'lock_type'
+ * is HFS_LOCK_RESRV the 'resrv' field is also incremented.
+ */
+void hfs_bnode_lock(struct hfs_bnode_ref *bnr, int lock_type)
+{
+ struct hfs_bnode *bn = bnr->bn;
+
+ if ((lock_type == bnr->lock_type) || !bn) {
+ return;
+ }
+
+ if (bnr->lock_type == HFS_LOCK_WRITE) {
+ hfs_bnode_commit(bnr->bn);
+ }
+
+ switch (lock_type) {
+ default:
+ goto bail;
+ break;
+
+ case HFS_LOCK_READ:
+ /* We may not obtain read access if any process is
+ currently modifying or waiting to modify this node.
+ If we can't obtain access we wait on the rqueue
+ wait queue to be woken up by the modifying process
+ when it relinquishes its lock. */
+ switch (bnr->lock_type) {
+ default:
+ goto bail;
+ break;
+
+ case HFS_LOCK_NONE:
+ while (bn->lock || bn->wqueue) {
+ hfs_sleep_on(&bn->rqueue);
+ }
+ ++bn->count;
+ break;
+ }
+ break;
+
+ case HFS_LOCK_RESRV:
+ /* We may not obtain a reservation (read access with
+ an option to write later), if any process currently
+ holds a reservation on this node. That includes
+ any process which is currently modifying this node.
+ If we can't obtain access, then we wait on the
+ rqueue wait queue to e woken up by the
+ reservation-holder when it calls hfs_bnode_relse. */
+ switch (bnr->lock_type) {
+ default:
+ goto bail;
+ break;
+
+ case HFS_LOCK_NONE:
+ while (bn->resrv) {
+ hfs_sleep_on(&bn->rqueue);
+ }
+ bn->resrv = 1;
+ ++bn->count;
+ break;
+
+ case HFS_LOCK_WRITE:
+ bn->lock = 0;
+ hfs_wake_up(&bn->rqueue);
+ break;
+ }
+ break;
+
+ case HFS_LOCK_WRITE:
+ switch (bnr->lock_type) {
+ default:
+ goto bail;
+ break;
+
+ case HFS_LOCK_NONE:
+ while (bn->resrv) {
+ hfs_sleep_on(&bn->rqueue);
+ }
+ bn->resrv = 1;
+ ++bn->count;
+ case HFS_LOCK_RESRV:
+ while (bn->count > 1) {
+ hfs_sleep_on(&bn->wqueue);
+ }
+ bn->lock = 1;
+ break;
+ }
+ break;
+
+ case HFS_LOCK_NONE:
+ switch (bnr->lock_type) {
+ default:
+ goto bail;
+ break;
+
+ case HFS_LOCK_READ:
+ /* This process was reading this node. If
+ there is now exactly one other process using
+ the node then hfs_wake_up() a (potentially
+ nonexistent) waiting process. Note that I
+ refer to "a" process since the reservation
+ system ensures that only one process can
+ get itself on the wait queue. */
+ if (bn->count == 2) {
+ hfs_wake_up(&bn->wqueue);
+ }
+ break;
+
+ case HFS_LOCK_WRITE:
+ /* This process was modifying this node.
+ Unlock the node and fall-through to the
+ HFS_LOCK_RESRV case, since a 'reservation'
+ is a prerequisite for HFS_LOCK_WRITE. */
+ bn->lock = 0;
+ case HFS_LOCK_RESRV:
+ /* This process had placed a 'reservation' on
+ this node, indicating an intention to
+ possibly modify the node. We can get to
+ this spot directly (if the 'reservation'
+ not converted to a HFS_LOCK_WRITE), or by
+ falling through from the above case if the
+ reservation was converted.
+ Since HFS_LOCK_RESRV and HFS_LOCK_WRITE
+ both block processes that want access
+ (HFS_LOCK_RESRV blocks other processes that
+ want reservations but allow HFS_LOCK_READ
+ accesses, while HFS_LOCK_WRITE must have
+ exclusive access and thus blocks both
+ types) we hfs_wake_up() any processes that
+ might be waiting for access. If multiple
+ processes are waiting for a reservation
+ then the magic of process scheduling will
+ settle the dispute. */
+ bn->resrv = 0;
+ hfs_wake_up(&bn->rqueue);
+ break;
+ }
+ --bn->count;
+ break;
+ }
+ bnr->lock_type = lock_type;
+ return;
+
+bail:
+ hfs_warn("hfs_bnode_lock: invalid lock change: %d->%d.\n",
+ bnr->lock_type, lock_type);
+ return;
+}
+
+/*
+ * hfs_bnode_relse()
+ *
+ * Description:
+ * This function is called when a process is done using a bnode. If
+ * the proper conditions are met then we call hfs_bnode_delete() to remove
+ * it from the cache. If it is not deleted then we update its state
+ * to reflect one less process using it.
+ * Input Variable(s):
+ * struct hfs_bnode *bn: pointer to the (struct hfs_bnode) to release.
+ * int lock_type: The type of lock held by the process releasing this node.
+ * Output Variable(s):
+ * NONE
+ * Returns:
+ * void
+ * Preconditions:
+ * 'bn' is NULL or points to a "valid" (struct hfs_bnode).
+ * Postconditions:
+ * If 'bn' meets the appropriate conditions (see below) then it is
+ * kept in the cache and all fields are set to consistent values
+ * which reflect one less process using the node than upon entry.
+ * If 'bn' does not meet the conditions then it is deleted (see
+ * hfs_bnode_delete() for postconditions).
+ * In either case, if 'lock_type' is HFS_LOCK_WRITE
+ * then the corresponding buffer is dirtied.
+ */
+void hfs_bnode_relse(struct hfs_bnode_ref *bnr)
+{
+ struct hfs_bnode *bn;
+
+ if (!bnr || !(bn = bnr->bn)) {
+ return;
+ }
+
+ /* We update the lock state of the node if it is still in use
+ or if it is "sticky" (such as the B-tree head and root).
+ Otherwise we just delete it. */
+ if ((bn->count > 1) || (bn->rqueue) || (bn->sticky != HFS_NOT_STICKY)) {
+ hfs_bnode_lock(bnr, HFS_LOCK_NONE);
+ } else {
+ /* dirty buffer if we (might) have modified it */
+ if (bnr->lock_type == HFS_LOCK_WRITE) {
+ hfs_bnode_commit(bn);
+ }
+ hfs_bnode_delete(bn);
+ bnr->lock_type = HFS_LOCK_NONE;
+ }
+ bnr->bn = NULL;
+}
+
+/*
+ * hfs_bnode_find()
+ *
+ * Description:
+ * This function is called to obtain a bnode. The cache is
+ * searched for the node. If it not found there it is added to
+ * the cache by hfs_bnode_read(). There are two special cases node=0
+ * (the header node) and node='tree'->bthRoot (the root node), in
+ * which the nodes are obtained from fields of 'tree' without
+ * consulting or modifying the cache.
+ * Input Variable(s):
+ * struct hfs_tree *tree: pointer to the (struct hfs_btree) from
+ * which to get a node.
+ * int node: the node number to get from 'tree'.
+ * int lock_type: The kind of access (HFS_LOCK_READ, or
+ * HFS_LOCK_RESRV) to obtain to the node
+ * Output Variable(s):
+ * NONE
+ * Returns:
+ * (struct hfs_bnode_ref) Reference to the requested node.
+ * Preconditions:
+ * 'tree' points to a "valid" (struct hfs_btree).
+ * Postconditions:
+ * If 'node' refers to a valid node in 'tree' and 'lock_type' has
+ * one of the values listed above and no I/O errors occur then the
+ * value returned refers to a valid (struct hfs_bnode) corresponding
+ * to the requested node with the requested access type. The node
+ * is also added to the cache if not previously present and not the
+ * root or header.
+ * If the conditions given above are not met, the bnode in the
+ * returned reference is NULL.
+ */
+struct hfs_bnode_ref hfs_bnode_find(struct hfs_btree *tree,
+ hfs_u32 node, int lock_type)
+{
+ struct hfs_bnode *bn;
+ struct hfs_bnode *empty = NULL;
+ struct hfs_bnode_ref bnr;
+
+ bnr.lock_type = HFS_LOCK_NONE;
+ bnr.bn = NULL;
+
+#if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
+ hfs_warn("hfs_bnode_find: %c %d:%d\n",
+ lock_type==HFS_LOCK_READ?'R':
+ (lock_type==HFS_LOCK_RESRV?'V':'W'),
+ (int)ntohl(tree->entry.cnid), node);
+#endif
+
+ /* check special cases */
+ if (!node) {
+ bn = &tree->head;
+ goto return_it;
+ } else if (node == tree->bthRoot) {
+ bn = tree->root;
+ goto return_it;
+ }
+
+restart:
+ /* look for the node in the cache. */
+ bn = bhash(tree, node);
+ while (bn && (bn->magic == HFS_BNODE_MAGIC)) {
+ if (bn->node == node) {
+ goto found_it;
+ }
+ bn = bn->next;
+ }
+
+ if (!empty) {
+#if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
+ ++bnode_count;
+#endif
+ if (HFS_NEW(empty)) {
+ goto restart;
+ }
+ return bnr;
+ }
+ bn = empty;
+ hfs_bnode_read(bn, tree, node, HFS_NOT_STICKY);
+ goto return_it;
+
+found_it:
+ /* check validity */
+ if (bn->magic != HFS_BNODE_MAGIC) {
+ /* If we find a corrupt bnode then we return
+ NULL. However, we don't try to remove it
+ from the cache or release its resources
+ since we have no idea what kind of trouble
+ we could get into that way. */
+ hfs_warn("hfs_bnode_find: bnode cache is corrupt.\n");
+ return bnr;
+ }
+ if (empty) {
+#if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
+ --bnode_count;
+#endif
+ HFS_DELETE(empty);
+ }
+
+return_it:
+ /* Wait our turn */
+ bnr.bn = bn;
+ hfs_bnode_lock(&bnr, lock_type);
+
+ /* Check for failure to read the node from disk */
+ if (!hfs_buffer_ok(bn->buf)) {
+ hfs_bnode_relse(&bnr);
+ }
+
+#if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
+ if (!bnr.bn) {
+ hfs_warn("hfs_bnode_find: failed\n");
+ } else {
+ hfs_warn("hfs_bnode_find: use %d(%d) lvl %d [%d]\n", bn->count,
+ bn->buf->b_count, bn->ndNHeight, bnode_count);
+ }
+#endif
+
+ return bnr;
+}
+
+/*
+ * hfs_bnode_commit()
+ *
+ * Called to write a possibly dirty bnode back to disk.
+ */
+void hfs_bnode_commit(struct hfs_bnode *bn)
+{
+ if (hfs_buffer_ok(bn->buf)) {
+ struct NodeDescriptor *nd;
+ nd = (struct NodeDescriptor *)hfs_buffer_data(bn->buf);
+
+ hfs_put_hl(bn->ndFLink, nd->ndFLink);
+ hfs_put_hl(bn->ndBLink, nd->ndBLink);
+ nd->ndType = bn->ndType;
+ nd->ndNHeight = bn->ndNHeight;
+ hfs_put_hs(bn->ndNRecs, nd->ndNRecs);
+ hfs_buffer_dirty(bn->buf);
+
+ /* increment write count */
+ hfs_mdb_dirty(bn->tree->sys_mdb);
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-09-20 19:12:56 +0000