dflow.c

C程序漏洞检查！

/***** uno: dflow.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                */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include "prnttree.h"
#include "token.h"
#include "gram.h"
#include "symtab.h"

extern int	Verbose, uno, vis;
extern char	*want, *progname;

       void	bugger(char *, treenode *, int);
extern char	*emalloc(unsigned int);
extern char	*x_stmnt(treenode *);
extern int	find_symbol(scopetab_t *, symentry_t *);
extern symentry_t *new_symentry(void);

static char SaveMe[1024];
static int  is_a_prototype = 1;

char	*Fct_name;
int	RealDecls;
int	watch;	/* debugging */
DuG	*d_g;

char *
doit(leafnode *leaf, int how)
{	scopetab_t *z;
	static char bstr[1024];
	static char lstr[1024];

	if (!leaf) return (char *) 0;

	if (leaf->syment && leaf->syment->nes)
		z = leaf->syment->nes;
	else
		z = (scopetab_t *) 0;

	strcpy(lstr, "");
	switch (how) {
	case 2:	sprintf(bstr, "%d:", leaf->hdr.line);
		strcat(lstr, bstr);	/* fall thru */
	case 0:	sprintf(bstr, "%s::", z?z->owner:"-");
		strcat(lstr, bstr);	/* fall thru */
	case 1:	sprintf(bstr, "%s%s", nmestr(leaf->data.sval), (!how)?" ":"");
		strcat(lstr, bstr);
	}
	return &lstr[0];
}

DuG *
dep_node(SymList *a, int imark)
{	DuG *g;

	for (g = d_g; g; g = g->nxt)
		if (g->sm == a->sm)
		{	g->marks |= imark;
			goto done;
		}

	g = (DuG *) emalloc(sizeof(DuG));

	if (!a->sm) printf("%s: dep_node without symbol\n", progname);

	g->sm = a->sm;
	g->marks = imark;
	g->rdcls |= RealDecls;
	g->d_e = (DuGP *) 0;
	g->nxt = d_g;
	d_g = g;
done:
	return g;
}

int
dep_edge(DuG *a, DuG *b, int dist)
{	DuGP *e;

	if (a->sm == b->sm)
		return 0;		/* self-loop */

	for (e = a->d_e; e; e = e->nxt)
	{	if (e->ptr == b)
			return 0;	/* already there */
	}

	e = (DuGP *) emalloc(sizeof(DuGP));
	e->ptr = b;
	e->dist = dist;
	e->nxt = a->d_e;
	a->d_e = e;

	return 1;
}

void
dep_graph(DefUse *d)
{	SymList *s, *t;
	DuG *a, *b;

	if (!d || uno) return;

	if (!d->def)
	for (t = d->use; t; t = t->nxt)
		dep_node(t, USE);

	for (s = d->def; s; s = s->nxt)
	{	a = dep_node(s, DEF);
		for (t = d->use; t; t = t->nxt)
		{	b = dep_node(t, USE);
			if (s->sm != t->sm)
				dep_edge(a, b, 1);
		}
	}
}

void
dump_defuse(DefUse *d, FILE *fp)
{	SymList *s;
	ArList *a;

	if (!d) return;

	if (d->def)
	{	fprintf(fp, "[D: ");
		for (s = d->def; s; s = s->nxt)
			fprintf(fp, "%s ", s->sm->nme->str);
		fprintf(fp, "] ");
	}
	if (d->use)
	{	fprintf(fp, "[U: ");
		for (s = d->use; s; s = s->nxt)
			fprintf(fp, "%s ", s->sm->nme->str);
		fprintf(fp, "] ");
	}
	if (d->other)
	{	fprintf(fp, "[O: ");
		for (s = d->other; s; s = s->nxt)
		{	fprintf(fp, "%s=", s->sm->nme->str);
			if (s->mark & DEF)	fprintf(fp, "D");
			if (s->mark & USE)	fprintf(fp, "U");
			if (s->mark & FCALL)	fprintf(fp, "F");
			if (s->mark & (REF0|REF1)) fprintf(fp, "r");
			if (s->mark & REF2)	fprintf(fp, "R");
			if (s->mark & DEREF)	fprintf(fp, "*");
			if (s->mark & ALIAS)	fprintf(fp, "&");
			if (s->mark & ARRAY_DECL)	fprintf(fp, "A");
			if (s->mark & HIDE)	fprintf(fp, "H");
			if (s->mark & DECL)	fprintf(fp, "T");

			if (s->mark & USEafterdef)	fprintf(fp, "Ua");
			if (s->mark & USEbeforedef)	fprintf(fp, "Ub");
			if (s->mark & PARAM)	fprintf(fp, "P");

		/*	fprintf(fp, " <%d>", s->sm->decl_level);	*/
			fprintf(fp, " ");
		}
		fprintf(fp, "] ");
	}

	if (d->aio && 0)
		for (a = d->aio; a; a = a->nxt)
			fprintf(fp, "ar=%s ", x_stmnt(a->tn));
}

