1 /* 2 * regional.c -- region based memory allocator. 3 * 4 * Copyright (c) 2001-2006, NLnet Labs. All rights reserved. 5 * 6 * Copyright (c) 2007, NLnet Labs. All rights reserved. 7 * 8 * This software is open source. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 14 * Redistributions of source code must retain the above copyright notice, 15 * this list of conditions and the following disclaimer. 16 * 17 * Redistributions in binary form must reproduce the above copyright notice, 18 * this list of conditions and the following disclaimer in the documentation 19 * and/or other materials provided with the distribution. 20 * 21 * Neither the name of the NLNET LABS nor the names of its contributors may 22 * be used to endorse or promote products derived from this software without 23 * specific prior written permission. 24 * 25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 26 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 27 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 28 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 29 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 30 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 31 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 32 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 33 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 34 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 35 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 36 */ 37 38 /** 39 * \file 40 * Regional allocator. Allocates small portions of of larger chunks. 41 */ 42 43 #include "config.h" 44 #include "util/log.h" 45 #include "util/regional.h" 46 47 #ifdef ALIGNMENT 48 # undef ALIGNMENT 49 #endif 50 /** increase size until it fits alignment of s bytes */ 51 #define ALIGN_UP(x, s) (((x) + s - 1) & (~(s - 1))) 52 /** what size to align on; make sure a char* fits in it. */ 53 #define ALIGNMENT (sizeof(uint64_t)) 54 55 /** Default reasonable size for chunks */ 56 #define REGIONAL_CHUNK_SIZE 8192 57 #ifdef UNBOUND_ALLOC_NONREGIONAL 58 /** All objects allocated outside of chunks, for debug */ 59 #define REGIONAL_LARGE_OBJECT_SIZE 0 60 #else 61 /** Default size for large objects - allocated outside of chunks. */ 62 #define REGIONAL_LARGE_OBJECT_SIZE 2048 63 #endif 64 65 struct regional* 66 regional_create(void) 67 { 68 return regional_create_custom(REGIONAL_CHUNK_SIZE); 69 } 70 71 /** init regional struct with first block */ 72 static void 73 regional_init(struct regional* r) 74 { 75 size_t a = ALIGN_UP(sizeof(struct regional), ALIGNMENT); 76 r->data = (char*)r + a; 77 r->available = r->first_size - a; 78 r->next = NULL; 79 r->large_list = NULL; 80 r->total_large = 0; 81 } 82 83 struct regional* 84 regional_create_custom(size_t size) 85 { 86 struct regional* r = (struct regional*)malloc(size); 87 size = ALIGN_UP(size, ALIGNMENT); 88 log_assert(sizeof(struct regional) <= size); 89 if(!r) return NULL; 90 r->first_size = size; 91 regional_init(r); 92 return r; 93 } 94 95 void 96 regional_free_all(struct regional *r) 97 { 98 char* p = r->next, *np; 99 while(p) { 100 np = *(char**)p; 101 free(p); 102 p = np; 103 } 104 p = r->large_list; 105 while(p) { 106 np = *(char**)p; 107 free(p); 108 p = np; 109 } 110 regional_init(r); 111 } 112 113 void 114 regional_destroy(struct regional *r) 115 { 116 if(!r) return; 117 regional_free_all(r); 118 free(r); 119 } 120 121 void * 122 regional_alloc(struct regional *r, size_t size) 123 { 124 size_t a; 125 void *s; 126 if( 127 #if SIZEOF_SIZE_T == 8 128 (unsigned long long)size >= 0xffffffffffffff00ULL 129 #else 130 (unsigned)size >= (unsigned)0xffffff00UL 131 #endif 132 ) 133 return NULL; /* protect against integer overflow in 134 malloc and ALIGN_UP */ 135 a = ALIGN_UP(size, ALIGNMENT); 136 /* large objects */ 137 if(a > REGIONAL_LARGE_OBJECT_SIZE) { 138 s = malloc(ALIGNMENT + size); 139 if(!s) return NULL; 140 r->total_large += ALIGNMENT+size; 141 *(char**)s = r->large_list; 142 r->large_list = (char*)s; 143 return (char*)s+ALIGNMENT; 144 } 145 /* create a new chunk */ 146 if(a > r->available) { 147 s = malloc(REGIONAL_CHUNK_SIZE); 148 if(!s) return NULL; 149 *(char**)s = r->next; 150 r->next = (char*)s; 151 r->data = (char*)s + ALIGNMENT; 152 r->available = REGIONAL_CHUNK_SIZE - ALIGNMENT; 153 } 154 /* put in this chunk */ 155 r->available -= a; 156 s = r->data; 157 r->data += a; 158 return s; 159 } 160 161 void * 162 regional_alloc_init(struct regional* r, const void *init, size_t size) 163 { 164 void *s = regional_alloc(r, size); 165 if(!s) return NULL; 166 memcpy(s, init, size); 167 return s; 168 } 169 170 void * 171 regional_alloc_zero(struct regional *r, size_t size) 172 { 173 void *s = regional_alloc(r, size); 174 if(!s) return NULL; 175 memset(s, 0, size); 176 return s; 177 } 178 179 char * 180 regional_strdup(struct regional *r, const char *string) 181 { 182 return (char*)regional_alloc_init(r, string, strlen(string)+1); 183 } 184 185 /** 186 * reasonably slow, but stats and get_mem are not supposed to be fast 187 * count the number of chunks in use 188 */ 189 static size_t 190 count_chunks(struct regional* r) 191 { 192 size_t c = 1; 193 char* p = r->next; 194 while(p) { 195 c++; 196 p = *(char**)p; 197 } 198 return c; 199 } 200 201 /** 202 * also reasonably slow, counts the number of large objects 203 */ 204 static size_t 205 count_large(struct regional* r) 206 { 207 size_t c = 0; 208 char* p = r->large_list; 209 while(p) { 210 c++; 211 p = *(char**)p; 212 } 213 return c; 214 } 215 216 void 217 regional_log_stats(struct regional *r) 218 { 219 /* some basic assertions put here (non time critical code) */ 220 log_assert(ALIGNMENT >= sizeof(char*)); 221 log_assert(REGIONAL_CHUNK_SIZE > ALIGNMENT); 222 log_assert(REGIONAL_CHUNK_SIZE-ALIGNMENT > REGIONAL_LARGE_OBJECT_SIZE); 223 log_assert(REGIONAL_CHUNK_SIZE >= sizeof(struct regional)); 224 /* debug print */ 225 log_info("regional %u chunks, %u large", 226 (unsigned)count_chunks(r), (unsigned)count_large(r)); 227 } 228 229 size_t 230 regional_get_mem(struct regional* r) 231 { 232 return r->first_size + (count_chunks(r)-1)*REGIONAL_CHUNK_SIZE 233 + r->total_large; 234 } 235