Changeset e2629b08 in mainline

Timestamp:

2012-03-07T10:11:41Z (12 years ago)

Author:

Frantisek Princ <frantisek.princ@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

9093c61

Parents:

b53a733

Message:

Prepared infrastructure for extent searching

Location:

uspace/lib/ext4

Files:

• libext4_extent.c (modified) (2 diffs)
• libext4_extent.h (modified) (1 diff)
• libext4_types.h (modified) (1 diff)

uspace/lib/ext4/libext4_extent.c

@@ -37 +37 @@
 
 #include <byteorder.h>
-#include "libext4_extent.h"
+#include <errno.h>
+#include <malloc.h>
+#include "libext4.h"
 
 uint32_t ext4_extent_get_first_block(ext4_extent_t *extent)
@@ -145 +147 @@
 {
         header->generation = host2uint32_t_le(generation);
+}
+
+static void ext4_extent_binsearch_idx(ext4_extent_path_t *path, uint32_t iblock)
+{
+        ext4_extent_header_t *header = path->header;
+        ext4_extent_index_t *r, *l, *m;
+
+        uint16_t entries_count = ext4_extent_header_get_entries_count(header);
+        l = EXT4_EXTENT_FIRST_INDEX(header) + 1;
+        r = l + entries_count - 1;
+
+        while (l <= r) {
+                m = l + (r - l) / 2;
+                uint32_t block = ext4_extent_index_get_first_block(m);
+                if (iblock < block) {
+                                r = m - 1;
+                } else {
+                                l = m + 1;
+                }
+        }
+
+        path->index = l - 1;
+}
+
+static void ext4_extent_binsearch(ext4_extent_path_t *path, uint32_t iblock)
+{
+        ext4_extent_header_t *header = path->header;
+        ext4_extent_t *r, *l, *m;
+
+        uint16_t entries_count = ext4_extent_header_get_entries_count(header);
+
+        if (entries_count == 0) {
+                // this leaf is empty
+                return;
+        }
+
+        l = EXT4_EXTENT_FIRST(header) + 1;
+        r = l + entries_count - 1;
+
+        while (l <= r) {
+                m = l + (r - l) / 2;
+                uint32_t block = ext4_extent_get_first_block(m);
+                if (iblock < block) {
+                                r = m - 1;
+                } else {
+                                l = m + 1;
+                }
+        }
+
+        path->extent = l - 1;
+
+}
+
+int ext4_extent_find_block(ext4_filesystem_t *fs, ext4_extent_path_t **path,
+                ext4_extent_header_t *header, uint32_t iblock)
+{
+        int rc;
+
+        uint16_t depth = ext4_extent_header_get_depth(header);
+
+        ext4_extent_header_t *eh = header;
+
+        ext4_extent_path_t *tmp_path;
+
+        // Added 2 for possible tree growing
+        tmp_path = malloc(sizeof(ext4_extent_path_t) * (depth + 2));
+        if (tmp_path == NULL) {
+                *path = NULL;
+                return ENOMEM;
+        }
+
+        tmp_path[0].block = NULL;
+        tmp_path[0].header = eh;
+
+        uint16_t pos = 0, idx = depth;
+        while (idx > 0) {
+
+                ext4_extent_binsearch_idx(tmp_path + pos, iblock);
+
+                tmp_path[pos].depth = idx;
+                tmp_path[pos].extent = NULL;
+
+                uint64_t fblock = ext4_extent_index_get_leaf(tmp_path[pos].index);
+                block_t *block;
+                rc = block_get(&block, fs->device, fblock, BLOCK_FLAGS_NONE);
+                if (rc != EOK) {
+                        // TODO cleanup
+                }
+
+                eh = (ext4_extent_header_t *)tmp_path[pos].block->data;
+                pos++;
+
+                tmp_path[pos].block = block;
+                tmp_path[pos].header = eh;
+
+                idx--;
+
+        }
+
+        tmp_path[pos].depth = idx;
+        tmp_path[pos].extent = NULL;
+        tmp_path[pos].index = NULL;
+
+    /* find extent */
+        ext4_extent_binsearch(tmp_path + pos, iblock);
+
+        /* if not an empty leaf */
+        if (tmp_path[pos].extent) {
+                uint64_t fblock = ext4_extent_get_start(tmp_path[pos].extent);
+                block_t *block;
+                rc = block_get(&block, fs->device, fblock, BLOCK_FLAGS_NONE);
+                if (rc != EOK) {
+                        // TODO cleanup
+                }
+                tmp_path[pos].block = block;
+        }
+
+        return EOK;
 }
 

uspace/lib/ext4/libext4_extent.h

@@ -61 +61 @@
 extern void ext4_extent_header_set_generation(ext4_extent_header_t *, uint32_t);
 
+extern int ext4_extent_find_block(ext4_filesystem_t *, ext4_extent_path_t **,
+                ext4_extent_header_t *, uint32_t);
 #endif
 

uspace/lib/ext4/libext4_types.h

@@ -485 +485 @@
 } ext4_extent_header_t;
 
+typedef struct ext4_extent_path {
+        block_t *block;
+        uint16_t depth;
+        ext4_extent_header_t *header;
+        ext4_extent_index_t *index;
+        ext4_extent_t *extent;
+} ext4_extent_path_t;
+
 #define EXT4_EXTENT_MAGIC       0xF30A
 #define EXT4_EXTENT_FIRST(header)       \