| 1 | /* $Id: kLdrHlpHeap.c 2847 2006-11-01 19:17:21Z 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 |  * Allocates zero initialized memory from the kLdr heap.
 | 
|---|
| 224 |  *
 | 
|---|
| 225 |  * @returns Pointer to the allocated heap block. NULL if we can't satify the request.
 | 
|---|
| 226 |  * @param   cb      The requested heap block size.
 | 
|---|
| 227 |  */
 | 
|---|
| 228 | void *kldrHlpAllocZ(size_t cb)
 | 
|---|
| 229 | {
 | 
|---|
| 230 |     void *pv = kLdrHeapAlloc(&g_Heap, cb);
 | 
|---|
| 231 |     if (pv)
 | 
|---|
| 232 |         kLdrHlpMemSet(pv, 0, cb);
 | 
|---|
| 233 |     return pv;
 | 
|---|
| 234 | }
 | 
|---|
| 235 | 
 | 
|---|
| 236 | 
 | 
|---|
| 237 | /**
 | 
|---|
| 238 |  * Frees memory allocated off the kLdr heap.
 | 
|---|
| 239 |  *
 | 
|---|
| 240 |  * @param   pv      Pointer to the heap block returned by kldrHlpAlloc().
 | 
|---|
| 241 |  */
 | 
|---|
| 242 | void kldrHlpFree(void *pv)
 | 
|---|
| 243 | {
 | 
|---|
| 244 |     kLdrHeapFree(&g_Heap, pv);
 | 
|---|
| 245 | }
 | 
|---|
| 246 | 
 | 
|---|
| 247 | 
 | 
|---|
| 248 | /**
 | 
|---|
| 249 |  * Donates memory to the heap.
 | 
|---|
| 250 |  *
 | 
|---|
| 251 |  * @param   pv      The address of the memory.
 | 
|---|
| 252 |  * @param   cb      The amount of memory.
 | 
|---|
| 253 |  */
 | 
|---|
| 254 | void kldrHlpHeapDonate(void *pv, size_t cb)
 | 
|---|
| 255 | {
 | 
|---|
| 256 |     kLdrHeapDonate(&g_Heap, pv, cb);
 | 
|---|
| 257 | }
 | 
|---|
| 258 | 
 | 
|---|
| 259 | 
 | 
|---|
| 260 | 
 | 
|---|
| 261 | /**
 | 
|---|
| 262 |  * Initializes the heap anchor.
 | 
|---|
| 263 |  *
 | 
|---|
| 264 |  * @returns 0 on success, non-zero on failure.
 | 
|---|
| 265 |  * @param   pHeap   The heap anchor to be initialized.
 | 
|---|
| 266 |  */
 | 
|---|
| 267 | static int kLdrHeapInit(PKLDRHEAPANCHOR pHeap)
 | 
|---|
| 268 | {
 | 
|---|
| 269 |     pHeap->pHead = NULL;
 | 
|---|
| 270 |     pHeap->pTail = NULL;
 | 
|---|
| 271 |     pHeap->pFreeHead = NULL;
 | 
|---|
| 272 |     pHeap->SegsHead.pNext = NULL;
 | 
|---|
| 273 |     pHeap->SegsHead.cSegs = 0;
 | 
|---|
| 274 |     return 0;
 | 
|---|
| 275 | }
 | 
|---|
| 276 | 
 | 
|---|
| 277 | 
 | 
|---|
| 278 | /**
 | 
|---|
| 279 |  * Deletes a heap.
 | 
|---|
| 280 |  * This will free all resources (memory) associated with the heap.
 | 
|---|
| 281 |  *
 | 
|---|
| 282 |  * @param   pHeap   The heap to be deleted.
 | 
|---|
| 283 |  */
 | 
|---|
| 284 | static void kLdrHeapDelete(PKLDRHEAPANCHOR pHeap)
 | 
