Implement new guard selection algorithm of prop 271
Parent ticket for tasks implementing the new guard selection algorithm described in https://lists.torproject.org/pipermail/tor-dev/2016-July/011234.html
Activity
changed milestone to %Tor: 0.3.0.x-final
added TorCoreTeam201612 actual-review-points=5 component::core tor/tor isaremoved milestone::Tor: 0.3.0.x-final nickwants029 owner::nickm priority::medium resolution::fixed review-group-13 reviewer::asn reviewer::chelsea severity::normal sponsor::U-must status::closed tor-guards-revamp type::task version::tor unspecified labels
Status: My
prop271-wipbranch (which I will rebase very much) has most of the common backend for prop271 implemented and tested. Next I finish the "waiting circuits list" magic, and tie it into Tor.Trac:
Status: new to assigned
Owner: N/A to nickm
Keywords: nickm-deferred-20161005 deleted, TorCoreTeam201611 added
Hello, I did a very rough initial review based on the WIP branch
prop271-wip. Haven't run it yet. Great work so far, very excited about splitting bridge code to another file as well.Some of these comments might be too low level for this stage of implementation, so feel free to ignore them. Also, I have not re-loaded the whole proposal in my brain yet, so I didn't go too deep in the nitty gritty details.
-
There are a few big scary functions that could be splitted into smaller functions to make them more manageable. e.g.
sampled_guards_update_from_consensus()andentry_guards_update_primary.Also the fundamental function
select_entry_guard_for_circuit()could be split into three smaller functions, each for one spec case. -
Agreed that the
entry_guard_succeeded()tristate is ugly and makes thecircuit_send_next_onion_skin()logic harder to read. Perhaps the retval could be turned into an enum? -
If
add_bridge_as_entry_guard()is a pub function of the entrynodes API, should it have a prefix? Or we are not at that level of tidyness yet? -
Why do we need the spaceless ISO time functions? Can't we use the spaceful ones for state? Or is it to maintain backwards compat?
-
Parsing guards from state seems a bit of a pain now. For example,
entry_guard_parse_from_state()does ad-hoc string parsing. Would it be possible to use the config parsing API for that? -
Could
smartlist_remove_keeporder()be implemented withsmartlist_pos()andsmartlist_del_keeporder()to avoid writing more smartlist code?
Finally, how should one robustly test this branch? Do you use iptable scripts or something?
-
-
Replying to asn:
Hello, I did a very rough initial review based on the WIP branch
prop271-wip. Haven't run it yet. Great work so far, very excited about splitting bridge code to another file as well.Some of these comments might be too low level for this stage of implementation, so feel free to ignore them. Also, I have not re-loaded the whole proposal in my brain yet, so I didn't go too deep in the nitty gritty details.
-
There are a few big scary functions that could be splitted into smaller functions to make them more manageable. e.g.
sampled_guards_update_from_consensus()andentry_guards_update_primary.Also the fundamental function
select_entry_guard_for_circuit()could be split into three smaller functions, each for one spec case.
Ack. I'll add a "XXXX can this split up" comment to those.
- Agreed that the
entry_guard_succeeded()tristate is ugly and makes thecircuit_send_next_onion_skin()logic harder to read. Perhaps the retval could be turned into an enum?
Ack, will fix.
- If
add_bridge_as_entry_guard()is a pub function of the entrynodes API, should it have a prefix? Or we are not at that level of tidyness yet?
The entire bridge->entry interface is in flux; I hope we clean it up by the end.
- Why do we need the spaceless ISO time functions? Can't we use the spaceful ones for state? Or is it to maintain backwards compat?
For the state format I chose, everything is spaceless. That makes it much much easier.
- Parsing guards from state seems a bit of a pain now. For example,
entry_guard_parse_from_state()does ad-hoc string parsing. Would it be possible to use the config parsing API for that?
Oooh. Interesting. We'd have to make it recursive, so it can handle the values within a line rather than just handling lines. Could be neat though. Maybe as another ticket?
- Could
smartlist_remove_keeporder()be implemented withsmartlist_pos()andsmartlist_del_keeporder()to avoid writing more smartlist code?
Only in quadratic-time: smartlist_remove_keeporder() needs to remove every occurrence of the target element. So to emulate it with pos and del_keeporder, you'd need to say:
int idx; while ( (idx = smartlist_pos(sl, element)) >= 0) { smartlist_del_keeporder(sl, idx); }Finally, how should one robustly test this branch? Do you use iptable scripts or something?
I've been doing ad-hoc iptable stuff, doing some of my hacking from nasty coffeeshop ISPs, etc. I haven't figured out how to do a really thorough hostile-network integration test though.
-
-
Okay, here we go.
46 files changed, 8004 insertions(+), 1356 deletions(-)The code is pretty solid, and I think it's worth reviewing now. I've made a new branch, "prop271_030_v1". This branch will not get rebased. I've uploaded it to gitlab for review at https://gitlab.com/nickm_tor/tor/merge_requests/11
There is a corresponding torspec branch in "prop271-changes" in my public torspec repository.
For follow-up items for this work, see #20822 (moved).
Trac:
Status: assigned to needs_review -
Hello,
I did some initial testing and a first pass of manual code review.
You can see the first testing results here: https://trac.torproject.org/projects/tor/wiki/doc/NewGuardAlgorithmTesting
I also left a few comments on the gitlab review with things that should be discussed. Some of those comments might be follow-up material (#20822 (moved)).
Also, please check my
prop271_030_v1branch for some misc fixes.BTW, starting tomorrow and until Monday I will be travelling and will have reduced connectivity and time for review. I might manage to do a few stuff, but I will continue in full force starting next Tuesday. Next week I can do more testing, and also some refactoring, and perhaps add some unittests (e.g. for the flappiness feature).
Trac:
Status: needs_review to needs_revision Hey Nick,
Here are some general thoughts, feel free to take/leave what is useful. I added notes to the gitlab review as well.
-
Naming conventions are a bit confusing, as we use entrynodes, entryguards, and guards. If this naming signifies pre and post prop271, maybe we can add in legacy namespacing to make it more clear (see below). Also, the bridge-specific module looks really great- if there is guard-specific code that is distinct from entrynodes, maybe this belongs in a separate guard module.
-
Making a clear distinction between pre and post prop271 code would definitely make reviewing easier, as well as eventually migrating away from legacy code... I liked asn's recommendation of namespacing, we could also move legacy code to it's own module, etc.
-
Some functions are quite large, such as sampled_guards_update_from_consensus and entry_guards_upgrade_waiting_circuits. I see some todos about splitting these up, which is great.
-
Would it make sense to put parsing code into a parser.c?
-
I didn't see a lot of tests here: https://gitlab.com/nickm_tor/tor/merge_requests/11 - is there another set of commits for these?
-
bridges.c doesn't have test coverage :(
-
It looks like there are several remaining todos that need to be completed. Which of these should be completed as part of this patch? For example, in entrynodes.c, update_guard_selection_choice has a comment about needing to expire existing circuits (line 653).
-
-
Replying to asn:
Hello,
I did some initial testing and a first pass of manual code review.
Thank you!
You can see the first testing results here: https://trac.torproject.org/projects/tor/wiki/doc/NewGuardAlgorithmTesting
I also left a few comments on the gitlab review with things that should be discussed. Some of those comments might be follow-up material (#20822 (moved)).
Okay. I'll look over all the comments on the gitlab pull request next.
Also, please check my
prop271_030_v1branch for some misc fixes.I've merged that into my branch; thak you!
BTW, starting tomorrow and until Monday I will be travelling and will have reduced connectivity and time for review. I might manage to do a few stuff, but I will continue in full force starting next Tuesday. Next week I can do more testing, and also some refactoring, and perhaps add some unittests (e.g. for the flappiness feature).
Thank you!
-
Replying to chelseakomlo:
Hey Nick,
Here are some general thoughts, feel free to take/leave what is useful. I added notes to the gitlab review as well.
-
Naming conventions are a bit confusing, as we use entrynodes, entryguards, and guards. If this naming signifies pre and post prop271, maybe we can add in legacy namespacing to make it more clear (see below). Also, the bridge-specific module looks really great- if there is guard-specific code that is distinct from entrynodes, maybe this belongs in a separate guard module.
-
Making a clear distinction between pre and post prop271 code would definitely make reviewing easier, as well as eventually migrating away from legacy code... I liked asn's recommendation of namespacing, we could also move legacy code to it's own module, etc.
I've tried adding #ifdefs around the old code, in 472a621ccc8a90bf90d8394210519974ad235848.
For namespacing, I think everything should wind up in one entryguards_* namespace once the legacy things are removed, and the rest of the code is cleaned up. The guards_* functions are there as generic frontends to the old and new code.
- Some functions are quite large, such as sampled_guards_update_from_consensus and entry_guards_upgrade_waiting_circuits. I see some todos about splitting these up, which is great.
Agreed.
- Would it make sense to put parsing code into a parser.c?
I'd like to extract it into something more general; for now it's pretty specific, though it could become more generally useful. I've added it #20919 (moved).
- I didn't see a lot of tests here: https://gitlab.com/nickm_tor/tor/merge_requests/11 - is there another set of commits for these?
I think we discussed this on IRC, and decided you needed to hit "expand" on gitlab, and then things got better.
- bridges.c doesn't have test coverage :(
Right. At least, that code is no less covered than it was before I moved it. :/
- It looks like there are several remaining todos that need to be completed. Which of these should be completed as part of this patch? For example, in entrynodes.c, update_guard_selection_choice has a comment about needing to expire existing circuits (line 653).
That's taken care of, so I removed the comment and updated the doxygen in 6a6625c632248c. Resolving todos in in general is #20718 (moved) under #20822 (moved)
-
-
Replying to nickm:
Okay, I think I've answered all the comments here and on gitlab, most of them with code fixes. Do we think this is ready for merge?
Thanks for fixing all the comments above. I'd like to do another round of review and testing next week before merging this. ETA for review results is Thursday.
If you feel like merging this, you can do this, and I'll follow up with comments anyhow.
-
I'm not in a hurry; Thursday would be fine. I've started trying to fix up some of the followup issues in other tickets under #20822 (moved) ; I can keep doing that while you do the second round. Thank you!
mentioned in issue #19888 (moved)
mentioned in issue #20718 (moved)
mentioned in issue #20719 (moved)
mentioned in issue #20834 (moved)
mentioned in issue #20922 (moved)
mentioned in issue #21039 (moved)
moved to tpo/core/tor#19877 (closed)
mentioned in issue tpo/core/tor#20834 (closed)
mentioned in issue tpo/core/tor#21039 (closed)
