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