Opened 3 years ago

Closed 6 weeks ago

Last modified 6 weeks ago

#13339 closed enhancement (implemented)

Prop140: Complete Consensus diffs / Merge GSoC project

Reported by: mvdan Owned by: nickm
Priority: High Milestone: Tor: 0.3.1.x-final
Component: Core Tor/Tor Version: Tor: 0.2.7
Severity: Normal Keywords: gsoc, merge, tor-client, prop140, 027-triaged-1-in, 028-triaged, pre028-patch, tor-dos, low-bandwidth, nickm-deferred-20160905, tor-03-unspecified-201612, sponsor4, TorCoreTeam201703
Cc: nickm, sebastian, yawning Actual Points:
Parent ID: Points: parent
Reviewer: Sponsor: Sponsor4

Description

Google Summer of Code finished over a month ago, and during this time I've been tidying up my code a bit and reading it for the merge. You will find it on github:

https://github.com/mvdan/tor

This ticket is for the sole purpose of following the merge process and its progress. But as always I'm on IRC and mail if you want to contact me directly.

I just rebased against master this morning. Nick and Sebastian have been reviewing my code over the summer, but of course more sets of eyes are needed.

The test coverage for the diff generation and application is fine (see test_consdiff.c), but there aren't any tests for the stuff I wrote to wire it into serving and fetching consensus diffs. Not really sure how to go about that, can't really promise I'd have the time to dive into it.

And regarding commit messages and changelog entries, I pretty much went with my instinct. Chances are they can be improved - the commit messages for future reference and the changelog entries for future release changelogs - so criticism is welcome.

Child Tickets

TicketTypeStatusOwnerSummary
#21643defectclosednickmProp140: Extract, test, revise, and clean the diff code
#21644taskclosednickmProp140: Fuzz the diff and patch code
#21647enhancementclosednickmProp140: directory caches cache multiple past diffs or consensuses
#21648defectclosednickmprop140: Caches generate diffs as appropriate
#21649enhancementclosednickmprop140: Caches serve diffs on request
#21650enhancementclosednickmprop140: Clients request diffs and handle diffs in replies
#21673defectclosednickmprop140: Handle signatures correctly
#22143defectclosednickmImplement May 3 updates to diff format in prop140
#22148defectclosednickmprop140: conformance to proposal, unhandled corner cases
#22149defectclosednickmprop140: Update dir-spec with prop140 protocols

Change History (64)

comment:1 Changed 3 years ago by nickm

  • Keywords tor-client prop140 added
  • Milestone set to Tor: 0.2.6.x-final
  • Priority changed from minor to major
  • Status changed from new to needs_review

comment:2 Changed 3 years ago by mvdan

  • Keywords changed from gsoc,merge tor-client prop140 to gsoc merge tor-client prop140

comment:3 Changed 3 years ago by tom

I didn't look very comprehensively, and just at consdiff. I could be missing context here, but it seems like there are some scenarios where consdiff_gen_diff would not free ed_diff? (I'm looking at https://github.com/mvdan/tor/blob/consdiff-5/src/or/consdiff.c#L737 )

1) gen_ed_diff succeeds but apply_ed_diff fails
2) gen_ed_diff succeeds, apply_ed_diff succeeds, but the "the generated ed diff did not generate the target consensus successfully"

comment:4 Changed 3 years ago by dgoulet

First of all, the test don't compile. Multiple warnings (too many to paste here but here is an idea):

src/test/test_consdiff.c:25:3: warning: implicit declaration of function ‘test_eq_ptr’ [-Wimplicit-function-declaration]
   test_eq_ptr(sl, sls->list);
src/test/test_consdiff.c:52:3: warning: implicit declaration of function ‘test_eq’ [-Wimplicit-function-declaration]
   test_eq(3, smartlist_slice_string_pos(sls, "a"));
   ^
src/test/test_consdiff.c:81:3: warning: implicit declaration of function ‘test_memeq’ [-Wimplicit-function-declaration]
   test_memeq(e_lengths1, lengths1, sizeof(int) * 6);
