trunk/src/symbol.c

/*
 *  Copyright (C) 2003-2005  Anders Gavare.  All rights reserved.
 *
 *  Redistribution and use in source and binary forms, with or without
 *  modification, are permitted provided that the following conditions are met:
 *
 *  1. Redistributions of source code must retain the above copyright
 *     notice, this list of conditions and the following disclaimer.
 *  2. Redistributions in binary form must reproduce the above copyright  
 *     notice, this list of conditions and the following disclaimer in the 
 *     documentation and/or other materials provided with the distribution.
 *  3. The name of the author may not be used to endorse or promote products
 *     derived from this software without specific prior written permission.
 *
 *  THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 *  ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 *  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 *  ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE   
 *  FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 *  DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 *  OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 *  HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 *  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 *  OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 *  SUCH DAMAGE.
 *
 *
 *  $Id: symbol.c,v 1.24 2005/04/10 16:42:56 debug Exp $
 *
 *  Address to symbol translation routines.
 *
 *  This module is (probably) independant from the rest of the emulator.
 *  symbol_init() must be called before any other function in this
 *  file is used.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "misc.h"

#include "symbol.h"


#define SYMBOLBUF_MAX   100


/*
 *  symbol_nsymbols():
 *
 *  Return n_symbols.
 */
int symbol_nsymbols(struct symbol_context *sc)
{
        return sc->n_symbols;
}


/*
 *  get_symbol_addr():
 *
 *  Find a symbol by name. If addr is non-NULL, *addr is set to the symbol's
 *  address. Return value is 1 if the symbol is found, 0 otherwise.
 *
 *  NOTE:  This is O(n).
 */
int get_symbol_addr(struct symbol_context *sc, char *symbol, uint64_t *addr)
{
        struct symbol *s;

        if (sc->sorted_array) {
                int i;
                for (i=0; i<sc->n_symbols; i++)
                        if (strcmp(symbol, sc->first_symbol[i].name) == 0) {
                                if (addr != NULL)
                                        *addr = sc->first_symbol[i].addr;
                                return 1;
                        }
        } else {
                s = sc->first_symbol;
                while (s != NULL) {
                        if (strcmp(symbol, s->name) == 0) {
                                if (addr != NULL)
                                        *addr = s->addr;
                                return 1;
                        }
                        s = s->next;
                }
        }

        return 0;
}


/*
 *  get_symbol_name():
 *
 *  Translate an address into a symbol name.  The return value is a pointer
 *  to a static char array, containing the symbol name.  (In other words,
 *  this function is not reentrant. This removes the need for memory allocation
 *  at the caller's side.)
 *
 *  If offset is not a NULL pointer, *offset is set to the offset within
 *  the symbol. For example, if there is a symbol at address 0x1000 with
 *  length 0x100, and a caller wants to know the symbol name of address
 *  0x1008, the symbol's name will be found in the static char array, and
 *  *offset will be set to 0x8.
 *
 *  If no symbol was found, NULL is returned instead.
 */
static char symbol_buf[SYMBOLBUF_MAX+1];
char *get_symbol_name(struct symbol_context *sc, uint64_t addr,
        uint64_t *offset)
{
        struct symbol *s;
        int stepsize, ofs;

        if (sc->n_symbols == 0)
                return NULL;

        if ((addr >> 32) == 0 && (addr & 0x80000000ULL))
                addr |= 0xffffffff00000000ULL;

        symbol_buf[0] = symbol_buf[SYMBOLBUF_MAX] = '\0';
        if (offset != NULL)
                *offset = 0;

        if (!sc->sorted_array) {
                /*  Slow, linear O(n) search:  */
                s = sc->first_symbol;
                while (s != NULL) {
                        /*  Found a match?  */
                        if (addr >= s->addr && addr < s->addr + s->len) {
                                if (addr == s->addr)
                                        snprintf(symbol_buf, SYMBOLBUF_MAX,
                                            "%s", s->name);
                                else
                                        snprintf(symbol_buf, SYMBOLBUF_MAX,
                                            "%s+0x%lx", s->name, (long)
                                            (addr - s->addr));
                                if (offset != NULL)
                                        *offset = addr - s->addr;
                                return symbol_buf;
                        }
                        s = s->next;
                }
        } else {
                /*  Faster, O(log n) search:  */
                stepsize = sc->n_symbols / 2;
                ofs = stepsize;
                while (stepsize > 0 || (stepsize == 0 && ofs == 0)) {
                        s = sc->first_symbol + ofs;

                        /*  Found a match?  */
                        if (addr >= s->addr && addr < s->addr + s->len) {
                                if (addr == s->addr)
                                        snprintf(symbol_buf, SYMBOLBUF_MAX,
                                            "%s", s->name);
                                else
                                        snprintf(symbol_buf, SYMBOLBUF_MAX,
                                            "%s+0x%lx", s->name, (long)
                                            (addr - s->addr));
                                if (offset != NULL)
                                        *offset = addr - s->addr;
                                return symbol_buf;
                        }

                        if (ofs == 0)
                                break;

                        stepsize >>= 1;

                        /*  Special case for offset 0 (end of search in
                            the Left direction  */
                        if (stepsize == 0)
                                ofs = 0;
                        else {
                                if (addr < s->addr)
                                        ofs -= stepsize;
                                else
                                        ofs += stepsize;
                        }
                }
        }

        /*  Not found? Then return NULL.  */
        return NULL;
}


