home *** CD-ROM | disk | FTP | other *** search
/ HAM Radio 3 / hamradioversion3.0examsandprograms1992.iso / misc / 9q920411 / alloc.c < prev    next >
C/C++ Source or Header  |  1992-04-10  |  10KB  |  407 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. /* Allocate block of 'nb' bytes */
  76. void *
  77. malloc(nb)
  78. unsigned nb;
  79. {
  80.     register HEADER HUGE *p, HUGE *q;
  81.     register unsigned nu;
  82.     int i;
  83.  
  84.     if(!istate())
  85.         Intalloc++;
  86.     if(nb == 0)
  87.         return NULL;
  88.  
  89.     /* Record the size of this request */
  90.     if((i = log2(nb)) >= 0)
  91.         Sizes[i]++;
  92.     
  93.     /* Round up to full block, then add one for header */
  94.     nu = ((nb + ABLKSIZE - 1) / ABLKSIZE) + 1;
  95.     if((q = Allocp) == NULLHDR){
  96.         Base.s.ptr = Allocp = q = &Base;
  97.         Base.s.size = 1;
  98.     }
  99.     for(p = q->s.ptr; ; q = p, p = p->s.ptr){
  100.         if(p->s.size >= nu){
  101.             /* This chunk is at least as large as we need */
  102.             if(p->s.size <= nu + 1){
  103.                 /* This is either a perfect fit (size == nu)
  104.                  * or the free chunk is just one unit larger.
  105.                  * In either case, alloc the whole thing,
  106.                  * because there's no point in keeping a free
  107.                  * block only large enough to hold the header.
  108.                  */
  109.                 q->s.ptr = p->s.ptr;
  110.             } else {
  111.                 /* Carve out piece from end of entry */
  112.                 p->s.size -= nu;
  113.                 p += p->s.size;
  114.                 p->s.size = nu;
  115.             }
  116. #ifdef    circular
  117.             Allocp = q;
  118. #endif
  119.             p->s.ptr = p;    /* for auditing */
  120.             Allocs++;
  121.             Availmem -= p->s.size;
  122.             p++;
  123.             break;
  124.         }
  125.         if(p == Allocp && ((p = morecore(nu)) == NULLHDR)){
  126.             Memfail++;
  127.             break;
  128.         }
  129.     }
  130. #ifdef    LARGEDATA
  131.     /* On the brain-damaged Intel CPUs in "large data" model,
  132.      * make sure the pointer's offset field isn't null
  133.      * (unless the entire pointer is null).
  134.      * The Turbo C compiler and certain
  135.      * library functions like strrchr() assume this.
  136.      */
  137.     if(FP_OFF(p) == 0 && FP_SEG(p) != 0){
  138.         /* Return denormalized but equivalent pointer */
  139.         return (void *)MK_FP(FP_SEG(p)-1,16);
  140.     }
  141. #endif
  142.     return (void *)p;
  143. }
  144. /* Get more memory from the system and put it on the heap */
  145. static HEADER HUGE *
  146. morecore(nu)
  147. unsigned nu;
  148. {
  149.     register char HUGE *cp;
  150.     register HEADER HUGE *up;
  151.  
  152.     Morecores++;
  153.     if ((int)(cp = (char HUGE *)sbrk(nu * ABLKSIZE)) == -1)
  154.         return NULLHDR;
  155.     up = (HEADER *)cp;
  156.     up->s.size = nu;
  157.     up->s.ptr = up;    /* satisfy audit */
  158.     free((void *)(up + 1));
  159.     Heapsize += nu*ABLKSIZE;
  160.     Frees--;    /* Nullify increment inside free() */
  161.     return Allocp;
  162. }
  163.  
  164. /* Put memory block back on heap */
  165. void
  166. free(blk)
  167. void *blk;
  168. {
  169.     register HEADER HUGE *p, HUGE *q;
  170.     unsigned short HUGE *ptr;
  171.  
  172.     if(!istate())
  173.         Intfree++;
  174.     if(blk == NULL)
  175.         return;        /* Required by ANSI */
  176.     p = (HEADER HUGE *)blk - 1;
  177.     /* Audit check */
  178.     if(p->s.ptr != p){
  179.         ptr = (unsigned short *)&blk;
  180.         printf("free: WARNING! invalid pointer (0x%lx) proc %s\n",
  181.          ptol(blk),Curproc->name);
  182.         stktrace();
  183.         Invalid++;
  184.         log(-1,"free: WARNING! invalid pointer (0x%lx) pc = 0x%x %x proc %s\n",
  185.          ptol(blk),ptr[-1],ptr[-2],Curproc->name);
  186.         return;
  187.     }
  188.     Availmem += p->s.size;
  189.     /* Search the free list looking for the right place to insert */
  190.     for(q = Allocp; !(p > q && p < q->s.ptr); q = q->s.ptr){
  191.         /* Highest address on circular list? */
  192.         if(q >= q->s.ptr && (p > q || p < q->s.ptr))
  193.             break;
  194.     }
  195.     if(p + p->s.size == q->s.ptr){
  196.         /* Combine with front of this entry */
  197.         p->s.size += q->s.ptr->s.size;
  198.         p->s.ptr = q->s.ptr->s.ptr;
  199.     } else {
  200.         /* Link to front of this entry */
  201.         p->s.ptr = q->s.ptr;
  202.     }
  203.     if(q + q->s.size == p){
  204.         /* Combine with end of this entry */
  205.         q->s.size += p->s.size;
  206.         q->s.ptr = p->s.ptr;
  207.     } else {
  208.         /* Link to end of this entry */
  209.         q->s.ptr = p;
  210.     }
  211. #ifdef    circular
  212.     Allocp = q;
  213. #endif
  214.     Frees++;
  215.     if(Memwait != 0)
  216.         psignal(&Memwait,0);
  217. }
  218.  
  219. #ifdef    notdef    /* Not presently used */
  220. /* Move existing block to new area */
  221. void *
  222. realloc(area,size)
  223. void *area;
  224. unsigned size;
  225. {
  226.     unsigned osize;
  227.     HEADER HUGE *hp;
  228.     char HUGE *cp;
  229.  
  230.     hp = ((HEADER *)area) - 1;
  231.     osize = (hp->s.size -1) * ABLKSIZE;
  232.  
  233.     free(area);
  234.     if((cp = malloc(size)) != NULL && cp != area)
  235.         memcpy((char *)cp,(char *)area,size>osize? osize : size);
  236.     return cp;
  237. }
  238. #endif
  239. /* Allocate block of cleared memory */
  240. void *
  241. calloc(nelem,size)
  242. unsigned nelem;    /* Number of elements */
  243. unsigned size;    /* Size of each element */
  244. {
  245.     register unsigned i;
  246.     register char *cp;
  247.  
  248.     i = nelem * size;
  249.     if((cp = malloc(i)) != NULL)
  250.         memset(cp,0,i);
  251.     return cp;
  252. }
  253. /* Version of malloc() that waits if necessary for memory to become available */
  254. void *
  255. mallocw(nb)
  256. unsigned nb;
  257. {
  258.     register void *p;
  259.  
  260.     while((p = malloc(nb)) == NULL){
  261.         Memwait++;
  262.         pwait(&Memwait);
  263.         Memwait--;
  264.     }
  265.     return p;
  266. }
  267. /* Version of calloc that waits if necessary for memory to become available */
  268. void *
  269. callocw(nelem,size)
  270. unsigned nelem;    /* Number of elements */
  271. unsigned size;    /* Size of each element */
  272. {
  273.     register unsigned i;
  274.     register char *cp;
  275.  
  276.     i = nelem * size;
  277.     cp = mallocw(i);
  278.     memset(cp,0,i);
  279.     return cp;
  280. }
  281. /* Return available memory on our heap plus available system memory */
  282. unsigned long
  283. availmem()
  284. {
  285.     return Availmem * ABLKSIZE + coreleft();
  286. }
  287.  
  288. /* Print heap stats */
  289. static int
  290. dostat(argc,argv,envp)
  291. int argc;
  292. char *argv[];
  293. void *envp;
  294. {
  295.     tprintf("heap size %lu avail %lu (%lu%%) morecores %lu coreleft %lu\n",
  296.      Heapsize,Availmem * ABLKSIZE,100L*Availmem*ABLKSIZE/Heapsize,
  297.      Morecores,coreleft());
  298.     tprintf("allocs %lu frees %lu (diff %lu) alloc fails %lu invalid frees %lu\n",
  299.         Allocs,Frees,Allocs-Frees,Memfail,Invalid);
  300.     tprintf("interrupts-off calls to malloc %lu free %lu\n",Intalloc,Intfree);
  301.     tprintf("garbage collections yellow %lu red %lu\n",Yellows,Reds);
  302.     iqstat();
  303.     return 0;
  304. }
  305.  
  306. /* Print heap free list */
  307. static int
  308. dofreelist(argc,argv,envp)
  309. int argc;
  310. char *argv[];
  311. void *envp;
  312. {
  313.     HEADER HUGE *p;
  314.     int i = 0;
  315.  
  316.     for(p = Base.s.ptr;p != &Base;p = p->s.ptr){
  317.         tprintf("%5lx %6lu",ptol((void *)p),p->s.size * ABLKSIZE);
  318.         if(++i == 4){
  319.             i = 0;
  320.             if(tprintf("\n") == EOF)
  321.                 return 0;
  322.         } else
  323.             tprintf(" | ");
  324.     }
  325.     if(i != 0)
  326.         tprintf("\n");
  327.     return 0;
  328. }
  329. static int
  330. dosizes(argc,argv,p)
  331. int argc;
  332. char *argv[];
  333. void *p;
  334. {
  335.     int i;
  336.  
  337.     for(i=0;i<16;i += 4){
  338.         tprintf("N>=%5u:%7ld| N>=%5u:%7ld| N>=%5u:%7ld| N>=%5u:%7ld\n",
  339.          1<<i,Sizes[i],    2<<i,Sizes[i+1],
  340.          4<<i,Sizes[i+2],8<<i,Sizes[i+3]);
  341.     }
  342.     return 0;
  343. }
  344. int
  345. domem(argc,argv,p)
  346. int argc;
  347. char *argv[];
  348. void *p;
  349. {
  350.     return subcmd(Memcmds,argc,argv,p);
  351. }
  352.  
  353. static int
  354. donibufs(argc,argv,p)
  355. int argc;
  356. char *argv[];
  357. void *p;
  358. {
  359.     return setint(&Nibufs,"Interrupt pool buffers",argc,argv);
  360. }
  361. static int
  362. doibufsize(argc,argv,p)
  363. int argc;
  364. char *argv[];
  365. void *p;
  366. {
  367.     return setuns(&Ibufsize,"Interrupt buffer size",argc,argv);
  368. }
  369.  
  370. static int
  371. dothresh(argc,argv,p)
  372. int argc;
  373. char *argv[];
  374. void *p;
  375. {
  376.     return setlong(&Memthresh,"Free memory threshold (bytes)",argc,argv);
  377. }
  378.  
  379. /* Background memory compactor, used when memory runs low */
  380. void
  381. gcollect(i,v1,v2)
  382. int i;    /* Args not used */
  383. void *v1;
  384. void *v2;
  385. {
  386.     void (**fp)();
  387.     int red;
  388.  
  389.     for(;;){
  390.         pause(1000L);    /* Run every second */
  391.         /* If memory is low, collect some garbage. If memory is VERY
  392.          * low, invoke the garbage collection routines in "red" mode.
  393.          */
  394.         if(availmem() < Memthresh){
  395.             if(availmem() < Memthresh/2){
  396.                 red = 1;
  397.                 Reds++;
  398.             } else {
  399.                 red = 0;
  400.                 Yellows++;
  401.             }
  402.             for(fp = Gcollect;*fp != NULL;fp++)
  403.                 (**fp)(red);
  404.         }
  405.     }
  406. }
  407.