source: mainline/uspace/lib/ext4/libext4_directory_index.c@ 5c83612b

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

adding directory entry using index tree (actually without splitting index block)
  • Property mode set to 100644
File size: 16.2 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 <string.h>
41#include "libext4.h"
42
43
44uint8_t ext4_directory_dx_root_info_get_hash_version(
45 ext4_directory_dx_root_info_t *root_info)
46{
47 return root_info->hash_version;
48}
49
50void ext4_directory_dx_root_info_set_hash_version(
51 ext4_directory_dx_root_info_t *root_info, uint8_t version)
52{
53 root_info->hash_version = version;
54}
55
56uint8_t ext4_directory_dx_root_info_get_info_length(
57 ext4_directory_dx_root_info_t *root_info)
58{
59 return root_info->info_length;
60}
61
62void ext4_directory_dx_root_info_set_info_length(
63 ext4_directory_dx_root_info_t *root_info, uint8_t info_length)
64{
65 root_info->info_length = info_length;
66}
67
68uint8_t ext4_directory_dx_root_info_get_indirect_levels(
69 ext4_directory_dx_root_info_t *root_info)
70{
71 return root_info->indirect_levels;
72}
73
74void ext4_directory_dx_root_info_set_indirect_levels(
75 ext4_directory_dx_root_info_t *root_info, uint8_t levels)
76{
77 root_info->indirect_levels = levels;
78}
79
80uint16_t ext4_directory_dx_countlimit_get_limit(
81 ext4_directory_dx_countlimit_t *countlimit)
82{
83 return uint16_t_le2host(countlimit->limit);
84}
85
86void ext4_directory_dx_countlimit_set_limit(
87 ext4_directory_dx_countlimit_t *countlimit, uint16_t limit)
88{
89 countlimit->limit = host2uint16_t_le(limit);
90}
91
92uint16_t ext4_directory_dx_countlimit_get_count(
93 ext4_directory_dx_countlimit_t *countlimit)
94{
95 return uint16_t_le2host(countlimit->count);
96}
97
98void ext4_directory_dx_countlimit_set_count(
99 ext4_directory_dx_countlimit_t *countlimit, uint16_t count)
100{
101 countlimit->count = host2uint16_t_le(count);
102}
103
104uint32_t ext4_directory_dx_entry_get_hash(ext4_directory_dx_entry_t *entry)
105{
106 return uint32_t_le2host(entry->hash);
107}
108
109void ext4_directory_dx_entry_set_hash(ext4_directory_dx_entry_t *entry,
110 uint32_t hash)
111{
112 entry->hash = host2uint32_t_le(hash);
113}
114
115uint32_t ext4_directory_dx_entry_get_block(ext4_directory_dx_entry_t *entry)
116{
117 return uint32_t_le2host(entry->block);
118}
119
120void ext4_directory_dx_entry_set_block(ext4_directory_dx_entry_t *entry,
121 uint32_t block)
122{
123 entry->block = host2uint32_t_le(block);
124}
125
126
127/**************************************************************************/
128
129
130static int ext4_directory_hinfo_init(ext4_hash_info_t *hinfo, block_t *root_block,
131 ext4_superblock_t *sb, size_t name_len, const char *name)
132{
133
134 ext4_directory_dx_root_t *root = (ext4_directory_dx_root_t *)root_block->data;
135
136 if (root->info.hash_version != EXT4_HASH_VERSION_TEA &&
137 root->info.hash_version != EXT4_HASH_VERSION_HALF_MD4 &&
138 root->info.hash_version != EXT4_HASH_VERSION_LEGACY) {
139 return EXT4_ERR_BAD_DX_DIR;
140 }
141
142 // Check unused flags
143 if (root->info.unused_flags != 0) {
144 EXT4FS_DBG("ERR: unused_flags = \%u", root->info.unused_flags);
145 return EXT4_ERR_BAD_DX_DIR;
146 }
147
148 // Check indirect levels
149 if (root->info.indirect_levels > 1) {
150 EXT4FS_DBG("ERR: indirect_levels = \%u", root->info.indirect_levels);
151 return EXT4_ERR_BAD_DX_DIR;
152 }
153
154 uint32_t block_size = ext4_superblock_get_block_size(sb);
155
156 uint32_t entry_space = block_size;
157 entry_space -= 2 * sizeof(ext4_directory_dx_dot_entry_t);
158 entry_space -= sizeof(ext4_directory_dx_root_info_t);
159 entry_space = entry_space / sizeof(ext4_directory_dx_entry_t);
160
161 uint16_t limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)&root->entries);
162 if (limit != entry_space) {
163 return EXT4_ERR_BAD_DX_DIR;
164 }
165
166 hinfo->hash_version = ext4_directory_dx_root_info_get_hash_version(&root->info);
167 if ((hinfo->hash_version <= EXT4_HASH_VERSION_TEA)
168 && (ext4_superblock_has_flag(sb, EXT4_SUPERBLOCK_FLAGS_UNSIGNED_HASH))) {
169 // 3 is magic from ext4 linux implementation
170 hinfo->hash_version += 3;
171 }
172
173 hinfo->seed = ext4_superblock_get_hash_seed(sb);
174
175 if (name) {
176 ext4_hash_string(hinfo, name_len, name);
177 }
178
179 return EOK;
180}
181
182static int ext4_directory_dx_get_leaf(ext4_hash_info_t *hinfo,
183 ext4_filesystem_t *fs, ext4_inode_t *inode, block_t *root_block,
184 ext4_directory_dx_block_t **dx_block, ext4_directory_dx_block_t *dx_blocks)
185{
186 int rc;
187
188 ext4_directory_dx_block_t *tmp_dx_block = dx_blocks;
189
190 ext4_directory_dx_root_t *root = (ext4_directory_dx_root_t *)root_block->data;
191 ext4_directory_dx_entry_t *entries = (ext4_directory_dx_entry_t *)&root->entries;
192
193 uint16_t limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)entries);
194 uint8_t indirect_level = ext4_directory_dx_root_info_get_indirect_levels(&root->info);
195
196 block_t *tmp_block = root_block;
197 ext4_directory_dx_entry_t *p, *q, *m, *at;
198 while (true) {
199
200 uint16_t count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)entries);
201 if ((count == 0) || (count > limit)) {
202 return EXT4_ERR_BAD_DX_DIR;
203 }
204
205 p = entries + 1;
206 q = entries + count - 1;
207
208 while (p <= q) {
209 m = p + (q - p) / 2;
210 if (ext4_directory_dx_entry_get_hash(m) > hinfo->hash) {
211 q = m - 1;
212 } else {
213 p = m + 1;
214 }
215 }
216
217 at = p - 1;
218
219 tmp_dx_block->block = tmp_block;
220 tmp_dx_block->entries = entries;
221 tmp_dx_block->position = at;
222
223 if (indirect_level == 0) {
224 *dx_block = tmp_dx_block;
225 return EOK;
226 }
227
228 uint32_t next_block = ext4_directory_dx_entry_get_block(at);
229
230 indirect_level--;
231
232 uint32_t fblock;
233 rc = ext4_filesystem_get_inode_data_block_index(fs, inode, next_block, &fblock);
234 if (rc != EOK) {
235 return rc;
236 }
237
238 rc = block_get(&tmp_block, fs->device, fblock, BLOCK_FLAGS_NONE);
239 if (rc != EOK) {
240 return rc;
241 }
242
243 entries = ((ext4_directory_dx_node_t *) tmp_block->data)->entries;
244 limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)entries);
245
246 uint16_t entry_space = ext4_superblock_get_block_size(fs->superblock)
247 - sizeof(ext4_directory_dx_dot_entry_t);
248 entry_space = entry_space / sizeof(ext4_directory_dx_entry_t);
249
250
251 if (limit != entry_space) {
252 block_put(tmp_block);
253 return EXT4_ERR_BAD_DX_DIR;
254 }
255
256 ++tmp_dx_block;
257 }
258
259 // Unreachable
260 return EOK;
261}
262
263
264static int ext4_directory_dx_find_dir_entry(block_t *block,
265 ext4_superblock_t *sb, size_t name_len, const char *name,
266 ext4_directory_entry_ll_t **res_entry, aoff64_t *block_offset)
267{
268
269 aoff64_t offset = 0;
270 ext4_directory_entry_ll_t *dentry = (ext4_directory_entry_ll_t *)block->data;
271 uint8_t *addr_limit = block->data + ext4_superblock_get_block_size(sb);
272
273 while ((uint8_t *)dentry < addr_limit) {
274
275 if ((uint8_t*) dentry + name_len > addr_limit) {
276 break;
277 }
278
279 if (dentry->inode != 0) {
280 if (name_len == ext4_directory_entry_ll_get_name_length(sb, dentry)) {
281 // Compare names
282 if (bcmp((uint8_t *)name, dentry->name, name_len) == 0) {
283 *block_offset = offset;
284 *res_entry = dentry;
285 return 1;
286 }
287 }
288 }
289
290
291 // Goto next entry
292 uint16_t dentry_len = ext4_directory_entry_ll_get_entry_length(dentry);
293
294 if (dentry_len == 0) {
295 // TODO error
296 return -1;
297 }
298
299 offset += dentry_len;
300 dentry = (ext4_directory_entry_ll_t *)((uint8_t *)dentry + dentry_len);
301 }
302
303 return 0;
304}
305
306static int ext4_directory_dx_next_block(ext4_filesystem_t *fs, ext4_inode_t *inode, uint32_t hash,
307 ext4_directory_dx_block_t *handle, ext4_directory_dx_block_t *handles)
308{
309 int rc;
310
311
312 uint32_t num_handles = 0;
313 ext4_directory_dx_block_t *p = handle;
314
315 while (1) {
316
317 p->position++;
318 uint16_t count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)p->entries);
319
320 if (p->position < p->entries + count) {
321 break;
322 }
323
324 if (p == handles) {
325 return 0;
326 }
327
328 num_handles++;
329 p--;
330 }
331
332 uint32_t current_hash = ext4_directory_dx_entry_get_hash(p->position);
333
334 if ((hash & 1) == 0) {
335 if ((current_hash & ~1) != hash) {
336 return 0;
337 }
338 }
339
340
341 while (num_handles--) {
342
343 uint32_t block_idx = ext4_directory_dx_entry_get_block(p->position);
344 uint32_t block_addr;
345 rc = ext4_filesystem_get_inode_data_block_index(fs, inode, block_idx, &block_addr);
346 if (rc != EOK) {
347 return rc;
348 }
349
350 block_t *block;
351 rc = block_get(&block, fs->device, block_addr, BLOCK_FLAGS_NONE);
352 if (rc != EOK) {
353 return rc;
354 }
355
356 p++;
357
358 block_put(p->block);
359 p->block = block;
360 p->entries = ((ext4_directory_dx_node_t *) block->data)->entries;
361 p->position = p->entries;
362 }
363
364 return 1;
365
366}
367
368int ext4_directory_dx_find_entry(ext4_directory_iterator_t *it,
369 ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, size_t len, const char *name)
370{
371 int rc;
372
373 // get direct block 0 (index root)
374 uint32_t root_block_addr;
375 rc = ext4_filesystem_get_inode_data_block_index(fs, inode_ref->inode, 0, &root_block_addr);
376 if (rc != EOK) {
377 return rc;
378 }
379
380 block_t *root_block;
381 rc = block_get(&root_block, fs->device, root_block_addr, BLOCK_FLAGS_NONE);
382 if (rc != EOK) {
383 it->current_block = NULL;
384 return rc;
385 }
386
387 ext4_hash_info_t hinfo;
388 rc = ext4_directory_hinfo_init(&hinfo, root_block, fs->superblock, len, name);
389 if (rc != EOK) {
390 block_put(root_block);
391 return EXT4_ERR_BAD_DX_DIR;
392 }
393
394 // Hardcoded number 2 means maximum height of index tree !!!
395 ext4_directory_dx_block_t dx_blocks[2];
396 ext4_directory_dx_block_t *dx_block;
397 rc = ext4_directory_dx_get_leaf(&hinfo, fs, inode_ref->inode, root_block, &dx_block, dx_blocks);
398 if (rc != EOK) {
399 block_put(root_block);
400 return EXT4_ERR_BAD_DX_DIR;
401 }
402
403
404 do {
405
406 uint32_t leaf_block_idx = ext4_directory_dx_entry_get_block(dx_block->position);
407 uint32_t leaf_block_addr;
408 rc = ext4_filesystem_get_inode_data_block_index(fs, inode_ref->inode, leaf_block_idx, &leaf_block_addr);
409 if (rc != EOK) {
410 return EXT4_ERR_BAD_DX_DIR;
411 }
412
413 block_t *leaf_block;
414 rc = block_get(&leaf_block, fs->device, leaf_block_addr, BLOCK_FLAGS_NONE);
415 if (rc != EOK) {
416 return EXT4_ERR_BAD_DX_DIR;
417 }
418
419 aoff64_t block_offset;
420 ext4_directory_entry_ll_t *res_dentry;
421 rc = ext4_directory_dx_find_dir_entry(leaf_block, fs->superblock, len, name,
422 &res_dentry, &block_offset);
423
424 // Found => return it
425 if (rc == 1) {
426 it->fs = fs;
427 it->inode_ref = inode_ref;
428 it->current_block = leaf_block;
429 it->current_offset = block_offset;
430 it->current = res_dentry;
431 return EOK;
432 }
433
434 block_put(leaf_block);
435
436 // ERROR - corrupted index
437 if (rc == -1) {
438 // TODO cleanup
439 return EXT4_ERR_BAD_DX_DIR;
440 }
441
442 rc = ext4_directory_dx_next_block(fs, inode_ref->inode, hinfo.hash, dx_block, &dx_blocks[0]);
443 if (rc < 0) {
444 // TODO cleanup
445 return EXT4_ERR_BAD_DX_DIR;
446 }
447
448 } while (rc == 1);
449
450 return ENOENT;
451}
452
453int ext4_directory_dx_add_entry(ext4_filesystem_t *fs,
454 ext4_inode_ref_t *parent, ext4_inode_ref_t *child,
455 size_t name_size, const char *name)
456{
457 int rc;
458
459 // get direct block 0 (index root)
460 uint32_t root_block_addr;
461 rc = ext4_filesystem_get_inode_data_block_index(fs, parent->inode, 0, &root_block_addr);
462 if (rc != EOK) {
463 return rc;
464 }
465
466 block_t *root_block;
467 rc = block_get(&root_block, fs->device, root_block_addr, BLOCK_FLAGS_NONE);
468 if (rc != EOK) {
469 return rc;
470 }
471
472 ext4_hash_info_t hinfo;
473 rc = ext4_directory_hinfo_init(&hinfo, root_block, fs->superblock, name_size, name);
474 if (rc != EOK) {
475 block_put(root_block);
476 return EXT4_ERR_BAD_DX_DIR;
477 }
478
479 // Hardcoded number 2 means maximum height of index tree !!!
480 ext4_directory_dx_block_t dx_blocks[2];
481 ext4_directory_dx_block_t *dx_block;
482 rc = ext4_directory_dx_get_leaf(&hinfo, fs, parent->inode, root_block, &dx_block, dx_blocks);
483 if (rc != EOK) {
484 block_put(root_block);
485 return EXT4_ERR_BAD_DX_DIR;
486 }
487
488
489 // Try to insert to existing data block
490 uint32_t leaf_block_idx = ext4_directory_dx_entry_get_block(dx_block->position);
491 uint32_t leaf_block_addr;
492 rc = ext4_filesystem_get_inode_data_block_index(fs, parent->inode, leaf_block_idx, &leaf_block_addr);
493 if (rc != EOK) {
494 return EXT4_ERR_BAD_DX_DIR;
495 }
496
497
498 block_t *target;
499 rc = block_get(&target, fs->device, leaf_block_addr, BLOCK_FLAGS_NONE);
500 if (rc != EOK) {
501 return EXT4_ERR_BAD_DX_DIR;
502 }
503
504 uint32_t block_size = ext4_superblock_get_block_size(fs->superblock);
505 uint16_t required_len = 8 + name_size + (4 - name_size % 4);
506
507 ext4_directory_entry_ll_t *de = target->data;
508 ext4_directory_entry_ll_t *stop = target->data + block_size;
509
510 EXT4FS_DBG("before while de = \%u, stop = \%u", (uint32_t)de, (uint32_t)stop);
511
512 while (de < stop) {
513
514 EXT4FS_DBG("before while de = \%u", (uint32_t)de);
515
516 uint32_t de_inode = ext4_directory_entry_ll_get_inode(de);
517 uint16_t de_rec_len = ext4_directory_entry_ll_get_entry_length(de);
518
519 if ((de_inode == 0) && (de_rec_len >= required_len)) {
520 ext4_directory_write_entry(fs->superblock, de, de_rec_len,
521 child, name, name_size);
522 target->dirty = true;
523 rc = block_put(target);
524 if (rc != EOK) {
525 return EXT4_ERR_BAD_DX_DIR;
526 }
527 return EOK;
528 }
529
530 if (de_inode != 0) {
531 uint16_t used_name_len = ext4_directory_entry_ll_get_name_length(
532 fs->superblock, de);
533
534 uint16_t used_space = 8 + used_name_len;
535 if ((used_name_len % 4) != 0) {
536 used_space += 4 - (used_name_len % 4);
537 }
538 uint16_t free_space = de_rec_len - used_space;
539
540 if (free_space >= required_len) {
541
542 EXT4FS_DBG("rec_len = \%u, used_space = \%u, free space = \%u", de_rec_len, used_space, free_space);
543
544 // Cut tail of current entry
545 ext4_directory_entry_ll_set_entry_length(de, used_space);
546 ext4_directory_entry_ll_t *new_entry = (void *)de + used_space;
547 ext4_directory_write_entry(fs->superblock, new_entry,
548 free_space, child, name, name_size);
549 target->dirty = true;
550 rc = block_put(target);
551 if (rc != EOK) {
552 return EXT4_ERR_BAD_DX_DIR;
553 }
554 return EOK;
555
556 }
557
558 }
559
560 de = (void *)de + de_rec_len;
561 }
562
563
564 EXT4FS_DBG("ERRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR");
565 return EXT4_ERR_BAD_DX_DIR;
566
567 // if ENOSPC in block -> next code
568
569 ext4_directory_dx_entry_t *entries = ((ext4_directory_dx_node_t *) dx_block->block->data)->entries;
570 uint16_t limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)entries);
571 uint16_t count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)entries);
572
573 ext4_directory_dx_entry_t *root_entries = ((ext4_directory_dx_node_t *) dx_blocks[0].block->data)->entries;
574
575 if (limit == count) {
576 EXT4FS_DBG("need to split index block !!!");
577
578 unsigned int levels = dx_block - dx_blocks;
579
580 uint16_t root_limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)root_entries);
581 uint16_t root_count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)root_entries);
582
583 if ((levels > 0) && (root_limit == root_count)) {
584 EXT4FS_DBG("Directory index is full");
585
586 // ENOSPC - cleanup !!!
587 return ENOSPC;
588 }
589
590
591 }
592
593 // TODO
594 return EOK;
595
596}
597
598
599/**
600 * @}
601 */
Note: See TracBrowser for help on using the repository browser.