Alloc.c (9550B)
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 }