Changeset 0dc91833 in mainline


Ignore:
Timestamp:
2011-10-26T11:41:21Z (12 years ago)
Author:
Frantisek Princ <frantisek.princ@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
bf9da656
Parents:
ab77928
Message:

splitted code because of very long source file

Location:
uspace
Files:
2 added
6 edited

Legend:

Unmodified
Added
Removed
  • uspace/lib/ext4/Makefile

    rab77928 r0dc91833  
    3535        libext4_block_group.c \
    3636        libext4_directory.c \
     37        libext4_directory_index.c \
    3738        libext4_extent.c \
    3839        libext4_filesystem.c \
  • uspace/lib/ext4/libext4.h

    rab77928 r0dc91833  
    3636#include "libext4_block_group.h"
    3737#include "libext4_directory.h"
     38#include "libext4_directory_index.h"
    3839#include "libext4_extent.h"
    3940#include "libext4_filesystem.h"
  • uspace/lib/ext4/libext4_directory.c

    rab77928 r0dc91833  
    246246
    247247
    248 static int ext4_directory_hinfo_init(ext4_hash_info_t *hinfo, block_t *root_block,
    249                 ext4_superblock_t *sb, size_t name_len, const char *name)
    250 {
    251         uint32_t block_size, entry_space;
    252         uint16_t limit;
    253         ext4_directory_dx_root_t *root;
    254 
    255         root = (ext4_directory_dx_root_t *)root_block->data;
    256 
    257         if (root->info.hash_version != EXT4_HASH_VERSION_TEA &&
    258                         root->info.hash_version != EXT4_HASH_VERSION_HALF_MD4 &&
    259                         root->info.hash_version != EXT4_HASH_VERSION_LEGACY) {
    260                 return EXT4_ERR_BAD_DX_DIR;
    261         }
    262 
    263         // Check unused flags
    264         if (root->info.unused_flags != 0) {
    265                 EXT4FS_DBG("ERR: unused_flags = \%u", root->info.unused_flags);
    266                 return EXT4_ERR_BAD_DX_DIR;
    267         }
    268 
    269         // Check indirect levels
    270         if (root->info.indirect_levels > 1) {
    271                 EXT4FS_DBG("ERR: indirect_levels = \%u", root->info.indirect_levels);
    272                 return EXT4_ERR_BAD_DX_DIR;
    273         }
    274 
    275         block_size = ext4_superblock_get_block_size(sb);
    276 
    277         entry_space = block_size;
    278         entry_space -= 2 * sizeof(ext4_directory_dx_dot_entry_t);
    279         entry_space -= sizeof(ext4_directory_dx_root_info_t);
    280     entry_space = entry_space / sizeof(ext4_directory_dx_entry_t);
    281 
    282     limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)&root->entries);
    283     if (limit != entry_space) {
    284         return EXT4_ERR_BAD_DX_DIR;
    285         }
    286 
    287         hinfo->hash_version = ext4_directory_dx_root_info_get_hash_version(&root->info);
    288         if ((hinfo->hash_version <= EXT4_HASH_VERSION_TEA)
    289                         && (ext4_superblock_has_flag(sb, EXT4_SUPERBLOCK_FLAGS_UNSIGNED_HASH))) {
    290                 // 3 is magic from ext4 linux implementation
    291                 hinfo->hash_version += 3;
    292         }
    293 
    294         hinfo->seed = ext4_superblock_get_hash_seed(sb);
    295 
    296         if (name) {
    297                 ext4_hash_string(hinfo, name_len, name);
    298         }
    299 
    300         return EOK;
    301 }
    302 
    303 static int ext4_directory_dx_get_leaf(ext4_hash_info_t *hinfo,
    304                 ext4_filesystem_t *fs, ext4_inode_t *inode, block_t *root_block,
    305                 ext4_directory_dx_handle_t **handle, ext4_directory_dx_handle_t *handles)
    306 {
    307         int rc;
    308         uint16_t count, limit, entry_space;
    309         uint8_t indirect_level;
    310         ext4_directory_dx_root_t *root;
    311         ext4_directory_dx_entry_t *p, *q, *m, *at;
    312         ext4_directory_dx_entry_t *entries;
    313         block_t *tmp_block = root_block;
    314         uint32_t fblock, next_block;
    315         ext4_directory_dx_handle_t *tmp_handle = handles;
    316 
    317         root = (ext4_directory_dx_root_t *)root_block->data;
    318         entries = (ext4_directory_dx_entry_t *)&root->entries;
    319 
    320         limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)entries);
    321         indirect_level = ext4_directory_dx_root_info_get_indirect_levels(&root->info);
    322 
    323         while (true) {
    324 
    325                 count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)entries);
    326                 if ((count == 0) || (count > limit)) {
    327                         return EXT4_ERR_BAD_DX_DIR;
    328                 }
    329 
    330                 p = entries + 1;
    331                 q = entries + count - 1;
    332 
    333                 while (p <= q) {
    334                         m = p + (q - p) / 2;
    335                         if (ext4_directory_dx_entry_get_hash(m) > hinfo->hash) {
    336                                 q = m - 1;
    337                         } else {
    338                                 p = m + 1;
    339                         }
    340                 }
    341 
    342                 at = p - 1;
    343 
    344                 tmp_handle->block = tmp_block;
    345                 tmp_handle->entries = entries;
    346                 tmp_handle->position = at;
    347 
    348         if (indirect_level == 0) {
    349                 *handle = tmp_handle;
    350                 return EOK;
    351         }
    352 
    353                 next_block = ext4_directory_dx_entry_get_block(at);
    354 
    355         indirect_level--;
    356 
    357         rc = ext4_filesystem_get_inode_data_block_index(fs, inode, next_block, &fblock);
    358         if (rc != EOK) {
    359                 return rc;
    360         }
    361 
    362         rc = block_get(&tmp_block, fs->device, fblock, BLOCK_FLAGS_NONE);
    363         if (rc != EOK) {
    364                 return rc;
    365         }
    366 
    367                 entries = ((ext4_directory_dx_node_t *) tmp_block->data)->entries;
    368                 limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)entries);
    369 
    370         entry_space = ext4_superblock_get_block_size(fs->superblock) - sizeof(ext4_directory_dx_dot_entry_t);
    371         entry_space = entry_space / sizeof(ext4_directory_dx_entry_t);
    372 
    373 
    374                 if (limit != entry_space) {
    375                         block_put(tmp_block);
    376                 return EXT4_ERR_BAD_DX_DIR;
    377                 }
    378 
    379                 ++tmp_handle;
    380         }
    381 
    382         // Unreachable
    383         return EOK;
    384 }
    385 
    386 
    387 static int ext4_dirextory_dx_find_dir_entry(block_t *block,
    388                 ext4_superblock_t *sb, size_t name_len, const char *name,
    389                 ext4_directory_entry_ll_t **res_entry, aoff64_t *block_offset)
    390 {
    391         ext4_directory_entry_ll_t *dentry;
    392         uint16_t dentry_len;
    393         uint8_t *addr_limit;
    394         aoff64_t offset = 0;
    395 
    396         dentry = (ext4_directory_entry_ll_t *)block->data;
    397         addr_limit = block->data + ext4_superblock_get_block_size(sb);
    398 
    399         while ((uint8_t *)dentry < addr_limit) {
    400 
    401                 if ((uint8_t*) dentry + name_len > addr_limit) {
    402                         break;
    403                 }
    404 
    405                 if (dentry->inode != 0) {
    406                         if (name_len == ext4_directory_entry_ll_get_name_length(sb, dentry)) {
    407                                 // Compare names
    408                                 if (bcmp((uint8_t *)name, dentry->name, name_len) == 0) {
    409                                         *block_offset = offset;
    410                                         *res_entry = dentry;
    411                                         return 1;
    412                                 }
    413                         }
    414                 }
    415 
    416 
    417                 // Goto next entry
    418                 dentry_len = ext4_directory_entry_ll_get_entry_length(dentry);
    419 
    420         if (dentry_len == 0) {
    421                 // TODO error
    422                 return -1;
    423         }
    424 
    425                 offset += dentry_len;
    426                 dentry = (ext4_directory_entry_ll_t *)((uint8_t *)dentry + dentry_len);
    427         }
    428 
    429         return 0;
    430 }
    431 
    432 static int ext4_directory_dx_next_block(ext4_filesystem_t *fs, ext4_inode_t *inode, uint32_t hash,
    433                 ext4_directory_dx_handle_t *handle, ext4_directory_dx_handle_t *handles)
    434 {
    435         ext4_directory_dx_handle_t *p;
    436         uint16_t count;
    437         uint32_t num_handles;
    438         uint32_t current_hash;
    439         block_t *block;
    440         uint32_t block_addr, block_idx;
    441     int rc;
    442 
    443     num_handles = 0;
    444     p = handle;
    445 
    446     while (1) {
    447 
    448         p->position++;
    449         count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)p->entries);
    450 
    451         if (p->position < p->entries + count) {
    452                 break;
    453         }
    454 
    455         if (p == handles) {
    456                 return 0;
    457         }
    458 
    459         num_handles++;
    460         p--;
    461     }
    462 
    463     current_hash = ext4_directory_dx_entry_get_hash(p->position);
    464 
    465     if ((hash & 1) == 0) {
    466         if ((current_hash & ~1) != hash) {
    467                 return 0;
    468         }
    469     }
    470 
    471     while (num_handles--) {
    472 
    473         block_idx = ext4_directory_dx_entry_get_block(p->position);
    474         rc = ext4_filesystem_get_inode_data_block_index(fs, inode, block_idx, &block_addr);
    475         if (rc != EOK) {
    476                 return rc;
    477         }
    478 
    479         rc = block_get(&block, fs->device, block_addr, BLOCK_FLAGS_NONE);
    480         if (rc != EOK) {
    481                 return rc;
    482         }
    483 
    484         p++;
    485 
    486         block_put(p->block);
    487         p->block = block;
    488         p->entries = ((ext4_directory_dx_node_t *) block->data)->entries;
    489         p->position = p->entries;
    490     }
    491 
    492     return 1;
    493 
    494 }
    495 
    496 int ext4_directory_dx_find_entry(ext4_directory_iterator_t *it,
    497                 ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, size_t len, const char *name)
    498 {
    499         int rc;
    500         uint32_t root_block_addr, leaf_block_addr, leaf_block_idx;
    501         aoff64_t block_offset;
    502         block_t *root_block, *leaf_block;
    503         ext4_hash_info_t hinfo;
    504         ext4_directory_entry_ll_t *res_dentry;
    505         // TODO better names
    506         ext4_directory_dx_handle_t handles[2], *handle;
    507 
    508         // get direct block 0 (index root)
    509         rc = ext4_filesystem_get_inode_data_block_index(fs, inode_ref->inode, 0, &root_block_addr);
    510         if (rc != EOK) {
    511                 return rc;
    512         }
    513 
    514         rc = block_get(&root_block, fs->device, root_block_addr, BLOCK_FLAGS_NONE);
    515         if (rc != EOK) {
    516                 it->current_block = NULL;
    517                 return rc;
    518         }
    519 
    520         rc = ext4_directory_hinfo_init(&hinfo, root_block, fs->superblock, len, name);
    521         if (rc != EOK) {
    522                 block_put(root_block);
    523                 return EXT4_ERR_BAD_DX_DIR;
    524         }
    525 
    526         rc = ext4_directory_dx_get_leaf(&hinfo, fs, inode_ref->inode, root_block, &handle, handles);
    527         if (rc != EOK) {
    528                 block_put(root_block);
    529                 return EXT4_ERR_BAD_DX_DIR;
    530         }
    531 
    532         do {
    533 
    534                 leaf_block_idx = ext4_directory_dx_entry_get_block(handle->position);
    535 
    536         rc = ext4_filesystem_get_inode_data_block_index(fs, inode_ref->inode, leaf_block_idx, &leaf_block_addr);
    537         if (rc != EOK) {
    538                 return EXT4_ERR_BAD_DX_DIR;
    539         }
    540 
    541                 rc = block_get(&leaf_block, fs->device, leaf_block_addr, BLOCK_FLAGS_NONE);
    542                 if (rc != EOK) {
    543                         return EXT4_ERR_BAD_DX_DIR;
    544                 }
    545 
    546                 rc = ext4_dirextory_dx_find_dir_entry(leaf_block, fs->superblock, len, name,
    547                                 &res_dentry, &block_offset);
    548 
    549                 // Found => return it
    550                 if (rc == 1) {
    551                         it->fs = fs;
    552                         it->inode_ref = inode_ref;
    553                         it->current_block = leaf_block;
    554                         it->current_offset = block_offset;
    555                         it->current = res_dentry;
    556                         return EOK;
    557                 }
    558 
    559                 block_put(leaf_block);
    560 
    561                 // ERROR - corrupted index
    562                 if (rc == -1) {
    563                         // TODO cleanup
    564                         return EXT4_ERR_BAD_DX_DIR;
    565                 }
    566 
    567                 rc = ext4_directory_dx_next_block(fs, inode_ref->inode, hinfo.hash, handle, &handles[0]);
    568                 if (rc < 0) {
    569                         // TODO cleanup
    570                         return EXT4_ERR_BAD_DX_DIR;
    571                 }
    572 
    573         } while (rc == 1);
    574 
    575         return ENOENT;
    576 }
    577248
    578249
  • uspace/lib/ext4/libext4_directory.h

    rab77928 r0dc91833  
    6262
    6363
    64 /* Structures for indexed directory */
    65 
    66 typedef struct ext4_directory_dx_countlimit {
    67         uint16_t limit;
    68     uint16_t count;
    69 } ext4_directory_dx_countlimit_t;
    70 
    71 typedef struct ext4_directory_dx_dot_entry {
    72         uint32_t inode;
    73         uint16_t entry_length;
    74     uint8_t name_length;
    75     uint8_t inode_type;
    76     uint8_t name[4];
    77 } ext4_directory_dx_dot_entry_t;
    78 
    79 typedef struct ext4_directory_dx_root_info {
    80         uint32_t reserved_zero;
    81         uint8_t hash_version;
    82         uint8_t info_length;
    83         uint8_t indirect_levels;
    84         uint8_t unused_flags;
    85 } ext4_directory_dx_root_info_t;
    86 
    87 typedef struct ext4_directory_dx_entry {
    88         uint32_t hash;
    89         uint32_t block;
    90 } ext4_directory_dx_entry_t;
    91 
    92 typedef struct ext4_directory_dx_root {
    93                 ext4_directory_dx_dot_entry_t dots[2];
    94                 ext4_directory_dx_root_info_t info;
    95                 ext4_directory_dx_entry_t entries[0];
    96 } ext4_directory_dx_root_t;
    97 
    98 typedef struct ext4_directory_dx_node {
    99         struct fake_directory_entry {
    100                 uint32_t inode;
    101                 uint16_t entry_length;
    102             uint8_t name_length;
    103             uint8_t inode_type;
    104         } fake;
    105         ext4_directory_dx_entry_t entries[0];
    106 } ext4_directory_dx_node_t;
    107 
    108 
    109 typedef struct ext4_directory_dx_handle {
    110         block_t *block;
    111         ext4_directory_dx_entry_t *entries;
    112         ext4_directory_dx_entry_t *position;
    113 } ext4_directory_dx_handle_t;
    114 
    115 
    116 
    117 #define EXT4_ERR_BAD_DX_DIR                     (-75000)
    118 #define EXT4_DIRECTORY_HTREE_EOF        (uint32_t)0x7fffffff
    119 
    120 
    12164extern uint32_t ext4_directory_entry_ll_get_inode(ext4_directory_entry_ll_t *);
    12265extern uint16_t ext4_directory_entry_ll_get_entry_length(
     
    12568    ext4_superblock_t *, ext4_directory_entry_ll_t *);
    12669
    127 extern uint8_t ext4_directory_dx_root_info_get_hash_version(ext4_directory_dx_root_info_t *);
    128 extern uint8_t ext4_directory_dx_root_info_get_info_length(ext4_directory_dx_root_info_t *);
    129 extern uint8_t ext4_directory_dx_root_info_get_indirect_levels(ext4_directory_dx_root_info_t *);
    130 
    131 extern uint16_t ext4_directory_dx_countlimit_get_limit(ext4_directory_dx_countlimit_t *);
    132 extern uint16_t ext4_directory_dx_countlimit_get_count(ext4_directory_dx_countlimit_t *);
    133 
    134 extern uint32_t ext4_directory_dx_entry_get_hash(ext4_directory_dx_entry_t *);
    135 extern uint32_t ext4_directory_dx_entry_get_block(ext4_directory_dx_entry_t *);
    136 
    13770extern int ext4_directory_iterator_init(ext4_directory_iterator_t *,
    13871                ext4_filesystem_t *, ext4_inode_ref_t *, aoff64_t);
     
    14073extern int ext4_directory_iterator_seek(ext4_directory_iterator_t *, aoff64_t pos);
    14174extern int ext4_directory_iterator_fini(ext4_directory_iterator_t *);
    142 extern int ext4_directory_dx_find_entry(ext4_directory_iterator_t *,
    143                 ext4_filesystem_t *, ext4_inode_ref_t *, size_t, const char *);
    14475
    14576#endif
  • uspace/lib/ext4/libext4_hash.c

    rab77928 r0dc91833  
    236236    void (*str2hashbuf)(const char *, int, uint32_t *, int) = str2hashbuf_signed;
    237237
    238     /*
    239     for (i = 0; i < 8; ++i) {
    240         in[i] = 0;
    241     }
    242     */
    243 
    244238    /* Initialize the default seed for the hash checksum functions */
    245239        buf[0] = 0x67452301;
  • uspace/srv/fs/ext4fs/ext4fs_ops.c

    rab77928 r0dc91833  
    232232                if (rc != EXT4_ERR_BAD_DX_DIR) {
    233233
    234                         // TODO check return value
    235234                        if (rc != EOK) {
    236235                                return rc;
Note: See TracChangeset for help on using the changeset viewer.