Subversion Repositories test_project

/*

 *  linux/fs/ufs/balloc.c

 *

 * Copyright (C) 1998

 * Daniel Pirkl <daniel.pirkl@email.cz>

 * Charles University, Faculty of Mathematics and Physics

 *

 * UFS2 write support Evgeniy Dushistov <dushistov@mail.ru>, 2007

 */

#include <linux/fs.h>

#include <linux/ufs_fs.h>

#include <linux/stat.h>

#include <linux/time.h>

#include <linux/string.h>

#include <linux/quotaops.h>

#include <linux/buffer_head.h>

#include <linux/capability.h>

#include <linux/bitops.h>

#include <asm/byteorder.h>

#include "ufs.h"

#include "swab.h"

#include "util.h"

#define INVBLOCK ((u64)-1L)

static u64 ufs_add_fragments(struct inode *, u64, unsigned, unsigned, int *);

static u64 ufs_alloc_fragments(struct inode *, unsigned, u64, unsigned, int *);

static u64 ufs_alloccg_block(struct inode *, struct ufs_cg_private_info *, u64, int *);

static u64 ufs_bitmap_search (struct super_block *, struct ufs_cg_private_info *, u64, unsigned);

static unsigned char ufs_fragtable_8fpb[], ufs_fragtable_other[];

static void ufs_clusteracct(struct super_block *, struct ufs_cg_private_info *, unsigned, int);

/*

 * Free 'count' fragments from fragment number 'fragment'

 */

void ufs_free_fragments(struct inode *inode, u64 fragment, unsigned count)

{

        struct super_block * sb;

        struct ufs_sb_private_info * uspi;

        struct ufs_super_block_first * usb1;

        struct ufs_cg_private_info * ucpi;

        struct ufs_cylinder_group * ucg;

        unsigned cgno, bit, end_bit, bbase, blkmap, i;

        u64 blkno;

        sb = inode->i_sb;

        uspi = UFS_SB(sb)->s_uspi;

        usb1 = ubh_get_usb_first(uspi);

        UFSD("ENTER, fragment %llu, count %u\n",

             (unsigned long long)fragment, count);

        if (ufs_fragnum(fragment) + count > uspi->s_fpg)

                ufs_error (sb, "ufs_free_fragments", "internal error");

        lock_super(sb);

        cgno = ufs_dtog(uspi, fragment);

        bit = ufs_dtogd(uspi, fragment);

        if (cgno >= uspi->s_ncg) {

                ufs_panic (sb, "ufs_free_fragments", "freeing blocks are outside device");

                goto failed;

        }

        ucpi = ufs_load_cylinder (sb, cgno);

        if (!ucpi)

                goto failed;

        ucg = ubh_get_ucg (UCPI_UBH(ucpi));

        if (!ufs_cg_chkmagic(sb, ucg)) {

                ufs_panic (sb, "ufs_free_fragments", "internal error, bad magic number on cg %u", cgno);

                goto failed;

        }

        end_bit = bit + count;

        bbase = ufs_blknum (bit);

        blkmap = ubh_blkmap (UCPI_UBH(ucpi), ucpi->c_freeoff, bbase);

        ufs_fragacct (sb, blkmap, ucg->cg_frsum, -1);

        for (i = bit; i < end_bit; i++) {

                if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, i))

                        ubh_setbit (UCPI_UBH(ucpi), ucpi->c_freeoff, i);

                else

                        ufs_error (sb, "ufs_free_fragments",

                                   "bit already cleared for fragment %u", i);

        }

        DQUOT_FREE_BLOCK (inode, count);

        fs32_add(sb, &ucg->cg_cs.cs_nffree, count);

        uspi->cs_total.cs_nffree += count;

        fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);

        blkmap = ubh_blkmap (UCPI_UBH(ucpi), ucpi->c_freeoff, bbase);

        ufs_fragacct(sb, blkmap, ucg->cg_frsum, 1);

        /*

         * Trying to reassemble free fragments into block

         */

        blkno = ufs_fragstoblks (bbase);

        if (ubh_isblockset(UCPI_UBH(ucpi), ucpi->c_freeoff, blkno)) {

                fs32_sub(sb, &ucg->cg_cs.cs_nffree, uspi->s_fpb);

                uspi->cs_total.cs_nffree -= uspi->s_fpb;

                fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, uspi->s_fpb);

                if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)

                        ufs_clusteracct (sb, ucpi, blkno, 1);

                fs32_add(sb, &ucg->cg_cs.cs_nbfree, 1);

                uspi->cs_total.cs_nbfree++;

                fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nbfree, 1);

                if (uspi->fs_magic != UFS2_MAGIC) {

                        unsigned cylno = ufs_cbtocylno (bbase);

                        fs16_add(sb, &ubh_cg_blks(ucpi, cylno,

                                                  ufs_cbtorpos(bbase)), 1);

                        fs32_add(sb, &ubh_cg_blktot(ucpi, cylno), 1);

                }

        }

        ubh_mark_buffer_dirty (USPI_UBH(uspi));

        ubh_mark_buffer_dirty (UCPI_UBH(ucpi));

        if (sb->s_flags & MS_SYNCHRONOUS) {

                ubh_ll_rw_block(SWRITE, UCPI_UBH(ucpi));

                ubh_wait_on_buffer (UCPI_UBH(ucpi));

        }

        sb->s_dirt = 1;

        unlock_super (sb);

        UFSD("EXIT\n");

        return;

