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