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