1/* -*- mode: C; c-basic-offset: 3; indent-tabs-mode: nil; -*- */
2/*
3  This file is part of drd, a thread error detector.
4
5  Copyright (C) 2006-2011 Bart Van Assche <bvanassche@acm.org>.
6
7  This program is free software; you can redistribute it and/or
8  modify it under the terms of the GNU General Public License as
9  published by the Free Software Foundation; either version 2 of the
10  License, or (at your option) any later version.
11
12  This program is distributed in the hope that it will be useful, but
13  WITHOUT ANY WARRANTY; without even the implied warranty of
14  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  General Public License for more details.
16
17  You should have received a copy of the GNU General Public License
18  along with this program; if not, write to the Free Software
19  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
20  02111-1307, USA.
21
22  The GNU General Public License is contained in the file COPYING.
23*/
24
25/*
26 * Block allocator for second-level bitmap nodes. Each node consists of
27 * an OSetGen node and a struct bitmap2. The code below allocates
28 * NODES_PER_CHUNK nodes at a time.
29 */
30
31
32#include "drd_basics.h"           /* DRD_() */
33#include "drd_bitmap.h"           /* struct bitmap2 */
34#include "pub_drd_bitmap.h"
35#include "pub_tool_basics.h"      /* Addr, SizeT */
36#include "pub_tool_libcassert.h"  /* tl_assert() */
37#include "pub_tool_libcbase.h"    /* VG_ROUNDUP() */
38#include "pub_tool_libcprint.h"   /* VG_(message)() */
39#include "pub_tool_mallocfree.h"  /* VG_(malloc), VG_(free) */
40
41
42#define NODES_PER_CHUNCK 512
43
44
45/* Local type definitions. */
46
47struct block_allocator_chunk {
48   struct block_allocator_chunk* next;
49   struct block_allocator_chunk* prev;
50   int   nallocated;
51   void* data;
52   void* data_end;
53   void* first_free;
54};
55
56
57/* Local variables. */
58
59static SizeT s_root_node_size;
60static SizeT s_bm2_node_size;
61static struct block_allocator_chunk* s_first;
62
63
64/* Function definitions. */
65
66/**
67 * Allocate a new chunk and insert it at the start of the doubly-linked list
68 * s_first.
69 */
70static struct block_allocator_chunk* allocate_new_chunk(void)
71{
72   struct block_allocator_chunk* p;
73   int i;
74
75   tl_assert(s_bm2_node_size > 0);
76
77   p = VG_(malloc)("drd.bitmap.bac",
78                   sizeof(*p) + NODES_PER_CHUNCK * s_bm2_node_size);
79   tl_assert(p);
80   p->next = s_first;
81   if (s_first)
82      p->next->prev = p;
83   s_first = p;
84   p->prev = 0;
85   p->nallocated = 0;
86   p->data = (char*)p + sizeof(*p);
87   tl_assert(p->data);
88   p->data_end = (char*)(p->data) + NODES_PER_CHUNCK * s_bm2_node_size;
89   p->first_free = p->data;
90   for (i = 0; i < NODES_PER_CHUNCK - 1; i++)
91   {
92      *(void**)((char*)(p->data) + i * s_bm2_node_size)
93         = (char*)(p->data) + (i + 1) * s_bm2_node_size;
94   }
95   tl_assert(i == NODES_PER_CHUNCK - 1);
96   *(void**)((char*)(p->data) + i * s_bm2_node_size) = NULL;
97
98   return p;
99}
100
101/** Free a chunk and remove it from the list of chunks. */
102static void free_chunk(struct block_allocator_chunk* const p)
103{
104   tl_assert(p);
105   tl_assert(p->nallocated == 0);
106
107   if (p == s_first)
108      s_first = p->next;
109   else if (p->prev)
110      p->prev->next = p->next;
111   if (p->next)
112      p->next->prev = p->prev;
113   VG_(free)(p);
114}
115
116/** Allocate a node. */
117void* DRD_(bm2_alloc_node)(HChar* const ec, const SizeT szB)
118{
119   /*
120    * If szB < sizeof(struct bitmap2) then this function has been called to
121    * allocate an AVL tree root node. Otherwise it has been called to allocate
122    * an AVL tree branch or leaf node.
123    */
124   if (s_root_node_size == 0)
125      s_root_node_size = szB;
126   if (szB == s_root_node_size)
127      return VG_(malloc)(ec, szB);
128
129   while (True)
130   {
131      struct block_allocator_chunk* p;
132
133      if (s_bm2_node_size == 0)
134         s_bm2_node_size = szB;
135      else
136         tl_assert(s_bm2_node_size == szB);
137
138      for (p = s_first; p; p = p->next)
139      {
140         if (p->first_free)
141         {
142            void* result;
143
144            p->nallocated++;
145            result = p->first_free;
146            p->first_free = *(void**)(p->first_free);
147            return result;
148         }
149      }
150
151      allocate_new_chunk();
152   }
153}
154
155/** Free a node. */
156void  DRD_(bm2_free_node)(void* const bm2)
157{
158   struct block_allocator_chunk* p;
159
160   tl_assert(bm2);
161
162   if (s_bm2_node_size > 0) {
163      for (p = s_first; p; p = p->next) {
164	 if (p->data <= bm2 && bm2 < p->data_end) {
165	    /* Free a non-root AVL tree node. */
166	    tl_assert(((char*)bm2 - (char*)(p->data)) % s_bm2_node_size == 0);
167	    *(void**)bm2 = p->first_free;
168	    p->first_free = bm2;
169	    tl_assert(p->nallocated >= 1);
170	    if (--(p->nallocated) == 0)
171	       free_chunk(p);
172	    return;
173	 }
174      }
175   }
176   /* Free the memory that was allocated for an AVL tree root node. */
177   VG_(free)(bm2);
178}
179