Hi all.
I stumbled upon to two /* ??? stupid n**2 algorithm */ comments in
ikev2_child.c, in functions
ikev2_evaluate_connection_protocol_fit. and
int ikev2_evaluate_connection_port_fit
I made a patch, trying to reduce it to O(n) algorithm,
it seems right to me, but probably it will be better if more people
examine it, so please do it if you can :)
Here's a github link:
https://github.com/vukasink/libreswan/commit/8000cd325e4897f2e96a644d5bc0172d097f1ec4
but you can also find it attached in this e-mail.
Regards,
Vukasin K.
diff --git a/programs/pluto/ikev2_child.c b/programs/pluto/ikev2_child.c
index fad79c8..9e99c3f 100644
--- a/programs/pluto/ikev2_child.c
+++ b/programs/pluto/ikev2_child.c
@@ -382,8 +382,10 @@ int ikev2_evaluate_connection_protocol_fit(const struct connection *d,
int *best_tsi_i,
int *best_tsr_i)
{
- int tsi_ni;
+ int tsi_ni, tsr_ni;
int bestfit_pr = -1;
+ int bestfit_i_temp = 0, bestfit_r_temp = 0;
+ int best_tsi_temp = -1, best_tsr_temp = -1;
const struct end *ei, *er;
int narrowing = (d->policy & POLICY_IKEV2_ALLOW_NARROWING);
@@ -394,44 +396,47 @@ int ikev2_evaluate_connection_protocol_fit(const struct connection *d,
ei = &sr->that;
er = &sr->this;
}
- /* compare tsi/r array to this/that, evaluating protocol how well it fits */
- /* ??? stupid n**2 algorithm */
+ /* compare tsi array to this */
for (tsi_ni = 0; tsi_ni < tsi_n; tsi_ni++) {
- int tsr_ni;
int fitrange_i = ikev2_match_protocol(ei->protocol, tsi[tsi_ni].ipprotoid,
role == ORIGINAL_RESPONDER && narrowing,
role == ORIGINAL_INITIATOR && narrowing,
"tsi", tsi_ni);
- if (fitrange_i == 0)
- continue; /* save effort! */
-
- for (tsr_ni = 0; tsr_ni < tsr_n; tsr_ni++) {
- int fitrange_r = ikev2_match_protocol(er->protocol, tsr[tsr_ni].ipprotoid,
- role == ORIGINAL_RESPONDER && narrowing,
- role == ORIGINAL_INITIATOR && narrowing,
- "tsr", tsr_ni);
-
- int matchiness;
-
- if (fitrange_r == 0)
- continue; /* save effort! */
-
- matchiness = fitrange_i + fitrange_r; /* ??? arbitrary objective function */
+ if (fitrange_i > bestfit_i_temp) {
+ bestfit_i_temp = fitrange_i;
+ best_tsi_temp = tsi_ni;
+ if (bestfit_i_temp == 255) /* we can't find a better one */
+ break;
+ }
+ }
+ /* compare tsr array to that */
+ for (tsr_ni = 0; tsr_ni < tsr_n; tsr_ni++) {
+ int fitrange_r = ikev2_match_protocol(er->protocol, tsr[tsr_ni].ipprotoid,
+ role == ORIGINAL_RESPONDER && narrowing,
+ role == ORIGINAL_INITIATOR && narrowing,
+ "tsr", tsr_ni);
- if (matchiness > bestfit_pr) {
- *best_tsi_i = tsi_ni;
- *best_tsr_i = tsr_ni;
- bestfit_pr = matchiness;
- DBG(DBG_CONTROL,
- DBG_log(" best protocol fit so far: tsi[%d] fitrange_i %d, tsr[%d] fitrange_r %d, matchiness %d",
- *best_tsi_i, fitrange_i,
- *best_tsr_i, fitrange_r,
- matchiness));
- }
+ if (fitrange_r > bestfit_r_temp) {
+ bestfit_r_temp = fitrange_r;
+ best_tsr_temp = tsr_ni;
+ if (bestfit_i_temp == 255) /* we can't find a better one */
+ break;
}
}
+ /* if we found at least one match (and thus the best) in each */
+ if (best_tsi_temp != -1 && best_tsr_temp != -1 ) {
+ *best_tsi_i = best_tsi_temp;
+ *best_tsr_i = best_tsr_temp;
+ bestfit_pr = bestfit_i_temp + bestfit_r_temp;
+ DBG(DBG_CONTROL,
+ DBG_log(" best protocol fit: tsi[%d] fitrange_i %d, tsr[%d] fitrange_r %d, matchiness %d",
+ *best_tsi_i, bestfit_i_temp,
+ *best_tsr_i, bestfit_r_temp,
+ bestfit_pr));
+ }
+
DBG(DBG_CONTROL, DBG_log(" protocol_fitness %d", bestfit_pr));
return bestfit_pr;
}
@@ -489,8 +494,10 @@ int ikev2_evaluate_connection_port_fit(const struct connection *d,
int *best_tsi_i,
int *best_tsr_i)
{
- int tsi_ni;
+ int tsi_ni, tsr_ni;
int bestfit_p = -1;
+ int bestfit_i_temp = 0, bestfit_r_temp = 0;
+ int best_tsi_temp = -1, best_tsr_temp = -1;
const struct end *ei, *er;
int narrowing = (d->policy & POLICY_IKEV2_ALLOW_NARROWING);
@@ -501,43 +508,43 @@ int ikev2_evaluate_connection_port_fit(const struct connection *d,
ei = &sr->that;
er = &sr->this;
}
- /* compare tsi/r array to this/that, evaluating how well each port range fits */
- /* ??? stupid n**2 algorithm */
+ /* compare tsi array to this */
for (tsi_ni = 0; tsi_ni < tsi_n; tsi_ni++) {
- int tsr_ni;
+
int fitrange_i = ikev2_match_port_range(ei->port, tsi[tsi_ni],
role == ORIGINAL_RESPONDER && narrowing,
role == ORIGINAL_INITIATOR && narrowing,
"tsi", tsi_ni);
- if (fitrange_i == 0)
- continue; /* save effort! */
-
- for (tsr_ni = 0; tsr_ni < tsr_n; tsr_ni++) {
- int fitrange_r = ikev2_match_port_range(er->port, tsr[tsr_ni],
- role == ORIGINAL_RESPONDER && narrowing,
- role == ORIGINAL_INITIATOR && narrowing,
- "tsr", tsr_ni);
-
- int matchiness;
-
- if (fitrange_r == 0)
- continue; /* no match */
-
- matchiness = fitrange_i + fitrange_r; /* ??? arbitrary objective function */
+ if (fitrange_i > bestfit_i_temp) {
+ bestfit_i_temp = fitrange_i;
+ best_tsi_temp = tsi_ni;
+ }
+ }
+ /* compare tsr array to that */
+ for (tsr_ni = 0; tsr_ni < tsr_n; tsr_ni++) {
+ int fitrange_r = ikev2_match_port_range(er->port, tsr[tsr_ni],
+ role == ORIGINAL_RESPONDER && narrowing,
+ role == ORIGINAL_INITIATOR && narrowing,
+ "tsr", tsr_ni);
- if (matchiness > bestfit_p) {
- *best_tsi_i = tsi_ni;
- *best_tsr_i = tsr_ni;
- bestfit_p = matchiness;
- DBG(DBG_CONTROL,
- DBG_log(" best ports fit so far: tsi[%d] fitrange_i %d, tsr[%d] fitrange_r %d, matchiness %d",
- *best_tsi_i, fitrange_i,
- *best_tsr_i, fitrange_r,
- matchiness));
- }
+ if (fitrange_r > bestfit_r_temp) {
+ bestfit_r_temp = fitrange_r;
+ best_tsr_temp = tsr_ni;
}
}
+ /* if we found at least one match (and thus the best) in each */
+ if (best_tsi_temp != -1 && best_tsr_temp != -1 ) {
+ *best_tsi_i = best_tsi_temp;
+ *best_tsr_i = best_tsr_temp;
+ bestfit_p = bestfit_i_temp + bestfit_r_temp;
+ DBG(DBG_CONTROL,
+ DBG_log(" best ports fit: tsi[%d] fitrange_i %d, tsr[%d] fitrange_r %d, matchiness %d",
+ *best_tsi_i, bestfit_i_temp,
+ *best_tsr_i, bestfit_r_temp,
+ bestfit_p));
+ }
+
DBG(DBG_CONTROL, DBG_log(" port_fitness %d", bestfit_p));
return bestfit_p;
}
_______________________________________________
Swan-dev mailing list
[email protected]
https://lists.libreswan.org/mailman/listinfo/swan-dev
