← 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/sharedmem/shared_mem_cache_data.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/sharedmem/shared_mem_cache_data.h
1
 
/*
2
 
 * Copyright 2011 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: morlovich@google.com (Maksim Orlovich)
18
 
 
19
 
// Data structure operation helpers for SharedMemCache. See the top of
20
 
// shared_mem_cache.cc for data format descriptions.
21
 
 
22
 
#ifndef PAGESPEED_KERNEL_SHAREDMEM_SHARED_MEM_CACHE_DATA_H_
23
 
#define PAGESPEED_KERNEL_SHAREDMEM_SHARED_MEM_CACHE_DATA_H_
24
 
 
25
 
#include <cstddef>                     // for size_t
26
 
#include <vector>
27
 
 
28
 
#include "base/logging.h"
29
 
#include "pagespeed/kernel/base/basictypes.h"
30
 
#include "pagespeed/kernel/base/scoped_ptr.h"
31
 
#include "pagespeed/kernel/base/string.h"
32
 
#include "pagespeed/kernel/base/thread_annotations.h"
33
 
 
34
 
namespace net_instaweb {
35
 
 
36
 
class AbstractMutex;
37
 
class AbstractSharedMem;
38
 
class AbstractSharedMemSegment;
39
 
class MessageHandler;
40
 
 
41
 
namespace SharedMemCacheData {
42
 
 
43
 
typedef int32 EntryNum;
44
 
typedef int32 BlockNum;
45
 
typedef std::vector<BlockNum> BlockVector;
46
 
 
47
 
const BlockNum kInvalidBlock = -1;
48
 
const EntryNum kInvalidEntry = -1;
49
 
const size_t kHashSize = 16;
50
 
 
51
 
struct SectorStats {
52
 
  SectorStats();
53
 
 
54
 
  // FS operation stats --- updated by SharedMemCache. We do it
55
 
  // this way rather than using the normal Statistics interface
56
 
  // to avoid having to worry about extra synchronization inside
57
 
  // critical sections --- since we already hold sector locks
58
 
  // when doing this stuff, it's easy to update per-sector data.
59
 
  // TODO(morlovich): Consider periodically pushing these to
60
 
  // normal Statistics.
61
 
  int64 num_put;
62
 
  int64 num_put_update;  // update of the same key
63
 
  int64 num_put_replace;  // replacement of different key
64
 
  int64 num_put_concurrent_create;
65
 
  int64 num_put_concurrent_full_set;
66
 
  int64 num_put_spins;  // # of times writers had to sleep behind readers
67
 
  int64 num_get;    // # of calls to get
68
 
  int64 num_get_hit;
69
 
 
70
 
  // Current state stats --- updated by SharedMemCacheData
71
 
  int64 used_entries;
72
 
  int64 used_blocks;
73
 
 
74
 
  // Adds number to this object's. No concurrency control is done.
75
 
  void Add(const SectorStats& other);
76
 
 
77
 
  // Text dump of the statistics. No concurrency control is done.
78
 
  GoogleString Dump(size_t total_entries, size_t total_blocks) const;
79
 
};
80
 
 
81
 
struct SectorHeader {
82
 
  BlockNum free_list_front;
83
 
  EntryNum lru_list_front;
84
 
  EntryNum lru_list_rear;
85
 
  int32 padding;
86
 
 
87
 
  SectorStats stats;
88
 
 
89
 
  // mutex goes here.
90
 
};
91
 
 
92
 
struct CacheEntry {
93
 
  char hash_bytes[kHashSize];
94
 
  int64 last_use_timestamp_ms;
95
 
  int32 byte_size;
96
 
 
97
 
  // For LRU list, prev/next are kInvalidEntry to denote 'none', which
98
 
  // can apply both at endpoints and for entries not in the LRU at all,
99
 
  // due to being free.
100
 
  EntryNum lru_prev;
101
 
  EntryNum lru_next;
102
 
 
103
 
  BlockNum first_block;
104
 
 
105
 
  // When this is true, someone is trying to overwrite this entry.
106
 
  bool creating : 1;
107
 
 
108
 
  // Number of readers currently accessing the data.
109
 
  uint32 open_count : 31;
110
 
 
111
 
  uint32 padding;  // ensures we're 8-aligned.
112
 
};
113
 
 
114
 
// Helper for operating on a given sector's data structures; helping
115
 
// access them, lay them out in memory, and initialize them. It does not
116
 
// implement the actual cache operations, however. In particular, its
117
 
// methods affect only a single data structure at the time and do not
118
 
// do anything to preserve cross-structure invariants.
119
 
template<size_t kBlockSize>
120
 
class Sector {
121
 
 public:
122
 
  // Creates a wrapper to help operate on cache sectors in a given region of
123
 
  // memory with given geometry.  The sector should have had as much memory
124
 
  // allocated for it as returned by a call to RequiredSize with the same
125
 
  // arguments.
126
 
  //
127
 
  // Note that this doesn't do any imperative initialization; you must
128
 
  // call Initialize() in the parent process, and Attach() in child processes,
129
 
  // and check their results as well. Also, segment is assumed to be owned
130
 
  // separately, with lifetime longer than ours.
131
 
  Sector(AbstractSharedMemSegment* segment, size_t sector_offset,
132
 
         size_t cache_entries, size_t data_blocks);
133
 
  ~Sector();
134
 
 
135
 
  // This should be called from child processes to initialize client
136
 
  // state for the cache already formatted by a call to Initialize() in
137
 
  // the parent.
138
 
  //
139
 
  // Returns if successful (which it should be if the parent process
140
 
  // successfully create the memory and Initialize()'d it).
141
 
  bool Attach(MessageHandler* handler);
142
 
 
143
 
  // This should be called from the initial/parent process before the children
144
 
  // start. It initializes the data structures in this sector, including
145
 
  // mutexes. Returns true on success.
146
 
  bool Initialize(MessageHandler* handler);
147
 
 
148
 
  // Computes how much memory a sector will need for given number of entries.
149
 
  // Also makes sure it's padded to proper alignment.
150
 
  static size_t RequiredSize(AbstractSharedMem* shmem_runtime,
151
 
                             size_t cache_entries, size_t data_blocks);
152
 
 
153
 
  // Mutex ops.
154
 
 
155
 
  // The sector lock should be held while doing any metadata accesses.
156
 
  AbstractMutex* mutex() const LOCK_RETURNED(mutex_) { return mutex_.get(); }
157
 
 
158
 
  // Block successor list ops.
159
 
  // ------------------------------------------------------------
160
 
  BlockNum GetBlockSuccessor(BlockNum block) EXCLUSIVE_LOCKS_REQUIRED(mutex()) {
161
 
    DCHECK_GE(block, 0);
162
 
    DCHECK_LT(block, static_cast<BlockNum>(data_blocks_));
163
 
    return block_successors_[block];
164
 
  }
165
 
 
166
 
  void SetBlockSuccessor(BlockNum block, BlockNum next)
167
 
      EXCLUSIVE_LOCKS_REQUIRED(mutex()) {
168
 
    DCHECK_GE(block, 0);
169
 
    DCHECK_LT(block, static_cast<BlockNum>(data_blocks_));
170
 
 
171
 
    DCHECK_GE(next, kInvalidBlock);
172
 
    DCHECK_LT(next, static_cast<BlockNum>(data_blocks_));
173
 
 
174
 
    block_successors_[block] = next;
175
 
  }
176
 
 
177
 
  // Links blocks in the vector in order, with later blocks being
178
 
  // marked as successors of later ones.
179
 
  void LinkBlockSuccessors(const BlockVector& blocks)
180
 
      EXCLUSIVE_LOCKS_REQUIRED(mutex()) {
181
 
    for (size_t pos = 0; pos < blocks.size(); ++pos) {
182
 
      if (pos == (blocks.size() - 1)) {
183
 
        SetBlockSuccessor(blocks[pos], kInvalidBlock);
184
 
      } else {
185
 
        SetBlockSuccessor(blocks[pos], blocks[pos + 1]);
186
 
      }
187
 
    }
188
 
  }
189
 
 
190
 
  // Freelist ops.
191
 
  // ------------------------------------------------------------
192
 
 
193
 
  // Allocates as close to the goal blocks from freelist as it can, and
194
 
  // appends their numbers to blocks. Returns how much it allocated.
195
 
  // Does not adjust block successor lists.
196
 
  //
197
 
  // Note that this doesn't attempt to free blocks that are in use by some
198
 
  // entries.
199
 
  int AllocBlocksFromFreeList(int goal, BlockVector* blocks)
200
 
      EXCLUSIVE_LOCKS_REQUIRED(mutex());
201
 
 
202
 
  // Puts all the passed in blocks onto this sector's freelist.
203
 
  // Does not read successors for passed in blocks, but does set them
204
 
  // for freelist membership.
205
 
  void ReturnBlocksToFreeList(const BlockVector& blocks)
206
 
      EXCLUSIVE_LOCKS_REQUIRED(mutex());
207
 
 
208
 
  // Cache directory ops.
209
 
  // ------------------------------------------------------------
210
 
 
211
 
  // Returns the given # entry.
212
 
  CacheEntry* EntryAt(EntryNum slot) {
213
 
    return reinterpret_cast<CacheEntry*>(directory_base_) + slot;
214
 
  }
215
 
 
216
 
  // Inserts the given entry into the LRU, at front.
217
 
  // Precondition: must not be in LRU.
218
 
  void InsertEntryIntoLRU(EntryNum entry_num);
219
 
 
220
 
  // Removes from the LRU. Safe to call if not in the LRU already.
221
 
  void UnlinkEntryFromLRU(EntryNum entry_num);
222
 
 
223
 
  EntryNum OldestEntryNum() {
224
 
    return sector_header_->lru_list_rear;
225
 
  }
226
 
 
227
 
  // Block ops.
228
 
  // ------------------------------------------------------------
229
 
 
230
 
  char* BlockBytes(BlockNum block_num) {
231
 
    return blocks_base_ + kBlockSize * block_num;
232
 
  }
233
 
 
234
 
  // Ops for lists of blocks corresponding to each directory entry,
235
 
  // and related size computations
236
 
  // ------------------------------------------------------------
237
 
 
238
 
  // Number of blocks of data needed for size blocks.
239
 
  static size_t DataBlocksForSize(size_t size) {
240
 
    return NeededPieces(size, kBlockSize);
241
 
  }
242
 
 
243
 
  // The # of bytes stored in block 'b' out of 'total' blocks for file of size
244
 
  // 'total_bytes'.
245
 
  // Precondition: 'total' is appropriate for 'total_bytes'.
246
 
  static size_t BytesInPortion(size_t total_bytes, size_t b, size_t total);
247
 
 
248
 
  // Appends the list of blocks used by the entry to 'blocks'.
249
 
  // Returns the number of items appended.
250
 
  int BlockListForEntry(CacheEntry* entry, BlockVector* out_blocks)
251
 
      EXCLUSIVE_LOCKS_REQUIRED(mutex());
252
 
 
253
 
  // Statistics stuff
254
 
  // ------------------------------------------------------------
255
 
 
256
 
  SectorStats* sector_stats() { return &sector_header_->stats; }
257
 
 
258
 
  // Prints out all statistics in the header (some of which are maintained
259
 
  // by the higher-level)
260
 
  void DumpStats(MessageHandler* handler);
261
 
 
262
 
 private:
263
 
  // Helper for doing sizing/memory layout computations.
264
 
  struct MemLayout;
265
 
 
266
 
  // How many piece_size pieces suffice to fit total
267
 
  static size_t NeededPieces(size_t total, size_t piece_size) {
268
 
    return (total + piece_size - 1) / piece_size;
269
 
  }
270
 
 
271
 
  // Configured geometry
272
 
  size_t cache_entries_;
273
 
  size_t data_blocks_;
274
 
 
275
 
  // Pointers to where various things are, and our sizes
276
 
  AbstractSharedMemSegment* segment_;
277
 
  scoped_ptr<AbstractMutex> mutex_;
278
 
  SectorHeader* sector_header_;
279
 
  BlockNum* block_successors_ PT_GUARDED_BY(mutex());
280
 
  char* directory_base_;
281
 
  char* blocks_base_;
282
 
  size_t sector_offset_;  // offset of the sector within the SHM segment
283
 
 
284
 
  DISALLOW_COPY_AND_ASSIGN(Sector);
285
 
};
286
 
 
287
 
}  // namespace SharedMemCacheData
288
 
 
289
 
}  // namespace net_instaweb
290
 
 
291
 
#endif  // PAGESPEED_KERNEL_SHAREDMEM_SHARED_MEM_CACHE_DATA_H_