From patchwork Sat Jan 30 10:56:29 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Sementsov-Ogievskiy X-Patchwork-Id: 8170621 Return-Path: X-Original-To: patchwork-qemu-devel@patchwork.kernel.org Delivered-To: patchwork-parsemail@patchwork2.web.kernel.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.136]) by patchwork2.web.kernel.org (Postfix) with ESMTP id 607AEBEEE5 for ; Sat, 30 Jan 2016 10:57:17 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id 8951920398 for ; Sat, 30 Jan 2016 10:57:16 +0000 (UTC) Received: from lists.gnu.org (lists.gnu.org [208.118.235.17]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id BFC8920395 for ; Sat, 30 Jan 2016 10:57:15 +0000 (UTC) Received: from localhost ([::1]:38240 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1aPTDO-00021B-2W for patchwork-qemu-devel@patchwork.kernel.org; Sat, 30 Jan 2016 05:57:14 -0500 Received: from eggs.gnu.org ([2001:4830:134:3::10]:51586) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1aPTDC-00020W-MS for qemu-devel@nongnu.org; Sat, 30 Jan 2016 05:57:03 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1aPTDA-0002Wq-DQ for qemu-devel@nongnu.org; Sat, 30 Jan 2016 05:57:02 -0500 Received: from mailhub.sw.ru ([195.214.232.25]:36993 helo=relay.sw.ru) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1aPTDA-0002SV-1A for qemu-devel@nongnu.org; Sat, 30 Jan 2016 05:57:00 -0500 Received: from kvm.sw.ru. ([10.28.8.145]) by relay.sw.ru (8.13.4/8.13.4) with ESMTP id u0TKtNev009503; Fri, 29 Jan 2016 23:55:28 +0300 (MSK) From: Vladimir Sementsov-Ogievskiy To: qemu-devel@nongnu.org Date: Sat, 30 Jan 2016 13:56:29 +0300 Message-Id: <1454151394-52320-2-git-send-email-vsementsov@virtuozzo.com> X-Mailer: git-send-email 1.8.3.1 In-Reply-To: <1454151394-52320-1-git-send-email-vsementsov@virtuozzo.com> References: <1454151394-52320-1-git-send-email-vsementsov@virtuozzo.com> X-detected-operating-system: by eggs.gnu.org: OpenBSD 3.x X-Received-From: 195.214.232.25 Cc: kwolf@redhat.com, Vladimir Sementsov-Ogievskiy , famz@redhat.com, den@virtuozzo.com, armbru@redhat.com, jsnow@redhat.com Subject: [Qemu-devel] [PATCH 1/6] block dirty bitmap: add next_zero function X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+patchwork-qemu-devel=patchwork.kernel.org@nongnu.org Sender: qemu-devel-bounces+patchwork-qemu-devel=patchwork.kernel.org@nongnu.org X-Spam-Status: No, score=-6.9 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_HI, UNPARSEABLE_RELAY autolearn=unavailable version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on mail.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP The function searches for next zero bit (corresponding to next not-dirty bit). Signed-off-by: Vladimir Sementsov-Ogievskiy --- block/dirty-bitmap.c | 5 +++++ include/block/dirty-bitmap.h | 2 ++ include/qemu/hbitmap.h | 8 ++++++++ util/hbitmap.c | 26 ++++++++++++++++++++++++++ 4 files changed, 41 insertions(+) diff --git a/block/dirty-bitmap.c b/block/dirty-bitmap.c index 919ce10..6da27d9 100644 --- a/block/dirty-bitmap.c +++ b/block/dirty-bitmap.c @@ -490,3 +490,8 @@ int64_t bdrv_get_dirty_count(BdrvDirtyBitmap *bitmap) { return hbitmap_count(bitmap->bitmap); } + +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start) +{ + return hbitmap_next_zero(bitmap->bitmap, start); +} diff --git a/include/block/dirty-bitmap.h b/include/block/dirty-bitmap.h index 6ba5bec..0033942 100644 --- a/include/block/dirty-bitmap.h +++ b/include/block/dirty-bitmap.h @@ -68,4 +68,6 @@ void bdrv_dirty_bitmap_deserialize_zeroes(BdrvDirtyBitmap *bitmap, bool finish); void bdrv_dirty_bitmap_deserialize_finish(BdrvDirtyBitmap *bitmap); +int64_t bdrv_dirty_bitmap_next_zero(BdrvDirtyBitmap *bitmap, uint64_t start); + #endif diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h index 00dbb60..852e423 100644 --- a/include/qemu/hbitmap.h +++ b/include/qemu/hbitmap.h @@ -259,6 +259,14 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first); */ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi); +/* hbitmap_next_zero: + * @hb: The HBitmap to operate on + * @start: The bit to start from. + * + * Find next not dirty bit. + */ +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start); + /* hbitmap_create_meta: * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap. * The caller owns the created bitmap and must call hbitmap_free_meta(hb) to diff --git a/util/hbitmap.c b/util/hbitmap.c index 1e49ab7..bcddca9 100644 --- a/util/hbitmap.c +++ b/util/hbitmap.c @@ -169,6 +169,32 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first) } } +int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start) +{ + size_t pos = (start >> hb->granularity) >> BITS_PER_LEVEL; + unsigned long *last_lev = hb->levels[HBITMAP_LEVELS - 1]; + uint64_t sz = hb->sizes[HBITMAP_LEVELS - 1]; + unsigned long cur = last_lev[pos]; + unsigned start_bit_offset = + (start >> hb->granularity) & (BITS_PER_LONG - 1); + cur |= (1UL << start_bit_offset) - 1; + + if (cur == (unsigned long)-1) { + do { + pos++; + } while (pos < sz && last_lev[pos] == (unsigned long)-1); + + if (pos >= sz) { + return -1; + } + + cur = last_lev[pos]; + } + + return MIN((pos << BITS_PER_LEVEL) + ctol(cur), hb->size - 1) + << hb->granularity; +} + bool hbitmap_empty(const HBitmap *hb) { return hb->count == 0;