src/stmem.cc

   1 /*
   2  * Copyright (C) 1996-2025 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     return lowestOffset ();
  99 }
 100
 101 size_t
 102 mem_hdr::writeAvailable(mem_node *aNode, int64_t location, size_t amount, char const *source)
 103 {
 104     /* if we attempt to overwrite existing data or leave a gap within a node */
 105     assert (location == aNode->nodeBuffer.offset + (int64_t)aNode->nodeBuffer.length);
 106     /* And we are not at the end of the node */
 107     assert (aNode->canAccept (location));
 108
 109     /* these two can go I think */
 110     assert (location - aNode->nodeBuffer.offset == (int64_t)aNode->nodeBuffer.length);
 111     size_t copyLen = min(amount, aNode->space());
 112
 113     memcpy(aNode->nodeBuffer.data + aNode->nodeBuffer.length, source, copyLen);
 114
 115     debugs(19, 9, this << " hi: " << inmem_hi);
 116     if (inmem_hi <= location)
 117         inmem_hi = location + copyLen;
 118
 119     /* Adjust the ptr and len according to what was deposited in the page */
 120     aNode->nodeBuffer.length += copyLen;
 121
 122     debugs(19, 9, this << " hi: " << inmem_hi);
 123     debugs(19, 9, this << " hi: " << endOffset());
 124     return copyLen;
 125 }
 126
 127 void
 128 mem_hdr::appendNode (mem_node *aNode)
 129 {
 130     nodes.insert (aNode, NodeCompare);
 131 }
 132
 133 /* returns a mem_node that contains location..
 134  * If no node contains the start, it returns NULL.
 135  */
 136 mem_node *
 137 mem_hdr::getBlockContainingLocation (int64_t location) const
 138 {
 139     // Optimize: do not create a whole mem_node just to store location
 140     mem_node target (location);
 141     target.nodeBuffer.length = 1;
 142     mem_node *const *result = nodes.find (&target, NodeCompare);
 143
 144     if (result)
 145         return *result;
 146
 147     return nullptr;
 148 }
 149
 150 size_t
 151 mem_hdr::copyAvailable(mem_node *aNode, int64_t location, size_t amount, char *target) const
 152 {
 153     if (aNode->nodeBuffer.offset > location)
 154         return 0;
 155
 156     assert (aNode->nodeBuffer.offset <= location);
 157
 158     assert (aNode->end() > location);
 159
 160     size_t copyOffset = location - aNode->nodeBuffer.offset;
 161
 162     size_t copyLen = min(amount, aNode->nodeBuffer.length - copyOffset);
 163
 164     memcpy(target, aNode->nodeBuffer.data + copyOffset, copyLen);
 165
 166     return copyLen;
 167 }
 168
 169 void
 170 mem_hdr::debugDump() const
 171 {
 172     debugs (19, 0, "mem_hdr::debugDump: lowest offset: " << lowestOffset() << " highest offset + 1: " << endOffset() << ".");
 173     std::ostringstream result;
 174     PointerPrinter<mem_node *> foo(result, " - ");
 175     getNodes().visit(foo);
 176     debugs (19, 0, "mem_hdr::debugDump: Current available data is: " << result.str() << ".");
 177 }
 178
 179 /* XXX: how do we deal with sparse results -
 180  * where we have (say)
 181  * 0-500 and 1000-1500, but are asked for
 182  * 0-2000
 183  * Partial answer:
 184  * we supply 0-500 and stop.
 185  */
 186 ssize_t
 187 mem_hdr::copy(StoreIOBuffer const &target) const
 188 {
 189
 190     assert(target.range().end > target.range().start);
 191     debugs(19, 6, "memCopy: " << this << " " << target.range());
 192
 193     /* we shouldn't ever ask for absent offsets */
 194
 195     if (nodes.size() == 0) {
 196         debugs(19, DBG_IMPORTANT, "mem_hdr::copy: No data to read");
 197         debugDump();
 198         assert (0);
 199         return 0;
 200     }
 201
 202     /* RC: the next assert is nearly useless */
 203     assert(target.length > 0);
 204
 205     /* Seek our way into store */
 206     mem_node *p = getBlockContainingLocation(target.offset);
 207
 208     if (!p) {
 209         debugs(19, DBG_IMPORTANT, "ERROR: memCopy: could not find start of " << target.range() <<
 210                " in memory.");
 211         debugDump();
 212         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");
 213         return 0;
 214     }
 215
 216     size_t bytes_to_go = target.length;
 217     char *ptr_to_buf = target.data;
 218     int64_t location = target.offset;
 219
 220     /* Start copying beginning with this block until
 221      * we're satiated */
 222
 223     while (p && bytes_to_go > 0) {
 224         size_t bytes_to_copy = copyAvailable (p,
 225                                               location, bytes_to_go, ptr_to_buf);
 226
 227         /* hit a sparse patch */
 228
 229         if (bytes_to_copy == 0)
 230             return target.length - bytes_to_go;
 231
 232         location += bytes_to_copy;
 233
 234         ptr_to_buf += bytes_to_copy;
 235
 236         bytes_to_go -= bytes_to_copy;
 237
 238         p = getBlockContainingLocation(location);
 239     }
 240
 241     return target.length - bytes_to_go;
 242 }
 243
 244 bool
 245 mem_hdr::hasContigousContentRange(Range<int64_t> const & range) const
 246 {
 247     int64_t currentStart = range.start;
 248
 249     while (mem_node *curr = getBlockContainingLocation(currentStart)) {
 250         currentStart = curr->end();
 251
 252         if (currentStart >= range.end)
 253             return true;
 254     }
 255
 256     return !range.size(); // empty range is contiguous
 257 }
 258
 259 bool
 260 mem_hdr::unionNotEmpty(StoreIOBuffer const &candidate)
 261 {
 262     assert (candidate.offset >= 0);
 263     mem_node target(candidate.offset);
 264     target.nodeBuffer.length = candidate.length;
 265     return nodes.find (&target, NodeCompare);
 266 }
 267
 268 mem_node *
 269 mem_hdr::nodeToRecieve(int64_t offset)
 270 {
 271     /* case 1: Nothing in memory */
 272
 273     if (!nodes.size()) {
 274         appendNode (new mem_node(offset));
 275         return nodes.start()->data;
 276     }
 277
 278     mem_node *candidate = nullptr;
 279     /* case 2: location fits within an extant node */
 280
 281     if (offset > 0) {
 282         mem_node search (offset - 1);
 283         search.nodeBuffer.length = 1;
 284         mem_node *const *leadup =  nodes.find (&search, NodeCompare);
 285
 286         if (leadup)
 287             candidate = *leadup;
 288     }
 289
 290     if (candidate && candidate->canAccept(offset))
 291         return candidate;
 292
 293     /* candidate can't accept, so we need a new node */
 294     candidate = new mem_node(offset);
 295
 296     appendNode (candidate);
 297
 298     /* simpler to write than a indented if */
 299     return candidate;
 300 }
 301
 302 bool
 303 mem_hdr::write (StoreIOBuffer const &writeBuffer)
 304 {
 305     debugs(19, 6, "mem_hdr::write: " << this << " " << writeBuffer.range() << " object end " << endOffset());
 306
 307     if (unionNotEmpty(writeBuffer)) {
 308         debugs(19, DBG_CRITICAL, "mem_hdr::write: writeBuffer: " << writeBuffer.range());
 309         debugDump();
 310         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");
 311         return false;
 312     }
 313
 314     assert (writeBuffer.offset >= 0);
 315
 316     mem_node *target;
 317     int64_t currentOffset = writeBuffer.offset;
 318     char *currentSource = writeBuffer.data;
 319     size_t len = writeBuffer.length;
 320
 321     while (len && (target = nodeToRecieve(currentOffset))) {
 322         size_t wrote = writeAvailable(target, currentOffset, len, currentSource);
 323         assert (wrote);
 324         len -= wrote;
 325         currentOffset += wrote;
 326         currentSource += wrote;
 327     }
 328
 329     return true;
 330 }
 331
 332 mem_hdr::mem_hdr() : inmem_hi(0)
 333 {
 334     debugs(19, 9, this << " hi: " << inmem_hi);
 335 }
 336
 337 mem_hdr::~mem_hdr()
 338 {
 339     freeContent();
 340 }
 341
 342 /* splay of mem nodes:
 343  * conditions:
 344  * a = b if a.intersection(b).size > 0;
 345  * a < b if a < b
 346  */
 347 int
 348 mem_hdr::NodeCompare(mem_node * const &left, mem_node * const &right)
 349 {
 350     // possibly Range can help us at some point.
 351
 352     if (left->dataRange().intersection(right->dataRange()).size() > 0)
 353         return 0;
 354
 355     return *left < *right ? -1 : 1;
 356 }
 357
 358 void
 359 mem_hdr::dump() const
 360 {
 361     debugs(20, DBG_IMPORTANT, "mem_hdr: " << (void *)this << " nodes.start() " << nodes.start());
 362     debugs(20, DBG_IMPORTANT, "mem_hdr: " << (void *)this << " nodes.finish() " << nodes.finish());
 363 }
 364
 365 size_t
 366 mem_hdr::size() const
 367 {
 368     return nodes.size();
 369 }
 370
 371 const Splay<mem_node *> &
 372 mem_hdr::getNodes() const
 373 {
 374     return nodes;
 375 }
 376