slab_allocator.hpp (4098B)
1 /* Relacy Race Detector 2 * Copyright (c) 2008-2013, Dmitry S. Vyukov 3 * All rights reserved. 4 * This software is provided AS-IS with no warranty, either express or implied. 5 * This software is distributed under a license and may not be copied, 6 * modified or distributed except as expressly authorized under the 7 * terms of the license contained in the file LICENSE in this distribution. 8 */ 9 10 #ifndef RL_SLAB_ALLOCATOR_HPP 11 #define RL_SLAB_ALLOCATOR_HPP 12 #ifdef _MSC_VER 13 # pragma once 14 #endif 15 16 #include "base.hpp" 17 18 19 namespace rl 20 { 21 22 23 template<typename type> 24 class slab_allocator : nocopy<> 25 { 26 public: 27 slab_allocator() 28 : freelist_() 29 , blocks_() 30 , alloc_count_() 31 { 32 } 33 34 ~slab_allocator() 35 { 36 char* pos = blocks_; 37 while (pos) 38 { 39 char* const next = *reinterpret_cast<char**>(pos); 40 ::free(pos); 41 pos = next; 42 } 43 } 44 45 type* alloc(void* ctx = 0) 46 { 47 if (freelist_) 48 { 49 type* p = freelist_; 50 freelist_ = *reinterpret_cast<type**>(p); 51 alloc_count_ += 1; 52 *(void**)p = ctx; 53 type* pp = reinterpret_cast<type*>((reinterpret_cast<void**>(p) + 1)); 54 return pp; 55 } 56 else 57 { 58 return alloc_batch(); 59 } 60 } 61 62 void free(type* p) 63 { 64 type** pos = reinterpret_cast<type**>((reinterpret_cast<void**>(p) - 1)); 65 pos[0] = freelist_; 66 freelist_ = reinterpret_cast<type*>(pos); 67 alloc_count_ -= 1; 68 } 69 70 bool iteration_end() 71 { 72 #ifndef RL_GC 73 return alloc_count_ == 0; 74 #else 75 freelist_ = 0; 76 size_t elem_size = sizeof(void*) + sizeof(type); 77 elem_size = (elem_size + 15) & ~15; 78 char* pos = blocks_; 79 while (pos) 80 { 81 char* p = pos; 82 p += elem_size; 83 for (size_t i = 0; i != batch_size; ++i) 84 { 85 *reinterpret_cast<type**>(p) = freelist_; 86 freelist_ = reinterpret_cast<type*>(p); 87 p += elem_size; 88 } 89 pos = *reinterpret_cast<char**>(pos); 90 } 91 return true; 92 #endif 93 } 94 95 void output_allocs(std::ostream& stream) 96 { 97 size_t elem_size = sizeof(void*) + sizeof(type); 98 elem_size = (elem_size + 15) & ~15; 99 set<void*>::type allocs; 100 char* pos = blocks_; 101 while (pos) 102 { 103 char* p = pos; 104 p += elem_size; 105 for (size_t i = 0; i != batch_size; ++i) 106 { 107 allocs.insert(p); 108 p += elem_size; 109 } 110 pos = *reinterpret_cast<char**>(pos); 111 } 112 set<void*>::type avail; 113 type* pos2 = freelist_; 114 while (pos2) 115 { 116 avail.insert(pos2); 117 pos2 = *reinterpret_cast<type**>(pos2); 118 } 119 vector<void*>::type diff; 120 std::set_difference(allocs.begin(), allocs.end(), avail.begin(), avail.end(), std::back_inserter(diff)); 121 for (size_t i = 0; i != diff.size(); ++i) 122 { 123 stream << *(void**)diff[i] << std::endl; 124 } 125 } 126 127 private: 128 static size_t const batch_size = 128; 129 type* freelist_; 130 char* blocks_; 131 size_t alloc_count_; 132 133 RL_NOINLINE type* alloc_batch() 134 { 135 size_t elem_size = sizeof(void*) + sizeof(type); 136 elem_size = (elem_size + 15) & ~15; 137 char* const batch = (char*)(::malloc)(elem_size * (batch_size + 1)); 138 if (0 == batch) 139 throw std::bad_alloc(); 140 *reinterpret_cast<char**>(batch) = blocks_; 141 blocks_ = batch; 142 char* p = batch; 143 p += elem_size; 144 for (size_t i = 0; i != batch_size; ++i) 145 { 146 *reinterpret_cast<type**>(p) = freelist_; 147 freelist_ = reinterpret_cast<type*>(p); 148 p += elem_size; 149 } 150 return alloc(); 151 } 152 }; 153 154 155 } 156 157 #endif