Changeset 7bc4508 in mainline


Ignore:
Timestamp:
2011-10-18T19:58:36Z (13 years ago)
Author:
Frantisek Princ <frantisek.princ@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
7bd2c19
Parents:
12f55220
Message:

First part of reading htree directory index - the most important functionality (computing hashes) still missing

Location:
uspace
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • uspace/lib/ext4/libext4_directory.c

    r12f55220 r7bc4508  
    6666}
    6767
     68uint8_t ext4_directory_dx_root_info_get_hash_version(ext4_directory_dx_root_info_t *root_info)
     69{
     70        return root_info->hash_version;
     71}
     72
     73uint8_t ext4_directory_dx_root_info_get_info_length(ext4_directory_dx_root_info_t *root_info)
     74{
     75        return root_info->info_length;
     76}
     77
     78uint8_t ext4_directory_dx_root_info_get_indirect_levels(ext4_directory_dx_root_info_t *root_info)
     79{
     80        return root_info->indirect_levels;
     81}
     82
     83uint16_t ext4_directory_dx_countlimit_get_limit(ext4_directory_dx_countlimit_t *countlimit)
     84{
     85        return uint16_t_le2host(countlimit->limit);
     86}
     87uint16_t ext4_directory_dx_countlimit_get_count(ext4_directory_dx_countlimit_t *countlimit)
     88{
     89        return uint16_t_le2host(countlimit->count);
     90}
     91
     92uint32_t ext4_directory_dx_entry_get_hash(ext4_directory_dx_entry_t *entry)
     93{
     94        return uint32_t_le2host(entry->hash);
     95}
     96
     97uint32_t ext4_directory_dx_entry_get_block(ext4_directory_dx_entry_t *entry)
     98{
     99        return uint32_t_le2host(entry->block);
     100}
     101
     102
     103
    68104int ext4_directory_iterator_init(ext4_directory_iterator_t *it,
    69105    ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, aoff64_t pos)
    … …  
    209245}
    210246
     247int ext4_directory_dx_find_entry(ext4_directory_iterator_t *it,
     248                ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, const char *name)
     249{
     250        int rc;
     251        uint32_t fblock;
     252        block_t *phys_block;
     253        ext4_directory_dx_root_t *root;
     254        uint32_t hash;
     255        ext4_directory_dx_hash_info_t hinfo;
     256
     257        // get direct block 0 (index root)
     258        rc = ext4_filesystem_get_inode_data_block_index(fs, inode_ref->inode, 0, &fblock);
     259        if (rc != EOK) {
     260                return rc;
     261        }
     262
     263        rc = block_get(&phys_block, fs->device, fblock, BLOCK_FLAGS_NONE);
     264        if (rc != EOK) {
     265                it->current_block = NULL;
     266                        return rc;
     267        }
     268
     269        // Now having index root
     270        root = (ext4_directory_dx_root_t *)phys_block->data;
     271
     272        // Check hash version - only if supported
     273        EXT4FS_DBG("hash_version = \%u", root->info.hash_version);
     274
     275        // Check unused flags
     276        if (root->info.unused_flags != 0) {
     277                EXT4FS_DBG("ERR: unused_flags = \%u", root->info.unused_flags);
     278                block_put(phys_block);
     279                return EXT4_ERR_BAD_DX_DIR;
     280        }
     281
     282        // Check indirect levels
     283        if (root->info.indirect_levels > 1) {
     284                EXT4FS_DBG("ERR: indirect_levels = \%u", root->info.indirect_levels);
     285                block_put(phys_block);
     286                return EXT4_ERR_BAD_DX_DIR;
     287        }
     288
     289        uint32_t bs = ext4_superblock_get_block_size(fs->superblock);
     290
     291        uint32_t entry_space = bs - 2* sizeof(ext4_directory_dx_dot_entry_t) - sizeof(ext4_directory_dx_root_info_t);
     292    entry_space = entry_space / sizeof(ext4_directory_dx_entry_t);
     293
     294
     295    uint32_t limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)&root->entries);
     296    uint32_t count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)&root->entries);
     297
     298    if (limit != entry_space) {
     299                block_put(phys_block);
     300        return EXT4_ERR_BAD_DX_DIR;
     301        }
     302
     303        if ((count == 0) || (count > limit)) {
     304                block_put(phys_block);
     305                return EXT4_ERR_BAD_DX_DIR;
     306        }
     307
     308        /* DEBUG list
     309    for (uint16_t i = 0; i < count; ++i) {
     310        uint32_t hash = ext4_directory_dx_entry_get_hash(&root->entries[i]);
     311        uint32_t block = ext4_directory_dx_entry_get_block(&root->entries[i]);
     312        EXT4FS_DBG("hash = \%u, block = \%u", hash, block);
     313    }
     314    */
     315
     316        hinfo.hash_version = ext4_directory_dx_root_info_get_hash_version(&root->info);
     317        if ((hinfo.hash_version <= EXT4_DIRECTORY_DX_HASH_TEA)
     318                        && (ext4_superblock_has_flag(fs->superblock, EXT4_SUPERBLOCK_FLAGS_UNSIGNED_HASH))) {
     319                // 3 is magic from ext4 linux implementation
     320                hinfo.hash_version += 3;
     321        }
     322
     323        hinfo.seed = ext4_superblock_get_hash_seed(fs->superblock);
     324        hinfo.hash = 0;
     325        if (name) {
     326                ext4_directory_hash(&hinfo, name);
     327        }
     328
     329        hash = hinfo.hash;
     330
     331        ext4_directory_dx_entry_t *p, *q, *m;
     332
     333        // TODO cycle
     334        // while (true)
     335
     336                p = &root->entries[1];
     337                q = &root->entries[count - 1];
     338
     339                while (p <= q) {
     340                        m = p + (q - p) / 2;
     341                        if (ext4_directory_dx_entry_get_hash(m) > hash) {
     342                                q = m - 1;
     343                        } else {
     344                                p = m + 1;
     345                        }
     346                }
     347
     348                /* TODO move to leaf or next node
     349                at = p - 1;
     350                dxtrace(printk(" %x->%u\n", at == entries? 0: dx_get_hash(at), dx_get_block(at)));
     351        frame->bh = bh;
     352        frame->entries = entries;
     353        frame->at = at;
     354
     355        if (indirect == 0) {
     356                        // TODO write return values !!!
     357                return EOK;
     358        }
     359
     360        indirect--;
     361
     362                // TODO read next block
     363                if (!(bh = ext4_bread (NULL,dir, dx_get_block(at), 0, err)))
     364                        goto fail2;
     365                at = entries = ((struct dx_node *) bh->b_data)->entries;
     366                if (dx_get_limit(entries) != dx_node_limit (dir)) {
     367                ext4_warning(dir->i_sb, "dx entry: limit != node limit");
     368                        brelse(bh);
     369            *err = ERR_BAD_DX_DIR;
     370                        goto fail2;
     371                }
     372                frame++;
     373                frame->bh = NULL;
     374                 */
     375
     376        // } END WHILE
     377
     378
     379        // TODO delete it !!!
     380        return EXT4_ERR_BAD_DX_DIR;
     381
     382        if ((it->current == NULL) || (it->current->inode == 0)) {
     383                        return ENOENT;
     384        }
     385
     386        return EOK;
     387}
     388
     389void ext4_directory_hash(ext4_directory_dx_hash_info_t *hinfo, const char* name)
     390{
     391        // TODO
     392}
    211393
    212394/**

  • uspace/lib/ext4/libext4_directory.h

    r12f55220 r7bc4508  
    6464/* Structures for indexed directory */
    6565
     66typedef struct ext4_directory_dx_countlimit {
     67        uint16_t limit;
     68    uint16_t count;
     69} ext4_directory_dx_countlimit_t;
     70
    6671typedef struct ext4_directory_dx_dot_entry {
    6772        uint32_t inode;
    … …  
    8792typedef struct ext4_directory_dx_root {
    8893                ext4_directory_dx_dot_entry_t dots[2];
    89                 // TODO insert root info items instead of special datatype
    9094                ext4_directory_dx_root_info_t info;
    91                 ext4_directory_dx_entry_t *entries;
     95                ext4_directory_dx_entry_t entries[0];
    9296} ext4_directory_dx_root_t;
    9397
     98typedef struct ext4_directory_dx_hash_info {
     99        uint32_t hash;
     100        uint32_t minor_hash;
     101        uint32_t hash_version;
     102        uint32_t *seed;
     103} ext4_directory_dx_hash_info_t;
    94104
    95 #define EXT4_DIRECTORY_HTREE_EOF  0x7fffffff
     105
     106#define EXT4_ERR_BAD_DX_DIR                     (-75000)
     107
     108#define EXT4_DIRECTORY_DX_HASH_LEGACY                           0
     109#define EXT4_DIRECTORY_DX_HASH_HALF_MD4                         1
     110#define EXT4_DIRECTORY_DX_HASH_TEA                                      2
     111#define EXT4_DIRECTORY_DX_HASH_LEGACY_UNSIGNED          3
     112#define EXT4_DIRECTORY_DX_HASH_HALF_MD4_UNSIGNED        4
     113#define EXT4_DIRECTORY_DX_HASH_TEA_UNSIGNED                     5
     114
     115#define EXT4_DIRECTORY_HTREE_EOF        0x7fffffff
    96116
    97117
    … …  
    102122    ext4_superblock_t *, ext4_directory_entry_ll_t *);
    103123
     124extern uint8_t ext4_directory_dx_root_info_get_hash_version(ext4_directory_dx_root_info_t *);
     125extern uint8_t ext4_directory_dx_root_info_get_info_length(ext4_directory_dx_root_info_t *);
     126extern uint8_t ext4_directory_dx_root_info_get_indirect_levels(ext4_directory_dx_root_info_t *);
     127
     128extern uint16_t ext4_directory_dx_countlimit_get_limit(ext4_directory_dx_countlimit_t *);
     129extern uint16_t ext4_directory_dx_countlimit_get_count(ext4_directory_dx_countlimit_t *);
     130
     131extern uint32_t ext4_directory_dx_entry_get_hash(ext4_directory_dx_entry_t *);
     132extern uint32_t ext4_directory_dx_entry_get_block(ext4_directory_dx_entry_t *);
     133
    104134extern int ext4_directory_iterator_init(ext4_directory_iterator_t *,
    105135                ext4_filesystem_t *, ext4_inode_ref_t *, aoff64_t);
    … …  
    107137extern int ext4_directory_iterator_seek(ext4_directory_iterator_t *, aoff64_t pos);
    108138extern int ext4_directory_iterator_fini(ext4_directory_iterator_t *);
     139extern int ext4_directory_dx_find_entry(ext4_directory_iterator_t *,
     140                ext4_filesystem_t *, ext4_inode_ref_t *, const char *);
     141
     142extern void ext4_directory_hash(ext4_directory_dx_hash_info_t *, const char* name);
    109143
    110144#endif

  • uspace/lib/ext4/libext4_inode.c

    r12f55220 r7bc4508  
    176176
    177177// Flags checker
    178 bool ext4_inode_has_flag(ext4_inode_t *inode, uint32_t flag) {
     178bool ext4_inode_has_flag(ext4_inode_t *inode, uint32_t flag)
     179{
    179180        if (ext4_inode_get_flags(inode) & flag) {
    180181                return true;

  • uspace/lib/ext4/libext4_superblock.c

    r12f55220 r7bc4508  
    185185
    186186
     187uint32_t* ext4_superblock_get_hash_seed(ext4_superblock_t *sb)
     188{
     189        return sb->hash_seed;
     190}
     191
     192uint32_t ext4_superblock_get_flags(ext4_superblock_t *sb)
     193{
     194        return uint32_t_le2host(sb->flags);
     195}
     196
     197
    187198/*
    188199 * More complex superblock functions
    189200 */
    190201
     202bool ext4_superblock_has_flag(ext4_superblock_t *sb, uint32_t flag)
     203{
     204        if (ext4_superblock_get_flags(sb) & flag) {
     205                return true;
     206        }
     207        return false;
     208}
     209
    191210int ext4_superblock_read_direct(service_id_t service_id,
    192211    ext4_superblock_t **superblock)

  • uspace/lib/ext4/libext4_superblock.h

    r12f55220 r7bc4508  
    109109        uint16_t min_extra_isize; // All inodes have at least # bytes
    110110        uint16_t want_extra_isize; // New inodes should reserve # bytes
    111         uint32_t lags; // Miscellaneous flags
     111        uint32_t flags; // Miscellaneous flags
    112112        uint16_t raid_stride; // RAID stride
    113113        uint16_t mmp_interval; // # seconds to wait in MMP checking
    … …  
    144144#define EXT4_SUPERBLOCK_OS_HURD         1
    145145
     146/*
     147 * Misc. filesystem flags
     148 */
     149#define EXT4_SUPERBLOCK_FLAGS_SIGNED_HASH       0x0001  /* Signed dirhash in use */
     150#define EXT4_SUPERBLOCK_FLAGS_UNSIGNED_HASH     0x0002  /* Unsigned dirhash in use */
     151#define EXT4_SUPERBLOCK_FLAGS_TEST_FILESYS      0x0004  /* to test development code */
     152
     153
    146154extern uint32_t ext4_superblock_get_inodes_count(ext4_superblock_t *);
    147155extern uint64_t ext4_superblock_get_blocks_count(ext4_superblock_t *);
    … …  
    191199uint32_t s_journal_dev; // Device number of journal file
    192200uint32_t s_last_orphan; // Head of list of inodes to delete
    193 uint32_t s_hash_seed[4]; // HTREE hash seed
     201*/
     202extern uint32_t* ext4_superblock_get_hash_seed(ext4_superblock_t *);
     203
     204/*
    194205uint8_t s_def_hash_version; // Default hash version to use
    195206uint8_t s_jnl_backup_type;
    … …  
    201212uint16_t s_min_extra_isize; // All inodes have at least # bytes
    202213uint16_t s_want_extra_isize; // New inodes should reserve # bytes
    203 uint32_t s_flags; // Miscellaneous flags
     214*/
     215extern uint32_t ext4_superblock_get_flags(ext4_superblock_t *);
     216/*
    204217uint16_t s_raid_stride; // RAID stride
    205218uint16_t s_mmp_interval; // # seconds to wait in MMP checking
    … …  
    229242
    230243/* More complex superblock functions */
     244extern bool ext4_superblock_has_flag(ext4_superblock_t *, uint32_t);
    231245extern int ext4_superblock_read_direct(service_id_t, ext4_superblock_t **);
    232246extern int ext4_superblock_check_sanity(ext4_superblock_t *);

  • uspace/srv/fs/ext4fs/ext4fs_ops.c

    r12f55220 r7bc4508  
    7575static int ext4fs_read_directory(ipc_callid_t, aoff64_t, size_t,
    7676    ext4fs_instance_t *, ext4_inode_ref_t *, size_t *);
    77 static int ext4fs_read_dx_directory(ipc_callid_t, aoff64_t, size_t,
    78     ext4fs_instance_t *, ext4_inode_ref_t *, size_t *);
    7977static int ext4fs_read_file(ipc_callid_t, aoff64_t, size_t, ext4fs_instance_t *,
    8078    ext4_inode_ref_t *, size_t *);
    … …  
    216214            EXT4_INODE_MODE_DIRECTORY)) {
    217215                return ENOTDIR;
     216        }
     217
     218        // TODO check super block COMPAT FEATURES
     219        if (ext4_inode_has_flag(eparent->inode_ref->inode, EXT4_INODE_FLAG_INDEX)) {
     220
     221                rc = ext4_directory_dx_find_entry(&it, fs, eparent->inode_ref, component);
     222
     223                // Index isn't corrupted
     224                if (rc != EXT4_ERR_BAD_DX_DIR) {
     225
     226                        // TODO check return value
     227                        if (rc != EOK) {
     228                                return rc;
     229                        }
     230
     231                        inode = ext4_directory_entry_ll_get_inode(it.current);
     232                        return ext4fs_node_get_core(rfn, eparent->instance, inode);
     233                }
     234
    218235        }
    219236
    … …  
    748765        bool found = false;
    749766
    750         // TODO check super block COMPAT FEATURES
    751         if (ext4_inode_has_flag(inode_ref->inode, EXT4_INODE_FLAG_INDEX)) {
    752                 rc = ext4fs_read_dx_directory(callid, pos, size, inst, inode_ref, rbytes);
    753                 // TODO return...
    754                 // return rc;
    755         }
    756 
    757767        rc = ext4_directory_iterator_init(&it, inst->filesystem, inode_ref, pos);
    758768        if (rc != EOK) {
    … …  
    825835                return ENOENT;
    826836        }
    827 }
    828 
    829 int ext4fs_read_dx_directory(ipc_callid_t callid, aoff64_t pos, size_t size,
    830     ext4fs_instance_t *inst, ext4_inode_ref_t *inode_ref, size_t *rbytes)
    831 {
    832         EXT4FS_DBG("Directory using HTree index");
    833         return ENOTSUP;
    834837}
    835838
Note: See TracChangeset for help on using the changeset viewer.