Subversion Repositories test_project

/*

 * Copyright (C) Sistina Software, Inc.  1997-2003 All rights reserved.

 * Copyright (C) 2004-2006 Red Hat, Inc.  All rights reserved.

 *

 * This copyrighted material is made available to anyone wishing to use,

 * modify, copy, or redistribute it subject to the terms and conditions

 * of the GNU General Public License version 2.

 */

/*

 * Implements Extendible Hashing as described in:

 *   "Extendible Hashing" by Fagin, et al in

 *     __ACM Trans. on Database Systems__, Sept 1979.

 *

 *

 * Here's the layout of dirents which is essentially the same as that of ext2

 * within a single block. The field de_name_len is the number of bytes

 * actually required for the name (no null terminator). The field de_rec_len

 * is the number of bytes allocated to the dirent. The offset of the next

 * dirent in the block is (dirent + dirent->de_rec_len). When a dirent is

 * deleted, the preceding dirent inherits its allocated space, ie

 * prev->de_rec_len += deleted->de_rec_len. Since the next dirent is obtained

 * by adding de_rec_len to the current dirent, this essentially causes the

 * deleted dirent to get jumped over when iterating through all the dirents.

 *

 * When deleting the first dirent in a block, there is no previous dirent so

 * the field de_ino is set to zero to designate it as deleted. When allocating

 * a dirent, gfs2_dirent_alloc iterates through the dirents in a block. If the

 * first dirent has (de_ino == 0) and de_rec_len is large enough, this first

 * dirent is allocated. Otherwise it must go through all the 'used' dirents

 * searching for one in which the amount of total space minus the amount of

 * used space will provide enough space for the new dirent.

 *

 * There are two types of blocks in which dirents reside. In a stuffed dinode,

 * the dirents begin at offset sizeof(struct gfs2_dinode) from the beginning of

 * the block.  In leaves, they begin at offset sizeof(struct gfs2_leaf) from the

 * beginning of the leaf block. The dirents reside in leaves when

 *

 * dip->i_di.di_flags & GFS2_DIF_EXHASH is true

 *

 * Otherwise, the dirents are "linear", within a single stuffed dinode block.

 *

 * When the dirents are in leaves, the actual contents of the directory file are

 * used as an array of 64-bit block pointers pointing to the leaf blocks. The

 * dirents are NOT in the directory file itself. There can be more than one

 * block pointer in the array that points to the same leaf. In fact, when a

 * directory is first converted from linear to exhash, all of the pointers

 * point to the same leaf.

 *

 * When a leaf is completely full, the size of the hash table can be

 * doubled unless it is already at the maximum size which is hard coded into

 * GFS2_DIR_MAX_DEPTH. After that, leaves are chained together in a linked list,

 * but never before the maximum hash table size has been reached.

 */

#include <linux/slab.h>

#include <linux/spinlock.h>

#include <linux/buffer_head.h>

#include <linux/sort.h>

#include <linux/gfs2_ondisk.h>

#include <linux/crc32.h>

#include <linux/vmalloc.h>

#include <linux/lm_interface.h>

#include "gfs2.h"

#include "incore.h"

#include "dir.h"

#include "glock.h"

#include "inode.h"

#include "meta_io.h"

#include "quota.h"

#include "rgrp.h"

#include "trans.h"

#include "bmap.h"

#include "util.h"

#define IS_LEAF     1 /* Hashed (leaf) directory */

#define IS_DINODE   2 /* Linear (stuffed dinode block) directory */

#define gfs2_disk_hash2offset(h) (((u64)(h)) >> 1)

#define gfs2_dir_offset2hash(p) ((u32)(((u64)(p)) << 1))

typedef int (*leaf_call_t) (struct gfs2_inode *dip, u32 index, u32 len,

                            u64 leaf_no, void *data);

typedef int (*gfs2_dscan_t)(const struct gfs2_dirent *dent,

                            const struct qstr *name, void *opaque);

int gfs2_dir_get_new_buffer(struct gfs2_inode *ip, u64 block,

                            struct buffer_head **bhp)

{

        struct buffer_head *bh;

        bh = gfs2_meta_new(ip->i_gl, block);

        gfs2_trans_add_bh(ip->i_gl, bh, 1);

        gfs2_metatype_set(bh, GFS2_METATYPE_JD, GFS2_FORMAT_JD);

        gfs2_buffer_clear_tail(bh, sizeof(struct gfs2_meta_header));

