source: mainline/uspace/lib/ext4/libext4_directory.c@ 5b16912

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

Moved append block function because of more common usage in the next commits
  • Property mode set to 100644
File size: 14.7 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
262void ext4_directory_write_entry(ext4_superblock_t *sb,
263 ext4_directory_entry_ll_t *entry, uint16_t entry_len,
264 ext4_inode_ref_t *child, const char *name, size_t name_len)
265{
266 ext4_directory_entry_ll_set_inode(entry, child->index);
267 ext4_directory_entry_ll_set_entry_length(entry, entry_len);
268 ext4_directory_entry_ll_set_name_length(sb, entry, name_len);
269
270 if (ext4_inode_is_type(sb, child->inode, EXT4_INODE_MODE_DIRECTORY)) {
271 ext4_directory_entry_ll_set_inode_type(
272 sb, entry, EXT4_DIRECTORY_FILETYPE_DIR);
273 } else {
274 ext4_directory_entry_ll_set_inode_type(
275 sb, entry, EXT4_DIRECTORY_FILETYPE_REG_FILE);
276 }
277 memcpy(entry->name, name, name_len);
278}
279
280int ext4_directory_add_entry(ext4_inode_ref_t * parent,
281 const char *name, ext4_inode_ref_t *child)
282{
283 int rc;
284
285 EXT4FS_DBG("adding entry to directory \%u [ino = \%u, name = \%s]", parent->index, child->index, name);
286
287 ext4_filesystem_t *fs = parent->fs;
288
289 // Index adding (if allowed)
290 if (ext4_superblock_has_feature_compatible(fs->superblock, EXT4_FEATURE_COMPAT_DIR_INDEX) &&
291 ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX)) {
292
293 rc = ext4_directory_dx_add_entry(parent, child, name);
294
295 // Check if index is not corrupted
296 if (rc != EXT4_ERR_BAD_DX_DIR) {
297
298 if (rc != EOK) {
299 return rc;
300 }
301
302 return EOK;
303 }
304
305 // Needed to clear dir index flag
306 ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX);
307 parent->dirty = true;
308
309 EXT4FS_DBG("index is corrupted - doing linear algorithm, index flag cleared");
310 }
311
312 // Linear algorithm
313
314 uint32_t iblock, fblock;
315 uint32_t block_size = ext4_superblock_get_block_size(fs->superblock);
316 uint32_t inode_size = ext4_inode_get_size(fs->superblock, parent->inode);
317 uint32_t total_blocks = inode_size / block_size;
318
319 uint32_t name_len = strlen(name);
320
321 // Find block, where is space for new entry
322 bool success = false;
323 for (iblock = 0; iblock < total_blocks; ++iblock) {
324
325 rc = ext4_filesystem_get_inode_data_block_index(parent, iblock, &fblock);
326 if (rc != EOK) {
327 return rc;
328 }
329
330 block_t *block;
331 rc = block_get(&block, fs->device, fblock, BLOCK_FLAGS_NONE);
332 if (rc != EOK) {
333 return rc;
334 }
335
336 rc = ext4_directory_try_insert_entry(fs->superblock, block, child, name, name_len);
337 if (rc == EOK) {
338 success = true;
339 }
340
341 rc = block_put(block);
342 if (rc != EOK) {
343 return rc;
344 }
345
346 if (success) {
347 return EOK;
348 }
349 }
350
351 // No free block found - needed to allocate next block
352
353 rc = ext4_filesystem_append_inode_block(parent, &fblock, &iblock);
354 if (rc != EOK) {
355 return rc;
356 }
357
358 // Load new block
359 block_t *new_block;
360 rc = block_get(&new_block, fs->device, fblock, BLOCK_FLAGS_NOREAD);
361 if (rc != EOK) {
362 return rc;
363 }
364
365 // Fill block with zeroes
366 memset(new_block->data, 0, block_size);
367 ext4_directory_entry_ll_t *block_entry = new_block->data;
368 ext4_directory_write_entry(fs->superblock, block_entry, block_size, child, name, name_len);
369
370 // Save new block
371 new_block->dirty = true;
372 rc = block_put(new_block);
373 if (rc != EOK) {
374 return rc;
375 }
376
377 return EOK;
378}
379
380int ext4_directory_find_entry(ext4_directory_search_result_t *result,
381 ext4_inode_ref_t *parent, const char *name)
382{
383 int rc;
384 uint32_t name_len = strlen(name);
385
386 ext4_superblock_t *sb = parent->fs->superblock;
387
388 // Index search
389 if (ext4_superblock_has_feature_compatible(sb, EXT4_FEATURE_COMPAT_DIR_INDEX) &&
390 ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX)) {
391
392 rc = ext4_directory_dx_find_entry(result, parent, name_len, name);
393
394 // Check if index is not corrupted
395 if (rc != EXT4_ERR_BAD_DX_DIR) {
396
397 if (rc != EOK) {
398 return rc;
399 }
400 return EOK;
401 }
402
403 EXT4FS_DBG("index is corrupted - doing linear search");
404 }
405
406 uint32_t iblock, fblock;
407 uint32_t block_size = ext4_superblock_get_block_size(sb);
408 uint32_t inode_size = ext4_inode_get_size(sb, parent->inode);
409 uint32_t total_blocks = inode_size / block_size;
410
411 for (iblock = 0; iblock < total_blocks; ++iblock) {
412
413 rc = ext4_filesystem_get_inode_data_block_index(parent, iblock, &fblock);
414 if (rc != EOK) {
415 return rc;
416 }
417
418 block_t *block;
419 rc = block_get(&block, parent->fs->device, fblock, BLOCK_FLAGS_NONE);
420 if (rc != EOK) {
421 return rc;
422 }
423
424 // find block entry
425 ext4_directory_entry_ll_t *res_entry;
426 rc = ext4_directory_find_in_block(block, sb, name_len, name, &res_entry);
427 if (rc == EOK) {
428 result->block = block;
429 result->dentry = res_entry;
430 return EOK;
431 }
432
433 rc = block_put(block);
434 if (rc != EOK) {
435 return rc;
436 }
437 }
438
439 result->block = NULL;
440 result->dentry = NULL;
441
442 return ENOENT;
443}
444
445
446int ext4_directory_remove_entry(ext4_inode_ref_t *parent, const char *name)
447{
448 int rc;
449
450 if (!ext4_inode_is_type(parent->fs->superblock, parent->inode,
451 EXT4_INODE_MODE_DIRECTORY)) {
452 return ENOTDIR;
453 }
454
455 ext4_directory_search_result_t result;
456 rc = ext4_directory_find_entry(&result, parent, name);
457 if (rc != EOK) {
458 return rc;
459 }
460
461 ext4_directory_entry_ll_set_inode(result.dentry, 0);
462
463 uint32_t pos = (void *)result.dentry - result.block->data;
464
465 uint32_t offset = 0;
466 if (pos != 0) {
467
468 ext4_directory_entry_ll_t *tmp_dentry = result.block->data;
469 uint16_t tmp_dentry_length =
470 ext4_directory_entry_ll_get_entry_length(tmp_dentry);
471
472 while ((offset + tmp_dentry_length) < pos) {
473 offset += ext4_directory_entry_ll_get_entry_length(tmp_dentry);
474 tmp_dentry = result.block->data + offset;
475 tmp_dentry_length =
476 ext4_directory_entry_ll_get_entry_length(tmp_dentry);
477 }
478
479 assert(tmp_dentry_length + offset == pos);
480
481 uint16_t del_entry_length =
482 ext4_directory_entry_ll_get_entry_length(result.dentry);
483 ext4_directory_entry_ll_set_entry_length(tmp_dentry,
484 tmp_dentry_length + del_entry_length);
485
486 }
487
488 result.block->dirty = true;
489
490 return ext4_directory_destroy_result(&result);
491}
492
493
494int ext4_directory_try_insert_entry(ext4_superblock_t *sb,
495 block_t *target_block, ext4_inode_ref_t *child,
496 const char *name, uint32_t name_len)
497{
498 uint32_t block_size = ext4_superblock_get_block_size(sb);
499 uint16_t required_len = sizeof(ext4_fake_directory_entry_t) + name_len;
500 if ((required_len % 4) != 0) {
501 required_len += 4 - (required_len % 4);
502 }
503
504 ext4_directory_entry_ll_t *dentry = target_block->data;
505 ext4_directory_entry_ll_t *stop = target_block->data + block_size;
506
507 while (dentry < stop) {
508
509 uint32_t inode = ext4_directory_entry_ll_get_inode(dentry);
510 uint16_t rec_len = ext4_directory_entry_ll_get_entry_length(dentry);
511
512 if ((inode == 0) && (rec_len >= required_len)) {
513 ext4_directory_write_entry(sb, dentry, rec_len, child, name, name_len);
514 target_block->dirty = true;
515 return EOK;
516 }
517
518 if (inode != 0) {
519 uint16_t used_name_len =
520 ext4_directory_entry_ll_get_name_length(sb, dentry);
521
522 uint16_t used_space =
523 sizeof(ext4_fake_directory_entry_t) + used_name_len;
524 if ((used_name_len % 4) != 0) {
525 used_space += 4 - (used_name_len % 4);
526 }
527 uint16_t free_space = rec_len - used_space;
528
529 if (free_space >= required_len) {
530
531 // Cut tail of current entry
532 ext4_directory_entry_ll_set_entry_length(dentry, used_space);
533 ext4_directory_entry_ll_t *new_entry =
534 (void *)dentry + used_space;
535 ext4_directory_write_entry(sb, new_entry,
536 free_space, child, name, name_len);
537
538 target_block->dirty = true;
539 return EOK;
540 }
541 }
542
543 dentry = (void *)dentry + rec_len;
544 }
545
546 return ENOSPC;
547}
548
549int ext4_directory_find_in_block(block_t *block,
550 ext4_superblock_t *sb, size_t name_len, const char *name,
551 ext4_directory_entry_ll_t **res_entry)
552{
553
554 ext4_directory_entry_ll_t *dentry = (ext4_directory_entry_ll_t *)block->data;
555 uint8_t *addr_limit = block->data + ext4_superblock_get_block_size(sb);
556
557 while ((uint8_t *)dentry < addr_limit) {
558
559 if ((uint8_t*) dentry + name_len > addr_limit) {
560 break;
561 }
562
563 if (dentry->inode != 0) {
564 if (name_len == ext4_directory_entry_ll_get_name_length(sb, dentry)) {
565 // Compare names
566 if (bcmp((uint8_t *)name, dentry->name, name_len) == 0) {
567 *res_entry = dentry;
568 return EOK;
569 }
570 }
571 }
572
573 // Goto next entry
574 uint16_t dentry_len = ext4_directory_entry_ll_get_entry_length(dentry);
575
576 if (dentry_len == 0) {
577 return EINVAL;
578 }
579
580 dentry = (ext4_directory_entry_ll_t *)((uint8_t *)dentry + dentry_len);
581 }
582
583 return ENOENT;
584}
585
586int ext4_directory_destroy_result(ext4_directory_search_result_t *result)
587{
588 if (result->block) {
589 return block_put(result->block);
590 }
591
592 return EOK;
593}
594
595/**
596 * @}
597 */
Note: See TracBrowser for help on using the repository browser.