source: mainline/uspace/lib/ext4/libext4_directory.c@ e7ed26be

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

simplied headers of more functions, improved bg_ref and inode_ref structures, added block group checksumming and fixed bug in block_group values updating

  • Property mode set to 100644
File size: 15.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.c
35 * @brief Ext4 directory structure operations.
36 */
37
38#include <byteorder.h>
39#include <errno.h>
40#include <malloc.h>
41#include <string.h>
42#include "libext4.h"
43
44static int ext4_directory_iterator_set(ext4_directory_iterator_t *,
45 uint32_t);
46
47
48uint32_t ext4_directory_entry_ll_get_inode(ext4_directory_entry_ll_t *de)
49{
50 return uint32_t_le2host(de->inode);
51}
52
53void ext4_directory_entry_ll_set_inode(ext4_directory_entry_ll_t *de,
54 uint32_t inode)
55{
56 de->inode = host2uint32_t_le(inode);
57}
58
59uint16_t ext4_directory_entry_ll_get_entry_length(
60 ext4_directory_entry_ll_t *de)
61{
62 return uint16_t_le2host(de->entry_length);
63}
64
65void ext4_directory_entry_ll_set_entry_length(ext4_directory_entry_ll_t *de,
66 uint16_t length)
67{
68 de->entry_length = host2uint16_t_le(length);
69}
70
71uint16_t ext4_directory_entry_ll_get_name_length(
72 ext4_superblock_t *sb, ext4_directory_entry_ll_t *de)
73{
74 if (ext4_superblock_get_rev_level(sb) == 0 &&
75 ext4_superblock_get_minor_rev_level(sb) < 5) {
76
77 return ((uint16_t)de->name_length_high) << 8 |
78 ((uint16_t)de->name_length);
79
80 }
81 return de->name_length;
82
83}
84
85void ext4_directory_entry_ll_set_name_length(ext4_superblock_t *sb,
86 ext4_directory_entry_ll_t *de, uint16_t length)
87{
88 de->name_length = (length << 8) >> 8;
89
90 if (ext4_superblock_get_rev_level(sb) == 0 &&
91 ext4_superblock_get_minor_rev_level(sb) < 5) {
92
93 de->name_length_high = length >> 8;
94 }
95}
96
97uint8_t ext4_directory_entry_ll_get_inode_type(
98 ext4_superblock_t *sb, ext4_directory_entry_ll_t *de)
99{
100 if (ext4_superblock_get_rev_level(sb) > 0 ||
101 ext4_superblock_get_minor_rev_level(sb) >= 5) {
102
103 return de->inode_type;
104 }
105
106 return EXT4_DIRECTORY_FILETYPE_UNKNOWN;
107
108}
109
110void ext4_directory_entry_ll_set_inode_type(
111 ext4_superblock_t *sb, ext4_directory_entry_ll_t *de, uint8_t type)
112{
113 if (ext4_superblock_get_rev_level(sb) > 0 ||
114 ext4_superblock_get_minor_rev_level(sb) >= 5) {
115
116 de->inode_type = type;
117 }
118
119 // else do nothing
120
121}
122
123int ext4_directory_iterator_init(ext4_directory_iterator_t *it,
124 ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, aoff64_t pos)
125{
126 it->inode_ref = inode_ref;
127 it->fs = fs;
128 it->current = NULL;
129 it->current_offset = 0;
130 it->current_block = NULL;
131
132 return ext4_directory_iterator_seek(it, pos);
133}
134
135
136int ext4_directory_iterator_next(ext4_directory_iterator_t *it)
137{
138 uint16_t skip;
139
140 assert(it->current != NULL);
141
142 skip = ext4_directory_entry_ll_get_entry_length(it->current);
143
144 return ext4_directory_iterator_seek(it, it->current_offset + skip);
145}
146
147
148int ext4_directory_iterator_seek(ext4_directory_iterator_t *it, aoff64_t pos)
149{
150 int rc;
151
152 uint64_t size = ext4_inode_get_size(it->fs->superblock, it->inode_ref->inode);
153
154 /* The iterator is not valid until we seek to the desired position */
155 it->current = NULL;
156
157 /* Are we at the end? */
158 if (pos >= size) {
159 if (it->current_block) {
160 rc = block_put(it->current_block);
161 it->current_block = NULL;
162 if (rc != EOK) {
163 return rc;
164 }
165 }
166
167 it->current_offset = pos;
168 return EOK;
169 }
170
171 uint32_t block_size = ext4_superblock_get_block_size(it->fs->superblock);
172 aoff64_t current_block_idx = it->current_offset / block_size;
173 aoff64_t next_block_idx = pos / block_size;
174
175 /* If we don't have a block or are moving accross block boundary,
176 * we need to get another block
177 */
178 if (it->current_block == NULL || current_block_idx != next_block_idx) {
179 if (it->current_block) {
180 rc = block_put(it->current_block);
181 it->current_block = NULL;
182 if (rc != EOK) {
183 return rc;
184 }
185 }
186
187 uint32_t next_block_phys_idx;
188 rc = ext4_filesystem_get_inode_data_block_index(it->inode_ref,
189 next_block_idx, &next_block_phys_idx);
190 if (rc != EOK) {
191 return rc;
192 }
193
194 rc = block_get(&it->current_block, it->fs->device, next_block_phys_idx,
195 BLOCK_FLAGS_NONE);
196 if (rc != EOK) {
197 it->current_block = NULL;
198 return rc;
199 }
200 }
201
202 it->current_offset = pos;
203
204 return ext4_directory_iterator_set(it, block_size);
205}
206
207static int ext4_directory_iterator_set(ext4_directory_iterator_t *it,
208 uint32_t block_size)
209{
210
211 it->current = NULL;
212
213 uint32_t offset_in_block = it->current_offset % block_size;
214
215 /* Ensure proper alignment */
216 if ((offset_in_block % 4) != 0) {
217 return EIO;
218 }
219
220 /* Ensure that the core of the entry does not overflow the block */
221 if (offset_in_block > block_size - 8) {
222 return EIO;
223 }
224
225 ext4_directory_entry_ll_t *entry = it->current_block->data + offset_in_block;
226
227 /* Ensure that the whole entry does not overflow the block */
228 uint16_t length = ext4_directory_entry_ll_get_entry_length(entry);
229 if (offset_in_block + length > block_size) {
230 return EIO;
231 }
232
233 /* Ensure the name length is not too large */
234 if (ext4_directory_entry_ll_get_name_length(it->fs->superblock,
235 entry) > length-8) {
236 return EIO;
237 }
238
239 it->current = entry;
240 return EOK;
241}
242
243
244int ext4_directory_iterator_fini(ext4_directory_iterator_t *it)
245{
246 int rc;
247
248 it->fs = NULL;
249 it->inode_ref = NULL;
250 it->current = NULL;
251
252 if (it->current_block) {
253 rc = block_put(it->current_block);
254 if (rc != EOK) {
255 return rc;
256 }
257 }
258
259 return EOK;
260}
261
262int ext4_directory_append_block(ext4_inode_ref_t *inode_ref,
263 uint32_t *fblock, uint32_t *iblock)
264{
265 int rc;
266
267 ext4_superblock_t *sb = inode_ref->fs->superblock;
268
269 // Compute next block index and allocate data block
270 uint64_t inode_size = ext4_inode_get_size(sb, inode_ref->inode);
271 uint32_t block_size = ext4_superblock_get_block_size(sb);
272
273 assert(inode_size % block_size == 0);
274
275 // Logical blocks are numbered from 0
276 uint32_t new_block_idx = inode_size / block_size;
277
278 uint32_t phys_block;
279 rc = ext4_balloc_alloc_block(inode_ref, &phys_block);
280 if (rc != EOK) {
281 return rc;
282 }
283
284 rc = ext4_filesystem_set_inode_data_block_index(inode_ref, new_block_idx, phys_block);
285 if (rc != EOK) {
286 ext4_balloc_free_block(inode_ref, phys_block);
287 return rc;
288 }
289
290 ext4_inode_set_size(inode_ref->inode, inode_size + block_size);
291
292 inode_ref->dirty = true;
293
294 *fblock = phys_block;
295 *iblock = new_block_idx;
296 return EOK;
297}
298
299void ext4_directory_write_entry(ext4_superblock_t *sb,
300 ext4_directory_entry_ll_t *entry, uint16_t entry_len,
301 ext4_inode_ref_t *child, const char *name, size_t name_len)
302{
303 ext4_directory_entry_ll_set_inode(entry, child->index);
304 ext4_directory_entry_ll_set_entry_length(entry, entry_len);
305 ext4_directory_entry_ll_set_name_length(sb, entry, name_len);
306
307 if (ext4_inode_is_type(sb, child->inode, EXT4_INODE_MODE_DIRECTORY)) {
308 ext4_directory_entry_ll_set_inode_type(
309 sb, entry, EXT4_DIRECTORY_FILETYPE_DIR);
310 } else {
311 ext4_directory_entry_ll_set_inode_type(
312 sb, entry, EXT4_DIRECTORY_FILETYPE_REG_FILE);
313 }
314 memcpy(entry->name, name, name_len);
315}
316
317int ext4_directory_add_entry(ext4_inode_ref_t * parent,
318 const char *name, ext4_inode_ref_t *child)
319{
320 int rc;
321
322 EXT4FS_DBG("adding entry to directory \%u [ino = \%u, name = \%s]", parent->index, child->index, name);
323
324 ext4_filesystem_t *fs = parent->fs;
325
326 // Index adding (if allowed)
327 if (ext4_superblock_has_feature_compatible(fs->superblock, EXT4_FEATURE_COMPAT_DIR_INDEX) &&
328 ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX)) {
329
330 rc = ext4_directory_dx_add_entry(parent, child, name);
331
332 // Check if index is not corrupted
333 if (rc != EXT4_ERR_BAD_DX_DIR) {
334
335 if (rc != EOK) {
336 return rc;
337 }
338
339 return EOK;
340 }
341
342 // Needed to clear dir index flag
343 ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX);
344 parent->dirty = true;
345
346 EXT4FS_DBG("index is corrupted - doing linear algorithm, index flag cleared");
347 }
348
349 // Linear algorithm
350
351 uint32_t iblock, fblock;
352 uint32_t block_size = ext4_superblock_get_block_size(fs->superblock);
353 uint32_t inode_size = ext4_inode_get_size(fs->superblock, parent->inode);
354 uint32_t total_blocks = inode_size / block_size;
355
356 uint32_t name_len = strlen(name);
357
358 // Find block, where is space for new entry
359 bool success = false;
360 for (iblock = 0; iblock < total_blocks; ++iblock) {
361
362 rc = ext4_filesystem_get_inode_data_block_index(parent, iblock, &fblock);
363 if (rc != EOK) {
364 return rc;
365 }
366
367 block_t *block;
368 rc = block_get(&block, fs->device, fblock, BLOCK_FLAGS_NONE);
369 if (rc != EOK) {
370 return rc;
371 }
372
373 rc = ext4_directory_try_insert_entry(fs->superblock, block, child, name, name_len);
374 if (rc == EOK) {
375 success = true;
376 }
377
378 rc = block_put(block);
379 if (rc != EOK) {
380 return rc;
381 }
382
383 if (success) {
384 return EOK;
385 }
386 }
387
388 // No free block found - needed to allocate next block
389
390 rc = ext4_directory_append_block(parent, &fblock, &iblock);
391 if (rc != EOK) {
392 return rc;
393 }
394
395 // Load new block
396 block_t *new_block;
397 rc = block_get(&new_block, fs->device, fblock, BLOCK_FLAGS_NOREAD);
398 if (rc != EOK) {
399 return rc;
400 }
401
402 // Fill block with zeroes
403 memset(new_block->data, 0, block_size);
404 ext4_directory_entry_ll_t *block_entry = new_block->data;
405 ext4_directory_write_entry(fs->superblock, block_entry, block_size, child, name, name_len);
406
407 // Save new block
408 new_block->dirty = true;
409 rc = block_put(new_block);
410 if (rc != EOK) {
411 return rc;
412 }
413
414 return EOK;
415}
416
417int ext4_directory_find_entry(ext4_directory_search_result_t *result,
418 ext4_inode_ref_t *parent, const char *name)
419{
420 int rc;
421 uint32_t name_len = strlen(name);
422
423 ext4_superblock_t *sb = parent->fs->superblock;
424
425 // Index search
426 if (ext4_superblock_has_feature_compatible(sb, EXT4_FEATURE_COMPAT_DIR_INDEX) &&
427 ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX)) {
428
429 rc = ext4_directory_dx_find_entry(result, parent, name_len, name);
430
431 // Check if index is not corrupted
432 if (rc != EXT4_ERR_BAD_DX_DIR) {
433
434 if (rc != EOK) {
435 return rc;
436 }
437 return EOK;
438 }
439
440 EXT4FS_DBG("index is corrupted - doing linear search");
441 }
442
443 uint32_t iblock, fblock;
444 uint32_t block_size = ext4_superblock_get_block_size(sb);
445 uint32_t inode_size = ext4_inode_get_size(sb, parent->inode);
446 uint32_t total_blocks = inode_size / block_size;
447
448 for (iblock = 0; iblock < total_blocks; ++iblock) {
449
450 rc = ext4_filesystem_get_inode_data_block_index(parent, iblock, &fblock);
451 if (rc != EOK) {
452 return rc;
453 }
454
455 block_t *block;
456 rc = block_get(&block, parent->fs->device, fblock, BLOCK_FLAGS_NONE);
457 if (rc != EOK) {
458 return rc;
459 }
460
461 // find block entry
462 ext4_directory_entry_ll_t *res_entry;
463 rc = ext4_directory_find_in_block(block, sb, name_len, name, &res_entry);
464 if (rc == EOK) {
465 result->block = block;
466 result->dentry = res_entry;
467 return EOK;
468 }
469
470 rc = block_put(block);
471 if (rc != EOK) {
472 return rc;
473 }
474 }
475
476 result->block = NULL;
477 result->dentry = NULL;
478
479 return ENOENT;
480}
481
482
483int ext4_directory_remove_entry(ext4_inode_ref_t *parent, const char *name)
484{
485 int rc;
486
487 if (!ext4_inode_is_type(parent->fs->superblock, parent->inode,
488 EXT4_INODE_MODE_DIRECTORY)) {
489 return ENOTDIR;
490 }
491
492 ext4_directory_search_result_t result;
493 rc = ext4_directory_find_entry(&result, parent, name);
494 if (rc != EOK) {
495 return rc;
496 }
497
498 ext4_directory_entry_ll_set_inode(result.dentry, 0);
499
500 uint32_t pos = (void *)result.dentry - result.block->data;
501
502 uint32_t offset = 0;
503 if (pos != 0) {
504
505 ext4_directory_entry_ll_t *tmp_dentry = result.block->data;
506 uint16_t tmp_dentry_length =
507 ext4_directory_entry_ll_get_entry_length(tmp_dentry);
508
509 while ((offset + tmp_dentry_length) < pos) {
510 offset += ext4_directory_entry_ll_get_entry_length(tmp_dentry);
511 tmp_dentry = result.block->data + offset;
512 tmp_dentry_length =
513 ext4_directory_entry_ll_get_entry_length(tmp_dentry);
514 }
515
516 assert(tmp_dentry_length + offset == pos);
517
518 uint16_t del_entry_length =
519 ext4_directory_entry_ll_get_entry_length(result.dentry);
520 ext4_directory_entry_ll_set_entry_length(tmp_dentry,
521 tmp_dentry_length + del_entry_length);
522
523 }
524
525 result.block->dirty = true;
526
527 return ext4_directory_destroy_result(&result);
528}
529
530
531int ext4_directory_try_insert_entry(ext4_superblock_t *sb,
532 block_t *target_block, ext4_inode_ref_t *child,
533 const char *name, uint32_t name_len)
534{
535 uint32_t block_size = ext4_superblock_get_block_size(sb);
536 uint16_t required_len = sizeof(ext4_fake_directory_entry_t) + name_len;
537 if ((required_len % 4) != 0) {
538 required_len += 4 - (required_len % 4);
539 }
540
541 ext4_directory_entry_ll_t *dentry = target_block->data;
542 ext4_directory_entry_ll_t *stop = target_block->data + block_size;
543
544 while (dentry < stop) {
545
546 uint32_t inode = ext4_directory_entry_ll_get_inode(dentry);
547 uint16_t rec_len = ext4_directory_entry_ll_get_entry_length(dentry);
548
549 if ((inode == 0) && (rec_len >= required_len)) {
550 ext4_directory_write_entry(sb, dentry, rec_len, child, name, name_len);
551 target_block->dirty = true;
552 return EOK;
553 }
554
555 if (inode != 0) {
556 uint16_t used_name_len =
557 ext4_directory_entry_ll_get_name_length(sb, dentry);
558
559 uint16_t used_space =
560 sizeof(ext4_fake_directory_entry_t) + used_name_len;
561 if ((used_name_len % 4) != 0) {
562 used_space += 4 - (used_name_len % 4);
563 }
564 uint16_t free_space = rec_len - used_space;
565
566 if (free_space >= required_len) {
567
568 // Cut tail of current entry
569 ext4_directory_entry_ll_set_entry_length(dentry, used_space);
570 ext4_directory_entry_ll_t *new_entry =
571 (void *)dentry + used_space;
572 ext4_directory_write_entry(sb, new_entry,
573 free_space, child, name, name_len);
574
575 target_block->dirty = true;
576 return EOK;
577 }
578 }
579
580 dentry = (void *)dentry + rec_len;
581 }
582
583 return ENOSPC;
584}
585
586int ext4_directory_find_in_block(block_t *block,
587 ext4_superblock_t *sb, size_t name_len, const char *name,
588 ext4_directory_entry_ll_t **res_entry)
589{
590
591 ext4_directory_entry_ll_t *dentry = (ext4_directory_entry_ll_t *)block->data;
592 uint8_t *addr_limit = block->data + ext4_superblock_get_block_size(sb);
593
594 while ((uint8_t *)dentry < addr_limit) {
595
596 if ((uint8_t*) dentry + name_len > addr_limit) {
597 break;
598 }
599
600 if (dentry->inode != 0) {
601 if (name_len == ext4_directory_entry_ll_get_name_length(sb, dentry)) {
602 // Compare names
603 if (bcmp((uint8_t *)name, dentry->name, name_len) == 0) {
604 *res_entry = dentry;
605 return EOK;
606 }
607 }
608 }
609
610 // Goto next entry
611 uint16_t dentry_len = ext4_directory_entry_ll_get_entry_length(dentry);
612
613 if (dentry_len == 0) {
614 return EINVAL;
615 }
616
617 dentry = (ext4_directory_entry_ll_t *)((uint8_t *)dentry + dentry_len);
618 }
619
620 return ENOENT;
621}
622
623int ext4_directory_destroy_result(ext4_directory_search_result_t *result)
624{
625 if (result->block) {
626 return block_put(result->block);
627 }
628
629 return EOK;
630}
631
632/**
633 * @}
634 */
Note: See TracBrowser for help on using the repository browser.