1 : /******************************************************************************
2 : * $Id$
3 : *
4 : * Project: VSI Virtual File System
5 : * Purpose: Implementation of caching IO layer.
6 : * Author: Frank Warmerdam, warmerdam@pobox.com
7 : *
8 : ******************************************************************************
9 : * Copyright (c) 2011, Frank Warmerdam <warmerdam@pobox.com>
10 : *
11 : * Permission is hereby granted, free of charge, to any person obtaining a
12 : * copy of this software and associated documentation files (the "Software"),
13 : * to deal in the Software without restriction, including without limitation
14 : * the rights to use, copy, modify, merge, publish, distribute, sublicense,
15 : * and/or sell copies of the Software, and to permit persons to whom the
16 : * Software is furnished to do so, subject to the following conditions:
17 : *
18 : * The above copyright notice and this permission notice shall be included
19 : * in all copies or substantial portions of the Software.
20 : *
21 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
22 : * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
23 : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
24 : * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
25 : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
26 : * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
27 : * DEALINGS IN THE SOFTWARE.
28 : ****************************************************************************/
29 :
30 : #include "cpl_vsi_virtual.h"
31 :
32 : CPL_CVSID("$Id$");
33 :
34 : /************************************************************************/
35 : /* ==================================================================== */
36 : /* VSICacheChunk */
37 : /* ==================================================================== */
38 : /************************************************************************/
39 :
40 : #define CHUNK_SIZE 32768
41 :
42 : class VSICacheChunk
43 : {
44 : public:
45 131 : VSICacheChunk() {
46 131 : poLRUPrev = poLRUNext = NULL;
47 131 : nDataFilled = 0;
48 131 : bDirty = FALSE;
49 131 : }
50 :
51 : int bDirty;
52 : size_t iBlock;
53 :
54 : VSICacheChunk *poLRUPrev;
55 : VSICacheChunk *poLRUNext;
56 :
57 : vsi_l_offset nDataFilled;
58 : GByte abyData[CHUNK_SIZE];
59 : };
60 :
61 : /************************************************************************/
62 : /* ==================================================================== */
63 : /* VSICachedFile */
64 : /* ==================================================================== */
65 : /************************************************************************/
66 :
67 : class VSICachedFile : public VSIVirtualHandle
68 : {
69 : public:
70 : VSICachedFile( VSIVirtualHandle * );
71 3 : ~VSICachedFile() { Close(); }
72 :
73 : void FlushLRU();
74 : int LoadBlocks( size_t nStartBlock, size_t nBlockCount,
75 : void *pBuffer, size_t nBufferSize );
76 : void Demote( VSICacheChunk * );
77 :
78 : VSIVirtualHandle *poBase;
79 :
80 : vsi_l_offset nOffset;
81 : vsi_l_offset nFileSize;
82 :
83 : GUIntBig nCacheUsed;
84 : GUIntBig nCacheMax;
85 :
86 : VSICacheChunk *poLRUStart;
87 : VSICacheChunk *poLRUEnd;
88 :
89 : std::vector<VSICacheChunk*> apoCache;
90 :
91 : int bEOF;
92 :
93 : virtual int Seek( vsi_l_offset nOffset, int nWhence );
94 : virtual vsi_l_offset Tell();
95 : virtual size_t Read( void *pBuffer, size_t nSize, size_t nMemb );
96 : virtual size_t Write( const void *pBuffer, size_t nSize, size_t nMemb );
97 : virtual int Eof();
98 : virtual int Flush();
99 : virtual int Close();
100 : };
101 :
102 : /************************************************************************/
103 : /* VSICachedFile() */
104 : /************************************************************************/
105 :
106 3 : VSICachedFile::VSICachedFile( VSIVirtualHandle *poBaseHandle )
107 :
108 : {
109 3 : poBase = poBaseHandle;
110 :
111 3 : nCacheUsed = 0;
112 : nCacheMax = CPLScanUIntBig(
113 3 : CPLGetConfigOption( "VSI_CACHE_SIZE", "25000000" ), 40 );
114 :
115 3 : poLRUStart = NULL;
116 3 : poLRUEnd = NULL;
117 :
118 3 : poBase->Seek( 0, SEEK_END );
119 3 : nFileSize = poBase->Tell();
120 :
121 3 : nOffset = 0;
122 3 : bEOF = FALSE;
123 3 : }
124 :
125 : /************************************************************************/
126 : /* Close() */
127 : /************************************************************************/
128 :
129 6 : int VSICachedFile::Close()
130 :
131 : {
132 : size_t i;
133 174 : for( i = 0; i < apoCache.size(); i++ )
134 168 : delete apoCache[i];
135 :
136 6 : apoCache.resize( 0 );
137 :
138 6 : poLRUStart = NULL;
139 6 : poLRUEnd = NULL;
140 :
141 6 : nCacheUsed = 0;
142 :
143 6 : if( poBase )
144 : {
145 3 : poBase->Close();
146 3 : delete poBase;
147 3 : poBase = NULL;
148 : }
149 :
150 6 : return 0;
151 : }
152 :
153 : /************************************************************************/
154 : /* Seek() */
155 : /************************************************************************/
156 :
157 15 : int VSICachedFile::Seek( vsi_l_offset nReqOffset, int nWhence )
158 :
159 : {
160 15 : bEOF = FALSE;
161 :
162 15 : if( nWhence == SEEK_SET )
163 : {
164 : // use offset directly.
165 : }
166 :
167 6 : else if( nWhence == SEEK_CUR )
168 : {
169 3 : nReqOffset += nOffset;
170 : }
171 :
172 3 : else if( nWhence == SEEK_END )
173 : {
174 3 : nReqOffset += nFileSize;
175 : }
176 :
177 15 : nOffset = nReqOffset;
178 :
179 15 : return 0;
180 : }
181 :
182 : /************************************************************************/
183 : /* Tell() */
184 : /************************************************************************/
185 :
186 9 : vsi_l_offset VSICachedFile::Tell()
187 :
188 : {
189 9 : return nOffset;
190 : }
191 :
192 : /************************************************************************/
193 : /* FlushLRU() */
194 : /************************************************************************/
195 :
196 83 : void VSICachedFile::FlushLRU()
197 :
198 : {
199 83 : CPLAssert( poLRUStart != NULL );
200 :
201 83 : VSICacheChunk *poBlock = poLRUStart;
202 :
203 83 : CPLAssert( nCacheUsed >= poBlock->nDataFilled );
204 :
205 83 : nCacheUsed -= poBlock->nDataFilled;
206 :
207 83 : poLRUStart = poBlock->poLRUNext;
208 83 : if( poLRUEnd == poBlock )
209 2 : poLRUEnd = NULL;
210 :
211 83 : if( poBlock->poLRUNext != NULL )
212 81 : poBlock->poLRUNext->poLRUPrev = NULL;
213 :
214 83 : CPLAssert( !poBlock->bDirty );
215 :
216 83 : apoCache[poBlock->iBlock] = NULL;
217 :
218 83 : delete poBlock;
219 83 : }
220 :
221 : /************************************************************************/
222 : /* Demote() */
223 : /* */
224 : /* Demote the indicated block to the end of the LRU list. */
225 : /* Potentially integrate the link into the list if it is not */
226 : /* already there. */
227 : /************************************************************************/
228 :
229 131 : void VSICachedFile::Demote( VSICacheChunk *poBlock )
230 :
231 : {
232 : // already at end?
233 131 : if( poLRUEnd == poBlock )
234 0 : return;
235 :
236 131 : if( poLRUStart == poBlock )
237 0 : poLRUStart = poBlock->poLRUNext;
238 :
239 131 : if( poBlock->poLRUPrev != NULL )
240 0 : poBlock->poLRUPrev->poLRUNext = poBlock->poLRUNext;
241 :
242 131 : if( poBlock->poLRUNext != NULL )
243 0 : poBlock->poLRUNext->poLRUPrev = poBlock->poLRUPrev;
244 :
245 131 : poBlock->poLRUNext = NULL;
246 131 : poBlock->poLRUPrev = NULL;
247 :
248 131 : if( poLRUEnd != NULL )
249 126 : poLRUEnd->poLRUNext = poBlock;
250 131 : poLRUEnd = poBlock;
251 :
252 131 : if( poLRUStart == NULL )
253 5 : poLRUStart = poBlock;
254 : }
255 :
256 : /************************************************************************/
257 : /* LoadBlocks() */
258 : /* */
259 : /* Load the desired set of blocks. Use pBuffer as a temporary */
260 : /* buffer if it would be helpful. */
261 : /************************************************************************/
262 :
263 63 : int VSICachedFile::LoadBlocks( size_t nStartBlock, size_t nBlockCount,
264 : void *pBuffer, size_t nBufferSize )
265 :
266 : {
267 63 : if( nBlockCount == 0 )
268 0 : return 1;
269 :
270 63 : if( apoCache.size() < nStartBlock + nBlockCount )
271 9 : apoCache.resize( nStartBlock + nBlockCount );
272 :
273 : /* -------------------------------------------------------------------- */
274 : /* When we want to load only one block, we can directly load it */
275 : /* into the target buffer with no concern about intermediaries. */
276 : /* -------------------------------------------------------------------- */
277 63 : if( nBlockCount == 1 )
278 : {
279 7 : poBase->Seek( nStartBlock * CHUNK_SIZE, SEEK_SET );
280 :
281 7 : apoCache[nStartBlock] = new VSICacheChunk();
282 :
283 7 : VSICacheChunk *poBlock = apoCache[nStartBlock];
284 :
285 7 : poBlock->iBlock = nStartBlock;
286 7 : poBlock->nDataFilled = poBase->Read( poBlock->abyData, 1, CHUNK_SIZE );
287 7 : nCacheUsed += poBlock->nDataFilled;
288 :
289 : // Merges into the LRU list.
290 7 : Demote( poBlock );
291 :
292 7 : return 1;
293 : }
294 :
295 : /* -------------------------------------------------------------------- */
296 : /* If the buffer is quite large but not quite large enough to */
297 : /* hold all the blocks we will take the pain of splitting the */
298 : /* io request in two in order to avoid allocating a large */
299 : /* temporary buffer. */
300 : /* -------------------------------------------------------------------- */
301 56 : if( nBufferSize > CHUNK_SIZE * 20
302 : && nBufferSize < nBlockCount * CHUNK_SIZE )
303 : {
304 1 : if( !LoadBlocks( nStartBlock, 2, pBuffer, nBufferSize ) )
305 0 : return 0;
306 :
307 1 : return LoadBlocks( nStartBlock+2, nBlockCount-2, pBuffer, nBufferSize );
308 : }
309 :
310 : /* -------------------------------------------------------------------- */
311 : /* Do we need to allocate our own buffer? */
312 : /* -------------------------------------------------------------------- */
313 55 : GByte *pabyWorkBuffer = (GByte *) pBuffer;
314 :
315 55 : if( nBufferSize < CHUNK_SIZE * nBlockCount )
316 1 : pabyWorkBuffer = (GByte *) CPLMalloc(CHUNK_SIZE * nBlockCount);
317 :
318 : /* -------------------------------------------------------------------- */
319 : /* Read the whole request into the working buffer. */
320 : /* -------------------------------------------------------------------- */
321 55 : if( poBase->Seek( nStartBlock * CHUNK_SIZE, SEEK_SET ) != 0 )
322 0 : return 0;
323 :
324 55 : size_t nDataRead = poBase->Read( pabyWorkBuffer, 1, nBlockCount*CHUNK_SIZE);
325 :
326 55 : if( nBlockCount * CHUNK_SIZE > nDataRead + CHUNK_SIZE - 1 )
327 48 : nBlockCount = (nDataRead + CHUNK_SIZE - 1) / CHUNK_SIZE;
328 :
329 179 : for( size_t i = 0; i < nBlockCount; i++ )
330 : {
331 124 : VSICacheChunk *poBlock = new VSICacheChunk();
332 :
333 124 : poBlock->iBlock = nStartBlock + i;
334 :
335 124 : CPLAssert( apoCache[i+nStartBlock] == NULL );
336 :
337 124 : apoCache[i + nStartBlock] = poBlock;
338 :
339 124 : if( nDataRead >= (i+1) * CHUNK_SIZE )
340 124 : poBlock->nDataFilled = CHUNK_SIZE;
341 : else
342 0 : poBlock->nDataFilled = nDataRead - i*CHUNK_SIZE;
343 :
344 : memcpy( poBlock->abyData, pabyWorkBuffer + i*CHUNK_SIZE,
345 124 : (size_t) poBlock->nDataFilled );
346 :
347 124 : nCacheUsed += poBlock->nDataFilled;
348 :
349 : // Merges into the LRU list.
350 124 : Demote( poBlock );
351 : }
352 :
353 55 : if( pabyWorkBuffer != pBuffer )
354 1 : CPLFree( pabyWorkBuffer );
355 :
356 55 : return 1;
357 : }
358 :
359 : /************************************************************************/
360 : /* Read() */
361 : /************************************************************************/
362 :
363 12 : size_t VSICachedFile::Read( void * pBuffer, size_t nSize, size_t nCount )
364 :
365 : {
366 12 : if( nOffset >= nFileSize )
367 : {
368 3 : bEOF = TRUE;
369 3 : return 0;
370 : }
371 :
372 : /* ==================================================================== */
373 : /* Make sure the cache is loaded for the whole request region. */
374 : /* ==================================================================== */
375 9 : size_t nStartBlock = (size_t) (nOffset / CHUNK_SIZE);
376 9 : size_t nEndBlock = (size_t) ((nOffset + nSize * nCount - 1) / CHUNK_SIZE);
377 :
378 189 : for( size_t iBlock = nStartBlock; iBlock <= nEndBlock; iBlock++ )
379 : {
380 180 : if( apoCache.size() <= iBlock || apoCache[iBlock] == NULL )
381 : {
382 58 : size_t nBlocksToLoad = 1;
383 639 : while( iBlock + nBlocksToLoad <= nEndBlock
384 : && (apoCache.size() <= iBlock+nBlocksToLoad
385 : || apoCache[iBlock+nBlocksToLoad] == NULL) )
386 523 : nBlocksToLoad++;
387 :
388 58 : LoadBlocks( iBlock, nBlocksToLoad, pBuffer, nSize * nCount );
389 : }
390 : }
391 :
392 : /* ==================================================================== */
393 : /* Copy data into the target buffer to the extent possible. */
394 : /* ==================================================================== */
395 9 : size_t nAmountCopied = 0;
396 :
397 150 : while( nAmountCopied < nSize * nCount )
398 : {
399 135 : size_t iBlock = (size_t) ((nOffset + nAmountCopied) / CHUNK_SIZE);
400 : size_t nThisCopy;
401 135 : VSICacheChunk *poBlock = apoCache[iBlock];
402 135 : if( poBlock == NULL )
403 : {
404 : /* We can reach that point when the amount to read exceeds */
405 : /* the cache size */
406 : LoadBlocks( iBlock, 1, ((GByte *) pBuffer) + nAmountCopied,
407 3 : MIN(nSize * nCount - nAmountCopied, CHUNK_SIZE) );
408 3 : poBlock = apoCache[iBlock];
409 3 : CPLAssert(poBlock != NULL);
410 : }
411 :
412 : nThisCopy = (size_t)
413 : ((iBlock * CHUNK_SIZE + poBlock->nDataFilled)
414 135 : - nAmountCopied - nOffset);
415 :
416 135 : if( nThisCopy > nSize * nCount - nAmountCopied )
417 3 : nThisCopy = nSize * nCount - nAmountCopied;
418 :
419 135 : if( nThisCopy == 0 )
420 3 : break;
421 :
422 : memcpy( ((GByte *) pBuffer) + nAmountCopied,
423 : poBlock->abyData
424 : + (nOffset + nAmountCopied) - iBlock * CHUNK_SIZE,
425 132 : nThisCopy );
426 :
427 132 : nAmountCopied += nThisCopy;
428 : }
429 :
430 9 : nOffset += nAmountCopied;
431 :
432 : /* -------------------------------------------------------------------- */
433 : /* Ensure the cache is reduced to our limit. */
434 : /* -------------------------------------------------------------------- */
435 101 : while( nCacheUsed > nCacheMax )
436 83 : FlushLRU();
437 :
438 9 : size_t nRet = nAmountCopied / nSize;
439 9 : if (nRet != nCount)
440 3 : bEOF = TRUE;
441 9 : return nRet;
442 : }
443 :
444 : /************************************************************************/
445 : /* Write() */
446 : /************************************************************************/
447 :
448 0 : size_t VSICachedFile::Write( const void * pBuffer, size_t nSize, size_t nCount )
449 :
450 : {
451 0 : return 0;
452 : }
453 :
454 : /************************************************************************/
455 : /* Eof() */
456 : /************************************************************************/
457 :
458 0 : int VSICachedFile::Eof()
459 :
460 : {
461 0 : return bEOF;
462 : }
463 :
464 : /************************************************************************/
465 : /* Flush() */
466 : /************************************************************************/
467 :
468 0 : int VSICachedFile::Flush()
469 :
470 : {
471 0 : return 0;
472 : }
473 :
474 : /************************************************************************/
475 : /* VSICreateCachedFile() */
476 : /************************************************************************/
477 :
478 : VSIVirtualHandle *
479 3 : VSICreateCachedFile( VSIVirtualHandle *poBaseHandle )
480 :
481 : {
482 3 : return new VSICachedFile( poBaseHandle );
483 : }
|