|---|
| 285 | {
 | 
|---|
| 286 |     /*
 | 
|---|
| 287 |      * Free the segments, LIFO order.
 | 
|---|
| 288 |      * The head element is the last to be free, while the
 | 
|---|
| 289 |      * head.pNext is really the tail pointer - neat or what?
 | 
|---|
| 290 |      */
 | 
|---|
| 291 |     while (     pHeap->SegsHead.cSegs
 | 
|---|
| 292 |            ||   pHeap->SegsHead.pNext)
 | 
|---|
| 293 |     {
 | 
|---|
| 294 |         /* find the tail. */
 | 
|---|
| 295 |         uint32_t        iSeg;
 | 
|---|
| 296 |         PKLDRHEAPSEGS   pSegs = pHeap->SegsHead.pNext;
 | 
|---|
| 297 |         if (!pSegs)
 | 
|---|
| 298 |             pSegs = &pHeap->SegsHead;
 | 
|---|
| 299 |         else
 | 
|---|
| 300 |         {
 | 
|---|
| 301 |             pHeap->SegsHead.pNext = pSegs->pNext;
 | 
|---|
| 302 |             pSegs->pNext = NULL;
 | 
|---|
| 303 |         }
 | 
|---|
| 304 | 
 | 
|---|
| 305 |         /* free the segments */
 | 
|---|
| 306 |         iSeg = pSegs->cSegs;
 | 
|---|
| 307 |         while (iSeg-- > 0)
 | 
|---|
| 308 |             kLdrHeapSegFree(&pSegs->aSegs[iSeg]);
 | 
|---|
| 309 |         pSegs->cSegs = 0;
 | 
|---|
| 310 |     }
 | 
|---|
| 311 | 
 | 
|---|
| 312 |     /* Zap the anchor. */
 | 
|---|
| 313 |     pHeap->pHead = NULL;
 | 
|---|
| 314 |     pHeap->pTail = NULL;
 | 
|---|
| 315 |     pHeap->pFreeHead = NULL;
 | 
|---|
| 316 |     pHeap->SegsHead.pNext = NULL;
 | 
|---|
| 317 |     pHeap->SegsHead.cSegs = 0;
 | 
|---|
| 318 | }
 | 
|---|
| 319 | 
 | 
|---|
| 320 | 
 | 
|---|
| 321 | /**
 | 
|---|
| 322 |  * Internal heap block allocator.
 | 
|---|
| 323 |  */
 | 
|---|
| 324 | static void *   kldrHeapAllocSub(PKLDRHEAPANCHOR pHeap, size_t cb)
 | 
|---|
| 325 | {
 | 
|---|
| 326 |     /*
 | 
|---|
| 327 |      * Find a fitting free block.
 | 
|---|
| 328 |      */
 | 
|---|
| 329 |     const size_t    cbReq = KLDR_ALIGN_Z(cb + sizeof(KLDRHEAPBLOCK), KLDRHEAPBLOCK_ALIGNMENT);
 | 
|---|
| 330 |     PKLDRHEAPFREE   pCur = pHeap->pFreeHead;
 | 
|---|
| 331 |     while (pCur)
 | 
|---|
| 332 |     {
 | 
|---|
| 333 |         if (pCur->Core.cb >= cbReq)
 | 
|---|
| 334 |         {
 | 
|---|
| 335 |             if (pCur->Core.cb != cbReq)
 | 
|---|
| 336 |             {
 | 
|---|
| 337 |                 /* check and see if there is a better match close by. */
 | 
|---|
| 338 |                 PKLDRHEAPFREE pCur2 = pCur->pNext;
 | 
|---|
| 339 |                 unsigned i = 16;
 | 
|---|
| 340 |                 while (i-- > 0 && pCur2)
 | 
|---|
| 341 |                 {
 | 
|---|
| 342 |                     if (pCur2->Core.cb >= cbReq)
 | 
|---|
| 343 |                     {
 | 
|---|
| 344 |                         if (pCur2->Core.cb == cbReq)
 | 
|---|
| 345 |                         {
 | 
|---|
| 346 |                             pCur = pCur2;
 | 
|---|
| 347 |                             break;
 | 
|---|
| 348 |                         }
 | 
|---|
| 349 |                         if (pCur2->Core.cb < pCur->Core.cb)
 | 
|---|
| 350 |                             pCur = pCur2;
 | 
|---|
| 351 |                     }
 | 
|---|
| 352 | 
 | 
|---|
| 353 |                     /* next */
 | 
|---|
| 354 |                     KLDRHEAP_ASSERT_FREE(pHeap, pCur2);
 | 
|---|
| 355 |                     pCur2 = pCur2->pNext;
 | 
|---|
| 356 |                 }
 | 
|---|
| 357 |             }
 | 
|---|
| 358 |             break;
 | 
|---|
| 359 |         }
 | 
|---|
| 360 | 
 | 
|---|
| 361 |         /* next */
 | 
|---|
| 362 |         KLDRHEAP_ASSERT_FREE(pHeap, pCur);
 | 
|---|
| 363 |         pCur = pCur->pNext;
 | 
|---|
| 364 |     }
 | 
|---|
| 365 |     if (!pCur)
 | 
|---|
| 366 |         return NULL;
 | 
|---|
| 367 |     KLDRHEAP_ASSERT_FREE(pHeap, pCur);
 | 
|---|
| 368 | 
 | 
|---|
| 369 |     /*
 | 
|---|
| 370 |      * Do we need to split out a block?
 | 
|---|
| 371 |      */
 | 
|---|
| 372 |     if (pCur->Core.cb - cbReq >= KLDRHEAPBLOCK_ALIGNMENT * 2)
 | 
|---|
| 373 |     {
 | 
|---|
| 374 |         PKLDRHEAPBLOCK pNew;
 | 
|---|
| 375 | 
 | 
|---|
| 376 |         pCur->Core.cb -= cbReq;
 | 
|---|
| 377 | 
 | 
|---|
| 378 |         pNew = (PKLDRHEAPBLOCK)((uintptr_t)pCur + pCur->Core.cb);
 | 
|---|
| 379 |         pNew->fFlags = 0;
 | 
|---|
| 380 |         pNew->cb = cbReq;
 | 
|---|
| 381 |         pNew->pNext = pCur->Core.pNext;
 | 
|---|
| 382 |         if (pNew->pNext)
 | 
|---|
| 383 |             pNew->pNext->pPrev = pNew;
 | 
|---|
| 384 |         else
 | 
|---|
| 385 |             pHeap->pTail = pNew;
 | 
|---|
| 386 |         pNew->pPrev = &pCur->Core;
 | 
|---|
| 387 |         pCur->Core.pNext = pNew;
 | 
|---|
| 388 | 
 | 
|---|
| 389 |         KLDRHEAP_ASSERT_FREE(pHeap, pCur);
 | 
|---|
| 390 |         KLDRHEAP_ASSERT_BLOCK(pHeap, pNew);
 | 
|---|
| 391 |         return pNew + 1;
 | 
|---|
| 392 |     }
 | 
|---|
| 393 | 
 | 
|---|
| 394 |     /*
 | 
|---|
| 395 |      * No, just unlink it from the free list and return.
 | 
|---|
| 396 |      */
 | 
|---|
| 397 |     if (pCur->pNext)
 | 
|---|
| 398 |         pCur->pNext->pPrev = pCur->pPrev;
 | 
|---|
| 399 |     if (pCur->pPrev)
 | 
|---|
| 400 |         pCur->pPrev->pNext = pCur->pNext;
 | 
|---|
| 401 |     else
 | 
|---|
| 402 |         pHeap->pFreeHead = pCur->pNext;
 | 
|---|
| 403 |     pCur->Core.fFlags &= ~KLDRHEAPBLOCK_FLAG_FREE;
 | 
|---|
| 404 | 
 | 
|---|
| 405 |     KLDRHEAP_ASSERT_BLOCK(pHeap, &pCur->Core);
 | 
|---|
| 406 |     return &pCur->Core + 1;
 | 
|---|
| 407 | }
 | 
|---|
| 408 | 
 | 
|---|
| 409 | 
 | 
|---|
| 410 | /**
 | 
|---|
| 411 |  * Allocate a heap block.
 | 
|---|
| 412 |  *
 | 
|---|
| 413 |  * @returns Pointer to the allocated heap block on success. On failure NULL is returned.
 | 
|---|
| 414 |  * @param   pHeap   The heap.
 | 
|---|
| 415 |  * @param   cb      The requested heap block size.
 | 
|---|
| 416 |  */
 | 
|---|
| 417 | static void *   kLdrHeapAlloc(PKLDRHEAPANCHOR pHeap, size_t cb)
 | 
|---|
| 418 | {
 | 
|---|
| 419 |     void *pv;
 | 
|---|
| 420 | 
 | 
|---|
| 421 |     /* adjust the requested block size. */
 | 
|---|
| 422 |     cb = KLDR_ALIGN_Z(cb, KLDRHEAPBLOCK_ALIGNMENT);
 | 
|---|
| 423 |     if (!cb)
 | 
|---|
| 424 |         cb = KLDRHEAPBLOCK_ALIGNMENT;
 | 
|---|
| 425 | 
 | 
|---|
| 426 |     /* try allocate the block. */
 | 
|---|
| 427 |     pv = kldrHeapAllocSub(pHeap, cb);
 | 
|---|
| 428 |     if (!pv)
 | 
|---|
| 429 |     {
 | 
|---|
| 430 |         /*
 | 
|---|
| 431 |          * Failed, add another segment and try again.
 | 
|---|
| 432 |          */
 | 
|---|
| 433 |         KLDRHEAPSEG Seg;
 | 
|---|
| 434 |         if (kLdrHeapSegAlloc(&Seg, cb + sizeof(KLDRHEAPSEGS) + sizeof(KLDRHEAPBLOCK) * 16))
 | 
|---|
| 435 |             return NULL;
 | 
|---|
| 436 | 
 | 
|---|
| 437 |         /* donate before insterting the segment, this makes sure we got heap to expand the segment list. */
 | 
|---|
| 438 |         kLdrHeapDonate(pHeap, Seg.pvBase, Seg.cb);
 | 
|---|
| 439 | 
 | 
|---|
| 440 |         /* insert the segment. */
 | 
|---|
| 441 |         if (pHeap->SegsHead.cSegs < sizeof(pHeap->SegsHead.aSegs) / sizeof(pHeap->SegsHead.aSegs[0]))
 | 
|---|
| 442 |             pHeap->SegsHead.aSegs[pHeap->SegsHead.cSegs++] = Seg;
 | 
|---|
| 443 |         else if (   pHeap->SegsHead.pNext
 | 
|---|
| 444 |                  && pHeap->SegsHead.pNext->cSegs < sizeof(pHeap->SegsHead.aSegs) / sizeof(pHeap->SegsHead.aSegs[0]))
 | 
|---|
| 445 |             pHeap->SegsHead.pNext->aSegs[pHeap->SegsHead.pNext->cSegs++] = Seg;
 | 
|---|
| 446 |         else
 | 
|---|
| 447 |         {
 | 
|---|
| 448 |             PKLDRHEAPSEGS pSegs = (PKLDRHEAPSEGS)kldrHeapAllocSub(pHeap, sizeof(*pSegs));
 | 
|---|
| 449 |             KLDRHEAP_ASSERT(pSegs);
 | 
|---|
| 450 |             pSegs->pNext = pHeap->SegsHead.pNext;
 | 
|---|
| 451 |             pHeap->SegsHead.pNext = pSegs;
 | 
|---|
| 452 |             pSegs->aSegs[0] = Seg;
 | 
|---|
| 453 |             pSegs->cSegs = 1;
 | 
|---|
| 454 |         }
 | 
|---|
| 455 | 
 | 
|---|
| 456 |         /* retry (should succeed) */
 | 
|---|
| 457 |         pv = kldrHeapAllocSub(pHeap, cb);
 | 
|---|
| 458 |         KLDRHEAP_ASSERT(pv);
 | 
|---|
| 459 |     }
 | 
|---|
| 460 | 
 | 
|---|
| 461 |     return pv;
 | 
|---|
| 462 | }
 | 
|---|
| 463 | 
 | 
|---|
| 464 | 
 | 
|---|
| 465 | /**
 | 
|---|
| 466 |  * Frees a heap block.
 | 
|---|
| 467 |  *
 | 
|---|
| 468 |  * @param   pHeap   The heap.
 | 
|---|
| 469 |  * @param   pv      The pointer returned by kLdrHeapAlloc().
 | 
|---|
| 470 |  */
 | 
|---|
| 471 | static void     kLdrHeapFree(PKLDRHEAPANCHOR pHeap, void *pv)
 | 
|---|
| 472 | {
 | 
|---|
| 473 |     PKLDRHEAPFREE pFree, pLeft, pRight;
 | 
|---|
| 474 | 
 | 
|---|
| 475 |     /* ignore NULL pointers. */
 | 
|---|
| 476 |     if (!pv)
 | 
|---|
| 477 |         return;
 | 
|---|
| 478 | 
 | 
|---|
| 479 |     pFree = (PKLDRHEAPFREE)((PKLDRHEAPBLOCK)pv - 1);
 | 
|---|
| 480 |     KLDRHEAP_ASSERT_BLOCK(pHeap, &pFree->Core);
 | 
|---|
| 481 |     KLDRHEAP_ASSERT(KLDRHEAPBLOCK_IS_ALLOCATED(&pFree->Core));
 | 
|---|
| 482 | 
 | 
|---|
| 483 |     /*
 | 
|---|
| 484 |      * Merge or link with left node?
 | 
|---|
| 485 |      */
 | 
|---|
| 486 |     pLeft = (PKLDRHEAPFREE)pFree->Core.pPrev;
 | 
|---|
| 487 |     if (    pLeft
 | 
|---|
| 488 |         &&  KLDRHEAPBLOCK_IS_FREE(&pLeft->Core)
 | 
|---|
| 489 |         &&  KLDRHEAPBLOCK_IS_ADJACENT(&pLeft->Core, &pFree->Core)
 | 
|---|
| 490 |        )
 | 
|---|
| 491 |     {
 | 
|---|
| 492 |         /* merge left */
 | 
|---|
| 493 |         pLeft->Core.pNext = pFree->Core.pNext;
 | 
|---|
| 494 |         if (pFree->Core.pNext)
 | 
|---|
| 495 |             pFree->Core.pNext->pPrev = &pLeft->Core;
 | 
|---|
| 496 |         else
 | 
|---|
| 497 |             pHeap->pTail = &pLeft->Core;
 | 
|---|
| 498 | 
 | 
|---|
| 499 |         pLeft->Core.cb += pFree->Core.cb;
 | 
|---|
| 500 |         pFree->Core.fFlags = ~0;
 | 
|---|
| 501 |         pFree = pLeft;
 | 
|---|
| 502 |     }
 | 
|---|
| 503 |     else
 | 
|---|
| 504 |     {
 | 
|---|
| 505 |         /* link left */
 | 
|---|
| 506 |         while (pLeft && !KLDRHEAPBLOCK_IS_FREE(&pLeft->Core))
 | 
|---|
| 507 |             pLeft = (PKLDRHEAPFREE)pLeft->Core.pPrev;
 | 
|---|
| 508 |         if (pLeft)
 | 
|---|
| 509 |         {
 | 
|---|
| 510 |             pFree->pPrev = pLeft;
 | 
|---|
| 511 |             pFree->pNext = pLeft->pNext;
 | 
|---|
| 512 |             if (pLeft->pNext)
 | 
|---|
| 513 |                 pLeft->pNext->pPrev = pFree;
 | 
|---|
| 514 |             pLeft->pNext  = pFree;
 | 
|---|
| 515 |         }
 | 
|---|
| 516 |         else
 | 
|---|
| 517 |         {
 | 
|---|
| 518 |             pFree->pPrev = NULL;
 | 
|---|
| 519 |             pFree->pNext = pHeap->pFreeHead;
 | 
|---|
| 520 |             if (pHeap->pFreeHead)
 | 
|---|
| 521 |                 pHeap->pFreeHead->pPrev = pFree;
 | 
|---|
| 522 |             pHeap->pFreeHead = pFree;
 | 
|---|
| 523 |         }
 | 
|---|
| 524 |         pFree->Core.fFlags |= KLDRHEAPBLOCK_FLAG_FREE;
 | 
|---|
| 525 |     }
 | 
|---|
| 526 |     KLDRHEAP_ASSERT_FREE(pHeap, pFree);
 | 
|---|
| 527 | 
 | 
|---|
| 528 |     /*
 | 
|---|
| 529 |      * Merge right?
 | 
|---|
| 530 |      */
 | 
|---|
| 531 |     pRight = (PKLDRHEAPFREE)pFree->Core.pNext;
 | 
|---|
| 532 |     if (    pRight
 | 
|---|
| 533 |         &&  KLDRHEAPBLOCK_IS_FREE(&pRight->Core)
 | 
|---|
| 534 |         &&  KLDRHEAPBLOCK_IS_ADJACENT(&pFree->Core, pRight)
 | 
|---|
| 535 |        )
 | 
|---|
| 536 |     {
 | 
|---|
| 537 |         /* unlink pRight from the global list. */
 | 
|---|
| 538 |         pFree->Core.pNext = pRight->Core.pNext;
 | 
|---|
| 539 |         if (pRight->Core.pNext)
 | 
|---|
| 540 |             pRight->Core.pNext->pPrev = &pFree->Core;
 | 
|---|
| 541 |         else
 | 
|---|
| 542 |             pHeap->pTail = &pFree->Core;
 | 
|---|
| 543 | 
 | 
|---|
| 544 |         /* unlink pRight from the free list. */
 | 
|---|
| 545 |         pFree->pNext = pRight->pNext;
 | 
|---|
| 546 |         if (pRight->pNext)
 | 
|---|
| 547 |             pRight->pNext->pPrev = pFree;
 | 
|---|
| 548 | 
 | 
|---|
| 549 |         /* update size and invalidate pRight. */
 | 
|---|
| 550 |         pFree->Core.cb += pRight->Core.cb;
 | 
|---|
| 551 |         pRight->Core.fFlags = ~0;
 | 
|---|
| 552 |     }
 | 
|---|
| 553 | }
 | 
