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