Changeset 0ca7286 in mainline for uspace/srv/fs/mfs/mfs_ops.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/mfs/mfs_ops.c

    r1c1da4b r0ca7286  
    4040#define OPEN_NODES_SERVICE_KEY 0
    4141#define OPEN_NODES_INODE_KEY 1
    42 #define OPEN_NODES_BUCKETS 256
    4342
    4443static bool check_magic_number(uint16_t magic, bool *native,
    … …  
    6160static int mfs_unlink(fs_node_t *, fs_node_t *, const char *name);
    6261static int mfs_destroy_node(fs_node_t *fn);
    63 static hash_index_t open_nodes_hash(unsigned long key[]);
    64 static int open_nodes_compare(unsigned long key[], hash_count_t keys,
    65     link_t *item);
    66 static void open_nodes_remove_cb(link_t *link);
     62static size_t open_nodes_hash(const link_t *item);
     63static size_t open_nodes_key_hash(unsigned long key[]);
     64static bool open_nodes_match(unsigned long key[], size_t keys,
     65    const link_t *item);
    6766static int mfs_node_get(fs_node_t **rfn, service_id_t service_id,
    6867    fs_index_t index);
    … …  
    9594
    9695/* Hash table interface for open nodes hash table */
    97 static hash_index_t
    98 open_nodes_hash(unsigned long key[])
    99 {
    100         /* TODO: This is very simple and probably can be improved */
    101         return key[OPEN_NODES_INODE_KEY] % OPEN_NODES_BUCKETS;
    102 }
    103 
    104 static int
    105 open_nodes_compare(unsigned long key[], hash_count_t keys,
    106     link_t *item)
    107 {
     96
     97static size_t
     98open_nodes_key_hash(unsigned long key[])
     99{
     100        /* As recommended by Effective Java, 2nd Edition. */
     101        size_t hash = 17;
     102        hash = 37 * hash + key[OPEN_NODES_SERVICE_KEY];
     103        hash = 37 * hash + key[OPEN_NODES_INODE_KEY];
     104        return hash;
     105}
     106
     107static size_t
     108open_nodes_hash(const link_t *item)
     109{
     110        struct mfs_node *m = hash_table_get_instance(item, struct mfs_node, link);
     111       
     112        unsigned long key[] = {
     113                [OPEN_NODES_SERVICE_KEY] = m->instance->service_id,
     114                [OPEN_NODES_INODE_KEY] = m->ino_i->index,
     115        };
     116       
     117        return open_nodes_key_hash(key);
     118}
     119
     120static bool
     121open_nodes_match(unsigned long key[], size_t keys, const link_t *item)
     122{
     123        assert(keys == 2);
    108124        struct mfs_node *mnode = hash_table_get_instance(item, struct mfs_node, link);
    109         assert(keys > 0);
    110         if (mnode->instance->service_id !=
    111             ((service_id_t) key[OPEN_NODES_SERVICE_KEY])) {
    112                 return false;
    113         }
    114         if (keys == 1) {
    115                 return true;
    116         }
    117         assert(keys == 2);
    118         return (mnode->ino_i->index == key[OPEN_NODES_INODE_KEY]);
    119 }
    120 
    121 static void
    122 open_nodes_remove_cb(link_t *link)
    123 {
    124         /* We don't use remove callback for this hash table */
    125 }
    126 
    127 static hash_table_operations_t open_nodes_ops = {
     125       
     126        service_id_t service_id = ((service_id_t) key[OPEN_NODES_SERVICE_KEY]);
     127       
     128        return mnode->instance->service_id == service_id
     129                && mnode->ino_i->index == key[OPEN_NODES_INODE_KEY];
     130}
     131
     132
     133static hash_table_ops_t open_nodes_ops = {
    128134        .hash = open_nodes_hash,
    129         .compare = open_nodes_compare,
    130         .remove_callback = open_nodes_remove_cb,
     135        .key_hash = open_nodes_key_hash,
     136        .match = open_nodes_match,
     137        .equal = 0,
     138        .remove_callback = 0,
    131139};
    132140
    … …  
    134142mfs_global_init(void)
    135143{
    136         if (!hash_table_create(&open_nodes, OPEN_NODES_BUCKETS,
    137             OPEN_NODES_KEYS, &open_nodes_ops)) {
     144        if (!hash_table_create(&open_nodes, 0, OPEN_NODES_KEYS, &open_nodes_ops)) {
    138145                return ENOMEM;
    139146        }
    … …  
    408415        link_initialize(&mnode->link);
    409416
    410         unsigned long key[] = {
    411                 [OPEN_NODES_SERVICE_KEY] = inst->service_id,
    412                 [OPEN_NODES_INODE_KEY] = inum,
    413         };
    414 
    415417        fibril_mutex_lock(&open_nodes_lock);
    416         hash_table_insert(&open_nodes, key, &mnode->link);
     418        hash_table_insert(&open_nodes, &mnode->link);
    417419        fibril_mutex_unlock(&open_nodes_lock);
    418420        inst->open_nodes_cnt++;
    … …  
    621623        *rfn = node;
    622624
    623         hash_table_insert(&open_nodes, key, &mnode->link);
     625        hash_table_insert(&open_nodes, &mnode->link);
    624626        inst->open_nodes_cnt++;
    625627
Note: See TracChangeset for help on using the changeset viewer.