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_hash.h"
48 /**@brief Get hash version used in directory index.
49 * @param root_info Pointer to root info structure of index
50 * @return Hash algorithm version
52 static inline uint8_t ext4_dir_dx_root_info_get_hash_version(
53 struct ext4_directory_dx_root_info *root_info)
55 return root_info->hash_version;
58 /**@brief Set hash version, that will be used in directory index.
59 * @param root_info Pointer to root info structure of index
60 * @param v Hash algorithm version
62 static inline void ext4_dir_dx_root_info_set_hash_version(
63 struct ext4_directory_dx_root_info *root_info, uint8_t v)
65 root_info->hash_version = v;
68 /**@brief Get length of root_info structure in bytes.
69 * @param root_info Pointer to root info structure of index
70 * @return Length of the structure
72 static inline uint8_t ext4_dir_dx_root_info_get_info_length(
73 struct ext4_directory_dx_root_info *root_info)
75 return root_info->info_length;
78 /**@brief Set length of root_info structure in bytes.
79 * @param root_info Pointer to root info structure of index
80 * @param info_length Length of the structure
82 static inline void ext4_dir_dx_root_info_set_info_length(
83 struct ext4_directory_dx_root_info *root_info, uint8_t len)
85 root_info->info_length = len;
88 /**@brief Get number of indirect levels of HTree.
89 * @param root_info Pointer to root info structure of index
90 * @return Height of HTree (actually only 0 or 1)
92 static inline uint8_t ext4_dir_dx_root_info_get_indirect_levels(
93 struct ext4_directory_dx_root_info *root_info)
95 return root_info->indirect_levels;
98 /**@brief Set number of indirect levels of HTree.
99 * @param root_info Pointer to root info structure of index
100 * @param lvl Height of HTree (actually only 0 or 1)
102 static inline void ext4_dir_dx_root_info_set_indirect_levels(
103 struct ext4_directory_dx_root_info *root_info, uint8_t lvl)
105 root_info->indirect_levels = lvl;
108 /**@brief Get maximum number of index node entries.
109 * @param climit Pointer to counlimit structure
110 * @return Maximum of entries in node
112 static inline uint16_t
113 ext4_dir_dx_countlimit_get_limit(struct ext4_directory_dx_countlimit *climit)
115 return to_le16(climit->limit);
118 /**@brief Set maximum number of index node entries.
119 * @param climit Pointer to counlimit structure
120 * @param limit Maximum of entries in node
123 ext4_dir_dx_countlimit_set_limit(struct ext4_directory_dx_countlimit *climit,
126 climit->limit = to_le16(limit);
129 /**@brief Get current number of index node entries.
130 * @param climit Pointer to counlimit structure
131 * @return Number of entries in node
133 static inline uint16_t
134 ext4_dir_dx_countlimit_get_count(struct ext4_directory_dx_countlimit *climit)
136 return to_le16(climit->count);
139 /**@brief Set current number of index node entries.
140 * @param climit Pointer to counlimit structure
141 * @param count Number of entries in node
144 ext4_dir_dx_countlimit_set_count(struct ext4_directory_dx_countlimit *climit,
147 climit->count = to_le16(count);
150 /**@brief Get hash value of index entry.
151 * @param entry Pointer to index entry
154 static inline uint32_t
155 ext4_dir_dx_entry_get_hash(struct ext4_directory_dx_entry *entry)
157 return to_le32(entry->hash);
160 /**@brief Set hash value of index entry.
161 * @param entry Pointer to index entry
162 * @param hash Hash value
165 ext4_dir_dx_entry_set_hash(struct ext4_directory_dx_entry *entry, uint32_t hash)
167 entry->hash = to_le32(hash);
170 /**@brief Get block address where child node is located.
171 * @param entry Pointer to index entry
172 * @return Block address of child node
174 static inline uint32_t
175 ext4_dir_dx_entry_get_block(struct ext4_directory_dx_entry *entry)
177 return to_le32(entry->block);
180 /**@brief Set block address where child node is located.
181 * @param entry Pointer to index entry
182 * @param block Block address of child node
185 ext4_dir_dx_entry_set_block(struct ext4_directory_dx_entry *entry,
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 /****************************************************************************/
207 int ext4_dir_dx_init(struct ext4_inode_ref *dir)
209 /* Load block 0, where will be index root located */
211 int rc = ext4_fs_get_inode_data_block_index(dir, 0, &fblock);
215 struct ext4_block block;
216 rc = ext4_block_get(dir->fs->bdev, &block, fblock);
220 /* Initialize pointers to data structures */
221 struct ext4_directory_dx_root *root = (void *)block.data;
222 struct ext4_directory_dx_root_info *info = &(root->info);
224 /* Initialize root info structure */
225 uint8_t hash_version = ext4_get8(&dir->fs->sb, default_hash_version);
227 ext4_dir_dx_root_info_set_hash_version(info, hash_version);
228 ext4_dir_dx_root_info_set_indirect_levels(info, 0);
229 ext4_dir_dx_root_info_set_info_length(info, 8);
231 /* Set limit and current number of entries */
232 struct ext4_directory_dx_countlimit *countlimit =
233 (struct ext4_directory_dx_countlimit *)&root->entries;
235 ext4_dir_dx_countlimit_set_count(countlimit, 1);
237 uint32_t block_size = ext4_sb_get_block_size(&dir->fs->sb);
238 uint32_t entry_space = block_size -
239 2 * sizeof(struct ext4_directory_dx_dot_entry) -
240 sizeof(struct ext4_directory_dx_root_info);
241 uint16_t root_limit =
242 entry_space / sizeof(struct ext4_directory_dx_entry);
243 ext4_dir_dx_countlimit_set_limit(countlimit, root_limit);
245 /* Append new block, where will be new entries inserted in the future */
247 rc = ext4_fs_append_inode_block(dir, &fblock, &iblock);
249 ext4_block_set(dir->fs->bdev, &block);
253 struct ext4_block new_block;
255 rc = ext4_block_get(dir->fs->bdev, &new_block, fblock);
257 ext4_block_set(dir->fs->bdev, &block);
261 /* Fill the whole block with empty entry */
262 struct ext4_directory_entry_ll *block_entry = (void *)new_block.data;
264 ext4_dir_entry_ll_set_entry_length(block_entry, block_size);
265 ext4_dir_entry_ll_set_inode(block_entry, 0);
267 new_block.dirty = true;
268 rc = ext4_block_set(dir->fs->bdev, &new_block);
270 ext4_block_set(dir->fs->bdev, &block);
274 /* Connect new block to the only entry in index */
275 struct ext4_directory_dx_entry *entry = root->entries;
276 ext4_dir_dx_entry_set_block(entry, iblock);
280 return ext4_block_set(dir->fs->bdev, &block);
283 /**@brief Initialize hash info structure necessary for index operations.
284 * @param hinfo Pointer to hinfo to be initialized
285 * @param root_block Root block (number 0) of index
286 * @param sb Pointer to superblock
287 * @param name_len Length of name to be computed hash value from
288 * @param name Name to be computed hash value from
289 * @return Standard error code
291 static int ext4_dir_hinfo_init(struct ext4_hash_info *hinfo,
292 struct ext4_block *root_block,
293 struct ext4_sblock *sb, size_t name_len,
296 struct ext4_directory_dx_root *root =
297 (struct ext4_directory_dx_root *)root_block->data;
299 if ((root->info.hash_version != EXT2_HTREE_LEGACY) &&
300 (root->info.hash_version != EXT2_HTREE_HALF_MD4) &&
301 (root->info.hash_version != EXT2_HTREE_TEA))
302 return EXT4_ERR_BAD_DX_DIR;
304 /* Check unused flags */
305 if (root->info.unused_flags != 0)
306 return EXT4_ERR_BAD_DX_DIR;
308 /* Check indirect levels */
309 if (root->info.indirect_levels > 1)
310 return EXT4_ERR_BAD_DX_DIR;
312 /* Check if node limit is correct */
313 uint32_t block_size = ext4_sb_get_block_size(sb);
314 uint32_t entry_space = block_size;
315 entry_space -= 2 * sizeof(struct ext4_directory_dx_dot_entry);
316 entry_space -= sizeof(struct ext4_directory_dx_root_info);
317 entry_space = entry_space / sizeof(struct ext4_directory_dx_entry);
319 uint16_t limit = ext4_dir_dx_countlimit_get_limit(
320 (struct ext4_directory_dx_countlimit *)&root->entries);
321 if (limit != entry_space)
322 return EXT4_ERR_BAD_DX_DIR;
324 /* Check hash version and modify if necessary */
325 hinfo->hash_version =
326 ext4_dir_dx_root_info_get_hash_version(&root->info);
327 if ((hinfo->hash_version <= EXT2_HTREE_TEA) &&
328 (ext4_sb_check_flag(sb, EXT4_SUPERBLOCK_FLAGS_UNSIGNED_HASH))) {
329 /* Use unsigned hash */
330 hinfo->hash_version += 3;
333 /* Load hash seed from superblock */
335 hinfo->seed = ext4_get8(sb, hash_seed);
337 /* Compute hash value of name */
339 return ext4_dir_dx_hash_string(hinfo, name_len, name);
344 /**@brief Walk through index tree and load leaf with corresponding hash value.
345 * @param hinfo Initialized hash info structure
346 * @param inode_ref Current i-node
347 * @param root_block Root block (iblock 0), where is root node located
348 * @param dx_block Pointer to leaf node in dx_blocks array
349 * @param dx_blocks Array with the whole path from root to leaf
350 * @return Standard error code
352 static int ext4_dir_dx_get_leaf(struct ext4_hash_info *hinfo,
353 struct ext4_inode_ref *inode_ref,
354 struct ext4_block *root_block,
355 struct ext4_directory_dx_block **dx_block,
356 struct ext4_directory_dx_block *dx_blocks)
358 struct ext4_directory_dx_block *tmp_dx_block = dx_blocks;
359 struct ext4_directory_dx_root *root =
360 (struct ext4_directory_dx_root *)root_block->data;
361 struct ext4_directory_dx_entry *entries =
362 (struct ext4_directory_dx_entry *)&root->entries;
364 uint16_t limit = ext4_dir_dx_countlimit_get_limit(
365 (struct ext4_directory_dx_countlimit *)entries);
366 uint8_t indirect_level =
367 ext4_dir_dx_root_info_get_indirect_levels(&root->info);
369 struct ext4_block *tmp_block = root_block;
370 struct ext4_directory_dx_entry *p;
371 struct ext4_directory_dx_entry *q;
372 struct ext4_directory_dx_entry *m;
373 struct ext4_directory_dx_entry *at;
375 /* Walk through the index tree */
377 uint16_t count = ext4_dir_dx_countlimit_get_count(
378 (struct ext4_directory_dx_countlimit *)entries);
379 if ((count == 0) || (count > limit))
380 return EXT4_ERR_BAD_DX_DIR;
382 /* Do binary search in every node */
384 q = entries + count - 1;
388 if (ext4_dir_dx_entry_get_hash(m) > hinfo->hash)
398 memcpy(&tmp_dx_block->block, tmp_block,
399 sizeof(struct ext4_block));
400 tmp_dx_block->entries = entries;
401 tmp_dx_block->position = at;
403 /* Is algorithm in the leaf? */
404 if (indirect_level == 0) {
405 *dx_block = tmp_dx_block;
409 /* Goto child node */
410 uint32_t next_block = ext4_dir_dx_entry_get_block(at);
415 int rc = ext4_fs_get_inode_data_block_index(
416 inode_ref, next_block, &fblock);
420 rc = ext4_block_get(inode_ref->fs->bdev, tmp_block, fblock);
425 ((struct ext4_directory_dx_node *)tmp_block->data)->entries;
426 limit = ext4_dir_dx_countlimit_get_limit(
427 (struct ext4_directory_dx_countlimit *)entries);
429 uint16_t entry_space =
430 ext4_sb_get_block_size(&inode_ref->fs->sb) -
431 sizeof(struct ext4_fake_directory_entry);
434 entry_space / sizeof(struct ext4_directory_dx_entry);
436 if (limit != entry_space) {
437 ext4_block_set(inode_ref->fs->bdev, tmp_block);
438 return EXT4_ERR_BAD_DX_DIR;
448 /**@brief Check if the the next block would be checked during entry search.
449 * @param inode_ref Directory i-node
450 * @param hash Hash value to check
451 * @param dx_block Current block
452 * @param dx_blocks Array with path from root to leaf node
453 * @return Standard Error code
455 static int ext4_dir_dx_next_block(struct ext4_inode_ref *inode_ref,
457 struct ext4_directory_dx_block *dx_block,
458 struct ext4_directory_dx_block *dx_blocks)
460 uint32_t num_handles = 0;
461 struct ext4_directory_dx_block *p = dx_block;
463 /* Try to find data block with next bunch of entries */
466 uint16_t count = ext4_dir_dx_countlimit_get_count(
467 (struct ext4_directory_dx_countlimit *)p->entries);
469 if (p->position < p->entries + count)
479 /* Check hash collision (if not occurred - no next block cannot be
481 uint32_t current_hash = ext4_dir_dx_entry_get_hash(p->position);
482 if ((hash & 1) == 0) {
483 if ((current_hash & ~1) != hash)
488 while (num_handles--) {
489 uint32_t block_idx = ext4_dir_dx_entry_get_block(p->position);
492 int rc = ext4_fs_get_inode_data_block_index(
493 inode_ref, block_idx, &block_addr);
497 struct ext4_block block;
498 rc = ext4_block_get(inode_ref->fs->bdev, &block, block_addr);
504 /* Don't forget to put old block (prevent memory leak) */
505 rc = ext4_block_set(inode_ref->fs->bdev, &p->block);
509 memcpy(&p->block, &p->block, sizeof(block));
511 ((struct ext4_directory_dx_node *)block.data)->entries;
512 p->position = p->entries;
518 int ext4_dir_dx_find_entry(struct ext4_directory_search_result *result,
519 struct ext4_inode_ref *inode_ref, size_t name_len,
522 /* Load direct block 0 (index root) */
523 uint32_t root_block_addr;
526 ext4_fs_get_inode_data_block_index(inode_ref, 0, &root_block_addr);
530 struct ext4_fs *fs = inode_ref->fs;
532 struct ext4_block root_block;
533 rc = ext4_block_get(fs->bdev, &root_block, root_block_addr);
537 /* Initialize hash info (compute hash value) */
538 struct ext4_hash_info hinfo;
539 rc = ext4_dir_hinfo_init(&hinfo, &root_block, &fs->sb, name_len, name);
541 ext4_block_set(fs->bdev, &root_block);
542 return EXT4_ERR_BAD_DX_DIR;
546 * Hardcoded number 2 means maximum height of index tree,
547 * specified in the Linux driver.
549 struct ext4_directory_dx_block dx_blocks[2];
550 struct ext4_directory_dx_block *dx_block;
551 struct ext4_directory_dx_block *tmp;
553 rc = ext4_dir_dx_get_leaf(&hinfo, inode_ref, &root_block, &dx_block,
556 ext4_block_set(fs->bdev, &root_block);
557 return EXT4_ERR_BAD_DX_DIR;
561 /* Load leaf block */
562 uint32_t leaf_block_idx =
563 ext4_dir_dx_entry_get_block(dx_block->position);
564 uint32_t leaf_block_addr;
566 rc = ext4_fs_get_inode_data_block_index(
567 inode_ref, leaf_block_idx, &leaf_block_addr);
571 struct ext4_block leaf_block;
572 rc = ext4_block_get(fs->bdev, &leaf_block, leaf_block_addr);
576 /* Linear search inside block */
577 struct ext4_directory_entry_ll *res_dentry;
578 rc = ext4_dir_find_in_block(&leaf_block, &fs->sb, name_len,
581 /* Found => return it */
583 result->block = leaf_block;
584 result->dentry = res_dentry;
588 /* Not found, leave untouched */
589 rc2 = ext4_block_set(fs->bdev, &leaf_block);
596 /* check if the next block could be checked */
597 rc = ext4_dir_dx_next_block(inode_ref, hinfo.hash, dx_block,
601 } while (rc == ENOENT);
603 /* Entry not found */
607 /* The whole path must be released (preventing memory leak) */
610 while (tmp <= dx_block) {
611 rc2 = ext4_block_set(fs->bdev, &tmp->block);
612 if (rc == EOK && rc2 != EOK)
620 #if CONFIG_DIR_INDEX_COMB_SORT
621 #define SWAP_ENTRY(se1, se2) \
623 struct ext4_dx_sort_entry tmp = se1; \
629 static void comb_sort(struct ext4_dx_sort_entry *se, uint32_t count)
631 struct ext4_dx_sort_entry *p, *q, *top = se + count - 1;
635 count = (count * 10) / 13;
638 for (p = top, q = p - count; q >= se; p--, q--)
639 if (p->hash < q->hash)
647 if (q[1].hash >= q[0].hash)
649 SWAP_ENTRY(*(q + 1), *q);
656 /**@brief Compare function used to pass in quicksort implementation.
657 * It can compare two entries by hash value.
658 * @param arg1 First entry
659 * @param arg2 Second entry
660 * @param dummy Unused parameter, can be NULL
662 * @return Classic compare result
663 * (0: equal, -1: arg1 < arg2, 1: arg1 > arg2)
665 static int ext4_dir_dx_entry_comparator(const void *arg1, const void *arg2)
667 struct ext4_dx_sort_entry *entry1 = (void *)arg1;
668 struct ext4_dx_sort_entry *entry2 = (void *)arg2;
670 if (entry1->hash == entry2->hash)
673 if (entry1->hash < entry2->hash)
680 /**@brief Insert new index entry to block.
681 * Note that space for new entry must be checked by caller.
682 * @param index_block Block where to insert new entry
683 * @param hash Hash value covered by child node
684 * @param iblock Logical number of child block
688 ext4_dir_dx_insert_entry(struct ext4_directory_dx_block *index_block,
689 uint32_t hash, uint32_t iblock)
691 struct ext4_directory_dx_entry *old_index_entry = index_block->position;
692 struct ext4_directory_dx_entry *new_index_entry = old_index_entry + 1;
694 struct ext4_directory_dx_countlimit *countlimit =
695 (struct ext4_directory_dx_countlimit *)index_block->entries;
696 uint32_t count = ext4_dir_dx_countlimit_get_count(countlimit);
698 struct ext4_directory_dx_entry *start_index = index_block->entries;
700 (uint8_t *)(start_index + count) - (uint8_t *)(new_index_entry);
702 memmove(new_index_entry + 1, new_index_entry, bytes);
704 ext4_dir_dx_entry_set_block(new_index_entry, iblock);
705 ext4_dir_dx_entry_set_hash(new_index_entry, hash);
707 ext4_dir_dx_countlimit_set_count(countlimit, count + 1);
709 index_block->block.dirty = true;
712 /**@brief Split directory entries to two parts preventing node overflow.
713 * @param inode_ref Directory i-node
714 * @param hinfo Hash info
715 * @param old_data_block Block with data to be split
716 * @param index_block Block where index entries are located
717 * @param new_data_block Output value for newly allocated data block
719 static int ext4_dir_dx_split_data(struct ext4_inode_ref *inode_ref,
720 struct ext4_hash_info *hinfo,
721 struct ext4_block *old_data_block,
722 struct ext4_directory_dx_block *index_block,
723 struct ext4_block *new_data_block)
727 /* Allocate buffer for directory entries */
728 uint32_t block_size = ext4_sb_get_block_size(&inode_ref->fs->sb);
730 uint8_t *entry_buffer = malloc(block_size);
731 if (entry_buffer == NULL)
734 /* dot entry has the smallest size available */
735 uint32_t max_entry_count =
736 block_size / sizeof(struct ext4_directory_dx_dot_entry);
738 /* Allocate sort entry */
739 struct ext4_dx_sort_entry *sort_array =
740 malloc(max_entry_count * sizeof(struct ext4_dx_sort_entry));
742 if (sort_array == NULL) {
748 uint32_t real_size = 0;
750 /* Initialize hinfo */
751 struct ext4_hash_info tmp_hinfo;
752 memcpy(&tmp_hinfo, hinfo, sizeof(struct ext4_hash_info));
754 /* Load all valid entries to the buffer */
755 struct ext4_directory_entry_ll *dentry = (void *)old_data_block->data;
756 uint8_t *entry_buffer_ptr = entry_buffer;
757 while ((void *)dentry < (void *)(old_data_block->data + block_size)) {
758 /* Read only valid entries */
759 if (ext4_dir_entry_ll_get_inode(dentry) &&
760 dentry->name_length) {
761 uint8_t len = ext4_dir_entry_ll_get_name_length(
762 &inode_ref->fs->sb, dentry);
764 rc = ext4_dir_dx_hash_string(&tmp_hinfo, len,
765 (char *)dentry->name);
772 uint32_t rec_len = 8 + len;
774 if ((rec_len % 4) != 0)
775 rec_len += 4 - (rec_len % 4);
777 memcpy(entry_buffer_ptr, dentry, rec_len);
779 sort_array[idx].dentry = entry_buffer_ptr;
780 sort_array[idx].rec_len = rec_len;
781 sort_array[idx].hash = tmp_hinfo.hash;
783 entry_buffer_ptr += rec_len;
784 real_size += rec_len;
788 dentry = (void *)((uint8_t *)dentry +
789 ext4_dir_entry_ll_get_entry_length(dentry));
792 /* Sort all entries */
793 #if CONFIG_DIR_INDEX_COMB_SORT
794 comb_sort(sort_array, idx);
796 qsort(sort_array, idx, sizeof(struct ext4_dx_sort_entry),
797 ext4_dir_dx_entry_comparator);
799 /* Allocate new block for store the second part of entries */
802 rc = ext4_fs_append_inode_block(inode_ref, &new_fblock, &new_iblock);
810 struct ext4_block new_data_block_tmp;
811 rc = ext4_block_get(inode_ref->fs->bdev, &new_data_block_tmp,
820 * Distribute entries to two blocks (by size)
823 uint32_t new_hash = 0;
824 uint32_t current_size = 0;
827 for (i = 0; i < idx; ++i) {
828 if ((current_size + sort_array[i].rec_len) > (block_size / 2)) {
829 new_hash = sort_array[i].hash;
834 current_size += sort_array[i].rec_len;
837 /* Check hash collision */
838 uint32_t continued = 0;
839 if (new_hash == sort_array[mid - 1].hash)
845 /* First part - to the old block */
846 for (i = 0; i < mid; ++i) {
847 ptr = old_data_block->data + offset;
848 memcpy(ptr, sort_array[i].dentry, sort_array[i].rec_len);
850 struct ext4_directory_entry_ll *tmp = ptr;
852 ext4_dir_entry_ll_set_entry_length(
853 tmp, sort_array[i].rec_len);
855 ext4_dir_entry_ll_set_entry_length(tmp,
856 block_size - offset);
858 offset += sort_array[i].rec_len;
861 /* Second part - to the new block */
863 for (i = mid; i < idx; ++i) {
864 ptr = new_data_block_tmp.data + offset;
865 memcpy(ptr, sort_array[i].dentry, sort_array[i].rec_len);
867 struct ext4_directory_entry_ll *tmp = ptr;
869 ext4_dir_entry_ll_set_entry_length(
870 tmp, sort_array[i].rec_len);
872 ext4_dir_entry_ll_set_entry_length(tmp,
873 block_size - offset);
875 offset += sort_array[i].rec_len;
878 /* Do some steps to finish operation */
879 old_data_block->dirty = true;
880 new_data_block_tmp.dirty = true;
885 ext4_dir_dx_insert_entry(index_block, new_hash + continued, new_iblock);
887 *new_data_block = new_data_block_tmp;
892 /**@brief Split index node and maybe some parent nodes in the tree hierarchy.
893 * @param inode_ref Directory i-node
894 * @param dx_blocks Array with path from root to leaf node
895 * @param dx_block Leaf block to be split if needed
899 ext4_dir_dx_split_index(struct ext4_inode_ref *inode_ref,
900 struct ext4_directory_dx_block *dx_blocks,
901 struct ext4_directory_dx_block *dx_block,
902 struct ext4_directory_dx_block **new_dx_block)
904 struct ext4_directory_dx_entry *entries;
906 if (dx_block == dx_blocks)
908 ((struct ext4_directory_dx_root *)dx_block->block.data)
912 ((struct ext4_directory_dx_node *)dx_block->block.data)
915 struct ext4_directory_dx_countlimit *countlimit =
916 (struct ext4_directory_dx_countlimit *)entries;
918 uint16_t leaf_limit = ext4_dir_dx_countlimit_get_limit(countlimit);
919 uint16_t leaf_count = ext4_dir_dx_countlimit_get_count(countlimit);
921 /* Check if is necessary to split index block */
922 if (leaf_limit == leaf_count) {
923 size_t levels = dx_block - dx_blocks;
925 struct ext4_directory_dx_entry *root_entries =
926 ((struct ext4_directory_dx_root *)dx_blocks[0].block.data)
929 struct ext4_directory_dx_countlimit *root_countlimit =
930 (struct ext4_directory_dx_countlimit *)root_entries;
931 uint16_t root_limit =
932 ext4_dir_dx_countlimit_get_limit(root_countlimit);
933 uint16_t root_count =
934 ext4_dir_dx_countlimit_get_count(root_countlimit);
936 /* Linux limitation */
937 if ((levels > 0) && (root_limit == root_count))
940 /* Add new block to directory */
943 int rc = ext4_fs_append_inode_block(inode_ref, &new_fblock,
949 struct ext4_block new_block;
951 ext4_block_get(inode_ref->fs->bdev, &new_block, new_fblock);
955 struct ext4_directory_dx_node *new_node =
956 (void *)new_block.data;
957 struct ext4_directory_dx_entry *new_entries = new_node->entries;
959 memset(&new_node->fake, 0,
960 sizeof(struct ext4_fake_directory_entry));
962 uint32_t block_size =
963 ext4_sb_get_block_size(&inode_ref->fs->sb);
965 new_node->fake.entry_length = block_size;
967 /* Split leaf node */
969 uint32_t count_left = leaf_count / 2;
970 uint32_t count_right = leaf_count - count_left;
971 uint32_t hash_right =
972 ext4_dir_dx_entry_get_hash(entries + count_left);
974 /* Copy data to new node */
975 memcpy((void *)new_entries,
976 (void *)(entries + count_left),
978 sizeof(struct ext4_directory_dx_entry));
980 /* Initialize new node */
981 struct ext4_directory_dx_countlimit *left_countlimit =
982 (struct ext4_directory_dx_countlimit *)entries;
983 struct ext4_directory_dx_countlimit *right_countlimit =
984 (struct ext4_directory_dx_countlimit *)new_entries;
986 ext4_dir_dx_countlimit_set_count(left_countlimit,
988 ext4_dir_dx_countlimit_set_count(right_countlimit,
991 uint32_t entry_space =
993 sizeof(struct ext4_fake_directory_entry);
994 uint32_t node_limit =
996 sizeof(struct ext4_directory_dx_entry);
997 ext4_dir_dx_countlimit_set_limit(right_countlimit,
1000 /* Which index block is target for new entry */
1001 uint32_t position_index =
1002 (dx_block->position - dx_block->entries);
1003 if (position_index >= count_left) {
1004 dx_block->block.dirty = true;
1006 struct ext4_block block_tmp = dx_block->block;
1008 dx_block->block = new_block;
1010 dx_block->position =
1011 new_entries + position_index - count_left;
1012 dx_block->entries = new_entries;
1014 new_block = block_tmp;
1017 /* Finally insert new entry */
1018 ext4_dir_dx_insert_entry(dx_blocks, hash_right,
1020 dx_blocks[0].block.dirty = true;
1021 dx_blocks[1].block.dirty = true;
1023 new_block.dirty = true;
1024 return ext4_block_set(inode_ref->fs->bdev, &new_block);
1026 /* Create second level index */
1028 /* Copy data from root to child block */
1029 memcpy((void *)new_entries, (void *)entries,
1031 sizeof(struct ext4_directory_dx_entry));
1033 struct ext4_directory_dx_countlimit *new_countlimit =
1034 (struct ext4_directory_dx_countlimit *)new_entries;
1036 uint32_t entry_space =
1038 sizeof(struct ext4_fake_directory_entry);
1039 uint32_t node_limit =
1041 sizeof(struct ext4_directory_dx_entry);
1042 ext4_dir_dx_countlimit_set_limit(new_countlimit,
1045 /* Set values in root node */
1046 struct ext4_directory_dx_countlimit
1047 *new_root_countlimit =
1048 (struct ext4_directory_dx_countlimit *)entries;
1050 ext4_dir_dx_countlimit_set_count(new_root_countlimit,
1052 ext4_dir_dx_entry_set_block(entries, new_iblock);
1054 ((struct ext4_directory_dx_root *)dx_blocks[0]
1056 ->info.indirect_levels = 1;
1058 /* Add new entry to the path */
1059 dx_block = dx_blocks + 1;
1060 dx_block->position =
1061 dx_blocks->position - entries + new_entries;
1062 dx_block->entries = new_entries;
1063 dx_block->block = new_block;
1065 *new_dx_block = dx_block;
1067 dx_blocks[0].block.dirty = true;
1068 dx_blocks[1].block.dirty = true;
1075 int ext4_dir_dx_add_entry(struct ext4_inode_ref *parent,
1076 struct ext4_inode_ref *child, const char *name)
1080 /* Get direct block 0 (index root) */
1081 uint32_t root_block_addr;
1083 ext4_fs_get_inode_data_block_index(parent, 0, &root_block_addr);
1087 struct ext4_fs *fs = parent->fs;
1088 struct ext4_block root_block;
1090 rc = ext4_block_get(fs->bdev, &root_block, root_block_addr);
1094 /* Initialize hinfo structure (mainly compute hash) */
1095 uint32_t name_len = strlen(name);
1096 struct ext4_hash_info hinfo;
1097 rc = ext4_dir_hinfo_init(&hinfo, &root_block, &fs->sb, name_len, name);
1099 ext4_block_set(fs->bdev, &root_block);
1100 return EXT4_ERR_BAD_DX_DIR;
1104 * Hardcoded number 2 means maximum height of index
1105 * tree defined in Linux.
1107 struct ext4_directory_dx_block dx_blocks[2];
1108 struct ext4_directory_dx_block *dx_block;
1109 struct ext4_directory_dx_block *dx_it;
1111 rc = ext4_dir_dx_get_leaf(&hinfo, parent, &root_block, &dx_block,
1114 rc = EXT4_ERR_BAD_DX_DIR;
1118 /* Try to insert to existing data block */
1119 uint32_t leaf_block_idx =
1120 ext4_dir_dx_entry_get_block(dx_block->position);
1121 uint32_t leaf_block_addr;
1122 rc = ext4_fs_get_inode_data_block_index(parent, leaf_block_idx,
1128 * Check if there is needed to split index node
1129 * (and recursively also parent nodes)
1131 rc = ext4_dir_dx_split_index(parent, dx_blocks, dx_block, &dx_block);
1133 goto release_target_index;
1135 struct ext4_block target_block;
1136 rc = ext4_block_get(fs->bdev, &target_block, leaf_block_addr);
1140 /* Check if insert operation passed */
1141 rc = ext4_dir_try_insert_entry(&fs->sb, &target_block, child, name,
1144 goto release_target_index;
1146 /* Split entries to two blocks (includes sorting by hash value) */
1147 struct ext4_block new_block;
1148 rc = ext4_dir_dx_split_data(parent, &hinfo, &target_block, dx_block,
1152 goto release_target_index;
1155 /* Where to save new entry */
1156 uint32_t new_block_hash =
1157 ext4_dir_dx_entry_get_hash(dx_block->position + 1);
1158 if (hinfo.hash >= new_block_hash)
1159 rc = ext4_dir_try_insert_entry(&fs->sb, &new_block, child, name,
1162 rc = ext4_dir_try_insert_entry(&fs->sb, &target_block, child,
1166 rc = ext4_block_set(fs->bdev, &new_block);
1170 /* Cleanup operations */
1172 release_target_index:
1175 rc = ext4_block_set(fs->bdev, &target_block);
1185 while (dx_it <= dx_block) {
1186 rc = ext4_block_set(fs->bdev, &dx_it->block);