aboutsummaryrefslogtreecommitdiffstats
path: root/net
diff options
context:
space:
mode:
authorYOSHIFUJI Hideaki <yoshfuji@linux-ipv6.org>2008-02-18 20:15:27 -0500
committerYOSHIFUJI Hideaki <yoshfuji@linux-ipv6.org>2008-03-24 21:23:56 -0400
commit3b6cdf94cd6dd0b64cc8646cf067a1ae0203276d (patch)
tree2c16cfb412a55471973ac02e08a823229c15d274 /net
parent92f1fecb45ef97acae94463302f79228a4b454d9 (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')
-rw-r--r--net/ipv6/xfrm6_state.c171
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,
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 */
52static int 53static 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
119static 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 */
88static 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 */ 110static 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 */
125static 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: 143static 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
173int xfrm6_extract_header(struct sk_buff *skb) 150int xfrm6_extract_header(struct sk_buff *skb)
generated by cgit v1.2.2 (git 2.25.0) at 2024-12-28 20:06:05 -0500