src/stmem.cc

   1
   2 /*
   3  * DEBUG: section 19    Store Memory Primitives
   4  * AUTHOR: Harvest Derived
   5  *
   6  * SQUID Web Proxy Cache          http://www.squid-cache.org/
   7  * ----------------------------------------------------------
   8  *
   9  *  Squid is the result of efforts by numerous individuals from
  10  *  the Internet community; see the CONTRIBUTORS file for full
  11  *  details.   Many organizations have provided support for Squid's
  12  *  development; see the SPONSORS file for full details.  Squid is
  13  *  Copyrighted (C) 2001 by the Regents of the University of
  14  *  California; see the COPYRIGHT file for full details.  Squid
  15  *  incorporates software developed and/or copyrighted by other
  16  *  sources; see the CREDITS file for full details.
  17  *
  18  *  This program is free software; you can redistribute it and/or modify
  19  *  it under the terms of the GNU General Public License as published by
  20  *  the Free Software Foundation; either version 2 of the License, or
  21  *  (at your option) any later version.
  22  *
  23  *  This program is distributed in the hope that it will be useful,
  24  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  25  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  26  *  GNU General Public License for more details.
  27  *
  28  *  You should have received a copy of the GNU General Public License
  29  *  along with this program; if not, write to the Free Software
  30  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
  31  *
  32  * Copyright (c) 2003, Robert Collins <robertc@squid-cache.org>
  33  */
  34
  35 #include "squid.h"
  36 #include "Generic.h"
  37 #include "mem_node.h"
  38 #include "MemObject.h"
  39 #include "profiler/Profiler.h"
  40 #include "stmem.h"
  41
  42 /*
  43  * NodeGet() is called to get the data buffer to pass to storeIOWrite().
  44  * By setting the write_pending flag here we are assuming that there
  45  * will be no other users of NodeGet().  The storeIOWrite() callback
  46  * is memNodeWriteComplete(), which, for whatever reason, lives in
  47  * mem_node.cc.
  48  */
  49 char *
  50 mem_hdr::NodeGet(mem_node * aNode)
  51 {
  52     assert(!aNode->write_pending);
  53     aNode->write_pending = 1;
  54     return aNode->data;
  55 }
  56
  57 int64_t
  58 mem_hdr::lowestOffset () const
  59 {
  60     const SplayNode<mem_node *> *theStart = nodes.start();
  61
  62     if (theStart)
  63         return theStart->data->nodeBuffer.offset;
  64
  65     return 0;
  66 }
  67
  68 int64_t
  69 mem_hdr::endOffset () const
  70 {
  71     int64_t result = 0;
  72     const SplayNode<mem_node *> *theEnd = nodes.finish();
  73
  74     if (theEnd)
  75         result = theEnd->data->dataRange().end;
  76
  77     assert (result == inmem_hi);
  78
  79     return result;
  80 }
  81
  82 void
  83 mem_hdr::freeContent()
  84 {
  85     nodes.destroy(SplayNode<mem_node *>::DefaultFree);
  86     inmem_hi = 0;
  87     debugs(19, 9, HERE << this << " hi: " << inmem_hi);
  88 }
  89
  90 bool
  91 mem_hdr::unlink(mem_node *aNode)
  92 {
  93     if (aNode->write_pending) {
  94         debugs(0, DBG_CRITICAL, "cannot unlink mem_node " << aNode << " while write_pending");
  95         return false;
  96     }
  97
  98     nodes.remove (aNode, NodeCompare);
  99     delete aNode;
 100     return true;
 101 }
 102
 103 int64_t
 104 mem_hdr::freeDataUpto(int64_t target_offset)
 105 {
 106     /* keep the last one to avoid change to other part of code */
 107
 108     SplayNode<mem_node*> const * theStart = nodes.start();
 109
 110     while ((theStart = nodes.start())) {
 111         if (theStart == nodes.finish())
 112             break;
 113
 114         if (theStart->data->end() > target_offset )
 115             break;
 116
 117         if (!unlink(theStart->data))
 118             break;
 119     }
 120
 121     assert (lowestOffset () <= target_offset);
 122
 123     return lowestOffset ();
 124 }
 125
 126 int
 127 mem_hdr::appendToNode(mem_node *aNode, const char *data, int maxLength)
 128 {
 129     size_t result = writeAvailable (aNode, aNode->nodeBuffer.offset + aNode->nodeBuffer.length ,maxLength, data);
 130     return result;
 131 }
 132
 133 size_t
 134 mem_hdr::writeAvailable(mem_node *aNode, int64_t location, size_t amount, char const *source)
 135 {
 136     /* if we attempt to overwrite existing data or leave a gap within a node */
 137     assert (location == aNode->nodeBuffer.offset + (int64_t)aNode->nodeBuffer.length);
 138     /* And we are not at the end of the node */
 139     assert (aNode->canAccept (location));
 140
 141     /* these two can go I think */
 142     assert (location - aNode->nodeBuffer.offset == (int64_t)aNode->nodeBuffer.length);
 143     size_t copyLen = min(amount, aNode->space());
 144
 145     memcpy(aNode->nodeBuffer.data + aNode->nodeBuffer.length, source, copyLen);
 146
 147     debugs(19, 9, HERE << this << " hi: " << inmem_hi);
 148     if (inmem_hi <= location)
 149         inmem_hi = location + copyLen;
 150
 151     /* Adjust the ptr and len according to what was deposited in the page */
 152     aNode->nodeBuffer.length += copyLen;
 153
 154     debugs(19, 9, HERE << this << " hi: " << inmem_hi);
 155     debugs(19, 9, HERE << this << " hi: " << endOffset());
 156     return copyLen;
 157 }
 158
 159 void
 160 mem_hdr::appendNode (mem_node *aNode)
 161 {
 162     nodes.insert (aNode, NodeCompare);
 163 }
 164
 165 void
 166 mem_hdr::makeAppendSpace()
 167 {
 168     if (!nodes.size()) {
 169         appendNode (new mem_node (0));
 170         return;
 171     }
 172
 173     if (!nodes.finish()->data->space())
 174         appendNode (new mem_node (endOffset()));
 175
 176     assert (nodes.finish()->data->space());
 177 }
 178
 179 void
 180 mem_hdr::internalAppend(const char *data, int len)
 181 {
 182     debugs(19, 6, "memInternalAppend: " << this << " len " << len);
 183
 184     while (len > 0) {
 185         makeAppendSpace();
 186         int copied = appendToNode (nodes.finish()->data, data, len);
 187         assert (copied);
 188
 189         len -= copied;
 190         data += copied;
 191     }
 192 }
 193
 194 /* returns a mem_node that contains location..
 195  * If no node contains the start, it returns NULL.
 196  */
 197 mem_node *
 198 mem_hdr::getBlockContainingLocation (int64_t location) const
 199 {
 200     // Optimize: do not create a whole mem_node just to store location
 201     mem_node target (location);
 202     target.nodeBuffer.length = 1;
 203     mem_node *const *result = nodes.find (&target, NodeCompare);
 204
 205     if (result)
 206         return *result;
 207
 208     return NULL;
 209 }
 210
 211 size_t
 212 mem_hdr::copyAvailable(mem_node *aNode, int64_t location, size_t amount, char *target) const
 213 {
 214     if (aNode->nodeBuffer.offset > location)
 215         return 0;
 216
 217     assert (aNode->nodeBuffer.offset <= location);
 218
 219     assert (aNode->end() > location);
 220
 221     size_t copyOffset = location - aNode->nodeBuffer.offset;
 222
 223     size_t copyLen = min(amount, aNode->nodeBuffer.length - copyOffset);
 224
 225     memcpy(target, aNode->nodeBuffer.data + copyOffset, copyLen);
 226
 227     return copyLen;
 228 }
 229
 230 void
 231 mem_hdr::debugDump() const
 232 {
 233     debugs (19, 0, "mem_hdr::debugDump: lowest offset: " << lowestOffset() << " highest offset + 1: " << endOffset() << ".");
 234     std::ostringstream result;
 235     PointerPrinter<mem_node *> foo(result, " - ");
 236     for_each (getNodes().begin(), getNodes().end(), foo);
 237     debugs (19, 0, "mem_hdr::debugDump: Current available data is: " << result.str() << ".");
 238 }
 239
 240 /* FIXME: how do we deal with sparse results -
 241  * where we have (say)
 242  * 0-500 and 1000-1500, but are asked for
 243  * 0-2000
 244  * Partial answer:
 245  * we supply 0-500 and stop.
 246  */
 247 ssize_t
 248 mem_hdr::copy(StoreIOBuffer const &target) const
 249 {
 250
 251     assert(target.range().end > target.range().start);
 252     debugs(19, 6, "memCopy: " << this << " " << target.range());
 253
 254     /* we shouldn't ever ask for absent offsets */
 255
 256     if (nodes.size() == 0) {
 257         debugs(19, DBG_IMPORTANT, "mem_hdr::copy: No data to read");
 258         debugDump();
 259         assert (0);
 260         return 0;
 261     }
 262
 263     /* RC: the next assert is nearly useless */
 264     assert(target.length > 0);
 265
 266     /* Seek our way into store */
 267     mem_node *p = getBlockContainingLocation(target.offset);
 268
 269     if (!p) {
 270         debugs(19, DBG_IMPORTANT, "memCopy: could not find start of " << target.range() <<
 271                " in memory.");
 272         debugDump();
 273         fatal("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 preceeding 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");
 274         return 0;
 275     }
 276
 277     size_t bytes_to_go = target.length;
 278     char *ptr_to_buf = target.data;
 279     int64_t location = target.offset;
 280
 281     /* Start copying begining with this block until
 282      * we're satiated */
 283
 284     while (p && bytes_to_go > 0) {
 285         size_t bytes_to_copy = copyAvailable (p,
 286                                               location, bytes_to_go, ptr_to_buf);
 287
 288         /* hit a sparse patch */
 289
 290         if (bytes_to_copy == 0)
 291             return target.length - bytes_to_go;
 292
 293         location += bytes_to_copy;
 294
 295         ptr_to_buf += bytes_to_copy;
 296
 297         bytes_to_go -= bytes_to_copy;
 298
 299         p = getBlockContainingLocation(location);
 300     }
 301
 302     return target.length - bytes_to_go;
 303 }
 304
 305 bool
 306 mem_hdr::hasContigousContentRange(Range<int64_t> const & range) const
 307 {
 308     int64_t currentStart = range.start;
 309
 310     while (mem_node *curr = getBlockContainingLocation(currentStart)) {
 311         currentStart = curr->end();
 312
 313         if (currentStart >= range.end)
 314             return true;
 315     }
 316
 317     return false;
 318 }
 319
 320 bool
 321 mem_hdr::unionNotEmpty(StoreIOBuffer const &candidate)
 322 {
 323     assert (candidate.offset >= 0);
 324     mem_node target(candidate.offset);
 325     target.nodeBuffer.length = candidate.length;
 326     return nodes.find (&target, NodeCompare);
 327 }
 328
 329 mem_node *
 330 mem_hdr::nodeToRecieve(int64_t offset)
 331 {
 332     /* case 1: Nothing in memory */
 333
 334     if (!nodes.size()) {
 335         appendNode (new mem_node(offset));
 336         return nodes.start()->data;
 337     }
 338
 339     mem_node *candidate = NULL;
 340     /* case 2: location fits within an extant node */
 341
 342     if (offset > 0) {
 343         mem_node search (offset - 1);
 344         search.nodeBuffer.length = 1;
 345         mem_node *const *leadup =  nodes.find (&search, NodeCompare);
 346
 347         if (leadup)
 348             candidate = *leadup;
 349     }
 350
 351     if (candidate && candidate->canAccept(offset))
 352         return candidate;
 353
 354     /* candidate can't accept, so we need a new node */
 355     candidate = new mem_node(offset);
 356
 357     appendNode (candidate);
 358
 359     /* simpler to write than a indented if */
 360     return candidate;
 361 }
 362
 363 bool
 364 mem_hdr::write (StoreIOBuffer const &writeBuffer)
 365 {
 366     PROF_start(mem_hdr_write);
 367     debugs(19, 6, "mem_hdr::write: " << this << " " << writeBuffer.range() << " object end " << endOffset());
 368
 369     if (unionNotEmpty(writeBuffer)) {
 370         debugs(19, DBG_CRITICAL, "mem_hdr::write: writeBuffer: " << writeBuffer.range());
 371         debugDump();
 372         fatal("Attempt to overwrite already in-memory data. Preceeding 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");
 373         PROF_stop(mem_hdr_write);
 374         return false;
 375     }
 376
 377     assert (writeBuffer.offset >= 0);
 378
 379     mem_node *target;
 380     int64_t currentOffset = writeBuffer.offset;
 381     char *currentSource = writeBuffer.data;
 382     size_t len = writeBuffer.length;
 383
 384     while (len && (target = nodeToRecieve(currentOffset))) {
 385         size_t wrote = writeAvailable(target, currentOffset, len, currentSource);
 386         assert (wrote);
 387         len -= wrote;
 388         currentOffset += wrote;
 389         currentSource += wrote;
 390     }
 391
 392     PROF_stop(mem_hdr_write);
 393     return true;
 394 }
 395
 396 mem_hdr::mem_hdr() : inmem_hi(0)
 397 {
 398     debugs(19, 9, HERE << this << " hi: " << inmem_hi);
 399 }
 400
 401 mem_hdr::~mem_hdr()
 402 {
 403     freeContent();
 404 }
 405
 406 /* splay of mem nodes:
 407  * conditions:
 408  * a = b if a.intersection(b).size > 0;
 409  * a < b if a < b
 410  */
 411 int
 412 mem_hdr::NodeCompare(mem_node * const &left, mem_node * const &right)
 413 {
 414     // possibly Range can help us at some point.
 415
 416     if (left->dataRange().intersection(right->dataRange()).size() > 0)
 417         return 0;
 418
 419     return *left < *right ? -1 : 1;
 420 }
 421
 422 void
 423 mem_hdr::dump() const
 424 {
 425     debugs(20, DBG_IMPORTANT, "mem_hdr: " << (void *)this << " nodes.start() " << nodes.start());
 426     debugs(20, DBG_IMPORTANT, "mem_hdr: " << (void *)this << " nodes.finish() " << nodes.finish());
 427 }
 428
 429 size_t
 430 mem_hdr::size() const
 431 {
 432     return nodes.size();
 433 }
 434
 435 mem_node const *
 436 mem_hdr::start() const
 437 {
 438     const SplayNode<mem_node *> * result = nodes.start();
 439
 440     if (result)
 441         return result->data;
 442
 443     return NULL;
 444 }
 445
 446 const Splay<mem_node *> &
 447 mem_hdr::getNodes() const
 448 {
 449     return nodes;
 450 }