patch-2.4.21 linux-2.4.21/net/ipv6/reassembly.c

• Lines: 220
• Date: 2003-06-13 07:51:39.000000000 -0700
• Orig file: linux-2.4.20/net/ipv6/reassembly.c
• Orig date: 2002-11-28 15:53:15.000000000 -0800

diff -urN linux-2.4.20/net/ipv6/reassembly.c linux-2.4.21/net/ipv6/reassembly.c
@@ -22,6 +22,7 @@
  *
  *      Horst von Brand Add missing #include <linux/string.h>
  *	Alexey Kuznetsov	SMP races, threading, cleanup.
+ *	Patrick McHardy		LRU queue of frag heads for evictor.
  */
 #include <linux/config.h>
 #include <linux/errno.h>
@@ -30,11 +31,14 @@
 #include <linux/socket.h>
 #include <linux/sockios.h>
 #include <linux/sched.h>
+#include <linux/list.h>
 #include <linux/net.h>
 #include <linux/netdevice.h>
 #include <linux/in6.h>
 #include <linux/ipv6.h>
 #include <linux/icmpv6.h>
+#include <linux/random.h>
+#include <linux/jhash.h>
 
 #include <net/sock.h>
 #include <net/snmp.h>
@@ -67,6 +71,7 @@
 struct frag_queue
 {
 	struct frag_queue	*next;
+	struct list_head lru_list;		/* lru list member	*/
 
 	__u32			id;		/* fragment id		*/
 	struct in6_addr		saddr;
@@ -95,6 +100,8 @@
 
 static struct frag_queue *ip6_frag_hash[IP6Q_HASHSZ];
 static rwlock_t ip6_frag_lock = RW_LOCK_UNLOCKED;
+static u32 ip6_frag_hash_rnd;
+static LIST_HEAD(ip6_frag_lru_list);
 int ip6_frag_nqueues = 0;
 
 static __inline__ void __fq_unlink(struct frag_queue *fq)
@@ -102,6 +109,7 @@
 	if(fq->next)
 		fq->next->pprev = fq->pprev;
 	*fq->pprev = fq->next;
+	list_del(&fq->lru_list);
 	ip6_frag_nqueues--;
 }
 
@@ -112,16 +120,73 @@
 	write_unlock(&ip6_frag_lock);
 }
 
-static __inline__ unsigned int ip6qhashfn(u32 id, struct in6_addr *saddr,
-					  struct in6_addr *daddr)
+static unsigned int ip6qhashfn(u32 id, struct in6_addr *saddr,
+			       struct in6_addr *daddr)
 {
-	unsigned int h = saddr->s6_addr32[3] ^ daddr->s6_addr32[3] ^ id;
+	u32 a, b, c;
 
-	h ^= (h>>16);
-	h ^= (h>>8);
-	return h & (IP6Q_HASHSZ - 1);
+	a = saddr->s6_addr32[0];
+	b = saddr->s6_addr32[1];
+	c = saddr->s6_addr32[2];
+
+	a += JHASH_GOLDEN_RATIO;
+	b += JHASH_GOLDEN_RATIO;
+	c += ip6_frag_hash_rnd;
+	__jhash_mix(a, b, c);
+
+	a += saddr->s6_addr32[3];
+	b += daddr->s6_addr32[0];
+	c += daddr->s6_addr32[1];
+	__jhash_mix(a, b, c);
+
+	a += daddr->s6_addr32[2];
+	b += daddr->s6_addr32[3];
+	c += id;
+	__jhash_mix(a, b, c);
+
+	return c & (IP6Q_HASHSZ - 1);
 }
 
+static struct timer_list ip6_frag_secret_timer;
+static int ip6_frag_secret_interval = 10 * 60 * HZ;
+
+static void ip6_frag_secret_rebuild(unsigned long dummy)
+{
+	unsigned long now = jiffies;
+	int i;
+
+	write_lock(&ip6_frag_lock);
+	get_random_bytes(&ip6_frag_hash_rnd, sizeof(u32));
+	for (i = 0; i < IP6Q_HASHSZ; i++) {
+		struct frag_queue *q;
+
+		q = ip6_frag_hash[i];
+		while (q) {
+			struct frag_queue *next = q->next;
+			unsigned int hval = ip6qhashfn(q->id,
+						       &q->saddr,
+						       &q->daddr);
+
+			if (hval != i) {
+				/* Unlink. */
+				if (q->next)
+					q->next->pprev = q->pprev;
+				*q->pprev = q->next;
+
+				/* Relink to new hash chain. */
+				if ((q->next = ip6_frag_hash[hval]) != NULL)
+					q->next->pprev = &q->next;
+				ip6_frag_hash[hval] = q;
+				q->pprev = &ip6_frag_hash[hval];
+			}
+
+			q = next;
+		}
+	}
+	write_unlock(&ip6_frag_lock);
+
+	mod_timer(&ip6_frag_secret_timer, now + ip6_frag_secret_interval);
+}
 
 atomic_t ip6_frag_mem = ATOMIC_INIT(0);
 
@@ -193,38 +258,30 @@
 
 static void ip6_evictor(void)
 {
-	int i, progress;
+	struct frag_queue *fq;
+	struct list_head *tmp;
 
-	do {
+	for(;;) {
 		if (atomic_read(&ip6_frag_mem) <= sysctl_ip6frag_low_thresh)
 			return;
-		progress = 0;
-		for (i = 0; i < IP6Q_HASHSZ; i++) {
-			struct frag_queue *fq;
-			if (ip6_frag_hash[i] == NULL)
-				continue;
-
-			read_lock(&ip6_frag_lock);
-			if ((fq = ip6_frag_hash[i]) != NULL) {
-				/* find the oldest queue for this hash bucket */
-				while (fq->next)
-					fq = fq->next;
-				atomic_inc(&fq->refcnt);
-				read_unlock(&ip6_frag_lock);
-
-				spin_lock(&fq->lock);
-				if (!(fq->last_in&COMPLETE))
-					fq_kill(fq);
-				spin_unlock(&fq->lock);
-
-				fq_put(fq);
-				IP6_INC_STATS_BH(Ip6ReasmFails);
-				progress = 1;
-				continue;
-			}
+		read_lock(&ip6_frag_lock);
+		if (list_empty(&ip6_frag_lru_list)) {
 			read_unlock(&ip6_frag_lock);
+			return;
 		}
-	} while (progress);
+		tmp = ip6_frag_lru_list.next;
+		fq = list_entry(tmp, struct frag_queue, lru_list);
+		atomic_inc(&fq->refcnt);
+		read_unlock(&ip6_frag_lock);
+
+		spin_lock(&fq->lock);
+		if (!(fq->last_in&COMPLETE))
+			fq_kill(fq);
+		spin_unlock(&fq->lock);
+
+		fq_put(fq);
+		IP6_INC_STATS_BH(Ip6ReasmFails);
+	}
 }
 
 static void ip6_frag_expire(unsigned long data)
@@ -294,6 +351,8 @@
 		fq->next->pprev = &fq->next;
 	ip6_frag_hash[hash] = fq;
 	fq->pprev = &ip6_frag_hash[hash];
+	INIT_LIST_HEAD(&fq->lru_list);
+	list_add_tail(&fq->lru_list, &ip6_frag_lru_list);
 	ip6_frag_nqueues++;
 	write_unlock(&ip6_frag_lock);
 	return fq;
@@ -501,6 +560,9 @@
 		fq->nhoffset = nhoff;
 		fq->last_in |= FIRST_IN;
 	}
+	write_lock(&ip6_frag_lock);
+	list_move_tail(&fq->lru_list, &ip6_frag_lru_list);
+	write_unlock(&ip6_frag_lock);
 	return;
 
 err:
@@ -679,3 +741,14 @@
 	kfree_skb(skb);
 	return -1;
 }
+
+void __init ipv6_frag_init(void)
+{
+	ip6_frag_hash_rnd = (u32) ((num_physpages ^ (num_physpages>>7)) ^
+				   (jiffies ^ (jiffies >> 6)));
+
+	init_timer(&ip6_frag_secret_timer);
+	ip6_frag_secret_timer.function = ip6_frag_secret_rebuild;
+	ip6_frag_secret_timer.expires = jiffies + ip6_frag_secret_interval;
+	add_timer(&ip6_frag_secret_timer);
+}