yusuk****@cheru*****
yusuk****@cheru*****
2005年 1月 5日 (水) 23:41:42 JST
田畑です。 新部さんの下記のメールが引っかかってましたので、再送します 内容についてはposix_memalignの移植性を調べてから返事します。 From: NIIBE Yutaka <gniib****@fsij*****> Subject: alloc.c changes which once tried in 2002 Date: Tue, 04 Jan 2005 19:23:14 +0900 > 3 年くらい前に一度やろうとしてみたのですけれどもそのままになっていたも > のです。今回, 改めてもう一度。 > > anthy の memory allocation は, ページを単位としてもらった領域を分割し > て利用するようになっています。 > > あらましは, > > * オブジェクトに対してアロケータを登録する。デストラクタが登録できる。 > * アロケータでオブジェクトを得る。 > * オブジェクトを個々に解放してよい。 > * アロケータごと全部解放するというオマケ付き。 > この時, ちゃんと個々のオブジェクトに対してデストラクタが呼ばれる。 > > という感じです。ページ毎にフリーリストが管理され, (将来的には)メモリを > ページ単位で解放することができるかもしれないようになっています。 > > > 今回の変更は, もうすこし管理のオーバヘッドを減らすというものです。これ > まで struct chunk には, ptr というメンバがあってそれは所属するページを > 指すようになっていました。posix_memalign を使って, アラインメントを取っ > てもらうようにするとこの ptr というメンバをなくすことができます。 > > test/ の下の例だと, > 49:(おおきなおせわさま) > の変換で 25 ページほど allocate されます(変更前は 27 ページ)。 > > ポータビリティなくなるからやんないほうがよいかしらん。posix_memalign > がない環境では, malloc を使うというようにするのが良いでしょうか。 > > とりあえず, 今, あるのを送ります。 > > あとで, 小さく区切って, 変更を送るようにします。 > > --- orig/configure.ac > +++ mod/configure.ac > @@ -3,6 +3,7 @@ > > AM_INIT_AUTOMAKE(anthy, 6024) > AM_CONFIG_HEADER(config.h) > +AC_GNU_SOURCE > > dnl Checks for programs. > AC_PROG_CC > --- orig/include/alloc.h > +++ mod/include/alloc.h > @@ -15,7 +15,7 @@ > * dtorの引数は解放されるオブジェクト > * 返り値: 作成したallocator > */ > -allocator anthy_create_allocator(int s, void (*dtor)(void *)); > +allocator anthy_create_allocator(unsigned int s, void (*dtor)(void *)); > > /* > * allocatorを解放する > > > --- orig/src-diclib/alloc.c > +++ mod/src-diclib/alloc.c > @@ -5,113 +5,108 @@ > * $Id: alloc.c,v 1.12 2002/05/15 11:21:10 yusuke Exp $ > * > * Copyright (C) 2000-2002 TABATA Yusuke, UGAWA Tomoharu > - * Copyright (C) 2002 NIIBE Yutaka > + * Copyright (C) 2002, 2005 NIIBE Yutaka > * > * dtor: destructor > * > * ページ中のフリーなchunkは単方向リストに継がれている > - * 使用中のchunkは属するページを指している > */ > > +#include <config.h> > #include <stdlib.h> > > #include <alloc.h> > #include <logger.h> > > -/*#define MEM_DEBUG*/ > -/**/ > -#define PAGE_MAGIC 0x12345678 > - > static int nr_pages; > > - > -#define PAGE_SIZE 4096 > -#ifdef MEM_DEBUG > -#define CHUNK_HEADER_SIZE (sizeof(void *) * 2) > -#else > -#define CHUNK_HEADER_SIZE (sizeof(void *)) > -#endif > -#define PAGE_HEADER_SIZE (sizeof(void *)*3+sizeof(int)) > +#define PAGE_SIZE 4096 > +#define PAGE_HEADER_SIZE (sizeof(void *)*2) > +#define PAGE_CONTENT_SIZE (PAGE_SIZE - PAGE_HEADER_SIZE) > +#define NUM_CHUNKS(a) (int)(PAGE_CONTENT_SIZE/a->size) > +#define MINIMUM_SIZE (sizeof(void *)*2) > +#define GLOBAL_FREE_LIST 1 > > struct chunk { > - void *ptr; > -#ifdef MEM_DEBUG > - void *ator; > + union { > + struct { > + struct chunk *next_in_page; > +#if defined(GLOBAL_FREE_LIST) > + struct chunk *free_list; > #endif > - void *storage[1]; > + } l; > + unsigned char storage[1]; > + } u; > }; > > /* > - * pageのstorage中には > - * max_obj = (PAGE_SIZE - PAGE_HEADER_SIZE)/ (size + CHUNK_HEADER_SIZE)個の > - * スロットがある。そのうちuse_count個のスロットがfree_listにつながっている、 > - * もしくは使用中である。 > + * pageのstorage中には (PAGE_SIZE - PAGE_HEADER_SIZE)/ size個の > + * スロットがある。 > */ > struct page { > - int magic; > - struct page *prev, *next; > - struct chunk *free_list; > + struct page *next; > + struct chunk *next_in_page; > unsigned char storage[1]; > }; > > struct allocator_priv { > - int size; > - int max_obj; > - int use_count; > - struct page page_list; > +#if defined(GLOBAL_FREE_LIST) > + struct chunk *free_list; > +#endif > + struct page *page_list; > struct allocator_priv *next; > void (*dtor)(void *);/* sfreeした際に呼ばれる */ > + unsigned int size; > }; > > static struct allocator_priv *allocator_list; > > -static struct chunk * > -get_chunk_address(void *s) > +static struct page * > +get_page(struct chunk *c) > { > - return (struct chunk *) > - ((unsigned long)s - CHUNK_HEADER_SIZE); > + unsigned long l = (unsigned long)c; > + l &= ~(PAGE_SIZE - 1); > + return (struct page *)l; > } > > -static struct page * > -alloc_page(void) > +static void > +alloc_page(allocator a) > { > + void *v; > struct page *p; > - p = malloc(PAGE_SIZE); > - if (!p) { > + struct chunk *c, *c0; > + int i; > + > + if (posix_memalign(&v, PAGE_SIZE, PAGE_SIZE) != 0) { > anthy_log(0, "Fatal error: Failed to allocate memory.\n"); > exit(1); > } > - p->magic = PAGE_MAGIC; > - p->free_list = NULL; > - return p; > -} > + nr_pages++; > + p = (struct page *)v; > > -static struct chunk * > -get_chunk_from_page(allocator a, struct page *p) > -{ > - struct chunk *c; > - if (p->free_list) { > - c = (struct chunk *)p->free_list; > - p->free_list = c->ptr; > - c->ptr = p; > - return c; > - } > - if (p != a->page_list.next || a->use_count == a->max_obj) { > - /* It's not the first page or the first page is full. */ > - return NULL; > - } > - c = (struct chunk *) > - &p->storage[a->use_count * (a->size + CHUNK_HEADER_SIZE)]; > - c->ptr = p; > - a->use_count ++; > - return c; > + p->next = a->page_list; > + a->page_list = p; > + > + c0 = NULL; > + for (i = 0; i < NUM_CHUNKS(a); i++) { > + c = (struct chunk *)&p->storage[i * a->size]; > + c->u.l.next_in_page = c0; > +#if defined(GLOBAL_FREE_LIST) > + c->u.l.free_list = a->free_list; > + a->free_list = c; > +#endif > + c0 = c; > + } > + p->next_in_page = c0; > } > > allocator > -anthy_create_allocator(int size, void (*dtor)(void *)) > +anthy_create_allocator(unsigned int size, void (*dtor)(void *)) > { > allocator a; > - if (size > (int)(PAGE_SIZE - PAGE_HEADER_SIZE - CHUNK_HEADER_SIZE)) { > + if (size < MINIMUM_SIZE) > + size = MINIMUM_SIZE; > + if (size > PAGE_CONTENT_SIZE) { > anthy_log(0, "Fatal error: too big allocator is requested.\n"); > exit(1); > } > @@ -122,10 +117,10 @@ > } > a->size = size; > a->dtor = dtor; > - a->max_obj = (PAGE_SIZE - PAGE_HEADER_SIZE) / (size + CHUNK_HEADER_SIZE); > - a->use_count = 0; > - a->page_list.next = &a->page_list; > - a->page_list.prev = &a->page_list; > + a->page_list = NULL; > +#if defined(GLOBAL_FREE_LIST) > + a->free_list = NULL; > +#endif > a->next = allocator_list; > allocator_list = a; > return a; > @@ -134,27 +129,35 @@ > static void > anthy_free_allocator_internal(allocator a) > { > + int i; > struct page *p, *p_next; > - int is_first_page = 1; > + int *chunk_freed = (int *)alloca (sizeof(int) * NUM_CHUNKS(a)); > > - for (p = a->page_list.next; p != &a->page_list; p = p_next) { > - int limit = is_first_page ? a->use_count : a->max_obj; > - int i; > + for (i = 0; i < NUM_CHUNKS(a); i++) > + chunk_freed[i] = 0; > > + for (p = a->page_list; p; p = p_next) { > p_next = p->next; > if (a->dtor) { > - for (i = 0; i < limit; i++) { > - struct chunk *c; > + struct chunk *c, *c_next; > > - c = (struct chunk *)&p->storage[i * (a->size + CHUNK_HEADER_SIZE)]; > - if (c->ptr == (void*)p) { > - a->dtor(c->storage); > - } > + for (c = p->next_in_page; c; c= c_next) { > + c_next = c->u.l.next_in_page; > + i = ((unsigned long)c - (unsigned long)p->storage) / a->size; > + chunk_freed[i] = 1; > + } > + > + for (i = 0; i < NUM_CHUNKS(a); i++) { > + if (chunk_freed[i]) > + chunk_freed[i] = 0; > + else { > + c = (struct chunk *)&p->storage[i * a->size]; > + a->dtor((void *)c->u.storage); > + } > } > } > free(p); > nr_pages--; > - is_first_page = 0; > } > free(a); > } > @@ -180,23 +183,25 @@ > { > struct page *p; > struct chunk *c; > - for (p = a->page_list.next; p != &a->page_list; p = p->next) { > - c = get_chunk_from_page(a, p); > +#if defined(GLOBAL_FREE_LIST) > + c = a->free_list; > + if (c) { > + a->free_list = c->u.l.free_list; > + p = get_page(c); > + p->next_in_page = c->u.l.next_in_page; > + return (void *)c->u.storage; > + } > +#else > + for (p = a->page_list; p; p = p->next) { > + c = p->next_in_page; > if (c) { > -#ifdef MEM_DEBUG > - c->ator = a; > -#endif > - return c->storage; > + p = get_page(c); > + p->next_in_page = c->u.l.next_in_page; > + return (void *)c->u.storage; > } > } > - p = alloc_page(); > - nr_pages++; > - > - p->next = a->page_list.next; > - p->prev = &a->page_list; > - a->page_list.next->prev = p; > - a->page_list.next = p; > - a->use_count = 0; > +#endif > + alloc_page(a); > return anthy_smalloc(a); > } > > @@ -205,23 +210,17 @@ > { > struct chunk *c; > struct page *p; > - c = get_chunk_address(ptr); > - p = (struct page *)c->ptr; > - if (p->magic != PAGE_MAGIC) { > - anthy_log(0, "sfree()ing Invalid Object\n"); > - abort(); > - } > -#ifdef MEM_DEBUG > - if (a != c->ator) { > - anthy_log(0, "sfree()ing Invalid Allocator\n"); > - abort(); > - } > -#endif > + c = (struct chunk *)ptr; > if (a->dtor) { > a->dtor(ptr); > } > - c->ptr = p->free_list; > - p->free_list = (void *)c; > + p = get_page(c); > + c->u.l.next_in_page = p->next_in_page; > + p->next_in_page = c; > +#if defined(GLOBAL_FREE_LIST) > + c->u.l.free_list = a->free_list; > + a->free_list = c; > +#endif > } > > void > >
