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_index.c
|
---|
34 | * @brief Ext4 directory index operations.
|
---|
35 | */
|
---|
36 |
|
---|
37 | #include <byteorder.h>
|
---|
38 | #include <errno.h>
|
---|
39 | #include <malloc.h>
|
---|
40 | #include <sort.h>
|
---|
41 | #include "libext4.h"
|
---|
42 |
|
---|
43 | /** Type entry to pass to sorting algorithm.
|
---|
44 | *
|
---|
45 | */
|
---|
46 | typedef struct ext4_dx_sort_entry {
|
---|
47 | uint32_t hash;
|
---|
48 | uint32_t rec_len;
|
---|
49 | void *dentry;
|
---|
50 | } ext4_dx_sort_entry_t;
|
---|
51 |
|
---|
52 | /** Get hash version used in directory index.
|
---|
53 | *
|
---|
54 | * @param root_info Pointer to root info structure of index
|
---|
55 | *
|
---|
56 | * @return Hash algorithm version
|
---|
57 | *
|
---|
58 | */
|
---|
59 | uint8_t ext4_directory_dx_root_info_get_hash_version(
|
---|
60 | ext4_directory_dx_root_info_t *root_info)
|
---|
61 | {
|
---|
62 | return root_info->hash_version;
|
---|
63 | }
|
---|
64 |
|
---|
65 | /** Set hash version, that will be used in directory index.
|
---|
66 | *
|
---|
67 | * @param root_info Pointer to root info structure of index
|
---|
68 | * @param version Hash algorithm version
|
---|
69 | *
|
---|
70 | */
|
---|
71 | void ext4_directory_dx_root_info_set_hash_version(
|
---|
72 | ext4_directory_dx_root_info_t *root_info, uint8_t version)
|
---|
73 | {
|
---|
74 | root_info->hash_version = version;
|
---|
75 | }
|
---|
76 |
|
---|
77 | /** Get length of root_info structure in bytes.
|
---|
78 | *
|
---|
79 | * @param root_info Pointer to root info structure of index
|
---|
80 | *
|
---|
81 | * @return Length of the structure
|
---|
82 | *
|
---|
83 | */
|
---|
84 | uint8_t ext4_directory_dx_root_info_get_info_length(
|
---|
85 | ext4_directory_dx_root_info_t *root_info)
|
---|
86 | {
|
---|
87 | return root_info->info_length;
|
---|
88 | }
|
---|
89 |
|
---|
90 | /** Set length of root_info structure in bytes.
|
---|
91 | *
|
---|
92 | * @param root_info Pointer to root info structure of index
|
---|
93 | * @param info_length Length of the structure
|
---|
94 | *
|
---|
95 | */
|
---|
96 | void ext4_directory_dx_root_info_set_info_length(
|
---|
97 | ext4_directory_dx_root_info_t *root_info, uint8_t info_length)
|
---|
98 | {
|
---|
99 | root_info->info_length = info_length;
|
---|
100 | }
|
---|
101 |
|
---|
102 | /** Get number of indirect levels of HTree.
|
---|
103 | *
|
---|
104 | * @param root_info Pointer to root info structure of index
|
---|
105 | *
|
---|
106 | * @return Height of HTree (actually only 0 or 1)
|
---|
107 | *
|
---|
108 | */
|
---|
109 | uint8_t ext4_directory_dx_root_info_get_indirect_levels(
|
---|
110 | ext4_directory_dx_root_info_t *root_info)
|
---|
111 | {
|
---|
112 | return root_info->indirect_levels;
|
---|
113 | }
|
---|
114 |
|
---|
115 | /** Set number of indirect levels of HTree.
|
---|
116 | *
|
---|
117 | * @param root_info Pointer to root info structure of index
|
---|
118 | * @param levels Height of HTree (actually only 0 or 1)
|
---|
119 | *
|
---|
120 | */
|
---|
121 | void ext4_directory_dx_root_info_set_indirect_levels(
|
---|
122 | ext4_directory_dx_root_info_t *root_info, uint8_t levels)
|
---|
123 | {
|
---|
124 | root_info->indirect_levels = levels;
|
---|
125 | }
|
---|
126 |
|
---|
127 | /** Get maximum number of index node entries.
|
---|
128 | *
|
---|
129 | * @param countlimit Pointer to counlimit structure
|
---|
130 | *
|
---|
131 | * @return Maximum of entries in node
|
---|
132 | *
|
---|
133 | */
|
---|
134 | uint16_t ext4_directory_dx_countlimit_get_limit(
|
---|
135 | ext4_directory_dx_countlimit_t *countlimit)
|
---|
136 | {
|
---|
137 | return uint16_t_le2host(countlimit->limit);
|
---|
138 | }
|
---|
139 |
|
---|
140 | /** Set maximum number of index node entries.
|
---|
141 | *
|
---|
142 | * @param countlimit Pointer to counlimit structure
|
---|
143 | * @param limit Maximum of entries in node
|
---|
144 | *
|
---|
145 | */
|
---|
146 | void ext4_directory_dx_countlimit_set_limit(
|
---|
147 | ext4_directory_dx_countlimit_t *countlimit, uint16_t limit)
|
---|
148 | {
|
---|
149 | countlimit->limit = host2uint16_t_le(limit);
|
---|
150 | }
|
---|
151 |
|
---|
152 | /** Get current number of index node entries.
|
---|
153 | *
|
---|
154 | * @param countlimit Pointer to counlimit structure
|
---|
155 | *
|
---|
156 | * @return Number of entries in node
|
---|
157 | *
|
---|
158 | */
|
---|
159 | uint16_t ext4_directory_dx_countlimit_get_count(
|
---|
160 | ext4_directory_dx_countlimit_t *countlimit)
|
---|
161 | {
|
---|
162 | return uint16_t_le2host(countlimit->count);
|
---|
163 | }
|
---|
164 |
|
---|
165 | /** Set current number of index node entries.
|
---|
166 | *
|
---|
167 | * @param countlimit Pointer to counlimit structure
|
---|
168 | * @param count Number of entries in node
|
---|
169 | *
|
---|
170 | */
|
---|
171 | void ext4_directory_dx_countlimit_set_count(
|
---|
172 | ext4_directory_dx_countlimit_t *countlimit, uint16_t count)
|
---|
173 | {
|
---|
174 | countlimit->count = host2uint16_t_le(count);
|
---|
175 | }
|
---|
176 |
|
---|
177 | /** Get hash value of index entry.
|
---|
178 | *
|
---|
179 | * @param entry Pointer to index entry
|
---|
180 | *
|
---|
181 | * @return Hash value
|
---|
182 | *
|
---|
183 | */
|
---|
184 | uint32_t ext4_directory_dx_entry_get_hash(ext4_directory_dx_entry_t *entry)
|
---|
185 | {
|
---|
186 | return uint32_t_le2host(entry->hash);
|
---|
187 | }
|
---|
188 |
|
---|
189 | /** Set hash value of index entry.
|
---|
190 | *
|
---|
191 | * @param entry Pointer to index entry
|
---|
192 | * @param hash Hash value
|
---|
193 | *
|
---|
194 | */
|
---|
195 | void ext4_directory_dx_entry_set_hash(ext4_directory_dx_entry_t *entry,
|
---|
196 | uint32_t hash)
|
---|
197 | {
|
---|
198 | entry->hash = host2uint32_t_le(hash);
|
---|
199 | }
|
---|
200 |
|
---|
201 | /** Get block address where child node is located.
|
---|
202 | *
|
---|
203 | * @param entry Pointer to index entry
|
---|
204 | *
|
---|
205 | * @return Block address of child node
|
---|
206 | *
|
---|
207 | */
|
---|
208 | uint32_t ext4_directory_dx_entry_get_block(ext4_directory_dx_entry_t *entry)
|
---|
209 | {
|
---|
210 | return uint32_t_le2host(entry->block);
|
---|
211 | }
|
---|
212 |
|
---|
213 | /** Set block address where child node is located.
|
---|
214 | *
|
---|
215 | * @param entry Pointer to index entry
|
---|
216 | * @param block Block address of child node
|
---|
217 | *
|
---|
218 | */
|
---|
219 | void ext4_directory_dx_entry_set_block(ext4_directory_dx_entry_t *entry,
|
---|
220 | uint32_t block)
|
---|
221 | {
|
---|
222 | entry->block = host2uint32_t_le(block);
|
---|
223 | }
|
---|
224 |
|
---|
225 | /** Initialize index structure of new directory.
|
---|
226 | *
|
---|
227 | * @param dir Pointer to directory i-node
|
---|
228 | *
|
---|
229 | * @return Error code
|
---|
230 | *
|
---|
231 | */
|
---|
232 | int ext4_directory_dx_init(ext4_inode_ref_t *dir)
|
---|
233 | {
|
---|
234 | /* Load block 0, where will be index root located */
|
---|
235 | uint32_t fblock;
|
---|
236 | int rc = ext4_filesystem_get_inode_data_block_index(dir, 0,
|
---|
237 | &fblock);
|
---|
238 | if (rc != EOK)
|
---|
239 | return rc;
|
---|
240 |
|
---|
241 | block_t *block;
|
---|
242 | rc = block_get(&block, dir->fs->device, fblock, BLOCK_FLAGS_NONE);
|
---|
243 | if (rc != EOK)
|
---|
244 | return rc;
|
---|
245 |
|
---|
246 | /* Initialize pointers to data structures */
|
---|
247 | ext4_directory_dx_root_t *root = block->data;
|
---|
248 | ext4_directory_dx_root_info_t *info = &(root->info);
|
---|
249 |
|
---|
250 | /* Initialize root info structure */
|
---|
251 | uint8_t hash_version =
|
---|
252 | ext4_superblock_get_default_hash_version(dir->fs->superblock);
|
---|
253 |
|
---|
254 | ext4_directory_dx_root_info_set_hash_version(info, hash_version);
|
---|
255 | ext4_directory_dx_root_info_set_indirect_levels(info, 0);
|
---|
256 | ext4_directory_dx_root_info_set_info_length(info, 8);
|
---|
257 |
|
---|
258 | /* Set limit and current number of entries */
|
---|
259 | ext4_directory_dx_countlimit_t *countlimit =
|
---|
260 | (ext4_directory_dx_countlimit_t *) &root->entries;
|
---|
261 | ext4_directory_dx_countlimit_set_count(countlimit, 1);
|
---|
262 |
|
---|
263 | uint32_t block_size =
|
---|
264 | ext4_superblock_get_block_size(dir->fs->superblock);
|
---|
265 | uint32_t entry_space =
|
---|
266 | block_size - 2 * sizeof(ext4_directory_dx_dot_entry_t) -
|
---|
267 | sizeof(ext4_directory_dx_root_info_t);
|
---|
268 | uint16_t root_limit = entry_space / sizeof(ext4_directory_dx_entry_t);
|
---|
269 | ext4_directory_dx_countlimit_set_limit(countlimit, root_limit);
|
---|
270 |
|
---|
271 | /* Append new block, where will be new entries inserted in the future */
|
---|
272 | uint32_t iblock;
|
---|
273 | rc = ext4_filesystem_append_inode_block(dir, &fblock, &iblock);
|
---|
274 | if (rc != EOK) {
|
---|
275 | block_put(block);
|
---|
276 | return rc;
|
---|
277 | }
|
---|
278 |
|
---|
279 | block_t *new_block;
|
---|
280 | rc = block_get(&new_block, dir->fs->device, fblock, BLOCK_FLAGS_NOREAD);
|
---|
281 | if (rc != EOK) {
|
---|
282 | block_put(block);
|
---|
283 | return rc;
|
---|
284 | }
|
---|
285 |
|
---|
286 | /* Fill the whole block with empty entry */
|
---|
287 | ext4_directory_entry_ll_t *block_entry = new_block->data;
|
---|
288 | ext4_directory_entry_ll_set_entry_length(block_entry, block_size);
|
---|
289 | ext4_directory_entry_ll_set_inode(block_entry, 0);
|
---|
290 |
|
---|
291 | new_block->dirty = true;
|
---|
292 | rc = block_put(new_block);
|
---|
293 | if (rc != EOK) {
|
---|
294 | block_put(block);
|
---|
295 | return rc;
|
---|
296 | }
|
---|
297 |
|
---|
298 | /* Connect new block to the only entry in index */
|
---|
299 | ext4_directory_dx_entry_t *entry = root->entries;
|
---|
300 | ext4_directory_dx_entry_set_block(entry, iblock);
|
---|
301 |
|
---|
302 | block->dirty = true;
|
---|
303 |
|
---|
304 | return block_put(block);
|
---|
305 | }
|
---|
306 |
|
---|
307 | /** Initialize hash info structure necessary for index operations.
|
---|
308 | *
|
---|
309 | * @param hinfo Pointer to hinfo to be initialized
|
---|
310 | * @param root_block Root block (number 0) of index
|
---|
311 | * @param sb Pointer to superblock
|
---|
312 | * @param name_len Length of name to be computed hash value from
|
---|
313 | * @param name Name to be computed hash value from
|
---|
314 | *
|
---|
315 | * @return Error code
|
---|
316 | *
|
---|
317 | */
|
---|
318 | static int ext4_directory_hinfo_init(ext4_hash_info_t *hinfo,
|
---|
319 | block_t *root_block, ext4_superblock_t *sb, size_t name_len,
|
---|
320 | const char *name)
|
---|
321 | {
|
---|
322 | ext4_directory_dx_root_t *root =
|
---|
323 | (ext4_directory_dx_root_t *) root_block->data;
|
---|
324 |
|
---|
325 | if ((root->info.hash_version != EXT4_HASH_VERSION_TEA) &&
|
---|
326 | (root->info.hash_version != EXT4_HASH_VERSION_HALF_MD4) &&
|
---|
327 | (root->info.hash_version != EXT4_HASH_VERSION_LEGACY))
|
---|
328 | return EXT4_ERR_BAD_DX_DIR;
|
---|
329 |
|
---|
330 | /* Check unused flags */
|
---|
331 | if (root->info.unused_flags != 0)
|
---|
332 | return EXT4_ERR_BAD_DX_DIR;
|
---|
333 |
|
---|
334 | /* Check indirect levels */
|
---|
335 | if (root->info.indirect_levels > 1)
|
---|
336 | return EXT4_ERR_BAD_DX_DIR;
|
---|
337 |
|
---|
338 | /* Check if node limit is correct */
|
---|
339 | uint32_t block_size = ext4_superblock_get_block_size(sb);
|
---|
340 | uint32_t entry_space = block_size;
|
---|
341 | entry_space -= 2 * sizeof(ext4_directory_dx_dot_entry_t);
|
---|
342 | entry_space -= sizeof(ext4_directory_dx_root_info_t);
|
---|
343 | entry_space = entry_space / sizeof(ext4_directory_dx_entry_t);
|
---|
344 |
|
---|
345 | uint16_t limit = ext4_directory_dx_countlimit_get_limit(
|
---|
346 | (ext4_directory_dx_countlimit_t *) &root->entries);
|
---|
347 | if (limit != entry_space)
|
---|
348 | return EXT4_ERR_BAD_DX_DIR;
|
---|
349 |
|
---|
350 | /* Check hash version and modify if necessary */
|
---|
351 | hinfo->hash_version =
|
---|
352 | ext4_directory_dx_root_info_get_hash_version(&root->info);
|
---|
353 | if ((hinfo->hash_version <= EXT4_HASH_VERSION_TEA) &&
|
---|
354 | (ext4_superblock_has_flag(sb, EXT4_SUPERBLOCK_FLAGS_UNSIGNED_HASH))) {
|
---|
355 | /* 3 is magic from ext4 linux implementation */
|
---|
356 | hinfo->hash_version += 3;
|
---|
357 | }
|
---|
358 |
|
---|
359 | /* Load hash seed from superblock */
|
---|
360 | hinfo->seed = ext4_superblock_get_hash_seed(sb);
|
---|
361 |
|
---|
362 | /* Compute hash value of name */
|
---|
363 | if (name)
|
---|
364 | ext4_hash_string(hinfo, name_len, name);
|
---|
365 |
|
---|
366 | return EOK;
|
---|
367 | }
|
---|
368 |
|
---|
369 | /** Walk through index tree and load leaf with corresponding hash value.
|
---|
370 | *
|
---|
371 | * @param hinfo Initialized hash info structure
|
---|
372 | * @param inode_ref Current i-node
|
---|
373 | * @param root_block Root block (iblock 0), where is root node located
|
---|
374 | * @param dx_block Pointer to leaf node in dx_blocks array
|
---|
375 | * @param dx_blocks Array with the whole path from root to leaf
|
---|
376 | *
|
---|
377 | * @return Error code
|
---|
378 | *
|
---|
379 | */
|
---|
380 | static int ext4_directory_dx_get_leaf(ext4_hash_info_t *hinfo,
|
---|
381 | ext4_inode_ref_t *inode_ref, block_t *root_block,
|
---|
382 | ext4_directory_dx_block_t **dx_block, ext4_directory_dx_block_t *dx_blocks)
|
---|
383 | {
|
---|
384 | ext4_directory_dx_block_t *tmp_dx_block = dx_blocks;
|
---|
385 | ext4_directory_dx_root_t *root =
|
---|
386 | (ext4_directory_dx_root_t *) root_block->data;
|
---|
387 | ext4_directory_dx_entry_t *entries =
|
---|
388 | (ext4_directory_dx_entry_t *) &root->entries;
|
---|
389 |
|
---|
390 | uint16_t limit = ext4_directory_dx_countlimit_get_limit(
|
---|
391 | (ext4_directory_dx_countlimit_t *) entries);
|
---|
392 | uint8_t indirect_level =
|
---|
393 | ext4_directory_dx_root_info_get_indirect_levels(&root->info);
|
---|
394 |
|
---|
395 | block_t *tmp_block = root_block;
|
---|
396 | ext4_directory_dx_entry_t *p;
|
---|
397 | ext4_directory_dx_entry_t *q;
|
---|
398 | ext4_directory_dx_entry_t *m;
|
---|
399 | ext4_directory_dx_entry_t *at;
|
---|
400 |
|
---|
401 | /* Walk through the index tree */
|
---|
402 | while (true) {
|
---|
403 | uint16_t count = ext4_directory_dx_countlimit_get_count(
|
---|
404 | (ext4_directory_dx_countlimit_t *) entries);
|
---|
405 | if ((count == 0) || (count > limit))
|
---|
406 | return EXT4_ERR_BAD_DX_DIR;
|
---|
407 |
|
---|
408 | /* Do binary search in every node */
|
---|
409 | p = entries + 1;
|
---|
410 | q = entries + count - 1;
|
---|
411 |
|
---|
412 | while (p <= q) {
|
---|
413 | m = p + (q - p) / 2;
|
---|
414 | if (ext4_directory_dx_entry_get_hash(m) > hinfo->hash)
|
---|
415 | q = m - 1;
|
---|
416 | else
|
---|
417 | p = m + 1;
|
---|
418 | }
|
---|
419 |
|
---|
420 | at = p - 1;
|
---|
421 |
|
---|
422 | /* Write results */
|
---|
423 | tmp_dx_block->block = tmp_block;
|
---|
424 | tmp_dx_block->entries = entries;
|
---|
425 | tmp_dx_block->position = at;
|
---|
426 |
|
---|
427 | /* Is algorithm in the leaf? */
|
---|
428 | if (indirect_level == 0) {
|
---|
429 | *dx_block = tmp_dx_block;
|
---|
430 | return EOK;
|
---|
431 | }
|
---|
432 |
|
---|
433 | /* Goto child node */
|
---|
434 | uint32_t next_block = ext4_directory_dx_entry_get_block(at);
|
---|
435 |
|
---|
436 | indirect_level--;
|
---|
437 |
|
---|
438 | uint32_t fblock;
|
---|
439 | int rc = ext4_filesystem_get_inode_data_block_index(inode_ref,
|
---|
440 | next_block, &fblock);
|
---|
441 | if (rc != EOK)
|
---|
442 | return rc;
|
---|
443 |
|
---|
444 | rc = block_get(&tmp_block, inode_ref->fs->device, fblock,
|
---|
445 | BLOCK_FLAGS_NONE);
|
---|
446 | if (rc != EOK)
|
---|
447 | return rc;
|
---|
448 |
|
---|
449 | entries = ((ext4_directory_dx_node_t *) tmp_block->data)->entries;
|
---|
450 | limit = ext4_directory_dx_countlimit_get_limit(
|
---|
451 | (ext4_directory_dx_countlimit_t *) entries);
|
---|
452 |
|
---|
453 | uint16_t entry_space =
|
---|
454 | ext4_superblock_get_block_size(inode_ref->fs->superblock) -
|
---|
455 | sizeof(ext4_directory_dx_dot_entry_t);
|
---|
456 | entry_space = entry_space / sizeof(ext4_directory_dx_entry_t);
|
---|
457 |
|
---|
458 | if (limit != entry_space) {
|
---|
459 | block_put(tmp_block);
|
---|
460 | return EXT4_ERR_BAD_DX_DIR;
|
---|
461 | }
|
---|
462 |
|
---|
463 | ++tmp_dx_block;
|
---|
464 | }
|
---|
465 |
|
---|
466 | /* Unreachable */
|
---|
467 | return EOK;
|
---|
468 | }
|
---|
469 |
|
---|
470 | /** Check if the the next block would be checked during entry search.
|
---|
471 | *
|
---|
472 | * @param inode_ref Directory i-node
|
---|
473 | * @param hash Hash value to check
|
---|
474 | * @param dx_block Current block
|
---|
475 | * @param dx_blocks Array with path from root to leaf node
|
---|
476 | *
|
---|
477 | * @return Error code
|
---|
478 | *
|
---|
479 | */
|
---|
480 | static int ext4_directory_dx_next_block(ext4_inode_ref_t *inode_ref,
|
---|
481 | uint32_t hash, ext4_directory_dx_block_t *dx_block,
|
---|
482 | ext4_directory_dx_block_t *dx_blocks)
|
---|
483 | {
|
---|
484 | uint32_t num_handles = 0;
|
---|
485 | ext4_directory_dx_block_t *p = dx_block;
|
---|
486 |
|
---|
487 | /* Try to find data block with next bunch of entries */
|
---|
488 | while (true) {
|
---|
489 | p->position++;
|
---|
490 | uint16_t count = ext4_directory_dx_countlimit_get_count(
|
---|
491 | (ext4_directory_dx_countlimit_t *) p->entries);
|
---|
492 |
|
---|
493 | if (p->position < p->entries + count)
|
---|
494 | break;
|
---|
495 |
|
---|
496 | if (p == dx_blocks)
|
---|
497 | return EOK;
|
---|
498 |
|
---|
499 | num_handles++;
|
---|
500 | p--;
|
---|
501 | }
|
---|
502 |
|
---|
503 | /* Check hash collision (if not occured - no next block cannot be used) */
|
---|
504 | uint32_t current_hash = ext4_directory_dx_entry_get_hash(p->position);
|
---|
505 | if ((hash & 1) == 0) {
|
---|
506 | if ((current_hash & ~1) != hash)
|
---|
507 | return 0;
|
---|
508 | }
|
---|
509 |
|
---|
510 | /* Fill new path */
|
---|
511 | while (num_handles--) {
|
---|
512 | uint32_t block_idx =
|
---|
513 | ext4_directory_dx_entry_get_block(p->position);
|
---|
514 | uint32_t block_addr;
|
---|
515 |
|
---|
516 | int rc = ext4_filesystem_get_inode_data_block_index(inode_ref,
|
---|
517 | block_idx, &block_addr);
|
---|
518 | if (rc != EOK)
|
---|
519 | return rc;
|
---|
520 |
|
---|
521 | block_t *block;
|
---|
522 | rc = block_get(&block, inode_ref->fs->device, block_addr, BLOCK_FLAGS_NONE);
|
---|
523 | if (rc != EOK)
|
---|
524 | return rc;
|
---|
525 |
|
---|
526 | p++;
|
---|
527 |
|
---|
528 | /* Don't forget to put old block (prevent memory leak) */
|
---|
529 | block_put(p->block);
|
---|
530 |
|
---|
531 | p->block = block;
|
---|
532 | p->entries = ((ext4_directory_dx_node_t *) block->data)->entries;
|
---|
533 | p->position = p->entries;
|
---|
534 | }
|
---|
535 |
|
---|
536 | return ENOENT;
|
---|
537 | }
|
---|
538 |
|
---|
539 | /** Try to find directory entry using directory index.
|
---|
540 | *
|
---|
541 | * @param result Output value - if entry will be found,
|
---|
542 | * than will be passed through this parameter
|
---|
543 | * @param inode_ref Directory i-node
|
---|
544 | * @param name_len Length of name to be found
|
---|
545 | * @param name Name to be found
|
---|
546 | *
|
---|
547 | * @return Error code
|
---|
548 | *
|
---|
549 | */
|
---|
550 | int ext4_directory_dx_find_entry(ext4_directory_search_result_t *result,
|
---|
551 | ext4_inode_ref_t *inode_ref, size_t name_len, const char *name)
|
---|
552 | {
|
---|
553 | /* Load direct block 0 (index root) */
|
---|
554 | uint32_t root_block_addr;
|
---|
555 | int rc = ext4_filesystem_get_inode_data_block_index(inode_ref, 0,
|
---|
556 | &root_block_addr);
|
---|
557 | if (rc != EOK)
|
---|
558 | return rc;
|
---|
559 |
|
---|
560 | ext4_filesystem_t *fs = inode_ref->fs;
|
---|
561 |
|
---|
562 | block_t *root_block;
|
---|
563 | rc = block_get(&root_block, fs->device, root_block_addr,
|
---|
564 | BLOCK_FLAGS_NONE);
|
---|
565 | if (rc != EOK)
|
---|
566 | return rc;
|
---|
567 |
|
---|
568 | /* Initialize hash info (compute hash value) */
|
---|
569 | ext4_hash_info_t hinfo;
|
---|
570 | rc = ext4_directory_hinfo_init(&hinfo, root_block, fs->superblock,
|
---|
571 | name_len, name);
|
---|
572 | if (rc != EOK) {
|
---|
573 | block_put(root_block);
|
---|
574 | return EXT4_ERR_BAD_DX_DIR;
|
---|
575 | }
|
---|
576 |
|
---|
577 | /*
|
---|
578 | * Hardcoded number 2 means maximum height of index tree,
|
---|
579 | * specified in the Linux driver.
|
---|
580 | */
|
---|
581 | ext4_directory_dx_block_t dx_blocks[2];
|
---|
582 | ext4_directory_dx_block_t *dx_block;
|
---|
583 | ext4_directory_dx_block_t *tmp;
|
---|
584 |
|
---|
585 | rc = ext4_directory_dx_get_leaf(&hinfo, inode_ref, root_block,
|
---|
586 | &dx_block, dx_blocks);
|
---|
587 | if (rc != EOK) {
|
---|
588 | block_put(root_block);
|
---|
589 | return EXT4_ERR_BAD_DX_DIR;
|
---|
590 | }
|
---|
591 |
|
---|
592 | do {
|
---|
593 | /* Load leaf block */
|
---|
594 | uint32_t leaf_block_idx =
|
---|
595 | ext4_directory_dx_entry_get_block(dx_block->position);
|
---|
596 | uint32_t leaf_block_addr;
|
---|
597 |
|
---|
598 | rc = ext4_filesystem_get_inode_data_block_index(inode_ref,
|
---|
599 | leaf_block_idx, &leaf_block_addr);
|
---|
600 | if (rc != EOK)
|
---|
601 | goto cleanup;
|
---|
602 |
|
---|
603 | block_t *leaf_block;
|
---|
604 | rc = block_get(&leaf_block, fs->device, leaf_block_addr,
|
---|
605 | BLOCK_FLAGS_NONE);
|
---|
606 | if (rc != EOK)
|
---|
607 | goto cleanup;
|
---|
608 |
|
---|
609 | /* Linear search inside block */
|
---|
610 | ext4_directory_entry_ll_t *res_dentry;
|
---|
611 | rc = ext4_directory_find_in_block(leaf_block, fs->superblock,
|
---|
612 | name_len, name, &res_dentry);
|
---|
613 |
|
---|
614 | /* Found => return it */
|
---|
615 | if (rc == EOK) {
|
---|
616 | result->block = leaf_block;
|
---|
617 | result->dentry = res_dentry;
|
---|
618 | goto cleanup;
|
---|
619 | }
|
---|
620 |
|
---|
621 | /* Not found, leave untouched */
|
---|
622 | block_put(leaf_block);
|
---|
623 |
|
---|
624 | if (rc != ENOENT)
|
---|
625 | goto cleanup;
|
---|
626 |
|
---|
627 | /* check if the next block could be checked */
|
---|
628 | rc = ext4_directory_dx_next_block(inode_ref, hinfo.hash,
|
---|
629 | dx_block, &dx_blocks[0]);
|
---|
630 | if (rc < 0)
|
---|
631 | goto cleanup;
|
---|
632 | } while (rc == ENOENT);
|
---|
633 |
|
---|
634 | /* Entry not found */
|
---|
635 | rc = ENOENT;
|
---|
636 |
|
---|
637 | cleanup:
|
---|
638 | /* The whole path must be released (preventing memory leak) */
|
---|
639 | tmp = dx_blocks;
|
---|
640 |
|
---|
641 | while (tmp <= dx_block) {
|
---|
642 | block_put(tmp->block);
|
---|
643 | ++tmp;
|
---|
644 | }
|
---|
645 |
|
---|
646 | return rc;
|
---|
647 | }
|
---|
648 |
|
---|
649 | /** Compare function used to pass in quicksort implementation.
|
---|
650 | *
|
---|
651 | * It can compare two entries by hash value.
|
---|
652 | *
|
---|
653 | * @param arg1 First entry
|
---|
654 | * @param arg2 Second entry
|
---|
655 | * @param dummy Unused parameter, can be NULL
|
---|
656 | *
|
---|
657 | * @return Classic compare result
|
---|
658 | * (0: equal, -1: arg1 < arg2, 1: arg1 > arg2)
|
---|
659 | *
|
---|
660 | */
|
---|
661 | static int ext4_directory_dx_entry_comparator(void *arg1, void *arg2, void *dummy)
|
---|
662 | {
|
---|
663 | ext4_dx_sort_entry_t *entry1 = arg1;
|
---|
664 | ext4_dx_sort_entry_t *entry2 = arg2;
|
---|
665 |
|
---|
666 | if (entry1->hash == entry2->hash)
|
---|
667 | return 0;
|
---|
668 |
|
---|
669 | if (entry1->hash < entry2->hash)
|
---|
670 | return -1;
|
---|
671 | else
|
---|
672 | return 1;
|
---|
673 | }
|
---|
674 |
|
---|
675 | /** Insert new index entry to block.
|
---|
676 | *
|
---|
677 | * Note that space for new entry must be checked by caller.
|
---|
678 | *
|
---|
679 | * @param index_block Block where to insert new entry
|
---|
680 | * @param hash Hash value covered by child node
|
---|
681 | * @param iblock Logical number of child block
|
---|
682 | *
|
---|
683 | */
|
---|
684 | static void ext4_directory_dx_insert_entry(
|
---|
685 | ext4_directory_dx_block_t *index_block, uint32_t hash, uint32_t iblock)
|
---|
686 | {
|
---|
687 | ext4_directory_dx_entry_t *old_index_entry = index_block->position;
|
---|
688 | ext4_directory_dx_entry_t *new_index_entry = old_index_entry + 1;
|
---|
689 |
|
---|
690 | ext4_directory_dx_countlimit_t *countlimit =
|
---|
691 | (ext4_directory_dx_countlimit_t *) index_block->entries;
|
---|
692 | uint32_t count = ext4_directory_dx_countlimit_get_count(countlimit);
|
---|
693 |
|
---|
694 | ext4_directory_dx_entry_t *start_index = index_block->entries;
|
---|
695 | size_t bytes = (void *) (start_index + count) - (void *) (new_index_entry);
|
---|
696 |
|
---|
697 | memmove(new_index_entry + 1, new_index_entry, bytes);
|
---|
698 |
|
---|
699 | ext4_directory_dx_entry_set_block(new_index_entry, iblock);
|
---|
700 | ext4_directory_dx_entry_set_hash(new_index_entry, hash);
|
---|
701 |
|
---|
702 | ext4_directory_dx_countlimit_set_count(countlimit, count + 1);
|
---|
703 |
|
---|
704 | index_block->block->dirty = true;
|
---|
705 | }
|
---|
706 |
|
---|
707 | /** Split directory entries to two parts preventing node overflow.
|
---|
708 | *
|
---|
709 | * @param inode_ref Directory i-node
|
---|
710 | * @param hinfo Hash info
|
---|
711 | * @param old_data_block Block with data to be split
|
---|
712 | * @param index_block Block where index entries are located
|
---|
713 | * @param new_data_block Output value for newly allocated data block
|
---|
714 | *
|
---|
715 | */
|
---|
716 | static int ext4_directory_dx_split_data(ext4_inode_ref_t *inode_ref,
|
---|
717 | ext4_hash_info_t *hinfo, block_t *old_data_block,
|
---|
718 | ext4_directory_dx_block_t *index_block, block_t **new_data_block)
|
---|
719 | {
|
---|
720 | int rc = EOK;
|
---|
721 |
|
---|
722 | /* Allocate buffer for directory entries */
|
---|
723 | uint32_t block_size =
|
---|
724 | ext4_superblock_get_block_size(inode_ref->fs->superblock);
|
---|
725 | void *entry_buffer = malloc(block_size);
|
---|
726 | if (entry_buffer == NULL)
|
---|
727 | return ENOMEM;
|
---|
728 |
|
---|
729 | /* dot entry has the smallest size available */
|
---|
730 | uint32_t max_entry_count =
|
---|
731 | block_size / sizeof(ext4_directory_dx_dot_entry_t);
|
---|
732 |
|
---|
733 | /* Allocate sort entry */
|
---|
734 | ext4_dx_sort_entry_t *sort_array =
|
---|
735 | malloc(max_entry_count * sizeof(ext4_dx_sort_entry_t));
|
---|
736 | if (sort_array == NULL) {
|
---|
737 | free(entry_buffer);
|
---|
738 | return ENOMEM;
|
---|
739 | }
|
---|
740 |
|
---|
741 | uint32_t idx = 0;
|
---|
742 | uint32_t real_size = 0;
|
---|
743 |
|
---|
744 | /* Initialize hinfo */
|
---|
745 | ext4_hash_info_t tmp_hinfo;
|
---|
746 | memcpy(&tmp_hinfo, hinfo, sizeof(ext4_hash_info_t));
|
---|
747 |
|
---|
748 | /* Load all valid entries to the buffer */
|
---|
749 | ext4_directory_entry_ll_t *dentry = old_data_block->data;
|
---|
750 | void *entry_buffer_ptr = entry_buffer;
|
---|
751 | while ((void *)dentry < old_data_block->data + block_size) {
|
---|
752 | /* Read only valid entries */
|
---|
753 | if (ext4_directory_entry_ll_get_inode(dentry) != 0) {
|
---|
754 | uint8_t len = ext4_directory_entry_ll_get_name_length(
|
---|
755 | inode_ref->fs->superblock, dentry);
|
---|
756 | ext4_hash_string(&tmp_hinfo, len, (char *) dentry->name);
|
---|
757 |
|
---|
758 | uint32_t rec_len = 8 + len;
|
---|
759 |
|
---|
760 | if ((rec_len % 4) != 0)
|
---|
761 | rec_len += 4 - (rec_len % 4);
|
---|
762 |
|
---|
763 | memcpy(entry_buffer_ptr, dentry, rec_len);
|
---|
764 |
|
---|
765 | sort_array[idx].dentry = entry_buffer_ptr;
|
---|
766 | sort_array[idx].rec_len = rec_len;
|
---|
767 | sort_array[idx].hash = tmp_hinfo.hash;
|
---|
768 |
|
---|
769 | entry_buffer_ptr += rec_len;
|
---|
770 | real_size += rec_len;
|
---|
771 | idx++;
|
---|
772 | }
|
---|
773 |
|
---|
774 | dentry = (void *) dentry +
|
---|
775 | ext4_directory_entry_ll_get_entry_length(dentry);
|
---|
776 | }
|
---|
777 |
|
---|
778 | /* Sort all entries */
|
---|
779 | qsort(sort_array, idx, sizeof(ext4_dx_sort_entry_t),
|
---|
780 | ext4_directory_dx_entry_comparator, NULL);
|
---|
781 |
|
---|
782 | /* Allocate new block for store the second part of entries */
|
---|
783 | uint32_t new_fblock;
|
---|
784 | uint32_t new_iblock;
|
---|
785 | rc = ext4_filesystem_append_inode_block(inode_ref, &new_fblock,
|
---|
786 | &new_iblock);
|
---|
787 | if (rc != EOK) {
|
---|
788 | free(sort_array);
|
---|
789 | free(entry_buffer);
|
---|
790 | return rc;
|
---|
791 | }
|
---|
792 |
|
---|
793 | /* Load new block */
|
---|
794 | block_t *new_data_block_tmp;
|
---|
795 | rc = block_get(&new_data_block_tmp, inode_ref->fs->device,
|
---|
796 | new_fblock, BLOCK_FLAGS_NOREAD);
|
---|
797 | if (rc != EOK) {
|
---|
798 | free(sort_array);
|
---|
799 | free(entry_buffer);
|
---|
800 | return rc;
|
---|
801 | }
|
---|
802 |
|
---|
803 | /*
|
---|
804 | * Distribute entries to two blocks (by size)
|
---|
805 | * - compute the half
|
---|
806 | */
|
---|
807 | uint32_t new_hash = 0;
|
---|
808 | uint32_t current_size = 0;
|
---|
809 | uint32_t mid = 0;
|
---|
810 | for (uint32_t i = 0; i < idx; ++i) {
|
---|
811 | if ((current_size + sort_array[i].rec_len) > (real_size / 2)) {
|
---|
812 | new_hash = sort_array[i].hash;
|
---|
813 | mid = i;
|
---|
814 | break;
|
---|
815 | }
|
---|
816 |
|
---|
817 | current_size += sort_array[i].rec_len;
|
---|
818 | }
|
---|
819 |
|
---|
820 | /* Check hash collision */
|
---|
821 | uint32_t continued = 0;
|
---|
822 | if (new_hash == sort_array[mid-1].hash)
|
---|
823 | continued = 1;
|
---|
824 |
|
---|
825 | uint32_t offset = 0;
|
---|
826 | void *ptr;
|
---|
827 |
|
---|
828 | /* First part - to the old block */
|
---|
829 | for (uint32_t i = 0; i < mid; ++i) {
|
---|
830 | ptr = old_data_block->data + offset;
|
---|
831 | memcpy(ptr, sort_array[i].dentry, sort_array[i].rec_len);
|
---|
832 |
|
---|
833 | ext4_directory_entry_ll_t *tmp = ptr;
|
---|
834 | if (i < (mid - 1))
|
---|
835 | ext4_directory_entry_ll_set_entry_length(tmp,
|
---|
836 | sort_array[i].rec_len);
|
---|
837 | else
|
---|
838 | ext4_directory_entry_ll_set_entry_length(tmp,
|
---|
839 | block_size - offset);
|
---|
840 |
|
---|
841 | offset += sort_array[i].rec_len;
|
---|
842 | }
|
---|
843 |
|
---|
844 | /* Second part - to the new block */
|
---|
845 | offset = 0;
|
---|
846 | for (uint32_t i = mid; i < idx; ++i) {
|
---|
847 | ptr = new_data_block_tmp->data + offset;
|
---|
848 | memcpy(ptr, sort_array[i].dentry, sort_array[i].rec_len);
|
---|
849 |
|
---|
850 | ext4_directory_entry_ll_t *tmp = ptr;
|
---|
851 | if (i < (idx - 1))
|
---|
852 | ext4_directory_entry_ll_set_entry_length(tmp,
|
---|
853 | sort_array[i].rec_len);
|
---|
854 | else
|
---|
855 | ext4_directory_entry_ll_set_entry_length(tmp,
|
---|
856 | block_size - offset);
|
---|
857 |
|
---|
858 | offset += sort_array[i].rec_len;
|
---|
859 | }
|
---|
860 |
|
---|
861 | /* Do some steps to finish operation */
|
---|
862 | old_data_block->dirty = true;
|
---|
863 | new_data_block_tmp->dirty = true;
|
---|
864 |
|
---|
865 | free(sort_array);
|
---|
866 | free(entry_buffer);
|
---|
867 |
|
---|
868 | ext4_directory_dx_insert_entry(index_block, new_hash + continued,
|
---|
869 | new_iblock);
|
---|
870 |
|
---|
871 | *new_data_block = new_data_block_tmp;
|
---|
872 |
|
---|
873 | return EOK;
|
---|
874 | }
|
---|
875 |
|
---|
876 | /** Split index node and maybe some parent nodes in the tree hierarchy.
|
---|
877 | *
|
---|
878 | * @param inode_ref Directory i-node
|
---|
879 | * @param dx_blocks Array with path from root to leaf node
|
---|
880 | * @param dx_block Leaf block to be split if needed
|
---|
881 | *
|
---|
882 | * @return Error code
|
---|
883 | *
|
---|
884 | */
|
---|
885 | static int ext4_directory_dx_split_index(ext4_inode_ref_t *inode_ref,
|
---|
886 | ext4_directory_dx_block_t *dx_blocks, ext4_directory_dx_block_t *dx_block)
|
---|
887 | {
|
---|
888 | ext4_directory_dx_entry_t *entries;
|
---|
889 | if (dx_block == dx_blocks)
|
---|
890 | entries =
|
---|
891 | ((ext4_directory_dx_root_t *) dx_block->block->data)->entries;
|
---|
892 | else
|
---|
893 | entries =
|
---|
894 | ((ext4_directory_dx_node_t *) dx_block->block->data)->entries;
|
---|
895 |
|
---|
896 | ext4_directory_dx_countlimit_t *countlimit =
|
---|
897 | (ext4_directory_dx_countlimit_t *) entries;
|
---|
898 |
|
---|
899 | uint16_t leaf_limit =
|
---|
900 | ext4_directory_dx_countlimit_get_limit(countlimit);
|
---|
901 | uint16_t leaf_count =
|
---|
902 | ext4_directory_dx_countlimit_get_count(countlimit);
|
---|
903 |
|
---|
904 | /* Check if is necessary to split index block */
|
---|
905 | if (leaf_limit == leaf_count) {
|
---|
906 | size_t levels = dx_block - dx_blocks;
|
---|
907 |
|
---|
908 | ext4_directory_dx_entry_t *root_entries =
|
---|
909 | ((ext4_directory_dx_root_t *) dx_blocks[0].block->data)->entries;
|
---|
910 |
|
---|
911 | ext4_directory_dx_countlimit_t *root_countlimit =
|
---|
912 | (ext4_directory_dx_countlimit_t *) root_entries;
|
---|
913 | uint16_t root_limit =
|
---|
914 | ext4_directory_dx_countlimit_get_limit(root_countlimit);
|
---|
915 | uint16_t root_count =
|
---|
916 | ext4_directory_dx_countlimit_get_count(root_countlimit);
|
---|
917 |
|
---|
918 | /* Linux limitation */
|
---|
919 | if ((levels > 0) && (root_limit == root_count))
|
---|
920 | return ENOSPC;
|
---|
921 |
|
---|
922 | /* Add new block to directory */
|
---|
923 | uint32_t new_fblock;
|
---|
924 | uint32_t new_iblock;
|
---|
925 | int rc = ext4_filesystem_append_inode_block(inode_ref,
|
---|
926 | &new_fblock, &new_iblock);
|
---|
927 | if (rc != EOK)
|
---|
928 | return rc;
|
---|
929 |
|
---|
930 | /* load new block */
|
---|
931 | block_t *new_block;
|
---|
932 | rc = block_get(&new_block, inode_ref->fs->device,
|
---|
933 | new_fblock, BLOCK_FLAGS_NOREAD);
|
---|
934 | if (rc != EOK)
|
---|
935 | return rc;
|
---|
936 |
|
---|
937 | ext4_directory_dx_node_t *new_node = new_block->data;
|
---|
938 | ext4_directory_dx_entry_t *new_entries = new_node->entries;
|
---|
939 |
|
---|
940 | uint32_t block_size =
|
---|
941 | ext4_superblock_get_block_size(inode_ref->fs->superblock);
|
---|
942 |
|
---|
943 | /* Split leaf node */
|
---|
944 | if (levels > 0) {
|
---|
945 | uint32_t count_left = leaf_count / 2;
|
---|
946 | uint32_t count_right = leaf_count - count_left;
|
---|
947 | uint32_t hash_right =
|
---|
948 | ext4_directory_dx_entry_get_hash(entries + count_left);
|
---|
949 |
|
---|
950 | /* Copy data to new node */
|
---|
951 | memcpy((void *) new_entries, (void *) (entries + count_left),
|
---|
952 | count_right * sizeof(ext4_directory_dx_entry_t));
|
---|
953 |
|
---|
954 | /* Initialize new node */
|
---|
955 | ext4_directory_dx_countlimit_t *left_countlimit =
|
---|
956 | (ext4_directory_dx_countlimit_t *) entries;
|
---|
957 | ext4_directory_dx_countlimit_t *right_countlimit =
|
---|
958 | (ext4_directory_dx_countlimit_t *) new_entries;
|
---|
959 |
|
---|
960 | ext4_directory_dx_countlimit_set_count(left_countlimit, count_left);
|
---|
961 | ext4_directory_dx_countlimit_set_count(right_countlimit, count_right);
|
---|
962 |
|
---|
963 | uint32_t entry_space =
|
---|
964 | block_size - sizeof(ext4_fake_directory_entry_t);
|
---|
965 | uint32_t node_limit =
|
---|
966 | entry_space / sizeof(ext4_directory_dx_entry_t);
|
---|
967 | ext4_directory_dx_countlimit_set_limit(right_countlimit, node_limit);
|
---|
968 |
|
---|
969 | /* Which index block is target for new entry */
|
---|
970 | uint32_t position_index = (dx_block->position - dx_block->entries);
|
---|
971 | if (position_index >= count_left) {
|
---|
972 | dx_block->block->dirty = true;
|
---|
973 |
|
---|
974 | block_t *block_tmp = dx_block->block;
|
---|
975 | dx_block->block = new_block;
|
---|
976 | dx_block->position =
|
---|
977 | new_entries + position_index - count_left;
|
---|
978 | dx_block->entries = new_entries;
|
---|
979 |
|
---|
980 | new_block = block_tmp;
|
---|
981 | }
|
---|
982 |
|
---|
983 | /* Finally insert new entry */
|
---|
984 | ext4_directory_dx_insert_entry(dx_blocks, hash_right, new_iblock);
|
---|
985 |
|
---|
986 | return block_put(new_block);
|
---|
987 | } else {
|
---|
988 | /* Create second level index */
|
---|
989 |
|
---|
990 | /* Copy data from root to child block */
|
---|
991 | memcpy((void *) new_entries, (void *) entries,
|
---|
992 | leaf_count * sizeof(ext4_directory_dx_entry_t));
|
---|
993 |
|
---|
994 | ext4_directory_dx_countlimit_t *new_countlimit =
|
---|
995 | (ext4_directory_dx_countlimit_t *) new_entries;
|
---|
996 |
|
---|
997 | uint32_t entry_space =
|
---|
998 | block_size - sizeof(ext4_fake_directory_entry_t);
|
---|
999 | uint32_t node_limit =
|
---|
1000 | entry_space / sizeof(ext4_directory_dx_entry_t);
|
---|
1001 | ext4_directory_dx_countlimit_set_limit(new_countlimit, node_limit);
|
---|
1002 |
|
---|
1003 | /* Set values in root node */
|
---|
1004 | ext4_directory_dx_countlimit_t *new_root_countlimit =
|
---|
1005 | (ext4_directory_dx_countlimit_t *) entries;
|
---|
1006 |
|
---|
1007 | ext4_directory_dx_countlimit_set_count(new_root_countlimit, 1);
|
---|
1008 | ext4_directory_dx_entry_set_block(entries, new_iblock);
|
---|
1009 |
|
---|
1010 | ((ext4_directory_dx_root_t *)
|
---|
1011 | dx_blocks[0].block->data)->info.indirect_levels = 1;
|
---|
1012 |
|
---|
1013 | /* Add new entry to the path */
|
---|
1014 | dx_block = dx_blocks + 1;
|
---|
1015 | dx_block->position = dx_block->position - entries + new_entries;
|
---|
1016 | dx_block->entries = new_entries;
|
---|
1017 | dx_block->block = new_block;
|
---|
1018 | }
|
---|
1019 | }
|
---|
1020 |
|
---|
1021 | return EOK;
|
---|
1022 | }
|
---|
1023 |
|
---|
1024 | /** Add new entry to indexed directory
|
---|
1025 | *
|
---|
1026 | * @param parent Directory i-node
|
---|
1027 | * @param child I-node to be referenced from directory entry
|
---|
1028 | * @param name Name of new directory entry
|
---|
1029 | *
|
---|
1030 | * @return Error code
|
---|
1031 | *
|
---|
1032 | */
|
---|
1033 | int ext4_directory_dx_add_entry(ext4_inode_ref_t *parent,
|
---|
1034 | ext4_inode_ref_t *child, const char *name)
|
---|
1035 | {
|
---|
1036 | int rc2 = EOK;
|
---|
1037 |
|
---|
1038 | /* Get direct block 0 (index root) */
|
---|
1039 | uint32_t root_block_addr;
|
---|
1040 | int rc = ext4_filesystem_get_inode_data_block_index(parent, 0,
|
---|
1041 | &root_block_addr);
|
---|
1042 | if (rc != EOK)
|
---|
1043 | return rc;
|
---|
1044 |
|
---|
1045 | ext4_filesystem_t *fs = parent->fs;
|
---|
1046 |
|
---|
1047 | block_t *root_block;
|
---|
1048 | rc = block_get(&root_block, fs->device, root_block_addr,
|
---|
1049 | BLOCK_FLAGS_NONE);
|
---|
1050 | if (rc != EOK)
|
---|
1051 | return rc;
|
---|
1052 |
|
---|
1053 | /* Initialize hinfo structure (mainly compute hash) */
|
---|
1054 | uint32_t name_len = str_size(name);
|
---|
1055 | ext4_hash_info_t hinfo;
|
---|
1056 | rc = ext4_directory_hinfo_init(&hinfo, root_block, fs->superblock,
|
---|
1057 | name_len, name);
|
---|
1058 | if (rc != EOK) {
|
---|
1059 | block_put(root_block);
|
---|
1060 | return EXT4_ERR_BAD_DX_DIR;
|
---|
1061 | }
|
---|
1062 |
|
---|
1063 | /*
|
---|
1064 | * Hardcoded number 2 means maximum height of index
|
---|
1065 | * tree defined in Linux.
|
---|
1066 | */
|
---|
1067 | ext4_directory_dx_block_t dx_blocks[2];
|
---|
1068 | ext4_directory_dx_block_t *dx_block;
|
---|
1069 | ext4_directory_dx_block_t *dx_it;
|
---|
1070 |
|
---|
1071 | rc = ext4_directory_dx_get_leaf(&hinfo, parent, root_block,
|
---|
1072 | &dx_block, dx_blocks);
|
---|
1073 | if (rc != EOK) {
|
---|
1074 | rc = EXT4_ERR_BAD_DX_DIR;
|
---|
1075 | goto release_index;
|
---|
1076 | }
|
---|
1077 |
|
---|
1078 | /* Try to insert to existing data block */
|
---|
1079 | uint32_t leaf_block_idx =
|
---|
1080 | ext4_directory_dx_entry_get_block(dx_block->position);
|
---|
1081 | uint32_t leaf_block_addr;
|
---|
1082 | rc = ext4_filesystem_get_inode_data_block_index(parent, leaf_block_idx,
|
---|
1083 | &leaf_block_addr);
|
---|
1084 | if (rc != EOK)
|
---|
1085 | goto release_index;
|
---|
1086 |
|
---|
1087 | block_t *target_block;
|
---|
1088 | rc = block_get(&target_block, fs->device, leaf_block_addr,
|
---|
1089 | BLOCK_FLAGS_NONE);
|
---|
1090 | if (rc != EOK)
|
---|
1091 | goto release_index;
|
---|
1092 |
|
---|
1093 | /* Check if insert operation passed */
|
---|
1094 | rc = ext4_directory_try_insert_entry(fs->superblock, target_block, child,
|
---|
1095 | name, name_len);
|
---|
1096 | if (rc == EOK)
|
---|
1097 | goto release_target_index;
|
---|
1098 |
|
---|
1099 | /*
|
---|
1100 | * Check if there is needed to split index node
|
---|
1101 | * (and recursively also parent nodes)
|
---|
1102 | */
|
---|
1103 | rc = ext4_directory_dx_split_index(parent, dx_blocks, dx_block);
|
---|
1104 | if (rc != EOK)
|
---|
1105 | goto release_target_index;
|
---|
1106 |
|
---|
1107 | /* Split entries to two blocks (includes sorting by hash value) */
|
---|
1108 | block_t *new_block = NULL;
|
---|
1109 | rc = ext4_directory_dx_split_data(parent, &hinfo, target_block,
|
---|
1110 | dx_block, &new_block);
|
---|
1111 | if (rc != EOK) {
|
---|
1112 | rc2 = rc;
|
---|
1113 | goto release_target_index;
|
---|
1114 | }
|
---|
1115 |
|
---|
1116 | /* Where to save new entry */
|
---|
1117 | uint32_t new_block_hash =
|
---|
1118 | ext4_directory_dx_entry_get_hash(dx_block->position + 1);
|
---|
1119 | if (hinfo.hash >= new_block_hash)
|
---|
1120 | rc = ext4_directory_try_insert_entry(fs->superblock, new_block,
|
---|
1121 | child, name, name_len);
|
---|
1122 | else
|
---|
1123 | rc = ext4_directory_try_insert_entry(fs->superblock, target_block,
|
---|
1124 | child, name, name_len);
|
---|
1125 |
|
---|
1126 | /* Cleanup */
|
---|
1127 | rc = block_put(new_block);
|
---|
1128 | if (rc != EOK)
|
---|
1129 | return rc;
|
---|
1130 |
|
---|
1131 | /* Cleanup operations */
|
---|
1132 |
|
---|
1133 | release_target_index:
|
---|
1134 | rc2 = rc;
|
---|
1135 |
|
---|
1136 | rc = block_put(target_block);
|
---|
1137 | if (rc != EOK)
|
---|
1138 | return rc;
|
---|
1139 |
|
---|
1140 | release_index:
|
---|
1141 | if (rc != EOK)
|
---|
1142 | rc2 = rc;
|
---|
1143 |
|
---|
1144 | dx_it = dx_blocks;
|
---|
1145 |
|
---|
1146 | while (dx_it <= dx_block) {
|
---|
1147 | rc = block_put(dx_it->block);
|
---|
1148 | if (rc != EOK)
|
---|
1149 | return rc;
|
---|
1150 |
|
---|
1151 | dx_it++;
|
---|
1152 | }
|
---|
1153 |
|
---|
1154 | return rc2;
|
---|
1155 | }
|
---|
1156 |
|
---|
1157 | /**
|
---|
1158 | * @}
|
---|
1159 | */
|
---|