Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 1 | /* Manage address space lookup table for libdwfl. |
Jan Kratochvil | 0b86746 | 2013-05-30 14:37:38 +0200 | [diff] [blame^] | 2 | Copyright (C) 2008, 2009, 2010, 2013 Red Hat, Inc. |
Mark Wielaard | de2ed97 | 2012-06-05 17:15:16 +0200 | [diff] [blame] | 3 | This file is part of elfutils. |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 4 | |
Mark Wielaard | de2ed97 | 2012-06-05 17:15:16 +0200 | [diff] [blame] | 5 | This file is free software; you can redistribute it and/or modify |
| 6 | it under the terms of either |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 7 | |
Mark Wielaard | de2ed97 | 2012-06-05 17:15:16 +0200 | [diff] [blame] | 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 |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 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 | |
Mark Wielaard | de2ed97 | 2012-06-05 17:15:16 +0200 | [diff] [blame] | 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/>. */ |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 28 | |
| 29 | #include "libdwflP.h" |
| 30 | |
Jan Kratochvil | 0b86746 | 2013-05-30 14:37:38 +0200 | [diff] [blame^] | 31 | GElf_Addr |
| 32 | internal_function |
| 33 | __libdwfl_segment_start (Dwfl *dwfl, GElf_Addr start) |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 34 | { |
| 35 | if (dwfl->segment_align > 1) |
| 36 | start &= -dwfl->segment_align; |
| 37 | return start; |
| 38 | } |
| 39 | |
Jan Kratochvil | 0b86746 | 2013-05-30 14:37:38 +0200 | [diff] [blame^] | 40 | GElf_Addr |
| 41 | internal_function |
| 42 | __libdwfl_segment_end (Dwfl *dwfl, GElf_Addr end) |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 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 |
| 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 | { |
Roland McGrath | 9cf28e4 | 2008-09-30 06:35:35 +0000 | [diff] [blame] | 67 | if (naddr != dwfl->lookup_addr) |
| 68 | free (naddr); |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 69 | return true; |
| 70 | } |
| 71 | dwfl->lookup_alloc = n; |
| 72 | dwfl->lookup_addr = naddr; |
| 73 | dwfl->lookup_segndx = nsegndx; |
Roland McGrath | 9cf28e4 | 2008-09-30 06:35:35 +0000 | [diff] [blame] | 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 | } |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 87 | } |
| 88 | |
| 89 | if (unlikely (i < dwfl->lookup_elts)) |
| 90 | { |
Roland McGrath | 4820a05 | 2010-05-04 19:46:56 -0700 | [diff] [blame] | 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]); |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 96 | if (dwfl->lookup_module != NULL) |
Roland McGrath | 4820a05 | 2010-05-04 19:46:56 -0700 | [diff] [blame] | 97 | memmove (&dwfl->lookup_module[i + need], &dwfl->lookup_module[i], |
| 98 | move * sizeof dwfl->lookup_module[0]); |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 99 | } |
| 100 | |
| 101 | if (need_start) |
| 102 | { |
| 103 | dwfl->lookup_addr[i] = start; |
| 104 | dwfl->lookup_segndx[i] = segndx; |
Roland McGrath | aba26e0 | 2010-05-06 01:12:15 -0700 | [diff] [blame] | 105 | if (dwfl->lookup_module != NULL) |
| 106 | dwfl->lookup_module[i] = NULL; |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 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; |
Roland McGrath | aba26e0 | 2010-05-06 01:12:15 -0700 | [diff] [blame] | 116 | if (dwfl->lookup_module != NULL) |
| 117 | dwfl->lookup_module[i] = NULL; |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 118 | } |
| 119 | |
| 120 | dwfl->lookup_elts += need; |
| 121 | |
| 122 | return false; |
| 123 | } |
| 124 | |
| 125 | static int |
| 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 |
Roland McGrath | 74afbee | 2009-01-22 04:52:56 -0800 | [diff] [blame] | 131 | || address < dwfl->lookup_addr[hint + 1])) |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 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 |
| 153 | reify_segments (Dwfl *dwfl) |
| 154 | { |
| 155 | int hint = -1; |
Roland McGrath | 4820a05 | 2010-05-04 19:46:56 -0700 | [diff] [blame] | 156 | int highest = -1; |
| 157 | bool fixup = false; |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 158 | for (Dwfl_Module *mod = dwfl->modulelist; mod != NULL; mod = mod->next) |
| 159 | if (! mod->gc) |
| 160 | { |
Jan Kratochvil | 0b86746 | 2013-05-30 14:37:38 +0200 | [diff] [blame^] | 161 | const GElf_Addr start = __libdwfl_segment_start (dwfl, mod->low_addr); |
| 162 | const GElf_Addr end = __libdwfl_segment_end (dwfl, mod->high_addr); |
Roland McGrath | 4820a05 | 2010-05-04 19:46:56 -0700 | [diff] [blame] | 163 | bool resized = false; |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 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; |
Roland McGrath | 4820a05 | 2010-05-04 19:46:56 -0700 | [diff] [blame] | 172 | resized = true; |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 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; |
Roland McGrath | 4820a05 | 2010-05-04 19:46:56 -0700 | [diff] [blame] | 181 | resized = true; |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 182 | } |
Roland McGrath | 9cf28e4 | 2008-09-30 06:35:35 +0000 | [diff] [blame] | 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; |
Roland McGrath | 4820a05 | 2010-05-04 19:46:56 -0700 | [diff] [blame] | 190 | resized = true; |
Roland McGrath | 9cf28e4 | 2008-09-30 06:35:35 +0000 | [diff] [blame] | 191 | } |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 192 | |
Roland McGrath | 9cf28e4 | 2008-09-30 06:35:35 +0000 | [diff] [blame] | 193 | if ((size_t) idx + 1 < dwfl->lookup_elts |
Roland McGrath | 4820a05 | 2010-05-04 19:46:56 -0700 | [diff] [blame] | 194 | && end < dwfl->lookup_addr[idx + 1]) |
| 195 | { |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 196 | /* The module ends in the middle of this segment. Split it. */ |
Roland McGrath | 4820a05 | 2010-05-04 19:46:56 -0700 | [diff] [blame] | 197 | if (unlikely (insert (dwfl, idx + 1, |
| 198 | end, dwfl->lookup_addr[idx + 1], -1))) |
| 199 | return true; |
| 200 | resized = true; |
| 201 | } |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 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); |
Roland McGrath | 4820a05 | 2010-05-04 19:46:56 -0700 | [diff] [blame] | 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; |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 227 | hint = (size_t) idx < dwfl->lookup_elts ? idx : -1; |
| 228 | } |
| 229 | |
Roland McGrath | 4820a05 | 2010-05-04 19:46:56 -0700 | [diff] [blame] | 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 | |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 236 | return false; |
| 237 | } |
| 238 | |
| 239 | int |
| 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 | } |
| 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 | |
Roland McGrath | 9cf28e4 | 2008-09-30 06:35:35 +0000 | [diff] [blame] | 295 | if (unlikely (dwfl->lookup_module != NULL)) |
| 296 | { |
| 297 | free (dwfl->lookup_module); |
| 298 | dwfl->lookup_module = NULL; |
| 299 | } |
| 300 | |
Jan Kratochvil | 0b86746 | 2013-05-30 14:37:38 +0200 | [diff] [blame^] | 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); |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 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 | |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 330 | return ndx; |
| 331 | } |
| 332 | INTDEF (dwfl_report_segment) |