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