VirtualBox

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

Last change on this file since 46200 was 46200, checked in by vboxsync, 12 years ago

bugfix.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 36.5 KB
Line 
1/* $Id: strcache.cpp 46200 2013-05-21 19:56:28Z 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.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 * 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 */
112typedef 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;
125AssertCompileSize(RTSTRCACHEENTRY, 16);
126/** Pointer to a string cache entry. */
127typedef RTSTRCACHEENTRY *PRTSTRCACHEENTRY;
128/** Pointer to a const string cache entry. */
129typedef 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 */
139typedef 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;
150AssertCompileSize(RTSTRCACHEENTRY, 16);
151/** Pointer to a big string cache entry. */
152typedef RTSTRCACHEBIGENTRY *PRTSTRCACHEBIGENTRY;
153/** Pointer to a const big string cache entry. */
154typedef RTSTRCACHEBIGENTRY *PCRTSTRCACHEBIGENTRY;
155
156
157/**
158 * A free string cache entry.
159 */
160typedef 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;
169AssertCompileSize(RTSTRCACHEENTRY, 16);
170AssertCompileMembersAtSameOffset(RTSTRCACHEENTRY, cRefs, RTSTRCACHEFREE, uZero);
171AssertCompileMembersAtSameOffset(RTSTRCACHEENTRY, szString, RTSTRCACHEFREE, pNext);
172/** Pointer to a free string cache entry. */
173typedef 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 */
182typedef 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;
197AssertCompileSize(RTSTRCACHEFREEMERGE, RT_BIT_32(RTSTRCACHE_MERGED_THRESHOLD_BIT));
198/** Pointer to a free cache string in the merge list. */
199typedef 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 */
217typedef 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;
224AssertCompileSize(RTSTRCACHECHUNK, 16);
225/** Pointer to the chunk tracking structure. */
226typedef RTSTRCACHECHUNK *PRTSTRCACHECHUNK;
227
228
229/**
230 * Cache instance data.
231 */
232typedef 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. */
256typedef RTSTRCACHEINT *PRTSTRCACHEINT;
257
258
259
260/*******************************************************************************
261* Global Variables *
262*******************************************************************************/
263/** Init once for the default string cache. */
264static RTONCE g_rtStrCacheOnce = RTONCE_INITIALIZER;
265/** The default string cache. */
266static RTSTRCACHE g_hrtStrCacheDefault = NIL_RTSTRCACHE;
267
268
269/** @callback_method_impl{FNRTONCE, Initializes g_hrtStrCacheDefault} */
270static DECLCALLBACK(int) rtStrCacheInitDefault(void *pvUser)
271{
272 NOREF(pvUser);
273 return RTStrCacheCreate(&g_hrtStrCacheDefault, "Default");
274}
275
276
277RTDECL(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}
305RT_EXPORT_SYMBOL(RTStrCacheCreate);
306
307
308RTDECL(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}
347RT_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 */
355static 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 */
379static 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 */
405static 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 */
426static 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 */
476static 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 */
514static 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 */
628static 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 */
700static 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 {
726 if (pEntry->cchString != RTSTRCACHEENTRY_BIG_LEN)
727 {
728 if ( !memcmp(pEntry->szString, pchString, cchString)
729 && pEntry->szString[cchString] == '\0')
730 return pEntry;
731 }
732 else
733 {
734 PRTSTRCACHEBIGENTRY pBigEntry = RT_FROM_MEMBER(pEntry, RTSTRCACHEBIGENTRY, Core);
735 if ( pBigEntry->cchString == cchString
736 && !memcmp(pBigEntry->Core.szString, pchString, cchString))
737 return &pBigEntry->Core;
738 }
739 }
740 }
741 /* Record the first NIL index for insertion in case we don't get a hit. */
742 else if (*piFreeHashTabEntry == UINT32_MAX)
743 *piFreeHashTabEntry = iHash;
744
745 /* Advance. */
746 iHash += RTSTRCACHE_COLLISION_INCR(uHashLen);
747 iHash %= pThis->cHashTab;
748 }
749}
750
751
752RTDECL(const char *) RTStrCacheEnterN(RTSTRCACHE hStrCache, const char *pchString, size_t cchString)
753{
754 PRTSTRCACHEINT pThis = hStrCache;
755 RTSTRCACHE_VALID_RETURN_RC(pThis, NULL);
756
757
758 /*
759 * Calculate the hash and figure the exact string length, then look for an existing entry.
760 */
761 uint32_t const uHash = sdbmN(pchString, cchString, &cchString);
762 uint32_t const uHashLen = RT_MAKE_U32(uHash, cchString);
763 AssertReturn(cchString < _1G, NULL);
764
765
766 RTCritSectEnter(&pThis->CritSect);
767 RTSTRCACHE_CHECK(pThis);
768
769 uint32_t iFreeHashTabEntry;
770 PRTSTRCACHEENTRY pEntry = rtStrCacheLookUp(pThis, uHashLen, cchString, pchString, &iFreeHashTabEntry);
771 if (pEntry)
772 {
773 uint32_t cRefs = ASMAtomicIncU32(&pEntry->cRefs);
774 Assert(cRefs < UINT32_MAX / 2);
775 }
776 else
777 {
778 /*
779 * Allocate a new entry.
780 */
781 uint32_t cbEntry = cchString + 1U + RT_UOFFSETOF(RTSTRCACHEENTRY, szString);
782 if (cbEntry >= RTSTRCACHE_MERGED_THRESHOLD_BIT)
783 {
784 if (cbEntry <= RTSTRCACHE_HEAP_THRESHOLD)
785 pEntry = rtStrCacheAllocMergedEntry(pThis, uHash, pchString, cchString, cbEntry);
786 else
787 pEntry = rtStrCacheAllocHeapEntry(pThis, uHash, pchString, cchString);
788 }
789 else
790 pEntry = rtStrCacheAllocFixedEntry(pThis, uHash, pchString, cchString, cbEntry > 16);
791 if (!pEntry)
792 {
793 RTSTRCACHE_CHECK(pThis);
794 RTCritSectLeave(&pThis->CritSect);
795 return NULL;
796 }
797
798 /*
799 * Insert it into the hash table.
800 */
801 if (pThis->cHashTab - pThis->cStrings < pThis->cHashTab / 2)
802 {
803 int rc = rtStrCacheGrowHashTab(pThis);
804 if (RT_SUCCESS(rc))
805 iFreeHashTabEntry = rtStrCacheFindEmptyHashTabEntry(pThis, uHashLen);
806 else if (pThis->cHashTab - pThis->cStrings <= pThis->cHashTab / 8) /* 12.5% full => error */
807 {
808 pThis->papHashTab[iFreeHashTabEntry] = pEntry;
809 pThis->cStrings++;
810 RTStrCacheRelease(hStrCache, pEntry->szString);
811
812 RTSTRCACHE_CHECK(pThis);
813 RTCritSectLeave(&pThis->CritSect);
814 return NULL;
815 }
816 }
817
818 pThis->papHashTab[iFreeHashTabEntry] = pEntry;
819 pThis->cStrings++;
820 Assert(pThis->cStrings < pThis->cHashTab && pThis->cStrings > 0);
821 }
822
823 RTSTRCACHE_CHECK(pThis);
824 RTCritSectLeave(&pThis->CritSect);
825 return pEntry->szString;
826}
827RT_EXPORT_SYMBOL(RTStrCacheEnterN);
828
829
830RTDECL(const char *) RTStrCacheEnter(RTSTRCACHE hStrCache, const char *psz)
831{
832 return RTStrCacheEnterN(hStrCache, psz, strlen(psz));
833}
834RT_EXPORT_SYMBOL(RTStrCacheEnter);
835
836
837static const char *rtStrCacheEnterLowerWorker(PRTSTRCACHEINT pThis, const char *pchString, size_t cchString)
838{
839 /*
840 * Try use a dynamic heap buffer first.
841 */
842 if (cchString < 512)
843 {
844 char *pszStackBuf = (char *)alloca(cchString + 1);
845 if (pszStackBuf)
846 {
847 memcpy(pszStackBuf, pchString, cchString);
848 pszStackBuf[cchString] = '\0';
849 RTStrToLower(pszStackBuf);
850 return RTStrCacheEnterN(pThis, pszStackBuf, cchString);
851 }
852 }
853
854 /*
855 * Fall back on heap.
856 */
857 char *pszHeapBuf = (char *)RTMemTmpAlloc(cchString + 1);
858 if (!pszHeapBuf)
859 return NULL;
860 memcpy(pszHeapBuf, pchString, cchString);
861 pszHeapBuf[cchString] = '\0';
862 RTStrToLower(pszHeapBuf);
863 const char *pszRet = RTStrCacheEnterN(pThis, pszHeapBuf, cchString);
864 RTMemTmpFree(pszHeapBuf);
865 return pszRet;
866}
867
868RTDECL(const char *) RTStrCacheEnterLowerN(RTSTRCACHE hStrCache, const char *pchString, size_t cchString)
869{
870 PRTSTRCACHEINT pThis = hStrCache;
871 RTSTRCACHE_VALID_RETURN_RC(pThis, NULL);
872 return rtStrCacheEnterLowerWorker(pThis, pchString, RTStrNLen(pchString, cchString));
873}
874RT_EXPORT_SYMBOL(RTStrCacheEnterLowerN);
875
876
877RTDECL(const char *) RTStrCacheEnterLower(RTSTRCACHE hStrCache, const char *psz)
878{
879 PRTSTRCACHEINT pThis = hStrCache;
880 RTSTRCACHE_VALID_RETURN_RC(pThis, NULL);
881 return rtStrCacheEnterLowerWorker(pThis, psz, strlen(psz));
882}
883RT_EXPORT_SYMBOL(RTStrCacheEnterLower);
884
885
886RTDECL(uint32_t) RTStrCacheRetain(const char *psz)
887{
888 AssertPtr(psz);
889
890 PRTSTRCACHEENTRY pStr = RT_FROM_MEMBER(psz, RTSTRCACHEENTRY, szString);
891 Assert(!((uintptr_t)pStr & 15) || pStr->cchString == RTSTRCACHEENTRY_BIG_LEN);
892
893 uint32_t cRefs = ASMAtomicIncU32(&pStr->cRefs);
894 Assert(cRefs > 1);
895 Assert(cRefs < UINT32_MAX / 2);
896
897 return cRefs;
898}
899RT_EXPORT_SYMBOL(RTStrCacheRetain);
900
901
902static uint32_t rtStrCacheFreeEntry(PRTSTRCACHEINT pThis, PRTSTRCACHEENTRY pStr)
903{
904 RTCritSectEnter(&pThis->CritSect);
905 RTSTRCACHE_CHECK(pThis);
906
907 /* Remove it from the hash table. */
908 uint32_t uHashLen = RT_MAKE_U32(pStr->uHash,
909 pStr->cchString == RTSTRCACHEENTRY_BIG_LEN
910 ? RT_FROM_MEMBER(pStr, RTSTRCACHEBIGENTRY, Core)->cchString
911 : pStr->cchString);
912 uint32_t iHash = uHashLen % pThis->cHashTab;
913 if (pThis->papHashTab[iHash] == pStr)
914 pThis->papHashTab[iHash] = PRTSTRCACHEENTRY_NIL;
915 else
916 {
917 do
918 {
919 AssertBreak(pThis->papHashTab[iHash] != NULL);
920 iHash += RTSTRCACHE_COLLISION_INCR(uHashLen);
921 iHash %= pThis->cHashTab;
922 } while (pThis->papHashTab[iHash] != pStr);
923 if (RT_LIKELY(pThis->papHashTab[iHash] == pStr))
924 pThis->papHashTab[iHash] = PRTSTRCACHEENTRY_NIL;
925 else
926 {
927 AssertFailed();
928 iHash = pThis->cHashTab;
929 while (iHash-- > 0)
930 if (pThis->papHashTab[iHash] == pStr)
931 break;
932 AssertMsgFailed(("iHash=%u cHashTab=%u\n", iHash, pThis->cHashTab));
933 }
934 }
935
936 pThis->cStrings--;
937 Assert(pThis->cStrings < pThis->cHashTab);
938
939 /* Free it. */
940 if (pStr->cchString != RTSTRCACHEENTRY_BIG_LEN)
941 {
942 uint32_t const cbMin = pStr->cchString + 1U + RT_UOFFSETOF(RTSTRCACHEENTRY, szString);
943 if (cbMin <= 32)
944 {
945 /*
946 * No merging, just add it to the list.
947 */
948 uint32_t const iFreeList = cbMin > 16;
949 ASMCompilerBarrier();
950 PRTSTRCACHEFREE pFreeStr = (PRTSTRCACHEFREE)pStr;
951 pFreeStr->cbFree = cbMin;
952 pFreeStr->uZero = 0;
953 pFreeStr->pNext = pThis->apFreeLists[iFreeList];
954 pThis->apFreeLists[iFreeList] = pFreeStr;
955 }
956 else
957 {
958 /*
959 * Complicated mode, we merge with adjecent nodes.
960 */
961 ASMCompilerBarrier();
962 PRTSTRCACHEFREEMERGE pFreeStr = (PRTSTRCACHEFREEMERGE)pStr;
963 pFreeStr->cbFree = RT_ALIGN_32(cbMin, sizeof(*pFreeStr));
964 pFreeStr->uMarker = RTSTRCACHEFREEMERGE_MAIN;
965 pFreeStr->pMain = NULL;
966 RTListInit(&pFreeStr->ListEntry);
967
968 /*
969 * Merge with previous?
970 * (Reading one block back is safe because there is always the
971 * RTSTRCACHECHUNK structure at the head of each memory chunk.)
972 */
973 uint32_t cInternalBlocks = pFreeStr->cbFree / sizeof(*pFreeStr);
974 PRTSTRCACHEFREEMERGE pMain = pFreeStr - 1;
975 if ( pMain->uMarker == RTSTRCACHEFREEMERGE_MAIN
976 || pMain->uMarker == RTSTRCACHEFREEMERGE_PART)
977 {
978 while (pMain->uMarker != RTSTRCACHEFREEMERGE_MAIN)
979 pMain--;
980 pMain->cbFree += pFreeStr->cbFree;
981 }
982 else
983 {
984 pMain = pFreeStr;
985 pFreeStr++;
986 cInternalBlocks--;
987 }
988
989 /*
990 * Mark internal blocks in the string we're freeing.
991 */
992 while (cInternalBlocks-- > 0)
993 {
994 pFreeStr->uMarker = RTSTRCACHEFREEMERGE_PART;
995 pFreeStr->cbFree = 0;
996 pFreeStr->pMain = pMain;
997 RTListInit(&pFreeStr->ListEntry);
998 pFreeStr++;
999 }
1000
1001 /*
1002 * Merge with next? Limitation: We won't try cross page boundraries.
1003 * (pFreeStr points to the next first free enter after the string now.)
1004 */
1005 if ( PAGE_ADDRESS(pFreeStr) == PAGE_ADDRESS(&pFreeStr[-1])
1006 && pFreeStr->uMarker == RTSTRCACHEFREEMERGE_MAIN)
1007 {
1008 pMain->cbFree += pFreeStr->cbFree;
1009 cInternalBlocks = pFreeStr->cbFree / sizeof(*pFreeStr);
1010 Assert(cInternalBlocks > 0);
1011
1012 /* Update the main block we merge with. */
1013 pFreeStr->cbFree = 0;
1014 pFreeStr->uMarker = RTSTRCACHEFREEMERGE_PART;
1015 RTListNodeRemove(&pFreeStr->ListEntry);
1016 RTListInit(&pFreeStr->ListEntry);
1017
1018 /* Change the internal blocks we merged in. */
1019 cInternalBlocks--;
1020 while (cInternalBlocks-- > 0)
1021 {
1022 pFreeStr++;
1023 pFreeStr->pMain = pMain;
1024 Assert(pFreeStr->uMarker == RTSTRCACHEFREEMERGE_PART);
1025 Assert(!pFreeStr->cbFree);
1026 }
1027 }
1028
1029 /*
1030 * Add/relink into the appropriate free list.
1031 */
1032 rtStrCacheRelinkMerged(pThis, pMain);
1033 }
1034 RTSTRCACHE_CHECK(pThis);
1035 RTCritSectLeave(&pThis->CritSect);
1036 }
1037 else
1038 {
1039 /* Big string. */
1040 PRTSTRCACHEBIGENTRY pBigStr = RT_FROM_MEMBER(pStr, RTSTRCACHEBIGENTRY, Core);
1041 RTListNodeRemove(&pBigStr->ListEntry);
1042
1043 RTSTRCACHE_CHECK(pThis);
1044 RTCritSectLeave(&pThis->CritSect);
1045
1046 RTMemFree(pBigStr);
1047 }
1048
1049 return 0;
1050}
1051
1052RTDECL(uint32_t) RTStrCacheRelease(RTSTRCACHE hStrCache, const char *psz)
1053{
1054 if (!psz)
1055 return 0;
1056
1057 PRTSTRCACHEINT pThis = hStrCache;
1058 RTSTRCACHE_VALID_RETURN_RC(pThis, UINT32_MAX);
1059
1060 AssertPtr(psz);
1061 PRTSTRCACHEENTRY pStr = RT_FROM_MEMBER(psz, RTSTRCACHEENTRY, szString);
1062 Assert(!((uintptr_t)pStr & 15) || pStr->cchString == RTSTRCACHEENTRY_BIG_LEN);
1063
1064 /*
1065 * Drop a reference and maybe free the entry.
1066 */
1067 uint32_t cRefs = ASMAtomicDecU32(&pStr->cRefs);
1068 Assert(cRefs < UINT32_MAX / 2);
1069 if (!cRefs)
1070 return rtStrCacheFreeEntry(pThis, pStr);
1071
1072 return cRefs;
1073}
1074RT_EXPORT_SYMBOL(RTStrCacheRelease);
1075
1076
1077RTDECL(size_t) RTStrCacheLength(const char *psz)
1078{
1079 if (!psz)
1080 return 0;
1081
1082 AssertPtr(psz);
1083 PRTSTRCACHEENTRY pStr = RT_FROM_MEMBER(psz, RTSTRCACHEENTRY, szString);
1084 if (pStr->cchString == RTSTRCACHEENTRY_BIG_LEN)
1085 {
1086 PRTSTRCACHEBIGENTRY pBigStr = RT_FROM_MEMBER(psz, RTSTRCACHEBIGENTRY, Core.szString);
1087 return pBigStr->cchString;
1088 }
1089 Assert(!((uintptr_t)pStr & 15));
1090 return pStr->cchString;
1091}
1092RT_EXPORT_SYMBOL(RTStrCacheLength);
1093
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