All of lore.kernel.org
 help / color / mirror / Atom feed
From: Olaf Hering <olaf@aepfle.de>
To: xen-devel@lists.xenproject.org
Cc: Olaf Hering <olaf@aepfle.de>, Ian Jackson <iwj@xenproject.org>,
	Wei Liu <wl@xen.org>, Juergen Gross <jgross@suse.com>
Subject: [PATCH v20210616 34/36] tools: add API for expandable bitmaps
Date: Wed, 16 Jun 2021 14:51:27 +0200	[thread overview]
Message-ID: <20210616125129.26563-35-olaf@aepfle.de> (raw)
In-Reply-To: <20210616125129.26563-1-olaf@aepfle.de>

Since the incoming migration stream lacks info about what the highest pfn
will be, data structures can not be allocated upfront.

Add an API for expandable bitmaps, loosely based on pfn_set_populated.

Signed-off-by: Olaf Hering <olaf@aepfle.de>

v02:
- remove xg_ prefix from functions
---
 tools/libs/saverestore/common.c | 40 ++++++++++++++++++++
 tools/libs/saverestore/common.h | 67 +++++++++++++++++++++++++++++++++
 2 files changed, 107 insertions(+)

diff --git a/tools/libs/saverestore/common.c b/tools/libs/saverestore/common.c
index 7da7fa4e2c..8b4e402df5 100644
--- a/tools/libs/saverestore/common.c
+++ b/tools/libs/saverestore/common.c
@@ -163,6 +163,46 @@ static void __attribute__((unused)) build_assertions(void)
     BUILD_BUG_ON(sizeof(struct xc_sr_rec_hvm_params)        != 8);
 }
 
