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