From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:45422) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YLIMs-0008Oa-TD for qemu-devel@nongnu.org; Tue, 10 Feb 2015 16:29:16 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1YLIMp-0004Ws-N2 for qemu-devel@nongnu.org; Tue, 10 Feb 2015 16:29:14 -0500 Received: from mx1.redhat.com ([209.132.183.28]:34549) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YLIMp-0004WW-GB for qemu-devel@nongnu.org; Tue, 10 Feb 2015 16:29:11 -0500 Message-ID: <54DA7825.8080702@redhat.com> Date: Tue, 10 Feb 2015 16:29:09 -0500 From: John Snow MIME-Version: 1.0 References: <1422356197-5285-1-git-send-email-vsementsov@parallels.com> <1422356197-5285-3-git-send-email-vsementsov@parallels.com> In-Reply-To: <1422356197-5285-3-git-send-email-vsementsov@parallels.com> Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 7bit Subject: Re: [Qemu-devel] [PATCH RFC v2 2/8] hbitmap: serialization List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Vladimir Sementsov-Ogievskiy , qemu-devel@nongnu.org Cc: kwolf@redhat.com, pbonzini@redhat.com, stefanha@redhat.com, den@openvz.org On 01/27/2015 05:56 AM, Vladimir Sementsov-Ogievskiy wrote: > Functions to serialize / deserialize(restore) HBitmap. HBitmap should be > saved to linear sequence of bits independently of endianness and bitmap > array element (unsigned long) size. Therefore Little Endian is chosen. > > These functions are appropriate for dirty bitmap migration, restoring > the bitmap in several steps is available. To save performance, every > step writes only the last level of the bitmap. All other levels are > restored by hbitmap_deserialize_finish() as a last step of restoring. > So, HBitmap is inconsistent while restoring. > > Signed-off-by: Vladimir Sementsov-Ogievskiy > --- > include/qemu/hbitmap.h | 59 +++++++++++++++++++++++++++++++ > util/hbitmap.c | 96 ++++++++++++++++++++++++++++++++++++++++++++++++++ > 2 files changed, 155 insertions(+) > > diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h > index c48c50a..1d37582 100644 > --- a/include/qemu/hbitmap.h > +++ b/include/qemu/hbitmap.h > @@ -137,6 +137,65 @@ void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count); > bool hbitmap_get(const HBitmap *hb, uint64_t item); > > /** > + * hbitmap_data_size: > + * @hb: HBitmap to operate on. > + * @count: Number of bits > + * > + * Return amount of bytes hbitmap_serialize_part needs > + */ > +uint64_t hbitmap_data_size(const HBitmap *hb, uint64_t count); > + > +/** > + * hbitmap_serialize_part > + * @hb: HBitmap to oprate on. > + * @buf: Buffer to store serialized bitmap. > + * @start: First bit to store. > + * @count: Number of bits to store. > + * > + * Stores HBitmap data corresponding to given region. The format of saved data > + * is linear sequence of bits, so it can be used by hbitmap_deserialize_part > + * independently of endianess and size of HBitmap level array elements > + */ > +void hbitmap_serialize_part(const HBitmap *hb, uint8_t *buf, > + uint64_t start, uint64_t count); > + > +/** > + * hbitmap_deserialize_part > + * @hb: HBitmap to operate on. > + * @buf: Buffer to restore bitmap data from. > + * @start: First bit to restore. > + * @count: Number of bits to restore. > + * > + * Retores HBitmap data corresponding to given region. The format is the same > + * as for hbitmap_serialize_part. > + * > + * ! The bitmap becomes inconsistent after this operation. > + * hbitmap_serialize_finish should be called before using the bitmap after > + * data restoring. > + */ > +void hbitmap_deserialize_part(HBitmap *hb, uint8_t *buf, > + uint64_t start, uint64_t count); > + > +/** > + * hbitmap_deserialize_part0 > + * @hb: HBitmap to operate on. > + * @start: First bit to restore. > + * @count: Number of bits to restore. > + * > + * Same as hbitmap_serialize_part, but fills the bitmap with zeroes. > + */ > +void hbitmap_deserialize_part0(HBitmap *hb, uint64_t start, uint64_t count); > + Not important enough to warrant a respin on its own: maybe "hbitmap_deserialize_zeroes"? "part0" is a little odd. > +/** > + * hbitmap_deserialize_finish > + * @hb: HBitmap to operate on. > + * > + * Repair HBitmap after calling hbitmap_deserialize_data. Actually, all HBitmap > + * layers are restored here. > + */ > +void hbitmap_deserialize_finish(HBitmap *hb); > + > +/** > * hbitmap_free: > * @hb: HBitmap to operate on. > * > diff --git a/util/hbitmap.c b/util/hbitmap.c > index f400dcb..55226a0 100644 > --- a/util/hbitmap.c > +++ b/util/hbitmap.c > @@ -366,6 +366,102 @@ bool hbitmap_get(const HBitmap *hb, uint64_t item) > return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit) != 0; > } > > +uint64_t hbitmap_data_size(const HBitmap *hb, uint64_t count) > +{ > + uint64_t size, gran; > + > + if (count == 0) { > + return 0; > + } > + > + gran = 1ll << hb->granularity; > + size = (((gran + count - 2) >> hb->granularity) >> BITS_PER_LEVEL) + 1; > + > + return size * sizeof(unsigned long); > +} > + > +void hbitmap_serialize_part(const HBitmap *hb, uint8_t *buf, > + uint64_t start, uint64_t count) > +{ > + uint64_t i; > + uint64_t last = start + count - 1; > + unsigned long *out = (unsigned long *)buf; > + > + if (count == 0) { > + return; > + } > + > + start = (start >> hb->granularity) >> BITS_PER_LEVEL; > + last = (last >> hb->granularity) >> BITS_PER_LEVEL; > + count = last - start + 1; > + > + for (i = start; i <= last; ++i) { > + unsigned long el = hb->levels[HBITMAP_LEVELS - 1][i]; > + out[i] = (BITS_PER_LONG == 32 ? cpu_to_le32(el) : cpu_to_le64(el)); > + } > +} > + > +void hbitmap_deserialize_part(HBitmap *hb, uint8_t *buf, > + uint64_t start, uint64_t count) > +{ > + uint64_t i; > + uint64_t last = start + count - 1; > + unsigned long *in = (unsigned long *)buf; > + > + if (count == 0) { > + return; > + } > + > + start = (start >> hb->granularity) >> BITS_PER_LEVEL; > + last = (last >> hb->granularity) >> BITS_PER_LEVEL; > + count = last - start + 1; > + > + for (i = start; i <= last; ++i) { > + hb->levels[HBITMAP_LEVELS - 1][i] = > + (BITS_PER_LONG == 32 ? le32_to_cpu(in[i]) : le64_to_cpu(in[i])); > + } > +} > + > +void hbitmap_deserialize_part0(HBitmap *hb, uint64_t start, uint64_t count) > +{ > + uint64_t last = start + count - 1; > + > + if (count == 0) { > + return; > + } > + > + start = (start >> hb->granularity) >> BITS_PER_LEVEL; > + last = (last >> hb->granularity) >> BITS_PER_LEVEL; > + count = last - start + 1; > + > + memset(hb->levels[HBITMAP_LEVELS - 1] + start, 0, > + count * sizeof(unsigned long)); > +} > + > +void hbitmap_deserialize_finish(HBitmap *bitmap) > +{ > + int64_t i, size, prev_size; > + int lev; > + > + /* restore levels starting from penultimate to zero level, assuming > + * that the last level is ok */ > + size = MAX((bitmap->size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1); > + for (lev = HBITMAP_LEVELS - 1; lev-- > 0; ) { > + prev_size = size; > + size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1); > + memset(bitmap->levels[lev], 0, size * sizeof(unsigned long)); > + > + for (i = 0; i < prev_size; ++i) { > + if (bitmap->levels[lev + 1][i]) { > + bitmap->levels[lev][i >> BITS_PER_LEVEL] |= > + 1 << (i & (BITS_PER_LONG - 1)); > + } > + } > + } > + > + bitmap->levels[0][0] |= 1UL << (BITS_PER_LONG - 1); > +} > + > void hbitmap_free(HBitmap *hb) > { > unsigned i; > Reviewed-by: John Snow