htree.c File Reference

#include "ext2fs.h"

Include dependency graph for htree.c:

Go to the source code of this file.

Macros
#define	NAMEI_RA_CHUNKS   2
#define	NAMEI_RA_BLOCKS   4
#define	NAMEI_RA_SIZE   (NAMEI_RA_CHUNKS * NAMEI_RA_BLOCKS)
#define	NAMEI_RA_INDEX(c, b)   (((c) * NAMEI_RA_BLOCKS) + (b))

Functions
__u32	ext3_current_time (struct inode *in)
void	ext3_warning (struct super_block *sb, const char *function, char *fmt,...)
struct buffer_head *	ext3_bread (struct ext2_icb *icb, struct inode *inode, unsigned long block, int *err)
struct buffer_head *	ext3_append (struct ext2_icb *icb, struct inode *inode, ext3_lblk_t *block, int *err)
void	ext3_inc_count (struct inode *inode)
void	ext3_dec_count (struct inode *inode)
unsigned char	ext3_type_by_mode (umode_t mode)
void	ext3_set_de_type (struct super_block *sb, struct ext3_dir_entry_2 *de, umode_t mode)
int	ext3_mark_inode_dirty (struct ext2_icb *icb, struct inode *in)
void	ext3_update_dx_flag (struct inode *inode)
int	add_dirent_to_buf (struct ext2_icb *icb, struct dentry *dentry, struct inode *inode, struct ext3_dir_entry_2 *de, struct buffer_head *bh)
int	ext3_release_dir (struct inode *inode, struct file *filp)
int	ext3_add_entry (struct ext2_icb *icb, struct dentry *dentry, struct inode *inode)
int	ext3_delete_entry (struct ext2_icb *icb, struct inode *dir, struct ext3_dir_entry_2 *de_del, struct buffer_head *bh)
int	ext3_is_dir_empty (struct ext2_icb *icb, struct inode *inode)
static int	search_dirblock (struct buffer_head *bh, struct inode *dir, struct dentry *dentry, unsigned long offset, struct ext3_dir_entry_2 **res_dir)
struct buffer_head *	ext3_find_entry (struct ext2_icb *icb, struct dentry *dentry, struct ext3_dir_entry_2 **res_dir)

Macro Definition Documentation

NAMEI_RA_BLOCKS

#define NAMEI_RA_BLOCKS   4

Definition at line 2151 of file htree.c.

NAMEI_RA_CHUNKS

#define NAMEI_RA_CHUNKS   2

Definition at line 2150 of file htree.c.

NAMEI_RA_INDEX

#define NAMEI_RA_INDEX	(		c,
			b
	)		(((c) * NAMEI_RA_BLOCKS) + (b))

Definition at line 2153 of file htree.c.

NAMEI_RA_SIZE

#define NAMEI_RA_SIZE   (NAMEI_RA_CHUNKS * NAMEI_RA_BLOCKS)

Definition at line 2152 of file htree.c.

Function Documentation

add_dirent_to_buf()

int add_dirent_to_buf	(	struct ext2_icb *	icb,
		struct dentry *	dentry,
		struct inode *	inode,
		struct ext3_dir_entry_2 *	de,
		struct buffer_head *	bh
	)

Definition at line 386 of file htree.c.

