Opened 2 months ago

Closed 43 hours ago

#23817 closed defect (fixed)

Tor re-tries directory mirrors that it knows are missing microdescriptors

Reported by: teor Owned by:
Priority: Medium Milestone: Tor: 0.3.1.x-final
Component: Core Tor/Tor Version:
Severity: Normal Keywords: tor-guard, tor-hs, prop224, 032-backport? 031-backport? spec-change
Cc: teor, asn Actual Points:
Parent ID: #21969 Points:
Reviewer: Sponsor:

Description

When a microdescriptor for a relay changes, it takes a while to propagate to directory mirrors. In this time, a client can:

  1. Download a consensus that references the new microdescriptor
  2. Try a directory mirror that has an older consensus, and therefore doesn't have that microdescriptor
  3. Repeat 2

This is a particular issue when:

  • the client first bootstraps, and the fallback or authority provides a newer consensus than any of its directory mirrors
  • the client has been asleep for a while, and its consensus has expired, so it fetches one straight away
  • only 1/3 of a client's directory guards has the new consensus

We can fix this by:

  • making clients try the same directory mirror for their consensus and microdescriptors
  • making clients avoid directory mirrors with missing microdescriptors
  • making clients use a fallback when all of their directory mirrors don't have a microdescriptor

This issue affects primary guards and v3 onion services.

Child Tickets

Change History (58)

comment:1 Changed 2 months ago by teor

Parent ID: #21969

comment:2 Changed 2 months ago by teor

This issue occurs because a directory guard that is missing microdescriptors we need is still considered live. We only mark a guard dead when we fail to connect to it. (When all guards are marked dead, we use a fallback or authority to fetch microdescriptors).

comment:3 in reply to:  2 Changed 7 weeks ago by asn

Replying to teor:

This issue occurs because a directory guard that is missing microdescriptors we need is still considered live. We only mark a guard dead when we fail to connect to it. (When all guards are marked dead, we use a fallback or authority to fetch microdescriptors).

IIUC a directory guard can be naturally missing microdescriptors because they still have not propagated to the network sufficiently, so marking it as a dead guard at that point is probably an overkill (aka we might end up marking many (directory) guards as dead for no reason). Perhaps you mean marking it as dead for the purpose of fetching that specific microdescriptor and just skip to the next directory guard for fetching that md? I think some sort of logic like that would be useful, especially when considering important mds like the primary guard mds (#21969).

Perhaps what I'm suggesting above is your #23863? Seems like these two tickets are connected.

Last edited 7 weeks ago by asn (previous) (diff)

comment:4 Changed 7 weeks ago by asn

Here is a draft of a suggested technical solution here which involves a cache tracking failed md downloads:

1) Introduce an md_failure_cache cache which tracks failed or missing mds downloads per relays. That is a cache with entries as follows: "We failed to fetch md <hash> from relays X, Y, Z".

engineering XXX: how to figure out missing mds from received batches

2) When we want to fetch a batch of mds from relay X, check md_failure_cache to see if any of the batched mds is included in the cache for relay X. if that's the case, add relay X to the excluded list of nodes for dirservers, so that our directory subsystems skips relay X and moves to the next one in line.

engineering XXX: is there an exclude list for dirserver downloads?

3) When we succeed in fetching an md, remove its entries from the cache (so that we retry in the future from relay X which is probably our top primary guard).

4) Finally, to address #23863, when we detect that we are missing mds from our primary guards, order an immediate download of those missing mds, so that the previous steps get done.

comment:5 Changed 7 weeks ago by asn

I'm inlining some logs demonstrating this issue for completeness.

Tor failed to fetch the md with hash AGkG6zefrl7Uvkqo+nfCI1fDbxjvSyzsNS5TiWa0JeU.
Tor's dirguards are:

  1. 79.137.112.5
  2. 54.36.38.63
  3. 86.105.212.130

Here are some logs demonstrating the issue:

Oct 25 16:10:10.000 [warn] Received answer to microdescriptor request (status 200, body size 254796) from server '79.137.112.5:443'
Oct 25 16:10:10.000 [warn] Initially requested 500 mds, got 495, missed 5
Oct 25 16:10:10.000 [warn] AGkG6zefrl7Uvkqo+nfCI1fDbxjvSyzsNS5TiWa0JeU failed 1 time(s); I'll try again in 1 seconds. 
...
Oct 25 16:10:11.000 [warn] Received answer to microdescriptor request (status 404, body size 0) from server '79.137.112.5:443'
Oct 25 16:10:11.000 [warn] AGkG6zefrl7Uvkqo+nfCI1fDbxjvSyzsNS5TiWa0JeU failed 2 time(s); I'll try again in 3 seconds.
...
Oct 25 16:10:15.000 [warn] Received answer to microdescriptor request (status 404, body size 0) from server '79.137.112.5:443'
Oct 25 16:10:15.000 [warn] AGkG6zefrl7Uvkqo+nfCI1fDbxjvSyzsNS5TiWa0JeU failed 3 time(s); I'll try again in 9 seconds.
...
Oct 25 16:11:15.000 [warn] Received answer to microdescriptor request (status 200, body size 5182) from server '54.36.38.63:443'
Oct 25 16:11:15.000 [warn] AGkG6zefrl7Uvkqo+nfCI1fDbxjvSyzsNS5TiWa0JeU failed 4 time(s); I'll try again in 15 seconds.
...
Oct 25 16:12:15.000 [warn] Received answer to microdescriptor request (status 404, body size 0) from server '54.36.38.63:443'
Oct 25 16:12:15.000 [warn] AGkG6zefrl7Uvkqo+nfCI1fDbxjvSyzsNS5TiWa0JeU failed 5 time(s); I'll try again in 38 seconds.
...
Oct 25 16:13:15.000 [warn] Sent request to directory server '86.105.212.130:443': (purpose: 19, request size: 1123, payload size: 0)
Oct 25 16:13:16.000 [warn] Received answer to microdescriptor request (status 200, body size 10713) from server '86.105.212.130:443'

We basically see Tor failing to fetch the same md from 79.137.112.5:443 three times within 2 minutes, and then it fails to fetch from 54.36.38.63:443 another two times within 2 minutes, until it tries 86.105.212.130 which succeeds (that dircache is probably more up-to-date than the other two).

If a fail cache was in place, we would have gone to 86.105.212.130 on our third try, instead of our sixth.

comment:6 Changed 6 weeks ago by asn

Here is an implementation plan of the failure cache idea from comment:4 .

First of all, the interface of the failure cache:

We introduce a digest256map_t *md_fetch_fail_cache which maps the 256-bit md hash to a smartlist of dirguards thru which we failed to fetch the md.

Now the code logic:

1) We populate md_fetch_fail_cache with dirguards in dir_microdesc_download_failed(). We remove them from the failure cache in microdescs_add_to_cache() when we successfuly add an md to the cache.

2) We add another entry_guard_restriction_t restriction type in guards_choose_dirguard(). We currently have one restriction type which is designed to restrict guard nodes based on the exit node choice and its family. We want another type which uses a smartlist and restricts dirguards based on whether we have failed to fetch an md from that dirguard. We are gonna use this in step 3.

3) In directory_get_from_dirserver() we query the md failure cache and pass any results to directory_pick_generic_dirserver() and then to guards_choose_dirguard() which uses the new restriction type to block previously failed dirguards from being selected.

How does this feel like to you?

There are two more steps we might want to do:

  • When we find that we are missing descs for our primary guards, we order an immediate download of the missing descs so that the above algorithm takes place.
  • If we fail to fetch the mds from all of our primary guards, we retry using fallback directories instead of trying deeper down our guard list. Teor suggested this, but it seems to be far from trivial to implement given the interface of our guard subsystem. If it provides big benefit we should consider it.

comment:7 in reply to:  6 ; Changed 6 weeks ago by teor

Replying to asn:

Here is an implementation plan of the failure cache idea from comment:4 .

First of all, the interface of the failure cache:

We introduce a digest256map_t *md_fetch_fail_cache which maps the 256-bit md hash to a smartlist of dirguards thru which we failed to fetch the md.

Now the code logic:

1) We populate md_fetch_fail_cache with dirguards in dir_microdesc_download_failed(). We remove them from the failure cache in microdescs_add_to_cache() when we successfuly add an md to the cache.

Successfully add *that* md to the cache?
Or any md from that dirguard?

I think this is ok, as long as we ask for mds in large enough batches.

2) We add another entry_guard_restriction_t restriction type in guards_choose_dirguard(). We currently have one restriction type which is designed to restrict guard nodes based on the exit node choice and its family. We want another type which uses a smartlist and restricts dirguards based on whether we have failed to fetch an md from that dirguard. We are gonna use this in step 3.

3) In directory_get_from_dirserver() we query the md failure cache and pass any results to directory_pick_generic_dirserver() and then to guards_choose_dirguard() which uses the new restriction type to block previously failed dirguards from being selected.

Do we block dirguards that have failed to deliver an md from downloads of that md?
Or do we block dirguards that have failed to deliver any mds from downloads of any md?

How does this feel like to you?

There are two more steps we might want to do:

  • When we find that we are missing descs for our primary guards, we order an immediate download of the missing descs so that the above algorithm takes place.

This seems ok, we will end up leaking our primary guards to our dirguards.
To reduce the exposure, we should try to trigger this as soon as we get the consensus, and batch these in with other md downloads. (That is, if we have any mds waiting, we should retry *all* of them, not just the one or two primary guard mds.)

  • If we fail to fetch the mds from all of our primary guards, we retry using fallback directories instead of trying deeper down our guard list. Teor suggested this, but it seems to be far from trivial to implement given the interface of our guard subsystem. If it provides big benefit we should consider it.

This is #23863, we get this behaviour automatically if we mark the guards as down (or change the definition of a "down" guard in directory_pick_generic_dirserver() so it checks the md failure cache).

comment:8 Changed 6 weeks ago by nickm

Keywords: 032-backport? 031-backport? added

comment:9 in reply to:  7 ; Changed 6 weeks ago by asn

Replying to teor:

Replying to asn:

Here is an implementation plan of the failure cache idea from comment:4 .

First of all, the interface of the failure cache:

We introduce a digest256map_t *md_fetch_fail_cache which maps the 256-bit md hash to a smartlist of dirguards thru which we failed to fetch the md.

Now the code logic:

1) We populate md_fetch_fail_cache with dirguards in dir_microdesc_download_failed(). We remove them from the failure cache in microdescs_add_to_cache() when we successfuly add an md to the cache.

Successfully add *that* md to the cache?
Or any md from that dirguard?

I meant, we remove *that* md from the md_fetch_fail_cache if we manage to fetch *that* md from any dir.

I think this is ok, as long as we ask for mds in large enough batches.

2) We add another entry_guard_restriction_t restriction type in guards_choose_dirguard(). We currently have one restriction type which is designed to restrict guard nodes based on the exit node choice and its family. We want another type which uses a smartlist and restricts dirguards based on whether we have failed to fetch an md from that dirguard. We are gonna use this in step 3.

3) In directory_get_from_dirserver() we query the md failure cache and pass any results to directory_pick_generic_dirserver() and then to guards_choose_dirguard() which uses the new restriction type to block previously failed dirguards from being selected.

Do we block dirguards that have failed to deliver an md from downloads of that md?
Or do we block dirguards that have failed to deliver any mds from downloads of any md?

Yes, that's a good question that I forgot to address in this proposal.

I guess my design above was suggesting that we block dirguards "that have failed to deliver any mds from downloads of any md", until those mds get fetched from another dirserver and get removed from the failure cache.

That kinda penalizes dirservers that dont have a totally up-to-date md cache, which perhaps kinda makes sense. But perhaps before we become so strict, we should check whether we can improve the dirserver logic of fetching new mds so that they are almost always up-to-date if possible? Or we can do this last part after we implement the failure cache proposal?

comment:10 in reply to:  9 ; Changed 6 weeks ago by teor

Replying to asn:

Replying to teor:

Replying to asn:

Here is an implementation plan of the failure cache idea from comment:4 .

First of all, the interface of the failure cache:

We introduce a digest256map_t *md_fetch_fail_cache which maps the 256-bit md hash to a smartlist of dirguards thru which we failed to fetch the md.

Now the code logic:

1) We populate md_fetch_fail_cache with dirguards in dir_microdesc_download_failed(). We remove them from the failure cache in microdescs_add_to_cache() when we successfuly add an md to the cache.

Successfully add *that* md to the cache?
Or any md from that dirguard?

I meant, we remove *that* md from the md_fetch_fail_cache if we manage to fetch *that* md from any dir.

I think this is ok, as long as we ask for mds in large enough batches.

2) We add another entry_guard_restriction_t restriction type in guards_choose_dirguard(). We currently have one restriction type which is designed to restrict guard nodes based on the exit node choice and its family. We want another type which uses a smartlist and restricts dirguards based on whether we have failed to fetch an md from that dirguard. We are gonna use this in step 3.

3) In directory_get_from_dirserver() we query the md failure cache and pass any results to directory_pick_generic_dirserver() and then to guards_choose_dirguard() which uses the new restriction type to block previously failed dirguards from being selected.

Do we block dirguards that have failed to deliver an md from downloads of that md?
Or do we block dirguards that have failed to deliver any mds from downloads of any md?

Yes, that's a good question that I forgot to address in this proposal.

I guess my design above was suggesting that we block dirguards "that have failed to deliver any mds from downloads of any md", until those mds get fetched from another dirserver and get removed from the failure cache.

I think this is the behaviour we want: trying each dir server for each specific md will mean that we time out, because there are more mds than there are dir servers.

There are two cases when this will cause us to fall back to the authorities:

  • we download a new consensus from the authorities, and they are the only ones with some of the mds in it
  • for some reason, an md referenced in the consensus is not mirrored correctly by relays or authorities (this would be a serious bug in tor)

To avoid this happening when it isn't necessary, we should expire failure cache entries after a random time. Maybe it should be the time when we expect dir servers to fetch a new consensus and new mds. I think this is 1-2 hours, but check dir-spec for the exact details. Or we could expire md failure caches each time we get a new consensus. That would be easier.

That kinda penalizes dirservers that dont have a totally up-to-date md cache, which perhaps kinda makes sense. But perhaps before we become so strict, we should check whether we can improve the dirserver logic of fetching new mds so that they are almost always up-to-date if possible? Or we can do this last part after we implement the failure cache proposal?

No, it's not possible to improve this behaviour without major changes to tor. A directory server can't fetch new mds until it fetches a new consensus that references them. And these fetches are done at random times to avoid flooding authorities with queries.

comment:11 in reply to:  10 ; Changed 6 weeks ago by asn

Replying to teor:

Replying to asn:

Replying to teor:

Replying to asn:

Here is an implementation plan of the failure cache idea from comment:4 .

First of all, the interface of the failure cache:

We introduce a digest256map_t *md_fetch_fail_cache which maps the 256-bit md hash to a smartlist of dirguards thru which we failed to fetch the md.

Now the code logic:

1) We populate md_fetch_fail_cache with dirguards in dir_microdesc_download_failed(). We remove them from the failure cache in microdescs_add_to_cache() when we successfuly add an md to the cache.

Successfully add *that* md to the cache?
Or any md from that dirguard?

I meant, we remove *that* md from the md_fetch_fail_cache if we manage to fetch *that* md from any dir.