|---|
| 554 | 
 | 
|---|
| 555 | 
 | 
|---|
| 556 | /**
 | 
|---|
| 557 |  * Donates memory to the heap.
 | 
|---|
| 558 |  *
 | 
|---|
| 559 |  * The donated memory is returned to the donator when the heap is deleted.
 | 
|---|
| 560 |  *
 | 
|---|
| 561 |  * @param pHeap The heap
 | 
|---|
| 562 |  * @param pv    The pointer to the donated memory.
 | 
|---|
| 563 |  * @param cb    Size of the donated memory.
 | 
|---|
| 564 |  */
 | 
|---|
| 565 | static void     kLdrHeapDonate(PKLDRHEAPANCHOR pHeap, void *pv, size_t cb)
 | 
|---|
| 566 | {
 | 
|---|
| 567 |     PKLDRHEAPBLOCK pBlock;
 | 
|---|
| 568 | 
 | 
|---|
| 569 |     /*
 | 
|---|
| 570 |      * Don't bother with small donations.
 | 
|---|
| 571 |      */
 | 
|---|
| 572 |     if (cb < KLDRHEAPBLOCK_ALIGNMENT * 4)
 | 
|---|
| 573 |         return;
 | 
|---|
| 574 | 
 | 
|---|
| 575 |     /*
 | 
|---|
| 576 |      * Align the donation on a heap block boundrary.
 | 
|---|
| 577 |      */
 | 
|---|
| 578 |     if ((uintptr_t)pv & (KLDRHEAPBLOCK_ALIGNMENT - 1))
 | 
|---|
| 579 |     {
 | 
|---|
| 580 |         cb -= (uintptr_t)pv & 31;
 | 
|---|
| 581 |         pv = KLDR_ALIGN_P(pv, KLDRHEAPBLOCK_ALIGNMENT);
 | 
|---|
| 582 |     }
 | 
|---|
| 583 |     cb &= ~(size_t)(KLDRHEAPBLOCK_ALIGNMENT - 1);
 | 
|---|
| 584 | 
 | 
|---|
| 585 |     /*
 | 
|---|
| 586 |      * Create an allocated block, link it and free it.
 | 
|---|
| 587 |      */
 | 
|---|
| 588 |     pBlock = (PKLDRHEAPBLOCK)pv;
 | 
|---|
| 589 |     pBlock->pNext = NULL;
 | 
|---|
| 590 |     pBlock->pPrev = NULL;
 | 
|---|
| 591 |     pBlock->cb = cb;
 | 
|---|
| 592 |     pBlock->fFlags = 0;
 | 
|---|
| 593 | 
 | 
|---|
| 594 |     /* insert */
 | 
|---|
| 595 |     if ((uintptr_t)pBlock < (uintptr_t)pHeap->pHead)
 | 
|---|
| 596 |     {
 | 
|---|
| 597 |         /* head */
 | 
|---|
| 598 |         pBlock->pNext = pHeap->pHead;
 | 
|---|
| 599 |         pHeap->pHead->pPrev = pBlock;
 | 
|---|
| 600 |         pHeap->pHead = pBlock;
 | 
|---|
| 601 |     }
 | 
|---|
| 602 |     else if ((uintptr_t)pBlock > (uintptr_t)pHeap->pTail)
 | 
|---|
| 603 |     {
 | 
|---|
| 604 |         if (pHeap->pTail)
 | 
|---|
| 605 |         {
 | 
|---|
| 606 |             /* tail */
 | 
|---|
| 607 |             pBlock->pPrev = pHeap->pTail;
 | 
|---|
| 608 |             pHeap->pTail->pNext = pBlock;
 | 
|---|
| 609 |             pHeap->pTail = pBlock;
 | 
|---|
| 610 |         }
 | 
|---|
| 611 |         else
 | 
|---|
| 612 |         {
 | 
|---|
| 613 |             /* first */
 | 
|---|
| 614 |             pHeap->pHead = pBlock;
 | 
|---|
| 615 |             pHeap->pTail = pBlock;
 | 
|---|
| 616 |         }
 | 
|---|
| 617 |     }
 | 
|---|
| 618 |     else
 | 
|---|
| 619 |     {
 | 
|---|
| 620 |         /* in list (unlikely) */
 | 
|---|
| 621 |         PKLDRHEAPBLOCK pPrev = pHeap->pHead;
 | 
|---|
| 622 |         PKLDRHEAPBLOCK pCur = pPrev->pNext;
 | 
|---|
| 623 |         for (;;)
 | 
|---|
| 624 |         {
 | 
|---|
| 625 |             KLDRHEAP_ASSERT_BLOCK(pHeap, pCur);
 | 
|---|
| 626 |             if ((uintptr_t)pCur > (uintptr_t)pBlock)
 | 
|---|
| 627 |                 break;
 | 
|---|
| 628 |             pPrev = pCur;
 | 
|---|
| 629 |             pCur = pCur->pNext;
 | 
|---|
| 630 |         }
 | 
|---|
| 631 | 
 | 
|---|
| 632 |         pBlock->pNext = pCur;
 | 
|---|
| 633 |         pBlock->pPrev = pPrev;
 | 
|---|
| 634 |         pPrev->pNext = pBlock;
 | 
|---|
| 635 |         pCur->pPrev = pBlock;
 | 
|---|
| 636 |     }
 | 
|---|
| 637 |     KLDRHEAP_ASSERT_BLOCK(pHeap, pBlock);
 | 
|---|
| 638 | 
 | 
|---|
| 639 |     /* free it */
 | 
|---|
| 640 |     kLdrHeapFree(pHeap, pBlock + 1);
 | 
|---|
| 641 | }
 | 
|---|
| 642 | 
 | 
|---|
| 643 | 
 | 
|---|
| 644 | 
 | 
|---|
| 645 | /**
 | 
|---|
| 646 |  * Allocates a new segment.
 | 
|---|
| 647 |  *
 | 
|---|
| 648 |  * @returns 0 on success, non-zero OS status code on failure.
 | 
|---|
| 649 |  * @param   pSeg    Where to put the info about the allocated segment.
 | 
|---|
| 650 |  * @param   cbMin   The minimum segment size.
 | 
|---|
| 651 |  */
 | 
|---|
| 652 | static int kLdrHeapSegAlloc(PKLDRHEAPSEG pSeg, size_t cbMin)
 | 
|---|
| 653 | {
 | 
|---|
| 654 | #ifdef __OS2__
 | 
|---|
| 655 |     APIRET rc;
 | 
|---|
| 656 | 
 | 
|---|
| 657 |     pSeg->cb = (cbMin + 0xffff) & ~(size_t)0xffff;
 | 
|---|
| 658 |     pSeg->pvBase = NULL;
 | 
|---|
| 659 |     rc = DosAllocMem(&pSeg->pvBase, pSeg->cb, PAG_COMMIT | PAG_READ | PAG_WRITE | OBJ_ANY);
 | 
|---|
| 660 |     if (rc == ERROR_INVALID_PARAMETER)
 | 
|---|
| 661 |         rc = DosAllocMem(&pSeg->pvBase, pSeg->cb, PAG_COMMIT | PAG_READ | PAG_WRITE);
 | 
|---|
| 662 |     if (rc)
 | 
|---|
| 663 |     {
 | 
|---|
| 664 |         pSeg->pvBase = NULL;
 | 
|---|
| 665 |         pSeg->cb = 0;
 | 
|---|
| 666 |         return rc;
 | 
|---|
| 667 |     }
 | 
|---|
| 668 | 
 | 
|---|
| 669 | #elif defined(__WIN__)
 | 
|---|
| 670 |     pSeg->cb = (cbMin + 0xffff) & ~(size_t)0xffff;
 | 
|---|
| 671 |     pSeg->pvBase = VirtualAlloc(NULL, pSeg->cb, MEM_COMMIT, PAGE_READWRITE);
 | 
|---|
| 672 |     if (!pSeg->pvBase)
 | 
|---|
| 673 |     {
 | 
|---|
| 674 |         pSeg->cb = 0;
 | 
|---|
| 675 |         return GetLastError();
 | 
|---|
| 676 |     }
 | 
|---|
| 677 | 
 | 
|---|
| 678 | #else
 | 
|---|
| 679 | # error "Port me"
 | 
|---|
| 680 | #endif
 | 
|---|
| 681 | 
 | 
|---|
| 682 |     return 0;
 | 
|---|
| 683 | }
 | 