failed:

        unlock_super (sb);

        UFSD("EXIT (FAILED)\n");

        return;

}

/*

 * Free 'count' fragments from fragment number 'fragment' (free whole blocks)

 */

void ufs_free_blocks(struct inode *inode, u64 fragment, unsigned count)

{

        struct super_block * sb;

        struct ufs_sb_private_info * uspi;

        struct ufs_super_block_first * usb1;

        struct ufs_cg_private_info * ucpi;

        struct ufs_cylinder_group * ucg;

        unsigned overflow, cgno, bit, end_bit, i;

        u64 blkno;

        sb = inode->i_sb;

        uspi = UFS_SB(sb)->s_uspi;

        usb1 = ubh_get_usb_first(uspi);

        UFSD("ENTER, fragment %llu, count %u\n",

             (unsigned long long)fragment, count);

        if ((fragment & uspi->s_fpbmask) || (count & uspi->s_fpbmask)) {

                ufs_error (sb, "ufs_free_blocks", "internal error, "

                           "fragment %llu, count %u\n",

                           (unsigned long long)fragment, count);

                goto failed;

        }

        lock_super(sb);

do_more:

        overflow = 0;

        cgno = ufs_dtog(uspi, fragment);

        bit = ufs_dtogd(uspi, fragment);

        if (cgno >= uspi->s_ncg) {

                ufs_panic (sb, "ufs_free_blocks", "freeing blocks are outside device");

                goto failed_unlock;

        }

        end_bit = bit + count;

        if (end_bit > uspi->s_fpg) {

                overflow = bit + count - uspi->s_fpg;

                count -= overflow;

                end_bit -= overflow;

        }

        ucpi = ufs_load_cylinder (sb, cgno);

        if (!ucpi)

                goto failed_unlock;

        ucg = ubh_get_ucg (UCPI_UBH(ucpi));

        if (!ufs_cg_chkmagic(sb, ucg)) {

                ufs_panic (sb, "ufs_free_blocks", "internal error, bad magic number on cg %u", cgno);

                goto failed_unlock;

        }

        for (i = bit; i < end_bit; i += uspi->s_fpb) {

                blkno = ufs_fragstoblks(i);

                if (ubh_isblockset(UCPI_UBH(ucpi), ucpi->c_freeoff, blkno)) {

                        ufs_error(sb, "ufs_free_blocks", "freeing free fragment");

                }

                ubh_setblock(UCPI_UBH(ucpi), ucpi->c_freeoff, blkno);

                if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)

                        ufs_clusteracct (sb, ucpi, blkno, 1);

                DQUOT_FREE_BLOCK(inode, uspi->s_fpb);

                fs32_add(sb, &ucg->cg_cs.cs_nbfree, 1);

                uspi->cs_total.cs_nbfree++;

                fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nbfree, 1);

                if (uspi->fs_magic != UFS2_MAGIC) {

                        unsigned cylno = ufs_cbtocylno(i);

                        fs16_add(sb, &ubh_cg_blks(ucpi, cylno,

                                                  ufs_cbtorpos(i)), 1);

                        fs32_add(sb, &ubh_cg_blktot(ucpi, cylno), 1);

                }

        }

        ubh_mark_buffer_dirty (USPI_UBH(uspi));

        ubh_mark_buffer_dirty (UCPI_UBH(ucpi));

        if (sb->s_flags & MS_SYNCHRONOUS) {

                ubh_ll_rw_block(SWRITE, UCPI_UBH(ucpi));

                ubh_wait_on_buffer (UCPI_UBH(ucpi));

        }

        if (overflow) {

                fragment += count;

                count = overflow;

                goto do_more;

        }

        sb->s_dirt = 1;

        unlock_super (sb);

        UFSD("EXIT\n");

        return;

