path: root/util/hbitmap.c
Commit message (Collapse)AuthorAgeFilesLines
* util/hbitmap: Add an API to reset all set bits in hbitmapWen Congyang2015-06-231-0/+13
| | | | | | | | | | | | | | The function bdrv_clear_dirty_bitmap() is updated to use faster hbitmap_reset_all() call. Signed-off-by: Wen Congyang <> Signed-off-by: zhanghailiang <> Signed-off-by: Gonglei <> Acked-by: Paolo Bonzini <> Reviewed-by: Eric Blake <> Reviewed-by: John Snow <> Message-id: Signed-off-by: Stefan Hajnoczi <>
* block: Resize bitmaps on bdrv_truncateJohn Snow2015-04-281-0/+48
| | | | | | | | | Signed-off-by: John Snow <> Reviewed-by: Max Reitz <> Reviewed-by: Stefan Hajnoczi <> Message-id: Signed-off-by: Stefan Hajnoczi <> Signed-off-by: Kevin Wolf <>
* hbitmap: add hbitmap_mergeJohn Snow2015-04-281-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 <> Reviewed-by: Max Reitz <> Reviewed-by: Eric Blake <> Reviewed-by: Stefan Hajnoczi <> Message-id: Signed-off-by: Stefan Hajnoczi <> Signed-off-by: Kevin Wolf <>
* hbitmap: cache array lengthsJohn Snow2015-04-281-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 <> Reviewed-by: Eric Blake <> Signed-off-by: John Snow <> Reviewed-by: Stefan Hajnoczi <> Message-id: Signed-off-by: Stefan Hajnoczi <> Signed-off-by: Kevin Wolf <>
* util: Use g_new() & friends where that makes obvious senseMarkus Armbruster2014-12-101-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 <> Reviewed-by: Eric Blake <> Reviewed-by: Fam Zheng <> Signed-off-by: Michael Tokarev <>
* util/hbitmap.c: Use ctpopl rather than reimplementing a local equivalentPeter Maydell2014-06-111-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 <> Reviewed-by: Paolo Bonzini <> Signed-off-by: Peter Maydell <>
* hbitmap: Use non-bitops ctzlRichard Henderson2013-02-161-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 <> Acked-by: Paolo Bonzini <> Reviewed-by: Eric Blake <> Signed-off-by: Blue Swirl <>
* bitops: unify bitops_ffsl with the one in host-utils.h, call it bitops_ctzlPaolo Bonzini2013-02-021-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 <> Reviewed-by: Eric Blake <> Tested-by: Andreas Färber <> Tested-by: Peter Maydell <> Signed-off-by: Blue Swirl <>
* hbitmap: add assertion on hbitmap_iter_initPaolo Bonzini2013-01-251-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 <> Signed-off-by: Paolo Bonzini <> Reviewed-by: Eric Blake <> Reviewed-by: Laszlo Ersek <> Signed-off-by: Kevin Wolf <>
* add hierarchical bitmap data type and test casesPaolo Bonzini2013-01-251-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 <> Reviewed-by: Eric Blake <> Signed-off-by: Paolo Bonzini <> Signed-off-by: Kevin Wolf <>
OpenPOWER on IntegriCloud