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

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

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