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