deps/libchdr/deps/lzma-22.01/src/Alloc.c

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