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

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

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