mm/allocator2.c

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