1/* $Id$ $Revision$ */
2/* vim:set shiftwidth=4 ts=8: */
3
4/*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14#include "vmhdr.h"
15
16/* Method to profile space usage.
17**
18** Written by Kiem-Phong Vo, kpv@research.att.com, 03/23/94.
19*/
20
21#define PFHASH(pf) ((pf)->data.data.hash)
22#define PFVM(pf) ((pf)->data.data.vm)
23#define PFFILE(pf) ((pf)->data.data.fm.file)
24#define PFLINE(pf) ((pf)->line)
25#define PFNAME(pf) ((pf)->data.f)
26#define PFNALLOC(pf) ((pf)->data.data.nalloc)
27#define PFALLOC(pf) ((pf)->data.data.alloc)
28#define PFNFREE(pf) ((pf)->data.data.nfree)
29#define PFFREE(pf) ((pf)->data.data.free)
30#define PFREGION(pf) ((pf)->data.data.region)
31#define PFMAX(pf) ((pf)->data.data.fm.max)
32
33typedef struct _pfdata_s Pfdata_t;
34struct _pfdata_s {
35 Vmulong_t hash; /* hash value */
36 union {
37 char *file; /* file name */
38 Vmulong_t max; /* max busy space for region */
39 } fm;
40 Vmalloc_t *vm; /* region alloc from */
41 Pfobj_t *region; /* pointer to region record */
42 Vmulong_t nalloc; /* number of alloc calls */
43 Vmulong_t alloc; /* amount allocated */
44 Vmulong_t nfree; /* number of free calls */
45 Vmulong_t free; /* amount freed */
46};
47struct _pfobj_s {
48 Pfobj_t *next; /* next in linked list */
49 int line; /* line #, 0 for name holder */
50 union {
51 Pfdata_t data;
52 char f[1]; /* actual file name */
53 } data;
54};
55
56static Pfobj_t **Pftable; /* hash table */
57#define PFTABLE 1019 /* table size */
58static Vmalloc_t *Vmpf; /* heap for our own use */
59
60/**
61 * @param vm region allocating from
62 * @param file the file issuing the allocation request
63 * @param line line number
64 */
65static Pfobj_t *pfsearch(Vmalloc_t * vm, char *file, int line)
66{
67 reg Pfobj_t *pf, *last;
68 reg Vmulong_t h;
69 reg int n;
70 reg char *cp;
71
72 if (!Vmpf && !(Vmpf = vmopen(Vmdcheap, Vmpool, 0)))
73 return NIL(Pfobj_t *);
74
75 /* make hash table; PFTABLE'th slot hold regions' records */
76 if (!Pftable) {
77 if (!
78 (Pftable =
79 (Pfobj_t **) vmalloc(Vmheap,
80 (PFTABLE + 1) * sizeof(Pfobj_t *))))
81 return NIL(Pfobj_t *);
82 for (n = PFTABLE; n >= 0; --n)
83 Pftable[n] = NIL(Pfobj_t *);
84 }
85
86 /* see if it's there with a combined hash value of vm,file,line */
87 h = line + (((Vmulong_t) vm) >> 4);
88 for (cp = file; *cp; ++cp)
89 h += (h << 7) + ((*cp) & 0377) + 987654321L;
90 n = (int) (h % PFTABLE);
91 for (last = NIL(Pfobj_t *), pf = Pftable[n]; pf;
92 last = pf, pf = pf->next)
93 if (PFLINE(pf) == line && PFVM(pf) == vm
94 && strcmp(PFFILE(pf), file) == 0)
95 break;
96
97 /* insert if not there yet */
98 if (!pf) {
99 reg Pfobj_t *fn;
100 reg Pfobj_t *pfvm;
101 reg Vmulong_t hn;
102
103 /* first get/construct the file name slot */
104 hn = 0;
105 for (cp = file; *cp; ++cp)
106 hn += (hn << 7) + ((*cp) & 0377) + 987654321L;
107 n = (int) (hn % PFTABLE);
108 for (fn = Pftable[n]; fn; fn = fn->next)
109 if (PFLINE(fn) < 0 && strcmp(PFNAME(fn), file) == 0)
110 break;
111 if (!fn) {
112 reg size_t s;
113 s = sizeof(Pfobj_t) - sizeof(Pfdata_t) + strlen(file) + 1;
114 if (!(fn = (Pfobj_t *) vmalloc(Vmheap, s)))
115 return NIL(Pfobj_t *);
116 fn->next = Pftable[n];
117 Pftable[n] = fn;
118 PFLINE(fn) = -1;
119 strcpy(PFNAME(fn), file);
120 }
121
122 /* get region record; note that these are ordered by vm */
123 last = NIL(Pfobj_t *);
124 for (pfvm = Pftable[PFTABLE]; pfvm; last = pfvm, pfvm = pfvm->next)
125 if (vm >= PFVM(pfvm))
126 break;
127 if (!pfvm || PFVM(pfvm) > vm) {
128 if (!(pfvm = (Pfobj_t *) vmalloc(Vmpf, sizeof(Pfobj_t))))
129 return NIL(Pfobj_t *);
130 if (last) {
131 pfvm->next = last->next;
132 last->next = pfvm;
133 } else {
134 pfvm->next = Pftable[PFTABLE];
135 Pftable[PFTABLE] = pfvm;
136 }
137 PFNALLOC(pfvm) = PFALLOC(pfvm) = 0;
138 PFNFREE(pfvm) = PFFREE(pfvm) = 0;
139 PFMAX(pfvm) = 0;
140 PFVM(pfvm) = vm;
141 PFLINE(pfvm) = 0;
142 }
143
144 if (!(pf = (Pfobj_t *) vmalloc(Vmpf, sizeof(Pfobj_t))))
145 return NIL(Pfobj_t *);
146 n = (int) (h % PFTABLE);
147 pf->next = Pftable[n];
148 Pftable[n] = pf;
149 PFLINE(pf) = line;
150 PFFILE(pf) = PFNAME(fn);
151 PFREGION(pf) = pfvm;
152 PFVM(pf) = vm;
153 PFNALLOC(pf) = 0;
154 PFALLOC(pf) = 0;
155 PFNFREE(pf) = 0;
156 PFFREE(pf) = 0;
157 PFHASH(pf) = h;
158 } else if (last) { /* do a move-to-front */
159 last->next = pf->next;
160 pf->next = Pftable[n];
161 Pftable[n] = pf;
162 }
163
164 return pf;
165}
166
167static void pfclose(Vmalloc_t * vm)
168{
169 reg int n;
170 reg Pfobj_t *pf, *next, *last;
171
172 /* free all records related to region vm */
173 for (n = PFTABLE; n >= 0; --n) {
174 for (last = NIL(Pfobj_t *), pf = Pftable[n]; pf;) {
175 next = pf->next;
176
177 if (PFLINE(pf) >= 0 && PFVM(pf) == vm) {
178 if (last)
179 last->next = next;
180 else
181 Pftable[n] = next;
182 vmfree(Vmpf, pf);
183 } else
184 last = pf;
185
186 pf = next;
187 }
188 }
189}
190
191static void pfsetinfo(Vmalloc_t * vm, Vmuchar_t * data, size_t size,
192 char *file, int line)
193{
194 reg Pfobj_t *pf;
195 reg Vmulong_t s;
196
197 /* let vmclose knows that there are records for region vm */
198 _Vmpfclose = pfclose;
199
200 if (!file || line <= 0) {
201 file = "";
202 line = 0;
203 }
204
205 if ((pf = pfsearch(vm, file, line))) {
206 PFALLOC(pf) += size;
207 PFNALLOC(pf) += 1;
208 }
209 PFOBJ(data) = pf;
210 PFSIZE(data) = size;
211
212 if (pf) { /* update region statistics */
213 pf = PFREGION(pf);
214 PFALLOC(pf) += size;
215 PFNALLOC(pf) += 1;
216 if ((s = PFALLOC(pf) - PFFREE(pf)) > PFMAX(pf))
217 PFMAX(pf) = s;
218 }
219}
220
221/* sort by file names and line numbers */
222static Pfobj_t *pfsort(Pfobj_t * pf)
223{
224 reg Pfobj_t *one, *two, *next;
225 reg int cmp;
226
227 if (!pf->next)
228 return pf;
229
230 /* partition to two equal size lists */
231 one = two = NIL(Pfobj_t *);
232 while (pf) {
233 next = pf->next;
234 pf->next = one;
235 one = pf;
236
237 if ((pf = next)) {
238 next = pf->next;
239 pf->next = two;
240 two = pf;
241 pf = next;
242 }
243 }
244
245 /* sort and merge the lists */
246 one = pfsort(one);
247 two = pfsort(two);
248 for (pf = next = NIL(Pfobj_t *);;) { /* make sure that the "<>" file comes first */
249 if (PFLINE(one) == 0 && PFLINE(two) == 0)
250 cmp = PFVM(one) > PFVM(two) ? 1 : -1;
251 else if (PFLINE(one) == 0)
252 cmp = -1;
253 else if (PFLINE(two) == 0)
254 cmp = 1;
255 else if ((cmp = strcmp(PFFILE(one), PFFILE(two))) == 0) {
256 cmp = PFLINE(one) - PFLINE(two);
257 if (cmp == 0)
258 cmp = PFVM(one) > PFVM(two) ? 1 : -1;
259 }
260
261 if (cmp < 0) {
262 if (!pf)
263 pf = one;
264 else
265 next->next = one;
266 next = one;
267 if (!(one = one->next)) {
268 if (two)
269 next->next = two;
270 return pf;
271 }
272 } else {
273 if (!pf)
274 pf = two;
275 else
276 next->next = two;
277 next = two;
278 if (!(two = two->next)) {
279 if (one)
280 next->next = one;
281 return pf;
282 }
283 }
284 }
285}
286
287static char *pfsummary(char *buf, Vmulong_t na, Vmulong_t sa,
288 Vmulong_t nf, Vmulong_t sf, Vmulong_t max,
289 Vmulong_t size)
290{
291 buf = (*_Vmstrcpy) (buf, "n_alloc", '=');
292 buf = (*_Vmstrcpy) (buf, (*_Vmitoa) (na, -1), ':');
293 buf = (*_Vmstrcpy) (buf, "n_free", '=');
294 buf = (*_Vmstrcpy) (buf, (*_Vmitoa) (nf, -1), ':');
295 buf = (*_Vmstrcpy) (buf, "s_alloc", '=');
296 buf = (*_Vmstrcpy) (buf, (*_Vmitoa) (sa, -1), ':');
297 buf = (*_Vmstrcpy) (buf, "s_free", '=');
298 buf = (*_Vmstrcpy) (buf, (*_Vmitoa) (sf, -1), ':');
299 if (max > 0) {
300 buf = (*_Vmstrcpy) (buf, "max_busy", '=');
301 buf = (*_Vmstrcpy) (buf, (*_Vmitoa) (max, -1), ':');
302 buf = (*_Vmstrcpy) (buf, "extent", '=');
303 buf = (*_Vmstrcpy) (buf, (*_Vmitoa) (size, -1), ':');
304 }
305 *buf++ = '\n';
306
307 return buf;
308}
309
310/* print profile data */
311int vmprofile(Vmalloc_t * vm, int fd)
312{
313 reg Pfobj_t *pf, *list, *next, *last;
314 reg int n;
315 reg Vmulong_t nalloc, alloc, nfree, free;
316 reg Seg_t *seg;
317 char buf[1024], *bufp, *endbuf;
318#define INITBUF() (bufp = buf, endbuf = buf+sizeof(buf)-128)
319#define CHKBUF() (bufp >= endbuf ? (write(fd,buf,bufp-buf), bufp=buf) : bufp)
320#define FLSBUF() (bufp > buf ? write(fd,buf,bufp-buf) : 0)
321
322 if (fd < 0)
323 return -1;
324
325 /* initialize functions from vmtrace.c that we use below */
326 if ((n = vmtrace(-1)) >= 0)
327 vmtrace(n);
328
329 alloc = free = nalloc = nfree = 0;
330 list = NIL(Pfobj_t *);
331 for (n = PFTABLE - 1; n >= 0; --n) {
332 for (pf = Pftable[n], last = NIL(Pfobj_t *); pf;) {
333 next = pf->next;
334
335 if (PFLINE(pf) < 0 || (vm && vm != PFVM(pf))) {
336 last = pf;
337 goto next_pf;
338 }
339
340 /* remove from hash table */
341 if (last)
342 last->next = next;
343 else
344 Pftable[n] = next;
345
346 /* put on output list */
347 pf->next = list;
348 list = pf;
349 nalloc += PFNALLOC(pf);
350 alloc += PFALLOC(pf);
351 nfree += PFNFREE(pf);
352 free += PFFREE(pf);
353
354 next_pf:
355 pf = next;
356 }
357 }
358
359 INITBUF();
360 bufp = (*_Vmstrcpy) (bufp, "ALLOCATION USAGE SUMMARY", ':');
361 bufp = pfsummary(bufp, nalloc, alloc, nfree, free, 0, 0);
362
363 /* print regions' summary data */
364 for (pf = Pftable[PFTABLE]; pf; pf = pf->next) {
365 if (vm && PFVM(pf) != vm)
366 continue;
367 alloc = 0;
368 for (seg = PFVM(pf)->data->seg; seg; seg = seg->next)
369 alloc += seg->extent;
370 bufp = (*_Vmstrcpy) (bufp, "region", '=');
371 bufp = (*_Vmstrcpy) (bufp, (*_Vmitoa) (VLONG(PFVM(pf)), 0), ':');
372 bufp = pfsummary(bufp, PFNALLOC(pf), PFALLOC(pf),
373 PFNFREE(pf), PFFREE(pf), PFMAX(pf), alloc);
374 }
375
376 /* sort then output detailed profile */
377 list = pfsort(list);
378 for (pf = list; pf;) { /* compute summary for file */
379 alloc = free = nalloc = nfree = 0;
380 for (last = pf; last; last = last->next) {
381 if (strcmp(PFFILE(last), PFFILE(pf)) != 0)
382 break;
383 nalloc += PFNALLOC(pf);
384 alloc += PFALLOC(last);
385 nfree += PFNFREE(last);
386 free += PFFREE(last);
387 }
388 CHKBUF();
389 bufp = (*_Vmstrcpy) (bufp, "file", '=');
390 bufp = (*_Vmstrcpy) (bufp, PFFILE(pf)[0] ? PFFILE(pf) : "<>", ':');
391 bufp = pfsummary(bufp, nalloc, alloc, nfree, free, 0, 0);
392
393 while (pf != last) { /* detailed data */
394 CHKBUF();
395 bufp = (*_Vmstrcpy) (bufp, "\tline", '=');
396 bufp = (*_Vmstrcpy) (bufp, (*_Vmitoa) (PFLINE(pf), -1), ':');
397 bufp = (*_Vmstrcpy) (bufp, "region", '=');
398 bufp =
399 (*_Vmstrcpy) (bufp, (*_Vmitoa) (VLONG(PFVM(pf)), 0), ':');
400 bufp =
401 pfsummary(bufp, PFNALLOC(pf), PFALLOC(pf), PFNFREE(pf),
402 PFFREE(pf), 0, 0);
403
404 /* reinsert into hash table */
405 next = pf->next;
406 n = (int) (PFHASH(pf) % PFTABLE);
407 pf->next = Pftable[n];
408 Pftable[n] = pf;
409 pf = next;
410 }
411 }
412
413 FLSBUF();
414 return 0;
415}
416
417static void *pfalloc(Vmalloc_t * vm, size_t size)
418{
419 reg size_t s;
420 reg void *data;
421 reg char *file;
422 reg int line;
423 reg Vmdata_t *vd = vm->data;
424
425 VMFILELINE(vm, file, line);
426 if (!(vd->mode & VM_TRUST) && ISLOCK(vd, 0))
427 return NIL(void *);
428 SETLOCK(vd, 0);
429
430 s = ROUND(size, ALIGN) + PF_EXTRA;
431 if (!(data = KPVALLOC(vm, s, (*(Vmbest->allocf)))))
432 goto done;
433
434 pfsetinfo(vm, (Vmuchar_t *) data, size, file, line);
435
436 if (!(vd->mode & VM_TRUST) && (vd->mode & VM_TRACE) && _Vmtrace) {
437 vm->file = file;
438 vm->line = line;
439 (*_Vmtrace) (vm, NIL(Vmuchar_t *), (Vmuchar_t *) data, size, 0);
440 }
441 done:
442 CLRLOCK(vd, 0);
443 return data;
444}
445
446static int pffree(Vmalloc_t * vm, void * data)
447{
448 reg Pfobj_t *pf;
449 reg size_t s;
450 reg char *file;
451 reg int line;
452 reg Vmdata_t *vd = vm->data;
453
454 VMFILELINE(vm, file, line);
455
456 if (!data)
457 return 0;
458
459 if (!(vd->mode & VM_TRUST)) {
460 if (ISLOCK(vd, 0))
461 return -1;
462 SETLOCK(vd, 0);
463 }
464
465 if (KPVADDR(vm, data, Vmbest->addrf) != 0) {
466 if (vm->disc->exceptf)
467 (void) (*vm->disc->exceptf) (vm, VM_BADADDR, data, vm->disc);
468 CLRLOCK(vd, 0);
469 return -1;
470 }
471
472 pf = PFOBJ(data);
473 s = PFSIZE(data);
474 if (pf) {
475 PFNFREE(pf) += 1;
476 PFFREE(pf) += s;
477 pf = PFREGION(pf);
478 PFNFREE(pf) += 1;
479 PFFREE(pf) += s;
480 }
481
482 if (!(vd->mode & VM_TRUST) && (vd->mode & VM_TRACE) && _Vmtrace) {
483 vm->file = file;
484 vm->line = line;
485 (*_Vmtrace) (vm, (Vmuchar_t *) data, NIL(Vmuchar_t *), s, 0);
486 }
487
488 CLRLOCK(vd, 0);
489 return (*(Vmbest->freef)) (vm, data);
490}
491
492static void *pfresize(Vmalloc_t * vm, void * data, size_t size,
493 int type)
494{
495 reg Pfobj_t *pf;
496 reg size_t s, news;
497 reg void *addr;
498 reg char *file;
499 reg int line;
500 reg size_t oldsize;
501 reg Vmdata_t *vd = vm->data;
502
503 if (!data) {
504 oldsize = 0;
505 addr = pfalloc(vm, size);
506 goto done;
507 }
508 if (size == 0) {
509 (void) pffree(vm, data);
510 return NIL(void *);
511 }
512
513 VMFILELINE(vm, file, line);
514 if (!(vd->mode & VM_TRUST)) {
515 if (ISLOCK(vd, 0))
516 return NIL(void *);
517 SETLOCK(vd, 0);
518 }
519
520 if (KPVADDR(vm, data, Vmbest->addrf) != 0) {
521 if (vm->disc->exceptf)
522 (void) (*vm->disc->exceptf) (vm, VM_BADADDR, data, vm->disc);
523 CLRLOCK(vd, 0);
524 return NIL(void *);
525 }
526
527 pf = PFOBJ(data);
528 s = oldsize = PFSIZE(data);
529
530 news = ROUND(size, ALIGN) + PF_EXTRA;
531 if ((addr =
532 KPVRESIZE(vm, data, news, (type & ~VM_RSZERO),
533 Vmbest->resizef))) {
534 if (pf) {
535 PFFREE(pf) += s;
536 PFNFREE(pf) += 1;
537 pf = PFREGION(pf);
538 PFFREE(pf) += s;
539 PFNFREE(pf) += 1;
540 pfsetinfo(vm, (Vmuchar_t *) addr, size, file, line);
541 }
542
543 if (!(vd->mode & VM_TRUST) && (vd->mode & VM_TRACE) && _Vmtrace) {
544 vm->file = file;
545 vm->line = line;
546 (*_Vmtrace) (vm, (Vmuchar_t *) data, (Vmuchar_t *) addr, size,
547 0);
548 }
549 } else if (pf) { /* reset old info */
550 PFALLOC(pf) -= s;
551 PFNALLOC(pf) -= 1;
552 pf = PFREGION(pf);
553 PFALLOC(pf) -= s;
554 PFNALLOC(pf) -= 1;
555 file = PFFILE(pf);
556 line = PFLINE(pf);
557 pfsetinfo(vm, (Vmuchar_t *) data, s, file, line);
558 }
559
560 CLRLOCK(vd, 0);
561
562 done:if (addr && (type & VM_RSZERO) && oldsize < size) {
563 reg Vmuchar_t *d = (Vmuchar_t *) addr + oldsize, *ed =
564 (Vmuchar_t *) addr + size;
565 do {
566 *d++ = 0;
567 } while (d < ed);
568 }
569
570 return addr;
571}
572
573static long pfsize(Vmalloc_t * vm, void * addr)
574{
575 return (*Vmbest->addrf) (vm, addr) != 0 ? -1L : (long) PFSIZE(addr);
576}
577
578static long pfaddr(Vmalloc_t * vm, void * addr)
579{
580 return (*Vmbest->addrf) (vm, addr);
581}
582
583static int pfcompact(Vmalloc_t * vm)
584{
585 return (*Vmbest->compactf) (vm);
586}
587
588static void *pfalign(Vmalloc_t * vm, size_t size, size_t align)
589{
590 reg size_t s;
591 reg void *data;
592 reg char *file;
593 reg int line;
594 reg Vmdata_t *vd = vm->data;
595
596 VMFILELINE(vm, file, line);
597
598 if (!(vd->mode & VM_TRUST) && ISLOCK(vd, 0))
599 return NIL(void *);
600 SETLOCK(vd, 0);
601
602 s = (size <= TINYSIZE ? TINYSIZE : ROUND(size, ALIGN)) + PF_EXTRA;
603 if (!(data = KPVALIGN(vm, s, align, Vmbest->alignf)))
604 goto done;
605
606 pfsetinfo(vm, (Vmuchar_t *) data, size, file, line);
607
608 if (!(vd->mode & VM_TRUST) && (vd->mode & VM_TRACE) && _Vmtrace) {
609 vm->file = file;
610 vm->line = line;
611 (*_Vmtrace) (vm, NIL(Vmuchar_t *), (Vmuchar_t *) data, size,
612 align);
613 }
614 done:
615 CLRLOCK(vd, 0);
616 return data;
617}
618
619static Vmethod_t _Vmprofile = {
620 pfalloc,
621 pfresize,
622 pffree,
623 pfaddr,
624 pfsize,
625 pfcompact,
626 pfalign,
627 VM_MTPROFILE
628};
629
630Vmethod_t* Vmprofile = &_Vmprofile;
631