home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 1 / 1497 < prev    next >
Encoding:
Internet Message Format  |  1992-03-01  |  8.9 KB
  1. From: m_mcdonald@vaxa.uwa.oz
  2. Newsgroups: alt.sources
  3. Subject: object module dependancy cycle tool
  4. Message-ID: <1990Jun21.151207.1916@vaxa.uwa.oz>
  5. Date: 21 Jun 90 07:12:07 GMT
  6.  
  7. /*
  8.     This program detects dependency cycles in object modules 
  9.     preventing them being sorted into a standard 1 pass library.
  10.  
  11.         Unlike "lorder *.o | tsort" which does tell you about
  12.     object modules in dependency cycles, cyc.c will explain exactly 
  13.     *which* labels are causing the cycles.
  14.     
  15.         There is perhaps a better way of doing this but I didn't know
  16.     about it when I wrote this and I still don't.
  17.         It's ugly and slow and will probably need mods if you have
  18.     a different  nm.
  19.         However it saved me a lot of time looking for cycles in 
  20.     10 object files where each file had 100-400 external labels. 
  21.     
  22.     If you all know a better way, sorry to be wasting bandwidth,
  23.     mail me and let me know.
  24.                 Matthew McDonald.
  25.  
  26. */
  27. /* 
  28.  * cyc.c - detect causes of dependency cycles in object modules 
  29.  *
  30.  *    and print names of the offending labels.
  31.  *
  32.  *         - Matthew McDonald 19/06/90
  33.  *
  34.  *    *very* nm specific 
  35.  *     - currently only useful for (prime 386) sys V nm
  36.  *    History:
  37.  *
  38.  *
  39.  *
  40.  */
  41.  
  42.  
  43. #include <stdio.h>
  44. #include <string.h>
  45. #include <malloc.h>
  46.  
  47. extern int exit();
  48. extern char *strchr();
  49.  
  50.  
  51. #define MAXOBJECT    120    /* Max object files in dependency cycle */
  52. #define MAXFILENAME    40    /* Max filename size  */
  53. #define MAXLABELS    800    /* # Labels per module we can cope with */
  54. #define COMMANDSIZE    50    /* Size of biggest command we'll make */
  55.  
  56. #define NM_DASH_U_JUNK_LINES    6 /* Number of junk lines in nm -u output */
  57. #define NM_JUNK_LINES        5 /* Number of junk lines in ordinary 
  58.                    * nm output */
  59. #define NMOUTPUTWIDTH    80      /* Assume all nm output <= 80 chars */
  60. #define    SECTION_FIELD    6      /* 'Section' is the 6th field of nm output */
  61. #define NM_FIELD_SEP    '|'      /* nm output field separator */
  62. #define NM_DASH_U_LABEL_START    4
  63.  
  64. char    *progname;                /* argv[0] */
  65. char    objnames[MAXOBJECT][MAXFILENAME];    /* Names of object files */
  66.  
  67. int    num_def[MAXOBJECT];        /* Number of Labels defined */
  68. char    *def_name[MAXOBJECT][MAXLABELS];/* Their names */
  69.  
  70. int    num_req[MAXOBJECT];        /* Number of Labels required */
  71. char    *req_name[MAXOBJECT][MAXLABELS];/* Their names */
  72. int    num_objs;
  73.  
  74. char    dependant[MAXOBJECT][MAXOBJECT];/* Dependancy matrix */
  75.  
  76. char    buffer[NMOUTPUTWIDTH+1];    /* input/error message buffer */
  77.  
  78.  
  79. void fatal(msg)
  80. char    *msg;
  81.     /* Crash out */
  82. {
  83.     fprintf(stderr,"%s: %s\n",progname,msg);
  84.     exit(1);
  85. }
  86.  
  87. char *newstring(size)
  88. int    size;
  89.     /* get a memory for a string - crash on failure */
  90. {
  91.     char *value;
  92.  
  93.     value = malloc(size+1);
  94.     if(!value)
  95.         fatal("out of memory");
  96.  
  97.     return value;
  98. }
  99.  
  100. void junk_nls(str)
  101. char    *str;
  102.     /* Remove trailing '\n's */
  103. {
  104.  
  105.     while(str[strlen(str)-1]=='\n')
  106.         str[strlen(str)-1]=0;
  107. }
  108.  
  109. void get_names()
  110.     /* Get names of object files - quite after "." */
  111. {
  112.     int i;
  113.  
  114.     for(i=1; i<(MAXOBJECT+1); i++){
  115.         scanf("%s",objnames[i]);
  116.         if(!strcmp(objnames[i],"."))
  117.             break;
  118.     }
  119.  
  120.     num_objs = i;
  121. }
  122.  
  123. #ifdef DEBUG
  124.     void print_requireds()
  125.         /* For each object file print required labels - debugging */
  126.     {
  127.         int i, j;
  128.  
  129.  
  130.         for(i=num_objs;--i;){
  131.             printf("File %s needs :\n",objnames[i]);
  132.             for(j=0;j<num_req[i];j++)
  133.                 printf("%d)'%s'\n",j,req_name[i][j]);
  134.         }
  135.     }
  136.  
  137.     void print_defineds()
  138.         /* For each of the files  print defined labels - debugging */
  139.     {
  140.         int i, j;
  141.  
  142.         for(i=num_objs;--i;){
  143.             printf("File %s defines :\n",objnames[i]);
  144.             for(j=0; j <num_def[i]; j++)
  145.                 printf("%d)'%s'\n",j,def_name[i][j]);
  146.         }
  147.     }
  148. #endif 
  149.  
  150. static int first_obj;
  151.  
  152. void print_dependancy(needer, definer)
  153. int needer;
  154. int definer;
  155. {
  156.     int x, y;
  157.  
  158.     for(x=0;x<num_req[needer];x++){
  159. #ifdef DEBUG
  160.         printf("checking %s's required label (%d)%s against:\n",
  161.         objnames[needer],x,req_name[definer][x]);
  162. #endif
  163.         for(y=0;y<num_def[definer];y++){
  164. #ifdef DEBUG
  165.             printf("\t%s's defined label (%d)%s\n",
  166.             objnames[definer],y,def_name[definer][y]);
  167. #endif
  168.             if(!strcmp(req_name[needer][x],def_name[definer][y]))
  169.                 printf("\t%s\n", req_name[needer][x]);
  170.         }
  171.     }
  172. }
  173.  
  174. int check_cycle2(obj)
  175. int    obj;
  176. {
  177.     int i;
  178.  
  179.     /* Detected a cycle, should only happen in check_cycle2()
  180.      * since no object file should depend on itself 
  181.      */
  182.     if(dependant[obj][first_obj]){
  183.         printf("%s depends on %s for label(s)\n",
  184.          objnames[obj],objnames[first_obj]);
  185.         print_dependancy(obj,first_obj);
  186.         return 1;
  187.     }
  188.     for(i=num_objs;--i;)
  189.         if(dependant[obj][i])
  190.             if(check_cycle2(i)){
  191.                 printf("%s depends on %s for label(s):\n",
  192.                  objnames[obj],objnames[i]);
  193.                 print_dependancy(obj,i);
  194.                 return 1;
  195.             }
  196.     /* No cycles */
  197.     return 0;
  198. }
  199.  
  200. int check_cycle(obj)
  201. int    obj;
  202. {
  203.     int i;
  204.  
  205.     first_obj = obj;
  206.  
  207.     /* Detected a cycle, should only happen in check_cycle2()
  208.      * since no object file should depend on itself 
  209.      */
  210.     if(dependant[obj][first_obj]){
  211.         printf("%s depends on %s for label(s):\n",
  212.          objnames[obj],objnames[first_obj]);
  213.         print_dependancy(obj,first_obj);
  214.         fatal("Internal error - object depends on itself");    
  215.     }
  216.  
  217.     for(i=num_objs;--i;)
  218.         if(dependant[obj][i])
  219.             if(check_cycle2(i)){
  220.                 printf("%s depends on %s for label(s):\n",
  221.                  objnames[obj],objnames[i]);
  222.                 print_dependancy(obj,i);
  223.                 return 1;
  224.             }
  225.     /* No cycles */
  226.     return 0;
  227. }
  228.  
  229. void find_dependencies()
  230.     /* Fill in the dependency matrix */
  231. {
  232.     int i, j,x, y;
  233.     
  234.  
  235.     /* Figure out the dependencies of the named files */
  236.     for(i=num_objs;--i;){
  237.         for(j=num_objs;--j;){
  238.         if(i==j)
  239.             /* Nothing requires a label defined by itself */
  240.             continue;
  241.         for(x=0;x<num_req[i];x++){
  242. #ifdef DEBUG
  243.             printf("checking %s's required label (%d)%s against:\n",
  244.             objnames[i],x,req_name[i][x]);
  245. #endif
  246.             for(y=0;y<num_def[j];y++){
  247. #ifdef DEBUG 
  248.             printf("\t%s's defined label (%d)%s\n",
  249.             objnames[j],y,def_name[j][y]);
  250. #endif
  251.             if(!strcmp(req_name[i][x],def_name[j][y])){
  252.                 /* object i depends on object j for req[x] */
  253. #ifdef DEBUG
  254.                 printf(" debug:  %s depends on %s for label %s\n",
  255.                     objnames[i],objnames[j],req_name[i][x]);
  256. #endif
  257.                dependant[i][j]=1;
  258.             }
  259.             }
  260.         }
  261.         }
  262.     }
  263. }
  264.  
  265. void get_required_labels()
  266.     /* For each of the files  get required labels */
  267. {
  268.  
  269.     char command[COMMANDSIZE];
  270.     FILE *instream;
  271.     int i,j;
  272.     int label=0;
  273.  
  274.     
  275.     for(i=num_objs;--i;){
  276.         sprintf(command,"nm -u %s",objnames[i]);
  277.         instream=popen(command,"r");
  278.         if(!instream){
  279.             sprintf(buffer,"could not exec %s\n",command);
  280.             fatal(buffer);
  281.         }
  282.         /* Throw away unwanted nm output */
  283.         for(j=0;j<NM_JUNK_LINES;j++)
  284.             fgets(buffer,NMOUTPUTWIDTH,instream);
  285.         while(fgets(buffer,NMOUTPUTWIDTH,instream)){
  286.             if(label==MAXLABELS)
  287.                 fatal("too many labels in object file");
  288.             junk_nls(buffer);
  289.             req_name[i][label]=newstring(strlen(buffer)-
  290.              NM_DASH_U_LABEL_START);
  291.             strcpy(req_name[i][label],buffer+4);
  292.             label++;
  293.         }
  294.         pclose(instream);
  295.         num_req[i]=label;        
  296.         label = 0;
  297.     }
  298. }
  299.  
  300. char *section_field(str)
  301. char    *str;
  302.     /* Return pointer to 'Section' field of an nm output line */
  303. {
  304.     char *tmp;
  305.     int i;
  306.  
  307.     tmp=strchr(str,NM_FIELD_SEP);
  308.     
  309.     for(i=0; i < (SECTION_FIELD-1); i++)
  310.         tmp=strchr(tmp+1,NM_FIELD_SEP);
  311.  
  312.     return tmp+1;
  313. }
  314.  
  315. int is_definition_section(section)
  316. char *section;
  317.     /* Does this section field mean label is definition or merely a 
  318.      * reference to one */
  319. {
  320.     /* with sys V nm, a '.' in 1st char of the section field virtually
  321.      * gaurantees that the label is defined in this module.
  322.      * Possibly the comparison should be against ".text", ".data", ".bss"
  323.      * and ".common" - but a "." seems to work fine for me.
  324.      */
  325.     return *section=='.';
  326. }
  327.  
  328. char *nm_output_to_label(line)
  329. char    *line;
  330.     /* convert an nm output line to the label contained in it by
  331.      * finding the end of the label making it zero -
  332.      * return the label 
  333.      */    
  334. {
  335.     char    *tmp1, *tmp2;
  336.  
  337.     tmp2 = strchr(buffer,' ');
  338.     tmp1 = strchr(buffer,NM_FIELD_SEP);
  339.     tmp1 = ( (tmp1<tmp2) ? tmp1 : tmp2);
  340.     *tmp1 = 0;
  341.     return line;
  342. }        
  343.  
  344. void get_defined_labels()
  345.     /* For each of the files get defined labels */
  346. {
  347.     char command[COMMANDSIZE];
  348.     FILE *instream;
  349.     int i,j;
  350.     int label=0;
  351.     char *tmp;
  352.  
  353.     for(i=num_objs;--i;){
  354.         sprintf(command,"nm %s",objnames[i]);
  355.         instream=popen(command,"r");
  356.         if(!instream){
  357.             sprintf(buffer,"could not exec %s\n",command);
  358.             fatal(buffer);
  359.         }
  360.         /* Throw away unwanted nm output */
  361.         for(j=0; j<NM_DASH_U_JUNK_LINES; j++)
  362.             fgets(buffer,NMOUTPUTWIDTH,instream);
  363.         while(fgets(buffer,NMOUTPUTWIDTH,instream)){
  364.             if(label==MAXLABELS)
  365.                 fatal("too many labels in object file");
  366.             junk_nls(buffer);
  367.             tmp=section_field(buffer);
  368.             if(is_definition_section(tmp)){
  369.                 tmp = nm_output_to_label(buffer);
  370.                 def_name[i][label]=newstring(strlen(tmp));
  371.                 /* Copy the label to definitions list */
  372.                 strcpy(def_name[i][label++],tmp);
  373.             }
  374.         }
  375.         pclose(instream);
  376.         num_def[i]=label;        
  377.         label = 0;
  378.     }
  379. }
  380.     
  381.  
  382. int main(argc, argv)
  383.     int    argc;
  384.     char    **argv;
  385. {
  386.  
  387.     int i;
  388.  
  389.     /* set up for error messages */
  390.     progname = argv[0];
  391.  
  392.     get_names();
  393.     get_required_labels();
  394. #    ifdef DEBUG
  395.         print_requireds();
  396. #    endif 
  397.     get_defined_labels();
  398. #    ifdef DEBUG
  399.         print_defineds();
  400. #    endif
  401.     find_dependencies();
  402.     for(i=num_objs;--i;)
  403.         if (check_cycle(i))
  404.             exit(0);
  405.     /*not very*/ fatal("no cycles exist\n");
  406.     
  407.     return 0; /* lint */
  408. }
  409.