util/regional.c

   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 /**
  84  * Create a new region, with custom first block and large-object sizes.
  85  * @param size: length of first block.
  86  * @param large_object_size: outside of chunk allocation threshold.
  87  * @return: newly allocated regional.
  88  */
  89 static struct regional*
  90 regional_create_custom_large_object(size_t size, size_t large_object_size)
  91 {
  92         struct regional* r;
  93         size = ALIGN_UP(size, ALIGNMENT);
  94         r = (struct regional*)malloc(size);
  95         log_assert(sizeof(struct regional) <= size);
  96         if(!r) return NULL;
  97         r->first_size = size;
  98         r->large_object_size = large_object_size;
  99         regional_init(r);
 100         return r;
 101 }
 102
 103 struct regional*
 104 regional_create_custom(size_t size)
 105 {
 106         return regional_create_custom_large_object(size,
 107                 REGIONAL_LARGE_OBJECT_SIZE);
 108 }
 109
 110 struct regional*
 111 regional_create_nochunk(size_t size)
 112 {
 113         return regional_create_custom_large_object(size, 0);
 114 }
 115
 116 void
 117 regional_free_all(struct regional *r)
 118 {
 119         char* p = r->next, *np;
 120         while(p) {
 121                 np = *(char**)p;
 122                 free(p);
 123                 p = np;
 124         }
 125         p = r->large_list;
 126         while(p) {
 127                 np = *(char**)p;
 128                 free(p);
 129                 p = np;
 130         }
 131         regional_init(r);
 132 }
 133
 134 void
 135 regional_destroy(struct regional *r)
 136 {
 137         if(!r) return;
 138         regional_free_all(r);
 139         free(r);
 140 }
 141
 142 void *
 143 regional_alloc(struct regional *r, size_t size)
 144 {
 145         size_t a;
 146         void *s;
 147         if(
 148 #if SIZEOF_SIZE_T == 8
 149                 (unsigned long long)size >= 0xffffffffffffff00ULL
 150 #else
 151                 (unsigned)size >= (unsigned)0xffffff00UL
 152 #endif
 153                 )
 154                 return NULL; /* protect against integer overflow in
 155                         malloc and ALIGN_UP */
 156         a = ALIGN_UP(size, ALIGNMENT);
 157         /* large objects */
 158         if(a > r->large_object_size) {
 159                 s = malloc(ALIGNMENT + size);
 160                 if(!s) return NULL;
 161                 r->total_large += ALIGNMENT+size;
 162                 *(char**)s = r->large_list;
 163                 r->large_list = (char*)s;
 164                 return (char*)s+ALIGNMENT;
 165         }
 166         /* create a new chunk */
 167         if(a > r->available) {
 168                 s = malloc(REGIONAL_CHUNK_SIZE);
 169                 if(!s) return NULL;
 170                 *(char**)s = r->next;
 171                 r->next = (char*)s;
 172                 r->data = (char*)s + ALIGNMENT;
 173                 r->available = REGIONAL_CHUNK_SIZE - ALIGNMENT;
 174         }
 175         /* put in this chunk */
 176         r->available -= a;
 177         s = r->data;
 178         r->data += a;
 179         return s;
 180 }
 181
 182 void *
 183 regional_alloc_init(struct regional* r, const void *init, size_t size)
 184 {
 185         void *s = regional_alloc(r, size);
 186         if(!s) return NULL;
 187         memcpy(s, init, size);
 188         return s;
 189 }
 190
 191 void *
 192 regional_alloc_zero(struct regional *r, size_t size)
 193 {
 194         void *s = regional_alloc(r, size);
 195         if(!s) return NULL;
 196         memset(s, 0, size);
 197         return s;
 198 }
 199
 200 char *
 201 regional_strdup(struct regional *r, const char *string)
 202 {
 203         return (char*)regional_alloc_init(r, string, strlen(string)+1);
 204 }
 205
 206 /**
 207  * reasonably slow, but stats and get_mem are not supposed to be fast
 208  * count the number of chunks in use
 209  */
 210 static size_t
 211 count_chunks(struct regional* r)
 212 {
 213         size_t c = 1;
 214         char* p = r->next;
 215         while(p) {
 216                 c++;
 217                 p = *(char**)p;
 218         }
 219         return c;
 220 }
 221
 222 /**
 223  * also reasonably slow, counts the number of large objects
 224  */
 225 static size_t
 226 count_large(struct regional* r)
 227 {
 228         size_t c = 0;
 229         char* p = r->large_list;
 230         while(p) {
 231                 c++;
 232                 p = *(char**)p;
 233         }
 234         return c;
 235 }
 236
 237 void
 238 regional_log_stats(struct regional *r)
 239 {
 240         /* some basic assertions put here (non time critical code) */
 241         log_assert(ALIGNMENT >= sizeof(char*));
 242         log_assert(REGIONAL_CHUNK_SIZE > ALIGNMENT);
 243         log_assert(REGIONAL_CHUNK_SIZE-ALIGNMENT > r->large_object_size);
 244         log_assert(REGIONAL_CHUNK_SIZE >= sizeof(struct regional));
 245         /* debug print */
 246         log_info("regional %u chunks, %u large",
 247                 (unsigned)count_chunks(r), (unsigned)count_large(r));
 248 }
 249
 250 size_t
 251 regional_get_mem(struct regional* r)
 252 {
 253         return r->first_size + (count_chunks(r)-1)*REGIONAL_CHUNK_SIZE
 254                 + r->total_large;
 255 }