1/* GLIB sliced memory - fast threaded memory chunk allocator
2 * Copyright (C) 2005 Tim Janik
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
8 *
9 * This library 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 GNU
12 * Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, write to the
16 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17 * Boston, MA 02111-1307, USA.
18 */
19#include <glib.h>
20
21#include <stdio.h>
22#include <string.h>
23
24#define quick_rand32()  (rand_accu = 1664525 * rand_accu + 1013904223, rand_accu)
25static guint    prime_size = 1021; // 769; // 509
26static gboolean clean_memchunks = FALSE;
27static guint    number_of_blocks = 10000;          /* total number of blocks allocated */
28static guint    number_of_repetitions = 10000;     /* number of alloc+free repetitions */
29static gboolean want_corruption = FALSE;
30
31/* --- old memchunk prototypes (memchunks.c) --- */
32void            old_mem_chunks_init     (void);
33GMemChunk*      old_mem_chunk_new       (const gchar  *name,
34                                         gint          atom_size,
35                                         gulong        area_size,
36                                         gint          type);
37void            old_mem_chunk_destroy   (GMemChunk *mem_chunk);
38gpointer        old_mem_chunk_alloc     (GMemChunk *mem_chunk);
39gpointer        old_mem_chunk_alloc0    (GMemChunk *mem_chunk);
40void            old_mem_chunk_free      (GMemChunk *mem_chunk,
41                                         gpointer   mem);
42void            old_mem_chunk_clean     (GMemChunk *mem_chunk);
43void            old_mem_chunk_reset     (GMemChunk *mem_chunk);
44void            old_mem_chunk_print     (GMemChunk *mem_chunk);
45void            old_mem_chunk_info      (void);
46#ifndef G_ALLOC_AND_FREE
47#define G_ALLOC_AND_FREE  2
48#endif
49
50/* --- functions --- */
51static inline int
52corruption (void)
53{
54  if (G_UNLIKELY (want_corruption))
55    {
56      /* corruption per call likelyness is about 1:4000000 */
57      guint32 r = g_random_int() % 8000009;
58      return r == 277 ? +1 : r == 281 ? -1 : 0;
59    }
60  return 0;
61}
62
63static inline gpointer
64memchunk_alloc (GMemChunk **memchunkp,
65                guint       size)
66{
67  size = MAX (size, 1);
68  if (G_UNLIKELY (!*memchunkp))
69    *memchunkp = old_mem_chunk_new ("", size, 4096, G_ALLOC_AND_FREE);
70  return old_mem_chunk_alloc (*memchunkp);
71}
72
73static inline void
74memchunk_free (GMemChunk *memchunk,
75               gpointer   chunk)
76{
77  old_mem_chunk_free (memchunk, chunk);
78  if (clean_memchunks)
79    old_mem_chunk_clean (memchunk);
80}
81
82static gpointer
83test_memchunk_thread (gpointer data)
84{
85  GMemChunk **memchunks;
86  guint i, j;
87  guint8 **ps;
88  guint   *ss;
89  guint32 rand_accu = 2147483563;
90  /* initialize random numbers */
91  if (data)
92    rand_accu = *(guint32*) data;
93  else
94    {
95      GTimeVal rand_tv;
96      g_get_current_time (&rand_tv);
97      rand_accu = rand_tv.tv_usec + (rand_tv.tv_sec << 16);
98    }
99
100  /* prepare for memchunk creation */
101  memchunks = g_alloca (sizeof (memchunks[0]) * prime_size);
102  memset (memchunks, 0, sizeof (memchunks[0]) * prime_size);
103
104  ps = g_new (guint8*, number_of_blocks);
105  ss = g_new (guint, number_of_blocks);
106  /* create number_of_blocks random sizes */
107  for (i = 0; i < number_of_blocks; i++)
108    ss[i] = quick_rand32() % prime_size;
109  /* allocate number_of_blocks blocks */
110  for (i = 0; i < number_of_blocks; i++)
111    ps[i] = memchunk_alloc (&memchunks[ss[i]], ss[i]);
112  for (j = 0; j < number_of_repetitions; j++)
113    {
114      /* free number_of_blocks/2 blocks */
115      for (i = 0; i < number_of_blocks; i += 2)
116        memchunk_free (memchunks[ss[i]], ps[i]);
117      /* allocate number_of_blocks/2 blocks with new sizes */
118      for (i = 0; i < number_of_blocks; i += 2)
119        {
120          ss[i] = quick_rand32() % prime_size;
121          ps[i] = memchunk_alloc (&memchunks[ss[i]], ss[i]);
122        }
123    }
124  /* free number_of_blocks blocks */
125  for (i = 0; i < number_of_blocks; i++)
126    memchunk_free (memchunks[ss[i]], ps[i]);
127  /* alloc and free many equally sized chunks in a row */
128  for (i = 0; i < number_of_repetitions; i++)
129    {
130      guint sz = quick_rand32() % prime_size;
131      guint k = number_of_blocks / 100;
132      for (j = 0; j < k; j++)
133        ps[j] = memchunk_alloc (&memchunks[sz], sz);
134      for (j = 0; j < k; j++)
135        memchunk_free (memchunks[sz], ps[j]);
136    }
137  /* cleanout memchunks */
138  for (i = 0; i < prime_size; i++)
139    if (memchunks[i])
140      old_mem_chunk_destroy (memchunks[i]);
141  g_free (ps);
142  g_free (ss);
143
144  return NULL;
145}
146
147static gpointer
148test_sliced_mem_thread (gpointer data)
149{
150  guint32 rand_accu = 2147483563;
151  guint i, j;
152  guint8 **ps;
153  guint   *ss;
154
155  /* initialize random numbers */
156  if (data)
157    rand_accu = *(guint32*) data;
158  else
159    {
160      GTimeVal rand_tv;
161      g_get_current_time (&rand_tv);
162      rand_accu = rand_tv.tv_usec + (rand_tv.tv_sec << 16);
163    }
164
165  ps = g_new (guint8*, number_of_blocks);
166  ss = g_new (guint, number_of_blocks);
167  /* create number_of_blocks random sizes */
168  for (i = 0; i < number_of_blocks; i++)
169    ss[i] = quick_rand32() % prime_size;
170  /* allocate number_of_blocks blocks */
171  for (i = 0; i < number_of_blocks; i++)
172    ps[i] = g_slice_alloc (ss[i] + corruption());
173  for (j = 0; j < number_of_repetitions; j++)
174    {
175      /* free number_of_blocks/2 blocks */
176      for (i = 0; i < number_of_blocks; i += 2)
177        g_slice_free1 (ss[i] + corruption(), ps[i] + corruption());
178      /* allocate number_of_blocks/2 blocks with new sizes */
179      for (i = 0; i < number_of_blocks; i += 2)
180        {
181          ss[i] = quick_rand32() % prime_size;
182          ps[i] = g_slice_alloc (ss[i] + corruption());
183        }
184    }
185  /* free number_of_blocks blocks */
186  for (i = 0; i < number_of_blocks; i++)
187    g_slice_free1 (ss[i] + corruption(), ps[i] + corruption());
188  /* alloc and free many equally sized chunks in a row */
189  for (i = 0; i < number_of_repetitions; i++)
190    {
191      guint sz = quick_rand32() % prime_size;
192      guint k = number_of_blocks / 100;
193      for (j = 0; j < k; j++)
194        ps[j] = g_slice_alloc (sz + corruption());
195      for (j = 0; j < k; j++)
196        g_slice_free1 (sz + corruption(), ps[j] + corruption());
197    }
198  g_free (ps);
199  g_free (ss);
200
201  return NULL;
202}
203
204static void
205usage (void)
206{
207  g_print ("Usage: slice-test [n_threads] [G|S|M|O][f][c][~] [maxblocksize] [seed]\n");
208}
209
210int
211main (int   argc,
212      char *argv[])
213{
214  guint seed32, *seedp = NULL;
215  gboolean ccounters = FALSE, use_memchunks = FALSE;
216  guint n_threads = 1;
217  const gchar *mode = "slab allocator + magazine cache", *emode = " ";
218  if (argc > 1)
219    n_threads = g_ascii_strtoull (argv[1], NULL, 10);
220  if (argc > 2)
221    {
222      guint i, l = strlen (argv[2]);
223      for (i = 0; i < l; i++)
224        switch (argv[2][i])
225          {
226          case 'G': /* GLib mode */
227            g_slice_set_config (G_SLICE_CONFIG_ALWAYS_MALLOC, FALSE);
228            g_slice_set_config (G_SLICE_CONFIG_BYPASS_MAGAZINES, FALSE);
229            mode = "slab allocator + magazine cache";
230            break;
231          case 'S': /* slab mode */
232            g_slice_set_config (G_SLICE_CONFIG_ALWAYS_MALLOC, FALSE);
233            g_slice_set_config (G_SLICE_CONFIG_BYPASS_MAGAZINES, TRUE);
234            mode = "slab allocator";
235            break;
236          case 'M': /* malloc mode */
237            g_slice_set_config (G_SLICE_CONFIG_ALWAYS_MALLOC, TRUE);
238            mode = "system malloc";
239            break;
240          case 'O': /* old memchunks */
241            use_memchunks = TRUE;
242            mode = "old memchunks";
243            break;
244          case 'f': /* eager freeing */
245            g_slice_set_config (G_SLICE_CONFIG_WORKING_SET_MSECS, 0);
246            clean_memchunks = TRUE;
247            emode = " with eager freeing";
248            break;
249          case 'c': /* print contention counters */
250            ccounters = TRUE;
251            break;
252          case '~':
253            want_corruption = TRUE; /* force occasional corruption */
254            break;
255          default:
256            usage();
257            return 1;
258          }
259    }
260  if (argc > 3)
261    prime_size = g_ascii_strtoull (argv[3], NULL, 10);
262  if (argc > 4)
263    {
264      seed32 = g_ascii_strtoull (argv[4], NULL, 10);
265      seedp = &seed32;
266    }
267
268  g_thread_init (NULL);
269
270  if (argc <= 1)
271    usage();
272
273  {
274    gchar strseed[64] = "<random>";
275    GThread **threads;
276    guint i;
277
278    if (seedp)
279      g_snprintf (strseed, 64, "%u", *seedp);
280    g_print ("Starting %d threads allocating random blocks <= %u bytes with seed=%s using %s%s\n", n_threads, prime_size, strseed, mode, emode);
281
282    threads = g_alloca (sizeof(GThread*) * n_threads);
283    if (!use_memchunks)
284      for (i = 0; i < n_threads; i++)
285        threads[i] = g_thread_create_full (test_sliced_mem_thread, seedp, 0, TRUE, FALSE, 0, NULL);
286    else
287      {
288        old_mem_chunks_init();
289        for (i = 0; i < n_threads; i++)
290          threads[i] = g_thread_create_full (test_memchunk_thread, seedp, 0, TRUE, FALSE, 0, NULL);
291      }
292    for (i = 0; i < n_threads; i++)
293      g_thread_join (threads[i]);
294
295    if (ccounters)
296      {
297        guint n, n_chunks = g_slice_get_config (G_SLICE_CONFIG_CHUNK_SIZES);
298        g_print ("    ChunkSize | MagazineSize | Contention\n");
299        for (i = 0; i < n_chunks; i++)
300          {
301            gint64 *vals = g_slice_get_config_state (G_SLICE_CONFIG_CONTENTION_COUNTER, i, &n);
302            g_print ("  %9llu   |  %9llu   |  %9llu\n", vals[0], vals[2], vals[1]);
303            g_free (vals);
304          }
305      }
306    else
307      g_print ("Done.\n");
308    return 0;
309  }
310}
311