// Copyright 2007 Google Inc. All Rights Reserved.
|
|
// Licensed under the Apache License, Version 2.0 (the "License");
|
// you may not use this file except in compliance with the License.
|
// You may obtain a copy of the License at
|
|
// http://www.apache.org/licenses/LICENSE-2.0
|
|
// Unless required by applicable law or agreed to in writing, software
|
// distributed under the License is distributed on an "AS IS" BASIS,
|
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
// See the License for the specific language governing permissions and
|
// limitations under the License.
|
|
// This is an interface to a simple thread safe container with fine-grain locks,
|
// used to hold data blocks and patterns.
|
|
// This file must work with autoconf on its public version,
|
// so these includes are correct.
|
#include "finelock_queue.h"
|
#include "os.h"
|
|
// Page entry queue implementation follows.
|
// Push and Get functions are analogous to lock and unlock operations on a given
|
// page entry, while preserving queue semantics.
|
//
|
// The actual 'queue' implementation is actually just an array. The entries are
|
// never shuffled or re-ordered like that of a real queue. Instead, Get
|
// functions return a random page entry of a given type and lock that particular
|
// page entry until it is unlocked by corresponding Put functions.
|
//
|
// In this implementation, a free page is those page entries where pattern is
|
// null (pe->pattern == 0)
|
|
|
// Constructor: Allocates memory and initialize locks.
|
FineLockPEQueue::FineLockPEQueue(
|
uint64 queuesize, int64 pagesize) {
|
q_size_ = queuesize;
|
pages_ = new struct page_entry[q_size_];
|
pagelocks_ = new pthread_mutex_t[q_size_];
|
page_size_ = pagesize;
|
|
// What metric should we measure this run.
|
queue_metric_ = kTouch;
|
|
{ // Init all the page locks.
|
for (uint64 i = 0; i < q_size_; i++) {
|
pthread_mutex_init(&(pagelocks_[i]), NULL);
|
// Pages start out owned (locked) by Sat::InitializePages.
|
// A locked state indicates that the page state is unknown,
|
// and the lock should not be aquired. As InitializePages creates
|
// the page records, they will be inserted and unlocked, at which point
|
// they are ready to be aquired and filled by worker threads.
|
sat_assert(pthread_mutex_lock(&(pagelocks_[i])) == 0);
|
}
|
}
|
|
{ // Init the random number generator.
|
for (int i = 0; i < 4; i++) {
|
rand_seed_[i] = i + 0xbeef;
|
pthread_mutex_init(&(randlocks_[i]), NULL);
|
}
|
}
|
|
// Try to make a linear congruential generator with our queue size.
|
// We need this to deterministically search all the queue (being able to find
|
// a single available element is a design requirement), but we don't want to
|
// cause any page to be more likley chosen than another. The previous
|
// sequential retry heavily biased pages at the beginning of a bunch, or
|
// isolated pages surrounded by unqualified ones.
|
int64 length = queuesize;
|
int64 modlength = length;
|
int64 a;
|
int64 c;
|
|
if (length < 3) {
|
a = 1;
|
c = 1;
|
} else {
|
// Search for a nontrivial generator.
|
a = getA(length) % length;
|
// If this queue size doesn't have a nontrivial generator (where the
|
// multiplier is greater then one) we'll check increasing queue sizes,
|
// and discard out of bounds results.
|
while (a == 1) {
|
modlength++;
|
a = getA(modlength) % modlength;
|
}
|
c = getC(modlength);
|
}
|
|
// This is our final generator.
|
a_ = a;
|
c_ = c;
|
modlength_ = modlength;
|
}
|
|
// Part of building a linear congruential generator n1 = (a * n0 + c) % m
|
// Get 'a', where a - 1 must be divisible by all prime
|
// factors of 'm', our queue size.
|
int64 FineLockPEQueue::getA(int64 m) {
|
int64 remaining = m;
|
int64 a = 1;
|
if ((((remaining / 4) * 4) == remaining)) {
|
a = 2;
|
}
|
// For each number, let's see if it's divisible,
|
// then divide it out.
|
for (int64 i = 2; i <= m; i++) {
|
if (((remaining / i) * i) == remaining) {
|
remaining /= i;
|
// Keep dividing it out until there's no more.
|
while (((remaining / i) * i) == remaining)
|
remaining /= i;
|
a *= i;
|
}
|
}
|
|
// Return 'a' as specified.
|
return (a + 1) % m;
|
}
|
|
|
// Part of building a linear congruential generator n1 = (a * n0 + c) % m
|
// Get a prime number approx 3/4 the size of our queue.
|
int64 FineLockPEQueue::getC(int64 m) {
|
// Start here at 3/4.
|
int64 start = (3 * m) / 4 + 1;
|
int64 possible_prime = start;
|
// Keep trying until we find a prime.
|
for (possible_prime = start; possible_prime > 1; possible_prime--) {
|
bool failed = false;
|
for (int64 i = 2; i < possible_prime; i++) {
|
if (((possible_prime / i) * i) == possible_prime) {
|
failed = true;
|
break;
|
}
|
}
|
if (!failed) {
|
return possible_prime;
|
}
|
}
|
// One is prime enough.
|
return 1;
|
}
|
|
// Destructor: Clean-up allocated memory and destroy pthread locks.
|
FineLockPEQueue::~FineLockPEQueue() {
|
uint64 i;
|
for (i = 0; i < q_size_; i++)
|
pthread_mutex_destroy(&(pagelocks_[i]));
|
delete[] pagelocks_;
|
delete[] pages_;
|
for (i = 0; i < 4; i++) {
|
pthread_mutex_destroy(&(randlocks_[i]));
|
}
|
}
|
|
|
bool FineLockPEQueue::QueueAnalysis() {
|
const char *measurement = "Error";
|
uint64 buckets[32];
|
|
if (queue_metric_ == kTries)
|
measurement = "Failed retrievals";
|
else if (queue_metric_ == kTouch)
|
measurement = "Reads per page";
|
|
// Buckets for each log2 access counts.
|
for (int b = 0; b < 32; b++) {
|
buckets[b] = 0;
|
}
|
|
// Bucketize the page counts by highest bit set.
|
for (uint64 i = 0; i < q_size_; i++) {
|
uint32 readcount = pages_[i].touch;
|
int b = 0;
|
for (b = 0; b < 31; b++) {
|
if (readcount < (1u << b))
|
break;
|
}
|
|
buckets[b]++;
|
}
|
|
logprintf(12, "Log: %s histogram\n", measurement);
|
for (int b = 0; b < 32; b++) {
|
if (buckets[b])
|
logprintf(12, "Log: %12d - %12d: %12d\n",
|
((1 << b) >> 1), 1 << b, buckets[b]);
|
}
|
|
return true;
|
}
|
|
namespace {
|
// Callback mechanism for exporting last action.
|
OsLayer *g_os;
|
FineLockPEQueue *g_fpqueue = 0;
|
|
// Global callback to hook into Os object.
|
bool err_log_callback(uint64 paddr, string *buf) {
|
if (g_fpqueue) {
|
return g_fpqueue->ErrorLogCallback(paddr, buf);
|
}
|
return false;
|
}
|
}
|
|
// Setup global state for exporting callback.
|
void FineLockPEQueue::set_os(OsLayer *os) {
|
g_os = os;
|
g_fpqueue = this;
|
}
|
|
OsLayer::ErrCallback FineLockPEQueue::get_err_log_callback() {
|
return err_log_callback;
|
}
|
|
// This call is used to export last transaction info on a particular physical
|
// address.
|
bool FineLockPEQueue::ErrorLogCallback(uint64 paddr, string *message) {
|
struct page_entry pe;
|
OsLayer *os = g_os;
|
sat_assert(g_os);
|
char buf[256];
|
|
// Find the page of this paddr.
|
int gotpage = GetPageFromPhysical(paddr, &pe);
|
if (!gotpage) {
|
return false;
|
}
|
|
// Find offset into the page.
|
uint64 addr_diff = paddr - pe.paddr;
|
|
// Find vaddr of this paddr. Make sure it matches,
|
// as sometimes virtual memory is not contiguous.
|
char *vaddr =
|
reinterpret_cast<char*>(os->PrepareTestMem(pe.offset, page_size_));
|
uint64 new_paddr = os->VirtualToPhysical(vaddr + addr_diff);
|
os->ReleaseTestMem(vaddr, pe.offset, page_size_);
|
|
// Is the physical address at this page offset the same as
|
// the physical address we were given?
|
if (new_paddr != paddr) {
|
return false;
|
}
|
|
// Print all the info associated with this page.
|
message->assign(" (Last Transaction:");
|
|
if (pe.lastpattern) {
|
int offset = addr_diff / 8;
|
datacast_t data;
|
|
data.l32.l = pe.lastpattern->pattern(offset << 1);
|
data.l32.h = pe.lastpattern->pattern((offset << 1) + 1);
|
|
snprintf(buf, sizeof(buf), " %s data=%#016llx",
|
pe.lastpattern->name(), data.l64);
|
message->append(buf);
|
}
|
snprintf(buf, sizeof(buf), " tsc=%#llx)", pe.ts);
|
message->append(buf);
|
return true;
|
}
|
|
bool FineLockPEQueue::GetPageFromPhysical(uint64 paddr,
|
struct page_entry *pe) {
|
// Traverse through array until finding a page
|
// that contains the address we want..
|
for (uint64 i = 0; i < q_size_; i++) {
|
uint64 page_addr = pages_[i].paddr;
|
// This assumes linear vaddr.
|
if ((page_addr <= paddr) && (page_addr + page_size_ > paddr)) {
|
*pe = pages_[i];
|
return true;
|
}
|
}
|
return false;
|
}
|
|
|
// Get a random number from the slot we locked.
|
uint64 FineLockPEQueue::GetRandom64FromSlot(int slot) {
|
// 64 bit LCG numbers suggested on the internets by
|
// http://nuclear.llnl.gov/CNP/rng/rngman/node4.html and others.
|
uint64 result = 2862933555777941757ULL * rand_seed_[slot] + 3037000493ULL;
|
rand_seed_[slot] = result;
|
return result;
|
}
|
|
// Get a random number, we have 4 generators to choose from so hopefully we
|
// won't be blocking on this.
|
uint64 FineLockPEQueue::GetRandom64() {
|
// Try each available slot.
|
for (int i = 0; i < 4; i++) {
|
if (pthread_mutex_trylock(&(randlocks_[i])) == 0) {
|
uint64 result = GetRandom64FromSlot(i);
|
pthread_mutex_unlock(&(randlocks_[i]));
|
return result;
|
}
|
}
|
// Forget it, just wait.
|
int i = 0;
|
if (pthread_mutex_lock(&(randlocks_[i])) == 0) {
|
uint64 result = GetRandom64FromSlot(i);
|
pthread_mutex_unlock(&(randlocks_[i]));
|
return result;
|
}
|
|
logprintf(0, "Process Error: Could not acquire random lock.\n");
|
sat_assert(0);
|
return 0;
|
}
|
|
|
// Helper function to get a random page entry with given predicate,
|
// ie, page_is_valid() or page_is_empty() as defined in finelock_queue.h.
|
//
|
// Setting tag to a value other than kDontCareTag (-1)
|
// indicates that we need a tag match, otherwise any tag will do.
|
//
|
// Returns true on success, false on failure.
|
bool FineLockPEQueue::GetRandomWithPredicateTag(struct page_entry *pe,
|
bool (*pred_func)(struct page_entry*),
|
int32 tag) {
|
if (!pe || !q_size_)
|
return false;
|
|
// Randomly index into page entry array.
|
uint64 first_try = GetRandom64() % q_size_;
|
uint64 next_try = 1;
|
|
// Traverse through array until finding a page meeting given predicate.
|
for (uint64 i = 0; i < q_size_; i++) {
|
uint64 index = (next_try + first_try) % q_size_;
|
// Go through the loop linear conguentially. We are offsetting by
|
// 'first_try' so this path will be a different sequence for every
|
// initioal value chosen.
|
next_try = (a_ * next_try + c_) % (modlength_);
|
while (next_try >= q_size_) {
|
// If we have chosen a modlength greater than the queue size,
|
// discard out of bounds results.
|
next_try = (a_ * next_try + c_) % (modlength_);
|
}
|
|
// If page does not meet predicate, don't trylock (expensive).
|
if (!(pred_func)(&pages_[index]))
|
continue;
|
|
// If page does not meet tag predicate, don't trylock (expensive).
|
if ((tag != kDontCareTag) && !(pages_[index].tag & tag))
|
continue;
|
|
if (pthread_mutex_trylock(&(pagelocks_[index])) == 0) {
|
// If page property (valid/empty) changes before successfully locking,
|
// release page and move on.
|
if (!(pred_func)(&pages_[index])) {
|
pthread_mutex_unlock(&(pagelocks_[index]));
|
continue;
|
} else {
|
// A page entry with given predicate is locked, returns success.
|
*pe = pages_[index];
|
|
// Add metrics as necessary.
|
if (pred_func == page_is_valid) {
|
// Measure time to fetch valid page.
|
if (queue_metric_ == kTries)
|
pe->touch = i;
|
// Measure number of times each page is read.
|
if (queue_metric_ == kTouch)
|
pe->touch++;
|
}
|
|
return true;
|
}
|
}
|
}
|
|
return false;
|
}
|
|
// Without tag hint.
|
bool FineLockPEQueue::GetRandomWithPredicate(struct page_entry *pe,
|
bool (*pred_func)(struct page_entry*)) {
|
return GetRandomWithPredicateTag(pe, pred_func, kDontCareTag);
|
}
|
|
|
// GetValid() randomly finds a valid page, locks it and returns page entry by
|
// pointer.
|
//
|
// Returns true on success, false on failure.
|
bool FineLockPEQueue::GetValid(struct page_entry *pe) {
|
return GetRandomWithPredicate(pe, page_is_valid);
|
}
|
|
bool FineLockPEQueue::GetValid(struct page_entry *pe, int32 mask) {
|
return GetRandomWithPredicateTag(pe, page_is_valid, mask);
|
}
|
|
// GetEmpty() randomly finds an empty page, locks it and returns page entry by
|
// pointer.
|
//
|
// Returns true on success, false on failure.
|
bool FineLockPEQueue::GetEmpty(struct page_entry *pe, int32 mask) {
|
return GetRandomWithPredicateTag(pe, page_is_empty, mask);
|
}
|
bool FineLockPEQueue::GetEmpty(struct page_entry *pe) {
|
return GetRandomWithPredicate(pe, page_is_empty);
|
}
|
|
// PutEmpty puts an empty page back into the queue, making it available by
|
// releasing the per-page-entry lock.
|
//
|
// Returns true on success, false on failure.
|
bool FineLockPEQueue::PutEmpty(struct page_entry *pe) {
|
if (!pe || !q_size_)
|
return false;
|
|
int64 index = pe->offset / page_size_;
|
if (!valid_index(index))
|
return false;
|
|
pages_[index] = *pe;
|
// Enforce that page entry is indeed empty.
|
pages_[index].pattern = 0;
|
return (pthread_mutex_unlock(&(pagelocks_[index])) == 0);
|
}
|
|
// PutValid puts a valid page back into the queue, making it available by
|
// releasing the per-page-entry lock.
|
//
|
// Returns true on success, false on failure.
|
bool FineLockPEQueue::PutValid(struct page_entry *pe) {
|
if (!pe || !page_is_valid(pe) || !q_size_)
|
return false;
|
|
int64 index = pe->offset / page_size_;
|
if (!valid_index(index))
|
return false;
|
|
pages_[index] = *pe;
|
return (pthread_mutex_unlock(&(pagelocks_[index])) == 0);
|
}
|
