- make aliases expansion use a rb tree instead of a tail queue, the code

  doesn't take advantage of the new structure yet, but this was a needed
  change for upcoming improvements.
- introduce aliasestree_{lookup,insert,remove} to the aliases api
- rename queue_generate_id() to generate_uid() and move it to utils.c as
  it is used all over the place and not only in queue

tree idea discussed with jacekm@, if you update rebuild aliases db, make
clean and flush queue

10 files changed, 116 insertions, 66 deletions

diff --git a/usr.sbin/smtpd/aliases.c b/usr.sbin/smtpd/aliases.c
index 0285c6cbdfb..cca16116499 100644
--- a/usr.sbin/smtpd/aliases.c
+++ b/usr.sbin/smtpd/aliases.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: aliases.c,v 1.25 2009/11/03 20:55:23 gilles Exp $	*/
+/*	$OpenBSD: aliases.c,v 1.26 2009/11/08 21:40:05 gilles Exp $	*/
 
 /*
  * Copyright (c) 2008 Gilles Chehade <gilles@openbsd.org>
@@ -34,7 +34,7 @@
 
 #include "smtpd.h"
 
-int aliases_expand_include(struct aliaseslist *, char *);
+int aliases_expand_include(struct aliasestree *, char *);
 int alias_is_filter(struct alias *, char *, size_t);
 int alias_is_username(struct alias *, char *, size_t);
 int alias_is_address(struct alias *, char *, size_t);
@@ -75,7 +75,7 @@ aliases_exist(struct smtpd *env, objid_t mapid, char *username)
 }
 
 int
-aliases_get(struct smtpd *env, objid_t mapid, struct aliaseslist *aliases, char *username)
+aliases_get(struct smtpd *env, objid_t mapid, struct aliasestree *aliases, char *username)
 {
 	char buf[MAXLOGNAME];
 	int ret;
@@ -128,7 +128,7 @@ aliases_get(struct smtpd *env, objid_t mapid, struct aliaseslist *aliases, char
 			if (aliasp == NULL)
 				fatal("aliases_get: calloc");
 			*aliasp = alias;
-			TAILQ_INSERT_HEAD(aliases, aliasp, entry);
+			aliasestree_insert(aliases, aliasp);
 		}
 	} while (--nbaliases);
 	aliasesdb->close(aliasesdb);
@@ -229,7 +229,7 @@ aliases_virtual_exist(struct smtpd *env, objid_t mapid, struct path *path)
 
 int
 aliases_virtual_get(struct smtpd *env, objid_t mapid,
-    struct aliaseslist *aliases, struct path *path)
+    struct aliasestree *aliases, struct path *path)
 {
 	int ret;
 	DBT key;
@@ -303,7 +303,7 @@ aliases_virtual_get(struct smtpd *env, objid_t mapid,
 			if (aliasp == NULL)
 				fatal("aliases_virtual_get: calloc");
 			*aliasp = alias;
-			TAILQ_INSERT_HEAD(aliases, aliasp, entry);
+			aliasestree_insert(aliases, aliasp);
 		}
 	} while (--nbaliases);
 	aliasesdb->close(aliasesdb);
@@ -311,7 +311,7 @@ aliases_virtual_get(struct smtpd *env, objid_t mapid,
 }
 
 int
-aliases_expand_include(struct aliaseslist *aliases, char *filename)
+aliases_expand_include(struct aliasestree *aliases, char *filename)
 {
 	FILE *fp;
 	char *line;
@@ -344,7 +344,7 @@ aliases_expand_include(struct aliaseslist *aliases, char *filename)
 			if (aliasp == NULL)
 				fatal("aliases_expand_include: calloc");
 			*aliasp = alias;
-			TAILQ_INSERT_TAIL(aliases, aliasp, entry);
+			aliasestree_insert(aliases, aliasp);
 		}
 
 		free(line);
@@ -485,3 +485,47 @@ alias_is_include(struct alias *alias, char *line, size_t len)
 	alias->type = ALIAS_INCLUDE;
 	return 1;
 }
+
+int
+alias_cmp(struct alias *a1, struct alias *a2)
+{
+	/*
+	 * do not return u_int64_t's
+	 */
+	if (a1->id < a2->id)
+		return (-1);
+
+	if (a1->id > a2->id)
+		return (1);
+
+	return (0);
+}
+
+struct alias *
+aliasestree_lookup(struct aliasestree *aliasestree, struct alias *alias)
+{
+	struct alias key;
+
+	key = *alias;
+	return RB_FIND(aliasestree, aliasestree, &key);
+}
+
+void
+aliasestree_insert(struct aliasestree *aliasestree, struct alias *alias)
+{
+	alias->id = generate_uid();
+	RB_INSERT(aliasestree, aliasestree, alias);
+}
+
+void
+aliasestree_remove(struct aliasestree *aliasestree, struct alias *alias)
+{
+	struct alias *node;
+
+	node = aliasestree_lookup(aliasestree, alias);
+	if (node == NULL)
+		fatalx("aliasestree_remove: node doesn't exist.");
+	RB_REMOVE(aliasestree, aliasestree, alias);
+}
+
+RB_GENERATE(aliasestree, alias, entry, alias_cmp);
diff --git a/usr.sbin/smtpd/enqueue.c b/usr.sbin/smtpd/enqueue.c
index e683354297b..87ed3035892 100644
--- a/usr.sbin/smtpd/enqueue.c
+++ b/usr.sbin/smtpd/enqueue.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: enqueue.c,v 1.24 2009/09/21 20:35:26 jacekm Exp $	*/
+/*	$OpenBSD: enqueue.c,v 1.25 2009/11/08 21:40:05 gilles Exp $	*/
 
 /*
  * Copyright (c) 2005 Henning Brauer <henning@bulabula.org>
@@ -233,7 +233,7 @@ enqueue(int argc, char *argv[])
 	if (!msg.saw_msgid)
 		if (client_data_printf(sp,
 		    "Message-Id: <%llu.enqueue@%s>\n",
-		    queue_generate_id(), host) < 0)
+			generate_uid(), host) < 0)
 			err(1, "client_data_printf failed");
 
 	/* add separating newline */
