Check query strings of query-style lookups for quoting. Bug 2850
[exim.git] / src / src / store.c
1 /*************************************************
2 *     Exim - an Internet mail transport agent    *
3 *************************************************/
4
5 /* Copyright (c) University of Cambridge 1995 - 2018 */
6 /* Copyright (c) The Exim maintainers 2019 - 2021 */
7 /* See the file NOTICE for conditions of use and distribution. */
8
9 /* Exim gets and frees all its store through these functions. In the original
10 implementation there was a lot of mallocing and freeing of small bits of store.
11 The philosophy has now changed to a scheme which includes the concept of
12 "stacking pools" of store. For the short-lived processes, there isn't any real
13 need to do any garbage collection, but the stack concept allows quick resetting
14 in places where this seems sensible.
15
16 Obviously the long-running processes (the daemon, the queue runner, and eximon)
17 must take care not to eat store.
18
19 The following different types of store are recognized:
20
21 . Long-lived, large blocks: This is implemented by retaining the original
22   malloc/free functions, and it used for permanent working buffers and for
23   getting blocks to cut up for the other types.
24
25 . Long-lived, small blocks: This is used for blocks that have to survive until
26   the process exits. It is implemented as a stacking pool (POOL_PERM). This is
27   functionally the same as store_malloc(), except that the store can't be
28   freed, but I expect it to be more efficient for handling small blocks.
29
30 . Short-lived, short blocks: Most of the dynamic store falls into this
31   category. It is implemented as a stacking pool (POOL_MAIN) which is reset
32   after accepting a message when multiple messages are received by a single
33   process. Resetting happens at some other times as well, usually fairly
34   locally after some specific processing that needs working store.
35
36 . There is a separate pool (POOL_SEARCH) that is used only for lookup storage.
37   This means it can be freed when search_tidyup() is called to close down all
38   the lookup caching.
39
40 - There is another pool (POOL_MESSAGE) used for medium-lifetime objects; within
41   a single message transaction but needed for longer than the use of the main
42   pool permits.  Currently this means only receive-time DKIM information.
43
44 - There is a dedicated pool for configuration data read from the config file(s).
45   Once complete, it is made readonly.
46
47 - There are pools for each active combination of lookup-quoting, dynamically created.
48
49 . Orthogonal to the four main pool types, there are two classes of memory: untainted
50   and tainted.  The latter is used for values derived from untrusted input, and
51   the string-expansion mechanism refuses to operate on such values (obviously,
52   it can expand an untainted value to return a tainted result).  The classes
53   are implemented by duplicating the four pool types.  Pool resets are requested
54   against the nontainted sibling and apply to both siblings.
55
56   Only memory blocks requested for tainted use are regarded as tainted; anything
57   else (including stack auto variables) is untainted.  Care is needed when coding
58   to not copy untrusted data into untainted memory, as downstream taint-checks
59   would be avoided.
60
61   Intermediate layers (eg. the string functions) can test for taint, and use this
62   for ensurinng that results have proper state.  For example the
63   string_vformat_trc() routing supporting the string_sprintf() interface will
64   recopy a string being built into a tainted allocation if it meets a %s for a
65   tainted argument.  Any intermediate-layer function that (can) return a new
66   allocation should behave this way; returning a tainted result if any tainted
67   content is used.  Intermediate-layer functions (eg. Ustrncpy) that modify
68   existing allocations fail if tainted data is written into an untainted area.
69   Users of functions that modify existing allocations should check if a tainted
70   source and an untainted destination is used, and fail instead (sprintf() being
71   the classic case).
72 */
73
74
75 #include "exim.h"
76 /* keep config.h before memcheck.h, for NVALGRIND */
77 #include "config.h"
78
79 #include <sys/mman.h>
80 #include "memcheck.h"
81
82
83 /* We need to know how to align blocks of data for general use. I'm not sure
84 how to get an alignment factor in general. In the current world, a value of 8
85 is probably right, and this is sizeof(double) on some systems and sizeof(void
86 *) on others, so take the larger of those. Since everything in this expression
87 is a constant, the compiler should optimize it to a simple constant wherever it
88 appears (I checked that gcc does do this). */
89
90 #define alignment \
91   (sizeof(void *) > sizeof(double) ? sizeof(void *) : sizeof(double))
92
93 /* store_reset() will not free the following block if the last used block has
94 less than this much left in it. */
95
96 #define STOREPOOL_MIN_SIZE 256
97
98 /* Structure describing the beginning of each big block. */
99
100 typedef struct storeblock {
101   struct storeblock *next;
102   size_t length;
103 } storeblock;
104
105 /* Pool descriptor struct */
106
107 typedef struct pooldesc {
108   storeblock *  chainbase;              /* list of blocks in pool */
109   storeblock *  current_block;          /* top block, still with free space */
110   void *        next_yield;             /* next allocation point */
111   int           yield_length;           /* remaining space in current block */
112   unsigned      store_block_order;      /* log2(size) block allocation size */
113
114   /* This variable is set by store_get() to its yield, and by store_reset() to
115   NULL. This enables string_cat() to optimize its store handling for very long
116   strings. That's why the variable is global. */
117
118   void *        store_last_get;
119
120   /* These are purely for stats-gathering */
121
122   int           nbytes;
123   int           maxbytes;
124   int           nblocks;
125   int           maxblocks;
126   unsigned      maxorder;
127 } pooldesc;
128
129 /* Enhanced pool descriptor for quoted pools */
130
131 typedef struct quoted_pooldesc {
132   pooldesc                      pool;
133   unsigned                      quoter;
134   struct quoted_pooldesc *      next;
135 } quoted_pooldesc;
136
137 /* Just in case we find ourselves on a system where the structure above has a
138 length that is not a multiple of the alignment, set up a macro for the padded
139 length. */
140
141 #define ALIGNED_SIZEOF_STOREBLOCK \
142   (((sizeof(storeblock) + alignment - 1) / alignment) * alignment)
143
144 /* Size of block to get from malloc to carve up into smaller ones. This
145 must be a multiple of the alignment. We assume that 4096 is going to be
146 suitably aligned.  Double the size per-pool for every malloc, to mitigate
147 certain denial-of-service attacks.  Don't bother to decrease on block frees.
148 We waste average half the current alloc size per pool.  This could be several
149 hundred kB now, vs. 4kB with a constant-size block size.  But the search time
150 for is_tainted(), linear in the number of blocks for the pool, is O(n log n)
151 rather than O(n^2).
152 A test of 2000 RCPTs and just accept ACL had 370kB in 21 blocks before,
153 504kB in 6 blocks now, for the untainted-main (largest) pool.
154 Builds for restricted-memory system can disable the expansion by
155 defining RESTRICTED_MEMORY */
156 /*XXX should we allow any for malloc's own overhead?  But how much? */
157
158 /* #define RESTRICTED_MEMORY */
159 #define STORE_BLOCK_SIZE(order) ((1U << (order)) - ALIGNED_SIZEOF_STOREBLOCK)
160
161 /* Variables holding data for the local pools of store. The current pool number
162 is held in store_pool, which is global so that it can be changed from outside.
163 Setting the initial length values to -1 forces a malloc for the first call,
164 even if the length is zero (which is used for getting a point to reset to). */
165
166 int store_pool = POOL_MAIN;
167
168 pooldesc paired_pools[N_PAIRED_POOLS];
169 quoted_pooldesc * quoted_pools = NULL;
170
171 static int n_nonpool_blocks;    /* current number of direct store_malloc() blocks */
172 static int max_nonpool_blocks;
173 static int max_pool_malloc;     /* max value for pool_malloc */
174 static int max_nonpool_malloc;  /* max value for nonpool_malloc */
175
176 /* pool_malloc holds the amount of memory used by the store pools; this goes up
177 and down as store is reset or released. nonpool_malloc is the total got by
178 malloc from other calls; this doesn't go down because it is just freed by
179 pointer. */
180
181 static int pool_malloc;
182 static int nonpool_malloc;
183
184
185 #ifndef COMPILE_UTILITY
186 static const uschar * pooluse[N_PAIRED_POOLS] = {
187 [POOL_MAIN] =           US"main",
188 [POOL_PERM] =           US"perm",
189 [POOL_CONFIG] =         US"config",
190 [POOL_SEARCH] =         US"search",
191 [POOL_MESSAGE] =        US"message",
192 [POOL_TAINT_MAIN] =     US"main",
193 [POOL_TAINT_PERM] =     US"perm",
194 [POOL_TAINT_CONFIG] =   US"config",
195 [POOL_TAINT_SEARCH] =   US"search",
196 [POOL_TAINT_MESSAGE] =  US"message",
197 };
198 static const uschar * poolclass[N_PAIRED_POOLS] = {
199 [POOL_MAIN] =           US"untainted",
200 [POOL_PERM] =           US"untainted",
201 [POOL_CONFIG] =         US"untainted",
202 [POOL_SEARCH] =         US"untainted",
203 [POOL_MESSAGE] =        US"untainted",
204 [POOL_TAINT_MAIN] =     US"tainted",
205 [POOL_TAINT_PERM] =     US"tainted",
206 [POOL_TAINT_CONFIG] =   US"tainted",
207 [POOL_TAINT_SEARCH] =   US"tainted",
208 [POOL_TAINT_MESSAGE] =  US"tainted",
209 };
210 #endif
211
212
213 static void * internal_store_malloc(size_t, const char *, int);
214 static void   internal_store_free(void *, const char *, int linenumber);
215
216 /******************************************************************************/
217
218 static void
219 pool_init(pooldesc * pp)
220 {
221 memset(pp, 0, sizeof(*pp));
222 pp->yield_length = -1;
223 pp->store_block_order = 12; /* log2(allocation_size) ie. 4kB */
224 }
225
226 /* Initialisation, for things fragile with parameter channges when using
227 static initialisers. */
228
229 void
230 store_init(void)
231 {
232 for (pooldesc * pp = paired_pools; pp < paired_pools + N_PAIRED_POOLS; pp++)
233   pool_init(pp);
234 }
235
236 /******************************************************************************/
237 /* Locating elements given memory pointer */
238
239 static BOOL
240 is_pointer_in_block(const storeblock * b, const void * p)
241 {
242 uschar * bc = US b + ALIGNED_SIZEOF_STOREBLOCK;
243 return US p >= bc && US p < bc + b->length;
244 }
245
246 static pooldesc *
247 pool_current_for_pointer(const void * p)
248 {
249 storeblock * b;
250
251 for (quoted_pooldesc * qp = quoted_pools; qp; qp = qp->next)
252   if ((b = qp->pool.current_block) && is_pointer_in_block(b, p))
253     return &qp->pool;
254
255 for (pooldesc * pp = paired_pools; pp < paired_pools + N_PAIRED_POOLS; pp++)
256   if ((b = pp->current_block) && is_pointer_in_block(b, p))
257     return pp;
258 return NULL;
259 }
260
261 static pooldesc *
262 pool_for_pointer(const void * p)
263 {
264 pooldesc * pp;
265 storeblock * b;
266
267 if ((pp = pool_current_for_pointer(p))) return pp;
268
269 for (quoted_pooldesc * qp = quoted_pools; qp; qp = qp->next)
270   for (b = qp->pool.chainbase; b; b = b->next)
271     if (is_pointer_in_block(b, p)) return &qp->pool;
272
273 for (pp = paired_pools; pp < paired_pools + N_PAIRED_POOLS; pp++)
274   for (b = pp->chainbase; b; b = b->next)
275     if (is_pointer_in_block(b, p)) return pp;
276
277 log_write(0, LOG_MAIN|LOG_PANIC_DIE, "bad memory reference; pool not found");
278 return NULL;
279 }
280
281 /******************************************************************************/
282 /* Test if a pointer refers to tainted memory.
283
284 Slower version check, for use when platform intermixes malloc and mmap area
285 addresses. Test against the current-block of all tainted pools first, then all
286 blocks of all tainted pools.
287
288 Return: TRUE iff tainted
289 */
290
291 BOOL
292 is_tainted_fn(const void * p)
293 {
294 storeblock * b;
295
296 if (p == GET_UNTAINTED) return FALSE;
297 if (p == GET_TAINTED) return TRUE;
298
299 for (pooldesc * pp = paired_pools + POOL_TAINT_BASE;
300      pp < paired_pools + N_PAIRED_POOLS; pp++)
301   if ((b = pp->current_block))
302     if (is_pointer_in_block(b, p)) return TRUE;
303
304 for (quoted_pooldesc * qp = quoted_pools; qp; qp = qp->next)
305   if (b = qp->pool.current_block)
306     if (is_pointer_in_block(b, p)) return TRUE;
307
308 for (pooldesc * pp = paired_pools + POOL_TAINT_BASE;
309      pp < paired_pools + N_PAIRED_POOLS; pp++)
310   for (b = pp->chainbase; b; b = b->next)
311     if (is_pointer_in_block(b, p)) return TRUE;
312
313 for (quoted_pooldesc * qp = quoted_pools; qp; qp = qp->next)
314   for (b = qp->pool.chainbase; b; b = b->next)
315     if (is_pointer_in_block(b, p)) return TRUE;
316
317 return FALSE;
318 }
319
320
321 void
322 die_tainted(const uschar * msg, const uschar * func, int line)
323 {
324 log_write(0, LOG_MAIN|LOG_PANIC_DIE, "Taint mismatch, %s: %s %d\n",
325         msg, func, line);
326 }
327
328
329 #ifndef COMPILE_UTILITY
330 /* Return the pool for the given quoter, or null */
331
332 static pooldesc *
333 pool_for_quoter(unsigned quoter)
334 {
335 for (quoted_pooldesc * qp = quoted_pools; qp; qp = qp->next)
336   if (qp->quoter == quoter)
337     return &qp->pool;
338 return NULL;
339 }
340
341 /* Allocate/init a new quoted-pool and return the pool */
342
343 static pooldesc *
344 quoted_pool_new(unsigned quoter)
345 {
346 // debug_printf("allocating quoted-pool\n");
347 quoted_pooldesc * qp = store_get_perm(sizeof(quoted_pooldesc), GET_UNTAINTED);
348
349 pool_init(&qp->pool);
350 qp->quoter = quoter;
351 qp->next = quoted_pools;
352 quoted_pools = qp;
353 return &qp->pool;
354 }
355 #endif
356
357
358 /******************************************************************************/
359 void
360 store_writeprotect(int pool)
361 {
362 #if !defined(COMPILE_UTILITY) && !defined(MISSING_POSIX_MEMALIGN)
363 for (storeblock * b =  paired_pools[pool].chainbase; b; b = b->next)
364   if (mprotect(b, ALIGNED_SIZEOF_STOREBLOCK + b->length, PROT_READ) != 0)
365     DEBUG(D_any) debug_printf("config block mprotect: (%d) %s\n", errno, strerror(errno));
366 #endif
367 }
368
369 /******************************************************************************/
370
371 static void *
372 pool_get(pooldesc * pp, int size, BOOL align_mem, const char * func, int linenumber)
373 {
374 /* Ensure we've been asked to allocate memory.
375 A negative size is a sign of a security problem.
376 A zero size might be also suspect, but our internal usage deliberately
377 does this to return a current watermark value for a later release of
378 allocated store. */
379
380 if (size < 0 || size >= INT_MAX/2)
381   log_write(0, LOG_MAIN|LOG_PANIC_DIE,
382             "bad memory allocation requested (%d bytes) at %s %d",
383             size, func, linenumber);
384
385 /* Round up the size to a multiple of the alignment. Although this looks a
386 messy statement, because "alignment" is a constant expression, the compiler can
387 do a reasonable job of optimizing, especially if the value of "alignment" is a
388 power of two. I checked this with -O2, and gcc did very well, compiling it to 4
389 instructions on a Sparc (alignment = 8). */
390
391 if (size % alignment != 0) size += alignment - (size % alignment);
392
393 /* If there isn't room in the current block, get a new one. The minimum
394 size is STORE_BLOCK_SIZE, and we would expect this to be the norm, since
395 these functions are mostly called for small amounts of store. */
396
397 if (size > pp->yield_length)
398   {
399   int length = MAX(
400           STORE_BLOCK_SIZE(pp->store_block_order) - ALIGNED_SIZEOF_STOREBLOCK,
401           size);
402   int mlength = length + ALIGNED_SIZEOF_STOREBLOCK;
403   storeblock * newblock;
404
405   /* Sometimes store_reset() may leave a block for us; check if we can use it */
406
407   if (  (newblock = pp->current_block)
408      && (newblock = newblock->next)
409      && newblock->length < length
410      )
411     {
412     /* Give up on this block, because it's too small */
413     pp->nblocks--;
414     internal_store_free(newblock, func, linenumber);
415     newblock = NULL;
416     }
417
418   /* If there was no free block, get a new one */
419
420   if (!newblock)
421     {
422     if ((pp->nbytes += mlength) > pp->maxbytes)
423       pp->maxbytes = pp->nbytes;
424     if ((pool_malloc += mlength) > max_pool_malloc)     /* Used in pools */
425       max_pool_malloc = pool_malloc;
426     nonpool_malloc -= mlength;                  /* Exclude from overall total */
427     if (++pp->nblocks > pp->maxblocks)
428       pp->maxblocks = pp->nblocks;
429
430 #ifndef MISSING_POSIX_MEMALIGN
431     if (align_mem)
432       {
433       long pgsize = sysconf(_SC_PAGESIZE);
434       int err = posix_memalign((void **)&newblock,
435                                 pgsize, (mlength + pgsize - 1) & ~(pgsize - 1));
436       if (err)
437         log_write(0, LOG_MAIN|LOG_PANIC_DIE,
438           "failed to alloc (using posix_memalign) %d bytes of memory: '%s'"
439           "called from line %d in %s",
440           size, strerror(err), linenumber, func);
441       }
442     else
443 #endif
444       newblock = internal_store_malloc(mlength, func, linenumber);
445     newblock->next = NULL;
446     newblock->length = length;
447 #ifndef RESTRICTED_MEMORY
448     if (pp->store_block_order++ > pp->maxorder)
449       pp->maxorder = pp->store_block_order;
450 #endif
451
452     if (! pp->chainbase)
453        pp->chainbase = newblock;
454     else
455       pp->current_block->next = newblock;
456     }
457
458   pp->current_block = newblock;
459   pp->yield_length = newblock->length;
460   pp->next_yield =
461     (void *)(CS pp->current_block + ALIGNED_SIZEOF_STOREBLOCK);
462   (void) VALGRIND_MAKE_MEM_NOACCESS(pp->next_yield, pp->yield_length);
463   }
464
465 /* There's (now) enough room in the current block; the yield is the next
466 pointer. */
467
468 pp->store_last_get = pp->next_yield;
469
470 (void) VALGRIND_MAKE_MEM_UNDEFINED(pp->store_last_get, size);
471 /* Update next pointer and number of bytes left in the current block. */
472
473 pp->next_yield = (void *)(CS pp->next_yield + size);
474 pp->yield_length -= size;
475 return pp->store_last_get;
476 }
477
478 /*************************************************
479 *       Get a block from the current pool        *
480 *************************************************/
481
482 /* Running out of store is a total disaster. This function is called via the
483 macro store_get(). The current store_pool is used, adjusting for taint.
484 If the protoype is quoted, use a quoted-pool.
485 Return a block of store within the current big block of the pool, getting a new
486 one if necessary. The address is saved in store_last_get for the pool.
487
488 Arguments:
489   size        amount wanted, bytes
490   proto_mem   class: get store conformant to this
491                 Special values: 0 forces untainted, 1 forces tainted
492   func        function from which called
493   linenumber  line number in source file
494
495 Returns:      pointer to store (panic on malloc failure)
496 */
497
498 void *
499 store_get_3(int size, const void * proto_mem, const char * func, int linenumber)
500 {
501 #ifndef COMPILE_UTILITY
502 int quoter = quoter_for_address(proto_mem);
503 #endif
504 pooldesc * pp;
505 void * yield;
506
507 #ifndef COMPILE_UTILITY
508 if (!is_real_quoter(quoter))
509 #endif
510   {
511   BOOL tainted = is_tainted(proto_mem);
512   int pool = tainted ? store_pool + POOL_TAINT_BASE : store_pool;
513   pp = paired_pools + pool;
514   yield = pool_get(pp, size, (pool == POOL_CONFIG), func, linenumber);
515
516   /* Cut out the debugging stuff for utilities, but stop picky compilers from
517   giving warnings. */
518
519 #ifndef COMPILE_UTILITY
520   DEBUG(D_memory)
521     debug_printf("---%d Get %6p %5d %-14s %4d\n", pool,
522       pp->store_last_get, size, func, linenumber);
523 #endif
524   }
525 #ifndef COMPILE_UTILITY
526 else
527   {
528   DEBUG(D_memory)
529     debug_printf("allocating quoted-block for quoter %u (from %s %d)\n",
530       quoter, func, linenumber);
531   if (!(pp = pool_for_quoter(quoter))) pp = quoted_pool_new(quoter);
532   yield = pool_get(pp, size, FALSE, func, linenumber);
533   DEBUG(D_memory)
534     debug_printf("---QQ Get %6p %5d %-14s %4d\n",
535       pp->store_last_get, size, func, linenumber);
536   }
537 #endif
538 return yield;
539 }
540
541
542
543 /*************************************************
544 *       Get a block from the PERM pool           *
545 *************************************************/
546
547 /* This is just a convenience function, useful when just a single block is to
548 be obtained.
549
550 Arguments:
551   size        amount wanted
552   proto_mem   class: get store conformant to this
553   func        function from which called
554   linenumber  line number in source file
555
556 Returns:      pointer to store (panic on malloc failure)
557 */
558
559 void *
560 store_get_perm_3(int size, const void * proto_mem, const char * func, int linenumber)
561 {
562 void * yield;
563 int old_pool = store_pool;
564 store_pool = POOL_PERM;
565 yield = store_get_3(size, proto_mem, func, linenumber);
566 store_pool = old_pool;
567 return yield;
568 }
569
570
571 #ifndef COMPILE_UTILITY
572 /*************************************************
573 *  Get a block annotated as being lookup-quoted  *
574 *************************************************/
575
576 /* Allocate from pool a pool consistent with the proto_mem augmented by the
577 requested quoter type.
578
579 XXX currently not handling mark/release
580
581 Args:   size            number of bytes to allocate
582         quoter          id for the quoting type
583         func            caller, for debug
584         linenumber      caller, for debug
585
586 Return: allocated memory block
587 */
588
589 static void *
590 store_force_get_quoted(int size, unsigned quoter,
591   const char * func, int linenumber)
592 {
593 pooldesc * pp = pool_for_quoter(quoter);
594 void * yield;
595
596 DEBUG(D_memory)
597   debug_printf("allocating quoted-block for quoter %u (from %s %d)\n", quoter, func, linenumber);
598
599 if (!pp) pp = quoted_pool_new(quoter);
600 yield = pool_get(pp, size, FALSE, func, linenumber);
601
602 DEBUG(D_memory)
603   debug_printf("---QQ Get %6p %5d %-14s %4d\n",
604     pp->store_last_get, size, func, linenumber);
605
606 return yield;
607 }
608
609 /* Maybe get memory for the specified quoter, but only if the
610 prototype memory is tainted. Otherwise, get plain memory.
611 */
612 void *
613 store_get_quoted_3(int size, const void * proto_mem, unsigned quoter,
614   const char * func, int linenumber)
615 {
616 // debug_printf("store_get_quoted_3: quoter %u\n", quoter);
617 return is_tainted(proto_mem)
618   ? store_force_get_quoted(size, quoter, func, linenumber)
619   : store_get_3(size, proto_mem, func, linenumber);
620 }
621
622 /* Return quoter for given address, or -1 if not in a quoted-pool. */
623 int
624 quoter_for_address(const void * p)
625 {
626 for (quoted_pooldesc * qp = quoted_pools; qp; qp = qp->next)
627   {
628   pooldesc * pp = &qp->pool;
629   storeblock * b;
630
631   if (b = pp->current_block)
632     if (is_pointer_in_block(b, p))
633       return qp->quoter;
634
635   for (b = pp->chainbase; b; b = b->next)
636     if (is_pointer_in_block(b, p))
637       return qp->quoter;
638   }
639 return -1;
640 }
641
642 /* Return TRUE iff the given address is quoted for the given type.
643 There is extra complexity to handle lookup providers with multiple
644 find variants but shared quote functions. */
645 BOOL
646 is_quoted_like(const void * p, unsigned quoter)
647 {
648 int pq = quoter_for_address(p);
649 BOOL y =
650   is_real_quoter(pq) && lookup_list[pq]->quote == lookup_list[quoter]->quote;
651 /* debug_printf("is_quoted(%p, %u): %c\n", p, quoter, y?'T':'F'); */
652 return y;
653 }
654
655 /* Return TRUE if the quoter value indicates an actual quoter */
656 BOOL
657 is_real_quoter(int quoter)
658 {
659 return quoter >= 0;
660 }
661
662 /* Return TRUE if the "new" data requires that the "old" data
663 be recopied to new-class memory.  We order the classes as
664
665   2: tainted, not quoted
666   1: quoted (which is also tainted)
667   0: untainted
668
669 If the "new" is higher-order than the "old", they are not compatible
670 and a copy is needed.  If both are quoted, but the quoters differ,
671 not compatible.  Otherwise they are compatible.
672 */
673 BOOL
674 is_incompatible_fn(const void * old, const void * new)
675 {
676 int oq, nq;
677 unsigned oi, ni;
678
679 ni = is_real_quoter(nq = quoter_for_address(new)) ? 1 : is_tainted(new) ? 2 : 0;
680 oi = is_real_quoter(oq = quoter_for_address(old)) ? 1 : is_tainted(old) ? 2 : 0;
681 return ni > oi || ni == oi && nq != oq;
682 }
683
684 #endif  /*!COMPILE_UTILITY*/
685
686 /*************************************************
687 *      Extend a block if it is at the top        *
688 *************************************************/
689
690 /* While reading strings of unknown length, it is often the case that the
691 string is being read into the block at the top of the stack. If it needs to be
692 extended, it is more efficient just to extend within the top block rather than
693 allocate a new block and then have to copy the data. This function is provided
694 for the use of string_cat(), but of course can be used elsewhere too.
695 The block itself is not expanded; only the top allocation from it.
696
697 Arguments:
698   ptr        pointer to store block
699   oldsize    current size of the block, as requested by user
700   newsize    new size required
701   func       function from which called
702   linenumber line number in source file
703
704 Returns:     TRUE if the block is at the top of the stack and has been
705              extended; FALSE if it isn't at the top of the stack, or cannot
706              be extended
707
708 XXX needs extension for quoted-tracking.  This assumes that the global store_pool
709 is the one to alloc from, which breaks with separated pools.
710 */
711
712 BOOL
713 store_extend_3(void * ptr, int oldsize, int newsize,
714    const char * func, int linenumber)
715 {
716 pooldesc * pp = pool_for_pointer(ptr);
717 int inc = newsize - oldsize;
718 int rounded_oldsize = oldsize;
719
720 if (oldsize < 0 || newsize < oldsize || newsize >= INT_MAX/2)
721   log_write(0, LOG_MAIN|LOG_PANIC_DIE,
722             "bad memory extension requested (%d -> %d bytes) at %s %d",
723             oldsize, newsize, func, linenumber);
724
725 if (rounded_oldsize % alignment != 0)
726   rounded_oldsize += alignment - (rounded_oldsize % alignment);
727
728 if (CS ptr + rounded_oldsize != CS (pp->next_yield) ||
729     inc > pp->yield_length + rounded_oldsize - oldsize)
730   return FALSE;
731
732 /* Cut out the debugging stuff for utilities, but stop picky compilers from
733 giving warnings. */
734
735 #ifndef COMPILE_UTILITY
736 DEBUG(D_memory)
737   {
738   quoted_pooldesc * qp;
739   for (qp = quoted_pools; qp; qp = qp->next)
740     if (pp == &qp->pool)
741       {
742       debug_printf("---Q%d Ext %6p %5d %-14s %4d\n",
743         (int)(qp - quoted_pools),
744         ptr, newsize, func, linenumber);
745       break;
746       }
747   if (!qp)
748     debug_printf("---%d Ext %6p %5d %-14s %4d\n",
749       (int)(pp - paired_pools),
750       ptr, newsize, func, linenumber);
751   }
752 #endif  /* COMPILE_UTILITY */
753
754 if (newsize % alignment != 0) newsize += alignment - (newsize % alignment);
755 pp->next_yield = CS ptr + newsize;
756 pp->yield_length -= newsize - rounded_oldsize;
757 (void) VALGRIND_MAKE_MEM_UNDEFINED(ptr + oldsize, inc);
758 return TRUE;
759 }
760
761
762
763
764 static BOOL
765 is_pwr2_size(int len)
766 {
767 unsigned x = len;
768 return (x & (x - 1)) == 0;
769 }
770
771
772 /*************************************************
773 *    Back up to a previous point on the stack    *
774 *************************************************/
775
776 /* This function resets the next pointer, freeing any subsequent whole blocks
777 that are now unused. Call with a cookie obtained from store_mark() only; do
778 not call with a pointer returned by store_get().  Both the untainted and tainted
779 pools corresposding to store_pool are reset.
780
781 Quoted pools are not handled.
782
783 Arguments:
784   ptr         place to back up to
785   pool        pool holding the pointer
786   func        function from which called
787   linenumber  line number in source file
788
789 Returns:      nothing
790 */
791
792 static void
793 internal_store_reset(void * ptr, int pool, const char *func, int linenumber)
794 {
795 storeblock * bb;
796 pooldesc * pp = paired_pools + pool;
797 storeblock * b = pp->current_block;
798 char * bc = CS b + ALIGNED_SIZEOF_STOREBLOCK;
799 int newlength, count;
800 #ifndef COMPILE_UTILITY
801 int oldmalloc = pool_malloc;
802 #endif
803
804 if (!b) return; /* exim_dumpdb gets this, becuse it has never used tainted mem */
805
806 /* Last store operation was not a get */
807
808 pp->store_last_get = NULL;
809
810 /* See if the place is in the current block - as it often will be. Otherwise,
811 search for the block in which it lies. */
812
813 if (CS ptr < bc || CS ptr > bc + b->length)
814   {
815   for (b =  pp->chainbase; b; b = b->next)
816     {
817     bc = CS b + ALIGNED_SIZEOF_STOREBLOCK;
818     if (CS ptr >= bc && CS ptr <= bc + b->length) break;
819     }
820   if (!b)
821     log_write(0, LOG_MAIN|LOG_PANIC_DIE, "internal error: store_reset(%p) "
822       "failed: pool=%d %-14s %4d", ptr, pool, func, linenumber);
823   }
824
825 /* Back up, rounding to the alignment if necessary. When testing, flatten
826 the released memory. */
827
828 newlength = bc + b->length - CS ptr;
829 #ifndef COMPILE_UTILITY
830 if (debug_store)
831   {
832   assert_no_variables(ptr, newlength, func, linenumber);
833   if (f.running_in_test_harness)
834     {
835     (void) VALGRIND_MAKE_MEM_DEFINED(ptr, newlength);
836     memset(ptr, 0xF0, newlength);
837     }
838   }
839 #endif
840 (void) VALGRIND_MAKE_MEM_NOACCESS(ptr, newlength);
841 pp->next_yield = CS ptr + (newlength % alignment);
842 count = pp->yield_length;
843 count = (pp->yield_length = newlength - (newlength % alignment)) - count;
844 pp->current_block = b;
845
846 /* Free any subsequent block. Do NOT free the first
847 successor, if our current block has less than 256 bytes left. This should
848 prevent us from flapping memory. However, keep this block only when it has
849 a power-of-two size so probably is not a custom inflated one. */
850
851 if (  pp->yield_length < STOREPOOL_MIN_SIZE
852    && b->next
853    && is_pwr2_size(b->next->length + ALIGNED_SIZEOF_STOREBLOCK))
854   {
855   b = b->next;
856 #ifndef COMPILE_UTILITY
857   if (debug_store)
858     assert_no_variables(b, b->length + ALIGNED_SIZEOF_STOREBLOCK,
859                         func, linenumber);
860 #endif
861   (void) VALGRIND_MAKE_MEM_NOACCESS(CS b + ALIGNED_SIZEOF_STOREBLOCK,
862                 b->length - ALIGNED_SIZEOF_STOREBLOCK);
863   }
864
865 bb = b->next;
866 if (pool != POOL_CONFIG)
867   b->next = NULL;
868
869 while ((b = bb))
870   {
871   int siz = b->length + ALIGNED_SIZEOF_STOREBLOCK;
872
873 #ifndef COMPILE_UTILITY
874   if (debug_store)
875     assert_no_variables(b, b->length + ALIGNED_SIZEOF_STOREBLOCK,
876                         func, linenumber);
877 #endif
878   bb = bb->next;
879   pp->nbytes -= siz;
880   pool_malloc -= siz;
881   pp->nblocks--;
882   if (pool != POOL_CONFIG)
883     internal_store_free(b, func, linenumber);
884
885 #ifndef RESTRICTED_MEMORY
886   if (pp->store_block_order > 13) pp->store_block_order--;
887 #endif
888   }
889
890 /* Cut out the debugging stuff for utilities, but stop picky compilers from
891 giving warnings. */
892
893 #ifndef COMPILE_UTILITY
894 DEBUG(D_memory)
895   debug_printf("---%d Rst %6p %5d %-14s %4d\tpool %d\n", pool, ptr,
896     count + oldmalloc - pool_malloc,
897     func, linenumber, pool_malloc);
898 #endif  /* COMPILE_UTILITY */
899 }
900
901
902 /* Back up the pool pair, untainted and tainted, of the store_pool setting.
903 Quoted pools are not handled.
904 */
905
906 rmark
907 store_reset_3(rmark r, const char * func, int linenumber)
908 {
909 void ** ptr = r;
910
911 if (store_pool >= POOL_TAINT_BASE)
912   log_write(0, LOG_MAIN|LOG_PANIC_DIE,
913     "store_reset called for pool %d: %s %d\n", store_pool, func, linenumber);
914 if (!r)
915   log_write(0, LOG_MAIN|LOG_PANIC_DIE,
916     "store_reset called with bad mark: %s %d\n", func, linenumber);
917
918 internal_store_reset(*ptr, store_pool + POOL_TAINT_BASE, func, linenumber);
919 internal_store_reset(ptr,  store_pool,             func, linenumber);
920 return NULL;
921 }
922
923
924 /**************/
925
926 /* Free tail-end unused allocation.  This lets us allocate a big chunk
927 early, for cases when we only discover later how much was really needed.
928
929 Can be called with a value from store_get(), or an offset after such.  Only
930 the tainted or untainted pool that serviced the store_get() will be affected.
931
932 This is mostly a cut-down version of internal_store_reset().
933 XXX needs rationalising
934 */
935
936 void
937 store_release_above_3(void * ptr, const char * func, int linenumber)
938 {
939 pooldesc * pp;
940
941 /* Search all pools' "current" blocks.  If it isn't one of those,
942 ignore it (it usually will be). */
943
944 if ((pp = pool_current_for_pointer(ptr)))
945   {
946   storeblock * b = pp->current_block;
947   int count, newlength;
948
949   /* Last store operation was not a get */
950
951   pp->store_last_get = NULL;
952
953   /* Back up, rounding to the alignment if necessary. When testing, flatten
954   the released memory. */
955
956   newlength = (CS b + ALIGNED_SIZEOF_STOREBLOCK) + b->length - CS ptr;
957 #ifndef COMPILE_UTILITY
958   if (debug_store)
959     {
960     assert_no_variables(ptr, newlength, func, linenumber);
961     if (f.running_in_test_harness)
962       {
963       (void) VALGRIND_MAKE_MEM_DEFINED(ptr, newlength);
964       memset(ptr, 0xF0, newlength);
965       }
966     }
967 #endif
968   (void) VALGRIND_MAKE_MEM_NOACCESS(ptr, newlength);
969   pp->next_yield = CS ptr + (newlength % alignment);
970   count = pp->yield_length;
971   count = (pp->yield_length = newlength - (newlength % alignment)) - count;
972
973   /* Cut out the debugging stuff for utilities, but stop picky compilers from
974   giving warnings. */
975
976 #ifndef COMPILE_UTILITY
977   DEBUG(D_memory)
978     {
979     quoted_pooldesc * qp;
980     for (qp = quoted_pools; qp; qp = qp->next)
981       if (pp == &qp->pool)
982         debug_printf("---Q%d Rel %6p %5d %-14s %4d\tpool %d\n",
983           (int)(qp - quoted_pools),
984           ptr, count, func, linenumber, pool_malloc);
985     if (!qp)
986       debug_printf("---%d Rel %6p %5d %-14s %4d\tpool %d\n",
987         (int)(pp - paired_pools), ptr, count,
988         func, linenumber, pool_malloc);
989     }
990 #endif
991   return;
992   }
993 #ifndef COMPILE_UTILITY
994 DEBUG(D_memory)
995   debug_printf("non-last memory release try: %s %d\n", func, linenumber);
996 #endif
997 }
998
999
1000
1001 rmark
1002 store_mark_3(const char * func, int linenumber)
1003 {
1004 void ** p;
1005
1006 #ifndef COMPILE_UTILITY
1007 DEBUG(D_memory)
1008   debug_printf("---%d Mrk                    %-14s %4d\tpool %d\n",
1009     store_pool, func, linenumber, pool_malloc);
1010 #endif  /* COMPILE_UTILITY */
1011
1012 if (store_pool >= POOL_TAINT_BASE)
1013   log_write(0, LOG_MAIN|LOG_PANIC_DIE,
1014     "store_mark called for pool %d: %s %d\n", store_pool, func, linenumber);
1015
1016 /* Stash a mark for the tainted-twin release, in the untainted twin. Return
1017 a cookie (actually the address in the untainted pool) to the caller.
1018 Reset uses the cookie to recover the t-mark, winds back the tainted pool with it
1019 and winds back the untainted pool with the cookie. */
1020
1021 p = store_get_3(sizeof(void *), GET_UNTAINTED, func, linenumber);
1022 *p = store_get_3(0, GET_TAINTED, func, linenumber);
1023 return p;
1024 }
1025
1026
1027
1028
1029 /************************************************
1030 *             Release store                     *
1031 ************************************************/
1032
1033 /* This function checks that the pointer it is given is the first thing in a
1034 block, and if so, releases that block.
1035
1036 Arguments:
1037   block       block of store to consider
1038   pp          pool containing the block
1039   func        function from which called
1040   linenumber  line number in source file
1041
1042 Returns:      nothing
1043 */
1044
1045 static void
1046 store_release_3(void * block, pooldesc * pp, const char * func, int linenumber)
1047 {
1048 /* It will never be the first block, so no need to check that. */
1049
1050 for (storeblock * b =  pp->chainbase; b; b = b->next)
1051   {
1052   storeblock * bb = b->next;
1053   if (bb && CS block == CS bb + ALIGNED_SIZEOF_STOREBLOCK)
1054     {
1055     int siz = bb->length + ALIGNED_SIZEOF_STOREBLOCK;
1056     b->next = bb->next;
1057     pp->nbytes -= siz;
1058     pool_malloc -= siz;
1059     pp->nblocks--;
1060
1061     /* Cut out the debugging stuff for utilities, but stop picky compilers
1062     from giving warnings. */
1063
1064 #ifndef COMPILE_UTILITY
1065     DEBUG(D_memory)
1066       debug_printf("-Release %6p %-20s %4d %d\n", (void *)bb, func,
1067         linenumber, pool_malloc);
1068
1069     if (f.running_in_test_harness)
1070       memset(bb, 0xF0, bb->length+ALIGNED_SIZEOF_STOREBLOCK);
1071 #endif  /* COMPILE_UTILITY */
1072
1073     internal_store_free(bb, func, linenumber);
1074     return;
1075     }
1076   }
1077 }
1078
1079
1080 /************************************************
1081 *             Move store                        *
1082 ************************************************/
1083
1084 /* Allocate a new block big enough to expend to the given size and
1085 copy the current data into it.  Free the old one if possible.
1086
1087 This function is specifically provided for use when reading very
1088 long strings, e.g. header lines. When the string gets longer than a
1089 complete block, it gets copied to a new block. It is helpful to free
1090 the old block iff the previous copy of the string is at its start,
1091 and therefore the only thing in it. Otherwise, for very long strings,
1092 dead store can pile up somewhat disastrously. This function checks that
1093 the pointer it is given is the first thing in a block, and that nothing
1094 has been allocated since. If so, releases that block.
1095
1096 Arguments:
1097   oldblock
1098   newsize       requested size
1099   len           current size
1100
1101 Returns:        new location of data
1102 */
1103
1104 void *
1105 store_newblock_3(void * oldblock, int newsize, int len,
1106   const char * func, int linenumber)
1107 {
1108 pooldesc * pp = pool_for_pointer(oldblock);
1109 BOOL release_ok = !is_tainted(oldblock) && pp->store_last_get == oldblock;              /*XXX why tainted not handled? */
1110 uschar * newblock;
1111
1112 if (len < 0 || len > newsize)
1113   log_write(0, LOG_MAIN|LOG_PANIC_DIE,
1114             "bad memory extension requested (%d -> %d bytes) at %s %d",
1115             len, newsize, func, linenumber);
1116
1117 newblock = store_get(newsize, oldblock);
1118 memcpy(newblock, oldblock, len);
1119 if (release_ok) store_release_3(oldblock, pp, func, linenumber);
1120 return (void *)newblock;
1121 }
1122
1123
1124
1125
1126 /*************************************************
1127 *                Malloc store                    *
1128 *************************************************/
1129
1130 /* Running out of store is a total disaster for exim. Some malloc functions
1131 do not run happily on very small sizes, nor do they document this fact. This
1132 function is called via the macro store_malloc().
1133
1134 Arguments:
1135   size        amount of store wanted
1136   func        function from which called
1137   line        line number in source file
1138
1139 Returns:      pointer to gotten store (panic on failure)
1140 */
1141
1142 static void *
1143 internal_store_malloc(size_t size, const char *func, int line)
1144 {
1145 void * yield;
1146
1147 /* Check specifically for a possibly result of conversion from
1148 a negative int, to the (unsigned, wider) size_t */
1149
1150 if (size >= INT_MAX/2)
1151   log_write(0, LOG_MAIN|LOG_PANIC_DIE,
1152             "bad memory allocation requested (" SIZE_T_FMT " bytes) at %s %d",
1153             size, func, line);
1154
1155 size += sizeof(size_t); /* space to store the size, used under debug */
1156 if (size < 16) size = 16;
1157
1158 if (!(yield = malloc(size)))
1159   log_write(0, LOG_MAIN|LOG_PANIC_DIE, "failed to malloc " SIZE_T_FMT " bytes of memory: "
1160     "called from line %d in %s", size, line, func);
1161
1162 #ifndef COMPILE_UTILITY
1163 DEBUG(D_any) *(size_t *)yield = size;
1164 #endif
1165 yield = US yield + sizeof(size_t);
1166
1167 if ((nonpool_malloc += size) > max_nonpool_malloc)
1168   max_nonpool_malloc = nonpool_malloc;
1169
1170 /* Cut out the debugging stuff for utilities, but stop picky compilers from
1171 giving warnings. */
1172
1173 #ifndef COMPILE_UTILITY
1174 /* If running in test harness, spend time making sure all the new store
1175 is not filled with zeros so as to catch problems. */
1176
1177 if (f.running_in_test_harness)
1178   memset(yield, 0xF0, size - sizeof(size_t));
1179 DEBUG(D_memory) debug_printf("--Malloc %6p %5lu bytes\t%-20s %4d\tpool %5d  nonpool %5d\n",
1180   yield, size, func, line, pool_malloc, nonpool_malloc);
1181 #endif  /* COMPILE_UTILITY */
1182
1183 return yield;
1184 }
1185
1186 void *
1187 store_malloc_3(size_t size, const char *func, int linenumber)
1188 {
1189 if (n_nonpool_blocks++ > max_nonpool_blocks)
1190   max_nonpool_blocks = n_nonpool_blocks;
1191 return internal_store_malloc(size, func, linenumber);
1192 }
1193
1194
1195 /************************************************
1196 *             Free store                        *
1197 ************************************************/
1198
1199 /* This function is called by the macro store_free().
1200
1201 Arguments:
1202   block       block of store to free
1203   func        function from which called
1204   linenumber  line number in source file
1205
1206 Returns:      nothing
1207 */
1208
1209 static void
1210 internal_store_free(void * block, const char * func, int linenumber)
1211 {
1212 uschar * p = US block - sizeof(size_t);
1213 #ifndef COMPILE_UTILITY
1214 DEBUG(D_any) nonpool_malloc -= *(size_t *)p;
1215 DEBUG(D_memory) debug_printf("----Free %6p %5ld bytes\t%-20s %4d\n",
1216                     block, *(size_t *)p, func, linenumber);
1217 #endif
1218 free(p);
1219 }
1220
1221 void
1222 store_free_3(void * block, const char * func, int linenumber)
1223 {
1224 n_nonpool_blocks--;
1225 internal_store_free(block, func, linenumber);
1226 }
1227
1228 /******************************************************************************/
1229 /* Stats output on process exit */
1230 void
1231 store_exit(void)
1232 {
1233 #ifndef COMPILE_UTILITY
1234 DEBUG(D_memory)
1235  {
1236  int i;
1237  debug_printf("----Exit nonpool max: %3d kB in %d blocks\n",
1238   (max_nonpool_malloc+1023)/1024, max_nonpool_blocks);
1239  debug_printf("----Exit npools  max: %3d kB\n", max_pool_malloc/1024);
1240
1241  for (i = 0; i < N_PAIRED_POOLS; i++)
1242    {
1243    pooldesc * pp = paired_pools + i;
1244    debug_printf("----Exit  pool %2d max: %3d kB in %d blocks at order %u\t%s %s\n",
1245     i, (pp->maxbytes+1023)/1024, pp->maxblocks, pp->maxorder,
1246     poolclass[i], pooluse[i]);
1247    }
1248  i = 0;
1249  for (quoted_pooldesc * qp = quoted_pools; qp; i++, qp = qp->next)
1250    {
1251    pooldesc * pp = &qp->pool;
1252    debug_printf("----Exit  pool Q%d max: %3d kB in %d blocks at order %u\ttainted quoted:%s\n",
1253     i, (pp->maxbytes+1023)/1024, pp->maxblocks, pp->maxorder, lookup_list[qp->quoter]->name);
1254    }
1255  }
1256 #endif
1257 }
1258
1259
1260 /******************************************************************************/
1261 /* Per-message pool management */
1262
1263 static rmark   message_reset_point    = NULL;
1264
1265 void
1266 message_start(void)
1267 {
1268 int oldpool = store_pool;
1269 store_pool = POOL_MESSAGE;
1270 if (!message_reset_point) message_reset_point = store_mark();
1271 store_pool = oldpool;
1272 }
1273
1274 void
1275 message_tidyup(void)
1276 {
1277 int oldpool;
1278 if (!message_reset_point) return;
1279 oldpool = store_pool;
1280 store_pool = POOL_MESSAGE;
1281 message_reset_point = store_reset(message_reset_point);
1282 store_pool = oldpool;
1283 }
1284
1285 /******************************************************************************/
1286 /* Debug analysis of address */
1287
1288 #ifndef COMPILE_UTILITY
1289 void
1290 debug_print_taint(const void * p)
1291 {
1292 int q = quoter_for_address(p);
1293 if (!is_tainted(p)) return;
1294 debug_printf("(tainted");
1295 if (is_real_quoter(q)) debug_printf(", quoted:%s", lookup_list[q]->name);
1296 debug_printf(")\n");
1297 }
1298 #endif
1299
1300 /* End of store.c */