Subversion Repositories or1k

/*

 * linux/fs/hfs/extent.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 functions related to the extents B-tree.

 *

 * "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.

 */

#include "hfs.h"

/*================ File-local data type ================*/

/* An extent record on disk*/

struct hfs_raw_extent {

        hfs_word_t      block1;

        hfs_word_t      length1;

        hfs_word_t      block2;

        hfs_word_t      length2;

        hfs_word_t      block3;

        hfs_word_t      length3;

};

/*================ File-local functions ================*/

/*

 * build_key

 */

static inline void build_key(struct hfs_ext_key *key,

                             const struct hfs_fork *fork, hfs_u16 block)

{

        key->KeyLen = 7;

        key->FkType = fork->fork;

        hfs_put_nl(fork->entry->cnid, key->FNum);

        hfs_put_hs(block,             key->FABN);

}

/*

 * lock_bitmap()

 *

 * Get an exclusive lock on the B-tree bitmap.

 */

static inline void lock_bitmap(struct hfs_mdb *mdb) {

        while (mdb->bitmap_lock) {

                hfs_sleep_on(&mdb->bitmap_wait);

        }

        mdb->bitmap_lock = 1;

}

/*

 * unlock_bitmap()

 *

 * Relinquish an exclusive lock on the B-tree bitmap.

 */

static inline void unlock_bitmap(struct hfs_mdb *mdb) {

        mdb->bitmap_lock = 0;

        hfs_wake_up(&mdb->bitmap_wait);

}

/*

 * dump_ext()

 *

 * prints the content of a extent for debugging purposes.

 */

#if defined(DEBUG_EXTENTS) || defined(DEBUG_ALL)

static void dump_ext(const char *msg, const struct hfs_extent *e) {

        if (e) {

                hfs_warn("%s (%d-%d) (%d-%d) (%d-%d)\n", msg,

                         e->start,

                         e->start + e->length[0] - 1,

                         e->start + e->length[0],

                         e->start + e->length[0] + e->length[1] - 1,

                         e->start + e->length[0] + e->length[1],

                         e->end);

        } else {

                hfs_warn("%s NULL\n", msg);

        }

}

#else

#define dump_ext(A,B) {}

#endif

/*

 * read_extent()

 *

 * Initializes a (struct hfs_extent) from a (struct hfs_raw_extent) and

 * the number of the starting block for the extent.

 *

 * Note that the callers must check that to,from != NULL

 */

static void read_extent(struct hfs_extent *to,

                        const struct hfs_raw_extent *from,

                        hfs_u16 start)

{

        to->start = start;

        to->block[0]  = hfs_get_hs(from->block1);

        to->length[0] = hfs_get_hs(from->length1);

        to->block[1]  = hfs_get_hs(from->block2);

        to->length[1] = hfs_get_hs(from->length2);

        to->block[2]  = hfs_get_hs(from->block3);

        to->length[2] = hfs_get_hs(from->length3);

        to->end = start + to->length[0] + to->length[1] + to->length[2] - 1;

        to->next = to->prev = NULL;

        to->count = 0;

}

/*

 * write_extent()

 *

 * Initializes a (struct hfs_raw_extent) from a (struct hfs_extent).

 *

 * Note that the callers must check that to,from != NULL

 */

static void write_extent(struct hfs_raw_extent *to,

                         const struct hfs_extent *from)

{

        hfs_put_hs(from->block[0], to->block1);

        hfs_put_hs(from->length[0], to->length1);

        hfs_put_hs(from->block[1], to->block2);

        hfs_put_hs(from->length[1], to->length2);

        hfs_put_hs(from->block[2], to->block3);

        hfs_put_hs(from->length[2], to->length3);

}

/*

 * decode_extent()

 *

 * Given an extent record and allocation block offset into the file,

 * return the number of the corresponding allocation block on disk,

 * or -1 if the desired block is not mapped by the given extent.

 *

 * Note that callers must check that extent != NULL

 */

static int decode_extent(const struct hfs_extent * extent, int block)

