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)(void *p, uint32_t h, void *up);
  47 typedef bool (*qht_iter_bool_func_t)(void *p, uint32_t h, void *up);
  48
  49 #define QHT_MODE_AUTO_RESIZE 0x1 /* auto-resize when heavily loaded */
  50 #define QHT_MODE_RAW_MUTEXES 0x2 /* bypass the profiler (QSP) */
  51
  52 /**
  53  * qht_init - Initialize a QHT
  54  * @ht: QHT to be initialized
  55  * @cmp: default comparison function. Cannot be NULL.
  56  * @n_elems: number of entries the hash table should be optimized for.
  57  * @mode: bitmask with OR'ed QHT_MODE_*
  58  */
  59 void qht_init(struct qht *ht, qht_cmp_func_t cmp, size_t n_elems,
  60               unsigned int mode);
  61
  62 /**
  63  * qht_destroy - destroy a previously initialized QHT
  64  * @ht: QHT to be destroyed
  65  *
  66  * Call only when there are no readers/writers left.
  67  */
  68 void qht_destroy(struct qht *ht);
  69
  70 /**
  71  * qht_insert - Insert a pointer into the hash table
  72  * @ht: QHT to insert to
  73  * @p: pointer to be inserted
  74  * @hash: hash corresponding to @p
  75  * @existing: address where the pointer to an existing entry can be copied to
  76  *
  77  * Attempting to insert a NULL @p is a bug.
  78  * Inserting the same pointer @p with different @hash values is a bug.
  79  *
  80  * In case of successful operation, smp_wmb() is implied before the pointer is
  81  * inserted into the hash table.
  82  *
  83  * Returns true on success.
  84  * Returns false if there is an existing entry in the table that is equivalent
  85  * (i.e. ht->cmp matches and the hash is the same) to @p-@h. If @existing
  86  * is !NULL, a pointer to this existing entry is copied to it.
  87  */
  88 bool qht_insert(struct qht *ht, void *p, uint32_t hash, void **existing);
  89
  90 /**
  91  * qht_lookup_custom - Look up a pointer using a custom comparison function.
  92  * @ht: QHT to be looked up
  93  * @userp: pointer to pass to @func
  94  * @hash: hash of the pointer to be looked up
  95  * @func: function to compare existing pointers against @userp
  96  *
  97  * Needs to be called under an RCU read-critical section.
  98  *
  99  * smp_read_barrier_depends() is implied before the call to @func.
 100  *
 101  * The user-provided @func compares pointers in QHT against @userp.
 102  * If the function returns true, a match has been found.
 103  *
 104  * Returns the corresponding pointer when a match is found.
 105  * Returns NULL otherwise.
 106  */
 107 void *qht_lookup_custom(const struct qht *ht, const void *userp, uint32_t hash,
 108                         qht_lookup_func_t func);
 109
 110 /**
 111  * qht_lookup - Look up a pointer in a QHT
 112  * @ht: QHT to be looked up
 113  * @userp: pointer to pass to the comparison function
 114  * @hash: hash of the pointer to be looked up
 115  *
 116  * Calls qht_lookup_custom() using @ht's default comparison function.
 117  */
 118 void *qht_lookup(const struct qht *ht, const void *userp, uint32_t hash);
 119
 120 /**
 121  * qht_remove - remove a pointer from the hash table
 122  * @ht: QHT to remove from
 123  * @p: pointer to be removed
 124  * @hash: hash corresponding to @p
 125  *
 126  * Attempting to remove a NULL @p is a bug.
 127  *
 128  * Just-removed @p pointers cannot be immediately freed; they need to remain
 129  * valid until the end of the RCU grace period in which qht_remove() is called.
 130  * This guarantees that concurrent lookups will always compare against valid
 131  * data.
 132  *
 133  * Returns true on success.
 134  * Returns false if the @p-@hash pair was not found.
 135  */
 136 bool qht_remove(struct qht *ht, const void *p, uint32_t hash);
 137
 138 /**
 139  * qht_reset - reset a QHT
 140  * @ht: QHT to be reset
 141  *
 142  * All entries in the hash table are reset. No resizing is performed.
 143  *
 144  * If concurrent readers may exist, the objects pointed to by the hash table
 145  * must remain valid for the existing RCU grace period -- see qht_remove().
 146  * See also: qht_reset_size()
 147  */
 148 void qht_reset(struct qht *ht);
 149
 150 /**
 151  * qht_reset_size - reset and resize a QHT
 152  * @ht: QHT to be reset and resized
 153  * @n_elems: number of entries the resized hash table should be optimized for.
 154  *
 155  * Returns true if the resize was necessary and therefore performed.
 156  * Returns false otherwise.
 157  *
 158  * If concurrent readers may exist, the objects pointed to by the hash table
 159  * must remain valid for the existing RCU grace period -- see qht_remove().
 160  * See also: qht_reset(), qht_resize().
 161  */
 162 bool qht_reset_size(struct qht *ht, size_t n_elems);
 163
 164 /**
 165  * qht_resize - resize a QHT
 166  * @ht: QHT to be resized
 167  * @n_elems: number of entries the resized hash table should be optimized for
 168  *
 169  * Returns true on success.
 170  * Returns false if the resize was not necessary and therefore not performed.
 171  * See also: qht_reset_size().
 172  */
 173 bool qht_resize(struct qht *ht, size_t n_elems);
 174
 175 /**
 176  * qht_iter - Iterate over a QHT
 177  * @ht: QHT to be iterated over
 178  * @func: function to be called for each entry in QHT
 179  * @userp: additional pointer to be passed to @func
 180  *
 181  * Each time it is called, user-provided @func is passed a pointer-hash pair,
 182  * plus @userp.
 183  *
 184  * Note: @ht cannot be accessed from @func
 185  * See also: qht_iter_remove()
 186  */
 187 void qht_iter(struct qht *ht, qht_iter_func_t func, void *userp);
 188
 189 /**
 190  * qht_iter_remove - Iterate over a QHT, optionally removing entries
 191  * @ht: QHT to be iterated over
 192  * @func: function to be called for each entry in QHT
 193  * @userp: additional pointer to be passed to @func
 194  *
 195  * Each time it is called, user-provided @func is passed a pointer-hash pair,
 196  * plus @userp. If @func returns true, the pointer-hash pair is removed.
 197  *
 198  * Note: @ht cannot be accessed from @func
 199  * See also: qht_iter()
 200  */
 201 void qht_iter_remove(struct qht *ht, qht_iter_bool_func_t func, void *userp);
 202
 203 /**
 204  * qht_statistics_init - Gather statistics from a QHT
 205  * @ht: QHT to gather statistics from
 206  * @stats: pointer to a &struct qht_stats to be filled in
 207  *
 208  * Does NOT need to be called under an RCU read-critical section,
 209  * since it does not dereference any pointers stored in the hash table.
 210  *
 211  * When done with @stats, pass the struct to qht_statistics_destroy().
 212  * Failing to do this will leak memory.
 213  */
 214 void qht_statistics_init(const struct qht *ht, struct qht_stats *stats);
 215
 216 /**
 217  * qht_statistics_destroy - Destroy a &struct qht_stats
 218  * @stats: &struct qht_stats to be destroyed
 219  *
 220  * See also: qht_statistics_init().
 221  */
 222 void qht_statistics_destroy(struct qht_stats *stats);
 223
 224 #endif /* QEMU_QHT_H */