Subversion Repositories Kolibri OS

Rev

Rev 5129 | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. /* Copyright (C) 1999 DJ Delorie, see COPYING.DJ for details */
  2. /* Copyright (C) 1998 DJ Delorie, see COPYING.DJ for details */
  3. /* Copyright (C) 1997 DJ Delorie, see COPYING.DJ for details */
  4.  
  5. #include <stdlib.h>
  6. #include <string.h>
  7. #include <unistd.h>
  8.  
  9. typedef struct BLOCK {
  10.   size_t size;
  11.   struct BLOCK *next;
  12.   int bucket;
  13. } BLOCK;
  14.  
  15. #define BEFORE(bp)      ((BLOCK *)((char *)bp - *(int *)((char *)bp - 4) - 8))
  16. #define BEFSZ(bp)       (*(size_t *)((char *)bp - 4))
  17. #define ENDSZ(bp)       (*(size_t *)((char *)bp + bp->size + 4))
  18. #define AFTER(bp)       ((BLOCK *)((char *)bp + bp->size + 8))
  19. #define DATA(bp)        ((char *)&(bp->next))
  20.  
  21. #define NUMSMALL        0
  22. #define ALIGN           8
  23. #define SMALL           (NUMSMALL*ALIGN)
  24.  
  25. static int malloc_mutex = 0;
  26.  
  27. static BLOCK *slop = 0;
  28. static BLOCK *freelist[30];
  29. #if NUMSMALL
  30. static BLOCK *smallblocks[NUMSMALL];
  31. #endif
  32.  
  33. static inline void malloc_lock(void)
  34. {
  35.   while (__sync_lock_test_and_set(&malloc_mutex, 1))
  36.     __menuet__delay100(1);
  37. }
  38.  
  39. static inline void malloc_unlock(void)
  40. {
  41.   __sync_lock_release(&malloc_mutex);
  42. }
  43.  
  44. #define MIN_SAVE_EXTRA  64
  45. #define BIG_BLOCK       4096
  46.  
  47. #define DEBUG 0
  48.  
  49. #if DEBUG
  50. static void
  51. check(BLOCK *b)
  52. {
  53.   printf("check %08x %d %08x %d\n", b, b->size, &(ENDSZ(b)), ENDSZ(b));
  54. }
  55. #define CHECK(p) do { check(p); assert(p->size == ENDSZ(p)); consistency(); } while (0)
  56. #define CHECK1(p) do { check(p); assert(p->size == ENDSZ(p)); } while (0)
  57. static void
  58. consistency()
  59. {
  60. #if 0
  61.   int b;
  62.   BLOCK *bl;
  63.   if (slop)
  64.     CHECK1(slop);
  65.   for (b=0; b<32; b++)
  66.     for (bl=freelist[b]; bl; bl=bl->next)
  67.       CHECK1(bl);
  68. #endif
  69. }
  70. #else
  71. #define CHECK(p)
  72. #endif
  73.  
  74. static inline int
  75. size2bucket(size_t size)
  76. {
  77.   int rv=0;
  78.   size>>=2;
  79.   while (size)
  80.   {
  81.     rv++;
  82.     size>>=1;
  83.   }
  84.   return rv;
  85. }
  86.  
  87. static inline int
  88. b2bucket(BLOCK *b)
  89. {
  90.   if (b->bucket == -1)
  91.     b->bucket = size2bucket(b->size);
  92.   return b->bucket;
  93. }
  94.  
  95. static inline BLOCK *
  96. split_block(BLOCK *b, size_t size)
  97. {
  98.   BLOCK *rv = (BLOCK *)((char *)b + size+8);
  99. #if DEBUG
  100.   printf("  split %u/%08x to %u/%08x, %u/%08x\n",
  101.          b->size, b, size, b, b->size - size - 8, rv);
  102. #endif
  103.   rv->size = b->size - size - 8;
  104.   rv->bucket = -1;
  105.   b->size = size;
  106.   ENDSZ(b) = b->size;
  107.   ENDSZ(rv) = rv->size;
  108.   CHECK(b);
  109.   CHECK(rv);
  110.   return rv;
  111. }
  112.  
  113. #define RET(rv) CHECK(rv); ENDSZ(rv) |= 1; rv->size |= 1; malloc_unlock(); return DATA(rv)
  114.  
  115. void * malloc(size_t size)
  116. {
  117.   int b, chunk_size;
  118.   BLOCK *rv, **prev;
  119.   static BLOCK *expected_sbrk = 0;
  120.  
  121.   if (size<ALIGN) size = ALIGN;
  122.   size = (size+(ALIGN-1))&~(ALIGN-1);
  123. #if DEBUG
  124.   printf("malloc(%u)\n", size);
  125. #endif
  126.  
  127.   malloc_lock();
  128.  
  129. #if NUMSMALL
  130.   if (size < SMALL)
  131.   {
  132.     rv = smallblocks[size/ALIGN];
  133.     if (rv)
  134.     {
  135.       smallblocks[size/ALIGN] = rv->next;
  136.       malloc_unlock();
  137.       return DATA(rv);
  138.     }
  139.   }
  140. #endif
  141.  
  142.   if (slop && slop->size >= size)
  143.   {
  144.     rv = slop;
  145. #if DEBUG
  146.     printf("  using slop %u/%08x\n", slop->size, slop);
  147. #endif
  148.     if (slop->size >= size+MIN_SAVE_EXTRA)
  149.     {
  150.       slop = split_block(slop, size);
  151. #if DEBUG
  152.       printf("  remaining slop %u/%08x\n", slop->size, slop);
  153. #endif
  154.     }
  155.     else
  156.       slop = 0;
  157.     RET(rv);
  158.   }
  159.  
  160.   b = size2bucket(size);
  161.   prev = &(freelist[b]);
  162.   for (rv=freelist[b]; rv; prev=&(rv->next), rv=rv->next)
  163.   {
  164.     if (rv->size >= size && rv->size < size+size/4)
  165.     {
  166.       *prev = rv->next;
  167.       RET(rv);
  168.     }
  169.   }
  170.  
  171.   while (b < 30)
  172.   {
  173.     prev = &(freelist[b]);
  174. #if DEBUG
  175.     printf("  checking bucket %d\n", b);
  176. #endif
  177.     for (rv=freelist[b]; rv; prev=&(rv->next), rv=rv->next)
  178.       if (rv->size >= size)
  179.       {
  180. #if DEBUG
  181.         printf("    found size %d/%08x\n", rv->size, rv);
  182. #endif
  183.         *prev = rv->next;
  184.         if (rv->size >= size+MIN_SAVE_EXTRA)
  185.         {
  186. #if DEBUG
  187.           printf("    enough to save\n");
  188. #endif
  189.           if (slop)
  190.           {
  191.             b = b2bucket(slop);
  192. #if DEBUG
  193.             printf("    putting old slop %u/%08x on free list %d\n",
  194.                    slop->size, slop, b);
  195. #endif
  196.             slop->next = freelist[b];
  197.             freelist[b] = slop;
  198.           }
  199.           slop = split_block(rv, size);
  200. #if DEBUG
  201.           printf("    slop size %u/%08x\n", slop->size, slop);
  202. #endif
  203.         }
  204.         RET(rv);
  205.       }
  206.     b++;
  207.   }
  208.  
  209.   chunk_size = size+16; /* two ends plus two placeholders */
  210.   rv = (BLOCK *)sbrk(chunk_size);
  211.   if (rv == (BLOCK *)(-1)) {
  212.     malloc_unlock();
  213.     return 0;
  214.   }
  215. #if DEBUG
  216.   printf("sbrk(%d) -> %08x, expected %08x\n", chunk_size, rv, expected_sbrk);
  217. #endif
  218.   if (rv == expected_sbrk)
  219.   {
  220.     expected_sbrk = (BLOCK *)((char *)rv + chunk_size);
  221.     /* absorb old end-block-marker */
  222. #if DEBUG
  223.     printf("  got expected sbrk\n");
  224. #endif
  225.     rv = (BLOCK *)((char *)rv - 4);
  226.   }
  227.   else
  228.   {
  229.     expected_sbrk = (BLOCK *)((char *)rv + chunk_size);
  230. #if DEBUG
  231.     printf("    disconnected sbrk\n");
  232. #endif
  233.     /* build start-block-marker */
  234.     rv->size = 1;
  235.     rv = (BLOCK *)((char *)rv + 4);
  236.     chunk_size -= 8;
  237.   }
  238.   rv->size = chunk_size - 8;
  239.   ENDSZ(rv) = rv->size;
  240.   AFTER(rv)->size = 1;
  241.   CHECK(rv);
  242.  
  243.   RET(rv);
  244. }
  245.  
  246. static inline BLOCK *
  247. merge(BLOCK *a, BLOCK *b, BLOCK *c)
  248. {
  249.   int bu;
  250.   BLOCK *bp, **bpp;
  251.  
  252. #if DEBUG
  253.   printf("  merge %u/%08x + %u/%08x = %u\n",
  254.          a->size, a, b->size, b, a->size+b->size+8);
  255. #endif
  256.  
  257.   CHECK(a);
  258.   CHECK(b);
  259.   CHECK(c);
  260.   if (c == slop)
  261.   {
  262. #if DEBUG
  263.     printf("  snipping slop %u/%08x\n", slop->size, slop);
  264. #endif
  265.     slop = 0;
  266.   }
  267.   bu = b2bucket(c);
  268. #if DEBUG
  269.   printf("bucket for %u/%08x is %d\n", c->size, c, bu);
  270. #endif
  271.   bpp = freelist+bu;
  272.   for (bp=freelist[bu]; bp; bpp=&(bp->next), bp=bp->next)
  273.   {
  274. #if DEBUG
  275.     printf("  %08x", bp);
  276. #endif
  277.     if (bp == c)
  278.     {
  279. #if DEBUG
  280.       printf("\n  snipping %u/%08x from freelist[%d]\n", bp->size, bp, bu);
  281. #endif
  282.       *bpp = bp->next;
  283.       break;
  284.     }
  285.   }
  286.   CHECK(c);
  287.  
  288.   a->size += b->size + 8;
  289.   a->bucket = -1;
  290.   ENDSZ(a) = a->size;
  291.  
  292.   CHECK(a);
  293.   return a;
  294. }
  295.  
  296. void
  297. free(void *ptr)
  298. {
  299.   int b;
  300.   BLOCK *block;
  301.   if (ptr == 0)
  302.     return;
  303.   block = (BLOCK *)((char *)ptr-4);
  304.  
  305.   malloc_lock();
  306.  
  307. #if NUMSMALL
  308.   if (block->size < SMALL)
  309.   {
  310.     block->next = smallblocks[block->size/ALIGN];
  311.     smallblocks[block->size/ALIGN] = block;
  312.     malloc_unlock();
  313.     return;
  314.   }
  315. #endif
  316.  
  317.   block->size &= ~1;
  318.   ENDSZ(block) &= ~1;
  319.   block->bucket = -1;
  320. #if DEBUG
  321.   printf("free(%u/%08x)\n", block->size, block);
  322. #endif
  323.  
  324.   CHECK(block);
  325.   if (! (AFTER(block)->size & 1))
  326.   {
  327.     CHECK(AFTER(block));
  328.   }
  329.   if (! (BEFSZ(block) & 1))
  330.   {
  331.     CHECK(BEFORE(block));
  332.     block = merge(BEFORE(block), block, BEFORE(block));
  333.   }
  334.   CHECK(block);
  335.   if (! (AFTER(block)->size & 1))
  336.   {
  337.     CHECK(AFTER(block));
  338.     block = merge(block, AFTER(block), AFTER(block));
  339.   }
  340.   CHECK(block);
  341.  
  342.   b = b2bucket(block);
  343.   block->next = freelist[b];
  344.   freelist[b] = block;
  345.   CHECK(block);
  346.   malloc_unlock();
  347. }
  348.  
  349. void * realloc(void *ptr, size_t size)
  350. {
  351.  BLOCK *b;
  352.  char *newptr;
  353.  size_t copysize;
  354.  if (ptr == 0) return malloc(size);
  355.  b = (BLOCK *)((char *)ptr-4);
  356.  copysize = b->size & ~1;
  357.  if (size <= copysize)
  358.  {
  359.   return ptr;
  360.   copysize = size;
  361.  }
  362.  newptr = (char *)malloc(size);
  363.  if (!newptr) return NULL;
  364.  memcpy(newptr, ptr, copysize);
  365.  free(ptr);
  366.  return newptr;
  367. }
  368.