static int
same_defuse(DefUse *a, DefUse *b)
{	SymList *s, *t;

	if (!a && !b)
		return 1;
	if (!a || !b)
		return 0;

	for (s = a->def, t = b->def; s && t; s = s->nxt, t = t->nxt)
		if (s->sm != t->sm)
			return 0;
	if (s || t)
		return 0;
	for (s = a->use, t = b->use; s && t; s = s->nxt, t = t->nxt)
		if (s->sm != t->sm)
			return 0;
	if (s || t)
		return 0;

	for (s = a->other, t = b->other; s && t; s = s->nxt, t = t->nxt)
		if (s->sm != t->sm
		||  s->mark != t->mark)
			return 0;

	if (s || t)
		return 0;
	return 1;
}

void
attach_defuse(treenode *n, char *t, DefUse *d)
{
	if (!d || !n) return;

	if (d->def || d->use)
		dep_graph(d);	/* update the graph */

	if (n->hdr.defuse)
	{	if (n->hdr.defuse != d
		&&  !same_defuse(d, n->hdr.defuse))
		{	printf("%s: %s:%d attach_defuse conflict %s %s\n",
				progname, n->hdr.fnm, n->hdr.line,
#ifdef DEFTYP
				n->hdr.deftyp,
#else
				"",
#endif
				t);
			printf("OLD:\n");
			dump_defuse(n->hdr.defuse, stdout);
			printf("\nNEW:\n");
			dump_defuse(d, stdout);
			printf("\n");
		}
	} else
	{	n->hdr.defuse = d;
#ifdef DEFTYP
		n->hdr.deftyp = t;
#endif
	}
}

static SymList *freesyml;
static SymList *allsym;

void
rel_all(SymList *s)
{
	if (!s) return;

	rel_all(s->all);
	s->all = freesyml;
	freesyml = s;
}

void
dflow_reset(void)
{
	rel_all(allsym);
	allsym = (SymList *) 0;
}

SymList *
symadd(symentry_t *sm, int mark)
{	SymList *sl;

	if (freesyml)
	{	sl = freesyml;
		freesyml = freesyml->all;
		memset(sl, 0, sizeof(SymList));
	} else
		sl = (SymList *) emalloc(sizeof(SymList));

	sl->nxt = (SymList *) 0;
	sl->mark = mark;
	sl->sm  = sm;

	sl->all = allsym;
	allsym = sl;

	return sl;
}

static ArList *freelar;

static ArList *
get_arlist(void)
{	ArList *ns;

	if (freelar)
	{	ns = freelar;
		freelar = ns->nxt;
		memset(ns, 0, sizeof(ArList));
	} else
		ns = (ArList *) emalloc(sizeof(ArList));
	return ns;
}

static ArList *
merge_aio(ArList *a1, ArList *a2)
{	ArList *s, *t, *ns;
	ArList *add_to_a1 = (ArList *) 0;
	ArList *last_in   = (ArList *) 0;

	if (!a1) return a2;
	if (!a2) return a1;

	for (t = a2; t; t = t->nxt)
	{	for (s = a1; s; s = s->nxt)
			if (s->tn == t->tn)
				break;

		if (!s) /* add t */
		{	ns = get_arlist();
			ns->tn = t->tn;
			if (!last_in)	/* preserve relative order */
				add_to_a1 = last_in = ns;
			else
			{	last_in->nxt = ns;
				last_in = ns;
	}	}	}

	if (!last_in)
		return a1;
	last_in->nxt = a1;
	a1 = add_to_a1;
	return a1;
}

static SymList *
merge_syms(SymList *s1, SymList *s2)
{	SymList *s, *t, *ns;
	SymList *add_to_s1 = (SymList *) 0;
	SymList *last_in   = (SymList *) 0;

	/* static int mcnt=1; */

	if (!s1) return s2;
	if (!s2) return s1;

	for (t = s2; t; t = t->nxt)
	{	for (s = s1; s; s = s->nxt)
			if (s->sm == t->sm
			&&  s->mark == t->mark)
				break;

		if (!s) /* add t */
		{	ns = symadd(t->sm, t->mark);
			/* preserve relative order */
			if (!last_in)
				add_to_s1 = last_in = ns;
			else
			{	last_in->nxt = ns;
				last_in = ns;
			}
	}	}

	if (!last_in)
		return s1;
	last_in->nxt = s1;
	s1 = add_to_s1;
	return s1;
}

