Commit | Line | Data |
---|---|---|
8e9db35f PB |
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. | |
4 | ** | |
5 | ** For PForth based on 'C' | |
6 | ** | |
7 | ** Author: Phil Burk | |
8 | ** Copyright 1994 3DO, Phil Burk, Larry Polansky, David Rosenboom | |
9 | ** | |
1f99f95d S |
10 | ** Permission to use, copy, modify, and/or distribute this |
11 | ** software for any purpose with or without fee is hereby granted. | |
12 | ** | |
13 | ** THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL | |
14 | ** WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED | |
15 | ** WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL | |
16 | ** THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR | |
17 | ** CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING | |
18 | ** FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF | |
19 | ** CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF | |
20 | ** OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. | |
8e9db35f PB |
21 | ** |
22 | **************************************************************** | |
23 | ** | |
24 | ***************************************************************/ | |
25 | ||
26 | #include "pf_all.h" | |
27 | ||
28 | ||
29 | #ifdef PF_NO_MALLOC | |
30 | ||
31 | static char *gMemPoolPtr; | |
32 | static ucell_t gMemPoolSize; | |
33 | ||
34 | /* CUSTOM: Make the memory pool bigger if you want. */ | |
35 | #ifndef PF_MEM_POOL_SIZE | |
36 | #define PF_MEM_POOL_SIZE (0x100000) | |
37 | #endif | |
38 | ||
39 | #define PF_MEM_BLOCK_SIZE (16) | |
40 | ||
41 | #ifndef PF_MALLOC_ADDRESS | |
42 | static char MemoryPool[PF_MEM_POOL_SIZE]; | |
43 | #define PF_MALLOC_ADDRESS MemoryPool | |
44 | #endif | |
45 | ||
46 | /********************************************************** | |
47 | ** Doubly Linked List Tools | |
48 | **********************************************************/ | |
49 | ||
50 | typedef struct DoublyLinkedListNode_s | |
51 | { | |
52 | struct DoublyLinkedListNode_s *dlln_Next; | |
53 | struct DoublyLinkedListNode_s *dlln_Previous; | |
54 | } DoublyLinkedListNode; | |
55 | ||
56 | typedef struct DoublyLinkedList_s | |
57 | { | |
58 | DoublyLinkedListNode *dll_First; | |
59 | DoublyLinkedListNode *dll_Null; | |
60 | DoublyLinkedListNode *dll_Last; | |
61 | } DoublyLinkedList; | |
62 | ||
63 | #define dllPreviousNode(n) ((n)->dlln_Previous) | |
64 | #define dllNextNode(n) ((n)->dlln_Next) | |
65 | ||
66 | void dllSetupList( DoublyLinkedList *dll ) | |
67 | { | |
68 | dll->dll_First = &(dll->dll_Null); | |
69 | dll->dll_Null = (DoublyLinkedListNode *) NULL; | |
70 | dll->dll_Last = &(dll->dll_First); | |
71 | } | |
72 | ||
73 | void dllLinkNodes( DoublyLinkedListNode *Node0, DoublyLinkedListNode *Node1 ) | |
74 | { | |
75 | Node0->dlln_Next = Node1; | |
76 | Node1->dlln_Previous = Node0; | |
77 | } | |
78 | ||
79 | void dllInsertNodeBefore( DoublyLinkedListNode *NewNodePtr, | |
80 | DoublyLinkedListNode *NodeInListPtr ) | |
81 | { | |
82 | DoublyLinkedListNode *NodePreviousPtr = dllPreviousNode( NodeInListPtr ); | |
83 | dllLinkNodes( NodePreviousPtr, NewNodePtr ); | |
84 | dllLinkNodes( NewNodePtr, NodeInListPtr ); | |
85 | } | |
86 | ||
87 | void dllInsertNodeAfter( DoublyLinkedListNode *NewNodePtr, | |
88 | DoublyLinkedListNode *NodeInListPtr ) | |
89 | { | |
90 | DoublyLinkedListNode *NodeNextPtr = dllNextNode( NodeInListPtr ); | |
91 | dllLinkNodes( NodeInListPtr, NewNodePtr ); | |
92 | dllLinkNodes( NewNodePtr, NodeNextPtr ); | |
93 | } | |
94 | ||
95 | void dllDumpNode( DoublyLinkedListNode *NodePtr ) | |
96 | { | |
97 | TOUCH(NodePtr); | |
98 | DBUG((" 0x%x -> (0x%x) -> 0x%x\n", | |
99 | dllPreviousNode( NodePtr ), NodePtr, | |
100 | dllNextNode( NodePtr ) )); | |
101 | } | |
102 | ||
103 | cell_t dllCheckNode( DoublyLinkedListNode *NodePtr ) | |
104 | { | |
105 | if( (NodePtr->dlln_Next->dlln_Previous != NodePtr) || | |
106 | (NodePtr->dlln_Previous->dlln_Next != NodePtr)) | |
107 | { | |
108 | ERR("dllCheckNode: Bad Node!\n"); | |
109 | dllDumpNode( dllPreviousNode( NodePtr ) ); | |
110 | dllDumpNode( NodePtr ); | |
111 | dllDumpNode( dllNextNode( NodePtr ) ); | |
112 | return -1; | |
113 | } | |
114 | else | |
115 | { | |
116 | return 0; | |
117 | } | |
118 | } | |
119 | void dllRemoveNode( DoublyLinkedListNode *NodePtr ) | |
120 | { | |
121 | if( dllCheckNode( NodePtr ) == 0 ) | |
122 | { | |
123 | dllLinkNodes( dllPreviousNode( NodePtr ), dllNextNode( NodePtr ) ); | |
124 | } | |
125 | } | |
126 | ||
127 | void dllAddNodeToHead( DoublyLinkedList *ListPtr, DoublyLinkedListNode *NewNodePtr ) | |
128 | { | |
129 | dllInsertNodeBefore( NewNodePtr, ListPtr->dll_First ); | |
130 | } | |
131 | ||
132 | void dllAddNodeToTail( DoublyLinkedList *ListPtr, DoublyLinkedListNode *NewNodePtr ) | |
133 | { | |
134 | dllInsertNodeAfter( NewNodePtr, ListPtr->dll_Last ); | |
135 | } | |
136 | ||
137 | #define dllIsNodeInList( n ) (!((n)->dlln_Next == NULL) ) | |
138 | #define dllIsLastNode( n ) ((n)->dlln_Next->dll_nNext == NULL ) | |
139 | #define dllIsListEmpty( l ) ((l)->dll_First == ((DoublyLinkedListNode *) &((l)->dll_Null)) ) | |
140 | #define dllFirstNode( l ) ((l)->dll_First) | |
141 | ||
142 | static DoublyLinkedList gMemList; | |
143 | ||
144 | typedef struct MemListNode | |
145 | { | |
146 | DoublyLinkedListNode mln_Node; | |
147 | cell_t mln_Size; | |
148 | } MemListNode; | |
149 | ||
150 | #ifdef PF_DEBUG | |
151 | /*************************************************************** | |
152 | ** Dump memory list. | |
153 | */ | |
154 | void maDumpList( void ) | |
155 | { | |
156 | MemListNode *mln; | |
157 | ||
158 | MSG("PForth MemList\n"); | |
159 | ||
160 | for( mln = (MemListNode *) dllFirstNode( &gMemList ); | |
161 | dllIsNodeInList( (DoublyLinkedListNode *) mln); | |
162 | mln = (MemListNode *) dllNextNode( (DoublyLinkedListNode *) mln ) ) | |
163 | { | |
164 | MSG(" Node at = 0x"); ffDotHex(mln); | |
165 | MSG_NUM_H(", size = 0x", mln->mln_Size); | |
166 | } | |
167 | } | |
168 | #endif | |
169 | ||
170 | ||
171 | /*************************************************************** | |
172 | ** Free mem of any size. | |
173 | */ | |
174 | static void pfFreeRawMem( char *Mem, cell_t NumBytes ) | |
175 | { | |
176 | MemListNode *mln, *FreeNode; | |
177 | MemListNode *AdjacentLower = NULL; | |
178 | MemListNode *AdjacentHigher = NULL; | |
179 | MemListNode *NextBiggest = NULL; | |
180 | ||
181 | /* Allocate in whole blocks of 16 bytes */ | |
182 | DBUG(("\npfFreeRawMem( 0x%x, 0x%x )\n", Mem, NumBytes )); | |
183 | NumBytes = (NumBytes + PF_MEM_BLOCK_SIZE - 1) & ~(PF_MEM_BLOCK_SIZE - 1); | |
184 | DBUG(("\npfFreeRawMem: Align NumBytes to 0x%x\n", NumBytes )); | |
185 | ||
186 | /* Check memory alignment. */ | |
187 | if( ( ((cell_t)Mem) & (PF_MEM_BLOCK_SIZE - 1)) != 0) | |
188 | { | |
189 | MSG_NUM_H("pfFreeRawMem: misaligned Mem = 0x", (cell_t) Mem ); | |
190 | return; | |
191 | } | |
192 | ||
193 | /* Scan list from low to high looking for various nodes. */ | |
194 | for( mln = (MemListNode *) dllFirstNode( &gMemList ); | |
195 | dllIsNodeInList( (DoublyLinkedListNode *) mln); | |
196 | mln = (MemListNode *) dllNextNode( (DoublyLinkedListNode *) mln ) ) | |
197 | { | |
198 | if( (((char *) mln) + mln->mln_Size) == Mem ) | |
199 | { | |
200 | AdjacentLower = mln; | |
201 | } | |
202 | else if( ((char *) mln) == ( Mem + NumBytes )) | |
203 | { | |
204 | AdjacentHigher = mln; | |
205 | } | |
206 | /* is this the next biggest node. */ | |
207 | else if( (NextBiggest == NULL) && (mln->mln_Size >= NumBytes) ) | |
208 | { | |
209 | NextBiggest = mln; | |
210 | } | |
211 | } | |
212 | ||
213 | /* Check to see if we can merge nodes. */ | |
214 | if( AdjacentHigher ) | |
215 | { | |
216 | DBUG((" Merge (0x%x) -> 0x%x\n", Mem, AdjacentHigher )); | |
217 | NumBytes += AdjacentHigher->mln_Size; | |
218 | dllRemoveNode( (DoublyLinkedListNode *) AdjacentHigher ); | |
219 | } | |
220 | if( AdjacentLower ) | |
221 | { | |
222 | DBUG((" Merge 0x%x -> (0x%x)\n", AdjacentLower, Mem )); | |
223 | AdjacentLower->mln_Size += NumBytes; | |
224 | } | |
225 | else | |
226 | { | |
227 | DBUG((" Link before 0x%x\n", NextBiggest )); | |
228 | FreeNode = (MemListNode *) Mem; | |
229 | FreeNode->mln_Size = NumBytes; | |
230 | if( NextBiggest == NULL ) | |
231 | { | |
232 | /* Nothing bigger so add to end of list. */ | |
233 | dllAddNodeToTail( &gMemList, (DoublyLinkedListNode *) FreeNode ); | |
234 | } | |
235 | else | |
236 | { | |
237 | /* Add this node before the next biggest one we found. */ | |
238 | dllInsertNodeBefore( (DoublyLinkedListNode *) FreeNode, | |
239 | (DoublyLinkedListNode *) NextBiggest ); | |
240 | } | |
241 | } | |
242 | ||
243 | /* maDumpList(); */ | |
244 | } | |
245 | ||
246 | ||
247 | ||
248 | /*************************************************************** | |
249 | ** Setup memory list. Initialize allocator. | |
250 | */ | |
251 | static void pfInitMemBlock( void *addr, ucell_t poolSize ) | |
252 | { | |
253 | char *AlignedMemory; | |
254 | cell_t AlignedSize; | |
255 | ||
256 | pfDebugMessage("pfInitMemBlock()\n"); | |
257 | /* Set globals. */ | |
258 | gMemPoolPtr = addr; | |
259 | gMemPoolSize = poolSize; | |
260 | ||
261 | dllSetupList( &gMemList ); | |
262 | ||
263 | /* Adjust to next highest aligned memory location. */ | |
264 | AlignedMemory = (char *) ((((cell_t)gMemPoolPtr) + PF_MEM_BLOCK_SIZE - 1) & | |
265 | ~(PF_MEM_BLOCK_SIZE - 1)); | |
266 | ||
267 | /* Adjust size to reflect aligned memory. */ | |
268 | AlignedSize = gMemPoolSize - (AlignedMemory - gMemPoolPtr); | |
269 | ||
270 | /* Align size of pool. */ | |
271 | AlignedSize = AlignedSize & ~(PF_MEM_BLOCK_SIZE - 1); | |
272 | ||
273 | /* Free to pool. */ | |
274 | pfFreeRawMem( AlignedMemory, AlignedSize ); | |
275 | ||
276 | } | |
277 | ||
278 | /*************************************************************** | |
279 | ** Allocate mem from list of free nodes. | |
280 | */ | |
281 | static char *pfAllocRawMem( cell_t NumBytes ) | |
282 | { | |
283 | char *Mem = NULL; | |
284 | MemListNode *mln; | |
285 | pfDebugMessage("pfAllocRawMem()\n"); | |
286 | ||
287 | if( NumBytes <= 0 ) return NULL; | |
288 | ||
289 | /* Allocate in whole blocks of 16 bytes */ | |
290 | NumBytes = (NumBytes + PF_MEM_BLOCK_SIZE - 1) & ~(PF_MEM_BLOCK_SIZE - 1); | |
291 | ||
292 | DBUG(("\npfAllocRawMem( 0x%x )\n", NumBytes )); | |
293 | ||
294 | /* Scan list from low to high until we find a node big enough. */ | |
295 | for( mln = (MemListNode *) dllFirstNode( &gMemList ); | |
296 | dllIsNodeInList( (DoublyLinkedListNode *) mln); | |
297 | mln = (MemListNode *) dllNextNode( (DoublyLinkedListNode *) mln ) ) | |
298 | { | |
299 | if( mln->mln_Size >= NumBytes ) | |
300 | { | |
301 | cell_t RemSize; | |
302 | ||
303 | Mem = (char *) mln; | |
304 | ||
305 | /* Remove this node from list. */ | |
306 | dllRemoveNode( (DoublyLinkedListNode *) mln ); | |
307 | ||
308 | /* Is there enough left in block to make it worth splitting? */ | |
309 | RemSize = mln->mln_Size - NumBytes; | |
310 | if( RemSize >= PF_MEM_BLOCK_SIZE ) | |
311 | { | |
312 | pfFreeRawMem( (Mem + NumBytes), RemSize ); | |
313 | } | |
314 | break; | |
315 | } | |
316 | ||
317 | } | |
318 | /* maDumpList(); */ | |
319 | DBUG(("Allocate mem at 0x%x.\n", Mem )); | |
320 | return Mem; | |
321 | } | |
322 | ||
323 | /*************************************************************** | |
324 | ** Keep mem size at first cell. | |
325 | */ | |
326 | char *pfAllocMem( cell_t NumBytes ) | |
327 | { | |
328 | cell_t *IntMem; | |
329 | ||
330 | if( NumBytes <= 0 ) return NULL; | |
331 | ||
332 | /* Allocate an extra cell for size. */ | |
333 | NumBytes += sizeof(cell_t); | |
334 | ||
335 | IntMem = (cell_t *)pfAllocRawMem( NumBytes ); | |
336 | ||
337 | if( IntMem != NULL ) *IntMem++ = NumBytes; | |
338 | ||
339 | return (char *) IntMem; | |
340 | } | |
341 | ||
342 | /*************************************************************** | |
343 | ** Free mem with mem size at first cell. | |
344 | */ | |
345 | void pfFreeMem( void *Mem ) | |
346 | { | |
347 | cell_t *IntMem; | |
348 | cell_t NumBytes; | |
349 | ||
350 | if( Mem == NULL ) return; | |
351 | ||
352 | /* Allocate an extra cell for size. */ | |
353 | IntMem = (cell_t *) Mem; | |
354 | IntMem--; | |
355 | NumBytes = *IntMem; | |
356 | ||
357 | pfFreeRawMem( (char *) IntMem, NumBytes ); | |
358 | ||
359 | } | |
360 | ||
361 | void pfInitMemoryAllocator( void ) | |
362 | { | |
363 | pfInitMemBlock( PF_MALLOC_ADDRESS, PF_MEM_POOL_SIZE ); | |
364 | } | |
365 | #else /* PF_NO_MALLOC */ | |
366 | ||
367 | int not_an_empty_file; /* Stops nasty compiler warnings when PF_NO_MALLOC not defined. */ | |
368 | ||
369 | #endif /* PF_NO_MALLOC */ |