source: trunk/Jgraph/jmalloc.c @ 606

Last change on this file since 606 was 418, checked in by Nicholas Riley, 12 years ago

Jgraph 8.3 from http://www.cs.utk.edu/~plank/plank/jgraph/jgraph.tar.gz

File size: 11.3 KB
Line 
1#include <stdio.h>
2#include <malloc.h>
3
4/* Each memory block has 8 extra 32-bit values associated with it.  If malloc
5   returns the pointer p to you, the state really looks like:
6
7jmal(p)------>  |------------------------------------------------------------|
8                | flink (next malloc block in absolute order)                |
9                |------------------------------------------------------------|
10                | blink (prev malloc block in absolute order)                |
11                |------------------------------------------------------------|
12                | nextfree (next free malloc block - no particular order)    |
13                |------------------------------------------------------------|
14                | prevfree (next free malloc block - no particular order)    |
15                |------------------------------------------------------------|
16                | size (size of memory allocated)                            |
17                |------------------------------------------------------------|
18                | cs2 (pointer to the second checksum, which is right after  |
19                |   the mem block)                                           |
20                |------------------------------------------------------------|
21                | cs (checksum right before mem block.  used to determine if |
22                |   there is an error of writing around the memory block)    |
23p------------>  |------------------------------------------------------------|
24                | space: the memory block                                    |
25                |                  ...                                       |
26                |                  ...                                       |
27                |------------------------------------------------------------|
28                | the second checksum                                        |
29                |------------------------------------------------------------|
30*/
31
32
33typedef struct jmalloc {
34  struct jmalloc *flink;
35  struct jmalloc *blink;
36  struct jmalloc *nextfree;
37  struct jmalloc *prevfree;
38  int size;
39  int *cs2;
40  int cs;
41  char *space;
42} *Jmalloc;
43
44#define JMSZ (sizeof(struct jmalloc))
45#define PTSZ (sizeof(char *))  /* Also assuming its > sizeof int */
46#define CHUNK_SIZE (16384 - JMSZ)       /* 16K */
47#define MASK 0x17826a9b
48#define JNULL ((Jmalloc) 0)
49
50static struct jmalloc j_head;
51static Jmalloc memlist;
52static int nfree = 0;
53static int nblocks = 0;
54static int init = 0;
55static Jmalloc start;
56static int free_called = 0;
57static int malloc_called = 0;
58static int used_mem = 0;
59static int free_mem = 0;
60static int used_blocks = 0;
61static int free_blocks = 0;
62
63#define cksum(p) (((int) &(p->cs)) - 1)
64#define jloc(l) ((char *) (&l->space))
65#define jmal(l) ((Jmalloc) (((char *)l) - JMSZ + PTSZ))
66#define isfree(l) (l->nextfree != JNULL)
67
68#define do_init() \
69  if (!init) {\
70    memlist = &j_head;\
71    memlist->flink = memlist;\
72    memlist->blink = memlist;\
73    memlist->nextfree = memlist;\
74    memlist->prevfree = memlist;\
75    memlist->size = 0;\
76    memlist->cs = cksum(memlist);\
77    memlist->cs2 = &memlist->cs;\
78    memlist->space = (char *) 0;\
79    start = memlist;\
80    init = 1;\
81  }
82
83dump_core()
84{
85  memlist->space[0] = 0;
86}
87
88char *set_used(l)
89Jmalloc l;
90{
91  start = l->nextfree;
92  l->prevfree->nextfree = l->nextfree;
93  l->nextfree->prevfree = l->prevfree;
94  l->prevfree = JNULL;
95  l->nextfree = JNULL;
96  used_mem += l->size;
97  free_mem -= l->size;
98  used_blocks++;
99  free_blocks--;
100
101  return jloc(l);
102}
103
104void *malloc(size)
105int size;
106{
107  int redo;
108  int done;
109  Jmalloc l;
110  char *tmp;
111  Jmalloc newl;
112  int newsize;
113 
114  do_init();
115  malloc_called++;
116  if (size <= 0) {
117    fprintf(stderr, "Error: Malloc(%d) called\n", size);
118    /* Dump core */
119    dump_core();
120  }
121   
122  if (size % PTSZ != 0) size += PTSZ - (size % PTSZ);
123
124  done = 0;
125  l = start;
126  while(!done) {
127    if (l->size >= size) {
128      done = 1;
129      redo = 0;
130    } else {
131      l = l->nextfree;
132      done = (l == start);
133      redo = done;
134    } 
135  }
136     
137  if (redo) {
138    if (size > CHUNK_SIZE) 
139      newsize = size + JMSZ; 
140      else newsize = CHUNK_SIZE + JMSZ;
141    newl = (Jmalloc) sbrk(newsize);
142    while (newl == (Jmalloc) -1 && newsize > size + JMSZ) {
143      newsize /= 2;
144      if (newsize < size + JMSZ) newsize = size + JMSZ;
145      newl = (Jmalloc) sbrk(newsize);
146    }
147     
148    if (newl == (Jmalloc) -1) {
149/*       fprintf(stderr, "Jmalloc: out of memory\n"); */
150/*       fprintf(stderr, "Used bytes = %d, Free bytes = %d\n",  */
151/*               used_mem, free_mem); */
152/*       fprintf(stderr, "Trying to get %d bytes (chunk of %d)\n",  */
153/*               size, newsize); */
154      return NULL;
155    }
156    newl->flink = memlist;
157    newl->blink = memlist->blink;
158    newl->flink->blink = newl;
159    newl->blink->flink = newl;
160    newl->nextfree = memlist;
161    newl->prevfree = memlist->prevfree;
162    newl->nextfree->prevfree = newl;
163    newl->prevfree->nextfree = newl;
164    newl->size = ((char *) sbrk(0)) - jloc(newl) - PTSZ;
165    free_mem += newl->size;
166    newl->cs = cksum(newl);
167    newl->cs2 = ((int *) (jloc(newl) + newl->size));
168    *(newl->cs2) = cksum(newl);
169    if(newl->size < size) {
170      fprintf(stderr, "Newl->size(%d) < size(%d)\n", newl->size, size);
171      exit(1);
172    }
173    free_blocks++;
174    l = newl;
175  } 
176
177  if (l->size - size < JMSZ) {
178    return set_used(l);
179  } else {
180    tmp = jloc(l);
181    newl = (Jmalloc) (tmp + size + PTSZ);
182    newl->flink = l->flink;
183    newl->blink = l;
184    newl->flink->blink = newl;
185    newl->blink->flink = newl;
186    newl->nextfree = l->nextfree;
187    newl->prevfree = l;
188    newl->nextfree->prevfree = newl;
189    newl->prevfree->nextfree = newl;
190    newl->size = l->size - size - JMSZ;
191    newl->cs = cksum(newl);
192    newl->cs2 = (int *) (jloc(newl) + newl->size);
193    *(newl->cs2) = cksum(newl);
194    free_mem += size + newl->size - l->size;
195    free_blocks++;
196    l->size = size;
197    l->cs2 = ((int *) (jloc(l) + l->size));
198    *(l->cs2) = cksum(l);
199    return set_used(l);
200  }
201}
202
203jmalloc_print_mem()
204{
205  Jmalloc l;
206  int done;
207  char *bufs[100];
208  int sizes[100];
209  int mc;
210  int fc;
211  int i, j;
212
213  do_init();
214  mc = malloc_called;
215  fc = free_called;
216  if (jmal(jloc(memlist)) != memlist) {
217    fprintf(stderr, "TROUBLE: memlist=0x%x, jmal(jloc(memlist))=0x%x)\n",
218            memlist, jmal(jloc(memlist)));
219    exit(1);
220  }
221  done = 0;
222  l = start;
223  i = 0;
224  while (!done) {
225    if (cksum(l) != l->cs) {
226      printf("Memory location 0x%x corrupted\n", jloc(l));
227      exit(1);
228    } else if (cksum(l) != *(l->cs2)) {
229      printf("Memory location 0x%x corrupted\n", jloc(l));
230      exit(1);
231    }
232   
233    bufs[i] = jloc(l);
234    sizes[i] = l->size;
235    if (l->nextfree == 0) sizes[i] = -sizes[i];
236    i++;
237    l = l->flink;
238    done = ((l == start) || i >= 100);
239  }
240  printf("Malloc called %d times\n", mc);
241  printf("Free called %d times\n", fc);
242  for (j = 0; j < i; j++) {
243    printf("Loc = 0x%x, size = %d, free = %d\n", bufs[j], 
244           (sizes[j] > 0) ? sizes[j] : -sizes[j], (sizes[j] >= 0));
245  }
246}
247
248jmalloc_check_mem()
249{
250  Jmalloc l;
251  int done;
252
253  done = 0;
254
255  l = start;
256
257  while (!done) {
258    if (cksum(l) != l->cs) {
259      fprintf(stderr, "Memory chunk violated: 0x%x: %s 0x%x.  %s 0x%x\n", 
260              jloc(l), "Checksum 1 is ", l->cs, "It should be", cksum(l));
261      dump_core();
262    } else if (cksum(l) != *(l->cs2)) {
263      fprintf(stderr, "Memory chunk violated: 0x%x: %s 0x%x.  %s 0x%x\n", 
264              jloc(l), "Checksum 2 is ", *(l->cs2), "It should be", cksum(l));
265      dump_core();
266    }
267    l = l->flink;
268    done = (l == start);
269  }
270}
271
272 
273void free(loc)
274char *loc;
275{
276  Jmalloc l;
277  Jmalloc pl, nl;
278
279  do_init();
280  free_called++;
281  l = jmal(loc); 
282
283  if (cksum(l) != l->cs) {
284    fprintf(stderr, "Error on free: memory chunk violated: 0x%x\n", loc);
285    dump_core();
286  } else if (cksum(l) != *(l->cs2)) {
287    fprintf(stderr, "Error on free: memory chunk violated: 0x%x\n", loc);
288    dump_core();
289  }
290
291  used_mem -= l->size;
292  free_mem += l->size;
293  free_blocks++;
294  used_blocks--;
295
296  pl = l->blink;
297  nl = l->flink;
298  if (isfree(pl) && (jloc(pl)+pl->size + PTSZ == (char *) l)) {
299    free_mem += JMSZ;
300    pl->size += l->size + JMSZ;
301    pl->flink = nl;
302    pl->flink->blink = pl;
303    l = pl;
304    free_blocks--;
305  } else {
306    l->prevfree = start;
307    l->nextfree = start->nextfree;
308    l->nextfree->prevfree = l;
309    l->prevfree->nextfree = l;
310  }
311
312  if (isfree(nl) && jloc(l)+l->size + PTSZ == (char *) nl) {
313    free_mem += JMSZ;
314    l->size += nl->size + JMSZ;
315    l->flink = nl->flink;
316    l->flink->blink = l;
317    free_blocks--;
318    nl->nextfree->prevfree = nl->prevfree;
319    nl->prevfree->nextfree = nl->nextfree;
320  }
321  start = l;
322}
323
324void *realloc(loc, size)
325char *loc;
326int size;
327{
328  Jmalloc l;
329  Jmalloc l2, nl;
330  char *loc2;
331  int i;
332  Jmalloc newl;
333
334
335  do_init();
336
337  if (size <= 0) {
338    fprintf(stderr, "Error: Malloc(%d) called\n", size);
339    /* Dump core */
340    dump_core();
341  }
342   
343  if (size % PTSZ != 0) size += PTSZ - (size % PTSZ);
344
345  l = jmal(loc); 
346
347  if (cksum(l) != l->cs) {
348    fprintf(stderr, "Error on realloc: memory chunk violated: 0x%x\n", loc);
349    dump_core();
350  } else if (cksum(l) != *(l->cs2)) {
351    fprintf(stderr, "Error on realloc: memory chunk violated: 0x%x\n", loc);
352    dump_core();
353  }
354
355  if (size < l->size) {
356    if (l->size - size < JMSZ + 4) return loc;
357    newl = (Jmalloc) (loc + size + PTSZ);
358    newl->flink = l->flink;
359    newl->blink = l;
360    newl->flink->blink = newl;
361    newl->blink->flink = newl;
362    newl->nextfree = start->nextfree;
363    newl->prevfree = start;
364    newl->nextfree->prevfree = newl;
365    newl->prevfree->nextfree = newl;
366    newl->size = l->size - size - JMSZ;
367    newl->cs = cksum(newl);
368    newl->cs2 = (int *) (jloc(newl) + newl->size);
369    *(newl->cs2) = cksum(newl);
370    used_mem += size - l->size;
371    free_mem += newl->size;
372    free_blocks++;
373    l->size = size;
374    l->cs2 = ((int *) (jloc(l) + l->size));
375    *(l->cs2) = cksum(l);
376    start = newl;
377    return loc;
378  }
379
380
381  nl = l->flink;
382
383  if (isfree(nl) && (jloc(l)+l->size + PTSZ == (char *) nl) &&
384      l->size + JMSZ + nl->size >= size) {
385    start = nl;
386    i = size - l->size - JMSZ;
387    if (i < 0) i = 4;
388    loc2 = malloc(i);
389    l2 = jmal(loc2);
390    if (l2 != nl) {
391      fprintf(stderr, "Realloc internal error: l2 != nl\n");
392      dump_core();
393    }
394
395    nl->flink->blink = nl->blink;
396    nl->blink->flink = nl->flink;
397    free_mem -= nl->size;
398    used_mem += nl->size + JMSZ;
399    free_blocks--;
400    l->size += nl->size + JMSZ;
401    l->cs2 = ((int *) (jloc(l) + l->size));
402    *(l->cs2) = cksum(l);
403    return loc;
404  } else {
405    loc2 = malloc(size);
406    for (i = 0; i < l->size; i++) loc2[i] = loc[i];
407    free(loc);
408    return loc2;
409  }
410}
411
412char *calloc(nelem, elsize)
413int nelem, elsize;
414{
415  int *iptr;
416  char *ptr;
417  int sz;
418  int i;
419
420  sz = nelem*elsize;
421  ptr = malloc(sz);
422  iptr = (int *) ptr;
423 
424  for (i = 0; i < sz/sizeof(int); i++) iptr[i] = 0;
425  for (i = i * sizeof(int); i < sz; i++) ptr[i] = 0;
426  return ptr;
427}
428
429int mallopt(cmd, value)
430int cmd, value;
431{
432  fprintf(stderr, "Mallopt is not defined...\n");
433  exit(1);
434}
435
436
437jmalloc_usage()
438{
439  fprintf(stderr, "Jmalloc: %d %s %d block%s. %d %s %d block%s\n",
440                    used_mem, "bytes used in", used_blocks, 
441                    (used_blocks == 1) ? "" : "s", 
442                    free_mem, "bytes free in", free_blocks,
443                    (free_blocks == 1) ? "" : "s");
444}
Note: See TracBrowser for help on using the repository browser.