PERFORCE change 217565 for review
Zheng Liu
lz at FreeBSD.org
Sat Sep 22 14:18:20 UTC 2012
http://p4web.freebsd.org/@@217565?ac=10
Change 217565 by lz at gnehzuil-desktop on 2012/09/22 14:17:23
Create htree index in a directory
When a directory has two or more blocks, we will create a htree index
for this directory.
Affected files ...
.. //depot/projects/soc2010/extfs/src/sys/fs/ext2fs/ext2_extern.h#10 edit
.. //depot/projects/soc2010/extfs/src/sys/fs/ext2fs/ext2_htree.c#5 edit
.. //depot/projects/soc2010/extfs/src/sys/fs/ext2fs/ext2_lookup.c#8 edit
.. //depot/projects/soc2010/extfs/src/sys/fs/ext2fs/htree.h#7 edit
Differences ...
==== //depot/projects/soc2010/extfs/src/sys/fs/ext2fs/ext2_extern.h#10 (text+ko) ====
@@ -41,6 +41,7 @@
struct ext2fs_dinode;
struct ext2fs_searchslot;
+struct ext2fs_direct_2;
struct indir;
struct inode;
struct mount;
@@ -91,6 +92,8 @@
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 *);
+int ext2_htree_create_index(struct vnode *, struct componentname *,
+ struct ext2fs_direct_2 *);
/* ext2_lookup.c */
int ext2_search_dirblock(struct inode *, void *, int *, const char *,
==== //depot/projects/soc2010/extfs/src/sys/fs/ext2fs/ext2_htree.c#5 (text+ko) ====
@@ -43,8 +43,14 @@
#include <fs/ext2fs/ext2_dir.h>
#include <fs/ext2fs/htree.h>
+static void ext2_append_entry(char *block, uint32_t blksize,
+ struct ext2fs_direct_2 *last_entry,
+ struct ext2fs_direct_2 *new_entry);
+static int ext2_htree_append_block(struct vnode *vp, char *data,
+ struct componentname *cnp, uint32_t blksize);
static int ext2_htree_check_next(struct inode *ip, uint32_t hash,
const char *name, struct ext2fs_htree_lookup_info *info);
+static int ext2_htree_cmp_sort_entry(const void *e1, const void *e2);
static int ext2_htree_find_leaf(struct inode *ip, const char *name,
int namelen, uint32_t *hash, uint8_t *hash_verion,
struct ext2fs_htree_lookup_info *info);
@@ -52,6 +58,17 @@
static uint16_t ext2_htree_get_count(struct ext2fs_htree_entry *ep);
static uint32_t ext2_htree_get_hash(struct ext2fs_htree_entry *ep);
static uint16_t ext2_htree_get_limit(struct ext2fs_htree_entry *ep);
+static void ext2_htree_insert_entry_to_level(struct ext2fs_htree_lookup_level *level,
+ uint32_t hash, uint32_t blk);
+static void ext2_htree_insert_entry(struct ext2fs_htree_lookup_info *info,
+ uint32_t hash, uint32_t blk);
+static void ext2_htree_set_block(struct ext2fs_htree_entry *ep, uint32_t blk);
+static void ext2_htree_set_count(struct ext2fs_htree_entry *ep, uint16_t cnt);
+static void ext2_htree_set_hash(struct ext2fs_htree_entry *ep, uint32_t hash);
+static void ext2_htree_set_limit(struct ext2fs_htree_entry *ep, uint16_t limit);
+static int ext2_htree_split_dirblock(char *block1, char *block2,
+ uint32_t blksize, uint32_t *hash_seed, uint8_t hash_version,
+ uint32_t *split_hash, struct ext2fs_direct_2 *entry);
static void ext2_htree_release(struct ext2fs_htree_lookup_info *info);
static uint32_t ext2_htree_root_limit(struct inode *ip, int len);
@@ -114,12 +131,24 @@
return (ep->h_blk & 0x00FFFFFF);
}
+static void
+ext2_htree_set_block(struct ext2fs_htree_entry *ep, uint32_t blk)
+{
+ ep->h_blk = blk;
+}
+
static uint16_t
ext2_htree_get_count(struct ext2fs_htree_entry *ep)
{
return (((struct ext2fs_htree_count *)(ep))->h_entries_num);
}
+static void
+ext2_htree_set_count(struct ext2fs_htree_entry *ep, uint16_t cnt)
+{
+ ((struct ext2fs_htree_count *)(ep))->h_entries_num = cnt;
+}
+
static uint32_t
ext2_htree_get_hash(struct ext2fs_htree_entry *ep)
{
@@ -132,6 +161,18 @@
return (((struct ext2fs_htree_count *)(ep))->h_entries_max);
}
+static void
+ext2_htree_set_hash(struct ext2fs_htree_entry *ep, uint32_t hash)
+{
+ ep->h_hash = hash;
+}
+
+static void
+ext2_htree_set_limit(struct ext2fs_htree_entry *ep, uint16_t limit)
+{
+ ((struct ext2fs_htree_count *)(ep))->h_entries_max = limit;
+}
+
static void ext2_htree_release(struct ext2fs_htree_lookup_info *info)
{
int i;
@@ -315,3 +356,316 @@
ext2_htree_release(&info);
return (ENOENT);
}
+
+static int
+ext2_htree_append_block(struct vnode *vp, char *data,
+ struct componentname *cnp, uint32_t blksize)
+{
+ struct iovec aiov;
+ struct uio auio;
+ struct inode *dp = VTOI(vp);
+ uint64_t cursize, newsize;
+ int error;
+
+ cursize = roundup(dp->i_size, blksize);
+ newsize = roundup(dp->i_size, blksize) + blksize;
+
+ auio.uio_offset = cursize;
+ auio.uio_resid = blksize;
+ aiov.iov_len = blksize;
+ aiov.iov_base = data;
+ auio.uio_iov = &aiov;
+ auio.uio_iovcnt = 1;
+ auio.uio_rw = UIO_WRITE;
+ auio.uio_segflg = UIO_SYSSPACE;
+ error = VOP_WRITE(vp, &auio, IO_SYNC, cnp->cn_cred);
+ if (!error)
+ dp->i_size = newsize;
+
+ return (error);
+}
+
+static void
+ext2_htree_insert_entry_to_level(struct ext2fs_htree_lookup_level *level,
+ uint32_t hash, uint32_t blk)
+{
+ struct ext2fs_htree_entry *target;
+ int entries_num;
+
+ target = level->h_entry + 1;
+ entries_num = ext2_htree_get_count(level->h_entries);
+
+ memmove(target + 1, target, (char *)(level->h_entries + entries_num) -
+ (char *)target);
+ ext2_htree_set_block(target, blk);
+ ext2_htree_set_hash(target, hash);
+ ext2_htree_set_count(level->h_entries, entries_num + 1);
+}
+
+/*
+ * Insert an index entry to the index node.
+ */
+static void
+ext2_htree_insert_entry(struct ext2fs_htree_lookup_info *info,
+ uint32_t hash, uint32_t blk)
+{
+ struct ext2fs_htree_lookup_level *level;
+
+ level = &info->h_levels[info->h_levels_num - 1];
+ ext2_htree_insert_entry_to_level(level, hash, blk);
+}
+
+/*
+ * Compare two entry sort descriptiors by name hash value.
+ * This is used together with qsort.
+ */
+static int
+ext2_htree_cmp_sort_entry(const void *e1, const void *e2)
+{
+ const struct ext2fs_htree_sort_entry *entry1, *entry2;
+
+ entry1 = (const struct ext2fs_htree_sort_entry *)e1;
+ entry2 = (const struct ext2fs_htree_sort_entry *)e2;
+
+ if (entry1->h_hash < entry2->h_hash)
+ return (-1);
+ if (entry2->h_hash > entry2->h_hash)
+ return (1);
+ return (0);
+}
+
+/*
+ * Append an entry to the end of the directory block.
+ */
+static void
+ext2_append_entry(char *block, uint32_t blksize,
+ struct ext2fs_direct_2 *last_entry,
+ struct ext2fs_direct_2 *new_entry)
+{
+ uint16_t entry_len;
+
+ entry_len = EXT2_DIR_REC_LEN(last_entry->e2d_namlen);
+ last_entry->e2d_reclen = entry_len;
+ last_entry = (struct ext2fs_direct_2 *)((char *)last_entry + entry_len);
+ new_entry->e2d_reclen = block + blksize - (char *)last_entry;
+ memcpy(last_entry, new_entry, entry_len);
+}
+
+/*
+ * Move half of entries from the old directory block to the new one.
+ */
+static int
+ext2_htree_split_dirblock(char *block1, char *block2, uint32_t blksize,
+ uint32_t *hash_seed, uint8_t hash_version,
+ uint32_t *split_hash, struct ext2fs_direct_2 *entry)
+{
+ int entry_cnt = 0;
+ int size = 0;
+ int i, k;
+ uint32_t offset;
+ uint16_t entry_len = 0;
+ uint32_t entry_hash;
+ struct ext2fs_direct_2 *ep, *last;
+ char *dest;
+ struct ext2fs_htree_sort_entry *sort_info;
+
+ ep = (struct ext2fs_direct_2 *)block1;
+ dest = block2;
+ sort_info = (struct ext2fs_htree_sort_entry *)
+ ((char *)block2 + blksize);
+
+ /*
+ * Calculate name hash value for the entry which is to be added.
+ */
+ ext2_htree_hash(entry->e2d_name, entry->e2d_namlen, hash_seed,
+ hash_version, &entry_hash, NULL);
+
+ /*
+ * Fill in directory entry sort descriptors.
+ */
+ while ((char *)ep < block1 + blksize) {
+ if (ep->e2d_ino && ep->e2d_namlen) {
+ entry_cnt++;
+ sort_info--;
+ sort_info->h_size = ep->e2d_reclen;
+ sort_info->h_offset = (char *)ep - block1;
+ ext2_htree_hash(ep->e2d_name, ep->e2d_namlen,
+ hash_seed, hash_version,
+ &sort_info->h_hash, NULL);
+ }
+ ep = (struct ext2fs_direct_2 *)
+ ((char *)ep + ep->e2d_reclen);
+ }
+
+ /*
+ * Sort directory entry descriptors by name hash value.
+ */
+ qsort(sort_info, entry_cnt, sizeof(struct ext2fs_htree_sort_entry),
+ ext2_htree_cmp_sort_entry);
+
+ /*
+ * Count the number of entries to move to directory block 2.
+ */
+ for (i = entry_cnt - 1; i >= 0; i--) {
+ if (sort_info[i].h_size + size > blksize / 2)
+ break;
+ size += sort_info[i].h_size;
+ }
+
+ *split_hash = sort_info[i + 1].h_hash;
+
+ /*
+ * Set collision bit.
+ */
+ if (*split_hash == sort_info[i].h_hash)
+ *split_hash += 1;
+
+ /*
+ * Move half of directory entries from block 1 to block 2.
+ */
+ for (k = i + 1; k < entry_cnt; k++) {
+ ep = (struct ext2fs_direct_2 *)((char *)block1 +
+ sort_info[k].h_offset);
+ entry_len = EXT2_DIR_REC_LEN(ep->e2d_namlen);
+ memcpy(dest, ep, entry_len);
+ ((struct ext2fs_direct_2 *)dest)->e2d_reclen = entry_len;
+ /* Mark directory entry as unused. */
+ ep->e2d_ino = 0;
+ dest += entry_len;
+ }
+ dest -= entry_len;
+
+ /* Shrink directory entries in block 1. */
+ last = (struct ext2fs_direct_2 *)block1;
+ entry_len = EXT2_DIR_REC_LEN(last->e2d_namlen);
+ for (offset = last->e2d_reclen; offset < blksize; ) {
+ ep = (struct ext2fs_direct_2 *)(block1 + offset);
+ offset += ep->e2d_reclen;
+ if (last->e2d_ino) {
+ /* trim the existing slot */
+ last->e2d_reclen = entry_len;
+ last = (struct ext2fs_direct_2 *)
+ ((char *)last + entry_len);
+ }
+ entry_len = EXT2_DIR_REC_LEN(ep->e2d_namlen);
+ memcpy((void *)last, (void *)ep, entry_len);
+ }
+
+ if (entry_hash >= *split_hash) {
+ /* Add entry to block 2. */
+ ext2_append_entry(block2, blksize,
+ (struct ext2fs_direct_2 *)dest, entry);
+
+ /* Adjust length field of last entry of block 1. */
+ last->e2d_reclen = block1 + blksize - (char *)last;
+ } else {
+ /* Add entry to block 1. */
+ ext2_append_entry(block1, blksize, last, entry);
+
+ /* Adjust length field of last entry of block 2. */
+ ((struct ext2fs_direct_2 *)dest)->e2d_reclen =
+ block2 + blksize - dest;
+ }
+
+ return (0);
+}
+
+/*
+ * Create an HTree index for a directory
+ */
+int
+ext2_htree_create_index(struct vnode *vp, struct componentname *cnp,
+ struct ext2fs_direct_2 *new_entry)
+{
+ struct buf *bp = NULL;
+ struct inode *dp;
+ struct ext2fs *fs;
+ struct m_ext2fs *m_fs;
+ struct ext2fs_direct_2 *ep, *dotdot;
+ struct ext2fs_htree_root *root;
+ struct ext2fs_htree_lookup_info info;
+ uint32_t blksize, dirlen, split_hash;
+ uint8_t hash_version;
+ char *buf1 = NULL;
+ char *buf2 = NULL;
+ int error = 0;
+
+ dp = VTOI(vp);
+ fs = dp->i_e2fs->e2fs;
+ m_fs = dp->i_e2fs;
+ blksize = m_fs->e2fs_bsize;
+
+ buf1 = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO);
+ buf2 = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO);
+
+ if ((error = ext2_blkatoff(vp, 0, NULL, &bp)) != 0)
+ goto out;
+
+ root = (struct ext2fs_htree_root *)bp->b_data;
+ dotdot = (struct ext2fs_direct_2 *)((char *)&(root->h_dotdot));
+ ep = (struct ext2fs_direct_2 *)((char *)dotdot + dotdot->e2d_reclen);
+ dirlen = (char *)root + blksize - (char *)ep;
+ memcpy(buf1, ep, dirlen);
+ ep = (struct ext2fs_direct_2 *)buf1;
+ while ((char *)ep < buf1 + dirlen)
+ ep = (struct ext2fs_direct_2 *)
+ ((char *)ep + ep->e2d_reclen);
+ ep->e2d_reclen = buf1 + blksize - (char *)ep;
+
+ dp->i_flags |= EXT2_DIR_INDEX;
+
+ /*
+ * Initialize index root.
+ */
+ dotdot->e2d_reclen = blksize - EXT2_DIR_REC_LEN(1);
+ memset(&root->h_info, 0, sizeof(root->h_info));
+ root->h_info.h_hash_version = fs->e3fs_def_hash_version;
+ root->h_info.h_info_len = sizeof(root->h_info);
+ ext2_htree_set_block(root->h_entries, 1);
+ ext2_htree_set_count(root->h_entries, 1);
+ ext2_htree_set_limit(root->h_entries,
+ ext2_htree_root_limit(dp, sizeof(root->h_info)));
+
+ memset(&info, 0, sizeof(info));
+ info.h_levels_num = 1;
+ info.h_levels[0].h_entries = root->h_entries;
+ info.h_levels[0].h_entry = root->h_entries;
+
+ hash_version = root->h_info.h_hash_version;
+ if (hash_version <= EXT2_HTREE_TEA)
+ hash_version += m_fs->e2fs_uhash;
+ ext2_htree_split_dirblock(buf1, buf2, blksize, fs->e3fs_hash_seed,
+ hash_version, &split_hash, new_entry);
+ ext2_htree_insert_entry(&info, split_hash, 2);
+
+ /*
+ * Write directory block 0.
+ */
+ error = bwrite(bp);
+ dp->i_flag |= IN_CHANGE | IN_UPDATE;
+ if (error)
+ goto out;
+
+ /*
+ * Write directory block 1.
+ */
+ error = ext2_htree_append_block(vp, buf1, cnp, blksize);
+ if (error)
+ goto out1;
+
+ /*
+ * Write directory block 2.
+ */
+ error = ext2_htree_append_block(vp, buf2, cnp, blksize);
+
+ free(buf1, M_TEMP);
+ free(buf2, M_TEMP);
+ return (error);
+out:
+ if (bp != NULL)
+ brelse(bp);
+out1:
+ free(buf1, M_TEMP);
+ free(buf2, M_TEMP);
+ return (error);
+}
==== //depot/projects/soc2010/extfs/src/sys/fs/ext2fs/ext2_lookup.c#8 (text+ko) ====
@@ -877,7 +877,7 @@
u_int dsize;
int error, loc, newentrysize, spacefree;
char *dirbuf;
- int DIRBLKSIZ = ip->i_e2fs->e2fs_bsize;
+ int DIRBLKSIZ = ip->i_e2fs->e2fs_bsize;
#ifdef DIAGNOSTIC
@@ -894,6 +894,18 @@
newdir.e2d_type = EXT2_FT_UNKNOWN;
bcopy(cnp->cn_nameptr, newdir.e2d_name, (unsigned)cnp->cn_namelen + 1);
newentrysize = EXT2_DIR_REC_LEN(newdir.e2d_namlen);
+
+ if (ip->i_e2fs->e2fs->e2fs_features_compat & EXT2F_COMPAT_DIR_INDEX) {
+ if ((dp->i_size / DIRBLKSIZ) == 1 &&
+ dp->i_offset == DIRBLKSIZ) {
+ /*
+ * Making indexed directory when one block is not
+ * enough to save all entries.
+ */
+ return ext2_htree_create_index(dvp, cnp, &newdir);
+ }
+ }
+
if (dp->i_count == 0) {
/*
* If dp->i_count is 0, then namei could find no
==== //depot/projects/soc2010/extfs/src/sys/fs/ext2fs/htree.h#7 (text+ko) ====
@@ -90,4 +90,10 @@
uint32_t h_levels_num;
};
+struct ext2fs_htree_sort_entry {
+ uint16_t h_offset;
+ uint16_t h_size;
+ uint32_t h_hash;
+};
+
#endif /* !_FS_EXT2FS_HTREE_H_ */
More information about the p4-projects
mailing list