1/*
2 * Copyright (c) 2000-2005 Apple Computer, Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28/*
29 * @OSF_COPYRIGHT@
30 */
31/*
32 * Mach Operating System
33 * Copyright (c) 1991,1990 Carnegie Mellon University
34 * All Rights Reserved.
35 *
36 * Permission to use, copy, modify and distribute this software and its
37 * documentation is hereby granted, provided that both the copyright
38 * notice and this permission notice appear in all copies of the
39 * software, derivative works or modified versions, and any portions
40 * thereof, and that both notices appear in supporting documentation.
41 *
42 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
43 * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
44 * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
45 *
46 * Carnegie Mellon requests users of this software to return to
47 *
48 *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
49 *  School of Computer Science
50 *  Carnegie Mellon University
51 *  Pittsburgh PA 15213-3890
52 *
53 * any improvements or extensions that they make and grant Carnegie Mellon
54 * the rights to redistribute these changes.
55 */
56/*
57 */
58/*
59 * 	Author: David B. Golub, Carnegie Mellon University
60 *	Date:	7/90
61 */
62
63#include <machine/db_machdep.h>
64#include <string.h>			/* For strcpy(), strcmp() */
65#include <mach/std_types.h>
66#include <kern/misc_protos.h>		/* For printf() */
67#include <kern/kalloc.h>
68#include <ddb/db_sym.h>
69#include <ddb/db_task_thread.h>
70#include <ddb/db_command.h>
71#include <ddb/db_output.h>		/* For db_printf() */
72
73#include <vm/vm_map.h>	/* vm_map_t */
74
75/*
76 * Multiple symbol tables
77 *
78 * mach, bootstrap, name_server, default_pager, unix, 1 spare
79 */
80#define	MAXNOSYMTABS	6
81
82db_symtab_t db_symtabs[MAXNOSYMTABS];
83int db_nsymtab = 0;
84
85db_symtab_t	*db_last_symtab;
86
87unsigned long	db_maxoff = 0x4000;
88extern		char end;
89unsigned long	db_maxval = (unsigned long)&end;
90natural_t	db_minval = 0x1000;
91
92/* Prototypes for functions local to this file.  XXX -- should be static!
93 */
94static char *db_qualify(
95	char		*sym,
96	register char	*symtabname);
97
98boolean_t db_eqname(
99	char		*src,
100	char		*dst,
101	unsigned	c);
102
103boolean_t db_symbol_is_ambiguous(char *name);
104
105void db_shorten_filename(char **filenamep);
106
107void qsort_swap(
108	register int	*a,
109	register int	*b,
110	register int	size);
111
112void qsort_rotate(
113	register int	*a,
114	register int	*b,
115	register int	*c,
116	register int	size);
117
118void qsort_recur(
119	char	*left,
120	char	*right,
121	int	eltsize,
122	int	(*compfun)(char *, char *));
123
124void qsort_checker(
125	char	*table,
126	int	nbelts,
127	int	eltsize,
128	int	(*compfun)(char *, char *));
129
130void bubble_sort(
131	char	*table,
132	int	nbelts,
133	int	eltsize,
134	int	(*compfun)(char *, char *));
135
136int no_print_completion(
137	db_symtab_t	*stab,
138	char		*symstr	);
139int no_lookup_incomplete(
140	db_symtab_t	*stab,
141	char		*symstr,
142	char		**name,
143	int		*len,
144	int		*toadd);
145
146/*
147 * Initialization routine for ddb.
148 */
149void
150ddb_init(void)
151{
152	X_db_init();
153	db_machdep_init();
154}
155
156extern vm_map_t kernel_map;
157/*
158 * Add symbol table, with given name, to list of symbol tables.
159 */
160boolean_t
161db_add_symbol_table(
162	int		type,
163	char		*start,
164	char		*db_end,
165	const char	*name,
166	char		*ref,
167	char		*map_pointer,
168	unsigned long	minsym,
169	unsigned long	maxsym,
170	boolean_t	sorted)
171{
172	register db_symtab_t *st;
173
174	if (db_nsymtab >= MAXNOSYMTABS)
175	    return (FALSE);
176
177	st = &db_symtabs[db_nsymtab];
178	st->type = type;
179	st->start = start;
180	st->end = db_end;
181	st->private = ref;
182	if (map_pointer == (char *)kernel_map ||
183	    (VM_MIN_KERNEL_ADDRESS - VM_MAX_ADDRESS > 0 &&
184	     minsym - VM_MIN_KERNEL_ADDRESS > 0))
185		st->map_pointer = 0;
186	else
187		st->map_pointer = map_pointer;
188	strcpy(st->name, name);
189	st->minsym = minsym;
190	st->maxsym = maxsym;
191	if (maxsym == 0)
192		st->sorted = FALSE;
193	else {
194		st->sorted = sorted;
195		if (db_maxval < maxsym + db_maxoff)
196			db_maxval = maxsym + db_maxoff;
197	}
198	db_nsymtab++;
199
200	return (TRUE);
201}
202
203/*
204 *  db_qualify("vm_map", "ux") returns "ux::vm_map".
205 *
206 *  Note: return value points to static data whose content is
207 *  overwritten by each call... but in practice this seems okay.
208 */
209static char *
210db_qualify(
211	char		*symname,
212	register char	*symtabname)
213{
214	static char     tmp[256];
215	register char	*s;
216
217	s = tmp;
218	while ((*s++ = *symtabname++)) {
219		;
220	}
221	s[-1] = ':';
222	*s++ = ':';
223	while ((*s++ = *symname++)) {
224		;
225	}
226	return tmp;
227}
228
229
230boolean_t
231db_eqname(
232	char		*src,
233	char		*dst,
234	unsigned	c)
235{
236	if (!strcmp(src, dst))
237	    return (TRUE);
238	if (src[0] == (char)c)
239	    return (!strcmp(src+1,dst));
240	return (FALSE);
241}
242
243boolean_t
244db_value_of_name(
245	const char	*name,
246	db_expr_t	*valuep)
247{
248	db_sym_t	sym;
249
250	sym = db_lookup(name);
251	if (sym == DB_SYM_NULL)
252	    return (FALSE);
253	db_symbol_values(0, sym, &name, valuep);
254	return (TRUE);
255}
256
257/*
258 * Display list of possible completions for a symbol.
259 */
260void
261db_print_completion(
262	char *symstr)
263{
264	register int i;
265	int symtab_start = 0;
266	int symtab_end = db_nsymtab;
267	register char *cp;
268
269	/*
270	 * Look for, remove, and remember any symbol table specifier.
271	 */
272	for (cp = symstr; *cp; cp++) {
273		if (*cp == ':' && cp[1] == ':') {
274			*cp = '\0';
275			for (i = 0; i < db_nsymtab; i++) {
276				if (! strcmp(symstr, db_symtabs[i].name)) {
277					symtab_start = i;
278					symtab_end = i + 1;
279					break;
280				}
281			}
282			*cp = ':';
283			if (i == db_nsymtab)
284				return;
285			symstr = cp+2;
286		}
287	}
288
289	/*
290	 * Look in the specified set of symbol tables.
291	 * Return on first match.
292	 */
293	for (i = symtab_start; i < symtab_end; i++) {
294		if (X_db_print_completion(&db_symtabs[i], symstr))
295			break;
296	}
297}
298
299/*
300 * Lookup a (perhaps incomplete) symbol.
301 * If the symbol has a qualifier (e.g., ux::vm_map),
302 * then only the specified symbol table will be searched;
303 * otherwise, all symbol tables will be searched.
304 */
305int
306db_lookup_incomplete(
307	char *symstr,
308	int symlen)
309{
310	register int i;
311	int symtab_start = 0;
312	int symtab_end = db_nsymtab;
313	register char *cp;
314	int nsym = 0;
315	char *name = (char *)0;
316	int len;
317	int toadd;
318
319	/*
320	 * Look for, remove, and remember any symbol table specifier.
321	 */
322	for (cp = symstr; *cp; cp++) {
323		if (*cp == ':' && cp[1] == ':') {
324			*cp = '\0';
325			for (i = 0; i < db_nsymtab; i++) {
326				if (! strcmp(symstr, db_symtabs[i].name)) {
327					symtab_start = i;
328					symtab_end = i + 1;
329					break;
330				}
331			}
332			*cp = ':';
333			if (i == db_nsymtab)
334				return 0;
335			symstr = cp+2;
336		}
337	}
338
339	/*
340	 * Look in the specified set of symbol tables.
341	 * Return on first match.
342	 */
343	for (i = symtab_start; i < symtab_end; i++) {
344		nsym = X_db_lookup_incomplete(&db_symtabs[i], symstr,
345					      &name, &len, &toadd);
346		if (nsym > 0) {
347			if (toadd > 0) {
348				len = strlen(symstr);
349				if (len + toadd >= symlen)
350					return 0;
351				bcopy(&name[len], &symstr[len], toadd);
352				symstr[len + toadd] = '\0';
353			}
354			break;
355		}
356	}
357	return nsym;
358}
359
360/*
361 * Lookup a symbol.
362 * If the symbol has a qualifier (e.g., ux::vm_map),
363 * then only the specified symbol table will be searched;
364 * otherwise, all symbol tables will be searched.
365 */
366db_sym_t
367db_lookup(const char *symstr)
368{
369	db_sym_t sp;
370	int i;
371	int symtab_start = 0;
372	int symtab_end = db_nsymtab;
373	char *cp;
374
375	/*
376	 * Look for, remove, and remember any symbol table specifier.
377	 */
378	for (cp = symstr; *cp; cp++) {
379		if (*cp == ':' && cp[1] == ':') {
380			*cp = '\0';
381			for (i = 0; i < db_nsymtab; i++) {
382				if (! strcmp(symstr, db_symtabs[i].name)) {
383					symtab_start = i;
384					symtab_end = i + 1;
385					break;
386				}
387			}
388			*cp = ':';
389			if (i == db_nsymtab)
390				db_error("Invalid symbol table name\n");
391			symstr = cp+2;
392		}
393	}
394
395	/*
396	 * Look in the specified set of symbol tables.
397	 * Return on first match.
398	 */
399	for (i = symtab_start; i < symtab_end; i++) {
400		if ((sp = X_db_lookup(&db_symtabs[i], symstr))) {
401			db_last_symtab = &db_symtabs[i];
402			return sp;
403		}
404	}
405	return 0;
406}
407
408/*
409 * Print a symbol completion
410 */
411void
412db_sym_print_completion(
413	db_symtab_t *stab,
414	char *name,
415	int function,
416	char *fname,
417	int line)
418{
419	if (stab != db_symtabs)
420		db_printf("%s::", stab->name);
421	db_printf(name);
422	if (function) {
423	    db_putchar('(');
424	    db_putchar(')');
425	}
426	if (fname) {
427	    db_printf(" [static from %s", fname);
428	    if (line > 0)
429		db_printf(":%d", line);
430	    db_putchar(']');
431	}
432	db_putchar('\n');
433}
434
435/*
436 * Common utility routine to parse a symbol string into a file
437 * name, a (possibly incomplete) symbol name without line number.
438 * This routine is called from aout_db_print_completion if the object
439 * dependent handler supports qualified search with a file name.
440 * It parses the symbol string, and call an object dependent routine
441 * with parsed file name and symbol name.
442 */
443int
444db_sym_parse_and_print_completion(
445	int		(*func)(db_symtab_t *,
446				 char *),
447	db_symtab_t	*symtab,
448	char		*symstr)
449{
450	register 	char *p;
451	register int	n;
452	char	 	*sym_name;
453	char		*component[2];
454	int		nsym;
455
456	/*
457	 * disassemble the symbol into components: [file_name:]symbol
458	 */
459	component[0] = symstr;
460	component[1] = 0;
461	for (p = symstr, n = 1; *p; p++) {
462		if (*p == ':') {
463			if (n == 2)
464				break;
465			*p = 0;
466			component[n++] = p+1;
467		}
468	}
469	if (*p == 0) {
470		if (n == 1) {
471			sym_name = component[0];
472		} else {
473			sym_name = component[1];
474		}
475		nsym = func(symtab, sym_name);
476	} else
477		nsym = 0;
478	if (n == 2)
479		component[1][-1] = ':';
480	return nsym;
481}
482
483/*
484 * Common utility routine to parse a symbol string into a file
485 * name, a (possibly incomplete) symbol name without line number.
486 * This routine is called from X_db_lookup_incomplete if the object
487 * dependent handler supports qualified search with a file name.
488 * It parses the symbol string, and call an object dependent routine
489 * with parsed file name and symbol name.
490 */
491int
492db_sym_parse_and_lookup_incomplete(
493	int		(*func)(db_symtab_t *,
494				char *,
495				char *,
496				int,
497				db_sym_t*,
498				char **,
499				int *),
500	db_symtab_t	*symtab,
501	char		*symstr,
502	char		**name,
503	int		*len,
504	int		*toadd)
505{
506	register 	char *p;
507	register int	n;
508	char	 	*file_name = 0;
509	char	 	*sym_name = 0;
510	char		*component[2];
511	int		nsym = 0;
512
513	/*
514	 * disassemble the symbol into components: [file_name:]symbol
515	 */
516	component[0] = symstr;
517	component[1] = 0;
518	for (p = symstr, n = 1; *p; p++) {
519		if (*p == ':') {
520			if (n == 2)
521				break;
522			*p = 0;
523			component[n++] = p+1;
524		}
525	}
526	if (*p == 0) {
527		if (n == 1) {
528			file_name = 0;
529			sym_name = component[0];
530		} else {
531			file_name = component[0];
532			sym_name = component[1];
533		}
534		nsym = func(symtab, file_name, sym_name, 0, (db_sym_t *)0,
535			    name, len);
536		if (nsym > 0)
537			*toadd = *len - strlen(sym_name);
538	}
539	if (n == 2)
540		component[1][-1] = ':';
541	return(nsym);
542}
543
544/*
545 * Common utility routine to parse a symbol string into a file
546 * name, a symbol name and line number.
547 * This routine is called from aout_db_lookup if the object dependent
548 * handler supports qualified search with a file name or a line number.
549 * It parses the symbol string, and call an object dependent routine
550 * with parsed file name, symbol name and line number.
551 */
552db_sym_t
553db_sym_parse_and_lookup(
554	int		(*func)(db_symtab_t *, char *, char *, int,
555				db_sym_t*, char **, int *),
556	db_symtab_t	*symtab,
557	char		*symstr)
558{
559	register 	char *p;
560	register int	n;
561	int	 	n_name;
562	int	 	line_number;
563	char	 	*file_name = 0;
564	char	 	*sym_name = 0;
565	char		*component[3];
566	db_sym_t 	found = DB_SYM_NULL;
567
568	/*
569	 * disassemble the symbol into components:
570	 *	[file_name:]symbol[:line_nubmer]
571	 */
572	component[0] = symstr;
573	component[1] = component[2] = 0;
574	for (p = symstr, n = 1; *p; p++) {
575		if (*p == ':') {
576			if (n >= 3)
577				break;
578			*p = 0;
579			component[n++] = p+1;
580		}
581	}
582	if (*p != 0)
583		goto out;
584	line_number = 0;
585	n_name = n;
586	p = component[n-1];
587	if (*p >= '0' && *p <= '9') {
588		if (n == 1)
589			goto out;
590		for (line_number = 0; *p; p++) {
591			if (*p < '0' || *p > '9')
592				goto out;
593			line_number = line_number*10 + *p - '0';
594		}
595		n_name--;
596	} else if (n >= 3)
597		goto out;
598	if (n_name == 1) {
599		for (p = component[0]; *p && *p != '.'; p++);
600		if (*p == '.') {
601			file_name = component[0];
602			sym_name = 0;
603		} else {
604			file_name = 0;
605			sym_name = component[0];
606		}
607	} else {
608		file_name = component[0];
609		sym_name = component[1];
610	}
611	(void) func(symtab, file_name, sym_name, line_number, &found,
612		   (char **)0, (int *)0);
613
614out:
615	while (--n >= 1)
616		component[n][-1] = ':';
617	return(found);
618}
619
620/*
621 * Does this symbol name appear in more than one symbol table?
622 * Used by db_symbol_values to decide whether to qualify a symbol.
623 */
624boolean_t db_qualify_ambiguous_names = TRUE;
625
626boolean_t
627db_symbol_is_ambiguous(char *name)
628{
629	register int	i;
630	register
631	boolean_t	found_once = FALSE;
632
633	if (!db_qualify_ambiguous_names)
634		return FALSE;
635
636	for (i = 0; i < db_nsymtab; i++) {
637		if (X_db_lookup(&db_symtabs[i], name)) {
638			if (found_once)
639				return TRUE;
640			found_once = TRUE;
641		}
642	}
643	return FALSE;
644}
645
646/*
647 * Find the closest symbol to val, and return its name
648 * and the difference between val and the symbol found.
649 */
650unsigned int db_search_maxoff = 0x4000;
651db_sym_t
652db_search_task_symbol(
653	register db_addr_t	val,
654	db_strategy_t		strategy,
655	db_addr_t		*offp,	/* better be unsigned */
656	task_t			task)
657{
658	db_addr_t diff, newdiff;
659	register int	i;
660	db_symtab_t	*sp;
661	db_sym_t	ret = DB_SYM_NULL, sym;
662	vm_map_t	map_for_val;
663
664	if (task == TASK_NULL)
665	    task = db_current_task();
666	map_for_val = (task == TASK_NULL)? VM_MAP_NULL: task->map;
667again:
668	newdiff = diff = -1;
669	db_last_symtab = 0;
670	for (sp = &db_symtabs[0], i = 0;
671	     i < db_nsymtab;
672	     sp++, i++) {
673	    if ((((vm_map_t)sp->map_pointer == VM_MAP_NULL) ||
674			((vm_map_t)sp->map_pointer == map_for_val)) &&
675			((sp->maxsym == 0) ||
676			((val >= (db_addr_t)sp->minsym) &&
677			(val <= (db_addr_t)sp->maxsym)))) {
678		sym = X_db_search_symbol(sp, val, strategy,
679						(db_expr_t *)&newdiff);
680		if (newdiff < diff) {
681		    db_last_symtab = sp;
682		    diff = newdiff;
683		    ret = sym;
684		    if (diff <= db_search_maxoff)
685			break;
686		}
687	    }
688	}
689	if (ret == DB_SYM_NULL && map_for_val != VM_MAP_NULL) {
690		map_for_val = VM_MAP_NULL;
691		goto again;
692	}
693	*offp = diff;
694	return ret;
695}
696
697/*
698 * Find the closest symbol to val, and return its name
699 * and the difference between val and the symbol found.
700 * Also return the filename and linenumber if available.
701 */
702db_sym_t
703db_search_task_symbol_and_line(
704	register db_addr_t	val,
705	__unused db_strategy_t	strategy,
706	db_expr_t		*offp,
707	char			**filenamep,
708	int			*linenump,
709	task_t			task,
710	int			*argsp)
711{
712	db_addr_t diff, newdiff;
713	register int	i;
714	db_symtab_t	*sp;
715	db_sym_t	ret = DB_SYM_NULL, sym;
716	vm_map_t	map_for_val;
717	char 		*func;
718	char		*filename;
719	int		linenum;
720	int		args;
721
722	if (task == TASK_NULL)
723	    task = db_current_task();
724	map_for_val = (task == TASK_NULL)? VM_MAP_NULL: task->map;
725	*filenamep = (char *) 0;
726	*linenump = 0;
727	*argsp = -1;
728    again:
729	filename = (char *) 0;
730	linenum = 0;
731	newdiff = diff = ~0UL;
732	db_last_symtab = 0;
733	for (sp = &db_symtabs[0], i = 0;
734	     i < db_nsymtab;
735	     sp++, i++) {
736	    if ((((vm_map_t)sp->map_pointer == VM_MAP_NULL) ||
737			((vm_map_t)sp->map_pointer == map_for_val)) &&
738			((sp->maxsym == 0) ||
739			((val >= (db_addr_t)sp->minsym) &&
740			(val <= (db_addr_t)sp->maxsym)))) {
741
742			sym = X_db_search_by_addr(sp, val, &filename, &func,
743						  &linenum, (db_expr_t *)&newdiff,
744						  &args);
745			if (sym && newdiff < diff) {
746				db_last_symtab = sp;
747				diff = newdiff;
748				ret = sym;
749				*filenamep = filename;
750				*linenump = linenum;
751				*argsp = args;
752				if (diff <= db_search_maxoff)
753				break;
754			}
755	    }
756	}
757	if (ret == DB_SYM_NULL && map_for_val != VM_MAP_NULL) {
758		map_for_val = VM_MAP_NULL;
759		goto again;
760	}
761	*offp = diff;
762	if (*filenamep)
763		db_shorten_filename(filenamep);
764	return ret;
765}
766
767/*
768 * Return name and value of a symbol
769 */
770void
771db_symbol_values(
772	db_symtab_t	*stab,
773	db_sym_t	sym,
774	const char		**namep,
775	db_expr_t	*valuep)
776{
777	db_expr_t	value;
778	char		*name;
779
780	if (sym == DB_SYM_NULL) {
781		*namep = 0;
782		return;
783	}
784	if (stab == 0)
785		stab = db_last_symtab;
786
787	X_db_symbol_values(stab, sym, &name, &value);
788
789	if (db_symbol_is_ambiguous(name)) {
790		*namep = db_qualify(name, db_last_symtab->name);
791	}else {
792		*namep = name;
793	}
794	if (valuep)
795		*valuep = value;
796}
797
798
799/*
800 * Print a the closest symbol to value
801 *
802 * After matching the symbol according to the given strategy
803 * we print it in the name+offset format, provided the symbol's
804 * value is close enough (eg smaller than db_maxoff).
805 * We also attempt to print [filename:linenum] when applicable
806 * (eg for procedure names).
807 *
808 * If we could not find a reasonable name+offset representation,
809 * then we just print the value in hex.  Small values might get
810 * bogus symbol associations, e.g. 3 might get some absolute
811 * value like _INCLUDE_VERSION or something, therefore we do
812 * not accept symbols whose value is zero (and use plain hex).
813 */
814
815void
816db_task_printsym(
817	db_addr_t	off,
818	db_strategy_t	strategy,
819	task_t		task)
820{
821	db_expr_t	d;
822	char 		*filename;
823	char		*name;
824	db_expr_t	value;
825	int 		linenum;
826	db_sym_t	cursym;
827
828	if (off >= db_maxval || off < db_minval) {
829		db_printf("%#lln", (unsigned long long)off);
830		return;
831	}
832	cursym = db_search_task_symbol(off, strategy, &d, task);
833
834	db_symbol_values(0, cursym, &name, &value);
835	if (name == 0 || d >= db_maxoff || value == 0) {
836		db_printf("%#lln",(unsigned long long) off);
837		return;
838	}
839	db_printf("%s", name);
840	if (d)
841		db_printf("+%llx", (unsigned long long)d);
842	if (strategy == DB_STGY_PROC) {
843		if (db_line_at_pc(cursym, &filename, &linenum, off)) {
844			db_printf(" [%s", filename);
845			if (linenum > 0)
846				db_printf(":%d", linenum);
847			db_printf("]");
848		}
849	}
850}
851
852/*
853 * Return symbol name for a given offset and
854 * change the offset to be relative to this symbol.
855 * Very usefull for xpr, when you want to log offsets
856 * in a user friendly way.
857 */
858
859char null_sym[] = "";
860
861char *
862db_get_sym(db_expr_t *off)
863{
864	db_sym_t	cursym;
865	db_expr_t	value;
866	char		*name;
867	db_addr_t	d;
868
869	cursym = db_search_symbol(*off, DB_STGY_ANY, &d);
870	db_symbol_values(0, cursym, &name, &value);
871	if (name)
872		*off = d;
873	else
874		name = null_sym;
875	return(name);
876}
877
878void
879db_printsym(
880	db_expr_t	off,
881	db_strategy_t	strategy)
882{
883	db_task_printsym(off, strategy, TASK_NULL);
884}
885
886int db_short_filename = 1;
887
888void
889db_shorten_filename(char **filenamep)
890{
891	char *cp, *cp_slash;
892
893	if (! *filenamep)
894		return;
895	for (cp = cp_slash = *filenamep; *cp; cp++) {
896		if (*cp == '/')
897			cp_slash = cp;
898	}
899	if (*cp_slash == '/')
900		*filenamep = cp_slash+1;
901}
902
903int
904db_task_getlinenum(
905	db_expr_t	off,
906	task_t		task)
907{
908	db_addr_t	d;
909	char 		*filename;
910	char		*name;
911	db_expr_t	value;
912	int 		linenum;
913	db_sym_t	cursym;
914	db_strategy_t	strategy = DB_STGY_PROC;
915
916	if (off >= db_maxval || off < db_minval) {
917		db_printf("%#lln", (unsigned long long)off);
918		return(-1);
919	}
920	cursym = db_search_task_symbol(off, strategy, &d, task);
921
922	db_symbol_values(0, cursym, &name, &value);
923	if (name == 0 || d >= db_maxoff || value == 0) {
924		return(-1);
925	}
926	if (db_line_at_pc(cursym, &filename, &linenum, off))
927		return(linenum);
928	else
929		return(-1);
930}
931
932boolean_t
933db_line_at_pc(
934	db_sym_t	sym,
935	char		**filename,
936	int		*linenum,
937	db_expr_t	pc)
938{
939	boolean_t result;
940
941	if (db_last_symtab == 0)
942		return FALSE;
943	if (X_db_line_at_pc( db_last_symtab, sym, filename, linenum, pc)) {
944		if (db_short_filename)
945			db_shorten_filename(filename);
946		result = TRUE;
947	} else
948		result = FALSE;
949	return(result);
950}
951
952int qsort_check = 0;
953
954void
955db_qsort(
956	char	*table,
957	int	nbelts,
958	int	eltsize,
959	int	(*compfun)(char *, char *))
960{
961	if (nbelts <= 0 || eltsize <= 0 || compfun == 0) {
962		printf("qsort: invalid parameters\n");
963		return;
964	}
965	qsort_recur(table, table + nbelts * eltsize, eltsize, compfun);
966
967	if (qsort_check)
968		qsort_checker(table, nbelts, eltsize, compfun);
969}
970
971void
972qsort_swap(
973	register int	*a,
974	register int	*b,
975	register int	size)
976{
977	register int temp;
978	char *aa, *bb;
979	char ctemp;
980
981	for (; size >= (signed)sizeof (int); size -= sizeof (int), a++, b++) {
982		temp = *a;
983		*a = *b;
984		*b = temp;
985	}
986	aa = (char *)a;
987	bb = (char *)b;
988	for (; size > 0; size--, aa++, bb++) {
989		ctemp = *aa;
990		*aa = *bb;
991		*bb = ctemp;
992	}
993}
994
995/* rotate the three elements to the left */
996void
997qsort_rotate(
998	register int	*a,
999	register int	*b,
1000	register int	*c,
1001	register int	size)
1002{
1003	register int temp;
1004	char *aa, *bb, *cc;
1005	char ctemp;
1006
1007	for (; size >= (signed)sizeof(int);
1008			size -= sizeof(int), a++, b++, c++) {
1009		temp = *a;
1010		*a = *c;
1011		*c = *b;
1012		*b = temp;
1013	}
1014	aa = (char *)a;
1015	bb = (char *)b;
1016	cc = (char *)c;
1017	for (; size > 0; size--, aa++, bb++, cc++) {
1018		ctemp = *aa;
1019		*aa = *cc;
1020		*cc = *bb;
1021		*bb = ctemp;
1022	}
1023}
1024
1025void
1026qsort_recur(
1027	char	*left,
1028	char	*right,
1029	int	eltsize,
1030	int	(*compfun)(char *, char *))
1031{
1032	char *i, *j;
1033	char *sameleft, *sameright;
1034
1035    top:
1036	if (left + eltsize - 1 >= right) {
1037		return;
1038	}
1039
1040	/* partition element (reference for "same"ness */
1041	sameleft = left + (((right - left) / eltsize) / 2) * eltsize;
1042	sameright = sameleft;
1043
1044	i = left;
1045	j = right - eltsize;
1046
1047    again:
1048    	while (i < sameleft) {
1049		int comp;
1050
1051		comp = (*compfun)(i, sameleft);
1052		if (comp == 0) {
1053			/*
1054			 * Move to the "same" partition.
1055			 */
1056			/*
1057			 * Shift the left part of the "same" partition to
1058			 * the left, so that "same" elements stay in their
1059			 * original order.
1060			 */
1061			sameleft -= eltsize;
1062			qsort_swap((int *) i, (int *) sameleft, eltsize);
1063		} else if (comp < 0) {
1064			/*
1065			 * Stay in the "left" partition.
1066			 */
1067			i += eltsize;
1068		} else {
1069			/*
1070			 * Should be moved to the "right" partition.
1071			 * Wait until the next loop finds an appropriate
1072			 * place to store this element.
1073			 */
1074			break;
1075		}
1076	}
1077
1078	while (j > sameright) {
1079		int comp;
1080
1081		comp = (*compfun)(sameright, j);
1082		if (comp == 0) {
1083			/*
1084			 * Move to the right of the "same" partition.
1085			 */
1086			sameright += eltsize;
1087			qsort_swap((int *) sameright, (int *) j, eltsize);
1088		} else if (comp > 0) {
1089			/*
1090			 * Move to the "left" partition.
1091			 */
1092			if (i == sameleft) {
1093				/*
1094				 * Unfortunately, the "left" partition
1095				 * has already been fully processed, so
1096				 * we have to shift the "same" partition
1097				 * to the right to free a "left" element.
1098				 * This is done by moving the leftest same
1099				 * to the right of the "same" partition.
1100				 */
1101				sameright += eltsize;
1102				qsort_rotate((int *) sameleft, (int*) sameright,
1103					     (int *) j, eltsize);
1104				sameleft += eltsize;
1105				i = sameleft;
1106			} else {
1107				/*
1108				 * Swap with the "left" partition element
1109				 * waiting to be moved to the "right"
1110				 * partition.
1111				 */
1112				qsort_swap((int *) i, (int *) j, eltsize);
1113				j -= eltsize;
1114				/*
1115				 * Go back to the 1st loop.
1116				 */
1117				i += eltsize;
1118				goto again;
1119			}
1120		} else {
1121			/*
1122			 * Stay in the "right" partition.
1123			 */
1124			j -= eltsize;
1125		}
1126	}
1127
1128	if (i != sameleft) {
1129		/*
1130		 * The second loop completed (the"right" partition is ok),
1131		 * but we have to go back to the first loop, and deal with
1132		 * the element waiting for a place in the "right" partition.
1133		 * Let's shift the "same" zone to the left.
1134		 */
1135		sameleft -= eltsize;
1136		qsort_rotate((int *) sameright, (int *) sameleft, (int *) i,
1137			     eltsize);
1138		sameright -= eltsize;
1139		j = sameright;
1140		/*
1141		 * Go back to 1st loop.
1142		 */
1143		goto again;
1144	}
1145
1146	/*
1147	 * The partitions are correct now. Recur on the smallest side only.
1148	 */
1149	if (sameleft - left >= right - (sameright + eltsize)) {
1150		qsort_recur(sameright + eltsize, right, eltsize, compfun);
1151		/*
1152		 * The "right" partition is now completely sorted.
1153		 * The "same" partition is OK, so...
1154		 * Ignore them, and start the loops again on the
1155		 * "left" partition.
1156		 */
1157		right = sameleft;
1158		goto top;
1159	} else {
1160		qsort_recur(left, sameleft, eltsize, compfun);
1161		/*
1162		 * The "left" partition is now completely sorted.
1163		 * The "same" partition is OK, so ...
1164		 * Ignore them, and start the loops again on the
1165		 * "right" partition.
1166		 */
1167		left = sameright + eltsize;
1168		goto top;
1169	}
1170}
1171
1172void
1173qsort_checker(
1174	char	*table,
1175	int	nbelts,
1176	int	eltsize,
1177	int	(*compfun)(char *, char *))
1178{
1179	char *curr, *prev, *last;
1180
1181	prev = table;
1182	curr = prev + eltsize;
1183	last = table + (nbelts * eltsize);
1184
1185	while (prev < last) {
1186		if ((*compfun)(prev, curr) > 0) {
1187			printf("**** qsort_checker: error between 0x%x and 0x%x!!!\n", prev, curr);
1188			break;
1189		}
1190		prev = curr;
1191		curr += eltsize;
1192	}
1193	printf("qsort_checker: OK\n");
1194}
1195
1196int qsort_search_debug = 0;
1197
1198void
1199db_qsort_limit_search(
1200	char	*target,
1201	char	**start,
1202	char	**db_end,
1203	int	eltsize,
1204	int	(*compfun)(char *, char *))
1205{
1206	register char *left, *right;
1207	char *oleft, *oright, *part;
1208	int nbiter = 0;
1209	int comp;
1210
1211	oleft = left = *start;
1212	oright = right = *db_end;
1213	part = (char *) 0;
1214
1215	while (left < right) {
1216		nbiter++;
1217		part = left + (((right - left) / eltsize) / 2) * eltsize;
1218		comp = (*compfun)(target, part);
1219		if (comp > 0) {
1220			oleft = left;
1221			oright = right;
1222			left = part;
1223			if (left == oleft)
1224				break;
1225			if (qsort_search_debug > 1)
1226				printf(" [ Moved left from 0x%x to 0x%x]\n",
1227				       oleft, left);
1228		} else if (comp < 0) {
1229			oright = right;
1230			oleft = left;
1231			right = part;
1232			if (qsort_search_debug > 1)
1233				printf(" [ Moved right from 0x%x to 0x%x]\n",
1234				       oright, right);
1235		} else {
1236			if (qsort_search_debug > 1)
1237				printf(" [ FOUND! left=0x%x right=0x%x]\n",
1238				       left, right);
1239			for (left = part;
1240			     left > *start && (*compfun)(left, part) == 0;
1241			     left -= eltsize);
1242			for (right = part + eltsize;
1243			     right < *db_end && (*compfun)(right, part) == 0;
1244			     right += eltsize);
1245			oright = right;
1246			oleft = left;
1247			break;
1248		}
1249	}
1250
1251	if (qsort_search_debug)
1252		printf("[ Limited from %x-%x to %x-%x in %d iters ]\n",
1253			  *start, *db_end, oleft, oright, nbiter);
1254	*start = oleft;
1255	*db_end = oright;
1256}
1257
1258void
1259bubble_sort(
1260	char	*table,
1261	int	nbelts,
1262	int	eltsize,
1263	int	(*compfun)(char *, char *))
1264{
1265	boolean_t sorted;
1266	char *b_end;
1267	register char *p;
1268
1269	b_end = table + ((nbelts-1) * eltsize);
1270	do {
1271		sorted = TRUE;
1272		for (p = table; p < b_end; p += eltsize) {
1273			if ((*compfun)(p, p + eltsize) > 0) {
1274				qsort_swap((int *) p, (int *) (p + eltsize),
1275					   eltsize);
1276				sorted = FALSE;
1277			}
1278		}
1279	} while (sorted == FALSE);
1280
1281	if (qsort_check)
1282		qsort_checker(table, nbelts, eltsize, compfun);
1283}
1284
1285vm_offset_t	vm_min_inks_addr = VM_MAX_KERNEL_ADDRESS;
1286
1287void
1288db_install_inks(
1289      vm_offset_t base)
1290{
1291	/* save addr to demarcate kernel/inks boundary (1st time only)  */
1292	if (vm_min_inks_addr == VM_MAX_KERNEL_ADDRESS) {
1293		vm_min_inks_addr = base;
1294		db_qualify_ambiguous_names = TRUE;
1295	}
1296}
1297
1298extern void db_clone_offsetXXX(char *, long);
1299
1300void
1301db_clone_symtabXXX(
1302	char *clonee,			/* which symtab to clone	*/
1303	char *cloner,			/* in-kernel-server name	*/
1304	vm_offset_t base)		/* base address of cloner	*/
1305{
1306	db_symtab_t	*st, *st_src;
1307	char *		memp;
1308	vm_size_t	size;
1309	long		offset;
1310
1311	if (db_nsymtab >= MAXNOSYMTABS) {
1312	    db_printf("db_clone_symtab: Too Many Symbol Tables\n");
1313	    return;
1314	}
1315
1316	db_install_inks(base);
1317
1318	st = &db_symtabs[db_nsymtab];	/* destination symtab		*/
1319	if ((st_src = db_symtab_cloneeXXX(clonee)) == 0) {
1320	    db_printf("db_clone_symtab: clonee (%s) not found\n", clonee);
1321	    return;
1322	}
1323					/* alloc new symbols		*/
1324	size = (vm_size_t)(st_src->end - st_src->private);
1325	memp = (char *)kalloc( round_page(size) );
1326	if (!memp) {
1327	    db_printf("db_clone_symtab: no memory for symtab\n");
1328	    return;
1329	}
1330
1331	*st = *st_src;			/* bulk copy src -> dest	*/
1332	strcpy(st->name, cloner);	/* new name			*/
1333	st->private = memp;		/* copy symbols			*/
1334	bcopy((const char *)st_src->private, st->private, size);
1335	st->start = memp + sizeof(int);	/* fixup pointers to symtab	*/
1336	st->end   = memp + *(int *)memp;
1337	st->map_pointer = 0;		/* no map because kernel-loaded */
1338
1339	/* Offset symbols, leaving strings pointing into st_src		*/
1340	offset	    = base - st_src->minsym;
1341	st->minsym  += offset;
1342	st->maxsym  += offset;
1343	db_clone_offsetXXX(memp, offset);
1344	db_nsymtab++;
1345
1346	db_printf( "[ cloned symbol table for %s: range 0x%x to 0x%x %s]\n",
1347		  st->name, st->minsym, st->maxsym,
1348		  st->sorted ? "(sorted) " : "");
1349	db_maxval = (unsigned int)st->maxsym + db_maxoff;
1350}
1351
1352db_symtab_t *
1353db_symtab_cloneeXXX(
1354      char *clonee)
1355{
1356	db_symtab_t *st, *st_src;
1357
1358	st = &db_symtabs[db_nsymtab];   /* destination symtab */
1359	for (st_src = &db_symtabs[0]; st_src < st; ++st_src)
1360		if (!strcmp(clonee, st_src->name))
1361			break;
1362	return ((st_src < st) ? st_src : 0);
1363}
1364
1365/*
1366 * Switch into symbol-table specific routines
1367 */
1368
1369#if	!defined(__alpha) && !defined(INTEL860)
1370#define DB_NO_COFF
1371#endif
1372
1373#ifndef	DB_NO_AOUT
1374#include <ddb/db_aout.h>
1375#endif
1376
1377#ifndef	DB_NO_COFF
1378#include <ddb/db_coff.h>
1379#endif
1380
1381static void no_init(void)
1382
1383{
1384	db_printf("Non-existent code for ddb init\n");
1385}
1386
1387static boolean_t
1388no_sym_init(__unused char *nstart, __unused char *nend, const char *name,
1389	    __unused char *task_addr)
1390{
1391	db_printf("Non-existent code for init of symtab %s\n", name);
1392	return FALSE;
1393}
1394
1395static db_sym_t
1396no_lookup(__unused db_symtab_t *stab, char *symstr)
1397{
1398	db_printf("Bogus lookup of symbol %s\n", symstr);
1399	return DB_SYM_NULL;
1400}
1401
1402static db_sym_t
1403no_search(__unused db_symtab_t *stab, db_addr_t off,
1404	  __unused db_strategy_t strategy, __unused db_expr_t *diffp)
1405{
1406	db_printf("Bogus search for offset %#llXn", (unsigned long long)off);
1407	return DB_SYM_NULL;
1408}
1409
1410static boolean_t
1411no_line_at_pc(__unused db_symtab_t *stab, __unused db_sym_t sym,
1412	      __unused char **file, __unused int *line, db_expr_t pc)
1413{
1414	db_printf("Bogus search for pc %#llX\n", (unsigned long long)pc);
1415	return FALSE;
1416}
1417
1418static void
1419no_symbol_values(__unused db_sym_t sym, char **namep, db_expr_t *valuep)
1420{
1421	db_printf("Bogus symbol value resolution\n");
1422	if (namep) *namep = NULL;
1423	if (valuep) *valuep = 0;
1424}
1425
1426static db_sym_t
1427no_search_by_addr(__unused db_symtab_t *stab, db_addr_t off,
1428		  __unused char **file, __unused char **func,
1429		  __unused int *line, __unused db_expr_t *diffp,
1430		  __unused int *args)
1431{
1432	db_printf("Bogus search for address %#llX\n", (unsigned long long)off);
1433	return DB_SYM_NULL;
1434}
1435
1436int
1437no_print_completion(__unused db_symtab_t *stab, __unused char *symstr)
1438{
1439	db_printf("Bogus print completion: not supported\n");
1440	return 0;
1441}
1442
1443int
1444no_lookup_incomplete(__unused db_symtab_t *stab,
1445		     __unused char *symstr, __unused char **name,
1446		     __unused int *len, __unused int *toadd)
1447{
1448	db_printf("Bogus lookup incomplete: not supported\n");
1449	return 0;
1450}
1451
1452#define NONE	\
1453	{	\
1454		.init = no_init, \
1455		.sym_init = no_sym_init, \
1456		.lookup = no_lookup, \
1457		.search_symbol = no_search, \
1458		.line_at_pc = no_line_at_pc, \
1459		.symbol_values = no_symbol_values, \
1460		.search_by_addr = no_search_by_addr, \
1461		.print_completion = no_print_completion, \
1462		.lookup_incomplete = no_lookup_incomplete, \
1463	}
1464
1465struct db_sym_switch x_db[] = {
1466
1467	/* BSD a.out format (really, sdb/dbx(1) symtabs) */
1468#ifdef	DB_NO_AOUT
1469	NONE,
1470#else	/* DB_NO_AOUT */
1471	{
1472		.init = aout_db_init,
1473		.sym_init = aout_db_sym_init,
1474		.lookup = aout_db_lookup,
1475		.search_symbol = aout_db_search_symbol,
1476		.line_at_pc = aout_db_line_at_pc,
1477		.symbol_values = aout_db_symbol_values,
1478		.search_by_addr = aout_db_search_by_addr,
1479		.print_completion = aout_db_print_completion,
1480		.lookup_incomplete = aout_db_lookup_incomplete,
1481	},
1482#endif	/* DB_NO_AOUT */
1483
1484#ifdef	DB_NO_COFF
1485	NONE,
1486#else	/* DB_NO_COFF */
1487	{
1488		.init = coff_db_init,
1489		.sym_init = coff_db_sym_init,
1490		.lookup = coff_db_lookup,
1491		.search_symbol = coff_db_search_symbol,
1492		.line_at_pc = coff_db_line_at_pc,
1493		.symbol_values = coff_db_symbol_values,
1494		.search_by_addr = coff_db_search_by_addr,
1495		.print_completion = coff_db_print_completion,
1496		.lookup_incomplete = coff_db_lookup_incomplete,
1497	},
1498#endif	/* DB_NO_COFF */
1499
1500	/* Machdep, not inited here */
1501	NONE
1502};
1503