/*
 *  add_symbol_name():
 *
 *  Add a symbol to the symbol list.
 */
void add_symbol_name(struct symbol_context *sc,
        uint64_t addr, uint64_t len, char *name, int type)
{
        struct symbol *s;

        if (sc->sorted_array) {
                fprintf(stderr, "add_symbol_name(): Internal error: the "
                    "symbol array is already sorted\n");
                exit(1);
        }

        if (name == NULL) {
                fprintf(stderr, "add_symbol_name(): name = NULL\n");
                exit(1);
        }

        /*  TODO: Maybe this should be optional?  */
        if (name[0] == '$')
                return;

        if ((addr >> 32) == 0 && (addr & 0x80000000ULL))
                addr |= 0xffffffff00000000ULL;

        s = malloc(sizeof(struct symbol));
        if (s == NULL) {
                fprintf(stderr, "out of memory\n");
                exit(1);
        }

        s->name = strdup(name);
        if (s->name == NULL) {
                fprintf(stderr, "out of memory\n");
                exit(1);
        }
        s->addr = addr;
        s->len  = len;
        s->type = type;

        sc->n_symbols ++;

        /*  Add first in list:  */
        s->next = sc->first_symbol;
        sc->first_symbol = s;
}


/*
 *  symbol_readfile():
 *
 *  Read 'nm -S' style symbols from a file.
 *
 *  TODO: This function is an ugly hack, and should be replaced
 *  with something that reads symbols directly from the executable
 *  images.
 */
void symbol_readfile(struct symbol_context *sc, char *fname)
{
        FILE *f;
        char b1[80]; uint64_t addr;
        char b2[80]; uint64_t len;
        char b3[80]; int type;
        char b4[80];
        int cur_n_symbols = sc->n_symbols;

        f = fopen(fname, "r");
        if (f == NULL) {
                perror(fname);
                exit(1);
        }

        while (!feof(f)) {
                memset(b1, 0, sizeof(b1));
                memset(b2, 0, sizeof(b2));
                memset(b3, 0, sizeof(b3));
                memset(b4, 0, sizeof(b4));
                fscanf(f, "%s %s\n", b1,b2);
                if (strlen(b2) < 2 && !(b2[0]>='0' && b2[0]<='9')) {
                        strcpy(b3, b2);
                        strcpy(b2, "0");
                        fscanf(f, "%s\n", b4);
                } else {
                        fscanf(f, "%s %s\n", b3,b4);
                }

                /*  printf("b1='%s' b2='%s' b3='%s' b4='%s'\n",
                    b1,b2,b3,b4);  */
                addr = strtoull(b1, NULL, 16);
                len  = strtoull(b2, NULL, 16);
                type = b3[0];
                /*  printf("addr=%016llx len=%016llx type=%i\n",
                    addr, len, type);  */

                if (type == 't' || type == 'r' || type == 'g')
                        continue;

                add_symbol_name(sc, addr, len, b4, type);
        }

        fclose(f);

        debug("%i symbols\n", sc->n_symbols - cur_n_symbols);
}


/*
 *  sym_addr_compare():
 *
 *  Helper function for sorting symbols according to their address.
 */
int sym_addr_compare(const void *a, const void *b)
{
        struct symbol *p1 = (struct symbol *) a;
        struct symbol *p2 = (struct symbol *) b;

        if (p1->addr < p2->addr)
                return -1;
        if (p1->addr > p2->addr)
                return 1;

        return 0;
}


/*
 *  symbol_recalc_sizes():
 *
 *  Recalculate sizes of symbols that have size = 0, by creating an array
 *  containing all symbols, qsort()-ing that array according to address, and
 *  recalculating the size fields if necessary.
 */
