>From 3abae8e66ebc0a664a02c29eb721c0ed2cdaaa54 Mon Sep 17 00:00:00 2001
From: Nils Goroll <[email protected]>
Date: Tue, 1 Mar 2016 18:17:10 +0100
Subject: [PATCH] improve the vbm facility and fix an off-by-one error
- change the allocation scheme to pow2()
- add VBITMAP_INITIALIZE() for on-stack use of struct vbitmap
- add a test program
- fix an off-by-one in vbit_set
---
include/Makefile.am | 11 +++++++
include/vbm.h | 63 ++++++++++++++++++++++++++++++++------
include/vbm_test.c | 87 +++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 151 insertions(+), 10 deletions(-)
create mode 100644 include/vbm_test.c
diff --git a/include/Makefile.am b/include/Makefile.am
index ced33c8..c42e54d 100644
--- a/include/Makefile.am
+++ b/include/Makefile.am
@@ -152,3 +152,14 @@ CLEANFILES = \
vcl.h \
vrt_obj.h \
vmod_abi.h
+
+if ENABLE_TESTS
+TESTS = vbm_test
+
+noinst_PROGRAMS = ${TESTS}
+
+vbm_test_SOURCES = vbm_test.c vbm.h
+
+test: ${TESTS}
+ @for test in ${TESTS} ; do ./$${test} ; done
+endif
diff --git a/include/vbm.h b/include/vbm.h
index 13d2d5f..e9890e6 100644
--- a/include/vbm.h
+++ b/include/vbm.h
@@ -29,17 +29,38 @@
* Self-sizeing bitmap operations
*/
+#include <stdlib.h>
+#include <string.h>
+#include <stdint.h>
+#include "vdef.h"
+
/**********************************************************************
- * Generic bitmap functions, may be generalized at some point.
+ * Generic bitmap functions
*/
#define VBITMAP_TYPE unsigned /* Our preferred wordsize */
#define VBITMAP_LUMP (1024) /* How many bits we alloc at a time */
#define VBITMAP_WORD (sizeof(VBITMAP_TYPE) * 8)
-#define VBITMAP_IDX(n) (n / VBITMAP_WORD)
-#define VBITMAP_BIT(n) (1U << (n % VBITMAP_WORD))
+#define VBITMAP_IDX(n) ((n) / VBITMAP_WORD)
+#define VBITMAP_BIT(n) (1U << ((n) % VBITMAP_WORD))
+
+static inline unsigned
+vbit_wordalign(unsigned bit, unsigned lump) {
+ assert(PWR2(VBITMAP_WORD));
+ assert(bit > 0);
+
+ lump = RUP2(lump, VBITMAP_WORD);
+ return RUP2(bit, lump);
+}
+
struct vbitmap {
+ unsigned flags;
+/* struct vbitmap is malloced */
+#define VBITMAP_FL_MALLOC 1
+/* bits space is malloced */
+#define VBITMAP_FL_MALLOC_BITS (1<<1)
+
VBITMAP_TYPE *bits;
unsigned nbits;
};
@@ -49,15 +70,31 @@ vbit_expand(struct vbitmap *vb, unsigned bit)
{
unsigned char *p;
- bit += VBITMAP_LUMP - 1;
- bit -= (bit % VBITMAP_LUMP);
- p = realloc(vb->bits, bit / 8);
- assert(p != NULL);
+ bit = vbit_wordalign(bit, VBITMAP_LUMP);
+ assert(bit > vb->nbits);
+
+ if (vb->flags & VBITMAP_FL_MALLOC_BITS) {
+ p = realloc(vb->bits, bit / 8);
+ assert(p != NULL);
+ } else {
+ p = malloc(bit / 8);
+ assert(p != NULL);
+ if (vb->nbits > 0)
+ memcpy(p, vb->bits, vb->nbits / 8);
+ }
memset(p + vb->nbits / 8, 0, (bit - vb->nbits) / 8);
+ vb->flags |= VBITMAP_FL_MALLOC_BITS;
vb->bits = (void*)p;
vb->nbits = bit;
}
+#define VBITMAP_INITIALIZE(vb, b) do { \
+ (vb).flags = 0; \
+ (vb).nbits = vbit_wordalign((b), VBITMAP_WORD); \
+ (vb).bits = alloca((vb).nbits / 8); \
+ memset((vb).bits, 0, (vb).nbits / 8); \
+ } while(0)
+
static inline struct vbitmap *
vbit_init(unsigned initial)
{
@@ -65,6 +102,7 @@ vbit_init(unsigned initial)
vb = calloc(sizeof *vb, 1);
assert(vb != NULL);
+ vb->flags |= VBITMAP_FL_MALLOC;
if (initial == 0)
initial = VBITMAP_LUMP;
vbit_expand(vb, initial);
@@ -77,8 +115,13 @@ vbit_destroy(struct vbitmap *vb)
if (vb == NULL)
return;
- free(vb->bits);
- free(vb);
+ if (vb->flags & VBITMAP_FL_MALLOC_BITS) {
+ free(vb->bits);
+ vb->bits = NULL;
+ vb->nbits = 0;
+ }
+ if (vb->flags & VBITMAP_FL_MALLOC)
+ free(vb);
}
static inline void
@@ -86,7 +129,7 @@ vbit_set(struct vbitmap *vb, unsigned bit)
{
if (bit >= vb->nbits)
- vbit_expand(vb, bit);
+ vbit_expand(vb, bit + 1);
vb->bits[VBITMAP_IDX(bit)] |= VBITMAP_BIT(bit);
}
diff --git a/include/vbm_test.c b/include/vbm_test.c
new file mode 100644
index 0000000..35bbb53
--- /dev/null
+++ b/include/vbm_test.c
@@ -0,0 +1,87 @@
+/*-
+ * Copyright 2016 UPLEX - Nils Goroll Systemoptimierung
+ * All rights reserved.
+ *
+ * Author: Nils Goroll <[email protected]>
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * Test Self-sizeing bitmap operations static initialization with dynamic growth
+ */
+
+#include <assert.h>
+#include <stdio.h>
+
+#include "vbm.h"
+
+int
+main(void)
+{
+ struct vbitmap vb_stk;
+ VBITMAP_INITIALIZE(vb_stk, 1);
+
+ VBITMAP_TYPE *obits = vb_stk.bits;
+ unsigned nbits = vb_stk.nbits;
+
+ assert(nbits == VBITMAP_WORD);
+
+ vbit_set(&vb_stk, nbits - 1);
+ assert(vbit_test(&vb_stk, nbits - 1));
+
+ assert(vb_stk.bits);
+ /* nothing malloc'ed - null ops */
+ vbit_destroy(&vb_stk);
+ assert(vb_stk.bits);
+ assert(vb_stk.bits == obits);
+
+ /* re-alloc */
+ vbit_set(&vb_stk, nbits);
+ assert(vbit_test(&vb_stk, nbits - 1));
+ assert(vbit_test(&vb_stk, nbits));
+ assert(vb_stk.nbits == VBITMAP_LUMP);
+ assert(vb_stk.bits != obits);
+ assert(vb_stk.flags & VBITMAP_FL_MALLOC_BITS);
+
+ assert(vb_stk.bits);
+ /* free the bits */
+ vbit_destroy(&vb_stk);
+ assert(vb_stk.bits == NULL);
+ assert(vb_stk.nbits == 0);
+
+ /* use again */
+ assert(20 < VBITMAP_LUMP);
+ vbit_set(&vb_stk, 20);
+ assert(vbit_test(&vb_stk, 20));
+ assert(vb_stk.nbits == VBITMAP_LUMP);
+ assert(vb_stk.flags & VBITMAP_FL_MALLOC_BITS);
+
+ /* grow */
+ vbit_set(&vb_stk, VBITMAP_LUMP);
+ assert(vbit_test(&vb_stk, 20));
+ assert(vbit_test(&vb_stk, VBITMAP_LUMP));
+ assert(vb_stk.nbits == 2 * VBITMAP_LUMP);
+ assert(vb_stk.flags & VBITMAP_FL_MALLOC_BITS);
+
+ vbit_destroy(&vb_stk);
+
+ return (0);
+}
--
2.1.4
_______________________________________________
varnish-dev mailing list
[email protected]
https://www.varnish-cache.org/lists/mailman/listinfo/varnish-dev
