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 31GElf_Addr 32internal_function 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 40GElf_Addr 41internal_function 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 49static bool 50insert (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 125static int 126lookup (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 152static bool 153reify_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 239int 240dwfl_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} 279INTDEF (dwfl_addrsegment) 280 281int 282dwfl_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} 332INTDEF (dwfl_report_segment) 333