LCOV - code coverage report
Current view: top level - libdwfl - segment.c (source / functions) Hit Total Coverage
Test: lcov.out Lines: 126 143 88.1 %
Date: 2017-01-05 09:15:16 Functions: 7 7 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* Manage address space lookup table for libdwfl.
       2             :    Copyright (C) 2008, 2009, 2010, 2013, 2015 Red Hat, Inc.
       3             :    This file is part of elfutils.
       4             : 
       5             :    This file is free software; you can redistribute it and/or modify
       6             :    it under the terms of either
       7             : 
       8             :      * the GNU Lesser General Public License as published by the Free
       9             :        Software Foundation; either version 3 of the License, or (at
      10             :        your option) any later version
      11             : 
      12             :    or
      13             : 
      14             :      * the GNU General Public License as published by the Free
      15             :        Software Foundation; either version 2 of the License, or (at
      16             :        your option) any later version
      17             : 
      18             :    or both in parallel, as here.
      19             : 
      20             :    elfutils is distributed in the hope that it will be useful, but
      21             :    WITHOUT ANY WARRANTY; without even the implied warranty of
      22             :    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
      23             :    General Public License for more details.
      24             : 
      25             :    You should have received copies of the GNU General Public License and
      26             :    the GNU Lesser General Public License along with this program.  If
      27             :    not, see <http://www.gnu.org/licenses/>.  */
      28             : 
      29             : #include "libdwflP.h"
      30             : 
      31             : GElf_Addr
      32             : internal_function
      33        3271 : __libdwfl_segment_start (Dwfl *dwfl, GElf_Addr start)
      34             : {
      35       49071 :   if (dwfl->segment_align > 1)
      36       48994 :     start &= -dwfl->segment_align;
      37        3271 :   return start;
      38             : }
      39             : 
      40             : GElf_Addr
      41             : internal_function
      42        3271 : __libdwfl_segment_end (Dwfl *dwfl, GElf_Addr end)
      43             : {
      44       49071 :   if (dwfl->segment_align > 1)
      45       48994 :     end = (end + dwfl->segment_align - 1) & -dwfl->segment_align;
      46        3271 :   return end;
      47             : }
      48             : 
      49             : static bool
      50       35705 : insert (Dwfl *dwfl, size_t i, GElf_Addr start, GElf_Addr end, int segndx)
      51             : {
      52       35705 :   bool need_start = (i == 0 || dwfl->lookup_addr[i - 1] != start);
      53       71410 :   bool need_end = (i + 1 >= dwfl->lookup_elts
      54       35705 :                    || dwfl->lookup_addr[i + 1] != end);
      55       35705 :   size_t need = need_start + need_end;
      56       35705 :   if (need == 0)
      57             :     return false;
      58             : 
      59       35705 :   if (dwfl->lookup_alloc - dwfl->lookup_elts < need)
      60             :     {
      61        5131 :       size_t n = dwfl->lookup_alloc == 0 ? 16 : dwfl->lookup_alloc * 2;
      62        5131 :       GElf_Addr *naddr = realloc (dwfl->lookup_addr, sizeof naddr[0] * n);
      63        5131 :       if (unlikely (naddr == NULL))
      64             :         return true;
      65        5131 :       int *nsegndx = realloc (dwfl->lookup_segndx, sizeof nsegndx[0] * n);
      66        5131 :       if (unlikely (nsegndx == NULL))
      67             :         {
      68           0 :           if (naddr != dwfl->lookup_addr)
      69           0 :             free (naddr);
      70             :           return true;
      71             :         }
      72        5131 :       dwfl->lookup_alloc = n;
      73        5131 :       dwfl->lookup_addr = naddr;
      74        5131 :       dwfl->lookup_segndx = nsegndx;
      75             : 
      76        5131 :       if (dwfl->lookup_module != NULL)
      77             :         {
      78             :           /* Make sure this array is big enough too.  */
      79           2 :           Dwfl_Module **old = dwfl->lookup_module;
      80           2 :           dwfl->lookup_module = realloc (dwfl->lookup_module,
      81             :                                          sizeof dwfl->lookup_module[0] * n);
      82           2 :           if (unlikely (dwfl->lookup_module == NULL))
      83             :             {
      84           0 :               free (old);
      85           0 :               return true;
      86             :             }
      87             :         }
      88             :     }
      89             : 
      90       35705 :   if (unlikely (i < dwfl->lookup_elts))
      91             :     {
      92          21 :       const size_t move = dwfl->lookup_elts - i;
      93          21 :       memmove (&dwfl->lookup_addr[i + need], &dwfl->lookup_addr[i],
      94             :                move * sizeof dwfl->lookup_addr[0]);
      95          21 :       memmove (&dwfl->lookup_segndx[i + need], &dwfl->lookup_segndx[i],
      96             :                move * sizeof dwfl->lookup_segndx[0]);
      97          21 :       if (dwfl->lookup_module != NULL)
      98          18 :         memmove (&dwfl->lookup_module[i + need], &dwfl->lookup_module[i],
      99             :                  move * sizeof dwfl->lookup_module[0]);
     100             :     }
     101             : 
     102       35705 :   if (need_start)
     103             :     {
     104       35369 :       dwfl->lookup_addr[i] = start;
     105       35369 :       dwfl->lookup_segndx[i] = segndx;
     106       35369 :       if (dwfl->lookup_module != NULL)
     107       30044 :         dwfl->lookup_module[i] = NULL;
     108             :       ++i;
     109             :     }
     110             :   else
     111         336 :     dwfl->lookup_segndx[i - 1] = segndx;
     112             : 
     113       35705 :   if (need_end)
     114             :     {
     115       35705 :       dwfl->lookup_addr[i] = end;
     116       35705 :       dwfl->lookup_segndx[i] = -1;
     117       35705 :       if (dwfl->lookup_module != NULL)
     118       30044 :         dwfl->lookup_module[i] = NULL;
     119             :     }
     120             : 
     121       35705 :   dwfl->lookup_elts += need;
     122             : 
     123       35705 :   return false;
     124             : }
     125             : 
     126             : static int
     127       45210 : lookup (Dwfl *dwfl, GElf_Addr address, int hint)
     128             : {
     129       45210 :   if (hint >= 0
     130       30113 :       && address >= dwfl->lookup_addr[hint]
     131       30096 :       && ((size_t) hint + 1 == dwfl->lookup_elts
     132          69 :           || address < dwfl->lookup_addr[hint + 1]))
     133             :     return hint;
     134             : 
     135             :   /* Do binary search on the array indexed by module load address.  */
     136       21153 :   size_t l = 0, u = dwfl->lookup_elts;
     137       59188 :   while (l < u)
     138             :     {
     139       54116 :       size_t idx = (l + u) / 2;
     140       54116 :       if (address < dwfl->lookup_addr[idx])
     141             :         u = idx;
     142             :       else
     143             :         {
     144       36722 :           l = idx + 1;
     145       36722 :           if (l == dwfl->lookup_elts || address < dwfl->lookup_addr[l])
     146       16081 :             return idx;
     147             :         }
     148             :     }
     149             : 
     150             :   return -1;
     151             : }
     152             : 
     153             : static bool
     154        5166 : reify_segments (Dwfl *dwfl)
     155             : {
     156        5166 :   int hint = -1;
     157        5166 :   int highest = -1;
     158        5166 :   bool fixup = false;
     159       50376 :   for (Dwfl_Module *mod = dwfl->modulelist; mod != NULL; mod = mod->next)
     160       45210 :     if (! mod->gc)
     161             :       {
     162       90420 :         const GElf_Addr start = __libdwfl_segment_start (dwfl, mod->low_addr);
     163       90420 :         const GElf_Addr end = __libdwfl_segment_end (dwfl, mod->high_addr);
     164       45210 :         bool resized = false;
     165             : 
     166       45210 :         int idx = lookup (dwfl, start, hint);
     167       45210 :         if (unlikely (idx < 0))
     168             :           {
     169             :             /* Module starts below any segment.  Insert a low one.  */
     170        5070 :             if (unlikely (insert (dwfl, 0, start, end, -1)))
     171             :               return true;
     172             :             idx = 0;
     173             :             resized = true;
     174             :           }
     175       40140 :         else if (dwfl->lookup_addr[idx] > start)
     176             :           {
     177             :             /* The module starts in the middle of this segment.  Split it.  */
     178           0 :             if (unlikely (insert (dwfl, idx + 1, start, end,
     179             :                                   dwfl->lookup_segndx[idx])))
     180             :               return true;
     181             :             ++idx;
     182             :             resized = true;
     183             :           }
     184       40140 :         else if (dwfl->lookup_addr[idx] < start)
     185             :           {
     186             :             /* The module starts past the end of this segment.
     187             :                Add a new one.  */
     188       30028 :             if (unlikely (insert (dwfl, idx + 1, start, end, -1)))
     189             :               return true;
     190             :             ++idx;
     191             :             resized = true;
     192             :           }
     193             : 
     194       45210 :         if ((size_t) idx + 1 < dwfl->lookup_elts
     195       35207 :             && end < dwfl->lookup_addr[idx + 1])
     196             :           {
     197             :             /* The module ends in the middle of this segment.  Split it.  */
     198          17 :             if (unlikely (insert (dwfl, idx + 1,
     199             :                                   end, dwfl->lookup_addr[idx + 1], -1)))
     200             :               return true;
     201             :             resized = true;
     202             :           }
     203             : 
     204       45210 :         if (dwfl->lookup_module == NULL)
     205             :           {
     206        5095 :             dwfl->lookup_module = calloc (dwfl->lookup_alloc,
     207             :                                           sizeof dwfl->lookup_module[0]);
     208        5095 :             if (unlikely (dwfl->lookup_module == NULL))
     209             :               return true;
     210             :           }
     211             : 
     212             :         /* Cache a backpointer in the module.  */
     213       45210 :         mod->segment = idx;
     214             : 
     215             :         /* Put MOD in the table for each segment that's inside it.  */
     216             :         do
     217       45490 :           dwfl->lookup_module[idx++] = mod;
     218       45490 :         while ((size_t) idx < dwfl->lookup_elts
     219       45490 :                && dwfl->lookup_addr[idx] < end);
     220       45210 :         assert (dwfl->lookup_module[mod->segment] == mod);
     221             : 
     222       45210 :         if (resized && idx - 1 >= highest)
     223             :           /* Expanding the lookup tables invalidated backpointers
     224             :              we've already stored.  Reset those ones.  */
     225       35114 :           fixup = true;
     226             : 
     227       45210 :         highest = idx - 1;
     228       45210 :         hint = (size_t) idx < dwfl->lookup_elts ? idx : -1;
     229             :       }
     230             : 
     231        5166 :   if (fixup)
     232             :     /* Reset backpointer indices invalidated by table insertions.  */
     233       70846 :     for (size_t idx = 0; idx < dwfl->lookup_elts; ++idx)
     234       70846 :       if (dwfl->lookup_module[idx] != NULL)
     235       45456 :         dwfl->lookup_module[idx]->segment = idx;
     236             : 
     237             :   return false;
     238             : }
     239             : 
     240             : int
     241        5971 : dwfl_addrsegment (Dwfl *dwfl, Dwarf_Addr address, Dwfl_Module **mod)
     242             : {
     243        5971 :   if (unlikely (dwfl == NULL))
     244             :     return -1;
     245             : 
     246        5971 :   if (unlikely (dwfl->lookup_module == NULL)
     247        5484 :       && mod != NULL
     248        5166 :       && unlikely (reify_segments (dwfl)))
     249             :     {
     250           0 :       __libdwfl_seterrno (DWFL_E_NOMEM);
     251           0 :       return -1;
     252             :     }
     253             : 
     254       11942 :   int idx = lookup (dwfl, address, -1);
     255        5971 :   if (likely (mod != NULL))
     256             :     {
     257        5653 :       if (unlikely (idx < 0) || unlikely (dwfl->lookup_module == NULL))
     258          73 :         *mod = NULL;
     259             :       else
     260             :         {
     261        5580 :           *mod = dwfl->lookup_module[idx];
     262             : 
     263             :           /* If this segment does not have a module, but the address is
     264             :              the upper boundary of the previous segment's module, use that.  */
     265        5580 :           if (*mod == NULL && idx > 0 && dwfl->lookup_addr[idx] == address)
     266             :             {
     267           2 :               *mod = dwfl->lookup_module[idx - 1];
     268           2 :               if (*mod != NULL && (*mod)->high_addr != address)
     269           0 :                 *mod = NULL;
     270             :             }
     271             :         }
     272             :     }
     273             : 
     274        5971 :   if (likely (idx >= 0))
     275             :     /* Translate internal segment table index to user segment index.  */
     276        5969 :     idx = dwfl->lookup_segndx[idx];
     277             : 
     278             :   return idx;
     279             : }
     280             : INTDEF (dwfl_addrsegment)
     281             : 
     282             : int
     283         590 : dwfl_report_segment (Dwfl *dwfl, int ndx, const GElf_Phdr *phdr, GElf_Addr bias,
     284             :                      const void *ident)
     285             : {
     286         590 :   if (dwfl == NULL)
     287             :     return -1;
     288             : 
     289         590 :   if (ndx < 0)
     290           0 :     ndx = dwfl->lookup_tail_ndx;
     291             : 
     292         590 :   if (phdr->p_align > 1 && (dwfl->segment_align <= 1 ||
     293             :                             phdr->p_align < dwfl->segment_align))
     294          30 :     dwfl->segment_align = phdr->p_align;
     295             : 
     296         590 :   if (unlikely (dwfl->lookup_module != NULL))
     297             :     {
     298           0 :       free (dwfl->lookup_module);
     299           0 :       dwfl->lookup_module = NULL;
     300             :     }
     301             : 
     302        1180 :   GElf_Addr start = __libdwfl_segment_start (dwfl, bias + phdr->p_vaddr);
     303        1180 :   GElf_Addr end = __libdwfl_segment_end (dwfl,
     304         590 :                                          bias + phdr->p_vaddr + phdr->p_memsz);
     305             : 
     306             :   /* Coalesce into the last one if contiguous and matching.  */
     307         590 :   if (ndx != dwfl->lookup_tail_ndx
     308         560 :       || ident == NULL
     309           0 :       || ident != dwfl->lookup_tail_ident
     310           0 :       || start != dwfl->lookup_tail_vaddr
     311           0 :       || phdr->p_offset != dwfl->lookup_tail_offset)
     312             :     {
     313             :       /* Normally just appending keeps us sorted.  */
     314             : 
     315         590 :       size_t i = dwfl->lookup_elts;
     316        1180 :       while (i > 0 && unlikely (start < dwfl->lookup_addr[i - 1]))
     317           0 :         --i;
     318             : 
     319         590 :       if (unlikely (insert (dwfl, i, start, end, ndx)))
     320             :         {
     321           0 :           __libdwfl_seterrno (DWFL_E_NOMEM);
     322           0 :           return -1;
     323             :         }
     324             :     }
     325             : 
     326         590 :   dwfl->lookup_tail_ident = ident;
     327         590 :   dwfl->lookup_tail_vaddr = end;
     328         590 :   dwfl->lookup_tail_offset = end - bias - phdr->p_vaddr + phdr->p_offset;
     329         590 :   dwfl->lookup_tail_ndx = ndx + 1;
     330             : 
     331         590 :   return ndx;
     332             : }
     333             : INTDEF (dwfl_report_segment)

Generated by: LCOV version 1.12