PDMAsyncCompletionFileCache.cpp@ 24350

Last change on this file since 24350 was 24278, checked in by vboxsync, 15 years ago
AsyncCompletion: Cleanup in the cache and more statistics (more to come)
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 58.2 KB

Line
1	/* $Id: PDMAsyncCompletionFileCache.cpp 24278 2009-11-02 20:26:07Z vboxsync $ */
2	/** @file
3	* PDM Async I/O - Transport data asynchronous in R3 using EMT.
4	* File data cache.
5	*/
6
7	/*
8	* Copyright (C) 2006-2008 Sun Microsystems, Inc.
9	*
10	* This file is part of VirtualBox Open Source Edition (OSE), as
11	* available from http://www.virtualbox.org. This file is free software;
12	* you can redistribute it and/or modify it under the terms of the GNU
13	* General Public License (GPL) as published by the Free Software
14	* Foundation, in version 2 as it comes in the "COPYING" file of the
15	* VirtualBox OSE distribution. VirtualBox OSE is distributed in the
16	* hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
17	*
18	* Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
19	* Clara, CA 95054 USA or visit http://www.sun.com if you need
20	* additional information or have any questions.
21	*/
22
23	/** @page pg_pdm_async_completion_cache PDM Async Completion Cache - The file I/O cache
24	* This component implements an I/O cache for file endpoints based on the ARC algorithm.
25	* http://en.wikipedia.org/wiki/Adaptive_Replacement_Cache
26	*
27	* The algorithm uses four LRU (Least frequently used) lists to store data in the cache.
28	* Two of them contain data where one stores entries which were accessed recently and one
29	* which is used for frequently accessed data.
30	* The other two lists are called ghost lists and store information about the accessed range
31	* but do not contain data. They are used to track data access. If these entries are accessed
32	* they will push the data to a higher position in the cache preventing it from getting removed
33	* quickly again.
34	*
35	* The algorithm needs to be modified to meet our requirements. Like the implementation
36	* for the ZFS filesystem we need to handle pages with a variable size. It would
37	* be possible to use a fixed size but would increase the computational
38	* and memory overhead.
39	* Because we do I/O asynchronously we also need to mark entries which are currently accessed
40	* as non evictable to prevent removal of the entry while the data is being accessed.
41	*/
42
43	/*******************************************************************************
44	* Header Files *
45	*******************************************************************************/
46	#define LOG_GROUP LOG_GROUP_PDM_ASYNC_COMPLETION
47	#include <iprt/types.h>
48	#include <iprt/mem.h>
49	#include <iprt/path.h>
50	#include <VBox/log.h>
51	#include <VBox/stam.h>
52
53	#include "PDMAsyncCompletionFileInternal.h"
54
55	#ifdef VBOX_STRICT
56	# define PDMACFILECACHE_IS_CRITSECT_OWNER(Cache) \
57	do \
58	{ \
59	AssertMsg(RTCritSectIsOwner(&pCache->CritSect), \
60	("Thread does not own critical section\n"));\
61	} while(0);
62	#else
63	# define PDMACFILECACHE_IS_CRITSECT_OWNER(Cache) do { } while(0);
64	#endif
65
66	/*******************************************************************************
67	* Internal Functions *
68	*******************************************************************************/
69	static void pdmacFileCacheTaskCompleted(PPDMACTASKFILE pTask, void *pvUser);
70
71	DECLINLINE(void) pdmacFileEpCacheEntryRelease(PPDMACFILECACHEENTRY pEntry)
72	{
73	AssertMsg(pEntry->cRefs > 0, ("Trying to release a not referenced entry\n"));
74	ASMAtomicDecU32(&pEntry->cRefs);
75	}
76
77	DECLINLINE(void) pdmacFileEpCacheEntryRef(PPDMACFILECACHEENTRY pEntry)
78	{
79	ASMAtomicIncU32(&pEntry->cRefs);
80	}
81
82	/**
83	* Checks consistency of a LRU list.
84	*
85	* @returns nothing
86	* @param pList The LRU list to check.
87	* @param pNotInList Element which is not allowed to occur in the list.
88	*/
89	static void pdmacFileCacheCheckList(PPDMACFILELRULIST pList, PPDMACFILECACHEENTRY pNotInList)
90	{
91	#ifdef PDMACFILECACHE_WITH_LRULIST_CHECKS
92	PPDMACFILECACHEENTRY pCurr = pList->pHead;
93
94	/* Check that there are no double entries and no cycles in the list. */
95	while (pCurr)
96	{
97	PPDMACFILECACHEENTRY pNext = pCurr->pNext;
98
99	while (pNext)
100	{
101	AssertMsg(pCurr != pNext,
102	("Entry %#p is at least two times in list %#p or there is a cycle in the list\n",
103	pCurr, pList));
104	pNext = pNext->pNext;
105	}
106
107	AssertMsg(pCurr != pNotInList, ("Not allowed entry %#p is in list\n", pCurr));
108
109	if (!pCurr->pNext)
110	AssertMsg(pCurr == pList->pTail, ("End of list reached but last element is not list tail\n"));
111
112	pCurr = pCurr->pNext;
113	}
114	#endif
115	}
116
117	/**
118	* Unlinks a cache entry from the LRU list it is assigned to.
119	*
120	* @returns nothing.
121	* @param pEntry The entry to unlink.
122	*/
123	static void pdmacFileCacheEntryRemoveFromList(PPDMACFILECACHEENTRY pEntry)
124	{
125	PPDMACFILELRULIST pList = pEntry->pList;
126	PPDMACFILECACHEENTRY pPrev, pNext;
127
128	LogFlowFunc((": Deleting entry %#p from list %#p\n", pEntry, pList));
129
130	AssertPtr(pList);
131	pdmacFileCacheCheckList(pList, NULL);
132
133	pPrev = pEntry->pPrev;
134	pNext = pEntry->pNext;
135
136	AssertMsg(pEntry != pPrev, ("Entry links to itself as previous element\n"));
137	AssertMsg(pEntry != pNext, ("Entry links to itself as next element\n"));
138
139	if (pPrev)
140	pPrev->pNext = pNext;
141	else
142	{
143	pList->pHead = pNext;
144
145	if (pNext)
146	pNext->pPrev = NULL;
147	}
148
149	if (pNext)
150	pNext->pPrev = pPrev;
151	else
152	{
153	pList->pTail = pPrev;
154
155	if (pPrev)
156	pPrev->pNext = NULL;
157	}
158
159	pEntry->pList = NULL;
160	pEntry->pPrev = NULL;
161	pEntry->pNext = NULL;
162	pList->cbCached -= pEntry->cbData;
163	pdmacFileCacheCheckList(pList, pEntry);
164	}
165
166	/**
167	* Adds a cache entry to the given LRU list unlinking it from the currently
168	* assigned list if needed.
169	*
170	* @returns nothing.
171	* @param pList List to the add entry to.
172	* @param pEntry Entry to add.
173	*/
174	static void pdmacFileCacheEntryAddToList(PPDMACFILELRULIST pList, PPDMACFILECACHEENTRY pEntry)
175	{
176	LogFlowFunc((": Adding entry %#p to list %#p\n", pEntry, pList));
177	pdmacFileCacheCheckList(pList, NULL);
178
179	/* Remove from old list if needed */
180	if (pEntry->pList)
181	pdmacFileCacheEntryRemoveFromList(pEntry);
182
183	pEntry->pNext = pList->pHead;
184	if (pList->pHead)
185	pList->pHead->pPrev = pEntry;
186	else
187	{
188	Assert(!pList->pTail);
189	pList->pTail = pEntry;
190	}
191
192	pEntry->pPrev = NULL;
193	pList->pHead = pEntry;
194	pList->cbCached += pEntry->cbData;
195	pEntry->pList = pList;
196	pdmacFileCacheCheckList(pList, NULL);
197	}
198
199	/**
200	* Destroys a LRU list freeing all entries.
201	*
202	* @returns nothing
203	* @param pList Pointer to the LRU list to destroy.
204	*
205	* @note The caller must own the critical section of the cache.
206	*/
207	static void pdmacFileCacheDestroyList(PPDMACFILELRULIST pList)
208	{
209	while (pList->pHead)
210	{
211	PPDMACFILECACHEENTRY pEntry = pList->pHead;
212
213	pList->pHead = pEntry->pNext;
214
215	AssertMsg(!(pEntry->fFlags & (PDMACFILECACHE_ENTRY_IO_IN_PROGRESS \| PDMACFILECACHE_ENTRY_IS_DIRTY)),
216	("Entry is dirty and/or still in progress fFlags=%#x\n", pEntry->fFlags));
217
218	RTMemPageFree(pEntry->pbData);
219	RTMemFree(pEntry);
220	}
221	}
222
223	/**
224	* Tries to remove the given amount of bytes from a given list in the cache
225	* moving the entries to one of the given ghosts lists
226	*
227	* @returns Amount of data which could be freed.
228	* @param pCache Pointer to the global cache data.
229	* @param cbData The amount of the data to free.
230	* @param pListSrc The source list to evict data from.
231	* @param pGhostListSrc The ghost list removed entries should be moved to
232	* NULL if the entry should be freed.
233	*
234	* @notes This function may return fewer bytes than requested because entries
235	* may be marked as non evictable if they are used for I/O at the moment.
236	*/
237	static size_t pdmacFileCacheEvictPagesFrom(PPDMACFILECACHEGLOBAL pCache, size_t cbData,
238	PPDMACFILELRULIST pListSrc, PPDMACFILELRULIST pGhostListDst)
239	{
240	size_t cbEvicted = 0;
241
242	PDMACFILECACHE_IS_CRITSECT_OWNER(pCache);
243
244	AssertMsg(cbData > 0, ("Evicting 0 bytes not possible\n"));
245	AssertMsg( !pGhostListDst
246	\|\| (pGhostListDst == &pCache->LruRecentlyGhost)
247	\|\| (pGhostListDst == &pCache->LruFrequentlyGhost),
248	("Destination list must be NULL or one of the ghost lists\n"));
249
250	/* Start deleting from the tail. */
251	PPDMACFILECACHEENTRY pEntry = pListSrc->pTail;
252
253	while ((cbEvicted < cbData) && pEntry)
254	{
255	PPDMACFILECACHEENTRY pCurr = pEntry;
256
257	pEntry = pEntry->pPrev;
258
259	/* We can't evict pages which are currently in progress */
260	if (!(pCurr->fFlags & PDMACFILECACHE_ENTRY_IO_IN_PROGRESS)
261	&& (ASMAtomicReadU32(&pCurr->cRefs) == 0))
262	{
263	/* Ok eviction candidate. Grab the endpoint semaphore and check again
264	* because somebody else might have raced us. */
265	PPDMACFILEENDPOINTCACHE pEndpointCache = &pCurr->pEndpoint->DataCache;
266	RTSemRWRequestWrite(pEndpointCache->SemRWEntries, RT_INDEFINITE_WAIT);
267
268	if (!(pCurr->fFlags & PDMACFILECACHE_ENTRY_IO_IN_PROGRESS)
269	&& (ASMAtomicReadU32(&pCurr->cRefs) == 0))
270	{
271	LogFlow(("Evicting entry %#p (%u bytes)\n", pCurr, pCurr->cbData));
272	if (pCurr->pbData)
273	{
274	RTMemPageFree(pCurr->pbData);
275	pCurr->pbData = NULL;
276	}
277
278	cbEvicted += pCurr->cbData;
279
280	if (pGhostListDst)
281	{
282	pdmacFileCacheEntryAddToList(pGhostListDst, pCurr);
283	}
284	else
285	{
286	/* Delete the entry from the AVL tree it is assigned to. */
287	STAM_PROFILE_ADV_START(&pCache->StatTreeRemove, Cache);
288	RTAvlrFileOffsetRemove(pCurr->pEndpoint->DataCache.pTree, pCurr->Core.Key);
289	STAM_PROFILE_ADV_STOP(&pCache->StatTreeRemove, Cache);
290
291	pdmacFileCacheEntryRemoveFromList(pCurr);
292	pCache->cbCached -= pCurr->cbData;
293
294	RTMemFree(pCurr);
295	}
296	}
297	RTSemRWReleaseWrite(pEndpointCache->SemRWEntries);
298	}
299	else
300	LogFlow(("Entry %#p (%u bytes) is still in progress and can't be evicted\n", pCurr, pCurr->cbData));
301	}
302
303	return cbEvicted;
304	}
305
306	static size_t pdmacFileCacheReplace(PPDMACFILECACHEGLOBAL pCache, size_t cbData, PPDMACFILELRULIST pEntryList)
307	{
308	PDMACFILECACHE_IS_CRITSECT_OWNER(pCache);
309
310	if ( (pCache->LruRecentlyUsed.cbCached)
311	&& ( (pCache->LruRecentlyUsed.cbCached > pCache->uAdaptVal)
312	\|\| ( (pEntryList == &pCache->LruFrequentlyGhost)
313	&& (pCache->LruRecentlyUsed.cbCached == pCache->uAdaptVal))))
314	{
315	/* We need to remove entry size pages from T1 and move the entries to B1 */
316	return pdmacFileCacheEvictPagesFrom(pCache, cbData,
317	&pCache->LruRecentlyUsed,
318	&pCache->LruRecentlyGhost);
319	}
320	else
321	{
322	/* We need to remove entry size pages from T2 and move the entries to B2 */
323	return pdmacFileCacheEvictPagesFrom(pCache, cbData,
324	&pCache->LruFrequentlyUsed,
325	&pCache->LruFrequentlyGhost);
326	}
327	}
328
329	/**
330	* Tries to evict the given amount of the data from the cache.
331	*
332	* @returns Bytes removed.
333	* @param pCache The global cache data.
334	* @param cbData Number of bytes to evict.
335	*/
336	static size_t pdmacFileCacheEvict(PPDMACFILECACHEGLOBAL pCache, size_t cbData)
337	{
338	size_t cbRemoved = ~0;
339
340	PDMACFILECACHE_IS_CRITSECT_OWNER(pCache);
341
342	if ((pCache->LruRecentlyUsed.cbCached + pCache->LruRecentlyGhost.cbCached) >= pCache->cbMax)
343	{
344	/* Delete desired pages from the cache. */
345	if (pCache->LruRecentlyUsed.cbCached < pCache->cbMax)
346	{
347	cbRemoved = pdmacFileCacheEvictPagesFrom(pCache, cbData,
348	&pCache->LruRecentlyGhost,
349	NULL);
350	}
351	else
352	{
353	cbRemoved = pdmacFileCacheEvictPagesFrom(pCache, cbData,
354	&pCache->LruRecentlyUsed,
355	NULL);
356	}
357	}
358	else
359	{
360	uint32_t cbUsed = pCache->LruRecentlyUsed.cbCached + pCache->LruRecentlyGhost.cbCached +
361	pCache->LruFrequentlyUsed.cbCached + pCache->LruFrequentlyGhost.cbCached;
362
363	if (cbUsed >= pCache->cbMax)
364	{
365	if (cbUsed == 2*pCache->cbMax)
366	cbRemoved = pdmacFileCacheEvictPagesFrom(pCache, cbData,
367	&pCache->LruFrequentlyGhost,
368	NULL);
369
370	if (cbRemoved >= cbData)
371	cbRemoved = pdmacFileCacheReplace(pCache, cbData, NULL);
372	}
373	}
374
375	return cbRemoved;
376	}
377
378	/**
379	* Updates the cache parameters
380	*
381	* @returns nothing.
382	* @param pCache The global cache data.
383	* @param pEntry The entry usign for the update.
384	*/
385	static void pdmacFileCacheUpdate(PPDMACFILECACHEGLOBAL pCache, PPDMACFILECACHEENTRY pEntry)
386	{
387	int32_t uUpdateVal = 0;
388
389	PDMACFILECACHE_IS_CRITSECT_OWNER(pCache);
390
391	/* Update parameters */
392	if (pEntry->pList == &pCache->LruRecentlyGhost)
393	{
394	if (pCache->LruRecentlyGhost.cbCached >= pCache->LruFrequentlyGhost.cbCached)
395	uUpdateVal = 1;
396	else
397	uUpdateVal = pCache->LruFrequentlyGhost.cbCached / pCache->LruRecentlyGhost.cbCached;
398
399	pCache->uAdaptVal = RT_MIN(pCache->uAdaptVal + uUpdateVal, pCache->cbMax);
400	}
401	else if (pEntry->pList == &pCache->LruFrequentlyGhost)
402	{
403	if (pCache->LruFrequentlyGhost.cbCached >= pCache->LruRecentlyGhost.cbCached)
404	uUpdateVal = 1;
405	else
406	uUpdateVal = pCache->LruRecentlyGhost.cbCached / pCache->LruFrequentlyGhost.cbCached;
407
408	pCache->uAdaptVal = RT_MIN(pCache->uAdaptVal - uUpdateVal, 0);
409	}
410	else
411	AssertMsgFailed(("Invalid list type\n"));
412	}
413
414	/**
415	* Initiates a read I/O task for the given entry.
416	*
417	* @returns nothing.
418	* @param pEntry The entry to fetch the data to.
419	*/
420	static void pdmacFileCacheReadFromEndpoint(PPDMACFILECACHEENTRY pEntry)
421	{
422	LogFlowFunc((": Reading data into cache entry %#p\n", pEntry));
423
424	/* Make sure no one evicts the entry while it is accessed. */
425	pEntry->fFlags \|= PDMACFILECACHE_ENTRY_IO_IN_PROGRESS;
426
427	PPDMACTASKFILE pIoTask = pdmacFileTaskAlloc(pEntry->pEndpoint);
428	AssertPtr(pIoTask);
429
430	AssertMsg(pEntry->pbData, ("Entry is in ghost state\n"));
431
432	pIoTask->pEndpoint = pEntry->pEndpoint;
433	pIoTask->enmTransferType = PDMACTASKFILETRANSFER_READ;
434	pIoTask->Off = pEntry->Core.Key;
435	pIoTask->DataSeg.cbSeg = pEntry->cbData;
436	pIoTask->DataSeg.pvSeg = pEntry->pbData;
437	pIoTask->pvUser = pEntry;
438	pIoTask->pfnCompleted = pdmacFileCacheTaskCompleted;
439
440	/* Send it off to the I/O manager. */
441	pdmacFileEpAddTask(pEntry->pEndpoint, pIoTask);
442	}
443
444	/**
445	* Initiates a write I/O task for the given entry.
446	*
447	* @returns nothing.
448	* @param pEntry The entry to read the data from.
449	*/
450	static void pdmacFileCacheWriteToEndpoint(PPDMACFILECACHEENTRY pEntry)
451	{
452	LogFlowFunc((": Writing data from cache entry %#p\n", pEntry));
453
454	/* Make sure no one evicts the entry while it is accessed. */
455	pEntry->fFlags \|= PDMACFILECACHE_ENTRY_IO_IN_PROGRESS;
456
457	PPDMACTASKFILE pIoTask = pdmacFileTaskAlloc(pEntry->pEndpoint);
458	AssertPtr(pIoTask);
459
460	AssertMsg(pEntry->pbData, ("Entry is in ghost state\n"));
461
462	pIoTask->pEndpoint = pEntry->pEndpoint;
463	pIoTask->enmTransferType = PDMACTASKFILETRANSFER_WRITE;
464	pIoTask->Off = pEntry->Core.Key;
465	pIoTask->DataSeg.cbSeg = pEntry->cbData;
466	pIoTask->DataSeg.pvSeg = pEntry->pbData;
467	pIoTask->pvUser = pEntry;
468	pIoTask->pfnCompleted = pdmacFileCacheTaskCompleted;
469
470	/* Send it off to the I/O manager. */
471	pdmacFileEpAddTask(pEntry->pEndpoint, pIoTask);
472	}
473
474	/**
475	* Completion callback for I/O tasks.
476	*
477	* @returns nothing.
478	* @param pTask The completed task.
479	* @param pvUser Opaque user data.
480	*/
481	static void pdmacFileCacheTaskCompleted(PPDMACTASKFILE pTask, void *pvUser)
482	{
483	PPDMACFILECACHEENTRY pEntry = (PPDMACFILECACHEENTRY)pvUser;
484	PPDMACFILECACHEGLOBAL pCache = pEntry->pCache;
485	PPDMASYNCCOMPLETIONENDPOINTFILE pEndpoint = pEntry->pEndpoint;
486
487	/* Reference the entry now as we are clearing the I/O in progres flag
488	* which protects the entry till now. */
489	pdmacFileEpCacheEntryRef(pEntry);
490
491	RTSemRWRequestWrite(pEndpoint->DataCache.SemRWEntries, RT_INDEFINITE_WAIT);
492	pEntry->fFlags &= ~PDMACFILECACHE_ENTRY_IO_IN_PROGRESS;
493
494	/* Process waiting segment list. The data in entry might have changed inbetween. */
495	PPDMACFILETASKSEG pCurr = pEntry->pWaitingHead;
496
497	AssertMsg((pCurr && pEntry->pWaitingTail) \|\| (!pCurr && !pEntry->pWaitingTail),
498	("The list tail was not updated correctly\n"));
499	pEntry->pWaitingTail = NULL;
500	pEntry->pWaitingHead = NULL;
501
502	if (pTask->enmTransferType == PDMACTASKFILETRANSFER_WRITE)
503	{
504	pEntry->fFlags &= ~PDMACFILECACHE_ENTRY_IS_DIRTY;
505
506	while (pCurr)
507	{
508	AssertMsg(pCurr->fWrite, ("Completed write entries should never have read tasks attached\n"));
509
510	memcpy(pEntry->pbData + pCurr->uBufOffset, pCurr->pvBuf, pCurr->cbTransfer);
511	pEntry->fFlags \|= PDMACFILECACHE_ENTRY_IS_DIRTY;
512
513	uint32_t uOld = ASMAtomicSubU32(&pCurr->pTask->cbTransferLeft, pCurr->cbTransfer);
514	AssertMsg(uOld >= pCurr->cbTransfer, ("New value would overflow\n"));
515	if (!(uOld - pCurr->cbTransfer)
516	&& !ASMAtomicXchgBool(&pCurr->pTask->fCompleted, true))
517	pdmR3AsyncCompletionCompleteTask(&pCurr->pTask->Core);
518
519	PPDMACFILETASKSEG pFree = pCurr;
520	pCurr = pCurr->pNext;
521
522	RTMemFree(pFree);
523	}
524	}
525	else
526	{
527	AssertMsg(pTask->enmTransferType == PDMACTASKFILETRANSFER_READ, ("Invalid transfer type\n"));
528	AssertMsg(!(pEntry->fFlags & PDMACFILECACHE_ENTRY_IS_DIRTY),("Invalid flags set\n"));
529
530	while (pCurr)
531	{
532	if (pCurr->fWrite)
533	{
534	memcpy(pEntry->pbData + pCurr->uBufOffset, pCurr->pvBuf, pCurr->cbTransfer);
535	pEntry->fFlags \|= PDMACFILECACHE_ENTRY_IS_DIRTY;
536	}
537	else
538	memcpy(pCurr->pvBuf, pEntry->pbData + pCurr->uBufOffset, pCurr->cbTransfer);
539
540	uint32_t uOld = ASMAtomicSubU32(&pCurr->pTask->cbTransferLeft, pCurr->cbTransfer);
541	AssertMsg(uOld >= pCurr->cbTransfer, ("New value would overflow\n"));
542	if (!(uOld - pCurr->cbTransfer)
543	&& !ASMAtomicXchgBool(&pCurr->pTask->fCompleted, true))
544	pdmR3AsyncCompletionCompleteTask(&pCurr->pTask->Core);
545
546	PPDMACFILETASKSEG pFree = pCurr;
547	pCurr = pCurr->pNext;
548
549	RTMemFree(pFree);
550	}
551	}
552
553	if (pEntry->fFlags & PDMACFILECACHE_ENTRY_IS_DIRTY)
554	pdmacFileCacheWriteToEndpoint(pEntry);
555
556	RTSemRWReleaseWrite(pEndpoint->DataCache.SemRWEntries);
557
558	/* Dereference so that it isn't protected anymore except we issued anyother write for it. */
559	pdmacFileEpCacheEntryRelease(pEntry);
560	}
561
562	/**
563	* Initializies the I/O cache.
564	*
565	* returns VBox status code.
566	* @param pClassFile The global class data for file endpoints.
567	* @param pCfgNode CFGM node to query configuration data from.
568	*/
569	int pdmacFileCacheInit(PPDMASYNCCOMPLETIONEPCLASSFILE pClassFile, PCFGMNODE pCfgNode)
570	{
571	int rc = VINF_SUCCESS;
572	PPDMACFILECACHEGLOBAL pCache = &pClassFile->Cache;
573
574	/* Initialize members */
575	pCache->LruRecentlyUsed.pHead = NULL;
576	pCache->LruRecentlyUsed.pTail = NULL;
577	pCache->LruRecentlyUsed.cbCached = 0;
578
579	pCache->LruFrequentlyUsed.pHead = NULL;
580	pCache->LruFrequentlyUsed.pTail = NULL;
581	pCache->LruFrequentlyUsed.cbCached = 0;
582
583	pCache->LruRecentlyGhost.pHead = NULL;
584	pCache->LruRecentlyGhost.pTail = NULL;
585	pCache->LruRecentlyGhost.cbCached = 0;
586
587	pCache->LruFrequentlyGhost.pHead = NULL;
588	pCache->LruFrequentlyGhost.pTail = NULL;
589	pCache->LruFrequentlyGhost.cbCached = 0;
590
591	rc = CFGMR3QueryU32Def(pCfgNode, "CacheSize", &pCache->cbMax, 5 * _1M);
592	AssertLogRelRCReturn(rc, rc);
593
594	pCache->cbCached = 0;
595	pCache->uAdaptVal = 0;
596	LogFlowFunc((": Maximum number of bytes cached %u\n", pCache->cbMax));
597
598	STAMR3Register(pClassFile->Core.pVM, &pCache->cbMax,
599	STAMTYPE_U32, STAMVISIBILITY_ALWAYS,
600	"/PDM/AsyncCompletion/File/cbMax",
601	STAMUNIT_BYTES,
602	"Maximum cache size");
603	STAMR3Register(pClassFile->Core.pVM, &pCache->cbCached,
604	STAMTYPE_U32, STAMVISIBILITY_ALWAYS,
605	"/PDM/AsyncCompletion/File/cbCached",
606	STAMUNIT_BYTES,
607	"Currently used cache");
608	STAMR3Register(pClassFile->Core.pVM, &pCache->LruRecentlyUsed.cbCached,
609	STAMTYPE_U32, STAMVISIBILITY_ALWAYS,
610	"/PDM/AsyncCompletion/File/cbCachedMru",
611	STAMUNIT_BYTES,
612	"Number of bytes cached in Mru list");
613	STAMR3Register(pClassFile->Core.pVM, &pCache->LruFrequentlyUsed.cbCached,
614	STAMTYPE_U32, STAMVISIBILITY_ALWAYS,
615	"/PDM/AsyncCompletion/File/cbCachedFru",
616	STAMUNIT_BYTES,
617	"Number of bytes cached in Fru list");
618	STAMR3Register(pClassFile->Core.pVM, &pCache->LruRecentlyGhost.cbCached,
619	STAMTYPE_U32, STAMVISIBILITY_ALWAYS,
620	"/PDM/AsyncCompletion/File/cbCachedMruGhost",
621	STAMUNIT_BYTES,
622	"Number of bytes cached in Mru ghost list");
623	STAMR3Register(pClassFile->Core.pVM, &pCache->LruFrequentlyGhost.cbCached,
624	STAMTYPE_U32, STAMVISIBILITY_ALWAYS,
625	"/PDM/AsyncCompletion/File/cbCachedFruGhost",
626	STAMUNIT_BYTES, "Number of bytes cached in Fru ghost list");
627
628	#ifdef VBOX_WITH_STATISTICS
629	STAMR3Register(pClassFile->Core.pVM, &pCache->cHits,
630	STAMTYPE_COUNTER, STAMVISIBILITY_ALWAYS,
631	"/PDM/AsyncCompletion/File/CacheHits",
632	STAMUNIT_COUNT, "Number of hits in the cache");
633	STAMR3Register(pClassFile->Core.pVM, &pCache->cPartialHits,
634	STAMTYPE_COUNTER, STAMVISIBILITY_ALWAYS,
635	"/PDM/AsyncCompletion/File/CachePartialHits",
636	STAMUNIT_COUNT, "Number of partial hits in the cache");
637	STAMR3Register(pClassFile->Core.pVM, &pCache->cMisses,
638	STAMTYPE_COUNTER, STAMVISIBILITY_ALWAYS,
639	"/PDM/AsyncCompletion/File/CacheMisses",
640	STAMUNIT_COUNT, "Number of misses when accessing the cache");
641	STAMR3Register(pClassFile->Core.pVM, &pCache->StatRead,
642	STAMTYPE_COUNTER, STAMVISIBILITY_ALWAYS,
643	"/PDM/AsyncCompletion/File/CacheRead",
644	STAMUNIT_BYTES, "Number of bytes read from the cache");
645	STAMR3Register(pClassFile->Core.pVM, &pCache->StatWritten,
646	STAMTYPE_COUNTER, STAMVISIBILITY_ALWAYS,
647	"/PDM/AsyncCompletion/File/CacheWritten",
648	STAMUNIT_BYTES, "Number of bytes written to the cache");
649	STAMR3Register(pClassFile->Core.pVM, &pCache->StatTreeGet,
650	STAMTYPE_PROFILE_ADV, STAMVISIBILITY_ALWAYS,
651	"/PDM/AsyncCompletion/File/CacheTreeGet",
652	STAMUNIT_TICKS_PER_CALL, "Time taken to access an entry in the tree");
653	STAMR3Register(pClassFile->Core.pVM, &pCache->StatTreeInsert,
654	STAMTYPE_PROFILE_ADV, STAMVISIBILITY_ALWAYS,
655	"/PDM/AsyncCompletion/File/CacheTreeInsert",
656	STAMUNIT_TICKS_PER_CALL, "Time taken to insert an entry in the tree");
657	STAMR3Register(pClassFile->Core.pVM, &pCache->StatTreeRemove,
658	STAMTYPE_PROFILE_ADV, STAMVISIBILITY_ALWAYS,
659	"/PDM/AsyncCompletion/File/CacheTreeRemove",
660	STAMUNIT_TICKS_PER_CALL, "Time taken to remove an entry an the tree");
661	#endif
662
663	/* Initialize the critical section */
664	rc = RTCritSectInit(&pCache->CritSect);
665	return rc;
666	}
667
668	/**
669	* Destroysthe cache freeing all data.
670	*
671	* returns nothing.
672	* @param pClassFile The global class data for file endpoints.
673	*/
674	void pdmacFileCacheDestroy(PPDMASYNCCOMPLETIONEPCLASSFILE pClassFile)
675	{
676	PPDMACFILECACHEGLOBAL pCache = &pClassFile->Cache;
677
678	/* Make sure no one else uses the cache now */
679	RTCritSectEnter(&pCache->CritSect);
680
681	/* Cleanup deleting all cache entries waiting for in progress entries to finish. */
682	pdmacFileCacheDestroyList(&pCache->LruRecentlyUsed);
683	pdmacFileCacheDestroyList(&pCache->LruFrequentlyUsed);
684	pdmacFileCacheDestroyList(&pCache->LruRecentlyGhost);
685	pdmacFileCacheDestroyList(&pCache->LruFrequentlyGhost);
686
687	RTCritSectLeave(&pCache->CritSect);
688
689	RTCritSectDelete(&pCache->CritSect);
690	}
691
692	/**
693	* Initializes per endpoint cache data
694	* like the AVL tree used to access cached entries.
695	*
696	* @returns VBox status code.
697	* @param pEndpoint The endpoint to init the cache for,
698	* @param pClassFile The global class data for file endpoints.
699	*/
700	int pdmacFileEpCacheInit(PPDMASYNCCOMPLETIONENDPOINTFILE pEndpoint, PPDMASYNCCOMPLETIONEPCLASSFILE pClassFile)
701	{
702	PPDMACFILEENDPOINTCACHE pEndpointCache = &pEndpoint->DataCache;
703
704	pEndpointCache->pCache = &pClassFile->Cache;
705
706	int rc = RTSemRWCreate(&pEndpointCache->SemRWEntries);
707	if (RT_SUCCESS(rc))
708	{
709	pEndpointCache->pTree = (PAVLRFOFFTREE)RTMemAllocZ(sizeof(AVLRFOFFTREE));
710	if (!pEndpointCache->pTree)
711	{
712	rc = VERR_NO_MEMORY;
713	RTSemRWDestroy(pEndpointCache->SemRWEntries);
714	}
715	}
716
717	#ifdef VBOX_WITH_STATISTICS
718	if (RT_SUCCESS(rc))
719	{
720	STAMR3RegisterF(pClassFile->Core.pVM, &pEndpointCache->StatWriteDeferred,
721	STAMTYPE_COUNTER, STAMVISIBILITY_ALWAYS,
722	STAMUNIT_COUNT, "Number of deferred writes",
723	"/PDM/AsyncCompletion/File/%s/Cache/DeferredWrites", RTPathFilename(pEndpoint->Core.pszUri));
724	}
725	#endif
726
727	return rc;
728	}
729
730	/**
731	* Callback for the AVL destroy routine. Frees a cache entry for this endpoint.
732	*
733	* @returns IPRT status code.
734	* @param pNode The node to destroy.
735	* @param pvUser Opaque user data.
736	*/
737	static int pdmacFileEpCacheEntryDestroy(PAVLRFOFFNODECORE pNode, void *pvUser)
738	{
739	PPDMACFILECACHEENTRY pEntry = (PPDMACFILECACHEENTRY)pNode;
740	PPDMACFILECACHEGLOBAL pCache = (PPDMACFILECACHEGLOBAL)pvUser;
741	PPDMACFILEENDPOINTCACHE pEndpointCache = &pEntry->pEndpoint->DataCache;
742
743	while (pEntry->fFlags & (PDMACFILECACHE_ENTRY_IO_IN_PROGRESS \| PDMACFILECACHE_ENTRY_IS_DIRTY))
744	{
745	RTSemRWReleaseWrite(pEndpointCache->SemRWEntries);
746	RTThreadSleep(250);
747	RTSemRWRequestWrite(pEndpointCache->SemRWEntries, RT_INDEFINITE_WAIT);
748	}
749
750	AssertMsg(!(pEntry->fFlags & (PDMACFILECACHE_ENTRY_IO_IN_PROGRESS \| PDMACFILECACHE_ENTRY_IS_DIRTY)),
751	("Entry is dirty and/or still in progress fFlags=%#x\n", pEntry->fFlags));
752
753	pdmacFileCacheEntryRemoveFromList(pEntry);
754	pCache->cbCached -= pEntry->cbData;
755
756	RTMemPageFree(pEntry->pbData);
757	RTMemFree(pEntry);
758
759	return VINF_SUCCESS;
760	}
761
762	/**
763	* Destroys all cache ressources used by the given endpoint.
764	*
765	* @returns nothing.
766	* @param pEndpoint The endpoint to the destroy.
767	*/
768	void pdmacFileEpCacheDestroy(PPDMASYNCCOMPLETIONENDPOINTFILE pEndpoint)
769	{
770	PPDMACFILEENDPOINTCACHE pEndpointCache = &pEndpoint->DataCache;
771	PPDMACFILECACHEGLOBAL pCache = pEndpointCache->pCache;
772
773	/* Make sure nobody is accessing the cache while we delete the tree. */
774	RTSemRWRequestWrite(pEndpointCache->SemRWEntries, RT_INDEFINITE_WAIT);
775	RTCritSectEnter(&pCache->CritSect);
776	RTAvlrFileOffsetDestroy(pEndpointCache->pTree, pdmacFileEpCacheEntryDestroy, pCache);
777	RTCritSectLeave(&pCache->CritSect);
778	RTSemRWReleaseWrite(pEndpointCache->SemRWEntries);
779
780	RTSemRWDestroy(pEndpointCache->SemRWEntries);
781
782	#ifdef VBOX_WITH_STATISTICS
783	PPDMASYNCCOMPLETIONEPCLASSFILE pEpClassFile = (PPDMASYNCCOMPLETIONEPCLASSFILE)pEndpoint->Core.pEpClass;
784
785	STAMR3Deregister(pEpClassFile->Core.pVM, &pEndpointCache->StatWriteDeferred);
786	#endif
787	}
788
789	static PPDMACFILECACHEENTRY pdmacFileEpCacheGetCacheEntryByOffset(PPDMACFILEENDPOINTCACHE pEndpointCache, RTFOFF off)
790	{
791	PPDMACFILECACHEGLOBAL pCache = pEndpointCache->pCache;
792	PPDMACFILECACHEENTRY pEntry = NULL;
793
794	STAM_PROFILE_ADV_START(&pCache->StatTreeGet, Cache);
795
796	RTSemRWRequestRead(pEndpointCache->SemRWEntries, RT_INDEFINITE_WAIT);
797	pEntry = (PPDMACFILECACHEENTRY)RTAvlrFileOffsetRangeGet(pEndpointCache->pTree, off);
798	if (pEntry)
799	pdmacFileEpCacheEntryRef(pEntry);
800	RTSemRWReleaseRead(pEndpointCache->SemRWEntries);
801
802	STAM_PROFILE_ADV_STOP(&pCache->StatTreeGet, Cache);
803
804	return pEntry;
805	}
806
807	static PPDMACFILECACHEENTRY pdmacFileEpCacheGetCacheBestFitEntryByOffset(PPDMACFILEENDPOINTCACHE pEndpointCache, RTFOFF off)
808	{
809	PPDMACFILECACHEGLOBAL pCache = pEndpointCache->pCache;
810	PPDMACFILECACHEENTRY pEntry = NULL;
811
812	STAM_PROFILE_ADV_START(&pCache->StatTreeGet, Cache);
813
814	RTSemRWRequestRead(pEndpointCache->SemRWEntries, RT_INDEFINITE_WAIT);
815	pEntry = (PPDMACFILECACHEENTRY)RTAvlrFileOffsetGetBestFit(pEndpointCache->pTree, off, true);
816	if (pEntry)
817	pdmacFileEpCacheEntryRef(pEntry);
818	RTSemRWReleaseRead(pEndpointCache->SemRWEntries);
819
820	STAM_PROFILE_ADV_STOP(&pCache->StatTreeGet, Cache);
821
822	return pEntry;
823	}
824
825	static void pdmacFileEpCacheInsertEntry(PPDMACFILEENDPOINTCACHE pEndpointCache, PPDMACFILECACHEENTRY pEntry)
826	{
827	PPDMACFILECACHEGLOBAL pCache = pEndpointCache->pCache;
828
829	STAM_PROFILE_ADV_START(&pCache->StatTreeInsert, Cache);
830	RTSemRWRequestWrite(pEndpointCache->SemRWEntries, RT_INDEFINITE_WAIT);
831	bool fInserted = RTAvlrFileOffsetInsert(pEndpointCache->pTree, &pEntry->Core);
832	AssertMsg(fInserted, ("Node was not inserted into tree\n"));
833	STAM_PROFILE_ADV_STOP(&pCache->StatTreeInsert, Cache);
834	RTSemRWReleaseWrite(pEndpointCache->SemRWEntries);
835	}
836
837	/**
838	* Allocates and initializes a new entry for the cache.
839	* The entry has a reference count of 1.
840	*
841	* @returns Pointer to the new cache entry or NULL if out of memory.
842	* @param pCache The cache the entry belongs to.
843	* @param pEndoint The endpoint the entry holds data for.
844	* @param off Start offset.
845	* @param cbData Size of the cache entry.
846	*/
847	static PPDMACFILECACHEENTRY pdmacFileCacheEntryAlloc(PPDMACFILECACHEGLOBAL pCache,
848	PPDMASYNCCOMPLETIONENDPOINTFILE pEndpoint,
849	RTFOFF off, size_t cbData)
850	{
851	PPDMACFILECACHEENTRY pEntryNew = (PPDMACFILECACHEENTRY)RTMemAllocZ(sizeof(PDMACFILECACHEENTRY));
852
853	if (RT_UNLIKELY(!pEntryNew))
854	return NULL;
855
856	pEntryNew->Core.Key = off;
857	pEntryNew->Core.KeyLast = off + cbData - 1;
858	pEntryNew->pEndpoint = pEndpoint;
859	pEntryNew->pCache = pCache;
860	pEntryNew->fFlags = 0;
861	pEntryNew->cRefs = 1; /* We are using it now. */
862	pEntryNew->pList = NULL;
863	pEntryNew->cbData = cbData;
864	pEntryNew->pWaitingHead = NULL;
865	pEntryNew->pWaitingTail = NULL;
866	pEntryNew->pbData = (uint8_t *)RTMemPageAlloc(cbData);
867
868	if (RT_UNLIKELY(!pEntryNew->pbData))
869	{
870	RTMemFree(pEntryNew);
871	return NULL;
872	}
873
874	return pEntryNew;
875	}
876
877	/**
878	* Adds a segment to the waiting list for a cache entry
879	* which is currently in progress.
880	*
881	* @returns nothing.
882	* @param pEntry The cache entry to add the segment to.
883	* @param pSeg The segment to add.
884	*/
885	static void pdmacFileEpCacheEntryAddWaitingSegment(PPDMACFILECACHEENTRY pEntry, PPDMACFILETASKSEG pSeg)
886	{
887	pSeg->pNext = NULL;
888
889	if (pEntry->pWaitingHead)
890	{
891	AssertPtr(pEntry->pWaitingTail);
892
893	pEntry->pWaitingTail->pNext = pSeg;
894	pEntry->pWaitingTail = pSeg;
895	}
896	else
897	{
898	Assert(!pEntry->pWaitingTail);
899
900	pEntry->pWaitingHead = pSeg;
901	pEntry->pWaitingTail = pSeg;
902	}
903	}
904
905	/**
906	* Checks that a set of flags is set/clear acquiring the R/W semaphore
907	* in exclusive mode.
908	*
909	* @returns true if the flag in fSet is set and the one in fClear is clear.
910	* false othwerise.
911	* The R/W semaphore is only held if true is returned.
912	*
913	* @param pEndpointCache The endpoint cache instance data.
914	* @param pEntry The entry to check the flags for.
915	* @param fSet The flag which is tested to be set.
916	* @param fClear The flag which is tested to be clear.
917	*/
918	DECLINLINE(bool) pdmacFileEpCacheEntryFlagIsSetClearAcquireLock(PPDMACFILEENDPOINTCACHE pEndpointCache,
919	PPDMACFILECACHEENTRY pEntry,
920	uint32_t fSet, uint32_t fClear)
921	{
922	bool fPassed = ((pEntry->fFlags & fSet) && !(pEntry->fFlags & fClear));
923
924	if (fPassed)
925	{
926	/* Acquire the lock and check again becuase the completion callback might have raced us. */
927	RTSemRWRequestWrite(pEndpointCache->SemRWEntries, RT_INDEFINITE_WAIT);
928
929	fPassed = ((pEntry->fFlags & fSet) && !(pEntry->fFlags & fClear));
930
931	/* Drop the lock if we didn't passed the test. */
932	if (!fPassed)
933	RTSemRWReleaseWrite(pEndpointCache->SemRWEntries);
934	}
935
936	return fPassed;
937	}
938
939	/**
940	* Advances the current segment buffer by the number of bytes transfered
941	* or gets the next segment.
942	*/
943	#define ADVANCE_SEGMENT_BUFFER(BytesTransfered) \
944	do \
945	{ \
946	cbSegLeft -= BytesTransfered; \
947	if (!cbSegLeft) \
948	{ \
949	iSegCurr++; \
950	cbSegLeft = paSegments[iSegCurr].cbSeg; \
951	pbSegBuf = (uint8_t *)paSegments[iSegCurr].pvSeg; \
952	} \
953	else \
954	pbSegBuf += BytesTransfered; \
955	} \
956	while (0);
957
958	/**
959	* Reads the specified data from the endpoint using the cache if possible.
960	*
961	* @returns VBox status code.
962	* @param pEndpoint The endpoint to read from.
963	* @param pTask The task structure used as identifier for this request.
964	* @param off The offset to start reading from.
965	* @param paSegments Pointer to the array holding the destination buffers.
966	* @param cSegments Number of segments in the array.
967	* @param cbRead Number of bytes to read.
968	*/
969	int pdmacFileEpCacheRead(PPDMASYNCCOMPLETIONENDPOINTFILE pEndpoint, PPDMASYNCCOMPLETIONTASKFILE pTask,
970	RTFOFF off, PCPDMDATASEG paSegments, size_t cSegments,
971	size_t cbRead)
972	{
973	int rc = VINF_SUCCESS;
974	PPDMACFILEENDPOINTCACHE pEndpointCache = &pEndpoint->DataCache;
975	PPDMACFILECACHEGLOBAL pCache = pEndpointCache->pCache;
976	PPDMACFILECACHEENTRY pEntry;
977
978	LogFlowFunc((": pEndpoint=%#p{%s} pTask=%#p off=%RTfoff paSegments=%#p cSegments=%u cbRead=%u\n",
979	pEndpoint, pEndpoint->Core.pszUri, pTask, off, paSegments, cSegments, cbRead));
980
981	pTask->cbTransferLeft = cbRead;
982	/* Set to completed to make sure that the task is valid while we access it. */
983	ASMAtomicWriteBool(&pTask->fCompleted, true);
984
985	int iSegCurr = 0;
986	uint8_t pbSegBuf = (uint8_t )paSegments[iSegCurr].pvSeg;
987	size_t cbSegLeft = paSegments[iSegCurr].cbSeg;
988
989	while (cbRead)
990	{
991	size_t cbToRead;
992
993	pEntry = pdmacFileEpCacheGetCacheEntryByOffset(pEndpointCache, off);
994
995	/*
996	* If there is no entry we try to create a new one eviciting unused pages
997	* if the cache is full. If this is not possible we will pass the request through
998	* and skip the caching (all entries may be still in progress so they can't
999	* be evicted)
1000	* If we have an entry it can be in one of the LRU lists where the entry
1001	* contains data (recently used or frequently used LRU) so we can just read
1002	* the data we need and put the entry at the head of the frequently used LRU list.
1003	* In case the entry is in one of the ghost lists it doesn't contain any data.
1004	* We have to fetch it again evicting pages from either T1 or T2 to make room.
1005	*/
1006	if (pEntry)
1007	{
1008	RTFOFF OffDiff = off - pEntry->Core.Key;
1009
1010	AssertMsg(off >= pEntry->Core.Key,
1011	("Overflow in calculation off=%RTfoff OffsetAligned=%RTfoff\n",
1012	off, pEntry->Core.Key));
1013
1014	AssertPtr(pEntry->pList);
1015
1016	cbToRead = RT_MIN(pEntry->cbData - OffDiff, cbRead);
1017	cbRead -= cbToRead;
1018
1019	if (!cbRead)
1020	STAM_COUNTER_INC(&pCache->cHits);
1021	else
1022	STAM_COUNTER_INC(&pCache->cPartialHits);
1023
1024	STAM_COUNTER_ADD(&pCache->StatRead, cbToRead);
1025
1026	/* Ghost lists contain no data. */
1027	if ( (pEntry->pList == &pCache->LruRecentlyUsed)
1028	\|\| (pEntry->pList == &pCache->LruFrequentlyUsed))
1029	{
1030	LogFlow(("Fetching data for ghost entry %#p from file\n", pEntry));
1031
1032	if (pdmacFileEpCacheEntryFlagIsSetClearAcquireLock(pEndpointCache, pEntry,
1033	PDMACFILECACHE_ENTRY_IO_IN_PROGRESS,
1034	PDMACFILECACHE_ENTRY_IS_DIRTY))
1035	{
1036	/* Entry didn't completed yet. Append to the list */
1037	while (cbToRead)
1038	{
1039	PPDMACFILETASKSEG pSeg = (PPDMACFILETASKSEG)RTMemAllocZ(sizeof(PDMACFILETASKSEG));
1040
1041	pSeg->pTask = pTask;
1042	pSeg->uBufOffset = OffDiff;
1043	pSeg->cbTransfer = RT_MIN(cbToRead, cbSegLeft);
1044	pSeg->pvBuf = pbSegBuf;
1045	pSeg->fWrite = false;
1046
1047	ADVANCE_SEGMENT_BUFFER(pSeg->cbTransfer);
1048
1049	pdmacFileEpCacheEntryAddWaitingSegment(pEntry, pSeg);
1050
1051	off += pSeg->cbTransfer;
1052	cbToRead -= pSeg->cbTransfer;
1053	OffDiff += pSeg->cbTransfer;
1054	}
1055	RTSemRWReleaseWrite(pEndpointCache->SemRWEntries);
1056	}
1057	else
1058	{
1059	/* Read as much as we can from the entry. */
1060	while (cbToRead)
1061	{
1062	size_t cbCopy = RT_MIN(cbSegLeft, cbToRead);
1063
1064	memcpy(pbSegBuf, pEntry->pbData + OffDiff, cbCopy);
1065
1066	ADVANCE_SEGMENT_BUFFER(cbCopy);
1067
1068	cbToRead -= cbCopy;
1069	off += cbCopy;
1070	OffDiff += cbCopy;
1071	ASMAtomicSubS32(&pTask->cbTransferLeft, cbCopy);
1072	}
1073	}
1074
1075	/* Move this entry to the top position */
1076	RTCritSectEnter(&pCache->CritSect);
1077	pdmacFileCacheEntryAddToList(&pCache->LruFrequentlyUsed, pEntry);
1078	RTCritSectLeave(&pCache->CritSect);
1079	}
1080	else
1081	{
1082	RTCritSectEnter(&pCache->CritSect);
1083	pdmacFileCacheUpdate(pCache, pEntry);
1084	pdmacFileCacheReplace(pCache, pEntry->cbData, pEntry->pList);
1085
1086	/* Move the entry to T2 and fetch it to the cache. */
1087	pdmacFileCacheEntryAddToList(&pCache->LruFrequentlyUsed, pEntry);
1088	RTCritSectLeave(&pCache->CritSect);
1089
1090	pEntry->pbData = (uint8_t *)RTMemPageAlloc(pEntry->cbData);
1091	AssertPtr(pEntry->pbData);
1092
1093	while (cbToRead)
1094	{
1095	PPDMACFILETASKSEG pSeg = (PPDMACFILETASKSEG)RTMemAllocZ(sizeof(PDMACFILETASKSEG));
1096
1097	AssertMsg(off >= pEntry->Core.Key,
1098	("Overflow in calculation off=%RTfoff OffsetAligned=%RTfoff\n",
1099	off, pEntry->Core.Key));
1100
1101	pSeg->pTask = pTask;
1102	pSeg->uBufOffset = OffDiff;
1103	pSeg->cbTransfer = RT_MIN(cbToRead, cbSegLeft);
1104	pSeg->pvBuf = pbSegBuf;
1105
1106	ADVANCE_SEGMENT_BUFFER(pSeg->cbTransfer);
1107
1108	pdmacFileEpCacheEntryAddWaitingSegment(pEntry, pSeg);
1109
1110	off += pSeg->cbTransfer;
1111	OffDiff += pSeg->cbTransfer;
1112	cbToRead -= pSeg->cbTransfer;
1113	}
1114
1115	pdmacFileCacheReadFromEndpoint(pEntry);
1116	}
1117	pdmacFileEpCacheEntryRelease(pEntry);
1118	}
1119	else
1120	{
1121	/* No entry found for this offset. Get best fit entry and fetch the data to the cache. */
1122	size_t cbToReadAligned;
1123	PPDMACFILECACHEENTRY pEntryBestFit = pdmacFileEpCacheGetCacheBestFitEntryByOffset(pEndpointCache, off);
1124
1125	LogFlow(("%sbest fit entry for off=%RTfoff (BestFit=%RTfoff BestFitEnd=%RTfoff BestFitSize=%u)\n",
1126	pEntryBestFit ? "" : "No ",
1127	off,
1128	pEntryBestFit ? pEntryBestFit->Core.Key : 0,
1129	pEntryBestFit ? pEntryBestFit->Core.KeyLast : 0,
1130	pEntryBestFit ? pEntryBestFit->cbData : 0));
1131
1132	if (pEntryBestFit && ((off + (RTFOFF)cbRead) > pEntryBestFit->Core.Key))
1133	{
1134	cbToRead = pEntryBestFit->Core.Key - off;
1135	pdmacFileEpCacheEntryRelease(pEntryBestFit);
1136	cbToReadAligned = cbToRead;
1137	}
1138	else
1139	{
1140	/*
1141	* Align the size to a 4KB boundary.
1142	* Memory size is aligned to a page boundary
1143	* and memory is wasted if the size is rahter small.
1144	* (For example reads with a size of 512 bytes.
1145	*/
1146	cbToRead = cbRead;
1147	cbToReadAligned = RT_ALIGN_Z(cbRead, PAGE_SIZE);
1148
1149	/* Clip read to file size */
1150	cbToReadAligned = RT_MIN(pEndpoint->cbFile - off, cbToReadAligned);
1151	if (pEntryBestFit)
1152	cbToReadAligned = RT_MIN(cbToReadAligned, pEntryBestFit->Core.Key - off);
1153	}
1154
1155	cbRead -= cbToRead;
1156
1157	if (!cbRead)
1158	STAM_COUNTER_INC(&pCache->cMisses);
1159	else
1160	STAM_COUNTER_INC(&pCache->cPartialHits);
1161
1162	RTCritSectEnter(&pCache->CritSect);
1163	size_t cbRemoved = pdmacFileCacheEvict(pCache, cbToReadAligned);
1164	RTCritSectLeave(&pCache->CritSect);
1165
1166	if (cbRemoved >= cbToReadAligned)
1167	{
1168	LogFlow(("Evicted %u bytes (%u requested). Creating new cache entry\n", cbRemoved, cbToReadAligned));
1169	PPDMACFILECACHEENTRY pEntryNew = pdmacFileCacheEntryAlloc(pCache, pEndpoint, off, cbToReadAligned);
1170	AssertPtr(pEntryNew);
1171
1172	RTCritSectEnter(&pCache->CritSect);
1173	pdmacFileCacheEntryAddToList(&pCache->LruRecentlyUsed, pEntryNew);
1174	pCache->cbCached += cbToReadAligned;
1175	RTCritSectLeave(&pCache->CritSect);
1176
1177	pdmacFileEpCacheInsertEntry(pEndpointCache, pEntryNew);
1178	uint32_t uBufOffset = 0;
1179
1180	while (cbToRead)
1181	{
1182	PPDMACFILETASKSEG pSeg = (PPDMACFILETASKSEG)RTMemAllocZ(sizeof(PDMACFILETASKSEG));
1183
1184	pSeg->pTask = pTask;
1185	pSeg->uBufOffset = uBufOffset;
1186	pSeg->cbTransfer = RT_MIN(cbToRead, cbSegLeft);
1187	pSeg->pvBuf = pbSegBuf;
1188
1189	ADVANCE_SEGMENT_BUFFER(pSeg->cbTransfer);
1190
1191	pdmacFileEpCacheEntryAddWaitingSegment(pEntryNew, pSeg);
1192
1193	off += pSeg->cbTransfer;
1194	cbToRead -= pSeg->cbTransfer;
1195	uBufOffset += pSeg->cbTransfer;
1196	}
1197
1198	pdmacFileCacheReadFromEndpoint(pEntryNew);
1199	pdmacFileEpCacheEntryRelease(pEntryNew); /* it is protected by the I/O in progress flag now. */
1200	}
1201	else
1202	{
1203	/*
1204	* There is not enough free space in the cache.
1205	* Pass the request directly to the I/O manager.
1206	*/
1207	LogFlow(("Couldn't evict %u bytes from the cache (%u actually removed). Remaining request will be passed through\n", cbToRead, cbRemoved));
1208
1209	while (cbToRead)
1210	{
1211	PPDMACTASKFILE pIoTask = pdmacFileTaskAlloc(pEndpoint);
1212	AssertPtr(pIoTask);
1213
1214	pIoTask->pEndpoint = pEndpoint;
1215	pIoTask->enmTransferType = PDMACTASKFILETRANSFER_READ;
1216	pIoTask->Off = off;
1217	pIoTask->DataSeg.cbSeg = RT_MIN(cbToRead, cbSegLeft);
1218	pIoTask->DataSeg.pvSeg = pbSegBuf;
1219	pIoTask->pvUser = pTask;
1220	pIoTask->pfnCompleted = pdmacFileEpTaskCompleted;
1221
1222	off += pIoTask->DataSeg.cbSeg;
1223	cbToRead -= pIoTask->DataSeg.cbSeg;
1224
1225	ADVANCE_SEGMENT_BUFFER(pIoTask->DataSeg.cbSeg);
1226
1227	/* Send it off to the I/O manager. */
1228	pdmacFileEpAddTask(pEndpoint, pIoTask);
1229	}
1230	}
1231	}
1232	}
1233
1234	ASMAtomicWriteBool(&pTask->fCompleted, false);
1235
1236	if (ASMAtomicReadS32(&pTask->cbTransferLeft) == 0
1237	&& !ASMAtomicXchgBool(&pTask->fCompleted, true))
1238	pdmR3AsyncCompletionCompleteTask(&pTask->Core);
1239
1240	return rc;
1241	}
1242
1243	/**
1244	* Writes the given data to the endpoint using the cache if possible.
1245	*
1246	* @returns VBox status code.
1247	* @param pEndpoint The endpoint to write to.
1248	* @param pTask The task structure used as identifier for this request.
1249	* @param off The offset to start writing to
1250	* @param paSegments Pointer to the array holding the source buffers.
1251	* @param cSegments Number of segments in the array.
1252	* @param cbWrite Number of bytes to write.
1253	*/
1254	int pdmacFileEpCacheWrite(PPDMASYNCCOMPLETIONENDPOINTFILE pEndpoint, PPDMASYNCCOMPLETIONTASKFILE pTask,
1255	RTFOFF off, PCPDMDATASEG paSegments, size_t cSegments,
1256	size_t cbWrite)
1257	{
1258	int rc = VINF_SUCCESS;
1259	PPDMACFILEENDPOINTCACHE pEndpointCache = &pEndpoint->DataCache;
1260	PPDMACFILECACHEGLOBAL pCache = pEndpointCache->pCache;
1261	PPDMACFILECACHEENTRY pEntry;
1262
1263	LogFlowFunc((": pEndpoint=%#p{%s} pTask=%#p off=%RTfoff paSegments=%#p cSegments=%u cbWrite=%u\n",
1264	pEndpoint, pEndpoint->Core.pszUri, pTask, off, paSegments, cSegments, cbWrite));
1265
1266	pTask->cbTransferLeft = cbWrite;
1267	/* Set to completed to make sure that the task is valid while we access it. */
1268	ASMAtomicWriteBool(&pTask->fCompleted, true);
1269
1270	int iSegCurr = 0;
1271	uint8_t pbSegBuf = (uint8_t )paSegments[iSegCurr].pvSeg;
1272	size_t cbSegLeft = paSegments[iSegCurr].cbSeg;
1273
1274	while (cbWrite)
1275	{
1276	size_t cbToWrite;
1277
1278	pEntry = pdmacFileEpCacheGetCacheEntryByOffset(pEndpointCache, off);
1279
1280	if (pEntry)
1281	{
1282	/* Write the data into the entry and mark it as dirty */
1283	AssertPtr(pEntry->pList);
1284
1285	RTFOFF OffDiff = off - pEntry->Core.Key;
1286
1287	AssertMsg(off >= pEntry->Core.Key,
1288	("Overflow in calculation off=%RTfoff OffsetAligned=%RTfoff\n",
1289	off, pEntry->Core.Key));
1290
1291	cbToWrite = RT_MIN(pEntry->cbData - OffDiff, cbWrite);
1292	cbWrite -= cbToWrite;
1293
1294	if (!cbWrite)
1295	STAM_COUNTER_INC(&pCache->cHits);
1296	else
1297	STAM_COUNTER_INC(&pCache->cPartialHits);
1298
1299	STAM_COUNTER_ADD(&pCache->StatWritten, cbToWrite);
1300
1301	/* Ghost lists contain no data. */
1302	if ( (pEntry->pList == &pCache->LruRecentlyUsed)
1303	\|\| (pEntry->pList == &pCache->LruFrequentlyUsed))
1304	{
1305
1306	/* If the entry is dirty it must be also in progress now and we have to defer updating it again. */
1307	if(pdmacFileEpCacheEntryFlagIsSetClearAcquireLock(pEndpointCache, pEntry,
1308	PDMACFILECACHE_ENTRY_IS_DIRTY,
1309	0))
1310	{
1311	AssertMsg(pEntry->fFlags & PDMACFILECACHE_ENTRY_IO_IN_PROGRESS,
1312	("Entry is dirty but not in progress\n"));
1313
1314	/* The data isn't written to the file yet */
1315	while (cbToWrite)
1316	{
1317	PPDMACFILETASKSEG pSeg = (PPDMACFILETASKSEG)RTMemAllocZ(sizeof(PDMACFILETASKSEG));
1318
1319	pSeg->pTask = pTask;
1320	pSeg->uBufOffset = OffDiff;
1321	pSeg->cbTransfer = RT_MIN(cbToWrite, cbSegLeft);
1322	pSeg->pvBuf = pbSegBuf;
1323	pSeg->fWrite = true;
1324
1325	ADVANCE_SEGMENT_BUFFER(pSeg->cbTransfer);
1326
1327	pdmacFileEpCacheEntryAddWaitingSegment(pEntry, pSeg);
1328
1329	off += pSeg->cbTransfer;
1330	OffDiff += pSeg->cbTransfer;
1331	cbToWrite -= pSeg->cbTransfer;
1332	}
1333	STAM_COUNTER_INC(&pEndpointCache->StatWriteDeferred);
1334	RTSemRWReleaseWrite(pEndpointCache->SemRWEntries);
1335	}
1336	else
1337	{
1338	/*
1339	* Check if a read is in progress for this entry.
1340	* We have to defer processing in that case.
1341	*/
1342	if(pdmacFileEpCacheEntryFlagIsSetClearAcquireLock(pEndpointCache, pEntry,
1343	PDMACFILECACHE_ENTRY_IO_IN_PROGRESS,
1344	0))
1345	{
1346	while (cbToWrite)
1347	{
1348	PPDMACFILETASKSEG pSeg = (PPDMACFILETASKSEG)RTMemAllocZ(sizeof(PDMACFILETASKSEG));
1349
1350	pSeg->pTask = pTask;
1351	pSeg->uBufOffset = OffDiff;
1352	pSeg->cbTransfer = RT_MIN(cbToWrite, cbSegLeft);
1353	pSeg->pvBuf = pbSegBuf;
1354	pSeg->fWrite = true;
1355
1356	ADVANCE_SEGMENT_BUFFER(pSeg->cbTransfer);
1357
1358	pdmacFileEpCacheEntryAddWaitingSegment(pEntry, pSeg);
1359
1360	off += pSeg->cbTransfer;
1361	OffDiff += pSeg->cbTransfer;
1362	cbToWrite -= pSeg->cbTransfer;
1363	}
1364	STAM_COUNTER_INC(&pEndpointCache->StatWriteDeferred);
1365	RTSemRWReleaseWrite(pEndpointCache->SemRWEntries);
1366	}
1367	else
1368	{
1369	/* Write as much as we can into the entry and update the file. */
1370	while (cbToWrite)
1371	{
1372	size_t cbCopy = RT_MIN(cbSegLeft, cbToWrite);
1373
1374	memcpy(pEntry->pbData + OffDiff, pbSegBuf, cbCopy);
1375
1376	ADVANCE_SEGMENT_BUFFER(cbCopy);
1377
1378	cbToWrite-= cbCopy;
1379	off += cbCopy;
1380	OffDiff += cbCopy;
1381	ASMAtomicSubS32(&pTask->cbTransferLeft, cbCopy);
1382	}
1383
1384	pEntry->fFlags \|= PDMACFILECACHE_ENTRY_IS_DIRTY;
1385	pdmacFileCacheWriteToEndpoint(pEntry);
1386	}
1387	}
1388
1389	/* Move this entry to the top position */
1390	RTCritSectEnter(&pCache->CritSect);
1391	pdmacFileCacheEntryAddToList(&pCache->LruFrequentlyUsed, pEntry);
1392	RTCritSectLeave(&pCache->CritSect);
1393	}
1394	else
1395	{
1396	RTCritSectEnter(&pCache->CritSect);
1397	pdmacFileCacheUpdate(pCache, pEntry);
1398	pdmacFileCacheReplace(pCache, pEntry->cbData, pEntry->pList);
1399
1400	/* Move the entry to T2 and fetch it to the cache. */
1401	pdmacFileCacheEntryAddToList(&pCache->LruFrequentlyUsed, pEntry);
1402	RTCritSectLeave(&pCache->CritSect);
1403
1404	pEntry->pbData = (uint8_t *)RTMemPageAlloc(pEntry->cbData);
1405	AssertPtr(pEntry->pbData);
1406
1407	while (cbToWrite)
1408	{
1409	PPDMACFILETASKSEG pSeg = (PPDMACFILETASKSEG)RTMemAllocZ(sizeof(PDMACFILETASKSEG));
1410
1411	AssertMsg(off >= pEntry->Core.Key,
1412	("Overflow in calculation off=%RTfoff OffsetAligned=%RTfoff\n",
1413	off, pEntry->Core.Key));
1414
1415	pSeg->pTask = pTask;
1416	pSeg->uBufOffset = OffDiff;
1417	pSeg->cbTransfer = RT_MIN(cbToWrite, cbSegLeft);
1418	pSeg->pvBuf = pbSegBuf;
1419	pSeg->fWrite = true;
1420
1421	ADVANCE_SEGMENT_BUFFER(pSeg->cbTransfer);
1422
1423	pdmacFileEpCacheEntryAddWaitingSegment(pEntry, pSeg);
1424
1425	off += pSeg->cbTransfer;
1426	OffDiff += pSeg->cbTransfer;
1427	cbToWrite -= pSeg->cbTransfer;
1428	}
1429
1430	STAM_COUNTER_INC(&pEndpointCache->StatWriteDeferred);
1431	pdmacFileCacheReadFromEndpoint(pEntry);
1432	}
1433
1434	/* Release the reference. If it is still needed the I/O in progress flag should protect it now. */
1435	pdmacFileEpCacheEntryRelease(pEntry);
1436	}
1437	else
1438	{
1439	/*
1440	* No entry found. Try to create a new cache entry to store the data in and if that fails
1441	* write directly to the file.
1442	*/
1443	PPDMACFILECACHEENTRY pEntryBestFit = pdmacFileEpCacheGetCacheBestFitEntryByOffset(pEndpointCache, off);
1444
1445	LogFlow(("%sest fit entry for off=%RTfoff (BestFit=%RTfoff BestFitEnd=%RTfoff BestFitSize=%u)\n",
1446	pEntryBestFit ? "B" : "No b",
1447	off,
1448	pEntryBestFit ? pEntryBestFit->Core.Key : 0,
1449	pEntryBestFit ? pEntryBestFit->Core.KeyLast : 0,
1450	pEntryBestFit ? pEntryBestFit->cbData : 0));
1451
1452	if (pEntryBestFit && ((off + (RTFOFF)cbWrite) > pEntryBestFit->Core.Key))
1453	{
1454	cbToWrite = pEntryBestFit->Core.Key - off;
1455	pdmacFileEpCacheEntryRelease(pEntryBestFit);
1456	}
1457	else
1458	cbToWrite = cbWrite;
1459
1460	cbWrite -= cbToWrite;
1461
1462	STAM_COUNTER_INC(&pCache->cMisses);
1463	STAM_COUNTER_ADD(&pCache->StatWritten, cbToWrite);
1464
1465	RTCritSectEnter(&pCache->CritSect);
1466	size_t cbRemoved = pdmacFileCacheEvict(pCache, cbToWrite);
1467	RTCritSectLeave(&pCache->CritSect);
1468
1469	if (cbRemoved >= cbToWrite)
1470	{
1471	uint8_t *pbBuf;
1472	PPDMACFILECACHEENTRY pEntryNew;
1473
1474	LogFlow(("Evicted %u bytes (%u requested). Creating new cache entry\n", cbRemoved, cbToWrite));
1475
1476	pEntryNew = pdmacFileCacheEntryAlloc(pCache, pEndpoint, off, cbToWrite);
1477	AssertPtr(pEntryNew);
1478
1479	RTCritSectEnter(&pCache->CritSect);
1480	pdmacFileCacheEntryAddToList(&pCache->LruRecentlyUsed, pEntryNew);
1481	pCache->cbCached += cbToWrite;
1482	RTCritSectLeave(&pCache->CritSect);
1483
1484	pdmacFileEpCacheInsertEntry(pEndpointCache, pEntryNew);
1485
1486	off += cbToWrite;
1487	pbBuf = pEntryNew->pbData;
1488
1489	while (cbToWrite)
1490	{
1491	size_t cbCopy = RT_MIN(cbSegLeft, cbToWrite);
1492
1493	memcpy(pbBuf, pbSegBuf, cbCopy);
1494
1495	ADVANCE_SEGMENT_BUFFER(cbCopy);
1496
1497	cbToWrite -= cbCopy;
1498	pbBuf += cbCopy;
1499	ASMAtomicSubS32(&pTask->cbTransferLeft, cbCopy);
1500	}
1501
1502	pEntryNew->fFlags \|= PDMACFILECACHE_ENTRY_IS_DIRTY;
1503	pdmacFileCacheWriteToEndpoint(pEntryNew);
1504	pdmacFileEpCacheEntryRelease(pEntryNew); /* it is protected by the I/O in progress flag now. */
1505	}
1506	else
1507	{
1508	/*
1509	* There is not enough free space in the cache.
1510	* Pass the request directly to the I/O manager.
1511	*/
1512	LogFlow(("Couldn't evict %u bytes from the cache (%u actually removed). Remaining request will be passed through\n", cbToWrite, cbRemoved));
1513
1514	while (cbToWrite)
1515	{
1516	PPDMACTASKFILE pIoTask = pdmacFileTaskAlloc(pEndpoint);
1517	AssertPtr(pIoTask);
1518
1519	pIoTask->pEndpoint = pEndpoint;
1520	pIoTask->enmTransferType = PDMACTASKFILETRANSFER_WRITE;
1521	pIoTask->Off = off;
1522	pIoTask->DataSeg.cbSeg = RT_MIN(cbToWrite, cbSegLeft);
1523	pIoTask->DataSeg.pvSeg = pbSegBuf;
1524	pIoTask->pvUser = pTask;
1525	pIoTask->pfnCompleted = pdmacFileEpTaskCompleted;
1526
1527	off += pIoTask->DataSeg.cbSeg;
1528	cbToWrite -= pIoTask->DataSeg.cbSeg;
1529
1530	ADVANCE_SEGMENT_BUFFER(pIoTask->DataSeg.cbSeg);
1531
1532	/* Send it off to the I/O manager. */
1533	pdmacFileEpAddTask(pEndpoint, pIoTask);
1534	}
1535	}
1536	}
1537	}
1538
1539	ASMAtomicWriteBool(&pTask->fCompleted, false);
1540
1541	if (ASMAtomicReadS32(&pTask->cbTransferLeft) == 0
1542	&& !ASMAtomicXchgBool(&pTask->fCompleted, true))
1543	pdmR3AsyncCompletionCompleteTask(&pTask->Core);
1544
1545	return VINF_SUCCESS;
1546	}
1547
1548	#undef ADVANCE_SEGMENT_BUFFER
1549

Note: See TracBrowser for help on using the repository browser.

source: vbox/trunk/src/VBox/VMM/PDMAsyncCompletionFileCache.cpp@ 24350

Download in other formats: