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