Viewing file:  btree.c (9.46 KB) -rw-r--r--
Select action/file-type:
 (+) |  (+) |  (+) | Code (+) | Session (+) |  (+) | SDB (+) |  (+) |  (+) |  (+) |  (+) |  (+) |
/*
* linux/fs/hfs/btree.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 manipulate the B-tree structure.
* The catalog and extents files are both B-trees.
*
* "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 functions ================*/
/*
* hfs_bnode_ditch()
*
* Description:
* This function deletes an entire linked list of bnodes, so it
* does not need to keep the linked list consistent as
* hfs_bnode_delete() does.
* Called by hfs_btree_init() for error cleanup and by hfs_btree_free().
* Input Variable(s):
* struct hfs_bnode *bn: pointer to the first (struct hfs_bnode) in
* the linked list to be deleted.
* Output Variable(s):
* NONE
* Returns:
* void
* Preconditions:
* 'bn' is NULL or points to a "valid" (struct hfs_bnode) with a 'prev'
* field of NULL.
* Postconditions:
* 'bn' and all (struct hfs_bnode)s in the chain of 'next' pointers
* are deleted, freeing the associated memory and hfs_buffer_put()ing
* the associated buffer.
*/
static void hfs_bnode_ditch(struct hfs_bnode *bn) {
struct hfs_bnode *tmp;
#if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
extern int bnode_count;
#endif
while (bn != NULL) {
tmp = bn->next;
#if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
hfs_warn("deleting node %d from tree %d with count %d\n",
bn->node, (int)ntohl(bn->tree->entry.cnid), bn->count);
--bnode_count;
#endif
hfs_buffer_put(bn->buf); /* safe: checks for NULL argument */
/* free all but the header */
if (bn->node) {
HFS_DELETE(bn);
}
bn = tmp;
}
}
/*================ Global functions ================*/
/*
* hfs_btree_free()
*
* Description:
* This function frees a (struct hfs_btree) obtained from hfs_btree_init().
* Called by hfs_put_super().
* Input Variable(s):
* struct hfs_btree *bt: pointer to the (struct hfs_btree) to free
* Output Variable(s):
* NONE
* Returns:
* void
* Preconditions:
* 'bt' is NULL or points to a "valid" (struct hfs_btree)
* Postconditions:
* If 'bt' points to a "valid" (struct hfs_btree) then all (struct
* hfs_bnode)s associated with 'bt' are freed by calling
* hfs_bnode_ditch() and the memory associated with the (struct
* hfs_btree) is freed.
* If 'bt' is NULL or not "valid" an error is printed and nothing
* is changed.
*/
void hfs_btree_free(struct hfs_btree *bt)
{
int lcv;
if (bt && (bt->magic == HFS_BTREE_MAGIC)) {
hfs_extent_free(&bt->entry.u.file.data_fork);
for (lcv=0; lcv<HFS_CACHELEN; ++lcv) {
#if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
hfs_warn("deleting nodes from bucket %d:\n", lcv);
#endif
hfs_bnode_ditch(bt->cache[lcv]);
}
#if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
hfs_warn("deleting header and bitmap nodes\n");
#endif
hfs_bnode_ditch(&bt->head);
#if defined(DEBUG_BNODES) || defined(DEBUG_ALL)
hfs_warn("deleting root node\n");
#endif
hfs_bnode_ditch(bt->root);
HFS_DELETE(bt);
} else if (bt) {
hfs_warn("hfs_btree_free: corrupted hfs_btree.\n");
}
}
/*
* hfs_btree_init()
*
* Description:
* Given some vital information from the MDB (HFS superblock),
* initializes the fields of a (struct hfs_btree).
* Input Variable(s):
* struct hfs_mdb *mdb: pointer to the MDB
* ino_t cnid: the CNID (HFS_CAT_CNID or HFS_EXT_CNID) of the B-tree
* hfs_u32 tsize: the size, in bytes, of the B-tree
* hfs_u32 csize: the size, in bytes, of the clump size for the B-tree
* Output Variable(s):
* NONE
* Returns:
* (struct hfs_btree *): pointer to the initialized hfs_btree on success,
* or NULL on failure
* Preconditions:
* 'mdb' points to a "valid" (struct hfs_mdb)
* Postconditions:
* Assuming the inputs are what they claim to be, no errors occur
* reading from disk, and no inconsistencies are noticed in the data
* read from disk, the return value is a pointer to a "valid"
* (struct hfs_btree). If there are errors reading from disk or
* inconsistencies are noticed in the data read from disk, then and
* all resources that were allocated are released and NULL is
* returned. If the inputs are not what they claim to be or if they
* are unnoticed inconsistencies in the data read from disk then the
* returned hfs_btree is probably going to lead to errors when it is
* used in a non-trivial way.
*/
struct hfs_btree * hfs_btree_init(struct hfs_mdb *mdb, ino_t cnid,
hfs_byte_t ext[12],
hfs_u32 tsize, hfs_u32 csize)
{
struct hfs_btree * bt;
struct BTHdrRec * th;
struct hfs_bnode * tmp;
unsigned int next;
#if defined(DEBUG_HEADER) || defined(DEBUG_ALL)
unsigned char *p, *q;
#endif
if (!mdb || !ext || !HFS_NEW(bt)) {
goto bail3;
}
bt->magic = HFS_BTREE_MAGIC;
bt->sys_mdb = mdb->sys_mdb;
bt->reserved = 0;
bt->lock = 0;
hfs_init_waitqueue(&bt->wait);
bt->dirt = 0;
memset(bt->cache, 0, sizeof(bt->cache));
#if 0 /* this is a fake entry. so we don't need to initialize it. */
memset(&bt->entry, 0, sizeof(bt->entry));
hfs_init_waitqueue(&bt->entry.wait);
INIT_LIST_HEAD(&bt->entry.hash);
INIT_LIST_HEAD(&bt->entry.list);
#endif
bt->entry.mdb = mdb;
bt->entry.cnid = cnid;
bt->entry.type = HFS_CDR_FIL;
bt->entry.u.file.magic = HFS_FILE_MAGIC;
bt->entry.u.file.clumpablks = (csize / mdb->alloc_blksz)
>> HFS_SECTOR_SIZE_BITS;
bt->entry.u.file.data_fork.entry = &bt->entry;
bt->entry.u.file.data_fork.lsize = tsize;
bt->entry.u.file.data_fork.psize = tsize >> HFS_SECTOR_SIZE_BITS;
bt->entry.u.file.data_fork.fork = HFS_FK_DATA;
hfs_extent_in(&bt->entry.u.file.data_fork, ext);
hfs_bnode_read(&bt->head, bt, 0, HFS_STICKY);
if (!hfs_buffer_ok(bt->head.buf)) {
goto bail2;
}
th = (struct BTHdrRec *)((char *)hfs_buffer_data(bt->head.buf) +
sizeof(struct NodeDescriptor));
/* read in the bitmap nodes (if any) */
tmp = &bt->head;
while ((next = tmp->ndFLink)) {
if (!HFS_NEW(tmp->next)) {
goto bail2;
}
hfs_bnode_read(tmp->next, bt, next, HFS_STICKY);
if (!hfs_buffer_ok(tmp->next->buf)) {
goto bail2;
}
tmp->next->prev = tmp;
tmp = tmp->next;
}
if (hfs_get_ns(th->bthNodeSize) != htons(HFS_SECTOR_SIZE)) {
hfs_warn("hfs_btree_init: bthNodeSize!=512 not supported\n");
goto bail2;
}
if (cnid == htonl(HFS_CAT_CNID)) {
bt->compare = (hfs_cmpfn)hfs_cat_compare;
} else if (cnid == htonl(HFS_EXT_CNID)) {
bt->compare = (hfs_cmpfn)hfs_ext_compare;
} else {
goto bail2;
}
bt->bthDepth = hfs_get_hs(th->bthDepth);
bt->bthRoot = hfs_get_hl(th->bthRoot);
bt->bthNRecs = hfs_get_hl(th->bthNRecs);
bt->bthFNode = hfs_get_hl(th->bthFNode);
bt->bthLNode = hfs_get_hl(th->bthLNode);
bt->bthNNodes = hfs_get_hl(th->bthNNodes);
bt->bthFree = hfs_get_hl(th->bthFree);
bt->bthKeyLen = hfs_get_hs(th->bthKeyLen);
#if defined(DEBUG_HEADER) || defined(DEBUG_ALL)
hfs_warn("bthDepth %d\n", bt->bthDepth);
hfs_warn("bthRoot %d\n", bt->bthRoot);
hfs_warn("bthNRecs %d\n", bt->bthNRecs);
hfs_warn("bthFNode %d\n", bt->bthFNode);
hfs_warn("bthLNode %d\n", bt->bthLNode);
hfs_warn("bthKeyLen %d\n", bt->bthKeyLen);
hfs_warn("bthNNodes %d\n", bt->bthNNodes);
hfs_warn("bthFree %d\n", bt->bthFree);
p = (unsigned char *)hfs_buffer_data(bt->head.buf);
q = p + HFS_SECTOR_SIZE;
while (p < q) {
hfs_warn("%02x %02x %02x %02x %02x %02x %02x %02x "
"%02x %02x %02x %02x %02x %02x %02x %02x\n",
*p++, *p++, *p++, *p++, *p++, *p++, *p++, *p++,
*p++, *p++, *p++, *p++, *p++, *p++, *p++, *p++);
}
#endif
/* Read in the root if it exists.
The header always exists, but the root exists only if the
tree is non-empty */
if (bt->bthDepth && bt->bthRoot) {
if (!HFS_NEW(bt->root)) {
goto bail2;
}
hfs_bnode_read(bt->root, bt, bt->bthRoot, HFS_STICKY);
if (!hfs_buffer_ok(bt->root->buf)) {
goto bail1;
}
} else {
bt->root = NULL;
}
return bt;
bail1:
hfs_bnode_ditch(bt->root);
bail2:
hfs_bnode_ditch(&bt->head);
HFS_DELETE(bt);
bail3:
return NULL;
}
/*
* hfs_btree_commit()
*
* Called to write a possibly dirty btree back to disk.
*/
void hfs_btree_commit(struct hfs_btree *bt, hfs_byte_t ext[12], hfs_lword_t size)
{
if (bt->dirt) {
struct BTHdrRec *th;
th = (struct BTHdrRec *)((char *)hfs_buffer_data(bt->head.buf) +
sizeof(struct NodeDescriptor));
hfs_put_hs(bt->bthDepth, th->bthDepth);
hfs_put_hl(bt->bthRoot, th->bthRoot);
hfs_put_hl(bt->bthNRecs, th->bthNRecs);
hfs_put_hl(bt->bthFNode, th->bthFNode);
hfs_put_hl(bt->bthLNode, th->bthLNode);
hfs_put_hl(bt->bthNNodes, th->bthNNodes);
hfs_put_hl(bt->bthFree, th->bthFree);
hfs_buffer_dirty(bt->head.buf);
/*
* Commit the bnodes which are not cached.
* The map nodes don't need to be committed here because
* they are committed every time they are changed.
*/
hfs_bnode_commit(&bt->head);
if (bt->root) {
hfs_bnode_commit(bt->root);
}
hfs_put_hl(bt->bthNNodes << HFS_SECTOR_SIZE_BITS, size);
hfs_extent_out(&bt->entry.u.file.data_fork, ext);
/* hfs_buffer_dirty(mdb->buf); (Done by caller) */
bt->dirt = 0;
}
}
|