aboutsummaryrefslogtreecommitdiff
path: root/tests/test-hbitmap.c
AgeCommit message (Collapse)Author
2019-10-17util/hbitmap: strict hbitmap_resetVladimir Sementsov-Ogievskiy
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-16tests/test-hbitmap: test next_zero and _next_dirty_area after truncateVladimir Sementsov-Ogievskiy
Test that hbitmap_next_zero and hbitmap_next_dirty_area can find things after old bitmap end. Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Message-id: 20190805164652.42409-1-vsementsov@virtuozzo.com Tested-by: John Snow <jsnow@redhat.com> Reviewed-by: John Snow <jsnow@redhat.com> Signed-off-by: John Snow <jsnow@redhat.com>
2019-01-15Revert "hbitmap: Add @advance param to hbitmap_iter_next()"Vladimir Sementsov-Ogievskiy
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-15Revert "test-hbitmap: Add non-advancing iter_next tests"Vladimir Sementsov-Ogievskiy
This reverts commit 269576848ec3d57d2d958cf5ac69b08c44adf816. The functionality is unused. Drop tests. Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Reviewed-by: John Snow <jsnow@redhat.com>
2019-01-15tests: add tests for hbitmap_next_dirty_areaVladimir Sementsov-Ogievskiy
Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
2019-01-15tests: add tests for hbitmap_next_zero with specified end parameterVladimir Sementsov-Ogievskiy
Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
2019-01-15dirty-bitmap: improve bdrv_dirty_bitmap_next_zeroVladimir Sementsov-Ogievskiy
Add bytes parameter to the function, to limit searched range. Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
2018-06-18test-hbitmap: Add non-advancing iter_next testsMax Reitz
Add a function that wraps hbitmap_iter_next() and always calls it in non-advancing mode first, and in advancing mode next. The result should always be the same. By using this function everywhere we called hbitmap_iter_next() before, we should get good test coverage for non-advancing hbitmap_iter_next(). 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-9-mreitz@redhat.com Signed-off-by: Max Reitz <mreitz@redhat.com>
2018-06-18hbitmap: Add @advance param to hbitmap_iter_next()Max Reitz
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-10tests/hbitmap: use ARRAY_SIZE macroPhilippe Mathieu-Daudé
Applied using the Coccinelle semantic patch scripts/coccinelle/use_osdep.cocci Signed-off-by: Philippe Mathieu-Daudé <f4bug@amsat.org> Signed-off-by: Michael Tokarev <mjt@tls.msk.ru> Reviewed-by: Marc-André Lureau <marcandre.lureau@redhat.com> Reviewed-by: John Snow <jsnow@redhat.com>
2017-12-18hbitmap: add next_zero functionVladimir Sementsov-Ogievskiy
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 Blake
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-11tests: add hbitmap iter testVladimir Sementsov-Ogievskiy
Test that hbitmap iter is resistant to bitmap resetting. Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com> Signed-off-by: Denis V. Lunev <den@openvz.org> Reviewed-by: Max Reitz <mreitz@redhat.com> Reviewed-by: John Snow <jsnow@redhat.com> Message-id: 20170628120530.31251-5-vsementsov@virtuozzo.com Signed-off-by: Max Reitz <mreitz@redhat.com>
2017-01-26test-hbitmap: Add hbitmap_is_serializable() callsMax Reitz
Add calls to hbitmap_is_serializable() (asserting that it returns true) where necessary (i.e. before every series of (de-)serialization function invocations). Signed-off-by: Max Reitz <mreitz@redhat.com> Message-Id: <20161115225746.3590-3-mreitz@redhat.com> Reviewed-by: Stefan Hajnoczi <stefanha@redhat.com> Signed-off-by: Fam Zheng <famz@redhat.com>
2016-10-24tests: Add test code for hbitmap serializationFam Zheng
Signed-off-by: Fam Zheng <famz@redhat.com> [Fixed minor constant issue. --js] Signed-off-by: John Snow <jsnow@redhat.com> Signed-off-by: John Snow <jsnow@redhat.com> Message-id: 1476395910-8697-10-git-send-email-jsnow@redhat.com Reviewed-by: Max Reitz <mreitz@redhat.com> Signed-off-by: Max Reitz <mreitz@redhat.com>
2016-10-24tests: Add test code for meta bitmapFam Zheng
Signed-off-by: Fam Zheng <famz@redhat.com> Reviewed-by: John Snow <jsnow@redhat.com> Reviewed-by: Max Reitz <mreitz@redhat.com> Signed-off-by: John Snow <jsnow@redhat.com> Message-id: 1476395910-8697-4-git-send-email-jsnow@redhat.com Signed-off-by: Max Reitz <mreitz@redhat.com>
2016-06-07hbitmap: Use DIV_ROUND_UPLaurent Vivier
Replace (((n) + (d) - 1) /(d)) by DIV_ROUND_UP(n,d). This patch is the result of coccinelle script scripts/coccinelle/round.cocci CC: Paolo Bonzini <pbonzini@redhat.com> Signed-off-by: Laurent Vivier <lvivier@redhat.com> Reviewed-by: John Snow <jsnow@redhat.com> Signed-off-by: Michael Tokarev <mjt@tls.msk.ru>
2016-06-07tests: Remove unnecessary glib.h includesPeter Maydell
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-16tests: 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> Reviewed-by: Eric Blake <eblake@redhat.com> Tested-by: Eric Blake <eblake@redhat.com>
2015-09-11maint: avoid useless "if (foo) free(foo)" patternMarkus Armbruster
My Coccinelle semantic patch finds a few more, because it also fixes up the equally pointless conditional if (foo) { free(foo); foo = NULL; } Result (feel free to squash it into your patch): Signed-off-by: Markus Armbruster <armbru@redhat.com> Reviewed-by: Eric Blake <eblake@redhat.com> Signed-off-by: Michael Tokarev <mjt@tls.msk.ru>
2015-06-23util/hbitmap: Add an API to reset all set bits in hbitmapWen Congyang
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-28hbitmap: truncate testsJohn Snow
The general approach is to set bits close to the boundaries of where we are truncating and ensure that everything appears to have gone OK. We test growing and shrinking by different amounts: - Less than the granularity - Less than the granularity, but across a boundary - Less than sizeof(unsigned long) - Less than sizeof(unsigned long), but across a ulong boundary - More than sizeof(unsigned long) 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-17-git-send-email-jsnow@redhat.com Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com> Signed-off-by: Kevin Wolf <kwolf@redhat.com>
2013-01-25hbitmap: add assertion on hbitmap_iter_initPaolo Bonzini
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 Bonzini
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.2.3 (git 2.26.2) at 2024-12-04 23:42:01 +0000