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