1/* 2 * Copyright (c) 1999-2003 Apple Computer, Inc. All Rights Reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. Please obtain a copy of the License at 10 * http://www.opensource.apple.com/apsl/ and read it before using this 11 * file. 12 * 13 * The Original Code and all software distributed under the License are 14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 18 * Please see the License for the specific language governing rights and 19 * limitations under the License. 20 * 21 * @APPLE_LICENSE_HEADER_END@ 22 */ 23#if defined(__MWERKS__) && !defined(__private_extern__) 24#define __private_extern__ __declspec(private_extern) 25#endif 26 27/* 28 * Global types, variables and routines declared in the file symbols.c. 29 * 30 * The following include file need to be included before this file: 31 * #include <nlist.h> 32 * #include "ld.h" 33 */ 34 35/* 36 * This structure holds an external symbol that has been merged and will be in 37 * the output file. The nlist feilds are used as follows: 38 * union { 39 * char *n_name; The name of the symbol (pointing into the merged 40 * string table). 41 * long n_strx; Only set write before the symbol is written to the 42 * output file and then the symbol is no longer used. 43 * } n_un; 44 * unsigned char n_type; Same as in an object file. 45 * unsigned char n_sect; " 46 * short n_desc; " 47 * unsigned long n_value; The value of the symbol as it came from the 48 * object it was defined in for N_SECT and N_ABS 49 * type symbols. 50 * For common symbols the size of the largest 51 * common. 52 * For N_INDR symbols a pointer to the 53 * merged_symbol that it is an indirect for. 54 * 55 */ 56struct merged_symbol { 57 struct nlist nlist; /* the nlist structure of this merged symbol */ 58 unsigned long name_len; /* the size of the symbol name */ 59 struct object_file /* pointer to the object file this symbol is */ 60 *definition_object; /* defined in */ 61 struct dynamic_library /* pointer to the dynamic library this symbol */ 62 *definition_library; /* is defined in, if defined_in_dylib==TRUE */ 63 struct object_file /* pointer to the object file this symbol is */ 64 *non_dylib_referenced_obj; /* first referenced in, */ 65 /* if referenced_in_non_dylib == TRUE */ 66 unsigned long 67 error_flagged_for_dylib:1, /* symbol reported as an error in dylib */ 68 defined_in_dylib:1, /* symbol defined in dylib */ 69 coalesced_defined_in_dylib:1, /* symbol defined in dylib that is a */ 70 /* coalesced symbol */ 71 weak_def_in_dylib:1, /* a weak definition in a dylib */ 72 referenced_in_non_dylib:1, /* symbol referenced in loaded objects and */ 73 /* will be in output file */ 74 flagged_read_only_reloc:1, /* symbol reported as an external reloc */ 75 /* in a read only section */ 76 twolevel_reference:1, /* set only for merged_symbol structs that */ 77 /* are not in the merged symbol table but */ 78 /* only in the undefined list as a two- */ 79 /* level namespace reference from a dylib.*/ 80 weak_reference_mismatch:1, /* seen both a weak and non-weak reference */ 81 seen_undef:1, /* seen an undefined reference from an */ 82 /* object file. So the N_WEAK_REF bit */ 83 /* does reflect the value for the output. */ 84 define_a_way:1, /* set if this symbol was defined as a */ 85 /* result of -undefined define_a_way */ 86 live:1, /* TRUE if the symbol is not to be dead */ 87 /* stripped. */ 88 unused:21; 89 unsigned long output_index; /* the symbol table index this symbol will */ 90 /* have in the output file. */ 91 int undef_order; /* if the symbol was undefined the order it */ 92 /* was seen. */ 93 /* 94 * For two-level namespace hints this is the index into the table of 95 * contents for the definition symbol in the dylib it is defined in, 96 */ 97 unsigned long itoc; 98 99 /* 100 * If the twolevel_reference bit above is set this is a pointer to 101 * the dynamic_library struct the two-level reference is in. Then the 102 * library ordinal in the nlist struct can be used with the dependent_images 103 * to cause the correct module to be loaded. 104 */ 105 struct dynamic_library *referencing_library; 106 107 /* 108 * When doing dead code stripping this is set to the fine_reloc this symbol 109 * is in if any. 110 */ 111 struct fine_reloc *fine_reloc; 112}; 113 114/* 115 * The number of merged_symbol structrures in a merged_symbol_list. 116 */ 117#ifndef RLD 118#define NSYMBOLS 20001 119#else 120#define NSYMBOLS 201 121#endif /* RLD */ 122/* The number of size of the hash table in a merged_symbol_list */ 123#define SYMBOL_LIST_HASH_SIZE (NSYMBOLS * 2) 124 125/* The number of buckets for conflicts */ 126#define SYMBOL_CHUNK_SIZE 10 127 128/* The collection of buckets for conflicting hash values */ 129struct merged_symbol_chunk 130{ 131 /* the buckets */ 132 struct merged_symbol symbols[SYMBOL_CHUNK_SIZE]; 133 134 /* 135 * next chunk (if this is not null, it means all of the buckets of this 136 * chunk are full) 137 */ 138 struct merged_symbol_chunk *next; 139}; 140 141/* 142 * The block that has the hash table and a pointer to symbol list. 143 */ 144struct merged_symbol_root { 145 /* the hashed array of chunks */ 146 struct merged_symbol_chunk chunks[SYMBOL_LIST_HASH_SIZE]; 147 148 /* the list of used symbols */ 149 struct merged_symbol_list *list; 150}; 151 152/* 153 * The symbol list is the list of symbols that have been used. It's a compact 154 * flat array of pointers into the sparse hash table. 155 */ 156struct merged_symbol_list { 157 /* pointers to symbols in the merged_symbol_chunk */ 158 struct merged_symbol *symbols[SYMBOL_LIST_HASH_SIZE]; 159 160 /* next free location in the symbols array */ 161 unsigned long used; 162 163 /* next linked symbol list (NULL means no more) */ 164 struct merged_symbol_list *next; 165}; 166 167 168/* the blocks that store the strings; allocated as needed */ 169struct string_block { 170 unsigned long size; /* the number of bytes in this block */ 171 unsigned long used; /* the number of bytes used in this block */ 172 char *strings; /* the strings */ 173 unsigned long index; /* the relitive index into the final symbol */ 174 /* table for the block (set in pass2). */ 175 enum bool base_strings; /* TRUE if this block is for strings from the */ 176 /* base file (used if strip_base_symbols is */ 177 /* TRUE) */ 178 enum bool dylib_strings; /* TRUE if this block is for strings from a */ 179 /* dylib file (string won't be in output). */ 180#ifdef RLD 181 long set_num; /* the object file set number these strings */ 182 /* come from. */ 183#endif /* RLD */ 184 struct string_block *next; /* the next block */ 185}; 186 187/* 188 * The structure for the undefined list and the structure that the items 189 * are allocated out of. 190 */ 191struct undefined_list { 192 struct merged_symbol 193 *merged_symbol; /* the undefined symbol */ 194 struct undefined_list *prev;/* previous in the chain */ 195 struct undefined_list *next;/* next in the chain */ 196}; 197 198/* 199 * The structure of the load map for common symbols. This is only used to help 200 * print the load map. It is created by define_commmon_symbols() in symbols.c 201 * and used in print_load_map() in layout.c. 202 */ 203struct common_load_map { 204 struct merged_section 205 *common_ms; /* the section common symbol were allocated in*/ 206 unsigned long 207 ncommon_symbols; /* number of common symbols */ 208 struct common_symbol /* a pointer to an array of structures (one */ 209 *common_symbols; /* for each common symbol) */ 210}; 211struct common_symbol { 212 struct merged_symbol /* a pointer the merged common symbol */ 213 *merged_symbol; 214 unsigned long common_size; /* the size of the merged common symbol */ 215}; 216 217/* 218 * The head of the symbol list and the total count of all external symbols 219 * in the list. The total count of private externals is included in the total 220 * count of the merged symbols. The count of merged symbols referenced only 221 * from dylibs will not be in the output file. 222 */ 223__private_extern__ struct merged_symbol_root *merged_symbol_root; 224__private_extern__ unsigned long nmerged_symbols; 225__private_extern__ unsigned long nmerged_private_symbols; 226__private_extern__ unsigned long nmerged_symbols_referenced_only_from_dylibs; 227 228/* 229 * nstripped_merged_symbols is set to the number of merged symbol being stripped 230 * out when the strip_level is STRIP_DYNAMIC_EXECUTABLE. 231 */ 232__private_extern__ unsigned long nstripped_merged_symbols; 233 234/* 235 * The head of the list of the blocks that store the strings for the merged 236 * symbols and the total size of all the strings. The size of the strings for 237 * the private externals is included in the the merge string size. 238 */ 239__private_extern__ struct string_block *merged_string_blocks; 240__private_extern__ unsigned long merged_string_size; 241__private_extern__ unsigned long merged_private_string_size; 242 243/* 244 * The head of the undefined list itself. This is a circular list so it can be 245 * searched from start to end and so new items can be put on the end. This 246 * structure never has it's merged_symbol filled in but only serves as the 247 * head and tail of the list. 248 */ 249__private_extern__ struct undefined_list undefined_list; 250 251/* 252 * The common symbol load map. Only allocated and filled in if load map is 253 * requested. 254 */ 255__private_extern__ struct common_load_map common_load_map; 256 257/* 258 * The object file that is created for the common symbols to be allocated in. 259 */ 260__private_extern__ 261struct object_file link_edit_common_object; 262 263/* 264 * The number of local symbols that will appear in the output file and the 265 * size of their strings. 266 */ 267__private_extern__ unsigned long nlocal_symbols; 268__private_extern__ unsigned long local_string_size; 269 270/* 271 * For local symbols of an object file that are not to be in the output a 272 * local symbol block is created and linked off of the object structure's 273 * localsym_blocks pointer. These blocks are linked in order by the index. 274 * If the symbols in that block are simply to be discarded the state is set 275 * to DISCARD_SYMBOLS. 276 * 277 * When a block of local symbols are being excluded from the output because 278 * it is a duplicate block of stabs in an include file (a N_BINCL/N_EINCL 279 * group) then the state is set to EXCLUDED_INCLUDE and the sum field is filled 280 * in and used to create the one N_EXCL stab to replace the group. 281 * 282 * The first time a N_BINCL is seen its sum needs to be set into its n_value 283 * so a local symbol block state will be set to BEGIN_INCLUDE and it will 284 * have a count of 1. 285 * 286 * For the other cases of when a block of local symbols are being excluded from 287 * the output (deleted coalesced symbols or indirect symbols) the state is set 288 * to DISCARD_SYMBOLS. 289 * 290 * The PARSE_SYMBOLS is used temporarily while parsing out N_BINCL/N_EINCL and 291 * then are removed from the list after parsing is done. 292 */ 293enum localsym_block_state { 294 PARSE_SYMBOLS, 295 BEGIN_INCLUDE, 296 EXCLUDED_INCLUDE, 297 DISCARD_SYMBOLS 298}; 299struct localsym_block { 300 unsigned long index; 301 unsigned long count; 302 enum localsym_block_state state; 303 unsigned long input_N_BINCL_n_value; 304 unsigned long sum; 305 struct localsym_block *next; 306}; 307 308/* 309 * The things to deal with creating local symbols with the object file's name 310 * for a given section. If the section name is (__TEXT,__text) these are the 311 * same as a UNIX link editor's file.o symbols for the text section. 312 */ 313struct sect_object_symbols { 314 enum bool specified; /* if this has been specified on the command line */ 315 char *segname; /* the segment name */ 316 char *sectname; /* the section name */ 317 struct merged_section *ms; /* the merged section structure */ 318}; 319__private_extern__ struct sect_object_symbols sect_object_symbols; 320 321/* 322 * The indr_symbol_pair structure is used when there are chains of N_INDR 323 * that have symbols both from dylibs and not from dylibs. The routine 324 * reduce_indr_symbols() creates this and the routines output_merged_symbols() 325 * and indirect_section_merge() both use it. What is going on is that when 326 * producing an output file the N_INDR symbols from a dylib can't be used in 327 * a chain of N_INDR symbols. So this structure contains merged_symbols which 328 * are N_INDR which should use the matching indr_symbol from the table instead 329 * of going through (struct merged_symbol *)(merged_symbol->nlist.n_value). 330 */ 331struct indr_symbol_pair { 332 struct merged_symbol *merged_symbol; 333 struct merged_symbol *indr_symbol; 334}; 335__private_extern__ struct indr_symbol_pair *indr_symbol_pairs; 336__private_extern__ unsigned long nindr_symbol_pairs; 337 338/* 339 * merged_symbols_relocated is set when the merged symbols are relocated to 340 * have addresses and section numbers as they would in the output file. 341 */ 342__private_extern__ enum bool merged_symbols_relocated; 343 344/* 345 * The strings in the string table can't start at offset 0 because a symbol with 346 * a string offset of zero is defined to have a null "" symbol name. So the 347 * first STRING_SIZE_OFFSET bytes are not used and the first string starts after 348 * this amount. Also these first bytes are zero so that if the special case of 349 * a zero index is not handled by a program it will happen to work. 350 */ 351#define STRING_SIZE_OFFSET (sizeof(long)) 352 353__private_extern__ void merge_symbols( 354 void); 355__private_extern__ struct merged_symbol *command_line_symbol( 356 char *symbol_name); 357__private_extern__ struct merged_symbol *lookup_symbol( 358 char *symbol_name); 359__private_extern__ void command_line_indr_symbol( 360 char *symbol_name, 361 char *indr_symbol_name); 362#ifndef RLD 363__private_extern__ void hash_instrument( 364 void); 365__private_extern__ void merge_dylib_module_symbols( 366 struct dynamic_library *dynamic_library); 367__private_extern__ void merge_bundle_loader_symbols( 368 struct dynamic_library *dynamic_library); 369#endif /* !defined(RLD) */ 370__private_extern__ void delete_from_undefined_list( 371 struct undefined_list *undefined); 372__private_extern__ void trace_merged_symbol( 373 struct merged_symbol *merged_symbol); 374__private_extern__ void free_pass1_symbol_data( 375 void); 376__private_extern__ void free_undefined_list( 377 void); 378__private_extern__ void define_common_symbols( 379 void); 380__private_extern__ void define_undefined_symbols_a_way( 381 void); 382__private_extern__ void mark_globals_live( 383 void); 384__private_extern__ void mark_N_NO_DEAD_STRIP_local_symbols_live( 385 void); 386__private_extern__ void set_fine_relocs_for_merged_symbols( 387 void); 388__private_extern__ void count_live_symbols( 389 void); 390__private_extern__ void define_link_editor_execute_symbols( 391 unsigned long header_address); 392__private_extern__ void setup_link_editor_symbols( 393 void); 394__private_extern__ void define_link_editor_dylib_symbols( 395 unsigned long header_address); 396__private_extern__ void define_link_editor_preload_symbols( 397 enum bool setup); 398__private_extern__ void reduce_indr_symbols( 399 void); 400__private_extern__ void process_undefineds( 401 void); 402__private_extern__ void reset_prebound_undefines( 403 void); 404__private_extern__ void assign_output_symbol_indexes( 405 void); 406#ifndef RLD 407__private_extern__ void layout_dylib_tables( 408 void); 409__private_extern__ void output_dylib_tables( 410 void); 411#endif 412__private_extern__ void layout_merged_symbols( 413 void); 414__private_extern__ void discard_local_symbols_for_section( 415 unsigned long nsect, 416 struct nlist *object_symbols, 417 char *object_strings, 418 struct section *s, 419 struct section_map *section_map); 420__private_extern__ void output_local_symbols( 421 void); 422__private_extern__ unsigned long local_symbol_output_index( 423 struct object_file *obj, 424 unsigned long index); 425__private_extern__ void set_merged_string_block_indexes( 426 void); 427__private_extern__ void output_merged_symbols( 428 void); 429#if defined(RLD) && !defined(SA_RLD) 430__private_extern__ 431void output_rld_symfile_merged_symbols( 432 void); 433#endif /* defined(RLD) && !defined(SA_RLD) */ 434__private_extern__ enum bool is_output_local_symbol( 435 unsigned char n_type, 436 unsigned char n_sect, 437 unsigned char n_desc, 438 struct object_file *obj, 439 char *symbol_name, 440 unsigned long *output_strlen); 441__private_extern__ unsigned long merged_symbol_output_index( 442 struct merged_symbol *merged_symbol); 443__private_extern__ void clear_read_only_reloc_flags( 444 void); 445__private_extern__ void flag_read_only_reloc( 446 struct section *s, 447 unsigned long output_index, 448 enum bool *first_time); 449 450#ifdef RLD 451__private_extern__ void free_multiple_defs( 452 void); 453__private_extern__ void remove_merged_symbols( 454 void); 455#endif /* RLD */ 456 457__private_extern__ struct section *get_output_section( 458 unsigned long sect); 459 460#ifdef DEBUG 461__private_extern__ void print_symbol_list( 462 char *string, 463 enum bool input_based); 464__private_extern__ void print_undefined_list( 465 void); 466#endif /* DEBUG */ 467