Integrate KIST socket/circuit scheduling

This ticket is a parent for tracking work needed to implement/test/simulate/integrate the new global scheduling and write-limiting techniques for handling kernel output. This is funded by Sponsor F.

The initial design is from Rob's USENIX Security 2014 paper entitled "Kernel-Informed Socket Transport", which will be available here: http://www.robgjansen.com/publications/kist-sec2014.pdf and the appendices here: http://www.cs.umn.edu/tech_reports_upload/tr2014/14-012.pdf

changed milestone to %Tor: 0.3.2.x-final

added component::core tor/tor kist milestone::Tor: 0.3.2.x-final owner::dgoulet performance priority::medium resolution::implemented review-group-22 review-group-23 scheduling severity::normal status::closed tcp term-project-ideas tor-relay type::enhancement labels

Trac:
Username: nikita
Cc: N/A to nikita

Trac:
Cc: nikita to nikita, yawning

Trac:
Keywords: scheduling deleted, scheduling tor-relay 026-triaged-1 added

Timeframewise, I think this won't be ready by the January cutoff for 0.2.6. But if I'm wrong, we can merge it.

Trac:
Milestone: Tor: 0.2.6.x-final to Tor: 0.2.7.x-final

Making serious progress on this will become my top priority after the Oakland deadline tomorrow. You can expect frequent updates from me starting then.

Trac:
cmux-highwater.shadowtor.pdf.xz-part0

Trac:
cmux-highwater.shadowtor.pdf.xz-part1

Trac:
cmux-lowwater.shadowtor.pdf.xz-part0

Trac:
cmux-lowwater.shadowtor.pdf.xz-part1

Trac:
cmux-maxflush.shadowtor.pdf.xz-part0

Trac:
cmux-maxflush.shadowtor.pdf.xz-part1

Whoops, those files were supposed to be attached to #12889 (closed). Push the wrong button in trac and everything is set in stone...

Trac:
Status: new to assigned

Marking triaged-out items from first round of 0.2.7 triage.

Trac:
Keywords: scheduling tor-relay 026-triaged-1 deleted, 026-triaged-1, tor-relay, 027-triaged-1-out, scheduling added

Make all non-needs_review, non-needs_revision, 027-triaged-1-out items belong to 0.2.???

Trac:
Milestone: Tor: 0.2.7.x-final to Tor: 0.2.???

Trac:
Keywords: N/A deleted, 6s194 added

These tickets were tagged "6s194" as ideas for possible term projects for students in MIT subject 6.S194 spring 2016. I'm retagging with term-project-ideas, so that the students can use the 6s194 tag for tickets they're actually working on.

Trac:
Keywords: 6s194 deleted, term-project-ideas added

Milestone renamed

Trac:
Milestone: Tor: 0.2.??? to Tor: 0.3.???

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

Trac:
Keywords: N/A deleted, tor-03-unspecified-201612 added
Milestone: Tor: 0.3.??? to Tor: unspecified

Remove an old triaging keyword.

Trac:
Keywords: tor-03-unspecified-201612 deleted, N/A added

Trac:
Keywords: N/A deleted, 027-triaged-in added

Trac:
Keywords: 027-triaged-in deleted, N/A added

Trac:
Keywords: 027-triaged-1-out deleted, N/A added

Trac:
Keywords: 026-triaged-1 deleted, N/A added

Change the status of all assigned/accepted Tor tickets with owner="" to "new".

Trac:
Status: assigned to new

Trac:
Severity: N/A to Normal
Reviewer: N/A to N/A
Keywords: N/A deleted, kist added
Sponsor: N/A to N/A

Trac:
Milestone: Tor: unspecified to Tor: 0.3.2.x-final
Owner: N/A to pastly
Status: new to assigned

See

• https://gitweb.torproject.org/user/pastly/tor.git/?h=kist-fortor-02 or
• https://oniongit.eu/pastly/tor/tree/kist-fortor-02

Adding dgoulet who wants to review KIST.

The difference between -01 and -02 is just rebasing from master ~4w ago to master today.

Trac:
Cc: nikita, yawning to nikita, yawning, dgoulet
Status: assigned to needs_review

Trac:
Reviewer: N/A to dgoulet
Cc: nikita, yawning, dgoulet to nikita, yawning

Oniongit: https://oniongit.eu/network/tor/merge_requests/4 https://oniongit.eu/pastly/tor/merge_requests/1

Hi, pastly & dgoulet! I just skimmed over the merge request on oniongit and added a few comments and questions. It's not a thorough review; just a cursory inspection. I'm sure dgoulet will have more questions and comments when he's back from vacation.

Trac:
Keywords: N/A deleted, review-group-22 added

Just went over the whole thing. Many things to discuss! but overall, I'm very happy and optimistic about this change. It makes things so much easier to understand, nice interface and design imo.

We can either discuss on IRC if you want to go faster than the back and forth on Gitlab. I'm good either way but ping me (us) when you have replied. Thanks!

Trac:
Status: needs_review to needs_revision

Progress addressing all the review in ticket12541_032_01.

It's missing few things so not ready for review.

Trac:
Status: needs_revision to accepted
Owner: pastly to dgoulet

Ok, I've gone through all the things, did some fixup on pastly branch, he reviewed it and everything got addressed (I hope!).

Time for more reviews.

Branch: ticket12541_032_01 https://oniongit.eu/dgoulet/tor/merge_requests/7

Trac:
Status: accepted to needs_review
Reviewer: dgoulet to N/A

Put 0.3.2 needs_review and merge_ready tickets into review-group-23.

Trac:
Keywords: N/A deleted, review-group-23 added

sooo... did you change anything in the vanilla scheduler? It's impossible to tell with the diffs. Wasn't there a bug in there you fixed? (https://oniongit.eu/pastly/tor/merge_requests/1#note_863)

I removed the SchedulerLowWaterMark__, SchedulerHighWaterMark__, and SchedulerMaxFlushCells__ options. They were ineffective and never meaningful.

Low: Tor had to have less than this in its outbufs or else it wouldn't start a scheduling round. High: Tor would stop a scheduling round if it hit this. MaxFlush: Tor would flush this many cells at maximum from a circuit queue to its outbuf at a time before moving on to another channel.

They were all set so high that they didn't matter.

I'm pretty sure the bug you are thinking of is #20459 (moved) fixed in c09993fdf6.

---

"What if ms >= 1000?" (https://oniongit.eu/pastly/tor/merge_requests/1#note_869)

I'm assuming you mean "what if diff >= 1000"

sched_run_interval (or _freq as it was called then) has a maximum of 100 ms. If diff is larger than sched_run_interval, the code block with event_active is called instead so it doesn't matter.

---

I've put off mucking around with int types still.

Trac:
Cc: nikita, yawning to nikita

I switched to monotonic time and tweaked/added some comments and log messages on top of dgoulet's branch. Ready for review so it can slip into 032 <3

https://oniongit.eu/pastly/tor/merge_requests/2

KIST deployment paper: https://arxiv.org/abs/1709.01044

reviewed; left comments on branch.

Trac:
Status: needs_review to needs_revision

Trac:
Status: needs_revision to needs_review

reviewed; left more comments on branch. also please see threads that didn't get checked off; I thought those had open questions when I looked. Also this needs a changes file.

Trac:
Status: needs_review to needs_revision

Answered. Fixup are in my kist-fortor-03 and pastly just pushed it to oniongit.

Trac:
Status: needs_revision to needs_review

Merging!

Please close this ticket once the new tickets from the review are open, and once appropriate child tickets are closed or unparented.

Trac:
Status: needs_review to merge_ready

Sweet glorious day

Trac:
Status: merge_ready to closed
Resolution: N/A to implemented

Replying to pastly:

Sweet glorious day Congrats pastly and rob, good stuff! :)

closed