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