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