00001
00030 #ifndef GALOIS_RUNTIME_MEM_H
00031 #define GALOIS_RUNTIME_MEM_H
00032
00033 #include "Galois/Runtime/PerThreadStorage.h"
00034 #include "Galois/Runtime/ll/SimpleLock.h"
00035 #include "Galois/Runtime/ll/PtrLock.h"
00036 #include "Galois/Runtime/ll/CacheLineStorage.h"
00037
00038
00039 #include <boost/utility.hpp>
00040 #include <cstdlib>
00041 #include <cstring>
00042 #include <map>
00043 #include <cstddef>
00044
00045 #include <memory.h>
00046
00047 namespace Galois {
00048 namespace Runtime {
00050 namespace MM {
00051
00052 const size_t smallPageSize = 4*1024;
00053 const size_t pageSize = 2*1024*1024;
00054 void* pageAlloc();
00055 void pageFree(void*);
00057 void pagePreAlloc(int numpages);
00059 void pageIn(void *buf, size_t len);
00060
00062 int numPageAllocTotal();
00064 int numPageAllocForThread(unsigned tid);
00065
00067 int numNumaAllocForNode(unsigned nodeid);
00069 int numNumaNodes();
00070
00078 void* largeInterleavedAlloc(size_t bytes, bool full = true);
00080 void largeInterleavedFree(void* mem, size_t bytes);
00081
00083 void* largeAlloc(size_t bytes, bool preFault = true);
00085 void largeFree(void* mem, size_t bytes);
00086
00088 void printInterleavedStats(int minPages = 16*1024);
00089
00091 template<class LocalHeap>
00092 class ThreadAwarePrivateHeap {
00093 PerThreadStorage<LocalHeap> heaps;
00094
00095 public:
00096 enum { AllocSize = LocalHeap::AllocSize };
00097
00098 ThreadAwarePrivateHeap() {}
00099 ~ThreadAwarePrivateHeap() {
00100 clear();
00101 }
00102
00103 inline void* allocate(size_t size) {
00104 return heaps.getLocal()->allocate(size);
00105 }
00106
00107 inline void deallocate(void* ptr) {
00108 heaps.getLocal()->deallocate(ptr);
00109 }
00110
00111 void clear() {
00112 for (unsigned int i = 0; i < heaps.size(); i++)
00113 heaps.getRemote(i)->clear();
00114 }
00115 };
00116
00118 template<class RealHeap>
00119 class LockedHeap : public RealHeap {
00120 LL::SimpleLock<true> lock;
00121 public :
00122 enum { AllocSize = RealHeap::AllocSize };
00123
00124 inline void* allocate(size_t size) {
00125 lock.lock();
00126 void* retval = RealHeap::allocate(size);
00127 lock.unlock();
00128 return retval;
00129 }
00130
00131 inline void deallocate(void* ptr) {
00132 lock.lock();
00133 RealHeap::deallocate(ptr);
00134 lock.unlock();
00135 }
00136 };
00137
00138 template<typename SourceHeap>
00139 class ZeroOut : public SourceHeap {
00140 public:
00141 enum { AllocSize = SourceHeap::AllocSize } ;
00142 inline void* allocate(size_t size) {
00143 void* retval = SourceHeap::allocate(size);
00144 memset(retval, 0, size);
00145 return retval;
00146 }
00147
00148 inline void deallocate(void* ptr) {
00149 SourceHeap::deallocate(ptr);
00150 }
00151 };
00152
00154 template<typename Header, typename SourceHeap>
00155 class AddHeader : public SourceHeap {
00156 enum { offset = (sizeof(Header) + (sizeof(double) - 1)) & ~(sizeof(double) - 1) };
00157
00158 public:
00159 inline void* allocate(size_t size) {
00160
00161 void* ptr = SourceHeap::allocate(size + offset);
00162
00163 return (char*)ptr + offset;
00164 }
00165
00166 inline void deallocate(void* ptr) {
00167 SourceHeap::deallocate(getHeader(ptr));
00168 }
00169
00170 inline static Header* getHeader(void* ptr) {
00171 return (Header*)((char*)ptr - offset);
00172 }
00173 };
00174
00176 template<class SourceHeap>
00177 class OwnerTaggedHeap : public AddHeader<void*, SourceHeap> {
00178 typedef AddHeader<OwnerTaggedHeap*, SourceHeap> Src;
00179 public:
00180 inline void* allocate(size_t size) {
00181 void* retval = Src::allocate(size);
00182 *(Src::getHeader(retval)) = this;
00183 return retval;
00184 }
00185
00186 inline void deallocate(void* ptr) {
00187 assert(*(Src::getHeader(ptr)) == this);
00188 Src::deallocate(ptr);
00189 }
00190
00191 inline static OwnerTaggedHeap* owner(void* ptr) {
00192 return *(OwnerTaggedHeap**)Src::getHeader(ptr);
00193 }
00194 };
00195
00197 template<class SourceHeap>
00198 class FreeListHeap : public SourceHeap {
00199 struct FreeNode {
00200 FreeNode* next;
00201 };
00202 FreeNode* head;
00203
00204 public:
00205 enum { AllocSize = SourceHeap::AllocSize };
00206
00207 void clear() {
00208 while (head) {
00209 FreeNode* N = head;
00210 head = N->next;
00211 SourceHeap::deallocate(N);
00212 }
00213 }
00214
00215 FreeListHeap() : head(0) {}
00216 ~FreeListHeap() {
00217 clear();
00218 }
00219
00220 inline void* allocate(size_t size) {
00221 if (head) {
00222 void* ptr = head;
00223 head = head->next;
00224 return ptr;
00225 }
00226 return SourceHeap::allocate(size);
00227 }
00228
00229 inline void deallocate(void* ptr) {
00230 if (!ptr) return;
00231 assert((uintptr_t)ptr > 0x100);
00232 FreeNode* NH = (FreeNode*)ptr;
00233 NH->next = head;
00234 head = NH;
00235 }
00236
00237 };
00238
00240 template<class SourceHeap>
00241 class SelfLockFreeListHeap : public SourceHeap {
00242 struct FreeNode {
00243 FreeNode* next;
00244 };
00245 FreeNode* head;
00246
00247 public:
00248 enum { AllocSize = SourceHeap::AllocSize };
00249
00250 void clear() {
00251 FreeNode* h = 0;
00252 do {
00253 h = head;
00254 } while (!__sync_bool_compare_and_swap(&head, h, 0));
00255 while (h) {
00256 FreeNode* N = h;
00257 h = N->next;
00258 SourceHeap::deallocate(N);
00259 }
00260 }
00261
00262 SelfLockFreeListHeap() : head(0) {}
00263 ~SelfLockFreeListHeap() {
00264 clear();
00265 }
00266
00267 inline void* allocate(size_t size) {
00268 static LL::SimpleLock<true> lock;
00269
00270 lock.lock();
00271 FreeNode* OH = 0;
00272 FreeNode* NH = 0;
00273 do {
00274 OH = head;
00275 if (!OH) {
00276 lock.unlock();
00277 return SourceHeap::allocate(size);
00278 }
00279 NH = OH->next;
00280 } while (!__sync_bool_compare_and_swap(&head, OH, NH));
00281 lock.unlock();
00282 assert(OH);
00283 return (void*)OH;
00284 }
00285
00286 inline void deallocate(void* ptr) {
00287 if (!ptr) return;
00288 FreeNode* OH;
00289 FreeNode* NH;
00290 do {
00291 OH = head;
00292 NH = (FreeNode*)ptr;
00293 NH->next = OH;
00294 } while (!__sync_bool_compare_and_swap(&head, OH, NH));
00295 }
00296
00297 };
00298
00299 template<unsigned ElemSize, typename SourceHeap>
00300 class BlockAlloc : public SourceHeap {
00301
00302 struct TyEq {
00303 double data[((ElemSize + sizeof(double) - 1) & ~(sizeof(double) - 1))/sizeof(double)];
00304 };
00305
00306 struct Block_basic {
00307 union {
00308 Block_basic* next;
00309 double dummy;
00310 };
00311 TyEq data[1];
00312 };
00313
00314 enum {BytesLeft = (SourceHeap::AllocSize - sizeof(Block_basic)),
00315 BytesLeftR = BytesLeft & ~(sizeof(double) - 1),
00316 FitLeft = BytesLeftR / sizeof(TyEq[1]),
00317 TotalFit = FitLeft + 1
00318 };
00319
00320 struct Block {
00321 union {
00322 Block* next;
00323 double dummy;
00324 };
00325 TyEq data[TotalFit];
00326 };
00327
00328 Block* head;
00329 int headIndex;
00330
00331 void refill() {
00332 void* P = SourceHeap::allocate(SourceHeap::AllocSize);
00333 Block* BP = (Block*)P;
00334 BP->next = head;
00335 head = BP;
00336 headIndex = 0;
00337 }
00338 public:
00339 enum { AllocSize = ElemSize };
00340
00341 void clear() {
00342 while(head) {
00343 Block* B = head;
00344 head = B->next;
00345 SourceHeap::deallocate(B);
00346 }
00347 }
00348
00349 BlockAlloc() :SourceHeap(), head(0), headIndex(0) {
00350
00351 assert(sizeof(Block) <= SourceHeap::AllocSize);
00352 }
00353
00354 ~BlockAlloc() {
00355 clear();
00356 }
00357
00358 inline void* allocate(size_t size) {
00359 assert(size == ElemSize);
00360 if (!head || headIndex == TotalFit)
00361 refill();
00362 return &head->data[headIndex++];
00363 }
00364
00365 inline void deallocate(void* ptr) {}
00366
00367 };
00368
00370 template<typename SourceHeap>
00371 class SimpleBumpPtr : public SourceHeap {
00372
00373 struct Block {
00374 union {
00375 Block* next;
00376 double dummy;
00377 };
00378 };
00379
00380 Block* head;
00381 int offset;
00382
00383 void refill() {
00384 void* P = SourceHeap::allocate(SourceHeap::AllocSize);
00385 Block* BP = (Block*)P;
00386 BP->next = head;
00387 head = BP;
00388 offset = sizeof(Block);
00389 }
00390 public:
00391 enum { AllocSize = 0 };
00392
00393 SimpleBumpPtr(): SourceHeap(), head(0), offset(0) {}
00394 ~SimpleBumpPtr() {
00395 clear();
00396 }
00397
00398 void clear() {
00399 while (head) {
00400 Block* B = head;
00401 head = B->next;
00402 SourceHeap::deallocate(B);
00403 }
00404 }
00405
00406 inline void* allocate(size_t size) {
00407
00408 size = (size + sizeof(double) - 1) & ~(sizeof(double) - 1);
00409
00410 if (!head || offset + size > SourceHeap::AllocSize)
00411 refill();
00412
00413 if (offset + size > SourceHeap::AllocSize) {
00414 assert(0 && "Too large");
00415 return 0;
00416 }
00417 char* retval = (char*)head;
00418 retval += offset;
00419 offset += size;
00420 return retval;
00421 }
00422
00423 inline void deallocate(void* ptr) {}
00424 };
00425
00430 template<typename SourceHeap>
00431 class SimpleBumpPtrWithMallocFallback : public SourceHeap {
00432 struct Block {
00433 union {
00434 Block* next;
00435 double dummy;
00436 };
00437 };
00438
00439 Block* head;
00440 Block* fallbackHead;
00441 int offset;
00442
00444 void refill(void* P, Block*& h, int* o) {
00445 Block* BP = (Block*)P;
00446 BP->next = h;
00447 h = BP;
00448 if (o)
00449 *o = sizeof(Block);
00450 }
00451 public:
00452 enum { AllocSize = 0 };
00453
00454 SimpleBumpPtrWithMallocFallback(): SourceHeap(), head(0), fallbackHead(0), offset(0) { }
00455
00456 ~SimpleBumpPtrWithMallocFallback() {
00457 clear();
00458 }
00459
00460 void clear() {
00461 while (head) {
00462 Block* B = head;
00463 head = B->next;
00464 SourceHeap::deallocate(B);
00465 }
00466 while (fallbackHead) {
00467 Block* B = fallbackHead;
00468 fallbackHead = B->next;
00469 free(B);
00470 }
00471 }
00472
00473 inline void* allocate(size_t size) {
00474
00475 size = (size + sizeof(double) - 1) & ~(sizeof(double) - 1);
00476
00477 if (!head || offset + size > SourceHeap::AllocSize)
00478 refill(SourceHeap::allocate(SourceHeap::AllocSize), head, &offset);
00479
00480 if (offset + size > SourceHeap::AllocSize) {
00481 void* p = malloc(size + sizeof(Block));
00482 refill(p, fallbackHead, NULL);
00483 return (char*)p + sizeof(Block);
00484 }
00485 char* retval = (char*)head;
00486 retval += offset;
00487 offset += size;
00488 return retval;
00489 }
00490
00491 inline void deallocate(void* ptr) {}
00492 };
00493
00496 class SystemBaseAlloc {
00497 public:
00498 enum { AllocSize = pageSize };
00499
00500 SystemBaseAlloc();
00501 ~SystemBaseAlloc();
00502
00503 inline void* allocate(size_t size) {
00504 return pageAlloc();
00505 }
00506
00507 inline void deallocate(void* ptr) {
00508 pageFree(ptr);
00509 }
00510 };
00511
00512 class SizedAllocatorFactory: private boost::noncopyable {
00513 public:
00514 typedef ThreadAwarePrivateHeap<
00515 FreeListHeap<SimpleBumpPtr<SystemBaseAlloc> > > SizedAlloc;
00516
00517 static SizedAlloc* getAllocatorForSize(const size_t);
00518
00519 private:
00520 static SizedAllocatorFactory* getInstance();
00521 static LL::PtrLock<SizedAllocatorFactory, true> instance;
00522 typedef std::map<size_t, SizedAlloc*> AllocatorsMap;
00523 AllocatorsMap allocators;
00524 LL::SimpleLock<true> lock;
00525
00526 SizedAlloc* getAllocForSize(const size_t);
00527
00528 static __thread AllocatorsMap* localAllocators;
00529
00530 SizedAllocatorFactory();
00531 ~SizedAllocatorFactory();
00532 };
00533
00534 class FixedSizeAllocator {
00535 SizedAllocatorFactory::SizedAlloc* alloc;
00536 public:
00537 FixedSizeAllocator(size_t sz) {
00538 alloc = SizedAllocatorFactory::getAllocatorForSize(sz);
00539 }
00540
00541 inline void* allocate(size_t sz) {
00542 return alloc->allocate(sz);
00543 }
00544
00545 inline void deallocate(void* ptr) {
00546 alloc->deallocate(ptr);
00547 }
00548
00549 inline bool operator!=(const FixedSizeAllocator& rhs) const {
00550 return alloc != rhs.alloc;
00551 }
00552 };
00553
00555
00557
00559 template<typename Ty>
00560 class FSBGaloisAllocator;
00561
00562 template<>
00563 class FSBGaloisAllocator<void> {
00564 public:
00565 typedef size_t size_type;
00566 typedef ptrdiff_t difference_type;
00567 typedef void* pointer;
00568 typedef const void* const_pointer;
00569 typedef void value_type;
00570
00571 template<typename Other>
00572 struct rebind { typedef FSBGaloisAllocator<Other> other; };
00573 };
00574
00575 template<typename Ty>
00576 class FSBGaloisAllocator {
00577 inline void destruct(char*) const { }
00578 inline void destruct(wchar_t*) const { }
00579 template<typename T> inline void destruct(T* t) const { t->~T(); }
00580
00581 FixedSizeAllocator Alloc;
00582
00583 public:
00584 typedef size_t size_type;
00585 typedef ptrdiff_t difference_type;
00586 typedef Ty *pointer;
00587 typedef const Ty *const_pointer;
00588 typedef Ty& reference;
00589 typedef const Ty& const_reference;
00590 typedef Ty value_type;
00591
00592 template<class Other>
00593 struct rebind { typedef FSBGaloisAllocator<Other> other; };
00594
00595 FSBGaloisAllocator() throw(): Alloc(sizeof(Ty)) {}
00596 template <class U> FSBGaloisAllocator (const FSBGaloisAllocator<U>&) throw(): Alloc(sizeof(Ty)) {}
00597
00598 inline pointer address(reference val) const { return &val; }
00599 inline const_pointer address(const_reference val) const { return &val; }
00600
00601 pointer allocate(size_type size) {
00602 if (size > max_size())
00603 throw std::bad_alloc();
00604 return static_cast<pointer>(Alloc.allocate(sizeof(Ty)));
00605 }
00606
00607 void deallocate(pointer ptr, size_type) {
00608 Alloc.deallocate(ptr);
00609 }
00610
00611 template<class U, class... Args>
00612 inline void construct(U* p, Args&&... args ) const {
00613 ::new((void*)p) U(std::forward<Args>(args)...);
00614 }
00615
00616 inline void destroy(pointer ptr) const {
00617 destruct(ptr);
00618 }
00619
00620 size_type max_size() const throw() { return 1; }
00621
00622 template<typename T1>
00623 inline bool operator!=(const FSBGaloisAllocator<T1>& rhs) const {
00624 return Alloc != rhs.Alloc;
00625 }
00626 };
00627
00628
00629
00630
00631
00632
00634 template<typename Ty, typename AllocTy>
00635 class ExternRefGaloisAllocator;
00636
00637 template<typename AllocTy>
00638 class ExternRefGaloisAllocator<void,AllocTy> {
00639 public:
00640 typedef size_t size_type;
00641 typedef ptrdiff_t difference_type;
00642 typedef void* pointer;
00643 typedef const void* const_pointer;
00644 typedef void value_type;
00645
00646 template<typename Other>
00647 struct rebind { typedef ExternRefGaloisAllocator<Other,AllocTy> other; };
00648 };
00649
00650 template<typename Ty, typename AllocTy>
00651 class ExternRefGaloisAllocator {
00652 inline void destruct(char*) const {}
00653 inline void destruct(wchar_t*) const { }
00654 template<typename T> inline void destruct(T* t) const { t->~T(); }
00655
00656 public:
00657 AllocTy* Alloc;
00658
00659 typedef size_t size_type;
00660 typedef ptrdiff_t difference_type;
00661 typedef Ty *pointer;
00662 typedef const Ty *const_pointer;
00663 typedef Ty& reference;
00664 typedef const Ty& const_reference;
00665 typedef Ty value_type;
00666
00667 template<class Other>
00668 struct rebind {
00669 typedef ExternRefGaloisAllocator<Other, AllocTy> other;
00670 };
00671
00672 explicit ExternRefGaloisAllocator(AllocTy* a) throw(): Alloc(a) {}
00673
00674 template<class T1>
00675 ExternRefGaloisAllocator(const ExternRefGaloisAllocator<T1,AllocTy>& rhs) throw() {
00676 Alloc = rhs.Alloc;
00677 }
00678
00679 inline pointer address(reference val) const { return &val; }
00680 inline const_pointer address(const_reference val) const { return &val; }
00681
00682 pointer allocate(size_type size) {
00683 if (size > max_size())
00684 throw std::bad_alloc();
00685 return static_cast<pointer>(Alloc->allocate(size*sizeof(Ty)));
00686 }
00687
00688 void deallocate(pointer ptr, size_type x) {
00689 Alloc->deallocate(ptr);
00690 }
00691
00692 inline void construct(pointer ptr, const_reference val) const {
00693 new (ptr) Ty(val);
00694 }
00695
00696 template<class U, class... Args >
00697 inline void construct(U* p, Args&&... args ) const {
00698 ::new((void*)p) U(std::forward<Args>(args)...);
00699 }
00700
00701 void destroy(pointer ptr) const {
00702 destruct(ptr);
00703 }
00704
00705 size_type max_size() const throw() { return size_t(-1)/sizeof(Ty); }
00706
00707 template<typename T1,typename A1>
00708 bool operator!=(const ExternRefGaloisAllocator<T1,A1>& rhs) const {
00709 return Alloc != rhs.Alloc;
00710 }
00711 };
00712
00713 }
00714 }
00715 }
00716
00717 #endif
