strcache.cpp@ 46199

Last change on this file since 46199 was 46199, checked in by vboxsync, 12 years ago
strcache.cpp: Enabled it. Some tuning.
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 36.0 KB

Line
1	/* $Id: strcache.cpp 46199 2013-05-21 19:49:19Z vboxsync $ */
2	/** @file
3	* IPRT - String Cache.
4	*/
5
6	/*
7	* Copyright (C) 2009-2013 Oracle Corporation
8	*
9	* This file is part of VirtualBox Open Source Edition (OSE), as
10	* available from http://www.215389.xyz. 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	* The contents of this file may alternatively be used under the terms
18	* of the Common Development and Distribution License Version 1.0
19	* (CDDL) only, as it comes in the "COPYING.CDDL" file of the
20	* VirtualBox OSE distribution, in which case the provisions of the
21	* CDDL are applicable instead of those of the GPL.
22	*
23	* You may elect to license modified versions of this file under the
24	* terms and conditions of either the GPL or the CDDL or both.
25	*/
26
27
28	/*******************************************************************************
29	* Header Files *
30	*******************************************************************************/
31	#include <iprt/strcache.h>
32	#include "internal/iprt.h"
33
34	#include <iprt/alloca.h>
35	#include <iprt/asm.h>
36	#include <iprt/assert.h>
37	#include <iprt/critsect.h>
38	#include <iprt/err.h>
39	#include <iprt/list.h>
40	#include <iprt/mem.h>
41	#include <iprt/once.h>
42	#include <iprt/param.h>
43	#include <iprt/string.h>
44
45	#include "internal/strhash.h"
46	#include "internal/magics.h"
47
48
49	/*******************************************************************************
50	* Defined Constants And Macros *
51	*******************************************************************************/
52	/** Special NIL pointer for the hash table. It differs from NULL in that it is
53	* a valid hash table entry when doing a lookup. */
54	#define PRTSTRCACHEENTRY_NIL ((PRTSTRCACHEENTRY)~(uintptr_t)1)
55
56	/** Calcuates the increment when handling a collision.
57	* The current formula makes sure it's always odd so we cannot possibly end
58	* up a cyclic loop with an even sized table. It also takes more bits from
59	* the length part. */
60	#define RTSTRCACHE_COLLISION_INCR(uHashLen) ( ((uHashLen >> 8) \| 1) )
61
62	/**
63	* The RTSTRCACHEENTRY size threshold at which we stop using our own allocator
64	* and switch to the application heap, expressed as a power of two.
65	*
66	* Using a 1KB as a reasonable limit here.
67	*/
68	#define RTSTRCACHE_HEAP_THRESHOLD_BIT 10
69	/** The RTSTRCACHE_HEAP_THRESHOLD_BIT as a byte limit. */
70	#define RTSTRCACHE_HEAP_THRESHOLD RT_BIT_32(RTSTRCACHE_HEAP_THRESHOLD_BIT)
71
72	/**
73	* The RTSTRCACHEENTRY size threshold at which we start using the merge free
74	* list for allocations, expressed as a power of two.
75	*/
76	#define RTSTRCACHE_MERGED_THRESHOLD_BIT 6
77
78
79	/** The number of bytes (power of two) that the merged allocation lists should
80	* be grown by. Must be much greater than RTSTRCACHE_MERGED_THRESHOLD. */
81	#define RTSTRCACHE_MERGED_GROW_SIZE _32K
82	/** The number of bytes (power of two) that the fixed allocation lists should
83	* be grown by. */
84	#define RTSTRCACHE_FIXED_GROW_SIZE _32K
85
86	/** Validates a string cache handle, translating RTSTRCACHE_DEFAULT when found,
87	* and returns rc if not valid. */
88	#define RTSTRCACHE_VALID_RETURN_RC(pStrCache, rc) \
89	do { \
90	if ((pStrCache) == RTSTRCACHE_DEFAULT) \
91	{ \
92	int rcOnce = RTOnce(&g_rtStrCacheOnce, rtStrCacheInitDefault, NULL); \
93	if (RT_FAILURE(rcOnce)) \
94	return (rc); \
95	(pStrCache) = g_hrtStrCacheDefault; \
96	} \
97	else \
98	{ \
99	AssertPtrReturn((pStrCache), (rc)); \
100	AssertReturn((pStrCache)->u32Magic == RTSTRCACHE_MAGIC, (rc)); \
101	} \
102	} while (0)
103
104
105
106	/*******************************************************************************
107	* Structures and Typedefs *
108	*******************************************************************************/
109	/**
110	* String cache entry.
111	*/
112	typedef struct RTSTRCACHEENTRY
113	{
114	/** The number of references. */
115	uint32_t volatile cRefs;
116	/** The lower 16-bit hash value. */
117	uint16_t uHash;
118	/** The string length (excluding the terminator).
119	* If this is set to RTSTRCACHEENTRY_BIG_LEN, this is a BIG entry
120	* (RTSTRCACHEBIGENTRY). */
121	uint16_t cchString;
122	/** The string. */
123	char szString[8];
124	} RTSTRCACHEENTRY;
125	AssertCompileSize(RTSTRCACHEENTRY, 16);
126	/** Pointer to a string cache entry. */
127	typedef RTSTRCACHEENTRY *PRTSTRCACHEENTRY;
128	/** Pointer to a const string cache entry. */
129	typedef RTSTRCACHEENTRY *PCRTSTRCACHEENTRY;
130
131	/** RTSTCACHEENTRY::cchString value for big cache entries. */
132	#define RTSTRCACHEENTRY_BIG_LEN UINT16_MAX
133
134	/**
135	* Big string cache entry.
136	*
137	* These are allocated individually from the application heap.
138	*/
139	typedef struct RTSTRCACHEBIGENTRY
140	{
141	/** List entry. */
142	RTLISTNODE ListEntry;
143	/** The string length. */
144	uint32_t cchString;
145	/** The full hash value / padding. */
146	uint32_t uHash;
147	/** The core entry. */
148	RTSTRCACHEENTRY Core;
149	} RTSTRCACHEBIGENTRY;
150	AssertCompileSize(RTSTRCACHEENTRY, 16);
151	/** Pointer to a big string cache entry. */
152	typedef RTSTRCACHEBIGENTRY *PRTSTRCACHEBIGENTRY;
153	/** Pointer to a const big string cache entry. */
154	typedef RTSTRCACHEBIGENTRY *PCRTSTRCACHEBIGENTRY;
155
156
157	/**
158	* A free string cache entry.
159	*/
160	typedef struct RTSTRCACHEFREE
161	{
162	/** Zero value indicating that it's a free entry (no refs, no hash). */
163	uint32_t uZero;
164	/** Number of free bytes. Only used for > 32 byte allocations. */
165	uint32_t cbFree;
166	/** Pointer to the next free item. */
167	struct RTSTRCACHEFREE *pNext;
168	} RTSTRCACHEFREE;
169	AssertCompileSize(RTSTRCACHEENTRY, 16);
170	AssertCompileMembersAtSameOffset(RTSTRCACHEENTRY, cRefs, RTSTRCACHEFREE, uZero);
171	AssertCompileMembersAtSameOffset(RTSTRCACHEENTRY, szString, RTSTRCACHEFREE, pNext);
172	/** Pointer to a free string cache entry. */
173	typedef RTSTRCACHEFREE *PRTSTRCACHEFREE;
174
175
176	/**
177	* A free string cache entry with merging.
178	*
179	* This differs from RTSTRCACHEFREE only in having a back pointer for more
180	* efficient list management (doubly vs. singly linked lists).
181	*/
182	typedef struct RTSTRCACHEFREEMERGE
183	{
184	/** Marker that indicates what kind of entry this is, either . */
185	uint32_t uMarker;
186	/** Number of free bytes. Only used for > 32 byte allocations. */
187	uint32_t cbFree;
188	/** Pointer to the main node. NULL for main nodes. */
189	struct RTSTRCACHEFREEMERGE *pMain;
190	/** The free list entry. */
191	RTLISTNODE ListEntry;
192	/** Pads the size up to the minimum allocation unit for the merge list.
193	* This both defines the minimum allocation unit and simplifies pointer
194	* manipulation during merging and splitting. */
195	uint8_t abPadding[ARCH_BITS == 32 ? 44 : 32];
196	} RTSTRCACHEFREEMERGE;
197	AssertCompileSize(RTSTRCACHEFREEMERGE, RT_BIT_32(RTSTRCACHE_MERGED_THRESHOLD_BIT));
198	/** Pointer to a free cache string in the merge list. */
199	typedef RTSTRCACHEFREEMERGE *PRTSTRCACHEFREEMERGE;
200
201	/** RTSTRCACHEFREEMERGE::uMarker value indicating that it's the real free chunk
202	* header. Must be something that's invalid UTF-8 for both little and big
203	* endian system. */
204	#define RTSTRCACHEFREEMERGE_MAIN UINT32_C(0xfffffff1)
205	/** RTSTRCACHEFREEMERGE::uMarker value indicating that it's part of a larger
206	* chunk of free memory. Must be something that's invalid UTF-8 for both little
207	* and big endian system. */
208	#define RTSTRCACHEFREEMERGE_PART UINT32_C(0xfffffff2)
209
210
211	/**
212	* Tracking structure chunk of memory used by the 16 byte or 32 byte
213	* allocations.
214	*
215	* This occupies the first entry in the chunk.
216	*/
217	typedef struct RTSTRCACHECHUNK
218	{
219	/** The size of the chunk. */
220	size_t cb;
221	/** Pointer to the next chunk. */
222	struct RTSTRCACHECHUNK *pNext;
223	} RTSTRCACHECHUNK;
224	AssertCompileSize(RTSTRCACHECHUNK, 16);
225	/** Pointer to the chunk tracking structure. */
226	typedef RTSTRCACHECHUNK *PRTSTRCACHECHUNK;
227
228
229	/**
230	* Cache instance data.
231	*/
232	typedef struct RTSTRCACHEINT
233	{
234	/** The string cache magic (RTSTRCACHE_MAGIC). */
235	uint32_t u32Magic;
236	/** Ref counter for the cache handle. */
237	uint32_t volatile cRefs;
238	/** The number of strings currently entered in the cache. */
239	uint32_t cStrings;
240	/** The size of the hash table. */
241	uint32_t cHashTab;
242	/** Pointer to the hash table. */
243	PRTSTRCACHEENTRY *papHashTab;
244	/** Free list for allocations of size: 64+, 16, and 32. */
245	PRTSTRCACHEFREE apFreeLists[2];
246	/** Free lists based on */
247	RTLISTANCHOR aMergedFreeLists[RTSTRCACHE_HEAP_THRESHOLD_BIT - RTSTRCACHE_MERGED_THRESHOLD_BIT + 1];
248	/** List of allocated memory chunks. */
249	PRTSTRCACHECHUNK pChunkList;
250	/** List of big cache entries. */
251	RTLISTANCHOR BigEntryList;
252	/** Critical section protecting the cache structures. */
253	RTCRITSECT CritSect;
254	} RTSTRCACHEINT;
255	/** Pointer to a cache instance. */
256	typedef RTSTRCACHEINT *PRTSTRCACHEINT;
257
258
259
260	/*******************************************************************************
261	* Global Variables *
262	*******************************************************************************/
263	/** Init once for the default string cache. */
264	static RTONCE g_rtStrCacheOnce = RTONCE_INITIALIZER;
265	/** The default string cache. */
266	static RTSTRCACHE g_hrtStrCacheDefault = NIL_RTSTRCACHE;
267
268
269	/** @callback_method_impl{FNRTONCE, Initializes g_hrtStrCacheDefault} */
270	static DECLCALLBACK(int) rtStrCacheInitDefault(void *pvUser)
271	{
272	NOREF(pvUser);
273	return RTStrCacheCreate(&g_hrtStrCacheDefault, "Default");
274	}
275
276
277	RTDECL(int) RTStrCacheCreate(PRTSTRCACHE phStrCache, const char *pszName)
278	{
279	int rc = VERR_NO_MEMORY;
280	PRTSTRCACHEINT pThis = (PRTSTRCACHEINT)RTMemAllocZ(sizeof(*pThis));
281	if (pThis)
282	{
283	pThis->cHashTab = 512;
284	pThis->papHashTab = (PRTSTRCACHEENTRY)RTMemAllocZ(sizeof(pThis->papHashTab[0]) pThis->cHashTab);
285	if (pThis->papHashTab)
286	{
287	rc = RTCritSectInit(&pThis->CritSect);
288	if (RT_SUCCESS(rc))
289	{
290	RTListInit(&pThis->BigEntryList);
291	for (uint32_t i = 0; i < RT_ELEMENTS(pThis->aMergedFreeLists); i++)
292	RTListInit(&pThis->aMergedFreeLists[i]);
293	pThis->cRefs = 1;
294	pThis->u32Magic = RTSTRCACHE_MAGIC;
295
296	*phStrCache = pThis;
297	return VINF_SUCCESS;
298	}
299	RTMemFree(pThis->papHashTab);
300	}
301	RTMemFree(pThis);
302	}
303	return rc;
304	}
305	RT_EXPORT_SYMBOL(RTStrCacheCreate);
306
307
308	RTDECL(int) RTStrCacheDestroy(RTSTRCACHE hStrCache)
309	{
310	if ( hStrCache == NIL_RTSTRCACHE
311	\|\| hStrCache == RTSTRCACHE_DEFAULT)
312	return VINF_SUCCESS;
313
314	PRTSTRCACHEINT pThis = hStrCache;
315	RTSTRCACHE_VALID_RETURN_RC(pThis, VERR_INVALID_HANDLE);
316
317	/*
318	* Invalidate it. Enter the crit sect just to be on the safe side.
319	*/
320	AssertReturn(ASMAtomicCmpXchgU32(&pThis->u32Magic, RTSTRCACHE_MAGIC_DEAD, RTSTRCACHE_MAGIC), VERR_INVALID_HANDLE);
321	RTCritSectEnter(&pThis->CritSect);
322	Assert(pThis->cRefs == 1);
323
324	PRTSTRCACHECHUNK pChunk;
325	while ((pChunk = pThis->pChunkList) != NULL)
326	{
327	pThis->pChunkList = pChunk->pNext;
328	RTMemPageFree(pChunk, pChunk->cb);
329	}
330
331	RTMemFree(pThis->papHashTab);
332	pThis->papHashTab = NULL;
333	pThis->cHashTab = 0;
334
335	PRTSTRCACHEBIGENTRY pCur, pNext;
336	RTListForEachSafe(&pThis->BigEntryList, pCur, pNext, RTSTRCACHEBIGENTRY, ListEntry)
337	{
338	RTMemFree(pCur);
339	}
340
341	RTCritSectLeave(&pThis->CritSect);
342	RTCritSectDelete(&pThis->CritSect);
343
344	RTMemFree(pThis);
345	return VINF_SUCCESS;
346	}
347	RT_EXPORT_SYMBOL(RTStrCacheDestroy);
348
349
350	#ifdef RT_STRICT
351	# define RTSTRCACHE_CHECK(a_pThis) do { rtStrCacheCheck(pThis); } while (0)
352	/**
353	* Internal cache check.
354	*/
355	static void rtStrCacheCheck(PRTSTRCACHEINT pThis)
356	{
357	for (uint32_t i = 0; i < RT_ELEMENTS(pThis->aMergedFreeLists); i++)
358	{
359	PRTSTRCACHEFREEMERGE pFree;
360	RTListForEach(&pThis->aMergedFreeLists[i], pFree, RTSTRCACHEFREEMERGE, ListEntry)
361	{
362	Assert(pFree->uMarker == RTSTRCACHEFREEMERGE_MAIN);
363	Assert(pFree->cbFree > 0);
364	Assert(RT_ALIGN_32(pFree->cbFree, sizeof(*pFree)) == pFree->cbFree);
365	}
366	}
367	}
368	#else
369	# define RTSTRCACHE_CHECK(a_pThis) do { } while (0)
370	#endif
371
372
373	/**
374	* Link/Relink into the free right list.
375	*
376	* @param pThis The string cache instance.
377	* @param pFree The free string entry.
378	*/
379	static void rtStrCacheRelinkMerged(PRTSTRCACHEINT pThis, PRTSTRCACHEFREEMERGE pFree)
380	{
381	Assert(pFree->uMarker == RTSTRCACHEFREEMERGE_MAIN);
382	Assert(pFree->cbFree > 0);
383	Assert(RT_ALIGN_32(pFree->cbFree, sizeof(*pFree)) == pFree->cbFree);
384
385	if (!RTListIsEmpty(&pFree->ListEntry))
386	RTListNodeRemove(&pFree->ListEntry);
387
388	uint32_t iList = (ASMBitLastSetU32(pFree->cbFree) - 1) - RTSTRCACHE_MERGED_THRESHOLD_BIT;
389	if (iList >= RT_ELEMENTS(pThis->aMergedFreeLists))
390	iList = RT_ELEMENTS(pThis->aMergedFreeLists) - 1;
391
392	RTListPrepend(&pThis->aMergedFreeLists[iList], &pFree->ListEntry);
393	}
394
395
396	/**
397	* Finds the first empty hash table entry given a hash+length value.
398	*
399	* ASSUMES that the hash table isn't full.
400	*
401	* @returns Hash table index.
402	* @param pThis The string cache instance.
403	* @param uHashLen The hash + length (not RTSTRCACHEENTRY_BIG_LEN).
404	*/
405	static uint32_t rtStrCacheFindEmptyHashTabEntry(PRTSTRCACHEINT pThis, uint32_t uHashLen)
406	{
407	uint32_t iHash = uHashLen % pThis->cHashTab;
408	for (;;)
409	{
410	PRTSTRCACHEENTRY pEntry = pThis->papHashTab[iHash];
411	if (pEntry == NULL \|\| pEntry == PRTSTRCACHEENTRY_NIL)
412	return iHash;
413
414	/* Advance. */
415	iHash += RTSTRCACHE_COLLISION_INCR(uHashLen);
416	iHash %= pThis->cHashTab;
417	}
418	}
419
420	/**
421	* Grows the hash table.
422	*
423	* @returns vINF_SUCCESS or VERR_NO_MEMORY.
424	* @param pThis The string cache instance.
425	*/
426	static int rtStrCacheGrowHashTab(PRTSTRCACHEINT pThis)
427	{
428	/*
429	* Allocate a new hash table two times the size of the old one.
430	*/
431	uint32_t cNew = pThis->cHashTab * 2;
432	PRTSTRCACHEENTRY papNew = (PRTSTRCACHEENTRY )RTMemAllocZ(sizeof(papNew[0]) * cNew);
433	if (papNew == NULL)
434	return VERR_NO_MEMORY;
435
436	/*
437	* Install the new table and move the items from the old table and into the new one.
438	*/
439	PRTSTRCACHEENTRY *papOld = pThis->papHashTab;
440	uint32_t iOld = pThis->cHashTab;
441
442	pThis->papHashTab = papNew;
443	pThis->cHashTab = cNew;
444
445	while (iOld-- > 0)
446	{
447	PRTSTRCACHEENTRY pEntry = papOld[iOld];
448	if (pEntry != NULL && pEntry != PRTSTRCACHEENTRY_NIL)
449	{
450	uint32_t cchString = pEntry->cchString;
451	if (cchString == RTSTRCACHEENTRY_BIG_LEN)
452	cchString = RT_FROM_MEMBER(pEntry, RTSTRCACHEBIGENTRY, Core)->cchString;
453
454	uint32_t iHash = rtStrCacheFindEmptyHashTabEntry(pThis, RT_MAKE_U32(pEntry->uHash, cchString));
455	pThis->papHashTab[iHash] = pEntry;
456	}
457	}
458
459	/*
460	* Free the old hash table.
461	*/
462	RTMemFree(papOld);
463	return VINF_SUCCESS;
464	}
465
466
467	/**
468	* Allocate a cache entry from the heap.
469	*
470	* @returns Pointer to the cache entry on success, NULL on allocation error.
471	* @param pThis The string cache instance.
472	* @param uHash The full hash of the string.
473	* @param pchString The string.
474	* @param cchString The string length.
475	*/
476	static PRTSTRCACHEENTRY rtStrCacheAllocHeapEntry(PRTSTRCACHEINT pThis, uint32_t uHash,
477	const char *pchString, uint32_t cchString)
478	{
479	/*
480	* Allocate a heap block for storing the string. We do some size aligning
481	* here to encourage the heap to give us optimal alignment.
482	*/
483	size_t cbEntry = RT_UOFFSETOF(RTSTRCACHEBIGENTRY, Core.szString[cchString + 1]);
484	PRTSTRCACHEBIGENTRY pBigEntry = (PRTSTRCACHEBIGENTRY)RTMemAlloc(RT_ALIGN_Z(cbEntry, 64));
485	if (!pBigEntry)
486	return NULL;
487
488	/*
489	* Initialize the block.
490	*/
491	RTListAppend(&pThis->BigEntryList, &pBigEntry->ListEntry);
492	pBigEntry->cchString = cchString;
493	pBigEntry->uHash = uHash;
494	pBigEntry->Core.cRefs = 1;
495	pBigEntry->Core.uHash = (uint16_t)uHash;
496	pBigEntry->Core.cchString = RTSTRCACHEENTRY_BIG_LEN;
497	memcpy(pBigEntry->Core.szString, pchString, cchString);
498	pBigEntry->Core.szString[cchString] = '\0';
499
500	return &pBigEntry->Core;
501	}
502
503
504	/**
505	* Allocate a cache entry from the merged free lists.
506	*
507	* @returns Pointer to the cache entry on success, NULL on allocation error.
508	* @param pThis The string cache instance.
509	* @param uHash The full hash of the string.
510	* @param pchString The string.
511	* @param cchString The string length.
512	* @param cbEntry The required entry size.
513	*/
514	static PRTSTRCACHEENTRY rtStrCacheAllocMergedEntry(PRTSTRCACHEINT pThis, uint32_t uHash,
515	const char *pchString, uint32_t cchString, uint32_t cbEntry)
516	{
517	cbEntry = RT_ALIGN_32(cbEntry, sizeof(RTSTRCACHEFREEMERGE));
518	Assert(cbEntry > cchString);
519
520	/*
521	* Search the list heads first.
522	*/
523	PRTSTRCACHEFREEMERGE pFree = NULL;
524
525	uint32_t iList = ASMBitLastSetU32(cbEntry) - 1;
526	if (!RT_IS_POWER_OF_TWO(cbEntry))
527	iList++;
528	iList -= RTSTRCACHE_MERGED_THRESHOLD_BIT;
529
530	while (iList < RT_ELEMENTS(pThis->aMergedFreeLists))
531	{
532	pFree = RTListGetFirst(&pThis->aMergedFreeLists[iList], RTSTRCACHEFREEMERGE, ListEntry);
533	if (pFree)
534	{
535	/*
536	* Found something. Should we we split it? We split from the end
537	* to avoid having to update all the sub entries.
538	*/
539	Assert(pFree->uMarker == RTSTRCACHEFREEMERGE_MAIN);
540	Assert(pFree->cbFree >= cbEntry);
541	Assert(RT_ALIGN_32(pFree->cbFree, sizeof(*pFree)) == pFree->cbFree);
542
543	if (pFree->cbFree == cbEntry)
544	RTListNodeRemove(&pFree->ListEntry);
545	else
546	{
547	uint32_t cRemainder = (pFree->cbFree - cbEntry) / sizeof(*pFree);
548	PRTSTRCACHEFREEMERGE pRemainder = pFree;
549	pFree += cRemainder;
550
551	Assert((pRemainder->cbFree - cbEntry) == cRemainder * sizeof(*pFree));
552	pRemainder->cbFree = cRemainder * sizeof(*pFree);
553
554	rtStrCacheRelinkMerged(pThis, pRemainder);
555	}
556	break;
557	}
558	iList++;
559	}
560	if (!pFree)
561	{
562	/*
563	* Allocate a new block. (We could search the list below in some
564	* cases, but it's too much effort to write and execute).
565	*/
566	size_t const cbChunk = RTSTRCACHE_MERGED_GROW_SIZE; AssertReturn(cbChunk > cbEntry * 2, NULL);
567	PRTSTRCACHECHUNK pChunk = (PRTSTRCACHECHUNK)RTMemPageAlloc(cbChunk);
568	if (!pChunk)
569	return NULL;
570	pChunk->cb = cbChunk;
571	pChunk->pNext = pThis->pChunkList;
572	pThis->pChunkList = pChunk;
573	AssertCompile(sizeof(pChunk) <= sizeof(pFree));
574
575	/*
576	* Get one node for the allocation at hand.
577	*/
578	pFree = (PRTSTRCACHEFREEMERGE)((uintptr_t)pChunk + sizeof(*pFree));
579
580	/*
581	* Create a free block out of the remainder (always a reminder).
582	*/
583	PRTSTRCACHEFREEMERGE pNewFree = (PRTSTRCACHEFREEMERGE)((uintptr_t)pFree + cbEntry);
584	pNewFree->uMarker = RTSTRCACHEFREEMERGE_MAIN;
585	pNewFree->cbFree = cbChunk - sizeof(*pNewFree) - cbEntry; Assert(pNewFree->cbFree < cbChunk && pNewFree->cbFree > 0);
586	pNewFree->pMain = NULL;
587	RTListInit(&pNewFree->ListEntry);
588
589	uint32_t iInternalBlock = pNewFree->cbFree / sizeof(*pNewFree);
590	while (iInternalBlock-- > 1)
591	{
592	pNewFree[iInternalBlock].uMarker = RTSTRCACHEFREEMERGE_PART;
593	pNewFree[iInternalBlock].cbFree = 0;
594	pNewFree[iInternalBlock].pMain = pNewFree;
595	}
596
597	rtStrCacheRelinkMerged(pThis, pNewFree);
598	}
599
600	/*
601	* Initialize the entry. We zero all bytes we don't use so they cannot
602	* accidentally be mistaken for a free entry.
603	*/
604	ASMCompilerBarrier();
605	PRTSTRCACHEENTRY pEntry = (PRTSTRCACHEENTRY)pFree;
606	pEntry->cRefs = 1;
607	pEntry->uHash = (uint16_t)uHash;
608	pEntry->cchString = (uint16_t)cchString;
609	memcpy(pEntry->szString, pchString, cchString);
610	RT_BZERO(&pEntry->szString[cchString], cbEntry - RT_UOFFSETOF(RTSTRCACHEENTRY, szString) - cchString);
611
612	RTSTRCACHE_CHECK(pThis);
613
614	return pEntry;
615	}
616
617
618	/**
619	* Allocate a cache entry from a fixed size free list.
620	*
621	* @returns Pointer to the cache entry on success, NULL on allocation error.
622	* @param pThis The string cache instance.
623	* @param uHash The full hash of the string.
624	* @param pchString The string.
625	* @param cchString The string length.
626	* @param iFreeList Which free list.
627	*/
628	static PRTSTRCACHEENTRY rtStrCacheAllocFixedEntry(PRTSTRCACHEINT pThis, uint32_t uHash,
629	const char *pchString, uint32_t cchString, uint32_t iFreeList)
630	{
631	/*
632	* Get an entry from the free list. If empty, allocate another chunk of
633	* memory and split it up into free entries of the desired size.
634	*/
635	PRTSTRCACHEFREE pFree = pThis->apFreeLists[iFreeList];
636	if (!pFree)
637	{
638	PRTSTRCACHECHUNK pChunk = (PRTSTRCACHECHUNK)RTMemPageAlloc(RTSTRCACHE_FIXED_GROW_SIZE);
639	if (!pChunk)
640	return NULL;
641	pChunk->cb = PAGE_SIZE;
642	pChunk->pNext = pThis->pChunkList;
643	pThis->pChunkList = pChunk;
644
645	PRTSTRCACHEFREE pPrev = NULL;
646	size_t const cbEntry = 1 << (iFreeList + 4);
647	uint32_t cLeft = PAGE_SIZE / cbEntry - 1;
648	pFree = (PRTSTRCACHEFREE)((uintptr_t)pChunk + cbEntry);
649
650	Assert(sizeof(*pChunk) <= cbEntry);
651	Assert(sizeof(*pFree) <= cbEntry);
652	Assert(cbEntry < PAGE_SIZE / 16);
653
654	while (cLeft-- > 0)
655	{
656	pFree->uZero = 0;
657	pFree->cbFree = cbEntry;
658	pFree->pNext = pPrev;
659	pPrev = pFree;
660	pFree = (PRTSTRCACHEFREE)((uintptr_t)pFree + cbEntry);
661	}
662
663	Assert(pPrev);
664	pThis->apFreeLists[iFreeList] = pFree = pPrev;
665	}
666
667	/*
668	* Unlink it.
669	*/
670	pThis->apFreeLists[iFreeList] = pFree->pNext;
671	ASMCompilerBarrier();
672
673	/*
674	* Initialize the entry.
675	*/
676	PRTSTRCACHEENTRY pEntry = (PRTSTRCACHEENTRY)pFree;
677	pEntry->cRefs = 1;
678	pEntry->uHash = (uint16_t)uHash;
679	pEntry->cchString = (uint16_t)cchString;
680	memcpy(pEntry->szString, pchString, cchString);
681	pEntry->szString[cchString] = '\0';
682
683	return pEntry;
684	}
685
686
687	/**
688	* Looks up a string in the hash table.
689	*
690	* @returns Pointer to the string cache entry, NULL + piFreeHashTabEntry if not
691	* found.
692	* @param pThis The string cache instance.
693	* @param uHashLen The hash + length (not RTSTRCACHEENTRY_BIG_LEN).
694	* @param cchString The real length.
695	* @param pchString The string.
696	* @param piFreeHashTabEntry Where to store the index insertion index if NULL
697	* is returned (same as what
698	* rtStrCacheFindEmptyHashTabEntry would return).
699	*/
700	static PRTSTRCACHEENTRY rtStrCacheLookUp(PRTSTRCACHEINT pThis, uint32_t uHashLen, uint32_t cchString, const char *pchString,
701	uint32_t *piFreeHashTabEntry)
702	{
703	*piFreeHashTabEntry = UINT32_MAX;
704
705	uint16_t cchStringFirst = RT_UOFFSETOF(RTSTRCACHEENTRY, szString[cchString + 1]) < RTSTRCACHE_HEAP_THRESHOLD
706	? (uint16_t)cchString : RTSTRCACHEENTRY_BIG_LEN;
707	uint32_t iHash = uHashLen % pThis->cHashTab;
708	for (;;)
709	{
710	PRTSTRCACHEENTRY pEntry = pThis->papHashTab[iHash];
711
712	/* Give up if NULL, but record the index for insertion. */
713	if (pEntry == NULL)
714	{
715	if (*piFreeHashTabEntry == UINT32_MAX)
716	*piFreeHashTabEntry = iHash;
717	return NULL;
718	}
719
720	if (pEntry != PRTSTRCACHEENTRY_NIL)
721	{
722	/* Compare. */
723	if ( pEntry->uHash == (uint16_t)uHashLen
724	&& pEntry->cchString == cchStringFirst
725	&& !memcmp(pEntry->szString, pchString, cchString)
726	&& pEntry->szString[cchString] == '\0')
727	return pEntry;
728	}
729	/* Record the first NIL index for insertion in case we don't get a hit. */
730	else if (*piFreeHashTabEntry == UINT32_MAX)
731	*piFreeHashTabEntry = iHash;
732
733	/* Advance. */
734	iHash += RTSTRCACHE_COLLISION_INCR(uHashLen);
735	iHash %= pThis->cHashTab;
736	}
737	}
738
739
740	RTDECL(const char ) RTStrCacheEnterN(RTSTRCACHE hStrCache, const char pchString, size_t cchString)
741	{
742	PRTSTRCACHEINT pThis = hStrCache;
743	RTSTRCACHE_VALID_RETURN_RC(pThis, NULL);
744
745
746	/*
747	* Calculate the hash and figure the exact string length, then look for an existing entry.
748	*/
749	uint32_t const uHash = sdbmN(pchString, cchString, &cchString);
750	uint32_t const uHashLen = RT_MAKE_U32(uHash, cchString);
751	AssertReturn(cchString < _1G, NULL);
752
753
754	RTCritSectEnter(&pThis->CritSect);
755	RTSTRCACHE_CHECK(pThis);
756
757	uint32_t iFreeHashTabEntry;
758	PRTSTRCACHEENTRY pEntry = rtStrCacheLookUp(pThis, uHashLen, cchString, pchString, &iFreeHashTabEntry);
759	if (pEntry)
760	{
761	uint32_t cRefs = ASMAtomicIncU32(&pEntry->cRefs);
762	Assert(cRefs < UINT32_MAX / 2);
763	}
764	else
765	{
766	/*
767	* Allocate a new entry.
768	*/
769	uint32_t cbEntry = cchString + 1U + RT_UOFFSETOF(RTSTRCACHEENTRY, szString);
770	if (cbEntry >= RTSTRCACHE_MERGED_THRESHOLD_BIT)
771	{
772	if (cbEntry <= RTSTRCACHE_HEAP_THRESHOLD)
773	pEntry = rtStrCacheAllocMergedEntry(pThis, uHash, pchString, cchString, cbEntry);
774	else
775	pEntry = rtStrCacheAllocHeapEntry(pThis, uHash, pchString, cchString);
776	}
777	else
778	pEntry = rtStrCacheAllocFixedEntry(pThis, uHash, pchString, cchString, cbEntry > 16);
779	if (!pEntry)
780	{
781	RTSTRCACHE_CHECK(pThis);
782	RTCritSectLeave(&pThis->CritSect);
783	return NULL;
784	}
785
786	/*
787	* Insert it into the hash table.
788	*/
789	if (pThis->cHashTab - pThis->cStrings < pThis->cHashTab / 2)
790	{
791	int rc = rtStrCacheGrowHashTab(pThis);
792	if (RT_SUCCESS(rc))
793	iFreeHashTabEntry = rtStrCacheFindEmptyHashTabEntry(pThis, uHashLen);
794	else if (pThis->cHashTab - pThis->cStrings <= pThis->cHashTab / 8) /* 12.5% full => error */
795	{
796	pThis->papHashTab[iFreeHashTabEntry] = pEntry;
797	pThis->cStrings++;
798	RTStrCacheRelease(hStrCache, pEntry->szString);
799
800	RTSTRCACHE_CHECK(pThis);
801	RTCritSectLeave(&pThis->CritSect);
802	return NULL;
803	}
804	}
805
806	pThis->papHashTab[iFreeHashTabEntry] = pEntry;
807	pThis->cStrings++;
808	Assert(pThis->cStrings < pThis->cHashTab && pThis->cStrings > 0);
809	}
810
811	RTSTRCACHE_CHECK(pThis);
812	RTCritSectLeave(&pThis->CritSect);
813	return pEntry->szString;
814	}
815	RT_EXPORT_SYMBOL(RTStrCacheEnterN);
816
817
818	RTDECL(const char ) RTStrCacheEnter(RTSTRCACHE hStrCache, const char psz)
819	{
820	return RTStrCacheEnterN(hStrCache, psz, strlen(psz));
821	}
822	RT_EXPORT_SYMBOL(RTStrCacheEnter);
823
824
825	static const char rtStrCacheEnterLowerWorker(PRTSTRCACHEINT pThis, const char pchString, size_t cchString)
826	{
827	/*
828	* Try use a dynamic heap buffer first.
829	*/
830	if (cchString < 512)
831	{
832	char pszStackBuf = (char )alloca(cchString + 1);
833	if (pszStackBuf)
834	{
835	memcpy(pszStackBuf, pchString, cchString);
836	pszStackBuf[cchString] = '\0';
837	RTStrToLower(pszStackBuf);
838	return RTStrCacheEnterN(pThis, pszStackBuf, cchString);
839	}
840	}
841
842	/*
843	* Fall back on heap.
844	*/
845	char pszHeapBuf = (char )RTMemTmpAlloc(cchString + 1);
846	if (!pszHeapBuf)
847	return NULL;
848	memcpy(pszHeapBuf, pchString, cchString);
849	pszHeapBuf[cchString] = '\0';
850	RTStrToLower(pszHeapBuf);
851	const char *pszRet = RTStrCacheEnterN(pThis, pszHeapBuf, cchString);
852	RTMemTmpFree(pszHeapBuf);
853	return pszRet;
854	}
855
856	RTDECL(const char ) RTStrCacheEnterLowerN(RTSTRCACHE hStrCache, const char pchString, size_t cchString)
857	{
858	PRTSTRCACHEINT pThis = hStrCache;
859	RTSTRCACHE_VALID_RETURN_RC(pThis, NULL);
860	return rtStrCacheEnterLowerWorker(pThis, pchString, RTStrNLen(pchString, cchString));
861	}
862	RT_EXPORT_SYMBOL(RTStrCacheEnterLowerN);
863
864
865	RTDECL(const char ) RTStrCacheEnterLower(RTSTRCACHE hStrCache, const char psz)
866	{
867	PRTSTRCACHEINT pThis = hStrCache;
868	RTSTRCACHE_VALID_RETURN_RC(pThis, NULL);
869	return rtStrCacheEnterLowerWorker(pThis, psz, strlen(psz));
870	}
871	RT_EXPORT_SYMBOL(RTStrCacheEnterLower);
872
873
874	RTDECL(uint32_t) RTStrCacheRetain(const char *psz)
875	{
876	AssertPtr(psz);
877
878	PRTSTRCACHEENTRY pStr = RT_FROM_MEMBER(psz, RTSTRCACHEENTRY, szString);
879	Assert(!((uintptr_t)pStr & 15) \|\| pStr->cchString == RTSTRCACHEENTRY_BIG_LEN);
880
881	uint32_t cRefs = ASMAtomicIncU32(&pStr->cRefs);
882	Assert(cRefs > 1);
883	Assert(cRefs < UINT32_MAX / 2);
884
885	return cRefs;
886	}
887	RT_EXPORT_SYMBOL(RTStrCacheRetain);
888
889
890	static uint32_t rtStrCacheFreeEntry(PRTSTRCACHEINT pThis, PRTSTRCACHEENTRY pStr)
891	{
892	RTCritSectEnter(&pThis->CritSect);
893	RTSTRCACHE_CHECK(pThis);
894
895	/* Remove it from the hash table. */
896	uint32_t uHashLen = RT_MAKE_U32(pStr->uHash,
897	pStr->cchString == RTSTRCACHEENTRY_BIG_LEN
898	? RT_FROM_MEMBER(pStr, RTSTRCACHEBIGENTRY, Core)->cchString
899	: pStr->cchString);
900	uint32_t iHash = uHashLen % pThis->cHashTab;
901	if (pThis->papHashTab[iHash] == pStr)
902	pThis->papHashTab[iHash] = PRTSTRCACHEENTRY_NIL;
903	else
904	{
905	do
906	{
907	AssertBreak(pThis->papHashTab[iHash] != NULL);
908	iHash += RTSTRCACHE_COLLISION_INCR(uHashLen);
909	iHash %= pThis->cHashTab;
910	} while (pThis->papHashTab[iHash] != pStr);
911	if (RT_LIKELY(pThis->papHashTab[iHash] == pStr))
912	pThis->papHashTab[iHash] = PRTSTRCACHEENTRY_NIL;
913	else
914	{
915	AssertFailed();
916	iHash = pThis->cHashTab;
917	while (iHash-- > 0)
918	if (pThis->papHashTab[iHash] == pStr)
919	break;
920	AssertMsgFailed(("iHash=%u cHashTab=%u\n", iHash, pThis->cHashTab));
921	}
922	}
923
924	pThis->cStrings--;
925	Assert(pThis->cStrings < pThis->cHashTab);
926
927	/* Free it. */
928	if (pStr->cchString != RTSTRCACHEENTRY_BIG_LEN)
929	{
930	uint32_t const cbMin = pStr->cchString + 1U + RT_UOFFSETOF(RTSTRCACHEENTRY, szString);
931	if (cbMin <= 32)
932	{
933	/*
934	* No merging, just add it to the list.
935	*/
936	uint32_t const iFreeList = cbMin > 16;
937	ASMCompilerBarrier();
938	PRTSTRCACHEFREE pFreeStr = (PRTSTRCACHEFREE)pStr;
939	pFreeStr->cbFree = cbMin;
940	pFreeStr->uZero = 0;
941	pFreeStr->pNext = pThis->apFreeLists[iFreeList];
942	pThis->apFreeLists[iFreeList] = pFreeStr;
943	}
944	else
945	{
946	/*
947	* Complicated mode, we merge with adjecent nodes.
948	*/
949	ASMCompilerBarrier();
950	PRTSTRCACHEFREEMERGE pFreeStr = (PRTSTRCACHEFREEMERGE)pStr;
951	pFreeStr->cbFree = RT_ALIGN_32(cbMin, sizeof(*pFreeStr));
952	pFreeStr->uMarker = RTSTRCACHEFREEMERGE_MAIN;
953	pFreeStr->pMain = NULL;
954	RTListInit(&pFreeStr->ListEntry);
955
956	/*
957	* Merge with previous?
958	* (Reading one block back is safe because there is always the
959	* RTSTRCACHECHUNK structure at the head of each memory chunk.)
960	*/
961	uint32_t cInternalBlocks = pFreeStr->cbFree / sizeof(*pFreeStr);
962	PRTSTRCACHEFREEMERGE pMain = pFreeStr - 1;
963	if ( pMain->uMarker == RTSTRCACHEFREEMERGE_MAIN
964	\|\| pMain->uMarker == RTSTRCACHEFREEMERGE_PART)
965	{
966	while (pMain->uMarker != RTSTRCACHEFREEMERGE_MAIN)
967	pMain--;
968	pMain->cbFree += pFreeStr->cbFree;
969	}
970	else
971	{
972	pMain = pFreeStr;
973	pFreeStr++;
974	cInternalBlocks--;
975	}
976
977	/*
978	* Mark internal blocks in the string we're freeing.
979	*/
980	while (cInternalBlocks-- > 0)
981	{
982	pFreeStr->uMarker = RTSTRCACHEFREEMERGE_PART;
983	pFreeStr->cbFree = 0;
984	pFreeStr->pMain = pMain;
985	RTListInit(&pFreeStr->ListEntry);
986	pFreeStr++;
987	}
988
989	/*
990	* Merge with next? Limitation: We won't try cross page boundraries.
991	* (pFreeStr points to the next first free enter after the string now.)
992	*/
993	if ( PAGE_ADDRESS(pFreeStr) == PAGE_ADDRESS(&pFreeStr[-1])
994	&& pFreeStr->uMarker == RTSTRCACHEFREEMERGE_MAIN)
995	{
996	pMain->cbFree += pFreeStr->cbFree;
997	cInternalBlocks = pFreeStr->cbFree / sizeof(*pFreeStr);
998	Assert(cInternalBlocks > 0);
999
1000	/* Update the main block we merge with. */
1001	pFreeStr->cbFree = 0;
1002	pFreeStr->uMarker = RTSTRCACHEFREEMERGE_PART;
1003	RTListNodeRemove(&pFreeStr->ListEntry);
1004	RTListInit(&pFreeStr->ListEntry);
1005
1006	/* Change the internal blocks we merged in. */
1007	cInternalBlocks--;
1008	while (cInternalBlocks-- > 0)
1009	{
1010	pFreeStr++;
1011	pFreeStr->pMain = pMain;
1012	Assert(pFreeStr->uMarker == RTSTRCACHEFREEMERGE_PART);
1013	Assert(!pFreeStr->cbFree);
1014	}
1015	}
1016
1017	/*
1018	* Add/relink into the appropriate free list.
1019	*/
1020	rtStrCacheRelinkMerged(pThis, pMain);
1021	}
1022	RTSTRCACHE_CHECK(pThis);
1023	RTCritSectLeave(&pThis->CritSect);
1024	}
1025	else
1026	{
1027	/* Big string. */
1028	PRTSTRCACHEBIGENTRY pBigStr = RT_FROM_MEMBER(pStr, RTSTRCACHEBIGENTRY, Core);
1029	RTListNodeRemove(&pBigStr->ListEntry);
1030
1031	RTSTRCACHE_CHECK(pThis);
1032	RTCritSectLeave(&pThis->CritSect);
1033
1034	RTMemFree(pBigStr);
1035	}
1036
1037	return 0;
1038	}
1039
1040	RTDECL(uint32_t) RTStrCacheRelease(RTSTRCACHE hStrCache, const char *psz)
1041	{
1042	if (!psz)
1043	return 0;
1044
1045	PRTSTRCACHEINT pThis = hStrCache;
1046	RTSTRCACHE_VALID_RETURN_RC(pThis, UINT32_MAX);
1047
1048	AssertPtr(psz);
1049	PRTSTRCACHEENTRY pStr = RT_FROM_MEMBER(psz, RTSTRCACHEENTRY, szString);
1050	Assert(!((uintptr_t)pStr & 15) \|\| pStr->cchString == RTSTRCACHEENTRY_BIG_LEN);
1051
1052	/*
1053	* Drop a reference and maybe free the entry.
1054	*/
1055	uint32_t cRefs = ASMAtomicDecU32(&pStr->cRefs);
1056	Assert(cRefs < UINT32_MAX / 2);
1057	if (!cRefs)
1058	return rtStrCacheFreeEntry(pThis, pStr);
1059
1060	return cRefs;
1061	}
1062	RT_EXPORT_SYMBOL(RTStrCacheRelease);
1063
1064
1065	RTDECL(size_t) RTStrCacheLength(const char *psz)
1066	{
1067	if (!psz)
1068	return 0;
1069
1070	AssertPtr(psz);
1071	PRTSTRCACHEENTRY pStr = RT_FROM_MEMBER(psz, RTSTRCACHEENTRY, szString);
1072	if (pStr->cchString == RTSTRCACHEENTRY_BIG_LEN)
1073	{
1074	PRTSTRCACHEBIGENTRY pBigStr = RT_FROM_MEMBER(psz, RTSTRCACHEBIGENTRY, Core.szString);
1075	return pBigStr->cchString;
1076	}
1077	Assert(!((uintptr_t)pStr & 15));
1078	return pStr->cchString;
1079	}
1080	RT_EXPORT_SYMBOL(RTStrCacheLength);
1081

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

source: vbox/trunk/src/VBox/Runtime/common/string/strcache.cpp@ 46199

Download in other formats: