dep/src/g3dlite/System.cpp

   1 /**
   2   @file System.cpp
   3
   4   @maintainer Morgan McGuire, matrix@graphics3d.com
   5
   6   Note: every routine must call init() first.
   7
   8   There are two kinds of detection used in this file.  At compile
   9   time, the _MSC_VER #define is used to determine whether x86 assembly
  10   can be used at all.  At runtime, processor detection is used to
  11   determine if we can safely call the routines that use that assembly.
  12
  13   @cite Rob Wyatt http://www.gamasutra.com/features/wyatts_world/19990709/processor_detection_01.htm
  14   @cite Benjamin Jurke http://www.flipcode.com/cgi-bin/msg.cgi?showThread=COTD-ProcessorDetectionClass&forum=cotd&id=-1
  15   @cite Michael Herf http://www.stereopsis.com/memcpy.html
  16
  17   @created 2003-01-25
  18   @edited  2006-05-17
  19  */
  20
  21 #include "G3D/platform.h"
  22 #include "G3D/System.h"
  23 #include "G3D/debug.h"
  24 #include "G3D/format.h"
  25
  26 #if defined(__OpenBSD__)
  27     #include <stdint.h>
  28 #endif
  29
  30 #ifdef G3D_WIN32
  31
  32     #include <conio.h>
  33     #include <sys/timeb.h>
  34     #include "G3D/RegistryUtil.h"
  35
  36 #elif defined(G3D_LINUX)
  37
  38     #include <stdlib.h>
  39     #include <stdio.h>
  40     #include <string.h>
  41     #include <errno.h>
  42     #include <sys/types.h>
  43     #include <sys/select.h>
  44     #include <termios.h>
  45     #include <unistd.h>
  46     #include <sys/ioctl.h>
  47     #include <sys/time.h>
  48     #include <pthread.h>
  49
  50     // #include <assert.h>
  51
  52 #elif defined(G3D_OSX)
  53
  54     #include <stdlib.h>
  55     #include <stdio.h>
  56     #include <errno.h>
  57     #include <sys/types.h>
  58     #include <sys/sysctl.h>
  59     #include <sys/select.h>
  60     #include <sys/time.h>
  61     #include <termios.h>
  62     #include <unistd.h>
  63     #include <pthread.h>
  64     #include <mach-o/arch.h>
  65
  66     #include <sstream>
  67     #include <CoreServices/CoreServices.h>
  68 #endif
  69
  70 #if defined(SSE)
  71     #include <xmmintrin.h>
  72 #endif
  73
  74 namespace G3D {
  75
  76 static char                                     versionCstr[1024];
  77 System::OutOfMemoryCallback                     System::outOfMemoryCallback = NULL;
  78
  79
  80 void System::init() {
  81     // Cannot use most G3D data structures or utility functions in here because
  82     // they are not initialized.
  83
  84     static bool initialized = false;
  85
  86     if (initialized) {
  87         return;
  88     }
  89
  90     initialized = true;
  91
  92     if ((G3D_VER % 100) != 0) {
  93         sprintf(versionCstr, "G3D %d.%02d beta %d",
  94             G3D_VER / 10000,
  95             (G3D_VER / 100) % 100,
  96             G3D_VER % 100);
  97     } else {
  98         sprintf(versionCstr, "G3D %d.%02d",
  99             G3D_VER / 10000,
 100             (G3D_VER / 100) % 100);
 101     }
 102
 103 }
 104
 105
 106
 107 void System::memcpy(void* dst, const void* src, size_t numBytes) {
 108         ::memcpy(dst, src, numBytes);
 109 }
 110
 111
 112 void System::memset(void* dst, uint8 value, size_t numBytes) {
 113         ::memset(dst, value, numBytes);
 114 }
 115
 116
 117
 118
 119
 120 ////////////////////////////////////////////////////////////////
 121 class BufferPool {
 122 public:
 123
 124     /** Only store buffers up to these sizes (in bytes) in each pool->
 125         Different pools have different management strategies.
 126
 127         A large block is preallocated for tiny buffers; they are used with
 128         tremendous frequency.  Other buffers are allocated as demanded.
 129       */
 130     enum {tinyBufferSize = 128, smallBufferSize = 1024, medBufferSize = 4096};
 131
 132     /**
 133        Most buffers we're allowed to store.
 134        64000 * 128  = 8 MB (preallocated)
 135         1024 * 1024 = 1 MB (allocated on demand)
 136         1024 * 4096 = 4 MB (allocated on demand)
 137      */
 138     enum {maxTinyBuffers = 64000, maxSmallBuffers = 1024, maxMedBuffers = 1024};
 139
 140 private:
 141
 142     class MemBlock {
 143     public:
 144         void*           ptr;
 145         size_t          bytes;
 146
 147         inline MemBlock() : ptr(NULL), bytes(0) {}
 148         inline MemBlock(void* p, size_t b) : ptr(p), bytes(b) {}
 149     };
 150
 151     MemBlock smallPool[maxSmallBuffers];
 152     int smallPoolSize;
 153
 154     MemBlock medPool[maxMedBuffers];
 155     int medPoolSize;
 156
 157     /** The tiny pool is a single block of storage into which all tiny
 158         objects are allocated.  This provides better locality for
 159         small objects and avoids the search time, since all tiny
 160         blocks are exactly the same size. */
 161     void* tinyPool[maxTinyBuffers];
 162     int tinyPoolSize;
 163
 164     /** Pointer to the data in the tiny pool */
 165     void* tinyHeap;
 166
 167 #   ifdef G3D_WIN32
 168     CRITICAL_SECTION    mutex;
 169 #   else
 170     pthread_mutex_t     mutex;
 171 #   endif
 172
 173     /** Provide synchronization between threads */
 174     void lock() {
 175 #       ifdef G3D_WIN32
 176             EnterCriticalSection(&mutex);
 177 #       else
 178             pthread_mutex_lock(&mutex);
 179 #       endif
 180     }
 181
 182     void unlock() {
 183 #       ifdef G3D_WIN32
 184             LeaveCriticalSection(&mutex);
 185 #       else
 186             pthread_mutex_unlock(&mutex);
 187 #       endif
 188     }
 189
 190     /**
 191      Malloc out of the tiny heap.
 192      */
 193     inline void* tinyMalloc(size_t bytes) {
 194         // Note that we ignore the actual byte size
 195         // and create a constant size block.
 196         (void)bytes;
 197         debugAssert(tinyBufferSize >= bytes);
 198
 199         void* ptr = NULL;
 200
 201         if (tinyPoolSize > 0) {
 202             --tinyPoolSize;
 203             // Return the last one
 204             ptr = tinyPool[tinyPoolSize];
 205         }
 206
 207         return ptr;
 208     }
 209
 210     /** Returns true if this is a pointer into the tiny heap. */
 211     bool inTinyHeap(void* ptr) {
 212         return (ptr >= tinyHeap) &&
 213                (ptr < (uint8*)tinyHeap + maxTinyBuffers * tinyBufferSize);
 214     }
 215
 216     void tinyFree(void* ptr) {
 217         debugAssert(tinyPoolSize < maxTinyBuffers);
 218
 219         // Put the pointer back into the free list
 220         tinyPool[tinyPoolSize] = ptr;
 221         ++tinyPoolSize;
 222
 223     }
 224
 225     void flushPool(MemBlock* pool, int& poolSize) {
 226         for (int i = 0; i < poolSize; ++i) {
 227             ::free(pool->ptr);
 228             pool->ptr = NULL;
 229             pool->bytes = 0;
 230         }
 231         poolSize = 0;
 232     }
 233
 234
 235     /**  Allocate out of a specific pool->  Return NULL if no suitable
 236          memory was found.
 237
 238          */
 239     void* malloc(MemBlock* pool, int& poolSize, size_t bytes) {
 240
 241         // OPT: find the smallest block that satisfies the request.
 242
 243         // See if there's something we can use in the buffer pool->
 244         // Search backwards since usually we'll re-use the last one.
 245         for (int i = (int)poolSize - 1; i >= 0; --i) {
 246             if (pool[i].bytes >= bytes) {
 247                 // We found a suitable entry in the pool->
 248
 249                 // No need to offset the pointer; it is already offset
 250                 void* ptr = pool[i].ptr;
 251
 252                 // Remove this element from the pool
 253                 --poolSize;
 254                 pool[i] = pool[poolSize];
 255
 256                 return ptr;
 257             }
 258         }
 259
 260         return NULL;
 261     }
 262
 263 public:
 264
 265     /** Count of memory allocations that have occurred. */
 266     int totalMallocs;
 267     int mallocsFromTinyPool;
 268     int mallocsFromSmallPool;
 269     int mallocsFromMedPool;
 270
 271     /** Amount of memory currently allocated (according to the application).
 272         This does not count the memory still remaining in the buffer pool,
 273         but does count extra memory required for rounding off to the size
 274         of a buffer.
 275         Primarily useful for detecting leaks.*/
 276     // TODO: make me an atomic int!
 277     int bytesAllocated;
 278
 279     BufferPool() {
 280         totalMallocs         = 0;
 281
 282         mallocsFromTinyPool  = 0;
 283         mallocsFromSmallPool = 0;
 284         mallocsFromMedPool   = 0;
 285
 286         bytesAllocated       = true;
 287
 288         tinyPoolSize         = 0;
 289         tinyHeap             = NULL;
 290
 291         smallPoolSize        = 0;
 292
 293         medPoolSize          = 0;
 294
 295
 296         // Initialize the tiny heap as a bunch of pointers into one
 297         // pre-allocated buffer.
 298         tinyHeap = ::malloc(maxTinyBuffers * tinyBufferSize);
 299         for (int i = 0; i < maxTinyBuffers; ++i) {
 300             tinyPool[i] = (uint8*)tinyHeap + (tinyBufferSize * i);
 301         }
 302         tinyPoolSize = maxTinyBuffers;
 303
 304 #       ifdef G3D_WIN32
 305             InitializeCriticalSection(&mutex);
 306 #       else
 307             pthread_mutex_init(&mutex, NULL);
 308 #       endif
 309     }
 310
 311
 312     ~BufferPool() {
 313         ::free(tinyHeap);
 314 #       ifdef G3D_WIN32
 315             DeleteCriticalSection(&mutex);
 316 #       else
 317             // No destruction on pthreads
 318 #       endif
 319     }
 320
 321
 322     void* realloc(void* ptr, size_t bytes) {
 323         if (ptr == NULL) {
 324             return malloc(bytes);
 325         }
 326
 327         if (inTinyHeap(ptr)) {
 328             if (bytes <= tinyBufferSize) {
 329                 // The old pointer actually had enough space.
 330                 return ptr;
 331             } else {
 332                 // Free the old pointer and malloc
 333
 334                 void* newPtr = malloc(bytes);
 335                 System::memcpy(newPtr, ptr, tinyBufferSize);
 336                 tinyFree(ptr);
 337                 return newPtr;
 338
 339             }
 340         } else {
 341             // In one of our heaps.
 342
 343             // See how big the block really was
 344             size_t realSize = ((uint32*)ptr)[-1];
 345             if (bytes <= realSize) {
 346                 // The old block was big enough.
 347                 return ptr;
 348             }
 349
 350             // Need to reallocate
 351             void* newPtr = malloc(bytes);
 352             System::memcpy(newPtr, ptr, realSize);
 353             free(ptr);
 354             return newPtr;
 355         }
 356     }
 357
 358
 359     void* malloc(size_t bytes) {
 360         lock();
 361         ++totalMallocs;
 362
 363         if (bytes <= tinyBufferSize) {
 364
 365             void* ptr = tinyMalloc(bytes);
 366
 367             if (ptr) {
 368                 ++mallocsFromTinyPool;
 369                 unlock();
 370                 return ptr;
 371             }
 372
 373         }
 374
 375         // Failure to allocate a tiny buffer is allowed to flow
 376         // through to a small buffer
 377         if (bytes <= smallBufferSize) {
 378
 379             void* ptr = malloc(smallPool, smallPoolSize, bytes);
 380
 381             if (ptr) {
 382                 ++mallocsFromSmallPool;
 383                 unlock();
 384                 return ptr;
 385             }
 386
 387         } else  if (bytes <= medBufferSize) {
 388             // Note that a small allocation failure does *not* fall
 389             // through into a medium allocation because that would
 390             // waste the medium buffer's resources.
 391
 392             void* ptr = malloc(medPool, medPoolSize, bytes);
 393
 394             if (ptr) {
 395                 ++mallocsFromMedPool;
 396                 unlock();
 397                 return ptr;
 398             }
 399         }
 400
 401         bytesAllocated += 4 + (int) bytes;
 402         unlock();
 403
 404         // Heap allocate
 405
 406         // Allocate 4 extra bytes for our size header (unfortunate,
 407         // since malloc already added its own header).
 408         void* ptr = ::malloc(bytes + 4);
 409
 410         if (ptr == NULL) {
 411             // Flush memory pools to try and recover space
 412             flushPool(smallPool, smallPoolSize);
 413             flushPool(medPool, medPoolSize);
 414             ptr = ::malloc(bytes + 4);
 415         }
 416
 417
 418         if (ptr == NULL) {
 419             if ((System::outOfMemoryCallback != NULL) &&
 420                 (System::outOfMemoryCallback(bytes + 4, true) == true)) {
 421                 // Re-attempt the malloc
 422                 ptr = ::malloc(bytes + 4);
 423             }
 424         }
 425
 426         if (ptr == NULL) {
 427             if (System::outOfMemoryCallback != NULL) {
 428                 // Notify the application
 429                 System::outOfMemoryCallback(bytes + 4, false);
 430             }
 431             return NULL;
 432         }
 433
 434         *(uint32*)ptr = (uint32)bytes;
 435
 436         return (uint8*)ptr + 4;
 437     }
 438
 439
 440     void free(void* ptr) {
 441         if (ptr == NULL) {
 442             // Free does nothing on null pointers
 443             return;
 444         }
 445
 446         debugAssert(isValidPointer(ptr));
 447
 448         if (inTinyHeap(ptr)) {
 449             lock();
 450             tinyFree(ptr);
 451             unlock();
 452             return;
 453         }
 454
 455         uint32 bytes = ((uint32*)ptr)[-1];
 456
 457         lock();
 458         if (bytes <= smallBufferSize) {
 459             if (smallPoolSize < maxSmallBuffers) {
 460                 smallPool[smallPoolSize] = MemBlock(ptr, bytes);
 461                 ++smallPoolSize;
 462                 unlock();
 463                 return;
 464             }
 465         } else if (bytes <= medBufferSize) {
 466             if (medPoolSize < maxMedBuffers) {
 467                 medPool[medPoolSize] = MemBlock(ptr, bytes);
 468                 ++medPoolSize;
 469                 unlock();
 470                 return;
 471             }
 472         }
 473         bytesAllocated -= bytes + 4;
 474         unlock();
 475
 476         // Free; the buffer pools are full or this is too big to store.
 477         ::free((uint8*)ptr - 4);
 478     }
 479
 480     std::string performance() const {
 481         if (totalMallocs > 0) {
 482             int pooled = mallocsFromTinyPool +
 483                          mallocsFromSmallPool +
 484                          mallocsFromMedPool;
 485
 486             int total = totalMallocs;
 487
 488             return format("malloc performance: %5.1f%% <= %db, %5.1f%% <= %db, "
 489                           "%5.1f%% <= %db, %5.1f%% > %db",
 490                           100.0 * mallocsFromTinyPool  / total,
 491                           BufferPool::tinyBufferSize,
 492                           100.0 * mallocsFromSmallPool / total,
 493                           BufferPool::smallBufferSize,
 494                           100.0 * mallocsFromMedPool   / total,
 495                           BufferPool::medBufferSize,
 496                           100.0 * (1.0 - (double)pooled / total),
 497                           BufferPool::medBufferSize);
 498         } else {
 499             return "No System::malloc calls made yet.";
 500         }
 501     }
 502
 503     std::string status() const {
 504         return format("preallocated shared buffers: %5d/%d x %db",
 505             maxTinyBuffers - tinyPoolSize, maxTinyBuffers, tinyBufferSize);
 506     }
 507 };
 508
 509 // Dynamically allocated because we need to ensure that
 510 // the buffer pool is still around when the last global variable
 511 // is deallocated.
 512 static BufferPool* bufferpool = NULL;
 513
 514 std::string System::mallocPerformance() {
 515 #ifndef NO_BUFFERPOOL
 516     return bufferpool->performance();
 517 #else
 518         return "NO_BUFFERPOOL";
 519 #endif
 520 }
 521
 522 std::string System::mallocStatus() {
 523 #ifndef NO_BUFFERPOOL
 524     return bufferpool->status();
 525 #else
 526         return "NO_BUFFERPOOL";
 527 #endif
 528 }
 529
 530
 531 void System::resetMallocPerformanceCounters() {
 532 #ifndef NO_BUFFERPOOL
 533     bufferpool->totalMallocs         = 0;
 534     bufferpool->mallocsFromMedPool   = 0;
 535     bufferpool->mallocsFromSmallPool = 0;
 536     bufferpool->mallocsFromTinyPool  = 0;
 537 #endif
 538 }
 539
 540
 541 #ifndef NO_BUFFERPOOL
 542 inline void initMem() {
 543     // Putting the test here ensures that the system is always
 544     // initialized, even when globals are being allocated.
 545     static bool initialized = false;
 546     if (! initialized) {
 547         bufferpool = new BufferPool();
 548         initialized = true;
 549     }
 550 }
 551 #endif
 552
 553
 554 void* System::malloc(size_t bytes) {
 555 #ifndef NO_BUFFERPOOL
 556     initMem();
 557     return bufferpool->malloc(bytes);
 558 #else
 559     return ::malloc(bytes);
 560 #endif
 561 }
 562
 563 void* System::calloc(size_t n, size_t x) {
 564 #ifndef NO_BUFFERPOOL
 565     void* b = System::malloc(n * x);
 566     System::memset(b, 0, n * x);
 567     return b;
 568 #else
 569     return ::calloc(n, x);
 570 #endif
 571 }
 572
 573
 574 void* System::realloc(void* block, size_t bytes) {
 575 #ifndef NO_BUFFERPOOL
 576     initMem();
 577     return bufferpool->realloc(block, bytes);
 578 #else
 579         return ::realloc(block, bytes);
 580 #endif
 581 }
 582
 583
 584 void System::free(void* p) {
 585 #ifndef NO_BUFFERPOOL
 586     bufferpool->free(p);
 587 #else
 588         return ::free(p);
 589 #endif
 590 }
 591
 592
 593 void* System::alignedMalloc(size_t bytes, size_t alignment) {
 594     alwaysAssertM(isPow2(alignment), "alignment must be a power of 2");
 595
 596     // We must align to at least a word boundary.
 597     alignment = iMax((int)alignment, sizeof(void *));
 598
 599     // Pad the allocation size with the alignment size and the
 600     // size of the redirect pointer.
 601     size_t totalBytes = bytes + alignment + sizeof(intptr_t);
 602
 603     void* truePtr = System::malloc(totalBytes);
 604
 605     if (!truePtr) {
 606         // malloc returned NULL
 607         return NULL;
 608     }
 609
 610     debugAssert(isValidHeapPointer(truePtr));
 611     #ifdef G3D_WIN32
 612     // The blocks we return will not be valid Win32 debug heap
 613     // pointers because they are offset
 614     //  debugAssert(_CrtIsValidPointer(truePtr, totalBytes, TRUE) );
 615     #endif
 616
 617     // The return pointer will be the next aligned location (we must at least
 618     // leave space for the redirect pointer, however).
 619     char* alignedPtr = ((char*)truePtr)+ sizeof(intptr_t);
 620
 621 #if 0
 622     // 2^n - 1 has the form 1111... in binary.
 623     uint32 bitMask = (alignment - 1);
 624
 625     // Advance forward until we reach an aligned location.
 626     while ((((intptr_t)alignedPtr) & bitMask) != 0) {
 627         alignedPtr += sizeof(void*);
 628     }
 629 #else
 630     alignedPtr += alignment - (((intptr_t)alignedPtr) & (alignment - 1));
 631     // assert((alignedPtr - truePtr) + bytes <= totalBytes);
 632 #endif
 633
 634     debugAssert((alignedPtr - truePtr) + bytes <= totalBytes);
 635
 636     // Immediately before the aligned location, write the true array location
 637     // so that we can free it correctly.
 638     intptr_t* redirectPtr = (intptr_t*)(alignedPtr - sizeof(intptr_t));
 639     redirectPtr[0] = (intptr_t)truePtr;
 640
 641     debugAssert(isValidHeapPointer(truePtr));
 642
 643     #ifdef G3D_WIN32
 644         debugAssert( _CrtIsValidPointer(alignedPtr, bytes, TRUE) );
 645     #endif
 646     return (void*)alignedPtr;
 647 }
 648
 649
 650 void System::alignedFree(void* _ptr) {
 651     if (_ptr == NULL) {
 652         return;
 653     }
 654
 655     char* alignedPtr = (char*)_ptr;
 656
 657     // Back up one word from the pointer the user passed in.
 658     // We now have a pointer to a pointer to the true start
 659     // of the memory block.
 660     intptr_t* redirectPtr = (intptr_t*)(alignedPtr - sizeof(intptr_t));
 661
 662     // Dereference that pointer so that ptr = true start
 663     void* truePtr = (void*)(redirectPtr[0]);
 664
 665     debugAssert(isValidHeapPointer(truePtr));
 666     System::free(truePtr);
 667 }
 668
 669
 670 }  // namespace