|
From: <sv...@va...> - 2009-05-24 18:10:53
|
Author: bart
Date: 2009-05-24 19:10:41 +0100 (Sun, 24 May 2009)
New Revision: 10130
Log:
Implemented a block allocator for DRD's second-level bitmap nodes.
Modified:
branches/DRDDEV/coregrind/m_oset.c
branches/DRDDEV/drd/drd_bitmap2_node.c
branches/DRDDEV/memcheck/tests/unit_oset.c
Modified: branches/DRDDEV/coregrind/m_oset.c
===================================================================
--- branches/DRDDEV/coregrind/m_oset.c 2009-05-24 07:53:33 UTC (rev 10129)
+++ branches/DRDDEV/coregrind/m_oset.c 2009-05-24 18:10:41 UTC (rev 10130)
@@ -80,6 +80,7 @@
#include "pub_core_libcassert.h"
#include "pub_core_libcprint.h"
#include "pub_core_oset.h"
+#include "pub_tool_mallocfree.h" /* VG_(malloc), VG_(free) */
/*--------------------------------------------------------------------*/
/*--- Types and constants ---*/
@@ -296,7 +297,7 @@
vg_assert(_free);
if (!_cmp) vg_assert(0 == _keyOff); // If no cmp, offset must be zero
- t = _alloc(_cc, sizeof(AvlTree));
+ t = VG_(malloc)("oset", sizeof(AvlTree));
t->keyOff = _keyOff;
t->cmp = _cmp;
t->alloc = _alloc;
@@ -348,7 +349,7 @@
vg_assert(sz == t->nElems);
/* Free the AvlTree itself. */
- t->free(t);
+ VG_(free)(t);
}
void VG_(OSetWord_Destroy)(AvlTree* t)
Modified: branches/DRDDEV/drd/drd_bitmap2_node.c
===================================================================
--- branches/DRDDEV/drd/drd_bitmap2_node.c 2009-05-24 07:53:33 UTC (rev 10129)
+++ branches/DRDDEV/drd/drd_bitmap2_node.c 2009-05-24 18:10:41 UTC (rev 10130)
@@ -22,30 +22,145 @@
The GNU General Public License is contained in the file COPYING.
*/
+/*
+ * Block allocator for second-level bitmap nodes. Each node consists of
+ * an OSetGen node and a struct bitmap2. The code below allocates
+ * NODES_PER_CHUNK nodes at a time.
+ */
+
#include "drd_basics.h" /* DRD_() */
#include "pub_drd_bitmap.h"
#include "pub_tool_basics.h" /* Addr, SizeT */
#include "pub_tool_libcassert.h" /* tl_assert() */
+#include "pub_tool_libcbase.h" /* VG_ROUNDUP() */
+#include "pub_tool_libcprint.h" /* VG_(message)() */
#include "pub_tool_mallocfree.h" /* VG_(malloc), VG_(free) */
-/* Local function declarations. */
+#define NODES_PER_CHUNCK 512
+/* Local type definitions. */
+struct block_allocator_chunk {
+ struct block_allocator_chunk* next;
+ struct block_allocator_chunk* prev;
+ int nallocated;
+ void* data;
+ void* data_end;
+ void* first_free;
+};
+
+
/* Local variables. */
+static SizeT s_bm2_node_size;
+static struct block_allocator_chunk* s_first;
/* Function definitions. */
+/**
+ * Allocate a new chunk and insert it at the start of the doubly-linked list
+ * s_first.
+ */
+static struct block_allocator_chunk* allocate_new_chunk(void)
+{
+ struct block_allocator_chunk* p;
+ int i;
+
+ tl_assert(s_bm2_node_size > 0);
+
+ p = VG_(malloc)("drd.bitmap.bac",
+ sizeof(*p) + NODES_PER_CHUNCK * s_bm2_node_size);
+ tl_assert(p);
+ p->next = s_first;
+ if (s_first)
+ p->next->prev = p;
+ s_first = p;
+ p->prev = 0;
+ p->nallocated = 0;
+ p->data = (char*)p + sizeof(*p);
+ tl_assert(p->data);
+ p->data_end = (char*)(p->data) + NODES_PER_CHUNCK * s_bm2_node_size;
+ p->first_free = p->data;
+ for (i = 0; i < NODES_PER_CHUNCK - 1; i++)
+ {
+ *(void**)((char*)(p->data) + i * s_bm2_node_size)
+ = (char*)(p->data) + (i + 1) * s_bm2_node_size;
+ }
+ tl_assert(i == NODES_PER_CHUNCK - 1);
+ *(void**)((char*)(p->data) + i * s_bm2_node_size) = NULL;
+
+ return p;
+}
+
+/** Free a chunk and remove it from the list of chunks. */
+static void free_chunk(struct block_allocator_chunk* const p)
+{
+ tl_assert(p);
+ tl_assert(p->nallocated == 0);
+
+ if (p == s_first)
+ s_first = p->next;
+ else if (p->prev)
+ p->prev->next = p->next;
+ if (p->next)
+ p->next->prev = p->prev;
+ VG_(free)(p);
+}
+
+/** Allocate a node. */
void* DRD_(bm2_alloc_node)(HChar* const ec, const SizeT szB)
{
- return VG_(malloc)(ec, szB);
+ while (True)
+ {
+ struct block_allocator_chunk* p;
+
+ if (s_bm2_node_size == 0)
+ s_bm2_node_size = szB;
+ else
+ tl_assert(s_bm2_node_size == szB);
+
+ for (p = s_first; p; p = p->next)
+ {
+ if (p->first_free)
+ {
+ void* result;
+
+ p->nallocated++;
+ result = p->first_free;
+ p->first_free = *(void**)(p->first_free);
+ return result;
+ }
+ }
+
+ allocate_new_chunk();
+ }
}
+/** Free a node. */
void DRD_(bm2_free_node)(void* const bm2)
{
- return VG_(free)(bm2);
+ struct block_allocator_chunk* p;
+
+ tl_assert(s_bm2_node_size > 0);
+ tl_assert(bm2);
+
+ for (p = s_first; p; p = p->next)
+ {
+ if (p->data <= bm2 && bm2 < p->data_end)
+ {
+ tl_assert(((char*)bm2 - (char*)(p->data)) % s_bm2_node_size == 0);
+ *(void**)bm2 = p->first_free;
+ p->first_free = bm2;
+ tl_assert(p->nallocated >= 1);
+ if (--(p->nallocated) == 0)
+ free_chunk(p);
+ return;
+ }
+ }
+
+ tl_assert(False);
}
Modified: branches/DRDDEV/memcheck/tests/unit_oset.c
===================================================================
--- branches/DRDDEV/memcheck/tests/unit_oset.c 2009-05-24 07:53:33 UTC (rev 10129)
+++ branches/DRDDEV/memcheck/tests/unit_oset.c 2009-05-24 18:10:41 UTC (rev 10130)
@@ -28,6 +28,11 @@
#define vgPlain_memset memset
#define vgPlain_memcpy memcpy
+void* VG_(malloc)(HChar* cc, SizeT nbytes)
+{ return malloc(nbytes); }
+void VG_(free)(void* p)
+{ return free(p); }
+
#include "coregrind/m_oset.c"
#define NN 1000 // Size of OSets being created
|