[XFRM] IPV6: Use distribution counting sort for xfrm_state/xfrm_tmpl chain.

Signed-off-by: YOSHIFUJI Hideaki <yoshfuji@linux-ipv6.org>

1 files changed, 74 insertions, 97 deletions

diff --git a/net/ipv6/xfrm6_state.c b/net/ipv6/xfrm6_state.c
index dc817e035e23..5a46bb99c3af 100644
--- a/net/ipv6/xfrm6_state.c
+++ b/net/ipv6/xfrm6_state.c
@@ -49,125 +49,102 @@ __xfrm6_init_tempsel(struct xfrm_state *x, struct flowi *fl,
 	x->props.family = AF_INET6;
 }
 
+/* distribution counting sort function for xfrm_state and xfrm_tmpl */
 static int
-__xfrm6_state_sort(struct xfrm_state **dst, struct xfrm_state **src, int n)
+__xfrm6_sort(void **dst, void **src, int n, int (*cmp)(void *p), int maxclass)
 {
 	int i;
-	int j = 0;
+	int class[XFRM_MAX_DEPTH];
+	int count[maxclass];
 
-	/* Rule 1: select IPsec transport except AH */
-	for (i = 0; i < n; i++) {
-		if (src[i]->props.mode == XFRM_MODE_TRANSPORT &&
-		    src[i]->id.proto != IPPROTO_AH) {
-			dst[j++] = src[i];
-			src[i] = NULL;
-		}
-	}
-	if (j == n)
-		goto end;
+	memset(count, 0, sizeof(count));
 
-	/* Rule 2: select MIPv6 RO or inbound trigger */
-#if defined(CONFIG_IPV6_MIP6) || defined(CONFIG_IPV6_MIP6_MODULE)
 	for (i = 0; i < n; i++) {
-		if (src[i] &&
-		    (src[i]->props.mode == XFRM_MODE_ROUTEOPTIMIZATION ||
-		     src[i]->props.mode == XFRM_MODE_IN_TRIGGER)) {
-			dst[j++] = src[i];
-			src[i] = NULL;
-		}
+		int c;
+		class[i] = c = cmp(src[i]);
+		count[c]++;
 	}
-	if (j == n)
-		goto end;
-#endif
 
-	/* Rule 3: select IPsec transport AH */
-	for (i = 0; i < n; i++) {
-		if (src[i] &&
-		    src[i]->props.mode == XFRM_MODE_TRANSPORT &&
-		    src[i]->id.proto == IPPROTO_AH) {
-			dst[j++] = src[i];
-			src[i] = NULL;
-		}
-	}
-	if (j == n)
-		goto end;
+	for (i = 2; i < maxclass; i++)
+		count[i] += count[i - 1];
 
-	/* Rule 4: select IPsec tunnel */
 	for (i = 0; i < n; i++) {
-		if (src[i] &&
-		    (src[i]->props.mode == XFRM_MODE_TUNNEL ||
-		     src[i]->props.mode == XFRM_MODE_BEET)) {
-			dst[j++] = src[i];
-			src[i] = NULL;
-		}
+		dst[count[class[i] - 1]++] = src[i];
+		src[i] = 0;
 	}
-	if (likely(j == n))
-		goto end;
 
-	/* Final rule */
-	for (i = 0; i < n; i++) {
-		if (src[i]) {
-			dst[j++] = src[i];
-			src[i] = NULL;
-		}
-	}
-
- end:
 	return 0;
 }
 
-static int
-__xfrm6_tmpl_sort(struct xfrm_tmpl **dst, struct xfrm_tmpl **src, int n)
+/*
+ * Rule for xfrm_state:
+ *
+ * rule 1: select IPsec transport except AH
+ * rule 2: select MIPv6 RO or inbound trigger
+ * rule 3: select IPsec transport AH
+ * rule 4: select IPsec tunnel
+ * rule 5: others
+ */
+static int __xfrm6_state_sort_cmp(void *p)
 {
-	int i;
-	int j = 0;
-
-	/* Rule 1: select IPsec transport */
-	for (i = 0; i < n; i++) {
-		if (src[i]->mode == XFRM_MODE_TRANSPORT) {
-			dst[j++] = src[i];
-			src[i] = NULL;
-		}
-	}
-	if (j == n)
-		goto end;
-
-	/* Rule 2: select MIPv6 RO or inbound trigger */
+	struct xfrm_state *v = p;
+
+	switch (v->props.mode) {
+	case XFRM_MODE_TRANSPORT:
+		if (v->id.proto != IPPROTO_AH)
+			return 1;
+		else
+			return 3;
 #if defined(CONFIG_IPV6_MIP6) || defined(CONFIG_IPV6_MIP6_MODULE)
-	for (i = 0; i < n; i++) {
-		if (src[i] &&
-		    (src[i]->mode == XFRM_MODE_ROUTEOPTIMIZATION ||
-		     src[i]->mode == XFRM_MODE_IN_TRIGGER)) {
-			dst[j++] = src[i];
-			src[i] = NULL;
-		}
-	}
-	if (j == n)
-		goto end;
+	case XFRM_MODE_ROUTEOPTIMIZATION:
+	case XFRM_MODE_IN_TRIGGER:
+		return 2;
 #endif
-
-	/* Rule 3: select IPsec tunnel */
-	for (i = 0; i < n; i++) {
-		if (src[i] &&
-		    (src[i]->mode == XFRM_MODE_TUNNEL ||
-		     src[i]->mode == XFRM_MODE_BEET)) {
-			dst[j++] = src[i];
-			src[i] = NULL;
-		}
+	case XFRM_MODE_TUNNEL:
+	case XFRM_MODE_BEET:
+		return 4;
 	}
-	if (likely(j == n))
-		goto end;
+	return 5;
+}
 
-	/* Final rule */
-	for (i = 0; i < n; i++) {
-		if (src[i]) {
-			dst[j++] = src[i];
-			src[i] = NULL;
-		}
+static int
+__xfrm6_state_sort(struct xfrm_state **dst, struct xfrm_state **src, int n)
+{
+	return __xfrm6_sort((void **)dst, (void **)src, n,
+			    __xfrm6_state_sort_cmp, 6);
+}
+
+/*
+ * Rule for xfrm_tmpl:
+ *
+ * rule 1: select IPsec transport
+ * rule 2: select MIPv6 RO or inbound trigger
+ * rule 3: select IPsec tunnel
+ * rule 4: others
+ */
+static int __xfrm6_tmpl_sort_cmp(void *p)
+{
+	struct xfrm_tmpl *v = p;
+	switch (v->mode) {
+	case XFRM_MODE_TRANSPORT:
+		return 1;
+#if defined(CONFIG_IPV6_MIP6) || defined(CONFIG_IPV6_MIP6_MODULE)
+	case XFRM_MODE_ROUTEOPTIMIZATION:
+	case XFRM_MODE_IN_TRIGGER:
+		return 2;
+#endif
+	case XFRM_MODE_TUNNEL:
+	case XFRM_MODE_BEET:
+		return 3;
 	}
+	return 4;
+}
 
- end:
-	return 0;
+static int
+__xfrm6_tmpl_sort(struct xfrm_tmpl **dst, struct xfrm_tmpl **src, int n)
+{
+	return __xfrm6_sort((void **)dst, (void **)src, n,
+			    __xfrm6_tmpl_sort_cmp, 5);
 }
 
 int xfrm6_extract_header(struct sk_buff *skb)