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