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_E3INDEX)
  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         u_int i;
 195
 196         for (i = 0; i < info->h_levels_num; i++) {
 197                 struct buf *bp = info->h_levels[i].h_bp;
 198
 199                 if (bp != NULL)
 200                         brelse(bp);
 201         }
 202 }
 203
 204 static uint32_t
 205 ext2_htree_root_limit(struct inode *ip, int len)
 206 {
 207         uint32_t space;
 208
 209         space = ip->i_e2fs->e2fs_bsize - EXT2_DIR_REC_LEN(1) -
 210             EXT2_DIR_REC_LEN(2) - len;
 211         return (space / sizeof(struct ext2fs_htree_entry));
 212 }
 213
 214 static uint32_t
 215 ext2_htree_node_limit(struct inode *ip)
 216 {
 217         struct m_ext2fs *fs;
 218         uint32_t space;
 219
 220         fs = ip->i_e2fs;
 221         space = fs->e2fs_bsize - EXT2_DIR_REC_LEN(0);
 222
 223         return (space / sizeof(struct ext2fs_htree_entry));
 224 }
 225
 226 static int
 227 ext2_htree_find_leaf(struct inode *ip, const char *name, int namelen,
 228     uint32_t *hash, uint8_t *hash_ver,
 229     struct ext2fs_htree_lookup_info *info)
 230 {
 231         struct vnode *vp;
 232         struct ext2fs *fs;
 233         struct m_ext2fs *m_fs;
 234         struct buf *bp = NULL;
 235         struct ext2fs_htree_root *rootp;
 236         struct ext2fs_htree_entry *entp, *start, *end, *middle, *found;
 237         struct ext2fs_htree_lookup_level *level_info;
 238         uint32_t hash_major = 0, hash_minor = 0;
 239         uint32_t levels, cnt;
 240         uint8_t hash_version;
 241
 242         if (name == NULL || info == NULL)
 243                 return (-1);
 244
 245         vp = ITOV(ip);
 246         fs = ip->i_e2fs->e2fs;
 247         m_fs = ip->i_e2fs;
 248
 249         if (ext2_blkatoff(vp, 0, NULL, &bp) != 0)
 250                 return (-1);
 251
 252         info->h_levels_num = 1;
 253         info->h_levels[0].h_bp = bp;
 254         rootp = (struct ext2fs_htree_root *)bp->b_data;
 255         if (rootp->h_info.h_hash_version != EXT2_HTREE_LEGACY &&
 256             rootp->h_info.h_hash_version != EXT2_HTREE_HALF_MD4 &&
 257             rootp->h_info.h_hash_version != EXT2_HTREE_TEA)
 258                 goto error;
 259
 260         hash_version = rootp->h_info.h_hash_version;
 261         if (hash_version <= EXT2_HTREE_TEA)
 262                 hash_version += m_fs->e2fs_uhash;
 263         *hash_ver = hash_version;
 264
 265         ext2_htree_hash(name, namelen, fs->e3fs_hash_seed,
 266             hash_version, &hash_major, &hash_minor);
 267         *hash = hash_major;
 268
 269         if ((levels = rootp->h_info.h_ind_levels) > 1)
 270                 goto error;
 271
 272         entp = (struct ext2fs_htree_entry *)(((char *)&rootp->h_info) +
 273             rootp->h_info.h_info_len);
 274
 275         if (ext2_htree_get_limit(entp) !=
 276             ext2_htree_root_limit(ip, rootp->h_info.h_info_len))
 277                 goto error;
 278
 279         while (1) {
 280                 cnt = ext2_htree_get_count(entp);
 281                 if (cnt == 0 || cnt > ext2_htree_get_limit(entp))
 282                         goto error;
 283
 284                 start = entp + 1;
 285                 end = entp + cnt - 1;
 286                 while (start <= end) {
 287                         middle = start + (end - start) / 2;
 288                         if (ext2_htree_get_hash(middle) > hash_major)
 289                                 end = middle - 1;
 290                         else
 291                                 start = middle + 1;
 292                 }
 293                 found = start - 1;
 294
 295                 level_info = &(info->h_levels[info->h_levels_num - 1]);
 296                 level_info->h_bp = bp;
 297                 level_info->h_entries = entp;
 298                 level_info->h_entry = found;
 299                 if (levels == 0)
 300                         return (0);
 301                 levels--;
 302                 if (ext2_blkatoff(vp,
 303                     ext2_htree_get_block(found) * m_fs->e2fs_bsize,
 304                     NULL, &bp) != 0)
 305                         goto error;
 306                 entp = ((struct ext2fs_htree_node *)bp->b_data)->h_entries;
 307                 info->h_levels_num++;
 308                 info->h_levels[info->h_levels_num - 1].h_bp = bp;
 309         }
 310
 311 error:
 312         ext2_htree_release(info);
 313         return (-1);
 314 }
 315
 316 /*
 317  * Try to lookup a directory entry in HTree index
 318  */
 319 int
 320 ext2_htree_lookup(struct inode *ip, const char *name, int namelen,
 321     struct buf **bpp, int *entryoffp, doff_t *offp,
 322     doff_t *prevoffp, doff_t *endusefulp,
 323     struct ext2fs_searchslot *ss)
 324 {
 325         struct vnode *vp;
 326         struct ext2fs_htree_lookup_info info;
 327         struct ext2fs_htree_entry *leaf_node;
 328         struct m_ext2fs *m_fs;
 329         struct buf *bp;
 330         uint32_t blk;
 331         uint32_t dirhash;
 332         uint32_t bsize;
 333         uint8_t hash_version;
 334         int search_next;
 335         int found = 0;
 336
 337         m_fs = ip->i_e2fs;
 338         bsize = m_fs->e2fs_bsize;
 339         vp = ITOV(ip);
 340
 341         /* TODO: print error msg because we don't lookup '.' and '..' */
 342
 343         memset(&info, 0, sizeof(info));
 344         if (ext2_htree_find_leaf(ip, name, namelen, &dirhash,
 345             &hash_version, &info))
 346                 return (-1);
 347
 348         do {
 349                 leaf_node = info.h_levels[info.h_levels_num - 1].h_entry;
 350                 blk = ext2_htree_get_block(leaf_node);
 351                 if (ext2_blkatoff(vp, blk * bsize, NULL, &bp) != 0) {
 352                         ext2_htree_release(&info);
 353                         return (-1);
 354                 }
 355
 356                 *offp = blk * bsize;
 357                 *entryoffp = 0;
 358                 *prevoffp = blk * bsize;
 359                 *endusefulp = blk * bsize;
 360
 361                 if (ss->slotstatus == NONE) {
 362                         ss->slotoffset = -1;
 363                         ss->slotfreespace = 0;
 364                 }
 365
 366                 if (ext2_search_dirblock(ip, bp->b_data, &found,
 367                     name, namelen, entryoffp, offp, prevoffp,
 368                     endusefulp, ss) != 0) {
 369                         brelse(bp);
 370                         ext2_htree_release(&info);
 371                         return (-1);
 372                 }
 373
 374                 if (found) {
 375                         *bpp = bp;
 376                         ext2_htree_release(&info);
 377                         return (0);
 378                 }
 379
 380                 brelse(bp);
 381                 search_next = ext2_htree_check_next(ip, dirhash, name, &info);
 382         } while (search_next);
 383
 384         ext2_htree_release(&info);
 385         return (ENOENT);
 386 }
 387
 388 static int
 389 ext2_htree_append_block(struct vnode *vp, char *data,
 390     struct componentname *cnp, uint32_t blksize)
 391 {
 392         struct iovec aiov;
 393         struct uio auio;
 394         struct inode *dp = VTOI(vp);
 395         uint64_t cursize, newsize;
 396         int error;
 397
 398         cursize = roundup(dp->i_size, blksize);
 399         newsize = cursize + blksize;
 400
 401         auio.uio_offset = cursize;
 402         auio.uio_resid = blksize;
 403         aiov.iov_len = blksize;
 404         aiov.iov_base = data;
 405         auio.uio_iov = &aiov;
 406         auio.uio_iovcnt = 1;
 407         auio.uio_rw = UIO_WRITE;
 408         auio.uio_segflg = UIO_SYSSPACE;
 409         error = VOP_WRITE(vp, &auio, IO_SYNC, cnp->cn_cred);
 410         if (!error)
 411                 dp->i_size = newsize;
 412
 413         return (error);
 414 }
 415
 416 static int
 417 ext2_htree_writebuf(struct ext2fs_htree_lookup_info *info)
 418 {
 419         int i, error;
 420
 421         for (i = 0; i < info->h_levels_num; i++) {
 422                 struct buf *bp = info->h_levels[i].h_bp;
 423
 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 (entry1->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 = 0;
 585         for (offset = 0; offset < blksize; ) {
 586                 ep = (struct ext2fs_direct_2 *)(block1 + offset);
 587                 offset += ep->e2d_reclen;
 588                 if (ep->e2d_ino) {
 589                         last = (struct ext2fs_direct_2 *)
 590                             ((char *)last + entry_len);
 591                         entry_len = EXT2_DIR_REC_LEN(ep->e2d_namlen);
 592                         memcpy((void *)last, (void *)ep, entry_len);
 593                         last->e2d_reclen = entry_len;
 594                 }
 595         }
 596
 597         if (entry_hash >= *split_hash) {
 598                 /* Add entry to block 2. */
 599                 ext2_append_entry(block2, blksize,
 600                     (struct ext2fs_direct_2 *)dest, entry);
 601
 602                 /* Adjust length field of last entry of block 1. */
 603                 last->e2d_reclen = block1 + blksize - (char *)last;
 604         } else {
 605                 /* Add entry to block 1. */
 606                 ext2_append_entry(block1, blksize, last, entry);
 607
 608                 /* Adjust length field of last entry of block 2. */
 609                 ((struct ext2fs_direct_2 *)dest)->e2d_reclen =
 610                     block2 + blksize - dest;
 611         }
 612
 613         return (0);
 614 }
 615
 616 /*
 617  * Create an HTree index for a directory
 618  */
 619 int
 620 ext2_htree_create_index(struct vnode *vp, struct componentname *cnp,
 621     struct ext2fs_direct_2 *new_entry)
 622 {
 623         struct buf *bp = NULL;
 624         struct inode *dp;
 625         struct ext2fs *fs;
 626         struct m_ext2fs *m_fs;
 627         struct ext2fs_direct_2 *ep, *dotdot;
 628         struct ext2fs_htree_root *root;
 629         struct ext2fs_htree_lookup_info info;
 630         uint32_t blksize, dirlen, split_hash;
 631         uint8_t hash_version;
 632         char *buf1 = NULL;
 633         char *buf2 = NULL;
 634         int error = 0;
 635
 636         dp = VTOI(vp);
 637         fs = dp->i_e2fs->e2fs;
 638         m_fs = dp->i_e2fs;
 639         blksize = m_fs->e2fs_bsize;
 640
 641         buf1 = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO);
 642         buf2 = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO);
 643
 644         if ((error = ext2_blkatoff(vp, 0, NULL, &bp)) != 0)
 645                 goto out;
 646
 647         root = (struct ext2fs_htree_root *)bp->b_data;
 648         dotdot = (struct ext2fs_direct_2 *)((char *)&(root->h_dotdot));
 649         ep = (struct ext2fs_direct_2 *)((char *)dotdot + dotdot->e2d_reclen);
 650         dirlen = (char *)root + blksize - (char *)ep;
 651         memcpy(buf1, ep, dirlen);
 652         ep = (struct ext2fs_direct_2 *)buf1;
 653         while ((char *)ep < buf1 + dirlen)
 654                 ep = (struct ext2fs_direct_2 *)
 655                     ((char *)ep + ep->e2d_reclen);
 656         ep->e2d_reclen = buf1 + blksize - (char *)ep;
 657
 658         dp->i_flag |= IN_E3INDEX;
 659
 660         /*
 661          * Initialize index root.
 662          */
 663         dotdot->e2d_reclen = blksize - EXT2_DIR_REC_LEN(1);
 664         memset(&root->h_info, 0, sizeof(root->h_info));
 665         root->h_info.h_hash_version = fs->e3fs_def_hash_version;
 666         root->h_info.h_info_len = sizeof(root->h_info);
 667         ext2_htree_set_block(root->h_entries, 1);
 668         ext2_htree_set_count(root->h_entries, 1);
 669         ext2_htree_set_limit(root->h_entries,
 670             ext2_htree_root_limit(dp, sizeof(root->h_info)));
 671
 672         memset(&info, 0, sizeof(info));
 673         info.h_levels_num = 1;
 674         info.h_levels[0].h_entries = root->h_entries;
 675         info.h_levels[0].h_entry = root->h_entries;
 676
 677         hash_version = root->h_info.h_hash_version;
 678         if (hash_version <= EXT2_HTREE_TEA)
 679                 hash_version += m_fs->e2fs_uhash;
 680         ext2_htree_split_dirblock(buf1, buf2, blksize, fs->e3fs_hash_seed,
 681             hash_version, &split_hash, new_entry);
 682         ext2_htree_insert_entry(&info, split_hash, 2);
 683
 684         /*
 685          * Write directory block 0.
 686          */
 687         if (DOINGASYNC(vp)) {
 688                 bdwrite(bp);
 689                 error = 0;
 690         } else {
 691                 error = bwrite(bp);
 692         }
 693         dp->i_flag |= IN_CHANGE | IN_UPDATE;
 694         if (error)
 695                 goto out;
 696
 697         /*
 698          * Write directory block 1.
 699          */
 700         error = ext2_htree_append_block(vp, buf1, cnp, blksize);
 701         if (error)
 702                 goto out1;
 703
 704         /*
 705          * Write directory block 2.
 706          */
 707         error = ext2_htree_append_block(vp, buf2, cnp, blksize);
 708
 709         free(buf1, M_TEMP);
 710         free(buf2, M_TEMP);
 711         return (error);
 712 out:
 713         if (bp != NULL)
 714                 brelse(bp);
 715 out1:
 716         free(buf1, M_TEMP);
 717         free(buf2, M_TEMP);
 718         return (error);
 719 }
 720
 721 /*
 722  * Add an entry to the directory using htree index.
 723  */
 724 int
 725 ext2_htree_add_entry(struct vnode *dvp, struct ext2fs_direct_2 *entry,
 726     struct componentname *cnp)
 727 {
 728         struct ext2fs_htree_entry *entries, *leaf_node;
 729         struct ext2fs_htree_lookup_info info;
 730         struct buf *bp = NULL;
 731         struct ext2fs *fs;
 732         struct m_ext2fs *m_fs;
 733         struct inode *ip;
 734         uint16_t ent_num;
 735         uint32_t dirhash, split_hash;
 736         uint32_t blksize, blknum;
 737         uint64_t cursize, dirsize;
 738         uint8_t hash_version;
 739         char *newdirblock = NULL;
 740         char *newidxblock = NULL;
 741         struct ext2fs_htree_node *dst_node;
 742         struct ext2fs_htree_entry *dst_entries;
 743         struct ext2fs_htree_entry *root_entires;
 744         struct buf *dst_bp = NULL;
 745         int error, write_bp = 0, write_dst_bp = 0, write_info = 0;
 746
 747         ip = VTOI(dvp);
 748         m_fs = ip->i_e2fs;
 749         fs = m_fs->e2fs;
 750         blksize = m_fs->e2fs_bsize;
 751
 752         if (ip->i_count != 0)
 753                 return ext2_add_entry(dvp, entry);
 754
 755         /* Target directory block is full, split it */
 756         memset(&info, 0, sizeof(info));
 757         error = ext2_htree_find_leaf(ip, entry->e2d_name, entry->e2d_namlen,
 758             &dirhash, &hash_version, &info);
 759         if (error)
 760                 return (error);
 761
 762         entries = info.h_levels[info.h_levels_num - 1].h_entries;
 763         ent_num = ext2_htree_get_count(entries);
 764         if (ent_num == ext2_htree_get_limit(entries)) {
 765                 /* Split the index node. */
 766                 root_entires = info.h_levels[0].h_entries;
 767                 newidxblock = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO);
 768                 dst_node = (struct ext2fs_htree_node *)newidxblock;
 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 = cursize + 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
 812                                 info.h_levels[1].h_bp = dst_bp;
 813                                 dst_bp = tmp;
 814
 815                                 info.h_levels[1].h_entry =
 816                                     info.h_levels[1].h_entry -
 817                                     (entries + src_ent_num) +
 818                                     dst_entries;
 819                                 info.h_levels[1].h_entries = dst_entries;
 820                         }
 821                         ext2_htree_insert_entry_to_level(&info.h_levels[0],
 822                             split_hash, blknum);
 823
 824                         /* Write new index node to disk */
 825                         error = bwrite(dst_bp);
 826                         ip->i_flag |= IN_CHANGE | IN_UPDATE;
 827                         if (error)
 828                                 goto finish;
 829                         write_dst_bp = 1;
 830                 } else {
 831                         /* Create second level for htree index */
 832                         struct ext2fs_htree_root *idx_root;
 833
 834                         memcpy(dst_entries, entries,
 835                             ent_num * sizeof(struct ext2fs_htree_entry));
 836                         ext2_htree_set_limit(dst_entries,
 837                             ext2_htree_node_limit(ip));
 838
 839                         idx_root = (struct ext2fs_htree_root *)
 840                             info.h_levels[0].h_bp->b_data;
 841                         idx_root->h_info.h_ind_levels = 1;
 842
 843                         ext2_htree_set_count(entries, 1);
 844                         ext2_htree_set_block(entries, blknum);
 845
 846                         info.h_levels_num = 2;
 847                         info.h_levels[1].h_entries = dst_entries;
 848                         info.h_levels[1].h_entry = info.h_levels[0].h_entry -
 849                             info.h_levels[0].h_entries + dst_entries;
 850                         info.h_levels[1].h_bp = dst_bp;
 851                         dst_bp = NULL;
 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 = cursize + 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 }