[src/trunk]: src/sys/ufs/ext2fs More htree writing support (Hrishikesh Goyal ...

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

details:   https://anonhg.NetBSD.org/src/rev/bc4327864059
branches:  trunk
changeset: 346984:bc4327864059
user:      christos <christos%NetBSD.org@localhost>
date:      Tue Aug 09 07:15:35 2016 +0000

description:
More htree writing support (Hrishikesh Goyal GSoC 2016)

diffstat:

 sys/ufs/ext2fs/Makefile         |    4 +-
 sys/ufs/ext2fs/ext2fs_extents.h |    6 +-
 sys/ufs/ext2fs/ext2fs_extern.h  |    9 +-
 sys/ufs/ext2fs/ext2fs_htree.c   |  562 +++++++++++++++++++++++++++++++++++++++-
 4 files changed, 568 insertions(+), 13 deletions(-)

diffs (truncated from 679 to 300 lines):

diff -r b0e4f7f44dc9 -r bc4327864059 sys/ufs/ext2fs/Makefile
--- a/sys/ufs/ext2fs/Makefile   Tue Aug 09 06:40:24 2016 +0000
+++ b/sys/ufs/ext2fs/Makefile   Tue Aug 09 07:15:35 2016 +0000
@@ -1,7 +1,7 @@
-#      $NetBSD: Makefile,v 1.2 2016/06/03 21:55:50 joerg Exp $
+#      $NetBSD: Makefile,v 1.3 2016/08/09 07:15:35 christos Exp $
 
 INCSDIR= /usr/include/ufs/ext2fs
 
-INCS=  ext2fs.h ext2fs_dinode.h ext2fs_dir.h ext2fs_extents.h ext2fs_extern.h
+INCS=  ext2fs.h ext2fs_dinode.h ext2fs_dir.h ext2fs_extern.h
 
 .include <bsd.kinc.mk>
diff -r b0e4f7f44dc9 -r bc4327864059 sys/ufs/ext2fs/ext2fs_extents.h
--- a/sys/ufs/ext2fs/ext2fs_extents.h   Tue Aug 09 06:40:24 2016 +0000
+++ b/sys/ufs/ext2fs/ext2fs_extents.h   Tue Aug 09 07:15:35 2016 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: ext2fs_extents.h,v 1.2 2016/06/10 06:30:58 dholland Exp $      */
+/*     $NetBSD: ext2fs_extents.h,v 1.3 2016/08/09 07:15:35 christos Exp $      */
 
 /*-
  * Copyright (c) 2012, 2010 Zheng Liu <lz%freebsd.org@localhost>
@@ -32,10 +32,6 @@
 #define        _UFS_EXT2FS_EXT2FS_EXTENTS_H_
 
 #include <sys/types.h>
-#ifndef _KERNEL
-#include <stdbool.h>
-#endif
-
 #include <ufs/ufs/inode.h>
 #define        EXT4_EXT_MAGIC  0xf30a
 
diff -r b0e4f7f44dc9 -r bc4327864059 sys/ufs/ext2fs/ext2fs_extern.h
--- a/sys/ufs/ext2fs/ext2fs_extern.h    Tue Aug 09 06:40:24 2016 +0000
+++ b/sys/ufs/ext2fs/ext2fs_extern.h    Tue Aug 09 07:15:35 2016 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: ext2fs_extern.h,v 1.49 2016/06/24 17:21:30 christos Exp $      */
+/*     $NetBSD: ext2fs_extern.h,v 1.50 2016/08/09 07:15:35 christos Exp $      */
 
 /*-
  * Copyright (c) 1991, 1993, 1994
@@ -79,6 +79,7 @@
 struct componentname;
 struct ufs_lookup_results;
 struct ext2fs_searchslot;
+struct ext2fs_direct;
 
 extern struct pool ext2fs_inode_pool;          /* memory pool for inodes */
 extern struct pool ext2fs_dinode_pool;         /* memory pool for dinodes */
@@ -132,6 +133,8 @@
 int ext2fs_dirrewrite(struct inode *, const struct ufs_lookup_results *,
                           struct inode *, struct componentname *);
 int ext2fs_dirempty(struct inode *, ino_t, kauth_cred_t);
+int ext2fs_add_entry(struct vnode *, struct ext2fs_direct *,
+    const struct ufs_lookup_results *); 
 
 /* ext2fs_subr.c */
 int ext2fs_blkatoff(struct vnode *, off_t, char **, struct buf **);
@@ -184,6 +187,10 @@
 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 *);
