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

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors