Index: trunk/src/VBox/Runtime/common/string/strcache.cpp
===================================================================
--- trunk/src/VBox/Runtime/common/string/strcache.cpp	(revision 46108)
+++ trunk/src/VBox/Runtime/common/string/strcache.cpp	(revision 46198)
@@ -5,5 +5,5 @@
 
 /*
- * Copyright (C) 2009-2010 Oracle Corporation
+ * Copyright (C) 2009-2013 Oracle Corporation
  *
  * This file is part of VirtualBox Open Source Edition (OSE), as
@@ -32,67 +32,17 @@
 #include "internal/iprt.h"
 
+#include <iprt/alloca.h>
 #include <iprt/asm.h>
 #include <iprt/assert.h>
+#include <iprt/critsect.h>
 #include <iprt/err.h>
-#include <iprt/mempool.h>
+#include <iprt/list.h>
+#include <iprt/mem.h>
+#include <iprt/once.h>
+#include <iprt/param.h>
 #include <iprt/string.h>
-#include <iprt/once.h>
-
-
-/*******************************************************************************
-*   Structures and Typedefs                                                    *
-*******************************************************************************/
-/**
- * String cache entry.
- *
- * Each entry is
- */
-typedef struct RTSTRCACHEENTRY
-{
-    /** The number of references. */
-    uint32_t volatile   cRefs;
-    /** Offset into the chunk (bytes). */
-    uint32_t            offChunk;
-    /** The string length. */
-    uint32_t            cch;
-    /** The primary hash value. */
-    uint32_t            uHash1;
-    /** The string. */
-    char                szString[16];
-} RTSTRCACHEENTRY;
-AssertCompileSize(RTSTRCACHEENTRY, 32);
-/** Pointer to a string cache entry. */
-typedef RTSTRCACHEENTRY *PRTSTRCACHEENTRY;
-/** Pointer to a const string cache entry. */
-typedef RTSTRCACHEENTRY *PCRTSTRCACHEENTRY;
-
-/**
- * Allocation chunk.
- */
-typedef struct RTSTRCACHECHUNK
-{
-    /** Pointer to the main string cache structure. */
-    struct RTSTRCACHEINT   *pCache;
-    /** Padding to align the entries on a 32-byte boundary. */
-    uint32_t                au32Padding[8 - (ARCH_BITS == 64) - 4];
-    /** The index of the first unused entry. */
-    uint32_t                iUnused;
-    /** The number of used entries. */
-    uint32_t                cUsed;
-    /** The number of entries in this chunk. */
-    uint32_t                cEntries;
-    /** The string cache entries, variable size. */
-    RTSTRCACHEENTRY         aEntries[1];
-} RTSTRCACHECHUNK;
-
-
-typedef struct RTSTRCACHEINT
-{
-    /** The string cache magic (RTSTRCACHE_MAGIC). */
-    uint32_t        u32Magic;
-
-} RTSTRCACHEINT;
-
-
+
+#include "internal/strhash.h"
+#include "internal/magics.h"
 
 
@@ -100,10 +50,41 @@
 *   Defined Constants And Macros                                               *
 *******************************************************************************/
