URL https://opencores.org/ocsvn/or1k/or1k/trunk

Subversion Repositories or1k

[/] [or1k/] [trunk/] [linux/] [linux-2.4/] [fs/] [hfsplus/] [extents.c] - Blame information for rev 1765

Details | Compare with Previous | View Log


/*
 *  linux/fs/hfsplus/extents.c
 *
 * Copyright (C) 2001
 * Brad Boyer (flar@allandria.com)
 * (C) 2003 Ardis Technologies <roman@ardistech.com>
 *
 * Handling of Extents both in catalog and extents overflow trees
 */
 
#include <linux/errno.h>
#include <linux/fs.h>
#include <linux/pagemap.h>
#include <linux/version.h>
#if LINUX_VERSION_CODE >= KERNEL_VERSION(2,5,0)
#include <linux/buffer_head.h>
#endif
 
#include "hfsplus_fs.h"
#include "hfsplus_raw.h"
 
/* Compare two extents keys, returns 0 on same, pos/neg for difference */
int hfsplus_cmp_ext_key(hfsplus_btree_key *k1, hfsplus_btree_key *k2)
{
        u32 k1id, k2id;
        u32 k1s, k2s;
 
        k1id = k1->ext.cnid;
        k2id = k2->ext.cnid;
        if (k1id != k2id)
                return be32_to_cpu(k1id) < be32_to_cpu(k2id) ? -1 : 1;
 
        if (k1->ext.fork_type != k2->ext.fork_type)
                return k1->ext.fork_type < k2->ext.fork_type ? -1 : 1;
 
        k1s = k1->ext.start_block;
        k2s = k2->ext.start_block;
        if (k1s == k2s)
                return 0;
        return be32_to_cpu(k1s) < be32_to_cpu(k2s) ? -1 : 1;
}
 
void hfsplus_fill_ext_key(hfsplus_btree_key *key, u32 cnid,
                          u32 block, u8 type)
{
        key->key_len = cpu_to_be16(HFSPLUS_EXT_KEYLEN - 2);
        key->ext.cnid = cpu_to_be32(cnid);
        key->ext.start_block = cpu_to_be32(block);
        key->ext.fork_type = type;
        key->ext.pad = 0;
}
 
static u32 hfsplus_find_extent(hfsplus_extent *extent, u32 off)
{
        int i;
        u32 count;
 
        for (i = 0; i < 8; extent++, i++) {
                count = be32_to_cpu(extent->block_count);
                if (off < count)
                        return be32_to_cpu(extent->start_block) + off;
                off -= count;
        }
        /* panic? */
        return 0;
}
 
static int hfsplus_find_extentry(struct hfsplus_find_data *fd,
                                 hfsplus_extent *extent)
{
        int res;
 
        fd->key->ext.cnid = 0;
        res = hfsplus_btree_find(fd);
        if (res && res != -ENOENT)
                return res;
        if (fd->key->ext.cnid != fd->search_key->ext.cnid ||
            fd->key->ext.fork_type != fd->search_key->ext.fork_type)
                return -ENOENT;
        //if (fd->entrylength != ext_key_size)...
        hfsplus_bnode_readbytes(fd->bnode, extent, fd->entryoffset, fd->entrylength);
        return 0;
}
 
/* Get a block at iblock for inode, possibly allocating if create */
int hfsplus_get_block(struct inode *inode, sector_t iblock,
                      struct buffer_head *bh_result, int create)
{
        struct super_block *sb;
        hfsplus_extent_rec ext_entry;
        struct hfsplus_find_data fd;
        int err = -EIO;
        u32 ablock, dblock = 0;
 
        sb = inode->i_sb;
 
        /* Convert inode block to disk allocation block */
        ablock = iblock;
 
        if (ablock >= HFSPLUS_I(inode).total_blocks) {
                if (ablock > HFSPLUS_I(inode).total_blocks || !create)
                        return -EIO;
                if (ablock >= HFSPLUS_I(inode).alloc_blocks) {
                        err = hfsplus_extend_file(inode);
                        if (err)
                                return err;
                }
                HFSPLUS_I(inode).mmu_private += sb->s_blocksize;
                HFSPLUS_I(inode).total_blocks++;
                mark_inode_dirty(inode);
        } else
                create = 0;
 
        if (ablock < HFSPLUS_I(inode).extent_blocks) {
                dblock = hfsplus_find_extent(HFSPLUS_I(inode).extents, ablock);
        } else {
                hfsplus_find_init(HFSPLUS_SB(sb).ext_tree, &fd);
                hfsplus_fill_ext_key(fd.search_key, inode->i_ino, ablock, HFSPLUS_IS_RSRC(inode) ?
                                     HFSPLUS_TYPE_RSRC : HFSPLUS_TYPE_DATA);
                err = hfsplus_find_extentry(&fd, ext_entry);
                if (!err)
                        dblock = hfsplus_find_extent(ext_entry, ablock -
                                                    be32_to_cpu(fd.key->ext.start_block));
                hfsplus_find_exit(&fd);
                if (err)
                        return err;
        }
 
        if (!dblock)
                return -EIO;
        dprint(DBG_EXTENT, "get_block(%lu): %lu - %u\n", inode->i_ino, iblock, dblock);
 
        map_bh(bh_result, sb, dblock + HFSPLUS_SB(sb).blockoffset);
        if (create)
                set_buffer_new(bh_result);
        return 0;
}
 
static void hfsplus_dump_extent(hfsplus_extent *extent)
{
        int i;
 
        dprint(DBG_EXTENT, "   ");
        for (i = 0; i < 8; i++)
                dprint(DBG_EXTENT, " %u:%u", be32_to_cpu(extent[i].start_block),
                                 be32_to_cpu(extent[i].block_count));
        dprint(DBG_EXTENT, "\n");
}
 
static int hfsplus_add_extent(hfsplus_extent *extent, u32 offset,
                              u32 alloc_block, u32 block_count)
{
        u32 count, start;
        int i;
 
        hfsplus_dump_extent(extent);
        for (i = 0; i < 8; extent++, i++) {
                count = be32_to_cpu(extent->block_count);
                if (offset == count) {
                        start = be32_to_cpu(extent->start_block);
                        if (alloc_block != start + count) {
                                if (++i >= 8)
                                        return -ENOSPC;
                                extent++;
                                extent->start_block = cpu_to_be32(alloc_block);
                        } else
                                block_count += count;
                        extent->block_count = cpu_to_be32(block_count);
                        return 0;
                } else if (offset < count)
                        break;
                offset -= count;
        }
        /* panic? */
        return -EIO;
}
 
void hfsplus_free_blocks(struct super_block *sb, u32 start, u32 count)
{
        struct inode *anode;
        struct buffer_head *bh;
        int size, blk, off;
        unsigned long *data, word, m;
 
        anode = HFSPLUS_SB(sb).alloc_file;
        size = sb->s_blocksize / sizeof(unsigned long);
        blk = (start >> sb->s_blocksize_bits) / 8;
        off = (start & (sb->s_blocksize * 8 - 1)) / 8 / sizeof(unsigned long);
        m = 1 << (~start & (8 * sizeof(unsigned long) - 1));
 
        HFSPLUS_SB(sb).free_blocks += count;
        sb->s_dirt = 1;
 
        while (count) {
                bh = hfsplus_getblk(anode, blk);
                data = (unsigned long *)bh->b_data;
                do {
                        word = ~be32_to_cpu(data[off]);
                        for (;;) {
                                if (word & m)
                                        printk("freeing free block %u\n", start);
                                word |= m;
                                start++;
                                if (!--count) {
                                        data[off] = cpu_to_be32(~word);
                                        goto done;
                                }
                                if (!(m >>= 1))
                                        break;
                        }
                        data[off] = cpu_to_be32(~word);
                        m = 1UL << (8 * sizeof(unsigned long) - 1);
                } while (++off < size);
        done:
                mark_buffer_dirty_inode(bh, anode);
                brelse(bh);
                if (++blk >= anode->i_blocks)
                        break;
                off = 0;
        }
        if (count)
                printk("%u block left to free\n", count);
}
 
int hfsplus_free_extents(struct super_block *sb, hfsplus_extent *extent,
                         u32 offset, u32 block_nr)
{
        u32 count, start;
        int i;
 
        hfsplus_dump_extent(extent);
        for (i = 0; i < 8; extent++, i++) {
                count = be32_to_cpu(extent->block_count);
                if (offset == count)
                        goto found;
                else if (offset < count)
                        break;
                offset -= count;
        }
        /* panic? */
        return -EIO;
found:
        for (;;) {
                start = be32_to_cpu(extent->start_block);
                if (count <= block_nr) {
                        hfsplus_free_blocks(sb, start, count);
                        extent->block_count = 0;
                        extent->start_block = 0;
                        block_nr -= count;
                } else {
                        count -= block_nr;
                        hfsplus_free_blocks(sb, start + count, block_nr);
                        extent->block_count = cpu_to_be32(count);
                        block_nr = 0;
                }
                if (!block_nr || !i)
                        return 0;
                i--;
                extent--;
                count = be32_to_cpu(extent->block_count);
        }
}
 
int hfsplus_free_fork(struct super_block *sb, u32 cnid, hfsplus_fork_raw *fork, int type)
{
        struct hfsplus_find_data fd;
        hfsplus_extent_rec ext_entry;
        u32 total_blocks, blocks, start;
        int res, i;
 
        total_blocks = be32_to_cpu(fork->total_blocks);
        if (!total_blocks)
                return 0;
 
        blocks = 0;
        for (i = 0; i < 8; i++)
                blocks += be32_to_cpu(fork->extents[i].block_count);
 
        res = hfsplus_free_extents(sb, fork->extents, blocks, blocks);
        if (res)
                return res;
        if (total_blocks == blocks)
                return 0;
 
        hfsplus_find_init(HFSPLUS_SB(sb).ext_tree, &fd);
        do {
                hfsplus_fill_ext_key(fd.search_key, cnid,
                                     total_blocks, type);
                res = hfsplus_find_extentry(&fd, ext_entry);
                if (res)
                        break;
                start = be32_to_cpu(fd.key->ext.start_block);
                hfsplus_free_extents(sb, ext_entry,
                                     total_blocks - start,
                                     total_blocks);
                hfsplus_bnode_remove_rec(&fd);
                total_blocks = start;
        } while (total_blocks > blocks);
        hfsplus_find_exit(&fd);
 
        return res;
}
 
