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