• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
ConvertUInt64ToString(UInt64 val,char * s)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 
ConvertUInt64ToHex(UInt64 val,char * s)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 
Print(const char * s)62 static void Print(const char *s)
63 {
64   fputs(s, DEBUG_OUT_STREAM);
65 }
66 
PrintAligned(const char * s,size_t align)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 
PrintLn()80 static void PrintLn()
81 {
82   Print("\n");
83 }
84 
PrintHex(UInt64 v,size_t align)85 static void PrintHex(UInt64 v, size_t align)
86 {
87   char s[32];
88   ConvertUInt64ToHex(v, s);
89   PrintAligned(s, align);
90 }
91 
PrintDec(UInt64 v,size_t align)92 static void PrintDec(UInt64 v, size_t align)
93 {
94   char s[32];
95   ConvertUInt64ToString(v, s);
96   PrintAligned(s, align);
97 }
98 
PrintAddr(void * p)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 
MyAlloc(size_t size)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 
MyFree(void * address)147 void MyFree(void *address)
148 {
149   PRINT_FREE("Free    ", g_allocCount, address);
150 
151   free(address);
152 }
153 
154 #ifdef _WIN32
155 
MidAlloc(size_t size)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 
MidFree(void * address)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 
SetLargePageSize()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 
BigAlloc(size_t size)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 
BigFree(void * address)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 
SzAlloc(ISzAllocPtr p,size_t size)240 static void *SzAlloc(ISzAllocPtr p, size_t size) { UNUSED_VAR(p); return MyAlloc(size); }
SzFree(ISzAllocPtr p,void * address)241 static void SzFree(ISzAllocPtr p, void *address) { UNUSED_VAR(p); MyFree(address); }
242 const ISzAlloc g_Alloc = { SzAlloc, SzFree };
243 
SzMidAlloc(ISzAllocPtr p,size_t size)244 static void *SzMidAlloc(ISzAllocPtr p, size_t size) { UNUSED_VAR(p); return MidAlloc(size); }
SzMidFree(ISzAllocPtr p,void * address)245 static void SzMidFree(ISzAllocPtr p, void *address) { UNUSED_VAR(p); MidFree(address); }
246 const ISzAlloc g_MidAlloc = { SzMidAlloc, SzMidFree };
247 
SzBigAlloc(ISzAllocPtr p,size_t size)248 static void *SzBigAlloc(ISzAllocPtr p, size_t size) { UNUSED_VAR(p); return BigAlloc(size); }
SzBigFree(ISzAllocPtr p,void * address)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 
SzAlignedAlloc(ISzAllocPtr pp,size_t size)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 
SzAlignedFree(ISzAllocPtr pp,void * address)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 
AlignOffsetAlloc_Alloc(ISzAllocPtr pp,size_t size)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 
AlignOffsetAlloc_Free(ISzAllocPtr pp,void * address)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 
AlignOffsetAlloc_CreateVTable(CAlignOffsetAlloc * p)451 void AlignOffsetAlloc_CreateVTable(CAlignOffsetAlloc *p)
452 {
453   p->vt.Alloc = AlignOffsetAlloc_Alloc;
454   p->vt.Free = AlignOffsetAlloc_Free;
455 }
456