{
    struct inode *dir = dentry->d_parent->d_inode;
    const char  *name = dentry->d_name.name;
    int     namelen = dentry->d_name.len;
    unsigned int    offset = 0;
    unsigned short  reclen;
    int     nlen, rlen, err;
    char        *top;
 
    reclen = EXT3_DIR_REC_LEN(namelen);
    if (!de) {
        de = (struct ext3_dir_entry_2 *)bh->b_data;
        top = bh->b_data + dir->i_sb->s_blocksize - reclen;
        while ((char *) de <= top) {
            if (!ext3_check_dir_entry("ext3_add_entry", dir, de,
                                      bh, offset)) {
                __brelse(bh);
                return -EIO;
            }
            if (ext3_match(namelen, name, de)) {
                __brelse(bh);
                return -EEXIST;
            }
            nlen = EXT3_DIR_REC_LEN(de->name_len);
            rlen = ext3_rec_len_from_disk(de->rec_len);
            if ((de->inode? rlen - nlen: rlen) >= reclen)
                break;
            de = (struct ext3_dir_entry_2 *)((char *)de + rlen);
            offset += rlen;
        }
        if ((char *) de > top)
            return -ENOSPC;
    }
 
    /* By now the buffer is marked for journaling */
    nlen = EXT3_DIR_REC_LEN(de->name_len);
    rlen = ext3_rec_len_from_disk(de->rec_len);
    if (de->inode) {
        struct ext3_dir_entry_2 *de1 = (struct ext3_dir_entry_2 *)((char *)de + nlen);
        de1->rec_len = ext3_rec_len_to_disk(rlen - nlen);
        de->rec_len = ext3_rec_len_to_disk(nlen);
        de = de1;
    }
    de->file_type = EXT3_FT_UNKNOWN;
    if (inode) {
        de->inode = cpu_to_le32(inode->i_ino);
        ext3_set_de_type(dir->i_sb, de, inode->i_mode);
    } else
        de->inode = 0;
    de->name_len = (__u8)namelen;
    memcpy(de->name, name, namelen);
 
    /*
     * XXX shouldn't update any times until successful
     * completion of syscall, but too many callers depend
     * on this.
     *
     * XXX similarly, too many callers depend on
     * ext4_new_inode() setting the times, but error
     * recovery deletes the inode, so the worst that can
     * happen is that the times are slightly out of date
     * and/or different from the directory change time.
     */
    dir->i_mtime = dir->i_ctime = ext3_current_time(dir);
    ext3_update_dx_flag(dir);
    dir->i_version++;
    ext3_mark_inode_dirty(icb, dir);
    set_buffer_dirty(bh);
    __brelse(bh);
    return 0;
}

Referenced by ext3_add_entry().

ext3_add_entry()

int ext3_add_entry	(	struct ext2_icb *	icb,
		struct dentry *	dentry,
		struct inode *	inode
	)

Definition at line 1946 of file htree.c.

{
    struct inode *dir = dentry->d_parent->d_inode;
    struct buffer_head *bh;
    struct ext3_dir_entry_2 *de;
    struct super_block *sb;
    int retval;
#ifdef EXT2_HTREE_INDEX
    int dx_fallback=0;
#endif
    unsigned blocksize;
    ext3_lblk_t block, blocks;
 
    sb = dir->i_sb;
    blocksize = sb->s_blocksize;
    if (!dentry->d_name.len)
        return -EINVAL;
 
#ifdef EXT2_HTREE_INDEX
    if (is_dx(dir)) {
        retval = ext3_dx_add_entry(icb, dentry, inode);
        if (!retval || (retval != ERR_BAD_DX_DIR))
            return retval;
        EXT3_I(dir)->i_flags &= ~EXT3_INDEX_FL;
        dx_fallback++;
        ext3_save_inode(icb, dir);
    }
#endif
 
    blocks = (ext3_lblk_t)(dir->i_size >> sb->s_blocksize_bits);
    for (block = 0; block < blocks; block++) {
        bh = ext3_bread(icb, dir, block, &retval);
        if (!bh)
            return retval;
        retval = add_dirent_to_buf(icb, dentry, inode, NULL, bh);
        if (retval != -ENOSPC)
            return retval;
 
#ifdef EXT2_HTREE_INDEX
        if (blocks == 1 && !dx_fallback &&
                EXT3_HAS_COMPAT_FEATURE(sb, EXT3_FEATURE_COMPAT_DIR_INDEX))
            return make_indexed_dir(icb, dentry, inode, bh);
#endif
 
        brelse(bh);
    }
    bh = ext3_append(icb, dir, &block, &retval);
    if (!bh)
        return retval;
    de = (struct ext3_dir_entry_2 *) bh->b_data;
    de->inode = 0;
    de->rec_len = ext3_rec_len_to_disk(blocksize);
    return add_dirent_to_buf(icb, dentry, inode, de, bh);
}