src/test/test_consdiff.c:161:3: warning: implicit declaration of function ‘test_assert’ [-Wimplicit-function-declaration]
   test_assert(!bitarray_is_set(changed1, 0));
src/test/test_consdiff.c:920:12: error: ‘legacy_test_helper’ undeclared here (not in a function)
   { #name, legacy_test_helper, 0, &legacy_setup, test_consdiff_ ## name }

Ok that's a big diff chunk of code. There are a lot of commits that could be squashed together here to make things easier. For instance, I'm thinking of from the older one up to when consdiff.c is created and consdiff_client/_server.c are deleted.

So I see in proposal 140 that multiple consensus hash can be fetched by the client but this implementation only uses one single hash. Is it the spec that is out dated or there is no use to fetch multiple consensus now?

I'll skip all coding style issue here for now since you told me you might change it. Here some minor thing I've found while going over the code. I'ven't yet finish a full review

src/or/consdiff.h

  • Clarify what "list" contains.
  • "len" maybe should be renamed to something more meaninful because it does NOT represent the len of the list but the range that should be used in that list (of what I understand)?

src/or/consdiff.c

  • You should set "network-status-diff-version" in a static const variable at the begining of the file. You are using it twice and since it's part of a public ABI, good practice to have that declared somewhere instead of in the middle of the code. Same goes for "hash" in consdiff_get_digests().
  • Same goes for "X-Or-Diff-From-Consensus:" in directory.c

src/or/networkstatus.c

  • I would go for switch/case when you check consensus_flavor_t since it's an enum and the compiler warns you when you forget one. Just a cool extra useful protection. In networkstatus_get_latest_consensus_by_flavor() and networkstatus_get_latest_consensus_mmap_by_flavor()

src/or/dirserv.c

  • connection_dirserv_add_cons_diff_bytes_to_outbuf(): this one looks really like connection_dirserv_add_networkstatus_bytes_to_outbuf except the lookup if done somewhere else. I feel like this one could get refactor to either take an enum type of what we want or "lookup fct pointer" instead of duplication.

Ok I'll stop for now but I have to say that it's good work :). Will do another run at it after your comments/changes.

comment:5 Changed 3 years ago by nickm

The compilation interface is not mvdan's fault: we deprecated the old unit test interface out from under him. Fortunately, we have an automated set of tools to fix it.

I've run them, and the result is branch consdiff-5-fixed in my public repository.

comment:6 Changed 3 years ago by mvdan

Thanks for pointing out that leak, tom. Will fix it.

And great to see all those comments, dgoulet! :)

Nick is right, I did notice I was using the deprecated method of testing but didn't look into it since it worked. I must have rebased against master some time later without noticing that the tests weren't compiling anymore. Will merge nickm's automated fix, thanks!

Regarding the rest, I'll try having a set of commits out by tomorrow.

One question though:

There are a lot of commits that could be squashed together here to make things easier. For instance, I'm thinking of from the older one up to when consdiff.c is created and consdiff_client/_server.c are deleted.

I did think about this when doing rebases during the summer - of course the initial number of commits was much larger - but I was often unsure how to rewrite the history properly.

For example, my reasoning behind leaving the old files there is that you can use git log/blame/etc with --follow to see where all the lines come from, without having a moderate chunk of code appearing from nowhere in consdiff.c. Or perhaps that is the best option?

I will try to rebase stuff like the test fixes into each of the commits that added tests, of course. That'll probably be the sixth branch.

comment:7 Changed 2 years ago by dgoulet

  • Status changed from needs_review to needs_revision

Changing to need_revision until you have a new branch/fixes. Thanks!

comment:8 Changed 2 years ago by nickm

I gave it a look-over too. Here's what I found:

util.c

  • Maybe we should make sure that the rm_rf function won't follow symlinks. Just in case.

consdiff.c

  • I need to review this later

consdiff.h

  • Does anything outside of consdiff.c use the structure here?

directory.c:

  • {get,set}_has_sent_bad_diff: I would be more comfortable if these assertions were just log_ratelim(LOG_WARN, LD_BUG) calls instead.
  • resolve_fetch_consensus:
    • It's stupid, but I'd prefer to see a check vs INT_MAX before casting body_len to int.
    • You need to pass an mmap to tor_munmap, not tor_free
  • connection_dir_client_reached_eof: We should probably log when we get a bad diff, and who sent it to us.
  • directory_handle_command_get:
    • tor_memdup() is better than malloc-plus-copy.
    • dir_fps might need a better name now.


dirserv.c

  • dirserv_lookup_cached_consensus_diff_by_digest should probably be renamed to ...by_hexdigest256.
  • The documentation for old_cached_consensus_by_digest should mention the types of the keys and the values.
  • new_cached_dir_comp looks to me like it's going to cause a memory leak or a double-free somehow.
  • dirserv_refresh_stored_consensuses should probably do something to check that the digest format is right, the date format is right, and that the consensuses are not corrupted.
  • Use char buf[constant]; tor_snprintf(buf, sizeof(buf)...), not char buf[constant]; tor_snprintf(buf, constant...)
  • Use the %ld printf format, not %li. (Almost nobody uses %i)
  • I think we have an alternative to atol that checks for errors better. Is it tor_parse_ulong?
  • In dirserv_remove_old_consensuses, you can get the current index into the smartlist iteration by looking at c_sl_idx. You don't need to have a separate i.
  • dirserv_update_consensus_diffs: I need to review this more later.
  • connection_dirserv_add_cons_diff_bytes_to_outbuf: does this decref the cached object correctly? Is this duplicate code?

networkstatus.c

  • networkstatus_get_old_consensuses_to_keep -- this can just use int, instead of int32.
  • current_{ns,md}_consensus_mmap needs to get passed to tor_munmap if it's set before we mmap a new one.

configuration

  • Instead of a boolean, maybe options->SaveConsensuses should be a number to save, or a maximum number of bytes to use when saving them?

Later:

  • I'd like to see fewer copies of strings done here. There's an easy way to do that, I think.
  • How expensive is dirserv_update_consensus_diffs? It seems kind of pricey. Maybe it needs to happen in the background?

comment:9 Changed 2 years ago by mvdan

I've started a new rebased branch, consdiff-6. What I've done so far:

  • Rebase against master and fix numerous conflicts
  • Replace usage of deprecated test_* functions
  • Replace usage of deprecated legacy_test_helper

Of course I still have all the fixes suggested above left to do. But those were the first steps to get my consdiff branch back up compiling and passing the tests :)

comment:10 Changed 2 years ago by mvdan

Okay, I just realised that nickm already did the test fixing, and in a slightly different way. So I cherry picked his fixes into consdiff-6 and then applied some check-spaces fixes on top.

I have now compiled a TODO list from all of your comments. I'll work through them, not sure how long it will take me but it will be a few days at least.

Quick question for dgoulet:

  • I think the usage of 'len' in smartlist_slice is correct. It means the length of the slice. It's similar to how slices in Go are defined (in fact I based my struct definition on that). What if I just improved the comments a bit?

comment:11 Changed 2 years ago by mvdan

Another question for dgoulet, regarding the declaration of "X-Or-Diff-From-Consensus" as a static const char* in directory.c - makes sense, but others like "X-Desc-Gen-Reason" don't do it. So I'm guessing that this should eventually be fixed for all of those static strings?

comment:12 follow-up: Changed 2 years ago by mvdan

Some more comments, for nickm this time :)

  • So in tor_rmdir, you say that we should check against S_IFLINK (that it is false) when checking for S_IFDIR. I thought that stat ran on the symlink, not on its target? In other words, we couldn't have both be true at the same time. If it's a symlink and it's not a folder, we delete it. In the opposite case, we enter the dir since we're not following a symlink.
  • smartlist_slice_t in consdiff.h instead of consdiff.c - this is mainly because back when I added it I wasn't sure whether I'd need it in other places. But also because I was thinking that the structure and its functions might be useful to other parts of Tor. After all, slicing a list is a very generic tool, and it sounds simple and cheap to me. Of course it would need polishing to be made public, so I think I'll just move it to consdiff.c for now.

Regarding what both you and dgoulet have said about the add_bytes function - GSoC was nearing its end and I was getting a bit confused by all the "serve bytes/files" code in dirserv.c, so what I did was take a function that kind of did what I wanted and tweaked it for my purposes. This has two obvious problems, the first that it duplicates code, but the second that I'm not exactly sure whether what I did is correct or not.

In other words, I would appreciate it if you could help me here. I remember nickm mentioning that this code has barely been touched in years, and that it's a tad confusing since it's gotten so complex. So I'd rather not do it alone :)

Oh, and I'll definitely be attending the winter dev meeting in Valencia in March. Will any of you guys be there?

comment:13 follow-up: Changed 2 years ago by mvdan

Forgot one thing for nickm:

{get,set}_has_sent_bad_diff: I would be more comfortable if these assertions were just log_ratelim(LOG_WARN, LD_BUG) calls instead.

I think I understand what you mean there, but I could find no mention of log_ratelim. I do see logs with LD_BUG in other places, but not sure what to do here.

comment:14 in reply to: ↑ 12 Changed 2 years ago by nickm

Replying to mvdan:

Some more comments, for nickm this time :)

  • So in tor_rmdir, you say that we should check against S_IFLINK (that it is false) when checking for S_IFDIR. I thought that stat ran on the symlink, not on its target? In other words, we couldn't have both be true at the same time. If it's a symlink and it's not a folder, we delete it. In the opposite case, we enter the dir since we're not following a symlink.

Maybe we should lstat it then? I worry that this could be used along with a symlink to rm_rf something we didn't intend to. Probably nothing to worry about given this use case, but a bit alarming.

  • smartlist_slice_t in consdiff.h instead of consdiff.c - this is mainly because back when I added it I wasn't sure whether I'd need it in other places. But also because I was thinking that the structure and its functions might be useful to other parts of Tor. After all, slicing a list is a very generic tool, and it sounds simple and cheap to me. Of course it would need polishing to be made public, so I think I'll just move it to consdiff.c for now.

Okay, unless you think that exposing it for testing could help test individual functions.

Regarding what both you and dgoulet have said about the add_bytes function - GSoC was nearing its end and I was getting a bit confused by all the "serve bytes/files" code in dirserv.c, so what I did was take a function that kind of did what I wanted and tweaked it for my purposes. This has two obvious problems, the first that it duplicates code, but the second that I'm not exactly sure whether what I did is correct or not.

In other words, I would appreciate it if you could help me here. I remember nickm mentioning that this code has barely been touched in years, and that it's a tad confusing since it's gotten so complex. So I'd rather not do it alone :)

Okay; I'll try to have a look.

Oh, and I'll definitely be attending the winter dev meeting in Valencia in March. Will any of you guys be there?

I sure will!

comment:15 in reply to: ↑ 13 Changed 2 years ago by nickm

Replying to mvdan:

Forgot one thing for nickm:

{get,set}_has_sent_bad_diff: I would be more comfortable if these assertions were just log_ratelim(LOG_WARN, LD_BUG) calls instead.

I think I understand what you mean there, but I could find no mention of log_ratelim. I do see logs with LD_BUG in other places, but not sure what to do here.

Whoops; the function is actually named "log_fn_ratelim".

comment:16 follow-up: Changed 2 years ago by mvdan

Some more questions:

Nick, you said:

current_{ns,md}_consensus_mmap needs to get passed to tor_munmap if it's set before we mmap a new one.

Am I not running tor_munmap already?

dir_fps might need a better name now.

This name was already introduced when I started my gsoc, so I'm not sure where it originates from.

I'll keep on working on the suggestions that I can get done on my own, about two thirds are already done. It would be great if I could have code reviews for consdiff.c as well as pointers for the dirserv.c add_cons_diff_bytes_to_outbuf as agreed :)

comment:17 in reply to: ↑ 16 Changed 2 years ago by nickm

Replying to mvdan:

Some more questions:

Nick, you said:

current_{ns,md}_consensus_mmap needs to get passed to tor_munmap if it's set before we mmap a new one.

Am I not running tor_munmap already?

I think that you're calling tor_munmap on shutdown, but you might not be calling it on reload.

