Branch data 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 : 90144 : __libdwfl_segment_start (Dwfl *dwfl, GElf_Addr start)
38 : : {
39 [ + - ]: 8456 : if (dwfl->segment_align > 1)
40 : 89980 : start &= -dwfl->segment_align;
41 : 90144 : return start;
42 : : }
43 : :
44 : : GElf_Addr
45 : : internal_function
46 : 90144 : __libdwfl_segment_end (Dwfl *dwfl, GElf_Addr end)
47 : : {
48 [ + - ]: 8456 : if (dwfl->segment_align > 1)
49 : 89980 : end = (end + dwfl->segment_align - 1) & -dwfl->segment_align;
50 : 90144 : return end;
51 : : }
52 : :
53 : : static bool
54 : 61486 : insert (Dwfl *dwfl, size_t i, GElf_Addr start, GElf_Addr end, int segndx)
55 : : {
56 [ + + + + ]: 61486 : bool need_start = (i == 0 || dwfl->lookup_addr[i - 1] != start);
57 : 122972 : bool need_end = (i + 1 >= dwfl->lookup_elts
58 [ + + + - ]: 61486 : || dwfl->lookup_addr[i + 1] != end);
59 : 61486 : size_t need = need_start + need_end;
60 [ - + ]: 61486 : if (need == 0)
61 : : return false;
62 : :
63 [ + + ]: 61486 : if (dwfl->lookup_alloc - dwfl->lookup_elts < need)
64 : : {
65 [ + + ]: 10284 : size_t n = dwfl->lookup_alloc == 0 ? 16 : dwfl->lookup_alloc * 2;
66 : 10284 : GElf_Addr *naddr = realloc (dwfl->lookup_addr, sizeof naddr[0] * n);
67 [ + - ]: 10284 : if (unlikely (naddr == NULL))
68 : : return true;
69 : 10284 : int *nsegndx = realloc (dwfl->lookup_segndx, sizeof nsegndx[0] * n);
70 [ - + ]: 10284 : if (unlikely (nsegndx == NULL))
71 : : {
72 [ # # ]: 0 : if (naddr != dwfl->lookup_addr)
73 : 0 : free (naddr);
74 : 0 : return true;
75 : : }
76 : 10284 : dwfl->lookup_alloc = n;
77 : 10284 : dwfl->lookup_addr = naddr;
78 : 10284 : dwfl->lookup_segndx = nsegndx;
79 : :
80 [ + + ]: 10284 : if (dwfl->lookup_module != NULL)
81 : : {
82 : : /* Make sure this array is big enough too. */
83 : 4 : Dwfl_Module **old = dwfl->lookup_module;
84 : 4 : dwfl->lookup_module = realloc (dwfl->lookup_module,
85 : : sizeof dwfl->lookup_module[0] * n);
86 [ - + ]: 4 : if (unlikely (dwfl->lookup_module == NULL))
87 : : {
88 : 0 : free (old);
89 : 0 : return true;
90 : : }
91 : : }
92 : : }
93 : :
94 [ + + ]: 61486 : if (unlikely (i < dwfl->lookup_elts))
95 : : {
96 : 44 : 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 [ + + ]: 44 : if (dwfl->lookup_module != NULL)
102 : 38 : memmove (&dwfl->lookup_module[i + need], &dwfl->lookup_module[i],
103 : : move * sizeof dwfl->lookup_module[0]);
104 : : }
105 : :
106 [ + + ]: 61486 : if (need_start)
107 : : {
108 : 60788 : dwfl->lookup_addr[i] = start;
109 : 60788 : dwfl->lookup_segndx[i] = segndx;
110 [ + + ]: 60788 : if (dwfl->lookup_module != NULL)
111 : 50084 : dwfl->lookup_module[i] = NULL;
112 : : ++i;
113 : : }
114 : : else
115 : 698 : dwfl->lookup_segndx[i - 1] = segndx;
116 : :
117 [ + - ]: 61486 : if (need_end)
118 : : {
119 : 61486 : dwfl->lookup_addr[i] = end;
120 : 61486 : dwfl->lookup_segndx[i] = -1;
121 [ + + ]: 61486 : if (dwfl->lookup_module != NULL)
122 : 50084 : dwfl->lookup_module[i] = NULL;
123 : : }
124 : :
125 : 61486 : dwfl->lookup_elts += need;
126 : :
127 : 61486 : return false;
128 : : }
129 : :
130 : : static int
131 : 92628 : lookup (Dwfl *dwfl, GElf_Addr address, int hint)
132 : : {
133 [ + + ]: 92628 : if (hint >= 0
134 [ + + ]: 50226 : && address >= dwfl->lookup_addr[hint]
135 [ + + ]: 50192 : && ((size_t) hint + 1 == dwfl->lookup_elts
136 [ + + ]: 144 : || address < dwfl->lookup_addr[hint + 1]))
137 : : return hint;
138 : :
139 : : /* Do binary search on the array indexed by module load address. */
140 : 42578 : size_t l = 0, u = dwfl->lookup_elts;
141 [ + + ]: 151778 : while (l < u)
142 : : {
143 : 99046 : size_t idx = (l + u) / 2;
144 [ + + ]: 99046 : if (address < dwfl->lookup_addr[idx])
145 : : u = idx;
146 : : else
147 : : {
148 : 63618 : l = idx + 1;
149 [ + + + + ]: 63618 : if (l == dwfl->lookup_elts || address < dwfl->lookup_addr[l])
150 : 32424 : return idx;
151 : : }
152 : : }
153 : :
154 : : return -1;
155 : : }
156 : :
157 : : static bool
158 : 10356 : reify_segments (Dwfl *dwfl)
159 : : {
160 : 10356 : int hint = -1;
161 : 10356 : int highest = -1;
162 : 10356 : bool fixup = false;
163 [ + + ]: 90794 : for (Dwfl_Module *mod = dwfl->modulelist; mod != NULL; mod = mod->next)
164 [ + - ]: 80438 : if (! mod->gc)
165 : : {
166 [ + + ]: 80438 : const GElf_Addr start = __libdwfl_segment_start (dwfl, mod->low_addr);
167 [ + + ]: 80438 : const GElf_Addr end = __libdwfl_segment_end (dwfl, mod->high_addr);
168 : 80438 : bool resized = false;
169 : :
170 : 80438 : int idx = lookup (dwfl, start, hint);
171 [ + + ]: 80438 : if (unlikely (idx < 0))
172 : : {
173 : : /* Module starts below any segment. Insert a low one. */
174 [ - + ]: 10150 : if (unlikely (insert (dwfl, 0, start, end, -1)))
175 : : return true;
176 : : idx = 0;
177 : : resized = true;
178 : : }
179 [ - + ]: 70288 : 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 [ + + ]: 70288 : else if (dwfl->lookup_addr[idx] < start)
189 : : {
190 : : /* The module starts past the end of this segment.
191 : : Add a new one. */
192 [ - + ]: 50048 : if (unlikely (insert (dwfl, idx + 1, start, end, -1)))
193 : : return true;
194 : : ++idx;
195 : : resized = true;
196 : : }
197 : :
198 [ + + ]: 80438 : if ((size_t) idx + 1 < dwfl->lookup_elts
199 [ + + ]: 60432 : && end < dwfl->lookup_addr[idx + 1])
200 : : {
201 : : /* The module ends in the middle of this segment. Split it. */
202 [ - + ]: 38 : if (unlikely (insert (dwfl, idx + 1,
203 : : end, dwfl->lookup_addr[idx + 1], -1)))
204 : : return true;
205 : : resized = true;
206 : : }
207 : :
208 [ + + ]: 80438 : if (dwfl->lookup_module == NULL)
209 : : {
210 : 10208 : dwfl->lookup_module = calloc (dwfl->lookup_alloc,
211 : : sizeof dwfl->lookup_module[0]);
212 [ - + ]: 10208 : if (unlikely (dwfl->lookup_module == NULL))
213 : : return true;
214 : : }
215 : :
216 : : /* Cache a backpointer in the module. */
217 : 80438 : mod->segment = idx;
218 : :
219 : : /* Put MOD in the table for each segment that's inside it. */
220 : 81016 : do
221 : 81016 : dwfl->lookup_module[idx++] = mod;
222 : 81016 : while ((size_t) idx < dwfl->lookup_elts
223 [ + + + + ]: 81016 : && dwfl->lookup_addr[idx] < end);
224 [ - + ]: 80438 : assert (dwfl->lookup_module[mod->segment] == mod);
225 : :
226 [ + + ]: 80438 : if (resized && idx - 1 >= highest)
227 : : /* Expanding the lookup tables invalidated backpointers
228 : : we've already stored. Reset those ones. */
229 : 60236 : fixup = true;
230 : :
231 : 80438 : highest = idx - 1;
232 [ + + ]: 80438 : hint = (size_t) idx < dwfl->lookup_elts ? idx : -1;
233 : : }
234 : :
235 [ + + ]: 10356 : if (fixup)
236 : : /* Reset backpointer indices invalidated by table insertions. */
237 [ + + ]: 131938 : for (size_t idx = 0; idx < dwfl->lookup_elts; ++idx)
238 [ + + ]: 121752 : if (dwfl->lookup_module[idx] != NULL)
239 : 80930 : dwfl->lookup_module[idx]->segment = idx;
240 : :
241 : : return false;
242 : : }
243 : :
244 : : int
245 : 12190 : dwfl_addrsegment (Dwfl *dwfl, Dwarf_Addr address, Dwfl_Module **mod)
246 : : {
247 [ - + ]: 12190 : if (unlikely (dwfl == NULL))
248 : : return -1;
249 : :
250 [ + + ]: 12190 : if (unlikely (dwfl->lookup_module == NULL)
251 [ + + ]: 10892 : && mod != NULL
252 [ - + ]: 10356 : && unlikely (reify_segments (dwfl)))
253 : : {
254 : 0 : __libdwfl_seterrno (DWFL_E_NOMEM);
255 : 0 : return -1;
256 : : }
257 : :
258 : 12190 : int idx = lookup (dwfl, address, -1);
259 [ + + ]: 12190 : if (likely (mod != NULL))
260 : : {
261 [ + + + + ]: 11654 : if (unlikely (idx < 0) || unlikely (dwfl->lookup_module == NULL))
262 : 152 : *mod = NULL;
263 : : else
264 : : {
265 : 11502 : *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 [ + + + - : 11502 : if (*mod == NULL && idx > 0 && dwfl->lookup_addr[idx] == address)
+ - ]
270 : : {
271 : 4 : *mod = dwfl->lookup_module[idx - 1];
272 [ + - - + ]: 4 : if (*mod != NULL && (*mod)->high_addr != address)
273 : 0 : *mod = NULL;
274 : : }
275 : : }
276 : : }
277 : :
278 [ + + ]: 12190 : if (likely (idx >= 0))
279 : : /* Translate internal segment table index to user segment index. */
280 : 12186 : idx = dwfl->lookup_segndx[idx];
281 : :
282 : : return idx;
283 : : }
284 : : INTDEF (dwfl_addrsegment)
285 : :
286 : : int
287 : 1250 : dwfl_report_segment (Dwfl *dwfl, int ndx, const GElf_Phdr *phdr, GElf_Addr bias,
288 : : const void *ident)
289 : : {
290 : : /* This was previously used for coalescing segments, but it was buggy since
291 : : day one. We don't use it anymore. */
292 : 1250 : (void)ident;
293 : :
294 [ - + ]: 1250 : if (dwfl == NULL)
295 : : return -1;
296 : :
297 [ - + ]: 1250 : if (ndx < 0)
298 : 0 : ndx = dwfl->next_segndx;
299 : :
300 [ + - + + : 1250 : if (phdr->p_align > 1 && (dwfl->segment_align <= 1 ||
- + ]
301 : : phdr->p_align < dwfl->segment_align))
302 : 70 : dwfl->segment_align = phdr->p_align;
303 : :
304 [ - + ]: 1250 : if (unlikely (dwfl->lookup_module != NULL))
305 : : {
306 : 0 : free (dwfl->lookup_module);
307 : 0 : dwfl->lookup_module = NULL;
308 : : }
309 : :
310 [ + - ]: 1250 : GElf_Addr start = __libdwfl_segment_start (dwfl, bias + phdr->p_vaddr);
311 : 2500 : GElf_Addr end = __libdwfl_segment_end (dwfl,
312 [ + - ]: 1250 : bias + phdr->p_vaddr + phdr->p_memsz);
313 : :
314 : : /* Normally just appending keeps us sorted. */
315 : :
316 : 1250 : size_t i = dwfl->lookup_elts;
317 [ + + - + ]: 1250 : while (i > 0 && unlikely (start < dwfl->lookup_addr[i - 1]))
318 : 0 : --i;
319 : :
320 [ - + ]: 1250 : if (unlikely (insert (dwfl, i, start, end, ndx)))
321 : : {
322 : 0 : __libdwfl_seterrno (DWFL_E_NOMEM);
323 : 0 : return -1;
324 : : }
325 : :
326 : 1250 : dwfl->next_segndx = ndx + 1;
327 : :
328 : 1250 : return ndx;
329 : : }
330 : : INTDEF (dwfl_report_segment)
|