        *bhp = bh;

        return 0;

}

static int gfs2_dir_get_existing_buffer(struct gfs2_inode *ip, u64 block,

                                        struct buffer_head **bhp)

{

        struct buffer_head *bh;

        int error;

        error = gfs2_meta_read(ip->i_gl, block, DIO_WAIT, &bh);

        if (error)

                return error;

        if (gfs2_metatype_check(GFS2_SB(&ip->i_inode), bh, GFS2_METATYPE_JD)) {

                brelse(bh);

                return -EIO;

        }

        *bhp = bh;

        return 0;

}

static int gfs2_dir_write_stuffed(struct gfs2_inode *ip, const char *buf,

                                  unsigned int offset, unsigned int size)

{

        struct buffer_head *dibh;

        int error;

        error = gfs2_meta_inode_buffer(ip, &dibh);

        if (error)

                return error;

        gfs2_trans_add_bh(ip->i_gl, dibh, 1);

        memcpy(dibh->b_data + offset + sizeof(struct gfs2_dinode), buf, size);

        if (ip->i_di.di_size < offset + size)

                ip->i_di.di_size = offset + size;

        ip->i_inode.i_mtime = ip->i_inode.i_ctime = CURRENT_TIME;

        gfs2_dinode_out(ip, dibh->b_data);

        brelse(dibh);

        return size;

}

/**

 * gfs2_dir_write_data - Write directory information to the inode

 * @ip: The GFS2 inode

 * @buf: The buffer containing information to be written

 * @offset: The file offset to start writing at

 * @size: The amount of data to write

 *

 * Returns: The number of bytes correctly written or error code

 */

static int gfs2_dir_write_data(struct gfs2_inode *ip, const char *buf,

                               u64 offset, unsigned int size)

{

        struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);

        struct buffer_head *dibh;

        u64 lblock, dblock;

        u32 extlen = 0;

        unsigned int o;

        int copied = 0;

        int error = 0;

        if (!size)

                return 0;

        if (gfs2_is_stuffed(ip) &&

            offset + size <= sdp->sd_sb.sb_bsize - sizeof(struct gfs2_dinode))

                return gfs2_dir_write_stuffed(ip, buf, (unsigned int)offset,

                                              size);

        if (gfs2_assert_warn(sdp, gfs2_is_jdata(ip)))

                return -EINVAL;

        if (gfs2_is_stuffed(ip)) {

                error = gfs2_unstuff_dinode(ip, NULL);

                if (error)

                        return error;

        }

        lblock = offset;

        o = do_div(lblock, sdp->sd_jbsize) + sizeof(struct gfs2_meta_header);

        while (copied < size) {

                unsigned int amount;

                struct buffer_head *bh;

                int new = 0;

                amount = size - copied;

                if (amount > sdp->sd_sb.sb_bsize - o)

                        amount = sdp->sd_sb.sb_bsize - o;

                if (!extlen) {

                        new = 1;

                        error = gfs2_extent_map(&ip->i_inode, lblock, &new,

                                                &dblock, &extlen);

                        if (error)

                                goto fail;

                        error = -EIO;

                        if (gfs2_assert_withdraw(sdp, dblock))

                                goto fail;

                }

                if (amount == sdp->sd_jbsize || new)

                        error = gfs2_dir_get_new_buffer(ip, dblock, &bh);

                else

                        error = gfs2_dir_get_existing_buffer(ip, dblock, &bh);

                if (error)

                        goto fail;

                gfs2_trans_add_bh(ip->i_gl, bh, 1);

                memcpy(bh->b_data + o, buf, amount);

                brelse(bh);

                buf += amount;

                copied += amount;

                lblock++;

                dblock++;

                extlen--;

                o = sizeof(struct gfs2_meta_header);

        }

out:

        error = gfs2_meta_inode_buffer(ip, &dibh);

        if (error)

                return error;

        if (ip->i_di.di_size < offset + copied)

                ip->i_di.di_size = offset + copied;

        ip->i_inode.i_mtime = ip->i_inode.i_ctime = CURRENT_TIME;

        gfs2_trans_add_bh(ip->i_gl, dibh, 1);

        gfs2_dinode_out(ip, dibh->b_data);

        brelse(dibh);

        return copied;

fail:

        if (copied)

                goto out;

        return error;

}

static int gfs2_dir_read_stuffed(struct gfs2_inode *ip, char *buf,

                                 u64 offset, unsigned int size)

