tests/test-ssfmalloc.c

   1 /* Test of simple and straight-forward malloc implementation.
   2    Copyright (C) 2020-2024 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation, either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  16
  17 /* Written by Bruno Haible <bruno@clisp.org>, 2020.  */
  18
  19 #include <config.h>
  20
  21 #include <stdint.h>
  22 #include <stdlib.h>
  23
  24 #if defined _WIN32 && !defined __CYGWIN__
  25
  26 /* Declare VirtualAlloc(), GetSystemInfo.  */
  27 # define WIN32_LEAN_AND_MEAN
  28 # define WIN32_EXTRA_LEAN
  29 # include <windows.h>
  30
  31 #else
  32
  33 /* Declare getpagesize(). */
  34 # include <unistd.h>
  35 /* On HP-UX, getpagesize exists, but it is not declared in <unistd.h> even if
  36    the compiler options -D_HPUX_SOURCE -D_XOPEN_SOURCE=600 are used.  */
  37 # ifdef __hpux
  38 extern
  39 #  ifdef __cplusplus
  40        "C"
  41 #  endif
  42        int getpagesize (void);
  43 # endif
  44
  45 /* Declare mmap().  */
  46 # include <sys/types.h>
  47 # include <sys/mman.h>
  48
  49 /* Some old mmap() implementations require the flag MAP_VARIABLE whenever you
  50    pass an addr == NULL. */
  51 # ifndef MAP_VARIABLE
  52 #  define MAP_VARIABLE 0
  53 # endif
  54
  55 #endif
  56
  57 /* ================= Back end of the malloc implementation ================= */
  58
  59 /* The memory page size.
  60    Once it is initialized, a power of 2.  Typically 4096 or 8192.  */
  61 static uintptr_t pagesize;
  62
  63 /* Initializes pagesize.  */
  64 static void
  65 init_pagesize (void)
  66 {
  67 #if defined _WIN32 && !defined __CYGWIN__
  68   /* GetSystemInfo
  69      <https://msdn.microsoft.com/en-us/library/ms724381.aspx>
  70      <https://msdn.microsoft.com/en-us/library/ms724958.aspx>  */
  71   SYSTEM_INFO info;
  72   GetSystemInfo (&info);
  73   pagesize = info.dwPageSize;
  74 #else
  75   pagesize = getpagesize ();
  76 #endif
  77 }
  78
  79 /* Allocates a contiguous set of pages of memory.
  80    size > 0, must be a multiple of pagesize.
  81    Returns a multiple of PAGESIZE, or 0 upon failure.  */
  82 static uintptr_t
  83 alloc_pages (size_t size)
  84 {
  85 #if defined _WIN32 && !defined __CYGWIN__
  86   /* VirtualAlloc
  87      <https://msdn.microsoft.com/en-us/library/aa366887.aspx>
  88      <https://msdn.microsoft.com/en-us/library/aa366786.aspx>  */
  89   void *mem = VirtualAlloc (NULL, size, MEM_COMMIT, PAGE_READWRITE);
  90   if (mem == NULL)
  91     return 0;
  92   return (uintptr_t) mem;
  93 #else
  94   /* Use mmap with the MAP_ANONYMOUS or MAP_ANON flag.  */
  95   void *mem = mmap (NULL, size, PROT_READ | PROT_WRITE,
  96                     MAP_PRIVATE | MAP_ANONYMOUS | MAP_VARIABLE, -1, 0);
  97   if (mem == (void *)(-1))
  98     return 0;
  99   return (uintptr_t) mem;
 100 #endif
 101 }
 102
 103 /* Frees a contiguous set of pages of memory, returned by alloc_pages.
 104    size > 0, must be a multiple of pagesize.  */
 105 static void
 106 free_pages (uintptr_t pages, size_t size)
 107 {
 108 #if defined _WIN32 && !defined __CYGWIN__
 109   /* VirtualFree
 110      <https://docs.microsoft.com/en-us/windows/win32/api/memoryapi/nf-memoryapi-virtualfree>  */
 111   if (!VirtualFree ((void *) pages, 0, MEM_RELEASE))
 112     abort ();
 113 #else
 114   if ((pages & (pagesize - 1)) != 0)
 115     abort ();
 116   if (munmap ((void *) pages, size) < 0)
 117     abort ();
 118 #endif
 119 }
 120
 121 /* Cygwin defines PAGESIZE in <limits.h>.  */
 122 #undef PAGESIZE
 123
 124 /* ======================= Instantiate the front end ======================= */
 125
 126 #define PAGESIZE pagesize
 127 /* On Cygwin and Linux/PowerPC, PAGESIZE is 65536.  On macOS 11, it is 16384.
 128    On all other platforms, it is either 4096 or 8192.  */
 129 #if defined __CYGWIN__ || (defined __linux__ && defined __powerpc__)
 130 # define PAGESIZE_MAX 65536
 131 #else
 132 # define PAGESIZE_MAX 16384
 133 #endif
 134
 135 #define ALLOC_PAGES alloc_pages
 136 #define FREE_PAGES free_pages
 137 #define ALIGNMENT (sizeof (void *)) /* or 8 or 16 or 32 */
 138 #define PAGE_RESERVED_HEADER_SIZE (3 * UINTPTR_WIDTH / 8) /* = 3 * sizeof (void *) */
 139
 140 #include "ssfmalloc.h"
 141
 142 /* ================================= Tests ================================= */
 143
 144 #include <limits.h>
 145 #include <string.h>
 146
 147 #include "macros.h"
 148
 149 /* Fills a block of a given size with some contents.  */
 150 static void
 151 fill_block (uintptr_t block, size_t size)
 152 {
 153   unsigned char code = (size % (UCHAR_MAX - 1)) + 1;
 154   memset ((char *) block, code, size);
 155 }
 156
 157 /* Verifies that the contents of a block is still present
 158    (i.e. has not accidentally been overwritten by other operations).  */
 159 static void
 160 verify_block (uintptr_t block, size_t size)
 161 {
 162   unsigned char code = (size % (UCHAR_MAX - 1)) + 1;
 163   char *p = (char *) block;
 164   for (; size > 0; p++, size--)
 165     if ((unsigned char) *p != code)
 166       abort ();
 167 }
 168
 169 static size_t block_sizes[] =
 170   {
 171     /* Small blocks.  */
 172     1,
 173     2,
 174     3,
 175     4,
 176     5,
 177     6,
 178     7,
 179     8,
 180     9,
 181     12,
 182     15,
 183     16,
 184     17,
 185     24,
 186     31,
 187     32,
 188     37,
 189     42,
 190     49,
 191     57,
 192     63,
 193     64,
 194     65,
 195     71,
 196     77,
 197     83,
 198     96,
 199     99,
 200     110,
 201     119,
 202     127,
 203     128,
 204     130,
 205     144,
 206     150,
 207     157,
 208     161,
 209     169,
 210     180,
 211     192,
 212     199,
 213     204,
 214     210,
 215     224,
 216     225,
 217     236,
 218     241,
 219     249,
 220     255,
 221     256,
 222     /* Medium blocks.  */
 223     257,
 224     281,
 225     284,
 226     294,
 227     301,
 228     308,
 229     341,
 230     447,
 231     525,
 232     659,
 233     771,
 234     842,
 235     729,
 236     999,
 237     1000,
 238     1020,
 239     1023,
 240     1024,
 241     1025,
 242     1280,
 243     1414,
 244     2047,
 245     2048,
 246     2049,
 247     2096,
 248     2401,
 249     2613,
 250     2843,
 251     3010,
 252     3213,
 253     3512,
 254     3678,
 255     3801,
 256     3900,
 257     /* Large blocks.  */
 258     4000,
 259     4060,
 260     4080,
 261     4090,
 262     4095,
 263     4096,
 264     4097,
 265     4121,
 266     5381,
 267     7814,
 268     8191,
 269     8192,
 270     8193,
 271     11238,
 272     16383,
 273     16384,
 274     16385,
 275     20184,
 276     51202,
 277     135010
 278   };
 279
 280 #define RANDOM(n) (rand () % (n))
 281 #define RANDOM_BLOCK_SIZE() block_sizes[RANDOM (SIZEOF (block_sizes))]
 282
 283 int
 284 main (int argc, char *argv[])
 285 {
 286   /* Allow the user to provide a non-default random seed on the command line.  */
 287   if (argc > 1)
 288     srand (atoi (argv[1]));
 289
 290   init_pagesize ();
 291
 292   /* Randomly allocate and deallocate blocks.
 293      Also verify that there are no unexpected modifications to the contents of
 294      these blocks.  */
 295   {
 296     unsigned int repeat;
 297     char *blocks[SIZEOF (block_sizes)];
 298
 299     {
 300       size_t i;
 301
 302       for (i = 0; i < SIZEOF (block_sizes); i++)
 303         blocks[i] = NULL;
 304     }
 305
 306     for (repeat = 0; repeat < 100000; repeat++)
 307       {
 308         unsigned int operation = RANDOM (2);
 309
 310         switch (operation)
 311           {
 312           case 0:
 313             { /* Allocate a block.  */
 314               size_t i = RANDOM (SIZEOF (block_sizes));
 315               size_t size = block_sizes[i];
 316               if (blocks[i] == NULL)
 317                 {
 318                   uintptr_t block = allocate_block (size);
 319                   if (block == 0)
 320                     abort ();
 321                   fill_block (block, size);
 322                   blocks[i] = (char *) block;
 323                 }
 324             }
 325             break;
 326           case 1:
 327             { /* Free a block.  */
 328               size_t i = RANDOM (SIZEOF (block_sizes));
 329               size_t size = block_sizes[i];
 330               if (blocks[i] != NULL)
 331                 {
 332                   uintptr_t block = (uintptr_t) blocks[i];
 333                   verify_block (block, size);
 334                   free_block (block);
 335                   blocks[i] = NULL;
 336                 }
 337             }
 338             break;
 339           }
 340       }
 341
 342     /* Free the remaining blocks.  */
 343     {
 344       size_t i;
 345
 346       for (i = 0; i < SIZEOF (block_sizes); i++)
 347         if (blocks[i] != NULL)
 348           {
 349             uintptr_t block = (uintptr_t) blocks[i];
 350             size_t size = block_sizes[i];
 351             verify_block (block, size);
 352             free_block (block);
 353           }
 354     }
 355   }
 356
 357   return test_exit_status;
 358 }