[MEDIUM] config: automatically find unused IDs for proxies, servers and listeners

Until now it was required that every custom ID was above 1000 in order to
avoid conflicts. Now we have the list of all assigned IDs and can automatically
pick the first unused one. This means that it is perfectly possible to interleave
automatic IDs with persistent IDs and the parser will automatically allocate
unused values starting with 1.
diff --git a/doc/configuration.txt b/doc/configuration.txt
index a92d304..6fe6e95 100644
--- a/doc/configuration.txt
+++ b/doc/configuration.txt
@@ -724,6 +724,7 @@
 fullconn                    X          -         X         X
 grace                       -          X         X         X
 http-check disable-on-404   X          -         X         X
+id                          -          X         X         X
 log                         X          X         X         X
 maxconn                     X          X         X         -
 mode                        X          X         X         X
@@ -1140,10 +1141,10 @@
                   work on other operating systems. The commonly advertised
                   value on Ethernet networks is 1460 = 1500(MTU) - 40(IP+TCP).
 
-    <id>          is a persistent value for socket ID. Must be unique and
-                  larger than 1000, as smaller values are reserved for
-                  auto-assigned ids. Can only be used when defining only
-                  a single socket.
+    <id>          is a persistent value for socket ID. Must be positive and
+                  unique in the proxy. An unused value will automatically be
+                  assigned if unset. Can only be used when defining only a
+                  single socket.
 
     <name>        is an optional name provided for stats
 
@@ -1748,8 +1749,14 @@
 
 
 id <value>
-  Set a persistent value for proxy ID. Must be unique and larger than 1000, as
-  smaller values are reserved for auto-assigned ids.
+  Set a persistent ID to a proxy.
+  May be used in sections :   defaults | frontend | listen | backend
+                                  no   |    yes   |   yes  |   yes
+  Arguments : none
+
+  Set a persistent ID for the proxy. This ID must be unique and positive.
+  An unused ID will automatically be assigned if unset. The first assigned
+  value will be 1. This ID is currently only returned in statistics.
 
 
 log global
@@ -4583,8 +4590,9 @@
   unspecified. See also the "check", "inter" and "rise" parameters.
 
 id <value>
-  Set a persistent value for server ID. Must be unique and larger than 1000, as
-  smaller values are reserved for auto-assigned ids.
+  Set a persistent ID for the server. This ID must be positive and unique for
+  the proxy. An unused ID will automatically be assigned if unset. The first
+  assigned value will be 1. This ID is currently only returned in statistics.
 
 inter <delay>
 fastinter <delay>
diff --git a/include/types/protocols.h b/include/types/protocols.h
index 62d9f60..849ca55 100644
--- a/include/types/protocols.h
+++ b/include/types/protocols.h
@@ -28,6 +28,7 @@
 #include <sys/un.h>
 
 #include <common/config.h>
+#include <common/eb32tree.h>
 #include <common/mini-clist.h>
 
 #include <types/counters.h>
@@ -108,6 +109,7 @@
 	struct {
 		const char *file;	/* file where the section appears */
 		int line;		/* line where the section appears */
+		struct eb32_node id;	/* place in the tree of used IDs */
 	} conf;				/* config information */
 };
 
diff --git a/include/types/proxy.h b/include/types/proxy.h
index 88a01cc..aac704d 100644
--- a/include/types/proxy.h
+++ b/include/types/proxy.h
@@ -29,6 +29,7 @@
 
 #include <common/appsession.h>
 #include <common/config.h>
+#include <common/eb32tree.h>
 #include <common/mini-clist.h>
 #include <common/regex.h>
 #include <common/sessionhash.h>
@@ -248,7 +249,6 @@
 	int check_len;				/* Length of the HTTP or SSL3 request */
 	struct chunk errmsg[HTTP_ERR_SIZE];	/* default or customized error messages for known errors */
 	int uuid;				/* universally unique proxy ID, used for SNMP */
-	int next_svid, next_lid;		/* next server-id and listener-id, used for SNMP */
 	unsigned int backlog;			/* force the frontend's listen backlog */
 	unsigned int bind_proc;			/* bitmask of processes using this proxy. 0 = all. */
 	struct error_snapshot invalid_req, invalid_rep; /* captures of last errors */
@@ -262,6 +262,9 @@
 	struct {
 		const char *file;		/* file where the section appears */
 		int line;			/* line where the section appears */
+		struct eb32_node id;		/* place in the tree of used IDs */
+		struct eb_root used_listener_id;/* list of listener IDs in use */
+		struct eb_root used_server_id;	/* list of server IDs in use */
 	} conf;					/* config information */
 };
 
@@ -287,7 +290,7 @@
 };
 
 extern struct proxy *proxy;
-extern int next_pxid;
+extern struct eb_root used_proxy_id;	/* list of proxy IDs in use */
 
 #endif /* _TYPES_PROXY_H */
 
diff --git a/include/types/server.h b/include/types/server.h
index 45528fa..fa01810 100644
--- a/include/types/server.h
+++ b/include/types/server.h
@@ -135,6 +135,7 @@
 	struct {
 		const char *file;		/* file where the section appears */
 		int line;			/* line where the section appears */
+		struct eb32_node id;		/* place in the tree of used IDs */
 	} conf;					/* config information */
 };
 
diff --git a/src/cfgparse.c b/src/cfgparse.c
index e65f59d..9868b05 100644
--- a/src/cfgparse.c
+++ b/src/cfgparse.c
@@ -258,7 +258,6 @@
 				tcpv4_add_listener(l);
 			}
 
-			l->luid = curproxy->next_lid++;
 			listeners++;
 		} /* end for(port) */
 	} /* end while(next) */
@@ -1013,9 +1012,8 @@
 		curproxy->loglev2 = defproxy.loglev2;
 		curproxy->minlvl2 = defproxy.minlvl2;
 		curproxy->grace  = defproxy.grace;
-		curproxy->uuid = next_pxid++;   /* generate a uuid for this proxy */
-		curproxy->next_svid = 1;        /* server id 0 is reserved */
-		curproxy->next_lid  = 1;        /* listener id 0 is reserved */
+		curproxy->conf.used_listener_id = EB_ROOT;
+		curproxy->conf.used_server_id = EB_ROOT;
 
 		goto out;
 	}
@@ -1172,6 +1170,7 @@
 			}
 
 			if (!strcmp(args[cur_arg], "id")) {
+				struct eb32_node *node;
 				struct listener *l;
 
 				if (curproxy->listen->next != last_listen) {
@@ -1189,21 +1188,25 @@
 				}
 
 				curproxy->listen->luid = atol(args[cur_arg + 1]);
+				curproxy->listen->conf.id.key = curproxy->listen->luid;
 
-				if (curproxy->listen->luid < 1001) {
-					Alert("parsing [%s:%d]: custom id has to be > 1000\n",
+				if (curproxy->listen->luid <= 0) {
+					Alert("parsing [%s:%d]: custom id has to be > 0\n",
 						file, linenum);
 					err_code |= ERR_ALERT | ERR_FATAL;
 					goto out;
 				}
 
-				for (l = curproxy->listen; l; l = l->next)
-					if (curproxy->listen != l && l->luid == curproxy->listen->luid) {
-						Alert("parsing [%s:%d]: custom id %d for socket '%s' already used at %s:%d.\n",
-						      file, linenum, l->luid, args[1], l->conf.file, l->conf.line);
-						err_code |= ERR_ALERT | ERR_FATAL;
-						goto out;
-					}
+				node = eb32_lookup(&curproxy->conf.used_listener_id, curproxy->listen->luid);
+				if (node) {
+					l = container_of(node, struct listener, conf.id);
+					Alert("parsing [%s:%d]: custom id %d for socket '%s' already used at %s:%d.\n",
+					      file, linenum, l->luid, args[1], l->conf.file, l->conf.line);
+					err_code |= ERR_ALERT | ERR_FATAL;
+					goto out;
+				}
+				eb32_insert(&curproxy->conf.used_listener_id, &curproxy->listen->conf.id);
+
 				cur_arg += 2;
 				continue;
 			}
@@ -1260,7 +1263,7 @@
 		}
 	}
 	else if (!strcmp(args[0], "id")) {
-		struct proxy *target;
+		struct eb32_node *node;
 
 		if (curproxy == &defproxy) {
 			Alert("parsing [%s:%d]: '%s' not allowed in 'defaults' section.\n",
@@ -1277,22 +1280,25 @@
 		}
 
 		curproxy->uuid = atol(args[1]);
+		curproxy->conf.id.key = curproxy->uuid;
 
-		if (curproxy->uuid < 1001) {
-			Alert("parsing [%s:%d]: custom id has to be > 1000.\n",
+		if (curproxy->uuid <= 0) {
+			Alert("parsing [%s:%d]: custom id has to be > 0.\n",
 				file, linenum);
 			err_code |= ERR_ALERT | ERR_FATAL;
 			goto out;
 		}
 
-		for (target = proxy; target; target = target->next)
-			if (curproxy != target && curproxy->uuid == target->uuid) {
-				Alert("parsing [%s:%d]: %s %s reuses same custom id as %s %s (declared at %s:%d).\n",
-				      file, linenum, proxy_type_str(curproxy), curproxy->id,
-				      proxy_type_str(target), target->id, target->conf.file, target->conf.line);
-				err_code |= ERR_ALERT | ERR_FATAL;
-				goto out;
-			}
+		node = eb32_lookup(&used_proxy_id, curproxy->uuid);
+		if (node) {
+			struct proxy *target = container_of(node, struct proxy, conf.id);
+			Alert("parsing [%s:%d]: %s %s reuses same custom id as %s %s (declared at %s:%d).\n",
+			      file, linenum, proxy_type_str(curproxy), curproxy->id,
+			      proxy_type_str(target), target->id, target->conf.file, target->conf.line);
+			err_code |= ERR_ALERT | ERR_FATAL;
+			goto out;
+		}
+		eb32_insert(&used_proxy_id, &curproxy->conf.id);
 	}
 	else if (!strcmp(args[0], "description")) {
 		int i, len=0;
@@ -2474,7 +2480,6 @@
 		newsrv->next = curproxy->srv;
 		curproxy->srv = newsrv;
 		newsrv->proxy = curproxy;
-		newsrv->puid = curproxy->next_svid++;
 		newsrv->conf.file = file;
 		newsrv->conf.line = linenum;
 
@@ -2521,7 +2526,7 @@
 		cur_arg = 3;
 		while (*args[cur_arg]) {
 			if (!strcmp(args[cur_arg], "id")) {
-				struct server *target;
+				struct eb32_node *node;
 
 				if (!*args[cur_arg + 1]) {
 					Alert("parsing [%s:%d]: '%s' expects an integer argument.\n",
@@ -2531,21 +2536,24 @@
 				}
 
 				newsrv->puid = atol(args[cur_arg + 1]);
+				newsrv->conf.id.key = newsrv->puid;
 
-				if (newsrv->puid< 1001) {
-					Alert("parsing [%s:%d]: custom id has to be > 1000.\n",
+				if (newsrv->puid <= 0) {
+					Alert("parsing [%s:%d]: custom id has to be > 0.\n",
 						file, linenum);
 					err_code |= ERR_ALERT | ERR_FATAL;
 					goto out;
 				}
 
-				for (target = proxy->srv; target; target = target->next)
-					if (newsrv != target && newsrv->puid == target->puid) {
-						Alert("parsing [%s:%d]: server %s reuses same custom id as server %s (declared at %s:%d).\n",
-						      file, linenum, newsrv->id, target->id, target->conf.file, target->conf.line);
-						err_code |= ERR_ALERT | ERR_FATAL;
-						goto out;
-					}
+				node = eb32_lookup(&curproxy->conf.used_server_id, newsrv->puid);
+				if (node) {
+					struct server *target = container_of(node, struct server, conf.id);
+					Alert("parsing [%s:%d]: server %s reuses same custom id as server %s (declared at %s:%d).\n",
+					      file, linenum, newsrv->id, target->id, target->conf.file, target->conf.line);
+					err_code |= ERR_ALERT | ERR_FATAL;
+					goto out;
+				}
+				eb32_insert(&curproxy->conf.used_server_id, &newsrv->conf.id);
 				cur_arg += 2;
 			}
 			else if (!strcmp(args[cur_arg], "cookie")) {
@@ -3986,6 +3994,7 @@
 	struct proxy *curproxy = NULL;
 	struct server *newsrv = NULL;
 	int err_code = 0;
+	unsigned int next_pxid = 1;
 
 	/*
 	 * Now, check for the integrity of all that we have collected.
@@ -4016,6 +4025,17 @@
 	while (curproxy != NULL) {
 		struct switching_rule *rule;
 		struct listener *listener;
+		unsigned int next_id;
+
+		if (!curproxy->uuid) {
+			/* proxy ID not set, use automatic numbering with first
+			 * spare entry starting with next_pxid.
+			 */
+			next_pxid = get_next_id(&used_proxy_id, next_pxid);
+			curproxy->conf.id.key = curproxy->uuid = next_pxid;
+			eb32_insert(&used_proxy_id, &curproxy->conf.id);
+			next_pxid++;
+		}
 
 		if (curproxy->state == PR_STSTOPPED) {
 			/* ensure we don't keep listeners uselessly bound */
@@ -4301,8 +4321,19 @@
 		/*
 		 * ensure that we're not cross-dressing a TCP server into HTTP.
 		 */
+		next_id = 1;
 		newsrv = curproxy->srv;
 		while (newsrv != NULL) {
+			if (!newsrv->puid) {
+				/* server ID not set, use automatic numbering with first
+				 * spare entry starting with next_svid.
+				 */
+				next_id = get_next_id(&curproxy->conf.used_server_id, next_id);
+				newsrv->conf.id.key = newsrv->puid = next_id;
+				eb32_insert(&curproxy->conf.used_server_id, &newsrv->conf.id);
+				next_id++;
+			}
+
 			if ((curproxy->mode != PR_MODE_HTTP) && (newsrv->rdr_len || newsrv->cklen)) {
 				Alert("config : %s '%s' : server cannot have cookie or redirect prefix in non-HTTP mode.\n",
 				      proxy_type_str(curproxy), curproxy->id);
@@ -4440,8 +4471,19 @@
 		}
 
 		/* adjust this proxy's listeners */
+		next_id = 1;
 		listener = curproxy->listen;
 		while (listener) {
+			if (!listener->luid) {
+				/* listener ID not set, use automatic numbering with first
+				 * spare entry starting with next_luid.
+				 */
+				next_id = get_next_id(&curproxy->conf.used_listener_id, next_id);
+				listener->conf.id.key = listener->luid = next_id;
+				eb32_insert(&curproxy->conf.used_listener_id, &listener->conf.id);
+				next_id++;
+			}
+
 			/* enable separate counters */
 			if (curproxy->options2 & PR_O2_SOCKSTAT) {
 				listener->counters = (struct licounters *)calloc(1, sizeof(struct licounters));
diff --git a/src/proxy.c b/src/proxy.c
index c7b1f4d..fa6a197 100644
--- a/src/proxy.c
+++ b/src/proxy.c
@@ -39,7 +39,7 @@
 
 int listeners;	/* # of proxy listeners, set by cfgparse, unset by maintain_proxies */
 struct proxy *proxy  = NULL;	/* list of all existing proxies */
-int next_pxid = 1;		/* UUID assigned to next new proxy, 0 reserved */
+struct eb_root used_proxy_id = EB_ROOT;	/* list of proxy IDs in use */
 
 /*
  * This function returns a string containing a name describing capabilities to