Referenced by Ext2AddEntry().

ext3_append()

struct buffer_head * ext3_append	(	struct ext2_icb *	icb,
		struct inode *	inode,
		ext3_lblk_t *	block,
		int *	err
	)

Definition at line 279 of file htree.c.

{
    PEXT2_MCB   mcb = CONTAINING_RECORD(inode, EXT2_MCB, Inode);
    PEXT2_FCB   dcb = mcb->Fcb;
    NTSTATUS    status;
 
    ASSERT(dcb);
    ASSERT(inode == dcb->Inode);
 
    /* allocate new block since there's no space for us */
    *block = (ext3_lblk_t)(inode->i_size >> inode->i_sb->s_blocksize_bits);
    dcb->Header.AllocationSize.QuadPart += dcb->Vcb->BlockSize;
    status = Ext2ExpandFile(icb, dcb->Vcb, mcb, &(dcb->Header.AllocationSize));
    if (NT_SUCCESS(status)) {
 
        /* update Dcb */
        dcb->Header.ValidDataLength = dcb->Header.FileSize = dcb->Header.AllocationSize;
        mcb->Inode.i_size = dcb->Header.AllocationSize.QuadPart;
 
        /* save parent directory's inode */
        Ext2SaveInode(icb, dcb->Vcb, inode);
    }
 
    return ext3_bread(icb, inode, *block, err);
}

Referenced by Ext2AddDotEntries(), and ext3_add_entry().

ext3_bread()

struct buffer_head * ext3_bread	(	struct ext2_icb *	icb,
		struct inode *	inode,
		unsigned long	block,
		int *	err
	)

Definition at line 230 of file htree.c.

{
    struct buffer_head * bh = NULL;
    NTSTATUS    status = STATUS_SUCCESS;
    ULONG       lbn = 0, num = 0;
 
    PEXT2_MCB   Mcb = CONTAINING_RECORD(inode, EXT2_MCB, Inode);
 
    /* for symlink file, read it's target instead */
    if (NULL != Mcb && IsMcbSymLink(Mcb))
        Mcb = Mcb->Target;
    if (NULL == Mcb) {
        *err = -EINVAL;
        return NULL;
    }
 
    /* mapping file offset to ext2 block */
    if (INODE_HAS_EXTENT(&Mcb->Inode)) {
        status = Ext2MapExtent(icb, inode->i_sb->s_priv,
                               Mcb, block, FALSE,
                               &lbn, &num);
    } else {
        status = Ext2MapIndirect(icb, inode->i_sb->s_priv,
                                 Mcb, block, FALSE,
                                 &lbn, &num);
    }
 
    if (!NT_SUCCESS(status)) {
        *err = Ext2LinuxError(status);
        return bh;
    }
 
    bh = sb_getblk(inode->i_sb, lbn);
    if (!bh) {
        *err = -ENOMEM;
        return bh;
    }
    if (buffer_uptodate(bh))
        return bh;
 
    *err = bh_submit_read(bh);
    if (*err) {
        __brelse(bh);
        return NULL;
    }
    return bh;
}

Referenced by ext3_add_entry(), ext3_append(), ext3_find_entry(), and ext3_is_dir_empty().

ext3_current_time()

__u32 ext3_current_time

(

struct inode *

in

)

Definition at line 204 of file htree.c.

{
    LARGE_INTEGER   SysTime;
    KeQuerySystemTime(&SysTime);
 
    return Ext2LinuxTime(SysTime);
}

Referenced by add_dirent_to_buf(), Ext2RemoveEntry(), and Ext2SetFileType().

ext3_dec_count()

void ext3_dec_count

(

struct inode *

inode

)

Definition at line 312 of file htree.c.

{
    inode->i_nlink--;
}

Referenced by Ext2RemoveEntry(), Ext2SetFileType(), and Ext2SetReparsePoint().

ext3_delete_entry()

int ext3_delete_entry	(	struct ext2_icb *	icb,
		struct inode *	dir,
		struct ext3_dir_entry_2 *	de_del,
		struct buffer_head *	bh
	)

