LCOV - code coverage report
Current view: top level - libdwfl - segment.c (source / functions) Hit Total Coverage
Test: elfutils-0.175 Lines: 126 143 88.1 %
Date: 2018-11-16 13:02:39 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             : #ifdef HAVE_CONFIG_H
      30             : # include <config.h>
      31             : #endif
      32             : 
      33             : #include "libdwflP.h"
      34             : 
      35             : GElf_Addr
      36             : internal_function
      37        5798 : __libdwfl_segment_start (Dwfl *dwfl, GElf_Addr start)
      38             : {
      39       51710 :   if (dwfl->segment_align > 1)
      40       51633 :     start &= -dwfl->segment_align;
      41        5798 :   return start;
      42             : }
      43             : 
      44             : GElf_Addr
      45             : internal_function
      46        5798 : __libdwfl_segment_end (Dwfl *dwfl, GElf_Addr end)
      47             : {
      48       51710 :   if (dwfl->segment_align > 1)
      49       51633 :     end = (end + dwfl->segment_align - 1) & -dwfl->segment_align;
      50        5798 :   return end;
      51             : }
      52             : 
      53             : static bool
      54       35801 : insert (Dwfl *dwfl, size_t i, GElf_Addr start, GElf_Addr end, int segndx)
      55             : {
      56       35801 :   bool need_start = (i == 0 || dwfl->lookup_addr[i - 1] != start);
      57       71602 :   bool need_end = (i + 1 >= dwfl->lookup_elts
      58       35801 :                    || dwfl->lookup_addr[i + 1] != end);
      59       35801 :   size_t need = need_start + need_end;
      60       35801 :   if (need == 0)
      61             :     return false;
      62             : 
      63       35801 :   if (dwfl->lookup_alloc - dwfl->lookup_elts < need)
      64             :     {
      65        5142 :       size_t n = dwfl->lookup_alloc == 0 ? 16 : dwfl->lookup_alloc * 2;
      66        5142 :       GElf_Addr *naddr = realloc (dwfl->lookup_addr, sizeof naddr[0] * n);
      67        5142 :       if (unlikely (naddr == NULL))
      68             :         return true;
      69        5142 :       int *nsegndx = realloc (dwfl->lookup_segndx, sizeof nsegndx[0] * n);
      70        5142 :       if (unlikely (nsegndx == NULL))
      71             :         {
      72           0 :           if (naddr != dwfl->lookup_addr)
      73           0 :             free (naddr);
      74             :           return true;
      75             :         }
      76        5142 :       dwfl->lookup_alloc = n;
      77        5142 :       dwfl->lookup_addr = naddr;
      78        5142 :       dwfl->lookup_segndx = nsegndx;
      79             : 
      80        5142 :       if (dwfl->lookup_module != NULL)
      81             :         {
      82             :           /* Make sure this array is big enough too.  */
      83           2 :           Dwfl_Module **old = dwfl->lookup_module;
      84           2 :           dwfl->lookup_module = realloc (dwfl->lookup_module,
      85             :                                          sizeof dwfl->lookup_module[0] * n);
      86           2 :           if (unlikely (dwfl->lookup_module == NULL))
      87             :             {
      88           0 :               free (old);
      89           0 :               return true;
      90             :             }
      91             :         }
      92             :     }
      93             : 
      94       35801 :   if (unlikely (i < dwfl->lookup_elts))
      95             :     {
      96          22 :       const size_t move = dwfl->lookup_elts - i;
      97          44 :       memmove (&dwfl->lookup_addr[i + need], &dwfl->lookup_addr[i],
      98             :                move * sizeof dwfl->lookup_addr[0]);
      99          44 :       memmove (&dwfl->lookup_segndx[i + need], &dwfl->lookup_segndx[i],
     100             :                move * sizeof dwfl->lookup_segndx[0]);
     101          22 :       if (dwfl->lookup_module != NULL)
     102          19 :         memmove (&dwfl->lookup_module[i + need], &dwfl->lookup_module[i],
     103             :                  move * sizeof dwfl->lookup_module[0]);
     104             :     }
     105             : 
     106       35801 :   if (need_start)
     107             :     {
     108       35404 :       dwfl->lookup_addr[i] = start;
     109       35404 :       dwfl->lookup_segndx[i] = segndx;
     110       35404 :       if (dwfl->lookup_module != NULL)
     111       30045 :         dwfl->lookup_module[i] = NULL;
     112             :       ++i;
     113             :     }
     114             :   else
     115         397 :     dwfl->lookup_segndx[i - 1] = segndx;
     116             : 
     117       35801 :   if (need_end)
     118             :     {
     119       35801 :       dwfl->lookup_addr[i] = end;
     120       35801 :       dwfl->lookup_segndx[i] = -1;
     121       35801 :       if (dwfl->lookup_module != NULL)
     122       30045 :         dwfl->lookup_module[i] = NULL;
     123             :     }
     124             : 
     125       35801 :   dwfl->lookup_elts += need;
     126             : 
     127       35801 :   return false;
     128             : }
     129             : 
     130             : static int
     131       45227 : lookup (Dwfl *dwfl, GElf_Addr address, int hint)
     132             : {
     133       45227 :   if (hint >= 0
     134       30124 :       && address >= dwfl->lookup_addr[hint]
     135       30102 :       && ((size_t) hint + 1 == dwfl->lookup_elts
     136          75 :           || address < dwfl->lookup_addr[hint + 1]))
     137             :     return hint;
     138             : 
     139             :   /* Do binary search on the array indexed by module load address.  */
     140       21318 :   size_t l = 0, u = dwfl->lookup_elts;
     141       59903 :   while (l < u)
     142             :     {
     143       54831 :       size_t idx = (l + u) / 2;
     144       54831 :       if (address < dwfl->lookup_addr[idx])
     145             :         u = idx;
     146             :       else
     147             :         {
     148       36915 :           l = idx + 1;
     149       36915 :           if (l == dwfl->lookup_elts || address < dwfl->lookup_addr[l])
     150       16246 :             return idx;
     151             :         }
     152             :     }
     153             : 
     154             :   return -1;
     155             : }
     156             : 
     157             : static bool
     158        5177 : reify_segments (Dwfl *dwfl)
     159             : {
     160        5177 :   int hint = -1;
     161        5177 :   int highest = -1;
     162        5177 :   bool fixup = false;
     163       50404 :   for (Dwfl_Module *mod = dwfl->modulelist; mod != NULL; mod = mod->next)
     164       45227 :     if (! mod->gc)
     165             :       {
     166       90454 :         const GElf_Addr start = __libdwfl_segment_start (dwfl, mod->low_addr);
     167       90454 :         const GElf_Addr end = __libdwfl_segment_end (dwfl, mod->high_addr);
     168       45227 :         bool resized = false;
     169             : 
     170       45227 :         int idx = lookup (dwfl, start, hint);
     171       45227 :         if (unlikely (idx < 0))
     172             :           {
     173             :             /* Module starts below any segment.  Insert a low one.  */
     174        5070 :             if (unlikely (insert (dwfl, 0, start, end, -1)))
     175             :               return true;
     176             :             idx = 0;
     177             :             resized = true;
     178             :           }
     179       40157 :         else if (dwfl->lookup_addr[idx] > start)
     180             :           {
     181             :             /* The module starts in the middle of this segment.  Split it.  */
     182           0 :             if (unlikely (insert (dwfl, idx + 1, start, end,
     183             :                                   dwfl->lookup_segndx[idx])))
     184             :               return true;
     185             :             ++idx;
     186             :             resized = true;
     187             :           }
     188       40157 :         else if (dwfl->lookup_addr[idx] < start)
     189             :           {
     190             :             /* The module starts past the end of this segment.
     191             :                Add a new one.  */
     192       30027 :             if (unlikely (insert (dwfl, idx + 1, start, end, -1)))
     193             :               return true;
     194             :             ++idx;
     195             :             resized = true;
     196             :           }
     197             : 
     198       45227 :         if ((size_t) idx + 1 < dwfl->lookup_elts
     199       35224 :             && end < dwfl->lookup_addr[idx + 1])
     200             :           {
     201             :             /* The module ends in the middle of this segment.  Split it.  */
     202          19 :             if (unlikely (insert (dwfl, idx + 1,
     203             :                                   end, dwfl->lookup_addr[idx + 1], -1)))
     204             :               return true;
     205             :             resized = true;
     206             :           }
     207             : 
     208       45227 :         if (dwfl->lookup_module == NULL)
     209             :           {
     210        5101 :             dwfl->lookup_module = calloc (dwfl->lookup_alloc,
     211             :                                           sizeof dwfl->lookup_module[0]);
     212        5101 :             if (unlikely (dwfl->lookup_module == NULL))
     213             :               return true;
     214             :           }
     215             : 
     216             :         /* Cache a backpointer in the module.  */
     217       45227 :         mod->segment = idx;
     218             : 
     219             :         /* Put MOD in the table for each segment that's inside it.  */
     220             :         do
     221       45558 :           dwfl->lookup_module[idx++] = mod;
     222       45558 :         while ((size_t) idx < dwfl->lookup_elts
     223       45558 :                && dwfl->lookup_addr[idx] < end);
     224       45227 :         assert (dwfl->lookup_module[mod->segment] == mod);
     225             : 
     226       45227 :         if (resized && idx - 1 >= highest)
     227             :           /* Expanding the lookup tables invalidated backpointers
     228             :              we've already stored.  Reset those ones.  */
     229       35116 :           fixup = true;
     230             : 
     231       45227 :         highest = idx - 1;
     232       45227 :         hint = (size_t) idx < dwfl->lookup_elts ? idx : -1;
     233             :       }
     234             : 
     235        5177 :   if (fixup)
     236             :     /* Reset backpointer indices invalidated by table insertions.  */
     237       70872 :     for (size_t idx = 0; idx < dwfl->lookup_elts; ++idx)
     238       70872 :       if (dwfl->lookup_module[idx] != NULL)
     239       45463 :         dwfl->lookup_module[idx]->segment = idx;
     240             : 
     241             :   return false;
     242             : }
     243             : 
     244             : int
     245        6122 : dwfl_addrsegment (Dwfl *dwfl, Dwarf_Addr address, Dwfl_Module **mod)
     246             : {
     247        6122 :   if (unlikely (dwfl == NULL))
     248             :     return -1;
     249             : 
     250        6122 :   if (unlikely (dwfl->lookup_module == NULL)
     251        5469 :       && mod != NULL
     252        5177 :       && unlikely (reify_segments (dwfl)))
     253             :     {
     254           0 :       __libdwfl_seterrno (DWFL_E_NOMEM);
     255           0 :       return -1;
     256             :     }
     257             : 
     258       12244 :   int idx = lookup (dwfl, address, -1);
     259        6122 :   if (likely (mod != NULL))
     260             :     {
     261        5830 :       if (unlikely (idx < 0) || unlikely (dwfl->lookup_module == NULL))
     262          78 :         *mod = NULL;
     263             :       else
     264             :         {
     265        5752 :           *mod = dwfl->lookup_module[idx];
     266             : 
     267             :           /* If this segment does not have a module, but the address is
     268             :              the upper boundary of the previous segment's module, use that.  */
     269        5752 :           if (*mod == NULL && idx > 0 && dwfl->lookup_addr[idx] == address)
     270             :             {
     271           2 :               *mod = dwfl->lookup_module[idx - 1];
     272           2 :               if (*mod != NULL && (*mod)->high_addr != address)
     273           0 :                 *mod = NULL;
     274             :             }
     275             :         }
     276             :     }
     277             : 
     278        6122 :   if (likely (idx >= 0))
     279             :     /* Translate internal segment table index to user segment index.  */
     280        6120 :     idx = dwfl->lookup_segndx[idx];
     281             : 
     282             :   return idx;
     283             : }
     284             : INTDEF (dwfl_addrsegment)
     285             : 
     286             : int
     287         685 : dwfl_report_segment (Dwfl *dwfl, int ndx, const GElf_Phdr *phdr, GElf_Addr bias,
     288             :                      const void *ident)
     289             : {
     290         685 :   if (dwfl == NULL)
     291             :     return -1;
     292             : 
     293         685 :   if (ndx < 0)
     294           0 :     ndx = dwfl->lookup_tail_ndx;
     295             : 
     296         685 :   if (phdr->p_align > 1 && (dwfl->segment_align <= 1 ||
     297             :                             phdr->p_align < dwfl->segment_align))
     298          36 :     dwfl->segment_align = phdr->p_align;
     299             : 
     300         685 :   if (unlikely (dwfl->lookup_module != NULL))
     301             :     {
     302           0 :       free (dwfl->lookup_module);
     303           0 :       dwfl->lookup_module = NULL;
     304             :     }
     305             : 
     306        1370 :   GElf_Addr start = __libdwfl_segment_start (dwfl, bias + phdr->p_vaddr);
     307        1370 :   GElf_Addr end = __libdwfl_segment_end (dwfl,
     308         685 :                                          bias + phdr->p_vaddr + phdr->p_memsz);
     309             : 
     310             :   /* Coalesce into the last one if contiguous and matching.  */
     311         685 :   if (ndx != dwfl->lookup_tail_ndx
     312         649 :       || ident == NULL
     313           0 :       || ident != dwfl->lookup_tail_ident
     314           0 :       || start != dwfl->lookup_tail_vaddr
     315           0 :       || phdr->p_offset != dwfl->lookup_tail_offset)
     316             :     {
     317             :       /* Normally just appending keeps us sorted.  */
     318             : 
     319         685 :       size_t i = dwfl->lookup_elts;
     320        1370 :       while (i > 0 && unlikely (start < dwfl->lookup_addr[i - 1]))
     321           0 :         --i;
     322             : 
     323         685 :       if (unlikely (insert (dwfl, i, start, end, ndx)))
     324             :         {
     325           0 :           __libdwfl_seterrno (DWFL_E_NOMEM);
     326           0 :           return -1;
     327             :         }
     328             :     }
     329             : 
     330         685 :   dwfl->lookup_tail_ident = ident;
     331         685 :   dwfl->lookup_tail_vaddr = end;
     332         685 :   dwfl->lookup_tail_offset = end - bias - phdr->p_vaddr + phdr->p_offset;
     333         685 :   dwfl->lookup_tail_ndx = ndx + 1;
     334             : 
     335         685 :   return ndx;
     336             : }
     337             : INTDEF (dwfl_report_segment)

Generated by: LCOV version 1.13