Changeset 0ca7286 in mainline for uspace/srv/fs/fat/fat_idx.c


Ignore:
Timestamp:
2012-07-21T11:19:27Z (12 years ago)
Author:
Adam Hraska <adam.hraska+hos@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
2732c94
Parents:
1c1da4b
Message:

Added resizing to user space (single-threaded) hash_table. Resizes in a way to mitigate effects of bad hash functions. Change of interface affected many files.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • uspace/srv/fs/fat/fat_idx.c

    r1c1da4b r0ca7286  
    4646#include <malloc.h>
    4747
     48
    4849/** Each instance of this type describes one interval of freed VFS indices. */
    4950typedef struct {
    … …  
    113114static hash_table_t up_hash;
    114115
    115 #define UPH_BUCKETS_LOG 12
    116 #define UPH_BUCKETS     (1 << UPH_BUCKETS_LOG)
    117 
    118116#define UPH_SID_KEY     0
    119117#define UPH_PFC_KEY     1
    120118#define UPH_PDI_KEY     2
    121119
    122 static hash_index_t pos_hash(unsigned long key[])
    123 {
    124         service_id_t service_id = (service_id_t)key[UPH_SID_KEY];
    125         fat_cluster_t pfc = (fat_cluster_t)key[UPH_PFC_KEY];
    126         unsigned pdi = (unsigned)key[UPH_PDI_KEY];
    127 
    128         hash_index_t h;
    129 
    130         /*
    131          * The least significant half of all bits are the least significant bits
    132          * of the parent node's first cluster.
    133          *
    134          * The least significant half of the most significant half of all bits
    135          * are the least significant bits of the node's dentry index within the
    136          * parent directory node.
    137          *
    138          * The most significant half of the most significant half of all bits
    139          * are the least significant bits of the device handle.
    140          */
    141         h = pfc & ((1 << (UPH_BUCKETS_LOG / 2)) - 1);
    142         h |= (pdi & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
    143             (UPH_BUCKETS_LOG / 2);
    144         h |= (service_id & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
    145             (3 * (UPH_BUCKETS_LOG / 4));
    146 
    147         return h;
    148 }
    149 
    150 static int pos_compare(unsigned long key[], hash_count_t keys, link_t *item)
     120static size_t pos_key_hash(unsigned long key[])
     121{
     122        /* Inspired by Effective Java, 2nd edition. */
     123        size_t hash = 17;
     124       
     125        hash = 31 * hash + key[UPH_PFC_KEY];
     126        hash = 31 * hash + key[UPH_PDI_KEY];
     127        hash = 31 * hash + key[UPH_SID_KEY];
     128       
     129        return hash;
     130}
     131
     132static size_t pos_hash(const link_t *item)
     133{
     134        fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uph_link);
     135       
     136        unsigned long pkey[] = {
     137                [UPH_SID_KEY] = fidx->service_id,
     138                [UPH_PFC_KEY] = fidx->pfc,
     139                [UPH_PDI_KEY] = fidx->pdi,
     140        };
     141       
     142        return pos_key_hash(pkey);
     143}
     144
     145static bool pos_match(unsigned long key[], size_t keys, const link_t *item)
    151146{
    152147        service_id_t service_id = (service_id_t)key[UPH_SID_KEY];
    … …  
    170165}
    171166
    172 static void pos_remove_callback(link_t *item)
    173 {
    174         /* nothing to do */
    175 }
    176 
    177 static hash_table_operations_t uph_ops = {
     167static hash_table_ops_t uph_ops = {
    178168        .hash = pos_hash,
    179         .compare = pos_compare,
    180         .remove_callback = pos_remove_callback,
     169        .key_hash = pos_key_hash,
     170        .match = pos_match,
     171        .equal = 0,
     172        .remove_callback = 0,
    181173};
    182174
    … …  
    187179static hash_table_t ui_hash;
    188180
    189 #define UIH_BUCKETS_LOG 12
    190 #define UIH_BUCKETS     (1 << UIH_BUCKETS_LOG)
    191 
    192181#define UIH_SID_KEY     0
    193182#define UIH_INDEX_KEY   1
    194183
    195 static hash_index_t idx_hash(unsigned long key[])
    196 {
    197         service_id_t service_id = (service_id_t)key[UIH_SID_KEY];
    198         fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];
    199 
    200         hash_index_t h;
    201 
    202         h = service_id & ((1 << (UIH_BUCKETS_LOG / 2)) - 1);
    203         h |= (index & ((1 << (UIH_BUCKETS_LOG / 2)) - 1)) <<
    204             (UIH_BUCKETS_LOG / 2);
    205 
    206         return h;
    207 }
    208 
    209 static int idx_compare(unsigned long key[], hash_count_t keys, link_t *item)
     184static size_t idx_key_hash(unsigned long key[])
     185{
     186        /*
     187         * Compute a simple hash unlimited by specific table size as per:
     188         * Effective Java, 2nd edition.
     189         */
     190        size_t hash = 17;
     191        hash = 31 * hash + key[UIH_SID_KEY];
     192        hash = 31 * hash + key[UIH_INDEX_KEY];
     193        return hash;
     194}
     195
     196static size_t idx_hash(const link_t *item)
     197{
     198        fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uih_link);
     199       
     200        unsigned long ikey[] = {
     201                [UIH_SID_KEY] = fidx->service_id,
     202                [UIH_INDEX_KEY] = fidx->index,
     203        };
     204
     205        return idx_key_hash(ikey);
     206}
     207
     208static bool idx_match(unsigned long key[], size_t keys, const link_t *item)
    210209{
    211210        service_id_t service_id = (service_id_t)key[UIH_SID_KEY];
    … …  
    234233}
    235234
    236 static hash_table_operations_t uih_ops = {
     235static hash_table_ops_t uih_ops = {
    237236        .hash = idx_hash,
    238         .compare = idx_compare,
     237        .key_hash = idx_key_hash,
     238        .match = idx_match,
     239        .equal = 0,
    239240        .remove_callback = idx_remove_callback,
    240241};
    … …  
    401402        }
    402403               
    403         unsigned long ikey[] = {
    404                 [UIH_SID_KEY] = service_id,
    405                 [UIH_INDEX_KEY] = fidx->index,
    406         };
    407        
    408         hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
     404        hash_table_insert(&ui_hash, &fidx->uih_link);
    409405        fibril_mutex_lock(&fidx->lock);
    410406        fibril_mutex_unlock(&used_lock);
    … …  
    438434                }
    439435               
    440                 unsigned long ikey[] = {
    441                         [UIH_SID_KEY] = service_id,
    442                         [UIH_INDEX_KEY] = fidx->index,
    443                 };
    444        
    445436                fidx->pfc = pfc;
    446437                fidx->pdi = pdi;
    447438
    448                 hash_table_insert(&up_hash, pkey, &fidx->uph_link);
    449                 hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
     439                hash_table_insert(&up_hash, &fidx->uph_link);
     440                hash_table_insert(&ui_hash, &fidx->uih_link);
    450441        }
    451442        fibril_mutex_lock(&fidx->lock);
    … …  
    457448void fat_idx_hashin(fat_idx_t *idx)
    458449{
    459         unsigned long pkey[] = {
    460                 [UPH_SID_KEY] = idx->service_id,
    461                 [UPH_PFC_KEY] = idx->pfc,
    462                 [UPH_PDI_KEY] = idx->pdi,
    463         };
    464 
    465         fibril_mutex_lock(&used_lock);
    466         hash_table_insert(&up_hash, pkey, &idx->uph_link);
     450        fibril_mutex_lock(&used_lock);
     451        hash_table_insert(&up_hash, &idx->uph_link);
    467452        fibril_mutex_unlock(&used_lock);
    468453}
    … …  
    470455void fat_idx_hashout(fat_idx_t *idx)
    471456{
    472         unsigned long pkey[] = {
    473                 [UPH_SID_KEY] = idx->service_id,
    474                 [UPH_PFC_KEY] = idx->pfc,
    475                 [UPH_PDI_KEY] = idx->pdi,
    476         };
    477 
    478         fibril_mutex_lock(&used_lock);
    479         hash_table_remove(&up_hash, pkey, 3);
     457        fibril_mutex_lock(&used_lock);
     458        hash_table_remove_item(&up_hash, &idx->uph_link);
    480459        fibril_mutex_unlock(&used_lock);
    481460}
    … …  
    532511int fat_idx_init(void)
    533512{
    534         if (!hash_table_create(&up_hash, UPH_BUCKETS, 3, &uph_ops))
     513        if (!hash_table_create(&up_hash, 0, 3, &uph_ops))
    535514                return ENOMEM;
    536         if (!hash_table_create(&ui_hash, UIH_BUCKETS, 2, &uih_ops)) {
     515        if (!hash_table_create(&ui_hash, 0, 2, &uih_ops)) {
    537516                hash_table_destroy(&up_hash);
    538517                return ENOMEM;
Note: See TracChangeset for help on using the changeset viewer.