source: trunk/src/win32k/misc/rmalloc.c@ 2503

Last change on this file since 2503 was 2503, checked in by bird, 26 years ago

Initial resident heap coding completed.
The AVL heap is seems to be much faster; it uses 40% of the time that the
traditional linked-list based heap is using when executing the heaptest.
File size: 31.4 KB
Line 
1/* $Id: rmalloc.c,v 1.2 2000-01-23 03:20:53 bird Exp $
2 *
3 * Resident Heap.
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 knut st. osmundsen
9 *
10 * Project Odin Software License can be found in LICENSE.TXT
11 *
12 */
13
14#define static
15/******************************************************************************
16* Defined macros and constants
17******************************************************************************/
18#ifdef DEBUG
19 #define DEBUG_ALLOC
20 #undef ALLWAYS_HEAPCHECK
21#endif
22
23#define HEAPANCHOR_SIGNATURE 0xBEEFFEEB
24#define MEMBLOCK_SIGNATURE 0xFEEBBEEF
25
26
27/*#define CB_HDR (sizeof(MEMBLOCK) - 1) /* size of MEMBLOCK header (in bytes) */
28#define CB_HDR ((int)&(((PMEMBLOCK)0)->achUserData[0]))
29#define PNEXT_BLOCK(a) ((PMEMBLOCK)((unsigned)(a) + CB_HDR + (a)->cbSize))
30#define BLOCKSIZE (1024*256) /* 256KB */
31
32
33#define MAX(a, b) (((a) > (b))? (a) : (b))
34#define ALIGN(a, alignment) (((a) + (alignment - 1UL)) & ~(alignment - 1UL))
35 /* aligns something, a, up to nearest alignment boundrary-
36 * Note: Aligment must be a 2**n number. */
37
38
39#define INCL_DOS
40#define INCL_DOSERRORS
41#ifdef RING0
42 #define INCL_NOAPI
43#else
44 #define INCL_DOSMEMMGR
45#endif
46
47
48/******************************************************************************
49* Headerfiles
50******************************************************************************/
51#include <os2.h>
52#ifdef RING0
53 #include "dev32hlp.h"
54 #include "asmutils.h"
55#else
56 #include <builtin.h>
57 #define Int3() __interrupt(3)
58#endif
59#include "log.h"
60#include "rmalloc.h"
61#include <memory.h>
62#include "dev32.h"
63#include "macros.h"
64
65
66/******************************************************************************
67* Structs and Typedefs
68******************************************************************************/
69typedef struct _MEMBLOCK /* MB */
70{
71 #ifdef DEBUG_ALLOC
72 unsigned long ulSignature; /* Contains MEMBLOCK_SIGNATURE (0xFEEBBEEF) */
73 #endif
74 unsigned cbSize; /* Size of user space (achBlock)*/
75 struct _MEMBLOCK * pNext; /* Pointer to the next memblock. */
76 unsigned char achUserData[1]; /* User data */
77} MEMBLOCK, *PMEMBLOCK;
78
79
80typedef struct _HeapAnchor /* HA */
81{
82 #ifdef DEBUG_ALLOC
83 unsigned long ulSignature; /* Contains HEAPANCHOR_SIGNATURE */
84 #endif
85 unsigned cbSize; /* Total amount of memory in this block. */
86 struct _HeapAnchor *pNext; /* Pointer to the next anchor block. */
87 struct _HeapAnchor *pPrev; /* Pointer to the previous anchor block. */
88 PMEMBLOCK pmbFree; /* Pointer to the used-memblock chain. */
89 unsigned cbFree; /* Amount of free memory. */
90 PMEMBLOCK pmbUsed; /* Pointer to the used-memblock chain. */
91 unsigned cbUsed; /* Amount of used memory. */
92
93} HEAPANCHOR, *PHEAPANCHOR;
94
95
96
97
98/******************************************************************************
99* Global data
100******************************************************************************/
101static PHEAPANCHOR phaFirst; /* Pointer to the first anchor block.*/
102static PHEAPANCHOR phaLast; /* Pointer to the first anchor block.*/
103static unsigned cbResHeapMax; /* Maximum amount of memory used by the heap. */
104
105#ifndef RING0
106char fResInited; /* init flag */
107#endif
108
109
110/******************************************************************************
111* Internal functions
112******************************************************************************/
113static void resInsertUsed(PHEAPANCHOR pha, PMEMBLOCK pmb);
114static void resInsertFree(PHEAPANCHOR pha, PMEMBLOCK pmb);
115static PMEMBLOCK resGetFreeMemblock(PHEAPANCHOR *ppha, unsigned cbUserSize);
116static PMEMBLOCK resFindUsedBlock(PHEAPANCHOR *ppha, void *pvUser, int fWithin);
117
118
119/**
120 * Inserts a memblock into the used chain.
121 * @param pha Pointer to the heap anchor which the block is to be inserted into.
122 * @param pmb Pointer to memblock to insert into the free list.
123 * @remark Sorts on address.
124 */
125static void resInsertUsed(PHEAPANCHOR pha, PMEMBLOCK pmb)
126{
127 if (pha->pmbUsed == NULL || pha->pmbUsed > pmb)
128 {
129 pmb->pNext = pha->pmbUsed;
130 pha->pmbUsed = pmb;
131 }
132 else
133 {
134 PMEMBLOCK pmbTmp = pha->pmbUsed;
135 while (pmbTmp->pNext != NULL && pmbTmp->pNext < pmb)
136 pmbTmp = pmbTmp->pNext;
137
138 pmb->pNext = pmbTmp->pNext;
139 pmbTmp->pNext= pmb;
140 }
141}
142
143
144/**
145 * Inserts a memblock into the free chain.
146 * Merges blocks adjecent blocks.
147 * @param pha Pointer to the heap anchor which the block is to be inserted into.
148 * @param pmb Pointer to memblock to insert into the free list.
149 * @remark Sorts on address.
150 */
151static void resInsertFree(PHEAPANCHOR pha, PMEMBLOCK pmb)
152{
153 pha->cbFree += pmb->cbSize;
154 if (pmb < pha->pmbFree || pha->pmbFree == NULL)
155 {
156 /* test for merge with first block */
157 if (pha->pmbFree != NULL && PNEXT_BLOCK(pmb) == pha->pmbFree)
158 {
159 pha->cbFree += CB_HDR;
160 pmb->cbSize += CB_HDR + pha->pmbFree->cbSize;
161 pmb->pNext = pha->pmbFree->pNext;
162 #ifdef DEBUG_ALLOC
163 pha->pmbFree->ulSignature = 0xF0EEEE0F;
164 pha->pmbFree->pNext = (void*)~0;
165 #endif
166 }
167 else
168 pmb->pNext = pha->pmbFree;
169 pha->pmbFree = pmb;
170 }
171 else
172 {
173 PMEMBLOCK pmbTmp = pha->pmbFree;
174 while (pmbTmp->pNext != NULL && pmbTmp->pNext < pmb)
175 pmbTmp = pmbTmp->pNext;
176
177 /* test for merge with left block */
178 if (PNEXT_BLOCK(pmbTmp) == pmb)
179 {
180 pmbTmp->cbSize += CB_HDR + pmb->cbSize;
181 pha->cbFree += CB_HDR;
182 #ifdef DEBUG_ALLOC
183 pmb->ulSignature = 0xF0EEEE0F;
184 pmb->pNext = (void*)~0;
185 #endif
186 pmb = pmbTmp;
187 }
188 else
189 {
190 pmb->pNext = pmbTmp->pNext;
191 pmbTmp->pNext = pmb;
192 }
193
194 /* test for merge with right block */
195 if (pmb->pNext != NULL && PNEXT_BLOCK(pmb) == pmb->pNext)
196 {
197 pmb->cbSize += CB_HDR + pmb->pNext->cbSize;
198 pha->cbFree += CB_HDR;
199 #ifdef DEBUG_ALLOC
200 pmb->pNext->ulSignature = 0xF0EEEE0F;
201 #endif
202 pmb->pNext = pmb->pNext->pNext;
203 }
204 }
205}
206
207
208/**
209 * Finds a free block at the requested size.
210 * @returns Pointer to block (not in free list any longer).
211 * @param ppha Upon return the pointer pointed to contains the heap
212 * anchor which the memory block was allocated from.
213 * @param cbUserSize Bytes the user have requested.
214 * @sketch cbUserSize is aligned to nearest 4 bytes.
215 * ...
216 *
217 */
218static PMEMBLOCK resGetFreeMemblock(PHEAPANCHOR *ppha, unsigned cbUserSize)
219{
220 unsigned cbBlockSize;
221 unsigned cbTotalSize = 0;
222
223 cbUserSize = (cbUserSize + 3) & ~3;
224 *ppha = phaFirst;
225 while (*ppha != NULL)
226 {
227 if ((*ppha)->cbFree >= cbUserSize + CB_HDR)
228 {
229 PMEMBLOCK pmbBestFit = NULL;
230 PMEMBLOCK pmbBestFitPrev = NULL;
231 PMEMBLOCK pmbCur = (*ppha)->pmbFree;
232 PMEMBLOCK pmbPrev = NULL;
233
234 /* search for block */
235 while (pmbCur != NULL)
236 {
237 /* check for perfect match first */
238 if (pmbCur->cbSize == cbUserSize)
239 break;
240 /* TODO: The following test may need to be adjusted later. */
241 else if (pmbCur->cbSize >= cbUserSize
242 && (pmbBestFit == NULL || pmbCur->cbSize < pmbBestFit->cbSize)
243 )
244 {
245 pmbBestFit = pmbCur;
246 pmbBestFitPrev = pmbPrev;
247 }
248
249 /* next */
250 pmbPrev = pmbCur;
251 pmbCur = pmbCur->pNext;
252 }
253
254 /* link out block */
255 if (pmbCur != NULL)
256 { /* prefect match */
257 if (pmbPrev != NULL)
258 pmbPrev->pNext = pmbCur->pNext;
259 else
260 (*ppha)->pmbFree = pmbCur->pNext;
261
262 (*ppha)->cbFree -= cbUserSize;
263 (*ppha)->cbUsed += cbUserSize;
264 }
265 else if (pmbBestFit != NULL)
266 { /* best fit */
267 /* two cases 1) split block. 2) block is too small to be splitted. */
268 if (pmbBestFit->cbSize > cbUserSize + CB_HDR)
269 {
270 pmbCur = (PMEMBLOCK)((unsigned)pmbBestFit + pmbBestFit->cbSize - cbUserSize);
271 #ifdef DEBUG_ALLOC
272 pmbCur->ulSignature = MEMBLOCK_SIGNATURE;
273 #endif
274 pmbCur->cbSize = cbUserSize;
275 pmbBestFit->cbSize -= cbUserSize + CB_HDR;
276
277 (*ppha)->cbFree -= cbUserSize + CB_HDR;
278 (*ppha)->cbUsed += cbUserSize;
279 }
280 else
281 {
282 if (pmbBestFitPrev != NULL)
283 pmbBestFitPrev->pNext = pmbBestFit->pNext;
284 else
285 (*ppha)->pmbFree = pmbBestFit->pNext;
286 pmbCur = pmbBestFit;
287
288 (*ppha)->cbFree -= pmbCur->cbSize;
289 (*ppha)->cbUsed += pmbCur->cbSize;
290 }
291 }
292
293 if (pmbCur != NULL)
294 return pmbCur;
295 }
296
297 cbTotalSize += (*ppha)->cbSize;
298
299 /* next heap anchor */
300 *ppha = (*ppha)->pNext;
301 }
302
303 /* add a new heap anchor? */
304 cbBlockSize = ALIGN(cbUserSize + CB_HDR * 2, BLOCKSIZE);
305 if (cbResHeapMax >= cbTotalSize + cbBlockSize)
306 {
307 #ifdef RING0
308 *ppha = D32Hlp_VMAlloc(0UL, cbBlockSize, ~0UL);
309 #else
310 if (DosAllocMem((void*)ppha, cbBlockSize, PAG_COMMIT | PAG_READ | PAG_WRITE) != 0)
311 *ppha = NULL;
312 #endif
313
314 if (*ppha != NULL)
315 {
316 register PHEAPANCHOR pha = *ppha;
317 PMEMBLOCK pmb;
318
319 /* anchor block */
320 #ifdef DEBUG_ALLOC
321 pha->ulSignature = HEAPANCHOR_SIGNATURE;
322 #endif
323 pha->cbSize = cbBlockSize;
324 pha->pmbUsed = NULL;
325 pha->cbUsed = cbUserSize;
326
327 /* free memblock */
328 pha->pmbFree = (PMEMBLOCK)((unsigned)pha + sizeof(*pha));
329 pha->cbFree = cbBlockSize - sizeof(*pha) - CB_HDR * 2 - cbUserSize;
330 #ifdef DEBUG_ALLOC
331 pha->pmbFree->ulSignature = MEMBLOCK_SIGNATURE;
332 #endif
333 pha->pmbFree->cbSize = pha->cbFree;
334 pha->pmbFree->pNext = NULL;
335
336 /* used memblock */
337 pmb = (PMEMBLOCK)((unsigned)pha + cbBlockSize - cbUserSize - CB_HDR);
338 #ifdef DEBUG_ALLOC
339 pmb->ulSignature = MEMBLOCK_SIGNATURE;
340 #endif
341 pmb->cbSize = cbUserSize;
342 pmb->pNext = NULL;
343
344 /* insert into list */
345 pha->pPrev = phaLast;
346 pha->pNext = NULL;
347 if (phaLast == NULL) /* Might never happen but just in case it does. */
348 phaLast = phaFirst = pha;
349 else
350 phaLast->pNext = pha;
351 phaLast = pha;
352
353 return pmb;
354 }
355 else
356 kprintf(("resGetFreeMemblock: Unable to allocate heap memory.\n"));
357 }
358 else
359 {
360 kprintf(("resGetFreeMemblock: Allocation failed, limit reached. \n"
361 " %d(=cbResHeapMax) < %d(=cbTotalSize) + %d(=cbBlockSize)\n",
362 cbResHeapMax, cbTotalSize, cbBlockSize));
363 }
364
365 return NULL;
366}
367
368
369/**
370 * Finds a used memory block.
371 * @returns Pointer to memblock if found.
372 * @param ppha Pointer to pointer to heap anchor block the returned memblock is located in. (output)
373 * @param pvUser User pointer to find the block to.
374 * @param fWithin When this flag is set, the pointer may point anywhere within the block.
375 * When clear, it has to point exactly at the start of the user data area.
376 */
377static PMEMBLOCK resFindUsedBlock(PHEAPANCHOR *ppha, void *pvUser, int fWithin)
378{
379 PMEMBLOCK pmb;
380
381 if (pvUser != NULL && ppha != NULL)
382 {
383 register PHEAPANCHOR pha = phaFirst;
384 while (pha != NULL
385 && !((unsigned)pvUser > (unsigned)pha
386 && (unsigned)pvUser < (unsigned)pha + pha->cbSize))
387 pha = pha->pNext;
388
389 if (pha != NULL)
390 {
391 #ifdef DEBUG_ALLOC
392 if (pha->ulSignature != HEAPANCHOR_SIGNATURE)
393 {
394 kprintf(("resFindUsedBlock: Invalid heapanchor signature.\n"));
395 return NULL;
396 }
397 #endif
398 *ppha = pha;
399 pmb = pha->pmbUsed;
400
401 if (fWithin)
402 {
403 while (pmb != NULL && !(pvUser >= (void*)pmb && pvUser < (void*)PNEXT_BLOCK(pmb)))
404 pmb = pmb->pNext;
405 }
406 else
407 {
408 pvUser = (void*)((unsigned)pvUser - CB_HDR);
409 while (pmb != NULL && pvUser != (void*)pmb)
410 pmb = pmb->pNext;
411 }
412 #ifdef DEBUG_ALLOC
413 if (pmb != NULL && pmb->ulSignature != MEMBLOCK_SIGNATURE)
414 {
415 kprintf(("resFindUsedBlock: Invalid memoryblock signature.\n"));
416 pmb = NULL;
417 }
418 #endif
419 }
420 else
421 pmb = NULL;
422 }
423 else
424 pmb = NULL;
425
426 return pmb;
427}
428
429
430/**
431 * Initiate the heap "subsystem".
432 * @returns 0 on success, not 0 on error.
433 * @param cbSizeInit The initial size of the heap in bytes.
434 * @param cbSizeMax Maximum heapsize in bytes.
435 */
436int ResHeapInit(unsigned cbSizeInit, unsigned cbSizeMax)
437{
438 unsigned cbSize = MAX(BLOCKSIZE, cbSizeInit);
439
440 cbResHeapMax = cbSizeMax;
441
442 #ifdef RING0
443 phaFirst = D32Hlp_VMAlloc(0UL, cbSize, ~0UL);
444 #else
445 if (DosAllocMem((void*)&phaFirst, cbSize, PAG_COMMIT | PAG_READ | PAG_WRITE) != 0)
446 phaFirst = NULL;
447 #endif
448 if (phaFirst == NULL)
449 {
450 kprintf(("unable to allocate heap memory.\n"));
451 Int3();
452 return -1;
453 }
454
455 #ifdef DEBUG_ALLOC
456 phaFirst->ulSignature = HEAPANCHOR_SIGNATURE;
457 #endif
458 phaFirst->cbSize = cbSize;
459 phaFirst->pNext = NULL;
460 phaFirst->pPrev = NULL;
461 phaFirst->pmbUsed = NULL;
462 phaFirst->cbUsed = 0UL;
463 phaFirst->pmbFree = (PMEMBLOCK)((unsigned)phaFirst+sizeof(*phaFirst));
464 phaFirst->cbFree = cbSize - sizeof(*phaFirst) - CB_HDR;
465
466 #ifdef DEBUG_ALLOC
467 phaFirst->pmbFree->ulSignature = MEMBLOCK_SIGNATURE;
468 #endif
469 phaFirst->pmbFree->cbSize = phaFirst->cbFree;
470 phaFirst->pmbFree->pNext = NULL;
471 phaLast = phaFirst;
472
473 #ifdef ALLWAYS_HEAPCHECK
474 if (!_res_heap_check())
475 {
476 /* error! */
477 kprintf(("%s: _res_heap_check failed!\n", "heapInit"));
478 Int3();
479 return -2;
480 }
481 #endif
482 #ifdef RING3
483 fInited = TRUE;
484 #endif
485 return 0;
486}
487
488
489/**
490 * malloc - allocates a given amount of memory.
491 * @returns Pointer to allocated memory.
492 * NULL if out of memory. (Or memory to fragmented.)
493 * @param cbSize Bytes user requests us to allocate. This is aligned
494 * to four bytes.
495 */
496void * rmalloc(unsigned cbSize)
497{
498 void *pvRet = NULL;
499
500 #ifdef ALLWAYS_HEAPCHECK
501 if (!_res_heap_check())
502 {
503 kprintf(("rmalloc: _res_heap_check failed!\n"));
504 return NULL;
505 }
506 #endif
507
508 if (cbSize != 0)
509 {
510 PHEAPANCHOR pha;
511 PMEMBLOCK pmb = resGetFreeMemblock(SSToDS(&pha), cbSize);
512 if (pmb != NULL)
513 {
514 resInsertUsed(pha, pmb);
515 pvRet = &pmb->achUserData[0];
516 }
517 }
518 else
519 { /* error! */
520 kprintf(("rmalloc: error cbSize = 0\n"));
521 }
522
523 return pvRet;
524}
525
526
527/**
528 * Reallocate a heapblock.
529 * @returns Pointer to new heapblock.
530 * @param pv Pointer to the block to realloc.
531 * @param cbNew The new block size.
532 */
533void *rrealloc(void *pv, unsigned cbNew)
534{
535 PMEMBLOCK pmb;
536 PHEAPANCHOR pha;
537
538 pmb = resFindUsedBlock(SSToDS(&pha), pv, FALSE);
539 if (pmb != NULL)
540 {
541 void *pvRet;
542
543 cbNew = ALIGN(cbNew, 4);
544 if (cbNew <= pmb->cbSize)
545 { /* shrink block */
546 pvRet = pv;
547 if (cbNew + CB_HDR < pmb->cbSize)
548 { /* split block */
549 PMEMBLOCK pmbNew = (PMEMBLOCK)((unsigned)pmb + CB_HDR + cbNew);
550 #ifdef DEBUG_ALLOC
551 pmbNew->ulSignature = MEMBLOCK_SIGNATURE;
552 #endif
553 pmbNew->cbSize = pmb->cbSize - cbNew - CB_HDR;
554 pmbNew->pNext = NULL;
555 pha->cbUsed -= pmb->cbSize - cbNew;
556 pmb->cbSize = cbNew;
557 resInsertFree(pha, pmbNew);
558 }
559 }
560 else
561 { /* expand block - this code may be more optimized... */
562 pvRet = rmalloc(cbNew);
563 if (pvRet != NULL)
564 {
565 memcpy(pvRet, pv, pmb->cbSize);
566 rfree(pv);
567 }
568 }
569 return pvRet;
570 }
571 return NULL;
572}
573
574
575/**
576 * Frees a block.
577 * @param pv User pointer.
578 */
579void rfree(void *pv)
580{
581 #ifdef ALLWAYS_HEAPCHECK
582 if (!_res_heap_check())
583 {
584 kprintf(("rfree: _res_heap_check failed!\n"));
585 return;
586 }
587 #endif
588
589 if (pv != NULL)
590 {
591 PHEAPANCHOR pha = phaFirst;
592
593 while (pha != NULL
594 && !((unsigned)pv > (unsigned)pha
595 && (unsigned)pv < (unsigned)pha + pha->cbSize))
596 pha = pha->pNext;
597
598 if (pha != NULL)
599 {
600 PMEMBLOCK pmbCur = pha->pmbUsed;
601 PMEMBLOCK pmbPrev = NULL;
602 pv = (void*)((unsigned)pv - CB_HDR);
603
604 while (pmbCur != NULL &&
605 #ifdef DEBUG_ALLOC /* pointer within block */
606 !(pv >= (void*)pmbCur && (void*)((unsigned)pv + CB_HDR) < (void*)PNEXT_BLOCK(pmbCur))
607 #else
608 pv != (void*)pmbCur
609 #endif
610 )
611 {
612 pmbPrev = pmbCur;
613 pmbCur = pmbCur->pNext;
614 }
615
616 if (pmbCur != NULL)
617 {
618 #ifdef DEBUG_ALLOC
619 if (pmbCur->ulSignature != MEMBLOCK_SIGNATURE)
620 {
621 kprintf(("rfree: Invalid memoryblock signature - pmbCur\n"));
622 return;
623 }
624 if (pmbPrev != NULL && pmbPrev->ulSignature != MEMBLOCK_SIGNATURE)
625 {
626 kprintf(("rfree: Invalid memoryblock signature - pmbPrev\n"));
627 return;
628 }
629 #endif
630 if (pv == pmbCur)
631 {
632 if (pmbPrev != NULL)
633 pmbPrev->pNext = pmbCur->pNext;
634 else
635 pha->pmbUsed = pmbCur->pNext;
636 pha->cbUsed -= pmbCur->cbSize;
637
638 resInsertFree(pha, pmbCur);
639
640 #ifdef ALLWAYS_HEAPCHECK
641 if (!_res_heap_check())
642 kprintf(("rfree: _res_heap_check failed 3!\n"));
643 #endif
644 }
645 else
646 kprintf(("rfree: pv is not pointing to start of block.\n"));
647 }
648 else
649 kprintf(("rfree: heap block not found!\n"));
650 }
651 else
652 kprintf(("rfree: heap block not within the large blocks!\n"));
653 }
654 else
655 kprintf(("rfree: Free received a NULL pointer!\n"));
656}
657
658
659/**
660 * Gets the size of a block.
661 * @returns Bytes in a block.
662 */
663unsigned _res_msize(void *pv)
664{
665 PHEAPANCHOR pha;
666 PMEMBLOCK pmb;
667
668 #ifdef ALLWAYS_HEAPCHECK
669 if (!_res_heap_check())
670 kprintf(("_msize: _res_heap_check failed!\n"));
671 #endif
672
673 pmb = resFindUsedBlock(SSToDS(&pha), pv, FALSE);
674 return pmb != NULL ? pmb->cbSize : 0;
675}
676
677
678/**
679 * Checks if pv is a valid heappointer.
680 * @returns 1 if valid. 0 if invalid.
681 * @param pv User data pointer.
682 */
683int _res_validptr(void *pv)
684{
685 PHEAPANCHOR pha;
686 PMEMBLOCK pmb;
687
688 #ifdef ALLWAYS_HEAPCHECK
689 if (!_res_heap_check())
690 kprintf(("_validptr: _res_heap_check failed!\n"));
691 #endif
692
693 pmb = resFindUsedBlock(SSToDS(&pha), pv, TRUE);
694 return pmb != NULL;
695}
696
697
698/**
699 * Checks that the dataaera made up by pv and cbSize valid with in the heap.
700 * @returns 1 if valid. 0 if invalid.
701 * @param pv User data pointer.
702 * @param cbSize Size of data which has to be valid.
703 */
704int _res_validptr2(void *pv, unsigned cbSize)
705{
706 PHEAPANCHOR pha;
707 PMEMBLOCK pmb;
708
709 #ifdef ALLWAYS_HEAPCHECK
710 if (!_res_heap_check())
711 kprintf(("_validptr: _res_heap_check failed!\n"));
712 #endif
713
714 pmb = resFindUsedBlock(SSToDS(&pha), pv, TRUE);
715 return pmb != NULL ? (pmb->cbSize - ((unsigned)pv - (unsigned)pmb - CB_HDR)) >= cbSize : FALSE;
716}
717
718
719/**
720 * Get amount of free memory (in bytes)
721 * @returns Amount of free memory (in bytes).
722 * @remark Note that this amount is of all free memory blocks and
723 * that these blocks are fragmented.
724 * You'll probably not be able to allocate a single block
725 * of the returned size.
726 */
727unsigned _res_memfree(void)
728{
729 PHEAPANCHOR pha = phaFirst;
730 unsigned cb;
731
732 #ifdef ALLWAYS_HEAPCHECK
733 if (!_res_heap_check())
734 kprintf(("res_memfree: _res_heap_check failed!\n"));
735 #endif
736
737 for (cb = 0; pha != NULL; pha = pha->pNext)
738 cb += pha->cbFree;
739
740 return cb;
741}
742
743
744/**
745 * Checks heap integrety.
746 * @returns TRUE when ok.
747 * FALSE on error.
748 * NULL if out of memory. (Or memory to fragmented.)
749 */
750int _res_heap_check(void)
751{
752#ifdef DEBUG_ALLOC
753 PHEAPANCHOR pha = phaFirst;
754 PHEAPANCHOR phaPrev = NULL;
755
756
757 while (pha != NULL)
758 {
759 PMEMBLOCK pmbFree = pha->pmbFree;
760 PMEMBLOCK pmbUsed = pha->pmbUsed;
761 PMEMBLOCK pmbLast = NULL;
762 unsigned cbFree = 0;
763 unsigned cbUsed = 0;
764 unsigned cbSize = sizeof(*pha);
765
766 /*
767 * Check the heap anchor.
768 */
769 if (pha->ulSignature != HEAPANCHOR_SIGNATURE)
770 {
771 kprintf(("_res_heap_check: invalid signature for pha=0x%08x\n", pha));
772 return FALSE;
773 }
774
775 if (pha->cbFree + pha->cbUsed >= pha->cbSize || pha->cbSize == 0)
776 {
777 kprintf(("_res_heap_check: cbFree + cbUsed >= cbSize for pha=0x%08x\n", pha));
778 return FALSE;
779 }
780
781 if (pha->pPrev != phaPrev)
782 {
783 kprintf(("_res_heap_check: internal error - error in heap anchor chain.\n"));
784 return FALSE;
785 }
786
787 if ((unsigned)MINNOTNULL(pmbFree, pmbUsed) != (unsigned)(pha+1))
788 {
789 kprintf(("_res_heap_check: The first free/used block don't start at start of memory\n"
790 " block. pmbFree=0x%08x, pmbUsed=0x%08x, pha+1=0x%08x\n",
791 pmbFree, pmbUsed, pha+1));
792 return FALSE;
793 }
794
795
796 /*
797 * Check the lists
798 */
799 while (pmbFree != NULL || pmbUsed != NULL)
800 {
801 /** @sketch:
802 * Check signatures and for lost memory.
803 *
804 * three cases:
805 * 1) pmbUsed adjecent to pmbUsed->pNext
806 * 2) pmbUsed adjecent to pmbFree
807 * 3) pmbFree adjecent to pmbFree->pNext
808 * 4) pmbFree adjecent to pmbUsed
809 * 5) pmbUsed is the last block
810 * 6) pmbFree is the last block
811 */
812 if (!( (pmbUsed != NULL && PNEXT_BLOCK(pmbUsed) == pmbUsed->pNext) /* 1.*/
813 || (pmbUsed != NULL && PNEXT_BLOCK(pmbUsed) == pmbFree) /* 2.*/
814 || (pmbFree != NULL && PNEXT_BLOCK(pmbFree) == pmbFree->pNext) /* 3.*/
815 || (pmbFree != NULL && PNEXT_BLOCK(pmbFree) == pmbUsed) /* 4.*/
816 || (pmbUsed != NULL && pmbFree == NULL && pmbUsed->pNext == NULL) /* 5.*/
817 || (pmbFree != NULL && pmbUsed == NULL && pmbFree->pNext == NULL) /* 6.*/
818 )
819 )
820 {
821 /* error hole */
822 kprintf(("_res_heap_check: internal error - memory hole!\n"));
823 return FALSE;
824 }
825
826 /* check signature and advance to the next block */
827 if (pmbUsed != NULL && (pmbFree == NULL || pmbUsed < pmbFree))
828 {
829 cbSize += CB_HDR + pmbUsed->cbSize;
830 cbUsed += pmbUsed->cbSize;
831 if (pmbUsed->ulSignature != MEMBLOCK_SIGNATURE)
832 return FALSE;
833 pmbLast = pmbUsed;
834 pmbUsed = pmbUsed->pNext;
835 }
836 else
837 {
838 cbSize += CB_HDR + pmbFree->cbSize;
839 cbFree += pmbFree->cbSize;
840 if (pmbFree->ulSignature != MEMBLOCK_SIGNATURE)
841 return FALSE;
842 pmbLast = pmbFree;
843 pmbFree = pmbFree->pNext;
844 }
845 }
846
847
848 /*
849 * Check the cbFree and cbUsed.
850 */
851 if (cbFree != pha->cbFree)
852 {
853 kprintf(("_res_heap_check: cbFree(%d) != pha->cbFree(%d)\n", cbFree, pha->cbFree));
854 return FALSE;
855 }
856
857 if (cbUsed != pha->cbUsed)
858 {
859 kprintf(("_res_heap_check: cbUsed(%d) != pha->cbUsed(%d)\n", cbUsed, pha->cbUsed));
860 return FALSE;
861 }
862
863 if (cbSize != pha->cbSize)
864 {
865 kprintf(("_res_heap_check: cbTotal(%d) != pha->cbSize(%d)\n", cbSize, pha->cbSize));
866 return FALSE;
867 }
868 /*
869 * Check right most node.
870 */
871 if (pmbLast == NULL || (unsigned)pha + pha->cbSize != (unsigned)PNEXT_BLOCK(pmbLast))
872 {
873 kprintf(("_res_heap_check: The last free/used block dont end at the end of memory block.\n"
874 " pmbLast(end)=0x%08x, pha+pha->cbSize=0x%08x\n",
875 pmbLast != NULL ? PNEXT_BLOCK(pmbLast) : NULL, (unsigned)pha + pha->cbSize));
876 return FALSE;
877 }
878
879
880 /*
881 * Next heap anchor
882 */
883 phaPrev = pha;
884 pha = pha->pNext;
885 }
886
887 /* check that end of chain is phaLast */
888 if (phaPrev != phaLast)
889 {
890 kprintf(("_res_heap_check: internal error - heap anchor chain didn't end on phaLast\n"));
891 return FALSE;
892 }
893
894#endif
895
896 return TRUE;
897}
898
899
900
901/**
902 * Frees unused heapanchors.
903 */
904void _res_heapmin(void)
905{
906 PHEAPANCHOR pha = phaLast;
907
908 while (pha != NULL && pha != phaFirst)
909 {
910 if (pha->cbUsed == 0)
911 {
912 APIRET rc;
913 PHEAPANCHOR phaToBeFreed = pha;
914 if (pha->pPrev != NULL)
915 pha->pPrev->pNext = pha->pNext;
916 else
917 phaFirst = pha->pPrev->pNext;
918 if (pha->pNext != NULL)
919 pha->pNext->pPrev = pha->pPrev;
920 else
921 phaLast = pha->pPrev;
922 pha = pha->pPrev;
923
924 /* free heap */
925 #ifdef RING0
926 rc = D32Hlp_VMFree(phaToBeFreed);
927 #else
928 rc = DosFreeMem(phaToBeFreed);
929 #endif
930 if (rc != NO_ERROR)
931 kprintf(("_res_heapmin: DosFreeMem failed for pha=0x%08x, rc = %d\n",
932 pha, rc));
933 }
934 else
935 pha = pha->pPrev;
936 }
937}
938
939
940/**
941 * Dumps a summary of the subheaps (heapanchor chain).
942 */
943void _res_dump_subheaps(void)
944{
945 PHEAPANCHOR pha;
946 int i;
947 unsigned cbTotalFree;
948 unsigned cTotalFree;
949 unsigned cbTotalUsed;
950 unsigned cTotalUsed;
951
952 kprintf(("------------------------------------\n"
953 "- Dumping subheap blocks (summary) -\n"
954 "------------------------------------\n"
955 ));
956
957 i = 0;
958 cTotalFree = 0;
959 cTotalUsed = 0;
960 cbTotalFree = 0;
961 cbTotalUsed = 0;
962 pha = phaFirst;
963 while (pha != NULL)
964 {
965 PMEMBLOCK pmb;
966 unsigned cbFree = 0;
967 unsigned cFree = 0;
968 unsigned cbUsed = 0;
969 unsigned cUsed = 0;
970
971
972 pmb = pha->pmbUsed;
973 while (pmb != NULL)
974 {
975 cUsed++;
976 cbUsed += pmb->cbSize;
977 pmb = pmb->pNext;
978 }
979
980 pmb = pha->pmbFree;
981 while (pmb != NULL)
982 {
983 cFree++;
984 cbFree += pmb->cbSize;
985 pmb = pmb->pNext;
986 }
987
988 kprintf(("HeapAnchor %2d addr=0x%08x cbSize=%6d cbFree=%6d cbUsed=%6d cUsed=%4d cFree=%d\n",
989 i, pha, pha->cbSize, pha->cbFree, pha->cbUsed, cUsed, cFree));
990
991 cTotalFree += cFree;
992 cbTotalFree += cbFree;
993 cTotalUsed += cUsed;
994 cbTotalUsed += cbUsed;
995
996 /* next */
997 pha = pha->pNext;
998 i++;
999 }
1000
1001 kprintf(("-----------------------------------------------------------------------------\n"
1002 " Free=%d #Free=%d AverageFree=%d Used=%d #Used=%d AverageUsed=%d\n"
1003 "-----------------------------------------------------------------------------\n",
1004 cbTotalFree, cTotalFree, cTotalFree > 0 ? cbTotalFree / cTotalFree : 0,
1005 cbTotalUsed, cTotalUsed, cTotalUsed > 0 ? cbTotalUsed / cTotalUsed : 0
1006 ));
1007}
1008
1009
1010/**
1011 * Dumps all allocated memory.
1012 */
1013void _res_dump_allocated(unsigned cb)
1014{
1015 PHEAPANCHOR pha;
1016 unsigned cBlocks;
1017 unsigned cbAllocated;
1018
1019 kprintf(("----------------------------\n"
1020 "- Dumping allocated blocks -\n"
1021 "----------------------------\n"));
1022
1023 cBlocks = 0;
1024 cbAllocated = 0;
1025 pha = phaFirst;
1026 while (pha != NULL)
1027 {
1028 PMEMBLOCK pmb = pha->pmbUsed;
1029 while (pmb != NULL)
1030 {
1031 int i;
1032 cBlocks++;
1033 cbAllocated += pmb->cbSize;
1034
1035 kprintf(("pvUserData=0x%08x cbSize=%6d\n",
1036 &pmb->achUserData[0], pmb->cbSize
1037 ));
1038 /* dump cb of the block */
1039 i = 0;
1040 while (i < cb)
1041 {
1042 int j;
1043
1044 /* hex */
1045 j = 0;
1046 while (j < 16)
1047 {
1048 if (j+i < cb && j+i < pmb->cbSize)
1049 kprintf((" %02x", pmb->achUserData[j+i]));
1050 else
1051 kprintf((" "));
1052 if (j == 7)
1053 kprintf((" -"));
1054 j++;
1055 }
1056
1057 /* ascii */
1058 j = 0;
1059 kprintf((" "));
1060 while (j < 16 && j+i < pmb->cbSize && j+i < cb)
1061 {
1062 kprintf(("%c", pmb->achUserData[j+i] < 0x20 ? '.' : pmb->achUserData[j+i]));
1063 j++;
1064 }
1065 kprintf(("\n"));
1066 i += j;
1067 }
1068
1069 /* next */
1070 pmb = pmb->pNext;
1071 }
1072
1073 /* next */
1074 pha = pha->pNext;
1075 }
1076
1077 kprintf((
1078 "---------------------------------------------\n"
1079 " #Blocks=%6d Allocated=%9d (bytes)\n"
1080 "---------------------------------------------\n",
1081 cBlocks, cbAllocated
1082 ));
1083
1084}
Note: See TracBrowser for help on using the repository browser.