tests/memchunks.c

   1 /* GLIB - Library of useful routines for C programming
   2  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
   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
  20 /*
  21  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
  22  * file for a list of people on the GLib Team.  See the ChangeLog
  23  * files for a list of changes.  These files are distributed with
  24  * GLib at ftp://ftp.gtk.org/pub/gtk/.
  25  */
  26
  27 /*
  28  * MT safe
  29  */
  30
  31 #include "config.h"
  32
  33 #include <stdlib.h>
  34 #include <string.h>
  35 #include <signal.h>
  36
  37 #include "glib.h"
  38
  39 /* notes on macros:
  40  * if ENABLE_GC_FRIENDLY is defined, freed memory should be 0-wiped.
  41  */
  42
  43 #define MEM_PROFILE_TABLE_SIZE 4096
  44
  45 #define MEM_AREA_SIZE 4L
  46
  47 static guint mem_chunk_recursion = 0;
  48 #  define MEM_CHUNK_ROUTINE_COUNT()     (mem_chunk_recursion)
  49 #  define ENTER_MEM_CHUNK_ROUTINE()     (mem_chunk_recursion = MEM_CHUNK_ROUTINE_COUNT () + 1)
  50 #  define LEAVE_MEM_CHUNK_ROUTINE()     (mem_chunk_recursion = MEM_CHUNK_ROUTINE_COUNT () - 1)
  51
  52 /* --- old memchunk prototypes --- */
  53 GMemChunk*      old_mem_chunk_new       (const gchar  *name,
  54                                          gint          atom_size,
  55                                          gulong        area_size,
  56                                          gint          type);
  57 void            old_mem_chunk_destroy   (GMemChunk *mem_chunk);
  58 gpointer        old_mem_chunk_alloc     (GMemChunk *mem_chunk);
  59 gpointer        old_mem_chunk_alloc0    (GMemChunk *mem_chunk);
  60 void            old_mem_chunk_free      (GMemChunk *mem_chunk,
  61                                          gpointer   mem);
  62 void            old_mem_chunk_clean     (GMemChunk *mem_chunk);
  63 void            old_mem_chunk_reset     (GMemChunk *mem_chunk);
  64 void            old_mem_chunk_print     (GMemChunk *mem_chunk);
  65 void            old_mem_chunk_info      (void);
  66
  67
  68 /* --- MemChunks --- */
  69 #ifndef G_ALLOC_AND_FREE
  70 typedef struct _GAllocator GAllocator;
  71 typedef struct _GMemChunk  GMemChunk;
  72 #define G_ALLOC_ONLY      1
  73 #define G_ALLOC_AND_FREE  2
  74 #endif
  75
  76 typedef struct _GFreeAtom      GFreeAtom;
  77 typedef struct _GMemArea       GMemArea;
  78
  79 struct _GFreeAtom
  80 {
  81   GFreeAtom *next;
  82 };
  83
  84 struct _GMemArea
  85 {
  86   GMemArea *next;            /* the next mem area */
  87   GMemArea *prev;            /* the previous mem area */
  88   gulong index;              /* the current index into the "mem" array */
  89   gulong free;               /* the number of free bytes in this mem area */
  90   gulong allocated;          /* the number of atoms allocated from this area */
  91   gulong mark;               /* is this mem area marked for deletion */
  92   gchar mem[MEM_AREA_SIZE];  /* the mem array from which atoms get allocated
  93                               * the actual size of this array is determined by
  94                               *  the mem chunk "area_size". ANSI says that it
  95                               *  must be declared to be the maximum size it
  96                               *  can possibly be (even though the actual size
  97                               *  may be less).
  98                               */
  99 };
 100
 101 struct _GMemChunk
 102 {
 103   const gchar *name;         /* name of this MemChunk...used for debugging output */
 104   gint type;                 /* the type of MemChunk: ALLOC_ONLY or ALLOC_AND_FREE */
 105   gint num_mem_areas;        /* the number of memory areas */
 106   gint num_marked_areas;     /* the number of areas marked for deletion */
 107   guint atom_size;           /* the size of an atom */
 108   gulong area_size;          /* the size of a memory area */
 109   GMemArea *mem_area;        /* the current memory area */
 110   GMemArea *mem_areas;       /* a list of all the mem areas owned by this chunk */
 111   GMemArea *free_mem_area;   /* the free area...which is about to be destroyed */
 112   GFreeAtom *free_atoms;     /* the free atoms list */
 113   GTree *mem_tree;           /* tree of mem areas sorted by memory address */
 114   GMemChunk *next;           /* pointer to the next chunk */
 115   GMemChunk *prev;           /* pointer to the previous chunk */
 116 };
 117
 118
 119 static gulong old_mem_chunk_compute_size (gulong    size,
 120                                           gulong    min_size) G_GNUC_CONST;
 121 static gint   old_mem_chunk_area_compare (GMemArea *a,
 122                                           GMemArea *b);
 123 static gint   old_mem_chunk_area_search  (GMemArea *a,
 124                                           gchar    *addr);
 125
 126 /* here we can't use StaticMutexes, as they depend upon a working
 127  * g_malloc, the same holds true for StaticPrivate
 128  */
 129 static GMutex         mem_chunks_lock;
 130 static GMemChunk     *mem_chunks = NULL;
 131
 132 GMemChunk*
 133 old_mem_chunk_new (const gchar  *name,
 134                    gint          atom_size,
 135                    gulong        area_size,
 136                    gint          type)
 137 {
 138   GMemChunk *mem_chunk;
 139   gulong rarea_size;
 140
 141   g_return_val_if_fail (atom_size > 0, NULL);
 142   g_return_val_if_fail (area_size >= atom_size, NULL);
 143
 144   ENTER_MEM_CHUNK_ROUTINE ();
 145
 146   area_size = (area_size + atom_size - 1) / atom_size;
 147   area_size *= atom_size;
 148
 149   mem_chunk = g_new (GMemChunk, 1);
 150   mem_chunk->name = name;
 151   mem_chunk->type = type;
 152   mem_chunk->num_mem_areas = 0;
 153   mem_chunk->num_marked_areas = 0;
 154   mem_chunk->mem_area = NULL;
 155   mem_chunk->free_mem_area = NULL;
 156   mem_chunk->free_atoms = NULL;
 157   mem_chunk->mem_tree = NULL;
 158   mem_chunk->mem_areas = NULL;
 159   mem_chunk->atom_size = atom_size;
 160
 161   if (mem_chunk->type == G_ALLOC_AND_FREE)
 162     mem_chunk->mem_tree = g_tree_new ((GCompareFunc) old_mem_chunk_area_compare);
 163
 164   if (mem_chunk->atom_size % G_MEM_ALIGN)
 165     mem_chunk->atom_size += G_MEM_ALIGN - (mem_chunk->atom_size % G_MEM_ALIGN);
 166
 167   rarea_size = area_size + sizeof (GMemArea) - MEM_AREA_SIZE;
 168   rarea_size = old_mem_chunk_compute_size (rarea_size, atom_size + sizeof (GMemArea) - MEM_AREA_SIZE);
 169   mem_chunk->area_size = rarea_size - (sizeof (GMemArea) - MEM_AREA_SIZE);
 170
 171   g_mutex_lock (&mem_chunks_lock);
 172   mem_chunk->next = mem_chunks;
 173   mem_chunk->prev = NULL;
 174   if (mem_chunks)
 175     mem_chunks->prev = mem_chunk;
 176   mem_chunks = mem_chunk;
 177   g_mutex_unlock (&mem_chunks_lock);
 178
 179   LEAVE_MEM_CHUNK_ROUTINE ();
 180
 181   return mem_chunk;
 182 }
 183
 184 void
 185 old_mem_chunk_destroy (GMemChunk *mem_chunk)
 186 {
 187   GMemArea *mem_areas;
 188   GMemArea *temp_area;
 189
 190   g_return_if_fail (mem_chunk != NULL);
 191
 192   ENTER_MEM_CHUNK_ROUTINE ();
 193
 194   mem_areas = mem_chunk->mem_areas;
 195   while (mem_areas)
 196     {
 197       temp_area = mem_areas;
 198       mem_areas = mem_areas->next;
 199       g_free (temp_area);
 200     }
 201
 202   g_mutex_lock (&mem_chunks_lock);
 203   if (mem_chunk->next)
 204     mem_chunk->next->prev = mem_chunk->prev;
 205   if (mem_chunk->prev)
 206     mem_chunk->prev->next = mem_chunk->next;
 207
 208   if (mem_chunk == mem_chunks)
 209     mem_chunks = mem_chunks->next;
 210   g_mutex_unlock (&mem_chunks_lock);
 211
 212   if (mem_chunk->type == G_ALLOC_AND_FREE)
 213     g_tree_destroy (mem_chunk->mem_tree);
 214
 215   g_free (mem_chunk);
 216
 217   LEAVE_MEM_CHUNK_ROUTINE ();
 218 }
 219
 220 gpointer
 221 old_mem_chunk_alloc (GMemChunk *mem_chunk)
 222 {
 223   GMemArea *temp_area;
 224   gpointer mem;
 225
 226   ENTER_MEM_CHUNK_ROUTINE ();
 227
 228   g_return_val_if_fail (mem_chunk != NULL, NULL);
 229
 230   while (mem_chunk->free_atoms)
 231     {
 232       /* Get the first piece of memory on the "free_atoms" list.
 233        * We can go ahead and destroy the list node we used to keep
 234        *  track of it with and to update the "free_atoms" list to
 235        *  point to its next element.
 236        */
 237       mem = mem_chunk->free_atoms;
 238       mem_chunk->free_atoms = mem_chunk->free_atoms->next;
 239
 240       /* Determine which area this piece of memory is allocated from */
 241       temp_area = g_tree_search (mem_chunk->mem_tree,
 242                                  (GCompareFunc) old_mem_chunk_area_search,
 243                                  mem);
 244
 245       /* If the area has been marked, then it is being destroyed.
 246        *  (ie marked to be destroyed).
 247        * We check to see if all of the segments on the free list that
 248        *  reference this area have been removed. This occurs when
 249        *  the amount of free memory is less than the allocatable size.
 250        * If the chunk should be freed, then we place it in the "free_mem_area".
 251        * This is so we make sure not to free the mem area here and then
 252        *  allocate it again a few lines down.
 253        * If we don't allocate a chunk a few lines down then the "free_mem_area"
 254        *  will be freed.
 255        * If there is already a "free_mem_area" then we'll just free this mem area.
 256        */
 257       if (temp_area->mark)
 258         {
 259           /* Update the "free" memory available in that area */
 260           temp_area->free += mem_chunk->atom_size;
 261
 262           if (temp_area->free == mem_chunk->area_size)
 263             {
 264               if (temp_area == mem_chunk->mem_area)
 265                 mem_chunk->mem_area = NULL;
 266
 267               if (mem_chunk->free_mem_area)
 268                 {
 269                   mem_chunk->num_mem_areas -= 1;
 270
 271                   if (temp_area->next)
 272                     temp_area->next->prev = temp_area->prev;
 273                   if (temp_area->prev)
 274                     temp_area->prev->next = temp_area->next;
 275                   if (temp_area == mem_chunk->mem_areas)
 276                     mem_chunk->mem_areas = mem_chunk->mem_areas->next;
 277
 278                   if (mem_chunk->type == G_ALLOC_AND_FREE)
 279                     g_tree_remove (mem_chunk->mem_tree, temp_area);
 280                   g_free (temp_area);
 281                 }
 282               else
 283                 mem_chunk->free_mem_area = temp_area;
 284
 285               mem_chunk->num_marked_areas -= 1;
 286             }
 287         }
 288       else
 289         {
 290           /* Update the number of allocated atoms count.
 291            */
 292           temp_area->allocated += 1;
 293
 294           /* The area wasn't marked...return the memory
 295            */
 296           goto outa_here;
 297         }
 298     }
 299
 300   /* If there isn't a current mem area or the current mem area is out of space
 301    *  then allocate a new mem area. We'll first check and see if we can use
 302    *  the "free_mem_area". Otherwise we'll just malloc the mem area.
 303    */
 304   if ((!mem_chunk->mem_area) ||
 305       ((mem_chunk->mem_area->index + mem_chunk->atom_size) > mem_chunk->area_size))
 306     {
 307       if (mem_chunk->free_mem_area)
 308         {
 309           mem_chunk->mem_area = mem_chunk->free_mem_area;
 310           mem_chunk->free_mem_area = NULL;
 311         }
 312       else
 313         {
 314 #ifdef ENABLE_GC_FRIENDLY
 315           mem_chunk->mem_area = (GMemArea*) g_malloc0 (sizeof (GMemArea) -
 316                                                        MEM_AREA_SIZE +
 317                                                        mem_chunk->area_size);
 318 #else /* !ENABLE_GC_FRIENDLY */
 319           mem_chunk->mem_area = (GMemArea*) g_malloc (sizeof (GMemArea) -
 320                                                       MEM_AREA_SIZE +
 321                                                       mem_chunk->area_size);
 322 #endif /* ENABLE_GC_FRIENDLY */
 323
 324           mem_chunk->num_mem_areas += 1;
 325           mem_chunk->mem_area->next = mem_chunk->mem_areas;
 326           mem_chunk->mem_area->prev = NULL;
 327
 328           if (mem_chunk->mem_areas)
 329             mem_chunk->mem_areas->prev = mem_chunk->mem_area;
 330           mem_chunk->mem_areas = mem_chunk->mem_area;
 331
 332           if (mem_chunk->type == G_ALLOC_AND_FREE)
 333             g_tree_insert (mem_chunk->mem_tree, mem_chunk->mem_area, mem_chunk->mem_area);
 334         }
 335
 336       mem_chunk->mem_area->index = 0;
 337       mem_chunk->mem_area->free = mem_chunk->area_size;
 338       mem_chunk->mem_area->allocated = 0;
 339       mem_chunk->mem_area->mark = 0;
 340     }
 341
 342   /* Get the memory and modify the state variables appropriately.
 343    */
 344   mem = (gpointer) &mem_chunk->mem_area->mem[mem_chunk->mem_area->index];
 345   mem_chunk->mem_area->index += mem_chunk->atom_size;
 346   mem_chunk->mem_area->free -= mem_chunk->atom_size;
 347   mem_chunk->mem_area->allocated += 1;
 348
 349  outa_here:
 350
 351   LEAVE_MEM_CHUNK_ROUTINE ();
 352
 353   return mem;
 354 }
 355
 356 gpointer
 357 old_mem_chunk_alloc0 (GMemChunk *mem_chunk)
 358 {
 359   gpointer mem;
 360
 361   mem = old_mem_chunk_alloc (mem_chunk);
 362   if (mem)
 363     {
 364       memset (mem, 0, mem_chunk->atom_size);
 365     }
 366
 367   return mem;
 368 }
 369
 370 void
 371 old_mem_chunk_free (GMemChunk *mem_chunk,
 372                     gpointer   mem)
 373 {
 374   GMemArea *temp_area;
 375   GFreeAtom *free_atom;
 376
 377   g_return_if_fail (mem_chunk != NULL);
 378   g_return_if_fail (mem != NULL);
 379
 380   ENTER_MEM_CHUNK_ROUTINE ();
 381
 382 #ifdef ENABLE_GC_FRIENDLY
 383   memset (mem, 0, mem_chunk->atom_size);
 384 #endif /* ENABLE_GC_FRIENDLY */
 385
 386   /* Don't do anything if this is an ALLOC_ONLY chunk
 387    */
 388   if (mem_chunk->type == G_ALLOC_AND_FREE)
 389     {
 390       /* Place the memory on the "free_atoms" list
 391        */
 392       free_atom = (GFreeAtom*) mem;
 393       free_atom->next = mem_chunk->free_atoms;
 394       mem_chunk->free_atoms = free_atom;
 395
 396       temp_area = g_tree_search (mem_chunk->mem_tree,
 397                                  (GCompareFunc) old_mem_chunk_area_search,
 398                                  mem);
 399
 400       temp_area->allocated -= 1;
 401
 402       if (temp_area->allocated == 0)
 403         {
 404           temp_area->mark = 1;
 405           mem_chunk->num_marked_areas += 1;
 406         }
 407     }
 408
 409   LEAVE_MEM_CHUNK_ROUTINE ();
 410 }
 411
 412 /* This doesn't free the free_area if there is one */
 413 void
 414 old_mem_chunk_clean (GMemChunk *mem_chunk)
 415 {
 416   GMemArea *mem_area;
 417   GFreeAtom *prev_free_atom;
 418   GFreeAtom *temp_free_atom;
 419   gpointer mem;
 420
 421   g_return_if_fail (mem_chunk != NULL);
 422
 423   ENTER_MEM_CHUNK_ROUTINE ();
 424
 425   if (mem_chunk->type == G_ALLOC_AND_FREE)
 426     {
 427       prev_free_atom = NULL;
 428       temp_free_atom = mem_chunk->free_atoms;
 429
 430       while (temp_free_atom)
 431         {
 432           mem = (gpointer) temp_free_atom;
 433
 434           mem_area = g_tree_search (mem_chunk->mem_tree,
 435                                     (GCompareFunc) old_mem_chunk_area_search,
 436                                     mem);
 437
 438           /* If this mem area is marked for destruction then delete the
 439            *  area and list node and decrement the free mem.
 440            */
 441           if (mem_area->mark)
 442             {
 443               if (prev_free_atom)
 444                 prev_free_atom->next = temp_free_atom->next;
 445               else
 446                 mem_chunk->free_atoms = temp_free_atom->next;
 447               temp_free_atom = temp_free_atom->next;
 448
 449               mem_area->free += mem_chunk->atom_size;
 450               if (mem_area->free == mem_chunk->area_size)
 451                 {
 452                   mem_chunk->num_mem_areas -= 1;
 453                   mem_chunk->num_marked_areas -= 1;
 454
 455                   if (mem_area->next)
 456                     mem_area->next->prev = mem_area->prev;
 457                   if (mem_area->prev)
 458                     mem_area->prev->next = mem_area->next;
 459                   if (mem_area == mem_chunk->mem_areas)
 460                     mem_chunk->mem_areas = mem_chunk->mem_areas->next;
 461                   if (mem_area == mem_chunk->mem_area)
 462                     mem_chunk->mem_area = NULL;
 463
 464                   if (mem_chunk->type == G_ALLOC_AND_FREE)
 465                     g_tree_remove (mem_chunk->mem_tree, mem_area);
 466                   g_free (mem_area);
 467                 }
 468             }
 469           else
 470             {
 471               prev_free_atom = temp_free_atom;
 472               temp_free_atom = temp_free_atom->next;
 473             }
 474         }
 475     }
 476   LEAVE_MEM_CHUNK_ROUTINE ();
 477 }
 478
 479 void
 480 old_mem_chunk_reset (GMemChunk *mem_chunk)
 481 {
 482   GMemArea *mem_areas;
 483   GMemArea *temp_area;
 484
 485   g_return_if_fail (mem_chunk != NULL);
 486
 487   ENTER_MEM_CHUNK_ROUTINE ();
 488
 489   mem_areas = mem_chunk->mem_areas;
 490   mem_chunk->num_mem_areas = 0;
 491   mem_chunk->mem_areas = NULL;
 492   mem_chunk->mem_area = NULL;
 493
 494   while (mem_areas)
 495     {
 496       temp_area = mem_areas;
 497       mem_areas = mem_areas->next;
 498       g_free (temp_area);
 499     }
 500
 501   mem_chunk->free_atoms = NULL;
 502
 503   if (mem_chunk->mem_tree)
 504     {
 505       g_tree_destroy (mem_chunk->mem_tree);
 506       mem_chunk->mem_tree = g_tree_new ((GCompareFunc) old_mem_chunk_area_compare);
 507     }
 508
 509   LEAVE_MEM_CHUNK_ROUTINE ();
 510 }
 511
 512 void
 513 old_mem_chunk_print (GMemChunk *mem_chunk)
 514 {
 515   GMemArea *mem_areas;
 516   gulong mem;
 517
 518   g_return_if_fail (mem_chunk != NULL);
 519
 520   mem_areas = mem_chunk->mem_areas;
 521   mem = 0;
 522
 523   while (mem_areas)
 524     {
 525       mem += mem_chunk->area_size - mem_areas->free;
 526       mem_areas = mem_areas->next;
 527     }
 528
 529   g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO,
 530          "%s: %ld bytes using %d mem areas",
 531          mem_chunk->name, mem, mem_chunk->num_mem_areas);
 532 }
 533
 534 void
 535 old_mem_chunk_info (void)
 536 {
 537   GMemChunk *mem_chunk;
 538   gint count;
 539
 540   count = 0;
 541   g_mutex_lock (&mem_chunks_lock);
 542   mem_chunk = mem_chunks;
 543   while (mem_chunk)
 544     {
 545       count += 1;
 546       mem_chunk = mem_chunk->next;
 547     }
 548   g_mutex_unlock (&mem_chunks_lock);
 549
 550   g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "%d mem chunks", count);
 551
 552   g_mutex_lock (&mem_chunks_lock);
 553   mem_chunk = mem_chunks;
 554   g_mutex_unlock (&mem_chunks_lock);
 555
 556   while (mem_chunk)
 557     {
 558       old_mem_chunk_print ((GMemChunk*) mem_chunk);
 559       mem_chunk = mem_chunk->next;
 560     }
 561 }
 562
 563 static gulong
 564 old_mem_chunk_compute_size (gulong size,
 565                             gulong min_size)
 566 {
 567   gulong power_of_2;
 568   gulong lower, upper;
 569
 570   power_of_2 = 16;
 571   while (power_of_2 < size)
 572     power_of_2 <<= 1;
 573
 574   lower = power_of_2 >> 1;
 575   upper = power_of_2;
 576
 577   if (size - lower < upper - size && lower >= min_size)
 578     return lower;
 579   else
 580     return upper;
 581 }
 582
 583 static gint
 584 old_mem_chunk_area_compare (GMemArea *a,
 585                             GMemArea *b)
 586 {
 587   if (a->mem > b->mem)
 588     return 1;
 589   else if (a->mem < b->mem)
 590     return -1;
 591   return 0;
 592 }
 593
 594 static gint
 595 old_mem_chunk_area_search (GMemArea *a,
 596                            gchar    *addr)
 597 {
 598   if (a->mem <= addr)
 599     {
 600       if (addr < &a->mem[a->index])
 601         return 0;
 602       return 1;
 603     }
 604   return -1;
 605 }