« back to all changes in this revision
Viewing changes to mem.c
- browse files at revision 1
- compare with another revision
- download diff
- download tarball
- view history from revision 1
- Committer: Bazaar Package Importer
- Author(s): Steve McIntyre
- Date: 2006-10-07 13:45:28 UTC
- Revision ID: james.westby@ubuntu.com-20061007134528-o2sucg2g13qkgma7
Tags: upstream-1.0
Import upstream version 1.0
- files added:
- admin
- coverager
- processor
added
removed
mem.c
1
#ifdef TEST
2
#include <limits.h>
3
#include <stdio.h>
4
#else
5
#include <php.h>
6
#endif
7
8
#include <assert.h>
9
#include <stdlib.h>
10
#include <string.h>
11
#include "mem.h"
12
#include "align.h"
13
14
#ifdef TEST
15
# define ALLOC_DEBUG
16
#endif
17
#ifdef ALLOC_DEBUG
18
# define ALLOC_DEBUG_BLOCK_CHECK
19
#endif
20
21
#if 0
22
#undef ALLOC_DEBUG_BLOCK_CHECK
23
#endif
24
25
#define CHAR_PTR(p) ((char *) (p))
26
#define PADD(p, a) (CHAR_PTR(p) + a)
27
#define PSUB(p1, p2) (CHAR_PTR(p1) - CHAR_PTR(p2))
28
29
// {{{ mem
30
struct _xc_block_t {
31
#ifdef ALLOC_DEBUG_BLOCK_CHECK
32
unsigned int magic;
33
#endif
34
xc_memsize_t size; /* reserved even after alloc */
35
xc_block_t *next; /* not used after alloc */
36
};
37
38
struct _xc_mem_t {
39
xc_memsize_t size;
40
xc_memsize_t avail; /* total free */
41
xc_block_t headblock[1]; /* just as a pointer to first block*/
42
};
43
44
#ifndef XtOffsetOf
45
# include <linux/stddef.h>
46
# define XtOffsetOf(s_type, field) offsetof(s_type, field)
47
#endif
48
49
#define SizeOf(type, field) sizeof( ((type *) 0)->field )
50
#define BLOCK_HEADER_SIZE() (ALIGN( XtOffsetOf(xc_block_t, size) + SizeOf(xc_block_t, size) ))
51
52
#define BLOCK_MAGIC ((unsigned int) 0x87655678)
53
54
/* }}} */
55
static inline void xc_block_setup(xc_block_t *b, xc_memsize_t size, xc_block_t *next) /* {{{ */
56
{
57
#ifdef ALLOC_DEBUG_BLOCK_CHECK
58
b->magic = BLOCK_MAGIC;
59
#endif
60
b->size = size;
61
b->next = next;
62
}
63
/* }}} */
64
#ifdef ALLOC_DEBUG_BLOCK_CHECK
65
static void xc_block_check(xc_block_t *b) /* {{{ */
66
{
67
if (b->magic != BLOCK_MAGIC) {
68
fprintf(stderr, "0x%X != 0x%X magic wrong \n", b->magic, BLOCK_MAGIC);
69
}
70
}
71
/* }}} */
72
#else
73
# define xc_block_check(b) do { } while(0)
74
#endif
75
76
77
void *xc_mem_malloc(xc_mem_t *mem, xc_memsize_t size) /* {{{ */
78
{
79
xc_block_t *prev, *cur;
80
xc_block_t *newb, *b;
81
xc_memsize_t realsize;
82
xc_memsize_t minsize;
83
void *p;
84
/* [xc_block_t:size|size] */
85
realsize = BLOCK_HEADER_SIZE() + size;
86
/* realsize is ALIGNed so next block start at ALIGNed address */
87
realsize = ALIGN(realsize);
88
89
#ifdef ALLOC_DEBUG
90
fprintf(stderr, "avail: %d (%dKB). Allocate size: %d realsize: %d (%dKB)"
91
, mem->avail, mem->avail / 1024
92
, size
93
, realsize, realsize / 1024
94
);
95
#endif
96
do {
97
p = NULL;
98
if (mem->avail < realsize) {
99
#ifdef ALLOC_DEBUG
100
fprintf(stderr, " oom\n");
101
#endif
102
break;
103
}
104
105
b = NULL;
106
minsize = INT_MAX;
107
108
/* prev|cur */
109
110
for (prev = mem->headblock; prev->next; prev = cur) {
111
/* while (prev->next != 0) { */
112
cur = prev->next;
113
xc_block_check(cur);
114
if (cur->size == realsize) {
115
/* found a perfect fit, stop searching */
116
b = prev;
117
break;
118
}
119
/* make sure we can split on the block */
120
else if (cur->size > (sizeof(xc_block_t) + realsize) &&
121
cur->size < minsize) {
122
/* cur is acceptable and memller */
123
b = prev;
124
minsize = cur->size;
125
}
126
prev = cur;
127
}
128
129
if (b == NULL) {
130
#ifdef ALLOC_DEBUG
131
fprintf(stderr, " no fit chunk\n");
132
#endif
133
break;
134
}
135
136
prev = b;
137
138
cur = prev->next;
139
p = PADD(cur, BLOCK_HEADER_SIZE());
140
141
/* update the block header */
142
mem->avail -= realsize;
143
144
/* perfect fit, just unlink */
145
if (cur->size == realsize) {
146
prev->next = cur->next;
147
#ifdef ALLOC_DEBUG
148
fprintf(stderr, " perfect fit. Got: %p\n", p);
149
#endif
150
break;
151
}
152
153
/* make new free block after alloced space */
154
155
/* save, as it might be overwrited by newb (cur->size is ok) */
156
b = cur->next;
157
158
/* prev|cur |next=b */
159
160
newb = (xc_block_t *)PADD(cur, realsize);
161
xc_block_setup(newb, cur->size - realsize, b);
162
cur->size = realsize;
163
/* prev|cur|newb|next
164
* `--^
165
*/
166
167
#ifdef ALLOC_DEBUG
168
fprintf(stderr, " -> avail: %d (%dKB). new next: %p offset: %d %dKB. Got: %p\n"
169
, mem->avail, mem->avail / 1024
170
, newb
171
, PSUB(newb, mem), PSUB(newb, mem) / 1024
172
, p
173
);
174
#endif
175
prev->next = newb;
176
/* prev|cur|newb|next
177
* `-----^
178
*/
179
180
} while (0);
181
182
return p;
183
}
184
/* }}} */
185
int xc_mem_free(xc_mem_t *mem, const void *p) /* {{{ return block size freed */
186
{
187
xc_block_t *cur, *b;
188
int size;
189
190
cur = (xc_block_t *) (CHAR_PTR(p) - BLOCK_HEADER_SIZE());
191
#ifdef ALLOC_DEBUG
192
fprintf(stderr, "freeing: %p", p);
193
fprintf(stderr, ", size=%d", cur->size);
194
#endif
195
xc_block_check(cur);
196
assert((char*)mem < (char*)cur && (char*)cur < (char*)mem + mem->size);
197
198
/* find free block right before the p */
199
b = mem->headblock;
200
while (b->next != 0 && b->next < cur) {
201
b = b->next;
202
}
203
204
/* restore block */
205
cur->next = b->next;
206
b->next = cur;
207
size = cur->size;
208
209
#ifdef ALLOC_DEBUG
210
fprintf(stderr, ", avail %d (%dKB)", mem->avail, mem->avail / 1024);
211
#endif
212
mem->avail += size;
213
214
/* combine prev|cur */
215
if (PADD(b, b->size) == (char *)cur) {
216
b->size += cur->size;
217
b->next = cur->next;
218
cur = b;
219
#ifdef ALLOC_DEBUG
220
fprintf(stderr, ", combine prev");
221
#endif
222
}
223
224
/* combine cur|next */
225
b = cur->next;
226
if (PADD(cur, cur->size) == (char *)b) {
227
cur->size += b->size;
228
cur->next = b->next;
229
#ifdef ALLOC_DEBUG
230
fprintf(stderr, ", combine next");
231
#endif
232
}
233
#ifdef ALLOC_DEBUG
234
fprintf(stderr, " -> avail %d (%dKB)\n", mem->avail, mem->avail / 1024);
235
#endif
236
return size;
237
}
238
/* }}} */
239
void *xc_mem_calloc(xc_mem_t *mem, xc_memsize_t memb, xc_memsize_t size) /* {{{ */
240
{
241
xc_memsize_t realsize = memb * size;
242
void *p = xc_mem_malloc(mem, realsize);
243
244
memset(p, 0, realsize);
245
return p;
246
}
247
/* }}} */
248
void *xc_mem_realloc(xc_mem_t *mem, const void *p, xc_memsize_t size) /* {{{ */
249
{
250
void *newp = xc_mem_malloc(mem, size);
251
memcpy(newp, p, size);
252
xc_mem_free(mem, p);
253
return newp;
254
}
255
/* }}} */
256
char *xc_mem_strndup(xc_mem_t *mem, const char *str, xc_memsize_t len) /* {{{ */
257
{
258
void *p = xc_mem_malloc(mem, len + 1);
259
memcpy(p, str, len + 1);
260
return p;
261
}
262
/* }}} */
263
char *xc_mem_strdup(xc_mem_t *mem, const char *str) /* {{{ */
264
{
265
return xc_mem_strndup(mem, str, strlen(str));
266
}
267
/* }}} */
268
269
xc_memsize_t xc_mem_avail(xc_mem_t *mem) /* {{{ */
270
{
271
return mem->avail;
272
}
273
/* }}} */
274
xc_memsize_t xc_mem_size(xc_mem_t *mem) /* {{{ */
275
{
276
return mem->size;
277
}
278
/* }}} */
279
280
const xc_block_t *xc_mem_freeblock_first(xc_mem_t *mem) /* {{{ */
281
{
282
return mem->headblock->next;
283
}
284
/* }}} */
285
const xc_block_t *xc_mem_freeblock_next(const xc_block_t *block) /* {{{ */
286
{
287
return block->next;
288
}
289
/* }}} */
290
xc_memsize_t xc_mem_block_size(const xc_block_t *block) /* {{{ */
291
{
292
return block->size;
293
}
294
/* }}} */
295
xc_memsize_t xc_mem_block_offset(const xc_mem_t *mem, const xc_block_t *block) /* {{{ */
296
{
297
return ((char *) block) - ((char *) mem);
298
}
299
/* }}} */
300
301
xc_mem_t *xc_mem_init(void *ptr, xc_memsize_t size) /* {{{ */
302
{
303
xc_mem_t *mem;
304
xc_block_t *b;
305
306
#define MINSIZE (ALIGN(sizeof(xc_mem_t)) + sizeof(xc_block_t))
307
/* requires at least the header and 1 tail block */
308
if (size < MINSIZE) {
309
fprintf(stderr, "xc_mem_init requires %d bytes at least\n", MINSIZE);
310
return NULL;
311
}
312
mem = (xc_mem_t *) ptr;
313
mem->size = size;
314
mem->avail = size - MINSIZE;
315
316
/* pointer to first block, right after ALIGNed header */
317
b = mem->headblock;
318
xc_block_setup(b, 0, (xc_block_t *) PADD(mem, ALIGN(sizeof(xc_mem_t))));
319
320
/* first block*/
321
b = b->next;
322
xc_block_setup(b, mem->avail, 0);
323
#undef MINSIZE
324
325
return mem;
326
}
327
/* }}} */
328
void xc_mem_destroy(xc_mem_t *mem) /* {{{ */
329
{
330
}
331
/* }}} */
332
333
#ifdef TEST
334
/* {{{ */
335
#undef CHECK
336
#define CHECK(a, msg) do { if ((a) == NULL) { puts(msg); return -1; } } while (0)
337
#include <time.h>
338
339
int main()
340
{
341
int count = 0;
342
void *p;
343
void *memory;
344
xc_mem_t *mem;
345
void **ptrs;
346
int size, i;
347
348
#if 0
349
fprintf(stderr, "%s", "Input test size: ");
350
scanf("%d", &size);
351
#else
352
size = 100;
353
#endif
354
CHECK(memory = malloc(size), "OOM");
355
CHECK(ptrs = malloc(size * sizeof(void*)), "OOM");
356
CHECK(mem = xc_mem_init(memory, size), "Failed init memory allocator");
357
358
while ((p = xc_mem_malloc(mem, 1))) {
359
ptrs[count ++] = p;
360
}
361
fprintf(stderr, "count=%d, random freeing\n", count);
362
srandom(time(NULL));
363
while (count) {
364
i = (random() % count);
365
fprintf(stderr, "freeing %d: ", i);
366
xc_mem_free(mem, ptrs[i]);
367
ptrs[i] = ptrs[count - 1];
368
count --;
369
}
370
371
free(ptrs);
372
free(memory);
373
return 0;
374
}
375
/* }}} */
376
#endif
Loggerhead is a web-based interface for Breezy
Version: 2.0.1