IOBufMgmt.cpp@ 98103

Last change on this file since 98103 was 98103, checked in by vboxsync, 23 months ago
Copyright year updates by scm.
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 98103 2023-01-17 14:15:46Z 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	* @returns nothing.
179	* @param pThis The I/O buffer manager instance.
180	*/
181	static void iobufMgrResetBins(PIOBUFMGRINT pThis)
182	{
183	/* Init the bins. */
184	size_t cbMax = pThis->cbMax;
185	size_t iObj = 0;
186	uint32_t cbBin = IOBUFMGR_BIN_SIZE_MIN;
187	for (unsigned i = 0; i < pThis->cBins; i++)
188	{
189	PIOBUFMGRBIN pBin = &pThis->paBins[i];
190	pBin->iFree = 0;
191	pBin->papvFree = &pThis->apvObj[iObj];
192	iObj += cbMax / cbBin;
193
194	/* Init the biggest possible bin with the free objects. */
195	if ( (cbBin << 1) > cbMax
196	\|\| i == pThis->cBins - 1)
197	{
198	uint8_t pbMem = (uint8_t )pThis->pvMem;
199	while (cbMax)
200	{
201	iobufMgrBinObjAdd(pBin, pbMem);
202	cbMax -= cbBin;
203	pbMem += cbBin;
204
205	if (cbMax < cbBin) /** @todo Populate smaller bins and don't waste memory. */
206	break;
207	}
208
209	/* Limit the number of available bins. */
210	pThis->cBins = i + 1;
211	break;
212	}
213
214	cbBin <<= 1;
215	}
216	}
217
218	/**
219	* Allocate one segment from the manager.
220	*
221	* @returns Number of bytes allocated, 0 if there is no free memory.
222	* @param pThis The I/O buffer manager instance.
223	* @param pSeg The segment to fill in on success.
224	* @param cb Maximum number of bytes to allocate.
225	*/
226	static size_t iobufMgrAllocSegment(PIOBUFMGRINT pThis, PRTSGSEG pSeg, size_t cb)
227	{
228	size_t cbAlloc = 0;
229
230	/* Round to the next power of two and get the bin to try first. */
231	uint32_t u32Order = ASMBitLastSetU32((uint32_t)cb) - 1;
232	if (cb & (RT_BIT_32(u32Order) - 1))
233	u32Order++;
234
235	u32Order = RT_CLAMP(u32Order, pThis->u32OrderMin, pThis->u32OrderMax);
236	unsigned iBin = u32Order - pThis->u32OrderMin;
237
238	/*
239	* Check whether the bin can satisfy the request. If not try the next bigger
240	* bin and so on. If there is nothing to find try the smaller bins.
241	*/
242	Assert(iBin < pThis->cBins);
243
244	PIOBUFMGRBIN pBin = &pThis->paBins[iBin];
245	/* Reset the bins if there is nothing in the current one but all the memory is marked as free. */
246	if ( pThis->cbFree == pThis->cbMax
247	&& pBin->iFree == 0)
248	iobufMgrResetBins(pThis);
249
250	if (pBin->iFree == 0)
251	{
252	unsigned iBinCur = iBin;
253	PIOBUFMGRBIN pBinCur = &pThis->paBins[iBinCur];
254
255	while (iBinCur < pThis->cBins)
256	{
257	if (pBinCur->iFree != 0)
258	{
259	uint8_t pbMem = (uint8_t )iobufMgrBinObjRemove(pBinCur);
260	AssertPtr(pbMem);
261
262	/* Always split into half. */
263	while (iBinCur > iBin)
264	{
265	iBinCur--;
266	pBinCur = &pThis->paBins[iBinCur];
267	iobufMgrBinObjAdd(pBinCur, pbMem + RT_BIT_Z(iBinCur + pThis->u32OrderMin));
268	}
269
270	/* For the last bin we will get two new memory blocks. */
271	iobufMgrBinObjAdd(pBinCur, pbMem);
272	Assert(pBin == pBinCur);
273	break;
274	}
275
276	pBinCur++;
277	iBinCur++;
278	}
279	}
280
281	/*
282	* If we didn't find something in the higher bins try to accumulate as much as possible from the smaller bins.
283	*/
284	if ( pBin->iFree == 0
285	&& iBin > 0)
286	{
287	#if 1
288	pThis->fAllocSuspended = true;
289	#else
290	do
291	{
292	iBin--;
293	pBin = &pThis->paBins[iBin];
294
295	if (pBin->iFree != 0)
296	{
297	pBin->iFree--;
298	pSeg->pvSeg = pBin->papvFree[pBin->iFree];
299	pSeg->cbSeg = (size_t)RT_BIT_32(iBin + pThis->u32OrderMin);
300	AssertPtr(pSeg->pvSeg);
301	cbAlloc = pSeg->cbSeg;
302	break;
303	}
304	}
305	while (iBin > 0);
306	#endif
307	}
308	else if (pBin->iFree != 0)
309	{
310	pSeg->pvSeg = iobufMgrBinObjRemove(pBin);
311	pSeg->cbSeg = RT_BIT_Z(u32Order);
312	cbAlloc = pSeg->cbSeg;
313	AssertPtr(pSeg->pvSeg);
314
315	pThis->cbFree -= cbAlloc;
316
317	#ifdef IOBUFMGR_VERIFY_ALLOCATIONS
318	/* Mark the objects as allocated. */
319	uint32_t iBinStart = ((uintptr_t)pSeg->pvSeg - (uintptr_t)pThis->pvMem) / IOBUFMGR_BIN_SIZE_MIN;
320	Assert( !(((uintptr_t)pSeg->pvSeg - (uintptr_t)pThis->pvMem) % IOBUFMGR_BIN_SIZE_MIN)
321	&& !(pSeg->cbSeg % IOBUFMGR_BIN_SIZE_MIN));
322	uint32_t iBinEnd = iBinStart + (pSeg->cbSeg / IOBUFMGR_BIN_SIZE_MIN);
323	while (iBinStart < iBinEnd)
324	{
325	bool fState = ASMBitTestAndSet(pThis->pbmObjState, iBinStart);
326	//LogFlowFunc(("iBinStart=%u fState=%RTbool -> true\n", iBinStart, fState));
327	AssertMsg(!fState, ("Trying to allocate an already allocated object\n"));
328	iBinStart++;
329	}
330	#endif
331	}
332
333	return cbAlloc;
334	}
335
336	DECLHIDDEN(int) IOBUFMgrCreate(PIOBUFMGR phIoBufMgr, size_t cbMax, uint32_t fFlags)
337	{
338	int rc = VINF_SUCCESS;
339
340	AssertPtrReturn(phIoBufMgr, VERR_INVALID_POINTER);
341	AssertReturn(cbMax, VERR_NOT_IMPLEMENTED);
342
343	/* Allocate the basic structure in one go. */
344	unsigned cBins = iobufMgrGetBinCount(IOBUFMGR_BIN_SIZE_MIN, IOBUFMGR_BIN_SIZE_MAX);
345	uint32_t cObjs = iobufMgrGetObjCount(cbMax, cBins, IOBUFMGR_BIN_SIZE_MIN);
346	PIOBUFMGRINT pThis = (PIOBUFMGRINT)RTMemAllocZ(RT_UOFFSETOF_DYN(IOBUFMGRINT, apvObj[cObjs]) + cBins * sizeof(IOBUFMGRBIN));
347	if (RT_LIKELY(pThis))
348	{
349	pThis->fFlags = fFlags;
350	pThis->cbMax = cbMax;
351	pThis->cbFree = cbMax;
352	pThis->cBins = cBins;
353	pThis->fAllocSuspended = false;
354	pThis->u32OrderMin = ASMBitLastSetU32(IOBUFMGR_BIN_SIZE_MIN) - 1;
355	pThis->u32OrderMax = ASMBitLastSetU32(IOBUFMGR_BIN_SIZE_MAX) - 1;
356	pThis->paBins = (PIOBUFMGRBIN)((uint8_t *)pThis + RT_UOFFSETOF_DYN(IOBUFMGRINT, apvObj[cObjs]));
357
358	#ifdef IOBUFMGR_VERIFY_ALLOCATIONS
359	pThis->pbmObjState = RTMemAllocZ((cbMax / IOBUFMGR_BIN_SIZE_MIN / 8) + 1);
360	if (!pThis->pbmObjState)
361	rc = VERR_NO_MEMORY;
362	#endif
363
364	if (RT_SUCCESS(rc))
365	rc = RTCritSectInit(&pThis->CritSectAlloc);
366	if (RT_SUCCESS(rc))
367	{
368	if (pThis->fFlags & IOBUFMGR_F_REQUIRE_NOT_PAGABLE)
369	rc = RTMemSaferAllocZEx(&pThis->pvMem, RT_ALIGN_Z(pThis->cbMax, _4K),
370	RTMEMSAFER_F_REQUIRE_NOT_PAGABLE);
371	else
372	pThis->pvMem = RTMemPageAllocZ(RT_ALIGN_Z(pThis->cbMax, _4K));
373
374	if ( RT_LIKELY(pThis->pvMem)
375	&& RT_SUCCESS(rc))
376	{
377	iobufMgrResetBins(pThis);
378
379	*phIoBufMgr = pThis;
380	return VINF_SUCCESS;
381	}
382	else
383	rc = VERR_NO_MEMORY;
384
385	RTCritSectDelete(&pThis->CritSectAlloc);
386	}
387
388	RTMemFree(pThis);
389	}
390	else
391	rc = VERR_NO_MEMORY;
392
393	return rc;
394	}
395
396	DECLHIDDEN(int) IOBUFMgrDestroy(IOBUFMGR hIoBufMgr)
397	{
398	PIOBUFMGRINT pThis = hIoBufMgr;
399
400	AssertPtrReturn(pThis, VERR_INVALID_HANDLE);
401
402	int rc = RTCritSectEnter(&pThis->CritSectAlloc);
403	if (RT_SUCCESS(rc))
404	{
405	if (pThis->cbFree == pThis->cbMax)
406	{
407	if (pThis->fFlags & IOBUFMGR_F_REQUIRE_NOT_PAGABLE)
408	RTMemSaferFree(pThis->pvMem, RT_ALIGN_Z(pThis->cbMax, _4K));
409	else
410	RTMemPageFree(pThis->pvMem, RT_ALIGN_Z(pThis->cbMax, _4K));
411
412	#ifdef IOBUFMGR_VERIFY_ALLOCATIONS
413	AssertPtr(pThis->pbmObjState);
414	RTMemFree(pThis->pbmObjState);
415	pThis->pbmObjState = NULL;
416	#endif
417
418	RTCritSectLeave(&pThis->CritSectAlloc);
419	RTCritSectDelete(&pThis->CritSectAlloc);
420	RTMemFree(pThis);
421	}
422	else
423	{
424	rc = VERR_INVALID_STATE;
425	RTCritSectLeave(&pThis->CritSectAlloc);
426	}
427	}
428
429	return rc;
430	}
431
432	DECLHIDDEN(int) IOBUFMgrAllocBuf(IOBUFMGR hIoBufMgr, PIOBUFDESC pIoBufDesc, size_t cbIoBuf, size_t *pcbIoBufAllocated)
433	{
434	PIOBUFMGRINT pThis = hIoBufMgr;
435
436	LogFlowFunc(("pThis=%#p pIoBufDesc=%#p cbIoBuf=%zu pcbIoBufAllocated=%#p\n",
437	pThis, pIoBufDesc, cbIoBuf, pcbIoBufAllocated));
438
439	AssertPtrReturn(pThis, VERR_INVALID_HANDLE);
440	AssertReturn(cbIoBuf > 0, VERR_INVALID_PARAMETER);
441
442	if ( !pThis->cbFree
443	\|\| pThis->fAllocSuspended)
444	return VERR_NO_MEMORY;
445
446	int rc = RTCritSectEnter(&pThis->CritSectAlloc);
447	if (RT_SUCCESS(rc))
448	{
449	unsigned iSeg = 0;
450	size_t cbLeft = cbIoBuf;
451	size_t cbIoBufAlloc = 0;
452	PRTSGSEG pSeg = &pIoBufDesc->Int.aSegs[0];
453
454	while ( iSeg < RT_ELEMENTS(pIoBufDesc->Int.aSegs)
455	&& cbLeft)
456	{
457	size_t cbAlloc = iobufMgrAllocSegment(pThis, pSeg, cbLeft);
458	if (!cbAlloc)
459	break;
460
461	iSeg++;
462	pSeg++;
463	cbLeft -= RT_MIN(cbAlloc, cbLeft);
464	cbIoBufAlloc += cbAlloc;
465	}
466
467	if (iSeg)
468	RTSgBufInit(&pIoBufDesc->SgBuf, &pIoBufDesc->Int.aSegs[0], iSeg);
469	else
470	rc = VERR_NO_MEMORY;
471
472	pIoBufDesc->Int.cSegsUsed = iSeg;
473	pIoBufDesc->Int.pIoBufMgr = pThis;
474	*pcbIoBufAllocated = cbIoBufAlloc;
475	Assert( (RT_SUCCESS(rc) && *pcbIoBufAllocated > 0)
476	\|\| RT_FAILURE(rc));
477
478	RTCritSectLeave(&pThis->CritSectAlloc);
479	}
480
481	return rc;
482	}
483
484	DECLHIDDEN(void) IOBUFMgrFreeBuf(PIOBUFDESC pIoBufDesc)
485	{
486	PIOBUFMGRINT pThis = pIoBufDesc->Int.pIoBufMgr;
487
488	LogFlowFunc(("pIoBufDesc=%#p{.cSegsUsed=%u}\n", pIoBufDesc, pIoBufDesc->Int.cSegsUsed));
489
490	AssertPtr(pThis);
491
492	int rc = RTCritSectEnter(&pThis->CritSectAlloc);
493	AssertRC(rc);
494
495	if (RT_SUCCESS(rc))
496	{
497	for (unsigned i = 0; i < pIoBufDesc->Int.cSegsUsed; i++)
498	{
499	PRTSGSEG pSeg = &pIoBufDesc->Int.aSegs[i];
500
501	uint32_t u32Order = ASMBitLastSetU32((uint32_t)pSeg->cbSeg) - 1;
502	unsigned iBin = u32Order - pThis->u32OrderMin;
503
504	Assert(iBin < pThis->cBins);
505	PIOBUFMGRBIN pBin = &pThis->paBins[iBin];
506	iobufMgrBinObjAdd(pBin, pSeg->pvSeg);
507	pThis->cbFree += pSeg->cbSeg;
508
509	#ifdef IOBUFMGR_VERIFY_ALLOCATIONS
510	/* Mark the objects as free. */
511	uint32_t iBinStart = ((uintptr_t)pSeg->pvSeg - (uintptr_t)pThis->pvMem) / IOBUFMGR_BIN_SIZE_MIN;
512	Assert( !(((uintptr_t)pSeg->pvSeg - (uintptr_t)pThis->pvMem) % IOBUFMGR_BIN_SIZE_MIN)
513	&& !(pSeg->cbSeg % IOBUFMGR_BIN_SIZE_MIN));
514	uint32_t iBinEnd = iBinStart + (pSeg->cbSeg / IOBUFMGR_BIN_SIZE_MIN);
515	while (iBinStart < iBinEnd)
516	{
517	bool fState = ASMBitTestAndClear(pThis->pbmObjState, iBinStart);
518	//LogFlowFunc(("iBinStart=%u fState=%RTbool -> false\n", iBinStart, fState));
519	AssertMsg(fState, ("Trying to free a non allocated object\n"));
520	iBinStart++;
521	}
522
523	/* Poison the state. */
524	pSeg->cbSeg = ~0;
525	pSeg->pvSeg = (void *)~(uintptr_t)0;
526	#endif
527	}
528
529	if ( pThis->cbFree == pThis->cbMax
530	&& pThis->fAllocSuspended)
531	{
532	iobufMgrResetBins(pThis);
533	pThis->fAllocSuspended = false;
534	}
535
536	RTCritSectLeave(&pThis->CritSectAlloc);
537	}
538
539	pIoBufDesc->Int.cSegsUsed = 0;
540	#ifdef IOBUFMGR_VERIFY_ALLOCATIONS
541	memset(&pIoBufDesc->SgBuf, 0xff, sizeof(pIoBufDesc->SgBuf));
542	#endif
543	}
544

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

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

Download in other formats: