mem.c 10.6 KB
Newer Older
1 2 3
/* $Id$ $Revision$ */
/* vim:set shiftwidth=4 ts=8: */

ellson's avatar
ellson committed
4 5 6 7 8 9 10 11 12
/*************************************************************************
 * Copyright (c) 2011 AT&T Intellectual Property 
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors: See CVS logs. Details at http://www.graphviz.org/
 *************************************************************************/
13

14
/* Lefteris Koutsofios - AT&T Labs Research */
15 16 17 18 19

#include "common.h"
#include "mem.h"

/* SHORTCUT: the following are imported from tbl.c */
20
extern void Tgchelper (void *), Tfreehelper (void *);
21 22 23 24

#define M_MAXTYPES 6

int Mhaspointers[M_MAXTYPES];
25
int Mgcstate;
26 27 28 29 30 31
int Mcouldgc;

typedef struct buffer_t {
    void *data;
    struct buffer_t *next;
} buffer_t;
32
#define BUFLEN sizeof (buffer_t)
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
static buffer_t *bufferlist;

typedef struct freeobj_t {
    Mheader_t head;
    void *next;
} freeobj_t;
#define FREEOBJSIZE sizeof (freeobj_t)
#define FREESIZE sizeof (void *)
static void **freearray;
static long freen;

#define MARKSIZE sizeof (void *)
#define MARKINCR 100
static void **markarray;
static long markn, marki;

#define OTSIZE sizeof (void *)
#define OTINCR 1000
static void **otarray[2];
static long otn, oti, otj;
static char otarea[2];

static void (*cbfunc) (void);

#define GCINCRSTEPS 4
static int gcsteps = GCINCRSTEPS;

60
#define NUMOFALLOCS 1024
61 62 63 64 65 66 67 68 69 70
static int numofallocs = 0;

#define CALCNUM(size) ((size < 20) ? 1000 : ((size < 200) ? 100 : 1))

#ifdef STATS
static caddr_t origsbrk, finsbrk;
static long objnum, objsiz;
static long typenum[M_MAXTYPES], typesiz[M_MAXTYPES];
#endif

71
static void allocbuffer (long);
72

73
void Minit (void (*func) (void)) {
74 75 76 77

#ifdef STATS
    int i;

78
    origsbrk = (caddr_t) sbrk (0);
79
    for (i = 0; i < M_MAXTYPES; i++)
80
        typenum[i] = typesiz[i] = 0;
81 82
#endif

83
    freearray = Marrayalloc ((long) FREESIZE);
84 85
    freen = 1;
    freearray[0] = NULL;
86
    markarray = Marrayalloc ((long) MARKINCR * MARKSIZE);
87 88
    markn = MARKINCR;
    marki = 0;
89 90
    otarray[0] = Marrayalloc ((long) OTINCR * OTSIZE);
    otarray[1] = Marrayalloc ((long) OTINCR * OTSIZE);
91 92 93 94 95 96 97
    otn = OTINCR;
    oti = otj = 0;
    otarea[0] = 1, otarea[1] = 2;
    cbfunc = func;
    Mcouldgc = FALSE;
}

98
void Mterm (void) {
99 100 101
    buffer_t *bp;

#ifdef STATS
102 103
    finsbrk = (caddr_t) sbrk (0);
    printf ("memory used by data: %ld\n", (long) (finsbrk - origsbrk));
104 105
#endif

106
    Marrayfree (otarray[0]), Marrayfree (otarray[1]);
107 108
    otarray[0] = otarray[1] = NULL;
    otn = otj = oti = 0;
109 110 111 112 113
    Marrayfree (freearray), freearray = NULL, freen = 0;
    Marrayfree (markarray), markarray = NULL, markn = marki = 0;
    for (bp = bufferlist; bp; ) {
        free (bp->data);
        bufferlist = bp, bp = bp->next, free (bufferlist);
114 115 116 117
    }
    bufferlist = NULL;
}

118
void *Mnew (long size, int type) {
119 120
    freeobj_t *fp;

121 122 123
    size = (
        size < FREEOBJSIZE
    ) ? M_BYTE2SIZE (FREEOBJSIZE) : M_BYTE2SIZE (size);
124
    if (size >= freen || !freearray[size]) {
125 126 127 128 129
        allocbuffer (size), numofallocs++;
        if (numofallocs == NUMOFALLOCS)
            Mdogc (M_GCFULL), gcsteps <<= 1, numofallocs = 0;
        else
            Mdogc (M_GCINCR);
130
    } else if (Mgcstate == M_GCON)
131
        Mdogc (M_GCINCR);
132 133
    fp = freearray[size], freearray[size] = fp->next;
    fp->head.type = type;
134
    Mmkcurr (fp);
135 136 137 138 139 140 141 142 143 144
    Mcouldgc = TRUE;

#ifdef STATS
    objnum++, objsiz += size;
    typenum[type]++, typesiz[type] += size;
#endif

    return fp;
}

145
void *Mallocate (long size) {
146 147
    freeobj_t *fp;

148 149 150
    size = (
        size < FREEOBJSIZE
    ) ? M_BYTE2SIZE (FREEOBJSIZE) : M_BYTE2SIZE (size);
151
    if (size >= freen || !freearray[size])
152
        allocbuffer (size);
153 154 155 156
    fp = freearray[size], freearray[size] = fp->next;
    return fp;
}

157
void Mfree (void *p, long size) {
158 159 160 161 162 163 164 165 166 167 168
    freeobj_t *fp;

    fp = p;
    fp->head.size = size;
    fp->head.area = 0;
    fp->head.type = 0;
    fp->next = freearray[fp->head.size], freearray[fp->head.size] = fp;
}

#ifndef FEATURE_MS

169
void *Marrayalloc (long size) {
170 171
    void *p;

172
    if (!(p = malloc (size)))
173
        panic1 (POS, "Marrayallocate", "cannot allocate array");
174 175 176
    return p;
}

177 178
void *Marraygrow (void *p, long size) {
    if (!(p = realloc (p, size)))
179
        panic1 (POS, "Marrayreallocate", "cannot re-allocate array");
180 181 182
    return p;
}

183 184
void Marrayfree (void *p) {
    free (p);
185 186 187 188 189 190 191 192 193
}

#else

static struct arraymap_t {
    HGLOBAL k;
    void *v;
} arraymap[100];

194
void *Marrayalloc (long size) {
195 196 197
    int i;

    for (i = 0; i < 100; i++)
198 199
        if (!arraymap[i].k)
            break;
200
    if (i == 100)
201
        panic1 (POS, "Marrayalloc", "out of space in arraymap");
202
    if (!(arraymap[i].k = GlobalAlloc (GPTR, size)))
203
        panic1 (POS, "Marrayallocate", "cannot allocate array");
204
    arraymap[i].v = GlobalLock (arraymap[i].k);
205 206 207
    return arraymap[i].v;
}

208
void *Marraygrow (void *p, long size) {
209 210 211
    int i;

    for (i = 0; i < 100; i++)
212 213
        if (arraymap[i].v == p)
            break;
214
    if (i == 100)
215
        panic1 (POS, "Marraygrow", "cannot locate pointer");
216
    if (!(arraymap[i].k = GlobalReAlloc (arraymap[i].k, size, GMEM_MOVEABLE)))
217
        panic1 (POS, "Marraygrow", "cannot re-allocate array");
218
    arraymap[i].v = GlobalLock (arraymap[i].k);
219 220 221
    return arraymap[i].v;
}

222
void Marrayfree (void *p) {
223 224 225
    int i;

    for (i = 0; i < 100; i++)
226 227
        if (arraymap[i].v == p)
            break;
228
    if (i == 100)
229
        panic1 (POS, "Marrayfree", "cannot locate pointer");
230 231
    GlobalUnlock (arraymap[i].k);
    GlobalFree (arraymap[i].k);
232 233 234 235 236
    arraymap[i].k = 0;
}

#endif

237
long Mpushmark (void *p) {
238
    if (marki == markn) {
239 240 241 242
        markarray = Marraygrow (
            markarray, (long) (markn + MARKINCR) * MARKSIZE
        );
        markn += MARKINCR;
243 244 245
    }
    markarray[marki++] = p;
    if (Mgcstate == M_GCON)
246
        Mmkcurr (p);
247 248 249
    return marki - 1;
}

250 251 252 253 254
void Mpopmark (long m) {
    if (m >= 0 && m < marki)
        marki = m;
    else
        warning (POS, "Mpopmark", "mark out of range");
255 256
}

257
void Mresetmark (long m, void *p) {
258 259
    markarray[m] = p;
    if (Mgcstate == M_GCON)
260
        Mmkcurr (p);
261 262
}

263 264 265
void Mmkcurr (void *p) {
    if (!p || M_AREAOF (p) == otarea[0])
        return;
266
    if (oti >= otn) {
267 268 269
        otarray[0] = Marraygrow (otarray[0], (long) (otn +OTINCR) * OTSIZE);
        otarray[1] = Marraygrow (otarray[1], (long) (otn +OTINCR) * OTSIZE);
        otn += OTINCR;
270 271 272 273 274
    }
    otarray[0][oti++] = p;
    ((Mheader_t *) p)->area = otarea[0];
}

275
void Mdogc (int gctype) {
276 277 278 279 280 281
    void *p;
    long i;
    char n;
    static long prevoti;

    if (Mgcstate == M_GCOFF) {
282 283 284 285 286 287
        Mgcstate = M_GCON;
        p = otarray[0], otarray[0] = otarray[1], otarray[1] = p;
        n = otarea[0], otarea[0] = otarea[1], otarea[1] = n;
        prevoti = oti, oti = otj = 0;
        for (i = 0; i < marki; i++)
            Mmkcurr (markarray[i]);
288 289
    }
    if (gctype == M_GCFULL) {
290 291 292 293 294 295
        while (otj != oti) {
            p = otarray[0][otj];
            if (Mhaspointers[M_TYPEOF (p)])
                Tgchelper (p);
            otj++;
        }
296
    } else {
297 298 299 300 301 302 303 304
        for (i = 0; i < gcsteps && otj != oti; i++) {
            p = otarray[0][otj];
            if (Mhaspointers[M_TYPEOF (p)])
                Tgchelper (p);
            otj++;
        }
        if (otj < oti)
            return;
305 306
    }
    for (i = 0; i < prevoti; i++) {
307 308 309 310 311 312
        p = otarray[1][i];
        if (p && M_AREAOF (p) == otarea[1]) {
            if (Mhaspointers[M_TYPEOF (p)])
                Tfreehelper (p);
            Mfree (p, (long) ((Mheader_t *) p)->size);
        }
313 314
    }
    if (gctype == M_GCINCR) {
315 316 317 318 319
        if (numofallocs < NUMOFALLOCS / 2) {
            int t = (gcsteps > GCINCRSTEPS) ? gcsteps >>= 1 : GCINCRSTEPS;
	    t = gcsteps;
            numofallocs = 0;
        }
320 321
    }
    if (cbfunc)
322
        (*cbfunc) ();
323 324 325 326
    Mgcstate = M_GCOFF;
    Mcouldgc = FALSE;
}

327
void Mreport (void) {
328 329 330 331 332
    Mheader_t *p;
    long num[M_MAXTYPES], siz[M_MAXTYPES];
    long i, n;
    freeobj_t *fp;

333 334
    Mdogc (M_GCFULL);
    Mdogc (M_GCFULL);
335
    for (i = 0; i < M_MAXTYPES; i++)
336
        num[i] = siz[i] = 0;
337
    for (i = 0; i < oti; i++) {
338 339 340 341 342
        p = otarray[0][i];
        siz[0] += p->size;
        siz[M_TYPEOF (p)] += p->size;
        num[M_TYPEOF (p)]++;
        num[0]++;
343
    }
344
    fprintf (stderr, "live objects:      %8ld (", num[0]);
345
    for (i = 1; i < M_MAXTYPES; i++)
346 347
        fprintf (stderr, "%8ld%s", num[i], (i == M_MAXTYPES - 1) ? "" : ",");
    fprintf (stderr, ")\n       sizes:      %8ld (", siz[0]);
348
    for (i = 1; i < M_MAXTYPES; i++)
349 350 351
        fprintf (stderr, "%8ld%s", siz[i], (i == M_MAXTYPES - 1) ? "" : ",");
    fprintf (stderr, ")\n");
    fprintf (stderr, "free lists: %ld\n", freen);
352
    for (i = 0; i < freen; i++) {
353 354 355 356
        for (n = 0, fp = freearray[i]; fp; fp = fp->next)
            n++;
        if (n > 0)
            fprintf (stderr, "free list: %ld - %ld\n", i, n);
357 358
    }
#ifdef STATS
359
    printf ("objects allocated: %8d (", objnum);
360
    for (i = 1; i < M_MAXTYPES; i++)
361 362
        printf ("%8d%s", typenum[i], (i == M_MAXTYPES - 1) ? "" : ",");
    printf (")\n            sizes: %8d (", objsiz);
363
    for (i = 1; i < M_MAXTYPES; i++)
364 365 366 367
        printf ("%8d%s", typesiz[i], (i == M_MAXTYPES - 1) ? "" : ",");
    printf (")\n");
    finsbrk = (caddr_t) sbrk (0);
    printf ("memory used by data: %ld\n", (long) (finsbrk - origsbrk));
368 369 370
#endif
}

371
static void allocbuffer (long size) {
372 373 374 375 376
    buffer_t *bp;
    char *p;
    long i, bytes, n;

    if (size >= freen) {
377
        if (size > M_SIZEMAX)
378
            panic1 (POS, "allocbuffer", "size %d > max size %d: try rebuilding using -DMINTSIZE", size, M_SIZEMAX);
379 380 381 382
        freearray = Marraygrow (freearray, (long) (size + 1) * FREESIZE);
        for (i = freen; i < size + 1; i++)
            freearray[i] = NULL;
        freen = size + 1;
383
    }
384
    n = CALCNUM (size);
385
    if (!freearray[size]) {
386
        if (!(bp = malloc (BUFLEN)))
387
            panic1 (POS, "allocbuffer", "cannot allocate buffer struct");
388
        if (!(bp->data = malloc (size * M_UNITSIZE * n)))
389
            panic1 (POS, "allocbuffer", "cannot allocate buffer");
390 391 392 393 394 395 396 397 398 399 400 401 402
        bp->next = bufferlist, bufferlist = bp;
        bytes = size * M_UNITSIZE;
        for (i = 0, p = bp->data; i < n - 1; i++, p += bytes) {
            ((freeobj_t *) p)->next = p + bytes;
            ((freeobj_t *) p)->head.size = (Msize_t) size;
            ((freeobj_t *) p)->head.area = 0;
            ((freeobj_t *) p)->head.type = 0;
        }
        ((freeobj_t *) p)->next = NULL;
        ((freeobj_t *) p)->head.size = (Msize_t) size;
        ((freeobj_t *) p)->head.area = 0;
        ((freeobj_t *) p)->head.type = 0;
        freearray[size] = bp->data;
403 404
    }
}