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