• 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 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.
valid_index(int64 index)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.
page_is_valid(struct page_entry * pe)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.
page_is_empty(struct page_entry * pe)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