uwx_utable.c revision 160157
1115013Smarcel/* 2160157SmarcelCopyright (c) 2003-2006 Hewlett-Packard Development Company, L.P. 3121642SmarcelPermission is hereby granted, free of charge, to any person 4121642Smarcelobtaining a copy of this software and associated documentation 5121642Smarcelfiles (the "Software"), to deal in the Software without 6121642Smarcelrestriction, including without limitation the rights to use, 7121642Smarcelcopy, modify, merge, publish, distribute, sublicense, and/or sell 8121642Smarcelcopies of the Software, and to permit persons to whom the 9121642SmarcelSoftware is furnished to do so, subject to the following 10121642Smarcelconditions: 11115013Smarcel 12121642SmarcelThe above copyright notice and this permission notice shall be 13121642Smarcelincluded in all copies or substantial portions of the Software. 14121642Smarcel 15121642SmarcelTHE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 16121642SmarcelEXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES 17121642SmarcelOF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 18121642SmarcelNONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT 19121642SmarcelHOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 20121642SmarcelWHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 21121642SmarcelFROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 22121642SmarcelOTHER DEALINGS IN THE SOFTWARE. 23121642Smarcel*/ 24121642Smarcel 25115013Smarcel#include "uwx_env.h" 26115013Smarcel#include "uwx_utable.h" 27115013Smarcel#include "uwx_swap.h" 28115013Smarcel#include "uwx_trace.h" 29115013Smarcel 30115013Smarcel/* 31115013Smarcel * uwx_utable.c 32115013Smarcel * 33115013Smarcel * This file contains the routines for searching an unwind table. 34115013Smarcel * The main entry point, uwx_search_utable(), gets the 35115013Smarcel * necessary information from the lookup ip callback's result 36115013Smarcel * vector, determines whether the table is 32-bit or 64-bit, 37115013Smarcel * then invokes the binary search routine for that format. 38115013Smarcel */ 39115013Smarcel 40115013Smarcel 41115013Smarcel/* Forward declarations */ 42115013Smarcel 43115013Smarcelint uwx_search_utable32( 44115013Smarcel struct uwx_env *env, 45129059Smarcel uint32_t ip, 46115013Smarcel uint32_t text_base, 47115013Smarcel uint32_t unwind_start, 48115013Smarcel uint32_t unwind_end, 49115013Smarcel struct uwx_utable_entry *uentry); 50115013Smarcel 51115013Smarcelint uwx_search_utable64( 52115013Smarcel struct uwx_env *env, 53129059Smarcel uint64_t ip, 54115013Smarcel uint64_t text_base, 55115013Smarcel uint64_t unwind_start, 56115013Smarcel uint64_t unwind_end, 57115013Smarcel struct uwx_utable_entry *uentry); 58115013Smarcel 59115013Smarcel 60115013Smarcel/* uwx_search_utable: Searches an unwind table for IP in current context */ 61115013Smarcel 62115013Smarcelint uwx_search_utable( 63115013Smarcel struct uwx_env *env, 64129059Smarcel uint64_t ip, 65115013Smarcel uint64_t *uvec, 66115013Smarcel struct uwx_utable_entry *uentry) 67115013Smarcel{ 68129059Smarcel uint64_t text_base; 69115013Smarcel uint64_t unwind_flags; 70129059Smarcel uint64_t unwind_start; 71129059Smarcel uint64_t unwind_end; 72115013Smarcel int keys; 73115013Smarcel int status; 74115013Smarcel 75115013Smarcel /* Get unwind table information from the result vector. */ 76115013Smarcel /* Make sure all three required values are given. */ 77115013Smarcel 78115013Smarcel keys = 0; 79115013Smarcel unwind_flags = 0; 80115013Smarcel while (*uvec != 0) { 81115013Smarcel switch ((int)*uvec++) { 82115013Smarcel case UWX_KEY_TBASE: 83115013Smarcel keys |= 1; 84160157Smarcel env->text_base = text_base = *uvec++; 85115013Smarcel break; 86115013Smarcel case UWX_KEY_UFLAGS: 87115013Smarcel unwind_flags = *uvec++; 88115013Smarcel break; 89115013Smarcel case UWX_KEY_USTART: 90115013Smarcel keys |= 2; 91115013Smarcel unwind_start = *uvec++; 92115013Smarcel break; 93115013Smarcel case UWX_KEY_UEND: 94115013Smarcel keys |= 4; 95115013Smarcel unwind_end = *uvec++; 96115013Smarcel break; 97160157Smarcel case UWX_KEY_GP: 98160157Smarcel uwx_set_reg(env, UWX_REG_GP, *uvec++); 99160157Smarcel break; 100115013Smarcel default: 101115013Smarcel return UWX_ERR_BADKEY; 102115013Smarcel } 103115013Smarcel } 104115013Smarcel if (keys != 7) 105115013Smarcel return UWX_ERR_BADKEY; 106115013Smarcel 107115013Smarcel /* Copy the unwind flags into the unwind entry. */ 108115013Smarcel /* (uwx_decode_uinfo needs to know whether it's 32-bit or 64-bit.) */ 109115013Smarcel 110115013Smarcel uentry->unwind_flags = unwind_flags; 111115013Smarcel 112115013Smarcel /* Call the appropriate binary search routine. */ 113115013Smarcel 114115013Smarcel if (unwind_flags & UNWIND_TBL_32BIT) 115115013Smarcel status = uwx_search_utable32(env, 116129059Smarcel (uint32_t) ip, 117115013Smarcel (uint32_t) text_base, 118115013Smarcel (uint32_t) unwind_start, 119115013Smarcel (uint32_t) unwind_end, 120115013Smarcel uentry); 121115013Smarcel else 122115013Smarcel status = uwx_search_utable64(env, 123129059Smarcel ip, text_base, unwind_start, unwind_end, uentry); 124115013Smarcel 125115013Smarcel return status; 126115013Smarcel} 127115013Smarcel 128115013Smarcel 129115013Smarcel/* uwx_search_utable32: Binary search of 32-bit unwind table */ 130115013Smarcel 131115013Smarcel#define COPYIN_UINFO_4(dest, src) \ 132115013Smarcel (env->remote? \ 133115013Smarcel (*env->copyin)(UWX_COPYIN_UINFO, (dest), (src), \ 134115013Smarcel WORDSZ, env->cb_token) : \ 135115013Smarcel (*(uint32_t *)(dest) = *(uint32_t *)(src), WORDSZ) ) 136115013Smarcel 137160157Smarcel#define SWIZZLE(x) (((uint64_t)((x) & 0xc0000000) << 31) | (x)) 138160157Smarcel 139115013Smarcelint uwx_search_utable32( 140115013Smarcel struct uwx_env *env, 141129059Smarcel uint32_t ip, 142115013Smarcel uint32_t text_base, 143115013Smarcel uint32_t unwind_start, 144115013Smarcel uint32_t unwind_end, 145115013Smarcel struct uwx_utable_entry *uentry) 146115013Smarcel{ 147160157Smarcel int status; 148115013Smarcel int lb; 149115013Smarcel int ub; 150129059Smarcel int mid; 151115013Smarcel int len; 152115013Smarcel uint32_t code_start; 153115013Smarcel uint32_t code_end; 154115013Smarcel uint32_t unwind_info; 155115013Smarcel 156115013Smarcel /* Since the unwind table uses segment-relative offsets, convert */ 157115013Smarcel /* the IP in the current context to a segment-relative offset. */ 158115013Smarcel 159129059Smarcel ip -= text_base; 160115013Smarcel 161115013Smarcel TRACE_T_SEARCH32(ip) 162115013Smarcel 163115013Smarcel /* Standard binary search. */ 164115013Smarcel /* Might modify this to do interpolation in the future. */ 165115013Smarcel 166115013Smarcel lb = 0; 167115013Smarcel ub = (unwind_end - unwind_start) / (3 * WORDSZ); 168115013Smarcel while (ub > lb) { 169115013Smarcel mid = (lb + ub) / 2; 170160157Smarcel len = COPYIN_UINFO_4((char *)&code_start, unwind_start+mid*3*WORDSZ); 171115013Smarcel len += COPYIN_UINFO_4((char *)&code_end, 172160157Smarcel unwind_start+mid*3*WORDSZ+WORDSZ); 173115013Smarcel if (len != 2 * WORDSZ) 174115013Smarcel return UWX_ERR_COPYIN_UTBL; 175115013Smarcel if (env->byte_swap) { 176115013Smarcel uwx_swap4(&code_start); 177115013Smarcel uwx_swap4(&code_end); 178115013Smarcel } 179115013Smarcel TRACE_T_BINSEARCH32(lb, ub, mid, code_start, code_end) 180115013Smarcel if (ip >= code_end) 181115013Smarcel lb = mid + 1; 182115013Smarcel else if (ip < code_start) 183115013Smarcel ub = mid; 184115013Smarcel else 185115013Smarcel break; 186115013Smarcel } 187115013Smarcel if (ub <= lb) 188115013Smarcel return UWX_ERR_NOUENTRY; 189115013Smarcel len = COPYIN_UINFO_4((char *)&unwind_info, 190160157Smarcel unwind_start+mid*3*WORDSZ+2*WORDSZ); 191115013Smarcel if (len != WORDSZ) 192115013Smarcel return UWX_ERR_COPYIN_UTBL; 193115013Smarcel if (env->byte_swap) 194115013Smarcel uwx_swap4(&unwind_info); 195160157Smarcel uentry->ptr_size = WORDSZ; 196160157Smarcel uentry->code_start = SWIZZLE(text_base + code_start); 197160157Smarcel uentry->code_end = SWIZZLE(text_base + code_end); 198160157Smarcel uentry->unwind_info = SWIZZLE(text_base + unwind_info); 199115013Smarcel return UWX_OK; 200115013Smarcel} 201115013Smarcel 202115013Smarcel 203115013Smarcel/* uwx_search_utable64: Binary search of 64-bit unwind table */ 204115013Smarcel 205115013Smarcel#define COPYIN_UINFO_8(dest, src) \ 206115013Smarcel (env->remote? \ 207160157Smarcel (*env->copyin)(UWX_COPYIN_UINFO, (dest), (src), \ 208115013Smarcel DWORDSZ, env->cb_token) : \ 209160157Smarcel (*(uint64_t *)(intptr_t)(dest) = *(uint64_t *)(intptr_t)(src), DWORDSZ) ) 210115013Smarcel 211115013Smarcelint uwx_search_utable64( 212115013Smarcel struct uwx_env *env, 213129059Smarcel uint64_t ip, 214115013Smarcel uint64_t text_base, 215115013Smarcel uint64_t unwind_start, 216115013Smarcel uint64_t unwind_end, 217115013Smarcel struct uwx_utable_entry *uentry) 218115013Smarcel{ 219160157Smarcel int status; 220115013Smarcel int lb; 221115013Smarcel int ub; 222129059Smarcel int mid; 223115013Smarcel int len; 224115013Smarcel uint64_t code_start; 225115013Smarcel uint64_t code_end; 226115013Smarcel uint64_t unwind_info; 227115013Smarcel 228115013Smarcel /* Since the unwind table uses segment-relative offsets, convert */ 229115013Smarcel /* the IP in the current context to a segment-relative offset. */ 230115013Smarcel 231129059Smarcel ip -= text_base; 232115013Smarcel 233115013Smarcel /* Standard binary search. */ 234115013Smarcel /* Might modify this to do interpolation in the future. */ 235115013Smarcel 236115013Smarcel lb = 0; 237115013Smarcel ub = (unwind_end - unwind_start) / (3 * DWORDSZ); 238115013Smarcel while (ub > lb) { 239115013Smarcel mid = (lb + ub) / 2; 240115013Smarcel len = COPYIN_UINFO_8((char *)&code_start, unwind_start+mid*3*DWORDSZ); 241115013Smarcel len += COPYIN_UINFO_8((char *)&code_end, 242115013Smarcel unwind_start+mid*3*DWORDSZ+DWORDSZ); 243115013Smarcel if (len != 2 * DWORDSZ) 244115013Smarcel return UWX_ERR_COPYIN_UTBL; 245115013Smarcel if (env->byte_swap) { 246115013Smarcel uwx_swap8(&code_start); 247115013Smarcel uwx_swap8(&code_end); 248115013Smarcel } 249115013Smarcel if (ip >= code_end) 250115013Smarcel lb = mid + 1; 251115013Smarcel else if (ip < code_start) 252115013Smarcel ub = mid; 253115013Smarcel else 254115013Smarcel break; 255115013Smarcel } 256115013Smarcel if (ub <= lb) 257115013Smarcel return UWX_ERR_NOUENTRY; 258115013Smarcel len = COPYIN_UINFO_8((char *)&unwind_info, 259115013Smarcel unwind_start+mid*3*DWORDSZ+2*DWORDSZ); 260115013Smarcel if (len != DWORDSZ) 261115013Smarcel return UWX_ERR_COPYIN_UTBL; 262115013Smarcel if (env->byte_swap) 263115013Smarcel uwx_swap8(&unwind_info); 264160157Smarcel uentry->ptr_size = DWORDSZ; 265115013Smarcel uentry->code_start = text_base + code_start; 266115013Smarcel uentry->code_end = text_base + code_end; 267115013Smarcel uentry->unwind_info = text_base + unwind_info; 268115013Smarcel return UWX_OK; 269115013Smarcel} 270