source: GPL/lib32/malloc.cpp@ 18

Last change on this file since 18 was 18, checked in by vladest, 20 years ago

initial import
File size: 22.5 KB
RevLine 
[18]1/* $Id: malloc.cpp,v 1.1.1.1 2003/07/02 13:57:02 eleph Exp $ */
2
3/* SCCSID = %W% %E% */
4/****************************************************************************
5 * *
6 * Copyright (c) IBM Corporation 1994 - 1997. *
7 * *
8 * The following IBM OS/2 source code is provided to you solely for the *
9 * the purpose of assisting you in your development of OS/2 device drivers. *
10 * You may use this code in accordance with the IBM License Agreement *
11 * provided in the IBM Device Driver Source Kit for OS/2. *
12 * *
13 ****************************************************************************/
14/**@internal %W%
15 * Implementation of the driver's built in memory management.
16 * @version %I%
17 * @context
18 * Unless otherwise noted, all interfaces are Ring-3 and Ring-0, 16-bit,
19 * kernel stack.
20 * @notes
21 * @history
22 * 01-Jul-95 Timur Tabi Creation
23 */
24
25#include <os2.h>
26#include <string.h> // memcpy(), memset()
27#include <stdio.h>
28#include <dbgos2.h>
29
30#include <devhelp.h>
31#ifdef KEE
32#include <kee.h>
33#endif
34#include "malloc.h"
35
36#if !defined(min)
37#define min(a,b) (((a) < (b)) ? (a) : (b))
38#endif
39
40#define DEFAULT_HEAP 256*1024
41#define HEAP_SIZE 256*1024
42
43#define SIGNATURE 0xBEEFDEAD // "DeadBeef" when view in hex in word order.
44
45#pragma pack(4)
46typedef struct _MEMBLOCK {
47 ULONG ulSignature;
48 ULONG uSize;
49 struct _MEMBLOCK NEAR *pmbNext;
50#ifdef DEBUGHEAP
51 char NEAR *pszFile;
52 ULONG ulLine;
53#endif
54 char achBlock[4];
55} MEMBLOCK, NEAR *PMEMBLOCK;
56#pragma pack()
57
58#define HDR_SIZE ( sizeof(MEMBLOCK) - 4 )
59
60// We won't leave a hole in memory any smaller than MIN_FragSize.
61#define MIN_FragSize 4
62
63//--- Global Variables used to manage the heap:
64//
65PMEMBLOCK pmbUsed = 0; // Points to head of list of allocated memory blocks.
66 // Newly allocated blocks are inserted into head of list.
67PMEMBLOCK pmbFree = 0; // Points to head of list of available memory blocks.
68unsigned uMemFree = 0; // N bytes available for allocation.
69LINEAR acHeap = NULL;
70
71#pragma off (unreferenced)
72
73//--- Heap methods:
74
75//*****************************************************************************
76//*****************************************************************************
77void dumpheap(void)
78{
79 int i;
80 PMEMBLOCK pmb;
81 unsigned u=0;
82
83 pmb=pmbUsed;
84 dprintf(("HEAP: Heap Dump - Used blocks\n"));
85 for (i=0; i<10; i++) {
86 dprintf((" pmb=%p, length=%ui\n",(void __far *) pmb, pmb->uSize));
87 u+=pmb->uSize;
88 pmb=pmb->pmbNext;
89 if (!pmb) break;
90 }
91 dprintf((" Total used = %ui\n",u));
92
93 u=0;
94 pmb=pmbFree;
95 dprintf(("HEAP: Heap Dump - Free blocks\n"));
96 for (i=0; i<50; i++) {
97 dprintf((" pmb=%p, length=%ui\n",(void __far *) pmb, pmb->uSize));
98 u+=pmb->uSize;
99 pmb=pmb->pmbNext;
100 if (!pmb) break;
101 }
102 dprintf((" Total free = %ui\n",u));
103}
104//*****************************************************************************
105//*****************************************************************************
106
107ULONG fMemoryDoc = 0;
108ULONG nAlloc = 0; // Current number of allocated blocks.
109ULONG cAlloc = 0; // Total memory in allocated blocks incl. headers.
110ULONG nAllocCalls = 0; // Cumulative total, number of malloc() calls.
111ULONG nFree = 0; // Current number of free blocks.
112ULONG cFree = 0; // Total memory in free blocks incl. headers.
113ULONG nFreeCalls = 0; // Cumulative total, number of free() calls.
114ULONG nCompact = 0; // Num of times we've joined two adjacent free
115 // blocks into a single larger block.
116ULONG cTotalHeap = HEAP_SIZE;
117
118//*****************************************************************************
119//*****************************************************************************
120BOOL SignatureCheck ( PMEMBLOCK p, PSZ idText )
121{
122 int bGoodPointer;
123
124 // Set bGoodPointer to indicate whether or not 'p' points within heap.
125 bGoodPointer = ((LINEAR)p >= (acHeap))
126 && ((LINEAR)p <= (( acHeap) + HEAP_SIZE)) ;
127 //### heap might have less than HEAP_SIZE bytes
128
129 // Check for correct signature.
130 if (bGoodPointer)
131 bGoodPointer = (p->ulSignature == SIGNATURE) && p->uSize < HEAP_SIZE;
132
133 if (! bGoodPointer)
134 {
135// ddprintf( "Heap pointer out of range, or signature exception: %p %s\n", p, idText );
136 DebugInt3();
137 }
138 return bGoodPointer;
139}
140//*****************************************************************************
141//*****************************************************************************
142#ifdef DEBUG
143void HeapCheck ( PSZ idText )
144{
145 PMEMBLOCK p;
146 for ( nAlloc = 0, cAlloc = 0, p = pmbUsed; p; p = p->pmbNext ) {
147 ++nAlloc;
148 SignatureCheck( p,(PSZ) "HeapCheck() Used list" );
149 cAlloc += p->uSize + HDR_SIZE;
150 }
151 for ( nFree = 0, cFree = 0, p = pmbFree; p; p = p->pmbNext ) {
152 ++nFree;
153 SignatureCheck( p,(PSZ) "HeapCheck() Free list" );
154 cFree += p->uSize + HDR_SIZE;
155 }
156 if (fMemoryDoc & 1) {
157 if (cAlloc + cFree != cTotalHeap) {
158// ddprintf( "Heap Alloc + Free != Total\n" );
159// dumpheap();
160 DebugInt3();
161 }
162 }
163}
164#else
165#define HeapCheck(a)
166#endif
167
168//*****************************************************************************
169//*****************************************************************************
170
171
172
173// Threshold for creating a new free block.
174#define MIN_Leftover (HDR_SIZE + MIN_FragSize)
175
176/* make_new_free()
177 Formats the back part of an existing free MEMBLOCK as a new, smaller
178 "Free" MEMBLOCK. Doesn't update Global vbls (caller responsibility).
179 IN: pmbOldFree - pointer to existing memory block.
180 uSize - offset, which won't be included in new allocation.
181 it's assumed HDR is not included in uSize.
182 OUT: pointer to new free MEMBLOCK, is a new block of free memory,
183 is created at pmbOldFree + uRequest. The memory block header
184 in both the new block and the old block are properly initialized
185 on return, but we don't update the Free list or Allocated list.
186 OUT: NULL if the new free memory block is smaller than the
187 framentation threshold.
188
189The fragmentation consideration comes into play when we find a block that's
190big enough to hold the requested memory, but not big enough for the leftover
191part to be useful as another free block.
192
193 _______________________free block_______________________________________
194 | free | |
195 | block | space available |
196 | header | (pmbFree->uSize bytes long) |
197 |(HDR_SIZE | |
198 |__bytes)__|_____________________________________________________________|
199
200 <-- HDR --> <------------------------- l -------------------------------->
201
202Must either be allocated in total, or must become:
203
204 _______________________used block_______________________________________
205 | used | | free | |
206 | block | space allocated | block | space |
207 | header | == uSize (following DWORD align't) | header | available |
208 |(HDR_SIZE | (pmbUsed->uSize bytes long) |(HDR_SIZE | |
209 |__bytes)__|_____________________________________|__bytes)__|____________|
210
211 <-- HDR --> <-------------- n ------------------><-- HDR --> <--- m ----->
212
213To be split into an allocated and a new, smaller free block, 'm' must be at
214least MIN_FragSize bytes long.
215
216Everything should remain 4 byte aligned since the HDR_SIZE, MIN_FragSize,
217and the space allocated (after we munge it) are all multiples of 4.
218
219This means that in order for a free block to be chosen, one of the following
220equation must hold
221
222 Case 1: n <= l < (n + HDR + MIN_FragSize)
223 Here, we'll allocate the entire block. This makes the block somewhat
224 larger than the request, but prevents some degree of fragmentation.
225
226 Case 2: (n + HDR + MIN_FragSize) <= l
227 We split the block into an allocated part to satisfy the allocation request,
228 and a free block which can be allocated in a subsequent request.
229*/
230
231PMEMBLOCK make_new_free(PMEMBLOCK pmbOldFree, unsigned uRequest)
232{
233 PMEMBLOCK pmbNewFree; // If we create a new free block, it goes here.
234
235 // Which of the two cases (as described in function header) have we got?
236 // We know we're big enough to satisfy request, is there enough leftover
237 // for a new free block?
238
239 if ((uRequest + MIN_Leftover) > pmbOldFree->uSize) {
240 // Not enough leftover, allocate the entire free block. Don't
241 // change pmbOldFree->uSize.
242 pmbNewFree = 0;
243 }
244 else {
245 // We've got enough leftover to make a new free block.
246 pmbNewFree = (PMEMBLOCK) ((char *) pmbOldFree + HDR_SIZE + uRequest );
247 pmbNewFree->ulSignature = SIGNATURE;
248 pmbNewFree->uSize = pmbOldFree->uSize - (uRequest + HDR_SIZE);
249 pmbNewFree->pmbNext = pmbOldFree->pmbNext;
250
251 // Update the size of the free block that was passed in.
252 pmbOldFree->uSize -= (pmbNewFree->uSize + HDR_SIZE);
253 }
254
255 return pmbNewFree;
256}
257
258
259/**@internal _msize
260 */
261unsigned _msize(void NEAR *pvBlock)
262{
263 PMEMBLOCK pmb;
264
265 if (!pvBlock)
266 return 0;
267
268 pmb = (PMEMBLOCK) ((char NEAR *) pvBlock - HDR_SIZE);
269
270 return pmb->uSize;
271}
272
273
274/**@internal pmbAllocateBlock
275 * Update all data structures for allocation of one memory block. It's
276 * assumed, on entry, that the block is large enough for the requested
277 * allocation.
278 * @param PMEMBLOCK pmb - the current memory block on the Free list to
279 * allocate.
280 * @param USHORT uRequest - size of the memory request to fill, not counting
281 * memory block header.
282 * @param PMEMBLOCK pmbPrev - the memory block which precedes the block being
283 * allocated in the Free list. NULL if no predecessor (ie, pmb is pointed to
284 * by ::pmbFree).
285 * @return PMEMBLOCK - pointer to the data part of the allocated memory block,
286 * suitable for return to malloc() caller.
287 */
288void NEAR *npvAllocateBlock( PMEMBLOCK pmb, ULONG uRequest, PMEMBLOCK pmbPrev )
289{
290 //pmb points to the selected block.
291 //pmbPrev points to the block prior to the selected block, NULL if pmbFree.
292 PMEMBLOCK pmbOldNext; // Original free block that follows the block being allocated.
293 PMEMBLOCK pmbNewFree; // Leftover free memory from the allocated block.
294
295 // Split this block into an allocated + free part if it's big enough.
296 pmbNewFree = make_new_free( pmb, uRequest );
297
298 // Update global memory counter.
299 uMemFree -= (pmb->uSize + HDR_SIZE);
300
301 // Add this block into the front of the Allocated list.
302 pmbOldNext = pmb->pmbNext;
303 pmb->pmbNext = pmbUsed;
304 pmbUsed = pmb;
305
306 // Remove the new allocation from the Free list.
307 if (pmbNewFree) { // If we split off a new free block
308 pmbNewFree->pmbNext = pmbOldNext;
309 if (pmbPrev) // If we're not at head of Free list
310 pmbPrev->pmbNext = pmbNewFree;
311 else
312 pmbFree = pmbNewFree;
313 }
314 else { // We allocated the entire free block.
315 if (pmbPrev) // If we're not at head of Free list
316 pmbPrev->pmbNext = pmbOldNext;
317 else
318 if (pmbOldNext)
319 pmbFree = pmbOldNext;
320 }
321
322 return (void NEAR *) pmb->achBlock;
323}
324
325
326/* malloc()
327This function searches the list of free blocks until it finds one big enough
328to hold the amount of memory requested, which is passed in uSize. The uSize
329request is sized up for:
330 - a memory block header
331 - four byte alignment
332 - minimum fragmentation
333
334See helper function make_new_free() for discussion of fragmentation handling.
335*/
336
337#ifdef DEBUGHEAP
338void NEAR *malloc(unsigned uSize, const char *filename, int lineno)
339#else
340void NEAR *malloc( unsigned uSize )
341#endif
342{
343 ULONG uRequest; // Request size after alignment.
344 PMEMBLOCK pmb, pmbPrev; // Use to walk free lists.
345 void NEAR *npvReturn = 0; // Return value.
346 ULONG cpuflags;
347
348#ifdef DEBUG
349// dprintf(("malloc(). size: %d",uSize));
350#endif
351 if(acHeap == NULL) {
352 if (!HeapInit(HEAP_SIZE))
353 {
354#ifdef DEBUG
355 dprintf(("malloc(): error heap initing"));
356#endif
357 return 0;
358 }
359 }
360#ifdef DEBUG
361// dprintf(("malloc(): heap inited"));
362#endif
363 if (!uSize || uSize > HEAP_SIZE) {
364 DebugInt3();
365 return 0;
366 }
367
368 cpuflags = DevPushfCli();
369 ++nAllocCalls; // Diagnostics.
370 HeapCheck((PSZ) "malloc() entry" );
371#ifdef DEBUG
372// dprintf(("malloc(): heap checked. pmbFree %x",pmbFree));
373#endif
374
375 uRequest = (uSize + 3) & -4; // Force DWORD alignment.
376
377 if (pmbFree->uSize >= uRequest)
378 npvReturn = npvAllocateBlock( pmbFree, uRequest, NULL );
379 else {
380 pmbPrev = pmbFree;
381 for ( pmb=pmbFree->pmbNext; pmb; pmbPrev=pmb, pmb=pmb->pmbNext)
382 {
383#ifdef DEBUG
384// dprintf(("malloc(): for. pmb %x",pmb));
385#endif
386 if (pmb->uSize >= uRequest) {
387 npvReturn = npvAllocateBlock( pmb, uRequest, pmbPrev );
388 break;
389 }
390 }
391 }
392
393 if (npvReturn) {
394#ifdef DEBUGHEAP
395 PMEMBLOCK pBlock = (PMEMBLOCK) (((PUCHAR) npvReturn) - HDR_SIZE);
396
397 pBlock->pszFile = (char *)filename;
398 pBlock->ulLine = lineno;
399#endif
400 SignatureCheck( (PMEMBLOCK) (((PUCHAR) npvReturn) - HDR_SIZE), (PSZ) "malloc() exit, allocated block" );
401 }
402 else {
403#ifdef DEBUG
404 dprintf(("malloc(): out of memory"));
405#endif
406 // Out of Memory !!!
407 DebugInt3();
408 }
409
410 HeapCheck((PSZ) "malloc() exit" );
411#ifdef DEBUG
412// dprintf(("malloc(): malloc exit"));
413#endif
414
415 DevPopf(cpuflags);
416 return npvReturn;
417}
418
419/* void compact(void)
420This function compacts the free blocks together. This function is a
421companion to free(), and thus the algorithm is tailored to how free()
422works. Change the algorithm in free(), and you'll have to change this
423function too.
424
425When free() frees a block, it sets the head of the free list, pmbFree, to
426point to it. Then the newly freed block points to whatever the old pmbFree
427pointed to. In other words, each new free block is added to the head of
428the free list.
429
430If compact() is always called after a block is freed, then it can be
431guaranteed that the free list is always compacted (i.e. you won't find
432two adjacent free blocks anywhere in the heap) _before_ each call to free().
433Therefore, the newly freed block can be located in only one of the
434following positions:
4351. Not adjacent to any other free blocks (compacting not necessary)
4362. Physically before another free block
4373. Physically after another free block
4384. Between two free blocks (i.e. the block occupies the entire space
439 between two free blocks)
440
441Since the newly freed block is the first in the free list, compact()
442starts with the second block in the list (i.e. pmbFree->pmbNext).
443Each free block is then compared with the newly freed block for
444adjacency. If a given block is located before the new block, then it
445can't possibly be also located after, and vice versa. Hence, the
446"else if" statement in the middle of the loop.
447
448Also, the newly freed block can only be adjacent to at most two other
449blocks. Therefore, the operation of combining two adjacent free blocks can
450only happen at most twice. The variable nFreed counts the number of times
451two blocks are combined. The function exits if nFreed reaches two. nFreed
452is initially 0.
453
454Helper macro after() takes a PMEMBLOCK (call it pmb) as a parameter,
455and calculates where an adjacent free block would exist if it were
456physically located after pmb.
457
458Helper function remove() removes an element from the free list.
459*/
460
461#define after(pmb) ((PMEMBLOCK) ((char *) pmb + pmb->uSize + HDR_SIZE))
462
463void remove(PMEMBLOCK pmb)
464{
465 PMEMBLOCK pmbPrev;
466
467 if (pmb == pmbFree) {
468 pmbFree = pmbFree->pmbNext;
469 return;
470 }
471
472 for (pmbPrev=pmbFree; pmbPrev; pmbPrev=pmbPrev->pmbNext)
473 if (pmbPrev->pmbNext == pmb) {
474 pmbPrev->pmbNext = pmb->pmbNext;
475 return;
476 }
477}
478//*****************************************************************************
479//*****************************************************************************
480void compact(void)
481{
482 PMEMBLOCK pmb;
483 int iFreed = 0;
484
485 for (pmb=pmbFree->pmbNext; pmb; pmb=pmb->pmbNext) {
486 if (pmb == pmb->pmbNext) {
487// ddprintf("HEAP: heap loop, %p points to itself\n", (void __far *) pmb);
488 DebugInt3();
489 }
490
491 if (after(pmb) == pmbFree) {
492// ddprintf("HEAP: compact found pointer %p (size=%ui) before pmbFree %p\n", (void __far *) pmb, pmb->uSize, (void __far *) pmbFree);
493 pmb->uSize += HDR_SIZE + pmbFree->uSize;
494 remove(pmbFree);
495 if (++iFreed == 2) goto exit;
496 }
497 else
498 if (after(pmbFree) == pmb) {
499// ddprintf("HEAP: compact found pointer %p (size=%ui) after pmbFree %p\n", (void __far *) pmb, pmb->uSize, (void __far *) pmbFree);
500 pmbFree->uSize += HDR_SIZE + pmb->uSize;
501 remove(pmb);
502 if (++iFreed == 2) goto exit;
503 }
504 }
505
506exit:
507 nCompact += iFreed;
508}
509//*****************************************************************************
510//*****************************************************************************
511#ifdef DEBUGHEAP
512void free(void NEAR *pvBlock, const char *filename, int lineno)
513#else
514void free(void NEAR *pvBlock)
515#endif
516{
517 PMEMBLOCK pmb,pmbPrev,pmbBlock;
518 int fSentinel;
519 ULONG cpuflags;
520
521 if(acHeap == NULL) {
522 DebugInt3();
523 return;
524 }
525
526 ++nFreeCalls;
527 if (!pvBlock) return; // support freeing of NULL
528
529 cpuflags = DevPushfCli();
530 pmbBlock=(PMEMBLOCK) ((char NEAR *) pvBlock - HDR_SIZE);
531
532 SignatureCheck( pmbBlock,(PSZ) "free() entry, Block to be freed" );
533 HeapCheck((PSZ) "free() entry" );
534
535 uMemFree += pmbBlock->uSize + HDR_SIZE;
536
537 if (pmbBlock == pmbUsed) { // are we freeing the first block?
538 pmbUsed = pmbUsed->pmbNext; // the 2nd block is now the 1st
539 pmbBlock->pmbNext = pmbFree; // this block is now free, so it points to 1st free block
540 pmbFree = pmbBlock; // this is now the 1st free block
541 compact();
542 goto exit;
543 }
544
545 pmbPrev=pmbUsed;
546 fSentinel = FALSE;
547 for (pmb=pmbUsed->pmbNext; pmb; pmbPrev=pmb, pmb=pmb->pmbNext) {
548 if (pmb == pmbBlock) {
549 if (fSentinel) {
550 dprintf(("HEAP: free sentinel triggered, pmb=%p\n", (void __far *) pmb));
551 DebugInt3();
552 }
553 pmbPrev->pmbNext = pmb->pmbNext; // delete this block from the chain
554 pmbBlock->pmbNext = pmbFree;
555 pmbFree = pmbBlock;
556 compact();
557 fSentinel = TRUE;
558 }
559 }
560
561exit: //--- Check things are still intact.
562 HeapCheck((PSZ) "free() exit" );
563 DevPopf(cpuflags);
564}
565//*****************************************************************************
566//*****************************************************************************
567unsigned _memfree(void)
568{
569 return uMemFree;
570}
571//*****************************************************************************
572//*****************************************************************************
573#ifdef DEBUGHEAP
574void NEAR *realloc(void NEAR *pvBlock, unsigned usLength, const char *filename, int lineno)
575#else
576void NEAR *realloc(void NEAR *pvBlock, unsigned usLength)
577#endif
578{
579 void NEAR *pv;
580
581 if (!pvBlock) // if ptr is null, alloc block
582#ifdef DEBUGHEAP
583 return malloc(usLength, filename, lineno);
584#else
585 return malloc(usLength);
586#endif
587
588 if (!usLength) { // if length is 0, free block
589#ifdef DEBUGHEAP
590 free(pvBlock, filename, lineno);
591#else
592 free(pvBlock);
593#endif
594 return 0;
595 }
596
597#ifdef DEBUGHEAP
598 pv = malloc(usLength, filename, lineno); // attempt to allocate the new block
599#else
600 pv = malloc(usLength); // attempt to allocate the new block
601#endif
602 if (!pv) // can't do it?
603 return 0; // just fail. Version 2 will try harder
604
605 memcpy(pv, pvBlock, min( _msize(pvBlock), usLength));
606
607#ifdef DEBUGHEAP
608 free(pvBlock, filename, lineno);
609#else
610 free(pvBlock);
611#endif
612 return pv;
613}
614//*****************************************************************************
615//*****************************************************************************
616BOOL IsHeapAddr(ULONG addr)
617{
618 int bGoodPointer;
619
620 bGoodPointer = ((LINEAR)addr >= acHeap)
621 && ((LINEAR)addr <= (acHeap + HEAP_SIZE)) ;
622
623 return bGoodPointer;
624}
625//*****************************************************************************
626extern "C" APIRET VMAlloc(ULONG size, ULONG flags, LINEAR *pAddr) ;
627//*****************************************************************************
628unsigned HeapInit(unsigned uSize)
629{
630 LINEAR addr;
631 SHORT sel;
632
633 if (!uSize)
634 uSize = DEFAULT_HEAP;
635
636 if (uSize > HEAP_SIZE)
637 uSize = HEAP_SIZE;
638
639 if(VMAlloc(uSize, VMDHA_FIXED, &addr)) {
640 DebugInt3();
641 return 0;
642 }
643 acHeap = addr;
644#ifdef DEBUG
645// dprintf(("HeapInit(): addr: %x", acHeap));
646#endif
647
648 pmbFree = (PMEMBLOCK) acHeap;
649 pmbFree->uSize = uSize - HDR_SIZE;
650 pmbFree->ulSignature = SIGNATURE;
651 pmbFree->pmbNext = 0;
652 uMemFree = pmbFree->uSize;
653 return pmbFree->uSize;
654}
655//*****************************************************************************
656//*****************************************************************************
657
Note: See TracBrowser for help on using the repository browser.