From 6a3499eccd00dcece97c9a970f264ad0aacc6e5a Mon Sep 17 00:00:00 2001
From: des <des@d4fa192b-c00b-0410-8231-f00ffab90ce4>
Date: Fri, 20 Jul 2007 10:23:12 +0000
Subject: [PATCH] Store stevedores in a circular list.  The head pointer keeps
 moving from one stevedore to the next.  The LRU code is invoked as soon as
 any of the stevedores fills up.

This algorithm is far from ideal, and will not work well with differently
sized stevedores, but it has the advantage of being simple and lock-free.


git-svn-id: svn+ssh://projects.linpro.no/svn/varnish/trunk@1734 d4fa192b-c00b-0410-8231-f00ffab90ce4
---
 varnish-cache/bin/varnishd/stevedore.c | 82 ++++++++++++++------------
 varnish-cache/bin/varnishd/stevedore.h |  4 +-
 2 files changed, 47 insertions(+), 39 deletions(-)

diff --git a/varnish-cache/bin/varnishd/stevedore.c b/varnish-cache/bin/varnishd/stevedore.c
index b018e3f1..79352dfa 100644
--- a/varnish-cache/bin/varnishd/stevedore.c
+++ b/varnish-cache/bin/varnishd/stevedore.c
@@ -36,48 +36,42 @@
 #include "heritage.h"
 #include "stevedore.h"
 
+/*
+ * Stevedores are kept in a circular list with the head pointer
+ * continuously moving from one element to the next.
+ */
+
 extern struct stevedore sma_stevedore;
 extern struct stevedore smf_stevedore;
 
-static TAILQ_HEAD(stevedore_head, stevedore) stevedores;
+static struct stevedore * volatile stevedores;
 
 struct storage *
 STV_alloc(size_t size)
 {
 	struct storage *st;
-	struct stevedore *stv, *stv_first;
+	struct stevedore *stv;
 
-	/* Simple round robin selecting of a stevedore. */
-	stv_first = TAILQ_FIRST(&stevedores);
-	stv = stv_first;
-	do {
-		AN(stv->alloc);
-		st = stv->alloc(stv, size);
-		TAILQ_REMOVE(&stevedores, stv, stevedore_list);
-		TAILQ_INSERT_TAIL(&stevedores, stv, stevedore_list);
-		if (st != NULL)
-			return (st);
-	} while ((stv = TAILQ_FIRST(&stevedores)) != stv_first);
+	for (;;) {
+		/* pick a stevedore and bump the head along */
+		stv = stevedores = stevedores->next;
 
-	/* No stevedore with enough space is found. Make room in the first
-	 * one in the list, and move it to the end. Ensuring the round-robin.
-	 */
-	stv = TAILQ_FIRST(&stevedores);
-	TAILQ_REMOVE(&stevedores, stv, stevedore_list);
-	TAILQ_INSERT_TAIL(&stevedores, stv, stevedore_list);
-
-	do {
-		if ((st = stv->alloc(stv, size)) == NULL)
-			AN(LRU_DiscardOne());
-	} while (st == NULL);
+		/* try to allocate from it */
+		if ((st = stv->alloc(stv, size)) != NULL) {
+			CHECK_OBJ_NOTNULL(st, STORAGE_MAGIC);
+			return (st);
+		}
 
-	return (st);
+		/* no luck; free some space and keep trying */
+		AN(LRU_DiscardOne());
+	}
 }
 
 void
 STV_trim(struct storage *st, size_t size)
 {
 
+	CHECK_OBJ_NOTNULL(st, STORAGE_MAGIC);
 	AN(st->stevedore);
 	if (st->stevedore->trim)
 		st->stevedore->trim(st, size);
@@ -87,6 +81,7 @@ void
 STV_free(struct storage *st)
 {
 
+	CHECK_OBJ_NOTNULL(st, STORAGE_MAGIC);
 	AN(st->stevedore);
 	AN(st->stevedore->free);
 	st->stevedore->free(st);
@@ -106,7 +101,7 @@ void
 STV_add(const char *spec)
 {
 	const char *p, *q;
-	struct stevedore *stp;
+	struct stevedore *stv;
 
 	p = strchr(spec, ',');
 	if (p == NULL)
@@ -116,29 +111,42 @@ STV_add(const char *spec)
 	xxxassert(p != NULL);
 	xxxassert(q != NULL);
 
-	stp = malloc(sizeof *stp);
+	stv = malloc(sizeof *stv);
 
 	if (!cmp_storage(&sma_stevedore, spec, p)) {
-		*stp = sma_stevedore;
+		*stv = sma_stevedore;
 	} else if (!cmp_storage(&smf_stevedore, spec, p)) {
-		*stp = smf_stevedore;
+		*stv = smf_stevedore;
 	} else {
 		fprintf(stderr, "Unknown storage method \"%.*s\"\n",
 		    (int)(p - spec), spec);
 		exit (2);
 	}
-	TAILQ_INSERT_HEAD(&stevedores, stp, stevedore_list);
-	if (stp->init != NULL)
-		stp->init(stp, q);
+	if (stv->init != NULL)
+		stv->init(stv, q);
+
+	if (!stevedores) {
+		fprintf(stderr, "first stevedore\n");
+		stevedores = stv->next = stv->prev = stv;
+	} else {
+		fprintf(stderr, "additional stevedore\n");
+		stv->next = stevedores;
+		stv->prev = stevedores->prev;
+		stv->next->prev = stv;
+		stv->prev->next = stv;
+		stevedores = stv;
+	}
 }
 
 void
 STV_open(void)
 {
-	struct stevedore *st;
+	struct stevedore *stv;
 
-	TAILQ_FOREACH(st, &stevedores, stevedore_list) {
-		if (st->open != NULL)
-			st->open(st);
-	}
+	stv = stevedores;
+	do {
+		if (stv->open != NULL)
+			stv->open(stv);
+		stv = stv->next;
+	} while (stv != stevedores);
 }
diff --git a/varnish-cache/bin/varnishd/stevedore.h b/varnish-cache/bin/varnishd/stevedore.h
index 119036a4..364bcf43 100644
--- a/varnish-cache/bin/varnishd/stevedore.h
+++ b/varnish-cache/bin/varnishd/stevedore.h
@@ -28,7 +28,6 @@
  *
  * $Id$
  */
- 
 
 #include "queue.h"
 
@@ -52,7 +51,8 @@ struct stevedore {
 
 	/* private fields */
 	void			*priv;
-	TAILQ_ENTRY(stevedore)	stevedore_list;
+
+	struct stevedore	*next, *prev;
 };
 
 struct storage *STV_alloc(size_t size);
-- 
2.39.5