Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r4e00f87 r9d58539  
    4141#include <str.h>
    4242#include <adt/hash_table.h>
    43 #include <adt/hash.h>
    4443#include <adt/list.h>
    4544#include <assert.h>
    … …  
    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);
    … …  
    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_SID_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        service_id_t service_id = (service_id_t)key[UPH_SID_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 |= (service_id & ((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        service_id_t service_id = (service_id_t)key[UPH_SID_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 (service_id == fidx->service_id);
     159        case 3:
     160                pfc = (exfat_cluster_t) key[UPH_PFC_KEY];
     161                pdi = (unsigned) key[UPH_PDI_KEY];
     162                return (service_id == fidx->service_id) && (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
    … …  
    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_SID_KEY     0
     192#define UIH_INDEX_KEY   1
     193
     194static hash_index_t idx_hash(unsigned long key[])
     195{
     196        service_id_t service_id = (service_id_t)key[UIH_SID_KEY];
     197        fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];
     198
     199        hash_index_t h;
     200
     201        h = service_id & ((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        service_id_t service_id = (service_id_t)key[UIH_SID_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 (service_id == fidx->service_id);
     217        case 2:
     218                index = (fs_index_t) key[UIH_INDEX_KEY];
     219                return (service_id == fidx->service_id) &&
     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};
    … …  
    343376        }
    344377               
     378        link_initialize(&fidx->uph_link);
     379        link_initialize(&fidx->uih_link);
    345380        fibril_mutex_initialize(&fidx->lock);
    346381        fidx->service_id = service_id;
    … …  
    365400        }
    366401               
    367         hash_table_insert(&ui_hash, &fidx->uih_link);
     402        unsigned long ikey[] = {
     403                [UIH_SID_KEY] = service_id,
     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);
    … …  
    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_SID_KEY] = service_id,
     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;
    … …  
    397437                }
    398438               
     439                unsigned long ikey[] = {
     440                        [UIH_SID_KEY] = service_id,
     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_SID_KEY] = idx->service_id,
     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_SID_KEY] = idx->service_id,
     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}
    … …  
    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_SID_KEY] = service_id,
     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_SID_KEY] = idx->service_id,
     511                [UIH_INDEX_KEY] = idx->index,
     512        };
     513        service_id_t service_id = idx->service_id;
     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(service_id, 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);
    … …  
    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 
    536570void exfat_idx_fini_by_service_id(service_id_t service_id)
    537571{
     572        unsigned long ikey[] = {
     573                [UIH_SID_KEY] = service_id
     574        };
     575        unsigned long pkey[] = {
     576                [UPH_SID_KEY] = service_id
     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
Note: See TracChangeset for help on using the changeset viewer.