ext2_htree.c revision 261311
1241675Suqs/*- 2241675Suqs * Copyright (c) 2010, 2012 Zheng Liu <lz@freebsd.org> 3241675Suqs * Copyright (c) 2012, Vyacheslav Matyushin 4241675Suqs * All rights reserved. 5241675Suqs * 6241675Suqs * Redistribution and use in source and binary forms, with or without 7241675Suqs * modification, are permitted provided that the following conditions 8241675Suqs * are met: 9241675Suqs * 1. Redistributions of source code must retain the above copyright 10241675Suqs * notice, this list of conditions and the following disclaimer. 11241675Suqs * 2. Redistributions in binary form must reproduce the above copyright 12241675Suqs * notice, this list of conditions and the following disclaimer in the 13241675Suqs * documentation and/or other materials provided with the distribution. 14241675Suqs * 15241675Suqs * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 16241675Suqs * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17241675Suqs * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18241675Suqs * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 19241675Suqs * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20241675Suqs * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21241675Suqs * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22241675Suqs * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23241675Suqs * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24241675Suqs * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25241675Suqs * SUCH DAMAGE. 26241675Suqs * 27241675Suqs * $FreeBSD: head/sys/fs/ext2fs/ext2_htree.c 261235 2014-01-28 14:39:05Z pfg $ 28241675Suqs */ 29241675Suqs 30241675Suqs#include <sys/param.h> 31241675Suqs#include <sys/endian.h> 32241675Suqs#include <sys/systm.h> 33241675Suqs#include <sys/namei.h> 34241675Suqs#include <sys/bio.h> 35241675Suqs#include <sys/buf.h> 36241675Suqs#include <sys/endian.h> 37241675Suqs#include <sys/mount.h> 38241675Suqs#include <sys/vnode.h> 39241675Suqs#include <sys/malloc.h> 40241675Suqs#include <sys/dirent.h> 41241675Suqs#include <sys/sysctl.h> 42241675Suqs 43241675Suqs#include <ufs/ufs/dir.h> 44241675Suqs 45241675Suqs#include <fs/ext2fs/inode.h> 46241675Suqs#include <fs/ext2fs/ext2_mount.h> 47241675Suqs#include <fs/ext2fs/ext2fs.h> 48241675Suqs#include <fs/ext2fs/fs.h> 49241675Suqs#include <fs/ext2fs/ext2_extern.h> 50241675Suqs#include <fs/ext2fs/ext2_dinode.h> 51241675Suqs#include <fs/ext2fs/ext2_dir.h> 52241675Suqs#include <fs/ext2fs/htree.h> 53241675Suqs 54241675Suqsstatic void ext2_append_entry(char *block, uint32_t blksize, 55241675Suqs struct ext2fs_direct_2 *last_entry, 56241675Suqs struct ext2fs_direct_2 *new_entry); 57241675Suqsstatic int ext2_htree_append_block(struct vnode *vp, char *data, 58241675Suqs struct componentname *cnp, uint32_t blksize); 59241675Suqsstatic int ext2_htree_check_next(struct inode *ip, uint32_t hash, 60241675Suqs const char *name, struct ext2fs_htree_lookup_info *info); 61241675Suqsstatic int ext2_htree_cmp_sort_entry(const void *e1, const void *e2); 62241675Suqsstatic int ext2_htree_find_leaf(struct inode *ip, const char *name, 63241675Suqs int namelen, uint32_t *hash, uint8_t *hash_verion, 64241675Suqs struct ext2fs_htree_lookup_info *info); 65241675Suqsstatic uint32_t ext2_htree_get_block(struct ext2fs_htree_entry *ep); 66241675Suqsstatic uint16_t ext2_htree_get_count(struct ext2fs_htree_entry *ep); 67241675Suqsstatic uint32_t ext2_htree_get_hash(struct ext2fs_htree_entry *ep); 68241675Suqsstatic uint16_t ext2_htree_get_limit(struct ext2fs_htree_entry *ep); 69241675Suqsstatic void ext2_htree_insert_entry_to_level(struct ext2fs_htree_lookup_level *level, 70241675Suqs uint32_t hash, uint32_t blk); 71241675Suqsstatic void ext2_htree_insert_entry(struct ext2fs_htree_lookup_info *info, 72241675Suqs uint32_t hash, uint32_t blk); 73241675Suqsstatic uint32_t ext2_htree_node_limit(struct inode *ip); 74241675Suqsstatic void ext2_htree_set_block(struct ext2fs_htree_entry *ep, 75241675Suqs uint32_t blk); 76241675Suqsstatic void ext2_htree_set_count(struct ext2fs_htree_entry *ep, 77241675Suqs uint16_t cnt); 78241675Suqsstatic void ext2_htree_set_hash(struct ext2fs_htree_entry *ep, 79241675Suqs uint32_t hash); 80241675Suqsstatic void ext2_htree_set_limit(struct ext2fs_htree_entry *ep, 81241675Suqs uint16_t limit); 82241675Suqsstatic int ext2_htree_split_dirblock(char *block1, char *block2, 83241675Suqs uint32_t blksize, uint32_t *hash_seed, uint8_t hash_version, 84241675Suqs uint32_t *split_hash, struct ext2fs_direct_2 *entry); 85241675Suqsstatic void ext2_htree_release(struct ext2fs_htree_lookup_info *info); 86241675Suqsstatic uint32_t ext2_htree_root_limit(struct inode *ip, int len); 87241675Suqsstatic int ext2_htree_writebuf(struct ext2fs_htree_lookup_info *info); 88241675Suqs 89241675Suqsint 90241675Suqsext2_htree_has_idx(struct inode *ip) 91241675Suqs{ 92241675Suqs if (EXT2_HAS_COMPAT_FEATURE(ip->i_e2fs, EXT2F_COMPAT_DIRHASHINDEX) && 93241675Suqs ip->i_flag & IN_E4INDEX) 94241675Suqs return (1); 95241675Suqs else 96241675Suqs return (0); 97241675Suqs} 98241675Suqs 99241675Suqsstatic int 100241675Suqsext2_htree_check_next(struct inode *ip, uint32_t hash, const char *name, 101241675Suqs struct ext2fs_htree_lookup_info *info) 102241675Suqs{ 103241675Suqs struct vnode *vp = ITOV(ip); 104241675Suqs struct ext2fs_htree_lookup_level *level; 105241675Suqs struct buf *bp; 106241675Suqs uint32_t next_hash; 107241675Suqs int idx = info->h_levels_num - 1; 108241675Suqs int levels = 0; 109241675Suqs 110241675Suqs do { 111241675Suqs level = &info->h_levels[idx]; 112241675Suqs level->h_entry++; 113241675Suqs if (level->h_entry < level->h_entries + 114241675Suqs ext2_htree_get_count(level->h_entries)) 115241675Suqs break; 116241675Suqs if (idx == 0) 117241675Suqs return (0); 118241675Suqs idx--; 119241675Suqs levels++; 120241675Suqs } while (1); 121241675Suqs 122241675Suqs next_hash = ext2_htree_get_hash(level->h_entry); 123241675Suqs if ((hash & 1) == 0) { 124241675Suqs if (hash != (next_hash & ~1)) 125241675Suqs return (0); 126241675Suqs } 127241675Suqs 128241675Suqs while (levels > 0) { 129241675Suqs levels--; 130241675Suqs if (ext2_blkatoff(vp, ext2_htree_get_block(level->h_entry) * 131241675Suqs ip->i_e2fs->e2fs_bsize, NULL, &bp) != 0) 132241675Suqs return (0); 133241675Suqs level = &info->h_levels[idx + 1]; 134241675Suqs brelse(level->h_bp); 135241675Suqs level->h_bp = bp; 136241675Suqs level->h_entry = level->h_entries = 137241675Suqs ((struct ext2fs_htree_node *)bp->b_data)->h_entries; 138241675Suqs } 139241675Suqs 140241675Suqs return (1); 141241675Suqs} 142241675Suqs 143241675Suqsstatic uint32_t 144241675Suqsext2_htree_get_block(struct ext2fs_htree_entry *ep) 145241675Suqs{ 146241675Suqs return (ep->h_blk & 0x00FFFFFF); 147241675Suqs} 148241675Suqs 149241675Suqsstatic void 150241675Suqsext2_htree_set_block(struct ext2fs_htree_entry *ep, uint32_t blk) 151241675Suqs{ 152241675Suqs ep->h_blk = blk; 153241675Suqs} 154241675Suqs 155241675Suqsstatic uint16_t 156241675Suqsext2_htree_get_count(struct ext2fs_htree_entry *ep) 157241675Suqs{ 158241675Suqs return (((struct ext2fs_htree_count *)(ep))->h_entries_num); 159241675Suqs} 160241675Suqs 161241675Suqsstatic void 162241675Suqsext2_htree_set_count(struct ext2fs_htree_entry *ep, uint16_t cnt) 163241675Suqs{ 164241675Suqs ((struct ext2fs_htree_count *)(ep))->h_entries_num = cnt; 165241675Suqs} 166241675Suqs 167241675Suqsstatic 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 = roundup(dp->i_size, blksize) + 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 (entry2->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 = EXT2_DIR_REC_LEN(last->e2d_namlen); 583 for (offset = last->e2d_reclen; offset < blksize; ) { 584 ep = (struct ext2fs_direct_2 *)(block1 + offset); 585 offset += ep->e2d_reclen; 586 if (last->e2d_ino) { 587 /* Trim the existing slot */ 588 last->e2d_reclen = entry_len; 589 last = (struct ext2fs_direct_2 *) 590 ((char *)last + entry_len); 591 } 592 entry_len = EXT2_DIR_REC_LEN(ep->e2d_namlen); 593 memcpy((void *)last, (void *)ep, entry_len); 594 } 595 596 if (entry_hash >= *split_hash) { 597 /* Add entry to block 2. */ 598 ext2_append_entry(block2, blksize, 599 (struct ext2fs_direct_2 *)dest, entry); 600 601 /* Adjust length field of last entry of block 1. */ 602 last->e2d_reclen = block1 + blksize - (char *)last; 603 } else { 604 /* Add entry to block 1. */ 605 ext2_append_entry(block1, blksize, last, entry); 606 607 /* Adjust length field of last entry of block 2. */ 608 ((struct ext2fs_direct_2 *)dest)->e2d_reclen = 609 block2 + blksize - dest; 610 } 611 612 return (0); 613} 614 615/* 616 * Create an HTree index for a directory 617 */ 618int 619ext2_htree_create_index(struct vnode *vp, struct componentname *cnp, 620 struct ext2fs_direct_2 *new_entry) 621{ 622 struct buf *bp = NULL; 623 struct inode *dp; 624 struct ext2fs *fs; 625 struct m_ext2fs *m_fs; 626 struct ext2fs_direct_2 *ep, *dotdot; 627 struct ext2fs_htree_root *root; 628 struct ext2fs_htree_lookup_info info; 629 uint32_t blksize, dirlen, split_hash; 630 uint8_t hash_version; 631 char *buf1 = NULL; 632 char *buf2 = NULL; 633 int error = 0; 634 635 dp = VTOI(vp); 636 fs = dp->i_e2fs->e2fs; 637 m_fs = dp->i_e2fs; 638 blksize = m_fs->e2fs_bsize; 639 640 buf1 = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO); 641 buf2 = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO); 642 643 if ((error = ext2_blkatoff(vp, 0, NULL, &bp)) != 0) 644 goto out; 645 646 root = (struct ext2fs_htree_root *)bp->b_data; 647 dotdot = (struct ext2fs_direct_2 *)((char *)&(root->h_dotdot)); 648 ep = (struct ext2fs_direct_2 *)((char *)dotdot + dotdot->e2d_reclen); 649 dirlen = (char *)root + blksize - (char *)ep; 650 memcpy(buf1, ep, dirlen); 651 ep = (struct ext2fs_direct_2 *)buf1; 652 while ((char *)ep < buf1 + dirlen) 653 ep = (struct ext2fs_direct_2 *) 654 ((char *)ep + ep->e2d_reclen); 655 ep->e2d_reclen = buf1 + blksize - (char *)ep; 656 657 dp->i_flag |= IN_E4INDEX; 658 659 /* 660 * Initialize index root. 661 */ 662 dotdot->e2d_reclen = blksize - EXT2_DIR_REC_LEN(1); 663 memset(&root->h_info, 0, sizeof(root->h_info)); 664 root->h_info.h_hash_version = fs->e3fs_def_hash_version; 665 root->h_info.h_info_len = sizeof(root->h_info); 666 ext2_htree_set_block(root->h_entries, 1); 667 ext2_htree_set_count(root->h_entries, 1); 668 ext2_htree_set_limit(root->h_entries, 669 ext2_htree_root_limit(dp, sizeof(root->h_info))); 670 671 memset(&info, 0, sizeof(info)); 672 info.h_levels_num = 1; 673 info.h_levels[0].h_entries = root->h_entries; 674 info.h_levels[0].h_entry = root->h_entries; 675 676 hash_version = root->h_info.h_hash_version; 677 if (hash_version <= EXT2_HTREE_TEA) 678 hash_version += m_fs->e2fs_uhash; 679 ext2_htree_split_dirblock(buf1, buf2, blksize, fs->e3fs_hash_seed, 680 hash_version, &split_hash, new_entry); 681 ext2_htree_insert_entry(&info, split_hash, 2); 682 683 /* 684 * Write directory block 0. 685 */ 686 if (DOINGASYNC(vp)) { 687 bdwrite(bp); 688 error = 0; 689 } else { 690 error = bwrite(bp); 691 } 692 dp->i_flag |= IN_CHANGE | IN_UPDATE; 693 if (error) 694 goto out; 695 696 /* 697 * Write directory block 1. 698 */ 699 error = ext2_htree_append_block(vp, buf1, cnp, blksize); 700 if (error) 701 goto out1; 702 703 /* 704 * Write directory block 2. 705 */ 706 error = ext2_htree_append_block(vp, buf2, cnp, blksize); 707 708 free(buf1, M_TEMP); 709 free(buf2, M_TEMP); 710 return (error); 711out: 712 if (bp != NULL) 713 brelse(bp); 714out1: 715 free(buf1, M_TEMP); 716 free(buf2, M_TEMP); 717 return (error); 718} 719 720/* 721 * Add an entry to the directory using htree index. 722 */ 723int 724ext2_htree_add_entry(struct vnode *dvp, struct ext2fs_direct_2 *entry, 725 struct componentname *cnp) 726{ 727 struct ext2fs_htree_entry *entries, *leaf_node; 728 struct ext2fs_htree_lookup_info info; 729 struct buf *bp = NULL; 730 struct ext2fs *fs; 731 struct m_ext2fs *m_fs; 732 struct inode *ip; 733 uint16_t ent_num; 734 uint32_t dirhash, split_hash; 735 uint32_t blksize, blknum; 736 uint64_t cursize, dirsize; 737 uint8_t hash_version; 738 char *newdirblock = NULL; 739 char *newidxblock = NULL; 740 struct ext2fs_htree_node *dst_node; 741 struct ext2fs_htree_entry *dst_entries; 742 struct ext2fs_htree_entry *root_entires; 743 struct buf *dst_bp = NULL; 744 int error, write_bp = 0, write_dst_bp = 0, write_info = 0; 745 746 ip = VTOI(dvp); 747 m_fs = ip->i_e2fs; 748 fs = m_fs->e2fs; 749 blksize = m_fs->e2fs_bsize; 750 751 if (ip->i_count != 0) 752 return ext2_add_entry(dvp, entry); 753 754 /* Target directory block is full, split it */ 755 memset(&info, 0, sizeof(info)); 756 error = ext2_htree_find_leaf(ip, entry->e2d_name, entry->e2d_namlen, 757 &dirhash, &hash_version, &info); 758 if (error) 759 return (error); 760 761 entries = info.h_levels[info.h_levels_num - 1].h_entries; 762 ent_num = ext2_htree_get_count(entries); 763 if (ent_num == ext2_htree_get_limit(entries)) { 764 /* Split the index node. */ 765 root_entires = info.h_levels[0].h_entries; 766 newidxblock = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO); 767 dst_node = (struct ext2fs_htree_node *)newidxblock; 768 dst_entries = dst_node->h_entries; 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 = roundup(ip->i_size, blksize) + 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 info.h_levels[1].h_bp = dst_bp; 812 dst_bp = tmp; 813 814 info.h_levels[1].h_entry = 815 info.h_levels[1].h_entry - 816 (entries + src_ent_num) + 817 dst_entries; 818 info.h_levels[1].h_entries = dst_entries; 819 } 820 ext2_htree_insert_entry_to_level(&info.h_levels[0], 821 split_hash, blknum); 822 823 /* Write new index node to disk */ 824 error = bwrite(dst_bp); 825 ip->i_flag |= IN_CHANGE | IN_UPDATE; 826 if (error) 827 goto finish; 828 write_dst_bp = 1; 829 } else { 830 /* Create second level for htree index */ 831 struct ext2fs_htree_root *idx_root; 832 833 memcpy(dst_entries, entries, 834 ent_num * sizeof(struct ext2fs_htree_entry)); 835 ext2_htree_set_limit(dst_entries, 836 ext2_htree_node_limit(ip)); 837 838 idx_root = (struct ext2fs_htree_root *) 839 info.h_levels[0].h_bp->b_data; 840 idx_root->h_info.h_ind_levels = 1; 841 842 ext2_htree_set_count(entries, 1); 843 ext2_htree_set_block(entries, blknum); 844 845 info.h_levels_num = 2; 846 info.h_levels[1].h_entries = dst_entries; 847 info.h_levels[1].h_entry = info.h_levels[0].h_entry - 848 info.h_levels[0].h_entries + dst_entries; 849 info.h_levels[1].h_bp = dst_bp; 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 = roundup(ip->i_size, blksize) + 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