source: trunk/src/win32k/misc/malloc.c@ 1536

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

Correcte a few bug rearding HEAP_SIZE and Yield.h
File size: 17.0 KB
Line 
1/* $Id: malloc.c,v 1.4 1999-11-01 09:28:58 bird Exp $
2 *
3 * 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 */
11
12#define static
13/******************************************************************************
14* Defined macros and constants
15******************************************************************************/
16#ifdef DEBUG
17 #define DEBUG_ALLOC
18#endif
19
20#define SIGNATURE 0xBEEFFEEB
21/*#define CB_HDR (sizeof(MEMBLOCK) - 1) /* size of MEMBLOCK header (in bytes) */
22#define CB_HDR (int)&(((PMEMBLOCK)0)->achUserData[0])
23#define PNEXT_BLOCK(a) ((PMEMBLOCK)((unsigned)(a) + CB_HDR + (a)->cbSize))
24
25#define INCL_DOS
26#define INCL_DOSERRORS
27#ifdef RING0
28 #define INCL_NOAPI
29#else
30 #define INCL_DOSMEMMGR
31#endif
32
33
34/******************************************************************************
35* Headerfiles
36******************************************************************************/
37#include <os2.h>
38#ifdef RING0
39 #include "dev32hlp.h"
40 #include "asmutils.h"
41#else
42 #include <builtin.h>
43 #define Int3() __interrupt(3)
44#endif
45#include "log.h"
46#include "malloc.h"
47#include <memory.h>
48
49
50/******************************************************************************
51* Structs and Typedefs
52******************************************************************************/
53#pragma pack(1)
54typedef struct _MEMBLOCK /* MB */
55{
56#ifdef DEBUG_ALLOC
57 unsigned long ulSignature; /* should be SIGNATURE (0xBEEFFEEB) */
58#endif
59 unsigned cbSize; /* size of user space (achBlock)*/
60 struct _MEMBLOCK *pNext;
61 unsigned char achUserData[1];
62} MEMBLOCK, *PMEMBLOCK;
63#pragma pack()
64
65/******************************************************************************
66* Global data
67******************************************************************************/
68/*#pragma info(nogen, nouni, noext)*/
69static PMEMBLOCK pUsed; /* pointer to the used memblock chain. */
70static PMEMBLOCK pFree; /* pointer to the free memblock chain. */
71static unsigned cbFree; /* bytes of free user memory in the heap.*/
72unsigned _uHeapMinPtr; /* heap pointers are greater or equal to this.*/
73unsigned _uHeapMaxPtr; /* heap pointers are less than this. */
74#ifndef RING0
75 char fInited; /* init flag */
76#endif
77
78/******************************************************************************
79* Internal functions
80******************************************************************************/
81static void insertUsed(PMEMBLOCK pMemblock);
82static void insertFree(PMEMBLOCK pMemblock);
83static PMEMBLOCK getFreeMemblock(unsigned cbUserSize);
84static PMEMBLOCK findBlock(PMEMBLOCK pMemblock, void *pvUser, int fWithin);
85
86
87/**
88 * Inserts a memblock into the used chain
89 * @param pMemblock Pointer to memblock which is to inserted.
90 * @remark Sorts on address.
91 */
92static void insertUsed(PMEMBLOCK pMemblock)
93{
94 if (pUsed == NULL || pUsed > pMemblock)
95 {
96 pMemblock->pNext = pUsed;
97 pUsed = pMemblock;
98 }
99 else
100 {
101 PMEMBLOCK pMb = pUsed;
102 while (pMb->pNext != NULL && pMb->pNext < pMemblock)
103 pMb = pMb->pNext;
104
105 pMemblock->pNext = pMb->pNext;
106 pMb->pNext= pMemblock;
107 }
108}
109
110
111/**
112 * Inserts a memblock into the free chain.
113 * Merges blocks adjecent blocks.
114 * @param pMemblock Pointer to memblock to insert into the free list.
115 * @remark Sorts on address.
116 */
117static void insertFree(PMEMBLOCK pMemblock)
118{
119 cbFree += pMemblock->cbSize;
120 if (pMemblock < pFree || pFree == NULL)
121 {
122 /* test for merge with 2nd block */
123 if (pFree != NULL && PNEXT_BLOCK(pMemblock) == pFree)
124 {
125 cbFree += pMemblock->cbSize + CB_HDR;
126 pFree->cbSize += CB_HDR;
127 #ifdef DEBUG_ALLOC
128 pMemblock->ulSignature = 0xF0EEEE0F;
129 #endif
130 }
131 else
132 {
133 pMemblock->pNext = pFree;
134 pFree = pMemblock;
135
136 }
137 }
138 else
139 {
140 PMEMBLOCK pMb = pFree;
141 while (pMb->pNext != NULL && pMb->pNext < pMemblock)
142 pMb = pMb->pNext;
143
144 /* test for merge with left block */
145 if (PNEXT_BLOCK(pMb) == pMemblock)
146 {
147 pMb->cbSize += CB_HDR + pMemblock->cbSize;
148 cbFree += CB_HDR;
149 #ifdef DEBUG_ALLOC
150 pMemblock->ulSignature = 0xF0EEEE0F;
151 #endif
152 pMemblock = pMb;
153 }
154 else
155 {
156 pMemblock->pNext = pMb->pNext;
157 pMb->pNext = pMemblock;
158 }
159
160 /* test for merge with right block */
161 if (PNEXT_BLOCK(pMemblock) == pMemblock->pNext && pMemblock->pNext != NULL)
162 {
163 pMemblock->cbSize += CB_HDR + pMemblock->pNext->cbSize;
164 cbFree += CB_HDR;
165 #ifdef DEBUG_ALLOC
166 pMemblock->pNext->ulSignature = 0xF0EEEE0F;
167 #endif
168 pMemblock->pNext = pMemblock->pNext->pNext;
169 }
170 }
171}
172
173
174/**
175 * Finds a free block at the requested size.
176 * @returns Pointer to block (not in free list any longer).
177 * @param cbUserSize Bytes the user have requested.
178 * @sketch cbUserSize is aligned to nearest 4 bytes.
179 *
180 *
181 */
182static PMEMBLOCK getFreeMemblock(unsigned cbUserSize)
183{
184 PMEMBLOCK pBestFit = NULL;
185 PMEMBLOCK pBestFitPrev = NULL;
186 PMEMBLOCK pCur = pFree;
187 PMEMBLOCK pPrev = NULL;
188
189 cbUserSize = (cbUserSize + 3) & ~3;
190
191 /* search for block */
192 while (pCur != NULL)
193 {
194 /* check for perfect match first */
195 if (pCur->cbSize == cbUserSize)
196 break;
197 /* TODO: The following test may need to be adjusted later. */
198 else if (pCur->cbSize >= cbUserSize
199 && (pBestFit == NULL || pCur->cbSize < pBestFit->cbSize)
200 )
201 {
202 pBestFit = pCur;
203 pBestFitPrev = pPrev;
204 }
205
206 /* next */
207 pPrev = pCur;
208 pCur = pCur->pNext;
209 }
210
211 /* link out block */
212 if (pCur != NULL)
213 { /* prefect match */
214 if (pPrev != NULL)
215 pPrev->pNext = pCur->pNext;
216 else
217 pFree = pCur->pNext;
218
219 cbFree -= cbUserSize;
220 }
221 else if (pBestFit != NULL)
222 { /* best fit */
223 /* two cases 1) split block. 2) block is too small to be splitted. */
224 if (pBestFit->cbSize > cbUserSize + CB_HDR)
225 {
226 pCur = (PMEMBLOCK)((unsigned)pBestFit + pBestFit->cbSize - cbUserSize);
227 #ifdef DEBUG_ALLOC
228 pCur->ulSignature = SIGNATURE;
229 #endif
230 pCur->cbSize = cbUserSize;
231 pBestFit->cbSize -= cbUserSize + CB_HDR;
232
233 cbFree -= cbUserSize + CB_HDR;
234 }
235 else
236 {
237 if (pBestFitPrev != NULL)
238 pBestFitPrev->pNext = pBestFit->pNext;
239 else
240 pFree = pBestFit->pNext;
241 pCur = pBestFit;
242
243 cbFree -= pCur->cbSize;
244 }
245 }
246
247 return pCur;
248}
249
250
251/**
252 * Finds a memory block starting the search at pMemblock.
253 * @returns Pointer to memblock if found.
254 * @param pMemblock Start node.
255 * @param pvUser User pointer to find the block to.
256 * @param fWithin When this flag is set, the pointer may point anywhere within the block.
257 */
258static PMEMBLOCK findBlock(PMEMBLOCK pMemblock, void *pvUser, int fWithin)
259{
260 if (pvUser != NULL && pMemblock != NULL)
261 {
262 if (fWithin)
263 while (pMemblock != NULL &&
264 !(pvUser >= (void*)pMemblock && pvUser < (void*)PNEXT_BLOCK(pMemblock))
265 )
266 pMemblock = pMemblock->pNext;
267 else
268 {
269 pvUser = (void*)((unsigned)pvUser - CB_HDR);
270 while (pMemblock != NULL && pvUser != (void*)pMemblock)
271 pMemblock = pMemblock->pNext;
272 }
273 }
274 else
275 pMemblock = NULL;
276
277 return pMemblock;
278}
279
280
281/**
282 * Initiate the heap "subsystem".
283 * @returns 0 on success, not 0 on error.
284 * @param cbSize Heapsize in bytes.
285 */
286int heapInit(unsigned cbSize)
287{
288 pUsed = NULL;
289
290 #ifdef RING0
291 pFree = D32Hlp_VMAlloc(VMDHA_SWAP, cbSize, ~0UL);
292 #else
293 if (DosAllocMem((void*)&pFree, cbSize, PAG_COMMIT | PAG_READ | PAG_WRITE) != 0)
294 pFree = NULL;
295 #endif
296 if (pFree == NULL)
297 {
298 kprintf(("unable to allocate heap memory.\n"));
299 Int3();
300 return -1;
301 }
302
303 #ifdef DEBUG_ALLOC
304 pFree->ulSignature = SIGNATURE;
305 #endif
306 pFree->cbSize = cbSize - CB_HDR;
307 pFree->pNext = NULL;
308 cbFree = pFree->cbSize;
309
310 _uHeapMinPtr = (unsigned)pFree + CB_HDR;
311 _uHeapMaxPtr = (unsigned)pFree + cbSize;
312
313 #ifdef DEBUG_ALLOC
314 if (!_heap_check())
315 {
316 /* error! */
317 kprintf(("%s: _heap_check failed!\n", "heapInit"));
318 Int3();
319 return -2;
320 }
321 #endif
322 #ifdef RING3
323 fInited = TRUE;
324 #endif
325 return 0;
326}
327
328
329/**
330 * malloc - allocates a given amount of memory.
331 * @returns Pointer to allocated memory.
332 * NULL if out of memory. (Or memory to fragmented.)
333 * @param cbSize Bytes user requests us to allocate. This is aligned
334 * to four bytes.
335 */
336void * malloc(unsigned cbSize)
337{
338 void *pvRet = NULL;
339
340 #ifdef DEBUG_ALLOC
341 if (!_heap_check())
342 {
343 kprintf(("%s: _heap_check failed!\n", "malloc"));
344 return NULL;
345 }
346 #endif
347
348 if (cbSize != 0)
349 {
350 PMEMBLOCK pMemblock = getFreeMemblock(cbSize);
351 if (pMemblock != NULL)
352 {
353 insertUsed(pMemblock);
354 pvRet = &pMemblock->achUserData[0];
355 }
356 }
357 else
358 {
359 /* error! */
360 kprintf(("%s: error cbSize = 0\n", "malloc"));
361 }
362
363 return pvRet;
364}
365
366
367/**
368 * Reallocate a heapblock.
369 * @returns Pointer to new heapblock.
370 * @param pv Pointer to the block to realloc.
371 * @param cbNew The new block size.
372 */
373void *realloc(void *pv, unsigned cbNew)
374{
375 PMEMBLOCK pMemblock;
376 pMemblock = findBlock(pUsed, pv, FALSE);
377 if (pMemblock != NULL)
378 {
379 void *pvRet;
380
381 cbNew = (cbNew + 3) & ~3;
382 if (cbNew <= pMemblock->cbSize)
383 { /* shrink block */
384 pvRet = pv;
385 if (cbNew + CB_HDR < pMemblock->cbSize)
386 { /* split block */
387 PMEMBLOCK pNewBlock = (PMEMBLOCK)((unsigned)pMemblock + CB_HDR + cbNew);
388 #ifdef DEBUG_ALLOC
389 pNewBlock->ulSignature = SIGNATURE;
390 #endif
391 pNewBlock->cbSize = pMemblock->cbSize - cbNew - CB_HDR;
392 pNewBlock->pNext = NULL;
393 pMemblock->cbSize = cbNew;
394 insertFree(pNewBlock);
395 }
396 }
397 else
398 { /* expand block */
399 pvRet = malloc(cbNew);
400 if (pvRet != NULL)
401 {
402 memcpy(pvRet, pv, pMemblock->cbSize);
403 free(pv);
404 }
405 }
406 return pvRet;
407 }
408 return NULL;
409}
410
411
412/**
413 * Frees a block.
414 * @param pv User pointer.
415 */
416void free(void *pv)
417{
418 #ifdef DEBUG_ALLOC
419 if (!_heap_check())
420 {
421 kprintf(("free: _heap_check failed!\n"));
422 return;
423 }
424 #endif
425
426 if (pv != NULL)
427 {
428 PMEMBLOCK pCur = pUsed;
429 PMEMBLOCK pPrev = NULL;
430 pv = (void*)((int)pv - CB_HDR);
431
432 while (pCur != NULL &&
433 #ifdef DEBUG_ALLOC /* pointer within block */
434 !(pv >= (void*)pCur && (void*)((unsigned)pv + CB_HDR) < (void*)PNEXT_BLOCK(pCur))
435 #else
436 pv != (void*)pCur
437 #endif
438 )
439 {
440 pPrev = pCur;
441 pCur = pCur->pNext;
442 }
443
444 if (pCur != NULL)
445 {
446 if (pv == pCur)
447 {
448 if (pPrev != NULL)
449 pPrev->pNext = pCur->pNext;
450 else
451 pUsed = pCur->pNext;
452
453 insertFree(pCur);
454
455 #ifdef DEBUG_ALLOC
456 if (!_heap_check())
457 kprintf(("%s: _heap_check failed 3!\n", "free"));
458 #endif
459 }
460 else
461 kprintf(("free: pv is not pointing to start of block.\n"));
462 }
463 else
464 kprintf(("free: heap block not found!\n"));
465 }
466 else
467 kprintf(("free: Free received a NULL pointer!\n"));
468}
469
470
471/**
472 * Gets the size of a block.
473 * @returns Bytes in a block.
474 */
475unsigned _msize(void *pv)
476{
477 PMEMBLOCK pBlock;
478 #ifdef DEBUG_ALLOC
479 if (!_heap_check())
480 kprintf(("_msize: _heap_check failed!\n"));
481 #endif
482 pBlock = findBlock(pUsed, pv, FALSE);
483 return pBlock != NULL ? pBlock->cbSize : 0;
484}
485
486
487/**
488 * Checks if pv is a valid heappointer.
489 * @returns 1 if valid. 0 if invalid.
490 * @param pv User data pointer.
491 */
492int _validptr(void *pv)
493{
494 PMEMBLOCK pBlock;
495
496 #ifdef DEBUG_ALLOC
497 if (!_heap_check())
498 kprintf(("_validptr: _heap_check failed!\n"));
499 #endif
500
501 pBlock = findBlock(pUsed, pv, TRUE);
502 return pBlock != NULL;
503}
504
505
506/**
507 * Checks that the dataaera made up by pv and cbSize valid with in the heap.
508 * @returns 1 if valid. 0 if invalid.
509 * @param pv User data pointer.
510 * @param cbSize Size of data which has to be valid.
511 */
512int _validptr2(void *pv, unsigned cbSize)
513{
514 PMEMBLOCK pBlock;
515
516 #ifdef DEBUG_ALLOC
517 if (!_heap_check())
518 kprintf(("_validptr: _heap_check failed!\n"));
519 #endif
520
521 pBlock = findBlock(pUsed, pv, TRUE);
522 return pBlock != NULL ? (pBlock->cbSize - ((unsigned)pv - (unsigned)pBlock - CB_HDR)) >= cbSize : FALSE;
523}
524
525
526/**
527 * Get amount of free memory (in bytes)
528 * @returns Amount of free memory (in bytes).
529 * @remark Note that this amount is of all free memory blocks and
530 * that these blocks are fragmented.
531 * You'll probably not be able to allocate a single block
532 * of the returned size.
533 */
534unsigned _memfree(void)
535{
536 #ifdef DEBUG_ALLOC
537 if (!_heap_check())
538 kprintf(("_memfree: _heap_check failed!\n"));
539 #endif
540 return cbFree;
541}
542
543
544/**
545 * Checks heap integrety.
546 * @returns TRUE when ok.
547 * FALSE on error.
548 * NULL if out of memory. (Or memory to fragmented.)
549 */
550int _heap_check(void)
551{
552 #ifdef DEBUG_ALLOC
553 PMEMBLOCK pCurFree = pFree;
554 PMEMBLOCK pCurUsed = pUsed;
555
556 while (pCurFree != NULL || pCurUsed != NULL)
557 {
558 /** @sketch:
559 * check signatures and for lost memory.
560 *
561 * three cases:
562 * 1) pCurUsed adjecent to pCurUsed->pNext
563 * 2) pCurUsed adjecent to pCurFree
564 * 3) pCurFree adjecent to pCurFree->pNext
565 * 4) pCurFree adjecent to pCurUsed
566 * 5) pCurUsed is the last block
567 * 6) pCurFree is the last block
568 */
569 #if 0
570 if (pCurUsed != NULL && PNEXT_BLOCK(pCurUsed) == pCurUsed->pNext) /* 1.*/
571 ;
572 else if (pCurUsed != NULL && PNEXT_BLOCK(pCurUsed) == pCurFree) /* 2.*/
573 ;
574 else if (pCurFree != NULL && PNEXT_BLOCK(pCurFree) == pCurFree->pNext) /* 3.*/
575 ;
576 else if (pCurFree != NULL && PNEXT_BLOCK(pCurFree) == pCurUsed) /* 4.*/
577 ;
578 else if (pCurUsed != NULL && pCurFree == NULL && pCurUsed->pNext == NULL) /* 5.*/
579 ;
580 else if (pCurFree != NULL && pCurUsed == NULL && pCurFree->pNext == NULL) /* 6.*/
581 ;
582 else
583 #else
584 if (!( (pCurUsed != NULL && PNEXT_BLOCK(pCurUsed) == pCurUsed->pNext) /* 1.*/
585 || (pCurUsed != NULL && PNEXT_BLOCK(pCurUsed) == pCurFree) /* 2.*/
586 || (pCurFree != NULL && PNEXT_BLOCK(pCurFree) == pCurFree->pNext) /* 3.*/
587 || (pCurFree != NULL && PNEXT_BLOCK(pCurFree) == pCurUsed) /* 4.*/
588 || (pCurUsed != NULL && pCurFree == NULL && pCurUsed->pNext == NULL) /* 5.*/
589 || (pCurFree != NULL && pCurUsed == NULL && pCurFree->pNext == NULL) /* 6.*/
590 )
591 )
592 #endif
593 {
594 /* error hole */
595 kprintf(("_heap_check: internal error - memory hole!\n"));
596 return FALSE;
597 }
598
599 /* check signature and advance to the next block */
600 if (pCurUsed != NULL && (pCurFree == NULL || pCurUsed < pCurFree))
601 {
602 if (pCurUsed->ulSignature != SIGNATURE)
603 return FALSE;
604 pCurUsed = pCurUsed->pNext;
605 }
606 else
607 {
608 if (pCurFree->ulSignature != SIGNATURE)
609 return FALSE;
610 pCurFree = pCurFree->pNext;
611 }
612 }
613 #endif
614 return TRUE;
615}
616
617
618#if !defined(RING0) && defined(__IBMC__)
619
620/**
621 * Initialize Memory Functions
622 * Called from _exeentry.
623 */
624int _rmem_init(void)
625{
626 int rc = heapInit(0x100000);
627 return rc;
628}
629
630/**
631 * Initialize Memory Functions
632 * Called from _exeentry.
633 */
634int _rmem_term(void)
635{
636 return 0;
637}
638
639#endif
Note: See TracBrowser for help on using the repository browser.