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