static DefUse *
merge_lists(DefUse *d1, DefUse *d2)
{	DefUse *nd;

	if (!d1) return d2;
	if (!d2) return d1;

	nd = (DefUse *) emalloc(sizeof(DefUse));
	if (!uno)
	{	nd->def   = merge_syms(d1->def, d2->def);
		nd->use   = merge_syms(d1->use, d2->use);
	}
	nd->other = merge_syms(d1->other, d2->other);
	nd->aio   = merge_aio(d1->aio, d2->aio);

	return nd;
}

static int
def_and_use(int tok)
{
	switch (tok) {
	case PLUS_EQ:
	case MINUS_EQ:
	case STAR_EQ:
	case DIV_EQ:
	case MOD_EQ:
	case B_NOT_EQ:
	case B_AND_EQ:
	case B_OR_EQ:
	case B_XOR_EQ:
	case L_SHIFT_EQ:
	case R_SHIFT_EQ:
		return 1;
	}
	return 0;
}

static char ref1_pref[1024];

static char *
set_u(struct symentry *x, char *nu)
{	char *u;

	if (!Fct_name) goto isglob;

	if (!x)
	{	u = (char *) emalloc(strlen(nu)+strlen(Fct_name)+1-1);
		sprintf(u, "%s%s", Fct_name, &nu[1]);
	} else if (x->decl_level == 0)
	{	u = (char *) emalloc(strlen(nu)+strlen("fct")+1-1);
		sprintf(u, "%s%s", "fct", &nu[1]);
	} else if (x->decl_level == 3)	/* is local */
	{	u = (char *) emalloc(strlen(nu)+strlen(Fct_name)+1-1);
		sprintf(u, "%s%s", Fct_name, &nu[1]);
	} else	/* extern 1 or global 2 */
	{
isglob:		u = (char *) emalloc(strlen(nu)+strlen("glob")+1-1);
		sprintf(u, "%s%s", "glob", &nu[1]);
	}
	return u;
}

typedef struct Fbase {
	char *nm;
	int   ln;
	struct Fbase *fcalls;
	struct Fbase *nxt;
} Fbase;

Fbase *fbase;

void
set_fbase(int ln, char *s)
{	Fbase *f;

	fbase = (Fbase *) 0;

	f = (Fbase *) emalloc(sizeof(Fbase));
	f->nm = (char *) emalloc(strlen(s)+1);
	strcpy(f->nm, s);
	f->ln = ln;
	f->fcalls = (Fbase *) 0;
	f->nxt = fbase;
	fbase = f;
}

static void
add_fbase(int ln, char *s)
{	Fbase *f, *g;

	if (!vis) return;

	if (!fbase)
		set_fbase(0, want);

	f = (Fbase *) emalloc(sizeof(Fbase));
	f->nm = (char *) emalloc(strlen(s)+1);
	strcpy(f->nm, s);
	f->ln = ln;
	f->nxt = f->fcalls = (Fbase *) 0;

	for (g = fbase->fcalls; g; g = g->fcalls)
		if (strcmp(g->nm, s) == 0)	/* follows a match */
		{	f->fcalls = g->fcalls;
			g->fcalls = f;
			return;
		}

	f->fcalls = fbase->fcalls;	/* or at the front */
	fbase->fcalls = f;
}

void
storefname(treenode *child)
{
	strcpy(SaveMe, "");
	bugger(SaveMe, child->lnode, 1);
	add_fbase(child->hdr.line, SaveMe);
}

void
dflow_mark(FILE *fd, int mark)
{	int i;

	for (i = 1; i <= ANY; i *= 2)
		switch (mark&i) {
		case   DEF: fprintf(fd, "DEF "); break;
		case FCALL: fprintf(fd, "FCALL "); break;
		case   USE: fprintf(fd, "USE "); break;
		case  REF0: fprintf(fd, "REF0 "); break;
		case  REF1: fprintf(fd, "REF1 "); break;
		case  REF2: fprintf(fd, "REF2 "); break;
		case DEREF: fprintf(fd, "DEREF "); break;
		case ALIAS: fprintf(fd, "ALIAS "); break;
		case ARRAY_DECL: fprintf(fd, "ARRAY_DECL "); break;
		case HIDE: fprintf(fd, "HIDE "); break;
		case DECL: fprintf(fd, "DECL "); break;
		case USEafterdef: fprintf(fd, "USEafterdef "); break;
		case USEbeforedef: fprintf(fd, "USEbeforedef "); break;
		case UNO_CONST: fprintf(fd, "CONST "); break;
		case PARAM: fprintf(fd, "PARAM "); break;
		}
}

static void
add_aio(DefUse *d, treenode *n)
{	ArList *nio;

	if (!d)
	{	if (0
		&& strncmp(n->hdr.fnm, "/usr/include", strlen("/usr/include")) != 0)
			printf("uno: %s:%d aio without d to attach to\n",
			n->hdr.fnm, n->hdr.line);
		return;
	}

	for (nio = d->aio; nio; nio = nio->nxt)
		if (nio->tn == n)