aboutsummaryrefslogtreecommitdiff
path: root/include/qemu/queue.h
AgeCommit message (Collapse)AuthorFilesLines
2020-09-23qemu/atomic.h: rename atomic_ to qatomic_Stefan Hajnoczi1-3/+4
clang's C11 atomic_fetch_*() functions only take a C11 atomic type pointer argument. QEMU uses direct types (int, etc) and this causes a compiler error when a QEMU code calls these functions in a source file that also included <stdatomic.h> via a system header file: $ CC=clang CXX=clang++ ./configure ... && make ../util/async.c:79:17: error: address argument to atomic operation must be a pointer to _Atomic type ('unsigned int *' invalid) Avoid using atomic_*() names in QEMU's atomic.h since that namespace is used by <stdatomic.h>. Prefix QEMU's APIs with 'q' so that atomic.h and <stdatomic.h> can co-exist. I checked /usr/include on my machine and searched GitHub for existing "qatomic_" users but there seem to be none. This patch was generated using: $ git grep -h -o '\<atomic\(64\)\?_[a-z0-9_]\+' include/qemu/atomic.h | \ sort -u >/tmp/changed_identifiers $ for identifier in $(</tmp/changed_identifiers); do sed -i "s%\<$identifier\>%q$identifier%g" \ $(git grep -I -l "\<$identifier\>") done I manually fixed line-wrap issues and misaligned rST tables. Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com> Reviewed-by: Philippe Mathieu-Daudé <philmd@redhat.com> Acked-by: Paolo Bonzini <pbonzini@redhat.com> Message-Id: <20200923105646.47864-1-stefanha@redhat.com>
2020-03-09qemu/queue.h: clear linked list pointers on removeStefan Hajnoczi1-4/+15
Do not leave stale linked list pointers around after removal. It's safer to set them to NULL so that use-after-removal results in an immediate segfault. The RCU queue removal macros are unchanged since nodes may still be traversed after removal. Suggested-by: Paolo Bonzini <pbonzini@redhat.com> Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com> Link: https://lore.kernel.org/r/20200224103406.1894923-2-stefanha@redhat.com Message-Id: <20200224103406.1894923-2-stefanha@redhat.com>
2020-02-22aio-posix: make AioHandler deletion O(1)Stefan Hajnoczi1-0/+3
It is not necessary to scan all AioHandlers for deletion. Keep a list of deleted handlers instead of scanning the full list of all handlers. The AioHandler->deleted field can be dropped. Let's check if the handler has been inserted into the deleted list instead. Add a new QLIST_IS_INSERTED() API for this check. Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com> Reviewed-by: Sergio Lopez <slp@redhat.com> Message-id: 20200214171712.541358-5-stefanha@redhat.com Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com>
2020-02-22qemu/queue.h: add QLIST_SAFE_REMOVE()Stefan Hajnoczi1-0/+14
QLIST_REMOVE() assumes the element is in a list. It also leaves the element's linked list pointers dangling. Introduce a safe version of QLIST_REMOVE() and convert open-coded instances of this pattern. Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com> Reviewed-by: Sergio Lopez <slp@redhat.com> Message-id: 20200214171712.541358-4-stefanha@redhat.com Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com>
2020-02-22rcu_queue: add QSLIST functionsPaolo Bonzini1-2/+13
QSLIST is the only family of lists for which we do not have RCU-friendly accessors, add them. Signed-off-by: Paolo Bonzini <pbonzini@redhat.com> Reviewed-by: Stefan Hajnoczi <stefanha@redhat.com> Message-id: 20200220103828.24525-1-pbonzini@redhat.com Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com>
2020-01-29migration: Simplify get_qlistEric Auger1-13/+6
Instead of inserting read elements at the head and then reversing the list, it is simpler to add each element after the previous one. Introduce QLIST_RAW_INSERT_AFTER helper and use it in get_qlist(). Signed-off-by: Eric Auger <eric.auger@redhat.com> Suggested-by: Juan Quintela <quintela@redhat.com> Reviewed-by: Juan Quintela <quintela@redhat.com> Signed-off-by: Juan Quintela <quintela@redhat.com>
2020-01-20migration: Support QLIST migrationEric Auger1-0/+39
Support QLIST migration using the same principle as QTAILQ: 94869d5c52 ("migration: migrate QTAILQ"). The VMSTATE_QLIST_V macro has the same proto as VMSTATE_QTAILQ_V. The change mainly resides in QLIST RAW macros: QLIST_RAW_INSERT_HEAD and QLIST_RAW_REVERSE. Tests also are provided. Signed-off-by: Eric Auger <eric.auger@redhat.com> Reviewed-by: Peter Xu <peterx@redhat.com> Reviewed-by: Juan Quintela <quintela@redhat.com> Signed-off-by: Juan Quintela <quintela@redhat.com>
2019-10-28queue: add QTAILQ_REMOVE_SEVERALEmilio G. Cota1-0/+10
This is faster than removing elements one by one. Will gain a user soon. Signed-off-by: Emilio G. Cota <cota@braap.org> Signed-off-by: Alex Bennée <alex.bennee@linaro.org> Reviewed-by: Richard Henderson <richard.henderson@linaro.org>
2019-08-16queue: Drop superfluous #include qemu/atomic.hMarkus Armbruster1-2/+0
When commit 5f7d05ecfda added QLIST_INSERT_HEAD_RCU() to qemu/queue.h, it had to include qemu/atomic.h. Commit 341774fe6cc removed QLIST_INSERT_HEAD_RCU() again, but neglected to remove the #include. Do that now. Signed-off-by: Markus Armbruster <armbru@redhat.com> Reviewed-by: Thomas Huth <thuth@redhat.com> Reviewed-by: Philippe Mathieu-Daudé <philmd@redhat.com> Tested-by: Philippe Mathieu-Daudé <philmd@redhat.com> Reviewed-by: Alex Bennée <alex.bennee@linaro.org> Message-Id: <20190812052359.30071-6-armbru@redhat.com>
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 2024-12-27 07:50:11 +0000