Date: Sat, 6 Jul 2013 18:28:07 +0000 (UTC) From: "Pedro F. Giffuni" <pfg@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r252890 - in head/sys: fs/ext2fs modules/ext2fs Message-ID: <201307061828.r66IS7cC061422@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: pfg Date: Sat Jul 6 18:28:06 2013 New Revision: 252890 URL: http://svnweb.freebsd.org/changeset/base/252890 Log: Initial implementation of the HTree directory index. This is a port of NetBSD's GSoC 2012 Ext3 HTree directory indexing by Vyacheslav Matyushin. It was cleaned up and enhanced for FreeBSD by Zheng Liu (lz@). This is an excellent example of work shared among different projects: Vyacheslav was able to look at an early prototype from Zheng Liu who was also able to check the code from Haiku (with permission). As in linux, the feature is not available by default and must be enabled explicitly with tune2fs. We still do not support the workarounds required in readdir for NFS. Submitted by: Zheng Liu Tested by: Mike Ma Sponsored by: Google Inc. MFC after: 1 week Added: head/sys/fs/ext2fs/ext2_hash.c (contents, props changed) head/sys/fs/ext2fs/ext2_htree.c (contents, props changed) head/sys/fs/ext2fs/htree.h (contents, props changed) Modified: head/sys/fs/ext2fs/ext2_dir.h head/sys/fs/ext2fs/ext2_extern.h head/sys/fs/ext2fs/ext2_inode_cnv.c head/sys/fs/ext2fs/ext2_lookup.c head/sys/fs/ext2fs/ext2_vfsops.c head/sys/fs/ext2fs/ext2fs.h head/sys/modules/ext2fs/Makefile Modified: head/sys/fs/ext2fs/ext2_dir.h ============================================================================== --- head/sys/fs/ext2fs/ext2_dir.h Sat Jul 6 17:11:33 2013 (r252889) +++ head/sys/fs/ext2fs/ext2_dir.h Sat Jul 6 18:28:06 2013 (r252890) @@ -40,6 +40,21 @@ struct ext2fs_direct { uint16_t e2d_namlen; /* length of string in e2d_name */ 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; /* sizeof the entry we are seeking */ +}; + /* * The new version of the directory entry. Since EXT2 structures are * stored in intel byte order, and the name_len field could never be Modified: head/sys/fs/ext2fs/ext2_extern.h ============================================================================== --- head/sys/fs/ext2fs/ext2_extern.h Sat Jul 6 17:11:33 2013 (r252889) +++ head/sys/fs/ext2fs/ext2_extern.h Sat Jul 6 18:28:06 2013 (r252890) @@ -40,12 +40,15 @@ #define _FS_EXT2FS_EXT2_EXTERN_H_ struct ext2fs_dinode; +struct ext2fs_direct_2; +struct ext2fs_searchslot; struct indir; struct inode; struct mount; struct vfsconf; struct vnode; +int ext2_add_entry(struct vnode *, struct ext2fs_direct_2 *); int ext2_alloc(struct inode *, int32_t, int32_t, int, struct ucred *, int32_t *); int ext2_balloc(struct inode *, @@ -81,6 +84,18 @@ int ext2_dirempty(struct inode *, ino_t, int ext2_checkpath(struct inode *, struct inode *, struct ucred *); int cg_has_sb(int i); int ext2_inactive(struct vop_inactive_args *); +int ext2_htree_add_entry(struct vnode *, struct ext2fs_direct_2 *, + struct componentname *); +int ext2_htree_create_index(struct vnode *, struct componentname *, + struct ext2fs_direct_2 *); +int ext2_htree_has_idx(struct inode *); +int ext2_htree_hash(const char *, int, uint32_t *, int, uint32_t *, + uint32_t *); +int ext2_htree_lookup(struct inode *, const char *, int, struct buf **, + int *, doff_t *, doff_t *, doff_t *, struct ext2fs_searchslot *); +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. Added: head/sys/fs/ext2fs/ext2_hash.c ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ head/sys/fs/ext2fs/ext2_hash.c Sat Jul 6 18:28:06 2013 (r252890) @@ -0,0 +1,289 @@ +/*- + * Copyright (c) 2010, 2013 Zheng Liu <lz@freebsd.org> + * Copyright (c) 2012, Vyacheslav Matyushin + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * $FreeBSD$ + */ + +#include <sys/param.h> +#include <sys/systm.h> +#include <sys/conf.h> +#include <sys/vnode.h> +#include <sys/stat.h> +#include <sys/mount.h> + +#include <fs/ext2fs/htree.h> +#include <fs/ext2fs/inode.h> +#include <fs/ext2fs/ext2_mount.h> +#include <fs/ext2fs/ext2_extern.h> + +/* F, G, and H are MD4 functions */ +#define F(x, y, z) (((x) & (y)) | ((~x) & (z))) +#define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z))) +#define H(x, y, z) ((x) ^ (y) ^ (z)) + +/* ROTATE_LEFT rotates x left n bits */ +#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32 - (n)))) + +/* + * FF, GG, and HH are transformations for rounds 1, 2, and 3. + * Rotation is separated from addition to prevent recompuatation + */ +#define FF(a, b, c, d, x, s) { \ + (a) += F ((b), (c), (d)) + (x); \ + (a) = ROTATE_LEFT ((a), (s)); \ +} + +#define GG(a, b, c, d, x, s) { \ + (a) += G ((b), (c), (d)) + (x) + (uint32_t)0x5A827999; \ + (a) = ROTATE_LEFT ((a), (s)); \ +} + +#define HH(a, b, c, d, x, s) { \ + (a) += H ((b), (c), (d)) + (x) + (uint32_t)0x6ED9EBA1; \ + (a) = ROTATE_LEFT ((a), (s)); \ +} + +/* + * MD4 basic transformation. It transforms state based on block. + * + * This is a half md4 algorithm because in Linux it uses this algorithm in dir + * index. This function is copied from kern/md4c.c file and is modified as + * necessary. + * + * The return value of this function is uint32_t in Linux, but actually we don't + * need to check this value. So in our version this function don't return any + * values. + */ +static void +ext2_half_md4(uint32_t hash[4], uint32_t data[8]) +{ + uint32_t a = hash[0], b = hash[1], c = hash[2], d = hash[3]; + + /* Round 1 */ + FF(a, b, c, d, data[0], 3); + FF(d, a, b, c, data[1], 7); + FF(c, d, a, b, data[2], 11); + FF(b, c, d, a, data[3], 19); + FF(a, b, c, d, data[4], 3); + FF(d, a, b, c, data[5], 7); + FF(c, d, a, b, data[6], 11); + FF(b, c, d, a, data[7], 19); + + /* Round 2 */ + GG(a, b, c, d, data[1], 3); + GG(d, a, b, c, data[3], 5); + GG(c, d, a, b, data[5], 9); + GG(b, c, d, a, data[7], 13); + GG(a, b, c, d, data[0], 3); + GG(d, a, b, c, data[2], 5); + GG(c, d, a, b, data[4], 9); + GG(b, c, d, a, data[6], 13); + + /* Round 3 */ + HH(a, b, c, d, data[3], 3); + HH(d, a, b, c, data[7], 9); + HH(c, d, a, b, data[2], 11); + HH(b, c, d, a, data[6], 15); + HH(a, b, c, d, data[1], 3); + HH(d, a, b, c, data[5], 9); + HH(c, d, a, b, data[0], 11); + HH(b, c, d, a, data[4], 15); + + hash[0] += a; + hash[1] += b; + hash[2] += c; + hash[3] += d; +} + +/* + * Tiny Encryption Algorithm. + */ +static void +ext2_tea(uint32_t hash[4], uint32_t data[8]) +{ + uint32_t tea_delta = 0x9E3779B9; + uint32_t sum; + uint32_t x = hash[0], y = hash[1]; + int n = 16; + int i = 1; + + while (n-- > 0) { + sum = i * tea_delta; + x += ((y << 4) + data[0]) ^ (y + sum) ^ ((y >> 5) + data[1]); + y += ((x << 4) + data[2]) ^ (x + sum) ^ ((x >> 5) + data[3]); + i++; + } + + hash[0] += x; + hash[1] += y; +} + +static uint32_t +ext2_legacy_hash(const char *name, int len, int unsigned_char) +{ + uint32_t h0, h1 = 0x12A3FE2D, h2 = 0x37ABE8F9; + uint32_t multi = 0x6D22F5; + const unsigned char *uname = (const unsigned char *)name; + const signed char *sname = (const signed char *)name; + int val, i; + + for (i = 0; i < len; i++) { + if (unsigned_char) + val = (u_int)*uname++; + else + val = (int)*sname++; + + h0 = h2 + (h1 ^ (val * multi)); + if (h0 & 0x80000000) + h0 -= 0x7FFFFFFF; + h2 = h1; + h1 = h0; + } + + return (h1 << 1); +} + +static void +ext2_prep_hashbuf(const char *src, int slen, uint32_t *dst, int dlen, + int unsigned_char) +{ + uint32_t padding = slen | (slen << 8) | (slen << 16) | (slen << 24); + uint32_t buf_val; + int len, i; + int buf_byte; + const unsigned char *ubuf = (const unsigned char *)src; + const signed char *sbuf = (const signed char *)src; + + if (slen > dlen) + len = dlen; + else + len = slen; + + buf_val = padding; + + for (i = 0; i < len; i++) { + if (unsigned_char) + buf_byte = (u_int)ubuf[i]; + else + buf_byte = (int)sbuf[i]; + + if ((i % 4) == 0) + buf_val = padding; + + buf_val <<= 8; + buf_val += buf_byte; + + if ((i % 4) == 3) { + *dst++ = buf_val; + dlen -= sizeof(uint32_t); + buf_val = padding; + } + } + + dlen -= sizeof(uint32_t); + if (dlen >= 0) + *dst++ = buf_val; + + dlen -= sizeof(uint32_t); + while (dlen >= 0) { + *dst++ = padding; + dlen -= sizeof(uint32_t); + } +} + +int +ext2_htree_hash(const char *name, int len, + uint32_t *hash_seed, int hash_version, + uint32_t *hash_major, uint32_t *hash_minor) +{ + uint32_t hash[4]; + uint32_t data[8]; + uint32_t major = 0, minor = 0; + int unsigned_char = 0; + + if (!name || !hash_major) + return (-1); + + if (len < 1 || len > 255) + goto error; + + hash[0] = 0x67452301; + hash[1] = 0xEFCDAB89; + hash[2] = 0x98BADCFE; + hash[3] = 0x10325476; + + if (hash_seed) + memcpy(hash, hash_seed, sizeof(hash)); + + switch (hash_version) { + case EXT2_HTREE_TEA_UNSIGNED: + unsigned_char = 1; + case EXT2_HTREE_TEA: + while (len > 0) { + ext2_prep_hashbuf(name, len, data, 16, unsigned_char); + ext2_tea(hash, data); + len -= 16; + name += 16; + } + major = hash[0]; + minor = hash[1]; + break; + case EXT2_HTREE_LEGACY_UNSIGNED: + unsigned_char = 1; + case EXT2_HTREE_LEGACY: + major = ext2_legacy_hash(name, len, unsigned_char); + break; + case EXT2_HTREE_HALF_MD4_UNSIGNED: + unsigned_char = 1; + case EXT2_HTREE_HALF_MD4: + while (len > 0) { + ext2_prep_hashbuf(name, len, data, 32, unsigned_char); + ext2_half_md4(hash, data); + len -= 32; + name += 32; + } + major = hash[0]; + minor = hash[1]; + break; + default: + goto error; + } + + major &= ~1; + if (major == (EXT2_HTREE_EOF << 1)) + major = (EXT2_HTREE_EOF - 1) << 1; + *hash_major = major; + if (hash_minor) + *hash_minor = minor; + + return (0); + +error: + *hash_major = 0; + if (hash_minor) + *hash_minor = 0; + return (-1); +} Added: head/sys/fs/ext2fs/ext2_htree.c ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ head/sys/fs/ext2fs/ext2_htree.c Sat Jul 6 18:28:06 2013 (r252890) @@ -0,0 +1,899 @@ +/*- + * Copyright (c) 2010, 2012 Zheng Liu <lz@freebsd.org> + * Copyright (c) 2012, Vyacheslav Matyushin + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * $FreeBSD$ + */ + +#include <sys/param.h> +#include <sys/endian.h> +#include <sys/systm.h> +#include <sys/namei.h> +#include <sys/bio.h> +#include <sys/buf.h> +#include <sys/endian.h> +#include <sys/mount.h> +#include <sys/vnode.h> +#include <sys/malloc.h> +#include <sys/dirent.h> +#include <sys/sysctl.h> + +#include <ufs/ufs/dir.h> + +#include <fs/ext2fs/inode.h> +#include <fs/ext2fs/ext2_mount.h> +#include <fs/ext2fs/ext2fs.h> +#include <fs/ext2fs/fs.h> +#include <fs/ext2fs/ext2_extern.h> +#include <fs/ext2fs/ext2_dinode.h> +#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); +static uint32_t ext2_htree_get_block(struct ext2fs_htree_entry *ep); +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 uint32_t ext2_htree_node_limit(struct inode *ip); +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); +static int ext2_htree_writebuf(struct ext2fs_htree_lookup_info *info); + +int +ext2_htree_has_idx(struct inode *ip) +{ + if (EXT2_HAS_COMPAT_FEATURE(ip->i_e2fs, EXT2F_COMPAT_DIRHASHINDEX) && + ip->i_flags & EXT4_INDEX) + return (1); + else + return (0); +} + +static int +ext2_htree_check_next(struct inode *ip, uint32_t hash, const char *name, + struct ext2fs_htree_lookup_info *info) +{ + struct vnode *vp = ITOV(ip); + struct ext2fs_htree_lookup_level *level; + struct buf *bp; + uint32_t next_hash; + int idx = info->h_levels_num - 1; + int levels = 0; + + do { + level = &info->h_levels[idx]; + level->h_entry++; + if (level->h_entry < level->h_entries + + ext2_htree_get_count(level->h_entries)) + break; + if (idx == 0) + return (0); + idx--; + levels++; + } while (1); + + next_hash = ext2_htree_get_hash(level->h_entry); + if ((hash & 1) == 0) { + if (hash != (next_hash & ~1)) + return (0); + } + + while (levels > 0) { + levels--; + if (ext2_blkatoff(vp, ext2_htree_get_block(level->h_entry) * + ip->i_e2fs->e2fs_bsize, NULL, &bp) != 0) + return (0); + level = &info->h_levels[idx + 1]; + brelse(level->h_bp); + level->h_bp = bp; + level->h_entry = level->h_entries = + ((struct ext2fs_htree_node *)bp->b_data)->h_entries; + } + + return (1); +} + +static uint32_t +ext2_htree_get_block(struct ext2fs_htree_entry *ep) +{ + 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) +{ + return (ep->h_hash); +} + +static uint16_t +ext2_htree_get_limit(struct ext2fs_htree_entry *ep) +{ + 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; + + for (i = 0; i < info->h_levels_num; i++) { + struct buf *bp = info->h_levels[i].h_bp; + if (bp != NULL) + brelse(bp); + } +} + +static uint32_t +ext2_htree_root_limit(struct inode *ip, int len) +{ + uint32_t space; + + space = ip->i_e2fs->e2fs_bsize - EXT2_DIR_REC_LEN(1) - + EXT2_DIR_REC_LEN(2) - len; + return (space / sizeof(struct ext2fs_htree_entry)); +} + +static uint32_t +ext2_htree_node_limit(struct inode *ip) +{ + struct m_ext2fs *fs; + uint32_t space; + + fs = ip->i_e2fs; + space = fs->e2fs_bsize - EXT2_DIR_REC_LEN(0); + + return (space / sizeof(struct ext2fs_htree_entry)); +} + +static int +ext2_htree_find_leaf(struct inode *ip, const char *name, int namelen, + uint32_t *hash, uint8_t *hash_ver, + struct ext2fs_htree_lookup_info *info) +{ + struct vnode *vp; + struct ext2fs *fs; + struct m_ext2fs *m_fs; + struct buf *bp = NULL; + struct ext2fs_htree_root *rootp; + struct ext2fs_htree_entry *entp, *start, *end, *middle, *found; + struct ext2fs_htree_lookup_level *level_info; + uint32_t hash_major = 0, hash_minor = 0; + uint32_t levels, cnt; + uint8_t hash_version; + + if (name == NULL || info == NULL) + return (-1); + + vp = ITOV(ip); + fs = ip->i_e2fs->e2fs; + m_fs = ip->i_e2fs; + + if (ext2_blkatoff(vp, 0, NULL, &bp) != 0) + return (-1); + + info->h_levels_num = 1; + info->h_levels[0].h_bp = bp; + rootp = (struct ext2fs_htree_root *)bp->b_data; + if (rootp->h_info.h_hash_version != EXT2_HTREE_LEGACY && + rootp->h_info.h_hash_version != EXT2_HTREE_HALF_MD4 && + rootp->h_info.h_hash_version != EXT2_HTREE_TEA) + goto error; + + hash_version = rootp->h_info.h_hash_version; + if (hash_version <= EXT2_HTREE_TEA) + hash_version += m_fs->e2fs_uhash; + *hash_ver = hash_version; + + ext2_htree_hash(name, namelen, fs->e3fs_hash_seed, + hash_version, &hash_major, &hash_minor); + *hash = hash_major; + + if ((levels = rootp->h_info.h_ind_levels) > 1) + goto error; + + entp = (struct ext2fs_htree_entry *)(((char *)&rootp->h_info) + + rootp->h_info.h_info_len); + + if (ext2_htree_get_limit(entp) != + ext2_htree_root_limit(ip, rootp->h_info.h_info_len)) + goto error; + + while (1) { + cnt = ext2_htree_get_count(entp); + if (cnt == 0 || cnt > ext2_htree_get_limit(entp)) + goto error; + + start = entp + 1; + end = entp + cnt - 1; + while (start <= end) { + middle = start + (end - start) / 2; + if (ext2_htree_get_hash(middle) > hash_major) + end = middle - 1; + else + start = middle + 1; + } + found = start - 1; + + level_info = &(info->h_levels[info->h_levels_num - 1]); + level_info->h_bp = bp; + level_info->h_entries = entp; + level_info->h_entry = found; + if (levels == 0) + return (0); + levels--; + if (ext2_blkatoff(vp, + ext2_htree_get_block(found) * m_fs->e2fs_bsize, + NULL, &bp) != 0) + goto error; + entp = ((struct ext2fs_htree_node *)bp->b_data)->h_entries; + info->h_levels_num++; + info->h_levels[info->h_levels_num - 1].h_bp = bp; + } + +error: + ext2_htree_release(info); + return (-1); +} + +/* + * Try to lookup an directory entry in HTree index + */ +int +ext2_htree_lookup(struct inode *ip, const char *name, int namelen, + struct buf **bpp, int *entryoffp, doff_t *offp, + doff_t *prevoffp, doff_t *endusefulp, + struct ext2fs_searchslot *ss) +{ + struct vnode *vp; + struct ext2fs_htree_lookup_info info; + struct ext2fs_htree_entry *leaf_node; + struct m_ext2fs *m_fs; + struct buf *bp; + uint32_t blk; + uint32_t dirhash; + uint32_t bsize; + uint8_t hash_version; + int search_next; + int found = 0; + + m_fs = ip->i_e2fs; + bsize = m_fs->e2fs_bsize; + vp = ITOV(ip); + + /* TODO: print error msg because we don't lookup '.' and '..' */ + + memset(&info, 0, sizeof(info)); + if (ext2_htree_find_leaf(ip, name, namelen, &dirhash, + &hash_version, &info)) + return (-1); + + do { + leaf_node = info.h_levels[info.h_levels_num - 1].h_entry; + blk = ext2_htree_get_block(leaf_node); + if (ext2_blkatoff(vp, blk * bsize, NULL, &bp) != 0) { + ext2_htree_release(&info); + return (-1); + } + + *offp = blk * bsize; + *entryoffp = 0; + *prevoffp = blk * bsize; + *endusefulp = blk * bsize; + + if (ss->slotstatus == NONE) { + ss->slotoffset = -1; + ss->slotfreespace = 0; + } + + if (ext2_search_dirblock(ip, bp->b_data, &found, + name, namelen, entryoffp, offp, prevoffp, + endusefulp, ss) != 0) { + brelse(bp); + ext2_htree_release(&info); + return (-1); + } + + if (found) { + *bpp = bp; + ext2_htree_release(&info); + return (0); + } + + brelse(bp); + search_next = ext2_htree_check_next(ip, dirhash, name, &info); + } while (search_next); + + 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 int +ext2_htree_writebuf(struct ext2fs_htree_lookup_info *info) +{ + int i, error; + + for (i = 0; i < info->h_levels_num; i++) { + struct buf *bp = info->h_levels[i].h_bp; + error = bwrite(bp); + if (error) + return (error); + } + + return (0); +} + +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, EXT2_DIR_REC_LEN(new_entry->e2d_namlen)); +} + +/* + * 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; *** DIFF OUTPUT TRUNCATED AT 1000 LINES ***
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201307061828.r66IS7cC061422>