[src/trunk]: src/sys GSoC 2016 (Hrishikesh Goyal): Htree index support from F...

[christos <christos%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/682ee95c5a9b
branches:  trunk
changeset: 816231:682ee95c5a9b
user:      christos <christos%NetBSD.org@localhost>
date:      Fri Jun 24 17:21:30 2016 +0000

description:
GSoC 2016 (Hrishikesh Goyal): Htree index support from FreeBSD

diffstat:

 sys/modules/ext2fs/Makefile    |    3 +-
 sys/ufs/ext2fs/ext2fs.h        |    9 +-
 sys/ufs/ext2fs/ext2fs_dir.h    |   26 +++-
 sys/ufs/ext2fs/ext2fs_extern.h |   15 +-
 sys/ufs/ext2fs/ext2fs_hash.c   |  314 ++++++++++++++++++++++++++++++++++++++++
 sys/ufs/ext2fs/ext2fs_hash.h   |   39 +++++
 sys/ufs/ext2fs/ext2fs_htree.c  |  316 +++++++++++++++++++++++++++++++++++++++++
 sys/ufs/ext2fs/ext2fs_htree.h  |  101 +++++++++++++
 sys/ufs/ext2fs/ext2fs_lookup.c |  139 +++++++++++++++++-
 sys/ufs/files.ufs              |    4 +-
 10 files changed, 957 insertions(+), 9 deletions(-)

diffs (truncated from 1141 to 300 lines):

diff -r f80f4c6c130f -r 682ee95c5a9b sys/modules/ext2fs/Makefile
--- a/sys/modules/ext2fs/Makefile       Fri Jun 24 16:08:54 2016 +0000
+++ b/sys/modules/ext2fs/Makefile       Fri Jun 24 17:21:30 2016 +0000
@@ -1,4 +1,4 @@
-#      $NetBSD: Makefile,v 1.3 2016/06/03 15:36:25 christos Exp $
+#      $NetBSD: Makefile,v 1.4 2016/06/24 17:22:13 christos Exp $
 
 .include "../Makefile.inc"
 
@@ -6,6 +6,7 @@
 
 KMOD=  ext2fs
 SRCS=  ext2fs_alloc.c ext2fs_balloc.c ext2fs_bmap.c ext2fs_bswap.c \
+       ext2fs_hash.c ext2fs_htree.c \
        ext2fs_extents.c ext2fs_inode.c ext2fs_lookup.c ext2fs_readwrite.c \
        ext2fs_rename.c ext2fs_subr.c ext2fs_vfsops.c ext2fs_vnops.c
 
diff -r f80f4c6c130f -r 682ee95c5a9b sys/ufs/ext2fs/ext2fs.h
--- a/sys/ufs/ext2fs/ext2fs.h   Fri Jun 24 16:08:54 2016 +0000
+++ b/sys/ufs/ext2fs/ext2fs.h   Fri Jun 24 17:21:30 2016 +0000
@@ -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 @@
        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 @@
                                         | 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 */
diff -r f80f4c6c130f -r 682ee95c5a9b sys/ufs/ext2fs/ext2fs_dir.h
--- a/sys/ufs/ext2fs/ext2fs_dir.h       Fri Jun 24 16:08:54 2016 +0000
+++ b/sys/ufs/ext2fs/ext2fs_dir.h       Fri Jun 24 17:21:30 2016 +0000
@@ -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 @@
        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 @@
        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_ */
diff -r f80f4c6c130f -r 682ee95c5a9b sys/ufs/ext2fs/ext2fs_extern.h
--- a/sys/ufs/ext2fs/ext2fs_extern.h    Fri Jun 24 16:08:54 2016 +0000
+++ b/sys/ufs/ext2fs/ext2fs_extern.h    Fri Jun 24 17:21:30 2016 +0000
@@ -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 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 @@
 /* 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 @@
                          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)
diff -r f80f4c6c130f -r 682ee95c5a9b sys/ufs/ext2fs/ext2fs_hash.c
--- /dev/null   Thu Jan 01 00:00:00 1970 +0000
+++ b/sys/ufs/ext2fs/ext2fs_hash.c      Fri Jun 24 17:21:30 2016 +0000
@@ -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 <lz%freebsd.org@localhost>
+ * 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;