I think this is ok, as long as we ask for mds in large enough batches.

2) We add another entry_guard_restriction_t restriction type in guards_choose_dirguard(). We currently have one restriction type which is designed to restrict guard nodes based on the exit node choice and its family. We want another type which uses a smartlist and restricts dirguards based on whether we have failed to fetch an md from that dirguard. We are gonna use this in step 3.

3) In directory_get_from_dirserver() we query the md failure cache and pass any results to directory_pick_generic_dirserver() and then to guards_choose_dirguard() which uses the new restriction type to block previously failed dirguards from being selected.

Do we block dirguards that have failed to deliver an md from downloads of that md?
Or do we block dirguards that have failed to deliver any mds from downloads of any md?

Yes, that's a good question that I forgot to address in this proposal.

I guess my design above was suggesting that we block dirguards "that have failed to deliver any mds from downloads of any md", until those mds get fetched from another dirserver and get removed from the failure cache.

I think this is the behaviour we want: trying each dir server for each specific md will mean that we time out, because there are more mds than there are dir servers.

There are two cases when this will cause us to fall back to the authorities:

  • we download a new consensus from the authorities, and they are the only ones with some of the mds in it
  • for some reason, an md referenced in the consensus is not mirrored correctly by relays or authorities (this would be a serious bug in tor)

To avoid this happening when it isn't necessary, we should expire failure cache entries after a random time. Maybe it should be the time when we expect dir servers to fetch a new consensus and new mds. I think this is 1-2 hours, but check dir-spec for the exact details. Or we could expire md failure caches each time we get a new consensus. That would be easier.

ACK. Based on our discussion above, I think the implementation can be simplified since we decided to go with the "block dirguards that have failed to deliver any mds from downloads of any md" approach:

Hence, instead of keeping track of which mds we failed to download from which relays, we can just keep track of the relays that have outdated md information without caring about which mds they failed to serve us. This simplifies things a lot from an engineering perspective since we don't need to map mds to relays. We can just keep an outdated_dirserver_list smartlist with the list of outdated dirservers and ignore those when we try to fetch mds.

This is also consistent with my empirical experience, where most dirservers will usually provide us with all the mds we asked them, except from a few dirservers which would refuse to give us 10 mds or so for a while. So we can just ban those dirservers for a while using the above logic.

And I agree with you, we should wipe the outdated_dirservers_list list everytime we fetch a new consensus. Should we also clear it at any other point? Maybe we should not let it grow to a huge size (cap it?).

I started implementing the original implementation plan today, before I realized the above simplification, so I will have to change some code to do this new design. I estimate that I will have an initial branch here early next week including unittests.

Onwards!

comment:12 in reply to:  11 Changed 6 weeks ago by teor

Replying to asn:

And I agree with you, we should wipe the outdated_dirservers_list list everytime we fetch a new consensus. Should we also clear it at any other point? Maybe we should not let it grow to a huge size (cap it?).

If we are clearing it on every consensus, and doing exponential backoffs (average 2.5x) on every failure, then the list can't grow much beyond log_2(3*60*60) = 14 entries. (After 3 hours, we should either stop trying because our consensus is not live, or we should get another consensus and clear the list. Or, if we keep trying with reasonably live consensuses, the limit will be log_2(24*60*60) = 17 entries.) So let's log a BUG() warning when the list has > 30 entries, because something is wrong with our logic if that happens.

I'm not sure if we should clear the list when it gets too big: it seems like that could trigger slow zombie behaviour, if clients keep on retrying a microdescriptor that doesn't exist. So we have to do something different at that point. And we have to set the point early enough that clients get all the microdescs they need within a minute or so.

So, when is the list too big?
(Or when have we waited too long?)
Should we mark guards down if they depend on a microdesc we can't get?
Should we give up until the next consensus?
Should we try a fallback or an authority?
Should we do something different if we're waiting for an important (primary guard) microdesc?

Maybe we need another ticket to answer these questions.
Because I think some of them can wait until we see how this change performs.

comment:13 Changed 5 weeks ago by asn

Status: newneeds_review

Hello. I pushed my branch at bug23817 in my repo.

Some info:

  • It's a basic failure cache that works in the most basic way: If a dirserver fails to serve an md, we blacklist it until we get a new consensus and skip it. Is this too harsh?
  • We don't do this for bridges because we might have only one dirserv basically.
  • We log a warn if the list grows more than 30 elements long because of comment:12.

The code is pretty clean I think and includes a unittest.

comment:14 Changed 5 weeks ago by asn

Keywords: spec-change added

This also warrants a spec change.

comment:15 Changed 5 weeks ago by nickm

Cc: teor added

Quick notes, not comprehensive:

  • The changes file doesn't say which version this is a bugfix on. (Does "make check" pass?)
  • Should this be a backport candidate for any earlier versions?
  • It looks like the first two commits on this branch are actually part of #23862, and already merged into 0.3.2?
  • Minor: The relay_digest argument to dir_microdesc_download_failed() would be better named "dir_id" or something, since it's the identity of the failing directory server?
  • Digestmap_t would be a better type to use for outdated_dirserver_list, but we can fix that later if need be.
  • Should entries on outdated_dirserver_list expire after some amount of time, in addition to just "whenever we get the next consensus?"
  • I wonder if we can think of a better name for this than "outdated dirserver" -- it's not outdated itself -- it just failed to give us microdescriptors for some consensus we had.
  • Do we check to make sure that the consensus is fairly recent before marking a dirserver as "outdated" in this way?
  • Maybe we should make sure that we never mark an authority as outdated?