dir_fps might need a better name now.

This name was already introduced when I started my gsoc, so I'm not sure where it originates from.

Right; this isn't something you need to fix yourself.

I'll keep on working on the suggestions that I can get done on my own, about two thirds are already done. It would be great if I could have code reviews for consdiff.c as well as pointers for the dirserv.c add_cons_diff_bytes_to_outbuf as agreed :)

I'll try!

comment:18 Changed 2 years ago by nickm

Right now this is looking early-0.2.7, I hope I hope I hope.

comment:19 Changed 2 years ago by nickm

  • Milestone changed from Tor: 0.2.6.x-final to Tor: 0.2.7.x-final

comment:20 Changed 2 years ago by nickm

The consdiff.c file looks good to me, but I want to do some more asserts to make sure that we never go off the end of a smartlist or bitarray, etc.

comment:21 follow-up: Changed 2 years ago by mvdan

After a quick chat with Nick, what is left to do is clear to me:

  • Clients will never keep more than one consensus, clarify that in prop140. Make servers give more than one base consensus in the headers when requesting a consensus diff.
  • Figure out the best use of the SaveConsensuses config option. Options (by my personal order of preference, will probably go with the first one):
    • Maximum storage to use on disk (oldest removed first)
    • Maximum number to keep on disk (oldest removed first)
    • Maximum amount of time to keep them for
  • Figure out the write_bytes_to_outbuf stuff - both for code duplication and for the proper functioning of my code.
  • Some other directory.c and dirserv.c improvements suggested by nickm

I also noticed that you guys bumped the standard from c89 to c99, so I did a style/format rewrite adapting to c99. This makes the code a tad more readable, especially some chunks of code in consdiff.c: https://github.com/mvdan/tor/commit/d0a9f85ead92895c524203e13c6ff9af8f9282e7

Apart from those, I only need more eyes on consdiff.c. The ed diff generation stuff is not simple when you first dive into it, so feel free to ping me with any questions you have. Do let me know if any chunks of code are missing comments too.

And one last thing, there are two items on my TODO list for which I need further info:

  • I'd like to see fewer copies of strings done here. There's an easy way to do that, I think.

nickm, what do you mean by 'here'?

  • How expensive is dirserv_update_consensus_diffs? It seems kind of pricey. Maybe it needs to happen in the background?

If we do that, we need some kind of mechanism to not serve any consensus diffs until they are all updated on disk and mmapped correctly. We need a thread-safe way to lock that out until it's complete. It could well get pricey, especially if the user sets a large SaveConsensuses value.

comment:22 Changed 2 years ago by nickm

  • Keywords 027-triaged-1-in added

Marking more tickets as triaged-in for 0.2.7

comment:23 Changed 2 years ago by isabela

  • Points set to medium
  • Version set to Tor: 0.2.7

comment:24 in reply to: ↑ 21 Changed 2 years ago by nickm

Replying to mvdan:

After a quick chat with Nick, what is left to do is clear to me:

[...]

  • I'd like to see fewer copies of strings done here. There's an easy way to do that, I think.

nickm, what do you mean by 'here'?

Let's forget about it for now and see if it matters in practice.

  • How expensive is dirserv_update_consensus_diffs? It seems kind of pricey. Maybe it needs to happen in the background?

If we do that, we need some kind of mechanism to not serve any consensus diffs until they are all updated on disk and mmapped correctly. We need a thread-safe way to lock that out until it's complete. It could well get pricey, especially if the user sets a large SaveConsensuses value.

Hm. This is not a prerequisite for merging this patch then, but it will tell us how urgent it is to do another patch on top of it to background this computation.

comment:25 follow-up: Changed 2 years ago by mvdan

I've addressed most of the comments: https://github.com/mvdan/tor/commits/consdiff

The last commit adds four TODOs, which I think are the only things left to deal with.

TODO: change bool with max size to take up in disk

I'll do this one.

TODO: check that the stored consensus is intact

Not sure how to do this one yet.

TODO: duplicate code from add_networkstatus_bytes_to_outbuf, works but is
probably buggy.

