PERFORCE change 192957 for review
Zheng Liu
lz at FreeBSD.org
Wed May 11 13:36:28 UTC 2011
http://p4web.freebsd.org/@@192957?ac=10
Change 192957 by lz at 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))
More information about the p4-projects
mailing list