Adding teor in cc -- asn asked if you could review this patch too. I'd like to merge it in the alpha coming out in a couple of days, if possible, though I understand you might not be able to review on that schedule.

comment:16 Changed 5 weeks ago by asn

Cc: asn added

comment:17 in reply to:  15 Changed 5 weeks ago by teor

Replying to nickm:

Quick notes, not comprehensive:

  • The changes file doesn't say which version this is a bugfix on. (Does "make check" pass?)

Some release early in the 0.3.0 series, probably 0.3.0.1-alpha.

  • Should this be a backport candidate for any earlier versions?

0.3.0 and 0.3.1.

  • It looks like the first two commits on this branch are actually part of #23862, and already merged into 0.3.2?
  • Minor: The relay_digest argument to dir_microdesc_download_failed() would be better named "dir_id" or something, since it's the identity of the failing directory server?
  • Digestmap_t would be a better type to use for outdated_dirserver_list, but we can fix that later if need be.
  • Should entries on outdated_dirserver_list expire after some amount of time, in addition to just "whenever we get the next consensus?"

This is potentially dangerous, because it could create slow zombies.
If we do this, 1 hour (consensus interval), 3 hours (live consensus), or 24 hours (reasonably live consensus) seem like reasonable expiry times, depending on when we stop fetching microdescs.

  • I wonder if we can think of a better name for this than "outdated dirserver" -- it's not outdated itself -- it just failed to give us microdescriptors for some consensus we had.

It's a dirserver that has a consensus that we don't.

  • Do we check to make sure that the consensus is fairly recent before marking a dirserver as "outdated" in this way?

We should check if our consensus is recent, and try to get a newer one.

  • Maybe we should make sure that we never mark an authority as outdated?

Yes, I think this is #23863: rather than marking an authority outdated, we should mark the relay with the missing microdesc as dead.
Until then, we should log a warning with the authority and specific microdesc id rather than marking the authority as dead.
(Is it possible for an authority to be out of sync and not serve the latest microdescs? What should happen is that it should adopt the latest majority consensus, download its microdescs, and serve them.)

Adding teor in cc -- asn asked if you could review this patch too. I'd like to merge it in the alpha coming out in a couple of days, if possible, though I understand you might not be able to review on that schedule.

Referencing a trac comment is fragile, let's summarise the exponential backoff reasoning instead:

