1238106Sdes/* 2238106Sdes * regional.c -- region based memory allocator. 3238106Sdes * 4238106Sdes * Copyright (c) 2001-2006, NLnet Labs. All rights reserved. 5238106Sdes * 6238106Sdes * Copyright (c) 2007, NLnet Labs. All rights reserved. 7238106Sdes * 8238106Sdes * This software is open source. 9238106Sdes * 10238106Sdes * Redistribution and use in source and binary forms, with or without 11238106Sdes * modification, are permitted provided that the following conditions 12238106Sdes * are met: 13238106Sdes * 14238106Sdes * Redistributions of source code must retain the above copyright notice, 15238106Sdes * this list of conditions and the following disclaimer. 16238106Sdes * 17238106Sdes * Redistributions in binary form must reproduce the above copyright notice, 18238106Sdes * this list of conditions and the following disclaimer in the documentation 19238106Sdes * and/or other materials provided with the distribution. 20238106Sdes * 21238106Sdes * Neither the name of the NLNET LABS nor the names of its contributors may 22238106Sdes * be used to endorse or promote products derived from this software without 23238106Sdes * specific prior written permission. 24238106Sdes * 25238106Sdes * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 26269257Sdes * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 27269257Sdes * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 28269257Sdes * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 29269257Sdes * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 30269257Sdes * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 31269257Sdes * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 32269257Sdes * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 33269257Sdes * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 34269257Sdes * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 35269257Sdes * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 36238106Sdes */ 37238106Sdes 38238106Sdes/** 39238106Sdes * \file 40238106Sdes * Regional allocator. Allocates small portions of of larger chunks. 41238106Sdes */ 42238106Sdes 43238106Sdes#include "config.h" 44238106Sdes#include "util/log.h" 45238106Sdes#include "util/regional.h" 46238106Sdes 47238106Sdes#ifdef ALIGNMENT 48238106Sdes# undef ALIGNMENT 49238106Sdes#endif 50238106Sdes/** increase size until it fits alignment of s bytes */ 51238106Sdes#define ALIGN_UP(x, s) (((x) + s - 1) & (~(s - 1))) 52238106Sdes/** what size to align on; make sure a char* fits in it. */ 53238106Sdes#define ALIGNMENT (sizeof(uint64_t)) 54238106Sdes 55238106Sdes/** Default reasonable size for chunks */ 56238106Sdes#define REGIONAL_CHUNK_SIZE 8192 57238106Sdes#ifdef UNBOUND_ALLOC_NONREGIONAL 58238106Sdes/** All objects allocated outside of chunks, for debug */ 59238106Sdes#define REGIONAL_LARGE_OBJECT_SIZE 0 60238106Sdes#else 61238106Sdes/** Default size for large objects - allocated outside of chunks. */ 62238106Sdes#define REGIONAL_LARGE_OBJECT_SIZE 2048 63238106Sdes#endif 64238106Sdes 65238106Sdesstruct regional* 66238106Sdesregional_create(void) 67238106Sdes{ 68238106Sdes return regional_create_custom(REGIONAL_CHUNK_SIZE); 69238106Sdes} 70238106Sdes 71238106Sdes/** init regional struct with first block */ 72238106Sdesstatic void 73238106Sdesregional_init(struct regional* r) 74238106Sdes{ 75238106Sdes size_t a = ALIGN_UP(sizeof(struct regional), ALIGNMENT); 76238106Sdes r->data = (char*)r + a; 77238106Sdes r->available = r->first_size - a; 78238106Sdes r->next = NULL; 79238106Sdes r->large_list = NULL; 80238106Sdes r->total_large = 0; 81238106Sdes} 82238106Sdes 83238106Sdesstruct regional* 84238106Sdesregional_create_custom(size_t size) 85238106Sdes{ 86238106Sdes struct regional* r = (struct regional*)malloc(size); 87238106Sdes log_assert(sizeof(struct regional) <= size); 88238106Sdes if(!r) return NULL; 89238106Sdes r->first_size = size; 90238106Sdes regional_init(r); 91238106Sdes return r; 92238106Sdes} 93238106Sdes 94238106Sdesvoid 95238106Sdesregional_free_all(struct regional *r) 96238106Sdes{ 97238106Sdes char* p = r->next, *np; 98238106Sdes while(p) { 99238106Sdes np = *(char**)p; 100238106Sdes free(p); 101238106Sdes p = np; 102238106Sdes } 103238106Sdes p = r->large_list; 104238106Sdes while(p) { 105238106Sdes np = *(char**)p; 106238106Sdes free(p); 107238106Sdes p = np; 108238106Sdes } 109238106Sdes regional_init(r); 110238106Sdes} 111238106Sdes 112238106Sdesvoid 113238106Sdesregional_destroy(struct regional *r) 114238106Sdes{ 115238106Sdes if(!r) return; 116238106Sdes regional_free_all(r); 117238106Sdes free(r); 118238106Sdes} 119238106Sdes 120238106Sdesvoid * 121238106Sdesregional_alloc(struct regional *r, size_t size) 122238106Sdes{ 123238106Sdes size_t a = ALIGN_UP(size, ALIGNMENT); 124238106Sdes void *s; 125238106Sdes /* large objects */ 126238106Sdes if(a > REGIONAL_LARGE_OBJECT_SIZE) { 127238106Sdes s = malloc(ALIGNMENT + size); 128238106Sdes if(!s) return NULL; 129238106Sdes r->total_large += ALIGNMENT+size; 130238106Sdes *(char**)s = r->large_list; 131238106Sdes r->large_list = (char*)s; 132238106Sdes return (char*)s+ALIGNMENT; 133238106Sdes } 134238106Sdes /* create a new chunk */ 135238106Sdes if(a > r->available) { 136238106Sdes s = malloc(REGIONAL_CHUNK_SIZE); 137238106Sdes if(!s) return NULL; 138238106Sdes *(char**)s = r->next; 139238106Sdes r->next = (char*)s; 140238106Sdes r->data = (char*)s + ALIGNMENT; 141238106Sdes r->available = REGIONAL_CHUNK_SIZE - ALIGNMENT; 142238106Sdes } 143238106Sdes /* put in this chunk */ 144238106Sdes r->available -= a; 145238106Sdes s = r->data; 146238106Sdes r->data += a; 147238106Sdes return s; 148238106Sdes} 149238106Sdes 150238106Sdesvoid * 151238106Sdesregional_alloc_init(struct regional* r, const void *init, size_t size) 152238106Sdes{ 153238106Sdes void *s = regional_alloc(r, size); 154238106Sdes if(!s) return NULL; 155238106Sdes memcpy(s, init, size); 156238106Sdes return s; 157238106Sdes} 158238106Sdes 159238106Sdesvoid * 160238106Sdesregional_alloc_zero(struct regional *r, size_t size) 161238106Sdes{ 162238106Sdes void *s = regional_alloc(r, size); 163238106Sdes if(!s) return NULL; 164238106Sdes memset(s, 0, size); 165238106Sdes return s; 166238106Sdes} 167238106Sdes 168238106Sdeschar * 169238106Sdesregional_strdup(struct regional *r, const char *string) 170238106Sdes{ 171238106Sdes return (char*)regional_alloc_init(r, string, strlen(string)+1); 172238106Sdes} 173238106Sdes 174238106Sdes/** 175238106Sdes * reasonably slow, but stats and get_mem are not supposed to be fast 176238106Sdes * count the number of chunks in use 177238106Sdes */ 178238106Sdesstatic size_t 179238106Sdescount_chunks(struct regional* r) 180238106Sdes{ 181238106Sdes size_t c = 1; 182238106Sdes char* p = r->next; 183238106Sdes while(p) { 184238106Sdes c++; 185238106Sdes p = *(char**)p; 186238106Sdes } 187238106Sdes return c; 188238106Sdes} 189238106Sdes 190238106Sdes/** 191238106Sdes * also reasonably slow, counts the number of large objects 192238106Sdes */ 193238106Sdesstatic size_t 194238106Sdescount_large(struct regional* r) 195238106Sdes{ 196238106Sdes size_t c = 0; 197238106Sdes char* p = r->large_list; 198238106Sdes while(p) { 199238106Sdes c++; 200238106Sdes p = *(char**)p; 201238106Sdes } 202238106Sdes return c; 203238106Sdes} 204238106Sdes 205238106Sdesvoid 206238106Sdesregional_log_stats(struct regional *r) 207238106Sdes{ 208238106Sdes /* some basic assertions put here (non time critical code) */ 209238106Sdes log_assert(ALIGNMENT >= sizeof(char*)); 210238106Sdes log_assert(REGIONAL_CHUNK_SIZE > ALIGNMENT); 211238106Sdes log_assert(REGIONAL_CHUNK_SIZE-ALIGNMENT > REGIONAL_LARGE_OBJECT_SIZE); 212238106Sdes log_assert(REGIONAL_CHUNK_SIZE >= sizeof(struct regional)); 213238106Sdes /* debug print */ 214238106Sdes log_info("regional %u chunks, %u large", 215238106Sdes (unsigned)count_chunks(r), (unsigned)count_large(r)); 216238106Sdes} 217238106Sdes 218238106Sdessize_t 219238106Sdesregional_get_mem(struct regional* r) 220238106Sdes{ 221238106Sdes return r->first_size + (count_chunks(r)-1)*REGIONAL_CHUNK_SIZE 222238106Sdes + r->total_large; 223238106Sdes} 224