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

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

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