1 | /* |
2 | * Copyright (c) 2013 Grzegorz Kostka (kostka.grzegorz@gmail.com) |
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 lwext4 |
30 | * @{ |
31 | */ |
32 | /** |
33 | * @file ext4_dir_idx.c |
34 | * @brief Directory indexing procedures. |
35 | */ |
36 | |
37 | #include <ext4_config.h> |
38 | #include <ext4_types.h> |
39 | #include <ext4_misc.h> |
40 | #include <ext4_errno.h> |
41 | #include <ext4_debug.h> |
42 | |
43 | #include <ext4_trans.h> |
44 | #include <ext4_dir_idx.h> |
45 | #include <ext4_dir.h> |
46 | #include <ext4_blockdev.h> |
47 | #include <ext4_fs.h> |
48 | #include <ext4_super.h> |
49 | #include <ext4_inode.h> |
50 | #include <ext4_crc32.h> |
51 | #include <ext4_hash.h> |
52 | |
53 | #include <string.h> |
54 | #include <stdlib.h> |
55 | |
56 | /**@brief Get hash version used in directory index. |
57 | * @param ri Pointer to root info structure of index |
58 | * @return Hash algorithm version |
59 | */ |
60 | static inline uint8_t |
61 | ext4_dir_dx_rinfo_get_hash_version(struct ext4_dir_idx_rinfo *ri) |
62 | { |
63 | return ri->hash_version; |
64 | } |
65 | |
66 | /**@brief Set hash version, that will be used in directory index. |
67 | * @param ri Pointer to root info structure of index |
68 | * @param v Hash algorithm version |
69 | */ |
70 | static inline void |
71 | ext4_dir_dx_rinfo_set_hash_version(struct ext4_dir_idx_rinfo *ri, uint8_t v) |
72 | { |
73 | ri->hash_version = v; |
74 | } |
75 | |
76 | /**@brief Get length of root_info structure in bytes. |
77 | * @param ri Pointer to root info structure of index |
78 | * @return Length of the structure |
79 | */ |
80 | static inline uint8_t |
81 | ext4_dir_dx_rinfo_get_info_length(struct ext4_dir_idx_rinfo *ri) |
82 | { |
83 | return ri->info_length; |
84 | } |
85 | |
86 | /**@brief Set length of root_info structure in bytes. |
87 | * @param ri Pointer to root info structure of index |
88 | * @param len Length of the structure |
89 | */ |
90 | static inline void |
91 | ext4_dir_dx_root_info_set_info_length(struct ext4_dir_idx_rinfo *ri, |
92 | uint8_t len) |
93 | { |
94 | ri->info_length = len; |
95 | } |
96 | |
97 | /**@brief Get number of indirect levels of HTree. |
98 | * @param ri Pointer to root info structure of index |
99 | * @return Height of HTree (actually only 0 or 1) |
100 | */ |
101 | static inline uint8_t |
102 | ext4_dir_dx_rinfo_get_indirect_levels(struct ext4_dir_idx_rinfo *ri) |
103 | { |
104 | return ri->indirect_levels; |
105 | } |
106 | |
107 | /**@brief Set number of indirect levels of HTree. |
108 | * @param ri Pointer to root info structure of index |
109 | * @param l Height of HTree (actually only 0 or 1) |
110 | */ |
111 | static inline void |
112 | ext4_dir_dx_rinfo_set_indirect_levels(struct ext4_dir_idx_rinfo *ri, uint8_t l) |
113 | { |
114 | ri->indirect_levels = l; |
115 | } |
116 | |
117 | /**@brief Get maximum number of index node entries. |
118 | * @param climit Pointer to counlimit structure |
119 | * @return Maximum of entries in node |
120 | */ |
121 | static inline uint16_t |
122 | ext4_dir_dx_climit_get_limit(struct ext4_dir_idx_climit *climit) |
123 | { |
124 | return to_le16(climit->limit); |
125 | } |
126 | |
127 | /**@brief Set maximum number of index node entries. |
128 | * @param climit Pointer to counlimit structure |
129 | * @param limit Maximum of entries in node |
130 | */ |
131 | static inline void |
132 | ext4_dir_dx_climit_set_limit(struct ext4_dir_idx_climit *climit, uint16_t limit) |
133 | { |
134 | climit->limit = to_le16(limit); |
135 | } |
136 | |
137 | /**@brief Get current number of index node entries. |
138 | * @param climit Pointer to counlimit structure |
139 | * @return Number of entries in node |
140 | */ |
141 | static inline uint16_t |
142 | ext4_dir_dx_climit_get_count(struct ext4_dir_idx_climit *climit) |
143 | { |
144 | return to_le16(climit->count); |
145 | } |
146 | |
147 | /**@brief Set current number of index node entries. |
148 | * @param climit Pointer to counlimit structure |
149 | * @param count Number of entries in node |
150 | */ |
151 | static inline void |
152 | ext4_dir_dx_climit_set_count(struct ext4_dir_idx_climit *climit, uint16_t count) |
153 | { |
154 | climit->count = to_le16(count); |
155 | } |
156 | |
157 | /**@brief Get hash value of index entry. |
158 | * @param entry Pointer to index entry |
159 | * @return Hash value |
160 | */ |
161 | static inline uint32_t |
162 | ext4_dir_dx_entry_get_hash(struct ext4_dir_idx_entry *entry) |
163 | { |
164 | return to_le32(entry->hash); |
165 | } |
166 | |
167 | /**@brief Set hash value of index entry. |
168 | * @param entry Pointer to index entry |
169 | * @param hash Hash value |
170 | */ |
171 | static inline void |
172 | ext4_dir_dx_entry_set_hash(struct ext4_dir_idx_entry *entry, uint32_t hash) |
173 | { |
174 | entry->hash = to_le32(hash); |
175 | } |
176 | |
177 | /**@brief Get block address where child node is located. |
178 | * @param entry Pointer to index entry |
179 | * @return Block address of child node |
180 | */ |
181 | static inline uint32_t |
182 | ext4_dir_dx_entry_get_block(struct ext4_dir_idx_entry *entry) |
183 | { |
184 | return to_le32(entry->block); |
185 | } |
186 | |
187 | /**@brief Set block address where child node is located. |
188 | * @param entry Pointer to index entry |
189 | * @param block Block address of child node |
190 | */ |
191 | static inline void |
192 | ext4_dir_dx_entry_set_block(struct ext4_dir_idx_entry *entry, uint32_t block) |
193 | { |
194 | entry->block = to_le32(block); |
195 | } |
196 | |
197 | /**@brief Sort entry item.*/ |
198 | struct ext4_dx_sort_entry { |
199 | uint32_t hash; |
200 | uint32_t rec_len; |
201 | void *dentry; |
202 | }; |
203 | |
204 | static int ext4_dir_dx_hash_string(struct ext4_hash_info *hinfo, int len, |
205 | const char *name) |
206 | { |
207 | return ext2_htree_hash(name, len, hash_seed: hinfo->seed, hash_version: hinfo->hash_version, |
208 | hash_major: &hinfo->hash, hash_minor: &hinfo->minor_hash); |
209 | } |
210 | |
211 | #if CONFIG_META_CSUM_ENABLE |
212 | static uint32_t ext4_dir_dx_checksum(struct ext4_inode_ref *inode_ref, void *de, |
213 | int count_offset, int count, |
214 | struct ext4_dir_idx_tail *t) |
215 | { |
216 | uint32_t orig_cum, csum = 0; |
217 | struct ext4_sblock *sb = &inode_ref->fs->sb; |
218 | int sz; |
219 | |
220 | /* Compute the checksum only if the filesystem supports it */ |
221 | if (ext4_sb_feature_ro_com(s: sb, EXT4_FRO_COM_METADATA_CSUM)) { |
222 | uint32_t ino_index = to_le32(inode_ref->index); |
223 | uint32_t ino_gen; |
224 | ino_gen = to_le32(ext4_inode_get_generation(inode_ref->inode)); |
225 | |
226 | sz = count_offset + (count * sizeof(struct ext4_dir_idx_tail)); |
227 | orig_cum = t->checksum; |
228 | t->checksum = 0; |
229 | /* First calculate crc32 checksum against fs uuid */ |
230 | csum = ext4_crc32c(EXT4_CRC32_INIT, buf: sb->uuid, size: sizeof(sb->uuid)); |
231 | /* Then calculate crc32 checksum against inode number |
232 | * and inode generation */ |
233 | csum = ext4_crc32c(crc: csum, buf: &ino_index, size: sizeof(ino_index)); |
234 | csum = ext4_crc32c(crc: csum, buf: &ino_gen, size: sizeof(ino_gen)); |
235 | /* After that calculate crc32 checksum against all the dx_entry */ |
236 | csum = ext4_crc32c(crc: csum, buf: de, size: sz); |
237 | /* Finally calculate crc32 checksum for dx_tail */ |
238 | csum = ext4_crc32c(crc: csum, buf: t, size: sizeof(struct ext4_dir_idx_tail)); |
239 | t->checksum = orig_cum; |
240 | } |
241 | return csum; |
242 | } |
243 | |
244 | static struct ext4_dir_idx_climit * |
245 | ext4_dir_dx_get_climit(struct ext4_inode_ref *inode_ref, |
246 | struct ext4_dir_en *dirent, int *offset) |
247 | { |
248 | struct ext4_dir_en *dp; |
249 | struct ext4_dir_idx_root *root; |
250 | struct ext4_sblock *sb = &inode_ref->fs->sb; |
251 | uint32_t block_size = ext4_sb_get_block_size(s: sb); |
252 | uint16_t entry_len = ext4_dir_en_get_entry_len(de: dirent); |
253 | int count_offset; |
254 | |
255 | |
256 | if (entry_len == 12) { |
257 | root = (struct ext4_dir_idx_root *)dirent; |
258 | dp = (struct ext4_dir_en *)&root->dots[1]; |
259 | if (ext4_dir_en_get_entry_len(de: dp) != (block_size - 12)) |
260 | return NULL; |
261 | if (root->info.reserved_zero) |
262 | return NULL; |
263 | if (root->info.info_length != sizeof(struct ext4_dir_idx_rinfo)) |
264 | return NULL; |
265 | count_offset = 32; |
266 | } else if (entry_len == block_size) { |
267 | count_offset = 8; |
268 | } else { |
269 | return NULL; |
270 | } |
271 | |
272 | if (offset) |
273 | *offset = count_offset; |
274 | return (struct ext4_dir_idx_climit *)(((char *)dirent) + count_offset); |
275 | } |
276 | |
277 | /* |
278 | * BIG FAT NOTES: |
279 | * Currently we do not verify the checksum of HTree node. |
280 | */ |
281 | static bool ext4_dir_dx_csum_verify(struct ext4_inode_ref *inode_ref, |
282 | struct ext4_dir_en *de) |
283 | { |
284 | struct ext4_sblock *sb = &inode_ref->fs->sb; |
285 | uint32_t block_size = ext4_sb_get_block_size(s: sb); |
286 | int coff, limit, cnt; |
287 | |
288 | if (ext4_sb_feature_ro_com(s: sb, EXT4_FRO_COM_METADATA_CSUM)) { |
289 | struct ext4_dir_idx_climit *climit; |
290 | climit = ext4_dir_dx_get_climit(inode_ref, dirent: de, offset: &coff); |
291 | if (!climit) { |
292 | /* Directory seems corrupted. */ |
293 | return true; |
294 | } |
295 | struct ext4_dir_idx_tail *t; |
296 | limit = ext4_dir_dx_climit_get_limit(climit); |
297 | cnt = ext4_dir_dx_climit_get_count(climit); |
298 | if (coff + (limit * sizeof(struct ext4_dir_idx_entry)) > |
299 | (block_size - sizeof(struct ext4_dir_idx_tail))) { |
300 | /* There is no space to hold the checksum */ |
301 | return true; |
302 | } |
303 | t = (void *)(((struct ext4_dir_idx_entry *)climit) + limit); |
304 | |
305 | uint32_t c; |
306 | c = to_le32(ext4_dir_dx_checksum(inode_ref, de, coff, cnt, t)); |
307 | if (t->checksum != c) |
308 | return false; |
309 | } |
310 | return true; |
311 | } |
312 | |
313 | |
314 | static void ext4_dir_set_dx_csum(struct ext4_inode_ref *inode_ref, |
315 | struct ext4_dir_en *dirent) |
316 | { |
317 | int coff, limit, count; |
318 | struct ext4_sblock *sb = &inode_ref->fs->sb; |
319 | uint32_t block_size = ext4_sb_get_block_size(s: sb); |
320 | |
321 | if (ext4_sb_feature_ro_com(s: sb, EXT4_FRO_COM_METADATA_CSUM)) { |
322 | struct ext4_dir_idx_climit *climit; |
323 | climit = ext4_dir_dx_get_climit(inode_ref, dirent, offset: &coff); |
324 | if (!climit) { |
325 | /* Directory seems corrupted. */ |
326 | return; |
327 | } |
328 | struct ext4_dir_idx_tail *t; |
329 | limit = ext4_dir_dx_climit_get_limit(climit); |
330 | count = ext4_dir_dx_climit_get_count(climit); |
331 | if (coff + (limit * sizeof(struct ext4_dir_idx_entry)) > |
332 | (block_size - sizeof(struct ext4_dir_idx_tail))) { |
333 | /* There is no space to hold the checksum */ |
334 | return; |
335 | } |
336 | |
337 | t = (void *)(((struct ext4_dir_idx_entry *)climit) + limit); |
338 | t->checksum = to_le32(ext4_dir_dx_checksum(inode_ref, dirent, |
339 | coff, count, t)); |
340 | } |
341 | } |
342 | #else |
343 | #define ext4_dir_dx_csum_verify(...) true |
344 | #define ext4_dir_set_dx_csum(...) |
345 | #endif |
346 | |
347 | /****************************************************************************/ |
348 | |
349 | int ext4_dir_dx_init(struct ext4_inode_ref *dir, struct ext4_inode_ref *parent) |
350 | { |
351 | /* Load block 0, where will be index root located */ |
352 | ext4_fsblk_t fblock; |
353 | uint32_t iblock = 0; |
354 | bool need_append = |
355 | (ext4_inode_get_size(sb: &dir->fs->sb, inode: dir->inode) |
356 | < EXT4_DIR_DX_INIT_BCNT) |
357 | ? true : false; |
358 | struct ext4_sblock *sb = &dir->fs->sb; |
359 | uint32_t block_size = ext4_sb_get_block_size(s: &dir->fs->sb); |
360 | struct ext4_block block; |
361 | |
362 | int rc; |
363 | |
364 | if (!need_append) |
365 | rc = ext4_fs_init_inode_dblk_idx(inode_ref: dir, iblock, fblock: &fblock); |
366 | else |
367 | rc = ext4_fs_append_inode_dblk(inode_ref: dir, fblock: &fblock, iblock: &iblock); |
368 | |
369 | if (rc != EOK) |
370 | return rc; |
371 | |
372 | rc = ext4_trans_block_get_noread(bdev: dir->fs->bdev, b: &block, lba: fblock); |
373 | if (rc != EOK) |
374 | return rc; |
375 | |
376 | /* Initialize pointers to data structures */ |
377 | struct ext4_dir_idx_root *root = (void *)block.data; |
378 | struct ext4_dir_idx_rinfo *info = &(root->info); |
379 | |
380 | memset(dest: root, c: 0, size: sizeof(struct ext4_dir_idx_root)); |
381 | struct ext4_dir_en *de; |
382 | |
383 | /* Initialize dot entries */ |
384 | de = (struct ext4_dir_en *)root->dots; |
385 | ext4_dir_write_entry(sb, en: de, entry_len: 12, child: dir, name: "." , name_len: strlen(s: "." )); |
386 | |
387 | de = (struct ext4_dir_en *)(root->dots + 1); |
388 | uint16_t elen = block_size - 12; |
389 | ext4_dir_write_entry(sb, en: de, entry_len: elen, child: parent, name: ".." , name_len: strlen(s: ".." )); |
390 | |
391 | /* Initialize root info structure */ |
392 | uint8_t hash_version = ext4_get8(&dir->fs->sb, default_hash_version); |
393 | |
394 | ext4_dir_dx_rinfo_set_hash_version(ri: info, v: hash_version); |
395 | ext4_dir_dx_rinfo_set_indirect_levels(ri: info, l: 0); |
396 | ext4_dir_dx_root_info_set_info_length(ri: info, len: 8); |
397 | |
398 | /* Set limit and current number of entries */ |
399 | struct ext4_dir_idx_climit *climit; |
400 | climit = (struct ext4_dir_idx_climit *)&root->en; |
401 | |
402 | ext4_dir_dx_climit_set_count(climit, count: 1); |
403 | |
404 | uint32_t entry_space; |
405 | entry_space = block_size - 2 * sizeof(struct ext4_dir_idx_dot_en) - |
406 | sizeof(struct ext4_dir_idx_rinfo); |
407 | |
408 | if (ext4_sb_feature_ro_com(s: sb, EXT4_FRO_COM_METADATA_CSUM)) |
409 | entry_space -= sizeof(struct ext4_dir_idx_tail); |
410 | |
411 | uint16_t root_limit = entry_space / sizeof(struct ext4_dir_idx_entry); |
412 | ext4_dir_dx_climit_set_limit(climit, limit: root_limit); |
413 | |
414 | /* Append new block, where will be new entries inserted in the future */ |
415 | iblock++; |
416 | if (!need_append) |
417 | rc = ext4_fs_init_inode_dblk_idx(inode_ref: dir, iblock, fblock: &fblock); |
418 | else |
419 | rc = ext4_fs_append_inode_dblk(inode_ref: dir, fblock: &fblock, iblock: &iblock); |
420 | |
421 | if (rc != EOK) { |
422 | ext4_block_set(bdev: dir->fs->bdev, b: &block); |
423 | return rc; |
424 | } |
425 | |
426 | struct ext4_block new_block; |
427 | rc = ext4_trans_block_get_noread(bdev: dir->fs->bdev, b: &new_block, lba: fblock); |
428 | if (rc != EOK) { |
429 | ext4_block_set(bdev: dir->fs->bdev, b: &block); |
430 | return rc; |
431 | } |
432 | |
433 | /* Fill the whole block with empty entry */ |
434 | struct ext4_dir_en *be = (void *)new_block.data; |
435 | |
436 | if (ext4_sb_feature_ro_com(s: sb, EXT4_FRO_COM_METADATA_CSUM)) { |
437 | uint16_t len = block_size - sizeof(struct ext4_dir_entry_tail); |
438 | ext4_dir_en_set_entry_len(de: be, l: len); |
439 | ext4_dir_en_set_name_len(sb, de: be, len: 0); |
440 | ext4_dir_en_set_inode_type(sb, de: be, t: EXT4_DE_UNKNOWN); |
441 | ext4_dir_init_entry_tail(EXT4_DIRENT_TAIL(be, block_size)); |
442 | ext4_dir_set_csum(inode_ref: dir, dirent: be); |
443 | } else { |
444 | ext4_dir_en_set_entry_len(de: be, l: block_size); |
445 | } |
446 | |
447 | ext4_dir_en_set_inode(de: be, inode: 0); |
448 | |
449 | ext4_trans_set_block_dirty(buf: new_block.buf); |
450 | rc = ext4_block_set(bdev: dir->fs->bdev, b: &new_block); |
451 | if (rc != EOK) { |
452 | ext4_block_set(bdev: dir->fs->bdev, b: &block); |
453 | return rc; |
454 | } |
455 | |
456 | /* Connect new block to the only entry in index */ |
457 | struct ext4_dir_idx_entry *entry = root->en; |
458 | ext4_dir_dx_entry_set_block(entry, block: iblock); |
459 | |
460 | ext4_dir_set_dx_csum(inode_ref: dir, dirent: (struct ext4_dir_en *)block.data); |
461 | ext4_trans_set_block_dirty(buf: block.buf); |
462 | |
463 | return ext4_block_set(bdev: dir->fs->bdev, b: &block); |
464 | } |
465 | |
466 | /**@brief Initialize hash info structure necessary for index operations. |
467 | * @param hinfo Pointer to hinfo to be initialized |
468 | * @param root_block Root block (number 0) of index |
469 | * @param sb Pointer to superblock |
470 | * @param name_len Length of name to be computed hash value from |
471 | * @param name Name to be computed hash value from |
472 | * @return Standard error code |
473 | */ |
474 | static int ext4_dir_hinfo_init(struct ext4_hash_info *hinfo, |
475 | struct ext4_block *root_block, |
476 | struct ext4_sblock *sb, size_t name_len, |
477 | const char *name) |
478 | { |
479 | struct ext4_dir_idx_root *root; |
480 | |
481 | root = (struct ext4_dir_idx_root *)root_block->data; |
482 | if ((root->info.hash_version != EXT2_HTREE_LEGACY) && |
483 | (root->info.hash_version != EXT2_HTREE_HALF_MD4) && |
484 | (root->info.hash_version != EXT2_HTREE_TEA)) |
485 | return EXT4_ERR_BAD_DX_DIR; |
486 | |
487 | /* Check unused flags */ |
488 | if (root->info.unused_flags != 0) |
489 | return EXT4_ERR_BAD_DX_DIR; |
490 | |
491 | /* Check indirect levels */ |
492 | if (root->info.indirect_levels > 1) |
493 | return EXT4_ERR_BAD_DX_DIR; |
494 | |
495 | /* Check if node limit is correct */ |
496 | uint32_t block_size = ext4_sb_get_block_size(s: sb); |
497 | uint32_t entry_space = block_size; |
498 | entry_space -= 2 * sizeof(struct ext4_dir_idx_dot_en); |
499 | entry_space -= sizeof(struct ext4_dir_idx_rinfo); |
500 | if (ext4_sb_feature_ro_com(s: sb, EXT4_FRO_COM_METADATA_CSUM)) |
501 | entry_space -= sizeof(struct ext4_dir_idx_tail); |
502 | entry_space = entry_space / sizeof(struct ext4_dir_idx_entry); |
503 | |
504 | struct ext4_dir_idx_climit *climit = (void *)&root->en; |
505 | uint16_t limit = ext4_dir_dx_climit_get_limit(climit); |
506 | if (limit != entry_space) |
507 | return EXT4_ERR_BAD_DX_DIR; |
508 | |
509 | /* Check hash version and modify if necessary */ |
510 | hinfo->hash_version = ext4_dir_dx_rinfo_get_hash_version(ri: &root->info); |
511 | if ((hinfo->hash_version <= EXT2_HTREE_TEA) && |
512 | (ext4_sb_check_flag(s: sb, EXT4_SUPERBLOCK_FLAGS_UNSIGNED_HASH))) { |
513 | /* Use unsigned hash */ |
514 | hinfo->hash_version += 3; |
515 | } |
516 | |
517 | /* Load hash seed from superblock */ |
518 | hinfo->seed = ext4_get8(sb, hash_seed); |
519 | |
520 | /* Compute hash value of name */ |
521 | if (name) |
522 | return ext4_dir_dx_hash_string(hinfo, len: name_len, name); |
523 | |
524 | return EOK; |
525 | } |
526 | |
527 | /**@brief Walk through index tree and load leaf with corresponding hash value. |
528 | * @param hinfo Initialized hash info structure |
529 | * @param inode_ref Current i-node |
530 | * @param root_block Root block (iblock 0), where is root node located |
531 | * @param dx_block Pointer to leaf node in dx_blocks array |
532 | * @param dx_blocks Array with the whole path from root to leaf |
533 | * @return Standard error code |
534 | */ |
535 | static int ext4_dir_dx_get_leaf(struct ext4_hash_info *hinfo, |
536 | struct ext4_inode_ref *inode_ref, |
537 | struct ext4_block *root_block, |
538 | struct ext4_dir_idx_block **dx_block, |
539 | struct ext4_dir_idx_block *dx_blocks) |
540 | { |
541 | struct ext4_dir_idx_root *root; |
542 | struct ext4_dir_idx_entry *entries; |
543 | struct ext4_dir_idx_entry *p; |
544 | struct ext4_dir_idx_entry *q; |
545 | struct ext4_dir_idx_entry *m; |
546 | struct ext4_dir_idx_entry *at; |
547 | ext4_fsblk_t fblk; |
548 | uint32_t block_size; |
549 | uint16_t limit; |
550 | uint16_t entry_space; |
551 | uint8_t ind_level; |
552 | int r; |
553 | |
554 | struct ext4_dir_idx_block *tmp_dx_blk = dx_blocks; |
555 | struct ext4_block *tmp_blk = root_block; |
556 | struct ext4_sblock *sb = &inode_ref->fs->sb; |
557 | |
558 | block_size = ext4_sb_get_block_size(s: sb); |
559 | root = (struct ext4_dir_idx_root *)root_block->data; |
560 | entries = (struct ext4_dir_idx_entry *)&root->en; |
561 | limit = ext4_dir_dx_climit_get_limit(climit: (void *)entries); |
562 | ind_level = ext4_dir_dx_rinfo_get_indirect_levels(ri: &root->info); |
563 | |
564 | /* Walk through the index tree */ |
565 | while (true) { |
566 | uint16_t cnt = ext4_dir_dx_climit_get_count(climit: (void *)entries); |
567 | if ((cnt == 0) || (cnt > limit)) |
568 | return EXT4_ERR_BAD_DX_DIR; |
569 | |
570 | /* Do binary search in every node */ |
571 | p = entries + 1; |
572 | q = entries + cnt - 1; |
573 | |
574 | while (p <= q) { |
575 | m = p + (q - p) / 2; |
576 | if (ext4_dir_dx_entry_get_hash(entry: m) > hinfo->hash) |
577 | q = m - 1; |
578 | else |
579 | p = m + 1; |
580 | } |
581 | |
582 | at = p - 1; |
583 | |
584 | /* Write results */ |
585 | memcpy(dest: &tmp_dx_blk->b, src: tmp_blk, size: sizeof(struct ext4_block)); |
586 | tmp_dx_blk->entries = entries; |
587 | tmp_dx_blk->position = at; |
588 | |
589 | /* Is algorithm in the leaf? */ |
590 | if (ind_level == 0) { |
591 | *dx_block = tmp_dx_blk; |
592 | return EOK; |
593 | } |
594 | |
595 | /* Goto child node */ |
596 | uint32_t n_blk = ext4_dir_dx_entry_get_block(entry: at); |
597 | |
598 | ind_level--; |
599 | |
600 | r = ext4_fs_get_inode_dblk_idx(inode_ref, iblock: n_blk, fblock: &fblk, support_unwritten: false); |
601 | if (r != EOK) |
602 | return r; |
603 | |
604 | r = ext4_trans_block_get(bdev: inode_ref->fs->bdev, b: tmp_blk, lba: fblk); |
605 | if (r != EOK) |
606 | return r; |
607 | |
608 | entries = ((struct ext4_dir_idx_node *)tmp_blk->data)->entries; |
609 | limit = ext4_dir_dx_climit_get_limit(climit: (void *)entries); |
610 | |
611 | entry_space = block_size - sizeof(struct ext4_fake_dir_entry); |
612 | if (ext4_sb_feature_ro_com(s: sb, EXT4_FRO_COM_METADATA_CSUM)) |
613 | entry_space -= sizeof(struct ext4_dir_idx_tail); |
614 | |
615 | entry_space = entry_space / sizeof(struct ext4_dir_idx_entry); |
616 | |
617 | if (limit != entry_space) { |
618 | ext4_block_set(bdev: inode_ref->fs->bdev, b: tmp_blk); |
619 | return EXT4_ERR_BAD_DX_DIR; |
620 | } |
621 | |
622 | if (!ext4_dir_dx_csum_verify(inode_ref, de: (void *)tmp_blk->data)) { |
623 | ext4_dbg(DEBUG_DIR_IDX, |
624 | DBG_WARN "HTree checksum failed." |
625 | "Inode: %" PRIu32", " |
626 | "Block: %" PRIu32"\n" , |
627 | inode_ref->index, |
628 | n_blk); |
629 | } |
630 | |
631 | ++tmp_dx_blk; |
632 | } |
633 | |
634 | /* Unreachable */ |
635 | return EOK; |
636 | } |
637 | |
638 | /**@brief Check if the the next block would be checked during entry search. |
639 | * @param inode_ref Directory i-node |
640 | * @param hash Hash value to check |
641 | * @param dx_block Current block |
642 | * @param dx_blocks Array with path from root to leaf node |
643 | * @return Standard Error code |
644 | */ |
645 | static int ext4_dir_dx_next_block(struct ext4_inode_ref *inode_ref, |
646 | uint32_t hash, |
647 | struct ext4_dir_idx_block *dx_block, |
648 | struct ext4_dir_idx_block *dx_blocks) |
649 | { |
650 | int r; |
651 | uint32_t num_handles = 0; |
652 | ext4_fsblk_t blk_adr; |
653 | struct ext4_dir_idx_block *p = dx_block; |
654 | |
655 | /* Try to find data block with next bunch of entries */ |
656 | while (true) { |
657 | uint16_t cnt = ext4_dir_dx_climit_get_count(climit: (void *)p->entries); |
658 | |
659 | p->position++; |
660 | if (p->position < p->entries + cnt) |
661 | break; |
662 | |
663 | if (p == dx_blocks) |
664 | return EOK; |
665 | |
666 | num_handles++; |
667 | p--; |
668 | } |
669 | |
670 | /* Check hash collision (if not occurred - no next block cannot be |
671 | * used)*/ |
672 | uint32_t current_hash = ext4_dir_dx_entry_get_hash(entry: p->position); |
673 | if ((hash & 1) == 0) { |
674 | if ((current_hash & ~1) != hash) |
675 | return 0; |
676 | } |
677 | |
678 | /* Fill new path */ |
679 | while (num_handles--) { |
680 | uint32_t blk = ext4_dir_dx_entry_get_block(entry: p->position); |
681 | r = ext4_fs_get_inode_dblk_idx(inode_ref, iblock: blk, fblock: &blk_adr, support_unwritten: false); |
682 | if (r != EOK) |
683 | return r; |
684 | |
685 | struct ext4_block b; |
686 | r = ext4_trans_block_get(bdev: inode_ref->fs->bdev, b: &b, lba: blk_adr); |
687 | if (r != EOK) |
688 | return r; |
689 | |
690 | if (!ext4_dir_dx_csum_verify(inode_ref, de: (void *)b.data)) { |
691 | ext4_dbg(DEBUG_DIR_IDX, |
692 | DBG_WARN "HTree checksum failed." |
693 | "Inode: %" PRIu32", " |
694 | "Block: %" PRIu32"\n" , |
695 | inode_ref->index, |
696 | blk); |
697 | } |
698 | |
699 | p++; |
700 | |
701 | /* Don't forget to put old block (prevent memory leak) */ |
702 | r = ext4_block_set(bdev: inode_ref->fs->bdev, b: &p->b); |
703 | if (r != EOK) |
704 | return r; |
705 | |
706 | memcpy(dest: &p->b, src: &b, size: sizeof(b)); |
707 | p->entries = ((struct ext4_dir_idx_node *)b.data)->entries; |
708 | p->position = p->entries; |
709 | } |
710 | |
711 | return ENOENT; |
712 | } |
713 | |
714 | int ext4_dir_dx_find_entry(struct ext4_dir_search_result *result, |
715 | struct ext4_inode_ref *inode_ref, size_t name_len, |
716 | const char *name) |
717 | { |
718 | /* Load direct block 0 (index root) */ |
719 | ext4_fsblk_t root_block_addr; |
720 | int rc2; |
721 | int rc; |
722 | rc = ext4_fs_get_inode_dblk_idx(inode_ref, iblock: 0, fblock: &root_block_addr, support_unwritten: false); |
723 | if (rc != EOK) |
724 | return rc; |
725 | |
726 | struct ext4_fs *fs = inode_ref->fs; |
727 | |
728 | struct ext4_block root_block; |
729 | rc = ext4_trans_block_get(bdev: fs->bdev, b: &root_block, lba: root_block_addr); |
730 | if (rc != EOK) |
731 | return rc; |
732 | |
733 | if (!ext4_dir_dx_csum_verify(inode_ref, de: (void *)root_block.data)) { |
734 | ext4_dbg(DEBUG_DIR_IDX, |
735 | DBG_WARN "HTree root checksum failed." |
736 | "Inode: %" PRIu32", " |
737 | "Block: %" PRIu32"\n" , |
738 | inode_ref->index, |
739 | (uint32_t)0); |
740 | } |
741 | |
742 | /* Initialize hash info (compute hash value) */ |
743 | struct ext4_hash_info hinfo; |
744 | rc = ext4_dir_hinfo_init(hinfo: &hinfo, root_block: &root_block, sb: &fs->sb, name_len, name); |
745 | if (rc != EOK) { |
746 | ext4_block_set(bdev: fs->bdev, b: &root_block); |
747 | return EXT4_ERR_BAD_DX_DIR; |
748 | } |
749 | |
750 | /* |
751 | * Hardcoded number 2 means maximum height of index tree, |
752 | * specified in the Linux driver. |
753 | */ |
754 | struct ext4_dir_idx_block dx_blocks[2]; |
755 | struct ext4_dir_idx_block *dx_block; |
756 | struct ext4_dir_idx_block *tmp; |
757 | |
758 | rc = ext4_dir_dx_get_leaf(hinfo: &hinfo, inode_ref, root_block: &root_block, dx_block: &dx_block, |
759 | dx_blocks); |
760 | if (rc != EOK) { |
761 | ext4_block_set(bdev: fs->bdev, b: &root_block); |
762 | return EXT4_ERR_BAD_DX_DIR; |
763 | } |
764 | |
765 | do { |
766 | /* Load leaf block */ |
767 | uint32_t leaf_blk_idx; |
768 | ext4_fsblk_t leaf_block_addr; |
769 | struct ext4_block b; |
770 | |
771 | leaf_blk_idx = ext4_dir_dx_entry_get_block(entry: dx_block->position); |
772 | rc = ext4_fs_get_inode_dblk_idx(inode_ref, iblock: leaf_blk_idx, |
773 | fblock: &leaf_block_addr, support_unwritten: false); |
774 | if (rc != EOK) |
775 | goto cleanup; |
776 | |
777 | rc = ext4_trans_block_get(bdev: fs->bdev, b: &b, lba: leaf_block_addr); |
778 | if (rc != EOK) |
779 | goto cleanup; |
780 | |
781 | if (!ext4_dir_csum_verify(inode_ref, dirent: (void *)b.data)) { |
782 | ext4_dbg(DEBUG_DIR_IDX, |
783 | DBG_WARN "HTree leaf block checksum failed." |
784 | "Inode: %" PRIu32", " |
785 | "Block: %" PRIu32"\n" , |
786 | inode_ref->index, |
787 | leaf_blk_idx); |
788 | } |
789 | |
790 | /* Linear search inside block */ |
791 | struct ext4_dir_en *de; |
792 | rc = ext4_dir_find_in_block(block: &b, sb: &fs->sb, name_len, name, res_entry: &de); |
793 | |
794 | /* Found => return it */ |
795 | if (rc == EOK) { |
796 | result->block = b; |
797 | result->dentry = de; |
798 | goto cleanup; |
799 | } |
800 | |
801 | /* Not found, leave untouched */ |
802 | rc2 = ext4_block_set(bdev: fs->bdev, b: &b); |
803 | if (rc2 != EOK) |
804 | goto cleanup; |
805 | |
806 | if (rc != ENOENT) |
807 | goto cleanup; |
808 | |
809 | /* check if the next block could be checked */ |
810 | rc = ext4_dir_dx_next_block(inode_ref, hash: hinfo.hash, dx_block, |
811 | dx_blocks: &dx_blocks[0]); |
812 | if (rc < 0) |
813 | goto cleanup; |
814 | } while (rc == ENOENT); |
815 | |
816 | /* Entry not found */ |
817 | rc = ENOENT; |
818 | |
819 | cleanup: |
820 | /* The whole path must be released (preventing memory leak) */ |
821 | tmp = dx_blocks; |
822 | |
823 | while (tmp <= dx_block) { |
824 | rc2 = ext4_block_set(bdev: fs->bdev, b: &tmp->b); |
825 | if (rc == EOK && rc2 != EOK) |
826 | rc = rc2; |
827 | ++tmp; |
828 | } |
829 | |
830 | return rc; |
831 | } |
832 | |
833 | /**@brief Compare function used to pass in quicksort implementation. |
834 | * It can compare two entries by hash value. |
835 | * @param arg1 First entry |
836 | * @param arg2 Second entry |
837 | * |
838 | * @return Classic compare result |
839 | * (0: equal, -1: arg1 < arg2, 1: arg1 > arg2) |
840 | */ |
841 | static int ext4_dir_dx_entry_comparator(const void *arg1, const void *arg2) |
842 | { |
843 | struct ext4_dx_sort_entry *entry1 = (void *)arg1; |
844 | struct ext4_dx_sort_entry *entry2 = (void *)arg2; |
845 | |
846 | if (entry1->hash == entry2->hash) |
847 | return 0; |
848 | |
849 | if (entry1->hash < entry2->hash) |
850 | return -1; |
851 | else |
852 | return 1; |
853 | } |
854 | |
855 | /**@brief Insert new index entry to block. |
856 | * Note that space for new entry must be checked by caller. |
857 | * @param inode_ref Directory i-node |
858 | * @param index_block Block where to insert new entry |
859 | * @param hash Hash value covered by child node |
860 | * @param iblock Logical number of child block |
861 | * |
862 | */ |
863 | static void |
864 | ext4_dir_dx_insert_entry(struct ext4_inode_ref *inode_ref __unused, |
865 | struct ext4_dir_idx_block *index_block, |
866 | uint32_t hash, uint32_t iblock) |
867 | { |
868 | struct ext4_dir_idx_entry *old_index_entry = index_block->position; |
869 | struct ext4_dir_idx_entry *new_index_entry = old_index_entry + 1; |
870 | struct ext4_dir_idx_climit *climit = (void *)index_block->entries; |
871 | struct ext4_dir_idx_entry *start_index = index_block->entries; |
872 | uint32_t count = ext4_dir_dx_climit_get_count(climit); |
873 | |
874 | size_t bytes; |
875 | bytes = (uint8_t *)(start_index + count) - (uint8_t *)(new_index_entry); |
876 | |
877 | memmove(dest: new_index_entry + 1, src: new_index_entry, size: bytes); |
878 | |
879 | ext4_dir_dx_entry_set_block(entry: new_index_entry, block: iblock); |
880 | ext4_dir_dx_entry_set_hash(entry: new_index_entry, hash); |
881 | ext4_dir_dx_climit_set_count(climit, count: count + 1); |
882 | ext4_dir_set_dx_csum(inode_ref, dirent: (void *)index_block->b.data); |
883 | ext4_trans_set_block_dirty(buf: index_block->b.buf); |
884 | } |
885 | |
886 | /**@brief Split directory entries to two parts preventing node overflow. |
887 | * @param inode_ref Directory i-node |
888 | * @param hinfo Hash info |
889 | * @param old_data_block Block with data to be split |
890 | * @param index_block Block where index entries are located |
891 | * @param new_data_block Output value for newly allocated data block |
892 | */ |
893 | static int ext4_dir_dx_split_data(struct ext4_inode_ref *inode_ref, |
894 | struct ext4_hash_info *hinfo, |
895 | struct ext4_block *old_data_block, |
896 | struct ext4_dir_idx_block *index_block, |
897 | struct ext4_block *new_data_block) |
898 | { |
899 | int rc = EOK; |
900 | struct ext4_sblock *sb = &inode_ref->fs->sb; |
901 | uint32_t block_size = ext4_sb_get_block_size(s: &inode_ref->fs->sb); |
902 | |
903 | /* Allocate buffer for directory entries */ |
904 | uint8_t *entry_buffer = ext4_malloc(size: block_size); |
905 | if (entry_buffer == NULL) |
906 | return ENOMEM; |
907 | |
908 | /* dot entry has the smallest size available */ |
909 | uint32_t max_ecnt = block_size / sizeof(struct ext4_dir_idx_dot_en); |
910 | |
911 | /* Allocate sort entry */ |
912 | struct ext4_dx_sort_entry *sort; |
913 | |
914 | sort = ext4_malloc(size: max_ecnt * sizeof(struct ext4_dx_sort_entry)); |
915 | if (sort == NULL) { |
916 | ext4_free(pointer: entry_buffer); |
917 | return ENOMEM; |
918 | } |
919 | |
920 | uint32_t idx = 0; |
921 | uint32_t real_size = 0; |
922 | |
923 | /* Initialize hinfo */ |
924 | struct ext4_hash_info hinfo_tmp; |
925 | memcpy(dest: &hinfo_tmp, src: hinfo, size: sizeof(struct ext4_hash_info)); |
926 | |
927 | /* Load all valid entries to the buffer */ |
928 | struct ext4_dir_en *de = (void *)old_data_block->data; |
929 | uint8_t *entry_buffer_ptr = entry_buffer; |
930 | while ((void *)de < (void *)(old_data_block->data + block_size)) { |
931 | /* Read only valid entries */ |
932 | if (ext4_dir_en_get_inode(de) && de->name_len) { |
933 | uint16_t len = ext4_dir_en_get_name_len(sb, de); |
934 | rc = ext4_dir_dx_hash_string(hinfo: &hinfo_tmp, len, |
935 | name: (char *)de->name); |
936 | if (rc != EOK) { |
937 | ext4_free(pointer: sort); |
938 | ext4_free(pointer: entry_buffer); |
939 | return rc; |
940 | } |
941 | |
942 | uint32_t rec_len = 8 + len; |
943 | if ((rec_len % 4) != 0) |
944 | rec_len += 4 - (rec_len % 4); |
945 | |
946 | memcpy(dest: entry_buffer_ptr, src: de, size: rec_len); |
947 | |
948 | sort[idx].dentry = entry_buffer_ptr; |
949 | sort[idx].rec_len = rec_len; |
950 | sort[idx].hash = hinfo_tmp.hash; |
951 | |
952 | entry_buffer_ptr += rec_len; |
953 | real_size += rec_len; |
954 | idx++; |
955 | } |
956 | |
957 | size_t elen = ext4_dir_en_get_entry_len(de); |
958 | de = (void *)((uint8_t *)de + elen); |
959 | } |
960 | |
961 | qsort(base: sort, count: idx, size: sizeof(struct ext4_dx_sort_entry), |
962 | compare: ext4_dir_dx_entry_comparator); |
963 | |
964 | /* Allocate new block for store the second part of entries */ |
965 | ext4_fsblk_t new_fblock; |
966 | uint32_t new_iblock; |
967 | rc = ext4_fs_append_inode_dblk(inode_ref, fblock: &new_fblock, iblock: &new_iblock); |
968 | if (rc != EOK) { |
969 | ext4_free(pointer: sort); |
970 | ext4_free(pointer: entry_buffer); |
971 | return rc; |
972 | } |
973 | |
974 | /* Load new block */ |
975 | struct ext4_block new_data_block_tmp; |
976 | rc = ext4_trans_block_get_noread(bdev: inode_ref->fs->bdev, b: &new_data_block_tmp, |
977 | lba: new_fblock); |
978 | if (rc != EOK) { |
979 | ext4_free(pointer: sort); |
980 | ext4_free(pointer: entry_buffer); |
981 | return rc; |
982 | } |
983 | |
984 | /* |
985 | * Distribute entries to two blocks (by size) |
986 | * - compute the half |
987 | */ |
988 | uint32_t new_hash = 0; |
989 | uint32_t current_size = 0; |
990 | uint32_t mid = 0; |
991 | uint32_t i; |
992 | for (i = 0; i < idx; ++i) { |
993 | if ((current_size + sort[i].rec_len) > (block_size / 2)) { |
994 | new_hash = sort[i].hash; |
995 | mid = i; |
996 | break; |
997 | } |
998 | |
999 | current_size += sort[i].rec_len; |
1000 | } |
1001 | |
1002 | /* Check hash collision */ |
1003 | uint32_t continued = 0; |
1004 | if (new_hash == sort[mid - 1].hash) |
1005 | continued = 1; |
1006 | |
1007 | uint32_t off = 0; |
1008 | void *ptr; |
1009 | if (ext4_sb_feature_ro_com(s: sb, EXT4_FRO_COM_METADATA_CSUM)) |
1010 | block_size -= sizeof(struct ext4_dir_entry_tail); |
1011 | |
1012 | /* First part - to the old block */ |
1013 | for (i = 0; i < mid; ++i) { |
1014 | ptr = old_data_block->data + off; |
1015 | memcpy(dest: ptr, src: sort[i].dentry, size: sort[i].rec_len); |
1016 | |
1017 | struct ext4_dir_en *t = ptr; |
1018 | if (i < (mid - 1)) |
1019 | ext4_dir_en_set_entry_len(de: t, l: sort[i].rec_len); |
1020 | else |
1021 | ext4_dir_en_set_entry_len(de: t, l: block_size - off); |
1022 | |
1023 | off += sort[i].rec_len; |
1024 | } |
1025 | |
1026 | /* Second part - to the new block */ |
1027 | off = 0; |
1028 | for (i = mid; i < idx; ++i) { |
1029 | ptr = new_data_block_tmp.data + off; |
1030 | memcpy(dest: ptr, src: sort[i].dentry, size: sort[i].rec_len); |
1031 | |
1032 | struct ext4_dir_en *t = ptr; |
1033 | if (i < (idx - 1)) |
1034 | ext4_dir_en_set_entry_len(de: t, l: sort[i].rec_len); |
1035 | else |
1036 | ext4_dir_en_set_entry_len(de: t, l: block_size - off); |
1037 | |
1038 | off += sort[i].rec_len; |
1039 | } |
1040 | |
1041 | block_size = ext4_sb_get_block_size(s: &inode_ref->fs->sb); |
1042 | |
1043 | /* Do some steps to finish operation */ |
1044 | sb = &inode_ref->fs->sb; |
1045 | if (ext4_sb_feature_ro_com(s: sb, EXT4_FRO_COM_METADATA_CSUM)) { |
1046 | struct ext4_dir_entry_tail *t; |
1047 | |
1048 | t = EXT4_DIRENT_TAIL(old_data_block->data, block_size); |
1049 | ext4_dir_init_entry_tail(t); |
1050 | t = EXT4_DIRENT_TAIL(new_data_block_tmp.data, block_size); |
1051 | ext4_dir_init_entry_tail(t); |
1052 | } |
1053 | ext4_dir_set_csum(inode_ref, dirent: (void *)old_data_block->data); |
1054 | ext4_dir_set_csum(inode_ref, dirent: (void *)new_data_block_tmp.data); |
1055 | ext4_trans_set_block_dirty(buf: old_data_block->buf); |
1056 | ext4_trans_set_block_dirty(buf: new_data_block_tmp.buf); |
1057 | |
1058 | ext4_free(pointer: sort); |
1059 | ext4_free(pointer: entry_buffer); |
1060 | |
1061 | ext4_dir_dx_insert_entry(inode_ref, index_block, hash: new_hash + continued, |
1062 | iblock: new_iblock); |
1063 | |
1064 | *new_data_block = new_data_block_tmp; |
1065 | return EOK; |
1066 | } |
1067 | |
1068 | /**@brief Split index node and maybe some parent nodes in the tree hierarchy. |
1069 | * @param ino_ref Directory i-node |
1070 | * @param dx_blks Array with path from root to leaf node |
1071 | * @param dxb Leaf block to be split if needed |
1072 | * @return Error code |
1073 | */ |
1074 | static int |
1075 | ext4_dir_dx_split_index(struct ext4_inode_ref *ino_ref, |
1076 | struct ext4_dir_idx_block *dx_blks, |
1077 | struct ext4_dir_idx_block *dxb, |
1078 | struct ext4_dir_idx_block **new_dx_block) |
1079 | { |
1080 | struct ext4_sblock *sb = &ino_ref->fs->sb; |
1081 | struct ext4_dir_idx_entry *e; |
1082 | int r; |
1083 | |
1084 | uint32_t block_size = ext4_sb_get_block_size(s: &ino_ref->fs->sb); |
1085 | uint32_t entry_space = block_size - sizeof(struct ext4_fake_dir_entry); |
1086 | uint32_t node_limit = entry_space / sizeof(struct ext4_dir_idx_entry); |
1087 | |
1088 | bool meta_csum = ext4_sb_feature_ro_com(s: sb, EXT4_FRO_COM_METADATA_CSUM); |
1089 | |
1090 | if (dxb == dx_blks) |
1091 | e = ((struct ext4_dir_idx_root *)dxb->b.data)->en; |
1092 | else |
1093 | e = ((struct ext4_dir_idx_node *)dxb->b.data)->entries; |
1094 | |
1095 | struct ext4_dir_idx_climit *climit = (struct ext4_dir_idx_climit *)e; |
1096 | |
1097 | uint16_t leaf_limit = ext4_dir_dx_climit_get_limit(climit); |
1098 | uint16_t leaf_count = ext4_dir_dx_climit_get_count(climit); |
1099 | |
1100 | /* Check if is necessary to split index block */ |
1101 | if (leaf_limit == leaf_count) { |
1102 | struct ext4_dir_idx_entry *ren; |
1103 | ptrdiff_t levels = dxb - dx_blks; |
1104 | |
1105 | ren = ((struct ext4_dir_idx_root *)dx_blks[0].b.data)->en; |
1106 | struct ext4_dir_idx_climit *rclimit = (void *)ren; |
1107 | uint16_t root_limit = ext4_dir_dx_climit_get_limit(climit: rclimit); |
1108 | uint16_t root_count = ext4_dir_dx_climit_get_count(climit: rclimit); |
1109 | |
1110 | |
1111 | /* Linux limitation */ |
1112 | if ((levels > 0) && (root_limit == root_count)) |
1113 | return ENOSPC; |
1114 | |
1115 | /* Add new block to directory */ |
1116 | ext4_fsblk_t new_fblk; |
1117 | uint32_t new_iblk; |
1118 | r = ext4_fs_append_inode_dblk(inode_ref: ino_ref, fblock: &new_fblk, iblock: &new_iblk); |
1119 | if (r != EOK) |
1120 | return r; |
1121 | |
1122 | /* load new block */ |
1123 | struct ext4_block b; |
1124 | r = ext4_trans_block_get_noread(bdev: ino_ref->fs->bdev, b: &b, lba: new_fblk); |
1125 | if (r != EOK) |
1126 | return r; |
1127 | |
1128 | struct ext4_dir_idx_node *new_node = (void *)b.data; |
1129 | struct ext4_dir_idx_entry *new_en = new_node->entries; |
1130 | |
1131 | memset(dest: &new_node->fake, c: 0, size: sizeof(struct ext4_fake_dir_entry)); |
1132 | new_node->fake.entry_length = block_size; |
1133 | |
1134 | /* Split leaf node */ |
1135 | if (levels > 0) { |
1136 | uint32_t count_left = leaf_count / 2; |
1137 | uint32_t count_right = leaf_count - count_left; |
1138 | uint32_t hash_right; |
1139 | size_t sz; |
1140 | |
1141 | struct ext4_dir_idx_climit *left_climit; |
1142 | struct ext4_dir_idx_climit *right_climit; |
1143 | |
1144 | hash_right = ext4_dir_dx_entry_get_hash(entry: e + count_left); |
1145 | /* Copy data to new node */ |
1146 | sz = count_right * sizeof(struct ext4_dir_idx_entry); |
1147 | memcpy(dest: new_en, src: e + count_left, size: sz); |
1148 | |
1149 | /* Initialize new node */ |
1150 | left_climit = (struct ext4_dir_idx_climit *)e; |
1151 | right_climit = (struct ext4_dir_idx_climit *)new_en; |
1152 | |
1153 | ext4_dir_dx_climit_set_count(climit: left_climit, count: count_left); |
1154 | ext4_dir_dx_climit_set_count(climit: right_climit, count: count_right); |
1155 | |
1156 | if (meta_csum) |
1157 | entry_space -= sizeof(struct ext4_dir_idx_tail); |
1158 | |
1159 | ext4_dir_dx_climit_set_limit(climit: right_climit, limit: node_limit); |
1160 | |
1161 | /* Which index block is target for new entry */ |
1162 | uint32_t position_index = |
1163 | (dxb->position - dxb->entries); |
1164 | if (position_index >= count_left) { |
1165 | ext4_dir_set_dx_csum( |
1166 | inode_ref: ino_ref, |
1167 | dirent: (struct ext4_dir_en *) |
1168 | dxb->b.data); |
1169 | ext4_trans_set_block_dirty(buf: dxb->b.buf); |
1170 | |
1171 | struct ext4_block block_tmp = dxb->b; |
1172 | |
1173 | dxb->b = b; |
1174 | |
1175 | dxb->position = |
1176 | new_en + position_index - count_left; |
1177 | dxb->entries = new_en; |
1178 | |
1179 | b = block_tmp; |
1180 | } |
1181 | |
1182 | /* Finally insert new entry */ |
1183 | ext4_dir_dx_insert_entry(inode_ref: ino_ref, index_block: dx_blks, hash: hash_right, |
1184 | iblock: new_iblk); |
1185 | ext4_dir_set_dx_csum(inode_ref: ino_ref, dirent: (void*)dx_blks[0].b.data); |
1186 | ext4_dir_set_dx_csum(inode_ref: ino_ref, dirent: (void*)dx_blks[1].b.data); |
1187 | ext4_trans_set_block_dirty(buf: dx_blks[0].b.buf); |
1188 | ext4_trans_set_block_dirty(buf: dx_blks[1].b.buf); |
1189 | |
1190 | ext4_dir_set_dx_csum(inode_ref: ino_ref, dirent: (void *)b.data); |
1191 | ext4_trans_set_block_dirty(buf: b.buf); |
1192 | return ext4_block_set(bdev: ino_ref->fs->bdev, b: &b); |
1193 | } else { |
1194 | size_t sz; |
1195 | /* Copy data from root to child block */ |
1196 | sz = leaf_count * sizeof(struct ext4_dir_idx_entry); |
1197 | memcpy(dest: new_en, src: e, size: sz); |
1198 | |
1199 | struct ext4_dir_idx_climit *new_climit = (void*)new_en; |
1200 | if (meta_csum) |
1201 | entry_space -= sizeof(struct ext4_dir_idx_tail); |
1202 | |
1203 | ext4_dir_dx_climit_set_limit(climit: new_climit, limit: node_limit); |
1204 | |
1205 | /* Set values in root node */ |
1206 | struct ext4_dir_idx_climit *new_root_climit = (void *)e; |
1207 | |
1208 | ext4_dir_dx_climit_set_count(climit: new_root_climit, count: 1); |
1209 | ext4_dir_dx_entry_set_block(entry: e, block: new_iblk); |
1210 | |
1211 | struct ext4_dir_idx_root *r = (void *)dx_blks[0].b.data; |
1212 | r->info.indirect_levels = 1; |
1213 | |
1214 | /* Add new entry to the path */ |
1215 | dxb = dx_blks + 1; |
1216 | dxb->position = dx_blks->position - e + new_en; |
1217 | dxb->entries = new_en; |
1218 | dxb->b = b; |
1219 | *new_dx_block = dxb; |
1220 | |
1221 | ext4_dir_set_dx_csum(inode_ref: ino_ref, dirent: (void*)dx_blks[0].b.data); |
1222 | ext4_dir_set_dx_csum(inode_ref: ino_ref, dirent: (void*)dx_blks[1].b.data); |
1223 | ext4_trans_set_block_dirty(buf: dx_blks[0].b.buf); |
1224 | ext4_trans_set_block_dirty(buf: dx_blks[1].b.buf); |
1225 | } |
1226 | } |
1227 | |
1228 | return EOK; |
1229 | } |
1230 | |
1231 | int ext4_dir_dx_add_entry(struct ext4_inode_ref *parent, |
1232 | struct ext4_inode_ref *child, const char *name, uint32_t name_len) |
1233 | { |
1234 | int rc2 = EOK; |
1235 | int r; |
1236 | /* Get direct block 0 (index root) */ |
1237 | ext4_fsblk_t rblock_addr; |
1238 | r = ext4_fs_get_inode_dblk_idx(inode_ref: parent, iblock: 0, fblock: &rblock_addr, support_unwritten: false); |
1239 | if (r != EOK) |
1240 | return r; |
1241 | |
1242 | struct ext4_fs *fs = parent->fs; |
1243 | struct ext4_block root_blk; |
1244 | |
1245 | r = ext4_trans_block_get(bdev: fs->bdev, b: &root_blk, lba: rblock_addr); |
1246 | if (r != EOK) |
1247 | return r; |
1248 | |
1249 | if (!ext4_dir_dx_csum_verify(inode_ref: parent, de: (void*)root_blk.data)) { |
1250 | ext4_dbg(DEBUG_DIR_IDX, |
1251 | DBG_WARN "HTree root checksum failed." |
1252 | "Inode: %" PRIu32", " |
1253 | "Block: %" PRIu32"\n" , |
1254 | parent->index, |
1255 | (uint32_t)0); |
1256 | } |
1257 | |
1258 | /* Initialize hinfo structure (mainly compute hash) */ |
1259 | struct ext4_hash_info hinfo; |
1260 | r = ext4_dir_hinfo_init(hinfo: &hinfo, root_block: &root_blk, sb: &fs->sb, name_len, name); |
1261 | if (r != EOK) { |
1262 | ext4_block_set(bdev: fs->bdev, b: &root_blk); |
1263 | return EXT4_ERR_BAD_DX_DIR; |
1264 | } |
1265 | |
1266 | /* |
1267 | * Hardcoded number 2 means maximum height of index |
1268 | * tree defined in Linux. |
1269 | */ |
1270 | struct ext4_dir_idx_block dx_blks[2]; |
1271 | struct ext4_dir_idx_block *dx_blk; |
1272 | struct ext4_dir_idx_block *dx_it; |
1273 | |
1274 | r = ext4_dir_dx_get_leaf(hinfo: &hinfo, inode_ref: parent, root_block: &root_blk, dx_block: &dx_blk, dx_blocks: dx_blks); |
1275 | if (r != EOK) { |
1276 | r = EXT4_ERR_BAD_DX_DIR; |
1277 | goto release_index; |
1278 | } |
1279 | |
1280 | /* Try to insert to existing data block */ |
1281 | uint32_t leaf_block_idx = ext4_dir_dx_entry_get_block(entry: dx_blk->position); |
1282 | ext4_fsblk_t leaf_block_addr; |
1283 | r = ext4_fs_get_inode_dblk_idx(inode_ref: parent, iblock: leaf_block_idx, |
1284 | fblock: &leaf_block_addr, support_unwritten: false); |
1285 | if (r != EOK) |
1286 | goto release_index; |
1287 | |
1288 | /* |
1289 | * Check if there is needed to split index node |
1290 | * (and recursively also parent nodes) |
1291 | */ |
1292 | r = ext4_dir_dx_split_index(ino_ref: parent, dx_blks, dxb: dx_blk, new_dx_block: &dx_blk); |
1293 | if (r != EOK) |
1294 | goto release_target_index; |
1295 | |
1296 | struct ext4_block target_block; |
1297 | r = ext4_trans_block_get(bdev: fs->bdev, b: &target_block, lba: leaf_block_addr); |
1298 | if (r != EOK) |
1299 | goto release_index; |
1300 | |
1301 | if (!ext4_dir_csum_verify(inode_ref: parent,dirent: (void *)target_block.data)) { |
1302 | ext4_dbg(DEBUG_DIR_IDX, |
1303 | DBG_WARN "HTree leaf block checksum failed." |
1304 | "Inode: %" PRIu32", " |
1305 | "Block: %" PRIu32"\n" , |
1306 | parent->index, |
1307 | leaf_block_idx); |
1308 | } |
1309 | |
1310 | /* Check if insert operation passed */ |
1311 | r = ext4_dir_try_insert_entry(sb: &fs->sb, inode_ref: parent, dst_blk: &target_block, child, |
1312 | name, name_len); |
1313 | if (r == EOK) |
1314 | goto release_target_index; |
1315 | |
1316 | /* Split entries to two blocks (includes sorting by hash value) */ |
1317 | struct ext4_block new_block; |
1318 | r = ext4_dir_dx_split_data(inode_ref: parent, hinfo: &hinfo, old_data_block: &target_block, index_block: dx_blk, |
1319 | new_data_block: &new_block); |
1320 | if (r != EOK) { |
1321 | rc2 = r; |
1322 | goto release_target_index; |
1323 | } |
1324 | |
1325 | /* Where to save new entry */ |
1326 | uint32_t blk_hash = ext4_dir_dx_entry_get_hash(entry: dx_blk->position + 1); |
1327 | if (hinfo.hash >= blk_hash) |
1328 | r = ext4_dir_try_insert_entry(sb: &fs->sb, inode_ref: parent, dst_blk: &new_block, |
1329 | child, name, name_len); |
1330 | else |
1331 | r = ext4_dir_try_insert_entry(sb: &fs->sb, inode_ref: parent, dst_blk: &target_block, |
1332 | child, name, name_len); |
1333 | |
1334 | /* Cleanup */ |
1335 | r = ext4_block_set(bdev: fs->bdev, b: &new_block); |
1336 | if (r != EOK) |
1337 | return r; |
1338 | |
1339 | /* Cleanup operations */ |
1340 | |
1341 | release_target_index: |
1342 | rc2 = r; |
1343 | |
1344 | r = ext4_block_set(bdev: fs->bdev, b: &target_block); |
1345 | if (r != EOK) |
1346 | return r; |
1347 | |
1348 | release_index: |
1349 | if (r != EOK) |
1350 | rc2 = r; |
1351 | |
1352 | dx_it = dx_blks; |
1353 | |
1354 | while (dx_it <= dx_blk) { |
1355 | r = ext4_block_set(bdev: fs->bdev, b: &dx_it->b); |
1356 | if (r != EOK) |
1357 | return r; |
1358 | |
1359 | dx_it++; |
1360 | } |
1361 | |
1362 | return rc2; |
1363 | } |
1364 | |
1365 | int ext4_dir_dx_reset_parent_inode(struct ext4_inode_ref *dir, |
1366 | uint32_t parent_inode) |
1367 | { |
1368 | /* Load block 0, where will be index root located */ |
1369 | ext4_fsblk_t fblock; |
1370 | int rc = ext4_fs_get_inode_dblk_idx(inode_ref: dir, iblock: 0, fblock: &fblock, support_unwritten: false); |
1371 | if (rc != EOK) |
1372 | return rc; |
1373 | |
1374 | struct ext4_block block; |
1375 | rc = ext4_trans_block_get(bdev: dir->fs->bdev, b: &block, lba: fblock); |
1376 | if (rc != EOK) |
1377 | return rc; |
1378 | |
1379 | if (!ext4_dir_dx_csum_verify(inode_ref: dir, de: (void *)block.data)) { |
1380 | ext4_dbg(DEBUG_DIR_IDX, |
1381 | DBG_WARN "HTree root checksum failed." |
1382 | "Inode: %" PRIu32", " |
1383 | "Block: %" PRIu32"\n" , |
1384 | dir->index, |
1385 | (uint32_t)0); |
1386 | } |
1387 | |
1388 | /* Initialize pointers to data structures */ |
1389 | struct ext4_dir_idx_root *root = (void *)block.data; |
1390 | |
1391 | /* Fill the inode field with a new parent ino. */ |
1392 | ext4_dx_dot_en_set_inode(de: &root->dots[1], inode: parent_inode); |
1393 | |
1394 | ext4_dir_set_dx_csum(inode_ref: dir, dirent: (void *)block.data); |
1395 | ext4_trans_set_block_dirty(buf: block.buf); |
1396 | |
1397 | return ext4_block_set(bdev: dir->fs->bdev, b: &block); |
1398 | } |
1399 | |
1400 | /** |
1401 | * @} |
1402 | */ |
1403 | |