Changeset 82cbf8c6 in mainline


Ignore:
Timestamp:
2017-10-08T19:37:24Z (7 years ago)
Author:
Jakub Jermar <jakub@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
2fd26bb
Parents:
81b9d3e
Message:

Replace the old hash table implementation in the kernel with the newer one

This replaces the original hash table implementation with the resizable one
already used in uspace. Along the way, the IRQ hash table code was streamlined
and cleaned up.

Location:
kernel
Files:
14 edited

Legend:

Unmodified
Added
Removed

  • kernel/genarch/include/genarch/mm/as_ht.h

    r81b9d3e r82cbf8c6  
    3737
    3838#include <mm/mm.h>
    39 #include <adt/list.h>
     39#include <adt/hash_table.h>
    4040#include <typedefs.h>
    4141
    … …  
    4646
    4747typedef struct pte {
    48         link_t link;            /**< Page hash table link. */
     48        ht_link_t link;         /**< Page hash table link. */
    4949        struct as *as;          /**< Address space. */
    5050        uintptr_t page;         /**< Virtual memory page. */

  • kernel/genarch/include/genarch/mm/page_ht.h

    r81b9d3e r82cbf8c6  
    4646#include <adt/hash_table.h>
    4747
    48 #define PAGE_HT_KEYS  2
    4948#define KEY_AS        0
    5049#define KEY_PAGE      1
    51 
    52 #define PAGE_HT_ENTRIES_BITS  13
    53 #define PAGE_HT_ENTRIES       (1 << PAGE_HT_ENTRIES_BITS)
    5450
    5551/* Macros for querying page hash table PTEs. */
    … …  
    6662extern slab_cache_t *pte_cache;
    6763extern hash_table_t page_ht;
    68 extern hash_table_operations_t ht_operations;
     64extern hash_table_ops_t ht_ops;
    6965
    7066#endif

  • kernel/genarch/src/mm/as_ht.c

    r81b9d3e r82cbf8c6  
    7575{
    7676        if (flags & FLAG_AS_KERNEL) {
    77                 hash_table_create(&page_ht, PAGE_HT_ENTRIES, 2, &ht_operations);
     77                hash_table_create(&page_ht, 0, 0, &ht_ops);
    7878                pte_cache = slab_cache_create("pte_t", sizeof(pte_t), 0,
    7979                    NULL, NULL, SLAB_CACHE_MAGDEFERRED);

  • kernel/genarch/src/mm/page_ht.c

    r81b9d3e r82cbf8c6  
    4949#include <arch.h>
    5050#include <assert.h>
     51#include <adt/hash.h>
    5152#include <adt/hash_table.h>
    5253#include <align.h>
    5354
    54 static size_t hash(sysarg_t[]);
    55 static bool compare(sysarg_t[], size_t, link_t *);
    56 static void remove_callback(link_t *);
     55static size_t ht_hash(const ht_link_t *);
     56static size_t ht_key_hash(void *);
     57static bool ht_key_equal(void *, const ht_link_t *);
     58static void ht_remove_callback(ht_link_t *);
    5759
    5860static void ht_mapping_insert(as_t *, uintptr_t, uintptr_t, unsigned int);
    … …  
    8082
    8183/** Hash table operations for page hash table. */
    82 hash_table_operations_t ht_operations = {
    83         .hash = hash,
    84         .compare = compare,
    85         .remove_callback = remove_callback
     84hash_table_ops_t ht_ops = {
     85        .hash = ht_hash,
     86        .key_hash = ht_key_hash,
     87        .key_equal = ht_key_equal,
     88        .remove_callback = ht_remove_callback
    8689};
    8790
    … …  
    9598};
    9699
    97 /** Compute page hash table index.
    98  *
    99  * @param key Array of two keys (i.e. page and address space).
    100  *
    101  * @return Index into page hash table.
    102  *
    103  */
    104 size_t hash(sysarg_t key[])
    105 {
    106         as_t *as = (as_t *) key[KEY_AS];
    107         uintptr_t page = (uintptr_t) key[KEY_PAGE];
    108        
    109         /*
    110          * Virtual page addresses have roughly the same probability
    111          * of occurring. Least significant bits of VPN compose the
    112          * hash index.
    113          *
    114          */
    115         size_t index = ((page >> PAGE_WIDTH) & (PAGE_HT_ENTRIES - 1));
    116        
    117         /*
    118          * Address space structures are likely to be allocated from
    119          * similar addresses. Least significant bits compose the
    120          * hash index.
    121          *
    122          */
    123         index |= ((sysarg_t) as) & (PAGE_HT_ENTRIES - 1);
    124        
    125         return index;
    126 }
    127 
    128 /** Compare page hash table item with page and/or address space.
    129  *
    130  * @param key  Array of one or two keys (i.e. page and/or address space).
    131  * @param keys Number of keys passed.
    132  * @param item Item to compare the keys with.
    133  *
    134  * @return true on match, false otherwise.
    135  *
    136  */
    137 bool compare(sysarg_t key[], size_t keys, link_t *item)
     100/** Return the hash of the key stored in the item */
     101size_t ht_hash(const ht_link_t *item)
     102{
     103        pte_t *pte = hash_table_get_inst(item, pte_t, link);
     104        size_t hash = 0;
     105        hash = hash_combine(hash, (uintptr_t) pte->as);
     106        hash = hash_combine(hash, pte->page >> PAGE_WIDTH);
     107        return hash;
     108}
     109
     110/** Return the hash of the key. */
     111size_t ht_key_hash(void *arg)
     112{
     113        uintptr_t *key = (uintptr_t *) arg;
     114        size_t hash = 0;
     115        hash = hash_combine(hash, key[KEY_AS]);
     116        hash = hash_combine(hash, key[KEY_PAGE] >> PAGE_WIDTH);
     117        return hash;
     118}
     119
     120/** Return true if the key is equal to the item's lookup key. */
     121bool ht_key_equal(void *arg, const ht_link_t *item)
     122{
     123        uintptr_t *key = (uintptr_t *) arg;
     124        pte_t *pte = hash_table_get_inst(item, pte_t, link);
     125        return (key[KEY_AS] == (uintptr_t) pte->as) &&
     126            (key[KEY_PAGE] == pte->page);
     127}
     128
     129/** Callback on page hash table item removal.
     130 *
     131 * @param item Page hash table item being removed.
     132 *
     133 */
     134void ht_remove_callback(ht_link_t *item)
    138135{
    139136        assert(item);
    140         assert(keys > 0);
    141         assert(keys <= PAGE_HT_KEYS);
    142        
    143         /*
    144          * Convert item to PTE.
    145          *
    146          */
    147         pte_t *pte = hash_table_get_instance(item, pte_t, link);
    148        
    149         if (keys == PAGE_HT_KEYS)
    150                 return (key[KEY_AS] == (uintptr_t) pte->as) &&
    151                     (key[KEY_PAGE] == pte->page);
    152        
    153         return (key[KEY_AS] == (uintptr_t) pte->as);
    154 }
    155 
    156 /** Callback on page hash table item removal.
    157  *
    158  * @param item Page hash table item being removed.
    159  *
    160  */
    161 void remove_callback(link_t *item)
    162 {
    163         assert(item);
    164        
    165         /*
    166          * Convert item to PTE.
    167          *
    168          */
    169         pte_t *pte = hash_table_get_instance(item, pte_t, link);
    170        
     137       
     138        pte_t *pte = hash_table_get_inst(item, pte_t, link);
    171139        slab_free(pte_cache, pte);
    172140}
    … …  
    186154    unsigned int flags)
    187155{
    188         sysarg_t key[2] = {
    189                 (uintptr_t) as,
    190                 page = ALIGN_DOWN(page, PAGE_SIZE)
     156        uintptr_t key[2] = {
     157                [KEY_AS] = (uintptr_t) as,
     158                [KEY_PAGE] = ALIGN_DOWN(page, PAGE_SIZE)
    191159        };
    192160
    … …  
    218186                write_barrier();
    219187               
    220                 hash_table_insert(&page_ht, key, &pte->link);
     188                hash_table_insert(&page_ht, &pte->link);
    221189        }
    222190
    … …  
    236204void ht_mapping_remove(as_t *as, uintptr_t page)
    237205{
    238         sysarg_t key[2] = {
    239                 (uintptr_t) as,
    240                 page = ALIGN_DOWN(page, PAGE_SIZE)
     206        uintptr_t key[2] = {
     207                [KEY_AS] = (uintptr_t) as,
     208                [KEY_PAGE] = ALIGN_DOWN(page, PAGE_SIZE)
    241209        };
    242210
    … …  
    249217         * by remove_callback().
    250218         */
    251         hash_table_remove(&page_ht, key, 2);
     219        hash_table_remove(&page_ht, key);
    252220
    253221        irq_spinlock_unlock(&page_ht_lock, true);
    254222}
    255223
    256 static pte_t *ht_mapping_find_internal(as_t *as, uintptr_t page, bool nolock)
    257 {
    258         sysarg_t key[2] = {
    259                 (uintptr_t) as,
    260                 page = ALIGN_DOWN(page, PAGE_SIZE)
     224static pte_t *
     225ht_mapping_find_internal(as_t *as, uintptr_t page, bool nolock)
     226{
     227        uintptr_t key[2] = {
     228                [KEY_AS] = (uintptr_t) as,
     229                [KEY_PAGE] = ALIGN_DOWN(page, PAGE_SIZE)
    261230        };
    262231
    263232        assert(nolock || page_table_locked(as));
    264233
    265         link_t *cur = hash_table_find(&page_ht, key);
     234        ht_link_t *cur = hash_table_find(&page_ht, key);
    266235        if (cur)
    267                 return hash_table_get_instance(cur, pte_t, link);
     236                return hash_table_get_inst(cur, pte_t, link);
    268237       
    269238        return NULL;

  • kernel/generic/include/adt/hash.h

    r81b9d3e r82cbf8c6  
    4545         * Public domain.
    4646         */
    47         hash = ~hash + (hash << 15); 
     47        hash = ~hash + (hash << 15);
    4848        hash = hash ^ (hash >> 12);
    4949        hash = hash + (hash << 2);
    5050        hash = hash ^ (hash >> 4);
    51         hash = hash * 2057; 
     51        hash = hash * 2057;
    5252        hash = hash ^ (hash >> 16);
    53         return hash;   
     53        return hash;
    5454}
    5555
    … …  
    6565        hash = hash ^ (hash >> 4);
    6666        hash = hash * 0x27d4eb2d;
    67         hash = hash ^ (hash >> 15);     
    68         /* 
     67        hash = hash ^ (hash >> 15);
     68        /*
    6969         * Lower order bits are mixed more thoroughly. Swap them with
    7070         * the higher order bits and make the resulting higher order bits
    … …  
    105105         * http://burtleburtle.net/bob/c/lookup3.c
    106106         */
    107         seed ^= hash + 0x9e3779b9 
     107        seed ^= hash + 0x9e3779b9
    108108                + ((seed << 5) | (seed >> (sizeof(size_t) * 8 - 5)));
    109         return seed;   
     109        return seed;
    110110}
    111111

  • kernel/generic/include/adt/hash_table.h

    r81b9d3e r82cbf8c6  
    11/*
    22 * Copyright (c) 2006 Jakub Jermar
     3 * Copyright (c) 2012 Adam Hraska
     4 *
    35 * All rights reserved.
    46 *
    … …  
    2729 */
    2830
    29 /** @addtogroup genericadt
     31/** @addtogroup libc
    3032 * @{
    3133 */
    … …  
    3335 */
    3436
    35 #ifndef KERN_HASH_TABLE_H_
    36 #define KERN_HASH_TABLE_H_
     37#ifndef LIBC_HASH_TABLE_H_
     38#define LIBC_HASH_TABLE_H_
    3739
    3840#include <adt/list.h>
    39 #include <typedefs.h>
     41#include <stdbool.h>
     42#include <macros.h>
     43
     44/** Opaque hash table link type. */
     45typedef struct ht_link {
     46        link_t link;
     47} ht_link_t;
    4048
    4149/** Set of operations for hash table. */
    4250typedef struct {
    43         /** Hash function.
    44          *
    45          * @param key   Array of keys needed to compute hash index. All keys must
    46          *              be passed.
    47          *
    48          * @return Index into hash table.
    49          */
    50         size_t (* hash)(sysarg_t key[]);
     51        /** Returns the hash of the key stored in the item (ie its lookup key). */
     52        size_t (*hash)(const ht_link_t *item);
    5153       
    52         /** Hash table item comparison function.
    53          *
    54          * @param key   Array of keys that will be compared with item. It is not
    55          *              necessary to pass all keys.
    56          *
    57          * @return true if the keys match, false otherwise.
    58         */
    59         bool (*compare)(sysarg_t key[], size_t keys, link_t *item);
     54        /** Returns the hash of the key. */
     55        size_t (*key_hash)(void *key);
     56       
     57        /** True if the items are equal (have the same lookup keys). */
     58        bool (*equal)(const ht_link_t *item1, const ht_link_t *item2);
     59
     60        /** Returns true if the key is equal to the item's lookup key. */
     61        bool (*key_equal)(void *key, const ht_link_t *item);
    6062
    6163        /** Hash table item removal callback.
     64         *
     65         * Must not invoke any mutating functions of the hash table.
    6266         *
    6367         * @param item Item that was removed from the hash table.
    6468         */
    65         void (*remove_callback)(link_t *item);
    66 } hash_table_operations_t;
     69        void (*remove_callback)(ht_link_t *item);
     70} hash_table_ops_t;
    6771
    6872/** Hash table structure. */
    6973typedef struct {
    70         list_t *entry;
    71         size_t entries;
    72         size_t max_keys;
    73         hash_table_operations_t *op;
     74        hash_table_ops_t *op;
     75        list_t *bucket;
     76        size_t bucket_cnt;
     77        size_t full_item_cnt;
     78        size_t item_cnt;
     79        size_t max_load;
     80        bool apply_ongoing;
    7481} hash_table_t;
    7582
    76 #define hash_table_get_instance(item, type, member) \
    77         list_get_instance((item), type, member)
     83#define hash_table_get_inst(item, type, member) \
     84        member_to_inst((item), type, member)
    7885
    79 extern void hash_table_create(hash_table_t *h, size_t m, size_t max_keys,
    80     hash_table_operations_t *op);
    81 extern void hash_table_insert(hash_table_t *h, sysarg_t key[], link_t *item);
    82 extern link_t *hash_table_find(hash_table_t *h, sysarg_t key[]);
    83 extern void hash_table_remove(hash_table_t *h, sysarg_t key[], size_t keys);
    84 extern void hash_table_remove_item(hash_table_t *h, link_t *item);
     86extern bool hash_table_create(hash_table_t *, size_t, size_t,
     87        hash_table_ops_t *);
     88extern void hash_table_destroy(hash_table_t *);
     89
     90extern bool hash_table_empty(hash_table_t *);
     91extern size_t hash_table_size(hash_table_t *);
     92
     93extern void hash_table_clear(hash_table_t *);
     94extern void hash_table_insert(hash_table_t *, ht_link_t *);
     95extern bool hash_table_insert_unique(hash_table_t *, ht_link_t *);
     96extern ht_link_t *hash_table_find(const hash_table_t *, void *);
     97extern ht_link_t *hash_table_find_next(const hash_table_t *, ht_link_t *);
     98extern size_t hash_table_remove(hash_table_t *, void *);
     99extern void hash_table_remove_item(hash_table_t *, ht_link_t *);
     100extern void hash_table_apply(hash_table_t *, bool (*)(ht_link_t *, void *),
     101        void *);
     102
    85103
    86104#endif

  • kernel/generic/include/ddi/irq.h

    r81b9d3e r82cbf8c6  
    102102typedef struct irq {
    103103        /** Hash table link. */
    104         link_t link;
     104        ht_link_t link;
    105105       
    106106        /** Lock protecting everything in this structure

  • kernel/generic/include/lib/ra.h

    r81b9d3e r82cbf8c6  
    7171typedef struct {
    7272        link_t segment_link;    /**< Span's segment list link. */
    73         link_t fu_link;         /**< Span's free list or used hash link. */
     73
     74        /*
     75         * A segment cannot be both on the free list and in the used hash.
     76         * Their respective links can therefore occupy the same space.
     77         */
     78        union {
     79                link_t fl_link;         /**< Span's free list link. */
     80                ht_link_t uh_link;      /**< Span's used hash link. */
     81        };
    7482
    7583        uintptr_t base;         /**< Segment base. */

  • kernel/generic/include/synch/futex.h

    r81b9d3e r82cbf8c6  
    3838#include <typedefs.h>
    3939#include <synch/waitq.h>
     40#include <adt/hash_table.h>
    4041
    4142/** Kernel-side futex structure. */
    … …  
    4647        waitq_t wq;
    4748        /** Futex hash table link. */
    48         link_t ht_link;
     49        ht_link_t ht_link;
    4950        /** Number of tasks that reference this futex. */
    5051        size_t refcount;

  • kernel/generic/src/adt/hash_table.c

    r81b9d3e r82cbf8c6  
    11/*
    2  * Copyright (c) 2006 Jakub Jermar
     2 * Copyright (c) 2008 Jakub Jermar
     3 * Copyright (c) 2012 Adam Hraska
     4 *
    35 * All rights reserved.
    46 *
    … …  
    2729 */
    2830
    29 /** @addtogroup genericadt
     31/** @addtogroup libc
    3032 * @{
    3133 */
    32 
    33 /**
    34  * @file
    35  * @brief Implementation of generic chained hash table.
    36  *
    37  * This file contains implementation of generic chained hash table.
     34/** @file
     35 */
     36
     37/*
     38 * This is an implementation of a generic resizable chained hash table.
     39 *
     40 * The table grows to 2*n+1 buckets each time, starting at n == 89,
     41 * per Thomas Wang's recommendation:
     42 * http://www.concentric.net/~Ttwang/tech/hashsize.htm
     43 *
     44 * This policy produces prime table sizes for the first five resizes
     45 * and generally produces table sizes which are either prime or
     46 * have fairly large (prime/odd) divisors. Having a prime table size
     47 * mitigates the use of suboptimal hash functions and distributes
     48 * items over the whole table.
    3849 */
    3950
    4051#include <adt/hash_table.h>
    4152#include <adt/list.h>
     53#include <mm/slab.h>
    4254#include <assert.h>
    43 #include <typedefs.h>
    44 #include <mm/slab.h>
    45 #include <mem.h>
     55#include <str.h>
     56
     57/* Optimal initial bucket count. See comment above. */
     58#define HT_MIN_BUCKETS  89
     59/* The table is resized when the average load per bucket exceeds this number. */
     60#define HT_MAX_LOAD     2
     61
     62
     63static size_t round_up_size(size_t);
     64static bool alloc_table(size_t, list_t **);
     65static void clear_items(hash_table_t *);
     66static void resize(hash_table_t *, size_t);
     67static void grow_if_needed(hash_table_t *);
     68static void shrink_if_needed(hash_table_t *);
     69
     70/* Dummy do nothing callback to invoke in place of remove_callback == NULL. */
     71static void nop_remove_callback(ht_link_t *item)
     72{
     73        /* no-op */
     74}
     75
    4676
    4777/** Create chained hash table.
    4878 *
    49  * @param h Hash table structure. Will be initialized by this call.
    50  * @param m Number of slots in the hash table.
    51  * @param max_keys Maximal number of keys needed to identify an item.
    52  * @param op Hash table operations structure.
    53  */
    54 void hash_table_create(hash_table_t *h, size_t m, size_t max_keys, hash_table_operations_t *op)
    55 {
    56         size_t i;
    57 
     79 * @param h        Hash table structure. Will be initialized by this call.
     80 * @param init_size Initial desired number of hash table buckets. Pass zero
     81 *                 if you want the default initial size.
     82 * @param max_load The table is resized when the average load per bucket
     83 *                 exceeds this number. Pass zero if you want the default.
     84 * @param op       Hash table operations structure. remove_callback()
     85 *                 is optional and can be NULL if no action is to be taken
     86 *                 upon removal. equal() is optional if and only if
     87 *                 hash_table_insert_unique() will never be invoked.
     88 *                 All other operations are mandatory.
     89 *
     90 * @return True on success
     91 *
     92 */
     93bool hash_table_create(hash_table_t *h, size_t init_size, size_t max_load,
     94    hash_table_ops_t *op)
     95{
    5896        assert(h);
    59         assert(op);
    60         assert(op->hash);
    61         assert(op->compare);
    62         assert(max_keys > 0);
    63        
    64         h->entry = (list_t *) malloc(m * sizeof(list_t), 0);
    65         if (!h->entry)
    66                 panic("Cannot allocate memory for hash table.");
    67        
    68         memsetb(h->entry, m * sizeof(list_t), 0);
    69        
    70         for (i = 0; i < m; i++)
    71                 list_initialize(&h->entry[i]);
    72        
    73         h->entries = m;
    74         h->max_keys = max_keys;
     97        assert(op && op->hash && op->key_hash && op->key_equal);
     98       
     99        /* Check for compulsory ops. */
     100        if (!op || !op->hash || !op->key_hash || !op->key_equal)
     101                return false;
     102       
     103        h->bucket_cnt = round_up_size(init_size);
     104       
     105        if (!alloc_table(h->bucket_cnt, &h->bucket))
     106                return false;
     107       
     108        h->max_load = (max_load == 0) ? HT_MAX_LOAD : max_load;
     109        h->item_cnt = 0;
    75110        h->op = op;
    76 }
    77 
    78 /** Insert item into hash table.
    79  *
    80  * @param h Hash table.
    81  * @param key Array of all keys necessary to compute hash index.
     111        h->full_item_cnt = h->max_load * h->bucket_cnt;
     112        h->apply_ongoing = false;
     113
     114        if (h->op->remove_callback == NULL) {
     115                h->op->remove_callback = nop_remove_callback;
     116        }
     117       
     118        return true;
     119}
     120
     121/** Destroy a hash table instance.
     122 *
     123 * @param h Hash table to be destroyed.
     124 *
     125 */
     126void hash_table_destroy(hash_table_t *h)
     127{
     128        assert(h && h->bucket);
     129        assert(!h->apply_ongoing);
     130       
     131        clear_items(h);
     132       
     133        free(h->bucket);
     134
     135        h->bucket = NULL;
     136        h->bucket_cnt = 0;
     137}
     138
     139/** Returns true if there are no items in the table. */
     140bool hash_table_empty(hash_table_t *h)
     141{
     142        assert(h && h->bucket);
     143        return h->item_cnt == 0;
     144}
     145
     146/** Returns the number of items in the table. */
     147size_t hash_table_size(hash_table_t *h)
     148{
     149        assert(h && h->bucket);
     150        return h->item_cnt;
     151}
     152
     153/** Remove all elements from the hash table
     154 *
     155 * @param h Hash table to be cleared
     156 */
     157void hash_table_clear(hash_table_t *h)
     158{
     159        assert(h && h->bucket);
     160        assert(!h->apply_ongoing);
     161       
     162        clear_items(h);
     163       
     164        /* Shrink the table to its minimum size if possible. */
     165        if (HT_MIN_BUCKETS < h->bucket_cnt) {
     166                resize(h, HT_MIN_BUCKETS);
     167        }
     168}
     169
     170/** Unlinks and removes all items but does not resize. */
     171static void clear_items(hash_table_t *h)
     172{
     173        if (h->item_cnt == 0)
     174                return;
     175       
     176        for (size_t idx = 0; idx < h->bucket_cnt; ++idx) {
     177                list_foreach_safe(h->bucket[idx], cur, next) {
     178                        assert(cur);
     179                        ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
     180                       
     181                        list_remove(cur);
     182                        h->op->remove_callback(cur_link);
     183                }
     184        }
     185       
     186        h->item_cnt = 0;
     187}
     188
     189/** Insert item into a hash table.
     190 *
     191 * @param h    Hash table.
    82192 * @param item Item to be inserted into the hash table.
    83193 */
    84 void hash_table_insert(hash_table_t *h, sysarg_t key[], link_t *item)
    85 {
    86         size_t chain;
    87        
     194void hash_table_insert(hash_table_t *h, ht_link_t *item)
     195{
    88196        assert(item);
    89         assert(h);
    90         assert(h->op);
    91         assert(h->op->hash);
    92         assert(h->op->compare);
    93        
    94         chain = h->op->hash(key);
    95         assert(chain < h->entries);
    96        
    97         list_append(item, &h->entry[chain]);
     197        assert(h && h->bucket);
     198        assert(!h->apply_ongoing);
     199       
     200        size_t idx = h->op->hash(item) % h->bucket_cnt;
     201       
     202        list_append(&item->link, &h->bucket[idx]);
     203        ++h->item_cnt;
     204        grow_if_needed(h);
     205}
     206
     207
     208/** Insert item into a hash table if not already present.
     209 *
     210 * @param h    Hash table.
     211 * @param item Item to be inserted into the hash table.
     212 *
     213 * @return False if such an item had already been inserted.
     214 * @return True if the inserted item was the only item with such a lookup key.
     215 */
     216bool hash_table_insert_unique(hash_table_t *h, ht_link_t *item)
     217{
     218        assert(item);
     219        assert(h && h->bucket && h->bucket_cnt);
     220        assert(h->op && h->op->hash && h->op->equal);
     221        assert(!h->apply_ongoing);
     222       
     223        size_t idx = h->op->hash(item) % h->bucket_cnt;
     224       
     225        /* Check for duplicates. */
     226        list_foreach(h->bucket[idx], link, ht_link_t, cur_link) {
     227                /*
     228                 * We could filter out items using their hashes first, but
     229                 * calling equal() might very well be just as fast.
     230                 */
     231                if (h->op->equal(cur_link, item))
     232                        return false;
     233        }
     234       
     235        list_append(&item->link, &h->bucket[idx]);
     236        ++h->item_cnt;
     237        grow_if_needed(h);
     238       
     239        return true;
    98240}
    99241
    100242/** Search hash table for an item matching keys.
    101243 *
    102  * @param h Hash table.
     244 * @param h   Hash table.
    103245 * @param key Array of all keys needed to compute hash index.
    104246 *
    105247 * @return Matching item on success, NULL if there is no such item.
    106  */
    107 link_t *hash_table_find(hash_table_t *h, sysarg_t key[])
    108 {
    109         size_t chain;
    110        
    111         assert(h);
    112         assert(h->op);
    113         assert(h->op->hash);
    114         assert(h->op->compare);
    115        
    116         chain = h->op->hash(key);
    117         assert(chain < h->entries);
    118        
    119         link_t *cur = list_first(&h->entry[chain]);
    120         while (cur != NULL) {
    121                 if (h->op->compare(key, h->max_keys, cur)) {
    122                         /*
    123                          * The entry is there.
     248 *
     249 */
     250ht_link_t *hash_table_find(const hash_table_t *h, void *key)
     251{
     252        assert(h && h->bucket);
     253       
     254        size_t idx = h->op->key_hash(key) % h->bucket_cnt;
     255
     256        list_foreach(h->bucket[idx], link, ht_link_t, cur_link) {
     257                /*
     258                 * Is this is the item we are looking for? We could have first
     259                 * checked if the hashes match but op->key_equal() may very well be
     260                 * just as fast as op->hash().
     261                 */
     262                if (h->op->key_equal(key, cur_link)) {
     263                        return cur_link;
     264                }
     265        }
     266       
     267        return NULL;
     268}
     269
     270/** Find the next item equal to item. */
     271ht_link_t *hash_table_find_next(const hash_table_t *h, ht_link_t *item)
     272{
     273        assert(item);
     274        assert(h && h->bucket);
     275
     276        /* Traverse the circular list until we reach the starting item again. */
     277        for (link_t *cur = item->link.next; cur != &item->link; cur = cur->next) {
     278                assert(cur);
     279                ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
     280                /*
     281                 * Is this is the item we are looking for? We could have first
     282                 * checked if the hashes match but op->equal() may very well be
     283                 * just as fast as op->hash().
     284                 */
     285                if (h->op->equal(cur_link, item)) {
     286                        return cur_link;
     287                }
     288        }
     289
     290        return NULL;
     291}
     292
     293/** Remove all matching items from hash table.
     294 *
     295 * For each removed item, h->remove_callback() is called.
     296 *
     297 * @param h    Hash table.
     298 * @param key  Array of keys that will be compared against items of
     299 *             the hash table.
     300 *
     301 * @return Returns the number of removed items.
     302 */
     303size_t hash_table_remove(hash_table_t *h, void *key)
     304{
     305        assert(h && h->bucket);
     306        assert(!h->apply_ongoing);
     307       
     308        size_t idx = h->op->key_hash(key) % h->bucket_cnt;
     309
     310        size_t removed = 0;
     311       
     312        list_foreach_safe(h->bucket[idx], cur, next) {
     313                ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
     314               
     315                if (h->op->key_equal(key, cur_link)) {
     316                        ++removed;
     317                        list_remove(cur);
     318                        h->op->remove_callback(cur_link);
     319                }
     320        }
     321
     322        h->item_cnt -= removed;
     323        shrink_if_needed(h);
     324       
     325        return removed;
     326}
     327
     328/** Removes an item already present in the table. The item must be in the table.*/
     329void hash_table_remove_item(hash_table_t *h, ht_link_t *item)
     330{
     331        assert(item);
     332        assert(h && h->bucket);
     333        assert(link_in_use(&item->link));
     334
     335        list_remove(&item->link);
     336        --h->item_cnt;
     337        h->op->remove_callback(item);
     338        shrink_if_needed(h);
     339}
     340
     341/** Apply function to all items in hash table.
     342 *
     343 * @param h   Hash table.
     344 * @param f   Function to be applied. Return false if no more items
     345 *            should be visited. The functor may only delete the supplied
     346 *            item. It must not delete the successor of the item passed
     347 *            in the first argument.
     348 * @param arg Argument to be passed to the function.
     349 */
     350void hash_table_apply(hash_table_t *h, bool (*f)(ht_link_t *, void *), void *arg)
     351{       
     352        assert(f);
     353        assert(h && h->bucket);
     354       
     355        if (h->item_cnt == 0)
     356                return;
     357       
     358        h->apply_ongoing = true;
     359       
     360        for (size_t idx = 0; idx < h->bucket_cnt; ++idx) {
     361                list_foreach_safe(h->bucket[idx], cur, next) {
     362                        ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
     363                        /*
     364                         * The next pointer had already been saved. f() may safely
     365                         * delete cur (but not next!).
    124366                         */
    125                         return cur;
    126                 }
    127                 cur = list_next(cur, &h->entry[chain]);
    128         }
    129        
    130         return NULL;
    131 }
    132 
    133 /** Remove all matching items from hash table.
    134  *
    135  * For each removed item, h->remove_callback() is called (if not NULL).
    136  *
    137  * @param h Hash table.
    138  * @param key Array of keys that will be compared against items of the hash table.
    139  * @param keys Number of keys in the key array.
    140  */
    141 void hash_table_remove(hash_table_t *h, sysarg_t key[], size_t keys)
    142 {
    143         size_t chain;
    144        
    145         assert(h);
    146         assert(h->op);
    147         assert(h->op->hash);
    148         assert(h->op->compare);
    149         assert(keys <= h->max_keys);
    150        
    151        
    152         if (keys == h->max_keys) {
    153                 link_t *cur;
     367                        if (!f(cur_link, arg))
     368                                goto out;
     369                }
     370        }
     371out:
     372        h->apply_ongoing = false;
     373       
     374        shrink_if_needed(h);
     375        grow_if_needed(h);
     376}
     377
     378/** Rounds up size to the nearest suitable table size. */
     379static size_t round_up_size(size_t size)
     380{
     381        size_t rounded_size = HT_MIN_BUCKETS;
     382       
     383        while (rounded_size < size) {
     384                rounded_size = 2 * rounded_size + 1;
     385        }
     386       
     387        return rounded_size;
     388}
     389
     390/** Allocates and initializes the desired number of buckets. True if successful.*/
     391static bool alloc_table(size_t bucket_cnt, list_t **pbuckets)
     392{
     393        assert(pbuckets && HT_MIN_BUCKETS <= bucket_cnt);
    154394               
    155                 /*
    156                  * All keys are known, hash_table_find() can be used to find the entry.
     395        list_t *buckets = malloc(bucket_cnt * sizeof(list_t), FRAME_ATOMIC);
     396        if (!buckets)
     397                return false;
     398       
     399        for (size_t i = 0; i < bucket_cnt; i++)
     400                list_initialize(&buckets[i]);
     401
     402        *pbuckets = buckets;
     403        return true;
     404}
     405
     406
     407/** Shrinks the table if the table is only sparely populated. */
     408static inline void shrink_if_needed(hash_table_t *h)
     409{
     410        if (h->item_cnt <= h->full_item_cnt / 4 && HT_MIN_BUCKETS < h->bucket_cnt) {
     411                /*
     412                 * Keep the bucket_cnt odd (possibly also prime).
     413                 * Shrink from 2n + 1 to n. Integer division discards the +1.
    157414                 */
    158        
    159                 cur = hash_table_find(h, key);
    160                 if (cur) {
    161                         list_remove(cur);
    162                         if (h->op->remove_callback)
    163                                 h->op->remove_callback(cur);
    164                 }
     415                size_t new_bucket_cnt = h->bucket_cnt / 2;
     416                resize(h, new_bucket_cnt);
     417        }
     418}
     419
     420/** Grows the table if table load exceeds the maximum allowed. */
     421static inline void grow_if_needed(hash_table_t *h)
     422{
     423        /* Grow the table if the average bucket load exceeds the maximum. */
     424        if (h->full_item_cnt < h->item_cnt) {
     425                /* Keep the bucket_cnt odd (possibly also prime). */
     426                size_t new_bucket_cnt = 2 * h->bucket_cnt + 1;
     427                resize(h, new_bucket_cnt);
     428        }
     429}
     430
     431/** Allocates and rehashes items to a new table. Frees the old table. */
     432static void resize(hash_table_t *h, size_t new_bucket_cnt)
     433{
     434        assert(h && h->bucket);
     435        assert(HT_MIN_BUCKETS <= new_bucket_cnt);
     436       
     437        /* We are traversing the table and resizing would mess up the buckets. */
     438        if (h->apply_ongoing)
    165439                return;
    166         }
    167        
    168         /*
    169          * Fewer keys were passed.
    170          * Any partially matching entries are to be removed.
    171          */
    172         for (chain = 0; chain < h->entries; chain++) {
    173                 link_t *cur;
    174                 for (cur = h->entry[chain].head.next; cur != &h->entry[chain].head;
    175                     cur = cur->next) {
    176                         if (h->op->compare(key, keys, cur)) {
    177                                 link_t *hlp;
    178                                
    179                                 hlp = cur;
    180                                 cur = cur->prev;
    181                                
    182                                 list_remove(hlp);
    183                                 if (h->op->remove_callback)
    184                                         h->op->remove_callback(hlp);
    185                                
    186                                 continue;
     440       
     441        list_t *new_buckets;
     442
     443        /* Leave the table as is if we cannot resize. */
     444        if (!alloc_table(new_bucket_cnt, &new_buckets))
     445                return;
     446       
     447        if (0 < h->item_cnt) {
     448                /* Rehash all the items to the new table. */
     449                for (size_t old_idx = 0; old_idx < h->bucket_cnt; ++old_idx) {
     450                        list_foreach_safe(h->bucket[old_idx], cur, next) {
     451                                ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link);
     452
     453                                size_t new_idx = h->op->hash(cur_link) % new_bucket_cnt;
     454                                list_remove(cur);
     455                                list_append(cur, &new_buckets[new_idx]);
    187456                        }
    188457                }
    189458        }
    190 }
    191 
    192 /** Remove an existing item from hash table.
    193  *
    194  * @param h     Hash table.
    195  * @param item  Item to remove from the hash table.
    196  */
    197 void hash_table_remove_item(hash_table_t *h, link_t *item)
    198 {
    199         assert(h);
    200         assert(h->op);
    201        
    202         list_remove(item);
    203         if (h->op->remove_callback)
    204                 h->op->remove_callback(item);
    205 }
     459       
     460        free(h->bucket);
     461        h->bucket = new_buckets;
     462        h->bucket_cnt = new_bucket_cnt;
     463        h->full_item_cnt = h->max_load * h->bucket_cnt;
     464}
     465
    206466
    207467/** @}

  • kernel/generic/src/ddi/irq.c

    r81b9d3e r82cbf8c6  
    4040
    4141#include <ddi/irq.h>
     42#include <adt/hash.h>
    4243#include <adt/hash_table.h>
    4344#include <mm/slab.h>
    … …  
    7172hash_table_t irq_uspace_hash_table;
    7273
    73 static size_t irq_ht_hash(sysarg_t *key);
    74 static bool irq_ht_compare(sysarg_t *key, size_t keys, link_t *item);
    75 static void irq_ht_remove(link_t *item);
    76 
    77 static hash_table_operations_t irq_ht_ops = {
     74static size_t irq_ht_hash(const ht_link_t *);
     75static size_t irq_ht_key_hash(void *);
     76static bool irq_ht_equal(const ht_link_t *, const ht_link_t *);
     77static bool irq_ht_key_equal(void *, const ht_link_t *);
     78
     79static hash_table_ops_t irq_ht_ops = {
    7880        .hash = irq_ht_hash,
    79         .compare = irq_ht_compare,
    80         .remove_callback = irq_ht_remove,
     81        .key_hash = irq_ht_key_hash,
     82        .equal = irq_ht_equal,
     83        .key_equal = irq_ht_key_equal
    8184};
    82 
    83 /** Number of buckets in either of the hash tables */
    84 static size_t buckets;
    8585
    8686/** Last valid INR */
    … …  
    9595void irq_init(size_t inrs, size_t chains)
    9696{
    97         buckets = chains;
    9897        last_inr = inrs - 1;
    9998
    … …  
    102101        assert(irq_slab);
    103102
    104         hash_table_create(&irq_uspace_hash_table, chains, 2, &irq_ht_ops);
    105         hash_table_create(&irq_kernel_hash_table, chains, 2, &irq_ht_ops);
     103        hash_table_create(&irq_uspace_hash_table, chains, 0, &irq_ht_ops);
     104        hash_table_create(&irq_kernel_hash_table, chains, 0, &irq_ht_ops);
    106105}
    107106
    … …  
    114113{
    115114        memsetb(irq, sizeof(irq_t), 0);
    116         link_initialize(&irq->link);
    117115        irq_spinlock_initialize(&irq->lock, "irq.lock");
    118116        irq->inr = -1;
    … …  
    131129void irq_register(irq_t *irq)
    132130{
    133         sysarg_t key[] = {
    134                 [IRQ_HT_KEY_INR] = (sysarg_t) irq->inr,
    135                 [IRQ_HT_KEY_MODE] = (sysarg_t) IRQ_HT_MODE_NO_CLAIM
    136         };
    137        
    138131        irq_spinlock_lock(&irq_kernel_hash_table_lock, true);
    139132        irq_spinlock_lock(&irq->lock, false);
    140         hash_table_insert(&irq_kernel_hash_table, key, &irq->link);
     133        hash_table_insert(&irq_kernel_hash_table, &irq->link);
    141134        irq_spinlock_unlock(&irq->lock, false);
    142135        irq_spinlock_unlock(&irq_kernel_hash_table_lock, true);
    143136}
    144137
    145 /** Search and lock the uspace IRQ hash table */
    146 static irq_t *irq_dispatch_and_lock_uspace(inr_t inr)
    147 {
    148         link_t *lnk;
    149         sysarg_t key[] = {
    150                 [IRQ_HT_KEY_INR] = (sysarg_t) inr,
    151                 [IRQ_HT_KEY_MODE] = (sysarg_t) IRQ_HT_MODE_CLAIM
    152         };
    153        
    154         irq_spinlock_lock(&irq_uspace_hash_table_lock, false);
    155         lnk = hash_table_find(&irq_uspace_hash_table, key);
    156         if (lnk) {
    157                 irq_t *irq = hash_table_get_instance(lnk, irq_t, link);
    158                 irq_spinlock_unlock(&irq_uspace_hash_table_lock, false);
    159                 return irq;
     138/** Search and lock an IRQ hash table */
     139static irq_t *
     140irq_dispatch_and_lock_table(hash_table_t *h, irq_spinlock_t *l, inr_t inr)
     141{
     142        irq_spinlock_lock(l, false);
     143        for (ht_link_t *lnk = hash_table_find(h, &inr); lnk;
     144            lnk = hash_table_find_next(h, lnk)) {
     145                irq_t *irq = hash_table_get_inst(lnk, irq_t, link);
     146                irq_spinlock_lock(&irq->lock, false);
     147                if (irq->claim(irq) == IRQ_ACCEPT) {
     148                        /* leave irq locked */
     149                        irq_spinlock_unlock(l, false);
     150                        return irq;
     151                }
     152                irq_spinlock_unlock(&irq->lock, false);
    160153        }
    161         irq_spinlock_unlock(&irq_uspace_hash_table_lock, false);
    162        
    163         return NULL;
    164 }
    165 
    166 /** Search and lock the kernel IRQ hash table */
    167 static irq_t *irq_dispatch_and_lock_kernel(inr_t inr)
    168 {
    169         link_t *lnk;
    170         sysarg_t key[] = {
    171                 [IRQ_HT_KEY_INR] = (sysarg_t) inr,
    172                 [IRQ_HT_KEY_MODE] = (sysarg_t) IRQ_HT_MODE_CLAIM
    173         };
    174        
    175         irq_spinlock_lock(&irq_kernel_hash_table_lock, false);
    176         lnk = hash_table_find(&irq_kernel_hash_table, key);
    177         if (lnk) {
    178                 irq_t *irq = hash_table_get_instance(lnk, irq_t, link);
    179                 irq_spinlock_unlock(&irq_kernel_hash_table_lock, false);
    180                 return irq;
    181         }
    182         irq_spinlock_unlock(&irq_kernel_hash_table_lock, false);
     154        irq_spinlock_unlock(l, false);
    183155       
    184156        return NULL;
    … …  
    209181       
    210182        if (console_override) {
    211                 irq_t *irq = irq_dispatch_and_lock_kernel(inr);
     183                irq_t *irq = irq_dispatch_and_lock_table(&irq_kernel_hash_table,
     184                    &irq_kernel_hash_table_lock, inr);
    212185                if (irq)
    213186                        return irq;
    214187               
    215                 return irq_dispatch_and_lock_uspace(inr);
     188                return irq_dispatch_and_lock_table(&irq_uspace_hash_table,
     189                    &irq_uspace_hash_table_lock, inr);
    216190        }
    217191       
    218         irq_t *irq = irq_dispatch_and_lock_uspace(inr);
     192        irq_t *irq = irq_dispatch_and_lock_table(&irq_uspace_hash_table,
     193            &irq_uspace_hash_table_lock, inr);
    219194        if (irq)
    220195                return irq;
    221196       
    222         return irq_dispatch_and_lock_kernel(inr);
    223 }
    224 
    225 /** Compute hash index for the key
    226  *
    227  * @param key  The first of the keys is inr and the second is mode. Only inr is
    228  *             used to compute the hash.
    229  *
    230  * @return Index into the hash table.
    231  *
    232  */
    233 size_t irq_ht_hash(sysarg_t key[])
    234 {
    235         inr_t inr = (inr_t) key[IRQ_HT_KEY_INR];
    236         return inr % buckets;
    237 }
    238 
    239 /** Compare hash table element with a key
    240  *
    241  * If mode is IRQ_HT_MODE_CLAIM, the result of the claim() function is used for
    242  * the match. Otherwise the key does not match.
    243  *
    244  * This function assumes interrupts are already disabled.
    245  *
    246  * @param key   Keys (i.e. inr and mode).
    247  * @param keys  This is 2.
    248  * @param item  The item to compare the key with.
    249  *
    250  * @return True on match
    251  * @return False on no match
    252  *
    253  */
    254 bool irq_ht_compare(sysarg_t key[], size_t keys, link_t *item)
    255 {
    256         irq_t *irq = hash_table_get_instance(item, irq_t, link);
    257         inr_t inr = (inr_t) key[IRQ_HT_KEY_INR];
    258         irq_ht_mode_t mode = (irq_ht_mode_t) key[IRQ_HT_KEY_MODE];
    259        
    260         bool rv;
    261        
    262         irq_spinlock_lock(&irq->lock, false);
    263         if (mode == IRQ_HT_MODE_CLAIM) {
    264                 /* Invoked by irq_dispatch_and_lock(). */
    265                 rv = ((irq->inr == inr) && (irq->claim(irq) == IRQ_ACCEPT));
    266         } else {
    267                 /* Invoked by irq_find_and_lock(). */
    268                 rv = false;
    269         }
    270        
    271         /* unlock only on non-match */
    272         if (!rv)
    273                 irq_spinlock_unlock(&irq->lock, false);
    274        
    275         return rv;
    276 }
    277 
    278 /** Unlock IRQ structure after hash_table_remove()
    279  *
    280  * @param lnk  Link in the removed and locked IRQ structure.
    281  */
    282 void irq_ht_remove(link_t *lnk)
    283 {
    284         irq_t *irq __attribute__((unused))
    285             = hash_table_get_instance(lnk, irq_t, link);
    286         irq_spinlock_unlock(&irq->lock, false);
     197        return irq_dispatch_and_lock_table(&irq_kernel_hash_table,
     198            &irq_kernel_hash_table_lock, inr);
     199}
     200
     201/** Return the hash of the key stored in the item. */
     202size_t irq_ht_hash(const ht_link_t *item)
     203{
     204        irq_t *irq = hash_table_get_inst(item, irq_t, link);
     205        return hash_mix(irq->inr);
     206}
     207
     208/** Return the hash of the key. */
     209size_t irq_ht_key_hash(void *key)
     210{
     211        inr_t *inr = (inr_t *) key;
     212        return hash_mix(*inr);
     213}
     214
     215/** Return true if the items have the same lookup key. */
     216bool irq_ht_equal(const ht_link_t *item1, const ht_link_t *item2)
     217{
     218        irq_t *irq1 = hash_table_get_inst(item1, irq_t, link);
     219        irq_t *irq2 = hash_table_get_inst(item2, irq_t, link);
     220        return irq1->inr == irq2->inr;
     221}
     222
     223/** Return true if the key is equal to the item's lookup key. */
     224bool irq_ht_key_equal(void *key, const ht_link_t *item)
     225{
     226        inr_t *inr = (inr_t *) key;
     227        irq_t *irq = hash_table_get_inst(item, irq_t, link);
     228        return irq->inr == *inr;
    287229}
    288230

  • kernel/generic/src/ipc/irq.c

    r81b9d3e r82cbf8c6  
    298298    irq_code_t *ucode)
    299299{
    300         sysarg_t key[] = {
    301                 [IRQ_HT_KEY_INR] = (sysarg_t) inr,
    302                 [IRQ_HT_KEY_MODE] = (sysarg_t) IRQ_HT_MODE_NO_CLAIM
    303         };
    304        
    305300        if ((inr < 0) || (inr > last_inr))
    306301                return ELIMIT;
    … …  
    351346       
    352347        irq->notif_cfg.hashed_in = true;
    353         hash_table_insert(&irq_uspace_hash_table, key, &irq->link);
     348        hash_table_insert(&irq_uspace_hash_table, &irq->link);
    354349       
    355350        irq_spinlock_unlock(&irq->lock, false);
    … …  
    388383        }
    389384
    390         /* kobj->irq->lock unlocked by the hash table remove_callback */
     385        irq_spinlock_unlock(&kobj->irq->lock, false);
    391386        irq_spinlock_unlock(&irq_uspace_hash_table_lock, true);
    392387

  • kernel/generic/src/lib/ra.c

    r81b9d3e r82cbf8c6  
    5050#include <panic.h>
    5151#include <adt/list.h>
     52#include <adt/hash.h>
    5253#include <adt/hash_table.h>
    5354#include <align.h>
    … …  
    5758static slab_cache_t *ra_segment_cache;
    5859
    59 #define USED_BUCKETS    1024
    60 
    61 static size_t used_hash(sysarg_t *key)
    62 {
    63         return ((*key >> 2) & (USED_BUCKETS - 1));
    64 }
    65 
    66 static bool used_compare(sysarg_t *key, size_t keys, link_t *item)
    67 {
    68         ra_segment_t *seg;
    69 
    70         seg = hash_table_get_instance(item, ra_segment_t, fu_link);
    71         return seg->base == *key;
    72 }
    73 
    74 static hash_table_operations_t used_ops = {
     60/** Return the hash of the key stored in the item */
     61static size_t used_hash(const ht_link_t *item)
     62{
     63        ra_segment_t *seg = hash_table_get_inst(item, ra_segment_t, uh_link);
     64        return hash_mix(seg->base);
     65}
     66
     67/** Return the hash of the key */
     68static size_t used_key_hash(void *key)
     69{
     70        uintptr_t *base = (uintptr_t *) key;
     71        return hash_mix(*base);
     72}
     73
     74/** Return true if the key is equal to the item's lookup key */
     75static bool used_key_equal(void *key, const ht_link_t *item)
     76{
     77        uintptr_t *base = (sysarg_t *) key;
     78        ra_segment_t *seg = hash_table_get_inst(item, ra_segment_t, uh_link);
     79        return seg->base == *base;
     80}
     81
     82static hash_table_ops_t used_ops = {
    7583        .hash = used_hash,
    76         .compare = used_compare,
    77         .remove_callback = NULL,
     84        .key_hash = used_key_hash,
     85        .key_equal = used_key_equal
    7886};
    7987
    … …  
    97105
    98106        link_initialize(&seg->segment_link);
    99         link_initialize(&seg->fu_link);
     107        link_initialize(&seg->fl_link);
    100108
    101109        seg->base = base;
    … …  
    160168        list_initialize(&span->segments);
    161169
    162         hash_table_create(&span->used, USED_BUCKETS, 1, &used_ops);
     170        hash_table_create(&span->used, 0, 0, &used_ops);
    163171
    164172        for (i = 0; i <= span->max_order; i++)
    … …  
    171179
    172180        /* Insert the first segment into the respective free list. */
    173         list_append(&seg->fu_link, &span->free[span->max_order]);
     181        list_append(&seg->fl_link, &span->free[span->max_order]);
    174182
    175183        return span;
    … …  
    232240                /* Take the first segment from the free list. */
    233241                seg = list_get_instance(list_first(&span->free[order]),
    234                     ra_segment_t, fu_link);
     242                    ra_segment_t, fl_link);
    235243
    236244                assert(seg->flags & RA_SEGMENT_FREE);
    … …  
    274282                            &seg->segment_link);
    275283                        pred_order = fnzb(ra_segment_size_get(pred));
    276                         list_append(&pred->fu_link, &span->free[pred_order]);
     284                        list_append(&pred->fl_link, &span->free[pred_order]);
    277285                }
    278286                if (succ) {
    … …  
    282290                            &seg->segment_link);
    283291                        succ_order = fnzb(ra_segment_size_get(succ));
    284                         list_append(&succ->fu_link, &span->free[succ_order]);
     292                        list_append(&succ->fl_link, &span->free[succ_order]);
    285293                }
    286294
    287295                /* Now remove the found segment from the free list. */
    288                 list_remove(&seg->fu_link);
     296                list_remove(&seg->fl_link);
    289297                seg->base = newbase;
    290298                seg->flags &= ~RA_SEGMENT_FREE;
    291299
    292300                /* Hash-in the segment into the used hash. */
    293                 sysarg_t key = seg->base;
    294                 hash_table_insert(&span->used, &key, &seg->fu_link);
     301                hash_table_insert(&span->used, &seg->uh_link);
    295302
    296303                *base = newbase;
    … …  
    304311{
    305312        sysarg_t key = base;
    306         link_t *link;
     313        ht_link_t *link;
    307314        ra_segment_t *seg;
    308315        ra_segment_t *pred;
    … …  
    318325                    PRIxn ", size=%" PRIdn ").", base, size);
    319326        }
    320         seg = hash_table_get_instance(link, ra_segment_t, fu_link);
     327        seg = hash_table_get_inst(link, ra_segment_t, uh_link);
    321328
    322329        /*
    323330         * Hash out the segment.
    324331         */
    325         hash_table_remove(&span->used, &key, 1);
     332        hash_table_remove_item(&span->used, link);
    326333
    327334        assert(!(seg->flags & RA_SEGMENT_FREE));
    … …  
    333340         */
    334341        if (list_first(&span->segments) != &seg->segment_link) {
    335                 pred = hash_table_get_instance(seg->segment_link.prev,
     342                pred = hash_table_get_inst(seg->segment_link.prev,
    336343                    ra_segment_t, segment_link);
    337344
    … …  
    345352                         * away.
    346353                         */
    347                         list_remove(&pred->fu_link);
     354                        list_remove(&pred->fl_link);
    348355                        list_remove(&pred->segment_link);
    349356                        seg->base = pred->base;
    … …  
    355362         * Check whether the segment can be coalesced with its right neighbor.
    356363         */
    357         succ = hash_table_get_instance(seg->segment_link.next, ra_segment_t,
     364        succ = hash_table_get_inst(seg->segment_link.next, ra_segment_t,
    358365            segment_link);
    359366        assert(succ->base > seg->base);
    … …  
    364371                 * and throw it away.
    365372                 */
    366                 list_remove(&succ->fu_link);
     373                list_remove(&succ->fl_link);
    367374                list_remove(&succ->segment_link);
    368375                ra_segment_destroy(succ);
    … …  
    372379        seg->flags |= RA_SEGMENT_FREE;
    373380        order = fnzb(ra_segment_size_get(seg));
    374         list_append(&seg->fu_link, &span->free[order]);
     381        list_append(&seg->fl_link, &span->free[order]);
    375382}
    376383

  • kernel/generic/src/synch/futex.c

    r81b9d3e r82cbf8c6  
    7474#include <genarch/mm/page_ht.h>
    7575#include <adt/cht.h>
     76#include <adt/hash.h>
    7677#include <adt/hash_table.h>
    7778#include <adt/list.h>
    … …  
    8081#include <panic.h>
    8182#include <errno.h>
    82 
    83 #define FUTEX_HT_SIZE   1024    /* keep it a power of 2 */
    8483
    8584/** Task specific pointer to a global kernel futex object. */
    … …  
    108107static bool find_futex_paddr(uintptr_t uaddr, uintptr_t *phys_addr);
    109108
    110 static size_t futex_ht_hash(sysarg_t *key);
    111 static bool futex_ht_compare(sysarg_t *key, size_t keys, link_t *item);
    112 static void futex_ht_remove_callback(link_t *item);
     109static size_t futex_ht_hash(const ht_link_t *item);
     110static size_t futex_ht_key_hash(void *key);
     111static bool futex_ht_key_equal(void *key, const ht_link_t *item);
     112static void futex_ht_remove_callback(ht_link_t *item);
    113113
    114114static size_t task_fut_ht_hash(const cht_link_t *link);
    … …  
    131131
    132132/** Global kernel futex hash table operations. */
    133 static hash_table_operations_t futex_ht_ops = {
     133static hash_table_ops_t futex_ht_ops = {
    134134        .hash = futex_ht_hash,
    135         .compare = futex_ht_compare,
     135        .key_hash = futex_ht_key_hash,
     136        .key_equal = futex_ht_key_equal,
    136137        .remove_callback = futex_ht_remove_callback
    137138};
    … …  
    149150void futex_init(void)
    150151{
    151         hash_table_create(&futex_ht, FUTEX_HT_SIZE, 1, &futex_ht_ops);
     152        hash_table_create(&futex_ht, 0, 0, &futex_ht_ops);
    152153}
    153154
    … …  
    234235{
    235236        waitq_initialize(&futex->wq);
    236         link_initialize(&futex->ht_link);
    237237        futex->paddr = paddr;
    238238        futex->refcount = 1;
    … …  
    256256       
    257257        if (0 == futex->refcount) {
    258                 hash_table_remove(&futex_ht, &futex->paddr, 1);
     258                hash_table_remove(&futex_ht, &futex->paddr);
    259259        }
    260260}
    … …  
    347347        spinlock_lock(&futex_ht_lock);
    348348       
    349         link_t *fut_link = hash_table_find(&futex_ht, &phys_addr);
     349        ht_link_t *fut_link = hash_table_find(&futex_ht, &phys_addr);
    350350       
    351351        if (fut_link) {
    … …  
    355355        } else {
    356356                futex_initialize(futex, phys_addr);
    357                 hash_table_insert(&futex_ht, &phys_addr, &futex->ht_link);
     357                hash_table_insert(&futex_ht, &futex->ht_link);
    358358        }
    359359       
    … …  
    437437
    438438
    439 /** Compute hash index into futex hash table.
    440  *
    441  * @param key           Address where the key (i.e. physical address of futex
    442  *                      counter) is stored.
    443  *
    444  * @return              Index into futex hash table.
    445  */
    446 size_t futex_ht_hash(sysarg_t *key)
    447 {
    448         return (*key & (FUTEX_HT_SIZE - 1));
    449 }
    450 
    451 /** Compare futex hash table item with a key.
    452  *
    453  * @param key           Address where the key (i.e. physical address of futex
    454  *                      counter) is stored.
    455  *
    456  * @return              True if the item matches the key. False otherwise.
    457  */
    458 bool futex_ht_compare(sysarg_t *key, size_t keys, link_t *item)
     439/** Return the hash of the key stored in the item */
     440size_t futex_ht_hash(const ht_link_t *item)
     441{
     442        futex_t *futex = hash_table_get_inst(item, futex_t, ht_link);
     443        return hash_mix(futex->paddr);
     444}
     445
     446/** Return the hash of the key */
     447size_t futex_ht_key_hash(void *key)
     448{
     449        uintptr_t *paddr = (uintptr_t *) key;
     450        return hash_mix(*paddr);
     451}
     452
     453/** Return true if the key is equal to the item's lookup key. */
     454bool futex_ht_key_equal(void *key, const ht_link_t *item)
     455{
     456        uintptr_t *paddr = (uintptr_t *) key;
     457        futex_t *futex = hash_table_get_inst(item, futex_t, ht_link);
     458        return *paddr == futex->paddr;
     459}
     460
     461/** Callback for removal items from futex hash table.
     462 *
     463 * @param item          Item removed from the hash table.
     464 */
     465void futex_ht_remove_callback(ht_link_t *item)
    459466{
    460467        futex_t *futex;
    461468
    462         assert(keys == 1);
    463 
    464         futex = hash_table_get_instance(item, futex_t, ht_link);
    465         return *key == futex->paddr;
    466 }
    467 
    468 /** Callback for removal items from futex hash table.
    469  *
    470  * @param item          Item removed from the hash table.
    471  */
    472 void futex_ht_remove_callback(link_t *item)
    473 {
    474         futex_t *futex;
    475 
    476         futex = hash_table_get_instance(item, futex_t, ht_link);
     469        futex = hash_table_get_inst(item, futex_t, ht_link);
    477470        free(futex);
    478471}
Note: See TracChangeset for help on using the changeset viewer.