failed_unlock:

        unlock_super (sb);

failed:

        UFSD("EXIT (FAILED)\n");

        return;

}

/*

 * Modify inode page cache in such way:

 * have - blocks with b_blocknr equal to oldb...oldb+count-1

 * get - blocks with b_blocknr equal to newb...newb+count-1

 * also we suppose that oldb...oldb+count-1 blocks

 * situated at the end of file.

 *

 * We can come here from ufs_writepage or ufs_prepare_write,

 * locked_page is argument of these functions, so we already lock it.

 */

static void ufs_change_blocknr(struct inode *inode, sector_t beg,

                               unsigned int count, sector_t oldb,

                               sector_t newb, struct page *locked_page)

{

        const unsigned blks_per_page =

                1 << (PAGE_CACHE_SHIFT - inode->i_blkbits);

        const unsigned mask = blks_per_page - 1;

        struct address_space * const mapping = inode->i_mapping;

        pgoff_t index, cur_index, last_index;

        unsigned pos, j, lblock;

        sector_t end, i;

        struct page *page;

        struct buffer_head *head, *bh;

        UFSD("ENTER, ino %lu, count %u, oldb %llu, newb %llu\n",

              inode->i_ino, count,

             (unsigned long long)oldb, (unsigned long long)newb);

        BUG_ON(!locked_page);

        BUG_ON(!PageLocked(locked_page));

        cur_index = locked_page->index;

        end = count + beg;

        last_index = end >> (PAGE_CACHE_SHIFT - inode->i_blkbits);

        for (i = beg; i < end; i = (i | mask) + 1) {

                index = i >> (PAGE_CACHE_SHIFT - inode->i_blkbits);

                if (likely(cur_index != index)) {

                        page = ufs_get_locked_page(mapping, index);

                        if (!page)/* it was truncated */

                                continue;

                        if (IS_ERR(page)) {/* or EIO */

                                ufs_error(inode->i_sb, __FUNCTION__,

                                          "read of page %llu failed\n",

                                          (unsigned long long)index);

                                continue;

                        }

                } else

                        page = locked_page;

                head = page_buffers(page);

                bh = head;

                pos = i & mask;

                for (j = 0; j < pos; ++j)

                        bh = bh->b_this_page;

                if (unlikely(index == last_index))

                        lblock = end & mask;

                else

                        lblock = blks_per_page;

                do {

                        if (j >= lblock)

                                break;

                        pos = (i - beg) + j;

                        if (!buffer_mapped(bh))

                                        map_bh(bh, inode->i_sb, oldb + pos);

                        if (!buffer_uptodate(bh)) {

                                ll_rw_block(READ, 1, &bh);

                                wait_on_buffer(bh);

                                if (!buffer_uptodate(bh)) {

                                        ufs_error(inode->i_sb, __FUNCTION__,

                                                  "read of block failed\n");

                                        break;

                                }

                        }

                        UFSD(" change from %llu to %llu, pos %u\n",

                             (unsigned long long)pos + oldb,

                             (unsigned long long)pos + newb, pos);

                        bh->b_blocknr = newb + pos;

                        unmap_underlying_metadata(bh->b_bdev,

                                                  bh->b_blocknr);

                        mark_buffer_dirty(bh);

                        ++j;

                        bh = bh->b_this_page;

                } while (bh != head);

                if (likely(cur_index != index))

                        ufs_put_locked_page(page);

        }

        UFSD("EXIT\n");

}

static void ufs_clear_frags(struct inode *inode, sector_t beg, unsigned int n,

                            int sync)

{

        struct buffer_head *bh;

        sector_t end = beg + n;

        for (; beg < end; ++beg) {

                bh = sb_getblk(inode->i_sb, beg);

                lock_buffer(bh);

                memset(bh->b_data, 0, inode->i_sb->s_blocksize);

                set_buffer_uptodate(bh);

                mark_buffer_dirty(bh);

                unlock_buffer(bh);

                if (IS_SYNC(inode) || sync)

                        sync_dirty_buffer(bh);

                brelse(bh);

        }

}

u64 ufs_new_fragments(struct inode *inode, void *p, u64 fragment,

                           u64 goal, unsigned count, int *err,

                           struct page *locked_page)

{

        struct super_block * sb;

        struct ufs_sb_private_info * uspi;

        struct ufs_super_block_first * usb1;

        unsigned cgno, oldcount, newcount;

        u64 tmp, request, result;

        UFSD("ENTER, ino %lu, fragment %llu, goal %llu, count %u\n",

             inode->i_ino, (unsigned long long)fragment,

             (unsigned long long)goal, count);

