aboutsummaryrefslogtreecommitdiff
path: root/util/hbitmap.c
AgeCommit message (Collapse)AuthorFilesLines
2022-03-07block/dirty-bitmap: introduce bdrv_dirty_bitmap_status()Vladimir Sementsov-Ogievskiy1-0/+33
Add a convenient function similar with bdrv_block_status() to get status of dirty bitmap. Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Reviewed-by: Hanna Reitz <hreitz@redhat.com> Message-Id: <20220303194349.2304213-9-vsementsov@virtuozzo.com> Signed-off-by: Hanna Reitz <hreitz@redhat.com>
2020-03-18block/dirty-bitmap: improve _next_dirty_area APIVladimir Sementsov-Ogievskiy1-17/+27
Firstly, _next_dirty_area is for scenarios when we may contiguously search for next dirty area inside some limited region, so it is more comfortable to specify "end" which should not be recalculated on each iteration. Secondly, let's add a possibility to limit resulting area size, not limiting searching area. This will be used in NBD code in further commit. (Note that now bdrv_dirty_bitmap_next_dirty_area is unused) Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Reviewed-by: Max Reitz <mreitz@redhat.com> Reviewed-by: John Snow <jsnow@redhat.com> Message-id: 20200205112041.6003-8-vsementsov@virtuozzo.com Signed-off-by: John Snow <jsnow@redhat.com>
2020-03-18block/dirty-bitmap: add _next_dirty APIVladimir Sementsov-Ogievskiy1-28/+32
We have bdrv_dirty_bitmap_next_zero, let's add corresponding bdrv_dirty_bitmap_next_dirty, which is more comfortable to use than bitmap iterators in some cases. For test modify test_hbitmap_next_zero_check_range to check both next_zero and next_dirty and add some new checks. Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Reviewed-by: Max Reitz <mreitz@redhat.com> Reviewed-by: John Snow <jsnow@redhat.com> Message-id: 20200205112041.6003-7-vsementsov@virtuozzo.com Signed-off-by: John Snow <jsnow@redhat.com>
2020-03-18block/dirty-bitmap: switch _next_dirty_area and _next_zero to int64_tVladimir Sementsov-Ogievskiy1-5/+8
We are going to introduce bdrv_dirty_bitmap_next_dirty so that same variable may be used to store its return value and to be its parameter, so it would int64_t. Similarly, we are going to refactor hbitmap_next_dirty_area to use hbitmap_next_dirty together with hbitmap_next_zero, therefore we want hbitmap_next_zero parameter type to be int64_t too. So, for convenience update all parameters of *_next_zero and *_next_dirty_area to be int64_t. Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Reviewed-by: Max Reitz <mreitz@redhat.com> Reviewed-by: John Snow <jsnow@redhat.com> Message-id: 20200205112041.6003-6-vsementsov@virtuozzo.com Signed-off-by: John Snow <jsnow@redhat.com>
2020-03-18hbitmap: drop meta bitmaps as they are unusedVladimir Sementsov-Ogievskiy1-16/+0
Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Reviewed-by: Max Reitz <mreitz@redhat.com> Reviewed-by: John Snow <jsnow@redhat.com> Message-id: 20200205112041.6003-5-vsementsov@virtuozzo.com Signed-off-by: John Snow <jsnow@redhat.com>
2020-03-18hbitmap: unpublish hbitmap_iter_skip_wordsVladimir Sementsov-Ogievskiy1-1/+1
Function is internal and even commented as internal. Drop its definition from .h file. Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Reviewed-by: Max Reitz <mreitz@redhat.com> Reviewed-by: John Snow <jsnow@redhat.com> Message-id: 20200205112041.6003-4-vsementsov@virtuozzo.com Signed-off-by: John Snow <jsnow@redhat.com>
2020-03-18hbitmap: move hbitmap_iter_next_word to hbitmap.cVladimir Sementsov-Ogievskiy1-0/+29
The function is definitely internal (it's not used by third party and it has complicated interface). Move it to .c file. Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Reviewed-by: Max Reitz <mreitz@redhat.com> Reviewed-by: John Snow <jsnow@redhat.com> Message-id: 20200205112041.6003-3-vsementsov@virtuozzo.com Signed-off-by: John Snow <jsnow@redhat.com>
2020-03-18hbitmap: assert that we don't create bitmap larger than INT64_MAXVladimir Sementsov-Ogievskiy1-0/+2
We have APIs which returns signed int64_t, to be able to return error. Therefore we can't handle bitmaps with absolute size larger than (INT64_MAX+1). Still, keep maximum to be INT64_MAX which is a bit safer. Note, that bitmaps are used to represent disk images, which can't exceed INT64_MAX anyway. Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Reviewed-by: Max Reitz <mreitz@redhat.com> Reviewed-by: Eric Blake <eblake@redhat.com> Reviewed-by: John Snow <jsnow@redhat.com> Message-id: 20200205112041.6003-2-vsementsov@virtuozzo.com Signed-off-by: John Snow <jsnow@redhat.com>
2019-10-28hbitmap: handle set/reset with zero lengthVladimir Sementsov-Ogievskiy1-0/+8
Passing zero length to these functions leads to unpredicted results. Zero-length set/reset may occur in active-mirror, on zero-length write (which is unlikely, but not guaranteed to never happen). Let's just do nothing on zero-length request. Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Message-id: 20191011090711.19940-2-vsementsov@virtuozzo.com Reviewed-by: Max Reitz <mreitz@redhat.com> Cc: qemu-stable@nongnu.org Signed-off-by: Max Reitz <mreitz@redhat.com>
2019-10-17util/hbitmap: strict hbitmap_resetVladimir Sementsov-Ogievskiy1-0/+4
hbitmap_reset has an unobvious property: it rounds requested region up. It may provoke bugs, like in recently fixed write-blocking mode of mirror: user calls reset on unaligned region, not keeping in mind that there are possible unrelated dirty bytes, covered by rounded-up region and information of this unrelated "dirtiness" will be lost. Make hbitmap_reset strict: assert that arguments are aligned, allowing only one exception when @start + @count == hb->orig_size. It's needed to comfort users of hbitmap_next_dirty_area, which cares about hb->orig_size. Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Reviewed-by: Max Reitz <mreitz@redhat.com> Message-Id: <20190806152611.280389-1-vsementsov@virtuozzo.com> [Maintainer edit: Max's suggestions from on-list. --js] [Maintainer edit: Eric's suggestion for aligned macro. --js] Signed-off-by: John Snow <jsnow@redhat.com>
2019-08-16hbitmap: enable merging across granularitiesJohn Snow1-1/+35
Signed-off-by: John Snow <jsnow@redhat.com> Reviewed-by: Max Reitz <mreitz@redhat.com> Message-id: 20190709232550.10724-9-jsnow@redhat.com Signed-off-by: John Snow <jsnow@redhat.com>
2019-08-16hbitmap: Fix merge when b is empty, and result is not an alias of aJohn Snow1-3/+10
Nobody calls the function like this currently, but we neither prohibit or cope with this behavior. I decided to make the function cope with it. Signed-off-by: John Snow <jsnow@redhat.com> Reviewed-by: Max Reitz <mreitz@redhat.com> Message-id: 20190709232550.10724-8-jsnow@redhat.com Signed-off-by: John Snow <jsnow@redhat.com>
2019-08-06util/hbitmap: update orig_size on truncateVladimir Sementsov-Ogievskiy1-1/+5
Without this, hbitmap_next_zero and hbitmap_next_dirty_area are broken after truncate. So, orig_size is broken since it's introduction in 76d570dc495c56bb. Fixes: 76d570dc495c56bb Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Message-id: 20190805120120.23585-1-vsementsov@virtuozzo.com Reviewed-by: Max Reitz <mreitz@redhat.com> Cc: qemu-stable@nongnu.org Signed-off-by: Max Reitz <mreitz@redhat.com>
2019-01-15Revert "hbitmap: Add @advance param to hbitmap_iter_next()"Vladimir Sementsov-Ogievskiy1-8/+4
This reverts commit a33fbb4f8b64226becf502a123733776ce319b24. The functionality is unused. Note: in addition to automatic revert, drop second parameter in hbitmap_iter_next() call from hbitmap_next_dirty_area() too. Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Reviewed-by: John Snow <jsnow@redhat.com>
2019-01-15dirty-bitmap: add bdrv_dirty_bitmap_next_dirty_areaVladimir Sementsov-Ogievskiy1-0/+39
The function alters bdrv_dirty_iter_next_area(), which is wrong and less efficient (see further commit "block/mirror: fix and improve do_sync_target_write" for description). Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
2019-01-15dirty-bitmap: improve bdrv_dirty_bitmap_next_zeroVladimir Sementsov-Ogievskiy1-5/+22
Add bytes parameter to the function, to limit searched range. Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
2018-10-29bitmap: Update count after a mergeEric Blake1-0/+3
We need an accurate count of the number of bits set in a bitmap after a merge. In particular, since the merge operation short-circuits a merge from an empty source, if you have bitmaps A, B, and C where B started empty, then merge C into B, and B into A, an inaccurate count meant that A did not get the contents of C. In the worst case, we may falsely regard the bitmap as empty when it has had new writes merged into it. Fixes: be58721db CC: qemu-stable@nongnu.org Signed-off-by: Eric Blake <eblake@redhat.com> Signed-off-by: John Snow <jsnow@redhat.com> Reviewed-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Message-id: 20181002233314.30159-1-jsnow@redhat.com Signed-off-by: John Snow <jsnow@redhat.com>
2018-10-29dirty-bitmap: make it possible to restore bitmap after mergeVladimir Sementsov-Ogievskiy1-3/+8
Add backup parameter to bdrv_merge_dirty_bitmap() to be used then with bdrv_restore_dirty_bitmap() if it needed to restore the bitmap after merge operation. This is needed to implement bitmap merge transaction action in further commit. Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Reviewed-by: John Snow <jsnow@redhat.com>
2018-06-18hbitmap: Add @advance param to hbitmap_iter_next()Max Reitz1-3/+7
This new parameter allows the caller to just query the next dirty position without moving the iterator. Signed-off-by: Max Reitz <mreitz@redhat.com> Reviewed-by: Fam Zheng <famz@redhat.com> Reviewed-by: John Snow <jsnow@redhat.com> Message-id: 20180613181823.13618-8-mreitz@redhat.com Signed-off-by: Max Reitz <mreitz@redhat.com>
2018-02-07hbitmap: fix missing restore count when finish deserializationLiang Li1-0/+1
The .count of HBitmap is forgot to set in function hbitmap_deserialize_finish, let's set it to the right value. Cc: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Cc: Fam Zheng <famz@redhat.com> Cc: Max Reitz <mreitz@redhat.com> Cc: John Snow <jsnow@redhat.com> Reviewed-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Signed-off-by: Weiping Zhang <zhangweiping@didichuxing.com> Signed-off-by: Liang Li <liliangleo@didichuxing.com> Reviewed-by: John Snow <jsnow@redhat.com> Message-id: 20180118131308.GA2181@liangdeMacBook-Pro.local Signed-off-by: John Snow <jsnow@redhat.com>
2017-12-18hbitmap: add next_zero functionVladimir Sementsov-Ogievskiy1-0/+39
The function searches for next zero bit. Also add interface for BdrvDirtyBitmap and unit test. Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Reviewed-by: John Snow <jsnow@redhat.com> Message-id: 20171012135313.227864-2-vsementsov@virtuozzo.com Signed-off-by: Jeff Cody <jcody@redhat.com>
2017-10-06hbitmap: Rename serialization_granularity to serialization_alignEric Blake1-4/+4
The only client of hbitmap_serialization_granularity() is dirty-bitmap's bdrv_dirty_bitmap_serialization_align(). Keeping the two names consistent is worthwhile, and the shorter name is more representative of what the function returns (the required alignment to be used for start/count of other serialization functions, where violating the alignment causes assertion failures). Signed-off-by: Eric Blake <eblake@redhat.com> Reviewed-by: John Snow <jsnow@redhat.com> Reviewed-by: Kevin Wolf <kwolf@redhat.com> Reviewed-by: Fam Zheng <famz@redhat.com> Signed-off-by: Kevin Wolf <kwolf@redhat.com>
2017-07-11qmp: add x-debug-block-dirty-bitmap-sha256Vladimir Sementsov-Ogievskiy1-0/+11
Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Message-id: 20170628120530.31251-26-vsementsov@virtuozzo.com Signed-off-by: Max Reitz <mreitz@redhat.com>
2017-07-11block/dirty-bitmap: add deserialize_ones funcVladimir Sementsov-Ogievskiy1-0/+17
Add bdrv_dirty_bitmap_deserialize_ones() function, which is needed for qcow2 bitmap loading, to handle unallocated bitmap parts, marked as all-ones. Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Reviewed-by: Kevin Wolf <kwolf@redhat.com> Reviewed-by: John Snow <jsnow@redhat.com> Message-id: 20170628120530.31251-7-vsementsov@virtuozzo.com Signed-off-by: Max Reitz <mreitz@redhat.com>
2017-07-11hbitmap: improve dirty iterVladimir Sementsov-Ogievskiy1-1/+22
Make dirty iter resistant to resetting bits in corresponding HBitmap. Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Reviewed-by: Max Reitz <mreitz@redhat.com> Reviewed-by: John Snow <jsnow@redhat.com> Message-id: 20170628120530.31251-4-vsementsov@virtuozzo.com Signed-off-by: Max Reitz <mreitz@redhat.com>
2017-01-26hbitmap: Add hbitmap_is_serializable()Max Reitz1-3/+19
Bitmaps with a granularity of 58 or above can be neither serialized nor deserialized (see the comment in the function added in this series for an explanation). This patch adds a function so that we can check whether a bitmap actually can be (de-)serialized at all, thus avoiding failing the necessary assertion in hbitmap_serialization_granularity(). Signed-off-by: Max Reitz <mreitz@redhat.com> Message-Id: <20161115225746.3590-2-mreitz@redhat.com> Reviewed-by: Stefan Hajnoczi <stefanha@redhat.com> Signed-off-by: Fam Zheng <famz@redhat.com>
2016-11-29hbitmap: Fix shifts of constants by granularityMax Reitz1-2/+6
An hbitmap's granularity may be anything from 0 to 63, so when shifting constants by its value, they should not be plain ints. Even having changed the types, hbitmap_serialization_granularity() still tries to shift 64 to the right by the granularity. This operation is undefined if the granularity is greater than 57. Adding an assertion is fine for now, because serializing is done only in tests so far, but this means that only bitmaps with a granularity below 58 can be serialized and we should thus add a hbitmap_is_serializable() function later. One of the two places touched in this patch uses QEMU_ALIGN_UP(x, 1 << y). We can use ROUND_UP() there, since the second parameter is obviously a power of two. Signed-off-by: Max Reitz <mreitz@redhat.com> Message-Id: <20161115224732.1334-1-mreitz@redhat.com> Reviewed-by: Stefan Hajnoczi <stefanha@redhat.com> Signed-off-by: Fam Zheng <famz@redhat.com>
2016-10-24hbitmap: serializationVladimir Sementsov-Ogievskiy1-0/+137
Functions to serialize / deserialize(restore) HBitmap. HBitmap should be saved to linear sequence of bits independently of endianness and bitmap array element (unsigned long) size. Therefore Little Endian is chosen. These functions are appropriate for dirty bitmap migration, restoring the bitmap in several steps is available. To save performance, every step writes only the last level of the bitmap. All other levels are restored by hbitmap_deserialize_finish() as a last step of restoring. So, HBitmap is inconsistent while restoring. Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> [Fix left shift operand to 1UL; add "finish" parameter. - Fam] Signed-off-by: Fam Zheng <famz@redhat.com> Signed-off-by: John Snow <jsnow@redhat.com> Message-id: 1476395910-8697-8-git-send-email-jsnow@redhat.com Signed-off-by: Max Reitz <mreitz@redhat.com>
2016-10-24HBitmap: Introduce "meta" bitmap to track bit changesFam Zheng1-15/+54
Upon each bit toggle, the corresponding bit in the meta bitmap will be set. Signed-off-by: Fam Zheng <famz@redhat.com> [Amended text inline. --js] Reviewed-by: Max Reitz <mreitz@redhat.com> Signed-off-by: John Snow <jsnow@redhat.com> Message-id: 1476395910-8697-3-git-send-email-jsnow@redhat.com Signed-off-by: Max Reitz <mreitz@redhat.com>
2016-06-16hbitmap: add 'pos < size' assertsVladimir Sementsov-Ogievskiy1-0/+3
For now, fail in hbitmap_set on start + count > size will come from hbitmap_set hb_count_between hbitmap_iter_init assert(pos < hb->size) This patch adds such checks to set/get/reset functions of hbitmap. Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Message-id: 1465924093-76875-2-git-send-email-vsementsov@virtuozzo.com Signed-off-by: Max Reitz <mreitz@redhat.com>
2016-06-07all: Remove unnecessary glib.h includesPeter Maydell1-1/+0
Remove glib.h includes, as it is provided by osdep.h. This commit was created with scripts/clean-includes. Signed-off-by: Peter Maydell <peter.maydell@linaro.org> Reviewed-by: Eric Blake <eblake@redhat.com> Tested-by: Eric Blake <eblake@redhat.com> Signed-off-by: Michael Tokarev <mjt@tls.msk.ru>
2016-02-04util: Clean up includesPeter Maydell1-3/+1
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-06-23util/hbitmap: Add an API to reset all set bits in hbitmapWen Congyang1-0/+13
The function bdrv_clear_dirty_bitmap() is updated to use faster hbitmap_reset_all() call. Signed-off-by: Wen Congyang <wency@cn.fujitsu.com> Signed-off-by: zhanghailiang <zhang.zhanghailiang@huawei.com> Signed-off-by: Gonglei <arei.gonglei@huawei.com> Acked-by: Paolo Bonzini <pbonzini@redhat.com> Reviewed-by: Eric Blake <eblake@redhat.com> Reviewed-by: John Snow <jsnow@redhat.com> Message-id: 555E868A.60506@cn.fujitsu.com Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com>
2015-04-28block: Resize bitmaps on bdrv_truncateJohn Snow1-0/+48
Signed-off-by: John Snow <jsnow@redhat.com> Reviewed-by: Max Reitz <mreitz@redhat.com> Reviewed-by: Stefan Hajnoczi <stefanha@redhat.com> Message-id: 1429314609-29776-16-git-send-email-jsnow@redhat.com Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com> Signed-off-by: Kevin Wolf <kwolf@redhat.com>
2015-04-28hbitmap: add hbitmap_mergeJohn Snow1-0/+33
We add a bitmap merge operation to assist in error cases where we wish to combine two bitmaps together. This is algorithmically O(bits) provided HBITMAP_LEVELS remains constant. For a full bitmap on a 64bit machine: sum(bits/64^k, k, 0, HBITMAP_LEVELS) ~= 1.01587 * bits We may be able to improve running speed for particularly sparse bitmaps by using iterators, but the running time for dense maps will be worse. We present the simpler solution first, and we can refine it later if needed. Signed-off-by: John Snow <jsnow@redhat.com> Reviewed-by: Max Reitz <mreitz@redhat.com> Reviewed-by: Eric Blake <eblake@redhat.com> Reviewed-by: Stefan Hajnoczi <stefanha@redhat.com> Message-id: 1429314609-29776-8-git-send-email-jsnow@redhat.com Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com> Signed-off-by: Kevin Wolf <kwolf@redhat.com>
2015-04-28hbitmap: cache array lengthsJohn Snow1-0/+4
As a convenience: between incremental backups, bitmap migrations and bitmap persistence we seem to need to recalculate these a lot. Because the lengths are a little bit-twiddly, let's just solidly cache them and be done with it. Reviewed-by: Max Reitz <mreitz@redhat.com> Reviewed-by: Eric Blake <eblake@redhat.com> Signed-off-by: John Snow <jsnow@redhat.com> Reviewed-by: Stefan Hajnoczi <stefanha@redhat.com> Message-id: 1429314609-29776-7-git-send-email-jsnow@redhat.com Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com> Signed-off-by: Kevin Wolf <kwolf@redhat.com>
2014-12-10util: Use g_new() & friends where that makes obvious senseMarkus Armbruster1-2/+2
g_new(T, n) is neater than g_malloc(sizeof(T) * n). It's also safer, for two reasons. One, it catches multiplication overflowing size_t. Two, it returns T * rather than void *, which lets the compiler catch more type errors. This commit only touches allocations with size arguments of the form sizeof(T). Signed-off-by: Markus Armbruster <armbru@redhat.com> Reviewed-by: Eric Blake <eblake@redhat.com> Reviewed-by: Fam Zheng <famz@redhat.com> Signed-off-by: Michael Tokarev <mjt@tls.msk.ru>
2014-06-11util/hbitmap.c: Use ctpopl rather than reimplementing a local equivalentPeter Maydell1-7/+2
The function popcountl() in hbitmap.c is effectively a reimplementation of what host-utils.h provides as ctpopl(). Use ctpopl() directly; this fixes a failure to compile on NetBSD (whose strings.h erroneously exposes a system popcountl() which clashes with this one). Reported-by: Martin Husemann <martin@duskware.de> Reviewed-by: Paolo Bonzini <pbonzini@redhat.com> Signed-off-by: Peter Maydell <peter.maydell@linaro.org>
2013-02-16hbitmap: Use non-bitops ctzlRichard Henderson1-1/+2
Both uses of ctz have already eliminated zero, and thus the difference in edge conditions between the two routines is irrelevant. Signed-off-by: Richard Henderson <rth@twiddle.net> Acked-by: Paolo Bonzini <pbonzini@redhat.com> Reviewed-by: Eric Blake <eblake@redhat.com> Signed-off-by: Blue Swirl <blauwirbel@gmail.com>
2013-02-02bitops: unify bitops_ffsl with the one in host-utils.h, call it bitops_ctzlPaolo Bonzini1-1/+1
We had two copies of a ffs function for longs with subtly different semantics and, for the one in bitops.h, a confusing name: the result was off-by-one compared to the library function ffsl. Unify the functions into one, and solve the name problem by calling the 0-based functions "bitops_ctzl" and "bitops_ctol" respectively. This also fixes the build on platforms with ffsl, including Mac OS X and Windows. Signed-off-by: Paolo Bonzini <pbonzini@redhat.com> Reviewed-by: Eric Blake <eblake@redhat.com> Tested-by: Andreas Färber <afaerber@suse.de> Tested-by: Peter Maydell <peter.maydell@linaro.org> Signed-off-by: Blue Swirl <blauwirbel@gmail.com>
2013-01-25hbitmap: add assertion on hbitmap_iter_initPaolo Bonzini1-0/+1
hbitmap_iter_init causes an out-of-bounds access when the "first" argument is or greater than or equal to the size of the bitmap. Forbid this with an assertion, and remove the failing testcase. Reported-by: Kevin Wolf <kwolf@redhat.com> Signed-off-by: Paolo Bonzini <pbonzini@redhat.com> Reviewed-by: Eric Blake <eblake@redhat.com> Reviewed-by: Laszlo Ersek <lersek@redhat.com> Signed-off-by: Kevin Wolf <kwolf@redhat.com>
2013-01-25add hierarchical bitmap data type and test casesPaolo Bonzini1-0/+400
HBitmaps provides an array of bits. The bits are stored as usual in an array of unsigned longs, but HBitmap is also optimized to provide fast iteration over set bits; going from one bit to the next is O(logB n) worst case, with B = sizeof(long) * CHAR_BIT: the result is low enough that the number of levels is in fact fixed. In order to do this, it stacks multiple bitmaps with progressively coarser granularity; in all levels except the last, bit N is set iff the N-th unsigned long is nonzero in the immediately next level. When iteration completes on the last level it can examine the 2nd-last level to quickly skip entire words, and even do so recursively to skip blocks of 64 words or powers thereof (32 on 32-bit machines). Given an index in the bitmap, it can be split in group of bits like this (for the 64-bit case): bits 0-57 => word in the last bitmap | bits 58-63 => bit in the word bits 0-51 => word in the 2nd-last bitmap | bits 52-57 => bit in the word bits 0-45 => word in the 3rd-last bitmap | bits 46-51 => bit in the word So it is easy to move up simply by shifting the index right by log2(BITS_PER_LONG) bits. To move down, you shift the index left similarly, and add the word index within the group. Iteration uses ffs (find first set bit) to find the next word to examine; this operation can be done in constant time in most current architectures. Setting or clearing a range of m bits on all levels, the work to perform is O(m + m/W + m/W^2 + ...), which is O(m) like on a regular bitmap. When iterating on a bitmap, each bit (on any level) is only visited once. Hence, The total cost of visiting a bitmap with m bits in it is the number of bits that are set in all bitmaps. Unless the bitmap is extremely sparse, this is also O(m + m/W + m/W^2 + ...), so the amortized cost of advancing from one bit to the next is usually constant. Reviewed-by: Laszlo Ersek <lersek@redhat.com> Reviewed-by: Eric Blake <eblake@redhat.com> Signed-off-by: Paolo Bonzini <pbonzini@redhat.com> Signed-off-by: Kevin Wolf <kwolf@redhat.com>
generated by cgit v1.1 at 2024-08-21 09:06:55 +0000