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