Opened 2 months ago

Closed 2 weeks ago

#24700 closed defect (fixed)

sched: With KIST, a channel can be added more than once in the pending list

Reported by: dgoulet Owned by: dgoulet
Priority: High Milestone: Tor: 0.3.3.x-final
Component: Core Tor/Tor Version: Tor:
Severity: Normal Keywords: tor-sched, kist, 032-backport
Cc: pastly Actual Points:
Parent ID: #23993 Points:
Reviewer: nickm Sponsor:


Here is the flow for this to happen (and it has been observed):

The scheduler flushes 100 bytes onto the outbuf of a channel. Then the channel it put in the re-add list (which is to add back the channel in the pending list at the _end_ of the scheduler loop) because it can't write anymore. Its state is set to waiting_to_write.

We then handle the next channel in the main loop but before that we'll try to write to kernel the outbuf of the previous channel which is in the re-add list.

If the outbuf is fully drained, scheduler_channel_wants_writes() is called which will add the channel back in the pending list *IF* it is in the waiting_to_write state which it is because it was set to that state just before being added to the re-add list.

Scheduler loop ends and we end up with twice the channel in the pending list. This can go on for a while resulting in the same channel being added many more times.

There are two ways to fix that, one quick and one more logical.

  1. The quick one is to let the state of the channel in PENDING mode (which is what Vanilla does) before adding it to the re-add list. That way, it won't get added back in the pending list by any callbacks.
  1. Originally, the assumption was that KIST takes care of the write on the socket and only KIST. But the reality is different, KIST will trigger writes to the kernel but anything after that, any errors or retry is handled by libevent write_event (#24448, and #24449).

So, it doesn't make sense for KIST to reschedule the channel as pending if it is waiting to write on the socket because from that point on, it will be the job of libevent to actually flush it with its poll(POLLOUT) feature. Thus the fix is to never add back a channel that is waiting to write.

I personally would like to have (2) for two reasons. First, we would save CPU time and useless syscalls in this fast path. Second, adding a channel that is waiting to write back into the pending list is not really good in terms of priority. It should not get considered for another round in the loop, it should simply wait until the socket has been written since the assumption in (2) is false in the first place.

Child Tickets

Change History (12)

comment:1 Changed 3 weeks ago by dgoulet

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

Moving this to 033 so we notice it!

comment:2 Changed 3 weeks ago by dgoulet

Parent ID: #23993
Reviewer: #23993

comment:3 Changed 3 weeks ago by dgoulet

See branch bug24700_032_01.

For the 032 fix, I went for the quick one detailed in (1).

Please, DO NOT merge forward this fix. For 033, this is resolved with #24554 which includes more fixes.

Version 0, edited 3 weeks ago by dgoulet (next)

comment:4 Changed 3 weeks ago by dgoulet

Keywords: 032-backport added

comment:5 Changed 3 weeks ago by dgoulet

Status: assignedneeds_review

comment:6 Changed 3 weeks ago by nickm

Priority: MediumHigh
Reviewer: nickm

comment:7 Changed 3 weeks ago by nickm


1) Can you tell me something about how this was tested? How do we know it will work?

2) When we merge to 0.3.3, should we remove the scheduler_set_channel_state() call instead?

2) Do you think we should redundantly keep track of the "is_inserted" property in the sched_heap_idx field? (See my branch 24700_heap_idx_033 for an idea of what I mean.)

comment:8 Changed 3 weeks ago by nickm

fwiw, my patch is wrong: it should say != not ==.

comment:9 Changed 3 weeks ago by nickm

I've made an updated version of your branch as bug24700_032_01 in my public repository.

comment:10 Changed 3 weeks ago by dgoulet

Status: needs_reviewneeds_revision

I'm taking this one. I'll pull nickm's changes and unit tests that we don't add twice the same channel in the pqueue.

comment:11 Changed 2 weeks ago by dgoulet

Status: needs_revisionneeds_review

Ok, the 032 branch has the fixes with extra checks from Nickm and also added checks on my part.

The 033 branch is the 032 branch merged into master + one commit for unit tests.

Branches: bug24700_032_01 and bug24700_033_01

comment:12 Changed 2 weeks ago by nickm

Resolution: fixed
Status: needs_reviewclosed

I've merged those to maint-0.3.2 and master. Let's test it hard!

Note: See TracTickets for help on using tickets.