From owner-p4-projects@FreeBSD.ORG Sat Sep 22 14:18:20 2012 Return-Path: Delivered-To: p4-projects@freebsd.org Received: by hub.freebsd.org (Postfix, from userid 32767) id 74C711065670; Sat, 22 Sep 2012 14:18:18 +0000 (UTC) Delivered-To: perforce@FreeBSD.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 12CE5106564A for ; Sat, 22 Sep 2012 14:18:18 +0000 (UTC) (envelope-from lz@FreeBSD.org) Received: from skunkworks.freebsd.org (skunkworks.freebsd.org [IPv6:2001:4f8:fff6::2d]) by mx1.freebsd.org (Postfix) with ESMTP id EFC128FC14 for ; Sat, 22 Sep 2012 14:18:17 +0000 (UTC) Received: from skunkworks.freebsd.org (localhost [127.0.0.1]) by skunkworks.freebsd.org (8.14.4/8.14.4) with ESMTP id q8MEIHCa068671 for ; Sat, 22 Sep 2012 14:18:17 GMT (envelope-from lz@FreeBSD.org) Received: (from perforce@localhost) by skunkworks.freebsd.org (8.14.4/8.14.4/Submit) id q8MEIHF9068668 for perforce@freebsd.org; Sat, 22 Sep 2012 14:18:17 GMT (envelope-from lz@FreeBSD.org) Date: Sat, 22 Sep 2012 14:18:17 GMT Message-Id: <201209221418.q8MEIHF9068668@skunkworks.freebsd.org> X-Authentication-Warning: skunkworks.freebsd.org: perforce set sender to lz@FreeBSD.org using -f From: Zheng Liu To: Perforce Change Reviews Precedence: bulk Cc: Subject: PERFORCE change 217565 for review X-BeenThere: p4-projects@freebsd.org X-Mailman-Version: 2.1.5 List-Id: p4 projects tree changes List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 22 Sep 2012 14:18:20 -0000 http://p4web.freebsd.org/@@217565?ac=10 Change 217565 by lz@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 #include +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_ */