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