| Message ID | 1355319999-30627-15-git-send-email-pbonzini@redhat.com |
|---|---|
| State | New |
| Headers | show |
On 12/12/2012 06:46 AM, Paolo Bonzini wrote: > Signed-off-by: Paolo Bonzini <pbonzini@redhat.com> > --- > hbitmap.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++---------- > hbitmap.h | 25 +++++++++++++++++++++++++ > 2 files changed, 72 insertions(+), 10 deletions(-) When using hbitmap_alloc_with_data, must the user pass in all 0 data, or do you do a one-time slow pass over the passed-in data to populate the remaining layers of the hbitmap to allow faster traversal later? > +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; > } Based on the implementation, you aren't inspecting the contents of data. > +/** > + * 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); But this documentation didn't mention that the caller must pass in all 0s.
Il 17/12/2012 18:14, Eric Blake ha scritto: > On 12/12/2012 06:46 AM, Paolo Bonzini wrote: >> Signed-off-by: Paolo Bonzini <pbonzini@redhat.com> >> --- >> hbitmap.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++---------- >> hbitmap.h | 25 +++++++++++++++++++++++++ >> 2 files changed, 72 insertions(+), 10 deletions(-) > > When using hbitmap_alloc_with_data, must the user pass in all 0 data, or > do you do a one-time slow pass over the passed-in data to populate the > remaining layers of the hbitmap to allow faster traversal later? Right, I should add such a pass. Paolo >> +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; >> } > > Based on the implementation, you aren't inspecting the contents of data. > >> +/** >> + * 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); > > But this documentation didn't mention that the caller must pass in all 0s. >
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. *
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com> --- hbitmap.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++---------- hbitmap.h | 25 +++++++++++++++++++++++++ 2 files changed, 72 insertions(+), 10 deletions(-)