newlib/libc/machine/xstormy16/tiny-malloc.c

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