source: mainline/uspace/lib/ext4/libext4_directory_index.c@ 1fff583

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 1fff583 was 7eb033ce, checked in by Frantisek Princ <frantisek.princ@…>, 13 years ago

not debugged version of dir index initialization
  • Property mode set to 100644
File size: 25.4 KB
Line 
1/*
2 * Copyright (c) 2011 Frantisek Princ
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29/** @addtogroup libext4
30 * @{
31 */
32
33/**
34 * @file libext4_directory_index.c
35 * @brief Ext4 directory index operations.
36 */
37
38#include <byteorder.h>
39#include <errno.h>
40#include <malloc.h>
41#include <sort.h>
42#include <string.h>
43#include "libext4.h"
44
45typedef struct ext4_dx_sort_entry {
46 uint32_t hash;
47 uint32_t rec_len;
48 void *dentry;
49} ext4_dx_sort_entry_t;
50
51
52uint8_t ext4_directory_dx_root_info_get_hash_version(
53 ext4_directory_dx_root_info_t *root_info)
54{
55 return root_info->hash_version;
56}
57
58void ext4_directory_dx_root_info_set_hash_version(
59 ext4_directory_dx_root_info_t *root_info, uint8_t version)
60{
61 root_info->hash_version = version;
62}
63
64uint8_t ext4_directory_dx_root_info_get_info_length(
65 ext4_directory_dx_root_info_t *root_info)
66{
67 return root_info->info_length;
68}
69
70void ext4_directory_dx_root_info_set_info_length(
71 ext4_directory_dx_root_info_t *root_info, uint8_t info_length)
72{
73 root_info->info_length = info_length;
74}
75
76uint8_t ext4_directory_dx_root_info_get_indirect_levels(
77 ext4_directory_dx_root_info_t *root_info)
78{
79 return root_info->indirect_levels;
80}
81
82void ext4_directory_dx_root_info_set_indirect_levels(
83 ext4_directory_dx_root_info_t *root_info, uint8_t levels)
84{
85 root_info->indirect_levels = levels;
86}
87
88uint16_t ext4_directory_dx_countlimit_get_limit(
89 ext4_directory_dx_countlimit_t *countlimit)
90{
91 return uint16_t_le2host(countlimit->limit);
92}
93
94void ext4_directory_dx_countlimit_set_limit(
95 ext4_directory_dx_countlimit_t *countlimit, uint16_t limit)
96{
97 countlimit->limit = host2uint16_t_le(limit);
98}
99
100uint16_t ext4_directory_dx_countlimit_get_count(
101 ext4_directory_dx_countlimit_t *countlimit)
102{
103 return uint16_t_le2host(countlimit->count);
104}
105
106void ext4_directory_dx_countlimit_set_count(
107 ext4_directory_dx_countlimit_t *countlimit, uint16_t count)
108{
109 countlimit->count = host2uint16_t_le(count);
110}
111
112uint32_t ext4_directory_dx_entry_get_hash(ext4_directory_dx_entry_t *entry)
113{
114 return uint32_t_le2host(entry->hash);
115}
116
117void ext4_directory_dx_entry_set_hash(ext4_directory_dx_entry_t *entry,
118 uint32_t hash)
119{
120 entry->hash = host2uint32_t_le(hash);
121}
122
123uint32_t ext4_directory_dx_entry_get_block(ext4_directory_dx_entry_t *entry)
124{
125 return uint32_t_le2host(entry->block);
126}
127
128void ext4_directory_dx_entry_set_block(ext4_directory_dx_entry_t *entry,
129 uint32_t block)
130{
131 entry->block = host2uint32_t_le(block);
132}
133
134
135/**************************************************************************/
136
137int ext4_directory_dx_init(ext4_inode_ref_t *dir)
138{
139 int rc;
140
141 uint32_t fblock;
142 rc = ext4_filesystem_get_inode_data_block_index(dir, 0, &fblock);
143 if (rc != EOK) {
144 return rc;
145 }
146
147 block_t *block;
148 rc = block_get(&block, dir->fs->device, fblock, BLOCK_FLAGS_NONE);
149 if (rc != EOK) {
150 return rc;
151 }
152
153 EXT4FS_DBG("fblock = \%u", fblock);
154
155 ext4_directory_dx_root_t *root = block->data;
156
157 ext4_directory_entry_ll_t *dot = (ext4_directory_entry_ll_t *)&root->dots[0];
158 ext4_directory_entry_ll_t *dot_dot = (ext4_directory_entry_ll_t *)&root->dots[1];
159
160 EXT4FS_DBG("dot len = \%u, dotdot len = \%u", ext4_directory_entry_ll_get_entry_length(dot), ext4_directory_entry_ll_get_entry_length(dot_dot));
161
162// uint32_t block_size = ext4_superblock_get_block_size(dir->fs->superblock);
163// uint16_t len = block_size - sizeof(ext4_directory_dx_dot_entry_t);
164
165// ext4_directory_entry_ll_set_entry_length(dot_dot, len);
166
167 ext4_directory_dx_root_info_t *info = &(root->info);
168
169 uint8_t hash_version =
170 ext4_superblock_get_default_hash_version(dir->fs->superblock);
171
172 ext4_directory_dx_root_info_set_hash_version(info, hash_version);
173 ext4_directory_dx_root_info_set_indirect_levels(info, 0);
174 ext4_directory_dx_root_info_set_info_length(info, 8);
175
176 ext4_directory_dx_countlimit_t *countlimit =
177 (ext4_directory_dx_countlimit_t *)&root->entries;
178 ext4_directory_dx_countlimit_set_count(countlimit, 1);
179
180 uint32_t block_size = ext4_superblock_get_block_size(dir->fs->superblock);
181 uint32_t entry_space = block_size - 2 * sizeof(ext4_directory_dx_dot_entry_t)
182 - sizeof(ext4_directory_dx_root_info_t);
183 uint16_t root_limit = entry_space / sizeof(ext4_directory_dx_entry_t);
184 ext4_directory_dx_countlimit_set_limit(countlimit, root_limit);
185
186 uint32_t iblock;
187 rc = ext4_filesystem_append_inode_block(dir, &fblock, &iblock);
188 if (rc != EOK) {
189 block_put(block);
190 return rc;
191 }
192
193 block_t *new_block;
194 rc = block_get(&new_block, dir->fs->device, fblock, BLOCK_FLAGS_NOREAD);
195 if (rc != EOK) {
196 block_put(block);
197 return rc;
198 }
199
200 ext4_directory_entry_ll_t *block_entry = new_block->data;
201 ext4_directory_entry_ll_set_entry_length(block_entry, block_size);
202 ext4_directory_entry_ll_set_inode(block_entry, 0);
203
204 new_block->dirty = true;
205 rc = block_put(new_block);
206 if (rc != EOK) {
207 block_put(block);
208 return rc;
209 }
210
211 ext4_directory_dx_entry_t *entry = root->entries;
212 ext4_directory_dx_entry_set_block(entry, iblock);
213
214 block->dirty = true;
215
216 rc = block_put(block);
217 if (rc != EOK) {
218 return rc;
219 }
220
221 return EOK;
222}
223
224static int ext4_directory_hinfo_init(ext4_hash_info_t *hinfo, block_t *root_block,
225 ext4_superblock_t *sb, size_t name_len, const char *name)
226{
227
228 ext4_directory_dx_root_t *root = (ext4_directory_dx_root_t *)root_block->data;
229
230 if (root->info.hash_version != EXT4_HASH_VERSION_TEA &&
231 root->info.hash_version != EXT4_HASH_VERSION_HALF_MD4 &&
232 root->info.hash_version != EXT4_HASH_VERSION_LEGACY) {
233 return EXT4_ERR_BAD_DX_DIR;
234 }
235
236 // Check unused flags
237 if (root->info.unused_flags != 0) {
238 EXT4FS_DBG("ERR: unused_flags = \%u", root->info.unused_flags);
239 return EXT4_ERR_BAD_DX_DIR;
240 }
241
242 // Check indirect levels
243 if (root->info.indirect_levels > 1) {
244 EXT4FS_DBG("ERR: indirect_levels = \%u", root->info.indirect_levels);
245 return EXT4_ERR_BAD_DX_DIR;
246 }
247
248 uint32_t block_size = ext4_superblock_get_block_size(sb);
249
250 uint32_t entry_space = block_size;
251 entry_space -= 2 * sizeof(ext4_directory_dx_dot_entry_t);
252 entry_space -= sizeof(ext4_directory_dx_root_info_t);
253 entry_space = entry_space / sizeof(ext4_directory_dx_entry_t);
254
255 uint16_t limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)&root->entries);
256 if (limit != entry_space) {
257 return EXT4_ERR_BAD_DX_DIR;
258 }
259
260 hinfo->hash_version = ext4_directory_dx_root_info_get_hash_version(&root->info);
261 if ((hinfo->hash_version <= EXT4_HASH_VERSION_TEA)
262 && (ext4_superblock_has_flag(sb, EXT4_SUPERBLOCK_FLAGS_UNSIGNED_HASH))) {
263 // 3 is magic from ext4 linux implementation
264 hinfo->hash_version += 3;
265 }
266
267 hinfo->seed = ext4_superblock_get_hash_seed(sb);
268
269 if (name) {
270 ext4_hash_string(hinfo, name_len, name);
271 }
272
273 return EOK;
274}
275
276static int ext4_directory_dx_get_leaf(ext4_hash_info_t *hinfo,
277 ext4_inode_ref_t *inode_ref, block_t *root_block,
278 ext4_directory_dx_block_t **dx_block, ext4_directory_dx_block_t *dx_blocks)
279{
280 int rc;
281
282 ext4_directory_dx_block_t *tmp_dx_block = dx_blocks;
283
284 ext4_directory_dx_root_t *root = (ext4_directory_dx_root_t *)root_block->data;
285 ext4_directory_dx_entry_t *entries = (ext4_directory_dx_entry_t *)&root->entries;
286
287 uint16_t limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)entries);
288 uint8_t indirect_level = ext4_directory_dx_root_info_get_indirect_levels(&root->info);
289
290 block_t *tmp_block = root_block;
291 ext4_directory_dx_entry_t *p, *q, *m, *at;
292 while (true) {
293
294 uint16_t count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)entries);
295 if ((count == 0) || (count > limit)) {
296 return EXT4_ERR_BAD_DX_DIR;
297 }
298
299 p = entries + 1;
300 q = entries + count - 1;
301
302 while (p <= q) {
303 m = p + (q - p) / 2;
304 if (ext4_directory_dx_entry_get_hash(m) > hinfo->hash) {
305 q = m - 1;
306 } else {
307 p = m + 1;
308 }
309 }
310
311 at = p - 1;
312
313 tmp_dx_block->block = tmp_block;
314 tmp_dx_block->entries = entries;
315 tmp_dx_block->position = at;
316
317 if (indirect_level == 0) {
318 *dx_block = tmp_dx_block;
319 return EOK;
320 }
321
322 uint32_t next_block = ext4_directory_dx_entry_get_block(at);
323
324 indirect_level--;
325
326 uint32_t fblock;
327 rc = ext4_filesystem_get_inode_data_block_index(
328 inode_ref, next_block, &fblock);
329 if (rc != EOK) {
330 return rc;
331 }
332
333 rc = block_get(&tmp_block, inode_ref->fs->device, fblock, BLOCK_FLAGS_NONE);
334 if (rc != EOK) {
335 return rc;
336 }
337
338 entries = ((ext4_directory_dx_node_t *) tmp_block->data)->entries;
339 limit = ext4_directory_dx_countlimit_get_limit(
340 (ext4_directory_dx_countlimit_t *)entries);
341
342 uint16_t entry_space = ext4_superblock_get_block_size(inode_ref->fs->superblock)
343 - sizeof(ext4_directory_dx_dot_entry_t);
344 entry_space = entry_space / sizeof(ext4_directory_dx_entry_t);
345
346
347 if (limit != entry_space) {
348 block_put(tmp_block);
349 return EXT4_ERR_BAD_DX_DIR;
350 }
351
352 ++tmp_dx_block;
353 }
354
355 // Unreachable
356 return EOK;
357}
358
359
360static int ext4_directory_dx_next_block(ext4_inode_ref_t *inode_ref, uint32_t hash,
361 ext4_directory_dx_block_t *handle, ext4_directory_dx_block_t *handles)
362{
363 int rc;
364
365
366 uint32_t num_handles = 0;
367 ext4_directory_dx_block_t *p = handle;
368
369 while (1) {
370
371 p->position++;
372 uint16_t count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)p->entries);
373
374 if (p->position < p->entries + count) {
375 break;
376 }
377
378 if (p == handles) {
379 return 0;
380 }
381
382 num_handles++;
383 p--;
384 }
385
386 uint32_t current_hash = ext4_directory_dx_entry_get_hash(p->position);
387
388 if ((hash & 1) == 0) {
389 if ((current_hash & ~1) != hash) {
390 return 0;
391 }
392 }
393
394
395 while (num_handles--) {
396
397 uint32_t block_idx = ext4_directory_dx_entry_get_block(p->position);
398 uint32_t block_addr;
399 rc = ext4_filesystem_get_inode_data_block_index(inode_ref, block_idx, &block_addr);
400 if (rc != EOK) {
401 return rc;
402 }
403
404 block_t *block;
405 rc = block_get(&block, inode_ref->fs->device, block_addr, BLOCK_FLAGS_NONE);
406 if (rc != EOK) {
407 return rc;
408 }
409
410 p++;
411
412 block_put(p->block);
413 p->block = block;
414 p->entries = ((ext4_directory_dx_node_t *) block->data)->entries;
415 p->position = p->entries;
416 }
417
418 return 1;
419
420}
421
422int ext4_directory_dx_find_entry(ext4_directory_search_result_t *result,
423 ext4_inode_ref_t *inode_ref, size_t name_len, const char *name)
424{
425 int rc;
426
427 // get direct block 0 (index root)
428 uint32_t root_block_addr;
429 rc = ext4_filesystem_get_inode_data_block_index(inode_ref, 0, &root_block_addr);
430 if (rc != EOK) {
431 return rc;
432 }
433
434 ext4_filesystem_t *fs = inode_ref->fs;
435
436 block_t *root_block;
437 rc = block_get(&root_block, fs->device, root_block_addr, BLOCK_FLAGS_NONE);
438 if (rc != EOK) {
439 return rc;
440 }
441
442 ext4_hash_info_t hinfo;
443 rc = ext4_directory_hinfo_init(&hinfo, root_block, fs->superblock, name_len, name);
444 if (rc != EOK) {
445 block_put(root_block);
446 return EXT4_ERR_BAD_DX_DIR;
447 }
448
449 // Hardcoded number 2 means maximum height of index tree !!!
450 ext4_directory_dx_block_t dx_blocks[2];
451 ext4_directory_dx_block_t *dx_block, *tmp;
452 rc = ext4_directory_dx_get_leaf(&hinfo, inode_ref, root_block, &dx_block, dx_blocks);
453 if (rc != EOK) {
454 block_put(root_block);
455 return EXT4_ERR_BAD_DX_DIR;
456 }
457
458
459 do {
460
461 uint32_t leaf_block_idx = ext4_directory_dx_entry_get_block(dx_block->position);
462 uint32_t leaf_block_addr;
463 rc = ext4_filesystem_get_inode_data_block_index(inode_ref, leaf_block_idx, &leaf_block_addr);
464 if (rc != EOK) {
465 goto cleanup;
466 }
467
468 block_t *leaf_block;
469 rc = block_get(&leaf_block, fs->device, leaf_block_addr, BLOCK_FLAGS_NONE);
470 if (rc != EOK) {
471 goto cleanup;
472 }
473
474 ext4_directory_entry_ll_t *res_dentry;
475 rc = ext4_directory_find_in_block(leaf_block, fs->superblock, name_len, name, &res_dentry);
476
477 // Found => return it
478 if (rc == EOK) {
479 result->block = leaf_block;
480 result->dentry = res_dentry;
481 goto cleanup;
482 }
483
484 // Not found, leave untouched
485 block_put(leaf_block);
486
487 if (rc != ENOENT) {
488 goto cleanup;
489 }
490
491 rc = ext4_directory_dx_next_block(inode_ref, hinfo.hash, dx_block, &dx_blocks[0]);
492 if (rc < 0) {
493 goto cleanup;
494 }
495
496 } while (rc == 1);
497
498 rc = ENOENT;
499
500cleanup:
501
502 tmp = dx_blocks;
503 while (tmp <= dx_block) {
504 block_put(tmp->block);
505 ++tmp;
506 }
507 return rc;
508}
509
510static int ext4_directory_dx_entry_comparator(void *arg1, void *arg2, void *dummy)
511{
512 ext4_dx_sort_entry_t *entry1 = arg1;
513 ext4_dx_sort_entry_t *entry2 = arg2;
514
515 if (entry1->hash == entry2->hash) {
516 return 0;
517 }
518
519 if (entry1->hash < entry2->hash) {
520 return -1;
521 } else {
522 return 1;
523 }
524
525}
526
527static void ext4_directory_dx_insert_entry(
528 ext4_directory_dx_block_t *index_block, uint32_t hash, uint32_t iblock)
529{
530 ext4_directory_dx_entry_t *old_index_entry = index_block->position;
531 ext4_directory_dx_entry_t *new_index_entry = old_index_entry + 1;
532
533 ext4_directory_dx_countlimit_t *countlimit =
534 (ext4_directory_dx_countlimit_t *)index_block->entries;
535 uint32_t count = ext4_directory_dx_countlimit_get_count(countlimit);
536
537 ext4_directory_dx_entry_t *start_index = index_block->entries;
538 size_t bytes = (void *)(start_index + count) - (void *)(new_index_entry);
539
540 memmove(new_index_entry + 1, new_index_entry, bytes);
541
542 ext4_directory_dx_entry_set_block(new_index_entry, iblock);
543 ext4_directory_dx_entry_set_hash(new_index_entry, hash);
544
545 ext4_directory_dx_countlimit_set_count(countlimit, count + 1);
546
547 index_block->block->dirty = true;
548}
549
550static int ext4_directory_dx_split_data(ext4_filesystem_t *fs,
551 ext4_inode_ref_t *inode_ref, ext4_hash_info_t *hinfo,
552 block_t *old_data_block, ext4_directory_dx_block_t *index_block, block_t **new_data_block)
553{
554 int rc = EOK;
555
556 // Allocate buffer for directory entries
557 uint32_t block_size = ext4_superblock_get_block_size(fs->superblock);
558 void *entry_buffer = malloc(block_size);
559 if (entry_buffer == NULL) {
560 return ENOMEM;
561 }
562
563 // dot entry has the smallest size available
564 uint32_t max_entry_count = block_size / sizeof(ext4_directory_dx_dot_entry_t);
565
566 // Allocate sort entry
567 ext4_dx_sort_entry_t *sort_array = malloc(max_entry_count * sizeof(ext4_dx_sort_entry_t));
568 if (sort_array == NULL) {
569 free(entry_buffer);
570 return ENOMEM;
571 }
572
573 uint32_t idx = 0;
574 uint32_t real_size = 0;
575
576 // Initialize hinfo
577 ext4_hash_info_t tmp_hinfo;
578 memcpy(&tmp_hinfo, hinfo, sizeof(ext4_hash_info_t));
579
580 // Load all valid entries to the buffer
581 ext4_directory_entry_ll_t *dentry = old_data_block->data;
582 void *entry_buffer_ptr = entry_buffer;
583 while ((void *)dentry < old_data_block->data + block_size) {
584
585 // Read only valid entries
586 if (ext4_directory_entry_ll_get_inode(dentry) != 0) {
587
588 uint8_t len = ext4_directory_entry_ll_get_name_length(fs->superblock, dentry);
589 ext4_hash_string(&tmp_hinfo, len, (char *)dentry->name);
590
591 uint32_t rec_len = 8 + len;
592
593 if ((rec_len % 4) != 0) {
594 rec_len += 4 - (rec_len % 4);
595 }
596
597 memcpy(entry_buffer_ptr, dentry, rec_len);
598
599 sort_array[idx].dentry = entry_buffer_ptr;
600 sort_array[idx].rec_len = rec_len;
601 sort_array[idx].hash = tmp_hinfo.hash;
602
603 entry_buffer_ptr += rec_len;
604 real_size += rec_len;
605 idx++;
606 }
607
608 dentry = (void *)dentry + ext4_directory_entry_ll_get_entry_length(dentry);
609 }
610
611 qsort(sort_array, idx, sizeof(ext4_dx_sort_entry_t),
612 ext4_directory_dx_entry_comparator, NULL);
613
614 uint32_t new_fblock;
615 uint32_t new_iblock;
616 rc = ext4_filesystem_append_inode_block(inode_ref, &new_fblock, &new_iblock);
617 if (rc != EOK) {
618 free(sort_array);
619 free(entry_buffer);
620 return rc;
621 }
622
623 // Load new block
624 block_t *new_data_block_tmp;
625 rc = block_get(&new_data_block_tmp, fs->device, new_fblock, BLOCK_FLAGS_NOREAD);
626 if (rc != EOK) {
627 free(sort_array);
628 free(entry_buffer);
629 return rc;
630 }
631
632 // Distribute entries to splitted blocks (by size)
633 uint32_t new_hash = 0;
634 uint32_t current_size = 0;
635 uint32_t mid = 0;
636 for (uint32_t i = 0; i < idx; ++i) {
637 if ((current_size + sort_array[i].rec_len) > (real_size / 2)) {
638 new_hash = sort_array[i].hash;
639 mid = i;
640 break;
641 }
642
643 current_size += sort_array[i].rec_len;
644 }
645
646 uint32_t continued = 0;
647 if (new_hash == sort_array[mid-1].hash) {
648 continued = 1;
649 }
650
651 uint32_t offset = 0;
652 void *ptr;
653
654 // First part - to the old block
655 for (uint32_t i = 0; i < mid; ++i) {
656 ptr = old_data_block->data + offset;
657 memcpy(ptr, sort_array[i].dentry, sort_array[i].rec_len);
658
659 ext4_directory_entry_ll_t *tmp = ptr;
660 if (i < (mid - 1)) {
661 ext4_directory_entry_ll_set_entry_length(tmp, sort_array[i].rec_len);
662 } else {
663 ext4_directory_entry_ll_set_entry_length(tmp, block_size - offset);
664 }
665
666 offset += sort_array[i].rec_len;
667 }
668
669 // Second part - to the new block
670 offset = 0;
671 for (uint32_t i = mid; i < idx; ++i) {
672 ptr = new_data_block_tmp->data + offset;
673 memcpy(ptr, sort_array[i].dentry, sort_array[i].rec_len);
674
675 ext4_directory_entry_ll_t *tmp = ptr;
676 if (i < (idx - 1)) {
677 ext4_directory_entry_ll_set_entry_length(tmp, sort_array[i].rec_len);
678 } else {
679 ext4_directory_entry_ll_set_entry_length(tmp, block_size - offset);
680 }
681
682 offset += sort_array[i].rec_len;
683 }
684
685 old_data_block->dirty = true;
686 new_data_block_tmp->dirty = true;
687
688 free(sort_array);
689 free(entry_buffer);
690
691 ext4_directory_dx_insert_entry(index_block, new_hash + continued, new_iblock);
692
693 *new_data_block = new_data_block_tmp;
694
695 return EOK;
696}
697
698
699static int ext4_directory_dx_split_index(ext4_filesystem_t *fs,
700 ext4_inode_ref_t *inode_ref, ext4_directory_dx_block_t *dx_blocks,
701 ext4_directory_dx_block_t *dx_block)
702{
703 int rc;
704
705 ext4_directory_dx_entry_t *entries;
706 if (dx_block == dx_blocks) {
707 entries = ((ext4_directory_dx_root_t *) dx_block->block->data)->entries;
708 } else {
709 entries = ((ext4_directory_dx_node_t *) dx_block->block->data)->entries;
710 }
711
712 ext4_directory_dx_countlimit_t *countlimit =
713 (ext4_directory_dx_countlimit_t *)entries;
714 uint16_t leaf_limit = ext4_directory_dx_countlimit_get_limit(countlimit);
715 uint16_t leaf_count = ext4_directory_dx_countlimit_get_count(countlimit);
716
717 // Check if is necessary to split index block
718 if (leaf_limit == leaf_count) {
719 EXT4FS_DBG("need to split index block !!!");
720
721 unsigned int levels = dx_block - dx_blocks;
722
723 ext4_directory_dx_entry_t *root_entries =
724 ((ext4_directory_dx_root_t *)dx_blocks[0].block->data)->entries;
725
726 ext4_directory_dx_countlimit_t *root_countlimit =
727 (ext4_directory_dx_countlimit_t *)root_entries;
728 uint16_t root_limit =
729 ext4_directory_dx_countlimit_get_limit(root_countlimit);
730 uint16_t root_count =
731 ext4_directory_dx_countlimit_get_count(root_countlimit);
732
733 if ((levels > 0) && (root_limit == root_count)) {
734 EXT4FS_DBG("Directory index is full");
735 return ENOSPC;
736 }
737
738 uint32_t new_fblock;
739 uint32_t new_iblock;
740 rc = ext4_filesystem_append_inode_block(
741 inode_ref, &new_fblock, &new_iblock);
742 if (rc != EOK) {
743 return rc;
744 }
745
746 // New block allocated
747 block_t * new_block;
748 rc = block_get(&new_block, fs->device, new_fblock, BLOCK_FLAGS_NOREAD);
749 if (rc != EOK) {
750 return rc;
751 }
752
753 ext4_directory_dx_node_t *new_node = new_block->data;
754 ext4_directory_dx_entry_t *new_entries = new_node->entries;
755
756 uint32_t block_size = ext4_superblock_get_block_size(fs->superblock);
757
758 if (levels > 0) {
759 EXT4FS_DBG("split index leaf node");
760 uint32_t count_left = leaf_count / 2;
761 uint32_t count_right = leaf_count - count_left;
762 uint32_t hash_right =
763 ext4_directory_dx_entry_get_hash(entries + count_left);
764
765 memcpy((void *) new_entries, (void *) (entries + count_left),
766 count_right * sizeof(ext4_directory_dx_entry_t));
767
768 ext4_directory_dx_countlimit_t *left_countlimit =
769 (ext4_directory_dx_countlimit_t *)entries;
770 ext4_directory_dx_countlimit_t *right_countlimit =
771 (ext4_directory_dx_countlimit_t *)new_entries;
772
773 ext4_directory_dx_countlimit_set_count(left_countlimit, count_left);
774 ext4_directory_dx_countlimit_set_count(right_countlimit, count_right);
775
776 uint32_t entry_space = block_size - sizeof(ext4_fake_directory_entry_t);
777 uint32_t node_limit = entry_space / sizeof(ext4_directory_dx_entry_t);
778 ext4_directory_dx_countlimit_set_limit(right_countlimit, node_limit);
779
780 // Which index block is target for new entry
781 uint32_t position_index = (dx_block->position - dx_block->entries);
782 if (position_index >= count_left) {
783
784 dx_block->block->dirty = true;
785
786 block_t *block_tmp = dx_block->block;
787 dx_block->block = new_block;
788 dx_block->position = new_entries + position_index - count_left;
789 dx_block->entries = new_entries;
790
791 new_block = block_tmp;
792
793 }
794
795 ext4_directory_dx_insert_entry(dx_blocks, hash_right, new_iblock);
796
797 return block_put(new_block);
798
799 } else {
800 EXT4FS_DBG("create second level");
801
802 memcpy((void *) new_entries, (void *) entries,
803 leaf_count * sizeof(ext4_directory_dx_entry_t));
804
805 ext4_directory_dx_countlimit_t *new_countlimit =
806 (ext4_directory_dx_countlimit_t *)new_entries;
807
808 uint32_t entry_space = block_size - sizeof(ext4_fake_directory_entry_t);
809 uint32_t node_limit = entry_space / sizeof(ext4_directory_dx_entry_t);
810 ext4_directory_dx_countlimit_set_limit(new_countlimit, node_limit);
811
812 // Set values in root node
813 ext4_directory_dx_countlimit_t *new_root_countlimit =
814 (ext4_directory_dx_countlimit_t *)entries;
815
816 ext4_directory_dx_countlimit_set_count(new_root_countlimit, 1);
817 ext4_directory_dx_entry_set_block(entries, new_iblock);
818
819 ((ext4_directory_dx_root_t *)dx_blocks[0].block->data)->info.indirect_levels = 1;
820
821 /* Add new access path frame */
822 dx_block = dx_blocks + 1;
823 dx_block->position = dx_block->position - entries + new_entries;
824 dx_block->entries = new_entries;
825 dx_block->block = new_block;
826 }
827
828 }
829
830 return EOK;
831}
832
833int ext4_directory_dx_add_entry(ext4_inode_ref_t *parent,
834 ext4_inode_ref_t *child, const char *name)
835{
836 int rc = EOK;
837 int rc2 = EOK;
838
839 // get direct block 0 (index root)
840 uint32_t root_block_addr;
841 rc = ext4_filesystem_get_inode_data_block_index(parent, 0, &root_block_addr);
842 if (rc != EOK) {
843 return rc;
844 }
845
846 ext4_filesystem_t *fs = parent->fs;
847
848 block_t *root_block;
849 rc = block_get(&root_block, fs->device, root_block_addr, BLOCK_FLAGS_NONE);
850 if (rc != EOK) {
851 return rc;
852 }
853
854 uint32_t name_len = strlen(name);
855 ext4_hash_info_t hinfo;
856 rc = ext4_directory_hinfo_init(&hinfo, root_block, fs->superblock, name_len, name);
857 if (rc != EOK) {
858 block_put(root_block);
859 EXT4FS_DBG("hinfo initialization error");
860 return EXT4_ERR_BAD_DX_DIR;
861 }
862
863 // Hardcoded number 2 means maximum height of index tree !!!
864 ext4_directory_dx_block_t dx_blocks[2];
865 ext4_directory_dx_block_t *dx_block, *dx_it;
866 rc = ext4_directory_dx_get_leaf(&hinfo, parent, root_block, &dx_block, dx_blocks);
867 if (rc != EOK) {
868 EXT4FS_DBG("get leaf error");
869 rc = EXT4_ERR_BAD_DX_DIR;
870 goto release_index;
871 }
872
873
874 // Try to insert to existing data block
875 uint32_t leaf_block_idx = ext4_directory_dx_entry_get_block(dx_block->position);
876 uint32_t leaf_block_addr;
877 rc = ext4_filesystem_get_inode_data_block_index(parent, leaf_block_idx, &leaf_block_addr);
878 if (rc != EOK) {
879 goto release_index;
880 }
881
882
883 block_t *target_block;
884 rc = block_get(&target_block, fs->device, leaf_block_addr, BLOCK_FLAGS_NONE);
885 if (rc != EOK) {
886 goto release_index;
887 }
888
889
890 rc = ext4_directory_try_insert_entry(fs->superblock, target_block, child, name, name_len);
891 if (rc == EOK) {
892 goto release_target_index;
893 }
894
895 EXT4FS_DBG("no free space found");
896
897 rc = ext4_directory_dx_split_index(fs, parent, dx_blocks, dx_block);
898 if (rc != EOK) {
899 goto release_target_index;
900 }
901
902 block_t *new_block = NULL;
903 rc = ext4_directory_dx_split_data(fs, parent, &hinfo, target_block, dx_block, &new_block);
904 if (rc != EOK) {
905 rc2 = rc;
906 goto release_target_index;
907 }
908
909 // Where to save new entry
910 uint32_t new_block_hash = ext4_directory_dx_entry_get_hash(dx_block->position + 1);
911 if (hinfo.hash >= new_block_hash) {
912 rc = ext4_directory_try_insert_entry(fs->superblock, new_block, child, name, name_len);
913 } else {
914 rc = ext4_directory_try_insert_entry(fs->superblock, target_block, child, name, name_len);
915 }
916
917
918
919
920 rc = block_put(new_block);
921 if (rc != EOK) {
922 EXT4FS_DBG("error writing new block");
923 return rc;
924 }
925
926release_target_index:
927
928 rc2 = rc;
929
930 rc = block_put(target_block);
931 if (rc != EOK) {
932 EXT4FS_DBG("error writing target block");
933 return rc;
934 }
935
936release_index:
937
938 if (rc != EOK) {
939 rc2 = rc;
940 }
941
942 dx_it = dx_blocks;
943
944 while (dx_it <= dx_block) {
945 rc = block_put(dx_it->block);
946 if (rc != EOK) {
947 EXT4FS_DBG("error writing index block");
948 return rc;
949 }
950 dx_it++;
951 }
952
953 return rc2;
954}
955
956
957/**
958 * @}
959 */
Note: See TracBrowser for help on using the repository browser.