int hfsplus_extend_file(struct inode *inode)
{
        struct super_block *sb = inode->i_sb;
        struct inode *anode = HFSPLUS_SB(sb).alloc_file;
        struct hfsplus_find_data fd;
        hfsplus_extent_rec ext_entry;
        struct buffer_head *bh;
        u32 blk, blk1, ablock, block_count;
        unsigned long *data, word, m;
        int res, size, off, i;
 
        if (anode->i_size * 8 < HFSPLUS_SB(sb).total_blocks - HFSPLUS_SB(sb).free_blocks + 8) {
                // extend alloc file
                BUG();
        }
        blk = blk1 = (HFSPLUS_SB(sb).next_alloc >> sb->s_blocksize_bits) / 8;
        off = (HFSPLUS_SB(sb).next_alloc & (sb->s_blocksize * 8 - 1)) / sizeof(unsigned long) / 8;
 
        for (;;) {
                // ignore first off for now...
                off = 0;
                bh = hfsplus_getblk(anode, blk);
                if (blk == anode->i_blocks - 1)
                        size = (HFSPLUS_SB(sb).total_blocks &
                                (sb->s_blocksize * 8 - 1)) /
                                8 / sizeof(unsigned long);
                else
                        size = sb->s_blocksize / sizeof(unsigned long);
                data = (unsigned long *)bh->b_data;
                do {
                        word = be32_to_cpu(data[off]);
                        if (!~word)
                                continue;
                        m = 1UL << (sizeof(unsigned long) * 8 - 1);
                        for (i = 0; m; i++, m >>= 1) {
                                if (word & m)
                                        continue;
                                ablock = (blk << sb->s_blocksize_bits) * 8 +
                                        off * sizeof(unsigned long) * 8 + i;
                                block_count = 1;
                                word |= m;
#if 0
                                while ((m >>= 1) && !(word & m)) {
                                        block_count++;
                                        word |= m;
                                }
#endif
                                data[off] = cpu_to_be32(word);
                                mark_buffer_dirty_inode(bh, anode);
                                brelse(bh);
                                goto found;
                        }
                } while (++off < size);
                brelse(bh);
                if (++blk >= anode->i_blocks)
                        blk = 0;
                if (blk == blk1)
                        return -ENOSPC;
        }
 
found:
        dprint(DBG_EXTENT, "extend %lu: %u,%u\n", inode->i_ino, ablock, block_count);
        if (HFSPLUS_I(inode).alloc_blocks <= HFSPLUS_I(inode).extent_blocks) {
                if (!HFSPLUS_I(inode).extent_blocks) {
                        dprint(DBG_EXTENT, "first extents\n");
                        /* no extents yet */
                        HFSPLUS_I(inode).extents[0].start_block = cpu_to_be32(ablock);
                        HFSPLUS_I(inode).extents[0].block_count = cpu_to_be32(block_count);
                        res = 0;
                } else
                        /* try to append to extents in inode */
                        res = hfsplus_add_extent(HFSPLUS_I(inode).extents,
                                                 HFSPLUS_I(inode).alloc_blocks,
                                                 ablock, block_count);
                if (!res) {
                        hfsplus_dump_extent(HFSPLUS_I(inode).extents);
                        HFSPLUS_I(inode).extent_blocks += block_count;
                } else if (res == -ENOSPC) {
                        /* create new extent, so find place to insert it */
                        hfsplus_find_init(HFSPLUS_SB(sb).ext_tree, &fd);
                        hfsplus_fill_ext_key(fd.search_key, inode->i_ino,
                                             HFSPLUS_I(inode).alloc_blocks,
                                             HFSPLUS_IS_RSRC(inode) ?
                                             HFSPLUS_TYPE_RSRC : HFSPLUS_TYPE_DATA);
                        res = hfsplus_find_extentry(&fd, ext_entry);
                        if (res && res != -ENOENT) {
                                hfsplus_find_exit(&fd);
                                goto out;
                        }
                        goto insert_extent;
                }
        } else {
                hfsplus_find_init(HFSPLUS_SB(sb).ext_tree, &fd);
                hfsplus_fill_ext_key(fd.search_key, inode->i_ino,
                                     HFSPLUS_I(inode).alloc_blocks,
                                     HFSPLUS_IS_RSRC(inode) ?
                                     HFSPLUS_TYPE_RSRC : HFSPLUS_TYPE_DATA);
                res = hfsplus_find_extentry(&fd, ext_entry);
                if (res) {
                        hfsplus_find_exit(&fd);
                        goto out;
                }
 
                res = hfsplus_add_extent(ext_entry, HFSPLUS_I(inode).alloc_blocks -
                                         be32_to_cpu(fd.key->ext.start_block),
                                         ablock, block_count);
                if (!res) {
                        hfsplus_dump_extent(ext_entry);
                        hfsplus_bnode_writebytes(fd.bnode, &ext_entry,
                                                 fd.entryoffset,
                                                 sizeof(ext_entry));
                } else if (res == -ENOSPC)
                        goto insert_extent;
                hfsplus_find_exit(&fd);
        }
out:
        if (!res) {
                HFSPLUS_I(inode).alloc_blocks += block_count;
                mark_inode_dirty(inode);
                HFSPLUS_SB(sb).free_blocks -= block_count;
                sb->s_dirt = 1;
        }
        return res;
 
insert_extent:
        dprint(DBG_EXTENT, "insert new extent\n");
        memset(ext_entry, 0, sizeof(ext_entry));
        ext_entry[0].start_block = cpu_to_be32(ablock);
        ext_entry[0].block_count = cpu_to_be32(block_count);
 
        hfsplus_bnode_insert_rec(&fd, ext_entry, sizeof(ext_entry));
        hfsplus_find_exit(&fd);
        res = 0;
        goto out;
}
 
