user/tpt/build.c

   1 /*
   2  * $Header: /cvs/sw/new-wave/user/tpt/build.c,v 1.1 2002-02-14 23:04:55 pauli Exp $
   3  * "foo $Revision: 1.1 $ bar"
   4  */
   5
   6 /*
   7  * Build the graph
   8  */
   9
  10 #include <stdio.h>
  11 #include <stdlib.h>
  12 #include <string.h>
  13 #include <assert.h>
  14 #include <ctype.h>
  15 #include <stdarg.h>
  16
  17 #include "tpt.h"
  18
  19 #define BUFSIZE 1000
  20
  21 static int
  22 dprintf(char *fmt, ...)
  23 {
  24         va_list ap;
  25         int ret;
  26
  27         va_start(ap, fmt);
  28         if (DEBUG)
  29                 ret = vprintf(fmt, ap);
  30         else
  31                 ret = 0;
  32         return ret;
  33 }
  34
  35 tpt_node *
  36 make_new_node()
  37 {
  38         tpt_node *ret = (tpt_node *)malloc(sizeof(*ret));
  39         int i;
  40
  41         for (i = 0; i < TIMEPEG_NR_SUCCS; i++)
  42         {
  43                 ret->succs[i].avg_tp = 0;
  44                 ret->succs[i].nr_times = 0;
  45                 ret->succs[i].min_tp = ~0;
  46                 ret->succs[i].max_tp = 0;
  47                 ret->succs[i].succ = 0;
  48         }
  49         ret->next = 0;
  50         ret->name = 0;
  51         ret->nr_succs = 0;
  52         return ret;
  53 }
  54
  55 char *
  56 skipwhite(char *p)
  57 {
  58         while (*p && isspace(*p))
  59                 p++;
  60         return p;
  61 }
  62
  63 static int
  64 line(FILE *f, char *buf, int eofok)
  65 {
  66         char *p;
  67
  68         if (fgets(buf, BUFSIZE, f) == 0)
  69         {
  70                 if (eofok)
  71                         return 0;
  72                 fprintf(stderr, "unexpected EOF\n");
  73                 exit(1);
  74         }
  75
  76         /* Chop trailing newline */
  77         p = buf + strlen(buf);
  78         p--;
  79         if (p >= buf && *p == '\n')
  80                 *p = '\0';
  81
  82         return 1;
  83 }
  84
  85 static void
  86 want(int v1, int v2, const char * const _line)
  87 {
  88         if (v1 != v2)
  89         {
  90                 fprintf(stderr, "error parsing line '%s'\n", _line);
  91                 fprintf(stderr, "expected %d items, got %d\n", v1, v2);
  92                 exit(1);
  93         }
  94 }
  95
  96 typedef struct linebuf
  97 {
  98         char *line;
  99         struct linebuf *next;
 100 } linebuf;
 101
 102 linebuf *
 103 build_linebuf(FILE *f)
 104 {
 105         char buf[1000];
 106         linebuf *lb = 0, *newlb;
 107         linebuf *head = 0;
 108
 109         while (!feof(f))
 110         {
 111                 if (line(f, buf, 1) == 0)
 112                         return head;
 113                 newlb = (linebuf *)malloc(sizeof(*lb));
 114                 newlb->line = strdup(buf);
 115                 if (head == 0)
 116                 {
 117                         head = newlb;
 118                         lb = head;
 119                 }
 120                 else
 121                 {
 122                         lb->next = newlb;
 123                         lb = newlb;
 124                 }
 125         }
 126         return head;
 127 }
 128
 129 tpt_node *
 130 find_node(tpt_node *list, const char * const name)
 131 {
 132         tpt_node *node = list;
 133
 134         while (node)
 135         {
 136                 if (strcmp(node->name, name) == 0)
 137                         break;
 138                 node = node->next;
 139         }
 140         return node;
 141 }
 142
 143 tpt_node *
 144 must_find_node(tpt_node *list, const char * const name)
 145 {
 146         tpt_node *ret = find_node(list, name);
 147         if (ret == 0)
 148         {
 149                 fprintf(stderr, "Internal error; Couldn't locate node `%s'\n", name);
 150                 exit(1);
 151         }
 152         return ret;
 153 }
 154
 155 #define NEXTLB()                                                                \
 156         do {                                                                    \
 157                 if (lb == 0)                                                    \
 158                 {                                                               \
 159                         fprintf(stderr,                                         \
 160                                 "input parsing failed at line %d\n", __LINE__); \
 161                         exit(1);                                                \
 162                 }                                                               \
 163                 lb = lb->next;                                                  \
 164                 if (lb)                                                         \
 165                         dprintf("NEXTLB:%s\n", lb->line);                       \
 166         } while (0)
 167
 168 struct tpt_node *
 169 build_graph(const char * const file_name, unsigned long mhz)
 170 {
 171         FILE *f = fopen(file_name, "r");
 172         int nr_cpus;
 173         struct tpt_node *list = 0;
 174         linebuf *linebufs, *lb;
 175         char buf[400];
 176
 177         if (f == 0)
 178         {
 179                 fprintf(stderr, "can't open '%s'\n", file_name);
 180                 exit(1);
 181         }
 182
 183         line(f, buf, 0);
 184         want(sscanf(buf, "%d", &nr_cpus), 1, buf);
 185
 186
 187         linebufs = build_linebuf(f);
 188         fclose(f);
 189
 190 #if 0
 191         for (lb = linebufs; lb; lb = lb->next)
 192         {
 193                 printf("%s\n", lb->line);
 194         }
 195         printf("DONE\n");
 196 #endif
 197
 198         /* Pass 1: allocate data structures and name them */
 199         lb = linebufs;
 200         while (lb)
 201         {
 202                 tpt_node *new_node;
 203                 int i;
 204                 char namebuf[200];
 205
 206                 new_node = make_new_node();
 207
 208                 if (sscanf(lb->line, " \"%[^\"]\"", namebuf) != 1)
 209                 {
 210                         fprintf(stderr, "tpt: name parsing failed(1) on `%s'\n", lb->line);
 211                         exit(1);
 212                 }
 213                 new_node->name = strdup(namebuf);
 214                 NEXTLB();
 215                 for (i = 0; i < nr_cpus; i++)
 216                 {
 217                         int nr_preds;
 218                         int j;
 219                         int cpu;
 220
 221                         if (sscanf(lb->line, "  cpu%d", &cpu) != 1)
 222                         {
 223                                 fprintf(stderr, "read of CPU field failed on '%s'\n", lb->line);
 224                                 exit(1);
 225                         }
 226
 227                         NEXTLB();               /* CPU identifier */
 228                         if (sscanf(lb->line, "  %d", &nr_preds) != 1)
 229                         {
 230                                 fprintf(stderr, "read of nr_preds failed on '%s'\n", lb->line);
 231                                 exit(1);
 232                         }
 233                         NEXTLB();
 234                         for (j = 0; j < nr_preds; j++)
 235                         {
 236                                 NEXTLB();
 237                         }
 238                 }
 239                 new_node->next = list;
 240                 list = new_node;
 241         }
 242
 243         /* Pass 2: fill in data */
 244
 245         /*
 246          * We do this by visiting each node and filling in its
 247          * predecessor's successor field...
 248          */
 249
 250         lb = linebufs;
 251         while (lb)
 252         {
 253                 tpt_node *node;
 254                 int i;
 255                 char namebuf[200];
 256
 257                 if (sscanf(lb->line, " \"%[^\"]\"", namebuf) != 1)
 258                 {
 259                         fprintf(stderr, "tpt: name parsing failed(2) on `%s'\n", lb->line);
 260                         exit(1);
 261                 }
 262                 node = must_find_node(list, namebuf);
 263                 NEXTLB();               /* Advance to CPU */
 264                 for (i = 0; i < nr_cpus; i++)
 265                 {
 266                         int nr_preds;
 267                         int j;
 268                         int cpu;
 269
 270                         if (sscanf(lb->line, "  cpu%d", &cpu) != 1)
 271                         {
 272                                 fprintf(stderr, "read of CPU field failed on '%s'\n", lb->line);
 273                                 exit(1);
 274                         }
 275                         NEXTLB();               /* CPU identifier */
 276
 277                         sscanf(lb->line, "  %d", &nr_preds);
 278                         NEXTLB();
 279
 280                         for (j = 0; j < nr_preds; j++)
 281                         {
 282                                 unsigned nr_times;
 283                                 unsigned long avglo, avghi, minlo, minhi, maxlo, maxhi;
 284                                 tpt_node *pred;
 285                                 unsigned succ_idx;
 286                                 char predname[200];
 287                                 struct timepeg_arc *arc;
 288                                 int nf;
 289
 290                                 nf = sscanf(    lb->line,
 291                                                 "   \"%[^\"]\" %u %u:%u %u:%u %u:%u",
 292                                                 predname,
 293                                                 &nr_times,
 294                                                 (int *)&avghi, (int *)&avglo,
 295                                                 (int *)&minhi, (int *)&minlo,
 296                                                 (int *)&maxhi, (int *)&maxlo);
 297                                 if (nf != 8)
 298                                 {
 299                                         fprintf(stderr, "error parsing `%s'\n", lb->line);
 300                                         exit(1);
 301                                 }
 302
 303                                 NEXTLB();
 304                                 pred = find_node(list, predname);
 305                                 if (pred == 0)
 306                                 {
 307                                         fprintf(stderr, "tpt: I'm confused\n");
 308                                         exit(1);
 309                                 }
 310
 311                                 /* Does this successor already exist? */
 312                                 arc = 0;
 313                                 for (succ_idx = 0; succ_idx < TIMEPEG_NR_SUCCS; succ_idx++)
 314                                 {
 315                                         if (pred->succs[succ_idx].succ == 0)
 316                                         {       /* Empty slot */
 317                                                 arc = &pred->succs[succ_idx];
 318                                                 assert(node != 0);
 319                                                 assert(pred->nr_succs == succ_idx);
 320                                                 pred->nr_succs++;
 321                                                 arc->succ = node;
 322                                                 break;
 323                                         }
 324                                         else if (pred->succs[succ_idx].succ == node)
 325                                         {       /* Another ref to this node */
 326                                                 arc = &pred->succs[succ_idx];
 327                                                 assert(arc->succ == node);
 328                                                 break;
 329                                         }
 330                                 }
 331
 332                                 if (arc)
 333                                 {
 334                                         timepeg_t avg, min, max;
 335
 336                                         arc->succ = node;
 337                                         arc->nr_times += nr_times;
 338
 339                                         avg = avghi;
 340                                         avg <<= 32;
 341                                         avg += avglo;
 342                                         arc->avg_tp += avg;
 343
 344                                         min = minhi;
 345                                         min <<= 32;
 346                                         min += minlo;
 347                                         if (min < arc->min_tp)
 348                                                 arc->min_tp = min;
 349
 350                                         max = maxhi;
 351                                         max <<= 32;
 352                                         max += maxlo;
 353                                         if (max > arc->max_tp)
 354                                                 arc->max_tp = max;
 355                                 }
 356                                 else
 357                                 {
 358                                         fprintf(stderr, "Internal error: TIMEPEG_NR_SUCCS is too small\n");
 359                                         exit(1);
 360                                 }
 361                         }
 362                 }
 363         }
 364         return list;
 365 }