mm/allocator.c

   1 /*
   2  * cacao/mm/allocator.c
   3  *
   4  * Copyright (c) 1998 A. Krall, R. Grafl, M. Gschwind, M. Probst, Ph. Tomsich
   5  * See file COPYRIGHT for information on usage and disclaimer of warranties
   6  *
   7  * Authors: Philipp Tomsich     EMAIL: cacao@complang.tuwien.ac.at
   8  *
   9  * $Id: allocator.c 34 1998-11-03 11:29:37Z phil $
  10  */
  11
  12 /*
  13    NOTES:
  14
  15    Locality preservation has not been added... yet
  16 */
  17
  18 #include "allocator.h"
  19
  20 static FREE_EXACT*  __freelist_exact[1 << EXACT];
  21 static FREE_EXACT** freelist_exact = &__freelist_exact[-1];
  22 static FREE_LARGE*  freelist_large[LARGE << SUBBIT];
  23
  24 #if SMALL_TABLES
  25 static unsigned char  highest[256];
  26 #else
  27 #       if EXACT_TOP_BIT < 8
  28 #       if (ADDRESS == 64)
  29 static unsigned char  highest_0[2048];
  30 #       else
  31 static unsigned char  highest_0[1024];
  32 #       endif
  33
  34 static unsigned char* highest_8  = &highest_0[256];
  35 static unsigned char* highest_16 = &highest_0[512];
  36 static unsigned char* highest_24 = &highest_0[768];
  37 #       if (ADDRESS == 64)
  38 static unsigned char* highest_32 = &highest_0[1024];
  39 static unsigned char* highest_40 = &highest_0[1280];
  40 static unsigned char* highest_48 = &highest_0[1538];
  41 static unsigned char* highest_56 = &highest_0[1792];
  42 #       endif
  43 #       else
  44 #       if (ADDRESS == 64)
  45 static unsigned char  highest_8[1792];
  46 #       else
  47 static unsigned char  highest_8[768];
  48 #       endif
  49
  50 static unsigned char* highest_16 = &highest_8[256];
  51 static unsigned char* highest_24 = &highest_8[512];
  52 #       if (ADDRESS == 64)
  53 static unsigned char* highest_32 = &highest_8[768];
  54 static unsigned char* highest_40 = &highest_8[1280];
  55 static unsigned char* highest_48 = &highest_8[1538];
  56 static unsigned char* highest_56 = &highest_8[1792];
  57 #       endif
  58 #       endif
  59 #endif
  60
  61 static
  62 unsigned char
  63 find_highest(SIZE bits){
  64 #if MSB_TO_LSB_SEARCH
  65         /* optimize for large allocation sizes */
  66 #       if SMALL_TABLES
  67 #               if ADDRESS == 64
  68                         if (bits & 0xff00000000000000ULL)
  69                                 return 56 + highest[bits >> 56 & 0xff];
  70                         if (bits & 0xff000000000000ULL)
  71                                 return 48 + highest[bits >> 48 & 0xff];
  72                         if (bits & 0xff0000000000ULL)
  73                                 return 40 + highest[bits >> 40 & 0xff];
  74                         if (bits & 0xff00000000ULL)
  75                                 return 32 + highest[bits >> 32 & 0xff];
  76 #               endif
  77
  78                         if (bits & 0xff000000)
  79                                 return 24 + highest[bits >> 24 & 0xff];
  80                         if (bits & 0xff0000)
  81                                 return 16 + highest[bits >> 16 & 0xff];
  82                         if (bits & 0xff00)
  83                                 return 8 + highest[bits >> 8 & 0xff];
  84
  85 #       if EXACT_TOP_BIT < 8
  86                         return highest[bits & 0xff];
  87 #               endif
  88 #       else
  89 #               if ADDRESS == 64
  90                         if (bits & 0xff00000000000000ULL)
  91                                 return highest_56[bits >> 56 & 0xff];
  92                         if (bits & 0xff000000000000ULL)
  93                                 return highest_48[bits >> 48 & 0xff];
  94                         if (bits & 0xff0000000000ULL)
  95                                 return highest_40[bits >> 40 & 0xff];
  96                         if (bits & 0xff00000000ULL)
  97                                 return highest_32[bits >> 32 & 0xff];
  98 #               endif
  99
 100                         if (bits & 0xff000000)
 101                                 return highest_24[bits >> 24 & 0xff];
 102                         if (bits & 0xff0000)
 103                                 return highest_16[bits >> 16 & 0xff];
 104                         if (bits & 0xff00)
 105                                 return highest_8[bits >> 8 & 0xff];
 106
 107 #       if EXACT_TOP_BIT < 8
 108                         return highest_0[bits & 0xff];
 109 #               endif
 110 #       endif
 111
 112 #else
 113         /* optimize for small allocation sizes */
 114
 115 #       if SMALL_TABLES
 116 #       if EXACT_TOP_BIT < 8
 117                         if (!(bits & ~0xffULL))
 118                                 return highest[bits & 0xff];
 119 #               endif
 120
 121                         if (!(bits & ~0xffffULL))
 122                                 return 8 + highest[bits >> 8 & 0xff];
 123
 124                         if (!(bits & ~0xffffffULL))
 125                                 return 16 + highest[bits >> 16 & 0xff];
 126
 127 #               if      ADDRESS == 32
 128                         return 24 + highest[bits >> 24 & 0xff];
 129 #               else
 130                         if (!(bits & ~0xffffffffULL))
 131                                 return 24 + highest[bits >> 24 & 0xff];
 132
 133                         if (!(bits & ~0xffffffffffULL))
 134                                 return 32 + highest[bits >> 32 & 0xff];
 135
 136                         if (!(bits & ~0xffffffffffffULL))
 137                                 return 40 + highest[bits >> 40 & 0xff];
 138
 139                         if (!(bits & ~0xffffffffffffffULL))
 140                                 return 48 + highest[bits >> 48 & 0xff];
 141
 142                         return 56 + highest[bits >> 56 & 0xff];
 143 #               endif
 144 #       else
 145 #       if EXACT_TOP_BIT < 8
 146                         if (!(bits & ~0xffULL))
 147                                 return highest_0[bits & 0xff];
 148 #               endif
 149
 150                         if (!(bits & ~0xffffULL))
 151                                 return highest_8[bits >> 8 & 0xff];
 152
 153                         if (!(bits & ~0xffffffULL))
 154                                 return highest_16[bits >> 16 & 0xff];
 155
 156 #               if      ADDRESS == 32
 157                         return highest_24[bits >> 24 & 0xff];
 158 #               else
 159                         if (!(bits & ~0xffffffffULL))
 160                                 return highest_24[bits >> 24 & 0xff];
 161
 162                         if (!(bits & ~0xffffffffffULL))
 163                                 return highest_32[bits >> 32 & 0xff];
 164
 165                         if (!(bits & ~0xffffffffffffULL))
 166                                 return highest_40[bits >> 40 & 0xff];
 167
 168                         if (!(bits & ~0xffffffffffffffULL))
 169                                 return highest_48[bits >> 48 & 0xff];
 170
 171                         return highest_56[bits >> 56 & 0xff];
 172 #               endif
 173 #       endif
 174 #endif
 175
 176 };
 177
 178 static
 179 void
 180 init_table()
 181 {
 182   static unsigned char r[10] = { 1, 1, 2, 4, 8, 16, 32, 64, 128 };
 183   int i, j, k, m;
 184
 185   i = 0;
 186   j = 0;
 187   k = 0;
 188   m = 0;
 189
 190   for (k = 0; k < 10; ++k) {
 191           for (m = 0; m < r[k]; ++m) {
 192 #if SMALL_TABLES
 193                   highest[i]  = j - (EXACT + ALIGN) - 1;
 194 #else
 195 #       if (EXACT_TOP_BIT < 8)
 196                   highest_0 [i]  = j - 8 - (EXACT + ALIGN) - 1;
 197 #       endif
 198                   highest_8 [i]  = j + 8 - (EXACT + ALIGN) - 1;
 199                   highest_16 [i] =  8 + highest_8 [i];
 200                   highest_24 [i] = 16 + highest_8 [i];
 201 #   if (ADDRESS == 64)
 202                   highest_32 [i] = 24 + highest_8 [i];
 203                   highest_40 [i] = 32 + highest_8 [i];
 204                   highest_48 [i] = 40 + highest_8 [i];
 205                   highest_56 [i] = 48 + highest_8 [i];
 206 #   endif
 207 #endif
 208
 209                   ++i;
 210           }
 211
 212           ++j;
 213   }
 214 }
 215
 216 #define PRESERVE_LOCALITY 0
 217
 218 #if FASTER_FAIL
 219 static SIZE     allocator_largest_free = 0;
 220 #endif
 221
 222 #if PRESERVE_LOCALITY
 223 static void* allocator_last_splitoff = 0;
 224 static SIZE  allocator_last_splitoff_size = 0;
 225 #endif
 226
 227 void
 228 allocator_reset()
 229 {
 230         int i;
 231
 232 #if FASTER_FAIL
 233         allocator_largest_free = 0;
 234 #endif
 235
 236 #if PRESERVE_LOCALITY
 237         allocator_last_splitoff = 0;
 238         allocator_last_splitoff_size = 0;
 239 #endif
 240
 241   for (i = 1; i <= (1 << EXACT); ++i)
 242           freelist_exact[i] = 0;
 243
 244   for (i = 0; i < (LARGE << SUBBIT); ++i)
 245           freelist_large[i] = 0;
 246 }
 247
 248
 249 #include <stdio.h>
 250
 251
 252 #if COUNT_ALLOCATIONS
 253 static unsigned long long       allocator_allocations = 0;
 254
 255 void
 256 allocator_display_count()
 257 {
 258         fprintf(stderr, "total allocations: %d\n", allocator_allocations);
 259 }
 260 #endif
 261
 262
 263 void
 264 allocator_init()
 265 {
 266         fprintf(stderr,
 267                         "allocator_init: $Id: allocator.c 34 1998-11-03 11:29:37Z phil $\n\n");
 268
 269         fprintf(stderr, "\t%d bit addresses\n", ADDRESS);
 270         fprintf(stderr, "\t%d bit alignment\n", ALIGN);
 271         fprintf(stderr, "\t%d exact bits\n", EXACT );
 272         fprintf(stderr, "\t%d large bits\n", LARGE );
 273         fprintf(stderr, "\t%d subbin bits\n", SUBBIT );
 274         fprintf(stderr, "\tusing %s tables\n",
 275                         SMALL_TABLES ? "small (256 byte)" : "large (2048 byte)");
 276         fprintf(stderr, "\tusing %s highest-bit search strategy\n",
 277                         MSB_TO_LSB_SEARCH ? "MSB-to-LSB" : "LSB-to-MSB");
 278
 279         fprintf(stderr,
 280                         "\tusing %d bytes for exact bins, %d bytes for sorted bins\n\n",
 281                         (1 << EXACT) << ALIGN,
 282                         (LARGE << SUBBIT) << ALIGN);
 283
 284         init_table();           /* set up the highest-table */
 285         allocator_reset();      /* clear the freelists & internal variables */
 286 }
 287
 288 int
 289 size_to_bin(SIZE  size)
 290 {
 291 #if PRINTF
 292         printf ("size: %d ", size);
 293 #endif
 294
 295 #if EXACT > 0
 296         if (size > ((1 << EXACT) << ALIGN)) {
 297 #endif
 298                 // unsigned char        shift = shift_table_32[highbit];
 299                 // int          bin = offset_table_32[highbit] + ( (size >> shift) & mask );
 300 #if SUBBIT != 0
 301                 unsigned char   highbit = find_highest(size);
 302                 unsigned char   shift = highbit + (EXACT + ALIGN - SUBBIT);
 303                 static int      mask = (1 << SUBBIT) - 1;
 304                 int                             bin = (highbit << SUBBIT) + ( (size >> shift) & mask );
 305
 306                 // printf("shift: %d, %d; %d; large bin: %d\n", shift, (size >> shift) & mask, highbit,  bin);
 307 #else
 308                 int                             bin = find_highest(size);
 309 #endif
 310
 311 #if PRINTF
 312                 printf("==> large bin: %d\n",  bin);
 313 #endif
 314
 315                 return bin;
 316 #if EXACT > 0
 317         } else {
 318 #if PRINTF
 319                 printf("==> exact bin: %d\n", (int)((size >> ALIGN) - 1));
 320 #endif
 321
 322                 return (size >> ALIGN);
 323         }
 324 #endif
 325 }
 326
 327 #include <assert.h>
 328
 329
 330 #define OLDEST_FIRST   1
 331
 332
 333
 334 /* FIXME:
 335    Should we enforce an additional "lowest address first" - ordering
 336    for the freelist-entries ??? Right now, I'm using oldest-first for
 337    the large bins and newest-first for the exact bins...
 338
 339    Sorting by the address may reduce heap fragmentation by reducing the
 340    heap growth-rate... */
 341
 342 void
 343 allocator_free(void* chunk, SIZE size)
 344 {
 345         assert(chunk && size);
 346
 347 #if FASTER_FAIL
 348         if (size > allocator_largest_free)
 349                 allocator_largest_free = size;
 350 #endif
 351
 352         if (size > ((1 << EXACT) << ALIGN)) {
 353                 int                     bin = size_to_bin(size);
 354                 FREE_LARGE*             curr = freelist_large[bin];
 355
 356                 ((FREE_LARGE*)chunk)->size = size;
 357
 358                 if (!freelist_large[bin] || (freelist_large[bin]->size > size)) {
 359                         /* prepend */
 360                         ((FREE_LARGE*)chunk)->next = freelist_large[bin];
 361                         freelist_large[bin] = (FREE_LARGE*)chunk;
 362                         return;
 363                 }
 364
 365                 while ((curr->next) && (curr->next->size <= size)) {
 366                         curr = curr->next;
 367                 };
 368
 369                 /* insert or append */
 370                 ((FREE_LARGE*)chunk)->next = curr->next;
 371                 curr->next=(FREE_LARGE*)chunk;
 372         } else {
 373                 int bin = size >> ALIGN;
 374
 375 #if OLDEST_FIRST
 376                 if (!freelist_exact[bin]) {
 377 #endif
 378                         /* simply prepend */
 379                         ((FREE_EXACT*)chunk)->next = freelist_exact[bin];
 380                         freelist_exact[bin] = (FREE_EXACT*)chunk;
 381 #if OLDEST_FIRST
 382                 } else {
 383                         FREE_EXACT*  curr = (FREE_EXACT*)freelist_exact[bin];
 384                         while (curr->next && (curr < (FREE_EXACT*)chunk))
 385                                 curr = curr->next;
 386
 387                         /* insert */
 388                         ((FREE_EXACT*)chunk)->next = curr->next;
 389                         curr->next = (FREE_EXACT*)chunk;
 390                 }
 391 #endif
 392         }
 393
 394         return;
 395 }
 396
 397 void*
 398 allocator_alloc(SIZE size)
 399 {
 400         void*   result = NULL;
 401         int     maxbin;
 402         int             bin;
 403
 404 #if COUNT_ALLOCATIONS
 405         allocator_allocations++;
 406 #endif
 407
 408 #if FASTER_FAIL
 409         if (size > allocator_largest_free)
 410                 return NULL;
 411 #endif
 412
 413 #if PRESERVE_LOCALITY
 414         allocator_last_splitoff = 0;
 415         allocator_last_splitoff_size = 0;
 416 #endif
 417
 418         if (size <= ((1 << EXACT) << ALIGN)) {
 419                 /* search the exact bins */
 420                 bin = size >> ALIGN;
 421                 maxbin = 1 << EXACT;
 422
 423                 while (bin <= maxbin) {
 424                         if (freelist_exact[bin]) {
 425                                 /* unlink */
 426                                 result = (void*)freelist_exact[bin];
 427                                 freelist_exact[bin]=freelist_exact[bin]->next;
 428
 429                                 /* split */
 430                                 if ((bin << ALIGN) > size)
 431                                         allocator_free(result + size, (bin << ALIGN) - size);
 432
 433                                 //                              fprintf(stderr, "found chunk in exact bin %d\n", bin);
 434
 435                                 return result;
 436                         } else
 437                                 ++bin;
 438                 }
 439
 440                 bin = 0;
 441         } else {
 442                 bin = size_to_bin(size);
 443         }
 444
 445         maxbin = LARGE << SUBBIT;
 446
 447         while (bin < maxbin) {
 448                 if (freelist_large[bin]) {
 449                         FREE_LARGE*  chunk = freelist_large[bin];
 450
 451                         //                      fprintf(stderr, "found chunk in large bin %d\n", bin);
 452
 453                         if (chunk->size >= size) {
 454                                 /* unlink */
 455                                 freelist_large[bin] = chunk->next;
 456
 457                                 /* split */
 458                                 if (chunk->size > size)
 459                                         allocator_free((void*)chunk + size, (chunk->size - size));
 460
 461                                 return (void*)chunk;
 462                         }
 463
 464                         while (chunk->next && (chunk->next->size < size))
 465                                 chunk = chunk->next;
 466
 467                         if (chunk->next) {
 468                                 /* unlink */
 469                                 FREE_LARGE*  new_chunk = chunk->next;
 470                                 chunk->next = new_chunk->next;
 471
 472                                 /* split */
 473                                 if (new_chunk->size > size)
 474                                         allocator_free((void*)new_chunk + size, (new_chunk->size - size));
 475
 476                                 return (void*)new_chunk;
 477                         }
 478                 }
 479
 480                 ++bin;
 481         }
 482
 483         return result;  /* NULL */
 484 }
 485
 486 void
 487 allocator_dump()
 488 {
 489         int i;
 490
 491         for (i = 1; i <= 1 << EXACT; ++i) {
 492                 int                     count = 0;
 493                 FREE_EXACT*     chunk = freelist_exact[i];
 494
 495                 while (chunk) {
 496                         chunk = chunk->next;
 497                         ++count;
 498                 }
 499
 500                 if (count)
 501                         printf("exact bin %d (%d byte blocks): %d\n", i, i * (1 << ALIGN), count);
 502         }
 503         for (i = 0; i < LARGE << SUBBIT; ++i) {
 504                 int                     count = 0;
 505                 FREE_LARGE*     chunk = freelist_large[i];
 506
 507                 if (chunk)
 508                         printf("large bin %d:\n", i);
 509
 510                 while (chunk) {
 511                         printf("\t%d bytes @ 0x%lx\n", chunk->size, chunk);
 512                         chunk = chunk->next;
 513                         ++count;
 514                 }
 515         }
 516
 517         printf("dump complete.\n");
 518 }
 519
 520
 521
 522
 523 /*
 524  * These are local overrides for various environment variables in Emacs.
 525  * Please do not remove this and leave it at the end of the file, where
 526  * Emacs will automagically detect them.
 527  * ---------------------------------------------------------------------
 528  * Local variables:
 529  * mode: c
 530  * indent-tabs-mode: t
 531  * c-basic-offset: 4
 532  * tab-width: 4
 533  * End:
 534  */