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