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>
44 #include <sys/sysctl.h>
46 #include <ufs/ufs/dir.h>
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>
58 SDT_PROVIDER_DECLARE(ext2fs);
61 * arg0: verbosity. Higher numbers give more verbose messages
62 * arg1: Textual message
64 SDT_PROBE_DEFINE2(ext2fs, , trace, htree, "int", "char*");
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,
88 static void ext2_htree_set_count(struct ext2fs_htree_entry *ep,
90 static void ext2_htree_set_hash(struct ext2fs_htree_entry *ep,
92 static void ext2_htree_set_limit(struct ext2fs_htree_entry *ep,
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);
104 ext2_htree_has_idx(struct inode *ip)
106 if (EXT2_HAS_COMPAT_FEATURE(ip->i_e2fs, EXT2F_COMPAT_DIRHASHINDEX) &&
107 ip->i_flag & IN_E3INDEX)
114 ext2_htree_check_next(struct inode *ip, uint32_t hash, const char *name,
115 struct ext2fs_htree_lookup_info *info)
117 struct vnode *vp = ITOV(ip);
118 struct ext2fs_htree_lookup_level *level;
121 int idx = info->h_levels_num - 1;
125 level = &info->h_levels[idx];
127 if (level->h_entry < level->h_entries +
128 ext2_htree_get_count(level->h_entries))
136 next_hash = ext2_htree_get_hash(level->h_entry);
137 if ((hash & 1) == 0) {
138 if (hash != (next_hash & ~1))
144 if (ext2_blkatoff(vp, ext2_htree_get_block(level->h_entry) *
145 ip->i_e2fs->e2fs_bsize, NULL, &bp) != 0)
147 level = &info->h_levels[idx + 1];
150 level->h_entry = level->h_entries =
151 ((struct ext2fs_htree_node *)bp->b_data)->h_entries;
158 ext2_htree_get_block(struct ext2fs_htree_entry *ep)
160 return (ep->h_blk & 0x00FFFFFF);
164 ext2_htree_set_block(struct ext2fs_htree_entry *ep, uint32_t blk)
170 ext2_htree_get_count(struct ext2fs_htree_entry *ep)
172 return (((struct ext2fs_htree_count *)(ep))->h_entries_num);
176 ext2_htree_set_count(struct ext2fs_htree_entry *ep, uint16_t cnt)
178 ((struct ext2fs_htree_count *)(ep))->h_entries_num = cnt;
182 ext2_htree_get_hash(struct ext2fs_htree_entry *ep)
188 ext2_htree_get_limit(struct ext2fs_htree_entry *ep)
190 return (((struct ext2fs_htree_count *)(ep))->h_entries_max);
194 ext2_htree_set_hash(struct ext2fs_htree_entry *ep, uint32_t hash)
200 ext2_htree_set_limit(struct ext2fs_htree_entry *ep, uint16_t limit)
202 ((struct ext2fs_htree_count *)(ep))->h_entries_max = limit;
206 ext2_htree_release(struct ext2fs_htree_lookup_info *info)
210 for (i = 0; i < info->h_levels_num; i++) {
211 struct buf *bp = info->h_levels[i].h_bp;
219 ext2_htree_root_limit(struct inode *ip, int len)
225 space = ip->i_e2fs->e2fs_bsize - EXT2_DIR_REC_LEN(1) -
226 EXT2_DIR_REC_LEN(2) - len;
228 if (EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_METADATA_CKSUM))
229 space -= sizeof(struct ext2fs_htree_tail);
231 return (space / sizeof(struct ext2fs_htree_entry));
235 ext2_htree_node_limit(struct inode *ip)
241 space = fs->e2fs_bsize - EXT2_DIR_REC_LEN(0);
243 if (EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_METADATA_CKSUM))
244 space -= sizeof(struct ext2fs_htree_tail);
246 return (space / sizeof(struct ext2fs_htree_entry));
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)
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;
265 if (name == NULL || info == NULL)
269 fs = ip->i_e2fs->e2fs;
272 if (ext2_blkatoff(vp, 0, NULL, &bp) != 0)
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)
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;
288 ext2_htree_hash(name, namelen, fs->e3fs_hash_seed,
289 hash_version, &hash_major, &hash_minor);
292 if ((levels = rootp->h_info.h_ind_levels) > 1)
295 entp = (struct ext2fs_htree_entry *)(((char *)&rootp->h_info) +
296 rootp->h_info.h_info_len);
298 if (ext2_htree_get_limit(entp) !=
299 ext2_htree_root_limit(ip, rootp->h_info.h_info_len))
303 cnt = ext2_htree_get_count(entp);
304 if (cnt == 0 || cnt > ext2_htree_get_limit(entp))
308 end = entp + cnt - 1;
309 while (start <= end) {
310 middle = start + (end - start) / 2;
311 if (ext2_htree_get_hash(middle) > hash_major)
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;
325 if (ext2_blkatoff(vp,
326 ext2_htree_get_block(found) * m_fs->e2fs_bsize,
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;
335 ext2_htree_release(info);
340 * Try to lookup a directory entry in HTree index
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)
349 struct ext2fs_htree_lookup_info info;
350 struct ext2fs_htree_entry *leaf_node;
351 struct m_ext2fs *m_fs;
356 uint8_t hash_version;
361 bsize = m_fs->e2fs_bsize;
364 /* TODO: print error msg because we don't lookup '.' and '..' */
366 memset(&info, 0, sizeof(info));
367 if (ext2_htree_find_leaf(ip, name, namelen, &dirhash,
368 &hash_version, &info))
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);
381 *prevoffp = blk * bsize;
382 *endusefulp = blk * bsize;
384 if (ss->slotstatus == NONE) {
386 ss->slotfreespace = 0;
389 if (ext2_search_dirblock(ip, bp->b_data, &found,
390 name, namelen, entryoffp, offp, prevoffp,
391 endusefulp, ss) != 0) {
393 ext2_htree_release(&info);
399 ext2_htree_release(&info);
404 search_next = ext2_htree_check_next(ip, dirhash, name, &info);
405 } while (search_next);
407 ext2_htree_release(&info);
412 ext2_htree_append_block(struct vnode *vp, char *data,
413 struct componentname *cnp, uint32_t blksize)
417 struct inode *dp = VTOI(vp);
418 uint64_t cursize, newsize;
421 cursize = roundup(dp->i_size, blksize);
422 newsize = cursize + blksize;
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;
430 auio.uio_rw = UIO_WRITE;
431 auio.uio_segflg = UIO_SYSSPACE;
432 error = VOP_WRITE(vp, &auio, IO_SYNC, cnp->cn_cred);
434 dp->i_size = newsize;
440 ext2_htree_writebuf(struct inode* ip, struct ext2fs_htree_lookup_info *info)
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);
456 ext2_htree_insert_entry_to_level(struct ext2fs_htree_lookup_level *level,
457 uint32_t hash, uint32_t blk)
459 struct ext2fs_htree_entry *target;
462 target = level->h_entry + 1;
463 entries_num = ext2_htree_get_count(level->h_entries);
465 memmove(target + 1, target, (char *)(level->h_entries + entries_num) -
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);
473 * Insert an index entry to the index node.
476 ext2_htree_insert_entry(struct ext2fs_htree_lookup_info *info,
477 uint32_t hash, uint32_t blk)
479 struct ext2fs_htree_lookup_level *level;
481 level = &info->h_levels[info->h_levels_num - 1];
482 ext2_htree_insert_entry_to_level(level, hash, blk);
486 * Compare two entry sort descriptors by name hash value.
487 * This is used together with qsort.
490 ext2_htree_cmp_sort_entry(const void *e1, const void *e2)
492 const struct ext2fs_htree_sort_entry *entry1, *entry2;
494 entry1 = (const struct ext2fs_htree_sort_entry *)e1;
495 entry2 = (const struct ext2fs_htree_sort_entry *)e2;
497 if (entry1->h_hash < entry2->h_hash)
499 if (entry1->h_hash > entry2->h_hash)
505 * Append an entry to the end of the directory block.
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)
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));
522 * Move half of entries from the old directory block to the new one.
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)
531 int size = 0, csum_size = 0;
534 uint16_t entry_len = 0;
536 struct ext2fs_direct_2 *ep, *last;
538 struct ext2fs_htree_sort_entry *sort_info;
541 ep = (struct ext2fs_direct_2 *)block1;
543 sort_info = (struct ext2fs_htree_sort_entry *)
544 ((char *)block2 + blksize);
546 if (EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_METADATA_CKSUM))
547 csum_size = sizeof(struct ext2fs_direct_tail);
550 * Calculate name hash value for the entry which is to be added.
552 ext2_htree_hash(entry->e2d_name, entry->e2d_namlen, hash_seed,
553 hash_version, &entry_hash, NULL);
556 * Fill in directory entry sort descriptors.
558 while ((char *)ep < block1 + blksize - csum_size) {
559 if (ep->e2d_ino && ep->e2d_namlen) {
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);
568 ep = (struct ext2fs_direct_2 *)
569 ((char *)ep + ep->e2d_reclen);
573 * Sort directory entry descriptors by name hash value.
575 qsort(sort_info, entry_cnt, sizeof(struct ext2fs_htree_sort_entry),
576 ext2_htree_cmp_sort_entry);
579 * Count the number of entries to move to directory block 2.
581 for (i = entry_cnt - 1; i >= 0; i--) {
582 if (sort_info[i].h_size + size > blksize / 2)
584 size += sort_info[i].h_size;
587 *split_hash = sort_info[i + 1].h_hash;
592 if (*split_hash == sort_info[i].h_hash)
596 * Move half of directory entries from block 1 to block 2.
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. */
610 /* Shrink directory entries in block 1. */
611 last = (struct ext2fs_direct_2 *)block1;
613 for (offset = 0; offset < blksize - csum_size; ) {
614 ep = (struct ext2fs_direct_2 *)(block1 + offset);
615 offset += ep->e2d_reclen;
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;
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);
630 /* Adjust length field of last entry of block 1. */
631 last->e2d_reclen = block1 + blksize - (char *)last - csum_size;
633 /* Add entry to block 1. */
634 ext2_append_entry(block1, blksize, last, entry, csum_size);
636 /* Adjust length field of last entry of block 2. */
637 ((struct ext2fs_direct_2 *)dest)->e2d_reclen =
638 block2 + blksize - dest - csum_size;
642 ext2_init_dirent_tail(EXT2_DIRENT_TAIL(block1, blksize));
643 ext2_init_dirent_tail(EXT2_DIRENT_TAIL(block2, blksize));
650 * Create an HTree index for a directory
653 ext2_htree_create_index(struct vnode *vp, struct componentname *cnp,
654 struct ext2fs_direct_2 *new_entry)
656 struct buf *bp = NULL;
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;
670 fs = dp->i_e2fs->e2fs;
672 blksize = m_fs->e2fs_bsize;
674 buf1 = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO);
675 buf2 = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO);
677 if ((error = ext2_blkatoff(vp, 0, NULL, &bp)) != 0)
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;
691 dp->i_flag |= IN_E3INDEX;
694 * Initialize index root.
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)));
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;
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);
718 * Write directory block 0.
720 ext2_dx_csum_set(dp, (struct ext2fs_direct_2 *)bp->b_data);
721 if (DOINGASYNC(vp)) {
727 dp->i_flag |= IN_CHANGE | IN_UPDATE;
732 * Write directory block 1.
734 ext2_dirent_csum_set(dp, (struct ext2fs_direct_2 *)buf1);
735 error = ext2_htree_append_block(vp, buf1, cnp, blksize);
740 * Write directory block 2.
742 ext2_dirent_csum_set(dp, (struct ext2fs_direct_2 *)buf2);
743 error = ext2_htree_append_block(vp, buf2, cnp, blksize);
758 * Add an entry to the directory using htree index.
761 ext2_htree_add_entry(struct vnode *dvp, struct ext2fs_direct_2 *entry,
762 struct componentname *cnp)
764 struct ext2fs_htree_entry *entries, *leaf_node;
765 struct ext2fs_htree_lookup_info info;
766 struct buf *bp = NULL;
768 struct m_ext2fs *m_fs;
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;
786 blksize = m_fs->e2fs_bsize;
788 if (ip->i_count != 0)
789 return ext2_add_entry(dvp, entry);
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);
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;
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,
817 error = ext2_blkatoff(dvp, cursize, NULL, &dst_bp);
820 dst_node = (struct ext2fs_htree_node *)dst_bp->b_data;
821 dst_entries = dst_node->h_entries;
823 if (info.h_levels_num == 2) {
824 uint16_t src_ent_num, dst_ent_num;
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");
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);
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));
846 if (info.h_levels[1].h_entry >= entries + src_ent_num) {
847 struct buf *tmp = info.h_levels[1].h_bp;
849 info.h_levels[1].h_bp = dst_bp;
852 info.h_levels[1].h_entry =
853 info.h_levels[1].h_entry -
854 (entries + src_ent_num) +
856 info.h_levels[1].h_entries = dst_entries;
858 ext2_htree_insert_entry_to_level(&info.h_levels[0],
861 /* Write new index node to disk */
863 (struct ext2fs_direct_2 *)dst_bp->b_data);
864 error = bwrite(dst_bp);
865 ip->i_flag |= IN_CHANGE | IN_UPDATE;
870 /* Create second level for htree index */
871 struct ext2fs_htree_root *idx_root;
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));
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;
882 ext2_htree_set_count(entries, 1);
883 ext2_htree_set_block(entries, blknum);
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;
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);
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;
908 /* Add index entry for the new directory block */
909 ext2_htree_insert_entry(&info, split_hash, blknum);
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);
917 /* Write the target directory block */
918 ext2_dirent_csum_set(ip, (struct ext2fs_direct_2 *)bp->b_data);
920 ip->i_flag |= IN_CHANGE | IN_UPDATE;
925 /* Write the index block */
926 error = ext2_htree_writebuf(ip, &info);
931 if (dst_bp != NULL && !write_dst_bp)
933 if (bp != NULL && !write_bp)
935 if (newdirblock != NULL)
936 free(newdirblock, M_TEMP);
937 if (newidxblock != NULL)
938 free(newidxblock, M_TEMP);
940 ext2_htree_release(&info);