1 /* 2 * ngtcp2 3 * 4 * Copyright (c) 2017 ngtcp2 contributors 5 * 6 * Permission is hereby granted, free of charge, to any person obtaining 7 * a copy of this software and associated documentation files (the 8 * "Software"), to deal in the Software without restriction, including 9 * without limitation the rights to use, copy, modify, merge, publish, 10 * distribute, sublicense, and/or sell copies of the Software, and to 11 * permit persons to whom the Software is furnished to do so, subject to 12 * the following conditions: 13 * 14 * The above copyright notice and this permission notice shall be 15 * included in all copies or substantial portions of the Software. 16 * 17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 21 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 22 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 23 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 24 */ 25 #ifndef NGTCP2_ACKTR_H 26 #define NGTCP2_ACKTR_H 27 28 #ifdef HAVE_CONFIG_H 29 # include <config.h> 30 #endif /* HAVE_CONFIG_H */ 31 32 #include <ngtcp2/ngtcp2.h> 33 34 #include "ngtcp2_mem.h" 35 #include "ngtcp2_ringbuf.h" 36 #include "ngtcp2_ksl.h" 37 #include "ngtcp2_pkt.h" 38 #include "ngtcp2_objalloc.h" 39 40 /* NGTCP2_ACKTR_MAX_ENT is the maximum number of ngtcp2_acktr_entry 41 which ngtcp2_acktr stores. */ 42 #define NGTCP2_ACKTR_MAX_ENT 1024 43 44 typedef struct ngtcp2_log ngtcp2_log; 45 46 /* 47 * ngtcp2_acktr_entry is a range of packets which need to be acked. 48 */ 49 typedef struct ngtcp2_acktr_entry { 50 union { 51 struct { 52 /* pkt_num is the largest packet number to acknowledge in this 53 range. */ 54 int64_t pkt_num; 55 /* len is the consecutive packets started from pkt_num which 56 includes pkt_num itself counting in decreasing order. So pkt_num 57 = 987 and len = 2, this entry includes packet 987 and 986. */ 58 size_t len; 59 /* tstamp is the timestamp when a packet denoted by pkt_num is 60 received. */ 61 ngtcp2_tstamp tstamp; 62 }; 63 64 ngtcp2_opl_entry oplent; 65 }; 66 } ngtcp2_acktr_entry; 67 68 ngtcp2_objalloc_def(acktr_entry, ngtcp2_acktr_entry, oplent); 69 70 /* 71 * ngtcp2_acktr_entry_objalloc_new allocates memory for ent, and 72 * initializes it with the given parameters. The pointer to the 73 * allocated object is stored to |*ent|. 74 * 75 * This function returns 0 if it succeeds, or one of the following 76 * negative error codes: 77 * 78 * NGTCP2_ERR_NOMEM 79 * Out of memory. 80 */ 81 int ngtcp2_acktr_entry_objalloc_new(ngtcp2_acktr_entry **ent, int64_t pkt_num, 82 ngtcp2_tstamp tstamp, 83 ngtcp2_objalloc *objalloc); 84 85 /* 86 * ngtcp2_acktr_entry_objalloc_del deallocates memory allocated for 87 * |ent|. 88 */ 89 void ngtcp2_acktr_entry_objalloc_del(ngtcp2_acktr_entry *ent, 90 ngtcp2_objalloc *objalloc); 91 92 typedef struct ngtcp2_acktr_ack_entry { 93 /* largest_ack is the largest packet number in outgoing ACK frame */ 94 int64_t largest_ack; 95 /* pkt_num is the packet number that ACK frame is included. */ 96 int64_t pkt_num; 97 } ngtcp2_acktr_ack_entry; 98 99 /* NGTCP2_ACKTR_FLAG_NONE indicates that no flag set. */ 100 #define NGTCP2_ACKTR_FLAG_NONE 0x00u 101 /* NGTCP2_ACKTR_FLAG_IMMEDIATE_ACK indicates that immediate 102 acknowledgement is required. */ 103 #define NGTCP2_ACKTR_FLAG_IMMEDIATE_ACK 0x01u 104 /* NGTCP2_ACKTR_FLAG_ACTIVE_ACK indicates that there are pending 105 protected packet to be acknowledged. */ 106 #define NGTCP2_ACKTR_FLAG_ACTIVE_ACK 0x02u 107 /* NGTCP2_ACKTR_FLAG_CANCEL_TIMER is set when ACK delay timer is 108 expired and canceled. */ 109 #define NGTCP2_ACKTR_FLAG_CANCEL_TIMER 0x0100u 110 111 /* 112 * ngtcp2_acktr tracks received packets which we have to send ack. 113 */ 114 typedef struct ngtcp2_acktr { 115 ngtcp2_objalloc objalloc; 116 ngtcp2_ringbuf acks; 117 /* ents includes ngtcp2_acktr_entry sorted by decreasing order of 118 packet number. */ 119 ngtcp2_ksl ents; 120 ngtcp2_log *log; 121 const ngtcp2_mem *mem; 122 /* flags is bitwise OR of zero, or more of NGTCP2_ACKTR_FLAG_*. */ 123 uint16_t flags; 124 /* first_unacked_ts is timestamp when ngtcp2_acktr_entry is added 125 first time after the last outgoing ACK frame. */ 126 ngtcp2_tstamp first_unacked_ts; 127 /* rx_npkt is the number of packets received without sending ACK. */ 128 size_t rx_npkt; 129 } ngtcp2_acktr; 130 131 /* 132 * ngtcp2_acktr_init initializes |acktr|. 133 * 134 * This function returns 0 if it succeeds, or one of the following 135 * negative error codes: 136 * 137 * NGTCP2_ERR_NOMEM 138 * Out of memory. 139 */ 140 int ngtcp2_acktr_init(ngtcp2_acktr *acktr, ngtcp2_log *log, 141 const ngtcp2_mem *mem); 142 143 /* 144 * ngtcp2_acktr_free frees resources allocated for |acktr|. It frees 145 * any ngtcp2_acktr_entry added to |acktr|. 146 */ 147 void ngtcp2_acktr_free(ngtcp2_acktr *acktr); 148 149 /* 150 * ngtcp2_acktr_add adds packet number |pkt_num| to |acktr|. 151 * |active_ack| is nonzero if |pkt_num| is retransmittable packet. 152 * 153 * This function assumes that |acktr| does not contain |pkt_num|. 154 * 155 * This function returns 0 if it succeeds, or one of the following 156 * negative error codes: 157 * 158 * NGTCP2_ERR_NOMEM 159 * OUt of memory. 160 */ 161 int ngtcp2_acktr_add(ngtcp2_acktr *acktr, int64_t pkt_num, int active_ack, 162 ngtcp2_tstamp ts); 163 164 /* 165 * ngtcp2_acktr_forget removes all entries which have the packet 166 * number that is equal to or less than ent->pkt_num. This function 167 * assumes that |acktr| includes |ent|. 168 */ 169 void ngtcp2_acktr_forget(ngtcp2_acktr *acktr, ngtcp2_acktr_entry *ent); 170 171 /* 172 * ngtcp2_acktr_get returns the pointer to pointer to the entry which 173 * has the largest packet number to be acked. If there is no entry, 174 * returned value satisfies ngtcp2_ksl_it_end(&it) != 0. 175 */ 176 ngtcp2_ksl_it ngtcp2_acktr_get(ngtcp2_acktr *acktr); 177 178 /* 179 * ngtcp2_acktr_empty returns nonzero if it has no packet to 180 * acknowledge. 181 */ 182 int ngtcp2_acktr_empty(ngtcp2_acktr *acktr); 183 184 /* 185 * ngtcp2_acktr_add_ack records outgoing ACK frame whose largest 186 * acknowledged packet number is |largest_ack|. |pkt_num| is the 187 * packet number of a packet in which ACK frame is included. This 188 * function returns a pointer to the object it adds. 189 */ 190 ngtcp2_acktr_ack_entry * 191 ngtcp2_acktr_add_ack(ngtcp2_acktr *acktr, int64_t pkt_num, int64_t largest_ack); 192 193 /* 194 * ngtcp2_acktr_recv_ack processes the incoming ACK frame |fr|. 195 * |pkt_num| is a packet number which includes |fr|. If we receive 196 * ACK which acknowledges the ACKs added by ngtcp2_acktr_add_ack, 197 * ngtcp2_acktr_entry which the outgoing ACK acknowledges is removed. 198 */ 199 void ngtcp2_acktr_recv_ack(ngtcp2_acktr *acktr, const ngtcp2_ack *fr); 200 201 /* 202 * ngtcp2_acktr_commit_ack tells |acktr| that ACK frame is generated. 203 */ 204 void ngtcp2_acktr_commit_ack(ngtcp2_acktr *acktr); 205 206 /* 207 * ngtcp2_acktr_require_active_ack returns nonzero if ACK frame should 208 * be generated actively. 209 */ 210 int ngtcp2_acktr_require_active_ack(ngtcp2_acktr *acktr, 211 ngtcp2_duration max_ack_delay, 212 ngtcp2_tstamp ts); 213 214 /* 215 * ngtcp2_acktr_immediate_ack tells |acktr| that immediate 216 * acknowledgement is required. 217 */ 218 void ngtcp2_acktr_immediate_ack(ngtcp2_acktr *acktr); 219 220 #endif /* NGTCP2_ACKTR_H */ 221