Date: Thu, 17 Mar 2016 19:28:15 +0000 (UTC) From: "Pedro F. Giffuni" <pfg@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-stable@freebsd.org, svn-src-stable-10@freebsd.org Subject: svn commit: r296992 - in stable/10/sys: conf fs/ext2fs modules/ext2fs Message-ID: <201603171928.u2HJSFBj029325@repo.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: pfg Date: Thu Mar 17 19:28:15 2016 New Revision: 296992 URL: https://svnweb.freebsd.org/changeset/base/296992 Log: MFC r294504, r294652, r294653, r294655: ext2fs: Bring back the htree dir_index implementation. The htree dir_index is perhaps one of the most characteristic features of the linux ext3 implementation. It was removed in r281670, due to repeated bug reports. Damjan Jovanic detected and fixed three bugs and did some stress testing by building Apache OpenOffice on top of it so it is now in good shape to bring back. Differential Revision: https://reviews.freebsd.org/D5007 Submitted by: Damjan Jovanovic Reviewed by: pfg RelNotes: yes Added: stable/10/sys/fs/ext2fs/ext2_hash.c - copied unchanged from r294504, head/sys/fs/ext2fs/ext2_hash.c stable/10/sys/fs/ext2fs/ext2_htree.c - copied, changed from r294504, head/sys/fs/ext2fs/ext2_htree.c Modified: stable/10/sys/conf/files stable/10/sys/fs/ext2fs/ext2_alloc.c stable/10/sys/fs/ext2fs/ext2_dinode.h stable/10/sys/fs/ext2fs/ext2_dir.h stable/10/sys/fs/ext2fs/ext2_extern.h stable/10/sys/fs/ext2fs/ext2_inode_cnv.c stable/10/sys/fs/ext2fs/ext2_lookup.c stable/10/sys/fs/ext2fs/ext2_vfsops.c stable/10/sys/fs/ext2fs/ext2fs.h stable/10/sys/fs/ext2fs/inode.h stable/10/sys/modules/ext2fs/Makefile Directory Properties: stable/10/ (props changed) Modified: stable/10/sys/conf/files ============================================================================== --- stable/10/sys/conf/files Thu Mar 17 19:01:44 2016 (r296991) +++ stable/10/sys/conf/files Thu Mar 17 19:28:15 2016 (r296992) @@ -2946,6 +2946,8 @@ fs/ext2fs/ext2_bmap.c optional ext2fs fs/ext2fs/ext2_extents.c optional ext2fs fs/ext2fs/ext2_inode.c optional ext2fs fs/ext2fs/ext2_inode_cnv.c optional ext2fs +fs/ext2fs/ext2_hash.c optional ext2fs +fs/ext2fs/ext2_htree.c optional ext2fs fs/ext2fs/ext2_lookup.c optional ext2fs fs/ext2fs/ext2_subr.c optional ext2fs fs/ext2fs/ext2_vfsops.c optional ext2fs Modified: stable/10/sys/fs/ext2fs/ext2_alloc.c ============================================================================== --- stable/10/sys/fs/ext2fs/ext2_alloc.c Thu Mar 17 19:01:44 2016 (r296991) +++ stable/10/sys/fs/ext2fs/ext2_alloc.c Thu Mar 17 19:28:15 2016 (r296992) @@ -393,6 +393,7 @@ ext2_valloc(struct vnode *pvp, int mode, * Linux doesn't read the old inode in when it is allocating a * new one. I will set at least i_size and i_blocks to zero. */ + ip->i_flag = 0; ip->i_size = 0; ip->i_blocks = 0; ip->i_mode = 0; Modified: stable/10/sys/fs/ext2fs/ext2_dinode.h ============================================================================== --- stable/10/sys/fs/ext2fs/ext2_dinode.h Thu Mar 17 19:01:44 2016 (r296991) +++ stable/10/sys/fs/ext2fs/ext2_dinode.h Thu Mar 17 19:28:15 2016 (r296992) @@ -51,7 +51,7 @@ /* * Inode flags * The system supports EXT2_IMMUTABLE, EXT2_APPEND and EXT2_NODUMP flags. - * The current implementation also uses EXT4_INDEX, EXT4_EXTENTS and + * The current implementation also uses EXT3_INDEX, EXT4_EXTENTS and * EXT4_HUGE_FILE with some restrictions, imposed the lack of write * support. */ @@ -63,7 +63,7 @@ #define EXT2_APPEND 0x00000020 /* Writes to file may only append */ #define EXT2_NODUMP 0x00000040 /* Do not dump file */ #define EXT2_NOATIME 0x00000080 /* Do not update atime */ -#define EXT4_INDEX 0x00001000 /* Hash-indexed directory */ +#define EXT3_INDEX 0x00001000 /* Hash-indexed directory */ #define EXT4_IMAGIC 0x00002000 /* AFS directory */ #define EXT4_JOURNAL_DATA 0x00004000 /* File data should be journaled */ #define EXT4_NOTAIL 0x00008000 /* File tail should not be merged */ Modified: stable/10/sys/fs/ext2fs/ext2_dir.h ============================================================================== --- stable/10/sys/fs/ext2fs/ext2_dir.h Thu Mar 17 19:01:44 2016 (r296991) +++ stable/10/sys/fs/ext2fs/ext2_dir.h Thu Mar 17 19:28:15 2016 (r296992) @@ -40,6 +40,21 @@ struct ext2fs_direct { uint16_t e2d_namlen; /* length of string in e2d_name */ char e2d_name[EXT2FS_MAXNAMLEN];/* name with length<=EXT2FS_MAXNAMLEN */ }; + +enum slotstatus { + NONE, + COMPACT, + FOUND +}; + +struct ext2fs_searchslot { + enum slotstatus slotstatus; + doff_t slotoffset; /* offset of area with free space */ + int slotsize; /* size of area at slotoffset */ + int slotfreespace; /* amount of space free in slot */ + int slotneeded; /* sizeof the entry we are seeking */ +}; + /* * The new version of the directory entry. Since EXT2 structures are * stored in intel byte order, and the name_len field could never be Modified: stable/10/sys/fs/ext2fs/ext2_extern.h ============================================================================== --- stable/10/sys/fs/ext2fs/ext2_extern.h Thu Mar 17 19:01:44 2016 (r296991) +++ stable/10/sys/fs/ext2fs/ext2_extern.h Thu Mar 17 19:28:15 2016 (r296992) @@ -40,12 +40,15 @@ #define _FS_EXT2FS_EXT2_EXTERN_H_ struct ext2fs_dinode; +struct ext2fs_direct_2; +struct ext2fs_searchslot; struct indir; struct inode; struct mount; struct vfsconf; struct vnode; +int ext2_add_entry(struct vnode *, struct ext2fs_direct_2 *); int ext2_alloc(struct inode *, daddr_t, e4fs_daddr_t, int, struct ucred *, e4fs_daddr_t *); int ext2_balloc(struct inode *, @@ -83,6 +86,18 @@ int ext2_dirempty(struct inode *, ino_t, int ext2_checkpath(struct inode *, struct inode *, struct ucred *); int cg_has_sb(int i); int ext2_inactive(struct vop_inactive_args *); +int ext2_htree_add_entry(struct vnode *, struct ext2fs_direct_2 *, + struct componentname *); +int ext2_htree_create_index(struct vnode *, struct componentname *, + struct ext2fs_direct_2 *); +int ext2_htree_has_idx(struct inode *); +int ext2_htree_hash(const char *, int, uint32_t *, int, uint32_t *, + uint32_t *); +int ext2_htree_lookup(struct inode *, const char *, int, struct buf **, + int *, doff_t *, doff_t *, doff_t *, struct ext2fs_searchslot *); +int ext2_search_dirblock(struct inode *, void *, int *, const char *, int, + int *, doff_t *, doff_t *, doff_t *, struct ext2fs_searchslot *); + /* Flags to low-level allocation routines. * The low 16-bits are reserved for IO_ flags from vnode.h. Copied: stable/10/sys/fs/ext2fs/ext2_hash.c (from r294504, head/sys/fs/ext2fs/ext2_hash.c) ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ stable/10/sys/fs/ext2fs/ext2_hash.c Thu Mar 17 19:28:15 2016 (r296992, copy of r294504, head/sys/fs/ext2fs/ext2_hash.c) @@ -0,0 +1,316 @@ +/*- + * Copyright (c) 2010, 2013 Zheng Liu <lz@freebsd.org> + * Copyright (c) 2012, Vyacheslav Matyushin + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * $FreeBSD$ + */ + +/* + * The following notice applies to the code in ext2_half_md4(): + * + * Copyright (C) 1990-2, RSA Data Security, Inc. All rights reserved. + * + * License to copy and use this software is granted provided that it + * is identified as the "RSA Data Security, Inc. MD4 Message-Digest + * Algorithm" in all material mentioning or referencing this software + * or this function. + * + * License is also granted to make and use derivative works provided + * that such works are identified as "derived from the RSA Data + * Security, Inc. MD4 Message-Digest Algorithm" in all material + * mentioning or referencing the derived work. + * + * RSA Data Security, Inc. makes no representations concerning either + * the merchantability of this software or the suitability of this + * software for any particular purpose. It is provided "as is" + * without express or implied warranty of any kind. + * + * These notices must be retained in any copies of any part of this + * documentation and/or software. + */ + +#include <sys/param.h> +#include <sys/systm.h> +#include <sys/conf.h> +#include <sys/vnode.h> +#include <sys/stat.h> +#include <sys/mount.h> + +#include <fs/ext2fs/htree.h> +#include <fs/ext2fs/inode.h> +#include <fs/ext2fs/ext2_mount.h> +#include <fs/ext2fs/ext2_extern.h> + +/* F, G, and H are MD4 functions */ +#define F(x, y, z) (((x) & (y)) | ((~x) & (z))) +#define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z))) +#define H(x, y, z) ((x) ^ (y) ^ (z)) + +/* ROTATE_LEFT rotates x left n bits */ +#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32 - (n)))) + +/* + * FF, GG, and HH are transformations for rounds 1, 2, and 3. + * Rotation is separated from addition to prevent recomputation. + */ +#define FF(a, b, c, d, x, s) { \ + (a) += F ((b), (c), (d)) + (x); \ + (a) = ROTATE_LEFT ((a), (s)); \ +} + +#define GG(a, b, c, d, x, s) { \ + (a) += G ((b), (c), (d)) + (x) + (uint32_t)0x5A827999; \ + (a) = ROTATE_LEFT ((a), (s)); \ +} + +#define HH(a, b, c, d, x, s) { \ + (a) += H ((b), (c), (d)) + (x) + (uint32_t)0x6ED9EBA1; \ + (a) = ROTATE_LEFT ((a), (s)); \ +} + +/* + * MD4 basic transformation. It transforms state based on block. + * + * This is a half md4 algorithm since Linux uses this algorithm for dir + * index. This function is derived from the RSA Data Security, Inc. MD4 + * Message-Digest Algorithm and was modified as necessary. + * + * The return value of this function is uint32_t in Linux, but actually we don't + * need to check this value, so in our version this function doesn't return any + * value. + */ +static void +ext2_half_md4(uint32_t hash[4], uint32_t data[8]) +{ + uint32_t a = hash[0], b = hash[1], c = hash[2], d = hash[3]; + + /* Round 1 */ + FF(a, b, c, d, data[0], 3); + FF(d, a, b, c, data[1], 7); + FF(c, d, a, b, data[2], 11); + FF(b, c, d, a, data[3], 19); + FF(a, b, c, d, data[4], 3); + FF(d, a, b, c, data[5], 7); + FF(c, d, a, b, data[6], 11); + FF(b, c, d, a, data[7], 19); + + /* Round 2 */ + GG(a, b, c, d, data[1], 3); + GG(d, a, b, c, data[3], 5); + GG(c, d, a, b, data[5], 9); + GG(b, c, d, a, data[7], 13); + GG(a, b, c, d, data[0], 3); + GG(d, a, b, c, data[2], 5); + GG(c, d, a, b, data[4], 9); + GG(b, c, d, a, data[6], 13); + + /* Round 3 */ + HH(a, b, c, d, data[3], 3); + HH(d, a, b, c, data[7], 9); + HH(c, d, a, b, data[2], 11); + HH(b, c, d, a, data[6], 15); + HH(a, b, c, d, data[1], 3); + HH(d, a, b, c, data[5], 9); + HH(c, d, a, b, data[0], 11); + HH(b, c, d, a, data[4], 15); + + hash[0] += a; + hash[1] += b; + hash[2] += c; + hash[3] += d; +} + +/* + * Tiny Encryption Algorithm. + */ +static void +ext2_tea(uint32_t hash[4], uint32_t data[8]) +{ + uint32_t tea_delta = 0x9E3779B9; + uint32_t sum; + uint32_t x = hash[0], y = hash[1]; + int n = 16; + int i = 1; + + while (n-- > 0) { + sum = i * tea_delta; + x += ((y << 4) + data[0]) ^ (y + sum) ^ ((y >> 5) + data[1]); + y += ((x << 4) + data[2]) ^ (x + sum) ^ ((x >> 5) + data[3]); + i++; + } + + hash[0] += x; + hash[1] += y; +} + +static uint32_t +ext2_legacy_hash(const char *name, int len, int unsigned_char) +{ + uint32_t h0, h1 = 0x12A3FE2D, h2 = 0x37ABE8F9; + uint32_t multi = 0x6D22F5; + const unsigned char *uname = (const unsigned char *)name; + const signed char *sname = (const signed char *)name; + int val, i; + + for (i = 0; i < len; i++) { + if (unsigned_char) + val = (u_int)*uname++; + else + val = (int)*sname++; + + h0 = h2 + (h1 ^ (val * multi)); + if (h0 & 0x80000000) + h0 -= 0x7FFFFFFF; + h2 = h1; + h1 = h0; + } + + return (h1 << 1); +} + +static void +ext2_prep_hashbuf(const char *src, int slen, uint32_t *dst, int dlen, + int unsigned_char) +{ + uint32_t padding = slen | (slen << 8) | (slen << 16) | (slen << 24); + uint32_t buf_val; + const unsigned char *ubuf = (const unsigned char *)src; + const signed char *sbuf = (const signed char *)src; + int len, i; + int buf_byte; + + if (slen > dlen) + len = dlen; + else + len = slen; + + buf_val = padding; + + for (i = 0; i < len; i++) { + if (unsigned_char) + buf_byte = (u_int)ubuf[i]; + else + buf_byte = (int)sbuf[i]; + + if ((i % 4) == 0) + buf_val = padding; + + buf_val <<= 8; + buf_val += buf_byte; + + if ((i % 4) == 3) { + *dst++ = buf_val; + dlen -= sizeof(uint32_t); + buf_val = padding; + } + } + + dlen -= sizeof(uint32_t); + if (dlen >= 0) + *dst++ = buf_val; + + dlen -= sizeof(uint32_t); + while (dlen >= 0) { + *dst++ = padding; + dlen -= sizeof(uint32_t); + } +} + +int +ext2_htree_hash(const char *name, int len, + uint32_t *hash_seed, int hash_version, + uint32_t *hash_major, uint32_t *hash_minor) +{ + uint32_t hash[4]; + uint32_t data[8]; + uint32_t major = 0, minor = 0; + int unsigned_char = 0; + + if (!name || !hash_major) + return (-1); + + if (len < 1 || len > 255) + goto error; + + hash[0] = 0x67452301; + hash[1] = 0xEFCDAB89; + hash[2] = 0x98BADCFE; + hash[3] = 0x10325476; + + if (hash_seed) + memcpy(hash, hash_seed, sizeof(hash)); + + switch (hash_version) { + case EXT2_HTREE_TEA_UNSIGNED: + unsigned_char = 1; + /* FALLTHROUGH */ + case EXT2_HTREE_TEA: + while (len > 0) { + ext2_prep_hashbuf(name, len, data, 16, unsigned_char); + ext2_tea(hash, data); + len -= 16; + name += 16; + } + major = hash[0]; + minor = hash[1]; + break; + case EXT2_HTREE_LEGACY_UNSIGNED: + unsigned_char = 1; + /* FALLTHROUGH */ + case EXT2_HTREE_LEGACY: + major = ext2_legacy_hash(name, len, unsigned_char); + break; + case EXT2_HTREE_HALF_MD4_UNSIGNED: + unsigned_char = 1; + /* FALLTHROUGH */ + case EXT2_HTREE_HALF_MD4: + while (len > 0) { + ext2_prep_hashbuf(name, len, data, 32, unsigned_char); + ext2_half_md4(hash, data); + len -= 32; + name += 32; + } + major = hash[1]; + minor = hash[2]; + break; + default: + goto error; + } + + major &= ~1; + if (major == (EXT2_HTREE_EOF << 1)) + major = (EXT2_HTREE_EOF - 1) << 1; + *hash_major = major; + if (hash_minor) + *hash_minor = minor; + + return (0); + +error: + *hash_major = 0; + if (hash_minor) + *hash_minor = 0; + return (-1); +} Copied and modified: stable/10/sys/fs/ext2fs/ext2_htree.c (from r294504, head/sys/fs/ext2fs/ext2_htree.c) ============================================================================== --- head/sys/fs/ext2fs/ext2_htree.c Thu Jan 21 14:50:28 2016 (r294504, copy source) +++ stable/10/sys/fs/ext2fs/ext2_htree.c Thu Mar 17 19:28:15 2016 (r296992) @@ -90,7 +90,7 @@ int ext2_htree_has_idx(struct inode *ip) { if (EXT2_HAS_COMPAT_FEATURE(ip->i_e2fs, EXT2F_COMPAT_DIRHASHINDEX) && - ip->i_flag & IN_E4INDEX) + ip->i_flag & IN_E3INDEX) return (1); else return (0); @@ -653,7 +653,7 @@ ext2_htree_create_index(struct vnode *vp ((char *)ep + ep->e2d_reclen); ep->e2d_reclen = buf1 + blksize - (char *)ep; - dp->i_flag |= IN_E4INDEX; + dp->i_flag |= IN_E3INDEX; /* * Initialize index root. Modified: stable/10/sys/fs/ext2fs/ext2_inode_cnv.c ============================================================================== --- stable/10/sys/fs/ext2fs/ext2_inode_cnv.c Thu Mar 17 19:01:44 2016 (r296991) +++ stable/10/sys/fs/ext2fs/ext2_inode_cnv.c Thu Mar 17 19:28:15 2016 (r296992) @@ -110,7 +110,7 @@ ext2_ei2i(struct ext2fs_dinode *ei, stru ip->i_flags |= (ei->e2di_flags & EXT2_APPEND) ? SF_APPEND : 0; ip->i_flags |= (ei->e2di_flags & EXT2_IMMUTABLE) ? SF_IMMUTABLE : 0; ip->i_flags |= (ei->e2di_flags & EXT2_NODUMP) ? UF_NODUMP : 0; - ip->i_flag |= (ei->e2di_flags & EXT4_INDEX) ? IN_E4INDEX : 0; + ip->i_flag |= (ei->e2di_flags & EXT3_INDEX) ? IN_E3INDEX : 0; ip->i_flag |= (ei->e2di_flags & EXT4_EXTENTS) ? IN_E4EXTENTS : 0; ip->i_blocks = ei->e2di_nblock; if (E2DI_HAS_HUGE_FILE(ip)) { @@ -160,7 +160,7 @@ ext2_i2ei(struct inode *ip, struct ext2f ei->e2di_flags |= (ip->i_flags & SF_APPEND) ? EXT2_APPEND: 0; ei->e2di_flags |= (ip->i_flags & SF_IMMUTABLE) ? EXT2_IMMUTABLE: 0; ei->e2di_flags |= (ip->i_flags & UF_NODUMP) ? EXT2_NODUMP: 0; - ei->e2di_flags |= (ip->i_flag & IN_E4INDEX) ? EXT4_INDEX: 0; + ei->e2di_flags |= (ip->i_flag & IN_E3INDEX) ? EXT3_INDEX: 0; ei->e2di_flags |= (ip->i_flag & IN_E4EXTENTS) ? EXT4_EXTENTS: 0; ei->e2di_nblock = ip->i_blocks & 0xffffffff; ei->e2di_nblock_high = ip->i_blocks >> 32 & 0xffff; Modified: stable/10/sys/fs/ext2fs/ext2_lookup.c ============================================================================== --- stable/10/sys/fs/ext2fs/ext2_lookup.c Thu Mar 17 19:01:44 2016 (r296991) +++ stable/10/sys/fs/ext2fs/ext2_lookup.c Thu Mar 17 19:28:15 2016 (r296992) @@ -113,9 +113,19 @@ static u_char dt_to_ext2_ft[] = { static int ext2_dirbadentry(struct vnode *dp, struct ext2fs_direct_2 *de, int entryoffsetinblock); +static int ext2_is_dot_entry(struct componentname *cnp); static int ext2_lookup_ino(struct vnode *vdp, struct vnode **vpp, struct componentname *cnp, ino_t *dd_ino); +static int +ext2_is_dot_entry(struct componentname *cnp) +{ + if (cnp->cn_namelen <= 2 && cnp->cn_nameptr[0] == '.' && + (cnp->cn_nameptr[1] == '.' || cnp->cn_nameptr[1] == '\0')) + return (1); + return (0); +} + /* * Vnode op for reading directories. */ @@ -296,13 +306,9 @@ ext2_lookup_ino(struct vnode *vdp, struc struct buf *bp; /* a buffer of directory entries */ struct ext2fs_direct_2 *ep; /* the current directory entry */ int entryoffsetinblock; /* offset of ep in bp's buffer */ - enum {NONE, COMPACT, FOUND} slotstatus; - doff_t slotoffset; /* offset of area with free space */ + struct ext2fs_searchslot ss; doff_t i_diroff; /* cached i_diroff value */ doff_t i_offset; /* cached i_offset value */ - int slotsize; /* size of area at slotoffset */ - int slotfreespace; /* amount of space free in slot */ - int slotneeded; /* size of the entry we're seeking */ int numdirpasses; /* strategy for directory search */ doff_t endsearch; /* offset to end directory search */ doff_t prevoff; /* prev entry dp->i_offset */ @@ -310,12 +316,13 @@ ext2_lookup_ino(struct vnode *vdp, struc struct vnode *tdp; /* returned by VFS_VGET */ doff_t enduseful; /* pointer past last used dir slot */ u_long bmask; /* block offset mask */ - int namlen, error; + int error; struct ucred *cred = cnp->cn_cred; int flags = cnp->cn_flags; int nameiop = cnp->cn_nameiop; ino_t ino, ino1; int ltype; + int entry_found = 0; int DIRBLKSIZ = VTOI(vdp)->i_e2fs->e2fs_bsize; @@ -326,31 +333,57 @@ ext2_lookup_ino(struct vnode *vdp, struc bmask = VFSTOEXT2(vdp->v_mount)->um_mountp->mnt_stat.f_iosize - 1; restart: bp = NULL; - slotoffset = -1; + ss.slotoffset = -1; /* * We now have a segment name to search for, and a directory to search. - */ - - /* + * * Suppress search for slots unless creating * file and at end of pathname, in which case * we watch for a place to put the new file in * case it doesn't already exist. */ i_diroff = dp->i_diroff; - slotstatus = FOUND; - slotfreespace = slotsize = slotneeded = 0; + ss.slotstatus = FOUND; + ss.slotfreespace = ss.slotsize = ss.slotneeded = 0; if ((nameiop == CREATE || nameiop == RENAME) && (flags & ISLASTCN)) { - slotstatus = NONE; - slotneeded = EXT2_DIR_REC_LEN(cnp->cn_namelen); + ss.slotstatus = NONE; + ss.slotneeded = EXT2_DIR_REC_LEN(cnp->cn_namelen); /* was - slotneeded = (sizeof(struct direct) - MAXNAMLEN + + ss.slotneeded = (sizeof(struct direct) - MAXNAMLEN + cnp->cn_namelen + 3) &~ 3; */ } /* + * Try to lookup dir entry using htree directory index. + * + * If we got an error or we want to find '.' or '..' entry, + * we will fall back to linear search. + */ + if (!ext2_is_dot_entry(cnp) && ext2_htree_has_idx(dp)) { + numdirpasses = 1; + entryoffsetinblock = 0; + switch (ext2_htree_lookup(dp, cnp->cn_nameptr, cnp->cn_namelen, + &bp, &entryoffsetinblock, &i_offset, &prevoff, + &enduseful, &ss)) { + case 0: + ep = (struct ext2fs_direct_2 *)((char *)bp->b_data + + (i_offset & bmask)); + goto foundentry; + case ENOENT: + i_offset = roundup2(dp->i_size, DIRBLKSIZ); + goto notfound; + default: + /* + * Something failed; just fallback to do a linear + * search. + */ + break; + } + } + + /* * If there is cached information on a previous search of * this directory, pick up where we last left off. * We cache only lookups as these are the most common @@ -384,96 +417,38 @@ searchloop: /* * If necessary, get the next directory block. */ - if ((i_offset & bmask) == 0) { - if (bp != NULL) - brelse(bp); - if ((error = - ext2_blkatoff(vdp, (off_t)i_offset, NULL, - &bp)) != 0) - return (error); - entryoffsetinblock = 0; - } + if (bp != NULL) + brelse(bp); + error = ext2_blkatoff(vdp, (off_t)i_offset, NULL, &bp); + if (error != 0) + return (error); + entryoffsetinblock = 0; /* * If still looking for a slot, and at a DIRBLKSIZE * boundary, have to start looking for free space again. */ - if (slotstatus == NONE && + if (ss.slotstatus == NONE && (entryoffsetinblock & (DIRBLKSIZ - 1)) == 0) { - slotoffset = -1; - slotfreespace = 0; + ss.slotoffset = -1; + ss.slotfreespace = 0; } - /* - * Get pointer to next entry. - * Full validation checks are slow, so we only check - * enough to insure forward progress through the - * directory. Complete checks can be run by setting - * "vfs.e2fs.dirchk" to be true. - */ - ep = (struct ext2fs_direct_2 *) - ((char *)bp->b_data + entryoffsetinblock); - if (ep->e2d_reclen == 0 || - (dirchk && ext2_dirbadentry(vdp, ep, entryoffsetinblock))) { - int i; - ext2_dirbad(dp, i_offset, "mangled entry"); - i = DIRBLKSIZ - (entryoffsetinblock & (DIRBLKSIZ - 1)); - i_offset += i; - entryoffsetinblock += i; - continue; - } - - /* - * If an appropriate sized slot has not yet been found, - * check to see if one is available. Also accumulate space - * in the current block so that we can determine if - * compaction is viable. - */ - if (slotstatus != FOUND) { - int size = ep->e2d_reclen; - - if (ep->e2d_ino != 0) - size -= EXT2_DIR_REC_LEN(ep->e2d_namlen); - if (size > 0) { - if (size >= slotneeded) { - slotstatus = FOUND; - slotoffset = i_offset; - slotsize = ep->e2d_reclen; - } else if (slotstatus == NONE) { - slotfreespace += size; - if (slotoffset == -1) - slotoffset = i_offset; - if (slotfreespace >= slotneeded) { - slotstatus = COMPACT; - slotsize = i_offset + - ep->e2d_reclen - slotoffset; - } - } - } + error = ext2_search_dirblock(dp, bp->b_data, &entry_found, + cnp->cn_nameptr, cnp->cn_namelen, + &entryoffsetinblock, &i_offset, &prevoff, + &enduseful, &ss); + if (error != 0) { + brelse(bp); + return (error); } - - /* - * Check for a name match. - */ - if (ep->e2d_ino) { - namlen = ep->e2d_namlen; - if (namlen == cnp->cn_namelen && - !bcmp(cnp->cn_nameptr, ep->e2d_name, - (unsigned)namlen)) { - /* - * Save directory entry's inode number and - * reclen in ndp->ni_ufs area, and release - * directory buffer. - */ - ino = ep->e2d_ino; - goto found; - } + if (entry_found) { + ep = (struct ext2fs_direct_2 *)((char *)bp->b_data + + (entryoffsetinblock & bmask)); +foundentry: + ino = ep->e2d_ino; + goto found; } - prevoff = i_offset; - i_offset += ep->e2d_reclen; - entryoffsetinblock += ep->e2d_reclen; - if (ep->e2d_ino) - enduseful = i_offset; } -/* notfound: */ +notfound: /* * If we started in the middle of the directory and failed * to find our target, we must check the beginning as well. @@ -508,15 +483,15 @@ searchloop: * can be put in the range from dp->i_offset to * dp->i_offset + dp->i_count. */ - if (slotstatus == NONE) { + if (ss.slotstatus == NONE) { dp->i_offset = roundup2(dp->i_size, DIRBLKSIZ); dp->i_count = 0; enduseful = dp->i_offset; } else { - dp->i_offset = slotoffset; - dp->i_count = slotsize; - if (enduseful < slotoffset + slotsize) - enduseful = slotoffset + slotsize; + dp->i_offset = ss.slotoffset; + dp->i_count = ss.slotsize; + if (enduseful < ss.slotoffset + ss.slotsize) + enduseful = ss.slotoffset + ss.slotsize; } dp->i_endoff = roundup2(enduseful, DIRBLKSIZ); /* @@ -722,6 +697,102 @@ found: return (0); } +int +ext2_search_dirblock(struct inode *ip, void *data, int *foundp, + const char *name, int namelen, int *entryoffsetinblockp, + doff_t *offp, doff_t *prevoffp, doff_t *endusefulp, + struct ext2fs_searchslot *ssp) +{ + struct vnode *vdp; + struct ext2fs_direct_2 *ep, *top; + uint32_t bsize = ip->i_e2fs->e2fs_bsize; + int offset = *entryoffsetinblockp; + int namlen; + + vdp = ITOV(ip); + + ep = (struct ext2fs_direct_2 *)((char *)data + offset); + top = (struct ext2fs_direct_2 *)((char *)data + + bsize - EXT2_DIR_REC_LEN(0)); + + while (ep < top) { + /* + * Full validation checks are slow, so we only check + * enough to insure forward progress through the + * directory. Complete checks can be run by setting + * "vfs.e2fs.dirchk" to be true. + */ + if (ep->e2d_reclen == 0 || + (dirchk && ext2_dirbadentry(vdp, ep, offset))) { + int i; + ext2_dirbad(ip, *offp, "mangled entry"); + i = bsize - (offset & (bsize - 1)); + *offp += i; + offset += i; + continue; + } + + /* + * If an appropriate sized slot has not yet been found, + * check to see if one is available. Also accumulate space + * in the current block so that we can determine if + * compaction is viable. + */ + if (ssp->slotstatus != FOUND) { + int size = ep->e2d_reclen; + + if (ep->e2d_ino != 0) + size -= EXT2_DIR_REC_LEN(ep->e2d_namlen); + if (size > 0) { + if (size >= ssp->slotneeded) { + ssp->slotstatus = FOUND; + ssp->slotoffset = *offp; + ssp->slotsize = ep->e2d_reclen; + } else if (ssp->slotstatus == NONE) { + ssp->slotfreespace += size; + if (ssp->slotoffset == -1) + ssp->slotoffset = *offp; + if (ssp->slotfreespace >= ssp->slotneeded) { + ssp->slotstatus = COMPACT; + ssp->slotsize = *offp + + ep->e2d_reclen - + ssp->slotoffset; + } + } + } + } + + /* + * Check for a name match. + */ + if (ep->e2d_ino) { + namlen = ep->e2d_namlen; + if (namlen == namelen && + !bcmp(name, ep->e2d_name, (unsigned)namlen)) { + /* + * Save directory entry's inode number and + * reclen in ndp->ni_ufs area, and release + * directory buffer. + */ + *foundp = 1; + return (0); + } + } + *prevoffp = *offp; + *offp += ep->e2d_reclen; + offset += ep->e2d_reclen; + *entryoffsetinblockp = offset; + if (ep->e2d_ino) + *endusefulp = *offp; + /* + * Get pointer to the next entry. + */ + ep = (struct ext2fs_direct_2 *)((char *)data + offset); + } + + return (0); +} + void ext2_dirbad(struct inode *ip, doff_t offset, char *how) { @@ -789,16 +860,12 @@ ext2_dirbadentry(struct vnode *dp, struc int ext2_direnter(struct inode *ip, struct vnode *dvp, struct componentname *cnp) { - struct ext2fs_direct_2 *ep, *nep; struct inode *dp; - struct buf *bp; struct ext2fs_direct_2 newdir; struct iovec aiov; struct uio auio; - u_int dsize; - int error, loc, newentrysize, spacefree; - char *dirbuf; - int DIRBLKSIZ = ip->i_e2fs->e2fs_bsize; + int error, newentrysize; + int DIRBLKSIZ = ip->i_e2fs->e2fs_bsize; #ifdef INVARIANTS @@ -815,6 +882,28 @@ ext2_direnter(struct inode *ip, struct v newdir.e2d_type = EXT2_FT_UNKNOWN; bcopy(cnp->cn_nameptr, newdir.e2d_name, (unsigned)cnp->cn_namelen + 1); newentrysize = EXT2_DIR_REC_LEN(newdir.e2d_namlen); + + if (ext2_htree_has_idx(dp)) { + error = ext2_htree_add_entry(dvp, &newdir, cnp); + if (error) { + dp->i_flag &= ~IN_E3INDEX; + dp->i_flag |= IN_CHANGE | IN_UPDATE; + } + return (error); + } + + if (EXT2_HAS_COMPAT_FEATURE(ip->i_e2fs, EXT2F_COMPAT_DIRHASHINDEX) && + !ext2_htree_has_idx(dp)) { + if ((dp->i_size / DIRBLKSIZ) == 1 && + dp->i_offset == DIRBLKSIZ) { + /* + * Making indexed directory when one block is not + * enough to save all entries. + */ + return ext2_htree_create_index(dvp, cnp, &newdir); + } + } + if (dp->i_count == 0) { /* * If dp->i_count is 0, then namei could find no @@ -846,6 +935,29 @@ ext2_direnter(struct inode *ip, struct v return (error); } + error = ext2_add_entry(dvp, &newdir); + if (!error && dp->i_endoff && dp->i_endoff < dp->i_size) + error = ext2_truncate(dvp, (off_t)dp->i_endoff, IO_SYNC, + cnp->cn_cred, cnp->cn_thread); + return (error); +} + +/* + * Insert an entry into the directory block. + * Compact the contents. + */ +int +ext2_add_entry(struct vnode *dvp, struct ext2fs_direct_2 *entry) +{ + struct ext2fs_direct_2 *ep, *nep; + struct inode *dp; + struct buf *bp; + u_int dsize; + int error, loc, newentrysize, spacefree; + char *dirbuf; + + dp = VTOI(dvp); + /* * If dp->i_count is non-zero, then namei found space * for the new entry in the range dp->i_offset to @@ -877,6 +989,7 @@ ext2_direnter(struct inode *ip, struct v * dp->i_offset + dp->i_count would yield the * space. */ + newentrysize = EXT2_DIR_REC_LEN(entry->e2d_namlen); ep = (struct ext2fs_direct_2 *)dirbuf; dsize = EXT2_DIR_REC_LEN(ep->e2d_namlen); spacefree = ep->e2d_reclen - dsize; @@ -902,15 +1015,15 @@ ext2_direnter(struct inode *ip, struct v if (ep->e2d_ino == 0) { if (spacefree + dsize < newentrysize) panic("ext2_direnter: compact1"); - newdir.e2d_reclen = spacefree + dsize; + entry->e2d_reclen = spacefree + dsize; } else { if (spacefree < newentrysize) panic("ext2_direnter: compact2"); - newdir.e2d_reclen = spacefree; + entry->e2d_reclen = spacefree; ep->e2d_reclen = dsize; ep = (struct ext2fs_direct_2 *)((char *)ep + dsize); } - bcopy((caddr_t)&newdir, (caddr_t)ep, (u_int)newentrysize); + bcopy((caddr_t)entry, (caddr_t)ep, (u_int)newentrysize); if (DOINGASYNC(dvp)) { bdwrite(bp); error = 0; @@ -918,9 +1031,6 @@ ext2_direnter(struct inode *ip, struct v error = bwrite(bp); } dp->i_flag |= IN_CHANGE | IN_UPDATE; - if (!error && dp->i_endoff && dp->i_endoff < dp->i_size) - error = ext2_truncate(dvp, (off_t)dp->i_endoff, IO_SYNC, - cnp->cn_cred, cnp->cn_thread); return (error); } Modified: stable/10/sys/fs/ext2fs/ext2_vfsops.c ============================================================================== --- stable/10/sys/fs/ext2fs/ext2_vfsops.c Thu Mar 17 19:01:44 2016 (r296991) +++ stable/10/sys/fs/ext2fs/ext2_vfsops.c Thu Mar 17 19:28:15 2016 (r296992) @@ -399,8 +399,22 @@ compute_sb_data(struct vnode *devvp, str if (es->e2fs_rev == E2FS_REV0 || !EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_LARGEFILE)) fs->e2fs_maxfilesize = 0x7fffffff; - else - fs->e2fs_maxfilesize = 0x7fffffffffffffff; + else { + fs->e2fs_maxfilesize = 0xffffffffffff; + if (EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_HUGE_FILE)) + fs->e2fs_maxfilesize = 0x7fffffffffffffff; + } + if (es->e4fs_flags & E2FS_UNSIGNED_HASH) { + fs->e2fs_uhash = 3; + } else if ((es->e4fs_flags & E2FS_SIGNED_HASH) == 0) { +#ifdef __CHAR_UNSIGNED__ + es->e4fs_flags |= E2FS_UNSIGNED_HASH; + fs->e2fs_uhash = 3; +#else + es->e4fs_flags |= E2FS_SIGNED_HASH; +#endif + } + return (0); } Modified: stable/10/sys/fs/ext2fs/ext2fs.h ============================================================================== --- stable/10/sys/fs/ext2fs/ext2fs.h Thu Mar 17 19:01:44 2016 (r296991) +++ stable/10/sys/fs/ext2fs/ext2fs.h Thu Mar 17 19:28:15 2016 (r296992) @@ -147,6 +147,7 @@ struct m_ext2fs { int32_t e2fs_contigsumsize; /* size of cluster summary array */ int32_t *e2fs_maxcluster; /* max cluster in each cyl group */ struct csum *e2fs_clustersum; /* cluster summary in each cyl group */ + int32_t e2fs_uhash; /* 3 if hash should be signed, 0 if not */ }; /* cluster summary information */ @@ -213,6 +214,7 @@ struct csum { * - EXT2F_INCOMPAT_FLEX_BG * - EXT2F_INCOMPAT_META_BG */ +#define EXT2F_COMPAT_SUPP EXT2F_COMPAT_DIRHASHINDEX #define EXT2F_ROCOMPAT_SUPP (EXT2F_ROCOMPAT_SPARSESUPER | \ EXT2F_ROCOMPAT_LARGEFILE | \ EXT2F_ROCOMPAT_EXTRA_ISIZE) @@ -243,6 +245,12 @@ struct csum { #define E2FS_ISCLEAN 0x0001 /* Unmounted cleanly */ #define E2FS_ERRORS 0x0002 /* Errors detected */ +/* + * Filesystem miscellaneous flags + */ +#define E2FS_SIGNED_HASH 0x0001 +#define E2FS_UNSIGNED_HASH 0x0002 + /* ext2 file system block group descriptor */ struct ext2_gd { Modified: stable/10/sys/fs/ext2fs/inode.h ============================================================================== --- stable/10/sys/fs/ext2fs/inode.h Thu Mar 17 19:01:44 2016 (r296991) +++ stable/10/sys/fs/ext2fs/inode.h Thu Mar 17 19:28:15 2016 (r296992) @@ -157,7 +157,7 @@ struct inode { *** DIFF OUTPUT TRUNCATED AT 1000 LINES ***
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201603171928.u2HJSFBj029325>