src/stmem.cc

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