resources/slob.cpp

   1 /* Simple List of Blocks allocator
   2  * Based on the SLOB allocator introduced to Linux kernel by M. Mackall.
   3  *
   4  * M. Mackall: slob: introduce the SLOB allocator, Linux Kernel Mailing List,
   5  * 2005, http://lkml.org/lkml/2005/11/1/230
   6  */
   7
   8 #include "slob.h"
   9 #include "manes/manec.h"
  10
  11 using namespace resources;
  12
  13 slob::slob() {
  14         physical = manes::manec::get()->get<physmem>("/physmem");
  15         first_block = (unit*)physical->allocate_space(0x1000);
  16         first_block->size = 0x1000;
  17         first_block->next = (unit*)0;
  18 }
  19
  20 void *slob::allocate_space(unsigned int size) {
  21         unit *before = 0;
  22         unit *current = first_block;
  23
  24         if (size < sizeof(unit))
  25                 size = sizeof(unit);
  26
  27         size += sizeof(unit);
  28         size = (size / sizeof(unit) + 1) * sizeof(unit);
  29
  30         if (size >= 0x1000) {
  31                 void *first_page = physical->allocate_space(PAGE_SHIFT + 1);
  32                 for (int i = size - PAGE_SIZE; i > 0; i -= PAGE_SIZE)
  33                         physical->allocate_space(PAGE_SHIFT + 1);
  34                 return first_page;
  35         }
  36
  37         while (current->size < size) {
  38                 if (!current->next)  {
  39                         current->next = (unit*)physical->allocate_space(0x1000);
  40                         current->next->size = 0x1000;
  41                         current->next->next = (unit*)0;
  42                 }
  43
  44                 before = current;
  45                 current = current->next;
  46         }
  47
  48         unit *new_unit;
  49
  50         if (current->size > size) {
  51                 new_unit = (unit*)((int)current + size);
  52
  53                 new_unit->size = current->size - size;
  54                 new_unit->next = current->next;
  55
  56         } else
  57                 new_unit = current->next;
  58
  59         if (before)
  60                 before->next = new_unit;
  61         else
  62                 first_block = new_unit;
  63
  64         current->size = size;
  65         current->next = 0;
  66
  67         return (void*)&current[1];
  68 }
  69
  70 void slob::deallocate_space(void *ptr) {
  71         if (((unsigned int)ptr & 0xffff) == 0)
  72                 return;
  73
  74         unit *dealloc = (unit*)((int)ptr - sizeof(unit));
  75
  76         if (!merge(dealloc)) {
  77                 dealloc->next = first_block;
  78                 first_block = dealloc;
  79         }
  80 }
  81
  82 unsigned int slob::get_size(void *ptr) const {
  83         unit *dealloc = (unit*)((int)ptr - sizeof(unit));
  84
  85         return dealloc->size;
  86 }
  87
  88 bool slob::merge(unit *ptr) {
  89         unit *current = first_block;
  90         unit *before = (unit*)0;
  91
  92         bool action = false;
  93
  94         do {
  95                 if ((unsigned int)current + current->size == (unsigned int)ptr) {
  96                         current->size += ptr->size;
  97
  98                         ptr = current;
  99                         action = true;
 100
 101                 } else if ((unsigned int)ptr + ptr->size == (unsigned int)current) {
 102                         before->next = ptr;
 103                         ptr->next = current->next;
 104                         ptr->size += current->size;
 105
 106                         current = ptr;
 107                         if (!before)
 108                                 first_block = ptr;
 109
 110                         action = true;
 111                 }
 112
 113                 before = current;
 114                 current = current->next;
 115         } while (current);
 116
 117         return action;
 118 }
 119
 120
 121 void slob::register_type() {
 122         manes::manec::get()->register_type<slob>("slob", "allocator");
 123 }