|---|
| 684 | 
 | 
|---|
| 685 | 
 | 
|---|
| 686 | /**
 | 
|---|
| 687 |  * Frees a segment.
 | 
|---|
| 688 |  *
 | 
|---|
| 689 |  * @param   pSeg    The segment to be freed.
 | 
|---|
| 690 |  */
 | 
|---|
| 691 | static void kLdrHeapSegFree(PKLDRHEAPSEG pSeg)
 | 
|---|
| 692 | {
 | 
|---|
| 693 | #ifdef __OS2__
 | 
|---|
| 694 |     APIRET rc = DosFreeMem(pSeg->pvBase);
 | 
|---|
| 695 |     KLDRHEAP_ASSERT(!rc); (void)rc;
 | 
|---|
| 696 | 
 | 
|---|
| 697 | #elif defined(__WIN__)
 | 
|---|
| 698 |     BOOL fRc = VirtualFree(pSeg->pvBase, 0 /*pSeg->cb*/, MEM_RELEASE);
 | 
|---|
| 699 |     KLDRHEAP_ASSERT(fRc); (void)fRc;
 | 
|---|
| 700 | 
 | 
|---|
| 701 | #else
 | 
|---|
| 702 | # error "Port me"
 | 
|---|
| 703 | #endif
 | 
|---|
| 704 | }
 | 
|---|
| 705 | 
 | 
|---|