source: rtems/cpukit/libdl/rtl-unresolved.c @ 89c59be

Last change on this file since 89c59be was 89c59be, checked in by Chris Johns <chrisj@…>, on Dec 17, 2018 at 5:36:48 AM

libdl: Add symbol searching and loading from archives.

  • Load archive symbol tables to support searching of archives for symbols.
  • Search archive symbols and load the object file that contains the symbol.
  • Search the global and archives until all remaining unresolved symbols are not found. Group the loaded object files in the pending queue.
  • Run the object file and loaded dependents as a group before adding to the main object list.
  • Remove orphaned object files after references are removed.

Updates #3686

  • Property mode set to 100644
File size: 19.5 KB
Line 
1/*
2 *  COPYRIGHT (c) 2012, 2018 Chris Johns <chrisj@rtems.org>
3 *
4 *  The license and distribution terms for this file may be
5 *  found in the file LICENSE in this distribution or at
6 *  http://www.rtems.org/license/LICENSE.
7 */
8/**
9 * @file
10 *
11 * @ingroup rtems_rtl
12 *
13 * @brief RTEMS Run-Time Linker Object File Unresolved Relocations Table.
14 */
15
16#if HAVE_CONFIG_H
17#include "config.h"
18#endif
19
20#include <errno.h>
21#include <inttypes.h>
22#include <stdlib.h>
23#include <stdio.h>
24#include <string.h>
25
26#include <rtems/rtl/rtl.h>
27#include "rtl-error.h"
28#include <rtems/rtl/rtl-unresolved.h>
29#include <rtems/rtl/rtl-trace.h>
30
31static rtems_rtl_unresolv_block*
32rtems_rtl_unresolved_block_alloc (rtems_rtl_unresolved* unresolved)
33{
34  /*
35   * The block header contains a record.
36   */
37  size_t size =
38    (sizeof(rtems_rtl_unresolv_block) +
39     (sizeof(rtems_rtl_unresolv_rec) * (unresolved->block_recs - 1)));
40  rtems_rtl_unresolv_block* block =
41    rtems_rtl_alloc_new (RTEMS_RTL_ALLOC_EXTERNAL, size, true);
42  if (block)
43  {
44    if (rtems_rtl_trace (RTEMS_RTL_TRACE_UNRESOLVED))
45      printf ("rtl: unresolv: block-alloc %p\n", block);
46    rtems_chain_append (&unresolved->blocks, &block->link);
47  }
48  else
49    rtems_rtl_set_error (ENOMEM, "no memory for unresolved block");
50  return block;
51}
52
53static size_t
54rtems_rtl_unresolved_symbol_rec_count (size_t length)
55{
56  return ((length + sizeof(rtems_rtl_unresolv_symbol) - 1) /
57          sizeof(rtems_rtl_unresolv_symbol));
58}
59
60
61static size_t
62rtems_rtl_unresolved_symbol_recs (const char* name)
63{
64  return rtems_rtl_unresolved_symbol_rec_count (strlen (name));
65}
66
67static int
68rtems_rtl_unresolved_rec_index (rtems_rtl_unresolv_block* block,
69                                rtems_rtl_unresolv_rec* rec)
70{
71  return (rec - &block->rec) / sizeof (rtems_rtl_unresolv_rec);
72}
73
74static rtems_rtl_unresolv_rec*
75rtems_rtl_unresolved_rec_first (rtems_rtl_unresolv_block* block)
76{
77  return &block->rec;
78}
79
80static rtems_rtl_unresolv_rec*
81rtems_rtl_unresolved_rec_next (rtems_rtl_unresolv_rec* rec)
82{
83  switch (rec->type)
84  {
85    case rtems_rtl_unresolved_empty:
86      /*
87       * Empty returns NULL. The end of the records in the block.
88       */
89      rec = NULL;
90      break;
91
92    case rtems_rtl_unresolved_symbol:
93      /*
94       * Determine how many records the name occupies. Round up.
95       */
96      rec += rtems_rtl_unresolved_symbol_rec_count (rec->rec.name.length);
97      break;
98
99    case rtems_rtl_unresolved_reloc:
100      ++rec;
101      break;
102
103    default:
104      break;
105  }
106
107  return rec;
108}
109
110static bool
111rtems_rtl_unresolved_rec_is_last (rtems_rtl_unresolv_block* block,
112                                  rtems_rtl_unresolv_rec*   rec)
113{
114  int index = (rec - &block->rec) / sizeof (rec);
115  return !rec || (index >= block->recs) || (rec->type == rtems_rtl_unresolved_empty);
116}
117
118static rtems_rtl_unresolv_rec*
119rtems_rtl_unresolved_rec_first_free (rtems_rtl_unresolv_block* block)
120{
121  return &block->rec + block->recs;
122}
123
124static int
125rtems_rtl_unresolved_find_name (rtems_rtl_unresolved* unresolved,
126                                const char*           name,
127                                bool                  update_refcount)
128{
129  size_t length = strlen (name) + 1;
130  int    index = 1;
131
132  rtems_chain_node* node = rtems_chain_first (&unresolved->blocks);
133  while (!rtems_chain_is_tail (&unresolved->blocks, node))
134  {
135    rtems_rtl_unresolv_block* block = (rtems_rtl_unresolv_block*) node;
136    rtems_rtl_unresolv_rec* rec = rtems_rtl_unresolved_rec_first (block);
137
138    while (!rtems_rtl_unresolved_rec_is_last (block, rec))
139    {
140      if (rec->type == rtems_rtl_unresolved_symbol)
141      {
142        if ((rec->rec.name.length == length)
143            && (strcmp (rec->rec.name.name, name) == 0))
144        {
145          if (update_refcount)
146            ++rec->rec.name.refs;
147          return index;
148        }
149        ++index;
150      }
151      rec = rtems_rtl_unresolved_rec_next (rec);
152    }
153
154    node = rtems_chain_next (node);
155  }
156
157  return 0 - index;
158}
159
160/**
161 * Struct to pass relocation data in the iterator.
162 */
163typedef struct rtems_rtl_unresolved_reloc_data
164{
165  uint16_t                name;     /**< Name index. */
166  rtems_rtl_unresolv_rec* name_rec; /**< Name record. */
167  rtems_rtl_obj_sym*      sym;      /**< The symbol record. */
168} rtems_rtl_unresolved_reloc_data;
169
170static bool
171rtems_rtl_unresolved_resolve_reloc (rtems_rtl_unresolv_rec* rec,
172                                    void*                   data)
173{
174  if (rec->type == rtems_rtl_unresolved_reloc)
175  {
176    rtems_chain_control*             pending;
177    rtems_rtl_unresolved_reloc_data* rd;
178
179    rd = (rtems_rtl_unresolved_reloc_data*) data;
180
181    if (rec->rec.reloc.name == rd->name && rec->rec.reloc.obj != NULL)
182    {
183      if (rtems_rtl_trace (RTEMS_RTL_TRACE_UNRESOLVED))
184        printf ("rtl: unresolv: resolve reloc: %s\n", rd->name_rec->rec.name.name);
185
186      rtems_rtl_obj_relocate_unresolved (&rec->rec.reloc, rd->sym);
187
188      /*
189       * If all unresolved externals are resolved add the obj module
190       * to the pending queue. This will flush the object module's
191       * data from the cache and call it's constructors.
192       */
193      if (rec->rec.reloc.obj->unresolved == 0)
194      {
195        pending = rtems_rtl_pending_unprotected ();
196        rtems_chain_append (pending, &rec->rec.reloc.obj->link);
197      }
198
199      /*
200       * Check Set the object pointer to NULL to indicate the record is not used
201       * anymore. Update the reference count of the name. The sweep after
202       * relocating will remove the reloc records with obj set to NULL and
203       * names with a reference count of 0.
204       */
205      rec->rec.reloc.obj = NULL;
206      if (rd->name_rec != NULL && rd->name_rec->rec.name.refs > 0)
207        --rd->name_rec->rec.name.refs;
208    }
209  }
210  return false;
211}
212
213static bool
214rtems_rtl_unresolved_resolve_iterator (rtems_rtl_unresolv_rec* rec,
215                                       void*                   data)
216{
217  if (rec->type == rtems_rtl_unresolved_symbol)
218  {
219    rtems_rtl_unresolved_reloc_data* rd;
220    rd = (rtems_rtl_unresolved_reloc_data*) data;
221
222    ++rd->name;
223
224    if (rtems_rtl_trace (RTEMS_RTL_TRACE_UNRESOLVED))
225      printf ("rtl: unresolv: lookup: %d: %s\n", rd->name, rec->rec.name.name);
226
227    rd->sym = rtems_rtl_symbol_global_find (rec->rec.name.name);
228
229    if (rd->sym)
230    {
231      if (rtems_rtl_trace (RTEMS_RTL_TRACE_UNRESOLVED))
232        printf ("rtl: unresolv: found: %s\n", rec->rec.name.name);
233
234      rd->name_rec = rec;
235
236      rtems_rtl_unresolved_iterate (rtems_rtl_unresolved_resolve_reloc, rd);
237
238      rd->name_rec = NULL;
239      rd->sym = NULL;
240    }
241  }
242
243  return false;
244}
245
246/**
247 * Struct to pass archive relocation data in the iterator.
248 */
249typedef struct rtems_rtl_unresolved_archive_reloc_data
250{
251  uint16_t            name;     /**< Name index. */
252  bool                loaded;   /**< Object file loaded. */
253  rtems_rtl_archives* archives; /**< The archives to search. */
254} rtems_rtl_unresolved_archive_reloc_data;
255
256static bool
257rtems_rtl_unresolved_archive_iterator (rtems_rtl_unresolv_rec* rec,
258                                       void*                   data)
259{
260  if (rec->type == rtems_rtl_unresolved_symbol)
261  {
262    rtems_rtl_unresolved_archive_reloc_data* ard;
263    ard = (rtems_rtl_unresolved_archive_reloc_data*) data;
264
265    ++ard->name;
266
267    if ((rec->rec.name.flags & RTEMS_RTL_UNRESOLV_SYM_SEARCH_ARCHIVE) != 0)
268    {
269      rtems_rtl_archive_search load;
270
271      if (rtems_rtl_trace (RTEMS_RTL_TRACE_UNRESOLVED))
272        printf ("rtl: unresolv: archive lookup: %d: %s\n",
273                ard->name, rec->rec.name.name);
274
275      load = rtems_rtl_archive_obj_load (ard->archives,
276                                         rec->rec.name.name, true);
277      if (load == rtems_rtl_archive_search_loaded)
278      {
279        ard->loaded = true;
280        return true;
281      }
282    }
283  }
284
285  return false;
286}
287
288static bool
289rtems_rtl_unresolved_archive_search_iterator (rtems_rtl_unresolv_rec* rec,
290                                              void*                   data)
291{
292  if (rec->type == rtems_rtl_unresolved_symbol)
293    rec->rec.name.flags = RTEMS_RTL_UNRESOLV_SYM_SEARCH_ARCHIVE;
294  return false;
295}
296
297static void
298rtems_rtl_unresolved_clean_block (rtems_rtl_unresolv_block* block,
299                                  rtems_rtl_unresolv_rec*   rec,
300                                  size_t                    count,
301                                  size_t                    recs_per_block)
302{
303  size_t index = rtems_rtl_unresolved_rec_index (block, rec);
304  size_t bytes =
305    (block->recs - index - count) * sizeof (rtems_rtl_unresolv_rec);
306  if (bytes)
307    memmove (rec, rec + count, bytes);
308  block->recs -= count;
309  bytes = count * sizeof (rtems_rtl_unresolv_rec);
310  memset (&block->rec + block->recs, 0, bytes);
311}
312
313static void
314rtems_rtl_unresolved_compact (void)
315{
316  rtems_rtl_unresolved* unresolved = rtems_rtl_unresolved_unprotected ();
317  if (unresolved)
318  {
319    /*
320     * Iterate over the blocks removing any empty strings. If a string is
321     * removed update the indexes of all strings above this level.
322     */
323    rtems_chain_node* node = rtems_chain_first (&unresolved->blocks);
324    uint16_t          index = 0;
325    while (!rtems_chain_is_tail (&unresolved->blocks, node))
326    {
327      rtems_rtl_unresolv_block* block = (rtems_rtl_unresolv_block*) node;
328      rtems_rtl_unresolv_rec*   rec = rtems_rtl_unresolved_rec_first (block);
329
330      while (!rtems_rtl_unresolved_rec_is_last (block, rec))
331      {
332        bool next_rec = true;
333        if (rec->type == rtems_rtl_unresolved_symbol)
334        {
335          ++index;
336          if (rec->rec.name.refs == 0)
337          {
338            /*
339             * Iterate over the remaining reloc records and update the index.
340             */
341            rtems_chain_node*       reindex_node;
342            rtems_rtl_unresolv_rec* reindex_first;
343            size_t                  name_recs;
344            if (rtems_rtl_trace (RTEMS_RTL_TRACE_UNRESOLVED))
345              printf ("rtl: unresolv: remove name: %s\n", rec->rec.name.name);
346            reindex_node = node;
347            reindex_first = rtems_rtl_unresolved_rec_next (rec);
348            while (!rtems_chain_is_tail (&unresolved->blocks, reindex_node))
349            {
350              rtems_rtl_unresolv_rec*   reindex_rec;
351              rtems_rtl_unresolv_block* reindex_block;
352              reindex_block = (rtems_rtl_unresolv_block*) reindex_node;
353              if (reindex_first != NULL)
354              {
355                reindex_rec = reindex_first;
356                reindex_first = NULL;
357              }
358              else
359              {
360                reindex_rec = rtems_rtl_unresolved_rec_first (reindex_block);
361              }
362              while (!rtems_rtl_unresolved_rec_is_last (reindex_block,
363                                                        reindex_rec))
364              {
365                if (reindex_rec->type == rtems_rtl_unresolved_reloc)
366                {
367                  if (reindex_rec->rec.reloc.name >= index)
368                    --reindex_rec->rec.reloc.name;
369                }
370                reindex_rec = rtems_rtl_unresolved_rec_next (reindex_rec);
371              }
372              reindex_node = rtems_chain_next (reindex_node);
373            }
374            /*
375             * Compact the block removing the name record.
376             */
377            name_recs = rtems_rtl_unresolved_symbol_recs (rec->rec.name.name);
378            rtems_rtl_unresolved_clean_block (block, rec, name_recs,
379                                              unresolved->block_recs);
380            --index;
381            next_rec = false;
382          }
383        }
384        else if (rec->type == rtems_rtl_unresolved_reloc)
385        {
386          if (rec->rec.reloc.obj == NULL)
387          {
388            rtems_rtl_unresolved_clean_block (block, rec, 1,
389                                              unresolved->block_recs);
390            next_rec = false;
391          }
392        }
393
394        if (next_rec)
395          rec = rtems_rtl_unresolved_rec_next (rec);
396      }
397
398      if (block->recs == 0)
399      {
400        rtems_chain_node* next_node = rtems_chain_next (node);
401        if (rtems_rtl_trace (RTEMS_RTL_TRACE_UNRESOLVED))
402          printf ("rtl: unresolv: block-del %p\n", block);
403        rtems_chain_extract (node);
404        rtems_rtl_alloc_del (RTEMS_RTL_ALLOC_EXTERNAL, block);
405        node = next_node;
406      }
407      else
408      {
409        node = rtems_chain_next (node);
410      }
411    }
412  }
413}
414
415bool
416rtems_rtl_unresolved_table_open (rtems_rtl_unresolved* unresolved,
417                                 size_t                block_recs)
418{
419  unresolved->marker = 0xdeadf00d;
420  unresolved->block_recs = block_recs;
421  rtems_chain_initialize_empty (&unresolved->blocks);
422  return true;
423}
424
425void
426rtems_rtl_unresolved_table_close (rtems_rtl_unresolved* unresolved)
427{
428  rtems_chain_node* node = rtems_chain_first (&unresolved->blocks);
429  while (!rtems_chain_is_tail (&unresolved->blocks, node))
430  {
431    rtems_chain_node* next = rtems_chain_next (node);
432    rtems_rtl_alloc_del (RTEMS_RTL_ALLOC_EXTERNAL, node);
433    node = next;
434  }
435}
436
437bool
438rtems_rtl_unresolved_iterate (rtems_rtl_unresolved_iterator iterator,
439                              void*                         data)
440{
441  rtems_rtl_unresolved* unresolved = rtems_rtl_unresolved_unprotected ();
442  if (unresolved)
443  {
444    rtems_chain_node* node = rtems_chain_first (&unresolved->blocks);
445    while (!rtems_chain_is_tail (&unresolved->blocks, node))
446    {
447      rtems_rtl_unresolv_block* block = (rtems_rtl_unresolv_block*) node;
448      rtems_rtl_unresolv_rec*   rec = rtems_rtl_unresolved_rec_first (block);
449
450      while (!rtems_rtl_unresolved_rec_is_last (block, rec))
451      {
452        if (iterator (rec, data))
453          return true;
454        rec = rtems_rtl_unresolved_rec_next (rec);
455      }
456
457      node = rtems_chain_next (node);
458    }
459  }
460  return false;
461}
462
463bool
464rtems_rtl_unresolved_add (rtems_rtl_obj*        obj,
465                          const uint16_t        flags,
466                          const char*           name,
467                          const uint16_t        sect,
468                          const rtems_rtl_word* rel)
469{
470  rtems_rtl_unresolved*     unresolved;
471  rtems_chain_node*         node;
472  rtems_rtl_unresolv_block* block;
473  rtems_rtl_unresolv_rec*   rec;
474  int                       name_index;
475  size_t                    name_recs;
476
477  if (rtems_rtl_trace (RTEMS_RTL_TRACE_UNRESOLVED))
478    printf ("rtl: unresolv: add: %s(s:%d) -> %s\n",
479            rtems_rtl_obj_oname (obj), sect, name);
480
481  unresolved = rtems_rtl_unresolved_unprotected ();
482  if (!unresolved)
483    return false;
484
485  /*
486   * Find the first block with a spare record.
487   */
488  node = rtems_chain_first (&unresolved->blocks);
489  block = NULL;
490  while (!rtems_chain_is_tail (&unresolved->blocks, node))
491  {
492    block = (rtems_rtl_unresolv_block*) node;
493    if (block->recs < unresolved->block_recs)
494      break;
495    block = NULL;
496    node = rtems_chain_next (node);
497  }
498
499  /*
500   * No blocks with any spare records, allocate a new block.
501   */
502  if (!block)
503  {
504    block = rtems_rtl_unresolved_block_alloc (unresolved);
505    if (!block)
506      return false;
507  }
508
509  name_index = rtems_rtl_unresolved_find_name (unresolved, name, true);
510  name_recs = rtems_rtl_unresolved_symbol_recs (name);
511
512  /*
513   * An index less than 0 means the name is present and "0 - index" is the next
514   * index to use.
515   */
516  if (name_index < 0)
517  {
518    rtems_rtl_unresolv_block* name_block = block;
519
520    /*
521     * Is there enough room to fit the name ? It not add a new block.
522     */
523    if (name_recs > (unresolved->block_recs - block->recs))
524    {
525      name_block = rtems_rtl_unresolved_block_alloc (unresolved);
526      if (!name_block)
527        return false;
528    }
529
530    rec = rtems_rtl_unresolved_rec_first_free (name_block);
531    rec->type = rtems_rtl_unresolved_symbol;
532    rec->rec.name.refs = 1;
533    rec->rec.name.flags = RTEMS_RTL_UNRESOLV_SYM_SEARCH_ARCHIVE;
534    rec->rec.name.length = strlen (name) + 1;
535    memcpy ((void*) &rec->rec.name.name[0], name, rec->rec.name.length + 1);
536    block->recs += name_recs;
537    name_index = 0 - name_index;
538
539    /*
540     * If the name block is the reloc block and it is full allocate a new
541     * block for the relocation record.
542     */
543    if ((block == name_block) && (block->recs >= unresolved->block_recs))
544    {
545      block = rtems_rtl_unresolved_block_alloc (unresolved);
546      if (!block)
547        return false;
548    }
549  }
550
551  rec = rtems_rtl_unresolved_rec_first_free (block);
552  rec->type = rtems_rtl_unresolved_reloc;
553  rec->rec.reloc.obj = obj;
554  rec->rec.reloc.flags = flags;
555  rec->rec.reloc.name = name_index;
556  rec->rec.reloc.sect = sect;
557  rec->rec.reloc.rel[0] = rel[0];
558  rec->rec.reloc.rel[1] = rel[1];
559  rec->rec.reloc.rel[2] = rel[2];
560
561  ++block->recs;
562
563  return true;
564}
565
566void
567rtems_rtl_unresolved_resolve (void)
568{
569  bool resolving = true;
570
571  if (rtems_rtl_trace (RTEMS_RTL_TRACE_UNRESOLVED))
572    printf ("rtl: unresolv: global resolve\n");
573
574  /*
575   * The resolving process is two separate stages, The first stage is to
576   * iterate over the unresolved symbols search the global symbol table. If a
577   * symbol is found iterate over the unresolved relocation records for the
578   * symbol fixing up the relocations. The second stage is to search the
579   * archives for symbols we have not been search before and if a symbol if
580   * found in an archve loaded the object file. Loading an object file stops
581   * the search of the archives for symbols and stage one is performed
582   * again. The process repeats until no more symbols are resolved.
583   */
584  while (resolving)
585  {
586    rtems_rtl_unresolved_reloc_data rd = {
587      .name = 0,
588      .name_rec = NULL,
589      .sym = NULL
590    };
591    rtems_rtl_unresolved_archive_reloc_data ard = {
592      .name = 0,
593      .loaded = false,
594      .archives = rtems_rtl_archives_unprotected ()
595    };
596
597    rtems_rtl_unresolved_iterate (rtems_rtl_unresolved_resolve_iterator, &rd);
598    rtems_rtl_unresolved_compact ();
599    rtems_rtl_unresolved_iterate (rtems_rtl_unresolved_archive_iterator, &ard);
600
601    resolving = ard.loaded;
602  }
603
604  if (rtems_rtl_trace (RTEMS_RTL_TRACE_UNRESOLVED))
605    rtems_rtl_unresolved_dump ();
606}
607
608bool
609rtems_rtl_unresolved_remove (rtems_rtl_obj*        obj,
610                             const char*           name,
611                             const uint16_t        sect,
612                             const rtems_rtl_word* rel)
613{
614  rtems_rtl_unresolved* unresolved;
615  unresolved = rtems_rtl_unresolved_unprotected ();
616  if (!unresolved)
617    return false;
618  return false;
619}
620
621/**
622 * Struct to pass relocation data in the iterator.
623 */
624typedef struct rtems_rtl_unresolved_dump_data
625{
626  size_t rec;
627  size_t names;
628} rtems_rtl_unresolved_dump_data;
629
630static bool
631rtems_rtl_unresolved_dump_iterator (rtems_rtl_unresolv_rec* rec,
632                                    void*                   data)
633{
634  rtems_rtl_unresolved_dump_data* dd;
635  dd = (rtems_rtl_unresolved_dump_data*) data;
636  switch (rec->type)
637  {
638  case rtems_rtl_unresolved_empty:
639    printf (" %03zu: 0: empty\n", dd->rec);
640    break;
641  case rtems_rtl_unresolved_symbol:
642    ++dd->names;
643    printf (" %3zu: 1:  name: %3d refs: %2d: %2d: %s\n",
644            dd->rec, dd->names,
645            rec->rec.name.refs, rec->rec.name.length, rec->rec.name.name);
646    break;
647  case rtems_rtl_unresolved_reloc:
648    printf (" %3zu: 2: reloc: obj:%s name:%2d: sect:%d\n",
649            dd->rec,
650            rec->rec.reloc.obj->oname,
651            rec->rec.reloc.name,
652            rec->rec.reloc.sect);
653    break;
654  default:
655    printf (" %03zu: %d: unknown\n", dd->rec, rec->type);
656    break;
657  }
658  ++dd->rec;
659  return false;
660}
661
662void
663rtems_rtl_unresolved_set_archive_search (void)
664{
665  rtems_rtl_unresolved_iterate (rtems_rtl_unresolved_archive_search_iterator,
666                                NULL);
667}
668
669void
670rtems_rtl_unresolved_dump (void)
671{
672  rtems_rtl_unresolved_dump_data dd = { 0 };
673  printf ("RTL Unresolved data:\n");
674  rtems_rtl_unresolved_iterate (rtems_rtl_unresolved_dump_iterator, &dd);
675}
Note: See TracBrowser for help on using the repository browser.