1 | /* $Id: kLdrHlpHeap.c 2826 2006-10-22 15:58:55Z bird $ */
|
---|
2 | /** @file
|
---|
3 | *
|
---|
4 | * kLdr - The Dynamic Loader, Helper Functions, Heap.
|
---|
5 | *
|
---|
6 | * Copyright (c) 2006 knut st. osmundsen <bird-kbuild-src@anduin.net>
|
---|
7 | *
|
---|
8 | *
|
---|
9 | * This file is part of kLdr.
|
---|
10 | *
|
---|
11 | * kLdr is free software; you can redistribute it and/or modify
|
---|
12 | * it under the terms of the GNU General Public License as published by
|
---|
13 | * the Free Software Foundation; either version 2 of the License, or
|
---|
14 | * (at your option) any later version.
|
---|
15 | *
|
---|
16 | * kLdr is distributed in the hope that it will be useful,
|
---|
17 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
18 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
---|
19 | * GNU General Public License for more details.
|
---|
20 | *
|
---|
21 | * You should have received a copy of the GNU General Public License
|
---|
22 | * along with kLdr; if not, write to the Free Software
|
---|
23 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
|
---|
24 | *
|
---|
25 | */
|
---|
26 |
|
---|
27 | #define KLDRHEAP_STRICT
|
---|
28 |
|
---|
29 | /*******************************************************************************
|
---|
30 | * Header Files *
|
---|
31 | *******************************************************************************/
|
---|
32 | #ifdef __OS2__
|
---|
33 | # define INCL_BASE
|
---|
34 | # define INCL_ERRORS
|
---|
35 | # include <os2.h>
|
---|
36 | #elif defined(__WIN__)
|
---|
37 | # include <Windows.h>
|
---|
38 | #else
|
---|
39 | # error "port me"
|
---|
40 | #endif
|
---|
41 |
|
---|
42 | #include <kLdr.h>
|
---|
43 | #include "kLdrHlp.h"
|
---|
44 |
|
---|
45 |
|
---|
46 |
|
---|
47 | /*******************************************************************************
|
---|
48 | * Structures and Typedefs *
|
---|
49 | *******************************************************************************/
|
---|
50 | /**
|
---|
51 | * A heap block.
|
---|
52 | */
|
---|
53 | typedef struct KLDRHEAPBLOCK
|
---|
54 | {
|
---|
55 | /** Next block in the global list. */
|
---|
56 | struct KLDRHEAPBLOCK *pNext;
|
---|
57 | /** Previous block in the global list. */
|
---|
58 | struct KLDRHEAPBLOCK *pPrev;
|
---|
59 | /** The size of this block including this header. */
|
---|
60 | size_t cb;
|
---|
61 | /** The flags. */
|
---|
62 | size_t fFlags;
|
---|
63 | } KLDRHEAPBLOCK, *PKLDRHEAPBLOCK;
|
---|
64 |
|
---|
65 | /** Indicates whether the block is free (set) or allocated (clear). */
|
---|
66 | #define KLDRHEAPBLOCK_FLAG_FREE ((size_t)1)
|
---|
67 | /** Valid flag mask. */
|
---|
68 | #define KLDRHEAPBLOCK_FLAG_MASK ((size_t)1)
|
---|
69 |
|
---|
70 | /** Checks if the block is freed. */
|
---|
71 | #define KLDRHEAPBLOCK_IS_FREE(pB) ( (pB)->fFlags & KLDRHEAPBLOCK_FLAG_FREE )
|
---|
72 | /** Check if the block is allocated. */
|
---|
73 | #define KLDRHEAPBLOCK_IS_ALLOCATED(pB) !KLDRHEAPBLOCK_IS_FREE(pB)
|
---|
74 | /** Checks if the two blocks are adjacent.
|
---|
75 | * Assumes pB1 < pB2. */
|
---|
76 | #define KLDRHEAPBLOCK_IS_ADJACENT(pB1, pB2) \
|
---|
77 | ( ((uintptr_t)(pB1) + (pB1)->cb) == (uintptr_t)(pB2) )
|
---|
78 |
|
---|
79 | /** The block alignment. */
|
---|
80 | #define KLDRHEAPBLOCK_ALIGNMENT sizeof(KLDRHEAPBLOCK)
|
---|
81 |
|
---|
82 | /** @def KLDRHEAP_ASSERT
|
---|
83 | * Heap assertion. */
|
---|
84 | /** @def KLDRHEAP_ASSERT_BLOCK
|
---|
85 | * Assert that a heap block is valid. */
|
---|
86 | /** @def KLDRHEAP_ASSERT_FREE
|
---|
87 | * Assert that a heap free block is valid. */
|
---|
88 | #ifdef KLDRHEAP_STRICT
|
---|
89 | # define KLDRHEAP_ASSERT(expr) kldrHlpAssert(expr)
|
---|
90 |
|
---|
91 | # define KLDRHEAP_ASSERT_BLOCK(pHeap, pBlock) \
|
---|
92 | do { \
|
---|
93 | KLDRHEAP_ASSERT(!((pBlock)->fFlags & ~KLDRHEAPBLOCK_FLAG_MASK)); \
|
---|
94 | KLDRHEAP_ASSERT(!((pBlock)->cb & (KLDRHEAPBLOCK_ALIGNMENT - 1))); \
|
---|
95 | KLDRHEAP_ASSERT((uintptr_t)(pBlock)->pPrev < (uintptr_t)(pBlock)); \
|
---|
96 | KLDRHEAP_ASSERT((uintptr_t)(pBlock)->pNext > (uintptr_t)(pBlock) || !(pBlock)->pNext); \
|
---|
97 | } while (0)
|
---|
98 |
|
---|
99 | # define KLDRHEAP_ASSERT_FREE(pHeap, pFree) \
|
---|
100 | do { \
|
---|
101 | KLDRHEAP_ASSERT_BLOCK(pHeap, &(pFree)->Core); \
|
---|
102 | KLDRHEAP_ASSERT((uintptr_t)(pFree)->pPrev < (uintptr_t)(pFree)); \
|
---|
103 | KLDRHEAP_ASSERT((uintptr_t)(pFree)->pNext > (uintptr_t)(pFree) || !(pFree)->pNext); \
|
---|
104 | } while (0)
|
---|
105 |
|
---|
106 | #else
|
---|
107 | # define KLDRHEAP_ASSERT(expr) do { } while (0)
|
---|
108 | # define KLDRHEAP_ASSERT_BLOCK(pH, pB) do { } while (0)
|
---|
109 | # define KLDRHEAP_ASSERT_FREE(pH, pF) do { } while (0)
|
---|
110 | #endif
|
---|
111 |
|
---|
112 |
|
---|
113 | /**
|
---|
114 | * A free heap block.
|
---|
115 | */
|
---|
116 | typedef struct KLDRHEAPFREE
|
---|
117 | {
|
---|
118 | /** The core bit which we have in common with used blocks. */
|
---|
119 | KLDRHEAPBLOCK Core;
|
---|
120 | /** The next free block. */
|
---|
121 | struct KLDRHEAPFREE *pNext;
|
---|
122 | /** The previous free block. */
|
---|
123 | struct KLDRHEAPFREE *pPrev;
|
---|
124 | } KLDRHEAPFREE, *PKLDRHEAPFREE;
|
---|
125 |
|
---|
126 |
|
---|
127 | /**
|
---|
128 | * A heap segment.
|
---|
129 | */
|
---|
130 | typedef struct KLDRHEAPSEG
|
---|
131 | {
|
---|
132 | /** The base address of the segment. */
|
---|
133 | void *pvBase;
|
---|
134 | /** The length of the segment (in bytes). */
|
---|
135 | size_t cb;
|
---|
136 | } KLDRHEAPSEG, *PKLDRHEAPSEG;
|
---|
137 |
|
---|
138 | /**
|
---|
139 | * Bundle of heap segments.
|
---|
140 | */
|
---|
141 | typedef struct KLDRHEAPSEGS
|
---|
142 | {
|
---|
143 | /** Pointer to the next segment bundle. */
|
---|
144 | struct KLDRHEAPSEGS *pNext;
|
---|
145 | /** The number of segments used. */
|
---|
146 | uint32_t cSegs;
|
---|
147 | /** Array of chunks. */
|
---|
148 | KLDRHEAPSEG aSegs[64];
|
---|
149 | } KLDRHEAPSEGS, *PKLDRHEAPSEGS;
|
---|
150 |
|
---|
151 |
|
---|
152 | /**
|
---|
153 | * Heap anchor block.
|
---|
154 | */
|
---|
155 | typedef struct KLDRHEAPANCHOR
|
---|
156 | {
|
---|
157 | /** Head of the block list. */
|
---|
158 | PKLDRHEAPBLOCK pHead;
|
---|
159 | /** Tail of the block list. */
|
---|
160 | PKLDRHEAPBLOCK pTail;
|
---|
161 | /** Head of the free list. */
|
---|
162 | PKLDRHEAPFREE pFreeHead;
|
---|
163 | /** Head segment bundle.
|
---|
164 | * The order of this list is important, but a bit peculiar.
|
---|
165 | * Logically, SegsHead::pNext is the tail pointer. */
|
---|
166 | KLDRHEAPSEGS SegsHead;
|
---|
167 | } KLDRHEAPANCHOR, *PKLDRHEAPANCHOR;
|
---|
168 |
|
---|
169 |
|
---|
170 |
|
---|
171 | /*******************************************************************************
|
---|
172 | * Global Variables *
|
---|
173 | *******************************************************************************/
|
---|
174 | /** The heap anchor block. */
|
---|
175 | static KLDRHEAPANCHOR g_Heap;
|
---|
176 |
|
---|
177 |
|
---|
178 | /*******************************************************************************
|
---|
179 | * Internal Functions *
|
---|
180 | *******************************************************************************/
|
---|
181 | static int kLdrHeapInit(PKLDRHEAPANCHOR pHeap);
|
---|
182 | static void kLdrHeapDelete(PKLDRHEAPANCHOR pHeap);
|
---|
183 | static void * kLdrHeapAlloc(PKLDRHEAPANCHOR pHeap, size_t cb);
|
---|
184 | static void kLdrHeapFree(PKLDRHEAPANCHOR pHeap, void *pv);
|
---|
185 | static void kLdrHeapDonate(PKLDRHEAPANCHOR pHeap, void *pv, size_t cb);
|
---|
186 | static int kLdrHeapSegAlloc(PKLDRHEAPSEG pSeg, size_t cb);
|
---|
187 | static void kLdrHeapSegFree(PKLDRHEAPSEG pSeg);
|
---|
188 |
|
---|
189 |
|
---|
190 | /**
|
---|
191 | * Initializes the kLdr heap.
|
---|
192 | *
|
---|
193 | * @returns 0 on success, non-zero OS specific status code on failure.
|
---|
194 | */
|
---|
195 | int kldrHlpHeapInit(void)
|
---|
196 | {
|
---|
197 | return kLdrHeapInit(&g_Heap);
|
---|
198 | }
|
---|
199 |
|
---|
200 |
|
---|
201 | /**
|
---|
202 | * Terminates the kLdr heap.
|
---|
203 | */
|
---|
204 | void kldrHlpHeapTerm(void)
|
---|
205 | {
|
---|
206 | kLdrHeapDelete(&g_Heap);
|
---|
207 | }
|
---|
208 |
|
---|
209 |
|
---|
210 | /**
|
---|
211 | * Allocates memory from the kLdr heap.
|
---|
212 | *
|
---|
213 | * @returns Pointer to the allocated heap block. NULL if we can't satify the request.
|
---|
214 | * @param cb The requested heap block size.
|
---|
215 | */
|
---|
216 | void *kldrHlpAlloc(size_t cb)
|
---|
217 | {
|
---|
218 | return kLdrHeapAlloc(&g_Heap, cb);
|
---|
219 | }
|
---|
220 |
|
---|
221 |
|
---|
222 | /**
|
---|
223 | * Frees memory allocated off the kLdr heap.
|
---|
224 | *
|
---|
225 | * @param pv Pointer to the heap block returned by kldrHlpAlloc().
|
---|
226 | */
|
---|
227 | void kldrHlpFree(void *pv)
|
---|
228 | {
|
---|
229 | kLdrHeapFree(&g_Heap, pv);
|
---|
230 | }
|
---|
231 |
|
---|
232 |
|
---|
233 | /**
|
---|
234 | * Donates memory to the heap.
|
---|
235 | *
|
---|
236 | * @param pv The address of the memory.
|
---|
237 | * @param cb The amount of memory.
|
---|
238 | */
|
---|
239 | void kldrHlpHeapDonate(void *pv, size_t cb)
|
---|
240 | {
|
---|
241 | kLdrHeapDonate(&g_Heap, pv, cb);
|
---|
242 | }
|
---|
243 |
|
---|
244 |
|
---|
245 |
|
---|
246 | /**
|
---|
247 | * Initializes the heap anchor.
|
---|
248 | *
|
---|
249 | * @returns 0 on success, non-zero on failure.
|
---|
250 | * @param pHeap The heap anchor to be initialized.
|
---|
251 | */
|
---|
252 | static int kLdrHeapInit(PKLDRHEAPANCHOR pHeap)
|
---|
253 | {
|
---|
254 | pHeap->pHead = NULL;
|
---|
255 | pHeap->pTail = NULL;
|
---|
256 | pHeap->pFreeHead = NULL;
|
---|
257 | pHeap->SegsHead.pNext = NULL;
|
---|
258 | pHeap->SegsHead.cSegs = 0;
|
---|
259 | return 0;
|
---|
260 | }
|
---|
261 |
|
---|
262 |
|
---|
263 | /**
|
---|
264 | * Deletes a heap.
|
---|
265 | * This will free all resources (memory) associated with the heap.
|
---|
266 | *
|
---|
267 | * @param pHeap The heap to be deleted.
|
---|
268 | */
|
---|
269 | static void kLdrHeapDelete(PKLDRHEAPANCHOR pHeap)
|
---|
270 | {
|
---|
271 | /*
|
---|
272 | * Free the segments, LIFO order.
|
---|
273 | * The head element is the last to be free, while the
|
---|
274 | * head.pNext is really the tail pointer - neat or what?
|
---|
275 | */
|
---|
276 | while ( pHeap->SegsHead.cSegs
|
---|
277 | || pHeap->SegsHead.pNext)
|
---|
278 | {
|
---|
279 | /* find the tail. */
|
---|
280 | uint32_t iSeg;
|
---|
281 | PKLDRHEAPSEGS pSegs = pHeap->SegsHead.pNext;
|
---|
282 | if (!pSegs)
|
---|
283 | pSegs = &pHeap->SegsHead;
|
---|
284 | else
|
---|
285 | {
|
---|
286 | pHeap->SegsHead.pNext = pSegs->pNext;
|
---|
287 | pSegs->pNext = NULL;
|
---|
288 | }
|
---|
289 |
|
---|
290 | /* free the segments */
|
---|
291 | iSeg = pSegs->cSegs;
|
---|
292 | while (iSeg-- > 0)
|
---|
293 | kLdrHeapSegFree(&pSegs->aSegs[iSeg]);
|
---|
294 | pSegs->cSegs = 0;
|
---|
295 | }
|
---|
296 |
|
---|
297 | /* Zap the anchor. */
|
---|
298 | pHeap->pHead = NULL;
|
---|
299 | pHeap->pTail = NULL;
|
---|
300 | pHeap->pFreeHead = NULL;
|
---|
301 | pHeap->SegsHead.pNext = NULL;
|
---|
302 | pHeap->SegsHead.cSegs = 0;
|
---|
303 | }
|
---|
304 |
|
---|
305 |
|
---|
306 | /**
|
---|
307 | * Internal heap block allocator.
|
---|
308 | */
|
---|
309 | static void * kldrHeapAllocSub(PKLDRHEAPANCHOR pHeap, size_t cb)
|
---|
310 | {
|
---|
311 | /*
|
---|
312 | * Find a fitting free block.
|
---|
313 | */
|
---|
314 | const size_t cbReq = KLDR_ALIGN_Z(cb + sizeof(KLDRHEAPBLOCK), KLDRHEAPBLOCK_ALIGNMENT);
|
---|
315 | PKLDRHEAPFREE pCur = pHeap->pFreeHead;
|
---|
316 | while (pCur)
|
---|
317 | {
|
---|
318 | if (pCur->Core.cb >= cbReq)
|
---|
319 | {
|
---|
320 | if (pCur->Core.cb != cbReq)
|
---|
321 | {
|
---|
322 | /* check and see if there is a better match close by. */
|
---|
323 | PKLDRHEAPFREE pCur2 = pCur->pNext;
|
---|
324 | unsigned i = 16;
|
---|
325 | while (i-- > 0 && pCur2)
|
---|
326 | {
|
---|
327 | if (pCur2->Core.cb >= cbReq)
|
---|
328 | {
|
---|
329 | if (pCur2->Core.cb == cbReq)
|
---|
330 | {
|
---|
331 | pCur = pCur2;
|
---|
332 | break;
|
---|
333 | }
|
---|
334 | if (pCur2->Core.cb < pCur->Core.cb)
|
---|
335 | pCur = pCur2;
|
---|
336 | }
|
---|
337 |
|
---|
338 | /* next */
|
---|
339 | KLDRHEAP_ASSERT_FREE(pHeap, pCur2);
|
---|
340 | pCur2 = pCur2->pNext;
|
---|
341 | }
|
---|
342 | }
|
---|
343 | break;
|
---|
344 | }
|
---|
345 |
|
---|
346 | /* next */
|
---|
347 | KLDRHEAP_ASSERT_FREE(pHeap, pCur);
|
---|
348 | pCur = pCur->pNext;
|
---|
349 | }
|
---|
350 | if (!pCur)
|
---|
351 | return NULL;
|
---|
352 | KLDRHEAP_ASSERT_FREE(pHeap, pCur);
|
---|
353 |
|
---|
354 | /*
|
---|
355 | * Do we need to split out a block?
|
---|
356 | */
|
---|
357 | if (pCur->Core.cb - cbReq >= KLDRHEAPBLOCK_ALIGNMENT * 2)
|
---|
358 | {
|
---|
359 | PKLDRHEAPBLOCK pNew;
|
---|
360 |
|
---|
361 | pCur->Core.cb -= cbReq;
|
---|
362 |
|
---|
363 | pNew = (PKLDRHEAPBLOCK)((uintptr_t)pCur + pCur->Core.cb);
|
---|
364 | pNew->fFlags = 0;
|
---|
365 | pNew->cb = cbReq;
|
---|
366 | pNew->pNext = pCur->Core.pNext;
|
---|
367 | if (pNew->pNext)
|
---|
368 | pNew->pNext->pPrev = pNew;
|
---|
369 | else
|
---|
370 | pHeap->pTail = pNew;
|
---|
371 | pNew->pPrev = &pCur->Core;
|
---|
372 | pCur->Core.pNext = pNew;
|
---|
373 |
|
---|
374 | KLDRHEAP_ASSERT_FREE(pHeap, pCur);
|
---|
375 | KLDRHEAP_ASSERT_BLOCK(pHeap, pNew);
|
---|
376 | return pNew + 1;
|
---|
377 | }
|
---|
378 |
|
---|
379 | /*
|
---|
380 | * No, just unlink it from the free list and return.
|
---|
381 | */
|
---|
382 | if (pCur->pNext)
|
---|
383 | pCur->pNext->pPrev = pCur->pPrev;
|
---|
384 | if (pCur->pPrev)
|
---|
385 | pCur->pPrev->pNext = pCur->pNext;
|
---|
386 | else
|
---|
387 | pHeap->pFreeHead = pCur->pNext;
|
---|
388 | pCur->Core.fFlags &= ~KLDRHEAPBLOCK_FLAG_FREE;
|
---|
389 |
|
---|
390 | KLDRHEAP_ASSERT_BLOCK(pHeap, &pCur->Core);
|
---|
391 | return &pCur->Core + 1;
|
---|
392 | }
|
---|
393 |
|
---|
394 |
|
---|
395 | /**
|
---|
396 | * Allocate a heap block.
|
---|
397 | *
|
---|
398 | * @returns Pointer to the allocated heap block on success. On failure NULL is returned.
|
---|
399 | * @param pHeap The heap.
|
---|
400 | * @param cb The requested heap block size.
|
---|
401 | */
|
---|
402 | static void * kLdrHeapAlloc(PKLDRHEAPANCHOR pHeap, size_t cb)
|
---|
403 | {
|
---|
404 | void *pv;
|
---|
405 |
|
---|
406 | /* adjust the requested block size. */
|
---|
407 | cb = KLDR_ALIGN_Z(cb, KLDRHEAPBLOCK_ALIGNMENT);
|
---|
408 | if (!cb)
|
---|
409 | cb = KLDRHEAPBLOCK_ALIGNMENT;
|
---|
410 |
|
---|
411 | /* try allocate the block. */
|
---|
412 | pv = kldrHeapAllocSub(pHeap, cb);
|
---|
413 | if (!pv)
|
---|
414 | {
|
---|
415 | /*
|
---|
416 | * Failed, add another segment and try again.
|
---|
417 | */
|
---|
418 | KLDRHEAPSEG Seg;
|
---|
419 | if (kLdrHeapSegAlloc(&Seg, cb + sizeof(KLDRHEAPSEGS) + sizeof(KLDRHEAPBLOCK) * 16))
|
---|
420 | return NULL;
|
---|
421 |
|
---|
422 | /* donate before insterting the segment, this makes sure we got heap to expand the segment list. */
|
---|
423 | kLdrHeapDonate(pHeap, Seg.pvBase, Seg.cb);
|
---|
424 |
|
---|
425 | /* insert the segment. */
|
---|
426 | if (pHeap->SegsHead.cSegs < sizeof(pHeap->SegsHead.aSegs) / sizeof(pHeap->SegsHead.aSegs[0]))
|
---|
427 | pHeap->SegsHead.aSegs[pHeap->SegsHead.cSegs++] = Seg;
|
---|
428 | else if ( pHeap->SegsHead.pNext
|
---|
429 | && pHeap->SegsHead.pNext->cSegs < sizeof(pHeap->SegsHead.aSegs) / sizeof(pHeap->SegsHead.aSegs[0]))
|
---|
430 | pHeap->SegsHead.pNext->aSegs[pHeap->SegsHead.pNext->cSegs++] = Seg;
|
---|
431 | else
|
---|
432 | {
|
---|
433 | PKLDRHEAPSEGS pSegs = (PKLDRHEAPSEGS)kldrHeapAllocSub(pHeap, sizeof(*pSegs));
|
---|
434 | KLDRHEAP_ASSERT(pSegs);
|
---|
435 | pSegs->pNext = pHeap->SegsHead.pNext;
|
---|
436 | pHeap->SegsHead.pNext = pSegs;
|
---|
437 | pSegs->aSegs[0] = Seg;
|
---|
438 | pSegs->cSegs = 1;
|
---|
439 | }
|
---|
440 |
|
---|
441 | /* retry (should succeed) */
|
---|
442 | pv = kldrHeapAllocSub(pHeap, cb);
|
---|
443 | KLDRHEAP_ASSERT(pv);
|
---|
444 | }
|
---|
445 |
|
---|
446 | return pv;
|
---|
447 | }
|
---|
448 |
|
---|
449 |
|
---|
450 | /**
|
---|
451 | * Frees a heap block.
|
---|
452 | *
|
---|
453 | * @param pHeap The heap.
|
---|
454 | * @param pv The pointer returned by kLdrHeapAlloc().
|
---|
455 | */
|
---|
456 | static void kLdrHeapFree(PKLDRHEAPANCHOR pHeap, void *pv)
|
---|
457 | {
|
---|
458 | PKLDRHEAPFREE pFree, pLeft, pRight;
|
---|
459 |
|
---|
460 | /* ignore NULL pointers. */
|
---|
461 | if (!pv)
|
---|
462 | return;
|
---|
463 |
|
---|
464 | pFree = (PKLDRHEAPFREE)((PKLDRHEAPBLOCK)pv - 1);
|
---|
465 | KLDRHEAP_ASSERT_BLOCK(pHeap, &pFree->Core);
|
---|
466 | KLDRHEAP_ASSERT(KLDRHEAPBLOCK_IS_ALLOCATED(&pFree->Core));
|
---|
467 |
|
---|
468 | /*
|
---|
469 | * Merge or link with left node?
|
---|
470 | */
|
---|
471 | pLeft = (PKLDRHEAPFREE)pFree->Core.pPrev;
|
---|
472 | if ( pLeft
|
---|
473 | && KLDRHEAPBLOCK_IS_FREE(&pLeft->Core)
|
---|
474 | && KLDRHEAPBLOCK_IS_ADJACENT(&pLeft->Core, &pFree->Core)
|
---|
475 | )
|
---|
476 | {
|
---|
477 | /* merge left */
|
---|
478 | pLeft->Core.pNext = pFree->Core.pNext;
|
---|
479 | if (pFree->Core.pNext)
|
---|
480 | pFree->Core.pNext->pPrev = &pLeft->Core;
|
---|
481 | else
|
---|
482 | pHeap->pTail = &pLeft->Core;
|
---|
483 |
|
---|
484 | pLeft->Core.cb += pFree->Core.cb;
|
---|
485 | pFree->Core.fFlags = ~0;
|
---|
486 | pFree = pLeft;
|
---|
487 | }
|
---|
488 | else
|
---|
489 | {
|
---|
490 | /* link left */
|
---|
491 | while (pLeft && !KLDRHEAPBLOCK_IS_FREE(&pLeft->Core))
|
---|
492 | pLeft = (PKLDRHEAPFREE)pLeft->Core.pPrev;
|
---|
493 | if (pLeft)
|
---|
494 | {
|
---|
495 | pFree->pPrev = pLeft;
|
---|
496 | pFree->pNext = pLeft->pNext;
|
---|
497 | if (pLeft->pNext)
|
---|
498 | pLeft->pNext->pPrev = pFree;
|
---|
499 | pLeft->pNext = pFree;
|
---|
500 | }
|
---|
501 | else
|
---|
502 | {
|
---|
503 | pFree->pPrev = NULL;
|
---|
504 | pFree->pNext = pHeap->pFreeHead;
|
---|
505 | if (pHeap->pFreeHead)
|
---|
506 | pHeap->pFreeHead->pPrev = pFree;
|
---|
507 | pHeap->pFreeHead = pFree;
|
---|
508 | }
|
---|
509 | pFree->Core.fFlags |= KLDRHEAPBLOCK_FLAG_FREE;
|
---|
510 | }
|
---|
511 | KLDRHEAP_ASSERT_FREE(pHeap, pFree);
|
---|
512 |
|
---|
513 | /*
|
---|
514 | * Merge right?
|
---|
515 | */
|
---|
516 | pRight = (PKLDRHEAPFREE)pFree->Core.pNext;
|
---|
517 | if ( pRight
|
---|
518 | && KLDRHEAPBLOCK_IS_FREE(&pRight->Core)
|
---|
519 | && KLDRHEAPBLOCK_IS_ADJACENT(&pFree->Core, pRight)
|
---|
520 | )
|
---|
521 | {
|
---|
522 | /* unlink pRight from the global list. */
|
---|
523 | pFree->Core.pNext = pRight->Core.pNext;
|
---|
524 | if (pRight->Core.pNext)
|
---|
525 | pRight->Core.pNext->pPrev = &pFree->Core;
|
---|
526 | else
|
---|
527 | pHeap->pTail = &pFree->Core;
|
---|
528 |
|
---|
529 | /* unlink pRight from the free list. */
|
---|
530 | pFree->pNext = pRight->pNext;
|
---|
531 | if (pRight->pNext)
|
---|
532 | pRight->pNext->pPrev = pFree;
|
---|
533 |
|
---|
534 | /* update size and invalidate pRight. */
|
---|
535 | pFree->Core.cb += pRight->Core.cb;
|
---|
536 | pRight->Core.fFlags = ~0;
|
---|
537 | }
|
---|
538 | }
|
---|
539 |
|
---|
540 |
|
---|
541 | /**
|
---|
542 | * Donates memory to the heap.
|
---|
543 | *
|
---|
544 | * The donated memory is returned to the donator when the heap is deleted.
|
---|
545 | *
|
---|
546 | * @param pHeap The heap
|
---|
547 | * @param pv The pointer to the donated memory.
|
---|
548 | * @param cb Size of the donated memory.
|
---|
549 | */
|
---|
550 | static void kLdrHeapDonate(PKLDRHEAPANCHOR pHeap, void *pv, size_t cb)
|
---|
551 | {
|
---|
552 | PKLDRHEAPBLOCK pBlock;
|
---|
553 |
|
---|
554 | /*
|
---|
555 | * Don't bother with small donations.
|
---|
556 | */
|
---|
557 | if (cb < KLDRHEAPBLOCK_ALIGNMENT * 4)
|
---|
558 | return;
|
---|
559 |
|
---|
560 | /*
|
---|
561 | * Align the donation on a heap block boundrary.
|
---|
562 | */
|
---|
563 | if ((uintptr_t)pv & (KLDRHEAPBLOCK_ALIGNMENT - 1))
|
---|
564 | {
|
---|
565 | cb -= (uintptr_t)pv & 31;
|
---|
566 | pv = KLDR_ALIGN_P(pv, KLDRHEAPBLOCK_ALIGNMENT);
|
---|
567 | }
|
---|
568 | cb &= ~(size_t)(KLDRHEAPBLOCK_ALIGNMENT - 1);
|
---|
569 |
|
---|
570 | /*
|
---|
571 | * Create an allocated block, link it and free it.
|
---|
572 | */
|
---|
573 | pBlock = (PKLDRHEAPBLOCK)pv;
|
---|
574 | pBlock->pNext = NULL;
|
---|
575 | pBlock->pPrev = NULL;
|
---|
576 | pBlock->cb = cb;
|
---|
577 | pBlock->fFlags = 0;
|
---|
578 |
|
---|
579 | /* insert */
|
---|
580 | if ((uintptr_t)pBlock < (uintptr_t)pHeap->pHead)
|
---|
581 | {
|
---|
582 | /* head */
|
---|
583 | pBlock->pNext = pHeap->pHead;
|
---|
584 | pHeap->pHead->pPrev = pBlock;
|
---|
585 | pHeap->pHead = pBlock;
|
---|
586 | }
|
---|
587 | else if ((uintptr_t)pBlock > (uintptr_t)pHeap->pTail)
|
---|
588 | {
|
---|
589 | if (pHeap->pTail)
|
---|
590 | {
|
---|
591 | /* tail */
|
---|
592 | pBlock->pPrev = pHeap->pTail;
|
---|
593 | pHeap->pTail->pNext = pBlock;
|
---|
594 | pHeap->pTail = pBlock;
|
---|
595 | }
|
---|
596 | else
|
---|
597 | {
|
---|
598 | /* first */
|
---|
599 | pHeap->pHead = pBlock;
|
---|
600 | pHeap->pTail = pBlock;
|
---|
601 | }
|
---|
602 | }
|
---|
603 | else
|
---|
604 | {
|
---|
605 | /* in list (unlikely) */
|
---|
606 | PKLDRHEAPBLOCK pPrev = pHeap->pHead;
|
---|
607 | PKLDRHEAPBLOCK pCur = pPrev->pNext;
|
---|
608 | for (;;)
|
---|
609 | {
|
---|
610 | KLDRHEAP_ASSERT_BLOCK(pHeap, pCur);
|
---|
611 | if ((uintptr_t)pCur > (uintptr_t)pBlock)
|
---|
612 | break;
|
---|
613 | pPrev = pCur;
|
---|
614 | pCur = pCur->pNext;
|
---|
615 | }
|
---|
616 |
|
---|
617 | pBlock->pNext = pCur;
|
---|
618 | pBlock->pPrev = pPrev;
|
---|
619 | pPrev->pNext = pBlock;
|
---|
620 | pCur->pPrev = pBlock;
|
---|
621 | }
|
---|
622 | KLDRHEAP_ASSERT_BLOCK(pHeap, pBlock);
|
---|
623 |
|
---|
624 | /* free it */
|
---|
625 | kLdrHeapFree(pHeap, pBlock + 1);
|
---|
626 | }
|
---|
627 |
|
---|
628 |
|
---|
629 |
|
---|
630 | /**
|
---|
631 | * Allocates a new segment.
|
---|
632 | *
|
---|
633 | * @returns 0 on success, non-zero OS status code on failure.
|
---|
634 | * @param pSeg Where to put the info about the allocated segment.
|
---|
635 | * @param cbMin The minimum segment size.
|
---|
636 | */
|
---|
637 | static int kLdrHeapSegAlloc(PKLDRHEAPSEG pSeg, size_t cbMin)
|
---|
638 | {
|
---|
639 | #ifdef __OS2__
|
---|
640 | APIRET rc;
|
---|
641 |
|
---|
642 | pSeg->cb = (cbMin + 0xffff) & ~(size_t)0xffff;
|
---|
643 | pSeg->pvBase = NULL;
|
---|
644 | rc = DosAllocMem(&pSeg->pvBase, pSeg->cb, PAG_COMMIT | PAG_READ | PAG_WRITE | OBJ_ANY);
|
---|
645 | if (rc == ERROR_INVALID_PARAMETER)
|
---|
646 | rc = DosAllocMem(&pSeg->pvBase, pSeg->cb, PAG_COMMIT | PAG_READ | PAG_WRITE);
|
---|
647 | if (rc)
|
---|
648 | {
|
---|
649 | pSeg->pvBase = NULL;
|
---|
650 | pSeg->cb = 0;
|
---|
651 | return rc;
|
---|
652 | }
|
---|
653 |
|
---|
654 | #elif defined(__WIN__)
|
---|
655 | pSeg->cb = (cbMin + 0xffff) & ~(size_t)0xffff;
|
---|
656 | pSeg->pvBase = VirtualAlloc(NULL, pSeg->cb, MEM_COMMIT, PAGE_READWRITE);
|
---|
657 | if (!pSeg->pvBase)
|
---|
658 | {
|
---|
659 | pSeg->cb = 0;
|
---|
660 | return GetLastError();
|
---|
661 | }
|
---|
662 |
|
---|
663 | #else
|
---|
664 | # error "Port me"
|
---|
665 | #endif
|
---|
666 |
|
---|
667 | return 0;
|
---|
668 | }
|
---|
669 |
|
---|
670 |
|
---|
671 | /**
|
---|
672 | * Frees a segment.
|
---|
673 | *
|
---|
674 | * @param pSeg The segment to be freed.
|
---|
675 | */
|
---|
676 | static void kLdrHeapSegFree(PKLDRHEAPSEG pSeg)
|
---|
677 | {
|
---|
678 | #ifdef __OS2__
|
---|
679 | APIRET rc = DosFreeMem(pSeg->pvBase);
|
---|
680 | KLDRHEAP_ASSERT(!rc); (void)rc;
|
---|
681 |
|
---|
682 | #elif defined(__WIN__)
|
---|
683 | BOOL fRc = VirtualFree(pSeg->pvBase, 0 /*pSeg->cb*/, MEM_RELEASE);
|
---|
684 | KLDRHEAP_ASSERT(fRc); (void)fRc;
|
---|
685 |
|
---|
686 | #else
|
---|
687 | # error "Port me"
|
---|
688 | #endif
|
---|
689 | }
|
---|
690 |
|
---|