IOBufMgmt.cpp@ 104027

Last change on this file since 104027 was 99739, checked in by vboxsync, 19 months ago
*: doxygen corrections (mostly about removing @returns from functions returning void).
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 16.6 KB

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

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

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

Download in other formats: