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