summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorSander Vrijders <sander.vrijders@intec.ugent.be>2016-03-11 16:54:05 +0100
committerSander Vrijders <sander.vrijders@intec.ugent.be>2016-03-11 16:54:05 +0100
commitbf5157839b3fed718ef8a5d1bb20f5290866a9cd (patch)
tree81034e89ec567fb990793118b9866e6ddb0f9d1e
parentf5cf4e478bf7dec70dc22d80de706f82ef4b38f1 (diff)
parentb68c90fbf9f4a60e4fc406903e38d20453ba8253 (diff)
downloadouroboros-bf5157839b3fed718ef8a5d1bb20f5290866a9cd.tar.gz
ouroboros-bf5157839b3fed718ef8a5d1bb20f5290866a9cd.zip
Merge remote-tracking branch 'upstream/be' into be-irmd
-rw-r--r--include/ouroboros/bitmap.h16
-rw-r--r--src/lib/bitmap.c61
-rw-r--r--src/lib/du_buff.c2
-rw-r--r--src/lib/tests/CMakeLists.txt3
-rw-r--r--src/lib/tests/bitmap_test.c77
-rw-r--r--src/lib/tests/du_buff_test.c57
-rw-r--r--src/lib/tests/linked_list.c26
7 files changed, 180 insertions, 62 deletions
diff --git a/include/ouroboros/bitmap.h b/include/ouroboros/bitmap.h
index 6296e2e0..c109f3e8 100644
--- a/include/ouroboros/bitmap.h
+++ b/include/ouroboros/bitmap.h
@@ -1,7 +1,7 @@
/*
* Ouroboros - Copyright (C) 2016
*
- * RINA bitmap implementation - wraps around bitmap from Linux kernel
+ * Bitmap implementation
*
* Sander Vrijders <sander.vrijders@intec.ugent.be>
* Francesco Salvestrini <f.salvestrini@nextworks.it>
@@ -28,14 +28,14 @@
#include <unistd.h>
#include <stdbool.h>
-struct rbmp;
+struct bmp;
-struct rbmp * rbmp_create(size_t bits, ssize_t offset);
-int rbmp_destroy(struct rbmp * b);
+struct bmp * bmp_create(size_t bits, ssize_t offset);
+int bmp_destroy(struct bmp * b);
-ssize_t rbmp_allocate(struct rbmp * instance);
-int rbmp_release(struct rbmp * instance,
- ssize_t id);
-bool rbmp_is_id_ok(struct rbmp * b, ssize_t id);
+ssize_t bmp_allocate(struct bmp * instance);
+int bmp_release(struct bmp * instance,
+ ssize_t id);
+bool bmp_is_id_valid(struct bmp * b, ssize_t id);
#endif
diff --git a/src/lib/bitmap.c b/src/lib/bitmap.c
index 3aaa422c..8aabb4f4 100644
--- a/src/lib/bitmap.c
+++ b/src/lib/bitmap.c
@@ -21,7 +21,10 @@
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
+#define OUROBOROS_PREFIX "bitmap"
+
#include <ouroboros/bitmap.h>
+#include <ouroboros/logs.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
@@ -37,8 +40,6 @@
#define BITS_TO_LONGS(nr) \
DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long))
-#define BITS_IN_BITMAP ((2 << BITS_PER_BYTE) * sizeof(size_t))
-
static unsigned long find_next_zero_bit(const unsigned long * addr,
unsigned long nbits)
{
@@ -59,7 +60,7 @@ static unsigned long find_next_zero_bit(const unsigned long * addr,
/* Find the free bit in the word */
mask = 1UL;
- while (!(tmp ^ mask)) {
+ while (!(tmp & mask)) {
pos++;
mask = 1UL << pos;
}
@@ -78,31 +79,30 @@ static void bitmap_clear(unsigned long * map,
unsigned int start)
{
unsigned long * p = map + BIT_WORD(start);
- unsigned long mask = ~(1UL << (start % (BITS_PER_LONG - 1)));
+ unsigned long mask = ~(1UL << (start % (BITS_PER_LONG)));
*p &= mask;
}
-
static void bitmap_set(unsigned long * map,
unsigned int start)
{
unsigned long * p = map + BIT_WORD(start);
- unsigned long mask = 1UL << (start % (BITS_PER_LONG - 1));
+ unsigned long mask = 1UL << (start % (BITS_PER_LONG));
*p |= mask;
}
-struct rbmp {
+struct bmp {
ssize_t offset;
size_t size;
- unsigned long bitmap[BITS_TO_LONGS(BITS_IN_BITMAP)];
+ unsigned long * bitmap;
};
-struct rbmp * rbmp_create(size_t bits, ssize_t offset)
+struct bmp * bmp_create(size_t bits, ssize_t offset)
{
- struct rbmp * tmp;
+ struct bmp * tmp;
if (bits == 0)
return NULL;
@@ -111,32 +111,41 @@ struct rbmp * rbmp_create(size_t bits, ssize_t offset)
if (!tmp)
return NULL;
+ tmp->bitmap = malloc(BITS_TO_LONGS(bits) * sizeof(*(tmp->bitmap)));
+ if (!tmp->bitmap)
+ return NULL;
+
tmp->size = bits;
tmp->offset = offset;
- bitmap_zero(tmp->bitmap, BITS_IN_BITMAP);
+ bitmap_zero(tmp->bitmap, bits);
return tmp;
}
-
-int rbmp_destroy(struct rbmp * b)
+int bmp_destroy(struct bmp * b)
{
- if (!b)
+ if (b == NULL)
+ return -1;
+
+ if (b->bitmap == NULL) {
+ free(b);
return -1;
+ }
+ free(b->bitmap);
free(b);
return 0;
}
-static ssize_t bad_id(struct rbmp * b)
+static ssize_t bad_id(struct bmp * b)
{
assert(b);
return b->offset - 1;
}
-ssize_t rbmp_allocate(struct rbmp * b)
+ssize_t bmp_allocate(struct bmp * b)
{
ssize_t id;
@@ -144,9 +153,9 @@ ssize_t rbmp_allocate(struct rbmp * b)
return bad_id(b);
id = (ssize_t) find_next_zero_bit(b->bitmap,
- BITS_IN_BITMAP);
+ b->size);
- if (id == BITS_IN_BITMAP)
+ if (id >= b->size)
return bad_id(b);
bitmap_set(b->bitmap, id);
@@ -154,8 +163,8 @@ ssize_t rbmp_allocate(struct rbmp * b)
return id + b->offset;
}
-static bool is_id_ok(struct rbmp * b,
- ssize_t id)
+static bool is_id_valid(struct bmp * b,
+ ssize_t id)
{
assert(b);
@@ -165,24 +174,24 @@ static bool is_id_ok(struct rbmp * b,
return true;
}
-bool rbmp_is_id_ok(struct rbmp * b,
- ssize_t id)
+bool bmp_is_id_valid(struct bmp * b,
+ ssize_t id)
{
if (!b)
return false;
- return is_id_ok(b, id);
+ return is_id_valid(b, id);
}
-int rbmp_release(struct rbmp * b,
- ssize_t id)
+int bmp_release(struct bmp * b,
+ ssize_t id)
{
ssize_t rid;
if (!b)
return -1;
- if (!is_id_ok(b, id))
+ if (!is_id_valid(b, id))
return -1;
rid = id - b->offset;
diff --git a/src/lib/du_buff.c b/src/lib/du_buff.c
index d88d7ac4..bd1a092d 100644
--- a/src/lib/du_buff.c
+++ b/src/lib/du_buff.c
@@ -29,7 +29,7 @@
#define OUROBOROS_PREFIX "du_buff"
#ifndef DU_BUFF_BLOCKSIZE
-#define DU_BUFF_BLOCKSIZE 1 << 16
+#define DU_BUFF_BLOCKSIZE (1 << 16)
#endif
#include "ouroboros/logs.h"
diff --git a/src/lib/tests/CMakeLists.txt b/src/lib/tests/CMakeLists.txt
index 2b02768b..99df7232 100644
--- a/src/lib/tests/CMakeLists.txt
+++ b/src/lib/tests/CMakeLists.txt
@@ -3,7 +3,8 @@ get_filename_component(src_folder "${tmp}" NAME)
create_test_sourcelist(${src_folder}_tests test_suite.c
# Add new tests here
- linked_list.c
+ bitmap_test.c
+ du_buff_test.c
)
add_executable(${src_folder}_test EXCLUDE_FROM_ALL ${${src_folder}_tests})
diff --git a/src/lib/tests/bitmap_test.c b/src/lib/tests/bitmap_test.c
new file mode 100644
index 00000000..4d2d0c73
--- /dev/null
+++ b/src/lib/tests/bitmap_test.c
@@ -0,0 +1,77 @@
+/*
+ * Ouroboros - Copyright (C) 2016
+ *
+ * Test of the bitmap
+ *
+ * Sander Vrijders <sander.vrijders@intec.ugent.be>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ */
+
+#include "bitmap.c"
+#include <time.h>
+#include <stdlib.h>
+
+#define BITMAP_SIZE 200
+
+int bitmap_test(int argc, char ** argv)
+{
+ struct bmp * bmp;
+ size_t bits = BITMAP_SIZE;
+ ssize_t id;
+ int i;
+ ssize_t r;
+ ssize_t offset = 100;
+
+ srand(time(NULL));
+
+ bmp = bmp_create(bits, offset);
+ if (bmp == NULL)
+ return -1;
+
+ if (bmp_destroy(bmp))
+ return -1;
+
+ bmp = bmp_create(bits, offset);
+ if (bmp == NULL)
+ return -1;
+
+ for (i = offset; i < BITMAP_SIZE + 5 + offset; i++) {
+ id = bmp_allocate(bmp);
+ if (!bmp_is_id_valid(bmp, id))
+ continue;
+
+ if (id != i)
+ return -1;
+ }
+
+ for (i = 0; i < BITMAP_SIZE + 5; i++) {
+ r = (ssize_t) (rand() % BITMAP_SIZE) + offset;
+
+ if (bmp_release(bmp, r))
+ return -1;
+
+ id = bmp_allocate(bmp);
+ if (!bmp_is_id_valid(bmp, id))
+ continue;
+ if (id != r)
+ return -1;
+ }
+
+ if (bmp_destroy(bmp))
+ return -1;
+
+ return 0;
+}
diff --git a/src/lib/tests/du_buff_test.c b/src/lib/tests/du_buff_test.c
new file mode 100644
index 00000000..7bdf1459
--- /dev/null
+++ b/src/lib/tests/du_buff_test.c
@@ -0,0 +1,57 @@
+/*
+ * Ouroboros - Copyright (C) 2016
+ *
+ * Test of the du_buff
+ *
+ * Dimitri Staessens <dimitri.staessens@intec.ugent.be>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ */
+
+#include "du_buff.c"
+
+#define TEST_BUFF_SIZE 16 * DU_BUFF_BLOCKSIZE
+#define MAX(a,b) a > b ? a : b
+
+int du_buff_test(int argc, char ** argv)
+{
+ int i, j, k;
+ int i_inc, j_inc, k_inc;
+
+ uint8_t bits[TEST_BUFF_SIZE];
+
+ for (i = 0; i < TEST_BUFF_SIZE; i++)
+ bits[i] = 170;
+
+ i_inc = MAX(1, DU_BUFF_BLOCKSIZE / 4);
+ j_inc = MAX(1, DU_BUFF_BLOCKSIZE / 8);
+ k_inc = MAX(1, DU_BUFF_BLOCKSIZE / 16);
+
+ for (i = DU_BUFF_BLOCKSIZE / 4; i <= TEST_BUFF_SIZE; i += i_inc) {
+ for (j = 0; j < i; j += j_inc) {
+ for (k = 0; k < i - j; k += k_inc) {
+ du_buff_t * dub = du_buff_create(i);
+ if (dub == NULL)
+ return -1;
+
+ if (du_buff_init(dub, k, bits, j) < 0)
+ return -1;
+
+ du_buff_destroy (dub);
+ }
+ }
+ }
+ return 0; /* tests succeeded */
+}
diff --git a/src/lib/tests/linked_list.c b/src/lib/tests/linked_list.c
deleted file mode 100644
index 2239b065..00000000
--- a/src/lib/tests/linked_list.c
+++ /dev/null
@@ -1,26 +0,0 @@
-/*
- * Ouroboros - Copyright (C) 2016
- *
- * Test of the linked list
- *
- * Sander Vrijders <sander.vrijders@intec.ugent.be>
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2 of the License, or
- * (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
- */
-
-int linked_list(int argc, char ** argv)
-{
- return 0;
-}