{

        if (!extent || (block < extent->start) || (block > extent->end) ||

            (extent->end == (hfs_u16)(extent->start - 1))) {

                return -1;

        }

        block -= extent->start;

        if (block < extent->length[0]) {

                return block + extent->block[0];

        }

        block -= extent->length[0];

        if (block < extent->length[1]) {

                return block + extent->block[1];

        }

        return block + extent->block[2] - extent->length[1];

}

/*

 * relse_ext()

 *

 * Reduce the reference count of an in-core extent record by one,

 * removing it from memory if the count falls to zero.

 */

static void relse_ext(struct hfs_extent *ext)

{

        if (--ext->count || !ext->start) {

                return;

        }

        ext->prev->next = ext->next;

        if (ext->next) {

                ext->next->prev = ext->prev;

        }

        HFS_DELETE(ext);

}

/*

 * set_cache()

 *

 * Changes the 'cache' field of the fork.

 */

static inline void set_cache(struct hfs_fork *fork, struct hfs_extent *ext)

{

        struct hfs_extent *tmp = fork->cache;

        ++ext->count;

        fork->cache = ext;

        relse_ext(tmp);

}

/*

 * find_ext()

 *

 * Given a pointer to a (struct hfs_file) and an allocation block

 * number in the file, find the extent record containing that block.

 * Returns a pointer to the extent record on success or NULL on failure.

 * The 'cache' field of 'fil' also points to the extent so it has a

 * reference count of at least 2.

 *

 * Callers must check that fil != NULL

 */

static struct hfs_extent * find_ext(struct hfs_fork *fork, int alloc_block)

{

        struct hfs_cat_entry *entry = fork->entry;

        struct hfs_btree *tr= entry->mdb->ext_tree;

        struct hfs_ext_key target, *key;

        struct hfs_brec brec;

        struct hfs_extent *ext, *ptr;

        int tmp;

        if (alloc_block < 0) {

                ext = &fork->first;

                goto found;

        }

        ext = fork->cache;

        if (!ext || (alloc_block < ext->start)) {

                ext = &fork->first;

        }

        while (ext->next && (alloc_block > ext->end)) {

                ext = ext->next;

        }

        if ((alloc_block <= ext->end) && (alloc_block >= ext->start)) {

                goto found;

        }

        /* time to read more extents */

        if (!HFS_NEW(ext)) {

                goto bail3;

        }

        build_key(&target, fork, alloc_block);

        tmp = hfs_bfind(&brec, tr, HFS_BKEY(&target), HFS_BFIND_READ_LE);

        if (tmp < 0) {

                goto bail2;

        }

        key = (struct hfs_ext_key *)brec.key;

        if ((hfs_get_nl(key->FNum) != hfs_get_nl(target.FNum)) ||

            (key->FkType != fork->fork)) {

                goto bail1;

        }

        read_extent(ext, brec.data, hfs_get_hs(key->FABN));

        hfs_brec_relse(&brec, NULL);

        if ((alloc_block > ext->end) && (alloc_block < ext->start)) {

                /* something strange happened */

                goto bail2;

        }

        ptr = fork->cache;

        if (!ptr || (alloc_block < ptr->start)) {

                ptr = &fork->first;

        }

        while (ptr->next && (alloc_block > ptr->end)) {

                ptr = ptr->next;

        }

        if (ext->start == ptr->start) {

                /* somebody beat us to it. */

                HFS_DELETE(ext);

                ext = ptr;

        } else if (ext->start < ptr->start) {

                /* insert just before ptr */

                ptr->prev->next = ext;

                ext->prev = ptr->prev;

                ext->next = ptr;

                ptr->prev = ext;

        } else {

                /* insert at end */

                ptr->next = ext;

                ext->prev = ptr;

        }

 found:

        ++ext->count; /* for return value */

        set_cache(fork, ext);

        return ext;

 bail1:

        hfs_brec_relse(&brec, NULL);

 bail2:

        HFS_DELETE(ext);

 bail3:

        return NULL;

}

