include/qemu/qht.h

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