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: NPeter Xu <peterx@redhat.com>
Reviewed-by: NJuan Quintela <quintela@redhat.com>
Message-Id: <20190603065056.25211-5-peterx@redhat.com>
Signed-off-by: NJuan Quintela <quintela@redhat.com>

---

Bitmap test used sizeof(unsigned long) instead of BITS_PER_LONG.

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: NPeter Xu <peterx@redhat.com>
Reviewed-by: NJuan Quintela <quintela@redhat.com>
Signed-off-by: NJuan Quintela <quintela@redhat.com>

Count how many bits set in the bitmap.
Reviewed-by: NDr. David Alan Gilbert <dgilbert@redhat.com>
Signed-off-by: NPeter Xu <peterx@redhat.com>
Reviewed-by: NJuan Quintela <quintela@redhat.com>
Signed-off-by: NJuan Quintela <quintela@redhat.com>

Signed-off-by: NGerd Hoffmann <kraxel@redhat.com>
Message-id: 20170421091632.30900-2-kraxel@redhat.com
Signed-off-by: NGerd Hoffmann <kraxel@redhat.com>

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: NFam Zheng <famz@redhat.com>
Reviewed-by: NFam Zheng <famz@redhat.com>
Signed-off-by: NPeter Lieven <pl@kamp.de>
Message-Id: <1484844230-24490-1-git-send-email-pl@kamp.de>
Signed-off-by: NPaolo Bonzini <pbonzini@redhat.com>

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: NWei Yang <richard.weiyang@gmail.com>
Signed-off-by: NMichael Tokarev <mjt@tls.msk.ru>

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: NPeter Maydell <peter.maydell@linaro.org>
Message-id: 1454089805-5470-6-git-send-email-peter.maydell@linaro.org

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: NDaniel P. Berrange <berrange@redhat.com>
Reviewed-by: NMarc-André Lureau <marcandre.lureau@redhat.com>
Reviewed-by: NMarkus Armbruster <armbru@redhat.com>
Signed-off-by: NMichael Tokarev <mjt@tls.msk.ru>

The new bitmap_test_and_clear_atomic() function clears a range and
returns whether or not the bits were set.
Signed-off-by: NStefan 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: NFam Zheng <famz@redhat.com>
Signed-off-by: NPaolo Bonzini <pbonzini@redhat.com>

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: NStefan 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: NFam Zheng <famz@redhat.com>
Signed-off-by: NPaolo Bonzini <pbonzini@redhat.com>

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: NJuan Quintela <quintela@redhat.com>
Reviewed-by: NEric Blake <eblake@redhat.com>
Reviewed-by: NOrit Wasserman <owasserm@redhat.com>

Signed-off-by: NPaolo Bonzini <pbonzini@redhat.com>

Signed-off-by: NPaolo Bonzini <pbonzini@redhat.com>

Add most used bitmap and bitops functions into bitmap.c and bitops.c.
Theses functions are mostly copied from Linux kernel source.

Some of these functions are already redefined in the VNC server. Some
of them could be used for some block stuff. The yet yo be submitted
NUMA work also need bitmaps.

bitops_ffsl() and bitops_flsl() are here because bitops/bitmap works
on unsigned long, not int, and we can't use current code because:
* ffs only works on int
* qemu_fls only works on int
* ffsl is a GNU extension
Signed-off-by: NCorentin Chary <corentincj@iksaif.net>
Signed-off-by: NAnthony Liguori <aliguori@us.ibm.com>