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; 79160163Smarcel text_base = 0; 80115013Smarcel unwind_flags = 0; 81160163Smarcel unwind_start = 0; 82160163Smarcel unwind_end = 0; 83115013Smarcel while (*uvec != 0) { 84115013Smarcel switch ((int)*uvec++) { 85115013Smarcel case UWX_KEY_TBASE: 86115013Smarcel keys |= 1; 87160157Smarcel env->text_base = text_base = *uvec++; 88115013Smarcel break; 89115013Smarcel case UWX_KEY_UFLAGS: 90115013Smarcel unwind_flags = *uvec++; 91115013Smarcel break; 92115013Smarcel case UWX_KEY_USTART: 93115013Smarcel keys |= 2; 94115013Smarcel unwind_start = *uvec++; 95115013Smarcel break; 96115013Smarcel case UWX_KEY_UEND: 97115013Smarcel keys |= 4; 98115013Smarcel unwind_end = *uvec++; 99115013Smarcel break; 100160157Smarcel case UWX_KEY_GP: 101160157Smarcel uwx_set_reg(env, UWX_REG_GP, *uvec++); 102160157Smarcel break; 103115013Smarcel default: 104115013Smarcel return UWX_ERR_BADKEY; 105115013Smarcel } 106115013Smarcel } 107115013Smarcel if (keys != 7) 108115013Smarcel return UWX_ERR_BADKEY; 109115013Smarcel 110115013Smarcel /* Copy the unwind flags into the unwind entry. */ 111115013Smarcel /* (uwx_decode_uinfo needs to know whether it's 32-bit or 64-bit.) */ 112115013Smarcel 113115013Smarcel uentry->unwind_flags = unwind_flags; 114115013Smarcel 115115013Smarcel /* Call the appropriate binary search routine. */ 116115013Smarcel 117115013Smarcel if (unwind_flags & UNWIND_TBL_32BIT) 118115013Smarcel status = uwx_search_utable32(env, 119129059Smarcel (uint32_t) ip, 120115013Smarcel (uint32_t) text_base, 121115013Smarcel (uint32_t) unwind_start, 122115013Smarcel (uint32_t) unwind_end, 123115013Smarcel uentry); 124115013Smarcel else 125115013Smarcel status = uwx_search_utable64(env, 126129059Smarcel ip, text_base, unwind_start, unwind_end, uentry); 127115013Smarcel 128115013Smarcel return status; 129115013Smarcel} 130115013Smarcel 131115013Smarcel 132115013Smarcel/* uwx_search_utable32: Binary search of 32-bit unwind table */ 133115013Smarcel 134115013Smarcel#define COPYIN_UINFO_4(dest, src) \ 135115013Smarcel (env->remote? \ 136115013Smarcel (*env->copyin)(UWX_COPYIN_UINFO, (dest), (src), \ 137115013Smarcel WORDSZ, env->cb_token) : \ 138115013Smarcel (*(uint32_t *)(dest) = *(uint32_t *)(src), WORDSZ) ) 139115013Smarcel 140160157Smarcel#define SWIZZLE(x) (((uint64_t)((x) & 0xc0000000) << 31) | (x)) 141160157Smarcel 142115013Smarcelint uwx_search_utable32( 143115013Smarcel struct uwx_env *env, 144129059Smarcel uint32_t ip, 145115013Smarcel uint32_t text_base, 146115013Smarcel uint32_t unwind_start, 147115013Smarcel uint32_t unwind_end, 148115013Smarcel struct uwx_utable_entry *uentry) 149115013Smarcel{ 150115013Smarcel int lb; 151115013Smarcel int ub; 152129059Smarcel int mid; 153115013Smarcel int len; 154115013Smarcel uint32_t code_start; 155115013Smarcel uint32_t code_end; 156115013Smarcel uint32_t unwind_info; 157115013Smarcel 158115013Smarcel /* Since the unwind table uses segment-relative offsets, convert */ 159115013Smarcel /* the IP in the current context to a segment-relative offset. */ 160115013Smarcel 161129059Smarcel ip -= text_base; 162115013Smarcel 163115013Smarcel TRACE_T_SEARCH32(ip) 164115013Smarcel 165115013Smarcel /* Standard binary search. */ 166115013Smarcel /* Might modify this to do interpolation in the future. */ 167115013Smarcel 168115013Smarcel lb = 0; 169115013Smarcel ub = (unwind_end - unwind_start) / (3 * WORDSZ); 170160163Smarcel mid = 0; 171115013Smarcel while (ub > lb) { 172115013Smarcel mid = (lb + ub) / 2; 173160163Smarcel len = COPYIN_UINFO_4((char *)&code_start, 174160163Smarcel (uintptr_t)(unwind_start+mid*3*WORDSZ)); 175115013Smarcel len += COPYIN_UINFO_4((char *)&code_end, 176160163Smarcel (uintptr_t)(unwind_start+mid*3*WORDSZ+WORDSZ)); 177115013Smarcel if (len != 2 * WORDSZ) 178115013Smarcel return UWX_ERR_COPYIN_UTBL; 179115013Smarcel if (env->byte_swap) { 180115013Smarcel uwx_swap4(&code_start); 181115013Smarcel uwx_swap4(&code_end); 182115013Smarcel } 183115013Smarcel TRACE_T_BINSEARCH32(lb, ub, mid, code_start, code_end) 184115013Smarcel if (ip >= code_end) 185115013Smarcel lb = mid + 1; 186115013Smarcel else if (ip < code_start) 187115013Smarcel ub = mid; 188115013Smarcel else 189115013Smarcel break; 190115013Smarcel } 191115013Smarcel if (ub <= lb) 192115013Smarcel return UWX_ERR_NOUENTRY; 193115013Smarcel len = COPYIN_UINFO_4((char *)&unwind_info, 194160163Smarcel (uintptr_t)(unwind_start+mid*3*WORDSZ+2*WORDSZ)); 195115013Smarcel if (len != WORDSZ) 196115013Smarcel return UWX_ERR_COPYIN_UTBL; 197115013Smarcel if (env->byte_swap) 198115013Smarcel uwx_swap4(&unwind_info); 199160157Smarcel uentry->ptr_size = WORDSZ; 200160157Smarcel uentry->code_start = SWIZZLE(text_base + code_start); 201160157Smarcel uentry->code_end = SWIZZLE(text_base + code_end); 202160157Smarcel uentry->unwind_info = SWIZZLE(text_base + unwind_info); 203115013Smarcel return UWX_OK; 204115013Smarcel} 205115013Smarcel 206115013Smarcel 207115013Smarcel/* uwx_search_utable64: Binary search of 64-bit unwind table */ 208115013Smarcel 209115013Smarcel#define COPYIN_UINFO_8(dest, src) \ 210115013Smarcel (env->remote? \ 211160157Smarcel (*env->copyin)(UWX_COPYIN_UINFO, (dest), (src), \ 212115013Smarcel DWORDSZ, env->cb_token) : \ 213160157Smarcel (*(uint64_t *)(intptr_t)(dest) = *(uint64_t *)(intptr_t)(src), DWORDSZ) ) 214115013Smarcel 215115013Smarcelint uwx_search_utable64( 216115013Smarcel struct uwx_env *env, 217129059Smarcel uint64_t ip, 218115013Smarcel uint64_t text_base, 219115013Smarcel uint64_t unwind_start, 220115013Smarcel uint64_t unwind_end, 221115013Smarcel struct uwx_utable_entry *uentry) 222115013Smarcel{ 223115013Smarcel int lb; 224115013Smarcel int ub; 225129059Smarcel int mid; 226115013Smarcel int len; 227115013Smarcel uint64_t code_start; 228115013Smarcel uint64_t code_end; 229115013Smarcel uint64_t unwind_info; 230115013Smarcel 231115013Smarcel /* Since the unwind table uses segment-relative offsets, convert */ 232115013Smarcel /* the IP in the current context to a segment-relative offset. */ 233115013Smarcel 234129059Smarcel ip -= text_base; 235115013Smarcel 236115013Smarcel /* Standard binary search. */ 237115013Smarcel /* Might modify this to do interpolation in the future. */ 238115013Smarcel 239115013Smarcel lb = 0; 240115013Smarcel ub = (unwind_end - unwind_start) / (3 * DWORDSZ); 241160163Smarcel mid = 0; 242115013Smarcel while (ub > lb) { 243115013Smarcel mid = (lb + ub) / 2; 244115013Smarcel len = COPYIN_UINFO_8((char *)&code_start, unwind_start+mid*3*DWORDSZ); 245115013Smarcel len += COPYIN_UINFO_8((char *)&code_end, 246115013Smarcel unwind_start+mid*3*DWORDSZ+DWORDSZ); 247115013Smarcel if (len != 2 * DWORDSZ) 248115013Smarcel return UWX_ERR_COPYIN_UTBL; 249115013Smarcel if (env->byte_swap) { 250115013Smarcel uwx_swap8(&code_start); 251115013Smarcel uwx_swap8(&code_end); 252115013Smarcel } 253115013Smarcel if (ip >= code_end) 254115013Smarcel lb = mid + 1; 255115013Smarcel else if (ip < code_start) 256115013Smarcel ub = mid; 257115013Smarcel else 258115013Smarcel break; 259115013Smarcel } 260115013Smarcel if (ub <= lb) 261115013Smarcel return UWX_ERR_NOUENTRY; 262115013Smarcel len = COPYIN_UINFO_8((char *)&unwind_info, 263115013Smarcel unwind_start+mid*3*DWORDSZ+2*DWORDSZ); 264115013Smarcel if (len != DWORDSZ) 265115013Smarcel return UWX_ERR_COPYIN_UTBL; 266115013Smarcel if (env->byte_swap) 267115013Smarcel uwx_swap8(&unwind_info); 268160157Smarcel uentry->ptr_size = DWORDSZ; 269115013Smarcel uentry->code_start = text_base + code_start; 270115013Smarcel uentry->code_end = text_base + code_end; 271115013Smarcel uentry->unwind_info = text_base + unwind_info; 272115013Smarcel return UWX_OK; 273115013Smarcel} 274