include/qemu/qht.h

   1 /*
   2  * Copyright (C) 2016, Emilio G. Cota <cota@braap.org>
   3  *
   4  * License: GNU GPL, version 2 or later.
   5  *   See the COPYING file in the top-level directory.
   6  */
   7 #ifndef QEMU_QHT_H
   8 #define QEMU_QHT_H
   9
  10 #include "qemu/seqlock.h"
  11 #include "qemu/thread.h"
  12 #include "qemu/qdist.h"
  13
  14 typedef bool (*qht_cmp_func_t)(const void *a, const void *b);
  15
  16 struct qht {
  17     struct qht_map *map;
  18     qht_cmp_func_t cmp;
  19     QemuMutex lock; /* serializes setters of ht->map */
  20     unsigned int mode;
  21 };
  22
  23 /**
  24  * struct qht_stats - Statistics of a QHT
  25  * @head_buckets: number of head buckets
  26  * @used_head_buckets: number of non-empty head buckets
  27  * @entries: total number of entries
  28  * @chain: frequency distribution representing the number of buckets in each
  29  *         chain, excluding empty chains.
  30  * @occupancy: frequency distribution representing chain occupancy rate.
  31  *             Valid range: from 0.0 (empty) to 1.0 (full occupancy).
  32  *
  33  * An entry is a pointer-hash pair.
  34  * Each bucket can host several entries.
  35  * Chains are chains of buckets, whose first link is always a head bucket.
  36  */
  37 struct qht_stats {
  38     size_t head_buckets;
  39     size_t used_head_buckets;
  40     size_t entries;
  41     struct qdist chain;
  42     struct qdist occupancy;
  43 };
  44
  45 typedef bool (*qht_lookup_func_t)(const void *obj, const void *userp);
  46 typedef void (*qht_iter_func_t)(struct qht *ht, void *p, uint32_t h, void *up);
  47
  48 #define QHT_MODE_AUTO_RESIZE 0x1 /* auto-resize when heavily loaded */
  49
  50 /**
  51  * qht_init - Initialize a QHT
  52  * @ht: QHT to be initialized
  53  * @cmp: default comparison function. Cannot be NULL.
  54  * @n_elems: number of entries the hash table should be optimized for.
  55  * @mode: bitmask with OR'ed QHT_MODE_*
  56  */
  57 void qht_init(struct qht *ht, qht_cmp_func_t cmp, size_t n_elems,
  58               unsigned int mode);
  59
  60 /**
  61  * qht_destroy - destroy a previously initialized QHT
  62  * @ht: QHT to be destroyed
  63  *
  64  * Call only when there are no readers/writers left.
  65  */
  66 void qht_destroy(struct qht *ht);
  67
  68 /**
  69  * qht_insert - Insert a pointer into the hash table
  70  * @ht: QHT to insert to
  71  * @p: pointer to be inserted
  72  * @hash: hash corresponding to @p
  73  * @existing: address where the pointer to an existing entry can be copied to
  74  *
  75  * Attempting to insert a NULL @p is a bug.
  76  * Inserting the same pointer @p with different @hash values is a bug.
  77  *
  78  * In case of successful operation, smp_wmb() is implied before the pointer is
  79  * inserted into the hash table.
  80  *
  81  * Returns true on success.
  82  * Returns false if there is an existing entry in the table that is equivalent
  83  * (i.e. ht->cmp matches and the hash is the same) to @p-@h. If @existing
  84  * is !NULL, a pointer to this existing entry is copied to it.
  85  */
  86 bool qht_insert(struct qht *ht, void *p, uint32_t hash, void **existing);
  87
  88 /**
  89  * qht_lookup_custom - Look up a pointer using a custom comparison function.
  90  * @ht: QHT to be looked up
  91  * @userp: pointer to pass to @func
  92  * @hash: hash of the pointer to be looked up
  93  * @func: function to compare existing pointers against @userp
  94  *
  95  * Needs to be called under an RCU read-critical section.
  96  *
  97  * smp_read_barrier_depends() is implied before the call to @func.
  98  *
  99  * The user-provided @func compares pointers in QHT against @userp.
 100  * If the function returns true, a match has been found.
 101  *
 102  * Returns the corresponding pointer when a match is found.
 103  * Returns NULL otherwise.
 104  */
 105 void *qht_lookup_custom(struct qht *ht, const void *userp, uint32_t hash,
 106                         qht_lookup_func_t func);
 107
 108 /**
 109  * qht_lookup - Look up a pointer in a QHT
 110  * @ht: QHT to be looked up
 111  * @userp: pointer to pass to the comparison function
 112  * @hash: hash of the pointer to be looked up
 113  *
 114  * Calls qht_lookup_custom() using @ht's default comparison function.
 115  */
 116 void *qht_lookup(struct qht *ht, const void *userp, uint32_t hash);
 117
 118 /**
 119  * qht_remove - remove a pointer from the hash table
 120  * @ht: QHT to remove from
 121  * @p: pointer to be removed
 122  * @hash: hash corresponding to @p
 123  *
 124  * Attempting to remove a NULL @p is a bug.
 125  *
 126  * Just-removed @p pointers cannot be immediately freed; they need to remain
 127  * valid until the end of the RCU grace period in which qht_remove() is called.
 128  * This guarantees that concurrent lookups will always compare against valid
 129  * data.
 130  *
 131  * Returns true on success.
 132  * Returns false if the @p-@hash pair was not found.
 133  */
 134 bool qht_remove(struct qht *ht, const void *p, uint32_t hash);
 135
 136 /**
 137  * qht_reset - reset a QHT
 138  * @ht: QHT to be reset
 139  *
 140  * All entries in the hash table are reset. No resizing is performed.
 141  *
 142  * If concurrent readers may exist, the objects pointed to by the hash table
 143  * must remain valid for the existing RCU grace period -- see qht_remove().
 144  * See also: qht_reset_size()
 145  */
 146 void qht_reset(struct qht *ht);
 147
 148 /**
 149  * qht_reset_size - reset and resize a QHT
 150  * @ht: QHT to be reset and resized
 151  * @n_elems: number of entries the resized hash table should be optimized for.
 152  *
 153  * Returns true if the resize was necessary and therefore performed.
 154  * Returns false otherwise.
 155  *
 156  * If concurrent readers may exist, the objects pointed to by the hash table
 157  * must remain valid for the existing RCU grace period -- see qht_remove().
 158  * See also: qht_reset(), qht_resize().
 159  */
 160 bool qht_reset_size(struct qht *ht, size_t n_elems);
 161
 162 /**
 163  * qht_resize - resize a QHT
 164  * @ht: QHT to be resized
 165  * @n_elems: number of entries the resized hash table should be optimized for
 166  *
 167  * Returns true on success.
 168  * Returns false if the resize was not necessary and therefore not performed.
 169  * See also: qht_reset_size().
 170  */
 171 bool qht_resize(struct qht *ht, size_t n_elems);
 172
 173 /**
 174  * qht_iter - Iterate over a QHT
 175  * @ht: QHT to be iterated over
 176  * @func: function to be called for each entry in QHT
 177  * @userp: additional pointer to be passed to @func
 178  *
 179  * Each time it is called, user-provided @func is passed a pointer-hash pair,
 180  * plus @userp.
 181  */
 182 void qht_iter(struct qht *ht, qht_iter_func_t func, void *userp);
 183
 184 /**
 185  * qht_statistics_init - Gather statistics from a QHT
 186  * @ht: QHT to gather statistics from
 187  * @stats: pointer to a &struct qht_stats to be filled in
 188  *
 189  * Does NOT need to be called under an RCU read-critical section,
 190  * since it does not dereference any pointers stored in the hash table.
 191  *
 192  * When done with @stats, pass the struct to qht_statistics_destroy().
 193  * Failing to do this will leak memory.
 194  */
 195 void qht_statistics_init(struct qht *ht, struct qht_stats *stats);
 196
 197 /**
 198  * qht_statistics_destroy - Destroy a &struct qht_stats
 199  * @stats: &struct qht_stats to be destroyed
 200  *
 201  * See also: qht_statistics_init().
 202  */
 203 void qht_statistics_destroy(struct qht_stats *stats);
 204
 205 #endif /* QEMU_QHT_H */