Definition at line 2005 of file htree.c.

{
    struct ext3_dir_entry_2 *de, *pde = NULL;
    size_t i = 0;
 
    de = (struct ext3_dir_entry_2 *) bh->b_data;
    while (i < bh->b_size) {
        if (!ext3_check_dir_entry("ext3_delete_entry", dir, de, bh, i))
            return -EIO;
        if (de == de_del)  {
            if (pde)
                pde->rec_len = ext3_rec_len_to_disk(
                                   ext3_rec_len_from_disk(pde->rec_len) +
                                   ext3_rec_len_from_disk(de->rec_len));
            else
                de->inode = 0;
            dir->i_version++;
            /* ext3_journal_dirty_metadata(handle, bh); */
            set_buffer_dirty(bh);
            return 0;
        }
        i += ext3_rec_len_from_disk(de->rec_len);
        pde = de;
        de = ext3_next_entry(de);
    }
    return -ENOENT;
}

Referenced by Ext2RemoveEntry().

ext3_find_entry()

struct buffer_head * ext3_find_entry	(	struct ext2_icb *	icb,
		struct dentry *	dentry,
		struct ext3_dir_entry_2 **	res_dir
	)

Definition at line 2166 of file htree.c.

{
    struct inode *dir = dentry->d_parent->d_inode;
    struct super_block *sb = dir->i_sb;
    struct buffer_head *bh_use[NAMEI_RA_SIZE];
    struct buffer_head *bh, *ret = NULL;
    ext3_lblk_t start, block, b;
    int ra_max = 0;     /* Number of bh's in the readahead
                   buffer, bh_use[] */
    int ra_ptr = 0;     /* Current index into readahead
                   buffer */
    int num = 0;
    ext3_lblk_t  nblocks;
    int i, err;
    int namelen = dentry->d_name.len;
 
    *res_dir = NULL;
    if (namelen > EXT3_NAME_LEN)
        return NULL;
 
#ifdef EXT2_HTREE_INDEX
    if (icb->MajorFunction != IRP_MJ_CREATE && is_dx(dir)) {
        bh = ext3_dx_find_entry(icb, dentry, res_dir, &err);
        /*
         * On success, or if the error was file not found,
         * return.  Otherwise, fall back to doing a search the
         * old fashioned way.
         */
        if (bh || (err != ERR_BAD_DX_DIR))
            return bh;
        dxtrace(printk("ext4_find_entry: dx failed, "
                       "falling back\n"));
    }
#endif
 
    nblocks = (ext3_lblk_t)(dir->i_size >> EXT3_BLOCK_SIZE_BITS(sb));
    start = 0;
    block = start;
restart:
    do {
        /*
         * We deal with the read-ahead logic here.
         */
        if (ra_ptr >= ra_max) {
            /* Refill the readahead buffer */
            ra_ptr = 0;
            b = block;
            for (ra_max = 0; ra_max < NAMEI_RA_SIZE; ra_max++) {
                /*
                 * Terminate if we reach the end of the
                 * directory and must wrap, or if our
                 * search has finished at this block.
                 */
                if (b >= nblocks || (num && block == start)) {
                    bh_use[ra_max] = NULL;
                    break;
                }
                num++;
                bh = ext3_bread(icb, dir, b++, &err);
                bh_use[ra_max] = bh;
            }
        }
        if ((bh = bh_use[ra_ptr++]) == NULL)
            goto next;
        wait_on_buffer(bh);
        if (!buffer_uptodate(bh)) {
            /* read error, skip block & hope for the best */
            ext3_error(sb, __FUNCTION__, "reading directory #%lu "
                       "offset %lu", dir->i_ino,
                       (unsigned long)block);
            brelse(bh);
            goto next;
        }
        i = search_dirblock(bh, dir, dentry,
                            block << EXT3_BLOCK_SIZE_BITS(sb), res_dir);
        if (i == 1) {
            ret = bh;
            goto cleanup_and_exit;
        } else {
            brelse(bh);
            if (i < 0)
                goto cleanup_and_exit;
        }
next:
        if (++block >= nblocks)
            block = 0;
    } while (block != start);
 
    /*
     * If the directory has grown while we were searching, then
     * search the last part of the directory before giving up.
     */
    block = nblocks;
    nblocks = (ext3_lblk_t)(dir->i_size >> EXT3_BLOCK_SIZE_BITS(sb));
    if (block < nblocks) {
        start = 0;
        goto restart;
    }
 
cleanup_and_exit:
    /* Clean up the read-ahead blocks */
    for (; ra_ptr < ra_max; ra_ptr++)
        brelse(bh_use[ra_ptr]);
    return ret;
}

