-
Notifications
You must be signed in to change notification settings - Fork 0
/
Malloc.c
423 lines (346 loc) · 8.75 KB
/
Malloc.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
/* This file is part of the checked memory manager MALLOC.
Written by Dick Grune, Vrije Universiteit, Amsterdam.
$Id: Malloc.c,v 1.26 2017-12-08 18:07:16 Gebruiker Exp $
*/
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include "any_int.h"
#include "Malloc.h"
/* make malloc.h available */
#undef malloc
#undef calloc
#undef realloc
#undef free
/*Library module source prelude */
#undef _MALLOC_CODE_
#ifndef lint
#define _MALLOC_CODE_
#endif
#ifdef LIB
#define _MALLOC_CODE_
#endif
#ifdef _MALLOC_CODE_
/* Library module source code */
#undef new
#define new use_my_new /* don't call Malloc in Malloc.c */
#define my_new(type) ((type *)malloc(sizeof (type)))
/* All output goes through designated files, so we block printf, etc. */
#undef printf
#define printf use_fprintf
#undef putchar
#define putchar use_fprintf
static size_t restricted_balance = 0; /* to simulate out-of-memory */
/* ADMINISTRATION */
static vlong_uint total = 0;
static vlong_uint balance = 0;
static vlong_uint max = 0;
struct alloc { /* corresponds to an allocated block */
struct alloc *next;
const char *addr;
size_t size;
const char *fname;
int l_nmb;
};
#define HASH_SIZE 16381 /* largest prime under 2^16 */
static struct alloc *alloc_bucket[HASH_SIZE];
#define alloc_bucket_for(x) alloc_bucket[((unsigned int)(x)%HASH_SIZE)]
/* MEMORY STATUS */
struct call { /* summarizes all the allocations at a call in the program */
struct call *next;
const char *fname;
int l_nmb;
unsigned int n_blocks;
int var_size; /* all blocks have the same size or not */
size_t size; /* !var_size: the one size; var_size: sum of sizes */
};
static struct call *
compacted_calls(void) {
struct call *list_of_calls = 0;
int i;
for (i = 0; i < HASH_SIZE; i++) {
struct alloc *al = alloc_bucket[i];
while (al) {
struct call *cl = list_of_calls;
/* try to find a call entry for this program location */
while (cl) {
if ( cl->fname == al->fname
&& cl->l_nmb == al->l_nmb
) break;
cl = cl->next;
}
if (cl) {
/* this is known call; update */
if (cl->var_size) {
cl->size += al->size;
}
else if (cl->size != al->size) {
/* switch to var_size */
cl->var_size = 1;
cl->size =
cl->n_blocks*cl->size + al->size;
}
cl->n_blocks++;
}
else { /* this is a new call */
cl = my_new(struct call);
cl->fname = al->fname;
cl->l_nmb = al->l_nmb;
cl->n_blocks = 1;
cl->var_size = 0;
cl->size = al->size;
/* prepend to list_of_calls */
cl->next = list_of_calls;
list_of_calls = cl;
}
al = al->next;
}
}
return list_of_calls;
}
static int
number_of_calls(const struct call *cl) {
int res = 0;
while (cl != 0) {
res++;
cl = cl->next;
}
return res;
}
static void
fprintloc(FILE *out, const char *fname, int l_nmb) {
fprintf(out, "\"%s\", line %d: ", fname, l_nmb);
}
static void
report_actual_call(FILE *out, const struct call *cl) {
fprintloc(out, cl->fname, cl->l_nmb);
fprintf(out, "still allocated: %d block%s of size ",
cl->n_blocks, (cl->n_blocks == 1 ? "" : "s")
);
if (cl->var_size) {
/* cl->size is the sum of the sizes */
size_t av = (cl->size+cl->n_blocks/2) / cl->n_blocks;
fprintf(out, "%s on average", any_uint2string(av, 0));
if (cl->n_blocks > 1) {
fprintf(out, " = %s", any_uint2string(cl->size, 0));
}
}
else {
/* cl->size is the single size */
fprintf(out, "%s", any_uint2string(cl->size, 0));
if (cl->n_blocks > 1) {
vlong_uint all = cl->size*cl->n_blocks;
fprintf(out, " = %s", any_uint2string(all, 0));
}
}
fprintf(out, "\n");
}
static void
report_actual_calls(FILE *out) {
const struct call *cl = compacted_calls(); /* allocates cl */
int n_calls = number_of_calls(cl);
if (n_calls == 0) return;
fprintf(out, "There %s %d call position%s with unreclaimed memory:\n",
(n_calls == 1 ? "is" : "are"),
n_calls,
(n_calls == 1 ? "" : "s")
);
while (cl) {
report_actual_call(out, cl);
struct call *next_cl = cl->next;
free((void *)cl); /* frees cl */
cl = next_cl;
}
}
void
ReportMemoryStatus(FILE *out) {
if (out == 0) out = stderr;
report_actual_calls(out);
fprintf(out, "Total memory allocated = %s", any_uint2string(total, 0));
fprintf(out, ", max. allocated = %s", any_uint2string(max, 0));
fprintf(out, ", still allocated = %s", any_uint2string(balance, 0));
fprintf(out, "\n");
fflush(out);
}
void /* used in external macros */
_out_of_memory(const char *msg, const char *fname, int l_nmb, size_t size) {
fprintloc(stderr, fname, l_nmb);
fprintf(stderr, "OUT OF MEMORY");
if (msg) {
fprintf(stderr, ": %s", msg);
}
if (size != 0) {
fprintf(stderr, ", requested size = %s bytes",
any_uint2string(size, 0));
}
fprintf(stderr, "\n");
fflush(stderr);
ReportMemoryStatus(stderr);
exit(1);
}
/* MALLOC */
static void
register_alloc(char *addr, size_t size, const char *fname, int l_nmb) {
/* registers the allocation of a block in the administration */
struct alloc *new;
struct alloc **al_hook = &alloc_bucket_for(addr);
if (addr == 0) return;
new = my_new(struct alloc);
new->addr = addr;
new->size = size;
new->fname = fname; /* no need to copy fname */
new->l_nmb = l_nmb;
new->next = *al_hook;
*al_hook = new;
total += size;
balance += size;
if (balance > max) {
max = balance;
}
}
void
MemClobber(void *p, size_t size) {
unsigned char *s = (unsigned char *)p;
size_t i;
for (i = 0; i < size; i++) {
s[i] = 0125; /* 0101 0101 */
}
}
void *
_mreg_malloc(int chk, size_t size, const char *fname, int l_nmb) {
void *res;
if (restricted_balance && balance + size > restricted_balance) {
res = 0;
} else {
res = malloc(size);
}
if (res == 0) {
if (chk) {
_out_of_memory(0, fname, l_nmb, size);
/*NOTREACHED*/
}
return res;
}
register_alloc(res, size, fname, l_nmb);
#ifdef MEMCLOBBER
MemClobber((char *)res, size);
#endif /* MEMCLOBBER */
return res;
}
char *
_new_string(int chk, const char *s, const char *fname, int l_nmb) {
return strcpy((char *)(_mreg_malloc(chk, strlen(s)+1, fname, l_nmb)),
s);
}
/* CALLOC */
void *
_mreg_calloc(int chk, size_t n, size_t size, const char *fname, int l_nmb) {
void *res;
if (restricted_balance && balance + n*size > restricted_balance) {
res = 0;
} else {
res = calloc(n, size);
}
if (res == 0) {
if (chk) {
_out_of_memory(0, fname, l_nmb, n*size);
/*NOTREACHED*/
}
return res;
}
register_alloc(res, n*size, fname, l_nmb);
return res;
}
/* REALLOC */
static struct alloc **
pointer_to_alloc_for(const char *addr) {
struct alloc **al_hook = &alloc_bucket_for(addr);
while (*al_hook) {
if ((*al_hook)->addr == addr) break;
al_hook = &(*al_hook)->next;
}
return al_hook;
}
static size_t
register_free(char *addr) {
/* registers the freeing of a block */
struct alloc **old_p = pointer_to_alloc_for(addr);
struct alloc *old = *old_p;
if (old == 0) return (size_t) -1;
size_t old_size = old->size;
*old_p = old->next;
free((void *)old);
balance -= old_size;
return old_size;
}
void *
_mreg_realloc(int chk, void *addr, size_t size, const char *fname, int l_nmb) {
void *res;
size_t old_size = register_free(addr);
/* we report first, because the realloc() below may cause a crash */
if ( /* we are not reallocating address 0, which is allowed */
addr != 0
&& /* the address was never handed out before */
old_size == (size_t) -1
) {
fprintloc(stderr, fname, l_nmb);
fprintf(stderr, ">>>> unallocated block reallocated <<<<\n");
fflush(stderr);
}
if (restricted_balance && balance + size > restricted_balance) {
res = 0;
} else {
res = realloc(addr, size);
}
if (res == 0) {
if (chk) {
_out_of_memory(0, fname, l_nmb, size);
/*NOTREACHED*/
}
return res;
}
register_alloc(res, size, fname, l_nmb);
#ifdef MEMCLOBBER
if (old_size > 0 && size > old_size) {
MemClobber(((char *)res)+old_size, size-old_size);
}
#endif /* MEMCLOBBER */
return res;
}
/* FREE */
/* ARGSUSED */
void
_mreg_free(void *addr, const char *fname, int l_nmb) {
size_t old_size = register_free(addr);
/* we report first, because the free() below may cause a crash */
if (old_size == (size_t) -1) {
fprintloc(stderr, fname, l_nmb);
fprintf(stderr, ">>>> unallocated block freed ");
fprintf(stderr, "or multiple free of allocated block <<<<\n");
fflush(stderr);
}
else {
#ifdef MEMCLOBBER
MemClobber((char *)addr, old_size);
#endif /* MEMCLOBBER */
}
free(addr);
}
/* End library module source code */
#endif /* _MALLOC_CODE_ */
#ifdef lint
static void
satisfy_lint(void *x) {
void *v;
v = _mreg_malloc(0, 0, 0, 0);
v = _new_string(0, 0, 0, 0);
v = _mreg_calloc(0, 0, 0, 0, 0);
v = _mreg_realloc(0, 0, 0, 0, 0);
_mreg_free(x, 0, 0);
OutOfMemoryExit(0);
ReportMemoryStatus(0);
MemClobber(v, 0);
satisfy_lint(v);
}
#endif /* lint */