sys/fs/ext2fs/ext2_htree.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
   3  *
   4  * Copyright (c) 2010, 2012 Zheng Liu <lz@freebsd.org>
   5  * Copyright (c) 2012, Vyacheslav Matyushin
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  27  * SUCH DAMAGE.
  28  *
  29  * $FreeBSD$
  30  */
  31
  32 #include <sys/param.h>
  33 #include <sys/endian.h>
  34 #include <sys/systm.h>
  35 #include <sys/namei.h>
  36 #include <sys/bio.h>
  37 #include <sys/buf.h>
  38 #include <sys/endian.h>
  39 #include <sys/mount.h>
  40 #include <sys/vnode.h>
  41 #include <sys/malloc.h>
  42 #include <sys/dirent.h>
  43 #include <sys/sdt.h>
  44 #include <sys/sysctl.h>
  45
  46 #include <ufs/ufs/dir.h>
  47
  48 #include <fs/ext2fs/fs.h>
  49 #include <fs/ext2fs/inode.h>
  50 #include <fs/ext2fs/ext2_mount.h>
  51 #include <fs/ext2fs/ext2fs.h>
  52 #include <fs/ext2fs/fs.h>
  53 #include <fs/ext2fs/ext2_extern.h>
  54 #include <fs/ext2fs/ext2_dinode.h>
  55 #include <fs/ext2fs/ext2_dir.h>
  56 #include <fs/ext2fs/htree.h>
  57
  58 SDT_PROVIDER_DECLARE(ext2fs);
  59 /*
  60  * ext2fs trace probe:
  61  * arg0: verbosity. Higher numbers give more verbose messages
  62  * arg1: Textual message
  63  */
  64 SDT_PROBE_DEFINE2(ext2fs, , trace, htree, "int", "char*");
  65
  66 static void     ext2_append_entry(char *block, uint32_t blksize,
  67                     struct ext2fs_direct_2 *last_entry,
  68                     struct ext2fs_direct_2 *new_entry, int csum_size);
  69 static int      ext2_htree_append_block(struct vnode *vp, char *data,
  70                     struct componentname *cnp, uint32_t blksize);
  71 static int      ext2_htree_check_next(struct inode *ip, uint32_t hash,
  72                     const char *name, struct ext2fs_htree_lookup_info *info);
  73 static int      ext2_htree_cmp_sort_entry(const void *e1, const void *e2);
  74 static int      ext2_htree_find_leaf(struct inode *ip, const char *name,
  75                     int namelen, uint32_t *hash, uint8_t *hash_version,
  76                     struct ext2fs_htree_lookup_info *info);
  77 static uint32_t ext2_htree_get_block(struct ext2fs_htree_entry *ep);
  78 static uint16_t ext2_htree_get_count(struct ext2fs_htree_entry *ep);
  79 static uint32_t ext2_htree_get_hash(struct ext2fs_htree_entry *ep);
  80 static uint16_t ext2_htree_get_limit(struct ext2fs_htree_entry *ep);
  81 static void     ext2_htree_insert_entry_to_level(struct ext2fs_htree_lookup_level *level,
  82                     uint32_t hash, uint32_t blk);
  83 static void     ext2_htree_insert_entry(struct ext2fs_htree_lookup_info *info,
  84                     uint32_t hash, uint32_t blk);
  85 static uint32_t ext2_htree_node_limit(struct inode *ip);
  86 static void     ext2_htree_set_block(struct ext2fs_htree_entry *ep,
  87                     uint32_t blk);
  88 static void     ext2_htree_set_count(struct ext2fs_htree_entry *ep,
  89                     uint16_t cnt);
  90 static void     ext2_htree_set_hash(struct ext2fs_htree_entry *ep,
  91                     uint32_t hash);
  92 static void     ext2_htree_set_limit(struct ext2fs_htree_entry *ep,
  93                     uint16_t limit);
  94 static int      ext2_htree_split_dirblock(struct inode *ip,
  95                     char *block1, char *block2, uint32_t blksize,
  96                     uint32_t *hash_seed, uint8_t hash_version,
  97                     uint32_t *split_hash, struct  ext2fs_direct_2 *entry);
  98 static void     ext2_htree_release(struct ext2fs_htree_lookup_info *info);
  99 static uint32_t ext2_htree_root_limit(struct inode *ip, int len);
 100 static int      ext2_htree_writebuf(struct inode *ip,
 101                     struct ext2fs_htree_lookup_info *info);
 102
 103 int
 104 ext2_htree_has_idx(struct inode *ip)
 105 {
 106         if (EXT2_HAS_COMPAT_FEATURE(ip->i_e2fs, EXT2F_COMPAT_DIRHASHINDEX) &&
 107             ip->i_flag & IN_E3INDEX)
 108                 return (1);
 109         else
 110                 return (0);
 111 }
 112
 113 static int
 114 ext2_htree_check_next(struct inode *ip, uint32_t hash, const char *name,
 115     struct ext2fs_htree_lookup_info *info)
 116 {
 117         struct vnode *vp = ITOV(ip);
 118         struct ext2fs_htree_lookup_level *level;
 119         struct buf *bp;
 120         uint32_t next_hash;
 121         int idx = info->h_levels_num - 1;
 122         int levels = 0;
 123
 124         do {
 125                 level = &info->h_levels[idx];
 126                 level->h_entry++;
 127                 if (level->h_entry < level->h_entries +
 128                     ext2_htree_get_count(level->h_entries))
 129                         break;
 130                 if (idx == 0)
 131                         return (0);
 132                 idx--;
 133                 levels++;
 134         } while (1);
 135
 136         next_hash = ext2_htree_get_hash(level->h_entry);
 137         if ((hash & 1) == 0) {
 138                 if (hash != (next_hash & ~1))
 139                         return (0);
 140         }
 141
 142         while (levels > 0) {
 143                 levels--;
 144                 if (ext2_blkatoff(vp, ext2_htree_get_block(level->h_entry) *
 145                     ip->i_e2fs->e2fs_bsize, NULL, &bp) != 0)
 146                         return (0);
 147                 level = &info->h_levels[idx + 1];
 148                 brelse(level->h_bp);
 149                 level->h_bp = bp;
 150                 level->h_entry = level->h_entries =
 151                     ((struct ext2fs_htree_node *)bp->b_data)->h_entries;
 152         }
 153
 154         return (1);
 155 }
 156
 157 static uint32_t
 158 ext2_htree_get_block(struct ext2fs_htree_entry *ep)
 159 {
 160         return (le32toh(ep->h_blk) & 0x00FFFFFF);
 161 }
 162
 163 static void
 164 ext2_htree_set_block(struct ext2fs_htree_entry *ep, uint32_t blk)
 165 {
 166         ep->h_blk = htole32(blk);
 167 }
 168
 169 static uint16_t
 170 ext2_htree_get_count(struct ext2fs_htree_entry *ep)
 171 {
 172         return (le16toh(((struct ext2fs_htree_count *)(ep))->h_entries_num));
 173 }
 174
 175 static void
 176 ext2_htree_set_count(struct ext2fs_htree_entry *ep, uint16_t cnt)
 177 {
 178         ((struct ext2fs_htree_count *)(ep))->h_entries_num = htole16(cnt);
 179 }
 180
 181 static uint32_t
 182 ext2_htree_get_hash(struct ext2fs_htree_entry *ep)
 183 {
 184         return (le32toh(ep->h_hash));
 185 }
 186
 187 static uint16_t
 188 ext2_htree_get_limit(struct ext2fs_htree_entry *ep)
 189 {
 190         return (le16toh(((struct ext2fs_htree_count *)(ep))->h_entries_max));
 191 }
 192
 193 static void
 194 ext2_htree_set_hash(struct ext2fs_htree_entry *ep, uint32_t hash)
 195 {
 196         ep->h_hash = htole32(hash);
 197 }
 198
 199 static void
 200 ext2_htree_set_limit(struct ext2fs_htree_entry *ep, uint16_t limit)
 201 {
 202         ((struct ext2fs_htree_count *)(ep))->h_entries_max = htole16(limit);
 203 }
 204
 205 static void
 206 ext2_htree_release(struct ext2fs_htree_lookup_info *info)
 207 {
 208         u_int i;
 209
 210         for (i = 0; i < info->h_levels_num; i++) {
 211                 struct buf *bp = info->h_levels[i].h_bp;
 212
 213                 if (bp != NULL)
 214                         brelse(bp);
 215         }
 216 }
 217
 218 static uint32_t
 219 ext2_htree_root_limit(struct inode *ip, int len)
 220 {
 221         struct m_ext2fs *fs;
 222         uint32_t space;
 223
 224         fs = ip->i_e2fs;
 225         space = ip->i_e2fs->e2fs_bsize - EXT2_DIR_REC_LEN(1) -
 226             EXT2_DIR_REC_LEN(2) - len;
 227
 228         if (EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_METADATA_CKSUM))
 229                 space -= sizeof(struct ext2fs_htree_tail);
 230
 231         return (space / sizeof(struct ext2fs_htree_entry));
 232 }
 233
 234 static uint32_t
 235 ext2_htree_node_limit(struct inode *ip)
 236 {
 237         struct m_ext2fs *fs;
 238         uint32_t space;
 239
 240         fs = ip->i_e2fs;
 241         space = fs->e2fs_bsize - EXT2_DIR_REC_LEN(0);
 242
 243         if (EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_METADATA_CKSUM))
 244                 space -= sizeof(struct ext2fs_htree_tail);
 245
 246         return (space / sizeof(struct ext2fs_htree_entry));
 247 }
 248
 249 static void
 250 ext2_get_hash_seed(struct ext2fs* es, uint32_t* seed)
 251 {
 252
 253         for (int i = 0; i < 4; i++)
 254                 seed[i] = le32toh(es->e3fs_hash_seed[i]);
 255 }
 256
 257 static int
 258 ext2_htree_find_leaf(struct inode *ip, const char *name, int namelen,
 259     uint32_t *hash, uint8_t *hash_ver,
 260     struct ext2fs_htree_lookup_info *info)
 261 {
 262         struct vnode *vp;
 263         struct ext2fs *fs;
 264         struct m_ext2fs *m_fs;
 265         struct buf *bp = NULL;
 266         struct ext2fs_htree_root *rootp;
 267         struct ext2fs_htree_entry *entp, *start, *end, *middle, *found;
 268         struct ext2fs_htree_lookup_level *level_info;
 269         uint32_t hash_major = 0, hash_minor = 0;
 270         uint32_t levels, cnt;
 271         uint32_t hash_seed[4];
 272         uint8_t hash_version;
 273
 274         if (name == NULL || info == NULL)
 275                 return (-1);
 276
 277         vp = ITOV(ip);
 278         fs = ip->i_e2fs->e2fs;
 279         m_fs = ip->i_e2fs;
 280
 281         if (ext2_blkatoff(vp, 0, NULL, &bp) != 0)
 282                 return (-1);
 283
 284         info->h_levels_num = 1;
 285         info->h_levels[0].h_bp = bp;
 286         rootp = (struct ext2fs_htree_root *)bp->b_data;
 287         if (rootp->h_info.h_hash_version != EXT2_HTREE_LEGACY &&
 288             rootp->h_info.h_hash_version != EXT2_HTREE_HALF_MD4 &&
 289             rootp->h_info.h_hash_version != EXT2_HTREE_TEA)
 290                 goto error;
 291
 292         hash_version = rootp->h_info.h_hash_version;
 293         if (hash_version <= EXT2_HTREE_TEA)
 294                 hash_version += m_fs->e2fs_uhash;
 295         *hash_ver = hash_version;
 296
 297         ext2_get_hash_seed(fs, hash_seed);
 298         ext2_htree_hash(name, namelen, hash_seed,
 299             hash_version, &hash_major, &hash_minor);
 300         *hash = hash_major;
 301
 302         if ((levels = rootp->h_info.h_ind_levels) > 1)
 303                 goto error;
 304
 305         entp = (struct ext2fs_htree_entry *)(((char *)&rootp->h_info) +
 306             rootp->h_info.h_info_len);
 307
 308         if (ext2_htree_get_limit(entp) !=
 309             ext2_htree_root_limit(ip, rootp->h_info.h_info_len))
 310                 goto error;
 311
 312         while (1) {
 313                 cnt = ext2_htree_get_count(entp);
 314                 if (cnt == 0 || cnt > ext2_htree_get_limit(entp))
 315                         goto error;
 316
 317                 start = entp + 1;
 318                 end = entp + cnt - 1;
 319                 while (start <= end) {
 320                         middle = start + (end - start) / 2;
 321                         if (ext2_htree_get_hash(middle) > hash_major)
 322                                 end = middle - 1;
 323                         else
 324                                 start = middle + 1;
 325                 }
 326                 found = start - 1;
 327
 328                 level_info = &(info->h_levels[info->h_levels_num - 1]);
 329                 level_info->h_bp = bp;
 330                 level_info->h_entries = entp;
 331                 level_info->h_entry = found;
 332                 if (levels == 0)
 333                         return (0);
 334                 levels--;
 335                 if (ext2_blkatoff(vp,
 336                     ext2_htree_get_block(found) * m_fs->e2fs_bsize,
 337                     NULL, &bp) != 0)
 338                         goto error;
 339                 entp = ((struct ext2fs_htree_node *)bp->b_data)->h_entries;
 340                 info->h_levels_num++;
 341                 info->h_levels[info->h_levels_num - 1].h_bp = bp;
 342         }
 343
 344 error:
 345         ext2_htree_release(info);
 346         return (-1);
 347 }
 348
 349 /*
 350  * Try to lookup a directory entry in HTree index
 351  */
 352 int
 353 ext2_htree_lookup(struct inode *ip, const char *name, int namelen,
 354     struct buf **bpp, int *entryoffp, doff_t *offp,
 355     doff_t *prevoffp, doff_t *endusefulp,
 356     struct ext2fs_searchslot *ss)
 357 {
 358         struct vnode *vp;
 359         struct ext2fs_htree_lookup_info info;
 360         struct ext2fs_htree_entry *leaf_node;
 361         struct m_ext2fs *m_fs;
 362         struct buf *bp;
 363         uint32_t blk;
 364         uint32_t dirhash;
 365         uint32_t bsize;
 366         uint8_t hash_version;
 367         int search_next;
 368         int found = 0;
 369
 370         m_fs = ip->i_e2fs;
 371         bsize = m_fs->e2fs_bsize;
 372         vp = ITOV(ip);
 373
 374         /* TODO: print error msg because we don't lookup '.' and '..' */
 375
 376         memset(&info, 0, sizeof(info));
 377         if (ext2_htree_find_leaf(ip, name, namelen, &dirhash,
 378             &hash_version, &info))
 379                 return (-1);
 380
 381         do {
 382                 leaf_node = info.h_levels[info.h_levels_num - 1].h_entry;
 383                 blk = ext2_htree_get_block(leaf_node);
 384                 if (ext2_blkatoff(vp, blk * bsize, NULL, &bp) != 0) {
 385                         ext2_htree_release(&info);
 386                         return (-1);
 387                 }
 388
 389                 *offp = blk * bsize;
 390                 *entryoffp = 0;
 391                 *prevoffp = blk * bsize;
 392                 *endusefulp = blk * bsize;
 393
 394                 if (ss->slotstatus == NONE) {
 395                         ss->slotoffset = -1;
 396                         ss->slotfreespace = 0;
 397                 }
 398
 399                 if (ext2_search_dirblock(ip, bp->b_data, &found,
 400                     name, namelen, entryoffp, offp, prevoffp,
 401                     endusefulp, ss) != 0) {
 402                         brelse(bp);
 403                         ext2_htree_release(&info);
 404                         return (-1);
 405                 }
 406
 407                 if (found) {
 408                         *bpp = bp;
 409                         ext2_htree_release(&info);
 410                         return (0);
 411                 }
 412
 413                 brelse(bp);
 414                 search_next = ext2_htree_check_next(ip, dirhash, name, &info);
 415         } while (search_next);
 416
 417         ext2_htree_release(&info);
 418         return (ENOENT);
 419 }
 420
 421 static int
 422 ext2_htree_append_block(struct vnode *vp, char *data,
 423     struct componentname *cnp, uint32_t blksize)
 424 {
 425         struct iovec aiov;
 426         struct uio auio;
 427         struct inode *dp = VTOI(vp);
 428         uint64_t cursize, newsize;
 429         int error;
 430
 431         cursize = roundup(dp->i_size, blksize);
 432         newsize = cursize + blksize;
 433
 434         auio.uio_offset = cursize;
 435         auio.uio_resid = blksize;
 436         aiov.iov_len = blksize;
 437         aiov.iov_base = data;
 438         auio.uio_iov = &aiov;
 439         auio.uio_iovcnt = 1;
 440         auio.uio_rw = UIO_WRITE;
 441         auio.uio_segflg = UIO_SYSSPACE;
 442         error = VOP_WRITE(vp, &auio, IO_SYNC, cnp->cn_cred);
 443         if (!error)
 444                 dp->i_size = newsize;
 445
 446         return (error);
 447 }
 448
 449 static int
 450 ext2_htree_writebuf(struct inode* ip, struct ext2fs_htree_lookup_info *info)
 451 {
 452         int i, error;
 453
 454         for (i = 0; i < info->h_levels_num; i++) {
 455                 struct buf *bp = info->h_levels[i].h_bp;
 456                 ext2_dx_csum_set(ip, (struct ext2fs_direct_2 *)bp->b_data);
 457                 error = bwrite(bp);
 458                 if (error)
 459                         return (error);
 460         }
 461
 462         return (0);
 463 }
 464
 465 static void
 466 ext2_htree_insert_entry_to_level(struct ext2fs_htree_lookup_level *level,
 467     uint32_t hash, uint32_t blk)
 468 {
 469         struct ext2fs_htree_entry *target;
 470         int entries_num;
 471
 472         target = level->h_entry + 1;
 473         entries_num = ext2_htree_get_count(level->h_entries);
 474
 475         memmove(target + 1, target, (char *)(level->h_entries + entries_num) -
 476             (char *)target);
 477         ext2_htree_set_block(target, blk);
 478         ext2_htree_set_hash(target, hash);
 479         ext2_htree_set_count(level->h_entries, entries_num + 1);
 480 }
 481
 482 /*
 483  * Insert an index entry to the index node.
 484  */
 485 static void
 486 ext2_htree_insert_entry(struct ext2fs_htree_lookup_info *info,
 487     uint32_t hash, uint32_t blk)
 488 {
 489         struct ext2fs_htree_lookup_level *level;
 490
 491         level = &info->h_levels[info->h_levels_num - 1];
 492         ext2_htree_insert_entry_to_level(level, hash, blk);
 493 }
 494
 495 /*
 496  * Compare two entry sort descriptors by name hash value.
 497  * This is used together with qsort.
 498  */
 499 static int
 500 ext2_htree_cmp_sort_entry(const void *e1, const void *e2)
 501 {
 502         const struct ext2fs_htree_sort_entry *entry1, *entry2;
 503
 504         entry1 = (const struct ext2fs_htree_sort_entry *)e1;
 505         entry2 = (const struct ext2fs_htree_sort_entry *)e2;
 506
 507         if (le32toh(entry1->h_hash) < le32toh(entry2->h_hash))
 508                 return (-1);
 509         if (le32toh(entry1->h_hash) > le32toh(entry2->h_hash))
 510                 return (1);
 511         return (0);
 512 }
 513
 514 /*
 515  * Append an entry to the end of the directory block.
 516  */
 517 static void
 518 ext2_append_entry(char *block, uint32_t blksize,
 519     struct ext2fs_direct_2 *last_entry,
 520     struct ext2fs_direct_2 *new_entry, int csum_size)
 521 {
 522         uint16_t entry_len;
 523
 524         entry_len = EXT2_DIR_REC_LEN(last_entry->e2d_namlen);
 525         last_entry->e2d_reclen = htole16(entry_len);
 526         last_entry = (struct ext2fs_direct_2 *)((char *)last_entry + entry_len);
 527         new_entry->e2d_reclen = htole16(block + blksize - (char *)last_entry -
 528             csum_size);
 529         memcpy(last_entry, new_entry, EXT2_DIR_REC_LEN(new_entry->e2d_namlen));
 530 }
 531
 532 /*
 533  * Move half of entries from the old directory block to the new one.
 534  */
 535 static int
 536 ext2_htree_split_dirblock(struct inode *ip, char *block1, char *block2,
 537     uint32_t blksize, uint32_t *hash_seed, uint8_t hash_version,
 538     uint32_t *split_hash, struct ext2fs_direct_2 *entry)
 539 {
 540         struct m_ext2fs *fs;
 541         int entry_cnt = 0;
 542         int size = 0, csum_size = 0;
 543         int i, k;
 544         uint32_t offset;
 545         uint16_t entry_len = 0;
 546         uint32_t entry_hash;
 547         struct ext2fs_direct_2 *ep, *last;
 548         char *dest;
 549         struct ext2fs_htree_sort_entry *sort_info;
 550
 551         fs = ip->i_e2fs;
 552         ep = (struct ext2fs_direct_2 *)block1;
 553         dest = block2;
 554         sort_info = (struct ext2fs_htree_sort_entry *)
 555             ((char *)block2 + blksize);
 556
 557         if (EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_METADATA_CKSUM))
 558                 csum_size = sizeof(struct ext2fs_direct_tail);
 559
 560         /*
 561          * Calculate name hash value for the entry which is to be added.
 562          */
 563         ext2_htree_hash(entry->e2d_name, entry->e2d_namlen, hash_seed,
 564             hash_version, &entry_hash, NULL);
 565
 566         /*
 567          * Fill in directory entry sort descriptors.
 568          */
 569         while ((char *)ep < block1 + blksize - csum_size) {
 570                 if (le32toh(ep->e2d_ino) && ep->e2d_namlen) {
 571                         entry_cnt++;
 572                         sort_info--;
 573                         sort_info->h_size = ep->e2d_reclen;
 574                         sort_info->h_offset = htole16((char *)ep - block1);
 575                         ext2_htree_hash(ep->e2d_name, ep->e2d_namlen,
 576                             hash_seed, hash_version,
 577                             &sort_info->h_hash, NULL);
 578                         sort_info->h_hash = htole32(sort_info->h_hash);
 579                 }
 580                 ep = (struct ext2fs_direct_2 *)
 581                     ((char *)ep + le16toh(ep->e2d_reclen));
 582         }
 583
 584         /*
 585          * Sort directory entry descriptors by name hash value.
 586          */
 587         qsort(sort_info, entry_cnt, sizeof(struct ext2fs_htree_sort_entry),
 588             ext2_htree_cmp_sort_entry);
 589
 590         /*
 591          * Count the number of entries to move to directory block 2.
 592          */
 593         for (i = entry_cnt - 1; i >= 0; i--) {
 594                 if (le16toh(sort_info[i].h_size) + size > blksize / 2)
 595                         break;
 596                 size += le16toh(sort_info[i].h_size);
 597         }
 598
 599         *split_hash = le32toh(sort_info[i + 1].h_hash);
 600
 601         /*
 602          * Set collision bit.
 603          */
 604         if (*split_hash == le32toh(sort_info[i].h_hash))
 605                 *split_hash += 1;
 606
 607         /*
 608          * Move half of directory entries from block 1 to block 2.
 609          */
 610         for (k = i + 1; k < entry_cnt; k++) {
 611                 ep = (struct ext2fs_direct_2 *)((char *)block1 +
 612                     le16toh(sort_info[k].h_offset));
 613                 entry_len = EXT2_DIR_REC_LEN(ep->e2d_namlen);
 614                 memcpy(dest, ep, entry_len);
 615                 ((struct ext2fs_direct_2 *)dest)->e2d_reclen =
 616                     htole16(entry_len);
 617                 /* Mark directory entry as unused. */
 618                 ep->e2d_ino = 0;
 619                 dest += entry_len;
 620         }
 621         dest -= entry_len;
 622
 623         /* Shrink directory entries in block 1. */
 624         last = (struct ext2fs_direct_2 *)block1;
 625         entry_len = 0;
 626         for (offset = 0; offset < blksize - csum_size; ) {
 627                 ep = (struct ext2fs_direct_2 *)(block1 + offset);
 628                 offset += le16toh(ep->e2d_reclen);
 629                 if (le32toh(ep->e2d_ino)) {
 630                         last = (struct ext2fs_direct_2 *)
 631                             ((char *)last + entry_len);
 632                         entry_len = EXT2_DIR_REC_LEN(ep->e2d_namlen);
 633                         memcpy((void *)last, (void *)ep, entry_len);
 634                         last->e2d_reclen = htole16(entry_len);
 635                 }
 636         }
 637
 638         if (entry_hash >= *split_hash) {
 639                 /* Add entry to block 2. */
 640                 ext2_append_entry(block2, blksize,
 641                     (struct ext2fs_direct_2 *)dest, entry, csum_size);
 642
 643                 /* Adjust length field of last entry of block 1. */
 644                 last->e2d_reclen = htole16(block1 + blksize - (char *)last -
 645                     csum_size);
 646         } else {
 647                 /* Add entry to block 1. */
 648                 ext2_append_entry(block1, blksize, last, entry, csum_size);
 649
 650                 /* Adjust length field of last entry of block 2. */
 651                 ((struct ext2fs_direct_2 *)dest)->e2d_reclen =
 652                     htole16(block2 + blksize - dest - csum_size);
 653         }
 654
 655         if (csum_size) {
 656                 ext2_init_dirent_tail(EXT2_DIRENT_TAIL(block1, blksize));
 657                 ext2_init_dirent_tail(EXT2_DIRENT_TAIL(block2, blksize));
 658         }
 659
 660         return (0);
 661 }
 662
 663 /*
 664  * Create an HTree index for a directory
 665  */
 666 int
 667 ext2_htree_create_index(struct vnode *vp, struct componentname *cnp,
 668     struct ext2fs_direct_2 *new_entry)
 669 {
 670         struct buf *bp = NULL;
 671         struct inode *dp;
 672         struct ext2fs *fs;
 673         struct m_ext2fs *m_fs;
 674         struct ext2fs_direct_2 *ep, *dotdot;
 675         struct ext2fs_htree_root *root;
 676         struct ext2fs_htree_lookup_info info;
 677         uint32_t blksize, dirlen, split_hash;
 678         uint32_t hash_seed[4];
 679         uint8_t hash_version;
 680         char *buf1 = NULL;
 681         char *buf2 = NULL;
 682         int error = 0;
 683
 684         dp = VTOI(vp);
 685         fs = dp->i_e2fs->e2fs;
 686         m_fs = dp->i_e2fs;
 687         blksize = m_fs->e2fs_bsize;
 688
 689         buf1 = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO);
 690         buf2 = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO);
 691
 692         if ((error = ext2_blkatoff(vp, 0, NULL, &bp)) != 0)
 693                 goto out;
 694
 695         root = (struct ext2fs_htree_root *)bp->b_data;
 696         dotdot = (struct ext2fs_direct_2 *)((char *)&(root->h_dotdot));
 697         ep = (struct ext2fs_direct_2 *)((char *)dotdot +
 698             le16toh(dotdot->e2d_reclen));
 699         dirlen = (char *)root + blksize - (char *)ep;
 700         memcpy(buf1, ep, dirlen);
 701         ep = (struct ext2fs_direct_2 *)buf1;
 702         while ((char *)ep < buf1 + dirlen)
 703                 ep = (struct ext2fs_direct_2 *)
 704                     ((char *)ep + le16toh(ep->e2d_reclen));
 705         ep->e2d_reclen = htole16(buf1 + blksize - (char *)ep);
 706
 707         dp->i_flag |= IN_E3INDEX;
 708
 709         /*
 710          * Initialize index root.
 711          */
 712         dotdot->e2d_reclen = htole16(blksize - EXT2_DIR_REC_LEN(1));
 713         memset(&root->h_info, 0, sizeof(root->h_info));
 714         root->h_info.h_hash_version = fs->e3fs_def_hash_version;
 715         root->h_info.h_info_len = sizeof(root->h_info);
 716         ext2_htree_set_block(root->h_entries, 1);
 717         ext2_htree_set_count(root->h_entries, 1);
 718         ext2_htree_set_limit(root->h_entries,
 719             ext2_htree_root_limit(dp, sizeof(root->h_info)));
 720
 721         memset(&info, 0, sizeof(info));
 722         info.h_levels_num = 1;
 723         info.h_levels[0].h_entries = root->h_entries;
 724         info.h_levels[0].h_entry = root->h_entries;
 725
 726         hash_version = root->h_info.h_hash_version;
 727         if (hash_version <= EXT2_HTREE_TEA)
 728                 hash_version += m_fs->e2fs_uhash;
 729         ext2_get_hash_seed(fs, hash_seed);
 730         ext2_htree_split_dirblock(dp, buf1, buf2, blksize, hash_seed,
 731             hash_version, &split_hash, new_entry);
 732         ext2_htree_insert_entry(&info, split_hash, 2);
 733
 734         /*
 735          * Write directory block 0.
 736          */
 737         ext2_dx_csum_set(dp, (struct ext2fs_direct_2 *)bp->b_data);
 738         if (DOINGASYNC(vp)) {
 739                 bdwrite(bp);
 740                 error = 0;
 741         } else {
 742                 error = bwrite(bp);
 743         }
 744         dp->i_flag |= IN_CHANGE | IN_UPDATE;
 745         if (error)
 746                 goto out;
 747
 748         /*
 749          * Write directory block 1.
 750          */
 751         ext2_dirent_csum_set(dp, (struct ext2fs_direct_2 *)buf1);
 752         error = ext2_htree_append_block(vp, buf1, cnp, blksize);
 753         if (error)
 754                 goto out1;
 755
 756         /*
 757          * Write directory block 2.
 758          */
 759         ext2_dirent_csum_set(dp, (struct ext2fs_direct_2 *)buf2);
 760         error = ext2_htree_append_block(vp, buf2, cnp, blksize);
 761
 762         free(buf1, M_TEMP);
 763         free(buf2, M_TEMP);
 764         return (error);
 765 out:
 766         if (bp != NULL)
 767                 brelse(bp);
 768 out1:
 769         free(buf1, M_TEMP);
 770         free(buf2, M_TEMP);
 771         return (error);
 772 }
 773
 774 /*
 775  * Add an entry to the directory using htree index.
 776  */
 777 int
 778 ext2_htree_add_entry(struct vnode *dvp, struct ext2fs_direct_2 *entry,
 779     struct componentname *cnp)
 780 {
 781         struct ext2fs_htree_entry *entries, *leaf_node;
 782         struct ext2fs_htree_lookup_info info;
 783         struct buf *bp = NULL;
 784         struct ext2fs *fs;
 785         struct m_ext2fs *m_fs;
 786         struct inode *ip;
 787         uint16_t ent_num;
 788         uint32_t dirhash, split_hash;
 789         uint32_t blksize, blknum;
 790         uint64_t cursize, dirsize;
 791         uint32_t hash_seed[4];
 792         uint8_t hash_version;
 793         char *newdirblock = NULL;
 794         char *newidxblock = NULL;
 795         struct ext2fs_htree_node *dst_node;
 796         struct ext2fs_htree_entry *dst_entries;
 797         struct ext2fs_htree_entry *root_entires;
 798         struct buf *dst_bp = NULL;
 799         int error, write_bp = 0, write_dst_bp = 0, write_info = 0;
 800
 801         ip = VTOI(dvp);
 802         m_fs = ip->i_e2fs;
 803         fs = m_fs->e2fs;
 804         blksize = m_fs->e2fs_bsize;
 805
 806         if (ip->i_count != 0)
 807                 return ext2_add_entry(dvp, entry);
 808
 809         /* Target directory block is full, split it */
 810         memset(&info, 0, sizeof(info));
 811         error = ext2_htree_find_leaf(ip, entry->e2d_name, entry->e2d_namlen,
 812             &dirhash, &hash_version, &info);
 813         if (error)
 814                 return (error);
 815
 816         entries = info.h_levels[info.h_levels_num - 1].h_entries;
 817         ent_num = ext2_htree_get_count(entries);
 818         if (ent_num == ext2_htree_get_limit(entries)) {
 819                 /* Split the index node. */
 820                 root_entires = info.h_levels[0].h_entries;
 821                 newidxblock = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO);
 822                 dst_node = (struct ext2fs_htree_node *)newidxblock;
 823                 memset(&dst_node->h_fake_dirent, 0,
 824                     sizeof(dst_node->h_fake_dirent));
 825                 dst_node->h_fake_dirent.e2d_reclen = htole16(blksize);
 826
 827                 cursize = roundup(ip->i_size, blksize);
 828                 dirsize = cursize + blksize;
 829                 blknum = dirsize / blksize - 1;
 830                 ext2_dx_csum_set(ip, (struct ext2fs_direct_2 *)newidxblock);
 831                 error = ext2_htree_append_block(dvp, newidxblock,
 832                     cnp, blksize);
 833                 if (error)
 834                         goto finish;
 835                 error = ext2_blkatoff(dvp, cursize, NULL, &dst_bp);
 836                 if (error)
 837                         goto finish;
 838                 dst_node = (struct ext2fs_htree_node *)dst_bp->b_data;
 839                 dst_entries = dst_node->h_entries;
 840
 841                 if (info.h_levels_num == 2) {
 842                         uint16_t src_ent_num, dst_ent_num;
 843
 844                         if (ext2_htree_get_count(root_entires) ==
 845                             ext2_htree_get_limit(root_entires)) {
 846                                 SDT_PROBE2(ext2fs, , trace, htree, 1,
 847                                     "directory index is full");
 848                                 error = EIO;
 849                                 goto finish;
 850                         }
 851
 852                         src_ent_num = ent_num / 2;
 853                         dst_ent_num = ent_num - src_ent_num;
 854                         split_hash = ext2_htree_get_hash(entries + src_ent_num);
 855
 856                         /* Move half of index entries to the new index node */
 857                         memcpy(dst_entries, entries + src_ent_num,
 858                             dst_ent_num * sizeof(struct ext2fs_htree_entry));
 859                         ext2_htree_set_count(entries, src_ent_num);
 860                         ext2_htree_set_count(dst_entries, dst_ent_num);
 861                         ext2_htree_set_limit(dst_entries,
 862                             ext2_htree_node_limit(ip));
 863
 864                         if (info.h_levels[1].h_entry >= entries + src_ent_num) {
 865                                 struct buf *tmp = info.h_levels[1].h_bp;
 866
 867                                 info.h_levels[1].h_bp = dst_bp;
 868                                 dst_bp = tmp;
 869
 870                                 info.h_levels[1].h_entry =
 871                                     info.h_levels[1].h_entry -
 872                                     (entries + src_ent_num) +
 873                                     dst_entries;
 874                                 info.h_levels[1].h_entries = dst_entries;
 875                         }
 876                         ext2_htree_insert_entry_to_level(&info.h_levels[0],
 877                             split_hash, blknum);
 878
 879                         /* Write new index node to disk */
 880                         ext2_dx_csum_set(ip,
 881                             (struct ext2fs_direct_2 *)dst_bp->b_data);
 882                         error = bwrite(dst_bp);
 883                         ip->i_flag |= IN_CHANGE | IN_UPDATE;
 884                         if (error)
 885                                 goto finish;
 886                         write_dst_bp = 1;
 887                 } else {
 888                         /* Create second level for htree index */
 889                         struct ext2fs_htree_root *idx_root;
 890
 891                         memcpy(dst_entries, entries,
 892                             ent_num * sizeof(struct ext2fs_htree_entry));
 893                         ext2_htree_set_limit(dst_entries,
 894                             ext2_htree_node_limit(ip));
 895
 896                         idx_root = (struct ext2fs_htree_root *)
 897                             info.h_levels[0].h_bp->b_data;
 898                         idx_root->h_info.h_ind_levels = 1;
 899
 900                         ext2_htree_set_count(entries, 1);
 901                         ext2_htree_set_block(entries, blknum);
 902
 903                         info.h_levels_num = 2;
 904                         info.h_levels[1].h_entries = dst_entries;
 905                         info.h_levels[1].h_entry = info.h_levels[0].h_entry -
 906                             info.h_levels[0].h_entries + dst_entries;
 907                         info.h_levels[1].h_bp = dst_bp;
 908                         dst_bp = NULL;
 909                 }
 910         }
 911
 912         leaf_node = info.h_levels[info.h_levels_num - 1].h_entry;
 913         blknum = ext2_htree_get_block(leaf_node);
 914         error = ext2_blkatoff(dvp, blknum * blksize, NULL, &bp);
 915         if (error)
 916                 goto finish;
 917
 918         /* Split target directory block */
 919         newdirblock = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO);
 920         ext2_get_hash_seed(fs, hash_seed);
 921         ext2_htree_split_dirblock(ip, (char *)bp->b_data, newdirblock, blksize,
 922             hash_seed, hash_version, &split_hash, entry);
 923         cursize = roundup(ip->i_size, blksize);
 924         dirsize = cursize + blksize;
 925         blknum = dirsize / blksize - 1;
 926
 927         /* Add index entry for the new directory block */
 928         ext2_htree_insert_entry(&info, split_hash, blknum);
 929
 930         /* Write the new directory block to the end of the directory */
 931         ext2_dirent_csum_set(ip, (struct ext2fs_direct_2 *)newdirblock);
 932         error = ext2_htree_append_block(dvp, newdirblock, cnp, blksize);
 933         if (error)
 934                 goto finish;
 935
 936         /* Write the target directory block */
 937         ext2_dirent_csum_set(ip, (struct ext2fs_direct_2 *)bp->b_data);
 938         error = bwrite(bp);
 939         ip->i_flag |= IN_CHANGE | IN_UPDATE;
 940         if (error)
 941                 goto finish;
 942         write_bp = 1;
 943
 944         /* Write the index block */
 945         error = ext2_htree_writebuf(ip, &info);
 946         if (!error)
 947                 write_info = 1;
 948
 949 finish:
 950         if (dst_bp != NULL && !write_dst_bp)
 951                 brelse(dst_bp);
 952         if (bp != NULL && !write_bp)
 953                 brelse(bp);
 954         if (newdirblock != NULL)
 955                 free(newdirblock, M_TEMP);
 956         if (newidxblock != NULL)
 957                 free(newidxblock, M_TEMP);
 958         if (!write_info)
 959                 ext2_htree_release(&info);
 960         return (error);
 961 }