1 /* Manage address space lookup table for libdwfl. 2 Copyright (C) 2008, 2009, 2010 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 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 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 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 const size_t move = dwfl->lookup_elts - i; 111 memmove (&dwfl->lookup_addr[i + need], &dwfl->lookup_addr[i], 112 move * sizeof dwfl->lookup_addr[0]); 113 memmove (&dwfl->lookup_segndx[i + need], &dwfl->lookup_segndx[i], 114 move * sizeof dwfl->lookup_segndx[0]); 115 if (dwfl->lookup_module != NULL) 116 memmove (&dwfl->lookup_module[i + need], &dwfl->lookup_module[i], 117 move * sizeof dwfl->lookup_module[0]); 118 } 119 120 if (need_start) 121 { 122 dwfl->lookup_addr[i] = start; 123 dwfl->lookup_segndx[i] = segndx; 124 if (dwfl->lookup_module != NULL) 125 dwfl->lookup_module[i] = NULL; 126 ++i; 127 } 128 else 129 dwfl->lookup_segndx[i - 1] = segndx; 130 131 if (need_end) 132 { 133 dwfl->lookup_addr[i] = end; 134 dwfl->lookup_segndx[i] = -1; 135 if (dwfl->lookup_module != NULL) 136 dwfl->lookup_module[i] = NULL; 137 } 138 139 dwfl->lookup_elts += need; 140 141 return false; 142 } 143 144 static int 145 lookup (Dwfl *dwfl, GElf_Addr address, int hint) 146 { 147 if (hint >= 0 148 && address >= dwfl->lookup_addr[hint] 149 && ((size_t) hint + 1 == dwfl->lookup_elts 150 || address < dwfl->lookup_addr[hint + 1])) 151 return hint; 152 153 /* Do binary search on the array indexed by module load address. */ 154 size_t l = 0, u = dwfl->lookup_elts; 155 while (l < u) 156 { 157 size_t idx = (l + u) / 2; 158 if (address < dwfl->lookup_addr[idx]) 159 u = idx; 160 else 161 { 162 l = idx + 1; 163 if (l == dwfl->lookup_elts || address < dwfl->lookup_addr[l]) 164 return idx; 165 } 166 } 167 168 return -1; 169 } 170 171 static bool 172 reify_segments (Dwfl *dwfl) 173 { 174 int hint = -1; 175 int highest = -1; 176 bool fixup = false; 177 for (Dwfl_Module *mod = dwfl->modulelist; mod != NULL; mod = mod->next) 178 if (! mod->gc) 179 { 180 const GElf_Addr start = segment_start (dwfl, mod->low_addr); 181 const GElf_Addr end = segment_end (dwfl, mod->high_addr); 182 bool resized = false; 183 184 int idx = lookup (dwfl, start, hint); 185 if (unlikely (idx < 0)) 186 { 187 /* Module starts below any segment. Insert a low one. */ 188 if (unlikely (insert (dwfl, 0, start, end, -1))) 189 return true; 190 idx = 0; 191 resized = true; 192 } 193 else if (dwfl->lookup_addr[idx] > start) 194 { 195 /* The module starts in the middle of this segment. Split it. */ 196 if (unlikely (insert (dwfl, idx + 1, start, end, 197 dwfl->lookup_segndx[idx]))) 198 return true; 199 ++idx; 200 resized = true; 201 } 202 else if (dwfl->lookup_addr[idx] < start) 203 { 204 /* The module starts past the end of this segment. 205 Add a new one. */ 206 if (unlikely (insert (dwfl, idx + 1, start, end, -1))) 207 return true; 208 ++idx; 209 resized = true; 210 } 211 212 if ((size_t) idx + 1 < dwfl->lookup_elts 213 && end < dwfl->lookup_addr[idx + 1]) 214 { 215 /* The module ends in the middle of this segment. Split it. */ 216 if (unlikely (insert (dwfl, idx + 1, 217 end, dwfl->lookup_addr[idx + 1], -1))) 218 return true; 219 resized = true; 220 } 221 222 if (dwfl->lookup_module == NULL) 223 { 224 dwfl->lookup_module = calloc (dwfl->lookup_alloc, 225 sizeof dwfl->lookup_module[0]); 226 if (unlikely (dwfl->lookup_module == NULL)) 227 return true; 228 } 229 230 /* Cache a backpointer in the module. */ 231 mod->segment = idx; 232 233 /* Put MOD in the table for each segment that's inside it. */ 234 do 235 dwfl->lookup_module[idx++] = mod; 236 while ((size_t) idx < dwfl->lookup_elts 237 && dwfl->lookup_addr[idx] < end); 238 assert (dwfl->lookup_module[mod->segment] == mod); 239 240 if (resized && idx - 1 >= highest) 241 /* Expanding the lookup tables invalidated backpointers 242 we've already stored. Reset those ones. */ 243 fixup = true; 244 245 highest = idx - 1; 246 hint = (size_t) idx < dwfl->lookup_elts ? idx : -1; 247 } 248 249 if (fixup) 250 /* Reset backpointer indices invalidated by table insertions. */ 251 for (size_t idx = 0; idx < dwfl->lookup_elts; ++idx) 252 if (dwfl->lookup_module[idx] != NULL) 253 dwfl->lookup_module[idx]->segment = idx; 254 255 return false; 256 } 257 258 int 259 dwfl_addrsegment (Dwfl *dwfl, Dwarf_Addr address, Dwfl_Module **mod) 260 { 261 if (unlikely (dwfl == NULL)) 262 return -1; 263 264 if (unlikely (dwfl->lookup_module == NULL) 265 && mod != NULL 266 && unlikely (reify_segments (dwfl))) 267 { 268 __libdwfl_seterrno (DWFL_E_NOMEM); 269 return -1; 270 } 271 272 int idx = lookup (dwfl, address, -1); 273 if (likely (mod != NULL)) 274 { 275 if (unlikely (idx < 0) || unlikely (dwfl->lookup_module == NULL)) 276 *mod = NULL; 277 else 278 { 279 *mod = dwfl->lookup_module[idx]; 280 281 /* If this segment does not have a module, but the address is 282 the upper boundary of the previous segment's module, use that. */ 283 if (*mod == NULL && idx > 0 && dwfl->lookup_addr[idx] == address) 284 { 285 *mod = dwfl->lookup_module[idx - 1]; 286 if (*mod != NULL && (*mod)->high_addr != address) 287 *mod = NULL; 288 } 289 } 290 } 291 292 if (likely (idx >= 0)) 293 /* Translate internal segment table index to user segment index. */ 294 idx = dwfl->lookup_segndx[idx]; 295 296 return idx; 297 } 298 INTDEF (dwfl_addrsegment) 299 300 int 301 dwfl_report_segment (Dwfl *dwfl, int ndx, const GElf_Phdr *phdr, GElf_Addr bias, 302 const void *ident) 303 { 304 if (dwfl == NULL) 305 return -1; 306 307 if (ndx < 0) 308 ndx = dwfl->lookup_tail_ndx; 309 310 if (phdr->p_align > 1 && (dwfl->segment_align <= 1 || 311 phdr->p_align < dwfl->segment_align)) 312 dwfl->segment_align = phdr->p_align; 313 314 if (unlikely (dwfl->lookup_module != NULL)) 315 { 316 free (dwfl->lookup_module); 317 dwfl->lookup_module = NULL; 318 } 319 320 GElf_Addr start = segment_start (dwfl, bias + phdr->p_vaddr); 321 GElf_Addr end = segment_end (dwfl, bias + phdr->p_vaddr + phdr->p_memsz); 322 323 /* Coalesce into the last one if contiguous and matching. */ 324 if (ndx != dwfl->lookup_tail_ndx 325 || ident == NULL 326 || ident != dwfl->lookup_tail_ident 327 || start != dwfl->lookup_tail_vaddr 328 || phdr->p_offset != dwfl->lookup_tail_offset) 329 { 330 /* Normally just appending keeps us sorted. */ 331 332 size_t i = dwfl->lookup_elts; 333 while (i > 0 && unlikely (start < dwfl->lookup_addr[i - 1])) 334 --i; 335 336 if (unlikely (insert (dwfl, i, start, end, ndx))) 337 { 338 __libdwfl_seterrno (DWFL_E_NOMEM); 339 return -1; 340 } 341 } 342 343 dwfl->lookup_tail_ident = ident; 344 dwfl->lookup_tail_vaddr = end; 345 dwfl->lookup_tail_offset = end - bias - phdr->p_vaddr + phdr->p_offset; 346 dwfl->lookup_tail_ndx = ndx + 1; 347 348 return ndx; 349 } 350 INTDEF (dwfl_report_segment) 351