void symbol_recalc_sizes(struct symbol_context *sc)
{
        struct symbol *tmp_array;
        struct symbol *last_ptr;
        struct symbol *tmp_ptr;
        int i;

        tmp_array = malloc(sizeof (struct symbol) * sc->n_symbols);
        if (tmp_array == NULL) {
                fprintf(stderr, "out of memory\n");
                exit(1);
        }

        /*  Copy first_symbol --> tmp_array, and remove the old
                first_symbol at the same time:  */
        tmp_ptr = sc->first_symbol;
        i = 0;
        while (tmp_ptr != NULL) {
                tmp_array[i] = *tmp_ptr;
                last_ptr = tmp_ptr;
                tmp_ptr = tmp_ptr->next;
                free(last_ptr);
                i++;
        }

        qsort(tmp_array, sc->n_symbols, sizeof(struct symbol),
            sym_addr_compare);
        sc->sorted_array = 1;

        /*  Recreate the first_symbol chain:  */
        sc->first_symbol = NULL;
        for (i=0; i<sc->n_symbols; i++) {
                /*  Recalculate size, if 0:  */
                if (tmp_array[i].len == 0) {
                        uint64_t len;
                        if (i != sc->n_symbols-1)
                                len = tmp_array[i+1].addr
                                    - tmp_array[i].addr;
                        else
                                len = 1;
                        tmp_array[i].len = len;
                }

                tmp_array[i].next = &tmp_array[i+1];
        }

        sc->first_symbol = tmp_array;
}


/*
 *  symbol_init():
 *
 *  Initialize the symbol hashtables.
 */
void symbol_init(struct symbol_context *sc)
{
        sc->first_symbol = NULL;
        sc->sorted_array = 0;
        sc->n_symbols = 0;
}

