1 #include <u.h>
2 #include <libc.h>
3 #include <bio.h>
4
5 void*
emalloc(ulong sz)6 emalloc(ulong sz)
7 {
8 void *v;
9
10 v = malloc(sz);
11 if(v == nil)
12 sysfatal("malloc %lud fails", sz);
13 memset(v, 0, sz);
14 return v;
15 }
16
17 void*
erealloc(void * v,ulong sz)18 erealloc(void *v, ulong sz)
19 {
20 v = realloc(v, sz);
21 if(v == nil)
22 sysfatal("realloc %lud fails", sz);
23 return v;
24 }
25
26 char*
estrdup(char * s)27 estrdup(char* s)
28 {
29 char *r;
30
31 r = strdup(s);
32 if(r == nil)
33 sysfatal("strdup fails");
34 return r;
35 }
36
37 typedef struct Block Block;
38 typedef struct Data Data;
39 struct Block {
40 ulong addr;
41 ulong size;
42 ulong w0;
43 ulong w1;
44 char *s0;
45 char *s1;
46 int mark;
47 int free;
48 Data *d;
49 };
50
51 struct Data {
52 ulong addr;
53 ulong val;
54 uchar type;
55 Block *b;
56 };
57
58 Block *block;
59 uint nblock;
60 uint ablock;
61
62 Data *data;
63 Data *edata;
64 uint ndata;
65 uint adata;
66
67 int
addrcmp(void * va,void * vb)68 addrcmp(void *va, void *vb)
69 {
70 ulong *a, *b;
71
72 a = va;
73 b = vb;
74 if(*a < *b)
75 return -1;
76 if(*a > *b)
77 return 1;
78 return 0;
79 }
80
81 Block*
findblock(ulong addr)82 findblock(ulong addr)
83 {
84 int lo, hi, m;
85
86 lo = 0;
87 hi = nblock;
88
89 while(lo < hi) {
90 m = (lo+hi)/2;
91 if(block[m].addr < addr)
92 lo = m+1;
93 else if(addr < block[m].addr)
94 hi = m;
95 else
96 return &block[m];
97 }
98 return nil;
99 }
100
101 Data*
finddata(ulong addr)102 finddata(ulong addr)
103 {
104 int lo, hi, m;
105
106 lo = 0;
107 hi = ndata;
108
109 while(lo < hi) {
110 m = (lo+hi)/2;
111 if(data[m].addr < addr)
112 lo = m+1;
113 else if(addr < data[m].addr)
114 hi = m;
115 else
116 return &data[m];
117 }
118 if(0 <= lo && lo < ndata)
119 return &data[lo];
120 return nil;
121 }
122
123 int nmark;
124
125 int
markblock(ulong from,ulong fromval,Block * b)126 markblock(ulong from, ulong fromval, Block *b)
127 {
128 Data *d;
129 ulong top;
130 Block *nb;
131
132 USED(from, fromval);
133 //print("trace 0x%.8lux from 0x%.8lux (%d)\n", b->addr, from, b->mark);
134 if(b->free){
135 // fprint(2, "possible dangling pointer *0x%.8lux = 0x%.8lux\n", from, fromval);
136 return 0;
137 }
138 if(b->mark)
139 return 0;
140 b->mark = 1;
141 nmark++;
142
143 if(d = finddata(b->addr)) {
144 assert(d->addr >= b->addr);
145 b->d = d;
146 top = b->addr+b->size;
147 for(; d < edata && d->addr < top; d++) {
148 assert(d->b == 0);
149 d->b = b;
150 if((nb = findblock(d->val-8)) || (nb = findblock(d->val-8-8)))
151 markblock(d->addr, d->val, nb);
152 }
153 return 1;
154 }
155 return 0;
156 }
157
158 enum {
159 AllocColor = 2, // dark blue: completely allocated region
160 HdrColor = 54, // bright blue: region with header
161 LeakColor = 205, // dark red: region with leak
162 LeakHdrColor = 240, // bright red: region with leaked header
163 FreeColor = 252, // bright yellow: completely free region
164 NoColor = 255, // padding, white
165 };
166
167 int
rXr(int as,int ae,int bs,int be)168 rXr(int as, int ae, int bs, int be)
169 {
170 return bs < ae && as < be;
171 }
172
173 void
main(int argc,char ** argv)174 main(int argc, char **argv)
175 {
176 Biobuf bio;
177 char *p, *f[10];
178 int bitmap, c, nf, resolution, n8, n16, hdr, nhdr, nlhdr, nleak, x, y, nb;
179 ulong allocstart, allocend, len, u;
180 Data *d, *ed;
181 Block *b, *eb;
182
183 bitmap = 0;
184 resolution = 8;
185 x = 512;
186 ARGBEGIN{
187 case 'b':
188 bitmap=1;
189 break;
190 case 'r':
191 resolution = atoi(EARGF(sysfatal("usage")));
192 break;
193 case 'x':
194 x = atoi(EARGF(sysfatal("usage")));
195 break;
196 }ARGEND
197
198 n8 = n16 = 0;
199 allocstart = allocend = 0;
200 Binit(&bio, 0, OREAD);
201 while(p=Brdline(&bio, '\n')) {
202 p[Blinelen(&bio)-1] = '\0';
203 nf = tokenize(p, f, nelem(f));
204 if(nf >= 4 && strcmp(f[0], "data") == 0) {
205 if(ndata >= adata){
206 if(adata == 0)
207 adata = 4096;
208 else
209 adata += adata / 4; /* increase 25% */
210 data = erealloc(data, adata * sizeof(Data));
211 }
212 data[ndata].addr = strtoul(f[1], nil, 0);
213 data[ndata].val = strtoul(f[2], nil, 0);
214 data[ndata].type = f[3][0];
215 data[ndata].b = 0;
216 ndata++;
217 }
218 if(nf >= 5 &&
219 (strcmp(f[0], "block") == 0 || strcmp(f[0], "free") == 0)) {
220 if(nblock >= ablock){
221 if(ablock == 0)
222 ablock = 4096;
223 else
224 ablock += ablock / 4; /* increase 25% */
225 block = erealloc(block, ablock * sizeof(Block));
226 }
227 block[nblock].addr = strtoul(f[1], nil, 0);
228 block[nblock].size = strtoul(f[2], nil, 0);
229 block[nblock].w0 = strtoul(f[3], nil, 0);
230 block[nblock].w1 = strtoul(f[4], nil, 0);
231 if (nf >= 7) {
232 block[nblock].s0 = estrdup(f[5]);
233 block[nblock].s1 = estrdup(f[6]);
234 } else {
235 block[nblock].s0 = "";
236 block[nblock].s1 = "";
237 }
238 block[nblock].mark = 0;
239 block[nblock].d = 0;
240 block[nblock].free = strcmp(f[0], "free") == 0;
241 nblock++;
242 }
243 if(nf >= 4 && strcmp(f[0], "range") == 0 && strcmp(f[1], "alloc") == 0) {
244 allocstart = strtoul(f[2], 0, 0)&~15;
245 allocend = strtoul(f[3], 0, 0);
246 }
247 }
248
249 qsort(block, nblock, sizeof(Block), addrcmp);
250 qsort(data, ndata, sizeof(Data), addrcmp);
251
252 ed = edata = data+ndata;
253 for(d=data; d<ed; d++) {
254 if(d->type == 'a')
255 continue;
256 if(b = findblock(d->val-8)) // pool header 2 words
257 n8 += markblock(d->addr, d->val, b);
258 else if(b = findblock(d->val-8-8)) // sometimes malloc header 2 words
259 n16 += markblock(d->addr, d->val, b);
260 else
261 {}//print("noblock %.8lux\n", d->val);
262 }
263
264 Binit(&bio, 1, OWRITE);
265 if(bitmap){
266 if(n8 > n16) // guess size of header
267 hdr = 8;
268 else
269 hdr = 16;
270
271 for(d=data; d<ed; d++)
272 if(d->type=='a')
273 break;
274 if(d==ed)
275 sysfatal("no allocated data region");
276
277 len = (allocend-allocstart+resolution-1)/resolution;
278 y = (len+x-1)/x;
279 Bprint(&bio, "%11s %11d %11d %11d %11d ", "m8", 0, 0, x, y);
280
281 //fprint(2, "alloc %lux %lux x %d y %d res %d\n", allocstart, allocend, x, y, resolution);
282
283 b = block;
284 eb = block+nblock;
285 for(u = allocstart; u<allocend; u+=resolution){
286 //fprint(2, "u %lux %lux baddr %lux\n", u, u+resolution, b->addr);
287 while(b->addr+b->size <= u && b < eb)
288 //{
289 //fprint(2, "\tskip %lux %lux\n", b->addr, b->addr+b->size);
290 b++;
291 //}
292 nhdr = 0;
293 nleak = 0;
294 nb = 0;
295 nlhdr = 0;
296 if(block < b && u < (b-1)->addr+(b-1)->size)
297 b--;
298
299 for(; b->addr < u+resolution && b < eb; b++){
300 //fprint(2, "\tblock %lux %lux %d\n", b->addr, b->addr+b->size, b->mark);
301 if(rXr(b->addr, b->addr+hdr, u, u+resolution)
302 || rXr(b->addr+b->size-8, b->addr+b->size, u, u+resolution)){
303 if(b->mark == 0 && !b->free)
304 nlhdr++;
305 else
306 nhdr++;
307 }
308 if(b->mark == 0 && !b->free)
309 nleak++;
310 nb++;
311 }
312 if(nhdr)
313 c = HdrColor;
314 else if(nlhdr)
315 c = LeakHdrColor;
316 else if(nleak)
317 c = LeakColor;
318 else if(nb)
319 c = AllocColor;
320 else
321 c = FreeColor;
322 //fprint(2, "\t%d\n", c);
323 Bputc(&bio, c);
324 }
325 allocend = allocstart+x*y*resolution;
326 for(; u < allocend; u+=resolution)
327 Bputc(&bio, NoColor);
328 }else{
329 eb = block+nblock;
330 for(b=block; b<eb; b++)
331 if(b->mark == 0 && !b->free)
332 Bprint(&bio, "block 0x%.8lux 0x%.8lux 0x%.8lux 0x%.8lux %s %s\n", b->addr, b->size, b->w0, b->w1, b->s0, b->s1);
333 }
334 Bterm(&bio);
335 exits(nil);
336 }
337