1/*
2Copyright (c) 2003-2006 Hewlett-Packard Development Company, L.P.
3Permission is hereby granted, free of charge, to any person
4obtaining a copy of this software and associated documentation
5files (the "Software"), to deal in the Software without
6restriction, including without limitation the rights to use,
7copy, modify, merge, publish, distribute, sublicense, and/or sell
8copies of the Software, and to permit persons to whom the
9Software is furnished to do so, subject to the following
10conditions:
11
12The above copyright notice and this permission notice shall be
13included in all copies or substantial portions of the Software.
14
15THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
16EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
17OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
18NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
19HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
20WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
22OTHER DEALINGS IN THE SOFTWARE.
23*/
24
25#include "uwx_env.h"
26#include "uwx_utable.h"
27#include "uwx_swap.h"
28#include "uwx_trace.h"
29
30/*
31 *  uwx_utable.c
32 *
33 *  This file contains the routines for searching an unwind table.
34 *  The main entry point, uwx_search_utable(), gets the
35 *  necessary information from the lookup ip callback's result
36 *  vector, determines whether the table is 32-bit or 64-bit,
37 *  then invokes the binary search routine for that format.
38 */
39
40
41/* Forward declarations */
42
43int uwx_search_utable32(
44    struct uwx_env *env,
45    uint32_t ip,
46    uint32_t text_base,
47    uint32_t unwind_start,
48    uint32_t unwind_end,
49    struct uwx_utable_entry *uentry);
50
51int uwx_search_utable64(
52    struct uwx_env *env,
53    uint64_t ip,
54    uint64_t text_base,
55    uint64_t unwind_start,
56    uint64_t unwind_end,
57    struct uwx_utable_entry *uentry);
58
59
60/* uwx_search_utable: Searches an unwind table for IP in current context */
61
62int uwx_search_utable(
63    struct uwx_env *env,
64    uint64_t ip,
65    uint64_t *uvec,
66    struct uwx_utable_entry *uentry)
67{
68    uint64_t text_base;
69    uint64_t unwind_flags;
70    uint64_t unwind_start;
71    uint64_t unwind_end;
72    int keys;
73    int status;
74
75    /* Get unwind table information from the result vector. */
76    /* Make sure all three required values are given. */
77
78    keys = 0;
79    text_base = 0;
80    unwind_flags = 0;
81    unwind_start = 0;
82    unwind_end = 0;
83    while (*uvec != 0) {
84	switch ((int)*uvec++) {
85	    case UWX_KEY_TBASE:
86		keys |= 1;
87		env->text_base = text_base = *uvec++;
88		break;
89	    case UWX_KEY_UFLAGS:
90		unwind_flags = *uvec++;
91		break;
92	    case UWX_KEY_USTART:
93		keys |= 2;
94		unwind_start = *uvec++;
95		break;
96	    case UWX_KEY_UEND:
97		keys |= 4;
98		unwind_end = *uvec++;
99		break;
100	    case UWX_KEY_GP:
101		uwx_set_reg(env, UWX_REG_GP, *uvec++);
102		break;
103	    default:
104		return UWX_ERR_BADKEY;
105	}
106    }
107    if (keys != 7)
108	return UWX_ERR_BADKEY;
109
110    /* Copy the unwind flags into the unwind entry. */
111    /* (uwx_decode_uinfo needs to know whether it's 32-bit or 64-bit.) */
112
113    uentry->unwind_flags = unwind_flags;
114
115    /* Call the appropriate binary search routine. */
116
117    if (unwind_flags & UNWIND_TBL_32BIT)
118	status = uwx_search_utable32(env,
119			(uint32_t) ip,
120			(uint32_t) text_base,
121			(uint32_t) unwind_start,
122			(uint32_t) unwind_end,
123			uentry);
124    else
125	status = uwx_search_utable64(env,
126			ip, text_base, unwind_start, unwind_end, uentry);
127
128    return status;
129}
130
131
132/* uwx_search_utable32: Binary search of 32-bit unwind table */
133
134#define COPYIN_UINFO_4(dest, src) \
135    (env->remote? \
136	(*env->copyin)(UWX_COPYIN_UINFO, (dest), (src), \
137						WORDSZ, env->cb_token) : \
138	(*(uint32_t *)(dest) = *(uint32_t *)(src), WORDSZ) )
139
140#define SWIZZLE(x) (((uint64_t)((x) & 0xc0000000) << 31) | (x))
141
142int uwx_search_utable32(
143    struct uwx_env *env,
144    uint32_t ip,
145    uint32_t text_base,
146    uint32_t unwind_start,
147    uint32_t unwind_end,
148    struct uwx_utable_entry *uentry)
149{
150    int lb;
151    int ub;
152    int mid;
153    int len;
154    uint32_t code_start;
155    uint32_t code_end;
156    uint32_t unwind_info;
157
158    /* Since the unwind table uses segment-relative offsets, convert */
159    /* the IP in the current context to a segment-relative offset. */
160
161    ip -= text_base;
162
163    TRACE_T_SEARCH32(ip)
164
165    /* Standard binary search. */
166    /* Might modify this to do interpolation in the future. */
167
168    lb = 0;
169    ub = (unwind_end - unwind_start) / (3 * WORDSZ);
170    mid = 0;
171    while (ub > lb) {
172	mid = (lb + ub) / 2;
173	len = COPYIN_UINFO_4((char *)&code_start,
174	    (uintptr_t)(unwind_start+mid*3*WORDSZ));
175	len += COPYIN_UINFO_4((char *)&code_end,
176	    (uintptr_t)(unwind_start+mid*3*WORDSZ+WORDSZ));
177	if (len != 2 * WORDSZ)
178	    return UWX_ERR_COPYIN_UTBL;
179	if (env->byte_swap) {
180	    uwx_swap4(&code_start);
181	    uwx_swap4(&code_end);
182	}
183	TRACE_T_BINSEARCH32(lb, ub, mid, code_start, code_end)
184	if (ip >= code_end)
185	    lb = mid + 1;
186	else if (ip < code_start)
187	    ub = mid;
188	else
189	    break;
190    }
191    if (ub <= lb)
192	return UWX_ERR_NOUENTRY;
193    len = COPYIN_UINFO_4((char *)&unwind_info,
194	(uintptr_t)(unwind_start+mid*3*WORDSZ+2*WORDSZ));
195    if (len != WORDSZ)
196	return UWX_ERR_COPYIN_UTBL;
197    if (env->byte_swap)
198	uwx_swap4(&unwind_info);
199    uentry->ptr_size = WORDSZ;
200    uentry->code_start = SWIZZLE(text_base + code_start);
201    uentry->code_end = SWIZZLE(text_base + code_end);
202    uentry->unwind_info = SWIZZLE(text_base + unwind_info);
203    return UWX_OK;
204}
205
206
207/* uwx_search_utable64: Binary search of 64-bit unwind table */
208
209#define COPYIN_UINFO_8(dest, src) \
210    (env->remote? \
211      (*env->copyin)(UWX_COPYIN_UINFO, (dest), (src), \
212						DWORDSZ, env->cb_token) : \
213      (*(uint64_t *)(intptr_t)(dest) = *(uint64_t *)(intptr_t)(src), DWORDSZ) )
214
215int uwx_search_utable64(
216    struct uwx_env *env,
217    uint64_t ip,
218    uint64_t text_base,
219    uint64_t unwind_start,
220    uint64_t unwind_end,
221    struct uwx_utable_entry *uentry)
222{
223    int lb;
224    int ub;
225    int mid;
226    int len;
227    uint64_t code_start;
228    uint64_t code_end;
229    uint64_t unwind_info;
230
231    /* Since the unwind table uses segment-relative offsets, convert */
232    /* the IP in the current context to a segment-relative offset. */
233
234    ip -= text_base;
235
236    /* Standard binary search. */
237    /* Might modify this to do interpolation in the future. */
238
239    lb = 0;
240    ub = (unwind_end - unwind_start) / (3 * DWORDSZ);
241    mid = 0;
242    while (ub > lb) {
243	mid = (lb + ub) / 2;
244	len = COPYIN_UINFO_8((char *)&code_start, unwind_start+mid*3*DWORDSZ);
245	len += COPYIN_UINFO_8((char *)&code_end,
246				unwind_start+mid*3*DWORDSZ+DWORDSZ);
247	if (len != 2 * DWORDSZ)
248	    return UWX_ERR_COPYIN_UTBL;
249	if (env->byte_swap) {
250	    uwx_swap8(&code_start);
251	    uwx_swap8(&code_end);
252	}
253	if (ip >= code_end)
254	    lb = mid + 1;
255	else if (ip < code_start)
256	    ub = mid;
257	else
258	    break;
259    }
260    if (ub <= lb)
261	return UWX_ERR_NOUENTRY;
262    len = COPYIN_UINFO_8((char *)&unwind_info,
263			unwind_start+mid*3*DWORDSZ+2*DWORDSZ);
264    if (len != DWORDSZ)
265	return UWX_ERR_COPYIN_UTBL;
266    if (env->byte_swap)
267	uwx_swap8(&unwind_info);
268    uentry->ptr_size = DWORDSZ;
269    uentry->code_start = text_base + code_start;
270    uentry->code_end = text_base + code_end;
271    uentry->unwind_info = text_base + unwind_info;
272    return UWX_OK;
273}
274