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
55 ext4_dir_dx_rinfo_get_hash_version(struct ext4_dir_idx_rinfo *ri)
57 return ri->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
65 ext4_dir_dx_rinfo_set_hash_version(struct ext4_dir_idx_rinfo *ri, uint8_t 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
75 ext4_dir_dx_rinfo_get_info_length(struct ext4_dir_idx_rinfo *ri)
77 return ri->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
85 ext4_dir_dx_root_info_set_info_length(struct ext4_dir_idx_rinfo *ri,
88 ri->info_length = len;
91 /**@brief Get number of indirect levels of HTree.
92 * @param root_info Pointer to root info structure of index
93 * @return Height of HTree (actually only 0 or 1)
96 ext4_dir_dx_rinfo_get_indirect_levels(struct ext4_dir_idx_rinfo *ri)
98 return ri->indirect_levels;
101 /**@brief Set number of indirect levels of HTree.
102 * @param root_info Pointer to root info structure of index
103 * @param lvl Height of HTree (actually only 0 or 1)
106 ext4_dir_dx_rinfo_set_indirect_levels(struct ext4_dir_idx_rinfo *ri, uint8_t l)
108 ri->indirect_levels = l;
111 /**@brief Get maximum number of index node entries.
112 * @param climit Pointer to counlimit structure
113 * @return Maximum of entries in node
115 static inline uint16_t
116 ext4_dir_dx_climit_get_limit(struct ext4_dir_idx_climit *climit)
118 return to_le16(climit->limit);
121 /**@brief Set maximum number of index node entries.
122 * @param climit Pointer to counlimit structure
123 * @param limit Maximum of entries in node
126 ext4_dir_dx_climit_set_limit(struct ext4_dir_idx_climit *climit, uint16_t limit)
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_climit_get_count(struct ext4_dir_idx_climit *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_climit_set_count(struct ext4_dir_idx_climit *climit, uint16_t count)
148 climit->count = to_le16(count);
151 /**@brief Get hash value of index entry.
152 * @param entry Pointer to index entry
155 static inline uint32_t
156 ext4_dir_dx_entry_get_hash(struct ext4_dir_idx_entry *entry)
158 return to_le32(entry->hash);
161 /**@brief Set hash value of index entry.
162 * @param entry Pointer to index entry
163 * @param hash Hash value
166 ext4_dir_dx_entry_set_hash(struct ext4_dir_idx_entry *entry, uint32_t hash)
168 entry->hash = to_le32(hash);
171 /**@brief Get block address where child node is located.
172 * @param entry Pointer to index entry
173 * @return Block address of child node
175 static inline uint32_t
176 ext4_dir_dx_entry_get_block(struct ext4_dir_idx_entry *entry)
178 return to_le32(entry->block);
181 /**@brief Set block address where child node is located.
182 * @param entry Pointer to index entry
183 * @param block Block address of child node
186 ext4_dir_dx_entry_set_block(struct ext4_dir_idx_entry *entry, uint32_t block)
188 entry->block = to_le32(block);
191 /**@brief Sort entry item.*/
192 struct ext4_dx_sort_entry {
198 static int ext4_dir_dx_hash_string(struct ext4_hash_info *hinfo, int len,
201 return ext2_htree_hash(name, len, hinfo->seed, hinfo->hash_version,
202 &hinfo->hash, &hinfo->minor_hash);
205 #if CONFIG_META_CSUM_ENABLE
206 static uint32_t ext4_dir_dx_checksum(struct ext4_inode_ref *inode_ref, void *de,
207 int count_offset, int count,
208 struct ext4_dir_idx_tail *t)
210 uint32_t orig_cum, csum = 0;
211 struct ext4_sblock *sb = &inode_ref->fs->sb;
214 /* Compute the checksum only if the filesystem supports it */
215 if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM)) {
216 uint32_t ino_index = to_le32(inode_ref->index);
218 ino_gen = to_le32(ext4_inode_get_generation(inode_ref->inode));
220 sz = count_offset + (count * sizeof(struct ext4_dir_idx_tail));
221 orig_cum = t->checksum;
223 /* First calculate crc32 checksum against fs uuid */
224 csum = ext4_crc32c(EXT4_CRC32_INIT, sb->uuid, sizeof(sb->uuid));
225 /* Then calculate crc32 checksum against inode number
226 * and inode generation */
227 csum = ext4_crc32c(csum, &ino_index, sizeof(ino_index));
228 csum = ext4_crc32c(csum, &ino_gen, sizeof(ino_gen));
229 /* After that calculate crc32 checksum against all the dx_entry */
230 csum = ext4_crc32c(csum, de, sz);
231 /* Finally calculate crc32 checksum for dx_tail */
232 csum = ext4_crc32c(csum, t, sizeof(struct ext4_dir_idx_tail));
233 t->checksum = orig_cum;
238 static struct ext4_dir_idx_climit *
239 ext4_dir_dx_get_climit(struct ext4_inode_ref *inode_ref,
240 struct ext4_dir_en *dirent, int *offset)
242 struct ext4_dir_en *dp;
243 struct ext4_dir_idx_root *root;
244 struct ext4_sblock *sb = &inode_ref->fs->sb;
245 uint32_t block_size = ext4_sb_get_block_size(sb);
246 uint16_t entry_len = ext4_dir_en_get_entry_len(dirent);
250 if (entry_len == 12) {
251 root = (struct ext4_dir_idx_root *)dirent;
252 dp = (struct ext4_dir_en *)&root->dots[1];
253 if (ext4_dir_en_get_entry_len(dp) != (block_size - 12))
255 if (root->info.reserved_zero)
257 if (root->info.info_length != sizeof(struct ext4_dir_idx_rinfo))
260 } else if (entry_len == block_size) {
267 *offset = count_offset;
268 return (struct ext4_dir_idx_climit *)(((char *)dirent) + count_offset);
273 * Currently we do not verify the checksum of HTree node.
275 static bool ext4_dir_dx_csum_verify(struct ext4_inode_ref *inode_ref,
276 struct ext4_dir_en *de)
278 struct ext4_sblock *sb = &inode_ref->fs->sb;
279 uint32_t block_size = ext4_sb_get_block_size(sb);
280 int coff, limit, cnt;
282 if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM)) {
283 struct ext4_dir_idx_climit *climit;
284 climit = ext4_dir_dx_get_climit(inode_ref, de, &coff);
286 /* Directory seems corrupted. */
289 struct ext4_dir_idx_tail *t;
290 limit = ext4_dir_dx_climit_get_limit(climit);
291 cnt = ext4_dir_dx_climit_get_count(climit);
292 if (coff + (limit * sizeof(struct ext4_dir_idx_entry)) >
293 (block_size - sizeof(struct ext4_dir_idx_tail))) {
294 /* There is no space to hold the checksum */
297 t = (void *)(((struct ext4_dir_idx_entry *)climit) + limit);
300 c = to_le32(ext4_dir_dx_checksum(inode_ref, de, coff, cnt, t));
301 if (t->checksum != c)
308 static void ext4_dir_set_dx_csum(struct ext4_inode_ref *inode_ref,
309 struct ext4_dir_en *dirent)
311 int coff, limit, count;
312 struct ext4_sblock *sb = &inode_ref->fs->sb;
313 uint32_t block_size = ext4_sb_get_block_size(sb);
315 if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM)) {
316 struct ext4_dir_idx_climit *climit;
317 climit = ext4_dir_dx_get_climit(inode_ref, dirent, &coff);
319 /* Directory seems corrupted. */
322 struct ext4_dir_idx_tail *t;
323 limit = ext4_dir_dx_climit_get_limit(climit);
324 count = ext4_dir_dx_climit_get_count(climit);
325 if (coff + (limit * sizeof(struct ext4_dir_idx_entry)) >
326 (block_size - sizeof(struct ext4_dir_idx_tail))) {
327 /* There is no space to hold the checksum */
331 t = (void *)(((struct ext4_dir_idx_entry *)climit) + limit);
332 t->checksum = to_le32(ext4_dir_dx_checksum(inode_ref, dirent,
337 #define ext4_dir_dx_csum_verify(...) true
338 #define ext4_dir_set_dx_csum(...)
341 /****************************************************************************/
343 int ext4_dir_dx_init(struct ext4_inode_ref *dir, struct ext4_inode_ref *parent)
345 /* Load block 0, where will be index root located */
348 struct ext4_sblock *sb = &dir->fs->sb;
349 uint32_t block_size = ext4_sb_get_block_size(&dir->fs->sb);
351 int rc = ext4_fs_append_inode_block(dir, &fblock, &iblock);
355 struct ext4_block block;
356 rc = ext4_block_get_noread(dir->fs->bdev, &block, fblock);
360 /* Initialize pointers to data structures */
361 struct ext4_dir_idx_root *root = (void *)block.data;
362 struct ext4_dir_idx_rinfo *info = &(root->info);
364 memset(root, 0, sizeof(struct ext4_dir_idx_root));
365 struct ext4_dir_en *de;
367 /* Initialize dot entries */
368 de = (struct ext4_dir_en *)root->dots;
369 ext4_dir_write_entry(sb, de, 12, dir, ".", strlen("."));
371 de = (struct ext4_dir_en *)(root->dots + 1);
372 uint16_t elen = block_size - 12;
373 ext4_dir_write_entry(sb, de, elen, parent, "..", strlen(".."));
375 /* Initialize root info structure */
376 uint8_t hash_version = ext4_get8(&dir->fs->sb, default_hash_version);
378 ext4_dir_dx_rinfo_set_hash_version(info, hash_version);
379 ext4_dir_dx_rinfo_set_indirect_levels(info, 0);
380 ext4_dir_dx_root_info_set_info_length(info, 8);
382 /* Set limit and current number of entries */
383 struct ext4_dir_idx_climit *climit;
384 climit = (struct ext4_dir_idx_climit *)&root->en;
386 ext4_dir_dx_climit_set_count(climit, 1);
388 uint32_t entry_space;
389 entry_space = block_size - 2 * sizeof(struct ext4_dir_idx_dot_en) -
390 sizeof(struct ext4_dir_idx_rinfo);
392 if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM))
393 entry_space -= sizeof(struct ext4_dir_idx_tail);
395 uint16_t root_limit = entry_space / sizeof(struct ext4_dir_idx_entry);
396 ext4_dir_dx_climit_set_limit(climit, root_limit);
398 /* Append new block, where will be new entries inserted in the future */
399 rc = ext4_fs_append_inode_block(dir, &fblock, &iblock);
401 ext4_block_set(dir->fs->bdev, &block);
405 struct ext4_block new_block;
406 rc = ext4_block_get_noread(dir->fs->bdev, &new_block, fblock);
408 ext4_block_set(dir->fs->bdev, &block);
412 /* Fill the whole block with empty entry */
413 struct ext4_dir_en *be = (void *)new_block.data;
415 if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM)) {
416 uint16_t len = block_size - sizeof(struct ext4_dir_entry_tail);
417 ext4_dir_en_set_entry_len(be, len);
418 ext4_dir_en_set_name_len(sb, be, 0);
419 ext4_dir_en_set_inode_type(sb, be, EXT4_DE_UNKNOWN);
420 ext4_dir_init_entry_tail(EXT4_DIRENT_TAIL(be, block_size));
421 ext4_dir_set_csum(dir, be);
423 ext4_dir_en_set_entry_len(be, block_size);
426 ext4_dir_en_set_inode(be, 0);
428 new_block.dirty = true;
429 rc = ext4_block_set(dir->fs->bdev, &new_block);
431 ext4_block_set(dir->fs->bdev, &block);
435 /* Connect new block to the only entry in index */
436 struct ext4_dir_idx_entry *entry = root->en;
437 ext4_dir_dx_entry_set_block(entry, iblock);
439 ext4_dir_set_dx_csum(dir, (struct ext4_dir_en *)block.data);
442 return ext4_block_set(dir->fs->bdev, &block);
445 /**@brief Initialize hash info structure necessary for index operations.
446 * @param hinfo Pointer to hinfo to be initialized
447 * @param root_block Root block (number 0) of index
448 * @param sb Pointer to superblock
449 * @param name_len Length of name to be computed hash value from
450 * @param name Name to be computed hash value from
451 * @return Standard error code
453 static int ext4_dir_hinfo_init(struct ext4_hash_info *hinfo,
454 struct ext4_block *root_block,
455 struct ext4_sblock *sb, size_t name_len,
458 struct ext4_dir_idx_root *root;
460 root = (struct ext4_dir_idx_root *)root_block->data;
461 if ((root->info.hash_version != EXT2_HTREE_LEGACY) &&
462 (root->info.hash_version != EXT2_HTREE_HALF_MD4) &&
463 (root->info.hash_version != EXT2_HTREE_TEA))
464 return EXT4_ERR_BAD_DX_DIR;
466 /* Check unused flags */
467 if (root->info.unused_flags != 0)
468 return EXT4_ERR_BAD_DX_DIR;
470 /* Check indirect levels */
471 if (root->info.indirect_levels > 1)
472 return EXT4_ERR_BAD_DX_DIR;
474 /* Check if node limit is correct */
475 uint32_t block_size = ext4_sb_get_block_size(sb);
476 uint32_t entry_space = block_size;
477 entry_space -= 2 * sizeof(struct ext4_dir_idx_dot_en);
478 entry_space -= sizeof(struct ext4_dir_idx_rinfo);
479 if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM))
480 entry_space -= sizeof(struct ext4_dir_idx_tail);
481 entry_space = entry_space / sizeof(struct ext4_dir_idx_entry);
483 struct ext4_dir_idx_climit *climit = (void *)&root->en;
484 uint16_t limit = ext4_dir_dx_climit_get_limit(climit);
485 if (limit != entry_space)
486 return EXT4_ERR_BAD_DX_DIR;
488 /* Check hash version and modify if necessary */
489 hinfo->hash_version = ext4_dir_dx_rinfo_get_hash_version(&root->info);
490 if ((hinfo->hash_version <= EXT2_HTREE_TEA) &&
491 (ext4_sb_check_flag(sb, EXT4_SUPERBLOCK_FLAGS_UNSIGNED_HASH))) {
492 /* Use unsigned hash */
493 hinfo->hash_version += 3;
496 /* Load hash seed from superblock */
497 hinfo->seed = ext4_get8(sb, hash_seed);
499 /* Compute hash value of name */
501 return ext4_dir_dx_hash_string(hinfo, name_len, name);
506 /**@brief Walk through index tree and load leaf with corresponding hash value.
507 * @param hinfo Initialized hash info structure
508 * @param inode_ref Current i-node
509 * @param root_block Root block (iblock 0), where is root node located
510 * @param dx_block Pointer to leaf node in dx_blocks array
511 * @param dx_blocks Array with the whole path from root to leaf
512 * @return Standard error code
514 static int ext4_dir_dx_get_leaf(struct ext4_hash_info *hinfo,
515 struct ext4_inode_ref *inode_ref,
516 struct ext4_block *root_block,
517 struct ext4_dir_idx_block **dx_block,
518 struct ext4_dir_idx_block *dx_blocks)
520 struct ext4_dir_idx_root *root;
521 struct ext4_dir_idx_entry *entries;
522 struct ext4_dir_idx_entry *p;
523 struct ext4_dir_idx_entry *q;
524 struct ext4_dir_idx_entry *m;
525 struct ext4_dir_idx_entry *at;
529 uint16_t entry_space;
533 struct ext4_dir_idx_block *tmp_dx_blk = dx_blocks;
534 struct ext4_block *tmp_blk = root_block;
535 struct ext4_sblock *sb = &inode_ref->fs->sb;
537 block_size = ext4_sb_get_block_size(sb);
538 root = (struct ext4_dir_idx_root *)root_block->data;
539 entries = (struct ext4_dir_idx_entry *)&root->en;
540 limit = ext4_dir_dx_climit_get_limit((void *)entries);
541 ind_level = ext4_dir_dx_rinfo_get_indirect_levels(&root->info);
543 /* Walk through the index tree */
545 uint16_t cnt = ext4_dir_dx_climit_get_count((void *)entries);
546 if ((cnt == 0) || (cnt > limit))
547 return EXT4_ERR_BAD_DX_DIR;
549 /* Do binary search in every node */
551 q = entries + cnt - 1;
555 if (ext4_dir_dx_entry_get_hash(m) > hinfo->hash)
564 memcpy(&tmp_dx_blk->b, tmp_blk, sizeof(struct ext4_block));
565 tmp_dx_blk->entries = entries;
566 tmp_dx_blk->position = at;
568 /* Is algorithm in the leaf? */
569 if (ind_level == 0) {
570 *dx_block = tmp_dx_blk;
574 /* Goto child node */
575 uint32_t next_block = ext4_dir_dx_entry_get_block(at);
579 r = ext4_fs_get_inode_data_block_index(inode_ref, next_block,
584 r = ext4_block_get(inode_ref->fs->bdev, tmp_blk, fblock);
588 entries = ((struct ext4_dir_idx_node *)tmp_blk->data)->entries;
589 limit = ext4_dir_dx_climit_get_limit((void *)entries);
591 entry_space = block_size - sizeof(struct ext4_fake_dir_entry);
592 if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM))
593 entry_space -= sizeof(struct ext4_dir_idx_tail);
595 entry_space = entry_space / sizeof(struct ext4_dir_idx_entry);
597 if (limit != entry_space) {
598 ext4_block_set(inode_ref->fs->bdev, tmp_blk);
599 return EXT4_ERR_BAD_DX_DIR;
602 if (!ext4_dir_dx_csum_verify(inode_ref, (void *)tmp_blk->data)) {
603 ext4_dbg(DEBUG_DIR_IDX,
604 DBG_WARN "HTree checksum failed."
605 "Inode: %" PRIu32", "
606 "Block: %" PRIu32"\n",
618 /**@brief Check if the the next block would be checked during entry search.
619 * @param inode_ref Directory i-node
620 * @param hash Hash value to check
621 * @param dx_block Current block
622 * @param dx_blocks Array with path from root to leaf node
623 * @return Standard Error code
625 static int ext4_dir_dx_next_block(struct ext4_inode_ref *inode_ref,
627 struct ext4_dir_idx_block *dx_block,
628 struct ext4_dir_idx_block *dx_blocks)
631 uint32_t num_handles = 0;
632 ext4_fsblk_t block_addr;
633 struct ext4_dir_idx_block *p = dx_block;
635 /* Try to find data block with next bunch of entries */
637 uint16_t cnt = ext4_dir_dx_climit_get_count((void *)p->entries);
640 if (p->position < p->entries + cnt)
650 /* Check hash collision (if not occurred - no next block cannot be
652 uint32_t current_hash = ext4_dir_dx_entry_get_hash(p->position);
653 if ((hash & 1) == 0) {
654 if ((current_hash & ~1) != hash)
659 while (num_handles--) {
660 uint32_t block_idx = ext4_dir_dx_entry_get_block(p->position);
662 r = ext4_fs_get_inode_data_block_index(inode_ref, block_idx,
668 r = ext4_block_get(inode_ref->fs->bdev, &b, block_addr);
672 if (!ext4_dir_dx_csum_verify(inode_ref, (void *)b.data)) {
673 ext4_dbg(DEBUG_DIR_IDX,
674 DBG_WARN "HTree checksum failed."
675 "Inode: %" PRIu32", "
676 "Block: %" PRIu32"\n",
683 /* Don't forget to put old block (prevent memory leak) */
684 r = ext4_block_set(inode_ref->fs->bdev, &p->b);
688 memcpy(&p->b, &b, sizeof(b));
689 p->entries = ((struct ext4_dir_idx_node *)b.data)->entries;
690 p->position = p->entries;
696 int ext4_dir_dx_find_entry(struct ext4_dir_search_result *result,
697 struct ext4_inode_ref *inode_ref, size_t name_len,
700 /* Load direct block 0 (index root) */
701 ext4_fsblk_t root_block_addr;
704 rc = ext4_fs_get_inode_data_block_index(inode_ref, 0, &root_block_addr,
709 struct ext4_fs *fs = inode_ref->fs;
711 struct ext4_block root_block;
712 rc = ext4_block_get(fs->bdev, &root_block, root_block_addr);
716 if (!ext4_dir_dx_csum_verify(inode_ref, (void *)root_block.data)) {
717 ext4_dbg(DEBUG_DIR_IDX,
718 DBG_WARN "HTree root checksum failed."
719 "Inode: %" PRIu32", "
720 "Block: %" PRIu32"\n",
725 /* Initialize hash info (compute hash value) */
726 struct ext4_hash_info hinfo;
727 rc = ext4_dir_hinfo_init(&hinfo, &root_block, &fs->sb, name_len, name);
729 ext4_block_set(fs->bdev, &root_block);
730 return EXT4_ERR_BAD_DX_DIR;
734 * Hardcoded number 2 means maximum height of index tree,
735 * specified in the Linux driver.
737 struct ext4_dir_idx_block dx_blocks[2];
738 struct ext4_dir_idx_block *dx_block;
739 struct ext4_dir_idx_block *tmp;
741 rc = ext4_dir_dx_get_leaf(&hinfo, inode_ref, &root_block, &dx_block,
744 ext4_block_set(fs->bdev, &root_block);
745 return EXT4_ERR_BAD_DX_DIR;
749 /* Load leaf block */
750 uint32_t leaf_blk_idx;
751 ext4_fsblk_t leaf_block_addr;
754 leaf_blk_idx = ext4_dir_dx_entry_get_block(dx_block->position);
755 rc = ext4_fs_get_inode_data_block_index(inode_ref, leaf_blk_idx,
756 &leaf_block_addr, false);
760 rc = ext4_block_get(fs->bdev, &b, leaf_block_addr);
764 if (!ext4_dir_csum_verify(inode_ref, (void *)b.data)) {
765 ext4_dbg(DEBUG_DIR_IDX,
766 DBG_WARN "HTree leaf block checksum failed."
767 "Inode: %" PRIu32", "
768 "Block: %" PRIu32"\n",
773 /* Linear search inside block */
774 struct ext4_dir_en *de;
775 rc = ext4_dir_find_in_block(&b, &fs->sb, name_len, name, &de);
777 /* Found => return it */
784 /* Not found, leave untouched */
785 rc2 = ext4_block_set(fs->bdev, &b);
792 /* check if the next block could be checked */
793 rc = ext4_dir_dx_next_block(inode_ref, hinfo.hash, dx_block,
797 } while (rc == ENOENT);
799 /* Entry not found */
803 /* The whole path must be released (preventing memory leak) */
806 while (tmp <= dx_block) {
807 rc2 = ext4_block_set(fs->bdev, &tmp->b);
808 if (rc == EOK && rc2 != EOK)
816 #if CONFIG_DIR_INDEX_COMB_SORT
817 #define SWAP_ENTRY(se1, se2) \
819 struct ext4_dx_sort_entry tmp = se1; \
825 static void comb_sort(struct ext4_dx_sort_entry *se, uint32_t count)
827 struct ext4_dx_sort_entry *p, *q, *top = se + count - 1;
831 count = (count * 10) / 13;
834 for (p = top, q = p - count; q >= se; p--, q--)
835 if (p->hash < q->hash)
843 if (q[1].hash >= q[0].hash)
845 SWAP_ENTRY(*(q + 1), *q);
852 /**@brief Compare function used to pass in quicksort implementation.
853 * It can compare two entries by hash value.
854 * @param arg1 First entry
855 * @param arg2 Second entry
856 * @param dummy Unused parameter, can be NULL
858 * @return Classic compare result
859 * (0: equal, -1: arg1 < arg2, 1: arg1 > arg2)
861 static int ext4_dir_dx_entry_comparator(const void *arg1, const void *arg2)
863 struct ext4_dx_sort_entry *entry1 = (void *)arg1;
864 struct ext4_dx_sort_entry *entry2 = (void *)arg2;
866 if (entry1->hash == entry2->hash)
869 if (entry1->hash < entry2->hash)
876 /**@brief Insert new index entry to block.
877 * Note that space for new entry must be checked by caller.
878 * @param inode_ref Directory i-node
879 * @param index_block Block where to insert new entry
880 * @param hash Hash value covered by child node
881 * @param iblock Logical number of child block
885 ext4_dir_dx_insert_entry(struct ext4_inode_ref *inode_ref __unused,
886 struct ext4_dir_idx_block *index_block,
887 uint32_t hash, uint32_t iblock)
889 struct ext4_dir_idx_entry *old_index_entry = index_block->position;
890 struct ext4_dir_idx_entry *new_index_entry = old_index_entry + 1;
891 struct ext4_dir_idx_climit *climit = (void *)index_block->entries;
892 struct ext4_dir_idx_entry *start_index = index_block->entries;
893 uint32_t count = ext4_dir_dx_climit_get_count(climit);
896 bytes = (uint8_t *)(start_index + count) - (uint8_t *)(new_index_entry);
898 memmove(new_index_entry + 1, new_index_entry, bytes);
900 ext4_dir_dx_entry_set_block(new_index_entry, iblock);
901 ext4_dir_dx_entry_set_hash(new_index_entry, hash);
902 ext4_dir_dx_climit_set_count(climit, count + 1);
903 ext4_dir_set_dx_csum(inode_ref, (void *)index_block->b.data);
904 index_block->b.dirty = true;
907 /**@brief Split directory entries to two parts preventing node overflow.
908 * @param inode_ref Directory i-node
909 * @param hinfo Hash info
910 * @param old_data_block Block with data to be split
911 * @param index_block Block where index entries are located
912 * @param new_data_block Output value for newly allocated data block
914 static int ext4_dir_dx_split_data(struct ext4_inode_ref *inode_ref,
915 struct ext4_hash_info *hinfo,
916 struct ext4_block *old_data_block,
917 struct ext4_dir_idx_block *index_block,
918 struct ext4_block *new_data_block)
921 struct ext4_sblock *sb = &inode_ref->fs->sb;
922 uint32_t block_size = ext4_sb_get_block_size(&inode_ref->fs->sb);
924 /* Allocate buffer for directory entries */
925 uint8_t *entry_buffer = malloc(block_size);
926 if (entry_buffer == NULL)
929 /* dot entry has the smallest size available */
930 uint32_t max_ecnt = block_size / sizeof(struct ext4_dir_idx_dot_en);
932 /* Allocate sort entry */
933 struct ext4_dx_sort_entry *sort;
935 sort = malloc(max_ecnt * sizeof(struct ext4_dx_sort_entry));
942 uint32_t real_size = 0;
944 /* Initialize hinfo */
945 struct ext4_hash_info hinfo_tmp;
946 memcpy(&hinfo_tmp, hinfo, sizeof(struct ext4_hash_info));
948 /* Load all valid entries to the buffer */
949 struct ext4_dir_en *de = (void *)old_data_block->data;
950 uint8_t *entry_buffer_ptr = entry_buffer;
951 while ((void *)de < (void *)(old_data_block->data + block_size)) {
952 /* Read only valid entries */
953 if (ext4_dir_en_get_inode(de) && de->name_len) {
954 uint8_t len = ext4_dir_en_get_name_len(sb, de);
955 rc = ext4_dir_dx_hash_string(&hinfo_tmp, len,
963 uint32_t rec_len = 8 + len;
964 if ((rec_len % 4) != 0)
965 rec_len += 4 - (rec_len % 4);
967 memcpy(entry_buffer_ptr, de, rec_len);
969 sort[idx].dentry = entry_buffer_ptr;
970 sort[idx].rec_len = rec_len;
971 sort[idx].hash = hinfo_tmp.hash;
973 entry_buffer_ptr += rec_len;
974 real_size += rec_len;
978 size_t elen = ext4_dir_en_get_entry_len(de);
979 de = (void *)((uint8_t *)de + elen);
982 /* Sort all entries */
983 #if CONFIG_DIR_INDEX_COMB_SORT
984 comb_sort(sort, idx);
986 qsort(sort, idx, sizeof(struct ext4_dx_sort_entry),
987 ext4_dir_dx_entry_comparator);
989 /* Allocate new block for store the second part of entries */
990 ext4_fsblk_t new_fblock;
992 rc = ext4_fs_append_inode_block(inode_ref, &new_fblock, &new_iblock);
1000 struct ext4_block new_data_block_tmp;
1001 rc = ext4_block_get_noread(inode_ref->fs->bdev, &new_data_block_tmp,
1010 * Distribute entries to two blocks (by size)
1011 * - compute the half
1013 uint32_t new_hash = 0;
1014 uint32_t current_size = 0;
1017 for (i = 0; i < idx; ++i) {
1018 if ((current_size + sort[i].rec_len) > (block_size / 2)) {
1019 new_hash = sort[i].hash;
1024 current_size += sort[i].rec_len;
1027 /* Check hash collision */
1028 uint32_t continued = 0;
1029 if (new_hash == sort[mid - 1].hash)
1034 if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM))
1035 block_size -= sizeof(struct ext4_dir_entry_tail);
1037 /* First part - to the old block */
1038 for (i = 0; i < mid; ++i) {
1039 ptr = old_data_block->data + off;
1040 memcpy(ptr, sort[i].dentry, sort[i].rec_len);
1042 struct ext4_dir_en *t = ptr;
1044 ext4_dir_en_set_entry_len(t, sort[i].rec_len);
1046 ext4_dir_en_set_entry_len(t, block_size - off);
1048 off += sort[i].rec_len;
1051 /* Second part - to the new block */
1053 for (i = mid; i < idx; ++i) {
1054 ptr = new_data_block_tmp.data + off;
1055 memcpy(ptr, sort[i].dentry, sort[i].rec_len);
1057 struct ext4_dir_en *t = ptr;
1059 ext4_dir_en_set_entry_len(t, sort[i].rec_len);
1061 ext4_dir_en_set_entry_len(t, block_size - off);
1063 off += sort[i].rec_len;
1066 block_size = ext4_sb_get_block_size(&inode_ref->fs->sb);
1068 /* Do some steps to finish operation */
1069 sb = &inode_ref->fs->sb;
1070 if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM)) {
1071 struct ext4_dir_entry_tail *t;
1073 t = EXT4_DIRENT_TAIL(old_data_block->data, block_size);
1074 ext4_dir_init_entry_tail(t);
1075 t = EXT4_DIRENT_TAIL(new_data_block_tmp.data, block_size);
1076 ext4_dir_init_entry_tail(t);
1078 ext4_dir_set_csum(inode_ref, (void *)old_data_block->data);
1079 ext4_dir_set_csum(inode_ref, (void *)new_data_block_tmp.data);
1080 old_data_block->dirty = true;
1081 new_data_block_tmp.dirty = true;
1086 ext4_dir_dx_insert_entry(inode_ref, index_block, new_hash + continued,
1089 *new_data_block = new_data_block_tmp;
1093 /**@brief Split index node and maybe some parent nodes in the tree hierarchy.
1094 * @param inode_ref Directory i-node
1095 * @param dx_blocks Array with path from root to leaf node
1096 * @param dx_block Leaf block to be split if needed
1097 * @return Error code
1100 ext4_dir_dx_split_index(struct ext4_inode_ref *ino_ref,
1101 struct ext4_dir_idx_block *dx_blks,
1102 struct ext4_dir_idx_block *dxb,
1103 struct ext4_dir_idx_block **new_dx_block)
1105 struct ext4_sblock *sb = &ino_ref->fs->sb;
1106 struct ext4_dir_idx_entry *e;
1109 uint32_t block_size = ext4_sb_get_block_size(&ino_ref->fs->sb);
1110 uint32_t entry_space = block_size - sizeof(struct ext4_fake_dir_entry);
1111 uint32_t node_limit = entry_space / sizeof(struct ext4_dir_idx_entry);
1113 bool meta_csum = ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM);
1116 e = ((struct ext4_dir_idx_root *)dxb->b.data)->en;
1118 e = ((struct ext4_dir_idx_node *)dxb->b.data)->entries;
1120 struct ext4_dir_idx_climit *climit = (struct ext4_dir_idx_climit *)e;
1122 uint16_t leaf_limit = ext4_dir_dx_climit_get_limit(climit);
1123 uint16_t leaf_count = ext4_dir_dx_climit_get_count(climit);
1125 /* Check if is necessary to split index block */
1126 if (leaf_limit == leaf_count) {
1127 struct ext4_dir_idx_entry *ren;
1128 ptrdiff_t levels = dxb - dx_blks;
1130 ren = ((struct ext4_dir_idx_root *)dx_blks[0].b.data)->en;
1131 struct ext4_dir_idx_climit *rclimit = (void *)ren;
1132 uint16_t root_limit = ext4_dir_dx_climit_get_limit(rclimit);
1133 uint16_t root_count = ext4_dir_dx_climit_get_count(rclimit);
1136 /* Linux limitation */
1137 if ((levels > 0) && (root_limit == root_count))
1140 /* Add new block to directory */
1141 ext4_fsblk_t new_fblk;
1143 r = ext4_fs_append_inode_block(ino_ref, &new_fblk, &new_iblk);
1147 /* load new block */
1148 struct ext4_block b;
1149 r = ext4_block_get_noread(ino_ref->fs->bdev, &b, new_fblk);
1153 struct ext4_dir_idx_node *new_node = (void *)b.data;
1154 struct ext4_dir_idx_entry *new_en = new_node->entries;
1156 memset(&new_node->fake, 0, sizeof(struct ext4_fake_dir_entry));
1157 new_node->fake.entry_length = block_size;
1159 /* Split leaf node */
1161 uint32_t count_left = leaf_count / 2;
1162 uint32_t count_right = leaf_count - count_left;
1163 uint32_t hash_right;
1166 struct ext4_dir_idx_climit *left_climit;
1167 struct ext4_dir_idx_climit *right_climit;
1169 hash_right = ext4_dir_dx_entry_get_hash(e + count_left);
1170 /* Copy data to new node */
1171 sz = count_right * sizeof(struct ext4_dir_idx_entry);
1172 memcpy(new_en, e + count_left, sz);
1174 /* Initialize new node */
1175 left_climit = (struct ext4_dir_idx_climit *)e;
1176 right_climit = (struct ext4_dir_idx_climit *)new_en;
1178 ext4_dir_dx_climit_set_count(left_climit, count_left);
1179 ext4_dir_dx_climit_set_count(right_climit, count_right);
1182 entry_space -= sizeof(struct ext4_dir_idx_tail);
1184 ext4_dir_dx_climit_set_limit(right_climit, node_limit);
1186 /* Which index block is target for new entry */
1187 uint32_t position_index =
1188 (dxb->position - dxb->entries);
1189 if (position_index >= count_left) {
1190 ext4_dir_set_dx_csum(
1192 (struct ext4_dir_en *)
1194 dxb->b.dirty = true;
1196 struct ext4_block block_tmp = dxb->b;
1201 new_en + position_index - count_left;
1202 dxb->entries = new_en;
1207 /* Finally insert new entry */
1208 ext4_dir_dx_insert_entry(ino_ref, dx_blks, hash_right,
1210 ext4_dir_set_dx_csum(ino_ref, (void *)dx_blks[0].b.data);
1211 ext4_dir_set_dx_csum(ino_ref, (void *)dx_blks[1].b.data);
1212 dx_blks[0].b.dirty = true;
1213 dx_blks[1].b.dirty = true;
1215 ext4_dir_set_dx_csum(ino_ref, (void *)b.data);
1217 return ext4_block_set(ino_ref->fs->bdev, &b);
1220 /* Copy data from root to child block */
1221 sz = leaf_count * sizeof(struct ext4_dir_idx_entry);
1222 memcpy(new_en, e, sz);
1224 struct ext4_dir_idx_climit *new_climit = (void*)new_en;
1226 entry_space -= sizeof(struct ext4_dir_idx_tail);
1228 ext4_dir_dx_climit_set_limit(new_climit, node_limit);
1230 /* Set values in root node */
1231 struct ext4_dir_idx_climit *new_root_climit = (void *)e;
1233 ext4_dir_dx_climit_set_count(new_root_climit, 1);
1234 ext4_dir_dx_entry_set_block(e, new_iblk);
1236 struct ext4_dir_idx_root *r = (void *)dx_blks[0].b.data;
1237 r->info.indirect_levels = 1;
1239 /* Add new entry to the path */
1241 dxb->position = dx_blks->position - e + new_en;
1242 dxb->entries = new_en;
1244 *new_dx_block = dxb;
1246 ext4_dir_set_dx_csum(ino_ref, (void *)dx_blks[0].b.data);
1247 ext4_dir_set_dx_csum(ino_ref, (void *)dx_blks[1].b.data);
1248 dx_blks[0].b.dirty = true;
1249 dx_blks[1].b.dirty = true;
1256 int ext4_dir_dx_add_entry(struct ext4_inode_ref *parent,
1257 struct ext4_inode_ref *child, const char *name)
1261 /* Get direct block 0 (index root) */
1262 ext4_fsblk_t rblock_addr;
1263 r = ext4_fs_get_inode_data_block_index(parent, 0, &rblock_addr, false);
1267 struct ext4_fs *fs = parent->fs;
1268 struct ext4_block root_blk;
1270 r = ext4_block_get(fs->bdev, &root_blk, rblock_addr);
1274 if (!ext4_dir_dx_csum_verify(parent, (void*)root_blk.data)) {
1275 ext4_dbg(DEBUG_DIR_IDX,
1276 DBG_WARN "HTree root checksum failed."
1277 "Inode: %" PRIu32", "
1278 "Block: %" PRIu32"\n",
1283 /* Initialize hinfo structure (mainly compute hash) */
1284 uint32_t name_len = strlen(name);
1285 struct ext4_hash_info hinfo;
1286 r = ext4_dir_hinfo_init(&hinfo, &root_blk, &fs->sb, name_len, name);
1288 ext4_block_set(fs->bdev, &root_blk);
1289 return EXT4_ERR_BAD_DX_DIR;
1293 * Hardcoded number 2 means maximum height of index
1294 * tree defined in Linux.
1296 struct ext4_dir_idx_block dx_blks[2];
1297 struct ext4_dir_idx_block *dx_blk;
1298 struct ext4_dir_idx_block *dx_it;
1300 r = ext4_dir_dx_get_leaf(&hinfo, parent, &root_blk, &dx_blk, dx_blks);
1302 r = EXT4_ERR_BAD_DX_DIR;
1306 /* Try to insert to existing data block */
1307 uint32_t leaf_block_idx = ext4_dir_dx_entry_get_block(dx_blk->position);
1308 ext4_fsblk_t leaf_block_addr;
1309 r = ext4_fs_get_inode_data_block_index(parent, leaf_block_idx,
1310 &leaf_block_addr, false);
1315 * Check if there is needed to split index node
1316 * (and recursively also parent nodes)
1318 r = ext4_dir_dx_split_index(parent, dx_blks, dx_blk, &dx_blk);
1320 goto release_target_index;
1322 struct ext4_block target_block;
1323 r = ext4_block_get(fs->bdev, &target_block, leaf_block_addr);
1327 if (!ext4_dir_csum_verify(parent,(void *)target_block.data)) {
1328 ext4_dbg(DEBUG_DIR_IDX,
1329 DBG_WARN "HTree leaf block checksum failed."
1330 "Inode: %" PRIu32", "
1331 "Block: %" PRIu32"\n",
1336 /* Check if insert operation passed */
1337 r = ext4_dir_try_insert_entry(&fs->sb, parent, &target_block, child,
1340 goto release_target_index;
1342 /* Split entries to two blocks (includes sorting by hash value) */
1343 struct ext4_block new_block;
1344 r = ext4_dir_dx_split_data(parent, &hinfo, &target_block, dx_blk,
1348 goto release_target_index;
1351 /* Where to save new entry */
1352 uint32_t blk_hash = ext4_dir_dx_entry_get_hash(dx_blk->position + 1);
1353 if (hinfo.hash >= blk_hash)
1354 r = ext4_dir_try_insert_entry(&fs->sb, parent, &new_block,
1355 child, name, name_len);
1357 r = ext4_dir_try_insert_entry(&fs->sb, parent, &target_block,
1358 child, name, name_len);
1361 r = ext4_block_set(fs->bdev, &new_block);
1365 /* Cleanup operations */
1367 release_target_index:
1370 r = ext4_block_set(fs->bdev, &target_block);
1380 while (dx_it <= dx_blk) {
1381 r = ext4_block_set(fs->bdev, &dx_it->b);
1391 int ext4_dir_dx_reset_parent_inode(struct ext4_inode_ref *dir,
1392 uint32_t parent_inode)
1394 /* Load block 0, where will be index root located */
1395 ext4_fsblk_t fblock;
1396 int rc = ext4_fs_get_inode_data_block_index(dir, 0, &fblock, false);
1400 struct ext4_block block;
1401 rc = ext4_block_get(dir->fs->bdev, &block, fblock);
1405 if (!ext4_dir_dx_csum_verify(dir, (void *)block.data)) {
1406 ext4_dbg(DEBUG_DIR_IDX,
1407 DBG_WARN "HTree root checksum failed."
1408 "Inode: %" PRIu32", "
1409 "Block: %" PRIu32"\n",
1414 /* Initialize pointers to data structures */
1415 struct ext4_dir_idx_root *root = (void *)block.data;
1417 /* Fill the inode field with a new parent ino. */
1418 ext4_dx_dot_en_set_inode(&root->dots[1], parent_inode);
1420 ext4_dir_set_dx_csum(dir, (void *)block.data);
1423 return ext4_block_set(dir->fs->bdev, &block);