/*

 * delete_extent()

 *

 * Description:

 *   Deletes an extent record from a fork, reducing its physical length.

 * Input Variable(s):

 *   struct hfs_fork *fork: the fork

 *   struct hfs_extent *ext: the current last extent for 'fork'

 * Output Variable(s):

 *   NONE

 * Returns:

 *   void

 * Preconditions:

 *   'fork' points to a valid (struct hfs_fork)

 *   'ext' point to a valid (struct hfs_extent) which is the last in 'fork'

 *    and which is not also the first extent in 'fork'.

 * Postconditions:

 *   The extent record has been removed if possible, and a warning has been

 *   printed otherwise.

 */

static void delete_extent(struct hfs_fork *fork, struct hfs_extent *ext)

{

        struct hfs_mdb *mdb = fork->entry->mdb;

        struct hfs_ext_key key;

        int error;

        if (fork->cache == ext) {

                set_cache(fork, ext->prev);

        }

        ext->prev->next = NULL;

        if (ext->count != 1) {

                hfs_warn("hfs_truncate: extent has count %d.\n", ext->count);

        }

        lock_bitmap(mdb);

        error = hfs_clear_vbm_bits(mdb, ext->block[2], ext->length[2]);

        if (error) {

                hfs_warn("hfs_truncate: error %d freeing blocks.\n", error);

        }

        error = hfs_clear_vbm_bits(mdb, ext->block[1], ext->length[1]);

        if (error) {

                hfs_warn("hfs_truncate: error %d freeing blocks.\n", error);

        }

        error = hfs_clear_vbm_bits(mdb, ext->block[0], ext->length[0]);

        if (error) {

                hfs_warn("hfs_truncate: error %d freeing blocks.\n", error);

        }

        unlock_bitmap(mdb);

        build_key(&key, fork, ext->start);

        error = hfs_bdelete(mdb->ext_tree, HFS_BKEY(&key));

        if (error) {

                hfs_warn("hfs_truncate: error %d deleting an extent.\n", error);

        }

        HFS_DELETE(ext);

}

/*

 * new_extent()

 *

 * Description:

 *   Adds a new extent record to a fork, extending its physical length.

 * Input Variable(s):

 *   struct hfs_fork *fork: the fork to extend

 *   struct hfs_extent *ext: the current last extent for 'fork'

 *   hfs_u16 ablock: the number of allocation blocks in 'fork'.

 *   hfs_u16 start: first allocation block to add to 'fork'.

 *   hfs_u16 len: the number of allocation blocks to add to 'fork'.

 *   hfs_u32 ablksz: number of sectors in an allocation block.

 * Output Variable(s):

 *   NONE

 * Returns:

 *   (struct hfs_extent *) the new extent or NULL

 * Preconditions:

 *   'fork' points to a valid (struct hfs_fork)

 *   'ext' point to a valid (struct hfs_extent) which is the last in 'fork'

 *   'ablock', 'start', 'len' and 'ablksz' are what they claim to be.

 * Postconditions:

 *   If NULL is returned then no changes have been made to 'fork'.

 *   If the return value is non-NULL that it is the extent that has been

 *   added to 'fork' both in memory and on disk.  The 'psize' field of

 *   'fork' has been updated to reflect the new physical size.

 */

static struct hfs_extent *new_extent(struct hfs_fork *fork,

                                     struct hfs_extent *ext,

                                     hfs_u16 ablock, hfs_u16 start,

                                     hfs_u16 len, hfs_u16 ablksz)

{

        struct hfs_raw_extent raw;

        struct hfs_ext_key key;

        int error;

        if (fork->entry->cnid == htonl(HFS_EXT_CNID)) {

                /* Limit extents tree to the record in the MDB */

                return NULL;

        }

        if (!HFS_NEW(ext->next)) {

                return NULL;

        }

        ext->next->prev = ext;

        ext->next->next = NULL;

        ext = ext->next;

        relse_ext(ext->prev);

        ext->start = ablock;

        ext->block[0] = start;

        ext->length[0] = len;

        ext->block[1] = 0;

        ext->length[1] = 0;

        ext->block[2] = 0;

        ext->length[2] = 0;

        ext->end = ablock + len - 1;

        ext->count = 1;

        write_extent(&raw, ext);

        build_key(&key, fork, ablock);

        error = hfs_binsert(fork->entry->mdb->ext_tree,

                            HFS_BKEY(&key), &raw, sizeof(raw));

        if (error) {

                ext->prev->next = NULL;

                HFS_DELETE(ext);

                return NULL;

        }

        set_cache(fork, ext);

        return ext;

}

