diff options
author | YOSHIFUJI Hideaki <yoshfuji@linux-ipv6.org> | 2008-02-18 20:15:27 -0500 |
---|---|---|
committer | YOSHIFUJI Hideaki <yoshfuji@linux-ipv6.org> | 2008-03-24 21:23:56 -0400 |
commit | 3b6cdf94cd6dd0b64cc8646cf067a1ae0203276d (patch) | |
tree | 2c16cfb412a55471973ac02e08a823229c15d274 /net/ipv6/xfrm6_state.c | |
parent | 92f1fecb45ef97acae94463302f79228a4b454d9 (diff) |
[XFRM] IPV6: Use distribution counting sort for xfrm_state/xfrm_tmpl chain.
Signed-off-by: YOSHIFUJI Hideaki <yoshfuji@linux-ipv6.org>
Diffstat (limited to 'net/ipv6/xfrm6_state.c')
-rw-r--r-- | net/ipv6/xfrm6_state.c | 171 |
1 files changed, 74 insertions, 97 deletions
diff --git a/net/ipv6/xfrm6_state.c b/net/ipv6/xfrm6_state.c index dc817e035e2..5a46bb99c3a 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, | |||
49 | x->props.family = AF_INET6; | 49 | x->props.family = AF_INET6; |
50 | } | 50 | } |
51 | 51 | ||
52 | /* distribution counting sort function for xfrm_state and xfrm_tmpl */ | ||
52 | static int | 53 | static int |
53 | __xfrm6_state_sort(struct xfrm_state **dst, struct xfrm_state **src, int n) | 54 | __xfrm6_sort(void **dst, void **src, int n, int (*cmp)(void *p), int maxclass) |
54 | { | 55 | { |
55 | int i; | 56 | int i; |
56 | int j = 0; | 57 | int class[XFRM_MAX_DEPTH]; |
58 | int count[maxclass]; | ||
57 | 59 | ||
58 | /* Rule 1: select IPsec transport except AH */ | 60 | memset(count, 0, sizeof(count)); |
59 | for (i = 0; i < n; i++) { | ||
60 | if (src[i]->props.mode == XFRM_MODE_TRANSPORT && | ||
61 | src[i]->id.proto != IPPROTO_AH) { | ||
62 | dst[j++] = src[i]; | ||
63 | src[i] = NULL; | ||
64 | } | ||
65 | } | ||
66 | if (j == n) | ||
67 | goto end; | ||
68 | 61 | ||
69 | /* Rule 2: select MIPv6 RO or inbound trigger */ | ||
70 | #if defined(CONFIG_IPV6_MIP6) || defined(CONFIG_IPV6_MIP6_MODULE) | ||
71 | for (i = 0; i < n; i++) { | 62 | for (i = 0; i < n; i++) { |
72 | if (src[i] && | 63 | int c; |
73 | (src[i]->props.mode == XFRM_MODE_ROUTEOPTIMIZATION || | 64 | class[i] = c = cmp(src[i]); |
74 | src[i]->props.mode == XFRM_MODE_IN_TRIGGER)) { | 65 | count[c]++; |
75 | dst[j++] = src[i]; | ||
76 | src[i] = NULL; | ||
77 | } | ||
78 | } | 66 | } |
79 | if (j == n) | ||
80 | goto end; | ||
81 | #endif | ||
82 | 67 | ||
83 | /* Rule 3: select IPsec transport AH */ | 68 | for (i = 2; i < maxclass; i++) |
84 | for (i = 0; i < n; i++) { | 69 | count[i] += count[i - 1]; |
85 | if (src[i] && | ||
86 | src[i]->props.mode == XFRM_MODE_TRANSPORT && | ||
87 | src[i]->id.proto == IPPROTO_AH) { | ||
88 | dst[j++] = src[i]; | ||
89 | src[i] = NULL; | ||
90 | } | ||
91 | } | ||
92 | if (j == n) | ||
93 | goto end; | ||
94 | 70 | ||
95 | /* Rule 4: select IPsec tunnel */ | ||
96 | for (i = 0; i < n; i++) { | 71 | for (i = 0; i < n; i++) { |
97 | if (src[i] && | 72 | dst[count[class[i] - 1]++] = src[i]; |
98 | (src[i]->props.mode == XFRM_MODE_TUNNEL || | 73 | src[i] = 0; |
99 | src[i]->props.mode == XFRM_MODE_BEET)) { | ||
100 | dst[j++] = src[i]; | ||
101 | src[i] = NULL; | ||
102 | } | ||
103 | } | 74 | } |
104 | if (likely(j == n)) | ||
105 | goto end; | ||
106 | 75 | ||
107 | /* Final rule */ | ||
108 | for (i = 0; i < n; i++) { | ||
109 | if (src[i]) { | ||
110 | dst[j++] = src[i]; | ||
111 | src[i] = NULL; | ||
112 | } | ||
113 | } | ||
114 | |||
115 | end: | ||
116 | return 0; | 76 | return 0; |
117 | } | 77 | } |
118 | 78 | ||
119 | static int | 79 | /* |
120 | __xfrm6_tmpl_sort(struct xfrm_tmpl **dst, struct xfrm_tmpl **src, int n) | 80 | * Rule for xfrm_state: |
81 | * | ||
82 | * rule 1: select IPsec transport except AH | ||
83 | * rule 2: select MIPv6 RO or inbound trigger | ||
84 | * rule 3: select IPsec transport AH | ||
85 | * rule 4: select IPsec tunnel | ||
86 | * rule 5: others | ||
87 | */ | ||
88 | static int __xfrm6_state_sort_cmp(void *p) | ||
121 | { | 89 | { |
122 | int i; | 90 | struct xfrm_state *v = p; |
123 | int j = 0; | 91 | |
124 | 92 | switch (v->props.mode) { | |
125 | /* Rule 1: select IPsec transport */ | 93 | case XFRM_MODE_TRANSPORT: |
126 | for (i = 0; i < n; i++) { | 94 | if (v->id.proto != IPPROTO_AH) |
127 | if (src[i]->mode == XFRM_MODE_TRANSPORT) { | 95 | return 1; |
128 | dst[j++] = src[i]; | 96 | else |
129 | src[i] = NULL; | 97 | return 3; |
130 | } | ||
131 | } | ||
132 | if (j == n) | ||
133 | goto end; | ||
134 | |||
135 | /* Rule 2: select MIPv6 RO or inbound trigger */ | ||
136 | #if defined(CONFIG_IPV6_MIP6) || defined(CONFIG_IPV6_MIP6_MODULE) | 98 | #if defined(CONFIG_IPV6_MIP6) || defined(CONFIG_IPV6_MIP6_MODULE) |
137 | for (i = 0; i < n; i++) { | 99 | case XFRM_MODE_ROUTEOPTIMIZATION: |
138 | if (src[i] && | 100 | case XFRM_MODE_IN_TRIGGER: |
139 | (src[i]->mode == XFRM_MODE_ROUTEOPTIMIZATION || | 101 | return 2; |
140 | src[i]->mode == XFRM_MODE_IN_TRIGGER)) { | ||
141 | dst[j++] = src[i]; | ||
142 | src[i] = NULL; | ||
143 | } | ||
144 | } | ||
145 | if (j == n) | ||
146 | goto end; | ||
147 | #endif | 102 | #endif |
148 | 103 | case XFRM_MODE_TUNNEL: | |
149 | /* Rule 3: select IPsec tunnel */ | 104 | case XFRM_MODE_BEET: |
150 | for (i = 0; i < n; i++) { | 105 | return 4; |
151 | if (src[i] && | ||
152 | (src[i]->mode == XFRM_MODE_TUNNEL || | ||
153 | src[i]->mode == XFRM_MODE_BEET)) { | ||
154 | dst[j++] = src[i]; | ||
155 | src[i] = NULL; | ||
156 | } | ||
157 | } | 106 | } |
158 | if (likely(j == n)) | 107 | return 5; |
159 | goto end; | 108 | } |
160 | 109 | ||
161 | /* Final rule */ | 110 | static int |
162 | for (i = 0; i < n; i++) { | 111 | __xfrm6_state_sort(struct xfrm_state **dst, struct xfrm_state **src, int n) |
163 | if (src[i]) { | 112 | { |
164 | dst[j++] = src[i]; | 113 | return __xfrm6_sort((void **)dst, (void **)src, n, |
165 | src[i] = NULL; | 114 | __xfrm6_state_sort_cmp, 6); |
166 | } | 115 | } |
116 | |||
117 | /* | ||
118 | * Rule for xfrm_tmpl: | ||
119 | * | ||
120 | * rule 1: select IPsec transport | ||
121 | * rule 2: select MIPv6 RO or inbound trigger | ||
122 | * rule 3: select IPsec tunnel | ||
123 | * rule 4: others | ||
124 | */ | ||
125 | static int __xfrm6_tmpl_sort_cmp(void *p) | ||
126 | { | ||
127 | struct xfrm_tmpl *v = p; | ||
128 | switch (v->mode) { | ||
129 | case XFRM_MODE_TRANSPORT: | ||
130 | return 1; | ||
131 | #if defined(CONFIG_IPV6_MIP6) || defined(CONFIG_IPV6_MIP6_MODULE) | ||
132 | case XFRM_MODE_ROUTEOPTIMIZATION: | ||
133 | case XFRM_MODE_IN_TRIGGER: | ||
134 | return 2; | ||
135 | #endif | ||
136 | case XFRM_MODE_TUNNEL: | ||
137 | case XFRM_MODE_BEET: | ||
138 | return 3; | ||
167 | } | 139 | } |
140 | return 4; | ||
141 | } | ||
168 | 142 | ||
169 | end: | 143 | static int |
170 | return 0; | 144 | __xfrm6_tmpl_sort(struct xfrm_tmpl **dst, struct xfrm_tmpl **src, int n) |
145 | { | ||
146 | return __xfrm6_sort((void **)dst, (void **)src, n, | ||
147 | __xfrm6_tmpl_sort_cmp, 5); | ||
171 | } | 148 | } |
172 | 149 | ||
173 | int xfrm6_extract_header(struct sk_buff *skb) | 150 | int xfrm6_extract_header(struct sk_buff *skb) |