aboutsummaryrefslogtreecommitdiff
path: root/util/qht.c
AgeCommit message (Collapse)AuthorFilesLines
2016-10-06qht: fix unlock-after-free segfault upon resizingEmilio G. Cota1-21/+28
The old map's bucket locks are being unlocked *after* that same old map has been passed to RCU for destruction. This is a bug that can cause a segfault, since there's no guarantee that the deletion will be deferred (e.g. there may be no concurrent readers). The segfault is easily triggered in RHEL6/CentOS6 with qht-test, particularly on a single-core system or by pinning qht-test to a single core. Fix it by unlocking the map's bucket locks right after having published the new map, and (crucially) before marking the map for deletion via call_rcu(). While at it, expand qht_do_resize() to atomically do (1) a reset, (2) a resize, or (3) a reset+resize. This simplifies the calling code, since the new function (qht_do_resize_reset()) acquires and releases the buckets' locks. Note that no qht_do_reset inline is provided, since it would have no users--qht_reset() already performs a reset without taking ht->lock. Reported-by: Peter Maydell <peter.maydell@linaro.org> Reported-by: Daniel P. Berrange <berrange@redhat.com> Signed-off-by: Emilio G. Cota <cota@braap.org> Message-Id: <1475706880-10667-3-git-send-email-cota@braap.org> Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
2016-10-06qht: simplify qht_reset_sizeEmilio G. Cota1-5/+3
Sometimes gcc doesn't pick up the fact that 'new' is properly set if 'resize == true', which may generate an unnecessary build warning. Fix it by removing 'resize' and directly checking that 'new' is non-NULL. Signed-off-by: Emilio G. Cota <cota@braap.org> Message-Id: <1475706880-10667-2-git-send-email-cota@braap.org> Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
2016-10-04util/qht: atomically set b->hashesAlex Bennée1-5/+5
ThreadSanitizer detects a possible race between reading/writing the hashes. The ordering semantics are already documented for QHT however for true C11 compliance we should use relaxed atomic primitives for accesses that are done across threads. On x86 this slightly changes to the code to not do a load/compare in a single instruction leading to a slight performance degradation. Running 'taskset -c 0 tests/qht-bench -n 1 -d 10' (i.e. all lookups) 10 times, we get: before the patch: $ ./mean.pl 34.04 34.24 34.38 34.25 34.18 34.51 34.46 34.44 34.29 34.08 34.287 +- 0.160072900059109 after: $ ./mean.pl 33.94 34.00 33.52 33.46 33.55 33.71 34.27 34.06 34.28 34.58 33.937 +- 0.374731014640279 Signed-off-by: Alex Bennée <alex.bennee@linaro.org> Reviewed-by: Emilio G. Cota <cota@braap.org> Message-Id: <20160930213106.20186-10-alex.bennee@linaro.org> Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
2016-08-02qht: do not segfault when gathering stats from an uninitialized qhtEmilio G. Cota1-1/+6
So far, QHT functions assume that the passed qht has previously been initialized--otherwise they segfault. This patch makes an exception for qht_statistics_init, with the goal of simplifying calling code. For instance, qht_statistics_init is called from the 'info jit' dump, and given that under KVM the TB qht is never initialized, we get a segfault. Thus, instead of complicating the 'info jit' code with additional checks, let's allow passing an uninitialized qht to qht_statistics_init. While at it, add a test for this to test-qht. Before the patch (for $ qemu -enable-kvm [...]): (qemu) info jit [...] direct jump count 0 (0%) (2 jumps=0 0%) Program received signal SIGSEGV, Segmentation fault. After the patch the "TB hash buckets", "TB hash occupancy" and "TB hash avg chain" lines are omitted. (qemu) info jit [...] direct jump count 0 (0%) (2 jumps=0 0%) TB hash buckets 0/0 (-nan% head buckets used) TB hash occupancy nan% avg chain occ. Histogram: (null) TB hash avg chain nan buckets. Histogram: (null) [...] Reported by: Changlong Xie <xiecl.fnst@cn.fujitsu.com> Signed-off-by: Emilio G. Cota <cota@braap.org> Message-Id: <1469205390-14369-1-git-send-email-cota@braap.org> [Extract printing statistics to an entirely separate function. - Paolo] Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
2016-08-02util/qht: Document memory ordering assumptionsPaolo Bonzini1-1/+6
It is naturally expected that some memory ordering should be provided around qht_insert() and qht_lookup(). Document these assumptions in the header file and put some comments in the source to denote how that memory ordering requirements are fulfilled. Signed-off-by: Paolo Bonzini <pbonzini@redhat.com> [Sergey Fedorov: commit title and message provided; comment on qht_remove() elided] Signed-off-by: Sergey Fedorov <serge.fdrv@gmail.com> Message-Id: <20160715175852.30749-2-sergey.fedorov@linaro.org> Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
2016-06-16clean-includes: run it once morePaolo Bonzini1-0/+1
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
2016-06-11qht: QEMU's fast, resizable and scalable Hash TableEmilio G. Cota1-0/+833
This is a fast, scalable chained hash table with optional auto-resizing, allowing reads that are concurrent with reads, and reads/writes that are concurrent with writes to separate buckets. A hash table with these features will be necessary for the scalability of the ongoing MTTCG work; before those changes arrive we can already benefit from the single-threaded speedup that qht also provides. Signed-off-by: Emilio G. Cota <cota@braap.org> Message-Id: <1465412133-3029-11-git-send-email-cota@braap.org> Signed-off-by: Richard Henderson <rth@twiddle.net>