source: mainline/uspace/lib/ext4/libext4_directory_index.c@ c83a55c

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

splitted code because of very long source file

  • Property mode set to 100644
File size: 9.8 KB
RevLine 
[0dc91833]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_index.c
35 * @brief TODO
36 */
37
38#include <errno.h>
39#include "libext4.h"
40
41static int ext4_directory_hinfo_init(ext4_hash_info_t *hinfo, block_t *root_block,
42 ext4_superblock_t *sb, size_t name_len, const char *name)
43{
44 uint32_t block_size, entry_space;
45 uint16_t limit;
46 ext4_directory_dx_root_t *root;
47
48 root = (ext4_directory_dx_root_t *)root_block->data;
49
50 if (root->info.hash_version != EXT4_HASH_VERSION_TEA &&
51 root->info.hash_version != EXT4_HASH_VERSION_HALF_MD4 &&
52 root->info.hash_version != EXT4_HASH_VERSION_LEGACY) {
53 return EXT4_ERR_BAD_DX_DIR;
54 }
55
56 // Check unused flags
57 if (root->info.unused_flags != 0) {
58 EXT4FS_DBG("ERR: unused_flags = \%u", root->info.unused_flags);
59 return EXT4_ERR_BAD_DX_DIR;
60 }
61
62 // Check indirect levels
63 if (root->info.indirect_levels > 1) {
64 EXT4FS_DBG("ERR: indirect_levels = \%u", root->info.indirect_levels);
65 return EXT4_ERR_BAD_DX_DIR;
66 }
67
68 block_size = ext4_superblock_get_block_size(sb);
69
70 entry_space = block_size;
71 entry_space -= 2 * sizeof(ext4_directory_dx_dot_entry_t);
72 entry_space -= sizeof(ext4_directory_dx_root_info_t);
73 entry_space = entry_space / sizeof(ext4_directory_dx_entry_t);
74
75 limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)&root->entries);
76 if (limit != entry_space) {
77 return EXT4_ERR_BAD_DX_DIR;
78 }
79
80 hinfo->hash_version = ext4_directory_dx_root_info_get_hash_version(&root->info);
81 if ((hinfo->hash_version <= EXT4_HASH_VERSION_TEA)
82 && (ext4_superblock_has_flag(sb, EXT4_SUPERBLOCK_FLAGS_UNSIGNED_HASH))) {
83 // 3 is magic from ext4 linux implementation
84 hinfo->hash_version += 3;
85 }
86
87 hinfo->seed = ext4_superblock_get_hash_seed(sb);
88
89 if (name) {
90 ext4_hash_string(hinfo, name_len, name);
91 }
92
93 return EOK;
94}
95
96static int ext4_directory_dx_get_leaf(ext4_hash_info_t *hinfo,
97 ext4_filesystem_t *fs, ext4_inode_t *inode, block_t *root_block,
98 ext4_directory_dx_block_t **dx_block, ext4_directory_dx_block_t *dx_blocks)
99{
100 int rc;
101 uint16_t count, limit, entry_space;
102 uint8_t indirect_level;
103 ext4_directory_dx_root_t *root;
104 ext4_directory_dx_entry_t *p, *q, *m, *at;
105 ext4_directory_dx_entry_t *entries;
106 block_t *tmp_block = root_block;
107 uint32_t fblock, next_block;
108 ext4_directory_dx_block_t *tmp_dx_block = dx_blocks;
109
110 root = (ext4_directory_dx_root_t *)root_block->data;
111 entries = (ext4_directory_dx_entry_t *)&root->entries;
112
113 limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)entries);
114 indirect_level = ext4_directory_dx_root_info_get_indirect_levels(&root->info);
115
116 while (true) {
117
118 count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)entries);
119 if ((count == 0) || (count > limit)) {
120 return EXT4_ERR_BAD_DX_DIR;
121 }
122
123 p = entries + 1;
124 q = entries + count - 1;
125
126 while (p <= q) {
127 m = p + (q - p) / 2;
128 if (ext4_directory_dx_entry_get_hash(m) > hinfo->hash) {
129 q = m - 1;
130 } else {
131 p = m + 1;
132 }
133 }
134
135 at = p - 1;
136
137 tmp_dx_block->block = tmp_block;
138 tmp_dx_block->entries = entries;
139 tmp_dx_block->position = at;
140
141 if (indirect_level == 0) {
142 *dx_block = tmp_dx_block;
143 return EOK;
144 }
145
146 next_block = ext4_directory_dx_entry_get_block(at);
147
148 indirect_level--;
149
150 rc = ext4_filesystem_get_inode_data_block_index(fs, inode, next_block, &fblock);
151 if (rc != EOK) {
152 return rc;
153 }
154
155 rc = block_get(&tmp_block, fs->device, fblock, BLOCK_FLAGS_NONE);
156 if (rc != EOK) {
157 return rc;
158 }
159
160 entries = ((ext4_directory_dx_node_t *) tmp_block->data)->entries;
161 limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)entries);
162
163 entry_space = ext4_superblock_get_block_size(fs->superblock) - sizeof(ext4_directory_dx_dot_entry_t);
164 entry_space = entry_space / sizeof(ext4_directory_dx_entry_t);
165
166
167 if (limit != entry_space) {
168 block_put(tmp_block);
169 return EXT4_ERR_BAD_DX_DIR;
170 }
171
172 ++tmp_dx_block;
173 }
174
175 // Unreachable
176 return EOK;
177}
178
179
180static int ext4_dirextory_dx_find_dir_entry(block_t *block,
181 ext4_superblock_t *sb, size_t name_len, const char *name,
182 ext4_directory_entry_ll_t **res_entry, aoff64_t *block_offset)
183{
184 ext4_directory_entry_ll_t *dentry;
185 uint16_t dentry_len;
186 uint8_t *addr_limit;
187 aoff64_t offset = 0;
188
189 dentry = (ext4_directory_entry_ll_t *)block->data;
190 addr_limit = block->data + ext4_superblock_get_block_size(sb);
191
192 while ((uint8_t *)dentry < addr_limit) {
193
194 if ((uint8_t*) dentry + name_len > addr_limit) {
195 break;
196 }
197
198 if (dentry->inode != 0) {
199 if (name_len == ext4_directory_entry_ll_get_name_length(sb, dentry)) {
200 // Compare names
201 if (bcmp((uint8_t *)name, dentry->name, name_len) == 0) {
202 *block_offset = offset;
203 *res_entry = dentry;
204 return 1;
205 }
206 }
207 }
208
209
210 // Goto next entry
211 dentry_len = ext4_directory_entry_ll_get_entry_length(dentry);
212
213 if (dentry_len == 0) {
214 // TODO error
215 return -1;
216 }
217
218 offset += dentry_len;
219 dentry = (ext4_directory_entry_ll_t *)((uint8_t *)dentry + dentry_len);
220 }
221
222 return 0;
223}
224
225static int ext4_directory_dx_next_block(ext4_filesystem_t *fs, ext4_inode_t *inode, uint32_t hash,
226 ext4_directory_dx_block_t *handle, ext4_directory_dx_block_t *handles)
227{
228 ext4_directory_dx_block_t *p;
229 uint16_t count;
230 uint32_t num_handles;
231 uint32_t current_hash;
232 block_t *block;
233 uint32_t block_addr, block_idx;
234 int rc;
235
236 num_handles = 0;
237 p = handle;
238
239 while (1) {
240
241 p->position++;
242 count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)p->entries);
243
244 if (p->position < p->entries + count) {
245 break;
246 }
247
248 if (p == handles) {
249 return 0;
250 }
251
252 num_handles++;
253 p--;
254 }
255
256 current_hash = ext4_directory_dx_entry_get_hash(p->position);
257
258 if ((hash & 1) == 0) {
259 if ((current_hash & ~1) != hash) {
260 return 0;
261 }
262 }
263
264 while (num_handles--) {
265
266 block_idx = ext4_directory_dx_entry_get_block(p->position);
267 rc = ext4_filesystem_get_inode_data_block_index(fs, inode, block_idx, &block_addr);
268 if (rc != EOK) {
269 return rc;
270 }
271
272 rc = block_get(&block, fs->device, block_addr, BLOCK_FLAGS_NONE);
273 if (rc != EOK) {
274 return rc;
275 }
276
277 p++;
278
279 block_put(p->block);
280 p->block = block;
281 p->entries = ((ext4_directory_dx_node_t *) block->data)->entries;
282 p->position = p->entries;
283 }
284
285 return 1;
286
287}
288
289int ext4_directory_dx_find_entry(ext4_directory_iterator_t *it,
290 ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, size_t len, const char *name)
291{
292 int rc;
293 uint32_t root_block_addr, leaf_block_addr, leaf_block_idx;
294 aoff64_t block_offset;
295 block_t *root_block, *leaf_block;
296 ext4_hash_info_t hinfo;
297 ext4_directory_entry_ll_t *res_dentry;
298 ext4_directory_dx_block_t dx_blocks[2], *dx_block;
299
300 // get direct block 0 (index root)
301 rc = ext4_filesystem_get_inode_data_block_index(fs, inode_ref->inode, 0, &root_block_addr);
302 if (rc != EOK) {
303 return rc;
304 }
305
306 rc = block_get(&root_block, fs->device, root_block_addr, BLOCK_FLAGS_NONE);
307 if (rc != EOK) {
308 it->current_block = NULL;
309 return rc;
310 }
311
312 rc = ext4_directory_hinfo_init(&hinfo, root_block, fs->superblock, len, name);
313 if (rc != EOK) {
314 block_put(root_block);
315 return EXT4_ERR_BAD_DX_DIR;
316 }
317
318 rc = ext4_directory_dx_get_leaf(&hinfo, fs, inode_ref->inode, root_block, &dx_block, dx_blocks);
319 if (rc != EOK) {
320 block_put(root_block);
321 return EXT4_ERR_BAD_DX_DIR;
322 }
323
324 do {
325
326 leaf_block_idx = ext4_directory_dx_entry_get_block(dx_block->position);
327
328 rc = ext4_filesystem_get_inode_data_block_index(fs, inode_ref->inode, leaf_block_idx, &leaf_block_addr);
329 if (rc != EOK) {
330 return EXT4_ERR_BAD_DX_DIR;
331 }
332
333 rc = block_get(&leaf_block, fs->device, leaf_block_addr, BLOCK_FLAGS_NONE);
334 if (rc != EOK) {
335 return EXT4_ERR_BAD_DX_DIR;
336 }
337
338 rc = ext4_dirextory_dx_find_dir_entry(leaf_block, fs->superblock, len, name,
339 &res_dentry, &block_offset);
340
341 // Found => return it
342 if (rc == 1) {
343 it->fs = fs;
344 it->inode_ref = inode_ref;
345 it->current_block = leaf_block;
346 it->current_offset = block_offset;
347 it->current = res_dentry;
348 return EOK;
349 }
350
351 block_put(leaf_block);
352
353 // ERROR - corrupted index
354 if (rc == -1) {
355 // TODO cleanup
356 return EXT4_ERR_BAD_DX_DIR;
357 }
358
359 rc = ext4_directory_dx_next_block(fs, inode_ref->inode, hinfo.hash, dx_block, &dx_blocks[0]);
360 if (rc < 0) {
361 // TODO cleanup
362 return EXT4_ERR_BAD_DX_DIR;
363 }
364
365 } while (rc == 1);
366
367 return ENOENT;
368}
369
370
371
372/**
373 * @}
374 */
Note: See TracBrowser for help on using the repository browser.