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

Changeset e2629b08 in mainline


Ignore:
Timestamp:
2012-03-07T10:11:41Z (10 years ago)
Author:
Frantisek Princ <frantisek.princ@…>
Branches:
lfn, master
Children:
9093c61
Parents:
b53a733
Message:

Prepared infrastructure for extent searching

Location:
uspace/lib/ext4
Files:
3 edited

Legend:

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

    rb53a733 re2629b08  
    3737
    3838#include <byteorder.h>
    39 #include "libext4_extent.h"
     39#include <errno.h>
     40#include <malloc.h>
     41#include "libext4.h"
    4042
    4143uint32_t ext4_extent_get_first_block(ext4_extent_t *extent)
     
    145147{
    146148        header->generation = host2uint32_t_le(generation);
     149}
     150
     151static void ext4_extent_binsearch_idx(ext4_extent_path_t *path, uint32_t iblock)
     152{
     153        ext4_extent_header_t *header = path->header;
     154        ext4_extent_index_t *r, *l, *m;
     155
     156        uint16_t entries_count = ext4_extent_header_get_entries_count(header);
     157        l = EXT4_EXTENT_FIRST_INDEX(header) + 1;
     158        r = l + entries_count - 1;
     159
     160        while (l <= r) {
     161                m = l + (r - l) / 2;
     162                uint32_t block = ext4_extent_index_get_first_block(m);
     163                if (iblock < block) {
     164                                r = m - 1;
     165                } else {
     166                                l = m + 1;
     167                }
     168        }
     169
     170        path->index = l - 1;
     171}
     172
     173static void ext4_extent_binsearch(ext4_extent_path_t *path, uint32_t iblock)
     174{
     175        ext4_extent_header_t *header = path->header;
     176        ext4_extent_t *r, *l, *m;
     177
     178        uint16_t entries_count = ext4_extent_header_get_entries_count(header);
     179
     180        if (entries_count == 0) {
     181                // this leaf is empty
     182                return;
     183        }
     184
     185        l = EXT4_EXTENT_FIRST(header) + 1;
     186        r = l + entries_count - 1;
     187
     188        while (l <= r) {
     189                m = l + (r - l) / 2;
     190                uint32_t block = ext4_extent_get_first_block(m);
     191                if (iblock < block) {
     192                                r = m - 1;
     193                } else {
     194                                l = m + 1;
     195                }
     196        }
     197
     198        path->extent = l - 1;
     199
     200}
     201
     202int ext4_extent_find_block(ext4_filesystem_t *fs, ext4_extent_path_t **path,
     203                ext4_extent_header_t *header, uint32_t iblock)
     204{
     205        int rc;
     206
     207        uint16_t depth = ext4_extent_header_get_depth(header);
     208
     209        ext4_extent_header_t *eh = header;
     210
     211        ext4_extent_path_t *tmp_path;
     212
     213        // Added 2 for possible tree growing
     214        tmp_path = malloc(sizeof(ext4_extent_path_t) * (depth + 2));
     215        if (tmp_path == NULL) {
     216                *path = NULL;
     217                return ENOMEM;
     218        }
     219
     220        tmp_path[0].block = NULL;
     221        tmp_path[0].header = eh;
     222
     223        uint16_t pos = 0, idx = depth;
     224        while (idx > 0) {
     225
     226                ext4_extent_binsearch_idx(tmp_path + pos, iblock);
     227
     228                tmp_path[pos].depth = idx;
     229                tmp_path[pos].extent = NULL;
     230
     231                uint64_t fblock = ext4_extent_index_get_leaf(tmp_path[pos].index);
     232                block_t *block;
     233                rc = block_get(&block, fs->device, fblock, BLOCK_FLAGS_NONE);
     234                if (rc != EOK) {
     235                        // TODO cleanup
     236                }
     237
     238                eh = (ext4_extent_header_t *)tmp_path[pos].block->data;
     239                pos++;
     240
     241                tmp_path[pos].block = block;
     242                tmp_path[pos].header = eh;
     243
     244                idx--;
     245
     246        }
     247
     248        tmp_path[pos].depth = idx;
     249        tmp_path[pos].extent = NULL;
     250        tmp_path[pos].index = NULL;
     251
     252    /* find extent */
     253        ext4_extent_binsearch(tmp_path + pos, iblock);
     254
     255        /* if not an empty leaf */
     256        if (tmp_path[pos].extent) {
     257                uint64_t fblock = ext4_extent_get_start(tmp_path[pos].extent);
     258                block_t *block;
     259                rc = block_get(&block, fs->device, fblock, BLOCK_FLAGS_NONE);
     260                if (rc != EOK) {
     261                        // TODO cleanup
     262                }
     263                tmp_path[pos].block = block;
     264        }
     265
     266        return EOK;
    147267}
    148268
  • uspace/lib/ext4/libext4_extent.h

    rb53a733 re2629b08  
    6161extern void ext4_extent_header_set_generation(ext4_extent_header_t *, uint32_t);
    6262
     63extern int ext4_extent_find_block(ext4_filesystem_t *, ext4_extent_path_t **,
     64                ext4_extent_header_t *, uint32_t);
    6365#endif
    6466
  • uspace/lib/ext4/libext4_types.h

    rb53a733 re2629b08  
    485485} ext4_extent_header_t;
    486486
     487typedef struct ext4_extent_path {
     488        block_t *block;
     489        uint16_t depth;
     490        ext4_extent_header_t *header;
     491        ext4_extent_index_t *index;
     492        ext4_extent_t *extent;
     493} ext4_extent_path_t;
     494
    487495#define EXT4_EXTENT_MAGIC       0xF30A
    488496#define EXT4_EXTENT_FIRST(header)       \
Note: See TracChangeset for help on using the changeset viewer.