/*
 * 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;
                if (tmp != 0) {
                        retval = (int)tmp;
                } else {
                        retval = (int)(hfs_get_hs(key1->FABN)
                                       - hfs_get_hs(key2->FABN));
                }
        }
        return retval;
}

/*
 * hfs_extent_adj()
 *
 * Given an hfs_fork shrink or grow the fork to hold the
 * forks logical size.
 */
void hfs_extent_adj(struct hfs_fork *fork)
{
        if (fork) {
                hfs_u32 blks, ablocks, ablksz;

                if (fork->lsize > HFS_FORK_MAX) {
                        fork->lsize = HFS_FORK_MAX;
                }

                blks = (fork->lsize+HFS_SECTOR_SIZE-1) >> HFS_SECTOR_SIZE_BITS;
                ablksz = fork->entry->mdb->alloc_blksz;
                ablocks = (blks + ablksz - 1) / ablksz;

                if (blks > fork->psize) {
                        grow_fork(fork, ablocks);
                        if (blks > fork->psize) {
                                fork->lsize =
                                        fork->psize >> HFS_SECTOR_SIZE_BITS;
                        }
                } else if (blks < fork->psize) {
                        shrink_fork(fork, ablocks);
                }
        }
}

/*
 * hfs_extent_map()
 *
 * Given an hfs_fork and a block number within the fork, return the
 * number of the corresponding physical block on disk, or zero on
 * error.
 */
int hfs_extent_map(struct hfs_fork *fork, int block, int create) 
{
        int ablksz, ablock, offset, tmp;
        struct hfs_extent *ext;

        if (!fork || !fork->entry || !fork->entry->mdb) {
                return 0;
        }

#if defined(DEBUG_EXTENTS) || defined(DEBUG_ALL)
        hfs_warn("hfs_extent_map: ablock %d of file %d, fork %d\n",
                 block, fork->entry->cnid, fork->fork);
#endif

        if (block < 0) {
                hfs_warn("hfs_extent_map: block < 0\n");
                return 0;
        }
        if (block > (HFS_FORK_MAX >> HFS_SECTOR_SIZE_BITS)) {
                hfs_warn("hfs_extent_map: block(0x%08x) > big; cnid=%d "
                         "fork=%d\n", block, fork->entry->cnid, fork->fork);
                return 0;
        }
        ablksz = fork->entry->mdb->alloc_blksz;
        offset = fork->entry->mdb->fs_start + (block % ablksz);
        ablock = block / ablksz;
        
        if (block >= fork->psize) {
                if (!create || (grow_fork(fork, ablock + 1) < 0))
                        return 0;
        }

#if defined(DEBUG_EXTENTS) || defined(DEBUG_ALL)
        hfs_warn("(lblock %d offset %d)\n", ablock, offset);
#endif

        if ((ext = find_ext(fork, ablock))) {
                dump_ext("trying new: ", ext);
                tmp = decode_extent(ext, ablock);
                relse_ext(ext);
                if (tmp >= 0) {
                        return tmp*ablksz + offset;
                }
        } 

        return 0;
}

/*
 * hfs_extent_out()
 *
 * Copy the first extent record from a (struct hfs_fork) to a (struct
 * raw_extent), record (normally the one in the catalog entry).
 */
void hfs_extent_out(const struct hfs_fork *fork, hfs_byte_t dummy[12])
{
        struct hfs_raw_extent *ext = (struct hfs_raw_extent *)dummy;

        if (fork && ext) {
                write_extent(ext, &fork->first);
                dump_ext("extent out: ", &fork->first);
        }
}

/*
 * hfs_extent_in()
 *
 * Copy an raw_extent to the 'first' and 'cache' fields of an hfs_fork.
 */
void hfs_extent_in(struct hfs_fork *fork, const hfs_byte_t dummy[12])
{
        const struct hfs_raw_extent *ext =
                (const struct hfs_raw_extent *)dummy;

        if (fork && ext) {
                read_extent(&fork->first, ext, 0);
                fork->cache = &fork->first;
                fork->first.count = 2;
                dump_ext("extent in: ", &fork->first);
        }
}

/* 
 * hfs_extent_free()
 *
 * Removes from memory all extents associated with 'fil'.
 */
void hfs_extent_free(struct hfs_fork *fork)
{
        if (fork) {
                set_cache(fork, &fork->first);

                if (fork->first.next) {
                        hfs_warn("hfs_extent_free: extents in use!\n");
                }
        }
}