Changeset 7bc4508 in mainline for uspace/lib/ext4/libext4_directory.c

Timestamp:

2011-10-18T19:58:36Z (14 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

File:

• uspace/lib/ext4/libext4_directory.c (modified) (2 diffs)

uspace/lib/ext4/libext4_directory.c

@@ -66 +66 @@
 }
 
+uint8_t ext4_directory_dx_root_info_get_hash_version(ext4_directory_dx_root_info_t *root_info)
+{
+        return root_info->hash_version;
+}
+
+uint8_t ext4_directory_dx_root_info_get_info_length(ext4_directory_dx_root_info_t *root_info)
+{
+        return root_info->info_length;
+}
+
+uint8_t ext4_directory_dx_root_info_get_indirect_levels(ext4_directory_dx_root_info_t *root_info)
+{
+        return root_info->indirect_levels;
+}
+
+uint16_t ext4_directory_dx_countlimit_get_limit(ext4_directory_dx_countlimit_t *countlimit)
+{
+        return uint16_t_le2host(countlimit->limit);
+}
+uint16_t ext4_directory_dx_countlimit_get_count(ext4_directory_dx_countlimit_t *countlimit)
+{
+        return uint16_t_le2host(countlimit->count);
+}
+
+uint32_t ext4_directory_dx_entry_get_hash(ext4_directory_dx_entry_t *entry)
+{
+        return uint32_t_le2host(entry->hash);
+}
+
+uint32_t ext4_directory_dx_entry_get_block(ext4_directory_dx_entry_t *entry)
+{
+        return uint32_t_le2host(entry->block);
+}
+
+
+
 int ext4_directory_iterator_init(ext4_directory_iterator_t *it,
     ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, aoff64_t pos)
@@ -209 +245 @@
 }
 
+int ext4_directory_dx_find_entry(ext4_directory_iterator_t *it,
+                ext4_filesystem_t *fs, ext4_inode_ref_t *inode_ref, const char *name)
+{
+        int rc;
+        uint32_t fblock;
+        block_t *phys_block;
+        ext4_directory_dx_root_t *root;
+        uint32_t hash;
+        ext4_directory_dx_hash_info_t hinfo;
+
+        // get direct block 0 (index root)
+        rc = ext4_filesystem_get_inode_data_block_index(fs, inode_ref->inode, 0, &fblock);
+        if (rc != EOK) {
+                return rc;
+        }
+
+        rc = block_get(&phys_block, fs->device, fblock, BLOCK_FLAGS_NONE);
+        if (rc != EOK) {
+                it->current_block = NULL;
+                        return rc;
+        }
+
+        // Now having index root
+        root = (ext4_directory_dx_root_t *)phys_block->data;
+
+        // Check hash version - only if supported
+        EXT4FS_DBG("hash_version = \%u", root->info.hash_version);
+
+        // Check unused flags
+        if (root->info.unused_flags != 0) {
+                EXT4FS_DBG("ERR: unused_flags = \%u", root->info.unused_flags);
+                block_put(phys_block);
+                return EXT4_ERR_BAD_DX_DIR;
+        }
+
+        // Check indirect levels
+        if (root->info.indirect_levels > 1) {
+                EXT4FS_DBG("ERR: indirect_levels = \%u", root->info.indirect_levels);
+                block_put(phys_block);
+                return EXT4_ERR_BAD_DX_DIR;
+        }
+
+        uint32_t bs = ext4_superblock_get_block_size(fs->superblock);
+
+        uint32_t entry_space = bs - 2* sizeof(ext4_directory_dx_dot_entry_t) - sizeof(ext4_directory_dx_root_info_t);
+    entry_space = entry_space / sizeof(ext4_directory_dx_entry_t);
+
+
+    uint32_t limit = ext4_directory_dx_countlimit_get_limit((ext4_directory_dx_countlimit_t *)&root->entries);
+    uint32_t count = ext4_directory_dx_countlimit_get_count((ext4_directory_dx_countlimit_t *)&root->entries);
+
+    if (limit != entry_space) {
+                block_put(phys_block);
+        return EXT4_ERR_BAD_DX_DIR;
+        }
+
+        if ((count == 0) || (count > limit)) {
+                block_put(phys_block);
+                return EXT4_ERR_BAD_DX_DIR;
+        }
+
+        /* DEBUG list
+    for (uint16_t i = 0; i < count; ++i) {
+        uint32_t hash = ext4_directory_dx_entry_get_hash(&root->entries[i]);
+        uint32_t block = ext4_directory_dx_entry_get_block(&root->entries[i]);
+        EXT4FS_DBG("hash = \%u, block = \%u", hash, block);
+    }
+    */
+
+        hinfo.hash_version = ext4_directory_dx_root_info_get_hash_version(&root->info);
+        if ((hinfo.hash_version <= EXT4_DIRECTORY_DX_HASH_TEA)
+                        && (ext4_superblock_has_flag(fs->superblock, EXT4_SUPERBLOCK_FLAGS_UNSIGNED_HASH))) {
+                // 3 is magic from ext4 linux implementation
+                hinfo.hash_version += 3;
+        }
+
+        hinfo.seed = ext4_superblock_get_hash_seed(fs->superblock);
+        hinfo.hash = 0;
+        if (name) {
+                ext4_directory_hash(&hinfo, name);
+        }
+
+        hash = hinfo.hash;
+
+        ext4_directory_dx_entry_t *p, *q, *m;
+
+        // TODO cycle
+        // while (true)
+
+                p = &root->entries[1];
+                q = &root->entries[count - 1];
+
+                while (p <= q) {
+                        m = p + (q - p) / 2;
+                        if (ext4_directory_dx_entry_get_hash(m) > hash) {
+                                q = m - 1;
+                        } else {
+                                p = m + 1;
+                        }
+                }
+
+                /* TODO move to leaf or next node
+                at = p - 1;
+                dxtrace(printk(" %x->%u\n", at == entries? 0: dx_get_hash(at), dx_get_block(at)));
+        frame->bh = bh;
+        frame->entries = entries;
+        frame->at = at;
+
+        if (indirect == 0) {
+                        // TODO write return values !!!
+                return EOK;
+        }
+
+        indirect--;
+
+                // TODO read next block
+                if (!(bh = ext4_bread (NULL,dir, dx_get_block(at), 0, err)))
+                        goto fail2;
+                at = entries = ((struct dx_node *) bh->b_data)->entries;
+                if (dx_get_limit(entries) != dx_node_limit (dir)) {
+                ext4_warning(dir->i_sb, "dx entry: limit != node limit");
+                        brelse(bh);
+            *err = ERR_BAD_DX_DIR;
+                        goto fail2;
+                }
+                frame++;
+                frame->bh = NULL;
+                 */
+
+        // } END WHILE
+
+
+        // TODO delete it !!!
+        return EXT4_ERR_BAD_DX_DIR;
+
+        if ((it->current == NULL) || (it->current->inode == 0)) {
+                        return ENOENT;
+        }
+
+        return EOK;
+}
+
+void ext4_directory_hash(ext4_directory_dx_hash_info_t *hinfo, const char* name)
+{
+        // TODO
+}
 
 /**