Fork us on GitHub Follow us on Facebook Follow us on Twitter

Changeset 246a5af in mainline


Ignore:
Timestamp:
2011-10-19T18:54:41Z (9 years ago)
Author:
Frantisek Princ <frantisek.princ@…>
Branches:
master
Children:
36d2c6f
Parents:
8158db7
Message:

htree leaf block searching complete - directory entry find process remaining

Location:
uspace/lib/ext4
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • uspace/lib/ext4/libext4_directory.c

    r8158db7 r246a5af  
    245245}
    246246
    247 int ext4_directory_dx_find_entry(ext4_directory_iterator_t *it,
    248                 ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, size_t len, const char *name)
    249 {
    250         int rc;
    251         uint32_t fblock;
    252         block_t *phys_block;
     247
     248static 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;
    253253        ext4_directory_dx_root_t *root;
    254         uint32_t hash;
    255         ext4_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);
     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        }
    274262
    275263        // Check unused flags
    276264        if (root->info.unused_flags != 0) {
    277265                EXT4FS_DBG("ERR: unused_flags = \%u", root->info.unused_flags);
    278                 block_put(phys_block);
    279266                return EXT4_ERR_BAD_DX_DIR;
    280267        }
     
    283270        if (root->info.indirect_levels > 1) {
    284271                EXT4FS_DBG("ERR: indirect_levels = \%u", root->info.indirect_levels);
    285                 block_put(phys_block);
    286272                return EXT4_ERR_BAD_DX_DIR;
    287273        }
    288274
    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);
     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);
    292280    entry_space = entry_space / sizeof(ext4_directory_dx_entry_t);
    293281
    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 
     282    limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)&root->entries);
    298283    if (limit != entry_space) {
    299                 block_put(phys_block);
    300284        return EXT4_ERR_BAD_DX_DIR;
    301285        }
    302286
    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_HASH_VERSION_TEA)
    318                         && (ext4_superblock_has_flag(fs->superblock, EXT4_SUPERBLOCK_FLAGS_UNSIGNED_HASH))) {
     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))) {
    319290                // 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;
     291                hinfo->hash_version += 3;
     292        }
     293
     294        hinfo->seed = ext4_superblock_get_hash_seed(sb);
     295
    325296        if (name) {
    326                 ext4_hash_string(&hinfo, len, 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];
     297                ext4_hash_string(hinfo, name_len, name);
     298        }
     299
     300        return EOK;
     301}
     302
     303static int ext4_directory_dx_get_leaf_block(ext4_hash_info_t *hinfo,
     304                ext4_filesystem_t *fs, ext4_inode_t *inode, uint32_t *leaf_block_idx,
     305                block_t *root_block)
     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 = NULL;
     314        uint32_t fblock;
     315
     316        root = (ext4_directory_dx_root_t *)root_block->data;
     317        entries = (ext4_directory_dx_entry_t *)&root->entries;
     318
     319        limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)entries);
     320        indirect_level = ext4_directory_dx_root_info_get_indirect_levels(&root->info);
     321
     322        while (true) {
     323
     324                count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)entries);
     325                if ((count == 0) || (count > limit)) {
     326                        return EXT4_ERR_BAD_DX_DIR;
     327                }
     328
     329                p = entries + 1;
     330                q = entries + count - 1;
    338331
    339332                while (p <= q) {
    340333                        m = p + (q - p) / 2;
    341                         if (ext4_directory_dx_entry_get_hash(m) > hash) {
     334                        if (ext4_directory_dx_entry_get_hash(m) > hinfo->hash) {
    342335                                q = m - 1;
    343336                        } else {
     
    346339                }
    347340
    348                 /* TODO move to leaf or next node
    349341                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 !!!
     342
     343        if (indirect_level == 0) {
     344                *leaf_block_idx = ext4_directory_dx_entry_get_block(at);
    357345                return EOK;
    358346        }
    359347
    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 
     348        indirect_level--;
     349
     350        rc = ext4_filesystem_get_inode_data_block_index(fs, inode, ext4_directory_dx_entry_get_block(at), &fblock);
     351        if (rc != EOK) {
     352                return rc;
     353        }
     354
     355        if (tmp_block) {
     356                block_put(tmp_block);
     357        }
     358
     359        rc = block_get(&tmp_block, fs->device, fblock, BLOCK_FLAGS_NONE);
     360        if (rc != EOK) {
     361                // TODO
     362                return rc;
     363        }
     364
     365                entries = ((ext4_directory_dx_node_t *) tmp_block->data)->entries;
     366                limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)entries);
     367
     368        entry_space = ext4_superblock_get_block_size(fs->superblock) - sizeof(ext4_directory_dx_dot_entry_t);
     369        entry_space = entry_space / sizeof(ext4_directory_dx_entry_t);
     370
     371
     372                if (limit != entry_space) {
     373                        block_put(tmp_block);
     374                return EXT4_ERR_BAD_DX_DIR;
     375                }
     376        }
     377
     378        if (tmp_block) {
     379                block_put(tmp_block);
     380        }
     381
     382        return EOK;
     383}
     384
     385
     386int ext4_directory_dx_find_entry(ext4_directory_iterator_t *it,
     387                ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, size_t len, const char *name)
     388{
     389        int rc;
     390        uint32_t root_block_addr, leaf_block_addr;
     391        block_t *root_block;
     392        ext4_hash_info_t hinfo;
     393
     394        // get direct block 0 (index root)
     395        rc = ext4_filesystem_get_inode_data_block_index(fs, inode_ref->inode, 0, &root_block_addr);
     396        if (rc != EOK) {
     397                return rc;
     398        }
     399
     400        rc = block_get(&root_block, fs->device, root_block_addr, BLOCK_FLAGS_NONE);
     401        if (rc != EOK) {
     402                it->current_block = NULL;
     403                return rc;
     404        }
     405
     406        rc = ext4_directory_hinfo_init(&hinfo, root_block, fs->superblock, len, name);
     407        if (rc != EOK) {
     408                EXT4FS_DBG("ERR: leaf block not found");
     409                block_put(root_block);
     410                return EXT4_ERR_BAD_DX_DIR;
     411        }
     412
     413        rc = ext4_directory_dx_get_leaf_block(&hinfo, fs, inode_ref->inode, &leaf_block_addr, root_block);
     414        if (rc != EOK) {
     415                return EXT4_ERR_BAD_DX_DIR;
     416        }
     417
     418        // TODO now having block - do directory entry search
    378419
    379420        // TODO delete it !!!
     421        // TODO block put
    380422        return EXT4_ERR_BAD_DX_DIR;
    381423
  • uspace/lib/ext4/libext4_directory.h

    r8158db7 r246a5af  
    9696} ext4_directory_dx_root_t;
    9797
     98typedef 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
    98108
    99109#define EXT4_ERR_BAD_DX_DIR                     (-75000)
  • uspace/lib/ext4/libext4_hash.c

    r8158db7 r246a5af  
    3939#include <mem.h>
    4040
    41 #include "libext4_directory.h"
    42 #include "libext4_hash.h"
     41#include "libext4.h"
    4342
    4443#define TEA_DELTA 0x9E3779B9
     
    227226}
    228227
    229 int ext4_hash_string(ext4_hash_info_t *hinfo, size_t len, const char *name)
     228int ext4_hash_string(ext4_hash_info_t *hinfo, int len, const char *name)
    230229{
    231230        uint32_t hash = 0;
     
    253252                }
    254253    }
    255 
    256254
    257255        switch (hinfo->hash_version) {
  • uspace/lib/ext4/libext4_hash.h

    r8158db7 r246a5af  
    5050} ext4_hash_info_t;
    5151
    52 extern int ext4_hash_string(ext4_hash_info_t *, size_t, const char *);
     52extern int ext4_hash_string(ext4_hash_info_t *, int, const char *);
    5353
    5454#endif
Note: See TracChangeset for help on using the changeset viewer.