git.gag.com Git - debian/pforth/blob - csrc/pf_mem.c

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