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