From: Michal Schmidt Date: Tue, 12 Aug 2014 21:35:23 +0000 (+0200) Subject: shared: split mempool implementation from hashmaps X-Git-Tag: v217~117 X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ianmdlvl/git?p=elogind.git;a=commitdiff_plain;h=b3dcf58e283ff1bcb2c1ffacccb158d6e0c271e6 shared: split mempool implementation from hashmaps --- diff --git a/Makefile.am b/Makefile.am index 4d93304cb..fae946a38 100644 --- a/Makefile.am +++ b/Makefile.am @@ -768,6 +768,8 @@ libsystemd_shared_la_SOURCES = \ src/shared/time-util.h \ src/shared/locale-util.c \ src/shared/locale-util.h \ + src/shared/mempool.c \ + src/shared/mempool.h \ src/shared/hashmap.c \ src/shared/hashmap.h \ src/shared/siphash24.c \ diff --git a/src/shared/hashmap.c b/src/shared/hashmap.c index 8225b8ebc..1c3a45289 100644 --- a/src/shared/hashmap.c +++ b/src/shared/hashmap.c @@ -28,6 +28,7 @@ #include "hashmap.h" #include "macro.h" #include "siphash24.h" +#include "mempool.h" #define INITIAL_N_BUCKETS 31 @@ -50,82 +51,21 @@ struct Hashmap { bool from_pool:1; }; -struct pool { - struct pool *next; - unsigned n_tiles; - unsigned n_used; +struct hashmap_tile { + Hashmap h; + struct hashmap_entry *initial_buckets[INITIAL_N_BUCKETS]; }; -static struct pool *first_hashmap_pool = NULL; -static void *first_hashmap_tile = NULL; - -static struct pool *first_entry_pool = NULL; -static void *first_entry_tile = NULL; - -static void* allocate_tile(struct pool **first_pool, void **first_tile, size_t tile_size, unsigned at_least) { - unsigned i; - - /* When a tile is released we add it to the list and simply - * place the next pointer at its offset 0. */ - - assert(tile_size >= sizeof(void*)); - assert(at_least > 0); - - if (*first_tile) { - void *r; - - r = *first_tile; - *first_tile = * (void**) (*first_tile); - return r; - } - - if (_unlikely_(!*first_pool) || _unlikely_((*first_pool)->n_used >= (*first_pool)->n_tiles)) { - unsigned n; - size_t size; - struct pool *p; - - n = *first_pool ? (*first_pool)->n_tiles : 0; - n = MAX(at_least, n * 2); - size = PAGE_ALIGN(ALIGN(sizeof(struct pool)) + n*tile_size); - n = (size - ALIGN(sizeof(struct pool))) / tile_size; - - p = malloc(size); - if (!p) - return NULL; - - p->next = *first_pool; - p->n_tiles = n; - p->n_used = 0; - - *first_pool = p; - } - - i = (*first_pool)->n_used++; - - return ((uint8_t*) (*first_pool)) + ALIGN(sizeof(struct pool)) + i*tile_size; -} - -static void deallocate_tile(void **first_tile, void *p) { - * (void**) p = *first_tile; - *first_tile = p; -} +static DEFINE_MEMPOOL(hashmap_pool, struct hashmap_tile, 8); +static DEFINE_MEMPOOL(hashmap_entry_pool, struct hashmap_entry, 64); #ifdef VALGRIND -static void drop_pool(struct pool *p) { - while (p) { - struct pool *n; - n = p->next; - free(p); - p = n; - } -} - -__attribute__((destructor)) static void cleanup_pool(void) { +__attribute__((destructor)) static void cleanup_pools(void) { /* Be nice to valgrind */ - drop_pool(first_hashmap_pool); - drop_pool(first_entry_pool); + mempool_drop(&hashmap_entry_pool); + mempool_drop(&hashmap_pool); } #endif @@ -223,33 +163,32 @@ static void get_hash_key(uint8_t hash_key[HASH_KEY_SIZE], bool reuse_is_ok) { Hashmap *hashmap_new(const struct hash_ops *hash_ops) { bool b; + struct hashmap_tile *ht; Hashmap *h; - size_t size; b = is_main_thread(); - size = ALIGN(sizeof(Hashmap)) + INITIAL_N_BUCKETS * sizeof(struct hashmap_entry*); - if (b) { - h = allocate_tile(&first_hashmap_pool, &first_hashmap_tile, size, 8); - if (!h) + ht = mempool_alloc_tile(&hashmap_pool); + if (!ht) return NULL; - memzero(h, size); + memzero(ht, sizeof(struct hashmap_tile)); } else { - h = malloc0(size); + ht = malloc0(sizeof(struct hashmap_tile)); - if (!h) + if (!ht) return NULL; } + h = &ht->h; h->hash_ops = hash_ops ? hash_ops : &trivial_hash_ops; h->n_buckets = INITIAL_N_BUCKETS; h->n_entries = 0; h->iterate_list_head = h->iterate_list_tail = NULL; - h->buckets = (struct hashmap_entry**) ((uint8_t*) h + ALIGN(sizeof(Hashmap))); + h->buckets = ht->initial_buckets; h->from_pool = b; @@ -339,7 +278,7 @@ static void remove_entry(Hashmap *h, struct hashmap_entry *e) { unlink_entry(h, e, hash); if (h->from_pool) - deallocate_tile(&first_entry_tile, e); + mempool_free_tile(&hashmap_entry_pool, e); else free(e); } @@ -357,7 +296,7 @@ void hashmap_free(Hashmap*h) { free(h->buckets); if (h->from_pool) - deallocate_tile(&first_hashmap_tile, h); + mempool_free_tile(&hashmap_pool, container_of(h, struct hashmap_tile, h)); else free(h); } @@ -497,7 +436,7 @@ static int __hashmap_put(Hashmap *h, const void *key, void *value, unsigned hash hash = bucket_hash(h, key); if (h->from_pool) - e = allocate_tile(&first_entry_pool, &first_entry_tile, sizeof(struct hashmap_entry), 64U); + e = mempool_alloc_tile(&hashmap_entry_pool); else e = new(struct hashmap_entry, 1); diff --git a/src/shared/mempool.c b/src/shared/mempool.c new file mode 100644 index 000000000..b39a37f2d --- /dev/null +++ b/src/shared/mempool.c @@ -0,0 +1,94 @@ +/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/ + +/*** + This file is part of systemd. + + Copyright 2010-2014 Lennart Poettering + Copyright 2014 Michal Schmidt + + systemd is free software; you can redistribute it and/or modify it + under the terms of the GNU Lesser General Public License as published by + the Free Software Foundation; either version 2.1 of the License, or + (at your option) any later version. + + systemd is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public License + along with systemd; If not, see . +***/ + +#include "mempool.h" +#include "macro.h" +#include "util.h" + +struct pool { + struct pool *next; + unsigned n_tiles; + unsigned n_used; +}; + +void* mempool_alloc_tile(struct mempool *mp) { + unsigned i; + + /* When a tile is released we add it to the list and simply + * place the next pointer at its offset 0. */ + + assert(mp->tile_size >= sizeof(void*)); + assert(mp->at_least > 0); + + if (mp->freelist) { + void *r; + + r = mp->freelist; + mp->freelist = * (void**) mp->freelist; + return r; + } + + if (_unlikely_(!mp->first_pool) || + _unlikely_(mp->first_pool->n_used >= mp->first_pool->n_tiles)) { + unsigned n; + size_t size; + struct pool *p; + + n = mp->first_pool ? mp->first_pool->n_tiles : 0; + n = MAX(mp->at_least, n * 2); + size = PAGE_ALIGN(ALIGN(sizeof(struct pool)) + n*mp->tile_size); + n = (size - ALIGN(sizeof(struct pool))) / mp->tile_size; + + p = malloc(size); + if (!p) + return NULL; + + p->next = mp->first_pool; + p->n_tiles = n; + p->n_used = 0; + + mp->first_pool = p; + } + + i = mp->first_pool->n_used++; + + return ((uint8_t*) mp->first_pool) + ALIGN(sizeof(struct pool)) + i*mp->tile_size; +} + +void mempool_free_tile(struct mempool *mp, void *p) { + * (void**) p = mp->freelist; + mp->freelist = p; +} + +#ifdef VALGRIND + +void mempool_drop(struct mempool *mp) { + struct pool *p = mp->first_pool; + while (p) { + struct pool *n; + n = p->next; + free(p); + p = n; + } +} + +#endif diff --git a/src/shared/mempool.h b/src/shared/mempool.h new file mode 100644 index 000000000..8b0bf381b --- /dev/null +++ b/src/shared/mempool.h @@ -0,0 +1,48 @@ +/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/ + +#pragma once + +/*** + This file is part of systemd. + + Copyright 2011-2014 Lennart Poettering + Copyright 2014 Michal Schmidt + + systemd is free software; you can redistribute it and/or modify it + under the terms of the GNU Lesser General Public License as published by + the Free Software Foundation; either version 2.1 of the License, or + (at your option) any later version. + + systemd is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public License + along with systemd; If not, see . +***/ + +#include + +struct pool; + +struct mempool { + struct pool *first_pool; + void *freelist; + size_t tile_size; + unsigned at_least; +}; + +void* mempool_alloc_tile(struct mempool *mp); +void mempool_free_tile(struct mempool *mp, void *p); + +#define DEFINE_MEMPOOL(pool_name, tile_type, alloc_at_least) \ +struct mempool pool_name = { \ + .tile_size = sizeof(tile_type), \ + .at_least = alloc_at_least, \ +} + + +#ifdef VALGRIND +void mempool_drop(struct mempool *mp); +#endif