All of this code is confusing to me, so help from someone who initially wrote it would be great.

TODO: might want to do this in the background and have a lock to not
serve consensus diffs until they are updated

What do we want to do about this one after all?

Last edited 2 years ago by mvdan (previous) (diff)

comment:26 Changed 2 years ago by mvdan

Also, I rebased on top of master again. The new branch is called "consdiff" instead of "consdiff-9" because I hope this will be the last rebase before the merge :)

comment:27 Changed 2 years ago by nickm

  • Keywords TorCoreTeam201508 added

comment:28 in reply to: ↑ 25 ; follow-up: Changed 23 months ago by nickm

Replying to mvdan:

I've addressed most of the comments: https://github.com/mvdan/tor/commits/consdiff

The last commit adds four TODOs, which I think are the only things left to deal with.

TODO: change bool with max size to take up in disk

I'll do this one.

Great.

TODO: check that the stored consensus is intact

Not sure how to do this one yet.

Hm. Maybe we should store it along with a digest, or try to parse it before we compute the diff?

TODO: duplicate code from add_networkstatus_bytes_to_outbuf, works but is
probably buggy.

All of this code is confusing to me, so help from someone who initially wrote it would be great.

TODO: might want to do this in the background and have a lock to not
serve consensus diffs until they are updated

What do we want to do about this one after all?

I can do these last two.

The final one will depend on the runtime of the code. How long does it take to recompute all the diffs? If it's a few milliseconds, that's fine. If it's a few hundred milliseconds or worse, we probably need to stick it in another thread.

comment:29 in reply to: ↑ 28 Changed 23 months ago by mvdan

Replying to nickm:

Replying to mvdan:

I've addressed most of the comments: https://github.com/mvdan/tor/commits/consdiff

The last commit adds four TODOs, which I think are the only things left to deal with.

TODO: change bool with max size to take up in disk

I'll do this one.

Great.

I'll do it on top of my current consdiff branch. Will you work on a branch of yours? Feel free to cherry pick my future commits.

TODO: check that the stored consensus is intact

Not sure how to do this one yet.

Hm. Maybe we should store it along with a digest, or try to parse it before we compute the diff?

What if the digest is corrupt? :)

Trying to parse it sounds better. Although that just checks whether it is valid, not whether it is correct.

I can't think of a simple solution to all of this right now. Surely there must be other files that may be corrupt in the filesystem when Tor starts up. What does it do for the rest? Sounds to me like we would be better off with a generic mechanism to check whether the tor data/config dir hasn't been tinkered with.

TODO: duplicate code from add_networkstatus_bytes_to_outbuf, works but is
probably buggy.

All of this code is confusing to me, so help from someone who initially wrote it would be great.

TODO: might want to do this in the background and have a lock to not
serve consensus diffs until they are updated

What do we want to do about this one after all?

I can do these last two.

The final one will depend on the runtime of the code. How long does it take to recompute all the diffs? If it's a few milliseconds, that's fine. If it's a few hundred milliseconds or worse, we probably need to stick it in another thread.

Back when I ran tests on my algorithm code, I did compute times for single test cases. I never tested the speed of the whole diff generation process at startup.

comment:30 Changed 22 months ago by nickm

  • Keywords TorCoreTeam201509 added; TorCoreTeam201508 removed
  • Milestone changed from Tor: 0.2.7.x-final to Tor: 0.2.8.x-final
  • Owner set to nickm
  • Status changed from needs_revision to assigned

comment:31 Changed 22 months ago by nickm

  • Status changed from assigned to needs_revision

comment:32 Changed 21 months ago by nickm

  • Keywords 028-triaged added

comment:33 Changed 21 months ago by yawning

  • Cc yawning added

comment:34 Changed 20 months ago by nickm

  • Keywords pre028-patch added

comment:35 Changed 17 months ago by nickm

  • Owner changed from nickm to yawning
  • Severity set to Normal
  • Status changed from needs_revision to assigned

Setting Yawning as the owner of this needs_revision ticket.

comment:36 Changed 17 months ago by nickm

  • Status changed from assigned to needs_revision

comment:37 Changed 16 months ago by fergus

