Linux codestyle format (tabs indenation)
[lwext4.git] / lwext4 / ext4_dir.c
1 /*\r
2  * Copyright (c) 2013 Grzegorz Kostka (kostka.grzegorz@gmail.com)\r
3  *\r
4  *\r
5  * HelenOS:\r
6  * Copyright (c) 2012 Martin Sucha\r
7  * Copyright (c) 2012 Frantisek Princ\r
8  * All rights reserved.\r
9  *\r
10  * Redistribution and use in source and binary forms, with or without\r
11  * modification, are permitted provided that the following conditions\r
12  * are met:\r
13  *\r
14  * - Redistributions of source code must retain the above copyright\r
15  *   notice, this list of conditions and the following disclaimer.\r
16  * - Redistributions in binary form must reproduce the above copyright\r
17  *   notice, this list of conditions and the following disclaimer in the\r
18  *   documentation and/or other materials provided with the distribution.\r
19  * - The name of the author may not be used to endorse or promote products\r
20  *   derived from this software without specific prior written permission.\r
21  *\r
22  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR\r
23  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\r
24  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.\r
25  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,\r
26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\r
27  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,\r
28  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY\r
29  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT\r
30  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF\r
31  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\r
32  */\r
33 \r
34 /** @addtogroup lwext4\r
35  * @{\r
36  */\r
37 /**\r
38  * @file  ext4_dir.h\r
39  * @brief Directory handle procedures.\r
40  */\r
41 \r
42 #include "ext4_config.h"\r
43 #include "ext4_dir.h"\r
44 #include "ext4_dir_idx.h"\r
45 #include "ext4_inode.h"\r
46 #include "ext4_fs.h"\r
47 \r
48 #include <string.h>\r
49 \r
50 /****************************************************************************/\r
51 \r
52 /**@brief Do some checks before returning iterator.\r
53  * @param it Iterator to be checked\r
54  * @param block_size Size of data block\r
55  * @return Error code\r
56  */\r
57 static int ext4_dir_iterator_set(struct ext4_directory_iterator *it,\r
58                                  uint32_t block_size)\r
59 {\r
60         it->current = NULL;\r
61 \r
62         uint32_t offset_in_block = it->current_offset % block_size;\r
63 \r
64         /* Ensure proper alignment */\r
65         if ((offset_in_block % 4) != 0)\r
66                 return EIO;\r
67 \r
68         /* Ensure that the core of the entry does not overflow the block */\r
69         if (offset_in_block > block_size - 8)\r
70                 return EIO;\r
71 \r
72         struct ext4_directory_entry_ll *entry =\r
73             (void *)(it->current_block.data + offset_in_block);\r
74 \r
75         /* Ensure that the whole entry does not overflow the block */\r
76         uint16_t length = ext4_dir_entry_ll_get_entry_length(entry);\r
77         if (offset_in_block + length > block_size)\r
78                 return EIO;\r
79 \r
80         /* Ensure the name length is not too large */\r
81         if (ext4_dir_entry_ll_get_name_length(&it->inode_ref->fs->sb, entry) >\r
82             length - 8)\r
83                 return EIO;\r
84 \r
85         /* Everything OK - "publish" the entry */\r
86         it->current = entry;\r
87         return EOK;\r
88 }\r
89 \r
90 /**@brief Seek to next valid directory entry.\r
91  *        Here can be jumped to the next data block.\r
92  * @param it  Initialized iterator\r
93  * @param pos Position of the next entry\r
94  * @return Error code\r
95  */\r
96 static int ext4_dir_iterator_seek(struct ext4_directory_iterator *it,\r
97                                   uint64_t pos)\r
98 {\r
99         uint64_t size =\r
100             ext4_inode_get_size(&it->inode_ref->fs->sb, it->inode_ref->inode);\r
101 \r
102         /* The iterator is not valid until we seek to the desired position */\r
103         it->current = NULL;\r
104 \r
105         /* Are we at the end? */\r
106         if (pos >= size) {\r
107                 if (it->current_block.lb_id) {\r
108 \r
109                         int rc = ext4_block_set(it->inode_ref->fs->bdev,\r
110                                                 &it->current_block);\r
111                         it->current_block.lb_id = 0;\r
112 \r
113                         if (rc != EOK)\r
114                                 return rc;\r
115                 }\r
116 \r
117                 it->current_offset = pos;\r
118                 return EOK;\r
119         }\r
120 \r
121         /* Compute next block address */\r
122         uint32_t block_size = ext4_sb_get_block_size(&it->inode_ref->fs->sb);\r
123         uint64_t current_block_idx = it->current_offset / block_size;\r
124         uint64_t next_block_idx = pos / block_size;\r
125 \r
126         /*\r
127          * If we don't have a block or are moving across block boundary,\r
128          * we need to get another block\r
129          */\r
130         if ((it->current_block.lb_id == 0) ||\r
131             (current_block_idx != next_block_idx)) {\r
132                 if (it->current_block.lb_id) {\r
133                         int rc = ext4_block_set(it->inode_ref->fs->bdev,\r
134                                                 &it->current_block);\r
135                         it->current_block.lb_id = 0;\r
136 \r
137                         if (rc != EOK)\r
138                                 return rc;\r
139                 }\r
140 \r
141                 uint32_t next_block_phys_idx;\r
142                 int rc = ext4_fs_get_inode_data_block_index(\r
143                     it->inode_ref, next_block_idx, &next_block_phys_idx);\r
144                 if (rc != EOK)\r
145                         return rc;\r
146 \r
147                 rc = ext4_block_get(it->inode_ref->fs->bdev, &it->current_block,\r
148                                     next_block_phys_idx);\r
149                 if (rc != EOK) {\r
150                         it->current_block.lb_id = 0;\r
151                         return rc;\r
152                 }\r
153         }\r
154 \r
155         it->current_offset = pos;\r
156 \r
157         return ext4_dir_iterator_set(it, block_size);\r
158 }\r
159 \r
160 int ext4_dir_iterator_init(struct ext4_directory_iterator *it,\r
161                            struct ext4_inode_ref *inode_ref, uint64_t pos)\r
162 {\r
163         it->inode_ref = inode_ref;\r
164         it->current = 0;\r
165         it->current_offset = 0;\r
166         it->current_block.lb_id = 0;\r
167 \r
168         return ext4_dir_iterator_seek(it, pos);\r
169 }\r
170 \r
171 int ext4_dir_iterator_next(struct ext4_directory_iterator *it)\r
172 {\r
173         int r = EOK;\r
174         uint16_t skip;\r
175 \r
176         while (r == EOK) {\r
177                 skip = ext4_dir_entry_ll_get_entry_length(it->current);\r
178                 r = ext4_dir_iterator_seek(it, it->current_offset + skip);\r
179 \r
180                 if (!it->current)\r
181                         break;\r
182                 /*Skip NULL referenced entry*/\r
183                 if (it->current->inode != 0)\r
184                         break;\r
185         }\r
186 \r
187         return r;\r
188 }\r
189 \r
190 int ext4_dir_iterator_fini(struct ext4_directory_iterator *it)\r
191 {\r
192         it->current = 0;\r
193 \r
194         if (it->current_block.lb_id)\r
195                 return ext4_block_set(it->inode_ref->fs->bdev,\r
196                                       &it->current_block);\r
197 \r
198         return EOK;\r
199 }\r
200 \r
201 void ext4_dir_write_entry(struct ext4_sblock *sb,\r
202                           struct ext4_directory_entry_ll *entry,\r
203                           uint16_t entry_len, struct ext4_inode_ref *child,\r
204                           const char *name, size_t name_len)\r
205 {\r
206         /* Check maximum entry length */\r
207         ext4_assert(entry_len <= ext4_sb_get_block_size(sb));\r
208 \r
209         /* Set basic attributes */\r
210         ext4_dir_entry_ll_set_inode(entry, child->index);\r
211         ext4_dir_entry_ll_set_entry_length(entry, entry_len);\r
212         ext4_dir_entry_ll_set_name_length(sb, entry, name_len);\r
213 \r
214         /* Write name */\r
215         memcpy(entry->name, name, name_len);\r
216 \r
217         /* Set type of entry */\r
218         if (ext4_inode_is_type(sb, child->inode, EXT4_INODE_MODE_DIRECTORY))\r
219                 ext4_dir_entry_ll_set_inode_type(sb, entry,\r
220                                                  EXT4_DIRECTORY_FILETYPE_DIR);\r
221         else\r
222                 ext4_dir_entry_ll_set_inode_type(\r
223                     sb, entry, EXT4_DIRECTORY_FILETYPE_REG_FILE);\r
224 }\r
225 \r
226 int ext4_dir_add_entry(struct ext4_inode_ref *parent, const char *name,\r
227                        uint32_t name_len, struct ext4_inode_ref *child)\r
228 {\r
229         struct ext4_fs *fs = parent->fs;\r
230 \r
231 #if CONFIG_DIR_INDEX_ENABLE\r
232         /* Index adding (if allowed) */\r
233         if ((ext4_sb_has_feature_compatible(&fs->sb,\r
234                                             EXT4_FEATURE_COMPAT_DIR_INDEX)) &&\r
235             (ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX))) {\r
236                 int rc = ext4_dir_dx_add_entry(parent, child, name);\r
237 \r
238                 /* Check if index is not corrupted */\r
239                 if (rc != EXT4_ERR_BAD_DX_DIR) {\r
240                         if (rc != EOK)\r
241                                 return rc;\r
242 \r
243                         return EOK;\r
244                 }\r
245 \r
246                 /* Needed to clear dir index flag if corrupted */\r
247                 ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX);\r
248                 parent->dirty = true;\r
249         }\r
250 #endif\r
251 \r
252         /* Linear algorithm */\r
253         uint32_t iblock = 0;\r
254         uint32_t fblock = 0;\r
255         uint32_t block_size = ext4_sb_get_block_size(&fs->sb);\r
256         uint32_t inode_size = ext4_inode_get_size(&fs->sb, parent->inode);\r
257         uint32_t total_blocks = inode_size / block_size;\r
258 \r
259         /* Find block, where is space for new entry and try to add */\r
260         bool success = false;\r
261         for (iblock = 0; iblock < total_blocks; ++iblock) {\r
262                 int rc =\r
263                     ext4_fs_get_inode_data_block_index(parent, iblock, &fblock);\r
264                 if (rc != EOK)\r
265                         return rc;\r
266 \r
267                 struct ext4_block block;\r
268                 rc = ext4_block_get(fs->bdev, &block, fblock);\r
269                 if (rc != EOK)\r
270                         return rc;\r
271 \r
272                 /* If adding is successful, function can finish */\r
273                 rc = ext4_dir_try_insert_entry(&fs->sb, &block, child, name,\r
274                                                name_len);\r
275                 if (rc == EOK)\r
276                         success = true;\r
277 \r
278                 rc = ext4_block_set(fs->bdev, &block);\r
279                 if (rc != EOK)\r
280                         return rc;\r
281 \r
282                 if (success)\r
283                         return EOK;\r
284         }\r
285 \r
286         /* No free block found - needed to allocate next data block */\r
287 \r
288         iblock = 0;\r
289         fblock = 0;\r
290         int rc = ext4_fs_append_inode_block(parent, &fblock, &iblock);\r
291         if (rc != EOK)\r
292                 return rc;\r
293 \r
294         /* Load new block */\r
295         struct ext4_block new_block;\r
296 \r
297         rc = ext4_block_get(fs->bdev, &new_block, fblock);\r
298         if (rc != EOK)\r
299                 return rc;\r
300 \r
301         /* Fill block with zeroes */\r
302         memset(new_block.data, 0, block_size);\r
303         struct ext4_directory_entry_ll *block_entry = (void *)new_block.data;\r
304         ext4_dir_write_entry(&fs->sb, block_entry, block_size, child, name,\r
305                              name_len);\r
306 \r
307         /* Save new block */\r
308         new_block.dirty = true;\r
309         rc = ext4_block_set(fs->bdev, &new_block);\r
310 \r
311         return rc;\r
312 }\r
313 \r
314 int ext4_dir_find_entry(struct ext4_directory_search_result *result,\r
315                         struct ext4_inode_ref *parent, const char *name,\r
316                         uint32_t name_len)\r
317 {\r
318         struct ext4_sblock *sb = &parent->fs->sb;\r
319 \r
320 #if CONFIG_DIR_INDEX_ENABLE\r
321         /* Index search */\r
322         if ((ext4_sb_has_feature_compatible(sb,\r
323                                             EXT4_FEATURE_COMPAT_DIR_INDEX)) &&\r
324             (ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX))) {\r
325                 int rc = ext4_dir_dx_find_entry(result, parent, name_len, name);\r
326 \r
327                 /* Check if index is not corrupted */\r
328                 if (rc != EXT4_ERR_BAD_DX_DIR) {\r
329                         if (rc != EOK)\r
330                                 return rc;\r
331 \r
332                         return EOK;\r
333                 }\r
334 \r
335                 /* Needed to clear dir index flag if corrupted */\r
336                 ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX);\r
337                 parent->dirty = true;\r
338         }\r
339 #endif\r
340 \r
341         /* Linear algorithm */\r
342 \r
343         uint32_t iblock;\r
344         uint32_t fblock;\r
345         uint32_t block_size = ext4_sb_get_block_size(sb);\r
346         uint32_t inode_size = ext4_inode_get_size(sb, parent->inode);\r
347         uint32_t total_blocks = inode_size / block_size;\r
348 \r
349         /* Walk through all data blocks */\r
350         for (iblock = 0; iblock < total_blocks; ++iblock) {\r
351                 /* Load block address */\r
352                 int rc =\r
353                     ext4_fs_get_inode_data_block_index(parent, iblock, &fblock);\r
354                 if (rc != EOK)\r
355                         return rc;\r
356 \r
357                 /* Load data block */\r
358                 struct ext4_block block;\r
359                 rc = ext4_block_get(parent->fs->bdev, &block, fblock);\r
360                 if (rc != EOK)\r
361                         return rc;\r
362 \r
363                 /* Try to find entry in block */\r
364                 struct ext4_directory_entry_ll *res_entry;\r
365                 rc = ext4_dir_find_in_block(&block, sb, name_len, name,\r
366                                             &res_entry);\r
367                 if (rc == EOK) {\r
368                         result->block = block;\r
369                         result->dentry = res_entry;\r
370                         return EOK;\r
371                 }\r
372 \r
373                 /* Entry not found - put block and continue to the next block */\r
374 \r
375                 rc = ext4_block_set(parent->fs->bdev, &block);\r
376                 if (rc != EOK)\r
377                         return rc;\r
378         }\r
379 \r
380         /* Entry was not found */\r
381 \r
382         result->block.lb_id = 0;\r
383         result->dentry = NULL;\r
384 \r
385         return ENOENT;\r
386 }\r
387 \r
388 int ext4_dir_remove_entry(struct ext4_inode_ref *parent, const char *name,\r
389                           uint32_t name_len)\r
390 {\r
391         /* Check if removing from directory */\r
392         if (!ext4_inode_is_type(&parent->fs->sb, parent->inode,\r
393                                 EXT4_INODE_MODE_DIRECTORY))\r
394                 return ENOTDIR;\r
395 \r
396         /* Try to find entry */\r
397         struct ext4_directory_search_result result;\r
398         int rc = ext4_dir_find_entry(&result, parent, name, name_len);\r
399         if (rc != EOK)\r
400                 return rc;\r
401 \r
402         /* Invalidate entry */\r
403         ext4_dir_entry_ll_set_inode(result.dentry, 0);\r
404 \r
405         /* Store entry position in block */\r
406         uint32_t pos = (uint8_t *)result.dentry - result.block.data;\r
407 \r
408         /*\r
409          * If entry is not the first in block, it must be merged\r
410          * with previous entry\r
411          */\r
412         if (pos != 0) {\r
413                 uint32_t offset = 0;\r
414 \r
415                 /* Start from the first entry in block */\r
416                 struct ext4_directory_entry_ll *tmp_dentry =\r
417                     (void *)result.block.data;\r
418                 uint16_t tmp_dentry_length =\r
419                     ext4_dir_entry_ll_get_entry_length(tmp_dentry);\r
420 \r
421                 /* Find direct predecessor of removed entry */\r
422                 while ((offset + tmp_dentry_length) < pos) {\r
423                         offset +=\r
424                             ext4_dir_entry_ll_get_entry_length(tmp_dentry);\r
425                         tmp_dentry = (void *)(result.block.data + offset);\r
426                         tmp_dentry_length =\r
427                             ext4_dir_entry_ll_get_entry_length(tmp_dentry);\r
428                 }\r
429 \r
430                 ext4_assert(tmp_dentry_length + offset == pos);\r
431 \r
432                 /* Add to removed entry length to predecessor's length */\r
433                 uint16_t del_entry_length =\r
434                     ext4_dir_entry_ll_get_entry_length(result.dentry);\r
435                 ext4_dir_entry_ll_set_entry_length(\r
436                     tmp_dentry, tmp_dentry_length + del_entry_length);\r
437         }\r
438 \r
439         result.block.dirty = true;\r
440 \r
441         return ext4_dir_destroy_result(parent, &result);\r
442 }\r
443 \r
444 int ext4_dir_try_insert_entry(struct ext4_sblock *sb,\r
445                               struct ext4_block *target_block,\r
446                               struct ext4_inode_ref *child, const char *name,\r
447                               uint32_t name_len)\r
448 {\r
449         /* Compute required length entry and align it to 4 bytes */\r
450         uint32_t block_size = ext4_sb_get_block_size(sb);\r
451         uint16_t required_len =\r
452             sizeof(struct ext4_fake_directory_entry) + name_len;\r
453 \r
454         if ((required_len % 4) != 0)\r
455                 required_len += 4 - (required_len % 4);\r
456 \r
457         /* Initialize pointers, stop means to upper bound */\r
458         struct ext4_directory_entry_ll *dentry = (void *)target_block->data;\r
459         struct ext4_directory_entry_ll *stop =\r
460             (void *)(target_block->data + block_size);\r
461 \r
462         /*\r
463          * Walk through the block and check for invalid entries\r
464          * or entries with free space for new entry\r
465          */\r
466         while (dentry < stop) {\r
467                 uint32_t inode = ext4_dir_entry_ll_get_inode(dentry);\r
468                 uint16_t rec_len = ext4_dir_entry_ll_get_entry_length(dentry);\r
469 \r
470                 /* If invalid and large enough entry, use it */\r
471                 if ((inode == 0) && (rec_len >= required_len)) {\r
472                         ext4_dir_write_entry(sb, dentry, rec_len, child, name,\r
473                                              name_len);\r
474                         target_block->dirty = true;\r
475 \r
476                         return EOK;\r
477                 }\r
478 \r
479                 /* Valid entry, try to split it */\r
480                 if (inode != 0) {\r
481                         uint16_t used_name_len =\r
482                             ext4_dir_entry_ll_get_name_length(sb, dentry);\r
483 \r
484                         uint16_t used_space =\r
485                             sizeof(struct ext4_fake_directory_entry) +\r
486                             used_name_len;\r
487 \r
488                         if ((used_name_len % 4) != 0)\r
489                                 used_space += 4 - (used_name_len % 4);\r
490 \r
491                         uint16_t free_space = rec_len - used_space;\r
492 \r
493                         /* There is free space for new entry */\r
494                         if (free_space >= required_len) {\r
495                                 /* Cut tail of current entry */\r
496                                 ext4_dir_entry_ll_set_entry_length(dentry,\r
497                                                                    used_space);\r
498                                 struct ext4_directory_entry_ll *new_entry =\r
499                                     (void *)((uint8_t *)dentry + used_space);\r
500                                 ext4_dir_write_entry(sb, new_entry, free_space,\r
501                                                      child, name, name_len);\r
502 \r
503                                 target_block->dirty = true;\r
504                                 return EOK;\r
505                         }\r
506                 }\r
507 \r
508                 /* Jump to the next entry */\r
509                 dentry = (void *)((uint8_t *)dentry + rec_len);\r
510         }\r
511 \r
512         /* No free space found for new entry */\r
513         return ENOSPC;\r
514 }\r
515 \r
516 int ext4_dir_find_in_block(struct ext4_block *block, struct ext4_sblock *sb,\r
517                            size_t name_len, const char *name,\r
518                            struct ext4_directory_entry_ll **res_entry)\r
519 {\r
520         /* Start from the first entry in block */\r
521         struct ext4_directory_entry_ll *dentry =\r
522             (struct ext4_directory_entry_ll *)block->data;\r
523 \r
524         /* Set upper bound for cycling */\r
525         uint8_t *addr_limit = block->data + ext4_sb_get_block_size(sb);\r
526 \r
527         /* Walk through the block and check entries */\r
528         while ((uint8_t *)dentry < addr_limit) {\r
529                 /* Termination condition */\r
530                 if ((uint8_t *)dentry + name_len > addr_limit)\r
531                         break;\r
532 \r
533                 /* Valid entry - check it */\r
534                 if (dentry->inode != 0) {\r
535                         /* For more efficient compare only lengths firstly*/\r
536                         if (ext4_dir_entry_ll_get_name_length(sb, dentry) ==\r
537                             name_len) {\r
538                                 /* Compare names */\r
539                                 if (memcmp((uint8_t *)name, dentry->name,\r
540                                            name_len) == 0) {\r
541                                         *res_entry = dentry;\r
542                                         return EOK;\r
543                                 }\r
544                         }\r
545                 }\r
546 \r
547                 uint16_t dentry_len =\r
548                     ext4_dir_entry_ll_get_entry_length(dentry);\r
549 \r
550                 /* Corrupted entry */\r
551                 if (dentry_len == 0)\r
552                         return EINVAL;\r
553 \r
554                 /* Jump to next entry */\r
555                 dentry = (struct ext4_directory_entry_ll *)((uint8_t *)dentry +\r
556                                                             dentry_len);\r
557         }\r
558 \r
559         /* Entry not found */\r
560         return ENOENT;\r
561 }\r
562 \r
563 int ext4_dir_destroy_result(struct ext4_inode_ref *parent,\r
564                             struct ext4_directory_search_result *result)\r
565 {\r
566         if (result->block.lb_id)\r
567                 return ext4_block_set(parent->fs->bdev, &result->block);\r
568 \r
569         return EOK;\r
570 }\r
571 \r
572 /**\r
573  * @}\r
574  */\r