source: mainline/uspace/lib/ext4/libext4_directory.c@ 565b6ff

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 565b6ff was 565b6ff, checked in by Frantisek Princ <frantisek.princ@…>, 13 years ago
  • bugfix in adding directory entry (linear)
  • added skeleton for using directory index (not used yet)
  • Property mode set to 100644
File size: 13.8 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
262static void 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_filesystem_t *fs, ext4_inode_ref_t * parent,
281 const char *entry_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, entry_name);
286
287 uint16_t name_len = strlen(entry_name);
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 EXT4FS_DBG("trying INDEX");
294
295 rc = ext4_directory_dx_add_entry(fs, parent, name_len, entry_name);
296
297 // Check if index is not corrupted
298 if (rc != EXT4_ERR_BAD_DX_DIR) {
299
300 if (rc != EOK) {
301 return rc;
302 }
303
304 return EOK;
305 }
306
307 // Needed to clear dir index flag
308 ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX);
309 parent->dirty = true;
310
311 EXT4FS_DBG("index is corrupted - doing linear algorithm, index flag cleared");
312 }
313
314 // Linear algorithm
315 uint16_t required_len = 8 + name_len + (4 - name_len % 4);
316
317 ext4_directory_iterator_t it;
318 rc = ext4_directory_iterator_init(&it, fs, parent, 0);
319 if (rc != EOK) {
320 return rc;
321 }
322
323 uint32_t block_size = ext4_superblock_get_block_size(fs->superblock);
324
325 while (it.current != NULL) {
326 uint32_t entry_inode = ext4_directory_entry_ll_get_inode(it.current);
327 uint16_t rec_len = ext4_directory_entry_ll_get_entry_length(it.current);
328
329 if ((entry_inode == 0) && (rec_len >= required_len)) {
330
331
332 ext4_directory_write_entry(fs->superblock, it.current, rec_len,
333 child, entry_name, name_len);
334 it.current_block->dirty = true;
335 return ext4_directory_iterator_fini(&it);
336 }
337
338 if (entry_inode != 0) {
339 uint16_t used_name_len = ext4_directory_entry_ll_get_name_length(
340 fs->superblock, it.current);
341
342 uint16_t used_space = 8 + used_name_len;
343 if ((used_name_len % 4) != 0) {
344 used_space += 4 - (used_name_len % 4);
345 }
346 uint16_t free_space = rec_len - used_space;
347
348 EXT4FS_DBG("rec_len = \%u, used_space = \%u, free space = \%u", rec_len, used_space, free_space);
349
350 if (free_space >= required_len) {
351 uint16_t used_len = rec_len - free_space;
352
353 // Cut tail of current entry
354 ext4_directory_entry_ll_set_entry_length(it.current, used_len);
355
356 // SEEK manually
357 uint32_t local_offset = (it.current_offset % block_size);
358 local_offset += used_len;
359 ext4_directory_entry_ll_t *new_entry = it.current_block->data + local_offset;
360
361 // We are sure, that both entries are in the same data block
362 // dirtyness will be set now
363
364 ext4_directory_write_entry(fs->superblock, new_entry,
365 free_space, child, entry_name, name_len);
366 it.current_block->dirty = true;
367 return ext4_directory_iterator_fini(&it);
368 }
369
370 }
371
372 rc = ext4_directory_iterator_next(&it);
373 if (rc != EOK) {
374 return rc;
375 }
376 }
377
378 // Save position and destroy iterator
379 aoff64_t pos = it.current_offset;
380 ext4_directory_iterator_fini(&it);
381
382 // Compute next block index and allocate data block
383 uint32_t block_idx = pos / block_size;
384
385 uint32_t fblock;
386 rc = ext4_filesystem_get_inode_data_block_index(fs, parent->inode, block_idx, &fblock);
387 if (rc != EOK) {
388 return rc;
389 }
390
391 if (fblock == 0) {
392 rc = ext4_balloc_alloc_block(fs, parent, &fblock);
393 if (rc != EOK) {
394 return rc;
395 }
396
397 rc = ext4_filesystem_set_inode_data_block_index(fs, parent, block_idx, fblock);
398 if (rc != EOK) {
399 ext4_balloc_free_block(fs, parent, fblock);
400 return rc;
401 }
402
403 uint64_t inode_size = ext4_inode_get_size(fs->superblock, parent->inode);
404 inode_size += block_size;
405 ext4_inode_set_size(parent->inode, inode_size);
406
407 parent->dirty = true;
408 }
409
410 // Load block
411 block_t *new_block;
412 rc = block_get(&new_block, fs->device, fblock, BLOCK_FLAGS_NOREAD);
413 if (rc != EOK) {
414 return rc;
415 }
416
417 // Fill block with zeroes
418 memset(new_block->data, 0, block_size);
419
420 ext4_directory_entry_ll_t *block_entry = new_block->data;
421
422 ext4_directory_write_entry(fs->superblock, block_entry, block_size,
423 child, entry_name, name_len);
424
425 new_block->dirty = true;
426 rc = block_put(new_block);
427 if (rc != EOK) {
428 return rc;
429 }
430
431 return EOK;
432}
433
434int ext4_directory_find_entry(ext4_directory_iterator_t *it,
435 ext4_inode_ref_t *parent, const char *name)
436{
437 int rc;
438 uint32_t name_size = strlen(name);
439
440 // Index search
441 if (ext4_superblock_has_feature_compatible(it->fs->superblock, EXT4_FEATURE_COMPAT_DIR_INDEX) &&
442 ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX)) {
443
444 rc = ext4_directory_dx_find_entry(it, it->fs, parent, name_size, name);
445
446 // Check if index is not corrupted
447 if (rc != EXT4_ERR_BAD_DX_DIR) {
448
449 if (rc != EOK) {
450 return rc;
451 }
452 return EOK;
453 }
454
455 EXT4FS_DBG("index is corrupted - doing linear search");
456
457 // TODO Needed to clear dir index flag
458 //ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX);
459 //parent->dirty = true;
460
461 }
462
463 bool found = false;
464 // Linear search
465 while (it->current != NULL) {
466 uint32_t inode = ext4_directory_entry_ll_get_inode(it->current);
467
468 /* ignore empty directory entries */
469 if (inode != 0) {
470 uint16_t entry_name_size = ext4_directory_entry_ll_get_name_length(
471 it->fs->superblock, it->current);
472
473 if (entry_name_size == name_size && bcmp(name, it->current->name,
474 name_size) == 0) {
475 found = true;
476 break;
477 }
478 }
479
480 rc = ext4_directory_iterator_next(it);
481 if (rc != EOK) {
482 return rc;
483 }
484 }
485
486 if (!found) {
487 return ENOENT;
488 }
489
490 return EOK;
491}
492
493
494int ext4_directory_remove_entry(ext4_filesystem_t* fs,
495 ext4_inode_ref_t *parent, const char *name)
496{
497 int rc;
498
499 if (!ext4_inode_is_type(fs->superblock, parent->inode,
500 EXT4_INODE_MODE_DIRECTORY)) {
501 return ENOTDIR;
502 }
503
504 ext4_directory_iterator_t it;
505 rc = ext4_directory_iterator_init(&it, fs, parent, 0);
506 if (rc != EOK) {
507 return rc;
508 }
509
510 rc = ext4_directory_find_entry(&it, parent, name);
511 if (rc != EOK) {
512 ext4_directory_iterator_fini(&it);
513 return rc;
514 }
515
516 // TODO modify HTREE index if exists
517
518 uint32_t block_size = ext4_superblock_get_block_size(fs->superblock);
519 uint32_t pos = it.current_offset % block_size;
520
521 ext4_directory_entry_ll_set_inode(it.current, 0);
522
523 if (pos != 0) {
524 uint32_t offset = 0;
525
526 ext4_directory_entry_ll_t *tmp_dentry = it.current_block->data;
527 uint16_t tmp_dentry_length =
528 ext4_directory_entry_ll_get_entry_length(tmp_dentry);
529
530 while ((offset + tmp_dentry_length) < pos) {
531 offset += ext4_directory_entry_ll_get_entry_length(tmp_dentry);
532 tmp_dentry = it.current_block->data + offset;
533 tmp_dentry_length =
534 ext4_directory_entry_ll_get_entry_length(tmp_dentry);
535 }
536
537 assert(tmp_dentry_length + offset == pos);
538
539 uint16_t del_entry_length =
540 ext4_directory_entry_ll_get_entry_length(it.current);
541 ext4_directory_entry_ll_set_entry_length(tmp_dentry,
542 tmp_dentry_length + del_entry_length);
543
544 }
545
546
547 it.current_block->dirty = true;
548
549 ext4_directory_iterator_fini(&it);
550 return EOK;
551}
552
553
554/**
555 * @}
556 */
Note: See TracBrowser for help on using the repository browser.