source: mainline/uspace/lib/ext4/libext4_directory_index.c@ ccac91e

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

splitting data block during adding dentry through index (not tested yet)
  • Property mode set to 100644
File size: 20.6 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
45
46uint8_t ext4_directory_dx_root_info_get_hash_version(
47 ext4_directory_dx_root_info_t *root_info)
48{
49 return root_info->hash_version;
50}
51
52void ext4_directory_dx_root_info_set_hash_version(
53 ext4_directory_dx_root_info_t *root_info, uint8_t version)
54{
55 root_info->hash_version = version;
56}
57
58uint8_t ext4_directory_dx_root_info_get_info_length(
59 ext4_directory_dx_root_info_t *root_info)
60{
61 return root_info->info_length;
62}
63
64void ext4_directory_dx_root_info_set_info_length(
65 ext4_directory_dx_root_info_t *root_info, uint8_t info_length)
66{
67 root_info->info_length = info_length;
68}
69
70uint8_t ext4_directory_dx_root_info_get_indirect_levels(
71 ext4_directory_dx_root_info_t *root_info)
72{
73 return root_info->indirect_levels;
74}
75
76void ext4_directory_dx_root_info_set_indirect_levels(
77 ext4_directory_dx_root_info_t *root_info, uint8_t levels)
78{
79 root_info->indirect_levels = levels;
80}
81
82uint16_t ext4_directory_dx_countlimit_get_limit(
83 ext4_directory_dx_countlimit_t *countlimit)
84{
85 return uint16_t_le2host(countlimit->limit);
86}
87
88void ext4_directory_dx_countlimit_set_limit(
89 ext4_directory_dx_countlimit_t *countlimit, uint16_t limit)
90{
91 countlimit->limit = host2uint16_t_le(limit);
92}
93
94uint16_t ext4_directory_dx_countlimit_get_count(
95 ext4_directory_dx_countlimit_t *countlimit)
96{
97 return uint16_t_le2host(countlimit->count);
98}
99
100void ext4_directory_dx_countlimit_set_count(
101 ext4_directory_dx_countlimit_t *countlimit, uint16_t count)
102{
103 countlimit->count = host2uint16_t_le(count);
104}
105
106uint32_t ext4_directory_dx_entry_get_hash(ext4_directory_dx_entry_t *entry)
107{
108 return uint32_t_le2host(entry->hash);
109}
110
111void ext4_directory_dx_entry_set_hash(ext4_directory_dx_entry_t *entry,
112 uint32_t hash)
113{
114 entry->hash = host2uint32_t_le(hash);
115}
116
117uint32_t ext4_directory_dx_entry_get_block(ext4_directory_dx_entry_t *entry)
118{
119 return uint32_t_le2host(entry->block);
120}
121
122void ext4_directory_dx_entry_set_block(ext4_directory_dx_entry_t *entry,
123 uint32_t block)
124{
125 entry->block = host2uint32_t_le(block);
126}
127
128
129/**************************************************************************/
130
131
132static int ext4_directory_hinfo_init(ext4_hash_info_t *hinfo, block_t *root_block,
133 ext4_superblock_t *sb, size_t name_len, const char *name)
134{
135
136 ext4_directory_dx_root_t *root = (ext4_directory_dx_root_t *)root_block->data;
137
138 if (root->info.hash_version != EXT4_HASH_VERSION_TEA &&
139 root->info.hash_version != EXT4_HASH_VERSION_HALF_MD4 &&
140 root->info.hash_version != EXT4_HASH_VERSION_LEGACY) {
141 return EXT4_ERR_BAD_DX_DIR;
142 }
143
144 // Check unused flags
145 if (root->info.unused_flags != 0) {
146 EXT4FS_DBG("ERR: unused_flags = \%u", root->info.unused_flags);
147 return EXT4_ERR_BAD_DX_DIR;
148 }
149
150 // Check indirect levels
151 if (root->info.indirect_levels > 1) {
152 EXT4FS_DBG("ERR: indirect_levels = \%u", root->info.indirect_levels);
153 return EXT4_ERR_BAD_DX_DIR;
154 }
155
156 uint32_t block_size = ext4_superblock_get_block_size(sb);
157
158 uint32_t entry_space = block_size;
159 entry_space -= 2 * sizeof(ext4_directory_dx_dot_entry_t);
160 entry_space -= sizeof(ext4_directory_dx_root_info_t);
161 entry_space = entry_space / sizeof(ext4_directory_dx_entry_t);
162
163 uint16_t limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)&root->entries);
164 if (limit != entry_space) {
165 return EXT4_ERR_BAD_DX_DIR;
166 }
167
168 hinfo->hash_version = ext4_directory_dx_root_info_get_hash_version(&root->info);
169 if ((hinfo->hash_version <= EXT4_HASH_VERSION_TEA)
170 && (ext4_superblock_has_flag(sb, EXT4_SUPERBLOCK_FLAGS_UNSIGNED_HASH))) {
171 // 3 is magic from ext4 linux implementation
172 hinfo->hash_version += 3;
173 }
174
175 hinfo->seed = ext4_superblock_get_hash_seed(sb);
176
177 if (name) {
178 ext4_hash_string(hinfo, name_len, name);
179 }
180
181 return EOK;
182}
183
184static int ext4_directory_dx_get_leaf(ext4_hash_info_t *hinfo,
185 ext4_filesystem_t *fs, ext4_inode_t *inode, block_t *root_block,
186 ext4_directory_dx_block_t **dx_block, ext4_directory_dx_block_t *dx_blocks)
187{
188 int rc;
189
190 ext4_directory_dx_block_t *tmp_dx_block = dx_blocks;
191
192 ext4_directory_dx_root_t *root = (ext4_directory_dx_root_t *)root_block->data;
193 ext4_directory_dx_entry_t *entries = (ext4_directory_dx_entry_t *)&root->entries;
194
195 uint16_t limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)entries);
196 uint8_t indirect_level = ext4_directory_dx_root_info_get_indirect_levels(&root->info);
197
198 block_t *tmp_block = root_block;
199 ext4_directory_dx_entry_t *p, *q, *m, *at;
200 while (true) {
201
202 uint16_t count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)entries);
203 if ((count == 0) || (count > limit)) {
204 return EXT4_ERR_BAD_DX_DIR;
205 }
206
207 p = entries + 1;
208 q = entries + count - 1;
209
210 while (p <= q) {
211 m = p + (q - p) / 2;
212 if (ext4_directory_dx_entry_get_hash(m) > hinfo->hash) {
213 q = m - 1;
214 } else {
215 p = m + 1;
216 }
217 }
218
219 at = p - 1;
220
221 tmp_dx_block->block = tmp_block;
222 tmp_dx_block->entries = entries;
223 tmp_dx_block->position = at;
224
225 if (indirect_level == 0) {
226 *dx_block = tmp_dx_block;
227 return EOK;
228 }
229
230 uint32_t next_block = ext4_directory_dx_entry_get_block(at);
231
232 indirect_level--;
233
234 uint32_t fblock;
235 rc = ext4_filesystem_get_inode_data_block_index(fs, inode, next_block, &fblock);
236 if (rc != EOK) {
237 return rc;
238 }
239
240 rc = block_get(&tmp_block, fs->device, fblock, BLOCK_FLAGS_NONE);
241 if (rc != EOK) {
242 return rc;
243 }
244
245 entries = ((ext4_directory_dx_node_t *) tmp_block->data)->entries;
246 limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)entries);
247
248 uint16_t entry_space = ext4_superblock_get_block_size(fs->superblock)
249 - sizeof(ext4_directory_dx_dot_entry_t);
250 entry_space = entry_space / sizeof(ext4_directory_dx_entry_t);
251
252
253 if (limit != entry_space) {
254 block_put(tmp_block);
255 return EXT4_ERR_BAD_DX_DIR;
256 }
257
258 ++tmp_dx_block;
259 }
260
261 // Unreachable
262 return EOK;
263}
264
265
266static int ext4_directory_dx_find_dir_entry(block_t *block,
267 ext4_superblock_t *sb, size_t name_len, const char *name,
268 ext4_directory_entry_ll_t **res_entry, aoff64_t *block_offset)
269{
270
271 aoff64_t offset = 0;
272 ext4_directory_entry_ll_t *dentry = (ext4_directory_entry_ll_t *)block->data;
273 uint8_t *addr_limit = block->data + ext4_superblock_get_block_size(sb);
274
275 while ((uint8_t *)dentry < addr_limit) {
276
277 if ((uint8_t*) dentry + name_len > addr_limit) {
278 break;
279 }
280
281 if (dentry->inode != 0) {
282 if (name_len == ext4_directory_entry_ll_get_name_length(sb, dentry)) {
283 // Compare names
284 if (bcmp((uint8_t *)name, dentry->name, name_len) == 0) {
285 *block_offset = offset;
286 *res_entry = dentry;
287 return 1;
288 }
289 }
290 }
291
292
293 // Goto next entry
294 uint16_t dentry_len = ext4_directory_entry_ll_get_entry_length(dentry);
295
296 if (dentry_len == 0) {
297 // Error
298 return -1;
299 }
300
301 offset += dentry_len;
302 dentry = (ext4_directory_entry_ll_t *)((uint8_t *)dentry + dentry_len);
303 }
304
305 return 0;
306}
307
308static int ext4_directory_dx_next_block(ext4_filesystem_t *fs, ext4_inode_t *inode, uint32_t hash,
309 ext4_directory_dx_block_t *handle, ext4_directory_dx_block_t *handles)
310{
311 int rc;
312
313
314 uint32_t num_handles = 0;
315 ext4_directory_dx_block_t *p = handle;
316
317 while (1) {
318
319 p->position++;
320 uint16_t count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)p->entries);
321
322 if (p->position < p->entries + count) {
323 break;
324 }
325
326 if (p == handles) {
327 return 0;
328 }
329
330 num_handles++;
331 p--;
332 }
333
334 uint32_t current_hash = ext4_directory_dx_entry_get_hash(p->position);
335
336 if ((hash & 1) == 0) {
337 if ((current_hash & ~1) != hash) {
338 return 0;
339 }
340 }
341
342
343 while (num_handles--) {
344
345 uint32_t block_idx = ext4_directory_dx_entry_get_block(p->position);
346 uint32_t block_addr;
347 rc = ext4_filesystem_get_inode_data_block_index(fs, inode, block_idx, &block_addr);
348 if (rc != EOK) {
349 return rc;
350 }
351
352 block_t *block;
353 rc = block_get(&block, fs->device, block_addr, BLOCK_FLAGS_NONE);
354 if (rc != EOK) {
355 return rc;
356 }
357
358 p++;
359
360 block_put(p->block);
361 p->block = block;
362 p->entries = ((ext4_directory_dx_node_t *) block->data)->entries;
363 p->position = p->entries;
364 }
365
366 return 1;
367
368}
369
370int ext4_directory_dx_find_entry(ext4_directory_iterator_t *it,
371 ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, size_t len, const char *name)
372{
373 int rc;
374
375 // get direct block 0 (index root)
376 uint32_t root_block_addr;
377 rc = ext4_filesystem_get_inode_data_block_index(fs, inode_ref->inode, 0, &root_block_addr);
378 if (rc != EOK) {
379 return rc;
380 }
381
382 block_t *root_block;
383 rc = block_get(&root_block, fs->device, root_block_addr, BLOCK_FLAGS_NONE);
384 if (rc != EOK) {
385 it->current_block = NULL;
386 return rc;
387 }
388
389 ext4_hash_info_t hinfo;
390 rc = ext4_directory_hinfo_init(&hinfo, root_block, fs->superblock, len, name);
391 if (rc != EOK) {
392 block_put(root_block);
393 return EXT4_ERR_BAD_DX_DIR;
394 }
395
396 // Hardcoded number 2 means maximum height of index tree !!!
397 ext4_directory_dx_block_t dx_blocks[2];
398 ext4_directory_dx_block_t *dx_block;
399 rc = ext4_directory_dx_get_leaf(&hinfo, fs, inode_ref->inode, root_block, &dx_block, dx_blocks);
400 if (rc != EOK) {
401 block_put(root_block);
402 return EXT4_ERR_BAD_DX_DIR;
403 }
404
405
406 do {
407
408 uint32_t leaf_block_idx = ext4_directory_dx_entry_get_block(dx_block->position);
409 uint32_t leaf_block_addr;
410 rc = ext4_filesystem_get_inode_data_block_index(fs, inode_ref->inode, leaf_block_idx, &leaf_block_addr);
411 if (rc != EOK) {
412 return EXT4_ERR_BAD_DX_DIR;
413 }
414
415 block_t *leaf_block;
416 rc = block_get(&leaf_block, fs->device, leaf_block_addr, BLOCK_FLAGS_NONE);
417 if (rc != EOK) {
418 return EXT4_ERR_BAD_DX_DIR;
419 }
420
421 aoff64_t block_offset;
422 ext4_directory_entry_ll_t *res_dentry;
423 rc = ext4_directory_dx_find_dir_entry(leaf_block, fs->superblock, len, name,
424 &res_dentry, &block_offset);
425
426 // Found => return it
427 if (rc == 1) {
428 it->fs = fs;
429 it->inode_ref = inode_ref;
430 it->current_block = leaf_block;
431 it->current_offset = block_offset;
432 it->current = res_dentry;
433 return EOK;
434 }
435
436 block_put(leaf_block);
437
438 // ERROR - corrupted index
439 if (rc == -1) {
440 // TODO cleanup
441 return EXT4_ERR_BAD_DX_DIR;
442 }
443
444 rc = ext4_directory_dx_next_block(fs, inode_ref->inode, hinfo.hash, dx_block, &dx_blocks[0]);
445 if (rc < 0) {
446 // TODO cleanup
447 return EXT4_ERR_BAD_DX_DIR;
448 }
449
450 } while (rc == 1);
451
452 return ENOENT;
453}
454
455typedef struct ext4_dx_sort_entry {
456 uint32_t hash;
457 uint32_t rec_len;
458 ext4_directory_entry_ll_t *dentry;
459} ext4_dx_sort_entry_t;
460
461static int dx_entry_comparator(void *arg1, void *arg2, void *dummy)
462{
463 ext4_dx_sort_entry_t *entry1 = arg1;
464 ext4_dx_sort_entry_t *entry2 = arg2;
465
466 if (entry1->hash == entry2->hash) {
467 return 0;
468 }
469
470 if (entry1->hash < entry2->hash) {
471 return -1;
472 } else {
473 return 1;
474 }
475
476}
477
478static int ext4_directory_dx_split_data(ext4_filesystem_t *fs,
479 ext4_inode_ref_t *inode_ref, ext4_hash_info_t *hinfo,
480 block_t *old_data_block, ext4_directory_dx_block_t *index_block, block_t **new_data_block)
481{
482 int rc;
483
484 uint32_t block_size = ext4_superblock_get_block_size(fs->superblock);
485 void *entry_buffer = malloc(block_size);
486 if (entry_buffer == NULL) {
487 return ENOMEM;
488 }
489
490 // Copy data to buffer
491 memcpy(entry_buffer, old_data_block->data, block_size);
492
493 ext4_directory_dx_countlimit_t *countlimit =
494 (ext4_directory_dx_countlimit_t *)index_block->entries;
495 uint32_t entry_count = ext4_directory_dx_countlimit_get_count(countlimit);
496 ext4_dx_sort_entry_t *sort_array = malloc(entry_count);
497 if (sort_array == NULL) {
498 free(entry_buffer);
499 return ENOMEM;
500 }
501
502 ext4_directory_entry_ll_t *dentry = old_data_block->data;
503
504 int idx = 0;
505 uint32_t real_size = 0;
506 void *entry_buffer_ptr = entry_buffer;
507 while ((void *)dentry < old_data_block->data + block_size) {
508 char *name = (char *)dentry->name;
509 uint8_t len = ext4_directory_entry_ll_get_name_length(fs->superblock, dentry);
510 uint32_t hash = ext4_hash_string(hinfo, len, name);
511
512 uint32_t rec_len = 8 + len;
513
514 if ((rec_len % 4) != 0) {
515 rec_len += 4 - (rec_len % 4);
516 }
517
518 memcpy(entry_buffer_ptr, dentry, rec_len);
519
520 sort_array[idx].dentry = entry_buffer_ptr;
521 sort_array[idx].rec_len = rec_len;
522 sort_array[idx].hash = hash;
523
524 entry_buffer_ptr += rec_len;
525 real_size += rec_len;
526
527 idx++;
528 dentry = (void *)dentry + ext4_directory_entry_ll_get_entry_length(dentry);
529 }
530
531 qsort(sort_array, entry_count, sizeof(ext4_dx_sort_entry_t), dx_entry_comparator, NULL);
532
533 uint32_t new_fblock;
534 rc = ext4_directory_append_block(fs, inode_ref, &new_fblock);
535 if (rc != EOK) {
536 free(sort_array);
537 free(entry_buffer);
538 return rc;
539 }
540
541 // Load new block
542 block_t *new_data_block_tmp;
543 rc = block_get(&new_data_block_tmp, fs->device, new_fblock, BLOCK_FLAGS_NOREAD);
544 if (rc != EOK) {
545 free(sort_array);
546 free(entry_buffer);
547 return rc;
548 }
549
550 // Distribute entries to splitted blocks (by size)
551
552 uint32_t new_hash = 0;
553 uint32_t current_size = 0;
554 int mid = 0;
555 for (int i = 0; i < idx; ++i) {
556 if (current_size > real_size / 2) {
557 new_hash = sort_array[i].hash;
558 mid = i;
559 break;
560 }
561
562 current_size += sort_array[i].rec_len;
563 }
564
565 uint32_t offset = 0;
566 void *ptr;
567
568 // First part - to the old block
569 for (int i = 0; i < mid; ++i) {
570 ptr = old_data_block->data + offset;
571 memcpy(ptr, sort_array[i].dentry, sort_array[i].rec_len);
572
573 ext4_directory_entry_ll_t *tmp = ptr;
574 if (i < (mid - 1)) {
575 ext4_directory_entry_ll_set_entry_length(tmp, sort_array[i].rec_len);
576 } else {
577 ext4_directory_entry_ll_set_entry_length(tmp, block_size - offset);
578 }
579
580 offset += sort_array[i].rec_len;
581 }
582
583 // Second part - to the new block
584 offset = 0;
585 for (int i = mid; i < idx; ++i) {
586 ptr = new_data_block_tmp->data + offset;
587 memcpy(ptr, sort_array[i].dentry, sort_array[i].rec_len);
588
589 ext4_directory_entry_ll_t *tmp = ptr;
590 if (i < (idx - 1)) {
591 ext4_directory_entry_ll_set_entry_length(tmp, sort_array[i].rec_len);
592 } else {
593 ext4_directory_entry_ll_set_entry_length(tmp, block_size - offset);
594 }
595
596 offset += sort_array[i].rec_len;
597 }
598
599 old_data_block->dirty = true;
600 new_data_block_tmp->dirty = true;
601
602 free(sort_array);
603 free(entry_buffer);
604
605 // TODO add new entry to index block
606 index_block->position++;
607
608 ext4_directory_dx_entry_set_block(index_block->position, new_fblock);
609 ext4_directory_dx_entry_set_hash(index_block->position, new_hash);
610
611 index_block->block->dirty = true;
612
613 *new_data_block = new_data_block_tmp;
614
615 return EOK;
616}
617
618
619int ext4_directory_dx_add_entry(ext4_filesystem_t *fs,
620 ext4_inode_ref_t *parent, ext4_inode_ref_t *child,
621 size_t name_size, const char *name)
622{
623 int rc;
624
625 // get direct block 0 (index root)
626 uint32_t root_block_addr;
627 rc = ext4_filesystem_get_inode_data_block_index(fs, parent->inode, 0, &root_block_addr);
628 if (rc != EOK) {
629 return rc;
630 }
631
632 block_t *root_block;
633 rc = block_get(&root_block, fs->device, root_block_addr, BLOCK_FLAGS_NONE);
634 if (rc != EOK) {
635 return rc;
636 }
637
638 ext4_hash_info_t hinfo;
639 rc = ext4_directory_hinfo_init(&hinfo, root_block, fs->superblock, name_size, name);
640 if (rc != EOK) {
641 block_put(root_block);
642 return EXT4_ERR_BAD_DX_DIR;
643 }
644
645 // Hardcoded number 2 means maximum height of index tree !!!
646 ext4_directory_dx_block_t dx_blocks[2];
647 ext4_directory_dx_block_t *dx_block;
648 rc = ext4_directory_dx_get_leaf(&hinfo, fs, parent->inode, root_block, &dx_block, dx_blocks);
649 if (rc != EOK) {
650 block_put(root_block);
651 return EXT4_ERR_BAD_DX_DIR;
652 }
653
654
655 // Try to insert to existing data block
656 uint32_t leaf_block_idx = ext4_directory_dx_entry_get_block(dx_block->position);
657 uint32_t leaf_block_addr;
658 rc = ext4_filesystem_get_inode_data_block_index(fs, parent->inode, leaf_block_idx, &leaf_block_addr);
659 if (rc != EOK) {
660 return EXT4_ERR_BAD_DX_DIR;
661 }
662
663
664 block_t *target_block;
665 rc = block_get(&target_block, fs->device, leaf_block_addr, BLOCK_FLAGS_NONE);
666 if (rc != EOK) {
667 return EXT4_ERR_BAD_DX_DIR;
668 }
669
670 uint32_t block_size = ext4_superblock_get_block_size(fs->superblock);
671 uint16_t required_len = 8 + name_size + (4 - name_size % 4);
672
673 ext4_directory_entry_ll_t *de = target_block->data;
674 ext4_directory_entry_ll_t *stop = target_block->data + block_size;
675
676 while (de < stop) {
677
678 uint32_t de_inode = ext4_directory_entry_ll_get_inode(de);
679 uint16_t de_rec_len = ext4_directory_entry_ll_get_entry_length(de);
680
681 if ((de_inode == 0) && (de_rec_len >= required_len)) {
682 ext4_directory_write_entry(fs->superblock, de, de_rec_len,
683 child, name, name_size);
684 target_block->dirty = true;
685 rc = block_put(target_block);
686 if (rc != EOK) {
687 return EXT4_ERR_BAD_DX_DIR;
688 }
689 return EOK;
690 }
691
692 if (de_inode != 0) {
693 uint16_t used_name_len = ext4_directory_entry_ll_get_name_length(
694 fs->superblock, de);
695
696 uint16_t used_space = 8 + used_name_len;
697 if ((used_name_len % 4) != 0) {
698 used_space += 4 - (used_name_len % 4);
699 }
700 uint16_t free_space = de_rec_len - used_space;
701
702 if (free_space >= required_len) {
703
704 EXT4FS_DBG("rec_len = \%u, used_space = \%u, free space = \%u", de_rec_len, used_space, free_space);
705
706 // Cut tail of current entry
707 ext4_directory_entry_ll_set_entry_length(de, used_space);
708 ext4_directory_entry_ll_t *new_entry = (void *)de + used_space;
709 ext4_directory_write_entry(fs->superblock, new_entry,
710 free_space, child, name, name_size);
711 target_block->dirty = true;
712 rc = block_put(target_block);
713 if (rc != EOK) {
714 return EXT4_ERR_BAD_DX_DIR;
715 }
716 return EOK;
717
718 }
719
720 }
721
722 de = (void *)de + de_rec_len;
723 }
724
725 EXT4FS_DBG("no free space found");
726
727 ext4_directory_dx_entry_t *entries = ((ext4_directory_dx_node_t *) dx_block->block->data)->entries;
728 uint16_t leaf_limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)entries);
729 uint16_t leaf_count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)entries);
730
731 ext4_directory_dx_entry_t *root_entries = ((ext4_directory_dx_node_t *) dx_blocks[0].block->data)->entries;
732
733 if (leaf_limit == leaf_count) {
734 EXT4FS_DBG("need to split index block !!!");
735
736 unsigned int levels = dx_block - dx_blocks;
737
738 uint16_t root_limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)root_entries);
739 uint16_t root_count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)root_entries);
740
741 if ((levels > 0) && (root_limit == root_count)) {
742 EXT4FS_DBG("Directory index is full");
743
744 // ENOSPC - cleanup !!!
745 return ENOSPC;
746 }
747
748 uint32_t fblock;
749 rc = ext4_directory_append_block(fs, parent, &fblock);
750 if (rc != EOK) {
751 // TODO error
752 }
753
754 // New block allocated
755 block_t * new_block;
756 rc = block_get(&new_block, fs->device, fblock, BLOCK_FLAGS_NOREAD);
757 if (rc != EOK) {
758 // TODO error
759 }
760
761 memset(new_block->data, 0, block_size);
762
763 if (levels > 0) {
764 EXT4FS_DBG("split index");
765 } else {
766 EXT4FS_DBG("create second level");
767 }
768 }
769
770 block_t *new_block;
771 rc = ext4_directory_dx_split_data(fs, parent, &hinfo, target_block, dx_block, &new_block);
772 if (rc != EOK) {
773 // TODO error
774 }
775
776 // TODO Where to save new entry
777
778
779 // TODO
780 return EOK;
781
782}
783
784
785/**
786 * @}
787 */
Note: See TracBrowser for help on using the repository browser.