From 3b6cdf94cd6dd0b64cc8646cf067a1ae0203276d Mon Sep 17 00:00:00 2001 From: YOSHIFUJI Hideaki Date: Tue, 19 Feb 2008 10:15:27 +0900 Subject: [PATCH] [XFRM] IPV6: Use distribution counting sort for xfrm_state/xfrm_tmpl chain. Signed-off-by: YOSHIFUJI Hideaki --- net/ipv6/xfrm6_state.c | 171 ++++++++++++++++++----------------------- 1 file changed, 74 insertions(+), 97 deletions(-) diff --git a/net/ipv6/xfrm6_state.c b/net/ipv6/xfrm6_state.c index dc817e035e..5a46bb99c3 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) -- 2.39.5