memory/allocators/persist_loop_slab_allocator.cc
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #include "memory/allocators/persist_loop_slab_allocator.h" | ||
| 2 | |||
| 3 | #include <algorithm> | ||
| 4 | #include <iostream> | ||
| 5 | |||
| 6 | DEFINE_double(shm_malloc_healthy_rate, 0.95, "shm malloc healthy rate"); | ||
| 7 | |||
| 8 | DECLARE_double(shm_malloc_healthy_rate); | ||
| 9 | |||
| 10 | namespace base { | ||
| 11 | namespace { | ||
| 12 | |||
| 13 | 1187948 | uint64_t BitmapRangeMask(int bit_offset, int count) { | |
| 14 | 1187948 | return (~uint64{0} >> (64 - count)) << bit_offset; | |
| 15 | } | ||
| 16 | |||
| 17 | 634182 | int64 FindUsedBitmapBlock(const uint64* bits, int64 index, int remaining) { | |
| 18 | 902124 | while (remaining > 0) { | |
| 19 | 731616 | const int bit_offset = index & 63; | |
| 20 | 731616 | const int count = std::min(64 - bit_offset, remaining); | |
| 21 | const uint64 occupied = | ||
| 22 | 731616 | bits[index >> 6] & BitmapRangeMask(bit_offset, count); | |
| 23 | 731616 | if (occupied != 0) { | |
| 24 | // All candidate starts through this occupied block must be skipped. | ||
| 25 | 463674 | return (index & ~int64{63}) + 63 - __builtin_clzll(occupied); | |
| 26 | } | ||
| 27 | 267942 | index += count; | |
| 28 | 267942 | remaining -= count; | |
| 29 | } | ||
| 30 | 170508 | return -1; | |
| 31 | } | ||
| 32 | |||
| 33 | 170508 | void SetBitmapRange(uint64* bits, int64 index, int remaining) { | |
| 34 | 372324 | while (remaining > 0) { | |
| 35 | 201816 | const int bit_offset = index & 63; | |
| 36 | 201816 | const int count = std::min(64 - bit_offset, remaining); | |
| 37 | 201816 | bits[index >> 6] |= BitmapRangeMask(bit_offset, count); | |
| 38 | 201816 | index += count; | |
| 39 | 201816 | remaining -= count; | |
| 40 | } | ||
| 41 | 170508 | } | |
| 42 | |||
| 43 | } // namespace | ||
| 44 | |||
| 45 | 738 | PersistLoopShmMalloc::PersistLoopShmMalloc( | |
| 46 | 738 | const std::string& filename, int64 memory_size, std::string medium) { | |
| 47 | 738 | block_num_ = 0; | |
| 48 | 738 | while (((block_num_ + 64) >> 3) + (block_num_ + 64) * sizeof(uint64) <= | |
| 49 | 49129566 | memory_size) { | |
| 50 | 49128828 | block_num_ += 64; | |
| 51 | } | ||
| 52 | 738 | healthy_used_ = block_num_ * FLAGS_shm_malloc_healthy_rate; | |
| 53 | 738 | bool file_exists = base::file_util::PathExists(filename); | |
| 54 | shm_file_ = | ||
| 55 | 738 | ShmFile::New(ShmFile::ConfigForMedium(medium, filename, memory_size)); | |
| 56 | 738 | if (!shm_file_) { | |
| 57 | ✗ | file_exists = false; | |
| 58 | ✗ | CHECK(base::file_util::Delete(filename, false)); | |
| 59 | shm_file_ = | ||
| 60 | ✗ | ShmFile::New(ShmFile::ConfigForMedium(medium, filename, memory_size)); | |
| 61 | ✗ | CHECK(shm_file_) << filename << " " << memory_size; | |
| 62 | } | ||
| 63 | |||
| 64 | 738 | used_bits_ = reinterpret_cast<uint64*>(shm_file_->Data()); | |
| 65 | 738 | data_ = shm_file_->Data() + (block_num_ >> 3); | |
| 66 | 738 | load_success_ = file_exists; | |
| 67 | 738 | Initialize(); | |
| 68 | 738 | if (!file_exists) { | |
| 69 | 738 | LOG(INFO) << "PersistLoopShmMalloc: first initialization."; | |
| 70 | } else { | ||
| 71 | ✗ | LOG(INFO) << "PersistLoopShmMalloc: Recovery from shutdown."; | |
| 72 | } | ||
| 73 | 738 | } | |
| 74 | |||
| 75 | ✗ | void PersistLoopShmMalloc::AddMallocs4Recovery(int64_t shm_offset) { | |
| 76 | // NOTE(xieminhui) use atomic instr to reduce conflict between threads. | ||
| 77 | // But the code below has redundancy with the function UseBlock | ||
| 78 | ✗ | __sync_fetch_and_add(&total_malloc_, 1); // NOLINT | |
| 79 | ✗ | int64_t offset = shm_offset; | |
| 80 | ✗ | CHECK_GE(offset, 0); | |
| 81 | ✗ | CHECK_LT(offset, block_num_ * 8L); | |
| 82 | ✗ | int memory_size = GetMallocSize(offset); | |
| 83 | ✗ | int memory_block_num = BlockNum(memory_size); | |
| 84 | |||
| 85 | ✗ | __sync_fetch_and_add(&total_used_, memory_block_num + 1); // NOLINT | |
| 86 | ✗ | int64_t sizeBlockIdx = BlockIndex(offset) - 1; | |
| 87 | |||
| 88 | ✗ | for (int i = 1; i <= memory_block_num; i++) { | |
| 89 | ✗ | int64 index = sizeBlockIdx + i; | |
| 90 | // Use Block [index] | ||
| 91 | uint64 temp; | ||
| 92 | do { | ||
| 93 | ✗ | temp = used_bits_[index >> 6]; | |
| 94 | ✗ | } while (!__sync_bool_compare_and_swap( | |
| 95 | ✗ | &used_bits_[index >> 6], // NOLINT | |
| 96 | temp, | ||
| 97 | ✗ | temp | (1ul << (index & 63)))); | |
| 98 | } | ||
| 99 | ✗ | } | |
| 100 | |||
| 101 | 109204 | bool PersistLoopShmMalloc::UnusedMemoryValid(int64 block_index) const { | |
| 102 | 109204 | int64 memory_block_num = BlockNum(Block()[block_index]); | |
| 103 | 109204 | if (memory_block_num < 0) { | |
| 104 | ✗ | LOG(ERROR) << "memory_block_num < 0"; | |
| 105 | ✗ | return false; | |
| 106 | } | ||
| 107 | 109204 | block_index++; | |
| 108 | 109204 | if (block_index + memory_block_num > block_num_) { | |
| 109 | ✗ | LOG(ERROR) << "block_index + memory_block_num > block_num_"; | |
| 110 | ✗ | return false; | |
| 111 | } | ||
| 112 | 235388 | while (memory_block_num > 0) { | |
| 113 | 126570 | const int bit_offset = block_index & 63; | |
| 114 | 126570 | const int count = std::min<int64>(64 - bit_offset, memory_block_num); | |
| 115 | 126570 | const uint64 mask = BitmapRangeMask(bit_offset, count); | |
| 116 | 126570 | if ((used_bits_[block_index >> 6] & mask) != mask) { | |
| 117 | 386 | return false; | |
| 118 | } | ||
| 119 | 126184 | block_index += count; | |
| 120 | 126184 | memory_block_num -= count; | |
| 121 | } | ||
| 122 | 108818 | return true; | |
| 123 | } | ||
| 124 | |||
| 125 | 768 | void PersistLoopShmMalloc::GetMallocsAppend( | |
| 126 | std::vector<char*>* mallocs_data) const { | ||
| 127 | 6193152 | for (int64 i = 0; i < block_num_ - 1; ++i) { | |
| 128 | 6192384 | if (!Used(i) && Used(i + 1)) { | |
| 129 | 768 | CHECK_GT(Block()[i], 0) << "block id = " << i; | |
| 130 | 768 | mallocs_data->push_back(data_ + ((i + 1) << 3)); | |
| 131 | } | ||
| 132 | } | ||
| 133 | 768 | } | |
| 134 | |||
| 135 | ✗ | void PersistLoopShmMalloc::GetMallocsAppend( | |
| 136 | std::vector<int64>* mallocs_offset) const { | ||
| 137 | ✗ | for (int64 i = 0; i < block_num_ - 1; ++i) { | |
| 138 | ✗ | if (!Used(i) && Used(i + 1)) { | |
| 139 | ✗ | CHECK_GT(Block()[i], 0) << "block id = " << i; | |
| 140 | ✗ | mallocs_offset->push_back((i + 1) << 3); | |
| 141 | } | ||
| 142 | } | ||
| 143 | ✗ | } | |
| 144 | |||
| 145 | ✗ | bool PersistLoopShmMalloc::MemoryValid() const { | |
| 146 | ✗ | int64 block_index = 0; | |
| 147 | ✗ | while (block_index < block_num_) { | |
| 148 | ✗ | if (Used(block_index)) | |
| 149 | ✗ | return false; | |
| 150 | ✗ | if (!UnusedMemoryValid(block_index)) | |
| 151 | ✗ | return false; | |
| 152 | ✗ | block_index += 1 + BlockNum(Block()[block_index]); | |
| 153 | } | ||
| 154 | ✗ | return block_index == block_num_; | |
| 155 | } | ||
| 156 | |||
| 157 | 173084 | char* PersistLoopShmMalloc::New(int memory_size) { | |
| 158 | 173084 | CHECK_GE(memory_size, 0); | |
| 159 | 173084 | if (memory_size == 0) { | |
| 160 | 2 | return data_ + sizeof(uint64) * block_num_; | |
| 161 | } | ||
| 162 | 173082 | base::AutoLock lock(lock_); | |
| 163 | 173082 | int memory_block_num = BlockNum(memory_size); | |
| 164 | 173082 | auto fast_malloc_list = fast_malloc_lists_.Get(memory_block_num); | |
| 165 | 173082 | if (fast_malloc_list && enable_fast_malloc_) { | |
| 166 | // 先尝试从刚回收的内存块中分配 | ||
| 167 | 106024 | while (fast_malloc_list->size()) { | |
| 168 | 100234 | int64 malloc_block = fast_malloc_list->front(); | |
| 169 | 100234 | fast_malloc_list->pop_front(); | |
| 170 | // Live headers have clear bits. Inspect the following bit too, unless | ||
| 171 | // the payload ends at the pool boundary, to avoid consuming a header. | ||
| 172 | const int check_blocks = | ||
| 173 | 100234 | std::min<int64>(memory_block_num + 2, block_num_ - malloc_block); | |
| 174 | 100234 | if (FindUsedBitmapBlock(used_bits_, malloc_block, check_blocks) < 0) { | |
| 175 | 99596 | Block()[malloc_block] = memory_size; | |
| 176 | 99596 | SetBitmapRange(used_bits_, malloc_block + 1, memory_block_num); | |
| 177 | 99596 | total_used_ += memory_block_num + 1; | |
| 178 | 99596 | total_malloc_++; | |
| 179 | 99596 | total_fast_malloc_.Inc(1); | |
| 180 | 99596 | clflushopt_range(&Block()[malloc_block], sizeof(uint64)); | |
| 181 | 99596 | return data_ + sizeof(uint64) * (malloc_block + 1); | |
| 182 | } | ||
| 183 | } | ||
| 184 | } | ||
| 185 | 73486 | int64 offset = 0; | |
| 186 | 73486 | int64 malloc_block = last_malloc_block_; | |
| 187 | 539684 | while (offset < block_num_) { | |
| 188 | 537110 | if (malloc_block + memory_block_num + 1 <= block_num_) { | |
| 189 | const int check_blocks = | ||
| 190 | 533948 | std::min<int64>(memory_block_num + 2, block_num_ - malloc_block); | |
| 191 | const int64 occupied = | ||
| 192 | 533948 | FindUsedBitmapBlock(used_bits_, malloc_block, check_blocks); | |
| 193 | 533948 | if (occupied < 0) { | |
| 194 | 70912 | Block()[malloc_block] = memory_size; | |
| 195 | 70912 | SetBitmapRange(used_bits_, malloc_block + 1, memory_block_num); | |
| 196 | 70912 | last_malloc_block_ = (malloc_block + memory_block_num + 1) % block_num_; | |
| 197 | 70912 | total_used_ += memory_block_num + 1; | |
| 198 | 70912 | total_malloc_++; | |
| 199 | 70912 | total_loop_malloc_.Inc(1); | |
| 200 | // persist the value first | ||
| 201 | // clflushopt_range(sync_data - sizeof(uint64), size + sizeof(uint64)); | ||
| 202 | // warning(xieminhui) Now we only clflush the !!!!!value_len!!!!! | ||
| 203 | 70912 | clflushopt_range(&Block()[malloc_block], sizeof(uint64)); | |
| 204 | 70912 | return data_ + sizeof(uint64) * (malloc_block + 1); | |
| 205 | } | ||
| 206 | 463036 | const int64 advance = occupied - malloc_block + 1; | |
| 207 | 463036 | malloc_block += advance; | |
| 208 | 463036 | offset += advance; | |
| 209 | } else { | ||
| 210 | 3162 | offset += block_num_ - malloc_block; | |
| 211 | 3162 | malloc_block = 0; | |
| 212 | } | ||
| 213 | } | ||
| 214 | // LOG(INFO) << "persist memory has no mem!"; | ||
| 215 | 2574 | return NULL; | |
| 216 | 173082 | } | |
| 217 | |||
| 218 | 109208 | bool PersistLoopShmMalloc::Free(void* memory_data) { | |
| 219 | 109208 | auto data = reinterpret_cast<const char*>(memory_data); | |
| 220 | 109208 | int64 offset = GetMallocOffset(data); | |
| 221 | 109208 | if (offset < 0) | |
| 222 | ✗ | return false; | |
| 223 | 109208 | if (offset == sizeof(uint64) * block_num_) | |
| 224 | 4 | return true; | |
| 225 | 109204 | base::AutoLock lock(lock_); | |
| 226 | 109204 | int64 block_index = BlockIndex(offset) - 1; | |
| 227 | 109204 | if (!Used(block_index) && UnusedMemoryValid(block_index)) { | |
| 228 | 108818 | int memory_block_num = BlockNum(Block()[block_index]); | |
| 229 | 108818 | if (enable_fast_malloc_) { | |
| 230 | 108818 | auto fast_malloc_list = fast_malloc_lists_.Get(memory_block_num); | |
| 231 | 108818 | if (!fast_malloc_list && fast_malloc_lists_.size() < max_fast_list_type) { | |
| 232 | 1290 | fast_malloc_list = new std::deque<int64>(); | |
| 233 | 1290 | fast_malloc_lists_.Insert(memory_block_num, fast_malloc_list); | |
| 234 | } | ||
| 235 | 108818 | if (fast_malloc_list && fast_malloc_list->size() < max_fast_list_num) { | |
| 236 | 105966 | fast_malloc_list->push_back(block_index); | |
| 237 | } | ||
| 238 | } | ||
| 239 | 108818 | int64 index = block_index; | |
| 240 | 108818 | int remaining = memory_block_num + 1; | |
| 241 | 236764 | while (remaining > 0) { | |
| 242 | 127946 | const int bit_offset = index & 63; | |
| 243 | 127946 | const int count = std::min(64 - bit_offset, remaining); | |
| 244 | 127946 | const uint64 mask = BitmapRangeMask(bit_offset, count); | |
| 245 | 127946 | used_bits_[index >> 6] &= ~mask; | |
| 246 | 127946 | index += count; | |
| 247 | 127946 | remaining -= count; | |
| 248 | } | ||
| 249 | 108818 | total_used_ -= memory_block_num + 1; | |
| 250 | 108818 | total_malloc_--; | |
| 251 | 108818 | return true; | |
| 252 | } | ||
| 253 | // NOTE(xieminhui): this block already be freed by other thread | ||
| 254 | |||
| 255 | // LOG(ERROR) << "block_index= " << block_index | ||
| 256 | // << ", Used(block_index)= " << Used(block_index) | ||
| 257 | // << ", UnusedMemoryValid(block_index)= " | ||
| 258 | // << UnusedMemoryValid(block_index); | ||
| 259 | 386 | return false; | |
| 260 | 109204 | } | |
| 261 | |||
| 262 | } // namespace base | ||
| 263 |