source: mainline/uspace/lib/ext4/libext4_directory_index.c@ 476bf2f6

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

duplicate code extraction
  • Property mode set to 100644
File size: 16.4 KB
RevLine 
[0dc91833]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
[c25e39b]35 * @brief Ext4 directory index operations.
[0dc91833]36 */
37
[343ccfd]38#include <byteorder.h>
[0dc91833]39#include <errno.h>
[5c83612b]40#include <string.h>
[0dc91833]41#include "libext4.h"
42
[343ccfd]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
[0dc91833]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
[d9bbe45]134 ext4_directory_dx_root_t *root = (ext4_directory_dx_root_t *)root_block->data;
[0dc91833]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
[d9bbe45]154 uint32_t block_size = ext4_superblock_get_block_size(sb);
[0dc91833]155
[d9bbe45]156 uint32_t entry_space = block_size;
[0dc91833]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
[d9bbe45]161 uint16_t limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)&root->entries);
[0dc91833]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;
[d9bbe45]187
[0dc91833]188 ext4_directory_dx_block_t *tmp_dx_block = dx_blocks;
189
[d9bbe45]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;
[0dc91833]192
[d9bbe45]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);
[0dc91833]195
[d9bbe45]196 block_t *tmp_block = root_block;
197 ext4_directory_dx_entry_t *p, *q, *m, *at;
[0dc91833]198 while (true) {
199
[d9bbe45]200 uint16_t count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)entries);
[0dc91833]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
[d9bbe45]228 uint32_t next_block = ext4_directory_dx_entry_get_block(at);
[0dc91833]229
230 indirect_level--;
231
[d9bbe45]232 uint32_t fblock;
[0dc91833]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
[d9bbe45]246 uint16_t entry_space = ext4_superblock_get_block_size(fs->superblock)
247 - sizeof(ext4_directory_dx_dot_entry_t);
[0dc91833]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
[d9bbe45]264static int ext4_directory_dx_find_dir_entry(block_t *block,
[0dc91833]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
[d9bbe45]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);
[0dc91833]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
[d9bbe45]292 uint16_t dentry_len = ext4_directory_entry_ll_get_entry_length(dentry);
[0dc91833]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{
[d9bbe45]309 int rc;
310
[0dc91833]311
[d9bbe45]312 uint32_t num_handles = 0;
313 ext4_directory_dx_block_t *p = handle;
[0dc91833]314
315 while (1) {
316
317 p->position++;
[d9bbe45]318 uint16_t count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)p->entries);
[0dc91833]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
[d9bbe45]332 uint32_t current_hash = ext4_directory_dx_entry_get_hash(p->position);
[0dc91833]333
334 if ((hash & 1) == 0) {
335 if ((current_hash & ~1) != hash) {
336 return 0;
337 }
338 }
339
[d9bbe45]340
[0dc91833]341 while (num_handles--) {
342
[d9bbe45]343 uint32_t block_idx = ext4_directory_dx_entry_get_block(p->position);
344 uint32_t block_addr;
[0dc91833]345 rc = ext4_filesystem_get_inode_data_block_index(fs, inode, block_idx, &block_addr);
346 if (rc != EOK) {
347 return rc;
348 }
349
[d9bbe45]350 block_t *block;
[0dc91833]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)
[d9bbe45]374 uint32_t root_block_addr;
[0dc91833]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
[d9bbe45]380 block_t *root_block;
[0dc91833]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
[d9bbe45]387 ext4_hash_info_t hinfo;
[0dc91833]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
[565b6ff]394 // Hardcoded number 2 means maximum height of index tree !!!
[d9bbe45]395 ext4_directory_dx_block_t dx_blocks[2];
396 ext4_directory_dx_block_t *dx_block;
[0dc91833]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
[d9bbe45]404 do {
[0dc91833]405
[d9bbe45]406 uint32_t leaf_block_idx = ext4_directory_dx_entry_get_block(dx_block->position);
407 uint32_t leaf_block_addr;
[0dc91833]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
[d9bbe45]413 block_t *leaf_block;
[0dc91833]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
[d9bbe45]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,
[0dc91833]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
[565b6ff]453int ext4_directory_dx_add_entry(ext4_filesystem_t *fs,
[5c83612b]454 ext4_inode_ref_t *parent, ext4_inode_ref_t *child,
455 size_t name_size, const char *name)
[565b6ff]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
[5c83612b]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 while (de < stop) {
511
512 uint32_t de_inode = ext4_directory_entry_ll_get_inode(de);
513 uint16_t de_rec_len = ext4_directory_entry_ll_get_entry_length(de);
514
515 if ((de_inode == 0) && (de_rec_len >= required_len)) {
516 ext4_directory_write_entry(fs->superblock, de, de_rec_len,
517 child, name, name_size);
518 target->dirty = true;
519 rc = block_put(target);
520 if (rc != EOK) {
521 return EXT4_ERR_BAD_DX_DIR;
522 }
523 return EOK;
524 }
525
526 if (de_inode != 0) {
527 uint16_t used_name_len = ext4_directory_entry_ll_get_name_length(
528 fs->superblock, de);
529
530 uint16_t used_space = 8 + used_name_len;
531 if ((used_name_len % 4) != 0) {
532 used_space += 4 - (used_name_len % 4);
533 }
534 uint16_t free_space = de_rec_len - used_space;
535
536 if (free_space >= required_len) {
537
538 EXT4FS_DBG("rec_len = \%u, used_space = \%u, free space = \%u", de_rec_len, used_space, free_space);
539
540 // Cut tail of current entry
541 ext4_directory_entry_ll_set_entry_length(de, used_space);
542 ext4_directory_entry_ll_t *new_entry = (void *)de + used_space;
543 ext4_directory_write_entry(fs->superblock, new_entry,
544 free_space, child, name, name_size);
545 target->dirty = true;
546 rc = block_put(target);
547 if (rc != EOK) {
548 return EXT4_ERR_BAD_DX_DIR;
549 }
550 return EOK;
551
552 }
553
554 }
555
556 de = (void *)de + de_rec_len;
557 }
558
[1ebb66f]559 EXT4FS_DBG("no free space found");
[5c83612b]560
561 ext4_directory_dx_entry_t *entries = ((ext4_directory_dx_node_t *) dx_block->block->data)->entries;
[1ebb66f]562 uint16_t leaf_limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)entries);
563 uint16_t leaf_count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)entries);
[5c83612b]564
565 ext4_directory_dx_entry_t *root_entries = ((ext4_directory_dx_node_t *) dx_blocks[0].block->data)->entries;
566
[1ebb66f]567 if (leaf_limit == leaf_count) {
[5c83612b]568 EXT4FS_DBG("need to split index block !!!");
569
570 unsigned int levels = dx_block - dx_blocks;
571
572 uint16_t root_limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)root_entries);
573 uint16_t root_count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)root_entries);
574
575 if ((levels > 0) && (root_limit == root_count)) {
576 EXT4FS_DBG("Directory index is full");
577
578 // ENOSPC - cleanup !!!
579 return ENOSPC;
580 }
581
[1ebb66f]582 uint32_t fblock;
[476bf2f6]583 rc = ext4_directory_append_block(fs, parent, &fblock);
[1ebb66f]584 if (rc != EOK) {
[476bf2f6]585 // TODO error
[1ebb66f]586 }
587
588 // New block allocated
589 block_t * new_block;
590 rc = block_get(&new_block, fs->device, fblock, BLOCK_FLAGS_NOREAD);
591 if (rc != EOK) {
592 // TODO error
593 }
[5c83612b]594
[1ebb66f]595 memset(new_block->data, 0, block_size);
596
597 if (levels > 0) {
598 EXT4FS_DBG("split index");
599 } else {
600 EXT4FS_DBG("create second level");
601 }
[5c83612b]602 }
603
604 // TODO
605 return EOK;
[565b6ff]606
607}
[0dc91833]608
609
610/**
611 * @}
612 */
Note: See TracBrowser for help on using the repository browser.