Referenced by Ext2RemoveEntry(), Ext2ScanDir(), and Ext2SetFileType().

ext3_inc_count()

void ext3_inc_count

(

struct inode *

inode

)

Definition at line 307 of file htree.c.

{
    inode->i_nlink++;
}

Referenced by Ext2AddEntry(), and Ext2SetFileType().

ext3_is_dir_empty()

int ext3_is_dir_empty	(	struct ext2_icb *	icb,
		struct inode *	inode
	)

Definition at line 2038 of file htree.c.

{
    unsigned int offset;
    struct buffer_head *bh;
    struct ext3_dir_entry_2 *de, *de1;
    struct super_block *sb;
    int err = 0;
 
    sb = inode->i_sb;
    if (inode->i_size < EXT3_DIR_REC_LEN(1) + EXT3_DIR_REC_LEN(2) ||
            !(bh = ext3_bread(icb, inode, 0, &err))) {
        if (err)
            ext3_error(inode->i_sb, __FUNCTION__,
                       "error %d reading directory #%lu offset 0",
                       err, inode->i_ino);
        else
            ext3_warning(inode->i_sb, __FUNCTION__,
                         "bad directory (dir #%lu) - no data block",
                         inode->i_ino);
        return 1;
    }
    de = (struct ext3_dir_entry_2 *) bh->b_data;
    de1 = ext3_next_entry(de);
    if (le32_to_cpu(de->inode) != inode->i_ino ||
            !le32_to_cpu(de1->inode) ||
            strcmp(".", de->name) ||
            strcmp("..", de1->name)) {
        ext3_warning(inode->i_sb, "empty_dir",
                     "bad directory (dir #%lu) - no `.' or `..'",
                     inode->i_ino);
        brelse(bh);
        return 1;
    }
    offset = ext3_rec_len_from_disk(de->rec_len) +
             ext3_rec_len_from_disk(de1->rec_len);
    de = ext3_next_entry(de1);
    while (offset < inode->i_size) {
        if (!bh ||
                (void *) de >= (void *) (bh->b_data+sb->s_blocksize)) {
            err = 0;
            brelse(bh);
            bh = ext3_bread(icb, inode, offset >> EXT3_BLOCK_SIZE_BITS(sb), &err);
            if (!bh) {
                if (err)
                    ext3_error(sb, __FUNCTION__, "error %d reading directory"
                               " #%lu offset %u", err, inode->i_ino, offset);
                offset += sb->s_blocksize;
                continue;
            }
            de = (struct ext3_dir_entry_2 *) bh->b_data;
        }
        if (!ext3_check_dir_entry("empty_dir", inode, de, bh, offset)) {
            de = (struct ext3_dir_entry_2 *)(bh->b_data +
                                             sb->s_blocksize);
            offset = (offset | (sb->s_blocksize - 1)) + 1;
            continue;
        }
        if (le32_to_cpu(de->inode)) {
            brelse(bh);
            return 0;
        }
        offset += ext3_rec_len_from_disk(de->rec_len);
        de = ext3_next_entry(de);
    }
    brelse(bh);
    return 1;
}

Referenced by Ext2IsDirectoryEmpty().

ext3_mark_inode_dirty()

int ext3_mark_inode_dirty	(	struct ext2_icb *	icb,
		struct inode *	in
	)

Definition at line 360 of file htree.c.

{
    if (Ext2SaveInode(icb, in->i_sb->s_priv, in))
        return 0;
 
    return -ENOMEM;
}

