• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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.
FineLockPEQueue(uint64 queuesize,int64 pagesize)37 FineLockPEQueue::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.
getA(int64 m)102 int64 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.
getC(int64 m)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--) {
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.
~FineLockPEQueue()149 FineLockPEQueue::~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 
QueueAnalysis()161 bool 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 
197 namespace {
198 // Callback mechanism for exporting last action.
199 OsLayer *g_os;
200 FineLockPEQueue *g_fpqueue = 0;
201 
202 // Global callback to hook into Os object.
err_log_callback(uint64 paddr,string * buf)203 bool 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.
set_os(OsLayer * os)212 void FineLockPEQueue::set_os(OsLayer *os) {
213   g_os = os;
214   g_fpqueue = this;
215 }
216 
get_err_log_callback()217 OsLayer::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.
ErrorLogCallback(uint64 paddr,string * message)223 bool 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 
GetPageFromPhysical(uint64 paddr,struct page_entry * pe)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 (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.
GetRandom64FromSlot(int slot)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;
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.
GetRandom64()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]));
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.
GetRandomWithPredicateTag(struct page_entry * pe,bool (* pred_func)(struct page_entry *),int32 tag)327 bool 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.
GetRandomWithPredicate(struct page_entry * pe,bool (* pred_func)(struct page_entry *))387 bool 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.
GetValid(struct page_entry * pe)397 bool FineLockPEQueue::GetValid(struct page_entry *pe) {
398   return GetRandomWithPredicate(pe, page_is_valid);
399 }
400 
GetValid(struct page_entry * pe,int32 mask)401 bool 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.
GetEmpty(struct page_entry * pe,int32 mask)409 bool FineLockPEQueue::GetEmpty(struct page_entry *pe, int32 mask) {
410   return GetRandomWithPredicateTag(pe, page_is_empty, mask);
411 }
GetEmpty(struct page_entry * pe)412 bool 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.
PutEmpty(struct page_entry * pe)420 bool 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.
PutValid(struct page_entry * pe)438 bool 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