root/core/suba.c

/* [<][>][^][v][top][bottom][index][help] */

DEFINITIONS

This source file includes following 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 */
  11 
  12 // Rewritten for CHDK.
  13 
  14 #include "stdlib.h"
  15 #include "stddef.h"
  16 
  17 #define SUBA_SEMAPHORE_TIMEOUT  1000
  18 #define SANITY_CHECKS           1
  19 
  20 #define SUBA_MAGIC 0x53554241
  21 #define CELL_MAGIC 0x5342434C
  22 
  23 // Free list cell header
  24 typedef struct {
  25     unsigned int    magic;      // cell check value
  26     size_t          size;
  27 } cell_hdr;
  28 
  29 // Free list cell
  30 typedef struct _cell {
  31     cell_hdr        h;
  32     struct _cell*   next;       // link to next cell in free list
  33 } cell;
  34 
  35 // Memory allocator
  36 typedef struct {
  37         unsigned int    magic;      // suba header identifier
  38         unsigned int*   magic2;     // guard value at the end of the block
  39     size_t          size;       // total size of memory area
  40         int             sem_id;     // Canon semaphore id
  41         cell            head;       // List header
  42         size_t          mincell;    // min cell size must be at least sizeof cell
  43 
  44     // CHDK added counters, modeled on DryOS values
  45     int free_block_count;       // Length of free list
  46     int free_size;              // Available memory in free list
  47     cell* largest_block;        // Largest block on free list
  48     size_t allocated_count;     // total number of current allocations
  49     size_t allocated_size;      // total amount of memory currently allocated, excluding overhead
  50     size_t allocated_peak;      // maximum value of allocated_size encountered
  51 } allocator;
  52 
  53 // Cell / Pointer manipulation macros
  54 #define ALIGNMASK           (sizeof(cell*)-1)
  55 #define ALIGN(s)            (((s) + ALIGNMASK) & ~ALIGNMASK)
  56 
  57 #define ACTUALSIZE(size)    (size + sizeof(cell_hdr))
  58 #define ALLOCSIZE(size)     (size - sizeof(cell_hdr))
  59 #define CELL2ALLOC(c)       (void*)((void*)c + sizeof(cell_hdr))
  60 #define ALLOC2CELL(p)       (cell*)((void*)p - sizeof(cell_hdr))
  61 
  62 #define CEND(c)             ((cell*)((char*)c + c->h.size))
  63 #define ISADJ(c1,c2)        (CEND(c1) == (c2))
  64 
  65 #if SANITY_CHECKS
  66 static cell*
  67 check_cell(const allocator *suba, cell* c, char *fn, int ln)
  68 {
  69         if (suba && (c > (cell*)suba) && (c < (cell*)((char*)suba + suba->size))) {
  70             if (c->h.magic != CELL_MAGIC)
  71                 DebugAssert("Corrupt cell header", ln);
  72                 return c;
  73         }
  74         char buf[200];
  75         sprintf(buf, "%s bad cell - %x %x", fn, c, suba);
  76         DebugAssert(buf, ln);
  77         return NULL;
  78 }
  79 #else
  80 #define check_cell(s, c, f, l) (c)
  81 #endif
  82 
  83 #ifdef SUBA_HOST_DEBUG
  84 // For testing on host (not in CHDK). Print free list to stdout.
  85 void suba_dump(allocator *suba)
  86 {
  87     cell *c = &suba->head;
  88     printf("%x %d => ", c, suba->mincell);
  89     while (c->h.size != 0)
  90     {
  91         printf("%x %d %x, ", c, c->h.size, c->next);
  92         c = c->next;
  93     }
  94     printf("%x %d %x\n", c, c->h.size, c->next);
  95 }
  96 
  97 int check_stats(allocator *suba)
  98 {
  99     if (!TakeSemaphore(suba->sem_id, SUBA_SEMAPHORE_TIMEOUT))
 100     {
 101         int count = -1;
 102         int free_size = 0;
 103         cell* largest = &suba->head;
 104         cell* c = check_cell(suba, &suba->head, "suba_getmeminfo", __LINE__);
 105         while (c->h.size != 0)
 106         {
 107             count += 1;
 108             free_size += ALLOCSIZE(c->h.size);
 109             if (c->h.size > largest->h.size) largest = c;
 110             c = check_cell(suba, c->next, "suba_getmeminfo", __LINE__);
 111         }
 112 
 113         if (suba->largest_block == NULL)
 114             suba->largest_block = largest;
 115 
 116         int rv = 1;
 117         if (suba->largest_block->h.size != largest->h.size)
 118         {
 119             printf("Mismatch - largest %x %d %x %d\n", suba->largest_block, suba->largest_block->h.size, largest->h.size);
 120             rv = 0;
 121         }
 122         if (suba->free_size != free_size)
 123         {
 124             printf("Mismatch - free_size\n");
 125             rv = 0;
 126         }
 127         if (suba->free_block_count != count)
 128         {
 129             printf("Mismatch - free_block_count\n");
 130             rv = 0;
 131         }
 132 
 133         GiveSemaphore(suba->sem_id);
 134 
 135         return rv;
 136     }
 137     else
 138     {
 139         DebugAssert("check_stats TakeSemaphore fail", __LINE__);
 140     }
 141 
 142     return 0;
 143 }
 144 #endif
 145 #ifdef SUBA_DEBUG
 146 void suba_dump(allocator *suba)
 147 {
 148     char buf[200];
 149     FILE *fp = fopen("A/suba_dump.log", "w");
 150     cell *c = &suba->head;
 151     sprintf(buf, "%x %d %x %d =>\n", c, suba->mincell, suba->largest_block, suba->largest_block->h.size);
 152     fwrite(buf, strlen(buf), 1, fp);
 153     while (c->h.size != 0)
 154     {
 155         sprintf(buf, "%x %d %x\n", c, c->h.size, c->next);
 156         fwrite(buf, strlen(buf), 1, fp);
 157         c = c->next;
 158     }
 159     sprintf(buf, "%x %d %x\n", c, c->h.size, c->next);
 160     fwrite(buf, strlen(buf), 1, fp);
 161     fclose(fp);
 162 }
 163 
 164 void check_stats(allocator *suba)
 165 {
 166     int count = -1;
 167     int free_size = 0;
 168     cell* largest = &suba->head;
 169     cell* c = check_cell(suba, &suba->head, "check_stats", __LINE__);
 170     while (c->h.size != 0)
 171     {
 172         count += 1;
 173         free_size += ALLOCSIZE(c->h.size);
 174         if (c->h.size > largest->h.size) largest = c;
 175         c = check_cell(suba, c->next, "check_stats", __LINE__);
 176     }
 177 
 178     char buf[200];
 179 
 180     if (suba->largest_block->h.size != largest->h.size)
 181     {
 182         suba_dump(suba);
 183         sprintf(buf, "largest %x %d %x %d\n", suba->largest_block, suba->largest_block->h.size, largest, largest->h.size);
 184         DebugAssert(buf, __LINE__);
 185     }
 186     if (suba->free_size != free_size)
 187     {
 188         suba_dump(suba);
 189         sprintf(buf, "free_size %d %d\n", suba->free_size, free_size);
 190         DebugAssert(buf, __LINE__);
 191     }
 192     if (suba->free_block_count != count)
 193     {
 194         suba_dump(suba);
 195         sprintf(buf, "free_count %d %d\n", suba->free_block_count, count);
 196         DebugAssert(buf, __LINE__);
 197     }
 198 }
 199 #endif
 200 
 201 void
 202 suba_getmeminfo(allocator *suba, int *allocated_size, int *allocated_peak, int *allocated_count, int *free_size, int *largest_block, int *free_block_count)
 203 {
 204     if (!TakeSemaphore(suba->sem_id, SUBA_SEMAPHORE_TIMEOUT))
 205     {
 206         if (suba->magic != SUBA_MAGIC || *suba->magic2 != SUBA_MAGIC)
 207             DebugAssert("suba_getmeminfo BAD MAGIC", __LINE__);
 208 
 209         // Find largest block if not currently known
 210         if (suba->largest_block == NULL)
 211         {
 212             cell* largest = &suba->head;
 213             cell* c = check_cell(suba, &suba->head, "suba_getmeminfo", __LINE__);
 214             while (c->h.size != 0)
 215             {
 216                 if (c->h.size > largest->h.size) largest = c;
 217                 c = check_cell(suba, c->next, "suba_getmeminfo", __LINE__);
 218             }
 219             suba->largest_block = largest;
 220         }
 221 
 222         *largest_block = ALLOCSIZE(suba->largest_block->h.size);
 223         *free_size = suba->free_size;
 224         *free_block_count = suba->free_block_count;
 225 
 226         *allocated_size = suba->allocated_size;
 227         *allocated_peak = suba->allocated_peak;
 228         *allocated_count = suba->allocated_count;
 229 
 230 #ifdef SUBA_DEBUG
 231         check_stats(suba);
 232 #endif
 233 
 234         GiveSemaphore(suba->sem_id);
 235     }
 236     else
 237     {
 238         DebugAssert("suba_getmeminfo TakeSemaphore fail", __LINE__);
 239     }
 240 }
 241 
 242 allocator *
 243 suba_init(allocator *suba, size_t size, size_t mincell, char *name)
 244 {
 245         size_t hdrsiz;
 246 
 247 #if SANITY_CHECKS
 248         if (suba == NULL || size == 0) {
 249                 DebugAssert("Invalid parameters to 'suba_init'", __LINE__);
 250                 return NULL;
 251         }
 252 #endif
 253 
 254         size = size & ~ALIGNMASK;
 255     hdrsiz = ALIGN(sizeof(allocator));
 256     mincell = ACTUALSIZE(ALIGN(mincell));
 257 
 258         // Initialise allocator header
 259     memset(suba, 0, hdrsiz);
 260     suba->magic = SUBA_MAGIC;
 261     // cell data must be large enough for next pointer
 262     suba->mincell = sizeof(cell);
 263     if (mincell > suba->mincell)
 264         suba->mincell = mincell;
 265     suba->size = size;
 266     suba->sem_id = CreateBinarySemaphore(name, 1);
 267 
 268     // Initialise free list
 269     cell *c1, *c2;
 270 
 271     // First cell - allocation block (size - header - empty terminator cell)
 272     c1 = (cell*)((void*)suba + hdrsiz);
 273     c1->h.size = size - hdrsiz - sizeof(cell);
 274     c1->h.magic = CELL_MAGIC;
 275 
 276     // Second cell - list terminator (size = 0, next = 0)
 277     c2 = CEND(c1);
 278     c2->h.size = 0;
 279     c2->h.magic = CELL_MAGIC;
 280     c2->next = 0;
 281 
 282     // Link first to second, reduce size of first so it will never merge with second terminator cell
 283     c1->next = c2;
 284     c1->h.size -= sizeof(cell*);
 285 
 286     // Guard value at the end of the memory block;
 287     suba->magic2 = (unsigned int*)CEND(c1);
 288     *suba->magic2 = SUBA_MAGIC;
 289 
 290     // Initial stats
 291     suba->free_block_count = 1;
 292     suba->free_size = ALLOCSIZE(c1->h.size);
 293     suba->largest_block = c1;
 294 
 295     // List head - dummy cell, separate from main block so will never be merged, too small to ever be allocated
 296     suba->head.h.size = sizeof(cell_hdr);
 297     suba->head.h.magic = CELL_MAGIC;
 298     suba->head.next = c1;
 299 
 300         return suba;
 301 }
 302 
 303 void *
 304 suba_alloc(allocator *suba, size_t size, int zero)
 305 {
 306         cell *this_cell = NULL;
 307 
 308         // sanitise size & calc real size needed
 309         size = ALIGN(size);
 310     int cellsize = ACTUALSIZE(size);
 311     if (cellsize < suba->mincell) cellsize = suba->mincell;
 312 
 313         if (!TakeSemaphore(suba->sem_id, SUBA_SEMAPHORE_TIMEOUT))
 314         {
 315             // Find first block big enough to satisfy request
 316             cell *prev_cell = &suba->head;
 317         this_cell = check_cell(suba, prev_cell->next, "suba_alloc", __LINE__);
 318         while (this_cell->h.size > 0 && this_cell->h.size < cellsize) {
 319             prev_cell = this_cell;
 320             this_cell = check_cell(suba, this_cell->next, "suba_alloc", __LINE__);
 321         }
 322 
 323         // Check if block large enough was found
 324         if (this_cell->h.size > 0) {
 325             if (this_cell == suba->largest_block)
 326                 suba->largest_block = NULL;     // Force recalculation of largest block in suba_getmeminfo
 327 
 328             if (this_cell->h.size > (cellsize + suba->mincell)) {
 329                 // split new cell - return from end of larger block
 330                 this_cell->h.size = this_cell->h.size - cellsize;
 331                 this_cell = CEND(this_cell);
 332                 this_cell->h.size = cellsize;
 333                 this_cell->h.magic = CELL_MAGIC;
 334                 suba->free_size -= cellsize;
 335             } else {
 336                 // use the entire cell - unlink from free list
 337                 prev_cell->next = this_cell->next;
 338                 cellsize = this_cell->h.size;
 339                 suba->free_block_count -= 1;
 340                 suba->free_size -= ALLOCSIZE(cellsize);
 341             }
 342 
 343             // CHDK counters
 344             suba->allocated_size += ALLOCSIZE(cellsize);
 345             suba->allocated_count++;
 346             if(suba->allocated_size > suba->allocated_peak) {
 347                 suba->allocated_peak = suba->allocated_size;
 348             }
 349         } else {
 350             this_cell = NULL;
 351         }
 352 
 353         GiveSemaphore(suba->sem_id);
 354     }
 355     else
 356     {
 357         DebugAssert("suba_alloc TakeSemaphore fail", __LINE__);
 358     }
 359 
 360         void *p = NULL;
 361 
 362         if (this_cell != NULL)
 363         {
 364             p = CELL2ALLOC(this_cell);
 365             if (zero) memset(p, 0, ALLOCSIZE(cellsize));
 366         }
 367 
 368         return p;
 369 }
 370 
 371 int
 372 suba_free(allocator *suba, void *ptr)
 373 {
 374     cell* this_cell = ALLOC2CELL(ptr);
 375 
 376 #if SANITY_CHECKS
 377     // Sanity checks
 378     check_cell(suba, this_cell, "suba_free", __LINE__);
 379     if (this_cell->h.size > suba->size) {
 380         DebugAssert("Trying to free bad block", __LINE__);
 381         return -1;
 382     }
 383 #endif
 384 
 385     if (!TakeSemaphore(suba->sem_id, SUBA_SEMAPHORE_TIMEOUT))
 386     {
 387         // CHDK counters
 388         suba->allocated_size -= ALLOCSIZE(this_cell->h.size);
 389         suba->allocated_count--;
 390 
 391         // List header
 392         cell* prev_cell = &suba->head;
 393 
 394         // find insertion point
 395         while (prev_cell->next < this_cell) {
 396             prev_cell = check_cell(suba, prev_cell->next, "suba_free", __LINE__);
 397         }
 398         cell* next_cell = check_cell(suba, prev_cell->next, "suba_free", __LINE__);
 399 
 400         // do prev cell and this cell need to be joined?
 401         if (ISADJ(prev_cell,this_cell)) {
 402             suba->free_size += this_cell->h.size;
 403             prev_cell->h.size += this_cell->h.size;
 404             this_cell = prev_cell;
 405         } else {
 406             this_cell->next = prev_cell->next;
 407             prev_cell->next = this_cell;
 408             suba->free_block_count += 1;
 409             suba->free_size += ALLOCSIZE(this_cell->h.size);
 410         }
 411 
 412         // do this cell and next cell need to be joined?
 413         if (ISADJ(this_cell,next_cell)) {
 414             this_cell->next = next_cell->next;
 415             this_cell->h.size += next_cell->h.size;
 416             suba->free_block_count -= 1;
 417             suba->free_size += sizeof(cell_hdr);
 418         }
 419 
 420         // Update largest_block if null or this one is now bigger
 421         if ((suba->largest_block != NULL) && (this_cell->h.size > suba->largest_block->h.size))
 422             suba->largest_block = this_cell;
 423 
 424         GiveSemaphore(suba->sem_id);
 425     }
 426     else
 427     {
 428         DebugAssert("suba_free TakeSemaphore fail", __LINE__);
 429         return -1;
 430     }
 431 
 432         return 0;
 433 }

/* [<][>][^][v][top][bottom][index][help] */