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