libdwfl/segment.c

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