        sb = inode->i_sb;

        uspi = UFS_SB(sb)->s_uspi;

        usb1 = ubh_get_usb_first(uspi);

        *err = -ENOSPC;

        lock_super (sb);

        tmp = ufs_data_ptr_to_cpu(sb, p);

        if (count + ufs_fragnum(fragment) > uspi->s_fpb) {

                ufs_warning(sb, "ufs_new_fragments", "internal warning"

                            " fragment %llu, count %u",

                            (unsigned long long)fragment, count);

                count = uspi->s_fpb - ufs_fragnum(fragment);

        }

        oldcount = ufs_fragnum (fragment);

        newcount = oldcount + count;

        /*

         * Somebody else has just allocated our fragments

         */

        if (oldcount) {

                if (!tmp) {

                        ufs_error(sb, "ufs_new_fragments", "internal error, "

                                  "fragment %llu, tmp %llu\n",

                                  (unsigned long long)fragment,

                                  (unsigned long long)tmp);

                        unlock_super(sb);

                        return INVBLOCK;

                }

                if (fragment < UFS_I(inode)->i_lastfrag) {

                        UFSD("EXIT (ALREADY ALLOCATED)\n");

                        unlock_super (sb);

                        return 0;

                }

        }

        else {

                if (tmp) {

                        UFSD("EXIT (ALREADY ALLOCATED)\n");

                        unlock_super(sb);

                        return 0;

                }

        }

        /*

         * There is not enough space for user on the device

         */

        if (!capable(CAP_SYS_RESOURCE) && ufs_freespace(uspi, UFS_MINFREE) <= 0) {

                unlock_super (sb);

                UFSD("EXIT (FAILED)\n");

                return 0;

        }

        if (goal >= uspi->s_size)

                goal = 0;

        if (goal == 0)

                cgno = ufs_inotocg (inode->i_ino);

        else

                cgno = ufs_dtog(uspi, goal);

        /*

         * allocate new fragment

         */

        if (oldcount == 0) {

                result = ufs_alloc_fragments (inode, cgno, goal, count, err);

                if (result) {

                        ufs_cpu_to_data_ptr(sb, p, result);

                        *err = 0;

                        UFS_I(inode)->i_lastfrag =

                                max_t(u32, UFS_I(inode)->i_lastfrag,

                                      fragment + count);

                        ufs_clear_frags(inode, result + oldcount,

                                        newcount - oldcount, locked_page != NULL);

                }

                unlock_super(sb);

                UFSD("EXIT, result %llu\n", (unsigned long long)result);

                return result;

        }

        /*

         * resize block

         */

        result = ufs_add_fragments (inode, tmp, oldcount, newcount, err);

        if (result) {

                *err = 0;

                UFS_I(inode)->i_lastfrag = max_t(u32, UFS_I(inode)->i_lastfrag, fragment + count);

                ufs_clear_frags(inode, result + oldcount, newcount - oldcount,

                                locked_page != NULL);

                unlock_super(sb);

                UFSD("EXIT, result %llu\n", (unsigned long long)result);

                return result;

        }

        /*

         * allocate new block and move data

         */

        switch (fs32_to_cpu(sb, usb1->fs_optim)) {

            case UFS_OPTSPACE:

                request = newcount;

                if (uspi->s_minfree < 5 || uspi->cs_total.cs_nffree

                    > uspi->s_dsize * uspi->s_minfree / (2 * 100))

                        break;

                usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);

                break;

            default:

                usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);

            case UFS_OPTTIME:

                request = uspi->s_fpb;

                if (uspi->cs_total.cs_nffree < uspi->s_dsize *

                    (uspi->s_minfree - 2) / 100)

                        break;

                usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);

                break;

        }

        result = ufs_alloc_fragments (inode, cgno, goal, request, err);

        if (result) {

                ufs_clear_frags(inode, result + oldcount, newcount - oldcount,

                                locked_page != NULL);

                ufs_change_blocknr(inode, fragment - oldcount, oldcount,

                                   uspi->s_sbbase + tmp,

                                   uspi->s_sbbase + result, locked_page);

                ufs_cpu_to_data_ptr(sb, p, result);

                *err = 0;

                UFS_I(inode)->i_lastfrag = max_t(u32, UFS_I(inode)->i_lastfrag, fragment + count);

                unlock_super(sb);

                if (newcount < request)

                        ufs_free_fragments (inode, result + newcount, request - newcount);

                ufs_free_fragments (inode, tmp, oldcount);

                UFSD("EXIT, result %llu\n", (unsigned long long)result);

                return result;

        }

        unlock_super(sb);

        UFSD("EXIT (FAILED)\n");

        return 0;

}

