1/*
2 * Copyright (c) 2013 Grzegorz Kostka (kostka.grzegorz@gmail.com)
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - 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 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29/** @addtogroup lwext4
30 * @{
31 */
32/**
33 * @file ext4_dir_idx.c
34 * @brief Directory indexing procedures.
35 */
36
37#include <ext4_config.h>
38#include <ext4_types.h>
39#include <ext4_misc.h>
40#include <ext4_errno.h>
41#include <ext4_debug.h>
42
43#include <ext4_trans.h>
44#include <ext4_dir_idx.h>
45#include <ext4_dir.h>
46#include <ext4_blockdev.h>
47#include <ext4_fs.h>
48#include <ext4_super.h>
49#include <ext4_inode.h>
50#include <ext4_crc32.h>
51#include <ext4_hash.h>
52
53#include <string.h>
54#include <stdlib.h>
55
56/**@brief Get hash version used in directory index.
57 * @param ri Pointer to root info structure of index
58 * @return Hash algorithm version
59 */
60static inline uint8_t
61ext4_dir_dx_rinfo_get_hash_version(struct ext4_dir_idx_rinfo *ri)
62{
63 return ri->hash_version;
64}
65
66/**@brief Set hash version, that will be used in directory index.
67 * @param ri Pointer to root info structure of index
68 * @param v Hash algorithm version
69 */
70static inline void
71ext4_dir_dx_rinfo_set_hash_version(struct ext4_dir_idx_rinfo *ri, uint8_t v)
72{
73 ri->hash_version = v;
74}
75
76/**@brief Get length of root_info structure in bytes.
77 * @param ri Pointer to root info structure of index
78 * @return Length of the structure
79 */
80static inline uint8_t
81ext4_dir_dx_rinfo_get_info_length(struct ext4_dir_idx_rinfo *ri)
82{
83 return ri->info_length;
84}
85
86/**@brief Set length of root_info structure in bytes.
87 * @param ri Pointer to root info structure of index
88 * @param len Length of the structure
89 */
90static inline void
91ext4_dir_dx_root_info_set_info_length(struct ext4_dir_idx_rinfo *ri,
92 uint8_t len)
93{
94 ri->info_length = len;
95}
96
97/**@brief Get number of indirect levels of HTree.
98 * @param ri Pointer to root info structure of index
99 * @return Height of HTree (actually only 0 or 1)
100 */
101static inline uint8_t
102ext4_dir_dx_rinfo_get_indirect_levels(struct ext4_dir_idx_rinfo *ri)
103{
104 return ri->indirect_levels;
105}
106
107/**@brief Set number of indirect levels of HTree.
108 * @param ri Pointer to root info structure of index
109 * @param l Height of HTree (actually only 0 or 1)
110 */
111static inline void
112ext4_dir_dx_rinfo_set_indirect_levels(struct ext4_dir_idx_rinfo *ri, uint8_t l)
113{
114 ri->indirect_levels = l;
115}
116
117/**@brief Get maximum number of index node entries.
118 * @param climit Pointer to counlimit structure
119 * @return Maximum of entries in node
120 */
121static inline uint16_t
122ext4_dir_dx_climit_get_limit(struct ext4_dir_idx_climit *climit)
123{
124 return to_le16(climit->limit);
125}
126
127/**@brief Set maximum number of index node entries.
128 * @param climit Pointer to counlimit structure
129 * @param limit Maximum of entries in node
130 */
131static inline void
132ext4_dir_dx_climit_set_limit(struct ext4_dir_idx_climit *climit, uint16_t limit)
133{
134 climit->limit = to_le16(limit);
135}
136
137/**@brief Get current number of index node entries.
138 * @param climit Pointer to counlimit structure
139 * @return Number of entries in node
140 */
141static inline uint16_t
142ext4_dir_dx_climit_get_count(struct ext4_dir_idx_climit *climit)
143{
144 return to_le16(climit->count);
145}
146
147/**@brief Set current number of index node entries.
148 * @param climit Pointer to counlimit structure
149 * @param count Number of entries in node
150 */
151static inline void
152ext4_dir_dx_climit_set_count(struct ext4_dir_idx_climit *climit, uint16_t count)
153{
154 climit->count = to_le16(count);
155}
156
157/**@brief Get hash value of index entry.
158 * @param entry Pointer to index entry
159 * @return Hash value
160 */
161static inline uint32_t
162ext4_dir_dx_entry_get_hash(struct ext4_dir_idx_entry *entry)
163{
164 return to_le32(entry->hash);
165}
166
167/**@brief Set hash value of index entry.
168 * @param entry Pointer to index entry
169 * @param hash Hash value
170 */
171static inline void
172ext4_dir_dx_entry_set_hash(struct ext4_dir_idx_entry *entry, uint32_t hash)
173{
174 entry->hash = to_le32(hash);
175}
176
177/**@brief Get block address where child node is located.
178 * @param entry Pointer to index entry
179 * @return Block address of child node
180 */
181static inline uint32_t
182ext4_dir_dx_entry_get_block(struct ext4_dir_idx_entry *entry)
183{
184 return to_le32(entry->block);
185}
186
187/**@brief Set block address where child node is located.
188 * @param entry Pointer to index entry
189 * @param block Block address of child node
190 */
191static inline void
192ext4_dir_dx_entry_set_block(struct ext4_dir_idx_entry *entry, uint32_t block)
193{
194 entry->block = to_le32(block);
195}
196
197/**@brief Sort entry item.*/
198struct ext4_dx_sort_entry {
199 uint32_t hash;
200 uint32_t rec_len;
201 void *dentry;
202};
203
204static int ext4_dir_dx_hash_string(struct ext4_hash_info *hinfo, int len,
205 const char *name)
206{
207 return ext2_htree_hash(name, len, hash_seed: hinfo->seed, hash_version: hinfo->hash_version,
208 hash_major: &hinfo->hash, hash_minor: &hinfo->minor_hash);
209}
210
211#if CONFIG_META_CSUM_ENABLE
212static uint32_t ext4_dir_dx_checksum(struct ext4_inode_ref *inode_ref, void *de,
213 int count_offset, int count,
214 struct ext4_dir_idx_tail *t)
215{
216 uint32_t orig_cum, csum = 0;
217 struct ext4_sblock *sb = &inode_ref->fs->sb;
218 int sz;
219
220 /* Compute the checksum only if the filesystem supports it */
221 if (ext4_sb_feature_ro_com(s: sb, EXT4_FRO_COM_METADATA_CSUM)) {
222 uint32_t ino_index = to_le32(inode_ref->index);
223 uint32_t ino_gen;
224 ino_gen = to_le32(ext4_inode_get_generation(inode_ref->inode));
225
226 sz = count_offset + (count * sizeof(struct ext4_dir_idx_tail));
227 orig_cum = t->checksum;
228 t->checksum = 0;
229 /* First calculate crc32 checksum against fs uuid */
230 csum = ext4_crc32c(EXT4_CRC32_INIT, buf: sb->uuid, size: sizeof(sb->uuid));
231 /* Then calculate crc32 checksum against inode number
232 * and inode generation */
233 csum = ext4_crc32c(crc: csum, buf: &ino_index, size: sizeof(ino_index));
234 csum = ext4_crc32c(crc: csum, buf: &ino_gen, size: sizeof(ino_gen));
235 /* After that calculate crc32 checksum against all the dx_entry */
236 csum = ext4_crc32c(crc: csum, buf: de, size: sz);
237 /* Finally calculate crc32 checksum for dx_tail */
238 csum = ext4_crc32c(crc: csum, buf: t, size: sizeof(struct ext4_dir_idx_tail));
239 t->checksum = orig_cum;
240 }
241 return csum;
242}
243
244static struct ext4_dir_idx_climit *
245ext4_dir_dx_get_climit(struct ext4_inode_ref *inode_ref,
246 struct ext4_dir_en *dirent, int *offset)
247{
248 struct ext4_dir_en *dp;
249 struct ext4_dir_idx_root *root;
250 struct ext4_sblock *sb = &inode_ref->fs->sb;
251 uint32_t block_size = ext4_sb_get_block_size(s: sb);
252 uint16_t entry_len = ext4_dir_en_get_entry_len(de: dirent);
253 int count_offset;
254
255
256 if (entry_len == 12) {
257 root = (struct ext4_dir_idx_root *)dirent;
258 dp = (struct ext4_dir_en *)&root->dots[1];
259 if (ext4_dir_en_get_entry_len(de: dp) != (block_size - 12))
260 return NULL;
261 if (root->info.reserved_zero)
262 return NULL;
263 if (root->info.info_length != sizeof(struct ext4_dir_idx_rinfo))
264 return NULL;
265 count_offset = 32;
266 } else if (entry_len == block_size) {
267 count_offset = 8;
268 } else {
269 return NULL;
270 }
271
272 if (offset)
273 *offset = count_offset;
274 return (struct ext4_dir_idx_climit *)(((char *)dirent) + count_offset);
275}
276
277/*
278 * BIG FAT NOTES:
279 * Currently we do not verify the checksum of HTree node.
280 */
281static bool ext4_dir_dx_csum_verify(struct ext4_inode_ref *inode_ref,
282 struct ext4_dir_en *de)
283{
284 struct ext4_sblock *sb = &inode_ref->fs->sb;
285 uint32_t block_size = ext4_sb_get_block_size(s: sb);
286 int coff, limit, cnt;
287
288 if (ext4_sb_feature_ro_com(s: sb, EXT4_FRO_COM_METADATA_CSUM)) {
289 struct ext4_dir_idx_climit *climit;
290 climit = ext4_dir_dx_get_climit(inode_ref, dirent: de, offset: &coff);
291 if (!climit) {
292 /* Directory seems corrupted. */
293 return true;
294 }
295 struct ext4_dir_idx_tail *t;
296 limit = ext4_dir_dx_climit_get_limit(climit);
297 cnt = ext4_dir_dx_climit_get_count(climit);
298 if (coff + (limit * sizeof(struct ext4_dir_idx_entry)) >
299 (block_size - sizeof(struct ext4_dir_idx_tail))) {
300 /* There is no space to hold the checksum */
301 return true;
302 }
303 t = (void *)(((struct ext4_dir_idx_entry *)climit) + limit);
304
305 uint32_t c;
306 c = to_le32(ext4_dir_dx_checksum(inode_ref, de, coff, cnt, t));
307 if (t->checksum != c)
308 return false;
309 }
310 return true;
311}
312
313
314static void ext4_dir_set_dx_csum(struct ext4_inode_ref *inode_ref,
315 struct ext4_dir_en *dirent)
316{
317 int coff, limit, count;
318 struct ext4_sblock *sb = &inode_ref->fs->sb;
319 uint32_t block_size = ext4_sb_get_block_size(s: sb);
320
321 if (ext4_sb_feature_ro_com(s: sb, EXT4_FRO_COM_METADATA_CSUM)) {
322 struct ext4_dir_idx_climit *climit;
323 climit = ext4_dir_dx_get_climit(inode_ref, dirent, offset: &coff);
324 if (!climit) {
325 /* Directory seems corrupted. */
326 return;
327 }
328 struct ext4_dir_idx_tail *t;
329 limit = ext4_dir_dx_climit_get_limit(climit);
330 count = ext4_dir_dx_climit_get_count(climit);
331 if (coff + (limit * sizeof(struct ext4_dir_idx_entry)) >
332 (block_size - sizeof(struct ext4_dir_idx_tail))) {
333 /* There is no space to hold the checksum */
334 return;
335 }
336
337 t = (void *)(((struct ext4_dir_idx_entry *)climit) + limit);
338 t->checksum = to_le32(ext4_dir_dx_checksum(inode_ref, dirent,
339 coff, count, t));
340 }
341}
342#else
343#define ext4_dir_dx_csum_verify(...) true
344#define ext4_dir_set_dx_csum(...)
345#endif
346
347/****************************************************************************/
348
349int ext4_dir_dx_init(struct ext4_inode_ref *dir, struct ext4_inode_ref *parent)
350{
351 /* Load block 0, where will be index root located */
352 ext4_fsblk_t fblock;
353 uint32_t iblock = 0;
354 bool need_append =
355 (ext4_inode_get_size(sb: &dir->fs->sb, inode: dir->inode)
356 < EXT4_DIR_DX_INIT_BCNT)
357 ? true : false;
358 struct ext4_sblock *sb = &dir->fs->sb;
359 uint32_t block_size = ext4_sb_get_block_size(s: &dir->fs->sb);
360 struct ext4_block block;
361
362 int rc;
363
364 if (!need_append)
365 rc = ext4_fs_init_inode_dblk_idx(inode_ref: dir, iblock, fblock: &fblock);
366 else
367 rc = ext4_fs_append_inode_dblk(inode_ref: dir, fblock: &fblock, iblock: &iblock);
368
369 if (rc != EOK)
370 return rc;
371
372 rc = ext4_trans_block_get_noread(bdev: dir->fs->bdev, b: &block, lba: fblock);
373 if (rc != EOK)
374 return rc;
375
376 /* Initialize pointers to data structures */
377 struct ext4_dir_idx_root *root = (void *)block.data;
378 struct ext4_dir_idx_rinfo *info = &(root->info);
379
380 memset(dest: root, c: 0, size: sizeof(struct ext4_dir_idx_root));
381 struct ext4_dir_en *de;
382
383 /* Initialize dot entries */
384 de = (struct ext4_dir_en *)root->dots;
385 ext4_dir_write_entry(sb, en: de, entry_len: 12, child: dir, name: ".", name_len: strlen(s: "."));
386
387 de = (struct ext4_dir_en *)(root->dots + 1);
388 uint16_t elen = block_size - 12;
389 ext4_dir_write_entry(sb, en: de, entry_len: elen, child: parent, name: "..", name_len: strlen(s: ".."));
390
391 /* Initialize root info structure */
392 uint8_t hash_version = ext4_get8(&dir->fs->sb, default_hash_version);
393
394 ext4_dir_dx_rinfo_set_hash_version(ri: info, v: hash_version);
395 ext4_dir_dx_rinfo_set_indirect_levels(ri: info, l: 0);
396 ext4_dir_dx_root_info_set_info_length(ri: info, len: 8);
397
398 /* Set limit and current number of entries */
399 struct ext4_dir_idx_climit *climit;
400 climit = (struct ext4_dir_idx_climit *)&root->en;
401
402 ext4_dir_dx_climit_set_count(climit, count: 1);
403
404 uint32_t entry_space;
405 entry_space = block_size - 2 * sizeof(struct ext4_dir_idx_dot_en) -
406 sizeof(struct ext4_dir_idx_rinfo);
407
408 if (ext4_sb_feature_ro_com(s: sb, EXT4_FRO_COM_METADATA_CSUM))
409 entry_space -= sizeof(struct ext4_dir_idx_tail);
410
411 uint16_t root_limit = entry_space / sizeof(struct ext4_dir_idx_entry);
412 ext4_dir_dx_climit_set_limit(climit, limit: root_limit);
413
414 /* Append new block, where will be new entries inserted in the future */
415 iblock++;
416 if (!need_append)
417 rc = ext4_fs_init_inode_dblk_idx(inode_ref: dir, iblock, fblock: &fblock);
418 else
419 rc = ext4_fs_append_inode_dblk(inode_ref: dir, fblock: &fblock, iblock: &iblock);
420
421 if (rc != EOK) {
422 ext4_block_set(bdev: dir->fs->bdev, b: &block);
423 return rc;
424 }
425
426 struct ext4_block new_block;
427 rc = ext4_trans_block_get_noread(bdev: dir->fs->bdev, b: &new_block, lba: fblock);
428 if (rc != EOK) {
429 ext4_block_set(bdev: dir->fs->bdev, b: &block);
430 return rc;
431 }
432
433 /* Fill the whole block with empty entry */
434 struct ext4_dir_en *be = (void *)new_block.data;
435
436 if (ext4_sb_feature_ro_com(s: sb, EXT4_FRO_COM_METADATA_CSUM)) {
437 uint16_t len = block_size - sizeof(struct ext4_dir_entry_tail);
438 ext4_dir_en_set_entry_len(de: be, l: len);
439 ext4_dir_en_set_name_len(sb, de: be, len: 0);
440 ext4_dir_en_set_inode_type(sb, de: be, t: EXT4_DE_UNKNOWN);
441 ext4_dir_init_entry_tail(EXT4_DIRENT_TAIL(be, block_size));
442 ext4_dir_set_csum(inode_ref: dir, dirent: be);
443 } else {
444 ext4_dir_en_set_entry_len(de: be, l: block_size);
445 }
446
447 ext4_dir_en_set_inode(de: be, inode: 0);
448
449 ext4_trans_set_block_dirty(buf: new_block.buf);
450 rc = ext4_block_set(bdev: dir->fs->bdev, b: &new_block);
451 if (rc != EOK) {
452 ext4_block_set(bdev: dir->fs->bdev, b: &block);
453 return rc;
454 }
455
456 /* Connect new block to the only entry in index */
457 struct ext4_dir_idx_entry *entry = root->en;
458 ext4_dir_dx_entry_set_block(entry, block: iblock);
459
460 ext4_dir_set_dx_csum(inode_ref: dir, dirent: (struct ext4_dir_en *)block.data);
461 ext4_trans_set_block_dirty(buf: block.buf);
462
463 return ext4_block_set(bdev: dir->fs->bdev, b: &block);
464}
465
466/**@brief Initialize hash info structure necessary for index operations.
467 * @param hinfo Pointer to hinfo to be initialized
468 * @param root_block Root block (number 0) of index
469 * @param sb Pointer to superblock
470 * @param name_len Length of name to be computed hash value from
471 * @param name Name to be computed hash value from
472 * @return Standard error code
473 */
474static int ext4_dir_hinfo_init(struct ext4_hash_info *hinfo,
475 struct ext4_block *root_block,
476 struct ext4_sblock *sb, size_t name_len,
477 const char *name)
478{
479 struct ext4_dir_idx_root *root;
480
481 root = (struct ext4_dir_idx_root *)root_block->data;
482 if ((root->info.hash_version != EXT2_HTREE_LEGACY) &&
483 (root->info.hash_version != EXT2_HTREE_HALF_MD4) &&
484 (root->info.hash_version != EXT2_HTREE_TEA))
485 return EXT4_ERR_BAD_DX_DIR;
486
487 /* Check unused flags */
488 if (root->info.unused_flags != 0)
489 return EXT4_ERR_BAD_DX_DIR;
490
491 /* Check indirect levels */
492 if (root->info.indirect_levels > 1)
493 return EXT4_ERR_BAD_DX_DIR;
494
495 /* Check if node limit is correct */
496 uint32_t block_size = ext4_sb_get_block_size(s: sb);
497 uint32_t entry_space = block_size;
498 entry_space -= 2 * sizeof(struct ext4_dir_idx_dot_en);
499 entry_space -= sizeof(struct ext4_dir_idx_rinfo);
500 if (ext4_sb_feature_ro_com(s: sb, EXT4_FRO_COM_METADATA_CSUM))
501 entry_space -= sizeof(struct ext4_dir_idx_tail);
502 entry_space = entry_space / sizeof(struct ext4_dir_idx_entry);
503
504 struct ext4_dir_idx_climit *climit = (void *)&root->en;
505 uint16_t limit = ext4_dir_dx_climit_get_limit(climit);
506 if (limit != entry_space)
507 return EXT4_ERR_BAD_DX_DIR;
508
509 /* Check hash version and modify if necessary */
510 hinfo->hash_version = ext4_dir_dx_rinfo_get_hash_version(ri: &root->info);
511 if ((hinfo->hash_version <= EXT2_HTREE_TEA) &&
512 (ext4_sb_check_flag(s: sb, EXT4_SUPERBLOCK_FLAGS_UNSIGNED_HASH))) {
513 /* Use unsigned hash */
514 hinfo->hash_version += 3;
515 }
516
517 /* Load hash seed from superblock */
518 hinfo->seed = ext4_get8(sb, hash_seed);
519
520 /* Compute hash value of name */
521 if (name)
522 return ext4_dir_dx_hash_string(hinfo, len: name_len, name);
523
524 return EOK;
525}
526
527/**@brief Walk through index tree and load leaf with corresponding hash value.
528 * @param hinfo Initialized hash info structure
529 * @param inode_ref Current i-node
530 * @param root_block Root block (iblock 0), where is root node located
531 * @param dx_block Pointer to leaf node in dx_blocks array
532 * @param dx_blocks Array with the whole path from root to leaf
533 * @return Standard error code
534 */
535static int ext4_dir_dx_get_leaf(struct ext4_hash_info *hinfo,
536 struct ext4_inode_ref *inode_ref,
537 struct ext4_block *root_block,
538 struct ext4_dir_idx_block **dx_block,
539 struct ext4_dir_idx_block *dx_blocks)
540{
541 struct ext4_dir_idx_root *root;
542 struct ext4_dir_idx_entry *entries;
543 struct ext4_dir_idx_entry *p;
544 struct ext4_dir_idx_entry *q;
545 struct ext4_dir_idx_entry *m;
546 struct ext4_dir_idx_entry *at;
547 ext4_fsblk_t fblk;
548 uint32_t block_size;
549 uint16_t limit;
550 uint16_t entry_space;
551 uint8_t ind_level;
552 int r;
553
554 struct ext4_dir_idx_block *tmp_dx_blk = dx_blocks;
555 struct ext4_block *tmp_blk = root_block;
556 struct ext4_sblock *sb = &inode_ref->fs->sb;
557
558 block_size = ext4_sb_get_block_size(s: sb);
559 root = (struct ext4_dir_idx_root *)root_block->data;
560 entries = (struct ext4_dir_idx_entry *)&root->en;
561 limit = ext4_dir_dx_climit_get_limit(climit: (void *)entries);
562 ind_level = ext4_dir_dx_rinfo_get_indirect_levels(ri: &root->info);
563
564 /* Walk through the index tree */
565 while (true) {
566 uint16_t cnt = ext4_dir_dx_climit_get_count(climit: (void *)entries);
567 if ((cnt == 0) || (cnt > limit))
568 return EXT4_ERR_BAD_DX_DIR;
569
570 /* Do binary search in every node */
571 p = entries + 1;
572 q = entries + cnt - 1;
573
574 while (p <= q) {
575 m = p + (q - p) / 2;
576 if (ext4_dir_dx_entry_get_hash(entry: m) > hinfo->hash)
577 q = m - 1;
578 else
579 p = m + 1;
580 }
581
582 at = p - 1;
583
584 /* Write results */
585 memcpy(dest: &tmp_dx_blk->b, src: tmp_blk, size: sizeof(struct ext4_block));
586 tmp_dx_blk->entries = entries;
587 tmp_dx_blk->position = at;
588
589 /* Is algorithm in the leaf? */
590 if (ind_level == 0) {
591 *dx_block = tmp_dx_blk;
592 return EOK;
593 }
594
595 /* Goto child node */
596 uint32_t n_blk = ext4_dir_dx_entry_get_block(entry: at);
597
598 ind_level--;
599
600 r = ext4_fs_get_inode_dblk_idx(inode_ref, iblock: n_blk, fblock: &fblk, support_unwritten: false);
601 if (r != EOK)
602 return r;
603
604 r = ext4_trans_block_get(bdev: inode_ref->fs->bdev, b: tmp_blk, lba: fblk);
605 if (r != EOK)
606 return r;
607
608 entries = ((struct ext4_dir_idx_node *)tmp_blk->data)->entries;
609 limit = ext4_dir_dx_climit_get_limit(climit: (void *)entries);
610
611 entry_space = block_size - sizeof(struct ext4_fake_dir_entry);
612 if (ext4_sb_feature_ro_com(s: sb, EXT4_FRO_COM_METADATA_CSUM))
613 entry_space -= sizeof(struct ext4_dir_idx_tail);
614
615 entry_space = entry_space / sizeof(struct ext4_dir_idx_entry);
616
617 if (limit != entry_space) {
618 ext4_block_set(bdev: inode_ref->fs->bdev, b: tmp_blk);
619 return EXT4_ERR_BAD_DX_DIR;
620 }
621
622 if (!ext4_dir_dx_csum_verify(inode_ref, de: (void *)tmp_blk->data)) {
623 ext4_dbg(DEBUG_DIR_IDX,
624 DBG_WARN "HTree checksum failed."
625 "Inode: %" PRIu32", "
626 "Block: %" PRIu32"\n",
627 inode_ref->index,
628 n_blk);
629 }
630
631 ++tmp_dx_blk;
632 }
633
634 /* Unreachable */
635 return EOK;
636}
637
638/**@brief Check if the the next block would be checked during entry search.
639 * @param inode_ref Directory i-node
640 * @param hash Hash value to check
641 * @param dx_block Current block
642 * @param dx_blocks Array with path from root to leaf node
643 * @return Standard Error code
644 */
645static int ext4_dir_dx_next_block(struct ext4_inode_ref *inode_ref,
646 uint32_t hash,
647 struct ext4_dir_idx_block *dx_block,
648 struct ext4_dir_idx_block *dx_blocks)
649{
650 int r;
651 uint32_t num_handles = 0;
652 ext4_fsblk_t blk_adr;
653 struct ext4_dir_idx_block *p = dx_block;
654
655 /* Try to find data block with next bunch of entries */
656 while (true) {
657 uint16_t cnt = ext4_dir_dx_climit_get_count(climit: (void *)p->entries);
658
659 p->position++;
660 if (p->position < p->entries + cnt)
661 break;
662
663 if (p == dx_blocks)
664 return EOK;
665
666 num_handles++;
667 p--;
668 }
669
670 /* Check hash collision (if not occurred - no next block cannot be
671 * used)*/
672 uint32_t current_hash = ext4_dir_dx_entry_get_hash(entry: p->position);
673 if ((hash & 1) == 0) {
674 if ((current_hash & ~1) != hash)
675 return 0;
676 }
677
678 /* Fill new path */
679 while (num_handles--) {
680 uint32_t blk = ext4_dir_dx_entry_get_block(entry: p->position);
681 r = ext4_fs_get_inode_dblk_idx(inode_ref, iblock: blk, fblock: &blk_adr, support_unwritten: false);
682 if (r != EOK)
683 return r;
684
685 struct ext4_block b;
686 r = ext4_trans_block_get(bdev: inode_ref->fs->bdev, b: &b, lba: blk_adr);
687 if (r != EOK)
688 return r;
689
690 if (!ext4_dir_dx_csum_verify(inode_ref, de: (void *)b.data)) {
691 ext4_dbg(DEBUG_DIR_IDX,
692 DBG_WARN "HTree checksum failed."
693 "Inode: %" PRIu32", "
694 "Block: %" PRIu32"\n",
695 inode_ref->index,
696 blk);
697 }
698
699 p++;
700
701 /* Don't forget to put old block (prevent memory leak) */
702 r = ext4_block_set(bdev: inode_ref->fs->bdev, b: &p->b);
703 if (r != EOK)
704 return r;
705
706 memcpy(dest: &p->b, src: &b, size: sizeof(b));
707 p->entries = ((struct ext4_dir_idx_node *)b.data)->entries;
708 p->position = p->entries;
709 }
710
711 return ENOENT;
712}
713
714int ext4_dir_dx_find_entry(struct ext4_dir_search_result *result,
715 struct ext4_inode_ref *inode_ref, size_t name_len,
716 const char *name)
717{
718 /* Load direct block 0 (index root) */
719 ext4_fsblk_t root_block_addr;
720 int rc2;
721 int rc;
722 rc = ext4_fs_get_inode_dblk_idx(inode_ref, iblock: 0, fblock: &root_block_addr, support_unwritten: false);
723 if (rc != EOK)
724 return rc;
725
726 struct ext4_fs *fs = inode_ref->fs;
727
728 struct ext4_block root_block;
729 rc = ext4_trans_block_get(bdev: fs->bdev, b: &root_block, lba: root_block_addr);
730 if (rc != EOK)
731 return rc;
732
733 if (!ext4_dir_dx_csum_verify(inode_ref, de: (void *)root_block.data)) {
734 ext4_dbg(DEBUG_DIR_IDX,
735 DBG_WARN "HTree root checksum failed."
736 "Inode: %" PRIu32", "
737 "Block: %" PRIu32"\n",
738 inode_ref->index,
739 (uint32_t)0);
740 }
741
742 /* Initialize hash info (compute hash value) */
743 struct ext4_hash_info hinfo;
744 rc = ext4_dir_hinfo_init(hinfo: &hinfo, root_block: &root_block, sb: &fs->sb, name_len, name);
745 if (rc != EOK) {
746 ext4_block_set(bdev: fs->bdev, b: &root_block);
747 return EXT4_ERR_BAD_DX_DIR;
748 }
749
750 /*
751 * Hardcoded number 2 means maximum height of index tree,
752 * specified in the Linux driver.
753 */
754 struct ext4_dir_idx_block dx_blocks[2];
755 struct ext4_dir_idx_block *dx_block;
756 struct ext4_dir_idx_block *tmp;
757
758 rc = ext4_dir_dx_get_leaf(hinfo: &hinfo, inode_ref, root_block: &root_block, dx_block: &dx_block,
759 dx_blocks);
760 if (rc != EOK) {
761 ext4_block_set(bdev: fs->bdev, b: &root_block);
762 return EXT4_ERR_BAD_DX_DIR;
763 }
764
765 do {
766 /* Load leaf block */
767 uint32_t leaf_blk_idx;
768 ext4_fsblk_t leaf_block_addr;
769 struct ext4_block b;
770
771 leaf_blk_idx = ext4_dir_dx_entry_get_block(entry: dx_block->position);
772 rc = ext4_fs_get_inode_dblk_idx(inode_ref, iblock: leaf_blk_idx,
773 fblock: &leaf_block_addr, support_unwritten: false);
774 if (rc != EOK)
775 goto cleanup;
776
777 rc = ext4_trans_block_get(bdev: fs->bdev, b: &b, lba: leaf_block_addr);
778 if (rc != EOK)
779 goto cleanup;
780
781 if (!ext4_dir_csum_verify(inode_ref, dirent: (void *)b.data)) {
782 ext4_dbg(DEBUG_DIR_IDX,
783 DBG_WARN "HTree leaf block checksum failed."
784 "Inode: %" PRIu32", "
785 "Block: %" PRIu32"\n",
786 inode_ref->index,
787 leaf_blk_idx);
788 }
789
790 /* Linear search inside block */
791 struct ext4_dir_en *de;
792 rc = ext4_dir_find_in_block(block: &b, sb: &fs->sb, name_len, name, res_entry: &de);
793
794 /* Found => return it */
795 if (rc == EOK) {
796 result->block = b;
797 result->dentry = de;
798 goto cleanup;
799 }
800
801 /* Not found, leave untouched */
802 rc2 = ext4_block_set(bdev: fs->bdev, b: &b);
803 if (rc2 != EOK)
804 goto cleanup;
805
806 if (rc != ENOENT)
807 goto cleanup;
808
809 /* check if the next block could be checked */
810 rc = ext4_dir_dx_next_block(inode_ref, hash: hinfo.hash, dx_block,
811 dx_blocks: &dx_blocks[0]);
812 if (rc < 0)
813 goto cleanup;
814 } while (rc == ENOENT);
815
816 /* Entry not found */
817 rc = ENOENT;
818
819cleanup:
820 /* The whole path must be released (preventing memory leak) */
821 tmp = dx_blocks;
822
823 while (tmp <= dx_block) {
824 rc2 = ext4_block_set(bdev: fs->bdev, b: &tmp->b);
825 if (rc == EOK && rc2 != EOK)
826 rc = rc2;
827 ++tmp;
828 }
829
830 return rc;
831}
832
833/**@brief Compare function used to pass in quicksort implementation.
834 * It can compare two entries by hash value.
835 * @param arg1 First entry
836 * @param arg2 Second entry
837 *
838 * @return Classic compare result
839 * (0: equal, -1: arg1 < arg2, 1: arg1 > arg2)
840 */
841static int ext4_dir_dx_entry_comparator(const void *arg1, const void *arg2)
842{
843 struct ext4_dx_sort_entry *entry1 = (void *)arg1;
844 struct ext4_dx_sort_entry *entry2 = (void *)arg2;
845
846 if (entry1->hash == entry2->hash)
847 return 0;
848
849 if (entry1->hash < entry2->hash)
850 return -1;
851 else
852 return 1;
853}
854
855/**@brief Insert new index entry to block.
856 * Note that space for new entry must be checked by caller.
857 * @param inode_ref Directory i-node
858 * @param index_block Block where to insert new entry
859 * @param hash Hash value covered by child node
860 * @param iblock Logical number of child block
861 *
862 */
863static void
864ext4_dir_dx_insert_entry(struct ext4_inode_ref *inode_ref __unused,
865 struct ext4_dir_idx_block *index_block,
866 uint32_t hash, uint32_t iblock)
867{
868 struct ext4_dir_idx_entry *old_index_entry = index_block->position;
869 struct ext4_dir_idx_entry *new_index_entry = old_index_entry + 1;
870 struct ext4_dir_idx_climit *climit = (void *)index_block->entries;
871 struct ext4_dir_idx_entry *start_index = index_block->entries;
872 uint32_t count = ext4_dir_dx_climit_get_count(climit);
873
874 size_t bytes;
875 bytes = (uint8_t *)(start_index + count) - (uint8_t *)(new_index_entry);
876
877 memmove(dest: new_index_entry + 1, src: new_index_entry, size: bytes);
878
879 ext4_dir_dx_entry_set_block(entry: new_index_entry, block: iblock);
880 ext4_dir_dx_entry_set_hash(entry: new_index_entry, hash);
881 ext4_dir_dx_climit_set_count(climit, count: count + 1);
882 ext4_dir_set_dx_csum(inode_ref, dirent: (void *)index_block->b.data);
883 ext4_trans_set_block_dirty(buf: index_block->b.buf);
884}
885
886/**@brief Split directory entries to two parts preventing node overflow.
887 * @param inode_ref Directory i-node
888 * @param hinfo Hash info
889 * @param old_data_block Block with data to be split
890 * @param index_block Block where index entries are located
891 * @param new_data_block Output value for newly allocated data block
892 */
893static int ext4_dir_dx_split_data(struct ext4_inode_ref *inode_ref,
894 struct ext4_hash_info *hinfo,
895 struct ext4_block *old_data_block,
896 struct ext4_dir_idx_block *index_block,
897 struct ext4_block *new_data_block)
898{
899 int rc = EOK;
900 struct ext4_sblock *sb = &inode_ref->fs->sb;
901 uint32_t block_size = ext4_sb_get_block_size(s: &inode_ref->fs->sb);
902
903 /* Allocate buffer for directory entries */
904 uint8_t *entry_buffer = ext4_malloc(size: block_size);
905 if (entry_buffer == NULL)
906 return ENOMEM;
907
908 /* dot entry has the smallest size available */
909 uint32_t max_ecnt = block_size / sizeof(struct ext4_dir_idx_dot_en);
910
911 /* Allocate sort entry */
912 struct ext4_dx_sort_entry *sort;
913
914 sort = ext4_malloc(size: max_ecnt * sizeof(struct ext4_dx_sort_entry));
915 if (sort == NULL) {
916 ext4_free(pointer: entry_buffer);
917 return ENOMEM;
918 }
919
920 uint32_t idx = 0;
921 uint32_t real_size = 0;
922
923 /* Initialize hinfo */
924 struct ext4_hash_info hinfo_tmp;
925 memcpy(dest: &hinfo_tmp, src: hinfo, size: sizeof(struct ext4_hash_info));
926
927 /* Load all valid entries to the buffer */
928 struct ext4_dir_en *de = (void *)old_data_block->data;
929 uint8_t *entry_buffer_ptr = entry_buffer;
930 while ((void *)de < (void *)(old_data_block->data + block_size)) {
931 /* Read only valid entries */
932 if (ext4_dir_en_get_inode(de) && de->name_len) {
933 uint16_t len = ext4_dir_en_get_name_len(sb, de);
934 rc = ext4_dir_dx_hash_string(hinfo: &hinfo_tmp, len,
935 name: (char *)de->name);
936 if (rc != EOK) {
937 ext4_free(pointer: sort);
938 ext4_free(pointer: entry_buffer);
939 return rc;
940 }
941
942 uint32_t rec_len = 8 + len;
943 if ((rec_len % 4) != 0)
944 rec_len += 4 - (rec_len % 4);
945
946 memcpy(dest: entry_buffer_ptr, src: de, size: rec_len);
947
948 sort[idx].dentry = entry_buffer_ptr;
949 sort[idx].rec_len = rec_len;
950 sort[idx].hash = hinfo_tmp.hash;
951
952 entry_buffer_ptr += rec_len;
953 real_size += rec_len;
954 idx++;
955 }
956
957 size_t elen = ext4_dir_en_get_entry_len(de);
958 de = (void *)((uint8_t *)de + elen);
959 }
960
961 qsort(base: sort, count: idx, size: sizeof(struct ext4_dx_sort_entry),
962 compare: ext4_dir_dx_entry_comparator);
963
964 /* Allocate new block for store the second part of entries */
965 ext4_fsblk_t new_fblock;
966 uint32_t new_iblock;
967 rc = ext4_fs_append_inode_dblk(inode_ref, fblock: &new_fblock, iblock: &new_iblock);
968 if (rc != EOK) {
969 ext4_free(pointer: sort);
970 ext4_free(pointer: entry_buffer);
971 return rc;
972 }
973
974 /* Load new block */
975 struct ext4_block new_data_block_tmp;
976 rc = ext4_trans_block_get_noread(bdev: inode_ref->fs->bdev, b: &new_data_block_tmp,
977 lba: new_fblock);
978 if (rc != EOK) {
979 ext4_free(pointer: sort);
980 ext4_free(pointer: entry_buffer);
981 return rc;
982 }
983
984 /*
985 * Distribute entries to two blocks (by size)
986 * - compute the half
987 */
988 uint32_t new_hash = 0;
989 uint32_t current_size = 0;
990 uint32_t mid = 0;
991 uint32_t i;
992 for (i = 0; i < idx; ++i) {
993 if ((current_size + sort[i].rec_len) > (block_size / 2)) {
994 new_hash = sort[i].hash;
995 mid = i;
996 break;
997 }
998
999 current_size += sort[i].rec_len;
1000 }
1001
1002 /* Check hash collision */
1003 uint32_t continued = 0;
1004 if (new_hash == sort[mid - 1].hash)
1005 continued = 1;
1006
1007 uint32_t off = 0;
1008 void *ptr;
1009 if (ext4_sb_feature_ro_com(s: sb, EXT4_FRO_COM_METADATA_CSUM))
1010 block_size -= sizeof(struct ext4_dir_entry_tail);
1011
1012 /* First part - to the old block */
1013 for (i = 0; i < mid; ++i) {
1014 ptr = old_data_block->data + off;
1015 memcpy(dest: ptr, src: sort[i].dentry, size: sort[i].rec_len);
1016
1017 struct ext4_dir_en *t = ptr;
1018 if (i < (mid - 1))
1019 ext4_dir_en_set_entry_len(de: t, l: sort[i].rec_len);
1020 else
1021 ext4_dir_en_set_entry_len(de: t, l: block_size - off);
1022
1023 off += sort[i].rec_len;
1024 }
1025
1026 /* Second part - to the new block */
1027 off = 0;
1028 for (i = mid; i < idx; ++i) {
1029 ptr = new_data_block_tmp.data + off;
1030 memcpy(dest: ptr, src: sort[i].dentry, size: sort[i].rec_len);
1031
1032 struct ext4_dir_en *t = ptr;
1033 if (i < (idx - 1))
1034 ext4_dir_en_set_entry_len(de: t, l: sort[i].rec_len);
1035 else
1036 ext4_dir_en_set_entry_len(de: t, l: block_size - off);
1037
1038 off += sort[i].rec_len;
1039 }
1040
1041 block_size = ext4_sb_get_block_size(s: &inode_ref->fs->sb);
1042
1043 /* Do some steps to finish operation */
1044 sb = &inode_ref->fs->sb;
1045 if (ext4_sb_feature_ro_com(s: sb, EXT4_FRO_COM_METADATA_CSUM)) {
1046 struct ext4_dir_entry_tail *t;
1047
1048 t = EXT4_DIRENT_TAIL(old_data_block->data, block_size);
1049 ext4_dir_init_entry_tail(t);
1050 t = EXT4_DIRENT_TAIL(new_data_block_tmp.data, block_size);
1051 ext4_dir_init_entry_tail(t);
1052 }
1053 ext4_dir_set_csum(inode_ref, dirent: (void *)old_data_block->data);
1054 ext4_dir_set_csum(inode_ref, dirent: (void *)new_data_block_tmp.data);
1055 ext4_trans_set_block_dirty(buf: old_data_block->buf);
1056 ext4_trans_set_block_dirty(buf: new_data_block_tmp.buf);
1057
1058 ext4_free(pointer: sort);
1059 ext4_free(pointer: entry_buffer);
1060
1061 ext4_dir_dx_insert_entry(inode_ref, index_block, hash: new_hash + continued,
1062 iblock: new_iblock);
1063
1064 *new_data_block = new_data_block_tmp;
1065 return EOK;
1066}
1067
1068/**@brief Split index node and maybe some parent nodes in the tree hierarchy.
1069 * @param ino_ref Directory i-node
1070 * @param dx_blks Array with path from root to leaf node
1071 * @param dxb Leaf block to be split if needed
1072 * @return Error code
1073 */
1074static int
1075ext4_dir_dx_split_index(struct ext4_inode_ref *ino_ref,
1076 struct ext4_dir_idx_block *dx_blks,
1077 struct ext4_dir_idx_block *dxb,
1078 struct ext4_dir_idx_block **new_dx_block)
1079{
1080 struct ext4_sblock *sb = &ino_ref->fs->sb;
1081 struct ext4_dir_idx_entry *e;
1082 int r;
1083
1084 uint32_t block_size = ext4_sb_get_block_size(s: &ino_ref->fs->sb);
1085 uint32_t entry_space = block_size - sizeof(struct ext4_fake_dir_entry);
1086 uint32_t node_limit = entry_space / sizeof(struct ext4_dir_idx_entry);
1087
1088 bool meta_csum = ext4_sb_feature_ro_com(s: sb, EXT4_FRO_COM_METADATA_CSUM);
1089
1090 if (dxb == dx_blks)
1091 e = ((struct ext4_dir_idx_root *)dxb->b.data)->en;
1092 else
1093 e = ((struct ext4_dir_idx_node *)dxb->b.data)->entries;
1094
1095 struct ext4_dir_idx_climit *climit = (struct ext4_dir_idx_climit *)e;
1096
1097 uint16_t leaf_limit = ext4_dir_dx_climit_get_limit(climit);
1098 uint16_t leaf_count = ext4_dir_dx_climit_get_count(climit);
1099
1100 /* Check if is necessary to split index block */
1101 if (leaf_limit == leaf_count) {
1102 struct ext4_dir_idx_entry *ren;
1103 ptrdiff_t levels = dxb - dx_blks;
1104
1105 ren = ((struct ext4_dir_idx_root *)dx_blks[0].b.data)->en;
1106 struct ext4_dir_idx_climit *rclimit = (void *)ren;
1107 uint16_t root_limit = ext4_dir_dx_climit_get_limit(climit: rclimit);
1108 uint16_t root_count = ext4_dir_dx_climit_get_count(climit: rclimit);
1109
1110
1111 /* Linux limitation */
1112 if ((levels > 0) && (root_limit == root_count))
1113 return ENOSPC;
1114
1115 /* Add new block to directory */
1116 ext4_fsblk_t new_fblk;
1117 uint32_t new_iblk;
1118 r = ext4_fs_append_inode_dblk(inode_ref: ino_ref, fblock: &new_fblk, iblock: &new_iblk);
1119 if (r != EOK)
1120 return r;
1121
1122 /* load new block */
1123 struct ext4_block b;
1124 r = ext4_trans_block_get_noread(bdev: ino_ref->fs->bdev, b: &b, lba: new_fblk);
1125 if (r != EOK)
1126 return r;
1127
1128 struct ext4_dir_idx_node *new_node = (void *)b.data;
1129 struct ext4_dir_idx_entry *new_en = new_node->entries;
1130
1131 memset(dest: &new_node->fake, c: 0, size: sizeof(struct ext4_fake_dir_entry));
1132 new_node->fake.entry_length = block_size;
1133
1134 /* Split leaf node */
1135 if (levels > 0) {
1136 uint32_t count_left = leaf_count / 2;
1137 uint32_t count_right = leaf_count - count_left;
1138 uint32_t hash_right;
1139 size_t sz;
1140
1141 struct ext4_dir_idx_climit *left_climit;
1142 struct ext4_dir_idx_climit *right_climit;
1143
1144 hash_right = ext4_dir_dx_entry_get_hash(entry: e + count_left);
1145 /* Copy data to new node */
1146 sz = count_right * sizeof(struct ext4_dir_idx_entry);
1147 memcpy(dest: new_en, src: e + count_left, size: sz);
1148
1149 /* Initialize new node */
1150 left_climit = (struct ext4_dir_idx_climit *)e;
1151 right_climit = (struct ext4_dir_idx_climit *)new_en;
1152
1153 ext4_dir_dx_climit_set_count(climit: left_climit, count: count_left);
1154 ext4_dir_dx_climit_set_count(climit: right_climit, count: count_right);
1155
1156 if (meta_csum)
1157 entry_space -= sizeof(struct ext4_dir_idx_tail);
1158
1159 ext4_dir_dx_climit_set_limit(climit: right_climit, limit: node_limit);
1160
1161 /* Which index block is target for new entry */
1162 uint32_t position_index =
1163 (dxb->position - dxb->entries);
1164 if (position_index >= count_left) {
1165 ext4_dir_set_dx_csum(
1166 inode_ref: ino_ref,
1167 dirent: (struct ext4_dir_en *)
1168 dxb->b.data);
1169 ext4_trans_set_block_dirty(buf: dxb->b.buf);
1170
1171 struct ext4_block block_tmp = dxb->b;
1172
1173 dxb->b = b;
1174
1175 dxb->position =
1176 new_en + position_index - count_left;
1177 dxb->entries = new_en;
1178
1179 b = block_tmp;
1180 }
1181
1182 /* Finally insert new entry */
1183 ext4_dir_dx_insert_entry(inode_ref: ino_ref, index_block: dx_blks, hash: hash_right,
1184 iblock: new_iblk);
1185 ext4_dir_set_dx_csum(inode_ref: ino_ref, dirent: (void*)dx_blks[0].b.data);
1186 ext4_dir_set_dx_csum(inode_ref: ino_ref, dirent: (void*)dx_blks[1].b.data);
1187 ext4_trans_set_block_dirty(buf: dx_blks[0].b.buf);
1188 ext4_trans_set_block_dirty(buf: dx_blks[1].b.buf);
1189
1190 ext4_dir_set_dx_csum(inode_ref: ino_ref, dirent: (void *)b.data);
1191 ext4_trans_set_block_dirty(buf: b.buf);
1192 return ext4_block_set(bdev: ino_ref->fs->bdev, b: &b);
1193 } else {
1194 size_t sz;
1195 /* Copy data from root to child block */
1196 sz = leaf_count * sizeof(struct ext4_dir_idx_entry);
1197 memcpy(dest: new_en, src: e, size: sz);
1198
1199 struct ext4_dir_idx_climit *new_climit = (void*)new_en;
1200 if (meta_csum)
1201 entry_space -= sizeof(struct ext4_dir_idx_tail);
1202
1203 ext4_dir_dx_climit_set_limit(climit: new_climit, limit: node_limit);
1204
1205 /* Set values in root node */
1206 struct ext4_dir_idx_climit *new_root_climit = (void *)e;
1207
1208 ext4_dir_dx_climit_set_count(climit: new_root_climit, count: 1);
1209 ext4_dir_dx_entry_set_block(entry: e, block: new_iblk);
1210
1211 struct ext4_dir_idx_root *r = (void *)dx_blks[0].b.data;
1212 r->info.indirect_levels = 1;
1213
1214 /* Add new entry to the path */
1215 dxb = dx_blks + 1;
1216 dxb->position = dx_blks->position - e + new_en;
1217 dxb->entries = new_en;
1218 dxb->b = b;
1219 *new_dx_block = dxb;
1220
1221 ext4_dir_set_dx_csum(inode_ref: ino_ref, dirent: (void*)dx_blks[0].b.data);
1222 ext4_dir_set_dx_csum(inode_ref: ino_ref, dirent: (void*)dx_blks[1].b.data);
1223 ext4_trans_set_block_dirty(buf: dx_blks[0].b.buf);
1224 ext4_trans_set_block_dirty(buf: dx_blks[1].b.buf);
1225 }
1226 }
1227
1228 return EOK;
1229}
1230
1231int ext4_dir_dx_add_entry(struct ext4_inode_ref *parent,
1232 struct ext4_inode_ref *child, const char *name, uint32_t name_len)
1233{
1234 int rc2 = EOK;
1235 int r;
1236 /* Get direct block 0 (index root) */
1237 ext4_fsblk_t rblock_addr;
1238 r = ext4_fs_get_inode_dblk_idx(inode_ref: parent, iblock: 0, fblock: &rblock_addr, support_unwritten: false);
1239 if (r != EOK)
1240 return r;
1241
1242 struct ext4_fs *fs = parent->fs;
1243 struct ext4_block root_blk;
1244
1245 r = ext4_trans_block_get(bdev: fs->bdev, b: &root_blk, lba: rblock_addr);
1246 if (r != EOK)
1247 return r;
1248
1249 if (!ext4_dir_dx_csum_verify(inode_ref: parent, de: (void*)root_blk.data)) {
1250 ext4_dbg(DEBUG_DIR_IDX,
1251 DBG_WARN "HTree root checksum failed."
1252 "Inode: %" PRIu32", "
1253 "Block: %" PRIu32"\n",
1254 parent->index,
1255 (uint32_t)0);
1256 }
1257
1258 /* Initialize hinfo structure (mainly compute hash) */
1259 struct ext4_hash_info hinfo;
1260 r = ext4_dir_hinfo_init(hinfo: &hinfo, root_block: &root_blk, sb: &fs->sb, name_len, name);
1261 if (r != EOK) {
1262 ext4_block_set(bdev: fs->bdev, b: &root_blk);
1263 return EXT4_ERR_BAD_DX_DIR;
1264 }
1265
1266 /*
1267 * Hardcoded number 2 means maximum height of index
1268 * tree defined in Linux.
1269 */
1270 struct ext4_dir_idx_block dx_blks[2];
1271 struct ext4_dir_idx_block *dx_blk;
1272 struct ext4_dir_idx_block *dx_it;
1273
1274 r = ext4_dir_dx_get_leaf(hinfo: &hinfo, inode_ref: parent, root_block: &root_blk, dx_block: &dx_blk, dx_blocks: dx_blks);
1275 if (r != EOK) {
1276 r = EXT4_ERR_BAD_DX_DIR;
1277 goto release_index;
1278 }
1279
1280 /* Try to insert to existing data block */
1281 uint32_t leaf_block_idx = ext4_dir_dx_entry_get_block(entry: dx_blk->position);
1282 ext4_fsblk_t leaf_block_addr;
1283 r = ext4_fs_get_inode_dblk_idx(inode_ref: parent, iblock: leaf_block_idx,
1284 fblock: &leaf_block_addr, support_unwritten: false);
1285 if (r != EOK)
1286 goto release_index;
1287
1288 /*
1289 * Check if there is needed to split index node
1290 * (and recursively also parent nodes)
1291 */
1292 r = ext4_dir_dx_split_index(ino_ref: parent, dx_blks, dxb: dx_blk, new_dx_block: &dx_blk);
1293 if (r != EOK)
1294 goto release_target_index;
1295
1296 struct ext4_block target_block;
1297 r = ext4_trans_block_get(bdev: fs->bdev, b: &target_block, lba: leaf_block_addr);
1298 if (r != EOK)
1299 goto release_index;
1300
1301 if (!ext4_dir_csum_verify(inode_ref: parent,dirent: (void *)target_block.data)) {
1302 ext4_dbg(DEBUG_DIR_IDX,
1303 DBG_WARN "HTree leaf block checksum failed."
1304 "Inode: %" PRIu32", "
1305 "Block: %" PRIu32"\n",
1306 parent->index,
1307 leaf_block_idx);
1308 }
1309
1310 /* Check if insert operation passed */
1311 r = ext4_dir_try_insert_entry(sb: &fs->sb, inode_ref: parent, dst_blk: &target_block, child,
1312 name, name_len);
1313 if (r == EOK)
1314 goto release_target_index;
1315
1316 /* Split entries to two blocks (includes sorting by hash value) */
1317 struct ext4_block new_block;
1318 r = ext4_dir_dx_split_data(inode_ref: parent, hinfo: &hinfo, old_data_block: &target_block, index_block: dx_blk,
1319 new_data_block: &new_block);
1320 if (r != EOK) {
1321 rc2 = r;
1322 goto release_target_index;
1323 }
1324
1325 /* Where to save new entry */
1326 uint32_t blk_hash = ext4_dir_dx_entry_get_hash(entry: dx_blk->position + 1);
1327 if (hinfo.hash >= blk_hash)
1328 r = ext4_dir_try_insert_entry(sb: &fs->sb, inode_ref: parent, dst_blk: &new_block,
1329 child, name, name_len);
1330 else
1331 r = ext4_dir_try_insert_entry(sb: &fs->sb, inode_ref: parent, dst_blk: &target_block,
1332 child, name, name_len);
1333
1334 /* Cleanup */
1335 r = ext4_block_set(bdev: fs->bdev, b: &new_block);
1336 if (r != EOK)
1337 return r;
1338
1339/* Cleanup operations */
1340
1341release_target_index:
1342 rc2 = r;
1343
1344 r = ext4_block_set(bdev: fs->bdev, b: &target_block);
1345 if (r != EOK)
1346 return r;
1347
1348release_index:
1349 if (r != EOK)
1350 rc2 = r;
1351
1352 dx_it = dx_blks;
1353
1354 while (dx_it <= dx_blk) {
1355 r = ext4_block_set(bdev: fs->bdev, b: &dx_it->b);
1356 if (r != EOK)
1357 return r;
1358
1359 dx_it++;
1360 }
1361
1362 return rc2;
1363}
1364
1365int ext4_dir_dx_reset_parent_inode(struct ext4_inode_ref *dir,
1366 uint32_t parent_inode)
1367{
1368 /* Load block 0, where will be index root located */
1369 ext4_fsblk_t fblock;
1370 int rc = ext4_fs_get_inode_dblk_idx(inode_ref: dir, iblock: 0, fblock: &fblock, support_unwritten: false);
1371 if (rc != EOK)
1372 return rc;
1373
1374 struct ext4_block block;
1375 rc = ext4_trans_block_get(bdev: dir->fs->bdev, b: &block, lba: fblock);
1376 if (rc != EOK)
1377 return rc;
1378
1379 if (!ext4_dir_dx_csum_verify(inode_ref: dir, de: (void *)block.data)) {
1380 ext4_dbg(DEBUG_DIR_IDX,
1381 DBG_WARN "HTree root checksum failed."
1382 "Inode: %" PRIu32", "
1383 "Block: %" PRIu32"\n",
1384 dir->index,
1385 (uint32_t)0);
1386 }
1387
1388 /* Initialize pointers to data structures */
1389 struct ext4_dir_idx_root *root = (void *)block.data;
1390
1391 /* Fill the inode field with a new parent ino. */
1392 ext4_dx_dot_en_set_inode(de: &root->dots[1], inode: parent_inode);
1393
1394 ext4_dir_set_dx_csum(inode_ref: dir, dirent: (void *)block.data);
1395 ext4_trans_set_block_dirty(buf: block.buf);
1396
1397 return ext4_block_set(bdev: dir->fs->bdev, b: &block);
1398}
1399
1400/**
1401 * @}
1402 */
1403