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