rebased to master after sw 3rd party completed
[dyninst.git] / dyninstAPI_RT / src / RTheap.c
1 /*
2  * See the dyninst/COPYRIGHT file for copyright information.
3  * 
4  * We provide the Paradyn Tools (below described as "Paradyn")
5  * on an AS IS basis, and do not warrant its validity or performance.
6  * We reserve the right to update, modify, or discontinue this
7  * software at any time.  We shall have no obligation to supply such
8  * updates or modifications or any other form of support to you.
9  * 
10  * By your use of Paradyn, you understand and agree that we (or any
11  * other person or entity with proprietary rights in Paradyn) are
12  * under no obligation to provide either maintenance services,
13  * update services, notices of latent defects, or correction of
14  * defects for Paradyn.
15  * 
16  * This library is free software; you can redistribute it and/or
17  * modify it under the terms of the GNU Lesser General Public
18  * License as published by the Free Software Foundation; either
19  * version 2.1 of the License, or (at your option) any later version.
20  * 
21  * This library is distributed in the hope that it will be useful,
22  * but WITHOUT ANY WARRANTY; without even the implied warranty of
23  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
24  * Lesser General Public License for more details.
25  * 
26  * You should have received a copy of the GNU Lesser General Public
27  * License along with this library; if not, write to the Free Software
28  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
29  */
30
31 /* $Id: RTheap.c,v 1.25 2006/05/03 00:31:25 jodom Exp $ */
32 /* RTheap.c: platform-generic heap management */
33
34 #include <stdlib.h>
35 #include <stdio.h>
36 #if !defined(os_windows) /* ccw 15 may 2000 : 29 mar 2001 */
37         /* win does not have these header files.  it appears the only
38         one that is used assert.h anyway.
39         */
40 #include <errno.h>
41 #include <unistd.h>
42 #include <sys/types.h>
43 #include <sys/stat.h>                 /* open() */
44 #include <fcntl.h>                    /* open() */
45 #else
46 extern int getpagesize();
47 #endif
48 #include <assert.h>
49
50 #include "dyninstAPI_RT/src/RTheap.h"
51 #include "dyninstAPI_RT/src/RTcommon.h"
52
53
54 typedef enum {
55   HEAP_TYPE_UNKNOWN = 0x0,
56   HEAP_TYPE_MMAP =    0x1,
57   HEAP_TYPE_MALLOC =  0x2
58 } heapType_t;
59     
60 typedef struct heap_t {
61   void *ret_addr;  /* address returned to mutator */
62   void *addr;      /* actual heap address */
63   size_t len;      /* actual heap length */
64   heapType_t type; /* heap allocation type */
65 } heap_t;
66
67 typedef struct heapList_t {
68   heap_t heap;
69   struct heapList_t *prev;
70   struct heapList_t *next;
71 } heapList_t;
72
73
74 /* local variables */
75 static heapList_t *Heaps = NULL;
76 static int psize = -1;
77
78
79 /*
80 static void heap_printMappings(int nmaps, dyninstmm_t *maps)
81 {
82   int i;
83   fprintf(stderr, "memory mappings:\n");
84   for(i = 0; i < nmaps; i++) {
85     dyninstmm_t *map = &maps[i];
86     Address addr = (Address)map->pr_vaddr;
87     fprintf(stderr, "  heap %2i: 0x%016lx-0x%016lx (%3lu pages, %.2fkB)\n", 
88             i, addr, addr + map->pr_size - 1, 
89             map->pr_size / psize, map->pr_size / 1024.0);
90   }
91 }
92 */
93
94 static void heap_checkMappings(int nmaps, dyninstmm_t *maps)
95 {
96   int i;
97   for (i = 0; i < nmaps-1; i++) {
98     if (maps[i].pr_vaddr + maps[i].pr_size > maps[i+1].pr_vaddr) {
99       fprintf(stderr, "*** memory mappings overlap\n");
100       abort();
101     }
102   }
103 }
104
105 static Address heap_alignUp(Address addr, int align)
106 {
107   if (addr % align == 0) return addr;
108   return ((addr / align) + 1) * align;
109 }
110
111 /*
112 static Address heap_alignDown(Address addr, int align)
113 {
114   if (addr % align == 0) return addr;
115   return ((addr / align) + 0) * align;
116 }
117 */
118
119 #define BEG(x) ((Address)(x)->pr_vaddr)
120 #define END(x) ((Address)(x)->pr_vaddr + (x)->pr_size)
121
122 static Address trymmap(size_t len, Address beg, Address end, size_t inc, int fd)
123 {
124   Address addr;
125   void *result;
126   /*We have a possibly large region (beg to end) and a hopefully smaller */
127   /* allocation size (len).  We try to map at every page in the region*/
128   /* until we get one that succeeds.*/
129   for (addr = beg; addr + len <= end; addr += inc) {
130     result = map_region((void *) addr, len, fd);
131     if (result)
132         return (Address) result;
133   }
134   return (Address) NULL;
135 }
136
137 /* Attempt to mmap a region of memory of size LEN bytes somewhere
138    between LO and HI.  Returns the address of the region on success, 0
139    otherwise.  MAPS is the current address space map, with NMAPS
140    elements.  FD is the mmap file descriptor argument. */
141 static Address constrained_mmap(size_t len, Address lo, Address hi,
142                                 const dyninstmm_t *maps, int nmaps, int fd)
143 {
144    const dyninstmm_t *mlo, *mhi, *p;
145    Address beg, end, try;
146 #if defined (os_linux)  && defined(arch_power)
147 // DYNINSTheap_loAddr should already be defined in DYNINSTos_malloc. 
148 // Redefining here, just in case constrained_mmap is called from a different call path.
149    DYNINSTheap_loAddr = getpagesize();
150 #endif
151
152    if (lo > DYNINSTheap_hiAddr) return 0;
153
154    if (lo < DYNINSTheap_loAddr) lo = DYNINSTheap_loAddr;
155    if (hi > DYNINSTheap_hiAddr) hi = DYNINSTheap_hiAddr;
156
157    /* Round down to nearest page boundary */
158    lo = lo & ~(psize-1);
159    hi = hi & ~(psize-1);
160
161    /* Round up to nearest page boundary */
162    if (len % psize) {
163       len += psize;
164       len = len & ~(psize-1);
165    }
166
167    assert(lo < hi);
168    /* Find lowest (mlo) and highest (mhi) segments between lo and
169       hi.  If either lo or hi occurs within a segment, they are
170       shifted out of it toward the other bound. */
171    mlo = maps;
172    mhi = &maps[nmaps-1];
173    while (mlo <= mhi) {
174       beg = BEG(mlo);
175       end = END(mlo);
176
177       if (lo < beg)
178          break;
179
180       if (lo >= beg && lo < end)
181          /* lo occurs in this segment.  Shift lo to end of segment. */
182          lo = end; /* still a page boundary */
183
184       ++mlo;
185    }
186              
187    while (mhi >= mlo) {
188       beg = BEG(mhi);
189       end = END(mhi);
190
191       if (hi > end)
192          break;
193       if (hi >= beg && hi <= end)
194          /* hi occurs in this segment (or just after it).  Shift
195             hi to beginning of segment. */
196          hi = beg; /* still a page boundary */
197
198       --mhi;
199    }
200    if (lo >= hi)
201       return 0;
202
203    /* We've set the bounds of the search, now go find some free space. */
204
205    /* Pathological cases in which the range (lo,hi) is entirely
206       above or below the rest of the address space, or there are no
207       segments between lo and hi.  Return no matter what from
208       here. */
209    if (BEG(mlo) >= hi || END(mhi) <= lo) {
210       return trymmap(len, lo, hi, psize, fd);
211    }
212    assert(lo < BEG(mlo) && hi > END(mhi));
213    /* Try to mmap in space before mlo */
214    try = trymmap(len, lo, BEG(mlo), psize, fd);
215    if (try) {
216       return try;
217    }
218
219    /* Try to mmap in space between mlo and mhi.  Try nothing here if
220       mlo and mhi are the same. */
221    for (p = mlo; p < mhi; p++) {
222       try = trymmap(len, END(p), BEG(p+1), psize, fd);
223       if (try)
224          return try;
225    }
226
227    /* Try to mmap in space between mhi and hi */
228    try = trymmap(len, END(mhi), hi, psize, fd);
229    if (try)
230       return try;
231
232    /* We've tried everything */
233    return 0;
234 }
235 #undef BEG
236 #undef END
237
238
239 static int heap_memmapCompare(const void *A, const void *B)
240 {
241   const dyninstmm_t *a = (const dyninstmm_t *)A;
242   const dyninstmm_t *b = (const dyninstmm_t *)B;
243   if (a->pr_vaddr < b->pr_vaddr) return -1;
244   if (a->pr_vaddr > b->pr_vaddr) return 1;
245   return 0;
246 }
247
248 void *DYNINSTos_malloc(size_t nbytes, void *lo_addr, void *hi_addr)
249 {
250   void *heap;
251   size_t size = nbytes;
252   heapList_t *node = (heapList_t *)malloc(sizeof(heapList_t));
253
254   /* initialize page size */
255   if (psize == -1) psize = getpagesize();
256
257   /* buffer size must be aligned */
258   if (size % DYNINSTheap_align != 0) {
259     free(node);
260     return ((void *)-1);
261   }
262
263   /* use malloc() if appropriate */
264   if (DYNINSTheap_useMalloc(lo_addr, hi_addr)) {
265
266     Address ret_heap;
267     int size_heap = size + DYNINSTheap_align;
268     heap = malloc(size_heap);
269     if (heap == NULL) {
270       free(node);
271 #ifdef DEBUG
272       fprintf(stderr, "Failed to MALLOC\n");      
273 #endif 
274       return NULL;
275     }
276     ret_heap = heap_alignUp((Address)heap, DYNINSTheap_align);
277     
278     /* malloc buffer must meet range constraints */
279     if (ret_heap < (Address)lo_addr ||
280         ret_heap + size - 1 > (Address)hi_addr) {
281       free(heap);
282       free(node);
283 #ifdef DEBUG
284       fprintf(stderr, "MALLOC'd area fails range constraints\n");
285 #endif 
286       return NULL;
287     }
288
289     /* define new heap */
290     node->heap.ret_addr = (void *)ret_heap;
291     node->heap.addr = heap;
292     node->heap.len = size_heap;
293     node->heap.type = HEAP_TYPE_MALLOC;
294
295
296   } else { /* use mmap() for allocation */
297     Address lo = (Address) lo_addr;
298     Address hi = (Address) hi_addr;
299     int fd;
300     unsigned nmaps;
301     dyninstmm_t *maps;
302
303     /* What if we need to allocate memory not in the area we can mmap? */
304 #if defined (os_linux)  && defined(arch_power)
305    DYNINSTheap_loAddr = getpagesize();
306 #endif
307     if ((hi < DYNINSTheap_loAddr) || (lo > DYNINSTheap_hiAddr)) {
308       free(node);
309 #ifdef DEBUG
310       fprintf(stderr, "CAN'T MMAP IN RANGE GIVEN\n");
311 #endif 
312       return NULL;
313     }
314     
315
316     /* Get memory map and sort it.  maps will point to malloc'd memory
317        that we must free. */
318     if (0 > DYNINSTgetMemoryMap(&nmaps, &maps)) {
319       free(node);
320 #ifdef DEBUG
321       fprintf(stderr, "failed MMAP\n");
322 #endif 
323       return NULL;
324     }
325     qsort(maps, (size_t)nmaps, (size_t)sizeof(dyninstmm_t), &heap_memmapCompare);
326     heap_checkMappings(nmaps, maps); /* sanity check */
327
328     /*DYNINSTheap_printMappings(nmaps, maps);*/
329
330     fd = DYNINSTheap_mmapFdOpen();
331     if (0 > fd) {
332       free(node);
333       free(maps);
334       return NULL;
335     }
336     heap = (void*) constrained_mmap(size, lo, hi, maps, nmaps, fd);
337     free(maps);
338     DYNINSTheap_mmapFdClose(fd);
339     if (!heap) {
340        free(node);
341 #ifdef DEBUG
342        fprintf(stderr, "failed MMAP(2)\n");
343 #endif 
344        return NULL;
345     }
346
347     /* define new heap */
348     node->heap.ret_addr = heap;
349     node->heap.addr = heap;
350     node->heap.len = size;
351     node->heap.type = HEAP_TYPE_MMAP;
352   }
353
354   /* insert new heap into heap list */
355   node->prev = NULL;
356   node->next = Heaps;
357   if (Heaps) Heaps->prev = node;
358   Heaps = node;
359   
360   return node->heap.ret_addr;
361 }
362
363 int DYNINSTos_free(void *buf)
364 {
365   int ret = 0;
366   heapList_t *t;
367   /*
368   fprintf(stderr, "*** DYNINSTos_free(0x%08x)\n", buf);
369   */
370   for (t = Heaps; t != NULL; t = t->next) {
371     /* lookup heap by (returned) address */
372     heap_t *heap = &t->heap;
373     if (heap->ret_addr != buf) continue;
374
375     /* remove heap from list */
376     if (t->next) t->next->prev = t->prev;
377     if (t->prev) t->prev->next = t->next;
378     if (Heaps == t) Heaps = t->next;
379
380     /* deallocate heap */
381     switch (heap->type) {
382     case HEAP_TYPE_MMAP:
383       if (!unmap_region(heap->addr, heap->len)) {
384         perror("DYNINSTos_free(munmap)");
385         ret = -1;
386       }
387       break;
388     case HEAP_TYPE_MALLOC:
389       free(heap->addr);
390       break;
391     default:
392       fprintf(stderr, "DYNINSTos_free(): unknown inferior heap type\n");
393       ret = -1;
394       break;
395     }
396
397     /* free list element */
398     free(t);
399     break;
400   }
401
402   return ret;
403 }
404