From patchwork Wed Dec 12 13:46:33 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paolo Bonzini X-Patchwork-Id: 205522 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from lists.gnu.org (lists.gnu.org [208.118.235.17]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id 9A8432C008D for ; Thu, 13 Dec 2012 00:52:11 +1100 (EST) Received: from localhost ([::1]:50541 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TimfV-0000vi-CT for incoming@patchwork.ozlabs.org; Wed, 12 Dec 2012 08:48:13 -0500 Received: from eggs.gnu.org ([208.118.235.92]:59120) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TimfD-0000M9-CZ for qemu-devel@nongnu.org; Wed, 12 Dec 2012 08:48:01 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Timf3-0003r2-Ku for qemu-devel@nongnu.org; Wed, 12 Dec 2012 08:47:55 -0500 Received: from mail-ia0-f180.google.com ([209.85.210.180]:49898) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Timf3-0003q7-F9 for qemu-devel@nongnu.org; Wed, 12 Dec 2012 08:47:45 -0500 Received: by mail-ia0-f180.google.com with SMTP id t4so925335iag.39 for ; Wed, 12 Dec 2012 05:47:45 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=sender:from:to:cc:subject:date:message-id:x-mailer:in-reply-to :references; bh=jwXIQxeAO2Jr8RfyhqE8RiN37aG/O3+VJMWYM2yn8gk=; b=XBoUZ8PO91iaRp1+z5BdzCT9wZTftqH9I6AOoW6jOZv1Z5v9Tu8MBZNEUkmVwVehLo ZZgvAZwmSiMANQO+kLgchcYpZsbqdDei6H2hpfIsEf7htdsSey0MuyqLnpzOk7p6voFf E3smcOrXYCcofzT4TRNMH+paKzS9XJGAu+oJ0uCmCNDiN08ckhRjX9XkYle5SOXOoM3v miznqnHT4u2sJcZrHVsV1tacGGWsL7S9O5agVlyG47mxbjuHvUOGg5q8G05oKF5CndQ0 bSzogpZN8gQyuJ7JQ5Aedp3q+6FWmI7F9S3zRcDc5IR/JoMORwwV+MXD0yDDHNbWNNV5 n2Vw== Received: by 10.50.213.73 with SMTP id nq9mr13587859igc.27.1355320064948; Wed, 12 Dec 2012 05:47:44 -0800 (PST) Received: from yakj.usersys.redhat.com (93-34-219-150.ip51.fastwebnet.it. [93.34.219.150]) by mx.google.com with ESMTPS id fv6sm1786818igc.17.2012.12.12.05.47.41 (version=TLSv1/SSLv3 cipher=OTHER); Wed, 12 Dec 2012 05:47:43 -0800 (PST) From: Paolo Bonzini To: qemu-devel@nongnu.org Date: Wed, 12 Dec 2012 14:46:33 +0100 Message-Id: <1355319999-30627-15-git-send-email-pbonzini@redhat.com> X-Mailer: git-send-email 1.8.0.1 In-Reply-To: <1355319999-30627-1-git-send-email-pbonzini@redhat.com> References: <1355319999-30627-1-git-send-email-pbonzini@redhat.com> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x [fuzzy] X-Received-From: 209.85.210.180 Cc: kwolf@redhat.com, jcody@redhat.com, stefanha@redhat.com Subject: [Qemu-devel] [PATCH 14/20] hbitmap: add hbitmap_alloc_with_data and hbitmap_required_size 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+incoming=patchwork.ozlabs.org@nongnu.org Sender: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Signed-off-by: Paolo Bonzini --- hbitmap.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++---------- hbitmap.h | 25 +++++++++++++++++++++++++ 2 files changed, 72 insertions(+), 10 deletions(-) diff --git a/hbitmap.c b/hbitmap.c index ae59f39..aa4586f 100644 --- a/hbitmap.c +++ b/hbitmap.c @@ -81,6 +81,9 @@ struct HBitmap { */ int granularity; + /* True if the last level should be freed by hbitmap_free. */ + bool last_level_allocated; + /* A number of progressively less coarse bitmaps (i.e. level 0 is the * coarsest). Each bit in level N represents a word in level N+1 that * has a set bit, except the last level where each bit represents the @@ -367,34 +370,68 @@ bool hbitmap_get(const HBitmap *hb, uint64_t item) void hbitmap_free(HBitmap *hb) { - unsigned i; - for (i = HBITMAP_LEVELS; i-- > 0; ) { + unsigned i = HBITMAP_LEVELS; + + if (!hb->last_level_allocated) { + i--; + } + + while (i-- > 0) { g_free(hb->levels[i]); } g_free(hb); } -HBitmap *hbitmap_alloc(uint64_t size, int granularity) +static uint64_t hbitmap_round_size(uint64_t size, int granularity) { - HBitmap *hb = g_malloc0(sizeof(struct HBitmap)); - unsigned i; - assert(granularity >= 0 && granularity < 64); + + if (!size) { + size = 1; + } + size = (size + (1ULL << granularity) - 1) >> granularity; assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE)); + return size; +} - hb->size = size; +size_t hbitmap_required_size(uint64_t size, int granularity) +{ + size_t longs; + + size = hbitmap_round_size(size, granularity); + longs = (size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL; + return longs * sizeof(unsigned long); +} + +HBitmap *hbitmap_alloc_with_data(uint64_t size, int granularity, void *data) +{ + HBitmap *hb = g_malloc0(sizeof(struct HBitmap)); + unsigned i; + + hb->size = hbitmap_round_size(size, granularity); hb->granularity = granularity; + hb->last_level_allocated = (data == NULL); + for (i = HBITMAP_LEVELS; i-- > 0; ) { - size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1); - hb->levels[i] = g_malloc0(size * sizeof(unsigned long)); + if (data == NULL) { + data = g_malloc0(hbitmap_required_size(size, granularity)); + } + hb->levels[i] = data; + data = NULL; + granularity += BITS_PER_LEVEL; } /* We necessarily have free bits in level 0 due to the definition * of HBITMAP_LEVELS, so use one for a sentinel. This speeds up * hbitmap_iter_skip_words. */ - assert(size == 1); + assert(hbitmap_required_size(size, granularity) == sizeof(unsigned long)); hb->levels[0][0] |= 1UL << (BITS_PER_LONG - 1); return hb; } + +HBitmap *hbitmap_alloc(uint64_t size, int granularity) +{ + return hbitmap_alloc_with_data(size, granularity, NULL); +} diff --git a/hbitmap.h b/hbitmap.h index 7ddfb66..35ee51a 100644 --- a/hbitmap.h +++ b/hbitmap.h @@ -64,6 +64,31 @@ struct HBitmapIter { HBitmap *hbitmap_alloc(uint64_t size, int granularity); /** + * hbitmap_required_size: + * @size: Number of bits in the bitmap. + * @granularity: Granularity of the bitmap. + * + * Return the number of bytes that are needed for a bitmap with the + * given size and granularity. + * + * A block of this size can then be passed to @hbitmap_alloc_with_data. + */ +size_t hbitmap_required_size(uint64_t size, int granularity); + +/** + * hbitmap_alloc_with_data: + * @size: Number of bits in the bitmap. + * @granularity: Granularity of the bitmap. + * @data: Pointer to a data block that will be used for the bottom level + * of the HBitmap. + * + * Allocate a new HBitmap, using a client-provided data block for the + * actual bitmap and allocating memory only for the compressed levels. + * If @data is NULL, this function is equivalent to @hbitmap_alloc. + */ +HBitmap *hbitmap_alloc_with_data(uint64_t size, int granularity, void *data); + +/** * hbitmap_empty: * @hb: HBitmap to operate on. *