+/*
+ * Expand the tracking structures as needed.
+ * To avoid realloc()ing too excessively, the size increased to the nearest
+ * power of two large enough to contain the required number of bits.
+ */
+bool _sr_bitmap_expand(struct sr_bitmap *bm, unsigned long bits)
+{
+    size_t new_max;
+    size_t old_sz, new_sz;
+    void *p;
+
+    if (bits <= bm->bits)
+        return true;
+
+    /* Round up to the nearest power of two larger than bit, less 1. */
+    new_max = bits;
+    new_max |= new_max >> 1;
+    new_max |= new_max >> 2;
+    new_max |= new_max >> 4;
+    new_max |= new_max >> 8;
+    new_max |= new_max >> 16;
+    if ( sizeof(unsigned long) > 4 )
+        new_max |= new_max >> 32;
+
+    /* Allocate units of unsigned long */
+    new_max = (new_max + BITS_PER_LONG - 1) & ~(BITS_PER_LONG - 1);
+
+    old_sz = bitmap_size(bm->bits);
+    new_sz = bitmap_size(new_max);
+    p = realloc(bm->p, new_sz);
+    if (!p)
+        return false;
+
+    memset(p + old_sz, 0, new_sz - old_sz);
+    bm->p = p;
+    bm->bits = new_max;
+
+    return true;
+}
+
 /*
  * Local variables:
  * mode: C
diff --git a/tools/libs/saverestore/common.h b/tools/libs/saverestore/common.h
index 60bbba6aa9..43aa1a7b86 100644
--- a/tools/libs/saverestore/common.h
+++ b/tools/libs/saverestore/common.h
@@ -30,6 +30,73 @@ const char *rec_type_to_str(uint32_t type);
 struct xc_sr_context;
 struct xc_sr_record;
 
+struct sr_bitmap
+{
+    void *p;
+    unsigned long bits;
+};
+
+extern bool _sr_bitmap_expand(struct sr_bitmap *bm, unsigned long bits);
+
+static inline bool sr_bitmap_expand(struct sr_bitmap *bm, unsigned long bits)
+{
+    if (bits > bm->bits)
+        return _sr_bitmap_expand(bm, bits);
+    return true;
+}
+
+static inline void sr_bitmap_free(struct sr_bitmap *bm)
+{
+    free(bm->p);
+    bm->p = NULL;
+}
+
+static inline bool sr_set_bit(unsigned long bit, struct sr_bitmap *bm)
+{
+    if (sr_bitmap_expand(bm, bit) == false)
+        return false;
+
+    set_bit(bit, bm->p);
+    return true;
+}
+
+static inline bool sr_test_bit(unsigned long bit, struct sr_bitmap *bm)
+{
+    if (bit > bm->bits)
+        return false;
+    return !!test_bit(bit, bm->p);
+}
+
+static inline void sr_clear_bit(unsigned long bit, struct sr_bitmap *bm)
+{
+    if (bit <= bm->bits)
+        clear_bit(bit, bm->p);
+}
+
+static inline bool sr_test_and_clear_bit(unsigned long bit, struct sr_bitmap *bm)
+{
+    if (bit > bm->bits)
+        return false;
+    return !!test_and_clear_bit(bit, bm->p);
+}
+
+/* No way to report potential allocation error, bitmap must be expanded prior usage */
+static inline bool sr_test_and_set_bit(unsigned long bit, struct sr_bitmap *bm)
+{
+    if (bit > bm->bits)
+        return false;
+    return !!test_and_set_bit(bit, bm->p);
+}
+
+static inline bool sr_set_long_bit(unsigned long base_bit, struct sr_bitmap *bm)
+{
+    if (sr_bitmap_expand(bm, base_bit + BITS_PER_LONG) == false)
+        return false;
+
+    set_bit_long(base_bit, bm->p);
+    return true;
+}
+
 /**
  * Save operations.  To be implemented for each type of guest, for use by the
  * common save algorithm.


  parent reply	other threads:[~2021-06-16 13:08 UTC|newest]

Thread overview: 46+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-06-16 12:50 [PATCH v20210616 00/36] leftover from 2020 Olaf Hering
2021-06-16 12:50 ` [PATCH v20210616 01/36] hotplug/Linux: fix starting of xenstored with restarting systemd Olaf Hering
2021-06-16 12:50 ` [PATCH v20210616 02/36] tools: add API to work with sevaral bits at once Olaf Hering
2021-06-16 12:50 ` [PATCH v20210616 03/36] xl: fix description of migrate --debug Olaf Hering
2021-06-16 12:50 ` [PATCH v20210616 04/36] tools: create libxensaverestore Olaf Hering
2021-06-16 15:17   ` Olaf Hering
2021-06-16 12:50 ` [PATCH v20210616 05/36] MAINTAINERS: add myself as saverestore maintainer Olaf Hering
2021-06-16 12:50 ` [PATCH v20210616 06/36] tools: add readv_exact to libxenctrl Olaf Hering
2021-06-16 12:51 ` [PATCH v20210616 07/36] tools: add sr_is_known_page_type to libsaverestore Olaf Hering
2021-06-16 12:51 ` [PATCH v20210616 08/36] tools: use sr_is_known_page_type Olaf Hering
2021-06-16 12:51 ` [PATCH v20210616 09/36] tools: unify type checking for data pfns in migration stream Olaf Hering
2021-06-16 12:51 ` [PATCH v20210616 10/36] tools: show migration transfer rate in send_dirty_pages Olaf Hering
2021-06-16 12:51 ` [PATCH v20210616 11/36] tools: prepare to allocate saverestore arrays once Olaf Hering
2021-06-16 12:51 ` [PATCH v20210616 12/36] tools: save: move mfns array Olaf Hering
2021-06-16 12:51 ` [PATCH v20210616 13/36] tools: save: move types array Olaf Hering
2021-06-16 12:51 ` [PATCH v20210616 14/36] tools: save: move errors array Olaf Hering
2021-06-16 12:51 ` [PATCH v20210616 15/36] tools: save: move iov array Olaf Hering
2021-06-16 12:51 ` [PATCH v20210616 16/36] tools: save: move rec_pfns array Olaf Hering
2021-06-16 12:51 ` [PATCH v20210616 17/36] tools: save: move guest_data array Olaf Hering
2021-06-16 12:51 ` [PATCH v20210616 18/36] tools: save: move local_pages array Olaf Hering
2021-06-16 12:51 ` [PATCH v20210616 19/36] tools: restore: move types array Olaf Hering
2021-06-16 12:51 ` [PATCH v20210616 20/36] tools: restore: move mfns array Olaf Hering
2021-06-16 12:51 ` [PATCH v20210616 21/36] tools: restore: move map_errs array Olaf Hering
2021-06-16 12:51 ` [PATCH v20210616 22/36] tools: restore: move mfns array in populate_pfns Olaf Hering
2021-06-16 12:51 ` [PATCH v20210616 23/36] tools: restore: move pfns " Olaf Hering
2021-06-16 12:51 ` [PATCH v20210616 24/36] tools: restore: split record processing Olaf Hering
2021-06-16 12:51 ` [PATCH v20210616 25/36] tools: restore: split handle_page_data Olaf Hering
2021-06-16 12:51 ` [PATCH v20210616 26/36] tools: restore: write data directly into guest Olaf Hering
2021-06-16 12:51 ` [PATCH v20210616 27/36] tools: recognize LIBXL_API_VERSION for 4.16 Olaf Hering
2021-06-16 12:51 ` [PATCH v20210616 28/36] tools: adjust libxl_domain_suspend to receive a struct props Olaf Hering
2021-06-16 12:51 ` [PATCH v20210616 29/36] tools: change struct precopy_stats to precopy_stats_t Olaf Hering
2021-06-16 12:51 ` [PATCH v20210616 30/36] tools: add callback to libxl for precopy_policy and precopy_stats_t Olaf Hering
2021-06-16 12:51 ` [PATCH v20210616 31/36] tools: add --max_iters to libxl_domain_suspend Olaf Hering
2021-06-16 12:51 ` [PATCH v20210616 32/36] tools: add --min_remaining " Olaf Hering
2021-06-16 12:51 ` [PATCH v20210616 33/36] tools: add --abort_if_busy " Olaf Hering
2021-06-16 12:51 ` Olaf Hering [this message]
2021-06-16 12:51 ` [PATCH v20210616 35/36] tools: use sr_bitmap for populated_pfns Olaf Hering
2021-06-16 12:51 ` [PATCH v20210616 36/36] tools: use superpages during restore of HVM guest Olaf Hering
2021-06-16 14:50 ` [PATCH v20210616 00/36] leftover from 2020 Andrew Cooper
2021-06-16 15:02   ` Olaf Hering
2021-06-17 11:02     ` Julien Grall
2021-06-17 17:40       ` Olaf Hering
2021-06-16 15:38   ` Olaf Hering
2021-06-17 11:24     ` Andrew Cooper
2021-06-17 14:55       ` Olaf Hering
2021-06-17 15:05         ` Andrew Cooper

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20210616125129.26563-35-olaf@aepfle.de \
    --to=olaf@aepfle.de \
    --cc=iwj@xenproject.org \
    --cc=jgross@suse.com \
    --cc=wl@xen.org \
    --cc=xen-devel@lists.xenproject.org \
    --subject='Re: [PATCH v20210616 34/36] tools: add API for expandable bitmaps' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.