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
ConvertUInt64ToString(UInt64 val,char * s)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
ConvertUInt64ToHex(UInt64 val,char * s)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
Print(const char * s)77 static void Print(const char *s)
78 {
79 fputs(s, DEBUG_OUT_STREAM);
80 }
81
PrintAligned(const char * s,size_t align)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
PrintLn(void)95 static void PrintLn(void)
96 {
97 Print("\n");
98 }
99
PrintHex(UInt64 v,size_t align)100 static void PrintHex(UInt64 v, size_t align)
101 {
102 char s[32];
103 ConvertUInt64ToHex(v, s);
104 PrintAligned(s, align);
105 }
106
PrintDec(int v,size_t align)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
PrintAddr(void * p)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
MyAlloc(size_t size)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
MyFree(void * address)188 void MyFree(void *address)
189 {
190 PRINT_FREE("Free ", g_allocCount, address)
191
192 free(address);
193 }
194
MyRealloc(void * address,size_t size)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
MidAlloc(size_t size)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
MidFree(void * address)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
SetLargePageSize(void)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
BigAlloc(size_t size)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
BigFree(void * address)314 void BigFree(void *address)
315 {
316 PRINT_FREE("Free-Big", g_allocCountBig, address)
317 MidFree(address);
318 }
319
320 #endif // _WIN32
321
322
SzAlloc(ISzAllocPtr p,size_t size)323 static void *SzAlloc(ISzAllocPtr p, size_t size) { UNUSED_VAR(p) return MyAlloc(size); }
SzFree(ISzAllocPtr p,void * address)324 static void SzFree(ISzAllocPtr p, void *address) { UNUSED_VAR(p) MyFree(address); }
325 const ISzAlloc g_Alloc = { SzAlloc, SzFree };
326
327 #ifdef _WIN32
SzMidAlloc(ISzAllocPtr p,size_t size)328 static void *SzMidAlloc(ISzAllocPtr p, size_t size) { UNUSED_VAR(p) return MidAlloc(size); }
SzMidFree(ISzAllocPtr p,void * address)329 static void SzMidFree(ISzAllocPtr p, void *address) { UNUSED_VAR(p) MidFree(address); }
SzBigAlloc(ISzAllocPtr p,size_t size)330 static void *SzBigAlloc(ISzAllocPtr p, size_t size) { UNUSED_VAR(p) return BigAlloc(size); }
SzBigFree(ISzAllocPtr p,void * address)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
z7_AlignedAlloc(size_t size)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
z7_AlignedFree(void * address)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
SzAlignedAlloc(ISzAllocPtr pp,size_t size)473 static void *SzAlignedAlloc(ISzAllocPtr pp, size_t size)
474 {
475 UNUSED_VAR(pp)
476 return z7_AlignedAlloc(size);
477 }
478
479
SzAlignedFree(ISzAllocPtr pp,void * address)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
AlignOffsetAlloc_Alloc(ISzAllocPtr pp,size_t size)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
AlignOffsetAlloc_Free(ISzAllocPtr pp,void * address)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
AlignOffsetAlloc_CreateVTable(CAlignOffsetAlloc * p)601 void AlignOffsetAlloc_CreateVTable(CAlignOffsetAlloc *p)
602 {
603 p->vt.Alloc = AlignOffsetAlloc_Alloc;
604 p->vt.Free = AlignOffsetAlloc_Free;
605 }
606