(see
+ * #23817 comment:12 for teor's argument)

Something like "since we use exponential backoff for directory fetches, clients should not fetch microdescs more than log2(3*3600) = 14 times per consensus. The backoff is random between last+1 and last*4, so we allow some extra fetches.".

Would it help to have the log contain the missing microdesc IDs, or at least the first N of them?

relay_is_outdated_dirserver should use smartlist_contains_string for consistency with relay_note_outdated_dirserver.

comment:18 Changed 5 weeks ago by asn

OK, I pushed a branch bug23817_v2 with the following changes:

  • It's now rebased on latest master (I will also prepare an 032 branch)
  • Renames relay_digest to dir_id in directory.c.
  • Adds a log message for failed mds.
  • Does not add dirauths as outdated dirservers.
  • Cleans up the outdated list if it grows above 30 elements.

A few notes:

  • I'm not checking if we have a recent consensus when we blacklist dirservers, as Nick suggested, which might actually be a problem. I think teor's suggestion of "check if our consensus is recent and try to get a newer one" is a whole project of its own that warrants its own ticket (or not?). What should we do here? Maybe we should not register outdated dirservers if we don't have a live consensus?
  • teor, I'm not sure if I agree with your exponential backoff + list size argument, since IIUC the exponential backoff applies only when we fail to fetch the same md multiple times, whereas the outdated list can overgrow just by failing many fetches for different mds. In any case, I opted for resetting the list after 30 arguments, which is a bit arbitrary but perhaps can save us from any surprising issues (?).
  • I did not reset the list based on elapsed time because of teor's argument about clients fetching consensuses every 1 hour or so. Let me know if you don't like this.
  • I renamed relay_digest to dir_id in directory.c. You want me to do the same in the microdesc.c fail cache?
Last edited 5 weeks ago by asn (previous) (diff)

comment:19 Changed 5 weeks ago by nickm

Maybe we should not register outdated dirservers if we don't have a live consensus?

I think that would be fine.

comment:20 in reply to:  19 Changed 5 weeks ago by asn

Replying to nickm:

Maybe we should not register outdated dirservers if we don't have a live consensus?

I think that would be fine.

I pushed a fixup for this. I also force-pushed because I had left a log_warn() accidentally.

comment:21 Changed 5 weeks ago by nickm

Status: needs_reviewmerge_ready

That change looks okay. I'll wait to see if Teor says "no" and otherwise, I'll merge.

Rationale: We should test this in 0.3.2, for possible backport. If it breaks alpha, we put out another alpha fast.

comment:22 in reply to:  18 Changed 5 weeks ago by teor

I am ok to merge this as-is, but let's think about the remaining issues in other tickets.

Also, this comment is misleading:

/* Is our guard an outdated dirserver? */

It would be better as:

/* Last time we tried to fetch microdescs, was this directory mirror missing any we asked for? */

Replying to asn:

OK, I pushed a branch bug23817_v2 with the following changes:

  • It's now rebased on latest master (I will also prepare an 032 branch)

Should we prepare an 030 branch instead/as well?

  • Renames relay_digest to dir_id in directory.c.
  • Adds a log message for failed mds.
  • Does not add dirauths as outdated dirservers.

Hmm, I wonder if a BUG() is the right thing to do here. It's probably ok in an alpha, but if a dirauth is out of sync, clients will log this as a BUG(), even though it's not their bug. (In most cases, if a dirauth is out of sync, that should self-correct, because it will be dropped from the consensus. Except for IPv6-only clients, which fetch mds from fallbacks and authorities so they can bootstrap.)

In any case, this should be rare.

  • Cleans up the outdated list if it grows above 30 elements.

I think this is ok for the moment (it is no worse than the previous behaviour), but we should think about setting this limit low, and then trying an authority when we reach it (and then giving up on the md). That's a separate ticket - #23863.

A few notes:

  • I'm not checking if we have a recent consensus when we blacklist dirservers, as Nick suggested, which might actually be a problem. I think teor's suggestion of "check if our consensus is recent and try to get a newer one" is a whole project of its own that warrants its own ticket (or not?). What should we do here? Maybe we should not register outdated dirservers if we don't have a live consensus?

Seems to make sense to me.

  • teor, I'm not sure if I agree with your exponential backoff + list size argument, since IIUC the exponential backoff applies only when we fail to fetch the same md multiple times, whereas the outdated list can overgrow just by failing many fetches for different mds. In any case, I opted for resetting the list after 30 arguments, which is a bit arbitrary but perhaps can save us from any surprising issues (?).

I think there is a small risk of a client -> relay DDoS here, but it's no worse than the previous behaviour.

  • I did not reset the list based on elapsed time because of teor's argument about clients fetching consensuses every 1 hour or so. Let me know if you don't like this.

Seems fine to me.

comment:23 Changed 5 weeks ago by teor

Ok, the fixup looks good to me, let's get this merged.

comment:24 Changed 5 weeks ago by teor

Status: merge_readyneeds_revision

This fails to compile in recent clang with:

src/or/microdesc.c:85:14: error: no previous extern declaration for non-static
      variable 'outdated_dirserver_list'
$ clang --version
Apple LLVM version 9.0.0 (clang-900.0.38)
Target: x86_64-apple-darwin16.7.0
...

(I have no idea what non-Apple clang version that corresponds to.)

comment:25 Changed 5 weeks ago by teor

Also, rst in the unit tests needs to be declared before any gotos, and set to NULL at declaration time:

src/test/test_entrynodes.c:1810:3: error: variable 'rst' is used uninitialized
      whenever 'if' condition is true [-Werror,-Wsometimes-uninitialized]
  tt_ptr_op(g2, OP_EQ, g);
  ^~~~~~~~~~~~~~~~~~~~~~~
./src/ext/tinytest_macros.h:166:2: note: expanded from macro 'tt_ptr_op'
        tt_assert_test_type(a,b,#a" "#op" "#b,const void*,              \
        ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
./src/ext/tinytest_macros.h:144:2: note: expanded from macro
      'tt_assert_test_type'
        tt_assert_test_fmt_type(a,b,str_test,type,test,type,fmt,        \
        ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
./src/ext/tinytest_macros.h:136:7: note: expanded from macro
      'tt_assert_test_fmt_type'
                if (!tt_status_) {                                      \
                    ^~~~~~~~~~~
src/test/test_entrynodes.c:1820:32: note: uninitialized use occurs here
  entry_guard_restriction_free(rst);

comment:26 Changed 5 weeks ago by teor

./changes/bug23817:
	Don't use a # before ticket numbers. ('bug 1234' not '#1234')
	Ticket marked as bugfix, but does not say 'Fixes bug XXX'

comment:27 Changed 5 weeks ago by nickm

I've got the 0.3.2 changes squashed and rebased as bug23817_v2_032_squashed, including a fix for the warning teor notes above.

comment:28 Changed 5 weeks ago by teor

Also, it looks like it's going to fail all the chutney tests:

FAIL: basic-min
FAIL: bridges-min
...

And it logs very noisy warnings that start like this:

Warning: Bug: Non-fatal assertion !(router_get_trusteddirserver_by_digest(relay_digest)) failed in microdesc_note_outdated_dirserver at src/or/microdesc.c:114. Stack trace: (on Tor 0.3.3.0-alpha-dev fd33f85c044310ba) Number: 1

This might need a rethink.

comment:29 Changed 5 weeks ago by nickm

bug23817_v2_032_squashed now fixes some of the above issues, but still needs rebasing onto 0.3.0.

comment:30 Changed 5 weeks ago by asn

bug23817_v2_032_squashed looks good. We also need to address the warning that teor mentioned in comment:28, perhaps we can remove the BUG() from the dirauth check?

Also, the test-network-all tests seem to be broken still in maint-0.3.2 because of sandbox failures so it's not easy to integration test it.

Last edited 5 weeks ago by asn (previous) (diff)

comment:31 in reply to:  30 Changed 5 weeks ago by teor

Replying to asn:

bug23817_v2_032_squashed looks good. We also need to address the warning that teor mentioned in comment:28, perhaps we can remove the BUG() from the dirauth check?

Also, the test-network-all tests seem to be broken still in maint-0.3.2 because of sandbox failures so it's not easy to integration test it.

Ah, they work for me, but I'm on a Mac :-)
I can test tomorrow (~12 hours) if you'd like.

comment:32 Changed 5 weeks ago by asn

I pushed bug23817_032_asn which is nick's bug23817_v2_032_squashed squashed to the very latest maint-0.3.2, plus a patch which removes the BUG from the dirauth detection.

It seems like this branch will fail the bridges-min integration test some times.

I'm not sure what's causing it but I noticed that the bridge 003br will fail to download mds from test002r and it will mark it as outdated dirserver. I also saw the same behavior where 004bc blacklisted its bridge because it didn't serve it mds. Perhaps that's causing trouble given the little amount of nodes on the network. :/

Last edited 5 weeks ago by asn (previous) (diff)

comment:33 Changed 5 weeks ago by teor

I thought you were disabling outdated dirservers for relays that bridges are using as bridge clients?
That's what you said in comment 13.

comment:34 Changed 5 weeks ago by teor

Hmm, maybe we should only exclude bridges when there is a small number of them.
We wouldn't want to do it on Tor Browser, which has ~20 bridges.

If we make that change, we should probably also make the change in networks with very restricted sets of guards. We have a guard context for that, right?

comment:35 in reply to:  33 Changed 4 weeks ago by asn

Replying to teor:

I thought you were disabling outdated dirservers for relays that bridges are using as bridge clients?
That's what you said in comment 13.

True. That was not it. The restriction was not applied in that case. Need to debug some more what's going on.

comment:36 Changed 4 weeks ago by asn

Status: needs_revisionneeds_review

OK guys I pushed bug23817_032_asn which is Nick's bug23817_032_asn with the following changes:

  • Rebased on latest origin/maint-0.3.2
  • Removes BUG from dirauth check
  • Skips dirserver restrictions on restricted guard selections and bridge selections with less than 10 bridges (yes another magic number...).

It passes all test-network-all tests for me. Please also test it yourself!

comment:37 Changed 4 weeks ago by nickm

I'd like to rename TOO_FEW_BRIDGES_FOR_RESTRICTION to TOO_FEW_BRIDGES_FOR_MD_RESTRICTION to clarify that it doesn't circumvent the restriction that prevents choosing the exit as the guard.

I don't know if I agree about "Don't set a restriction if we are on a restricted guard selection". Shouldn't looking at the number of filtered guards be sufficient?

comment:38 in reply to:  37 Changed 4 weeks ago by asn

Status: needs_reviewneeds_revision

Replying to nickm:

I'd like to rename TOO_FEW_BRIDGES_FOR_RESTRICTION to TOO_FEW_BRIDGES_FOR_MD_RESTRICTION to clarify that it doesn't circumvent the restriction that prevents choosing the exit as the guard.

Agreed.

I don't know if I agree about "Don't set a restriction if we are on a restricted guard selection". Shouldn't looking at the number of filtered guards be sufficient?

Hm, yes. I did the restricted guard selection set to guarantee that it won't apply to people who have pinned a single entry guard or something. Checking the number of filtered guards in that case could make sense. We could check the number of filtered guards against TOO_FEW_BRIDGES_FOR_MD_RESTRICTION (and maybe rename it appropriately).

comment:39 Changed 4 weeks ago by nickm

I've tried to implement the approach above in a branch bug23817_032_asn_a, based on your code. In a different branch, called bug23817_032_asn_b, I've taken an approach that might be simpler, using existing functions. Do you like one of those?

comment:40 Changed 4 weeks ago by nickm

Status: needs_revisionneeds_review

comment:41 in reply to:  39 Changed 4 weeks ago by asn

Status: needs_reviewmerge_ready

Replying to nickm:

I've tried to implement the approach above in a branch bug23817_032_asn_a, based on your code. In a different branch, called bug23817_032_asn_b, I've taken an approach that might be simpler, using existing functions. Do you like one of those?

I like your filtered approach Nick.

I think I like (a) more than (b) because num_reachable_filtered_guards() tries to do a bit too many things at once (resets timeouts, and also only counts reachable filtered guards instead of just filtered). (a) seems simpler to understand.

In (a) we can also constify the entry_guard_t * inside the smartlist loop. I tested it on the real net and on chutney test-network-all and seems to work well (and restrictions seem to apply correctly).

Marking this as merge_ready.

comment:42 Changed 4 weeks ago by nickm

Okay. Let's give teor another change to look at it, if he has time?

comment:43 Changed 4 weeks ago by nickm

made a squashed version as bug23817_032_asn_a_squashed

comment:44 Changed 4 weeks ago by nickm

I can't see any more bugs or pending issues here. So I'm going to merge this to 0.3.2 now, in hopes that it gets some testing over the weekend before the next alpha release next week. Tim, if you have time to look at it next week anyway, it would probably be good to get another round of (post-merge) review on this.

I tried again to rebase onto 0.3.1, in case we decide to backport there. Most of the conflicts came from the unit tests, so I have two new branches now: a bug23817_031 that contains everything but the unit tests, and bug23817_tests_032 that has the tests only.

comment:45 Changed 4 weeks ago by nickm

Milestone: Tor: 0.3.3.x-finalTor: 0.3.1.x-final

comment:46 Changed 4 weeks ago by asn

031 branch lgtm and passes both test-network-all and manual real network test.

comment:47 Changed 4 weeks ago by teor

The code looks good to me, and everything passes.

I have added some questions to #24113 and #23863 about possible changes to this code when we do those tickets.

I have one question that we should resolve before backporting to 0.3.1 or releasing 0.3.2:

In should_set_md_dirserver_restriction(), what if we have more than 10 filtered guards, but less than 10 of them are actually contactable or running?

For example, this can happen with the default Tor Browser bridges if a client can only contact bridges over IPv6, but hasn't set any reachability options. (There are many Tor Browser bridges, but only one of them has IPv6.)

(I can't remember if filtered guards are guaranteed to be running or not.)

comment:48 Changed 4 weeks ago by nickm

Filtered guards aren't guaranteed to be running; for that, we would want to look at "usable filtered guards" as in my approach b.

comment:49 Changed 4 weeks ago by teor

Status: merge_readyneeds_revision

So, let's always track the md fail restriction, but stop applying it when the number of reachable filtered guards is below some threshold?
This will probably mean extracting the const counting part out of num_reachable_fultered_guards().

Otherwise, we might end up blocking someone's only working bridge, and that would be worse than the original bug.

comment:50 in reply to:  49 Changed 3 weeks ago by asn

Replying to teor:

So, let's always track the md fail restriction, but stop applying it when the number of reachable filtered guards is below some threshold?

Hm, that might be a reasonable improvement that could help some edge-cases. That would need some light refactoring. We would need to refactor that so we always apply the restriction, but check the threshold in guard_obeys_md_dirserver_restriction() before enforcing the restriction.

FWIW, this branch seems to have been merged in master and 0.3.2 so we would need to fixup those two trees.

comment:51 Changed 3 weeks ago by asn

Status: needs_revisionneeds_review

Please see my branches bug23817_usable_filtered_032 and bug23817_usable_filtered_033 which implement teor's comments above and are basically true to the bug23817_032_asn_b from nickm's comment:39 (but a bit simplified).

Passes real network test and test-network-all for me.

Last edited 3 weeks ago by asn (previous) (diff)

comment:52 Changed 3 weeks ago by nickm

So, num_reachable_filtered_guards() is O(N) in the total number of guard nodes in the network; I don't think we want to re-run it for every guard that we check in guard_obeys_md_dirserver_restriction, or this will be an O(N2) computation.

comment:53 Changed 3 weeks ago by nickm

Milestone: Tor: 0.3.1.x-finalTor: 0.3.2.x-final

comment:54 in reply to:  52 Changed 3 weeks ago by asn

Replying to nickm:

So, num_reachable_filtered_guards() is O(N) in the total number of guard nodes in the network; I don't think we want to re-run it for every guard that we check in guard_obeys_md_dirserver_restriction, or this will be an O(N2) computation.

Thanks for pointing this out. I think my idea of moving the guard-size check on restriction enforcing time, instead of keeping it at restriction creation time was a bad one.

The guard restriction is applied on the circuit_guard_state_t which gets applied on the dir_connection_t so everytime we want to fetch new mds we will do the guard-size check and create a new restriction, which works fine with the current design, so no need to change it.

I have two new branches with annoying names:
bug23817_usable_filtered_033_v2 and bug23817_usable_filtered_032_v2 which should be the minimal change here.

The way I see it, moving from checking filtered guards to checking reachable filtered guards, moves us from overblocking to underblocking which seems better and less disturbing. That is, when we checked filtered guards we could blacklist guards even tho most of them don't actually work (like teor's example in comment:47). Now that we check reachable filtered guards we could potentially not blacklist guards when we actually should (e.g. if the network was down, and we marked all our guards as unreachable, and then one guard failed to give us an md, we will not blacklist it just because the other guards were found unreachable).

Let me know how you feel about this one.

Last edited 3 weeks ago by asn (previous) (diff)

comment:55 Changed 3 weeks ago by nickm

Did you forget to upload these branches?

comment:56 Changed 3 weeks ago by nickm

(If not, please let me know where to find them.)

comment:57 Changed 3 weeks ago by nickm

Milestone: Tor: 0.3.2.x-finalTor: 0.3.1.x-final
Status: needs_reviewmerge_ready

Thanks for the upload! I've cherrypicked the fix onto bug23817_031, and re-merged that into 0.3.2 and forward. Calling that a backport candidate again.

comment:58 Changed 43 hours ago by nickm

Resolution: fixed
Status: merge_readyclosed

merged to 0.3.1 too.

Note: See TracTickets for help on using tickets.