src/stmem.cc

   1 /*
   2  * Copyright (C) 1996-2023 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 *
  26 mem_hdr::NodeGet(mem_node * aNode)
  27 {
  28     assert(!aNode->write_pending);
  29     aNode->write_pending = true;
  30     return aNode->data;
  31 }
  32
  33 int64_t
  34 mem_hdr::lowestOffset () const
  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
  45 mem_hdr::endOffset () const
  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
  59 mem_hdr::freeContent()
  60 {
  61     nodes.destroy();
  62     inmem_hi = 0;
  63     debugs(19, 9, this << " hi: " << inmem_hi);
  64 }
  65
  66 bool
  67 mem_hdr::unlink(mem_node *aNode)
  68 {
  69     if (aNode->write_pending) {
  70         debugs(0, DBG_CRITICAL, "ERROR: 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, 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, this << " hi: " << inmem_hi);
 132     debugs(19, 9, this << " hi: " << endOffset());
 133     return copyLen;
 134 }
 135
 136 void
 137 mem_hdr::appendNode (mem_node *aNode)
 138 {
 139     nodes.insert (aNode, NodeCompare);
 140 }
 141
 142 void
 143 mem_hdr::makeAppendSpace()
 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 nullptr;
 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
 208 mem_hdr::debugDump() const
 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 */
 244     mem_node *p = getBlockContainingLocation(target.offset);
 245
 246     if (!p) {
 247         debugs(19, DBG_IMPORTANT, "ERROR: 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
 283 mem_hdr::hasContigousContentRange(Range<int64_t> const & range) const
 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
 298 mem_hdr::unionNotEmpty(StoreIOBuffer const &candidate)
 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 = nullptr;
 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, this << " hi: " << inmem_hi);
 373 }
 374
 375 mem_hdr::~mem_hdr()
 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
 397 mem_hdr::dump() const
 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
 404 mem_hdr::size() const
 405 {
 406     return nodes.size();
 407 }
 408
 409 mem_node const *
 410 mem_hdr::start() const
 411 {
 412     const SplayNode<mem_node *> * result = nodes.start();
 413
 414     if (result)
 415         return result->data;
 416
 417     return nullptr;
 418 }
 419
 420 const Splay<mem_node *> &
 421 mem_hdr::getNodes() const
 422 {
 423     return nodes;
 424 }
 425