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