gprofng/src/HeapMap.cc

   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
  29 typedef struct HeapObj
  30 {
  31   uint64_t addr;
  32   uint64_t size;
  33   long val;
  34   HeapObj *next;
  35 } HeapObj;
  36
  37 typedef struct HeapChunk
  38 {
  39   void *addr;
  40   HeapChunk *next;
  41 } HeapChunk;
  42
  43 HeapMap::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
  58 HeapMap::~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
  72 void
  73 HeapMap::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
 120 long
 121 HeapMap::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
 149 void
 150 HeapMap::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
 171 HeapObj *
 172 HeapMap::getHeapObj ()
 173 {
 174   if (empty == NULL)
 175     allocateChunk ();
 176   HeapObj *ret = empty;
 177   empty = ret->next;
 178   return ret;
 179 }
 180
 181 void
 182 HeapMap::releaseHeapObj (HeapObj *obj)
 183 {
 184   obj->next = empty;
 185   empty = obj;
 186 }
 187
 188 UnmapChunk*
 189 HeapMap::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
 200 UnmapChunk*
 201 HeapMap::munmap (uint64_t addr, int64_t size)
 202 {
 203   UnmapChunk* list = process (NULL, addr, size);
 204   return list;
 205 }
 206
 207 UnmapChunk*
 208 HeapMap::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 }