libdwfl/segment.c

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