compilers/linux86-0.16.17/libc/malloc/malloc.c

   1 /* Copyright (C) 1995,1996 Robert de Bath <rdebath@cix.compulink.co.uk>
   2  * This file is part of the Linux-8086 C library and is distributed
   3  * under the GNU Library General Public License.
   4  */
   5
   6 /*
   7  * This is a combined alloca/malloc package. It uses a classic algorithm
   8  * and so may be seen to be quite slow compared to more modern routines
   9  * with 'nasty' distributions.
  10  */
  11
  12 #include <malloc.h>
  13 #include <errno.h>
  14
  15 #define MCHUNK          2048    /* Allocation unit in 'mem' elements */
  16 #define XLAZY_FREE              /* If set frees can be infinitly defered */
  17 #define XMINALLOC       32      /* Smallest chunk to alloc in 'mem's */
  18 #define XVERBOSE                /* Lots of noise, debuging ? */
  19
  20 #undef  malloc
  21 #define MAX_INT ((int)(((unsigned)-1)>>1))
  22
  23 #ifdef VERBOSE
  24 #define noise __noise
  25 #else
  26 #define noise(y,x)
  27 #endif
  28
  29 typedef union mem_cell
  30 {
  31    union mem_cell *next;        /* A pointer to the next mem */
  32    unsigned int size;           /* An int >= sizeof pointer */
  33    char *depth;                 /* For the alloca hack */
  34 }
  35 mem;
  36
  37 #define m_size(p)  ((p) [0].size)       /* For malloc */
  38 #define m_next(p)  ((p) [1].next)       /* For malloc and alloca */
  39 #define m_deep(p)  ((p) [0].depth)      /* For alloca */
  40
  41 extern void *__mini_malloc __P ((size_t));
  42 extern void *(*__alloca_alloc) __P ((size_t));
  43 extern mem *__freed_list;
  44
  45 #ifdef L_free
  46 /* Start the alloca with just the dumb version of malloc */
  47
  48 void *(*__alloca_alloc) __P ((size_t)) = __mini_malloc;
  49 mem  *__freed_list = 0;
  50
  51 #ifdef VERBOSE
  52 /* NB: Careful here, stdio may use malloc - so we can't */
  53 static
  54 phex(val)
  55 {
  56    static char hex[] = "0123456789ABCDEF";
  57    int   i;
  58    for (i = sizeof(int)*8-4; i >= 0; i -= 4)
  59       write(2, hex + ((val >> i) & 0xF), 1);
  60 }
  61
  62 noise(y, x)
  63 char *y;
  64 mem  *x;
  65 {
  66    write(2, "Malloc ", 7);
  67    phex(x);
  68    write(2, " sz ", 4);
  69    if(x) phex(m_size(x)); else phex(0);
  70    write(2, " nxt ", 5);
  71    if(x) phex(m_next(x)); else phex(0);
  72    write(2, " is ", 4);
  73    write(2, y, strlen(y));
  74    write(2, "\n", 1);
  75 }
  76 #endif
  77
  78 #endif
  79
  80 #ifdef L_alloca
  81 /* This alloca is based on the same concept as the EMACS fallback alloca.
  82  * It should probably be considered Copyright the FSF under the GPL.
  83  */
  84 static mem *alloca_stack = 0;
  85
  86 void *
  87 alloca(size)
  88 size_t size;
  89 {
  90    auto char probe;             /* Probes stack depth: */
  91    register mem *hp;
  92
  93    /*
  94     * Reclaim garbage, defined as all alloca'd storage that was allocated
  95     * from deeper in the stack than currently.
  96     */
  97
  98    for (hp = alloca_stack; hp != 0;)
  99       if (m_deep(hp) < &probe)
 100       {
 101          register mem *np = m_next(hp);
 102          free((void *) hp);     /* Collect garbage.  */
 103          hp = np;               /* -> next header.  */
 104       }
 105       else
 106          break;                 /* Rest are not deeper.  */
 107
 108    alloca_stack = hp;           /* -> last valid storage.  */
 109    if (size == 0)
 110       return 0;                 /* No allocation required.  */
 111
 112    hp = (mem *) (*__alloca_alloc) (sizeof(mem)*2 + size);
 113    if (hp == 0)
 114       return hp;
 115
 116    m_next(hp) = alloca_stack;
 117    m_deep(hp) = &probe;
 118    alloca_stack = hp;
 119
 120    /* User storage begins just after header.  */
 121    return (void *) (hp + 2);
 122 }
 123 #endif                          /* L_alloca */
 124
 125 #ifdef L_free
 126 void
 127 free(ptr)
 128 void *ptr;
 129 {
 130    register mem *top;
 131    register mem *chk = (mem *) ptr;
 132
 133    if (chk == 0)
 134       return;                   /* free(NULL) - be nice */
 135    chk--;
 136
 137  try_this:;
 138    top = (mem *) sbrk(0);
 139    if (chk + m_size(chk) == top)
 140    {
 141       noise("FREE brk", chk);
 142       brk(top-m_size(chk));
 143       /*
 144        * Adding this code allow free to release blocks in any order; they
 145        * can still only be allocated from the top of the heap tho.
 146        */
 147 #ifdef __MINI_MALLOC__
 148       if (__alloca_alloc == __mini_malloc && __freed_list)
 149       {
 150          mem *prev, *curr;
 151          chk = __freed_list;
 152          __freed_list = m_next(__freed_list);
 153          goto try_this;
 154       }
 155 #endif
 156    }
 157    else
 158    {                            /* Nope, not sure where this goes, leave
 159                                  * it for malloc to deal with */
 160 #ifdef __MINI_MALLOC__
 161       if( __freed_list || chk > __freed_list )
 162       { m_next(chk) = __freed_list; __freed_list = chk; }
 163       else
 164       {
 165          register mem *prev;
 166          prev=__freed_list;
 167          for(top=__freed_list; top && top > chk; prev=top, top=m_next(top))
 168              ;
 169          m_next(chk) = top;
 170          m_next(prev) = chk;
 171       }
 172 #else
 173       m_next(chk) = __freed_list;
 174       __freed_list = chk;
 175 #endif
 176       noise("ADD LIST", chk);
 177    }
 178 }
 179
 180 void *
 181 __mini_malloc(size)
 182 size_t size;
 183 {
 184    register mem *ptr;
 185    register unsigned int sz;
 186
 187    /* First time round this _might_ be odd, But we won't do that! */
 188    sz = (unsigned int) sbrk(0);
 189    if (sz & (sizeof(mem) - 1))
 190       sbrk(4 - (sz & (sizeof(mem) - 1)));
 191
 192    if (size <= 0)
 193       return 0;
 194    /* Minor oops here, sbrk has a signed argument */
 195    if( size > (((unsigned)-1)>>1)-sizeof(mem)*3 )
 196    {
 197       errno = ENOMEM;
 198       return 0;
 199    }
 200
 201    size += sizeof(mem) * 2 - 1; /* Round up and leave space for size field */
 202    size /= sizeof(mem);
 203
 204    ptr = (mem *) sbrk(size * sizeof(mem));
 205    if ((int) ptr == -1)
 206       return 0;
 207
 208    m_size(ptr) = size;
 209    noise("CREATE", ptr);
 210    return ptr + 1;
 211 }
 212 #endif                          /* L_free */
 213
 214 #ifdef L_malloc
 215
 216 /*
 217  * The chunk_list pointer is either NULL or points to a chunk in a
 218  * circular list of all the free blocks in memory
 219  */
 220
 221 #define Static static
 222
 223 static mem *chunk_list = 0;
 224 Static void __insert_chunk();
 225 Static mem *__search_chunk();
 226
 227 void *
 228 malloc(size)
 229 size_t size;
 230 {
 231    register mem *ptr = 0;
 232    register unsigned int sz;
 233
 234    if (size == 0)
 235       return 0;                 /* ANSI STD */
 236
 237    sz = size + sizeof(mem) * 2 - 1;
 238    sz /= sizeof(mem);
 239
 240 #ifdef MINALLOC
 241    if (sz < MINALLOC)
 242       sz = MINALLOC;
 243 #endif
 244
 245 #ifdef VERBOSE
 246    {
 247       static mem arr[2];
 248       m_size(arr) = sz;
 249       noise("WANTED", arr);
 250    }
 251 #endif
 252
 253    __alloca_alloc = malloc;     /* We'll be messing with the heap now TVM */
 254
 255 #ifdef LAZY_FREE
 256    ptr = __search_chunk(sz);
 257    if (ptr == 0)
 258    {
 259 #endif
 260
 261       /* First deal with the freed list */
 262       if (__freed_list)
 263       {
 264          while (__freed_list)
 265          {
 266             ptr = __freed_list;
 267             __freed_list = m_next(__freed_list);
 268
 269             if (m_size(ptr) == sz)      /* Oh! Well that's lucky ain't it
 270                                          * :-) */
 271             {
 272                noise("LUCKY MALLOC", ptr);
 273                return ptr + 1;
 274             }
 275
 276             __insert_chunk(ptr);
 277          }
 278          ptr = m_next(chunk_list);
 279          if (ptr + m_size(ptr) == (void *) sbrk(0))
 280          {
 281             /* Time to free for real */
 282             m_next(chunk_list) = m_next(ptr);
 283             if (ptr == m_next(ptr))
 284                chunk_list = 0;
 285             free(ptr + 1);
 286          }
 287 #ifdef LAZY_FREE
 288          ptr = __search_chunk(sz);
 289 #endif
 290       }
 291 #ifndef LAZY_FREE
 292       ptr = __search_chunk(sz);
 293 #endif
 294       if (ptr == 0)
 295       {
 296 #ifdef MCHUNK
 297          unsigned int alloc;
 298          alloc = sizeof(mem) * (MCHUNK * ((sz + MCHUNK - 1) / MCHUNK) - 1);
 299          ptr = __mini_malloc(alloc);
 300          if (ptr)
 301             __insert_chunk(ptr - 1);
 302          else           /* Oooo, near end of RAM */
 303          {
 304             unsigned int needed = alloc;
 305             for(alloc/=2; alloc>256 && needed; )
 306             {
 307                ptr = __mini_malloc(alloc);
 308                if (ptr)
 309                {
 310                   if( alloc > needed ) needed = 0; else needed -= alloc;
 311                   __insert_chunk(ptr - 1);
 312                }
 313                else     alloc/=2;
 314             }
 315          }
 316          ptr = __search_chunk(sz);
 317          if (ptr == 0)
 318 #endif
 319          {
 320 #ifndef MCHUNK
 321             ptr = __mini_malloc(size);
 322 #endif
 323 #ifdef VERBOSE
 324             if( ptr == 0 )
 325                noise("MALLOC FAIL", 0);
 326             else
 327                noise("MALLOC NOW", ptr - 1);
 328 #endif
 329             return ptr;
 330          }
 331       }
 332 #ifdef LAZY_FREE
 333    }
 334 #endif
 335
 336 #ifdef VERBOSE
 337    ptr[1].size = 0x55555555;
 338 #endif
 339    noise("MALLOC RET", ptr);
 340    return ptr + 1;
 341 }
 342
 343 /*
 344  * This function takes a pointer to a block of memory and inserts it into
 345  * the chain of memory chunks
 346  */
 347
 348 Static void
 349 __insert_chunk(mem_chunk)
 350 mem  *mem_chunk;
 351 {
 352    register mem *p1, *p2;
 353    if (chunk_list == 0)         /* Simple case first */
 354    {
 355       m_next(mem_chunk) = chunk_list = mem_chunk;
 356       noise("FIRST CHUNK", mem_chunk);
 357       return;
 358    }
 359    p1 = mem_chunk;
 360    p2 = chunk_list;
 361
 362    do
 363    {
 364       if (p1 > p2)
 365       {
 366          if (m_next(p2) <= p2)
 367          {                      /* We're at the top of the chain, p1 is
 368                                  * higher */
 369
 370             if (p2 + m_size(p2) == p1)
 371             {                   /* Good, stick 'em together */
 372                noise("INSERT CHUNK", mem_chunk);
 373                m_size(p2) += m_size(p1);
 374                noise("JOIN 1", p2);
 375             }
 376             else
 377             {
 378                m_next(p1) = m_next(p2);
 379                m_next(p2) = p1;
 380                noise("INSERT CHUNK", mem_chunk);
 381                noise("FROM", p2);
 382             }
 383             return;
 384          }
 385          if (m_next(p2) > p1)
 386          {
 387             /* In chain, p1 between p2 and next */
 388
 389             m_next(p1) = m_next(p2);
 390             m_next(p2) = p1;
 391             noise("INSERT CHUNK", mem_chunk);
 392             noise("FROM", p2);
 393
 394             /* Try to join above */
 395             if (p1 + m_size(p1) == m_next(p1))
 396             {
 397                m_size(p1) += m_size(m_next(p1));
 398                m_next(p1) = m_next(m_next(p1));
 399                noise("JOIN 2", p1);
 400             }
 401             /* Try to join below */
 402             if (p2 + m_size(p2) == p1)
 403             {
 404                m_size(p2) += m_size(p1);
 405                m_next(p2) = m_next(p1);
 406                noise("JOIN 3", p2);
 407             }
 408             chunk_list = p2;    /* Make sure it's valid */
 409             return;
 410          }
 411       }
 412       else if (p1 < p2)
 413       {
 414          if (m_next(p2) <= p2 && p1 < m_next(p2))
 415          {
 416             /* At top of chain, next is bottom of chain, p1 is below next */
 417
 418             m_next(p1) = m_next(p2);
 419             m_next(p2) = p1;
 420             noise("INSERT CHUNK", mem_chunk);
 421             noise("FROM", p2);
 422             chunk_list = p2;
 423
 424             if (p1 + m_size(p1) == m_next(p1))
 425             {
 426                if (p2 == m_next(p1))
 427                   chunk_list = p1;
 428                m_size(p1) += m_size(m_next(p1));
 429                m_next(p1) = m_next(m_next(p1));
 430                noise("JOIN 4", p1);
 431             }
 432             return;
 433          }
 434       }
 435       chunk_list = p2;          /* Save for search */
 436       p2 = m_next(p2);
 437    }
 438    while (p2 != chunk_list);
 439
 440    /* If we get here we have a problem, ignore it, maybe it'll go away */
 441    noise("DROPPED CHUNK", mem_chunk);
 442 }
 443
 444 /*
 445  * This function will search for a chunk in memory of at least 'mem_size'
 446  * when found, if the chunk is too big it'll be split, and pointer to the
 447  * chunk returned. If none is found NULL is returned.
 448  */
 449
 450 Static mem *
 451 __search_chunk(mem_size)
 452 unsigned int mem_size;
 453 {
 454    register mem *p1, *p2;
 455    if (chunk_list == 0)         /* Simple case first */
 456       return 0;
 457
 458    /* Search for a block >= the size we want */
 459    p1 = m_next(chunk_list);
 460    p2 = chunk_list;
 461    do
 462    {
 463       noise("CHECKED", p1);
 464       if (m_size(p1) >= mem_size)
 465          break;
 466
 467       p2 = p1;
 468       p1 = m_next(p1);
 469    }
 470    while (p2 != chunk_list);
 471
 472    /* None found, exit */
 473    if (m_size(p1) < mem_size)
 474       return 0;
 475
 476    /* If it's exactly right remove it */
 477    if (m_size(p1) < mem_size + 2)
 478    {
 479       noise("FOUND RIGHT", p1);
 480       chunk_list = m_next(p2) = m_next(p1);
 481       if (chunk_list == p1)
 482          chunk_list = 0;
 483       return p1;
 484    }
 485
 486    noise("SPLIT", p1);
 487    /* Otherwise split it */
 488    m_next(p2) = p1 + mem_size;
 489    chunk_list = p2;
 490
 491    p2 = m_next(p2);
 492    m_size(p2) = m_size(p1) - mem_size;
 493    m_next(p2) = m_next(p1);
 494    m_size(p1) = mem_size;
 495    if (chunk_list == p1)
 496       chunk_list = p2;
 497 #ifdef VERBOSE
 498    p1[1].size = 0xAAAAAAAA;
 499 #endif
 500    noise("INSERT CHUNK", p2);
 501    noise("FOUND CHUNK", p1);
 502    noise("LIST IS", chunk_list);
 503    return p1;
 504 }
 505
 506 #endif                          /* L_malloc */
 507
 508 #ifdef L_calloc
 509 void *
 510 calloc(elm, sz)
 511 unsigned int elm, sz;
 512 {
 513    register unsigned int v;
 514    register void *ptr;
 515    ptr = malloc(v = elm * sz);
 516    if (ptr)
 517       memset(ptr, 0, v);
 518    return ptr;
 519 }
 520 #endif                          /* L_calloc */
 521
 522 #ifdef L_realloc
 523 void *
 524 realloc(ptr, size)
 525 void *ptr;
 526 size_t size;
 527 {
 528    void *nptr;
 529    unsigned int osize;
 530    if (ptr == 0)
 531       return malloc(size);
 532
 533    osize = (m_size(((mem *) ptr) - 1) - 1) * sizeof(mem);
 534    if (size <= osize)
 535    {
 536       return ptr;
 537    }
 538
 539    nptr = malloc(size);
 540
 541    if (nptr == 0)
 542       return 0;
 543
 544    memcpy(nptr, ptr, osize);
 545    free(ptr);
 546
 547    return nptr;
 548 }
 549 #endif                          /* L_realloc */