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

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

Fixed bugs in directory removal process
  • Property mode set to 100644
File size: 8.6 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
97
98int ext4_directory_iterator_init(ext4_directory_iterator_t *it,
99 ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, aoff64_t pos)
100{
101 it->inode_ref = inode_ref;
102 it->fs = fs;
103 it->current = NULL;
104 it->current_offset = 0;
105 it->current_block = NULL;
106
107 return ext4_directory_iterator_seek(it, pos);
108}
109
110
111int ext4_directory_iterator_next(ext4_directory_iterator_t *it)
112{
113 uint16_t skip;
114
115 assert(it->current != NULL);
116
117 skip = ext4_directory_entry_ll_get_entry_length(it->current);
118
119 return ext4_directory_iterator_seek(it, it->current_offset + skip);
120}
121
122
123int ext4_directory_iterator_seek(ext4_directory_iterator_t *it, aoff64_t pos)
124{
125 int rc;
126
127 uint64_t size;
128 aoff64_t current_block_idx;
129 aoff64_t next_block_idx;
130 uint32_t next_block_phys_idx;
131 uint32_t block_size;
132
133 size = ext4_inode_get_size(it->fs->superblock, it->inode_ref->inode);
134
135 /* The iterator is not valid until we seek to the desired position */
136 it->current = NULL;
137
138 /* Are we at the end? */
139 if (pos >= size) {
140 if (it->current_block) {
141 rc = block_put(it->current_block);
142 it->current_block = NULL;
143 if (rc != EOK) {
144 return rc;
145 }
146 }
147
148 it->current_offset = pos;
149 return EOK;
150 }
151
152 block_size = ext4_superblock_get_block_size(it->fs->superblock);
153 current_block_idx = it->current_offset / block_size;
154 next_block_idx = pos / block_size;
155
156 /* If we don't have a block or are moving accross block boundary,
157 * we need to get another block
158 */
159 if (it->current_block == NULL || current_block_idx != next_block_idx) {
160 if (it->current_block) {
161 rc = block_put(it->current_block);
162 it->current_block = NULL;
163 if (rc != EOK) {
164 return rc;
165 }
166 }
167
168 rc = ext4_filesystem_get_inode_data_block_index(it->fs,
169 it->inode_ref->inode, next_block_idx, &next_block_phys_idx);
170 if (rc != EOK) {
171 return rc;
172 }
173
174 rc = block_get(&it->current_block, it->fs->device, next_block_phys_idx,
175 BLOCK_FLAGS_NONE);
176 if (rc != EOK) {
177 it->current_block = NULL;
178 return rc;
179 }
180 }
181
182 it->current_offset = pos;
183
184 return ext4_directory_iterator_set(it, block_size);
185}
186
187static int ext4_directory_iterator_set(ext4_directory_iterator_t *it,
188 uint32_t block_size)
189{
190 uint32_t offset_in_block = it->current_offset % block_size;
191
192 it->current = NULL;
193
194 /* Ensure proper alignment */
195 if ((offset_in_block % 4) != 0) {
196 return EIO;
197 }
198
199 /* Ensure that the core of the entry does not overflow the block */
200 if (offset_in_block > block_size - 8) {
201 return EIO;
202 }
203
204 ext4_directory_entry_ll_t *entry = it->current_block->data + offset_in_block;
205
206 /* Ensure that the whole entry does not overflow the block */
207 uint16_t length = ext4_directory_entry_ll_get_entry_length(entry);
208 if (offset_in_block + length > block_size) {
209 return EIO;
210 }
211
212 /* Ensure the name length is not too large */
213 if (ext4_directory_entry_ll_get_name_length(it->fs->superblock,
214 entry) > length-8) {
215 return EIO;
216 }
217
218 it->current = entry;
219 return EOK;
220}
221
222
223int ext4_directory_iterator_fini(ext4_directory_iterator_t *it)
224{
225 int rc;
226
227 it->fs = NULL;
228 it->inode_ref = NULL;
229 it->current = NULL;
230
231 if (it->current_block) {
232 rc = block_put(it->current_block);
233 if (rc != EOK) {
234 return rc;
235 }
236 }
237
238 return EOK;
239}
240
241
242int ext4_directory_find_entry(ext4_directory_iterator_t *it,
243 ext4_inode_ref_t *parent, const char *name)
244{
245 int rc;
246 uint32_t name_size = strlen(name);
247
248 // Index search
249 if (ext4_superblock_has_feature_compatible(it->fs->superblock, EXT4_FEATURE_COMPAT_DIR_INDEX) &&
250 ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX)) {
251
252 rc = ext4_directory_dx_find_entry(it, it->fs, parent, name_size, name);
253
254 // Check if index is not corrupted
255 if (rc != EXT4_ERR_BAD_DX_DIR) {
256
257 if (rc != EOK) {
258 return rc;
259 }
260 return EOK;
261 }
262
263 EXT4FS_DBG("index is corrupted - doing linear search");
264 }
265
266 bool found = false;
267 // Linear search
268 while (it->current != NULL) {
269 uint32_t inode = ext4_directory_entry_ll_get_inode(it->current);
270
271 /* ignore empty directory entries */
272 if (inode != 0) {
273 uint16_t entry_name_size = ext4_directory_entry_ll_get_name_length(
274 it->fs->superblock, it->current);
275
276 if (entry_name_size == name_size && bcmp(name, it->current->name,
277 name_size) == 0) {
278 found = true;
279 break;
280 }
281 }
282
283 rc = ext4_directory_iterator_next(it);
284 if (rc != EOK) {
285 return rc;
286 }
287 }
288
289 if (!found) {
290 return ENOENT;
291 }
292
293 return EOK;
294}
295
296
297int ext4_directory_remove_entry(ext4_filesystem_t* fs,
298 ext4_inode_ref_t *parent, const char *name)
299{
300 int rc;
301 ext4_directory_iterator_t it;
302
303 if (!ext4_inode_is_type(fs->superblock, parent->inode,
304 EXT4_INODE_MODE_DIRECTORY)) {
305 return ENOTDIR;
306 }
307
308 rc = ext4_directory_iterator_init(&it, fs, parent, 0);
309 if (rc != EOK) {
310 return rc;
311 }
312
313 rc = ext4_directory_find_entry(&it, parent, name);
314 if (rc != EOK) {
315 ext4_directory_iterator_fini(&it);
316 return rc;
317 }
318
319 // TODO modify HTREE index if exists
320
321 uint32_t block_size = ext4_superblock_get_block_size(fs->superblock);
322 uint32_t pos = it.current_offset % block_size;
323
324 ext4_directory_entry_ll_set_inode(it.current, 0);
325
326 if (pos != 0) {
327 uint32_t offset = 0;
328
329 ext4_directory_entry_ll_t *tmp_dentry = it.current_block->data;
330 uint16_t tmp_dentry_length =
331 ext4_directory_entry_ll_get_entry_length(tmp_dentry);
332
333 while ((offset + tmp_dentry_length) < pos) {
334 offset += ext4_directory_entry_ll_get_entry_length(tmp_dentry);
335 tmp_dentry = it.current_block->data + offset;
336 tmp_dentry_length =
337 ext4_directory_entry_ll_get_entry_length(tmp_dentry);
338 }
339
340 assert(tmp_dentry_length + offset == pos);
341
342 uint16_t del_entry_length =
343 ext4_directory_entry_ll_get_entry_length(it.current);
344 ext4_directory_entry_ll_set_entry_length(tmp_dentry,
345 tmp_dentry_length + del_entry_length);
346
347 }
348
349
350 it.current_block->dirty = true;
351
352 ext4_directory_iterator_fini(&it);
353 return EOK;
354}
355
356
357/**
358 * @}
359 */
Note: See TracBrowser for help on using the repository browser.