diff --git a/src/lb_chash.c b/src/lb_chash.c
index e3bf65d..7e188ac 100644
--- a/src/lb_chash.c
+++ b/src/lb_chash.c
@@ -66,6 +66,8 @@
  * as many times as its weight indicates it. If it's there too often, we remove
  * the last occurrences. If it's not there enough, we add more occurrences. To
  * remove a server from the tree, normally call this with eweight=0.
+ *
+ * The server's lock and the lbprm's lock must be held.
  */
 static inline void chash_queue_dequeue_srv(struct server *s)
 {
@@ -112,6 +114,8 @@
  * It is not important whether the server was already down or not. It is not
  * important either that the new state is completely down (the caller may not
  * know all the variables of a server's state).
+ *
+ * The server's lock must be held. The lbprm lock will be used.
  */
 static void chash_set_server_status_down(struct server *srv)
 {
@@ -120,6 +124,8 @@
 	if (!srv_lb_status_changed(srv))
                return;
 
+	HA_SPIN_LOCK(LBPRM_LOCK, &p->lbprm.lock);
+
 	if (srv_willbe_usable(srv))
 		goto out_update_state;
 
@@ -155,6 +161,8 @@
 	update_backend_weight(p);
  out_update_state:
 	srv_lb_commit_status(srv);
+
+	HA_SPIN_UNLOCK(LBPRM_LOCK, &p->lbprm.lock);
 }
 
 /* This function updates the server trees according to server <srv>'s new
@@ -163,6 +171,8 @@
  * important either that the new state is completely UP (the caller may not
  * know all the variables of a server's state). This function will not change
  * the weight of a server which was already up.
+ *
+ * The server's lock must be held. The lbprm lock will be used.
  */
 static void chash_set_server_status_up(struct server *srv)
 {
@@ -171,6 +181,8 @@
 	if (!srv_lb_status_changed(srv))
                return;
 
+	HA_SPIN_LOCK(LBPRM_LOCK, &p->lbprm.lock);
+
 	if (!srv_willbe_usable(srv))
 		goto out_update_state;
 
@@ -211,10 +223,14 @@
 	update_backend_weight(p);
  out_update_state:
 	srv_lb_commit_status(srv);
+
+	HA_SPIN_UNLOCK(LBPRM_LOCK, &p->lbprm.lock);
 }
 
 /* This function must be called after an update to server <srv>'s effective
  * weight. It may be called after a state change too.
+ *
+ * The server's lock must be held. The lbprm lock may be used.
  */
 static void chash_update_server_weight(struct server *srv)
 {
@@ -248,6 +264,8 @@
 		return;
 	}
 
+	HA_SPIN_LOCK(LBPRM_LOCK, &p->lbprm.lock);
+
 	/* only adjust the server's presence in the tree */
 	chash_queue_dequeue_srv(srv);
 
@@ -258,6 +276,8 @@
 
 	update_backend_weight(p);
 	srv_lb_commit_status(srv);
+
+	HA_SPIN_UNLOCK(LBPRM_LOCK, &p->lbprm.lock);
 }
 
 /*
@@ -303,21 +323,29 @@
 	unsigned int dn, dp;
 	int loop;
 
+	HA_SPIN_LOCK(LBPRM_LOCK, &p->lbprm.lock);
+
 	if (p->srv_act)
 		root = &p->lbprm.chash.act;
-	else if (p->lbprm.fbck)
-		return p->lbprm.fbck;
+	else if (p->lbprm.fbck) {
+		nsrv = p->lbprm.fbck;
+		goto out;
+	}
 	else if (p->srv_bck)
 		root = &p->lbprm.chash.bck;
-	else
-		return NULL;
+	else {
+		nsrv = NULL;
+		goto out;
+	}
 
 	/* find the node after and the node before */
 	next = eb32_lookup_ge(root, hash);
 	if (!next)
 		next = eb32_first(root);
-	if (!next)
-		return NULL; /* tree is empty */
+	if (!next) {
+		nsrv = NULL; /* tree is empty */
+		goto out;
+	}
 
 	prev = eb32_prev(next);
 	if (!prev)
@@ -349,6 +377,8 @@
 		nsrv = eb32_entry(next, struct tree_occ, node)->server;
 	}
 
