src/utilcode/memorypool.cpp

   1 // Licensed to the .NET Foundation under one or more agreements.
   2 // The .NET Foundation licenses this file to you under the MIT license.
   3 // See the LICENSE file in the project root for more information.
   4
   5 #include "stdafx.h"
   6
   7 #include "memorypool.h"
   8 #include "ex.h"
   9
  10 size_t MemoryPool::GetSize()
  11 {
  12     LIMITED_METHOD_CONTRACT;
  13     size_t retval=0;
  14
  15     Block *block = m_blocks;
  16     while (block != NULL)
  17     {
  18         retval+=(BYTE*)block->elementsEnd-(BYTE*)block->elements;
  19         block = block->next;
  20     }
  21     return retval;
  22 }
  23
  24 #ifndef DACCESS_COMPILE
  25
  26 BOOL MemoryPool::AddBlock(SIZE_T elementCount)
  27 {
  28     CONTRACTL {
  29         NOTHROW;
  30         GC_NOTRIGGER;
  31         INJECT_FAULT(return FALSE;);
  32     } CONTRACTL_END;
  33
  34     //
  35     // Check for arithmetic overflow
  36     //
  37     S_SIZE_T cbBlockSize = S_SIZE_T(elementCount) * S_SIZE_T(m_elementSize);
  38     S_SIZE_T cbAllocSize = S_SIZE_T(sizeof(Block)) + cbBlockSize;
  39     if (cbBlockSize.IsOverflow() || cbAllocSize.IsOverflow())
  40         return FALSE;
  41
  42     //
  43     // Allocate the new block.
  44     //
  45
  46     Block *block = (Block *) new (nothrow) BYTE [cbAllocSize.Value()];
  47
  48     if (block == NULL)
  49         return FALSE;
  50
  51     //
  52     // Chain all elements together for the free list
  53     //
  54
  55     _ASSERTE(m_freeList == NULL);
  56     Element **prev = &m_freeList;
  57
  58     Element *e = block->elements;
  59     Element *eEnd = (Element *) ((BYTE*) block->elements + elementCount*m_elementSize);
  60     while (e < eEnd)
  61     {
  62         *prev = e;
  63         prev = &e->next;
  64 #if _DEBUG
  65         DeadBeef(e);
  66 #endif
  67         e = (Element*) ((BYTE*)e + m_elementSize);
  68     }
  69
  70     *prev = NULL;
  71
  72     //
  73     // Initialize the other block fields & link the block into the block list
  74     //
  75
  76     block->elementsEnd = e;
  77     block->next = m_blocks;
  78     m_blocks = block;
  79
  80     return TRUE;
  81 }
  82
  83 void MemoryPool::DeadBeef(Element *element)
  84 {
  85 #if _DEBUG
  86     CONTRACTL {
  87         NOTHROW;
  88         GC_NOTRIGGER;
  89         CANNOT_TAKE_LOCK;
  90     } CONTRACTL_END;
  91
  92     int *i = &element->deadBeef;
  93     int *iEnd = (int*) ((BYTE*)element + m_elementSize);
  94     while (i < iEnd)
  95         *i++ = (int) 0xdeadbeef;
  96 #else
  97     LIMITED_METHOD_CONTRACT;
  98 #endif
  99 }
 100
 101 MemoryPool::MemoryPool(SIZE_T elementSize, SIZE_T initGrowth, SIZE_T initCount)
 102     : m_elementSize(elementSize),
 103       m_growCount(initGrowth),
 104       m_blocks(NULL),
 105       m_freeList(NULL)
 106 {
 107     CONTRACTL {
 108         if (initCount) THROWS; else NOTHROW;
 109         GC_NOTRIGGER;
 110     } CONTRACTL_END;
 111
 112     _ASSERTE(elementSize >= sizeof(Element));
 113     _ASSERTE((elementSize & ((sizeof(PVOID)-1))) == 0);
 114
 115     if (initCount > 0)
 116         AddBlock(initCount);
 117 }
 118
 119 MemoryPool::~MemoryPool()
 120 {
 121     LIMITED_METHOD_CONTRACT;
 122     Block *block = m_blocks;
 123     while (block != NULL)
 124     {
 125         Block *next = block->next;
 126         delete [] (BYTE*) block;
 127         block = next;
 128     }
 129 }
 130
 131 BOOL MemoryPool::IsElement(void *element)
 132 {
 133     LIMITED_METHOD_CONTRACT;
 134
 135     Block *block = m_blocks;
 136     while (block != NULL)
 137     {
 138         if (element >= block->elements    &&
 139             element <  block->elementsEnd  )
 140         {
 141             return ((BYTE *)element - (BYTE*)block->elements) % m_elementSize == 0;
 142         }
 143         block = block->next;
 144     }
 145
 146     return FALSE;
 147 }
 148
 149 BOOL MemoryPool::IsAllocatedElement(void *element)
 150 {
 151     CONTRACTL {
 152         NOTHROW;
 153         GC_NOTRIGGER;
 154         CANNOT_TAKE_LOCK;
 155     } CONTRACTL_END;
 156
 157     if (!IsElement(element))
 158         return FALSE;
 159
 160     //
 161     // Now, make sure the element isn't
 162     // in the free list.
 163     //
 164
 165 #if _DEBUG
 166     //
 167     // In a debug build, all objects on the free list
 168     // will be marked with deadbeef.  This means that
 169     // if the object is not deadbeef, it's not on the
 170     // free list.
 171     //
 172     // This check will give us decent performance in
 173     // a debug build for FreeElement, since we
 174     // always expect to return TRUE in that case.
 175     //
 176
 177     if (((Element*)element)->deadBeef != (int) 0xdeadBeef)
 178         return TRUE;
 179 #endif
 180
 181     Element *f = m_freeList;
 182     while (f != NULL)
 183     {
 184         if (f == element)
 185             return FALSE;
 186         f = f->next;
 187     }
 188
 189 #if _DEBUG
 190     //
 191     // We should never get here in a debug build, because
 192     // all free elements should be deadbeefed.
 193     //
 194     _ASSERTE(!"Unreachable");
 195 #endif
 196
 197     return TRUE;
 198 }
 199
 200 void *MemoryPool::AllocateElement()
 201 {
 202     CONTRACTL {
 203         THROWS;
 204         GC_NOTRIGGER;
 205     } CONTRACTL_END;
 206
 207     void *element = AllocateElementNoThrow();
 208     if (element == NULL)
 209         ThrowOutOfMemory();
 210
 211     return element;
 212 }
 213
 214 void *MemoryPool::AllocateElementNoThrow()
 215 {
 216     CONTRACTL {
 217         NOTHROW;
 218         GC_NOTRIGGER;
 219         INJECT_FAULT( return FALSE; );
 220     } CONTRACTL_END;
 221
 222     void *element = m_freeList;
 223
 224     if (element == NULL)
 225     {
 226         if (!AddBlock(m_growCount))
 227             return NULL;
 228
 229         m_growCount *= 2;
 230         element = m_freeList;
 231     }
 232
 233     // if we come there means that addblock succeeded and m_freelist isn't null anymore
 234     PREFIX_ASSUME(m_freeList!= NULL);
 235     m_freeList = m_freeList->next;
 236
 237     return element;
 238 }
 239
 240 void MemoryPool::FreeElement(void *element)
 241 {
 242     CONTRACTL {
 243         NOTHROW;
 244         GC_NOTRIGGER;
 245         CANNOT_TAKE_LOCK;
 246     } CONTRACTL_END;
 247
 248 #if _DEBUG // don't want to do this assert in a non-debug build; it is expensive
 249     _ASSERTE(IsAllocatedElement(element));
 250 #endif
 251
 252     Element *e = (Element *) element;
 253
 254 #if _DEBUG
 255     DeadBeef(e);
 256 #endif
 257
 258     e->next = m_freeList;
 259     m_freeList = e;
 260 }
 261
 262 void MemoryPool::FreeAllElements()
 263 {
 264     LIMITED_METHOD_CONTRACT;
 265
 266     Block *block = m_blocks;
 267     while (block != NULL)
 268     {
 269         Block *next = block->next;
 270         delete [] block;
 271         block = next;
 272     }
 273
 274     m_freeList = NULL;
 275     m_blocks = NULL;
 276 }
 277
 278
 279
 280 MemoryPool::Iterator::Iterator(MemoryPool *pool)
 281 {
 282     LIMITED_METHOD_CONTRACT;
 283
 284     //
 285     // Warning!  This only works if you haven't freed
 286     // any elements.
 287     //
 288
 289     m_next = pool->m_blocks;
 290     m_e = NULL;
 291     m_eEnd = NULL;
 292     m_end = (BYTE*) pool->m_freeList;
 293     m_size = pool->m_elementSize;
 294 }
 295
 296 BOOL MemoryPool::Iterator::Next()
 297 {
 298     LIMITED_METHOD_CONTRACT;
 299
 300     if (m_e == m_eEnd
 301         || (m_e == m_end && m_end != NULL))
 302     {
 303         if (m_next == NULL)
 304             return FALSE;
 305         m_e = (BYTE*) m_next->elements;
 306         m_eEnd = (BYTE*) m_next->elementsEnd;
 307         m_next = m_next->next;
 308         if (m_e == m_end)
 309             return FALSE;
 310     }
 311
 312     m_e += m_size;
 313
 314     return TRUE;
 315 }
 316
 317 #endif