A question for whoever cares to answer it:

I noticed the consensus diffs proposal had been sitting around unimplemented since 2008 and, after some cursory searches didn't turn up anything related, I decided to take a crack at it. I didn't find this ticket until I had mostly finished my implementation. Is the seven months since this was last meaningfully touched a long enough delay that I should submit my code for review, or would I be stepping on someones toes?

Last edited 16 months ago by fergus (previous) (diff)

comment:38 Changed 16 months ago by nickm

  • Milestone changed from Tor: 0.2.8.x-final to Tor: 0.2.9.x-final

These seem like features, or like other stuff unlikely to be possible this month. Bumping them to 0.2.9

comment:39 Changed 15 months ago by isabela

  • Sponsor set to SponsorU-can

comment:40 Changed 15 months ago by nickm

  • Keywords TorCoreTeam201509 removed

Removing TorCoreTeam201509 from these tickets, since we do not own a time machine.

comment:41 Changed 15 months ago by nickm

  • Keywords tor-dos added

comment:42 Changed 13 months ago by isabela

  • Points changed from medium to 3

comment:43 Changed 13 months ago by arma

  • Keywords low-bandwidth added

comment:44 Changed 13 months ago by yawning

  • Status changed from needs_revision to assigned

Taking this for 0.2.9

comment:45 Changed 10 months ago by nickm

  • Keywords nickm-deferred-20160905 added
  • Milestone changed from Tor: 0.2.9.x-final to Tor: 0.2.???

Hi, Yawning! I'm deferring these tickets assigned to you from 0.2.9 to 0.2.???, since you're going to be out for September. But if you wind up wanting to do any of them for 0.2.9 anyway, please feel free to move them back.

(This is my ticket-deferring afternoon)

comment:46 Changed 8 months ago by teor

  • Milestone changed from Tor: 0.2.??? to Tor: 0.3.???

Milestone renamed

comment:47 Changed 6 months ago by nickm

  • Keywords tor-03-unspecified-201612 added
  • Milestone changed from Tor: 0.3.??? to Tor: unspecified

Finally admitting that 0.3.??? was a euphemism for Tor: unspecified all along.

comment:48 Changed 6 months ago by nickm

  • Keywords sponsor4 added

Bulk-adding "sponsor4" keyword to items that would appear to reduce low-bw clients' directory bandwidth usage. But we shouldn't build these without measurement/proposals: see #21205 and #21209.

comment:49 Changed 4 months ago by nickm

  • Keywords TorCoreTeam201703 added
  • Milestone changed from Tor: unspecified to Tor: 0.3.1.x-final
  • Owner yawning deleted
  • Sponsor changed from SponsorU-can to Sponsor4

comment:50 Changed 4 months ago by nickm

  • Points changed from 3 to parent
  • Summary changed from Merge GSoC project - Consensus Diffs to Prop140: Complete Consensus diffs / Merge GSoC project

comment:51 Changed 4 months ago by mvdan

Hey nick,

It's been almost two years and I don't have a lot of free time these days, but I'm still here if you need any questions answered or you want me to do a rebase.

Thanks for trying to get this merged - better late than never :)

comment:52 Changed 4 months ago by nickm

Thanks, Daniel! I'll let you know as any questions come up. Right now I think it's mainly going to be a bunch of additional testing and refactoring.

I just did a rebase, plus some code updates as a branch consdiff_rebased in my public repository. My next plan is to split it into the consdiff parts and the other parts, and start working through them independently.

Thanks again for all your work here: I hope we can finally get it to go live in a couple of months. You might be interested to know that it will be of even greater benefit now than it would have been two years ago: see the updates to proposal 140, and proposals 274-278.

comment:53 Changed 4 months ago by nickm

  • Owner set to nickm

comment:54 Changed 4 months ago by dgoulet

  • Keywords changed from gsoc, merge, tor-client, prop140, 027-triaged-1-in, 028-triaged, pre028-patch, tor-dos, low-bandwidth, nickm-deferred-20160905, tor-03-unspecified-201612, sponsor4 TorCoreTeam201703 to gsoc, merge, tor-client, prop140, 027-triaged-1-in, 028-triaged, pre028-patch, tor-dos, low-bandwidth, nickm-deferred-20160905, tor-03-unspecified-201612, sponsor4, TorCoreTeam201703

comment:55 Changed 3 months ago by Sebastian

Hi Daniel, great that you're still around :) I have a question about the unit tests. In the function test_consdiff_calc_changes() in the second test, you're calculating the changes between "a\na\na\na\n" and "a\nb\na\nb\n" - and then we expect the first bit vector to be marked unchanged, changed, changed, unchanged. What am I missing here? According to the documentation of calc_changes() I would think that the proper result would be unchanged, changed, unchanged, changed.

comment:56 Changed 3 months ago by mvdan

Hi Sebastian,

I had to re-read my own docs because I completely forgot what calc_changes() even was :)

According to the documentation of calc_changes() I would think that the proper result would be unchanged, changed, unchanged, changed.

Admitting that I don't fully remember how this thing worked, I think you're assuming too much.

For example, having [a a a a] and [a b a b], and the bits [0 1 1 0] and [0 1 0 1], what we will do is:

  • change the second and third elements [a a] with [b]: [a b a]
  • add a fourth element [b]: [a b a b]

The ed diff, if I recall correctly, should be something like (doing this in my head, so could be wrong):

1,2cb
.
3ab
.

I understand you were expecting the bits to be [0 1 0 1] and [0 1 0 1]. Then, the diff would be something like:

2cb
.
4cb
.

Note that the two are valid. Yours is a bit smaller as far as bytes used, but it's still the same number of operations.

If I remember correctly, calc_changes optimizes for number of lines added/deleted in the diff, not for the size of the ed diff. This is because it doesn't do an ed diff at all - the ed diff is done at a higher level, in a func that calls calc_changes. It ended up with this result just like it could have ended with yours - both mean four lines changed (deleted+added) in total. In other words, the number of bits set to "1" across both bit vectors is 4.

Perhaps a way to get slightly smaller ed diffs would be to get calc_changes to prefer the operator 'c' over 'a' and 'd'. But remember that this operation should only be used in very small pieces of the consensus, so I don't expect you'd be saving much at the cost of complexity.

So TL;DR: the expected values are correct. Not the smallest ed diff nor the one that a human would do, but one that is almost as small.

Last edited 3 months ago by mvdan (previous) (diff)

comment:57 Changed 3 months ago by mvdan

Another thought - could be that calc_changes is buggy somewhere, causing it to end up with diffs that are correct but not the optimal it would find if it were doing divide-and-conquer properly. Perhaps optimal_column_to_split is wrong, or perhaps we should use its return value plus one or minus one instead of as-is.

In my head, divide and conquer should be able to come up with your version just fine. Then again, the version it finds is just as optimal given its "number of lines added+deleted" heuristic.

comment:58 Changed 3 months ago by Sebastian

Ok. I was just confused by the docs of the calc_changes function I think. I did a reimplementation that I want to be compatible, so I'll be sure to match the C version you provided :) Thank you.

comment:59 Changed 3 months ago by mvdan

Yeah, I agree that the docs aren't very clear. Out of curiosity, what is the reimplementation for? Performance, safety?

comment:60 Changed 3 months ago by Sebastian

We're doing a Rust experiment and the consdiff code is fairly self-contained and seemed to be a decent chunk of code to actually show that Rust can work for us.

comment:61 Changed 3 months ago by mvdan

Oh, that's very interesting. I read that blog post. Though I have to say I'm a Go person these days ;)

Kidding aside, this sounds like a good idea. I'm sure the code will be much more readable with all the slicing and vectors.

comment:62 Changed 7 weeks ago by nickm

  • Status changed from assigned to needs_review

We can close this when its children are closed. :)

comment:63 Changed 6 weeks ago by nickm

  • Resolution set to implemented
  • Status changed from needs_review to closed

It's all merged and seems to be working! :)

comment:64 Changed 6 weeks ago by mvdan

Great to hear! Thanks for finally getting it merged :)

Note: See TracTickets for help on using tickets.