Date: Wed, 11 May 2011 13:36:27 GMT From: Zheng Liu <lz@FreeBSD.org> To: Perforce Change Reviews <perforce@FreeBSD.org> Subject: PERFORCE change 192957 for review Message-ID: <201105111336.p4BDaRKp056652@skunkworks.freebsd.org>
index | next in thread | raw e-mail
http://p4web.freebsd.org/@@192957?ac=10 Change 192957 by lz@freebsd-dev on 2011/05/11 13:35:53 Implement ext2_htree_lookup(). Affected files ... .. //depot/projects/soc2010/extfs/src/sys/fs/ext2fs/ext2_htree.c#2 edit .. //depot/projects/soc2010/extfs/src/sys/fs/ext2fs/htree.h#3 edit Differences ... ==== //depot/projects/soc2010/extfs/src/sys/fs/ext2fs/ext2_htree.c#2 (text+ko) ==== @@ -33,6 +33,7 @@ #include <sys/stat.h> #include <sys/buf.h> #include <sys/hash.h> +#include <sys/namei.h> #include <fs/ext2fs/inode.h> #include <fs/ext2fs/ext2_mount.h> @@ -84,10 +85,246 @@ }; struct htree_frame { + struct buf *bp; + struct htree_entry *entries; + struct htree_entry *at; }; -int ext2_htree_lookup(struct inode *ip, struct componentname *cnp, +struct htree_map_entry { + uint32_t hash; + uint16_t offset; + uint16_t size; +}; + +static int htree_get_limit(struct htree_entry *); +static int htree_hash(char *, int, struct htree_hash_info *); +static int htree_node_limit(struct inode *); +static int htree_probe(struct inode *, struct componentname *, struct htree_hash_info *, + struct htree_frame [], struct htree_frame *); +static int htree_root_limit(struct inode *, int); + +static int +htree_get_limit(struct htree_entry *ep) +{ + return (((struct htree_countlimit *)(ep))->limit); +} + +static int +htree_node_limit(struct inode *ip) +{ + struct m_ext2fs *fs; + int space; + + fs = ip->i_e2fs; + space = fs->e2fs_bsize - EXT2_DIR_REC_LEN(0); + return (space / sizeof(struct htree_entry)); +} + +static int +htree_root_limit(struct inode *ip, int len) +{ + struct m_ext2fs *fs; + int space; + + fs = ip->i_e2fs; + space = fs->e2fs_bsize - EXT2_DIR_REC_LEN(1) - + EXT2_DIR_REC_LEN(2) - len; + return (space / sizeof(struct htree_entry)); +} + +static int +htree_hash(char *name, int len, struct htree_hash_info *hp) +{ + char *p; + int i; + uint32_t in[8], buf[4]; + uint32_t hash = 0, minhash = 0; + + /* initialize default hash value */ + buf[0] = 0x67452301; + buf[1] = 0xefcdab89; + buf[2] = 0x98badcfe; + buf[3] = 0x10325476; + + if (hp->ht_seed) { + for (i = 0; i < 4; i++) + if (hp->ht_seed[i]) + break; + if (i < 4) + memcpy(buf, hp->ht_seed, sizeof(buf)); + } + + switch (hp->ht_version) { + case HTREE_HASH_LEGACY_UNSIGNED: + hash = legacy_hash_unsigned(name, len); + break; + case HTREE_HASH_LEGACY: + hash = legacy_hash_signed(name, len); + break; + case HTREE_HASH_HALF_MD4_UNSIGNED: + p = name; + while (len > 0) { + str2hashbuf_unsigned(p, len, in, 8); + half_md4_transform(buf, in); + len -= 32; + p += 32; + } + minhash = buf[2]; + hash = buf[1]; + break; + case HTREE_HASH_HALF_MD4: + p = name; + while (len > 0) { + str2hashbuf_signed(p, len, in, 8); + half_md4_transform(buf, in); + len -= 32; + p += 32; + } + minhash = buf[2]; + hash = buf[1]; + break; + case HTREE_HASH_TEA_UNSIGNED: + p = name; + while (len > 0) { + str2hashbuf_unsigned(p, len, in, 4); + tea_transform(buf, in); + name -= 16; + p += 16; + } + minhash = buf[1]; + hash = buf[0]; + break; + case HTREE_HASH_TEA: + p = name; + while (len > 0) { + str2hashbuf_signed(p, len, in, 4); + tea_transform(buf, in); + name -= 16; + p += 16; + } + minhash = buf[1]; + hash = buf[0]; + break; + default: + hp->ht_hash = 0; + return (-1); + } + + hash = hash & ~1; + if (hash == (HTREE_EOF << 1)) + hash = (HTREE_EOF - 1) << 1; + hp->ht_minhash = minhash; + hp->ht_hash = hash; + + return (0); +} + +static int +htree_probe(struct inode *ip, struct componentname *cnp, struct htree_hash_info *hinfop, + struct htree_frame frames[], struct htree_frame *fp) +{ + struct ext2fs *fs; + struct buf *bp = NULL; + struct htree_entry *ep, *p, *q, *m, *at; + struct htree_root *rp; + int error; + uint32_t hash; + int ind, cnt; + char *name = cnp->cn_nameptr; + + fs = ip->i_e2fs->e2fs; + fp->bp = NULL; + if ((error = ext2_blkatoff(ITOV(ip), (off_t)0, NULL, &bp)) != 0) + return (error); + + rp = (struct htree_root *)bp->b_data; + if (rp->info.version != HTREE_HASH_TEA && + rp->info.version != HTREE_HASH_HALF_MD4 && + rp->info.version != HTREE_HASH_LEGACY) + goto err; + + hinfop->ht_version = rp->info.version; + if (hinfop->ht_version <= HTREE_HASH_TEA) + hinfop->ht_version += 3; + hinfop->ht_seed = fs->e3fs_hash_seed; + + if (name != NULL) + htree_hash(name, cnp->cn_namelen, hinfop); + + hash = hinfop->ht_hash; + + if (rp->info.unused & 1) + goto err; + + if ((ind = rp->info.ind_levels) > 1) + goto err; + + ep = (struct htree_entry *)(((char *)&rp->info) + + rp->info.info_len); + + if (htree_get_limit(ep) != + htree_root_limit(ip, rp->info.info_len)) + goto err; + + while (1) { + cnt = ((struct htree_countlimit *)(ep))->count; + if (cnt == 0 || cnt > htree_get_limit(ep)) + goto err; + + p = ep + 1; + q = ep + cnt - 1; + while (p <= q) { + m = p + (q - p) / 2; + if (m->hash > hash) + q = m - 1; + else + p = m + 1; + } + + at = p - 1; + memcpy(&fp->entries, ep, sizeof(*ep)); + memcpy(&fp->at, at, sizeof(*at)); + + if (!ind--) { + if (bp != NULL) + brelse(bp); + return (0); + } + if (bp != NULL) { + brelse(bp); + bp = NULL; + } + if ((error = ext2_blkatoff(ITOV(ip), (ep->blk & 0x00ffffff), + NULL, &bp))) + return (error); + at = ep = ((struct htree_node *)bp->b_data)->entries; + if (htree_get_limit(ep) != htree_node_limit(ip)) + goto err; + fp++; + } + + if (bp != NULL) + brelse(bp); + + return (0); + +err: + if (bp != NULL) + brelse(bp); + + return (HTREE_BAD_DIR); +} + +int +ext2_htree_lookup(struct inode *ip, struct componentname *cnp, struct ext2fs_direct_2 **epp) { + struct htree_hash_info hinfo; + struct htree_frame *fp = NULL, frames[2]; + + memset(&hinfo, 0, sizeof(hinfo)); + if (htree_probe(ip, cnp, &hinfo, frames, fp) < 0) + return -1; + return 0; } ==== //depot/projects/soc2010/extfs/src/sys/fs/ext2fs/htree.h#3 (text+ko) ==== @@ -28,6 +28,17 @@ #ifndef _FS_EXT4FS_HTREE_H_ #define _FS_EXT4FS_HTREE_H_ +#define HTREE_HASH_LEGACY 0 +#define HTREE_HASH_HALF_MD4 1 +#define HTREE_HASH_TEA 2 +#define HTREE_HASH_LEGACY_UNSIGNED 3 +#define HTREE_HASH_HALF_MD4_UNSIGNED 4 +#define HTREE_HASH_TEA_UNSIGNED 5 + +#define HTREE_BAD_DIR -75000 + +#define HTREE_EOF 0x7fffffff + struct htree_hash_info { uint32_t ht_hash; uint32_t ht_minhash; @@ -35,7 +46,7 @@ uint32_t *ht_seed; }; -#define is_dx(fs, ip) \ +#define is_htree(fs, ip) \ ((fs->e2fs_features_compat & EXT2F_COMPAT_DIR_INDEX) & \ (ip->i_flags & EXT2_INDEX))home | help
Want to link to this message? Use this
URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201105111336.p4BDaRKp056652>