1252890Spfg/*- 2252890Spfg * Copyright (c) 2010, 2012 Zheng Liu <lz@freebsd.org> 3252890Spfg * Copyright (c) 2012, Vyacheslav Matyushin 4252890Spfg * All rights reserved. 5252890Spfg * 6252890Spfg * Redistribution and use in source and binary forms, with or without 7252890Spfg * modification, are permitted provided that the following conditions 8252890Spfg * are met: 9252890Spfg * 1. Redistributions of source code must retain the above copyright 10252890Spfg * notice, this list of conditions and the following disclaimer. 11252890Spfg * 2. Redistributions in binary form must reproduce the above copyright 12252890Spfg * notice, this list of conditions and the following disclaimer in the 13252890Spfg * documentation and/or other materials provided with the distribution. 14252890Spfg * 15252890Spfg * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 16252890Spfg * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17252890Spfg * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18252890Spfg * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 19252890Spfg * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20252890Spfg * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21252890Spfg * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22252890Spfg * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23252890Spfg * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24252890Spfg * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25252890Spfg * SUCH DAMAGE. 26252890Spfg * 27252890Spfg * $FreeBSD$ 28252890Spfg */ 29252890Spfg 30252890Spfg#include <sys/param.h> 31252890Spfg#include <sys/endian.h> 32252890Spfg#include <sys/systm.h> 33252890Spfg#include <sys/namei.h> 34252890Spfg#include <sys/bio.h> 35252890Spfg#include <sys/buf.h> 36252890Spfg#include <sys/endian.h> 37252890Spfg#include <sys/mount.h> 38252890Spfg#include <sys/vnode.h> 39252890Spfg#include <sys/malloc.h> 40252890Spfg#include <sys/dirent.h> 41252890Spfg#include <sys/sysctl.h> 42252890Spfg 43252890Spfg#include <ufs/ufs/dir.h> 44252890Spfg 45252890Spfg#include <fs/ext2fs/inode.h> 46252890Spfg#include <fs/ext2fs/ext2_mount.h> 47252890Spfg#include <fs/ext2fs/ext2fs.h> 48252890Spfg#include <fs/ext2fs/fs.h> 49252890Spfg#include <fs/ext2fs/ext2_extern.h> 50252890Spfg#include <fs/ext2fs/ext2_dinode.h> 51252890Spfg#include <fs/ext2fs/ext2_dir.h> 52252890Spfg#include <fs/ext2fs/htree.h> 53252890Spfg 54252890Spfgstatic void ext2_append_entry(char *block, uint32_t blksize, 55252890Spfg struct ext2fs_direct_2 *last_entry, 56252890Spfg struct ext2fs_direct_2 *new_entry); 57252890Spfgstatic int ext2_htree_append_block(struct vnode *vp, char *data, 58252890Spfg struct componentname *cnp, uint32_t blksize); 59252890Spfgstatic int ext2_htree_check_next(struct inode *ip, uint32_t hash, 60252890Spfg const char *name, struct ext2fs_htree_lookup_info *info); 61252890Spfgstatic int ext2_htree_cmp_sort_entry(const void *e1, const void *e2); 62252890Spfgstatic int ext2_htree_find_leaf(struct inode *ip, const char *name, 63262723Spfg int namelen, uint32_t *hash, uint8_t *hash_version, 64252890Spfg struct ext2fs_htree_lookup_info *info); 65252890Spfgstatic uint32_t ext2_htree_get_block(struct ext2fs_htree_entry *ep); 66252890Spfgstatic uint16_t ext2_htree_get_count(struct ext2fs_htree_entry *ep); 67252890Spfgstatic uint32_t ext2_htree_get_hash(struct ext2fs_htree_entry *ep); 68252890Spfgstatic uint16_t ext2_htree_get_limit(struct ext2fs_htree_entry *ep); 69252890Spfgstatic void ext2_htree_insert_entry_to_level(struct ext2fs_htree_lookup_level *level, 70252890Spfg uint32_t hash, uint32_t blk); 71252890Spfgstatic void ext2_htree_insert_entry(struct ext2fs_htree_lookup_info *info, 72252890Spfg uint32_t hash, uint32_t blk); 73252890Spfgstatic uint32_t ext2_htree_node_limit(struct inode *ip); 74252890Spfgstatic void ext2_htree_set_block(struct ext2fs_htree_entry *ep, 75252890Spfg uint32_t blk); 76252890Spfgstatic void ext2_htree_set_count(struct ext2fs_htree_entry *ep, 77252890Spfg uint16_t cnt); 78252890Spfgstatic void ext2_htree_set_hash(struct ext2fs_htree_entry *ep, 79252890Spfg uint32_t hash); 80252890Spfgstatic void ext2_htree_set_limit(struct ext2fs_htree_entry *ep, 81252890Spfg uint16_t limit); 82252890Spfgstatic int ext2_htree_split_dirblock(char *block1, char *block2, 83252890Spfg uint32_t blksize, uint32_t *hash_seed, uint8_t hash_version, 84252890Spfg uint32_t *split_hash, struct ext2fs_direct_2 *entry); 85252890Spfgstatic void ext2_htree_release(struct ext2fs_htree_lookup_info *info); 86252890Spfgstatic uint32_t ext2_htree_root_limit(struct inode *ip, int len); 87252890Spfgstatic int ext2_htree_writebuf(struct ext2fs_htree_lookup_info *info); 88252890Spfg 89252890Spfgint 90252890Spfgext2_htree_has_idx(struct inode *ip) 91252890Spfg{ 92252890Spfg if (EXT2_HAS_COMPAT_FEATURE(ip->i_e2fs, EXT2F_COMPAT_DIRHASHINDEX) && 93261311Spfg ip->i_flag & IN_E4INDEX) 94252890Spfg return (1); 95252890Spfg else 96252890Spfg return (0); 97252890Spfg} 98252890Spfg 99252890Spfgstatic int 100252890Spfgext2_htree_check_next(struct inode *ip, uint32_t hash, const char *name, 101252890Spfg struct ext2fs_htree_lookup_info *info) 102252890Spfg{ 103252890Spfg struct vnode *vp = ITOV(ip); 104252890Spfg struct ext2fs_htree_lookup_level *level; 105252890Spfg struct buf *bp; 106252890Spfg uint32_t next_hash; 107252890Spfg int idx = info->h_levels_num - 1; 108252890Spfg int levels = 0; 109252890Spfg 110252890Spfg do { 111252890Spfg level = &info->h_levels[idx]; 112252890Spfg level->h_entry++; 113252890Spfg if (level->h_entry < level->h_entries + 114252890Spfg ext2_htree_get_count(level->h_entries)) 115252890Spfg break; 116252890Spfg if (idx == 0) 117252890Spfg return (0); 118252890Spfg idx--; 119252890Spfg levels++; 120252890Spfg } while (1); 121252890Spfg 122252890Spfg next_hash = ext2_htree_get_hash(level->h_entry); 123252890Spfg if ((hash & 1) == 0) { 124252890Spfg if (hash != (next_hash & ~1)) 125252890Spfg return (0); 126252890Spfg } 127252890Spfg 128252890Spfg while (levels > 0) { 129252890Spfg levels--; 130252890Spfg if (ext2_blkatoff(vp, ext2_htree_get_block(level->h_entry) * 131252890Spfg ip->i_e2fs->e2fs_bsize, NULL, &bp) != 0) 132252890Spfg return (0); 133252890Spfg level = &info->h_levels[idx + 1]; 134252890Spfg brelse(level->h_bp); 135252890Spfg level->h_bp = bp; 136252890Spfg level->h_entry = level->h_entries = 137252890Spfg ((struct ext2fs_htree_node *)bp->b_data)->h_entries; 138252890Spfg } 139252890Spfg 140252890Spfg return (1); 141252890Spfg} 142252890Spfg 143252890Spfgstatic uint32_t 144252890Spfgext2_htree_get_block(struct ext2fs_htree_entry *ep) 145252890Spfg{ 146252890Spfg return (ep->h_blk & 0x00FFFFFF); 147252890Spfg} 148252890Spfg 149252890Spfgstatic void 150252890Spfgext2_htree_set_block(struct ext2fs_htree_entry *ep, uint32_t blk) 151252890Spfg{ 152252890Spfg ep->h_blk = blk; 153252890Spfg} 154252890Spfg 155252890Spfgstatic uint16_t 156252890Spfgext2_htree_get_count(struct ext2fs_htree_entry *ep) 157252890Spfg{ 158252890Spfg return (((struct ext2fs_htree_count *)(ep))->h_entries_num); 159252890Spfg} 160252890Spfg 161252890Spfgstatic void 162252890Spfgext2_htree_set_count(struct ext2fs_htree_entry *ep, uint16_t cnt) 163252890Spfg{ 164252890Spfg ((struct ext2fs_htree_count *)(ep))->h_entries_num = cnt; 165252890Spfg} 166252890Spfg 167252890Spfgstatic uint32_t 168252890Spfgext2_htree_get_hash(struct ext2fs_htree_entry *ep) 169252890Spfg{ 170252890Spfg return (ep->h_hash); 171252890Spfg} 172252890Spfg 173252890Spfgstatic uint16_t 174252890Spfgext2_htree_get_limit(struct ext2fs_htree_entry *ep) 175252890Spfg{ 176252890Spfg return (((struct ext2fs_htree_count *)(ep))->h_entries_max); 177252890Spfg} 178252890Spfg 179252890Spfgstatic void 180252890Spfgext2_htree_set_hash(struct ext2fs_htree_entry *ep, uint32_t hash) 181252890Spfg{ 182252890Spfg ep->h_hash = hash; 183252890Spfg} 184252890Spfg 185252890Spfgstatic void 186252890Spfgext2_htree_set_limit(struct ext2fs_htree_entry *ep, uint16_t limit) 187252890Spfg{ 188252890Spfg ((struct ext2fs_htree_count *)(ep))->h_entries_max = limit; 189252890Spfg} 190252890Spfg 191252890Spfgstatic void 192252890Spfgext2_htree_release(struct ext2fs_htree_lookup_info *info) 193252890Spfg{ 194252890Spfg int i; 195252890Spfg 196252890Spfg for (i = 0; i < info->h_levels_num; i++) { 197252890Spfg struct buf *bp = info->h_levels[i].h_bp; 198252890Spfg if (bp != NULL) 199252890Spfg brelse(bp); 200252890Spfg } 201252890Spfg} 202252890Spfg 203252890Spfgstatic uint32_t 204252890Spfgext2_htree_root_limit(struct inode *ip, int len) 205252890Spfg{ 206252890Spfg uint32_t space; 207252890Spfg 208252890Spfg space = ip->i_e2fs->e2fs_bsize - EXT2_DIR_REC_LEN(1) - 209252890Spfg EXT2_DIR_REC_LEN(2) - len; 210252890Spfg return (space / sizeof(struct ext2fs_htree_entry)); 211252890Spfg} 212252890Spfg 213252890Spfgstatic uint32_t 214252890Spfgext2_htree_node_limit(struct inode *ip) 215252890Spfg{ 216252890Spfg struct m_ext2fs *fs; 217252890Spfg uint32_t space; 218252890Spfg 219252890Spfg fs = ip->i_e2fs; 220252890Spfg space = fs->e2fs_bsize - EXT2_DIR_REC_LEN(0); 221252890Spfg 222252890Spfg return (space / sizeof(struct ext2fs_htree_entry)); 223252890Spfg} 224252890Spfg 225252890Spfgstatic int 226252890Spfgext2_htree_find_leaf(struct inode *ip, const char *name, int namelen, 227252890Spfg uint32_t *hash, uint8_t *hash_ver, 228252890Spfg struct ext2fs_htree_lookup_info *info) 229252890Spfg{ 230252890Spfg struct vnode *vp; 231252890Spfg struct ext2fs *fs; 232252890Spfg struct m_ext2fs *m_fs; 233252890Spfg struct buf *bp = NULL; 234252890Spfg struct ext2fs_htree_root *rootp; 235252890Spfg struct ext2fs_htree_entry *entp, *start, *end, *middle, *found; 236252890Spfg struct ext2fs_htree_lookup_level *level_info; 237252890Spfg uint32_t hash_major = 0, hash_minor = 0; 238252890Spfg uint32_t levels, cnt; 239252890Spfg uint8_t hash_version; 240252890Spfg 241252890Spfg if (name == NULL || info == NULL) 242252890Spfg return (-1); 243252890Spfg 244252890Spfg vp = ITOV(ip); 245252890Spfg fs = ip->i_e2fs->e2fs; 246252890Spfg m_fs = ip->i_e2fs; 247252890Spfg 248252890Spfg if (ext2_blkatoff(vp, 0, NULL, &bp) != 0) 249252890Spfg return (-1); 250252890Spfg 251252890Spfg info->h_levels_num = 1; 252252890Spfg info->h_levels[0].h_bp = bp; 253252890Spfg rootp = (struct ext2fs_htree_root *)bp->b_data; 254252890Spfg if (rootp->h_info.h_hash_version != EXT2_HTREE_LEGACY && 255252890Spfg rootp->h_info.h_hash_version != EXT2_HTREE_HALF_MD4 && 256252890Spfg rootp->h_info.h_hash_version != EXT2_HTREE_TEA) 257252890Spfg goto error; 258252890Spfg 259252890Spfg hash_version = rootp->h_info.h_hash_version; 260252890Spfg if (hash_version <= EXT2_HTREE_TEA) 261252890Spfg hash_version += m_fs->e2fs_uhash; 262252890Spfg *hash_ver = hash_version; 263252890Spfg 264252890Spfg ext2_htree_hash(name, namelen, fs->e3fs_hash_seed, 265252890Spfg hash_version, &hash_major, &hash_minor); 266252890Spfg *hash = hash_major; 267252890Spfg 268252890Spfg if ((levels = rootp->h_info.h_ind_levels) > 1) 269252890Spfg goto error; 270252890Spfg 271252890Spfg entp = (struct ext2fs_htree_entry *)(((char *)&rootp->h_info) + 272252890Spfg rootp->h_info.h_info_len); 273252890Spfg 274252890Spfg if (ext2_htree_get_limit(entp) != 275252890Spfg ext2_htree_root_limit(ip, rootp->h_info.h_info_len)) 276252890Spfg goto error; 277252890Spfg 278252890Spfg while (1) { 279252890Spfg cnt = ext2_htree_get_count(entp); 280252890Spfg if (cnt == 0 || cnt > ext2_htree_get_limit(entp)) 281252890Spfg goto error; 282252890Spfg 283252890Spfg start = entp + 1; 284252890Spfg end = entp + cnt - 1; 285252890Spfg while (start <= end) { 286252890Spfg middle = start + (end - start) / 2; 287252890Spfg if (ext2_htree_get_hash(middle) > hash_major) 288252890Spfg end = middle - 1; 289252890Spfg else 290252890Spfg start = middle + 1; 291252890Spfg } 292252890Spfg found = start - 1; 293252890Spfg 294252890Spfg level_info = &(info->h_levels[info->h_levels_num - 1]); 295252890Spfg level_info->h_bp = bp; 296252890Spfg level_info->h_entries = entp; 297252890Spfg level_info->h_entry = found; 298252890Spfg if (levels == 0) 299252890Spfg return (0); 300252890Spfg levels--; 301252890Spfg if (ext2_blkatoff(vp, 302252890Spfg ext2_htree_get_block(found) * m_fs->e2fs_bsize, 303252890Spfg NULL, &bp) != 0) 304252890Spfg goto error; 305252890Spfg entp = ((struct ext2fs_htree_node *)bp->b_data)->h_entries; 306252890Spfg info->h_levels_num++; 307252890Spfg info->h_levels[info->h_levels_num - 1].h_bp = bp; 308252890Spfg } 309252890Spfg 310252890Spfgerror: 311252890Spfg ext2_htree_release(info); 312252890Spfg return (-1); 313252890Spfg} 314252890Spfg 315252890Spfg/* 316252907Spfg * Try to lookup a directory entry in HTree index 317252890Spfg */ 318252890Spfgint 319252890Spfgext2_htree_lookup(struct inode *ip, const char *name, int namelen, 320252890Spfg struct buf **bpp, int *entryoffp, doff_t *offp, 321252890Spfg doff_t *prevoffp, doff_t *endusefulp, 322252890Spfg struct ext2fs_searchslot *ss) 323252890Spfg{ 324252890Spfg struct vnode *vp; 325252890Spfg struct ext2fs_htree_lookup_info info; 326252890Spfg struct ext2fs_htree_entry *leaf_node; 327252890Spfg struct m_ext2fs *m_fs; 328252890Spfg struct buf *bp; 329252890Spfg uint32_t blk; 330252890Spfg uint32_t dirhash; 331252890Spfg uint32_t bsize; 332252890Spfg uint8_t hash_version; 333252890Spfg int search_next; 334252890Spfg int found = 0; 335252890Spfg 336252890Spfg m_fs = ip->i_e2fs; 337252890Spfg bsize = m_fs->e2fs_bsize; 338252890Spfg vp = ITOV(ip); 339252890Spfg 340252890Spfg /* TODO: print error msg because we don't lookup '.' and '..' */ 341252890Spfg 342252890Spfg memset(&info, 0, sizeof(info)); 343252890Spfg if (ext2_htree_find_leaf(ip, name, namelen, &dirhash, 344252890Spfg &hash_version, &info)) 345252890Spfg return (-1); 346252890Spfg 347252890Spfg do { 348252890Spfg leaf_node = info.h_levels[info.h_levels_num - 1].h_entry; 349252890Spfg blk = ext2_htree_get_block(leaf_node); 350252890Spfg if (ext2_blkatoff(vp, blk * bsize, NULL, &bp) != 0) { 351252890Spfg ext2_htree_release(&info); 352252890Spfg return (-1); 353252890Spfg } 354252890Spfg 355252890Spfg *offp = blk * bsize; 356252890Spfg *entryoffp = 0; 357252890Spfg *prevoffp = blk * bsize; 358252890Spfg *endusefulp = blk * bsize; 359252890Spfg 360252890Spfg if (ss->slotstatus == NONE) { 361252890Spfg ss->slotoffset = -1; 362252890Spfg ss->slotfreespace = 0; 363252890Spfg } 364252890Spfg 365252890Spfg if (ext2_search_dirblock(ip, bp->b_data, &found, 366252890Spfg name, namelen, entryoffp, offp, prevoffp, 367252890Spfg endusefulp, ss) != 0) { 368252890Spfg brelse(bp); 369252890Spfg ext2_htree_release(&info); 370252890Spfg return (-1); 371252890Spfg } 372252890Spfg 373252890Spfg if (found) { 374252890Spfg *bpp = bp; 375252890Spfg ext2_htree_release(&info); 376252890Spfg return (0); 377252890Spfg } 378252890Spfg 379252890Spfg brelse(bp); 380252890Spfg search_next = ext2_htree_check_next(ip, dirhash, name, &info); 381252890Spfg } while (search_next); 382252890Spfg 383252890Spfg ext2_htree_release(&info); 384252890Spfg return (ENOENT); 385252890Spfg} 386252890Spfg 387252890Spfgstatic int 388252890Spfgext2_htree_append_block(struct vnode *vp, char *data, 389252890Spfg struct componentname *cnp, uint32_t blksize) 390252890Spfg{ 391252890Spfg struct iovec aiov; 392252890Spfg struct uio auio; 393252890Spfg struct inode *dp = VTOI(vp); 394252890Spfg uint64_t cursize, newsize; 395252890Spfg int error; 396252890Spfg 397252890Spfg cursize = roundup(dp->i_size, blksize); 398252890Spfg newsize = roundup(dp->i_size, blksize) + blksize; 399252890Spfg 400252890Spfg auio.uio_offset = cursize; 401252890Spfg auio.uio_resid = blksize; 402252890Spfg aiov.iov_len = blksize; 403252890Spfg aiov.iov_base = data; 404252890Spfg auio.uio_iov = &aiov; 405252890Spfg auio.uio_iovcnt = 1; 406252890Spfg auio.uio_rw = UIO_WRITE; 407252890Spfg auio.uio_segflg = UIO_SYSSPACE; 408252890Spfg error = VOP_WRITE(vp, &auio, IO_SYNC, cnp->cn_cred); 409252890Spfg if (!error) 410252890Spfg dp->i_size = newsize; 411252890Spfg 412252890Spfg return (error); 413252890Spfg} 414252890Spfg 415252890Spfgstatic int 416252890Spfgext2_htree_writebuf(struct ext2fs_htree_lookup_info *info) 417252890Spfg{ 418252890Spfg int i, error; 419252890Spfg 420252890Spfg for (i = 0; i < info->h_levels_num; i++) { 421252890Spfg struct buf *bp = info->h_levels[i].h_bp; 422252890Spfg error = bwrite(bp); 423252890Spfg if (error) 424252890Spfg return (error); 425252890Spfg } 426252890Spfg 427252890Spfg return (0); 428252890Spfg} 429252890Spfg 430252890Spfgstatic void 431252890Spfgext2_htree_insert_entry_to_level(struct ext2fs_htree_lookup_level *level, 432252890Spfg uint32_t hash, uint32_t blk) 433252890Spfg{ 434252890Spfg struct ext2fs_htree_entry *target; 435252890Spfg int entries_num; 436252890Spfg 437252890Spfg target = level->h_entry + 1; 438252890Spfg entries_num = ext2_htree_get_count(level->h_entries); 439252890Spfg 440252890Spfg memmove(target + 1, target, (char *)(level->h_entries + entries_num) - 441252890Spfg (char *)target); 442252890Spfg ext2_htree_set_block(target, blk); 443252890Spfg ext2_htree_set_hash(target, hash); 444252890Spfg ext2_htree_set_count(level->h_entries, entries_num + 1); 445252890Spfg} 446252890Spfg 447252890Spfg/* 448252890Spfg * Insert an index entry to the index node. 449252890Spfg */ 450252890Spfgstatic void 451252890Spfgext2_htree_insert_entry(struct ext2fs_htree_lookup_info *info, 452252890Spfg uint32_t hash, uint32_t blk) 453252890Spfg{ 454252890Spfg struct ext2fs_htree_lookup_level *level; 455252890Spfg 456252890Spfg level = &info->h_levels[info->h_levels_num - 1]; 457252890Spfg ext2_htree_insert_entry_to_level(level, hash, blk); 458252890Spfg} 459252890Spfg 460252890Spfg/* 461252907Spfg * Compare two entry sort descriptors by name hash value. 462252890Spfg * This is used together with qsort. 463252890Spfg */ 464252890Spfgstatic int 465252890Spfgext2_htree_cmp_sort_entry(const void *e1, const void *e2) 466252890Spfg{ 467252890Spfg const struct ext2fs_htree_sort_entry *entry1, *entry2; 468252890Spfg 469252890Spfg entry1 = (const struct ext2fs_htree_sort_entry *)e1; 470252890Spfg entry2 = (const struct ext2fs_htree_sort_entry *)e2; 471252890Spfg 472252890Spfg if (entry1->h_hash < entry2->h_hash) 473252890Spfg return (-1); 474262943Spfg if (entry1->h_hash > entry2->h_hash) 475252890Spfg return (1); 476252890Spfg return (0); 477252890Spfg} 478252890Spfg 479252890Spfg/* 480252890Spfg * Append an entry to the end of the directory block. 481252890Spfg */ 482252890Spfgstatic void 483252890Spfgext2_append_entry(char *block, uint32_t blksize, 484252890Spfg struct ext2fs_direct_2 *last_entry, 485252890Spfg struct ext2fs_direct_2 *new_entry) 486252890Spfg{ 487252890Spfg uint16_t entry_len; 488252890Spfg 489252890Spfg entry_len = EXT2_DIR_REC_LEN(last_entry->e2d_namlen); 490252890Spfg last_entry->e2d_reclen = entry_len; 491252890Spfg last_entry = (struct ext2fs_direct_2 *)((char *)last_entry + entry_len); 492252890Spfg new_entry->e2d_reclen = block + blksize - (char *)last_entry; 493252890Spfg memcpy(last_entry, new_entry, EXT2_DIR_REC_LEN(new_entry->e2d_namlen)); 494252890Spfg} 495252890Spfg 496252890Spfg/* 497252890Spfg * Move half of entries from the old directory block to the new one. 498252890Spfg */ 499252890Spfgstatic int 500252890Spfgext2_htree_split_dirblock(char *block1, char *block2, uint32_t blksize, 501252890Spfg uint32_t *hash_seed, uint8_t hash_version, 502252890Spfg uint32_t *split_hash, struct ext2fs_direct_2 *entry) 503252890Spfg{ 504252890Spfg int entry_cnt = 0; 505252890Spfg int size = 0; 506252890Spfg int i, k; 507252890Spfg uint32_t offset; 508252890Spfg uint16_t entry_len = 0; 509252890Spfg uint32_t entry_hash; 510252890Spfg struct ext2fs_direct_2 *ep, *last; 511252890Spfg char *dest; 512252890Spfg struct ext2fs_htree_sort_entry *sort_info; 513252890Spfg 514252890Spfg ep = (struct ext2fs_direct_2 *)block1; 515252890Spfg dest = block2; 516252890Spfg sort_info = (struct ext2fs_htree_sort_entry *) 517252890Spfg ((char *)block2 + blksize); 518252890Spfg 519252890Spfg /* 520252890Spfg * Calculate name hash value for the entry which is to be added. 521252890Spfg */ 522252890Spfg ext2_htree_hash(entry->e2d_name, entry->e2d_namlen, hash_seed, 523252890Spfg hash_version, &entry_hash, NULL); 524252890Spfg 525252890Spfg /* 526252890Spfg * Fill in directory entry sort descriptors. 527252890Spfg */ 528252890Spfg while ((char *)ep < block1 + blksize) { 529252890Spfg if (ep->e2d_ino && ep->e2d_namlen) { 530252890Spfg entry_cnt++; 531252890Spfg sort_info--; 532252890Spfg sort_info->h_size = ep->e2d_reclen; 533252890Spfg sort_info->h_offset = (char *)ep - block1; 534252890Spfg ext2_htree_hash(ep->e2d_name, ep->e2d_namlen, 535252890Spfg hash_seed, hash_version, 536252890Spfg &sort_info->h_hash, NULL); 537252890Spfg } 538252890Spfg ep = (struct ext2fs_direct_2 *) 539252890Spfg ((char *)ep + ep->e2d_reclen); 540252890Spfg } 541252890Spfg 542252890Spfg /* 543252890Spfg * Sort directory entry descriptors by name hash value. 544252890Spfg */ 545252890Spfg qsort(sort_info, entry_cnt, sizeof(struct ext2fs_htree_sort_entry), 546252890Spfg ext2_htree_cmp_sort_entry); 547252890Spfg 548252890Spfg /* 549252890Spfg * Count the number of entries to move to directory block 2. 550252890Spfg */ 551252890Spfg for (i = entry_cnt - 1; i >= 0; i--) { 552252890Spfg if (sort_info[i].h_size + size > blksize / 2) 553252890Spfg break; 554252890Spfg size += sort_info[i].h_size; 555252890Spfg } 556252890Spfg 557252890Spfg *split_hash = sort_info[i + 1].h_hash; 558252890Spfg 559252890Spfg /* 560252890Spfg * Set collision bit. 561252890Spfg */ 562252890Spfg if (*split_hash == sort_info[i].h_hash) 563252890Spfg *split_hash += 1; 564252890Spfg 565252890Spfg /* 566252890Spfg * Move half of directory entries from block 1 to block 2. 567252890Spfg */ 568252890Spfg for (k = i + 1; k < entry_cnt; k++) { 569252890Spfg ep = (struct ext2fs_direct_2 *)((char *)block1 + 570252890Spfg sort_info[k].h_offset); 571252890Spfg entry_len = EXT2_DIR_REC_LEN(ep->e2d_namlen); 572252890Spfg memcpy(dest, ep, entry_len); 573252890Spfg ((struct ext2fs_direct_2 *)dest)->e2d_reclen = entry_len; 574252890Spfg /* Mark directory entry as unused. */ 575252890Spfg ep->e2d_ino = 0; 576252890Spfg dest += entry_len; 577252890Spfg } 578252890Spfg dest -= entry_len; 579252890Spfg 580252890Spfg /* Shrink directory entries in block 1. */ 581252890Spfg last = (struct ext2fs_direct_2 *)block1; 582252890Spfg entry_len = EXT2_DIR_REC_LEN(last->e2d_namlen); 583252890Spfg for (offset = last->e2d_reclen; offset < blksize; ) { 584252890Spfg ep = (struct ext2fs_direct_2 *)(block1 + offset); 585252890Spfg offset += ep->e2d_reclen; 586252890Spfg if (last->e2d_ino) { 587252907Spfg /* Trim the existing slot */ 588252890Spfg last->e2d_reclen = entry_len; 589252890Spfg last = (struct ext2fs_direct_2 *) 590252890Spfg ((char *)last + entry_len); 591252890Spfg } 592252890Spfg entry_len = EXT2_DIR_REC_LEN(ep->e2d_namlen); 593252890Spfg memcpy((void *)last, (void *)ep, entry_len); 594252890Spfg } 595252890Spfg 596252890Spfg if (entry_hash >= *split_hash) { 597252890Spfg /* Add entry to block 2. */ 598252890Spfg ext2_append_entry(block2, blksize, 599252890Spfg (struct ext2fs_direct_2 *)dest, entry); 600252890Spfg 601252890Spfg /* Adjust length field of last entry of block 1. */ 602252890Spfg last->e2d_reclen = block1 + blksize - (char *)last; 603252890Spfg } else { 604252890Spfg /* Add entry to block 1. */ 605252890Spfg ext2_append_entry(block1, blksize, last, entry); 606252890Spfg 607252890Spfg /* Adjust length field of last entry of block 2. */ 608252890Spfg ((struct ext2fs_direct_2 *)dest)->e2d_reclen = 609252890Spfg block2 + blksize - dest; 610252890Spfg } 611252890Spfg 612252890Spfg return (0); 613252890Spfg} 614252890Spfg 615252890Spfg/* 616252890Spfg * Create an HTree index for a directory 617252890Spfg */ 618252890Spfgint 619252890Spfgext2_htree_create_index(struct vnode *vp, struct componentname *cnp, 620252890Spfg struct ext2fs_direct_2 *new_entry) 621252890Spfg{ 622252890Spfg struct buf *bp = NULL; 623252890Spfg struct inode *dp; 624252890Spfg struct ext2fs *fs; 625252890Spfg struct m_ext2fs *m_fs; 626252890Spfg struct ext2fs_direct_2 *ep, *dotdot; 627252890Spfg struct ext2fs_htree_root *root; 628252890Spfg struct ext2fs_htree_lookup_info info; 629252890Spfg uint32_t blksize, dirlen, split_hash; 630252890Spfg uint8_t hash_version; 631252890Spfg char *buf1 = NULL; 632252890Spfg char *buf2 = NULL; 633252890Spfg int error = 0; 634252890Spfg 635252890Spfg dp = VTOI(vp); 636252890Spfg fs = dp->i_e2fs->e2fs; 637252890Spfg m_fs = dp->i_e2fs; 638252890Spfg blksize = m_fs->e2fs_bsize; 639252890Spfg 640252890Spfg buf1 = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO); 641252890Spfg buf2 = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO); 642252890Spfg 643252890Spfg if ((error = ext2_blkatoff(vp, 0, NULL, &bp)) != 0) 644252890Spfg goto out; 645252890Spfg 646252890Spfg root = (struct ext2fs_htree_root *)bp->b_data; 647252890Spfg dotdot = (struct ext2fs_direct_2 *)((char *)&(root->h_dotdot)); 648252890Spfg ep = (struct ext2fs_direct_2 *)((char *)dotdot + dotdot->e2d_reclen); 649252890Spfg dirlen = (char *)root + blksize - (char *)ep; 650252890Spfg memcpy(buf1, ep, dirlen); 651252890Spfg ep = (struct ext2fs_direct_2 *)buf1; 652252890Spfg while ((char *)ep < buf1 + dirlen) 653252890Spfg ep = (struct ext2fs_direct_2 *) 654252890Spfg ((char *)ep + ep->e2d_reclen); 655252890Spfg ep->e2d_reclen = buf1 + blksize - (char *)ep; 656252890Spfg 657261311Spfg dp->i_flag |= IN_E4INDEX; 658252890Spfg 659252890Spfg /* 660252890Spfg * Initialize index root. 661252890Spfg */ 662252890Spfg dotdot->e2d_reclen = blksize - EXT2_DIR_REC_LEN(1); 663252890Spfg memset(&root->h_info, 0, sizeof(root->h_info)); 664252890Spfg root->h_info.h_hash_version = fs->e3fs_def_hash_version; 665252890Spfg root->h_info.h_info_len = sizeof(root->h_info); 666252890Spfg ext2_htree_set_block(root->h_entries, 1); 667252890Spfg ext2_htree_set_count(root->h_entries, 1); 668252890Spfg ext2_htree_set_limit(root->h_entries, 669252890Spfg ext2_htree_root_limit(dp, sizeof(root->h_info))); 670252890Spfg 671252890Spfg memset(&info, 0, sizeof(info)); 672252890Spfg info.h_levels_num = 1; 673252890Spfg info.h_levels[0].h_entries = root->h_entries; 674252890Spfg info.h_levels[0].h_entry = root->h_entries; 675252890Spfg 676252890Spfg hash_version = root->h_info.h_hash_version; 677252890Spfg if (hash_version <= EXT2_HTREE_TEA) 678252890Spfg hash_version += m_fs->e2fs_uhash; 679252890Spfg ext2_htree_split_dirblock(buf1, buf2, blksize, fs->e3fs_hash_seed, 680252890Spfg hash_version, &split_hash, new_entry); 681252890Spfg ext2_htree_insert_entry(&info, split_hash, 2); 682252890Spfg 683252890Spfg /* 684252890Spfg * Write directory block 0. 685252890Spfg */ 686252890Spfg if (DOINGASYNC(vp)) { 687252890Spfg bdwrite(bp); 688252890Spfg error = 0; 689252890Spfg } else { 690252890Spfg error = bwrite(bp); 691252890Spfg } 692252890Spfg dp->i_flag |= IN_CHANGE | IN_UPDATE; 693252890Spfg if (error) 694252890Spfg goto out; 695252890Spfg 696252890Spfg /* 697252890Spfg * Write directory block 1. 698252890Spfg */ 699252890Spfg error = ext2_htree_append_block(vp, buf1, cnp, blksize); 700252890Spfg if (error) 701252890Spfg goto out1; 702252890Spfg 703252890Spfg /* 704252890Spfg * Write directory block 2. 705252890Spfg */ 706252890Spfg error = ext2_htree_append_block(vp, buf2, cnp, blksize); 707252890Spfg 708252890Spfg free(buf1, M_TEMP); 709252890Spfg free(buf2, M_TEMP); 710252890Spfg return (error); 711252890Spfgout: 712252890Spfg if (bp != NULL) 713252890Spfg brelse(bp); 714252890Spfgout1: 715252890Spfg free(buf1, M_TEMP); 716252890Spfg free(buf2, M_TEMP); 717252890Spfg return (error); 718252890Spfg} 719252890Spfg 720252890Spfg/* 721252890Spfg * Add an entry to the directory using htree index. 722252890Spfg */ 723252890Spfgint 724252890Spfgext2_htree_add_entry(struct vnode *dvp, struct ext2fs_direct_2 *entry, 725252890Spfg struct componentname *cnp) 726252890Spfg{ 727252890Spfg struct ext2fs_htree_entry *entries, *leaf_node; 728252890Spfg struct ext2fs_htree_lookup_info info; 729252890Spfg struct buf *bp = NULL; 730252890Spfg struct ext2fs *fs; 731252890Spfg struct m_ext2fs *m_fs; 732252890Spfg struct inode *ip; 733252890Spfg uint16_t ent_num; 734252890Spfg uint32_t dirhash, split_hash; 735252890Spfg uint32_t blksize, blknum; 736252890Spfg uint64_t cursize, dirsize; 737252890Spfg uint8_t hash_version; 738252890Spfg char *newdirblock = NULL; 739252890Spfg char *newidxblock = NULL; 740252890Spfg struct ext2fs_htree_node *dst_node; 741252890Spfg struct ext2fs_htree_entry *dst_entries; 742252890Spfg struct ext2fs_htree_entry *root_entires; 743252890Spfg struct buf *dst_bp = NULL; 744252890Spfg int error, write_bp = 0, write_dst_bp = 0, write_info = 0; 745252890Spfg 746252890Spfg ip = VTOI(dvp); 747252890Spfg m_fs = ip->i_e2fs; 748252890Spfg fs = m_fs->e2fs; 749252890Spfg blksize = m_fs->e2fs_bsize; 750252890Spfg 751252890Spfg if (ip->i_count != 0) 752252890Spfg return ext2_add_entry(dvp, entry); 753252890Spfg 754252890Spfg /* Target directory block is full, split it */ 755252890Spfg memset(&info, 0, sizeof(info)); 756252890Spfg error = ext2_htree_find_leaf(ip, entry->e2d_name, entry->e2d_namlen, 757252890Spfg &dirhash, &hash_version, &info); 758252890Spfg if (error) 759252890Spfg return (error); 760252890Spfg 761252890Spfg entries = info.h_levels[info.h_levels_num - 1].h_entries; 762252890Spfg ent_num = ext2_htree_get_count(entries); 763252890Spfg if (ent_num == ext2_htree_get_limit(entries)) { 764252890Spfg /* Split the index node. */ 765252890Spfg root_entires = info.h_levels[0].h_entries; 766252890Spfg newidxblock = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO); 767252890Spfg dst_node = (struct ext2fs_htree_node *)newidxblock; 768252890Spfg dst_entries = dst_node->h_entries; 769252890Spfg memset(&dst_node->h_fake_dirent, 0, 770252890Spfg sizeof(dst_node->h_fake_dirent)); 771252890Spfg dst_node->h_fake_dirent.e2d_reclen = blksize; 772252890Spfg 773252890Spfg cursize = roundup(ip->i_size, blksize); 774252890Spfg dirsize = roundup(ip->i_size, blksize) + blksize; 775252890Spfg blknum = dirsize / blksize - 1; 776252890Spfg 777252890Spfg error = ext2_htree_append_block(dvp, newidxblock, 778252890Spfg cnp, blksize); 779252890Spfg if (error) 780252890Spfg goto finish; 781252890Spfg error = ext2_blkatoff(dvp, cursize, NULL, &dst_bp); 782252890Spfg if (error) 783252890Spfg goto finish; 784252890Spfg dst_node = (struct ext2fs_htree_node *)dst_bp->b_data; 785252890Spfg dst_entries = dst_node->h_entries; 786252890Spfg 787252890Spfg if (info.h_levels_num == 2) { 788252890Spfg uint16_t src_ent_num, dst_ent_num; 789252890Spfg 790252890Spfg if (ext2_htree_get_count(root_entires) == 791252890Spfg ext2_htree_get_limit(root_entires)) { 792252890Spfg /* Directory index is full */ 793252890Spfg error = EIO; 794252890Spfg goto finish; 795252890Spfg } 796252890Spfg 797252890Spfg src_ent_num = ent_num / 2; 798252890Spfg dst_ent_num = ent_num - src_ent_num; 799252890Spfg split_hash = ext2_htree_get_hash(entries + src_ent_num); 800252890Spfg 801252890Spfg /* Move half of index entries to the new index node */ 802252890Spfg memcpy(dst_entries, entries + src_ent_num, 803252890Spfg dst_ent_num * sizeof(struct ext2fs_htree_entry)); 804252890Spfg ext2_htree_set_count(entries, src_ent_num); 805252890Spfg ext2_htree_set_count(dst_entries, dst_ent_num); 806252890Spfg ext2_htree_set_limit(dst_entries, 807252890Spfg ext2_htree_node_limit(ip)); 808252890Spfg 809252890Spfg if (info.h_levels[1].h_entry >= entries + src_ent_num) { 810252890Spfg struct buf *tmp = info.h_levels[1].h_bp; 811252890Spfg info.h_levels[1].h_bp = dst_bp; 812252890Spfg dst_bp = tmp; 813252890Spfg 814252890Spfg info.h_levels[1].h_entry = 815252890Spfg info.h_levels[1].h_entry - 816252890Spfg (entries + src_ent_num) + 817252890Spfg dst_entries; 818252890Spfg info.h_levels[1].h_entries = dst_entries; 819252890Spfg } 820252890Spfg ext2_htree_insert_entry_to_level(&info.h_levels[0], 821252890Spfg split_hash, blknum); 822252890Spfg 823252890Spfg /* Write new index node to disk */ 824252890Spfg error = bwrite(dst_bp); 825252890Spfg ip->i_flag |= IN_CHANGE | IN_UPDATE; 826252890Spfg if (error) 827252890Spfg goto finish; 828252890Spfg write_dst_bp = 1; 829252890Spfg } else { 830252890Spfg /* Create second level for htree index */ 831252890Spfg struct ext2fs_htree_root *idx_root; 832252890Spfg 833252890Spfg memcpy(dst_entries, entries, 834252890Spfg ent_num * sizeof(struct ext2fs_htree_entry)); 835252890Spfg ext2_htree_set_limit(dst_entries, 836252890Spfg ext2_htree_node_limit(ip)); 837252890Spfg 838252890Spfg idx_root = (struct ext2fs_htree_root *) 839252890Spfg info.h_levels[0].h_bp->b_data; 840252890Spfg idx_root->h_info.h_ind_levels = 1; 841252890Spfg 842252890Spfg ext2_htree_set_count(entries, 1); 843252890Spfg ext2_htree_set_block(entries, blknum); 844252890Spfg 845252890Spfg info.h_levels_num = 2; 846252890Spfg info.h_levels[1].h_entries = dst_entries; 847252890Spfg info.h_levels[1].h_entry = info.h_levels[0].h_entry - 848252890Spfg info.h_levels[0].h_entries + dst_entries; 849252890Spfg info.h_levels[1].h_bp = dst_bp; 850252890Spfg } 851252890Spfg } 852252890Spfg 853252890Spfg leaf_node = info.h_levels[info.h_levels_num - 1].h_entry; 854252890Spfg blknum = ext2_htree_get_block(leaf_node); 855252890Spfg error = ext2_blkatoff(dvp, blknum * blksize, NULL, &bp); 856252890Spfg if (error) 857252890Spfg goto finish; 858252890Spfg 859252890Spfg /* Split target directory block */ 860252890Spfg newdirblock = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO); 861252890Spfg ext2_htree_split_dirblock((char *)bp->b_data, newdirblock, blksize, 862252890Spfg fs->e3fs_hash_seed, hash_version, &split_hash, entry); 863252890Spfg cursize = roundup(ip->i_size, blksize); 864252890Spfg dirsize = roundup(ip->i_size, blksize) + blksize; 865252890Spfg blknum = dirsize / blksize - 1; 866252890Spfg 867252890Spfg /* Add index entry for the new directory block */ 868252890Spfg ext2_htree_insert_entry(&info, split_hash, blknum); 869252890Spfg 870252890Spfg /* Write the new directory block to the end of the directory */ 871252890Spfg error = ext2_htree_append_block(dvp, newdirblock, cnp, blksize); 872252890Spfg if (error) 873252890Spfg goto finish; 874252890Spfg 875252890Spfg /* Write the target directory block */ 876252890Spfg error = bwrite(bp); 877252890Spfg ip->i_flag |= IN_CHANGE | IN_UPDATE; 878252890Spfg if (error) 879252890Spfg goto finish; 880252890Spfg write_bp = 1; 881252890Spfg 882252890Spfg /* Write the index block */ 883252890Spfg error = ext2_htree_writebuf(&info); 884252890Spfg if (!error) 885252890Spfg write_info = 1; 886252890Spfg 887252890Spfgfinish: 888252890Spfg if (dst_bp != NULL && !write_dst_bp) 889252890Spfg brelse(dst_bp); 890252890Spfg if (bp != NULL && !write_bp) 891252890Spfg brelse(bp); 892252890Spfg if (newdirblock != NULL) 893252890Spfg free(newdirblock, M_TEMP); 894252890Spfg if (newidxblock != NULL) 895252890Spfg free(newidxblock, M_TEMP); 896252890Spfg if (!write_info) 897252890Spfg ext2_htree_release(&info); 898252890Spfg return (error); 899252890Spfg} 900