{

        struct buffer_head *dibh;

        int error;

        error = gfs2_meta_inode_buffer(ip, &dibh);

        if (!error) {

                offset += sizeof(struct gfs2_dinode);

                memcpy(buf, dibh->b_data + offset, size);

                brelse(dibh);

        }

        return (error) ? error : size;

}

/**

 * gfs2_dir_read_data - Read a data from a directory inode

 * @ip: The GFS2 Inode

 * @buf: The buffer to place result into

 * @offset: File offset to begin jdata_readng from

 * @size: Amount of data to transfer

 *

 * Returns: The amount of data actually copied or the error

 */

static int gfs2_dir_read_data(struct gfs2_inode *ip, char *buf, u64 offset,

                              unsigned int size, unsigned ra)

{

        struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);

        u64 lblock, dblock;

        u32 extlen = 0;

        unsigned int o;

        int copied = 0;

        int error = 0;

        if (offset >= ip->i_di.di_size)

                return 0;

        if (offset + size > ip->i_di.di_size)

                size = ip->i_di.di_size - offset;

        if (!size)

                return 0;

        if (gfs2_is_stuffed(ip))

                return gfs2_dir_read_stuffed(ip, buf, offset, size);

        if (gfs2_assert_warn(sdp, gfs2_is_jdata(ip)))

                return -EINVAL;

        lblock = offset;

        o = do_div(lblock, sdp->sd_jbsize) + sizeof(struct gfs2_meta_header);

        while (copied < size) {

                unsigned int amount;

                struct buffer_head *bh;

                int new;

                amount = size - copied;

                if (amount > sdp->sd_sb.sb_bsize - o)

                        amount = sdp->sd_sb.sb_bsize - o;

                if (!extlen) {

                        new = 0;

                        error = gfs2_extent_map(&ip->i_inode, lblock, &new,

                                                &dblock, &extlen);

                        if (error || !dblock)

                                goto fail;

                        BUG_ON(extlen < 1);

                        if (!ra)

                                extlen = 1;

                        bh = gfs2_meta_ra(ip->i_gl, dblock, extlen);

                } else {

                        error = gfs2_meta_read(ip->i_gl, dblock, DIO_WAIT, &bh);

                        if (error)

                                goto fail;

                }

                error = gfs2_metatype_check(sdp, bh, GFS2_METATYPE_JD);

                if (error) {

                        brelse(bh);

                        goto fail;

                }

                dblock++;

                extlen--;

                memcpy(buf, bh->b_data + o, amount);

                brelse(bh);

                buf += amount;

                copied += amount;

                lblock++;

                o = sizeof(struct gfs2_meta_header);

        }

        return copied;

fail:

        return (copied) ? copied : error;

}

static inline int gfs2_dirent_sentinel(const struct gfs2_dirent *dent)

{

        return dent->de_inum.no_addr == 0 || dent->de_inum.no_formal_ino == 0;

}

static inline int __gfs2_dirent_find(const struct gfs2_dirent *dent,

                                     const struct qstr *name, int ret)

{

        if (!gfs2_dirent_sentinel(dent) &&

            be32_to_cpu(dent->de_hash) == name->hash &&

            be16_to_cpu(dent->de_name_len) == name->len &&

            memcmp(dent+1, name->name, name->len) == 0)

                return ret;

        return 0;

}

static int gfs2_dirent_find(const struct gfs2_dirent *dent,

                            const struct qstr *name,

                            void *opaque)

{

        return __gfs2_dirent_find(dent, name, 1);

}

static int gfs2_dirent_prev(const struct gfs2_dirent *dent,

                            const struct qstr *name,

                            void *opaque)

{

        return __gfs2_dirent_find(dent, name, 2);

}

/*

 * name->name holds ptr to start of block.

 * name->len holds size of block.

 */

static int gfs2_dirent_last(const struct gfs2_dirent *dent,

                            const struct qstr *name,

                            void *opaque)

{

        const char *start = name->name;

        const char *end = (const char *)dent + be16_to_cpu(dent->de_rec_len);

        if (name->len == (end - start))

                return 1;

        return 0;

}

static int gfs2_dirent_find_space(const struct gfs2_dirent *dent,

                                  const struct qstr *name,

                                  void *opaque)

{

        unsigned required = GFS2_DIRENT_SIZE(name->len);

        unsigned actual = GFS2_DIRENT_SIZE(be16_to_cpu(dent->de_name_len));

        unsigned totlen = be16_to_cpu(dent->de_rec_len);

        if (gfs2_dirent_sentinel(dent))

                actual = GFS2_DIRENT_SIZE(0);

        if (totlen - actual >= required)

                return 1;

        return 0;

}

struct dirent_gather {

        const struct gfs2_dirent **pdent;

        unsigned offset;

};

static int gfs2_dirent_gather(const struct gfs2_dirent *dent,

                              const struct qstr *name,

                              void *opaque)

{

        struct dirent_gather *g = opaque;

        if (!gfs2_dirent_sentinel(dent)) {

                g->pdent[g->offset++] = dent;

        }

        return 0;

}

/*

 * Other possible things to check:

 * - Inode located within filesystem size (and on valid block)

 * - Valid directory entry type

 * Not sure how heavy-weight we want to make this... could also check

 * hash is correct for example, but that would take a lot of extra time.

 * For now the most important thing is to check that the various sizes

 * are correct.

 */

static int gfs2_check_dirent(struct gfs2_dirent *dent, unsigned int offset,

                             unsigned int size, unsigned int len, int first)

{

        const char *msg = "gfs2_dirent too small";

        if (unlikely(size < sizeof(struct gfs2_dirent)))

                goto error;

        msg = "gfs2_dirent misaligned";

        if (unlikely(offset & 0x7))

                goto error;

        msg = "gfs2_dirent points beyond end of block";

        if (unlikely(offset + size > len))

                goto error;

        msg = "zero inode number";

        if (unlikely(!first && gfs2_dirent_sentinel(dent)))

                goto error;

        msg = "name length is greater than space in dirent";

        if (!gfs2_dirent_sentinel(dent) &&

            unlikely(sizeof(struct gfs2_dirent)+be16_to_cpu(dent->de_name_len) >

                     size))

                goto error;

        return 0;

error:

        printk(KERN_WARNING "gfs2_check_dirent: %s (%s)\n", msg,

               first ? "first in block" : "not first in block");

        return -EIO;

}

static int gfs2_dirent_offset(const void *buf)

{

        const struct gfs2_meta_header *h = buf;

        int offset;

        BUG_ON(buf == NULL);

        switch(be32_to_cpu(h->mh_type)) {

        case GFS2_METATYPE_LF:

                offset = sizeof(struct gfs2_leaf);

                break;

        case GFS2_METATYPE_DI:

                offset = sizeof(struct gfs2_dinode);

                break;

        default:

                goto wrong_type;

        }

        return offset;

wrong_type:

        printk(KERN_WARNING "gfs2_scan_dirent: wrong block type %u\n",

               be32_to_cpu(h->mh_type));

        return -1;

}

static struct gfs2_dirent *gfs2_dirent_scan(struct inode *inode, void *buf,

                                            unsigned int len, gfs2_dscan_t scan,

                                            const struct qstr *name,

                                            void *opaque)

{

        struct gfs2_dirent *dent, *prev;

        unsigned offset;

        unsigned size;

        int ret = 0;

        ret = gfs2_dirent_offset(buf);

        if (ret < 0)

                goto consist_inode;

        offset = ret;

        prev = NULL;

        dent = buf + offset;

        size = be16_to_cpu(dent->de_rec_len);

        if (gfs2_check_dirent(dent, offset, size, len, 1))

                goto consist_inode;

        do {

                ret = scan(dent, name, opaque);

                if (ret)

                        break;

                offset += size;

                if (offset == len)

                        break;

                prev = dent;

                dent = buf + offset;

                size = be16_to_cpu(dent->de_rec_len);

                if (gfs2_check_dirent(dent, offset, size, len, 0))

                        goto consist_inode;

        } while(1);

        switch(ret) {

        case 0:

                return NULL;

        case 1:

                return dent;

        case 2:

                return prev ? prev : dent;

        default:

                BUG_ON(ret > 0);

                return ERR_PTR(ret);

        }

consist_inode:

        gfs2_consist_inode(GFS2_I(inode));

        return ERR_PTR(-EIO);

}

/**

 * dirent_first - Return the first dirent

 * @dip: the directory

 * @bh: The buffer

 * @dent: Pointer to list of dirents

 *

 * return first dirent whether bh points to leaf or stuffed dinode

 *

 * Returns: IS_LEAF, IS_DINODE, or -errno

 */

