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