← Back to branch summary

~alinuxninja/nginx-edge/trunk

« back to all changes in this revision

Viewing changes to debian/modules/ngx_pagespeed/psol/include/pagespeed/kernel/cache/purge_set.h

  • Committer: Vivian
  • Date: 2015-12-04 18:20:11 UTC
  • Revision ID: git-v1:a36f2bc32e884f7473b3a47040e5411306144d7d
* Do not extract psol.tar.gz

Show diffs side-by-side

added added

removed removed

Lines of Context:
debian/modules/ngx_pagespeed/psol/include/pagespeed/kernel/cache/purge_set.h
1
 
/*
2
 
 * Copyright 2013 Google Inc.
3
 
 *
4
 
 * Licensed under the Apache License, Version 2.0 (the "License");
5
 
 * you may not use this file except in compliance with the License.
6
 
 * You may obtain a copy of the License at
7
 
 *
8
 
 *      http://www.apache.org/licenses/LICENSE-2.0
9
 
 *
10
 
 * Unless required by applicable law or agreed to in writing, software
11
 
 * distributed under the License is distributed on an "AS IS" BASIS,
12
 
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13
 
 * See the License for the specific language governing permissions and
14
 
 * limitations under the License.
15
 
 */
16
 
 
17
 
// Author: jmarantz@google.com (Joshua Marantz)
18
 
 
19
 
#ifndef NET_INSTAWEB_UTIL_PUBLIC_PURGE_SET_H_
20
 
#define NET_INSTAWEB_UTIL_PUBLIC_PURGE_SET_H_
21
 
 
22
 
#include <algorithm>
23
 
#include <cstddef>
24
 
 
25
 
#include "pagespeed/kernel/base/basictypes.h"
26
 
#include "pagespeed/kernel/base/scoped_ptr.h"
27
 
#include "pagespeed/kernel/base/string.h"
28
 
#include "pagespeed/kernel/base/timer.h"
29
 
#include "pagespeed/kernel/cache/lru_cache_base.h"
30
 
 
31
 
namespace net_instaweb {
32
 
 
33
 
 
34
 
 
35
 
// Maintains a bounded collection of cache-purge records.  These can
36
 
// be used to validate data read from a cache.
37
 
//
38
 
// The entire cache can be flushed as of a certain point in time by
39
 
// calling UpdateInvalidationTimestampMs.
40
 
//
41
 
// We bound the cache-purge data to a certain number of bytes.  When
42
 
// we exceed that, we discard old invalidation records, and bump up
43
 
// the global invalidation timestamp to cover the evicted purges.
44
 
class PurgeSet {
45
 
  class InvalidationTimestampHelper;
46
 
  typedef LRUCacheBase<int64, InvalidationTimestampHelper> Lru;
47
 
 
48
 
 public:
49
 
  typedef Lru::Iterator Iterator;
50
 
 
51
 
  // Used for sanity checking timestamps read from the cache.flush file,
52
 
  // allowing for small skew and system clock adjustments.  Setting this
53
 
  // to 10 minutes means that we can prevent any cache entries from
54
 
  // being valid for 10 minutes, disabling whatever functionality is
55
 
  // dependent on that.
56
 
  static const int64 kClockSkewAllowanceMs = 10 * Timer::kMinuteMs;
57
 
 
58
 
  // Initial value used for the global timestamp.  This means there
59
 
  // is no valid timestamp.
60
 
  static const int64 kInitialTimestampMs = -1;
61
 
 
62
 
  // The default constructor makes a 1-byte invalidation set.  Use
63
 
  // set_max_size after construction.  The default constructor is
64
 
  // needed for CopyOnWrite.
65
 
  PurgeSet();
66
 
 
67
 
  explicit PurgeSet(size_t max_size);
68
 
  PurgeSet(const PurgeSet& src);
69
 
  ~PurgeSet();
70
 
 
71
 
  // Call this immediately after construction.
72
 
  void set_max_size(size_t x) { lru_->set_max_bytes_in_cache(x); }
73
 
 
74
 
  PurgeSet& operator=(const PurgeSet& src);
75
 
 
76
 
  // Flushes any item in the cache older than timestamp_ms.
77
 
  //
78
 
  //
79
 
  // Returns false if this request represents an excessive warp back in
80
 
  // time.
81
 
  bool UpdateGlobalInvalidationTimestampMs(int64 timestamp_ms);
82
 
 
83
 
  // Adds a new cache purge record to the set.  If we spill over our
84
 
  // invalidation limit, we will reset the global cache purge-point based
85
 
  // on the evicted node.
86
 
  //
87
 
  // Returns false if this request represents an excessive warp back in
88
 
  // time.
89
 
  bool Put(const GoogleString& key, int64 timestamp_ms);
90
 
 
91
 