void hfsplus_truncate(struct inode *inode)
{
        struct super_block *sb = inode->i_sb;
        struct hfsplus_find_data fd;
        hfsplus_extent_rec ext_entry;
        u32 blk_cnt, start;
        int res;
 
        dprint(DBG_INODE, "truncate: %lu, %Lu -> %Lu\n", inode->i_ino,
               (long long)HFSPLUS_I(inode).mmu_private, inode->i_size);
        if (inode->i_size == HFSPLUS_I(inode).mmu_private)
                return;
        if (inode->i_size > HFSPLUS_I(inode).mmu_private) {
                struct address_space *mapping = inode->i_mapping;
                struct page *page;
                u32 size = inode->i_size - 1;
                int res;
 
                page = grab_cache_page(mapping, size >> PAGE_CACHE_SHIFT);
                if (!page)
                        return;
                size &= PAGE_CACHE_SIZE - 1;
                size++;
                res = mapping->a_ops->prepare_write(NULL, page, size, size);
                if (!res)
                        res = mapping->a_ops->commit_write(NULL, page, size, size);
                if (res)
                        inode->i_size = HFSPLUS_I(inode).mmu_private;
                unlock_page(page);
                page_cache_release(page);
                mark_inode_dirty(inode);
                return;
        }
        blk_cnt = (inode->i_size + sb->s_blocksize - 1) >> sb->s_blocksize_bits;
 
        while (1) {
                if (HFSPLUS_I(inode).alloc_blocks <= HFSPLUS_I(inode).extent_blocks) {
                        hfsplus_free_extents(sb, HFSPLUS_I(inode).extents,
                                             HFSPLUS_I(inode).alloc_blocks,
                                             HFSPLUS_I(inode).alloc_blocks - blk_cnt);
                        hfsplus_dump_extent(HFSPLUS_I(inode).extents);
                        HFSPLUS_I(inode).extent_blocks = blk_cnt;
                        break;
                }
                hfsplus_find_init(HFSPLUS_SB(sb).ext_tree, &fd);
                hfsplus_fill_ext_key(fd.search_key, inode->i_ino,
                                     HFSPLUS_I(inode).alloc_blocks,
                                     HFSPLUS_IS_RSRC(inode) ?
                                     HFSPLUS_TYPE_RSRC : HFSPLUS_TYPE_DATA);
                res = hfsplus_find_extentry(&fd, ext_entry);
                if (res) {
                        hfsplus_find_exit(&fd);
                        break;
                }
                start = be32_to_cpu(fd.key->ext.start_block);
                hfsplus_free_extents(sb, ext_entry,
                                     HFSPLUS_I(inode).alloc_blocks - start,
                                     HFSPLUS_I(inode).alloc_blocks - blk_cnt);
                hfsplus_dump_extent(ext_entry);
                if (blk_cnt > start) {
                        hfsplus_bnode_writebytes(fd.bnode, &ext_entry,
                                                 fd.entryoffset,
                                                 sizeof(ext_entry));
                        hfsplus_find_exit(&fd);
                        break;
                }
                HFSPLUS_I(inode).alloc_blocks = start;
                hfsplus_bnode_remove_rec(&fd);
                hfsplus_find_exit(&fd);
        }
        HFSPLUS_I(inode).mmu_private = inode->i_size;
        HFSPLUS_I(inode).alloc_blocks = HFSPLUS_I(inode).total_blocks = blk_cnt;
}

Browse

Tools

Subversion Repositories or1k

[/] [or1k/] [trunk/] [linux/] [linux-2.4/] [fs/] [hfsplus/] [extents.c] - Blame information for rev 1765

