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