Prioritized Accept Queues with Preemption Capability

diff -urN -X dontdiff linux-2.4.9/include/net/sock.h linux-2.4.9-ppaq/include/net/sock.h
@@ -239,6 +239,11 @@
 #define pppoe_relay	proto.pppoe.relay
 #endif
 
+#ifdef CONFIG_PRIO_ACCEPTQ
+/* Priorities range from 0-7 */
+#define MAX_ACCEPTQ_PRIO        7
+#endif
+
 /* This defines a selective acknowledgement block. */
 struct tcp_sack_block {
 	__u32	start_seq;

@@ -409,7 +414,11 @@
 
 	/* FIFO of established children */
 	struct open_request	*accept_queue;
+#ifdef CONFIG_PRIO_ACCEPTQ
+	struct open_request     *accept_queue_tail[MAX_ACCEPTQ_PRIO];
+#else
 	struct open_request	*accept_queue_tail;
+#endif
 
 	int			write_pending;	/* A write to socket waits to start. */
 

diff -urN -X dontdiff linux-2.4.9/include/net/tcp.h linux-2.4.9-ppaq/include/net/tcp.h
@@ -519,6 +519,9 @@
 		struct tcp_v6_open_req v6_req;
 #endif
 	} af;
+#ifdef CONFIG_PRIO_ACCEPTQ
+	int acceptq_prio;
+#endif
 };
 
 /* SLAB cache for open requests. */

@@ -1572,10 +1575,33 @@
 					 struct sock *child)
 {
 	struct tcp_opt *tp = &sk->tp_pinfo.af_tcp;
+#ifdef CONFIG_PRIO_ACCEPTQ
+	int prio = req->acceptq_prio;
+	int prev_prio;
+#endif
 
 	req->sk = child;
 	tcp_acceptq_added(sk);
 
+#ifdef CONFIG_PRIO_ACCEPTQ
+	if (!tp->accept_queue_tail[prio]) {
+		for (prev_prio = prio - 1; prev_prio >= 0; prev_prio--)
+			if (tp->accept_queue_tail[prev_prio])
+				break;
+		tp->accept_queue_tail[prio] = req;
+		if (prev_prio >= 0) {
+			req->dl_next = tp->accept_queue_tail[prev_prio]->dl_next;
+			tp->accept_queue_tail[prev_prio]->dl_next = req; 
+		} else {
+			req->dl_next = tp->accept_queue;
+			tp->accept_queue = req;
+		}
+	} else {
+		req->dl_next = tp->accept_queue_tail[prio]->dl_next;
+		tp->accept_queue_tail[prio]->dl_next = req;
+		tp->accept_queue_tail[prio] = req;
+	}
+#else
 	if (!tp->accept_queue_tail) {
 		tp->accept_queue = req;
 	} else {

@@ -1583,6 +1609,7 @@
 	}
 	tp->accept_queue_tail = req;
 	req->dl_next = NULL;
+#endif
 }
 
 struct tcp_listen_opt

@@ -1649,6 +1676,10 @@
 					struct tcp_opt *tp,
 					struct sk_buff *skb)
 {
+#ifdef CONFIG_PRIO_ACCEPTQ
+	int nfmark = (int)skb->nfmark;
+#endif
+
 	req->rcv_wnd = 0;		/* So that tcp_send_synack() knows! */
 	req->rcv_isn = TCP_SKB_CB(skb)->seq;
 	req->mss = tp->mss_clamp;

@@ -1660,6 +1691,9 @@
 	req->acked = 0;
 	req->ecn_ok = 0;
 	req->rmt_port = skb->h.th->source;
+#ifdef CONFIG_PRIO_ACCEPTQ
+	req->acceptq_prio = (nfmark < 0) ? 0 : ((nfmark > MAX_ACCEPTQ_PRIO) ? MAX_ACCEPTQ_PRIO : nfmark);
+#endif
 }
 
 #define TCP_MEM_QUANTUM	((int)PAGE_SIZE)

diff -urN -X dontdiff linux-2.4.9/net/ipv4/tcp.c linux-2.4.9-ppaq/net/ipv4/tcp.c
@@ -529,7 +529,12 @@
 
 	sk->max_ack_backlog = 0;
 	sk->ack_backlog = 0;
