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