From 63bef95aac0ff411b315d34fb316ceed9328b13e Mon Sep 17 00:00:00 2001 From: Wouter Wijngaards Date: Thu, 18 Oct 2007 15:40:31 +0000 Subject: [PATCH] regional. git-svn-id: file:///svn/unbound/trunk@696 be551aaa-1e26-0410-a405-d3ace91eadb9 --- doc/Changelog | 1 + doc/unbound.doxygen | 3 +- testdata/01-doc.tpkg | Bin 855 -> 866 bytes util/regional.c | 213 +++++++++++++++++++++++++++++++++++++++++++ util/regional.h | 148 ++++++++++++++++++++++++++++++ 5 files changed, 364 insertions(+), 1 deletion(-) create mode 100644 util/regional.c create mode 100644 util/regional.h diff --git a/doc/Changelog b/doc/Changelog index 7ac4f4561..c13265b74 100644 --- a/doc/Changelog +++ b/doc/Changelog @@ -10,6 +10,7 @@ make download_ldns refreshes the tarball with ldns svn trunk. - ldns-src.tar.gz is used if no ldns is found on the system, and statically linked into unbound. + - start of regional allocator code. 17 October 2007: Wouter - fixup another cycle detect and ns-addr timeout resolution bug. diff --git a/doc/unbound.doxygen b/doc/unbound.doxygen index 04abbce53..d9b87e85e 100644 --- a/doc/unbound.doxygen +++ b/doc/unbound.doxygen @@ -495,7 +495,8 @@ EXCLUDE = ./build \ util/configparser.c \ util/configparser.h \ util/configlexer.c \ - util/locks.h + util/locks.h \ + ./ldns-src # The EXCLUDE_SYMLINKS tag can be used select whether or not files or # directories that are symbolic links (a Unix filesystem feature) are excluded diff --git a/testdata/01-doc.tpkg b/testdata/01-doc.tpkg index 0e4ea228aa452cac5022b7bcc3a595411279d03d..b4a7f11ee739c27153bccf69407bf0348bf751a5 100644 GIT binary patch literal 866 zc-jGC1D*UIiwFRab{9tg1MQY=Z`(Eyfc;hc6$d%UUI4w>u?5ITfXqoztY{Go#qwbo z5JsXU&Jrn*R1*LD9VIuhvvxs)WZf`6NG$4jFC>pAGERa*=3&8AG%FZzLWxc2R|D(hY`QJ7T)8>U^AoE9g z-^u@EdXzroKTdE=N69Q5LHx4A_&opf{EuNA1hA8O2!b&ggO;7j8JLPeLp9DEZg81a zyk>A)F#+6sr){rdaLM(H&6+>870E2)4B=-Vjd z^cq99RBJBEZK!>Ny(oKKgk1b`e(c-Op-G5EQ9SreuY6b=3*(eENwPwT{gI~zIO^M@`YkyY_hkQR~ zI{{HZ2!Wst2K+IsFmkK7FgS&(=D1W}*3EZxx5{I?5p0IBCLot$#mlfFt6|zV{iHrg zedtYarMP`Apt%`ZgM8npGrW!l%a$t5)N`$CcK3Ya%|(A`JmcO3=h0b3(#^0a+@ievfzu6HU|FdL{ z_rzqH&gSm?|0nnftMmg_X|}xskYAb7SWX!vVNA}L&J}M>FIZMAU+)(kSt`~y&Zt2b zm#l!FsQ{QlGRyEUPGEWd5hj>#@}A-ug8xiqP^b_t!)17i5B`TJDOH6gOLS67waI`i z@k4|aEKEk0O>xFrCJK%6ht^wGw;8!m41c6Xy^na}XS+8Ua@yU!u^$@LzQ79vD>Cwi s^18D&-+J904u`|xa5x+ehr{7;I2;a#!{Kl^9FEuEPf+!)DgY<|0NQJ@y8r+H literal 855 zc-jG11E~BTiwFQnXaYt61MODpYuhjo&sXcOIGoZwAb#Wt4lQ(P$Jp2?W2_&>psKCd zT5QQka@+j(JK0&6bT3v~#y0(EBl&bs-JPT;9%M2NGOohjLm@)UW|MB5j(5fldT}(3 zqVaSbN26X84~LU!4<--h(H0tQr~>F+$;L4CW4>Rl|D}k&=6^FaOq+YQftcRP`&Ryk z!)bhz|7eEvcpOiLJ&5ktjql?>&wn5Kg8^)%9tMLx>4TPyN*S1fK}9u24wtx1OI|X# zDwqIn9%;L(82JE$B?Lhjn0l25$QEoQKEnR~7e(J$M=OoSl^b$vekm1j0qq=#oL->G znrh8OzA?2cuw!LsiICH`CkMVY9r)z+(W{e#imn*pON@c11?2V<4#SLHhN3A;7#{A& za~qa`mc3<|W7y-@M%z>)Sc~FpL7xrZv)EBA`tqATE zx8oeD%Wl@ucZC|m%dnHIsnSf{Rk~!?cNbo-6|=$rzI-XumA*^N+DJunh6?1WsYiCt zf3D(I2CABx+xu^6;V)gmZYylRo!ioBY3FmSZQ@}WcMARU3#!`uE4>JJN3 zm7zTmFl3x=m2THU#Pbs9V__1nt5%Ptg}iBs1l2)7H3(^&si~MS)Nm=VSG`S@dsxPq z6pXNIZeS0I-+za&@eF(W z4fb}jc>|F5OlfSw1mYkf$4sY+*QO;b3YM;RTa_#nYbVFlpo%k=!AmLtMi5UD{EK2( zoVceXA@?ahAXt`==aiR?mHE^A?%?3y;Nalk h;Nalk;Nalk;Nalk;Nalk;Nb8O_zaO~RnGt@008mkvoiny diff --git a/util/regional.c b/util/regional.c new file mode 100644 index 000000000..d22f149e1 --- /dev/null +++ b/util/regional.c @@ -0,0 +1,213 @@ +/* + * regional.c -- region based memory allocator. + * + * Copyright (c) 2001-2006, NLnet Labs. All rights reserved. + * + * Copyright (c) 2007, NLnet Labs. All rights reserved. + * + * This software is open source. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * Neither the name of the NLNET LABS nor the names of its contributors may + * be used to endorse or promote products derived from this software without + * specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +/** + * \file + * Region allocator. Allocates small portions of of larger chunks. + */ + +#include "config.h" +#include "util/log.h" +#include "util/regional.h" + +#ifdef ALIGNMENT +# undef ALIGNMENT +#endif +/** increase size until it fits alignment of s bytes */ +#define ALIGN_UP(x, s) (((x) + s - 1) & (~(s - 1))) +/** what size to align on; make sure a char* fits in it. */ +#define ALIGNMENT (sizeof(uint64_t)) + +/** Default reasonable size for chunks */ +#define REGIONAL_CHUNK_SIZE 8192 +/** Default size for large objects - allocated outside of chunks. */ +#define REGIONAL_LARGE_OBJECT_SIZE 2048 + +struct regional* +regional_create() +{ + void *block = malloc(REGIONAL_CHUNK_SIZE); + if(!block) return NULL; + return regional_create_custom(block, REGIONAL_CHUNK_SIZE); +} + +/** init regional struct with first block */ +static void +regional_init(struct regional* r) +{ + r->next = NULL; + r->size = r->first_size; + r->allocated = ALIGN_UP(sizeof(struct regional), ALIGNMENT); + r->data = (char*)r; + r->total_large = 0; + r->large_list = NULL; +} + +struct regional* +regional_create_custom(void* block, size_t size) +{ + struct regional* r = (struct regional*)block; + log_assert(sizeof(struct regional) <= size); + r->first_size = size; + regional_init(r); + return r; +} + +void +regional_free_all(struct regional *r) +{ + char* p = r->next, *np; + while(p) { + np = *(char**)p; + free(p); + p = np; + } + p = r->large_list; + while(p) { + np = *(char**)p; + free(p); + p = np; + } + regional_init(r); +} + +void +regional_destroy(struct regional *r) +{ + regional_free_all(r); + free(r); +} + +void * +regional_alloc(struct regional *r, size_t size) +{ + size_t a = ALIGN_UP(size, ALIGNMENT); + void *s; + /* large objects */ + if(a > REGIONAL_LARGE_OBJECT_SIZE) { + s = malloc(ALIGNMENT + size); + if(!s) return NULL; + r->total_large += ALIGNMENT+size; + *(char**)s = r->large_list; + r->large_list = (char*)s; + return s+ALIGNMENT; + } + /* create a new chunk */ + if(r->allocated + a > r->size) { + s = malloc(REGIONAL_CHUNK_SIZE); + if(!s) return NULL; + *(char**)s = r->data; + r->data = s; + r->allocated = ALIGNMENT; + r->size = REGIONAL_CHUNK_SIZE; + } + /* put in this chunk */ + s = r->data + r->allocated; + r->allocated += a; + return s; +} + +void * +regional_alloc_init(struct regional* r, const void *init, size_t size) +{ + void *s = regional_alloc(r, size); + if(!s) + return NULL; + memcpy(s, init, size); + return s; +} + +void * +regional_alloc_zero(struct regional *r, size_t size) +{ + void *s = regional_alloc(r, size); + if(!s) + return NULL; + memset(s, 0, size); + return s; +} + +char * +regional_strdup(struct regional *r, const char *string) +{ + return regional_alloc_init(r, string, strlen(string)+1); +} + +/** + * reasonably slow, but stats and get_mem are not supposed to be fast + * count the number of chunks in use + */ +static size_t +count_chunks(struct regional* r) +{ + size_t c = 1; + char* p = r->next; + while(p) { + c++; + p = *(char**)p; + } + return c; +} + +/** + * also reasonably slow, counts the number of large objects + */ +static size_t +count_large(struct regional* r) +{ + size_t c = 0; + char* p = r->large_list; + while(p) { + c++; + p = *(char**)p; + } + return c; +} + +void +regional_log_stats(struct regional *r) +{ + log_info("regional %u chunks, %u large", + (unsigned)count_chunks(r), (unsigned)count_large(r)); +} + +size_t +regional_get_mem(struct regional* r) +{ + return r->first_size + (count_chunks(r)-1)*REGIONAL_CHUNK_SIZE + + r->total_large; +} diff --git a/util/regional.h b/util/regional.h new file mode 100644 index 000000000..7c2975f73 --- /dev/null +++ b/util/regional.h @@ -0,0 +1,148 @@ +/* + * regional.h -- region based memory allocator. + * + * Copyright (c) 2007, NLnet Labs. All rights reserved. + * + * This software is open source. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * Neither the name of the NLNET LABS nor the names of its contributors may + * be used to endorse or promote products derived from this software without + * specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +/** + * \file + * Region allocator. Allocates small portions of of larger chunks. + * + * Different from (nsd) region-allocator.h + * o does not have recycle bin + * o does not collect stats + * o does not keep cleanup list + * o does not have function pointers to setup + * o allocs the regional struct inside the first block. + * o can take a block to create regional from. + */ + +#ifndef UTIL_REGIONAL_H_ +#define UTIL_REGIONAL_H_ + +/** + * the regional* is the first block*. + * every block has a ptr to the next in first bytes. + * and so does the regional struct, which is the first block. + */ +struct regional +{ + /** next chunk. NULL if first chunk is the only chunk. */ + char* next; + /** number of bytes allocated in the current chunk. */ + size_t allocated; + /** initial chunk size */ + size_t first_size; + /** current chunk size */ + size_t size; + /** total large size */ + size_t total_large; + /** + * current chunk + * can be cast to char** to obtain next chunk pointer. + */ + char *data; + /** first large object, cast to char** to obtain next ptr */ + char* large_list; +}; + +/** + * Create a new regional. + */ +struct regional* regional_create(); + +/** + * Create a new region, with custom settings. + * @param block: initial data block + * The regional returned is allocated in the block (start of it). + * @param size: length of block. + */ +struct regional* regional_create_custom(void* block, size_t size); + +/** + * Free all memory associated with REGION. Only keeps the first block with + * the regional inside it. + * @param r: the region. + */ +void regional_free_all(struct regional *r); + +/** + * Destroy regional. All memory associated with regional is freed as if + * regional_free_all was called, as well as destroying the regional struct. + * @param r: to delete. + */ +void regional_destroy(struct regional *r); + +/** + * Allocate SIZE bytes of memory inside REGION. The memory is + * deallocated when region_free_all is called for this region. + * @param r: the region. + * @param size: number of bytes. + * @return: pointer to memory allocated. + */ +void *regional_alloc(struct regional *r, size_t size); + +/** + * Allocate SIZE bytes of memory inside REGION and copy INIT into it. + * The memory is deallocated when region_free_all is called for this + * region. + * @param r: the region. + * @param init: to copy. + * @param size: number of bytes. + * @return: pointer to memory allocated. + */ +void *regional_alloc_init(struct regional* r, const void *init, size_t size); + +/** + * Allocate SIZE bytes of memory inside REGION that are initialized to + * 0. The memory is deallocated when region_free_all is called for + * this region. + * @param r: the region. + * @param size: number of bytes. + * @return: pointer to memory allocated. + */ +void *regional_alloc_zero(struct regional *r, size_t size); + +/** + * Duplicate STRING and allocate the result in REGION. + * @param r: the region. + * @param string: null terminated string. + */ +char *regional_strdup(struct regional *r, const char *string); + +/** Debug print REGION statistics to LOG */ +void regional_log_stats(struct regional *r); + +/** get total memory size in use by region */ +size_t regional_get_mem(struct regional* r); + +#endif /* UTIL_REGIONAL_H_ */ -- 2.47.2