+ out:
+	HA_SPIN_UNLOCK(LBPRM_LOCK, &p->lbprm.lock);
 	return nsrv;
 }
 
diff --git a/src/lb_fas.c b/src/lb_fas.c
index d301143..69b85d7 100644
--- a/src/lb_fas.c
+++ b/src/lb_fas.c
@@ -31,13 +31,18 @@
 /* Remove a server from a tree. It must have previously been dequeued. This
  * function is meant to be called when a server is going down or has its
  * weight disabled.
+ *
+ * The server's lock and the lbprm's lock must be held.
  */
 static inline void fas_remove_from_tree(struct server *s)
 {
 	s->lb_tree = NULL;
 }
 
-/* simply removes a server from a tree */
+/* simply removes a server from a tree.
+ *
+ * The server's lock and the lbprm's lock must be held.
+ */
 static inline void fas_dequeue_srv(struct server *s)
 {
 	eb32_delete(&s->lb_node);
@@ -48,6 +53,8 @@
  * available server in declaration order (or ID order) until its maxconn is
  * reached. It is important to understand that the server weight is not used
  * here.
+ *
+ * The server's lock and the lbprm's lock must be held.
  */
 static inline void fas_queue_srv(struct server *s)
 {
@@ -58,6 +65,8 @@
 /* Re-position the server in the FS tree after it has been assigned one
  * connection or after it has released one. Note that it is possible that
  * the server has been moved out of the tree due to failed health-checks.
+ *
+ * The server's lock must be held. The lbprm's lock will be used.
  */
 static void fas_srv_reposition(struct server *s)
 {
@@ -75,6 +84,8 @@
  * It is not important whether the server was already down or not. It is not
  * important either that the new state is completely down (the caller may not
  * know all the variables of a server's state).
+ *
+ * The server's lock must be held. The lbprm's lock will be used.
  */
 static void fas_set_server_status_down(struct server *srv)
 {
@@ -86,6 +97,8 @@
 	if (srv_willbe_usable(srv))
 		goto out_update_state;
 
+	HA_SPIN_LOCK(LBPRM_LOCK, &p->lbprm.lock);
+
 	if (!srv_currently_usable(srv))
 		/* server was already down */
 		goto out_update_backend;
@@ -117,6 +130,8 @@
  out_update_backend:
 	/* check/update tot_used, tot_weight */
 	update_backend_weight(p);
+	HA_SPIN_UNLOCK(LBPRM_LOCK, &p->lbprm.lock);
+
  out_update_state:
 	srv_lb_commit_status(srv);
 }
@@ -127,6 +142,8 @@
  * important either that the new state is completely UP (the caller may not
  * know all the variables of a server's state). This function will not change
  * the weight of a server which was already up.
+ *
+ * The server's lock must be held. The lbprm's lock will be used.
  */
 static void fas_set_server_status_up(struct server *srv)
 {
@@ -138,6 +155,8 @@
 	if (!srv_willbe_usable(srv))
 		goto out_update_state;
 
+	HA_SPIN_LOCK(LBPRM_LOCK, &p->lbprm.lock);
+
 	if (srv_currently_usable(srv))
 		/* server was already up */
 		goto out_update_backend;
@@ -175,12 +194,16 @@
  out_update_backend:
 	/* check/update tot_used, tot_weight */
 	update_backend_weight(p);
+	HA_SPIN_UNLOCK(LBPRM_LOCK, &p->lbprm.lock);
+
  out_update_state:
 	srv_lb_commit_status(srv);
 }
 
 /* This function must be called after an update to server <srv>'s effective
  * weight. It may be called after a state change too.
+ *
+ * The server's lock must be held. The lbprm's lock will be used.
  */
 static void fas_update_server_weight(struct server *srv)
 {
@@ -214,6 +237,8 @@
 		return;
 	}
 
+	HA_SPIN_LOCK(LBPRM_LOCK, &p->lbprm.lock);
+
 	if (srv->lb_tree)
 		fas_dequeue_srv(srv);
 
@@ -228,6 +253,8 @@
 	fas_queue_srv(srv);
 
 	update_backend_weight(p);
+	HA_SPIN_UNLOCK(LBPRM_LOCK, &p->lbprm.lock);
+
 	srv_lb_commit_status(srv);
 }
 
@@ -269,6 +296,8 @@
 
 /* Return next server from the FS tree in backend <p>. If the tree is empty,
  * return NULL. Saturated servers are skipped.
+ *
+ * The server's lock must be held. The lbprm's lock will be used.
  */
 struct server *fas_get_next_server(struct proxy *p, struct server *srvtoavoid)
 {
diff --git a/src/lb_fwlc.c b/src/lb_fwlc.c
index fd9b437..ca42221 100644
--- a/src/lb_fwlc.c
+++ b/src/lb_fwlc.c
@@ -25,13 +25,18 @@
 /* Remove a server from a tree. It must have previously been dequeued. This
  * function is meant to be called when a server is going down or has its
  * weight disabled.
+ *
+ * The server's lock and the lbprm's lock must be held.
  */
 static inline void fwlc_remove_from_tree(struct server *s)
 {
 	s->lb_tree = NULL;
 }
 
-/* simply removes a server from a tree */
+/* simply removes a server from a tree.
+ *
+ * The server's lock and the lbprm's lock must be held.
+ */
 static inline void fwlc_dequeue_srv(struct server *s)
 {
 	eb32_delete(&s->lb_node);
@@ -40,6 +45,8 @@
 /* Queue a server in its associated tree, assuming the weight is >0.
  * Servers are sorted by #conns/weight. To ensure maximum accuracy,
  * we use #conns*SRV_EWGHT_MAX/eweight as the sorting key.
+ *
+ * The server's lock and the lbprm's lock must be held.
  */
 static inline void fwlc_queue_srv(struct server *s)
 {
@@ -50,6 +57,8 @@
 /* Re-position the server in the FWLC tree after it has been assigned one
  * connection or after it has released one. Note that it is possible that
  * the server has been moved out of the tree due to failed health-checks.
+ *
+ * The server's lock must be held. The lbprm's lock will be used.
  */
 static void fwlc_srv_reposition(struct server *s)
 {
@@ -67,6 +76,8 @@
  * It is not important whether the server was already down or not. It is not
  * important either that the new state is completely down (the caller may not
  * know all the variables of a server's state).
+ *
+ * The server's lock must be held. The lbprm's lock will be used.
  */
 static void fwlc_set_server_status_down(struct server *srv)
 {
@@ -77,6 +88,8 @@
 
 	if (srv_willbe_usable(srv))
 		goto out_update_state;
+	HA_SPIN_LOCK(LBPRM_LOCK, &p->lbprm.lock);
+
 
 	if (!srv_currently_usable(srv))
 		/* server was already down */
@@ -109,6 +122,8 @@
 out_update_backend:
 	/* check/update tot_used, tot_weight */
 	update_backend_weight(p);
+	HA_SPIN_UNLOCK(LBPRM_LOCK, &p->lbprm.lock);
+
  out_update_state:
 	srv_lb_commit_status(srv);
 }
@@ -119,6 +134,8 @@
  * important either that the new state is completely UP (the caller may not
  * know all the variables of a server's state). This function will not change
  * the weight of a server which was already up.
+ *
+ * The server's lock must be held. The lbprm's lock will be used.
  */
 static void fwlc_set_server_status_up(struct server *srv)
 {
@@ -130,6 +147,8 @@
 	if (!srv_willbe_usable(srv))
 		goto out_update_state;
 
+	HA_SPIN_LOCK(LBPRM_LOCK, &p->lbprm.lock);
+
 	if (srv_currently_usable(srv))
 		/* server was already up */
 		goto out_update_backend;
@@ -167,12 +186,16 @@
  out_update_backend:
 	/* check/update tot_used, tot_weight */
 	update_backend_weight(p);
+	HA_SPIN_UNLOCK(LBPRM_LOCK, &p->lbprm.lock);
+
  out_update_state:
 	srv_lb_commit_status(srv);
 }
 
 /* This function must be called after an update to server <srv>'s effective
  * weight. It may be called after a state change too.
+ *
+ * The server's lock must be held. The lbprm's lock will be used.
  */
 static void fwlc_update_server_weight(struct server *srv)
 {
@@ -206,6 +229,8 @@
 		return;
 	}
 
+	HA_SPIN_LOCK(LBPRM_LOCK, &p->lbprm.lock);
+
 	if (srv->lb_tree)
 		fwlc_dequeue_srv(srv);
 
@@ -220,6 +245,8 @@
 	fwlc_queue_srv(srv);
 
 	update_backend_weight(p);
+	HA_SPIN_UNLOCK(LBPRM_LOCK, &p->lbprm.lock);
+
 	srv_lb_commit_status(srv);
 }
 
@@ -261,6 +288,8 @@
 
 /* Return next server from the FWLC tree in backend <p>. If the tree is empty,
  * return NULL. Saturated servers are skipped.
+ *
+ * The server's lock must be held. The lbprm's lock will be used.
  */
 struct server *fwlc_get_next_server(struct proxy *p, struct server *srvtoavoid)
 {
diff --git a/src/lb_fwrr.c b/src/lb_fwrr.c
index cba7db5..73a140b 100644
--- a/src/lb_fwrr.c
+++ b/src/lb_fwrr.c
@@ -33,6 +33,8 @@
  * It is not important whether the server was already down or not. It is not
  * important either that the new state is completely down (the caller may not
  * know all the variables of a server's state).
+ *
+ * The server's lock must be held. The lbprm's lock will be used.
  */
 static void fwrr_set_server_status_down(struct server *srv)
 {
@@ -45,6 +47,8 @@
 	if (srv_willbe_usable(srv))
 		goto out_update_state;
 
+	HA_SPIN_LOCK(LBPRM_LOCK, &p->lbprm.lock);
+
 	if (!srv_currently_usable(srv))
 		/* server was already down */
 		goto out_update_backend;
@@ -79,6 +83,8 @@
 out_update_backend:
 	/* check/update tot_used, tot_weight */
 	update_backend_weight(p);
+	HA_SPIN_UNLOCK(LBPRM_LOCK, &p->lbprm.lock);
+
  out_update_state:
 	srv_lb_commit_status(srv);
 }
@@ -89,6 +95,8 @@
  * important either that the new state is completely UP (the caller may not
  * know all the variables of a server's state). This function will not change
  * the weight of a server which was already up.
+ *
+ * The server's lock must be held. The lbprm's lock will be used.
  */
 static void fwrr_set_server_status_up(struct server *srv)
 {
@@ -101,6 +109,8 @@
 	if (!srv_willbe_usable(srv))
 		goto out_update_state;
 
+	HA_SPIN_LOCK(LBPRM_LOCK, &p->lbprm.lock);
+
 	if (srv_currently_usable(srv))
 		/* server was already up */
 		goto out_update_backend;
@@ -141,12 +151,16 @@
 out_update_backend:
 	/* check/update tot_used, tot_weight */
 	update_backend_weight(p);
+	HA_SPIN_UNLOCK(LBPRM_LOCK, &p->lbprm.lock);
+
  out_update_state:
 	srv_lb_commit_status(srv);
 }
 
 /* This function must be called after an update to server <srv>'s effective
  * weight. It may be called after a state change too.
+ *
+ * The server's lock must be held. The lbprm's lock will be used.
  */
 static void fwrr_update_server_weight(struct server *srv)
 {
@@ -181,6 +195,8 @@
 		return;
 	}
 
+	HA_SPIN_LOCK(LBPRM_LOCK, &p->lbprm.lock);
+
 	grp = (srv->flags & SRV_F_BACKUP) ? &p->lbprm.fwrr.bck : &p->lbprm.fwrr.act;
 	grp->next_weight = grp->next_weight - srv->cur_eweight + srv->next_eweight;
 
@@ -227,12 +243,16 @@
 	}
 
 	update_backend_weight(p);
+	HA_SPIN_UNLOCK(LBPRM_LOCK, &p->lbprm.lock);
+
 	srv_lb_commit_status(srv);
 }
 
 /* Remove a server from a tree. It must have previously been dequeued. This
  * function is meant to be called when a server is going down or has its
  * weight disabled.
+ *
+ * The server's lock and the lbprm's lock must be held.
  */
 static inline void fwrr_remove_from_tree(struct server *s)
 {
@@ -242,6 +262,8 @@
 /* Queue a server in the weight tree <root>, assuming the weight is >0.
  * We want to sort them by inverted weights, because we need to place
  * heavy servers first in order to get a smooth distribution.
+ *
+ * The server's lock and the lbprm's lock must be held.
  */
 static inline void fwrr_queue_by_weight(struct eb_root *root, struct server *s)
 {
@@ -299,7 +321,10 @@
 	}
 }
 
-/* simply removes a server from a weight tree */
+/* simply removes a server from a weight tree.
+ *
+ * The server's lock and the lbprm's lock must be held.
+ */
 static inline void fwrr_dequeue_srv(struct server *s)
 {
 	eb32_delete(&s->lb_node);
@@ -308,6 +333,8 @@
 /* queues a server into the appropriate group and tree depending on its
  * backup status, and ->npos. If the server is disabled, simply assign
  * it to the NULL tree.
+ *
+ * The server's lock and the lbprm's lock must be held.
  */
 static void fwrr_queue_srv(struct server *s)
 {
@@ -346,13 +373,19 @@
 	}
 }
 
-/* prepares a server when extracting it from the "init" tree */
+/* prepares a server when extracting it from the "init" tree.
+ *
+ * The server's lock and the lbprm's lock must be held.
+ */
 static inline void fwrr_get_srv_init(struct server *s)
 {
 	s->npos = s->rweight = 0;
 }
 
-/* prepares a server when extracting it from the "next" tree */
+/* prepares a server when extracting it from the "next" tree.
+ *
+ * The server's lock and the lbprm's lock must be held.
+ */
 static inline void fwrr_get_srv_next(struct server *s)
 {
 	struct fwrr_group *grp = (s->flags & SRV_F_BACKUP) ?
@@ -362,7 +395,10 @@
 	HA_ATOMIC_ADD(&s->npos, grp->curr_weight);
 }
 
-/* prepares a server when it was marked down */
+/* prepares a server when it was marked down.
+ *
+ * The server's lock and the lbprm's lock must be held.
+ */
 static inline void fwrr_get_srv_down(struct server *s)
 {
 	struct fwrr_group *grp = (s->flags & SRV_F_BACKUP) ?
@@ -372,7 +408,10 @@
 	s->npos = grp->curr_pos;
 }
 
-/* prepares a server when extracting it from its tree */
+/* prepares a server when extracting it from its tree.
+ *
+ * The server's lock and the lbprm's lock must be held.
+ */
 static void fwrr_get_srv(struct server *s)
 {
 	struct proxy *p = s->proxy;
@@ -393,6 +432,8 @@
 
 /* switches trees "init" and "next" for FWRR group <grp>. "init" should be empty
  * when this happens, and "next" filled with servers sorted by weights.
+ *
+ * The lbprm's lock must be held.
  */
 static inline void fwrr_switch_trees(struct fwrr_group *grp)
 {
@@ -406,6 +447,8 @@
 
 /* return next server from the current tree in FWRR group <grp>, or a server
  * from the "init" tree if appropriate. If both trees are empty, return NULL.
+ *
+ * The lbprm's lock must be held.
  */
 static struct server *fwrr_get_server_from_group(struct fwrr_group *grp)
 {
@@ -435,7 +478,9 @@
 
 /* Computes next position of server <s> in the group. It is mandatory for <s>
  * to have a non-zero, positive eweight.
-*/
+ *
+ * The server's lock and the lbprm's lock must be held.
+ */
 static inline void fwrr_update_position(struct fwrr_group *grp, struct server *s)
 {
 	if (!s->npos) {
@@ -463,6 +508,8 @@
 /* Return next server from the current tree in backend <p>, or a server from
  * the init tree if appropriate. If both trees are empty, return NULL.
  * Saturated servers are skipped and requeued.
+ *
+ * The server's lock must be held. The lbprm's lock will be used.
  */
 struct server *fwrr_get_next_server(struct proxy *p, struct server *srvtoavoid)
 {
diff --git a/src/lb_map.c b/src/lb_map.c
index a1e1d34..54569b0 100644
--- a/src/lb_map.c
+++ b/src/lb_map.c
@@ -24,7 +24,10 @@
 #include <proto/proto_tcp.h>
 #include <proto/queue.h>
 
-/* this function updates the map according to server <srv>'s new state */
+/* this function updates the map according to server <srv>'s new state.
+ *
+ * The server's lock must be held. The lbprm's lock will be used.
+ */
 static void map_set_server_status_down(struct server *srv)
 {
 	struct proxy *p = srv->proxy;
@@ -36,14 +39,19 @@
 		goto out_update_state;
 
 	/* FIXME: could be optimized since we know what changed */
+	HA_SPIN_LOCK(LBPRM_LOCK, &p->lbprm.lock);
 	recount_servers(p);
 	update_backend_weight(p);
 	recalc_server_map(p);
+	HA_SPIN_UNLOCK(LBPRM_LOCK, &p->lbprm.lock);
  out_update_state:
 	srv_lb_commit_status(srv);
 }
 
-/* This function updates the map according to server <srv>'s new state */
+/* This function updates the map according to server <srv>'s new state.
+ *
+ * The server's lock must be held. The lbprm's lock will be used.
+ */
 static void map_set_server_status_up(struct server *srv)
 {
 	struct proxy *p = srv->proxy;
@@ -55,9 +63,11 @@
 		goto out_update_state;
 
 	/* FIXME: could be optimized since we know what changed */
+	HA_SPIN_LOCK(LBPRM_LOCK, &p->lbprm.lock);
 	recount_servers(p);
 	update_backend_weight(p);
 	recalc_server_map(p);
+	HA_SPIN_UNLOCK(LBPRM_LOCK, &p->lbprm.lock);
  out_update_state:
 	srv_lb_commit_status(srv);
 }
@@ -66,6 +76,8 @@
  * px->lbprm.tot_wact, tot_wbck, tot_used, tot_weight, so it must be
  * called after recount_servers(). It also expects px->lbprm.map.srv
  * to be allocated with the largest size needed. It updates tot_weight.
+ *
+ * The lbprm's lock must be held.
  */
 void recalc_server_map(struct proxy *px)
 {
@@ -202,6 +214,8 @@
  * the proxy <px> following the round-robin method.
  * If any server is found, it will be returned and px->lbprm.map.rr_idx will be updated
  * to point to the next server. If no valid server is found, NULL is returned.
+ *
+ * The lbprm's lock will be used.
  */
 struct server *map_get_server_rr(struct proxy *px, struct server *srvtoavoid)
 {
@@ -250,12 +264,18 @@
  * pointed to by the result of a modulo operation on <hash>. The server map may
  * be recomputed if required before being looked up. If any server is found, it
  * will be returned.  If no valid server is found, NULL is returned.
+ *
+ * The lbprm's lock will be used.
  */
 struct server *map_get_server_hash(struct proxy *px, unsigned int hash)
 {
-	if (px->lbprm.tot_weight == 0)
-		return NULL;
-	return px->lbprm.map.srv[hash % px->lbprm.tot_weight];
+	struct server *srv = NULL;
+
+	HA_SPIN_LOCK(LBPRM_LOCK, &px->lbprm.lock);
+	if (px->lbprm.tot_weight)
+		srv = px->lbprm.map.srv[hash % px->lbprm.tot_weight];
+	HA_SPIN_UNLOCK(LBPRM_LOCK, &px->lbprm.lock);
+	return srv;
 }