1// Copyright 2007 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// This is an interface to a simple thread safe container with fine-grain locks, 16// used to hold data blocks and patterns. 17 18// This file must work with autoconf on its public version, 19// so these includes are correct. 20#include "finelock_queue.h" 21#include "os.h" 22 23// Page entry queue implementation follows. 24// Push and Get functions are analogous to lock and unlock operations on a given 25// page entry, while preserving queue semantics. 26// 27// The actual 'queue' implementation is actually just an array. The entries are 28// never shuffled or re-ordered like that of a real queue. Instead, Get 29// functions return a random page entry of a given type and lock that particular 30// page entry until it is unlocked by corresponding Put functions. 31// 32// In this implementation, a free page is those page entries where pattern is 33// null (pe->pattern == 0) 34 35 36// Constructor: Allocates memory and initialize locks. 37FineLockPEQueue::FineLockPEQueue( 38 uint64 queuesize, int64 pagesize) { 39 q_size_ = queuesize; 40 pages_ = new struct page_entry[q_size_]; 41 pagelocks_ = new pthread_mutex_t[q_size_]; 42 page_size_ = pagesize; 43 44 // What metric should we measure this run. 45 queue_metric_ = kTouch; 46 47 { // Init all the page locks. 48 for (uint64 i = 0; i < q_size_; i++) { 49 pthread_mutex_init(&(pagelocks_[i]), NULL); 50 // Pages start out owned (locked) by Sat::InitializePages. 51 // A locked state indicates that the page state is unknown, 52 // and the lock should not be aquired. As InitializePages creates 53 // the page records, they will be inserted and unlocked, at which point 54 // they are ready to be aquired and filled by worker threads. 55 sat_assert(pthread_mutex_lock(&(pagelocks_[i])) == 0); 56 } 57 } 58 59 { // Init the random number generator. 60 for (int i = 0; i < 4; i++) { 61 rand_seed_[i] = i + 0xbeef; 62 pthread_mutex_init(&(randlocks_[i]), NULL); 63 } 64 } 65 66 // Try to make a linear congruential generator with our queue size. 67 // We need this to deterministically search all the queue (being able to find 68 // a single available element is a design requirement), but we don't want to 69 // cause any page to be more likley chosen than another. The previous 70 // sequential retry heavily biased pages at the beginning of a bunch, or 71 // isolated pages surrounded by unqualified ones. 72 int64 length = queuesize; 73 int64 modlength = length; 74 int64 a; 75 int64 c; 76 77 if (length < 3) { 78 a = 1; 79 c = 1; 80 } else { 81 // Search for a nontrivial generator. 82 a = getA(length) % length; 83 // If this queue size doesn't have a nontrivial generator (where the 84 // multiplier is greater then one) we'll check increasing queue sizes, 85 // and discard out of bounds results. 86 while (a == 1) { 87 modlength++; 88 a = getA(modlength) % modlength; 89 } 90 c = getC(modlength); 91 } 92 93 // This is our final generator. 94 a_ = a; 95 c_ = c; 96 modlength_ = modlength; 97} 98 99// Part of building a linear congruential generator n1 = (a * n0 + c) % m 100// Get 'a', where a - 1 must be divisible by all prime 101// factors of 'm', our queue size. 102int64 FineLockPEQueue::getA(int64 m) { 103 int64 remaining = m; 104 int64 a = 1; 105 if ((((remaining / 4) * 4) == remaining)) { 106 a = 2; 107 } 108 // For each number, let's see if it's divisible, 109 // then divide it out. 110 for (int64 i = 2; i <= m; i++) { 111 if (((remaining / i) * i) == remaining) { 112 remaining /= i; 113 // Keep dividing it out until there's no more. 114 while (((remaining / i) * i) == remaining) 115 remaining /= i; 116 a *= i; 117 } 118 } 119 120 // Return 'a' as specified. 121 return (a + 1) % m; 122} 123 124 125// Part of building a linear congruential generator n1 = (a * n0 + c) % m 126// Get a prime number approx 3/4 the size of our queue. 127int64 FineLockPEQueue::getC(int64 m) { 128 // Start here at 3/4. 129 int64 start = (3 * m) / 4 + 1; 130 int64 possible_prime = start; 131 // Keep trying until we find a prime. 132 for (possible_prime = start; possible_prime > 1; possible_prime--) { 133 bool failed = false; 134 for (int64 i = 2; i < possible_prime; i++) { 135 if (((possible_prime / i) * i) == possible_prime) { 136 failed = true; 137 break; 138 } 139 } 140 if (!failed) { 141 return possible_prime; 142 } 143 } 144 // One is prime enough. 145 return 1; 146} 147 148// Destructor: Clean-up allocated memory and destroy pthread locks. 149FineLockPEQueue::~FineLockPEQueue() { 150 uint64 i; 151 for (i = 0; i < q_size_; i++) 152 pthread_mutex_destroy(&(pagelocks_[i])); 153 delete[] pagelocks_; 154 delete[] pages_; 155 for (i = 0; i < 4; i++) { 156 pthread_mutex_destroy(&(randlocks_[i])); 157 } 158} 159 160 161bool FineLockPEQueue::QueueAnalysis() { 162 const char *measurement = "Error"; 163 uint64 buckets[32]; 164 165 if (queue_metric_ == kTries) 166 measurement = "Failed retrievals"; 167 else if (queue_metric_ == kTouch) 168 measurement = "Reads per page"; 169 170 // Buckets for each log2 access counts. 171 for (int b = 0; b < 32; b++) { 172 buckets[b] = 0; 173 } 174 175 // Bucketize the page counts by highest bit set. 176 for (uint64 i = 0; i < q_size_; i++) { 177 uint32 readcount = pages_[i].touch; 178 int b = 0; 179 for (b = 0; b < 31; b++) { 180 if (readcount < (1u << b)) 181 break; 182 } 183 184 buckets[b]++; 185 } 186 187 logprintf(12, "Log: %s histogram\n", measurement); 188 for (int b = 0; b < 32; b++) { 189 if (buckets[b]) 190 logprintf(12, "Log: %12d - %12d: %12d\n", 191 ((1 << b) >> 1), 1 << b, buckets[b]); 192 } 193 194 return true; 195} 196 197namespace { 198// Callback mechanism for exporting last action. 199OsLayer *g_os; 200FineLockPEQueue *g_fpqueue = 0; 201 202// Global callback to hook into Os object. 203bool err_log_callback(uint64 paddr, string *buf) { 204 if (g_fpqueue) { 205 return g_fpqueue->ErrorLogCallback(paddr, buf); 206 } 207 return false; 208} 209} 210 211// Setup global state for exporting callback. 212void FineLockPEQueue::set_os(OsLayer *os) { 213 g_os = os; 214 g_fpqueue = this; 215} 216 217OsLayer::ErrCallback FineLockPEQueue::get_err_log_callback() { 218 return err_log_callback; 219} 220 221// This call is used to export last transaction info on a particular physical 222// address. 223bool FineLockPEQueue::ErrorLogCallback(uint64 paddr, string *message) { 224 struct page_entry pe; 225 OsLayer *os = g_os; 226 sat_assert(g_os); 227 char buf[256]; 228 229 // Find the page of this paddr. 230 int gotpage = GetPageFromPhysical(paddr, &pe); 231 if (!gotpage) { 232 return false; 233 } 234 235 // Find offset into the page. 236 uint64 addr_diff = paddr - pe.paddr; 237 238 // Find vaddr of this paddr. Make sure it matches, 239 // as sometimes virtual memory is not contiguous. 240 char *vaddr = 241 reinterpret_cast<char*>(os->PrepareTestMem(pe.offset, page_size_)); 242 uint64 new_paddr = os->VirtualToPhysical(vaddr + addr_diff); 243 os->ReleaseTestMem(vaddr, pe.offset, page_size_); 244 245 // Is the physical address at this page offset the same as 246 // the physical address we were given? 247 if (new_paddr != paddr) { 248 return false; 249 } 250 251 // Print all the info associated with this page. 252 message->assign(" (Last Transaction:"); 253 254 if (pe.lastpattern) { 255 int offset = addr_diff / 8; 256 datacast_t data; 257 258 data.l32.l = pe.lastpattern->pattern(offset << 1); 259 data.l32.h = pe.lastpattern->pattern((offset << 1) + 1); 260 261 snprintf(buf, sizeof(buf), " %s data=%#016llx", 262 pe.lastpattern->name(), data.l64); 263 message->append(buf); 264 } 265 snprintf(buf, sizeof(buf), " tsc=%#llx)", pe.ts); 266 message->append(buf); 267 return true; 268} 269 270bool FineLockPEQueue::GetPageFromPhysical(uint64 paddr, 271 struct page_entry *pe) { 272 // Traverse through array until finding a page 273 // that contains the address we want.. 274 for (uint64 i = 0; i < q_size_; i++) { 275 uint64 page_addr = pages_[i].paddr; 276 // This assumes linear vaddr. 277 if ((page_addr <= paddr) && (page_addr + page_size_ > paddr)) { 278 *pe = pages_[i]; 279 return true; 280 } 281 } 282 return false; 283} 284 285 286// Get a random number from the slot we locked. 287uint64 FineLockPEQueue::GetRandom64FromSlot(int slot) { 288 // 64 bit LCG numbers suggested on the internets by 289 // http://nuclear.llnl.gov/CNP/rng/rngman/node4.html and others. 290 uint64 result = 2862933555777941757ULL * rand_seed_[slot] + 3037000493ULL; 291 rand_seed_[slot] = result; 292 return result; 293} 294 295// Get a random number, we have 4 generators to choose from so hopefully we 296// won't be blocking on this. 297uint64 FineLockPEQueue::GetRandom64() { 298 // Try each available slot. 299 for (int i = 0; i < 4; i++) { 300 if (pthread_mutex_trylock(&(randlocks_[i])) == 0) { 301 uint64 result = GetRandom64FromSlot(i); 302 pthread_mutex_unlock(&(randlocks_[i])); 303 return result; 304 } 305 } 306 // Forget it, just wait. 307 int i = 0; 308 if (pthread_mutex_lock(&(randlocks_[i])) == 0) { 309 uint64 result = GetRandom64FromSlot(i); 310 pthread_mutex_unlock(&(randlocks_[i])); 311 return result; 312 } 313 314 logprintf(0, "Process Error: Could not acquire random lock.\n"); 315 sat_assert(0); 316 return 0; 317} 318 319 320// Helper function to get a random page entry with given predicate, 321// ie, page_is_valid() or page_is_empty() as defined in finelock_queue.h. 322// 323// Setting tag to a value other than kDontCareTag (-1) 324// indicates that we need a tag match, otherwise any tag will do. 325// 326// Returns true on success, false on failure. 327bool FineLockPEQueue::GetRandomWithPredicateTag(struct page_entry *pe, 328 bool (*pred_func)(struct page_entry*), 329 int32 tag) { 330 if (!pe || !q_size_) 331 return false; 332 333 // Randomly index into page entry array. 334 uint64 first_try = GetRandom64() % q_size_; 335 uint64 next_try = 1; 336 337 // Traverse through array until finding a page meeting given predicate. 338 for (uint64 i = 0; i < q_size_; i++) { 339 uint64 index = (next_try + first_try) % q_size_; 340 // Go through the loop linear conguentially. We are offsetting by 341 // 'first_try' so this path will be a different sequence for every 342 // initioal value chosen. 343 next_try = (a_ * next_try + c_) % (modlength_); 344 while (next_try >= q_size_) { 345 // If we have chosen a modlength greater than the queue size, 346 // discard out of bounds results. 347 next_try = (a_ * next_try + c_) % (modlength_); 348 } 349 350 // If page does not meet predicate, don't trylock (expensive). 351 if (!(pred_func)(&pages_[index])) 352 continue; 353 354 // If page does not meet tag predicate, don't trylock (expensive). 355 if ((tag != kDontCareTag) && !(pages_[index].tag & tag)) 356 continue; 357 358 if (pthread_mutex_trylock(&(pagelocks_[index])) == 0) { 359 // If page property (valid/empty) changes before successfully locking, 360 // release page and move on. 361 if (!(pred_func)(&pages_[index])) { 362 pthread_mutex_unlock(&(pagelocks_[index])); 363 continue; 364 } else { 365 // A page entry with given predicate is locked, returns success. 366 *pe = pages_[index]; 367 368 // Add metrics as necessary. 369 if (pred_func == page_is_valid) { 370 // Measure time to fetch valid page. 371 if (queue_metric_ == kTries) 372 pe->touch = i; 373 // Measure number of times each page is read. 374 if (queue_metric_ == kTouch) 375 pe->touch++; 376 } 377 378 return true; 379 } 380 } 381 } 382 383 return false; 384} 385 386// Without tag hint. 387bool FineLockPEQueue::GetRandomWithPredicate(struct page_entry *pe, 388 bool (*pred_func)(struct page_entry*)) { 389 return GetRandomWithPredicateTag(pe, pred_func, kDontCareTag); 390} 391 392 393// GetValid() randomly finds a valid page, locks it and returns page entry by 394// pointer. 395// 396// Returns true on success, false on failure. 397bool FineLockPEQueue::GetValid(struct page_entry *pe) { 398 return GetRandomWithPredicate(pe, page_is_valid); 399} 400 401bool FineLockPEQueue::GetValid(struct page_entry *pe, int32 mask) { 402 return GetRandomWithPredicateTag(pe, page_is_valid, mask); 403} 404 405// GetEmpty() randomly finds an empty page, locks it and returns page entry by 406// pointer. 407// 408// Returns true on success, false on failure. 409bool FineLockPEQueue::GetEmpty(struct page_entry *pe, int32 mask) { 410 return GetRandomWithPredicateTag(pe, page_is_empty, mask); 411} 412bool FineLockPEQueue::GetEmpty(struct page_entry *pe) { 413 return GetRandomWithPredicate(pe, page_is_empty); 414} 415 416// PutEmpty puts an empty page back into the queue, making it available by 417// releasing the per-page-entry lock. 418// 419// Returns true on success, false on failure. 420bool FineLockPEQueue::PutEmpty(struct page_entry *pe) { 421 if (!pe || !q_size_) 422 return false; 423 424 int64 index = pe->offset / page_size_; 425 if (!valid_index(index)) 426 return false; 427 428 pages_[index] = *pe; 429 // Enforce that page entry is indeed empty. 430 pages_[index].pattern = 0; 431 return (pthread_mutex_unlock(&(pagelocks_[index])) == 0); 432} 433 434// PutValid puts a valid page back into the queue, making it available by 435// releasing the per-page-entry lock. 436// 437// Returns true on success, false on failure. 438bool FineLockPEQueue::PutValid(struct page_entry *pe) { 439 if (!pe || !page_is_valid(pe) || !q_size_) 440 return false; 441 442 int64 index = pe->offset / page_size_; 443 if (!valid_index(index)) 444 return false; 445 446 pages_[index] = *pe; 447 return (pthread_mutex_unlock(&(pagelocks_[index])) == 0); 448} 449