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
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 + 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
126static int
127lookup (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
153static bool
154reify_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
240int
241dwfl_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}
280INTDEF (dwfl_addrsegment)
281
282int
283dwfl_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}
333INTDEF (dwfl_report_segment)
334