debug/programs/tiny-malloc.c

   1 // https://github.com/32bitmicro/newlib-nano-1.0/blob/master/newlib/libc/machine/xstormy16/tiny-malloc.c
   2
   3 /* A replacement malloc with:
   4    - Much reduced code size;
   5    - Smaller RAM footprint;
   6    - The ability to handle downward-growing heaps;
   7    but
   8    - Slower;
   9    - Probably higher memory fragmentation;
  10    - Doesn't support threads (but, if it did support threads,
  11      it wouldn't need a global lock, only a compare-and-swap instruction);
  12    - Assumes the maximum alignment required is the alignment of a pointer;
  13    - Assumes that memory is already there and doesn't need to be allocated.
  14
  15 * Synopsis of public routines
  16
  17   malloc(size_t n);
  18      Return a pointer to a newly allocated chunk of at least n bytes, or null
  19      if no space is available.
  20   free(void* p);
  21      Release the chunk of memory pointed to by p, or no effect if p is null.
  22   realloc(void* p, size_t n);
  23      Return a pointer to a chunk of size n that contains the same data
  24      as does chunk p up to the minimum of (n, p's size) bytes, or null
  25      if no space is available. The returned pointer may or may not be
  26      the same as p. If p is null, equivalent to malloc.  Unless the
  27      #define REALLOC_ZERO_BYTES_FREES below is set, realloc with a
  28      size argument of zero (re)allocates a minimum-sized chunk.
  29   memalign(size_t alignment, size_t n);
  30      Return a pointer to a newly allocated chunk of n bytes, aligned
  31      in accord with the alignment argument, which must be a power of
  32      two.  Will fail if 'alignment' is too large.
  33   calloc(size_t unit, size_t quantity);
  34      Returns a pointer to quantity * unit bytes, with all locations
  35      set to zero.
  36   cfree(void* p);
  37      Equivalent to free(p).
  38   malloc_trim(size_t pad);
  39      Release all but pad bytes of freed top-most memory back
  40      to the system. Return 1 if successful, else 0.
  41   malloc_usable_size(void* p);
  42      Report the number usable allocated bytes associated with allocated
  43      chunk p. This may or may not report more bytes than were requested,
  44      due to alignment and minimum size constraints.
  45   malloc_stats();
  46      Prints brief summary statistics on stderr.
  47   mallinfo()
  48      Returns (by copy) a struct containing various summary statistics.
  49   mallopt(int parameter_number, int parameter_value)
  50      Changes one of the tunable parameters described below. Returns
  51      1 if successful in changing the parameter, else 0.  Actually, returns 0
  52      always, as no parameter can be changed.
  53 */
  54
  55 #ifdef __xstormy16__
  56 #define MALLOC_DIRECTION -1
  57 #endif
  58
  59 #ifndef MALLOC_DIRECTION
  60 #define MALLOC_DIRECTION 1
  61 #endif
  62
  63 #include <stddef.h>
  64
  65 void* malloc(size_t);
  66 void    free(void*);
  67 void* realloc(void*, size_t);
  68 void* memalign(size_t, size_t);
  69 void* valloc(size_t);
  70 void* pvalloc(size_t);
  71 void* calloc(size_t, size_t);
  72 void    cfree(void*);
  73 int     malloc_trim(size_t);
  74 size_t  malloc_usable_size(void*);
  75 void    malloc_stats(void);
  76 int     mallopt(int, int);
  77 struct mallinfo mallinfo(void);
  78
  79 typedef struct freelist_entry {
  80   size_t size;
  81   struct freelist_entry *next;
  82 } *fle;
  83
  84 extern void * __malloc_end;
  85 extern fle __malloc_freelist;
  86
  87 /* Return the number of bytes that need to be added to X to make it
  88    aligned to an ALIGN boundary.  ALIGN must be a power of 2.  */
  89 #define M_ALIGN(x, align) (-(size_t)(x) & ((align) - 1))
  90
  91 /* Return the number of bytes that need to be subtracted from X to make it
  92    aligned to an ALIGN boundary.  ALIGN must be a power of 2.  */
  93 #define M_ALIGN_SUB(x, align) ((size_t)(x) & ((align) - 1))
  94
  95 extern char *__malloc_start;
  96
  97 /* This is the minimum gap allowed between __malloc_end and the top of
  98    the stack.  This is only checked for when __malloc_end is
  99    decreased; if instead the stack grows into the heap, silent data
 100    corruption will result.  */
 101 #define MALLOC_MINIMUM_GAP 32
 102
 103 #ifdef __xstormy16__
 104 register void * stack_pointer asm ("r15");
 105 #define MALLOC_LIMIT stack_pointer
 106 #else
 107 #define MALLOC_LIMIT __builtin_frame_address (0)
 108 #endif
 109
 110 #if MALLOC_DIRECTION < 0
 111 #define CAN_ALLOC_P(required)                           \
 112   (((size_t) __malloc_end - (size_t)MALLOC_LIMIT        \
 113     - MALLOC_MINIMUM_GAP) >= (required))
 114 #else
 115 #define CAN_ALLOC_P(required)                           \
 116   (((size_t)MALLOC_LIMIT - (size_t) __malloc_end        \
 117     - MALLOC_MINIMUM_GAP) >= (required))
 118 #endif
 119
 120 /* real_size is the size we actually have to allocate, allowing for
 121    overhead and alignment.  */
 122 #define REAL_SIZE(sz)                                           \
 123   ((sz) < sizeof (struct freelist_entry) - sizeof (size_t)      \
 124    ? sizeof (struct freelist_entry)                             \
 125    : sz + sizeof (size_t) + M_ALIGN(sz, sizeof (size_t)))
 126
 127 #ifdef DEFINE_MALLOC
 128
 129 void * __malloc_end = &__malloc_start;
 130 fle __malloc_freelist;
 131
 132 void *
 133 malloc (size_t sz)
 134 {
 135   fle *nextfree;
 136   fle block;
 137
 138   /* real_size is the size we actually have to allocate, allowing for
 139      overhead and alignment.  */
 140   size_t real_size = REAL_SIZE (sz);
 141
 142   /* Look for the first block on the freelist that is large enough.  */
 143   for (nextfree = &__malloc_freelist;
 144        *nextfree;
 145        nextfree = &(*nextfree)->next)
 146     {
 147       block = *nextfree;
 148
 149       if (block->size >= real_size)
 150         {
 151           /* If the block found is just the right size, remove it from
 152              the free list.  Otherwise, split it.  */
 153           if (block->size < real_size + sizeof (struct freelist_entry))
 154             {
 155               *nextfree = block->next;
 156               return (void *)&block->next;
 157             }
 158           else
 159             {
 160               size_t newsize = block->size - real_size;
 161               fle newnext = block->next;
 162               *nextfree = (fle)((size_t)block + real_size);
 163               (*nextfree)->size = newsize;
 164               (*nextfree)->next = newnext;
 165               goto done;
 166             }
 167         }
 168
 169       /* If this is the last block on the freelist, and it was too small,
 170          enlarge it.  */
 171       if (! block->next
 172           && __malloc_end == (void *)((size_t)block + block->size))
 173         {
 174           size_t moresize = real_size - block->size;
 175           if (! CAN_ALLOC_P (moresize))
 176             return NULL;
 177
 178           *nextfree = NULL;
 179           if (MALLOC_DIRECTION < 0)
 180             {
 181               block = __malloc_end = (void *)((size_t)block - moresize);
 182             }
 183           else
 184             {
 185               __malloc_end = (void *)((size_t)block + real_size);
 186             }
 187
 188           goto done;
 189         }
 190     }
 191
 192   /* No free space at the end of the free list.  Allocate new space
 193      and use that.  */
 194
 195   if (! CAN_ALLOC_P (real_size))
 196     return NULL;
 197
 198   if (MALLOC_DIRECTION > 0)
 199     {
 200       block = __malloc_end;
 201       __malloc_end = (void *)((size_t)__malloc_end + real_size);
 202     }
 203   else
 204     {
 205       block = __malloc_end = (void *)((size_t)__malloc_end - real_size);
 206     }
 207  done:
 208   block->size = real_size;
 209   return (void *)&block->next;
 210 }
 211
 212 #endif
 213
 214 #ifdef DEFINE_FREE
 215
 216 void
 217 free (void *block_p)
 218 {
 219   fle *nextfree;
 220   fle block = (fle)((size_t) block_p - offsetof (struct freelist_entry, next));
 221
 222   if (block_p == NULL)
 223     return;
 224
 225   /* Look on the freelist to see if there's a free block just before
 226      or just after this block.  */
 227   for (nextfree = &__malloc_freelist;
 228        *nextfree;
 229        nextfree = &(*nextfree)->next)
 230     {
 231       fle thisblock = *nextfree;
 232       if ((size_t)thisblock + thisblock->size == (size_t) block)
 233         {
 234           thisblock->size += block->size;
 235           if (MALLOC_DIRECTION > 0
 236               && thisblock->next
 237               && (size_t) block + block->size == (size_t) thisblock->next)
 238             {
 239               thisblock->size += thisblock->next->size;
 240               thisblock->next = thisblock->next->next;
 241             }
 242           return;
 243         }
 244       else if ((size_t) thisblock == (size_t) block + block->size)
 245         {
 246           if (MALLOC_DIRECTION < 0
 247               && thisblock->next
 248               && (size_t) block == ((size_t) thisblock->next
 249                                     + thisblock->next->size))
 250             {
 251               *nextfree = thisblock->next;
 252               thisblock->next->size += block->size + thisblock->size;
 253             }
 254           else
 255             {
 256               block->size += thisblock->size;
 257               block->next = thisblock->next;
 258               *nextfree = block;
 259             }
 260           return;
 261         }
 262       else if ((MALLOC_DIRECTION > 0
 263                 && (size_t) thisblock > (size_t) block)
 264                || (MALLOC_DIRECTION < 0
 265                    && (size_t) thisblock < (size_t) block))
 266         break;
 267     }
 268
 269   block->next = *nextfree;
 270   *nextfree = block;
 271   return;
 272 }
 273 #endif
 274
 275 #ifdef DEFINE_REALLOC
 276 void *
 277 realloc (void *block_p, size_t sz)
 278 {
 279   fle block = (fle)((size_t) block_p - offsetof (struct freelist_entry, next));
 280   size_t real_size = REAL_SIZE (sz);
 281   size_t old_real_size;
 282
 283   if (block_p == NULL)
 284     return malloc (sz);
 285
 286   old_real_size = block->size;
 287
 288   /* Perhaps we need to allocate more space.  */
 289   if (old_real_size < real_size)
 290     {
 291       void *result;
 292       size_t old_size = old_real_size - sizeof (size_t);
 293
 294       /* Need to allocate, copy, and free.  */
 295       result = malloc (sz);
 296       if (result == NULL)
 297         return NULL;
 298       memcpy (result, block_p, old_size < sz ? old_size : sz);
 299       free (block_p);
 300       return result;
 301     }
 302   /* Perhaps we can free some space.  */
 303   if (old_real_size - real_size >= sizeof (struct freelist_entry))
 304     {
 305       fle newblock = (fle)((size_t)block + real_size);
 306       block->size = real_size;
 307       newblock->size = old_real_size - real_size;
 308       free (&newblock->next);
 309     }
 310   return block_p;
 311 }
 312 #endif
 313
 314 #ifdef DEFINE_CALLOC
 315 void *
 316 calloc (size_t n, size_t elem_size)
 317 {
 318   void *result;
 319   size_t sz = n * elem_size;
 320   result = malloc (sz);
 321   if (result != NULL)
 322     memset (result, 0, sz);
 323   return result;
 324 }
 325 #endif
 326
 327 #ifdef DEFINE_CFREE
 328 void
 329 cfree (void *p)
 330 {
 331   free (p);
 332 }
 333 #endif
 334
 335 #ifdef DEFINE_MEMALIGN
 336 void *
 337 memalign (size_t align, size_t sz)
 338 {
 339   fle *nextfree;
 340   fle block;
 341
 342   /* real_size is the size we actually have to allocate, allowing for
 343      overhead and alignment.  */
 344   size_t real_size = REAL_SIZE (sz);
 345
 346   /* Some sanity checking on 'align'. */
 347   if ((align & (align - 1)) != 0
 348       || align <= 0)
 349     return NULL;
 350
 351   /* Look for the first block on the freelist that is large enough.  */
 352   /* One tricky part is this: We want the result to be a valid pointer
 353      to free.  That means that there has to be room for a size_t
 354      before the block.  If there's additional space before the block,
 355      it should go on the freelist, or it'll be lost---we could add it
 356      to the size of the block before it in memory, but finding the
 357      previous block is expensive.  */
 358   for (nextfree = &__malloc_freelist;
 359        ;
 360        nextfree = &(*nextfree)->next)
 361     {
 362       size_t before_size;
 363       size_t old_size;
 364
 365       /* If we've run out of free blocks, allocate more space.  */
 366       if (! *nextfree)
 367         {
 368           old_size = real_size;
 369           if (MALLOC_DIRECTION < 0)
 370             {
 371               old_size += M_ALIGN_SUB (((size_t)__malloc_end
 372                                         - old_size + sizeof (size_t)),
 373                                        align);
 374               if (! CAN_ALLOC_P (old_size))
 375                 return NULL;
 376               block = __malloc_end = (void *)((size_t)__malloc_end - old_size);
 377             }
 378           else
 379             {
 380               block = __malloc_end;
 381               old_size += M_ALIGN ((size_t)__malloc_end + sizeof (size_t),
 382                                    align);
 383               if (! CAN_ALLOC_P (old_size))
 384                 return NULL;
 385               __malloc_end = (void *)((size_t)__malloc_end + old_size);
 386             }
 387           *nextfree = block;
 388           block->size = old_size;
 389           block->next = NULL;
 390         }
 391       else
 392         {
 393           block = *nextfree;
 394           old_size = block->size;
 395         }
 396
 397
 398       before_size = M_ALIGN (&block->next, align);
 399       if (before_size != 0)
 400         before_size = sizeof (*block) + M_ALIGN (&(block+1)->next, align);
 401
 402       /* If this is the last block on the freelist, and it is too small,
 403          enlarge it.  */
 404       if (! block->next
 405           && old_size < real_size + before_size
 406           && __malloc_end == (void *)((size_t)block + block->size))
 407         {
 408           if (MALLOC_DIRECTION < 0)
 409             {
 410               size_t moresize = real_size - block->size;
 411               moresize += M_ALIGN_SUB ((size_t)&block->next - moresize, align);
 412               if (! CAN_ALLOC_P (moresize))
 413                 return NULL;
 414               block = __malloc_end = (void *)((size_t)block - moresize);
 415               block->next = NULL;
 416               block->size = old_size = old_size + moresize;
 417               before_size = 0;
 418             }
 419           else
 420             {
 421               if (! CAN_ALLOC_P (before_size + real_size - block->size))
 422                 return NULL;
 423               __malloc_end = (void *)((size_t)block + before_size + real_size);
 424               block->size = old_size = before_size + real_size;
 425             }
 426
 427           /* Two out of the four cases below will now be possible; which
 428              two depends on MALLOC_DIRECTION.  */
 429         }
 430
 431       if (old_size >= real_size + before_size)
 432         {
 433           /* This block will do.  If there needs to be space before it,
 434              split the block.  */
 435           if (before_size != 0)
 436             {
 437               fle old_block = block;
 438
 439               old_block->size = before_size;
 440               block = (fle)((size_t)block + before_size);
 441
 442               /* If there's no space after the block, we're now nearly
 443                  done; just make a note of the size required.
 444                  Otherwise, we need to create a new free space block.  */
 445               if (old_size - before_size
 446                   <= real_size + sizeof (struct freelist_entry))
 447                 {
 448                   block->size = old_size - before_size;
 449                   return (void *)&block->next;
 450                 }
 451               else
 452                 {
 453                   fle new_block;
 454                   new_block = (fle)((size_t)block + real_size);
 455                   new_block->size = old_size - before_size - real_size;
 456                   if (MALLOC_DIRECTION > 0)
 457                     {
 458                       new_block->next = old_block->next;
 459                       old_block->next = new_block;
 460                     }
 461                   else
 462                     {
 463                       new_block->next = old_block;
 464                       *nextfree = new_block;
 465                     }
 466                   goto done;
 467                 }
 468             }
 469           else
 470             {
 471               /* If the block found is just the right size, remove it from
 472                  the free list.  Otherwise, split it.  */
 473               if (old_size <= real_size + sizeof (struct freelist_entry))
 474                 {
 475                   *nextfree = block->next;
 476                   return (void *)&block->next;
 477                 }
 478               else
 479                 {
 480                   size_t newsize = old_size - real_size;
 481                   fle newnext = block->next;
 482                   *nextfree = (fle)((size_t)block + real_size);
 483                   (*nextfree)->size = newsize;
 484                   (*nextfree)->next = newnext;
 485                   goto done;
 486                 }
 487             }
 488         }
 489     }
 490
 491  done:
 492   block->size = real_size;
 493   return (void *)&block->next;
 494 }
 495 #endif
 496
 497 #ifdef DEFINE_VALLOC
 498 void *
 499 valloc (size_t sz)
 500 {
 501   return memalign (128, sz);
 502 }
 503 #endif
 504 #ifdef DEFINE_PVALLOC
 505 void *
 506 pvalloc (size_t sz)
 507 {
 508   return memalign (128, sz + M_ALIGN (sz, 128));
 509 }
 510 #endif
 511
 512 #ifdef DEFINE_MALLINFO
 513 #include "malloc.h"
 514
 515 struct mallinfo
 516 mallinfo (void)
 517 {
 518   struct mallinfo r;
 519   fle fr;
 520   size_t free_size;
 521   size_t total_size;
 522   size_t free_blocks;
 523
 524   memset (&r, 0, sizeof (r));
 525
 526   free_size = 0;
 527   free_blocks = 0;
 528   for (fr = __malloc_freelist; fr; fr = fr->next)
 529     {
 530       free_size += fr->size;
 531       free_blocks++;
 532       if (! fr->next)
 533         {
 534           int atend;
 535           if (MALLOC_DIRECTION > 0)
 536             atend = (void *)((size_t)fr + fr->size) == __malloc_end;
 537           else
 538             atend = (void *)fr == __malloc_end;
 539           if (atend)
 540             r.keepcost = fr->size;
 541         }
 542     }
 543
 544   if (MALLOC_DIRECTION > 0)
 545     total_size = (char *)__malloc_end - (char *)&__malloc_start;
 546   else
 547     total_size = (char *)&__malloc_start - (char *)__malloc_end;
 548
 549 #ifdef DEBUG
 550   /* Fixme: should walk through all the in-use blocks and see if
 551      they're valid.  */
 552 #endif
 553
 554   r.arena = total_size;
 555   r.fordblks = free_size;
 556   r.uordblks = total_size - free_size;
 557   r.ordblks = free_blocks;
 558   return r;
 559 }
 560 #endif
 561
 562 #ifdef DEFINE_MALLOC_STATS
 563 #include "malloc.h"
 564 #include <stdio.h>
 565
 566 void
 567 malloc_stats(void)
 568 {
 569   struct mallinfo i;
 570   FILE *fp;
 571
 572   fp = stderr;
 573   i = mallinfo();
 574   fprintf (fp, "malloc has reserved %u bytes between %p and %p\n",
 575            i.arena, &__malloc_start, __malloc_end);
 576   fprintf (fp, "there are %u bytes free in %u chunks\n",
 577            i.fordblks, i.ordblks);
 578   fprintf (fp, "of which %u bytes are at the end of the reserved space\n",
 579            i.keepcost);
 580   fprintf (fp, "and %u bytes are in use.\n", i.uordblks);
 581 }
 582 #endif
 583
 584 #ifdef DEFINE_MALLOC_USABLE_SIZE
 585 size_t
 586 malloc_usable_size (void *block_p)
 587 {
 588   fle block = (fle)((size_t) block_p - offsetof (struct freelist_entry, next));
 589   return block->size - sizeof (size_t);
 590 }
 591 #endif
 592
 593 #ifdef DEFINE_MALLOPT
 594 int
 595 mallopt (int n, int v)
 596 {
 597   (void)n; (void)v;
 598   return 0;
 599 }
 600 #endif