aboutsummaryrefslogtreecommitdiff
path: root/include/qemu/queue.h
AgeCommit message (Collapse)AuthorFilesLines
2019-02-05queue: fix QTAILQ_FOREACH_REVERSE_SAFEPaolo Bonzini1-1/+1
The iteration was stopping as soon as prev_var was set to NULL, and therefore it skipped the first element. Fortunately, or unfortunately, we have only one use of QTAILQ_FOREACH_REVERSE_SAFE. Thus this only showed up as incorrect register preferences on the very first translation block that was compiled. Reported-by: Thomas Huth <thuth@redhat.com> Reviewed-by: Emilio G. Cota <cota@braap.org> Reviewed-by: Richard Henderson <richard.henderson@linaro.org> Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
2019-01-11qemu/queue.h: simplify reverse access to QTAILQPaolo Bonzini1-8/+8
The new definition of QTAILQ does not require passing the headname, remove it. Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
2019-01-11qemu/queue.h: reimplement QTAILQ without pointer-to-pointersPaolo Bonzini1-78/+61
QTAILQ is a doubly linked list, with a pointer-to-pointer to the last element from the head, and the previous element from each node. But if you squint enough, QTAILQ becomes a combination of a singly-linked forwards list, and another singly-linked list which goes backwards and is circular. This is the idea that lets QTAILQ implement reverse iteration: only, because the backwards list points inside the node, accessing the previous element needs to go two steps back and one forwards. What this patch does is implement it in these terms, without actually changing the in-memory layout at all. The coexistence of the two lists is realized by making QTAILQ_HEAD and QTAILQ_ENTRY unions of the forwards pointer and a generic QTailQLink node. Thq QTailQLink can walk the list in both directions; the union is needed so that the forwards pointer can have the correct type, as a sort of poor man's template. While there are other ways to get the same layout without a union, this one has the advantage of simpler operation in the debugger, because the fields tqh_first and tqe_next still exist as before the patch. Those fields are also used by scripts/qemugdb/mtree.py, so it's a good idea to preserve them. The advantage of the new representation is that the two-back-one-forward dance done by backwards accesses can be done all while operating on QTailQLinks. No casting to the head struct is needed anymore because, even though the QTailQLink's forward pointer is a void *, we can use typeof to recover the correct type. This patch only changes the implementation, not the interface. The next patch will remove the head struct name from the backwards visit macros. Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
2019-01-11qemu/queue.h: remove Q_TAILQ_{HEAD,ENTRY}Paolo Bonzini1-8/+6
These are not present for other kinds of queue, and unused. Zap them before more changes are made to the QTAILQ implementation. Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
2018-08-22migration: hold the lock only if it is really neededXiao Guangrong1-0/+1
Try to hold src_page_req_mutex only if the queue is not empty Reviewed-by: Dr. David Alan Gilbert <dgilbert@redhat.com> Reviewed-by: Peter Xu <peterx@redhat.com> Signed-off-by: Xiao Guangrong <xiaoguangrong@tencent.com> Reviewed-by: Juan Quintela <quintela@redhat.com> Signed-off-by: Juan Quintela <quintela@redhat.com>
2018-03-27queue: add QSIMPLEQ_PREPEND()Stefan Hajnoczi1-0/+8
QSIMPLEQ_CONCAT(a, b) joins a = a + b. The new QSIMPLEQ_PREPEND(a, b) API joins a = b + a. Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com> Reviewed-by: Paolo Bonzini <pbonzini@redhat.com> Message-id: 20180322152834.12656-2-stefanha@redhat.com Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com>
2017-12-29tcg: Dynamically allocate TCGOpsRichard Henderson1-0/+5
With no fixed array allocation, we can't overflow a buffer. This will be important as optimizations related to host vectors may expand the number of ops used. Use QTAILQ to link the ops together. Signed-off-by: Richard Henderson <richard.henderson@linaro.org>
2017-01-24migration: migrate QTAILQJianjun Duan1-0/+60
Currently we cannot directly transfer a QTAILQ instance because of the limitation in the migration code. Here we introduce an approach to transfer such structures. We created VMStateInfo vmstate_info_qtailq for QTAILQ. Similar VMStateInfo can be created for other data structures such as list. When a QTAILQ is migrated from source to target, it is appended to the corresponding QTAILQ structure, which is assumed to have been properly initialized. This approach will be used to transfer pending_events and ccs_list in spapr state. We also create some macros in qemu/queue.h to access a QTAILQ using pointer arithmetic. This ensures that we do not depend on the implementation details about QTAILQ in the migration code. Reviewed-by: Dr. David Alan Gilbert <dgilbert@redhat.com> Signed-off-by: Jianjun Duan <duanj@linux.vnet.ibm.com> Message-Id: <1484852453-12728-3-git-send-email-duanj@linux.vnet.ibm.com> Signed-off-by: Dr. David Alan Gilbert <dgilbert@redhat.com>
2016-09-13qtail: clean up direct access to tqe_prev fieldIgor Mammedov1-0/+2
instead of accessing tqe_prev field dircetly outside of queue.h use macros to check if element is in list and make sure that afer element is removed from list tqe_prev field could be used to do the same check. Signed-off-by: Igor Mammedov <imammedo@redhat.com> Message-Id: <1469450832-84343-1-git-send-email-imammedo@redhat.com> Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
2016-07-12Clean up ill-advised or unusual header guardsMarkus Armbruster1-3/+3
Cleaned up with scripts/clean-header-guards.pl. Signed-off-by: Markus Armbruster <armbru@redhat.com> Reviewed-by: Richard Henderson <rth@twiddle.net>
2015-10-16block: Remove bdrv_swap()Kevin Wolf1-6/+0
bdrv_swap() is unused now. Remove it and all functions that have no other users than bdrv_swap(). In particular, this removes the .bdrv_rebind callbacks from block drivers. Signed-off-by: Kevin Wolf <kwolf@redhat.com> Reviewed-by: Max Reitz <mreitz@redhat.com> Reviewed-by: Alberto Garcia <berto@igalia.com> Reviewed-by: Fam Zheng <famz@redhat.com> Reviewed-by: Stefan Hajnoczi <stefanha@redhat.com>
2015-06-12queue.h: Add QLIST_FIX_HEAD_PTR()Kevin Wolf1-0/+6
If the head of a list has been moved to a different memory location, the le_prev link in the first list entry has to be fixed up. Provide a macro that implements this fixup. Signed-off-by: Kevin Wolf <kwolf@redhat.com> Reviewed-by: Eric Blake <eblake@redhat.com> Reviewed-by: Max Reitz <mreitz@redhat.com>
2015-03-12queue: fix QSLIST_INSERT_HEAD_ATOMIC racePaolo Bonzini1-5/+6
There is a not-so-subtle race in QSLIST_INSERT_HEAD_ATOMIC. Because atomic_cmpxchg returns the old value instead of a success flag, QSLIST_INSERT_HEAD_ATOMIC was checking for success by comparing against the second argument to atomic_cmpxchg. Unfortunately, this only works if the second argument is a local or thread-local variable. If it is in memory, it can be subject to common subexpression elimination (and then everything's fine) or reloaded after the atomic_cmpxchg, depending on the compiler's whims. If the latter happens, the race can happen. A thread can sneak in, doing something on elm->field.sle_next after the atomic_cmpxchg and before the comparison. This causes a wrong failure, and then two threads are using "elm" at the same time. In the case discovered by Christian, the sequence was likely something like this: thread 1 | thread 2 QSLIST_INSERT_HEAD_ATOMIC | atomic_cmpxchg succeeds | elm added to list | | steal release_pool | QSLIST_REMOVE_HEAD | elm removed from list | ... | QSLIST_INSERT_HEAD_ATOMIC | (overwrites sle_next) spurious failure | atomic_cmpxchg succeeds | elm added to list again | | steal release_pool | QSLIST_REMOVE_HEAD | elm removed again | The last three steps could be done by a third thread as well. A reproducer that failed in a matter of seconds is as follows: - the guest has 32 VCPUs on a 28 core host (hyperthreading was enabled), memory was 16G just to err on the safe side (the host has 64G, but hey at least you need no s390) - the guest has 24 null-aio virtio-blk devices using dataplane (-object iothread,id=ioN -drive if=none,id=blkN,driver=null-aio,size=500G -device virtio-blk-pci,iothread=ioN,drive=blkN) - the guest also has a single network interface. It's only doing loopback tests so slirp vs. tap and the model doesn't matter. - the guest is running fio with the following script: [global] rw=randread blocksize=16k ioengine=libaio runtime=10m buffered=0 fallocate=none time_based iodepth=32 [virtio1a] filename=/dev/block/252\:16 [virtio1b] filename=/dev/block/252\:16 ... [virtio24a] filename=/dev/block/252\:384 [virtio24b] filename=/dev/block/252\:384 [listen1] protocol=tcp ioengine=net port=12345 listen rw=read bs=4k size=1000g [connect1] protocol=tcp hostname=localhost ioengine=net port=12345 protocol=tcp rw=write startdelay=1 size=1000g ... [listen8] protocol=tcp ioengine=net port=12352 listen rw=read bs=4k size=1000g [connect8] protocol=tcp hostname=localhost ioengine=net port=12352 rw=write startdelay=1 size=1000g Moral of the story: I should refrain from writing more clever stuff. At least it looks like it is not too clever to be undebuggable. Reported-by: Christian Borntraeger <borntraeger@de.ibm.com> Tested-by: Christian Borntraeger <borntraeger@de.ibm.com> Signed-off-by: Paolo Bonzini <pbonzini@redhat.com> Message-id: 1426002357-6889-1-git-send-email-pbonzini@redhat.com Fixes: c740ad92d0d958fa785e5d7aa1b67ecaf30a6a54 Signed-off-by: Paolo Bonzini <pbonzini@redhat.com> Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com>
2015-02-16rcu: introduce RCU-enabled QLISTMike Day1-11/+0
Add RCU-enabled variants on the existing bsd DQ facility. Each operation has the same interface as the existing (non-RCU) version. Also, each operation is implemented as macro. Using the RCU-enabled QLIST, existing QLIST users will be able to convert to RCU without using a different list interface. Signed-off-by: Mike Day <ncmike@ncultra.org> Reviewed-by: Fam Zheng <famz@redhat.com> Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
2015-02-02rcu: add rcu libraryPaolo Bonzini1-0/+13
This includes a (mangled) copy of the liburcu code. The main changes are: 1) removing dependencies on many other header files in liburcu; 2) removing for simplicity the tentative busy waiting in synchronize_rcu, which has limited performance effects; 3) replacing futexes in synchronize_rcu with QemuEvents for Win32 portability. The API is the same as liburcu, so it should be possible in the future to require liburcu on POSIX systems for example and use our copy only on Windows. Among the various versions available I chose urcu-mb, which is the least invasive implementation even though it does not have the fastest rcu_read_{lock,unlock} implementation. The urcu flavor can be changed later, after benchmarking. Reviewed-by: Fam Zheng <famz@redhat.com> Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
2015-01-13QSLIST: add lock-free operationsPaolo Bonzini1-2/+13
These operations are trivial to implement and do not have ABA problems. They are enough to implement simple multiple-producer, single consumer lock-free lists or, as in the next patch, the multiple consumers can steal a whole batch of elements and process them at their leisure. Signed-off-by: Paolo Bonzini <pbonzini@redhat.com> Reviewed-by: Fam Zheng <famz@redhat.com> Message-id: 1417518350-6167-5-git-send-email-pbonzini@redhat.com Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com>
2014-12-12linux-aio: simplify removal of completed iocbs from the listPaolo Bonzini1-0/+11
There is no need to do another O(n) pass on the list; the iocb to split the list at is already available through the array we passed to io_submit. Signed-off-by: Paolo Bonzini <pbonzini@redhat.com> Reviewed-by: Kevin Wolf <kwolf@redhat.com> Message-id: 1418305950-30924-6-git-send-email-pbonzini@redhat.com Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com>
2012-12-19misc: move include files to include/qemu/Paolo Bonzini1-0/+414
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
generated by cgit v1.1 at 2025-03-19 14:17:50 +0000