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