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