2 * util/alloc.c - memory allocation service.
4 * Copyright (c) 2007, NLnet Labs. All rights reserved.
6 * This software is open source.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
12 * Redistributions of source code must retain the above copyright notice,
13 * this list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 * this list of conditions and the following disclaimer in the documentation
17 * and/or other materials provided with the distribution.
19 * Neither the name of the NLNET LABS nor the names of its contributors may
20 * be used to endorse or promote products derived from this software without
21 * specific prior written permission.
23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
26 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
27 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
29 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
30 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
31 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
33 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
39 * This file contains memory allocation functions.
43 #include "util/alloc.h"
44 #include "util/regional.h"
45 #include "util/data/packed_rrset.h"
46 #include "util/fptr_wlist.h"
48 /** custom size of cached regional blocks */
49 #define ALLOC_REG_SIZE 16384
50 /** number of bits for ID part of uint64, rest for number of threads. */
51 #define THRNUM_SHIFT 48 /* for 65k threads, 2^48 rrsets per thr. */
53 /** setup new special type */
55 alloc_setup_special(alloc_special_type* t)
57 memset(t, 0, sizeof(*t));
58 lock_rw_init(&t->entry.lock);
62 /** prealloc some entries in the cache. To minimize contention.
63 * Result is 1 lock per alloc_max newly created entries.
64 * @param alloc: the structure to fill up.
67 prealloc_setup(struct alloc_cache* alloc)
69 alloc_special_type* p;
71 for(i=0; i<ALLOC_SPECIAL_MAX; i++) {
72 if(!(p = (alloc_special_type*)malloc(
73 sizeof(alloc_special_type)))) {
74 log_err("prealloc: out of memory");
77 alloc_setup_special(p);
78 alloc_set_special_next(p, alloc->quar);
84 /** prealloc region blocks */
86 prealloc_blocks(struct alloc_cache* alloc, size_t num)
90 for(i=0; i<num; i++) {
91 r = regional_create_custom(ALLOC_REG_SIZE);
93 log_err("prealloc blocks: out of memory");
96 r->next = (char*)alloc->reg_list;
98 alloc->num_reg_blocks ++;
103 alloc_init(struct alloc_cache* alloc, struct alloc_cache* super,
106 memset(alloc, 0, sizeof(*alloc));
107 alloc->super = super;
108 alloc->thread_num = thread_num;
109 alloc->next_id = (uint64_t)thread_num; /* in steps, so that type */
110 alloc->next_id <<= THRNUM_SHIFT; /* of *_id is used. */
111 alloc->last_id = 1; /* so no 64bit constants, */
112 alloc->last_id <<= THRNUM_SHIFT; /* or implicit 'int' ops. */
113 alloc->last_id -= 1; /* for compiler portability. */
114 alloc->last_id |= alloc->next_id;
115 alloc->next_id += 1; /* because id=0 is special. */
116 alloc->max_reg_blocks = 100;
117 alloc->num_reg_blocks = 0;
118 alloc->reg_list = NULL;
119 alloc->cleanup = NULL;
120 alloc->cleanup_arg = NULL;
122 prealloc_blocks(alloc, alloc->max_reg_blocks);
124 lock_quick_init(&alloc->lock);
125 lock_protect(&alloc->lock, alloc, sizeof(*alloc));
129 /** free the special list */
131 alloc_clear_special_list(struct alloc_cache* alloc)
133 alloc_special_type* p, *np;
137 np = alloc_special_next(p);
138 /* deinit special type */
139 lock_rw_destroy(&p->entry.lock);
146 alloc_clear_special(struct alloc_cache* alloc)
149 lock_quick_lock(&alloc->lock);
151 alloc_clear_special_list(alloc);
155 lock_quick_unlock(&alloc->lock);
160 alloc_clear(struct alloc_cache* alloc)
162 alloc_special_type* p;
163 struct regional* r, *nr;
167 lock_quick_destroy(&alloc->lock);
169 if(alloc->super && alloc->quar) {
170 /* push entire list into super */
172 while(alloc_special_next(p)) /* find last */
173 p = alloc_special_next(p);
174 lock_quick_lock(&alloc->super->lock);
175 alloc_set_special_next(p, alloc->super->quar);
176 alloc->super->quar = alloc->quar;
177 alloc->super->num_quar += alloc->num_quar;
178 lock_quick_unlock(&alloc->super->lock);
180 alloc_clear_special_list(alloc);
186 nr = (struct regional*)r->next;
190 alloc->reg_list = NULL;
191 alloc->num_reg_blocks = 0;
195 alloc_get_id(struct alloc_cache* alloc)
197 uint64_t id = alloc->next_id++;
198 if(id == alloc->last_id) {
199 log_warn("rrset alloc: out of 64bit ids. Clearing cache.");
200 fptr_ok(fptr_whitelist_alloc_cleanup(alloc->cleanup));
201 (*alloc->cleanup)(alloc->cleanup_arg);
203 /* start back at first number */ /* like in alloc_init*/
204 alloc->next_id = (uint64_t)alloc->thread_num;
205 alloc->next_id <<= THRNUM_SHIFT; /* in steps for comp. */
206 alloc->next_id += 1; /* portability. */
207 /* and generate new and safe id */
208 id = alloc->next_id++;
214 alloc_special_obtain(struct alloc_cache* alloc)
216 alloc_special_type* p;
218 /* see if in local cache */
221 alloc->quar = alloc_special_next(p);
223 p->id = alloc_get_id(alloc);
226 /* see if in global cache */
228 /* could maybe grab alloc_max/2 entries in one go,
229 * but really, isn't that just as fast as this code? */
230 lock_quick_lock(&alloc->super->lock);
231 if((p = alloc->super->quar)) {
232 alloc->super->quar = alloc_special_next(p);
233 alloc->super->num_quar--;
235 lock_quick_unlock(&alloc->super->lock);
237 p->id = alloc_get_id(alloc);
242 prealloc_setup(alloc);
243 if(!(p = (alloc_special_type*)malloc(sizeof(alloc_special_type)))) {
244 log_err("alloc_special_obtain: out of memory");
247 alloc_setup_special(p);
248 p->id = alloc_get_id(alloc);
252 /** push mem and some more items to the super */
254 pushintosuper(struct alloc_cache* alloc, alloc_special_type* mem)
257 alloc_special_type *p = alloc->quar;
259 log_assert(alloc && alloc->super &&
260 alloc->num_quar >= ALLOC_SPECIAL_MAX);
261 /* push ALLOC_SPECIAL_MAX/2 after mem */
262 alloc_set_special_next(mem, alloc->quar);
263 for(i=1; i<ALLOC_SPECIAL_MAX/2; i++) {
264 p = alloc_special_next(p);
266 alloc->quar = alloc_special_next(p);
267 alloc->num_quar -= ALLOC_SPECIAL_MAX/2;
269 /* dump mem+list into the super quar list */
270 lock_quick_lock(&alloc->super->lock);
271 alloc_set_special_next(p, alloc->super->quar);
272 alloc->super->quar = mem;
273 alloc->super->num_quar += ALLOC_SPECIAL_MAX/2 + 1;
274 lock_quick_unlock(&alloc->super->lock);
275 /* so 1 lock per mem+alloc/2 deletes */
279 alloc_special_release(struct alloc_cache* alloc, alloc_special_type* mem)
285 lock_quick_lock(&alloc->lock); /* superalloc needs locking */
288 alloc_special_clean(mem);
289 if(alloc->super && alloc->num_quar >= ALLOC_SPECIAL_MAX) {
290 /* push it to the super structure */
291 pushintosuper(alloc, mem);
295 alloc_set_special_next(mem, alloc->quar);
299 lock_quick_unlock(&alloc->lock);
304 alloc_stats(struct alloc_cache* alloc)
306 log_info("%salloc: %d in cache, %d blocks.", alloc->super?"":"sup",
307 (int)alloc->num_quar, (int)alloc->num_reg_blocks);
310 size_t alloc_get_mem(struct alloc_cache* alloc)
312 alloc_special_type* p;
313 size_t s = sizeof(*alloc);
315 lock_quick_lock(&alloc->lock); /* superalloc needs locking */
317 s += sizeof(alloc_special_type) * alloc->num_quar;
318 for(p = alloc->quar; p; p = alloc_special_next(p)) {
319 s += lock_get_mem(&p->entry.lock);
321 s += alloc->num_reg_blocks * ALLOC_REG_SIZE;
323 lock_quick_unlock(&alloc->lock);
329 alloc_reg_obtain(struct alloc_cache* alloc)
331 if(alloc->num_reg_blocks > 0) {
332 struct regional* r = alloc->reg_list;
333 alloc->reg_list = (struct regional*)r->next;
335 alloc->num_reg_blocks--;
338 return regional_create_custom(ALLOC_REG_SIZE);
342 alloc_reg_release(struct alloc_cache* alloc, struct regional* r)
344 if(alloc->num_reg_blocks >= alloc->max_reg_blocks) {
349 regional_free_all(r);
350 log_assert(r->next == NULL);
351 r->next = (char*)alloc->reg_list;
353 alloc->num_reg_blocks++;
357 alloc_set_id_cleanup(struct alloc_cache* alloc, void (*cleanup)(void*),
360 alloc->cleanup = cleanup;
361 alloc->cleanup_arg = arg;
364 /** global debug value to keep track of total memory mallocs */
365 size_t unbound_mem_alloc = 0;
366 /** global debug value to keep track of total memory frees */
367 size_t unbound_mem_freed = 0;
368 #ifdef UNBOUND_ALLOC_STATS
369 /** special value to know if the memory is being tracked */
370 uint64_t mem_special = (uint64_t)0xfeed43327766abcdLL;
374 /** malloc with stats */
375 void *unbound_stat_malloc(size_t size)
378 if(size == 0) size = 1;
379 res = malloc(size+16);
380 if(!res) return NULL;
381 unbound_mem_alloc += size;
382 log_info("stat %p=malloc(%u)", res+16, (unsigned)size);
383 memcpy(res, &size, sizeof(size));
384 memcpy(res+8, &mem_special, sizeof(mem_special));
391 #define INT_MAX (((int)-1)>>1)
393 /** calloc with stats */
394 void *unbound_stat_calloc(size_t nmemb, size_t size)
398 if(nmemb != 0 && INT_MAX/nmemb < size)
399 return NULL; /* integer overflow check */
400 s = (nmemb*size==0)?(size_t)1:nmemb*size;
401 res = calloc(1, s+16);
402 if(!res) return NULL;
403 log_info("stat %p=calloc(%u, %u)", res+16, (unsigned)nmemb, (unsigned)size);
404 unbound_mem_alloc += s;
405 memcpy(res, &s, sizeof(s));
406 memcpy(res+8, &mem_special, sizeof(mem_special));
412 /** free with stats */
413 void unbound_stat_free(void *ptr)
417 if(memcmp(ptr-8, &mem_special, sizeof(mem_special)) != 0) {
422 memcpy(&s, ptr, sizeof(s));
423 log_info("stat free(%p) size %u", ptr+16, (unsigned)s);
425 unbound_mem_freed += s;
431 /** realloc with stats */
432 void *unbound_stat_realloc(void *ptr, size_t size)
436 if(!ptr) return unbound_stat_malloc(size);
437 if(memcmp(ptr-8, &mem_special, sizeof(mem_special)) != 0) {
438 return realloc(ptr, size);
441 unbound_stat_free(ptr);
445 memcpy(&cursz, ptr, sizeof(cursz));
447 /* nothing changes */
450 res = malloc(size+16);
451 if(!res) return NULL;
452 unbound_mem_alloc += size;
453 unbound_mem_freed += cursz;
454 log_info("stat realloc(%p, %u) from %u", ptr+16, (unsigned)size, (unsigned)cursz);
456 memcpy(res+16, ptr+16, size);
457 } else if(size > cursz) {
458 memcpy(res+16, ptr+16, cursz);
462 memcpy(res, &size, sizeof(size));
463 memcpy(res+8, &mem_special, sizeof(mem_special));
467 /** log to file where alloc was done */
468 void *unbound_stat_malloc_log(size_t size, const char* file, int line,
471 log_info("%s:%d %s malloc(%u)", file, line, func, (unsigned)size);
472 return unbound_stat_malloc(size);
475 /** log to file where alloc was done */
476 void *unbound_stat_calloc_log(size_t nmemb, size_t size, const char* file,
477 int line, const char* func)
479 log_info("%s:%d %s calloc(%u, %u)", file, line, func,
480 (unsigned) nmemb, (unsigned)size);
481 return unbound_stat_calloc(nmemb, size);
484 /** log to file where free was done */
485 void unbound_stat_free_log(void *ptr, const char* file, int line,
488 if(ptr && memcmp(ptr-8, &mem_special, sizeof(mem_special)) == 0) {
490 memcpy(&s, ptr-16, sizeof(s));
491 log_info("%s:%d %s free(%p) size %u",
492 file, line, func, ptr, (unsigned)s);
494 log_info("%s:%d %s unmatched free(%p)", file, line, func, ptr);
495 unbound_stat_free(ptr);
498 /** log to file where alloc was done */
499 void *unbound_stat_realloc_log(void *ptr, size_t size, const char* file,
500 int line, const char* func)
502 log_info("%s:%d %s realloc(%p, %u)", file, line, func,
503 ptr, (unsigned)size);
504 return unbound_stat_realloc(ptr, size);
507 #endif /* UNBOUND_ALLOC_STATS */
508 #ifdef UNBOUND_ALLOC_LITE
513 /** length of prefix and suffix */
514 static size_t lite_pad = 16;
515 /** prefix value to check */
516 static char* lite_pre = "checkfront123456";
517 /** suffix value to check */
518 static char* lite_post= "checkafter123456";
520 void *unbound_stat_malloc_lite(size_t size, const char* file, int line,
523 /* [prefix .. len .. actual data .. suffix] */
524 void* res = malloc(size+lite_pad*2+sizeof(size_t));
525 if(!res) return NULL;
526 memmove(res, lite_pre, lite_pad);
527 memmove(res+lite_pad, &size, sizeof(size_t));
528 memset(res+lite_pad+sizeof(size_t), 0x1a, size); /* init the memory */
529 memmove(res+lite_pad+size+sizeof(size_t), lite_post, lite_pad);
530 return res+lite_pad+sizeof(size_t);
533 void *unbound_stat_calloc_lite(size_t nmemb, size_t size, const char* file,
534 int line, const char* func)
538 if(nmemb != 0 && INT_MAX/nmemb < size)
539 return NULL; /* integer overflow check */
541 res = malloc(req+lite_pad*2+sizeof(size_t));
542 if(!res) return NULL;
543 memmove(res, lite_pre, lite_pad);
544 memmove(res+lite_pad, &req, sizeof(size_t));
545 memset(res+lite_pad+sizeof(size_t), 0, req);
546 memmove(res+lite_pad+req+sizeof(size_t), lite_post, lite_pad);
547 return res+lite_pad+sizeof(size_t);
550 void unbound_stat_free_lite(void *ptr, const char* file, int line,
556 real = ptr-lite_pad-sizeof(size_t);
557 if(memcmp(real, lite_pre, lite_pad) != 0) {
558 log_err("free(): prefix failed %s:%d %s", file, line, func);
559 log_hex("prefix here", real, lite_pad);
560 log_hex(" should be", lite_pre, lite_pad);
561 fatal_exit("alloc assertion failed");
563 memmove(&orig, real+lite_pad, sizeof(size_t));
564 if(memcmp(real+lite_pad+orig+sizeof(size_t), lite_post, lite_pad)!=0){
565 log_err("free(): suffix failed %s:%d %s", file, line, func);
566 log_err("alloc size is %d", (int)orig);
567 log_hex("suffix here", real+lite_pad+orig+sizeof(size_t),
569 log_hex(" should be", lite_post, lite_pad);
570 fatal_exit("alloc assertion failed");
572 memset(real, 0xdd, orig+lite_pad*2+sizeof(size_t)); /* mark it */
576 void *unbound_stat_realloc_lite(void *ptr, size_t size, const char* file,
577 int line, const char* func)
579 /* always free and realloc (no growing) */
584 return unbound_stat_malloc_lite(size, file, line, func);
588 unbound_stat_free_lite(ptr, file, line, func);
591 /* change allocation size and copy */
592 real = ptr-lite_pad-sizeof(size_t);
593 if(memcmp(real, lite_pre, lite_pad) != 0) {
594 log_err("realloc(): prefix failed %s:%d %s", file, line, func);
595 log_hex("prefix here", real, lite_pad);
596 log_hex(" should be", lite_pre, lite_pad);
597 fatal_exit("alloc assertion failed");
599 memmove(&orig, real+lite_pad, sizeof(size_t));
600 if(memcmp(real+lite_pad+orig+sizeof(size_t), lite_post, lite_pad)!=0){
601 log_err("realloc(): suffix failed %s:%d %s", file, line, func);
602 log_err("alloc size is %d", (int)orig);
603 log_hex("suffix here", real+lite_pad+orig+sizeof(size_t),
605 log_hex(" should be", lite_post, lite_pad);
606 fatal_exit("alloc assertion failed");
608 /* new alloc and copy over */
609 newa = unbound_stat_malloc_lite(size, file, line, func);
613 memmove(newa, ptr, orig);
614 else memmove(newa, ptr, size);
615 memset(real, 0xdd, orig+lite_pad*2+sizeof(size_t)); /* mark it */
620 char* unbound_strdup_lite(const char* s, const char* file, int line,
623 /* this routine is made to make sure strdup() uses the malloc_lite */
624 size_t l = strlen(s)+1;
625 char* n = (char*)unbound_stat_malloc_lite(l, file, line, func);
631 char* unbound_lite_wrapstr(char* s)
633 char* n = unbound_strdup_lite(s, __FILE__, __LINE__, __func__);
638 #undef sldns_pkt2wire
639 sldns_status unbound_lite_pkt2wire(uint8_t **dest, const sldns_pkt *p,
644 sldns_status s = sldns_pkt2wire(&md, p, &ms);
646 *dest = unbound_stat_malloc_lite(ms, __FILE__, __LINE__,
649 if(!*dest) { free(md); return LDNS_STATUS_MEM_ERR; }
650 memcpy(*dest, md, ms);
660 int unbound_lite_i2d_DSA_SIG(DSA_SIG* dsasig, unsigned char** sig)
662 unsigned char* n = NULL;
663 int r= i2d_DSA_SIG(dsasig, &n);
665 *sig = unbound_stat_malloc_lite((size_t)r, __FILE__, __LINE__,
668 memcpy(*sig, n, (size_t)r);
676 #endif /* UNBOUND_ALLOC_LITE */