Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • uspace/srv/fs/exfat/exfat_idx.c

    r4e00f87 re090244c  
    4141#include <str.h>
    4242#include <adt/hash_table.h>
    43 #include <adt/hash.h>
    4443#include <adt/list.h>
    4544#include <assert.h>
    … …  
    6059typedef struct {
    6160        link_t link;
    62         service_id_t service_id;
     61        devmap_handle_t devmap_handle;
    6362
    6463        /** Next unassigned index. */
    … …  
    7776static LIST_INITIALIZE(unused_list);
    7877
    79 static void unused_initialize(unused_t *u, service_id_t service_id)
     78static void unused_initialize(unused_t *u, devmap_handle_t devmap_handle)
    8079{
    8180        link_initialize(&u->link);
    82         u->service_id = service_id;
     81        u->devmap_handle = devmap_handle;
    8382        u->next = 0;
    8483        u->remaining = ((uint64_t)((fs_index_t)-1)) + 1;
    … …  
    8685}
    8786
    88 static unused_t *unused_find(service_id_t service_id, bool lock)
     87static unused_t *unused_find(devmap_handle_t devmap_handle, bool lock)
    8988{
    9089        unused_t *u;
    … …  
    9291        if (lock)
    9392                fibril_mutex_lock(&unused_lock);
    94 
    9593        list_foreach(unused_list, l) {
    9694                u = list_get_instance(l, unused_t, link);
    97                 if (u->service_id == service_id)
     95                if (u->devmap_handle == devmap_handle)
    9896                        return u;
    9997        }
    … …  
    109107/**
    110108 * Global hash table of all used exfat_idx_t structures.
    111  * The index structures are hashed by the service_id, parent node's first
     109 * The index structures are hashed by the devmap_handle, parent node's first
    112110 * cluster and index within the parent directory.
    113111 */
    114112static hash_table_t up_hash;
    115113
    116 typedef struct {
    117         service_id_t service_id;
     114#define UPH_BUCKETS_LOG 12
     115#define UPH_BUCKETS     (1 << UPH_BUCKETS_LOG)
     116
     117#define UPH_DH_KEY      0
     118#define UPH_PFC_KEY     1
     119#define UPH_PDI_KEY     2
     120
     121static hash_index_t pos_hash(unsigned long key[])
     122{
     123        devmap_handle_t devmap_handle = (devmap_handle_t)key[UPH_DH_KEY];
     124        exfat_cluster_t pfc = (exfat_cluster_t)key[UPH_PFC_KEY];
     125        unsigned pdi = (unsigned)key[UPH_PDI_KEY];
     126
     127        hash_index_t h;
     128
     129        /*
     130         * The least significant half of all bits are the least significant bits
     131         * of the parent node's first cluster.
     132         *
     133         * The least significant half of the most significant half of all bits
     134         * are the least significant bits of the node's dentry index within the
     135         * parent directory node.
     136         *
     137         * The most significant half of the most significant half of all bits
     138         * are the least significant bits of the device handle.
     139         */
     140        h = pfc & ((1 << (UPH_BUCKETS_LOG / 2)) - 1);
     141        h |= (pdi & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
     142            (UPH_BUCKETS_LOG / 2);
     143        h |= (devmap_handle & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
     144            (3 * (UPH_BUCKETS_LOG / 4));
     145
     146        return h;
     147}
     148
     149static int pos_compare(unsigned long key[], hash_count_t keys, link_t *item)
     150{
     151        devmap_handle_t devmap_handle = (devmap_handle_t)key[UPH_DH_KEY];
    118152        exfat_cluster_t pfc;
    119153        unsigned pdi;
    120 } pos_key_t;
    121 
    122 static inline size_t pos_key_hash(void *key)
    123 {
    124         pos_key_t *pos = (pos_key_t*)key;
    125        
    126         size_t hash = 0;
    127         hash = hash_combine(pos->pfc, pos->pdi);
    128         return hash_combine(hash, pos->service_id);
    129 }
    130 
    131 static size_t pos_hash(const ht_link_t *item)
    132 {
    133         exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uph_link);
    134        
    135         pos_key_t pkey = {
    136                 .service_id = fidx->service_id,
    137                 .pfc = fidx->pfc,
    138                 .pdi = fidx->pdi,
    139         };
    140        
    141         return pos_key_hash(&pkey);
    142 }
    143 
    144 static bool pos_key_equal(void *key, const ht_link_t *item)
    145 {
    146         pos_key_t *pos = (pos_key_t*)key;
    147         exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uph_link);
    148        
    149         return pos->service_id == fidx->service_id
    150                 && pos->pdi == fidx->pdi
    151                 && pos->pfc == fidx->pfc;
    152 }
    153 
    154 static hash_table_ops_t uph_ops = {
     154        exfat_idx_t *fidx = list_get_instance(item, exfat_idx_t, uph_link);
     155
     156        switch (keys) {
     157        case 1:
     158                return (devmap_handle == fidx->devmap_handle);
     159        case 3:
     160                pfc = (exfat_cluster_t) key[UPH_PFC_KEY];
     161                pdi = (unsigned) key[UPH_PDI_KEY];
     162                return (devmap_handle == fidx->devmap_handle) && (pfc == fidx->pfc) &&
     163                    (pdi == fidx->pdi);
     164        default:
     165                assert((keys == 1) || (keys == 3));
     166        }
     167
     168        return 0;
     169}
     170
     171static void pos_remove_callback(link_t *item)
     172{
     173        /* nothing to do */
     174}
     175
     176static hash_table_operations_t uph_ops = {
    155177        .hash = pos_hash,
    156         .key_hash = pos_key_hash,
    157         .key_equal = pos_key_equal,
    158         .equal = NULL,
    159         .remove_callback = NULL,
     178        .compare = pos_compare,
     179        .remove_callback = pos_remove_callback,
    160180};
    161181
    162182/**
    163183 * Global hash table of all used fat_idx_t structures.
    164  * The index structures are hashed by the service_id and index.
     184 * The index structures are hashed by the devmap_handle and index.
    165185 */
    166186static hash_table_t ui_hash;
    167187
    168 typedef struct {
    169         service_id_t service_id;
     188#define UIH_BUCKETS_LOG 12
     189#define UIH_BUCKETS     (1 << UIH_BUCKETS_LOG)
     190
     191#define UIH_DH_KEY      0
     192#define UIH_INDEX_KEY   1
     193
     194static hash_index_t idx_hash(unsigned long key[])
     195{
     196        devmap_handle_t devmap_handle = (devmap_handle_t)key[UIH_DH_KEY];
     197        fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];
     198
     199        hash_index_t h;
     200
     201        h = devmap_handle & ((1 << (UIH_BUCKETS_LOG / 2)) - 1);
     202        h |= (index & ((1 << (UIH_BUCKETS_LOG / 2)) - 1)) <<
     203            (UIH_BUCKETS_LOG / 2);
     204
     205        return h;
     206}
     207
     208static int idx_compare(unsigned long key[], hash_count_t keys, link_t *item)
     209{
     210        devmap_handle_t devmap_handle = (devmap_handle_t)key[UIH_DH_KEY];
    170211        fs_index_t index;
    171 } idx_key_t;
    172 
    173 static size_t idx_key_hash(void *key_arg)
    174 {
    175         idx_key_t *key = (idx_key_t*)key_arg;
    176         return hash_combine(key->service_id, key->index);
    177 }
    178 
    179 static size_t idx_hash(const ht_link_t *item)
    180 {
    181         exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uih_link);
    182         return hash_combine(fidx->service_id, fidx->index);
    183 }
    184 
    185 static bool idx_key_equal(void *key_arg, const ht_link_t *item)
    186 {
    187         exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uih_link);
    188         idx_key_t *key = (idx_key_t*)key_arg;
    189        
    190         return key->index == fidx->index && key->service_id == fidx->service_id;
    191 }
    192 
    193 static void idx_remove_callback(ht_link_t *item)
    194 {
    195         exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uih_link);
     212        exfat_idx_t *fidx = list_get_instance(item, exfat_idx_t, uih_link);
     213
     214        switch (keys) {
     215        case 1:
     216                return (devmap_handle == fidx->devmap_handle);
     217        case 2:
     218                index = (fs_index_t) key[UIH_INDEX_KEY];
     219                return (devmap_handle == fidx->devmap_handle) &&
     220                    (index == fidx->index);
     221        default:
     222                assert((keys == 1) || (keys == 2));
     223        }
     224
     225        return 0;
     226}
     227
     228static void idx_remove_callback(link_t *item)
     229{
     230        exfat_idx_t *fidx = list_get_instance(item, exfat_idx_t, uih_link);
    196231
    197232        free(fidx);
    198233}
    199234
    200 static hash_table_ops_t uih_ops = {
     235static hash_table_operations_t uih_ops = {
    201236        .hash = idx_hash,
    202         .key_hash = idx_key_hash,
    203         .key_equal = idx_key_equal,
    204         .equal = NULL,
     237        .compare = idx_compare,
    205238        .remove_callback = idx_remove_callback,
    206239};
    207240
    208241/** Allocate a VFS index which is not currently in use. */
    209 static bool exfat_index_alloc(service_id_t service_id, fs_index_t *index)
     242static bool exfat_index_alloc(devmap_handle_t devmap_handle, fs_index_t *index)
    210243{
    211244        unused_t *u;
    212245       
    213246        assert(index);
    214         u = unused_find(service_id, true);
     247        u = unused_find(devmap_handle, true);
    215248        if (!u)
    216249                return false;   
    … …  
    269302
    270303/** Free a VFS index, which is no longer in use. */
    271 static void exfat_index_free(service_id_t service_id, fs_index_t index)
     304static void exfat_index_free(devmap_handle_t devmap_handle, fs_index_t index)
    272305{
    273306        unused_t *u;
    274307
    275         u = unused_find(service_id, true);
     308        u = unused_find(devmap_handle, true);
    276309        assert(u);
    277310
    … …  
    331364}
    332365
    333 static int exfat_idx_create(exfat_idx_t **fidxp, service_id_t service_id)
     366static int exfat_idx_create(exfat_idx_t **fidxp, devmap_handle_t devmap_handle)
    334367{
    335368        exfat_idx_t *fidx;
    … …  
    338371        if (!fidx)
    339372                return ENOMEM;
    340         if (!exfat_index_alloc(service_id, &fidx->index)) {
     373        if (!exfat_index_alloc(devmap_handle, &fidx->index)) {
    341374                free(fidx);
    342375                return ENOSPC;
    343376        }
    344377               
     378        link_initialize(&fidx->uph_link);
     379        link_initialize(&fidx->uih_link);
    345380        fibril_mutex_initialize(&fidx->lock);
    346         fidx->service_id = service_id;
     381        fidx->devmap_handle = devmap_handle;
    347382        fidx->pfc = 0;  /* no parent yet */
    348383        fidx->pdi = 0;
    … …  
    353388}
    354389
    355 int exfat_idx_get_new(exfat_idx_t **fidxp, service_id_t service_id)
     390int exfat_idx_get_new(exfat_idx_t **fidxp, devmap_handle_t devmap_handle)
    356391{
    357392        exfat_idx_t *fidx;
    … …  
    359394
    360395        fibril_mutex_lock(&used_lock);
    361         rc = exfat_idx_create(&fidx, service_id);
     396        rc = exfat_idx_create(&fidx, devmap_handle);
    362397        if (rc != EOK) {
    363398                fibril_mutex_unlock(&used_lock);
    … …  
    365400        }
    366401               
    367         hash_table_insert(&ui_hash, &fidx->uih_link);
     402        unsigned long ikey[] = {
     403                [UIH_DH_KEY] = devmap_handle,
     404                [UIH_INDEX_KEY] = fidx->index,
     405        };
     406       
     407        hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
    368408        fibril_mutex_lock(&fidx->lock);
    369409        fibril_mutex_unlock(&used_lock);
    … …  
    374414
    375415exfat_idx_t *
    376 exfat_idx_get_by_pos(service_id_t service_id, exfat_cluster_t pfc, unsigned pdi)
     416exfat_idx_get_by_pos(devmap_handle_t devmap_handle, exfat_cluster_t pfc, unsigned pdi)
    377417{
    378418        exfat_idx_t *fidx;
    379        
    380         pos_key_t pos_key = {
    381                 .service_id = service_id,
    382                 .pfc = pfc,
    383                 .pdi = pdi,
     419        link_t *l;
     420        unsigned long pkey[] = {
     421                [UPH_DH_KEY] = devmap_handle,
     422                [UPH_PFC_KEY] = pfc,
     423                [UPH_PDI_KEY] = pdi,
    384424        };
    385425
    386426        fibril_mutex_lock(&used_lock);
    387         ht_link_t *l = hash_table_find(&up_hash, &pos_key);
     427        l = hash_table_find(&up_hash, pkey);
    388428        if (l) {
    389                 fidx = hash_table_get_inst(l, exfat_idx_t, uph_link);
     429                fidx = hash_table_get_instance(l, exfat_idx_t, uph_link);
    390430        } else {
    391431                int rc;
    392432
    393                 rc = exfat_idx_create(&fidx, service_id);
     433                rc = exfat_idx_create(&fidx, devmap_handle);
    394434                if (rc != EOK) {
    395435                        fibril_mutex_unlock(&used_lock);
    … …  
    397437                }
    398438               
     439                unsigned long ikey[] = {
     440                        [UIH_DH_KEY] = devmap_handle,
     441                        [UIH_INDEX_KEY] = fidx->index,
     442                };
     443       
    399444                fidx->pfc = pfc;
    400445                fidx->pdi = pdi;
    401446
    402                 hash_table_insert(&up_hash, &fidx->uph_link);
    403                 hash_table_insert(&ui_hash, &fidx->uih_link);
     447                hash_table_insert(&up_hash, pkey, &fidx->uph_link);
     448                hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
    404449        }
    405450        fibril_mutex_lock(&fidx->lock);
    … …  
    411456void exfat_idx_hashin(exfat_idx_t *idx)
    412457{
     458        unsigned long pkey[] = {
     459                [UPH_DH_KEY] = idx->devmap_handle,
     460                [UPH_PFC_KEY] = idx->pfc,
     461                [UPH_PDI_KEY] = idx->pdi,
     462        };
     463
    413464        fibril_mutex_lock(&used_lock);
    414         hash_table_insert(&up_hash, &idx->uph_link);
     465        hash_table_insert(&up_hash, pkey, &idx->uph_link);
    415466        fibril_mutex_unlock(&used_lock);
    416467}
    … …  
    418469void exfat_idx_hashout(exfat_idx_t *idx)
    419470{
     471        unsigned long pkey[] = {
     472                [UPH_DH_KEY] = idx->devmap_handle,
     473                [UPH_PFC_KEY] = idx->pfc,
     474                [UPH_PDI_KEY] = idx->pdi,
     475        };
     476
    420477        fibril_mutex_lock(&used_lock);
    421         hash_table_remove_item(&up_hash, &idx->uph_link);
     478        hash_table_remove(&up_hash, pkey, 3);
    422479        fibril_mutex_unlock(&used_lock);
    423480}
    424481
    425482exfat_idx_t *
    426 exfat_idx_get_by_index(service_id_t service_id, fs_index_t index)
     483exfat_idx_get_by_index(devmap_handle_t devmap_handle, fs_index_t index)
    427484{
    428485        exfat_idx_t *fidx = NULL;
    429 
    430         idx_key_t idx_key = {
    431                 .service_id = service_id,
    432                 .index = index,
     486        link_t *l;
     487        unsigned long ikey[] = {
     488                [UIH_DH_KEY] = devmap_handle,
     489                [UIH_INDEX_KEY] = index,
    433490        };
    434491
    435492        fibril_mutex_lock(&used_lock);
    436         ht_link_t *l = hash_table_find(&ui_hash, &idx_key);
     493        l = hash_table_find(&ui_hash, ikey);
    437494        if (l) {
    438                 fidx = hash_table_get_inst(l, exfat_idx_t, uih_link);
     495                fidx = hash_table_get_instance(l, exfat_idx_t, uih_link);
    439496                fibril_mutex_lock(&fidx->lock);
    440497        }
    … …  
    450507void exfat_idx_destroy(exfat_idx_t *idx)
    451508{
    452         idx_key_t idx_key = {
    453                 .service_id = idx->service_id,
    454                 .index = idx->index,
    455         };
     509        unsigned long ikey[] = {
     510                [UIH_DH_KEY] = idx->devmap_handle,
     511                [UIH_INDEX_KEY] = idx->index,
     512        };
     513        devmap_handle_t devmap_handle = idx->devmap_handle;
     514        fs_index_t index = idx->index;
    456515
    457516        /* TODO: assert(idx->pfc == FAT_CLST_RES0); */
    … …  
    464523         * the index hash only.
    465524         */
    466         hash_table_remove(&ui_hash, &idx_key);
     525        hash_table_remove(&ui_hash, ikey, 2);
    467526        fibril_mutex_unlock(&used_lock);
    468527        /* Release the VFS index. */
    469         exfat_index_free(idx_key.service_id, idx_key.index);
     528        exfat_index_free(devmap_handle, index);
    470529        /* The index structure itself is freed in idx_remove_callback(). */
    471530}
    … …  
    473532int exfat_idx_init(void)
    474533{
    475         if (!hash_table_create(&up_hash, 0, 0, &uph_ops))
     534        if (!hash_table_create(&up_hash, UPH_BUCKETS, 3, &uph_ops))
    476535                return ENOMEM;
    477         if (!hash_table_create(&ui_hash, 0, 0, &uih_ops)) {
     536        if (!hash_table_create(&ui_hash, UIH_BUCKETS, 2, &uih_ops)) {
    478537                hash_table_destroy(&up_hash);
    479538                return ENOMEM;
    … …  
    485544{
    486545        /* We assume the hash tables are empty. */
    487         assert(hash_table_empty(&up_hash) && hash_table_empty(&ui_hash));
    488546        hash_table_destroy(&up_hash);
    489547        hash_table_destroy(&ui_hash);
    490548}
    491549
    492 int exfat_idx_init_by_service_id(service_id_t service_id)
     550int exfat_idx_init_by_devmap_handle(devmap_handle_t devmap_handle)
    493551{
    494552        unused_t *u;
    … …  
    498556        if (!u)
    499557                return ENOMEM;
    500         unused_initialize(u, service_id);
     558        unused_initialize(u, devmap_handle);
    501559        fibril_mutex_lock(&unused_lock);
    502         if (!unused_find(service_id, false)) {
     560        if (!unused_find(devmap_handle, false)) {
    503561                list_append(&u->link, &unused_list);
    504562        } else {
    … …  
    510568}
    511569
    512 static bool rm_pos_service_id(ht_link_t *item, void *arg)
    513 {
    514         service_id_t service_id = *(service_id_t*)arg;
    515         exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uph_link);
    516 
    517         if (fidx->service_id == service_id) {
    518                 hash_table_remove_item(&up_hash, item);
    519         }
    520        
    521         return true;
    522 }
    523 
    524 static bool rm_idx_service_id(ht_link_t *item, void *arg)
    525 {
    526         service_id_t service_id = *(service_id_t*)arg;
    527         exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uih_link);
    528 
    529         if (fidx->service_id == service_id) {
    530                 hash_table_remove_item(&ui_hash, item);
    531         }
    532        
    533         return true;
    534 }
    535 
    536 void exfat_idx_fini_by_service_id(service_id_t service_id)
    537 {
     570void exfat_idx_fini_by_devmap_handle(devmap_handle_t devmap_handle)
     571{
     572        unsigned long ikey[] = {
     573                [UIH_DH_KEY] = devmap_handle
     574        };
     575        unsigned long pkey[] = {
     576                [UPH_DH_KEY] = devmap_handle
     577        };
     578
    538579        /*
    539580         * Remove this instance's index structure from up_hash and ui_hash.
    … …  
    542583         */
    543584        fibril_mutex_lock(&used_lock);
    544         hash_table_apply(&up_hash, rm_pos_service_id, &service_id);
    545         hash_table_apply(&ui_hash, rm_idx_service_id, &service_id);
     585        hash_table_remove(&up_hash, pkey, 1);
     586        hash_table_remove(&ui_hash, ikey, 1);
    546587        fibril_mutex_unlock(&used_lock);
    547588
    … …  
    549590         * Free the unused and freed structures for this instance.
    550591         */
    551         unused_t *u = unused_find(service_id, true);
     592        unused_t *u = unused_find(devmap_handle, true);
    552593        assert(u);
    553594        list_remove(&u->link);
Note: See TracChangeset for help on using the changeset viewer.