Changeset 46198 in vbox for trunk/src/VBox/Runtime/common/string/strcache.cpp
- Timestamp:
- May 21, 2013 7:30:52 PM (12 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/src/VBox/Runtime/common/string/strcache.cpp
r46108 r46198 5 5 6 6 /* 7 * Copyright (C) 2009-201 0Oracle Corporation7 * Copyright (C) 2009-2013 Oracle Corporation 8 8 * 9 9 * This file is part of VirtualBox Open Source Edition (OSE), as … … 32 32 #include "internal/iprt.h" 33 33 34 #include <iprt/alloca.h> 34 35 #include <iprt/asm.h> 35 36 #include <iprt/assert.h> 37 #include <iprt/critsect.h> 36 38 #include <iprt/err.h> 37 #include <iprt/mempool.h> 39 #include <iprt/list.h> 40 #include <iprt/mem.h> 41 #include <iprt/once.h> 42 #include <iprt/param.h> 38 43 #include <iprt/string.h> 39 #include <iprt/once.h> 40 41 42 /******************************************************************************* 43 * Structures and Typedefs * 44 *******************************************************************************/ 45 /** 46 * String cache entry. 47 * 48 * Each entry is 49 */ 50 typedef struct RTSTRCACHEENTRY 51 { 52 /** The number of references. */ 53 uint32_t volatile cRefs; 54 /** Offset into the chunk (bytes). */ 55 uint32_t offChunk; 56 /** The string length. */ 57 uint32_t cch; 58 /** The primary hash value. */ 59 uint32_t uHash1; 60 /** The string. */ 61 char szString[16]; 62 } RTSTRCACHEENTRY; 63 AssertCompileSize(RTSTRCACHEENTRY, 32); 64 /** Pointer to a string cache entry. */ 65 typedef RTSTRCACHEENTRY *PRTSTRCACHEENTRY; 66 /** Pointer to a const string cache entry. */ 67 typedef RTSTRCACHEENTRY *PCRTSTRCACHEENTRY; 68 69 /** 70 * Allocation chunk. 71 */ 72 typedef struct RTSTRCACHECHUNK 73 { 74 /** Pointer to the main string cache structure. */ 75 struct RTSTRCACHEINT *pCache; 76 /** Padding to align the entries on a 32-byte boundary. */ 77 uint32_t au32Padding[8 - (ARCH_BITS == 64) - 4]; 78 /** The index of the first unused entry. */ 79 uint32_t iUnused; 80 /** The number of used entries. */ 81 uint32_t cUsed; 82 /** The number of entries in this chunk. */ 83 uint32_t cEntries; 84 /** The string cache entries, variable size. */ 85 RTSTRCACHEENTRY aEntries[1]; 86 } RTSTRCACHECHUNK; 87 88 89 typedef struct RTSTRCACHEINT 90 { 91 /** The string cache magic (RTSTRCACHE_MAGIC). */ 92 uint32_t u32Magic; 93 94 } RTSTRCACHEINT; 95 96 44 45 #include "internal/strhash.h" 46 #include "internal/magics.h" 97 47 98 48 … … 100 50 * Defined Constants And Macros * 101 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 102 78 /** Validates a string cache handle, translating RTSTRCACHE_DEFAULT when found, 103 79 * and returns rc if not valid. */ 104 80 #define RTSTRCACHE_VALID_RETURN_RC(pStrCache, rc) \ 105 81 do { \ 106 if ((pStrCache) == RTMEMPOOL_DEFAULT) \ 107 (pStrCache) = &g_rtMemPoolDefault; \ 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 } \ 108 89 else \ 109 90 { \ … … 113 94 } while (0) 114 95 115 /** Validates a memory pool entry and returns rc if not valid. */ 116 #define RTSTRCACHE_VALID_ENTRY_RETURN_RC(pEntry, rc) \ 117 do { \ 118 AssertPtrReturn(pEntry, (rc)); \ 119 AssertPtrNullReturn((pEntry)->pMemPool, (rc)); \ 120 Assert((pEntry)->cRefs < UINT32_MAX / 2); \ 121 AssertReturn((pEntry)->pMemPool->u32Magic == RTMEMPOOL_MAGIC, (rc)); \ 122 } while (0) 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 123 250 124 251 … … 126 253 * Global Variables * 127 254 *******************************************************************************/ 128 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 } 129 267 130 268 131 269 RTDECL(int) RTStrCacheCreate(PRTSTRCACHE phStrCache, const char *pszName) 132 270 { 133 AssertCompile(sizeof(RTSTRCACHE) == sizeof(RTMEMPOOL)); 134 AssertCompile(NIL_RTSTRCACHE == (RTSTRCACHE)NIL_RTMEMPOOL); 135 AssertCompile(RTSTRCACHE_DEFAULT == (RTSTRCACHE)RTMEMPOOL_DEFAULT); 136 return RTMemPoolCreate((PRTMEMPOOL)phStrCache, pszName); 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; 137 296 } 138 297 RT_EXPORT_SYMBOL(RTStrCacheCreate); … … 141 300 RTDECL(int) RTStrCacheDestroy(RTSTRCACHE hStrCache) 142 301 { 143 if ( 144 || 302 if ( hStrCache == NIL_RTSTRCACHE 303 || hStrCache == RTSTRCACHE_DEFAULT) 145 304 return VINF_SUCCESS; 146 return RTMemPoolDestroy((RTMEMPOOL)hStrCache); 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; 147 338 } 148 339 RT_EXPORT_SYMBOL(RTStrCacheDestroy); 149 340 150 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 151 732 RTDECL(const char *) RTStrCacheEnterN(RTSTRCACHE hStrCache, const char *pchString, size_t cchString) 152 733 { 153 AssertPtr(pchString); 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); 154 743 AssertReturn(cchString < _1G, NULL); 155 Assert(!RTStrEnd(pchString, cchString)); 156 157 return (const char *)RTMemPoolDupEx((RTMEMPOOL)hStrCache, pchString, cchString, 1); 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; 158 806 } 159 807 RT_EXPORT_SYMBOL(RTStrCacheEnterN); … … 167 815 168 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 169 848 RTDECL(const char *) RTStrCacheEnterLowerN(RTSTRCACHE hStrCache, const char *pchString, size_t cchString) 170 849 { 171 AssertPtr(pchString); 172 AssertReturn(cchString < _1G, NULL); 173 Assert(!RTStrEnd(pchString, cchString)); 174 175 char *pszRet = (char *)RTMemPoolDupEx((RTMEMPOOL)hStrCache, pchString, cchString, 1); 176 if (pszRet) 177 RTStrToLower(pszRet); 178 return pszRet; 850 PRTSTRCACHEINT pThis = hStrCache; 851 RTSTRCACHE_VALID_RETURN_RC(pThis, NULL); 852 return rtStrCacheEnterLowerWorker(pThis, pchString, RTStrNLen(pchString, cchString)); 179 853 } 180 854 RT_EXPORT_SYMBOL(RTStrCacheEnterLowerN); … … 183 857 RTDECL(const char *) RTStrCacheEnterLower(RTSTRCACHE hStrCache, const char *psz) 184 858 { 185 return RTStrCacheEnterLowerN(hStrCache, psz, strlen(psz)); 859 PRTSTRCACHEINT pThis = hStrCache; 860 RTSTRCACHE_VALID_RETURN_RC(pThis, NULL); 861 return rtStrCacheEnterLowerWorker(pThis, psz, strlen(psz)); 186 862 } 187 863 RT_EXPORT_SYMBOL(RTStrCacheEnterLower); … … 191 867 { 192 868 AssertPtr(psz); 193 return RTMemPoolRetain((void *)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; 194 878 } 195 879 RT_EXPORT_SYMBOL(RTStrCacheRetain); 196 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 } 197 1031 198 1032 RTDECL(uint32_t) RTStrCacheRelease(RTSTRCACHE hStrCache, const char *psz) … … 200 1034 if (!psz) 201 1035 return 0; 202 return RTMemPoolRelease((RTMEMPOOL)hStrCache, (void *)psz); 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; 203 1053 } 204 1054 RT_EXPORT_SYMBOL(RTStrCacheRelease); … … 209 1059 if (!psz) 210 1060 return 0; 211 return strlen(psz); 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; 212 1071 } 213 1072 RT_EXPORT_SYMBOL(RTStrCacheLength);
Note:
See TracChangeset
for help on using the changeset viewer.
