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