static int dirent_first(struct gfs2_inode *dip, struct buffer_head *bh,

                        struct gfs2_dirent **dent)

{

        struct gfs2_meta_header *h = (struct gfs2_meta_header *)bh->b_data;

        if (be32_to_cpu(h->mh_type) == GFS2_METATYPE_LF) {

                if (gfs2_meta_check(GFS2_SB(&dip->i_inode), bh))

                        return -EIO;

                *dent = (struct gfs2_dirent *)(bh->b_data +

                                               sizeof(struct gfs2_leaf));

                return IS_LEAF;

        } else {

                if (gfs2_metatype_check(GFS2_SB(&dip->i_inode), bh, GFS2_METATYPE_DI))

                        return -EIO;

                *dent = (struct gfs2_dirent *)(bh->b_data +

                                               sizeof(struct gfs2_dinode));

                return IS_DINODE;

        }

}

static int dirent_check_reclen(struct gfs2_inode *dip,

                               const struct gfs2_dirent *d, const void *end_p)

{

        const void *ptr = d;

        u16 rec_len = be16_to_cpu(d->de_rec_len);

        if (unlikely(rec_len < sizeof(struct gfs2_dirent)))

                goto broken;

        ptr += rec_len;

        if (ptr < end_p)

                return rec_len;

        if (ptr == end_p)

                return -ENOENT;

broken:

        gfs2_consist_inode(dip);

        return -EIO;

}

/**

 * dirent_next - Next dirent

 * @dip: the directory

 * @bh: The buffer

 * @dent: Pointer to list of dirents

 *

 * Returns: 0 on success, error code otherwise

 */

static int dirent_next(struct gfs2_inode *dip, struct buffer_head *bh,

                       struct gfs2_dirent **dent)

{

        struct gfs2_dirent *cur = *dent, *tmp;

        char *bh_end = bh->b_data + bh->b_size;

        int ret;

        ret = dirent_check_reclen(dip, cur, bh_end);

        if (ret < 0)

                return ret;

        tmp = (void *)cur + ret;

        ret = dirent_check_reclen(dip, tmp, bh_end);

        if (ret == -EIO)

                return ret;

        /* Only the first dent could ever have de_inum.no_addr == 0 */

        if (gfs2_dirent_sentinel(tmp)) {

                gfs2_consist_inode(dip);

                return -EIO;

        }

        *dent = tmp;

        return 0;

}

/**

 * dirent_del - Delete a dirent

 * @dip: The GFS2 inode

 * @bh: The buffer

 * @prev: The previous dirent

 * @cur: The current dirent

 *

 */

static void dirent_del(struct gfs2_inode *dip, struct buffer_head *bh,

                       struct gfs2_dirent *prev, struct gfs2_dirent *cur)

{

        u16 cur_rec_len, prev_rec_len;

        if (gfs2_dirent_sentinel(cur)) {

                gfs2_consist_inode(dip);

                return;

        }

        gfs2_trans_add_bh(dip->i_gl, bh, 1);

        /* If there is no prev entry, this is the first entry in the block.

           The de_rec_len is already as big as it needs to be.  Just zero

           out the inode number and return.  */

        if (!prev) {

                cur->de_inum.no_addr = 0;

                cur->de_inum.no_formal_ino = 0;

                return;

        }

        /*  Combine this dentry with the previous one.  */

        prev_rec_len = be16_to_cpu(prev->de_rec_len);

        cur_rec_len = be16_to_cpu(cur->de_rec_len);

        if ((char *)prev + prev_rec_len != (char *)cur)

                gfs2_consist_inode(dip);

        if ((char *)cur + cur_rec_len > bh->b_data + bh->b_size)

                gfs2_consist_inode(dip);

        prev_rec_len += cur_rec_len;

        prev->de_rec_len = cpu_to_be16(prev_rec_len);

}

/*

 * Takes a dent from which to grab space as an argument. Returns the

 * newly created dent.

 */

static struct gfs2_dirent *gfs2_init_dirent(struct inode *inode,

                                            struct gfs2_dirent *dent,

                                            const struct qstr *name,

                                            struct buffer_head *bh)

{

        struct gfs2_inode *ip = GFS2_I(inode);

        struct gfs2_dirent *ndent;

        unsigned offset = 0, totlen;

        if (!gfs2_dirent_sentinel(dent))

                offset = GFS2_DIRENT_SIZE(be16_to_cpu(dent->de_name_len));