home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS 1992 June / SIMTEL_0692.cdr / msdos / pgmutl / val_link.arc / LIBRARY.C < prev    next >
Text File  |  1989-02-18  |  13KB  |  308 lines
  1. /*                                 LIBRARY.C                               */
  2.  
  3. /*+-------------------------------------------------------------------------+
  4.   |                                                                         |
  5.   |                            process_libraries                            |
  6.   |                                                                         |
  7.   +-------------------------------------------------------------------------+*/
  8. void process_libraries()
  9. BeginDeclarations
  10. file_info_ptr                          current_lib_file_info;
  11. EndDeclarations
  12. BeginCode
  13.  library_processing_start_time = Now;
  14.  While library_request_count Exceeds 0
  15.   BeginWhile
  16.    TraverseList(lib_file_list, current_lib_file_info)
  17.     BeginTraverse
  18.      process_library(current_lib_file_info);
  19.     EndTraverse;
  20.   EndWhile;
  21.  write_temp_file(0, Null, 0, 0, 0);
  22.  file_close_for_write();
  23.  return;
  24. EndCode
  25.  
  26. /*+-------------------------------------------------------------------------+
  27.   |                                                                         |
  28.   |                            process_library                              |
  29.   |                                                                         |
  30.   +-------------------------------------------------------------------------+*/
  31. void process_library(file_info_ptr lib_file)
  32. BeginDeclarations
  33. #define Lib_file                       (*lib_file)
  34. bit_32                                 pos;
  35. public_entry_ptr                       pub;
  36. #define Pub                            (*pub)
  37. EndDeclarations
  38. BeginCode
  39.  While Lib_file.request_count Exceeds 0
  40.   BeginWhile
  41.    file_open_for_read(lib_file);
  42.    Lib_file.pass_count++;
  43.    TraverseList(Lib_file.external_list, pub)
  44.     BeginTraverse
  45.      LoopIf((Pub.type_entry IsNot public_in_library) OrIf
  46.             (Not Pub.Library.requested));
  47.      pos = Bit_32(Pub.Library.page) * Bit_32(Lib_file.page_size);
  48.      file_position(pos);
  49.      Lib_file.module_count++;
  50.      obj_tmodule();
  51.      If Pub.type_entry IsNot internal
  52.       Then
  53.        linker_error(12, "Library directory error:\n"
  54.                         "\tLibrary:  \"%Fs\"\n"
  55.                         "\t Module:  \"%Fs\"\n"
  56.                         "\t Offset:  %lu\n"
  57.                         "\t  Error:  Above module did not resolve \"%Fs\"\n"
  58.                         "\t          when the library directory indicated it "
  59.                                      "would.\n",
  60.                         Lib_file.filename,
  61.                         (*tmodule_name).symbol,
  62.                         pos,
  63.                         Pub.symbol);
  64.       EndIf;
  65.     EndTraverse;
  66.    file_close_for_read();
  67.   EndWhile;
  68.  return;
  69. EndCode
  70. #undef Lib_file
  71. #undef Pub
  72.  
  73. /*+-------------------------------------------------------------------------+
  74.   |                                                                         |
  75.   |                       process_library_directories                       |
  76.   |                                                                         |
  77.   +-------------------------------------------------------------------------+*/
  78. void process_library_directories()
  79. BeginDeclarations
  80. file_info_ptr                          current_lib_file_info;
  81. EndDeclarations
  82. BeginCode
  83.  library_directory_start_time = Now;
  84.  public_sort_array = (public_entry_ptr_array)
  85.                        allocate_memory
  86.                         (Addr(dynamic_pool),
  87.                          Bit_32(sizeof(public_entry_ptr)) *
  88.                           Bit_32(MAX_PUBLICS_IN_LIBRARY));
  89.  TraverseList(lib_file_list, current_lib_file_info)
  90.   BeginTraverse
  91.    process_library_directory(current_lib_file_info);
  92.   EndTraverse;
  93.  release_pool(Addr(dynamic_pool));
  94.  return;
  95. EndCode
  96.  
  97. /*+-------------------------------------------------------------------------+
  98.   |                                                                         |
  99.   |                        process_library_directory                        |
  100.   |                                                                         |
  101.   +-------------------------------------------------------------------------+*/
  102. void process_library_directory(file_info_ptr lib_file)
  103. BeginDeclarations
  104. #define Lib_file                       (*lib_file)
  105. bit_16                                 entry_number;
  106. bit_16                                 current_block;
  107. library_directory_ptr                  directory_page;
  108. #define Directory_page                 (*directory_page)
  109. library_file_header_ptr                lib_hdr;
  110. #define Lib_hdr                        (*lib_hdr)
  111. bit_16                                 n_directory_blocks;
  112. public_entry_ptr                       pub;
  113. #define Pub                            (*pub)
  114. public_entry_ptr_array                 public_array;
  115. library_symbol_entry_ptr               symbol;
  116. bit_16                                 symbol_count;
  117. bit_16                                 symbol_index;
  118. #define Symbol                         (*symbol)
  119. bit_16                                *symbol_in_page;
  120. #define Symbol_in_page                 (*symbol_in_page)
  121. EndDeclarations
  122. BeginCode
  123.  lib_hdr = (library_file_header_ptr) object_file_element;
  124.  file_open_for_read(lib_file);
  125.  file_IO_limit(sizeof(library_file_header_type));
  126.  file_read(object_file_element, sizeof(library_file_header_type));
  127.  If Lib_hdr.flag IsNot 0xF0
  128.   Then
  129.    linker_error(4,"File \"%Fs\" is not in LIB file format.\n"
  130.                   "\tThis file has been ignored.\n",
  131.                   (*lib_file).filename);
  132.    Delete lib_file FromList lib_file_list EndDelete;
  133.    file_close_for_read();
  134.    return;
  135.   EndIf;
  136.  Lib_file.page_size            = Lib_hdr.page_size + 3;
  137.  Lib_file.request_count        = 0;
  138.  First(Lib_file.external_list) =
  139.  Last(Lib_file.external_list)  = Null;
  140.  n_directory_blocks            = Lib_hdr.n_directory_blocks;
  141.  file_position(Lib_hdr.directory_position);
  142.  file_IO_limit(0);
  143.  symbol_count = 0;
  144.  public_array = public_sort_array;
  145.  For current_block=0;
  146.      current_block LessThan  n_directory_blocks;
  147.      current_block++
  148.   BeginFor
  149.    file_read(object_file_element, 512);
  150.    directory_page = (library_directory_ptr) object_file_element;
  151.    For entry_number=0; entry_number LessThan 37; entry_number++
  152.     BeginFor
  153.      symbol_index =
  154.       Directory_page.offset_to_symbol[entry_number] ShiftedLeft 1;
  155.      LoopIf(symbol_index IsZero);
  156.      symbol = (library_symbol_entry_ptr)
  157.               Addr(Directory_page.offset_to_symbol[symbol_index]);
  158.      symbol_in_page = (bit_16 *)
  159.                       Addr(Symbol.symbol[Symbol.length_of_symbol]);
  160.      If case_ignore.val
  161.       Then
  162.        far_to_lower(Symbol.symbol, Symbol.length_of_symbol);
  163.       EndIf;
  164.      pub = lookup_public(Symbol.length_of_symbol, Symbol.symbol, 0);
  165. /*+-------------------------------------------------------------------------+
  166.   |                                                                         |
  167.   | The Microsoft linker does not seem to concern itself with the ambiguity |
  168.   | which occurs when more than one library contains a module resolving an  |
  169.   | external reference.  It just seems to take the module from the first    |
  170.   | library which can resolve the external.  This linker behaves in the     |
  171.   | same manner except it will log when it ignores a module in a library.   |
  172.   |                                                                         |
  173.   +-------------------------------------------------------------------------+*/
  174.      If Pub.type_entry IsNot unused
  175.       Then  /* Log the ambiguity. */
  176.        linker_error(4,"The symbol \"%Fs\" is defined in the libraries\n"
  177.                       "\t\"%Fs\" and \"%Fs\".\n"
  178.                       "\tThe latter has been ignored.\n",
  179.                       Pub.symbol,
  180.                       (*Pub.Library.lib_file).filename, Lib_file.filename);
  181.       Else
  182.        Pub.type_entry        = public_in_library;
  183.        Pub.Library.page      = Symbol_in_page;
  184.        Pub.Library.lib_file  = lib_file;
  185.        Pub.Library.requested = False;
  186.        If symbol_count NotLessThan MAX_PUBLICS_IN_LIBRARY
  187.         Then
  188.          linker_error(8,"Limitation of not more than %u public symbols in "
  189.                         "a library\n"
  190.                         "\texceeded for library \"%Fs\".\n",
  191.                         MAX_PUBLICS_IN_LIBRARY,
  192.                         Lib_file.filename);
  193.         EndIf;
  194.        *public_array++ = pub;
  195.        symbol_count++;
  196.       EndIf;
  197.     EndFor;
  198.   EndFor;
  199.  file_close_for_read();
  200.  If symbol_count Exceeds 0
  201.   Then
  202.    sort_directory(0, symbol_count-1);
  203.    public_array = public_sort_array;
  204.    For entry_number=0; entry_number LessThan symbol_count; entry_number++
  205.     BeginFor
  206.      Insert *public_array++ AtEnd InList Lib_file.external_list EndInsert;
  207.     EndFor;
  208.   EndIf;
  209.  return;
  210. EndCode
  211. #undef Pub
  212. #undef Lib_file
  213. #undef Lib_hdr
  214. #undef Library_page
  215. #undef Symbol
  216. #undef Symbol_in_page
  217.  
  218. /*+-------------------------------------------------------------------------+
  219.   |                                                                         |
  220.   |                              sort_directory                             |
  221.   |                                                                         |
  222.   +-------------------------------------------------------------------------+
  223.  
  224. Well, there is always much ado concerning the best sort method for a
  225. particular application.  What is used here is a simple "quick sort".
  226. See Knuth, "Searching and Sorting", page 114 for a description of the
  227. algorithm.  What is really important here is why we are sorting.  After
  228. the OBJ modules are processed, we must scan the libraries to see what
  229. modules from the library must be included.  If the symbols in the
  230. symbol table are in ascending module order, then we will include modules
  231. from the library in ascending order.  This may not seem too important
  232. at first glance, but consider that the library will be heavily buffered
  233. and we can reduce I/O overhead by processing modules in the same buffer.
  234. We may not get all the modules in one pass (a module at the end of the
  235. library could require a module at the beginning of the library).  However,
  236. experience has shown that all modules from a library can usually be
  237. included in less than three passes.  The linker statistics will show
  238. the number of passes for and modules included from each library.  If
  239. you want to test this theory, just comment out the sort in the
  240. procedure "process_library_directory" and compare the number of passes
  241. before and after.
  242.  
  243. Now, all this could be avoided if the librarian had placed the modules
  244. in the library in some sort of an approximation of a topologically
  245. sorted order.  (A true topological sort is not usually possible because
  246. relational loops are not all that infrequent.)  However, if modules with
  247. relational loops were placed close to each other, it is very likely
  248. that the I/O buffering could cause the library to be fully processed in
  249. one pass.  This would improve performance, but it would not insure that
  250. a library could be processed in exactly one pass.
  251.  
  252. Consider the case where a relational loop occurs with modules which are
  253. not in the same library (this case forces multiple passes).  E.G.,
  254. suppose module A1 in library A requires module B1 in library B.  Further,
  255. suppose module B1 in turn requires module A2 back in library A.  When
  256. processing library A (the first time), we have no way of knowing we also
  257. need A2 until after we process B1 in library B.  We then have to go back
  258. to library A and pick up A2.  The more this happens, the longer the link
  259. time.*/
  260. void sort_directory(bit_16 left, bit_16 right)
  261. BeginDeclarations
  262. bit_16                                 i;
  263. bit_16                                 j;
  264. public_entry_ptr                       temp;
  265. EndDeclarations
  266. BeginCode
  267.  If left NotLessThan right
  268.   Then
  269.    return;
  270.   EndIf;
  271.  i = left;
  272.  j = right;
  273.  While i LessThan j
  274.   BeginWhile
  275.    While i LessThan j
  276.     BeginWhile
  277.      If (*public_sort_array[i]).Library.page GreaterThan
  278.         (*public_sort_array[j]).Library.page
  279.       Then
  280.        temp                 = public_sort_array[i];
  281.        public_sort_array[i] = public_sort_array[j];
  282.        public_sort_array[j] = temp;
  283.        ExitLoop;
  284.       EndIf;
  285.      j--;
  286.     EndWhile;
  287.    While i LessThan j
  288.     BeginWhile
  289.      If (*public_sort_array[i]).Library.page GreaterThan
  290.         (*public_sort_array[j]).Library.page
  291.       Then
  292.        temp                 = public_sort_array[i];
  293.        public_sort_array[i] = public_sort_array[j];
  294.        public_sort_array[j] = temp;
  295.        ExitLoop;
  296.       EndIf;
  297.      i++;
  298.     EndWhile;
  299.   EndWhile;
  300.   If i Exceeds 0
  301.    Then
  302.     sort_directory(left, i-1);
  303.    EndIf;
  304.  sort_directory(i+1,  right);
  305.  return;
  306. EndCode
  307.  
  308.