Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed
  • uspace/srv/fs/exfat/exfat_idx.c

    re090244c r4e00f87  
    4141#include <str.h>
    4242#include <adt/hash_table.h>
     43#include <adt/hash.h>
    4344#include <adt/list.h>
    4445#include <assert.h>
     
    5960typedef struct {
    6061        link_t link;
    61         devmap_handle_t devmap_handle;
     62        service_id_t service_id;
    6263
    6364        /** Next unassigned index. */
     
    7677static LIST_INITIALIZE(unused_list);
    7778
    78 static void unused_initialize(unused_t *u, devmap_handle_t devmap_handle)
     79static void unused_initialize(unused_t *u, service_id_t service_id)
    7980{
    8081        link_initialize(&u->link);
    81         u->devmap_handle = devmap_handle;
     82        u->service_id = service_id;
    8283        u->next = 0;
    8384        u->remaining = ((uint64_t)((fs_index_t)-1)) + 1;
     
    8586}
    8687
    87 static unused_t *unused_find(devmap_handle_t devmap_handle, bool lock)
     88static unused_t *unused_find(service_id_t service_id, bool lock)
    8889{
    8990        unused_t *u;
     
    9192        if (lock)
    9293                fibril_mutex_lock(&unused_lock);
     94
    9395        list_foreach(unused_list, l) {
    9496                u = list_get_instance(l, unused_t, link);
    95                 if (u->devmap_handle == devmap_handle)
     97                if (u->service_id == service_id)
    9698                        return u;
    9799        }
     
    107109/**
    108110 * Global hash table of all used exfat_idx_t structures.
    109  * The index structures are hashed by the devmap_handle, parent node's first
     111 * The index structures are hashed by the service_id, parent node's first
    110112 * cluster and index within the parent directory.
    111113 */
    112114static hash_table_t up_hash;
    113115
    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 
    121 static 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 
    149 static 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];
     116typedef struct {
     117        service_id_t service_id;
    152118        exfat_cluster_t pfc;
    153119        unsigned pdi;
    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 
    171 static void pos_remove_callback(link_t *item)
    172 {
    173         /* nothing to do */
    174 }
    175 
    176 static hash_table_operations_t uph_ops = {
     120} pos_key_t;
     121
     122static 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
     131static 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
     144static 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
     154static hash_table_ops_t uph_ops = {
    177155        .hash = pos_hash,
    178         .compare = pos_compare,
    179         .remove_callback = pos_remove_callback,
     156        .key_hash = pos_key_hash,
     157        .key_equal = pos_key_equal,
     158        .equal = NULL,
     159        .remove_callback = NULL,
    180160};
    181161
    182162/**
    183163 * Global hash table of all used fat_idx_t structures.
    184  * The index structures are hashed by the devmap_handle and index.
     164 * The index structures are hashed by the service_id and index.
    185165 */
    186166static hash_table_t ui_hash;
    187167
    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 
    194 static 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 
    208 static 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];
     168typedef struct {
     169        service_id_t service_id;
    211170        fs_index_t index;
    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 
    228 static void idx_remove_callback(link_t *item)
    229 {
    230         exfat_idx_t *fidx = list_get_instance(item, exfat_idx_t, uih_link);
     171} idx_key_t;
     172
     173static 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
     179static 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
     185static 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
     193static void idx_remove_callback(ht_link_t *item)
     194{
     195        exfat_idx_t *fidx = hash_table_get_inst(item, exfat_idx_t, uih_link);
    231196
    232197        free(fidx);
    233198}
    234199
    235 static hash_table_operations_t uih_ops = {
     200static hash_table_ops_t uih_ops = {
    236201        .hash = idx_hash,
    237         .compare = idx_compare,
     202        .key_hash = idx_key_hash,
     203        .key_equal = idx_key_equal,
     204        .equal = NULL,
    238205        .remove_callback = idx_remove_callback,
    239206};
    240207
    241208/** Allocate a VFS index which is not currently in use. */
    242 static bool exfat_index_alloc(devmap_handle_t devmap_handle, fs_index_t *index)
     209static bool exfat_index_alloc(service_id_t service_id, fs_index_t *index)
    243210{
    244211        unused_t *u;
    245212       
    246213        assert(index);
    247         u = unused_find(devmap_handle, true);
     214        u = unused_find(service_id, true);
    248215        if (!u)
    249216                return false;   
     
    302269
    303270/** Free a VFS index, which is no longer in use. */
    304 static void exfat_index_free(devmap_handle_t devmap_handle, fs_index_t index)
     271static void exfat_index_free(service_id_t service_id, fs_index_t index)
    305272{
    306273        unused_t *u;
    307274
    308         u = unused_find(devmap_handle, true);
     275        u = unused_find(service_id, true);
    309276        assert(u);
    310277
     
    364331}
    365332
    366 static int exfat_idx_create(exfat_idx_t **fidxp, devmap_handle_t devmap_handle)
     333static int exfat_idx_create(exfat_idx_t **fidxp, service_id_t service_id)
    367334{
    368335        exfat_idx_t *fidx;
     
    371338        if (!fidx)
    372339                return ENOMEM;
    373         if (!exfat_index_alloc(devmap_handle, &fidx->index)) {
     340        if (!exfat_index_alloc(service_id, &fidx->index)) {
    374341                free(fidx);
    375342                return ENOSPC;
    376343        }
    377344               
    378         link_initialize(&fidx->uph_link);
    379         link_initialize(&fidx->uih_link);
    380345        fibril_mutex_initialize(&fidx->lock);
    381         fidx->devmap_handle = devmap_handle;
     346        fidx->service_id = service_id;
    382347        fidx->pfc = 0;  /* no parent yet */
    383348        fidx->pdi = 0;
     
    388353}
    389354
    390 int exfat_idx_get_new(exfat_idx_t **fidxp, devmap_handle_t devmap_handle)
     355int exfat_idx_get_new(exfat_idx_t **fidxp, service_id_t service_id)
    391356{
    392357        exfat_idx_t *fidx;
     
    394359
    395360        fibril_mutex_lock(&used_lock);
    396         rc = exfat_idx_create(&fidx, devmap_handle);
     361        rc = exfat_idx_create(&fidx, service_id);
    397362        if (rc != EOK) {
    398363                fibril_mutex_unlock(&used_lock);
     
    400365        }
    401366               
    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);
     367        hash_table_insert(&ui_hash, &fidx->uih_link);
    408368        fibril_mutex_lock(&fidx->lock);
    409369        fibril_mutex_unlock(&used_lock);
     
    414374
    415375exfat_idx_t *
    416 exfat_idx_get_by_pos(devmap_handle_t devmap_handle, exfat_cluster_t pfc, unsigned pdi)
     376exfat_idx_get_by_pos(service_id_t service_id, exfat_cluster_t pfc, unsigned pdi)
    417377{
    418378        exfat_idx_t *fidx;
    419         link_t *l;
    420         unsigned long pkey[] = {
    421                 [UPH_DH_KEY] = devmap_handle,
    422                 [UPH_PFC_KEY] = pfc,
    423                 [UPH_PDI_KEY] = pdi,
     379       
     380        pos_key_t pos_key = {
     381                .service_id = service_id,
     382                .pfc = pfc,
     383                .pdi = pdi,
    424384        };
    425385
    426386        fibril_mutex_lock(&used_lock);
    427         l = hash_table_find(&up_hash, pkey);
     387        ht_link_t *l = hash_table_find(&up_hash, &pos_key);
    428388        if (l) {
    429                 fidx = hash_table_get_instance(l, exfat_idx_t, uph_link);
     389                fidx = hash_table_get_inst(l, exfat_idx_t, uph_link);
    430390        } else {
    431391                int rc;
    432392
    433                 rc = exfat_idx_create(&fidx, devmap_handle);
     393                rc = exfat_idx_create(&fidx, service_id);
    434394                if (rc != EOK) {
    435395                        fibril_mutex_unlock(&used_lock);
     
    437397                }
    438398               
    439                 unsigned long ikey[] = {
    440                         [UIH_DH_KEY] = devmap_handle,
    441                         [UIH_INDEX_KEY] = fidx->index,
    442                 };
    443        
    444399                fidx->pfc = pfc;
    445400                fidx->pdi = pdi;
    446401
    447                 hash_table_insert(&up_hash, pkey, &fidx->uph_link);
    448                 hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
     402                hash_table_insert(&up_hash, &fidx->uph_link);
     403                hash_table_insert(&ui_hash, &fidx->uih_link);
    449404        }
    450405        fibril_mutex_lock(&fidx->lock);
     
    456411void exfat_idx_hashin(exfat_idx_t *idx)
    457412{
    458         unsigned long pkey[] = {
    459                 [UPH_DH_KEY] = idx->devmap_handle,
    460                 [UPH_PFC_KEY] = idx->pfc,
    461                 [UPH_PDI_KEY] = idx->pdi,
     413        fibril_mutex_lock(&used_lock);
     414        hash_table_insert(&up_hash, &idx->uph_link);
     415        fibril_mutex_unlock(&used_lock);
     416}
     417
     418void exfat_idx_hashout(exfat_idx_t *idx)
     419{
     420        fibril_mutex_lock(&used_lock);
     421        hash_table_remove_item(&up_hash, &idx->uph_link);
     422        fibril_mutex_unlock(&used_lock);
     423}
     424
     425exfat_idx_t *
     426exfat_idx_get_by_index(service_id_t service_id, fs_index_t index)
     427{
     428        exfat_idx_t *fidx = NULL;
     429
     430        idx_key_t idx_key = {
     431                .service_id = service_id,
     432                .index = index,
    462433        };
    463434
    464435        fibril_mutex_lock(&used_lock);
    465         hash_table_insert(&up_hash, pkey, &idx->uph_link);
    466         fibril_mutex_unlock(&used_lock);
    467 }
    468 
    469 void exfat_idx_hashout(exfat_idx_t *idx)
    470 {
    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 
    477         fibril_mutex_lock(&used_lock);
    478         hash_table_remove(&up_hash, pkey, 3);
    479         fibril_mutex_unlock(&used_lock);
    480 }
    481 
    482 exfat_idx_t *
    483 exfat_idx_get_by_index(devmap_handle_t devmap_handle, fs_index_t index)
    484 {
    485         exfat_idx_t *fidx = NULL;
    486         link_t *l;
    487         unsigned long ikey[] = {
    488                 [UIH_DH_KEY] = devmap_handle,
    489                 [UIH_INDEX_KEY] = index,
    490         };
    491 
    492         fibril_mutex_lock(&used_lock);
    493         l = hash_table_find(&ui_hash, ikey);
     436        ht_link_t *l = hash_table_find(&ui_hash, &idx_key);
    494437        if (l) {
    495                 fidx = hash_table_get_instance(l, exfat_idx_t, uih_link);
     438                fidx = hash_table_get_inst(l, exfat_idx_t, uih_link);
    496439                fibril_mutex_lock(&fidx->lock);
    497440        }
     
    507450void exfat_idx_destroy(exfat_idx_t *idx)
    508451{
    509         unsigned long ikey[] = {
    510                 [UIH_DH_KEY] = idx->devmap_handle,
    511                 [UIH_INDEX_KEY] = idx->index,
     452        idx_key_t idx_key = {
     453                .service_id = idx->service_id,
     454                .index = idx->index,
    512455        };
    513         devmap_handle_t devmap_handle = idx->devmap_handle;
    514         fs_index_t index = idx->index;
    515456
    516457        /* TODO: assert(idx->pfc == FAT_CLST_RES0); */
     
    523464         * the index hash only.
    524465         */
    525         hash_table_remove(&ui_hash, ikey, 2);
     466        hash_table_remove(&ui_hash, &idx_key);
    526467        fibril_mutex_unlock(&used_lock);
    527468        /* Release the VFS index. */
    528         exfat_index_free(devmap_handle, index);
     469        exfat_index_free(idx_key.service_id, idx_key.index);
    529470        /* The index structure itself is freed in idx_remove_callback(). */
    530471}
     
    532473int exfat_idx_init(void)
    533474{
    534         if (!hash_table_create(&up_hash, UPH_BUCKETS, 3, &uph_ops))
     475        if (!hash_table_create(&up_hash, 0, 0, &uph_ops))
    535476                return ENOMEM;
    536         if (!hash_table_create(&ui_hash, UIH_BUCKETS, 2, &uih_ops)) {
     477        if (!hash_table_create(&ui_hash, 0, 0, &uih_ops)) {
    537478                hash_table_destroy(&up_hash);
    538479                return ENOMEM;
     
    544485{
    545486        /* We assume the hash tables are empty. */
     487        assert(hash_table_empty(&up_hash) && hash_table_empty(&ui_hash));
    546488        hash_table_destroy(&up_hash);
    547489        hash_table_destroy(&ui_hash);
    548490}
    549491
    550 int exfat_idx_init_by_devmap_handle(devmap_handle_t devmap_handle)
     492int exfat_idx_init_by_service_id(service_id_t service_id)
    551493{
    552494        unused_t *u;
     
    556498        if (!u)
    557499                return ENOMEM;
    558         unused_initialize(u, devmap_handle);
     500        unused_initialize(u, service_id);
    559501        fibril_mutex_lock(&unused_lock);
    560         if (!unused_find(devmap_handle, false)) {
     502        if (!unused_find(service_id, false)) {
    561503                list_append(&u->link, &unused_list);
    562504        } else {
     
    568510}
    569511
    570 void 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 
     512static 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
     524static 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
     536void exfat_idx_fini_by_service_id(service_id_t service_id)
     537{
    579538        /*
    580539         * Remove this instance's index structure from up_hash and ui_hash.
     
    583542         */
    584543        fibril_mutex_lock(&used_lock);
    585         hash_table_remove(&up_hash, pkey, 1);
    586         hash_table_remove(&ui_hash, ikey, 1);
     544        hash_table_apply(&up_hash, rm_pos_service_id, &service_id);
     545        hash_table_apply(&ui_hash, rm_idx_service_id, &service_id);
    587546        fibril_mutex_unlock(&used_lock);
    588547
     
    590549         * Free the unused and freed structures for this instance.
    591550         */
    592         unused_t *u = unused_find(devmap_handle, true);
     551        unused_t *u = unused_find(service_id, true);
    593552        assert(u);
    594553        list_remove(&u->link);
Note: See TracChangeset for help on using the changeset viewer.