1 /***************************************************************
2 ** Memory allocator for systems that don't have real one.
3 ** This might be useful when bringing up a new computer with no OS.
5 ** For PForth based on 'C'
8 ** Copyright 1994 3DO, Phil Burk, Larry Polansky, David Rosenboom
10 ** The pForth software code is dedicated to the public domain,
11 ** and any third party may reproduce, distribute and modify
12 ** the pForth software code or any derivative works thereof
13 ** without any compensation or license. The pForth software
14 ** code is provided on an "as is" basis without any warranty
15 ** of any kind, including, without limitation, the implied
16 ** warranties of merchantability and fitness for a particular
17 ** purpose and their equivalents under the laws of any jurisdiction.
19 ****************************************************************
21 ***************************************************************/
28 static char *gMemPoolPtr;
29 static ucell_t gMemPoolSize;
31 /* CUSTOM: Make the memory pool bigger if you want. */
32 #ifndef PF_MEM_POOL_SIZE
33 #define PF_MEM_POOL_SIZE (0x100000)
36 #define PF_MEM_BLOCK_SIZE (16)
38 #ifndef PF_MALLOC_ADDRESS
39 static char MemoryPool[PF_MEM_POOL_SIZE];
40 #define PF_MALLOC_ADDRESS MemoryPool
43 /**********************************************************
44 ** Doubly Linked List Tools
45 **********************************************************/
47 typedef struct DoublyLinkedListNode_s
49 struct DoublyLinkedListNode_s *dlln_Next;
50 struct DoublyLinkedListNode_s *dlln_Previous;
51 } DoublyLinkedListNode;
53 typedef struct DoublyLinkedList_s
55 DoublyLinkedListNode *dll_First;
56 DoublyLinkedListNode *dll_Null;
57 DoublyLinkedListNode *dll_Last;
60 #define dllPreviousNode(n) ((n)->dlln_Previous)
61 #define dllNextNode(n) ((n)->dlln_Next)
63 void dllSetupList( DoublyLinkedList *dll )
65 dll->dll_First = &(dll->dll_Null);
66 dll->dll_Null = (DoublyLinkedListNode *) NULL;
67 dll->dll_Last = &(dll->dll_First);
70 void dllLinkNodes( DoublyLinkedListNode *Node0, DoublyLinkedListNode *Node1 )
72 Node0->dlln_Next = Node1;
73 Node1->dlln_Previous = Node0;
76 void dllInsertNodeBefore( DoublyLinkedListNode *NewNodePtr,
77 DoublyLinkedListNode *NodeInListPtr )
79 DoublyLinkedListNode *NodePreviousPtr = dllPreviousNode( NodeInListPtr );
80 dllLinkNodes( NodePreviousPtr, NewNodePtr );
81 dllLinkNodes( NewNodePtr, NodeInListPtr );
84 void dllInsertNodeAfter( DoublyLinkedListNode *NewNodePtr,
85 DoublyLinkedListNode *NodeInListPtr )
87 DoublyLinkedListNode *NodeNextPtr = dllNextNode( NodeInListPtr );
88 dllLinkNodes( NodeInListPtr, NewNodePtr );
89 dllLinkNodes( NewNodePtr, NodeNextPtr );
92 void dllDumpNode( DoublyLinkedListNode *NodePtr )
95 DBUG((" 0x%x -> (0x%x) -> 0x%x\n",
96 dllPreviousNode( NodePtr ), NodePtr,
97 dllNextNode( NodePtr ) ));
100 cell_t dllCheckNode( DoublyLinkedListNode *NodePtr )
102 if( (NodePtr->dlln_Next->dlln_Previous != NodePtr) ||
103 (NodePtr->dlln_Previous->dlln_Next != NodePtr))
105 ERR("dllCheckNode: Bad Node!\n");
106 dllDumpNode( dllPreviousNode( NodePtr ) );
107 dllDumpNode( NodePtr );
108 dllDumpNode( dllNextNode( NodePtr ) );
116 void dllRemoveNode( DoublyLinkedListNode *NodePtr )
118 if( dllCheckNode( NodePtr ) == 0 )
120 dllLinkNodes( dllPreviousNode( NodePtr ), dllNextNode( NodePtr ) );
124 void dllAddNodeToHead( DoublyLinkedList *ListPtr, DoublyLinkedListNode *NewNodePtr )
126 dllInsertNodeBefore( NewNodePtr, ListPtr->dll_First );
129 void dllAddNodeToTail( DoublyLinkedList *ListPtr, DoublyLinkedListNode *NewNodePtr )
131 dllInsertNodeAfter( NewNodePtr, ListPtr->dll_Last );
134 #define dllIsNodeInList( n ) (!((n)->dlln_Next == NULL) )
135 #define dllIsLastNode( n ) ((n)->dlln_Next->dll_nNext == NULL )
136 #define dllIsListEmpty( l ) ((l)->dll_First == ((DoublyLinkedListNode *) &((l)->dll_Null)) )
137 #define dllFirstNode( l ) ((l)->dll_First)
139 static DoublyLinkedList gMemList;
141 typedef struct MemListNode
143 DoublyLinkedListNode mln_Node;
148 /***************************************************************
151 void maDumpList( void )
155 MSG("PForth MemList\n");
157 for( mln = (MemListNode *) dllFirstNode( &gMemList );
158 dllIsNodeInList( (DoublyLinkedListNode *) mln);
159 mln = (MemListNode *) dllNextNode( (DoublyLinkedListNode *) mln ) )
161 MSG(" Node at = 0x"); ffDotHex(mln);
162 MSG_NUM_H(", size = 0x", mln->mln_Size);
168 /***************************************************************
169 ** Free mem of any size.
171 static void pfFreeRawMem( char *Mem, cell_t NumBytes )
173 MemListNode *mln, *FreeNode;
174 MemListNode *AdjacentLower = NULL;
175 MemListNode *AdjacentHigher = NULL;
176 MemListNode *NextBiggest = NULL;
178 /* Allocate in whole blocks of 16 bytes */
179 DBUG(("\npfFreeRawMem( 0x%x, 0x%x )\n", Mem, NumBytes ));
180 NumBytes = (NumBytes + PF_MEM_BLOCK_SIZE - 1) & ~(PF_MEM_BLOCK_SIZE - 1);
181 DBUG(("\npfFreeRawMem: Align NumBytes to 0x%x\n", NumBytes ));
183 /* Check memory alignment. */
184 if( ( ((cell_t)Mem) & (PF_MEM_BLOCK_SIZE - 1)) != 0)
186 MSG_NUM_H("pfFreeRawMem: misaligned Mem = 0x", (cell_t) Mem );
190 /* Scan list from low to high looking for various nodes. */
191 for( mln = (MemListNode *) dllFirstNode( &gMemList );
192 dllIsNodeInList( (DoublyLinkedListNode *) mln);
193 mln = (MemListNode *) dllNextNode( (DoublyLinkedListNode *) mln ) )
195 if( (((char *) mln) + mln->mln_Size) == Mem )
199 else if( ((char *) mln) == ( Mem + NumBytes ))
201 AdjacentHigher = mln;
203 /* is this the next biggest node. */
204 else if( (NextBiggest == NULL) && (mln->mln_Size >= NumBytes) )
210 /* Check to see if we can merge nodes. */
213 DBUG((" Merge (0x%x) -> 0x%x\n", Mem, AdjacentHigher ));
214 NumBytes += AdjacentHigher->mln_Size;
215 dllRemoveNode( (DoublyLinkedListNode *) AdjacentHigher );
219 DBUG((" Merge 0x%x -> (0x%x)\n", AdjacentLower, Mem ));
220 AdjacentLower->mln_Size += NumBytes;
224 DBUG((" Link before 0x%x\n", NextBiggest ));
225 FreeNode = (MemListNode *) Mem;
226 FreeNode->mln_Size = NumBytes;
227 if( NextBiggest == NULL )
229 /* Nothing bigger so add to end of list. */
230 dllAddNodeToTail( &gMemList, (DoublyLinkedListNode *) FreeNode );
234 /* Add this node before the next biggest one we found. */
235 dllInsertNodeBefore( (DoublyLinkedListNode *) FreeNode,
236 (DoublyLinkedListNode *) NextBiggest );
245 /***************************************************************
246 ** Setup memory list. Initialize allocator.
248 static void pfInitMemBlock( void *addr, ucell_t poolSize )
253 pfDebugMessage("pfInitMemBlock()\n");
256 gMemPoolSize = poolSize;
258 dllSetupList( &gMemList );
260 /* Adjust to next highest aligned memory location. */
261 AlignedMemory = (char *) ((((cell_t)gMemPoolPtr) + PF_MEM_BLOCK_SIZE - 1) &
262 ~(PF_MEM_BLOCK_SIZE - 1));
264 /* Adjust size to reflect aligned memory. */
265 AlignedSize = gMemPoolSize - (AlignedMemory - gMemPoolPtr);
267 /* Align size of pool. */
268 AlignedSize = AlignedSize & ~(PF_MEM_BLOCK_SIZE - 1);
271 pfFreeRawMem( AlignedMemory, AlignedSize );
275 /***************************************************************
276 ** Allocate mem from list of free nodes.
278 static char *pfAllocRawMem( cell_t NumBytes )
282 pfDebugMessage("pfAllocRawMem()\n");
284 if( NumBytes <= 0 ) return NULL;
286 /* Allocate in whole blocks of 16 bytes */
287 NumBytes = (NumBytes + PF_MEM_BLOCK_SIZE - 1) & ~(PF_MEM_BLOCK_SIZE - 1);
289 DBUG(("\npfAllocRawMem( 0x%x )\n", NumBytes ));
291 /* Scan list from low to high until we find a node big enough. */
292 for( mln = (MemListNode *) dllFirstNode( &gMemList );
293 dllIsNodeInList( (DoublyLinkedListNode *) mln);
294 mln = (MemListNode *) dllNextNode( (DoublyLinkedListNode *) mln ) )
296 if( mln->mln_Size >= NumBytes )
302 /* Remove this node from list. */
303 dllRemoveNode( (DoublyLinkedListNode *) mln );
305 /* Is there enough left in block to make it worth splitting? */
306 RemSize = mln->mln_Size - NumBytes;
307 if( RemSize >= PF_MEM_BLOCK_SIZE )
309 pfFreeRawMem( (Mem + NumBytes), RemSize );
316 DBUG(("Allocate mem at 0x%x.\n", Mem ));
320 /***************************************************************
321 ** Keep mem size at first cell.
323 char *pfAllocMem( cell_t NumBytes )
327 if( NumBytes <= 0 ) return NULL;
329 /* Allocate an extra cell for size. */
330 NumBytes += sizeof(cell_t);
332 IntMem = (cell_t *)pfAllocRawMem( NumBytes );
334 if( IntMem != NULL ) *IntMem++ = NumBytes;
336 return (char *) IntMem;
339 /***************************************************************
340 ** Free mem with mem size at first cell.
342 void pfFreeMem( void *Mem )
347 if( Mem == NULL ) return;
349 /* Allocate an extra cell for size. */
350 IntMem = (cell_t *) Mem;
354 pfFreeRawMem( (char *) IntMem, NumBytes );
358 void pfInitMemoryAllocator( void )
360 pfInitMemBlock( PF_MALLOC_ADDRESS, PF_MEM_POOL_SIZE );
362 #else /* PF_NO_MALLOC */
364 int not_an_empty_file; /* Stops nasty compiler warnings when PF_NO_MALLOC not defined. */
366 #endif /* PF_NO_MALLOC */