| 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 |
|
|---|
| 7 | jmal(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) |
|
|---|
| 23 | p------------> |------------------------------------------------------------|
|
|---|
| 24 | | space: the memory block |
|
|---|
| 25 | | ... |
|
|---|
| 26 | | ... |
|
|---|
| 27 | |------------------------------------------------------------|
|
|---|
| 28 | | the second checksum |
|
|---|
| 29 | |------------------------------------------------------------|
|
|---|
| 30 | */
|
|---|
| 31 |
|
|---|
| 32 |
|
|---|
| 33 | typedef 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 |
|
|---|
| 50 | static struct jmalloc j_head;
|
|---|
| 51 | static Jmalloc memlist;
|
|---|
| 52 | static int nfree = 0;
|
|---|
| 53 | static int nblocks = 0;
|
|---|
| 54 | static int init = 0;
|
|---|
| 55 | static Jmalloc start;
|
|---|
| 56 | static int free_called = 0;
|
|---|
| 57 | static int malloc_called = 0;
|
|---|
| 58 | static int used_mem = 0;
|
|---|
| 59 | static int free_mem = 0;
|
|---|
| 60 | static int used_blocks = 0;
|
|---|
| 61 | static 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 |
|
|---|
| 83 | dump_core()
|
|---|
| 84 | {
|
|---|
| 85 | memlist->space[0] = 0;
|
|---|
| 86 | }
|
|---|
| 87 |
|
|---|
| 88 | char *set_used(l)
|
|---|
| 89 | Jmalloc 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 |
|
|---|
| 104 | void *malloc(size)
|
|---|
| 105 | int 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 |
|
|---|
| 203 | jmalloc_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 |
|
|---|
| 248 | jmalloc_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 |
|
|---|
| 273 | void free(loc)
|
|---|
| 274 | char *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 |
|
|---|
| 324 | void *realloc(loc, size)
|
|---|
| 325 | char *loc;
|
|---|
| 326 | int 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 |
|
|---|
| 412 | char *calloc(nelem, elsize)
|
|---|
| 413 | int 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 |
|
|---|
| 429 | int mallopt(cmd, value)
|
|---|
| 430 | int cmd, value;
|
|---|
| 431 | {
|
|---|
| 432 | fprintf(stderr, "Mallopt is not defined...\n");
|
|---|
| 433 | exit(1);
|
|---|
| 434 | }
|
|---|
| 435 |
|
|---|
| 436 |
|
|---|
| 437 | jmalloc_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 | }
|
|---|
