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