1/* Manage address space lookup table for libdwfl.
2   Copyright (C) 2008, 2009, 2010 Red Hat, Inc.
3   This file is part of Red Hat elfutils.
4
5   Red Hat elfutils is free software; you can redistribute it and/or modify
6   it under the terms of the GNU General Public License as published by the
7   Free Software Foundation; version 2 of the License.
8
9   Red Hat elfutils is distributed in the hope that it will be useful, but
10   WITHOUT ANY WARRANTY; without even the implied warranty of
11   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12   General Public License for more details.
13
14   You should have received a copy of the GNU General Public License along
15   with Red Hat elfutils; if not, write to the Free Software Foundation,
16   Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301 USA.
17
18   In addition, as a special exception, Red Hat, Inc. gives You the
19   additional right to link the code of Red Hat elfutils with code licensed
20   under any Open Source Initiative certified open source license
21   (http://www.opensource.org/licenses/index.php) which requires the
22   distribution of source code with any binary distribution and to
23   distribute linked combinations of the two.  Non-GPL Code permitted under
24   this exception must only link to the code of Red Hat elfutils through
25   those well defined interfaces identified in the file named EXCEPTION
26   found in the source code files (the "Approved Interfaces").  The files
27   of Non-GPL Code may instantiate templates or use macros or inline
28   functions from the Approved Interfaces without causing the resulting
29   work to be covered by the GNU General Public License.  Only Red Hat,
30   Inc. may make changes or additions to the list of Approved Interfaces.
31   Red Hat's grant of this exception is conditioned upon your not adding
32   any new exceptions.  If you wish to add a new Approved Interface or
33   exception, please contact Red Hat.  You must obey the GNU General Public
34   License in all respects for all of the Red Hat elfutils code and other
35   code used in conjunction with Red Hat elfutils except the Non-GPL Code
36   covered by this exception.  If you modify this file, you may extend this
37   exception to your version of the file, but you are not obligated to do
38   so.  If you do not wish to provide this exception without modification,
39   you must delete this exception statement from your version and license
40   this file solely under the GPL without exception.
41
42   Red Hat elfutils is an included package of the Open Invention Network.
43   An included package of the Open Invention Network is a package for which
44   Open Invention Network licensees cross-license their patents.  No patent
45   license is granted, either expressly or impliedly, by designation as an
46   included package.  Should you wish to participate in the Open Invention
47   Network licensing program, please visit www.openinventionnetwork.com
48   <http://www.openinventionnetwork.com>.  */
49
50#include "libdwflP.h"
51
52static GElf_Addr
53segment_start (Dwfl *dwfl, GElf_Addr start)
54{
55  if (dwfl->segment_align > 1)
56    start &= -dwfl->segment_align;
57  return start;
58}
59
60static GElf_Addr
61segment_end (Dwfl *dwfl, GElf_Addr end)
62{
63  if (dwfl->segment_align > 1)
64    end = (end + dwfl->segment_align - 1) & -dwfl->segment_align;
65  return end;
66}
67
68static bool
69insert (Dwfl *dwfl, size_t i, GElf_Addr start, GElf_Addr end, int segndx)
70{
71  bool need_start = (i == 0 || dwfl->lookup_addr[i - 1] != start);
72  bool need_end = (i >= dwfl->lookup_elts || dwfl->lookup_addr[i + 1] != end);
73  size_t need = need_start + need_end;
74  if (need == 0)
75    return false;
76
77  if (dwfl->lookup_alloc - dwfl->lookup_elts < need)
78    {
79      size_t n = dwfl->lookup_alloc == 0 ? 16 : dwfl->lookup_alloc * 2;
80      GElf_Addr *naddr = realloc (dwfl->lookup_addr, sizeof naddr[0] * n);
81      if (unlikely (naddr == NULL))
82	return true;
83      int *nsegndx = realloc (dwfl->lookup_segndx, sizeof nsegndx[0] * n);
84      if (unlikely (nsegndx == NULL))
85	{
86	  if (naddr != dwfl->lookup_addr)
87	    free (naddr);
88	  return true;
89	}
90      dwfl->lookup_alloc = n;
91      dwfl->lookup_addr = naddr;
92      dwfl->lookup_segndx = nsegndx;
93
94      if (dwfl->lookup_module != NULL)
95	{
96	  /* Make sure this array is big enough too.  */
97	  Dwfl_Module **old = dwfl->lookup_module;
98	  dwfl->lookup_module = realloc (dwfl->lookup_module,
99					 sizeof dwfl->lookup_module[0] * n);
100	  if (unlikely (dwfl->lookup_module == NULL))
101	    {
102	      free (old);
103	      return true;
104	    }
105	}
106    }
107
108  if (unlikely (i < dwfl->lookup_elts))
109    {
110      const size_t move = dwfl->lookup_elts - i;
111      memmove (&dwfl->lookup_addr[i + need], &dwfl->lookup_addr[i],
112	       move * sizeof dwfl->lookup_addr[0]);
113      memmove (&dwfl->lookup_segndx[i + need], &dwfl->lookup_segndx[i],
114	       move * sizeof dwfl->lookup_segndx[0]);
115      if (dwfl->lookup_module != NULL)
116	memmove (&dwfl->lookup_module[i + need], &dwfl->lookup_module[i],
117		 move * sizeof dwfl->lookup_module[0]);
118    }
119
120  if (need_start)
121    {
122      dwfl->lookup_addr[i] = start;
123      dwfl->lookup_segndx[i] = segndx;
124      if (dwfl->lookup_module != NULL)
125	dwfl->lookup_module[i] = NULL;
126      ++i;
127    }
128  else
129    dwfl->lookup_segndx[i - 1] = segndx;
130
131  if (need_end)
132    {
133      dwfl->lookup_addr[i] = end;
134      dwfl->lookup_segndx[i] = -1;
135      if (dwfl->lookup_module != NULL)
136	dwfl->lookup_module[i] = NULL;
137    }
138
139  dwfl->lookup_elts += need;
140
141  return false;
142}
143
144static int
145lookup (Dwfl *dwfl, GElf_Addr address, int hint)
146{
147  if (hint >= 0
148      && address >= dwfl->lookup_addr[hint]
149      && ((size_t) hint + 1 == dwfl->lookup_elts
150	  || address < dwfl->lookup_addr[hint + 1]))
151    return hint;
152
153  /* Do binary search on the array indexed by module load address.  */
154  size_t l = 0, u = dwfl->lookup_elts;
155  while (l < u)
156    {
157      size_t idx = (l + u) / 2;
158      if (address < dwfl->lookup_addr[idx])
159	u = idx;
160      else
161	{
162	  l = idx + 1;
163	  if (l == dwfl->lookup_elts || address < dwfl->lookup_addr[l])
164	    return idx;
165	}
166    }
167
168  return -1;
169}
170
171static bool
172reify_segments (Dwfl *dwfl)
173{
174  int hint = -1;
175  int highest = -1;
176  bool fixup = false;
177  for (Dwfl_Module *mod = dwfl->modulelist; mod != NULL; mod = mod->next)
178    if (! mod->gc)
179      {
180	const GElf_Addr start = segment_start (dwfl, mod->low_addr);
181	const GElf_Addr end = segment_end (dwfl, mod->high_addr);
182	bool resized = false;
183
184	int idx = lookup (dwfl, start, hint);
185	if (unlikely (idx < 0))
186	  {
187	    /* Module starts below any segment.  Insert a low one.  */
188	    if (unlikely (insert (dwfl, 0, start, end, -1)))
189	      return true;
190	    idx = 0;
191	    resized = true;
192	  }
193	else if (dwfl->lookup_addr[idx] > start)
194	  {
195	    /* The module starts in the middle of this segment.  Split it.  */
196	    if (unlikely (insert (dwfl, idx + 1, start, end,
197				  dwfl->lookup_segndx[idx])))
198	      return true;
199	    ++idx;
200	    resized = true;
201	  }
202	else if (dwfl->lookup_addr[idx] < start)
203	  {
204	    /* The module starts past the end of this segment.
205	       Add a new one.  */
206	    if (unlikely (insert (dwfl, idx + 1, start, end, -1)))
207	      return true;
208	    ++idx;
209	    resized = true;
210	  }
211
212	if ((size_t) idx + 1 < dwfl->lookup_elts
213	    && end < dwfl->lookup_addr[idx + 1])
214	  {
215	    /* The module ends in the middle of this segment.  Split it.  */
216	    if (unlikely (insert (dwfl, idx + 1,
217				  end, dwfl->lookup_addr[idx + 1], -1)))
218	      return true;
219	    resized = true;
220	  }
221
222	if (dwfl->lookup_module == NULL)
223	  {
224	    dwfl->lookup_module = calloc (dwfl->lookup_alloc,
225					  sizeof dwfl->lookup_module[0]);
226	    if (unlikely (dwfl->lookup_module == NULL))
227	      return true;
228	  }
229
230	/* Cache a backpointer in the module.  */
231	mod->segment = idx;
232
233	/* Put MOD in the table for each segment that's inside it.  */
234	do
235	  dwfl->lookup_module[idx++] = mod;
236	while ((size_t) idx < dwfl->lookup_elts
237	       && dwfl->lookup_addr[idx] < end);
238	assert (dwfl->lookup_module[mod->segment] == mod);
239
240	if (resized && idx - 1 >= highest)
241	  /* Expanding the lookup tables invalidated backpointers
242	     we've already stored.  Reset those ones.  */
243	  fixup = true;
244
245	highest = idx - 1;
246	hint = (size_t) idx < dwfl->lookup_elts ? idx : -1;
247      }
248
249  if (fixup)
250    /* Reset backpointer indices invalidated by table insertions.  */
251    for (size_t idx = 0; idx < dwfl->lookup_elts; ++idx)
252      if (dwfl->lookup_module[idx] != NULL)
253	dwfl->lookup_module[idx]->segment = idx;
254
255  return false;
256}
257
258int
259dwfl_addrsegment (Dwfl *dwfl, Dwarf_Addr address, Dwfl_Module **mod)
260{
261  if (unlikely (dwfl == NULL))
262    return -1;
263
264  if (unlikely (dwfl->lookup_module == NULL)
265      && mod != NULL
266      && unlikely (reify_segments (dwfl)))
267    {
268      __libdwfl_seterrno (DWFL_E_NOMEM);
269      return -1;
270    }
271
272  int idx = lookup (dwfl, address, -1);
273  if (likely (mod != NULL))
274    {
275      if (unlikely (idx < 0) || unlikely (dwfl->lookup_module == NULL))
276	*mod = NULL;
277      else
278	{
279	  *mod = dwfl->lookup_module[idx];
280
281	  /* If this segment does not have a module, but the address is
282	     the upper boundary of the previous segment's module, use that.  */
283	  if (*mod == NULL && idx > 0 && dwfl->lookup_addr[idx] == address)
284	    {
285	      *mod = dwfl->lookup_module[idx - 1];
286	      if (*mod != NULL && (*mod)->high_addr != address)
287		*mod = NULL;
288	    }
289	}
290    }
291
292  if (likely (idx >= 0))
293    /* Translate internal segment table index to user segment index.  */
294    idx = dwfl->lookup_segndx[idx];
295
296  return idx;
297}
298INTDEF (dwfl_addrsegment)
299
300int
301dwfl_report_segment (Dwfl *dwfl, int ndx, const GElf_Phdr *phdr, GElf_Addr bias,
302		     const void *ident)
303{
304  if (dwfl == NULL)
305    return -1;
306
307  if (ndx < 0)
308    ndx = dwfl->lookup_tail_ndx;
309
310  if (phdr->p_align > 1 && (dwfl->segment_align <= 1 ||
311			    phdr->p_align < dwfl->segment_align))
312    dwfl->segment_align = phdr->p_align;
313
314  if (unlikely (dwfl->lookup_module != NULL))
315    {
316      free (dwfl->lookup_module);
317      dwfl->lookup_module = NULL;
318    }
319
320  GElf_Addr start = segment_start (dwfl, bias + phdr->p_vaddr);
321  GElf_Addr end = segment_end (dwfl, bias + phdr->p_vaddr + phdr->p_memsz);
322
323  /* Coalesce into the last one if contiguous and matching.  */
324  if (ndx != dwfl->lookup_tail_ndx
325      || ident == NULL
326      || ident != dwfl->lookup_tail_ident
327      || start != dwfl->lookup_tail_vaddr
328      || phdr->p_offset != dwfl->lookup_tail_offset)
329    {
330      /* Normally just appending keeps us sorted.  */
331
332      size_t i = dwfl->lookup_elts;
333      while (i > 0 && unlikely (start < dwfl->lookup_addr[i - 1]))
334	--i;
335
336      if (unlikely (insert (dwfl, i, start, end, ndx)))
337	{
338	  __libdwfl_seterrno (DWFL_E_NOMEM);
339	  return -1;
340	}
341    }
342
343  dwfl->lookup_tail_ident = ident;
344  dwfl->lookup_tail_vaddr = end;
345  dwfl->lookup_tail_offset = end - bias - phdr->p_vaddr + phdr->p_offset;
346  dwfl->lookup_tail_ndx = ndx + 1;
347
348  return ndx;
349}
350INTDEF (dwfl_report_segment)
351