diff options
Diffstat (limited to 'fs/hfs/balloc.c')
| -rw-r--r-- | fs/hfs/balloc.c | 437 |
1 files changed, 437 insertions, 0 deletions
diff --git a/fs/hfs/balloc.c b/fs/hfs/balloc.c new file mode 100644 index 000000000..d7e17e72f --- /dev/null +++ b/fs/hfs/balloc.c @@ -0,0 +1,437 @@ +/* + * linux/fs/hfs/balloc.c + * + * Copyright (C) 1995-1997 Paul H. Hargrove + * This file may be distributed under the terms of the GNU 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_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; +} |