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