source: mainline/uspace/lib/ext4/libext4_directory.c@ 7bd2c19

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

First part of reading htree directory index - the most important functionality (computing hashes) still missing
  • Property mode set to 100644
File size: 10.0 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 TODO
36 */
37
38#include <byteorder.h>
39#include <errno.h>
40#include "libext4.h"
41
42static int ext4_directory_iterator_set(ext4_directory_iterator_t *,
43 uint32_t);
44
45
46uint32_t ext4_directory_entry_ll_get_inode(ext4_directory_entry_ll_t *de)
47{
48 return uint32_t_le2host(de->inode);
49}
50
51uint16_t ext4_directory_entry_ll_get_entry_length(
52 ext4_directory_entry_ll_t *de)
53{
54 return uint16_t_le2host(de->entry_length);
55}
56
57uint16_t ext4_directory_entry_ll_get_name_length(
58 ext4_superblock_t *sb, ext4_directory_entry_ll_t *de)
59{
60 if (ext4_superblock_get_rev_level(sb) == 0 &&
61 ext4_superblock_get_minor_rev_level(sb) < 5) {
62 return ((uint16_t)de->name_length_high) << 8 |
63 ((uint16_t)de->name_length);
64 }
65 return de->name_length;
66}
67
68uint8_t ext4_directory_dx_root_info_get_hash_version(ext4_directory_dx_root_info_t *root_info)
69{
70 return root_info->hash_version;
71}
72
73uint8_t ext4_directory_dx_root_info_get_info_length(ext4_directory_dx_root_info_t *root_info)
74{
75 return root_info->info_length;
76}
77
78uint8_t ext4_directory_dx_root_info_get_indirect_levels(ext4_directory_dx_root_info_t *root_info)
79{
80 return root_info->indirect_levels;
81}
82
83uint16_t ext4_directory_dx_countlimit_get_limit(ext4_directory_dx_countlimit_t *countlimit)
84{
85 return uint16_t_le2host(countlimit->limit);
86}
87uint16_t ext4_directory_dx_countlimit_get_count(ext4_directory_dx_countlimit_t *countlimit)
88{
89 return uint16_t_le2host(countlimit->count);
90}
91
92uint32_t ext4_directory_dx_entry_get_hash(ext4_directory_dx_entry_t *entry)
93{
94 return uint32_t_le2host(entry->hash);
95}
96
97uint32_t ext4_directory_dx_entry_get_block(ext4_directory_dx_entry_t *entry)
98{
99 return uint32_t_le2host(entry->block);
100}
101
102
103
104int ext4_directory_iterator_init(ext4_directory_iterator_t *it,
105 ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, aoff64_t pos)
106{
107 it->inode_ref = inode_ref;
108 it->fs = fs;
109 it->current = NULL;
110 it->current_offset = 0;
111 it->current_block = NULL;
112
113 return ext4_directory_iterator_seek(it, pos);
114}
115
116
117int ext4_directory_iterator_next(ext4_directory_iterator_t *it)
118{
119 uint16_t skip;
120
121 assert(it->current != NULL);
122
123 skip = ext4_directory_entry_ll_get_entry_length(it->current);
124
125 return ext4_directory_iterator_seek(it, it->current_offset + skip);
126}
127
128
129int ext4_directory_iterator_seek(ext4_directory_iterator_t *it, aoff64_t pos)
130{
131 int rc;
132
133 uint64_t size;
134 aoff64_t current_block_idx;
135 aoff64_t next_block_idx;
136 uint32_t next_block_phys_idx;
137 uint32_t block_size;
138
139 size = ext4_inode_get_size(it->fs->superblock, it->inode_ref->inode);
140
141 /* The iterator is not valid until we seek to the desired position */
142 it->current = NULL;
143
144 /* Are we at the end? */
145 if (pos >= size) {
146 if (it->current_block) {
147 rc = block_put(it->current_block);
148 it->current_block = NULL;
149 if (rc != EOK) {
150 return rc;
151 }
152 }
153
154 it->current_offset = pos;
155 return EOK;
156 }
157
158 block_size = ext4_superblock_get_block_size(it->fs->superblock);
159 current_block_idx = it->current_offset / block_size;
160 next_block_idx = pos / block_size;
161
162 /* If we don't have a block or are moving accross block boundary,
163 * we need to get another block
164 */
165 if (it->current_block == NULL || current_block_idx != next_block_idx) {
166 if (it->current_block) {
167 rc = block_put(it->current_block);
168 it->current_block = NULL;
169 if (rc != EOK) {
170 return rc;
171 }
172 }
173
174 rc = ext4_filesystem_get_inode_data_block_index(it->fs,
175 it->inode_ref->inode, next_block_idx, &next_block_phys_idx);
176 if (rc != EOK) {
177 return rc;
178 }
179
180 rc = block_get(&it->current_block, it->fs->device, next_block_phys_idx,
181 BLOCK_FLAGS_NONE);
182 if (rc != EOK) {
183 it->current_block = NULL;
184 return rc;
185 }
186 }
187
188 it->current_offset = pos;
189
190 return ext4_directory_iterator_set(it, block_size);
191}
192
193static int ext4_directory_iterator_set(ext4_directory_iterator_t *it,
194 uint32_t block_size)
195{
196 uint32_t offset_in_block = it->current_offset % block_size;
197
198 it->current = NULL;
199
200 /* Ensure proper alignment */
201 if ((offset_in_block % 4) != 0) {
202 return EIO;
203 }
204
205 /* Ensure that the core of the entry does not overflow the block */
206 if (offset_in_block > block_size - 8) {
207 return EIO;
208 }
209
210 ext4_directory_entry_ll_t *entry = it->current_block->data + offset_in_block;
211
212 /* Ensure that the whole entry does not overflow the block */
213 uint16_t length = ext4_directory_entry_ll_get_entry_length(entry);
214 if (offset_in_block + length > block_size) {
215 return EIO;
216 }
217
218 /* Ensure the name length is not too large */
219 if (ext4_directory_entry_ll_get_name_length(it->fs->superblock,
220 entry) > length-8) {
221 return EIO;
222 }
223
224 it->current = entry;
225 return EOK;
226}
227
228
229int ext4_directory_iterator_fini(ext4_directory_iterator_t *it)
230{
231 int rc;
232
233 it->fs = NULL;
234 it->inode_ref = NULL;
235 it->current = NULL;
236
237 if (it->current_block) {
238 rc = block_put(it->current_block);
239 if (rc != EOK) {
240 return rc;
241 }
242 }
243
244 return EOK;
245}
246
247int ext4_directory_dx_find_entry(ext4_directory_iterator_t *it,
248 ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, const char *name)
249{
250 int rc;
251 uint32_t fblock;
252 block_t *phys_block;
253 ext4_directory_dx_root_t *root;
254 uint32_t hash;
255 ext4_directory_dx_hash_info_t hinfo;
256
257 // get direct block 0 (index root)
258 rc = ext4_filesystem_get_inode_data_block_index(fs, inode_ref->inode, 0, &fblock);
259 if (rc != EOK) {
260 return rc;
261 }
262
263 rc = block_get(&phys_block, fs->device, fblock, BLOCK_FLAGS_NONE);
264 if (rc != EOK) {
265 it->current_block = NULL;
266 return rc;
267 }
268
269 // Now having index root
270 root = (ext4_directory_dx_root_t *)phys_block->data;
271
272 // Check hash version - only if supported
273 EXT4FS_DBG("hash_version = \%u", root->info.hash_version);
274
275 // Check unused flags
276 if (root->info.unused_flags != 0) {
277 EXT4FS_DBG("ERR: unused_flags = \%u", root->info.unused_flags);
278 block_put(phys_block);
279 return EXT4_ERR_BAD_DX_DIR;
280 }
281
282 // Check indirect levels
283 if (root->info.indirect_levels > 1) {
284 EXT4FS_DBG("ERR: indirect_levels = \%u", root->info.indirect_levels);
285 block_put(phys_block);
286 return EXT4_ERR_BAD_DX_DIR;
287 }
288
289 uint32_t bs = ext4_superblock_get_block_size(fs->superblock);
290
291 uint32_t entry_space = bs - 2* sizeof(ext4_directory_dx_dot_entry_t) - sizeof(ext4_directory_dx_root_info_t);
292 entry_space = entry_space / sizeof(ext4_directory_dx_entry_t);
293
294
295 uint32_t limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)&root->entries);
296 uint32_t count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)&root->entries);
297
298 if (limit != entry_space) {
299 block_put(phys_block);
300 return EXT4_ERR_BAD_DX_DIR;
301 }
302
303 if ((count == 0) || (count > limit)) {
304 block_put(phys_block);
305 return EXT4_ERR_BAD_DX_DIR;
306 }
307
308 /* DEBUG list
309 for (uint16_t i = 0; i < count; ++i) {
310 uint32_t hash = ext4_directory_dx_entry_get_hash(&root->entries[i]);
311 uint32_t block = ext4_directory_dx_entry_get_block(&root->entries[i]);
312 EXT4FS_DBG("hash = \%u, block = \%u", hash, block);
313 }
314 */
315
316 hinfo.hash_version = ext4_directory_dx_root_info_get_hash_version(&root->info);
317 if ((hinfo.hash_version <= EXT4_DIRECTORY_DX_HASH_TEA)
318 && (ext4_superblock_has_flag(fs->superblock, EXT4_SUPERBLOCK_FLAGS_UNSIGNED_HASH))) {
319 // 3 is magic from ext4 linux implementation
320 hinfo.hash_version += 3;
321 }
322
323 hinfo.seed = ext4_superblock_get_hash_seed(fs->superblock);
324 hinfo.hash = 0;
325 if (name) {
326 ext4_directory_hash(&hinfo, name);
327 }
328
329 hash = hinfo.hash;
330
331 ext4_directory_dx_entry_t *p, *q, *m;
332
333 // TODO cycle
334 // while (true)
335
336 p = &root->entries[1];
337 q = &root->entries[count - 1];
338
339 while (p <= q) {
340 m = p + (q - p) / 2;
341 if (ext4_directory_dx_entry_get_hash(m) > hash) {
342 q = m - 1;
343 } else {
344 p = m + 1;
345 }
346 }
347
348 /* TODO move to leaf or next node
349 at = p - 1;
350 dxtrace(printk(" %x->%u\n", at == entries? 0: dx_get_hash(at), dx_get_block(at)));
351 frame->bh = bh;
352 frame->entries = entries;
353 frame->at = at;
354
355 if (indirect == 0) {
356 // TODO write return values !!!
357 return EOK;
358 }
359
360 indirect--;
361
362 // TODO read next block
363 if (!(bh = ext4_bread (NULL,dir, dx_get_block(at), 0, err)))
364 goto fail2;
365 at = entries = ((struct dx_node *) bh->b_data)->entries;
366 if (dx_get_limit(entries) != dx_node_limit (dir)) {
367 ext4_warning(dir->i_sb, "dx entry: limit != node limit");
368 brelse(bh);
369 *err = ERR_BAD_DX_DIR;
370 goto fail2;
371 }
372 frame++;
373 frame->bh = NULL;
374 */
375
376 // } END WHILE
377
378
379 // TODO delete it !!!
380 return EXT4_ERR_BAD_DX_DIR;
381
382 if ((it->current == NULL) || (it->current->inode == 0)) {
383 return ENOENT;
384 }
385
386 return EOK;
387}
388
389void ext4_directory_hash(ext4_directory_dx_hash_info_t *hinfo, const char* name)
390{
391 // TODO
392}
393
394/**
395 * @}
396 */
Note: See TracBrowser for help on using the repository browser.