handletablesimple.cpp@ 99248

Last change on this file since 99248 was 98103, checked in by vboxsync, 2 years ago
Copyright year updates by scm.
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 10.4 KB

Line
1	/* $Id: handletablesimple.cpp 98103 2023-01-17 14:15:46Z vboxsync $ */
2	/** @file
3	* IPRT - Handle Tables.
4	*/
5
6	/*
7	* Copyright (C) 2008-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	* The contents of this file may alternatively be used under the terms
26	* of the Common Development and Distribution License Version 1.0
27	* (CDDL), a copy of it is provided in the "COPYING.CDDL" file included
28	* in the VirtualBox distribution, in which case the provisions of the
29	* CDDL are applicable instead of those of the GPL.
30	*
31	* You may elect to license modified versions of this file under the
32	* terms and conditions of either the GPL or the CDDL or both.
33	*
34	* SPDX-License-Identifier: GPL-3.0-only OR CDDL-1.0
35	*/
36
37
38	/*********************************************************************************************************************************
39	* Header Files *
40	*********************************************************************************************************************************/
41	#include <iprt/handletable.h>
42	#include "internal/iprt.h"
43
44	#include <iprt/mem.h>
45	#include <iprt/spinlock.h>
46	#include <iprt/err.h>
47	#include <iprt/assert.h>
48	#include <iprt/param.h>
49	#include <iprt/string.h>
50	#include <iprt/asm.h>
51	#include "internal/magics.h"
52	#include "handletable.h"
53
54
55	RTDECL(int) RTHandleTableAlloc(RTHANDLETABLE hHandleTable, void pvObj, uint32_t ph)
56	{
57	/* validate the input */
58	PRTHANDLETABLEINT pThis = (PRTHANDLETABLEINT)hHandleTable;
59	AssertPtrReturn(pThis, VERR_INVALID_HANDLE);
60	AssertReturn(pThis->u32Magic == RTHANDLETABLE_MAGIC, VERR_INVALID_HANDLE);
61	AssertReturn(!(pThis->fFlags & RTHANDLETABLE_FLAGS_CONTEXT), VERR_INVALID_FUNCTION);
62	AssertReturn(!RTHT_IS_FREE(pvObj), VERR_INVALID_PARAMETER);
63	AssertPtrReturn(ph, VERR_INVALID_POINTER);
64	*ph = pThis->uBase - 1;
65
66	/*
67	* Allocation loop.
68	*/
69	rtHandleTableLock(pThis);
70
71	int rc;
72	do
73	{
74	/*
75	* Try grab a free entry from the head of the free list.
76	*/
77	uint32_t i = pThis->iFreeHead;
78	if (i != NIL_RTHT_INDEX)
79	{
80	PRTHTENTRYFREE pFree = (PRTHTENTRYFREE)rtHandleTableLookupSimpleIdx(pThis, i);
81	Assert(pFree);
82	if (i == pThis->iFreeTail)
83	pThis->iFreeTail = pThis->iFreeHead = NIL_RTHT_INDEX;
84	else
85	pThis->iFreeHead = RTHT_GET_FREE_IDX(pFree);
86	pThis->cCurAllocated++;
87	Assert(pThis->cCurAllocated <= pThis->cCur);
88
89	/*
90	* Setup the entry and return.
91	*/
92	PRTHTENTRY pEntry = (PRTHTENTRY)pFree;
93	pEntry->pvObj = pvObj;
94	*ph = i + pThis->uBase;
95	rc = VINF_SUCCESS;
96	}
97	/*
98	* Must expand the handle table, unless it's full.
99	*/
100	else if (pThis->cCur >= pThis->cMax)
101	{
102	rc = VERR_NO_MORE_HANDLES;
103	Assert(pThis->cCur == pThis->cCurAllocated);
104	}
105	else
106	{
107	/*
108	* Do we have to expand the 1st level table too?
109	*/
110	uint32_t const iLevel1 = pThis->cCur / RTHT_LEVEL2_ENTRIES;
111	uint32_t cLevel1 = iLevel1 >= pThis->cLevel1
112	? pThis->cLevel1 + PAGE_SIZE / sizeof(void *)
113	: 0;
114	if (cLevel1 > pThis->cMax / RTHT_LEVEL2_ENTRIES)
115	cLevel1 = pThis->cMax / RTHT_LEVEL2_ENTRIES;
116	Assert(!cLevel1 \|\| pThis->cMax / RTHT_LEVEL2_ENTRIES >= RTHT_LEVEL1_DYN_ALLOC_THRESHOLD);
117
118	/* leave the lock (never do fancy stuff from behind a spinlock). */
119	rtHandleTableUnlock(pThis);
120
121	/*
122	* Do the allocation(s).
123	*/
124	rc = VERR_TRY_AGAIN;
125	void **papvLevel1 = NULL;
126	if (cLevel1)
127	{
128	papvLevel1 = (void *)RTMemAlloc(sizeof(void ) * cLevel1);
129	if (!papvLevel1)
130	return VERR_NO_MEMORY;
131	}
132
133	PRTHTENTRY paTable = (PRTHTENTRY)RTMemAlloc(sizeof(paTable) RTHT_LEVEL2_ENTRIES);
134	if (!paTable)
135	{
136	RTMemFree(papvLevel1);
137	return VERR_NO_MEMORY;
138	}
139
140	/* re-enter the lock. */
141	rtHandleTableLock(pThis);
142
143	/*
144	* Insert the new bits, but be a bit careful as someone might have
145	* raced us expanding the table.
146	*/
147	/* deal with the 1st level lookup expansion first */
148	if (cLevel1)
149	{
150	Assert(papvLevel1);
151	if (cLevel1 > pThis->cLevel1)
152	{
153	/* Replace the 1st level table. */
154	memcpy(papvLevel1, pThis->papvLevel1, sizeof(void ) pThis->cLevel1);
155	memset(&papvLevel1[pThis->cLevel1], 0, sizeof(void ) (cLevel1 - pThis->cLevel1));
156	pThis->cLevel1 = cLevel1;
157	void **papvTmp = pThis->papvLevel1;
158	pThis->papvLevel1 = papvLevel1;
159	papvLevel1 = papvTmp;
160	}
161
162	/* free the obsolete one (outside the lock of course) */
163	rtHandleTableUnlock(pThis);
164	RTMemFree(papvLevel1);
165	rtHandleTableLock(pThis);
166	}
167
168	/* insert the table we allocated. */
169	uint32_t iLevel1New = pThis->cCur / RTHT_LEVEL2_ENTRIES;
170	if ( iLevel1New < pThis->cLevel1
171	&& pThis->cCur < pThis->cMax)
172	{
173	pThis->papvLevel1[iLevel1New] = paTable;
174
175	/* link all entries into a free list. */
176	Assert(!(pThis->cCur % RTHT_LEVEL2_ENTRIES));
177	for (i = 0; i < RTHT_LEVEL2_ENTRIES - 1; i++)
178	RTHT_SET_FREE_IDX((PRTHTENTRYFREE)&paTable[i], i + 1 + pThis->cCur);
179	RTHT_SET_FREE_IDX((PRTHTENTRYFREE)&paTable[RTHT_LEVEL2_ENTRIES - 1], NIL_RTHT_INDEX);
180
181	/* join the free list with the other. */
182	if (pThis->iFreeTail == NIL_RTHT_INDEX)
183	pThis->iFreeHead = pThis->cCur;
184	else
185	{
186	PRTHTENTRYFREE pPrev = (PRTHTENTRYFREE)rtHandleTableLookupSimpleIdx(pThis, pThis->iFreeTail);
187	Assert(pPrev);
188	RTHT_SET_FREE_IDX(pPrev, pThis->cCur);
189	}
190	pThis->iFreeTail = pThis->cCur + RTHT_LEVEL2_ENTRIES - 1;
191
192	pThis->cCur += RTHT_LEVEL2_ENTRIES;
193	}
194	else
195	{
196	/* free the table (raced someone, and we lost). */
197	rtHandleTableUnlock(pThis);
198	RTMemFree(paTable);
199	rtHandleTableLock(pThis);
200	}
201
202	rc = VERR_TRY_AGAIN;
203	}
204	} while (rc == VERR_TRY_AGAIN);
205
206	rtHandleTableUnlock(pThis);
207
208	return rc;
209	}
210	RT_EXPORT_SYMBOL(RTHandleTableAlloc);
211
212
213	RTDECL(void *) RTHandleTableLookup(RTHANDLETABLE hHandleTable, uint32_t h)
214	{
215	/* validate the input */
216	PRTHANDLETABLEINT pThis = (PRTHANDLETABLEINT)hHandleTable;
217	AssertPtrReturn(pThis, NULL);
218	AssertReturn(pThis->u32Magic == RTHANDLETABLE_MAGIC, NULL);
219	AssertReturn(!(pThis->fFlags & RTHANDLETABLE_FLAGS_CONTEXT), NULL);
220
221	void *pvObj = NULL;
222
223	/* acquire the lock */
224	rtHandleTableLock(pThis);
225
226	/*
227	* Perform the lookup and retaining.
228	*/
229	PRTHTENTRY pEntry = rtHandleTableLookupSimple(pThis, h);
230	if (pEntry)
231	{
232	pvObj = pEntry->pvObj;
233	if (!RTHT_IS_FREE(pvObj))
234	{
235	if (pThis->pfnRetain)
236	{
237	int rc = pThis->pfnRetain(hHandleTable, pEntry->pvObj, NULL, pThis->pvRetainUser);
238	if (RT_FAILURE(rc))
239	pvObj = NULL;
240	}
241	}
242	else
243	pvObj = NULL;
244	}
245
246	/* release the lock */
247	rtHandleTableUnlock(pThis);
248	return pvObj;
249	}
250	RT_EXPORT_SYMBOL(RTHandleTableLookup);
251
252
253	RTDECL(void *) RTHandleTableFree(RTHANDLETABLE hHandleTable, uint32_t h)
254	{
255	/* validate the input */
256	PRTHANDLETABLEINT pThis = (PRTHANDLETABLEINT)hHandleTable;
257	AssertPtrReturn(pThis, NULL);
258	AssertReturn(pThis->u32Magic == RTHANDLETABLE_MAGIC, NULL);
259	AssertReturn(!(pThis->fFlags & RTHANDLETABLE_FLAGS_CONTEXT), NULL);
260
261	void *pvObj = NULL;
262
263	/* acquire the lock */
264	rtHandleTableLock(pThis);
265
266	/*
267	* Perform the lookup and retaining.
268	*/
269	PRTHTENTRY pEntry = rtHandleTableLookupSimple(pThis, h);
270	if (pEntry)
271	{
272	pvObj = pEntry->pvObj;
273	if (!RTHT_IS_FREE(pvObj))
274	{
275	if (pThis->pfnRetain)
276	{
277	int rc = pThis->pfnRetain(hHandleTable, pEntry->pvObj, NULL, pThis->pvRetainUser);
278	if (RT_FAILURE(rc))
279	pvObj = NULL;
280	}
281
282	/*
283	* Link it into the free list.
284	*/
285	if (pvObj)
286	{
287	PRTHTENTRYFREE pFree = (PRTHTENTRYFREE)pEntry;
288	RTHT_SET_FREE_IDX(pFree, NIL_RTHT_INDEX);
289
290	uint32_t const i = h - pThis->uBase;
291	if (pThis->iFreeTail == NIL_RTHT_INDEX)
292	pThis->iFreeHead = pThis->iFreeTail = i;
293	else
294	{
295	PRTHTENTRYFREE pPrev = (PRTHTENTRYFREE)rtHandleTableLookupSimpleIdx(pThis, pThis->iFreeTail);
296	Assert(pPrev);
297	RTHT_SET_FREE_IDX(pPrev, i);
298	pThis->iFreeTail = i;
299	}
300
301	Assert(pThis->cCurAllocated > 0);
302	pThis->cCurAllocated--;
303	}
304	}
305	else
306	pvObj = NULL;
307	}
308
309	/* release the lock */
310	rtHandleTableUnlock(pThis);
311	return pvObj;
312	}
313	RT_EXPORT_SYMBOL(RTHandleTableFree);
314

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

source: vbox/trunk/src/VBox/Runtime/common/misc/handletablesimple.cpp@ 99248

Download in other formats: