Adding upstream version 0.12.1+dfsg.upstream/0.12.1+dfsgupstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 421 insertions, 0 deletions

diff --git a/lib/ngtcp2_cc.h b/lib/ngtcp2_cc.h
new file mode 100644
index 0000000..6d9e0c2
--- /dev/null
+++ b/lib/ngtcp2_cc.h
@@ -0,0 +1,421 @@
+/*
+ * ngtcp2
+ *
+ * Copyright (c) 2018 ngtcp2 contributors
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to
+ * permit persons to whom the Software is furnished to do so, subject to
+ * the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+ * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+ * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+ * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ */
+#ifndef NGTCP2_CC_H
+#define NGTCP2_CC_H
+
+#ifdef HAVE_CONFIG_H
+#  include <config.h>
+#endif /* HAVE_CONFIG_H */
+
+#include <ngtcp2/ngtcp2.h>
+
+#define NGTCP2_LOSS_REDUCTION_FACTOR_BITS 1
+#define NGTCP2_PERSISTENT_CONGESTION_THRESHOLD 3
+
+typedef struct ngtcp2_log ngtcp2_log;
+
+/**
+ * @struct
+ *
+ * :type:`ngtcp2_cc_base` is the base structure of custom congestion
+ * control algorithm.  It must be the first field of custom congestion
+ * controller.
+ */
+typedef struct ngtcp2_cc_base {
+  /**
+   * :member:`log` is ngtcp2 library internal logger.
+   */
+  ngtcp2_log *log;
+} ngtcp2_cc_base;
+
+/**
+ * @struct
+ *
+ * :type:`ngtcp2_cc_pkt` is a convenient structure to include
+ * acked/lost/sent packet.
+ */
+typedef struct ngtcp2_cc_pkt {
+  /**
+   * :member:`pkt_num` is the packet number
+   */
+  int64_t pkt_num;
+  /**
+   * :member:`pktlen` is the length of packet.
+   */
+  size_t pktlen;
+  /**
+   * :member:`pktns_id` is the ID of packet number space which this
+   * packet belongs to.
+   */
+  ngtcp2_pktns_id pktns_id;
+  /**
+   * :member:`sent_ts` is the timestamp when packet is sent.
+   */
+  ngtcp2_tstamp sent_ts;
+  /**
+   * :member:`lost` is the number of bytes lost when this packet was
+   * sent.
+   */
+  uint64_t lost;
+  /**
+   * :member:`tx_in_flight` is the bytes in flight when this packet
+   * was sent.
+   */
+  uint64_t tx_in_flight;
+  /**
+   * :member:`is_app_limited` is nonzero if the connection is
+   * app-limited when this packet was sent.
+   */
+  int is_app_limited;
+} ngtcp2_cc_pkt;
+
+/**
+ * @struct
+ *
+ * :type:`ngtcp2_cc_ack` is a convenient structure which stores
+ * acknowledged and lost bytes.
+ */
+typedef struct ngtcp2_cc_ack {
+  /**
+   * :member:`prior_bytes_in_flight` is the in-flight bytes before
+   * processing this ACK.
+   */
+  uint64_t prior_bytes_in_flight;
+  /**
+   * :member:`bytes_delivered` is the number of bytes acknowledged.
+   */
+  uint64_t bytes_delivered;
+  /**
+   * :member:`bytes_lost` is the number of bytes declared lost.
+   */
+  uint64_t bytes_lost;
+  /**
+   * :member:`pkt_delivered` is the cumulative acknowledged bytes when
+   * the last packet acknowledged by this ACK was sent.
+   */
+  uint64_t pkt_delivered;
+  /**
+   * :member:`largest_acked_sent_ts` is the time when the largest
+   * acknowledged packet was sent.
+   */
+  ngtcp2_tstamp largest_acked_sent_ts;
+  /**
+   * :member:`rtt` is the RTT sample.  It is UINT64_MAX if no RTT
+   * sample is available.
+   */
+  ngtcp2_duration rtt;
+} ngtcp2_cc_ack;
+
+typedef struct ngtcp2_cc ngtcp2_cc;
+
+/**
+ * @functypedef
+ *
+ * :type:`ngtcp2_cc_on_pkt_acked` is a callback function which is
+ * called with an acknowledged packet.
+ */
+typedef void (*ngtcp2_cc_on_pkt_acked)(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat,
+                                       const ngtcp2_cc_pkt *pkt,
+                                       ngtcp2_tstamp ts);
+
+/**
+ * @functypedef
+ *
+ * :type:`ngtcp2_cc_on_pkt_lost` is a callback function which is
+ * called with a lost packet.
+ */
+typedef void (*ngtcp2_cc_on_pkt_lost)(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat,
+                                      const ngtcp2_cc_pkt *pkt,
+                                      ngtcp2_tstamp ts);
+/**
+ * @functypedef
+ *
+ * :type:`ngtcp2_cc_congestion_event` is a callback function which is
+ * called when congestion event happens (e.g., when packet is lost).
+ */
+typedef void (*ngtcp2_cc_congestion_event)(ngtcp2_cc *cc,
+                                           ngtcp2_conn_stat *cstat,
+                                           ngtcp2_tstamp sent_ts,
+                                           ngtcp2_tstamp ts);
+
+/**
+ * @functypedef
+ *
+ * :type:`ngtcp2_cc_on_spurious_congestion` is a callback function
+ * which is called when a spurious congestion is detected.
+ */
+typedef void (*ngtcp2_cc_on_spurious_congestion)(ngtcp2_cc *cc,
+                                                 ngtcp2_conn_stat *cstat,
+                                                 ngtcp2_tstamp ts);
+
+/**
+ * @functypedef
+ *
+ * :type:`ngtcp2_cc_on_persistent_congestion` is a callback function
+ * which is called when persistent congestion is established.
+ */
+typedef void (*ngtcp2_cc_on_persistent_congestion)(ngtcp2_cc *cc,
+                                                   ngtcp2_conn_stat *cstat,
+                                                   ngtcp2_tstamp ts);
+
+/**
+ * @functypedef
+ *
+ * :type:`ngtcp2_cc_on_ack_recv` is a callback function which is
+ * called when an acknowledgement is received.
+ */
+typedef void (*ngtcp2_cc_on_ack_recv)(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat,
+                                      const ngtcp2_cc_ack *ack,
+                                      ngtcp2_tstamp ts);
+
+/**
+ * @functypedef
+ *
+ * :type:`ngtcp2_cc_on_pkt_sent` is a callback function which is
+ * called when an ack-eliciting packet is sent.
+ */
+typedef void (*ngtcp2_cc_on_pkt_sent)(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat,
+                                      const ngtcp2_cc_pkt *pkt);
+
+/**
+ * @functypedef
+ *
+ * :type:`ngtcp2_cc_new_rtt_sample` is a callback function which is
+ * called when new RTT sample is obtained.
+ */
+typedef void (*ngtcp2_cc_new_rtt_sample)(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat,
+                                         ngtcp2_tstamp ts);
+
+/**
+ * @functypedef
+ *
+ * :type:`ngtcp2_cc_reset` is a callback function which is called when
+ * congestion state must be reset.
+ */
+typedef void (*ngtcp2_cc_reset)(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat,
+                                ngtcp2_tstamp ts);
+
+/**
+ * @enum
+ *
+ * :type:`ngtcp2_cc_event_type` defines congestion control events.
+ */
+typedef enum ngtcp2_cc_event_type {
+  /**
+   * :enum:`NGTCP2_CC_EVENT_TX_START` occurs when ack-eliciting packet
+   * is sent and no other ack-eliciting packet is present.
+   */
+  NGTCP2_CC_EVENT_TYPE_TX_START
+} ngtcp2_cc_event_type;
+
+/**
+ * @functypedef
+ *
+ * :type:`ngtcp2_cc_event` is a callback function which is called when
+ * a specific event happens.
+ */
+typedef void (*ngtcp2_cc_event)(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat,
+                                ngtcp2_cc_event_type event, ngtcp2_tstamp ts);
+
+/**
+ * @struct
+ *
+ * :type:`ngtcp2_cc` is congestion control algorithm interface to
+ * allow custom implementation.
+ */
+typedef struct ngtcp2_cc {
+  /**
+   * :member:`ccb` is a pointer to :type:`ngtcp2_cc_base` which
+   * usually contains a state.
+   */
+  ngtcp2_cc_base *ccb;
+  /**
+   * :member:`on_pkt_acked` is a callback function which is called
+   * when a packet is acknowledged.
+   */
+  ngtcp2_cc_on_pkt_acked on_pkt_acked;
+  /**
+   * :member:`on_pkt_lost` is a callback function which is called when
+   * a packet is lost.
+   */
+  ngtcp2_cc_on_pkt_lost on_pkt_lost;
+  /**
+   * :member:`congestion_event` is a callback function which is called
+   * when congestion event happens (.e.g, packet is lost).
+   */
+  ngtcp2_cc_congestion_event congestion_event;
+  /**
+   * :member:`on_spurious_congestion` is a callback function which is
+   * called when a spurious congestion is detected.
+   */
+  ngtcp2_cc_on_spurious_congestion on_spurious_congestion;
+  /**
+   * :member:`on_persistent_congestion` is a callback function which
+   * is called when persistent congestion is established.
+   */
+  ngtcp2_cc_on_persistent_congestion on_persistent_congestion;
+  /**
+   * :member:`on_ack_recv` is a callback function which is called when
+   * an acknowledgement is received.
+   */
+  ngtcp2_cc_on_ack_recv on_ack_recv;
+  /**
+   * :member:`on_pkt_sent` is a callback function which is called when
+   * ack-eliciting packet is sent.
+   */
+  ngtcp2_cc_on_pkt_sent on_pkt_sent;
+  /**
+   * :member:`new_rtt_sample` is a callback function which is called
+   * when new RTT sample is obtained.
+   */
+  ngtcp2_cc_new_rtt_sample new_rtt_sample;
+  /**
+   * :member:`reset` is a callback function which is called when
+   * congestion control state must be reset.
+   */
+  ngtcp2_cc_reset reset;
+  /**
+   * :member:`event` is a callback function which is called when a
+   * specific event happens.
+   */
+  ngtcp2_cc_event event;
+} ngtcp2_cc;
+
+/*
+ * ngtcp2_cc_compute_initcwnd computes initial cwnd.
+ */
+uint64_t ngtcp2_cc_compute_initcwnd(size_t max_packet_size);
+
+ngtcp2_cc_pkt *ngtcp2_cc_pkt_init(ngtcp2_cc_pkt *pkt, int64_t pkt_num,
+                                  size_t pktlen, ngtcp2_pktns_id pktns_id,
+                                  ngtcp2_tstamp sent_ts, uint64_t lost,
+                                  uint64_t tx_in_flight, int is_app_limited);
+
+/* ngtcp2_reno_cc is the RENO congestion controller. */
+typedef struct ngtcp2_reno_cc {
+  ngtcp2_cc_base ccb;
+  uint64_t max_delivery_rate_sec;
+  uint64_t target_cwnd;
+  uint64_t pending_add;
+} ngtcp2_reno_cc;
+
+int ngtcp2_cc_reno_cc_init(ngtcp2_cc *cc, ngtcp2_log *log,
+                           const ngtcp2_mem *mem);
+
+void ngtcp2_cc_reno_cc_free(ngtcp2_cc *cc, const ngtcp2_mem *mem);
+
+void ngtcp2_reno_cc_init(ngtcp2_reno_cc *cc, ngtcp2_log *log);
+
+void ngtcp2_reno_cc_free(ngtcp2_reno_cc *cc);
+
+void ngtcp2_cc_reno_cc_on_pkt_acked(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat,
+                                    const ngtcp2_cc_pkt *pkt, ngtcp2_tstamp ts);
+
+void ngtcp2_cc_reno_cc_congestion_event(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat,
+                                        ngtcp2_tstamp sent_ts,
+                                        ngtcp2_tstamp ts);
+
+void ngtcp2_cc_reno_cc_on_persistent_congestion(ngtcp2_cc *cc,
+                                                ngtcp2_conn_stat *cstat,
+                                                ngtcp2_tstamp ts);
+
+void ngtcp2_cc_reno_cc_on_ack_recv(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat,
+                                   const ngtcp2_cc_ack *ack, ngtcp2_tstamp ts);
+
+void ngtcp2_cc_reno_cc_reset(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat,
+                             ngtcp2_tstamp ts);
+
+/* ngtcp2_cubic_cc is CUBIC congestion controller. */
+typedef struct ngtcp2_cubic_cc {
+  ngtcp2_cc_base ccb;
+  uint64_t max_delivery_rate_sec;
+  uint64_t target_cwnd;
+  uint64_t w_last_max;
+  uint64_t w_tcp;
+  uint64_t origin_point;
+  ngtcp2_tstamp epoch_start;
+  uint64_t k;
+  /* prior stores the congestion state when a congestion event occurs
+     in order to restore the state when it turns out that the event is
+     spurious. */
+  struct {
+    uint64_t cwnd;
+    uint64_t ssthresh;
+    uint64_t w_last_max;
+    uint64_t w_tcp;
+    uint64_t origin_point;
+    ngtcp2_tstamp epoch_start;
+    uint64_t k;
+  } prior;
+  /* HyStart++ variables */
+  size_t rtt_sample_count;
+  uint64_t current_round_min_rtt;
+  uint64_t last_round_min_rtt;
+  int64_t window_end;
+  uint64_t pending_add;
+  uint64_t pending_w_add;
+} ngtcp2_cubic_cc;
+
+int ngtcp2_cc_cubic_cc_init(ngtcp2_cc *cc, ngtcp2_log *log,
+                            const ngtcp2_mem *mem);
+
+void ngtcp2_cc_cubic_cc_free(ngtcp2_cc *cc, const ngtcp2_mem *mem);
+
+void ngtcp2_cubic_cc_init(ngtcp2_cubic_cc *cc, ngtcp2_log *log);
+
+void ngtcp2_cubic_cc_free(ngtcp2_cubic_cc *cc);
+
+void ngtcp2_cc_cubic_cc_on_pkt_acked(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat,
+                                     const ngtcp2_cc_pkt *pkt,
+                                     ngtcp2_tstamp ts);
+
+void ngtcp2_cc_cubic_cc_congestion_event(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat,
+                                         ngtcp2_tstamp sent_ts,
+                                         ngtcp2_tstamp ts);
+
+void ngtcp2_cc_cubic_cc_on_spurious_congestion(ngtcp2_cc *ccx,
+                                               ngtcp2_conn_stat *cstat,
+                                               ngtcp2_tstamp ts);
+
+void ngtcp2_cc_cubic_cc_on_persistent_congestion(ngtcp2_cc *cc,
+                                                 ngtcp2_conn_stat *cstat,
+                                                 ngtcp2_tstamp ts);
+
+void ngtcp2_cc_cubic_cc_on_ack_recv(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat,
+                                    const ngtcp2_cc_ack *ack, ngtcp2_tstamp ts);
+
+void ngtcp2_cc_cubic_cc_on_pkt_sent(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat,
+                                    const ngtcp2_cc_pkt *pkt);
+
+void ngtcp2_cc_cubic_cc_new_rtt_sample(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat,
+                                       ngtcp2_tstamp ts);
+
+void ngtcp2_cc_cubic_cc_reset(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat,
+                              ngtcp2_tstamp ts);
+
+void ngtcp2_cc_cubic_cc_event(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat,
+                              ngtcp2_cc_event_type event, ngtcp2_tstamp ts);
+
+#endif /* NGTCP2_CC_H */