Subversion Repositories or1k

/*

 * linux/fs/hfs/balloc.c

 *

 * Copyright (C) 1995-1997  Paul H. Hargrove

 * This file may be distributed under the terms of the GNU General Public License.

 *

 * hfs_bnode_alloc() and hfs_bnode_bitop() are based on GPLed code

 * Copyright (C) 1995  Michael Dreher

 *

 * This file contains the code to create and destroy 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 functions ================*/

/*

 * get_new_node()

 *

 * Get a buffer for a new node with out reading it from disk.

 */

static hfs_buffer get_new_node(struct hfs_btree *tree, hfs_u32 node)

{

        int tmp;

        hfs_buffer retval = HFS_BAD_BUFFER;

        tmp = hfs_extent_map(&tree->entry.u.file.data_fork, node, 0);

        if (tmp) {

                retval = hfs_buffer_get(tree->sys_mdb, tmp, 0);

        }

        return retval;

}

/*

 * hfs_bnode_init()

 *

 * Description:

 *   Initialize a newly allocated bnode.

 * Input Variable(s):

 *   struct hfs_btree *tree: Pointer to a B-tree

 *   hfs_u32 node: the node number to allocate

 * Output Variable(s):

 *   NONE

 * Returns:

 *   struct hfs_bnode_ref for the new node

 * Preconditions:

 *   'tree' points to a "valid" (struct hfs_btree)

 *   'node' exists and has been allocated in the bitmap of bnodes.

 * Postconditions:

 *   On success:

 *    The node is not read from disk, nor added to the bnode cache.

 *    The 'sticky' and locking-related fields are all zero/NULL.

 *    The bnode's nd{[FB]Link, Type, NHeight} fields are uninitialized.

 *    The bnode's ndNRecs field and offsets table indicate an empty bnode.

 *   On failure:

 *    The node is deallocated.

 */

static struct hfs_bnode_ref hfs_bnode_init(struct hfs_btree * tree,

                                           hfs_u32 node)

{

#if defined(DEBUG_BNODES) || defined(DEBUG_ALL)

        extern int bnode_count;

#endif

        struct hfs_bnode_ref retval;

        retval.lock_type = HFS_LOCK_NONE;

        if (!HFS_NEW(retval.bn)) {

                hfs_warn("hfs_bnode_init: out of memory.\n");

                goto bail2;

        }

        /* Partially initialize the in-core structure */

        memset(retval.bn, 0, sizeof(*retval.bn));

        retval.bn->magic = HFS_BNODE_MAGIC;

        retval.bn->tree = tree;

        retval.bn->node = node;

        hfs_init_waitqueue(&retval.bn->wqueue);

        hfs_init_waitqueue(&retval.bn->rqueue);

        hfs_bnode_lock(&retval, HFS_LOCK_WRITE);

        retval.bn->buf = get_new_node(tree, node);

        if (!hfs_buffer_ok(retval.bn->buf)) {

                goto bail1;

        }

#if defined(DEBUG_BNODES) || defined(DEBUG_ALL)

        ++bnode_count;

#endif

        /* Partially initialize the on-disk structure */

        memset(hfs_buffer_data(retval.bn->buf), 0, HFS_SECTOR_SIZE);

        hfs_put_hs(sizeof(struct NodeDescriptor), RECTBL(retval.bn, 1));

        return retval;

bail1:

        HFS_DELETE(retval.bn);

bail2:

        /* clear the bit in the bitmap */

        hfs_bnode_bitop(tree, node, 0);

        return retval;

}

/*

 * init_mapnode()

 *

 * Description:

 *   Initializes a given node as a mapnode in the given tree.

 * Input Variable(s):

 *   struct hfs_bnode *bn: the node to add the mapnode after.

 *   hfs_u32: the node to use as a mapnode.

 * Output Variable(s):

 *   NONE

 * Returns:

 *   struct hfs_bnode *: the new mapnode or NULL

 * Preconditions:

 *   'tree' is a valid (struct hfs_btree).

 *   'node' is the number of the first node in 'tree' that is not

 *    represented by a bit in the existing mapnodes.

 * Postconditions:

 *   On failure 'tree' is unchanged and NULL is returned.

 *   On success the node given by 'node' has been added to the linked

 *    list of mapnodes attached to 'tree', and has been initialized as

 *    a valid mapnode with its first bit set to indicate itself as

 *    allocated.

 */

static struct hfs_bnode *init_mapnode(struct hfs_bnode *bn, hfs_u32 node)

{

#if defined(DEBUG_BNODES) || defined(DEBUG_ALL)

        extern int bnode_count;

#endif

        struct hfs_bnode *retval;

        if (!HFS_NEW(retval)) {

                hfs_warn("hfs_bnode_add: out of memory.\n");

                return NULL;

        }

        memset(retval, 0, sizeof(*retval));

        retval->magic = HFS_BNODE_MAGIC;

        retval->tree = bn->tree;

        retval->node = node;

        retval->sticky = HFS_STICKY;

        retval->buf = get_new_node(bn->tree, node);

        if (!hfs_buffer_ok(retval->buf)) {

                HFS_DELETE(retval);

                return NULL;

        }

#if defined(DEBUG_BNODES) || defined(DEBUG_ALL)

        ++bnode_count;

#endif

        /* Initialize the bnode data structure */

        memset(hfs_buffer_data(retval->buf), 0, HFS_SECTOR_SIZE);

        retval->ndFLink = 0;

        retval->ndBLink = bn->node;

        retval->ndType = ndMapNode;

        retval->ndNHeight = 0;

        retval->ndNRecs = 1;

        hfs_put_hs(sizeof(struct NodeDescriptor), RECTBL(retval, 1));

        hfs_put_hs(0x1fa,                         RECTBL(retval, 2));

        *((hfs_u8 *)bnode_key(retval, 1)) = 0x80; /* set first bit of bitmap */

        retval->prev = bn;

        hfs_bnode_commit(retval);

        bn->ndFLink = node;

        bn->next = retval;

        hfs_bnode_commit(bn);

        return retval;

}

/*================ Global functions ================*/

/*

 * hfs_bnode_bitop()

 *

 * Description:

 *   Allocate/free the requested node of a B-tree of the hfs filesystem

 *   by setting/clearing the corresponding bit in the B-tree bitmap.

 *   The size of the B-tree will not be changed.

 * Input Variable(s):

 *   struct hfs_btree *tree: Pointer to a B-tree

 *   hfs_u32 bitnr: The node number to free

 *   int set: 0 to clear the bit, non-zero to set it.

 * Output Variable(s):

 *   None

 * Returns:

 *    0: no error

 *   -1: The node was already allocated/free, nothing has been done.

 *   -2: The node is out of range of the B-tree.

 *   -4: not enough map nodes to hold all the bits

 * Preconditions:

 *   'tree' points to a "valid" (struct hfs_btree)

 *   'bitnr' is a node number within the range of the btree, which is

 *   currently free/allocated.

 * Postconditions:

 *   The bit number 'bitnr' of the node bitmap is set/cleared and the

 *   number of free nodes in the btree is decremented/incremented by one.

 */

int hfs_bnode_bitop(struct hfs_btree *tree, hfs_u32 bitnr, int set)

{

        struct hfs_bnode *bn;   /* the current bnode */

        hfs_u16 start;          /* the start (in bits) of the bitmap in node */

        hfs_u16 len;            /* the len (in bits) of the bitmap in node */

        hfs_u32 *u32;           /* address of the u32 containing the bit */

        if (bitnr >= tree->bthNNodes) {

                hfs_warn("hfs_bnode_bitop: node number out of range.\n");

                return -2;

        }

        bn = &tree->head;

        for (;;) {

                start = bnode_offset(bn, bn->ndNRecs) << 3;

                len = (bnode_offset(bn, bn->ndNRecs + 1) << 3) - start;

                if (bitnr < len) {

                        break;

                }

                /* continue on to next map node if available */

                if (!(bn = bn->next)) {

                        hfs_warn("hfs_bnode_bitop: too few map nodes.\n");

                        return -4;

                }

                bitnr -= len;

        }

        /* Change the correct bit */

        bitnr += start;

        u32 = (hfs_u32 *)hfs_buffer_data(bn->buf) + (bitnr >> 5);

        bitnr %= 32;

        if ((set && hfs_set_bit(bitnr, u32)) ||

            (!set && !hfs_clear_bit(bitnr, u32))) {

                hfs_warn("hfs_bnode_bitop: bitmap corruption.\n");

                return -1;

        }

        hfs_buffer_dirty(bn->buf);

        /* adjust the free count */

        tree->bthFree += (set ? -1 : 1);

        tree->dirt = 1;

        return 0;

}

/*

 * hfs_bnode_alloc()

 *

 * Description:

 *   Find a cleared bit in the B-tree node bitmap of the hfs filesystem,

 *   set it and return the corresponding bnode, with its contents zeroed.

 *   When there is no free bnode in the tree, an error is returned, no

 *   new nodes will be added by this function!

 * Input Variable(s):

 *   struct hfs_btree *tree: Pointer to a B-tree

 * Output Variable(s):

 *   NONE

 * Returns:

 *   struct hfs_bnode_ref for the new bnode

 * Preconditions:

 *   'tree' points to a "valid" (struct hfs_btree)

 *   There is at least one free bnode.

 * Postconditions:

 *   On success:

 *     The corresponding bit in the btree bitmap is set.

 *     The number of free nodes in the btree is decremented by one.

 *   The node is not read from disk, nor added to the bnode cache.

 *   The 'sticky' field is uninitialized.

 */

struct hfs_bnode_ref hfs_bnode_alloc(struct hfs_btree *tree)

{

        struct hfs_bnode *bn;   /* the current bnode */

        hfs_u32 bitnr = 0;       /* which bit are we examining */

        hfs_u16 first;          /* the first clear bit in this bnode */

        hfs_u16 start;          /* the start (in bits) of the bitmap in node */

        hfs_u16 end;            /* the end (in bits) of the bitmap in node */

        hfs_u32 *data;          /* address of the data in this bnode */

        bn = &tree->head;

        for (;;) {

                start = bnode_offset(bn, bn->ndNRecs) << 3;

                end = bnode_offset(bn, bn->ndNRecs + 1) << 3;

                data =  (hfs_u32 *)hfs_buffer_data(bn->buf);

                /* search the current node */

                first = hfs_find_zero_bit(data, end, start);

                if (first < end) {

                        break;

                }

                /* continue search in next map node */

                bn = bn->next;

                if (!bn) {

                        hfs_warn("hfs_bnode_alloc: too few map nodes.\n");

                        goto bail;

                }

                bitnr += (end - start);

        }

        if ((bitnr += (first - start)) >= tree->bthNNodes) {

                hfs_warn("hfs_bnode_alloc: no free nodes found, "

                         "count wrong?\n");

                goto bail;

        }

        if (hfs_set_bit(first % 32, data + (first>>5))) {

                hfs_warn("hfs_bnode_alloc: bitmap corruption.\n");

                goto bail;

        }

        hfs_buffer_dirty(bn->buf);

        /* decrement the free count */

        --tree->bthFree;

        tree->dirt = 1;

        return hfs_bnode_init(tree, bitnr);

bail:

        return (struct hfs_bnode_ref){NULL, HFS_LOCK_NONE};

}

/*

 * hfs_btree_extend()

 *

 * Description:

 *   Adds nodes to a B*-tree if possible.

 * Input Variable(s):

 *   struct hfs_btree *tree: the btree to add nodes to.

 * Output Variable(s):

 *   NONE

 * Returns:

 *   void

 * Preconditions:

 *   'tree' is a valid (struct hfs_btree *).

 * Postconditions:

 *   If possible the number of nodes indicated by the tree's clumpsize

 *    have been added to the tree, updating all in-core and on-disk

 *    allocation information.

 *   If insufficient disk-space was available then fewer nodes may have

 *    been added than would be expected based on the clumpsize.

 *   In the case of the extents B*-tree this function will add fewer

 *    nodes than expected if adding more would result in an extent

 *    record for the extents tree being added to the extents tree.

 *    The situation could be dealt with, but doing so confuses Macs.

 */

void hfs_btree_extend(struct hfs_btree *tree)

{

        struct hfs_bnode_ref head;

        struct hfs_bnode *bn, *tmp;

        struct hfs_cat_entry *entry = &tree->entry;

        struct hfs_mdb *mdb = entry->mdb;

        hfs_u32 old_nodes, new_nodes, total_nodes, new_mapnodes, seen;

        old_nodes = entry->u.file.data_fork.psize;

        entry->u.file.data_fork.lsize += 1; /* rounded up to clumpsize */

        hfs_extent_adj(&entry->u.file.data_fork);

        total_nodes = entry->u.file.data_fork.psize;

        entry->u.file.data_fork.lsize = total_nodes << HFS_SECTOR_SIZE_BITS;

        new_nodes = total_nodes - old_nodes;

        if (!new_nodes) {

                return;

        }

        head = hfs_bnode_find(tree, 0, HFS_LOCK_WRITE);

        if (!(bn = head.bn)) {

                hfs_warn("hfs_btree_extend: header node not found.\n");

                return;

        }

        seen = 0;

        new_mapnodes = 0;

        for (;;) {

                seen += bnode_rsize(bn, bn->ndNRecs) << 3;

                if (seen >= total_nodes) {

                        break;

                }

                if (!bn->next) {

                        tmp = init_mapnode(bn, seen);

                        if (!tmp) {

                                hfs_warn("hfs_btree_extend: "

                                         "can't build mapnode.\n");

                                hfs_bnode_relse(&head);

                                return;

                        }

                        ++new_mapnodes;

                }

                bn = bn->next;

        }

        hfs_bnode_relse(&head);

        tree->bthNNodes = total_nodes;

        tree->bthFree += (new_nodes - new_mapnodes);

        tree->dirt = 1;

        /* write the backup MDB, not returning until it is written */

        hfs_mdb_commit(mdb, 1);

        return;

}

/*

 * hfs_bnode_free()

 *

 * Remove a node from the cache and mark it free in the bitmap.

 */

int hfs_bnode_free(struct hfs_bnode_ref *bnr)

{

        hfs_u32 node = bnr->bn->node;

        struct hfs_btree *tree = bnr->bn->tree;

        if (bnr->bn->count != 1) {

                hfs_warn("hfs_bnode_free: count != 1.\n");

                return -EIO;

        }

        hfs_bnode_relse(bnr);

        hfs_bnode_bitop(tree, node, 0);

        return 0;

}