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

   1 /* Alloc.c -- Memory allocation functions
   2 2024-02-18 : Igor Pavlov : Public domain */
   3
   4 #include "Precomp.h"
   5
   6 #ifdef _WIN32
   7 #include "7zWindows.h"
   8 #endif
   9 #include <stdlib.h>
  10
  11 #include "Alloc.h"
  12
  13 #if defined(Z7_LARGE_PAGES) && defined(_WIN32) && \
  14     (!defined(Z7_WIN32_WINNT_MIN) || Z7_WIN32_WINNT_MIN < 0x0502)  // < Win2003 (xp-64)
  15   #define Z7_USE_DYN_GetLargePageMinimum
  16 #endif
  17
  18 // for debug:
  19 #if 0
  20 #if defined(__CHERI__) && defined(__SIZEOF_POINTER__) && (__SIZEOF_POINTER__ == 16)
  21 // #pragma message("=== Z7_ALLOC_NO_OFFSET_ALLOCATOR === ")
  22 #define Z7_ALLOC_NO_OFFSET_ALLOCATOR
  23 #endif
  24 #endif
  25
  26 // #define SZ_ALLOC_DEBUG
  27 /* #define SZ_ALLOC_DEBUG */
  28
  29 /* use SZ_ALLOC_DEBUG to debug alloc/free operations */
  30 #ifdef SZ_ALLOC_DEBUG
  31
  32 #include <string.h>
  33 #include <stdio.h>
  34 static int g_allocCount = 0;
  35 #ifdef _WIN32
  36 static int g_allocCountMid = 0;
  37 static int g_allocCountBig = 0;
  38 #endif
  39
  40
  41 #define CONVERT_INT_TO_STR(charType, tempSize) \
  42   char temp[tempSize]; unsigned i = 0; \
  43   while (val >= 10) { temp[i++] = (char)('0' + (unsigned)(val % 10)); val /= 10; } \
  44   *s++ = (charType)('0' + (unsigned)val); \
  45   while (i != 0) { i--; *s++ = temp[i]; } \
  46   *s = 0;
  47
  48 static void ConvertUInt64ToString(UInt64 val, char *s)
  49 {
  50   CONVERT_INT_TO_STR(char, 24)
  51 }
  52
  53 #define GET_HEX_CHAR(t) ((char)(((t < 10) ? ('0' + t) : ('A' + (t - 10)))))
  54
  55 static void ConvertUInt64ToHex(UInt64 val, char *s)
  56 {
  57   UInt64 v = val;
  58   unsigned i;
  59   for (i = 1;; i++)
  60   {
  61     v >>= 4;
  62     if (v == 0)
  63       break;
  64   }
  65   s[i] = 0;
  66   do
  67   {
  68     unsigned t = (unsigned)(val & 0xF);
  69     val >>= 4;
  70     s[--i] = GET_HEX_CHAR(t);
  71   }
  72   while (i);
  73 }
  74
  75 #define DEBUG_OUT_STREAM stderr
  76
  77 static void Print(const char *s)
  78 {
  79   fputs(s, DEBUG_OUT_STREAM);
  80 }
  81
  82 static void PrintAligned(const char *s, size_t align)
  83 {
  84   size_t len = strlen(s);
  85   for(;;)
  86   {
  87     fputc(' ', DEBUG_OUT_STREAM);
  88     if (len >= align)
  89       break;
  90     ++len;
  91   }
  92   Print(s);
  93 }
  94
  95 static void PrintLn(void)
  96 {
  97   Print("\n");
  98 }
  99
 100 static void PrintHex(UInt64 v, size_t align)
 101 {
 102   char s[32];
 103   ConvertUInt64ToHex(v, s);
 104   PrintAligned(s, align);
 105 }
 106
 107 static void PrintDec(int v, size_t align)
 108 {
 109   char s[32];
 110   ConvertUInt64ToString((unsigned)v, s);
 111   PrintAligned(s, align);
 112 }
 113
 114 static void PrintAddr(void *p)
 115 {
 116   PrintHex((UInt64)(size_t)(ptrdiff_t)p, 12);
 117 }
 118
 119
 120 #define PRINT_REALLOC(name, cnt, size, ptr) { \
 121     Print(name " "); \
 122     if (!ptr) PrintDec(cnt++, 10); \
 123     PrintHex(size, 10); \
 124     PrintAddr(ptr); \
 125     PrintLn(); }
 126
 127 #define PRINT_ALLOC(name, cnt, size, ptr) { \
 128     Print(name " "); \
 129     PrintDec(cnt++, 10); \
 130     PrintHex(size, 10); \
 131     PrintAddr(ptr); \
 132     PrintLn(); }
 133
 134 #define PRINT_FREE(name, cnt, ptr) if (ptr) { \
 135     Print(name " "); \
 136     PrintDec(--cnt, 10); \
 137     PrintAddr(ptr); \
 138     PrintLn(); }
 139
 140 #else
 141
 142 #ifdef _WIN32
 143 #define PRINT_ALLOC(name, cnt, size, ptr)
 144 #endif
 145 #define PRINT_FREE(name, cnt, ptr)
 146 #define Print(s)
 147 #define PrintLn()
 148 #ifndef Z7_ALLOC_NO_OFFSET_ALLOCATOR
 149 #define PrintHex(v, align)
 150 #endif
 151 #define PrintAddr(p)
 152
 153 #endif
 154
 155
 156 /*
 157 by specification:
 158   malloc(non_NULL, 0)   : returns NULL or a unique pointer value that can later be successfully passed to free()
 159   realloc(NULL, size)   : the call is equivalent to malloc(size)
 160   realloc(non_NULL, 0)  : the call is equivalent to free(ptr)
 161
 162 in main compilers:
 163   malloc(0)             : returns non_NULL
 164   realloc(NULL,     0)  : returns non_NULL
 165   realloc(non_NULL, 0)  : returns NULL
 166 */
 167
 168
 169 void *MyAlloc(size_t size)
 170 {
 171   if (size == 0)
 172     return NULL;
 173   // PRINT_ALLOC("Alloc    ", g_allocCount, size, NULL)
 174   #ifdef SZ_ALLOC_DEBUG
 175   {
 176     void *p = malloc(size);
 177     if (p)
 178     {
 179       PRINT_ALLOC("Alloc    ", g_allocCount, size, p)
 180     }
 181     return p;
 182   }
 183   #else
 184   return malloc(size);
 185   #endif
 186 }
 187
 188 void MyFree(void *address)
 189 {
 190   PRINT_FREE("Free    ", g_allocCount, address)
 191
 192   free(address);
 193 }
 194
 195 void *MyRealloc(void *address, size_t size)
 196 {
 197   if (size == 0)
 198   {
 199     MyFree(address);
 200     return NULL;
 201   }
 202   // PRINT_REALLOC("Realloc  ", g_allocCount, size, address)
 203   #ifdef SZ_ALLOC_DEBUG
 204   {
 205     void *p = realloc(address, size);
 206     if (p)
 207     {
 208       PRINT_REALLOC("Realloc    ", g_allocCount, size, address)
 209     }
 210     return p;
 211   }
 212   #else
 213   return realloc(address, size);
 214   #endif
 215 }
 216
 217
 218 #ifdef _WIN32
 219
 220 void *MidAlloc(size_t size)
 221 {
 222   if (size == 0)
 223     return NULL;
 224   #ifdef SZ_ALLOC_DEBUG
 225   {
 226     void *p = VirtualAlloc(NULL, size, MEM_COMMIT, PAGE_READWRITE);
 227     if (p)
 228     {
 229       PRINT_ALLOC("Alloc-Mid", g_allocCountMid, size, p)
 230     }
 231     return p;
 232   }
 233   #else
 234   return VirtualAlloc(NULL, size, MEM_COMMIT, PAGE_READWRITE);
 235   #endif
 236 }
 237
 238 void MidFree(void *address)
 239 {
 240   PRINT_FREE("Free-Mid", g_allocCountMid, address)
 241
 242   if (!address)
 243     return;
 244   VirtualFree(address, 0, MEM_RELEASE);
 245 }
 246
 247 #ifdef Z7_LARGE_PAGES
 248
 249 #ifdef MEM_LARGE_PAGES
 250   #define MY_MEM_LARGE_PAGES  MEM_LARGE_PAGES
 251 #else
 252   #define MY_MEM_LARGE_PAGES  0x20000000
 253 #endif
 254
 255 extern
 256 SIZE_T g_LargePageSize;
 257 SIZE_T g_LargePageSize = 0;
 258 typedef SIZE_T (WINAPI *Func_GetLargePageMinimum)(VOID);
 259
 260 void SetLargePageSize(void)
 261 {
 262   SIZE_T size;
 263 #ifdef Z7_USE_DYN_GetLargePageMinimum
 264 Z7_DIAGNOSTIC_IGNORE_CAST_FUNCTION
 265
 266   const
 267    Func_GetLargePageMinimum fn =
 268   (Func_GetLargePageMinimum) Z7_CAST_FUNC_C GetProcAddress(GetModuleHandle(TEXT("kernel32.dll")),
 269        "GetLargePageMinimum");
 270   if (!fn)
 271     return;
 272   size = fn();
 273 #else
 274   size = GetLargePageMinimum();
 275 #endif
 276   if (size == 0 || (size & (size - 1)) != 0)
 277     return;
 278   g_LargePageSize = size;
 279 }
 280
 281 #endif // Z7_LARGE_PAGES
 282
 283 void *BigAlloc(size_t size)
 284 {
 285   if (size == 0)
 286     return NULL;
 287
 288   PRINT_ALLOC("Alloc-Big", g_allocCountBig, size, NULL)
 289
 290   #ifdef Z7_LARGE_PAGES
 291   {
 292     SIZE_T ps = g_LargePageSize;
 293     if (ps != 0 && ps <= (1 << 30) && size > (ps / 2))
 294     {
 295       size_t size2;
 296       ps--;
 297       size2 = (size + ps) & ~ps;
 298       if (size2 >= size)
 299       {
 300         void *p = VirtualAlloc(NULL, size2, MEM_COMMIT | MY_MEM_LARGE_PAGES, PAGE_READWRITE);
 301         if (p)
 302         {
 303           PRINT_ALLOC("Alloc-BM ", g_allocCountMid, size2, p)
 304           return p;
 305         }
 306       }
 307     }
 308   }
 309   #endif
 310
 311   return MidAlloc(size);
 312 }
 313
 314 void BigFree(void *address)
 315 {
 316   PRINT_FREE("Free-Big", g_allocCountBig, address)
 317   MidFree(address);
 318 }
 319
 320 #endif // _WIN32
 321
 322
 323 static void *SzAlloc(ISzAllocPtr p, size_t size) { UNUSED_VAR(p)  return MyAlloc(size); }
 324 static void SzFree(ISzAllocPtr p, void *address) { UNUSED_VAR(p)  MyFree(address); }
 325 const ISzAlloc g_Alloc = { SzAlloc, SzFree };
 326
 327 #ifdef _WIN32
 328 static void *SzMidAlloc(ISzAllocPtr p, size_t size) { UNUSED_VAR(p)  return MidAlloc(size); }
 329 static void SzMidFree(ISzAllocPtr p, void *address) { UNUSED_VAR(p)  MidFree(address); }
 330 static void *SzBigAlloc(ISzAllocPtr p, size_t size) { UNUSED_VAR(p)  return BigAlloc(size); }
 331 static void SzBigFree(ISzAllocPtr p, void *address) { UNUSED_VAR(p)  BigFree(address); }
 332 const ISzAlloc g_MidAlloc = { SzMidAlloc, SzMidFree };
 333 const ISzAlloc g_BigAlloc = { SzBigAlloc, SzBigFree };
 334 #endif
 335
 336 #ifndef Z7_ALLOC_NO_OFFSET_ALLOCATOR
 337
 338 #define ADJUST_ALLOC_SIZE 0
 339 /*
 340 #define ADJUST_ALLOC_SIZE (sizeof(void *) - 1)
 341 */
 342 /*
 343   Use (ADJUST_ALLOC_SIZE = (sizeof(void *) - 1)), if
 344      MyAlloc() can return address that is NOT multiple of sizeof(void *).
 345 */
 346
 347 /*
 348   uintptr_t : <stdint.h> C99 (optional)
 349             : unsupported in VS6
 350 */
 351 typedef
 352   #ifdef _WIN32
 353     UINT_PTR
 354   #elif 1
 355     uintptr_t
 356   #else
 357     ptrdiff_t
 358   #endif
 359     MY_uintptr_t;
 360
 361 #if 0 \
 362     || (defined(__CHERI__) \
 363     || defined(__SIZEOF_POINTER__) && (__SIZEOF_POINTER__ > 8))
 364 // for 128-bit pointers (cheri):
 365 #define MY_ALIGN_PTR_DOWN(p, align)  \
 366     ((void *)((char *)(p) - ((size_t)(MY_uintptr_t)(p) & ((align) - 1))))
 367 #else
 368 #define MY_ALIGN_PTR_DOWN(p, align) \
 369     ((void *)((((MY_uintptr_t)(p)) & ~((MY_uintptr_t)(align) - 1))))
 370 #endif
 371
 372 #endif
 373
 374 #if !defined(_WIN32) \
 375     && (defined(Z7_ALLOC_NO_OFFSET_ALLOCATOR) \
 376         || defined(_POSIX_C_SOURCE) && (_POSIX_C_SOURCE >= 200112L))
 377   #define USE_posix_memalign
 378 #endif
 379
 380 #ifndef USE_posix_memalign
 381 #define MY_ALIGN_PTR_UP_PLUS(p, align) MY_ALIGN_PTR_DOWN(((char *)(p) + (align) + ADJUST_ALLOC_SIZE), align)
 382 #endif
 383
 384 /*
 385   This posix_memalign() is for test purposes only.
 386   We also need special Free() function instead of free(),
 387   if this posix_memalign() is used.
 388 */
 389
 390 /*
 391 static int posix_memalign(void **ptr, size_t align, size_t size)
 392 {
 393   size_t newSize = size + align;
 394   void *p;
 395   void *pAligned;
 396   *ptr = NULL;
 397   if (newSize < size)
 398     return 12; // ENOMEM
 399   p = MyAlloc(newSize);
 400   if (!p)
 401     return 12; // ENOMEM
 402   pAligned = MY_ALIGN_PTR_UP_PLUS(p, align);
 403   ((void **)pAligned)[-1] = p;
 404   *ptr = pAligned;
 405   return 0;
 406 }
 407 */
 408
 409 /*
 410   ALLOC_ALIGN_SIZE >= sizeof(void *)
 411   ALLOC_ALIGN_SIZE >= cache_line_size
 412 */
 413
 414 #define ALLOC_ALIGN_SIZE ((size_t)1 << 7)
 415
 416 void *z7_AlignedAlloc(size_t size)
 417 {
 418 #ifndef USE_posix_memalign
 419
 420   void *p;
 421   void *pAligned;
 422   size_t newSize;
 423
 424   /* also we can allocate additional dummy ALLOC_ALIGN_SIZE bytes after aligned
 425      block to prevent cache line sharing with another allocated blocks */
 426
 427   newSize = size + ALLOC_ALIGN_SIZE * 1 + ADJUST_ALLOC_SIZE;
 428   if (newSize < size)
 429     return NULL;
 430
 431   p = MyAlloc(newSize);
 432
 433   if (!p)
 434     return NULL;
 435   pAligned = MY_ALIGN_PTR_UP_PLUS(p, ALLOC_ALIGN_SIZE);
 436
 437   Print(" size="); PrintHex(size, 8);
 438   Print(" a_size="); PrintHex(newSize, 8);
 439   Print(" ptr="); PrintAddr(p);
 440   Print(" a_ptr="); PrintAddr(pAligned);
 441   PrintLn();
 442
 443   ((void **)pAligned)[-1] = p;
 444
 445   return pAligned;
 446
 447 #else
 448
 449   void *p;
 450   if (posix_memalign(&p, ALLOC_ALIGN_SIZE, size))
 451     return NULL;
 452
 453   Print(" posix_memalign="); PrintAddr(p);
 454   PrintLn();
 455
 456   return p;
 457
 458 #endif
 459 }
 460
 461
 462 void z7_AlignedFree(void *address)
 463 {
 464 #ifndef USE_posix_memalign
 465   if (address)
 466     MyFree(((void **)address)[-1]);
 467 #else
 468   free(address);
 469 #endif
 470 }
 471
 472
 473 static void *SzAlignedAlloc(ISzAllocPtr pp, size_t size)
 474 {
 475   UNUSED_VAR(pp)
 476   return z7_AlignedAlloc(size);
 477 }
 478
 479
 480 static void SzAlignedFree(ISzAllocPtr pp, void *address)
 481 {
 482   UNUSED_VAR(pp)
 483 #ifndef USE_posix_memalign
 484   if (address)
 485     MyFree(((void **)address)[-1]);
 486 #else
 487   free(address);
 488 #endif
 489 }
 490
 491
 492 const ISzAlloc g_AlignedAlloc = { SzAlignedAlloc, SzAlignedFree };
 493
 494
 495
 496 /* we align ptr to support cases where CAlignOffsetAlloc::offset is not multiply of sizeof(void *) */
 497 #ifndef Z7_ALLOC_NO_OFFSET_ALLOCATOR
 498 #if 1
 499   #define MY_ALIGN_PTR_DOWN_1(p)  MY_ALIGN_PTR_DOWN(p, sizeof(void *))
 500   #define REAL_BLOCK_PTR_VAR(p)  ((void **)MY_ALIGN_PTR_DOWN_1(p))[-1]
 501 #else
 502   // we can use this simplified code,
 503   // if (CAlignOffsetAlloc::offset == (k * sizeof(void *))
 504   #define REAL_BLOCK_PTR_VAR(p)  (((void **)(p))[-1])
 505 #endif
 506 #endif
 507
 508
 509 #if 0
 510 #ifndef Z7_ALLOC_NO_OFFSET_ALLOCATOR
 511 #include <stdio.h>
 512 static void PrintPtr(const char *s, const void *p)
 513 {
 514   const Byte *p2 = (const Byte *)&p;
 515   unsigned i;
 516   printf("%s %p ", s, p);
 517   for (i = sizeof(p); i != 0;)
 518   {
 519     i--;
 520     printf("%02x", p2[i]);
 521   }
 522   printf("\n");
 523 }
 524 #endif
 525 #endif
 526
 527
 528 static void *AlignOffsetAlloc_Alloc(ISzAllocPtr pp, size_t size)
 529 {
 530 #if defined(Z7_ALLOC_NO_OFFSET_ALLOCATOR)
 531   UNUSED_VAR(pp)
 532   return z7_AlignedAlloc(size);
 533 #else
 534   const CAlignOffsetAlloc *p = Z7_CONTAINER_FROM_VTBL_CONST(pp, CAlignOffsetAlloc, vt);
 535   void *adr;
 536   void *pAligned;
 537   size_t newSize;
 538   size_t extra;
 539   size_t alignSize = (size_t)1 << p->numAlignBits;
 540
 541   if (alignSize < sizeof(void *))
 542     alignSize = sizeof(void *);
 543
 544   if (p->offset >= alignSize)
 545     return NULL;
 546
 547   /* also we can allocate additional dummy ALLOC_ALIGN_SIZE bytes after aligned
 548      block to prevent cache line sharing with another allocated blocks */
 549   extra = p->offset & (sizeof(void *) - 1);
 550   newSize = size + alignSize + extra + ADJUST_ALLOC_SIZE;
 551   if (newSize < size)
 552     return NULL;
 553
 554   adr = ISzAlloc_Alloc(p->baseAlloc, newSize);
 555
 556   if (!adr)
 557     return NULL;
 558
 559   pAligned = (char *)MY_ALIGN_PTR_DOWN((char *)adr +
 560       alignSize - p->offset + extra + ADJUST_ALLOC_SIZE, alignSize) + p->offset;
 561
 562 #if 0
 563   printf("\nalignSize = %6x, offset=%6x, size=%8x \n", (unsigned)alignSize, (unsigned)p->offset, (unsigned)size);
 564   PrintPtr("base", adr);
 565   PrintPtr("alig", pAligned);
 566 #endif
 567
 568   PrintLn();
 569   Print("- Aligned: ");
 570   Print(" size="); PrintHex(size, 8);
 571   Print(" a_size="); PrintHex(newSize, 8);
 572   Print(" ptr="); PrintAddr(adr);
 573   Print(" a_ptr="); PrintAddr(pAligned);
 574   PrintLn();
 575
 576   REAL_BLOCK_PTR_VAR(pAligned) = adr;
 577
 578   return pAligned;
 579 #endif
 580 }
 581
 582
 583 static void AlignOffsetAlloc_Free(ISzAllocPtr pp, void *address)
 584 {
 585 #if defined(Z7_ALLOC_NO_OFFSET_ALLOCATOR)
 586   UNUSED_VAR(pp)
 587   z7_AlignedFree(address);
 588 #else
 589   if (address)
 590   {
 591     const CAlignOffsetAlloc *p = Z7_CONTAINER_FROM_VTBL_CONST(pp, CAlignOffsetAlloc, vt);
 592     PrintLn();
 593     Print("- Aligned Free: ");
 594     PrintLn();
 595     ISzAlloc_Free(p->baseAlloc, REAL_BLOCK_PTR_VAR(address));
 596   }
 597 #endif
 598 }
 599
 600
 601 void AlignOffsetAlloc_CreateVTable(CAlignOffsetAlloc *p)
 602 {
 603   p->vt.Alloc = AlignOffsetAlloc_Alloc;
 604   p->vt.Free = AlignOffsetAlloc_Free;
 605 }