root/core/suba.c

DEFINITIONS

1. check_cell
2. suba_dump
3. check_stats
4. suba_dump
5. check_stats
6. suba_getmeminfo
7. suba_init
8. suba_alloc
9. suba_free

   1 /* 
   2 
   3 SUBA.C
   4 
   5 Based on suba - sub-allocate memory from larger chunk of memory
   6  * Copyright (c) 2003 Michael B. Allen <mba2000 ioplex.com>
   7  *
   8  * The MIT License
   9  * 
  10 */
  12 // Rewritten for CHDK.
  14 #include "stdlib.h"
  15 #include "stddef.h"
  16 #include "string.h"
  17 #include "semaphore.h"
  19 #define SUBA_SEMAPHORE_TIMEOUT  1000
  20 #define SANITY_CHECKS           1
  22 #define SUBA_MAGIC 0x53554241
  23 #define CELL_MAGIC 0x5342434C
  25 // Free list cell header
  26 typedef struct {
  27     unsigned int    magic;      // cell check value
size_t          size;
  29 } cell_hdr;
  31 // Free list cell
  32 typedef struct _cell {
cell_hdr        h;
  34     struct _cell*   next;       // link to next cell in free list
  35 } cell;
  37 // Memory allocator
  38 typedef struct {
  39         unsigned int    magic;      // suba header identifier
  40         unsigned int*   magic2;     // guard value at the end of the block
size_t          size;       // total size of memory area
  42         int             sem_id;     // Canon semaphore id
cell            head;       // List header
size_t          mincell;    // min cell size must be at least sizeof cell
  46     // CHDK added counters, modeled on DryOS values
  47     int free_block_count;       // Length of free list
  48     int free_size;              // Available memory in free list
cell* largest_block;        // Largest block on free list
size_t allocated_count;     // total number of current allocations
size_t allocated_size;      // total amount of memory currently allocated, excluding overhead
size_t allocated_peak;      // maximum value of allocated_size encountered
  53 } allocator;
  55 // Cell / Pointer manipulation macros
  56 #define ALIGNMASK           (sizeof(cell*)-1)
  57 #define ALIGN(s)            (((s) + ALIGNMASK) & ~ALIGNMASK)
  59 #define ACTUALSIZE(size)    (size + sizeof(cell_hdr))
  60 #define ALLOCSIZE(size)     (size - sizeof(cell_hdr))
  61 #define CELL2ALLOC(c)       (void*)((void*)c + sizeof(cell_hdr))
  62 #define ALLOC2CELL(p)       (cell*)((void*)p - sizeof(cell_hdr))
  64 #define CEND(c)             ((cell*)((char*)c + c->h.size))
  65 #define ISADJ(c1,c2)        (CEND(c1) == (c2))
  67 #if SANITY_CHECKS
  68 static cell*
check_cell(const allocator *suba, cell* c, char *fn, int ln)
  70 {
  71     if (suba && (c > (cell*)suba) && (c < (cell*)((char*)suba + suba->size))) {
  72         if (c->h.magic != CELL_MAGIC)
DebugAssert("Corrupt cell header", ln);
  74         return c;
  75     }
  76     char buf[200];
sprintf(buf, "%s bad cell - %x %x", fn, c, suba);
DebugAssert(buf, ln);
  79     return NULL;
  80 }
  81 #else
  82 #define check_cell(s, c, f, l) (c)
  83 #endif
  85 #ifdef SUBA_HOST_DEBUG
  86 // For testing on host (not in CHDK). Print free list to stdout.
  87 void suba_dump(allocator *suba)
  88 {
cell *c = &suba->head;
printf("%x %d => ", c, suba->mincell);
  91     while (c->h.size != 0)
  92     {
printf("%x %d %x, ", c, c->h.size, c->next);
c = c->next;
  95     }
printf("%x %d %x\n", c, c->h.size, c->next);
  97 }
  99 int check_stats(allocator *suba)
 100 {
 101     if (!TakeSemaphore(suba->sem_id, SUBA_SEMAPHORE_TIMEOUT))
 102     {
 103         int count = -1;
 104         int free_size = 0;
cell* largest = &suba->head;
cell* c = check_cell(suba, &suba->head, "suba_getmeminfo", __LINE__);
 107         while (c->h.size != 0)
 108         {
count += 1;
free_size += ALLOCSIZE(c->h.size);
 111             if (c->h.size > largest->h.size) largest = c;
c = check_cell(suba, c->next, "suba_getmeminfo", __LINE__);
 113         }
 115         if (suba->largest_block == NULL)
suba->largest_block = largest;
 118         int rv = 1;
 119         if (suba->largest_block->h.size != largest->h.size)
 120         {
printf("Mismatch - largest %x %d %x %d\n", suba->largest_block, suba->largest_block->h.size, largest->h.size);
rv = 0;
 123         }
 124         if (suba->free_size != free_size)
 125         {
printf("Mismatch - free_size\n");
rv = 0;
 128         }
 129         if (suba->free_block_count != count)
 130         {
printf("Mismatch - free_block_count\n");
rv = 0;
 133         }
GiveSemaphore(suba->sem_id);
 137         return rv;
 138     }
 139     else
 140     {
DebugAssert("check_stats TakeSemaphore fail", __LINE__);
 142     }
 144     return 0;
 145 }
 146 #endif
 147 #ifdef SUBA_DEBUG
 148 void suba_dump(allocator *suba)
 149 {
 150     char buf[200];
FILE *fp = fopen("A/suba_dump.log", "w");
cell *c = &suba->head;
sprintf(buf, "%x %d %x %d =>\n", c, suba->mincell, suba->largest_block, suba->largest_block->h.size);
fwrite(buf, strlen(buf), 1, fp);
 155     while (c->h.size != 0)
 156     {
sprintf(buf, "%x %d %x\n", c, c->h.size, c->next);
fwrite(buf, strlen(buf), 1, fp);
c = c->next;
 160     }
sprintf(buf, "%x %d %x\n", c, c->h.size, c->next);
fwrite(buf, strlen(buf), 1, fp);
fclose(fp);
 164 }
 166 void check_stats(allocator *suba)
 167 {
 168     int count = -1;
 169     int free_size = 0;
cell* largest = &suba->head;
cell* c = check_cell(suba, &suba->head, "check_stats", __LINE__);
 172     while (c->h.size != 0)
 173     {
count += 1;
free_size += ALLOCSIZE(c->h.size);
 176         if (c->h.size > largest->h.size) largest = c;
c = check_cell(suba, c->next, "check_stats", __LINE__);
 178     }
 180     char buf[200];
 182     if (suba->largest_block->h.size != largest->h.size)
 183     {
suba_dump(suba);
sprintf(buf, "largest %x %d %x %d\n", suba->largest_block, suba->largest_block->h.size, largest, largest->h.size);
DebugAssert(buf, __LINE__);
 187     }
 188     if (suba->free_size != free_size)
 189     {
suba_dump(suba);
sprintf(buf, "free_size %d %d\n", suba->free_size, free_size);
DebugAssert(buf, __LINE__);
 193     }
 194     if (suba->free_block_count != count)
 195     {
suba_dump(suba);
sprintf(buf, "free_count %d %d\n", suba->free_block_count, count);
DebugAssert(buf, __LINE__);
 199     }
 200 }
 201 #endif
 203 void
suba_getmeminfo(allocator *suba, int *allocated_size, int *allocated_peak, int *allocated_count, int *free_size, int *largest_block, int *free_block_count)
 205 {
 206     if (!TakeSemaphore(suba->sem_id, SUBA_SEMAPHORE_TIMEOUT))
 207     {
 208         if (suba->magic != SUBA_MAGIC || *suba->magic2 != SUBA_MAGIC)
DebugAssert("suba_getmeminfo BAD MAGIC", __LINE__);
 211         // Find largest block if not currently known
 212         if (suba->largest_block == NULL)
 213         {
cell* largest = &suba->head;
cell* c = check_cell(suba, &suba->head, "suba_getmeminfo", __LINE__);
 216             while (c->h.size != 0)
 217             {
 218                 if (c->h.size > largest->h.size) largest = c;
c = check_cell(suba, c->next, "suba_getmeminfo", __LINE__);
 220             }
suba->largest_block = largest;
 222         }
 224         *largest_block = ALLOCSIZE(suba->largest_block->h.size);
 225         *free_size = suba->free_size;
 226         *free_block_count = suba->free_block_count;
 228         *allocated_size = suba->allocated_size;
 229         *allocated_peak = suba->allocated_peak;
 230         *allocated_count = suba->allocated_count;
 232 #ifdef SUBA_DEBUG
check_stats(suba);
 234 #endif
GiveSemaphore(suba->sem_id);
 237     }
 238     else
 239     {
DebugAssert("suba_getmeminfo TakeSemaphore fail", __LINE__);
 241     }
 242 }
allocator *
suba_init(allocator *suba, size_t size, size_t mincell, char *name)
 246 {
size_t hdrsiz;
 249 #if SANITY_CHECKS
 250         if (suba == NULL || size == 0) {
DebugAssert("Invalid parameters to 'suba_init'", __LINE__);
 252                 return NULL;
 253         }
 254 #endif
size = size & ~ALIGNMASK;
hdrsiz = ALIGN(sizeof(allocator));
mincell = ACTUALSIZE(ALIGN(mincell));
 260         // Initialise allocator header
memset(suba, 0, hdrsiz);
suba->magic = SUBA_MAGIC;
 263     // cell data must be large enough for next pointer
suba->mincell = sizeof(cell);
 265     if (mincell > suba->mincell)
suba->mincell = mincell;
suba->size = size;
suba->sem_id = CreateBinarySemaphore(name, 1);
 270     // Initialise free list
cell *c1, *c2;
 273     // First cell - allocation block (size - header - empty terminator cell)
c1 = (cell*)((void*)suba + hdrsiz);
c1->h.size = size - hdrsiz - sizeof(cell);
c1->h.magic = CELL_MAGIC;
 278     // Second cell - list terminator (size = 0, next = 0)
c2 = CEND(c1);
c2->h.size = 0;
c2->h.magic = CELL_MAGIC;
c2->next = 0;
 284     // Link first to second, reduce size of first so it will never merge with second terminator cell
c1->next = c2;
c1->h.size -= sizeof(cell*);
 288     // Guard value at the end of the memory block;
suba->magic2 = (unsigned int*)CEND(c1);
 290     *suba->magic2 = SUBA_MAGIC;
 292     // Initial stats
suba->free_block_count = 1;
suba->free_size = ALLOCSIZE(c1->h.size);
suba->largest_block = c1;
 297     // List head - dummy cell, separate from main block so will never be merged, too small to ever be allocated
suba->head.h.size = sizeof(cell_hdr);
suba->head.h.magic = CELL_MAGIC;
suba->head.next = c1;
 302         return suba;
 303 }
 305 void *
suba_alloc(allocator *suba, size_t size, int zero)
 307 {
cell *this_cell = NULL;
 310         // sanitise size & calc real size needed
size = ALIGN(size);
size_t cellsize = ACTUALSIZE(size);
 313     if (cellsize < suba->mincell) cellsize = suba->mincell;
 315         if (!TakeSemaphore(suba->sem_id, SUBA_SEMAPHORE_TIMEOUT))
 316         {
 317             // Find first block big enough to satisfy request
cell *prev_cell = &suba->head;
this_cell = check_cell(suba, prev_cell->next, "suba_alloc", __LINE__);
 320         while (this_cell->h.size > 0 && this_cell->h.size < cellsize) {
prev_cell = this_cell;
this_cell = check_cell(suba, this_cell->next, "suba_alloc", __LINE__);
 323         }
 325         // Check if block large enough was found
 326         if (this_cell->h.size > 0) {
 327             if (this_cell == suba->largest_block)
suba->largest_block = NULL;     // Force recalculation of largest block in suba_getmeminfo
 330             if (this_cell->h.size > (cellsize + suba->mincell)) {
 331                 // split new cell - return from end of larger block
this_cell->h.size = this_cell->h.size - cellsize;
this_cell = CEND(this_cell);
this_cell->h.size = cellsize;
this_cell->h.magic = CELL_MAGIC;
suba->free_size -= cellsize;
 337             } else {
 338                 // use the entire cell - unlink from free list
prev_cell->next = this_cell->next;
cellsize = this_cell->h.size;
suba->free_block_count -= 1;
suba->free_size -= ALLOCSIZE(cellsize);
 343             }
 345             // CHDK counters
suba->allocated_size += ALLOCSIZE(cellsize);
suba->allocated_count++;
 348             if(suba->allocated_size > suba->allocated_peak) {
suba->allocated_peak = suba->allocated_size;
 350             }
 351         } else {
this_cell = NULL;
 353         }
GiveSemaphore(suba->sem_id);
 356     }
 357     else
 358     {
DebugAssert("suba_alloc TakeSemaphore fail", __LINE__);
 360     }
 362         void *p = NULL;
 364         if (this_cell != NULL)
 365         {
p = CELL2ALLOC(this_cell);
 367             if (zero) memset(p, 0, ALLOCSIZE(cellsize));
 368         }
 370         return p;
 371 }
 373 int
suba_free(allocator *suba, void *ptr)
 375 {
cell* this_cell = ALLOC2CELL(ptr);
 378 #if SANITY_CHECKS
 379     // Sanity checks
check_cell(suba, this_cell, "suba_free", __LINE__);
 381     if (this_cell->h.size > suba->size) {
DebugAssert("Trying to free bad block", __LINE__);
 383         return -1;
 384     }
 385 #endif
 387     if (!TakeSemaphore(suba->sem_id, SUBA_SEMAPHORE_TIMEOUT))
 388     {
 389         // CHDK counters
suba->allocated_size -= ALLOCSIZE(this_cell->h.size);
suba->allocated_count--;
 393         // List header
cell* prev_cell = &suba->head;
 396         // find insertion point
 397         while (prev_cell->next < this_cell) {
prev_cell = check_cell(suba, prev_cell->next, "suba_free", __LINE__);
 399         }
cell* next_cell = check_cell(suba, prev_cell->next, "suba_free", __LINE__);
 402         // do prev cell and this cell need to be joined?
 403         if (ISADJ(prev_cell,this_cell)) {
suba->free_size += this_cell->h.size;
prev_cell->h.size += this_cell->h.size;
this_cell = prev_cell;
 407         } else {
this_cell->next = prev_cell->next;
prev_cell->next = this_cell;
suba->free_block_count += 1;
suba->free_size += ALLOCSIZE(this_cell->h.size);
 412         }
 414         // do this cell and next cell need to be joined?
 415         if (ISADJ(this_cell,next_cell)) {
this_cell->next = next_cell->next;
this_cell->h.size += next_cell->h.size;
suba->free_block_count -= 1;
suba->free_size += sizeof(cell_hdr);
 420         }
 422         // Update largest_block if null or this one is now bigger
 423         if ((suba->largest_block != NULL) && (this_cell->h.size > suba->largest_block->h.size))
suba->largest_block = this_cell;
GiveSemaphore(suba->sem_id);
 427     }
 428     else
 429     {
DebugAssert("suba_free TakeSemaphore fail", __LINE__);
 431         return -1;
 432     }
 434         return 0;
 435 }