From: teodor Date: Thu, 10 Feb 2005 16:30:52 +0000 (+0000) Subject: add bulk memory operations and memtest X-Git-Url: http://www.sigaev.ru/git/gitweb.cgi?p=tedtools.git;a=commitdiff_plain;h=ba7e1d079124ac7e5685a0cf918229d1a9a26735 add bulk memory operations and memtest --- diff --git a/Makefile b/Makefile index c0c9404..df63daf 100644 --- a/Makefile +++ b/Makefile @@ -11,7 +11,7 @@ LIB=-g -L. -ltedtools -lm OBJS=tlog.o tmalloc.o tools.o prs_hmap.o sfxstr.o \ regis.o prs_inf.o shmem.o tcp.o udp.o connpool.o \ psort.o flatdb.o tbtree.o -PROGS=sfxtest hextest inftest kilter psortex flatdbtest tbtreetest gendata +PROGS=sfxtest hextest inftest kilter psortex flatdbtest tbtreetest gendata memtest .SUFFIXES: .o.c @@ -34,7 +34,7 @@ test: all @[ -d results ] || mkdir results @[ -d diffs ] || mkdir diffs @[ -d temp ] || mkdir temp - @for FILE in btree flatdb hex inf psort sfxmem ; do \ + @for FILE in btree flatdb hex inf mem psort sfxmem ; do \ echo -n $$FILE " ........ " ; \ if sh tests/$$FILE > results/$$FILE 2>results/$$FILE.errout && diff -c expected/$$FILE results/$$FILE > diffs/$$FILE ; then \ echo ok ; \ diff --git a/expected/mem b/expected/mem new file mode 100644 index 0000000..594df35 --- /dev/null +++ b/expected/mem @@ -0,0 +1,9 @@ +lc:abcdefghijklmnopqrstuvwxyz uc:ABCDEFGHIJKLMNOPQRSTUVWXYZ free:1048492 +lc:abcdefghijklmnopqrstuvwxyz free:1048532 +uc:ABCDEFGHIJKLMNOPQRSTUVWXYZ free:1048492 +mixed:ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz free:1048380 +mixed:ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz free:1048380 +mixed:ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz free:1048320 +mixed:ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz free:1048320 freenew:0 +mixed:ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz free:1048320 freechild:1048508 +Child: 0 diff --git a/memtest.c b/memtest.c new file mode 100644 index 0000000..83097e3 --- /dev/null +++ b/memtest.c @@ -0,0 +1,193 @@ +/* + * Copyright (c) 2004 Teodor Sigaev + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. 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. + * 3. Neither the name of the author nor the names of any co-contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY 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 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. + */ + +#include +#include +#include +#include + + +#include "tmalloc.h" +#include "tlog.h" +#include "tools.h" + +static void +usage() { + puts( + "Usage:\n" + "memtest [-c COUNT [-m]]\n" + ); + exit(1); +} + +extern char *optarg; +extern int opterr; + +int +main(int argn, char *argv[]) { + MemoryContext *base, *child; + int i; + int count=0, iscntx=0; + + opentlog(TL_OPEN_STDERR,TL_DEBUG, NULL); + opterr=0; + + while((i=getopt(argn,argv,"c:hm")) != EOF) { + switch(i) { + case 'c': + count=atoi(optarg); + break; + case 'm': + iscntx=1; + break; + case 'h': + default: + usage(); + break; + } + } + + if ( count == 0 ) { + char *ptr, *ptr1; + + /* test correctness */ + base = allocMemoryContext(NULL, MC_DEBUG); + child = allocMemoryContext(base, MC_DEBUG); + + ptr = mcalloc(base, 30); + for(i=0;i<26;i++) + ptr[i] = 97+i; + ptr[i]='\0'; + + ptr1 = mcstrdup(base, ptr); + strupper(ptr1); + printf("lc:%s uc:%s free:%d\n", ptr, ptr1, base->chunk->freesize); + + mcfree(ptr1); + printf("lc:%s free:%d\n", ptr, base->chunk->freesize); + + ptr1 = mcstrdup(base, ptr); + mcfree(ptr); + strupper(ptr1); + printf("uc:%s free:%d\n", ptr1, base->chunk->freesize); + + ptr= mcstrdup(base, ptr1); + strlower(ptr); + ptr1 =mcrealloc(ptr1, 60); + strcat(ptr1, ptr); + printf("mixed:%s free:%d\n", ptr1, base->chunk->freesize); + + ptr = mcrealloc(ptr1, 59); + tassert( ptr==ptr1 ); + printf("mixed:%s free:%d\n", ptr, base->chunk->freesize); + + ptr = mcrealloc(ptr1, 120); + tassert( ptr==ptr1 ); + printf("mixed:%s free:%d\n", ptr, base->chunk->freesize); + + ptr = mcalloc(base, CNTXCHUNK); + strcpy(ptr, ptr1); + printf("mixed:%s free:%d freenew:%d\n", ptr1, base->chunk->freesize, base->chunk->next->freesize); + + ptr= mcstrdup(child, ptr1); + printf("mixed:%s free:%d freechild:%d\n", ptr1, base->chunk->freesize, child->chunk->freesize); + + freeMemoryContext(child); + printf("Child: %d\n", (int)(base->child)); + + child = allocMemoryContext(base, MC_DEBUG); + freeMemoryContext(base); + } else { + struct timeval begin; + char *ptr, *ptr1; + + srandom(1); + if ( iscntx ) { + gettimeofday(&begin, NULL); + base = allocMemoryContext(NULL, MC_DEBUG); + for(i=0;ikeylen ) { if ( key->value ) memcpy( ptr->key.fixed.key, key->value, db->keylen ); - else - memset( ptr->key.fixed.key, 0, db->keylen ); } else { page->freespace -= PTRALIGN(key->length); ptr->key.varlen.length = key->length; @@ -600,13 +598,11 @@ packInternalKV(TBTree *db, TBTPage *page, TBTPointer *ptr, TBTValue *key, u_int3 ptr->pointer.internal.link = pagenumber; } - static void deleteKV(TBTree *db, TBTPage *page, TBTPointer **ptrs, u_int32_t num) { - static char buf[TBTREEPAGESIZE]; - char *bufptr = buf; TBTPointer *ptr = (TBTPointer*)page->data, *tmp, **ptrptr = ptrs; - u_int32_t i, start; + u_int32_t i; + /* suppose ptrs are ordered! */ tmp = ptr; while( ptrptr - ptrs < num && (char*)ptr - page->data < db->pointersize*page->npointer ) { @@ -632,25 +628,30 @@ deleteKV(TBTree *db, TBTPage *page, TBTPointer **ptrs, u_int32_t num) { page->npointer-=num; - tmp = (TBTPointer*)page->data; - start = page->npointer * db->pointersize + page->freespace; - for(i=0;inpointer;i++) { - if ( page->isleaf ) { - memcpy( bufptr, page->data + tmp->pointer.leaf.offset, tmp->pointer.leaf.length ); - tmp->pointer.leaf.offset = start + (bufptr-buf); - bufptr+=PTRALIGN(tmp->pointer.leaf.length); + if ( page->isleaf || db->keylen == 0 ) { + static char buf[TBTREEPAGESIZE]; + char *bufptr = buf; + u_int32_t start = page->npointer * db->pointersize + page->freespace; + + tmp = (TBTPointer*)page->data; + for(i=0;inpointer;i++) { + if ( page->isleaf ) { + memcpy( bufptr, page->data + tmp->pointer.leaf.offset, tmp->pointer.leaf.length ); + tmp->pointer.leaf.offset = start + (bufptr-buf); + bufptr+=PTRALIGN(tmp->pointer.leaf.length); + } + + if ( db->keylen == 0 ) { + if ( tmp->key.varlen.length ) + memcpy( bufptr, page->data + tmp->key.varlen.offset, tmp->key.varlen.length ); + tmp->key.varlen.offset = start + (bufptr-buf); + bufptr+=PTRALIGN(tmp->key.varlen.length); + } + tmp = (TBTPointer*)( (char*)tmp + db->pointersize ); } - if ( db->keylen == 0 ) { - if ( tmp->key.varlen.length ) - memcpy( bufptr, page->data + tmp->key.varlen.offset, tmp->key.varlen.length ); - tmp->key.varlen.offset = start + (bufptr-buf); - bufptr+=PTRALIGN(tmp->key.varlen.length); - } - tmp = (TBTPointer*)( (char*)tmp + db->pointersize ); + memcpy( page->data + start, buf, bufptr-buf ); } - - memcpy( page->data + start, buf, bufptr-buf ); } static u_int32_t diff --git a/tbtree.h b/tbtree.h index 9e75231..083d34c 100644 --- a/tbtree.h +++ b/tbtree.h @@ -38,12 +38,6 @@ #define offsetof(type, field) ((int) &((type *)0)->field) #endif /* offsetof */ -#define TYPEALIGN(ALIGNVAL,LEN) \ - (((long) (LEN) + (ALIGNVAL-1)) & ~((long) (ALIGNVAL-1))) - -#define PTRALIGN(LEN) TYPEALIGN(sizeof(void*), (LEN)) - -/*#define HASHSIZE(LEN) ( TYPEALIGN(2, (int)((LEN)*2)) + 1 )*/ #define HASHSIZE(LEN) ( (LEN)<<1 ) /* end utils */ @@ -157,6 +151,7 @@ typedef struct { } TBTIterator; int TBTInitIterator(TBTree *db, TBTIterator *iterator ); +int TBTInitPrefixIterator(TBTree *db, TBTIterator *iterator, TBTValue *key ); int TBTIterate(TBTree *db, TBTIterator *iterator, TBTValue *key, TBTValue *value ); void TBTFreeIterator(TBTree *db, TBTIterator *iterator); diff --git a/tests/mem b/tests/mem new file mode 100644 index 0000000..4dafb25 --- /dev/null +++ b/tests/mem @@ -0,0 +1 @@ +./memtest diff --git a/tmalloc.c b/tmalloc.c index 953e28f..d6c0b76 100644 --- a/tmalloc.c +++ b/tmalloc.c @@ -117,3 +117,160 @@ clrspace(char *buf) { return ptrc - buf; } + +MemoryContext * +allocMemoryContext(MemoryContext* parent, int flags) { + MemoryContext *res; + + res = (MemoryContext*)tmalloc( sizeof(MemoryContext) ); + res->flags = flags; + res->parent = parent; + if ( parent ) { + res->child = parent->child; + parent->child = res; + } else + res->child = NULL; + + res->chunk = (MemoryChunk*)tmalloc( MEMCHNKHDRSZ + CNTXCHUNK ); + res->chunk->size = res->chunk->freesize = CNTXCHUNK; + res->chunk->next = NULL; + + return res; +} + +void +freeMemoryContext(MemoryContext *cntx) { + MemoryContext *ptr=cntx; + MemoryChunk *chunk, *chunkptr; + + if ( cntx->parent ) + cntx->parent->child=NULL; + + while( ptr ) { + cntx=ptr->child; + + chunkptr=ptr->chunk; + while( chunkptr ) { + chunk=chunkptr->next; + tfree(chunkptr); + chunkptr=chunk; + } + + tfree(ptr); + ptr=cntx; + } +} + +void* +mcalloc(MemoryContext *cntx, size_t size) { + MemoryChunk *chunk = cntx->chunk; + MCAllocatedSpace *alloc; + + size = PTRALIGN(size) + MCASHDRSZ; + if ( cntx->flags & MC_DEBUG ) + size += sizeof(u_int32_t); + + if ( chunk->freesize < size ) { + MemoryChunk *newchunk; + + if ( size >= CNTXCHUNK ) { + newchunk = (MemoryChunk*)tmalloc(MEMCHNKHDRSZ + size); + newchunk->size = newchunk->freesize = size; + newchunk->next = chunk->next; + chunk->next = newchunk; + } else { + newchunk = (MemoryChunk*)tmalloc(MEMCHNKHDRSZ + CNTXCHUNK); + newchunk->size = newchunk->freesize = CNTXCHUNK; + newchunk->next = chunk; + cntx->chunk = newchunk; + } + + chunk = newchunk; + } + + chunk->freesize -= size; + alloc = (MCAllocatedSpace*)( chunk->data + chunk->freesize ); + alloc->size = size; + alloc->cntx = cntx; + + if ( cntx->flags & MC_DEBUG ) { + *(u_int32_t*)((char*)alloc + alloc->size - sizeof(u_int32_t) ) = MCMAGICKNUMBER; + memset( alloc->data, 0xc3, size - MCASHDRSZ - sizeof(u_int32_t) ); + } + + return (void*)(alloc->data); +} + +void * +mc0alloc(MemoryContext *cntx, size_t size) { + void *res = mcalloc(cntx, size); + memset( res, 0, size ); + return res; +} + +void * +mcrealloc(void * ptr, size_t size) { + MCAllocatedSpace *alloc = (MCAllocatedSpace*)( (char*)ptr - MCASHDRSZ ); + size_t realsize; + + if ( ptr==NULL ) + tlog(TL_CRIT|TL_EXIT, "mcrealloc: realloc null pointer"); + + if ( alloc->cntx->flags & MC_DEBUG ) { + tassert( *(u_int32_t*)( (char*)alloc + alloc->size - sizeof(u_int32_t) ) == MCMAGICKNUMBER ); + realsize = alloc->size - MCASHDRSZ - sizeof(u_int32_t); + } else + realsize = alloc->size - MCASHDRSZ; + + if ( size > realsize ) { + if ( (char*)alloc == alloc->cntx->chunk->data + alloc->cntx->chunk->freesize && + PTRALIGN(size)-realsize <= alloc->cntx->chunk->freesize ) { + /* just enlarge */ + alloc->cntx->chunk->freesize -= PTRALIGN(size)-realsize; + alloc->size+=PTRALIGN(size)-realsize; + if ( alloc->cntx->flags & MC_DEBUG ) { + memset( (char*)(alloc->data) + realsize, 0xc3, PTRALIGN(size)-realsize ); + *(u_int32_t*)((char*)alloc + alloc->size - sizeof(u_int32_t) ) = MCMAGICKNUMBER; + } + } else { + void *newptr = mcalloc(alloc->cntx, size); + memcpy( newptr, ptr, realsize ); + ptr = newptr; + if ( alloc->cntx->flags & MC_DEBUG ) + memset( (char*)ptr + realsize, 0xc3, PTRALIGN(size)-realsize ); + } + } + + return ptr; +} + + +void +mcfree(void * ptr) { + MCAllocatedSpace *alloc = (MCAllocatedSpace*)( (char*)ptr - MCASHDRSZ ); + + if ( ptr==NULL ) + tlog(TL_CRIT|TL_EXIT, "mcfree: free null pointer"); + + if ( alloc->cntx->flags & MC_DEBUG ) + tassert( *(u_int32_t*)((char*)alloc + alloc->size - sizeof(u_int32_t) ) == MCMAGICKNUMBER ); + + if ( (char*)alloc == alloc->cntx->chunk->data + alloc->cntx->chunk->freesize ) /* last allocated value */ + alloc->cntx->chunk->freesize+=alloc->size; + + alloc->cntx=NULL; +} + +char * +mcstrdup(MemoryContext *cntx, char * src) { + return mcnstrdup(cntx, src, strlen(src)); +} + +char * +mcnstrdup(MemoryContext *cntx, char *src, int len) { + char *dest=(char*)mcalloc(cntx, len+1); + memcpy(dest, src, len); + dest[len]='\0'; + return dest; +} + diff --git a/tmalloc.h b/tmalloc.h index 0c3a275..fce5dba 100644 --- a/tmalloc.h +++ b/tmalloc.h @@ -42,4 +42,51 @@ char * tnstrdup(char *src, int len); char * strlower(char * src); char * strupper(char * src); int clrspace(char *buf); + +/* fast allocate */ + +#define CNTXCHUNK (1024*1024) + +typedef struct MemoryChunk { + size_t size; + size_t freesize; + struct MemoryChunk *next; + char data[1]; +} MemoryChunk; + +#define MEMCHNKHDRSZ ( sizeof(u_int32_t)*2 + sizeof(MemoryChunk*) ) + +typedef struct MemoryContext { + u_int32_t flags; + struct MemoryContext *parent; + struct MemoryContext *child; + MemoryChunk *chunk; +} MemoryContext; + +#define MC_DEBUG 0x01 + +typedef struct { + size_t size; + MemoryContext *cntx; + char data[1]; +} MCAllocatedSpace; + +#define MCASHDRSZ ( sizeof(size_t) + sizeof(MemoryContext*) ) +#define MCMAGICKNUMBER (0xFE0FBEEF) + +#define TYPEALIGN(ALIGNVAL,LEN) \ + (((long) (LEN) + (ALIGNVAL-1)) & ~((long) (ALIGNVAL-1))) + +#define PTRALIGN(LEN) TYPEALIGN(sizeof(void*), (LEN)) + +MemoryContext *allocMemoryContext(MemoryContext* parent, int flags); +void freeMemoryContext(MemoryContext* cntx); +void* mcalloc(MemoryContext *cntx, size_t size); +void* mc0alloc(MemoryContext *cntx, size_t size); +void* mcrealloc(void * ptr, size_t size); +void mcfree(void * ptr); +char * mcstrdup(MemoryContext *cntx, char * src); +char * mcnstrdup(MemoryContext *cntx, char *src, int len); + + #endif