1 /* $Cambridge: exim/src/src/store.c,v 1.5 2009/11/16 19:50:37 nm4 Exp $ */
3 /*************************************************
4 * Exim - an Internet mail transport agent *
5 *************************************************/
7 /* Copyright (c) University of Cambridge 1995 - 2009 */
8 /* See the file NOTICE for conditions of use and distribution. */
10 /* Exim gets and frees all its store through these functions. In the original
11 implementation there was a lot of mallocing and freeing of small bits of store.
12 The philosophy has now changed to a scheme which includes the concept of
13 "stacking pools" of store. For the short-lived processes, there isn't any real
14 need to do any garbage collection, but the stack concept allows quick resetting
15 in places where this seems sensible.
17 Obviously the long-running processes (the daemon, the queue runner, and eximon)
18 must take care not to eat store.
20 The following different types of store are recognized:
22 . Long-lived, large blocks: This is implemented by retaining the original
23 malloc/free functions, and it used for permanent working buffers and for
24 getting blocks to cut up for the other types.
26 . Long-lived, small blocks: This is used for blocks that have to survive until
27 the process exits. It is implemented as a stacking pool (POOL_PERM). This is
28 functionally the same as store_malloc(), except that the store can't be
29 freed, but I expect it to be more efficient for handling small blocks.
31 . Short-lived, short blocks: Most of the dynamic store falls into this
32 category. It is implemented as a stacking pool (POOL_MAIN) which is reset
33 after accepting a message when multiple messages are received by a single
34 process. Resetting happens at some other times as well, usually fairly
35 locally after some specific processing that needs working store.
37 . There is a separate pool (POOL_SEARCH) that is used only for lookup storage.
38 This means it can be freed when search_tidyup() is called to close down all
47 /* We need to know how to align blocks of data for general use. I'm not sure
48 how to get an alignment factor in general. In the current world, a value of 8
49 is probably right, and this is sizeof(double) on some systems and sizeof(void
50 *) on others, so take the larger of those. Since everything in this expression
51 is a constant, the compiler should optimize it to a simple constant wherever it
52 appears (I checked that gcc does do this). */
55 ((sizeof(void *) > sizeof(double))? sizeof(void *) : sizeof(double))
57 /* Size of block to get from malloc to carve up into smaller ones. This
58 must be a multiple of the alignment. We assume that 8192 is going to be
61 #define STORE_BLOCK_SIZE 8192
63 /* store_reset() will not free the following block if the last used block has
64 less than this much left in it. */
66 #define STOREPOOL_MIN_SIZE 256
68 /* Structure describing the beginning of each big block. */
70 typedef struct storeblock {
71 struct storeblock *next;
75 /* Just in case we find ourselves on a system where the structure above has a
76 length that is not a multiple of the alignment, set up a macro for the padded
79 #define ALIGNED_SIZEOF_STOREBLOCK \
80 (((sizeof(storeblock) + alignment - 1) / alignment) * alignment)
82 /* Variables holding data for the local pools of store. The current pool number
83 is held in store_pool, which is global so that it can be changed from outside.
84 Setting the initial length values to -1 forces a malloc for the first call,
85 even if the length is zero (which is used for getting a point to reset to). */
87 int store_pool = POOL_PERM;
89 static storeblock *chainbase[3] = { NULL, NULL, NULL };
90 static storeblock *current_block[3] = { NULL, NULL, NULL };
91 static void *next_yield[3] = { NULL, NULL, NULL };
92 static int yield_length[3] = { -1, -1, -1 };
94 /* pool_malloc holds the amount of memory used by the store pools; this goes up
95 and down as store is reset or released. nonpool_malloc is the total got by
96 malloc from other calls; this doesn't go down because it is just freed by
99 static int pool_malloc = 0;
100 static int nonpool_malloc = 0;
102 /* This variable is set by store_get() to its yield, and by store_reset() to
103 NULL. This enables string_cat() to optimize its store handling for very long
104 strings. That's why the variable is global. */
106 void *store_last_get[3] = { NULL, NULL, NULL };
110 /*************************************************
111 * Get a block from the current pool *
112 *************************************************/
114 /* Running out of store is a total disaster. This function is called via the
115 macro store_get(). It passes back a block of store within the current big
116 block, getting a new one if necessary. The address is saved in
121 filename source file from which called
122 linenumber line number in source file.
124 Returns: pointer to store (panic on malloc failure)
128 store_get_3(int size, const char *filename, int linenumber)
130 /* Round up the size to a multiple of the alignment. Although this looks a
131 messy statement, because "alignment" is a constant expression, the compiler can
132 do a reasonable job of optimizing, especially if the value of "alignment" is a
133 power of two. I checked this with -O2, and gcc did very well, compiling it to 4
134 instructions on a Sparc (alignment = 8). */
136 if (size % alignment != 0) size += alignment - (size % alignment);
138 /* If there isn't room in the current block, get a new one. The minimum
139 size is STORE_BLOCK_SIZE, and we would expect this to be the norm, since
140 these functions are mostly called for small amounts of store. */
142 if (size > yield_length[store_pool])
144 int length = (size <= STORE_BLOCK_SIZE)? STORE_BLOCK_SIZE : size;
145 int mlength = length + ALIGNED_SIZEOF_STOREBLOCK;
146 storeblock *newblock = NULL;
148 /* Sometimes store_reset() may leave a block for us; check if we can use it */
150 if (current_block[store_pool] != NULL &&
151 current_block[store_pool]->next != NULL)
153 newblock = current_block[store_pool]->next;
154 if (newblock->length < length)
156 /* Give up on this block, because it's too small */
157 store_free(newblock);
162 /* If there was no free block, get a new one */
164 if (newblock == NULL)
166 pool_malloc += mlength; /* Used in pools */
167 nonpool_malloc -= mlength; /* Exclude from overall total */
168 newblock = store_malloc(mlength);
169 newblock->next = NULL;
170 newblock->length = length;
171 if (chainbase[store_pool] == NULL) chainbase[store_pool] = newblock;
172 else current_block[store_pool]->next = newblock;
175 current_block[store_pool] = newblock;
176 yield_length[store_pool] = newblock->length;
177 next_yield[store_pool] =
178 (void *)((char *)current_block[store_pool] + ALIGNED_SIZEOF_STOREBLOCK);
179 VALGRIND_MAKE_MEM_NOACCESS(next_yield[store_pool], yield_length[store_pool]);
182 /* There's (now) enough room in the current block; the yield is the next
185 store_last_get[store_pool] = next_yield[store_pool];
187 /* Cut out the debugging stuff for utilities, but stop picky compilers from
190 #ifdef COMPILE_UTILITY
192 linenumber = linenumber;
196 if (running_in_test_harness)
197 debug_printf("---%d Get %5d\n", store_pool, size);
199 debug_printf("---%d Get %6p %5d %-14s %4d\n", store_pool,
200 store_last_get[store_pool], size, filename, linenumber);
202 #endif /* COMPILE_UTILITY */
204 VALGRIND_MAKE_MEM_UNDEFINED(store_last_get[store_pool], size);
205 /* Update next pointer and number of bytes left in the current block. */
207 next_yield[store_pool] = (void *)((char *)next_yield[store_pool] + size);
208 yield_length[store_pool] -= size;
210 return store_last_get[store_pool];
215 /*************************************************
216 * Get a block from the PERM pool *
217 *************************************************/
219 /* This is just a convenience function, useful when just a single block is to
224 filename source file from which called
225 linenumber line number in source file.
227 Returns: pointer to store (panic on malloc failure)
231 store_get_perm_3(int size, const char *filename, int linenumber)
234 int old_pool = store_pool;
235 store_pool = POOL_PERM;
236 yield = store_get_3(size, filename, linenumber);
237 store_pool = old_pool;
243 /*************************************************
244 * Extend a block if it is at the top *
245 *************************************************/
247 /* While reading strings of unknown length, it is often the case that the
248 string is being read into the block at the top of the stack. If it needs to be
249 extended, it is more efficient just to extend the top block rather than
250 allocate a new block and then have to copy the data. This function is provided
251 for the use of string_cat(), but of course can be used elsewhere too.
254 ptr pointer to store block
255 oldsize current size of the block, as requested by user
256 newsize new size required
257 filename source file from which called
258 linenumber line number in source file
260 Returns: TRUE if the block is at the top of the stack and has been
261 extended; FALSE if it isn't at the top of the stack, or cannot
266 store_extend_3(void *ptr, int oldsize, int newsize, const char *filename,
269 int inc = newsize - oldsize;
270 int rounded_oldsize = oldsize;
272 if (rounded_oldsize % alignment != 0)
273 rounded_oldsize += alignment - (rounded_oldsize % alignment);
275 if ((char *)ptr + rounded_oldsize != (char *)(next_yield[store_pool]) ||
276 inc > yield_length[store_pool] + rounded_oldsize - oldsize)
279 /* Cut out the debugging stuff for utilities, but stop picky compilers from
282 #ifdef COMPILE_UTILITY
284 linenumber = linenumber;
288 if (running_in_test_harness)
289 debug_printf("---%d Ext %5d\n", store_pool, newsize);
291 debug_printf("---%d Ext %6p %5d %-14s %4d\n", store_pool, ptr, newsize,
292 filename, linenumber);
294 #endif /* COMPILE_UTILITY */
296 if (newsize % alignment != 0) newsize += alignment - (newsize % alignment);
297 next_yield[store_pool] = (char *)ptr + newsize;
298 yield_length[store_pool] -= newsize - rounded_oldsize;
299 VALGRIND_MAKE_MEM_UNDEFINED(ptr + oldsize, inc);
306 /*************************************************
307 * Back up to a previous point on the stack *
308 *************************************************/
310 /* This function resets the next pointer, freeing any subsequent whole blocks
311 that are now unused. Normally it is given a pointer that was the yield of a
312 call to store_get, and is therefore aligned, but it may be given an offset
313 after such a pointer in order to release the end of a block and anything that
317 ptr place to back up to
318 filename source file from which called
319 linenumber line number in source file
325 store_reset_3(void *ptr, const char *filename, int linenumber)
328 storeblock *b = current_block[store_pool];
329 char *bc = (char *)b + ALIGNED_SIZEOF_STOREBLOCK;
332 /* Last store operation was not a get */
334 store_last_get[store_pool] = NULL;
336 /* See if the place is in the current block - as it often will be. Otherwise,
337 search for the block in which it lies. */
339 if ((char *)ptr < bc || (char *)ptr > bc + b->length)
341 for (b = chainbase[store_pool]; b != NULL; b = b->next)
343 bc = (char *)b + ALIGNED_SIZEOF_STOREBLOCK;
344 if ((char *)ptr >= bc && (char *)ptr <= bc + b->length) break;
347 log_write(0, LOG_MAIN|LOG_PANIC_DIE, "internal error: store_reset(%d) "
348 "failed: pool=%d %-14s %4d", ptr, store_pool, filename, linenumber);
351 /* Back up, rounding to the alignment if necessary. When testing, flatten
352 the released memory. */
354 newlength = bc + b->length - (char *)ptr;
355 #ifndef COMPILE_UTILITY
356 if (running_in_test_harness) memset(ptr, 0xF0, newlength);
358 VALGRIND_MAKE_MEM_NOACCESS(ptr, newlength);
359 yield_length[store_pool] = newlength - (newlength % alignment);
360 next_yield[store_pool] = (char *)ptr + (newlength % alignment);
361 current_block[store_pool] = b;
363 /* Free any subsequent block. Do NOT free the first successor, if our
364 current block has less than 256 bytes left. This should prevent us from
365 flapping memory. However, keep this block only when it has the default size. */
367 if (yield_length[store_pool] < STOREPOOL_MIN_SIZE &&
369 b->next->length == STORE_BLOCK_SIZE)
372 VALGRIND_MAKE_MEM_NOACCESS((char *)b + ALIGNED_SIZEOF_STOREBLOCK, b->length - ALIGNED_SIZEOF_STOREBLOCK);
382 pool_malloc -= b->length + ALIGNED_SIZEOF_STOREBLOCK;
383 store_free_3(b, filename, linenumber);
386 /* Cut out the debugging stuff for utilities, but stop picky compilers from
389 #ifdef COMPILE_UTILITY
391 linenumber = linenumber;
395 if (running_in_test_harness)
396 debug_printf("---%d Rst ** %d\n", store_pool, pool_malloc);
398 debug_printf("---%d Rst %6p ** %-14s %4d %d\n", store_pool, ptr,
399 filename, linenumber, pool_malloc);
401 #endif /* COMPILE_UTILITY */
408 /************************************************
410 ************************************************/
412 /* This function is specifically provided for use when reading very
413 long strings, e.g. header lines. When the string gets longer than a
414 complete block, it gets copied to a new block. It is helpful to free
415 the old block iff the previous copy of the string is at its start,
416 and therefore the only thing in it. Otherwise, for very long strings,
417 dead store can pile up somewhat disastrously. This function checks that
418 the pointer it is given is the first thing in a block, and if so,
422 block block of store to consider
423 filename source file from which called
424 linenumber line number in source file
430 store_release_3(void *block, const char *filename, int linenumber)
434 /* It will never be the first block, so no need to check that. */
436 for (b = chainbase[store_pool]; b != NULL; b = b->next)
438 storeblock *bb = b->next;
439 if (bb != NULL && (char *)block == (char *)bb + ALIGNED_SIZEOF_STOREBLOCK)
442 pool_malloc -= bb->length + ALIGNED_SIZEOF_STOREBLOCK;
444 /* Cut out the debugging stuff for utilities, but stop picky compilers
445 from giving warnings. */
447 #ifdef COMPILE_UTILITY
449 linenumber = linenumber;
453 if (running_in_test_harness)
454 debug_printf("-Release %d\n", pool_malloc);
456 debug_printf("-Release %6p %-20s %4d %d\n", (void *)bb, filename,
457 linenumber, pool_malloc);
459 if (running_in_test_harness)
460 memset(bb, 0xF0, bb->length+ALIGNED_SIZEOF_STOREBLOCK);
461 #endif /* COMPILE_UTILITY */
472 /*************************************************
474 *************************************************/
476 /* Running out of store is a total disaster for exim. Some malloc functions
477 do not run happily on very small sizes, nor do they document this fact. This
478 function is called via the macro store_malloc().
481 size amount of store wanted
482 filename source file from which called
483 linenumber line number in source file
485 Returns: pointer to gotten store (panic on failure)
489 store_malloc_3(int size, const char *filename, int linenumber)
493 if (size < 16) size = 16;
494 yield = malloc((size_t)size);
497 log_write(0, LOG_MAIN|LOG_PANIC_DIE, "failed to malloc %d bytes of memory: "
498 "called from line %d of %s", size, linenumber, filename);
500 nonpool_malloc += size;
502 /* Cut out the debugging stuff for utilities, but stop picky compilers from
505 #ifdef COMPILE_UTILITY
507 linenumber = linenumber;
510 /* If running in test harness, spend time making sure all the new store
511 is not filled with zeros so as to catch problems. */
513 if (running_in_test_harness)
515 memset(yield, 0xF0, (size_t)size);
516 DEBUG(D_memory) debug_printf("--Malloc %5d %d %d\n", size, pool_malloc,
521 DEBUG(D_memory) debug_printf("--Malloc %6p %5d %-14s %4d %d %d\n", yield,
522 size, filename, linenumber, pool_malloc, nonpool_malloc);
524 #endif /* COMPILE_UTILITY */
530 /************************************************
532 ************************************************/
534 /* This function is called by the macro store_free().
537 block block of store to free
538 filename source file from which called
539 linenumber line number in source file
545 store_free_3(void *block, const char *filename, int linenumber)
547 #ifdef COMPILE_UTILITY
549 linenumber = linenumber;
553 if (running_in_test_harness)
554 debug_printf("----Free\n");
556 debug_printf("----Free %6p %-20s %4d\n", block, filename, linenumber);
558 #endif /* COMPILE_UTILITY */