VirtualBox

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

Last change on this file since 63942 was 63562, checked in by vboxsync, 8 years ago

scm: cleaning up todos
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 11.7 KB
Line 
1/* $Id: IOBufMgmt.cpp 63562 2016-08-16 14:04:03Z vboxsync $ */
2/** @file
3 * VBox storage devices: I/O buffer management API.
4 */
5
6/*
7 * Copyright (C) 2016 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#include <VBox/cdefs.h>
18#include <VBox/err.h>
19#include <iprt/assert.h>
20#include <iprt/critsect.h>
21#include <iprt/mem.h>
22#include <iprt/memsafer.h>
23#include <iprt/sg.h>
24#include <iprt/asm.h>
25
26/** The minimum bin size to create - power of two!. */
27#define IOBUFMGR_BIN_SIZE_MIN _4K
28/** The maximum bin size to create - power of two!. */
29#define IOBUFMGR_BIN_SIZE_MAX _1M
30
31/** Pointer to the internal I/O buffer manager data. */
32typedef struct IOBUFMGRINT *PIOBUFMGRINT;
33
34/**
35 * Internal I/O buffer descriptor data.
36 */
37typedef struct IOBUFDESCINT
38{
39 /** Data segments. */
40 RTSGSEG aSegs[10];
41 /** Data segments used for the current allocation. */
42 unsigned cSegsUsed;
43 /** Pointer to I/O buffer manager. */
44 PIOBUFMGRINT pIoBufMgr;
45} IOBUFDESCINT;
46
47/**
48 * A
49 */
50typedef struct IOBUFMGRBIN
51{
52 /** Index of the next free entry. */
53 unsigned iFree;
54 /** Pointer to the array of free objects for this bin. */
55 void **papvFree;
56} IOBUFMGRBIN;
57typedef IOBUFMGRBIN *PIOBUFMGRBIN;
58
59/**
60 * Internal I/O buffer manager data.
61 */
62typedef struct IOBUFMGRINT
63{
64 /** Critical section protecting the allocation path. */
65 RTCRITSECT CritSectAlloc;
66 /** Flags the manager was created with. */
67 uint32_t fFlags;
68 /** Maximum size of I/O memory to allocate. */
69 size_t cbMax;
70 /** Amount of free memory. */
71 size_t cbFree;
72 /** The order of smallest bin. */
73 uint32_t u32OrderMin;
74 /** The order of largest bin. */
75 uint32_t u32OrderMax;
76 /** Pointer to the base memory of the allocation. */
77 void *pvMem;
78 /** Number of bins for free objects. */
79 unsigned cBins;
80 /** Array of bins. */
81 PIOBUFMGRBIN paBins;
82 /** Array of pointer entries for the various bins - variable in size. */
83 void *apvObj[1];
84} IOBUFMGRINT;
85
86/* Must be included after IOBUFDESCINT was defined. */
87#define IOBUFDESCINT_DECLARED
88#include "IOBufMgmt.h"
89
90DECLINLINE(unsigned) iobufMgrGetBinCount(size_t cbMin, size_t cbMax)
91{
92 unsigned u32Max = ASMBitLastSetU32((uint32_t)cbMax);
93 unsigned u32Min = ASMBitLastSetU32((uint32_t)cbMin);
94
95 Assert(cbMax >= cbMin && cbMax != 0 && cbMin != 0);
96 return u32Max - u32Min + 1;
97}
98
99DECLINLINE(uint32_t) iobufMgrGetObjCount(size_t cbMem, unsigned cBins, size_t cbMinBin)
100{
101 size_t cObjs = 0;
102 size_t cbBin = cbMinBin;
103
104 while (cBins-- > 0)
105 {
106 cObjs += cbMem / cbBin;
107 cbBin <<= 1; /* The size doubles for every bin. */
108 }
109
110 Assert((uint32_t)cObjs == cObjs);
111 return (uint32_t)cObjs;
112}
113
114DECLHIDDEN(int) IOBUFMgrCreate(PIOBUFMGR phIoBufMgr, size_t cbMax, uint32_t fFlags)
115{
116 int rc = VINF_SUCCESS;
117
118 AssertPtrReturn(phIoBufMgr, VERR_INVALID_POINTER);
119 AssertReturn(cbMax, VERR_NOT_IMPLEMENTED);
120
121 /* Allocate the basic structure in one go. */
122 unsigned cBins = iobufMgrGetBinCount(IOBUFMGR_BIN_SIZE_MIN, IOBUFMGR_BIN_SIZE_MAX);
123 uint32_t cObjs = iobufMgrGetObjCount(cbMax, cBins, IOBUFMGR_BIN_SIZE_MIN);
124 PIOBUFMGRINT pThis = (PIOBUFMGRINT)RTMemAllocZ(RT_OFFSETOF(IOBUFMGRINT, apvObj[cObjs]) + cBins * sizeof(IOBUFMGRBIN));
125 if (RT_LIKELY(pThis))
126 {
127 pThis->fFlags = fFlags;
128 pThis->cbMax = cbMax;
129 pThis->cbFree = cbMax;
130 pThis->cBins = cBins;
131 pThis->u32OrderMin = ASMBitLastSetU32(IOBUFMGR_BIN_SIZE_MIN) - 1;
132 pThis->u32OrderMax = ASMBitLastSetU32(IOBUFMGR_BIN_SIZE_MAX) - 1;
133 pThis->paBins = (PIOBUFMGRBIN)((uint8_t *)pThis + RT_OFFSETOF(IOBUFMGRINT, apvObj[cObjs]));
134
135 rc = RTCritSectInit(&pThis->CritSectAlloc);
136 if (RT_SUCCESS(rc))
137 {
138 if (pThis->fFlags & IOBUFMGR_F_REQUIRE_NOT_PAGABLE)
139 rc = RTMemSaferAllocZEx(&pThis->pvMem, RT_ALIGN_Z(pThis->cbMax, _4K),
140 RTMEMSAFER_F_REQUIRE_NOT_PAGABLE);
141 else
142 pThis->pvMem = RTMemPageAllocZ(RT_ALIGN_Z(pThis->cbMax, _4K));
143
144 if ( RT_LIKELY(pThis->pvMem)
145 && RT_SUCCESS(rc))
146 {
147 /* Init the bins. */
148 size_t iObj = 0;
149 uint32_t cbBin = IOBUFMGR_BIN_SIZE_MIN;
150 for (unsigned i = 0; i < cBins; i++)
151 {
152 PIOBUFMGRBIN pBin = &pThis->paBins[i];
153 pBin->iFree = 0;
154 pBin->papvFree = &pThis->apvObj[iObj];
155 iObj += cbMax / cbBin;
156
157 /* Init the biggest possible bin with the free objects. */
158 if ( (cbBin << 1) > cbMax
159 || i == cBins - 1)
160 {
161 uint8_t *pbMem = (uint8_t *)pThis->pvMem;
162 while (cbMax)
163 {
164 pBin->papvFree[pBin->iFree] = pbMem;
165 cbMax -= cbBin;
166 pbMem += cbBin;
167 pBin->iFree++;
168
169 if (cbMax < cbBin) /** @todo Populate smaller bins and don't waste memory. */
170 break;
171 }
172
173 /* Limit the number of available bins. */
174 pThis->cBins = i + 1;
175 break;
176 }
177
178 cbBin <<= 1;
179 }
180
181 *phIoBufMgr = pThis;
182 return VINF_SUCCESS;
183 }
184 else
185 rc = VERR_NO_MEMORY;
186
187 RTCritSectDelete(&pThis->CritSectAlloc);
188 }
189
190 RTMemFree(pThis);
191 }
192 else
193 rc = VERR_NO_MEMORY;
194
195 return rc;
196}
197
198DECLHIDDEN(int) IOBUFMgrDestroy(IOBUFMGR hIoBufMgr)
199{
200 PIOBUFMGRINT pThis = hIoBufMgr;
201
202 AssertPtrReturn(pThis, VERR_INVALID_HANDLE);
203
204 int rc = RTCritSectEnter(&pThis->CritSectAlloc);
205 if (RT_SUCCESS(rc))
206 {
207 if (pThis->cbFree == pThis->cbMax)
208 {
209 if (pThis->fFlags & IOBUFMGR_F_REQUIRE_NOT_PAGABLE)
210 RTMemSaferFree(pThis->pvMem, RT_ALIGN_Z(pThis->cbMax, _4K));
211 else
212 RTMemPageFree(pThis->pvMem, RT_ALIGN_Z(pThis->cbMax, _4K));
213
214 RTCritSectLeave(&pThis->CritSectAlloc);
215 RTCritSectDelete(&pThis->CritSectAlloc);
216 RTMemFree(pThis);
217 }
218 else
219 {
220 rc = VERR_INVALID_STATE;
221 RTCritSectLeave(&pThis->CritSectAlloc);
222 }
223 }
224
225 return rc;
226}
227
228static size_t iobufMgrAllocSegment(PIOBUFMGRINT pThis, PRTSGSEG pSeg, size_t cb)
229{
230 size_t cbAlloc = 0;
231
232 /* Round to the next power of two and get the bin to try first. */
233 uint32_t u32Order = ASMBitLastSetU32((uint32_t)cb) - 1;
234 if (cbAlloc & ~RT_BIT_32(u32Order))
235 u32Order <<= 1;
236
237 u32Order = RT_CLAMP(u32Order, pThis->u32OrderMin, pThis->u32OrderMax);
238 unsigned iBin = u32Order - pThis->u32OrderMin;
239
240 /*
241 * Check whether the bin can satisfy the request. If not try the next bigger
242 * bin and so on. If there is nothing to find try the smaller bins.
243 */
244 Assert(iBin < pThis->cBins);
245
246 PIOBUFMGRBIN pBin = &pThis->paBins[iBin];
247 if (pBin->iFree == 0)
248 {
249 unsigned iBinCur = iBin;
250 PIOBUFMGRBIN pBinCur = &pThis->paBins[iBinCur];
251
252 while (iBinCur < pThis->cBins)
253 {
254 if (pBinCur->iFree != 0)
255 {
256 pBinCur->iFree--;
257 uint8_t *pbMem = (uint8_t *)pBinCur->papvFree[pBinCur->iFree];
258 AssertPtr(pbMem);
259
260 /* Always split into half. */
261 while (iBinCur > iBin)
262 {
263 iBinCur--;
264 pBinCur = &pThis->paBins[iBinCur];
265 pBinCur->papvFree[pBinCur->iFree] = pbMem + (size_t)RT_BIT(iBinCur + pThis->u32OrderMin); /* (RT_BIT causes weird MSC warning without cast) */
266 pBinCur->iFree++;
267 }
268
269 /* For the last bin we will get two new memory blocks. */
270 pBinCur->papvFree[pBinCur->iFree] = pbMem;
271 pBinCur->iFree++;
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 /** @todo Defragment in case there is enough memory free but we can't find something in our bin. */
285 if ( pBin->iFree == 0
286 && iBin > 0)
287 {
288 do
289 {
290 iBin--;
291 pBin = &pThis->paBins[iBin];
292
293 if (pBin->iFree != 0)
294 {
295 pBin->iFree--;
296 pSeg->pvSeg = pBin->papvFree[pBin->iFree];
297 pSeg->cbSeg = (size_t)RT_BIT_32(iBin + pThis->u32OrderMin);
298 AssertPtr(pSeg->pvSeg);
299 cbAlloc = pSeg->cbSeg;
300 break;
301 }
302 }
303 while (iBin > 0);
304 }
305 else if (pBin->iFree != 0)
306 {
307 pBin->iFree--;
308 pSeg->pvSeg = pBin->papvFree[pBin->iFree];
309 pSeg->cbSeg = (size_t)RT_BIT_32(u32Order);
310 cbAlloc = pSeg->cbSeg;
311 AssertPtr(pSeg->pvSeg);
312 }
313
314 return cbAlloc;
315}
316
317DECLHIDDEN(int) IOBUFMgrAllocBuf(IOBUFMGR hIoBufMgr, PIOBUFDESC pIoBufDesc, size_t cbIoBuf,
318 size_t *pcbIoBufAllocated)
319{
320 PIOBUFMGRINT pThis = hIoBufMgr;
321
322 AssertPtrReturn(pThis, VERR_INVALID_HANDLE);
323
324 if (!pThis->cbFree)
325 return VERR_NO_MEMORY;
326
327 int rc = RTCritSectEnter(&pThis->CritSectAlloc);
328 if (RT_SUCCESS(rc))
329 {
330 unsigned iSeg = 0;
331 size_t cbLeft = cbIoBuf;
332 PRTSGSEG pSeg = &pIoBufDesc->Int.aSegs[0];
333
334 while ( iSeg < RT_ELEMENTS(pIoBufDesc->Int.aSegs)
335 && cbLeft)
336 {
337 size_t cbAlloc = iobufMgrAllocSegment(pThis, pSeg, cbLeft);
338 if (!cbAlloc)
339 break;
340
341 iSeg++;
342 pSeg++;
343 cbLeft -= RT_MIN(cbAlloc, cbLeft);
344 }
345
346 if (iSeg)
347 RTSgBufInit(&pIoBufDesc->SgBuf, &pIoBufDesc->Int.aSegs[0], iSeg);
348 else
349 rc = VERR_NO_MEMORY;
350
351 pIoBufDesc->Int.cSegsUsed = iSeg;
352 pIoBufDesc->Int.pIoBufMgr = pThis;
353 *pcbIoBufAllocated = cbIoBuf - cbLeft;
354
355 pThis->cbFree -= cbIoBuf - cbLeft;
356
357 RTCritSectLeave(&pThis->CritSectAlloc);
358 }
359
360 return rc;
361}
362
363DECLHIDDEN(void) IOBUFMgrFreeBuf(PIOBUFDESC pIoBufDesc)
364{
365 PIOBUFMGRINT pThis = pIoBufDesc->Int.pIoBufMgr;
366
367 AssertPtr(pThis);
368
369 int rc = RTCritSectEnter(&pThis->CritSectAlloc);
370 AssertRC(rc);
371
372 if (RT_SUCCESS(rc))
373 {
374 for (unsigned i = 0; i < pIoBufDesc->Int.cSegsUsed; i++)
375 {
376 PRTSGSEG pSeg = &pIoBufDesc->Int.aSegs[i];
377
378 uint32_t u32Order = ASMBitLastSetU32((uint32_t)pSeg->cbSeg) - 1;
379 unsigned iBin = u32Order - pThis->u32OrderMin;
380
381 Assert(iBin < pThis->cBins);
382 PIOBUFMGRBIN pBin = &pThis->paBins[iBin];
383 pBin->papvFree[pBin->iFree] = pSeg->pvSeg;
384 pBin->iFree++;
385 pThis->cbFree += (size_t)RT_BIT_32(u32Order);
386 }
387 RTCritSectLeave(&pThis->CritSectAlloc);
388 }
389
390 pIoBufDesc->Int.cSegsUsed = 0;
391}
392
Note: See TracBrowser for help on using the repository browser.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette