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.
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.
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.
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.
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.
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>. */
53 segment_start (Dwfl *dwfl, GElf_Addr start)
55 if (dwfl->segment_align > 1)
56 start &= -dwfl->segment_align;
61 segment_end (Dwfl *dwfl, GElf_Addr end)
63 if (dwfl->segment_align > 1)
64 end = (end + dwfl->segment_align - 1) & -dwfl->segment_align;
69 insert (Dwfl *dwfl, size_t i, GElf_Addr start, GElf_Addr end, int segndx)
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;
77 if (dwfl->lookup_alloc - dwfl->lookup_elts < need)
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))
83 int *nsegndx = realloc (dwfl->lookup_segndx, sizeof nsegndx[0] * n);
84 if (unlikely (nsegndx == NULL))
86 if (naddr != dwfl->lookup_addr)
90 dwfl->lookup_alloc = n;
91 dwfl->lookup_addr = naddr;
92 dwfl->lookup_segndx = nsegndx;
94 if (dwfl->lookup_module != NULL)
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))
108 if (unlikely (i < dwfl->lookup_elts))
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]);
122 dwfl->lookup_addr[i] = start;
123 dwfl->lookup_segndx[i] = segndx;
124 if (dwfl->lookup_module != NULL)
125 dwfl->lookup_module[i] = NULL;
129 dwfl->lookup_segndx[i - 1] = segndx;
133 dwfl->lookup_addr[i] = end;
134 dwfl->lookup_segndx[i] = -1;
135 if (dwfl->lookup_module != NULL)
136 dwfl->lookup_module[i] = NULL;
139 dwfl->lookup_elts += need;
145 lookup (Dwfl *dwfl, GElf_Addr address, int hint)
148 && address >= dwfl->lookup_addr[hint]
149 && ((size_t) hint + 1 == dwfl->lookup_elts
150 || address < dwfl->lookup_addr[hint + 1]))
153 /* Do binary search on the array indexed by module load address. */
154 size_t l = 0, u = dwfl->lookup_elts;
157 size_t idx = (l + u) / 2;
158 if (address < dwfl->lookup_addr[idx])
163 if (l == dwfl->lookup_elts || address < dwfl->lookup_addr[l])
172 reify_segments (Dwfl *dwfl)
177 for (Dwfl_Module *mod = dwfl->modulelist; mod != NULL; mod = mod->next)
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;
184 int idx = lookup (dwfl, start, hint);
185 if (unlikely (idx < 0))
187 /* Module starts below any segment. Insert a low one. */
188 if (unlikely (insert (dwfl, 0, start, end, -1)))
193 else if (dwfl->lookup_addr[idx] > start)
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])))
202 else if (dwfl->lookup_addr[idx] < start)
204 /* The module starts past the end of this segment.
206 if (unlikely (insert (dwfl, idx + 1, start, end, -1)))
212 if ((size_t) idx + 1 < dwfl->lookup_elts
213 && end < dwfl->lookup_addr[idx + 1])
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)))
222 if (dwfl->lookup_module == NULL)
224 dwfl->lookup_module = calloc (dwfl->lookup_alloc,
225 sizeof dwfl->lookup_module[0]);
226 if (unlikely (dwfl->lookup_module == NULL))
230 /* Cache a backpointer in the module. */
233 /* Put MOD in the table for each segment that's inside it. */
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);
240 if (resized && idx - 1 >= highest)
241 /* Expanding the lookup tables invalidated backpointers
242 we've already stored. Reset those ones. */
246 hint = (size_t) idx < dwfl->lookup_elts ? idx : -1;
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;
259 dwfl_addrsegment (Dwfl *dwfl, Dwarf_Addr address, Dwfl_Module **mod)
261 if (unlikely (dwfl == NULL))
264 if (unlikely (dwfl->lookup_module == NULL)
266 && unlikely (reify_segments (dwfl)))
268 __libdwfl_seterrno (DWFL_E_NOMEM);
272 int idx = lookup (dwfl, address, -1);
273 if (likely (mod != NULL))
275 if (unlikely (idx < 0) || unlikely (dwfl->lookup_module == NULL))
279 *mod = dwfl->lookup_module[idx];
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)
285 *mod = dwfl->lookup_module[idx - 1];
286 if (*mod != NULL && (*mod)->high_addr != address)
292 if (likely (idx >= 0))
293 /* Translate internal segment table index to user segment index. */
294 idx = dwfl->lookup_segndx[idx];
298 INTDEF (dwfl_addrsegment)
301 dwfl_report_segment (Dwfl *dwfl, int ndx, const GElf_Phdr *phdr, GElf_Addr bias,
308 ndx = dwfl->lookup_tail_ndx;
310 if (phdr->p_align > 1 && (dwfl->segment_align <= 1 ||
311 phdr->p_align < dwfl->segment_align))
312 dwfl->segment_align = phdr->p_align;
314 if (unlikely (dwfl->lookup_module != NULL))
316 free (dwfl->lookup_module);
317 dwfl->lookup_module = NULL;
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);
323 /* Coalesce into the last one if contiguous and matching. */
324 if (ndx != dwfl->lookup_tail_ndx
326 || ident != dwfl->lookup_tail_ident
327 || start != dwfl->lookup_tail_vaddr
328 || phdr->p_offset != dwfl->lookup_tail_offset)
330 /* Normally just appending keeps us sorted. */
332 size_t i = dwfl->lookup_elts;
333 while (i > 0 && unlikely (start < dwfl->lookup_addr[i - 1]))
336 if (unlikely (insert (dwfl, i, start, end, ndx)))
338 __libdwfl_seterrno (DWFL_E_NOMEM);
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;
350 INTDEF (dwfl_report_segment)