/*

 * update_ext()

 *

 * Given a (struct hfs_fork) write an extent record back to disk.

 */

static void update_ext(struct hfs_fork *fork, struct hfs_extent *ext)

{

        struct hfs_ext_key target;

        struct hfs_brec brec;

        if (ext->start) {

                build_key(&target, fork, ext->start);

                if (!hfs_bfind(&brec, fork->entry->mdb->ext_tree,

                               HFS_BKEY(&target), HFS_BFIND_WRITE)) {

                        write_extent(brec.data, ext);

                        hfs_brec_relse(&brec, NULL);

                }

        }

}

/*

 * zero_blocks()

 *

 * Zeros-out 'num' allocation blocks beginning with 'start'.

 */

static int zero_blocks(struct hfs_mdb *mdb, int start, int num) {

        hfs_buffer buf;

        int end;

        int j;

        start = mdb->fs_start + start * mdb->alloc_blksz;

        end = start + num * mdb->alloc_blksz;

        for (j=start; j<end; ++j) {

                if (hfs_buffer_ok(buf = hfs_buffer_get(mdb->sys_mdb, j, 0))) {

                        memset(hfs_buffer_data(buf), 0, HFS_SECTOR_SIZE);

                        hfs_buffer_dirty(buf);

                        hfs_buffer_put(buf);

                }

        }

        return 0;

}

/*

 * shrink_fork()

 *

 * Try to remove enough allocation blocks from 'fork'

 * so that it is 'ablocks' allocation blocks long.

 */

static void shrink_fork(struct hfs_fork *fork, int ablocks)

{

        struct hfs_mdb *mdb = fork->entry->mdb;

        struct hfs_extent *ext;

        int i, error, next, count;

        hfs_u32 ablksz = mdb->alloc_blksz;

        next =  (fork->psize / ablksz) - 1;

        ext = find_ext(fork, next);

        while (ext && ext->start && (ext->start >= ablocks)) {

                next = ext->start - 1;

                delete_extent(fork, ext);

                ext = find_ext(fork, next);

        }

        if (!ext) {

                fork->psize = (next + 1) * ablksz;

                return;

        }

        if ((count = next + 1 - ablocks) > 0) {

                for (i=2; (i>=0) && !ext->length[i]; --i) {};

                lock_bitmap(mdb);

                while (count && (ext->length[i] <= count)) {

                        ext->end -= ext->length[i];

                        count -= ext->length[i];

                        error = hfs_clear_vbm_bits(mdb, ext->block[i],

                                                   ext->length[i]);

                        if (error) {

                                hfs_warn("hfs_truncate: error %d freeing "

                                       "blocks.\n", error);

                        }

                        ext->block[i] = ext->length[i] = 0;

                        --i;

                }

                if (count) {

                        ext->end -= count;

                        ext->length[i] -= count;

                        error = hfs_clear_vbm_bits(mdb, ext->block[i] +

                                                       ext->length[i], count);

                        if (error) {

                                hfs_warn("hfs_truncate: error %d freeing "

                                       "blocks.\n", error);

                        }

                }

                unlock_bitmap(mdb);

                update_ext(fork, ext);

        }

        fork->psize = ablocks * ablksz;

}

/*

 * grow_fork()

 *

 * Try to add enough allocation blocks to 'fork'

 * so that it is 'ablock' allocation blocks long.

 */

static int grow_fork(struct hfs_fork *fork, int ablocks)

{

        struct hfs_cat_entry *entry = fork->entry;

        struct hfs_mdb *mdb = entry->mdb;

        struct hfs_extent *ext;

        int i, start, err;

        hfs_u16 need, len=0;

        hfs_u32 ablksz = mdb->alloc_blksz;

        hfs_u32 blocks, clumpablks;

        blocks = fork->psize;

        need = ablocks - blocks/ablksz;

        if (need < 1) { /* no need to grow the fork */

                return 0;

        }

        /* round up to clumpsize */

        if (entry->u.file.clumpablks) {

                clumpablks = entry->u.file.clumpablks;

        } else {

                clumpablks = mdb->clumpablks;

        }

        need = ((need + clumpablks - 1) / clumpablks) * clumpablks;

        /* find last extent record and try to extend it */

        if (!(ext = find_ext(fork, blocks/ablksz - 1))) {

                /* somehow we couldn't find the end of the file! */

                return -1;

        }

        /* determine which is the last used extent in the record */

        /* then try to allocate the blocks immediately following it */

        for (i=2; (i>=0) && !ext->length[i]; --i) {};

        if (i>=0) {

                /* try to extend the last extent */

                start = ext->block[i] + ext->length[i];

                err = 0;

                lock_bitmap(mdb);

                len = hfs_vbm_count_free(mdb, start);

                if (!len) {

                        unlock_bitmap(mdb);

                        goto more_extents;

                }

                if (need < len) {

                        len = need;

                }

                err = hfs_set_vbm_bits(mdb, start, len);

                unlock_bitmap(mdb);

                if (err) {

                        relse_ext(ext);

                        return -1;

                }

                zero_blocks(mdb, start, len);

                ext->length[i] += len;

                ext->end += len;

                blocks = (fork->psize += len * ablksz);

                need -= len;

                update_ext(fork, ext);

        }

more_extents:

        /* add some more extents */

        while (need) {

                len = need;

                err = 0;

                lock_bitmap(mdb);

                start = hfs_vbm_search_free(mdb, &len);

                if (need < len) {

                        len = need;

                }

                err = hfs_set_vbm_bits(mdb, start, len);

                unlock_bitmap(mdb);

                if (!len || err) {

                        relse_ext(ext);

                        return -1;

                }

                zero_blocks(mdb, start, len);

                /* determine which is the first free extent in the record */

                for (i=0; (i<3) && ext->length[i]; ++i) {};

                if (i < 3) {

                        ext->block[i] = start;

                        ext->length[i] = len;

                        ext->end += len;

                        update_ext(fork, ext);

                } else {

                        if (!(ext = new_extent(fork, ext, blocks/ablksz,

                                               start, len, ablksz))) {

                                lock_bitmap(mdb);

                                hfs_clear_vbm_bits(mdb, start, len);

                                unlock_bitmap(mdb);

                                return -1;

                        }

                }

                blocks = (fork->psize += len * ablksz);

                need -= len;

        }

        set_cache(fork, ext);

        relse_ext(ext);

        return 0;

}

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

/*

 * hfs_ext_compare()

 *

 * Description:

 *   This is the comparison function used for the extents B-tree.  In

 *   comparing extent B-tree entries, the file id is the most

 *   significant field (compared as unsigned ints); the fork type is

 *   the second most significant field (compared as unsigned chars);

 *   and the allocation block number field is the least significant

 *   (compared as unsigned ints).

 * Input Variable(s):

 *   struct hfs_ext_key *key1: pointer to the first key to compare

 *   struct hfs_ext_key *key2: pointer to the second key to compare

 * Output Variable(s):

 *   NONE

 * Returns:

 *   int: negative if key1<key2, positive if key1>key2, and 0 if key1==key2

 * Preconditions:

 *   key1 and key2 point to "valid" (struct hfs_ext_key)s.

 * Postconditions:

 *   This function has no side-effects */

int hfs_ext_compare(const struct hfs_ext_key *key1,

                    const struct hfs_ext_key *key2)

{

        unsigned int tmp;

        int retval;

        tmp = hfs_get_hl(key1->FNum) - hfs_get_hl(key2->FNum);

        if (tmp != 0) {

                retval = (int)tmp;

        } else {

                tmp = (unsigned char)key1->FkType - (unsigned char)key2->FkType;