PDMAsyncCompletionFileCache.cpp@ 25045

Last change on this file since 25045 was 24708, checked in by vboxsync, 15 years ago
AsyncCompletion: Remove the entry from the endpoint where it belongs to and not the current endpoint. Fixes weird crashes with multiple images
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 74.5 KB

Line
1	/* $Id: PDMAsyncCompletionFileCache.cpp 24708 2009-11-16 18:18:53Z 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	#define RT_STRICT
48	#include <iprt/types.h>
49	#include <iprt/mem.h>
50	#include <iprt/path.h>
51	#include <VBox/log.h>
52	#include <VBox/stam.h>
53
54	#include "PDMAsyncCompletionFileInternal.h"
55
56	#ifdef VBOX_STRICT
57	# define PDMACFILECACHE_IS_CRITSECT_OWNER(Cache) \
58	do \
59	{ \
60	AssertMsg(RTCritSectIsOwner(&pCache->CritSect), \
61	("Thread does not own critical section\n"));\
62	} while(0);
63	#else
64	# define PDMACFILECACHE_IS_CRITSECT_OWNER(Cache) do { } while(0);
65	#endif
66
67	/*******************************************************************************
68	* Internal Functions *
69	*******************************************************************************/
70	static void pdmacFileCacheTaskCompleted(PPDMACTASKFILE pTask, void *pvUser);
71
72	DECLINLINE(void) pdmacFileEpCacheEntryRelease(PPDMACFILECACHEENTRY pEntry)
73	{
74	AssertMsg(pEntry->cRefs > 0, ("Trying to release a not referenced entry\n"));
75	ASMAtomicDecU32(&pEntry->cRefs);
76	}
77
78	DECLINLINE(void) pdmacFileEpCacheEntryRef(PPDMACFILECACHEENTRY pEntry)
79	{
80	ASMAtomicIncU32(&pEntry->cRefs);
81	}
82
83	/**
84	* Checks consistency of a LRU list.
85	*
86	* @returns nothing
87	* @param pList The LRU list to check.
88	* @param pNotInList Element which is not allowed to occur in the list.
89	*/
90	static void pdmacFileCacheCheckList(PPDMACFILELRULIST pList, PPDMACFILECACHEENTRY pNotInList)
91	{
92	#ifdef PDMACFILECACHE_WITH_LRULIST_CHECKS
93	PPDMACFILECACHEENTRY pCurr = pList->pHead;
94
95	/* Check that there are no double entries and no cycles in the list. */
96	while (pCurr)
97	{
98	PPDMACFILECACHEENTRY pNext = pCurr->pNext;
99
100	while (pNext)
101	{
102	AssertMsg(pCurr != pNext,
103	("Entry %#p is at least two times in list %#p or there is a cycle in the list\n",
104	pCurr, pList));
105	pNext = pNext->pNext;
106	}
107
108	AssertMsg(pCurr != pNotInList, ("Not allowed entry %#p is in list\n", pCurr));
109
110	if (!pCurr->pNext)
111	AssertMsg(pCurr == pList->pTail, ("End of list reached but last element is not list tail\n"));
112
113	pCurr = pCurr->pNext;
114	}
115	#endif
116	}
117
118	/**
119	* Unlinks a cache entry from the LRU list it is assigned to.
120	*
121	* @returns nothing.
122	* @param pEntry The entry to unlink.
123	*/
124	static void pdmacFileCacheEntryRemoveFromList(PPDMACFILECACHEENTRY pEntry)
125	{
126	PPDMACFILELRULIST pList = pEntry->pList;
127	PPDMACFILECACHEENTRY pPrev, pNext;
128
129	LogFlowFunc((": Deleting entry %#p from list %#p\n", pEntry, pList));
130
131	AssertPtr(pList);
132	pdmacFileCacheCheckList(pList, NULL);
133
134	pPrev = pEntry->pPrev;
135	pNext = pEntry->pNext;
136
137	AssertMsg(pEntry != pPrev, ("Entry links to itself as previous element\n"));
138	AssertMsg(pEntry != pNext, ("Entry links to itself as next element\n"));
139
140	if (pPrev)
141	pPrev->pNext = pNext;
142	else
143	{
144	pList->pHead = pNext;
145
146	if (pNext)
147	pNext->pPrev = NULL;
148	}
149
150	if (pNext)
151	pNext->pPrev = pPrev;
152	else
153	{
154	pList->pTail = pPrev;
155
156	if (pPrev)
157	pPrev->pNext = NULL;
158	}
159
160	pEntry->pList = NULL;
161	pEntry->pPrev = NULL;
162	pEntry->pNext = NULL;
163	pList->cbCached -= pEntry->cbData;
164	pdmacFileCacheCheckList(pList, pEntry);
165	}
166
167	/**
168	* Adds a cache entry to the given LRU list unlinking it from the currently
169	* assigned list if needed.
170	*
171	* @returns nothing.
172	* @param pList List to the add entry to.
173	* @param pEntry Entry to add.
174	*/
175	static void pdmacFileCacheEntryAddToList(PPDMACFILELRULIST pList, PPDMACFILECACHEENTRY pEntry)
176	{
177	LogFlowFunc((": Adding entry %#p to list %#p\n", pEntry, pList));
178	pdmacFileCacheCheckList(pList, NULL);
179
180	/* Remove from old list if needed */
181	if (pEntry->pList)
182	pdmacFileCacheEntryRemoveFromList(pEntry);
183
184	pEntry->pNext = pList->pHead;
185	if (pList->pHead)
186	pList->pHead->pPrev = pEntry;
187	else
188	{
189	Assert(!pList->pTail);
190	pList->pTail = pEntry;
191	}
192
193	pEntry->pPrev = NULL;
194	pList->pHead = pEntry;
195	pList->cbCached += pEntry->cbData;
196	pEntry->pList = pList;
197	pdmacFileCacheCheckList(pList, NULL);
198	}
199
200	/**
201	* Destroys a LRU list freeing all entries.
202	*
203	* @returns nothing
204	* @param pList Pointer to the LRU list to destroy.
205	*
206	* @note The caller must own the critical section of the cache.
207	*/
208	static void pdmacFileCacheDestroyList(PPDMACFILELRULIST pList)
209	{
210	while (pList->pHead)
211	{
212	PPDMACFILECACHEENTRY pEntry = pList->pHead;
213
214	pList->pHead = pEntry->pNext;
215
216	AssertMsg(!(pEntry->fFlags & (PDMACFILECACHE_ENTRY_IO_IN_PROGRESS \| PDMACFILECACHE_ENTRY_IS_DIRTY)),
217	("Entry is dirty and/or still in progress fFlags=%#x\n", pEntry->fFlags));
218
219	RTMemPageFree(pEntry->pbData);
220	RTMemFree(pEntry);
221	}
222	}
223
224	/**
225	* Tries to remove the given amount of bytes from a given list in the cache
226	* moving the entries to one of the given ghosts lists
227	*
228	* @returns Amount of data which could be freed.
229	* @param pCache Pointer to the global cache data.
230	* @param cbData The amount of the data to free.
231	* @param pListSrc The source list to evict data from.
232	* @param pGhostListSrc The ghost list removed entries should be moved to
233	* NULL if the entry should be freed.
234	* @param fReuseBuffer Flag whether a buffer should be reused if it has the same size
235	* @param ppbBuf Where to store the address of the buffer if an entry with the
236	* same size was found and fReuseBuffer is true.
237	*
238	* @notes This function may return fewer bytes than requested because entries
239	* may be marked as non evictable if they are used for I/O at the moment.
240	*/
241	static size_t pdmacFileCacheEvictPagesFrom(PPDMACFILECACHEGLOBAL pCache, size_t cbData,
242	PPDMACFILELRULIST pListSrc, PPDMACFILELRULIST pGhostListDst,
243	bool fReuseBuffer, uint8_t **ppbBuffer)
244	{
245	size_t cbEvicted = 0;
246
247	PDMACFILECACHE_IS_CRITSECT_OWNER(pCache);
248
249	AssertMsg(cbData > 0, ("Evicting 0 bytes not possible\n"));
250	#ifdef VBOX_WITH_2Q_CACHE
251	AssertMsg( !pGhostListDst
252	\|\| (pGhostListDst == &pCache->LruRecentlyUsedOut),
253	("Destination list must be NULL or the recently used but paged out list\n"));
254	#else
255	AssertMsg( !pGhostListDst
256	\|\| (pGhostListDst == &pCache->LruRecentlyGhost)
257	\|\| (pGhostListDst == &pCache->LruFrequentlyGhost),
258	("Destination list must be NULL or one of the ghost lists\n"));
259	#endif
260
261	if (fReuseBuffer)
262	{
263	AssertPtr(ppbBuffer);
264	*ppbBuffer = NULL;
265	}
266
267	/* Start deleting from the tail. */
268	PPDMACFILECACHEENTRY pEntry = pListSrc->pTail;
269
270	while ((cbEvicted < cbData) && pEntry)
271	{
272	PPDMACFILECACHEENTRY pCurr = pEntry;
273
274	pEntry = pEntry->pPrev;
275
276	/* We can't evict pages which are currently in progress */
277	if (!(pCurr->fFlags & PDMACFILECACHE_ENTRY_IO_IN_PROGRESS)
278	&& (ASMAtomicReadU32(&pCurr->cRefs) == 0))
279	{
280	/* Ok eviction candidate. Grab the endpoint semaphore and check again
281	* because somebody else might have raced us. */
282	PPDMACFILEENDPOINTCACHE pEndpointCache = &pCurr->pEndpoint->DataCache;
283	RTSemRWRequestWrite(pEndpointCache->SemRWEntries, RT_INDEFINITE_WAIT);
284
285	if (!(pCurr->fFlags & PDMACFILECACHE_ENTRY_IO_IN_PROGRESS)
286	&& (ASMAtomicReadU32(&pCurr->cRefs) == 0))
287	{
288	AssertMsg(!(pCurr->fFlags & PDMACFILECACHE_ENTRY_IS_DEPRECATED),
289	("This entry is deprecated so it should have the I/O in progress flag set\n"));
290	Assert(!pCurr->pbDataReplace);
291
292	LogFlow(("Evicting entry %#p (%u bytes)\n", pCurr, pCurr->cbData));
293
294	if (fReuseBuffer && (pCurr->cbData == cbData))
295	{
296	STAM_COUNTER_INC(&pCache->StatBuffersReused);
297	*ppbBuffer = pCurr->pbData;
298	}
299	else if (pCurr->pbData)
300	RTMemPageFree(pCurr->pbData);
301
302	pCurr->pbData = NULL;
303	cbEvicted += pCurr->cbData;
304
305	pCache->cbCached -= pCurr->cbData;
306
307	if (pGhostListDst)
308	{
309	#ifdef VBOX_WITH_2Q_CACHE
310	/* We have to remove the last entries from the paged out list. */
311	while (pGhostListDst->cbCached > pCache->cbRecentlyUsedOutMax)
312	{
313	PPDMACFILECACHEENTRY pFree = pGhostListDst->pTail;
314	PPDMACFILEENDPOINTCACHE pEndpointCacheFree = &pFree->pEndpoint->DataCache;
315
316	RTSemRWRequestWrite(pEndpointCacheFree->SemRWEntries, RT_INDEFINITE_WAIT);
317
318	pdmacFileCacheEntryRemoveFromList(pFree);
319
320	STAM_PROFILE_ADV_START(&pCache->StatTreeRemove, Cache);
321	RTAvlrFileOffsetRemove(pEndpointCacheFree->pTree, pFree->Core.Key);
322	STAM_PROFILE_ADV_STOP(&pCache->StatTreeRemove, Cache);
323
324	RTSemRWReleaseWrite(pEndpointCacheFree->SemRWEntries);
325	RTMemFree(pFree);
326	}
327	#endif
328
329	pdmacFileCacheEntryAddToList(pGhostListDst, pCurr);
330	}
331	else
332	{
333	/* Delete the entry from the AVL tree it is assigned to. */
334	STAM_PROFILE_ADV_START(&pCache->StatTreeRemove, Cache);
335	RTAvlrFileOffsetRemove(pCurr->pEndpoint->DataCache.pTree, pCurr->Core.Key);
336	STAM_PROFILE_ADV_STOP(&pCache->StatTreeRemove, Cache);
337
338	pdmacFileCacheEntryRemoveFromList(pCurr);
339	RTMemFree(pCurr);
340	}
341	}
342	RTSemRWReleaseWrite(pEndpointCache->SemRWEntries);
343	}
344	else
345	LogFlow(("Entry %#p (%u bytes) is still in progress and can't be evicted\n", pCurr, pCurr->cbData));
346	}
347
348	return cbEvicted;
349	}
350
351	#ifdef VBOX_WITH_2Q_CACHE
352	static bool pdmacFileCacheReclaim(PPDMACFILECACHEGLOBAL pCache, size_t cbData, bool fReuseBuffer, uint8_t **ppbBuffer)
353	{
354	size_t cbRemoved = 0;
355
356	if ((pCache->cbCached + cbData) < pCache->cbMax)
357	return true;
358	else if ((pCache->LruRecentlyUsedIn.cbCached + cbData) > pCache->cbRecentlyUsedInMax)
359	{
360	/* Try to evict as many bytes as possible from A1in */
361	cbRemoved = pdmacFileCacheEvictPagesFrom(pCache, cbData, &pCache->LruRecentlyUsedIn,
362	&pCache->LruRecentlyUsedOut, fReuseBuffer, ppbBuffer);
363
364	/*
365	* If it was not possible to remove enough entries
366	* try the frequently accessed cache.
367	*/
368	if (cbRemoved < cbData)
369	{
370	Assert(!fReuseBuffer \|\| !ppbBuffer); / It is not possible that we got a buffer with the correct size but we didn't freed enough data. */
371
372	cbRemoved += pdmacFileCacheEvictPagesFrom(pCache, cbData - cbRemoved, &pCache->LruFrequentlyUsed,
373	NULL, fReuseBuffer, ppbBuffer);
374	}
375	}
376	else
377	{
378	/* We have to remove entries from frequently access list. */
379	cbRemoved = pdmacFileCacheEvictPagesFrom(pCache, cbData, &pCache->LruFrequentlyUsed,
380	NULL, fReuseBuffer, ppbBuffer);
381	}
382
383	LogFlowFunc((": removed %u bytes, requested %u\n", cbRemoved, cbData));
384	return (cbRemoved >= cbData);
385	}
386
387	#else
388
389	static size_t pdmacFileCacheReplace(PPDMACFILECACHEGLOBAL pCache, size_t cbData, PPDMACFILELRULIST pEntryList,
390	bool fReuseBuffer, uint8_t **ppbBuffer)
391	{
392	PDMACFILECACHE_IS_CRITSECT_OWNER(pCache);
393
394	if ( (pCache->LruRecentlyUsed.cbCached)
395	&& ( (pCache->LruRecentlyUsed.cbCached > pCache->uAdaptVal)
396	\|\| ( (pEntryList == &pCache->LruFrequentlyGhost)
397	&& (pCache->LruRecentlyUsed.cbCached == pCache->uAdaptVal))))
398	{
399	/* We need to remove entry size pages from T1 and move the entries to B1 */
400	return pdmacFileCacheEvictPagesFrom(pCache, cbData,
401	&pCache->LruRecentlyUsed,
402	&pCache->LruRecentlyGhost,
403	fReuseBuffer, ppbBuffer);
404	}
405	else
406	{
407	/* We need to remove entry size pages from T2 and move the entries to B2 */
408	return pdmacFileCacheEvictPagesFrom(pCache, cbData,
409	&pCache->LruFrequentlyUsed,
410	&pCache->LruFrequentlyGhost,
411	fReuseBuffer, ppbBuffer);
412	}
413	}
414
415	/**
416	* Tries to evict the given amount of the data from the cache.
417	*
418	* @returns Bytes removed.
419	* @param pCache The global cache data.
420	* @param cbData Number of bytes to evict.
421	*/
422	static size_t pdmacFileCacheEvict(PPDMACFILECACHEGLOBAL pCache, size_t cbData, bool fReuseBuffer, uint8_t **ppbBuffer)
423	{
424	size_t cbRemoved = ~0;
425
426	PDMACFILECACHE_IS_CRITSECT_OWNER(pCache);
427
428	if ((pCache->LruRecentlyUsed.cbCached + pCache->LruRecentlyGhost.cbCached) >= pCache->cbMax)
429	{
430	/* Delete desired pages from the cache. */
431	if (pCache->LruRecentlyUsed.cbCached < pCache->cbMax)
432	{
433	cbRemoved = pdmacFileCacheEvictPagesFrom(pCache, cbData,
434	&pCache->LruRecentlyGhost,
435	NULL,
436	fReuseBuffer, ppbBuffer);
437	}
438	else
439	{
440	cbRemoved = pdmacFileCacheEvictPagesFrom(pCache, cbData,
441	&pCache->LruRecentlyUsed,
442	NULL,
443	fReuseBuffer, ppbBuffer);
444	}
445	}
446	else
447	{
448	uint32_t cbUsed = pCache->LruRecentlyUsed.cbCached + pCache->LruRecentlyGhost.cbCached +
449	pCache->LruFrequentlyUsed.cbCached + pCache->LruFrequentlyGhost.cbCached;
450
451	if (cbUsed >= pCache->cbMax)
452	{
453	if (cbUsed == 2*pCache->cbMax)
454	cbRemoved = pdmacFileCacheEvictPagesFrom(pCache, cbData,
455	&pCache->LruFrequentlyGhost,
456	NULL,
457	fReuseBuffer, ppbBuffer);
458
459	if (cbRemoved >= cbData)
460	cbRemoved = pdmacFileCacheReplace(pCache, cbData, NULL, fReuseBuffer, ppbBuffer);
461	}
462	}
463
464	return cbRemoved;
465	}
466
467	/**
468	* Updates the cache parameters
469	*
470	* @returns nothing.
471	* @param pCache The global cache data.
472	* @param pEntry The entry usign for the update.
473	*/
474	static void pdmacFileCacheUpdate(PPDMACFILECACHEGLOBAL pCache, PPDMACFILECACHEENTRY pEntry)
475	{
476	int32_t uUpdateVal = 0;
477
478	PDMACFILECACHE_IS_CRITSECT_OWNER(pCache);
479
480	/* Update parameters */
481	if (pEntry->pList == &pCache->LruRecentlyGhost)
482	{
483	if (pCache->LruRecentlyGhost.cbCached >= pCache->LruFrequentlyGhost.cbCached)
484	uUpdateVal = 1;
485	else
486	uUpdateVal = pCache->LruFrequentlyGhost.cbCached / pCache->LruRecentlyGhost.cbCached;
487
488	pCache->uAdaptVal = RT_MIN(pCache->uAdaptVal + uUpdateVal, pCache->cbMax);
489	}
490	else if (pEntry->pList == &pCache->LruFrequentlyGhost)
491	{
492	if (pCache->LruFrequentlyGhost.cbCached >= pCache->LruRecentlyGhost.cbCached)
493	uUpdateVal = 1;
494	else
495	uUpdateVal = pCache->LruRecentlyGhost.cbCached / pCache->LruFrequentlyGhost.cbCached;
496
497	pCache->uAdaptVal = RT_MIN(pCache->uAdaptVal - uUpdateVal, 0);
498	}
499	else
500	AssertMsgFailed(("Invalid list type\n"));
501	}
502	#endif
503
504	/**
505	* Initiates a read I/O task for the given entry.
506	*
507	* @returns nothing.
508	* @param pEntry The entry to fetch the data to.
509	*/
510	static void pdmacFileCacheReadFromEndpoint(PPDMACFILECACHEENTRY pEntry)
511	{
512	LogFlowFunc((": Reading data into cache entry %#p\n", pEntry));
513
514	/* Make sure no one evicts the entry while it is accessed. */
515	pEntry->fFlags \|= PDMACFILECACHE_ENTRY_IO_IN_PROGRESS;
516
517	PPDMACTASKFILE pIoTask = pdmacFileTaskAlloc(pEntry->pEndpoint);
518	AssertPtr(pIoTask);
519
520	AssertMsg(pEntry->pbData, ("Entry is in ghost state\n"));
521
522	pIoTask->pEndpoint = pEntry->pEndpoint;
523	pIoTask->enmTransferType = PDMACTASKFILETRANSFER_READ;
524	pIoTask->Off = pEntry->Core.Key;
525	pIoTask->DataSeg.cbSeg = pEntry->cbData;
526	pIoTask->DataSeg.pvSeg = pEntry->pbData;
527	pIoTask->pvUser = pEntry;
528	pIoTask->pfnCompleted = pdmacFileCacheTaskCompleted;
529
530	/* Send it off to the I/O manager. */
531	pdmacFileEpAddTask(pEntry->pEndpoint, pIoTask);
532	}
533
534	/**
535	* Initiates a write I/O task for the given entry.
536	*
537	* @returns nothing.
538	* @param pEntry The entry to read the data from.
539	*/
540	static void pdmacFileCacheWriteToEndpoint(PPDMACFILECACHEENTRY pEntry)
541	{
542	LogFlowFunc((": Writing data from cache entry %#p\n", pEntry));
543
544	/* Make sure no one evicts the entry while it is accessed. */
545	pEntry->fFlags \|= PDMACFILECACHE_ENTRY_IO_IN_PROGRESS;
546
547	PPDMACTASKFILE pIoTask = pdmacFileTaskAlloc(pEntry->pEndpoint);
548	AssertPtr(pIoTask);
549
550	AssertMsg(pEntry->pbData, ("Entry is in ghost state\n"));
551
552	pIoTask->pEndpoint = pEntry->pEndpoint;
553	pIoTask->enmTransferType = PDMACTASKFILETRANSFER_WRITE;
554	pIoTask->Off = pEntry->Core.Key;
555	pIoTask->DataSeg.cbSeg = pEntry->cbData;
556	pIoTask->DataSeg.pvSeg = pEntry->pbData;
557	pIoTask->pvUser = pEntry;
558	pIoTask->pfnCompleted = pdmacFileCacheTaskCompleted;
559
560	/* Send it off to the I/O manager. */
561	pdmacFileEpAddTask(pEntry->pEndpoint, pIoTask);
562	}
563
564	/**
565	* Completion callback for I/O tasks.
566	*
567	* @returns nothing.
568	* @param pTask The completed task.
569	* @param pvUser Opaque user data.
570	*/
571	static void pdmacFileCacheTaskCompleted(PPDMACTASKFILE pTask, void *pvUser)
572	{
573	PPDMACFILECACHEENTRY pEntry = (PPDMACFILECACHEENTRY)pvUser;
574	PPDMACFILECACHEGLOBAL pCache = pEntry->pCache;
575	PPDMASYNCCOMPLETIONENDPOINTFILE pEndpoint = pEntry->pEndpoint;
576	PPDMACFILEENDPOINTCACHE pEndpointCache = &pEndpoint->DataCache;
577
578	/* Reference the entry now as we are clearing the I/O in progres flag
579	* which protects the entry till now. */
580	pdmacFileEpCacheEntryRef(pEntry);
581
582	RTSemRWRequestWrite(pEndpoint->DataCache.SemRWEntries, RT_INDEFINITE_WAIT);
583	pEntry->fFlags &= ~PDMACFILECACHE_ENTRY_IO_IN_PROGRESS;
584
585	/* Process waiting segment list. The data in entry might have changed inbetween. */
586	PPDMACFILETASKSEG pCurr = pEntry->pWaitingHead;
587
588	AssertMsg((pCurr && pEntry->pWaitingTail) \|\| (!pCurr && !pEntry->pWaitingTail),
589	("The list tail was not updated correctly\n"));
590	pEntry->pWaitingTail = NULL;
591	pEntry->pWaitingHead = NULL;
592
593	if (pTask->enmTransferType == PDMACTASKFILETRANSFER_WRITE)
594	{
595	if (pEntry->fFlags & PDMACFILECACHE_ENTRY_IS_DEPRECATED)
596	{
597	AssertMsg(!pCurr, ("The entry is deprecated but has waiting write segments attached\n"));
598
599	RTMemPageFree(pEntry->pbData);
600	pEntry->pbData = pEntry->pbDataReplace;
601	pEntry->pbDataReplace = NULL;
602	pEntry->fFlags &= ~PDMACFILECACHE_ENTRY_IS_DEPRECATED;
603	}
604	else
605	{
606	pEntry->fFlags &= ~PDMACFILECACHE_ENTRY_IS_DIRTY;
607
608	while (pCurr)
609	{
610	AssertMsg(pCurr->fWrite, ("Completed write entries should never have read tasks attached\n"));
611
612	memcpy(pEntry->pbData + pCurr->uBufOffset, pCurr->pvBuf, pCurr->cbTransfer);
613	pEntry->fFlags \|= PDMACFILECACHE_ENTRY_IS_DIRTY;
614
615	uint32_t uOld = ASMAtomicSubU32(&pCurr->pTask->cbTransferLeft, pCurr->cbTransfer);
616	AssertMsg(uOld >= pCurr->cbTransfer, ("New value would overflow\n"));
617	if (!(uOld - pCurr->cbTransfer)
618	&& !ASMAtomicXchgBool(&pCurr->pTask->fCompleted, true))
619	pdmR3AsyncCompletionCompleteTask(&pCurr->pTask->Core);
620
621	PPDMACFILETASKSEG pFree = pCurr;
622	pCurr = pCurr->pNext;
623
624	RTMemFree(pFree);
625	}
626	}
627	}
628	else
629	{
630	AssertMsg(pTask->enmTransferType == PDMACTASKFILETRANSFER_READ, ("Invalid transfer type\n"));
631	AssertMsg(!(pEntry->fFlags & PDMACFILECACHE_ENTRY_IS_DIRTY),("Invalid flags set\n"));
632
633	while (pCurr)
634	{
635	if (pCurr->fWrite)
636	{
637	memcpy(pEntry->pbData + pCurr->uBufOffset, pCurr->pvBuf, pCurr->cbTransfer);
638	pEntry->fFlags \|= PDMACFILECACHE_ENTRY_IS_DIRTY;
639	}
640	else
641	memcpy(pCurr->pvBuf, pEntry->pbData + pCurr->uBufOffset, pCurr->cbTransfer);
642
643	uint32_t uOld = ASMAtomicSubU32(&pCurr->pTask->cbTransferLeft, pCurr->cbTransfer);
644	AssertMsg(uOld >= pCurr->cbTransfer, ("New value would overflow\n"));
645	if (!(uOld - pCurr->cbTransfer)
646	&& !ASMAtomicXchgBool(&pCurr->pTask->fCompleted, true))
647	pdmR3AsyncCompletionCompleteTask(&pCurr->pTask->Core);
648
649	PPDMACFILETASKSEG pFree = pCurr;
650	pCurr = pCurr->pNext;
651
652	RTMemFree(pFree);
653	}
654	}
655
656	if (pEntry->fFlags & PDMACFILECACHE_ENTRY_IS_DIRTY)
657	pdmacFileCacheWriteToEndpoint(pEntry);
658
659	RTSemRWReleaseWrite(pEndpoint->DataCache.SemRWEntries);
660
661	/* Dereference so that it isn't protected anymore except we issued anyother write for it. */
662	pdmacFileEpCacheEntryRelease(pEntry);
663	}
664
665	/**
666	* Initializies the I/O cache.
667	*
668	* returns VBox status code.
669	* @param pClassFile The global class data for file endpoints.
670	* @param pCfgNode CFGM node to query configuration data from.
671	*/
672	int pdmacFileCacheInit(PPDMASYNCCOMPLETIONEPCLASSFILE pClassFile, PCFGMNODE pCfgNode)
673	{
674	int rc = VINF_SUCCESS;
675	PPDMACFILECACHEGLOBAL pCache = &pClassFile->Cache;
676
677	rc = CFGMR3QueryU32Def(pCfgNode, "CacheSize", &pCache->cbMax, 5 * _1M);
678	AssertLogRelRCReturn(rc, rc);
679
680	pCache->cbCached = 0;
681	LogFlowFunc((": Maximum number of bytes cached %u\n", pCache->cbMax));
682
683	/* Initialize members */
684	#ifdef VBOX_WITH_2Q_CACHE
685	pCache->LruRecentlyUsedIn.pHead = NULL;
686	pCache->LruRecentlyUsedIn.pTail = NULL;
687	pCache->LruRecentlyUsedIn.cbCached = 0;
688
689	pCache->LruRecentlyUsedOut.pHead = NULL;
690	pCache->LruRecentlyUsedOut.pTail = NULL;
691	pCache->LruRecentlyUsedOut.cbCached = 0;
692
693	pCache->LruFrequentlyUsed.pHead = NULL;
694	pCache->LruFrequentlyUsed.pTail = NULL;
695	pCache->LruFrequentlyUsed.cbCached = 0;
696
697	pCache->cbRecentlyUsedInMax = (pCache->cbMax / 100) * 25; /* 25% of the buffer size */
698	pCache->cbRecentlyUsedOutMax = (pCache->cbMax / 100) * 50; /* 50% of the buffer size */
699	LogFlowFunc((": cbRecentlyUsedInMax=%u cbRecentlyUsedOutMax=%u\n", pCache->cbRecentlyUsedInMax, pCache->cbRecentlyUsedOutMax));
700	#else
701	pCache->LruRecentlyUsed.pHead = NULL;
702	pCache->LruRecentlyUsed.pTail = NULL;
703	pCache->LruRecentlyUsed.cbCached = 0;
704
705	pCache->LruFrequentlyUsed.pHead = NULL;
706	pCache->LruFrequentlyUsed.pTail = NULL;
707	pCache->LruFrequentlyUsed.cbCached = 0;
708
709	pCache->LruRecentlyGhost.pHead = NULL;
710	pCache->LruRecentlyGhost.pTail = NULL;
711	pCache->LruRecentlyGhost.cbCached = 0;
712
713	pCache->LruFrequentlyGhost.pHead = NULL;
714	pCache->LruFrequentlyGhost.pTail = NULL;
715	pCache->LruFrequentlyGhost.cbCached = 0;
716
717	pCache->uAdaptVal = 0;
718	#endif
719
720	STAMR3Register(pClassFile->Core.pVM, &pCache->cbMax,
721	STAMTYPE_U32, STAMVISIBILITY_ALWAYS,
722	"/PDM/AsyncCompletion/File/cbMax",
723	STAMUNIT_BYTES,
724	"Maximum cache size");
725	STAMR3Register(pClassFile->Core.pVM, &pCache->cbCached,
726	STAMTYPE_U32, STAMVISIBILITY_ALWAYS,
727	"/PDM/AsyncCompletion/File/cbCached",
728	STAMUNIT_BYTES,
729	"Currently used cache");
730	#ifdef VBOX_WITH_2Q_CACHE
731	STAMR3Register(pClassFile->Core.pVM, &pCache->LruRecentlyUsedIn.cbCached,
732	STAMTYPE_U32, STAMVISIBILITY_ALWAYS,
733	"/PDM/AsyncCompletion/File/cbCachedMruIn",
734	STAMUNIT_BYTES,
735	"Number of bytes cached in MRU list");
736	STAMR3Register(pClassFile->Core.pVM, &pCache->LruRecentlyUsedOut.cbCached,
737	STAMTYPE_U32, STAMVISIBILITY_ALWAYS,
738	"/PDM/AsyncCompletion/File/cbCachedMruOut",
739	STAMUNIT_BYTES,
740	"Number of bytes cached in FRU list");
741	STAMR3Register(pClassFile->Core.pVM, &pCache->LruFrequentlyUsed.cbCached,
742	STAMTYPE_U32, STAMVISIBILITY_ALWAYS,
743	"/PDM/AsyncCompletion/File/cbCachedFru",
744	STAMUNIT_BYTES,
745	"Number of bytes cached in FRU ghost list");
746	#else
747	STAMR3Register(pClassFile->Core.pVM, &pCache->LruRecentlyUsed.cbCached,
748	STAMTYPE_U32, STAMVISIBILITY_ALWAYS,
749	"/PDM/AsyncCompletion/File/cbCachedMru",
750	STAMUNIT_BYTES,
751	"Number of bytes cached in Mru list");
752	STAMR3Register(pClassFile->Core.pVM, &pCache->LruFrequentlyUsed.cbCached,
753	STAMTYPE_U32, STAMVISIBILITY_ALWAYS,
754	"/PDM/AsyncCompletion/File/cbCachedFru",
755	STAMUNIT_BYTES,
756	"Number of bytes cached in Fru list");
757	STAMR3Register(pClassFile->Core.pVM, &pCache->LruRecentlyGhost.cbCached,
758	STAMTYPE_U32, STAMVISIBILITY_ALWAYS,
759	"/PDM/AsyncCompletion/File/cbCachedMruGhost",
760	STAMUNIT_BYTES,
761	"Number of bytes cached in Mru ghost list");
762	STAMR3Register(pClassFile->Core.pVM, &pCache->LruFrequentlyGhost.cbCached,
763	STAMTYPE_U32, STAMVISIBILITY_ALWAYS,
764	"/PDM/AsyncCompletion/File/cbCachedFruGhost",
765	STAMUNIT_BYTES, "Number of bytes cached in Fru ghost list");
766	#endif
767
768	#ifdef VBOX_WITH_STATISTICS
769	STAMR3Register(pClassFile->Core.pVM, &pCache->cHits,
770	STAMTYPE_COUNTER, STAMVISIBILITY_ALWAYS,
771	"/PDM/AsyncCompletion/File/CacheHits",
772	STAMUNIT_COUNT, "Number of hits in the cache");
773	STAMR3Register(pClassFile->Core.pVM, &pCache->cPartialHits,
774	STAMTYPE_COUNTER, STAMVISIBILITY_ALWAYS,
775	"/PDM/AsyncCompletion/File/CachePartialHits",
776	STAMUNIT_COUNT, "Number of partial hits in the cache");
777	STAMR3Register(pClassFile->Core.pVM, &pCache->cMisses,
778	STAMTYPE_COUNTER, STAMVISIBILITY_ALWAYS,
779	"/PDM/AsyncCompletion/File/CacheMisses",
780	STAMUNIT_COUNT, "Number of misses when accessing the cache");
781	STAMR3Register(pClassFile->Core.pVM, &pCache->StatRead,
782	STAMTYPE_COUNTER, STAMVISIBILITY_ALWAYS,
783	"/PDM/AsyncCompletion/File/CacheRead",
784	STAMUNIT_BYTES, "Number of bytes read from the cache");
785	STAMR3Register(pClassFile->Core.pVM, &pCache->StatWritten,
786	STAMTYPE_COUNTER, STAMVISIBILITY_ALWAYS,
787	"/PDM/AsyncCompletion/File/CacheWritten",
788	STAMUNIT_BYTES, "Number of bytes written to the cache");
789	STAMR3Register(pClassFile->Core.pVM, &pCache->StatTreeGet,
790	STAMTYPE_PROFILE_ADV, STAMVISIBILITY_ALWAYS,
791	"/PDM/AsyncCompletion/File/CacheTreeGet",
792	STAMUNIT_TICKS_PER_CALL, "Time taken to access an entry in the tree");
793	STAMR3Register(pClassFile->Core.pVM, &pCache->StatTreeInsert,
794	STAMTYPE_PROFILE_ADV, STAMVISIBILITY_ALWAYS,
795	"/PDM/AsyncCompletion/File/CacheTreeInsert",
796	STAMUNIT_TICKS_PER_CALL, "Time taken to insert an entry in the tree");
797	STAMR3Register(pClassFile->Core.pVM, &pCache->StatTreeRemove,
798	STAMTYPE_PROFILE_ADV, STAMVISIBILITY_ALWAYS,
799	"/PDM/AsyncCompletion/File/CacheTreeRemove",
800	STAMUNIT_TICKS_PER_CALL, "Time taken to remove an entry an the tree");
801	STAMR3Register(pClassFile->Core.pVM, &pCache->StatBuffersReused,
802	STAMTYPE_COUNTER, STAMVISIBILITY_ALWAYS,
803	"/PDM/AsyncCompletion/File/CacheBuffersReused",
804	STAMUNIT_COUNT, "Number of times a buffer could be reused");
805	#ifndef VBOX_WITH_2Q_CACHE
806	STAMR3Register(pClassFile->Core.pVM, &pCache->uAdaptVal,
807	STAMTYPE_U32, STAMVISIBILITY_ALWAYS,
808	"/PDM/AsyncCompletion/File/CacheAdaptValue",
809	STAMUNIT_COUNT,
810	"Adaption value of the cache");
811	#endif
812	#endif
813
814	/* Initialize the critical section */
815	rc = RTCritSectInit(&pCache->CritSect);
816
817	if (RT_SUCCESS(rc))
818	LogRel(("AIOMgr: Cache successfully initialised. Cache size is %u bytes\n", pCache->cbMax));
819
820	return rc;
821	}
822
823	/**
824	* Destroysthe cache freeing all data.
825	*
826	* returns nothing.
827	* @param pClassFile The global class data for file endpoints.
828	*/
829	void pdmacFileCacheDestroy(PPDMASYNCCOMPLETIONEPCLASSFILE pClassFile)
830	{
831	PPDMACFILECACHEGLOBAL pCache = &pClassFile->Cache;
832
833	/* Make sure no one else uses the cache now */
834	RTCritSectEnter(&pCache->CritSect);
835
836	#ifdef VBOX_WITH_2Q_CACHE
837	/* Cleanup deleting all cache entries waiting for in progress entries to finish. */
838	pdmacFileCacheDestroyList(&pCache->LruRecentlyUsedIn);
839	pdmacFileCacheDestroyList(&pCache->LruRecentlyUsedOut);
840	pdmacFileCacheDestroyList(&pCache->LruFrequentlyUsed);
841	#else
842	/* Cleanup deleting all cache entries waiting for in progress entries to finish. */
843	pdmacFileCacheDestroyList(&pCache->LruRecentlyUsed);
844	pdmacFileCacheDestroyList(&pCache->LruFrequentlyUsed);
845	pdmacFileCacheDestroyList(&pCache->LruRecentlyGhost);
846	pdmacFileCacheDestroyList(&pCache->LruFrequentlyGhost);
847	#endif
848
849	RTCritSectLeave(&pCache->CritSect);
850
851	RTCritSectDelete(&pCache->CritSect);
852	}
853
854	/**
855	* Initializes per endpoint cache data
856	* like the AVL tree used to access cached entries.
857	*
858	* @returns VBox status code.
859	* @param pEndpoint The endpoint to init the cache for,
860	* @param pClassFile The global class data for file endpoints.
861	*/
862	int pdmacFileEpCacheInit(PPDMASYNCCOMPLETIONENDPOINTFILE pEndpoint, PPDMASYNCCOMPLETIONEPCLASSFILE pClassFile)
863	{
864	PPDMACFILEENDPOINTCACHE pEndpointCache = &pEndpoint->DataCache;
865
866	pEndpointCache->pCache = &pClassFile->Cache;
867
868	int rc = RTSemRWCreate(&pEndpointCache->SemRWEntries);
869	if (RT_SUCCESS(rc))
870	{
871	pEndpointCache->pTree = (PAVLRFOFFTREE)RTMemAllocZ(sizeof(AVLRFOFFTREE));
872	if (!pEndpointCache->pTree)
873	{
874	rc = VERR_NO_MEMORY;
875	RTSemRWDestroy(pEndpointCache->SemRWEntries);
876	}
877	}
878
879	#ifdef VBOX_WITH_STATISTICS
880	if (RT_SUCCESS(rc))
881	{
882	STAMR3RegisterF(pClassFile->Core.pVM, &pEndpointCache->StatWriteDeferred,
883	STAMTYPE_COUNTER, STAMVISIBILITY_ALWAYS,
884	STAMUNIT_COUNT, "Number of deferred writes",
885	"/PDM/AsyncCompletion/File/%s/Cache/DeferredWrites", RTPathFilename(pEndpoint->Core.pszUri));
886	}
887	#endif
888
889	return rc;
890	}
891
892	/**
893	* Callback for the AVL destroy routine. Frees a cache entry for this endpoint.
894	*
895	* @returns IPRT status code.
896	* @param pNode The node to destroy.
897	* @param pvUser Opaque user data.
898	*/
899	static int pdmacFileEpCacheEntryDestroy(PAVLRFOFFNODECORE pNode, void *pvUser)
900	{
901	PPDMACFILECACHEENTRY pEntry = (PPDMACFILECACHEENTRY)pNode;
902	PPDMACFILECACHEGLOBAL pCache = (PPDMACFILECACHEGLOBAL)pvUser;
903	PPDMACFILEENDPOINTCACHE pEndpointCache = &pEntry->pEndpoint->DataCache;
904
905	while (pEntry->fFlags & (PDMACFILECACHE_ENTRY_IO_IN_PROGRESS \| PDMACFILECACHE_ENTRY_IS_DIRTY))
906	{
907	RTSemRWReleaseWrite(pEndpointCache->SemRWEntries);
908	RTThreadSleep(250);
909	RTSemRWRequestWrite(pEndpointCache->SemRWEntries, RT_INDEFINITE_WAIT);
910	}
911
912	AssertMsg(!(pEntry->fFlags & (PDMACFILECACHE_ENTRY_IO_IN_PROGRESS \| PDMACFILECACHE_ENTRY_IS_DIRTY)),
913	("Entry is dirty and/or still in progress fFlags=%#x\n", pEntry->fFlags));
914
915	pdmacFileCacheEntryRemoveFromList(pEntry);
916	pCache->cbCached -= pEntry->cbData;
917
918	RTMemPageFree(pEntry->pbData);
919	RTMemFree(pEntry);
920
921	return VINF_SUCCESS;
922	}
923
924	/**
925	* Destroys all cache ressources used by the given endpoint.
926	*
927	* @returns nothing.
928	* @param pEndpoint The endpoint to the destroy.
929	*/
930	void pdmacFileEpCacheDestroy(PPDMASYNCCOMPLETIONENDPOINTFILE pEndpoint)
931	{
932	PPDMACFILEENDPOINTCACHE pEndpointCache = &pEndpoint->DataCache;
933	PPDMACFILECACHEGLOBAL pCache = pEndpointCache->pCache;
934
935	/* Make sure nobody is accessing the cache while we delete the tree. */
936	RTSemRWRequestWrite(pEndpointCache->SemRWEntries, RT_INDEFINITE_WAIT);
937	RTCritSectEnter(&pCache->CritSect);
938	RTAvlrFileOffsetDestroy(pEndpointCache->pTree, pdmacFileEpCacheEntryDestroy, pCache);
939	RTCritSectLeave(&pCache->CritSect);
940	RTSemRWReleaseWrite(pEndpointCache->SemRWEntries);
941
942	RTSemRWDestroy(pEndpointCache->SemRWEntries);
943
944	#ifdef VBOX_WITH_STATISTICS
945	PPDMASYNCCOMPLETIONEPCLASSFILE pEpClassFile = (PPDMASYNCCOMPLETIONEPCLASSFILE)pEndpoint->Core.pEpClass;
946
947	STAMR3Deregister(pEpClassFile->Core.pVM, &pEndpointCache->StatWriteDeferred);
948	#endif
949	}
950
951	static PPDMACFILECACHEENTRY pdmacFileEpCacheGetCacheEntryByOffset(PPDMACFILEENDPOINTCACHE pEndpointCache, RTFOFF off)
952	{
953	PPDMACFILECACHEGLOBAL pCache = pEndpointCache->pCache;
954	PPDMACFILECACHEENTRY pEntry = NULL;
955
956	STAM_PROFILE_ADV_START(&pCache->StatTreeGet, Cache);
957
958	RTSemRWRequestRead(pEndpointCache->SemRWEntries, RT_INDEFINITE_WAIT);
959	pEntry = (PPDMACFILECACHEENTRY)RTAvlrFileOffsetRangeGet(pEndpointCache->pTree, off);
960	if (pEntry)
961	pdmacFileEpCacheEntryRef(pEntry);
962	RTSemRWReleaseRead(pEndpointCache->SemRWEntries);
963
964	STAM_PROFILE_ADV_STOP(&pCache->StatTreeGet, Cache);
965
966	return pEntry;
967	}
968
969	static PPDMACFILECACHEENTRY pdmacFileEpCacheGetCacheBestFitEntryByOffset(PPDMACFILEENDPOINTCACHE pEndpointCache, RTFOFF off)
970	{
971	PPDMACFILECACHEGLOBAL pCache = pEndpointCache->pCache;
972	PPDMACFILECACHEENTRY pEntry = NULL;
973
974	STAM_PROFILE_ADV_START(&pCache->StatTreeGet, Cache);
975
976	RTSemRWRequestRead(pEndpointCache->SemRWEntries, RT_INDEFINITE_WAIT);
977	pEntry = (PPDMACFILECACHEENTRY)RTAvlrFileOffsetGetBestFit(pEndpointCache->pTree, off, true);
978	if (pEntry)
979	pdmacFileEpCacheEntryRef(pEntry);
980	RTSemRWReleaseRead(pEndpointCache->SemRWEntries);
981
982	STAM_PROFILE_ADV_STOP(&pCache->StatTreeGet, Cache);
983
984	return pEntry;
985	}
986
987	static void pdmacFileEpCacheInsertEntry(PPDMACFILEENDPOINTCACHE pEndpointCache, PPDMACFILECACHEENTRY pEntry)
988	{
989	PPDMACFILECACHEGLOBAL pCache = pEndpointCache->pCache;
990
991	STAM_PROFILE_ADV_START(&pCache->StatTreeInsert, Cache);
992	RTSemRWRequestWrite(pEndpointCache->SemRWEntries, RT_INDEFINITE_WAIT);
993	bool fInserted = RTAvlrFileOffsetInsert(pEndpointCache->pTree, &pEntry->Core);
994	AssertMsg(fInserted, ("Node was not inserted into tree\n"));
995	STAM_PROFILE_ADV_STOP(&pCache->StatTreeInsert, Cache);
996	RTSemRWReleaseWrite(pEndpointCache->SemRWEntries);
997	}
998
999	/**
1000	* Allocates and initializes a new entry for the cache.
1001	* The entry has a reference count of 1.
1002	*
1003	* @returns Pointer to the new cache entry or NULL if out of memory.
1004	* @param pCache The cache the entry belongs to.
1005	* @param pEndoint The endpoint the entry holds data for.
1006	* @param off Start offset.
1007	* @param cbData Size of the cache entry.
1008	* @param pbBuffer Pointer to the buffer to use.
1009	* NULL if a new buffer should be allocated.
1010	* The buffer needs to have the same size of the entry.
1011	*/
1012	static PPDMACFILECACHEENTRY pdmacFileCacheEntryAlloc(PPDMACFILECACHEGLOBAL pCache,
1013	PPDMASYNCCOMPLETIONENDPOINTFILE pEndpoint,
1014	RTFOFF off, size_t cbData, uint8_t *pbBuffer)
1015	{
1016	PPDMACFILECACHEENTRY pEntryNew = (PPDMACFILECACHEENTRY)RTMemAllocZ(sizeof(PDMACFILECACHEENTRY));
1017
1018	if (RT_UNLIKELY(!pEntryNew))
1019	return NULL;
1020
1021	pEntryNew->Core.Key = off;
1022	pEntryNew->Core.KeyLast = off + cbData - 1;
1023	pEntryNew->pEndpoint = pEndpoint;
1024	pEntryNew->pCache = pCache;
1025	pEntryNew->fFlags = 0;
1026	pEntryNew->cRefs = 1; /* We are using it now. */
1027	pEntryNew->pList = NULL;
1028	pEntryNew->cbData = cbData;
1029	pEntryNew->pWaitingHead = NULL;
1030	pEntryNew->pWaitingTail = NULL;
1031	pEntryNew->pbDataReplace = NULL;
1032	if (pbBuffer)
1033	pEntryNew->pbData = pbBuffer;
1034	else
1035	pEntryNew->pbData = (uint8_t *)RTMemPageAlloc(cbData);
1036
1037	if (RT_UNLIKELY(!pEntryNew->pbData))
1038	{
1039	RTMemFree(pEntryNew);
1040	return NULL;
1041	}
1042
1043	return pEntryNew;
1044	}
1045
1046	/**
1047	* Adds a segment to the waiting list for a cache entry
1048	* which is currently in progress.
1049	*
1050	* @returns nothing.
1051	* @param pEntry The cache entry to add the segment to.
1052	* @param pSeg The segment to add.
1053	*/
1054	DECLINLINE(void) pdmacFileEpCacheEntryAddWaitingSegment(PPDMACFILECACHEENTRY pEntry, PPDMACFILETASKSEG pSeg)
1055	{
1056	pSeg->pNext = NULL;
1057
1058	if (pEntry->pWaitingHead)
1059	{
1060	AssertPtr(pEntry->pWaitingTail);
1061
1062	pEntry->pWaitingTail->pNext = pSeg;
1063	pEntry->pWaitingTail = pSeg;
1064	}
1065	else
1066	{
1067	Assert(!pEntry->pWaitingTail);
1068
1069	pEntry->pWaitingHead = pSeg;
1070	pEntry->pWaitingTail = pSeg;
1071	}
1072	}
1073
1074	/**
1075	* Checks that a set of flags is set/clear acquiring the R/W semaphore
1076	* in exclusive mode.
1077	*
1078	* @returns true if the flag in fSet is set and the one in fClear is clear.
1079	* false othwerise.
1080	* The R/W semaphore is only held if true is returned.
1081	*
1082	* @param pEndpointCache The endpoint cache instance data.
1083	* @param pEntry The entry to check the flags for.
1084	* @param fSet The flag which is tested to be set.
1085	* @param fClear The flag which is tested to be clear.
1086	*/
1087	DECLINLINE(bool) pdmacFileEpCacheEntryFlagIsSetClearAcquireLock(PPDMACFILEENDPOINTCACHE pEndpointCache,
1088	PPDMACFILECACHEENTRY pEntry,
1089	uint32_t fSet, uint32_t fClear)
1090	{
1091	bool fPassed = ((pEntry->fFlags & fSet) && !(pEntry->fFlags & fClear));
1092
1093	if (fPassed)
1094	{
1095	/* Acquire the lock and check again becuase the completion callback might have raced us. */
1096	RTSemRWRequestWrite(pEndpointCache->SemRWEntries, RT_INDEFINITE_WAIT);
1097
1098	fPassed = ((pEntry->fFlags & fSet) && !(pEntry->fFlags & fClear));
1099
1100	/* Drop the lock if we didn't passed the test. */
1101	if (!fPassed)
1102	RTSemRWReleaseWrite(pEndpointCache->SemRWEntries);
1103	}
1104
1105	return fPassed;
1106	}
1107
1108	/**
1109	* Advances the current segment buffer by the number of bytes transfered
1110	* or gets the next segment.
1111	*/
1112	#define ADVANCE_SEGMENT_BUFFER(BytesTransfered) \
1113	do \
1114	{ \
1115	cbSegLeft -= BytesTransfered; \
1116	if (!cbSegLeft) \
1117	{ \
1118	iSegCurr++; \
1119	cbSegLeft = paSegments[iSegCurr].cbSeg; \
1120	pbSegBuf = (uint8_t *)paSegments[iSegCurr].pvSeg; \
1121	} \
1122	else \
1123	pbSegBuf += BytesTransfered; \
1124	} \
1125	while (0)
1126
1127	/**
1128	* Reads the specified data from the endpoint using the cache if possible.
1129	*
1130	* @returns VBox status code.
1131	* @param pEndpoint The endpoint to read from.
1132	* @param pTask The task structure used as identifier for this request.
1133	* @param off The offset to start reading from.
1134	* @param paSegments Pointer to the array holding the destination buffers.
1135	* @param cSegments Number of segments in the array.
1136	* @param cbRead Number of bytes to read.
1137	*/
1138	int pdmacFileEpCacheRead(PPDMASYNCCOMPLETIONENDPOINTFILE pEndpoint, PPDMASYNCCOMPLETIONTASKFILE pTask,
1139	RTFOFF off, PCPDMDATASEG paSegments, size_t cSegments,
1140	size_t cbRead)
1141	{
1142	int rc = VINF_SUCCESS;
1143	PPDMACFILEENDPOINTCACHE pEndpointCache = &pEndpoint->DataCache;
1144	PPDMACFILECACHEGLOBAL pCache = pEndpointCache->pCache;
1145	PPDMACFILECACHEENTRY pEntry;
1146
1147	LogFlowFunc((": pEndpoint=%#p{%s} pTask=%#p off=%RTfoff paSegments=%#p cSegments=%u cbRead=%u\n",
1148	pEndpoint, pEndpoint->Core.pszUri, pTask, off, paSegments, cSegments, cbRead));
1149
1150	pTask->cbTransferLeft = cbRead;
1151	/* Set to completed to make sure that the task is valid while we access it. */
1152	ASMAtomicWriteBool(&pTask->fCompleted, true);
1153
1154	int iSegCurr = 0;
1155	uint8_t pbSegBuf = (uint8_t )paSegments[iSegCurr].pvSeg;
1156	size_t cbSegLeft = paSegments[iSegCurr].cbSeg;
1157
1158	while (cbRead)
1159	{
1160	size_t cbToRead;
1161
1162	pEntry = pdmacFileEpCacheGetCacheEntryByOffset(pEndpointCache, off);
1163
1164	/*
1165	* If there is no entry we try to create a new one eviciting unused pages
1166	* if the cache is full. If this is not possible we will pass the request through
1167	* and skip the caching (all entries may be still in progress so they can't
1168	* be evicted)
1169	* If we have an entry it can be in one of the LRU lists where the entry
1170	* contains data (recently used or frequently used LRU) so we can just read
1171	* the data we need and put the entry at the head of the frequently used LRU list.
1172	* In case the entry is in one of the ghost lists it doesn't contain any data.
1173	* We have to fetch it again evicting pages from either T1 or T2 to make room.
1174	*/
1175	if (pEntry)
1176	{
1177	RTFOFF OffDiff = off - pEntry->Core.Key;
1178
1179	AssertMsg(off >= pEntry->Core.Key,
1180	("Overflow in calculation off=%RTfoff OffsetAligned=%RTfoff\n",
1181	off, pEntry->Core.Key));
1182
1183	AssertPtr(pEntry->pList);
1184
1185	cbToRead = RT_MIN(pEntry->cbData - OffDiff, cbRead);
1186	cbRead -= cbToRead;
1187
1188	if (!cbRead)
1189	STAM_COUNTER_INC(&pCache->cHits);
1190	else
1191	STAM_COUNTER_INC(&pCache->cPartialHits);
1192
1193	STAM_COUNTER_ADD(&pCache->StatRead, cbToRead);
1194
1195	/* Ghost lists contain no data. */
1196	#ifdef VBOX_WITH_2Q_CACHE
1197	if ( (pEntry->pList == &pCache->LruRecentlyUsedIn)
1198	\|\| (pEntry->pList == &pCache->LruFrequentlyUsed))
1199	{
1200	#else
1201	if ( (pEntry->pList == &pCache->LruRecentlyUsed)
1202	\|\| (pEntry->pList == &pCache->LruFrequentlyUsed))
1203	{
1204	#endif
1205	if(pdmacFileEpCacheEntryFlagIsSetClearAcquireLock(pEndpointCache, pEntry,
1206	PDMACFILECACHE_ENTRY_IS_DEPRECATED,
1207	0))
1208	{
1209	/* Entry is deprecated. Read data from the new buffer. */
1210	while (cbToRead)
1211	{
1212	size_t cbCopy = RT_MIN(cbSegLeft, cbToRead);
1213
1214	memcpy(pbSegBuf, pEntry->pbDataReplace + OffDiff, cbCopy);
1215
1216	ADVANCE_SEGMENT_BUFFER(cbCopy);
1217
1218	cbToRead -= cbCopy;
1219	off += cbCopy;
1220	OffDiff += cbCopy;
1221	ASMAtomicSubS32(&pTask->cbTransferLeft, cbCopy);
1222	}
1223	RTSemRWReleaseWrite(pEndpointCache->SemRWEntries);
1224	}
1225	else
1226	{
1227	if (pdmacFileEpCacheEntryFlagIsSetClearAcquireLock(pEndpointCache, pEntry,
1228	PDMACFILECACHE_ENTRY_IO_IN_PROGRESS,
1229	PDMACFILECACHE_ENTRY_IS_DIRTY))
1230	{
1231	/* Entry didn't completed yet. Append to the list */
1232	while (cbToRead)
1233	{
1234	PPDMACFILETASKSEG pSeg = (PPDMACFILETASKSEG)RTMemAllocZ(sizeof(PDMACFILETASKSEG));
1235
1236	pSeg->pTask = pTask;
1237	pSeg->uBufOffset = OffDiff;
1238	pSeg->cbTransfer = RT_MIN(cbToRead, cbSegLeft);
1239	pSeg->pvBuf = pbSegBuf;
1240	pSeg->fWrite = false;
1241
1242	ADVANCE_SEGMENT_BUFFER(pSeg->cbTransfer);
1243
1244	pdmacFileEpCacheEntryAddWaitingSegment(pEntry, pSeg);
1245
1246	off += pSeg->cbTransfer;
1247	cbToRead -= pSeg->cbTransfer;
1248	OffDiff += pSeg->cbTransfer;
1249	}
1250	RTSemRWReleaseWrite(pEndpointCache->SemRWEntries);
1251	}
1252	else
1253	{
1254	/* Read as much as we can from the entry. */
1255	while (cbToRead)
1256	{
1257	size_t cbCopy = RT_MIN(cbSegLeft, cbToRead);
1258
1259	memcpy(pbSegBuf, pEntry->pbData + OffDiff, cbCopy);
1260
1261	ADVANCE_SEGMENT_BUFFER(cbCopy);
1262
1263	cbToRead -= cbCopy;
1264	off += cbCopy;
1265	OffDiff += cbCopy;
1266	ASMAtomicSubS32(&pTask->cbTransferLeft, cbCopy);
1267	}
1268	}
1269	}
1270
1271	/* Move this entry to the top position */
1272	#ifdef VBOX_WITH_2Q_CACHE
1273	if (pEntry->pList == &pCache->LruFrequentlyUsed)
1274	{
1275	RTCritSectEnter(&pCache->CritSect);
1276	pdmacFileCacheEntryAddToList(&pCache->LruFrequentlyUsed, pEntry);
1277	RTCritSectLeave(&pCache->CritSect);
1278	}
1279	#else
1280	RTCritSectEnter(&pCache->CritSect);
1281	pdmacFileCacheEntryAddToList(&pCache->LruFrequentlyUsed, pEntry);
1282	RTCritSectLeave(&pCache->CritSect);
1283	#endif
1284	}
1285	else
1286	{
1287	uint8_t *pbBuffer = NULL;
1288
1289	LogFlow(("Fetching data for ghost entry %#p from file\n", pEntry));
1290
1291	#ifdef VBOX_WITH_2Q_CACHE
1292	RTCritSectEnter(&pCache->CritSect);
1293	pdmacFileCacheEntryRemoveFromList(pEntry); /* Remove it before we remove data, otherwise it may get freed when evicting data. */
1294	pdmacFileCacheReclaim(pCache, pEntry->cbData, true, &pbBuffer);
1295
1296	/* Move the entry to Am and fetch it to the cache. */
1297	pdmacFileCacheEntryAddToList(&pCache->LruFrequentlyUsed, pEntry);
1298	RTCritSectLeave(&pCache->CritSect);
1299	#else
1300	RTCritSectEnter(&pCache->CritSect);
1301	pdmacFileCacheUpdate(pCache, pEntry);
1302	pdmacFileCacheReplace(pCache, pEntry->cbData, pEntry->pList, true, &pbBuffer);
1303
1304	/* Move the entry to T2 and fetch it to the cache. */
1305	pdmacFileCacheEntryAddToList(&pCache->LruFrequentlyUsed, pEntry);
1306	RTCritSectLeave(&pCache->CritSect);
1307	#endif
1308
1309	if (pbBuffer)
1310	pEntry->pbData = pbBuffer;
1311	else
1312	pEntry->pbData = (uint8_t *)RTMemPageAlloc(pEntry->cbData);
1313	AssertPtr(pEntry->pbData);
1314
1315	while (cbToRead)
1316	{
1317	PPDMACFILETASKSEG pSeg = (PPDMACFILETASKSEG)RTMemAllocZ(sizeof(PDMACFILETASKSEG));
1318
1319	AssertMsg(off >= pEntry->Core.Key,
1320	("Overflow in calculation off=%RTfoff OffsetAligned=%RTfoff\n",
1321	off, pEntry->Core.Key));
1322
1323	pSeg->pTask = pTask;
1324	pSeg->uBufOffset = OffDiff;
1325	pSeg->cbTransfer = RT_MIN(cbToRead, cbSegLeft);
1326	pSeg->pvBuf = pbSegBuf;
1327
1328	ADVANCE_SEGMENT_BUFFER(pSeg->cbTransfer);
1329
1330	pdmacFileEpCacheEntryAddWaitingSegment(pEntry, pSeg);
1331
1332	off += pSeg->cbTransfer;
1333	OffDiff += pSeg->cbTransfer;
1334	cbToRead -= pSeg->cbTransfer;
1335	}
1336
1337	pdmacFileCacheReadFromEndpoint(pEntry);
1338	}
1339	pdmacFileEpCacheEntryRelease(pEntry);
1340	}
1341	else
1342	{
1343	/* No entry found for this offset. Get best fit entry and fetch the data to the cache. */
1344	size_t cbToReadAligned;
1345	PPDMACFILECACHEENTRY pEntryBestFit = pdmacFileEpCacheGetCacheBestFitEntryByOffset(pEndpointCache, off);
1346
1347	LogFlow(("%sbest fit entry for off=%RTfoff (BestFit=%RTfoff BestFitEnd=%RTfoff BestFitSize=%u)\n",
1348	pEntryBestFit ? "" : "No ",
1349	off,
1350	pEntryBestFit ? pEntryBestFit->Core.Key : 0,
1351	pEntryBestFit ? pEntryBestFit->Core.KeyLast : 0,
1352	pEntryBestFit ? pEntryBestFit->cbData : 0));
1353
1354	if (pEntryBestFit && ((off + (RTFOFF)cbRead) > pEntryBestFit->Core.Key))
1355	{
1356	cbToRead = pEntryBestFit->Core.Key - off;
1357	pdmacFileEpCacheEntryRelease(pEntryBestFit);
1358	cbToReadAligned = cbToRead;
1359	}
1360	else
1361	{
1362	if (pEntryBestFit)
1363	pdmacFileEpCacheEntryRelease(pEntryBestFit);
1364
1365	/*
1366	* Align the size to a 4KB boundary.
1367	* Memory size is aligned to a page boundary
1368	* and memory is wasted if the size is rahter small.
1369	* (For example reads with a size of 512 bytes.
1370	*/
1371	cbToRead = cbRead;
1372	cbToReadAligned = RT_ALIGN_Z(cbRead, PAGE_SIZE);
1373
1374	/* Clip read to file size */
1375	cbToReadAligned = RT_MIN(pEndpoint->cbFile - off, cbToReadAligned);
1376	if (pEntryBestFit)
1377	cbToReadAligned = RT_MIN(cbToReadAligned, pEntryBestFit->Core.Key - off);
1378	}
1379
1380	cbRead -= cbToRead;
1381
1382	if (!cbRead)
1383	STAM_COUNTER_INC(&pCache->cMisses);
1384	else
1385	STAM_COUNTER_INC(&pCache->cPartialHits);
1386
1387	uint8_t *pbBuffer = NULL;
1388
1389	#ifdef VBOX_WITH_2Q_CACHE
1390	RTCritSectEnter(&pCache->CritSect);
1391	bool fEnough = pdmacFileCacheReclaim(pCache, cbToReadAligned, true, &pbBuffer);
1392	RTCritSectLeave(&pCache->CritSect);
1393
1394	if (fEnough)
1395	{
1396	LogFlow(("Evicted enough bytes (%u requested). Creating new cache entry\n", cbToReadAligned));
1397	#else
1398	RTCritSectEnter(&pCache->CritSect);
1399	size_t cbRemoved = pdmacFileCacheEvict(pCache, cbToReadAligned, true, &pbBuffer);
1400	RTCritSectLeave(&pCache->CritSect);
1401
1402	if (cbRemoved >= cbToReadAligned)
1403	{
1404	LogFlow(("Evicted %u bytes (%u requested). Creating new cache entry\n", cbRemoved, cbToReadAligned));
1405	#endif
1406	PPDMACFILECACHEENTRY pEntryNew = pdmacFileCacheEntryAlloc(pCache, pEndpoint, off, cbToReadAligned, pbBuffer);
1407	AssertPtr(pEntryNew);
1408
1409	RTCritSectEnter(&pCache->CritSect);
1410	#ifdef VBOX_WITH_2Q_CACHE
1411	pdmacFileCacheEntryAddToList(&pCache->LruRecentlyUsedIn, pEntryNew);
1412	#else
1413	pdmacFileCacheEntryAddToList(&pCache->LruRecentlyUsed, pEntryNew);
1414	#endif
1415	pCache->cbCached += cbToReadAligned;
1416	RTCritSectLeave(&pCache->CritSect);
1417
1418	pdmacFileEpCacheInsertEntry(pEndpointCache, pEntryNew);
1419	uint32_t uBufOffset = 0;
1420
1421	while (cbToRead)
1422	{
1423	PPDMACFILETASKSEG pSeg = (PPDMACFILETASKSEG)RTMemAllocZ(sizeof(PDMACFILETASKSEG));
1424
1425	pSeg->pTask = pTask;
1426	pSeg->uBufOffset = uBufOffset;
1427	pSeg->cbTransfer = RT_MIN(cbToRead, cbSegLeft);
1428	pSeg->pvBuf = pbSegBuf;
1429
1430	ADVANCE_SEGMENT_BUFFER(pSeg->cbTransfer);
1431
1432	pdmacFileEpCacheEntryAddWaitingSegment(pEntryNew, pSeg);
1433
1434	off += pSeg->cbTransfer;
1435	cbToRead -= pSeg->cbTransfer;
1436	uBufOffset += pSeg->cbTransfer;
1437	}
1438
1439	pdmacFileCacheReadFromEndpoint(pEntryNew);
1440	pdmacFileEpCacheEntryRelease(pEntryNew); /* it is protected by the I/O in progress flag now. */
1441	}
1442	else
1443	{
1444	/*
1445	* There is not enough free space in the cache.
1446	* Pass the request directly to the I/O manager.
1447	*/
1448	LogFlow(("Couldn't evict %u bytes from the cache. Remaining request will be passed through\n", cbToRead));
1449
1450	while (cbToRead)
1451	{
1452	PPDMACTASKFILE pIoTask = pdmacFileTaskAlloc(pEndpoint);
1453	AssertPtr(pIoTask);
1454
1455	pIoTask->pEndpoint = pEndpoint;
1456	pIoTask->enmTransferType = PDMACTASKFILETRANSFER_READ;
1457	pIoTask->Off = off;
1458	pIoTask->DataSeg.cbSeg = RT_MIN(cbToRead, cbSegLeft);
1459	pIoTask->DataSeg.pvSeg = pbSegBuf;
1460	pIoTask->pvUser = pTask;
1461	pIoTask->pfnCompleted = pdmacFileEpTaskCompleted;
1462
1463	off += pIoTask->DataSeg.cbSeg;
1464	cbToRead -= pIoTask->DataSeg.cbSeg;
1465
1466	ADVANCE_SEGMENT_BUFFER(pIoTask->DataSeg.cbSeg);
1467
1468	/* Send it off to the I/O manager. */
1469	pdmacFileEpAddTask(pEndpoint, pIoTask);
1470	}
1471	}
1472	}
1473	}
1474
1475	ASMAtomicWriteBool(&pTask->fCompleted, false);
1476
1477	if (ASMAtomicReadS32(&pTask->cbTransferLeft) == 0
1478	&& !ASMAtomicXchgBool(&pTask->fCompleted, true))
1479	pdmR3AsyncCompletionCompleteTask(&pTask->Core);
1480
1481	return rc;
1482	}
1483
1484	/**
1485	* Writes the given data to the endpoint using the cache if possible.
1486	*
1487	* @returns VBox status code.
1488	* @param pEndpoint The endpoint to write to.
1489	* @param pTask The task structure used as identifier for this request.
1490	* @param off The offset to start writing to
1491	* @param paSegments Pointer to the array holding the source buffers.
1492	* @param cSegments Number of segments in the array.
1493	* @param cbWrite Number of bytes to write.
1494	*/
1495	int pdmacFileEpCacheWrite(PPDMASYNCCOMPLETIONENDPOINTFILE pEndpoint, PPDMASYNCCOMPLETIONTASKFILE pTask,
1496	RTFOFF off, PCPDMDATASEG paSegments, size_t cSegments,
1497	size_t cbWrite)
1498	{
1499	int rc = VINF_SUCCESS;
1500	PPDMACFILEENDPOINTCACHE pEndpointCache = &pEndpoint->DataCache;
1501	PPDMACFILECACHEGLOBAL pCache = pEndpointCache->pCache;
1502	PPDMACFILECACHEENTRY pEntry;
1503
1504	LogFlowFunc((": pEndpoint=%#p{%s} pTask=%#p off=%RTfoff paSegments=%#p cSegments=%u cbWrite=%u\n",
1505	pEndpoint, pEndpoint->Core.pszUri, pTask, off, paSegments, cSegments, cbWrite));
1506
1507	pTask->cbTransferLeft = cbWrite;
1508	/* Set to completed to make sure that the task is valid while we access it. */
1509	ASMAtomicWriteBool(&pTask->fCompleted, true);
1510
1511	int iSegCurr = 0;
1512	uint8_t pbSegBuf = (uint8_t )paSegments[iSegCurr].pvSeg;
1513	size_t cbSegLeft = paSegments[iSegCurr].cbSeg;
1514
1515	while (cbWrite)
1516	{
1517	size_t cbToWrite;
1518
1519	pEntry = pdmacFileEpCacheGetCacheEntryByOffset(pEndpointCache, off);
1520
1521	if (pEntry)
1522	{
1523	/* Write the data into the entry and mark it as dirty */
1524	AssertPtr(pEntry->pList);
1525
1526	RTFOFF OffDiff = off - pEntry->Core.Key;
1527
1528	AssertMsg(off >= pEntry->Core.Key,
1529	("Overflow in calculation off=%RTfoff OffsetAligned=%RTfoff\n",
1530	off, pEntry->Core.Key));
1531
1532	cbToWrite = RT_MIN(pEntry->cbData - OffDiff, cbWrite);
1533	cbWrite -= cbToWrite;
1534
1535	if (!cbWrite)
1536	STAM_COUNTER_INC(&pCache->cHits);
1537	else
1538	STAM_COUNTER_INC(&pCache->cPartialHits);
1539
1540	STAM_COUNTER_ADD(&pCache->StatWritten, cbToWrite);
1541
1542	/* Ghost lists contain no data. */
1543	#ifdef VBOX_WITH_2Q_CACHE
1544	if ( (pEntry->pList == &pCache->LruRecentlyUsedIn)
1545	\|\| (pEntry->pList == &pCache->LruFrequentlyUsed))
1546	#else
1547	if ( (pEntry->pList == &pCache->LruRecentlyUsed)
1548	\|\| (pEntry->pList == &pCache->LruFrequentlyUsed))
1549	#endif
1550	{
1551	/* Check if the buffer is deprecated. */
1552	if(pdmacFileEpCacheEntryFlagIsSetClearAcquireLock(pEndpointCache, pEntry,
1553	PDMACFILECACHE_ENTRY_IS_DEPRECATED,
1554	0))
1555	{
1556	AssertMsg(pEntry->fFlags & PDMACFILECACHE_ENTRY_IO_IN_PROGRESS,
1557	("Entry is deprecated but not in progress\n"));
1558	AssertPtr(pEntry->pbDataReplace);
1559
1560	LogFlow(("Writing to deprecated buffer of entry %#p\n", pEntry));
1561
1562	/* Update the data from the write. */
1563	while (cbToWrite)
1564	{
1565	size_t cbCopy = RT_MIN(cbSegLeft, cbToWrite);
1566
1567	memcpy(pEntry->pbDataReplace + OffDiff, pbSegBuf, cbCopy);
1568
1569	ADVANCE_SEGMENT_BUFFER(cbCopy);
1570
1571	cbToWrite-= cbCopy;
1572	off += cbCopy;
1573	OffDiff += cbCopy;
1574	ASMAtomicSubS32(&pTask->cbTransferLeft, cbCopy);
1575	}
1576	RTSemRWReleaseWrite(pEndpointCache->SemRWEntries);
1577	}
1578	else /* Deprecated flag not set */
1579	{
1580	/* If the entry is dirty it must be also in progress now and we have to defer updating it again. */
1581	if(pdmacFileEpCacheEntryFlagIsSetClearAcquireLock(pEndpointCache, pEntry,
1582	PDMACFILECACHE_ENTRY_IS_DIRTY,
1583	0))
1584	{
1585	AssertMsg(pEntry->fFlags & PDMACFILECACHE_ENTRY_IO_IN_PROGRESS,
1586	("Entry is dirty but not in progress\n"));
1587	Assert(!pEntry->pbDataReplace);
1588
1589	/* Deprecate the current buffer. */
1590	if (!pEntry->pWaitingHead)
1591	pEntry->pbDataReplace = (uint8_t *)RTMemPageAlloc(pEntry->cbData);
1592
1593	/* If we are out of memory or have waiting segments
1594	* defer the write. */
1595	if (!pEntry->pbDataReplace \|\| pEntry->pWaitingHead)
1596	{
1597	/* The data isn't written to the file yet */
1598	while (cbToWrite)
1599	{
1600	PPDMACFILETASKSEG pSeg = (PPDMACFILETASKSEG)RTMemAllocZ(sizeof(PDMACFILETASKSEG));
1601
1602	pSeg->pTask = pTask;
1603	pSeg->uBufOffset = OffDiff;
1604	pSeg->cbTransfer = RT_MIN(cbToWrite, cbSegLeft);
1605	pSeg->pvBuf = pbSegBuf;
1606	pSeg->fWrite = true;
1607
1608	ADVANCE_SEGMENT_BUFFER(pSeg->cbTransfer);
1609
1610	pdmacFileEpCacheEntryAddWaitingSegment(pEntry, pSeg);
1611
1612	off += pSeg->cbTransfer;
1613	OffDiff += pSeg->cbTransfer;
1614	cbToWrite -= pSeg->cbTransfer;
1615	}
1616	STAM_COUNTER_INC(&pEndpointCache->StatWriteDeferred);
1617	}
1618	else /* Deprecate buffer */
1619	{
1620	LogFlow(("Deprecating buffer for entry %#p\n", pEntry));
1621	pEntry->fFlags \|= PDMACFILECACHE_ENTRY_IS_DEPRECATED;
1622
1623	#if 1
1624	/* Copy the data before the update. */
1625	if (OffDiff)
1626	memcpy(pEntry->pbDataReplace, pEntry->pbData, OffDiff);
1627
1628	/* Copy data behind the update. */
1629	if ((pEntry->cbData - OffDiff - cbToWrite) > 0)
1630	memcpy(pEntry->pbDataReplace + OffDiff + cbToWrite,
1631	pEntry->pbData + OffDiff + cbToWrite,
1632	(pEntry->cbData - OffDiff - cbToWrite));
1633	#else
1634	/* A safer method but probably slower. */
1635	memcpy(pEntry->pbDataReplace, pEntry->pbData, pEntry->cbData);
1636	#endif
1637
1638	/* Update the data from the write. */
1639	while (cbToWrite)
1640	{
1641	size_t cbCopy = RT_MIN(cbSegLeft, cbToWrite);
1642
1643	memcpy(pEntry->pbDataReplace + OffDiff, pbSegBuf, cbCopy);
1644
1645	ADVANCE_SEGMENT_BUFFER(cbCopy);
1646
1647	cbToWrite-= cbCopy;
1648	off += cbCopy;
1649	OffDiff += cbCopy;
1650	ASMAtomicSubS32(&pTask->cbTransferLeft, cbCopy);
1651	}
1652
1653	/* We are done here. A new write is initiated if the current request completes. */
1654	}
1655
1656	RTSemRWReleaseWrite(pEndpointCache->SemRWEntries);
1657	}
1658	else /* Dirty bit not set */
1659	{
1660	/*
1661	* Check if a read is in progress for this entry.
1662	* We have to defer processing in that case.
1663	*/
1664	if(pdmacFileEpCacheEntryFlagIsSetClearAcquireLock(pEndpointCache, pEntry,
1665	PDMACFILECACHE_ENTRY_IO_IN_PROGRESS,
1666	0))
1667	{
1668	while (cbToWrite)
1669	{
1670	PPDMACFILETASKSEG pSeg = (PPDMACFILETASKSEG)RTMemAllocZ(sizeof(PDMACFILETASKSEG));
1671
1672	pSeg->pTask = pTask;
1673	pSeg->uBufOffset = OffDiff;
1674	pSeg->cbTransfer = RT_MIN(cbToWrite, cbSegLeft);
1675	pSeg->pvBuf = pbSegBuf;
1676	pSeg->fWrite = true;
1677
1678	ADVANCE_SEGMENT_BUFFER(pSeg->cbTransfer);
1679
1680	pdmacFileEpCacheEntryAddWaitingSegment(pEntry, pSeg);
1681
1682	off += pSeg->cbTransfer;
1683	OffDiff += pSeg->cbTransfer;
1684	cbToWrite -= pSeg->cbTransfer;
1685	}
1686	STAM_COUNTER_INC(&pEndpointCache->StatWriteDeferred);
1687	RTSemRWReleaseWrite(pEndpointCache->SemRWEntries);
1688	}
1689	else /* I/O in progres flag not set */
1690	{
1691	/* Write as much as we can into the entry and update the file. */
1692	while (cbToWrite)
1693	{
1694	size_t cbCopy = RT_MIN(cbSegLeft, cbToWrite);
1695
1696	memcpy(pEntry->pbData + OffDiff, pbSegBuf, cbCopy);
1697
1698	ADVANCE_SEGMENT_BUFFER(cbCopy);
1699
1700	cbToWrite-= cbCopy;
1701	off += cbCopy;
1702	OffDiff += cbCopy;
1703	ASMAtomicSubS32(&pTask->cbTransferLeft, cbCopy);
1704	}
1705
1706	pEntry->fFlags \|= PDMACFILECACHE_ENTRY_IS_DIRTY;
1707	pdmacFileCacheWriteToEndpoint(pEntry);
1708	}
1709	} /* Dirty bit not set */
1710
1711	/* Move this entry to the top position */
1712	#ifdef VBOX_WITH_2Q_CACHE
1713	if (pEntry->pList == &pCache->LruFrequentlyUsed)
1714	{
1715	RTCritSectEnter(&pCache->CritSect);
1716	pdmacFileCacheEntryAddToList(&pCache->LruFrequentlyUsed, pEntry);
1717	RTCritSectLeave(&pCache->CritSect);
1718	} /* Deprecated flag not set. */
1719	#else
1720	RTCritSectEnter(&pCache->CritSect);
1721	pdmacFileCacheEntryAddToList(&pCache->LruFrequentlyUsed, pEntry);
1722	RTCritSectLeave(&pCache->CritSect);
1723	#endif
1724	}
1725	}
1726	else /* Entry is on the ghost list */
1727	{
1728	uint8_t *pbBuffer = NULL;
1729
1730	#ifdef VBOX_WITH_2Q_CACHE
1731	RTCritSectEnter(&pCache->CritSect);
1732	pdmacFileCacheEntryRemoveFromList(pEntry); /* Remove it before we remove data, otherwise it may get freed when evicting data. */
1733	pdmacFileCacheReclaim(pCache, pEntry->cbData, true, &pbBuffer);
1734
1735	/* Move the entry to Am and fetch it to the cache. */
1736	pdmacFileCacheEntryAddToList(&pCache->LruFrequentlyUsed, pEntry);
1737	RTCritSectLeave(&pCache->CritSect);
1738	#else
1739	RTCritSectEnter(&pCache->CritSect);
1740	pdmacFileCacheUpdate(pCache, pEntry);
1741	pdmacFileCacheReplace(pCache, pEntry->cbData, pEntry->pList, true, &pbBuffer);
1742
1743	/* Move the entry to T2 and fetch it to the cache. */
1744	pdmacFileCacheEntryAddToList(&pCache->LruFrequentlyUsed, pEntry);
1745	RTCritSectLeave(&pCache->CritSect);
1746	#endif
1747
1748	if (pbBuffer)
1749	pEntry->pbData = pbBuffer;
1750	else
1751	pEntry->pbData = (uint8_t *)RTMemPageAlloc(pEntry->cbData);
1752	AssertPtr(pEntry->pbData);
1753
1754	while (cbToWrite)
1755	{
1756	PPDMACFILETASKSEG pSeg = (PPDMACFILETASKSEG)RTMemAllocZ(sizeof(PDMACFILETASKSEG));
1757
1758	AssertMsg(off >= pEntry->Core.Key,
1759	("Overflow in calculation off=%RTfoff OffsetAligned=%RTfoff\n",
1760	off, pEntry->Core.Key));
1761
1762	pSeg->pTask = pTask;
1763	pSeg->uBufOffset = OffDiff;
1764	pSeg->cbTransfer = RT_MIN(cbToWrite, cbSegLeft);
1765	pSeg->pvBuf = pbSegBuf;
1766	pSeg->fWrite = true;
1767
1768	ADVANCE_SEGMENT_BUFFER(pSeg->cbTransfer);
1769
1770	pdmacFileEpCacheEntryAddWaitingSegment(pEntry, pSeg);
1771
1772	off += pSeg->cbTransfer;
1773	OffDiff += pSeg->cbTransfer;
1774	cbToWrite -= pSeg->cbTransfer;
1775	}
1776
1777	STAM_COUNTER_INC(&pEndpointCache->StatWriteDeferred);
1778	pdmacFileCacheReadFromEndpoint(pEntry);
1779	}
1780
1781	/* Release the reference. If it is still needed the I/O in progress flag should protect it now. */
1782	pdmacFileEpCacheEntryRelease(pEntry);
1783	}
1784	else /* No entry found */
1785	{
1786	/*
1787	* No entry found. Try to create a new cache entry to store the data in and if that fails
1788	* write directly to the file.
1789	*/
1790	PPDMACFILECACHEENTRY pEntryBestFit = pdmacFileEpCacheGetCacheBestFitEntryByOffset(pEndpointCache, off);
1791
1792	LogFlow(("%sest fit entry for off=%RTfoff (BestFit=%RTfoff BestFitEnd=%RTfoff BestFitSize=%u)\n",
1793	pEntryBestFit ? "B" : "No b",
1794	off,
1795	pEntryBestFit ? pEntryBestFit->Core.Key : 0,
1796	pEntryBestFit ? pEntryBestFit->Core.KeyLast : 0,
1797	pEntryBestFit ? pEntryBestFit->cbData : 0));
1798
1799	if (pEntryBestFit && ((off + (RTFOFF)cbWrite) > pEntryBestFit->Core.Key))
1800	{
1801	cbToWrite = pEntryBestFit->Core.Key - off;
1802	pdmacFileEpCacheEntryRelease(pEntryBestFit);
1803	}
1804	else
1805	{
1806	if (pEntryBestFit)
1807	pdmacFileEpCacheEntryRelease(pEntryBestFit);
1808
1809	cbToWrite = cbWrite;
1810	}
1811
1812	cbWrite -= cbToWrite;
1813
1814	STAM_COUNTER_INC(&pCache->cMisses);
1815	STAM_COUNTER_ADD(&pCache->StatWritten, cbToWrite);
1816
1817	uint8_t *pbBuffer = NULL;
1818
1819	#ifdef VBOX_WITH_2Q_CACHE
1820	RTCritSectEnter(&pCache->CritSect);
1821	bool fEnough = pdmacFileCacheReclaim(pCache, cbToWrite, true, &pbBuffer);
1822	RTCritSectLeave(&pCache->CritSect);
1823
1824	if (fEnough)
1825	{
1826	LogFlow(("Evicted enough bytes (%u requested). Creating new cache entry\n", cbToWrite));
1827	#else
1828	RTCritSectEnter(&pCache->CritSect);
1829	size_t cbRemoved = pdmacFileCacheEvict(pCache, cbToWrite, true, &pbBuffer);
1830	RTCritSectLeave(&pCache->CritSect);
1831
1832	if (cbRemoved >= cbToWrite)
1833	{
1834	LogFlow(("Evicted %u bytes (%u requested). Creating new cache entry\n", cbRemoved, cbToWrite));
1835
1836	#endif
1837	uint8_t *pbBuf;
1838	PPDMACFILECACHEENTRY pEntryNew;
1839
1840	pEntryNew = pdmacFileCacheEntryAlloc(pCache, pEndpoint, off, cbToWrite, pbBuffer);
1841	AssertPtr(pEntryNew);
1842
1843	RTCritSectEnter(&pCache->CritSect);
1844	#ifdef VBOX_WITH_2Q_CACHE
1845	pdmacFileCacheEntryAddToList(&pCache->LruRecentlyUsedIn, pEntryNew);
1846	#else
1847	pdmacFileCacheEntryAddToList(&pCache->LruRecentlyUsed, pEntryNew);
1848	#endif
1849	pCache->cbCached += cbToWrite;
1850	RTCritSectLeave(&pCache->CritSect);
1851
1852	pdmacFileEpCacheInsertEntry(pEndpointCache, pEntryNew);
1853
1854	off += cbToWrite;
1855	pbBuf = pEntryNew->pbData;
1856
1857	while (cbToWrite)
1858	{
1859	size_t cbCopy = RT_MIN(cbSegLeft, cbToWrite);
1860
1861	memcpy(pbBuf, pbSegBuf, cbCopy);
1862
1863	ADVANCE_SEGMENT_BUFFER(cbCopy);
1864
1865	cbToWrite -= cbCopy;
1866	pbBuf += cbCopy;
1867	ASMAtomicSubS32(&pTask->cbTransferLeft, cbCopy);
1868	}
1869
1870	pEntryNew->fFlags \|= PDMACFILECACHE_ENTRY_IS_DIRTY;
1871	pdmacFileCacheWriteToEndpoint(pEntryNew);
1872	pdmacFileEpCacheEntryRelease(pEntryNew); /* it is protected by the I/O in progress flag now. */
1873	}
1874	else
1875	{
1876	/*
1877	* There is not enough free space in the cache.
1878	* Pass the request directly to the I/O manager.
1879	*/
1880	LogFlow(("Couldn't evict %u bytes from the cache. Remaining request will be passed through\n", cbToWrite));
1881
1882	while (cbToWrite)
1883	{
1884	PPDMACTASKFILE pIoTask = pdmacFileTaskAlloc(pEndpoint);
1885	AssertPtr(pIoTask);
1886
1887	pIoTask->pEndpoint = pEndpoint;
1888	pIoTask->enmTransferType = PDMACTASKFILETRANSFER_WRITE;
1889	pIoTask->Off = off;
1890	pIoTask->DataSeg.cbSeg = RT_MIN(cbToWrite, cbSegLeft);
1891	pIoTask->DataSeg.pvSeg = pbSegBuf;
1892	pIoTask->pvUser = pTask;
1893	pIoTask->pfnCompleted = pdmacFileEpTaskCompleted;
1894
1895	off += pIoTask->DataSeg.cbSeg;
1896	cbToWrite -= pIoTask->DataSeg.cbSeg;
1897
1898	ADVANCE_SEGMENT_BUFFER(pIoTask->DataSeg.cbSeg);
1899
1900	/* Send it off to the I/O manager. */
1901	pdmacFileEpAddTask(pEndpoint, pIoTask);
1902	}
1903	}
1904	}
1905	}
1906
1907	ASMAtomicWriteBool(&pTask->fCompleted, false);
1908
1909	if (ASMAtomicReadS32(&pTask->cbTransferLeft) == 0
1910	&& !ASMAtomicXchgBool(&pTask->fCompleted, true))
1911	pdmR3AsyncCompletionCompleteTask(&pTask->Core);
1912
1913	return VINF_SUCCESS;
1914	}
1915
1916	#undef ADVANCE_SEGMENT_BUFFER
1917

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

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

Download in other formats: