IOBufMgmt.cpp@ 76553

Last change on this file since 76553 was 76553, checked in by vboxsync, 6 years ago
scm --update-copyright-year
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 16.4 KB

Line
1	/* $Id: IOBufMgmt.cpp 76553 2019-01-01 01:45:53Z vboxsync $ */
2	/** @file
3	* VBox storage devices: I/O buffer management API.
4	*/
5
6	/*
7	* Copyright (C) 2016-2019 Oracle Corporation
8	*
9	* This file is part of VirtualBox Open Source Edition (OSE), as
10	* available from http://www.virtualbox.org. This file is free software;
11	* you can redistribute it and/or modify it under the terms of the GNU
12	* General Public License (GPL) as published by the Free Software
13	* Foundation, in version 2 as it comes in the "COPYING" file of the
14	* VirtualBox OSE distribution. VirtualBox OSE is distributed in the
15	* hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
16	*/
17	#define LOG_GROUP LOG_GROUP_IOBUFMGMT
18	#include <VBox/cdefs.h>
19	#include <iprt/errcore.h>
20	#include <VBox/log.h>
21	#include <iprt/assert.h>
22	#include <iprt/critsect.h>
23	#include <iprt/mem.h>
24	#include <iprt/memsafer.h>
25	#include <iprt/sg.h>
26	#include <iprt/string.h>
27	#include <iprt/asm.h>
28
29	/** Set to verify the allocations for distinct memory areas. */
30	//#define IOBUFMGR_VERIFY_ALLOCATIONS 1
31
32	/** The minimum bin size to create - power of two!. */
33	#define IOBUFMGR_BIN_SIZE_MIN _4K
34	/** The maximum bin size to create - power of two!. */
35	#define IOBUFMGR_BIN_SIZE_MAX _1M
36
37	/** Pointer to the internal I/O buffer manager data. */
38	typedef struct IOBUFMGRINT *PIOBUFMGRINT;
39
40	/**
41	* Internal I/O buffer descriptor data.
42	*/
43	typedef struct IOBUFDESCINT
44	{
45	/** Data segments. */
46	RTSGSEG aSegs[10];
47	/** Data segments used for the current allocation. */
48	unsigned cSegsUsed;
49	/** Pointer to I/O buffer manager. */
50	PIOBUFMGRINT pIoBufMgr;
51	} IOBUFDESCINT;
52
53	/**
54	* A
55	*/
56	typedef struct IOBUFMGRBIN
57	{
58	/** Index of the next free entry. */
59	unsigned iFree;
60	/** Pointer to the array of free objects for this bin. */
61	void **papvFree;
62	} IOBUFMGRBIN;
63	typedef IOBUFMGRBIN *PIOBUFMGRBIN;
64
65	/**
66	* Internal I/O buffer manager data.
67	*/
68	typedef struct IOBUFMGRINT
69	{
70	/** Critical section protecting the allocation path. */
71	RTCRITSECT CritSectAlloc;
72	/** Flags the manager was created with. */
73	uint32_t fFlags;
74	/** Maximum size of I/O memory to allocate. */
75	size_t cbMax;
76	/** Amount of free memory. */
77	size_t cbFree;
78	/** The order of smallest bin. */
79	uint32_t u32OrderMin;
80	/** The order of largest bin. */
81	uint32_t u32OrderMax;
82	/** Pointer to the base memory of the allocation. */
83	void *pvMem;
84	/** Number of bins for free objects. */
85	uint32_t cBins;
86	/** Flag whether allocation is on hold waiting for everything to be free
87	* to be able to defragment the memory. */
88	bool fAllocSuspended;
89	/** Array of bins. */
90	PIOBUFMGRBIN paBins;
91	#ifdef IOBUFMGR_VERIFY_ALLOCATIONS
92	/** Pointer to the object state (allocated/free) bitmap. */
93	void *pbmObjState;
94	#endif
95	/** Array of pointer entries for the various bins - variable in size. */
96	void *apvObj[1];
97	} IOBUFMGRINT;
98
99	/* Must be included after IOBUFDESCINT was defined. */
100	#define IOBUFDESCINT_DECLARED
101	#include "IOBufMgmt.h"
102
103	/**
104	* Gets the number of bins required between the given minimum and maximum size
105	* to have a bin for every power of two size inbetween.
106	*
107	* @returns The number of bins required.
108	* @param cbMin The size of the smallest bin.
109	* @param cbMax The size of the largest bin.
110	*/
111	DECLINLINE(uint32_t) iobufMgrGetBinCount(uint32_t cbMin, uint32_t cbMax)
112	{
113	uint32_t u32Max = ASMBitLastSetU32(cbMax);
114	uint32_t u32Min = ASMBitLastSetU32(cbMin);
115
116	Assert(cbMax >= cbMin && cbMax != 0 && cbMin != 0);
117	return u32Max - u32Min + 1;
118	}
119
120	/**
121	* Returns the number of entries required in the object array to cover all bins.
122	*
123	* @returns Number of entries required in the object array.
124	* @param cbMem Size of the memory buffer.
125	* @param cBins Number of bins available.
126	* @param cbMinBin Minimum object size.
127	*/
128	DECLINLINE(uint32_t) iobufMgrGetObjCount(size_t cbMem, unsigned cBins, size_t cbMinBin)
129	{
130	size_t cObjs = 0;
131	size_t cbBin = cbMinBin;
132
133	while (cBins-- > 0)
134	{
135	cObjs += cbMem / cbBin;
136	cbBin <<= 1; /* The size doubles for every bin. */
137	}
138
139	Assert((uint32_t)cObjs == cObjs);
140	return (uint32_t)cObjs;
141	}
142
143	DECLINLINE(void) iobufMgrBinObjAdd(PIOBUFMGRBIN pBin, void *pvObj)
144	{
145	LogFlowFunc(("pBin=%#p{.iFree=%u} pvObj=%#p\n", pBin, pBin->iFree, pvObj));
146	AssertPtr(pvObj);
147	pBin->papvFree[pBin->iFree] = pvObj;
148	pBin->iFree++;
149	LogFlowFunc(("return pBin=%#p{.iFree=%u}\n", pBin, pBin->iFree));
150	}
151
152	DECLINLINE(void *) iobufMgrBinObjRemove(PIOBUFMGRBIN pBin)
153	{
154	LogFlowFunc(("pBin=%#p{.iFree=%u}\n", pBin, pBin->iFree));
155	Assert(pBin->iFree > 0);
156
157	pBin->iFree--;
158	void *pvObj = pBin->papvFree[pBin->iFree];
159	AssertPtr(pvObj);
160
161	LogFlowFunc(("returns pvObj=%#p pBin=%#p{.iFree=%u}\n", pvObj, pBin, pBin->iFree));
162	return pvObj;
163	}
164
165	/**
166	* Resets the bins to factory default (memory resigin in the largest bin).
167	*
168	* @returns nothing.
169	* @param pThis The I/O buffer manager instance.
170	*/
171	static void iobufMgrResetBins(PIOBUFMGRINT pThis)
172	{
173	/* Init the bins. */
174	size_t cbMax = pThis->cbMax;
175	size_t iObj = 0;
176	uint32_t cbBin = IOBUFMGR_BIN_SIZE_MIN;
177	for (unsigned i = 0; i < pThis->cBins; i++)
178	{
179	PIOBUFMGRBIN pBin = &pThis->paBins[i];
180	pBin->iFree = 0;
181	pBin->papvFree = &pThis->apvObj[iObj];
182	iObj += cbMax / cbBin;
183
184	/* Init the biggest possible bin with the free objects. */
185	if ( (cbBin << 1) > cbMax
186	\|\| i == pThis->cBins - 1)
187	{
188	uint8_t pbMem = (uint8_t )pThis->pvMem;
189	while (cbMax)
190	{
191	iobufMgrBinObjAdd(pBin, pbMem);
192	cbMax -= cbBin;
193	pbMem += cbBin;
194
195	if (cbMax < cbBin) /** @todo Populate smaller bins and don't waste memory. */
196	break;
197	}
198
199	/* Limit the number of available bins. */
200	pThis->cBins = i + 1;
201	break;
202	}
203
204	cbBin <<= 1;
205	}
206	}
207
208	/**
209	* Allocate one segment from the manager.
210	*
211	* @returns Number of bytes allocated, 0 if there is no free memory.
212	* @param pThis The I/O buffer manager instance.
213	* @param pSeg The segment to fill in on success.
214	* @param cb Maximum number of bytes to allocate.
215	*/
216	static size_t iobufMgrAllocSegment(PIOBUFMGRINT pThis, PRTSGSEG pSeg, size_t cb)
217	{
218	size_t cbAlloc = 0;
219
220	/* Round to the next power of two and get the bin to try first. */
221	uint32_t u32Order = ASMBitLastSetU32((uint32_t)cb) - 1;
222	if (cb & (RT_BIT_32(u32Order) - 1))
223	u32Order++;
224
225	u32Order = RT_CLAMP(u32Order, pThis->u32OrderMin, pThis->u32OrderMax);
226	unsigned iBin = u32Order - pThis->u32OrderMin;
227
228	/*
229	* Check whether the bin can satisfy the request. If not try the next bigger
230	* bin and so on. If there is nothing to find try the smaller bins.
231	*/
232	Assert(iBin < pThis->cBins);
233
234	PIOBUFMGRBIN pBin = &pThis->paBins[iBin];
235	/* Reset the bins if there is nothing in the current one but all the memory is marked as free. */
236	if ( pThis->cbFree == pThis->cbMax
237	&& pBin->iFree == 0)
238	iobufMgrResetBins(pThis);
239
240	if (pBin->iFree == 0)
241	{
242	unsigned iBinCur = iBin;
243	PIOBUFMGRBIN pBinCur = &pThis->paBins[iBinCur];
244
245	while (iBinCur < pThis->cBins)
246	{
247	if (pBinCur->iFree != 0)
248	{
249	uint8_t pbMem = (uint8_t )iobufMgrBinObjRemove(pBinCur);
250	AssertPtr(pbMem);
251
252	/* Always split into half. */
253	while (iBinCur > iBin)
254	{
255	iBinCur--;
256	pBinCur = &pThis->paBins[iBinCur];
257	iobufMgrBinObjAdd(pBinCur, pbMem + (size_t)RT_BIT(iBinCur + pThis->u32OrderMin)); /* (RT_BIT causes weird MSC warning without cast) */
258	}
259
260	/* For the last bin we will get two new memory blocks. */
261	iobufMgrBinObjAdd(pBinCur, pbMem);
262	Assert(pBin == pBinCur);
263	break;
264	}
265
266	pBinCur++;
267	iBinCur++;
268	}
269	}
270
271	/*
272	* If we didn't find something in the higher bins try to accumulate as much as possible from the smaller bins.
273	*/
274	if ( pBin->iFree == 0
275	&& iBin > 0)
276	{
277	#if 1
278	pThis->fAllocSuspended = true;
279	#else
280	do
281	{
282	iBin--;
283	pBin = &pThis->paBins[iBin];
284
285	if (pBin->iFree != 0)
286	{
287	pBin->iFree--;
288	pSeg->pvSeg = pBin->papvFree[pBin->iFree];
289	pSeg->cbSeg = (size_t)RT_BIT_32(iBin + pThis->u32OrderMin);
290	AssertPtr(pSeg->pvSeg);
291	cbAlloc = pSeg->cbSeg;
292	break;
293	}
294	}
295	while (iBin > 0);
296	#endif
297	}
298	else if (pBin->iFree != 0)
299	{
300	pSeg->pvSeg = iobufMgrBinObjRemove(pBin);
301	pSeg->cbSeg = (size_t)RT_BIT_32(u32Order);
302	cbAlloc = pSeg->cbSeg;
303	AssertPtr(pSeg->pvSeg);
304
305	pThis->cbFree -= cbAlloc;
306
307	#ifdef IOBUFMGR_VERIFY_ALLOCATIONS
308	/* Mark the objects as allocated. */
309	uint32_t iBinStart = ((uintptr_t)pSeg->pvSeg - (uintptr_t)pThis->pvMem) / IOBUFMGR_BIN_SIZE_MIN;
310	Assert( !(((uintptr_t)pSeg->pvSeg - (uintptr_t)pThis->pvMem) % IOBUFMGR_BIN_SIZE_MIN)
311	&& !(pSeg->cbSeg % IOBUFMGR_BIN_SIZE_MIN));
312	uint32_t iBinEnd = iBinStart + (pSeg->cbSeg / IOBUFMGR_BIN_SIZE_MIN);
313	while (iBinStart < iBinEnd)
314	{
315	bool fState = ASMBitTestAndSet(pThis->pbmObjState, iBinStart);
316	//LogFlowFunc(("iBinStart=%u fState=%RTbool -> true\n", iBinStart, fState));
317	AssertMsg(!fState, ("Trying to allocate an already allocated object\n"));
318	iBinStart++;
319	}
320	#endif
321	}
322
323	return cbAlloc;
324	}
325
326	DECLHIDDEN(int) IOBUFMgrCreate(PIOBUFMGR phIoBufMgr, size_t cbMax, uint32_t fFlags)
327	{
328	int rc = VINF_SUCCESS;
329
330	AssertPtrReturn(phIoBufMgr, VERR_INVALID_POINTER);
331	AssertReturn(cbMax, VERR_NOT_IMPLEMENTED);
332
333	/* Allocate the basic structure in one go. */
334	unsigned cBins = iobufMgrGetBinCount(IOBUFMGR_BIN_SIZE_MIN, IOBUFMGR_BIN_SIZE_MAX);
335	uint32_t cObjs = iobufMgrGetObjCount(cbMax, cBins, IOBUFMGR_BIN_SIZE_MIN);
336	PIOBUFMGRINT pThis = (PIOBUFMGRINT)RTMemAllocZ(RT_UOFFSETOF_DYN(IOBUFMGRINT, apvObj[cObjs]) + cBins * sizeof(IOBUFMGRBIN));
337	if (RT_LIKELY(pThis))
338	{
339	pThis->fFlags = fFlags;
340	pThis->cbMax = cbMax;
341	pThis->cbFree = cbMax;
342	pThis->cBins = cBins;
343	pThis->fAllocSuspended = false;
344	pThis->u32OrderMin = ASMBitLastSetU32(IOBUFMGR_BIN_SIZE_MIN) - 1;
345	pThis->u32OrderMax = ASMBitLastSetU32(IOBUFMGR_BIN_SIZE_MAX) - 1;
346	pThis->paBins = (PIOBUFMGRBIN)((uint8_t *)pThis + RT_UOFFSETOF_DYN(IOBUFMGRINT, apvObj[cObjs]));
347
348	#ifdef IOBUFMGR_VERIFY_ALLOCATIONS
349	pThis->pbmObjState = RTMemAllocZ((cbMax / IOBUFMGR_BIN_SIZE_MIN / 8) + 1);
350	if (!pThis->pbmObjState)
351	rc = VERR_NO_MEMORY;
352	#endif
353
354	if (RT_SUCCESS(rc))
355	rc = RTCritSectInit(&pThis->CritSectAlloc);
356	if (RT_SUCCESS(rc))
357	{
358	if (pThis->fFlags & IOBUFMGR_F_REQUIRE_NOT_PAGABLE)
359	rc = RTMemSaferAllocZEx(&pThis->pvMem, RT_ALIGN_Z(pThis->cbMax, _4K),
360	RTMEMSAFER_F_REQUIRE_NOT_PAGABLE);
361	else
362	pThis->pvMem = RTMemPageAllocZ(RT_ALIGN_Z(pThis->cbMax, _4K));
363
364	if ( RT_LIKELY(pThis->pvMem)
365	&& RT_SUCCESS(rc))
366	{
367	iobufMgrResetBins(pThis);
368
369	*phIoBufMgr = pThis;
370	return VINF_SUCCESS;
371	}
372	else
373	rc = VERR_NO_MEMORY;
374
375	RTCritSectDelete(&pThis->CritSectAlloc);
376	}
377
378	RTMemFree(pThis);
379	}
380	else
381	rc = VERR_NO_MEMORY;
382
383	return rc;
384	}
385
386	DECLHIDDEN(int) IOBUFMgrDestroy(IOBUFMGR hIoBufMgr)
387	{
388	PIOBUFMGRINT pThis = hIoBufMgr;
389
390	AssertPtrReturn(pThis, VERR_INVALID_HANDLE);
391
392	int rc = RTCritSectEnter(&pThis->CritSectAlloc);
393	if (RT_SUCCESS(rc))
394	{
395	if (pThis->cbFree == pThis->cbMax)
396	{
397	if (pThis->fFlags & IOBUFMGR_F_REQUIRE_NOT_PAGABLE)
398	RTMemSaferFree(pThis->pvMem, RT_ALIGN_Z(pThis->cbMax, _4K));
399	else
400	RTMemPageFree(pThis->pvMem, RT_ALIGN_Z(pThis->cbMax, _4K));
401
402	#ifdef IOBUFMGR_VERIFY_ALLOCATIONS
403	AssertPtr(pThis->pbmObjState);
404	RTMemFree(pThis->pbmObjState);
405	pThis->pbmObjState = NULL;
406	#endif
407
408	RTCritSectLeave(&pThis->CritSectAlloc);
409	RTCritSectDelete(&pThis->CritSectAlloc);
410	RTMemFree(pThis);
411	}
412	else
413	{
414	rc = VERR_INVALID_STATE;
415	RTCritSectLeave(&pThis->CritSectAlloc);
416	}
417	}
418
419	return rc;
420	}
421
422	DECLHIDDEN(int) IOBUFMgrAllocBuf(IOBUFMGR hIoBufMgr, PIOBUFDESC pIoBufDesc, size_t cbIoBuf,
423	size_t *pcbIoBufAllocated)
424	{
425	PIOBUFMGRINT pThis = hIoBufMgr;
426
427	LogFlowFunc(("pThis=%#p pIoBufDesc=%#p cbIoBuf=%zu pcbIoBufAllocated=%#p\n",
428	pThis, pIoBufDesc, cbIoBuf, pcbIoBufAllocated));
429
430	AssertPtrReturn(pThis, VERR_INVALID_HANDLE);
431	AssertReturn(cbIoBuf > 0, VERR_INVALID_PARAMETER);
432
433	if ( !pThis->cbFree
434	\|\| pThis->fAllocSuspended)
435	return VERR_NO_MEMORY;
436
437	int rc = RTCritSectEnter(&pThis->CritSectAlloc);
438	if (RT_SUCCESS(rc))
439	{
440	unsigned iSeg = 0;
441	size_t cbLeft = cbIoBuf;
442	size_t cbIoBufAlloc = 0;
443	PRTSGSEG pSeg = &pIoBufDesc->Int.aSegs[0];
444
445	while ( iSeg < RT_ELEMENTS(pIoBufDesc->Int.aSegs)
446	&& cbLeft)
447	{
448	size_t cbAlloc = iobufMgrAllocSegment(pThis, pSeg, cbLeft);
449	if (!cbAlloc)
450	break;
451
452	iSeg++;
453	pSeg++;
454	cbLeft -= RT_MIN(cbAlloc, cbLeft);
455	cbIoBufAlloc += cbAlloc;
456	}
457
458	if (iSeg)
459	RTSgBufInit(&pIoBufDesc->SgBuf, &pIoBufDesc->Int.aSegs[0], iSeg);
460	else
461	rc = VERR_NO_MEMORY;
462
463	pIoBufDesc->Int.cSegsUsed = iSeg;
464	pIoBufDesc->Int.pIoBufMgr = pThis;
465	*pcbIoBufAllocated = cbIoBufAlloc;
466	Assert( (RT_SUCCESS(rc) && *pcbIoBufAllocated > 0)
467	\|\| RT_FAILURE(rc));
468
469	RTCritSectLeave(&pThis->CritSectAlloc);
470	}
471
472	return rc;
473	}
474
475	DECLHIDDEN(void) IOBUFMgrFreeBuf(PIOBUFDESC pIoBufDesc)
476	{
477	PIOBUFMGRINT pThis = pIoBufDesc->Int.pIoBufMgr;
478
479	LogFlowFunc(("pIoBufDesc=%#p{.cSegsUsed=%u}\n", pIoBufDesc, pIoBufDesc->Int.cSegsUsed));
480
481	AssertPtr(pThis);
482
483	int rc = RTCritSectEnter(&pThis->CritSectAlloc);
484	AssertRC(rc);
485
486	if (RT_SUCCESS(rc))
487	{
488	for (unsigned i = 0; i < pIoBufDesc->Int.cSegsUsed; i++)
489	{
490	PRTSGSEG pSeg = &pIoBufDesc->Int.aSegs[i];
491
492	uint32_t u32Order = ASMBitLastSetU32((uint32_t)pSeg->cbSeg) - 1;
493	unsigned iBin = u32Order - pThis->u32OrderMin;
494
495	Assert(iBin < pThis->cBins);
496	PIOBUFMGRBIN pBin = &pThis->paBins[iBin];
497	iobufMgrBinObjAdd(pBin, pSeg->pvSeg);
498	pThis->cbFree += pSeg->cbSeg;
499
500	#ifdef IOBUFMGR_VERIFY_ALLOCATIONS
501	/* Mark the objects as free. */
502	uint32_t iBinStart = ((uintptr_t)pSeg->pvSeg - (uintptr_t)pThis->pvMem) / IOBUFMGR_BIN_SIZE_MIN;
503	Assert( !(((uintptr_t)pSeg->pvSeg - (uintptr_t)pThis->pvMem) % IOBUFMGR_BIN_SIZE_MIN)
504	&& !(pSeg->cbSeg % IOBUFMGR_BIN_SIZE_MIN));
505	uint32_t iBinEnd = iBinStart + (pSeg->cbSeg / IOBUFMGR_BIN_SIZE_MIN);
506	while (iBinStart < iBinEnd)
507	{
508	bool fState = ASMBitTestAndClear(pThis->pbmObjState, iBinStart);
509	//LogFlowFunc(("iBinStart=%u fState=%RTbool -> false\n", iBinStart, fState));
510	AssertMsg(fState, ("Trying to free a non allocated object\n"));
511	iBinStart++;
512	}
513
514	/* Poison the state. */
515	pSeg->cbSeg = ~0;
516	pSeg->pvSeg = (void *)~(uintptr_t)0;
517	#endif
518	}
519
520	if ( pThis->cbFree == pThis->cbMax
521	&& pThis->fAllocSuspended)
522	{
523	iobufMgrResetBins(pThis);
524	pThis->fAllocSuspended = false;
525	}
526
527	RTCritSectLeave(&pThis->CritSectAlloc);
528	}
529
530	pIoBufDesc->Int.cSegsUsed = 0;
531	#ifdef IOBUFMGR_VERIFY_ALLOCATIONS
532	memset(&pIoBufDesc->SgBuf, 0xff, sizeof(pIoBufDesc->SgBuf));
533	#endif
534	}
535

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

source: vbox/trunk/src/VBox/Devices/Storage/IOBufMgmt.cpp@ 76553

Download in other formats: