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
47 struct 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
59 static SizeT s_root_node_size;
60 static SizeT s_bm2_node_size;
61 static 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 */
allocate_new_chunk(void)70 static 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. */
free_chunk(struct block_allocator_chunk * const p)102 static 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. */
DRD_(bm2_alloc_node)117 void* 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. */
DRD_(bm2_free_node)156 void 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