home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume31 / jgraph / part06 / jmalloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-07-14  |  11.3 KB  |  445 lines
  1. #include <stdio.h>
  2. #include <malloc.h>
  3.  
  4. /* Each memory block has 8 extra 32-bit values associated with it.  If malloc
  5.    returns the pointer p to you, the state really looks like:
  6.  
  7. jmal(p)------>  |------------------------------------------------------------|
  8.                 | flink (next malloc block in absolute order)                |
  9.                 |------------------------------------------------------------|
  10.                 | blink (prev malloc block in absolute order)                |
  11.                 |------------------------------------------------------------|
  12.                 | nextfree (next free malloc block - no particular order)    |
  13.                 |------------------------------------------------------------|
  14.                 | prevfree (next free malloc block - no particular order)    |
  15.                 |------------------------------------------------------------|
  16.                 | size (size of memory allocated)                            |
  17.                 |------------------------------------------------------------|
  18.                 | cs2 (pointer to the second checksum, which is right after  |
  19.                 |   the mem block)                                           |
  20.                 |------------------------------------------------------------|
  21.                 | cs (checksum right before mem block.  used to determine if |
  22.                 |   there is an error of writing around the memory block)    |
  23. p------------>  |------------------------------------------------------------|
  24.                 | space: the memory block                                    |
  25.                 |                  ...                                       |
  26.                 |                  ...                                       |
  27.                 |------------------------------------------------------------|
  28.             | the second checksum                                        |
  29.                 |------------------------------------------------------------|
  30. */
  31.  
  32.  
  33. typedef struct jmalloc {
  34.   struct jmalloc *flink;
  35.   struct jmalloc *blink;
  36.   struct jmalloc *nextfree;
  37.   struct jmalloc *prevfree;
  38.   int size;
  39.   int *cs2;
  40.   int cs;
  41.   char *space;
  42. } *Jmalloc;
  43.  
  44. #define JMSZ (sizeof(struct jmalloc))
  45. #define PTSZ (sizeof(char *))  /* Also assuming its > sizeof int */
  46. #define CHUNK_SIZE (16384 - JMSZ)    /* 16K */
  47. #define MASK 0x17826a9b
  48. #define JNULL ((Jmalloc) 0)
  49.  
  50. static struct jmalloc j_head;
  51. static Jmalloc memlist;
  52. static int nfree = 0;
  53. static int nblocks = 0;
  54. static int init = 0;
  55. static Jmalloc start;
  56. static int free_called = 0;
  57. static int malloc_called = 0;
  58. static int used_mem = 0;
  59. static int free_mem = 0;
  60. static int used_blocks = 0;
  61. static int free_blocks = 0;
  62.  
  63. #define cksum(p) (((int) &(p->cs)) - 1)
  64. #define jloc(l) ((char *) (&l->space))
  65. #define jmal(l) ((Jmalloc) (((char *)l) - JMSZ + PTSZ))
  66. #define isfree(l) (l->nextfree != JNULL)
  67.  
  68. #define do_init() \
  69.   if (!init) {\
  70.     memlist = &j_head;\
  71.     memlist->flink = memlist;\
  72.     memlist->blink = memlist;\
  73.     memlist->nextfree = memlist;\
  74.     memlist->prevfree = memlist;\
  75.     memlist->size = 0;\
  76.     memlist->cs = cksum(memlist);\
  77.     memlist->cs2 = &memlist->cs;\
  78.     memlist->space = (char *) 0;\
  79.     start = memlist;\
  80.     init = 1;\
  81.   }
  82.  
  83. dump_core()
  84. {
  85.   memlist->space[0] = 0;
  86. }
  87.  
  88. char *set_used(l)
  89. Jmalloc l;
  90. {
  91.   start = l->nextfree;
  92.   l->prevfree->nextfree = l->nextfree;
  93.   l->nextfree->prevfree = l->prevfree;
  94.   l->prevfree = JNULL;
  95.   l->nextfree = JNULL;
  96.   used_mem += l->size;
  97.   free_mem -= l->size;
  98.   used_blocks++;
  99.   free_blocks--;
  100.  
  101.   return jloc(l);
  102. }
  103.  
  104. void *malloc(size)
  105. int size;
  106. {
  107.   int redo;
  108.   int done;
  109.   Jmalloc l;
  110.   char *tmp;
  111.   Jmalloc newl;
  112.   int newsize;
  113.   
  114.   do_init();
  115.   malloc_called++;
  116.   if (size <= 0) {
  117.     fprintf(stderr, "Error: Malloc(%d) called\n", size);
  118.     /* Dump core */
  119.     dump_core();
  120.   }
  121.     
  122.   if (size % PTSZ != 0) size += PTSZ - (size % PTSZ);
  123.  
  124.   done = 0;
  125.   l = start;
  126.   while(!done) {
  127.     if (l->size >= size) {
  128.       done = 1;
  129.       redo = 0;
  130.     } else {
  131.       l = l->nextfree;
  132.       done = (l == start);
  133.       redo = done;
  134.     } 
  135.   }
  136.       
  137.   if (redo) {
  138.     if (size > CHUNK_SIZE) 
  139.       newsize = size + JMSZ; 
  140.       else newsize = CHUNK_SIZE + JMSZ;
  141.     newl = (Jmalloc) sbrk(newsize);
  142.     while (newl == (Jmalloc) -1 && newsize > size + JMSZ) {
  143.       newsize /= 2;
  144.       if (newsize < size + JMSZ) newsize = size + JMSZ;
  145.       newl = (Jmalloc) sbrk(newsize);
  146.     }
  147.       
  148.     if (newl == (Jmalloc) -1) {
  149. /*       fprintf(stderr, "Jmalloc: out of memory\n"); */
  150. /*       fprintf(stderr, "Used bytes = %d, Free bytes = %d\n",  */
  151. /*               used_mem, free_mem); */
  152. /*       fprintf(stderr, "Trying to get %d bytes (chunk of %d)\n",  */
  153. /*               size, newsize); */
  154.       return NULL;
  155.     }
  156.     newl->flink = memlist;
  157.     newl->blink = memlist->blink;
  158.     newl->flink->blink = newl;
  159.     newl->blink->flink = newl;
  160.     newl->nextfree = memlist;
  161.     newl->prevfree = memlist->prevfree;
  162.     newl->nextfree->prevfree = newl;
  163.     newl->prevfree->nextfree = newl;
  164.     newl->size = ((char *) sbrk(0)) - jloc(newl) - PTSZ;
  165.     free_mem += newl->size;
  166.     newl->cs = cksum(newl);
  167.     newl->cs2 = ((int *) (jloc(newl) + newl->size));
  168.     *(newl->cs2) = cksum(newl);
  169.     if(newl->size < size) {
  170.       fprintf(stderr, "Newl->size(%d) < size(%d)\n", newl->size, size);
  171.       exit(1);
  172.     }
  173.     free_blocks++;
  174.     l = newl;
  175.   } 
  176.  
  177.   if (l->size - size < JMSZ) {
  178.     return set_used(l);
  179.   } else {
  180.     tmp = jloc(l);
  181.     newl = (Jmalloc) (tmp + size + PTSZ);
  182.     newl->flink = l->flink;
  183.     newl->blink = l;
  184.     newl->flink->blink = newl;
  185.     newl->blink->flink = newl;
  186.     newl->nextfree = l->nextfree;
  187.     newl->prevfree = l;
  188.     newl->nextfree->prevfree = newl;
  189.     newl->prevfree->nextfree = newl;
  190.     newl->size = l->size - size - JMSZ;
  191.     newl->cs = cksum(newl);
  192.     newl->cs2 = (int *) (jloc(newl) + newl->size);
  193.     *(newl->cs2) = cksum(newl);
  194.     free_mem += size + newl->size - l->size;
  195.     free_blocks++;
  196.     l->size = size;
  197.     l->cs2 = ((int *) (jloc(l) + l->size));
  198.     *(l->cs2) = cksum(l);
  199.     return set_used(l);
  200.   }
  201. }
  202.  
  203. jmalloc_print_mem()
  204. {
  205.   Jmalloc l;
  206.   int done;
  207.   char *bufs[100];
  208.   int sizes[100];
  209.   int mc;
  210.   int fc;
  211.   int i, j;
  212.  
  213.   do_init();
  214.   mc = malloc_called;
  215.   fc = free_called;
  216.   if (jmal(jloc(memlist)) != memlist) {
  217.     fprintf(stderr, "TROUBLE: memlist=0x%x, jmal(jloc(memlist))=0x%x)\n",
  218.             memlist, jmal(jloc(memlist)));
  219.     exit(1);
  220.   }
  221.   done = 0;
  222.   l = start;
  223.   i = 0;
  224.   while (!done) {
  225.     if (cksum(l) != l->cs) {
  226.       printf("Memory location 0x%x corrupted\n", jloc(l));
  227.       exit(1);
  228.     } else if (cksum(l) != *(l->cs2)) {
  229.       printf("Memory location 0x%x corrupted\n", jloc(l));
  230.       exit(1);
  231.     }
  232.     
  233.     bufs[i] = jloc(l);
  234.     sizes[i] = l->size;
  235.     if (l->nextfree == 0) sizes[i] = -sizes[i];
  236.     i++;
  237.     l = l->flink;
  238.     done = ((l == start) || i >= 100);
  239.   }
  240.   printf("Malloc called %d times\n", mc);
  241.   printf("Free called %d times\n", fc);
  242.   for (j = 0; j < i; j++) {
  243.     printf("Loc = 0x%x, size = %d, free = %d\n", bufs[j], 
  244.            (sizes[j] > 0) ? sizes[j] : -sizes[j], (sizes[j] >= 0));
  245.   }
  246. }
  247.  
  248. jmalloc_check_mem()
  249. {
  250.   Jmalloc l;
  251.   int done;
  252.  
  253.   done = 0;
  254.  
  255.   l = start;
  256.  
  257.   while (!done) {
  258.     if (cksum(l) != l->cs) {
  259.       fprintf(stderr, "Memory chunk violated: 0x%x: %s 0x%x.  %s 0x%x\n", 
  260.               jloc(l), "Checksum 1 is ", l->cs, "It should be", cksum(l));
  261.       dump_core();
  262.     } else if (cksum(l) != *(l->cs2)) {
  263.       fprintf(stderr, "Memory chunk violated: 0x%x: %s 0x%x.  %s 0x%x\n", 
  264.               jloc(l), "Checksum 2 is ", *(l->cs2), "It should be", cksum(l));
  265.       dump_core();
  266.     }
  267.     l = l->flink;
  268.     done = (l == start);
  269.   }
  270. }
  271.  
  272.   
  273. void free(loc)
  274. char *loc;
  275. {
  276.   Jmalloc l;
  277.   Jmalloc pl, nl;
  278.  
  279.   do_init();
  280.   free_called++;
  281.   l = jmal(loc); 
  282.  
  283.   if (cksum(l) != l->cs) {
  284.     fprintf(stderr, "Error on free: memory chunk violated: 0x%x\n", loc);
  285.     dump_core();
  286.   } else if (cksum(l) != *(l->cs2)) {
  287.     fprintf(stderr, "Error on free: memory chunk violated: 0x%x\n", loc);
  288.     dump_core();
  289.   }
  290.  
  291.   used_mem -= l->size;
  292.   free_mem += l->size;
  293.   free_blocks++;
  294.   used_blocks--;
  295.  
  296.   pl = l->blink;
  297.   nl = l->flink;
  298.   if (isfree(pl) && (jloc(pl)+pl->size + PTSZ == (char *) l)) {
  299.     free_mem += JMSZ;
  300.     pl->size += l->size + JMSZ;
  301.     pl->flink = nl;
  302.     pl->flink->blink = pl;
  303.     l = pl;
  304.     free_blocks--;
  305.   } else {
  306.     l->prevfree = start;
  307.     l->nextfree = start->nextfree;
  308.     l->nextfree->prevfree = l;
  309.     l->prevfree->nextfree = l;
  310.   }
  311.  
  312.   if (isfree(nl) && jloc(l)+l->size + PTSZ == (char *) nl) {
  313.     free_mem += JMSZ;
  314.     l->size += nl->size + JMSZ;
  315.     l->flink = nl->flink;
  316.     l->flink->blink = l;
  317.     free_blocks--;
  318.     nl->nextfree->prevfree = nl->prevfree;
  319.     nl->prevfree->nextfree = nl->nextfree;
  320.   }
  321.   start = l;
  322. }
  323.  
  324. void *realloc(loc, size)
  325. char *loc;
  326. int size;
  327. {
  328.   Jmalloc l;
  329.   Jmalloc l2, nl;
  330.   char *loc2;
  331.   int i;
  332.   Jmalloc newl;
  333.  
  334.  
  335.   do_init();
  336.  
  337.   if (size <= 0) {
  338.     fprintf(stderr, "Error: Malloc(%d) called\n", size);
  339.     /* Dump core */
  340.     dump_core();
  341.   }
  342.     
  343.   if (size % PTSZ != 0) size += PTSZ - (size % PTSZ);
  344.  
  345.   l = jmal(loc); 
  346.  
  347.   if (cksum(l) != l->cs) {
  348.     fprintf(stderr, "Error on realloc: memory chunk violated: 0x%x\n", loc);
  349.     dump_core();
  350.   } else if (cksum(l) != *(l->cs2)) {
  351.     fprintf(stderr, "Error on realloc: memory chunk violated: 0x%x\n", loc);
  352.     dump_core();
  353.   }
  354.  
  355.   if (size < l->size) {
  356.     if (l->size - size < JMSZ + 4) return loc;
  357.     newl = (Jmalloc) (loc + size + PTSZ);
  358.     newl->flink = l->flink;
  359.     newl->blink = l;
  360.     newl->flink->blink = newl;
  361.     newl->blink->flink = newl;
  362.     newl->nextfree = start->nextfree;
  363.     newl->prevfree = start;
  364.     newl->nextfree->prevfree = newl;
  365.     newl->prevfree->nextfree = newl;
  366.     newl->size = l->size - size - JMSZ;
  367.     newl->cs = cksum(newl);
  368.     newl->cs2 = (int *) (jloc(newl) + newl->size);
  369.     *(newl->cs2) = cksum(newl);
  370.     used_mem += size - l->size;
  371.     free_mem += newl->size;
  372.     free_blocks++;
  373.     l->size = size;
  374.     l->cs2 = ((int *) (jloc(l) + l->size));
  375.     *(l->cs2) = cksum(l);
  376.     start = newl;
  377.     return loc;
  378.   }
  379.  
  380.  
  381.   nl = l->flink;
  382.  
  383.   if (isfree(nl) && (jloc(l)+l->size + PTSZ == (char *) nl) &&
  384.       l->size + JMSZ + nl->size >= size) {
  385.     start = nl;
  386.     i = size - l->size - JMSZ;
  387.     if (i < 0) i = 4;
  388.     loc2 = malloc(i);
  389.     l2 = jmal(loc2);
  390.     if (l2 != nl) {
  391.       fprintf(stderr, "Realloc internal error: l2 != nl\n");
  392.       dump_core();
  393.     }
  394.  
  395.     nl->flink->blink = nl->blink;
  396.     nl->blink->flink = nl->flink;
  397.     free_mem -= nl->size;
  398.     used_mem += nl->size + JMSZ;
  399.     free_blocks--;
  400.     l->size += nl->size + JMSZ;
  401.     l->cs2 = ((int *) (jloc(l) + l->size));
  402.     *(l->cs2) = cksum(l);
  403.     return loc;
  404.   } else {
  405.     loc2 = malloc(size);
  406.     for (i = 0; i < l->size; i++) loc2[i] = loc[i];
  407.     free(loc);
  408.     return loc2;
  409.   }
  410. }
  411.  
  412. char *calloc(nelem, elsize)
  413. int nelem, elsize;
  414. {
  415.   int *iptr;
  416.   char *ptr;
  417.   int sz;
  418.   int i;
  419.  
  420.   sz = nelem*elsize;
  421.   ptr = malloc(sz);
  422.   iptr = (int *) ptr;
  423.   
  424.   for (i = 0; i < sz/sizeof(int); i++) iptr[i] = 0;
  425.   for (i = i * sizeof(int); i < sz; i++) ptr[i] = 0;
  426.   return ptr;
  427. }
  428.  
  429. int mallopt(cmd, value)
  430. int cmd, value;
  431. {
  432.   fprintf(stderr, "Mallopt is not defined...\n");
  433.   exit(1);
  434. }
  435.  
  436.  
  437. jmalloc_usage()
  438. {
  439.   fprintf(stderr, "Jmalloc: %d %s %d block%s. %d %s %d block%s\n",
  440.                     used_mem, "bytes used in", used_blocks, 
  441.                     (used_blocks == 1) ? "" : "s", 
  442.                     free_mem, "bytes free in", free_blocks,
  443.                     (free_blocks == 1) ? "" : "s");
  444. }
  445.