VirtualBox

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

Last change on this file was 99739, checked in by vboxsync, 12 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. */
48typedef struct IOBUFMGRINT *PIOBUFMGRINT;
49
50/**
51 * Internal I/O buffer descriptor data.
52 */
53typedef 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 */
66typedef 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;
73typedef IOBUFMGRBIN *PIOBUFMGRBIN;
74
75/**
76 * Internal I/O buffer manager data.
77 */
78typedef 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 */
121DECLINLINE(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 */
138DECLINLINE(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
153DECLINLINE(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
162DECLINLINE(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 */
180static 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 */
225static 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
335DECLHIDDEN(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
395DECLHIDDEN(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
431DECLHIDDEN(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
483DECLHIDDEN(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.

© 2023 Oracle
Contact – Privacy policy – Terms of Use