+#ifdef CONFIG_PRIO_ACCEPTQ
+	tp->accept_queue = NULL;
+	memset(tp->accept_queue_tail, 0, (sizeof(struct open_request *) * (MAX_ACCEPTQ_PRIO + 1)));
+#else
 	tp->accept_queue = tp->accept_queue_tail = NULL;
+#endif
 	tp->syn_wait_lock = RW_LOCK_UNLOCKED;
 	tcp_delack_init(tp);
 

@@ -588,7 +593,12 @@
 	write_lock_bh(&tp->syn_wait_lock);
 	tp->listen_opt =NULL;
 	write_unlock_bh(&tp->syn_wait_lock);
+#ifdef CONFIG_PRIO_ACCEPTQ
+	tp->accept_queue = NULL;
+	memset(tp->accept_queue_tail, 0, (sizeof(struct open_request *) * (MAX_ACCEPTQ_PRIO + 1)));
+#else
 	tp->accept_queue = tp->accept_queue_tail = NULL;
+#endif
 
 	if (lopt->qlen) {
 		for (i=0; i<TCP_SYNQ_HSIZE; i++) {

@@ -2109,6 +2119,9 @@
 	struct open_request *req;
 	struct sock *newsk;
 	int error;
+#ifdef CONFIG_PRIO_ACCEPTQ
+	int prio;
+#endif
 
 	lock_sock(sk); 
 

@@ -2134,8 +2147,17 @@
 	}
 
 	req = tp->accept_queue;
+#ifdef CONFIG_PRIO_ACCEPTQ
+	tp->accept_queue = req->dl_next;
+	for (prio = 0; prio <= MAX_ACCEPTQ_PRIO; prio++)
+		if (req = tp->accept_queue_tail[prio]) {
+			tp->accept_queue_tail[prio] = NULL;
+			break;
+		}
+#else
 	if ((tp->accept_queue = req->dl_next) = NULL)
 		tp->accept_queue_tail = NULL;
+#endif
 
  	newsk = req->sk;
 	tcp_acceptq_removed(sk);

137 lines not on this page · raw message

diff -urN -X dontdiff linux-2.4.9/net/ipv4/tcp_minisocks.c linux-2.4.9-ppaq/net/ipv4/tcp_minisocks.c
@@ -734,7 +734,12 @@
 		newtp->num_sacks = 0;
 		newtp->urg_data = 0;
 		newtp->listen_opt = NULL;
+#ifdef CONFIG_PRIO_ACCEPTQ
+		newtp->accept_queue = NULL;
+		memset(newtp->accept_queue_tail, 0, (sizeof(struct open_request *) * (MAX_ACCEPTQ_PRIO + 1)));
+#else
 		newtp->accept_queue = newtp->accept_queue_tail = NULL;
+#endif
 		/* Deinitialize syn_wait_lock to trap illegal accesses. */
 		memset(&newtp->syn_wait_lock, 0, sizeof(newtp->syn_wait_lock));
 

@@ -802,6 +807,9 @@
 	int paws_reject = 0;
 	struct tcp_opt ttp;
 	struct sock *child;
+#ifdef CONFIG_PRIO_ACCEPTQ
+	struct open_request *r1, *r2;
+#endif
 
 	ttp.saw_tstamp = 0;
 	if (th->doff > (sizeof(struct tcphdr)>>2)) {

@@ -913,10 +921,24 @@
 	 * ESTABLISHED STATE. If it will be dropped after
 	 * socket is created, wait for troubles.
 	 */
+#ifdef CONFIG_PRIO_ACCEPTQ
+	r1 = *prev;
+#endif
 	child = tp->af_specific->syn_recv_sock(sk, skb, req, NULL);
 	if (child = NULL)
 		goto listen_overflow;
+#ifdef CONFIG_PRIO_ACCEPTQ
+	r2 = *prev;
 
+	/* With Prioritized Accept Queues, it is possible that prev pointer can 
+	 * change in the above call to syn_recv_sock(). This can happen if an 
+	 * openreq is preempted and moved from acceptq to syn table and it 
+	 * hashes to the same bucket as 'req' and 'req' is the first entry in 
+	 * the hash bucket. If so, prev needs to be updated.
+	 */ 
+	if ((req = r1) && (r1 != r2))
+		prev = &r2->dl_next;
+#endif
 	tcp_synq_unlink(tp, req, prev);
 	tcp_synq_removed(sk, req);
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++