Context Navigation

source: GPL/trunk/lib32/malloc.cpp@ 227

Last change on this file since 227 was 73, checked in by vladest, 20 years ago
Fixed compile issues Fixed SB128 driver
File size: 22.5 KB

Line
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)
46	typedef 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	//
65	PMEMBLOCK pmbUsed = 0; // Points to head of list of allocated memory blocks.
66	// Newly allocated blocks are inserted into head of list.
67	PMEMBLOCK pmbFree = 0; // Points to head of list of available memory blocks.
68	unsigned uMemFree = 0; // N bytes available for allocation.
69	LINEAR acHeap = NULL;
70
71	#pragma off (unreferenced)
72
73	//--- Heap methods:
74
75	//*****************************************************************************
76	//*****************************************************************************
77	void 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
107	ULONG fMemoryDoc = 0;
108	ULONG nAlloc = 0; // Current number of allocated blocks.
109	ULONG cAlloc = 0; // Total memory in allocated blocks incl. headers.
110	ULONG nAllocCalls = 0; // Cumulative total, number of malloc() calls.
111	ULONG nFree = 0; // Current number of free blocks.
112	ULONG cFree = 0; // Total memory in free blocks incl. headers.
113	ULONG nFreeCalls = 0; // Cumulative total, number of free() calls.
114	ULONG nCompact = 0; // Num of times we've joined two adjacent free
115	// blocks into a single larger block.
116	ULONG cTotalHeap = HEAP_SIZE;
117
118	//*****************************************************************************
119	//*****************************************************************************
120	BOOL 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
143	void 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
189	The fragmentation consideration comes into play when we find a block that's
190	big enough to hold the requested memory, but not big enough for the leftover
191	part 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
202	Must 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
213	To be split into an allocated and a new, smaller free block, 'm' must be at
214	least MIN_FragSize bytes long.
215
216	Everything should remain 4 byte aligned since the HDR_SIZE, MIN_FragSize,
217	and the space allocated (after we munge it) are all multiples of 4.
218
219	This means that in order for a free block to be chosen, one of the following
220	equation 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
231	PMEMBLOCK 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	*/
261	unsigned _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	*/
288	void 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()
327	This function searches the list of free blocks until it finds one big enough
328	to hold the amount of memory requested, which is passed in uSize. The uSize
329	request is sized up for:
330	- a memory block header
331	- four byte alignment
332	- minimum fragmentation
333
334	See helper function make_new_free() for discussion of fragmentation handling.
335	*/
336
337	#ifdef DEBUGHEAP
338	void NEAR malloc(unsigned uSize, const char filename, int lineno)
339	#else
340	void 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)
420	This function compacts the free blocks together. This function is a
421	companion to free(), and thus the algorithm is tailored to how free()
422	works. Change the algorithm in free(), and you'll have to change this
423	function too.
424
425	When free() frees a block, it sets the head of the free list, pmbFree, to
426	point to it. Then the newly freed block points to whatever the old pmbFree
427	pointed to. In other words, each new free block is added to the head of
428	the free list.
429
430	If compact() is always called after a block is freed, then it can be
431	guaranteed that the free list is always compacted (i.e. you won't find
432	two adjacent free blocks anywhere in the heap) _before_ each call to free().
433	Therefore, the newly freed block can be located in only one of the
434	following positions:
435	1. Not adjacent to any other free blocks (compacting not necessary)
436	2. Physically before another free block
437	3. Physically after another free block
438	4. Between two free blocks (i.e. the block occupies the entire space
439	between two free blocks)
440
441	Since the newly freed block is the first in the free list, compact()
442	starts with the second block in the list (i.e. pmbFree->pmbNext).
443	Each free block is then compared with the newly freed block for
444	adjacency. If a given block is located before the new block, then it
445	can't possibly be also located after, and vice versa. Hence, the
446	"else if" statement in the middle of the loop.
447
448	Also, the newly freed block can only be adjacent to at most two other
449	blocks. Therefore, the operation of combining two adjacent free blocks can
450	only happen at most twice. The variable nFreed counts the number of times
451	two blocks are combined. The function exits if nFreed reaches two. nFreed
452	is initially 0.
453
454	Helper macro after() takes a PMEMBLOCK (call it pmb) as a parameter,
455	and calculates where an adjacent free block would exist if it were
456	physically located after pmb.
457
458	Helper function remove() removes an element from the free list.
459	*/
460
461	#define after(pmb) ((PMEMBLOCK) ((char *) pmb + pmb->uSize + HDR_SIZE))
462
463	void 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	//*****************************************************************************
480	void 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
506	exit:
507	nCompact += iFreed;
508	}
509	//*****************************************************************************
510	//*****************************************************************************
511	#ifdef DEBUGHEAP
512	void free(void NEAR pvBlock, const char filename, int lineno)
513	#else
514	void 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
561	exit: //--- Check things are still intact.
562	HeapCheck((PSZ) "free() exit" );
563	DevPopf(cpuflags);
564	}
565	//*****************************************************************************
566	//*****************************************************************************
567	unsigned _memfree(void)
568	{
569	return uMemFree;
570	}
571	//*****************************************************************************
572	//*****************************************************************************
573	#ifdef DEBUGHEAP
574	void NEAR realloc(void NEAR pvBlock, unsigned usLength, const char *filename, int lineno)
575	#else
576	void 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	//*****************************************************************************
616	BOOL 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	//*****************************************************************************
626	extern "C" APIRET VMAlloc(ULONG size, ULONG flags, LINEAR *pAddr) ;
627	//*****************************************************************************
628	unsigned 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	//*****************************************************************************

Note: See TracBrowser for help on using the repository browser.

Download in other formats: