PERFORCE change 216632 for review
Zheng Liu
lz at FreeBSD.org
Tue Aug 28 16:36:52 UTC 2012
http://p4web.freebsd.org/@@216632?ac=10
Change 216632 by lz at gnehzuil-desktop on 2012/08/28 16:36:39
In ext2_lookup we firstly try to find a dir entry. If it fails, it will
fall back to linear search.
Affected files ...
.. //depot/projects/soc2010/extfs/src/sys/fs/ext2fs/ext2_dir.h#3 edit
.. //depot/projects/soc2010/extfs/src/sys/fs/ext2fs/ext2_extern.h#9 edit
.. //depot/projects/soc2010/extfs/src/sys/fs/ext2fs/ext2_htree.c#4 add
.. //depot/projects/soc2010/extfs/src/sys/fs/ext2fs/ext2_inode_cnv.c#3 edit
.. //depot/projects/soc2010/extfs/src/sys/fs/ext2fs/ext2_lookup.c#7 edit
.. //depot/projects/soc2010/extfs/src/sys/fs/ext2fs/htree.h#6 edit
.. //depot/projects/soc2010/extfs/src/sys/modules/ext2fs/Makefile#6 edit
Differences ...
==== //depot/projects/soc2010/extfs/src/sys/fs/ext2fs/ext2_dir.h#3 (text+ko) ====
@@ -53,6 +53,17 @@
uint8_t e2d_type; /* file type */
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; /* size of the entry we 're seeking */
+};
+
/*
* Ext2 directory file types. Only the low 3 bits are used. The
* other bits are reserved for now.
==== //depot/projects/soc2010/extfs/src/sys/fs/ext2fs/ext2_extern.h#9 (text+ko) ====
@@ -40,6 +40,7 @@
#define _FS_EXT2FS_EXT2_EXTERN_H_
struct ext2fs_dinode;
+struct ext2fs_searchslot;
struct indir;
struct inode;
struct mount;
@@ -86,6 +87,16 @@
int ext2_htree_hash(const char *, int, uint32_t *, int,
uint32_t *, uint32_t *);
+/* ext2_htree.c */
+int ext2_htree_has_idx(struct inode *);
+int ext2_htree_lookup(struct inode *, const char *, int, struct buf **,
+ int *, doff_t *, doff_t *, doff_t *, struct ext2fs_searchslot *);
+
+/* ext2_lookup.c */
+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.
*/
==== //depot/projects/soc2010/extfs/src/sys/fs/ext2fs/ext2_inode_cnv.c#3 (text+ko) ====
@@ -93,7 +93,7 @@
ip->i_birthtime = ei->e2di_crtime;
ip->i_birthnsec = XTIME_TO_NSEC(ei->e2di_crtime_extra);
}
- ip->i_flags = 0;
+ ip->i_flags = ei->e2di_flags;
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;
@@ -139,7 +139,6 @@
ei->e2di_crtime_extra = NSEC_TO_XTIME(ip->i_birthnsec);
}
ei->e2di_flags = ip->i_flags;
- ei->e2di_flags = 0;
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;
==== //depot/projects/soc2010/extfs/src/sys/fs/ext2fs/ext2_lookup.c#7 (text+ko) ====
@@ -115,9 +115,19 @@
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.
*
@@ -299,13 +309,9 @@
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 */
- int slotsize; /* size of area at slotoffset */
+ struct ext2fs_searchslot ss;
doff_t i_diroff; /* cached i_diroff value */
doff_t i_offset; /* cached i_offset value */
- 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 */
@@ -313,12 +319,13 @@
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;
@@ -329,13 +336,11 @@
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
@@ -343,18 +348,45 @@
*/
ino = 0;
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 '.' and '..' 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 fall back 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
@@ -388,96 +420,37 @@
/*
* 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;
+ 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);
}
-
- /*
- * 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;
- }
- }
- }
- }
-
- /*
- * 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.
@@ -513,15 +486,15 @@
* 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);
dp->i_flag |= IN_CHANGE | IN_UPDATE;
@@ -723,6 +696,103 @@
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(ip, offset, how)
struct inode *ip;
==== //depot/projects/soc2010/extfs/src/sys/fs/ext2fs/htree.h#6 (text+ko) ====
@@ -40,4 +40,54 @@
#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;
+};
+
#endif /* !_FS_EXT2FS_HTREE_H_ */
==== //depot/projects/soc2010/extfs/src/sys/modules/ext2fs/Makefile#6 (text+ko) ====
@@ -4,7 +4,7 @@
KMOD= ext2fs
SRCS= opt_ddb.h opt_directio.h opt_quota.h opt_suiddir.h vnode_if.h \
ext2_alloc.c ext2_balloc.c ext2_bmap.c ext2_hash.c \
- ext2_inode.c ext2_inode_cnv.c ext2_lookup.c \
+ ext2_htree.c ext2_inode.c ext2_inode_cnv.c ext2_lookup.c \
ext2_prealloc.c ext2_subr.c ext2_vfsops.c ext2_vnops.c
.include <bsd.kmod.mk>
More information about the p4-projects
mailing list