symtab.c

C程序漏洞检查

/***** uno: symtab.c *****/

/* Copyright (c) 2000-2003 by Lucent Technologies - Bell Laboratories     */
/* All Rights Reserved.  This software is for educational purposes only.  */
/* Permission is given to distribute this code provided that this intro-  */
/* ductory message is not removed and no monies are exchanged.            */
/* No guarantee is expressed or implied by the distribution of this code. */
/* Software written by Gerard J. Holzmann based on the public domain      */
/* ANSI-C parser Ctree Version 0.14 from Shaun Flisakowski                */

/* Original version by Shaun Flisakowski, Jul 15, 1997 */

#include  <stdio.h>
#include  <stdlib.h>
#include  <string.h>
#include  <assert.h>
#include  "utype.h"
#include  "symtab.h"
#include  "nmetab.h"
#include  "prnttree.h"

#define DBG	0	/* debugging */

static int	child_insert(scopetab_t *mom, scopetab_t *kid);
static symentry_t *mk_g(str_t *sym, treenode *tn, int knd);
static void	po_deltabs(scopetab_t *that);
       void	show_hashtab(hashtab_t *that, int, FILE *fp);
static void	show_scopetab(scopetab_t *that, int, FILE *fp);
static void	show_symentry(symentry_t *that, int, FILE *fp);

extern char	*current_filename(void);
extern int	current_linenumber(void);
extern void	*sbrk(unsigned long);
extern int	uno_ignore(symentry_t *);
extern char	*x_stmnt(treenode *);

extern void	x_frag(treenode *, FILE *);
extern int	Verbose;
extern char	*progname;

#define CHUNK	(1<<20)			/* allocate memory in 1 Mb increments */
#define ALGN	sizeof(double)		/* secure word alignment */

static long memcnt = 0L;
static long memwaste = 0L;

void efree(void *m) { return; }

static long left = 0;
static char *have = (char *) 0;
static symentry_t *fses = (symentry_t *) 0;

static hashtab_t  *freehtab = (hashtab_t *) 0;
static scopetab_t *freestab = (scopetab_t *) 0;
static symtab_t   *freesymt = (symtab_t *) 0;

int vis;

static char *
not_malloc(uint n)
{	char *tmp;

	if (left < n)
	{	int grow = (n < CHUNK) ? CHUNK : n;
		have = (char *) malloc(grow);
		if (!have)
		{	fprintf(stderr, "%s: out of memory\n", progname);
			exit(1);
		}
		memset(have, 0, grow);
		left = grow;
	}
	tmp = have;
	have += n;
	left -= n;

	return tmp;
}

void *
emalloc(uint m)
{	char *tmp;
	long n = m + ALGN;	/* for possible alignment */

	assert(m != 0);

	tmp = not_malloc(n);

	if (((uint) tmp)&(ALGN-1))
	{	tmp += (long) (ALGN  - (((uint) tmp)&(ALGN-1)));
		memwaste += ALGN;
	} else
	{	left += ALGN;	/* return the extra bytes */
		have -= ALGN;
	}

	memcnt += m;

	return (void *) tmp;
}

void
memstats(void)
{
	printf("uno:local: %6d memory used", memcnt);
	if (memwaste && memcnt)
	printf(", %d%% memory wasted for alignments\n", 100*memwaste/memcnt);
}

static void
dotabs(int tabs, FILE *fp)
{	int j;

	for (j = 0; j < tabs; j++)
		fprintf(fp, "|\t");
}

static void
print_frag(treenode *root, FILE *fd)
{
	fprintf(fd, "\t[");	/* source text */
	if (root && (root->hdr.which != FOR_T))
		fprintf(fd, "%s", x_stmnt(root));
	else
		fprintf(fd, "fct");
	fprintf(fd, "]");
}

static void
show_symentry(symentry_t *that, int tabs, FILE *fp)
{
	dotabs(tabs+1, fp);
	fprintf(fp, "%s", that->nme->str);
	print_frag(that->node, fp);
	if (that->node
	&&  that->node->hdr.type != TN_FUNC_DEF
	&& !that->used)
		fprintf(fp, " unused");

	fprintf(fp, "\n");
}