Referenced by add_dirent_to_buf(), Ext2AddDotEntries(), Ext2AddEntry(), Ext2RemoveEntry(), and Ext2SetFileType().

ext3_release_dir()

int ext3_release_dir	(	struct inode *	inode,
		struct file *	filp
	)

Definition at line 1929 of file htree.c.

{
    return 0;
}

Referenced by Ext2Cleanup().

ext3_set_de_type()

void ext3_set_de_type	(	struct super_block *	sb,
		struct ext3_dir_entry_2 *	de,
		umode_t	mode
	)

Definition at line 347 of file htree.c.

{
    if (EXT3_HAS_INCOMPAT_FEATURE(sb, EXT3_FEATURE_INCOMPAT_FILETYPE))
        de->file_type = ext3_type_by_mode(mode);
}

Referenced by add_dirent_to_buf(), Ext2AddDotEntries(), and Ext2SetFileType().

ext3_type_by_mode()

unsigned char ext3_type_by_mode

(

umode_t

mode

)

Definition at line 317 of file htree.c.

{
    unsigned char type = 0;
 
    switch (mode & S_IFMT) {
    case S_IFREG:
        type = EXT3_FT_REG_FILE;
        break;
    case S_IFDIR:
        type = EXT3_FT_DIR;
        break;
    case S_IFCHR:
        type =  EXT3_FT_CHRDEV;
        break;
    case S_IFBLK:
        type = EXT3_FT_BLKDEV;
        break;
    case S_IFIFO:
        type = EXT3_FT_FIFO;
        break;
    case S_IFSOCK:
        type = EXT3_FT_SOCK;
        break;
    case S_IFLNK:
        type = EXT3_FT_SYMLINK;
    }
 
    return type;
};

Referenced by ext3_set_de_type().

ext3_update_dx_flag()

void ext3_update_dx_flag

(

struct inode *

inode

)

Definition at line 368 of file htree.c.

{
    if (!EXT3_HAS_COMPAT_FEATURE(inode->i_sb,
                                 EXT3_FEATURE_COMPAT_DIR_INDEX))
        EXT3_I(inode)->i_flags &= ~EXT3_INDEX_FL;
}

Referenced by add_dirent_to_buf(), and Ext2RemoveEntry().

ext3_warning()

void ext3_warning	(	struct super_block *	sb,
		const char *	function,
		char *	fmt,
			...
	)

Definition at line 212 of file htree.c.

{
#if DX_DEBUG
    va_list args;
 
    va_start(args, fmt);
    printk("EXT3-fs warning (device %s): %s: ",
           sb->s_id, function);
    printk(fmt, args);
    printk("\n");
    va_end(args);
#endif
}

Referenced by Ext2RemoveEntry(), and ext3_is_dir_empty().

search_dirblock()

static int search_dirblock ( struct buffer_head *  bh, struct inode *  dir, struct dentry *  dentry, unsigned long  offset, struct ext3_dir_entry_2 **  res_dir  )

inlinestatic

Definition at line 2109 of file htree.c.

{
    struct ext3_dir_entry_2 * de;
    char * dlimit;
    int de_len;
    const char *name = dentry->d_name.name;
    int namelen = dentry->d_name.len;
 
    de = (struct ext3_dir_entry_2 *) bh->b_data;
    dlimit = bh->b_data + dir->i_sb->s_blocksize;
    while ((char *) de < dlimit) {
        /* this code is executed quadratically often */
        /* do minimal checking `by hand' */
 
        if ((char *) de + namelen <= dlimit &&
                ext3_match (namelen, name, de)) {
            /* found a match - just to be sure, do a full check */
            if (!ext3_check_dir_entry("ext3_find_entry",
                                      dir, de, bh, offset))
                return -1;
            *res_dir = de;
            return 1;
        }
        /* prevent looping on a bad block */
        de_len = ext3_rec_len_from_disk(de->rec_len);
 
        if (de_len <= 0)
            return -1;
        offset += de_len;
        de = (struct ext3_dir_entry_2 *) ((char *) de + de_len);
    }
    return 0;
}

Referenced by ext3_find_entry().