1 /* Manage address space lookup table for libdwfl.
2 Copyright (C) 2008 Red Hat, Inc.
3 This file is part of Red Hat elfutils.
4
5 Red Hat elfutils is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by the
7 Free Software Foundation; version 2 of the License.
8
9 Red Hat elfutils is distributed in the hope that it will be useful, but
10 WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 General Public License for more details.
13
14 You should have received a copy of the GNU General Public License along
15 with Red Hat elfutils; if not, write to the Free Software Foundation,
16 Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301 USA.
17
18 In addition, as a special exception, Red Hat, Inc. gives You the
19 additional right to link the code of Red Hat elfutils with code licensed
20 under any Open Source Initiative certified open source license
21 (http://www.opensource.org/licenses/index.php) which requires the
22 distribution of source code with any binary distribution and to
23 distribute linked combinations of the two. Non-GPL Code permitted under
24 this exception must only link to the code of Red Hat elfutils through
25 those well defined interfaces identified in the file named EXCEPTION
26 found in the source code files (the "Approved Interfaces"). The files
27 of Non-GPL Code may instantiate templates or use macros or inline
28 functions from the Approved Interfaces without causing the resulting
29 work to be covered by the GNU General Public License. Only Red Hat,
30 Inc. may make changes or additions to the list of Approved Interfaces.
31 Red Hat's grant of this exception is conditioned upon your not adding
32 any new exceptions. If you wish to add a new Approved Interface or
33 exception, please contact Red Hat. You must obey the GNU General Public
34 License in all respects for all of the Red Hat elfutils code and other
35 code used in conjunction with Red Hat elfutils except the Non-GPL Code
36 covered by this exception. If you modify this file, you may extend this
37 exception to your version of the file, but you are not obligated to do
38 so. If you do not wish to provide this exception without modification,
39 you must delete this exception statement from your version and license
40 this file solely under the GPL without exception.
41
42 Red Hat elfutils is an included package of the Open Invention Network.
43 An included package of the Open Invention Network is a package for which
44 Open Invention Network licensees cross-license their patents. No patent
45 license is granted, either expressly or impliedly, by designation as an
46 included package. Should you wish to participate in the Open Invention
47 Network licensing program, please visit www.openinventionnetwork.com
48 <http://www.openinventionnetwork.com>. */
49
50 #include "libdwflP.h"
51
52 static GElf_Addr
segment_start(Dwfl * dwfl,GElf_Addr start)53 segment_start (Dwfl *dwfl, GElf_Addr start)
54 {
55 if (dwfl->segment_align > 1)
56 start &= -dwfl->segment_align;
57 return start;
58 }
59
60 static GElf_Addr
segment_end(Dwfl * dwfl,GElf_Addr end)61 segment_end (Dwfl *dwfl, GElf_Addr end)
62 {
63 if (dwfl->segment_align > 1)
64 end = (end + dwfl->segment_align - 1) & -dwfl->segment_align;
65 return end;
66 }
67
68 static bool
insert(Dwfl * dwfl,size_t i,GElf_Addr start,GElf_Addr end,int segndx)69 insert (Dwfl *dwfl, size_t i, GElf_Addr start, GElf_Addr end, int segndx)
70 {
71 bool need_start = (i == 0 || dwfl->lookup_addr[i - 1] != start);
72 bool need_end = (i >= dwfl->lookup_elts || dwfl->lookup_addr[i + 1] != end);
73 size_t need = need_start + need_end;
74 if (need == 0)
75 return false;
76
77 if (dwfl->lookup_alloc - dwfl->lookup_elts < need)
78 {
79 size_t n = dwfl->lookup_alloc == 0 ? 16 : dwfl->lookup_alloc * 2;
80 GElf_Addr *naddr = realloc (dwfl->lookup_addr, sizeof naddr[0] * n);
81 if (unlikely (naddr == NULL))
82 return true;
83 int *nsegndx = realloc (dwfl->lookup_segndx, sizeof nsegndx[0] * n);
84 if (unlikely (nsegndx == NULL))
85 {
86 if (naddr != dwfl->lookup_addr)
87 free (naddr);
88 return true;
89 }
90 dwfl->lookup_alloc = n;
91 dwfl->lookup_addr = naddr;
92 dwfl->lookup_segndx = nsegndx;
93
94 if (dwfl->lookup_module != NULL)
95 {
96 /* Make sure this array is big enough too. */
97 Dwfl_Module **old = dwfl->lookup_module;
98 dwfl->lookup_module = realloc (dwfl->lookup_module,
99 sizeof dwfl->lookup_module[0] * n);
100 if (unlikely (dwfl->lookup_module == NULL))
101 {
102 free (old);
103 return true;
104 }
105 }
106 }
107
108 if (unlikely (i < dwfl->lookup_elts))
109 {
110 memcpy (&dwfl->lookup_addr[i + need], &dwfl->lookup_addr[i],
111 need * sizeof dwfl->lookup_addr[0]);
112 memcpy (&dwfl->lookup_segndx[i + need], &dwfl->lookup_segndx[i],
113 need * sizeof dwfl->lookup_segndx[0]);
114 if (dwfl->lookup_module != NULL)
115 memcpy (&dwfl->lookup_module[i + need], &dwfl->lookup_module[i],
116 need * sizeof dwfl->lookup_module[0]);
117 }
118
119 if (need_start)
120 {
121 dwfl->lookup_addr[i] = start;
122 dwfl->lookup_segndx[i] = segndx;
123 ++i;
124 }
125 else
126 dwfl->lookup_segndx[i - 1] = segndx;
127
128 if (need_end)
129 {
130 dwfl->lookup_addr[i] = end;
131 dwfl->lookup_segndx[i] = -1;
132 }
133
134 dwfl->lookup_elts += need;
135
136 return false;
137 }
138
139 static int
lookup(Dwfl * dwfl,GElf_Addr address,int hint)140 lookup (Dwfl *dwfl, GElf_Addr address, int hint)
141 {
142 if (hint >= 0
143 && address >= dwfl->lookup_addr[hint]
144 && ((size_t) hint + 1 == dwfl->lookup_elts
145 || address <= dwfl->lookup_addr[hint + 1]))
146 return hint;
147
148 /* Do binary search on the array indexed by module load address. */
149 size_t l = 0, u = dwfl->lookup_elts;
150 while (l < u)
151 {
152 size_t idx = (l + u) / 2;
153 if (address < dwfl->lookup_addr[idx])
154 u = idx;
155 else
156 {
157 l = idx + 1;
158 if (l == dwfl->lookup_elts || address < dwfl->lookup_addr[l])
159 return idx;
160 }
161 }
162
163 return -1;
164 }
165
166 static bool
reify_segments(Dwfl * dwfl)167 reify_segments (Dwfl *dwfl)
168 {
169 int hint = -1;
170 for (Dwfl_Module *mod = dwfl->modulelist; mod != NULL; mod = mod->next)
171 if (! mod->gc)
172 {
173 const GElf_Addr start = segment_start (dwfl, mod->low_addr);
174 const GElf_Addr end = segment_end (dwfl, mod->high_addr);
175
176 int idx = lookup (dwfl, start, hint);
177 if (unlikely (idx < 0))
178 {
179 /* Module starts below any segment. Insert a low one. */
180 if (unlikely (insert (dwfl, 0, start, end, -1)))
181 return true;
182 idx = 0;
183 }
184 else if (dwfl->lookup_addr[idx] > start)
185 {
186 /* The module starts in the middle of this segment. Split it. */
187 if (unlikely (insert (dwfl, idx + 1, start, end,
188 dwfl->lookup_segndx[idx])))
189 return true;
190 ++idx;
191 }
192 else if (dwfl->lookup_addr[idx] < start)
193 {
194 /* The module starts past the end of this segment.
195 Add a new one. */
196 if (unlikely (insert (dwfl, idx + 1, start, end, -1)))
197 return true;
198 ++idx;
199 }
200
201 if ((size_t) idx + 1 < dwfl->lookup_elts
202 && end < dwfl->lookup_addr[idx + 1]
203 /* The module ends in the middle of this segment. Split it. */
204 && unlikely (insert (dwfl, idx + 1,
205 end, dwfl->lookup_addr[idx + 1], -1)))
206 return true;
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 hint = (size_t) idx < dwfl->lookup_elts ? idx : -1;
225 }
226
227 return false;
228 }
229
230 int
dwfl_addrsegment(Dwfl * dwfl,Dwarf_Addr address,Dwfl_Module ** mod)231 dwfl_addrsegment (Dwfl *dwfl, Dwarf_Addr address, Dwfl_Module **mod)
232 {
233 if (unlikely (dwfl == NULL))
234 return -1;
235
236 if (unlikely (dwfl->lookup_module == NULL)
237 && mod != NULL
238 && unlikely (reify_segments (dwfl)))
239 {
240 __libdwfl_seterrno (DWFL_E_NOMEM);
241 return -1;
242 }
243
244 int idx = lookup (dwfl, address, -1);
245 if (likely (mod != NULL))
246 {
247 if (unlikely (idx < 0) || unlikely (dwfl->lookup_module == NULL))
248 *mod = NULL;
249 else
250 {
251 *mod = dwfl->lookup_module[idx];
252
253 /* If this segment does not have a module, but the address is
254 the upper boundary of the previous segment's module, use that. */
255 if (*mod == NULL && idx > 0 && dwfl->lookup_addr[idx] == address)
256 {
257 *mod = dwfl->lookup_module[idx - 1];
258 if (*mod != NULL && (*mod)->high_addr != address)
259 *mod = NULL;
260 }
261 }
262 }
263
264 if (likely (idx >= 0))
265 /* Translate internal segment table index to user segment index. */
266 idx = dwfl->lookup_segndx[idx];
267
268 return idx;
269 }
INTDEF(dwfl_addrsegment)270 INTDEF (dwfl_addrsegment)
271
272 int
273 dwfl_report_segment (Dwfl *dwfl, int ndx, const GElf_Phdr *phdr, GElf_Addr bias,
274 const void *ident)
275 {
276 if (dwfl == NULL)
277 return -1;
278
279 if (ndx < 0)
280 ndx = dwfl->lookup_tail_ndx;
281
282 if (phdr->p_align > 1 && (dwfl->segment_align <= 1 ||
283 phdr->p_align < dwfl->segment_align))
284 dwfl->segment_align = phdr->p_align;
285
286 if (unlikely (dwfl->lookup_module != NULL))
287 {
288 free (dwfl->lookup_module);
289 dwfl->lookup_module = NULL;
290 }
291
292 GElf_Addr start = segment_start (dwfl, bias + phdr->p_vaddr);
293 GElf_Addr end = segment_end (dwfl, bias + phdr->p_vaddr + phdr->p_memsz);
294
295 /* Coalesce into the last one if contiguous and matching. */
296 if (ndx != dwfl->lookup_tail_ndx
297 || ident == NULL
298 || ident != dwfl->lookup_tail_ident
299 || start != dwfl->lookup_tail_vaddr
300 || phdr->p_offset != dwfl->lookup_tail_offset)
301 {
302 /* Normally just appending keeps us sorted. */
303
304 size_t i = dwfl->lookup_elts;
305 while (i > 0 && unlikely (start < dwfl->lookup_addr[i - 1]))
306 --i;
307
308 if (unlikely (insert (dwfl, i, start, end, ndx)))
309 {
310 __libdwfl_seterrno (DWFL_E_NOMEM);
311 return -1;
312 }
313 }
314
315 dwfl->lookup_tail_ident = ident;
316 dwfl->lookup_tail_vaddr = end;
317 dwfl->lookup_tail_offset = end - bias - phdr->p_vaddr + phdr->p_offset;
318 dwfl->lookup_tail_ndx = ndx + 1;
319
320 return ndx;
321 }
322 INTDEF (dwfl_report_segment)
323