Subversion Repositories Kolibri OS

Rev

Rev 7520 | Go to most recent revision | Blame | Last modification | View Log | Download | RSS feed

  1. /*
  2.  * Easy and fast memory allocator from
  3.  * https://wiki.osdev.org/Memory_Allocation
  4.  * Coded by Siemargl, 2018
  5.  *
  6.  * No Garbage Collector
  7.  */
  8.  
  9. #include <stddef.h>
  10. #include <stdint.h>
  11. #include <string.h>
  12. #include <assert.h>
  13. #include <stdlib.h>
  14.  
  15. #define UINT_MAX  (4294967295U)
  16.  
  17. #ifndef NDEBUG
  18. #include <stdio.h>
  19. #       ifdef __TINYC__
  20. #               include <kolibrisys.h>
  21. #               define TRACE1(s, a) { char buf[400]; sprintf(buf, s, a); debug_out_str(buf); }
  22. #               define TRACE2(s, a, b) { char buf[400]; sprintf(buf, s, a, b); debug_out_str(buf); }
  23. #       else
  24. #               define TRACE1(s, a) printf(s, a)
  25. #               define TRACE2(s, a, b) printf(s, a, b)
  26. #       endif
  27. #else
  28. #       define TRACE1(s, a) (void)0
  29. #       define TRACE2(s, a, b) (void)0
  30. #endif
  31.  
  32.  
  33.  
  34.  
  35. // get address, fromwhere function was called
  36. #define CALLEDFROM(param1) (*(int*)((char*)&param1-4)-5)
  37.    
  38. const uint32_t c_used = 0x44455355; //'USED'
  39. const uint32_t c_free = 0x45455246; //'FREE'
  40.  
  41. struct hdrfree {
  42.         uint32_t        mark; // 'FREE'
  43.         size_t          size; // including header
  44.         struct hdrfree  *prev;
  45.         struct hdrfree  *next;
  46. };
  47.  
  48. struct hdrused {
  49.         uint32_t        mark; // 'USED'
  50.         size_t          size;
  51. };
  52.  
  53.  
  54. static char *__freebase = NULL;         // begin of free area
  55. static char *__freetop = NULL;          // after last byte of free area
  56. static struct hdrfree *__firstfree = NULL;      // ptr to first node in dual-link list
  57.  
  58. static struct {
  59.         uint32_t        malloc_calls;
  60.         uint32_t        malloc_max;
  61.         uint32_t        malloc_sum;
  62.        
  63.         uint32_t        sysalloc_calls;
  64.         uint32_t        sysalloc_max;
  65.         uint32_t        sysalloc_sum;
  66.        
  67.         uint32_t        crtfreeblocks; // number of free blocks, checking corruptions
  68.         uint32_t        freeblocks_sum;
  69. } wtalloc_stat;
  70.  
  71.  
  72. void *wtmalloc(size_t sz)
  73. {
  74.         struct hdrfree *fndnode, *newnode;
  75.         sz = (sizeof(struct hdrused) + sz + 15) & ~15; // align 16bytes
  76. //TRACE1("_call alloc(%d)\n", sz);
  77.  
  78.         //statistics
  79.         wtalloc_stat.malloc_calls++;
  80.         if (sz > wtalloc_stat.malloc_max) wtalloc_stat.malloc_max = sz;
  81.         wtalloc_stat.malloc_sum += sz;
  82.        
  83.         // try to find free block enough size
  84.         fndnode = __firstfree;
  85.         while(fndnode)
  86.         {
  87. #ifndef NDEBUG
  88.                 if (fndnode->mark != c_free)
  89.                 {
  90.                         TRACE2("heap free block list corrupt %x  EIP@%x\n", fndnode, CALLEDFROM(sz));
  91.                         assert(0);
  92.                 }
  93. #endif
  94.                 if (fndnode->size >= sz) break;
  95.                 fndnode = fndnode->next;
  96.         }
  97.        
  98.         if (fndnode) // found free block
  99.         {
  100.                 if (fndnode->size - sz > 15) // split smaller size, move free node
  101.                 {
  102. //TRACE2("alloc(%d) split (%x)\n", sz, fndnode);
  103.                         wtalloc_stat.freeblocks_sum -= sz;
  104.                         newnode = (struct hdrfree*)((char*)fndnode + sz);
  105.                         newnode->mark = c_free;
  106.                         newnode->size = fndnode->size - sz;
  107.                         newnode->next = fndnode->next;
  108.                         newnode->prev = fndnode->prev;
  109.                        
  110.                         if (fndnode->next)
  111.                                 fndnode->next->prev = newnode;
  112.                        
  113.                         //перед может быть не нода, а 1й указатель
  114.                         if (fndnode->prev)
  115.                                 newnode->prev->next = newnode;
  116.                         else
  117.                                 __firstfree = newnode;
  118.                 } else // nothing to split, just exclude
  119.                 {
  120. //TRACE1("alloc(%d) remove freenode\n", sz);
  121.  
  122.                         wtalloc_stat.crtfreeblocks--;
  123.                         wtalloc_stat.freeblocks_sum -= fndnode->size;
  124.                         if (fndnode->next)
  125.                                 fndnode->next->prev = fndnode->prev;
  126.                         //перед может быть не нода, а 1й указатель
  127.                         if (fndnode->prev)
  128.                                 fndnode->prev->next = fndnode->next;
  129.                         else
  130.                                 __firstfree = fndnode->next;
  131.                 }
  132.                
  133.                 fndnode->mark = c_used;
  134.                 fndnode->size = sz;
  135.                 return (char*)fndnode + sizeof(struct hdrused);
  136.         }
  137.        
  138.         char *ptr;
  139.         // free block not found, try to add @end
  140.         if (__freetop - __freebase < sz)  // not enough memory - call system
  141.         {
  142.                 if (sz > UINT_MAX - 16) return NULL;  // check 32-bit heap overflow
  143. //              size_t new_heap_size = (__freetop - __freebase + sz + 4095) & ~4095;  
  144.                 size_t new_heap_size = (sz + sz / 5 + 4095) & ~4095;  // 20% reserved
  145.                
  146.                 //statistics
  147.                 wtalloc_stat.sysalloc_calls++;
  148.                 if (new_heap_size > wtalloc_stat.malloc_max) wtalloc_stat.sysalloc_max = new_heap_size;
  149.                 wtalloc_stat.sysalloc_sum += new_heap_size;
  150.  
  151.  
  152.                 //хвост сунуть в свободные, а фритоп и базу перености на новый кусок
  153.                 ptr = sysmalloc(new_heap_size);   // rounded 4k
  154. //TRACE2("call systemalloc(%d) returned %x\n", new_heap_size, ptr);
  155.                 if (!ptr)
  156.                 {
  157.                         TRACE2("sysmalloc failed trying to allocate %u bytes EIP@%x\n", sz, CALLEDFROM(sz));
  158.                         return NULL;
  159.                 }
  160.                 // add new free block in front of list
  161.                 if (__freetop - __freebase > 15)
  162.                 {
  163.                         newnode = (struct hdrfree*)__freebase;
  164.                         newnode->mark = c_free;
  165.                         newnode->size = __freetop - __freebase;
  166.                         newnode->next = __firstfree;
  167.                         newnode->prev = NULL;
  168.                         if (__firstfree)
  169.                                 __firstfree->prev = newnode;
  170.                         __firstfree = newnode;
  171.                         wtalloc_stat.crtfreeblocks++;
  172.                         wtalloc_stat.freeblocks_sum += newnode->size;
  173. //TRACE2("alloc(%d) add tail %d to freenode", sz, newnode->size);
  174. //TRACE1(".tail [%x]\n", newnode);
  175.                 }
  176.                 // we don't save allocated block from system, so cant free them ltr
  177.                
  178.                 __freebase = ptr;
  179.                 __freetop = __freebase + new_heap_size;
  180.         }
  181.        
  182.         ptr = __freebase + sizeof(struct hdrused);
  183.         ((struct hdrused*)__freebase)->mark = c_used;
  184.         ((struct hdrused*)__freebase)->size = sz;
  185.         __freebase += sz;
  186. //TRACE1("__freebase [%x]\n", __freebase);
  187.  
  188.  
  189. // check list availability
  190. /*
  191. int maxfree = 0;
  192. for (fndnode = __firstfree; fndnode; fndnode = fndnode->next)
  193. {
  194.         if (fndnode->size > maxfree) maxfree = fndnode->size;
  195. }
  196.  
  197. TRACE2("alloc(%d) from freebase, maxfree = %d,", sz, maxfree);
  198. TRACE1(" freelist len = %u \n", wtalloc_stat.crtfreeblocks);
  199. */     
  200.         return ptr;
  201. }
  202.  
  203. void wtfree(void *ptr)
  204. {
  205.         if (!ptr) return;
  206.  
  207. //TRACE1("free() to freenode, sized %d\n", ((struct hdrused*)((char*)ptr - 8))->size);
  208.  
  209. #ifndef NDEBUG
  210.         if (((struct hdrused*)((char*)ptr - 8))->mark != c_used)
  211.         {
  212.                 TRACE2("try free unallocated block ptr = %x bytes EIP@%x\n", ptr, CALLEDFROM(ptr));
  213.                 assert(0);
  214.         }
  215. #endif
  216.         struct hdrfree *newnode = (struct hdrfree*)((char*)ptr - 8);
  217.         newnode->mark = c_free;
  218.         //size stays
  219.         newnode->next = NULL;
  220.         newnode->prev = NULL;
  221.        
  222.  
  223.         // experimental - try to merge, if adjanced from bottom is also freeblock
  224.         int reorganized = 0;
  225.         struct hdrfree *higher;
  226.         {
  227.                 struct hdrfree *p1;
  228.                 higher = NULL;
  229.                 for (p1 = __firstfree; p1; p1 = p1->next)
  230.                 {
  231.                         higher = (struct hdrfree *)((char*)p1 + p1->size);
  232.                         if (higher == newnode) break;
  233.                 }
  234.                 if (p1) // yes, it is
  235.                 {
  236.                         wtalloc_stat.freeblocks_sum += newnode->size;
  237.                         p1->size += newnode->size;
  238.                         // p1->prev, p1->next  already OK
  239.                         newnode->mark = 0; // for safety
  240.                         newnode = p1;  // continue optimization
  241. //TRACE2("free block merged w/bottom sized %u bytes, list len %u\n", p1->size, wtalloc_stat.crtfreeblocks);
  242.                         reorganized = 1;
  243.                 }
  244.         }
  245.  
  246.  
  247. /* removed, as very seldom succeeds */
  248.         // experimental - try to merge, if adjanced from top is also freeblock
  249.         higher = (struct hdrfree *)((char*)newnode + newnode->size);
  250. // dont work - we try to read after our memory
  251. //      if ((char*)higher < (char*)__freetop &&   // saves from reading out of our memory
  252. //              higher->mark == c_free) // only suspisious, must be in list
  253.         {
  254.                 struct hdrfree *p1;
  255.                 for (p1 = __firstfree; p1 && p1 != higher; p1 = p1->next);
  256.                 if (p1) // yes, it is
  257.                 {
  258.                         if (newnode->next || newnode->prev)  // optimized 1st stage, must remove from list and readd later
  259.                         {
  260.                                 wtalloc_stat.crtfreeblocks--;
  261.                                 wtalloc_stat.freeblocks_sum -= newnode->size;
  262.                                 if (newnode->next)
  263.                                         newnode->next->prev = newnode->prev;
  264.                                 if (newnode->prev)
  265.                                         newnode->prev->next = newnode->next;
  266.                                 else
  267.                                         __firstfree = newnode->next;
  268.                         }
  269.                         wtalloc_stat.freeblocks_sum += newnode->size;
  270.                         newnode->size += higher->size;
  271.                         newnode->prev = higher->prev;
  272.                         newnode->next = higher->next;
  273.                         higher->mark = 0; // for safety
  274.                         if (higher->next)
  275.                                 higher->next->prev = newnode;
  276.                         if (higher->prev)
  277.                                 higher->prev->next = newnode;
  278.                         else
  279.                                 __firstfree = newnode;
  280. //TRACE1("free block merged w/top\n", 0);
  281.                         reorganized = 1;
  282.                 }
  283.         }
  284.  
  285.         if (reorganized) return;  // experimental reorganized do all work
  286.        
  287. //TRACE1("free block added\n", 0);
  288.         wtalloc_stat.crtfreeblocks++;
  289.         wtalloc_stat.freeblocks_sum += newnode->size;
  290.  
  291.         newnode->next = __firstfree;
  292.         newnode->prev = NULL;
  293.         if (__firstfree)
  294.                 __firstfree->prev = newnode;
  295.         __firstfree = newnode;
  296. }      
  297.  
  298.  
  299. void *wtrealloc(void *ptr, size_t sz)
  300. {
  301.         if (!ptr) return wtmalloc(sz);
  302.        
  303.         struct hdrused* oldptr = (struct hdrused*)((char*)ptr - 8);
  304.  
  305. #ifndef NDEBUG
  306.         if (oldptr->mark != c_used)
  307.         {
  308.                 TRACE2("try realloc unallocated block ptr = %x  EIP@%x\n", ptr, CALLEDFROM(ptr));
  309.                 assert(0);
  310.         }
  311. #endif
  312.  
  313.         if (oldptr->size - 8 >= sz) return ptr; // enough room in this block, ex from freelist
  314.        
  315.         /* experimental growth last block */
  316.         int growth = (oldptr->size + sz + 15) & ~15;
  317.         if ((char*)oldptr + oldptr->size == __freebase &&
  318.                 __freetop - __freebase + oldptr->size >= growth )  // we at top, can grow up
  319.         {
  320.                 wtalloc_stat.malloc_sum += growth - oldptr->size;
  321.                 __freebase += growth - oldptr->size;
  322.                 oldptr->size = growth;
  323.                 return ptr;
  324.         }
  325.        
  326.         void *newptr = wtmalloc(sz);
  327.         if (newptr)
  328.         {
  329.                 memcpy(newptr, (char*)oldptr +8, oldptr->size -8); // why forgeting -8 dont fail test?!?
  330.                 wtfree((char*)oldptr +8);
  331.                 return newptr;
  332.         }
  333.        
  334.         return NULL;
  335. }      
  336.  
  337. void* wtcalloc( size_t num, size_t size )
  338. {
  339.         void *newptr = wtmalloc(num * size);
  340.         if (newptr)
  341.                 memset(newptr, 0, num * size);
  342.         return newptr;
  343. }
  344.  
  345.  
  346.  
  347.  
  348. int wtmalloc_freelist_check()
  349. //контроль целостности списка фри OK == 1
  350. {
  351.         int cnt = 0;
  352.         struct hdrfree *ptr = __firstfree;
  353.        
  354.         if(ptr && ptr->prev)
  355.         {
  356.                 TRACE1("allocated memory freelist 1st block fail, ptr = %x\n", ptr);
  357.                 return 0;
  358.         }
  359.        
  360.         for(;ptr; ptr = ptr->next)
  361.         {
  362. //TRACE1("(%x)", ptr);
  363.  
  364.                 cnt++;
  365.                 if (ptr->mark != c_free)
  366.                 {
  367.                         TRACE1("allocated memory freelist check fail, ptr = %x\n", ptr);
  368.                         return 0;
  369.                 }
  370.         }
  371.         if (cnt != wtalloc_stat.crtfreeblocks)
  372.         {
  373.                 TRACE2("allocated memory freelist check fail, length must be = %u but is %u\n", wtalloc_stat.crtfreeblocks, cnt);
  374.                 return 0;
  375.         }
  376.         return 1;      
  377. }
  378.  
  379. void wtmalloc_freelist_print()
  380. {
  381.         struct hdrfree *ptr = __firstfree;
  382.         for(;ptr; ptr = ptr->next)
  383.         {
  384.                 TRACE2("(%x[%u])", ptr, ptr->size);
  385.         }
  386.         TRACE1("\n", 0);
  387.        
  388. }
  389.  
  390. int wtmalloc_poiner_check(void *ptr)
  391. //контроль указателя - mark  OK == 1
  392. {
  393.         if (((struct hdrused*)((char*)ptr - 8))->mark != c_used)
  394.         {
  395.                 TRACE2("pointer watermark check fail ptr = %x bytes EIP@%x\n", ptr, CALLEDFROM(ptr));
  396.                 return 0;
  397.         }
  398.         return 1;
  399. }
  400.  
  401. void wtdump_alloc_stats()
  402. {
  403.                 TRACE1("----Watermark allocator stats:----\n", 0);
  404.                 TRACE2("allocated %u calls, max of %u bytes\n", wtalloc_stat.malloc_calls, wtalloc_stat.malloc_max);
  405.                 TRACE2("total %u bytes, average call %u bytes\n", wtalloc_stat.malloc_sum, wtalloc_stat.malloc_sum / wtalloc_stat.malloc_calls);
  406.                 TRACE1("SYSTEM:\n", 0);
  407.                 TRACE2("allocated %u calls, max of %u bytes\n", wtalloc_stat.sysalloc_calls, wtalloc_stat.sysalloc_max);
  408.                 TRACE2("total %u bytes, average call %u bytes\n", wtalloc_stat.sysalloc_sum, wtalloc_stat.sysalloc_sum / wtalloc_stat.sysalloc_calls);
  409.                 TRACE2("free list %u bytes, length %u chunks\n", wtalloc_stat.freeblocks_sum, wtalloc_stat.crtfreeblocks);
  410. }
  411.