proto: Remove write_source (pull in `IndexMap` to avoid borrowing issues)

[gretchenfrage]

This PR is competing with and mutually exclusive with my previous #2242 and #2230. I think this is the best iteration so far.

Successfully removes WriteSource without utilizing a callback (per #2230) nor introducing lifetime stuff (per #2242), and successfully splits up the write_source method's logic more deeply than those two.

Introduces dependency on indexmap crate. This seems fine to me. It's an extremely common crate and likely to be useful for other things too.

Notes on possible follow-up work

As I've expressed on the other PRs, I like the idea of introducing some sort of public API capable of doing what WriteSource can do. This PR is actually more helpful to that goal than #2242. In #2242, introducing some sort of quinn version of WriteGuard<'_> would mean we'd want to create a struct which contains both a mutex guard and a proto::WriteGuard<'_> which borrows from that mutex guard. This probably would require us to either pull in the ouroboros crate or write equivalent unsafe code manually, or to complicate the API in some ugly way. Conversely, with the approach implemented in this PR, we could conceivably just make write_limit and write_unchecked public and give quinn a WriteGuard struct which contains a mutex guard and a usize write budget. Or something like that.

Also, a different bit of follow-up work that could be done after that would be to modify RecvStream to do a similar sort of preemptive hashmap lookup, if we wanted.

[gretchenfrage]

Previous attempts to simplify this and remove the WriteSource trait were complicated by the fact that it is desirable to cache a single StreamId hashmap lookup over the course of this whole process.

Was that really the issue? This feels like it might be a premature optimization. FxHashMap on StreamId should be comically fast already. IndexMap's implementation looks great, but it is more deps for unclear benefit, and something we could pursue in future without breakage if a need is shown. Unless you've done benchmarking already?

I made a comment to this effect in the message of #2242:

I did some looking and it looks like the write_source API was introduced in #1013. The main aim of that PR seemed to be simply to introduce the ability to directly use Bytes in general. This made me wonder why this wasn't done by adding a method that just wrote one Bytes at a time. From looking at the code, it looks like the main penalty to do this would be duplicated hash table look-ups for the stream. Caching the &mut, as this PR does, avoids that.

[Ralith]

The reason behind our batched high level APIs isn't to avoid multiple hash-table lookups -- it's to avoid churning the connection Mutex, which might be contended, at the quinn layer. Maybe we pushed that concern down further than necessary before, but we shouldn't hold ourselves to that now.

[gretchenfrage]

Based on your comments about 1. hash map lookups being maybe cheap enough to do a lot of times 2. write_limit checks being maybe cheap enough to do a lot of times, I prototyped this commit here: https://github.com/quinn-rs/quinn/commit/866e9c2cd0afe6705e0bfd090a7f2d3e7bf9e221 which does some deeper refactors that take advantage of considering those things really cheap to do.

Basically it leaves us with the following primitive methods:

    /// Get how many bytes could be written immediately
    ///
    /// Always returns `Ok(0)` if blocked, never returns `WriteError::Blocked`.
    pub fn write_limit(&self) -> Result<usize, WriteError> { .. }

    /// Ensure that a [`StreamEvent::Writable`][1] event is emitted once [`write_limit`][2]
    /// transitions from `Ok(0)` to a non-zero value
    ///
    /// Panics if `self.write_limit() != Ok(0)`.
    ///
    /// [1]: crate::StreamEvent::Writable
    /// [2]: Self::write_limit
    pub fn mark_blocked(&mut self) { .. }

    /// Immediately write the entirety of `chunk` on the given stream, or panic if unable
    ///
    /// Requires that `self.write_limit().unwrap() >= chunk.len()`, panics otherwise.
    pub fn write_immediate(&mut self, chunk: Bytes) { .. }

And also 3 non-primitive methods (doesn't implement anything a user couldn't implement):

• write
• write_chunks
• write_limit_or_mark_blocked

I think that design has some nice qualities of it being easy to reason about error handling. And it doesn't pull in indexmap. @Ralith I'm wondering what you think?

[Ralith]

Looks generally attractive. I wonder if we could move the errors from write_limit to mark_blocked, and rename the latter to something like fn begin_write(&mut self) -> Result<(), WriteError> to simplify things for callers a little?

[gretchenfrage]

I wonder if we could move the errors from write_limit to mark_blocked

I don't think that would be the right choice. Basically, it's a natural answer to the question asked. "How many bytes could I write on this stream right now?" "You can never write bytes on this stream again, it's errored."

Renaming the other thing sounds good.

[Ralith]

My thinking is that caller logic is simplified if the branch on "is the limit 0" gets pushed down into shared logic, so you can write stream.begin_write()? instead of if limit == 0 { stream.mark_blocked(); return Err(WriteError::Blocked.into()); }. Once begin_write is returning one type of error, it seems like it might be simpler to centralize the rest there.

Both are, unfortunately, easy to forget...

[gretchenfrage]

On the other hand, if someone is making logic which calls write_limit without immediately following it with a call to begin_write, if it's 0, and we return a limit of 0 in cases where it's errored, I worry that they would never observe and handle the fact that the stream is errored

(Imagine, I don't know, a program which streams in frames from a video camera, and whenever one arrives, sends it down the quic stream iff the stream can currently fit the whole video frame)

[Ralith]

Makes sense. I don't feel that strongly, either way is a big improvement.