home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 116.lha / SmallTalk / Sources / memory.c < prev    next >
Encoding:
C/C++ Source or Header  |  1986-11-20  |  12.6 KB  |  520 lines
  1. /*
  2.     Little Smalltalk, version 2
  3.     Written by Tim Budd, Oregon State University, July 1987
  4.  
  5.     Improved incorporating suggestions by
  6.         Steve Crawley, Cambridge University, October 1987
  7.         Steven Pemberton, CWI, Amsterdam, Oct 1987
  8.  
  9.     memory management module
  10.  
  11.     This is a rather simple, straightforward, reference counting scheme.
  12.     There are no provisions for detecting cycles, nor any attempt made
  13.     at compaction.    Free lists of various sizes are maintained.
  14.     At present only objects up to 255 bytes can be allocated,
  15.     which mostly only limits the size of method (in text) you can create.
  16.  
  17.     reference counts are not stored as part of an object image, but
  18.     are instead recreated when the object is read back in.
  19.     This is accomplished using a mark-sweep algorithm, similar
  20.     to those used in garbage collection.
  21.  
  22.     There is a large amount of differences in the qualities of malloc
  23.     procedures in the Unix world.  Some perform very badly when asked
  24.     to allocate thousands of very small memory blocks, while others
  25.     take this without any difficulty.  The routine mBlockAlloc is used
  26.     to allocate a small bit of memory; the version given below
  27.     allocates a large block and then chops it up as needed; if desired,
  28.     for versions of malloc that can handle small blocks with ease
  29.     this can be replaced using the following macro:
  30.  
  31. # define mBlockAlloc(size) (object *) calloc((unsigned) size, sizeof(object))
  32.  
  33.     This can, and should, be replaced by a better memory management
  34.     algorithm.
  35. */
  36. # include <stdio.h>
  37. # include "env.h"
  38. # include "memory.h"
  39. # ifdef STRING
  40. # include <string.h>
  41. # endif
  42. # ifdef STRINGS
  43. # include <strings.h>
  44. # endif
  45.  
  46. #ifdef AMIGA
  47. # define mBlockAlloc(size) ((object *)calloc((unsigned)size,sizeof(object)))
  48. #endif
  49.  
  50. # define ObjectTableMax 5000
  51. # define MemoryBlockSize 2000
  52.  
  53. # ifdef ALLOC
  54. # include <alloc.h>
  55. # endif
  56. # ifndef ALLOC
  57. extern char *calloc();
  58. # endif
  59.  
  60. boolean debugging = false;
  61. object sysobj;    /* temporary used to avoid rereference in macros */
  62. object intobj;
  63.  
  64. object symbols;     /* table of all symbols created */
  65. object globalNames;    /* table of all accessible global names */
  66.  
  67. /*
  68.     in theory the objectTable should only be accessible to the memory
  69.     manager.  Indeed, given the right macro definitions, this can be
  70.     made so.  Never the less, for efficiency sake some of the macros
  71.     can also be defined to access the object table directly
  72. */
  73.  
  74. struct objectStruct objectTable[ObjectTableMax];
  75.  
  76. /*
  77.     The following global variables are strictly local to the memory
  78.     manager module
  79. */
  80.  
  81. # define FREELISTMAX 256
  82. static object objectFreeList[FREELISTMAX];/* free list of objects */
  83.  
  84. # ifndef mBlockAlloc
  85.         /* the current memory block being hacked up */
  86. static object *memoryBlock;        /* malloc'ed chunck of memory */
  87. static int    currentMemoryPosition;    /* last used position in above */
  88. # endif
  89.  
  90.  
  91. /* initialize the memory management module */
  92. noreturn initMemoryManager() {
  93.     int i;
  94.  
  95.     /* set all the free list pointers to zero */
  96.     for (i = 0; i < FREELISTMAX; i++)
  97.         objectFreeList[i] = nilobj;
  98.  
  99.     /* set all the reference counts to zero */
  100.     for (i = 0; i < ObjectTableMax; i++) {
  101.         objectTable[i].referenceCount = 0;
  102.         objectTable[i].size = 0;
  103.         }
  104.  
  105.     /* make up the initial free lists */
  106.     setFreeLists();
  107.  
  108. # ifndef mBlockAlloc
  109.     /* force an allocation on first object assignment */
  110.     currentMemoryPosition = MemoryBlockSize + 1;
  111. # endif
  112.  
  113.     /* object at location 0 is the nil object, so give it nonzero ref */
  114.     objectTable[0].referenceCount = 1;
  115.     objectTable[0].size = 0;
  116.     objectTable[0].type = objectMemory;
  117.  
  118. }
  119.  
  120. /* setFreeLists - initialise the free lists */
  121. setFreeLists() {
  122.     int z, i;
  123.     struct objectStruct *p;
  124.  
  125.     for (z=ObjectTableMax-1; z>0; z--) {
  126.         if (objectTable[z].referenceCount == 0){
  127.             /* Unreferenced, so do a sort of sysDecr: */
  128.             p= &objectTable[z];
  129. /*if (p->size > 0) printf("Unreferenced: %d\n", z);*/
  130.             p->class = objectFreeList[p->size];
  131.             objectFreeList[p->size]= z;
  132.             for (i= p->size; i>0; )
  133.                 p->memory[--i] = nilobj;
  134.             }
  135.         }
  136. }
  137.  
  138. /* report a (generally fatal) memory manager error */
  139. noreturn sysError(s1, s2)
  140. char *s1, *s2;
  141. {
  142.     /*    Lattice has trouble with the original definitions:
  143.     *    noreturn fprintf...
  144.     *    so they were changed.
  145.     *    3/4/88 jgh        */
  146.  
  147.     fprintf(stderr,"%s\n%s\n", s1, s2);
  148.     abort();
  149. }
  150.  
  151. /*
  152.   mBlockAlloc - rip out a block (array) of object of the given size from
  153.     the current malloc block
  154. */
  155. # ifndef mBlockAlloc
  156. static object *mBlockAlloc(memorySize)
  157. int memorySize;
  158. {    object *objptr;
  159.  
  160.     if (currentMemoryPosition + memorySize >= MemoryBlockSize) {
  161.  
  162.         /* we toss away space here.  Space-Frugal users may want to
  163.         fix this by making a new object of size
  164.         MemoryBlockSize - currentMemoryPositon - 1
  165.         and putting it on the free list, but I think
  166.         the savings is potentially small */
  167.  
  168.         memoryBlock = (object *) calloc((unsigned) MemoryBlockSize, sizeof(object));
  169.         if (! memoryBlock)
  170.             sysError("out of memory","malloc failed");
  171.         currentMemoryPosition = 0;
  172.         }
  173.     objptr = (object *) &memoryBlock[currentMemoryPosition];
  174.     currentMemoryPosition += memorySize;
  175.     return(objptr);
  176. }
  177. # endif
  178.  
  179. /* allocate a new memory object */
  180. object alcObject(memorySize, memoryType)
  181. int memorySize;
  182. int memoryType;
  183. {    int i;
  184.     register int position;
  185.     boolean done;
  186.  
  187.     if (memorySize >= FREELISTMAX) {
  188.         sysError("allocation bigger than 255","");
  189.         }
  190.  
  191.     /* first try the free lists, this is fastest */
  192.     if ((position = objectFreeList[memorySize]) != 0) {
  193.         objectFreeList[memorySize] = objectTable[position].class;
  194.         }
  195.  
  196.     /* if not there, next try making a size zero object and
  197.         making it bigger */
  198.     else if ((position = objectFreeList[0]) != 0) {
  199.         objectFreeList[0] = objectTable[position].class;
  200.         objectTable[position].size = memorySize;
  201.         objectTable[position].memory = mBlockAlloc(memorySize);
  202.         }
  203.  
  204.     else {        /* not found, must work a bit harder */
  205.         done = false;
  206.  
  207.         /* first try making a bigger object smaller */
  208.         for (i = memorySize + 1; i < FREELISTMAX; i++)
  209.             if ((position = objectFreeList[i]) != 0) {
  210.                 objectFreeList[i] = objectTable[position].class;
  211.                 /* just trim it a bit */
  212.                 objectTable[position].size = memorySize;
  213.                 done = true;
  214.                 break;
  215.                 }
  216.  
  217.         /* next try making a smaller object bigger */
  218.         if (! done)
  219.             for (i = 1; i < memorySize; i++)
  220.                 if ((position = objectFreeList[i]) != 0) {
  221.                     objectFreeList[i] =
  222.                         objectTable[position].class;
  223.                     objectTable[position].size = memorySize;
  224. # ifdef mBlockAlloc
  225.                     free(objectTable[position].memory);
  226. # endif
  227.                     objectTable[position].memory =
  228.                         mBlockAlloc(memorySize);
  229.                     done = true;
  230.                     break;
  231.                     }
  232.  
  233.         /* if we STILL don't have it then there is nothing */
  234.         /* more we can do */
  235.         if (! done)
  236.             sysError("out of objects","alloc");
  237.         }
  238.  
  239.     /* set class and type */
  240.     objectTable[position].referenceCount = 0;
  241.     objectTable[position].class = nilobj;
  242.     objectTable[position].type = memoryType;
  243.     return(position << 1);
  244. }
  245.  
  246. object allocSymbol(str)
  247. char *str;
  248. {    object newSym;
  249.  
  250.     newSym = alcObject((2 + strlen(str))/2, charMemory);
  251.     ignore strcpy(charPtr(newSym), str);
  252.     return(newSym);
  253. }
  254.  
  255. # ifdef incr
  256. object incrobj;     /* buffer for increment macro */
  257. # endif
  258. # ifndef incr
  259. noreturn incr(z)
  260. object z;
  261. {
  262.     if (z && ! isInteger(z)) {
  263.         objectTable[z>>1].referenceCount++;
  264.         }
  265. }
  266. # endif
  267.  
  268. # ifndef decr
  269. noreturn decr(z)
  270. object z;
  271. {
  272.     if (z && ! isInteger(z)) {
  273.         if (--objectTable[z>>1].referenceCount <= 0) {
  274.             sysDecr(z);
  275.             }
  276.         }
  277. }
  278. # endif
  279.  
  280. /* do the real work in the decr procedure */
  281. noreturn sysDecr(z)
  282. object z;
  283. {    register struct objectStruct *p;
  284.     register int i;
  285.  
  286.     p = &objectTable[z>>1];
  287.     if (p->referenceCount < 0) {
  288.         sysError("negative reference count","");
  289.         }
  290.     decr(p->class);
  291.     p->class = objectFreeList[p->size];
  292.     objectFreeList[p->size] = z>>1;
  293.     if (((int) p->size) > 0) {
  294.         if (p->type == objectMemory)
  295.             for (i = p->size; i > 0 ; )
  296.                 decr(p->memory[--i]);
  297.         for (i = p->size; i > 0; )
  298.             p->memory[--i] = nilobj;
  299.         }
  300.  
  301. }
  302.  
  303. # ifndef basicAt
  304. object basicAt(z, i)
  305. object z;
  306. register int i;
  307. {
  308.     if (isInteger(z))
  309.         sysError("attempt to index","into integer");
  310.     else if ((i <= 0) || (i > objectSize(z))) {
  311.         ignore fprintf(stderr,"index %d size %d\n", i, (int) objectSize(z));
  312.         sysError("index out of range","in basicAt");
  313.         }
  314.     else
  315.         return(sysMemPtr(z)[i-1]);
  316.     return(0);
  317. }
  318. # endif
  319. # ifndef basicAtPut
  320.  
  321. noreturn basicAtPut(z, i, v)
  322. object z, v;
  323. register int i;
  324. {
  325.     if (isInteger(z))
  326.         sysError("assigning index to","integer value");
  327.     else if ((i <= 0) || (i > objectSize(z))) {
  328.         ignore fprintf(stderr,"index %d size %d\n", i, (int) objectSize(z));
  329.         sysError("index out of range","in basicAtPut");
  330.         }
  331.     else {
  332.         incr(v);
  333.         decr(sysMemPtr(z)[i-1]);
  334.         sysMemPtr(z)[i-1] = v;
  335.         }
  336. }
  337. # endif
  338.  
  339. # ifndef byteAt
  340. int byteAt(z, i)
  341. object z;
  342. register int i;
  343. {    char *bp;
  344.  
  345.     if (isInteger(z))
  346.         sysError("indexing integer","byteAt");
  347.     else if ((i <= 0) || (i > 2 * objectSize(z))) {
  348.         sysError("index out of range","byteAt");
  349.         }
  350.     else {
  351.         bp = charPtr(z);
  352.         i = bp[i-1];
  353.         }
  354.     return(i);
  355. }
  356. # endif
  357.  
  358. # ifndef byteAtPut
  359. noreturn byteAtPut(z, i, x)
  360. object z;
  361. int i, x;
  362. {    char *bp;
  363.  
  364.     if (isInteger(z))
  365.         sysError("indexing integer","byteAtPut");
  366.     else if ((i <= 0) || (i > 2 * objectSize(z))) {
  367.         sysError("index out of range", "byteAtPut");
  368.         }
  369.     else {
  370.         bp = charPtr(z);
  371.         bp[i-1] = x;
  372.         }
  373. }
  374. # endif
  375. /*
  376.     imageWrite - write out an object image
  377. */
  378. static iwerr() { sysError("imageWrite count error",""); }
  379.  
  380. /* ptr - used for conversions to keep lint happy */
  381. # define ptr(x) ((char *) x)
  382.  
  383. noreturn imageWrite(fp)
  384. FILE *fp;
  385. {    short i;
  386.  
  387.     if (fwrite(ptr(&symbols), sizeof(object), 1, fp) != 1) iwerr();
  388.     if (fwrite(ptr(&globalNames), sizeof(object), 1, fp) != 1) iwerr();
  389.  
  390.     for (i = 0; i < ObjectTableMax; i++) {
  391.         if (objectTable[i].referenceCount > 0) {
  392.             if (fwrite(ptr(&i), sizeof(short), 1, fp) != 1) iwerr();
  393.             if (fwrite(ptr(&objectTable[i].class), sizeof(object), 1, fp)
  394.                 != 1) iwerr();
  395.             if (fwrite(ptr(&objectTable[i].size), sizeof(byte), 1, fp)
  396.                 != 1) iwerr();
  397.             if (fwrite(ptr(&objectTable[i].type), sizeof(byte), 1, fp)
  398.                 != 1) iwerr();
  399.             if (objectTable[i].size != 0)
  400.                 if (fwrite(ptr(objectTable[i].memory), sizeof(object),
  401.                     (int) byteToInt(objectTable[i].size), fp) != byteToInt(objectTable[i].size))
  402.                         iwerr();
  403.             }
  404.         }
  405. }
  406.  
  407. /*
  408. Written by Steven Pemberton:
  409. The following routine assures that objects read in are really referenced,
  410. eliminating junk that may be in the object file but not referenced.
  411. It is essentially a marking garbage collector algorithm using the
  412. reference counts as the mark
  413. */
  414.  
  415. static visit(x)
  416. object x;
  417. {
  418.     int i, s;
  419.     object *p;
  420.  
  421.     if (x && !isInteger(x)) {
  422.         if (++(objectTable[x>>1].referenceCount) == 1) {
  423.             /* then it's the first time we've visited it, so: */
  424.             visit(objectTable[x>>1].class);
  425.             s= (int) byteToInt(objectTable[x>>1].size);
  426.             if (s>0 && objectTable[x>>1].type == objectMemory) {
  427.                 p= objectTable[x>>1].memory;
  428.                 for (i=0; i < s; i++) visit(p[i]);
  429.                 }
  430.             }
  431.         }
  432. }
  433.  
  434. /*
  435.     imageRead - read in an object image
  436.         we toss out the free lists built initially,
  437.         reconstruct the linkages, then rebuild the free
  438.         lists around the new objects.
  439.         The only objects with nonzero reference counts
  440.         will be those reachable from either symbols or
  441.         globalNames.
  442. */
  443. static irerr() { sysError("imageWrite count error",""); }
  444.  
  445. noreturn imageRead(fp)
  446. FILE *fp;
  447. {    short i;
  448.     object *p;
  449.  
  450.     if (fread(ptr(&symbols), sizeof(object), 1, fp) != 1) irerr();
  451.     if (fread(ptr(&globalNames), sizeof(object), 1, fp) != 1) irerr();
  452.  
  453.     while(fread(ptr(&i), sizeof(short), 1, fp) == 1) {
  454.         if ((i < 0) || (i > ObjectTableMax))
  455.             sysError("index out of range","imageRead");
  456.         if (fread(ptr(&objectTable[i].class), sizeof(object), 1, fp)
  457.                 != 1) irerr();
  458.         if ((objectTable[i].class < 0) ||
  459.             (objectTable[i].class > ObjectTableMax))
  460.                 sysError("class out of range","imageRead");
  461.         if (fread(ptr(&objectTable[i].size), sizeof(byte), 1, fp)
  462.                 != 1) irerr();
  463.         if (fread(ptr(&objectTable[i].type), sizeof(byte), 1, fp)
  464.                 != 1) irerr();
  465.         if (objectTable[i].size != 0) {
  466.             p = objectTable[i].memory = mBlockAlloc((int) objectTable[i].size);
  467.             if (fread(ptr(p), sizeof(object),
  468.                  (int) byteToInt(objectTable[i].size), fp) != byteToInt(objectTable[i].size))
  469.                         irerr();
  470.             }
  471.         else
  472.             objectTable[i].memory = (object *) 0;
  473.         }
  474.  
  475.     /* now restore ref counts, getting rid of unneeded junk */
  476.     visit(symbols);
  477.     visit(globalNames);
  478.     /* toss out the old free lists, build new ones */
  479.     objectFreeList[0] = nilobj;
  480.     setFreeLists();
  481. }
  482.  
  483. static ncopy(p, q, n)
  484. char *p, *q;
  485. int n;
  486. {
  487.  
  488.     while (n>0) {
  489.         *p++ = *q++;
  490.         n--;
  491.         }
  492. }
  493.  
  494. object allocFloat(d)
  495. double d;
  496. {    object newObj;
  497.  
  498.     newObj = alcObject((int) sizeof (double), floatMemory);
  499.     ncopy(charPtr(newObj), (char *) &d, (int) sizeof (double));
  500.     return(newObj);
  501. }
  502.  
  503. double floatValue(obj)
  504. object obj;
  505. {    double d;
  506.  
  507.     ncopy((char *) &d, charPtr(obj), (int) sizeof (double));
  508.     return(d);
  509. }
  510.  
  511. int objcount()
  512. {    int i, count;
  513.  
  514.  
  515.     for (count = i = 0; i < ObjectTableMax; i++)
  516.         if (objectTable[i].referenceCount > 0)
  517.             count++;
  518.     return(count);
  519. }
  520.