1/* Alloc.c -- Memory allocation functions
  22018-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>
 21int g_allocCount = 0;
 22int g_allocCountMid = 0;
 23int 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
 33static 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
 40static 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
 62static void Print(const char *s)
 63{
 64  fputs(s, DEBUG_OUT_STREAM);
 65}
 66
 67static 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
 80static void PrintLn()
 81{
 82  Print("\n");
 83}
 84
 85static void PrintHex(UInt64 v, size_t align)
 86{
 87  char s[32];
 88  ConvertUInt64ToHex(v, s);
 89  PrintAligned(s, align);
 90}
 91
 92static void PrintDec(UInt64 v, size_t align)
 93{
 94  char s[32];
 95  ConvertUInt64ToString(v, s);
 96  PrintAligned(s, align);
 97}
 98
 99static 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
132void *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
147void MyFree(void *address)
148{
149  PRINT_FREE("Free    ", g_allocCount, address);
150  
151  free(address);
152}
153
154#ifdef _WIN32
155
156void *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
166void 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
180SIZE_T g_LargePageSize = 0;
181typedef SIZE_T (WINAPI *GetLargePageMinimumP)();
182#endif
183
184void 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
200void *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
228void 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
240static void *SzAlloc(ISzAllocPtr p, size_t size) { UNUSED_VAR(p); return MyAlloc(size); }
241static void SzFree(ISzAllocPtr p, void *address) { UNUSED_VAR(p); MyFree(address); }
242const ISzAlloc g_Alloc = { SzAlloc, SzFree };
243
244static void *SzMidAlloc(ISzAllocPtr p, size_t size) { UNUSED_VAR(p); return MidAlloc(size); }
245static void SzMidFree(ISzAllocPtr p, void *address) { UNUSED_VAR(p); MidFree(address); }
246const ISzAlloc g_MidAlloc = { SzMidAlloc, SzMidFree };
247
248static void *SzBigAlloc(ISzAllocPtr p, size_t size) { UNUSED_VAR(p); return BigAlloc(size); }
249static void SzBigFree(ISzAllocPtr p, void *address) { UNUSED_VAR(p); BigFree(address); }
250const 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/*
297static 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
322static 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
370static 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
382const 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
394static 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
438static 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
451void AlignOffsetAlloc_CreateVTable(CAlignOffsetAlloc *p)
452{
453  p->vt.Alloc = AlignOffsetAlloc_Alloc;
454  p->vt.Free = AlignOffsetAlloc_Free;
455}