  // Merge two invalidation records.
92
 
  void Merge(const PurgeSet& src);
93
 
 
94
 
  // Validates a key against specific invalidation records for that
95
 
  // key, and against the overall invalidation timestamp/
96
 
  bool IsValid(const GoogleString& key, int64 timestamp_ms) const;
97
 
 
98
 
  int64 global_invalidation_timestamp_ms() const {
99
 
    return global_invalidation_timestamp_ms_;
100
 
  }
101
 
 
102
 
  bool has_global_invalidation_timestamp_ms() const {
103
 
    return global_invalidation_timestamp_ms_ != kInitialTimestampMs;
104
 
  }
105
 
 
106
 
  Iterator Begin() const { return lru_->Begin(); }
107
 
  Iterator End() const { return lru_->End(); }
108
 
 
109
 
  int num_elements() const { return lru_->num_elements(); }
110
 
  void Clear();
111
 
  void Swap(PurgeSet* that);
112
 
 
113
 
  bool Equals(const PurgeSet& that) const;
114
 
  bool empty() const;
115
 
 
116
 
  GoogleString ToString() const;
117
 
 
118
 
 private:
119
 
  class InvalidationTimestampHelper {
120
 
   public:
121
 
    explicit InvalidationTimestampHelper(PurgeSet* purge_set)
122
 
        : purge_set_(purge_set) {
123
 
    }
124
 
 
125
 
    size_t size(int64 value) const {
126
 
      return sizeof(value);
127
 
    }
128
 
    bool Equal(int64 a, int64 b) const {
129
 
      return a == b;
130
 
    }
131
 
 
132
 
    // Update global invalidation timestamp whenever a purge record is
133
 
    // evicted to guarantee that that resource remains purged.
134
 
    void EvictNotify(int64 evicted_record_timestamp_ms) {
135
 
      purge_set_->EvictNotify(evicted_record_timestamp_ms);
136
 
    }
137
 
 
138
 
    // Only replace purge records if the new one is newer.
139
 
    bool ShouldReplace(int64 old_timestamp_ms, int64 new_timestamp_ms) const {
140
 
      return new_timestamp_ms > old_timestamp_ms;
141
 
    }
142
 
 
143
 
    void Swap(InvalidationTimestampHelper* that) {
144
 
      std::swap(purge_set_, that->purge_set_);
145
 
    }
146
 
 
147
 
   private:
148
 
    PurgeSet* purge_set_;
149
 
  };
150
 
 
151
 
  friend class InvalidationTimestampHelper;
152
 
 
153
 
  void EvictNotify(int64 evicted_record_timestamp_ms);
154
 
 
155
 
  // Determines whether this timestamp is monotonically increasing from
156
 
  // previous ones encountered.  Small amounts of time-reversal are handled
157
 
  // by setting them to a recently observed time.  Large amounts of
158
 
  // time-reversal cause false to be returned.
159
 
  //
160
 
  // Here several scenarios:
161
 
  //   1. Time goes backward by a few mintues or less:
162
 
  //      a. On purge requests, force monotonically increasing time.
163
 
  //      b. IsValid: we may report false negatives, disabling PageSpeed
164
 
  //         for a few minutes.
165
 
  //   2. Time moves backward by a large amount (>10 minutes):
166
 
  //      a. Purge requests: rejected until time is corrected.  The only
167
 
  //         sure-fire remedy is to delete all caches, restart memcached
168
 
  //         and pagespeed servers.
169
 
  //      b. IsValid: returns false, disabling PageSpeed until the situation
170
 
  //         is corrected.  We view it as unacceptable to bring purged cache
171
 
  //         entries back from the dead.
172
 
  // TODO(jmarantz): add a statistic that gets bumped from IsValid when
173
 
  // a far-future expires is detected.
174
 
  bool SanitizeTimestamp(int64* timestamp_ms);
175
 
 
176
 
  // Global invalidation timestamp value. Anything with a timestamp older than
177
 
  // this is considered purged already.
178
 
  int64 global_invalidation_timestamp_ms_;
179
 
 
180
 
  // last_invalidation_timestamp_ms is used to keep the data structure invariant
181
 
  // in the face of time jumping backwards.  That can happen if someone resets
182
 
  // the system-clock or there is a correction due to NTP sync, etc.
183
 
  int64 last_invalidation_timestamp_ms_;
184
 
 
185
 
  InvalidationTimestampHelper helper_;
186
 
  scoped_ptr<Lru> lru_;
187
 
 
188
 
  // Explicit copy-constructor and assign-operator are provided so
189
 
  // this class can be used for CopyOnWrite.
190
 
};
191
 
 
192
 
}  // namespace net_instaweb
193
 
 
194
 
#endif  // NET_INSTAWEB_UTIL_PUBLIC_PURGE_SET_H_