+int ext2fs_htree_create_index(struct vnode *, struct componentname *,
+    struct ext2fs_direct *);
+int ext2fs_htree_add_entry(struct vnode *, struct ext2fs_direct *,
+    struct componentname *);
 
 __END_DECLS
 
diff -r b0e4f7f44dc9 -r bc4327864059 sys/ufs/ext2fs/ext2fs_htree.c
--- a/sys/ufs/ext2fs/ext2fs_htree.c     Tue Aug 09 06:40:24 2016 +0000
+++ b/sys/ufs/ext2fs/ext2fs_htree.c     Tue Aug 09 07:15:35 2016 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: ext2fs_htree.c,v 1.1 2016/06/24 17:21:30 christos Exp $        */
+/*     $NetBSD: ext2fs_htree.c,v 1.2 2016/08/09 07:15:35 christos Exp $        */
 
 /*-
  * Copyright (c) 2010, 2012 Zheng Liu <lz%freebsd.org@localhost>
@@ -26,10 +26,10 @@
  * 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 $
+ * $FreeBSD: head/sys/fs/ext2fs/ext2fs_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 $");
+__KERNEL_RCSID(0, "$NetBSD: ext2fs_htree.c,v 1.2 2016/08/09 07:15:35 christos Exp $");
 
 #include <sys/param.h>
 #include <sys/systm.h>
@@ -46,7 +46,7 @@
 #include <sys/pool.h>
 #include <sys/signalvar.h>
 #include <sys/kauth.h>
-
+#include <sys/malloc.h>
 #include <ufs/ufs/dir.h>
 
 #include <ufs/ufs/inode.h>
@@ -59,9 +59,13 @@
 #include <ufs/ext2fs/ext2fs_htree.h>
 #include <ufs/ext2fs/ext2fs_hash.h>
 
+static int ext2fs_htree_find_leaf(struct inode *, const char *, int ,
+    uint32_t *, uint8_t *, struct ext2fs_htree_lookup_info *);
+    
 int
 ext2fs_htree_has_idx(struct inode *ip)
 {
+       /* XXX ip->i_flags should have got checked here for IN_E3INDEX */
        return EXT2_HAS_COMPAT_FEATURE(ip->i_e2fs, EXT2F_COMPAT_DIRHASHINDEX)
            && (ip->i_din.e2fs_din->e2di_flags & EXT2_INDEX);
 }
@@ -72,7 +76,6 @@
        return ep->h_blk & 0x00FFFFFF;
 }
 
-
 static void
 ext2fs_htree_release(struct ext2fs_htree_lookup_info *info)
 {
@@ -109,6 +112,555 @@
        return ep->h_hash;
 }
 
+
+static void
+ext2fs_htree_set_block(struct ext2fs_htree_entry *ep, uint32_t blk)
+{
+       ep->h_blk = blk;
+}
+
+static void
+ext2fs_htree_set_count(struct ext2fs_htree_entry *ep, uint16_t cnt)
+{
+       ((struct ext2fs_htree_count *)(ep))->h_entries_num = cnt;
+}
+
+static void
+ext2fs_htree_set_hash(struct ext2fs_htree_entry *ep, uint32_t hash)
+{
+       ep->h_hash = hash;
+}
+
+static void
+ext2fs_htree_set_limit(struct ext2fs_htree_entry *ep, uint16_t limit)
+{
+       ((struct ext2fs_htree_count *)(ep))->h_entries_max = limit;
+}
+
+static uint32_t
+ext2fs_htree_node_limit(struct inode *ip)
+{
+       struct m_ext2fs *fs;
+       uint32_t space;
+
+       fs = ip->i_e2fs;
+       space = fs->e2fs_bsize - EXT2_DIR_REC_LEN(0);
+
+       return space / sizeof(struct ext2fs_htree_entry);
+}
+
+static int
+ext2fs_htree_append_block(struct vnode *vp, char *data,
+    struct componentname *cnp, uint32_t blksize)
+{
+       struct iovec aiov;
+       struct uio auio;
+       struct inode *dp = VTOI(vp);
+       uint64_t cursize, newsize;
+       int error;
+
+       cursize = roundup(dp->i_size, blksize);
+       newsize = cursize + blksize;
+
+       auio.uio_offset = cursize;
+       auio.uio_resid = blksize;
+       aiov.iov_len = blksize;
+       aiov.iov_base = data;
+       auio.uio_iov = &aiov;
+       auio.uio_iovcnt = 1;
+       auio.uio_rw = UIO_WRITE;
+       auio.uio_vmspace = vmspace_kernel();
+       error = VOP_WRITE(vp, &auio, IO_SYNC, cnp->cn_cred);
+       if (!error)
+               dp->i_size = newsize;
+
+       return error;
+}
+
+static int
+ext2fs_htree_writebuf(struct ext2fs_htree_lookup_info *info)
+{
+       int i, error;
+
+       for (i = 0; i < info->h_levels_num; i++) {
+               struct buf *bp = info->h_levels[i].h_bp;
+               error = bwrite(bp);
+               if (error)
+                       return error;
+       }
+
+       return 0;
+}
+
+static void
+ext2fs_htree_insert_entry_to_level(struct ext2fs_htree_lookup_level *level,
+    uint32_t hash, uint32_t blk)
+{
+       struct ext2fs_htree_entry *target;
+       int entries_num;
+
+       target = level->h_entry + 1;
+       entries_num = ext2fs_htree_get_count(level->h_entries);
+
+       memmove(target + 1, target, (char *)(level->h_entries + entries_num) -
+           (char *)target);
+       ext2fs_htree_set_block(target, blk);
+       ext2fs_htree_set_hash(target, hash);
+       ext2fs_htree_set_count(level->h_entries, entries_num + 1);
+}
+
+/*
+ * Insert an index entry to the index node.
+ */
+static void
+ext2fs_htree_insert_entry(struct ext2fs_htree_lookup_info *info,
+    uint32_t hash, uint32_t blk)
+{
+       struct ext2fs_htree_lookup_level *level;
+
+       level = &info->h_levels[info->h_levels_num - 1];
+       ext2fs_htree_insert_entry_to_level(level, hash, blk);
+}
+
+/*
+ * Compare two entry sort descriptors by name hash value.
+ * This is used together with qsort.
+ */
+static int
+ext2fs_htree_cmp_sort_entry(const void *e1, const void *e2)
+{
+       const struct ext2fs_htree_sort_entry *entry1, *entry2;
+
+       entry1 = (const struct ext2fs_htree_sort_entry *)e1;
+       entry2 = (const struct ext2fs_htree_sort_entry *)e2;
+
+       if (entry1->h_hash < entry2->h_hash)
+               return -1;
+       if (entry1->h_hash > entry2->h_hash)
+               return 1;
+       return 0;
+}
+
+/*
+ * Append an entry to the end of the directory block.
+ */
+static void
+ext2fs_append_entry(char *block, uint32_t blksize,
+    struct ext2fs_direct *last_entry, struct ext2fs_direct *new_entry)
+{
+       uint16_t entry_len;
+
+       entry_len = EXT2_DIR_REC_LEN(last_entry->e2d_namlen);
+       last_entry->e2d_reclen = entry_len;
+       last_entry = (struct ext2fs_direct *)((char *)last_entry + entry_len);
+       new_entry->e2d_reclen = block + blksize - (char *)last_entry;
+       memcpy(last_entry, new_entry, EXT2_DIR_REC_LEN(new_entry->e2d_namlen));
+}
+
+/*
+ * Move half of entries from the old directory block to the new one.
+ */
+static int
+ext2fs_htree_split_dirblock(char *block1, char *block2, uint32_t blksize,
+    uint32_t *hash_seed, uint8_t hash_version,
+    uint32_t *split_hash, struct ext2fs_direct *entry)
+{
+       int entry_cnt = 0;
+       int size = 0;
+       int i, k;
+       uint32_t offset;
+       uint16_t entry_len = 0;
+       uint32_t entry_hash;
+       struct ext2fs_direct *ep, *last;
+       char *dest;
+       struct ext2fs_htree_sort_entry *sort_info, dummy;
+
+       ep = (struct ext2fs_direct *)block1;
+       dest = block2;
+       sort_info = (struct ext2fs_htree_sort_entry *)
+           ((char *)block2 + blksize);
+
+       /*
+        * Calculate name hash value for the entry which is to be added.
+        */
+       ext2fs_htree_hash(entry->e2d_name, entry->e2d_namlen, hash_seed,
+           hash_version, &entry_hash, NULL);