7 //      http://www.apache.org/licenses/LICENSE-2.0
15 // This is an interface to a simple thread safe container with fine-grain locks,
23 // Page entry queue implementation follows.
25 // page entry, while preserving queue semantics.
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)
47   {  // Init all the page locks.  in FineLockPEQueue()
51         // A locked state indicates that the page state is unknown,  in FineLockPEQueue()
53         // the page records, they will be inserted and unlocked, at which point  in FineLockPEQueue()
69   // cause any page to be more likley chosen than another. The previous  in FineLockPEQueue()
100 // Get 'a', where a - 1 must be divisible by all prime
132   for (possible_prime = start; possible_prime > 1; possible_prime--) {  in getC()
148 // Destructor: Clean-up allocated memory and destroy pthread locks.
168     measurement = "Reads per page";  in QueueAnalysis()
175   // Bucketize the page counts by highest bit set.  in QueueAnalysis()
190       logprintf(12, "Log:  %12d - %12d: %12d\n",  in QueueAnalysis()
205     return g_fpqueue->ErrorLogCallback(paddr, buf);  in err_log_callback()
229   // Find the page of this paddr.  in ErrorLogCallback()
235   // Find offset into the page.  in ErrorLogCallback()
236   uint64 addr_diff = paddr - pe.paddr;  in ErrorLogCallback()
241     reinterpret_cast<char*>(os->PrepareTestMem(pe.offset, page_size_));  in ErrorLogCallback()
242   uint64 new_paddr = os->VirtualToPhysical(vaddr + addr_diff);  in ErrorLogCallback()
243   os->ReleaseTestMem(vaddr, pe.offset, page_size_);  in ErrorLogCallback()
245   // Is the physical address at this page offset the same as  in ErrorLogCallback()
251   // Print all the info associated with this page.  in ErrorLogCallback()
252   message->assign(" (Last Transaction:");  in ErrorLogCallback()
258     data.l32.l = pe.lastpattern->pattern(offset << 1);  in ErrorLogCallback()
259     data.l32.h = pe.lastpattern->pattern((offset << 1) + 1);  in ErrorLogCallback()
262                   pe.lastpattern->name(), data.l64);  in ErrorLogCallback()
263     message->append(buf);  in ErrorLogCallback()
266   message->append(buf);  in ErrorLogCallback()
272   // Traverse through array until finding a page  in GetPageFromPhysical()
320 // Helper function to get a random page entry with given predicate,
323 // Setting tag to a value other than kDontCareTag (-1)
333   // Randomly index into page entry array.  in GetRandomWithPredicateTag()
337   // Traverse through array until finding a page meeting given predicate.  in GetRandomWithPredicateTag()
339     uint64 index = (next_try + first_try) % q_size_;  in GetRandomWithPredicateTag()  local
350     // If page does not meet predicate, don't trylock (expensive).  in GetRandomWithPredicateTag()
351     if (!(pred_func)(&pages_[index]))  in GetRandomWithPredicateTag()
354     // If page does not meet tag predicate, don't trylock (expensive).  in GetRandomWithPredicateTag()
355     if ((tag != kDontCareTag) && !(pages_[index].tag & tag))  in GetRandomWithPredicateTag()
358     if (pthread_mutex_trylock(&(pagelocks_[index])) == 0) {  in GetRandomWithPredicateTag()
359       // If page property (valid/empty) changes before successfully locking,  in GetRandomWithPredicateTag()
360       // release page and move on.  in GetRandomWithPredicateTag()
361       if (!(pred_func)(&pages_[index])) {  in GetRandomWithPredicateTag()
362         pthread_mutex_unlock(&(pagelocks_[index]));  in GetRandomWithPredicateTag()
365         // A page entry with given predicate is locked, returns success.  in GetRandomWithPredicateTag()
366         *pe = pages_[index];  in GetRandomWithPredicateTag()
370           // Measure time to fetch valid page.  in GetRandomWithPredicateTag()
372             pe->touch = i;  in GetRandomWithPredicateTag()
373           // Measure number of times each page is read.  in GetRandomWithPredicateTag()
375             pe->touch++;  in GetRandomWithPredicateTag()
393 // GetValid() randomly finds a valid page, locks it and returns page entry by
405 // GetEmpty() randomly finds an empty page, locks it and returns page entry by
416 // PutEmpty puts an empty page back into the queue, making it available by
417 // releasing the per-page-entry lock.
424   int64 index = pe->offset / page_size_;  in PutEmpty()  local
425   if (!valid_index(index))  in PutEmpty()
428   pages_[index] = *pe;  in PutEmpty()
429   // Enforce that page entry is indeed empty.  in PutEmpty()
430   pages_[index].pattern = 0;  in PutEmpty()
431   return (pthread_mutex_unlock(&(pagelocks_[index])) == 0);  in PutEmpty()
434 // PutValid puts a valid page back into the queue, making it available by
435 // releasing the per-page-entry lock.
442   int64 index = pe->offset / page_size_;  in PutValid()  local
443   if (!valid_index(index))  in PutValid()
446   pages_[index] = *pe;  in PutValid()
447   return (pthread_mutex_unlock(&(pagelocks_[index])) == 0);  in PutValid()