1 | /*
|
---|
2 | * Copyright (c) 2011 Martin Sucha
|
---|
3 | * Copyright (c) 2012 Frantisek Princ
|
---|
4 | * All rights reserved.
|
---|
5 | *
|
---|
6 | * Redistribution and use in source and binary forms, with or without
|
---|
7 | * modification, are permitted provided that the following conditions
|
---|
8 | * are met:
|
---|
9 | *
|
---|
10 | * - Redistributions of source code must retain the above copyright
|
---|
11 | * notice, this list of conditions and the following disclaimer.
|
---|
12 | * - Redistributions in binary form must reproduce the above copyright
|
---|
13 | * notice, this list of conditions and the following disclaimer in the
|
---|
14 | * documentation and/or other materials provided with the distribution.
|
---|
15 | * - The name of the author may not be used to endorse or promote products
|
---|
16 | * derived from this software without specific prior written permission.
|
---|
17 | *
|
---|
18 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
|
---|
19 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
|
---|
20 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
|
---|
21 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
|
---|
22 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
|
---|
23 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
|
---|
24 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
|
---|
25 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
|
---|
26 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
|
---|
27 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
---|
28 | */
|
---|
29 |
|
---|
30 | /** @addtogroup libext4
|
---|
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 "libext4.h"
|
---|
42 |
|
---|
43 | /** Get i-node number from directory entry.
|
---|
44 | *
|
---|
45 | * @param de Directory entry
|
---|
46 | *
|
---|
47 | * @return I-node number
|
---|
48 | *
|
---|
49 | */
|
---|
50 | uint32_t ext4_directory_entry_ll_get_inode(ext4_directory_entry_ll_t *de)
|
---|
51 | {
|
---|
52 | return uint32_t_le2host(de->inode);
|
---|
53 | }
|
---|
54 |
|
---|
55 | /** Set i-node number to directory entry.
|
---|
56 | *
|
---|
57 | * @param de Directory entry
|
---|
58 | * @param inode I-node number
|
---|
59 | *
|
---|
60 | */
|
---|
61 | void ext4_directory_entry_ll_set_inode(ext4_directory_entry_ll_t *de,
|
---|
62 | uint32_t inode)
|
---|
63 | {
|
---|
64 | de->inode = host2uint32_t_le(inode);
|
---|
65 | }
|
---|
66 |
|
---|
67 | /** Get directory entry length.
|
---|
68 | *
|
---|
69 | * @param de Directory entry
|
---|
70 | *
|
---|
71 | * @return Entry length
|
---|
72 | *
|
---|
73 | */
|
---|
74 | uint16_t ext4_directory_entry_ll_get_entry_length(ext4_directory_entry_ll_t *de)
|
---|
75 | {
|
---|
76 | return uint16_t_le2host(de->entry_length);
|
---|
77 | }
|
---|
78 |
|
---|
79 | /** Set directory entry length.
|
---|
80 | *
|
---|
81 | * @param de Directory entry
|
---|
82 | * @param length Entry length
|
---|
83 | *
|
---|
84 | */
|
---|
85 | void ext4_directory_entry_ll_set_entry_length(ext4_directory_entry_ll_t *de,
|
---|
86 | uint16_t length)
|
---|
87 | {
|
---|
88 | de->entry_length = host2uint16_t_le(length);
|
---|
89 | }
|
---|
90 |
|
---|
91 | /** Get directory entry name length.
|
---|
92 | *
|
---|
93 | * @param sb Superblock
|
---|
94 | * @param de Directory entry
|
---|
95 | *
|
---|
96 | * @return Entry name length
|
---|
97 | *
|
---|
98 | */
|
---|
99 | uint16_t ext4_directory_entry_ll_get_name_length(ext4_superblock_t *sb,
|
---|
100 | ext4_directory_entry_ll_t *de)
|
---|
101 | {
|
---|
102 | if ((ext4_superblock_get_rev_level(sb) == 0) &&
|
---|
103 | (ext4_superblock_get_minor_rev_level(sb) < 5))
|
---|
104 | return ((uint16_t)de->name_length_high) << 8 |
|
---|
105 | ((uint16_t)de->name_length);
|
---|
106 |
|
---|
107 | return de->name_length;
|
---|
108 |
|
---|
109 | }
|
---|
110 |
|
---|
111 | /** Set directory entry name length.
|
---|
112 | *
|
---|
113 | * @param sb Superblock
|
---|
114 | * @param de Directory entry
|
---|
115 | * @param length Entry name length
|
---|
116 | *
|
---|
117 | */
|
---|
118 | void ext4_directory_entry_ll_set_name_length(ext4_superblock_t *sb,
|
---|
119 | ext4_directory_entry_ll_t *de, uint16_t length)
|
---|
120 | {
|
---|
121 | de->name_length = (length << 8) >> 8;
|
---|
122 |
|
---|
123 | if ((ext4_superblock_get_rev_level(sb) == 0) &&
|
---|
124 | (ext4_superblock_get_minor_rev_level(sb) < 5))
|
---|
125 | de->name_length_high = length >> 8;
|
---|
126 |
|
---|
127 | /* Else do nothing */
|
---|
128 | }
|
---|
129 |
|
---|
130 | /** Get i-node type of directory entry.
|
---|
131 | *
|
---|
132 | * @param sb Superblock
|
---|
133 | * @param de Directory entry
|
---|
134 | *
|
---|
135 | * @return I-node type (file, dir, etc.)
|
---|
136 | *
|
---|
137 | */
|
---|
138 | uint8_t ext4_directory_entry_ll_get_inode_type(ext4_superblock_t *sb,
|
---|
139 | ext4_directory_entry_ll_t *de)
|
---|
140 | {
|
---|
141 | if ((ext4_superblock_get_rev_level(sb) > 0) ||
|
---|
142 | (ext4_superblock_get_minor_rev_level(sb) >= 5))
|
---|
143 | return de->inode_type;
|
---|
144 |
|
---|
145 | return EXT4_DIRECTORY_FILETYPE_UNKNOWN;
|
---|
146 | }
|
---|
147 |
|
---|
148 | /** Set i-node type of directory entry.
|
---|
149 | *
|
---|
150 | * @param sb Superblock
|
---|
151 | * @param de Directory entry
|
---|
152 | * @param type I-node type (file, dir, etc.)
|
---|
153 | *
|
---|
154 | */
|
---|
155 | void ext4_directory_entry_ll_set_inode_type(ext4_superblock_t *sb,
|
---|
156 | ext4_directory_entry_ll_t *de, uint8_t type)
|
---|
157 | {
|
---|
158 | if ((ext4_superblock_get_rev_level(sb) > 0) ||
|
---|
159 | (ext4_superblock_get_minor_rev_level(sb) >= 5))
|
---|
160 | de->inode_type = type;
|
---|
161 |
|
---|
162 | /* Else do nothing */
|
---|
163 | }
|
---|
164 |
|
---|
165 | static int ext4_directory_iterator_seek(ext4_directory_iterator_t *, aoff64_t);
|
---|
166 | static int ext4_directory_iterator_set(ext4_directory_iterator_t *, uint32_t);
|
---|
167 |
|
---|
168 | /** Initialize directory iterator.
|
---|
169 | *
|
---|
170 | * Set position to the first valid entry from the required position.
|
---|
171 | *
|
---|
172 | * @param it Pointer to iterator to be initialized
|
---|
173 | * @param inode_ref Directory i-node
|
---|
174 | * @param pos Position to start reading entries from
|
---|
175 | *
|
---|
176 | * @return Error code
|
---|
177 | *
|
---|
178 | */
|
---|
179 | int ext4_directory_iterator_init(ext4_directory_iterator_t *it,
|
---|
180 | ext4_inode_ref_t *inode_ref, aoff64_t pos)
|
---|
181 | {
|
---|
182 | it->inode_ref = inode_ref;
|
---|
183 | it->current = NULL;
|
---|
184 | it->current_offset = 0;
|
---|
185 | it->current_block = NULL;
|
---|
186 |
|
---|
187 | return ext4_directory_iterator_seek(it, pos);
|
---|
188 | }
|
---|
189 |
|
---|
190 | /** Jump to the next valid entry
|
---|
191 | *
|
---|
192 | * @param it Initialized iterator
|
---|
193 | *
|
---|
194 | * @return Error code
|
---|
195 | *
|
---|
196 | */
|
---|
197 | int ext4_directory_iterator_next(ext4_directory_iterator_t *it)
|
---|
198 | {
|
---|
199 | assert(it->current != NULL);
|
---|
200 |
|
---|
201 | uint16_t skip = ext4_directory_entry_ll_get_entry_length(it->current);
|
---|
202 |
|
---|
203 | return ext4_directory_iterator_seek(it, it->current_offset + skip);
|
---|
204 | }
|
---|
205 |
|
---|
206 | /** Seek to next valid directory entry.
|
---|
207 | *
|
---|
208 | * Here can be jumped to the next data block.
|
---|
209 | *
|
---|
210 | * @param it Initialized iterator
|
---|
211 | * @param pos Position of the next entry
|
---|
212 | *
|
---|
213 | * @return Error code
|
---|
214 | *
|
---|
215 | */
|
---|
216 | int ext4_directory_iterator_seek(ext4_directory_iterator_t *it, aoff64_t pos)
|
---|
217 | {
|
---|
218 | uint64_t size = ext4_inode_get_size(it->inode_ref->fs->superblock,
|
---|
219 | it->inode_ref->inode);
|
---|
220 |
|
---|
221 | /* The iterator is not valid until we seek to the desired position */
|
---|
222 | it->current = NULL;
|
---|
223 |
|
---|
224 | /* Are we at the end? */
|
---|
225 | if (pos >= size) {
|
---|
226 | if (it->current_block) {
|
---|
227 | int rc = block_put(it->current_block);
|
---|
228 | it->current_block = NULL;
|
---|
229 |
|
---|
230 | if (rc != EOK)
|
---|
231 | return rc;
|
---|
232 | }
|
---|
233 |
|
---|
234 | it->current_offset = pos;
|
---|
235 | return EOK;
|
---|
236 | }
|
---|
237 |
|
---|
238 | /* Compute next block address */
|
---|
239 | uint32_t block_size =
|
---|
240 | ext4_superblock_get_block_size(it->inode_ref->fs->superblock);
|
---|
241 | aoff64_t current_block_idx = it->current_offset / block_size;
|
---|
242 | aoff64_t next_block_idx = pos / block_size;
|
---|
243 |
|
---|
244 | /*
|
---|
245 | * If we don't have a block or are moving accross block boundary,
|
---|
246 | * we need to get another block
|
---|
247 | */
|
---|
248 | if ((it->current_block == NULL) ||
|
---|
249 | (current_block_idx != next_block_idx)) {
|
---|
250 | if (it->current_block) {
|
---|
251 | int rc = block_put(it->current_block);
|
---|
252 | it->current_block = NULL;
|
---|
253 |
|
---|
254 | if (rc != EOK)
|
---|
255 | return rc;
|
---|
256 | }
|
---|
257 |
|
---|
258 | uint32_t next_block_phys_idx;
|
---|
259 | int rc = ext4_filesystem_get_inode_data_block_index(it->inode_ref,
|
---|
260 | next_block_idx, &next_block_phys_idx);
|
---|
261 | if (rc != EOK)
|
---|
262 | return rc;
|
---|
263 |
|
---|
264 | rc = block_get(&it->current_block, it->inode_ref->fs->device,
|
---|
265 | next_block_phys_idx, BLOCK_FLAGS_NONE);
|
---|
266 | if (rc != EOK) {
|
---|
267 | it->current_block = NULL;
|
---|
268 | return rc;
|
---|
269 | }
|
---|
270 | }
|
---|
271 |
|
---|
272 | it->current_offset = pos;
|
---|
273 |
|
---|
274 | return ext4_directory_iterator_set(it, block_size);
|
---|
275 | }
|
---|
276 |
|
---|
277 | /** Do some checks before returning iterator.
|
---|
278 | *
|
---|
279 | * @param it Iterator to be checked
|
---|
280 | * @param block_size Size of data block
|
---|
281 | *
|
---|
282 | * @return Error code
|
---|
283 | *
|
---|
284 | */
|
---|
285 | static int ext4_directory_iterator_set(ext4_directory_iterator_t *it,
|
---|
286 | uint32_t block_size)
|
---|
287 | {
|
---|
288 | it->current = NULL;
|
---|
289 |
|
---|
290 | uint32_t offset_in_block = it->current_offset % block_size;
|
---|
291 |
|
---|
292 | /* Ensure proper alignment */
|
---|
293 | if ((offset_in_block % 4) != 0)
|
---|
294 | return EIO;
|
---|
295 |
|
---|
296 | /* Ensure that the core of the entry does not overflow the block */
|
---|
297 | if (offset_in_block > block_size - 8)
|
---|
298 | return EIO;
|
---|
299 |
|
---|
300 | ext4_directory_entry_ll_t *entry =
|
---|
301 | it->current_block->data + offset_in_block;
|
---|
302 |
|
---|
303 | /* Ensure that the whole entry does not overflow the block */
|
---|
304 | uint16_t length = ext4_directory_entry_ll_get_entry_length(entry);
|
---|
305 | if (offset_in_block + length > block_size)
|
---|
306 | return EIO;
|
---|
307 |
|
---|
308 | /* Ensure the name length is not too large */
|
---|
309 | if (ext4_directory_entry_ll_get_name_length(
|
---|
310 | it->inode_ref->fs->superblock, entry) > length-8)
|
---|
311 | return EIO;
|
---|
312 |
|
---|
313 | /* Everything OK - "publish" the entry */
|
---|
314 | it->current = entry;
|
---|
315 | return EOK;
|
---|
316 | }
|
---|
317 |
|
---|
318 | /** Uninitialize directory iterator.
|
---|
319 | *
|
---|
320 | * Release all allocated structures.
|
---|
321 | *
|
---|
322 | * @param it Iterator to be finished
|
---|
323 | *
|
---|
324 | * @return Error code
|
---|
325 | *
|
---|
326 | */
|
---|
327 | int ext4_directory_iterator_fini(ext4_directory_iterator_t *it)
|
---|
328 | {
|
---|
329 | it->inode_ref = NULL;
|
---|
330 | it->current = NULL;
|
---|
331 |
|
---|
332 | if (it->current_block)
|
---|
333 | return block_put(it->current_block);
|
---|
334 |
|
---|
335 | return EOK;
|
---|
336 | }
|
---|
337 |
|
---|
338 | /** Write directory entry to concrete data block.
|
---|
339 | *
|
---|
340 | * @param sb Superblock
|
---|
341 | * @param entry Pointer to entry to be written
|
---|
342 | * @param entry_len Length of new entry
|
---|
343 | * @param child Child i-node to be written to new entry
|
---|
344 | * @param name Name of the new entry
|
---|
345 | * @param name_len Length of entry name
|
---|
346 | *
|
---|
347 | */
|
---|
348 | void ext4_directory_write_entry(ext4_superblock_t *sb,
|
---|
349 | ext4_directory_entry_ll_t *entry, uint16_t entry_len,
|
---|
350 | ext4_inode_ref_t *child, const char *name, size_t name_len)
|
---|
351 | {
|
---|
352 | /* Check maximum entry length */
|
---|
353 | uint32_t block_size = ext4_superblock_get_block_size(sb);
|
---|
354 | assert(entry_len <= block_size);
|
---|
355 |
|
---|
356 | /* Set basic attributes */
|
---|
357 | ext4_directory_entry_ll_set_inode(entry, child->index);
|
---|
358 | ext4_directory_entry_ll_set_entry_length(entry, entry_len);
|
---|
359 | ext4_directory_entry_ll_set_name_length(sb, entry, name_len);
|
---|
360 |
|
---|
361 | /* Write name */
|
---|
362 | memcpy(entry->name, name, name_len);
|
---|
363 |
|
---|
364 | /* Set type of entry */
|
---|
365 | if (ext4_inode_is_type(sb, child->inode, EXT4_INODE_MODE_DIRECTORY))
|
---|
366 | ext4_directory_entry_ll_set_inode_type(sb, entry,
|
---|
367 | EXT4_DIRECTORY_FILETYPE_DIR);
|
---|
368 | else
|
---|
369 | ext4_directory_entry_ll_set_inode_type(sb, entry,
|
---|
370 | EXT4_DIRECTORY_FILETYPE_REG_FILE);
|
---|
371 | }
|
---|
372 |
|
---|
373 | /** Add new entry to the directory.
|
---|
374 | *
|
---|
375 | * @param parent Directory i-node
|
---|
376 | * @param name Name of new entry
|
---|
377 | * @param child I-node to be referenced from new entry
|
---|
378 | *
|
---|
379 | * @return Error code
|
---|
380 | *
|
---|
381 | */
|
---|
382 | int ext4_directory_add_entry(ext4_inode_ref_t *parent, const char *name,
|
---|
383 | ext4_inode_ref_t *child)
|
---|
384 | {
|
---|
385 | ext4_filesystem_t *fs = parent->fs;
|
---|
386 |
|
---|
387 | /* Index adding (if allowed) */
|
---|
388 | if ((ext4_superblock_has_feature_compatible(fs->superblock,
|
---|
389 | EXT4_FEATURE_COMPAT_DIR_INDEX)) &&
|
---|
390 | (ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX))) {
|
---|
391 | int rc = ext4_directory_dx_add_entry(parent, child, name);
|
---|
392 |
|
---|
393 | /* Check if index is not corrupted */
|
---|
394 | if (rc != EXT4_ERR_BAD_DX_DIR) {
|
---|
395 | if (rc != EOK)
|
---|
396 | return rc;
|
---|
397 |
|
---|
398 | return EOK;
|
---|
399 | }
|
---|
400 |
|
---|
401 | /* Needed to clear dir index flag if corrupted */
|
---|
402 | ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX);
|
---|
403 | parent->dirty = true;
|
---|
404 | }
|
---|
405 |
|
---|
406 | /* Linear algorithm */
|
---|
407 |
|
---|
408 | uint32_t iblock = 0;
|
---|
409 | uint32_t fblock = 0;
|
---|
410 | uint32_t block_size = ext4_superblock_get_block_size(fs->superblock);
|
---|
411 | uint32_t inode_size = ext4_inode_get_size(fs->superblock, parent->inode);
|
---|
412 | uint32_t total_blocks = inode_size / block_size;
|
---|
413 |
|
---|
414 | uint32_t name_len = str_size(name);
|
---|
415 |
|
---|
416 | /* Find block, where is space for new entry and try to add */
|
---|
417 | bool success = false;
|
---|
418 | for (iblock = 0; iblock < total_blocks; ++iblock) {
|
---|
419 | int rc = ext4_filesystem_get_inode_data_block_index(parent,
|
---|
420 | iblock, &fblock);
|
---|
421 | if (rc != EOK)
|
---|
422 | return rc;
|
---|
423 |
|
---|
424 | block_t *block;
|
---|
425 | rc = block_get(&block, fs->device, fblock, BLOCK_FLAGS_NONE);
|
---|
426 | if (rc != EOK)
|
---|
427 | return rc;
|
---|
428 |
|
---|
429 | /* If adding is successful, function can finish */
|
---|
430 | rc = ext4_directory_try_insert_entry(fs->superblock, block,
|
---|
431 | child, name, name_len);
|
---|
432 | if (rc == EOK)
|
---|
433 | success = true;
|
---|
434 |
|
---|
435 | rc = block_put(block);
|
---|
436 | if (rc != EOK)
|
---|
437 | return rc;
|
---|
438 |
|
---|
439 | if (success)
|
---|
440 | return EOK;
|
---|
441 | }
|
---|
442 |
|
---|
443 | /* No free block found - needed to allocate next data block */
|
---|
444 |
|
---|
445 | iblock = 0;
|
---|
446 | fblock = 0;
|
---|
447 | int rc = ext4_filesystem_append_inode_block(parent, &fblock, &iblock);
|
---|
448 | if (rc != EOK)
|
---|
449 | return rc;
|
---|
450 |
|
---|
451 | /* Load new block */
|
---|
452 | block_t *new_block;
|
---|
453 | rc = block_get(&new_block, fs->device, fblock, BLOCK_FLAGS_NOREAD);
|
---|
454 | if (rc != EOK)
|
---|
455 | return rc;
|
---|
456 |
|
---|
457 | /* Fill block with zeroes */
|
---|
458 | memset(new_block->data, 0, block_size);
|
---|
459 | ext4_directory_entry_ll_t *block_entry = new_block->data;
|
---|
460 | ext4_directory_write_entry(fs->superblock, block_entry, block_size,
|
---|
461 | child, name, name_len);
|
---|
462 |
|
---|
463 | /* Save new block */
|
---|
464 | new_block->dirty = true;
|
---|
465 | rc = block_put(new_block);
|
---|
466 |
|
---|
467 | return rc;
|
---|
468 | }
|
---|
469 |
|
---|
470 | /** Find directory entry with passed name.
|
---|
471 | *
|
---|
472 | * @param result Result structure to be returned if entry found
|
---|
473 | * @param parent Directory i-node
|
---|
474 | * @param name Name of entry to be found
|
---|
475 | *
|
---|
476 | * @return Error code
|
---|
477 | *
|
---|
478 | */
|
---|
479 | int ext4_directory_find_entry(ext4_directory_search_result_t *result,
|
---|
480 | ext4_inode_ref_t *parent, const char *name)
|
---|
481 | {
|
---|
482 | uint32_t name_len = str_size(name);
|
---|
483 |
|
---|
484 | ext4_superblock_t *sb = parent->fs->superblock;
|
---|
485 |
|
---|
486 | /* Index search */
|
---|
487 | if ((ext4_superblock_has_feature_compatible(sb,
|
---|
488 | EXT4_FEATURE_COMPAT_DIR_INDEX)) &&
|
---|
489 | (ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX))) {
|
---|
490 | int rc = ext4_directory_dx_find_entry(result, parent, name_len,
|
---|
491 | name);
|
---|
492 |
|
---|
493 | /* Check if index is not corrupted */
|
---|
494 | if (rc != EXT4_ERR_BAD_DX_DIR) {
|
---|
495 | if (rc != EOK)
|
---|
496 | return rc;
|
---|
497 |
|
---|
498 | return EOK;
|
---|
499 | }
|
---|
500 |
|
---|
501 | /* Needed to clear dir index flag if corrupted */
|
---|
502 | ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX);
|
---|
503 | parent->dirty = true;
|
---|
504 | }
|
---|
505 |
|
---|
506 | /* Linear algorithm */
|
---|
507 |
|
---|
508 | uint32_t iblock;
|
---|
509 | uint32_t fblock;
|
---|
510 | uint32_t block_size = ext4_superblock_get_block_size(sb);
|
---|
511 | uint32_t inode_size = ext4_inode_get_size(sb, parent->inode);
|
---|
512 | uint32_t total_blocks = inode_size / block_size;
|
---|
513 |
|
---|
514 | /* Walk through all data blocks */
|
---|
515 | for (iblock = 0; iblock < total_blocks; ++iblock) {
|
---|
516 | /* Load block address */
|
---|
517 | int rc = ext4_filesystem_get_inode_data_block_index(parent, iblock,
|
---|
518 | &fblock);
|
---|
519 | if (rc != EOK)
|
---|
520 | return rc;
|
---|
521 |
|
---|
522 | /* Load data block */
|
---|
523 | block_t *block;
|
---|
524 | rc = block_get(&block, parent->fs->device, fblock, BLOCK_FLAGS_NONE);
|
---|
525 | if (rc != EOK)
|
---|
526 | return rc;
|
---|
527 |
|
---|
528 | /* Try to find entry in block */
|
---|
529 | ext4_directory_entry_ll_t *res_entry;
|
---|
530 | rc = ext4_directory_find_in_block(block, sb, name_len, name,
|
---|
531 | &res_entry);
|
---|
532 | if (rc == EOK) {
|
---|
533 | result->block = block;
|
---|
534 | result->dentry = res_entry;
|
---|
535 | return EOK;
|
---|
536 | }
|
---|
537 |
|
---|
538 | /* Entry not found - put block and continue to the next block */
|
---|
539 |
|
---|
540 | rc = block_put(block);
|
---|
541 | if (rc != EOK)
|
---|
542 | return rc;
|
---|
543 | }
|
---|
544 |
|
---|
545 | /* Entry was not found */
|
---|
546 |
|
---|
547 | result->block = NULL;
|
---|
548 | result->dentry = NULL;
|
---|
549 |
|
---|
550 | return ENOENT;
|
---|
551 | }
|
---|
552 |
|
---|
553 | /** Remove directory entry.
|
---|
554 | *
|
---|
555 | * @param parent Directory i-node
|
---|
556 | * @param name Name of the entry to be removed
|
---|
557 | *
|
---|
558 | * @return Error code
|
---|
559 | *
|
---|
560 | */
|
---|
561 | int ext4_directory_remove_entry(ext4_inode_ref_t *parent, const char *name)
|
---|
562 | {
|
---|
563 | /* Check if removing from directory */
|
---|
564 | if (!ext4_inode_is_type(parent->fs->superblock, parent->inode,
|
---|
565 | EXT4_INODE_MODE_DIRECTORY))
|
---|
566 | return ENOTDIR;
|
---|
567 |
|
---|
568 | /* Try to find entry */
|
---|
569 | ext4_directory_search_result_t result;
|
---|
570 | int rc = ext4_directory_find_entry(&result, parent, name);
|
---|
571 | if (rc != EOK)
|
---|
572 | return rc;
|
---|
573 |
|
---|
574 | /* Invalidate entry */
|
---|
575 | ext4_directory_entry_ll_set_inode(result.dentry, 0);
|
---|
576 |
|
---|
577 | /* Store entry position in block */
|
---|
578 | uint32_t pos = (void *) result.dentry - result.block->data;
|
---|
579 |
|
---|
580 | /*
|
---|
581 | * If entry is not the first in block, it must be merged
|
---|
582 | * with previous entry
|
---|
583 | */
|
---|
584 | if (pos != 0) {
|
---|
585 | uint32_t offset = 0;
|
---|
586 |
|
---|
587 | /* Start from the first entry in block */
|
---|
588 | ext4_directory_entry_ll_t *tmp_dentry = result.block->data;
|
---|
589 | uint16_t tmp_dentry_length =
|
---|
590 | ext4_directory_entry_ll_get_entry_length(tmp_dentry);
|
---|
591 |
|
---|
592 | /* Find direct predecessor of removed entry */
|
---|
593 | while ((offset + tmp_dentry_length) < pos) {
|
---|
594 | offset +=
|
---|
595 | ext4_directory_entry_ll_get_entry_length(tmp_dentry);
|
---|
596 | tmp_dentry = result.block->data + offset;
|
---|
597 | tmp_dentry_length =
|
---|
598 | ext4_directory_entry_ll_get_entry_length(tmp_dentry);
|
---|
599 | }
|
---|
600 |
|
---|
601 | assert(tmp_dentry_length + offset == pos);
|
---|
602 |
|
---|
603 | /* Add to removed entry length to predecessor's length */
|
---|
604 | uint16_t del_entry_length =
|
---|
605 | ext4_directory_entry_ll_get_entry_length(result.dentry);
|
---|
606 | ext4_directory_entry_ll_set_entry_length(tmp_dentry,
|
---|
607 | tmp_dentry_length + del_entry_length);
|
---|
608 | }
|
---|
609 |
|
---|
610 | result.block->dirty = true;
|
---|
611 |
|
---|
612 | return ext4_directory_destroy_result(&result);
|
---|
613 | }
|
---|
614 |
|
---|
615 | /** Try to insert entry to concrete data block.
|
---|
616 | *
|
---|
617 | * @param sb Superblock
|
---|
618 | * @param target_block Block to try to insert entry to
|
---|
619 | * @param child Child i-node to be inserted by new entry
|
---|
620 | * @param name Name of the new entry
|
---|
621 | * @param name_len Length of the new entry name
|
---|
622 | *
|
---|
623 | * @return Error code
|
---|
624 | *
|
---|
625 | */
|
---|
626 | int ext4_directory_try_insert_entry(ext4_superblock_t *sb,
|
---|
627 | block_t *target_block, ext4_inode_ref_t *child, const char *name,
|
---|
628 | uint32_t name_len)
|
---|
629 | {
|
---|
630 | /* Compute required length entry and align it to 4 bytes */
|
---|
631 | uint32_t block_size = ext4_superblock_get_block_size(sb);
|
---|
632 | uint16_t required_len = sizeof(ext4_fake_directory_entry_t) + name_len;
|
---|
633 |
|
---|
634 | if ((required_len % 4) != 0)
|
---|
635 | required_len += 4 - (required_len % 4);
|
---|
636 |
|
---|
637 | /* Initialize pointers, stop means to upper bound */
|
---|
638 | ext4_directory_entry_ll_t *dentry = target_block->data;
|
---|
639 | ext4_directory_entry_ll_t *stop = target_block->data + block_size;
|
---|
640 |
|
---|
641 | /*
|
---|
642 | * Walk through the block and check for invalid entries
|
---|
643 | * or entries with free space for new entry
|
---|
644 | */
|
---|
645 | while (dentry < stop) {
|
---|
646 | uint32_t inode = ext4_directory_entry_ll_get_inode(dentry);
|
---|
647 | uint16_t rec_len = ext4_directory_entry_ll_get_entry_length(dentry);
|
---|
648 |
|
---|
649 | /* If invalid and large enough entry, use it */
|
---|
650 | if ((inode == 0) && (rec_len >= required_len)) {
|
---|
651 | ext4_directory_write_entry(sb, dentry, rec_len, child,
|
---|
652 | name, name_len);
|
---|
653 | target_block->dirty = true;
|
---|
654 |
|
---|
655 | return EOK;
|
---|
656 | }
|
---|
657 |
|
---|
658 | /* Valid entry, try to split it */
|
---|
659 | if (inode != 0) {
|
---|
660 | uint16_t used_name_len =
|
---|
661 | ext4_directory_entry_ll_get_name_length(sb, dentry);
|
---|
662 |
|
---|
663 | uint16_t used_space =
|
---|
664 | sizeof(ext4_fake_directory_entry_t) + used_name_len;
|
---|
665 |
|
---|
666 | if ((used_name_len % 4) != 0)
|
---|
667 | used_space += 4 - (used_name_len % 4);
|
---|
668 |
|
---|
669 | uint16_t free_space = rec_len - used_space;
|
---|
670 |
|
---|
671 | /* There is free space for new entry */
|
---|
672 | if (free_space >= required_len) {
|
---|
673 | /* Cut tail of current entry */
|
---|
674 | ext4_directory_entry_ll_set_entry_length(dentry, used_space);
|
---|
675 | ext4_directory_entry_ll_t *new_entry =
|
---|
676 | (void *) dentry + used_space;
|
---|
677 | ext4_directory_write_entry(sb, new_entry,
|
---|
678 | free_space, child, name, name_len);
|
---|
679 |
|
---|
680 | target_block->dirty = true;
|
---|
681 |
|
---|
682 | return EOK;
|
---|
683 | }
|
---|
684 | }
|
---|
685 |
|
---|
686 | /* Jump to the next entry */
|
---|
687 | dentry = (void *) dentry + rec_len;
|
---|
688 | }
|
---|
689 |
|
---|
690 | /* No free space found for new entry */
|
---|
691 | return ENOSPC;
|
---|
692 | }
|
---|
693 |
|
---|
694 | /** Try to find entry in block by name.
|
---|
695 | *
|
---|
696 | * @param block Block containing entries
|
---|
697 | * @param sb Superblock
|
---|
698 | * @param name_len Length of entry name
|
---|
699 | * @param name Name of entry to be found
|
---|
700 | * @param res_entry Output pointer to found entry, NULL if not found
|
---|
701 | *
|
---|
702 | * @return Error code
|
---|
703 | *
|
---|
704 | */
|
---|
705 | int ext4_directory_find_in_block(block_t *block, ext4_superblock_t *sb,
|
---|
706 | size_t name_len, const char *name, ext4_directory_entry_ll_t **res_entry)
|
---|
707 | {
|
---|
708 | /* Start from the first entry in block */
|
---|
709 | ext4_directory_entry_ll_t *dentry =
|
---|
710 | (ext4_directory_entry_ll_t *) block->data;
|
---|
711 |
|
---|
712 | /* Set upper bound for cycling */
|
---|
713 | uint8_t *addr_limit = block->data + ext4_superblock_get_block_size(sb);
|
---|
714 |
|
---|
715 | /* Walk through the block and check entries */
|
---|
716 | while ((uint8_t *) dentry < addr_limit) {
|
---|
717 | /* Termination condition */
|
---|
718 | if ((uint8_t *) dentry + name_len > addr_limit)
|
---|
719 | break;
|
---|
720 |
|
---|
721 | /* Valid entry - check it */
|
---|
722 | if (dentry->inode != 0) {
|
---|
723 | /* For more effectivity compare firstly only lengths */
|
---|
724 | if (ext4_directory_entry_ll_get_name_length(sb, dentry) ==
|
---|
725 | name_len) {
|
---|
726 | /* Compare names */
|
---|
727 | if (bcmp((uint8_t *) name, dentry->name, name_len) == 0) {
|
---|
728 | *res_entry = dentry;
|
---|
729 | return EOK;
|
---|
730 | }
|
---|
731 | }
|
---|
732 | }
|
---|
733 |
|
---|
734 | uint16_t dentry_len =
|
---|
735 | ext4_directory_entry_ll_get_entry_length(dentry);
|
---|
736 |
|
---|
737 | /* Corrupted entry */
|
---|
738 | if (dentry_len == 0)
|
---|
739 | return EINVAL;
|
---|
740 |
|
---|
741 | /* Jump to next entry */
|
---|
742 | dentry = (ext4_directory_entry_ll_t *) ((uint8_t *) dentry + dentry_len);
|
---|
743 | }
|
---|
744 |
|
---|
745 | /* Entry not found */
|
---|
746 | return ENOENT;
|
---|
747 | }
|
---|
748 |
|
---|
749 | /** Simple function to release allocated data from result.
|
---|
750 | *
|
---|
751 | * @param result Search result to destroy
|
---|
752 | *
|
---|
753 | * @return Error code
|
---|
754 | *
|
---|
755 | */
|
---|
756 | int ext4_directory_destroy_result(ext4_directory_search_result_t *result)
|
---|
757 | {
|
---|
758 | if (result->block)
|
---|
759 | return block_put(result->block);
|
---|
760 |
|
---|
761 | return EOK;
|
---|
762 | }
|
---|
763 |
|
---|
764 | /**
|
---|
765 | * @}
|
---|
766 | */
|
---|