Line No.	Rev	Author	Line
1	1275	phoenix	`/*`
2			`* linux/fs/hfsplus/extents.c`
3			`*`
4			`* Copyright (C) 2001`
5			`* Brad Boyer (flar@allandria.com)`
6			`* (C) 2003 Ardis Technologies <roman@ardistech.com>`
7			`*`
8			`* Handling of Extents both in catalog and extents overflow trees`
9			`*/`
10
11			`#include <linux/errno.h>`
12			`#include <linux/fs.h>`
13			`#include <linux/pagemap.h>`
14			`#include <linux/version.h>`
15			`#if LINUX_VERSION_CODE >= KERNEL_VERSION(2,5,0)`
16			`#include <linux/buffer_head.h>`
17			`#endif`
18
19			`#include "hfsplus_fs.h"`
20			`#include "hfsplus_raw.h"`
21
22			`/* Compare two extents keys, returns 0 on same, pos/neg for difference */`
23			`int hfsplus_cmp_ext_key(hfsplus_btree_key k1, hfsplus_btree_key k2)`
24			`{`
25			`u32 k1id, k2id;`
26			`u32 k1s, k2s;`
27
28			`k1id = k1->ext.cnid;`
29			`k2id = k2->ext.cnid;`
30			`if (k1id != k2id)`
31			`return be32_to_cpu(k1id) < be32_to_cpu(k2id) ? -1 : 1;`
32
33			`if (k1->ext.fork_type != k2->ext.fork_type)`
34			`return k1->ext.fork_type < k2->ext.fork_type ? -1 : 1;`
35
36			`k1s = k1->ext.start_block;`
37			`k2s = k2->ext.start_block;`
38			`if (k1s == k2s)`
39			`return 0;`
40			`return be32_to_cpu(k1s) < be32_to_cpu(k2s) ? -1 : 1;`
41			`}`
42
43			`void hfsplus_fill_ext_key(hfsplus_btree_key *key, u32 cnid,`
44			`u32 block, u8 type)`
45			`{`
46			`key->key_len = cpu_to_be16(HFSPLUS_EXT_KEYLEN - 2);`
47			`key->ext.cnid = cpu_to_be32(cnid);`
48			`key->ext.start_block = cpu_to_be32(block);`
49			`key->ext.fork_type = type;`
50			`key->ext.pad = 0;`
51			`}`
52
53			`static u32 hfsplus_find_extent(hfsplus_extent *extent, u32 off)`
54			`{`
55			`int i;`
56			`u32 count;`
57
58			`for (i = 0; i < 8; extent++, i++) {`
59			`count = be32_to_cpu(extent->block_count);`
60			`if (off < count)`
61			`return be32_to_cpu(extent->start_block) + off;`
62			`off -= count;`
63			`}`
64			`/* panic? */`
65			`return 0;`
66			`}`
67
68			`static int hfsplus_find_extentry(struct hfsplus_find_data *fd,`
69			`hfsplus_extent *extent)`
70			`{`
71			`int res;`
72
73			`fd->key->ext.cnid = 0;`
74			`res = hfsplus_btree_find(fd);`
75			`if (res && res != -ENOENT)`
76			`return res;`
77			`if (fd->key->ext.cnid != fd->search_key->ext.cnid \|\|`
78			`fd->key->ext.fork_type != fd->search_key->ext.fork_type)`
79			`return -ENOENT;`
80			`//if (fd->entrylength != ext_key_size)...`
81			`hfsplus_bnode_readbytes(fd->bnode, extent, fd->entryoffset, fd->entrylength);`
82			`return 0;`
83			`}`
84
85			`/* Get a block at iblock for inode, possibly allocating if create */`
86			`int hfsplus_get_block(struct inode *inode, sector_t iblock,`
87			`struct buffer_head *bh_result, int create)`
88			`{`
89			`struct super_block *sb;`
90			`hfsplus_extent_rec ext_entry;`
91			`struct hfsplus_find_data fd;`
92			`int err = -EIO;`
93			`u32 ablock, dblock = 0;`
94
95			`sb = inode->i_sb;`
96
97			`/* Convert inode block to disk allocation block */`
98			`ablock = iblock;`
99
100			`if (ablock >= HFSPLUS_I(inode).total_blocks) {`
101			`if (ablock > HFSPLUS_I(inode).total_blocks \|\| !create)`
102			`return -EIO;`
103			`if (ablock >= HFSPLUS_I(inode).alloc_blocks) {`
104			`err = hfsplus_extend_file(inode);`
105			`if (err)`
106			`return err;`
107			`}`
108			`HFSPLUS_I(inode).mmu_private += sb->s_blocksize;`
109			`HFSPLUS_I(inode).total_blocks++;`
110			`mark_inode_dirty(inode);`
111			`} else`
112			`create = 0;`
113
114			`if (ablock < HFSPLUS_I(inode).extent_blocks) {`
115			`dblock = hfsplus_find_extent(HFSPLUS_I(inode).extents, ablock);`
116			`} else {`
117			`hfsplus_find_init(HFSPLUS_SB(sb).ext_tree, &fd);`
118			`hfsplus_fill_ext_key(fd.search_key, inode->i_ino, ablock, HFSPLUS_IS_RSRC(inode) ?`
119			`HFSPLUS_TYPE_RSRC : HFSPLUS_TYPE_DATA);`
120			`err = hfsplus_find_extentry(&fd, ext_entry);`
121			`if (!err)`
122			`dblock = hfsplus_find_extent(ext_entry, ablock -`
123			`be32_to_cpu(fd.key->ext.start_block));`
124			`hfsplus_find_exit(&fd);`
125			`if (err)`
126			`return err;`
127			`}`
128
129			`if (!dblock)`
130			`return -EIO;`
131			`dprint(DBG_EXTENT, "get_block(%lu): %lu - %u\n", inode->i_ino, iblock, dblock);`
132
133			`map_bh(bh_result, sb, dblock + HFSPLUS_SB(sb).blockoffset);`
134			`if (create)`
135			`set_buffer_new(bh_result);`
136			`return 0;`
137			`}`
138
139			`static void hfsplus_dump_extent(hfsplus_extent *extent)`
140			`{`
141			`int i;`
142
143			`dprint(DBG_EXTENT, " ");`
144			`for (i = 0; i < 8; i++)`
145			`dprint(DBG_EXTENT, " %u:%u", be32_to_cpu(extent[i].start_block),`
146			`be32_to_cpu(extent[i].block_count));`
147			`dprint(DBG_EXTENT, "\n");`
148			`}`
149
150			`static int hfsplus_add_extent(hfsplus_extent *extent, u32 offset,`
151			`u32 alloc_block, u32 block_count)`
152			`{`
153			`u32 count, start;`
154			`int i;`
155
156			`hfsplus_dump_extent(extent);`
157			`for (i = 0; i < 8; extent++, i++) {`
158			`count = be32_to_cpu(extent->block_count);`
159			`if (offset == count) {`
160			`start = be32_to_cpu(extent->start_block);`
161			`if (alloc_block != start + count) {`
162			`if (++i >= 8)`
163			`return -ENOSPC;`
164			`extent++;`
165			`extent->start_block = cpu_to_be32(alloc_block);`
166			`} else`
167			`block_count += count;`
168			`extent->block_count = cpu_to_be32(block_count);`
169			`return 0;`
170			`} else if (offset < count)`
171			`break;`
172			`offset -= count;`
173			`}`
174			`/* panic? */`
175			`return -EIO;`
176			`}`
177
178			`void hfsplus_free_blocks(struct super_block *sb, u32 start, u32 count)`
179			`{`
180			`struct inode *anode;`
181			`struct buffer_head *bh;`
182			`int size, blk, off;`
183			`unsigned long *data, word, m;`
184
185			`anode = HFSPLUS_SB(sb).alloc_file;`
186			`size = sb->s_blocksize / sizeof(unsigned long);`
187			`blk = (start >> sb->s_blocksize_bits) / 8;`
188			`off = (start & (sb->s_blocksize * 8 - 1)) / 8 / sizeof(unsigned long);`
189			`m = 1 << (~start & (8 * sizeof(unsigned long) - 1));`
190
191			`HFSPLUS_SB(sb).free_blocks += count;`
192			`sb->s_dirt = 1;`
193
194			`while (count) {`
195			`bh = hfsplus_getblk(anode, blk);`
196			`data = (unsigned long *)bh->b_data;`
197			`do {`
198			`word = ~be32_to_cpu(data[off]);`
199			`for (;;) {`
200			`if (word & m)`
201			`printk("freeing free block %u\n", start);`
202			`word \|= m;`
203			`start++;`
204			`if (!--count) {`
205			`data[off] = cpu_to_be32(~word);`
206			`goto done;`
207			`}`
208			`if (!(m >>= 1))`
209			`break;`
210			`}`
211			`data[off] = cpu_to_be32(~word);`
212			`m = 1UL << (8 * sizeof(unsigned long) - 1);`
213			`} while (++off < size);`
214			`done:`
215			`mark_buffer_dirty_inode(bh, anode);`
216			`brelse(bh);`
217			`if (++blk >= anode->i_blocks)`
218			`break;`
219			`off = 0;`
220			`}`
221			`if (count)`
222			`printk("%u block left to free\n", count);`
223			`}`
224
225			`int hfsplus_free_extents(struct super_block sb, hfsplus_extent extent,`
226			`u32 offset, u32 block_nr)`
227			`{`
228			`u32 count, start;`
229			`int i;`
230
231			`hfsplus_dump_extent(extent);`
232			`for (i = 0; i < 8; extent++, i++) {`
233			`count = be32_to_cpu(extent->block_count);`
234			`if (offset == count)`
235			`goto found;`
236			`else if (offset < count)`
237			`break;`
238			`offset -= count;`
239			`}`
240			`/* panic? */`
241			`return -EIO;`
242			`found:`
243			`for (;;) {`
244			`start = be32_to_cpu(extent->start_block);`
245			`if (count <= block_nr) {`
246			`hfsplus_free_blocks(sb, start, count);`
247			`extent->block_count = 0;`
248			`extent->start_block = 0;`
249			`block_nr -= count;`
250			`} else {`
251			`count -= block_nr;`
252			`hfsplus_free_blocks(sb, start + count, block_nr);`
253			`extent->block_count = cpu_to_be32(count);`
254			`block_nr = 0;`
255			`}`
256			`if (!block_nr \|\| !i)`
257			`return 0;`
258			`i--;`
259			`extent--;`
260			`count = be32_to_cpu(extent->block_count);`
261			`}`
262			`}`
263
264			`int hfsplus_free_fork(struct super_block sb, u32 cnid, hfsplus_fork_raw fork, int type)`
265			`{`
266			`struct hfsplus_find_data fd;`
267			`hfsplus_extent_rec ext_entry;`
268			`u32 total_blocks, blocks, start;`
269			`int res, i;`
270
271			`total_blocks = be32_to_cpu(fork->total_blocks);`
272			`if (!total_blocks)`
273			`return 0;`
274
275			`blocks = 0;`
276			`for (i = 0; i < 8; i++)`
277			`blocks += be32_to_cpu(fork->extents[i].block_count);`
278
279			`res = hfsplus_free_extents(sb, fork->extents, blocks, blocks);`
280			`if (res)`
281			`return res;`
282			`if (total_blocks == blocks)`
283			`return 0;`
284
285			`hfsplus_find_init(HFSPLUS_SB(sb).ext_tree, &fd);`
286			`do {`
287			`hfsplus_fill_ext_key(fd.search_key, cnid,`
288			`total_blocks, type);`
289			`res = hfsplus_find_extentry(&fd, ext_entry);`
290			`if (res)`
291			`break;`
292			`start = be32_to_cpu(fd.key->ext.start_block);`
293			`hfsplus_free_extents(sb, ext_entry,`
294			`total_blocks - start,`
295			`total_blocks);`
296			`hfsplus_bnode_remove_rec(&fd);`
297			`total_blocks = start;`
298			`} while (total_blocks > blocks);`
299			`hfsplus_find_exit(&fd);`
300
301			`return res;`
302			`}`
303
304			`int hfsplus_extend_file(struct inode *inode)`
305			`{`
306			`struct super_block *sb = inode->i_sb;`
307			`struct inode *anode = HFSPLUS_SB(sb).alloc_file;`
308			`struct hfsplus_find_data fd;`
309			`hfsplus_extent_rec ext_entry;`
310			`struct buffer_head *bh;`
311			`u32 blk, blk1, ablock, block_count;`
312			`unsigned long *data, word, m;`
313			`int res, size, off, i;`
314
315			`if (anode->i_size * 8 < HFSPLUS_SB(sb).total_blocks - HFSPLUS_SB(sb).free_blocks + 8) {`
316			`// extend alloc file`
317			`BUG();`
318			`}`
319			`blk = blk1 = (HFSPLUS_SB(sb).next_alloc >> sb->s_blocksize_bits) / 8;`
320			`off = (HFSPLUS_SB(sb).next_alloc & (sb->s_blocksize * 8 - 1)) / sizeof(unsigned long) / 8;`
321
322			`for (;;) {`
323			`// ignore first off for now...`
324			`off = 0;`
325			`bh = hfsplus_getblk(anode, blk);`
326			`if (blk == anode->i_blocks - 1)`
327			`size = (HFSPLUS_SB(sb).total_blocks &`
328			`(sb->s_blocksize * 8 - 1)) /`
329			`8 / sizeof(unsigned long);`
330			`else`
331			`size = sb->s_blocksize / sizeof(unsigned long);`
332			`data = (unsigned long *)bh->b_data;`
333			`do {`
334			`word = be32_to_cpu(data[off]);`
335			`if (!~word)`
336			`continue;`
337			`m = 1UL << (sizeof(unsigned long) * 8 - 1);`
338			`for (i = 0; m; i++, m >>= 1) {`
339			`if (word & m)`
340			`continue;`
341			`ablock = (blk << sb->s_blocksize_bits) * 8 +`
342			`off * sizeof(unsigned long) * 8 + i;`
343			`block_count = 1;`
344			`word \|= m;`
345			`#if 0`
346			`while ((m >>= 1) && !(word & m)) {`
347			`block_count++;`
348			`word \|= m;`
349			`}`
350			`#endif`
351			`data[off] = cpu_to_be32(word);`
352			`mark_buffer_dirty_inode(bh, anode);`
353			`brelse(bh);`
354			`goto found;`
355			`}`
356			`} while (++off < size);`
357			`brelse(bh);`
358			`if (++blk >= anode->i_blocks)`
359			`blk = 0;`
360			`if (blk == blk1)`
361			`return -ENOSPC;`
362			`}`
363
364			`found:`
365			`dprint(DBG_EXTENT, "extend %lu: %u,%u\n", inode->i_ino, ablock, block_count);`
366			`if (HFSPLUS_I(inode).alloc_blocks <= HFSPLUS_I(inode).extent_blocks) {`
367			`if (!HFSPLUS_I(inode).extent_blocks) {`
368			`dprint(DBG_EXTENT, "first extents\n");`
369			`/* no extents yet */`
370			`HFSPLUS_I(inode).extents[0].start_block = cpu_to_be32(ablock);`
371			`HFSPLUS_I(inode).extents[0].block_count = cpu_to_be32(block_count);`
372			`res = 0;`
373			`} else`
374			`/* try to append to extents in inode */`
375			`res = hfsplus_add_extent(HFSPLUS_I(inode).extents,`
376			`HFSPLUS_I(inode).alloc_blocks,`
377			`ablock, block_count);`
378			`if (!res) {`
379			`hfsplus_dump_extent(HFSPLUS_I(inode).extents);`
380			`HFSPLUS_I(inode).extent_blocks += block_count;`
381			`} else if (res == -ENOSPC) {`
382			`/* create new extent, so find place to insert it */`
383			`hfsplus_find_init(HFSPLUS_SB(sb).ext_tree, &fd);`
384			`hfsplus_fill_ext_key(fd.search_key, inode->i_ino,`
385			`HFSPLUS_I(inode).alloc_blocks,`
386			`HFSPLUS_IS_RSRC(inode) ?`
387			`HFSPLUS_TYPE_RSRC : HFSPLUS_TYPE_DATA);`
388			`res = hfsplus_find_extentry(&fd, ext_entry);`
389			`if (res && res != -ENOENT) {`
390			`hfsplus_find_exit(&fd);`
391			`goto out;`
392			`}`
393			`goto insert_extent;`
394			`}`
395			`} else {`
396			`hfsplus_find_init(HFSPLUS_SB(sb).ext_tree, &fd);`
397			`hfsplus_fill_ext_key(fd.search_key, inode->i_ino,`
398			`HFSPLUS_I(inode).alloc_blocks,`
399			`HFSPLUS_IS_RSRC(inode) ?`
400			`HFSPLUS_TYPE_RSRC : HFSPLUS_TYPE_DATA);`
401			`res = hfsplus_find_extentry(&fd, ext_entry);`
402			`if (res) {`
403			`hfsplus_find_exit(&fd);`
404			`goto out;`
405			`}`
406
407			`res = hfsplus_add_extent(ext_entry, HFSPLUS_I(inode).alloc_blocks -`
408			`be32_to_cpu(fd.key->ext.start_block),`
409			`ablock, block_count);`
410			`if (!res) {`
411			`hfsplus_dump_extent(ext_entry);`
412			`hfsplus_bnode_writebytes(fd.bnode, &ext_entry,`
413			`fd.entryoffset,`
414			`sizeof(ext_entry));`
415			`} else if (res == -ENOSPC)`
416			`goto insert_extent;`
417			`hfsplus_find_exit(&fd);`
418			`}`
419			`out:`
420			`if (!res) {`
421			`HFSPLUS_I(inode).alloc_blocks += block_count;`
422			`mark_inode_dirty(inode);`
423			`HFSPLUS_SB(sb).free_blocks -= block_count;`
424			`sb->s_dirt = 1;`
425			`}`
426			`return res;`
427
428			`insert_extent:`
429			`dprint(DBG_EXTENT, "insert new extent\n");`
430			`memset(ext_entry, 0, sizeof(ext_entry));`
431			`ext_entry[0].start_block = cpu_to_be32(ablock);`
432			`ext_entry[0].block_count = cpu_to_be32(block_count);`
433
434			`hfsplus_bnode_insert_rec(&fd, ext_entry, sizeof(ext_entry));`
435			`hfsplus_find_exit(&fd);`
436			`res = 0;`
437			`goto out;`
438			`}`
439
440			`void hfsplus_truncate(struct inode *inode)`
441			`{`
442			`struct super_block *sb = inode->i_sb;`
443			`struct hfsplus_find_data fd;`
444			`hfsplus_extent_rec ext_entry;`
445			`u32 blk_cnt, start;`
446			`int res;`
447
448			`dprint(DBG_INODE, "truncate: %lu, %Lu -> %Lu\n", inode->i_ino,`
449			`(long long)HFSPLUS_I(inode).mmu_private, inode->i_size);`
450			`if (inode->i_size == HFSPLUS_I(inode).mmu_private)`
451			`return;`
452			`if (inode->i_size > HFSPLUS_I(inode).mmu_private) {`
453			`struct address_space *mapping = inode->i_mapping;`
454			`struct page *page;`
455			`u32 size = inode->i_size - 1;`
456			`int res;`
457
458			`page = grab_cache_page(mapping, size >> PAGE_CACHE_SHIFT);`
459			`if (!page)`
460			`return;`
461			`size &= PAGE_CACHE_SIZE - 1;`
462			`size++;`
463			`res = mapping->a_ops->prepare_write(NULL, page, size, size);`
464			`if (!res)`
465			`res = mapping->a_ops->commit_write(NULL, page, size, size);`
466			`if (res)`
467			`inode->i_size = HFSPLUS_I(inode).mmu_private;`
468			`unlock_page(page);`
469			`page_cache_release(page);`
470			`mark_inode_dirty(inode);`
471			`return;`
472			`}`
473			`blk_cnt = (inode->i_size + sb->s_blocksize - 1) >> sb->s_blocksize_bits;`
474
475			`while (1) {`
476			`if (HFSPLUS_I(inode).alloc_blocks <= HFSPLUS_I(inode).extent_blocks) {`
477			`hfsplus_free_extents(sb, HFSPLUS_I(inode).extents,`
478			`HFSPLUS_I(inode).alloc_blocks,`
479			`HFSPLUS_I(inode).alloc_blocks - blk_cnt);`
480			`hfsplus_dump_extent(HFSPLUS_I(inode).extents);`
481			`HFSPLUS_I(inode).extent_blocks = blk_cnt;`
482			`break;`
483			`}`
484			`hfsplus_find_init(HFSPLUS_SB(sb).ext_tree, &fd);`
485			`hfsplus_fill_ext_key(fd.search_key, inode->i_ino,`
486			`HFSPLUS_I(inode).alloc_blocks,`
487			`HFSPLUS_IS_RSRC(inode) ?`
488			`HFSPLUS_TYPE_RSRC : HFSPLUS_TYPE_DATA);`
489			`res = hfsplus_find_extentry(&fd, ext_entry);`
490			`if (res) {`
491			`hfsplus_find_exit(&fd);`
492			`break;`
493			`}`
494			`start = be32_to_cpu(fd.key->ext.start_block);`
495			`hfsplus_free_extents(sb, ext_entry,`
496			`HFSPLUS_I(inode).alloc_blocks - start,`
497			`HFSPLUS_I(inode).alloc_blocks - blk_cnt);`
498			`hfsplus_dump_extent(ext_entry);`
499			`if (blk_cnt > start) {`
500			`hfsplus_bnode_writebytes(fd.bnode, &ext_entry,`
501			`fd.entryoffset,`
502			`sizeof(ext_entry));`
503			`hfsplus_find_exit(&fd);`
504			`break;`
505			`}`
506			`HFSPLUS_I(inode).alloc_blocks = start;`
507			`hfsplus_bnode_remove_rec(&fd);`
508			`hfsplus_find_exit(&fd);`
509			`}`
510			`HFSPLUS_I(inode).mmu_private = inode->i_size;`
511			`HFSPLUS_I(inode).alloc_blocks = HFSPLUS_I(inode).total_blocks = blk_cnt;`
512			`}`