source/libs/cairo/cairo-src/src/cairo-mempool.c

   1 /* Cairo - a vector graphics library with display and print output
   2  *
   3  * Copyright © 2007 Chris Wilson
   4  * Copyright © 2009 Intel Corporation
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it either under the terms of the GNU Lesser General Public
   8  * License version 2.1 as published by the Free Software Foundation
   9  * (the "LGPL") or, at your option, under the terms of the Mozilla
  10  * Public License Version 1.1 (the "MPL"). If you do not alter this
  11  * notice, a recipoolent may use your version of this file under either
  12  * the MPL or the LGPL.
  13  *
  14  * You should have received a copy of the LGPL along with this library
  15  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
  17  * You should have received a copy of the MPL along with this library
  18  * in the file COPYING-MPL-1.1
  19  *
  20  * The contents of this file are subject to the Mozilla Public License
  21  * Version 1.1 (the "License"); you may not use this file except in
  22  * compliance with the License. You may obtain a copy of the License at
  23  * http://www.mozilla.org/MPL/
  24  *
  25  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  26  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  27  * the specific language governing rights and limitations.
  28  *
  29  * The Original Code is the cairo graphics library.
  30  *
  31  * The Initial Developer of the Original Code is Red Hat, Inc.
  32  *
  33  * Contributors(s):
  34  *      Chris Wilson <chris@chris-wilson.co.uk>
  35  */
  36
  37 #include "cairoint.h"
  38
  39 #include "cairo-mempool-private.h"
  40 #include "cairo-list-inline.h"
  41
  42 /* a simple buddy allocator for memory pools
  43  * XXX fragmentation? use Doug Lea's malloc?
  44  */
  45
  46 #define BITTEST(p, n)  ((p)->map[(n) >> 3] &   (128 >> ((n) & 7)))
  47 #define BITSET(p, n)   ((p)->map[(n) >> 3] |=  (128 >> ((n) & 7)))
  48 #define BITCLEAR(p, n) ((p)->map[(n) >> 3] &= ~(128 >> ((n) & 7)))
  49
  50 static void
  51 clear_bits (cairo_mempool_t *pool, size_t first, size_t last)
  52 {
  53     size_t i, n = last;
  54     size_t first_full = (first + 7) & ~7;
  55     size_t past_full = last & ~7;
  56     size_t bytes;
  57
  58     if (n > first_full)
  59         n = first_full;
  60     for (i = first; i < n; i++)
  61           BITCLEAR (pool, i);
  62
  63     if (past_full > first_full) {
  64         bytes = past_full - first_full;
  65         bytes = bytes >> 3;
  66         memset (pool->map + (first_full >> 3), 0, bytes);
  67     }
  68
  69     if (past_full < n)
  70         past_full = n;
  71     for (i = past_full; i < last; i++)
  72         BITCLEAR (pool, i);
  73 }
  74
  75 static void
  76 free_bits (cairo_mempool_t *pool, size_t start, int bits, cairo_bool_t clear)
  77 {
  78     struct _cairo_memblock *block;
  79
  80     if (clear)
  81         clear_bits (pool, start, start + (1 << bits));
  82
  83     block = pool->blocks + start;
  84     block->bits = bits;
  85
  86     cairo_list_add (&block->link, &pool->free[bits]);
  87
  88     pool->free_bytes += 1 << (bits + pool->min_bits);
  89     if (bits > pool->max_free_bits)
  90         pool->max_free_bits = bits;
  91 }
  92
  93 /* Add a chunk to the free list */
  94 static void
  95 free_blocks (cairo_mempool_t *pool,
  96              size_t first,
  97              size_t last,
  98              cairo_bool_t clear)
  99 {
 100     size_t i, len;
 101     int bits = 0;
 102
 103     for (i = first, len = 1; i < last; i += len) {
 104         /* To avoid cost quadratic in the number of different
 105          * blocks produced from this chunk of store, we have to
 106          * use the size of the previous block produced from this
 107          * chunk as the starting point to work out the size of the
 108          * next block we can produce. If you look at the binary
 109          * representation of the starting points of the blocks
 110          * produced, you can see that you first of all increase the
 111          * size of the blocks produced up to some maximum as the
 112          * address dealt with gets offsets added on which zap out
 113          * low order bits, then decrease as the low order bits of the
 114          * final block produced get added in. E.g. as you go from
 115          * 001 to 0111 you generate blocks
 116          * of size 001 at 001 taking you to 010
 117          * of size 010 at 010 taking you to 100
 118          * of size 010 at 100 taking you to 110
 119          * of size 001 at 110 taking you to 111
 120          * So the maximum total cost of the loops below this comment
 121          * is one trip from the lowest blocksize to the highest and
 122          * back again.
 123          */
 124         while (bits < pool->num_sizes - 1) {
 125             size_t next_bits = bits + 1;
 126             size_t next_len = len << 1;
 127
 128             if (i + next_bits > last) {
 129                 /* off end of chunk to be freed */
 130                 break;
 131             }
 132
 133             if (i & (next_len - 1)) /* block would not be on boundary */
 134                 break;
 135
 136             bits = next_bits;
 137             len = next_len;
 138         }
 139
 140         do {
 141             if (i + len <= last && /* off end of chunk to be freed */
 142                 (i & (len - 1)) == 0) /* block would not be on boundary */
 143                 break;
 144
 145             bits--; len >>=1;
 146         } while (len);
 147
 148         if (len == 0)
 149             break;
 150
 151         free_bits (pool, i, bits, clear);
 152     }
 153 }
 154
 155 static struct _cairo_memblock *
 156 get_buddy (cairo_mempool_t *pool, size_t offset, int bits)
 157 {
 158     struct _cairo_memblock *block;
 159
 160     if (offset + (1 << bits) >= pool->num_blocks)
 161         return NULL; /* invalid */
 162
 163     if (BITTEST (pool, offset + (1 << bits) - 1))
 164         return NULL; /* buddy is allocated */
 165
 166     block = pool->blocks + offset;
 167     if (block->bits != bits)
 168         return NULL; /* buddy is partially allocated */
 169
 170     return block;
 171 }
 172
 173 static void
 174 merge_buddies (cairo_mempool_t *pool,
 175                struct _cairo_memblock *block,
 176                int max_bits)
 177 {
 178     size_t block_offset = block - pool->blocks;
 179     int bits = block->bits;
 180
 181     while (bits < max_bits - 1) {
 182         /* while you can, merge two blocks and get a legal block size */
 183         size_t buddy_offset = block_offset ^ (1 << bits);
 184
 185         block = get_buddy (pool, buddy_offset, bits);
 186         if (block == NULL)
 187             break;
 188
 189         cairo_list_del (&block->link);
 190
 191         /* Merged block starts at buddy */
 192         if (buddy_offset < block_offset)
 193             block_offset = buddy_offset;
 194
 195         bits++;
 196     }
 197
 198     block = pool->blocks + block_offset;
 199     block->bits = bits;
 200     cairo_list_add (&block->link, &pool->free[bits]);
 201
 202     if (bits > pool->max_free_bits)
 203         pool->max_free_bits = bits;
 204 }
 205
 206 /* attempt to merge all available buddies up to a particular size */
 207 static int
 208 merge_bits (cairo_mempool_t *pool, int max_bits)
 209 {
 210     struct _cairo_memblock *block, *buddy, *next;
 211     int bits;
 212
 213     for (bits = 0; bits < max_bits - 1; bits++) {
 214         cairo_list_foreach_entry_safe (block, next,
 215                                        struct _cairo_memblock,
 216                                        &pool->free[bits],
 217                                        link)
 218         {
 219             size_t buddy_offset = (block - pool->blocks) ^ (1 << bits);
 220
 221             buddy = get_buddy (pool, buddy_offset, bits);
 222             if (buddy == NULL)
 223                 continue;
 224
 225             if (buddy == next) {
 226                 next = cairo_container_of (buddy->link.next,
 227                                            struct _cairo_memblock,
 228                                            link);
 229             }
 230
 231             cairo_list_del (&block->link);
 232             merge_buddies (pool, block, max_bits);
 233         }
 234     }
 235
 236     return pool->max_free_bits;
 237 }
 238
 239 /* find store for 1 << bits blocks */
 240 static void *
 241 buddy_malloc (cairo_mempool_t *pool, int bits)
 242 {
 243     size_t past, offset;
 244     struct _cairo_memblock *block;
 245     int b;
 246
 247     if (bits > pool->max_free_bits && bits > merge_bits (pool, bits))
 248         return NULL;
 249
 250     /* Find a list with blocks big enough on it */
 251     block = NULL;
 252     for (b = bits; b <= pool->max_free_bits; b++) {
 253         if (! cairo_list_is_empty (&pool->free[b])) {
 254             block = cairo_list_first_entry (&pool->free[b],
 255                                             struct _cairo_memblock,
 256                                             link);
 257             break;
 258         }
 259     }
 260     assert (block != NULL);
 261
 262     cairo_list_del (&block->link);
 263
 264     while (cairo_list_is_empty (&pool->free[pool->max_free_bits])) {
 265         if (--pool->max_free_bits == -1)
 266             break;
 267     }
 268
 269     /* Mark end of allocated area */
 270     offset = block - pool->blocks;
 271     past = offset + (1 << bits);
 272     BITSET (pool, past - 1);
 273     block->bits = bits;
 274
 275     /* If we used a larger free block than we needed, free the rest */
 276     pool->free_bytes -= 1 << (b + pool->min_bits);
 277     free_blocks (pool, past, offset + (1 << b), 0);
 278
 279     return pool->base + ((block - pool->blocks) << pool->min_bits);
 280 }
 281
 282 cairo_status_t
 283 _cairo_mempool_init (cairo_mempool_t *pool,
 284                       void *base, size_t bytes,
 285                       int min_bits, int num_sizes)
 286 {
 287     unsigned long tmp;
 288     int num_blocks;
 289     int i;
 290
 291     /* Align the start to an integral chunk */
 292     tmp = ((unsigned long) base) & ((1 << min_bits) - 1);
 293     if (tmp) {
 294         tmp = (1 << min_bits) - tmp;
 295         base = (char *)base + tmp;
 296         bytes -= tmp;
 297     }
 298
 299     assert ((((unsigned long) base) & ((1 << min_bits) - 1)) == 0);
 300     assert (num_sizes < ARRAY_LENGTH (pool->free));
 301
 302     pool->base = base;
 303     pool->free_bytes = 0;
 304     pool->max_bytes = bytes;
 305     pool->max_free_bits = -1;
 306
 307     num_blocks = bytes >> min_bits;
 308     pool->blocks = calloc (num_blocks, sizeof (struct _cairo_memblock));
 309     if (pool->blocks == NULL)
 310         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 311
 312     pool->num_blocks = num_blocks;
 313     pool->min_bits = min_bits;
 314     pool->num_sizes = num_sizes;
 315
 316     for (i = 0; i < ARRAY_LENGTH (pool->free); i++)
 317         cairo_list_init (&pool->free[i]);
 318
 319     pool->map = malloc ((num_blocks + 7) >> 3);
 320     if (pool->map == NULL) {
 321         free (pool->blocks);
 322         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 323     }
 324
 325     memset (pool->map, -1, (num_blocks + 7) >> 3);
 326     clear_bits (pool, 0, num_blocks);
 327
 328     /* Now add all blocks to the free list */
 329     free_blocks (pool, 0, num_blocks, 1);
 330
 331     return CAIRO_STATUS_SUCCESS;
 332 }
 333
 334 void *
 335 _cairo_mempool_alloc (cairo_mempool_t *pool, size_t bytes)
 336 {
 337     size_t size;
 338     int bits;
 339
 340     size = 1 << pool->min_bits;
 341     for (bits = 0; size < bytes; bits++)
 342         size <<= 1;
 343     if (bits >= pool->num_sizes)
 344         return NULL;
 345
 346     return buddy_malloc (pool, bits);
 347 }
 348
 349 void
 350 _cairo_mempool_free (cairo_mempool_t *pool, void *storage)
 351 {
 352     size_t block_offset;
 353     struct _cairo_memblock *block;
 354
 355     block_offset = ((char *)storage - pool->base) >> pool->min_bits;
 356     block = pool->blocks + block_offset;
 357
 358     BITCLEAR (pool, block_offset + ((1 << block->bits) - 1));
 359     pool->free_bytes += 1 << (block->bits + pool->min_bits);
 360
 361     merge_buddies (pool, block, pool->num_sizes);
 362 }
 363
 364 void
 365 _cairo_mempool_fini (cairo_mempool_t *pool)
 366 {
 367     free (pool->map);
 368     free (pool->blocks);
 369 }