qemu/include/qemu/qht.h
<<
>>
Prefs
   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
  14struct 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 */
  34struct 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
  42typedef bool (*qht_lookup_func_t)(const void *obj, const void *userp);
  43typedef 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 */
  53void 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 */
  61void 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 */
  78bool 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 */
  97void *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 */
 116bool 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 */
 128void 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 */
 142bool 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 */
 153bool 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 */
 164void 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 */
 177void qht_statistics_init(struct qht *ht, struct qht_stats *stats);
 178
 179/**
 180 * qht_statistics_destroy - Destroy a struct qht_stats
 181 * @stats: stuct qht_stats to be destroyed
 182 *
 183 * See also: qht_statistics_init().
 184 */
 185void qht_statistics_destroy(struct qht_stats *stats);
 186
 187#endif /* QEMU_QHT_H */
 188