malloc.h

   1 constant FREE_MAGIC $FAEE;
   2 constant ALLOC_MAGIC $A10C;
   3
   4 constant FB_MAGIC 0;
   5 constant FB_PREV 1;
   6 constant FB_NEXT 2;
   7 constant FB_SIZE 3;
   8 constant FB__SIZE (4*2);
   9
  10 constant AB_MAGIC 0;
  11 constant AB_SIZE 1;
  12 constant AB__SIZE (2*2);
  13
  14 global mem_top = 0;
  15 global mem_bottom = 0;
  16 global mem_firstfree = 0;
  17
  18 ! Initialise the heap manager, given a value for TOP. It's assumed that the
  19 ! heap will stretch to HIMEM.
  20
  21 [ mem_init bottom top;
  22         mem_bottom = bottom;
  23         mem_top = top;
  24         ! Create a free chunk spanning the length of the block.
  25         mem_firstfree = mem_bottom;
  26         mem_firstfree-->FB_MAGIC = FREE_MAGIC;
  27         mem_firstfree-->FB_PREV = 0;
  28         mem_firstfree-->FB_NEXT = 0;
  29         mem_firstfree-->FB_SIZE = mem_top - mem_bottom;
  30 ];
  31
  32 ! Zero a block of memory.
  33
  34 [ mem_zero ptr size;
  35         while (size)
  36         {
  37                 (ptr++)->0 = 0;
  38                 size--;
  39         }
  40 ];
  41
  42 ! Remove a node from the list.
  43
  44 [ mem_node_remove p;
  45         if (p == mem_firstfree)
  46                 mem_firstfree = p-->FB_NEXT;
  47         if (p-->FB_PREV)
  48                 p-->FB_PREV-->FB_NEXT = p-->FB_NEXT;
  49         if (p-->FB_NEXT)
  50                 p-->FB_NEXT-->FB_PREV = p-->FB_PREV;
  51 ];
  52
  53 ! Try and allocate a block.
  54
  55 [ mem_alloc size p;
  56         ! Add space for the AB_ header.
  57
  58         size = size + AB__SIZE;
  59
  60         ! This block will eventually have to be a FB, once it's freed. So it
  61         ! has to be big enough for the FB_ structure.
  62
  63         if (size < FB__SIZE)
  64                 size = FB__SIZE;
  65
  66         ! Iterate through the list trying to find a free chunk large enough.
  67
  68         p = mem_firstfree;
  69         while ((p ~= 0) && (p-->FB_SIZE < size))
  70         {
  71                 p = p-->FB_NEXT;
  72         }
  73
  74         if (p == 0)
  75         {
  76                 ! No sufficiently large chunk could be found.
  77                 return 0;
  78         }
  79
  80         ! Can the block be shrunk, or is there not enough room?
  81
  82         if ((p-->FB_SIZE - size) < FB__SIZE)
  83         {
  84                 ! Yes; remove the node completely.
  85                 size = p-->FB_SIZE;
  86                 mem_node_remove(p);
  87         }
  88         else
  89         {
  90                 ! No. Instead of removing the node, we shrink it
  91                 p-->FB_SIZE = p-->FB_SIZE - size;
  92                 p = p + p-->FB_SIZE;
  93         }
  94
  95         ! Initialise the allocated node.
  96
  97         mem_zero(p, size);
  98         p-->AB_MAGIC = ALLOC_MAGIC;
  99         p-->AB_SIZE = size;
 100
 101         return p+AB__SIZE;
 102 ];
 103
 104 ! Try to free a block.
 105
 106 [ mem_free p  q;
 107         ! Adjust the pointer to point to the alloc node itself.
 108         p = p - AB__SIZE;
 109
 110 #ifdef DEBUG;
 111         ! Check the magic number.
 112         if (p-->AB_MAGIC ~= ALLOC_MAGIC)
 113         {
 114                 print "Trying to free invalid node ", p, "!^";
 115                 print "Magic was "; phex(p-->AB_MAGIC, 4);
 116                 print " when it should have been "; phex(ALLOC_MAGIC, 4);
 117                 print ".^";
 118                 return;
 119         }
 120 #endif;
 121
 122         ! Turn the alloc node into a free node.
 123
 124         q = p-->AB_SIZE;
 125 #ifdef DEBUG;
 126         memset(p, $55, q);
 127 #endif;
 128         p-->FB_MAGIC = FREE_MAGIC;
 129         p-->FB_NEXT = mem_firstfree;
 130         p-->FB_PREV = 0;
 131         p-->FB_SIZE = q;
 132         if (mem_firstfree)
 133                 mem_firstfree-->FB_PREV = p;
 134         mem_firstfree = p;
 135
 136         ! Right. We've successfully freed the block; p points to the FB
 137         ! structure.
 138         !
 139         ! Unfortunately, they way we use memory leads to lots of
 140         ! fragmentation, which is bad. So we need to find out if we can coalesce
 141         ! with the block immediately afterwards.
 142
 143         if ((p+q)-->0 ~= FREE_MAGIC)
 144         {
 145                 ! Nothing coalescable.
 146                 return;
 147         }
 148
 149         ! Change the size of our block to encompass the next block...
 150
 151         p-->FB_SIZE = q + (p+q)-->FB_SIZE;
 152
 153         ! ...and remove the next block from the free list.
 154
 155         mem_node_remove(p+q);
 156 ];
 157
 158 ! Get amount of free memory.
 159
 160 [ mem_countfree p size;
 161         size = 0;
 162         p = mem_firstfree;
 163         while (p ~= 0)
 164         {
 165                 size = size + p-->FB_SIZE;
 166                 p = p-->FB_NEXT;
 167         }
 168         return size;
 169 ];
 170
 171 ! Get total amount of memory.
 172
 173 [ mem_counttotal;
 174         return (mem_top - mem_bottom);
 175 ];
 176
 177 ! Get amount of used memory.
 178
 179 [ mem_countused;
 180         return mem_counttotal() - mem_countfree();
 181 ];
 182
 183 #ifdef DEBUG;
 184 ! Dump the free list.
 185
 186 [ mem_show_free_list p;
 187         print "Free list start^";
 188         p = mem_firstfree;
 189         while (p ~= 0)
 190         {
 191                 print "  node ", p, " prev=", p-->FB_PREV, " next=", p-->FB_NEXT;
 192                 print " size=", p-->FB_SIZE;
 193                 if (p-->FB_MAGIC ~= FREE_MAGIC)
 194                         print " invalid magic";
 195                 print "^";
 196                 p = p-->FB_NEXT;
 197         }
 198         print "Free list end; used=", mem_countused(), " total=", mem_counttotal(), "^";
 199 ];
 200
 201 #endif;
 202