libdm/mm/pool-fast.c

   1 /*
   2  * Copyright (C) 2001-2004 Sistina Software, Inc. All rights reserved.
   3  * Copyright (C) 2004-2010 Red Hat, Inc. All rights reserved.
   4  *
   5  * This file is part of the device-mapper userspace tools.
   6  *
   7  * This copyrighted material is made available to anyone wishing to use,
   8  * modify, copy, or redistribute it subject to the terms and conditions
   9  * of the GNU Lesser General Public License v.2.1.
  10  *
  11  * You should have received a copy of the GNU Lesser General Public License
  12  * along with this program; if not, write to the Free Software Foundation,
  13  * Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  14  */
  15
  16 #ifdef VALGRIND_POOL
  17 #include "valgrind/memcheck.h"
  18 #endif
  19
  20 #include "dmlib.h"
  21
  22 struct chunk {
  23         char *begin, *end;
  24         struct chunk *prev;
  25 };
  26
  27 struct dm_pool {
  28         struct dm_list list;
  29         struct chunk *chunk, *spare_chunk;      /* spare_chunk is a one entry free
  30                                                    list to stop 'bobbling' */
  31         size_t chunk_size;
  32         size_t object_len;
  33         unsigned object_alignment;
  34 };
  35
  36 static void _align_chunk(struct chunk *c, unsigned alignment);
  37 static struct chunk *_new_chunk(struct dm_pool *p, size_t s);
  38 static void _free_chunk(struct chunk *c);
  39
  40 /* by default things come out aligned for doubles */
  41 #define DEFAULT_ALIGNMENT __alignof__ (double)
  42
  43 struct dm_pool *dm_pool_create(const char *name, size_t chunk_hint)
  44 {
  45         size_t new_size = 1024;
  46         struct dm_pool *p = dm_zalloc(sizeof(*p));
  47
  48         if (!p) {
  49                 log_error("Couldn't create memory pool %s (size %"
  50                           PRIsize_t ")", name, sizeof(*p));
  51                 return 0;
  52         }
  53
  54         /* round chunk_hint up to the next power of 2 */
  55         p->chunk_size = chunk_hint + sizeof(struct chunk);
  56         while (new_size < p->chunk_size)
  57                 new_size <<= 1;
  58         p->chunk_size = new_size;
  59         dm_list_add(&_dm_pools, &p->list);
  60         return p;
  61 }
  62
  63 void dm_pool_destroy(struct dm_pool *p)
  64 {
  65         struct chunk *c, *pr;
  66         _free_chunk(p->spare_chunk);
  67         c = p->chunk;
  68         while (c) {
  69                 pr = c->prev;
  70                 _free_chunk(c);
  71                 c = pr;
  72         }
  73
  74         dm_list_del(&p->list);
  75         dm_free(p);
  76 }
  77
  78 void *dm_pool_alloc(struct dm_pool *p, size_t s)
  79 {
  80         return dm_pool_alloc_aligned(p, s, DEFAULT_ALIGNMENT);
  81 }
  82
  83 void *dm_pool_alloc_aligned(struct dm_pool *p, size_t s, unsigned alignment)
  84 {
  85         struct chunk *c = p->chunk;
  86         void *r;
  87
  88         /* realign begin */
  89         if (c)
  90                 _align_chunk(c, alignment);
  91
  92         /* have we got room ? */
  93         if (!c || (c->begin > c->end) || (c->end - c->begin < s)) {
  94                 /* allocate new chunk */
  95                 size_t needed = s + alignment + sizeof(struct chunk);
  96                 c = _new_chunk(p, (needed > p->chunk_size) ?
  97                                needed : p->chunk_size);
  98
  99                 if (!c)
 100                         return NULL;
 101
 102                 _align_chunk(c, alignment);
 103         }
 104
 105         r = c->begin;
 106         c->begin += s;
 107
 108 #ifdef VALGRIND_POOL
 109         VALGRIND_MAKE_MEM_UNDEFINED(r, s);
 110 #endif
 111
 112         return r;
 113 }
 114
 115 void dm_pool_empty(struct dm_pool *p)
 116 {
 117         struct chunk *c;
 118
 119         for (c = p->chunk; c && c->prev; c = c->prev)
 120                 ;
 121
 122         if (c)
 123                 dm_pool_free(p, (char *) (c + 1));
 124 }
 125
 126 void dm_pool_free(struct dm_pool *p, void *ptr)
 127 {
 128         struct chunk *c = p->chunk;
 129
 130         while (c) {
 131                 if (((char *) c < (char *) ptr) &&
 132                     ((char *) c->end > (char *) ptr)) {
 133                         c->begin = ptr;
 134 #ifdef VALGRIND_POOL
 135                         VALGRIND_MAKE_MEM_NOACCESS(c->begin, c->end - c->begin);
 136 #endif
 137                         break;
 138                 }
 139
 140                 if (p->spare_chunk)
 141                         _free_chunk(p->spare_chunk);
 142
 143                 c->begin = (char *) (c + 1);
 144 #ifdef VALGRIND_POOL
 145                 VALGRIND_MAKE_MEM_NOACCESS(c->begin, c->end - c->begin);
 146 #endif
 147
 148                 p->spare_chunk = c;
 149                 c = c->prev;
 150         }
 151
 152         if (!c)
 153                 log_error(INTERNAL_ERROR "pool_free asked to free pointer "
 154                           "not in pool");
 155         else
 156                 p->chunk = c;
 157 }
 158
 159 int dm_pool_begin_object(struct dm_pool *p, size_t hint)
 160 {
 161         struct chunk *c = p->chunk;
 162         const size_t align = DEFAULT_ALIGNMENT;
 163
 164         p->object_len = 0;
 165         p->object_alignment = align;
 166
 167         if (c)
 168                 _align_chunk(c, align);
 169
 170         if (!c || (c->begin > c->end) || (c->end - c->begin < hint)) {
 171                 /* allocate a new chunk */
 172                 c = _new_chunk(p,
 173                                hint > (p->chunk_size - sizeof(struct chunk)) ?
 174                                hint + sizeof(struct chunk) + align :
 175                                p->chunk_size);
 176
 177                 if (!c)
 178                         return 0;
 179
 180                 _align_chunk(c, align);
 181         }
 182
 183         return 1;
 184 }
 185
 186 int dm_pool_grow_object(struct dm_pool *p, const void *extra, size_t delta)
 187 {
 188         struct chunk *c = p->chunk, *nc;
 189
 190         if (!delta)
 191                 delta = strlen(extra);
 192
 193         if (c->end - (c->begin + p->object_len) < delta) {
 194                 /* move into a new chunk */
 195                 if (p->object_len + delta > (p->chunk_size / 2))
 196                         nc = _new_chunk(p, (p->object_len + delta) * 2);
 197                 else
 198                         nc = _new_chunk(p, p->chunk_size);
 199
 200                 if (!nc)
 201                         return 0;
 202
 203                 _align_chunk(p->chunk, p->object_alignment);
 204
 205 #ifdef VALGRIND_POOL
 206                 VALGRIND_MAKE_MEM_UNDEFINED(p->chunk->begin, p->object_len);
 207 #endif
 208
 209                 memcpy(p->chunk->begin, c->begin, p->object_len);
 210
 211 #ifdef VALGRIND_POOL
 212                 VALGRIND_MAKE_MEM_NOACCESS(c->begin, p->object_len);
 213 #endif
 214
 215                 c = p->chunk;
 216         }
 217
 218 #ifdef VALGRIND_POOL
 219         VALGRIND_MAKE_MEM_UNDEFINED(p->chunk->begin + p->object_len, delta);
 220 #endif
 221
 222         memcpy(c->begin + p->object_len, extra, delta);
 223         p->object_len += delta;
 224         return 1;
 225 }
 226
 227 void *dm_pool_end_object(struct dm_pool *p)
 228 {
 229         struct chunk *c = p->chunk;
 230         void *r = c->begin;
 231         c->begin += p->object_len;
 232         p->object_len = 0u;
 233         p->object_alignment = DEFAULT_ALIGNMENT;
 234         return r;
 235 }
 236
 237 void dm_pool_abandon_object(struct dm_pool *p)
 238 {
 239         p->object_len = 0;
 240         p->object_alignment = DEFAULT_ALIGNMENT;
 241 }
 242
 243 static void _align_chunk(struct chunk *c, unsigned alignment)
 244 {
 245         c->begin += alignment - ((unsigned long) c->begin & (alignment - 1));
 246 }
 247
 248 static struct chunk *_new_chunk(struct dm_pool *p, size_t s)
 249 {
 250         struct chunk *c;
 251
 252         if (p->spare_chunk &&
 253             ((p->spare_chunk->end - p->spare_chunk->begin) >= s)) {
 254                 /* reuse old chunk */
 255                 c = p->spare_chunk;
 256                 p->spare_chunk = 0;
 257         } else {
 258                 if (!(c = dm_malloc(s))) {
 259                         log_error("Out of memory.  Requested %" PRIsize_t
 260                                   " bytes.", s);
 261                         return NULL;
 262                 }
 263
 264                 c->begin = (char *) (c + 1);
 265                 c->end = (char *) c + s;
 266
 267 #ifdef VALGRIND_POOL
 268                 VALGRIND_MAKE_MEM_NOACCESS(c->begin, c->end - c->begin);
 269 #endif
 270         }
 271
 272         c->prev = p->chunk;
 273         p->chunk = c;
 274         return c;
 275 }
 276
 277 static void _free_chunk(struct chunk *c)
 278 {
 279         if (c) {
 280 #ifdef VALGRIND_POOL
 281                 VALGRIND_MAKE_MEM_UNDEFINED(c, c->end - (char *) c);
 282 #endif
 283
 284                 dm_free(c);
 285         }
 286 }