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.
33class 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