diff --git a/usr.sbin/smtpd/forward.c b/usr.sbin/smtpd/forward.c
index 94df78af645..f2d70a9f608 100644
--- a/usr.sbin/smtpd/forward.c
+++ b/usr.sbin/smtpd/forward.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: forward.c,v 1.15 2009/11/08 19:38:26 gilles Exp $	*/
+/*	$OpenBSD: forward.c,v 1.16 2009/11/08 21:40:05 gilles Exp $	*/
 
 /*
  * Copyright (c) 2008 Gilles Chehade <gilles@openbsd.org>
@@ -35,7 +35,7 @@
 #include "smtpd.h"
 
 int
-forwards_get(int fd, struct aliaseslist *aliases)
+forwards_get(int fd, struct aliasestree *aliases)
 {
 	FILE *fp;
 	struct alias alias;
@@ -99,7 +99,7 @@ forwards_get(int fd, struct aliaseslist *aliases)
 			if (aliasp == NULL)
 				fatal("calloc");
 			*aliasp = alias;
-			TAILQ_INSERT_HEAD(aliases, aliasp, entry);
+			aliasestree_insert(aliases, aliasp);
 			nbaliases++;
 		} while (*cp != '\0');
 	}
diff --git a/usr.sbin/smtpd/lka.c b/usr.sbin/smtpd/lka.c
index 29b45fbfaab..741efc2923f 100644
--- a/usr.sbin/smtpd/lka.c
+++ b/usr.sbin/smtpd/lka.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: lka.c,v 1.81 2009/11/08 19:38:26 gilles Exp $	*/
+/*	$OpenBSD: lka.c,v 1.82 2009/11/08 21:40:05 gilles Exp $	*/
 
 /*
  * Copyright (c) 2008 Pierre-Yves Ritschard <pyr@openbsd.org>
@@ -59,7 +59,7 @@ struct rule    *ruleset_match(struct smtpd *, char *, struct path *, struct sock
 int		lka_resolve_path(struct smtpd *, struct lkasession *, struct path *);
 struct lkasession *lka_session_init(struct smtpd *, struct submit_status *);
 void		lka_request_forwardfile(struct smtpd *, struct lkasession *, char *);
-void		lka_clear_aliaseslist(struct aliaseslist *);
+void		lka_clear_aliasestree(struct aliasestree *);
 void		lka_clear_deliverylist(struct deliverylist *);
 int		lka_encode_credentials(char *, size_t, char *);
 size_t		lka_expand(char *, size_t, struct path *);
@@ -232,7 +232,7 @@ lka_dispatch_parent(int sig, short event, void *p)
 
 			/* received a descriptor, we have a forward file ... */
 			if (fd != -1) {
-				if (! forwards_get(fd, &lkasession->aliaseslist)) {
+				if (! forwards_get(fd, &lkasession->aliasestree)) {
 					lkasession->ss.code = 530;
 					lkasession->flags |= F_ERROR;					
 				}
@@ -370,7 +370,7 @@ lka_dispatch_mfa(int sig, short event, void *p)
 
 			if (path->flags & F_PATH_ALIAS) {
 				if (! aliases_get(env, ss->u.path.rule.r_amap,
-					&lkasession->aliaseslist, ss->u.path.user)) {
+					&lkasession->aliasestree, ss->u.path.user)) {
 					ss->code = 530;
 					imsg_compose_event(iev, IMSG_LKA_RCPT, 0, 0, -1,
 					    ss, sizeof(*ss));
@@ -381,7 +381,7 @@ lka_dispatch_mfa(int sig, short event, void *p)
 
 			if (path->flags & F_PATH_VIRTUAL) {
 				if (! aliases_virtual_get(env, ss->u.path.cond->c_map,
-					&lkasession->aliaseslist, &ss->u.path)) {
+					&lkasession->aliasestree, &ss->u.path)) {
 					ss->code = 530;
 					imsg_compose_event(iev, IMSG_LKA_RCPT, 0, 0, -1,
 					    ss, sizeof(*ss));
@@ -940,11 +940,11 @@ lka_expand_resume(struct smtpd *env, struct lkasession *lkasession)
 
 	lkasessionpath = &lkasession->path;
 	rmalias = NULL;
-	TAILQ_FOREACH(alias, &lkasession->aliaseslist, entry) {
+	RB_FOREACH(alias, aliasestree, &lkasession->aliasestree) {
 		struct path path;
 
 		if (rmalias) {
-			TAILQ_REMOVE(&lkasession->aliaseslist, rmalias, entry);
+			aliasestree_remove(&lkasession->aliasestree, rmalias);
 			free(rmalias);
 			rmalias = NULL;
 		}
@@ -967,20 +967,20 @@ lka_expand_resume(struct smtpd *env, struct lkasession *lkasession)
 
 		else if (respath->flags & F_PATH_ALIAS) {
 			if (aliases_get(env, lkasessionpath->rule.r_amap,
-				&lkasession->aliaseslist, respath->user))
+				&lkasession->aliasestree, respath->user))
 				done = 0;
 		}
 
 		else if (respath->flags & F_PATH_VIRTUAL) {
 			if (aliases_virtual_get(env, lkasessionpath->cond->c_map,
-				&lkasession->aliaseslist, respath))
+				&lkasession->aliasestree, respath))
 				done = 0;
 		}
 
 	}
 
 	if (rmalias) {
-		TAILQ_REMOVE(&lkasession->aliaseslist, rmalias, entry);
+		aliasestree_remove(&lkasession->aliasestree, rmalias);
 		free(rmalias);
 	}
 
@@ -988,7 +988,7 @@ lka_expand_resume(struct smtpd *env, struct lkasession *lkasession)
 		return -1;
 	}
 
-	if (TAILQ_FIRST(&lkasession->aliaseslist) == NULL)
+	if (RB_ROOT(&lkasession->aliasestree) == NULL)
 		return 0;
 
 	return 1;
@@ -1078,12 +1078,12 @@ lkasession_cmp(struct lkasession *s1, struct lkasession *s2)
 }
 
 void
-lka_clear_aliaseslist(struct aliaseslist *aliaseslist)
+lka_clear_aliasestree(struct aliasestree *aliasestree)
 {
 	struct alias *alias;
 
-	while ((alias = TAILQ_FIRST(aliaseslist)) != NULL) {
-		TAILQ_REMOVE(aliaseslist, alias, entry);
+	while ((alias = RB_ROOT(aliasestree)) != NULL) {
+		aliasestree_remove(aliasestree, alias);
 		free(alias);
 	}
 }
@@ -1130,12 +1130,12 @@ lka_session_init(struct smtpd *env, struct submit_status *ss)
 	if (lkasession == NULL)
 		fatal("lka_session_init: calloc");
 
-	lkasession->id = queue_generate_id();
+	lkasession->id = generate_uid();
 	lkasession->path = ss->u.path;
 	lkasession->message = ss->msg;
 	lkasession->ss = *ss;
 	
-	TAILQ_INIT(&lkasession->aliaseslist);
+	RB_INIT(&lkasession->aliasestree);
 	TAILQ_INIT(&lkasession->deliverylist);
 	SPLAY_INSERT(lkatree, &env->lka_sessions, lkasession);
 
@@ -1168,7 +1168,7 @@ lka_expansion_done(struct smtpd *env, struct lkasession *lkasession)
 	struct path *path;
 
 	if (lkasession->flags & F_ERROR) {
-		lka_clear_aliaseslist(&lkasession->aliaseslist);
+		lka_clear_aliasestree(&lkasession->aliasestree);
 		lka_clear_deliverylist(&lkasession->deliverylist);
 		imsg_compose_event(env->sc_ievs[PROC_MFA], IMSG_LKA_RCPT, 0, 0,
 		    -1, &lkasession->ss, sizeof(struct submit_status));
@@ -1192,5 +1192,4 @@ lka_expansion_done(struct smtpd *env, struct lkasession *lkasession)
 	lka_session_destroy(env, lkasession);
 }
 
-
 SPLAY_GENERATE(lkatree, lkasession, nodes, lkasession_cmp);
diff --git a/usr.sbin/smtpd/queue.c b/usr.sbin/smtpd/queue.c
index 89a766e4065..c9074ea3b6e 100644
--- a/usr.sbin/smtpd/queue.c
+++ b/usr.sbin/smtpd/queue.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: queue.c,v 1.72 2009/11/01 22:15:27 gilles Exp $	*/
+/*	$OpenBSD: queue.c,v 1.73 2009/11/08 21:40:05 gilles Exp $	*/
 
 /*
  * Copyright (c) 2008 Gilles Chehade <gilles@openbsd.org>
@@ -410,7 +410,7 @@ queue_dispatch_lka(int sig, short event, void *p)
 
 			IMSG_SIZE_CHECK(messagep);
 
-			messagep->id = queue_generate_id();
+			messagep->id = generate_uid();
 			ss.id = messagep->session_id;
 
 			if (IS_MAILBOX(messagep->recipient) ||
diff --git a/usr.sbin/smtpd/queue_shared.c b/usr.sbin/smtpd/queue_shared.c
index 1e9f90ac995..eecfa600f7a 100644
--- a/usr.sbin/smtpd/queue_shared.c
+++ b/usr.sbin/smtpd/queue_shared.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: queue_shared.c,v 1.25 2009/09/15 16:50:06 jacekm Exp $	*/
+/*	$OpenBSD: queue_shared.c,v 1.26 2009/11/08 21:40:05 gilles Exp $	*/
 
 /*
  * Copyright (c) 2008 Gilles Chehade <gilles@openbsd.org>
@@ -570,23 +570,6 @@ queue_load_envelope(struct message *messagep, char *evpid)
 	return 1;
 }
 
-u_int64_t
-queue_generate_id(void)
-{
-	u_int64_t	id;
-	struct timeval	tp;
-
-	if (gettimeofday(&tp, NULL) == -1)
-		fatal("queue_generate_id: time");
-
-	id = (u_int32_t)tp.tv_sec;
-	id <<= 32;
-	id |= (u_int32_t)tp.tv_usec;
-	usleep(1);
-
-	return (id);
-}
-
 u_int16_t
 queue_hash(char *msgid)
 {
diff --git a/usr.sbin/smtpd/runner.c b/usr.sbin/smtpd/runner.c
index cb7f3d3ef29..31b0017057d 100644
--- a/usr.sbin/smtpd/runner.c
+++ b/usr.sbin/smtpd/runner.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: runner.c,v 1.70 2009/11/03 11:10:43 jacekm Exp $	*/
+/*	$OpenBSD: runner.c,v 1.71 2009/11/08 21:40:05 gilles Exp $	*/
 
 /*
  * Copyright (c) 2008 Gilles Chehade <gilles@openbsd.org>
@@ -960,7 +960,7 @@ batch_record(struct smtpd *env, struct message *messagep)
 		if (batchp == NULL)
 			fatal("batch_record: calloc");
 
-		batchp->id = queue_generate_id();
+		batchp->id = generate_uid();
 
 		(void)strlcpy(batchp->message_id, messagep->message_id,
 		    sizeof(batchp->message_id));
diff --git a/usr.sbin/smtpd/smtp.c b/usr.sbin/smtpd/smtp.c
index e1f939f66e5..14465f9d355 100644
--- a/usr.sbin/smtpd/smtp.c
+++ b/usr.sbin/smtpd/smtp.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: smtp.c,v 1.63 2009/10/25 21:06:06 gilles Exp $	*/
+/*	$OpenBSD: smtp.c,v 1.64 2009/11/08 21:40:05 gilles Exp $	*/
 
 /*
  * Copyright (c) 2008 Gilles Chehade <gilles@openbsd.org>
@@ -535,7 +535,7 @@ smtp_dispatch_control(int sig, short event, void *p)
 			if ((s = calloc(1, sizeof(*s))) == NULL)
 				fatal(NULL);
 
-			s->s_id = queue_generate_id();
+			s->s_id = generate_uid();
 			s->s_fd = fd[0];
 			s->s_env = env;
 			s->s_l = &l;
@@ -643,7 +643,7 @@ smtp_dispatch_runner(int sig, short event, void *p)
 			if ((s = calloc(1, sizeof(*s))) == NULL)
 				fatal(NULL);
 
-			s->s_id = queue_generate_id();
+			s->s_id = generate_uid();
 			s->s_fd = fd[0];
 			s->s_env = env;
 			s->s_l = &l;
@@ -841,7 +841,7 @@ smtp_accept(int fd, short event, void *p)
 		fatal(NULL);
 	len = sizeof(s->s_ss);
 
-	s->s_id = queue_generate_id();
+	s->s_id = generate_uid();
 	s->s_fd = s_fd;
 	s->s_env = l->env;
 	s->s_l = l;
diff --git a/usr.sbin/smtpd/smtpd.h b/usr.sbin/smtpd/smtpd.h
index 6d6d5080aaf..17028a8783d 100644
--- a/usr.sbin/smtpd/smtpd.h
+++ b/usr.sbin/smtpd/smtpd.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: smtpd.h,v 1.154 2009/11/08 19:38:26 gilles Exp $	*/
+/*	$OpenBSD: smtpd.h,v 1.155 2009/11/08 21:40:05 gilles Exp $	*/
 
 /*
  * Copyright (c) 2008 Gilles Chehade <gilles@openbsd.org>
@@ -374,7 +374,8 @@ enum alias_type {
 };
 
 struct alias {
-	TAILQ_ENTRY(alias)		entry;
+	RB_ENTRY(alias)			entry;
+	u_int64_t			 id;
 	enum alias_type			 type;
 	union alias_data {
 		char username[MAXLOGNAME];
@@ -383,7 +384,6 @@ struct alias {
 		struct path path;
 	}                                   u;
 };
-TAILQ_HEAD(aliaseslist, alias);
 
 enum message_type {
 	T_MDA_MESSAGE		= 0x1,
@@ -726,8 +726,10 @@ struct lkasession {
 	u_int64_t			 id;
 
 	struct path			 path;
-	struct aliaseslist		 aliaseslist;
 	struct deliverylist    		 deliverylist;
+
+	RB_HEAD(aliasestree, alias)	 aliasestree;
+
 	u_int8_t			 iterations;
 	u_int32_t			 pending;
 	enum lkasession_flags		 flags;
@@ -777,11 +779,16 @@ struct mta_session {
 
 /* aliases.c */
 int aliases_exist(struct smtpd *, objid_t, char *);
-int aliases_get(struct smtpd *, objid_t, struct aliaseslist *, char *);
+int aliases_get(struct smtpd *, objid_t, struct aliasestree *, char *);
 int aliases_vdomain_exists(struct smtpd *, objid_t, char *);
 int aliases_virtual_exist(struct smtpd *, objid_t, struct path *);
-int aliases_virtual_get(struct smtpd *, objid_t, struct aliaseslist *, struct path *);
+int aliases_virtual_get(struct smtpd *, objid_t, struct aliasestree *, struct path *);
 int alias_parse(struct alias *, char *);
+int alias_cmp(struct alias *, struct alias *);
+void aliasestree_insert(struct aliasestree *, struct alias *);
+void aliasestree_remove(struct aliasestree *, struct alias *);
+struct alias *aliasestree_lookup(struct aliasestree *, struct alias *);
+RB_PROTOTYPE(aliasestree, alias, entry, alias_cmp);
 
 /* authenticate.c */
 int authenticate_user(char *, char *);
@@ -816,7 +823,7 @@ void		 dns_async(struct smtpd *, struct imsgev *, int,
 
 
 /* forward.c */
-int forwards_get(int, struct aliaseslist *);
+int forwards_get(int, struct aliasestree *);
 
 /* smtpd.c */
 int	 child_cmp(struct child *, struct child *);
@@ -836,7 +843,6 @@ int		 msg_cmp(struct message *, struct message *);
 
 /* queue.c */
 pid_t		 queue(struct smtpd *);
-u_int64_t	 queue_generate_id(void);
 int		 queue_load_envelope(struct message *, char *);
 int		 queue_update_envelope(struct message *);
 int		 queue_remove_envelope(struct message *);
@@ -984,3 +990,4 @@ void		 message_set_errormsg(struct message *, char *, ...);
 char		*message_get_errormsg(struct message *);
 void		 sa_set_port(struct sockaddr *, int);
 struct path	*path_dup(struct path *);
+u_int64_t	 generate_uid(void);
diff --git a/usr.sbin/smtpd/util.c b/usr.sbin/smtpd/util.c
index 806e46ad908..a7af7b6dbd8 100644
--- a/usr.sbin/smtpd/util.c
+++ b/usr.sbin/smtpd/util.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: util.c,v 1.28 2009/11/08 19:38:26 gilles Exp $	*/
+/*	$OpenBSD: util.c,v 1.29 2009/11/08 21:40:05 gilles Exp $	*/
 
 /*
  * Copyright (c) 2000,2001 Markus Friedl.  All rights reserved.
@@ -432,3 +432,20 @@ path_dup(struct path *path)
 
 	return pathp;
 }
+
+u_int64_t
+generate_uid(void)
+{
+	u_int64_t	id;
+	struct timeval	tp;
+
+	if (gettimeofday(&tp, NULL) == -1)
+		fatal("generate_uid: time");
+
+	id = (u_int32_t)tp.tv_sec;
+	id <<= 32;
+	id |= (u_int32_t)tp.tv_usec;
+	usleep(1);
+
+	return (id);
+}