1 /* -*- mode: C; c-basic-offset: 3; -*- */ 2 /* 3 This file is part of drd, a thread error detector. 4 5 Copyright (C) 2006-2010 Bart Van Assche <bvanassche (at) 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_bm2_node_size; 60 static struct block_allocator_chunk* s_first; 61 62 63 /* Function definitions. */ 64 65 /** 66 * Allocate a new chunk and insert it at the start of the doubly-linked list 67 * s_first. 68 */ 69 static struct block_allocator_chunk* allocate_new_chunk(void) 70 { 71 struct block_allocator_chunk* p; 72 int i; 73 74 tl_assert(s_bm2_node_size > 0); 75 76 p = VG_(malloc)("drd.bitmap.bac", 77 sizeof(*p) + NODES_PER_CHUNCK * s_bm2_node_size); 78 tl_assert(p); 79 p->next = s_first; 80 if (s_first) 81 p->next->prev = p; 82 s_first = p; 83 p->prev = 0; 84 p->nallocated = 0; 85 p->data = (char*)p + sizeof(*p); 86 tl_assert(p->data); 87 p->data_end = (char*)(p->data) + NODES_PER_CHUNCK * s_bm2_node_size; 88 p->first_free = p->data; 89 for (i = 0; i < NODES_PER_CHUNCK - 1; i++) 90 { 91 *(void**)((char*)(p->data) + i * s_bm2_node_size) 92 = (char*)(p->data) + (i + 1) * s_bm2_node_size; 93 } 94 tl_assert(i == NODES_PER_CHUNCK - 1); 95 *(void**)((char*)(p->data) + i * s_bm2_node_size) = NULL; 96 97 return p; 98 } 99 100 /** Free a chunk and remove it from the list of chunks. */ 101 static void free_chunk(struct block_allocator_chunk* const p) 102 { 103 tl_assert(p); 104 tl_assert(p->nallocated == 0); 105 106 if (p == s_first) 107 s_first = p->next; 108 else if (p->prev) 109 p->prev->next = p->next; 110 if (p->next) 111 p->next->prev = p->prev; 112 VG_(free)(p); 113 } 114 115 /** Allocate a node. */ 116 void* DRD_(bm2_alloc_node)(HChar* const ec, const SizeT szB) 117 { 118 /* 119 * If szB < sizeof(struct bitmap2) then this function has been called to 120 * allocate an AVL tree root node. Otherwise it has been called to allocate 121 * an AVL tree branch or leaf node. 122 */ 123 if (szB < sizeof(struct bitmap2)) 124 return VG_(malloc)(ec, szB); 125 126 while (True) 127 { 128 struct block_allocator_chunk* p; 129 130 if (s_bm2_node_size == 0) 131 s_bm2_node_size = szB; 132 else 133 tl_assert(s_bm2_node_size == szB); 134 135 for (p = s_first; p; p = p->next) 136 { 137 if (p->first_free) 138 { 139 void* result; 140 141 p->nallocated++; 142 result = p->first_free; 143 p->first_free = *(void**)(p->first_free); 144 return result; 145 } 146 } 147 148 allocate_new_chunk(); 149 } 150 } 151 152 /** Free a node. */ 153 void DRD_(bm2_free_node)(void* const bm2) 154 { 155 struct block_allocator_chunk* p; 156 157 tl_assert(s_bm2_node_size > 0); 158 tl_assert(bm2); 159 160 for (p = s_first; p; p = p->next) 161 { 162 if (p->data <= bm2 && bm2 < p->data_end) 163 { 164 /* Free the memory that was allocated for a non-root AVL tree node. */ 165 tl_assert(((char*)bm2 - (char*)(p->data)) % s_bm2_node_size == 0); 166 *(void**)bm2 = p->first_free; 167 p->first_free = bm2; 168 tl_assert(p->nallocated >= 1); 169 if (--(p->nallocated) == 0) 170 free_chunk(p); 171 return; 172 } 173 } 174 175 /* Free the memory that was allocated for an AVL tree root node. */ 176 VG_(free)(bm2); 177 } 178
