Module Name: src
Committed By: christos
Date: Fri Jun 24 17:21:30 UTC 2016
Modified Files:
src/sys/ufs/ext2fs: ext2fs.h ext2fs_dir.h ext2fs_extern.h
ext2fs_lookup.c
Added Files:
src/sys/ufs/ext2fs: ext2fs_hash.c ext2fs_hash.h ext2fs_htree.c
ext2fs_htree.h
Log Message:
GSoC 2016 (Hrishikesh Goyal): Htree index support from FreeBSD
To generate a diff of this commit:
cvs rdiff -u -r1.37 -r1.38 src/sys/ufs/ext2fs/ext2fs.h
cvs rdiff -u -r1.19 -r1.20 src/sys/ufs/ext2fs/ext2fs_dir.h
cvs rdiff -u -r1.48 -r1.49 src/sys/ufs/ext2fs/ext2fs_extern.h
cvs rdiff -u -r0 -r1.1 src/sys/ufs/ext2fs/ext2fs_hash.c \
src/sys/ufs/ext2fs/ext2fs_hash.h src/sys/ufs/ext2fs/ext2fs_htree.c \
src/sys/ufs/ext2fs/ext2fs_htree.h
cvs rdiff -u -r1.79 -r1.80 src/sys/ufs/ext2fs/ext2fs_lookup.c
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/sys/ufs/ext2fs/ext2fs.h
diff -u src/sys/ufs/ext2fs/ext2fs.h:1.37 src/sys/ufs/ext2fs/ext2fs.h:1.38
--- src/sys/ufs/ext2fs/ext2fs.h:1.37 Fri Jun 3 11:35:48 2016
+++ src/sys/ufs/ext2fs/ext2fs.h Fri Jun 24 13:21:30 2016
@@ -1,4 +1,4 @@
-/* $NetBSD: ext2fs.h,v 1.37 2016/06/03 15:35:48 christos Exp $ */
+/* $NetBSD: ext2fs.h,v 1.38 2016/06/24 17:21:30 christos Exp $ */
/*
* Copyright (c) 1982, 1986, 1993
@@ -235,6 +235,7 @@ struct m_ext2fs {
u_char e2fs_fsmnt[MAXMNTLEN]; /* name mounted on */
int8_t e2fs_ronly; /* mounted read-only flag */
int8_t e2fs_fmod; /* super block modified flag */
+ int8_t e2fs_uhash; /* 3 if hash should be signed, 0 if not */
int32_t e2fs_bsize; /* block size */
int32_t e2fs_bshift; /* ``lblkno'' calc of logical blkno */
int32_t e2fs_bmask; /* ``blkoff'' calc of blk offsets */
@@ -331,6 +332,12 @@ struct m_ext2fs {
| EXT2F_INCOMPAT_EXTENTS)
/*
+ * Feature set definitions
+ */
+#define EXT2_HAS_COMPAT_FEATURE(sb, mask) \
+ ((sb)->e2fs.e2fs_features_compat & htole32(mask))
+
+/*
* Definitions of behavior on errors
*/
#define E2FS_BEH_CONTINUE 1 /* continue operation */
Index: src/sys/ufs/ext2fs/ext2fs_dir.h
diff -u src/sys/ufs/ext2fs/ext2fs_dir.h:1.19 src/sys/ufs/ext2fs/ext2fs_dir.h:1.20
--- src/sys/ufs/ext2fs/ext2fs_dir.h:1.19 Tue May 8 20:21:18 2012
+++ src/sys/ufs/ext2fs/ext2fs_dir.h Fri Jun 24 13:21:30 2016
@@ -1,4 +1,4 @@
-/* $NetBSD: ext2fs_dir.h,v 1.19 2012/05/09 00:21:18 riastradh Exp $ */
+/* $NetBSD: ext2fs_dir.h,v 1.20 2016/06/24 17:21:30 christos Exp $ */
/*
* Copyright (c) 1982, 1986, 1989, 1993
@@ -114,6 +114,20 @@ struct ext2fs_direct {
char e2d_name[EXT2FS_MAXNAMLEN];/* name with length<=EXT2FS_MAXNAMLEN */
};
+enum ext2fs_slotstatus {
+ NONE,
+ COMPACT,
+ FOUND
+};
+
+struct ext2fs_searchslot {
+ enum ext2fs_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 */
+};
+
/* Ext2 directory file types (not the same as FFS. Sigh.) */
#define EXT2_FT_UNKNOWN 0
#define EXT2_FT_REG_FILE 1
@@ -179,4 +193,14 @@ struct ext2fs_dirtemplate {
char dotdot_name[4]; /* ditto */
};
+/*
+ * EXT2_DIR_PAD defines the directory entries boundaries
+ *
+ * NOTE: It must be a multiple of 4
+ */
+#define EXT2_DIR_PAD 4
+#define EXT2_DIR_ROUND (EXT2_DIR_PAD - 1)
+#define EXT2_DIR_REC_LEN(namelen) \
+ (((namelen) + 8 + EXT2_DIR_ROUND) & ~EXT2_DIR_ROUND)
+
#endif /* !_UFS_EXT2FS_EXT2FS_DIR_H_ */
Index: src/sys/ufs/ext2fs/ext2fs_extern.h
diff -u src/sys/ufs/ext2fs/ext2fs_extern.h:1.48 src/sys/ufs/ext2fs/ext2fs_extern.h:1.49
--- src/sys/ufs/ext2fs/ext2fs_extern.h:1.48 Fri Mar 27 13:27:56 2015
+++ src/sys/ufs/ext2fs/ext2fs_extern.h Fri Jun 24 13:21:30 2016
@@ -1,4 +1,4 @@
-/* $NetBSD: ext2fs_extern.h,v 1.48 2015/03/27 17:27:56 riastradh Exp $ */
+/* $NetBSD: ext2fs_extern.h,v 1.49 2016/06/24 17:21:30 christos Exp $ */
/*-
* Copyright (c) 1991, 1993, 1994
@@ -78,6 +78,7 @@ struct vnode;
struct mbuf;
struct componentname;
struct ufs_lookup_results;
+struct ext2fs_searchslot;
extern struct pool ext2fs_inode_pool; /* memory pool for inodes */
extern struct pool ext2fs_dinode_pool; /* memory pool for dinodes */
@@ -120,6 +121,9 @@ int ext2fs_inactive(void *);
/* ext2fs_lookup.c */
int ext2fs_readdir(void *);
int ext2fs_lookup(void *);
+int ext2fs_search_dirblock(struct inode *, void *, int *,
+ const char *, int , int *, doff_t *, doff_t *, doff_t *,
+ struct ext2fs_searchslot *);
int ext2fs_direnter(struct inode *, struct vnode *,
const struct ufs_lookup_results *,
struct componentname *);
@@ -172,6 +176,15 @@ int ext2fs_makeinode(int, struct vnode *
struct componentname *cnp);
int ext2fs_reclaim(void *);
+/* ext2fs_hash.c */
+int ext2fs_htree_hash(const char *, int, uint32_t *, int, uint32_t *,
+ uint32_t *);
+
+/* ext2fs_htree.c */
+int ext2fs_htree_has_idx(struct inode *);
+int ext2fs_htree_lookup(struct inode *, const char *, int, struct buf **,
+ int *, doff_t *, doff_t *, doff_t *, struct ext2fs_searchslot *);
+
__END_DECLS
#define IS_EXT2_VNODE(vp) (vp->v_tag == VT_EXT2FS)
Index: src/sys/ufs/ext2fs/ext2fs_lookup.c
diff -u src/sys/ufs/ext2fs/ext2fs_lookup.c:1.79 src/sys/ufs/ext2fs/ext2fs_lookup.c:1.80
--- src/sys/ufs/ext2fs/ext2fs_lookup.c:1.79 Tue Jan 12 16:29:29 2016
+++ src/sys/ufs/ext2fs/ext2fs_lookup.c Fri Jun 24 13:21:30 2016
@@ -1,4 +1,4 @@
-/* $NetBSD: ext2fs_lookup.c,v 1.79 2016/01/12 21:29:29 riastradh Exp $ */
+/* $NetBSD: ext2fs_lookup.c,v 1.80 2016/06/24 17:21:30 christos Exp $ */
/*
* Modified for NetBSD 1.2E
@@ -48,7 +48,7 @@
*/
#include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: ext2fs_lookup.c,v 1.79 2016/01/12 21:29:29 riastradh Exp $");
+__KERNEL_RCSID(0, "$NetBSD: ext2fs_lookup.c,v 1.80 2016/06/24 17:21:30 christos Exp $");
#include <sys/param.h>
#include <sys/systm.h>
@@ -70,6 +70,7 @@ __KERNEL_RCSID(0, "$NetBSD: ext2fs_looku
#include <ufs/ext2fs/ext2fs_extern.h>
#include <ufs/ext2fs/ext2fs_dir.h>
#include <ufs/ext2fs/ext2fs.h>
+#include <ufs/ext2fs/ext2fs_htree.h>
#include <miscfs/genfs/genfs.h>
@@ -117,6 +118,13 @@ ext2fs_dirconv2ffs(struct ext2fs_direct
ffsdir->d_reclen = _DIRENT_SIZE(ffsdir);
}
+static int
+ext2fs_is_dot_entry(struct componentname *cnp)
+{
+ return cnp->cn_namelen <= 2 && cnp->cn_nameptr[0] == '.' &&
+ (cnp->cn_nameptr[1] == '.' || cnp->cn_nameptr[1] == '\0');
+}
+
/*
* Vnode op for reading directories.
*
@@ -271,7 +279,7 @@ ext2fs_lookup(void *v)
struct buf *bp; /* a buffer of directory entries */
struct ext2fs_direct *ep; /* the current directory entry */
int entryoffsetinblock; /* offset of ep in bp's buffer */
- enum {NONE, COMPACT, FOUND} slotstatus;
+ enum ext2fs_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 */
@@ -292,6 +300,8 @@ ext2fs_lookup(void *v)
int dirblksiz = ump->um_dirblksiz;
ino_t foundino;
struct ufs_lookup_results *results;
+ doff_t i_offset; /* cached i_offset value */
+ struct ext2fs_searchslot ss;
flags = cnp->cn_flags;
@@ -372,6 +382,37 @@ ext2fs_lookup(void *v)
endsearch = roundup(ext2fs_size(dp), dirblksiz);
enduseful = 0;
+ /*
+ * 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 (ext2fs_htree_has_idx(dp) && ext2fs_is_dot_entry(cnp)) {
+ numdirpasses = 1;
+ entryoffsetinblock = 0;
+
+ int htree_lookup_ret = ext2fs_htree_lookup(dp, cnp->cn_nameptr,
+ cnp->cn_namelen, &bp, &entryoffsetinblock, &i_offset,
+ &prevoff, &enduseful, &ss);
+ switch (htree_lookup_ret) {
+ case 0:
+ ep = (struct ext2fs_direct*)((char *)bp->b_data +
+ (i_offset & bmask));
+ foundino = ep->e2d_ino;
+ goto found;
+ case ENOENT:
+ i_offset = roundup2(dp->i_size, dp->i_e2fs->e2fs_bsize);
+ goto notfound;
+ default:
+ /*
+ * Something failed; just fallback to do a linear
+ * search.
+ */
+ break;
+ }
+ }
+
searchloop:
while (results->ulr_offset < endsearch) {
if (curcpu()->ci_schedstate.spc_flags & SPCF_SHOULDYIELD)
@@ -473,7 +514,7 @@ searchloop:
if (ep->e2d_ino)
enduseful = results->ulr_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.
@@ -666,6 +707,96 @@ found:
return 0;
}
+int
+ext2fs_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 = ITOV(ip);
+ struct ext2fs_direct *ep, *top;
+ uint32_t bsize = ip->i_e2fs->e2fs_bsize;
+ int offset = *entryoffsetinblockp;
+ int namlen;
+
+ ep = (void *)((char *)data + offset);
+ top = (void *)((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 && ext2fs_dirbadentry(vdp, ep, offset))) {
+ int i;
+ ufs_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 >= ssp->slotneeded) {
+ ssp->slotstatus = FOUND;
+ ssp->slotoffset = *offp;
+ ssp->slotsize = ep->e2d_reclen;
+ } else if (size > 0 && 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 &&
+ !memcmp(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 = (void *)((char *)data + offset);
+ }
+
+ return 0;
+}
+
/*
* Do consistency checking on a directory entry:
* record length must be multiple of 4
Added files:
Index: src/sys/ufs/ext2fs/ext2fs_hash.c
diff -u /dev/null src/sys/ufs/ext2fs/ext2fs_hash.c:1.1
--- /dev/null Fri Jun 24 13:21:30 2016
+++ src/sys/ufs/ext2fs/ext2fs_hash.c Fri Jun 24 13:21:30 2016
@@ -0,0 +1,314 @@
+/* $NetBSD: ext2fs_hash.c,v 1.1 2016/06/24 17:21:30 christos Exp $ */
+
+/*-
+ * Copyright (c) 2010, 2013 Zheng Liu <[email protected]>
+ * 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: head/sys/fs/ext2fs/ext2_hash.c 294504 2016-01-21 14:50:28Z pfg $
+ */
+
+/*
+ * 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/cdefs.h>
+__KERNEL_RCSID(0, "$NetBSD: ext2fs_hash.c,v 1.1 2016/06/24 17:21:30 christos Exp $");
+
+#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 <ufs/ext2fs/ext2fs_htree.h>
+#include <ufs/ext2fs/ext2fs_hash.h>
+#include <ufs/ufs/inode.h>
+#include <ufs/ufs/ufsmount.h>
+#include <ufs/ext2fs/ext2fs_extern.h>
+
+/*
+ * 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)); \
+}
+
+static void
+ext2fs_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);
+ }
+}
+
+static uint32_t
+ext2fs_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;
+}
+
+/*
+ * 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
+ext2fs_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
+ext2fs_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;
+}
+
+int
+ext2fs_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) {
+ ext2fs_prep_hashbuf(name, len, data, 16, unsigned_char);
+ ext2fs_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 = ext2fs_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) {
+ ext2fs_prep_hashbuf(name, len, data, 32, unsigned_char);
+ ext2fs_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;
+}
Index: src/sys/ufs/ext2fs/ext2fs_hash.h
diff -u /dev/null src/sys/ufs/ext2fs/ext2fs_hash.h:1.1
--- /dev/null Fri Jun 24 13:21:30 2016
+++ src/sys/ufs/ext2fs/ext2fs_hash.h Fri Jun 24 13:21:30 2016
@@ -0,0 +1,39 @@
+/* $NetBSD: ext2fs_hash.h,v 1.1 2016/06/24 17:21:30 christos Exp $ */
+
+/*-
+ * Copyright (c) 2016 The NetBSD Foundation, Inc.
+ * 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 NETBSD FOUNDATION, INC. 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 FOUNDATION 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.
+ */
+#ifndef _EXT2FS_HASH_H_
+#define _EXT2FS_HASH_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))))
+
+#endif /* _EXT2FS_HASH_H_ */
Index: src/sys/ufs/ext2fs/ext2fs_htree.c
diff -u /dev/null src/sys/ufs/ext2fs/ext2fs_htree.c:1.1
--- /dev/null Fri Jun 24 13:21:30 2016
+++ src/sys/ufs/ext2fs/ext2fs_htree.c Fri Jun 24 13:21:30 2016
@@ -0,0 +1,316 @@
+/* $NetBSD: ext2fs_htree.c,v 1.1 2016/06/24 17:21:30 christos Exp $ */
+
+/*-
+ * Copyright (c) 2010, 2012 Zheng Liu <[email protected]>
+ * 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: head/sys/fs/ext2fs/ext2_htree.c 294653 2016-01-24 02:41:49Z pfg $
+ */
+#include <sys/cdefs.h>
+__KERNEL_RCSID(0, "$NetBSD: ext2fs_htree.c,v 1.1 2016/06/24 17:21:30 christos Exp $");
+
+#include <sys/param.h>
+#include <sys/systm.h>
+#include <sys/resourcevar.h>
+#include <sys/kernel.h>
+#include <sys/file.h>
+#include <sys/stat.h>
+#include <sys/buf.h>
+#include <sys/proc.h>
+#include <sys/mount.h>
+#include <sys/namei.h>
+#include <sys/vnode.h>
+#include <sys/lockf.h>
+#include <sys/pool.h>
+#include <sys/signalvar.h>
+#include <sys/kauth.h>
+
+#include <ufs/ufs/dir.h>
+
+#include <ufs/ufs/inode.h>
+#include <ufs/ufs/ufsmount.h>
+#include <ufs/ext2fs/ext2fs.h>
+
+#include <ufs/ext2fs/ext2fs_extern.h>
+#include <ufs/ext2fs/ext2fs_dinode.h>
+#include <ufs/ext2fs/ext2fs_dir.h>
+#include <ufs/ext2fs/ext2fs_htree.h>
+#include <ufs/ext2fs/ext2fs_hash.h>
+
+int
+ext2fs_htree_has_idx(struct inode *ip)
+{
+ return EXT2_HAS_COMPAT_FEATURE(ip->i_e2fs, EXT2F_COMPAT_DIRHASHINDEX)
+ && (ip->i_din.e2fs_din->e2di_flags & EXT2_INDEX);
+}
+
+static off_t
+ext2fs_htree_get_block(struct ext2fs_htree_entry *ep)
+{
+ return ep->h_blk & 0x00FFFFFF;
+}
+
+
+static void
+ext2fs_htree_release(struct ext2fs_htree_lookup_info *info)
+{
+ for (u_int i = 0; i < info->h_levels_num; i++) {
+ struct buf *bp = info->h_levels[i].h_bp;
+ if (bp != NULL)
+ brelse(bp, 0);
+ }
+}
+
+static uint16_t
+ext2fs_htree_get_limit(struct ext2fs_htree_entry *ep)
+{
+ return ((struct ext2fs_htree_count *)(ep))->h_entries_max;
+}
+
+static uint32_t
+ext2fs_htree_root_limit(struct inode *ip, int len)
+{
+ uint32_t space = ip->i_e2fs->e2fs_bsize - EXT2_DIR_REC_LEN(1) -
+ EXT2_DIR_REC_LEN(2) - len;
+ return space / sizeof(struct ext2fs_htree_entry);
+}
+
+static uint16_t
+ext2fs_htree_get_count(struct ext2fs_htree_entry *ep)
+{
+ return ((struct ext2fs_htree_count *)(ep))->h_entries_num;
+}
+
+static uint32_t
+ext2fs_htree_get_hash(struct ext2fs_htree_entry *ep)
+{
+ return ep->h_hash;
+}
+
+static int
+ext2fs_htree_check_next(struct inode *ip, uint32_t hash, const char *name,
+ struct ext2fs_htree_lookup_info *info)
+{
+ struct vnode *vp = ITOV(ip);
+ struct ext2fs_htree_lookup_level *level;
+ struct buf *bp;
+ uint32_t next_hash;
+ int idx = info->h_levels_num - 1;
+ int levels = 0;
+
+ for (;;) {
+ level = &info->h_levels[idx];
+ level->h_entry++;
+ if (level->h_entry < level->h_entries +
+ ext2fs_htree_get_count(level->h_entries))
+ break;
+ if (idx == 0)
+ return 0;
+ idx--;
+ levels++;
+ }
+
+ next_hash = ext2fs_htree_get_hash(level->h_entry);
+ if ((hash & 1) == 0) {
+ if (hash != (next_hash & ~1))
+ return 0;
+ }
+
+ while (levels > 0) {
+ levels--;
+ if (ext2fs_blkatoff(vp, ext2fs_htree_get_block(level->h_entry) *
+ ip->i_e2fs->e2fs_bsize, NULL, &bp) != 0)
+ return 0;
+ level = &info->h_levels[idx + 1];
+ brelse(level->h_bp, 0);
+ level->h_bp = bp;
+ level->h_entry = level->h_entries =
+ ((struct ext2fs_htree_node *)bp->b_data)->h_entries;
+ }
+
+ return 1;
+}
+
+static int
+ext2fs_htree_find_leaf(struct inode *ip, const char *name, int namelen,
+ uint32_t *hash, uint8_t *hash_ver,
+ struct ext2fs_htree_lookup_info *info)
+{
+ struct vnode *vp;
+ struct ext2fs *fs;/* F, G, and H are MD4 functions */
+ struct m_ext2fs *m_fs;
+ struct buf *bp = NULL;
+ struct ext2fs_htree_root *rootp;
+ struct ext2fs_htree_entry *entp, *start, *end, *middle, *found;
+ struct ext2fs_htree_lookup_level *level_info;
+ uint32_t hash_major = 0, hash_minor = 0;
+ uint32_t levels, cnt;
+ uint8_t hash_version;
+
+ if (name == NULL || info == NULL)
+ return -1;
+
+ vp = ITOV(ip);
+ fs = &(ip->i_e2fs->e2fs);
+ m_fs = ip->i_e2fs;
+
+ if (ext2fs_blkatoff(vp, 0, NULL, &bp) != 0)
+ return -1;
+
+ info->h_levels_num = 1;
+ info->h_levels[0].h_bp = bp;
+ rootp = (struct ext2fs_htree_root *)bp->b_data;
+ if (rootp->h_info.h_hash_version != EXT2_HTREE_LEGACY &&
+ rootp->h_info.h_hash_version != EXT2_HTREE_HALF_MD4 &&
+ rootp->h_info.h_hash_version != EXT2_HTREE_TEA)
+ goto error;
+
+ hash_version = rootp->h_info.h_hash_version;
+ if (hash_version <= EXT2_HTREE_TEA)
+ hash_version += m_fs->e2fs_uhash;
+ *hash_ver = hash_version;
+
+ ext2fs_htree_hash(name, namelen, fs->e3fs_hash_seed,
+ hash_version, &hash_major, &hash_minor);
+ *hash = hash_major;
+
+ if ((levels = rootp->h_info.h_ind_levels) > 1)
+ goto error;
+
+ entp = (struct ext2fs_htree_entry *)(((char *)&rootp->h_info) +
+ rootp->h_info.h_info_len);
+
+ if (ext2fs_htree_get_limit(entp) !=
+ ext2fs_htree_root_limit(ip, rootp->h_info.h_info_len))
+ goto error;
+
+ for (;;) {
+ cnt = ext2fs_htree_get_count(entp);
+ if (cnt == 0 || cnt > ext2fs_htree_get_limit(entp))
+ goto error;
+
+ start = entp + 1;
+ end = entp + cnt - 1;
+ while (start <= end) {
+ middle = start + (end - start) / 2;
+ if (ext2fs_htree_get_hash(middle) > hash_major)
+ end = middle - 1;
+ else
+ start = middle + 1;
+ }
+ found = start - 1;
+
+ level_info = &(info->h_levels[info->h_levels_num - 1]);
+ level_info->h_bp = bp;
+ level_info->h_entries = entp;
+ level_info->h_entry = found;
+ if (levels == 0)
+ return (0);
+ levels--;
+ if (ext2fs_blkatoff(vp,
+ ext2fs_htree_get_block(found) * m_fs->e2fs_bsize,
+ NULL, &bp) != 0)
+ goto error;
+ entp = ((struct ext2fs_htree_node *)bp->b_data)->h_entries;
+ info->h_levels_num++;
+ info->h_levels[info->h_levels_num - 1].h_bp = bp;
+ }
+
+error:
+ ext2fs_htree_release(info);
+ return -1;
+}
+
+/*
+ * Try to lookup a directory entry in HTree index
+ */
+int
+ext2fs_htree_lookup(struct inode *ip, const char *name, int namelen,
+ struct buf **bpp, int *entryoffp, doff_t *offp,
+ doff_t *prevoffp, doff_t *endusefulp, struct ext2fs_searchslot *ss)
+{
+ struct vnode *vp;
+ struct ext2fs_htree_lookup_info info;
+ struct ext2fs_htree_entry *leaf_node;
+ struct m_ext2fs *m_fs;
+ struct buf *bp;
+ uint32_t blk;
+ uint32_t dirhash;
+ uint32_t bsize;
+ uint8_t hash_version;
+ int search_next;
+
+ m_fs = ip->i_e2fs;
+ bsize = m_fs->e2fs_bsize;
+ vp = ITOV(ip);
+
+ /* TODO: print error msg because we don't lookup '.' and '..' */
+
+ memset(&info, 0, sizeof(info));
+ if (ext2fs_htree_find_leaf(ip, name, namelen, &dirhash,
+ &hash_version, &info)) {
+ return -1;
+ }
+
+ do {
+ leaf_node = info.h_levels[info.h_levels_num - 1].h_entry;
+ blk = ext2fs_htree_get_block(leaf_node);
+ if (ext2fs_blkatoff(vp, blk * bsize, NULL, &bp) != 0) {
+ ext2fs_htree_release(&info);
+ return -1;
+ }
+
+ *offp = blk * bsize;
+ *entryoffp = 0;
+ *prevoffp = blk * bsize;
+ *endusefulp = blk * bsize;
+
+ if (ss->slotstatus == NONE) {
+ ss->slotoffset = -1;
+ ss->slotfreespace = 0;
+ }
+
+ int found;
+ if (ext2fs_search_dirblock(ip, bp->b_data, &found,
+ name, namelen, entryoffp, offp, prevoffp,
+ endusefulp, ss) != 0) {
+ brelse(bp, 0);
+ ext2fs_htree_release(&info);
+ return -1;
+ }
+
+ if (found) {
+ *bpp = bp;
+ ext2fs_htree_release(&info);
+ return 0;
+ }
+
+ brelse(bp,0);
+ search_next = ext2fs_htree_check_next(ip, dirhash, name, &info);
+ } while (search_next);
+
+ ext2fs_htree_release(&info);
+ return ENOENT;
+}
Index: src/sys/ufs/ext2fs/ext2fs_htree.h
diff -u /dev/null src/sys/ufs/ext2fs/ext2fs_htree.h:1.1
--- /dev/null Fri Jun 24 13:21:30 2016
+++ src/sys/ufs/ext2fs/ext2fs_htree.h Fri Jun 24 13:21:30 2016
@@ -0,0 +1,101 @@
+/* $NetBSD: ext2fs_htree.h,v 1.1 2016/06/24 17:21:30 christos Exp $ */
+
+/*-
+ * Copyright (c) 2010, 2012 Zheng Liu <[email protected]>
+ * 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: head/sys/fs/ext2fs/htree.h 262623 2014-02-28 21:25:32Z pfg $
+ */
+#ifndef _FS_EXT2FS_HTREE_H_
+#define _FS_EXT2FS_HTREE_H_
+
+/* EXT3 HTree directory indexing */
+
+#define EXT2_HTREE_LEGACY 0
+#define EXT2_HTREE_HALF_MD4 1
+#define EXT2_HTREE_TEA 2
+#define EXT2_HTREE_LEGACY_UNSIGNED 3
+#define EXT2_HTREE_HALF_MD4_UNSIGNED 4
+#define EXT2_HTREE_TEA_UNSIGNED 5
+
+#define EXT2_HTREE_EOF 0x7FFFFFFF
+
+struct ext2fs_fake_direct {
+ uint32_t e2d_ino; /* inode number of entry */
+ uint16_t e2d_reclen; /* length of this record */
+ uint8_t e2d_namlen; /* length of string in d_name */
+ uint8_t e2d_type; /* file type */
+};
+
+struct ext2fs_htree_count {
+ uint16_t h_entries_max;
+ uint16_t h_entries_num;
+};
+
+struct ext2fs_htree_entry {
+ uint32_t h_hash;
+ uint32_t h_blk;
+};
+
+struct ext2fs_htree_root_info {
+ uint32_t h_reserved1;
+ uint8_t h_hash_version;
+ uint8_t h_info_len;
+ uint8_t h_ind_levels;
+ uint8_t h_reserved2;
+};
+
+struct ext2fs_htree_root {
+ struct ext2fs_fake_direct h_dot;
+ char h_dot_name[4];
+ struct ext2fs_fake_direct h_dotdot;
+ char h_dotdot_name[4];
+ struct ext2fs_htree_root_info h_info;
+ struct ext2fs_htree_entry h_entries[0];
+};
+
+struct ext2fs_htree_node {
+ struct ext2fs_fake_direct h_fake_dirent;
+ struct ext2fs_htree_entry h_entries[0];
+};
+
+struct ext2fs_htree_lookup_level {
+ struct buf *h_bp;
+ struct ext2fs_htree_entry *h_entries;
+ struct ext2fs_htree_entry *h_entry;
+};
+
+struct ext2fs_htree_lookup_info {
+ struct ext2fs_htree_lookup_level h_levels[2];
+ uint32_t h_levels_num;
+};
+
+struct ext2fs_htree_sort_entry {
+ uint16_t h_offset;
+ uint16_t h_size;
+ uint32_t h_hash;
+};
+
+#endif /* !_FS_EXT2FS_HTREE_H_ */
