Initialize Tizen 2.3
[external/prelink.git] / src / cxx.c
1 /* Copyright (C) 2001, 2002, 2003, 2007, 2009 Red Hat, Inc.
2    Written by Jakub Jelinek <jakub@redhat.com>, 2001.
3
4    This program is free software; you can redistribute it and/or modify
5    it under the terms of the GNU General Public License as published by
6    the Free Software Foundation; either version 2, or (at your option)
7    any later version.
8
9    This program is distributed in the hope that it will be useful,
10    but WITHOUT ANY WARRANTY; without even the implied warranty of
11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12    GNU General Public License for more details.
13
14    You should have received a copy of the GNU General Public License
15    along with this program; if not, write to the Free Software Foundation,
16    Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
17
18 #include <config.h>
19 #include <alloca.h>
20 #include <assert.h>
21 #include <errno.h>
22 #include <error.h>
23 #include <fcntl.h>
24 #include <stdio.h>
25 #include <string.h>
26 #include <unistd.h>
27 #include <sys/wait.h>
28 #include "prelink.h"
29
30 static struct
31   {
32     const char *prefix;
33     unsigned char prefix_len, st_info, check_pltref;
34   }
35 specials[] =
36   {
37     /* G++ 3.0 ABI.  */
38     /* Virtual table.  */
39     { "_ZTV", 4, GELF_ST_INFO (STB_WEAK, STT_OBJECT), 1 },
40     /* Typeinfo.  */
41     { "_ZTI", 4, GELF_ST_INFO (STB_WEAK, STT_OBJECT), 0 },
42     /* G++ 2.96-RH ABI.  */
43     /* Virtual table.  */
44     { "__vt_", 5, GELF_ST_INFO (STB_WEAK, STT_OBJECT), 0 },
45     { NULL, 0, 0, 0 }
46   };
47
48 struct find_cxx_sym_valsize
49 {
50   GElf_Addr start;
51   GElf_Addr end;
52   unsigned int idx;
53   unsigned char mark;
54 };
55
56 struct find_cxx_sym_cache
57 {
58   Elf_Data *symtab, *strtab;
59   int symsec, strsec, count;
60   struct find_cxx_sym_valsize vals[];
61 };
62
63 struct find_cxx_sym
64 {
65   DSO *dso;
66   int n;
67   struct find_cxx_sym_cache *cache;
68   struct prelink_entry *ent;
69   Elf_Data *symtab, *strtab;
70   int symsec, strsec;
71   int lastndx;
72   GElf_Sym sym;
73 };
74
75 static int
76 cachecmp (const void *a, const void *b)
77 {
78   GElf_Addr va = ((const struct find_cxx_sym_valsize *) a)->start;
79   GElf_Addr vb = ((const struct find_cxx_sym_valsize *) b)->start;
80
81   if (va < vb)
82     return -1;
83   if (va > vb)
84     return 1;
85
86   va = ((const struct find_cxx_sym_valsize *) a)->end;
87   vb = ((const struct find_cxx_sym_valsize *) b)->end;
88
89   if (va < vb)
90     return -1;
91
92   return va > vb;
93 }
94
95 static struct find_cxx_sym_cache *
96 create_cache (DSO *dso, int plt)
97 {
98   Elf_Data *symtab, *strtab;
99   Elf_Scn *scn;
100   int symsec, strsec, ndx, dndx, maxndx;
101   struct find_cxx_sym_cache *cache;
102   GElf_Addr top;
103
104   symsec = addr_to_sec (dso, dso->info[DT_SYMTAB]);
105   if (symsec == -1)
106     return (struct find_cxx_sym_cache *) -1UL;
107   scn = dso->scn[symsec];
108   symtab = elf_getdata (scn, NULL);
109   assert (elf_getdata (scn, symtab) == NULL);
110   strsec = addr_to_sec (dso, dso->info[DT_STRTAB]);
111   if (strsec == -1)
112     return (struct find_cxx_sym_cache *) -1UL;
113   scn = dso->scn[strsec];
114   strtab = elf_getdata (scn, NULL);
115   assert (elf_getdata (scn, strtab) == NULL);
116   maxndx = symtab->d_size / dso->shdr[symsec].sh_entsize;
117
118   cache = malloc (sizeof (*cache) + sizeof (cache->vals[0]) * maxndx);
119   if (cache == NULL)
120     {
121       error (0, ENOMEM, "%s: Could load symbol table", dso->filename);
122       return NULL;
123     }
124
125   cache->symsec = symsec;
126   cache->strsec = strsec;
127   cache->symtab = symtab;
128   cache->strtab = strtab;
129   for (ndx = 0, dndx = 0; ndx < maxndx; ++ndx)
130     {
131       GElf_Sym sym;
132       const char *name;
133       int k;
134
135       gelfx_getsym (dso->elf, symtab, ndx, &sym);
136       if (plt)
137         {
138           if (sym.st_shndx != SHN_UNDEF || sym.st_value == 0)
139             continue;
140         }
141       else if (sym.st_shndx == SHN_UNDEF)
142         continue;
143       cache->vals[dndx].start = sym.st_value;
144       cache->vals[dndx].end = sym.st_value + sym.st_size;
145       cache->vals[dndx].idx = ndx;
146       cache->vals[dndx].mark = 0;
147       name = (const char *) strtab->d_buf + sym.st_name;
148       if (!plt && ELF32_ST_VISIBILITY (sym.st_other) == STV_DEFAULT)
149         for (k = 0; specials[k].prefix; ++k)
150           if (sym.st_info == specials[k].st_info
151               && strncmp (name, specials[k].prefix,
152                           specials[k].prefix_len) == 0)
153             {
154               cache->vals[dndx].mark = 1;
155               break;
156             }
157       ++dndx;
158     }
159
160   maxndx = dndx;
161   qsort (cache->vals, maxndx, sizeof (cache->vals[0]), cachecmp);
162
163   if (!plt)
164     {
165       for (top = 0, ndx = 0; ndx < maxndx; ++ndx)
166         {
167           if (cache->vals[ndx].start < top
168               || (ndx < maxndx - 1
169                   && cache->vals[ndx].end > cache->vals[ndx + 1].start))
170             cache->vals[ndx].mark = 0;
171           if (cache->vals[ndx].end > top)
172             top = cache->vals[ndx].end;
173         }
174
175       for (ndx = dndx = 0; ndx < maxndx; ++ndx)
176         if (cache->vals[ndx].mark)
177           cache->vals[dndx++] = cache->vals[ndx];
178     }
179   cache->count = dndx;
180   return cache;
181 }
182
183 static int
184 find_cxx_sym (struct prelink_info *info, GElf_Addr addr,
185               struct find_cxx_sym *fcs, int reloc_size,
186               struct find_cxx_sym_cache **cache)
187 {
188   int n, ndeps = info->ent->ndepends + 1;
189   unsigned int hi, lo, mid;
190   DSO *dso = NULL;
191   struct find_cxx_sym_cache *c;
192
193   if (fcs->dso == NULL
194       || addr < fcs->dso->base
195       || addr >= fcs->dso->end)
196     {
197       for (n = 1; n < ndeps; ++n)
198         {
199           dso = info->dsos[n];
200           if (addr >= dso->base
201               && addr < dso->end)
202             break;
203         }
204
205       if (n == ndeps
206           && addr >= info->dso->base
207           && addr < info->dso->end)
208         {
209           n = 0;
210           dso = info->dso;
211         }
212
213       assert (n < ndeps);
214
215       if (cache[n] == NULL)
216         {
217           cache[n] = create_cache (dso, 0);
218           if (cache[n] == NULL)
219             return -2;
220         }
221       if (cache[n] == (struct find_cxx_sym_cache *) -1UL)
222         return -1;
223
224       fcs->n = n;
225       fcs->ent = n ? info->ent->depends[n - 1] : info->ent;
226       fcs->dso = dso;
227       fcs->cache = cache[n];
228       fcs->symsec = fcs->cache->symsec;
229       fcs->symtab = fcs->cache->symtab;
230       fcs->strsec = fcs->cache->strsec;
231       fcs->strtab = fcs->cache->strtab;
232       fcs->lastndx = -1;
233     }
234   else
235     dso = fcs->dso;
236
237   c = fcs->cache;
238   lo = 0;
239   hi = c->count;
240   if (fcs->lastndx != -1)
241     {
242       if (c->vals[fcs->lastndx].start <= addr)
243         {
244           lo = fcs->lastndx;
245           if (hi - lo >= 16)
246             {
247               if (c->vals[lo + 2].start > addr)
248                 hi = lo + 2;
249               else if (c->vals[lo + 15].start > addr)
250                 hi = lo + 15;
251             }
252         }
253       else
254         {
255           hi = fcs->lastndx;
256           if (hi >= 15)
257             {
258               if (c->vals[hi - 2].start <= addr)
259                 lo = hi - 2;
260               else if (c->vals[hi - 15].start <= addr)
261                 lo = hi - 15;
262             }
263         }
264     }
265   while (lo < hi)
266     {
267       mid = (lo + hi) / 2;
268       if (c->vals[mid].start <= addr)
269         {
270           if (c->vals[mid].end >= addr + reloc_size)
271             {
272               gelfx_getsym (dso->elf, fcs->symtab, c->vals[mid].idx,
273                             &fcs->sym);
274               fcs->lastndx = mid;
275               return c->vals[mid].idx;
276             }
277           lo = mid + 1;
278         }
279       else
280         hi = mid;
281     }
282
283   return -1;
284 }
285
286 /* The idea here is that C++ virtual tables are always emitted
287    in .gnu.linkonce.d.* sections as WEAK symbols and they
288    need to be the same.
289    We check if they are and if yes, remove conflicts against
290    virtual tables which will not be used.  */
291
292 int
293 remove_redundant_cxx_conflicts (struct prelink_info *info)
294 {
295   int i, j, k, n, o, state, removed = 0;
296   int ndx, sec;
297   unsigned int hi, lo, mid;
298   int reloc_type, reloc_size;
299   struct find_cxx_sym fcs1, fcs2;
300   char *mem1, *mem2;
301   const char *name = NULL, *secname = NULL;
302   GElf_Addr symtab_start;
303   GElf_Word symoff;
304   Elf_Data *binsymtab = NULL;
305   int binsymtabsec;
306   struct prelink_conflict *conflict;
307   struct find_cxx_sym_cache **cache;
308   struct find_cxx_sym_cache *binsymcache = NULL;
309   int ret = 0;
310   int rtype_class_valid;
311
312   /* Don't bother doing this for non-C++ programs.  */
313   for (i = 0; i < info->ent->ndepends; ++i)
314     if (strstr (info->ent->depends[i]->canon_filename, "libstdc++"))
315       break;
316   if (i == info->ent->ndepends)
317     return 0;
318
319   binsymtabsec = addr_to_sec (info->dso, info->dso->info[DT_SYMTAB]);
320   if (binsymtabsec != -1)
321     {
322       Elf_Scn *scn = info->dso->scn[binsymtabsec];
323
324       binsymtab = elf_getdata (scn, NULL);
325       assert (elf_getdata (scn, binsymtab) == NULL);
326     }
327
328   rtype_class_valid = info->dso->arch->rtype_class_valid;
329
330   state = 0;
331   memset (&fcs1, 0, sizeof (fcs1));
332   memset (&fcs2, 0, sizeof (fcs2));
333   cache = alloca (sizeof (struct find_cxx_sym_cache *)
334                   * (info->ent->ndepends + 1));
335   memset (cache, '\0', sizeof (struct find_cxx_sym_cache *)
336                        * (info->ent->ndepends + 1));
337   for (i = 0; i < info->conflict_rela_size; ++i)
338     {
339       size_t cidx;
340
341       reloc_type = GELF_R_TYPE (info->conflict_rela[i].r_info);
342       reloc_size = info->dso->arch->reloc_size (reloc_type);
343
344       if (GELF_R_SYM (info->conflict_rela[i].r_info) != 0)
345         continue;
346
347       if (state
348           && fcs1.sym.st_value <= info->conflict_rela[i].r_offset
349           && fcs1.sym.st_value + fcs1.sym.st_size
350              >= info->conflict_rela[i].r_offset + reloc_size)
351         {
352           if (state == 3)
353             goto remove_noref;
354           if (state == 2)
355             goto check_pltref;
356           continue;
357         }
358
359       n = find_cxx_sym (info, info->conflict_rela[i].r_offset,
360                         &fcs1, reloc_size, cache);
361
362       state = 0;
363       if (n == -1)
364         continue;
365       if (n == -2)
366         {
367           ret = 1;
368           goto out_free_cache;
369         }
370       state = 1;
371       sec = addr_to_sec (fcs1.dso, fcs1.sym.st_value);
372       if (sec == -1)
373         continue;
374       secname = strptr (fcs1.dso, fcs1.dso->ehdr.e_shstrndx,
375                         fcs1.dso->shdr[sec].sh_name);
376       if (secname == NULL)
377         continue;
378
379       name = (const char *) fcs1.strtab->d_buf + fcs1.sym.st_name;
380
381       for (k = 0; specials[k].prefix; ++k)
382         if (ELF32_ST_VISIBILITY (fcs1.sym.st_other) == STV_DEFAULT
383             && fcs1.sym.st_info == specials[k].st_info
384             && strncmp (name, specials[k].prefix, specials[k].prefix_len) == 0)
385           break;
386
387       if (specials[k].prefix == NULL)
388         continue;
389
390       if (strcmp (secname, ".data") != 0
391           && strcmp (secname, ".data.rel.ro") != 0
392           && strcmp (secname, ".sdata") != 0)
393         continue;
394
395       if (specials[k].check_pltref)
396         state = 2;
397
398       symtab_start = fcs1.dso->shdr[fcs1.symsec].sh_addr - fcs1.dso->base;
399       symoff = symtab_start + n * fcs1.dso->shdr[fcs1.symsec].sh_entsize;
400
401       cidx = 0;
402       if (info->conflicts[fcs1.n].hash != &info->conflicts[fcs1.n].first)
403         cidx = symoff % 251;
404       for (conflict = info->conflicts[fcs1.n].hash[cidx]; conflict;
405            conflict = conflict->next)
406         if (conflict->symoff == symoff
407             && conflict->reloc_class == rtype_class_valid)
408           break;
409
410       if (conflict == NULL)
411         goto check_pltref;
412
413       if (conflict->conflict.ent != fcs1.ent
414           || fcs1.dso->base + conflict->conflictval != fcs1.sym.st_value)
415         goto check_pltref;
416
417       if (verbose > 4)
418         error (0, 0, "Possible C++ conflict removal from unreferenced table at %s:%s+%d",
419                fcs1.dso->filename, name,
420                (int) (info->conflict_rela[i].r_offset - fcs1.sym.st_value));
421
422       /* Limit size slightly.  */
423       if (fcs1.sym.st_size > 16384)
424         goto check_pltref;
425
426       o = find_cxx_sym (info, conflict->lookup.ent->base + conflict->lookupval,
427                         &fcs2, fcs1.sym.st_size, cache);
428
429       if (o == -2)
430         {
431           ret = 1;
432           goto out_free_cache;
433         }
434
435       if (o == -1
436           || fcs1.sym.st_size != fcs2.sym.st_size
437           || fcs1.sym.st_info != fcs2.sym.st_info
438           || ELF32_ST_VISIBILITY (fcs2.sym.st_other) != STV_DEFAULT
439           || strcmp (name, (char *) fcs2.strtab->d_buf + fcs2.sym.st_name) != 0)
440         goto check_pltref;
441
442       mem1 = malloc (fcs1.sym.st_size * 2);
443       if (mem1 == NULL)
444         {
445           error (0, ENOMEM, "%s: Could not compare %s arrays",
446                  info->dso->filename, name);
447           ret = 1;
448           goto out_free_cache;
449         }
450
451       mem2 = mem1 + fcs1.sym.st_size;
452
453       if (get_relocated_mem (info, fcs1.dso, fcs1.sym.st_value, mem1,
454                              fcs1.sym.st_size, 0)
455           || get_relocated_mem (info, fcs2.dso, fcs2.sym.st_value, mem2,
456                                 fcs1.sym.st_size, 0)
457           || memcmp (mem1, mem2, fcs1.sym.st_size) != 0)
458         {
459           free (mem1);
460           goto check_pltref;
461         }
462
463       free (mem1);
464
465       state = 3;
466
467 remove_noref:
468       if (verbose > 3)
469         error (0, 0, "Removing C++ conflict from unreferenced table at %s:%s+%d",
470                fcs1.dso->filename, name,
471                (int) (info->conflict_rela[i].r_offset - fcs1.sym.st_value));
472
473       info->conflict_rela[i].r_info =
474         GELF_R_INFO (1, GELF_R_TYPE (info->conflict_rela[i].r_info));
475       ++removed;
476       continue;
477
478 check_pltref:
479       /* If the binary calls directly (or takes its address) one of the
480          methods in a virtual table, but doesn't define it, there is no
481          need to leave conflicts in the virtual table which will only
482          slow down the code (as it has to hop through binary's .plt
483          back to the method).  */
484       if (state != 2
485           || info->conflict_rela[i].r_addend < info->dso->base
486           || info->conflict_rela[i].r_addend >= info->dso->end
487           || binsymtab == NULL)
488         continue;
489
490       if (binsymcache == NULL)
491         {
492           binsymcache = create_cache (info->dso, 1);
493           if (binsymcache == NULL)
494             {
495               ret = 1;
496               goto out_free_cache;
497             }
498         }
499       if (binsymcache == (struct find_cxx_sym_cache *) -1UL)
500         continue;
501
502       lo = 0;
503       mid = 0;
504       hi = binsymcache->count;
505       while (lo < hi)
506         {
507           mid = (lo + hi) / 2;
508           if (binsymcache->vals[mid].start < info->conflict_rela[i].r_addend)
509             lo = mid + 1;
510           else if (binsymcache->vals[mid].start
511                    > info->conflict_rela[i].r_addend)
512             hi = mid;
513           else
514             break;
515         }
516       if (lo >= hi)
517         continue;
518
519       while (mid > 0 && binsymcache->vals[mid - 1].start
520                         == info->conflict_rela[i].r_addend)
521         --mid;
522
523       while (mid < binsymcache->count
524              && binsymcache->vals[mid].start
525                 == info->conflict_rela[i].r_addend)
526         {
527           GElf_Sym sym;
528
529           ndx = binsymcache->vals[mid].idx;
530           mid++;
531           gelfx_getsym (info->dso->elf, binsymtab, ndx, &sym);
532           assert (sym.st_value == info->conflict_rela[i].r_addend);
533           if (sym.st_shndx == SHN_UNDEF && sym.st_value)
534             {
535               struct prelink_symbol *s;
536               size_t maxidx, l;
537
538               if (verbose > 4)
539                 error (0, 0, "Possible C++ conflict removal due to reference to binary's .plt at %s:%s+%d",
540                        fcs1.dso->filename, name,
541                        (int) (info->conflict_rela[i].r_offset
542                               - fcs1.sym.st_value));
543
544               for (s = &info->symbols[ndx]; s; s = s->next)
545                 if (s->reloc_class == RTYPE_CLASS_PLT)
546                   break;
547
548               if (s == NULL)
549                 break;
550
551               maxidx = 1;
552               if (info->conflicts[fcs1.n].hash
553                   != &info->conflicts[fcs1.n].first)
554                 {
555                   if (info->conflicts[fcs1.n].hash2 == NULL)
556                     {
557                       info->conflicts[fcs1.n].hash2
558                         = calloc (sizeof (struct prelink_conflict *), 251);
559                       if (info->conflicts[fcs1.n].hash2 != NULL)
560                         {
561                           for (l = 0; l < 251; l++)
562                             for (conflict = info->conflicts[fcs1.n].hash[l];
563                                  conflict; conflict = conflict->next)
564                               if (conflict->reloc_class == rtype_class_valid
565                                   && conflict->conflict.ent)
566                                 {
567                                   size_t ccidx
568                                     = (conflict->lookup.ent->base
569                                        + conflict->lookupval) % 251;
570                                   conflict->next2
571                                     = info->conflicts[fcs1.n].hash2[ccidx];
572                                   info->conflicts[fcs1.n].hash2[ccidx]
573                                     = conflict;
574                                 }
575                         }
576                     }
577                   if (info->conflicts[fcs1.n].hash2 != NULL)
578                     {
579                       size_t ccidx = info->conflict_rela[i].r_addend % 251;
580                       for (conflict = info->conflicts[fcs1.n].hash2[ccidx];
581                            conflict; conflict = conflict->next2)
582                         if (conflict->lookup.ent->base + conflict->lookupval
583                             == info->conflict_rela[i].r_addend
584                             && (conflict->conflict.ent->base
585                                 + conflict->conflictval
586                                 == s->u.ent->base + s->value))
587                           goto pltref_remove;
588                       break;
589                     }
590                   maxidx = 251;
591                 }
592
593               for (l = 0; l < maxidx; l++)
594                 for (conflict = info->conflicts[fcs1.n].hash[l];
595                      conflict; conflict = conflict->next)
596                   if (conflict->lookup.ent->base + conflict->lookupval
597                       == info->conflict_rela[i].r_addend
598                       && conflict->conflict.ent
599                       && (conflict->conflict.ent->base
600                           + conflict->conflictval == s->u.ent->base + s->value)
601                       && conflict->reloc_class == rtype_class_valid)
602                     {
603 pltref_remove:
604                       if (verbose > 3)
605                         error (0, 0, "Removing C++ conflict due to reference to binary's .plt at %s:%s+%d",
606                                fcs1.dso->filename, name,
607                                (int) (info->conflict_rela[i].r_offset
608                                       - fcs1.sym.st_value));
609
610                       info->conflict_rela[i].r_info =
611                         GELF_R_INFO (1, GELF_R_TYPE (info->conflict_rela[i].r_info));
612                       ++removed;
613                       goto pltref_check_done;
614                     }
615
616 pltref_check_done:
617               break;
618             }
619         }
620     }
621
622   if (removed)
623     {
624       for (i = 0, j = 0; i < info->conflict_rela_size; ++i)
625         if (GELF_R_SYM (info->conflict_rela[i].r_info) == 0)
626           {
627             if (i != j)
628               info->conflict_rela[j] = info->conflict_rela[i];
629             ++j;
630           }
631       info->conflict_rela_size = j;
632     }
633
634 out_free_cache:
635   for (i = 0; i < info->ent->ndepends + 1; i++)
636     if (cache[i] && cache[i] != (struct find_cxx_sym_cache *) -1UL)
637       free (cache[i]);
638   if (binsymcache && binsymcache != (struct find_cxx_sym_cache *) -1UL)
639     free (binsymcache);
640   return ret;
641 }