1130803Smarcel/* 2130803SmarcelCopyright (c) 2003-2006 Hewlett-Packard Development Company, L.P. 3130803SmarcelPermission is hereby granted, free of charge, to any person 4130803Smarcelobtaining a copy of this software and associated documentation 5130803Smarcelfiles (the "Software"), to deal in the Software without 6130803Smarcelrestriction, including without limitation the rights to use, 7130803Smarcelcopy, modify, merge, publish, distribute, sublicense, and/or sell 8130803Smarcelcopies of the Software, and to permit persons to whom the 9130803SmarcelSoftware is furnished to do so, subject to the following 10130803Smarcelconditions: 11130803Smarcel 12130803SmarcelThe above copyright notice and this permission notice shall be 13130803Smarcelincluded in all copies or substantial portions of the Software. 14130803Smarcel 15130803SmarcelTHE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 16130803SmarcelEXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES 17130803SmarcelOF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 18130803SmarcelNONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT 19130803SmarcelHOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 20130803SmarcelWHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 21130803SmarcelFROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 22130803SmarcelOTHER DEALINGS IN THE SOFTWARE. 23130803Smarcel*/ 24130803Smarcel 25130803Smarcel#include "uwx_env.h" 26130803Smarcel#include "uwx_utable.h" 27130803Smarcel#include "uwx_swap.h" 28130803Smarcel#include "uwx_trace.h" 29130803Smarcel 30130803Smarcel/* 31130803Smarcel * uwx_utable.c 32130803Smarcel * 33130803Smarcel * This file contains the routines for searching an unwind table. 34130803Smarcel * The main entry point, uwx_search_utable(), gets the 35130803Smarcel * necessary information from the lookup ip callback's result 36130803Smarcel * vector, determines whether the table is 32-bit or 64-bit, 37130803Smarcel * then invokes the binary search routine for that format. 38130803Smarcel */ 39130803Smarcel 40130803Smarcel 41130803Smarcel/* Forward declarations */ 42130803Smarcel 43130803Smarcelint uwx_search_utable32( 44130803Smarcel struct uwx_env *env, 45130803Smarcel uint32_t ip, 46130803Smarcel uint32_t text_base, 47130803Smarcel uint32_t unwind_start, 48130803Smarcel uint32_t unwind_end, 49130803Smarcel struct uwx_utable_entry *uentry); 50130803Smarcel 51130803Smarcelint uwx_search_utable64( 52130803Smarcel struct uwx_env *env, 53130803Smarcel uint64_t ip, 54130803Smarcel uint64_t text_base, 55130803Smarcel uint64_t unwind_start, 56130803Smarcel uint64_t unwind_end, 57130803Smarcel struct uwx_utable_entry *uentry); 58130803Smarcel 59130803Smarcel 60130803Smarcel/* uwx_search_utable: Searches an unwind table for IP in current context */ 61130803Smarcel 62130803Smarcelint uwx_search_utable( 63130803Smarcel struct uwx_env *env, 64130803Smarcel uint64_t ip, 65130803Smarcel uint64_t *uvec, 66130803Smarcel struct uwx_utable_entry *uentry) 67130803Smarcel{ 68130803Smarcel uint64_t text_base; 69130803Smarcel uint64_t unwind_flags; 70130803Smarcel uint64_t unwind_start; 71130803Smarcel uint64_t unwind_end; 72130803Smarcel int keys; 73130803Smarcel int status; 74130803Smarcel 75130803Smarcel /* Get unwind table information from the result vector. */ 76130803Smarcel /* Make sure all three required values are given. */ 77130803Smarcel 78130803Smarcel keys = 0; 79130803Smarcel text_base = 0; 80130803Smarcel unwind_flags = 0; 81130803Smarcel unwind_start = 0; 82130803Smarcel unwind_end = 0; 83130803Smarcel while (*uvec != 0) { 84130803Smarcel switch ((int)*uvec++) { 85130803Smarcel case UWX_KEY_TBASE: 86130803Smarcel keys |= 1; 87130803Smarcel env->text_base = text_base = *uvec++; 88130803Smarcel break; 89130803Smarcel case UWX_KEY_UFLAGS: 90130803Smarcel unwind_flags = *uvec++; 91130803Smarcel break; 92130803Smarcel case UWX_KEY_USTART: 93130803Smarcel keys |= 2; 94130803Smarcel unwind_start = *uvec++; 95130803Smarcel break; 96130803Smarcel case UWX_KEY_UEND: 97130803Smarcel keys |= 4; 98130803Smarcel unwind_end = *uvec++; 99130803Smarcel break; 100130803Smarcel case UWX_KEY_GP: 101130803Smarcel uwx_set_reg(env, UWX_REG_GP, *uvec++); 102130803Smarcel break; 103130803Smarcel default: 104130803Smarcel return UWX_ERR_BADKEY; 105130803Smarcel } 106130803Smarcel } 107130803Smarcel if (keys != 7) 108130803Smarcel return UWX_ERR_BADKEY; 109130803Smarcel 110130803Smarcel /* Copy the unwind flags into the unwind entry. */ 111130803Smarcel /* (uwx_decode_uinfo needs to know whether it's 32-bit or 64-bit.) */ 112130803Smarcel 113130803Smarcel uentry->unwind_flags = unwind_flags; 114130803Smarcel 115130803Smarcel /* Call the appropriate binary search routine. */ 116130803Smarcel 117130803Smarcel if (unwind_flags & UNWIND_TBL_32BIT) 118130803Smarcel status = uwx_search_utable32(env, 119130803Smarcel (uint32_t) ip, 120130803Smarcel (uint32_t) text_base, 121130803Smarcel (uint32_t) unwind_start, 122130803Smarcel (uint32_t) unwind_end, 123130803Smarcel uentry); 124130803Smarcel else 125130803Smarcel status = uwx_search_utable64(env, 126130803Smarcel ip, text_base, unwind_start, unwind_end, uentry); 127130803Smarcel 128130803Smarcel return status; 129130803Smarcel} 130130803Smarcel 131130803Smarcel 132130803Smarcel/* uwx_search_utable32: Binary search of 32-bit unwind table */ 133130803Smarcel 134130803Smarcel#define COPYIN_UINFO_4(dest, src) \ 135130803Smarcel (env->remote? \ 136130803Smarcel (*env->copyin)(UWX_COPYIN_UINFO, (dest), (src), \ 137130803Smarcel WORDSZ, env->cb_token) : \ 138130803Smarcel (*(uint32_t *)(dest) = *(uint32_t *)(src), WORDSZ) ) 139130803Smarcel 140130803Smarcel#define SWIZZLE(x) (((uint64_t)((x) & 0xc0000000) << 31) | (x)) 141130803Smarcel 142130803Smarcelint uwx_search_utable32( 143130803Smarcel struct uwx_env *env, 144130803Smarcel uint32_t ip, 145130803Smarcel uint32_t text_base, 146130803Smarcel uint32_t unwind_start, 147130803Smarcel uint32_t unwind_end, 148130803Smarcel struct uwx_utable_entry *uentry) 149130803Smarcel{ 150130803Smarcel int lb; 151130803Smarcel int ub; 152130803Smarcel int mid; 153130803Smarcel int len; 154130803Smarcel uint32_t code_start; 155130803Smarcel uint32_t code_end; 156130803Smarcel uint32_t unwind_info; 157130803Smarcel 158130803Smarcel /* Since the unwind table uses segment-relative offsets, convert */ 159130803Smarcel /* the IP in the current context to a segment-relative offset. */ 160130803Smarcel 161130803Smarcel ip -= text_base; 162130803Smarcel 163130803Smarcel TRACE_T_SEARCH32(ip) 164130803Smarcel 165130803Smarcel /* Standard binary search. */ 166130803Smarcel /* Might modify this to do interpolation in the future. */ 167130803Smarcel 168130803Smarcel lb = 0; 169130803Smarcel ub = (unwind_end - unwind_start) / (3 * WORDSZ); 170130803Smarcel mid = 0; 171130803Smarcel while (ub > lb) { 172130803Smarcel mid = (lb + ub) / 2; 173130803Smarcel len = COPYIN_UINFO_4((char *)&code_start, 174130803Smarcel (uintptr_t)(unwind_start+mid*3*WORDSZ)); 175130803Smarcel len += COPYIN_UINFO_4((char *)&code_end, 176130803Smarcel (uintptr_t)(unwind_start+mid*3*WORDSZ+WORDSZ)); 177130803Smarcel if (len != 2 * WORDSZ) 178130803Smarcel return UWX_ERR_COPYIN_UTBL; 179130803Smarcel if (env->byte_swap) { 180130803Smarcel uwx_swap4(&code_start); 181130803Smarcel uwx_swap4(&code_end); 182130803Smarcel } 183130803Smarcel TRACE_T_BINSEARCH32(lb, ub, mid, code_start, code_end) 184130803Smarcel if (ip >= code_end) 185130803Smarcel lb = mid + 1; 186130803Smarcel else if (ip < code_start) 187130803Smarcel ub = mid; 188130803Smarcel else 189130803Smarcel break; 190130803Smarcel } 191130803Smarcel if (ub <= lb) 192130803Smarcel return UWX_ERR_NOUENTRY; 193130803Smarcel len = COPYIN_UINFO_4((char *)&unwind_info, 194130803Smarcel (uintptr_t)(unwind_start+mid*3*WORDSZ+2*WORDSZ)); 195130803Smarcel if (len != WORDSZ) 196130803Smarcel return UWX_ERR_COPYIN_UTBL; 197130803Smarcel if (env->byte_swap) 198130803Smarcel uwx_swap4(&unwind_info); 199130803Smarcel uentry->ptr_size = WORDSZ; 200130803Smarcel uentry->code_start = SWIZZLE(text_base + code_start); 201130803Smarcel uentry->code_end = SWIZZLE(text_base + code_end); 202130803Smarcel uentry->unwind_info = SWIZZLE(text_base + unwind_info); 203130803Smarcel return UWX_OK; 204130803Smarcel} 205130803Smarcel 206130803Smarcel 207130803Smarcel/* uwx_search_utable64: Binary search of 64-bit unwind table */ 208130803Smarcel 209130803Smarcel#define COPYIN_UINFO_8(dest, src) \ 210130803Smarcel (env->remote? \ 211130803Smarcel (*env->copyin)(UWX_COPYIN_UINFO, (dest), (src), \ 212130803Smarcel DWORDSZ, env->cb_token) : \ 213130803Smarcel (*(uint64_t *)(intptr_t)(dest) = *(uint64_t *)(intptr_t)(src), DWORDSZ) ) 214130803Smarcel 215130803Smarcelint uwx_search_utable64( 216130803Smarcel struct uwx_env *env, 217130803Smarcel uint64_t ip, 218130803Smarcel uint64_t text_base, 219130803Smarcel uint64_t unwind_start, 220130803Smarcel uint64_t unwind_end, 221130803Smarcel struct uwx_utable_entry *uentry) 222130803Smarcel{ 223130803Smarcel int lb; 224130803Smarcel int ub; 225130803Smarcel int mid; 226130803Smarcel int len; 227130803Smarcel uint64_t code_start; 228130803Smarcel uint64_t code_end; 229130803Smarcel uint64_t unwind_info; 230130803Smarcel 231130803Smarcel /* Since the unwind table uses segment-relative offsets, convert */ 232130803Smarcel /* the IP in the current context to a segment-relative offset. */ 233130803Smarcel 234130803Smarcel ip -= text_base; 235130803Smarcel 236130803Smarcel /* Standard binary search. */ 237130803Smarcel /* Might modify this to do interpolation in the future. */ 238130803Smarcel 239130803Smarcel lb = 0; 240130803Smarcel ub = (unwind_end - unwind_start) / (3 * DWORDSZ); 241130803Smarcel mid = 0; 242130803Smarcel while (ub > lb) { 243130803Smarcel mid = (lb + ub) / 2; 244130803Smarcel len = COPYIN_UINFO_8((char *)&code_start, unwind_start+mid*3*DWORDSZ); 245130803Smarcel len += COPYIN_UINFO_8((char *)&code_end, 246130803Smarcel unwind_start+mid*3*DWORDSZ+DWORDSZ); 247130803Smarcel if (len != 2 * DWORDSZ) 248130803Smarcel return UWX_ERR_COPYIN_UTBL; 249130803Smarcel if (env->byte_swap) { 250130803Smarcel uwx_swap8(&code_start); 251130803Smarcel uwx_swap8(&code_end); 252130803Smarcel } 253130803Smarcel if (ip >= code_end) 254130803Smarcel lb = mid + 1; 255130803Smarcel else if (ip < code_start) 256130803Smarcel ub = mid; 257130803Smarcel else 258130803Smarcel break; 259130803Smarcel } 260130803Smarcel if (ub <= lb) 261130803Smarcel return UWX_ERR_NOUENTRY; 262130803Smarcel len = COPYIN_UINFO_8((char *)&unwind_info, 263130803Smarcel unwind_start+mid*3*DWORDSZ+2*DWORDSZ); 264130803Smarcel if (len != DWORDSZ) 265130803Smarcel return UWX_ERR_COPYIN_UTBL; 266130803Smarcel if (env->byte_swap) 267130803Smarcel uwx_swap8(&unwind_info); 268130803Smarcel uentry->ptr_size = DWORDSZ; 269130803Smarcel uentry->code_start = text_base + code_start; 270130803Smarcel uentry->code_end = text_base + code_end; 271130803Smarcel uentry->unwind_info = text_base + unwind_info; 272130803Smarcel return UWX_OK; 273130803Smarcel} 274130803Smarcel