camel/camel-memchunk.c

   1 /*
   2  * Copyright (C) 1999-2008 Novell, Inc. (www.novell.com)
   3  *
   4  * Authors: Michael Zucchi <notzed@ximian.com>
   5  *          Jacob Berkman <jacob@ximian.com>
   6  *
   7  * This program is free software; you can redistribute it and/or
   8  * modify it under the terms of version 2 of the GNU Lesser General Public
   9  * License as published by the Free Software Foundation.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
  19  * USA
  20  *
  21 */
  22
  23 #include "camel-memchunk.h"
  24
  25 #include <string.h> /* memset() */
  26
  27 /*#define TIMEIT*/
  28
  29 #ifdef TIMEIT
  30 #include <sys/time.h>
  31 #include <unistd.h>
  32
  33 struct timeval timeit_start;
  34
  35 static void
  36 time_start (const gchar *desc)
  37 {
  38         gettimeofday (&timeit_start, NULL);
  39         printf ("starting: %s\n", desc);
  40 }
  41
  42 static void
  43 time_end (const gchar *desc)
  44 {
  45         gulong diff;
  46         struct timeval end;
  47
  48         gettimeofday (&end, NULL);
  49         diff = end.tv_sec * 1000 + end.tv_usec / 1000;
  50         diff -= timeit_start.tv_sec * 1000 + timeit_start.tv_usec / 1000;
  51         printf (
  52                 "%s took %ld.%03ld seconds\n",
  53                 desc, diff / 1000, diff % 1000);
  54 }
  55 #else
  56 #define time_start(x)
  57 #define time_end(x)
  58 #endif
  59
  60 typedef struct _MemChunkFreeNode {
  61         struct _MemChunkFreeNode *next;
  62         guint atoms;
  63 } MemChunkFreeNode;
  64
  65 /**
  66  * CamelMemChunk:
  67  *
  68  * Since: 3.4
  69  **/
  70 struct _CamelMemChunk {
  71         guint blocksize;        /* number of atoms in a block */
  72         guint atomsize; /* size of each atom */
  73         GPtrArray *blocks;      /* blocks of raw memory */
  74         struct _MemChunkFreeNode *free;
  75 };
  76
  77 /**
  78  * camel_memchunk_new:
  79  * @atomcount: the number of atoms stored in a single malloc'd block of memory
  80  * @atomsize: the size of each allocation
  81  *
  82  * Create a new #CamelMemChunk header.  Memchunks are an efficient way to
  83  * allocate and deallocate identical sized blocks of memory quickly, and
  84  * space efficiently.
  85  *
  86  * camel_memchunks are effectively the same as gmemchunks, only faster (much),
  87  * and they use less memory overhead for housekeeping.
  88  *
  89  * Returns: a new #CamelMemChunk
  90  *
  91  * Since: 3.4
  92  **/
  93 CamelMemChunk *
  94 camel_memchunk_new (gint atomcount,
  95                     gint atomsize)
  96 {
  97         CamelMemChunk *memchunk = g_malloc (sizeof (*memchunk));
  98
  99         memchunk->blocksize = atomcount;
 100         memchunk->atomsize = MAX (atomsize, sizeof (MemChunkFreeNode));
 101         memchunk->blocks = g_ptr_array_new ();
 102         memchunk->free = NULL;
 103
 104         return memchunk;
 105 }
 106
 107 /**
 108  * camel_memchunk_alloc:
 109  * @memchunk: an #CamelMemChunk
 110  *
 111  * Allocate a new atom size block of memory from an #CamelMemChunk.
 112  * Free the returned atom with camel_memchunk_free().
 113  *
 114  * Returns: an allocated block of memory
 115  *
 116  * Since: 3.4
 117  **/
 118 gpointer
 119 camel_memchunk_alloc (CamelMemChunk *memchunk)
 120 {
 121         gchar *b;
 122         MemChunkFreeNode *f;
 123         gpointer mem;
 124
 125         f = memchunk->free;
 126         if (f) {
 127                 f->atoms--;
 128                 if (f->atoms > 0) {
 129                         mem = ((gchar *) f) + (f->atoms * memchunk->atomsize);
 130                 } else {
 131                         mem = f;
 132                         memchunk->free = memchunk->free->next;
 133                 }
 134                 return mem;
 135         } else {
 136                 b = g_malloc (memchunk->blocksize * memchunk->atomsize);
 137                 g_ptr_array_add (memchunk->blocks, b);
 138                 f = (MemChunkFreeNode *) &b[memchunk->atomsize];
 139                 f->atoms = memchunk->blocksize - 1;
 140                 f->next = NULL;
 141                 memchunk->free = f;
 142                 return b;
 143         }
 144 }
 145
 146 /**
 147  * camel_memchunk_alloc0:
 148  * @memchunk: an #CamelMemChunk
 149  *
 150  * Allocate a new atom size block of memory from an #CamelMemChunk,
 151  * and fill the memory with zeros.  Free the returned atom with
 152  * camel_memchunk_free().
 153  *
 154  * Returns: an allocated block of memory
 155  *
 156  * Since: 3.4
 157  **/
 158 gpointer
 159 camel_memchunk_alloc0 (CamelMemChunk *memchunk)
 160 {
 161         gpointer mem;
 162
 163         mem = camel_memchunk_alloc (memchunk);
 164         memset (mem, 0, memchunk->atomsize);
 165
 166         return mem;
 167 }
 168
 169 /**
 170  * camel_memchunk_free:
 171  * @memchunk: an #CamelMemChunk
 172  * @mem: address of atom to free
 173  *
 174  * Free a single atom back to the free pool of atoms in the given
 175  * memchunk.
 176  *
 177  * Since: 3.4
 178  **/
 179 void
 180 camel_memchunk_free (CamelMemChunk *memchunk,
 181                      gpointer mem)
 182 {
 183         MemChunkFreeNode *f;
 184
 185         /* Put the location back in the free list.  If we knew if the
 186          * preceeding or following cells were free, we could merge the
 187          * free nodes, but it doesn't really add much. */
 188         f = mem;
 189         f->next = memchunk->free;
 190         memchunk->free = f;
 191         f->atoms = 1;
 192
 193         /* We could store the free list sorted - we could then do the above,
 194          * and also probably improve the locality of reference properties for
 195          * the allocator.  (And it would simplify some other algorithms at
 196          * that, but slow this one down significantly.) */
 197 }
 198
 199 /**
 200  * camel_memchunk_empty:
 201  * @memchunk: an #CamelMemChunk
 202  *
 203  * Clean out the memchunk buffers.  Marks all allocated memory as free blocks,
 204  * but does not give it back to the system.  Can be used if the memchunk
 205  * is to be used repeatedly.
 206  *
 207  * Since: 3.4
 208  **/
 209 void
 210 camel_memchunk_empty (CamelMemChunk *memchunk)
 211 {
 212         MemChunkFreeNode *f, *h = NULL;
 213         gint i;
 214
 215         for (i = 0; i < memchunk->blocks->len; i++) {
 216                 f = (MemChunkFreeNode *) memchunk->blocks->pdata[i];
 217                 f->atoms = memchunk->blocksize;
 218                 f->next = h;
 219                 h = f;
 220         }
 221
 222         memchunk->free = h;
 223 }
 224
 225 struct _cleaninfo {
 226         struct _cleaninfo *next;
 227         gchar *base;
 228         gint count;
 229         gint size;              /* just so tree_search has it, sigh */
 230 };
 231
 232 static gint
 233 tree_compare (struct _cleaninfo *a,
 234               struct _cleaninfo *b)
 235 {
 236         if (a->base < b->base)
 237                 return -1;
 238         else if (a->base > b->base)
 239                 return 1;
 240         return 0;
 241 }
 242
 243 static gint
 244 tree_search (struct _cleaninfo *a,
 245              gchar *mem)
 246 {
 247         if (a->base <= mem) {
 248                 if (mem < &a->base[a->size])
 249                         return 0;
 250                 return 1;
 251         }
 252         return -1;
 253 }
 254
 255 /**
 256  * camel_memchunk_clean:
 257  * @memchunk: an #CamelMemChunk
 258  *
 259  * Scan all empty blocks and check for blocks which can be free'd
 260  * back to the system.
 261  *
 262  * This routine may take a while to run if there are many allocated
 263  * memory blocks (if the total number of allocations is many times
 264  * greater than atomcount).
 265  *
 266  * Since: 3.4
 267  **/
 268 void
 269 camel_memchunk_clean (CamelMemChunk *memchunk)
 270 {
 271         GTree *tree;
 272         gint i;
 273         MemChunkFreeNode *f;
 274         struct _cleaninfo *ci, *hi = NULL;
 275
 276         f = memchunk->free;
 277         if (memchunk->blocks->len == 0 || f == NULL)
 278                 return;
 279
 280         /* first, setup the tree/list so we can map free block addresses to block addresses */
 281         tree = g_tree_new ((GCompareFunc) tree_compare);
 282         for (i = 0; i < memchunk->blocks->len; i++) {
 283                 ci = alloca (sizeof (*ci));
 284                 ci->count = 0;
 285                 ci->base = memchunk->blocks->pdata[i];
 286                 ci->size = memchunk->blocksize * memchunk->atomsize;
 287                 g_tree_insert (tree, ci, ci);
 288                 ci->next = hi;
 289                 hi = ci;
 290         }
 291
 292         /* now, scan all free nodes, and count them in their tree node */
 293         while (f) {
 294                 ci = g_tree_search (tree, (GCompareFunc) tree_search, f);
 295                 if (ci) {
 296                         ci->count += f->atoms;
 297                 } else {
 298                         g_warning ("error, can't find free node in memory block\n");
 299                 }
 300                 f = f->next;
 301         }
 302
 303         /* if any nodes are all free, free & unlink them */
 304         ci = hi;
 305         while (ci) {
 306                 if (ci->count == memchunk->blocksize) {
 307                         MemChunkFreeNode *prev = NULL;
 308
 309                         f = memchunk->free;
 310                         while (f) {
 311                                 if (tree_search (ci, (gpointer) f) == 0) {
 312                                         /* prune this node from our free-node list */
 313                                         if (prev)
 314                                                 prev->next = f->next;
 315                                         else
 316                                                 memchunk->free = f->next;
 317                                 } else {
 318                                         prev = f;
 319                                 }
 320
 321                                 f = f->next;
 322                         }
 323
 324                         g_ptr_array_remove_fast (memchunk->blocks, ci->base);
 325                         g_free (ci->base);
 326                 }
 327                 ci = ci->next;
 328         }
 329
 330         g_tree_destroy (tree);
 331 }
 332
 333 /**
 334  * camel_memchunk_destroy:
 335  * @memchunk: an #CamelMemChunk
 336  *
 337  * Free the memchunk header, and all associated memory.
 338  *
 339  * Since: 3.4
 340  **/
 341 void
 342 camel_memchunk_destroy (CamelMemChunk *memchunk)
 343 {
 344         gint i;
 345
 346         if (memchunk == NULL)
 347                 return;
 348
 349         for (i = 0; i < memchunk->blocks->len; i++)
 350                 g_free (memchunk->blocks->pdata[i]);
 351
 352         g_ptr_array_free (memchunk->blocks, TRUE);
 353
 354         g_free (memchunk);
 355 }
 356
 357 #if 0
 358
 359 #define CHUNK_SIZE (20)
 360 #define CHUNK_COUNT (32)
 361
 362 #define s(x)
 363
 364 main ()
 365 {
 366         gint i;
 367         MemChunk *mc;
 368         gpointer mem, *last;
 369         GMemChunk *gmc;
 370         struct _EStrv *s;
 371
 372         s = strv_new (8);
 373         s = strv_set (s, 1, "Testing 1");
 374         s = strv_set (s, 2, "Testing 2");
 375         s = strv_set (s, 3, "Testing 3");
 376         s = strv_set (s, 4, "Testing 4");
 377         s = strv_set (s, 5, "Testing 5");
 378         s = strv_set (s, 6, "Testing 7");
 379
 380         for (i = 0; i < 8; i++) {
 381                 printf ("s[%d] = %s\n", i, strv_get (s, i));
 382         }
 383
 384         s (sleep (5));
 385
 386         printf ("packing ...\n");
 387         s = strv_pack (s);
 388
 389         for (i = 0; i < 8; i++) {
 390                 printf ("s[%d] = %s\n", i, strv_get (s, i));
 391         }
 392
 393         printf ("setting ...\n");
 394
 395         s = strv_set_ref (s, 1, "Testing 1 x");
 396
 397         for (i = 0; i < 8; i++) {
 398                 printf ("s[%d] = %s\n", i, strv_get (s, i));
 399         }
 400
 401         printf ("packing ...\n");
 402         s = strv_pack (s);
 403
 404         for (i = 0; i < 8; i++) {
 405                 printf ("s[%d] = %s\n", i, strv_get (s, i));
 406         }
 407
 408         strv_free (s);
 409
 410 #if 0
 411         time_start ("Using memchunks");
 412         mc = memchunk_new (CHUNK_COUNT, CHUNK_SIZE);
 413         for (i = 0; i < 1000000; i++) {
 414                 mem = memchunk_alloc (mc);
 415                 if ((i & 1) == 0)
 416                         memchunk_free (mc, mem);
 417         }
 418         s (sleep (10));
 419         memchunk_destroy (mc);
 420         time_end ("allocating 1000000 memchunks, freeing 500k");
 421
 422         time_start ("Using gmemchunks");
 423         gmc = g_mem_chunk_new ("memchunk", CHUNK_SIZE, CHUNK_SIZE * CHUNK_COUNT, G_ALLOC_AND_FREE);
 424         for (i = 0; i < 1000000; i++) {
 425                 mem = g_mem_chunk_alloc (gmc);
 426                 if ((i & 1) == 0)
 427                         g_mem_chunk_free (gmc, mem);
 428         }
 429         s (sleep (10));
 430         g_mem_chunk_destroy (gmc);
 431         time_end ("allocating 1000000 gmemchunks, freeing 500k");
 432
 433         time_start ("Using memchunks");
 434         mc = memchunk_new (CHUNK_COUNT, CHUNK_SIZE);
 435         for (i = 0; i < 1000000; i++) {
 436                 mem = memchunk_alloc (mc);
 437         }
 438         s (sleep (10));
 439         memchunk_destroy (mc);
 440         time_end ("allocating 1000000 memchunks");
 441
 442         time_start ("Using gmemchunks");
 443         gmc = g_mem_chunk_new ("memchunk", CHUNK_SIZE, CHUNK_COUNT * CHUNK_SIZE, G_ALLOC_ONLY);
 444         for (i = 0; i < 1000000; i++) {
 445                 mem = g_mem_chunk_alloc (gmc);
 446         }
 447         s (sleep (10));
 448         g_mem_chunk_destroy (gmc);
 449         time_end ("allocating 1000000 gmemchunks");
 450
 451         time_start ("Using malloc");
 452         for (i = 0; i < 1000000; i++) {
 453                 malloc (CHUNK_SIZE);
 454         }
 455         time_end ("allocating 1000000 malloc");
 456 #endif
 457
 458 }
 459
 460 #endif