| 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.c
|
|---|
| 34 | * @brief Ext4 directory structure operations.
|
|---|
| 35 | */
|
|---|
| 36 |
|
|---|
| 37 | #include <byteorder.h>
|
|---|
| 38 | #include <errno.h>
|
|---|
| 39 | #include <malloc.h>
|
|---|
| 40 | #include "libext4.h"
|
|---|
| 41 |
|
|---|
| 42 | /** Get i-node number from directory entry.
|
|---|
| 43 | *
|
|---|
| 44 | * @param de Directory entry
|
|---|
| 45 | *
|
|---|
| 46 | * @return I-node number
|
|---|
| 47 | *
|
|---|
| 48 | */
|
|---|
| 49 | uint32_t ext4_directory_entry_ll_get_inode(ext4_directory_entry_ll_t *de)
|
|---|
| 50 | {
|
|---|
| 51 | return uint32_t_le2host(de->inode);
|
|---|
| 52 | }
|
|---|
| 53 |
|
|---|
| 54 | /** Set i-node number to directory entry.
|
|---|
| 55 | *
|
|---|
| 56 | * @param de Directory entry
|
|---|
| 57 | * @param inode I-node number
|
|---|
| 58 | *
|
|---|
| 59 | */
|
|---|
| 60 | void ext4_directory_entry_ll_set_inode(ext4_directory_entry_ll_t *de,
|
|---|
| 61 | uint32_t inode)
|
|---|
| 62 | {
|
|---|
| 63 | de->inode = host2uint32_t_le(inode);
|
|---|
| 64 | }
|
|---|
| 65 |
|
|---|
| 66 | /** Get directory entry length.
|
|---|
| 67 | *
|
|---|
| 68 | * @param de Directory entry
|
|---|
| 69 | *
|
|---|
| 70 | * @return Entry length
|
|---|
| 71 | *
|
|---|
| 72 | */
|
|---|
| 73 | uint16_t ext4_directory_entry_ll_get_entry_length(ext4_directory_entry_ll_t *de)
|
|---|
| 74 | {
|
|---|
| 75 | return uint16_t_le2host(de->entry_length);
|
|---|
| 76 | }
|
|---|
| 77 |
|
|---|
| 78 | /** Set directory entry length.
|
|---|
| 79 | *
|
|---|
| 80 | * @param de Directory entry
|
|---|
| 81 | * @param length Entry length
|
|---|
| 82 | *
|
|---|
| 83 | */
|
|---|
| 84 | void ext4_directory_entry_ll_set_entry_length(ext4_directory_entry_ll_t *de,
|
|---|
| 85 | uint16_t length)
|
|---|
| 86 | {
|
|---|
| 87 | de->entry_length = host2uint16_t_le(length);
|
|---|
| 88 | }
|
|---|
| 89 |
|
|---|
| 90 | /** Get directory entry name length.
|
|---|
| 91 | *
|
|---|
| 92 | * @param sb Superblock
|
|---|
| 93 | * @param de Directory entry
|
|---|
| 94 | *
|
|---|
| 95 | * @return Entry name length
|
|---|
| 96 | *
|
|---|
| 97 | */
|
|---|
| 98 | uint16_t ext4_directory_entry_ll_get_name_length(ext4_superblock_t *sb,
|
|---|
| 99 | ext4_directory_entry_ll_t *de)
|
|---|
| 100 | {
|
|---|
| 101 | if ((ext4_superblock_get_rev_level(sb) == 0) &&
|
|---|
| 102 | (ext4_superblock_get_minor_rev_level(sb) < 5))
|
|---|
| 103 | return ((uint16_t)de->name_length_high) << 8 |
|
|---|
| 104 | ((uint16_t)de->name_length);
|
|---|
| 105 |
|
|---|
| 106 | return de->name_length;
|
|---|
| 107 |
|
|---|
| 108 | }
|
|---|
| 109 |
|
|---|
| 110 | /** Set directory entry name length.
|
|---|
| 111 | *
|
|---|
| 112 | * @param sb Superblock
|
|---|
| 113 | * @param de Directory entry
|
|---|
| 114 | * @param length Entry name length
|
|---|
| 115 | *
|
|---|
| 116 | */
|
|---|
| 117 | void ext4_directory_entry_ll_set_name_length(ext4_superblock_t *sb,
|
|---|
| 118 | ext4_directory_entry_ll_t *de, uint16_t length)
|
|---|
| 119 | {
|
|---|
| 120 | de->name_length = (length << 8) >> 8;
|
|---|
| 121 |
|
|---|
| 122 | if ((ext4_superblock_get_rev_level(sb) == 0) &&
|
|---|
| 123 | (ext4_superblock_get_minor_rev_level(sb) < 5))
|
|---|
| 124 | de->name_length_high = length >> 8;
|
|---|
| 125 |
|
|---|
| 126 | /* Else do nothing */
|
|---|
| 127 | }
|
|---|
| 128 |
|
|---|
| 129 | /** Get i-node type of directory entry.
|
|---|
| 130 | *
|
|---|
| 131 | * @param sb Superblock
|
|---|
| 132 | * @param de Directory entry
|
|---|
| 133 | *
|
|---|
| 134 | * @return I-node type (file, dir, etc.)
|
|---|
| 135 | *
|
|---|
| 136 | */
|
|---|
| 137 | uint8_t ext4_directory_entry_ll_get_inode_type(ext4_superblock_t *sb,
|
|---|
| 138 | ext4_directory_entry_ll_t *de)
|
|---|
| 139 | {
|
|---|
| 140 | if ((ext4_superblock_get_rev_level(sb) > 0) ||
|
|---|
| 141 | (ext4_superblock_get_minor_rev_level(sb) >= 5))
|
|---|
| 142 | return de->inode_type;
|
|---|
| 143 |
|
|---|
| 144 | return EXT4_DIRECTORY_FILETYPE_UNKNOWN;
|
|---|
| 145 | }
|
|---|
| 146 |
|
|---|
| 147 | /** Set i-node type of directory entry.
|
|---|
| 148 | *
|
|---|
| 149 | * @param sb Superblock
|
|---|
| 150 | * @param de Directory entry
|
|---|
| 151 | * @param type I-node type (file, dir, etc.)
|
|---|
| 152 | *
|
|---|
| 153 | */
|
|---|
| 154 | void ext4_directory_entry_ll_set_inode_type(ext4_superblock_t *sb,
|
|---|
| 155 | ext4_directory_entry_ll_t *de, uint8_t type)
|
|---|
| 156 | {
|
|---|
| 157 | if ((ext4_superblock_get_rev_level(sb) > 0) ||
|
|---|
| 158 | (ext4_superblock_get_minor_rev_level(sb) >= 5))
|
|---|
| 159 | de->inode_type = type;
|
|---|
| 160 |
|
|---|
| 161 | /* Else do nothing */
|
|---|
| 162 | }
|
|---|
| 163 |
|
|---|
| 164 | static int ext4_directory_iterator_seek(ext4_directory_iterator_t *, aoff64_t);
|
|---|
| 165 | static int ext4_directory_iterator_set(ext4_directory_iterator_t *, uint32_t);
|
|---|
| 166 |
|
|---|
| 167 | /** Initialize directory iterator.
|
|---|
| 168 | *
|
|---|
| 169 | * Set position to the first valid entry from the required position.
|
|---|
| 170 | *
|
|---|
| 171 | * @param it Pointer to iterator to be initialized
|
|---|
| 172 | * @param inode_ref Directory i-node
|
|---|
| 173 | * @param pos Position to start reading entries from
|
|---|
| 174 | *
|
|---|
| 175 | * @return Error code
|
|---|
| 176 | *
|
|---|
| 177 | */
|
|---|
| 178 | int ext4_directory_iterator_init(ext4_directory_iterator_t *it,
|
|---|
| 179 | ext4_inode_ref_t *inode_ref, aoff64_t pos)
|
|---|
| 180 | {
|
|---|
| 181 | it->inode_ref = inode_ref;
|
|---|
| 182 | it->current = NULL;
|
|---|
| 183 | it->current_offset = 0;
|
|---|
| 184 | it->current_block = NULL;
|
|---|
| 185 |
|
|---|
| 186 | return ext4_directory_iterator_seek(it, pos);
|
|---|
| 187 | }
|
|---|
| 188 |
|
|---|
| 189 | /** Jump to the next valid entry
|
|---|
| 190 | *
|
|---|
| 191 | * @param it Initialized iterator
|
|---|
| 192 | *
|
|---|
| 193 | * @return Error code
|
|---|
| 194 | *
|
|---|
| 195 | */
|
|---|
| 196 | int ext4_directory_iterator_next(ext4_directory_iterator_t *it)
|
|---|
| 197 | {
|
|---|
| 198 | assert(it->current != NULL);
|
|---|
| 199 |
|
|---|
| 200 | uint16_t skip = ext4_directory_entry_ll_get_entry_length(it->current);
|
|---|
| 201 |
|
|---|
| 202 | return ext4_directory_iterator_seek(it, it->current_offset + skip);
|
|---|
| 203 | }
|
|---|
| 204 |
|
|---|
| 205 | /** Seek to next valid directory entry.
|
|---|
| 206 | *
|
|---|
| 207 | * Here can be jumped to the next data block.
|
|---|
| 208 | *
|
|---|
| 209 | * @param it Initialized iterator
|
|---|
| 210 | * @param pos Position of the next entry
|
|---|
| 211 | *
|
|---|
| 212 | * @return Error code
|
|---|
| 213 | *
|
|---|
| 214 | */
|
|---|
| 215 | int ext4_directory_iterator_seek(ext4_directory_iterator_t *it, aoff64_t pos)
|
|---|
| 216 | {
|
|---|
| 217 | uint64_t size = ext4_inode_get_size(it->inode_ref->fs->superblock,
|
|---|
| 218 | it->inode_ref->inode);
|
|---|
| 219 |
|
|---|
| 220 | /* The iterator is not valid until we seek to the desired position */
|
|---|
| 221 | it->current = NULL;
|
|---|
| 222 |
|
|---|
| 223 | /* Are we at the end? */
|
|---|
| 224 | if (pos >= size) {
|
|---|
| 225 | if (it->current_block) {
|
|---|
| 226 | int rc = block_put(it->current_block);
|
|---|
| 227 | it->current_block = NULL;
|
|---|
| 228 |
|
|---|
| 229 | if (rc != EOK)
|
|---|
| 230 | return rc;
|
|---|
| 231 | }
|
|---|
| 232 |
|
|---|
| 233 | it->current_offset = pos;
|
|---|
| 234 | return EOK;
|
|---|
| 235 | }
|
|---|
| 236 |
|
|---|
| 237 | /* Compute next block address */
|
|---|
| 238 | uint32_t block_size =
|
|---|
| 239 | ext4_superblock_get_block_size(it->inode_ref->fs->superblock);
|
|---|
| 240 | aoff64_t current_block_idx = it->current_offset / block_size;
|
|---|
| 241 | aoff64_t next_block_idx = pos / block_size;
|
|---|
| 242 |
|
|---|
| 243 | /*
|
|---|
| 244 | * If we don't have a block or are moving accross block boundary,
|
|---|
| 245 | * we need to get another block
|
|---|
| 246 | */
|
|---|
| 247 | if ((it->current_block == NULL) ||
|
|---|
| 248 | (current_block_idx != next_block_idx)) {
|
|---|
| 249 | if (it->current_block) {
|
|---|
| 250 | int rc = block_put(it->current_block);
|
|---|
| 251 | it->current_block = NULL;
|
|---|
| 252 |
|
|---|
| 253 | if (rc != EOK)
|
|---|
| 254 | return rc;
|
|---|
| 255 | }
|
|---|
| 256 |
|
|---|
| 257 | uint32_t next_block_phys_idx;
|
|---|
| 258 | int rc = ext4_filesystem_get_inode_data_block_index(it->inode_ref,
|
|---|
| 259 | next_block_idx, &next_block_phys_idx);
|
|---|
| 260 | if (rc != EOK)
|
|---|
| 261 | return rc;
|
|---|
| 262 |
|
|---|
| 263 | rc = block_get(&it->current_block, it->inode_ref->fs->device,
|
|---|
| 264 | next_block_phys_idx, BLOCK_FLAGS_NONE);
|
|---|
| 265 | if (rc != EOK) {
|
|---|
| 266 | it->current_block = NULL;
|
|---|
| 267 | return rc;
|
|---|
| 268 | }
|
|---|
| 269 | }
|
|---|
| 270 |
|
|---|
| 271 | it->current_offset = pos;
|
|---|
| 272 |
|
|---|
| 273 | return ext4_directory_iterator_set(it, block_size);
|
|---|
| 274 | }
|
|---|
| 275 |
|
|---|
| 276 | /** Do some checks before returning iterator.
|
|---|
| 277 | *
|
|---|
| 278 | * @param it Iterator to be checked
|
|---|
| 279 | * @param block_size Size of data block
|
|---|
| 280 | *
|
|---|
| 281 | * @return Error code
|
|---|
| 282 | *
|
|---|
| 283 | */
|
|---|
| 284 | static int ext4_directory_iterator_set(ext4_directory_iterator_t *it,
|
|---|
| 285 | uint32_t block_size)
|
|---|
| 286 | {
|
|---|
| 287 | it->current = NULL;
|
|---|
| 288 |
|
|---|
| 289 | uint32_t offset_in_block = it->current_offset % block_size;
|
|---|
| 290 |
|
|---|
| 291 | /* Ensure proper alignment */
|
|---|
| 292 | if ((offset_in_block % 4) != 0)
|
|---|
| 293 | return EIO;
|
|---|
| 294 |
|
|---|
| 295 | /* Ensure that the core of the entry does not overflow the block */
|
|---|
| 296 | if (offset_in_block > block_size - 8)
|
|---|
| 297 | return EIO;
|
|---|
| 298 |
|
|---|
| 299 | ext4_directory_entry_ll_t *entry =
|
|---|
| 300 | it->current_block->data + offset_in_block;
|
|---|
| 301 |
|
|---|
| 302 | /* Ensure that the whole entry does not overflow the block */
|
|---|
| 303 | uint16_t length = ext4_directory_entry_ll_get_entry_length(entry);
|
|---|
| 304 | if (offset_in_block + length > block_size)
|
|---|
| 305 | return EIO;
|
|---|
| 306 |
|
|---|
| 307 | /* Ensure the name length is not too large */
|
|---|
| 308 | if (ext4_directory_entry_ll_get_name_length(
|
|---|
| 309 | it->inode_ref->fs->superblock, entry) > length-8)
|
|---|
| 310 | return EIO;
|
|---|
| 311 |
|
|---|
| 312 | /* Everything OK - "publish" the entry */
|
|---|
| 313 | it->current = entry;
|
|---|
| 314 | return EOK;
|
|---|
| 315 | }
|
|---|
| 316 |
|
|---|
| 317 | /** Uninitialize directory iterator.
|
|---|
| 318 | *
|
|---|
| 319 | * Release all allocated structures.
|
|---|
| 320 | *
|
|---|
| 321 | * @param it Iterator to be finished
|
|---|
| 322 | *
|
|---|
| 323 | * @return Error code
|
|---|
| 324 | *
|
|---|
| 325 | */
|
|---|
| 326 | int ext4_directory_iterator_fini(ext4_directory_iterator_t *it)
|
|---|
| 327 | {
|
|---|
| 328 | it->inode_ref = NULL;
|
|---|
| 329 | it->current = NULL;
|
|---|
| 330 |
|
|---|
| 331 | if (it->current_block)
|
|---|
| 332 | return block_put(it->current_block);
|
|---|
| 333 |
|
|---|
| 334 | return EOK;
|
|---|
| 335 | }
|
|---|
| 336 |
|
|---|
| 337 | /** Write directory entry to concrete data block.
|
|---|
| 338 | *
|
|---|
| 339 | * @param sb Superblock
|
|---|
| 340 | * @param entry Pointer to entry to be written
|
|---|
| 341 | * @param entry_len Length of new entry
|
|---|
| 342 | * @param child Child i-node to be written to new entry
|
|---|
| 343 | * @param name Name of the new entry
|
|---|
| 344 | * @param name_len Length of entry name
|
|---|
| 345 | *
|
|---|
| 346 | */
|
|---|
| 347 | void ext4_directory_write_entry(ext4_superblock_t *sb,
|
|---|
| 348 | ext4_directory_entry_ll_t *entry, uint16_t entry_len,
|
|---|
| 349 | ext4_inode_ref_t *child, const char *name, size_t name_len)
|
|---|
| 350 | {
|
|---|
| 351 | /* Check maximum entry length */
|
|---|
| 352 | uint32_t block_size = ext4_superblock_get_block_size(sb);
|
|---|
| 353 | assert(entry_len <= block_size);
|
|---|
| 354 |
|
|---|
| 355 | /* Set basic attributes */
|
|---|
| 356 | ext4_directory_entry_ll_set_inode(entry, child->index);
|
|---|
| 357 | ext4_directory_entry_ll_set_entry_length(entry, entry_len);
|
|---|
| 358 | ext4_directory_entry_ll_set_name_length(sb, entry, name_len);
|
|---|
| 359 |
|
|---|
| 360 | /* Write name */
|
|---|
| 361 | memcpy(entry->name, name, name_len);
|
|---|
| 362 |
|
|---|
| 363 | /* Set type of entry */
|
|---|
| 364 | if (ext4_inode_is_type(sb, child->inode, EXT4_INODE_MODE_DIRECTORY))
|
|---|
| 365 | ext4_directory_entry_ll_set_inode_type(sb, entry,
|
|---|
| 366 | EXT4_DIRECTORY_FILETYPE_DIR);
|
|---|
| 367 | else
|
|---|
| 368 | ext4_directory_entry_ll_set_inode_type(sb, entry,
|
|---|
| 369 | EXT4_DIRECTORY_FILETYPE_REG_FILE);
|
|---|
| 370 | }
|
|---|
| 371 |
|
|---|
| 372 | /** Add new entry to the directory.
|
|---|
| 373 | *
|
|---|
| 374 | * @param parent Directory i-node
|
|---|
| 375 | * @param name Name of new entry
|
|---|
| 376 | * @param child I-node to be referenced from new entry
|
|---|
| 377 | *
|
|---|
| 378 | * @return Error code
|
|---|
| 379 | *
|
|---|
| 380 | */
|
|---|
| 381 | int ext4_directory_add_entry(ext4_inode_ref_t *parent, const char *name,
|
|---|
| 382 | ext4_inode_ref_t *child)
|
|---|
| 383 | {
|
|---|
| 384 | ext4_filesystem_t *fs = parent->fs;
|
|---|
| 385 |
|
|---|
| 386 | /* Index adding (if allowed) */
|
|---|
| 387 | if ((ext4_superblock_has_feature_compatible(fs->superblock,
|
|---|
| 388 | EXT4_FEATURE_COMPAT_DIR_INDEX)) &&
|
|---|
| 389 | (ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX))) {
|
|---|
| 390 | int rc = ext4_directory_dx_add_entry(parent, child, name);
|
|---|
| 391 |
|
|---|
| 392 | /* Check if index is not corrupted */
|
|---|
| 393 | if (rc != EXT4_ERR_BAD_DX_DIR) {
|
|---|
| 394 | if (rc != EOK)
|
|---|
| 395 | return rc;
|
|---|
| 396 |
|
|---|
| 397 | return EOK;
|
|---|
| 398 | }
|
|---|
| 399 |
|
|---|
| 400 | /* Needed to clear dir index flag if corrupted */
|
|---|
| 401 | ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX);
|
|---|
| 402 | parent->dirty = true;
|
|---|
| 403 | }
|
|---|
| 404 |
|
|---|
| 405 | /* Linear algorithm */
|
|---|
| 406 |
|
|---|
| 407 | uint32_t iblock = 0;
|
|---|
| 408 | uint32_t fblock = 0;
|
|---|
| 409 | uint32_t block_size = ext4_superblock_get_block_size(fs->superblock);
|
|---|
| 410 | uint32_t inode_size = ext4_inode_get_size(fs->superblock, parent->inode);
|
|---|
| 411 | uint32_t total_blocks = inode_size / block_size;
|
|---|
| 412 |
|
|---|
| 413 | uint32_t name_len = str_size(name);
|
|---|
| 414 |
|
|---|
| 415 | /* Find block, where is space for new entry and try to add */
|
|---|
| 416 | bool success = false;
|
|---|
| 417 | for (iblock = 0; iblock < total_blocks; ++iblock) {
|
|---|
| 418 | int rc = ext4_filesystem_get_inode_data_block_index(parent,
|
|---|
| 419 | iblock, &fblock);
|
|---|
| 420 | if (rc != EOK)
|
|---|
| 421 | return rc;
|
|---|
| 422 |
|
|---|
| 423 | block_t *block;
|
|---|
| 424 | rc = block_get(&block, fs->device, fblock, BLOCK_FLAGS_NONE);
|
|---|
| 425 | if (rc != EOK)
|
|---|
| 426 | return rc;
|
|---|
| 427 |
|
|---|
| 428 | /* If adding is successful, function can finish */
|
|---|
| 429 | rc = ext4_directory_try_insert_entry(fs->superblock, block,
|
|---|
| 430 | child, name, name_len);
|
|---|
| 431 | if (rc == EOK)
|
|---|
| 432 | success = true;
|
|---|
| 433 |
|
|---|
| 434 | rc = block_put(block);
|
|---|
| 435 | if (rc != EOK)
|
|---|
| 436 | return rc;
|
|---|
| 437 |
|
|---|
| 438 | if (success)
|
|---|
| 439 | return EOK;
|
|---|
| 440 | }
|
|---|
| 441 |
|
|---|
| 442 | /* No free block found - needed to allocate next data block */
|
|---|
| 443 |
|
|---|
| 444 | iblock = 0;
|
|---|
| 445 | fblock = 0;
|
|---|
| 446 | int rc = ext4_filesystem_append_inode_block(parent, &fblock, &iblock);
|
|---|
| 447 | if (rc != EOK)
|
|---|
| 448 | return rc;
|
|---|
| 449 |
|
|---|
| 450 | /* Load new block */
|
|---|
| 451 | block_t *new_block;
|
|---|
| 452 | rc = block_get(&new_block, fs->device, fblock, BLOCK_FLAGS_NOREAD);
|
|---|
| 453 | if (rc != EOK)
|
|---|
| 454 | return rc;
|
|---|
| 455 |
|
|---|
| 456 | /* Fill block with zeroes */
|
|---|
| 457 | memset(new_block->data, 0, block_size);
|
|---|
| 458 | ext4_directory_entry_ll_t *block_entry = new_block->data;
|
|---|
| 459 | ext4_directory_write_entry(fs->superblock, block_entry, block_size,
|
|---|
| 460 | child, name, name_len);
|
|---|
| 461 |
|
|---|
| 462 | /* Save new block */
|
|---|
| 463 | new_block->dirty = true;
|
|---|
| 464 | rc = block_put(new_block);
|
|---|
| 465 |
|
|---|
| 466 | return rc;
|
|---|
| 467 | }
|
|---|
| 468 |
|
|---|
| 469 | /** Find directory entry with passed name.
|
|---|
| 470 | *
|
|---|
| 471 | * @param result Result structure to be returned if entry found
|
|---|
| 472 | * @param parent Directory i-node
|
|---|
| 473 | * @param name Name of entry to be found
|
|---|
| 474 | *
|
|---|
| 475 | * @return Error code
|
|---|
| 476 | *
|
|---|
| 477 | */
|
|---|
| 478 | int ext4_directory_find_entry(ext4_directory_search_result_t *result,
|
|---|
| 479 | ext4_inode_ref_t *parent, const char *name)
|
|---|
| 480 | {
|
|---|
| 481 | uint32_t name_len = str_size(name);
|
|---|
| 482 |
|
|---|
| 483 | ext4_superblock_t *sb = parent->fs->superblock;
|
|---|
| 484 |
|
|---|
| 485 | /* Index search */
|
|---|
| 486 | if ((ext4_superblock_has_feature_compatible(sb,
|
|---|
| 487 | EXT4_FEATURE_COMPAT_DIR_INDEX)) &&
|
|---|
| 488 | (ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX))) {
|
|---|
| 489 | int rc = ext4_directory_dx_find_entry(result, parent, name_len,
|
|---|
| 490 | name);
|
|---|
| 491 |
|
|---|
| 492 | /* Check if index is not corrupted */
|
|---|
| 493 | if (rc != EXT4_ERR_BAD_DX_DIR) {
|
|---|
| 494 | if (rc != EOK)
|
|---|
| 495 | return rc;
|
|---|
| 496 |
|
|---|
| 497 | return EOK;
|
|---|
| 498 | }
|
|---|
| 499 |
|
|---|
| 500 | /* Needed to clear dir index flag if corrupted */
|
|---|
| 501 | ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX);
|
|---|
| 502 | parent->dirty = true;
|
|---|
| 503 | }
|
|---|
| 504 |
|
|---|
| 505 | /* Linear algorithm */
|
|---|
| 506 |
|
|---|
| 507 | uint32_t iblock;
|
|---|
| 508 | uint32_t fblock;
|
|---|
| 509 | uint32_t block_size = ext4_superblock_get_block_size(sb);
|
|---|
| 510 | uint32_t inode_size = ext4_inode_get_size(sb, parent->inode);
|
|---|
| 511 | uint32_t total_blocks = inode_size / block_size;
|
|---|
| 512 |
|
|---|
| 513 | /* Walk through all data blocks */
|
|---|
| 514 | for (iblock = 0; iblock < total_blocks; ++iblock) {
|
|---|
| 515 | /* Load block address */
|
|---|
| 516 | int rc = ext4_filesystem_get_inode_data_block_index(parent, iblock,
|
|---|
| 517 | &fblock);
|
|---|
| 518 | if (rc != EOK)
|
|---|
| 519 | return rc;
|
|---|
| 520 |
|
|---|
| 521 | /* Load data block */
|
|---|
| 522 | block_t *block;
|
|---|
| 523 | rc = block_get(&block, parent->fs->device, fblock, BLOCK_FLAGS_NONE);
|
|---|
| 524 | if (rc != EOK)
|
|---|
| 525 | return rc;
|
|---|
| 526 |
|
|---|
| 527 | /* Try to find entry in block */
|
|---|
| 528 | ext4_directory_entry_ll_t *res_entry;
|
|---|
| 529 | rc = ext4_directory_find_in_block(block, sb, name_len, name,
|
|---|
| 530 | &res_entry);
|
|---|
| 531 | if (rc == EOK) {
|
|---|
| 532 | result->block = block;
|
|---|
| 533 | result->dentry = res_entry;
|
|---|
| 534 | return EOK;
|
|---|
| 535 | }
|
|---|
| 536 |
|
|---|
| 537 | /* Entry not found - put block and continue to the next block */
|
|---|
| 538 |
|
|---|
| 539 | rc = block_put(block);
|
|---|
| 540 | if (rc != EOK)
|
|---|
| 541 | return rc;
|
|---|
| 542 | }
|
|---|
| 543 |
|
|---|
| 544 | /* Entry was not found */
|
|---|
| 545 |
|
|---|
| 546 | result->block = NULL;
|
|---|
| 547 | result->dentry = NULL;
|
|---|
| 548 |
|
|---|
| 549 | return ENOENT;
|
|---|
| 550 | }
|
|---|
| 551 |
|
|---|
| 552 | /** Remove directory entry.
|
|---|
| 553 | *
|
|---|
| 554 | * @param parent Directory i-node
|
|---|
| 555 | * @param name Name of the entry to be removed
|
|---|
| 556 | *
|
|---|
| 557 | * @return Error code
|
|---|
| 558 | *
|
|---|
| 559 | */
|
|---|
| 560 | int ext4_directory_remove_entry(ext4_inode_ref_t *parent, const char *name)
|
|---|
| 561 | {
|
|---|
| 562 | /* Check if removing from directory */
|
|---|
| 563 | if (!ext4_inode_is_type(parent->fs->superblock, parent->inode,
|
|---|
| 564 | EXT4_INODE_MODE_DIRECTORY))
|
|---|
| 565 | return ENOTDIR;
|
|---|
| 566 |
|
|---|
| 567 | /* Try to find entry */
|
|---|
| 568 | ext4_directory_search_result_t result;
|
|---|
| 569 | int rc = ext4_directory_find_entry(&result, parent, name);
|
|---|
| 570 | if (rc != EOK)
|
|---|
| 571 | return rc;
|
|---|
| 572 |
|
|---|
| 573 | /* Invalidate entry */
|
|---|
| 574 | ext4_directory_entry_ll_set_inode(result.dentry, 0);
|
|---|
| 575 |
|
|---|
| 576 | /* Store entry position in block */
|
|---|
| 577 | uint32_t pos = (void *) result.dentry - result.block->data;
|
|---|
| 578 |
|
|---|
| 579 | /*
|
|---|
| 580 | * If entry is not the first in block, it must be merged
|
|---|
| 581 | * with previous entry
|
|---|
| 582 | */
|
|---|
| 583 | if (pos != 0) {
|
|---|
| 584 | uint32_t offset = 0;
|
|---|
| 585 |
|
|---|
| 586 | /* Start from the first entry in block */
|
|---|
| 587 | ext4_directory_entry_ll_t *tmp_dentry = result.block->data;
|
|---|
| 588 | uint16_t tmp_dentry_length =
|
|---|
| 589 | ext4_directory_entry_ll_get_entry_length(tmp_dentry);
|
|---|
| 590 |
|
|---|
| 591 | /* Find direct predecessor of removed entry */
|
|---|
| 592 | while ((offset + tmp_dentry_length) < pos) {
|
|---|
| 593 | offset +=
|
|---|
| 594 | ext4_directory_entry_ll_get_entry_length(tmp_dentry);
|
|---|
| 595 | tmp_dentry = result.block->data + offset;
|
|---|
| 596 | tmp_dentry_length =
|
|---|
| 597 | ext4_directory_entry_ll_get_entry_length(tmp_dentry);
|
|---|
| 598 | }
|
|---|
| 599 |
|
|---|
| 600 | assert(tmp_dentry_length + offset == pos);
|
|---|
| 601 |
|
|---|
| 602 | /* Add to removed entry length to predecessor's length */
|
|---|
| 603 | uint16_t del_entry_length =
|
|---|
| 604 | ext4_directory_entry_ll_get_entry_length(result.dentry);
|
|---|
| 605 | ext4_directory_entry_ll_set_entry_length(tmp_dentry,
|
|---|
| 606 | tmp_dentry_length + del_entry_length);
|
|---|
| 607 | }
|
|---|
| 608 |
|
|---|
| 609 | result.block->dirty = true;
|
|---|
| 610 |
|
|---|
| 611 | return ext4_directory_destroy_result(&result);
|
|---|
| 612 | }
|
|---|
| 613 |
|
|---|
| 614 | /** Try to insert entry to concrete data block.
|
|---|
| 615 | *
|
|---|
| 616 | * @param sb Superblock
|
|---|
| 617 | * @param target_block Block to try to insert entry to
|
|---|
| 618 | * @param child Child i-node to be inserted by new entry
|
|---|
| 619 | * @param name Name of the new entry
|
|---|
| 620 | * @param name_len Length of the new entry name
|
|---|
| 621 | *
|
|---|
| 622 | * @return Error code
|
|---|
| 623 | *
|
|---|
| 624 | */
|
|---|
| 625 | int ext4_directory_try_insert_entry(ext4_superblock_t *sb,
|
|---|
| 626 | block_t *target_block, ext4_inode_ref_t *child, const char *name,
|
|---|
| 627 | uint32_t name_len)
|
|---|
| 628 | {
|
|---|
| 629 | /* Compute required length entry and align it to 4 bytes */
|
|---|
| 630 | uint32_t block_size = ext4_superblock_get_block_size(sb);
|
|---|
| 631 | uint16_t required_len = sizeof(ext4_fake_directory_entry_t) + name_len;
|
|---|
| 632 |
|
|---|
| 633 | if ((required_len % 4) != 0)
|
|---|
| 634 | required_len += 4 - (required_len % 4);
|
|---|
| 635 |
|
|---|
| 636 | /* Initialize pointers, stop means to upper bound */
|
|---|
| 637 | ext4_directory_entry_ll_t *dentry = target_block->data;
|
|---|
| 638 | ext4_directory_entry_ll_t *stop = target_block->data + block_size;
|
|---|
| 639 |
|
|---|
| 640 | /*
|
|---|
| 641 | * Walk through the block and check for invalid entries
|
|---|
| 642 | * or entries with free space for new entry
|
|---|
| 643 | */
|
|---|
| 644 | while (dentry < stop) {
|
|---|
| 645 | uint32_t inode = ext4_directory_entry_ll_get_inode(dentry);
|
|---|
| 646 | uint16_t rec_len = ext4_directory_entry_ll_get_entry_length(dentry);
|
|---|
| 647 |
|
|---|
| 648 | /* If invalid and large enough entry, use it */
|
|---|
| 649 | if ((inode == 0) && (rec_len >= required_len)) {
|
|---|
| 650 | ext4_directory_write_entry(sb, dentry, rec_len, child,
|
|---|
| 651 | name, name_len);
|
|---|
| 652 | target_block->dirty = true;
|
|---|
| 653 |
|
|---|
| 654 | return EOK;
|
|---|
| 655 | }
|
|---|
| 656 |
|
|---|
| 657 | /* Valid entry, try to split it */
|
|---|
| 658 | if (inode != 0) {
|
|---|
| 659 | uint16_t used_name_len =
|
|---|
| 660 | ext4_directory_entry_ll_get_name_length(sb, dentry);
|
|---|
| 661 |
|
|---|
| 662 | uint16_t used_space =
|
|---|
| 663 | sizeof(ext4_fake_directory_entry_t) + used_name_len;
|
|---|
| 664 |
|
|---|
| 665 | if ((used_name_len % 4) != 0)
|
|---|
| 666 | used_space += 4 - (used_name_len % 4);
|
|---|
| 667 |
|
|---|
| 668 | uint16_t free_space = rec_len - used_space;
|
|---|
| 669 |
|
|---|
| 670 | /* There is free space for new entry */
|
|---|
| 671 | if (free_space >= required_len) {
|
|---|
| 672 | /* Cut tail of current entry */
|
|---|
| 673 | ext4_directory_entry_ll_set_entry_length(dentry, used_space);
|
|---|
| 674 | ext4_directory_entry_ll_t *new_entry =
|
|---|
| 675 | (void *) dentry + used_space;
|
|---|
| 676 | ext4_directory_write_entry(sb, new_entry,
|
|---|
| 677 | free_space, child, name, name_len);
|
|---|
| 678 |
|
|---|
| 679 | target_block->dirty = true;
|
|---|
| 680 |
|
|---|
| 681 | return EOK;
|
|---|
| 682 | }
|
|---|
| 683 | }
|
|---|
| 684 |
|
|---|
| 685 | /* Jump to the next entry */
|
|---|
| 686 | dentry = (void *) dentry + rec_len;
|
|---|
| 687 | }
|
|---|
| 688 |
|
|---|
| 689 | /* No free space found for new entry */
|
|---|
| 690 | return ENOSPC;
|
|---|
| 691 | }
|
|---|
| 692 |
|
|---|
| 693 | /** Try to find entry in block by name.
|
|---|
| 694 | *
|
|---|
| 695 | * @param block Block containing entries
|
|---|
| 696 | * @param sb Superblock
|
|---|
| 697 | * @param name_len Length of entry name
|
|---|
| 698 | * @param name Name of entry to be found
|
|---|
| 699 | * @param res_entry Output pointer to found entry, NULL if not found
|
|---|
| 700 | *
|
|---|
| 701 | * @return Error code
|
|---|
| 702 | *
|
|---|
| 703 | */
|
|---|
| 704 | int ext4_directory_find_in_block(block_t *block, ext4_superblock_t *sb,
|
|---|
| 705 | size_t name_len, const char *name, ext4_directory_entry_ll_t **res_entry)
|
|---|
| 706 | {
|
|---|
| 707 | /* Start from the first entry in block */
|
|---|
| 708 | ext4_directory_entry_ll_t *dentry =
|
|---|
| 709 | (ext4_directory_entry_ll_t *) block->data;
|
|---|
| 710 |
|
|---|
| 711 | /* Set upper bound for cycling */
|
|---|
| 712 | uint8_t *addr_limit = block->data + ext4_superblock_get_block_size(sb);
|
|---|
| 713 |
|
|---|
| 714 | /* Walk through the block and check entries */
|
|---|
| 715 | while ((uint8_t *) dentry < addr_limit) {
|
|---|
| 716 | /* Termination condition */
|
|---|
| 717 | if ((uint8_t *) dentry + name_len > addr_limit)
|
|---|
| 718 | break;
|
|---|
| 719 |
|
|---|
| 720 | /* Valid entry - check it */
|
|---|
| 721 | if (dentry->inode != 0) {
|
|---|
| 722 | /* For more effectivity compare firstly only lengths */
|
|---|
| 723 | if (ext4_directory_entry_ll_get_name_length(sb, dentry) ==
|
|---|
| 724 | name_len) {
|
|---|
| 725 | /* Compare names */
|
|---|
| 726 | if (bcmp((uint8_t *) name, dentry->name, name_len) == 0) {
|
|---|
| 727 | *res_entry = dentry;
|
|---|
| 728 | return EOK;
|
|---|
| 729 | }
|
|---|
| 730 | }
|
|---|
| 731 | }
|
|---|
| 732 |
|
|---|
| 733 | uint16_t dentry_len =
|
|---|
| 734 | ext4_directory_entry_ll_get_entry_length(dentry);
|
|---|
| 735 |
|
|---|
| 736 | /* Corrupted entry */
|
|---|
| 737 | if (dentry_len == 0)
|
|---|
| 738 | return EINVAL;
|
|---|
| 739 |
|
|---|
| 740 | /* Jump to next entry */
|
|---|
| 741 | dentry = (ext4_directory_entry_ll_t *) ((uint8_t *) dentry + dentry_len);
|
|---|
| 742 | }
|
|---|
| 743 |
|
|---|
| 744 | /* Entry not found */
|
|---|
| 745 | return ENOENT;
|
|---|
| 746 | }
|
|---|
| 747 |
|
|---|
| 748 | /** Simple function to release allocated data from result.
|
|---|
| 749 | *
|
|---|
| 750 | * @param result Search result to destroy
|
|---|
| 751 | *
|
|---|
| 752 | * @return Error code
|
|---|
| 753 | *
|
|---|
| 754 | */
|
|---|
| 755 | int ext4_directory_destroy_result(ext4_directory_search_result_t *result)
|
|---|
| 756 | {
|
|---|
| 757 | if (result->block)
|
|---|
| 758 | return block_put(result->block);
|
|---|
| 759 |
|
|---|
| 760 | return EOK;
|
|---|
| 761 | }
|
|---|
| 762 |
|
|---|
| 763 | /**
|
|---|
| 764 | * @}
|
|---|
| 765 | */
|
|---|