modules/src/malloc/mal.c

   1 /* $Id: mal.c,v 1.22 1994/06/24 11:17:57 ceriel Exp $ */
   2 /*
   3  * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
   4  * See the copyright notice in the ACK home directory, in the file "Copyright".
   5  */
   6 #include        "param.h"
   7 #include        "impl.h"
   8 #include        "check.h"
   9 #include        "log.h"
  10 #include        "phys.h"
  11
  12 /*      Malloc space is traversed by N doubly-linked lists of chunks, each
  13         containing a couple of house-keeping data addressed as a
  14         'mallink' and a piece of useful space, called the block.
  15         The N lists are accessed through their starting pointers in
  16         free_list[].  Free_list[n] points to a list of chunks between
  17         2**(n+LOG_MIN_SIZE) and 2**(n+LOG_MIN_SIZE+1)-1, which means
  18         that the smallest chunk is 2**LOG_MIN_SIZE (== MIN_SIZE).
  19 */
  20
  21 #ifdef SYSTEM
  22 #include        <system.h>
  23 #define SBRK    sys_break
  24 #else
  25 #define SBRK    sbrk
  26 #define ILL_BREAK               (char *)(-1)    /* funny failure value */
  27 #endif
  28 extern char *SBRK();
  29 #ifdef STORE
  30 #define MAX_STORE       32
  31 #define MAX_SZ_IN_STORE (MAX_STORE*ALIGNMENT)
  32 private do_free(), sell_out();
  33 privatedata mallink *store[MAX_STORE];
  34 #endif /* STORE */
  35
  36 char *
  37 malloc(n)
  38         register unsigned int n;
  39 {check_mallinks("malloc entry");{
  40         register mallink *ml;
  41         register int min_class;
  42
  43         if (n == 0) {
  44                 return 0;
  45         }
  46         if (n < MIN_SIZE) n = align(MIN_SIZE); else n = align(n);
  47 #ifdef STORE
  48         if (n <= MAX_SZ_IN_STORE)       {
  49                 /* look in the store first */
  50                 register mallink **stp = &store[(n >> LOG_ALIGNMENT) - 1];
  51
  52                 if (ml = *stp)  {
  53                         *stp = log_next_of(ml);
  54                         set_store(ml, 0);
  55                         check_mallinks("malloc fast exit");
  56                         assert(! in_store(ml));
  57                         return block_of_mallink(ml);
  58                 }
  59         }
  60 #endif /* STORE */
  61
  62         check_work_empty("malloc, entry");
  63
  64         /*      Acquire a chunk of at least size n if at all possible;
  65                 Try everything.
  66         */
  67         {
  68                 /*      Inline substitution of "smallest".
  69                 */
  70                 register unsigned int n1 = n;
  71
  72                 assert(n1 < (1L << LOG_MAX_SIZE));
  73                 min_class = 0;
  74
  75                 do {
  76                         n1 >>= 1;
  77                         min_class++;
  78                 } while (n1 >= MIN_SIZE);
  79         }
  80
  81         if (min_class >= MAX_FLIST)
  82                 return (char *) 0;      /* we don't deal in blocks that big */
  83         ml = first_present(min_class);
  84         if (ml == MAL_NULL)     {
  85                 /*      Try and extend */
  86                 register char *p;
  87 #define GRABSIZE        4096            /* Power of 2 */
  88                 register unsigned int req =
  89                         ((MIN_SIZE<<min_class)+ mallink_size() + GRABSIZE - 1) &
  90                                 ~(GRABSIZE-1);
  91
  92                 if (!ml_last)   {
  93                         /* first align SBRK() */
  94
  95                         p = SBRK(0);
  96                         SBRK((int) (align((size_type) p) - (size_type) p));
  97                 }
  98
  99                 /* SBRK takes an int; sorry ... */
 100                 if ((int) req < 0) {
 101                         p = ILL_BREAK;
 102                 }
 103                 else {
 104                         p = SBRK((int)req);
 105                 }
 106                 if (p == ILL_BREAK) {
 107                         req = n + mallink_size();
 108                         if ((int) req >= 0) p = SBRK((int)req);
 109                 }
 110                 if (p == ILL_BREAK)     {
 111                         /*      Now this is bad.  The system will not give us
 112                                 more memory.  We can only liquidate our store
 113                                 and hope it helps.
 114                         */
 115 #ifdef STORE
 116                         sell_out();
 117                         ml = first_present(min_class);
 118                         if (ml == MAL_NULL)     {
 119 #endif /* STORE */
 120                                 /* In this emergency we try to locate a suitable
 121                                    chunk in the free_list just below the safe
 122                                    one; some of these chunks may fit the job.
 123                                 */
 124                                 ml = search_free_list(min_class - 1, n);
 125                                 if (!ml)        /* really out of space */
 126                                         return (char *) 0;
 127                                 started_working_on(ml);
 128                                 unlink_free_chunk(ml);
 129                                 check_mallinks("suitable_chunk, forced");
 130 #ifdef STORE
 131                         }
 132                         else started_working_on(ml);
 133 #endif /* STORE */
 134                 }
 135                 else {
 136                         assert((size_type)p == align((size_type)p));
 137                         ml = create_chunk(p, req);
 138                 }
 139                 check_mallinks("suitable_chunk, extended");
 140         }
 141         else started_working_on(ml);
 142
 143         /* we have a chunk */
 144         set_free(ml, 0);
 145         calc_checksum(ml);
 146         check_mallinks("suitable_chunk, removed");
 147         n += mallink_size();
 148         if (n + MIN_SIZE <= size_of(ml)) {
 149                 truncate(ml, n);
 150         }
 151         stopped_working_on(ml);
 152         check_mallinks("malloc exit");
 153         check_work_empty("malloc exit");
 154 #ifdef STORE
 155         assert(! in_store(ml));
 156 #endif
 157         return block_of_mallink(ml);
 158 }}
 159
 160 free(addr)
 161         char *addr;
 162 {check_mallinks("free entry");{
 163         register mallink *ml;
 164
 165         if (addr == 0) {
 166                 check_mallinks("free(0) very fast exit");
 167                 return;
 168         }
 169         ml = mallink_of_block(addr);
 170
 171 #ifdef STORE
 172
 173         if (free_of(ml) || in_store(ml))
 174                 return;                         /* user frees free block */
 175         if (size_of(ml) <= MAX_SZ_IN_STORE)     {
 176                 /* return to store */
 177                 mallink **stp = &store[(size_of(ml) >> LOG_ALIGNMENT) - 1];
 178
 179                 set_log_next(ml, *stp);
 180                 *stp = ml;
 181                 set_store(ml, 1);
 182                 calc_checksum(ml);
 183                 check_mallinks("free fast exit");
 184         }
 185         else    {
 186                 do_free(ml);
 187                 check_mallinks("free exit");
 188         }
 189 }}
 190
 191 private
 192 do_free(ml)
 193         register mallink *ml;
 194 {{
 195 #endif
 196
 197 #ifndef STORE
 198         if (free_of(ml))        return;
 199 #endif /* STORE */
 200         started_working_on(ml);
 201         set_free(ml, 1);
 202         calc_checksum(ml);
 203         if (! last_mallink(ml)) {
 204                 register mallink *next = phys_next_of(ml);
 205
 206                 if (free_of(next)) coalesce_forw(ml, next);
 207         }
 208
 209         if (! first_mallink(ml)) {
 210                 register mallink *prev = phys_prev_of(ml);
 211
 212                 if (free_of(prev)) {
 213                         coalesce_backw(ml, prev);
 214                         ml = prev;
 215                 }
 216         }
 217         link_free_chunk(ml);
 218         stopped_working_on(ml);
 219         check_work_empty("free");
 220
 221         /* Compile-time checks on param.h */
 222         switch (0)      {
 223         case MIN_SIZE < OFF_SET * sizeof(mallink):      break;
 224         case 1: break;
 225         /*      If this statement does not compile due to duplicate case
 226                 entry, the minimum size block cannot hold the links for
 227                 the free blocks.  Either raise LOG_MIN_SIZE or switch
 228                 off NON_STANDARD.
 229         */
 230         }
 231         switch(0)       {
 232         case sizeof(char *) != sizeof(size_type):       break;
 233         case 1: break;
 234         /*      If this statement does not compile due to duplicate
 235                 case entry, size_type is not defined correctly.
 236                 Redefine and compile again.
 237         */
 238         }
 239 }}
 240
 241 char *
 242 realloc(addr, n)
 243         char *addr;
 244         register unsigned int n;
 245 {check_mallinks("realloc entry");{
 246         register mallink *ml, *ph_next;
 247         register size_type size;
 248
 249         if (addr == 0) {
 250                 /*      Behave like most Unix realloc's when handed a
 251                         null-pointer
 252                 */
 253                 return malloc(n);
 254         }
 255         if (n == 0) {
 256                 free(addr);
 257                 return 0;
 258         }
 259         ml = mallink_of_block(addr);
 260         if (n < MIN_SIZE) n = align(MIN_SIZE); else n = align(n);
 261 #ifdef STORE
 262         if (in_store(ml)) {
 263                 register mallink *stp = store[(size_of(ml) >> LOG_ALIGNMENT) - 1];
 264                 mallink *stp1 = 0;
 265                 while (ml != stp)       {
 266                         stp1 = stp;
 267                         stp = log_next_of(stp);
 268                 }
 269                 stp = log_next_of(stp);
 270                 if (! stp1) store[(size_of(ml) >> LOG_MIN_SIZE) - 1] = stp;
 271                 else set_log_next(stp1, stp);
 272                 set_store(ml, 0);
 273                 calc_checksum(ml);
 274         }
 275 #endif
 276         if (free_of(ml)) {
 277                 unlink_free_chunk(ml);
 278                 set_free(ml, 0);                /* user reallocs free block */
 279         }
 280         started_working_on(ml);
 281         size = size_of(ml);
 282         if (    /* we can simplify the problem by adding the next chunk: */
 283                 n > size &&
 284                 !last_mallink(ml) &&
 285                 (ph_next = phys_next_of(ml), free_of(ph_next)) &&
 286                 n <= size + mallink_size() + size_of(ph_next)
 287         )       {
 288                 /* add in the physically next chunk */
 289                 unlink_free_chunk(ph_next);
 290                 combine_chunks(ml, ph_next);
 291                 size = size_of(ml);
 292                 check_mallinks("realloc, combining");
 293         }
 294         if (n > size)   {               /* this didn't help */
 295                 char *new;
 296                 register char *l1, *l2 = addr;
 297
 298                 stopped_working_on(ml);
 299                 if (!(new = l1 = malloc(n))) return (char *) 0; /* no way */
 300                 while (size--) *l1++ = *l2++;
 301                 free(addr);
 302                 check_work_empty("mv_realloc");
 303 #ifdef STORE
 304                 assert(! in_store(mallink_of_block(new)));
 305 #endif
 306                 return new;
 307         }
 308         /* it helped, but maybe too well */
 309         n += mallink_size();
 310         if (n + MIN_SIZE <= size_of(ml)) {
 311                 truncate(ml, n);
 312         }
 313         stopped_working_on(ml);
 314         check_mallinks("realloc exit");
 315         check_work_empty("realloc");
 316 #ifdef STORE
 317         assert(! in_store(ml));
 318 #endif
 319         return addr;
 320 }}
 321
 322 /*      Auxiliary routines */
 323
 324 #ifdef STORE
 325 private
 326 sell_out()      {
 327         /*      Frees all block in store.
 328         */
 329         register mallink **stp;
 330
 331         for (stp = &store[0]; stp < &store[MAX_STORE]; stp++)   {
 332                 register mallink *ml = *stp;
 333
 334                 while (ml)      {
 335                         *stp = log_next_of(ml);
 336                         set_store(ml, 0);
 337                         do_free(ml);
 338                         ml = *stp;
 339                 }
 340         }
 341
 342 }
 343 #endif /* STORE */
 344
 345 #ifdef  ASSERT
 346 public
 347 m_assert(fn, ln)
 348         char *fn;
 349 {
 350         char ch;
 351
 352         while (*fn)
 353                 write(2, fn++, 1);
 354         write(2, ": malloc assert failed in line ", 31);
 355         ch = (ln / 100) + '0'; write(2, &ch, 1); ln %= 100;
 356         ch = (ln / 10) + '0'; write(2, &ch, 1); ln %= 10;
 357         ch = (ln / 1) + '0'; write(2, &ch, 1);
 358         write(2, "\n", 1);
 359         maldump(1);
 360 }
 361 #endif  /* ASSERT */