symentry_t *
new_symentry(void)
{	symentry_t *that;

	if (fses)
	{	that = fses;
		fses = fses->next;
		memset(that, 0, sizeof(symentry_t));
	} else
		that = (symentry_t *) emalloc(sizeof(symentry_t));

	that->ln = current_linenumber();	/* gjh */
	that->fn = current_filename();		/* gjh */
	return that;
}

static symentry_t*
mk_g(str_t *sym, treenode *tn, int knd)	/* mk_generic */
{	symentry_t *that;

	that = new_symentry();

	that->kind = knd;
	that->nme  = sym;
	that->node = tn;
	that->nes = (scopetab_t *) 0;
	that->decl_level = 0;
	that->container = NULL;

	return that;
}

symentry_t *
mk_typedef(str_t *sym, treenode *tn) { return mk_g(sym,tn,TYPEDEF_ENTRY); }

symentry_t *
mk_funcdef(str_t *sym, treenode *tn) { return mk_g(sym,tn,FUNCDEF_ENTRY); }

symentry_t *
mk_vardecl(str_t *sym, treenode *tn) { return mk_g(sym,tn,VARDECL_ENTRY); }

symentry_t *
mk_enum_const(str_t *sym, treenode *tn) { return mk_g(sym,tn,ENUM_CONST_ENTRY); }

symentry_t *
mk_label(str_t *sym, treenode *tn) { return mk_g(sym,tn,LABEL_ENTRY); }

symentry_t *
mk_tag(str_t *sym, treenode *tn) { return mk_g(sym,tn,TAG_ENTRY); }

symentry_t *
mk_component(str_t *sym, treenode *tn, treenode *container)
{	symentry_t *entry = mk_g(sym,tn,COMP_ENTRY);

	entry->container = container;
	return entry;
}

int is_typedef(symentry_t *that)    { return that && (that->kind == TYPEDEF_ENTRY); }
int is_enum_const(symentry_t *that) { return that && (that->kind == ENUM_CONST_ENTRY); }

static void
free_symlist(symentry_t *list)
{
	if (list)
	{	free_symlist(list->next);
		memset(list, 0, sizeof(symentry_t *));
		list->next = fses;
		fses = list;
	}
}

static void
free_hashtab(hashtab_t *that)
{	int j;

	if (that)
	{	for (j=0; j < that->tsize; j++)
		{	free_symlist(that->tab[j]);
			that->tab[j] = (symentry_t *) 0;
		}
		that->nxt = freehtab;
		freehtab = that;
	}
}

hashtab_t *
new_hashtab(void)
{	hashtab_t *that;

	if (freehtab)
	{	that = freehtab;
		freehtab = that->nxt;
		if (that->tsize != INIT_HASHTAB_SIZE)
		{	fprintf(stderr, "cannot happen nht\n");
			exit(1);
		}
		memset(that->tab, 0, sizeof(symentry_t*) * that->tsize);
	} else
	{	that = (hashtab_t *) emalloc(sizeof(hashtab_t));
		that->tsize = INIT_HASHTAB_SIZE;
		that->tab = (symentry_t **) emalloc( sizeof(symentry_t*) * that->tsize );
	}
	that->nent = 0;

	return that;
}

symentry_t *
hashtab_lookup(hashtab_t *that, str_t *nme)
{	symentry_t *curr;
	int j;
  
	if (!nme || !that) return NULL;

	j = nme->hash % that->tsize;
	for (curr = that->tab[j]; curr; curr = curr->next)
		if (curr->nme
		&&  strcmp(curr->nme->str, nme->str) == 0) 
			return curr;

	return NULL;
}

symentry_t*
hashtab_insert(hashtab_t *that, symentry_t *entry)
{	int j;
	symentry_t *ret;

	if ((ret = hashtab_lookup(that, entry->nme)))
	{
		return ret;
	}

	if (0) printf("insert in hashtab %u -- %s\n",
		that, entry->nme->str);

	j = entry->nme->hash % that->tsize;
	entry->next = that->tab[j];
	that->tab[j] = entry;

	return entry;
}

void
show_hashtab(hashtab_t *that, int tabs, FILE *fp)
{	symentry_t *t;
	int j;

	for (j = 0; j < that->tsize; j++)
	for (t = that->tab[j]; t; t = t->next)
		show_symentry(t, tabs, fp);
}

