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

Last change on this file since 3770 was 3770, checked in by bird, 13 years ago

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