1/* Copyright (C) 2021 Free Software Foundation, Inc. 2 Contributed by Oracle. 3 4 This file is part of GNU Binutils. 5 6 This program is free software; you can redistribute it and/or modify 7 it under the terms of the GNU General Public License as published by 8 the Free Software Foundation; either version 3, or (at your option) 9 any later version. 10 11 This program is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 GNU General Public License for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with this program; if not, write to the Free Software 18 Foundation, 51 Franklin Street - Fifth Floor, Boston, 19 MA 02110-1301, USA. */ 20 21#include "config.h" 22#include "util.h" 23#include "HeapMap.h" 24 25#define HEAPCHUNKSZ 1024 // number of HeapObj's in a chunk 26#define HEAPCHAINS 9192 // number of address-based chains 27#define hash(x) (((x) >> 6) % HEAPCHAINS) 28 29typedef struct HeapObj 30{ 31 uint64_t addr; 32 uint64_t size; 33 long val; 34 HeapObj *next; 35} HeapObj; 36 37typedef struct HeapChunk 38{ 39 void *addr; 40 HeapChunk *next; 41} HeapChunk; 42 43HeapMap::HeapMap () 44{ 45 chunks = NULL; 46 empty = NULL; 47 chain = new HeapObj*[HEAPCHAINS]; 48 for (int i = 0; i < HEAPCHAINS; i++) 49 chain[i] = NULL; 50 51 mmaps = new HeapObj; 52 mmaps->addr = (uint64_t) 0; 53 mmaps->size = (uint64_t) 0; 54 mmaps->val = -1; 55 mmaps->next = NULL; 56} 57 58HeapMap::~HeapMap () 59{ 60 // free up all the chunks 61 HeapChunk *c = chunks; 62 while (c != NULL) 63 { 64 HeapChunk *next = c->next; 65 delete c; 66 c = next; 67 } 68 delete[] chain; 69 delete mmaps; 70} 71 72void 73HeapMap::allocate (uint64_t addr, long val) 74{ 75 // get a HeapObj, and set it up for the allocated block 76 HeapObj *incoming = getHeapObj (); 77 incoming->addr = addr; 78 incoming->val = val; 79 incoming->next = NULL; 80 81 // determine which chain the block belongs on 82 int ichain = (int) hash (addr); 83 84 // if this is the first, just set it up and return 85 if (chain[ichain] == NULL) 86 { 87 chain[ichain] = incoming; 88 return; 89 } 90 // chain is non-empty -- find the slot for this one 91 // chain is maintained in reverse address order 92 HeapObj *prev = NULL; 93 HeapObj *next = chain[ichain]; 94 95 for (;;) 96 { 97 if ((next == NULL) || (next->addr < incoming->addr)) 98 { 99 // we've found the spot 100 incoming->next = next; 101 if (prev == NULL) 102 chain[ichain] = incoming; 103 else 104 prev->next = incoming; 105 return; 106 } 107 if (next->addr == incoming->addr) 108 { 109 // error -- two blocks with same address active 110 // ignore the new one 111 releaseHeapObj (incoming); 112 return; 113 } 114 // not yet, keep looking 115 prev = next; 116 next = next->next; 117 } 118} 119 120long 121HeapMap::deallocate (uint64_t addr) 122{ 123 int ichain = (int) hash (addr); 124 HeapObj *cur = chain[ichain]; 125 HeapObj *prev = NULL; 126 while (cur != NULL) 127 { 128 if (cur->addr == addr) 129 { 130 // we've found the block 131 long val = cur->val; 132 133 // delete the block from the chain 134 if (prev == NULL) 135 chain[ichain] = cur->next; 136 else 137 prev->next = cur->next; 138 releaseHeapObj (cur); 139 return val; 140 } 141 prev = cur; 142 cur = cur->next; 143 } 144 145 // block not found 146 return 0; 147} 148 149void 150HeapMap::allocateChunk () 151{ 152 // allocate the memory 153 HeapChunk *c = new HeapChunk; 154 HeapObj *newc = new HeapObj[HEAPCHUNKSZ]; 155 156 // set up the chunk, and queue it for destructor's use 157 c->addr = (void *) newc; 158 c->next = chunks; 159 chunks = c; 160 161 // Initialize the HeapObj's in the chunk to one chain 162 // last entry is left NULL, terminating the chain 163 for (int i = 0; i < (HEAPCHUNKSZ - 1); i++) 164 newc[i].next = newc + i + 1; 165 newc[HEAPCHUNKSZ - 1].next = NULL; 166 167 // put that chain on the empty queue 168 empty = newc; 169} 170 171HeapObj * 172HeapMap::getHeapObj () 173{ 174 if (empty == NULL) 175 allocateChunk (); 176 HeapObj *ret = empty; 177 empty = ret->next; 178 return ret; 179} 180 181void 182HeapMap::releaseHeapObj (HeapObj *obj) 183{ 184 obj->next = empty; 185 empty = obj; 186} 187 188UnmapChunk* 189HeapMap::mmap (uint64_t addr, int64_t size, long val) 190{ 191 HeapObj *incoming = getHeapObj (); 192 incoming->addr = addr; 193 incoming->size = size; 194 incoming->val = val; 195 incoming->next = NULL; 196 UnmapChunk* list = process (incoming, addr, size); 197 return list; 198} 199 200UnmapChunk* 201HeapMap::munmap (uint64_t addr, int64_t size) 202{ 203 UnmapChunk* list = process (NULL, addr, size); 204 return list; 205} 206 207UnmapChunk* 208HeapMap::process (HeapObj *obj, uint64_t addr, int64_t size) 209{ 210 // Some graphics are used to clarify the alignment of mmap regions 211 // obj, shown as consecutive pages: "NNNNNN" 212 // cur, shown as consecutive pages: "CCCCCC" 213 214 // Find the first overlap, start of N is before end of C. Examples: 215 // CCCCC 216 // NNNNN 217 // or 218 // CCCCC 219 // NNN 220 // or 221 // CCCCC 222 // NNNNN 223 // or 224 // CCCCC 225 // NNNNNNN 226 HeapObj *prev = mmaps; 227 HeapObj *cur = prev->next; 228 while (cur) 229 { 230 if (addr < cur->addr + cur->size) 231 break; 232 prev = cur; 233 cur = prev->next; 234 } 235 236 // None found 237 if (cur == NULL) 238 { 239 prev->next = obj; 240 return NULL; 241 } 242 243 UnmapChunk* list = NULL; 244 if (addr > cur->addr) 245 { 246 if (cur->addr + cur->size <= addr + size) 247 { 248 // Process overlap on the left (low side) of new allocation 249 // New range: N-start to C-end (gets freed below) 250 prev = cur; 251 cur = getHeapObj (); 252 cur->addr = addr; 253 cur->size = prev->addr + prev->size - addr; 254 cur->val = prev->val; 255 cur->next = prev->next; 256 257 // Truncate range: C-start to N-start 258 prev->size = addr - prev->addr; 259 } 260 else 261 { 262 // Process new allocation that fits completely within old allocation 263 // New range: N-start to N-end (freed below) 264 int64_t c_end = cur->addr + cur->size; 265 prev = cur; 266 cur = getHeapObj (); 267 cur->addr = addr; 268 cur->size = size; 269 cur->val = prev->val; 270 cur->next = prev->next; 271 272 // Truncate range: C-start to N-start 273 prev->size = addr - prev->addr; 274 275 // New range: N-end to C-end. 276 HeapObj *next = getHeapObj (); 277 next->addr = addr + size; 278 next->size = c_end - next->addr; 279 next->val = cur->val; 280 next->next = cur->next; 281 cur->next = next; 282 } 283 } 284 285 // Process all full overlaps. 286 // Copy details of cur to UnmapChunk list, remove cur from mmaps 287 while (cur && cur->addr + cur->size <= addr + size) 288 { 289 290 UnmapChunk* uc = new UnmapChunk; 291 uc->val = cur->val; 292 uc->size = cur->size; 293 uc->next = list; 294 list = uc; 295 296 HeapObj *t = cur; 297 cur = cur->next; 298 releaseHeapObj (t); 299 } 300 301 if (cur && cur->addr < addr + size) 302 { 303 // Process the last overlap (right side of new allocation) 304 // Copy details of cur to UnmapChunk list 305 UnmapChunk* uc = new UnmapChunk; 306 uc->val = cur->val; 307 uc->size = addr + size - cur->addr; 308 uc->next = list; 309 list = uc; 310 311 // Truncate left side of cur 312 cur->size -= uc->size; 313 cur->addr = addr + size; 314 } 315 316 // Insert new allocation 317 if (obj) 318 { 319 prev->next = obj; 320 obj->next = cur; 321 } 322 else 323 prev->next = cur; 324 return list; 325} 326