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_RTB_H 26 #define NGTCP2_RTB_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_pkt.h" 35 #include "ngtcp2_ksl.h" 36 #include "ngtcp2_pq.h" 37 38 typedef struct ngtcp2_conn ngtcp2_conn; 39 typedef struct ngtcp2_pktns ngtcp2_pktns; 40 typedef struct ngtcp2_log ngtcp2_log; 41 typedef struct ngtcp2_qlog ngtcp2_qlog; 42 typedef struct ngtcp2_strm ngtcp2_strm; 43 typedef struct ngtcp2_rst ngtcp2_rst; 44 45 /* NGTCP2_FRAME_CHAIN_BINDER_FLAG_NONE indicates that no flag is 46 set. */ 47 #define NGTCP2_FRAME_CHAIN_BINDER_FLAG_NONE 0x00 48 /* NGTCP2_FRAME_CHAIN_BINDER_FLAG_ACK indicates that an information 49 which a frame carries has been acknowledged. */ 50 #define NGTCP2_FRAME_CHAIN_BINDER_FLAG_ACK 0x01 51 52 /* 53 * ngtcp2_frame_chain_binder binds 2 or more of ngtcp2_frame_chain to 54 * share the acknowledgement state. In general, all 55 * ngtcp2_frame_chains bound to the same binder must have the same 56 * information. 57 */ 58 typedef struct ngtcp2_frame_chain_binder { 59 size_t refcount; 60 /* flags is bitwise OR of zero or more of 61 NGTCP2_FRAME_CHAIN_BINDER_FLAG_*. */ 62 uint32_t flags; 63 } ngtcp2_frame_chain_binder; 64 65 int ngtcp2_frame_chain_binder_new(ngtcp2_frame_chain_binder **pbinder, 66 const ngtcp2_mem *mem); 67 68 typedef struct ngtcp2_frame_chain ngtcp2_frame_chain; 69 70 /* 71 * ngtcp2_frame_chain chains frames in a single packet. 72 */ 73 struct ngtcp2_frame_chain { 74 ngtcp2_frame_chain *next; 75 ngtcp2_frame_chain_binder *binder; 76 ngtcp2_frame fr; 77 }; 78 79 /* 80 * ngtcp2_bind_frame_chains binds two frame chains |a| and |b| using 81 * new or existing ngtcp2_frame_chain_binder. |a| might have non-NULL 82 * a->binder. |b| must not have non-NULL b->binder. 83 * 84 * This function returns 0 if it succeeds, or one of the following 85 * negative error codes: 86 * 87 * NGTCP2_ERR_NOMEM 88 * Out of memory 89 */ 90 int ngtcp2_bind_frame_chains(ngtcp2_frame_chain *a, ngtcp2_frame_chain *b, 91 const ngtcp2_mem *mem); 92 93 /* NGTCP2_MAX_STREAM_DATACNT is the maximum number of ngtcp2_vec that 94 a ngtcp2_stream can include. */ 95 #define NGTCP2_MAX_STREAM_DATACNT 256 96 97 /* NGTCP2_MAX_CRYPTO_DATACNT is the maximum number of ngtcp2_vec that 98 a ngtcp2_crypto can include. */ 99 #define NGTCP2_MAX_CRYPTO_DATACNT 8 100 101 /* 102 * ngtcp2_frame_chain_new allocates ngtcp2_frame_chain object and 103 * assigns its pointer to |*pfrc|. 104 * 105 * This function returns 0 if it succeeds, or one of the following 106 * negative error codes: 107 * 108 * NGTCP2_ERR_NOMEM 109 * Out of memory. 110 */ 111 int ngtcp2_frame_chain_new(ngtcp2_frame_chain **pfrc, const ngtcp2_mem *mem); 112 113 /* 114 * ngtcp2_frame_chain_extralen_new works like ngtcp2_frame_chain_new, 115 * but it allocates extra memory |extralen| in order to extend 116 * ngtcp2_frame. 117 */ 118 int ngtcp2_frame_chain_extralen_new(ngtcp2_frame_chain **pfrc, size_t extralen, 119 const ngtcp2_mem *mem); 120 121 /* 122 * ngtcp2_frame_chain_stream_datacnt_new works like 123 * ngtcp2_frame_chain_new, but it allocates enough data to store 124 * additional |datacnt| - 1 ngtcp2_vec object after ngtcp2_stream 125 * object. If |datacnt| equals to 1, ngtcp2_frame_chain_new is called 126 * internally. 127 */ 128 int ngtcp2_frame_chain_stream_datacnt_new(ngtcp2_frame_chain **pfrc, 129 size_t datacnt, 130 const ngtcp2_mem *mem); 131 132 /* 133 * ngtcp2_frame_chain_crypto_datacnt_new works like 134 * ngtcp2_frame_chain_new, but it allocates enough data to store 135 * additional |datacnt| - 1 ngtcp2_vec object after ngtcp2_crypto 136 * object. If |datacnt| equals to 1, ngtcp2_frame_chain_new is called 137 * internally. 138 */ 139 int ngtcp2_frame_chain_crypto_datacnt_new(ngtcp2_frame_chain **pfrc, 140 size_t datacnt, 141 const ngtcp2_mem *mem); 142 143 int ngtcp2_frame_chain_new_token_new(ngtcp2_frame_chain **pfrc, 144 const ngtcp2_vec *token, 145 const ngtcp2_mem *mem); 146 147 /* 148 * ngtcp2_frame_chain_del deallocates |frc|. It also deallocates the 149 * memory pointed by |frc|. 150 */ 151 void ngtcp2_frame_chain_del(ngtcp2_frame_chain *frc, const ngtcp2_mem *mem); 152 153 /* 154 * ngtcp2_frame_chain_init initializes |frc|. 155 */ 156 void ngtcp2_frame_chain_init(ngtcp2_frame_chain *frc); 157 158 /* 159 * ngtcp2_frame_chain_list_del deletes |frc|, and all objects 160 * connected by next field. 161 */ 162 void ngtcp2_frame_chain_list_del(ngtcp2_frame_chain *frc, 163 const ngtcp2_mem *mem); 164 165 /* NGTCP2_RTB_ENTRY_FLAG_NONE indicates that no flag is set. */ 166 #define NGTCP2_RTB_ENTRY_FLAG_NONE 0x00 167 /* NGTCP2_RTB_ENTRY_FLAG_PROBE indicates that the entry includes a 168 probe packet. */ 169 #define NGTCP2_RTB_ENTRY_FLAG_PROBE 0x01 170 /* NGTCP2_RTB_ENTRY_FLAG_RETRANSMITTABLE indicates that the entry 171 includes a frame which must be retransmitted until it is 172 acknowledged. In most cases, this flag is used along with 173 NGTCP2_RTB_ENTRY_FLAG_ACK_ELICITING. We have these 2 flags because 174 NGTCP2_RTB_ENTRY_FLAG_RETRANSMITTABLE triggers PTO, but just 175 NGTCP2_RTB_ENTRY_FLAG_ACK_ELICITING does not. */ 176 #define NGTCP2_RTB_ENTRY_FLAG_RETRANSMITTABLE 0x02 177 /* NGTCP2_RTB_ENTRY_FLAG_ACK_ELICITING indicates that the entry 178 elicits acknowledgement. */ 179 #define NGTCP2_RTB_ENTRY_FLAG_ACK_ELICITING 0x04 180 /* NGTCP2_RTB_ENTRY_FLAG_PTO_RECLAIMED indicates that the packet has 181 been reclaimed on PTO. It is not marked lost yet and still 182 consumes congestion window. */ 183 #define NGTCP2_RTB_ENTRY_FLAG_PTO_RECLAIMED 0x08 184 /* NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED indicates that the entry 185 has been marked lost and, optionally, scheduled to retransmit. */ 186 #define NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED 0x10 187 /* NGTCP2_RTB_ENTRY_FLAG_ECN indicates that the entry is included in a 188 UDP datagram with ECN marking. */ 189 #define NGTCP2_RTB_ENTRY_FLAG_ECN 0x20 190 /* NGTCP2_RTB_ENTRY_FLAG_DATAGRAM indicates that the entry includes 191 DATAGRAM frame. */ 192 #define NGTCP2_RTB_ENTRY_FLAG_DATAGRAM 0x40 193 194 typedef struct ngtcp2_rtb_entry ngtcp2_rtb_entry; 195 196 /* 197 * ngtcp2_rtb_entry is an object stored in ngtcp2_rtb. It corresponds 198 * to the one packet which is waiting for its ACK. 199 */ 200 struct ngtcp2_rtb_entry { 201 ngtcp2_rtb_entry *next; 202 203 struct { 204 int64_t pkt_num; 205 uint8_t type; 206 uint8_t flags; 207 } hd; 208 ngtcp2_frame_chain *frc; 209 /* ts is the time point when a packet included in this entry is sent 210 to a peer. */ 211 ngtcp2_tstamp ts; 212 /* lost_ts is the time when this entry is marked lost. */ 213 ngtcp2_tstamp lost_ts; 214 /* pktlen is the length of QUIC packet */ 215 size_t pktlen; 216 struct { 217 uint64_t delivered; 218 ngtcp2_tstamp delivered_ts; 219 ngtcp2_tstamp first_sent_ts; 220 int is_app_limited; 221 } rst; 222 /* flags is bitwise-OR of zero or more of 223 NGTCP2_RTB_ENTRY_FLAG_*. */ 224 uint8_t flags; 225 }; 226 227 /* 228 * ngtcp2_rtb_entry_new allocates ngtcp2_rtb_entry object, and assigns 229 * its pointer to |*pent|. On success, |*pent| takes ownership of 230 * |frc|. 231 * 232 * This function returns 0 if it succeeds, or one of the following 233 * negative error codes: 234 * 235 * NGTCP2_ERR_NOMEM 236 * Out of memory. 237 */ 238 int ngtcp2_rtb_entry_new(ngtcp2_rtb_entry **pent, const ngtcp2_pkt_hd *hd, 239 ngtcp2_frame_chain *frc, ngtcp2_tstamp ts, 240 size_t pktlen, uint8_t flags, const ngtcp2_mem *mem); 241 242 /* 243 * ngtcp2_rtb_entry_del deallocates |ent|. It also frees memory 244 * pointed by |ent|. 245 */ 246 void ngtcp2_rtb_entry_del(ngtcp2_rtb_entry *ent, const ngtcp2_mem *mem); 247 248 /* 249 * ngtcp2_rtb tracks sent packets, and its ACK timeout for 250 * retransmission. 251 */ 252 typedef struct ngtcp2_rtb { 253 /* ents includes ngtcp2_rtb_entry sorted by decreasing order of 254 packet number. */ 255 ngtcp2_ksl ents; 256 /* crypto is CRYPTO stream. */ 257 ngtcp2_strm *crypto; 258 ngtcp2_rst *rst; 259 ngtcp2_cc *cc; 260 ngtcp2_log *log; 261 ngtcp2_qlog *qlog; 262 const ngtcp2_mem *mem; 263 /* largest_acked_tx_pkt_num is the largest packet number 264 acknowledged by the peer. */ 265 int64_t largest_acked_tx_pkt_num; 266 /* num_ack_eliciting is the number of ACK eliciting entries. */ 267 size_t num_ack_eliciting; 268 /* num_retransmittable is the number of packets which contain frames 269 that must be retransmitted on loss. */ 270 size_t num_retransmittable; 271 /* probe_pkt_left is the number of probe packet to send */ 272 size_t probe_pkt_left; 273 /* pktns_id is the identifier of packet number space. */ 274 ngtcp2_pktns_id pktns_id; 275 /* cc_pkt_num is the smallest packet number that is contributed to 276 ngtcp2_conn_stat.bytes_in_flight. */ 277 int64_t cc_pkt_num; 278 /* cc_bytes_in_flight is the number of in-flight bytes that is 279 contributed to ngtcp2_conn_stat.bytes_in_flight. It only 280 includes the bytes after congestion state is reset. */ 281 uint64_t cc_bytes_in_flight; 282 /* persistent_congestion_start_ts is the time when persistent 283 congestion evaluation is started. It happens roughly after 284 handshake is confirmed. */ 285 ngtcp2_tstamp persistent_congestion_start_ts; 286 /* num_lost_pkts is the number entries in ents which has 287 NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED flag set. */ 288 size_t num_lost_pkts; 289 } ngtcp2_rtb; 290 291 /* 292 * ngtcp2_rtb_init initializes |rtb|. 293 */ 294 void ngtcp2_rtb_init(ngtcp2_rtb *rtb, ngtcp2_pktns_id pktns_id, 295 ngtcp2_strm *crypto, ngtcp2_rst *rst, ngtcp2_cc *cc, 296 ngtcp2_log *log, ngtcp2_qlog *qlog, const ngtcp2_mem *mem); 297 298 /* 299 * ngtcp2_rtb_free deallocates resources allocated for |rtb|. 300 */ 301 void ngtcp2_rtb_free(ngtcp2_rtb *rtb); 302 303 /* 304 * ngtcp2_rtb_add adds |ent| to |rtb|. 305 * 306 * This function returns 0 if it succeeds, or one of the following 307 * negative error codes: 308 * 309 * NGTCP2_ERR_NOMEM 310 * Out of memory 311 */ 312 int ngtcp2_rtb_add(ngtcp2_rtb *rtb, ngtcp2_rtb_entry *ent, 313 ngtcp2_conn_stat *cstat); 314 315 /* 316 * ngtcp2_rtb_head returns the iterator which points to the entry 317 * which has the largest packet number. If there is no entry, 318 * returned value satisfies ngtcp2_ksl_it_end(&it) != 0. 319 */ 320 ngtcp2_ksl_it ngtcp2_rtb_head(ngtcp2_rtb *rtb); 321 322 /* 323 * ngtcp2_rtb_recv_ack removes acked ngtcp2_rtb_entry from |rtb|. 324 * |pkt_num| is a packet number which includes |fr|. |pkt_ts| is the 325 * timestamp when packet is received. |ts| should be the current 326 * time. Usually they are the same, but for buffered packets, 327 * |pkt_ts| would be earlier than |ts|. 328 * 329 * This function returns the number of newly acknowledged packets if 330 * it succeeds, or one of the following negative error codes: 331 * 332 * NGTCP2_ERR_CALLBACK_FAILURE 333 * User callback failed 334 * NGTCP2_ERR_NOMEM 335 * Out of memory 336 */ 337 ngtcp2_ssize ngtcp2_rtb_recv_ack(ngtcp2_rtb *rtb, const ngtcp2_ack *fr, 338 ngtcp2_conn_stat *cstat, ngtcp2_conn *conn, 339 ngtcp2_pktns *pktns, ngtcp2_tstamp pkt_ts, 340 ngtcp2_tstamp ts); 341 342 /* 343 * ngtcp2_rtb_detect_lost_pkt detects lost packets and prepends the 344 * frames contained them to |*pfrc|. Even when this function fails, 345 * some frames might be prepended to |*pfrc| and the caller should 346 * handle them. 347 */ 348 int ngtcp2_rtb_detect_lost_pkt(ngtcp2_rtb *rtb, ngtcp2_conn *conn, 349 ngtcp2_pktns *pktns, ngtcp2_conn_stat *cstat, 350 ngtcp2_tstamp ts); 351 352 /* 353 * ngtcp2_rtb_remove_expired_lost_pkt removes expired lost packet. 354 */ 355 void ngtcp2_rtb_remove_expired_lost_pkt(ngtcp2_rtb *rtb, ngtcp2_duration pto, 356 ngtcp2_tstamp ts); 357 358 /* 359 * ngtcp2_rtb_lost_pkt_ts returns the earliest time when the still 360 * retained packet was lost. It returns UINT64_MAX if no such packet 361 * exists. 362 */ 363 ngtcp2_tstamp ngtcp2_rtb_lost_pkt_ts(ngtcp2_rtb *rtb); 364 365 /* 366 * ngtcp2_rtb_remove_all removes all packets from |rtb| and prepends 367 * all frames to |*pfrc|. Even when this function fails, some frames 368 * might be prepended to |*pfrc| and the caller should handle them. 369 */ 370 int ngtcp2_rtb_remove_all(ngtcp2_rtb *rtb, ngtcp2_conn *conn, 371 ngtcp2_pktns *pktns, ngtcp2_conn_stat *cstat); 372 373 /* 374 * ngtcp2_rtb_remove_early_data removes all entries for 0RTT packets. 375 */ 376 void ngtcp2_rtb_remove_early_data(ngtcp2_rtb *rtb, ngtcp2_conn_stat *cstat); 377 378 /* 379 * ngtcp2_rtb_empty returns nonzero if |rtb| have no entry. 380 */ 381 int ngtcp2_rtb_empty(ngtcp2_rtb *rtb); 382 383 /* 384 * ngtcp2_rtb_reset_cc_state resets congestion state in |rtb|. 385 * |cc_pkt_num| is the next outbound packet number which is sent under 386 * new congestion state. 387 */ 388 void ngtcp2_rtb_reset_cc_state(ngtcp2_rtb *rtb, int64_t cc_pkt_num); 389 390 /* 391 * ngtcp2_rtb_remove_expired_lost_pkt ensures that the number of lost 392 * packets at most |n|. 393 */ 394 void ngtcp2_rtb_remove_excessive_lost_pkt(ngtcp2_rtb *rtb, size_t n); 395 396 /* 397 * ngtcp2_rtb_reclaim_on_pto reclaims up to |num_pkts| packets which 398 * are in-flight and not marked lost to send them in PTO probe. The 399 * reclaimed frames are chained to |*pfrc|. 400 * 401 * This function returns the number of packets reclaimed if it 402 * succeeds, or one of the following negative error codes: 403 * 404 * NGTCP2_ERR_NOMEM 405 * Out of memory 406 */ 407 ngtcp2_ssize ngtcp2_rtb_reclaim_on_pto(ngtcp2_rtb *rtb, ngtcp2_conn *conn, 408 ngtcp2_pktns *pktns, size_t num_pkts); 409 410 #endif /* NGTCP2_RTB_H */ 411