1 // Copyright 2008 Google Inc. All Rights Reserved. 2 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 7 // http://www.apache.org/licenses/LICENSE-2.0 8 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 // Thread-safe container of disk blocks 16 17 // This file must work with autoconf on its public version, 18 // so these includes are correct. 19 #include "disk_blocks.h" 20 21 #include <utility> 22 23 // BlockData 24 BlockData::BlockData() : address_(0), size_(0), 25 references_(0), initialized_(false), 26 pattern_(NULL) { 27 pthread_mutex_init(&data_mutex_, NULL); 28 } 29 30 BlockData::~BlockData() { 31 pthread_mutex_destroy(&data_mutex_); 32 } 33 34 void BlockData::set_initialized() { 35 pthread_mutex_lock(&data_mutex_); 36 initialized_ = true; 37 pthread_mutex_unlock(&data_mutex_); 38 } 39 40 bool BlockData::initialized() const { 41 pthread_mutex_lock(&data_mutex_); 42 bool initialized = initialized_; 43 pthread_mutex_unlock(&data_mutex_); 44 return initialized; 45 } 46 47 // DiskBlockTable 48 DiskBlockTable::DiskBlockTable() : sector_size_(0), write_block_size_(0), 49 device_name_(""), device_sectors_(0), 50 segment_size_(0), size_(0) { 51 pthread_mutex_init(&data_mutex_, NULL); 52 pthread_mutex_init(¶meter_mutex_, NULL); 53 pthread_cond_init(&data_condition_, NULL); 54 } 55 56 DiskBlockTable::~DiskBlockTable() { 57 pthread_mutex_destroy(&data_mutex_); 58 pthread_mutex_destroy(¶meter_mutex_); 59 pthread_cond_destroy(&data_condition_); 60 } 61 62 // 64-bit non-negative random number generator. Stolen from 63 // depot/google3/base/tracecontext_unittest.cc. 64 int64 DiskBlockTable::Random64() { 65 int64 x = random(); 66 x = (x << 30) ^ random(); 67 x = (x << 30) ^ random(); 68 if (x >= 0) 69 return x; 70 else 71 return -x; 72 } 73 74 uint64 DiskBlockTable::Size() { 75 pthread_mutex_lock(&data_mutex_); 76 uint64 size = size_; 77 pthread_mutex_unlock(&data_mutex_); 78 return size; 79 } 80 81 void DiskBlockTable::InsertOnStructure(BlockData *block) { 82 int64 address = block->address(); 83 StorageData *sd = new StorageData(); 84 sd->block = block; 85 sd->pos = size_; 86 // Creating new block ... 87 pthread_mutex_lock(&data_mutex_); 88 if (pos_to_addr_.size() <= size_) { 89 pos_to_addr_.insert(pos_to_addr_.end(), address); 90 } else { 91 pos_to_addr_[size_] = address; 92 } 93 addr_to_block_[address] = sd; 94 size_++; 95 pthread_cond_broadcast(&data_condition_); 96 pthread_mutex_unlock(&data_mutex_); 97 } 98 99 int DiskBlockTable::RemoveBlock(BlockData *block) { 100 // For write threads, check the reference counter and remove 101 // it from the structure. 102 int64 address = block->address(); 103 AddrToBlockMap::iterator it = addr_to_block_.find(address); 104 int ret = 1; 105 if (it != addr_to_block_.end()) { 106 int curr_pos = it->second->pos; 107 int last_pos = size_ - 1; 108 AddrToBlockMap::iterator last_it = addr_to_block_.find( 109 pos_to_addr_[last_pos]); 110 sat_assert(size_ > 0); 111 sat_assert(last_it != addr_to_block_.end()); 112 // Everything is fine, removing block from table. 113 pthread_mutex_lock(&data_mutex_); 114 pos_to_addr_[curr_pos] = pos_to_addr_[last_pos]; 115 last_it->second->pos = curr_pos; 116 delete it->second; 117 addr_to_block_.erase(it); 118 size_--; 119 block->DecreaseReferenceCounter(); 120 if (block->GetReferenceCounter() == 0) 121 delete block; 122 else if (block->GetReferenceCounter() < 0) 123 ret = 0; 124 pthread_cond_broadcast(&data_condition_); 125 pthread_mutex_unlock(&data_mutex_); 126 } else { 127 ret = 0; 128 } 129 return ret; 130 } 131 132 int DiskBlockTable::ReleaseBlock(BlockData *block) { 133 // If caller is a random thread, just check the reference counter. 134 int ret = 1; 135 pthread_mutex_lock(&data_mutex_); 136 int references = block->GetReferenceCounter(); 137 if (references == 1) 138 delete block; 139 else if (references > 0) 140 block->DecreaseReferenceCounter(); 141 else 142 ret = 0; 143 pthread_mutex_unlock(&data_mutex_); 144 return ret; 145 } 146 147 BlockData *DiskBlockTable::GetRandomBlock() { 148 struct timespec ts; 149 struct timeval tp; 150 gettimeofday(&tp, NULL); 151 ts.tv_sec = tp.tv_sec; 152 ts.tv_nsec = tp.tv_usec * 1000; 153 ts.tv_sec += 2; // Wait for 2 seconds. 154 int result = 0; 155 pthread_mutex_lock(&data_mutex_); 156 while (!size_ && result != ETIMEDOUT) { 157 result = pthread_cond_timedwait(&data_condition_, &data_mutex_, &ts); 158 } 159 if (result == ETIMEDOUT) { 160 pthread_mutex_unlock(&data_mutex_); 161 return NULL; 162 } else { 163 int64 random_number = Random64(); 164 int64 random_pos = random_number % size_; 165 int64 address = pos_to_addr_[random_pos]; 166 AddrToBlockMap::const_iterator it = addr_to_block_.find(address); 167 sat_assert(it != addr_to_block_.end()); 168 BlockData *b = it->second->block; 169 // A block is returned only if its content is written on disk. 170 if (b->initialized()) { 171 b->IncreaseReferenceCounter(); 172 } else { 173 b = NULL; 174 } 175 pthread_mutex_unlock(&data_mutex_); 176 return b; 177 } 178 } 179 180 void DiskBlockTable::SetParameters(int sector_size, 181 int write_block_size, 182 int64 device_sectors, 183 int64 segment_size, 184 const string& device_name) { 185 sat_assert(size_ == 0); 186 pthread_mutex_lock(¶meter_mutex_); 187 sector_size_ = sector_size; 188 write_block_size_ = write_block_size; 189 device_sectors_ = device_sectors; 190 segment_size_ = segment_size; 191 device_name_ = device_name; 192 pthread_mutex_unlock(¶meter_mutex_); 193 } 194 195 BlockData *DiskBlockTable::GetUnusedBlock(int64 segment) { 196 int64 sector = 0; 197 BlockData *block = new BlockData(); 198 bool good_sequence = false; 199 if (block == NULL) { 200 logprintf(0, "Process Error: Unable to allocate memory " 201 "for sector data for disk %s.\n", device_name_.c_str()); 202 return NULL; 203 } 204 pthread_mutex_lock(¶meter_mutex_); 205 sat_assert(device_sectors_ != 0); 206 // Align the first sector with the beginning of a write block 207 int num_sectors = write_block_size_ / sector_size_; 208 for (int i = 0; i < kBlockRetry && !good_sequence; i++) { 209 good_sequence = true; 210 // Use the entire disk or a small segment of the disk to allocate the first 211 // sector in the block from. 212 if (segment_size_ == -1) { 213 sector = (Random64() & 0x7FFFFFFFFFFFFFFFLL) % ( 214 device_sectors_ / num_sectors); 215 sector *= num_sectors; 216 } else { 217 sector = (Random64() & 0x7FFFFFFFFFFFFFFFLL) % ( 218 segment_size_ / num_sectors); 219 sector *= num_sectors; 220 sector += segment * segment_size_; 221 // Make sure the block is within the segment. 222 if (sector + num_sectors > (segment + 1) * segment_size_) { 223 good_sequence = false; 224 continue; 225 } 226 } 227 // Make sure the entire block is in range. 228 if (sector + num_sectors > device_sectors_) { 229 good_sequence = false; 230 continue; 231 } 232 // Check to see if the block is free. Since the blocks are 233 // now aligned to the write_block_size, it is not necessary 234 // to check each sector, just the first block (a sector 235 // overlap will never occur). 236 pthread_mutex_lock(&data_mutex_); 237 if (addr_to_block_.find(sector) != addr_to_block_.end()) { 238 good_sequence = false; 239 } 240 pthread_mutex_unlock(&data_mutex_); 241 } 242 243 if (good_sequence) { 244 block->set_address(sector); 245 block->set_size(write_block_size_); 246 block->IncreaseReferenceCounter(); 247 InsertOnStructure(block); 248 } else { 249 // No contiguous sequence of num_sectors sectors was found within 250 // kBlockRetry iterations so return an error value. 251 delete block; 252 block = NULL; 253 } 254 pthread_mutex_unlock(¶meter_mutex_); 255 return block; 256 } 257
