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 page entry queue implementation with fine grain locks aim to ease
16 // lock contention over previous queue implementation (with one lock protecting
19 #ifndef STRESSAPPTEST_FINELOCK_QUEUE_H_
20 #define STRESSAPPTEST_FINELOCK_QUEUE_H_
24 // This file must work with autoconf on its public version,
25 // so these includes are correct.
28 #include "queue.h" // Using page_entry struct.
31 // This is a threadsafe randomized queue of pages with per-page entry lock
32 // for worker threads to use.
33 class FineLockPEQueue {
35 FineLockPEQueue(uint64 queuesize, int64 pagesize);
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);
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);
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);
55 // Not that much blocking random number generator.
57 uint64 GetRandom64FromSlot(int slot);
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_;
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;
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;
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*));
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*),
84 // Used to make a linear congruential path through the queue.
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.
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.
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
103 int64 a_; // 'a' multiplicative value for progressing
104 // linear congruentially through the list.
105 int64 c_; // 'c' additive value for prgressing randomly
107 int64 modlength_; // 'm' mod value for linear congruential
108 // generator. Used when q_size_ doesn't
109 // generate a good progression through the
112 uint64 rand_seed_[4]; // Random number state for 4 generators.
113 pthread_mutex_t randlocks_[4]; // Per-random-generator locks.
115 DISALLOW_COPY_AND_ASSIGN(FineLockPEQueue);
118 #endif // STRESSAPPTEST_FINELOCK_QUEUE_H_