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 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 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 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 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 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 } 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