static u64 ufs_add_fragments(struct inode *inode, u64 fragment,

                             unsigned oldcount, unsigned newcount, int *err)

{

        struct super_block * sb;

        struct ufs_sb_private_info * uspi;

        struct ufs_super_block_first * usb1;

        struct ufs_cg_private_info * ucpi;

        struct ufs_cylinder_group * ucg;

        unsigned cgno, fragno, fragoff, count, fragsize, i;

        UFSD("ENTER, fragment %llu, oldcount %u, newcount %u\n",

             (unsigned long long)fragment, oldcount, newcount);

        sb = inode->i_sb;

        uspi = UFS_SB(sb)->s_uspi;

        usb1 = ubh_get_usb_first (uspi);

        count = newcount - oldcount;

        cgno = ufs_dtog(uspi, fragment);

        if (fs32_to_cpu(sb, UFS_SB(sb)->fs_cs(cgno).cs_nffree) < count)

                return 0;

        if ((ufs_fragnum (fragment) + newcount) > uspi->s_fpb)

                return 0;

        ucpi = ufs_load_cylinder (sb, cgno);

        if (!ucpi)

                return 0;

        ucg = ubh_get_ucg (UCPI_UBH(ucpi));

        if (!ufs_cg_chkmagic(sb, ucg)) {

                ufs_panic (sb, "ufs_add_fragments",

                        "internal error, bad magic number on cg %u", cgno);

                return 0;

        }

        fragno = ufs_dtogd(uspi, fragment);

        fragoff = ufs_fragnum (fragno);

        for (i = oldcount; i < newcount; i++)

                if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i))

                        return 0;

        /*

         * Block can be extended

         */

        ucg->cg_time = cpu_to_fs32(sb, get_seconds());

        for (i = newcount; i < (uspi->s_fpb - fragoff); i++)

                if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i))

                        break;

        fragsize = i - oldcount;

        if (!fs32_to_cpu(sb, ucg->cg_frsum[fragsize]))

                ufs_panic (sb, "ufs_add_fragments",

                        "internal error or corrupted bitmap on cg %u", cgno);

        fs32_sub(sb, &ucg->cg_frsum[fragsize], 1);

        if (fragsize != count)

                fs32_add(sb, &ucg->cg_frsum[fragsize - count], 1);

        for (i = oldcount; i < newcount; i++)

                ubh_clrbit (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i);

        if(DQUOT_ALLOC_BLOCK(inode, count)) {

                *err = -EDQUOT;

                return 0;

        }

        fs32_sub(sb, &ucg->cg_cs.cs_nffree, count);

        fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);

        uspi->cs_total.cs_nffree -= count;

        ubh_mark_buffer_dirty (USPI_UBH(uspi));

        ubh_mark_buffer_dirty (UCPI_UBH(ucpi));

        if (sb->s_flags & MS_SYNCHRONOUS) {

                ubh_ll_rw_block(SWRITE, UCPI_UBH(ucpi));

                ubh_wait_on_buffer (UCPI_UBH(ucpi));

        }

        sb->s_dirt = 1;

        UFSD("EXIT, fragment %llu\n", (unsigned long long)fragment);

        return fragment;

}

#define UFS_TEST_FREE_SPACE_CG \

        ucg = (struct ufs_cylinder_group *) UFS_SB(sb)->s_ucg[cgno]->b_data; \

        if (fs32_to_cpu(sb, ucg->cg_cs.cs_nbfree)) \

                goto cg_found; \

        for (k = count; k < uspi->s_fpb; k++) \

                if (fs32_to_cpu(sb, ucg->cg_frsum[k])) \

                        goto cg_found;

static u64 ufs_alloc_fragments(struct inode *inode, unsigned cgno,

                               u64 goal, unsigned count, int *err)

{

        struct super_block * sb;

        struct ufs_sb_private_info * uspi;

        struct ufs_super_block_first * usb1;

        struct ufs_cg_private_info * ucpi;

        struct ufs_cylinder_group * ucg;

        unsigned oldcg, i, j, k, allocsize;

        u64 result;

        UFSD("ENTER, ino %lu, cgno %u, goal %llu, count %u\n",

             inode->i_ino, cgno, (unsigned long long)goal, count);

        sb = inode->i_sb;

        uspi = UFS_SB(sb)->s_uspi;

        usb1 = ubh_get_usb_first(uspi);

        oldcg = cgno;

        /*

         * 1. searching on preferred cylinder group

         */

        UFS_TEST_FREE_SPACE_CG

        /*

         * 2. quadratic rehash

         */