]>
git.ipfire.org Git - thirdparty/squid.git/blob - src/stmem.cc
3 * DEBUG: section 19 Store Memory Primitives
4 * AUTHOR: Harvest Derived
6 * SQUID Web Proxy Cache http://www.squid-cache.org/
7 * ----------------------------------------------------------
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.
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.
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.
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.
32 * Copyright (c) 2003, Robert Collins <robertc@squid-cache.org>
38 #include "MemObject.h"
39 #include "profiler/Profiler.h"
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
50 mem_hdr :: NodeGet ( mem_node
* aNode
)
52 assert (! aNode
-> write_pending
);
53 aNode
-> write_pending
= true ;
58 mem_hdr :: lowestOffset () const
60 const SplayNode
< mem_node
*> * theStart
= nodes
. start ();
63 return theStart
-> data
-> nodeBuffer
. offset
;
69 mem_hdr :: endOffset () const
72 const SplayNode
< mem_node
*> * theEnd
= nodes
. finish ();
75 result
= theEnd
-> data
-> dataRange (). end
;
77 assert ( result
== inmem_hi
);
83 mem_hdr :: freeContent ()
85 nodes
. destroy ( SplayNode
< mem_node
*>:: DefaultFree
);
87 debugs ( 19 , 9 , HERE
<< this << " hi: " << inmem_hi
);
91 mem_hdr :: unlink ( mem_node
* aNode
)
93 if ( aNode
-> write_pending
) {
94 debugs ( 0 , DBG_CRITICAL
, "cannot unlink mem_node " << aNode
<< " while write_pending" );
98 nodes
. remove ( aNode
, NodeCompare
);
104 mem_hdr :: freeDataUpto ( int64_t target_offset
)
106 /* keep the last one to avoid change to other part of code */
107 SplayNode
< mem_node
*> const * theStart
;
109 while (( theStart
= nodes
. start ())) {
110 if ( theStart
== nodes
. finish ())
113 if ( theStart
-> data
-> end () > target_offset
)
116 if (! unlink ( theStart
-> data
))
120 assert ( lowestOffset () <= target_offset
);
122 return lowestOffset ();
126 mem_hdr :: appendToNode ( mem_node
* aNode
, const char * data
, int maxLength
)
128 size_t result
= writeAvailable ( aNode
, aNode
-> nodeBuffer
. offset
+ aNode
-> nodeBuffer
. length
, maxLength
, data
);
133 mem_hdr :: writeAvailable ( mem_node
* aNode
, int64_t location
, size_t amount
, char const * source
)
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
));
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 ());
144 memcpy ( aNode
-> nodeBuffer
. data
+ aNode
-> nodeBuffer
. length
, source
, copyLen
);
146 debugs ( 19 , 9 , HERE
<< this << " hi: " << inmem_hi
);
147 if ( inmem_hi
<= location
)
148 inmem_hi
= location
+ copyLen
;
150 /* Adjust the ptr and len according to what was deposited in the page */
151 aNode
-> nodeBuffer
. length
+= copyLen
;
153 debugs ( 19 , 9 , HERE
<< this << " hi: " << inmem_hi
);
154 debugs ( 19 , 9 , HERE
<< this << " hi: " << endOffset ());
159 mem_hdr :: appendNode ( mem_node
* aNode
)
161 nodes
. insert ( aNode
, NodeCompare
);
165 mem_hdr :: makeAppendSpace ()
168 appendNode ( new mem_node ( 0 ));
172 if (! nodes
. finish ()-> data
-> space ())
173 appendNode ( new mem_node ( endOffset ()));
175 assert ( nodes
. finish ()-> data
-> space ());
179 mem_hdr :: internalAppend ( const char * data
, int len
)
181 debugs ( 19 , 6 , "memInternalAppend: " << this << " len " << len
);
185 int copied
= appendToNode ( nodes
. finish ()-> data
, data
, len
);
193 /* returns a mem_node that contains location..
194 * If no node contains the start, it returns NULL.
197 mem_hdr :: getBlockContainingLocation ( int64_t location
) const
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
);
211 mem_hdr :: copyAvailable ( mem_node
* aNode
, int64_t location
, size_t amount
, char * target
) const
213 if ( aNode
-> nodeBuffer
. offset
> location
)
216 assert ( aNode
-> nodeBuffer
. offset
<= location
);
218 assert ( aNode
-> end () > location
);
220 size_t copyOffset
= location
- aNode
-> nodeBuffer
. offset
;
222 size_t copyLen
= min ( amount
, aNode
-> nodeBuffer
. length
- copyOffset
);
224 memcpy ( target
, aNode
-> nodeBuffer
. data
+ copyOffset
, copyLen
);
230 mem_hdr :: debugDump () const
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 () << "." );
239 /* FIXME: how do we deal with sparse results -
240 * where we have (say)
241 * 0-500 and 1000-1500, but are asked for
244 * we supply 0-500 and stop.
247 mem_hdr :: copy ( StoreIOBuffer
const & target
) const
250 assert ( target
. range (). end
> target
. range (). start
);
251 debugs ( 19 , 6 , "memCopy: " << this << " " << target
. range ());
253 /* we shouldn't ever ask for absent offsets */
255 if ( nodes
. size () == 0 ) {
256 debugs ( 19 , DBG_IMPORTANT
, "mem_hdr::copy: No data to read" );
262 /* RC: the next assert is nearly useless */
263 assert ( target
. length
> 0 );
265 /* Seek our way into store */
266 mem_node
* p
= getBlockContainingLocation ( target
. offset
);
269 debugs ( 19 , DBG_IMPORTANT
, "memCopy: could not find start of " << target
. range () <<
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 " );
276 size_t bytes_to_go
= target
. length
;
277 char * ptr_to_buf
= target
. data
;
278 int64_t location
= target
. offset
;
280 /* Start copying begining with this block until
283 while ( p
&& bytes_to_go
> 0 ) {
284 size_t bytes_to_copy
= copyAvailable ( p
,
285 location
, bytes_to_go
, ptr_to_buf
);
287 /* hit a sparse patch */
289 if ( bytes_to_copy
== 0 )
290 return target
. length
- bytes_to_go
;
292 location
+= bytes_to_copy
;
294 ptr_to_buf
+= bytes_to_copy
;
296 bytes_to_go
-= bytes_to_copy
;
298 p
= getBlockContainingLocation ( location
);
301 return target
. length
- bytes_to_go
;
305 mem_hdr :: hasContigousContentRange ( Range
< int64_t > const & range
) const
307 int64_t currentStart
= range
. start
;
309 while ( mem_node
* curr
= getBlockContainingLocation ( currentStart
)) {
310 currentStart
= curr
-> end ();
312 if ( currentStart
>= range
. end
)
316 return ! range
. size (); // empty range is contigous
320 mem_hdr :: unionNotEmpty ( StoreIOBuffer
const & candidate
)
322 assert ( candidate
. offset
>= 0 );
323 mem_node
target ( candidate
. offset
);
324 target
. nodeBuffer
. length
= candidate
. length
;
325 return nodes
. find (& target
, NodeCompare
);
329 mem_hdr :: nodeToRecieve ( int64_t offset
)
331 /* case 1: Nothing in memory */
334 appendNode ( new mem_node ( offset
));
335 return nodes
. start ()-> data
;
338 mem_node
* candidate
= NULL
;
339 /* case 2: location fits within an extant node */
342 mem_node
search ( offset
- 1 );
343 search
. nodeBuffer
. length
= 1 ;
344 mem_node
* const * leadup
= nodes
. find (& search
, NodeCompare
);
350 if ( candidate
&& candidate
-> canAccept ( offset
))
353 /* candidate can't accept, so we need a new node */
354 candidate
= new mem_node ( offset
);
356 appendNode ( candidate
);
358 /* simpler to write than a indented if */
363 mem_hdr :: write ( StoreIOBuffer
const & writeBuffer
)
365 PROF_start ( mem_hdr_write
);
366 debugs ( 19 , 6 , "mem_hdr::write: " << this << " " << writeBuffer
. range () << " object end " << endOffset ());
368 if ( unionNotEmpty ( writeBuffer
)) {
369 debugs ( 19 , DBG_CRITICAL
, "mem_hdr::write: writeBuffer: " << writeBuffer
. range ());
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
);
376 assert ( writeBuffer
. offset
>= 0 );
379 int64_t currentOffset
= writeBuffer
. offset
;
380 char * currentSource
= writeBuffer
. data
;
381 size_t len
= writeBuffer
. length
;
383 while ( len
&& ( target
= nodeToRecieve ( currentOffset
))) {
384 size_t wrote
= writeAvailable ( target
, currentOffset
, len
, currentSource
);
387 currentOffset
+= wrote
;
388 currentSource
+= wrote
;
391 PROF_stop ( mem_hdr_write
);
395 mem_hdr :: mem_hdr () : inmem_hi ( 0 )
397 debugs ( 19 , 9 , HERE
<< this << " hi: " << inmem_hi
);
405 /* splay of mem nodes:
407 * a = b if a.intersection(b).size > 0;
411 mem_hdr :: NodeCompare ( mem_node
* const & left
, mem_node
* const & right
)
413 // possibly Range can help us at some point.
415 if ( left
-> dataRange (). intersection ( right
-> dataRange ()). size () > 0 )
418 return * left
< * right
? - 1 : 1 ;
422 mem_hdr :: dump () const
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 ());
429 mem_hdr :: size () const
435 mem_hdr :: start () const
437 const SplayNode
< mem_node
*> * result
= nodes
. start ();
445 const Splay
< mem_node
*> &
446 mem_hdr :: getNodes () const