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