src/stmem.cc

   1 /*
   2  * Copyright (C) 1996-2020 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 *
  27 mem_hdr::NodeGet(mem_node * aNode)
  28 {
  29     assert(!aNode->write_pending);
  30     aNode->write_pending = true;
  31     return aNode->data;
  32 }
  33
  34 int64_t
  35 mem_hdr::lowestOffset () const
  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
  46 mem_hdr::endOffset () const
  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
  60 mem_hdr::freeContent()
  61 {
  62     nodes.destroy();
  63     inmem_hi = 0;
  64     debugs(19, 9, HERE << this << " hi: " << inmem_hi);
  65 }
  66
  67 bool
  68 mem_hdr::unlink(mem_node *aNode)
  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
 138 mem_hdr::appendNode (mem_node *aNode)
 139 {
 140     nodes.insert (aNode, NodeCompare);
 141 }
 142
 143 void
 144 mem_hdr::makeAppendSpace()
 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
 158 mem_hdr::internalAppend(const char *data, int len)
 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
 209 mem_hdr::debugDump() const
 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 /* XXX: 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 */
 245     mem_node *p = getBlockContainingLocation(target.offset);
 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 beginning 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
 284 mem_hdr::hasContigousContentRange(Range<int64_t> const & range) const
 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 contiguous
 296 }
 297
 298 bool
 299 mem_hdr::unionNotEmpty(StoreIOBuffer const &candidate)
 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
 379 mem_hdr::~mem_hdr()
 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
 401 mem_hdr::dump() const
 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
 408 mem_hdr::size() const
 409 {
 410     return nodes.size();
 411 }
 412
 413 mem_node const *
 414 mem_hdr::start() 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 *> &
 425 mem_hdr::getNodes() const
 426 {
 427     return nodes;
 428 }
 429