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: stable/11/sys/fs/ext2fs/ext2_htree.c 314225 2017-02-24 21:35:53Z pfg $ 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, 63262623Spfg 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) && 93294653Spfg ip->i_flag & IN_E3INDEX) 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, 101311231Spfg 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{ 194298518Spfg u_int i; 195252890Spfg 196252890Spfg for (i = 0; i < info->h_levels_num; i++) { 197252890Spfg struct buf *bp = info->h_levels[i].h_bp; 198311231Spfg 199252890Spfg if (bp != NULL) 200252890Spfg brelse(bp); 201252890Spfg } 202252890Spfg} 203252890Spfg 204252890Spfgstatic uint32_t 205252890Spfgext2_htree_root_limit(struct inode *ip, int len) 206252890Spfg{ 207252890Spfg uint32_t space; 208252890Spfg 209252890Spfg space = ip->i_e2fs->e2fs_bsize - EXT2_DIR_REC_LEN(1) - 210252890Spfg EXT2_DIR_REC_LEN(2) - len; 211252890Spfg return (space / sizeof(struct ext2fs_htree_entry)); 212252890Spfg} 213252890Spfg 214252890Spfgstatic uint32_t 215252890Spfgext2_htree_node_limit(struct inode *ip) 216252890Spfg{ 217252890Spfg struct m_ext2fs *fs; 218252890Spfg uint32_t space; 219252890Spfg 220252890Spfg fs = ip->i_e2fs; 221252890Spfg space = fs->e2fs_bsize - EXT2_DIR_REC_LEN(0); 222252890Spfg 223252890Spfg return (space / sizeof(struct ext2fs_htree_entry)); 224252890Spfg} 225252890Spfg 226252890Spfgstatic int 227252890Spfgext2_htree_find_leaf(struct inode *ip, const char *name, int namelen, 228311231Spfg uint32_t *hash, uint8_t *hash_ver, 229311231Spfg struct ext2fs_htree_lookup_info *info) 230252890Spfg{ 231252890Spfg struct vnode *vp; 232252890Spfg struct ext2fs *fs; 233252890Spfg struct m_ext2fs *m_fs; 234252890Spfg struct buf *bp = NULL; 235252890Spfg struct ext2fs_htree_root *rootp; 236252890Spfg struct ext2fs_htree_entry *entp, *start, *end, *middle, *found; 237252890Spfg struct ext2fs_htree_lookup_level *level_info; 238252890Spfg uint32_t hash_major = 0, hash_minor = 0; 239252890Spfg uint32_t levels, cnt; 240252890Spfg uint8_t hash_version; 241252890Spfg 242252890Spfg if (name == NULL || info == NULL) 243252890Spfg return (-1); 244252890Spfg 245252890Spfg vp = ITOV(ip); 246252890Spfg fs = ip->i_e2fs->e2fs; 247252890Spfg m_fs = ip->i_e2fs; 248252890Spfg 249252890Spfg if (ext2_blkatoff(vp, 0, NULL, &bp) != 0) 250252890Spfg return (-1); 251252890Spfg 252252890Spfg info->h_levels_num = 1; 253252890Spfg info->h_levels[0].h_bp = bp; 254252890Spfg rootp = (struct ext2fs_htree_root *)bp->b_data; 255252890Spfg if (rootp->h_info.h_hash_version != EXT2_HTREE_LEGACY && 256252890Spfg rootp->h_info.h_hash_version != EXT2_HTREE_HALF_MD4 && 257252890Spfg rootp->h_info.h_hash_version != EXT2_HTREE_TEA) 258252890Spfg goto error; 259252890Spfg 260252890Spfg hash_version = rootp->h_info.h_hash_version; 261252890Spfg if (hash_version <= EXT2_HTREE_TEA) 262252890Spfg hash_version += m_fs->e2fs_uhash; 263252890Spfg *hash_ver = hash_version; 264252890Spfg 265252890Spfg ext2_htree_hash(name, namelen, fs->e3fs_hash_seed, 266252890Spfg hash_version, &hash_major, &hash_minor); 267252890Spfg *hash = hash_major; 268252890Spfg 269252890Spfg if ((levels = rootp->h_info.h_ind_levels) > 1) 270252890Spfg goto error; 271252890Spfg 272252890Spfg entp = (struct ext2fs_htree_entry *)(((char *)&rootp->h_info) + 273252890Spfg rootp->h_info.h_info_len); 274252890Spfg 275252890Spfg if (ext2_htree_get_limit(entp) != 276252890Spfg ext2_htree_root_limit(ip, rootp->h_info.h_info_len)) 277252890Spfg goto error; 278252890Spfg 279252890Spfg while (1) { 280252890Spfg cnt = ext2_htree_get_count(entp); 281252890Spfg if (cnt == 0 || cnt > ext2_htree_get_limit(entp)) 282252890Spfg goto error; 283252890Spfg 284252890Spfg start = entp + 1; 285252890Spfg end = entp + cnt - 1; 286252890Spfg while (start <= end) { 287252890Spfg middle = start + (end - start) / 2; 288252890Spfg if (ext2_htree_get_hash(middle) > hash_major) 289252890Spfg end = middle - 1; 290252890Spfg else 291252890Spfg start = middle + 1; 292252890Spfg } 293252890Spfg found = start - 1; 294252890Spfg 295252890Spfg level_info = &(info->h_levels[info->h_levels_num - 1]); 296252890Spfg level_info->h_bp = bp; 297252890Spfg level_info->h_entries = entp; 298252890Spfg level_info->h_entry = found; 299252890Spfg if (levels == 0) 300252890Spfg return (0); 301252890Spfg levels--; 302252890Spfg if (ext2_blkatoff(vp, 303252890Spfg ext2_htree_get_block(found) * m_fs->e2fs_bsize, 304252890Spfg NULL, &bp) != 0) 305252890Spfg goto error; 306252890Spfg entp = ((struct ext2fs_htree_node *)bp->b_data)->h_entries; 307252890Spfg info->h_levels_num++; 308252890Spfg info->h_levels[info->h_levels_num - 1].h_bp = bp; 309252890Spfg } 310252890Spfg 311252890Spfgerror: 312252890Spfg ext2_htree_release(info); 313252890Spfg return (-1); 314252890Spfg} 315252890Spfg 316252890Spfg/* 317252907Spfg * Try to lookup a directory entry in HTree index 318252890Spfg */ 319252890Spfgint 320252890Spfgext2_htree_lookup(struct inode *ip, const char *name, int namelen, 321311231Spfg struct buf **bpp, int *entryoffp, doff_t *offp, 322311231Spfg doff_t *prevoffp, doff_t *endusefulp, 323311231Spfg struct ext2fs_searchslot *ss) 324252890Spfg{ 325252890Spfg struct vnode *vp; 326252890Spfg struct ext2fs_htree_lookup_info info; 327252890Spfg struct ext2fs_htree_entry *leaf_node; 328252890Spfg struct m_ext2fs *m_fs; 329252890Spfg struct buf *bp; 330252890Spfg uint32_t blk; 331252890Spfg uint32_t dirhash; 332252890Spfg uint32_t bsize; 333252890Spfg uint8_t hash_version; 334252890Spfg int search_next; 335252890Spfg int found = 0; 336252890Spfg 337252890Spfg m_fs = ip->i_e2fs; 338252890Spfg bsize = m_fs->e2fs_bsize; 339252890Spfg vp = ITOV(ip); 340252890Spfg 341252890Spfg /* TODO: print error msg because we don't lookup '.' and '..' */ 342252890Spfg 343252890Spfg memset(&info, 0, sizeof(info)); 344252890Spfg if (ext2_htree_find_leaf(ip, name, namelen, &dirhash, 345252890Spfg &hash_version, &info)) 346252890Spfg return (-1); 347252890Spfg 348252890Spfg do { 349252890Spfg leaf_node = info.h_levels[info.h_levels_num - 1].h_entry; 350252890Spfg blk = ext2_htree_get_block(leaf_node); 351252890Spfg if (ext2_blkatoff(vp, blk * bsize, NULL, &bp) != 0) { 352252890Spfg ext2_htree_release(&info); 353252890Spfg return (-1); 354252890Spfg } 355252890Spfg 356252890Spfg *offp = blk * bsize; 357252890Spfg *entryoffp = 0; 358252890Spfg *prevoffp = blk * bsize; 359252890Spfg *endusefulp = blk * bsize; 360252890Spfg 361252890Spfg if (ss->slotstatus == NONE) { 362252890Spfg ss->slotoffset = -1; 363252890Spfg ss->slotfreespace = 0; 364252890Spfg } 365252890Spfg 366252890Spfg if (ext2_search_dirblock(ip, bp->b_data, &found, 367252890Spfg name, namelen, entryoffp, offp, prevoffp, 368252890Spfg endusefulp, ss) != 0) { 369252890Spfg brelse(bp); 370252890Spfg ext2_htree_release(&info); 371252890Spfg return (-1); 372252890Spfg } 373252890Spfg 374252890Spfg if (found) { 375252890Spfg *bpp = bp; 376252890Spfg ext2_htree_release(&info); 377252890Spfg return (0); 378252890Spfg } 379252890Spfg 380252890Spfg brelse(bp); 381252890Spfg search_next = ext2_htree_check_next(ip, dirhash, name, &info); 382252890Spfg } while (search_next); 383252890Spfg 384252890Spfg ext2_htree_release(&info); 385252890Spfg return (ENOENT); 386252890Spfg} 387252890Spfg 388252890Spfgstatic int 389252890Spfgext2_htree_append_block(struct vnode *vp, char *data, 390311231Spfg struct componentname *cnp, uint32_t blksize) 391252890Spfg{ 392252890Spfg struct iovec aiov; 393252890Spfg struct uio auio; 394252890Spfg struct inode *dp = VTOI(vp); 395252890Spfg uint64_t cursize, newsize; 396252890Spfg int error; 397252890Spfg 398252890Spfg cursize = roundup(dp->i_size, blksize); 399277354Spfg newsize = cursize + blksize; 400252890Spfg 401252890Spfg auio.uio_offset = cursize; 402252890Spfg auio.uio_resid = blksize; 403252890Spfg aiov.iov_len = blksize; 404252890Spfg aiov.iov_base = data; 405252890Spfg auio.uio_iov = &aiov; 406252890Spfg auio.uio_iovcnt = 1; 407252890Spfg auio.uio_rw = UIO_WRITE; 408252890Spfg auio.uio_segflg = UIO_SYSSPACE; 409252890Spfg error = VOP_WRITE(vp, &auio, IO_SYNC, cnp->cn_cred); 410252890Spfg if (!error) 411252890Spfg dp->i_size = newsize; 412252890Spfg 413252890Spfg return (error); 414252890Spfg} 415252890Spfg 416252890Spfgstatic int 417252890Spfgext2_htree_writebuf(struct ext2fs_htree_lookup_info *info) 418252890Spfg{ 419252890Spfg int i, error; 420252890Spfg 421252890Spfg for (i = 0; i < info->h_levels_num; i++) { 422252890Spfg struct buf *bp = info->h_levels[i].h_bp; 423311231Spfg 424252890Spfg error = bwrite(bp); 425252890Spfg if (error) 426252890Spfg return (error); 427252890Spfg } 428252890Spfg 429252890Spfg return (0); 430252890Spfg} 431252890Spfg 432252890Spfgstatic void 433252890Spfgext2_htree_insert_entry_to_level(struct ext2fs_htree_lookup_level *level, 434311231Spfg uint32_t hash, uint32_t blk) 435252890Spfg{ 436252890Spfg struct ext2fs_htree_entry *target; 437252890Spfg int entries_num; 438252890Spfg 439252890Spfg target = level->h_entry + 1; 440252890Spfg entries_num = ext2_htree_get_count(level->h_entries); 441252890Spfg 442252890Spfg memmove(target + 1, target, (char *)(level->h_entries + entries_num) - 443252890Spfg (char *)target); 444252890Spfg ext2_htree_set_block(target, blk); 445252890Spfg ext2_htree_set_hash(target, hash); 446252890Spfg ext2_htree_set_count(level->h_entries, entries_num + 1); 447252890Spfg} 448252890Spfg 449252890Spfg/* 450252890Spfg * Insert an index entry to the index node. 451252890Spfg */ 452252890Spfgstatic void 453252890Spfgext2_htree_insert_entry(struct ext2fs_htree_lookup_info *info, 454311231Spfg uint32_t hash, uint32_t blk) 455252890Spfg{ 456252890Spfg struct ext2fs_htree_lookup_level *level; 457252890Spfg 458252890Spfg level = &info->h_levels[info->h_levels_num - 1]; 459252890Spfg ext2_htree_insert_entry_to_level(level, hash, blk); 460252890Spfg} 461252890Spfg 462252890Spfg/* 463252907Spfg * Compare two entry sort descriptors by name hash value. 464252890Spfg * This is used together with qsort. 465252890Spfg */ 466252890Spfgstatic int 467252890Spfgext2_htree_cmp_sort_entry(const void *e1, const void *e2) 468252890Spfg{ 469252890Spfg const struct ext2fs_htree_sort_entry *entry1, *entry2; 470252890Spfg 471252890Spfg entry1 = (const struct ext2fs_htree_sort_entry *)e1; 472252890Spfg entry2 = (const struct ext2fs_htree_sort_entry *)e2; 473252890Spfg 474252890Spfg if (entry1->h_hash < entry2->h_hash) 475252890Spfg return (-1); 476262869Spfg if (entry1->h_hash > entry2->h_hash) 477252890Spfg return (1); 478252890Spfg return (0); 479252890Spfg} 480252890Spfg 481252890Spfg/* 482252890Spfg * Append an entry to the end of the directory block. 483252890Spfg */ 484252890Spfgstatic void 485252890Spfgext2_append_entry(char *block, uint32_t blksize, 486311231Spfg struct ext2fs_direct_2 *last_entry, 487311231Spfg struct ext2fs_direct_2 *new_entry) 488252890Spfg{ 489252890Spfg uint16_t entry_len; 490252890Spfg 491252890Spfg entry_len = EXT2_DIR_REC_LEN(last_entry->e2d_namlen); 492252890Spfg last_entry->e2d_reclen = entry_len; 493252890Spfg last_entry = (struct ext2fs_direct_2 *)((char *)last_entry + entry_len); 494252890Spfg new_entry->e2d_reclen = block + blksize - (char *)last_entry; 495252890Spfg memcpy(last_entry, new_entry, EXT2_DIR_REC_LEN(new_entry->e2d_namlen)); 496252890Spfg} 497252890Spfg 498252890Spfg/* 499252890Spfg * Move half of entries from the old directory block to the new one. 500252890Spfg */ 501252890Spfgstatic int 502252890Spfgext2_htree_split_dirblock(char *block1, char *block2, uint32_t blksize, 503311231Spfg uint32_t *hash_seed, uint8_t hash_version, 504311231Spfg uint32_t *split_hash, struct ext2fs_direct_2 *entry) 505252890Spfg{ 506252890Spfg int entry_cnt = 0; 507252890Spfg int size = 0; 508252890Spfg int i, k; 509252890Spfg uint32_t offset; 510252890Spfg uint16_t entry_len = 0; 511252890Spfg uint32_t entry_hash; 512252890Spfg struct ext2fs_direct_2 *ep, *last; 513252890Spfg char *dest; 514252890Spfg struct ext2fs_htree_sort_entry *sort_info; 515252890Spfg 516252890Spfg ep = (struct ext2fs_direct_2 *)block1; 517252890Spfg dest = block2; 518252890Spfg sort_info = (struct ext2fs_htree_sort_entry *) 519252890Spfg ((char *)block2 + blksize); 520252890Spfg 521252890Spfg /* 522252890Spfg * Calculate name hash value for the entry which is to be added. 523252890Spfg */ 524252890Spfg ext2_htree_hash(entry->e2d_name, entry->e2d_namlen, hash_seed, 525252890Spfg hash_version, &entry_hash, NULL); 526252890Spfg 527252890Spfg /* 528252890Spfg * Fill in directory entry sort descriptors. 529252890Spfg */ 530252890Spfg while ((char *)ep < block1 + blksize) { 531252890Spfg if (ep->e2d_ino && ep->e2d_namlen) { 532252890Spfg entry_cnt++; 533252890Spfg sort_info--; 534252890Spfg sort_info->h_size = ep->e2d_reclen; 535252890Spfg sort_info->h_offset = (char *)ep - block1; 536252890Spfg ext2_htree_hash(ep->e2d_name, ep->e2d_namlen, 537252890Spfg hash_seed, hash_version, 538252890Spfg &sort_info->h_hash, NULL); 539252890Spfg } 540252890Spfg ep = (struct ext2fs_direct_2 *) 541252890Spfg ((char *)ep + ep->e2d_reclen); 542252890Spfg } 543252890Spfg 544252890Spfg /* 545252890Spfg * Sort directory entry descriptors by name hash value. 546252890Spfg */ 547252890Spfg qsort(sort_info, entry_cnt, sizeof(struct ext2fs_htree_sort_entry), 548252890Spfg ext2_htree_cmp_sort_entry); 549252890Spfg 550252890Spfg /* 551252890Spfg * Count the number of entries to move to directory block 2. 552252890Spfg */ 553252890Spfg for (i = entry_cnt - 1; i >= 0; i--) { 554252890Spfg if (sort_info[i].h_size + size > blksize / 2) 555252890Spfg break; 556252890Spfg size += sort_info[i].h_size; 557252890Spfg } 558252890Spfg 559252890Spfg *split_hash = sort_info[i + 1].h_hash; 560252890Spfg 561252890Spfg /* 562252890Spfg * Set collision bit. 563252890Spfg */ 564252890Spfg if (*split_hash == sort_info[i].h_hash) 565252890Spfg *split_hash += 1; 566252890Spfg 567252890Spfg /* 568252890Spfg * Move half of directory entries from block 1 to block 2. 569252890Spfg */ 570252890Spfg for (k = i + 1; k < entry_cnt; k++) { 571252890Spfg ep = (struct ext2fs_direct_2 *)((char *)block1 + 572252890Spfg sort_info[k].h_offset); 573252890Spfg entry_len = EXT2_DIR_REC_LEN(ep->e2d_namlen); 574252890Spfg memcpy(dest, ep, entry_len); 575252890Spfg ((struct ext2fs_direct_2 *)dest)->e2d_reclen = entry_len; 576252890Spfg /* Mark directory entry as unused. */ 577252890Spfg ep->e2d_ino = 0; 578252890Spfg dest += entry_len; 579252890Spfg } 580252890Spfg dest -= entry_len; 581252890Spfg 582252890Spfg /* Shrink directory entries in block 1. */ 583252890Spfg last = (struct ext2fs_direct_2 *)block1; 584294504Spfg entry_len = 0; 585294504Spfg for (offset = 0; offset < blksize; ) { 586252890Spfg ep = (struct ext2fs_direct_2 *)(block1 + offset); 587252890Spfg offset += ep->e2d_reclen; 588294504Spfg if (ep->e2d_ino) { 589252890Spfg last = (struct ext2fs_direct_2 *) 590311231Spfg ((char *)last + entry_len); 591294504Spfg entry_len = EXT2_DIR_REC_LEN(ep->e2d_namlen); 592294504Spfg memcpy((void *)last, (void *)ep, entry_len); 593294504Spfg last->e2d_reclen = entry_len; 594252890Spfg } 595252890Spfg } 596252890Spfg 597252890Spfg if (entry_hash >= *split_hash) { 598252890Spfg /* Add entry to block 2. */ 599252890Spfg ext2_append_entry(block2, blksize, 600252890Spfg (struct ext2fs_direct_2 *)dest, entry); 601252890Spfg 602252890Spfg /* Adjust length field of last entry of block 1. */ 603252890Spfg last->e2d_reclen = block1 + blksize - (char *)last; 604252890Spfg } else { 605252890Spfg /* Add entry to block 1. */ 606252890Spfg ext2_append_entry(block1, blksize, last, entry); 607252890Spfg 608252890Spfg /* Adjust length field of last entry of block 2. */ 609252890Spfg ((struct ext2fs_direct_2 *)dest)->e2d_reclen = 610252890Spfg block2 + blksize - dest; 611252890Spfg } 612252890Spfg 613252890Spfg return (0); 614252890Spfg} 615252890Spfg 616252890Spfg/* 617252890Spfg * Create an HTree index for a directory 618252890Spfg */ 619252890Spfgint 620252890Spfgext2_htree_create_index(struct vnode *vp, struct componentname *cnp, 621311231Spfg struct ext2fs_direct_2 *new_entry) 622252890Spfg{ 623252890Spfg struct buf *bp = NULL; 624252890Spfg struct inode *dp; 625252890Spfg struct ext2fs *fs; 626252890Spfg struct m_ext2fs *m_fs; 627252890Spfg struct ext2fs_direct_2 *ep, *dotdot; 628252890Spfg struct ext2fs_htree_root *root; 629252890Spfg struct ext2fs_htree_lookup_info info; 630252890Spfg uint32_t blksize, dirlen, split_hash; 631252890Spfg uint8_t hash_version; 632252890Spfg char *buf1 = NULL; 633252890Spfg char *buf2 = NULL; 634252890Spfg int error = 0; 635252890Spfg 636252890Spfg dp = VTOI(vp); 637252890Spfg fs = dp->i_e2fs->e2fs; 638252890Spfg m_fs = dp->i_e2fs; 639252890Spfg blksize = m_fs->e2fs_bsize; 640252890Spfg 641252890Spfg buf1 = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO); 642252890Spfg buf2 = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO); 643252890Spfg 644252890Spfg if ((error = ext2_blkatoff(vp, 0, NULL, &bp)) != 0) 645252890Spfg goto out; 646252890Spfg 647252890Spfg root = (struct ext2fs_htree_root *)bp->b_data; 648252890Spfg dotdot = (struct ext2fs_direct_2 *)((char *)&(root->h_dotdot)); 649252890Spfg ep = (struct ext2fs_direct_2 *)((char *)dotdot + dotdot->e2d_reclen); 650252890Spfg dirlen = (char *)root + blksize - (char *)ep; 651252890Spfg memcpy(buf1, ep, dirlen); 652252890Spfg ep = (struct ext2fs_direct_2 *)buf1; 653252890Spfg while ((char *)ep < buf1 + dirlen) 654252890Spfg ep = (struct ext2fs_direct_2 *) 655252890Spfg ((char *)ep + ep->e2d_reclen); 656252890Spfg ep->e2d_reclen = buf1 + blksize - (char *)ep; 657252890Spfg 658294653Spfg dp->i_flag |= IN_E3INDEX; 659252890Spfg 660252890Spfg /* 661252890Spfg * Initialize index root. 662252890Spfg */ 663252890Spfg dotdot->e2d_reclen = blksize - EXT2_DIR_REC_LEN(1); 664252890Spfg memset(&root->h_info, 0, sizeof(root->h_info)); 665252890Spfg root->h_info.h_hash_version = fs->e3fs_def_hash_version; 666252890Spfg root->h_info.h_info_len = sizeof(root->h_info); 667252890Spfg ext2_htree_set_block(root->h_entries, 1); 668252890Spfg ext2_htree_set_count(root->h_entries, 1); 669252890Spfg ext2_htree_set_limit(root->h_entries, 670252890Spfg ext2_htree_root_limit(dp, sizeof(root->h_info))); 671252890Spfg 672252890Spfg memset(&info, 0, sizeof(info)); 673252890Spfg info.h_levels_num = 1; 674252890Spfg info.h_levels[0].h_entries = root->h_entries; 675252890Spfg info.h_levels[0].h_entry = root->h_entries; 676252890Spfg 677252890Spfg hash_version = root->h_info.h_hash_version; 678252890Spfg if (hash_version <= EXT2_HTREE_TEA) 679252890Spfg hash_version += m_fs->e2fs_uhash; 680252890Spfg ext2_htree_split_dirblock(buf1, buf2, blksize, fs->e3fs_hash_seed, 681252890Spfg hash_version, &split_hash, new_entry); 682252890Spfg ext2_htree_insert_entry(&info, split_hash, 2); 683252890Spfg 684252890Spfg /* 685252890Spfg * Write directory block 0. 686252890Spfg */ 687252890Spfg if (DOINGASYNC(vp)) { 688252890Spfg bdwrite(bp); 689252890Spfg error = 0; 690252890Spfg } else { 691252890Spfg error = bwrite(bp); 692252890Spfg } 693252890Spfg dp->i_flag |= IN_CHANGE | IN_UPDATE; 694252890Spfg if (error) 695252890Spfg goto out; 696252890Spfg 697252890Spfg /* 698252890Spfg * Write directory block 1. 699252890Spfg */ 700252890Spfg error = ext2_htree_append_block(vp, buf1, cnp, blksize); 701252890Spfg if (error) 702252890Spfg goto out1; 703252890Spfg 704252890Spfg /* 705252890Spfg * Write directory block 2. 706252890Spfg */ 707252890Spfg error = ext2_htree_append_block(vp, buf2, cnp, blksize); 708252890Spfg 709252890Spfg free(buf1, M_TEMP); 710252890Spfg free(buf2, M_TEMP); 711252890Spfg return (error); 712252890Spfgout: 713252890Spfg if (bp != NULL) 714252890Spfg brelse(bp); 715252890Spfgout1: 716252890Spfg free(buf1, M_TEMP); 717252890Spfg free(buf2, M_TEMP); 718252890Spfg return (error); 719252890Spfg} 720252890Spfg 721252890Spfg/* 722252890Spfg * Add an entry to the directory using htree index. 723252890Spfg */ 724252890Spfgint 725252890Spfgext2_htree_add_entry(struct vnode *dvp, struct ext2fs_direct_2 *entry, 726311231Spfg struct componentname *cnp) 727252890Spfg{ 728252890Spfg struct ext2fs_htree_entry *entries, *leaf_node; 729252890Spfg struct ext2fs_htree_lookup_info info; 730252890Spfg struct buf *bp = NULL; 731252890Spfg struct ext2fs *fs; 732252890Spfg struct m_ext2fs *m_fs; 733252890Spfg struct inode *ip; 734252890Spfg uint16_t ent_num; 735252890Spfg uint32_t dirhash, split_hash; 736252890Spfg uint32_t blksize, blknum; 737252890Spfg uint64_t cursize, dirsize; 738252890Spfg uint8_t hash_version; 739252890Spfg char *newdirblock = NULL; 740252890Spfg char *newidxblock = NULL; 741252890Spfg struct ext2fs_htree_node *dst_node; 742252890Spfg struct ext2fs_htree_entry *dst_entries; 743252890Spfg struct ext2fs_htree_entry *root_entires; 744252890Spfg struct buf *dst_bp = NULL; 745252890Spfg int error, write_bp = 0, write_dst_bp = 0, write_info = 0; 746252890Spfg 747252890Spfg ip = VTOI(dvp); 748252890Spfg m_fs = ip->i_e2fs; 749252890Spfg fs = m_fs->e2fs; 750252890Spfg blksize = m_fs->e2fs_bsize; 751252890Spfg 752311231Spfg if (ip->i_count != 0) 753252890Spfg return ext2_add_entry(dvp, entry); 754252890Spfg 755252890Spfg /* Target directory block is full, split it */ 756252890Spfg memset(&info, 0, sizeof(info)); 757252890Spfg error = ext2_htree_find_leaf(ip, entry->e2d_name, entry->e2d_namlen, 758252890Spfg &dirhash, &hash_version, &info); 759252890Spfg if (error) 760252890Spfg return (error); 761252890Spfg 762252890Spfg entries = info.h_levels[info.h_levels_num - 1].h_entries; 763252890Spfg ent_num = ext2_htree_get_count(entries); 764252890Spfg if (ent_num == ext2_htree_get_limit(entries)) { 765252890Spfg /* Split the index node. */ 766252890Spfg root_entires = info.h_levels[0].h_entries; 767252890Spfg newidxblock = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO); 768252890Spfg dst_node = (struct ext2fs_htree_node *)newidxblock; 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); 774277354Spfg dirsize = cursize + 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; 811311231Spfg 812252890Spfg info.h_levels[1].h_bp = dst_bp; 813252890Spfg dst_bp = tmp; 814252890Spfg 815252890Spfg info.h_levels[1].h_entry = 816252890Spfg info.h_levels[1].h_entry - 817252890Spfg (entries + src_ent_num) + 818252890Spfg dst_entries; 819252890Spfg info.h_levels[1].h_entries = dst_entries; 820252890Spfg } 821252890Spfg ext2_htree_insert_entry_to_level(&info.h_levels[0], 822252890Spfg split_hash, blknum); 823252890Spfg 824252890Spfg /* Write new index node to disk */ 825252890Spfg error = bwrite(dst_bp); 826252890Spfg ip->i_flag |= IN_CHANGE | IN_UPDATE; 827252890Spfg if (error) 828252890Spfg goto finish; 829252890Spfg write_dst_bp = 1; 830252890Spfg } else { 831252890Spfg /* Create second level for htree index */ 832252890Spfg struct ext2fs_htree_root *idx_root; 833252890Spfg 834252890Spfg memcpy(dst_entries, entries, 835252890Spfg ent_num * sizeof(struct ext2fs_htree_entry)); 836252890Spfg ext2_htree_set_limit(dst_entries, 837252890Spfg ext2_htree_node_limit(ip)); 838252890Spfg 839252890Spfg idx_root = (struct ext2fs_htree_root *) 840252890Spfg info.h_levels[0].h_bp->b_data; 841252890Spfg idx_root->h_info.h_ind_levels = 1; 842252890Spfg 843252890Spfg ext2_htree_set_count(entries, 1); 844252890Spfg ext2_htree_set_block(entries, blknum); 845252890Spfg 846252890Spfg info.h_levels_num = 2; 847252890Spfg info.h_levels[1].h_entries = dst_entries; 848252890Spfg info.h_levels[1].h_entry = info.h_levels[0].h_entry - 849252890Spfg info.h_levels[0].h_entries + dst_entries; 850252890Spfg info.h_levels[1].h_bp = dst_bp; 851294504Spfg dst_bp = NULL; 852252890Spfg } 853252890Spfg } 854252890Spfg 855252890Spfg leaf_node = info.h_levels[info.h_levels_num - 1].h_entry; 856252890Spfg blknum = ext2_htree_get_block(leaf_node); 857252890Spfg error = ext2_blkatoff(dvp, blknum * blksize, NULL, &bp); 858252890Spfg if (error) 859252890Spfg goto finish; 860252890Spfg 861252890Spfg /* Split target directory block */ 862252890Spfg newdirblock = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO); 863252890Spfg ext2_htree_split_dirblock((char *)bp->b_data, newdirblock, blksize, 864252890Spfg fs->e3fs_hash_seed, hash_version, &split_hash, entry); 865252890Spfg cursize = roundup(ip->i_size, blksize); 866278791Spfg dirsize = cursize + blksize; 867252890Spfg blknum = dirsize / blksize - 1; 868252890Spfg 869252890Spfg /* Add index entry for the new directory block */ 870252890Spfg ext2_htree_insert_entry(&info, split_hash, blknum); 871252890Spfg 872252890Spfg /* Write the new directory block to the end of the directory */ 873252890Spfg error = ext2_htree_append_block(dvp, newdirblock, cnp, blksize); 874252890Spfg if (error) 875252890Spfg goto finish; 876252890Spfg 877252890Spfg /* Write the target directory block */ 878252890Spfg error = bwrite(bp); 879252890Spfg ip->i_flag |= IN_CHANGE | IN_UPDATE; 880252890Spfg if (error) 881252890Spfg goto finish; 882252890Spfg write_bp = 1; 883252890Spfg 884252890Spfg /* Write the index block */ 885252890Spfg error = ext2_htree_writebuf(&info); 886252890Spfg if (!error) 887252890Spfg write_info = 1; 888252890Spfg 889252890Spfgfinish: 890252890Spfg if (dst_bp != NULL && !write_dst_bp) 891252890Spfg brelse(dst_bp); 892252890Spfg if (bp != NULL && !write_bp) 893252890Spfg brelse(bp); 894252890Spfg if (newdirblock != NULL) 895252890Spfg free(newdirblock, M_TEMP); 896252890Spfg if (newidxblock != NULL) 897252890Spfg free(newidxblock, M_TEMP); 898252890Spfg if (!write_info) 899252890Spfg ext2_htree_release(&info); 900252890Spfg return (error); 901252890Spfg} 902