source: trunk/libc/src/kNIX/heap.c@ 2902

Last change on this file since 2902 was 2902, checked in by bird, 19 years ago

hacking.
  • Property cvs2svn:cvs-rev set to 1.4
  • Property svn:eol-style set to native
  • Property svn:executable set to *
File size: 14.7 KB
Line 
1/* $Id: $ */
2/** @file
3 *
4 * kNIX - sbrk/brk heap.
5 *
6 * Copyright (c) 1996 by Eberhard Mattes
7 * Copyright (c) 2006 knut st. osmundsen <bird-srcspam@anduin.net>
8 *
9 *
10 * This file is part of kLIBC.
11 *
12 * kLIBC is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU Lesser General Public License as published
14 * by the Free Software Foundation; either version 2 of the License, or
15 * (at your option) any later version.
16 *
17 * kLIBC is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU Lesser General Public License for more details.
21 *
22 * You should have received a copy of the GNU Lesser General Public License
23 * along with kLIBC; if not, write to the Free Software
24 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
25 *
26 */
27
28
29/*******************************************************************************
30* Header Files *
31*******************************************************************************/
32#define __LIBC_LOG_GROUP __LIBC_LOG_GRP_HEAP
33#include "kNIX.h"
34#ifdef __OS2__
35# define INCL_DOSERRORS
36# define INCL_FSMACROS
37# define INCL_EXAPIS
38# include <os2emx.h>
39#endif
40#ifdef __NT__
41# include <klibc/nt/nt.h>
42#endif
43#include <errno.h>
44#include <klibc/backend.h>
45#include <klibc/logstrict.h>
46
47
48
49/**
50 * Wrapper around the OS api for freeing an object.
51 */
52static __inline__ void heapFreeObj(uintptr_t ObjPtr)
53{
54#ifdef __OS2__
55 FS_VAR_SAVE_LOAD();
56 int rc = DosFreeMemEx((void *)ObjPtr);
57 LIBC_ASSERTM(!rc, vs"ObjPtr=%p rc=%d\n", ObjPtr, rc); (void)rc;
58 FS_RESTORE();
59
60#elif defined(__NT__)
61 PVOID pv = (void *)ObjPtr;
62 NTSTATUS rc = NtFreeVirtualMemory(NtCurrentProcess(), /* ProcessHandle */
63 &pv, /* BaseAddress */
64 NULL, /* FreeSize */
65 MEM_RELEASE); /* FreeType */
66 LIBC_ASSERTM(NT_SUCCESS(rc), "ObjPtr=%p rc=%x\n", ObjPtr, rc); (void)rc;
67
68#else
69# error "Port me!"
70#endif
71}
72
73
74/**
75 * Allocate a memory object of SIZE bytes which is not located below
76 * MIN_ADDR.
77 *
78 * @returns The address of the memory object.
79 * @returns Return 0 on error.
80 */
81static uintptr_t heapAllocObjAbove(uintptr_t size, uintptr_t min_addr)
82{
83 void *pv = NULL;
84#ifdef __OS2__
85 FS_VAR_SAVE_LOAD();
86 int rc = DosAllocMemEx(&pv, size, PAG_READ | PAG_WRITE | OBJ_FORK);
87 FS_RESTORE();
88 if (rc)
89 return 0;
90
91#elif defined(__NT__)
92 ULONG cb = size;
93 NTSTATUS rc = NtAllocateVirtualMemory(NtCurrentProcess(), /* ProcessHandle */
94 &pv, /* BaseAddress (In/Out) */
95 0, /* ZeroBits */
96 &cb, /* AllocationSize */
97 MEM_RESERVE, /* AllocationType */
98 PAGE_READWRITE); /* Protect */
99 if (!NT_SUCCESS(rc))
100 return 0;
101
102#else
103# error "Port me!"
104#endif
105
106 if ((uintptr_t)pv > min_addr)
107 return (uintptr_t)pv;
108
109 /*
110 * The memory object is located below MIN_ADDR. Recurse until we
111 * get an appropriate object or until we run out of memory.
112 */
113 uintptr_t ret = heapAllocObjAbove(size, min_addr);
114
115 /* We got a suitable object. Free the bad one. */
116 heapFreeObj((uintptr_t)pv);
117 return ret;
118}
119
120
121/**
122 * Wrapper around the OS api for committing memory.
123 */
124static __inline__ int heapCommitObj(uintptr_t addr, uintptr_t size)
125{
126#ifdef __OS2__
127 FS_VAR_SAVE_LOAD();
128 int rc = DosSetMem((void *)addr, size, PAG_DEFAULT | PAG_COMMIT);
129 FS_RESTORE();
130 return !rc ? 0 : -EINVAL;
131
132#elif defined(__NT__)
133 ULONG cb = size;
134 PVOID pv = (void *)addr;
135 NTSTATUS rc = NtAllocateVirtualMemory(NtCurrentProcess(), /* ProcessHandle */
136 &pv, /* BaseAddress (In/Out) */
137 0, /* ZeroBits */
138 &cb, /* AllocationSize */
139 MEM_COMMIT, /* AllocationType */
140 PAGE_READWRITE); /* Protect */
141 return NT_SUCCESS(rc) ? 0 : -EINVAL;
142
143#else
144# error "Port me!"
145#endif
146}
147
148
149/**
150 * Wrapper around the OS api for decommitting memory.
151 */
152static __inline__ int heapDecommitObj(uintptr_t addr, uintptr_t size)
153{
154#ifdef __OS2__
155 FS_VAR_SAVE_LOAD();
156 int rc = DosSetMem((void *)addr, size, PAG_DECOMMIT);
157 FS_RESTORE();
158 return !rc ? 0 : -EINVAL;
159
160#elif defined(__NT__)
161 ULONG cb = size;
162 PVOID pv = (void *)addr;
163 NTSTATUS rc = NtFreeVirtualMemory(NtCurrentProcess(), /* ProcessHandle */
164 &pv, /* BaseAddress */
165 &cb, /* FreeSize */
166 MEM_DECOMMIT); /* FreeType */
167 return NT_SUCCESS(rc) ? 0 : -EINVAL;
168
169#else
170# error "Port me!"
171#endif
172}
173
174
175
176/**
177 * Expand the top heap object by INCR bytes. INCR is a positive number.
178 * Return the previous break address or 0 (error).
179 */
180void *__libc_back_heapExpandObjBy(uintptr_t incr)
181{
182 LIBCLOG_ENTER("incr=%p\n", (void *)incr);
183
184 const uintptr_t old_brk = __libc_back_gpHeapTopObj->brk;
185 const uintptr_t new_brk = old_brk + incr;
186 if ( new_brk < __libc_back_gpHeapTopObj->base
187 || new_brk > __libc_back_gpHeapTopObj->end)
188 LIBCLOG_ERROR_RETURN_P(NULL);
189
190 uintptr_t addr = old_brk;
191 uintptr_t size = incr;
192 if (addr & 0xfff)
193 {
194 uintptr_t rest = 0x1000 - (addr & 0xfff);
195 if (rest >= size)
196 size = 0;
197 else
198 {
199 size -= rest;
200 addr += rest;
201 }
202 }
203 if (size != 0)
204 {
205 if (heapCommitObj(addr, size) != 0)
206 LIBCLOG_ERROR_RETURN_P(NULL);
207 }
208 __libc_back_gpHeapTopObj->brk = new_brk;
209 LIBCLOG_RETURN_P((void *)old_brk);
210}
211
212
213/**
214 * Shrink the top heap object by DECR bytes. DECR is a positive number.
215 * Return the previous break address or 0 (error).
216 */
217void *__libc_back_heapShrinkObjBy(uintptr_t decr)
218{
219 LIBCLOG_ENTER("decr=%p\n", (void *)decr);
220
221 const uintptr_t old_brk = __libc_back_gpHeapTopObj->brk;
222 const uintptr_t new_brk = old_brk - decr;
223 if ( new_brk < __libc_back_gpHeapTopObj->base
224 || new_brk > __libc_back_gpHeapTopObj->end)
225 LIBCLOG_ERROR_RETURN_P(NULL);
226
227 const uintptr_t addr = (new_brk + 0xfff) & ~(uintptr_t)0xfff;
228 const uintptr_t high = (__libc_back_gpHeapTopObj->brk + 0xfff) & ~(uintptr_t)0xfff;
229 if (high > addr)
230 {
231 if (heapDecommitObj(addr, high - addr) != 0)
232 LIBCLOG_ERROR_RETURN_P(NULL);
233 }
234 __libc_back_gpHeapTopObj->brk = new_brk;
235 LIBCLOG_RETURN_P((void *)old_brk);
236}
237
238
239/**
240 * Expand the heap by INCR bytes. INCR is a positive number.
241 * Return the base address of the expansion or 0 (error).
242 */
243void *__libc_back_heapExpandBy(uintptr_t incr, __LIBCSBRKMODEL enmSBrkModel)
244{
245 LIBCLOG_ENTER("incr=%p enmSBrkModel=%d\n", incr, enmSBrkModel);
246 const unsigned old_obj_count = __libc_back_gcHeapObjs;
247
248 /*
249 *Allocate the first object if not yet done.
250 */
251 if (__libc_back_gcHeapObjs == 0)
252 {
253 uintptr_t size = __libc_back_gcbHeap;
254 if (incr > size)
255 size = (incr + 0xffff) & ~(uintptr_t)0xffff;
256 uintptr_t base = heapAllocObjAbove(size, 0);
257 if (base == 0)
258 LIBCLOG_ERROR_RETURN_P(NULL);
259 __libc_back_gaHeapObjs[0].base = base;
260 __libc_back_gaHeapObjs[0].brk = base;
261 __libc_back_gaHeapObjs[0].end = base + size;
262 __libc_back_gcHeapObjs = 1;
263 __libc_back_gpHeapTopObj = &__libc_back_gaHeapObjs[0];
264 }
265
266 /*
267 * Now we have at least one heap object. Check for arithmetic
268 * overflow.
269 */
270 if (__libc_back_gpHeapTopObj->brk + incr < __libc_back_gpHeapTopObj->base)
271 {
272 /*
273 * Overflow. If we've just allocated the first heap object,
274 * deallocate it again unless memory must be allocated contiguously.
275 */
276 if ( old_obj_count == 0
277 && enmSBrkModel != __LIBC_SBRK_MODEL_CONTIGUOUS)
278 {
279 heapFreeObj(__libc_back_gaHeapObjs[0].base);
280 __libc_back_gcHeapObjs = 0;
281 __libc_back_gpHeapTopObj = NULL;
282 }
283 LIBCLOG_ERROR_RETURN_P(NULL);
284 }
285
286 /*
287 * Check whether we need another heap object. Allocate one if we
288 * need one and are allowed to allocate one. This should not happen
289 * if we just allocated the first one above.
290 */
291 if (__libc_back_gpHeapTopObj->brk + incr > __libc_back_gpHeapTopObj->end)
292 {
293 /*
294 * We need another heap object. Fail if we are not allowed to
295 * allocate non-contiguous memory or if we already have the
296 * maximum number of heap objects.
297 */
298 if ( enmSBrkModel == __LIBC_SBRK_MODEL_CONTIGUOUS
299 || __libc_back_gcHeapObjs >= CFG_KNIX_MAX_HEAP_OBJS)
300 LIBCLOG_ERROR_RETURN_P(NULL);
301
302 /*
303 * Allocate at least __libc_back_gcbHeap bytes. The new object must
304 * be located above the currently top one.
305 */
306 uintptr_t size = __libc_back_gcbHeap;
307 if (incr > size)
308 size = (incr + 0xffff) & ~(uintptr_t)0xffff;
309
310 uintptr_t base;
311 for (;;)
312 {
313 if (enmSBrkModel == __LIBC_SBRK_MODEL_ARBITRARY)
314 base = heapAllocObjAbove(size, 0);
315 else
316 base = heapAllocObjAbove(size, __libc_back_gpHeapTopObj->end);
317 if (base != 0)
318 break;
319
320 /*
321 * If we're out of virtual address space, halve the size and
322 * try again until allocation succeeds. Of course, don't
323 * attempt to allocate less than INCR bytes.
324 */
325 size /= 2;
326 if (size < incr)
327 LIBCLOG_ERROR_RETURN_P(NULL);
328 }
329
330 __libc_back_gpHeapTopObj = &__libc_back_gaHeapObjs[__libc_back_gcHeapObjs++];
331 __libc_back_gpHeapTopObj->base = base;
332 __libc_back_gpHeapTopObj->brk = base;
333 __libc_back_gpHeapTopObj->end = base + size;
334 }
335
336 /*
337 * Now __libc_back_gpHeapTopObj points to an object which has enough
338 * space. Commit memory as required. _sys_expand_heap_obj() returns
339 * the top object's break address, which is the base address of the
340 * expansion as an object might have been added.
341 */
342 void *pRet = __libc_back_heapExpandObjBy(incr);
343 if (pRet)
344 LIBCLOG_RETURN_P(pRet);
345 LIBCLOG_ERROR_RETURN_P(pRet);
346}
347
348
349/**
350 * Shrink the heap to the new break address NEW_BRK.
351 * Return the previous break address or 0 (error).
352 */
353void *__libc_back_heapShrinkTo(uintptr_t new_brk)
354{
355 LIBCLOG_ENTER("new_brk=%ld\n", new_brk);
356
357 /*
358 * Find the heap object containing the new break address. Fail if
359 * there is no such heap object. Note that the new break address
360 * must not be beyond the heap object current break address, that
361 * is, we cannot shrink the heap (by deallocating objects) and grow
362 * a heap object in one step.
363 */
364 unsigned iObj;
365 for (iObj = 0; iObj < __libc_back_gcHeapObjs; ++iObj)
366 if ( __libc_back_gaHeapObjs[iObj].base <= new_brk
367 && __libc_back_gaHeapObjs[iObj].brk >= new_brk)
368 break;
369 if (iObj >= __libc_back_gcHeapObjs)
370 return 0;
371
372 /* We have at least one heap object, OBJ, so this is safe. */
373 void * const pvOldBrk = (void *)__libc_back_gpHeapTopObj->brk;
374
375 /*
376 * Free objects which are between the new break address and the old
377 * one. Fail if there are such objects and __LIBC_SBRK_MODEL_CONTIGUOUS is
378 * selected.
379 */
380 if (iObj != __libc_back_gcHeapObjs - 1)
381 {
382 if (__libc_back_genmSBrkModel == __LIBC_SBRK_MODEL_CONTIGUOUS)
383 LIBCLOG_ERROR_RETURN_P(NULL);
384
385 while (__libc_back_gcHeapObjs - 1 > iObj)
386 {
387 __libc_back_gcHeapObjs -= 1;
388 heapFreeObj(__libc_back_gaHeapObjs[__libc_back_gcHeapObjs].base);
389 __libc_back_gaHeapObjs[__libc_back_gcHeapObjs].base = 0;
390 }
391 __libc_back_gpHeapTopObj = &__libc_back_gaHeapObjs[__libc_back_gcHeapObjs-1];
392 }
393
394 if (new_brk == __libc_back_gpHeapTopObj->base)
395 {
396 /*
397 * The top object is shrunk to zero bytes, deallocate it and bump NEW_BRK back
398 * to the previous object. If __LIBC_SBRK_MODEL_CONTIGUOUS is selected and
399 * the (only) object is shrunk to 0 bytes, it will be kept anyway to avoid
400 * breaking programs which depend on the object keeping its address:
401 *
402 * p = sbrk(1000);
403 * sbrk(-1000);
404 * assert(sbrk(1000) == p);
405 *
406 * The assertion should not fail. However, programs which select
407 * __LIBC_SBRK_MODEL_MONOTONOUS or __LIBC_SBRK_MODEL_ARBITRARY should be
408 * prepared for failure of the assertion. Consider the following code:
409 *
410 * sbrk(1000);
411 * p = sbrk(0);
412 * sbrk(-1000);
413 * brk(p);
414 *
415 * Here, brk() may fail due to deallocation of the top object.
416 */
417 if ( iObj != 0
418 || __libc_back_genmSBrkModel != __LIBC_SBRK_MODEL_CONTIGUOUS)
419 {
420 __libc_back_gcHeapObjs -= 1;
421 heapFreeObj(__libc_back_gaHeapObjs[__libc_back_gcHeapObjs].base);
422 __libc_back_gaHeapObjs[__libc_back_gcHeapObjs].base = 0;
423
424 if (__libc_back_gcHeapObjs == 0)
425 __libc_back_gpHeapTopObj = NULL;
426 else
427 {
428 __libc_back_gpHeapTopObj = &__libc_back_gaHeapObjs[__libc_back_gcHeapObjs-1];
429 new_brk = __libc_back_gpHeapTopObj->brk;
430 }
431 }
432 }
433
434 /*
435 * Now decommit unused pages of the top heap object, if there is one.
436 */
437 if ( __libc_back_gcHeapObjs > 0
438 && __libc_back_heapShrinkObjBy(__libc_back_gpHeapTopObj->brk - new_brk) == 0)
439 LIBCLOG_RETURN_P(NULL);
440 LIBCLOG_RETURN_P(pvOldBrk);
441}
442
443
444/**
445 * Shrink the heap by DECR bytes. DECR is a positive number.
446 * Return the previous break address or 0 (error).
447 */
448void *__libc_back_heapShrinkBy(uintptr_t decr, __LIBCSBRKMODEL enmSBrkModel)
449{
450 LIBCLOG_ENTER("decr=%ld enmSBrkModel=%d\n", decr, enmSBrkModel);
451 if ( __libc_back_gcHeapObjs != 0
452 && __libc_back_gpHeapTopObj->brk - decr >= __libc_back_gpHeapTopObj->base)
453 {
454 void *pvRet = __libc_back_heapShrinkTo(__libc_back_gpHeapTopObj->brk - decr);
455 LIBCLOG_RETURN_P(pvRet);
456 }
457 LIBCLOG_RETURN_P(NULL);
458}
459
Note: See TracBrowser for help on using the repository browser.