home *** CD-ROM | disk | FTP | other *** search
/ Media Share 9 / MEDIASHARE_09.ISO / hamradio / s920603.zip / ALLOC.C next >
C/C++ Source or Header  |  1992-05-21  |  12KB  |  500 lines
  1. /* memory allocation routines
  2.  * Copyright 1991 Phil Karn, KA9Q
  3.  *
  4.  * Adapted from alloc routine in K&R; memory statistics and interrupt
  5.  * protection added for use with net package. Must be used in place of
  6.  * standard Turbo-C library routines because the latter check for stack/heap
  7.  * collisions. This causes erroneous failures because process stacks are
  8.  * allocated off the heap.
  9.  */
  10.  
  11. #include <stdio.h>
  12. #include <dos.h>
  13. #include <alloc.h>
  14. #include "global.h"
  15. #include "mbuf.h"
  16. #include "proc.h"
  17. #include "cmdparse.h"
  18.  
  19. static unsigned long Memfail;    /* Count of allocation failures */
  20. static unsigned long Allocs;    /* Total allocations */
  21. static unsigned long Frees;    /* Total frees */
  22. static unsigned long Invalid;    /* Total calls to free with garbage arg */
  23. static unsigned long Intalloc;    /* Calls to malloc with ints disabled */
  24. static unsigned long Intfree;    /* Calls to free with ints disabled */
  25. static int Memwait;        /* Number of tasks waiting for memory */
  26. static unsigned long Yellows;    /* Yellow alert garbage collections */
  27. static unsigned long Reds;    /* Red alert garbage collections */
  28. unsigned long Availmem;        /* Heap memory, ABLKSIZE units */
  29. static unsigned long Morecores;
  30.  
  31. static unsigned long Sizes[16];
  32.  
  33. static int dostat __ARGS((int argc,char *argv[],void *p));
  34. static int dofreelist __ARGS((int argc,char *argv[],void *p));
  35. static int doibufsize __ARGS((int argc,char *argv[],void *p));
  36. static int donibufs __ARGS((int argc,char *argv[],void *p));
  37. static int dothresh __ARGS((int argc,char *argv[],void *p));
  38. static int dosizes __ARGS((int argc,char *argv[],void *p));
  39.  
  40. struct cmds Memcmds[] = {
  41.     "freelist",    dofreelist,    0, 0, NULLCHAR,
  42.     "ibufsize",    doibufsize,    0, 0, NULLCHAR,
  43.     "nibufs",    donibufs,    0, 0, NULLCHAR,
  44.     "sizes",    dosizes,    0, 0, NULLCHAR,
  45.     "status",    dostat,        0, 0, NULLCHAR,
  46.     "thresh",    dothresh,    0, 0, NULLCHAR,
  47.     NULLCHAR,
  48. };
  49.  
  50. #ifdef    LARGEDATA
  51. #define    HUGE    huge
  52. #else
  53. #define    HUGE
  54. #endif
  55.  
  56. union header {
  57.     struct {
  58.         union header HUGE *ptr;
  59.         unsigned long size;
  60.     } s;
  61.     long l[2];
  62. };
  63.  
  64. typedef union header HEADER;
  65. #define    NULLHDR    (HEADER HUGE *)NULL
  66.  
  67. #define    ABLKSIZE    (sizeof (HEADER))
  68.  
  69. static HEADER HUGE *morecore __ARGS((unsigned nu));
  70.  
  71. static HEADER Base;
  72. static HEADER HUGE *Allocp = NULLHDR;
  73. static unsigned long Heapsize;
  74.  
  75. /* Memory blocks obtained from MS-DOS by allocmem() call */
  76. struct sysblock {
  77.     unsigned seg;
  78.     unsigned npar;
  79. };
  80. #define    NSYSBLOCK    5
  81. struct sysblock Sysblock[NSYSBLOCK];
  82.  
  83. /* Allocate block of 'nb' bytes */
  84. void *
  85. malloc(nb)
  86. unsigned nb;
  87. {
  88.     register HEADER HUGE *p, HUGE *q;
  89.     register unsigned nu;
  90.     int i;
  91.  
  92.     if(!istate())
  93.         Intalloc++;
  94.     if(nb == 0)
  95.         return NULL;
  96.  
  97.     /* Record the size of this request */
  98.     if((i = log2(nb)) >= 0)
  99.         Sizes[i]++;
  100.     
  101.     /* Round up to full block, then add one for header */
  102.     nu = ((nb + ABLKSIZE - 1) / ABLKSIZE) + 1;
  103.     if((q = Allocp) == NULLHDR){
  104.         Base.s.ptr = Allocp = q = &Base;
  105.         Base.s.size = 1;
  106.     }
  107.     for(p = q->s.ptr; ; q = p, p = p->s.ptr){
  108.         if(p->s.size >= nu){
  109.             /* This chunk is at least as large as we need */
  110.             if(p->s.size <= nu + 1){
  111.                 /* This is either a perfect fit (size == nu)
  112.                  * or the free chunk is just one unit larger.
  113.                  * In either case, alloc the whole thing,
  114.                  * because there's no point in keeping a free
  115.                  * block only large enough to hold the header.
  116.                  */
  117.                 q->s.ptr = p->s.ptr;
  118.             } else {
  119.                 /* Carve out piece from end of entry */
  120.                 p->s.size -= nu;
  121.                 p += p->s.size;
  122.                 p->s.size = nu;
  123.             }
  124. #ifdef    circular
  125.             Allocp = q;
  126. #endif
  127.             p->s.ptr = p;    /* for auditing */
  128.             Allocs++;
  129.             Availmem -= p->s.size;
  130.             p++;
  131.             break;
  132.         }
  133.         if(p == Allocp && ((p = morecore(nu)) == NULLHDR)){
  134.             Memfail++;
  135.             break;
  136.         }
  137.     }
  138. #ifdef    LARGEDATA
  139.     /* On the brain-damaged Intel CPUs in "large data" model,
  140.      * make sure the pointer's offset field isn't null
  141.      * (unless the entire pointer is null).
  142.      * The Turbo C compiler and certain
  143.      * library functions like strrchr() assume this.
  144.      */
  145.     if(FP_OFF(p) == 0 && FP_SEG(p) != 0){
  146.         /* Return denormalized but equivalent pointer */
  147.         return (void *)MK_FP(FP_SEG(p)-1,16);
  148.     }
  149. #endif
  150.     return (void *)p;
  151. }
  152. /* Get more memory from the system and put it on the heap */
  153. static HEADER HUGE *
  154. morecore(nu)
  155. unsigned nu;
  156. {
  157.     char HUGE *cp;
  158.     HEADER HUGE *up;
  159.     unsigned size;
  160.     unsigned segp;
  161.     unsigned npar;
  162.     struct sysblock *sp;
  163.     int i;
  164.  
  165.     Morecores++;
  166.     size = nu * ABLKSIZE;
  167.     /* First try to expand our main memory block */
  168.     if ((int)(cp = (char HUGE *)sbrk(size)) != -1){
  169.         up = (HEADER *)cp;
  170.         up->s.size = nu;
  171.         up->s.ptr = up;    /* satisfy audit */
  172.         free((void *)(up + 1));
  173.         Heapsize += size;
  174.         Frees--;    /* Nullify increment inside free() */
  175.         return Allocp;
  176.     }
  177.     /* That failed; the main memory block must have grown into another
  178.      * allocated block, or something else (e.g., the increase handles
  179.      * call in ioinit()) must have allocated memory just beyond it.
  180.      * Allocate or extend an additional memory block.
  181.      */
  182.     npar = (size+16)/16;    /* Convert size from bytes to paragraphs */
  183.     cp = NULL;
  184.     for(sp=Sysblock,i=0;i < NSYSBLOCK;i++,sp++){
  185.         if(sp->npar != 0){
  186.             /* Try to expand this block */
  187.             if(setblock(sp->seg,sp->npar + npar) != -1){
  188.                 /* Failed (-1 == SUCCESS; strange!) */
  189.                 continue;
  190.             }
  191.             /* Block expansion succeeded */
  192.             cp = MK_FP(sp->seg + sp->npar,0);
  193.             sp->npar += npar;
  194.         } else {
  195.             /* Allocate new block */
  196.             if(allocmem(npar,&segp) != -1){
  197.                 return NULL;    /* Complete failure */
  198.             }
  199.             /* -1 indicates SUCCESS (strange) */
  200.             sp->seg = segp;
  201.             sp->npar = npar;
  202.             cp = MK_FP(segp,0);
  203.         }
  204.         break;
  205.     }
  206.     if(cp != (char HUGE *)NULL){
  207.         /* Expand or create succeeded, add to heap */
  208.         up = (HEADER *)cp;
  209.         up->s.size = (npar*16)/ABLKSIZE;
  210.         up->s.ptr = up;    /* satisfy audit */
  211.         free((void *)(up + 1));
  212.         Heapsize += npar*16;
  213.         Frees--;    /* Nullify increment inside free() */
  214.         return Allocp;
  215.     }
  216.     return NULL;
  217. }
  218.  
  219. /* Put memory block back on heap */
  220. void
  221. free(blk)
  222. void *blk;
  223. {
  224.     register HEADER HUGE *p, HUGE *q;
  225.     unsigned short HUGE *ptr;
  226.  
  227.     if(!istate())
  228.         Intfree++;
  229.     if(blk == NULL)
  230.         return;        /* Required by ANSI */
  231.     p = (HEADER HUGE *)blk - 1;
  232.     /* Audit check */
  233.     if(p->s.ptr != p){
  234.         ptr = (unsigned short *)&blk;
  235.         printf("free: WARNING! invalid pointer (0x%lx) proc %s\n",
  236.          ptol(blk),Curproc->name);
  237.         stktrace();
  238.         Invalid++;
  239.         log(-1,"free: WARNING! invalid pointer (0x%lx) pc = 0x%x %x proc %s\n",
  240.          ptol(blk),ptr[-1],ptr[-2],Curproc->name);
  241.         return;
  242.     }
  243.     Availmem += p->s.size;
  244.     /* Search the free list looking for the right place to insert */
  245.     for(q = Allocp; !(p > q && p < q->s.ptr); q = q->s.ptr){
  246.         /* Highest address on circular list? */
  247.         if(q >= q->s.ptr && (p > q || p < q->s.ptr))
  248.             break;
  249.     }
  250.     if(p + p->s.size == q->s.ptr){
  251.         /* Combine with front of this entry */
  252.         p->s.size += q->s.ptr->s.size;
  253.         p->s.ptr = q->s.ptr->s.ptr;
  254.     } else {
  255.         /* Link to front of this entry */
  256.         p->s.ptr = q->s.ptr;
  257.     }
  258.     if(q + q->s.size == p){
  259.         /* Combine with end of this entry */
  260.         q->s.size += p->s.size;
  261.         q->s.ptr = p->s.ptr;
  262.     } else {
  263.         /* Link to end of this entry */
  264.         q->s.ptr = p;
  265.     }
  266. #ifdef    circular
  267.     Allocp = q;
  268. #endif
  269.     Frees++;
  270.     if(Memwait != 0)
  271.         psignal(&Memwait,0);
  272. }
  273.  
  274. #ifdef    notdef    /* Not presently used */
  275. /* Move existing block to new area */
  276. void *
  277. realloc(area,size)
  278. void *area;
  279. unsigned size;
  280. {
  281.     unsigned osize;
  282.     HEADER HUGE *hp;
  283.     char HUGE *cp;
  284.  
  285.     hp = ((HEADER *)area) - 1;
  286.     osize = (hp->s.size -1) * ABLKSIZE;
  287.  
  288.     free(area);
  289.     if((cp = malloc(size)) != NULL && cp != area)
  290.         memcpy((char *)cp,(char *)area,size>osize? osize : size);
  291.     return cp;
  292. }
  293. #endif
  294. /* Allocate block of cleared memory */
  295. void *
  296. calloc(nelem,size)
  297. unsigned nelem;    /* Number of elements */
  298. unsigned size;    /* Size of each element */
  299. {
  300.     register unsigned i;
  301.     register char *cp;
  302.  
  303.     i = nelem * size;
  304.     if((cp = malloc(i)) != NULL)
  305.         memset(cp,0,i);
  306.     return cp;
  307. }
  308. /* Version of malloc() that waits if necessary for memory to become available */
  309. void *
  310. mallocw(nb)
  311. unsigned nb;
  312. {
  313.     register void *p;
  314.  
  315.     while((p = malloc(nb)) == NULL){
  316.         Memwait++;
  317.         pwait(&Memwait);
  318.         Memwait--;
  319.     }
  320.     return p;
  321. }
  322. /* Version of calloc that waits if necessary for memory to become available */
  323. void *
  324. callocw(nelem,size)
  325. unsigned nelem;    /* Number of elements */
  326. unsigned size;    /* Size of each element */
  327. {
  328.     register unsigned i;
  329.     register char *cp;
  330.  
  331.     i = nelem * size;
  332.     cp = mallocw(i);
  333.     memset(cp,0,i);
  334.     return cp;
  335. }
  336. /* Return 0 if at least Memthresh memory is available. Return 1 if
  337.  * less than Memthresh but more than Memthresh/2 is available; i.e.,
  338.  * if a yellow garbage collection should be performed. Return 2 if
  339.  * less than Memthresh/2 is available, i.e., a red collection should
  340.  * be performed.
  341.  */
  342. int
  343. availmem()
  344. {
  345.     void *p;
  346.  
  347.     if(Availmem*ABLKSIZE >= Memthresh)
  348.         return 0;    /* We're clearly OK */
  349.  
  350.     /* There's not enough on the heap; try calling malloc to see if
  351.      * it can get more from the system
  352.      */
  353.     if((p = malloc(Memthresh)) != NULL){
  354.         free(p);
  355.         return 0;    /* Okay */
  356.     }
  357.     if((p = malloc(Memthresh/2)) != NULL){
  358.         free(p);
  359.         return 1;    /* Yellow alert */
  360.     }
  361.     return 2;        /* Red alert */
  362. }
  363.  
  364. /* Print heap stats */
  365. static int
  366. dostat(argc,argv,envp)
  367. int argc;
  368. char *argv[];
  369. void *envp;
  370. {
  371.     struct sysblock *sp;
  372.     int i;
  373.  
  374.     printf("heap size %lu avail %lu (%lu%%) morecores %lu\n",
  375.      Heapsize,Availmem * ABLKSIZE,100L*Availmem*ABLKSIZE/Heapsize,
  376.      Morecores);
  377.     if(Sysblock[0].npar != 0){
  378.         printf("Extra blocks:");
  379.         for(i=0,sp=Sysblock;i< NSYSBLOCK;i++,sp++){
  380.             if(sp->npar == 0)
  381.                 break;
  382.             printf(" (%x0-%x0)",sp->seg,sp->seg+sp->npar);
  383.         }
  384.         printf("\n");
  385.     }
  386.     printf("allocs %lu frees %lu (diff %lu) alloc fails %lu invalid frees %lu\n",
  387.         Allocs,Frees,Allocs-Frees,Memfail,Invalid);
  388.     printf("pushdown calls %lu pushdown calls to malloc %lu\n",
  389.         Pushdowns,Pushalloc);
  390.     printf("interrupts-off calls to malloc %lu free %lu\n",Intalloc,Intfree);
  391.     printf("garbage collections yellow %lu red %lu\n",Yellows,Reds);
  392.     iqstat();
  393.     return 0;
  394. }
  395.  
  396. /* Print heap free list */
  397. static int
  398. dofreelist(argc,argv,envp)
  399. int argc;
  400. char *argv[];
  401. void *envp;
  402. {
  403.     HEADER HUGE *p;
  404.     int i = 0;
  405.  
  406.     for(p = Base.s.ptr;p != (HEADER HUGE *)&Base;p = p->s.ptr){
  407.         printf("%5lx %6lu",ptol((void *)p),p->s.size * ABLKSIZE);
  408.         if(++i == 4){
  409.             i = 0;
  410.             if(printf("\n") == EOF)
  411.                 return 0;
  412.         } else
  413.             printf(" | ");
  414.     }
  415.     if(i != 0)
  416.         printf("\n");
  417.     return 0;
  418. }
  419. static int
  420. dosizes(argc,argv,p)
  421. int argc;
  422. char *argv[];
  423. void *p;
  424. {
  425.     int i;
  426.  
  427.     for(i=0;i<16;i += 4){
  428.         printf("N>=%5u:%7ld| N>=%5u:%7ld| N>=%5u:%7ld| N>=%5u:%7ld\n",
  429.          1<<i,Sizes[i],    2<<i,Sizes[i+1],
  430.          4<<i,Sizes[i+2],8<<i,Sizes[i+3]);
  431.     }
  432.     return 0;
  433. }
  434. int
  435. domem(argc,argv,p)
  436. int argc;
  437. char *argv[];
  438. void *p;
  439. {
  440.     return subcmd(Memcmds,argc,argv,p);
  441. }
  442.  
  443. static int
  444. donibufs(argc,argv,p)
  445. int argc;
  446. char *argv[];
  447. void *p;
  448. {
  449.     return setint(&Nibufs,"Interrupt pool buffers",argc,argv);
  450. }
  451. static int
  452. doibufsize(argc,argv,p)
  453. int argc;
  454. char *argv[];
  455. void *p;
  456. {
  457.     return setuns(&Ibufsize,"Interrupt buffer size",argc,argv);
  458. }
  459.  
  460. static int
  461. dothresh(argc,argv,p)
  462. int argc;
  463. char *argv[];
  464. void *p;
  465. {
  466.     return setlong(&Memthresh,"Free memory threshold (bytes)",argc,argv);
  467. }
  468.  
  469. /* Background memory compactor, used when memory runs low */
  470. void
  471. gcollect(i,v1,v2)
  472. int i;    /* Args not used */
  473. void *v1;
  474. void *v2;
  475. {
  476.     void (**fp)();
  477.     int red;
  478.  
  479.     for(;;){
  480.         pause(1000L);    /* Run every second */
  481.         /* If memory is low, collect some garbage. If memory is VERY
  482.          * low, invoke the garbage collection routines in "red" mode.
  483.          */
  484.         switch(availmem()){
  485.         case 0:
  486.             continue;    /* All is well */
  487.         case 1:
  488.             red = 0;
  489.             Yellows++;
  490.             break;
  491.         case 2:
  492.             red = 1;
  493.             Reds++;
  494.             break;
  495.         }
  496.         for(fp = Gcollect;*fp != NULL;fp++)
  497.             (**fp)(red);
  498.     }
  499. }
  500.