shithub: riscv

Download patch

ref: a2f7d03d4ef7f606680894693f52150a8eb1ac28
parent: 2bdd2663dbea21a0718b718965a1db75dbf2fdb4
author: cinap_lenrek <[email protected]>
date: Wed Jul 23 11:28:37 EDT 2014 

rc: fix slow Xqdol(), avoid recursion in conclist(), estrdup(), avoid copying

Xqdol() used to take quadratic time because of strcat(),
the code isnt really needed as list2str() aready does the
same thing in linear time without the strcat().

add estrdup() which uses emalloc() so allocation error are
catched.

move strdups() of name from callers into newvar().

avoid recursion of conclist(), and avoid copying of word
strings by providing Newword() function which doesnt copy
the word string.


--- a/sys/src/cmd/rc/code.c
+++ b/sys/src/cmd/rc/code.c
@@ -56,7 +56,7 @@
 cleanhere(char *f)
 {
 	emitf(Xdelhere);
-	emits(strdup(f));
+	emits(estrdup(f));
 }
 
 char*
@@ -258,7 +258,7 @@
 		else{
 			emitf(Xmark);
 			emitf(Xword);
-			emits(strdup("*"));
+			emits(estrdup("*"));
 			emitf(Xdol);
 		}
 		emitf(Xmark);		/* dummy value for Xlocal */
@@ -275,7 +275,7 @@
 		break;
 	case WORD:
 		emitf(Xword);
-		emits(strdup(t->str));
+		emits(estrdup(t->str));
 		break;
 	case DUP:
 		if(t->rtype==DUPFD){
--- a/sys/src/cmd/rc/exec.c
+++ b/sys/src/cmd/rc/exec.c
@@ -28,23 +28,33 @@
 }
 
 word*
-newword(char *wd, word *next)
+Newword(char *wd, word *next)
 {
 	word *p = new(word);
-	p->word = strdup(wd);
+	p->word = wd;
 	p->next = next;
 	return p;
 }
-
 void
-pushword(char *wd)
+Pushword(char *wd)
 {
 	if(runq->argv==0)
 		panic("pushword but no argv!", 0);
-	runq->argv->words = newword(wd, runq->argv->words);
+	runq->argv->words = Newword(wd, runq->argv->words);
 }
 
+word*
+newword(char *wd, word *next)
+{
+	return Newword(estrdup(wd), next);
+}
 void
+pushword(char *wd)
+{
+	Pushword(estrdup(wd));
+}
+
+void
 popword(void)
 {
 	word *p;
@@ -113,7 +123,7 @@
 newvar(char *name, var *next)
 {
 	var *v = new(var);
-	v->name = name;
+	v->name = estrdup(name);
 	v->val = 0;
 	v->fn = 0;
 	v->changed = 0;
@@ -174,7 +184,7 @@
 	start(bootstrap, 1, (var *)0);
 	/* prime bootstrap argv */
 	pushlist();
-	argv0 = strdup(argv[0]);
+	argv0 = estrdup(argv[0]);
 	for(i = argc-1;i!=0;--i) pushword(argv[i]);
 	for(;;){
 		if(flag['r'])
@@ -304,7 +314,7 @@
 			--runq->pc;
 			starval = vlook("*")->val;
 			start(trapreq->fn, trapreq->pc, (struct var *)0);
-			runq->local = newvar(strdup("*"), runq->local);
+			runq->local = newvar("*", runq->local);
 			runq->local->val = copywords(starval, (struct word *)0);
 			runq->local->changed = 1;
 			runq->redir = runq->startredir = 0;
@@ -548,16 +558,21 @@
 word*
 conclist(word *lp, word *rp, word *tail)
 {
-	char *buf;
-	word *v;
-	if(lp->next || rp->next)
-		tail = conclist(lp->next==0? lp: lp->next,
-			rp->next==0? rp: rp->next, tail);
-	buf = emalloc(strlen(lp->word)+strlen((char *)rp->word)+1);
-	strcpy(buf, lp->word);
-	strcat(buf, rp->word);
-	v = newword(buf, tail);
-	efree(buf);
+	word *v, *p, **end;
+	int ln, rn;
+
+	for(end = &v;;){
+		ln = strlen(lp->word), rn = strlen(rp->word);
+		p = Newword(emalloc(ln+rn+1), (word *)0);
+		Memcpy(p->word, lp->word, ln);
+		Memcpy(p->word+ln, rp->word, rn+1);
+		*end = p, end = &p->next;
+		if(lp->next == 0 && rp->next == 0)
+			break;
+		if(lp->next) lp = lp->next;
+		if(rp->next) rp = rp->next;
+	}
+	*end = tail;
 	return v;
 }
 
@@ -647,9 +662,8 @@
 void
 Xqdol(void)
 {
-	word *a, *p;
 	char *s;
-	int n;
+	word *a;
 	if(count(runq->argv->words)!=1){
 		Xerror1("variable name not singleton!");
 		return;
@@ -658,24 +672,7 @@
 	deglob(s);
 	a = vlook(s)->val;
 	poplist();
-	n = count(a);
-	if(n==0){
-		pushword("");
-		return;
-	}
-	for(p = a;p;p = p->next) n+=strlen(p->word);
-	s = emalloc(n);
-	if(a){
-		strcpy(s, a->word);
-		for(p = a->next;p;p = p->next){
-			strcat(s, " ");
-			strcat(s, p->word);
-		}
-	}
-	else
-		s[0]='\0';
-	pushword(s);
-	efree(s);
+	Pushword(list2str(a));
 }
 
 word*
@@ -780,7 +777,7 @@
 		return;
 	}
 	deglob(runq->argv->words->word);
-	runq->local = newvar(strdup(runq->argv->words->word), runq->local);
+	runq->local = newvar(runq->argv->words->word, runq->local);
 	poplist();
 	globlist();
 	runq->local->val = runq->argv->words;
--- a/sys/src/cmd/rc/haventfork.c
+++ b/sys/src/cmd/rc/haventfork.c
@@ -14,7 +14,7 @@
 	word *p;
 
 	p = vlook("*")->val;
-	argv = malloc((count(p)+6)*sizeof(char*));
+	argv = emalloc((count(p)+6)*sizeof(char*));
 	argc = 0;
 	argv[argc++] = argv0;
 	if(flag['e'])
--- a/sys/src/cmd/rc/here.c
+++ b/sys/src/cmd/rc/here.c
@@ -34,7 +34,7 @@
 	h->tag = tag;
 	hexnum(&tmp[9], getpid());
 	hexnum(&tmp[14], ser++);
-	h->name = strdup(tmp);
+	h->name = estrdup(tmp);
 	return token(tmp, WORD);
 }
 /*
--- a/sys/src/cmd/rc/rc.h
+++ b/sys/src/cmd/rc/rc.h
@@ -103,6 +103,7 @@
 void *emalloc(long);
 void *erealloc(void *, long);
 void efree(void *);
+char *estrdup(char*);
 
 #define	NOFILE	128		/* should come from <param.h> */
 
--- a/sys/src/cmd/rc/simple.c
+++ b/sys/src/cmd/rc/simple.c
@@ -131,7 +131,7 @@
 	runq->argv->words = 0;
 	poplist();
 	start(func->fn, func->pc, runq->local);
-	runq->local = newvar(strdup("*"), runq->local);
+	runq->local = newvar("*", runq->local);
 	runq->local->val = starval;
 	runq->local->changed = 1;
 }
@@ -172,7 +172,7 @@
 				dir = smprint("%s/%s", cdpath->word,
 					a->next->word);
 			else
-				dir = strdup(a->next->word);
+				dir = estrdup(a->next->word);
 
 			if(dochdir(dir) >= 0){
 				if(cdpath->word[0] != '\0' &&
@@ -355,7 +355,7 @@
 		Xerror1("Usage: . [-i] file [arg ...]");
 		return;
 	}
-	zero = strdup(p->argv->words->word);
+	zero = estrdup(p->argv->words->word);
 	popword();
 	fd = -1;
 	for(path = searchpath(zero); path; path = path->next){
@@ -362,7 +362,7 @@
 		if(path->word[0] != '\0')
 			file = smprint("%s/%s", path->word, zero);
 		else
-			file = strdup(zero);
+			file = estrdup(zero);
 
 		fd = open(file, 0);
 		free(file);
@@ -480,7 +480,7 @@
 						file = smprint("%s/%s",
 							path->word, a->word);
 					else
-						file = strdup(a->word);
+						file = estrdup(a->word);
 					if(Executable(file)){
 						pfmt(out, "%s\n", file);
 						free(file);
--- a/sys/src/cmd/rc/subr.c
+++ b/sys/src/cmd/rc/subr.c
@@ -30,6 +30,19 @@
 		free(p);
 	else pfmt(err, "free 0\n");
 }
+
+char*
+estrdup(char *s)
+{
+	char *d;
+	int n;
+
+	n = strlen(s)+1;
+	d = emalloc(n);
+	Memcpy(d, s, n);
+	return d;
+}
+
 extern int lastword, lastdol;
 
 void
--- a/sys/src/cmd/rc/trap.c
+++ b/sys/src/cmd/rc/trap.c
@@ -18,7 +18,7 @@
 		trapreq = vlook(Signame[i]);
 		if(trapreq->fn){
 			start(trapreq->fn, trapreq->pc, (struct var *)0);
-			runq->local = newvar(strdup("*"), runq->local);
+			runq->local = newvar("*", runq->local);
 			runq->local->val = copywords(starval, (struct word *)0);
 			runq->local->changed = 1;
 			runq->redir = runq->startredir = 0;
--- a/sys/src/cmd/rc/tree.c
+++ b/sys/src/cmd/rc/tree.c
@@ -111,7 +111,7 @@
 	t = tree1(SIMPLE, t);
 	s = openstr();
 	pfmt(s, "%t", t);
-	t->str = strdup((char *)s->strp);
+	t->str = estrdup((char *)s->strp);
 	closeio(s);
 	for(u = t->child[0];u->type==ARGLIST;u = u->child[0]){
 		if(u->child[1]->type==DUP
--- a/sys/src/cmd/rc/unix.c
+++ b/sys/src/cmd/rc/unix.c
@@ -256,7 +256,7 @@
 		case ENOEXEC:
 			pfmt(err, "%s: Bourne again\n", argv[1]);
 			argv[0]="sh";
-			argv[1] = strdup(file);
+			argv[1] = estrdup(file);
 			execve("/bin/sh", argv, env);
 			goto Bad;
 		case ETXTBSY:
--- a/sys/src/cmd/rc/var.c
+++ b/sys/src/cmd/rc/var.c
@@ -63,7 +63,7 @@
 	int h = hash(name, NVAR);
 	var *v;
 	for(v = gvar[h];v;v = v->next) if(strcmp(v->name, name)==0) return v;
-	return gvar[h] = newvar(strdup(name), gvar[h]);
+	return gvar[h] = newvar(name, gvar[h]);
 }
 
 var*