home *** CD-ROM | disk | FTP | other *** search
/ Atari FTP / ATARI_FTP_0693.zip / ATARI_FTP_0693 / Mint / mint104s.zoo / mint.src / nalloc2.c < prev    next >
C/C++ Source or Header  |  1993-03-08  |  6KB  |  259 lines
  1. /*
  2.  * Copyright 1992 Atari Corporation. All rights reserved.
  3.  */
  4.  
  5. /*
  6.  * General-purpose memory allocator, on the MWC arena model, with
  7.  * this added feature:
  8.  *
  9.  * All blocks are coalesced when they're freed.  If this results in
  10.  * an arena with only one block, and that free, it's returned to the
  11.  * OS.
  12.  *
  13.  * The functions here have the same names and bindings as the MWC
  14.  * memory manager, which is the same as the UNIX names and bindings.
  15.  *
  16.  * MiNT version: used for kmalloc to manage kernel memory in small hunks,
  17.  * rather than using a page at a time.
  18.  */
  19.  
  20. #include "mint.h"
  21.  
  22. #if 0
  23. #define NALLOC_DEBUG(c) TRACE(("nalloc: %c",c));
  24. #else
  25. #define NALLOC_DEBUG(c) /* nothing */
  26. #endif
  27.  
  28. #define NKMAGIC 0x19870425L
  29.  
  30. /*
  31.  * block header: every memory block has one.
  32.  * A block is either allocated or on the free
  33.  * list of the arena.  There is no allocated list: it's not necessary.
  34.  * The next pointer is only valid for free blocks: for allocated blocks
  35.  * maybe it should hold a verification value..?
  36.  *
  37.  * Zero-length blocks are possible and free; they hold space which might 
  38.  * get coalesced usefully later on.
  39.  */
  40.  
  41. struct block {
  42.     struct block *b_next;   /* NULL for last guy; next alloc or next free */
  43.     long b_size;
  44. };
  45.  
  46. /*
  47.  * arena header: every arena has one.  Each arena is always completely
  48.  * filled with blocks; the first starts right after this header.
  49.  */
  50.  
  51. struct arena {
  52.     struct arena *a_next;
  53.     struct block *a_ffirst;
  54.     long a_size;
  55. };
  56.  
  57. /*
  58.  * Arena linked-list pointer, and block size.
  59.  */
  60.  
  61. static struct arena *a_first = (struct arena *)NULL;
  62.  
  63. void
  64. nalloc_arena_add(start,len)
  65. void *start;
  66. long len;
  67. {
  68.     struct arena *a = start;
  69.     struct block *b;
  70.  
  71.     a->a_next = a_first;
  72.     a_first = a;
  73.     a->a_ffirst = b = (struct block *)(a+1);
  74.     a->a_size = len;
  75.     b->b_next = NULL;
  76.     b->b_size = (len - sizeof(*a) - sizeof(*b));
  77. }
  78.     
  79.  
  80. void *
  81. nalloc(size)
  82. long size;
  83. {
  84.     struct arena *a;
  85.     struct block *b, *mb, **q;
  86.     long temp;
  87.  
  88.     NALLOC_DEBUG('A');
  89.  
  90.     /* force even-sized alloc's */
  91.     size = (size+1) & ~1;
  92.  
  93.     for (a = a_first; a; a = a->a_next) {
  94.     for (b = *(q = &a->a_ffirst); b; b = *(q = &b->b_next)) {
  95.         /* if big enough, use it */
  96.         if (b->b_size >= size) {
  97.  
  98.         /* got one */
  99.         mb = b;
  100.  
  101.         /* cut the free block into an allocated part & a free part */
  102.         temp = mb->b_size - size - sizeof(struct block);
  103.         if (temp >= 0) {
  104.             /* large enough to cut */
  105.             NALLOC_DEBUG('c');
  106.             b = (struct block *)(((char *)(b+1)) + size);
  107.             b->b_size = temp;
  108.             b->b_next = mb->b_next;
  109.             *q = b;
  110.             mb->b_size = size;
  111.             mb->b_next = (struct block *)NKMAGIC;
  112.         }
  113.         else {
  114.             /* not big enough to cut: unlink this from free list */
  115.             NALLOC_DEBUG('w');
  116.             *q = mb->b_next;
  117.         }
  118.         return (void *)(mb+1);
  119.         }
  120.     }
  121.     }
  122.  
  123.     /* no block available: get a new arena */
  124.  
  125. #if 1
  126.     return NULL;    /* MiNT: fail. */
  127. #else
  128.     if (!minarena) {
  129.     minarena = Malloc(-1L) / 20;
  130.     if (minarena > MAXARENA) minarena = MAXARENA;
  131.     }
  132.  
  133.     if (size < minarena) {
  134.     NALLOC_DEBUG('m');
  135.     temp = minarena;
  136.     }
  137.     else {
  138.     NALLOC_DEBUG('s');
  139.     temp = size;
  140.     }
  141.  
  142.     a = (struct arena *)Malloc(temp + 
  143.                 sizeof(struct arena) +
  144.                 sizeof(struct block));
  145.  
  146.     /* if Malloc failed return failure */
  147.     if (a == 0) {
  148.         NALLOC_DEBUG('x');
  149.         return 0;
  150.     }
  151.  
  152.     a->a_size = temp + sizeof(struct block);
  153.     a->a_next = a_first;
  154.     a_first = a;
  155.     mb = (struct block *)(a+1);
  156.     mb->b_next = NULL;
  157.     mb->b_size = size;
  158.  
  159.     if (temp > (size + sizeof(struct block))) {
  160.         NALLOC_DEBUG('c');
  161.     b = a->a_ffirst = ((char *)(mb+1)) + size;
  162.     b->b_next = NULL;
  163.     b->b_size = temp - size - sizeof(struct block);
  164.     }
  165.     else {
  166.     a->a_ffirst = NULL;
  167.     }
  168.     return (void *)(++mb);
  169. #endif
  170. }
  171.  
  172. void
  173. nfree(start)
  174. void *start;
  175. {
  176.     struct arena *a, **qa;
  177.     struct block *b;
  178.     struct block *pb;
  179.     struct block *fb = (struct block *)start;
  180.  
  181.     NALLOC_DEBUG('F');
  182.     if (fb->b_next != (struct block *)NKMAGIC) {
  183.     FATAL("nfree: block %lx not allocated by nalloc!",fb);
  184.     }
  185.  
  186.     /* set fb (and b) to header start */
  187.     b = --fb;
  188.  
  189.     /* the arena this block lives in */
  190.     for (a = *(qa = &a_first); a; a = *(qa = &a->a_next)) {
  191.     if ((unsigned long)b > (unsigned long)a &&
  192.         (unsigned long)b < (((unsigned long)a) + a->a_size)) goto found;
  193.     }
  194.     FATAL("nfree: block %lx not in any arena!",fb);
  195.  
  196. found:
  197.     /* Found it! */
  198.     /* a is this block's arena */
  199.  
  200.     /* set pb to the previous free block in this arena, b to next */
  201.     for (pb = NULL, b = a->a_ffirst;
  202.      b && (b < fb);
  203.      pb = b, b = b->b_next) ;
  204.  
  205.     fb->b_next = b;
  206.  
  207.     /* Coalesce backwards: if any prev ... */
  208.     if (pb) {
  209.     /* if it's adjacent ... */
  210.     if ((((unsigned long)(pb+1)) + pb->b_size) == (unsigned long)fb) {
  211.         NALLOC_DEBUG('b');
  212.         pb->b_size += sizeof(struct block) + fb->b_size;
  213.         fb = pb;
  214.     }
  215.     else {
  216.         /* ... else not adjacent, but there is a prev free block */
  217.         /* so set its next ptr to fb */
  218.         pb->b_next = fb;
  219.     }
  220.     }
  221.     else {
  222.     /* ... else no prev free block: set arena's free list ptr to fb */
  223.     a->a_ffirst = fb;
  224.     }
  225.  
  226.     /* Coalesce forwards: b holds start of free block AFTER fb, if any */
  227.     if (b && (((unsigned long)(fb+1)) + fb->b_size) == (unsigned long)b) {
  228.     NALLOC_DEBUG('f');
  229.     fb->b_size += sizeof(struct block) + b->b_size;
  230.     fb->b_next = b->b_next;
  231.     }
  232.  
  233. #if 0
  234.     /* if, after coalescing, this arena is entirely free, Mfree it! */
  235.     if (a->a_ffirst == a+1 && 
  236.         (a->a_ffirst->b_size + sizeof(struct block)) == a->a_size) {
  237.         NALLOC_DEBUG('!');
  238.         *qa = a->a_next;
  239.         (void)Mfree(a);
  240.     }
  241. #endif
  242.  
  243.     return;
  244. }
  245.  
  246. void
  247. NALLOC_DUMP()
  248. {
  249.     struct arena *a;
  250.     struct block *b;
  251.  
  252.     for (a = a_first; a; a = a->a_next) {
  253.     FORCE("Arena at %lx size %lx: free list:",a,a->a_size);
  254.     for (b = a->a_ffirst; b; b = b->b_next) {
  255.         FORCE("    %8lx size %8lx",b,b->b_size);
  256.     }
  257.     }
  258. }
  259.