sys/fs/ext2fs/ext2_htree.c

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