diff options
Diffstat (limited to 'include')
| -rw-r--r-- | include/exec/exec-all.h | 2 | ||||
| -rw-r--r-- | include/exec/tb-context.h | 7 | ||||
| -rw-r--r-- | include/exec/tb-hash-xx.h | 94 | ||||
| -rw-r--r-- | include/exec/tb-hash.h | 7 | ||||
| -rw-r--r-- | include/qemu/compiler.h | 2 | ||||
| -rw-r--r-- | include/qemu/processor.h | 30 | ||||
| -rw-r--r-- | include/qemu/qdist.h | 63 | ||||
| -rw-r--r-- | include/qemu/qht.h | 183 | ||||
| -rw-r--r-- | include/qemu/seqlock.h | 14 | ||||
| -rw-r--r-- | include/qemu/thread.h | 35 |
10 files changed, 419 insertions, 18 deletions
diff --git a/include/exec/exec-all.h b/include/exec/exec-all.h index e076397e2f..c1f59fa59d 100644 --- a/include/exec/exec-all.h +++ b/include/exec/exec-all.h @@ -215,8 +215,6 @@ struct TranslationBlock { void *tc_ptr; /* pointer to the translated code */ uint8_t *tc_search; /* pointer to search data */ - /* next matching tb for physical address. */ - struct TranslationBlock *phys_hash_next; /* original tb when cflags has CF_NOCACHE */ struct TranslationBlock *orig_tb; /* first and second physical page containing code. The lower bit diff --git a/include/exec/tb-context.h b/include/exec/tb-context.h index 5efe3d9087..e209c1c28c 100644 --- a/include/exec/tb-context.h +++ b/include/exec/tb-context.h @@ -21,9 +21,10 @@ #define QEMU_TB_CONTEXT_H_ #include "qemu/thread.h" +#include "qemu/qht.h" -#define CODE_GEN_PHYS_HASH_BITS 15 -#define CODE_GEN_PHYS_HASH_SIZE (1 << CODE_GEN_PHYS_HASH_BITS) +#define CODE_GEN_HTABLE_BITS 15 +#define CODE_GEN_HTABLE_SIZE (1 << CODE_GEN_HTABLE_BITS) typedef struct TranslationBlock TranslationBlock; typedef struct TBContext TBContext; @@ -31,7 +32,7 @@ typedef struct TBContext TBContext; struct TBContext { TranslationBlock *tbs; - TranslationBlock *tb_phys_hash[CODE_GEN_PHYS_HASH_SIZE]; + struct qht htable; int nb_tbs; /* any access to the tbs or the page table must use this lock */ QemuMutex tb_lock; diff --git a/include/exec/tb-hash-xx.h b/include/exec/tb-hash-xx.h new file mode 100644 index 0000000000..9f3fc05636 --- /dev/null +++ b/include/exec/tb-hash-xx.h @@ -0,0 +1,94 @@ +/* + * xxHash - Fast Hash algorithm + * Copyright (C) 2012-2016, Yann Collet + * + * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * + Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * You can contact the author at : + * - xxHash source repository : https://github.com/Cyan4973/xxHash + */ +#ifndef EXEC_TB_HASH_XX +#define EXEC_TB_HASH_XX + +#include <qemu/bitops.h> + +#define PRIME32_1 2654435761U +#define PRIME32_2 2246822519U +#define PRIME32_3 3266489917U +#define PRIME32_4 668265263U +#define PRIME32_5 374761393U + +#define TB_HASH_XX_SEED 1 + +/* + * xxhash32, customized for input variables that are not guaranteed to be + * contiguous in memory. + */ +static inline +uint32_t tb_hash_func5(uint64_t a0, uint64_t b0, uint32_t e) +{ + uint32_t v1 = TB_HASH_XX_SEED + PRIME32_1 + PRIME32_2; + uint32_t v2 = TB_HASH_XX_SEED + PRIME32_2; + uint32_t v3 = TB_HASH_XX_SEED + 0; + uint32_t v4 = TB_HASH_XX_SEED - PRIME32_1; + uint32_t a = a0 >> 32; + uint32_t b = a0; + uint32_t c = b0 >> 32; + uint32_t d = b0; + uint32_t h32; + + v1 += a * PRIME32_2; + v1 = rol32(v1, 13); + v1 *= PRIME32_1; + + v2 += b * PRIME32_2; + v2 = rol32(v2, 13); + v2 *= PRIME32_1; + + v3 += c * PRIME32_2; + v3 = rol32(v3, 13); + v3 *= PRIME32_1; + + v4 += d * PRIME32_2; + v4 = rol32(v4, 13); + v4 *= PRIME32_1; + + h32 = rol32(v1, 1) + rol32(v2, 7) + rol32(v3, 12) + rol32(v4, 18); + h32 += 20; + + h32 += e * PRIME32_3; + h32 = rol32(h32, 17) * PRIME32_4; + + h32 ^= h32 >> 15; + h32 *= PRIME32_2; + h32 ^= h32 >> 13; + h32 *= PRIME32_3; + h32 ^= h32 >> 16; + + return h32; +} + +#endif /* EXEC_TB_HASH_XX */ diff --git a/include/exec/tb-hash.h b/include/exec/tb-hash.h index 0f4e8a08af..1d0200bc91 100644 --- a/include/exec/tb-hash.h +++ b/include/exec/tb-hash.h @@ -20,6 +20,8 @@ #ifndef EXEC_TB_HASH #define EXEC_TB_HASH +#include "exec/tb-hash-xx.h" + /* Only the bottom TB_JMP_PAGE_BITS of the jump cache hash bits vary for addresses on the same page. The top bits are the same. This allows TLB invalidation to quickly clear a subset of the hash table. */ @@ -43,9 +45,10 @@ static inline unsigned int tb_jmp_cache_hash_func(target_ulong pc) | (tmp & TB_JMP_ADDR_MASK)); } -static inline unsigned int tb_phys_hash_func(tb_page_addr_t pc) +static inline +uint32_t tb_hash_func(tb_page_addr_t phys_pc, target_ulong pc, uint32_t flags) { - return (pc >> 2) & (CODE_GEN_PHYS_HASH_SIZE - 1); + return tb_hash_func5(phys_pc, pc, flags); } #endif diff --git a/include/qemu/compiler.h b/include/qemu/compiler.h index 8f1cc7ba67..b64f899870 100644 --- a/include/qemu/compiler.h +++ b/include/qemu/compiler.h @@ -41,6 +41,8 @@ # define QEMU_PACKED __attribute__((packed)) #endif +#define QEMU_ALIGNED(X) __attribute__((aligned(X))) + #ifndef glue #define xglue(x, y) x ## y #define glue(x, y) xglue(x, y) diff --git a/include/qemu/processor.h b/include/qemu/processor.h new file mode 100644 index 0000000000..8b2570283a --- /dev/null +++ b/include/qemu/processor.h @@ -0,0 +1,30 @@ +/* + * Copyright (C) 2016, Emilio G. Cota <cota@braap.org> + * + * License: GNU GPL, version 2. + * See the COPYING file in the top-level directory. + */ +#ifndef QEMU_PROCESSOR_H +#define QEMU_PROCESSOR_H + +#include "qemu/atomic.h" + +#if defined(__i386__) || defined(__x86_64__) +# define cpu_relax() asm volatile("rep; nop" ::: "memory") + +#elif defined(__ia64__) +# define cpu_relax() asm volatile("hint @pause" ::: "memory") + +#elif defined(__aarch64__) +# define cpu_relax() asm volatile("yield" ::: "memory") + +#elif defined(__powerpc64__) +/* set Hardware Multi-Threading (HMT) priority to low; then back to medium */ +# define cpu_relax() asm volatile("or 1, 1, 1;" \ + "or 2, 2, 2;" ::: "memory") + +#else +# define cpu_relax() barrier() +#endif + +#endif /* QEMU_PROCESSOR_H */ diff --git a/include/qemu/qdist.h b/include/qemu/qdist.h new file mode 100644 index 0000000000..f30050c2d1 --- /dev/null +++ b/include/qemu/qdist.h @@ -0,0 +1,63 @@ +/* + * Copyright (C) 2016, Emilio G. Cota <cota@braap.org> + * + * License: GNU GPL, version 2 or later. + * See the COPYING file in the top-level directory. + */ +#ifndef QEMU_QDIST_H +#define QEMU_QDIST_H + +#include "qemu/osdep.h" +#include "qemu-common.h" +#include "qemu/bitops.h" + +/* + * Samples with the same 'x value' end up in the same qdist_entry, + * e.g. inc(0.1) and inc(0.1) end up as {x=0.1, count=2}. + * + * Binning happens only at print time, so that we retain the flexibility to + * choose the binning. This might not be ideal for workloads that do not care + * much about precision and insert many samples all with different x values; + * in that case, pre-binning (e.g. entering both 0.115 and 0.097 as 0.1) + * should be considered. + */ +struct qdist_entry { + double x; + unsigned long count; +}; + +struct qdist { + struct qdist_entry *entries; + size_t n; + size_t size; +}; + +#define QDIST_PR_BORDER BIT(0) +#define QDIST_PR_LABELS BIT(1) +/* the remaining options only work if PR_LABELS is set */ +#define QDIST_PR_NODECIMAL BIT(2) +#define QDIST_PR_PERCENT BIT(3) +#define QDIST_PR_100X BIT(4) +#define QDIST_PR_NOBINRANGE BIT(5) + +void qdist_init(struct qdist *dist); +void qdist_destroy(struct qdist *dist); + +void qdist_add(struct qdist *dist, double x, long count); +void qdist_inc(struct qdist *dist, double x); +double qdist_xmin(const struct qdist *dist); +double qdist_xmax(const struct qdist *dist); +double qdist_avg(const struct qdist *dist); +unsigned long qdist_sample_count(const struct qdist *dist); +size_t qdist_unique_entries(const struct qdist *dist); + +/* callers must free the returned string with g_free() */ +char *qdist_pr_plain(const struct qdist *dist, size_t n_groups); + +/* callers must free the returned string with g_free() */ +char *qdist_pr(const struct qdist *dist, size_t n_groups, uint32_t opt); + +/* Only qdist code and test code should ever call this function */ +void qdist_bin__internal(struct qdist *to, const struct qdist *from, size_t n); + +#endif /* QEMU_QDIST_H */ diff --git a/include/qemu/qht.h b/include/qemu/qht.h new file mode 100644 index 0000000000..aec60aa534 --- /dev/null +++ b/include/qemu/qht.h @@ -0,0 +1,183 @@ +/* + * Copyright (C) 2016, Emilio G. Cota <cota@braap.org> + * + * License: GNU GPL, version 2 or later. + * See the COPYING file in the top-level directory. + */ +#ifndef QEMU_QHT_H +#define QEMU_QHT_H + +#include "qemu/osdep.h" +#include "qemu/seqlock.h" +#include "qemu/thread.h" +#include "qemu/qdist.h" + +struct qht { + struct qht_map *map; + QemuMutex lock; /* serializes setters of ht->map */ + unsigned int mode; +}; + +/** + * struct qht_stats - Statistics of a QHT + * @head_buckets: number of head buckets + * @used_head_buckets: number of non-empty head buckets + * @entries: total number of entries + * @chain: frequency distribution representing the number of buckets in each + * chain, excluding empty chains. + * @occupancy: frequency distribution representing chain occupancy rate. + * Valid range: from 0.0 (empty) to 1.0 (full occupancy). + * + * An entry is a pointer-hash pair. + * Each bucket can host several entries. + * Chains are chains of buckets, whose first link is always a head bucket. + */ +struct qht_stats { + size_t head_buckets; + size_t used_head_buckets; + size_t entries; + struct qdist chain; + struct qdist occupancy; +}; + +typedef bool (*qht_lookup_func_t)(const void *obj, const void *userp); +typedef void (*qht_iter_func_t)(struct qht *ht, void *p, uint32_t h, void *up); + +#define QHT_MODE_AUTO_RESIZE 0x1 /* auto-resize when heavily loaded */ + +/** + * qht_init - Initialize a QHT + * @ht: QHT to be initialized + * @n_elems: number of entries the hash table should be optimized for. + * @mode: bitmask with OR'ed QHT_MODE_* + */ +void qht_init(struct qht *ht, size_t n_elems, unsigned int mode); + +/** + * qht_destroy - destroy a previously initialized QHT + * @ht: QHT to be destroyed + * + * Call only when there are no readers/writers left. + */ +void qht_destroy(struct qht *ht); + +/** + * qht_insert - Insert a pointer into the hash table + * @ht: QHT to insert to + * @p: pointer to be inserted + * @hash: hash corresponding to @p + * + * Attempting to insert a NULL @p is a bug. + * Inserting the same pointer @p with different @hash values is a bug. + * + * Returns true on sucess. + * Returns false if the @p-@hash pair already exists in the hash table. + */ +bool qht_insert(struct qht *ht, void *p, uint32_t hash); + +/** + * qht_lookup - Look up a pointer in a QHT + * @ht: QHT to be looked up + * @func: function to compare existing pointers against @userp + * @userp: pointer to pass to @func + * @hash: hash of the pointer to be looked up + * + * Needs to be called under an RCU read-critical section. + * + * The user-provided @func compares pointers in QHT against @userp. + * If the function returns true, a match has been found. + * + * Returns the corresponding pointer when a match is found. + * Returns NULL otherwise. + */ +void *qht_lookup(struct qht *ht, qht_lookup_func_t func, const void *userp, + uint32_t hash); + +/** + * qht_remove - remove a pointer from the hash table + * @ht: QHT to remove from + * @p: pointer to be removed + * @hash: hash corresponding to @p + * + * Attempting to remove a NULL @p is a bug. + * + * Just-removed @p pointers cannot be immediately freed; they need to remain + * valid until the end of the RCU grace period in which qht_remove() is called. + * This guarantees that concurrent lookups will always compare against valid + * data. + * + * Returns true on success. + * Returns false if the @p-@hash pair was not found. + */ +bool qht_remove(struct qht *ht, const void *p, uint32_t hash); + +/** + * qht_reset - reset a QHT + * @ht: QHT to be reset + * + * All entries in the hash table are reset. No resizing is performed. + * + * If concurrent readers may exist, the objects pointed to by the hash table + * must remain valid for the existing RCU grace period -- see qht_remove(). + * See also: qht_reset_size() + */ +void qht_reset(struct qht *ht); + +/** + * qht_reset_size - reset and resize a QHT + * @ht: QHT to be reset and resized + * @n_elems: number of entries the resized hash table should be optimized for. + * + * Returns true if the resize was necessary and therefore performed. + * Returns false otherwise. + * + * If concurrent readers may exist, the objects pointed to by the hash table + * must remain valid for the existing RCU grace period -- see qht_remove(). + * See also: qht_reset(), qht_resize(). + */ +bool qht_reset_size(struct qht *ht, size_t n_elems); + +/** + * qht_resize - resize a QHT + * @ht: QHT to be resized + * @n_elems: number of entries the resized hash table should be optimized for + * + * Returns true on success. + * Returns false if the resize was not necessary and therefore not performed. + * See also: qht_reset_size(). + */ +bool qht_resize(struct qht *ht, size_t n_elems); + +/** + * qht_iter - Iterate over a QHT + * @ht: QHT to be iterated over + * @func: function to be called for each entry in QHT + * @userp: additional pointer to be passed to @func + * + * Each time it is called, user-provided @func is passed a pointer-hash pair, + * plus @userp. + */ +void qht_iter(struct qht *ht, qht_iter_func_t func, void *userp); + +/** + * qht_statistics_init - Gather statistics from a QHT + * @ht: QHT to gather statistics from + * @stats: pointer to a struct qht_stats to be filled in + * + * Does NOT need to be called under an RCU read-critical section, + * since it does not dereference any pointers stored in the hash table. + * + * When done with @stats, pass the struct to qht_statistics_destroy(). + * Failing to do this will leak memory. + */ +void qht_statistics_init(struct qht *ht, struct qht_stats *stats); + +/** + * qht_statistics_destroy - Destroy a struct qht_stats + * @stats: stuct qht_stats to be destroyed + * + * See also: qht_statistics_init(). + */ +void qht_statistics_destroy(struct qht_stats *stats); + +#endif /* QEMU_QHT_H */ diff --git a/include/qemu/seqlock.h b/include/qemu/seqlock.h index 70b01fd60d..4dfc055353 100644 --- a/include/qemu/seqlock.h +++ b/include/qemu/seqlock.h @@ -19,37 +19,29 @@ typedef struct QemuSeqLock QemuSeqLock; struct QemuSeqLock { - QemuMutex *mutex; unsigned sequence; }; -static inline void seqlock_init(QemuSeqLock *sl, QemuMutex *mutex) +static inline void seqlock_init(QemuSeqLock *sl) { - sl->mutex = mutex; sl->sequence = 0; } /* Lock out other writers and update the count. */ -static inline void seqlock_write_lock(QemuSeqLock *sl) +static inline void seqlock_write_begin(QemuSeqLock *sl) { - if (sl->mutex) { - qemu_mutex_lock(sl->mutex); - } ++sl->sequence; /* Write sequence before updating other fields. */ smp_wmb(); } -static inline void seqlock_write_unlock(QemuSeqLock *sl) +static inline void seqlock_write_end(QemuSeqLock *sl) { /* Write other fields before finalizing sequence. */ smp_wmb(); ++sl->sequence; - if (sl->mutex) { - qemu_mutex_unlock(sl->mutex); - } } static inline unsigned seqlock_read_begin(QemuSeqLock *sl) diff --git a/include/qemu/thread.h b/include/qemu/thread.h index bdae6dfdbe..c5d71cf8fc 100644 --- a/include/qemu/thread.h +++ b/include/qemu/thread.h @@ -1,6 +1,8 @@ #ifndef __QEMU_THREAD_H #define __QEMU_THREAD_H 1 +#include "qemu/processor.h" +#include "qemu/atomic.h" typedef struct QemuMutex QemuMutex; typedef struct QemuCond QemuCond; @@ -60,4 +62,37 @@ struct Notifier; void qemu_thread_atexit_add(struct Notifier *notifier); void qemu_thread_atexit_remove(struct Notifier *notifier); +typedef struct QemuSpin { + int value; +} QemuSpin; + +static inline void qemu_spin_init(QemuSpin *spin) +{ + __sync_lock_release(&spin->value); +} + +static inline void qemu_spin_lock(QemuSpin *spin) +{ + while (unlikely(__sync_lock_test_and_set(&spin->value, true))) { + while (atomic_read(&spin->value)) { + cpu_relax(); + } + } +} + +static inline bool qemu_spin_trylock(QemuSpin *spin) +{ + return __sync_lock_test_and_set(&spin->value, true); +} + +static inline bool qemu_spin_locked(QemuSpin *spin) +{ + return atomic_read(&spin->value); +} + +static inline void qemu_spin_unlock(QemuSpin *spin) +{ + __sync_lock_release(&spin->value); +} + #endif |