typedef struct Scoop Scoop;
struct Scoop {
	int		n;
	scopetab_t	**g;
	Scoop		*nxt;
};

static Scoop *scoop, *freescoop;

scopetab_t **
getscoop(int n)
{	Scoop *s, *prevs = (Scoop *) 0;
	scopetab_t **g = (scopetab_t **) 0;

	for (s = scoop; s; prevs = s, s = s->nxt)
		if (s->n == n)
		{	g = s->g;
			if (!prevs)
				scoop = s->nxt;
			else
				prevs->nxt = s->nxt;
				
			s->n = 0;
			s->g = (scopetab_t **) 0;
			s->nxt = freescoop;
			freescoop = s;
			break;
		}
	if (!g)
		g = (scopetab_t **) emalloc( sizeof(scopetab_t*) * n );

	return g;
}

static void
free_scopetab(scopetab_t *that)
{	Scoop *s;

	if (that)
	{	free_hashtab(that->htab);

		if (freescoop)
		{	s = freescoop;
			freescoop = s->nxt;
		} else
			s = (Scoop *) emalloc(sizeof(Scoop));

		s->n = that->size;
		s->g = that->children;
		s->nxt = scoop;
		scoop = s;

		that->parent = freestab;
		freestab = that;
	}
}

scopetab_t*
new_scopetab(scopetab_t *mom)
{	scopetab_t *that;

	if (freestab)
	{	that = freestab;
		freestab = that->parent;
		memset(that, 0, sizeof(scopetab_t));
	} else
		that = (scopetab_t *) emalloc(sizeof(scopetab_t));

	if (0)
	printf("new scope tab %u, level %d\n", that, mom?mom->level+1:EXTERN_SCOPE);

	that->size = INIT_CHILD_SIZE;

	that->children = getscoop(that->size);

	that->parent = mom;
	if (mom)
		that->level = mom->level + 1;
	else
		that->level = EXTERN_SCOPE;

	return that;
}

symentry_t*
scopetab_find(scopetab_t *that, str_t *nme)
{	symentry_t *ret = NULL, *oret = NULL;
	int j;
	extern int structfieldflag;

if (DBG) {	printf("scopetab_find %s -- hashtab: <%u> -- ", nme->str, that?that->htab:0);
		printf("scopetab: %u, level: %d  nsyms: %d  nchild: %d -- structfield: %s -- owner_t: %d\n",
			that, that?that->level:-1, that?that->nsyms:-1, that?that->nchild:-1,
			structfieldflag?"YES":"no",
			that?that->owner_t:-1);
	}

	if (that)
	{	if (that->visited)
			return NULL;
		that->visited = 1;	/* prevent circularity */

		if (that->htab)
		{	if (!structfieldflag
			||   (that->level >= 3
			&&    that->owner_t == TN_OBJ_DEF))	/* Struct/Union, must have owner_t before ref */
			{	ret = hashtab_lookup(that->htab, nme);
			}
		}

		if (!ret && structfieldflag)	/* gjh */
		for (j = 0; j < that->nchild; j++)
		{	ret = scopetab_find(that->children[j], nme);
			if (ret)
			{	ret->used = 1;	/* set for all matches, return last */
				oret = ret;
if (DBG)			printf("Candidate Match %s: %u - %s:%d nes: %s\n",
					nme->str, ret, ret->fn, ret->ln,
					ret->nes && ret->nes->owner ? ret->nes->owner : "no owner");
		}	}
		if (!ret && oret) ret = oret;

		if (!ret) ret = scopetab_find(that->parent,nme);	/* goes up one level */

		that->visited = 0;
	}
	if (ret && structfieldflag) ret->used = 1;

	return ret;
}

symentry_t *
scopetab_insert(scopetab_t *that, symentry_t *entry)
{
#if DBG
	int i;
	printf("	Inserting '%s' at level %d -- owner %s (%d) -- nchild %d\n",
		entry->nme->str, that->level, that->owner, that->owner_t, that->nchild);
	printf("	scopetab: %u; ", that);
	for (i = 0; i < that->nchild; i++)