chiark - git - ian - stressapptest/blob - src/finelock_queue.h

   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_