From 4a59b73d7bfd0f136f654e874afb5d2a9bf4df2e Mon Sep 17 00:00:00 2001 From: Alex Auvolat Date: Thu, 1 Sep 2022 12:46:33 +0200 Subject: Add actual support for order tag --- src/send.rs | 112 ++++++++++++++++++++++++++++++++++++++++++------------------ 1 file changed, 78 insertions(+), 34 deletions(-) (limited to 'src/send.rs') diff --git a/src/send.rs b/src/send.rs index c40787f..ea6cf9f 100644 --- a/src/send.rs +++ b/src/send.rs @@ -1,4 +1,4 @@ -use std::collections::VecDeque; +use std::collections::{HashMap, VecDeque}; use std::pin::Pin; use std::sync::Arc; use std::task::{Context, Poll}; @@ -7,7 +7,7 @@ use async_trait::async_trait; use bytes::{BufMut, Bytes, BytesMut}; use log::*; -use futures::AsyncWriteExt; +use futures::{AsyncWriteExt, Future}; use kuska_handshake::async_std::BoxStreamWrite; use tokio::sync::mpsc; @@ -36,15 +36,21 @@ pub(crate) const ERROR_MARKER: ChunkLength = 0x4000; pub(crate) const CHUNK_HAS_CONTINUATION: ChunkLength = 0x8000; pub(crate) const CHUNK_LENGTH_MASK: ChunkLength = 0x3FFF; -pub(crate) type SendStream = (RequestID, RequestPriority, ByteStream); +pub(crate) type SendStream = (RequestID, RequestPriority, Option, ByteStream); struct SendQueue { - items: Vec<(u8, VecDeque)>, + items: Vec<(u8, SendQueuePriority)>, +} + +struct SendQueuePriority { + items: VecDeque, + order: HashMap>, } struct SendQueueItem { id: RequestID, prio: RequestPriority, + order_tag: Option, data: ByteStreamReader, } @@ -59,11 +65,11 @@ impl SendQueue { let pos_prio = match self.items.binary_search_by(|(p, _)| p.cmp(&prio)) { Ok(i) => i, Err(i) => { - self.items.insert(i, (prio, VecDeque::new())); + self.items.insert(i, (prio, SendQueuePriority::new())); i } }; - self.items[pos_prio].1.push_back(item); + self.items[pos_prio].1.push(item); } fn is_empty(&self) -> bool { self.items.iter().all(|(_k, v)| v.is_empty()) @@ -75,29 +81,34 @@ impl SendQueue { } } -struct SendQueuePollNextReady<'a> { - queue: &'a mut SendQueue, -} - -impl<'a> futures::Future for SendQueuePollNextReady<'a> { - type Output = (RequestID, DataFrame); - - fn poll(mut self: Pin<&mut Self>, ctx: &mut Context<'_>) -> Poll { - for (i, (_prio, items_at_prio)) in self.queue.items.iter_mut().enumerate() { - let mut ready_item = None; - for (j, item) in items_at_prio.iter_mut().enumerate() { - let mut item_reader = item.data.read_exact_or_eos(MAX_CHUNK_LENGTH as usize); - match Pin::new(&mut item_reader).poll(ctx) { - Poll::Pending => (), - Poll::Ready(ready_v) => { - ready_item = Some((j, ready_v)); - break; - } +impl SendQueuePriority { + fn new() -> Self { + Self { + items: VecDeque::new(), + order: HashMap::new(), + } + } + fn push(&mut self, item: SendQueueItem) { + if let Some(OrderTag(stream, order)) = item.order_tag { + let order_vec = self.order.entry(stream).or_default(); + let i = order_vec.iter().take_while(|o2| **o2 < order).count(); + order_vec.insert(i, order); + } + self.items.push_back(item); + } + fn is_empty(&self) -> bool { + self.items.is_empty() + } + fn poll_next_ready(&mut self, ctx: &mut Context<'_>) -> Poll<(RequestID, DataFrame)> { + for (j, item) in self.items.iter_mut().enumerate() { + if let Some(OrderTag(stream, order)) = item.order_tag { + if order > *self.order.get(&stream).unwrap().front().unwrap() { + continue; } } - if let Some((j, bytes_or_err)) = ready_item { - let item = items_at_prio.remove(j).unwrap(); + let mut item_reader = item.data.read_exact_or_eos(MAX_CHUNK_LENGTH as usize); + if let Poll::Ready(bytes_or_err) = Pin::new(&mut item_reader).poll(ctx) { let id = item.id; let eos = item.data.eos(); @@ -106,15 +117,47 @@ impl<'a> futures::Future for SendQueuePollNextReady<'a> { _ => unreachable!(), }); + if eos || packet.is_err() { + if let Some(OrderTag(stream, order)) = item.order_tag { + assert_eq!( + self.order.get_mut(&stream).unwrap().pop_front(), + Some(order) + ) + } + self.items.remove(j); + } + let data_frame = DataFrame::from_packet(packet, !eos); - if !eos && !matches!(data_frame, DataFrame::Error(_)) { - items_at_prio.push_back(item); - } else if items_at_prio.is_empty() { + return Poll::Ready((id, data_frame)); + } + } + + Poll::Pending + } + fn dump(&self, prio: u8) -> String { + self.items + .iter() + .map(|i| format!("[{} {} {:?}]", prio, i.id, i.order_tag)) + .collect::>() + .join(" ") + } +} + +struct SendQueuePollNextReady<'a> { + queue: &'a mut SendQueue, +} + +impl<'a> futures::Future for SendQueuePollNextReady<'a> { + type Output = (RequestID, DataFrame); + + fn poll(mut self: Pin<&mut Self>, ctx: &mut Context<'_>) -> Poll { + for (i, (_prio, items_at_prio)) in self.queue.items.iter_mut().enumerate() { + if let Poll::Ready(res) = items_at_prio.poll_next_ready(ctx) { + if items_at_prio.is_empty() { self.queue.items.remove(i); } - - return Poll::Ready((id, data_frame)); + return Poll::Ready(res); } } // If the queue is empty, this futures is eternally pending. @@ -200,8 +243,7 @@ pub(crate) trait SendLoop: Sync { sending .items .iter() - .map(|(_, i)| i.iter().map(|x| x.id)) - .flatten() + .map(|(prio, i)| i.dump(*prio)) .collect::>() ); @@ -217,12 +259,14 @@ pub(crate) trait SendLoop: Sync { // recv_fut is cancellation-safe according to tokio doc, // send_fut is cancellation-safe as implemented above? tokio::select! { + biased; // always read incomming channel first if it has data sth = recv_fut => { - if let Some((id, prio, data)) = sth { + if let Some((id, prio, order_tag, data)) = sth { trace!("send_loop: add stream {} to send", id); sending.push(SendQueueItem { id, prio, + order_tag, data: ByteStreamReader::new(data), }); } else { -- cgit v1.2.3