]>
Commit | Line | Data |
---|---|---|
df92bd2a | 1 | |
30a4f2a8 | 2 | /* |
e4a67a80 | 3 | * $Id: stmem.cc,v 1.81 2003/09/06 12:47:35 robertc Exp $ |
30a4f2a8 | 4 | * |
6f6f0853 | 5 | * DEBUG: section 19 Store Memory Primitives |
30a4f2a8 | 6 | * AUTHOR: Harvest Derived |
7 | * | |
2b6662ba | 8 | * SQUID Web Proxy Cache http://www.squid-cache.org/ |
e25c139f | 9 | * ---------------------------------------------------------- |
30a4f2a8 | 10 | * |
2b6662ba | 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. | |
30a4f2a8 | 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 | |
cbdec147 | 32 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA. |
e25c139f | 33 | * |
42a503bd | 34 | * Copyright (c) 2003, Robert Collins <robertc@squid-cache.org> |
019dd986 | 35 | */ |
ed43818f | 36 | |
44a47c6e | 37 | #include "squid.h" |
528b2c61 | 38 | #include "stmem.h" |
39 | #include "mem_node.h" | |
40 | #include "MemObject.h" | |
41 | ||
42 | int | |
43 | mem_hdr::lowestOffset () const | |
44 | { | |
42a503bd | 45 | const SplayNode<mem_node *> *theStart = nodes.start(); |
46 | ||
47 | if (theStart) | |
48 | return theStart->data->nodeBuffer.offset; | |
62e76326 | 49 | |
528b2c61 | 50 | return 0; |
51 | } | |
52 | ||
53 | off_t | |
54 | mem_hdr::endOffset () const | |
55 | { | |
56 | off_t result = 0; | |
42a503bd | 57 | const SplayNode<mem_node *> *theEnd = nodes.end(); |
62e76326 | 58 | |
42a503bd | 59 | if (theEnd) |
60 | result = theEnd->data->dataRange().end; | |
62e76326 | 61 | |
528b2c61 | 62 | assert (result == inmem_hi); |
62e76326 | 63 | |
528b2c61 | 64 | return result; |
65 | } | |
090089c4 | 66 | |
d89d1fb6 | 67 | void |
528b2c61 | 68 | mem_hdr::freeContent() |
69 | { | |
42a503bd | 70 | nodes.destroy(SplayNode<mem_node *>::DefaultFree); |
528b2c61 | 71 | inmem_hi = 0; |
72 | } | |
73 | ||
74 | void | |
42a503bd | 75 | mem_hdr::unlink(mem_node *aNode) |
528b2c61 | 76 | { |
42a503bd | 77 | nodes.remove (aNode, NodeCompare); |
00d77d6b | 78 | delete aNode; |
090089c4 | 79 | } |
80 | ||
d89d1fb6 | 81 | int |
528b2c61 | 82 | mem_hdr::freeDataUpto(int target_offset) |
83 | { | |
84 | /* keep the last one to avoid change to other part of code */ | |
62e76326 | 85 | |
42a503bd | 86 | SplayNode<mem_node*> const * theStart = nodes.start(); |
87 | ||
88 | while (theStart && theStart != nodes.end() && | |
89 | theStart->data->end() <= (size_t) target_offset ) { | |
90 | unlink(theStart->data); | |
91 | theStart = nodes.start(); | |
92 | } | |
62e76326 | 93 | |
528b2c61 | 94 | assert (lowestOffset () <= target_offset); |
62e76326 | 95 | |
528b2c61 | 96 | return lowestOffset (); |
97 | } | |
98 | ||
62e76326 | 99 | int |
528b2c61 | 100 | mem_hdr::appendToNode(mem_node *aNode, const char *data, int maxLength) |
101 | { | |
102 | size_t result = writeAvailable (aNode, aNode->nodeBuffer.offset + aNode->nodeBuffer.length ,maxLength, data); | |
103 | return result; | |
104 | } | |
105 | ||
106 | size_t | |
107 | mem_hdr::writeAvailable(mem_node *aNode, size_t location, size_t amount, char const *source) | |
108 | { | |
109 | /* if we attempt to overwrite existing data or leave a gap within a node */ | |
110 | assert (location == aNode->nodeBuffer.offset + aNode->nodeBuffer.length); | |
111 | /* And we are not at the end of the node */ | |
112 | assert (aNode->canAccept (location)); | |
62e76326 | 113 | |
528b2c61 | 114 | /* these two can go I think */ |
e4a67a80 | 115 | assert (location - aNode->nodeBuffer.offset == aNode->nodeBuffer.length); |
528b2c61 | 116 | size_t copyLen = XMIN (amount, aNode->space()); |
117 | ||
118 | xmemcpy(aNode->nodeBuffer.data + aNode->nodeBuffer.length, source, copyLen); | |
119 | ||
120 | if (inmem_hi <= (off_t) location) | |
62e76326 | 121 | inmem_hi = location + copyLen; |
122 | ||
528b2c61 | 123 | /* Adjust the ptr and len according to what was deposited in the page */ |
124 | aNode->nodeBuffer.length += copyLen; | |
62e76326 | 125 | |
528b2c61 | 126 | mem_node::store_mem_size += copyLen; |
62e76326 | 127 | |
528b2c61 | 128 | return copyLen; |
129 | } | |
130 | ||
131 | void | |
132 | mem_hdr::appendNode (mem_node *aNode) | |
133 | { | |
42a503bd | 134 | nodes.insert (aNode, NodeCompare); |
090089c4 | 135 | } |
136 | ||
e6e5d90d | 137 | void |
528b2c61 | 138 | mem_hdr::makeAppendSpace() |
139 | { | |
42a503bd | 140 | if (!nodes.size()) { |
141 | appendNode (new mem_node (0)); | |
62e76326 | 142 | return; |
090089c4 | 143 | } |
62e76326 | 144 | |
42a503bd | 145 | if (!nodes.end()->data->space()) |
62e76326 | 146 | appendNode (new mem_node (endOffset())); |
147 | ||
42a503bd | 148 | assert (nodes.end()->data->space()); |
528b2c61 | 149 | } |
150 | ||
151 | void | |
152 | mem_hdr::internalAppend(const char *data, int len) | |
153 | { | |
154 | debug(19, 6) ("memInternalAppend: len %d\n", len); | |
62e76326 | 155 | |
090089c4 | 156 | while (len > 0) { |
62e76326 | 157 | makeAppendSpace(); |
42a503bd | 158 | int copied = appendToNode (nodes.end()->data, data, len); |
62e76326 | 159 | assert (copied); |
160 | ||
161 | len -= copied; | |
162 | data += copied; | |
090089c4 | 163 | } |
090089c4 | 164 | } |
165 | ||
528b2c61 | 166 | /* returns a mem_node that contains location.. |
167 | * If no node contains the start, it returns NULL. | |
168 | */ | |
169 | mem_node * | |
170 | mem_hdr::getBlockContainingLocation (size_t location) const | |
171 | { | |
42a503bd | 172 | mem_node target (location); |
173 | target.nodeBuffer.length = 1; | |
174 | mem_node *const *result = nodes.find (&target, NodeCompare); | |
62e76326 | 175 | |
42a503bd | 176 | if (result) |
177 | return *result; | |
62e76326 | 178 | |
42a503bd | 179 | return NULL; |
528b2c61 | 180 | } |
181 | ||
182 | size_t | |
183 | mem_hdr::copyAvailable(mem_node *aNode, size_t location, size_t amount, char *target) const | |
184 | { | |
185 | if (aNode->nodeBuffer.offset > (off_t) location) | |
62e76326 | 186 | return 0; |
187 | ||
528b2c61 | 188 | assert (aNode->nodeBuffer.offset <= (off_t) location); |
62e76326 | 189 | |
528b2c61 | 190 | assert (aNode->end() > location); |
62e76326 | 191 | |
528b2c61 | 192 | size_t copyOffset = location - aNode->nodeBuffer.offset; |
62e76326 | 193 | |
528b2c61 | 194 | size_t copyLen = XMIN (amount, aNode->nodeBuffer.length - copyOffset); |
195 | ||
196 | xmemcpy(target, aNode->nodeBuffer.data + copyOffset, copyLen); | |
62e76326 | 197 | |
528b2c61 | 198 | return copyLen; |
199 | } | |
200 | ||
62e76326 | 201 | /* FIXME: how do we deal with sparse results - |
528b2c61 | 202 | * where we have (say) |
203 | * 0-500 and 1000-1500, but are asked for | |
204 | * 0-2000 | |
205 | * Partial answer: | |
206 | * we supply 0-500 and stop. | |
207 | */ | |
02be0294 | 208 | ssize_t |
528b2c61 | 209 | mem_hdr::copy(off_t offset, char *buf, size_t size) const |
090089c4 | 210 | { |
528b2c61 | 211 | |
212 | debug(19, 6) ("memCopy: offset %ld: size %u\n", (long int) offset, size); | |
62e76326 | 213 | |
42a503bd | 214 | if (nodes.size() == 0) { |
215 | /* we shouldn't ever ask for absent offsets */ | |
216 | assert (0); | |
62e76326 | 217 | return 0; |
42a503bd | 218 | } |
62e76326 | 219 | |
528b2c61 | 220 | /* RC: the next assert is nearly useless */ |
97a88399 | 221 | assert(size > 0); |
528b2c61 | 222 | |
090089c4 | 223 | /* Seek our way into store */ |
528b2c61 | 224 | mem_node *p = getBlockContainingLocation((size_t)offset); |
62e76326 | 225 | |
528b2c61 | 226 | if (!p) { |
62e76326 | 227 | debug(19, 1) ("memCopy: could not find offset %u in memory.\n", (size_t) offset); |
228 | /* we shouldn't ever ask for absent offsets */ | |
229 | assert (0); | |
230 | return 0; | |
090089c4 | 231 | } |
62e76326 | 232 | |
528b2c61 | 233 | size_t bytes_to_go = size; |
234 | char *ptr_to_buf = buf; | |
235 | off_t location = offset; | |
62e76326 | 236 | |
090089c4 | 237 | /* Start copying begining with this block until |
238 | * we're satiated */ | |
528b2c61 | 239 | |
090089c4 | 240 | while (p && bytes_to_go > 0) { |
62e76326 | 241 | size_t bytes_to_copy = copyAvailable (p, |
242 | location, bytes_to_go, ptr_to_buf); | |
243 | ||
244 | /* hit a sparse patch */ | |
245 | ||
246 | if (bytes_to_copy == 0) | |
247 | return size - bytes_to_go; | |
248 | ||
249 | location += bytes_to_copy; | |
250 | ||
251 | ptr_to_buf += bytes_to_copy; | |
252 | ||
253 | bytes_to_go -= bytes_to_copy; | |
254 | ||
42a503bd | 255 | p = getBlockContainingLocation(location); |
090089c4 | 256 | } |
62e76326 | 257 | |
d89d1fb6 | 258 | return size - bytes_to_go; |
090089c4 | 259 | } |
528b2c61 | 260 | |
261 | bool | |
4c50505b | 262 | mem_hdr::hasContigousContentRange(Range<size_t> const & range) const |
528b2c61 | 263 | { |
4c50505b | 264 | size_t currentStart = range.start; |
62e76326 | 265 | |
528b2c61 | 266 | while (mem_node *curr = getBlockContainingLocation(currentStart)) { |
62e76326 | 267 | currentStart = curr->end(); |
268 | ||
4c50505b | 269 | if (currentStart >= range.end) |
62e76326 | 270 | return true; |
528b2c61 | 271 | } |
62e76326 | 272 | |
528b2c61 | 273 | return false; |
274 | } | |
275 | ||
276 | bool | |
277 | mem_hdr::unionNotEmpty(StoreIOBuffer const &candidate) | |
278 | { | |
528b2c61 | 279 | assert (candidate.offset >= 0); |
42a503bd | 280 | mem_node target(candidate.offset); |
281 | target.nodeBuffer.length = candidate.length; | |
282 | return nodes.find (&target, NodeCompare); | |
528b2c61 | 283 | } |
284 | ||
285 | mem_node * | |
286 | mem_hdr::nodeToRecieve(off_t offset) | |
287 | { | |
288 | /* case 1: Nothing in memory */ | |
62e76326 | 289 | |
42a503bd | 290 | if (!nodes.size()) { |
62e76326 | 291 | appendNode (new mem_node(offset)); |
42a503bd | 292 | return nodes.start()->data; |
528b2c61 | 293 | } |
294 | ||
42a503bd | 295 | mem_node *candidate = NULL; |
528b2c61 | 296 | /* case 2: location fits within an extant node */ |
62e76326 | 297 | |
42a503bd | 298 | if (offset > 0) { |
299 | mem_node search (offset - 1); | |
300 | search.nodeBuffer.length = 1; | |
301 | mem_node *const *leadup = nodes.find (&search, NodeCompare); | |
302 | ||
303 | if (leadup) | |
304 | candidate = *leadup; | |
528b2c61 | 305 | } |
306 | ||
42a503bd | 307 | if (candidate && candidate->canAccept(offset)) |
62e76326 | 308 | return candidate; |
528b2c61 | 309 | |
310 | /* candidate can't accept, so we need a new node */ | |
311 | candidate = new mem_node(offset); | |
62e76326 | 312 | |
528b2c61 | 313 | appendNode (candidate); |
62e76326 | 314 | |
528b2c61 | 315 | /* simpler to write than a indented if */ |
316 | return candidate; | |
317 | } | |
318 | ||
319 | ||
320 | bool | |
321 | mem_hdr::write (StoreIOBuffer const &writeBuffer) | |
322 | { | |
1d5161bd | 323 | PROF_start(mem_hdr_write); |
62e76326 | 324 | // mem_node *tempNode; |
23da259f | 325 | debug(19, 6) ("mem_hdr::write: offset %lu len %ld, object end %lu\n", (unsigned long)writeBuffer.offset, (long)writeBuffer.length, (unsigned long)endOffset()); |
528b2c61 | 326 | |
327 | if (unionNotEmpty(writeBuffer)) { | |
62e76326 | 328 | fatal("Attempt to overwrite already in-memory data\n"); |
1d5161bd | 329 | PROF_stop(mem_hdr_write); |
62e76326 | 330 | return false; |
528b2c61 | 331 | } |
332 | ||
333 | assert (writeBuffer.offset >= 0); | |
334 | ||
335 | mem_node *target; | |
336 | off_t currentOffset = writeBuffer.offset; | |
337 | char *currentSource = writeBuffer.data; | |
338 | size_t len = writeBuffer.length; | |
62e76326 | 339 | |
528b2c61 | 340 | while (len && (target = nodeToRecieve(currentOffset))) { |
62e76326 | 341 | size_t wrote = writeAvailable(target, currentOffset, len, currentSource); |
342 | assert (wrote); | |
343 | len -= wrote; | |
344 | currentOffset += wrote; | |
345 | currentSource += wrote; | |
528b2c61 | 346 | } |
347 | ||
1d5161bd | 348 | PROF_stop(mem_hdr_write); |
528b2c61 | 349 | return true; |
350 | } | |
4c50505b | 351 | |
42a503bd | 352 | mem_hdr::mem_hdr() : inmem_hi(0) |
4c50505b | 353 | {} |
354 | ||
355 | mem_hdr::~mem_hdr() | |
356 | { | |
357 | freeContent(); | |
358 | } | |
42a503bd | 359 | |
360 | /* splay of mem nodes: | |
361 | * conditions: | |
362 | * a = b if a.intersection(b).size > 0; | |
363 | * a < b if a < b | |
364 | */ | |
365 | int | |
366 | mem_hdr::NodeCompare(mem_node * const &left, mem_node * const &right) | |
367 | { | |
368 | // possibly Range can help us at some point. | |
369 | ||
370 | if (left->dataRange().intersection(right->dataRange()).size() > 0) | |
371 | return 0; | |
372 | ||
373 | return *left < *right ? -1 : 1; | |
374 | } | |
375 | ||
376 | void | |
377 | mem_hdr::dump() const | |
378 | { | |
379 | debug(20, 1) ("mem_hdr: %p nodes.start() %p\n", this, nodes.start()); | |
380 | debug(20, 1) ("mem_hdr: %p nodes.end() %p\n", this, nodes.end()); | |
381 | } | |
382 | ||
383 | size_t | |
384 | mem_hdr::size() const | |
385 | { | |
386 | return nodes.size(); | |
387 | } | |
388 | ||
389 | mem_node const * | |
390 | mem_hdr::start() const | |
391 | { | |
392 | const SplayNode<mem_node *> * result = nodes.start(); | |
393 | ||
394 | if (result) | |
395 | return result->data; | |
396 | ||
397 | return NULL; | |
398 | } |