+/** Special NIL pointer for the hash table.  It differs from NULL in that it is
+ * a valid hash table entry when doing a lookup. */
+#define PRTSTRCACHEENTRY_NIL                ((PRTSTRCACHEENTRY)~(uintptr_t)1)
+
+/** Calcuates the increment when handling a collision.
+ * The current formula makes sure it's always odd so we cannot possibly end
+ * up a cyclic loop with an even sized table.  It also takes more bits from
+ * the length part. */
+#define RTSTRCACHE_COLLISION_INCR(uHashLen) ( ((uHashLen >> 8) | 1) )
+
+/**
+ * The RTSTRCACHEENTRY size threshold at which we stop using our own allocator
+ * and switch to the application heap, expressed as a power of two.
+ *
+ * Using a 1KB as a reasonable limit here.
+ */
+#define RTSTRCACHE_HEAP_THRESHOLD_BIT       10
+/** The RTSTRCACHE_HEAP_THRESHOLD_BIT as a byte limit. */
+#define RTSTRCACHE_HEAP_THRESHOLD           RT_BIT_32(RTSTRCACHE_HEAP_THRESHOLD_BIT)
+
+/**
+ * The RTSTRCACHEENTRY size threshold at which we start using the merge free
+ * list for allocations, expressed as a power of two.
+ */
+#define RTSTRCACHE_MERGED_THRESHOLD_BIT     6
+
 /** Validates a string cache handle, translating RTSTRCACHE_DEFAULT when found,
  * and returns rc if not valid. */
 #define RTSTRCACHE_VALID_RETURN_RC(pStrCache, rc) \
     do { \
-        if ((pStrCache) == RTMEMPOOL_DEFAULT) \
-            (pStrCache) = &g_rtMemPoolDefault; \
+        if ((pStrCache) == RTSTRCACHE_DEFAULT) \
+        { \
+            int rcOnce = RTOnce(&g_rtStrCacheOnce, rtStrCacheInitDefault, NULL); \
+            if (RT_FAILURE(rcOnce)) \
+                return (rc); \
+            (pStrCache) = g_hrtStrCacheDefault; \
+        } \
         else \
         { \
@@ -113,12 +94,158 @@
     } while (0)
 
-/** Validates a memory pool entry and returns rc if not valid. */
-#define RTSTRCACHE_VALID_ENTRY_RETURN_RC(pEntry, rc) \
-    do { \
-        AssertPtrReturn(pEntry, (rc)); \
-        AssertPtrNullReturn((pEntry)->pMemPool, (rc)); \
-        Assert((pEntry)->cRefs < UINT32_MAX / 2); \
-        AssertReturn((pEntry)->pMemPool->u32Magic == RTMEMPOOL_MAGIC, (rc)); \
-    } while (0)
+
+
+/*******************************************************************************
+*   Structures and Typedefs                                                    *
+*******************************************************************************/
+/**
+ * String cache entry.
+ */
+typedef struct RTSTRCACHEENTRY
+{
+    /** The number of references. */
+    uint32_t volatile   cRefs;
+    /** The lower 16-bit hash value. */
+    uint16_t            uHash;
+    /** The string length (excluding the terminator).
+     * If this is set to RTSTRCACHEENTRY_BIG_LEN, this is a BIG entry
+     * (RTSTRCACHEBIGENTRY). */
+    uint16_t            cchString;
+    /** The string. */
+    char                szString[8];
+} RTSTRCACHEENTRY;
+AssertCompileSize(RTSTRCACHEENTRY, 16);
+/** Pointer to a string cache entry. */
+typedef RTSTRCACHEENTRY *PRTSTRCACHEENTRY;
+/** Pointer to a const string cache entry. */
+typedef RTSTRCACHEENTRY *PCRTSTRCACHEENTRY;
+
+/** RTSTCACHEENTRY::cchString value for big cache entries. */
+#define RTSTRCACHEENTRY_BIG_LEN UINT16_MAX
+
+/**
+ * Big string cache entry.
+ *
+ * These are allocated individually from the application heap.
+ */
+typedef struct RTSTRCACHEBIGENTRY
+{
+    /** List entry. */
+    RTLISTNODE          ListEntry;
+    /** The string length. */
+    uint32_t            cchString;
+    /** The full hash value / padding. */
+    uint32_t            uHash;
+    /** The core entry. */
+    RTSTRCACHEENTRY     Core;
+} RTSTRCACHEBIGENTRY;
+AssertCompileSize(RTSTRCACHEENTRY, 16);
+/** Pointer to a big string cache entry. */
+typedef RTSTRCACHEBIGENTRY *PRTSTRCACHEBIGENTRY;
+/** Pointer to a const big string cache entry. */
+typedef RTSTRCACHEBIGENTRY *PCRTSTRCACHEBIGENTRY;
+
+
+/**
+ * A free string cache entry.
+ */
+typedef struct RTSTRCACHEFREE
+{
+    /** Zero value indicating that it's a free entry (no refs, no hash). */
+    uint32_t                uZero;
+    /** Number of free bytes.  Only used for > 32 byte allocations. */
+    uint32_t                cbFree;
+    /** Pointer to the next free item. */
+    struct RTSTRCACHEFREE  *pNext;
+} RTSTRCACHEFREE;
+AssertCompileSize(RTSTRCACHEENTRY, 16);
+AssertCompileMembersAtSameOffset(RTSTRCACHEENTRY, cRefs,    RTSTRCACHEFREE, uZero);
+AssertCompileMembersAtSameOffset(RTSTRCACHEENTRY, szString, RTSTRCACHEFREE, pNext);
+/** Pointer to a free string cache entry. */
+typedef RTSTRCACHEFREE *PRTSTRCACHEFREE;
+
+
+/**
+ * A free string cache entry with merging.
+ *
+ * This differs from RTSTRCACHEFREE only in having a back pointer for more
+ * efficient list management (doubly vs. singly linked lists).
+ */
+typedef struct RTSTRCACHEFREEMERGE
+{
+    /** Marker that indicates what kind of entry this is, either . */
+    uint32_t                    uMarker;
+    /** Number of free bytes.  Only used for > 32 byte allocations. */
+    uint32_t                    cbFree;
+    /** Pointer to the main node.  NULL for main nodes. */
+    struct RTSTRCACHEFREEMERGE *pMain;
+    /** The free list entry. */
+    RTLISTNODE                  ListEntry;
+    /** Pads the size up to the minimum allocation unit for the merge list.
+     * This both defines the minimum allocation unit and simplifies pointer
+     * manipulation during merging and splitting. */
+    uint8_t                     abPadding[ARCH_BITS == 32 ? 44 : 32];
+} RTSTRCACHEFREEMERGE;
+AssertCompileSize(RTSTRCACHEFREEMERGE, RT_BIT_32(RTSTRCACHE_MERGED_THRESHOLD_BIT));
+/** Pointer to a free cache string in the merge list. */
+typedef RTSTRCACHEFREEMERGE *PRTSTRCACHEFREEMERGE;
+
+/** RTSTRCACHEFREEMERGE::uMarker value indicating that it's the real free chunk
+ *  header.  Must be something that's invalid UTF-8 for both little and big
+ *  endian system. */
+#define RTSTRCACHEFREEMERGE_MAIN    UINT32_C(0xfffffff1)
+/** RTSTRCACHEFREEMERGE::uMarker value indicating that it's part of a larger
+ * chunk of free memory.  Must be something that's invalid UTF-8 for both little
+ * and big endian system. */
+#define RTSTRCACHEFREEMERGE_PART    UINT32_C(0xfffffff2)
+
+
+/**
+ * Tracking structure chunk of memory used by the 16 byte or 32 byte
+ * allocations.
+ *
+ * This occupies the first entry in the chunk.
+ */
+typedef struct RTSTRCACHECHUNK
+{
+    /** The size of the chunk. */
+    size_t                      cb;
+    /** Pointer to the next chunk. */
+    struct RTSTRCACHECHUNK     *pNext;
+} RTSTRCACHECHUNK;
+AssertCompileSize(RTSTRCACHECHUNK, 16);
+/** Pointer to the chunk tracking structure. */
+typedef RTSTRCACHECHUNK *PRTSTRCACHECHUNK;
+
+
+/**
+ * Cache instance data.
+ */
+typedef struct RTSTRCACHEINT
+{
+    /** The string cache magic (RTSTRCACHE_MAGIC). */
+    uint32_t                u32Magic;
+    /** Ref counter for the cache handle. */
+    uint32_t volatile       cRefs;
+    /** The number of strings currently entered in the cache. */
+    uint32_t                cStrings;
+    /** The size of the hash table. */
+    uint32_t                cHashTab;
+    /** Pointer to the hash table. */
+    PRTSTRCACHEENTRY       *papHashTab;
+    /** Free list for allocations of size: 64+, 16, and 32. */
+    PRTSTRCACHEFREE         apFreeLists[2];
+    /** Free lists based on */
+    RTLISTANCHOR            aMergedFreeLists[RTSTRCACHE_HEAP_THRESHOLD_BIT - RTSTRCACHE_MERGED_THRESHOLD_BIT + 1];
+    /** List of allocated memory chunks. */
+    PRTSTRCACHECHUNK        pChunkList;
+    /** List of big cache entries. */
+    RTLISTANCHOR            BigEntryList;
+    /** Critical section protecting the cache structures. */
+    RTCRITSECT              CritSect;
+} RTSTRCACHEINT;
+/** Pointer to a cache instance. */
+typedef RTSTRCACHEINT *PRTSTRCACHEINT;
+
 
 
@@ -126,13 +253,45 @@
 *   Global Variables                                                           *
 *******************************************************************************/
-
+/** Init once for the default string cache. */
+static RTONCE       g_rtStrCacheOnce     = RTONCE_INITIALIZER;
+/** The default string cache. */
+static RTSTRCACHE   g_hrtStrCacheDefault = NIL_RTSTRCACHE;
+
+
+/** @callback_method_impl{FNRTONCE, Initializes g_hrtStrCacheDefault} */
+static DECLCALLBACK(int) rtStrCacheInitDefault(void *pvUser)
+{
+    NOREF(pvUser);
+    return RTStrCacheCreate(&g_hrtStrCacheDefault, "Default");
+}
 
 
 RTDECL(int) RTStrCacheCreate(PRTSTRCACHE phStrCache, const char *pszName)
 {
-    AssertCompile(sizeof(RTSTRCACHE) == sizeof(RTMEMPOOL));
-    AssertCompile(NIL_RTSTRCACHE == (RTSTRCACHE)NIL_RTMEMPOOL);
-    AssertCompile(RTSTRCACHE_DEFAULT == (RTSTRCACHE)RTMEMPOOL_DEFAULT);
-    return RTMemPoolCreate((PRTMEMPOOL)phStrCache, pszName);
+    int            rc    = VERR_NO_MEMORY;
+    PRTSTRCACHEINT pThis = (PRTSTRCACHEINT)RTMemAllocZ(sizeof(*pThis));
+    if (pThis)
+    {
+        pThis->cHashTab   = 512;
+        pThis->papHashTab = (PRTSTRCACHEENTRY*)RTMemAllocZ(sizeof(pThis->papHashTab[0]) * pThis->cHashTab);
+        if (pThis->papHashTab)
+        {
+            rc = RTCritSectInit(&pThis->CritSect);
+            if (RT_SUCCESS(rc))
+            {
+                RTListInit(&pThis->BigEntryList);
+                for (uint32_t i = 0; i < RT_ELEMENTS(pThis->aMergedFreeLists); i++)
+                    RTListInit(&pThis->aMergedFreeLists[i]);
+                pThis->cRefs    = 1;
+                pThis->u32Magic = RTSTRCACHE_MAGIC;
+
+                *phStrCache = pThis;
+                return VINF_SUCCESS;
+            }
+            RTMemFree(pThis->papHashTab);
+        }
+        RTMemFree(pThis);
+    }
+    return rc;
 }
 RT_EXPORT_SYMBOL(RTStrCacheCreate);
@@ -141,19 +300,508 @@
 RTDECL(int) RTStrCacheDestroy(RTSTRCACHE hStrCache)
 {
-    if (    hStrCache == NIL_RTSTRCACHE
-        ||  hStrCache == RTSTRCACHE_DEFAULT)
+    if (   hStrCache == NIL_RTSTRCACHE
+        || hStrCache == RTSTRCACHE_DEFAULT)
         return VINF_SUCCESS;
-    return RTMemPoolDestroy((RTMEMPOOL)hStrCache);
+
+    PRTSTRCACHEINT pThis = hStrCache;
+    RTSTRCACHE_VALID_RETURN_RC(pThis, VERR_INVALID_HANDLE);
+
+    /*
+     * Invalidate it. Enter the crit sect just to be on the safe side.
+     */
+    AssertReturn(ASMAtomicCmpXchgU32(&pThis->u32Magic, RTSTRCACHE_MAGIC_DEAD, RTSTRCACHE_MAGIC), VERR_INVALID_HANDLE);
+    RTCritSectEnter(&pThis->CritSect);
+    Assert(pThis->cRefs == 1);
+
+    PRTSTRCACHECHUNK pChunk;
+    while ((pChunk = pThis->pChunkList) != NULL)
+    {
+        pThis->pChunkList = pChunk->pNext;
+        RTMemPageFree(pChunk, pChunk->cb);
+    }
+
+    RTMemFree(pThis->papHashTab);
+    pThis->papHashTab = NULL;
+    pThis->cHashTab   = 0;
+
+    PRTSTRCACHEBIGENTRY pCur, pNext;
+    RTListForEachSafe(&pThis->BigEntryList, pCur, pNext, RTSTRCACHEBIGENTRY, ListEntry)
+    {
+        RTMemFree(pCur);
+    }
+
+    RTCritSectLeave(&pThis->CritSect);
+    RTCritSectDelete(&pThis->CritSect);
+
+    RTMemFree(pThis);
+    return VINF_SUCCESS;
 }
 RT_EXPORT_SYMBOL(RTStrCacheDestroy);
 
 
+#ifdef RT_STRICT
+# define RTSTRCACHE_CHECK(a_pThis)  do { rtStrCacheCheck(pThis); } while (0)
+/**
+ * Internal cache check.
+ */
+static void rtStrCacheCheck(PRTSTRCACHEINT pThis)
+{
+    for (uint32_t i = 0; i < RT_ELEMENTS(pThis->aMergedFreeLists); i++)
+    {
+        PRTSTRCACHEFREEMERGE pFree;
+        RTListForEach(&pThis->aMergedFreeLists[i], pFree, RTSTRCACHEFREEMERGE, ListEntry)
+        {
+            Assert(pFree->uMarker == RTSTRCACHEFREEMERGE_MAIN);
+            Assert(pFree->cbFree > 0);
+            Assert(RT_ALIGN_32(pFree->cbFree, sizeof(*pFree)) == pFree->cbFree);
+        }
+    }
+}
+#else
+# define RTSTRCACHE_CHECK(a_pThis)  do { } while (0)
+#endif
+
+
+/**
+ * Link/Relink into the free right list.
+ *
+ * @param   pThis               The string cache instance.
+ * @param   pFree               The free string entry.
+ */
+static void rtStrCacheRelinkMerged(PRTSTRCACHEINT pThis, PRTSTRCACHEFREEMERGE pFree)
+{
+    Assert(pFree->uMarker == RTSTRCACHEFREEMERGE_MAIN);
+    Assert(pFree->cbFree > 0);
+    Assert(RT_ALIGN_32(pFree->cbFree, sizeof(*pFree)) == pFree->cbFree);
+
+    if (!RTListIsEmpty(&pFree->ListEntry))
+        RTListNodeRemove(&pFree->ListEntry);
+
+    uint32_t iList = (ASMBitLastSetU32(pFree->cbFree) - 1) - RTSTRCACHE_MERGED_THRESHOLD_BIT;
+    if (iList >= RT_ELEMENTS(pThis->aMergedFreeLists))
+        iList = RT_ELEMENTS(pThis->aMergedFreeLists) - 1;
+
+    RTListPrepend(&pThis->aMergedFreeLists[iList], &pFree->ListEntry);
+}
+
+
+/**
+ * Finds the first empty hash table entry given a hash+length value.
+ *
+ * ASSUMES that the hash table isn't full.
+ *
+ * @returns Hash table index.
+ * @param   pThis               The string cache instance.
+ * @param   uHashLen            The hash + length (not RTSTRCACHEENTRY_BIG_LEN).
+ */
+static uint32_t rtStrCacheFindEmptyHashTabEntry(PRTSTRCACHEINT pThis, uint32_t uHashLen)
+{
+    uint32_t iHash = uHashLen % pThis->cHashTab;
+    for (;;)
+    {
+        PRTSTRCACHEENTRY pEntry = pThis->papHashTab[iHash];
+        if (pEntry == NULL || pEntry == PRTSTRCACHEENTRY_NIL)
+            return iHash;
+
+        /* Advance. */
+        iHash += RTSTRCACHE_COLLISION_INCR(uHashLen);
+        iHash %= pThis->cHashTab;
+    }
+}
+
+/**
+ * Grows the hash table.
+ *
+ * @returns vINF_SUCCESS or VERR_NO_MEMORY.
+ * @param   pThis               The string cache instance.
+ */
+static int rtStrCacheGrowHashTab(PRTSTRCACHEINT pThis)
+{
+    /*
+     * Allocate a new hash table two times the size of the old one.
+     */
+    uint32_t            cNew   = pThis->cHashTab * 2;
+    PRTSTRCACHEENTRY   *papNew = (PRTSTRCACHEENTRY  *)RTMemAllocZ(sizeof(papNew[0]) * cNew);
+    if (papNew == NULL)
+        return VERR_NO_MEMORY;
+
+    /*
+     * Install the new table and move the items from the old table and into the new one.
+     */
+    PRTSTRCACHEENTRY   *papOld = pThis->papHashTab;
+    uint32_t            iOld   = pThis->cHashTab;
+
+    pThis->papHashTab = papNew;
+    pThis->cHashTab   = cNew;
+
+    while (iOld-- > 0)
+    {
+        PRTSTRCACHEENTRY pEntry = papOld[iOld];
+        if (pEntry != NULL && pEntry != PRTSTRCACHEENTRY_NIL)
+        {
+            uint32_t cchString = pEntry->cchString;
+            if (cchString == RTSTRCACHEENTRY_BIG_LEN)
+                cchString = RT_FROM_MEMBER(pEntry, RTSTRCACHEBIGENTRY, Core)->cchString;
+
+            uint32_t iHash = rtStrCacheFindEmptyHashTabEntry(pThis, RT_MAKE_U32(pEntry->uHash, cchString));
+            pThis->papHashTab[iHash] = pEntry;
+        }
+    }
+
+    /*
+     * Free the old hash table.
+     */
+    RTMemFree(papOld);
+    return VINF_SUCCESS;
+}
+
+
+/**
+ * Allocate a cache entry from the heap.
+ *
+ * @returns Pointer to the cache entry on success, NULL on allocation error.
+ * @param   pThis               The string cache instance.
+ * @param   uHash               The full hash of the string.
+ * @param   pchString           The string.
+ * @param   cchString           The string length.
+ */
+static PRTSTRCACHEENTRY rtStrCacheAllocHeapEntry(PRTSTRCACHEINT pThis, uint32_t uHash,
+                                                 const char *pchString, uint32_t cchString)
+{
+    /*
+     * Allocate a heap block for storing the string. We do some size aligning
+     * here to encourage the heap to give us optimal alignment.
+     */
+    size_t              cbEntry   = RT_UOFFSETOF(RTSTRCACHEBIGENTRY, Core.szString[cchString + 1]);
+    PRTSTRCACHEBIGENTRY pBigEntry = (PRTSTRCACHEBIGENTRY)RTMemAlloc(RT_ALIGN_Z(cbEntry, 64));
+    if (!pBigEntry)
+        return NULL;
+
+    /*
+     * Initialize the block.
+     */
+    RTListAppend(&pThis->BigEntryList, &pBigEntry->ListEntry);
+    pBigEntry->cchString        = cchString;
+    pBigEntry->uHash            = uHash;
+    pBigEntry->Core.cRefs       = 1;
+    pBigEntry->Core.uHash       = (uint16_t)uHash;
+    pBigEntry->Core.cchString   = RTSTRCACHEENTRY_BIG_LEN;
+    memcpy(pBigEntry->Core.szString, pchString, cchString);
+    pBigEntry->Core.szString[cchString] = '\0';
+
+    return &pBigEntry->Core;
+}
+
+
+/**
+ * Allocate a cache entry from the merged free lists.
+ *
+ * @returns Pointer to the cache entry on success, NULL on allocation error.
+ * @param   pThis               The string cache instance.
+ * @param   uHash               The full hash of the string.
+ * @param   pchString           The string.
+ * @param   cchString           The string length.
+ * @param   cbEntry             The required entry size.
+ */
+static PRTSTRCACHEENTRY rtStrCacheAllocMergedEntry(PRTSTRCACHEINT pThis, uint32_t uHash,
+                                                   const char *pchString, uint32_t cchString, uint32_t cbEntry)
+{
+    cbEntry = RT_ALIGN_32(cbEntry, sizeof(RTSTRCACHEFREEMERGE));
+    Assert(cbEntry > cchString);
+
+    /*
+     * Search the list heads first.
+     */
+    PRTSTRCACHEFREEMERGE pFree = NULL;
+
+    uint32_t iList = ASMBitLastSetU32(cbEntry) - 1;
+    if (!RT_IS_POWER_OF_TWO(cbEntry))
+        iList++;
+    iList -= RTSTRCACHE_MERGED_THRESHOLD_BIT;
+
+    while (iList < RT_ELEMENTS(pThis->aMergedFreeLists))
+    {
+        pFree = RTListGetFirst(&pThis->aMergedFreeLists[iList], RTSTRCACHEFREEMERGE, ListEntry);
+        if (pFree)
+        {
+            /*
+             * Found something. Should we we split it?  We split from the end
+             * to avoid having to update all the sub entries.
+             */
+            Assert(pFree->uMarker == RTSTRCACHEFREEMERGE_MAIN);
+            Assert(pFree->cbFree >= cbEntry);
+            Assert(RT_ALIGN_32(pFree->cbFree, sizeof(*pFree)) == pFree->cbFree);
+
+            if (pFree->cbFree == cbEntry)
+                RTListNodeRemove(&pFree->ListEntry);
+            else
+            {
+                uint32_t             cRemainder = (pFree->cbFree - cbEntry) / sizeof(*pFree);
+                PRTSTRCACHEFREEMERGE pRemainder = pFree;
+                pFree += cRemainder;
+
+                Assert((pRemainder->cbFree - cbEntry) == cRemainder * sizeof(*pFree));
+                pRemainder->cbFree = cRemainder * sizeof(*pFree);
+
+                rtStrCacheRelinkMerged(pThis, pRemainder);
+            }
+            break;
+        }
+        iList++;
+    }
+    if (!pFree)
+    {
+        /*
+         * Allocate a new block. (We could search the list below in some
+         * cases, but it's too much effort to write and execute).
+         */
+        size_t const     cbChunk = RTSTRCACHE_HEAP_THRESHOLD * 16;   AssertReturn(cbChunk > cbEntry * 2, NULL);
+        PRTSTRCACHECHUNK pChunk  = (PRTSTRCACHECHUNK)RTMemPageAlloc(cbChunk);
+        if (!pChunk)
+            return NULL;
+        pChunk->cb    = cbChunk;
+        pChunk->pNext = pThis->pChunkList;
+        pThis->pChunkList = pChunk;
+        AssertCompile(sizeof(*pChunk) <= sizeof(*pFree));
+
+        /*
+         * Get one node for the allocation at hand.
+         */
+        pFree = (PRTSTRCACHEFREEMERGE)((uintptr_t)pChunk + sizeof(*pFree));
+
+        /*
+         * Create a free block out of the remainder (always a reminder).
+         */
+        PRTSTRCACHEFREEMERGE pNewFree = (PRTSTRCACHEFREEMERGE)((uintptr_t)pFree + cbEntry);
+        pNewFree->uMarker = RTSTRCACHEFREEMERGE_MAIN;
+        pNewFree->cbFree  = cbChunk - sizeof(*pNewFree) - cbEntry; Assert(pNewFree->cbFree < cbChunk && pNewFree->cbFree > 0);
+        pNewFree->pMain   = NULL;
+        RTListInit(&pNewFree->ListEntry);
+
+        uint32_t iInternalBlock = pNewFree->cbFree / sizeof(*pNewFree);
+        while (iInternalBlock-- > 1)
+        {
+            pNewFree[iInternalBlock].uMarker = RTSTRCACHEFREEMERGE_PART;
+            pNewFree[iInternalBlock].cbFree  = 0;
+            pNewFree[iInternalBlock].pMain   = pNewFree;
+        }
+
+        rtStrCacheRelinkMerged(pThis, pNewFree);
+    }
+
+    /*
+     * Initialize the entry.  We zero all bytes we don't use so they cannot
+     * accidentally be mistaken for a free entry.
+     */
+    ASMCompilerBarrier();
+    PRTSTRCACHEENTRY pEntry = (PRTSTRCACHEENTRY)pFree;
+    pEntry->cRefs       = 1;
+    pEntry->uHash       = (uint16_t)uHash;
+    pEntry->cchString   = (uint16_t)cchString;
+    memcpy(pEntry->szString, pchString, cchString);
+    RT_BZERO(&pEntry->szString[cchString], cbEntry - RT_UOFFSETOF(RTSTRCACHEENTRY, szString) - cchString);
+
+    RTSTRCACHE_CHECK(pThis);
+
+    return pEntry;
+}
+
+
+/**
+ * Allocate a cache entry from a fixed size free list.
+ *
+ * @returns Pointer to the cache entry on success, NULL on allocation error.
+ * @param   pThis               The string cache instance.
+ * @param   uHash               The full hash of the string.
+ * @param   pchString           The string.
+ * @param   cchString           The string length.
+ * @param   iFreeList           Which free list.
+ */
+static PRTSTRCACHEENTRY rtStrCacheAllocFixedEntry(PRTSTRCACHEINT pThis, uint32_t uHash,
+                                                  const char *pchString, uint32_t cchString, uint32_t iFreeList)
+{
+    /*
+     * Get an entry from the free list. If empty, allocate another chunk of
+     * memory and split it up into free entries of the desired size.
+     */
+    PRTSTRCACHEFREE pFree = pThis->apFreeLists[iFreeList];
+    if (!pFree)
+    {
+        PRTSTRCACHECHUNK pChunk = (PRTSTRCACHECHUNK)RTMemPageAlloc(PAGE_SIZE);
+        if (!pChunk)
+            return NULL;
+        pChunk->cb = PAGE_SIZE;
+        pChunk->pNext = pThis->pChunkList;
+        pThis->pChunkList = pChunk;
+
+        PRTSTRCACHEFREE pPrev   = NULL;
+        size_t const    cbEntry = 1 << (iFreeList + 4);
+        uint32_t        cLeft   = PAGE_SIZE / cbEntry - 1;
+        pFree = (PRTSTRCACHEFREE)((uintptr_t)pChunk + cbEntry);
+
+        Assert(sizeof(*pChunk) <= cbEntry);
+        Assert(sizeof(*pFree)  <= cbEntry);
+        Assert(cbEntry < PAGE_SIZE / 16);
+
+        while (cLeft-- > 0)
+        {
+            pFree->uZero  = 0;
+            pFree->cbFree = cbEntry;
+            pFree->pNext  = pPrev;
+            pPrev = pFree;
+            pFree = (PRTSTRCACHEFREE)((uintptr_t)pFree + cbEntry);
+        }
+
+        Assert(pPrev);
+        pThis->apFreeLists[iFreeList] = pFree = pPrev;
+    }
+
+    /*
+     * Unlink it.
+     */
+    pThis->apFreeLists[iFreeList] = pFree->pNext;
+    ASMCompilerBarrier();
+
+    /*
+     * Initialize the entry.
+     */
+    PRTSTRCACHEENTRY pEntry = (PRTSTRCACHEENTRY)pFree;
+    pEntry->cRefs     = 1;
+    pEntry->uHash     = (uint16_t)uHash;
+    pEntry->cchString = (uint16_t)cchString;
+    memcpy(pEntry->szString, pchString, cchString);
+    pEntry->szString[cchString] = '\0';
+
+    return pEntry;
+}
+
+
+/**
+ * Looks up a string in the hash table.
+ *
+ * @returns Pointer to the string cache entry, NULL + piFreeHashTabEntry if not
+ *          found.
+ * @param   pThis               The string cache instance.
+ * @param   uHashLen            The hash + length (not RTSTRCACHEENTRY_BIG_LEN).
+ * @param   cchString           The real length.
+ * @param   pchString           The string.
+ * @param   piFreeHashTabEntry  Where to store the index insertion index if NULL
+ *                              is returned (same as what
+ *                              rtStrCacheFindEmptyHashTabEntry would return).
+ */
+static PRTSTRCACHEENTRY rtStrCacheLookUp(PRTSTRCACHEINT pThis, uint32_t uHashLen, uint32_t cchString, const char *pchString,
+                                         uint32_t *piFreeHashTabEntry)
+{
+    *piFreeHashTabEntry = UINT32_MAX;
+
+    uint16_t cchStringFirst = RT_UOFFSETOF(RTSTRCACHEENTRY, szString[cchString + 1]) < RTSTRCACHE_HEAP_THRESHOLD
+                            ? (uint16_t)cchString : RTSTRCACHEENTRY_BIG_LEN;
+    uint32_t iHash          = uHashLen % pThis->cHashTab;
+    for (;;)
+    {
+        PRTSTRCACHEENTRY pEntry = pThis->papHashTab[iHash];
+
+        /* Give up if NULL, but record the index for insertion. */
+        if (pEntry == NULL)
+        {
+            if (*piFreeHashTabEntry == UINT32_MAX)
+                *piFreeHashTabEntry = iHash;
+            return NULL;
+        }
+
+        if (pEntry != PRTSTRCACHEENTRY_NIL)
+        {
+            /* Compare. */
+            if (   pEntry->uHash     == (uint16_t)uHashLen
+                && pEntry->cchString == cchStringFirst
+                && !memcmp(pEntry->szString, pchString, cchString)
+                && pEntry->szString[cchString] == '\0')
+                return pEntry;
+        }
+        /* Record the first NIL index for insertion in case we don't get a hit. */
+        else if (*piFreeHashTabEntry == UINT32_MAX)
+            *piFreeHashTabEntry = iHash;
+
+        /* Advance. */
+        iHash += RTSTRCACHE_COLLISION_INCR(uHashLen);
+        iHash %= pThis->cHashTab;
+    }
+}
+
+
 RTDECL(const char *) RTStrCacheEnterN(RTSTRCACHE hStrCache, const char *pchString, size_t cchString)
 {
-    AssertPtr(pchString);
+    PRTSTRCACHEINT pThis = hStrCache;
+    RTSTRCACHE_VALID_RETURN_RC(pThis, NULL);
+
+
+    /*
+     * Calculate the hash and figure the exact string length, then look for an existing entry.
+     */
+    uint32_t const uHash    = sdbmN(pchString, cchString, &cchString);
+    uint32_t const uHashLen = RT_MAKE_U32(uHash, cchString);
     AssertReturn(cchString < _1G, NULL);
-    Assert(!RTStrEnd(pchString, cchString));
-
-    return (const char *)RTMemPoolDupEx((RTMEMPOOL)hStrCache, pchString, cchString, 1);
+
+
+    RTCritSectEnter(&pThis->CritSect);
+    RTSTRCACHE_CHECK(pThis);
+
+    uint32_t iFreeHashTabEntry;
+    PRTSTRCACHEENTRY pEntry = rtStrCacheLookUp(pThis, uHashLen, cchString, pchString, &iFreeHashTabEntry);
+    if (pEntry)
+    {
+        uint32_t cRefs = ASMAtomicIncU32(&pEntry->cRefs);
+        Assert(cRefs < UINT32_MAX / 2);
+    }
+    else
+    {
+        /*
+         * Allocate a new entry.
+         */
+        uint32_t cbEntry = cchString + 1U + RT_UOFFSETOF(RTSTRCACHEENTRY, szString);
+        if (cbEntry >= RTSTRCACHE_MERGED_THRESHOLD_BIT)
+        {
+            if (cbEntry < RTSTRCACHE_HEAP_THRESHOLD * 2)
+                pEntry = rtStrCacheAllocMergedEntry(pThis, uHash, pchString, cchString, cbEntry);
+            else
+                pEntry = rtStrCacheAllocHeapEntry(pThis, uHash, pchString, cchString);
+        }
+        else
+            pEntry = rtStrCacheAllocFixedEntry(pThis, uHash, pchString, cchString, cbEntry > 16);
+        if (!pEntry)
+        {
+            RTSTRCACHE_CHECK(pThis);
+            RTCritSectLeave(&pThis->CritSect);
+            return NULL;
+        }
+
+        /*
+         * Insert it into the hash table.
+         */
+        if (pThis->cHashTab - pThis->cStrings < pThis->cHashTab / 2)
+        {
+            int rc = rtStrCacheGrowHashTab(pThis);
+            if (RT_SUCCESS(rc))
+                iFreeHashTabEntry = rtStrCacheFindEmptyHashTabEntry(pThis, uHashLen);
+            else if (pThis->cHashTab - pThis->cStrings <= pThis->cHashTab / 8) /* 12.5% full => error */
+            {
+                pThis->papHashTab[iFreeHashTabEntry] = pEntry;
+                pThis->cStrings++;
+                RTStrCacheRelease(hStrCache, pEntry->szString);
+
+                RTSTRCACHE_CHECK(pThis);
+                RTCritSectLeave(&pThis->CritSect);
+                return NULL;
+            }
+        }
+
+        pThis->papHashTab[iFreeHashTabEntry] = pEntry;
+        pThis->cStrings++;
+        Assert(pThis->cStrings < pThis->cHashTab && pThis->cStrings > 0);
+    }
+
+    RTSTRCACHE_CHECK(pThis);
+    RTCritSectLeave(&pThis->CritSect);
+    return pEntry->szString;
 }
 RT_EXPORT_SYMBOL(RTStrCacheEnterN);
@@ -167,14 +815,40 @@
 
 
+static const char *rtStrCacheEnterLowerWorker(PRTSTRCACHEINT pThis, const char *pchString, size_t cchString)
+{
+    /*
+     * Try use a dynamic heap buffer first.
+     */
+    if (cchString < 512)
+    {
+        char *pszStackBuf = (char *)alloca(cchString + 1);
+        if (pszStackBuf)
+        {
+            memcpy(pszStackBuf, pchString, cchString);
+            pszStackBuf[cchString] = '\0';
+            RTStrToLower(pszStackBuf);
+            return RTStrCacheEnterN(pThis, pszStackBuf, cchString);
+        }
+    }
+
+    /*
+     * Fall back on heap.
+     */
+    char *pszHeapBuf = (char *)RTMemTmpAlloc(cchString + 1);
+    if (!pszHeapBuf)
+        return NULL;
+    memcpy(pszHeapBuf, pchString, cchString);
+    pszHeapBuf[cchString] = '\0';
+    RTStrToLower(pszHeapBuf);
+    const char *pszRet = RTStrCacheEnterN(pThis, pszHeapBuf, cchString);
+    RTMemTmpFree(pszHeapBuf);
+    return pszRet;
+}
+
 RTDECL(const char *) RTStrCacheEnterLowerN(RTSTRCACHE hStrCache, const char *pchString, size_t cchString)
 {
-    AssertPtr(pchString);
-    AssertReturn(cchString < _1G, NULL);
-    Assert(!RTStrEnd(pchString, cchString));
-
-    char *pszRet = (char *)RTMemPoolDupEx((RTMEMPOOL)hStrCache, pchString, cchString, 1);
-    if (pszRet)
-        RTStrToLower(pszRet);
-    return pszRet;
+    PRTSTRCACHEINT pThis = hStrCache;
+    RTSTRCACHE_VALID_RETURN_RC(pThis, NULL);
+    return rtStrCacheEnterLowerWorker(pThis, pchString, RTStrNLen(pchString, cchString));
 }
 RT_EXPORT_SYMBOL(RTStrCacheEnterLowerN);
@@ -183,5 +857,7 @@
 RTDECL(const char *) RTStrCacheEnterLower(RTSTRCACHE hStrCache, const char *psz)
 {
-    return RTStrCacheEnterLowerN(hStrCache, psz, strlen(psz));
+    PRTSTRCACHEINT pThis = hStrCache;
+    RTSTRCACHE_VALID_RETURN_RC(pThis, NULL);
+    return rtStrCacheEnterLowerWorker(pThis, psz, strlen(psz));
 }
 RT_EXPORT_SYMBOL(RTStrCacheEnterLower);
@@ -191,8 +867,166 @@
 {
     AssertPtr(psz);
-    return RTMemPoolRetain((void *)psz);
+
+    PRTSTRCACHEENTRY pStr = RT_FROM_MEMBER(psz, RTSTRCACHEENTRY, szString);
+    Assert(!((uintptr_t)pStr & 15) || pStr->cchString == RTSTRCACHEENTRY_BIG_LEN);
+
+    uint32_t cRefs = ASMAtomicIncU32(&pStr->cRefs);
+    Assert(cRefs > 1);
+    Assert(cRefs < UINT32_MAX / 2);
+
+    return cRefs;
 }
 RT_EXPORT_SYMBOL(RTStrCacheRetain);
 
+
+static uint32_t rtStrCacheFreeEntry(PRTSTRCACHEINT pThis, PRTSTRCACHEENTRY pStr)
+{
+    RTCritSectEnter(&pThis->CritSect);
+    RTSTRCACHE_CHECK(pThis);
+
+    /* Remove it from the hash table. */
+    uint32_t uHashLen = RT_MAKE_U32(pStr->uHash,
+                                    pStr->cchString == RTSTRCACHEENTRY_BIG_LEN
+                                    ? RT_FROM_MEMBER(pStr, RTSTRCACHEBIGENTRY, Core)->cchString
+                                    : pStr->cchString);
+    uint32_t iHash    = uHashLen % pThis->cHashTab;
+    if (pThis->papHashTab[iHash] == pStr)
+        pThis->papHashTab[iHash] = PRTSTRCACHEENTRY_NIL;
+    else
+    {
+        do
+        {
+            AssertBreak(pThis->papHashTab[iHash] != NULL);
+            iHash += RTSTRCACHE_COLLISION_INCR(uHashLen);
+            iHash %= pThis->cHashTab;
+        } while (pThis->papHashTab[iHash] != pStr);
+        if (RT_LIKELY(pThis->papHashTab[iHash] == pStr))
+            pThis->papHashTab[iHash] = PRTSTRCACHEENTRY_NIL;
+        else
+        {
+            AssertFailed();
+            iHash = pThis->cHashTab;
+            while (iHash-- > 0)
+                if (pThis->papHashTab[iHash] == pStr)
+                    break;
+            AssertMsgFailed(("iHash=%u cHashTab=%u\n", iHash, pThis->cHashTab));
+        }
+    }
+
+    pThis->cStrings--;
+    Assert(pThis->cStrings < pThis->cHashTab);
+
+    /* Free it. */
+    if (pStr->cchString != RTSTRCACHEENTRY_BIG_LEN)
+    {
+        uint32_t const cbMin = pStr->cchString + 1U + RT_UOFFSETOF(RTSTRCACHEENTRY, szString);
+        if (cbMin <= 32)
+        {
+            /*
+             * No merging, just add it to the list.
+             */
+            uint32_t const iFreeList = cbMin > 16;
+            ASMCompilerBarrier();
+            PRTSTRCACHEFREE pFreeStr = (PRTSTRCACHEFREE)pStr;
+            pFreeStr->cbFree   = cbMin;
+            pFreeStr->uZero    = 0;
+            pFreeStr->pNext    = pThis->apFreeLists[iFreeList];
+            pThis->apFreeLists[iFreeList] = pFreeStr;
+        }
+        else
+        {
+            /*
+             * Complicated mode, we merge with adjecent nodes.
+             */
+            ASMCompilerBarrier();
+            PRTSTRCACHEFREEMERGE pFreeStr = (PRTSTRCACHEFREEMERGE)pStr;
+            pFreeStr->cbFree   = RT_ALIGN_32(cbMin, sizeof(*pFreeStr));
+            pFreeStr->uMarker  = RTSTRCACHEFREEMERGE_MAIN;
+            pFreeStr->pMain    = NULL;
+            RTListInit(&pFreeStr->ListEntry);
+
+            /*
+             * Merge with previous?
+             * (Reading one block back is safe because there is always the
+             * RTSTRCACHECHUNK structure at the head of each memory chunk.)
+             */
+            uint32_t             cInternalBlocks = pFreeStr->cbFree / sizeof(*pFreeStr);
+            PRTSTRCACHEFREEMERGE pMain = pFreeStr - 1;
+            if (   pMain->uMarker == RTSTRCACHEFREEMERGE_MAIN
+                || pMain->uMarker == RTSTRCACHEFREEMERGE_PART)
+            {
+                while (pMain->uMarker != RTSTRCACHEFREEMERGE_MAIN)
+                    pMain--;
+                pMain->cbFree += pFreeStr->cbFree;
+            }
+            else
+            {
+                pMain = pFreeStr;
+                pFreeStr++;
+                cInternalBlocks--;
+            }
+
+            /*
+             * Mark internal blocks in the string we're freeing.
+             */
+            while (cInternalBlocks-- > 0)
+            {
+                pFreeStr->uMarker = RTSTRCACHEFREEMERGE_PART;
+                pFreeStr->cbFree  = 0;
+                pFreeStr->pMain   = pMain;
+                RTListInit(&pFreeStr->ListEntry);
+                pFreeStr++;
+            }
+
+            /*
+             * Merge with next? Limitation: We won't try cross page boundraries.
+             * (pFreeStr points to the next first free enter after the string now.)
+             */
+            if (   PAGE_ADDRESS(pFreeStr) == PAGE_ADDRESS(&pFreeStr[-1])
+                && pFreeStr->uMarker == RTSTRCACHEFREEMERGE_MAIN)
+            {
+                pMain->cbFree    += pFreeStr->cbFree;
+                cInternalBlocks   = pFreeStr->cbFree / sizeof(*pFreeStr);
+                Assert(cInternalBlocks > 0);
+
+                /* Update the main block we merge with. */
+                pFreeStr->cbFree  = 0;
+                pFreeStr->uMarker = RTSTRCACHEFREEMERGE_PART;
+                RTListNodeRemove(&pFreeStr->ListEntry);
+                RTListInit(&pFreeStr->ListEntry);
+
+                /* Change the internal blocks we merged in. */
+                cInternalBlocks--;
+                while (cInternalBlocks-- > 0)
+                {
+                    pFreeStr++;
+                    pFreeStr->pMain = pMain;
+                    Assert(pFreeStr->uMarker == RTSTRCACHEFREEMERGE_PART);
+                    Assert(!pFreeStr->cbFree);
+                }
+            }
+
+            /*
+             * Add/relink into the appropriate free list.
+             */
+            rtStrCacheRelinkMerged(pThis, pMain);
+        }
+        RTSTRCACHE_CHECK(pThis);
+        RTCritSectLeave(&pThis->CritSect);
+    }
+    else
+    {
+        /* Big string. */
+        PRTSTRCACHEBIGENTRY pBigStr = RT_FROM_MEMBER(pStr, RTSTRCACHEBIGENTRY, Core);
+        RTListNodeRemove(&pBigStr->ListEntry);
+
+        RTSTRCACHE_CHECK(pThis);
+        RTCritSectLeave(&pThis->CritSect);
+
+        RTMemFree(pBigStr);
+    }
+
+    return 0;
+}
 
 RTDECL(uint32_t) RTStrCacheRelease(RTSTRCACHE hStrCache, const char *psz)
@@ -200,5 +1034,21 @@
     if (!psz)
         return 0;
-    return RTMemPoolRelease((RTMEMPOOL)hStrCache, (void *)psz);
+
+    PRTSTRCACHEINT pThis = hStrCache;
+    RTSTRCACHE_VALID_RETURN_RC(pThis, UINT32_MAX);
+
+    AssertPtr(psz);
+    PRTSTRCACHEENTRY pStr = RT_FROM_MEMBER(psz, RTSTRCACHEENTRY, szString);
+    Assert(!((uintptr_t)pStr & 15) || pStr->cchString == RTSTRCACHEENTRY_BIG_LEN);
+
+    /*
+     * Drop a reference and maybe free the entry.
+     */
+    uint32_t cRefs = ASMAtomicDecU32(&pStr->cRefs);
+    Assert(cRefs < UINT32_MAX / 2);
+    if (!cRefs)
+        return rtStrCacheFreeEntry(pThis, pStr);
+
+    return cRefs;
 }
 RT_EXPORT_SYMBOL(RTStrCacheRelease);
@@ -209,5 +1059,14 @@
     if (!psz)
         return 0;
-    return strlen(psz);
+
+    AssertPtr(psz);
+    PRTSTRCACHEENTRY pStr = RT_FROM_MEMBER(psz, RTSTRCACHEENTRY, szString);
+    if (pStr->cchString == RTSTRCACHEENTRY_BIG_LEN)
+    {
+        PRTSTRCACHEBIGENTRY pBigStr = RT_FROM_MEMBER(psz, RTSTRCACHEBIGENTRY, Core.szString);
+        return pBigStr->cchString;
+    }
+    Assert(!((uintptr_t)pStr & 15));
+    return pStr->cchString;
 }
 RT_EXPORT_SYMBOL(RTStrCacheLength);
