strcache.cpp@ 46198

Last change on this file since 46198 was 46198, checked in by vboxsync, 12 years ago
strcache.cpp: Reimplemented as a real string cache.
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 35.7 KB

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

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

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

Download in other formats: