24f4771c2cd568539cedf195414335fad2f97962
[akaros.git] / user / c3po / threads / blocking_graph.c
1 /**
2  *
3  *  Fucntions to gather/manage statistics about nodes in the call graph
4  *
5  **/
6
7 #include "threadlib.h"
8 #include "threadlib_internal.h"
9 #include "blocking_graph.h"
10 #include "util.h"
11
12 #include <unistd.h>
13 #include <stdlib.h>
14 #include <string.h>
15 #include <execinfo.h>
16
17
18 #ifndef DEBUG_blocking_graph_c
19 #undef debug
20 #define debug(...)
21 #undef tdebug
22 #define tdebug(...)
23 #endif
24
25 // Set this to 1 to print thread stats
26 #define PRINT_STAT 0
27
28
29 // external flags, to turn off stats gathering
30 int bg_save_stats = 1;
31 int bg_stats_epoch = 0;
32
33
34 // track the nodes - used for dynamic graph building 
35 // (BG_NODE_TYPE_YIELD and BG_NODE_TYPE_NAMED)
36 static PLHashTable *nodehash = NULL;
37
38
39 // function prototypes
40 PLHashNumber HashPtr(const void *key);
41
42
43 // used to inform the BG routines how they got there...  Set by the IO routines
44 const char *cap_current_syscall;  
45
46 //////////////////////////////////////////////////////////////////////
47 // node list handling
48 //////////////////////////////////////////////////////////////////////
49
50 // dummy node, for threads that don't have a real node yet
51 bg_node_t *bg_dummy_node=NULL;
52 bg_node_t *bg_exit_node=NULL;
53
54 // FIXME: this stuff is horribly non-thread safe!!  There are races
55 // both on bg_maxnode, and (due to realloc) bg_nodelist!!.  Changes to
56 // both should be infrequent, so optomistic concurrency control is
57 // ultimately the way to go.
58
59 // list of nodes
60 int bg_num_nodes = 0;
61 static int bg_nodelist_size = 0;
62 bg_node_t **bg_nodelist = NULL;
63
64 #define BG_NODELIST_INC 100
65
66
67 static inline bg_node_t* bg_newnode(bg_node_type_t type)
68 {
69   bg_node_t* node;
70
71   // allocate the node
72   node = malloc( sizeof(bg_node_t) );
73   assert(node);
74   bzero(node, sizeof(bg_node_t));
75
76   node->type = type;
77   node->node_num = bg_num_nodes++;
78   node->latch = LATCH_INITIALIZER_UNLOCKED;
79
80   // set the system call
81   node->system_call = (cap_current_syscall ? cap_current_syscall : "unknown");
82
83   node->edgehash = PL_NewHashTable(20, HashPtr, PL_CompareValues, PL_CompareValues, NULL, NULL);
84   assert(node->edgehash);
85
86   // allocate list space if necessary
87   if(node->node_num >= bg_nodelist_size) {
88     bg_nodelist = realloc(bg_nodelist, (bg_nodelist_size+BG_NODELIST_INC)*sizeof(bg_node_t*));
89     assert(bg_nodelist);
90     bzero(&bg_nodelist[bg_nodelist_size], BG_NODELIST_INC*sizeof(bg_node_t*));
91     bg_nodelist_size += BG_NODELIST_INC;
92   }
93
94   bg_nodelist[ node->node_num ] = node;
95
96   return node;
97 }
98
99
100
101
102 //////////////////////////////////////////////////////////////////////
103 // blocking graph node management
104 //////////////////////////////////////////////////////////////////////
105
106 static latch_t nodehash_latch = LATCH_INITIALIZER_UNLOCKED;
107
108 /**
109  * add a named node
110  **/
111 void bg_named_set_node(char *file, char *func, int line)
112 {
113   bg_node_t *this_node;
114   static bg_node_t key_node;
115
116   // we skipped a blocking point without actually yielding.  Insert a
117   // yield now.  This both changes how the edges in the graph look,
118   // and ensures that we have enough yields.
119   // 
120   // FIXME: not sure if this is really a good idea!!
121   if( current_thread->curr_stats.node != NULL )
122     thread_yield();
123
124
125   // lock the node hash
126   thread_latch( nodehash_latch );
127
128   key_node.type = BG_NODE_TYPE_NAMED;
129   key_node.u.named.file = file;
130   key_node.u.named.func = func;
131   key_node.u.named.line = line;
132
133   // get the node structure for the current node
134   this_node = PL_HashTableLookup(nodehash, &key_node);
135   if( this_node == NULL ) {
136     this_node = bg_newnode(BG_NODE_TYPE_NAMED);
137
138     this_node->u.named.file = file;
139     this_node->u.named.func = func;
140     this_node->u.named.line = line;
141
142     PL_HashTableAdd(nodehash, this_node, this_node);
143   }
144
145   // unlock the node hash
146   thread_unlatch( nodehash_latch );
147
148   current_thread->curr_stats.node = this_node;
149 }
150
151
152 /**
153  * Add a cil-specified node
154  **/
155 // FIXME: implement this in earnest
156 void bg_cil_set_node(int num)
157 {
158   // we skipped a blocking point without actually yielding.  Insert a
159   // yield now.  This both changes how the edges in the graph look,
160   // and ensures that we have enough yields.
161   // 
162   // FIXME: not sure if this is really a good idea!!
163   if( current_thread->curr_stats.node != NULL )
164     thread_yield();
165
166   // this should have already been initialized
167   current_thread->curr_stats.node = bg_nodelist[ num ];
168 }
169
170
171
172 /**
173  * add a yield point node
174  **/
175 #define MAX_STACK_FRAMES 200
176 void bg_backtrace_set_node()
177 {
178   bg_node_t *this_node;
179   static void* stack[MAX_STACK_FRAMES];
180   static bg_node_t key_node;
181
182   // lock
183   thread_latch( nodehash_latch );
184   
185   // fill in the key node
186   key_node.type = BG_NODE_TYPE_YIELD;
187   key_node.u.yield.stack = stack;
188   key_node.u.yield.numframes = backtrace(stack, MAX_STACK_FRAMES);
189   
190   // look up this stack trace
191   this_node = (bg_node_t*) PL_HashTableLookup(nodehash, &key_node);
192   if(this_node == NULL) {
193     this_node = bg_newnode(BG_NODE_TYPE_YIELD);
194
195     assert( cap_current_syscall ); // so we can find the places that don't set this...
196     
197     this_node->u.yield.numframes = key_node.u.yield.numframes;
198     this_node->u.yield.stack = malloc(sizeof(void*) * key_node.u.yield.numframes); 
199     assert(this_node->u.yield.stack);
200     memcpy(this_node->u.yield.stack, stack, sizeof(void*) * key_node.u.yield.numframes);
201     
202     PL_HashTableAdd(nodehash, this_node, this_node);
203   }
204   
205   // unlock
206   thread_unlatch( nodehash_latch );
207
208   current_thread->curr_stats.node = this_node;
209 }
210
211
212 /**
213  * update the blocking graph node for the current thread.  This also
214  * updates the stats for the node, and the edge just taken.
215  **/
216
217 // keep totals and show averages
218 //#define ADD_STATS(sum,new) (sum += new)
219 //#define AVG_STATS(sum,count) (count > 0 ? (sum/count) : 0)
220
221 // keep a decaying history
222 // FIXME: cheesy hack here to do fixed-point arithmatic.  needs to be un-done on output!!
223 #define ADD_STATS(avg,new) ( avg = (avg==0) ? ((new)<<2) : ((avg*7 + ((new)<<2)) >> 3) )
224 #define AVG_STATS(avg,count) (avg>>2)
225
226
227 void bg_update_stats()
228 {
229   bg_node_t *this_node = current_thread->curr_stats.node;
230   bg_node_t *prev_node = current_thread->prev_stats.node;
231   thread_stats_t *prev_stats = &current_thread->prev_stats;
232   thread_stats_t *curr_stats = &current_thread->curr_stats;
233   bg_edge_t *edge;
234
235   // short circuit, if there's nothing to do.  
236   //
237   // FIXME: need to do epochs or something, so the first set of stats
238   // aren't bogus when we turn things on again.
239
240   // update stats for the current thread
241   bg_set_current_stats( curr_stats );
242
243   // if the prev stats are not from the current epoch, don't add the
244   // info in, as it isn't valid
245   if( prev_stats->epoch != bg_stats_epoch )
246     return;
247   
248
249   // update aggregate stats for the previous node
250   {
251     // NOTE: don't bother latching since the numbers are only updated
252     // here, and it's not that big of a deal if others see slightly
253     // inconsistent data
254
255     prev_node->stats.count++;
256
257     // update the stack usage.  NOTE: the stack grows down, so we subtract the new from the old
258     ADD_STATS(prev_node->stats.stack, prev_stats->stack - curr_stats->stack);
259     
260     // update the total stack numbers as well
261     ADD_STATS(total_stack_in_use, prev_stats->stack - curr_stats->stack);
262     
263     // update the cpu ticks, memory, etc.
264     ADD_STATS(prev_node->stats.cpu_ticks, curr_stats->cpu_ticks - prev_stats->cpu_ticks);
265 #ifdef USE_PERFCTR
266     ADD_STATS(prev_node->stats.real_ticks, curr_stats->real_ticks - prev_stats->real_ticks);
267 #endif // USE_PERFCTR
268     ADD_STATS(prev_node->stats.files, curr_stats->files - prev_stats->files);
269     ADD_STATS(prev_node->stats.sockets, curr_stats->sockets - prev_stats->sockets);
270     ADD_STATS(prev_node->stats.heap, curr_stats->heap - prev_stats->heap);
271   }
272
273   // get the edge structure from prev_node -> this_node
274   {
275     // get or add the edge structure
276     thread_latch( prev_node->latch );
277     edge = PL_HashTableLookup(prev_node->edgehash, this_node);
278     if( edge == NULL ) {
279       edge = malloc( sizeof(bg_edge_t) );
280       assert(edge);
281       bzero(edge, sizeof(bg_edge_t));
282       edge->src  = prev_node;
283       edge->dest = this_node;
284       edge->latch = LATCH_INITIALIZER_UNLOCKED;
285       PL_HashTableAdd(prev_node->edgehash, this_node, edge);
286     }
287     thread_unlatch( prev_node->latch );
288  
289     // update the edge stats.  NOTE: as above, no latch needed
290     {
291       edge->stats.count++;
292       assert( edge->stats.count > 0 );
293       
294       // update the stack usage.  NOTE: the stack grows down, so we subtract the new from the old
295       ADD_STATS(edge->stats.stack, prev_stats->stack - curr_stats->stack);
296       
297       // update the total stack numbers as well
298       ADD_STATS(total_stack_in_use, prev_stats->stack - curr_stats->stack);
299       
300       // update the cpu ticks, memory, etc.
301       ADD_STATS(edge->stats.cpu_ticks, curr_stats->cpu_ticks - prev_stats->cpu_ticks);
302 #ifdef USE_PERFCTR
303       ADD_STATS(edge->stats.real_ticks, curr_stats->real_ticks - prev_stats->real_ticks);
304 #endif
305       ADD_STATS(edge->stats.files, curr_stats->files - prev_stats->files);
306       ADD_STATS(edge->stats.sockets, curr_stats->sockets - prev_stats->sockets);
307       ADD_STATS(edge->stats.heap, curr_stats->heap - prev_stats->heap);
308     }
309   }
310
311
312   // update some global stats
313   update_edge_totals( curr_stats->cpu_ticks - prev_stats->cpu_ticks );
314
315 }
316
317
318
319
320 //////////////////////////////////////////////////////////////////////
321 // printing functions
322 //////////////////////////////////////////////////////////////////////
323
324
325 PRIntn edge_enumerator(PLHashEntry *e, PRIntn i, void *arg)
326 {
327   bg_edge_t *edge = (bg_edge_t*) e->value;
328   bg_node_t *s = edge->src;
329   bg_node_t *d = edge->dest;
330   (void) arg, (void) i;
331
332   // header for this edge
333   switch( edge->src->type ) {
334   case BG_NODE_TYPE_NAMED:
335     output("  %s:%s():%d -> %s:%s():%d", 
336            s->u.named.file, s->u.named.func, s->u.named.line, 
337            d->u.named.file, d->u.named.func, d->u.named.line);
338     break;
339   default: 
340     output("  %3d -> %3d", s->node_num, d->node_num);
341   }
342
343   output("     [ label = \"");
344   output(" num %6d  \\l", edge->stats.count);
345   output(" cpu  %6lld   \\l",  AVG_STATS(edge->stats.cpu_ticks,   edge->stats.count));
346 #ifdef USE_PERFCTR
347   output(" rcpu %6lld   \\l",  AVG_STATS(edge->stats.real_ticks,  edge->stats.count));
348 #endif
349   output(" stak %ld     \\l",  AVG_STATS(edge->stats.stack,       edge->stats.count));
350   output(" heap %ld     \\l",  AVG_STATS(edge->stats.heap,        edge->stats.count)); 
351   output(" sock %d     \\l",   AVG_STATS(edge->stats.sockets,     edge->stats.count)); 
352   output(" file %d     \\l",   AVG_STATS(edge->stats.files,       edge->stats.count)); 
353   //output("       // mutexes/run  %d\n", edge->stats.mutexes / edge->stats.count); 
354   output("\" ");
355   if( edge->stats.stack < 0 )   // FIXME: better heuristic here
356     output(" color=green");
357   output(" ]\n");
358   
359   return 0;
360 }
361
362
363 void dump_blocking_graph(void)
364 {
365   int i;
366
367   output("// blocking graph dump - create graph with dot -Tgif -oOUTFILE INFILE\n");
368   output("digraph foo {\n");
369   output("  ratio=compress\n");
370   output("  margin=\"0,0\"\n");
371   output("  nodesep=0.1\n");
372   output("  ranksep=0.001\n");
373   output("  rankdir=LR\n");
374   output("  ordering=out\n");
375   output("  node [shape=ellipse style=filled fillcolor=\"#e0e0e0\" color=black]\n");
376   output("  node [label=\"\\N\" fontsize=10 height=.1 width=.1]\n");
377   output("  edge [fontsize=7 arrowsize=.8]\n");
378   output("  \n");
379
380   // output the nodes in order, so the graph will be reasonable looking
381   output("  // NODES\n");
382   for(i=0; i<bg_num_nodes; i++) {
383     bg_node_t *node = bg_nodelist[i];
384     if(node->num_here)
385       output("  %3d     [ label=\"\\N:%s - %d\" fontcolor=\"red\" ]\n", 
386              node->node_num, node->system_call, node->num_here);
387     else
388       output("  %3d     [ label=\"\\N:%s\" ]\n", 
389              node->node_num, node->system_call);
390   }
391   output("  \n");
392
393   // now output the edge info
394   output("  // EDGES\n");
395   for(i=0; i<bg_num_nodes; i++) {
396     PL_HashTableEnumerateEntries( bg_nodelist[i]->edgehash, edge_enumerator, NULL);
397   }
398
399   output("}\n\n");
400 }
401
402
403
404 //////////////////////////////////////////////////////////////////////
405 // Utilities for node hash
406 //////////////////////////////////////////////////////////////////////
407
408 PLHashNumber HashPtr(const void *key)
409 {
410   return (((unsigned long) key)>>2) ^ 0x57954317;
411 }
412
413
414 PLHashNumber HashNode(const void *key)
415 {
416   bg_node_t *node = (bg_node_t*) key;
417   switch( node->type ) {
418   case BG_NODE_TYPE_NAMED: 
419     return (((unsigned long) node->u.named.file)>>2) ^ 
420       //(((unsigned long) node->u.named.func)>>2) ^ 
421       (((unsigned long) node->u.named.line)>>2) ^ 
422       0x57954317;
423   case BG_NODE_TYPE_YIELD: {
424     unsigned long ret = 0x57954317;
425     void **s = node->u.yield.stack;
426     int numframes = node->u.yield.numframes;
427     
428     while(numframes > 1) {
429       ret ^= (unsigned long) *s;
430       s++;
431       numframes--;
432     }
433     
434     return ret;
435   }
436
437   case BG_NODE_TYPE_CIL:
438     return node->node_num;
439   default:
440     assert(0);
441   }
442   
443   assert(0);
444   return 0; // never reached
445 }
446
447 PRIntn CompareKeyNodes(const void *v1, const void *v2)
448 {
449   bg_node_t *n1 = (bg_node_t*) v1;
450   bg_node_t *n2 = (bg_node_t*) v2;
451   assert(n1->type == n2->type);
452
453   switch( n1->type ) {
454   case BG_NODE_TYPE_NAMED: 
455     if( n1->u.named.line != n2->u.named.line ) return 0;
456     //if( n1->u.named.func != n2->u.named.func ) return 0;
457     if( n1->u.named.file != n2->u.named.file ) return 0;
458     return 1;
459   case BG_NODE_TYPE_YIELD: {
460     void **s1, **s2;
461     int numframes;
462     
463     // check numframes
464     if( n1->u.yield.numframes != n2->u.yield.numframes ) return 0;
465
466     for(numframes = n1->u.yield.numframes, s1 = n1->u.yield.stack, s2 = n2->u.yield.stack;
467         numframes > 1;
468         s1++, s2++, numframes--) 
469       if(*s1 != *s2) return 0;
470
471     return 1;
472   }
473   case BG_NODE_TYPE_CIL: 
474     return n1->node_num == n2->node_num;
475   default:
476     assert(0);
477   }
478
479   // never reached
480   assert(0);
481   return 0;
482 }
483
484 PRIntn CompareValueNodes(const void *v1, const void *v2)
485 {
486   bg_node_t *n1 = (bg_node_t*) v1;
487   bg_node_t *n2 = (bg_node_t*) v2;
488
489   assert(n1->type == n2->type);
490   return n1->node_num == n2->node_num;
491 }
492
493
494
495 //////////////////////////////////////////////////////////////////////
496 // Initialization
497 //////////////////////////////////////////////////////////////////////
498
499 void init_blocking_graph(void)
500 {
501
502   // allocate the node hash
503   nodehash  = PL_NewHashTable(100, HashNode, CompareKeyNodes, CompareValueNodes, NULL, NULL);
504   assert(nodehash);
505
506   // add the dummy node to the list
507   cap_current_syscall = "thread_create";
508   bg_dummy_node = bg_newnode( BG_NODE_TYPE_DUMMY );
509
510   cap_current_syscall = "thread_exit";
511   bg_exit_node = bg_newnode( BG_NODE_TYPE_DUMMY );
512 }
513