Advertisement
firdacz

Same-Size Allocator

Aug 28th, 2014
361
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //header:
  2. #ifndef __KER__SSA_H__
  3. #define __KER__SSA_H__
  4.  
  5. #include "defs.h"
  6. #include "inc/types.h"
  7.  
  8. typedef struct _ssapage ssapg_s;
  9. typedef struct _ssallocator ssa_s;
  10.  
  11. struct _ssapage
  12. {
  13.     ssapg_s * next, * prev;
  14.     void * free;
  15.     word used;
  16.     char data[0]; // reserved[first - 4 * 4], blocks[bpp][size];
  17. };
  18.  
  19. struct _ssallocator
  20. {
  21.     ssapg_s * other, * empty; // <other> serves also as lock
  22.     word size, bpp; // block size (in bytes), blocks per page
  23. };
  24.  
  25. #define ssa_locked(a)       ({ ssa_s * __a = (a); assert(__a); ptrlock_locked(& __a ->other); })
  26. #define ssa_lock(a)         ({ ssa_s * __a = (a); assert(__a); ptrlock_lock(& __a ->other); })
  27. #define ssa_trylock(a)      ({ ssa_s * __a = (a); assert(__a); ptrlock_trylock(& __a ->other); })
  28. #define ssa_unlock(a)       ({ ssa_s * __a = (a); assert(__a); ptrlock_unlock(& __a ->other); })
  29.  
  30. // allocate block
  31. extern void * ssa_alloc(ssa_s * a);
  32.  
  33. // release block
  34. extern void ssa_free(ssa_s * a, void * b);
  35.  
  36. extern ssa_s ssa16w;
  37. #define alloc16w()          ssa_alloc(& ssa16w)
  38. #define free16w(b)          ssa_free(& ssa16w, b)
  39.  
  40. extern ssa_s ssa3w;
  41. #define alloc3w()           ssa_alloc(& ssa3w)
  42. #define free3w(b)           ssa_free(& ssa3w, b)
  43.  
  44. #endif
  45.  
  46. //source:
  47. #include "out.h"
  48. #include "ssa.h"
  49. #include "page.h"
  50. #include "inc/sl.h"
  51.  
  52. ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  53. // same-size-allocators
  54. ssa_s ssa16w = {
  55.     other:  nil,
  56.     empty:  nil,
  57.     size:   16 * sizeof(word),
  58.     bpp:    (BYTES_PER_PAGE - sizeof(ssapg_s)) / (16 * sizeof(word))
  59. };
  60. ssa_s ssa3w = {
  61.     other:  nil,
  62.     empty:  nil,
  63.     size:   3 * sizeof(word),
  64.     bpp:    (BYTES_PER_PAGE - sizeof(ssapg_s)) / (3 * sizeof(word))
  65. };
  66.  
  67. ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  68. // allocate block
  69. void * ssa_alloc(ssa_s * a)
  70. {
  71.     ssapg_s * pg;
  72.  
  73.     ssa_lock(a);
  74.     if ((pg = a ->other))
  75.     {// we have some non-full-non-empty page
  76.        
  77.         void * b, * next;
  78.        
  79.         assert(pg ->prev == (ssapg_s *) & a ->other && pg ->used > 0 && pg ->used < a ->bpp);
  80.        
  81.     //  use the empty slot
  82.         pg ->free = next = * (void **) (b = pg ->free);
  83.         ++ pg ->used;
  84.        
  85.         if (! next)
  86.         {// the page was used up
  87.            
  88.             ssapg_s * next;
  89.  
  90.             assert(pg ->used == a ->bpp);
  91.            
  92.         //  remove it from the list
  93.             a ->other = next = pg ->next;
  94.             if (next) next ->prev = (ssapg_s *) & a ->other;
  95.         }
  96.        
  97.         ssa_unlock(a);
  98.         return b;
  99.     }
  100.     else if ((pg = a ->empty))
  101.     {// we have an empty page
  102.        
  103.         void * b;
  104.         ssapg_s * next;
  105.  
  106.         assert(pg ->used == 0 && pg ->free);
  107.  
  108.     //  use the empty slot
  109.         pg ->free = * (void **) (b = pg ->free);
  110.         pg ->used = 1;
  111.  
  112.     //  move the page from the list of empty pages ...
  113.         a ->empty = pg ->next;
  114.  
  115.     //  ... to the list of non-full-non-empty pages
  116.         if ((next = a ->other)) next ->prev = pg;
  117.         a ->other = pg;
  118.         pg ->next = next;
  119.         pg ->prev = (ssapg_s *) & a ->other;
  120.        
  121.         ssa_unlock(a);
  122.         return b;
  123.     }
  124.     else
  125.     {// allocate and use new page
  126.  
  127.         char * b, * stop, * next;
  128.         unsigned size;
  129.        
  130.     //  allocate new page
  131.         if (! (pg = pgalloc()))
  132.             goto error;
  133.        
  134.     //  add the page to the list of non-full-non-empty pages
  135.         assert(! a ->other);
  136.         a ->other = pg;
  137.         pg ->next = nil;
  138.         pg ->prev = (ssapg_s *) & a ->other;
  139.        
  140.     //  format the page
  141.         pg ->used = 1;
  142.         stop = ((char *) (pg + 1)) + (size = a ->size);
  143.         b = ((char *) pg) + BYTES_PER_PAGE;
  144.         next = nil;
  145.         for (;;)
  146.         {
  147.             b -= size;
  148.             if (b < stop)
  149.                 break;
  150.             * (void **) b = next;
  151.             next = b;
  152.         }
  153.         pg ->free = next;
  154.        
  155.         ssa_unlock(a);
  156.         return b;
  157.     }
  158.  
  159.     assert(0);
  160.  
  161. error:
  162.     assert2(0, (
  163.         outs("desc: could not allocate block"),
  164.         outs("\nallocator:       "), outp(a),
  165.         outs("\nblock size:      "), outi(a ->size), outs(" bytes ("), outi(a ->size / 4), outs(" words)"),
  166.         outs("\nblocks per page: "), outi(a ->bpp),
  167.         outnl()
  168.     ));
  169.     ssa_unlock(a);
  170.     return nil;
  171. }
  172.  
  173. ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  174. // release block
  175. void ssa_free(ssa_s * a, void * b)
  176. {
  177.     ssapg_s * pg = page_from_pointer(b);
  178.    
  179.     ssa_lock(a);
  180.     if (pg ->free)
  181.     {// the page is not full
  182.        
  183.         assert(pg ->used > 0 && pg ->used < a ->bpp);
  184.        
  185.         * (void **) b = pg ->free;
  186.         pg ->free = b;
  187.        
  188.         if (! -- pg ->used)
  189.         {// the page is now empty
  190.  
  191.             ssapg_s * next, * prev;
  192.            
  193.         //  move it from the list of non-full-non-empty pages ...
  194.             (prev = pg ->prev) ->next = next = pg ->next;
  195.             if (next) next ->prev = prev;
  196.  
  197.         //  ... to the list of empty pages
  198.             pg ->next = a ->empty;
  199.             a ->empty = pg;
  200.         }
  201.     }
  202.     else
  203.     {// the page is now full
  204.  
  205.         ssapg_s * next;
  206.        
  207.         assert(pg ->used == a ->bpp);
  208.        
  209.         -- pg ->used;
  210.         * (void **) b = nil;
  211.         pg ->free = b;
  212.        
  213.     // add it to the list of non-full-non-empty pages
  214.         pg ->next = next = a ->other;
  215.         pg ->prev = (ssapg_s *) a ->other;
  216.         a ->other = pg;
  217.         if (next) next ->prev = pg;
  218.     }
  219.     ssa_unlock(a);
  220. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement