Date: Tue, 28 Aug 2012 16:36:51 GMT From: Zheng Liu <lz@FreeBSD.org> To: Perforce Change Reviews <perforce@FreeBSD.org> Subject: PERFORCE change 216632 for review Message-ID: <201208281636.q7SGapvg076210@skunkworks.freebsd.org>
next in thread | raw e-mail | index | archive | help
http://p4web.freebsd.org/@@216632?ac=10 Change 216632 by lz@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>
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201208281636.q7SGapvg076210>