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