1 // Copyright 2007 Google Inc. All Rights Reserved.
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
7 // http://www.apache.org/licenses/LICENSE-2.0
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.
15 // This is an interface to a simple thread safe container with fine-grain locks,
16 // used to hold data blocks and patterns.
18 // This file must work with autoconf on its public version,
19 // so these includes are correct.
20 #include "finelock_queue.h"
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.
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.
32 // In this implementation, a free page is those page entries where pattern is
33 // null (pe->pattern == 0)
36 // Constructor: Allocates memory and initialize locks.
37 FineLockPEQueue::FineLockPEQueue(
38 uint64 queuesize, int64 pagesize) {
40 pages_ = new struct page_entry[q_size_];
41 pagelocks_ = new pthread_mutex_t[q_size_];
42 page_size_ = pagesize;
44 // What metric should we measure this run.
45 queue_metric_ = kTouch;
47 { // Init all the page locks.
48 for (int64 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);
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);
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;
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.
88 a = getA(modlength) % modlength;
93 // This is our final generator.
96 modlength_ = modlength;
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.
102 int64 FineLockPEQueue::getA(int64 m) {
105 if ((((remaining / 4) * 4) == remaining)) {
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) {
113 // Keep dividing it out until there's no more.
114 while (((remaining / i) * i) == remaining)
120 // Return 'a' as specified.
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.
127 int64 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--) {
134 for (int64 i = 2; i < possible_prime; i++) {
135 if (((possible_prime / i) * i) == possible_prime) {
141 return possible_prime;
144 // One is prime enough.
148 // Destructor: Clean-up allocated memory and destroy pthread locks.
149 FineLockPEQueue::~FineLockPEQueue() {
151 for (i = 0; i < q_size_; i++)
152 pthread_mutex_destroy(&(pagelocks_[i]));
155 for (i = 0; i < 4; i++) {
156 pthread_mutex_destroy(&(randlocks_[i]));
161 bool FineLockPEQueue::QueueAnalysis() {
162 const char *measurement = "Error";
165 if (queue_metric_ == kTries)
166 measurement = "Failed retrievals";
167 else if (queue_metric_ == kTouch)
168 measurement = "Reads per page";
170 // Buckets for each log2 access counts.
171 for (int b = 0; b < 32; b++) {
175 // Bucketize the page counts by highest bit set.
176 for (int64 i = 0; i < q_size_; i++) {
177 uint32 readcount = pages_[i].touch;
179 for (b = 0; b < 31; b++) {
180 if (readcount < (1 << b))
187 logprintf(12, "Log: %s histogram\n", measurement);
188 for (int b = 0; b < 32; b++) {
190 logprintf(12, "Log: %12d - %12d: %12d\n",
191 ((1 << b) >> 1), 1 << b, buckets[b]);
198 // Callback mechanism for exporting last action.
200 FineLockPEQueue *g_fpqueue = 0;
202 // Global callback to hook into Os object.
203 bool err_log_callback(uint64 paddr, string *buf) {
205 return g_fpqueue->ErrorLogCallback(paddr, buf);
211 // Setup global state for exporting callback.
212 void FineLockPEQueue::set_os(OsLayer *os) {
217 OsLayer::ErrCallback FineLockPEQueue::get_err_log_callback() {
218 return err_log_callback;
221 // This call is used to export last transaction info on a particular physical
223 bool FineLockPEQueue::ErrorLogCallback(uint64 paddr, string *message) {
224 struct page_entry pe;
229 // Find the page of this paddr.
230 int gotpage = GetPageFromPhysical(paddr, &pe);
235 // Find offset into the page.
236 uint64 addr_diff = paddr - pe.paddr;
238 // Find vaddr of this paddr. Make sure it matches,
239 // as sometimes virtual memory is not contiguous.
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_);
245 // Is the physical address at this page offset the same as
246 // the physical address we were given?
247 if (new_paddr != paddr) {
251 // Print all the info associated with this page.
252 message->assign(" (Last Transaction:");
254 if (pe.lastpattern) {
255 int offset = addr_diff / 8;
258 data.l32.l = pe.lastpattern->pattern(offset << 1);
259 data.l32.h = pe.lastpattern->pattern((offset << 1) + 1);
261 snprintf(buf, sizeof(buf), " %s data=%#016llx",
262 pe.lastpattern->name(), data.l64);
263 message->append(buf);
265 snprintf(buf, sizeof(buf), " tsc=%#llx)", pe.ts);
266 message->append(buf);
270 bool 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 (int64 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)) {
286 // Get a random number from the slot we locked.
287 uint64 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;
295 // Get a random number, we have 4 generators to choose from so hopefully we
296 // won't be blocking on this.
297 uint64 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]));
306 // Forget it, just wait.
308 if (pthread_mutex_lock(&(randlocks_[i])) == 0) {
309 uint64 result = GetRandom64FromSlot(i);
310 pthread_mutex_unlock(&(randlocks_[i]));
314 logprintf(0, "Process Error: Could not acquire random lock.\n");
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.
323 // Setting tag to a value other than kDontCareTag (-1)
324 // indicates that we need a tag match, otherwise any tag will do.
326 // Returns true on success, false on failure.
327 bool FineLockPEQueue::GetRandomWithPredicateTag(struct page_entry *pe,
328 bool (*pred_func)(struct page_entry*),
333 // Randomly index into page entry array.
334 uint64 first_try = GetRandom64() % q_size_;
337 // Traverse through array until finding a page meeting given predicate.
338 for (int64 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_);
350 // If page does not meet predicate, don't trylock (expensive).
351 if (!(pred_func)(&pages_[index]))
354 // If page does not meet tag predicate, don't trylock (expensive).
355 if ((tag != kDontCareTag) && !(pages_[index].tag & tag))
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]));
365 // A page entry with given predicate is locked, returns success.
368 // Add metrics as necessary.
369 if (pred_func == page_is_valid) {
370 // Measure time to fetch valid page.
371 if (queue_metric_ == kTries)
373 // Measure number of times each page is read.
374 if (queue_metric_ == kTouch)
387 bool FineLockPEQueue::GetRandomWithPredicate(struct page_entry *pe,
388 bool (*pred_func)(struct page_entry*)) {
389 return GetRandomWithPredicateTag(pe, pred_func, kDontCareTag);
393 // GetValid() randomly finds a valid page, locks it and returns page entry by
396 // Returns true on success, false on failure.
397 bool FineLockPEQueue::GetValid(struct page_entry *pe) {
398 return GetRandomWithPredicate(pe, page_is_valid);
401 bool FineLockPEQueue::GetValid(struct page_entry *pe, int32 mask) {
402 return GetRandomWithPredicateTag(pe, page_is_valid, mask);
405 // GetEmpty() randomly finds an empty page, locks it and returns page entry by
408 // Returns true on success, false on failure.
409 bool FineLockPEQueue::GetEmpty(struct page_entry *pe, int32 mask) {
410 return GetRandomWithPredicateTag(pe, page_is_empty, mask);
412 bool FineLockPEQueue::GetEmpty(struct page_entry *pe) {
413 return GetRandomWithPredicate(pe, page_is_empty);
416 // PutEmpty puts an empty page back into the queue, making it available by
417 // releasing the per-page-entry lock.
419 // Returns true on success, false on failure.
420 bool FineLockPEQueue::PutEmpty(struct page_entry *pe) {
424 int64 index = pe->offset / page_size_;
425 if (!valid_index(index))
429 // Enforce that page entry is indeed empty.
430 pages_[index].pattern = 0;
431 return (pthread_mutex_unlock(&(pagelocks_[index])) == 0);
434 // PutValid puts a valid page back into the queue, making it available by
435 // releasing the per-page-entry lock.
437 // Returns true on success, false on failure.
438 bool FineLockPEQueue::PutValid(struct page_entry *pe) {
439 if (!pe || !page_is_valid(pe) || !q_size_)
442 int64 index = pe->offset / page_size_;
443 if (!valid_index(index))
447 return (pthread_mutex_unlock(&(pagelocks_[index])) == 0);