2 * Copyright (c) 2013 Grzegorz Kostka (kostka.grzegorz@gmail.com)
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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.
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.
29 /** @addtogroup lwext4
33 * @file ext4_dir_idx.c
34 * @brief Directory indexing procedures.
37 #include "ext4_config.h"
38 #include "ext4_dir_idx.h"
40 #include "ext4_blockdev.h"
42 #include "ext4_super.h"
43 #include "ext4_inode.h"
44 #include "ext4_crc32c.h"
45 #include "ext4_hash.h"
50 /**@brief Get hash version used in directory index.
51 * @param root_info Pointer to root info structure of index
52 * @return Hash algorithm version
54 static inline uint8_t ext4_dir_dx_root_info_get_hash_version(
55 struct ext4_dir_idx_root_info *root_info)
57 return root_info->hash_version;
60 /**@brief Set hash version, that will be used in directory index.
61 * @param root_info Pointer to root info structure of index
62 * @param v Hash algorithm version
64 static inline void ext4_dir_dx_root_info_set_hash_version(
65 struct ext4_dir_idx_root_info *root_info, uint8_t v)
67 root_info->hash_version = v;
70 /**@brief Get length of root_info structure in bytes.
71 * @param root_info Pointer to root info structure of index
72 * @return Length of the structure
74 static inline uint8_t ext4_dir_dx_root_info_get_info_length(
75 struct ext4_dir_idx_root_info *root_info)
77 return root_info->info_length;
80 /**@brief Set length of root_info structure in bytes.
81 * @param root_info Pointer to root info structure of index
82 * @param info_length Length of the structure
84 static inline void ext4_dir_dx_root_info_set_info_length(
85 struct ext4_dir_idx_root_info *root_info, uint8_t len)
87 root_info->info_length = len;
90 /**@brief Get number of indirect levels of HTree.
91 * @param root_info Pointer to root info structure of index
92 * @return Height of HTree (actually only 0 or 1)
94 static inline uint8_t ext4_dir_dx_root_info_get_indirect_levels(
95 struct ext4_dir_idx_root_info *root_info)
97 return root_info->indirect_levels;
100 /**@brief Set number of indirect levels of HTree.
101 * @param root_info Pointer to root info structure of index
102 * @param lvl Height of HTree (actually only 0 or 1)
104 static inline void ext4_dir_dx_root_info_set_indirect_levels(
105 struct ext4_dir_idx_root_info *root_info, uint8_t lvl)
107 root_info->indirect_levels = lvl;
110 /**@brief Get maximum number of index node entries.
111 * @param climit Pointer to counlimit structure
112 * @return Maximum of entries in node
114 static inline uint16_t
115 ext4_dir_dx_countlimit_get_limit(struct ext4_dir_idx_countlimit *climit)
117 return to_le16(climit->limit);
120 /**@brief Set maximum number of index node entries.
121 * @param climit Pointer to counlimit structure
122 * @param limit Maximum of entries in node
125 ext4_dir_dx_countlimit_set_limit(struct ext4_dir_idx_countlimit *climit,
128 climit->limit = to_le16(limit);
131 /**@brief Get current number of index node entries.
132 * @param climit Pointer to counlimit structure
133 * @return Number of entries in node
135 static inline uint16_t
136 ext4_dir_dx_countlimit_get_count(struct ext4_dir_idx_countlimit *climit)
138 return to_le16(climit->count);
141 /**@brief Set current number of index node entries.
142 * @param climit Pointer to counlimit structure
143 * @param count Number of entries in node
146 ext4_dir_dx_countlimit_set_count(struct ext4_dir_idx_countlimit *climit,
149 climit->count = to_le16(count);
152 /**@brief Get hash value of index entry.
153 * @param entry Pointer to index entry
156 static inline uint32_t
157 ext4_dir_dx_entry_get_hash(struct ext4_dir_idx_entry *entry)
159 return to_le32(entry->hash);
162 /**@brief Set hash value of index entry.
163 * @param entry Pointer to index entry
164 * @param hash Hash value
167 ext4_dir_dx_entry_set_hash(struct ext4_dir_idx_entry *entry, uint32_t hash)
169 entry->hash = to_le32(hash);
172 /**@brief Get block address where child node is located.
173 * @param entry Pointer to index entry
174 * @return Block address of child node
176 static inline uint32_t
177 ext4_dir_dx_entry_get_block(struct ext4_dir_idx_entry *entry)
179 return to_le32(entry->block);
182 /**@brief Set block address where child node is located.
183 * @param entry Pointer to index entry
184 * @param block Block address of child node
187 ext4_dir_dx_entry_set_block(struct ext4_dir_idx_entry *entry,
190 entry->block = to_le32(block);
193 /**@brief Sort entry item.*/
194 struct ext4_dx_sort_entry {
200 static int ext4_dir_dx_hash_string(struct ext4_hash_info *hinfo, int len,
203 return ext2_htree_hash(name, len, hinfo->seed, hinfo->hash_version,
204 &hinfo->hash, &hinfo->minor_hash);
207 #if CONFIG_META_CSUM_ENABLE
209 ext4_dir_dx_checksum(struct ext4_inode_ref *inode_ref,
211 int count_offset, int count, struct ext4_dir_idx_tail *t)
213 uint32_t orig_checksum, checksum = 0;
214 struct ext4_sblock *sb = &inode_ref->fs->sb;
217 /* Compute the checksum only if the filesystem supports it */
218 if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM)) {
219 uint32_t ino_index = to_le32(inode_ref->index);
221 to_le32(ext4_inode_get_generation(inode_ref->inode));
223 size = count_offset +
224 (count * sizeof(struct ext4_dir_idx_tail));
225 orig_checksum = t->checksum;
227 /* First calculate crc32 checksum against fs uuid */
228 checksum = ext4_crc32c(EXT4_CRC32_INIT, sb->uuid,
230 /* Then calculate crc32 checksum against inode number
231 * and inode generation */
232 checksum = ext4_crc32c(checksum, &ino_index,
234 checksum = ext4_crc32c(checksum, &ino_gen,
236 /* After that calculate crc32 checksum against all the dx_entry */
237 checksum = ext4_crc32c(checksum, dirent, size);
238 /* Finally calculate crc32 checksum for dx_tail */
239 checksum = ext4_crc32c(checksum, t,
240 sizeof(struct ext4_dir_idx_tail));
241 t->checksum = orig_checksum;
246 static struct ext4_dir_idx_countlimit *
247 ext4_dir_dx_get_countlimit(struct ext4_inode_ref *inode_ref,
248 struct ext4_dir_entry_ll *dirent,
251 struct ext4_dir_entry_ll *dp;
252 struct ext4_dir_idx_root *root;
253 struct ext4_sblock *sb = &inode_ref->fs->sb;
256 if (ext4_dir_entry_ll_get_entry_length(dirent) ==
257 ext4_sb_get_block_size(sb))
259 else if (ext4_dir_entry_ll_get_entry_length(dirent) == 12) {
260 root = (struct ext4_dir_idx_root *)dirent;
261 dp = (struct ext4_dir_entry_ll *)&root->dots[1];
262 if (ext4_dir_entry_ll_get_entry_length(dp) !=
263 ext4_sb_get_block_size(sb) - 12)
265 if (root->info.reserved_zero ||
266 root->info.info_length != sizeof(struct ext4_dir_idx_root_info))
273 *offset = count_offset;
274 return (struct ext4_dir_idx_countlimit *)(((char *)dirent) + count_offset);
279 * Currently we do not verify the checksum of HTree node.
282 ext4_dir_dx_checksum_verify(struct ext4_inode_ref *inode_ref,
283 struct ext4_dir_entry_ll *dirent)
285 struct ext4_sblock *sb = &inode_ref->fs->sb;
286 int count_offset, limit, count;
288 if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM)) {
289 struct ext4_dir_idx_countlimit *countlimit =
290 ext4_dir_dx_get_countlimit(inode_ref, dirent, &count_offset);
292 /* Directory seems corrupted. */
295 struct ext4_dir_idx_tail *t;
296 limit = ext4_dir_dx_countlimit_get_limit(countlimit);
297 count = ext4_dir_dx_countlimit_get_count(countlimit);
298 if (count_offset + (limit * sizeof(struct ext4_dir_idx_entry)) >
299 ext4_sb_get_block_size(sb) -
300 sizeof(struct ext4_dir_idx_tail)) {
301 /* There is no space to hold the checksum */
304 t = (void *)(((struct ext4_dir_idx_entry *)countlimit) + limit);
306 if (t->checksum != to_le32(ext4_dir_dx_checksum(inode_ref,
317 ext4_dir_set_dx_checksum(struct ext4_inode_ref *inode_ref,
318 struct ext4_dir_entry_ll *dirent)
320 int count_offset, limit, count;
321 struct ext4_sblock *sb = &inode_ref->fs->sb;
323 if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM)) {
324 struct ext4_dir_idx_countlimit *countlimit =
325 ext4_dir_dx_get_countlimit(inode_ref, dirent, &count_offset);
327 /* Directory seems corrupted. */
330 struct ext4_dir_idx_tail *t;
331 limit = ext4_dir_dx_countlimit_get_limit(countlimit);
332 count = ext4_dir_dx_countlimit_get_count(countlimit);
333 if (count_offset + (limit * sizeof(struct ext4_dir_idx_entry)) >
334 ext4_sb_get_block_size(sb) -
335 sizeof(struct ext4_dir_idx_tail)) {
336 /* There is no space to hold the checksum */
339 t = (struct ext4_dir_idx_tail *)
340 (((struct ext4_dir_idx_entry *)countlimit) + limit);
342 t->checksum = to_le32(ext4_dir_dx_checksum(inode_ref, dirent,
343 count_offset, count, t));
347 #define ext4_dir_dx_checksum_verify(...) true
348 #define ext4_dir_set_dx_checksum(...)
351 /****************************************************************************/
353 int ext4_dir_dx_init(struct ext4_inode_ref *dir, struct ext4_inode_ref *parent)
355 /* Load block 0, where will be index root located */
358 struct ext4_sblock *sb = &dir->fs->sb;
359 int rc = ext4_fs_append_inode_block(dir, &fblock, &iblock);
363 struct ext4_block block;
364 rc = ext4_block_get_noread(dir->fs->bdev, &block, fblock);
368 /* Initialize pointers to data structures */
369 struct ext4_dir_idx_root *root = (void *)block.data;
370 struct ext4_dir_idx_root_info *info = &(root->info);
372 /* Initialize dot entries */
373 ext4_dir_write_entry(&dir->fs->sb,
374 (struct ext4_dir_entry_ll *)root->dots,
380 ext4_dir_write_entry(&dir->fs->sb,
381 (struct ext4_dir_entry_ll *)(root->dots + 1),
382 ext4_sb_get_block_size(sb) - 12,
387 /* Initialize root info structure */
388 uint8_t hash_version = ext4_get8(&dir->fs->sb, default_hash_version);
390 ext4_dir_dx_root_info_set_hash_version(info, hash_version);
391 ext4_dir_dx_root_info_set_indirect_levels(info, 0);
392 ext4_dir_dx_root_info_set_info_length(info, 8);
394 /* Set limit and current number of entries */
395 struct ext4_dir_idx_countlimit *countlimit =
396 (struct ext4_dir_idx_countlimit *)&root->entries;
398 ext4_dir_dx_countlimit_set_count(countlimit, 1);
400 uint32_t block_size = ext4_sb_get_block_size(&dir->fs->sb);
401 uint32_t entry_space = block_size -
402 2 * sizeof(struct ext4_dir_idx_dot_entry) -
403 sizeof(struct ext4_dir_idx_root_info);
404 if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM))
405 entry_space -= sizeof(struct ext4_dir_idx_tail);
407 uint16_t root_limit =
408 entry_space / sizeof(struct ext4_dir_idx_entry);
410 ext4_dir_dx_countlimit_set_limit(countlimit, root_limit);
412 /* Append new block, where will be new entries inserted in the future */
413 rc = ext4_fs_append_inode_block(dir, &fblock, &iblock);
415 ext4_block_set(dir->fs->bdev, &block);
419 struct ext4_block new_block;
421 rc = ext4_block_get_noread(dir->fs->bdev, &new_block, fblock);
423 ext4_block_set(dir->fs->bdev, &block);
427 /* Fill the whole block with empty entry */
428 struct ext4_dir_entry_ll *block_entry = (void *)new_block.data;
430 if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM)) {
431 ext4_dir_entry_ll_set_entry_length(block_entry,
433 sizeof(struct ext4_dir_entry_tail));
434 ext4_dir_entry_ll_set_name_length(sb,
437 ext4_dir_entry_ll_set_inode_type(sb,
439 EXT4_DIRENTRY_UNKNOWN);
441 initialize_dir_tail(EXT4_DIRENT_TAIL(block_entry,
442 ext4_sb_get_block_size(sb)));
443 ext4_dir_set_checksum(dir,
444 (struct ext4_dir_entry_ll *)new_block.data);
446 ext4_dir_entry_ll_set_entry_length(block_entry, block_size);
449 ext4_dir_entry_ll_set_inode(block_entry, 0);
451 new_block.dirty = true;
452 rc = ext4_block_set(dir->fs->bdev, &new_block);
454 ext4_block_set(dir->fs->bdev, &block);
458 /* Connect new block to the only entry in index */
459 struct ext4_dir_idx_entry *entry = root->entries;
460 ext4_dir_dx_entry_set_block(entry, iblock);
462 ext4_dir_set_dx_checksum(dir,
463 (struct ext4_dir_entry_ll *)block.data);
466 return ext4_block_set(dir->fs->bdev, &block);
469 /**@brief Initialize hash info structure necessary for index operations.
470 * @param hinfo Pointer to hinfo to be initialized
471 * @param root_block Root block (number 0) of index
472 * @param sb Pointer to superblock
473 * @param name_len Length of name to be computed hash value from
474 * @param name Name to be computed hash value from
475 * @return Standard error code
477 static int ext4_dir_hinfo_init(struct ext4_hash_info *hinfo,
478 struct ext4_block *root_block,
479 struct ext4_sblock *sb, size_t name_len,
482 struct ext4_dir_idx_root *root =
483 (struct ext4_dir_idx_root *)root_block->data;
485 if ((root->info.hash_version != EXT2_HTREE_LEGACY) &&
486 (root->info.hash_version != EXT2_HTREE_HALF_MD4) &&
487 (root->info.hash_version != EXT2_HTREE_TEA))
488 return EXT4_ERR_BAD_DX_DIR;
490 /* Check unused flags */
491 if (root->info.unused_flags != 0)
492 return EXT4_ERR_BAD_DX_DIR;
494 /* Check indirect levels */
495 if (root->info.indirect_levels > 1)
496 return EXT4_ERR_BAD_DX_DIR;
498 /* Check if node limit is correct */
499 uint32_t block_size = ext4_sb_get_block_size(sb);
500 uint32_t entry_space = block_size;
501 entry_space -= 2 * sizeof(struct ext4_dir_idx_dot_entry);
502 entry_space -= sizeof(struct ext4_dir_idx_root_info);
503 if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM))
504 entry_space -= sizeof(struct ext4_dir_idx_tail);
505 entry_space = entry_space / sizeof(struct ext4_dir_idx_entry);
507 uint16_t limit = ext4_dir_dx_countlimit_get_limit(
508 (struct ext4_dir_idx_countlimit *)&root->entries);
509 if (limit != entry_space)
510 return EXT4_ERR_BAD_DX_DIR;
512 /* Check hash version and modify if necessary */
513 hinfo->hash_version =
514 ext4_dir_dx_root_info_get_hash_version(&root->info);
515 if ((hinfo->hash_version <= EXT2_HTREE_TEA) &&
516 (ext4_sb_check_flag(sb, EXT4_SUPERBLOCK_FLAGS_UNSIGNED_HASH))) {
517 /* Use unsigned hash */
518 hinfo->hash_version += 3;
521 /* Load hash seed from superblock */
523 hinfo->seed = ext4_get8(sb, hash_seed);
525 /* Compute hash value of name */
527 return ext4_dir_dx_hash_string(hinfo, name_len, name);
532 /**@brief Walk through index tree and load leaf with corresponding hash value.
533 * @param hinfo Initialized hash info structure
534 * @param inode_ref Current i-node
535 * @param root_block Root block (iblock 0), where is root node located
536 * @param dx_block Pointer to leaf node in dx_blocks array
537 * @param dx_blocks Array with the whole path from root to leaf
538 * @return Standard error code
540 static int ext4_dir_dx_get_leaf(struct ext4_hash_info *hinfo,
541 struct ext4_inode_ref *inode_ref,
542 struct ext4_block *root_block,
543 struct ext4_dir_idx_block **dx_block,
544 struct ext4_dir_idx_block *dx_blocks)
546 struct ext4_dir_idx_block *tmp_dx_block = dx_blocks;
547 struct ext4_dir_idx_root *root =
548 (struct ext4_dir_idx_root *)root_block->data;
549 struct ext4_dir_idx_entry *entries =
550 (struct ext4_dir_idx_entry *)&root->entries;
552 uint16_t limit = ext4_dir_dx_countlimit_get_limit(
553 (struct ext4_dir_idx_countlimit *)entries);
554 uint8_t indirect_level =
555 ext4_dir_dx_root_info_get_indirect_levels(&root->info);
557 struct ext4_block *tmp_block = root_block;
558 struct ext4_dir_idx_entry *p;
559 struct ext4_dir_idx_entry *q;
560 struct ext4_dir_idx_entry *m;
561 struct ext4_dir_idx_entry *at;
563 /* Walk through the index tree */
565 uint16_t count = ext4_dir_dx_countlimit_get_count(
566 (struct ext4_dir_idx_countlimit *)entries);
567 if ((count == 0) || (count > limit))
568 return EXT4_ERR_BAD_DX_DIR;
570 /* Do binary search in every node */
572 q = entries + count - 1;
576 if (ext4_dir_dx_entry_get_hash(m) > hinfo->hash)
586 memcpy(&tmp_dx_block->block, tmp_block,
587 sizeof(struct ext4_block));
588 tmp_dx_block->entries = entries;
589 tmp_dx_block->position = at;
591 /* Is algorithm in the leaf? */
592 if (indirect_level == 0) {
593 *dx_block = tmp_dx_block;
597 /* Goto child node */
598 uint32_t next_block = ext4_dir_dx_entry_get_block(at);
603 int rc = ext4_fs_get_inode_data_block_index(
604 inode_ref, next_block, &fblock, false);
608 rc = ext4_block_get(inode_ref->fs->bdev, tmp_block, fblock);
613 ((struct ext4_dir_idx_node *)tmp_block->data)->entries;
614 limit = ext4_dir_dx_countlimit_get_limit(
615 (struct ext4_dir_idx_countlimit *)entries);
617 struct ext4_sblock *sb = &inode_ref->fs->sb;
618 uint16_t entry_space = ext4_sb_get_block_size(sb) -
619 sizeof(struct ext4_fake_dir_entry);
621 if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM))
622 entry_space -= sizeof(struct ext4_dir_idx_tail);
624 entry_space = entry_space / sizeof(struct ext4_dir_idx_entry);
626 if (limit != entry_space) {
627 ext4_block_set(inode_ref->fs->bdev, tmp_block);
628 return EXT4_ERR_BAD_DX_DIR;
631 if (!ext4_dir_dx_checksum_verify(inode_ref,
632 (struct ext4_dir_entry_ll *)tmp_block->data)) {
633 ext4_dbg(DEBUG_DIR_IDX,
634 DBG_WARN "HTree checksum failed."
635 "Inode: %" PRIu32", "
636 "Block: %" PRIu32"\n",
648 /**@brief Check if the the next block would be checked during entry search.
649 * @param inode_ref Directory i-node
650 * @param hash Hash value to check
651 * @param dx_block Current block
652 * @param dx_blocks Array with path from root to leaf node
653 * @return Standard Error code
655 static int ext4_dir_dx_next_block(struct ext4_inode_ref *inode_ref,
657 struct ext4_dir_idx_block *dx_block,
658 struct ext4_dir_idx_block *dx_blocks)
660 uint32_t num_handles = 0;
661 struct ext4_dir_idx_block *p = dx_block;
663 /* Try to find data block with next bunch of entries */
666 uint16_t count = ext4_dir_dx_countlimit_get_count(
667 (struct ext4_dir_idx_countlimit *)p->entries);
669 if (p->position < p->entries + count)
679 /* Check hash collision (if not occurred - no next block cannot be
681 uint32_t current_hash = ext4_dir_dx_entry_get_hash(p->position);
682 if ((hash & 1) == 0) {
683 if ((current_hash & ~1) != hash)
688 while (num_handles--) {
689 uint32_t block_idx = ext4_dir_dx_entry_get_block(p->position);
690 ext4_fsblk_t block_addr;
692 int rc = ext4_fs_get_inode_data_block_index(
693 inode_ref, block_idx, &block_addr, false);
697 struct ext4_block block;
698 rc = ext4_block_get(inode_ref->fs->bdev, &block, block_addr);
702 if (!ext4_dir_dx_checksum_verify(inode_ref,
703 (struct ext4_dir_entry_ll *)block.data)) {
704 ext4_dbg(DEBUG_DIR_IDX,
705 DBG_WARN "HTree checksum failed."
706 "Inode: %" PRIu32", "
707 "Block: %" PRIu32"\n",
714 /* Don't forget to put old block (prevent memory leak) */
715 rc = ext4_block_set(inode_ref->fs->bdev, &p->block);
719 memcpy(&p->block, &block, sizeof(block));
721 ((struct ext4_dir_idx_node *)block.data)->entries;
722 p->position = p->entries;
728 int ext4_dir_dx_find_entry(struct ext4_dir_search_result *result,
729 struct ext4_inode_ref *inode_ref, size_t name_len,
732 /* Load direct block 0 (index root) */
733 ext4_fsblk_t root_block_addr;
736 ext4_fs_get_inode_data_block_index(inode_ref,
737 0, &root_block_addr, false);
741 struct ext4_fs *fs = inode_ref->fs;
743 struct ext4_block root_block;
744 rc = ext4_block_get(fs->bdev, &root_block, root_block_addr);
748 if (!ext4_dir_dx_checksum_verify(inode_ref,
749 (struct ext4_dir_entry_ll *)root_block.data)) {
750 ext4_dbg(DEBUG_DIR_IDX,
751 DBG_WARN "HTree root checksum failed."
752 "Inode: %" PRIu32", "
753 "Block: %" PRIu32"\n",
758 /* Initialize hash info (compute hash value) */
759 struct ext4_hash_info hinfo;
760 rc = ext4_dir_hinfo_init(&hinfo, &root_block, &fs->sb, name_len, name);
762 ext4_block_set(fs->bdev, &root_block);
763 return EXT4_ERR_BAD_DX_DIR;
767 * Hardcoded number 2 means maximum height of index tree,
768 * specified in the Linux driver.
770 struct ext4_dir_idx_block dx_blocks[2];
771 struct ext4_dir_idx_block *dx_block;
772 struct ext4_dir_idx_block *tmp;
774 rc = ext4_dir_dx_get_leaf(&hinfo, inode_ref, &root_block, &dx_block,
777 ext4_block_set(fs->bdev, &root_block);
778 return EXT4_ERR_BAD_DX_DIR;
782 /* Load leaf block */
783 uint32_t leaf_block_idx =
784 ext4_dir_dx_entry_get_block(dx_block->position);
785 ext4_fsblk_t leaf_block_addr;
787 rc = ext4_fs_get_inode_data_block_index(
788 inode_ref, leaf_block_idx, &leaf_block_addr,
793 struct ext4_block leaf_block;
794 rc = ext4_block_get(fs->bdev, &leaf_block, leaf_block_addr);
798 if (!ext4_dir_checksum_verify(inode_ref,
799 (struct ext4_dir_entry_ll *)leaf_block.data)) {
800 ext4_dbg(DEBUG_DIR_IDX,
801 DBG_WARN "HTree leaf block checksum failed."
802 "Inode: %" PRIu32", "
803 "Block: %" PRIu32"\n",
808 /* Linear search inside block */
809 struct ext4_dir_entry_ll *res_dentry;
810 rc = ext4_dir_find_in_block(&leaf_block, &fs->sb, name_len,
813 /* Found => return it */
815 result->block = leaf_block;
816 result->dentry = res_dentry;
820 /* Not found, leave untouched */
821 rc2 = ext4_block_set(fs->bdev, &leaf_block);
828 /* check if the next block could be checked */
829 rc = ext4_dir_dx_next_block(inode_ref, hinfo.hash, dx_block,
833 } while (rc == ENOENT);
835 /* Entry not found */
839 /* The whole path must be released (preventing memory leak) */
842 while (tmp <= dx_block) {
843 rc2 = ext4_block_set(fs->bdev, &tmp->block);
844 if (rc == EOK && rc2 != EOK)
852 #if CONFIG_DIR_INDEX_COMB_SORT
853 #define SWAP_ENTRY(se1, se2) \
855 struct ext4_dx_sort_entry tmp = se1; \
861 static void comb_sort(struct ext4_dx_sort_entry *se, uint32_t count)
863 struct ext4_dx_sort_entry *p, *q, *top = se + count - 1;
867 count = (count * 10) / 13;
870 for (p = top, q = p - count; q >= se; p--, q--)
871 if (p->hash < q->hash)
879 if (q[1].hash >= q[0].hash)
881 SWAP_ENTRY(*(q + 1), *q);
888 /**@brief Compare function used to pass in quicksort implementation.
889 * It can compare two entries by hash value.
890 * @param arg1 First entry
891 * @param arg2 Second entry
892 * @param dummy Unused parameter, can be NULL
894 * @return Classic compare result
895 * (0: equal, -1: arg1 < arg2, 1: arg1 > arg2)
897 static int ext4_dir_dx_entry_comparator(const void *arg1, const void *arg2)
899 struct ext4_dx_sort_entry *entry1 = (void *)arg1;
900 struct ext4_dx_sort_entry *entry2 = (void *)arg2;
902 if (entry1->hash == entry2->hash)
905 if (entry1->hash < entry2->hash)
912 /**@brief Insert new index entry to block.
913 * Note that space for new entry must be checked by caller.
914 * @param inode_ref Directory i-node
915 * @param index_block Block where to insert new entry
916 * @param hash Hash value covered by child node
917 * @param iblock Logical number of child block
921 ext4_dir_dx_insert_entry(struct ext4_inode_ref *inode_ref __unused,
922 struct ext4_dir_idx_block *index_block,
923 uint32_t hash, uint32_t iblock)
925 struct ext4_dir_idx_entry *old_index_entry = index_block->position;
926 struct ext4_dir_idx_entry *new_index_entry = old_index_entry + 1;
928 struct ext4_dir_idx_countlimit *countlimit =
929 (struct ext4_dir_idx_countlimit *)index_block->entries;
930 uint32_t count = ext4_dir_dx_countlimit_get_count(countlimit);
932 struct ext4_dir_idx_entry *start_index = index_block->entries;
934 (uint8_t *)(start_index + count) - (uint8_t *)(new_index_entry);
936 memmove(new_index_entry + 1, new_index_entry, bytes);
938 ext4_dir_dx_entry_set_block(new_index_entry, iblock);
939 ext4_dir_dx_entry_set_hash(new_index_entry, hash);
941 ext4_dir_dx_countlimit_set_count(countlimit, count + 1);
943 ext4_dir_set_dx_checksum(inode_ref,
944 (struct ext4_dir_entry_ll *)index_block->block.data);
945 index_block->block.dirty = true;
948 /**@brief Split directory entries to two parts preventing node overflow.
949 * @param inode_ref Directory i-node
950 * @param hinfo Hash info
951 * @param old_data_block Block with data to be split
952 * @param index_block Block where index entries are located
953 * @param new_data_block Output value for newly allocated data block
955 static int ext4_dir_dx_split_data(struct ext4_inode_ref *inode_ref,
956 struct ext4_hash_info *hinfo,
957 struct ext4_block *old_data_block,
958 struct ext4_dir_idx_block *index_block,
959 struct ext4_block *new_data_block)
963 /* Allocate buffer for directory entries */
964 uint32_t block_size = ext4_sb_get_block_size(&inode_ref->fs->sb);
966 uint8_t *entry_buffer = malloc(block_size);
967 if (entry_buffer == NULL)
970 /* dot entry has the smallest size available */
971 uint32_t max_entry_count =
972 block_size / sizeof(struct ext4_dir_idx_dot_entry);
974 /* Allocate sort entry */
975 struct ext4_dx_sort_entry *sort_array =
976 malloc(max_entry_count * sizeof(struct ext4_dx_sort_entry));
978 if (sort_array == NULL) {
984 uint32_t real_size = 0;
986 /* Initialize hinfo */
987 struct ext4_hash_info tmp_hinfo;
988 memcpy(&tmp_hinfo, hinfo, sizeof(struct ext4_hash_info));
990 /* Load all valid entries to the buffer */
991 struct ext4_dir_entry_ll *dentry = (void *)old_data_block->data;
992 uint8_t *entry_buffer_ptr = entry_buffer;
993 while ((void *)dentry < (void *)(old_data_block->data + block_size)) {
994 /* Read only valid entries */
995 if (ext4_dir_entry_ll_get_inode(dentry) && dentry->name_length) {
996 uint8_t len = ext4_dir_entry_ll_get_name_length(
997 &inode_ref->fs->sb, dentry);
999 rc = ext4_dir_dx_hash_string(&tmp_hinfo, len,
1000 (char *)dentry->name);
1007 uint32_t rec_len = 8 + len;
1009 if ((rec_len % 4) != 0)
1010 rec_len += 4 - (rec_len % 4);
1012 memcpy(entry_buffer_ptr, dentry, rec_len);
1014 sort_array[idx].dentry = entry_buffer_ptr;
1015 sort_array[idx].rec_len = rec_len;
1016 sort_array[idx].hash = tmp_hinfo.hash;
1018 entry_buffer_ptr += rec_len;
1019 real_size += rec_len;
1023 dentry = (void *)((uint8_t *)dentry +
1024 ext4_dir_entry_ll_get_entry_length(dentry));
1027 /* Sort all entries */
1028 #if CONFIG_DIR_INDEX_COMB_SORT
1029 comb_sort(sort_array, idx);
1031 qsort(sort_array, idx, sizeof(struct ext4_dx_sort_entry),
1032 ext4_dir_dx_entry_comparator);
1034 /* Allocate new block for store the second part of entries */
1035 ext4_fsblk_t new_fblock;
1036 uint32_t new_iblock;
1037 rc = ext4_fs_append_inode_block(inode_ref, &new_fblock, &new_iblock);
1044 /* Load new block */
1045 struct ext4_block new_data_block_tmp;
1046 rc = ext4_block_get_noread(inode_ref->fs->bdev, &new_data_block_tmp,
1055 * Distribute entries to two blocks (by size)
1056 * - compute the half
1058 uint32_t new_hash = 0;
1059 uint32_t current_size = 0;
1062 for (i = 0; i < idx; ++i) {
1063 if ((current_size + sort_array[i].rec_len) > (block_size / 2)) {
1064 new_hash = sort_array[i].hash;
1069 current_size += sort_array[i].rec_len;
1072 /* Check hash collision */
1073 uint32_t continued = 0;
1074 if (new_hash == sort_array[mid - 1].hash)
1077 uint32_t offset = 0;
1079 struct ext4_sblock *sb = &inode_ref->fs->sb;
1080 if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM))
1081 block_size -= sizeof(struct ext4_dir_entry_tail);
1083 /* First part - to the old block */
1084 for (i = 0; i < mid; ++i) {
1085 ptr = old_data_block->data + offset;
1086 memcpy(ptr, sort_array[i].dentry, sort_array[i].rec_len);
1088 struct ext4_dir_entry_ll *tmp = ptr;
1090 ext4_dir_entry_ll_set_entry_length(
1091 tmp, sort_array[i].rec_len);
1093 ext4_dir_entry_ll_set_entry_length(tmp,
1094 block_size - offset);
1096 offset += sort_array[i].rec_len;
1099 /* Second part - to the new block */
1101 for (i = mid; i < idx; ++i) {
1102 ptr = new_data_block_tmp.data + offset;
1103 memcpy(ptr, sort_array[i].dentry, sort_array[i].rec_len);
1105 struct ext4_dir_entry_ll *tmp = ptr;
1107 ext4_dir_entry_ll_set_entry_length(
1108 tmp, sort_array[i].rec_len);
1110 ext4_dir_entry_ll_set_entry_length(tmp,
1111 block_size - offset);
1113 offset += sort_array[i].rec_len;
1116 block_size = ext4_sb_get_block_size(&inode_ref->fs->sb);
1118 /* Do some steps to finish operation */
1119 sb = &inode_ref->fs->sb;
1120 if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM)) {
1121 initialize_dir_tail(EXT4_DIRENT_TAIL(old_data_block->data,
1123 initialize_dir_tail(EXT4_DIRENT_TAIL(new_data_block_tmp.data,
1126 ext4_dir_set_checksum(inode_ref,
1127 (struct ext4_dir_entry_ll *)old_data_block->data);
1128 ext4_dir_set_checksum(inode_ref,
1129 (struct ext4_dir_entry_ll *)new_data_block_tmp.data);
1130 old_data_block->dirty = true;
1131 new_data_block_tmp.dirty = true;
1136 ext4_dir_dx_insert_entry(inode_ref,
1138 new_hash + continued, new_iblock);
1140 *new_data_block = new_data_block_tmp;
1145 /**@brief Split index node and maybe some parent nodes in the tree hierarchy.
1146 * @param inode_ref Directory i-node
1147 * @param dx_blocks Array with path from root to leaf node
1148 * @param dx_block Leaf block to be split if needed
1149 * @return Error code
1152 ext4_dir_dx_split_index(struct ext4_inode_ref *inode_ref,
1153 struct ext4_dir_idx_block *dx_blocks,
1154 struct ext4_dir_idx_block *dx_block,
1155 struct ext4_dir_idx_block **new_dx_block)
1157 struct ext4_sblock *sb = &inode_ref->fs->sb;
1158 struct ext4_dir_idx_entry *entries;
1160 if (dx_block == dx_blocks)
1162 ((struct ext4_dir_idx_root *)dx_block->block.data)
1166 ((struct ext4_dir_idx_node *)dx_block->block.data)
1169 struct ext4_dir_idx_countlimit *countlimit =
1170 (struct ext4_dir_idx_countlimit *)entries;
1172 uint16_t leaf_limit = ext4_dir_dx_countlimit_get_limit(countlimit);
1173 uint16_t leaf_count = ext4_dir_dx_countlimit_get_count(countlimit);
1175 /* Check if is necessary to split index block */
1176 if (leaf_limit == leaf_count) {
1177 size_t levels = dx_block - dx_blocks;
1179 struct ext4_dir_idx_entry *root_entries =
1180 ((struct ext4_dir_idx_root *)dx_blocks[0].block.data)
1183 struct ext4_dir_idx_countlimit *root_countlimit =
1184 (struct ext4_dir_idx_countlimit *)root_entries;
1185 uint16_t root_limit =
1186 ext4_dir_dx_countlimit_get_limit(root_countlimit);
1187 uint16_t root_count =
1188 ext4_dir_dx_countlimit_get_count(root_countlimit);
1190 /* Linux limitation */
1191 if ((levels > 0) && (root_limit == root_count))
1194 /* Add new block to directory */
1195 ext4_fsblk_t new_fblock;
1196 uint32_t new_iblock;
1197 int rc = ext4_fs_append_inode_block(inode_ref, &new_fblock,
1202 /* load new block */
1203 struct ext4_block new_block;
1205 ext4_block_get_noread(inode_ref->fs->bdev,
1206 &new_block, new_fblock);
1210 struct ext4_dir_idx_node *new_node =
1211 (void *)new_block.data;
1212 struct ext4_dir_idx_entry *new_entries = new_node->entries;
1214 memset(&new_node->fake, 0,
1215 sizeof(struct ext4_fake_dir_entry));
1217 uint32_t block_size =
1218 ext4_sb_get_block_size(&inode_ref->fs->sb);
1220 new_node->fake.entry_length = block_size;
1222 /* Split leaf node */
1224 uint32_t count_left = leaf_count / 2;
1225 uint32_t count_right = leaf_count - count_left;
1226 uint32_t hash_right =
1227 ext4_dir_dx_entry_get_hash(entries + count_left);
1229 /* Copy data to new node */
1230 memcpy((void *)new_entries,
1231 (void *)(entries + count_left),
1233 sizeof(struct ext4_dir_idx_entry));
1235 /* Initialize new node */
1236 struct ext4_dir_idx_countlimit *left_countlimit =
1237 (struct ext4_dir_idx_countlimit *)entries;
1238 struct ext4_dir_idx_countlimit *right_countlimit =
1239 (struct ext4_dir_idx_countlimit *)new_entries;
1241 ext4_dir_dx_countlimit_set_count(left_countlimit,
1243 ext4_dir_dx_countlimit_set_count(right_countlimit,
1246 uint32_t entry_space =
1248 sizeof(struct ext4_fake_dir_entry);
1249 if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM))
1250 entry_space -= sizeof(struct ext4_dir_idx_tail);
1252 uint32_t node_limit =
1253 entry_space / sizeof(struct ext4_dir_idx_entry);
1255 ext4_dir_dx_countlimit_set_limit(right_countlimit,
1258 /* Which index block is target for new entry */
1259 uint32_t position_index =
1260 (dx_block->position - dx_block->entries);
1261 if (position_index >= count_left) {
1262 ext4_dir_set_dx_checksum(
1264 (struct ext4_dir_entry_ll *)
1265 dx_block->block.data);
1266 dx_block->block.dirty = true;
1268 struct ext4_block block_tmp = dx_block->block;
1270 dx_block->block = new_block;
1272 dx_block->position =
1273 new_entries + position_index - count_left;
1274 dx_block->entries = new_entries;
1276 new_block = block_tmp;
1279 /* Finally insert new entry */
1280 ext4_dir_dx_insert_entry(inode_ref,
1281 dx_blocks, hash_right,
1283 ext4_dir_set_dx_checksum(inode_ref,
1284 (struct ext4_dir_entry_ll *)
1285 dx_blocks[0].block.data);
1286 ext4_dir_set_dx_checksum(inode_ref,
1287 (struct ext4_dir_entry_ll *)
1288 dx_blocks[1].block.data);
1289 dx_blocks[0].block.dirty = true;
1290 dx_blocks[1].block.dirty = true;
1292 ext4_dir_set_dx_checksum(inode_ref,
1293 (struct ext4_dir_entry_ll *)
1295 new_block.dirty = true;
1296 return ext4_block_set(inode_ref->fs->bdev, &new_block);
1298 /* Create second level index */
1300 /* Copy data from root to child block */
1301 memcpy((void *)new_entries, (void *)entries,
1303 sizeof(struct ext4_dir_idx_entry));
1305 struct ext4_dir_idx_countlimit *new_countlimit =
1306 (struct ext4_dir_idx_countlimit *)new_entries;
1308 uint32_t entry_space =
1310 sizeof(struct ext4_fake_dir_entry);
1311 if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM))
1312 entry_space -= sizeof(struct ext4_dir_idx_tail);
1314 uint32_t node_limit =
1315 entry_space / sizeof(struct ext4_dir_idx_entry);
1316 ext4_dir_dx_countlimit_set_limit(new_countlimit,
1319 /* Set values in root node */
1320 struct ext4_dir_idx_countlimit
1321 *new_root_countlimit =
1322 (struct ext4_dir_idx_countlimit *)entries;
1324 ext4_dir_dx_countlimit_set_count(new_root_countlimit,
1326 ext4_dir_dx_entry_set_block(entries, new_iblock);
1328 ((struct ext4_dir_idx_root *)dx_blocks[0]
1330 ->info.indirect_levels = 1;
1332 /* Add new entry to the path */
1333 dx_block = dx_blocks + 1;
1334 dx_block->position =
1335 dx_blocks->position - entries + new_entries;
1336 dx_block->entries = new_entries;
1337 dx_block->block = new_block;
1339 *new_dx_block = dx_block;
1341 ext4_dir_set_dx_checksum(inode_ref,
1342 (struct ext4_dir_entry_ll *)
1343 dx_blocks[0].block.data);
1344 ext4_dir_set_dx_checksum(inode_ref,
1345 (struct ext4_dir_entry_ll *)
1346 dx_blocks[1].block.data);
1347 dx_blocks[0].block.dirty = true;
1348 dx_blocks[1].block.dirty = true;
1355 int ext4_dir_dx_add_entry(struct ext4_inode_ref *parent,
1356 struct ext4_inode_ref *child, const char *name)
1360 /* Get direct block 0 (index root) */
1361 ext4_fsblk_t root_block_addr;
1363 ext4_fs_get_inode_data_block_index(parent,
1364 0, &root_block_addr,
1369 struct ext4_fs *fs = parent->fs;
1370 struct ext4_block root_block;
1372 rc = ext4_block_get(fs->bdev, &root_block, root_block_addr);
1376 if (!ext4_dir_dx_checksum_verify(parent,
1377 (struct ext4_dir_entry_ll *)root_block.data)) {
1378 ext4_dbg(DEBUG_DIR_IDX,
1379 DBG_WARN "HTree root checksum failed."
1380 "Inode: %" PRIu32", "
1381 "Block: %" PRIu32"\n",
1386 /* Initialize hinfo structure (mainly compute hash) */
1387 uint32_t name_len = strlen(name);
1388 struct ext4_hash_info hinfo;
1389 rc = ext4_dir_hinfo_init(&hinfo, &root_block, &fs->sb, name_len, name);
1391 ext4_block_set(fs->bdev, &root_block);
1392 return EXT4_ERR_BAD_DX_DIR;
1396 * Hardcoded number 2 means maximum height of index
1397 * tree defined in Linux.
1399 struct ext4_dir_idx_block dx_blocks[2];
1400 struct ext4_dir_idx_block *dx_block;
1401 struct ext4_dir_idx_block *dx_it;
1403 rc = ext4_dir_dx_get_leaf(&hinfo, parent, &root_block, &dx_block,
1406 rc = EXT4_ERR_BAD_DX_DIR;
1410 /* Try to insert to existing data block */
1411 uint32_t leaf_block_idx =
1412 ext4_dir_dx_entry_get_block(dx_block->position);
1413 ext4_fsblk_t leaf_block_addr;
1414 rc = ext4_fs_get_inode_data_block_index(parent, leaf_block_idx,
1421 * Check if there is needed to split index node
1422 * (and recursively also parent nodes)
1424 rc = ext4_dir_dx_split_index(parent, dx_blocks, dx_block, &dx_block);
1426 goto release_target_index;
1428 struct ext4_block target_block;
1429 rc = ext4_block_get(fs->bdev, &target_block, leaf_block_addr);
1433 if (!ext4_dir_checksum_verify(parent,
1434 (struct ext4_dir_entry_ll *)target_block.data)) {
1435 ext4_dbg(DEBUG_DIR_IDX,
1436 DBG_WARN "HTree leaf block checksum failed."
1437 "Inode: %" PRIu32", "
1438 "Block: %" PRIu32"\n",
1443 /* Check if insert operation passed */
1444 rc = ext4_dir_try_insert_entry(&fs->sb, parent, &target_block, child,
1447 goto release_target_index;
1449 /* Split entries to two blocks (includes sorting by hash value) */
1450 struct ext4_block new_block;
1451 rc = ext4_dir_dx_split_data(parent, &hinfo, &target_block, dx_block,
1455 goto release_target_index;
1458 /* Where to save new entry */
1459 uint32_t new_block_hash =
1460 ext4_dir_dx_entry_get_hash(dx_block->position + 1);
1461 if (hinfo.hash >= new_block_hash)
1462 rc = ext4_dir_try_insert_entry(&fs->sb, parent, &new_block,
1463 child, name, name_len);
1465 rc = ext4_dir_try_insert_entry(&fs->sb, parent, &target_block,
1466 child, name, name_len);
1469 rc = ext4_block_set(fs->bdev, &new_block);
1473 /* Cleanup operations */
1475 release_target_index:
1478 rc = ext4_block_set(fs->bdev, &target_block);
1488 while (dx_it <= dx_block) {
1489 rc = ext4_block_set(fs->bdev, &dx_it->block);
1499 int ext4_dir_dx_reset_parent_inode(struct ext4_inode_ref *dir,
1500 uint32_t parent_inode)
1502 /* Load block 0, where will be index root located */
1503 ext4_fsblk_t fblock;
1504 int rc = ext4_fs_get_inode_data_block_index(dir, 0, &fblock, false);
1508 struct ext4_block block;
1509 rc = ext4_block_get(dir->fs->bdev, &block, fblock);
1513 if (!ext4_dir_dx_checksum_verify(dir,
1514 (struct ext4_dir_entry_ll *)block.data)) {
1515 ext4_dbg(DEBUG_DIR_IDX,
1516 DBG_WARN "HTree root checksum failed."
1517 "Inode: %" PRIu32", "
1518 "Block: %" PRIu32"\n",
1523 /* Initialize pointers to data structures */
1524 struct ext4_dir_idx_root *root = (void *)block.data;
1526 /* Fill the inode field with a new parent ino. */
1527 ext4_dx_dot_entry_set_inode(&root->dots[1], parent_inode);
1529 ext4_dir_set_dx_checksum(dir,
1530 (struct ext4_dir_entry_ll *)
1534 return ext4_block_set(dir->fs->bdev, &block);