Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 1 | /* Manage address space lookup table for libdwfl. |
Roland McGrath | 74afbee | 2009-01-22 04:52:56 -0800 | [diff] [blame^] | 2 | Copyright (C) 2008, 2009 Red Hat, Inc. |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 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 | { |
Roland McGrath | 9cf28e4 | 2008-09-30 06:35:35 +0000 | [diff] [blame] | 86 | if (naddr != dwfl->lookup_addr) |
| 87 | free (naddr); |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 88 | return true; |
| 89 | } |
| 90 | dwfl->lookup_alloc = n; |
| 91 | dwfl->lookup_addr = naddr; |
| 92 | dwfl->lookup_segndx = nsegndx; |
Roland McGrath | 9cf28e4 | 2008-09-30 06:35:35 +0000 | [diff] [blame] | 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 | } |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 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 |
Roland McGrath | 74afbee | 2009-01-22 04:52:56 -0800 | [diff] [blame^] | 145 | || address < dwfl->lookup_addr[hint + 1])) |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 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 | } |
Roland McGrath | 9cf28e4 | 2008-09-30 06:35:35 +0000 | [diff] [blame] | 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 | } |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 200 | |
Roland McGrath | 9cf28e4 | 2008-09-30 06:35:35 +0000 | [diff] [blame] | 201 | if ((size_t) idx + 1 < dwfl->lookup_elts |
| 202 | && end < dwfl->lookup_addr[idx + 1] |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 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 | |
Roland McGrath | 9cf28e4 | 2008-09-30 06:35:35 +0000 | [diff] [blame] | 286 | if (unlikely (dwfl->lookup_module != NULL)) |
| 287 | { |
| 288 | free (dwfl->lookup_module); |
| 289 | dwfl->lookup_module = NULL; |
| 290 | } |
| 291 | |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 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 | |
Roland McGrath | b4d6f0f | 2008-08-25 22:55:17 +0000 | [diff] [blame] | 320 | return ndx; |
| 321 | } |
| 322 | INTDEF (dwfl_report_segment) |