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

   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 **
  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.
  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 */