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