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 page entry queue implementation with fine grain locks aim to ease 16 // lock contention over previous queue implementation (with one lock protecting 17 // the entire queue). 18 19 #ifndef STRESSAPPTEST_FINELOCK_QUEUE_H_ 20 #define STRESSAPPTEST_FINELOCK_QUEUE_H_ 21 22 #include <string> 23 24 // This file must work with autoconf on its public version, 25 // so these includes are correct. 26 #include "sattypes.h" 27 #include "pattern.h" 28 #include "queue.h" // Using page_entry struct. 29 #include "os.h" 30 31 // This is a threadsafe randomized queue of pages with per-page entry lock 32 // for worker threads to use. 33 class FineLockPEQueue { 34 public: 35 FineLockPEQueue(uint64 queuesize, int64 pagesize); 36 ~FineLockPEQueue(); 37 38 // Put and get functions for page entries. 39 bool GetEmpty(struct page_entry *pe); 40 bool GetValid(struct page_entry *pe); 41 bool PutEmpty(struct page_entry *pe); 42 bool PutValid(struct page_entry *pe); 43 44 // Put and get functions for page entries, selecting on tags. 45 bool GetEmpty(struct page_entry *pe, int32 tag); 46 bool GetValid(struct page_entry *pe, int32 tag); 47 48 bool QueueAnalysis(); 49 bool GetPageFromPhysical(uint64 paddr, struct page_entry *pe); 50 void set_os(OsLayer *os); 51 OsLayer::ErrCallback get_err_log_callback(); 52 bool ErrorLogCallback(uint64 paddr, string *buf); 53 54 private: 55 // Not that much blocking random number generator. 56 uint64 GetRandom64(); 57 uint64 GetRandom64FromSlot(int slot); 58 59 // Helper function to check index range, returns true if index is valid. 60 bool valid_index(int64 index) { 61 return index >= 0 && static_cast<uint64>(index) < q_size_; 62 } 63 64 // Returns true if page entry is valid, false otherwise. 65 static bool page_is_valid(struct page_entry *pe) { 66 return pe->pattern != NULL; 67 } 68 // Returns true if page entry is empty, false otherwise. 69 static bool page_is_empty(struct page_entry *pe) { 70 return pe->pattern == NULL; 71 } 72 73 // Helper function to get a random page entry with given predicate, 74 // ie, page_is_valid() or page_is_empty() as defined above. 75 bool GetRandomWithPredicate(struct page_entry *pe, 76 bool (*pred_func)(struct page_entry*)); 77 78 // Helper function to get a random page entry with given predicate, 79 // ie, page_is_valid() or page_is_empty() as defined above. 80 bool GetRandomWithPredicateTag(struct page_entry *pe, 81 bool (*pred_func)(struct page_entry*), 82 int32 tag); 83 84 // Used to make a linear congruential path through the queue. 85 int64 getA(int64 m); 86 int64 getC(int64 m); 87 88 pthread_mutex_t *pagelocks_; // Per-page-entry locks. 89 struct page_entry *pages_; // Where page entries are held. 90 uint64 q_size_; // Size of the queue. 91 int64 page_size_; // For calculating array index from offset. 92 93 enum { 94 kTries = 1, // Measure the number of attempts in the queue 95 // before getting a matching page. 96 kTouch = 2 } // Measure the number of touches on each page. 97 queue_metric_; // What to measure in the 'tries' field. 98 99 // Progress pseudorandomly through the queue. It's required that we can find 100 // every value in the list, but progressing through the same order each time 101 // causes bunching of pages, leading to long seach times for the correct 102 // type of pages. 103 int64 a_; // 'a' multiplicative value for progressing 104 // linear congruentially through the list. 105 int64 c_; // 'c' additive value for prgressing randomly 106 // through the list. 107 int64 modlength_; // 'm' mod value for linear congruential 108 // generator. Used when q_size_ doesn't 109 // generate a good progression through the 110 // list. 111 112 uint64 rand_seed_[4]; // Random number state for 4 generators. 113 pthread_mutex_t randlocks_[4]; // Per-random-generator locks. 114 115 DISALLOW_COPY_AND_ASSIGN(FineLockPEQueue); 116 }; 117 118 #endif // STRESSAPPTEST_FINELOCK_QUEUE_H_ 119