1/*--------------------------------------------------------------------------- 2| Copyright (C) 1999-2000 Jochen C. Loewer (loewerj@hotmail.com) 3+---------------------------------------------------------------------------- 4| 5| $Id: domalloc.c,v 1.10 2007/08/18 00:33:12 rolf Exp $ 6| 7| 8| A special memory allocator, which uses pre-allocated / bit masked 9| based administration of memory blocks with fixed sizes, like 10| DOM nodes. This will hopefully save some memory. 11| 12| 13| The contents of this file are subject to the Mozilla Public License 14| Version 1.1 (the "License"); you may not use this file except in 15| compliance with the License. You may obtain a copy of the License at 16| http://www.mozilla.org/MPL/ 17| 18| Software distributed under the License is distributed on an "AS IS" 19| basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the 20| License for the specific language governing rights and limitations 21| under the License. 22| 23| The Original Code is tDOM. 24| 25| The Initial Developer of the Original Code is Jochen Loewer 26| Portions created by Jochen Loewer are Copyright (C) 1998, 1999 27| Jochen Loewer. All Rights Reserved. 28| 29| Contributor(s): 30| 31| 32| written by Jochen Loewer 33| October, 2000 34| 35\--------------------------------------------------------------------------*/ 36 37/*--------------------------------------------------------------------------- 38| Includes 39| 40\--------------------------------------------------------------------------*/ 41#include <tcl.h> 42#include <stdlib.h> 43#include <string.h> 44#include <domalloc.h> 45 46 47/*--------------------------------------------------------------------------- 48| Defines 49| 50\--------------------------------------------------------------------------*/ 51#define DBG(x) 52#define MAX_BINS 256 53#define BIN_HASH_SIZE 512 54#define BIN_HASH_MASK 0x01FF 55#define CACHE_SIZE 4 56#define BLOCK_DATA_SIZE 31000 57#define BLOCK_SIZE_BITS 16 58 59 60/*--------------------------------------------------------------------------- 61| Typedefs 62| 63\--------------------------------------------------------------------------*/ 64typedef struct domAllocBlock { 65 struct domAllocBin * bin; 66 void * end; 67 struct domAllocBlock * prev; 68 struct domAllocBlock * next; 69 int hashIndex1; 70 struct domAllocBlock * hashNext1; 71 int hashIndex2; 72 struct domAllocBlock * hashNext2; 73 int slots; 74 int freeSlots; 75 int bitmaps; 76 int freePos; 77 int freeBit; 78 unsigned int freeMask; 79} domAllocBlock; 80 81 82typedef struct domAllocBin { 83 int size; 84 int nrSlots; 85 int freeSlots; 86 int nrBlocks; 87 domAllocBlock * freeBlocks; 88 domAllocBlock * usedBlocks; 89} domAllocBin; 90 91 92typedef struct domAllocBins { 93 struct domAllocBin * bin[MAX_BINS]; 94 struct domAllocBlock * hashedBlocks[BIN_HASH_SIZE]; 95 struct domAllocBlock * blockCache[CACHE_SIZE]; 96} domAllocBins; 97 98 99/*--------------------------------------------------------------------------- 100| Globals. This is a "single-threaded" allocator. 101| 102\--------------------------------------------------------------------------*/ 103static domAllocBins bins; 104 105#ifdef TCL_THREADS 106# define TDomThreaded(x) x 107 static Tcl_Mutex binMutex; 108#else 109# define TDomThreaded(x) 110#endif 111 112/*--------------------------------------------------------------------------- 113| domAllocInit 114| 115\--------------------------------------------------------------------------*/ 116void 117domAllocInit() 118{ 119 int i; 120 121 DBG(fprintf(stderr, "domAllocInit...\n");) 122 123 for (i=0; i < MAX_BINS; i++) bins.bin[i] = NULL; 124 for (i=0; i < CACHE_SIZE; i++) bins.blockCache[i] = NULL; 125 for (i=0; i < BIN_HASH_SIZE; i++) bins.hashedBlocks[i] = NULL; 126} 127 128 129/*-------------------------------------------------------------------------- 130| fillHashTable 131| 132\--------------------------------------------------------------------------*/ 133static void 134fillHashTable ( 135 domAllocBlock * block, 136 void * mem 137) 138{ 139 domAllocBlock * hashedBlock; 140 unsigned int i; 141 142 i = ( (unsigned int)mem >> BLOCK_SIZE_BITS) & BIN_HASH_MASK; 143 hashedBlock = bins.hashedBlocks[i]; 144 while (hashedBlock != NULL) { 145 if (hashedBlock == block) { 146 /* all is fine, block is already in hash table */ 147 return; 148 } 149 if (hashedBlock->hashIndex1 == (int)i) hashedBlock = hashedBlock->hashNext1; 150 else if (hashedBlock->hashIndex2 == (int)i) hashedBlock = hashedBlock->hashNext2; 151 else hashedBlock = NULL; 152 } 153 154 /* add block in hash table */ 155 if (block->hashIndex1 == -1) { 156 block->hashIndex1 = i; 157 block->hashNext1 = bins.hashedBlocks[i]; 158 } else 159 if (block->hashIndex2 == -1) { 160 block->hashIndex2 = i; 161 block->hashNext2 = bins.hashedBlocks[i]; 162 } else { 163 DBG( 164 fprintf(stderr, "\ntoo many hash entries for %x %x->%d %d,%d!\n", 165 (unsigned int)block, 166 (unsigned int)mem, i, block->hashIndex1, block->hashIndex2);) 167 } 168 bins.hashedBlocks[i] = block; 169} 170 171/*-------------------------------------------------------------------------- 172| domAlloc 173| 174\--------------------------------------------------------------------------*/ 175void * 176domAlloc ( 177 int size 178) 179{ 180 domAllocBin * bin; 181 domAllocBlock * block; 182 domAllocBlock * hashedBlock; 183 int i, j, slots, bitmaps, blockSize; 184 unsigned int mask; 185 char * mem; 186 unsigned int * usedBitmap; 187 188 189 DBG(fprintf(stderr, "\ndomAlloc %d \n", size);) 190 191 if (size >= MAX_BINS) { 192 DBG(fprintf(stderr, "\nSize too large as used for bin!\n");) 193 return NULL; 194 } 195 196 /*------------------------------------------------- 197 | FIXME 198 | 199 | Rewrite with TSD-based bins to avoid mutex 200 | contention. Threads are going to step on 201 | each other toes here which is not what we 202 | would like to have, don't we ? (zv) 203 \------------------------------------------------*/ 204 205 TDomThreaded(Tcl_MutexLock(&binMutex);) /* LOCK !*/ 206 207 if (bins.bin[size] == NULL) { 208 /*------------------------------------------------- 209 | create new bin 210 \------------------------------------------------*/ 211 bin = (domAllocBin *)malloc(sizeof(domAllocBin)); 212 bin->size = size; 213 bin->nrSlots = 0; 214 bin->freeSlots = 0; 215 bin->nrBlocks = 0; 216 bin->freeBlocks = NULL; 217 bin->usedBlocks = NULL; 218 219 bins.bin[size] = bin; 220 221 } else { 222 bin = bins.bin[size]; 223 } 224 225 if (bin->freeSlots == 0) { 226 DBG(fprintf(stderr, "allocating new block ... \n");) 227 /*---------------------------------------------------------------- 228 | allocate and initialize a new block 229 | 230 \---------------------------------------------------------------*/ 231 bitmaps = (BLOCK_DATA_SIZE / size) / 32; 232 slots = bitmaps * 32; 233 blockSize = sizeof(domAllocBlock) + bitmaps*4 + slots*size; 234 235 block = (domAllocBlock *)malloc( blockSize ); 236 block->bin = bin; 237 block->end = (char*)block + blockSize; 238 block->slots = slots; 239 block->freeSlots = slots; 240 block->bitmaps = bitmaps; 241 block->freePos = 0; 242 block->freeBit = 0; 243 block->freeMask = 0x80000000; 244 block->hashIndex1 = -1; 245 block->hashNext1 = NULL; 246 block->hashIndex2 = -1; 247 block->hashNext2 = NULL; 248 249 usedBitmap = (unsigned int *) ((char*)block + sizeof(domAllocBlock)); 250 memset(usedBitmap, 0, bitmaps * 4); 251 252 bin->nrSlots += slots; 253 bin->freeSlots += slots; 254 bin->nrBlocks++; 255 256 block->prev = NULL; /* prepend this new block to free list */ 257 block->next = bin->freeBlocks; 258 bin->freeBlocks = block; 259 260 /*--------------------------------------------------------- 261 | enter block in 'hash' table: 262 | first and last memory location could have different 263 | hash entries due to different upper address bits 264 \--------------------------------------------------------*/ 265 mem = (char*)usedBitmap + bitmaps * 4; 266 fillHashTable (block, mem); 267 mem += (slots-1) * size; 268 fillHashTable (block, mem); 269 270 } else { 271 block = bin->freeBlocks; 272 } 273 274 /*------------------------------------------------------------------------ 275 | find free slot in (partial) free block 276 | 277 \-----------------------------------------------------------------------*/ 278 usedBitmap = (unsigned int *) ((char*)block + sizeof(domAllocBlock)); 279 i = block->freePos; /* start at old pos to quickly find a free slot */ 280 j = block->freeBit; 281 mask = block->freeMask; 282 do { 283 DBG(fprintf(stderr, "looking %d slot i=%d j=%d %x mask %x\n", 284 size, i, j, usedBitmap[i], mask); ) 285 if (usedBitmap[i] != 0xFFFFFFFF) { 286 do { 287 if ((usedBitmap[i] & mask)==0) { 288 DBG(fprintf(stderr, "found free slot i=%d j=%d %x mask %x\n", 289 i, j, usedBitmap[i], mask); ) 290 mem = ((char*)usedBitmap) + (4*block->bitmaps) + ((i*32)+j) * size; 291 usedBitmap[i] |= mask; 292 block->freeSlots--; 293 bin->freeSlots--; 294 if (block->freeSlots == 0) { 295 DBG(fprintf(stderr, "freeSlots == 0\n");) 296 297 if (block->prev == NULL) { /* remove block from free list */ 298 bin->freeBlocks = block->next; 299 } else { 300 block->prev->next = block->next; 301 } 302 if (block->next) block->next->prev = block->prev; 303 304 block->next = bin->usedBlocks; /* add block to used list */ 305 if (block->next) block->next->prev = block; 306 block->prev = NULL; 307 bin->usedBlocks = block; 308 309 /* check consistency */ 310 hashedBlock = block->bin->freeBlocks; 311 while (hashedBlock) { 312 if (hashedBlock == block) { 313 DBG(fprintf(stderr, "strange block still in free list \n");) 314 } 315 hashedBlock = hashedBlock->next; 316 } 317 318 } 319 /* keep found free position for later, 320 * so that next slots can be found quickly 321 */ 322 block->freePos = i; 323 j++; mask = mask >> 1; 324 if (j >= 32) { j = 0; mask = 0x80000000; } 325 block->freeBit = j; 326 block->freeMask = mask; 327 328 TDomThreaded(Tcl_MutexUnlock(&binMutex);) /* UNLOCK !*/ 329 return mem; 330 } 331 j++; mask = mask >> 1; 332 if (j >= 32) { j = 0; mask = 0x80000000; } 333 } while (j != block->freeBit); 334 } 335 i++; 336 if (i >= block->bitmaps) i = 0; 337 } while (i != block->freePos); 338 339 /* TDomThreaded(Tcl_MutexUnlock(&binMutex);) */ 340 341 DBG(fprintf(stderr, "\ndomAlloc: can't happen! \n");) 342 *((char*)0) = 0; /* Use Tcl_Panic() for this ? */ 343 return NULL; 344} 345 346 347/*--------------------------------------------------------------------------- 348| domFree 349| 350\--------------------------------------------------------------------------*/ 351void 352domFree ( 353 void * mem 354) 355{ 356 domAllocBlock * block; 357 domAllocBlock * hashedBlock; 358 domAllocBlock * prevBlock; 359 int slotNr, i, foundInCache; 360 unsigned int * usedBitmap; 361 unsigned int mask; 362 363 DBG(fprintf(stderr, "domFree...\n");) 364 365 if (mem == NULL) return; 366 367 /*------------------------------------------------- 368 | FIXME (see domAlloc comments) 369 | 370 \------------------------------------------------*/ 371 372 TDomThreaded(Tcl_MutexLock(&binMutex);) 373 374 /*------------------------------------------------------------------- 375 | Find the block, which corresponds to the given memory location 376 | 377 | - First try to look in the memory range cache. 378 | 379 \------------------------------------------------------------------*/ 380 block = NULL; 381 foundInCache = 0; 382 for (i=0; i < CACHE_SIZE; i++) { 383 if ((bins.blockCache[i] != NULL) && 384 (mem > (void*)(bins.blockCache[i])) && 385 (mem < (void*)(bins.blockCache[i]->end))) { 386 block = bins.blockCache[i]; 387 foundInCache = 1; 388 break; 389 } 390 } 391 /*------------------------------------------------------------------- 392 | - Otherwise try to lookup corresponding block in hashtable 393 | 394 \------------------------------------------------------------------*/ 395 if (!foundInCache) { 396 i = ( (unsigned int)mem >> BLOCK_SIZE_BITS) & BIN_HASH_MASK; 397 block = bins.hashedBlocks[i]; 398 while (block != NULL) { 399 if ((mem > (void*)block) && (mem < (void*)(block->end))) break; 400 if (block->hashIndex1 == i) block = block->hashNext1; 401 else if (block->hashIndex2 == i) block = block->hashNext2; 402 else block = NULL; 403 } 404 } 405 406 if (block == NULL) { 407 DBG(fprintf(stderr, "\n unable to free mem %x !\n", (unsigned int)mem);) 408 TDomThreaded(Tcl_MutexUnlock(&binMutex);) 409 return; 410 } 411 412 /*------------------------------------------------------------------- 413 | clear the allocation bit 414 \------------------------------------------------------------------*/ 415 usedBitmap = (unsigned int *) ((char*)block + sizeof(domAllocBlock)); 416 slotNr = ( (char*)mem - (char*)usedBitmap - block->bitmaps*4 ) / block->bin->size; 417 DBG( 418 if (slotNr >= block->slots) { 419 fprintf(stderr, "assertion failed: slotNr = %d \n", slotNr); 420 }) 421 i = slotNr >> 5 ; /* slotNr / 32 */ 422 mask = 0x80000000 >> (slotNr % 32); 423 usedBitmap[i] &= ~mask; 424 block->freeSlots++; 425 block->bin->freeSlots++; 426 427 DBG( 428 if ((block->freeSlots < 1) || (block->freeSlots > block->slots)) { 429 fprintf(stderr, "assertion failed: freeSlots = %d \n", block->freeSlots); 430 }) 431 432 /*------------------------------------------------------------------- 433 | update free/used lists 434 \------------------------------------------------------------------*/ 435 if (block->freeSlots == 1) { 436 if (block->prev == NULL) { /* remove block from used list */ 437 block->bin->usedBlocks = block->next; 438 } else { 439 block->prev->next = block->next; 440 } 441 if (block->next) block->next->prev = block->prev; 442 443 block->next = block->bin->freeBlocks; /* add block to free list */ 444 if (block->next) block->next->prev = block; 445 block->prev = NULL; 446 block->bin->freeBlocks = block; 447 448 DBG( 449 /* check consistency */ 450 hashedBlock = block->bin->usedBlocks; 451 while (hashedBlock) { 452 if (hashedBlock == block) { 453 fprintf(stderr, "strange block still in used list \n"); 454 } 455 hashedBlock = hashedBlock->next; 456 } 457 ) 458 } 459 460 /*------------------------------------------------------------------- 461 | free the whole block, when all slots are freed 462 \------------------------------------------------------------------*/ 463 if (block->freeSlots == block->slots) { 464 465 DBG(fprintf(stderr, "block completely freed %x\n", 466 (unsigned int)block);) 467 468 if (block->prev == NULL) { /* remove block from free list */ 469 block->bin->freeBlocks = block->next; 470 } else { 471 block->prev->next = block->next; 472 } 473 if (block->next) block->next->prev = block->prev; 474 475 block->bin->nrSlots -= block->slots; 476 block->bin->freeSlots -= block->slots; 477 block->bin->nrBlocks--; 478 479 /*-------------------------------------------------------------------- 480 | remove block from (two) hash lists 481 \-------------------------------------------------------------------*/ 482 i = block->hashIndex1; 483 if (i != -1) { 484 DBG(fprintf(stderr, "remove from hash list %d \n", i);) 485 prevBlock = NULL; 486 hashedBlock = bins.hashedBlocks[i]; 487 while (hashedBlock) { 488 if (hashedBlock == block) break; 489 prevBlock = hashedBlock; 490 if (hashedBlock->hashIndex1 == i) hashedBlock = hashedBlock->hashNext1; 491 else if (hashedBlock->hashIndex2 == i) hashedBlock = hashedBlock->hashNext2; 492 else hashedBlock = NULL; 493 } 494 if (prevBlock == NULL) { 495 bins.hashedBlocks[i] = block->hashNext1; 496 } else { 497 if (prevBlock->hashIndex1 == i) prevBlock->hashNext1 = block->hashNext1; 498 else if (prevBlock->hashIndex2 == i) prevBlock->hashNext2 = block->hashNext1; 499 } 500 } 501 i = block->hashIndex2; 502 if (i != -1) { 503 DBG(fprintf(stderr, "remove from hash list %d \n", i);) 504 prevBlock = NULL; 505 hashedBlock = bins.hashedBlocks[i]; 506 while (hashedBlock) { 507 if (hashedBlock == block) break; 508 prevBlock = hashedBlock; 509 if (hashedBlock->hashIndex1 == i) hashedBlock = hashedBlock->hashNext1; 510 else if (hashedBlock->hashIndex2 == i) hashedBlock = hashedBlock->hashNext2; 511 else hashedBlock = NULL; 512 } 513 if (prevBlock == NULL) { 514 bins.hashedBlocks[i] = block->hashNext2; 515 } else { 516 if (prevBlock->hashIndex1 == i) prevBlock->hashNext1 = block->hashNext2; 517 else if (prevBlock->hashIndex2 == i) prevBlock->hashNext2 = block->hashNext2; 518 } 519 } 520 521 /*------------------------------------------------------ 522 | remove block from cache, if found 523 \-----------------------------------------------------*/ 524 for (i=0; i < CACHE_SIZE; i++) { 525 if (bins.blockCache[i] == block) { 526 bins.blockCache[i] = NULL; 527 } 528 } 529 530 DBG( 531 /* check consistency */ 532 for (i=0; i < block->bitmaps; i++) { 533 if (usedBitmap[i] != 0) { 534 fprintf(stderr, "strange bitmap %d is %x \n", i, usedBitmap[i]); 535 } 536 } 537 for (i=0; i < BIN_HASH_SIZE; i++) { 538 hashedBlock = bins.hashedBlocks[i]; 539 while (hashedBlock) { 540 if (hashedBlock == block) { 541 fprintf(stderr, "strange block %d still in hash table \n", i); 542 } 543 if (hashedBlock->hashIndex1 == i) hashedBlock = hashedBlock->hashNext1; 544 else if (hashedBlock->hashIndex2 == i) hashedBlock = hashedBlock->hashNext2; 545 else hashedBlock = NULL; 546 } 547 } 548 hashedBlock = block->bin->freeBlocks; 549 while (hashedBlock) { 550 if (hashedBlock == block) { 551 fprintf(stderr, "strange block still in free list \n"); 552 } 553 hashedBlock = hashedBlock->next; 554 } 555 hashedBlock = block->bin->usedBlocks; 556 while (hashedBlock) { 557 if (hashedBlock == block) { 558 fprintf(stderr, "strange block still in used list \n"); 559 } 560 hashedBlock = hashedBlock->next; 561 } 562 ) 563 free((char*)block); 564 565 } else { 566 /*----------------------------------------------------------- 567 | update cache 568 \----------------------------------------------------------*/ 569 if (!foundInCache) { 570 /* remove oldest entry and add this block */ 571 for (i=1; i < CACHE_SIZE; i++) { 572 bins.blockCache[i-1] = bins.blockCache[i]; 573 } 574 bins.blockCache[CACHE_SIZE-1] = block; 575 } 576 } 577 TDomThreaded(Tcl_MutexUnlock(&binMutex);) /* UNLOCK !*/ 578} 579