PDMAsyncCompletionFileCache.cpp@ 22898

Last change on this file since 22898 was 22851, checked in by vboxsync, 15 years ago
Fixes for async I/O manager
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 52.3 KB

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

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

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

Download in other formats: