From owner-p4-projects@FreeBSD.ORG Tue Aug 3 08:28:40 2010 Return-Path: Delivered-To: p4-projects@freebsd.org Received: by hub.freebsd.org (Postfix, from userid 32767) id 4C099106566B; Tue, 3 Aug 2010 08:28:40 +0000 (UTC) Delivered-To: perforce@FreeBSD.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id E15E51065674 for ; Tue, 3 Aug 2010 08:28:39 +0000 (UTC) (envelope-from lz@FreeBSD.org) Received: from repoman.freebsd.org (repoman.freebsd.org [IPv6:2001:4f8:fff6::29]) by mx1.freebsd.org (Postfix) with ESMTP id CF2CC8FC0A for ; Tue, 3 Aug 2010 08:28:39 +0000 (UTC) Received: from repoman.freebsd.org (localhost [127.0.0.1]) by repoman.freebsd.org (8.14.4/8.14.4) with ESMTP id o738SdZE039831 for ; Tue, 3 Aug 2010 08:28:39 GMT (envelope-from lz@FreeBSD.org) Received: (from perforce@localhost) by repoman.freebsd.org (8.14.4/8.14.4/Submit) id o738Sd7S039829 for perforce@freebsd.org; Tue, 3 Aug 2010 08:28:39 GMT (envelope-from lz@FreeBSD.org) Date: Tue, 3 Aug 2010 08:28:39 GMT Message-Id: <201008030828.o738Sd7S039829@repoman.freebsd.org> X-Authentication-Warning: repoman.freebsd.org: perforce set sender to lz@FreeBSD.org using -f From: Zheng Liu To: Perforce Change Reviews Precedence: bulk Cc: Subject: PERFORCE change 181755 for review X-BeenThere: p4-projects@freebsd.org X-Mailman-Version: 2.1.5 List-Id: p4 projects tree changes List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 03 Aug 2010 08:28:40 -0000 http://p4web.freebsd.org/@@181755?ac=10 Change 181755 by lz@gnehzuil-freebsd on 2010/08/03 08:28:18 Finished to read ext4 directory entry with hash directory index. * Add two files. ext2_htree.[ch]. * The implementation of half md4 algorithm. We copy it from kern/md4c.c and modify it because in Linux it uses a half md4 algorithm. * Maybe there are two functions that need to be re-implemented because they are very similar to Linux's implementation. Until now I don't have a good implementation. All of goals have been completed. Next I will test and clean my code. Affected files ... .. //depot/projects/soc2010/ext4fs/src/sys/fs/ext2fs/ext2_htree.c#1 add .. //depot/projects/soc2010/ext4fs/src/sys/fs/ext2fs/ext2_htree.h#2 edit .. //depot/projects/soc2010/ext4fs/src/sys/fs/ext2fs/ext2_lookup.c#5 edit Differences ... ==== //depot/projects/soc2010/ext4fs/src/sys/fs/ext2fs/ext2_htree.h#2 (text+ko) ==== @@ -28,6 +28,15 @@ #ifndef _FS_EXT2FS_EXT2_HTREE_H_ #define _FS_EXT2FS_EXT2_HTREE_H_ +#define DIRINDEX_HASH_LEGACY 0 +#define DIRINDEX_HASH_HALF_MD4 1 +#define DIRINDEX_HASH_TEA 2 +#define DIRINDEX_HASH_LEGACY_UNSIGNED 3 +#define DIRINDEX_HASH_HALF_MD4_UNSIGNED 4 +#define DIRINDEX_HASH_TEA_UNSIGNED 5 + +#define DIRINDEX_BAD_DIR -75000 + /* * define some data structures for hash directory index. */ @@ -68,9 +77,8 @@ }; struct dirindex_frame { - struct buffer *di_bp; - struct dirindex_entry *di_ent; - struct dirindex_entry *di_at; + struct dirindex_entry di_ent; + struct dirindex_entry di_at; }; struct dirindex_map_entry { @@ -79,4 +87,16 @@ u_int16_t di_size; }; +struct dirindex_hash_info { + u_int32_t di_hash; + u_int32_t di_minhash; + int di_hashversion; + u_int32_t *di_seed; +}; + +/* ext2_htree.c */ +int ext4_is_dirindex(struct inode *); +int ext4_dirindex_lookup(struct vnode *, char *, int, + doff_t *, struct buf **, doff_t *prevoffp); + #endif /* !_FS_EXT2FS_EXT2_HTREE_H_ */ ==== //depot/projects/soc2010/ext4fs/src/sys/fs/ext2fs/ext2_lookup.c#5 (text+ko) ==== @@ -60,6 +60,7 @@ #include #include #include +#include #ifdef DIAGNOSTIC static int dirchk = 1; @@ -348,6 +349,25 @@ cnp->cn_namelen + 3) &~ 3; */ } + bmask = VFSTOEXT2(vdp->v_mount)->um_mountp->mnt_stat.f_iosize - 1; + + /* Usr hash directory index to search a large direcotries. */ + numdirpasses = 2; + prevoff = 0; + if (ext4_is_dirindex(dp)) { + switch (ext4_dirindex_lookup(vdp, cnp->cn_nameptr, + cnp->cn_namelen, &i_offset, &bp, NULL)) { + case 0: + ep = (struct ext2fs_direct_2 *)((char *)bp->b_data + + (i_offset & bmask)); + entryoffsetinblock = i_offset; + goto dirindex_found; + case ENOENT: + default: + break; + } + } + /* * If there is cached information on a previous search of * this directory, pick up where we last left off. @@ -359,7 +379,6 @@ * profiling time and hence has been removed in the interest * of simplicity. */ - bmask = VFSTOEXT2(vdp->v_mount)->um_mountp->mnt_stat.f_iosize - 1; if (nameiop != LOOKUP || i_diroff == 0 || i_diroff > dp->i_size) { entryoffsetinblock = 0; @@ -462,6 +481,7 @@ * reclen in ndp->ni_ufs area, and release * directory buffer. */ +dirindex_found: ino = ep->e2d_ino; goto found; }