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 (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_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 */ 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. */ 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. */ 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. */ 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
