source: trunk/src/win32k/misc/smalloc_avl.c

Last change on this file was 4164, checked in by bird, 25 years ago

Merged in the Grace branch. New Win32k!
File size: 53.6 KB
Line 
1/* $Id: smalloc_avl.c,v 1.4 2000-09-02 21:08:15 bird Exp $
2 *
3 * Swappable Heap - AVL.
4 *
5 * Note: This heap does very little checking on input.
6 * Use with care! We're running at Ring-0!
7 *
8 * Copyright (c) 1999-2000 knut st. osmundsen
9 *
10 * Project Odin Software License can be found in LICENSE.TXT
11 *
12 */
13
14
15/*******************************************************************************
16* Defined Constants And Macros *
17*******************************************************************************/
18#pragma info(notrd)
19#ifdef DEBUG
20 #define DEBUG_ALLOC
21 #undef ALLWAYS_HEAPCHECK
22 #undef SOMETIMES_HEAPCHECK
23#endif
24
25#define SIGNATURE_END 0xBEDAADEB
26#define SIGNATURE_START 0xDABEEBAD
27#define HEAPANCHOR_SIGNATURE 0xBEEFFEEB
28
29#ifdef DEBUG_ALLOC
30 #define CB_SIGNATURE_START 4
31 #define CB_SIGNATURE_END 4
32#else
33 #define CB_SIGNATURE_START 0
34 #define CB_SIGNATURE_END 0
35#endif
36#define CB_SIGNATURES (CB_SIGNATURE_END + CB_SIGNATURE_START)
37
38#define PNEXT_BLOCK(a) ((AVLKEY)(((PMEMBLOCK)(a))->u1.uData + ((PMEMBLOCK)(a))->u2.cbSize))
39#define PDATA(a) ((a) != NULL ? (PMEMBLOCK)(a)->u1.pvData : NULL)
40#define MEMBLOCK_FROM_FREESIZENODE(a) \
41 ((PMEMBLOCK)((unsigned)(a) - (unsigned)(&((PMEMBLOCK)0)->u2.coreFree)))
42
43#define BLOCKSIZE (1024*256) /* 256KB */
44#define ALIGNMENT (sizeof(unsigned))
45#define MEMBLOCKS_PER_CHUNK (256)
46
47
48#define INCL_DOS
49#define INCL_DOSERRORS
50#ifdef RING0
51 #define INCL_NOAPI
52#else
53 #define INCL_DOSMEMMGR
54#endif
55
56
57/******************************************************************************
58* Headerfiles
59******************************************************************************/
60#include <os2.h>
61#include "devSegDf.h" /* Win32k segment definitions. */
62#ifdef RING0
63 #include "dev32hlp.h"
64#endif
65#include "asmutils.h"
66#include "log.h"
67#include "smalloc.h"
68#include "rmalloc.h"
69#include "dev32.h"
70#include "avl.h"
71#include "macros.h"
72#include <memory.h>
73
74
75/*******************************************************************************
76* Structures and Typedefs *
77*******************************************************************************/
78#pragma pack(4)
79typedef struct _MEMBLOCK /* mb */
80{
81 union
82 {
83 AVLNODECORE core; /* AVLNode core for the tree sorted on address */
84 void * pvData; /* Pointer to the memory (core.Key and uData) */
85 unsigned uData; /* Address to the memory (core.Key and pvData) */
86 unsigned * puData; /* Address to the memory (core.Key and pvData) */
87 } u1;
88 union
89 {
90 AVLNODECORE coreFree; /* AVLNode core for the tree sorted on size */
91 unsigned cbSize; /* Size of the memory block. (Key of the AVLNodeCore) */
92 } u2;
93 struct _MEMBLOCK *pmbNext; /* Pointer to list of blocks with the same size */
94} MEMBLOCK, *PMEMBLOCK;
95
96
97typedef struct _HeapAnchor /* ha */
98{
99 #ifdef DEBUG_ALLOC
100 unsigned long ulSignature; /* Contains HEAPANCHOR_SIGNATURE */
101 #endif
102 void * pvBlock; /* Pointer to the start of this block. */
103 unsigned cbSize; /* Total amount of memory in this block. */
104 struct _HeapAnchor *pNext; /* Pointer to the next anchor block. */
105 struct _HeapAnchor *pPrev; /* Pointer to the previous anchor block. */
106 PAVLNODECORE pcoreFree; /* Pointer to the used-memblock chain. */
107 PAVLNODECORE pcoreFreeSize; /* Pointer to free-size-tree. */
108 unsigned cbFree; /* Amount of free memory. */
109 PAVLNODECORE pcoreUsed; /* Pointer to the used-memblock chain. */
110 unsigned cbUsed; /* Amount of used memory. */
111
112} HEAPANCHOR, *PHEAPANCHOR;
113
114
115typedef struct _MemblockChunk /* mc */
116{
117 struct _MemblockChunk * pNext; /* Pointer to next chunk */
118 unsigned cFree; /* Number of free memblocks */
119 char achBitmap[MEMBLOCKS_PER_CHUNK/8]; /* Used(1)/Free(0) bitmap */
120 MEMBLOCK amb[MEMBLOCKS_PER_CHUNK]; /* Array of memblocks */
121} MEMBLOCKCHUNK, *PMEMBLOCKCHUNK;
122
123
124typedef struct _SubHeaps_Callback_param
125{
126 unsigned cb;
127 unsigned c;
128} SUBHEAPS_CALLBACK_PARAM, *PSUBHEAPS_CALLBACK_PARAM;
129
130
131typedef struct _Allocated_Callback_param
132{
133 unsigned cb; /* Number of bytes of user data to dump. */
134 unsigned cbAllocated;
135 unsigned cBlocks;
136} ALLOCATED_CALLBACK_PARAM, *PALLOCATED_CALLBACK_PARAM;
137
138/******************************************************************************
139* Global data
140******************************************************************************/
141static PHEAPANCHOR phaFirst; /* Pointer to the first anchor block.*/
142static PHEAPANCHOR phaLast; /* Pointer to the last anchor block.*/
143unsigned cbSwpHeapMax; /* Maximum amount of memory used by the heap. */
144static PMEMBLOCKCHUNK pmcFirst; /* Pointer to the first memblock chunk. */
145
146#ifndef RING0
147char fSwpInited; /* init flag */
148#endif
149
150
151/******************************************************************************
152* Internal functions
153******************************************************************************/
154_Inline PMEMBLOCK swpAllocateMemblock(void);
155_Inline void swpReleaseMemblock(PMEMBLOCK pmb);
156static void swpInsertUsed(PHEAPANCHOR pha, PMEMBLOCK pmb);
157static void swpRemoveFromFreeSize(PHEAPANCHOR pha, PMEMBLOCK pmb);
158static void swpInsertIntoFreeSize(PHEAPANCHOR pha, PMEMBLOCK pmb);
159static void swpInsertFree(PHEAPANCHOR pha, PMEMBLOCK pmb);
160static PMEMBLOCK swpGetFreeMemblock(PHEAPANCHOR *ppha, unsigned cbUserSize);
161static PMEMBLOCK swpFindUsedBlock(PHEAPANCHOR *ppha, void *pvUser);
162static PMEMBLOCK swpFindWithinUsedBlock(PHEAPANCHOR *ppha, void *pvUser);
163#ifdef DEBUG_ALLOC
164static int swpCheckAVLTree(PMEMBLOCK pmb);
165static int swpCheckAVLTreeFree(PAVLNODECORE pNode);
166#endif
167static unsigned _swp_dump_subheaps_callback(PMEMBLOCK pmb, PSUBHEAPS_CALLBACK_PARAM pCb);
168static unsigned _swp_dump_allocated_callback(PMEMBLOCK pmb, PALLOCATED_CALLBACK_PARAM pParam);
169
170
171/**
172 * Allocates a new memblock.
173 * @returns Pointer to a Memblock.
174 * @author knut st. osmundsen
175 * @remark Quick and dirty implementation.
176 */
177_Inline PMEMBLOCK swpAllocateMemblock(void)
178{
179 #if 0
180 PMEMBLOCK pmb = (PMEMBLOCK)rmalloc(sizeof(MEMBLOCK));
181 if (pmb != NULL)
182 memset(pmb, 0, sizeof(*pmb));
183 return pmb;
184
185 #else
186
187 unsigned long *pul;
188 int i = 0;
189 PMEMBLOCKCHUNK pmcLast = NULL;
190 PMEMBLOCKCHUNK pmc = pmcFirst;
191 while (pmc != NULL && pmc->cFree == 0)
192 {
193 pmcLast = pmc;
194 pmc = pmc->pNext;
195 }
196
197 /* allocate another chunk? */
198 if (pmc == NULL)
199 {
200 pmc = rmalloc(sizeof(*pmc));
201 if (pmc != NULL)
202 {
203 memset(pmc, 0, sizeof(*pmc));
204 pmc->cFree = MEMBLOCKS_PER_CHUNK;
205 if (pmcLast == NULL)
206 pmcFirst = pmc;
207 else
208 pmcLast->pNext = pmc;
209 }
210 else
211 {
212 kprintf(("swpAllocateMemblock: rmalloc failed\n"));
213 return NULL;
214 }
215 }
216
217 /* find first free */
218 pmc->cFree--;
219 pul = (unsigned long*)pmc->achBitmap;
220 while (*pul == 0xFFFFFFFF)
221 pul++, i += 8*4;
222 while (pmc->achBitmap[i/8] & (0x1 << (i%8)))
223 i++;
224 pmc->achBitmap[i/8] |= (0x1 << (i%8));
225 return &pmc->amb[i];
226 #endif
227}
228
229/**
230 * Releases a memblock.
231 * @param pmb Pointer to the memory block which is to be release.
232 * @author knut st. osmundsen
233 * @remark Quick and dirty implementation.
234 */
235_Inline void swpReleaseMemblock(PMEMBLOCK pmb)
236{
237 #if 0
238 if (pmb != NULL)
239 rfree(pmb);
240 #else
241 int i;
242 PMEMBLOCKCHUNK pmc = pmcFirst;
243 while (pmc != NULL && !((void*)pmc < (void*)pmb && (unsigned)pmc + sizeof(*pmc) > (unsigned)pmb))
244 pmc = pmc->pNext;
245
246 if (pmc != NULL)
247 {
248 i = ((unsigned)pmb - (unsigned)pmc->amb) / sizeof(pmc->amb[0]);
249 #ifdef DEBUG
250 if ((pmc->achBitmap[i / 8] & (1 << (i % 8))) == 0)
251 {
252 kprintf(("swpReleaseMemblock: the memblock requested to be freed are allread free!\n"));
253 pmc->cFree--;
254 }
255 #endif
256 pmc->cFree++;
257 pmc->achBitmap[i / 8] &= pmc->achBitmap[i / 8] & ~(0x1 << (i % 8));
258 }
259 else
260 kprintf(("swpReleaseMemblock: hmm pmb is not found within any pmc.\n"));
261 #endif
262}
263
264
265/**
266 * Inserts a memblock into the used chain.
267 * @param pha Pointer to the heap anchor which the block is to be inserted into.
268 * @param pmb Pointer to memblock to insert into the free list.
269 * @remark Sorts on address.
270 */
271static void swpInsertUsed(PHEAPANCHOR pha, PMEMBLOCK pmb)
272{
273 pha->cbUsed += pmb->u2.cbSize;
274 AVLInsert(&pha->pcoreUsed, &pmb->u1.core);
275}
276
277
278/**
279 * Remove a given memblockfree from the free-size-tree.
280 */
281static void swpRemoveFromFreeSize(PHEAPANCHOR pha, PMEMBLOCK pmb)
282{
283 PMEMBLOCK pmbParent;
284 PMEMBLOCK pmbTmp;
285
286 pmbTmp = (PMEMBLOCK)AVLGetWithParent(&pha->pcoreFreeSize,
287 (PPAVLNODECORE)SSToDS(&pmbParent),
288 pmb->u2.coreFree.Key);
289 if (pmbTmp != NULL)
290 {
291 pmbTmp = MEMBLOCK_FROM_FREESIZENODE(pmbTmp);
292 if (pmbTmp != pmb)
293 {
294 PMEMBLOCK pmbPrev;
295 do
296 {
297 pmbPrev = pmbTmp;
298 pmbTmp = pmbTmp->pmbNext;
299 } while (pmbTmp != NULL && pmbTmp != pmb);
300
301 if (pmbTmp != NULL)
302 pmbPrev->pmbNext = pmbTmp->pmbNext;
303 else
304 kprintf(("swpRemoveFromFreeSize: internal heap error, pmb not in list.\n"));
305 }
306 else
307 { /* pmb is first in the list */
308 if (pmbTmp->pmbNext == NULL)
309 { /* no list - no other nodes of this size: simply remove it. */
310 AVLRemove(&pha->pcoreFreeSize, pmb->u2.coreFree.Key);
311 }
312 else
313 { /* other nodes of this size: replace pmb with the first node in the chain. */
314 memcpy((void*)&pmbTmp->pmbNext->u2.coreFree, (void*)&pmbTmp->u2.coreFree, sizeof(pmbTmp->u2.coreFree));
315 if (pmbParent != NULL)
316 {
317 pmbParent = MEMBLOCK_FROM_FREESIZENODE(pmbParent);
318 if (pmbTmp->u2.coreFree.Key < pmbParent->u2.coreFree.Key)
319 pmbParent->u2.coreFree.pLeft = &pmb->pmbNext->u2.coreFree;
320 else
321 pmbParent->u2.coreFree.pRight = &pmb->pmbNext->u2.coreFree;
322 }
323 else
324 pha->pcoreFreeSize = &pmb->pmbNext->u2.coreFree;
325 }
326 }
327 }
328 else
329 kprintf(("swpRemoveFromFreeSize: internal heap error, free-node not in free-size tree.\n"));
330}
331
332
333/**
334 * Inserts a block into the free-size-tree.
335 */
336static void swpInsertIntoFreeSize(PHEAPANCHOR pha, PMEMBLOCK pmb)
337{
338 PMEMBLOCK pmbTmp;
339
340 pmbTmp = (PMEMBLOCK)AVLGet(&pha->pcoreFreeSize, pmb->u2.coreFree.Key);
341 if (pmbTmp != NULL)
342 {
343 pmbTmp = MEMBLOCK_FROM_FREESIZENODE(pmbTmp);
344 while (pmbTmp->pmbNext != NULL && pmbTmp->pmbNext > pmb)
345 pmbTmp = pmbTmp->pmbNext;
346
347 pmb->pmbNext = pmbTmp->pmbNext;
348 pmbTmp->pmbNext = pmb;
349 }
350 else
351 {
352 pmb->pmbNext = NULL;
353 AVLInsert(&pha->pcoreFreeSize, &pmb->u2.coreFree);
354 }
355}
356
357
358/**
359 * Inserts a memblock into the free chain.
360 * Merges blocks adjecent blocks.
361 * @param pha Pointer to the heap anchor which the block is to be inserted into.
362 * @param pmb Pointer to memblock to insert into the free list.
363 * @remark Sorts on address.
364 */
365static void swpInsertFree(PHEAPANCHOR pha, PMEMBLOCK pmb)
366{
367 PMEMBLOCK pmbRight;
368 PMEMBLOCK pmbRightParent;
369 PMEMBLOCK pmbLeft;
370
371 pha->cbFree += pmb->u2.cbSize;
372
373 /*
374 * Get both right and left to determin which case we have here.
375 * Four cases are possible:
376 * 1 - insert no merge.
377 * 2 - insert left merge.
378 * 3 - insert right merge.
379 * 4 - insert both left and right merge.
380 */
381 pmbRight = (PMEMBLOCK)AVLGetWithParent(&pha->pcoreFree,
382 (PPAVLNODECORE)SSToDS(&pmbRightParent),
383 PNEXT_BLOCK(pmb));
384 pmbLeft = (PMEMBLOCK)AVLGetBestFit(&pha->pcoreFree, pmb->u1.core.Key, FALSE);
385 if (pmbLeft != NULL && PNEXT_BLOCK(pmbLeft) != pmb->u1.core.Key)
386 pmbLeft = NULL;
387
388 if (pmbLeft == NULL && pmbRight == NULL)
389 { /* 1 - insert no merge */
390 AVLInsert(&pha->pcoreFree, &pmb->u1.core);
391 swpInsertIntoFreeSize(pha, pmb);
392 }
393 else if (pmbLeft != NULL && pmbRight == NULL)
394 { /* 2 - insert left merge: just add pmb to pmbLeft. */
395 swpRemoveFromFreeSize(pha, pmbLeft);
396 pmbLeft->u2.cbSize += pmb->u2.cbSize;
397 swpInsertIntoFreeSize(pha, pmbLeft);
398 swpReleaseMemblock(pmb);
399 }
400 else if (pmbLeft == NULL && pmbRight != NULL)
401 { /* 3 - insert right merge: replace pmbRight with pmb in the pmbFree tree; */
402 swpRemoveFromFreeSize(pha, pmbRight);
403 pmb->u1.core.uchHeight = pmbRight->u1.core.uchHeight;
404 pmb->u1.core.pLeft = pmbRight->u1.core.pLeft;
405 pmb->u1.core.pRight = pmbRight->u1.core.pRight;
406 pmb->u2.cbSize += pmbRight->u2.cbSize;
407 swpInsertIntoFreeSize(pha, pmb);
408 if (pmbRightParent != NULL)
409 {
410 if (pmb->u1.core.Key < pmbRightParent->u1.core.Key)
411 pmbRightParent->u1.core.pLeft = &pmb->u1.core;
412 else
413 pmbRightParent->u1.core.pRight = &pmb->u1.core;
414 }
415 else
416 pha->pcoreFree = &pmb->u1.core;
417 swpReleaseMemblock(pmbRight);
418 }
419 else
420 { /* 4 -insert both left and right merge */
421 if (AVLRemove(&pha->pcoreFree, pmbRight->u1.core.Key) != (PAVLNODECORE)pmbRight)
422 {
423 kprintf(("InsertFree: AVLRemove on pmbRight failed.\n"));
424 return;
425 }
426 swpRemoveFromFreeSize(pha, pmbLeft);
427 swpRemoveFromFreeSize(pha, pmbRight);
428 pmbLeft->u2.cbSize += pmb->u2.cbSize + pmbRight->u2.cbSize;
429 swpInsertIntoFreeSize(pha, pmbLeft);
430 swpReleaseMemblock(pmb);
431 swpReleaseMemblock(pmbRight);
432 }
433}
434
435
436/**
437 * Finds a free block at the requested size.
438 * @returns Pointer to block (not in free list any longer).
439 * @param ppha Upon return the pointer pointed to contains the heap
440 * anchor which the memory block was allocated from.
441 * @param cbUserSize Bytes the user have requested.
442 * @sketch cbUserSize is aligned to nearest 4 bytes.
443 * ...
444 *
445 */
446static PMEMBLOCK swpGetFreeMemblock(PHEAPANCHOR *ppha, unsigned cbUserSize)
447{
448 unsigned cbBlockSize;
449 unsigned cbTotalSize = 0;
450
451 cbUserSize = ALIGN(cbUserSize, ALIGNMENT) + CB_SIGNATURES;
452
453 *ppha = phaFirst;
454 while (*ppha != NULL)
455 {
456 if ((*ppha)->cbFree >= cbUserSize)
457 {
458 PMEMBLOCK pmb;
459
460 pmb = (PMEMBLOCK)AVLGetBestFit(&(*ppha)->pcoreFreeSize, cbUserSize, TRUE);
461 if (pmb != NULL)
462 {
463 pmb = MEMBLOCK_FROM_FREESIZENODE(pmb);
464 swpRemoveFromFreeSize(*ppha, pmb);
465 (*ppha)->cbFree -= pmb->u2.cbSize;
466
467 /* pmb is now the block which we are to return, but do we have to split it? */
468 if (pmb->u2.cbSize > cbUserSize + CB_SIGNATURES)
469 {
470 PMEMBLOCK pmbTmp = pmb;
471 pmb = swpAllocateMemblock();
472 if (pmb == NULL)
473 {
474 kprintf(("swpGetFreeMemblock: swpAllocateMemblock failed.\n"));
475 swpInsertIntoFreeSize(*ppha, pmbTmp);
476 (*ppha)->cbFree += pmbTmp->u2.cbSize;
477 return NULL;
478 }
479 pmb->u1.uData = pmbTmp->u1.uData + pmbTmp->u2.cbSize - cbUserSize;
480 pmbTmp->u2.cbSize -= cbUserSize;
481 pmb->u2.cbSize = cbUserSize;
482 (*ppha)->cbFree += pmbTmp->u2.cbSize;
483 #ifdef DEBUG_ALLOC
484 pmb->u1.puData[-1] = SIGNATURE_END;
485 pmb->u1.puData[0] = SIGNATURE_START;
486 #endif
487 swpInsertIntoFreeSize(*ppha, pmbTmp);
488 }
489 else
490 {
491 PMEMBLOCK pmbTmp = (PMEMBLOCK)AVLRemove(&(*ppha)->pcoreFree, pmb->u1.core.Key);
492 if (pmbTmp != pmb)
493 {
494 kprintf(("swpGetFreeMemblock: Internal heap error - failed to Remove best fit block!\n"));
495 return NULL;
496 }
497 }
498 return pmb;
499 }
500 }
501
502 cbTotalSize += (*ppha)->cbSize;
503
504 /* next heap anchor */
505 *ppha = (*ppha)->pNext;
506 }
507
508
509 /*
510 * Add a new heap anchor?
511 */
512 cbBlockSize = ALIGN(cbUserSize + CB_SIGNATURES + 1, BLOCKSIZE);
513 if (cbSwpHeapMax >= cbTotalSize + cbBlockSize)
514 {
515 /* allocate new heapanchor */
516 *ppha = rmalloc(sizeof(**ppha));
517 if (ppha != NULL)
518 {
519 PMEMBLOCK pmbFree = swpAllocateMemblock();
520 PMEMBLOCK pmbUsed = swpAllocateMemblock();
521 if (pmbFree != NULL && pmbUsed != NULL)
522 {
523 register PHEAPANCHOR pha = *ppha;
524 memset(pha, 0, sizeof(*pha));
525 #ifdef RING0
526 pha->pvBlock = D32Hlp_VMAlloc(VMDHA_SWAP, cbBlockSize, ~0UL);
527 #else
528 if (DosAllocMem(&pha->pvBlock, cbBlockSize, PAG_COMMIT | PAG_READ | PAG_WRITE) != 0)
529 pha->pvBlock = NULL;
530 #endif
531 if (pha->pvBlock != NULL)
532 {
533 /* anchor block */
534 #ifdef DEBUG_ALLOC
535 pha->ulSignature = HEAPANCHOR_SIGNATURE;
536 #endif
537 pha->cbSize = cbBlockSize;
538
539 /* free memblock */
540 pmbFree->u1.uData = (unsigned)pha->pvBlock;
541 pmbFree->u2.cbSize = cbBlockSize - cbUserSize;
542 #ifdef DEBUG_ALLOC
543 pmbFree->u1.puData[0] = SIGNATURE_START;
544 pmbFree->u1.puData[(pmbFree->u2.cbSize / sizeof(unsigned)) - 1] = SIGNATURE_END;
545 #endif
546 swpInsertFree(pha, pmbFree);
547
548 /* used memblock */
549 pmbUsed->u1.uData = pmbFree->u1.uData + pmbFree->u2.cbSize;
550 pmbUsed->u2.cbSize = cbUserSize;
551 #ifdef DEBUG_ALLOC
552 pmbUsed->u1.puData[0] = SIGNATURE_START;
553 pmbUsed->u1.puData[(pmbUsed->u2.cbSize / sizeof(unsigned)) - 1] = SIGNATURE_END;
554 #endif
555
556 /* insert into list */
557 pha->pPrev = phaLast;
558 pha->pNext = NULL;
559 if (phaLast == NULL) /* Might never happen but just in case it does. */
560 phaLast = phaFirst = pha;
561 else
562 phaLast->pNext = pha;
563 phaLast = pha;
564
565 return pmbUsed;
566 }
567 else
568 kprintf(("swpGetFreeMemblock: unable to allocate a new heap block.\n"));
569 }
570 else
571 kprintf(("swpGetFreeMemblock: swpAllocateMemblock failed.\n"));
572 swpReleaseMemblock(pmbFree);
573 swpReleaseMemblock(pmbUsed);
574 rfree(*ppha);
575 }
576 else
577 kprintf(("swpGetFreeMemblock: rmalloc failed for when allocating a new heap anchor.\n"));
578
579 return NULL;
580 }
581 else
582 {
583 kprintf(("swpGetFreeMemblock: Allocation failed, limit reached. \n"
584 " %d(=cbResHeapMax) < %d(=cbTotalSize) + %d(=cbBlockSize)\n",
585 cbSwpHeapMax, cbTotalSize, cbBlockSize));
586 }
587
588 return NULL;
589}
590
591
592/**
593 * Finds a used memory block.
594 * @returns Pointer to memblock if found.
595 * @param ppha Pointer to pointer to heap anchor block the returned memblock is located in. (output)
596 * NULL is allowed.
597 * @param pvUser User pointer to find the block to.
598 */
599static PMEMBLOCK swpFindUsedBlock(PHEAPANCHOR *ppha, void *pvUser)
600{
601 if (pvUser != NULL)
602 {
603 register PHEAPANCHOR pha = phaFirst;
604 while (pha != NULL && !(pvUser > pha->pvBlock && (unsigned)pvUser < (unsigned)pha->pvBlock + pha->cbSize))
605 pha = pha->pNext;
606
607 if (ppha != NULL)
608 *ppha = pha;
609 if (pha != NULL)
610 {
611 register PMEMBLOCK pmb;
612 #ifdef DEBUG_ALLOC
613 if (pha->ulSignature != HEAPANCHOR_SIGNATURE)
614 {
615 kprintf(("swpFindUsedBlock: Invalid heapanchor signature.\n"));
616 return NULL;
617 }
618 #endif
619 pmb = (PMEMBLOCK)AVLGet(&pha->pcoreUsed, (AVLKEY)((unsigned)pvUser - CB_SIGNATURE_START));
620 #ifdef DEBUG_ALLOC
621 if (pmb != NULL && pmb->u1.puData[0] != SIGNATURE_START)
622 {
623 kprintf(("swpFindUsedBlock: Invalid memblock start signature.\n"));
624 pmb = NULL;
625 }
626 if (pmb != NULL && pmb->u1.puData[(pmb->u2.cbSize/sizeof(unsigned)) - 1] != SIGNATURE_END)
627 {
628 kprintf(("swpFindUsedBlock: Invalid memblock end signature.\n"));
629 pmb = NULL;
630 }
631 #endif
632 return pmb;
633 }
634 }
635
636 return NULL;
637}
638
639
640/**
641 * Finds a used memory block from a pointer into the userdata.
642 * @returns Pointer to memblock if found.
643 * @param ppha Pointer to pointer to heap anchor block the returned memblock is located in. (output)
644 * NULL is allowed.
645 * @param pvUser User pointer to find the block to.
646 */
647static PMEMBLOCK swpFindWithinUsedBlock(PHEAPANCHOR *ppha, void *pvUser)
648{
649 register PHEAPANCHOR pha = phaFirst;
650
651 if (pvUser == NULL)
652 return NULL;
653
654 while (pha != NULL && !(pvUser > pha->pvBlock && (unsigned)pvUser < (unsigned)pha->pvBlock + pha->cbSize))
655 pha = pha->pNext;
656
657 if (ppha != NULL)
658 *ppha = pha;
659 if (pha != NULL)
660 {
661 PMEMBLOCK pmb;
662
663 #ifdef DEBUG_ALLOC
664 if (pha->ulSignature != HEAPANCHOR_SIGNATURE)
665 {
666 kprintf(("swpFindWithinUsedBlock: Invalid heapanchor signature.\n"));
667 return NULL;
668 }
669 #endif
670
671
672 pmb = (PMEMBLOCK)AVLGetBestFit(&pha->pcoreUsed, (AVLKEY)pvUser - CB_SIGNATURE_START, TRUE);
673 if (pmb != NULL
674 && pmb->u1.uData + pmb->u2.cbSize - CB_SIGNATURE_END > (unsigned)pvUser
675 && pmb->u1.uData + CB_SIGNATURE_START <= (unsigned)pvUser
676 )
677 {
678 #ifdef DEBUG_ALLOC
679 if (pmb != NULL && pmb->u1.puData[0] != SIGNATURE_START)
680 {
681 kprintf(("swpFindWithinUsedBlock: Invalid memblock start signature.\n"));
682 pmb = NULL;
683 }
684 if (pmb != NULL && pmb->u1.puData[(pmb->u2.cbSize/sizeof(unsigned)) - 1] != SIGNATURE_END)
685 {
686 kprintf(("swpFindWithinUsedBlock: Invalid memblock end signature.\n"));
687 pmb = NULL;
688 }
689 #endif
690 return pmb;
691 }
692 }
693
694 return NULL;
695}
696
697
698/**
699 * Initiate the heap "subsystem".
700 * @returns 0 on success, not 0 on error.
701 * @param cbSizeInit The initial size of the heap in bytes.
702 * @param cbSizeMax Maximum heapsize in bytes.
703 */
704int swpHeapInit(unsigned cbSizeInit, unsigned cbSizeMax)
705{
706 PMEMBLOCK pmbFree;
707 cbSwpHeapMax = cbSizeMax;
708 pmcFirst = NULL;
709 pmbFree = swpAllocateMemblock();
710 if (pmbFree != NULL)
711 {
712 phaFirst = rmalloc(sizeof(*phaFirst));
713 if (phaFirst != NULL)
714 {
715 unsigned cbSize = MAX(BLOCKSIZE, cbSizeInit);
716 memset(phaFirst, 0, sizeof(*phaFirst));
717 #ifdef RING0
718 phaFirst->pvBlock = D32Hlp_VMAlloc(VMDHA_SWAP, cbSize, ~0UL);
719 #else
720 if (DosAllocMem(&phaFirst->pvBlock, cbSize, PAG_COMMIT | PAG_READ | PAG_WRITE) != 0)
721 phaFirst->pvBlock = NULL;
722 #endif
723 if (phaFirst->pvBlock != NULL)
724 {
725 /* anchor block */
726 #ifdef DEBUG_ALLOC
727 phaFirst->ulSignature = HEAPANCHOR_SIGNATURE;
728 #endif
729 phaFirst->cbSize = cbSize;
730
731 /* free memblock */
732 pmbFree->u1.uData = (unsigned)phaFirst->pvBlock;
733 pmbFree->u2.cbSize = cbSize;
734 #ifdef DEBUG_ALLOC
735 pmbFree->u1.puData[0] = SIGNATURE_START;
736 pmbFree->u1.puData[(pmbFree->u2.cbSize / sizeof(unsigned)) - 1] = SIGNATURE_END;
737 #endif
738 swpInsertFree(phaFirst, pmbFree);
739
740 /* insert into list */
741 phaFirst->pPrev = phaFirst->pNext = NULL;
742 phaLast = phaFirst;
743
744 #if defined(ALLWAYS_HEAPCHECK) || defined(SOMETIMES_HEAPCHECK)
745 if (!_swp_heap_check())
746 { /* error! */
747 kprintf(("swpHeapInit: _swp_heap_check failed!\n"));
748 #ifdef DEBUG
749 Int3();
750 #endif
751 return -2;
752 }
753 #endif
754 #ifndef RING0
755 fSwpInited = TRUE;
756 #endif
757
758 return 0;
759 }
760 else
761 kprintf(("swpHeapInit: failed to allocate heap block\n"));
762 rfree(phaFirst);
763 phaFirst = NULL;
764 }
765 else
766 {
767 kprintf(("swpHeapInit: rmalloc failed to allocate a heap anchor.\n"));
768 #ifdef DEBUG
769 Int3();
770 #endif
771 }
772 swpReleaseMemblock(pmbFree);
773 }
774 else
775 kprintf(("swpHeapInit: swpAllocateMemblock failed.\n"));
776 return -1;
777}
778
779
780/**
781 * malloc - allocates a given amount of memory.
782 * @returns Pointer to allocated memory.
783 * NULL if out of memory. (Or memory to fragmented.)
784 * @param cbSize Bytes user requests us to allocate. This is aligned
785 * to four bytes.
786 */
787void * smalloc(unsigned cbSize)
788{
789 #if defined(ALLWAYS_HEAPCHECK) || defined(SOMETIMES_HEAPCHECK)
790 if (!_swp_heap_check())
791 {
792 kprintf(("smalloc: _swp_heap_check failed!\n"));
793 return NULL;
794 }
795 #endif
796
797 if (cbSize != 0)
798 {
799 PHEAPANCHOR pha;
800 PMEMBLOCK pmb = swpGetFreeMemblock(SSToDS(&pha), cbSize);
801 if (pmb != NULL)
802 {
803 swpInsertUsed(pha, pmb);
804 return (void*)(pmb->u1.uData + CB_SIGNATURE_START);
805 }
806 }
807 else
808 kprintf(("smalloc: error cbSize = 0\n"));
809
810 return NULL;
811}
812
813
814/**
815 * Reallocate a heapblock.
816 * @returns Pointer to new heapblock.
817 * @param pv Pointer to the block to realloc.
818 * If pv is NULL, this call is equal to malloc.
819 * @param cbNew The new block size.
820 */
821void *srealloc(void *pv, unsigned cbNew)
822{
823 PMEMBLOCK pmb;
824 PHEAPANCHOR pha;
825
826 #if defined(ALLWAYS_HEAPCHECK) || defined(SOMETIMES_HEAPCHECK)
827 if (!_swp_heap_check())
828 {
829 kprintf(("srealloc: _swp_heap_check failed!\n"));
830 return NULL;
831 }
832 #endif
833 pmb = swpFindUsedBlock(SSToDS(&pha), pv);
834 if (pmb != NULL)
835 {
836 void *pvRet;
837
838 cbNew = ALIGN(cbNew, ALIGNMENT) + CB_SIGNATURES;
839 if (cbNew <= pmb->u2.cbSize)
840 { /* shrink block */
841 pvRet = pv;
842 if (cbNew + CB_SIGNATURES < pmb->u2.cbSize)
843 { /* split block */
844 PMEMBLOCK pmbNew = swpAllocateMemblock();
845 if (pmbNew != NULL)
846 {
847 pmbNew->u1.uData = pmb->u1.uData + cbNew;
848 pmbNew->u2.cbSize = pmb->u2.cbSize - cbNew;
849 pha->cbUsed -= pmb->u2.cbSize - cbNew;
850 pmb->u2.cbSize = cbNew;
851 #ifdef DEBUG_ALLOC
852 pmbNew->u1.puData[-1] = SIGNATURE_END;
853 pmbNew->u1.puData[0] = SIGNATURE_START;
854 pmbNew->u1.puData[(pmbNew->u2.cbSize / sizeof(unsigned)) - 1] = SIGNATURE_END;
855 #endif
856 swpInsertFree(pha, pmbNew);
857 #ifdef ALLWAYS_HEAPCHECK
858 if (!_swp_heap_check())
859 {
860 kprintf(("srealloc: _swp_heap_check failed!\n"));
861 return NULL;
862 }
863 #endif
864 }
865 else
866 kprintf(("srealloc: swpAllocateMemblock failed\n"));
867 }
868 }
869 else
870 { /* expand block - this code may be optimized... */
871 #if 0
872 pvRet = smalloc(cbNew);
873 if (pvRet != NULL)
874 {
875 memcpy(pvRet, pv, pmb->u2.cbSize);
876 sfree(pv);
877 }
878 #else
879 /* optimized FIXME! */
880 PMEMBLOCK pmbRight = (PMEMBLOCK)AVLGet(&pha->pcoreFree, PNEXT_BLOCK(pmb));
881 if (pmbRight != NULL && pmbRight->u2.cbSize + pmb->u2.cbSize >= cbNew)
882 {
883 pvRet = pv;
884 /* split the free block? */
885 if (pmbRight->u2.cbSize + pmb->u2.cbSize - CB_SIGNATURES > cbNew)
886 {
887 pha->cbFree -= pmbRight->u2.cbSize;
888 swpRemoveFromFreeSize(pha, pmbRight);
889 pmbRight->u1.uData = pmb->u1.uData + cbNew;
890 pmbRight->u2.cbSize = pmbRight->u2.cbSize + pmb->u2.cbSize - cbNew;
891 #ifdef DEBUG_ALLOC
892 pmbRight->u1.puData[-1] = SIGNATURE_END;
893 pmbRight->u1.puData[0] = SIGNATURE_START;
894 pmbRight->u1.puData[(pmbRight->u2.cbSize / sizeof(unsigned)) - 1] = SIGNATURE_END;
895 #endif
896 swpInsertIntoFreeSize(pha, pmbRight);
897 pha->cbUsed += cbNew - pmb->u2.cbSize;
898 pmb->u2.cbSize = cbNew;
899 pha->cbFree += pmbRight->u2.cbSize;
900 }
901 else
902 {
903 if (AVLRemove(&pha->pcoreFree, pmbRight->u1.core.Key) != &pmbRight->u1.core)
904 {
905 kprintf(("srealloc: AVLRemove failed for pmbRight - hmm!\n"));
906 return NULL;
907 }
908 swpRemoveFromFreeSize(pha, pmbRight);
909 pmb->u2.cbSize += pmbRight->u2.cbSize;
910 pha->cbFree -= pmbRight->u2.cbSize;
911 pha->cbUsed += pmbRight->u2.cbSize;
912 swpReleaseMemblock(pmbRight);
913 }
914
915 }
916 else
917 { /* worst case: allocate a new block, copy data and free the old block. */
918 pvRet = smalloc(cbNew);
919 if (pvRet != NULL)
920 {
921 memcpy(pvRet, pv, pmb->u2.cbSize-CB_SIGNATURES);
922 sfree(pv);
923 }
924 }
925 #endif
926 }
927 return pvRet;
928 }
929 else
930 {
931 if (pv == NULL)
932 return smalloc(cbNew);
933 kprintf(("srealloc: invalid user pointer, pv=0x%08x\n", pv));
934 }
935 return NULL;
936}
937
938
939/**
940 * Frees a block.
941 * @param pv User pointer.
942 */
943void sfree(void *pv)
944{
945 #if defined(ALLWAYS_HEAPCHECK) || defined(SOMETIMES_HEAPCHECK)
946 if (!_swp_heap_check())
947 {
948 kprintf(("sfree: _swp_heap_check failed!\n"));
949 return;
950 }
951 #endif
952
953 if (pv != NULL)
954 {
955 PHEAPANCHOR pha = phaFirst;
956
957 while (pha != NULL && !(pv > pha->pvBlock
958 && (unsigned)pv < (unsigned)pha->pvBlock + pha->cbSize))
959 pha = pha->pNext;
960
961 if (pha != NULL)
962 {
963 PMEMBLOCK pmb = (PMEMBLOCK)AVLRemove(&pha->pcoreUsed, ((AVLKEY)pv - CB_SIGNATURE_START));
964 if (pmb != NULL)
965 {
966 pha->cbUsed -= pmb->u2.cbSize;
967 swpInsertFree(pha, pmb);
968 }
969 else
970 kprintf(("sfree: heap block not found!\n"));
971 }
972 else
973 kprintf(("sfree: heap block not within the large blocks!\n"));
974 }
975 else
976 kprintf(("sfree: Free received a NULL pointer!\n"));
977}
978
979
980/**
981 * Gets the size of a block.
982 * @returns Bytes in a block.
983 */
984unsigned _swp_msize(void *pv)
985{
986 PHEAPANCHOR pha;
987 PMEMBLOCK pmb;
988
989 #ifdef ALLWAYS_HEAPCHECK
990 if (!_swp_heap_check())
991 kprintf(("_swp_msize: _swp_heap_check failed!\n"));
992 #endif
993
994 pmb = swpFindUsedBlock(SSToDS(&pha), pv);
995 return pmb != NULL ? pmb->u2.cbSize - CB_SIGNATURES : 0;
996}
997
998
999/**
1000 * Checks if pv is a valid heappointer.
1001 * @returns 1 if valid. 0 if invalid.
1002 * @param pv User data pointer.
1003 */
1004int _swp_validptr(void *pv)
1005{
1006 PMEMBLOCK pmb;
1007
1008 #ifdef ALLWAYS_HEAPCHECK
1009 if (!_swp_heap_check())
1010 kprintf(("_swp_validptr: _swp_heap_check failed!\n"));
1011 #endif
1012
1013 pmb = swpFindWithinUsedBlock(NULL, pv);
1014 return pmb != NULL ?
1015 (unsigned)pv - CB_SIGNATURE_START >= pmb->u1.uData
1016 && (unsigned)pv - pmb->u1.uData - CB_SIGNATURES < pmb->u2.cbSize
1017 : FALSE;
1018}
1019
1020
1021/**
1022 * Checks that the dataaera made up by pv and cbSize valid with in the heap.
1023 * @returns 1 if valid. 0 if invalid.
1024 * @param pv User data pointer.
1025 * @param cbSize Size of data which has to be valid.
1026 */
1027int _swp_validptr2(void *pv, unsigned cbSize)
1028{
1029 PMEMBLOCK pmb;
1030
1031 #ifdef ALLWAYS_HEAPCHECK
1032 if (!_swp_heap_check())
1033 kprintf(("_swp_validptr: _swp_heap_check failed!\n"));
1034 #endif
1035
1036 pmb = swpFindWithinUsedBlock(NULL, pv);
1037 if (pmb != NULL)
1038 {
1039 pv = (void*)((unsigned)pv - pmb->u1.uData);
1040 return (unsigned)pv > CB_SIGNATURE_START
1041 && (pmb->u2.cbSize - CB_SIGNATURES - (unsigned)pv) >= cbSize;
1042 }
1043 return FALSE;
1044}
1045
1046
1047/**
1048 * Get amount of free memory (in bytes)
1049 * @returns Amount of free memory (in bytes).
1050 * @remark Note that this amount is of all free memory blocks and
1051 * that these blocks are fragmented.
1052 * You'll probably not be able to allocate a single block
1053 * of the returned size.
1054 */
1055unsigned _swp_memfree(void)
1056{
1057 PHEAPANCHOR pha = phaFirst;
1058 unsigned cb;
1059
1060 #ifdef ALLWAYS_HEAPCHECK
1061 if (!_swp_heap_check())
1062 kprintf(("_swp_memfree: _swp_heap_check failed!\n"));
1063 #endif
1064
1065 for (cb = 0; pha != NULL; pha = pha->pNext)
1066 cb += pha->cbFree;
1067
1068 return cb;
1069}
1070
1071
1072/**
1073 * Get amount of used memory (in bytes)
1074 * @returns Amount of used memory (in bytes).
1075 */
1076unsigned _swp_memused(void)
1077{
1078 PHEAPANCHOR pha = phaFirst;
1079 unsigned cb;
1080
1081 #ifdef ALLWAYS_HEAPCHECK
1082 if (!_swp_heap_check())
1083 kprintf(("_swp_memused: _swp_heap_check failed!\n"));
1084 #endif
1085
1086 for (cb = 0; pha != NULL; pha = pha->pNext)
1087 cb += pha->cbUsed;
1088
1089 return cb;
1090}
1091
1092
1093/**
1094 * Collects the heap state.
1095 * @returns 0 on success.
1096 * -1 on error.
1097 * @param pState Pointer to a HEAPSTATE structure which is
1098 * filled upon successful return.
1099 */
1100int _swp_state(PHEAPSTATE pState)
1101{
1102 PHEAPANCHOR pha;
1103
1104 #ifdef ALLWAYS_HEAPCHECK
1105 if (!_res_heap_check())
1106 {
1107 kprintf(("_res_state: _res_heap_check failed!\n"));
1108 return -1;
1109 }
1110 #endif
1111
1112 if (pState == NULL)
1113 return -1;
1114
1115 /*
1116 * Loop thru all the anchor blocks and all memory blocks
1117 * building the stats.
1118 */
1119 memset(pState, 0, sizeof(HEAPSTATE));
1120 for (pha = phaFirst; pha != NULL; pha = pha->pNext)
1121 {
1122 AVLENUMDATA EnumData;
1123 PAVLENUMDATA pEnumData = SSToDS(&EnumData);
1124 PMEMBLOCK pmb;
1125
1126 /* count of free blocks */
1127 pmb = (PMEMBLOCK)AVLBeginEnumTree((PPAVLNODECORE)&pha->pcoreFree, pEnumData, TRUE);
1128 while (pmb)
1129 {
1130 pState->cBlocksFree++;
1131 pmb = (PMEMBLOCK)AVLGetNextNode(pEnumData);
1132 }
1133
1134 /* count of used blocks */
1135 pmb = (PMEMBLOCK)AVLBeginEnumTree((PPAVLNODECORE)&pha->pcoreUsed, pEnumData, TRUE);
1136 while (pmb)
1137 {
1138 pState->cBlocksUsed++;
1139 pmb = (PMEMBLOCK)AVLGetNextNode(pEnumData);
1140 }
1141
1142 /* sizes */
1143 pState->cbHeapSize += pha->cbSize;
1144 pState->cbHeapFree += pha->cbFree;
1145 pState->cbHeapUsed += pha->cbUsed;
1146 }
1147
1148 return 0;
1149}
1150
1151
1152/**
1153 * Checks heap integrety.
1154 * @returns TRUE when ok.
1155 * FALSE on error.
1156 * NULL if out of memory. (Or memory to fragmented.)
1157 */
1158int _swp_heap_check(void)
1159{
1160#ifdef DEBUG_ALLOC
1161 PHEAPANCHOR pha = phaFirst;
1162 PHEAPANCHOR phaPrev = NULL;
1163
1164
1165 while (pha != NULL)
1166 {
1167 AVLENUMDATA FreeEnumData;
1168 AVLENUMDATA UsedEnumData;
1169 PMEMBLOCK pmbFree = (PMEMBLOCK)AVLBeginEnumTree(&pha->pcoreFree,
1170 (PAVLENUMDATA)SSToDS(&FreeEnumData), TRUE);
1171 PMEMBLOCK pmbFreeNext = (PMEMBLOCK)AVLGetNextNode((PAVLENUMDATA)SSToDS(&FreeEnumData));
1172 PMEMBLOCK pmbUsed = (PMEMBLOCK)AVLBeginEnumTree(&pha->pcoreUsed,
1173 (PAVLENUMDATA)SSToDS(&UsedEnumData), TRUE);
1174 PMEMBLOCK pmbUsedNext = (PMEMBLOCK)AVLGetNextNode((PAVLENUMDATA)SSToDS(&UsedEnumData));
1175 PMEMBLOCK pmbLast = NULL;
1176 unsigned cbFree = 0;
1177 unsigned cbUsed = 0;
1178 unsigned cbSize = 0;
1179
1180 /*
1181 * Check the heap anchor.
1182 */
1183 if (pha->ulSignature != HEAPANCHOR_SIGNATURE)
1184 {
1185 kprintf(("_swp_heap_check: invalid signature for pha=0x%08x\n", pha));
1186 Int3();
1187 return FALSE;
1188 }
1189
1190 if (pha->cbFree + pha->cbUsed != pha->cbSize || pha->cbSize == 0)
1191 {
1192 kprintf(("_swp_heap_check: cbFree + cbUsed >= cbSize for pha=0x%08x\n", pha));
1193 Int3();
1194 return FALSE;
1195 }
1196
1197 if (pha->pPrev != phaPrev)
1198 {
1199 kprintf(("_swp_heap_check: error in heap anchor chain.\n"));
1200 Int3();
1201 return FALSE;
1202 }
1203
1204 if ((void*)MINNOTNULL(PDATA(pmbFree), PDATA(pmbUsed)) != pha->pvBlock)
1205 {
1206 kprintf(("_swp_heap_check: The first free/used block don't start at start of memory block.\n"
1207 " PDATA(pmbFree)=0x%08x, PDATA(pmbUsed)=0x%08x, pha->pvBlock=0x%08x\n",
1208 PDATA(pmbFree), PDATA(pmbUsed), pha->pvBlock));
1209 Int3();
1210 return FALSE;
1211 }
1212
1213 /*
1214 * Check the tree AVL-trees - !extra debug test!
1215 */
1216 if (swpCheckAVLTree((PMEMBLOCK)pha->pcoreUsed) != 0)
1217 {
1218 kprintf(("_swp_heap_check: the Used tree is invalid.\n"));
1219 Int3();
1220 return FALSE;
1221 }
1222 if (swpCheckAVLTree((PMEMBLOCK)pha->pcoreFree) != 0)
1223 {
1224 kprintf(("_swp_heap_check: the Free tree is invalid.\n"));
1225 Int3();
1226 return FALSE;
1227 }
1228 if (swpCheckAVLTreeFree(pha->pcoreFreeSize) != 0)
1229 {
1230 kprintf(("_swp_heap_check: the free-size tree is invalid.\n"));
1231 Int3();
1232 return FALSE;
1233 }
1234
1235 /*
1236 * Check the lists
1237 */
1238 while (pmbFree != NULL || pmbUsed != NULL)
1239 {
1240 /** @sketch:
1241 * Check signatures and for lost memory.
1242 *
1243 * three cases:
1244 * 1) pmbUsed adjecent to pmbUsed->pNext
1245 * 2) pmbUsed adjecent to pmbFree
1246 * 3) pmbFree adjecent to pmbFree->pNext
1247 * 4) pmbFree adjecent to pmbUsed
1248 * 5) pmbUsed is the last block
1249 * 6) pmbFree is the last block
1250 */
1251 if (!( (pmbUsed != NULL && PNEXT_BLOCK(pmbUsed) == (AVLKEY)PDATA(pmbUsedNext)) /* 1.*/
1252 || (pmbUsed != NULL && PNEXT_BLOCK(pmbUsed) == (AVLKEY)PDATA(pmbFree)) /* 2.*/
1253 || (pmbFree != NULL && PNEXT_BLOCK(pmbFree) == (AVLKEY)PDATA(pmbFreeNext)) /* 3.*/
1254 || (pmbFree != NULL && PNEXT_BLOCK(pmbFree) == (AVLKEY)PDATA(pmbUsed)) /* 4.*/
1255 || (pmbUsed != NULL && pmbFree == NULL && pmbUsedNext == NULL) /* 5.*/
1256 || (pmbFree != NULL && pmbUsed == NULL && pmbFreeNext == NULL) /* 6.*/
1257 )
1258 )
1259 {
1260 /* error hole */
1261 kprintf(("_swp_heap_check: internal error - memory hole!\n"));
1262 Int3();
1263 return FALSE;
1264 }
1265
1266 /* check signatures and advance to the next block */
1267 if (pmbUsed != NULL && (pmbFree == NULL || pmbUsed->u1.core.Key < pmbFree->u1.core.Key))
1268 {
1269 cbSize += pmbUsed->u2.cbSize;
1270 cbUsed += pmbUsed->u2.cbSize;
1271 if (pmbUsed->u1.puData[0] != SIGNATURE_START)
1272 {
1273 kprintf(("_swp_heap_check: invalid start signature on used block, pv=0x%08x\n", pmbUsed->u1.pvData));
1274 Int3();
1275 return FALSE;
1276 }
1277 if (pmbUsed->u1.puData[(pmbUsed->u2.cbSize / sizeof(unsigned)) - 1] != SIGNATURE_END)
1278 {
1279 kprintf(("_swp_heap_check: invalid end signature on used block, pv=0x%08x\n", pmbUsed->u1.pvData));
1280 Int3();
1281 return FALSE;
1282 }
1283 pmbLast = pmbUsed;
1284 pmbUsed = pmbUsedNext;
1285 pmbUsedNext = (PMEMBLOCK)AVLGetNextNode((PAVLENUMDATA)SSToDS(&UsedEnumData));
1286 }
1287 else
1288 {
1289 PMEMBLOCK pmb = (PMEMBLOCK)AVLGet(&pha->pcoreFreeSize, pmbFree->u2.cbSize);
1290 if (pmb != NULL)
1291 {
1292 pmb = MEMBLOCK_FROM_FREESIZENODE(pmb);
1293 while (pmb != NULL && pmb != pmbFree)
1294 pmb = pmb->pmbNext;
1295 if (pmb == NULL)
1296 {
1297 kprintf(("_swp_heap_check: pmbFree=0x%08 is not found in the free-size-tree.\n", pmbFree));
1298 Int3();
1299 return FALSE;
1300 }
1301 }
1302 else
1303 {
1304 kprintf(("_swp_heap_check: pmbFree=0x%08 is not found in the free-size-tree.\n", pmbFree));
1305 Int3();
1306 return FALSE;
1307 }
1308
1309 cbSize += pmbFree->u2.cbSize;
1310 cbFree += pmbFree->u2.cbSize;
1311 if (pmbFree->u1.puData[0] != SIGNATURE_START)
1312 {
1313 kprintf(("_swp_heap_check: invalid start signature on free block, pv=0x%08x\n", pmbUsed->u1.pvData));
1314 Int3();
1315 return FALSE;
1316 }
1317 if (pmbFree->u1.puData[(pmbFree->u2.cbSize / sizeof(unsigned)) - 1] != SIGNATURE_END)
1318 {
1319 kprintf(("_swp_heap_check: invalid end signature on free block, pv=0x%08x\n", pmbUsed->u1.pvData));
1320 Int3();
1321 return FALSE;
1322 }
1323 pmbLast = pmbFree;
1324 pmbFree = pmbFreeNext;
1325 pmbFreeNext = (PMEMBLOCK)AVLGetNextNode((PAVLENUMDATA)SSToDS(&FreeEnumData));
1326 }
1327 }
1328
1329
1330 /*
1331 * Check the cbFree and cbUsed.
1332 */
1333 if (cbFree != pha->cbFree)
1334 {
1335 kprintf(("_swp_heap_check: cbFree(%d) != pha->cbFree(%d)\n", cbFree, pha->cbFree));
1336 Int3();
1337 return FALSE;
1338 }
1339
1340 if (cbUsed != pha->cbUsed)
1341 {
1342 kprintf(("_swp_heap_check: cbUsed(%d) != pha->cbUsed(%d)\n", cbUsed, pha->cbUsed));
1343 Int3();
1344 return FALSE;
1345 }
1346
1347 if (cbSize != pha->cbSize)
1348 {
1349 kprintf(("_swp_heap_check: cbTotal(%d) != pha->cbSize(%d)\n", cbSize, pha->cbSize));
1350 Int3();
1351 return FALSE;
1352 }
1353 /*
1354 * Check right most node.
1355 */
1356 if (pmbLast == NULL || (unsigned)pha->pvBlock + pha->cbSize != (unsigned)PNEXT_BLOCK(pmbLast))
1357 {
1358 kprintf(("_swp_heap_check: The last free/used block dont end at the end of memory block.\n"
1359 " pmbLast(end)=0x%08x, pha->pvBlock+pha->cbSize=0x%08x\n",
1360 pmbLast != NULL ? PNEXT_BLOCK(pmbLast) : 0, (unsigned)pha->pvBlock + pha->cbSize));
1361 Int3();
1362 return FALSE;
1363 }
1364
1365
1366 /*
1367 * Next heap anchor
1368 */
1369 phaPrev = pha;
1370 pha = pha->pNext;
1371 }
1372
1373 /* check that end of chain is phaLast */
1374 if (phaPrev != phaLast)
1375 {
1376 kprintf(("_swp_heap_check: internal error - heap anchor chain didn't end on phaLast\n"));
1377 Int3();
1378 return FALSE;
1379 }
1380
1381#endif
1382
1383 return TRUE;
1384}
1385
1386#ifdef DEBUG_ALLOC
1387/**
1388 * Check the integrity of the a Free/Used AVL tree where Key == node pointer.
1389 */
1390static int swpCheckAVLTree(PMEMBLOCK pmb)
1391{
1392 if (pmb == NULL)
1393 return 0;
1394 if (pmb->u1.core.Key < 0x10000)
1395 {
1396 kprintf(("swpCheckAVLTree: Invalid Key!\n"));
1397 Int3();
1398 return -1;
1399 }
1400 if (pmb->u1.uData % ALIGNMENT != 0)
1401 {
1402 kprintf(("swpCheckAVLTree: Data is not correctly aligned, uData=0x%08x\n", pmb->u1.uData));
1403 Int3();
1404 return -1;
1405 }
1406 if (pmb->u1.core.pLeft != NULL && (pmb->u1.core.pLeft < (PAVLNODECORE)0x10000
1407 || pmb->u1.core.Key <= (AVLKEY)pmb->u1.core.pLeft->Key))
1408 {
1409 kprintf(("swpCheckAVLTree: Invalid pLeft!\n"));
1410 Int3();
1411 return -1;
1412 }
1413 if (pmb->u1.core.pRight != NULL && (pmb->u1.core.pRight < (PAVLNODECORE)0x10000
1414 || pmb->u1.core.Key >= (AVLKEY)pmb->u1.core.pRight->Key))
1415 {
1416 kprintf(("swpCheckAVLTree: Invalid pRight!\n"));
1417 Int3();
1418 return -1;
1419 }
1420 if (pmb->u1.core.pLeft != NULL && swpCheckAVLTree((PMEMBLOCK)pmb->u1.core.pLeft) != 0)
1421 return -1;
1422 if (pmb->u1.core.pRight != NULL && swpCheckAVLTree((PMEMBLOCK)pmb->u1.core.pRight) != 0)
1423 return -1;
1424 return 0;
1425}
1426
1427
1428/**
1429 * Check the integrity of the a Free/Used AVL tree where Key == node pointer.
1430 */
1431static int swpCheckAVLTreeFree(PAVLNODECORE pNode)
1432{
1433 PMEMBLOCK pmb;
1434
1435 if (pNode == NULL)
1436 return 0;
1437 if (pNode->Key < 4 || (pNode->Key % ALIGNMENT) != 0)
1438 {
1439 kprintf(("swpCheckAVLTreeFree: Invalid Key! 0x%08x\n", pNode->Key));
1440 Int3();
1441 return -1;
1442 }
1443 if (pNode->pLeft != NULL && (pNode->pLeft < (PAVLNODECORE)0x10000 || pNode->Key <= pNode->pLeft->Key))
1444 {
1445 kprintf(("swpCheckAVLTreeFree: Invalid pLeft!\n"));
1446 Int3();
1447 return -1;
1448 }
1449 if (pNode->pRight != NULL && (pNode->pRight < (PAVLNODECORE)0x10000 || pNode->Key >= pNode->pRight->Key))
1450 {
1451 kprintf(("swpCheckAVLTreeFree: Invalid pRight!\n"));
1452 Int3();
1453 return -1;
1454 }
1455 pmb = MEMBLOCK_FROM_FREESIZENODE(pNode);
1456 if (pmb->pmbNext != NULL && pmb->pmbNext < (PMEMBLOCK)0x10000)
1457 {
1458 kprintf(("swpCheckAVLTreeFree: invalid pmbNext pointer, pmbNext=0x%08x\n", pmb->pmbNext));
1459 Int3();
1460 return -1;
1461 }
1462 while (pmb->pmbNext != NULL)
1463 {
1464 if (pmb->pmbNext < (PMEMBLOCK)0x10000)
1465 {
1466 kprintf(("swpCheckAVLTreeFree: invalid pmbNext pointer, pmbNext=0x%08x\n", pmb->pmbNext));
1467 Int3();
1468 return -1;
1469 }
1470 if (pmb->u2.coreFree.Key != pNode->Key)
1471 {
1472 kprintf(("swpCheckAVLTreeFree: invalid key, pmb->coreFree.Key=%d, pNode->Key=%d\n", pmb->u2.coreFree.Key, pNode->Key));
1473 Int3();
1474 return -1;
1475 }
1476 /* next */
1477 pmb = pmb->pmbNext;
1478 }
1479
1480 if (pNode->pLeft != NULL && swpCheckAVLTreeFree(pNode->pLeft) != 0)
1481 return -1;
1482 if (pNode->pRight != NULL && swpCheckAVLTreeFree(pNode->pRight) != 0)
1483 return -1;
1484 return 0;
1485}
1486#endif
1487
1488
1489/**
1490 * Frees unused heapanchors.
1491 */
1492void _swp_heapmin(void)
1493{
1494 PMEMBLOCKCHUNK pmcLast;
1495 PMEMBLOCKCHUNK pmc;
1496 PHEAPANCHOR pha = phaLast;
1497
1498 while (pha != NULL && pha != phaFirst)
1499 {
1500 if (pha->cbUsed == 0)
1501 {
1502 APIRET rc;
1503 PHEAPANCHOR phaToBeFreed = pha;
1504 if (pha->pPrev != NULL)
1505 pha->pPrev->pNext = pha->pNext;
1506 else
1507 phaFirst = pha->pPrev->pNext;
1508 if (pha->pNext != NULL)
1509 pha->pNext->pPrev = pha->pPrev;
1510 else
1511 phaLast = pha->pPrev;
1512 pha = pha->pPrev;
1513
1514 /* free heap */
1515 #ifdef RING0
1516 rc = D32Hlp_VMFree(phaToBeFreed->pvBlock);
1517 #else
1518 rc = DosFreeMem(phaToBeFreed->pvBlock);
1519 #endif
1520 if (rc != NO_ERROR)
1521 kprintf(("_swp_heapmin: DosFreeMem/D32Help_VMFree failed for 0x%08x, rc = %d\n",
1522 pha, rc));
1523 rfree(phaToBeFreed);
1524 }
1525 else
1526 pha = pha->pPrev;
1527 }
1528
1529 pmcLast = NULL;
1530 pmc = pmcFirst;
1531 while (pmc != NULL)
1532 {
1533 #ifdef DEBUG_ALLOC
1534 if (pmc->cFree > MEMBLOCKS_PER_CHUNK)
1535 {
1536 kprintf(("_swp_heapmin: internal heap error - pmc->cFree(%d) > MEMBLOCKS_PER_CHUNK(%d)\n",
1537 pmc->cFree, MEMBLOCKS_PER_CHUNK));
1538 }
1539 #endif
1540 if (pmc->cFree == MEMBLOCKS_PER_CHUNK && pmcLast != NULL)
1541 {
1542 pmcLast->pNext = pmc->pNext;
1543 rfree(pmc);
1544 pmc = pmcLast->pNext;
1545 }
1546 else
1547 {
1548 pmcLast = pmc;
1549 pmc = pmc->pNext;
1550 }
1551 }
1552}
1553
1554
1555/**
1556 * Dumps a summary of the subheaps (heapanchor chain).
1557 */
1558void _swp_dump_subheaps(void)
1559{
1560 PHEAPANCHOR pha;
1561 int i;
1562 unsigned cbTotalFree;
1563 unsigned cTotalFree;
1564 unsigned cbTotalUsed;
1565 unsigned cTotalUsed;
1566
1567 kprintf(("------------------------------------\n"
1568 "- Dumping subheap blocks (summary) -\n"
1569 "------------------------------------\n"
1570 ));
1571
1572 i = 0;
1573 cTotalFree = 0;
1574 cTotalUsed = 0;
1575 cbTotalFree = 0;
1576 cbTotalUsed = 0;
1577 pha = phaFirst;
1578 while (pha != NULL)
1579 {
1580 SUBHEAPS_CALLBACK_PARAM FreeParam = {0, 0};
1581 SUBHEAPS_CALLBACK_PARAM UsedParam = {0, 0};
1582
1583 AVLDoWithAll(&pha->pcoreUsed, 1,
1584 (PAVLCALLBACK)_swp_dump_subheaps_callback, SSToDS(&UsedParam));
1585 AVLDoWithAll(&pha->pcoreFree, 1,
1586 (PAVLCALLBACK)_swp_dump_subheaps_callback, SSToDS(&FreeParam));
1587
1588 kprintf(("HeapAnchor %2d addr=0x%08x cbSize=%6d cbFree=%6d cbUsed=%6d cUsed=%4d cFree=%d\n",
1589 i, pha, pha->cbSize, pha->cbFree, pha->cbUsed, UsedParam.c, FreeParam.c));
1590
1591 cTotalFree += FreeParam.c;
1592 cbTotalFree += FreeParam.cb;
1593 cTotalUsed += UsedParam.c;
1594 cbTotalUsed += UsedParam.cb;
1595
1596 /* next */
1597 pha = pha->pNext;
1598 i++;
1599 }
1600
1601 kprintf(("-----------------------------------------------------------------------------\n"
1602 " Free=%d #Free=%d AverageFree=%d Used=%d #Used=%d AverageUsed=%d\n"
1603 "-----------------------------------------------------------------------------\n",
1604 cbTotalFree, cTotalFree, cTotalFree > 0 ? cbTotalFree / cTotalFree : 0,
1605 cbTotalUsed, cTotalUsed, cTotalUsed > 0 ? cbTotalUsed / cTotalUsed : 0
1606 ));
1607}
1608
1609
1610
1611/**
1612 * Callbackfunction used by _swp_dump_subheaps to summarize a tree.
1613 */
1614static unsigned _swp_dump_subheaps_callback(PMEMBLOCK pmb, PSUBHEAPS_CALLBACK_PARAM pParam)
1615{
1616 pParam->cb += pmb->u2.cbSize;
1617 pParam->c++;
1618 return 0;
1619}
1620
1621
1622/**
1623 * Dumps all allocated memory.
1624 */
1625void _swp_dump_allocated(unsigned cb)
1626{
1627 PHEAPANCHOR pha;
1628 ALLOCATED_CALLBACK_PARAM Param = {cb, 0, 0};
1629
1630 kprintf(("----------------------------\n"
1631 "- Dumping allocated blocks -\n"
1632 "----------------------------\n"));
1633
1634 pha = phaFirst;
1635 while (pha != NULL)
1636 {
1637 /* iterate thru tree using callback */
1638 AVLDoWithAll((PPAVLNODECORE)&pha->pcoreUsed, TRUE,
1639 (PAVLCALLBACK)_swp_dump_allocated_callback, SSToDS(&Param));
1640
1641 /* next */
1642 pha = pha->pNext;
1643 }
1644
1645 kprintf((
1646 "---------------------------------------------\n"
1647 " #Blocks=%6d Allocated=%9d (bytes)\n"
1648 "---------------------------------------------\n",
1649 Param.cBlocks, Param.cbAllocated
1650 ));
1651}
1652
1653/**
1654 * Callback function which dumps a node, and update statistics.
1655 */
1656static unsigned _swp_dump_allocated_callback(PMEMBLOCK pmb, PALLOCATED_CALLBACK_PARAM pParam)
1657{
1658 int i;
1659
1660 pParam->cBlocks++;
1661 pParam->cbAllocated += pmb->u2.cbSize;
1662
1663 kprintf(("pvUserData=0x%08x cbSize=%6d\n",
1664 pmb->u1.pvData, pmb->u2.cbSize
1665 ));
1666 /* dump cb of the block */
1667 i = 0;
1668 while (i < pParam->cb)
1669 {
1670 int j;
1671 char *pachUserData = (char*)pmb->u1.pvData;
1672
1673 /* hex */
1674 j = 0;
1675 while (j < 16)
1676 {
1677 if (j+i < pParam->cb && j+i < pmb->u2.cbSize)
1678 kprintf((" %02x", pachUserData[j+i]));
1679 else
1680 kprintf((" "));
1681 if (j == 7)
1682 kprintf((" -"));
1683 j++;
1684 }
1685
1686 /* ascii */
1687 j = 0;
1688 kprintf((" "));
1689 while (j < 16 && j+i < pmb->u2.cbSize && j+i < pParam->cb)
1690 {
1691 kprintf(("%c", pachUserData[j+i] < 0x20 ? '.' : pachUserData[j+i]));
1692 j++;
1693 }
1694 kprintf(("\n"));
1695 i += j;
1696 }
1697
1698 return 0;
1699}
1700
Note: See TracBrowser for help on using the repository browser.