git.ozlabs.org Git - ccan/blob - ccan/block_pool/block_pool.c

   1 /*
   2         Copyright (c) 2009  Joseph A. Adams
   3         All rights reserved.
   4
   5         Redistribution and use in source and binary forms, with or without
   6         modification, are permitted provided that the following conditions
   7         are met:
   8         1. Redistributions of source code must retain the above copyright
   9            notice, this list of conditions and the following disclaimer.
  10         2. Redistributions in binary form must reproduce the above copyright
  11            notice, this list of conditions and the following disclaimer in the
  12            documentation and/or other materials provided with the distribution.
  13         3. The name of the author may not be used to endorse or promote products
  14            derived from this software without specific prior written permission.
  15
  16         THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  17         IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  18         OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  19         IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  20         INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  21         NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  22         DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  23         THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24         (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  25         THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26 */
  27
  28 #include "block_pool.h"
  29 #include <stdlib.h>
  30 #include <stdio.h>
  31 #include <string.h>
  32
  33 //must be a power of 2
  34 #define BLOCK_SIZE 4096
  35
  36 struct block {
  37         size_t remaining;
  38         size_t size;
  39         char *data;
  40 };
  41
  42 struct block_pool {
  43         size_t count;
  44         size_t alloc; //2^n - 1, where n is an integer > 1
  45         struct block *block;
  46
  47         //blocks are arranged in a max-heap by the .remaining field
  48         // (except the root block does not percolate down until it is filled)
  49 };
  50
  51 static int destructor(struct block_pool *bp) {
  52         struct block *block = bp->block;
  53         size_t d = bp->count;
  54
  55         for (;d--;block++)
  56                 free(block->data);
  57         free(bp->block);
  58
  59         return 0;
  60 }
  61
  62 struct block_pool *block_pool_new(void *ctx) {
  63         struct block_pool *bp = talloc(ctx, struct block_pool);
  64         talloc_set_destructor(bp, destructor);
  65
  66         bp->count = 0;
  67         bp->alloc = 7;
  68         bp->block = malloc(bp->alloc * sizeof(struct block));
  69
  70         return bp;
  71 }
  72
  73 static void *new_block(struct block *b, size_t needed) {
  74         b->size = (needed+(BLOCK_SIZE-1)) & ~(BLOCK_SIZE-1);
  75         b->remaining = b->size - needed;
  76         b->data = malloc(b->size);
  77         return b->data;
  78 }
  79
  80 //for the first block, keep the memory usage low in case it's the only block.
  81 static void *new_block_tiny(struct block *b, size_t needed) {
  82         if (needed < 256)
  83                 b->size = 256;
  84         else
  85                 b->size = (needed+(BLOCK_SIZE-1)) & ~(BLOCK_SIZE-1);
  86         b->remaining = b->size - needed;
  87         b->data = malloc(b->size);
  88         return b->data;
  89 }
  90
  91 static void *try_block(struct block *b, size_t size, size_t align) {
  92         size_t offset = b->size - b->remaining;
  93         offset = (offset+align) & ~align;
  94
  95         if (b->size-offset >= size) {
  96                 //good, we can use this block
  97                 void *ret = b->data + offset;
  98                 b->remaining = b->size-offset-size;
  99
 100                 return ret;
 101         }
 102
 103         return NULL;
 104 }
 105
 106 #define L(node) (node+node+1)
 107 #define R(node) (node+node+2)
 108 #define P(node) ((node-1)>>1)
 109
 110 #define V(node) (bp->block[node].remaining)
 111
 112 static void percolate_down(struct block_pool *bp, size_t node) {
 113         size_t child = L(node);
 114         struct block tmp;
 115
 116         //get the maximum child
 117         if (child >= bp->count)
 118                 return;
 119         if (child+1 < bp->count && V(child+1) > V(child))
 120                 child++;
 121
 122         if (V(child) <= V(node))
 123                 return;
 124
 125         tmp = bp->block[node];
 126         bp->block[node] = bp->block[child];
 127         bp->block[child] = tmp;
 128
 129         percolate_down(bp, child);
 130 }
 131
 132 //note:  percolates up to either 1 or 2 as a root
 133 static void percolate_up(struct block_pool *bp, size_t node) {
 134         size_t parent = P(node);
 135         struct block tmp;
 136
 137         if (node<3 || V(parent) >= V(node))
 138                 return;
 139
 140         tmp = bp->block[node];
 141         bp->block[node] = bp->block[parent];
 142         bp->block[parent] = tmp;
 143
 144         percolate_up(bp, parent);
 145 }
 146
 147 void *block_pool_alloc_align(struct block_pool *bp, size_t size, size_t align) {
 148         void *ret;
 149
 150         if (align)
 151                 align--;
 152
 153         //if there aren't any blocks, make a new one
 154         if (!bp->count) {
 155                 bp->count = 1;
 156                 return new_block_tiny(bp->block, size);
 157         }
 158
 159         //try the root block
 160         ret = try_block(bp->block, size, align);
 161         if (ret)
 162                 return ret;
 163
 164         //root block is filled, percolate down and try the biggest one
 165         percolate_down(bp, 0);
 166         ret = try_block(bp->block, size, align);
 167         if (ret)
 168                 return ret;
 169
 170         //the biggest wasn't big enough; we need a new block
 171         if (bp->count >= bp->alloc) {
 172                 //make room for another block
 173                 bp->alloc += bp->alloc;
 174                 bp->alloc++;
 175                 bp->block = realloc(bp->block, bp->alloc * sizeof(struct block));
 176         }
 177         ret = new_block(bp->block+(bp->count++), size);
 178
 179         //fix the heap after adding the new block
 180         percolate_up(bp, bp->count-1);
 181
 182         return ret;
 183 }
 184
 185 #undef L
 186 #undef R
 187 #undef P
 188 #undef V
 189
 190 char *block_pool_strdup(struct block_pool *bp, const char *str) {
 191         size_t size = strlen(str)+1;
 192         char *ret = block_pool_alloc_align(bp, size, 1);
 193
 194         memcpy(ret, str, size);
 195         return ret;
 196 }