1	/*
2	* Copyright (C) 2003-2005 Anders Gavare. All rights reserved.
3	*
4	* Redistribution and use in source and binary forms, with or without
5	* modification, are permitted provided that the following conditions are met:
6	*
7	* 1. Redistributions of source code must retain the above copyright
8	* notice, this list of conditions and the following disclaimer.
9	* 2. Redistributions in binary form must reproduce the above copyright
10	* notice, this list of conditions and the following disclaimer in the
11	* documentation and/or other materials provided with the distribution.
12	* 3. The name of the author may not be used to endorse or promote products
13	* derived from this software without specific prior written permission.
14	*
15	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
16	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18	* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
19	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
21	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
22	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
25	* SUCH DAMAGE.
26	*
27	*
28	* $Id: symbol.c,v 1.24 2005/04/10 16:42:56 debug Exp $
29	*
30	* Address to symbol translation routines.
31	*
32	* This module is (probably) independant from the rest of the emulator.
33	* symbol_init() must be called before any other function in this
34	* file is used.
35	*/
36
37	#include <stdio.h>
38	#include <stdlib.h>
39	#include <string.h>
40
41	#include "misc.h"
42
43	#include "symbol.h"
44
45
46	#define SYMBOLBUF_MAX 100
47
48
49	/*
50	* symbol_nsymbols():
51	*
52	* Return n_symbols.
53	*/
54	int symbol_nsymbols(struct symbol_context *sc)
55	{
56	return sc->n_symbols;
57	}
58
59
60	/*
61	* get_symbol_addr():
62	*
63	* Find a symbol by name. If addr is non-NULL, *addr is set to the symbol's
64	* address. Return value is 1 if the symbol is found, 0 otherwise.
65	*
66	* NOTE: This is O(n).
67	*/
68	int get_symbol_addr(struct symbol_context sc, char symbol, uint64_t *addr)
69	{
70	struct symbol *s;
71
72	if (sc->sorted_array) {
73	int i;
74	for (i=0; i<sc->n_symbols; i++)
75	if (strcmp(symbol, sc->first_symbol[i].name) == 0) {
76	if (addr != NULL)
77	*addr = sc->first_symbol[i].addr;
78	return 1;
79	}
80	} else {
81	s = sc->first_symbol;
82	while (s != NULL) {
83	if (strcmp(symbol, s->name) == 0) {
84	if (addr != NULL)
85	*addr = s->addr;
86	return 1;
87	}
88	s = s->next;
89	}
90	}
91
92	return 0;
93	}
94
95
96	/*
97	* get_symbol_name():
98	*
99	* Translate an address into a symbol name. The return value is a pointer
100	* to a static char array, containing the symbol name. (In other words,
101	* this function is not reentrant. This removes the need for memory allocation
102	* at the caller's side.)
103	*
104	* If offset is not a NULL pointer, *offset is set to the offset within
105	* the symbol. For example, if there is a symbol at address 0x1000 with
106	* length 0x100, and a caller wants to know the symbol name of address
107	* 0x1008, the symbol's name will be found in the static char array, and
108	* *offset will be set to 0x8.
109	*
110	* If no symbol was found, NULL is returned instead.
111	*/
112	static char symbol_buf[SYMBOLBUF_MAX+1];
113	char get_symbol_name(struct symbol_context sc, uint64_t addr,
114	uint64_t *offset)
115	{
116	struct symbol *s;
117	int stepsize, ofs;
118
119	if (sc->n_symbols == 0)
120	return NULL;
121
122	if ((addr >> 32) == 0 && (addr & 0x80000000ULL))
123	addr \|= 0xffffffff00000000ULL;
124
125	symbol_buf[0] = symbol_buf[SYMBOLBUF_MAX] = '\0';
126	if (offset != NULL)
127	*offset = 0;
128
129	if (!sc->sorted_array) {
130	/* Slow, linear O(n) search: */
131	s = sc->first_symbol;
132	while (s != NULL) {
133	/* Found a match? */
134	if (addr >= s->addr && addr < s->addr + s->len) {
135	if (addr == s->addr)
136	snprintf(symbol_buf, SYMBOLBUF_MAX,
137	"%s", s->name);
138	else
139	snprintf(symbol_buf, SYMBOLBUF_MAX,
140	"%s+0x%lx", s->name, (long)
141	(addr - s->addr));
142	if (offset != NULL)
143	*offset = addr - s->addr;
144	return symbol_buf;
145	}
146	s = s->next;
147	}
148	} else {
149	/* Faster, O(log n) search: */
150	stepsize = sc->n_symbols / 2;
151	ofs = stepsize;
152	while (stepsize > 0 \|\| (stepsize == 0 && ofs == 0)) {
153	s = sc->first_symbol + ofs;
154
155	/* Found a match? */
156	if (addr >= s->addr && addr < s->addr + s->len) {
157	if (addr == s->addr)
158	snprintf(symbol_buf, SYMBOLBUF_MAX,
159	"%s", s->name);
160	else
161	snprintf(symbol_buf, SYMBOLBUF_MAX,
162	"%s+0x%lx", s->name, (long)
163	(addr - s->addr));
164	if (offset != NULL)
165	*offset = addr - s->addr;
166	return symbol_buf;
167	}
168
169	if (ofs == 0)
170	break;
171
172	stepsize >>= 1;
173
174	/* Special case for offset 0 (end of search in
175	the Left direction */
176	if (stepsize == 0)
177	ofs = 0;
178	else {
179	if (addr < s->addr)
180	ofs -= stepsize;
181	else
182	ofs += stepsize;
183	}
184	}
185	}
186
187	/* Not found? Then return NULL. */
188	return NULL;
189	}
190
191
192	/*
193	* add_symbol_name():
194	*
195	* Add a symbol to the symbol list.
196	*/
197	void add_symbol_name(struct symbol_context *sc,
198	uint64_t addr, uint64_t len, char *name, int type)
199	{
200	struct symbol *s;
201
202	if (sc->sorted_array) {
203	fprintf(stderr, "add_symbol_name(): Internal error: the "
204	"symbol array is already sorted\n");
205	exit(1);
206	}
207
208	if (name == NULL) {
209	fprintf(stderr, "add_symbol_name(): name = NULL\n");
210	exit(1);
211	}
212
213	/* TODO: Maybe this should be optional? */
214	if (name[0] == '$')
215	return;
216
217	if ((addr >> 32) == 0 && (addr & 0x80000000ULL))
218	addr \|= 0xffffffff00000000ULL;
219
220	s = malloc(sizeof(struct symbol));
221	if (s == NULL) {
222	fprintf(stderr, "out of memory\n");
223	exit(1);
224	}
225
226	s->name = strdup(name);
227	if (s->name == NULL) {
228	fprintf(stderr, "out of memory\n");
229	exit(1);
230	}
231	s->addr = addr;
232	s->len = len;
233	s->type = type;
234
235	sc->n_symbols ++;
236
237	/* Add first in list: */
238	s->next = sc->first_symbol;
239	sc->first_symbol = s;
240	}
241
242
243	/*
244	* symbol_readfile():
245	*
246	* Read 'nm -S' style symbols from a file.
247	*
248	* TODO: This function is an ugly hack, and should be replaced
249	* with something that reads symbols directly from the executable
250	* images.
251	*/
252	void symbol_readfile(struct symbol_context sc, char fname)
253	{
254	FILE *f;
255	char b1[80]; uint64_t addr;
256	char b2[80]; uint64_t len;
257	char b3[80]; int type;
258	char b4[80];
259	int cur_n_symbols = sc->n_symbols;
260
261	f = fopen(fname, "r");
262	if (f == NULL) {
263	perror(fname);
264	exit(1);
265	}
266
267	while (!feof(f)) {
268	memset(b1, 0, sizeof(b1));
269	memset(b2, 0, sizeof(b2));
270	memset(b3, 0, sizeof(b3));
271	memset(b4, 0, sizeof(b4));
272	fscanf(f, "%s %s\n", b1,b2);
273	if (strlen(b2) < 2 && !(b2[0]>='0' && b2[0]<='9')) {
274	strcpy(b3, b2);
275	strcpy(b2, "0");
276	fscanf(f, "%s\n", b4);
277	} else {
278	fscanf(f, "%s %s\n", b3,b4);
279	}
280
281	/* printf("b1='%s' b2='%s' b3='%s' b4='%s'\n",
282	b1,b2,b3,b4); */
283	addr = strtoull(b1, NULL, 16);
284	len = strtoull(b2, NULL, 16);
285	type = b3[0];
286	/* printf("addr=%016llx len=%016llx type=%i\n",
287	addr, len, type); */
288
289	if (type == 't' \|\| type == 'r' \|\| type == 'g')
290	continue;
291
292	add_symbol_name(sc, addr, len, b4, type);
293	}
294
295	fclose(f);
296
297	debug("%i symbols\n", sc->n_symbols - cur_n_symbols);
298	}
299
300
301	/*
302	* sym_addr_compare():
303	*
304	* Helper function for sorting symbols according to their address.
305	*/
306	int sym_addr_compare(const void a, const void b)
307	{
308	struct symbol p1 = (struct symbol ) a;
309	struct symbol p2 = (struct symbol ) b;
310
311	if (p1->addr < p2->addr)
312	return -1;
313	if (p1->addr > p2->addr)
314	return 1;
315
316	return 0;
317	}
318
319
320	/*
321	* symbol_recalc_sizes():
322	*
323	* Recalculate sizes of symbols that have size = 0, by creating an array
324	* containing all symbols, qsort()-ing that array according to address, and
325	* recalculating the size fields if necessary.
326	*/
327	void symbol_recalc_sizes(struct symbol_context *sc)
328	{
329	struct symbol *tmp_array;
330	struct symbol *last_ptr;
331	struct symbol *tmp_ptr;
332	int i;
333
334	tmp_array = malloc(sizeof (struct symbol) * sc->n_symbols);
335	if (tmp_array == NULL) {
336	fprintf(stderr, "out of memory\n");
337	exit(1);
338	}
339
340	/* Copy first_symbol --> tmp_array, and remove the old
341	first_symbol at the same time: */
342	tmp_ptr = sc->first_symbol;
343	i = 0;
344	while (tmp_ptr != NULL) {
345	tmp_array[i] = *tmp_ptr;
346	last_ptr = tmp_ptr;
347	tmp_ptr = tmp_ptr->next;
348	free(last_ptr);
349	i++;
350	}
351
352	qsort(tmp_array, sc->n_symbols, sizeof(struct symbol),
353	sym_addr_compare);
354	sc->sorted_array = 1;
355
356	/* Recreate the first_symbol chain: */
357	sc->first_symbol = NULL;
358	for (i=0; i<sc->n_symbols; i++) {
359	/* Recalculate size, if 0: */
360	if (tmp_array[i].len == 0) {
361	uint64_t len;
362	if (i != sc->n_symbols-1)
363	len = tmp_array[i+1].addr
364	- tmp_array[i].addr;
365	else
366	len = 1;
367	tmp_array[i].len = len;
368	}
369
370	tmp_array[i].next = &tmp_array[i+1];
371	}
372
373	sc->first_symbol = tmp_array;
374	}
375
376
377	/*
378	* symbol_init():
379	*
380	* Initialize the symbol hashtables.
381	*/
382	void symbol_init(struct symbol_context *sc)
383	{
384	sc->first_symbol = NULL;
385	sc->sorted_array = 0;
386	sc->n_symbols = 0;
387	}
388