PDMAsyncCompletionFileCache.cpp@ 24681

Last change on this file since 24681 was 24622, checked in by vboxsync, 15 years ago
Build fix for debug builds
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 74.3 KB

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

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

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

Download in other formats: