memory_atomic.c

   1 /* -*- Mode: C ; c-basic-offset: 2 -*- */
   2 /*****************************************************************************
   3  *
   4  *   Non-sleeping memory allocation
   5  *
   6  *   Copyright (C) 2006,2007 Nedko Arnaudov <nedko@arnaudov.name>
   7  *
   8  *   This program is free software; you can redistribute it and/or modify
   9  *   it under the terms of the GNU General Public License as published by
  10  *   the Free Software Foundation; version 2 of the License
  11  *
  12  *   This program is distributed in the hope that it will be useful,
  13  *   but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  *   GNU General Public License for more details.
  16  *
  17  *   You should have received a copy of the GNU General Public License
  18  *   along with this program; if not, write to the Free Software
  19  *   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  *****************************************************************************/
  22
  23 #include <stdlib.h>
  24 #include <assert.h>
  25 #include <stdbool.h>
  26 #include <pthread.h>
  27
  28 #include "memory_atomic.h"
  29 #include "list.h"
  30 #include "log.h"
  31
  32 struct rtsafe_memory_pool
  33 {
  34   size_t data_size;
  35   size_t min_preallocated;
  36   size_t max_preallocated;
  37
  38   unsigned int used_count;
  39   struct list_head unused;
  40   unsigned int unused_count;
  41
  42   bool enforce_thread_safety;
  43   /* next members are initialized/used only if enforce_thread_safety is true */
  44   pthread_mutex_t mutex;
  45   unsigned int unused_count2;
  46   struct list_head pending;
  47 };
  48
  49 #define RTSAFE_GROUPS_PREALLOCATE      1024
  50
  51 bool
  52 rtsafe_memory_pool_create(
  53   size_t data_size,
  54   size_t min_preallocated,
  55   size_t max_preallocated,
  56   bool enforce_thread_safety,
  57   rtsafe_memory_pool_handle * pool_handle_ptr)
  58 {
  59   int ret;
  60   struct rtsafe_memory_pool * pool_ptr;
  61
  62   assert(min_preallocated <= max_preallocated);
  63
  64   pool_ptr = malloc(sizeof(struct rtsafe_memory_pool));
  65   if (pool_ptr == NULL)
  66   {
  67     return false;
  68   }
  69
  70   pool_ptr->data_size = data_size;
  71   pool_ptr->min_preallocated = min_preallocated;
  72   pool_ptr->max_preallocated = max_preallocated;
  73
  74   pool_ptr->used_count = 0;
  75
  76   INIT_LIST_HEAD(&pool_ptr->unused);
  77   pool_ptr->unused_count = 0;
  78
  79   pool_ptr->enforce_thread_safety = enforce_thread_safety;
  80   if (enforce_thread_safety)
  81   {
  82     ret = pthread_mutex_init(&pool_ptr->mutex, NULL);
  83     if (ret != 0)
  84     {
  85       free(pool_ptr);
  86       return false;
  87     }
  88
  89     INIT_LIST_HEAD(&pool_ptr->pending);
  90     pool_ptr->unused_count2 = 0;
  91   }
  92
  93   rtsafe_memory_pool_sleepy((rtsafe_memory_pool_handle)pool_ptr);
  94   *pool_handle_ptr = pool_ptr;
  95
  96   return true;
  97 }
  98
  99 #define pool_ptr ((struct rtsafe_memory_pool *)pool_handle)
 100
 101 void
 102 rtsafe_memory_pool_destroy(
 103   rtsafe_memory_pool_handle pool_handle)
 104 {
 105   int ret;
 106   struct list_head * node_ptr;
 107
 108   /* caller should deallocate all chunks prior releasing pool itself */
 109   assert(pool_ptr->used_count == 0);
 110
 111   while (pool_ptr->unused_count != 0)
 112   {
 113     assert(!list_empty(&pool_ptr->unused));
 114
 115     node_ptr = pool_ptr->unused.next;
 116
 117     list_del(node_ptr);
 118     pool_ptr->unused_count--;
 119
 120     free(node_ptr);
 121   }
 122
 123   assert(list_empty(&pool_ptr->unused));
 124
 125   if (pool_ptr->enforce_thread_safety)
 126   {
 127     while (!list_empty(&pool_ptr->pending))
 128     {
 129       node_ptr = pool_ptr->pending.next;
 130
 131       list_del(node_ptr);
 132
 133       free(node_ptr);
 134     }
 135
 136     ret = pthread_mutex_destroy(&pool_ptr->mutex);
 137     assert(ret == 0);
 138   }
 139
 140   free(pool_ptr);
 141 }
 142
 143 /* adjust unused list size */
 144 void
 145 rtsafe_memory_pool_sleepy(
 146   rtsafe_memory_pool_handle pool_handle)
 147 {
 148   struct list_head * node_ptr;
 149   unsigned int count;
 150
 151   if (pool_ptr->enforce_thread_safety)
 152   {
 153     pthread_mutex_lock(&pool_ptr->mutex);
 154
 155     count = pool_ptr->unused_count2;
 156
 157     assert(pool_ptr->min_preallocated < pool_ptr->max_preallocated);
 158
 159     while (count < pool_ptr->min_preallocated)
 160     {
 161       node_ptr = malloc(sizeof(struct list_head) + pool_ptr->data_size);
 162       if (node_ptr == NULL)
 163       {
 164         break;
 165       }
 166
 167       list_add_tail(node_ptr, &pool_ptr->pending);
 168
 169       count++;
 170     }
 171
 172     while (count > pool_ptr->max_preallocated && !list_empty(&pool_ptr->pending))
 173     {
 174       node_ptr = pool_ptr->pending.next;
 175
 176       list_del(node_ptr);
 177
 178       free(node_ptr);
 179
 180       count--;
 181     }
 182
 183     pthread_mutex_unlock(&pool_ptr->mutex);
 184   }
 185   else
 186   {
 187     while (pool_ptr->unused_count < pool_ptr->min_preallocated)
 188     {
 189       node_ptr = malloc(sizeof(struct list_head) + pool_ptr->data_size);
 190       if (node_ptr == NULL)
 191       {
 192         return;
 193       }
 194
 195       list_add_tail(node_ptr, &pool_ptr->unused);
 196       pool_ptr->unused_count++;
 197     }
 198
 199     while (pool_ptr->unused_count > pool_ptr->max_preallocated)
 200     {
 201       assert(!list_empty(&pool_ptr->unused));
 202
 203       node_ptr = pool_ptr->unused.next;
 204
 205       list_del(node_ptr);
 206       pool_ptr->unused_count--;
 207
 208       free(node_ptr);
 209     }
 210   }
 211 }
 212
 213 /* find entry in unused list, fail if it is empty */
 214 void *
 215 rtsafe_memory_pool_allocate(
 216   rtsafe_memory_pool_handle pool_handle)
 217 {
 218   struct list_head * node_ptr;
 219
 220   if (list_empty(&pool_ptr->unused))
 221   {
 222     return NULL;
 223   }
 224
 225   node_ptr = pool_ptr->unused.next;
 226   list_del(node_ptr);
 227   pool_ptr->unused_count--;
 228   pool_ptr->used_count++;
 229
 230   if (pool_ptr->enforce_thread_safety &&
 231       pthread_mutex_trylock(&pool_ptr->mutex) == 0)
 232   {
 233     while (pool_ptr->unused_count < pool_ptr->min_preallocated && !list_empty(&pool_ptr->pending))
 234     {
 235       node_ptr = pool_ptr->pending.next;
 236
 237       list_del(node_ptr);
 238       list_add_tail(node_ptr, &pool_ptr->unused);
 239       pool_ptr->unused_count++;
 240     }
 241
 242     pool_ptr->unused_count2 = pool_ptr->unused_count;
 243
 244     pthread_mutex_unlock(&pool_ptr->mutex);
 245   }
 246
 247   return (node_ptr + 1);
 248 }
 249
 250 /* move from used to unused list */
 251 void
 252 rtsafe_memory_pool_deallocate(
 253   rtsafe_memory_pool_handle pool_handle,
 254   void * data)
 255 {
 256   struct list_head * node_ptr;
 257
 258   list_add_tail((struct list_head *)data - 1, &pool_ptr->unused);
 259   pool_ptr->used_count--;
 260   pool_ptr->unused_count++;
 261
 262   if (pool_ptr->enforce_thread_safety &&
 263       pthread_mutex_trylock(&pool_ptr->mutex) == 0)
 264   {
 265     while (pool_ptr->unused_count > pool_ptr->max_preallocated)
 266     {
 267       assert(!list_empty(&pool_ptr->unused));
 268
 269       node_ptr = pool_ptr->unused.next;
 270
 271       list_del(node_ptr);
 272       list_add_tail(node_ptr, &pool_ptr->pending);
 273       pool_ptr->unused_count--;
 274     }
 275
 276     pool_ptr->unused_count2 = pool_ptr->unused_count;
 277
 278     pthread_mutex_unlock(&pool_ptr->mutex);
 279   }
 280 }
 281
 282 void *
 283 rtsafe_memory_pool_allocate_sleepy(
 284   rtsafe_memory_pool_handle pool_handle)
 285 {
 286   void * data;
 287
 288   do
 289   {
 290     rtsafe_memory_pool_sleepy(pool_handle);
 291     data = rtsafe_memory_pool_allocate(pool_handle);
 292   }
 293   while (data == NULL);
 294
 295   return data;
 296 }
 297
 298 /* max alloc is DATA_MIN * (2 ^ POOLS_COUNT) - DATA_SUB */
 299 #define DATA_MIN       1024
 300 #define DATA_SUB       100      /* alloc slightly smaller chunks in hope to not allocating additional page for control data */
 301
 302 struct rtsafe_memory_pool_generic
 303 {
 304   size_t size;
 305   rtsafe_memory_pool_handle pool;
 306 };
 307
 308 struct rtsafe_memory
 309 {
 310   struct rtsafe_memory_pool_generic * pools;
 311   size_t pools_count;
 312 };
 313
 314 bool
 315 rtsafe_memory_init(
 316   size_t max_size,
 317   size_t prealloc_min,
 318   size_t prealloc_max,
 319   bool enforce_thread_safety,
 320   rtsafe_memory_handle * handle_ptr)
 321 {
 322   size_t i;
 323   size_t size;
 324   struct rtsafe_memory * memory_ptr;
 325
 326   LOG_DEBUG("rtsafe_memory_init() called.");
 327
 328   memory_ptr = malloc(sizeof(struct rtsafe_memory));
 329   if (memory_ptr == NULL)
 330   {
 331     goto fail;
 332   }
 333
 334   size = DATA_MIN;
 335   memory_ptr->pools_count = 1;
 336
 337   while ((size << memory_ptr->pools_count) < max_size + DATA_SUB)
 338   {
 339     memory_ptr->pools_count++;
 340
 341     if (memory_ptr->pools_count > sizeof(size_t) * 8)
 342     {
 343       assert(0);                /* chances that caller really need such huge size are close to zero */
 344       goto fail_free;
 345     }
 346   }
 347
 348   memory_ptr->pools = malloc(memory_ptr->pools_count * sizeof(struct rtsafe_memory_pool_generic));
 349   if (memory_ptr->pools == NULL)
 350   {
 351     goto fail_free;
 352   }
 353
 354   size = DATA_MIN;
 355
 356   for (i = 0 ; i < memory_ptr->pools_count ; i++)
 357   {
 358     memory_ptr->pools[i].size = size - DATA_SUB;
 359
 360     if (!rtsafe_memory_pool_create(
 361           memory_ptr->pools[i].size,
 362           prealloc_min,
 363           prealloc_max,
 364           enforce_thread_safety,
 365           &memory_ptr->pools[i].pool))
 366     {
 367       while (i > 0)
 368       {
 369         i--;
 370         rtsafe_memory_pool_destroy(memory_ptr->pools[i].pool);
 371       }
 372
 373       goto fail_free_pools;
 374     }
 375
 376     size = size << 1;
 377   }
 378
 379   *handle_ptr = (rtsafe_memory_handle)memory_ptr;
 380
 381   return true;
 382
 383 fail_free_pools:
 384   free(memory_ptr->pools);
 385
 386 fail_free:
 387   free(memory_ptr);
 388
 389 fail:
 390   return false;
 391 }
 392
 393 #define memory_ptr ((struct rtsafe_memory *)handle_ptr)
 394 void
 395 rtsafe_memory_uninit(
 396   rtsafe_memory_handle handle_ptr)
 397 {
 398   unsigned int i;
 399
 400   LOG_DEBUG("rtsafe_memory_uninit() called.");
 401
 402   for (i = 0 ; i < memory_ptr->pools_count ; i++)
 403   {
 404     LOG_DEBUG("Destroying pool for size %u", (unsigned int)memory_ptr->pools[i].size);
 405     rtsafe_memory_pool_destroy(memory_ptr->pools[i].pool);
 406   }
 407
 408   free(memory_ptr->pools);
 409
 410   free(memory_ptr);
 411 }
 412
 413 void *
 414 rtsafe_memory_allocate(
 415   rtsafe_memory_handle handle_ptr,
 416   size_t size)
 417 {
 418   rtsafe_memory_pool_handle * data_ptr;
 419   size_t i;
 420
 421   LOG_DEBUG("rtsafe_memory_allocate() called.");
 422
 423   /* pool handle is stored just before user data to ease deallocation */
 424   size += sizeof(rtsafe_memory_pool_handle);
 425
 426   for (i = 0 ; i < memory_ptr->pools_count ; i++)
 427   {
 428     if (size <= memory_ptr->pools[i].size)
 429     {
 430       LOG_DEBUG("Using chunk with size %u.", (unsigned int)memory_ptr->pools[i].size);
 431       data_ptr = rtsafe_memory_pool_allocate(memory_ptr->pools[i].pool);
 432       if (data_ptr == NULL)
 433       {
 434         LOG_DEBUG("rtsafe_memory_pool_allocate() failed.");
 435         return NULL;
 436       }
 437
 438       *data_ptr = memory_ptr->pools[i].pool;
 439
 440       LOG_DEBUG("rtsafe_memory_allocate() returning %p", (data_ptr + 1));
 441       return (data_ptr + 1);
 442     }
 443   }
 444
 445   /* data size too big, increase POOLS_COUNT */
 446   LOG_WARNING("Data size is too big");
 447   return NULL;
 448 }
 449
 450 void
 451 rtsafe_memory_sleepy(
 452   rtsafe_memory_handle handle_ptr)
 453 {
 454   unsigned int i;
 455
 456   for (i = 0 ; i < memory_ptr->pools_count ; i++)
 457   {
 458     rtsafe_memory_pool_sleepy(memory_ptr->pools[i].pool);
 459   }
 460 }
 461
 462 void
 463 rtsafe_memory_deallocate(
 464   void * data)
 465 {
 466   LOG_DEBUG("rtsafe_memory_deallocate(%p) called.", data);
 467   rtsafe_memory_pool_deallocate(
 468     *((rtsafe_memory_pool_handle *)data -1),
 469     (rtsafe_memory_pool_handle *)data - 1);
 470 }