Merged revisions 10129:10130 from the DRDDEV branch to the trunk.

git-svn-id: svn://svn.valgrind.org/valgrind/trunk@10355 a5019735-40e9-0310-863c-91ae7b9d1cf9

6 files changed, 194 insertions, 9 deletions

diff --git a/drd/Makefile.am b/drd/Makefile.am
index 84655f236..6f4b099e1 100644
--- a/drd/Makefile.am
+++ b/drd/Makefile.am
@@ -119,6 +119,7 @@ vgpreload_drd_amd64_darwin_so_LDFLAGS      = $(PRELOAD_LDFLAGS_AMD64_DARWIN)\
 
 DRD_SOURCES =           \
   drd_barrier.c         \
+  drd_bitmap2_node.c    \
   drd_clientobj.c       \
   drd_clientreq.c       \
   drd_cond.c            \
diff --git a/drd/drd_bitmap.c b/drd/drd_bitmap.c
index 65477f122..7c3c7d5ff 100644
--- a/drd/drd_bitmap.c
+++ b/drd/drd_bitmap.c
@@ -92,8 +92,8 @@ void DRD_(bm_init)(struct bitmap* const bm)
       bm->cache[i].a1  = ~(UWord)1;
       bm->cache[i].bm2 = 0;
    }
-   bm->oset = VG_(OSetGen_Create)(0, 0, VG_(malloc), "drd.bitmap.bn.2",
-                                  VG_(free));
+   bm->oset = VG_(OSetGen_Create)(0, 0, DRD_(bm2_alloc_node),
+                                  "drd.bitmap.bn.2", DRD_(bm2_free_node));
 }
 
 /** Free the memory allocated by DRD_(bm_init)(). */
@@ -1227,13 +1227,6 @@ ULong DRD_(bm_get_bitmap2_merge_count)(void)
    return s_bitmap2_merge_count;
 }
 
-/** Clear the bitmap contents. */
-static void bm2_clear(struct bitmap2* const bm2)
-{
-   tl_assert(bm2);
-   VG_(memset)(&bm2->bm1, 0, sizeof(bm2->bm1));
-}
-
 /** Compute *bm2l |= *bm2r. */
 static
 void bm2_merge(struct bitmap2* const bm2l, const struct bitmap2* const bm2r)
diff --git a/drd/drd_bitmap.h b/drd/drd_bitmap.h
index 3e07db920..55144c265 100644
--- a/drd/drd_bitmap.h
+++ b/drd/drd_bitmap.h
@@ -536,6 +536,16 @@ bm2_lookup_exclusive(struct bitmap* const bm, const UWord a1)
    return bm2;
 }
 
+/** Clear the content of the second-level bitmap. */
+static __inline__
+void bm2_clear(struct bitmap2* const bm2)
+{
+#ifdef ENABLE_DRD_CONSISTENCY_CHECKS
+   tl_assert(bm2);
+#endif
+   VG_(memset)(&bm2->bm1, 0, sizeof(bm2->bm1));
+}
+
 /**
  * Insert an uninitialized second level bitmap for the address a1.
  *
diff --git a/drd/drd_bitmap2_node.c b/drd/drd_bitmap2_node.c
new file mode 100644
index 000000000..6d016da99
--- /dev/null
+++ b/drd/drd_bitmap2_node.c
@@ -0,0 +1,177 @@
+/* -*- mode: C; c-basic-offset: 3; -*- */
+/*
+  This file is part of drd, a thread error detector.
+
+  Copyright (C) 2006-2009 Bart Van Assche <bart.vanassche@gmail.com>.
+
+  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., 59 Temple Place, Suite 330, Boston, MA
+  02111-1307, USA.
+
+  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 "drd_bitmap.h"           /* struct bitmap2 */
+#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) */
+
+
+#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)
+{
+   /*
+    * If szB < sizeof(struct bitmap2) then this function has been called to
+    * allocate an AVL tree root node. Otherwise it has been called to allocate
+    * an AVL tree branch or leaf node. 
+    */
+   if (szB < sizeof(struct bitmap2))
+      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)
+{
+   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)
+      {
+	 /* Free the memory that was allocated for a non-root AVL tree node. */
+         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;
+      }
+   }
+
+   /* Free the memory that was allocated for an AVL tree root node. */
+   VG_(free)(bm2);
+}
diff --git a/drd/pub_drd_bitmap.h b/drd/pub_drd_bitmap.h
index 8d7ad1a34..360b38c6d 100644
--- a/drd/pub_drd_bitmap.h
+++ b/drd/pub_drd_bitmap.h
@@ -148,4 +148,7 @@ ULong DRD_(bm_get_bitmap_creation_count)(void);
 ULong DRD_(bm_get_bitmap2_creation_count)(void);
 ULong DRD_(bm_get_bitmap2_merge_count)(void);
 
+void* DRD_(bm2_alloc_node)(HChar* const ec, const SizeT szB);
+void  DRD_(bm2_free_node)(void* const bm2);
+
 #endif /* __PUB_DRD_BITMAP_H */
diff --git a/drd/tests/unit_bitmap.c b/drd/tests/unit_bitmap.c
index 88519ed69..280943c6c 100644
--- a/drd/tests/unit_bitmap.c
+++ b/drd/tests/unit_bitmap.c
@@ -8,6 +8,7 @@
 #include <unistd.h>
 #include "coregrind/m_oset.c"
 #include "drd/drd_bitmap.c"
+#include "drd/drd_bitmap2_node.c"
 #include "drd/pub_drd_bitmap.h"