tests/filltab25.c - haproxy - Gitiles

 /*
  * experimental weighted round robin scheduler - (c) 2007 willy tarreau.
  *
  * This filling algorithm is excellent at spreading the servers, as it also
  * takes care of keeping the most uniform distance between occurences of each
  * server, by maximizing this distance. It reduces the number of variables
  * and expensive operations.
  */

 #include <stdio.h>
 #include <stdlib.h>
 #include "eb32tree.h"

 struct srv {
 	struct eb32_node node;
 	struct eb_root *tree; // we want to know where the server is
 	int num;
 	int w; /* weight */
 	int next, last;
 	int rem;
 } *srv;

 /* those trees represent a sliding window of 3 time frames */
 struct eb_root tree_0 = EB_ROOT;
 struct eb_root tree_1 = EB_ROOT;
 struct eb_root tree_2 = EB_ROOT;

 struct eb_root *init_tree; /* receives positions 0..sw-1 */
 struct eb_root *next_tree; /* receives positions >= 2sw */

 int nsrv;       /* # of servers */
 int nsw, sw;    /* sum of weights */
 int p;          /* current position, between sw..2sw-1 */

 /* queue a server in the weights tree */
 void queue_by_weight(struct eb_root *root, struct srv *s) {
 	s->node.key = 255 - s->w;
 	eb32i_insert(root, &s->node);
 	s->tree = root;
 }

 /* queue a server in the weight tree <root>, except if its weight is 0 */
 void queue_by_weight_0(struct eb_root *root, struct srv *s) {
 	if (s->w) {
 		s->node.key = 255 - s->w;
 		eb32i_insert(root, &s->node);
 		s->tree = root;
 	} else {
 		s->tree = NULL;
 	}
 }

 static inline void dequeue_srv(struct srv *s) {
 	eb32_delete(&s->node);
 }

 /* queues a server into the correct tree depending on ->next */
 void put_srv(struct srv *s) {
 	if (s->w <= 0 ||
 	    s->next >= 2*sw ||    /* delay everything which does not fit into the window */
 	    s->next >= sw+nsw) {  /* and everything which does not fit into the theorical new window */
 		/* put into next tree */
 		s->next -= sw; // readjust next in case we could finally take this back to current.
 		queue_by_weight_0(next_tree, s);
 	} else { /* FIXME: sw can be smaller than s->rem! */
 		//s->node.key = sw * s->next + s->rem - s->w;
 		//s->node.key = 65536 * s->next + s->rem - s->w;
 		//s->node.key = 256*s->next + (s->rem / 256);
 		//s->node.key = 256*s->next + ((s->rem - s->w) / 256);
 		s->node.key = 16*s->next + ((s->rem - s->w) / 4096);
 		eb32i_insert(&tree_0, &s->node);
 		s->tree = &tree_0;
 	}
 }

 /* prepares a server when extracting it from the init tree */
 static inline void get_srv_init(struct srv *s) {
 	s->next = s->rem = 0;
 }

 /* prepares a server when extracting it from the next tree */
 static inline void get_srv_next(struct srv *s) {
 	s->next += sw;
 }

 /* prepares a server when extracting it from the next tree */
 static inline void get_srv_down(struct srv *s) {
 	s->next = p;
 }

 /* prepares a server when extracting it from its tree */
 void get_srv(struct srv *s) {
 	if (s->tree == init_tree) {
 		get_srv_init(s);
 	}
 	else if (s->tree == next_tree) {
 		get_srv_next(s);
 	}
 	else if (s->tree == NULL) {
 		get_srv_down(s);
 	}
 }


 /* return next server from the current tree, or a server from the init tree
  * if appropriate. If both trees are empty, return NULL.
  */
 struct srv *get_next_server() {
 	struct eb32_node *node;
 	struct srv *s;

 	node = eb32_first(&tree_0);
 	s = eb32_entry(node, struct srv, node);

 	if (!node || s->next > p) {
 		/* either we have no server left, or we have a hole */
 		struct eb32_node *node2;
 		node2 = eb32_first(init_tree);
 		if (node2) {
 			node = node2;
 			s = eb32_entry(node, struct srv, node);
 			get_srv_init(s);
 			if (s->w == 0)
 				node = NULL;
 		}
 	}
 	if (node)
 		return s;
 	else
 		return NULL;
 }

 void update_position(struct srv *s) {
 	//if (s->tree == init_tree) {
 	if (!s->next) {
 		// first time ever for this server
 		s->last = p;
 		s->next = p + nsw / s->w;
 		s->rem += nsw % s->w;

 		if (s->rem >= s->w) {
 			s->rem -= s->w;
 			s->next++;
 		}
 	} else {
 		s->last = s->next;  // or p ?
 		//s->next += sw / s->w;
 		//s->rem += sw % s->w;
 		s->next += nsw / s->w;
 		s->rem += nsw % s->w;

 		if (s->rem >= s->w) {
 			s->rem -= s->w;
 			s->next++;
 		}
 	}
 }


 /* switches trees init_tree and next_tree. init_tree should be empty when
  * this happens, and next_tree filled with servers sorted by weights.
  */
 void switch_trees() {
 	struct eb_root *swap;
 	swap = init_tree;
 	init_tree = next_tree;
 	next_tree = swap;
 	sw = nsw;
 	p = sw;
 }

 main(int argc, char **argv) {
 	int conns;
 	int i;

 	struct srv *s;

 	argc--; argv++;
 	nsrv = argc;

 	if (!nsrv)
 		exit(1);

 	srv  = (struct srv *)calloc(nsrv, sizeof(struct srv));

 	sw = 0;
 	for (i = 0; i < nsrv; i++) {
 		s = &srv[i];
 		s->num = i;
 		s->w = atol(argv[i]);
 		sw += s->w;
 	}

 	nsw = sw;

 	init_tree = &tree_1;
 	next_tree = &tree_2;

 	/* and insert all the servers in the PREV tree */
 	/* note that it is required to insert them according to
 	 * the reverse order of their weights.
 	 */
 	printf("---------------:");
 	for (i = 0; i < nsrv; i++) {
 		s = &srv[i];
 		queue_by_weight_0(init_tree, s);
 		printf("%2d", s->w);
 	}
 	printf("\n");

 	p = sw; // time base of current tree
 	conns = 0;
 	while (1) {
 		struct eb32_node *node;

 		printf("%08d|%06d: ", conns, p);

 		/* if we have en empty tree, let's first try to collect weights
 		 * which might have changed.
 		 */
 		if (!sw) {
 			if (nsw) {
 				sw = nsw;
 				p = sw;
 				/* do not switch trees, otherwise new servers (from init)
 				 * would end up in next.
 				 */
 				//switch_trees();
 				//printf("bla\n");
 			}
 			else
 				goto next_iteration;
 		}

 		s = get_next_server();
 		if (!s) {
 			printf("----------- switch (empty) -- sw=%d -> %d ---------\n", sw, nsw);
 			switch_trees();
 			s = get_next_server();
 			printf("%08d|%06d: ", conns, p);

 			if (!s)
 				goto next_iteration;
 		}
 		else if (s->next >= 2*sw) {
 			printf("ARGGGGG! s[%d].next=%d, max=%d\n", s->num, s->next, 2*sw-1);
 		}

 		/* now we have THE server we want to put at this position */
 		for (i = 0; i < s->num; i++) {
 			if (srv[i].w > 0)
 				printf(". ");
 			else
 				printf("_ ");
 		}
 		printf("# ");
 		for (i = s->num + 1; i < nsrv; i++) {
 			if (srv[i].w > 0)
 				printf(". ");
 			else
 				printf("_ ");
 		}
 		printf("  : ");

 		printf("s=%02d v=%04d w=%03d n=%03d r=%03d ",
 		       s->num, s->node.key, s->w, s->next, s->rem);

 		update_position(s);
 		printf(" | next=%03d, rem=%03d ", s->next, s->rem);

 		if (s->next >= sw * 2) {
 			dequeue_srv(s);
 			//queue_by_weight(next_tree, s);
 			put_srv(s);
 			printf(" => next (w=%d, n=%d) ", s->w, s->next);
 		}
 		else {
 			printf(" => curr ");

 			//s->node.key = s->next;
 			/* we want to ensure that in case of conflicts, servers with
 			 * the highest weights will get served first. Also, we still
 			 * have the remainder to see where the entry expected to be
 			 * inserted.
 			 */
 			//s->node.key = 256 * s->next + 255 - s->w;
 			//s->node.key = sw * s->next + sw / s->w;
 			//s->node.key = sw * s->next + s->rem;  /// seems best (check with filltab15) !

 			//s->node.key = (2 * sw * s->next) + s->rem + sw / s->w;

 			/* FIXME: must be optimized */
 			dequeue_srv(s);
 			put_srv(s);
 			//eb32i_insert(&tree_0, &s->node);
 			//s->tree = &tree_0;
 		}

 	next_iteration:
 		p++;
 		conns++;
 		if (/*conns == 30*/ /**/random()%1000 == 0/**/) {
 			int w = /*20*//**/random()%10000/**/;
 			int num = /*1*//**/random()%nsrv/**/;
 			struct srv *s = &srv[num];

 			nsw = nsw - s->w + w;
 			//sw=nsw;

 			if (s->tree == init_tree) {
 				printf(" -- chgwght1(%d): %d->%d, n=%d --", s->num, s->w, w, s->next);
 				printf("(init)");
 				s->w = w;
 				dequeue_srv(s);
 				queue_by_weight_0(s->tree, s);
 			}
 			else if (s->tree == NULL) {
 				printf(" -- chgwght2(%d): %d->%d, n=%d --", s->num, s->w, w, s->next);
 				printf("(down)");
 				s->w = w;
 				dequeue_srv(s);
 				//queue_by_weight_0(init_tree, s);
 				get_srv(s);
 				s->next = p + (nsw + sw - p) / s->w;
 				put_srv(s);
 			}
 			else {
 				int oldnext;

 				/* the server is either active or in the next queue */
 				get_srv(s);
 				printf(" -- chgwght3(%d): %d->%d, n=%d, sw=%d, nsw=%d --", s->num, s->w, w, s->next, sw, nsw);

 				oldnext = s->next;
 				s->w = w;

 				/* we must measure how far we are from the end of the current window
 				 * and try to fit their as many entries as should theorically be.
 				 */

 				//s->w = s->w * (2*sw - p) / sw;
 				if (s->w > 0) {
 					int step = (nsw /*+ sw - p*/) / s->w;
 					s->next = s->last + step;
 					s->rem = 0;
 					if (s->next > oldnext) {
 						s->next = oldnext;
 						printf(" aaaaaaa ");
 					}

 					if (s->next < p + 2) {
 						s->next = p + step;
 						printf(" bbbbbb ");
 					}
 				} else {
 					printf(" push -- ");
 					/* push it into the next tree */
 					s->w = 0;
 					s->next = p + sw;
 				}


 				dequeue_srv(s);
 				printf(" n=%d", s->next);
 				put_srv(s);
 			}
 		}

 		printf("\n");

 		if (0 && conns % 50000 == 0) {
 			printf("-------- %-5d : changing all weights ----\n", conns);

 			for (i = 0; i < nsrv; i++) {
 				int w = i + 1;
 				s = &srv[i];
 				nsw = nsw - s->w + w;
 				s->w = w;
 				dequeue_srv(s);
 				queue_by_weight_0(next_tree, s); // or init_tree ?
 			}
 		}

 	}
 }
	/*
	* experimental weighted round robin scheduler - (c) 2007 willy tarreau.
	*
	* This filling algorithm is excellent at spreading the servers, as it also
	* takes care of keeping the most uniform distance between occurences of each
	* server, by maximizing this distance. It reduces the number of variables
	* and expensive operations.
	*/

	#include <stdio.h>
	#include <stdlib.h>
	#include "eb32tree.h"

	struct srv {
	struct eb32_node node;
	struct eb_root *tree; // we want to know where the server is
	int num;
	int w; /* weight */
	int next, last;
	int rem;
	} *srv;

	/* those trees represent a sliding window of 3 time frames */
	struct eb_root tree_0 = EB_ROOT;
	struct eb_root tree_1 = EB_ROOT;
	struct eb_root tree_2 = EB_ROOT;

	struct eb_root init_tree; / receives positions 0..sw-1 */
	struct eb_root next_tree; / receives positions >= 2sw */

	int nsrv; /* # of servers */
	int nsw, sw; /* sum of weights */
	int p; /* current position, between sw..2sw-1 */

	/* queue a server in the weights tree */
	void queue_by_weight(struct eb_root root, struct srv s) {
	s->node.key = 255 - s->w;
	eb32i_insert(root, &s->node);
	s->tree = root;
	}

	/* queue a server in the weight tree <root>, except if its weight is 0 */
	void queue_by_weight_0(struct eb_root root, struct srv s) {
	if (s->w) {
	s->node.key = 255 - s->w;
	eb32i_insert(root, &s->node);
	s->tree = root;
	} else {
	s->tree = NULL;
	}
	}

	static inline void dequeue_srv(struct srv *s) {
	eb32_delete(&s->node);
	}

	/* queues a server into the correct tree depending on ->next */
	void put_srv(struct srv *s) {
	if (s->w <= 0 \|\|
	s->next >= 2sw \|\| / delay everything which does not fit into the window */
	s->next >= sw+nsw) { /* and everything which does not fit into the theorical new window */
	/* put into next tree */
	s->next -= sw; // readjust next in case we could finally take this back to current.
	queue_by_weight_0(next_tree, s);
	} else { /* FIXME: sw can be smaller than s->rem! */
	//s->node.key = sw * s->next + s->rem - s->w;
	//s->node.key = 65536 * s->next + s->rem - s->w;
	//s->node.key = 256*s->next + (s->rem / 256);
	//s->node.key = 256*s->next + ((s->rem - s->w) / 256);
	s->node.key = 16*s->next + ((s->rem - s->w) / 4096);
	eb32i_insert(&tree_0, &s->node);
	s->tree = &tree_0;
	}
	}

	/* prepares a server when extracting it from the init tree */
	static inline void get_srv_init(struct srv *s) {
	s->next = s->rem = 0;
	}

	/* prepares a server when extracting it from the next tree */
	static inline void get_srv_next(struct srv *s) {
	s->next += sw;
	}

	/* prepares a server when extracting it from the next tree */
	static inline void get_srv_down(struct srv *s) {
	s->next = p;
	}

	/* prepares a server when extracting it from its tree */
	void get_srv(struct srv *s) {
	if (s->tree == init_tree) {
	get_srv_init(s);
	}
	else if (s->tree == next_tree) {
	get_srv_next(s);
	}
	else if (s->tree == NULL) {
	get_srv_down(s);
	}
	}


	/* return next server from the current tree, or a server from the init tree
	* if appropriate. If both trees are empty, return NULL.
	*/
	struct srv *get_next_server() {
	struct eb32_node *node;
	struct srv *s;

	node = eb32_first(&tree_0);
	s = eb32_entry(node, struct srv, node);

	if (!node \|\| s->next > p) {
	/* either we have no server left, or we have a hole */
	struct eb32_node *node2;
	node2 = eb32_first(init_tree);
	if (node2) {
	node = node2;
	s = eb32_entry(node, struct srv, node);
	get_srv_init(s);
	if (s->w == 0)
	node = NULL;
	}
	}
	if (node)
	return s;
	else
	return NULL;
	}

	void update_position(struct srv *s) {
	//if (s->tree == init_tree) {
	if (!s->next) {
	// first time ever for this server
	s->last = p;
	s->next = p + nsw / s->w;
	s->rem += nsw % s->w;

	if (s->rem >= s->w) {
	s->rem -= s->w;
	s->next++;
	}
	} else {
	s->last = s->next; // or p ?
	//s->next += sw / s->w;
	//s->rem += sw % s->w;
	s->next += nsw / s->w;
	s->rem += nsw % s->w;

	if (s->rem >= s->w) {
	s->rem -= s->w;
	s->next++;
	}
	}
	}


	/* switches trees init_tree and next_tree. init_tree should be empty when
	* this happens, and next_tree filled with servers sorted by weights.
	*/
	void switch_trees() {
	struct eb_root *swap;
	swap = init_tree;
	init_tree = next_tree;
	next_tree = swap;
	sw = nsw;
	p = sw;
	}

	main(int argc, char **argv) {
	int conns;
	int i;

	struct srv *s;

	argc--; argv++;
	nsrv = argc;

	if (!nsrv)
	exit(1);

	srv = (struct srv *)calloc(nsrv, sizeof(struct srv));

	sw = 0;
	for (i = 0; i < nsrv; i++) {
	s = &srv[i];
	s->num = i;
	s->w = atol(argv[i]);
	sw += s->w;
	}

	nsw = sw;

	init_tree = &tree_1;
	next_tree = &tree_2;

	/* and insert all the servers in the PREV tree */
	/* note that it is required to insert them according to
	* the reverse order of their weights.
	*/
	printf("---------------:");
	for (i = 0; i < nsrv; i++) {
	s = &srv[i];
	queue_by_weight_0(init_tree, s);
	printf("%2d", s->w);
	}
	printf("\n");

	p = sw; // time base of current tree
	conns = 0;
	while (1) {
	struct eb32_node *node;

	printf("%08d\|%06d: ", conns, p);

	/* if we have en empty tree, let's first try to collect weights
	* which might have changed.
	*/
	if (!sw) {
	if (nsw) {
	sw = nsw;
	p = sw;
	/* do not switch trees, otherwise new servers (from init)
	* would end up in next.
	*/
	//switch_trees();
	//printf("bla\n");
	}
	else
	goto next_iteration;
	}

	s = get_next_server();
	if (!s) {
	printf("----------- switch (empty) -- sw=%d -> %d ---------\n", sw, nsw);
	switch_trees();
	s = get_next_server();
	printf("%08d\|%06d: ", conns, p);

	if (!s)
	goto next_iteration;
	}
	else if (s->next >= 2*sw) {
	printf("ARGGGGG! s[%d].next=%d, max=%d\n", s->num, s->next, 2*sw-1);
	}

	/* now we have THE server we want to put at this position */
	for (i = 0; i < s->num; i++) {
	if (srv[i].w > 0)
	printf(". ");
	else
	printf("_ ");
	}
	printf("# ");
	for (i = s->num + 1; i < nsrv; i++) {
	if (srv[i].w > 0)
	printf(". ");
	else
	printf("_ ");
	}
	printf(" : ");

	printf("s=%02d v=%04d w=%03d n=%03d r=%03d ",
	s->num, s->node.key, s->w, s->next, s->rem);

	update_position(s);
	printf(" \| next=%03d, rem=%03d ", s->next, s->rem);

	if (s->next >= sw * 2) {
	dequeue_srv(s);
	//queue_by_weight(next_tree, s);
	put_srv(s);
	printf(" => next (w=%d, n=%d) ", s->w, s->next);
	}
	else {
	printf(" => curr ");

	//s->node.key = s->next;
	/* we want to ensure that in case of conflicts, servers with
	* the highest weights will get served first. Also, we still
	* have the remainder to see where the entry expected to be
	* inserted.
	*/
	//s->node.key = 256 * s->next + 255 - s->w;
	//s->node.key = sw * s->next + sw / s->w;
	//s->node.key = sw * s->next + s->rem; /// seems best (check with filltab15) !

	//s->node.key = (2 * sw * s->next) + s->rem + sw / s->w;

	/* FIXME: must be optimized */
	dequeue_srv(s);
	put_srv(s);
	//eb32i_insert(&tree_0, &s->node);
	//s->tree = &tree_0;
	}

	next_iteration:
	p++;
	conns++;
	if (/conns == 30/ //random()%1000 == 0//) {
	int w = /20///random()%10000//;
	int num = /1///random()%nsrv//;
	struct srv *s = &srv[num];

	nsw = nsw - s->w + w;
	//sw=nsw;

	if (s->tree == init_tree) {
	printf(" -- chgwght1(%d): %d->%d, n=%d --", s->num, s->w, w, s->next);
	printf("(init)");
	s->w = w;
	dequeue_srv(s);
	queue_by_weight_0(s->tree, s);
	}
	else if (s->tree == NULL) {
	printf(" -- chgwght2(%d): %d->%d, n=%d --", s->num, s->w, w, s->next);
	printf("(down)");
	s->w = w;
	dequeue_srv(s);
	//queue_by_weight_0(init_tree, s);
	get_srv(s);
	s->next = p + (nsw + sw - p) / s->w;
	put_srv(s);
	}
	else {
	int oldnext;

	/* the server is either active or in the next queue */
	get_srv(s);
	printf(" -- chgwght3(%d): %d->%d, n=%d, sw=%d, nsw=%d --", s->num, s->w, w, s->next, sw, nsw);

	oldnext = s->next;
	s->w = w;

	/* we must measure how far we are from the end of the current window
	* and try to fit their as many entries as should theorically be.
	*/

	//s->w = s->w * (2*sw - p) / sw;
	if (s->w > 0) {
	int step = (nsw /+ sw - p/) / s->w;
	s->next = s->last + step;
	s->rem = 0;
	if (s->next > oldnext) {
	s->next = oldnext;
	printf(" aaaaaaa ");
	}

	if (s->next < p + 2) {
	s->next = p + step;
	printf(" bbbbbb ");
	}
	} else {
	printf(" push -- ");
	/* push it into the next tree */
	s->w = 0;
	s->next = p + sw;
	}


	dequeue_srv(s);
	printf(" n=%d", s->next);
	put_srv(s);
	}
	}

	printf("\n");

	if (0 && conns % 50000 == 0) {
	printf("-------- %-5d : changing all weights ----\n", conns);

	for (i = 0; i < nsrv; i++) {
	int w = i + 1;
	s = &srv[i];
	nsw = nsw - s->w + w;
	s->w = w;
	dequeue_srv(s);
	queue_by_weight_0(next_tree, s); // or init_tree ?
	}
	}

	}
	}