Subject: [PATCH 02/16] Squashfs: directory lookup operations - Kernel

This is a discussion on Subject: [PATCH 02/16] Squashfs: directory lookup operations - Kernel ; Signed-off-by: Phillip Lougher --- fs/squashfs/namei.c | 226 ++++++++++++++++++++++++++++++++++++++++++++++++++ + 1 files changed, 226 insertions(+), 0 deletions(-) diff --git a/fs/squashfs/namei.c b/fs/squashfs/namei.c new file mode 100644 index 0000000..fdc1b03 --- /dev/null +++ b/fs/squashfs/namei.c @@ -0,0 +1,226 @@ +/* + * Squashfs - a ...

+ Reply to Thread
Results 1 to 4 of 4

Thread: Subject: [PATCH 02/16] Squashfs: directory lookup operations

  1. Subject: [PATCH 02/16] Squashfs: directory lookup operations


    Signed-off-by: Phillip Lougher
    ---
    fs/squashfs/namei.c | 226 ++++++++++++++++++++++++++++++++++++++++++++++++++ +
    1 files changed, 226 insertions(+), 0 deletions(-)

    diff --git a/fs/squashfs/namei.c b/fs/squashfs/namei.c
    new file mode 100644
    index 0000000..fdc1b03
    --- /dev/null
    +++ b/fs/squashfs/namei.c
    @@ -0,0 +1,226 @@
    +/*
    + * Squashfs - a compressed read only filesystem for Linux
    + *
    + * Copyright (c) 2002, 2003, 2004, 2005, 2006, 2007, 2008
    + * Phillip Lougher
    + *
    + * This program is free software; you can redistribute it and/or
    + * modify it under the terms of the GNU General Public License
    + * as published by the Free Software Foundation; either version 2,
    + * or (at your option) any later version.
    + *
    + * This program is distributed in the hope that it will be useful,
    + * but WITHOUT ANY WARRANTY; without even the implied warranty of
    + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
    + * GNU General Public License for more details.
    + *
    + * You should have received a copy of the GNU General Public License
    + * along with this program; if not, write to the Free Software
    + * Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
    + *
    + * namei.c
    + */
    +
    +/*
    + * This file implements code to do filename lookup in directories.
    + *
    + * Like inodes, directories are packed into compressed metadata blocks, stored
    + * in a directory table. Directories are accessed using the start address of
    + * the metablock containing the directory and the offset into the
    + * decompressed block ().
    + *
    + * Directories are organised in a slightly complex way, and are not simply
    + * a list of file names. The organisation takes advantage of the
    + * fact that (in most cases) the inodes of the files will be in the same
    + * compressed metadata block, and therefore, can share the start block.
    + * Directories are therefore organised in a two level list, a directory
    + * header containing the shared start block value, and a sequence of directory
    + * entries, each of which share the shared start block. A new directory header
    + * is written once/if the inode start block changes. The directory
    + * header/directory entry list is repeated as many times as necessary.
    + *
    + * Directories are sorted, and can contain a directory index to speed up
    + * file lookup. Directory indexes store one entry per metablock, each entry
    + * storing the index/filename mapping to the first directory header
    + * in each metadata block. Directories are sorted in alphabetical order,
    + * and at lookup the index is scanned linearly looking for the first filename
    + * alphabetically larger than the filename being looked up. At this point the
    + * location of the metadata block the filename is in has been found.
    + * The general idea of the index is ensure only one metadata block needs to be
    + * decompressed to do a lookup irrespective of the length of the directory.
    + * This scheme has the advantage that it doesn't require extra memory overhead
    + * and doesn't require much extra storage on disk.
    + */
    +
    +#include
    +#include
    +#include
    +#include
    +#include
    +#include
    +#include
    +#include
    +#include
    +
    +#include "squashfs.h"
    +
    +/*
    + * Lookup name in the directory index, returning the location of the metadata
    + * block containing it, and the directory index this represents.
    + */
    +static int get_dir_index_using_name(struct super_block *s,
    + long long *next_block, unsigned int *next_offset,
    + long long index_start, unsigned int index_offset,
    + int i_count, const char *name, int len)
    +{
    + struct squashfs_sb_info *msblk = s->s_fs_info;
    + int i, size, length = 0;
    + struct squashfs_dir_index *index;
    + char *str;
    +
    + TRACE("Entered get_dir_index_using_name, i_count %d\n", i_count);
    +
    + str = kmalloc(sizeof(*index) + (SQUASHFS_NAME_LEN + 1) * 2, GFP_KERNEL);
    + if (str == NULL) {
    + ERROR("Failed to allocate squashfs_dir_index\n");
    + goto out;
    + }
    +
    + index = (struct squashfs_dir_index *) (str + SQUASHFS_NAME_LEN + 1);
    + strncpy(str, name, len);
    + str[len] = '\0';
    +
    + for (i = 0; i < i_count; i++) {
    + squashfs_read_metadata(s, index, index_start, index_offset,
    + sizeof(*index), &index_start,
    + &index_offset);
    +
    + size = le32_to_cpu(index->size) + 1;
    +
    + squashfs_read_metadata(s, index->name, index_start,
    + index_offset, size, &index_start,
    + &index_offset);
    +
    + index->name[size] = '\0';
    +
    + if (strcmp(index->name, str) > 0)
    + break;
    +
    + length = le32_to_cpu(index->index);
    + *next_block = le32_to_cpu(index->start_block) +
    + msblk->directory_table_start;
    + }
    +
    + *next_offset = (length + *next_offset) % SQUASHFS_METADATA_SIZE;
    + kfree(str);
    +
    +out:
    + /*
    + * Return index (f_pos) of the looked up metadata block. Translate
    + * from internal f_pos to external f_pos which is offset by 3 because
    + * we invent "." and ".." entries which are not actually stored in the
    + * directory.
    + */
    + return length + 3;
    +}
    +
    +
    +static struct dentry *squashfs_lookup(struct inode *i, struct dentry *dentry,
    + struct nameidata *nd)
    +{
    + const unsigned char *name = dentry->d_name.name;
    + int len = dentry->d_name.len;
    + struct inode *inode = NULL;
    + struct squashfs_sb_info *msblk = i->i_sb->s_fs_info;
    + long long next_block = SQUASHFS_I(i)->start_block +
    + msblk->directory_table_start;
    + int next_offset = SQUASHFS_I(i)->offset, length = 0, dir_count, size;
    + struct squashfs_dir_header dirh;
    + struct squashfs_dir_entry *dire;
    + unsigned int start_block, offset, ino_number;
    + long long ino;
    +
    + TRACE("Entered squashfs_lookup [%llx:%x]\n", next_block, next_offset);
    +
    + dire = kmalloc(sizeof(*dire) + SQUASHFS_NAME_LEN + 1, GFP_KERNEL);
    + if (dire == NULL) {
    + ERROR("Failed to allocate squashfs_dir_entry\n");
    + goto exit_lookup;
    + }
    +
    + if (len > SQUASHFS_NAME_LEN)
    + goto exit_lookup;
    +
    + length = get_dir_index_using_name(i->i_sb, &next_block, &next_offset,
    + SQUASHFS_I(i)->dir_index_start,
    + SQUASHFS_I(i)->dir_index_offset,
    + SQUASHFS_I(i)->dir_index_count, name, len);
    +
    + while (length < i_size_read(i)) {
    + /*
    + * Read directory header.
    + */
    + if (!squashfs_read_metadata(i->i_sb, &dirh, next_block,
    + next_offset, sizeof(dirh), &next_block,
    + &next_offset))
    + goto failed_read;
    +
    + length += sizeof(dirh);
    +
    + dir_count = le32_to_cpu(dirh.count) + 1;
    + while (dir_count--) {
    + /*
    + * Read directory entry.
    + */
    + if (!squashfs_read_metadata(i->i_sb, dire,
    + next_block, next_offset, sizeof(*dire),
    + &next_block, &next_offset))
    + goto failed_read;
    +
    + size = le16_to_cpu(dire->size) + 1;
    +
    + if (!squashfs_read_metadata(i->i_sb, dire->name,
    + next_block, next_offset, size,
    + &next_block, &next_offset))
    + goto failed_read;
    +
    + length += sizeof(*dire) + size;
    +
    + if (name[0] < dire->name[0])
    + goto exit_lookup;
    +
    + if (len == size && !strncmp(name, dire->name, len)) {
    + start_block = le32_to_cpu(dirh.start_block);
    + offset = le16_to_cpu(dire->offset);
    + ino_number = le32_to_cpu(dirh.inode_number) +
    + (short) le16_to_cpu(dire->inode_number);
    + ino = SQUASHFS_MKINODE(start_block, offset);
    +
    + TRACE("calling squashfs_iget for directory "
    + "entry %s, inode %x:%x, %d\n", name,
    + start_block, offset, ino_number);
    +
    + inode = squashfs_iget(i->i_sb, ino, ino_number);
    +
    + goto exit_lookup;
    + }
    + }
    + }
    +
    +exit_lookup:
    + kfree(dire);
    + if (inode)
    + return d_splice_alias(inode, dentry);
    + d_add(dentry, inode);
    + return ERR_PTR(0);
    +
    +failed_read:
    + ERROR("Unable to read directory block [%llx:%x]\n", next_block,
    + next_offset);
    + goto exit_lookup;
    +}
    +
    +
    +const struct inode_operations squashfs_dir_inode_ops = {
    + .lookup = squashfs_lookup
    +};
    --
    1.5.2.5

    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  2. Re: Subject: [PATCH 02/16] Squashfs: directory lookup operations

    On Fri, 17 Oct 2008, Phillip Lougher wrote:
    > --- /dev/null
    > +++ b/fs/squashfs/namei.c


    > +static int get_dir_index_using_name(struct super_block *s,
    > + long long *next_block, unsigned int *next_offset,
    > + long long index_start, unsigned int index_offset,
    > + int i_count, const char *name, int len)
    > +{
    > + struct squashfs_sb_info *msblk = s->s_fs_info;
    > + int i, size, length = 0;
    > + struct squashfs_dir_index *index;
    > + char *str;
    > +
    > + TRACE("Entered get_dir_index_using_name, i_count %d\n", i_count);
    > +
    > + str = kmalloc(sizeof(*index) + (SQUASHFS_NAME_LEN + 1) * 2, GFP_KERNEL);
    > + if (str == NULL) {
    > + ERROR("Failed to allocate squashfs_dir_index\n");
    > + goto out;
    > + }
    > +
    > + index = (struct squashfs_dir_index *) (str + SQUASHFS_NAME_LEN + 1);


    As str has been returned by kmalloc(), and SQUASHFS_NAME_LEN is equal to 256,
    `str + SQUASHFS_NAME_LEN + 1` is an odd address.

    > + strncpy(str, name, len);
    > + str[len] = '\0';
    > +
    > + for (i = 0; i < i_count; i++) {
    > + squashfs_read_metadata(s, index, index_start, index_offset,
    > + sizeof(*index), &index_start,
    > + &index_offset);
    > +
    > + size = le32_to_cpu(index->size) + 1;

    ^^^^^^^^^^^
    > +
    > + squashfs_read_metadata(s, index->name, index_start,
    > + index_offset, size, &index_start,
    > + &index_offset);
    > +
    > + index->name[size] = '\0';
    > +
    > + if (strcmp(index->name, str) > 0)
    > + break;
    > +
    > + length = le32_to_cpu(index->index);

    ^^^^^^^^^^^
    > + *next_block = le32_to_cpu(index->start_block) +

    ^^^^^^^^^^^^^^^^^^
    > + msblk->directory_table_start;
    > + }


    Hence accessing multi-byte fields in struct squashfs_dir_index causes unaligned
    accesses, which are emulated on some architectures (e.g. on MIPS).

    Use get_unaligned_le32() for unaligned accesses.

    Signed-off-by: Geert Uytterhoeven
    ---
    Actual patch is against current squashfs4.

    fs/squashfs/namei.c | 8 +++++---
    1 file changed, 5 insertions(+), 3 deletions(-)

    --- a/fs/squashfs/namei.c
    +++ b/fs/squashfs/namei.c
    @@ -59,6 +59,8 @@
    #include
    #include

    +#include
    +
    #include "squashfs_fs.h"
    #include "squashfs_fs_sb.h"
    #include "squashfs_fs_i.h"
    @@ -101,7 +103,7 @@ static int get_dir_index_using_name(stru
    break;


    - size = le32_to_cpu(index->size) + 1;
    + size = get_unaligned_le32(&index->size) + 1;

    err = squashfs_read_metadata(sb, index->name, &index_start,
    &index_offset, size);
    @@ -113,8 +115,8 @@ static int get_dir_index_using_name(stru
    if (strcmp(index->name, str) > 0)
    break;

    - length = le32_to_cpu(index->index);
    - *next_block = le32_to_cpu(index->start_block) +
    + length = get_unaligned_le32(&index->index);
    + *next_block = get_unaligned_le32(&index->start_block) +
    msblk->directory_table;
    }


    With kind regards,

    Geert Uytterhoeven
    Software Architect

    Sony Techsoft Centre Europe
    The Corporate Village · Da Vincilaan 7-D1 · B-1935 Zaventem · Belgium

    Phone: +32 (0)2 700 8453
    Fax: +32 (0)2 700 8622
    E-mail: Geert.Uytterhoeven@sonycom.com
    Internet: http://www.sony-europe.com/

    A division of Sony Europe (Belgium) N.V.
    VAT BE 0413.825.160 · RPR Brussels
    Fortis · BIC GEBABEBB · IBAN BE41293037680010

  3. Re: Subject: [PATCH 02/16] Squashfs: directory lookup operations

    Geert Uytterhoeven wrote:
    > On Fri, 17 Oct 2008, Phillip Lougher wrote:
    >> --- /dev/null
    >> +++ b/fs/squashfs/namei.c

    >
    >> +static int get_dir_index_using_name(struct super_block *s,
    >> + long long *next_block, unsigned int *next_offset,
    >> + long long index_start, unsigned int index_offset,
    >> + int i_count, const char *name, int len)
    >> +{
    >> + struct squashfs_sb_info *msblk = s->s_fs_info;
    >> + int i, size, length = 0;
    >> + struct squashfs_dir_index *index;
    >> + char *str;
    >> +
    >> + TRACE("Entered get_dir_index_using_name, i_count %d\n", i_count);
    >> +
    >> + str = kmalloc(sizeof(*index) + (SQUASHFS_NAME_LEN + 1) * 2, GFP_KERNEL);
    >> + if (str == NULL) {
    >> + ERROR("Failed to allocate squashfs_dir_index\n");
    >> + goto out;
    >> + }
    >> +
    >> + index = (struct squashfs_dir_index *) (str + SQUASHFS_NAME_LEN + 1);

    >
    > As str has been returned by kmalloc(), and SQUASHFS_NAME_LEN is equal to 256,
    > `str + SQUASHFS_NAME_LEN + 1` is an odd address.
    >

    [..]
    >> + size = le32_to_cpu(index->size) + 1;

    > ^^^^^^^^^^^

    [.]
    > Hence accessing multi-byte fields in struct squashfs_dir_index causes unaligned
    > accesses, which are emulated on some architectures (e.g. on MIPS).
    >
    > Use get_unaligned_le32() for unaligned accesses.


    How about aligning it properly in the first place instead?
    Three ways:

    1) reordering index and str here, so that index comes first,
    str next.

    2) using another constant instead of +1

    3) using separate allocations for separate objects.

    /mjt
    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  4. Re: Subject: [PATCH 02/16] Squashfs: directory lookup operations

    On Tue, 28 Oct 2008, Michael Tokarev wrote:
    > Geert Uytterhoeven wrote:
    > > On Fri, 17 Oct 2008, Phillip Lougher wrote:
    > > > --- /dev/null
    > > > +++ b/fs/squashfs/namei.c

    > >
    > > > +static int get_dir_index_using_name(struct super_block *s,
    > > > + long long *next_block, unsigned int *next_offset,
    > > > + long long index_start, unsigned int index_offset,
    > > > + int i_count, const char *name, int len)
    > > > +{
    > > > + struct squashfs_sb_info *msblk = s->s_fs_info;
    > > > + int i, size, length = 0;
    > > > + struct squashfs_dir_index *index;
    > > > + char *str;
    > > > +
    > > > + TRACE("Entered get_dir_index_using_name, i_count %d\n", i_count);
    > > > +
    > > > + str = kmalloc(sizeof(*index) + (SQUASHFS_NAME_LEN + 1) * 2,
    > > > GFP_KERNEL);
    > > > + if (str == NULL) {
    > > > + ERROR("Failed to allocate squashfs_dir_index\n");
    > > > + goto out;
    > > > + }
    > > > +
    > > > + index = (struct squashfs_dir_index *) (str + SQUASHFS_NAME_LEN + 1);

    > >
    > > As str has been returned by kmalloc(), and SQUASHFS_NAME_LEN is equal to
    > > 256,
    > > `str + SQUASHFS_NAME_LEN + 1` is an odd address.
    > >

    > [..]
    > > > + size = le32_to_cpu(index->size) + 1;

    > > ^^^^^^^^^^^

    > [.]
    > > Hence accessing multi-byte fields in struct squashfs_dir_index causes
    > > unaligned
    > > accesses, which are emulated on some architectures (e.g. on MIPS).
    > >
    > > Use get_unaligned_le32() for unaligned accesses.

    >
    > How about aligning it properly in the first place instead?
    > Three ways:
    >
    > 1) reordering index and str here, so that index comes first,
    > str next.
    >
    > 2) using another constant instead of +1
    >
    > 3) using separate allocations for separate objects.


    You're right.

    Somehow I was convinced this was part of the on-disk layout, so it could not be
    changed. But that's not the case...

    With kind regards,

    Geert Uytterhoeven
    Software Architect

    Sony Techsoft Centre Europe
    The Corporate Village · Da Vincilaan 7-D1 · B-1935 Zaventem · Belgium

    Phone: +32 (0)2 700 8453
    Fax: +32 (0)2 700 8622
    E-mail: Geert.Uytterhoeven@sonycom.com
    Internet: http://www.sony-europe.com/

    A division of Sony Europe (Belgium) N.V.
    VAT BE 0413.825.160 · RPR Brussels
    Fortis · BIC GEBABEBB · IBAN BE41293037680010

+ Reply to Thread