BaseTools/Source/C/LzmaCompress/Sdk/C/Alloc.c

   1 /* Alloc.c -- Memory allocation functions
   2 2018-04-27 : Igor Pavlov : Public domain */
   3
   4 #include "Precomp.h"
   5
   6 #include <stdio.h>
   7
   8 #ifdef _WIN32
   9 #include <windows.h>
  10 #endif
  11 #include <stdlib.h>
  12
  13 #include "Alloc.h"
  14
  15 /* #define _SZ_ALLOC_DEBUG */
  16
  17 /* use _SZ_ALLOC_DEBUG to debug alloc/free operations */
  18 #ifdef _SZ_ALLOC_DEBUG
  19
  20 #include <stdio.h>
  21 int g_allocCount = 0;
  22 int g_allocCountMid = 0;
  23 int g_allocCountBig = 0;
  24
  25
  26 #define CONVERT_INT_TO_STR(charType, tempSize) \
  27   unsigned char temp[tempSize]; unsigned i = 0; \
  28   while (val >= 10) { temp[i++] = (unsigned char)('0' + (unsigned)(val % 10)); val /= 10; } \
  29   *s++ = (charType)('0' + (unsigned)val); \
  30   while (i != 0) { i--; *s++ = temp[i]; } \
  31   *s = 0;
  32
  33 static void ConvertUInt64ToString(UInt64 val, char *s)
  34 {
  35   CONVERT_INT_TO_STR(char, 24);
  36 }
  37
  38 #define GET_HEX_CHAR(t) ((char)(((t < 10) ? ('0' + t) : ('A' + (t - 10)))))
  39
  40 static void ConvertUInt64ToHex(UInt64 val, char *s)
  41 {
  42   UInt64 v = val;
  43   unsigned i;
  44   for (i = 1;; i++)
  45   {
  46     v >>= 4;
  47     if (v == 0)
  48       break;
  49   }
  50   s[i] = 0;
  51   do
  52   {
  53     unsigned t = (unsigned)(val & 0xF);
  54     val >>= 4;
  55     s[--i] = GET_HEX_CHAR(t);
  56   }
  57   while (i);
  58 }
  59
  60 #define DEBUG_OUT_STREAM stderr
  61
  62 static void Print(const char *s)
  63 {
  64   fputs(s, DEBUG_OUT_STREAM);
  65 }
  66
  67 static void PrintAligned(const char *s, size_t align)
  68 {
  69   size_t len = strlen(s);
  70   for(;;)
  71   {
  72     fputc(' ', DEBUG_OUT_STREAM);
  73     if (len >= align)
  74       break;
  75     ++len;
  76   }
  77   Print(s);
  78 }
  79
  80 static void PrintLn()
  81 {
  82   Print("\n");
  83 }
  84
  85 static void PrintHex(UInt64 v, size_t align)
  86 {
  87   char s[32];
  88   ConvertUInt64ToHex(v, s);
  89   PrintAligned(s, align);
  90 }
  91
  92 static void PrintDec(UInt64 v, size_t align)
  93 {
  94   char s[32];
  95   ConvertUInt64ToString(v, s);
  96   PrintAligned(s, align);
  97 }
  98
  99 static void PrintAddr(void *p)
 100 {
 101   PrintHex((UInt64)(size_t)(ptrdiff_t)p, 12);
 102 }
 103
 104
 105 #define PRINT_ALLOC(name, cnt, size, ptr) \
 106     Print(name " "); \
 107     PrintDec(cnt++, 10); \
 108     PrintHex(size, 10); \
 109     PrintAddr(ptr); \
 110     PrintLn();
 111
 112 #define PRINT_FREE(name, cnt, ptr) if (ptr) { \
 113     Print(name " "); \
 114     PrintDec(--cnt, 10); \
 115     PrintAddr(ptr); \
 116     PrintLn(); }
 117
 118 #else
 119
 120 #define PRINT_ALLOC(name, cnt, size, ptr)
 121 #define PRINT_FREE(name, cnt, ptr)
 122 #define Print(s)
 123 #define PrintLn()
 124 #define PrintHex(v, align)
 125 #define PrintDec(v, align)
 126 #define PrintAddr(p)
 127
 128 #endif
 129
 130
 131
 132 void *MyAlloc(size_t size)
 133 {
 134   if (size == 0)
 135     return NULL;
 136   #ifdef _SZ_ALLOC_DEBUG
 137   {
 138     void *p = malloc(size);
 139     PRINT_ALLOC("Alloc    ", g_allocCount, size, p);
 140     return p;
 141   }
 142   #else
 143   return malloc(size);
 144   #endif
 145 }
 146
 147 void MyFree(void *address)
 148 {
 149   PRINT_FREE("Free    ", g_allocCount, address);
 150
 151   free(address);
 152 }
 153
 154 #ifdef _WIN32
 155
 156 void *MidAlloc(size_t size)
 157 {
 158   if (size == 0)
 159     return NULL;
 160
 161   PRINT_ALLOC("Alloc-Mid", g_allocCountMid, size, NULL);
 162
 163   return VirtualAlloc(NULL, size, MEM_COMMIT, PAGE_READWRITE);
 164 }
 165
 166 void MidFree(void *address)
 167 {
 168   PRINT_FREE("Free-Mid", g_allocCountMid, address);
 169
 170   if (!address)
 171     return;
 172   VirtualFree(address, 0, MEM_RELEASE);
 173 }
 174
 175 #ifndef MEM_LARGE_PAGES
 176 #undef _7ZIP_LARGE_PAGES
 177 #endif
 178
 179 #ifdef _7ZIP_LARGE_PAGES
 180 SIZE_T g_LargePageSize = 0;
 181 typedef SIZE_T (WINAPI *GetLargePageMinimumP)();
 182 #endif
 183
 184 void SetLargePageSize()
 185 {
 186   #ifdef _7ZIP_LARGE_PAGES
 187   SIZE_T size;
 188   GetLargePageMinimumP largePageMinimum = (GetLargePageMinimumP)
 189         GetProcAddress(GetModuleHandle(TEXT("kernel32.dll")), "GetLargePageMinimum");
 190   if (!largePageMinimum)
 191     return;
 192   size = largePageMinimum();
 193   if (size == 0 || (size & (size - 1)) != 0)
 194     return;
 195   g_LargePageSize = size;
 196   #endif
 197 }
 198
 199
 200 void *BigAlloc(size_t size)
 201 {
 202   if (size == 0)
 203     return NULL;
 204
 205   PRINT_ALLOC("Alloc-Big", g_allocCountBig, size, NULL);
 206
 207   #ifdef _7ZIP_LARGE_PAGES
 208   {
 209     SIZE_T ps = g_LargePageSize;
 210     if (ps != 0 && ps <= (1 << 30) && size > (ps / 2))
 211     {
 212       size_t size2;
 213       ps--;
 214       size2 = (size + ps) & ~ps;
 215       if (size2 >= size)
 216       {
 217         void *res = VirtualAlloc(NULL, size2, MEM_COMMIT | MEM_LARGE_PAGES, PAGE_READWRITE);
 218         if (res)
 219           return res;
 220       }
 221     }
 222   }
 223   #endif
 224
 225   return VirtualAlloc(NULL, size, MEM_COMMIT, PAGE_READWRITE);
 226 }
 227
 228 void BigFree(void *address)
 229 {
 230   PRINT_FREE("Free-Big", g_allocCountBig, address);
 231
 232   if (!address)
 233     return;
 234   VirtualFree(address, 0, MEM_RELEASE);
 235 }
 236
 237 #endif
 238
 239
 240 static void *SzAlloc(ISzAllocPtr p, size_t size) { UNUSED_VAR(p); return MyAlloc(size); }
 241 static void SzFree(ISzAllocPtr p, void *address) { UNUSED_VAR(p); MyFree(address); }
 242 const ISzAlloc g_Alloc = { SzAlloc, SzFree };
 243
 244 static void *SzMidAlloc(ISzAllocPtr p, size_t size) { UNUSED_VAR(p); return MidAlloc(size); }
 245 static void SzMidFree(ISzAllocPtr p, void *address) { UNUSED_VAR(p); MidFree(address); }
 246 const ISzAlloc g_MidAlloc = { SzMidAlloc, SzMidFree };
 247
 248 static void *SzBigAlloc(ISzAllocPtr p, size_t size) { UNUSED_VAR(p); return BigAlloc(size); }
 249 static void SzBigFree(ISzAllocPtr p, void *address) { UNUSED_VAR(p); BigFree(address); }
 250 const ISzAlloc g_BigAlloc = { SzBigAlloc, SzBigFree };
 251
 252
 253 /*
 254   uintptr_t : <stdint.h> C99 (optional)
 255             : unsupported in VS6
 256 */
 257
 258 #ifdef _WIN32
 259   typedef UINT_PTR UIntPtr;
 260 #else
 261   /*
 262   typedef uintptr_t UIntPtr;
 263   */
 264   typedef ptrdiff_t UIntPtr;
 265 #endif
 266
 267
 268 #define ADJUST_ALLOC_SIZE 0
 269 /*
 270 #define ADJUST_ALLOC_SIZE (sizeof(void *) - 1)
 271 */
 272 /*
 273   Use (ADJUST_ALLOC_SIZE = (sizeof(void *) - 1)), if
 274      MyAlloc() can return address that is NOT multiple of sizeof(void *).
 275 */
 276
 277
 278 /*
 279 #define MY_ALIGN_PTR_DOWN(p, align) ((void *)((char *)(p) - ((size_t)(UIntPtr)(p) & ((align) - 1))))
 280 */
 281 #define MY_ALIGN_PTR_DOWN(p, align) ((void *)((((UIntPtr)(p)) & ~((UIntPtr)(align) - 1))))
 282
 283 #define MY_ALIGN_PTR_UP_PLUS(p, align) MY_ALIGN_PTR_DOWN(((char *)(p) + (align) + ADJUST_ALLOC_SIZE), align)
 284
 285
 286 #if (_POSIX_C_SOURCE >= 200112L) && !defined(_WIN32)
 287   #define USE_posix_memalign
 288 #endif
 289
 290 /*
 291   This posix_memalign() is for test purposes only.
 292   We also need special Free() function instead of free(),
 293   if this posix_memalign() is used.
 294 */
 295
 296 /*
 297 static int posix_memalign(void **ptr, size_t align, size_t size)
 298 {
 299   size_t newSize = size + align;
 300   void *p;
 301   void *pAligned;
 302   *ptr = NULL;
 303   if (newSize < size)
 304     return 12; // ENOMEM
 305   p = MyAlloc(newSize);
 306   if (!p)
 307     return 12; // ENOMEM
 308   pAligned = MY_ALIGN_PTR_UP_PLUS(p, align);
 309   ((void **)pAligned)[-1] = p;
 310   *ptr = pAligned;
 311   return 0;
 312 }
 313 */
 314
 315 /*
 316   ALLOC_ALIGN_SIZE >= sizeof(void *)
 317   ALLOC_ALIGN_SIZE >= cache_line_size
 318 */
 319
 320 #define ALLOC_ALIGN_SIZE ((size_t)1 << 7)
 321
 322 static void *SzAlignedAlloc(ISzAllocPtr pp, size_t size)
 323 {
 324   #ifndef USE_posix_memalign
 325
 326   void *p;
 327   void *pAligned;
 328   size_t newSize;
 329   UNUSED_VAR(pp);
 330
 331   /* also we can allocate additional dummy ALLOC_ALIGN_SIZE bytes after aligned
 332      block to prevent cache line sharing with another allocated blocks */
 333
 334   newSize = size + ALLOC_ALIGN_SIZE * 1 + ADJUST_ALLOC_SIZE;
 335   if (newSize < size)
 336     return NULL;
 337
 338   p = MyAlloc(newSize);
 339
 340   if (!p)
 341     return NULL;
 342   pAligned = MY_ALIGN_PTR_UP_PLUS(p, ALLOC_ALIGN_SIZE);
 343
 344   Print(" size="); PrintHex(size, 8);
 345   Print(" a_size="); PrintHex(newSize, 8);
 346   Print(" ptr="); PrintAddr(p);
 347   Print(" a_ptr="); PrintAddr(pAligned);
 348   PrintLn();
 349
 350   ((void **)pAligned)[-1] = p;
 351
 352   return pAligned;
 353
 354   #else
 355
 356   void *p;
 357   UNUSED_VAR(pp);
 358   if (posix_memalign(&p, ALLOC_ALIGN_SIZE, size))
 359     return NULL;
 360
 361   Print(" posix_memalign="); PrintAddr(p);
 362   PrintLn();
 363
 364   return p;
 365
 366   #endif
 367 }
 368
 369
 370 static void SzAlignedFree(ISzAllocPtr pp, void *address)
 371 {
 372   UNUSED_VAR(pp);
 373   #ifndef USE_posix_memalign
 374   if (address)
 375     MyFree(((void **)address)[-1]);
 376   #else
 377   free(address);
 378   #endif
 379 }
 380
 381
 382 const ISzAlloc g_AlignedAlloc = { SzAlignedAlloc, SzAlignedFree };
 383
 384
 385
 386 #define MY_ALIGN_PTR_DOWN_1(p) MY_ALIGN_PTR_DOWN(p, sizeof(void *))
 387
 388 /* we align ptr to support cases where CAlignOffsetAlloc::offset is not multiply of sizeof(void *) */
 389 #define REAL_BLOCK_PTR_VAR(p) ((void **)MY_ALIGN_PTR_DOWN_1(p))[-1]
 390 /*
 391 #define REAL_BLOCK_PTR_VAR(p) ((void **)(p))[-1]
 392 */
 393
 394 static void *AlignOffsetAlloc_Alloc(ISzAllocPtr pp, size_t size)
 395 {
 396   CAlignOffsetAlloc *p = CONTAINER_FROM_VTBL(pp, CAlignOffsetAlloc, vt);
 397   void *adr;
 398   void *pAligned;
 399   size_t newSize;
 400   size_t extra;
 401   size_t alignSize = (size_t)1 << p->numAlignBits;
 402
 403   if (alignSize < sizeof(void *))
 404     alignSize = sizeof(void *);
 405
 406   if (p->offset >= alignSize)
 407     return NULL;
 408
 409   /* also we can allocate additional dummy ALLOC_ALIGN_SIZE bytes after aligned
 410      block to prevent cache line sharing with another allocated blocks */
 411   extra = p->offset & (sizeof(void *) - 1);
 412   newSize = size + alignSize + extra + ADJUST_ALLOC_SIZE;
 413   if (newSize < size)
 414     return NULL;
 415
 416   adr = ISzAlloc_Alloc(p->baseAlloc, newSize);
 417
 418   if (!adr)
 419     return NULL;
 420
 421   pAligned = (char *)MY_ALIGN_PTR_DOWN((char *)adr +
 422       alignSize - p->offset + extra + ADJUST_ALLOC_SIZE, alignSize) + p->offset;
 423
 424   PrintLn();
 425   Print("- Aligned: ");
 426   Print(" size="); PrintHex(size, 8);
 427   Print(" a_size="); PrintHex(newSize, 8);
 428   Print(" ptr="); PrintAddr(adr);
 429   Print(" a_ptr="); PrintAddr(pAligned);
 430   PrintLn();
 431
 432   REAL_BLOCK_PTR_VAR(pAligned) = adr;
 433
 434   return pAligned;
 435 }
 436
 437
 438 static void AlignOffsetAlloc_Free(ISzAllocPtr pp, void *address)
 439 {
 440   if (address)
 441   {
 442     CAlignOffsetAlloc *p = CONTAINER_FROM_VTBL(pp, CAlignOffsetAlloc, vt);
 443     PrintLn();
 444     Print("- Aligned Free: ");
 445     PrintLn();
 446     ISzAlloc_Free(p->baseAlloc, REAL_BLOCK_PTR_VAR(address));
 447   }
 448 }
 449
 450
 451 void AlignOffsetAlloc_CreateVTable(CAlignOffsetAlloc *p)
 452 {
 453   p->vt.Alloc = AlignOffsetAlloc_Alloc;
 454   p->vt.Free = AlignOffsetAlloc_Free;
 455 }