Subversion Repositories Kolibri OS

Rev

Go to most recent revision | 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. #include <menuet/sem.h>
  9.  
  10. typedef struct BLOCK {
  11.   size_t size;
  12.   struct BLOCK *next;
  13.   int bucket;
  14. } BLOCK;
  15.  
  16. #define BEFORE(bp)      ((BLOCK *)((char *)bp - *(int *)((char *)bp - 4) - 8))
  17. #define BEFSZ(bp)       (*(size_t *)((char *)bp - 4))
  18. #define ENDSZ(bp)       (*(size_t *)((char *)bp + bp->size + 4))
  19. #define AFTER(bp)       ((BLOCK *)((char *)bp + bp->size + 8))
  20. #define DATA(bp)        ((char *)&(bp->next))
  21.  
  22. #define NUMSMALL        0
  23. #define ALIGN           8
  24. #define SMALL           (NUMSMALL*ALIGN)
  25.  
  26. DECLARE_STATIC_SEM(malloc_mutex)
  27.  
  28. static BLOCK *slop = 0;
  29. static BLOCK *freelist[30];
  30. #if NUMSMALL
  31. static BLOCK *smallblocks[NUMSMALL];
  32. #endif
  33.  
  34. static inline void malloc_lock(void)
  35. {
  36.  sem_lock(&malloc_mutex);
  37. }
  38.  
  39. static inline void malloc_unlock(void)
  40. {
  41.  sem_unlock(&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; 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. #if NUMSMALL
  128.   if (size < SMALL)
  129.   {
  130.     rv = smallblocks[size/ALIGN];
  131.     if (rv)
  132.     {
  133.       smallblocks[size/ALIGN] = rv->next;
  134.       return DATA(rv);
  135.     }
  136.   }
  137. #endif
  138.  
  139.   if (slop && slop->size >= size)
  140.   {
  141.     rv = slop;
  142. #if DEBUG
  143.     printf("  using slop %u/%08x\n", slop->size, slop);
  144. #endif
  145.     if (slop->size >= size+MIN_SAVE_EXTRA)
  146.     {
  147.       slop = split_block(slop, size);
  148. #if DEBUG
  149.       printf("  remaining slop %u/%08x\n", slop->size, slop);
  150. #endif
  151.     }
  152.     else
  153.       slop = 0;
  154.     RET(rv);
  155.   }
  156.  
  157.   b = size2bucket(size);
  158.   prev = &(freelist[b]);
  159.   for (rv=freelist[b]; rv; prev=&(rv->next), rv=rv->next)
  160.   {
  161.     if (rv->size >= size && rv->size < size+size/4)
  162.     {
  163.       *prev = rv->next;
  164.       RET(rv);
  165.     }
  166.   }
  167.  
  168.   while (b < 30)
  169.   {
  170.     prev = &(freelist[b]);
  171. #if DEBUG
  172.     printf("  checking bucket %d\n", b);
  173. #endif
  174.     for (rv=freelist[b]; rv; prev=&(rv->next), rv=rv->next)
  175.       if (rv->size >= size)
  176.       {
  177. #if DEBUG
  178.         printf("    found size %d/%08x\n", rv->size, rv);
  179. #endif
  180.         *prev = rv->next;
  181.         if (rv->size >= size+MIN_SAVE_EXTRA)
  182.         {
  183. #if DEBUG
  184.           printf("    enough to save\n");
  185. #endif
  186.           if (slop)
  187.           {
  188.             b = b2bucket(slop);
  189. #if DEBUG
  190.             printf("    putting old slop %u/%08x on free list %d\n",
  191.                    slop->size, slop, b);
  192. #endif
  193.             slop->next = freelist[b];
  194.             freelist[b] = slop;
  195.           }
  196.           slop = split_block(rv, size);
  197. #if DEBUG
  198.           printf("    slop size %u/%08x\n", slop->size, slop);
  199. #endif
  200.         }
  201.         RET(rv);
  202.       }
  203.     b++;
  204.   }
  205.  
  206.   chunk_size = size+16; /* two ends plus two placeholders */
  207.   rv = (BLOCK *)sbrk(chunk_size);
  208.   if (rv == (BLOCK *)(-1))
  209.     return 0;
  210. #if DEBUG
  211.   printf("sbrk(%d) -> %08x, expected %08x\n", chunk_size, rv, expected_sbrk);
  212. #endif
  213.   if (rv == expected_sbrk)
  214.   {
  215.     expected_sbrk = (BLOCK *)((char *)rv + chunk_size);
  216.     /* absorb old end-block-marker */
  217. #if DEBUG
  218.     printf("  got expected sbrk\n");
  219. #endif
  220.     rv = (BLOCK *)((char *)rv - 4);
  221.   }
  222.   else
  223.   {
  224.     expected_sbrk = (BLOCK *)((char *)rv + chunk_size);
  225. #if DEBUG
  226.     printf("    disconnected sbrk\n");
  227. #endif
  228.     /* build start-block-marker */
  229.     rv->size = 1;
  230.     rv = (BLOCK *)((char *)rv + 4);
  231.     chunk_size -= 8;
  232.   }
  233.   rv->size = chunk_size - 8;
  234.   ENDSZ(rv) = rv->size;
  235.   AFTER(rv)->size = 1;
  236.   CHECK(rv);
  237.  
  238.   RET(rv);
  239. }
  240.  
  241. static inline BLOCK *
  242. merge(BLOCK *a, BLOCK *b, BLOCK *c)
  243. {
  244.   int bu;
  245.   BLOCK *bp, **bpp;
  246.  
  247. #if DEBUG
  248.   printf("  merge %u/%08x + %u/%08x = %u\n",
  249.          a->size, a, b->size, b, a->size+b->size+8);
  250. #endif
  251.  
  252.   CHECK(a);
  253.   CHECK(b);
  254.   CHECK(c);
  255.   if (c == slop)
  256.   {
  257. #if DEBUG
  258.     printf("  snipping slop %u/%08x\n", slop->size, slop);
  259. #endif
  260.     slop = 0;
  261.   }
  262.   bu = b2bucket(c);
  263. #if DEBUG
  264.   printf("bucket for %u/%08x is %d\n", c->size, c, bu);
  265. #endif
  266.   bpp = freelist+bu;
  267.   for (bp=freelist[bu]; bp; bpp=&(bp->next), bp=bp->next)
  268.   {
  269. #if DEBUG
  270.     printf("  %08x", bp);
  271. #endif
  272.     if (bp == c)
  273.     {
  274. #if DEBUG
  275.       printf("\n  snipping %u/%08x from freelist[%d]\n", bp->size, bp, bu);
  276. #endif
  277.       *bpp = bp->next;
  278.       break;
  279.     }
  280.   }
  281.   CHECK(c);
  282.  
  283.   a->size += b->size + 8;
  284.   a->bucket = -1;
  285.   ENDSZ(a) = a->size;
  286.  
  287.   CHECK(a);
  288.   return a;
  289. }
  290.  
  291. void
  292. free(void *ptr)
  293. {
  294.   int b;
  295.   BLOCK *block;
  296.   if (ptr == 0)
  297.     return;
  298.   block = (BLOCK *)((char *)ptr-4);
  299.  
  300. #if NUMSMALL
  301.   if (block->size < SMALL)
  302.   {
  303.     block->next = smallblocks[block->size/ALIGN];
  304.     smallblocks[block->size/ALIGN] = block;
  305.     return;
  306.   }
  307. #endif
  308.  
  309.   block->size &= ~1;
  310.   ENDSZ(block) &= ~1;
  311.   block->bucket = -1;
  312. #if DEBUG
  313.   printf("free(%u/%08x)\n", block->size, block);
  314. #endif
  315.  
  316.   CHECK(block);
  317.   if (! (AFTER(block)->size & 1))
  318.   {
  319.     CHECK(AFTER(block));
  320.   }
  321.   if (! (BEFSZ(block) & 1))
  322.   {
  323.     CHECK(BEFORE(block));
  324.     block = merge(BEFORE(block), block, BEFORE(block));
  325.   }
  326.   CHECK(block);
  327.   if (! (AFTER(block)->size & 1))
  328.   {
  329.     CHECK(AFTER(block));
  330.     block = merge(block, AFTER(block), AFTER(block));
  331.   }
  332.   CHECK(block);
  333.  
  334.   b = b2bucket(block);
  335.   block->next = freelist[b];
  336.   freelist[b] = block;
  337.   CHECK(block);
  338. }
  339.  
  340. void * realloc(void *ptr, size_t size)
  341. {
  342.  BLOCK *b;
  343.  char *newptr;
  344.  size_t copysize;
  345.  if (ptr == 0) return malloc(size);
  346.  b = (BLOCK *)((char *)ptr-4);
  347.  copysize = b->size & ~1;
  348.  if (size <= copysize)
  349.  {
  350.   return ptr;
  351.   copysize = size;
  352.  }
  353.  newptr = (char *)malloc(size);
  354.  if (!newptr) return NULL;
  355.  memcpy(newptr, ptr, copysize);
  356.  free(ptr);
  357.  return newptr;
  358. }
  359.