aboutsummaryrefslogtreecommitdiff
path: root/util/bitmap.c
AgeCommit message (Collapse)Author
2020-09-23qemu/atomic.h: rename atomic_ to qatomic_Stefan Hajnoczi
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>
2019-07-15bitmap: Add bitmap_copy_with_{src|dst}_offset()Peter Xu
These helpers copy the source bitmap to destination bitmap with a shift either on the src or dst bitmap. Meanwhile, we never have bitmap tests but we should. This patch also introduces the initial test cases for utils/bitmap.c but it only tests the newly introduced functions. Signed-off-by: Peter Xu <peterx@redhat.com> Reviewed-by: Juan Quintela <quintela@redhat.com> Message-Id: <20190603065056.25211-5-peterx@redhat.com> Signed-off-by: Juan Quintela <quintela@redhat.com> --- Bitmap test used sizeof(unsigned long) instead of BITS_PER_LONG.
2017-09-22bitmap: provide to_le/from_le helpersPeter Xu
Provide helpers to convert bitmaps to little endian format. It can be used when we want to send one bitmap via network to some other hosts. One thing to mention is that, these helpers only solve the problem of endianess, but it does not solve the problem of different word size on machines (the bitmaps managing same count of bits may contains different size when malloced). So we need to take care of the size alignment issue on the callers for now. Signed-off-by: Peter Xu <peterx@redhat.com> Reviewed-by: Juan Quintela <quintela@redhat.com> Signed-off-by: Juan Quintela <quintela@redhat.com>
2017-09-22bitmap: introduce bitmap_count_one()Peter Xu
Count how many bits set in the bitmap. Reviewed-by: Dr. David Alan Gilbert <dgilbert@redhat.com> Signed-off-by: Peter Xu <peterx@redhat.com> Reviewed-by: Juan Quintela <quintela@redhat.com> Signed-off-by: Juan Quintela <quintela@redhat.com>
2017-04-24bitmap: add bitmap_copy_and_clear_atomicGerd Hoffmann
Signed-off-by: Gerd Hoffmann <kraxel@redhat.com> Message-id: 20170421091632.30900-2-kraxel@redhat.com Signed-off-by: Gerd Hoffmann <kraxel@redhat.com>
2017-01-20bitmap: assert that start and nr are non negativePeter Lieven
commit e1123a3b introduced a data corruption regression in the iscsi driver because it passed -1 as nr to bitmap_set and bitmap_clear. Add an assertion to catch such flaws earlier. Suggested-by: Fam Zheng <famz@redhat.com> Reviewed-by: Fam Zheng <famz@redhat.com> Signed-off-by: Peter Lieven <pl@kamp.de> Message-Id: <1484844230-24490-1-git-send-email-pl@kamp.de> Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
2016-10-08bitmap: refine and move BITMAP_{FIRST/LAST}_WORD_MASKWei Yang
According to linux kernel commit <89c1e79eb30> ("linux/bitmap.h: improve BITMAP_{LAST,FIRST}_WORD_MASK"), these two macro could be improved. This patch takes this change and also move them all in header file. Signed-off-by: Wei Yang <richard.weiyang@gmail.com> Signed-off-by: Michael Tokarev <mjt@tls.msk.ru>
2016-02-04util: Clean up includesPeter Maydell
Clean up includes so that osdep.h is included first and headers which it implies are not included manually. This commit was created with scripts/clean-includes. Signed-off-by: Peter Maydell <peter.maydell@linaro.org> Message-id: 1454089805-5470-6-git-send-email-peter.maydell@linaro.org
2015-09-11maint: remove / fix many doubled wordsDaniel P. Berrange
Many source files have doubled words (eg "the the", "to to", and so on). Most of these can simply be removed, but a couple were actual mis-spellings (eg "to to" instead of "to do"). There was even one triple word score "to to to" :-) Signed-off-by: Daniel P. Berrange <berrange@redhat.com> Reviewed-by: Marc-André Lureau <marcandre.lureau@redhat.com> Reviewed-by: Markus Armbruster <armbru@redhat.com> Signed-off-by: Michael Tokarev <mjt@tls.msk.ru>
2015-06-05bitmap: add atomic test and clearStefan Hajnoczi
The new bitmap_test_and_clear_atomic() function clears a range and returns whether or not the bits were set. Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com> Message-Id: <1417519399-3166-3-git-send-email-stefanha@redhat.com> [Test before xchg; then a full barrier is needed at the end just like in the previous patch. The barrier can be avoided if we did at least one xchg. - Paolo] Reviewed-by: Fam Zheng <famz@redhat.com> Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
2015-06-05bitmap: add atomic set functionsStefan Hajnoczi
Use atomic_or() for atomic bitmaps where several threads may set bits at the same time. This avoids the race condition between threads loading an element, bitwise ORing, and then storing the element. When setting all bits in a word we can avoid atomic ops and instead just use an smp_mb() at the end. Most bitmap users don't need atomicity so introduce new functions. Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com> Message-Id: <1417519399-3166-2-git-send-email-stefanha@redhat.com> [Avoid barrier in the single word case, use full barrier instead of write. - Paolo] Reviewed-by: Fam Zheng <famz@redhat.com> Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
2014-01-13bitmap: use long as indexJuan Quintela
Move index and size fields from int to long. We need that for migration. long is 64 bits on sane architectures, and 32bits should be enough on all the 32bits architectures. Signed-off-by: Juan Quintela <quintela@redhat.com> Reviewed-by: Eric Blake <eblake@redhat.com> Reviewed-by: Orit Wasserman <owasserm@redhat.com>
2013-01-12build: move libqemuutil.a components to util/Paolo Bonzini
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>