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