stmem.cc
Go to the documentation of this file.
1 /*
2  * Copyright (C) 1996-2017 The Squid Software Foundation and contributors
3  *
4  * Squid software is distributed under GPLv2+ license and includes
5  * contributions from numerous individuals and organizations.
6  * Please see the COPYING and CONTRIBUTORS files for details.
7  */
8 
9 /* DEBUG: section 19 Store Memory Primitives */
10 
11 #include "squid.h"
12 #include "Generic.h"
13 #include "HttpReply.h"
14 #include "mem_node.h"
15 #include "MemObject.h"
16 #include "profiler/Profiler.h"
17 #include "stmem.h"
18 
19 /*
20  * NodeGet() is called to get the data buffer to pass to storeIOWrite().
21  * By setting the write_pending flag here we are assuming that there
22  * will be no other users of NodeGet(). The storeIOWrite() callback
23  * is memNodeWriteComplete(), which, for whatever reason, lives in
24  * mem_node.cc.
25  */
26 char *
28 {
29  assert(!aNode->write_pending);
30  aNode->write_pending = true;
31  return aNode->data;
32 }
33 
34 int64_t
36 {
37  const SplayNode<mem_node *> *theStart = nodes.start();
38 
39  if (theStart)
40  return theStart->data->nodeBuffer.offset;
41 
42  return 0;
43 }
44 
45 int64_t
47 {
48  int64_t result = 0;
49  const SplayNode<mem_node *> *theEnd = nodes.finish();
50 
51  if (theEnd)
52  result = theEnd->data->dataRange().end;
53 
54  assert (result == inmem_hi);
55 
56  return result;
57 }
58 
59 void
61 {
62  nodes.destroy();
63  inmem_hi = 0;
64  debugs(19, 9, HERE << this << " hi: " << inmem_hi);
65 }
66 
67 bool
69 {
70  if (aNode->write_pending) {
71  debugs(0, DBG_CRITICAL, "cannot unlink mem_node " << aNode << " while write_pending");
72  return false;
73  }
74 
75  debugs(19, 8, this << " removing " << aNode);
76  nodes.remove (aNode, NodeCompare);
77  delete aNode;
78  return true;
79 }
80 
81 int64_t
82 mem_hdr::freeDataUpto(int64_t target_offset)
83 {
84  debugs(19, 8, this << " up to " << target_offset);
85  /* keep the last one to avoid change to other part of code */
86  SplayNode<mem_node*> const * theStart;
87 
88  while ((theStart = nodes.start())) {
89  if (theStart == nodes.finish())
90  break;
91 
92  if (theStart->data->end() > target_offset )
93  break;
94 
95  if (!unlink(theStart->data))
96  break;
97  }
98 
99  assert (lowestOffset () <= target_offset);
100 
101  return lowestOffset ();
102 }
103 
104 int
105 mem_hdr::appendToNode(mem_node *aNode, const char *data, int maxLength)
106 {
107  size_t result = writeAvailable (aNode, aNode->nodeBuffer.offset + aNode->nodeBuffer.length,maxLength, data);
108  return result;
109 }
110 
111 size_t
112 mem_hdr::writeAvailable(mem_node *aNode, int64_t location, size_t amount, char const *source)
113 {
114  /* if we attempt to overwrite existing data or leave a gap within a node */
115  assert (location == aNode->nodeBuffer.offset + (int64_t)aNode->nodeBuffer.length);
116  /* And we are not at the end of the node */
117  assert (aNode->canAccept (location));
118 
119  /* these two can go I think */
120  assert (location - aNode->nodeBuffer.offset == (int64_t)aNode->nodeBuffer.length);
121  size_t copyLen = min(amount, aNode->space());
122 
123  memcpy(aNode->nodeBuffer.data + aNode->nodeBuffer.length, source, copyLen);
124 
125  debugs(19, 9, HERE << this << " hi: " << inmem_hi);
126  if (inmem_hi <= location)
127  inmem_hi = location + copyLen;
128 
129  /* Adjust the ptr and len according to what was deposited in the page */
130  aNode->nodeBuffer.length += copyLen;
131 
132  debugs(19, 9, HERE << this << " hi: " << inmem_hi);
133  debugs(19, 9, HERE << this << " hi: " << endOffset());
134  return copyLen;
135 }
136 
137 void
139 {
140  nodes.insert (aNode, NodeCompare);
141 }
142 
143 void
145 {
146  if (!nodes.size()) {
147  appendNode (new mem_node (0));
148  return;
149  }
150 
151  if (!nodes.finish()->data->space())
152  appendNode (new mem_node (endOffset()));
153 
154  assert (nodes.finish()->data->space());
155 }
156 
157 void
159 {
160  debugs(19, 6, "memInternalAppend: " << this << " len " << len);
161 
162  while (len > 0) {
163  makeAppendSpace();
164  int copied = appendToNode (nodes.finish()->data, data, len);
165  assert (copied);
166 
167  len -= copied;
168  data += copied;
169  }
170 }
171 
172 /* returns a mem_node that contains location..
173  * If no node contains the start, it returns NULL.
174  */
175 mem_node *
176 mem_hdr::getBlockContainingLocation (int64_t location) const
177 {
178  // Optimize: do not create a whole mem_node just to store location
179  mem_node target (location);
180  target.nodeBuffer.length = 1;
181  mem_node *const *result = nodes.find (&target, NodeCompare);
182 
183  if (result)
184  return *result;
185 
186  return NULL;
187 }
188 
189 size_t
190 mem_hdr::copyAvailable(mem_node *aNode, int64_t location, size_t amount, char *target) const
191 {
192  if (aNode->nodeBuffer.offset > location)
193  return 0;
194 
195  assert (aNode->nodeBuffer.offset <= location);
196 
197  assert (aNode->end() > location);
198 
199  size_t copyOffset = location - aNode->nodeBuffer.offset;
200 
201  size_t copyLen = min(amount, aNode->nodeBuffer.length - copyOffset);
202 
203  memcpy(target, aNode->nodeBuffer.data + copyOffset, copyLen);
204 
205  return copyLen;
206 }
207 
208 void
210 {
211  debugs (19, 0, "mem_hdr::debugDump: lowest offset: " << lowestOffset() << " highest offset + 1: " << endOffset() << ".");
212  std::ostringstream result;
213  PointerPrinter<mem_node *> foo(result, " - ");
214  getNodes().visit(foo);
215  debugs (19, 0, "mem_hdr::debugDump: Current available data is: " << result.str() << ".");
216 }
217 
218 /* FIXME: how do we deal with sparse results -
219  * where we have (say)
220  * 0-500 and 1000-1500, but are asked for
221  * 0-2000
222  * Partial answer:
223  * we supply 0-500 and stop.
224  */
225 ssize_t
226 mem_hdr::copy(StoreIOBuffer const &target) const
227 {
228 
229  assert(target.range().end > target.range().start);
230  debugs(19, 6, "memCopy: " << this << " " << target.range());
231 
232  /* we shouldn't ever ask for absent offsets */
233 
234  if (nodes.size() == 0) {
235  debugs(19, DBG_IMPORTANT, "mem_hdr::copy: No data to read");
236  debugDump();
237  assert (0);
238  return 0;
239  }
240 
241  /* RC: the next assert is nearly useless */
242  assert(target.length > 0);
243 
244  /* Seek our way into store */
246 
247  if (!p) {
248  debugs(19, DBG_IMPORTANT, "memCopy: could not find start of " << target.range() <<
249  " in memory.");
250  debugDump();
251  fatal_dump("Squid has attempted to read data from memory that is not present. This is an indication of of (pre-3.0) code that hasn't been updated to deal with sparse objects in memory. Squid should coredump.allowing to review the cause. Immediately preceding this message is a dump of the available data in the format [start,end). The [ means from the value, the ) means up to the value. I.e. [1,5) means that there are 4 bytes of data, at offsets 1,2,3,4.\n");
252  return 0;
253  }
254 
255  size_t bytes_to_go = target.length;
256  char *ptr_to_buf = target.data;
257  int64_t location = target.offset;
258 
259  /* Start copying begining with this block until
260  * we're satiated */
261 
262  while (p && bytes_to_go > 0) {
263  size_t bytes_to_copy = copyAvailable (p,
264  location, bytes_to_go, ptr_to_buf);
265 
266  /* hit a sparse patch */
267 
268  if (bytes_to_copy == 0)
269  return target.length - bytes_to_go;
270 
271  location += bytes_to_copy;
272 
273  ptr_to_buf += bytes_to_copy;
274 
275  bytes_to_go -= bytes_to_copy;
276 
277  p = getBlockContainingLocation(location);
278  }
279 
280  return target.length - bytes_to_go;
281 }
282 
283 bool
285 {
286  int64_t currentStart = range.start;
287 
288  while (mem_node *curr = getBlockContainingLocation(currentStart)) {
289  currentStart = curr->end();
290 
291  if (currentStart >= range.end)
292  return true;
293  }
294 
295  return !range.size(); // empty range is contigous
296 }
297 
298 bool
300 {
301  assert (candidate.offset >= 0);
302  mem_node target(candidate.offset);
303  target.nodeBuffer.length = candidate.length;
304  return nodes.find (&target, NodeCompare);
305 }
306 
307 mem_node *
308 mem_hdr::nodeToRecieve(int64_t offset)
309 {
310  /* case 1: Nothing in memory */
311 
312  if (!nodes.size()) {
313  appendNode (new mem_node(offset));
314  return nodes.start()->data;
315  }
316 
317  mem_node *candidate = NULL;
318  /* case 2: location fits within an extant node */
319 
320  if (offset > 0) {
321  mem_node search (offset - 1);
322  search.nodeBuffer.length = 1;
323  mem_node *const *leadup = nodes.find (&search, NodeCompare);
324 
325  if (leadup)
326  candidate = *leadup;
327  }
328 
329  if (candidate && candidate->canAccept(offset))
330  return candidate;
331 
332  /* candidate can't accept, so we need a new node */
333  candidate = new mem_node(offset);
334 
335  appendNode (candidate);
336 
337  /* simpler to write than a indented if */
338  return candidate;
339 }
340 
341 bool
342 mem_hdr::write (StoreIOBuffer const &writeBuffer)
343 {
344  PROF_start(mem_hdr_write);
345  debugs(19, 6, "mem_hdr::write: " << this << " " << writeBuffer.range() << " object end " << endOffset());
346 
347  if (unionNotEmpty(writeBuffer)) {
348  debugs(19, DBG_CRITICAL, "mem_hdr::write: writeBuffer: " << writeBuffer.range());
349  debugDump();
350  fatal_dump("Attempt to overwrite already in-memory data. Preceding this there should be a mem_hdr::write output that lists the attempted write, and the currently present data. Please get a 'backtrace full' from this error - using the generated core, and file a bug report with the squid developers including the last 10 lines of cache.log and the backtrace.\n");
351  PROF_stop(mem_hdr_write);
352  return false;
353  }
354 
355  assert (writeBuffer.offset >= 0);
356 
357  mem_node *target;
358  int64_t currentOffset = writeBuffer.offset;
359  char *currentSource = writeBuffer.data;
360  size_t len = writeBuffer.length;
361 
362  while (len && (target = nodeToRecieve(currentOffset))) {
363  size_t wrote = writeAvailable(target, currentOffset, len, currentSource);
364  assert (wrote);
365  len -= wrote;
366  currentOffset += wrote;
367  currentSource += wrote;
368  }
369 
370  PROF_stop(mem_hdr_write);
371  return true;
372 }
373 
374 mem_hdr::mem_hdr() : inmem_hi(0)
375 {
376  debugs(19, 9, HERE << this << " hi: " << inmem_hi);
377 }
378 
380 {
381  freeContent();
382 }
383 
384 /* splay of mem nodes:
385  * conditions:
386  * a = b if a.intersection(b).size > 0;
387  * a < b if a < b
388  */
389 int
390 mem_hdr::NodeCompare(mem_node * const &left, mem_node * const &right)
391 {
392  // possibly Range can help us at some point.
393 
394  if (left->dataRange().intersection(right->dataRange()).size() > 0)
395  return 0;
396 
397  return *left < *right ? -1 : 1;
398 }
399 
400 void
402 {
403  debugs(20, DBG_IMPORTANT, "mem_hdr: " << (void *)this << " nodes.start() " << nodes.start());
404  debugs(20, DBG_IMPORTANT, "mem_hdr: " << (void *)this << " nodes.finish() " << nodes.finish());
405 }
406 
407 size_t
409 {
410  return nodes.size();
411 }
412 
413 mem_node const *
415 {
416  const SplayNode<mem_node *> * result = nodes.start();
417 
418  if (result)
419  return result->data;
420 
421  return NULL;
422 }
423 
424 const Splay<mem_node *> &
426 {
427  return nodes;
428 }
429 
void insert(Value const &, SPLAYCMP *compare)
Definition: splay.h:300
bool unlink(mem_node *aNode)
Definition: stmem.cc:68
SplayNode< V > const * start() const
Definition: splay.h:327
int64_t endOffset() const
Definition: stmem.cc:46
int64_t freeDataUpto(int64_t)
Definition: stmem.cc:82
#define assert(EX)
Definition: assert.h:17
size_t size() const
Definition: stmem.cc:408
void internalAppend(const char *data, int len)
Definition: stmem.cc:158
void makeAppendSpace()
Definition: stmem.cc:144
char data[SM_PAGE_SIZE]
Definition: mem_node.h:37
bool unionNotEmpty(StoreIOBuffer const &)
Definition: stmem.cc:299
mem_node const * start() const
Definition: stmem.cc:414
void dump() const
Definition: stmem.cc:401
size_t copyAvailable(mem_node *aNode, int64_t location, size_t amount, char *target) const
Definition: stmem.cc:190
Definition: Range.h:18
Value const * find(FindValue const &, int(*compare)(FindValue const &a, Value const &b)) const
#define DBG_CRITICAL
Definition: Debug.h:44
char * p
Definition: membanger.c:43
size_t space() const
Definition: mem_node.cc:86
S size() const
Definition: Range.h:61
int64_t inmem_hi
Definition: stmem.h:59
int appendToNode(mem_node *aNode, const char *data, int maxLength)
Definition: stmem.cc:105
int64_t end() const
Definition: mem_node.cc:74
void fatal_dump(const char *message)
Definition: fatal.cc:89
int64_t lowestOffset() const
Definition: stmem.cc:35
SplayNode< V > const * finish() const
Definition: splay.h:337
bool write_pending
Definition: mem_node.h:38
void const char HLPCB void * data
Definition: stub_helper.cc:16
int64_t offset
Definition: StoreIOBuffer.h:55
bool write(StoreIOBuffer const &)
Definition: stmem.cc:342
#define debugs(SECTION, LEVEL, CONTENT)
Definition: Debug.h:123
#define DBG_IMPORTANT
Definition: Debug.h:45
void remove(Value const &, SPLAYCMP *compare)
Definition: splay.h:314
Splay< mem_node * > nodes
Definition: stmem.h:60
C start
Definition: Range.h:24
ssize_t copy(StoreIOBuffer const &) const
Definition: stmem.cc:226
void appendNode(mem_node *aNode)
Definition: stmem.cc:138
C end
Definition: Range.h:25
int unsigned int const char *desc STUB void int len
Definition: stub_fd.cc:20
mem_node * nodeToRecieve(int64_t offset)
Definition: stmem.cc:308
std::ostream & HERE(std::ostream &s)
Definition: Debug.h:147
void visit(Visitor &v) const
recursively visit all nodes, in left-to-right order
Definition: splay.h:276
StoreIOBuffer nodeBuffer
Definition: mem_node.h:35
Value data
Definition: splay.h:27
Range< int64_t > range() const
Definition: StoreIOBuffer.h:42
static Splay< mem_node * >::SPLAYCMP NodeCompare
Definition: stmem.h:47
mem_hdr()
Definition: stmem.cc:374
#define PROF_start(probename)
Definition: Profiler.h:62
void debugDump() const
Definition: stmem.cc:209
~mem_hdr()
Definition: stmem.cc:379
Range< int64_t > dataRange() const
Definition: mem_node.cc:80
const Splay< mem_node * > & getNodes() const
Definition: stmem.cc:425
void destroy(SPLAYFREE *=SplayNode< V >::DefaultFree)
Definition: splay.h:347
bool hasContigousContentRange(Range< int64_t > const &range) const
Definition: stmem.cc:284
#define PROF_stop(probename)
Definition: Profiler.h:63
char * NodeGet(mem_node *aNode)
Definition: stmem.cc:27
size_t size() const
Definition: splay.h:359
size_t writeAvailable(mem_node *aNode, int64_t location, size_t amount, char const *source)
Definition: stmem.cc:112
mem_node * getBlockContainingLocation(int64_t location) const
Definition: stmem.cc:176
void freeContent()
Definition: stmem.cc:60
#define NULL
Definition: types.h:166
A const & min(A const &lhs, A const &rhs)
bool canAccept(int64_t const &location) const
Definition: mem_node.cc:102

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors