URL
https://opencores.org/ocsvn/or1k/or1k/trunk
Subversion Repositories or1k
[/] [or1k/] [tags/] [LINUX_2_4_26_OR32/] [linux/] [linux-2.4/] [fs/] [hfs/] [bnode.c] - Rev 1780
Go to most recent revision | Compare with Previous | Blame | View Log
/* * linux/fs/hfs/bnode.c * * Copyright (C) 1995-1997 Paul H. Hargrove * This file may be distributed under the terms of the GNU General 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; hfs_init_waitqueue(&bnode->rqueue); hfs_init_waitqueue(&bnode->wqueue); 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 || waitqueue_active(&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) || (waitqueue_active(&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); hfs_warn("hfs_bnode_find: blnk %u flnk %u recs %u\n", bn->ndBLink, bn->ndFLink, bn->ndNRecs); } #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); } }
Go to most recent revision | Compare with Previous | Blame | View Log