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
27
clear_bits (cairo_mempool_t *pool, size_t first, size_t last)
52
{
53
27
    size_t i, n = last;
54
27
    size_t first_full = (first + 7) & ~7;
55
27
    size_t past_full = last & ~7;
56
    size_t bytes;
57

            
58
27
    if (n > first_full)
59
27
	n = first_full;
60
27
    for (i = first; i < n; i++)
61
	  BITCLEAR (pool, i);
62

            
63
27
    if (past_full > first_full) {
64
27
	bytes = past_full - first_full;
65
27
	bytes = bytes >> 3;
66
27
	memset (pool->map + (first_full >> 3), 0, bytes);
67
    }
68

            
69
27
    if (past_full < n)
70
	past_full = n;
71
27
    for (i = past_full; i < last; i++)
72
	BITCLEAR (pool, i);
73
27
}
74

            
75
static void
76
27
free_bits (cairo_mempool_t *pool, size_t start, int bits, cairo_bool_t clear)
77
{
78
    struct _cairo_memblock *block;
79

            
80
27
    if (clear)
81
24
	clear_bits (pool, start, start + (((size_t) 1) << bits));
82

            
83
27
    block = pool->blocks + start;
84
27
    block->bits = bits;
85

            
86
27
    cairo_list_add (&block->link, &pool->free[bits]);
87

            
88
27
    pool->free_bytes += ((size_t) 1) << (bits + pool->min_bits);
89
27
    if (bits > pool->max_free_bits)
90
3
	pool->max_free_bits = bits;
91
27
}
92

            
93
/* Add a chunk to the free list */
94
static void
95
6
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
6
    int bits = 0;
102

            
103
33
    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
90
	while (bits < pool->num_sizes - 1) {
125
66
	    size_t next_bits = bits + 1;
126
66
	    size_t next_len = len << 1;
127

            
128
66
	    if (i + next_bits > last) {
129
		/* off end of chunk to be freed */
130
	        break;
131
	    }
132

            
133
66
	    if (i & (next_len - 1)) /* block would not be on boundary */
134
3
	        break;
135

            
136
63
	    bits = next_bits;
137
63
	    len = next_len;
138
	}
139

            
140
	do {
141
27
	    if (i + len <= last && /* off end of chunk to be freed */
142
27
		(i & (len - 1)) == 0) /* block would not be on boundary */
143
27
		break;
144

            
145
	    bits--; len >>=1;
146
	} while (len);
147

            
148
27
	if (len == 0)
149
	    break;
150

            
151
27
	free_bits (pool, i, bits, clear);
152
    }
153
6
}
154

            
155
static struct _cairo_memblock *
156
3
get_buddy (cairo_mempool_t *pool, size_t offset, int bits)
157
{
158
    struct _cairo_memblock *block;
159

            
160
3
    if (offset + (((size_t) 1) << bits) >= pool->num_blocks)
161
3
	return NULL; /* invalid */
162

            
163
    if (BITTEST (pool, offset + (((size_t) 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
3
merge_buddies (cairo_mempool_t *pool,
175
	       struct _cairo_memblock *block,
176
	       int max_bits)
177
{
178
3
    size_t block_offset = block - pool->blocks;
179
3
    int bits = block->bits;
180

            
181
3
    while (bits < max_bits - 1) {
182
	/* while you can, merge two blocks and get a legal block size */
183
3
	size_t buddy_offset = block_offset ^ (((size_t) 1) << bits);
184

            
185
3
	block = get_buddy (pool, buddy_offset, bits);
186
3
	if (block == NULL)
187
3
	    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
3
    block = pool->blocks + block_offset;
199
3
    block->bits = bits;
200
3
    cairo_list_add (&block->link, &pool->free[bits]);
201

            
202
3
    if (bits > pool->max_free_bits)
203
	pool->max_free_bits = bits;
204
3
}
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) ^ (((size_t) 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
3
buddy_malloc (cairo_mempool_t *pool, int bits)
242
{
243
    size_t past, offset;
244
    struct _cairo_memblock *block;
245
    int b;
246

            
247
3
    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
3
    block = NULL;
252
6
    for (b = bits; b <= pool->max_free_bits; b++) {
253
6
	if (! cairo_list_is_empty (&pool->free[b])) {
254
3
	    block = cairo_list_first_entry (&pool->free[b],
255
					    struct _cairo_memblock,
256
					    link);
257
3
	    break;
258
	}
259
    }
260
3
    assert (block != NULL);
261

            
262
3
    cairo_list_del (&block->link);
263

            
264
3
    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
3
    offset = block - pool->blocks;
271
3
    past = offset + (((size_t) 1) << bits);
272
3
    BITSET (pool, past - 1);
273
3
    block->bits = bits;
274

            
275
    /* If we used a larger free block than we needed, free the rest */
276
3
    pool->free_bytes -= ((size_t) 1) << (b + pool->min_bits);
277
3
    free_blocks (pool, past, offset + (((size_t) 1) << b), 0);
278

            
279
3
    return pool->base + ((block - pool->blocks) << pool->min_bits);
280
}
281

            
282
cairo_status_t
283
3
_cairo_mempool_init (cairo_mempool_t *pool,
284
		      void *base, size_t bytes,
285
		      int min_bits, int num_sizes)
286
{
287
    uintptr_t tmp;
288
    int num_blocks;
289
    int i;
290

            
291
    /* Align the start to an integral chunk */
292
3
    tmp = ((uintptr_t) base) & ((((size_t) 1) << min_bits) - 1);
293
3
    if (tmp) {
294
	tmp = (((size_t) 1) << min_bits) - tmp;
295
	base = (char *)base + tmp;
296
	bytes -= tmp;
297
    }
298

            
299
3
    assert ((((uintptr_t) base) & ((((size_t) 1) << min_bits) - 1)) == 0);
300
3
    assert (num_sizes < ARRAY_LENGTH (pool->free));
301

            
302
3
    pool->base = base;
303
3
    pool->free_bytes = 0;
304
3
    pool->max_bytes = bytes;
305
3
    pool->max_free_bits = -1;
306

            
307
3
    num_blocks = bytes >> min_bits;
308
3
    pool->blocks = _cairo_calloc_ab (num_blocks, sizeof (struct _cairo_memblock));
309
3
    if (pool->blocks == NULL)
310
	return _cairo_error (CAIRO_STATUS_NO_MEMORY);
311

            
312
3
    pool->num_blocks = num_blocks;
313
3
    pool->min_bits = min_bits;
314
3
    pool->num_sizes = num_sizes;
315

            
316
99
    for (i = 0; i < ARRAY_LENGTH (pool->free); i++)
317
96
	cairo_list_init (&pool->free[i]);
318

            
319
3
    pool->map = _cairo_malloc ((num_blocks + 7) >> 3);
320
3
    if (pool->map == NULL) {
321
	free (pool->blocks);
322
	return _cairo_error (CAIRO_STATUS_NO_MEMORY);
323
    }
324

            
325
3
    memset (pool->map, -1, (num_blocks + 7) >> 3);
326
3
    clear_bits (pool, 0, num_blocks);
327

            
328
    /* Now add all blocks to the free list */
329
3
    free_blocks (pool, 0, num_blocks, 1);
330

            
331
3
    return CAIRO_STATUS_SUCCESS;
332
}
333

            
334
void *
335
3
_cairo_mempool_alloc (cairo_mempool_t *pool, size_t bytes)
336
{
337
    size_t size;
338
    int bits;
339

            
340
3
    size = ((size_t) 1) << pool->min_bits;
341
33
    for (bits = 0; size < bytes; bits++)
342
30
	size <<= 1;
343
3
    if (bits >= pool->num_sizes)
344
	return NULL;
345

            
346
3
    return buddy_malloc (pool, bits);
347
}
348

            
349
void
350
3
_cairo_mempool_free (cairo_mempool_t *pool, void *storage)
351
{
352
    size_t block_offset;
353
    struct _cairo_memblock *block;
354

            
355
3
    block_offset = ((char *)storage - pool->base) >> pool->min_bits;
356
3
    block = pool->blocks + block_offset;
357

            
358
3
    BITCLEAR (pool, block_offset + ((((size_t) 1) << block->bits) - 1));
359
3
    pool->free_bytes += ((size_t) 1) << (block->bits + pool->min_bits);
360

            
361
3
    merge_buddies (pool, block, pool->num_sizes);
362
3
}
363

            
364
void
365
3
_cairo_mempool_fini (cairo_mempool_t *pool)
366
{
367
3
    free (pool->map);
368
3
    free (pool->blocks);
369
3
}