2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
4 * Copyright (c) 2010, 2012 Zheng Liu <lz@freebsd.org>
5 * Copyright (c) 2012, Vyacheslav Matyushin
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
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.
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
32 #include <sys/param.h>
33 #include <sys/endian.h>
34 #include <sys/systm.h>
35 #include <sys/namei.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>
45 #include <ufs/ufs/dir.h>
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>
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,
79 static void ext2_htree_set_count(struct ext2fs_htree_entry *ep,
81 static void ext2_htree_set_hash(struct ext2fs_htree_entry *ep,
83 static void ext2_htree_set_limit(struct ext2fs_htree_entry *ep,
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);
95 ext2_htree_has_idx(struct inode *ip)
97 if (EXT2_HAS_COMPAT_FEATURE(ip->i_e2fs, EXT2F_COMPAT_DIRHASHINDEX) &&
98 ip->i_flag & IN_E3INDEX)
105 ext2_htree_check_next(struct inode *ip, uint32_t hash, const char *name,
106 struct ext2fs_htree_lookup_info *info)
108 struct vnode *vp = ITOV(ip);
109 struct ext2fs_htree_lookup_level *level;
112 int idx = info->h_levels_num - 1;
116 level = &info->h_levels[idx];
118 if (level->h_entry < level->h_entries +
119 ext2_htree_get_count(level->h_entries))
127 next_hash = ext2_htree_get_hash(level->h_entry);
128 if ((hash & 1) == 0) {
129 if (hash != (next_hash & ~1))
135 if (ext2_blkatoff(vp, ext2_htree_get_block(level->h_entry) *
136 ip->i_e2fs->e2fs_bsize, NULL, &bp) != 0)
138 level = &info->h_levels[idx + 1];
141 level->h_entry = level->h_entries =
142 ((struct ext2fs_htree_node *)bp->b_data)->h_entries;
149 ext2_htree_get_block(struct ext2fs_htree_entry *ep)
151 return (ep->h_blk & 0x00FFFFFF);
155 ext2_htree_set_block(struct ext2fs_htree_entry *ep, uint32_t blk)
161 ext2_htree_get_count(struct ext2fs_htree_entry *ep)
163 return (((struct ext2fs_htree_count *)(ep))->h_entries_num);
167 ext2_htree_set_count(struct ext2fs_htree_entry *ep, uint16_t cnt)
169 ((struct ext2fs_htree_count *)(ep))->h_entries_num = cnt;
173 ext2_htree_get_hash(struct ext2fs_htree_entry *ep)
179 ext2_htree_get_limit(struct ext2fs_htree_entry *ep)
181 return (((struct ext2fs_htree_count *)(ep))->h_entries_max);
185 ext2_htree_set_hash(struct ext2fs_htree_entry *ep, uint32_t hash)
191 ext2_htree_set_limit(struct ext2fs_htree_entry *ep, uint16_t limit)
193 ((struct ext2fs_htree_count *)(ep))->h_entries_max = limit;
197 ext2_htree_release(struct ext2fs_htree_lookup_info *info)
201 for (i = 0; i < info->h_levels_num; i++) {
202 struct buf *bp = info->h_levels[i].h_bp;
210 ext2_htree_root_limit(struct inode *ip, int len)
216 space = ip->i_e2fs->e2fs_bsize - EXT2_DIR_REC_LEN(1) -
217 EXT2_DIR_REC_LEN(2) - len;
219 if (EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_METADATA_CKSUM))
220 space -= sizeof(struct ext2fs_htree_tail);
222 return (space / sizeof(struct ext2fs_htree_entry));
226 ext2_htree_node_limit(struct inode *ip)
232 space = fs->e2fs_bsize - EXT2_DIR_REC_LEN(0);
234 if (EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_METADATA_CKSUM))
235 space -= sizeof(struct ext2fs_htree_tail);
237 return (space / sizeof(struct ext2fs_htree_entry));
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)
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;
256 if (name == NULL || info == NULL)
260 fs = ip->i_e2fs->e2fs;
263 if (ext2_blkatoff(vp, 0, NULL, &bp) != 0)
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)
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;
279 ext2_htree_hash(name, namelen, fs->e3fs_hash_seed,
280 hash_version, &hash_major, &hash_minor);
283 if ((levels = rootp->h_info.h_ind_levels) > 1)
286 entp = (struct ext2fs_htree_entry *)(((char *)&rootp->h_info) +
287 rootp->h_info.h_info_len);
289 if (ext2_htree_get_limit(entp) !=
290 ext2_htree_root_limit(ip, rootp->h_info.h_info_len))
294 cnt = ext2_htree_get_count(entp);
295 if (cnt == 0 || cnt > ext2_htree_get_limit(entp))
299 end = entp + cnt - 1;
300 while (start <= end) {
301 middle = start + (end - start) / 2;
302 if (ext2_htree_get_hash(middle) > hash_major)
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;
316 if (ext2_blkatoff(vp,
317 ext2_htree_get_block(found) * m_fs->e2fs_bsize,
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;
326 ext2_htree_release(info);
331 * Try to lookup a directory entry in HTree index
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)
340 struct ext2fs_htree_lookup_info info;
341 struct ext2fs_htree_entry *leaf_node;
342 struct m_ext2fs *m_fs;
347 uint8_t hash_version;
352 bsize = m_fs->e2fs_bsize;
355 /* TODO: print error msg because we don't lookup '.' and '..' */
357 memset(&info, 0, sizeof(info));
358 if (ext2_htree_find_leaf(ip, name, namelen, &dirhash,
359 &hash_version, &info))
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);
372 *prevoffp = blk * bsize;
373 *endusefulp = blk * bsize;
375 if (ss->slotstatus == NONE) {
377 ss->slotfreespace = 0;
380 if (ext2_search_dirblock(ip, bp->b_data, &found,
381 name, namelen, entryoffp, offp, prevoffp,
382 endusefulp, ss) != 0) {
384 ext2_htree_release(&info);
390 ext2_htree_release(&info);
395 search_next = ext2_htree_check_next(ip, dirhash, name, &info);
396 } while (search_next);
398 ext2_htree_release(&info);
403 ext2_htree_append_block(struct vnode *vp, char *data,
404 struct componentname *cnp, uint32_t blksize)
408 struct inode *dp = VTOI(vp);
409 uint64_t cursize, newsize;
412 cursize = roundup(dp->i_size, blksize);
413 newsize = cursize + blksize;
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;
421 auio.uio_rw = UIO_WRITE;
422 auio.uio_segflg = UIO_SYSSPACE;
423 error = VOP_WRITE(vp, &auio, IO_SYNC, cnp->cn_cred);
425 dp->i_size = newsize;
431 ext2_htree_writebuf(struct inode* ip, struct ext2fs_htree_lookup_info *info)
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);
447 ext2_htree_insert_entry_to_level(struct ext2fs_htree_lookup_level *level,
448 uint32_t hash, uint32_t blk)
450 struct ext2fs_htree_entry *target;
453 target = level->h_entry + 1;
454 entries_num = ext2_htree_get_count(level->h_entries);
456 memmove(target + 1, target, (char *)(level->h_entries + entries_num) -
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);
464 * Insert an index entry to the index node.
467 ext2_htree_insert_entry(struct ext2fs_htree_lookup_info *info,
468 uint32_t hash, uint32_t blk)
470 struct ext2fs_htree_lookup_level *level;
472 level = &info->h_levels[info->h_levels_num - 1];
473 ext2_htree_insert_entry_to_level(level, hash, blk);
477 * Compare two entry sort descriptors by name hash value.
478 * This is used together with qsort.
481 ext2_htree_cmp_sort_entry(const void *e1, const void *e2)
483 const struct ext2fs_htree_sort_entry *entry1, *entry2;
485 entry1 = (const struct ext2fs_htree_sort_entry *)e1;
486 entry2 = (const struct ext2fs_htree_sort_entry *)e2;
488 if (entry1->h_hash < entry2->h_hash)
490 if (entry1->h_hash > entry2->h_hash)
496 * Append an entry to the end of the directory block.
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)
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));
513 * Move half of entries from the old directory block to the new one.
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)
522 int size = 0, csum_size = 0;
525 uint16_t entry_len = 0;
527 struct ext2fs_direct_2 *ep, *last;
529 struct ext2fs_htree_sort_entry *sort_info;
532 ep = (struct ext2fs_direct_2 *)block1;
534 sort_info = (struct ext2fs_htree_sort_entry *)
535 ((char *)block2 + blksize);
537 if (EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_METADATA_CKSUM))
538 csum_size = sizeof(struct ext2fs_direct_tail);
541 * Calculate name hash value for the entry which is to be added.
543 ext2_htree_hash(entry->e2d_name, entry->e2d_namlen, hash_seed,
544 hash_version, &entry_hash, NULL);
547 * Fill in directory entry sort descriptors.
549 while ((char *)ep < block1 + blksize - csum_size) {
550 if (ep->e2d_ino && ep->e2d_namlen) {
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);
559 ep = (struct ext2fs_direct_2 *)
560 ((char *)ep + ep->e2d_reclen);
564 * Sort directory entry descriptors by name hash value.
566 qsort(sort_info, entry_cnt, sizeof(struct ext2fs_htree_sort_entry),
567 ext2_htree_cmp_sort_entry);
570 * Count the number of entries to move to directory block 2.
572 for (i = entry_cnt - 1; i >= 0; i--) {
573 if (sort_info[i].h_size + size > blksize / 2)
575 size += sort_info[i].h_size;
578 *split_hash = sort_info[i + 1].h_hash;
583 if (*split_hash == sort_info[i].h_hash)
587 * Move half of directory entries from block 1 to block 2.
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. */
601 /* Shrink directory entries in block 1. */
602 last = (struct ext2fs_direct_2 *)block1;
604 for (offset = 0; offset < blksize - csum_size; ) {
605 ep = (struct ext2fs_direct_2 *)(block1 + offset);
606 offset += ep->e2d_reclen;
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;
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);
621 /* Adjust length field of last entry of block 1. */
622 last->e2d_reclen = block1 + blksize - (char *)last - csum_size;
624 /* Add entry to block 1. */
625 ext2_append_entry(block1, blksize, last, entry, csum_size);
627 /* Adjust length field of last entry of block 2. */
628 ((struct ext2fs_direct_2 *)dest)->e2d_reclen =
629 block2 + blksize - dest - csum_size;
633 ext2_init_dirent_tail(EXT2_DIRENT_TAIL(block1, blksize));
634 ext2_init_dirent_tail(EXT2_DIRENT_TAIL(block2, blksize));
641 * Create an HTree index for a directory
644 ext2_htree_create_index(struct vnode *vp, struct componentname *cnp,
645 struct ext2fs_direct_2 *new_entry)
647 struct buf *bp = NULL;
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;
661 fs = dp->i_e2fs->e2fs;
663 blksize = m_fs->e2fs_bsize;
665 buf1 = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO);
666 buf2 = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO);
668 if ((error = ext2_blkatoff(vp, 0, NULL, &bp)) != 0)
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;
682 dp->i_flag |= IN_E3INDEX;
685 * Initialize index root.
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)));
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;
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);
709 * Write directory block 0.
711 ext2_dx_csum_set(dp, (struct ext2fs_direct_2 *)bp->b_data);
712 if (DOINGASYNC(vp)) {
718 dp->i_flag |= IN_CHANGE | IN_UPDATE;
723 * Write directory block 1.
725 ext2_dirent_csum_set(dp, (struct ext2fs_direct_2 *)buf1);
726 error = ext2_htree_append_block(vp, buf1, cnp, blksize);
731 * Write directory block 2.
733 ext2_dirent_csum_set(dp, (struct ext2fs_direct_2 *)buf2);
734 error = ext2_htree_append_block(vp, buf2, cnp, blksize);
749 * Add an entry to the directory using htree index.
752 ext2_htree_add_entry(struct vnode *dvp, struct ext2fs_direct_2 *entry,
753 struct componentname *cnp)
755 struct ext2fs_htree_entry *entries, *leaf_node;
756 struct ext2fs_htree_lookup_info info;
757 struct buf *bp = NULL;
759 struct m_ext2fs *m_fs;
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;
777 blksize = m_fs->e2fs_bsize;
779 if (ip->i_count != 0)
780 return ext2_add_entry(dvp, entry);
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);
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;
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,
808 error = ext2_blkatoff(dvp, cursize, NULL, &dst_bp);
811 dst_node = (struct ext2fs_htree_node *)dst_bp->b_data;
812 dst_entries = dst_node->h_entries;
814 if (info.h_levels_num == 2) {
815 uint16_t src_ent_num, dst_ent_num;
817 if (ext2_htree_get_count(root_entires) ==
818 ext2_htree_get_limit(root_entires)) {
819 /* Directory index is full */
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);
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));
836 if (info.h_levels[1].h_entry >= entries + src_ent_num) {
837 struct buf *tmp = info.h_levels[1].h_bp;
839 info.h_levels[1].h_bp = dst_bp;
842 info.h_levels[1].h_entry =
843 info.h_levels[1].h_entry -
844 (entries + src_ent_num) +
846 info.h_levels[1].h_entries = dst_entries;
848 ext2_htree_insert_entry_to_level(&info.h_levels[0],
851 /* Write new index node to disk */
853 (struct ext2fs_direct_2 *)dst_bp->b_data);
854 error = bwrite(dst_bp);
855 ip->i_flag |= IN_CHANGE | IN_UPDATE;
860 /* Create second level for htree index */
861 struct ext2fs_htree_root *idx_root;
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));
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;
872 ext2_htree_set_count(entries, 1);
873 ext2_htree_set_block(entries, blknum);
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;
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);
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;
898 /* Add index entry for the new directory block */
899 ext2_htree_insert_entry(&info, split_hash, blknum);
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);
907 /* Write the target directory block */
908 ext2_dirent_csum_set(ip, (struct ext2fs_direct_2 *)bp->b_data);
910 ip->i_flag |= IN_CHANGE | IN_UPDATE;
915 /* Write the index block */
916 error = ext2_htree_writebuf(ip, &info);
921 if (dst_bp != NULL && !write_dst_bp)
923 if (bp != NULL && !write_bp)
925 if (newdirblock != NULL)
926 free(newdirblock, M_TEMP);
927 if (newidxblock != NULL)
928 free(newidxblock, M_TEMP);
930 ext2_htree_release(&info);