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