CHANGELOG revision bdba46fd
12018-04-23 2 3 - Fix busy loop: tickable must make progress. When connection is 4 self-reporting as tickable, it must make progress when ticked. There 5 are two issues: 6 1. If there are buffered packets, the connection is only tickable if 7 they can be sent out. 8 2. A connection is tickable if there are streams on the servicing 9 queue. When the tick occurs, we must service the stream 10 independent of whether any packets are sent. 11 - Fix assertion in pacer which can be incorrect under some 12 conditions. 13 - cmake: do not turn on address sanitizer if in Travis. 14 152018-04-20 16 17 - [BUGFIX] Fix bug in lsquic_engine_connect() exposed by yesterday's 18 changes. 19 202018-04-19 21 22 - [BUGFIX] Add connection to Tickable Queue on stream write 23 - cmake: use MSVC variable instead of trying to detect 24 - engine: improve connection incref/decref logging 25 - stream: don't ignore errors that may occur on triggered flush 26 - connection: remove obsolete method 27 - engine: indicate connection as tickable if previous call went 28 over threshold 29 302018-04-09 31 32 [API Change, OPTIMIZATION] Only process conns that need to be processed 33 34 The API is simplified: do not expose the user code to several 35 queues. A "connection queue" is now an internal concept. 36 The user processes connections using the single function 37 lsquic_engine_process_conns(). When this function is called, 38 only those connections are processed that need to be processed. 39 A connection needs to be processed when: 40 41 1. New incoming packets have been fed to the connection. 42 2. User wants to read from a stream that is readable. 43 3. User wants to write to a stream that is writeable. 44 4. There are buffered packets that can be sent out. (This 45 means that the user wrote to a stream outside of the 46 lsquic library callback.) 47 5. A control frame (such as BLOCKED) needs to be sent out. 48 6. A stream needs to be serviced or delayed stream needs to 49 be created. 50 7. An alarm rings. 51 8. Pacer timer expires. 52 53 To achieve this, the library places the connections into two 54 priority queues (min heaps): 55 56 1. Tickable Queue; and 57 2. Advisory Tick Time queue (ATTQ). 58 59 Each time lsquic_engine_process_conns() is called, the Tickable 60 Queue is emptied. After the connections have been ticked, they are 61 queried again: if a connection is not being closed, it is placed 62 either in the Tickable Queue if it is ready to be ticked again or 63 it is placed in the Advisory Tick Time Queue. It is assumed that 64 a connection always has at least one timer set (the idle alarm). 65 66 The connections in the Tickable Queue are arranged in the least 67 recently ticked order. This lets connections that have been quiet 68 longer to get their packets scheduled first. 69 70 This change means that the library no longer needs to be ticked 71 periodically. The user code can query the library when is the 72 next tick event and schedule it exactly. When connections are 73 processed, only the tickable connections are processed, not *all* 74 the connections. When there are no tick events, it means that no 75 timer event is necessary -- only the file descriptor READ event 76 is active. 77 78 The following are improvements and simplifications that have 79 been triggered: 80 81 - Queue of connections with incoming packets is gone. 82 - "Pending Read/Write Events" Queue is gone (along with its 83 history and progress checks). This queue has become the 84 Tickable Queue. 85 - The connection hash no longer needs to track the connection 86 insertion order. 87 882018-04-02 89 90 - [FEATURE] Windows support 91 92 - Reduce stack use -- outgoing packet batch is now allocated on the heap. 93 942018-03-09 95 96 - [OPTIMIZATION] Merge series of ACKs if possible 97 98 Parsed single-range ACK frames (that is the majority of frames) are 99 saved in the connection and their processing is deferred until the 100 connection is ticked. If several ACKs come in a series between 101 adjacent ticks, we check whether the latest ACK is a strict superset 102 of the saved ACK. If it is, the older ACK is not processed. 103 104 If ACK frames can be merged, they are merged and only one of them is 105 either processed or saved. 106 107 - [OPTIMIZATION] Speed up ACK verification by simplifying send history. 108 109 Never generate a gap in the sent packet number sequence. This reduces 110 the send history to a single number instead of potentially a series of 111 packet ranges and thereby speeds up ACK verification. 112 113 By default, detecting a gap in the send history is not fatal: only a 114 single warning is generated per connection. The connection can continue 115 to operate even if the ACK verification code is not able to detect some 116 inconsistencies. 117 118 - [OPTIMIZATION] Rearrange the lsquic_send_ctl struct 119 120 The first part of struct lsquic_send_ctl now consists of members that 121 are used in lsquic_send_ctl_got_ack() (in the absense of packet loss, 122 which is the normal case). To speed up reads and writes, we no longer 123 try to save space by using 8- and 16-bit integers. Use regular integer 124 width for everything. 125 126 - [OPTIMIZATION] Cache size of sent packet. 127 128 - [OPTIMIZATION] Keep track of the largest ACKed in packet_out 129 130 Instead of parsing our own ACK frames when packet has been acked, 131 use the value saved in the packet_out structure when the ACK frame 132 was generated. 133 134 - [OPTIMIZATION] Take RTT sampling conditional out of ACK loop 135 136 - [OPTIMIZATION] ACK processing: only call clock_gettime() if needed 137 138 - [OPTIMIZATION] Several code-level optimizations to ACK processing. 139 140 - Fix: http_client: fix -I flag; switch assert() to abort() 141 1422018-02-26 143 - [API Change] lsquic_engine_connect() returns pointer to the connection 144 object. 145 - [API Change] Add lsquic_conn_get_engine() to get engine object from 146 connection object. 147 - [API Change] Add lsquic_conn_status() to query connection status. 148 - [API Change] Add add lsquic_conn_set_ctx(). 149 - [API Change] Add new timestamp format, e.g. 2017-03-21 13:43:46.671345 150 - [OPTIMIZATION] Process handshake STREAM frames as soon as packet 151 arrives. 152 - [OPTIMIZATION] Do not compile expensive send controller sanity check 153 by default. 154 - [OPTIMIZATION] Add fast path to gquic_be_gen_reg_pkt_header. 155 - [OPTIMIZATION] Only make squeeze function call if necessary. 156 - [OPTIMIZATION] Speed up Q039 ACK frame parsing. 157 - [OPTIMIZATION] Fit most used elements of packet_out into first 64 bytes. 158 - [OPTIMIZATION] Keep track of scheduled bytes instead of calculating. 159 - [OPTIMIZATION] Prefetch next unacked packet when processing ACK. 160 - [OPTIMIZATION] Leverage fact that ACK ranges and unacked list are. 161 ordered. 162 - [OPTIMIZATION] Reduce function pointer use for STREAM frame generation 163 - Fix: reset incoming streams that arrive after we send GOAWAY. 164 - Fix: delay client on_new_conn() call until connection is fully set up. 165 - Fixes to buffered packets logic: splitting, STREAM frame elision. 166 - Fix: do not dispatch on_write callback if no packets are available. 167 - Fix WINDOW_UPDATE send and resend logic. 168 - Fix STREAM frame extension code. 169 - Fix: Drop unflushed data when stream is reset. 170 - Switch to tracking CWND using bytes rather than packets. 171 - Fix TCP friendly adjustment in cubic. 172 - Fix: do not generate invalid STOP_WAITING frames during high packet 173 loss. 174 - Pacer fixes. 175 1762017-12-18 177 178 - Fix: better follow cubic curve after idle period 179 - Fix: add missing parts to outgoing packet splitting code 180 - Fix: compilation using gcc 4.8.4 181 1822017-10-31 183 184 - Add APIs.txt -- describes LSQUIC APIs 185 1862017-10-31 187 188 - [API Change] Sendfile-like functionality is gone. The stream no 189 longer opens files and deals with file descriptors. (Among other 190 things, this makes the code more portable.) Three writing functions 191 are provided: 192 193 lsquic_stream_write 194 lsquic_stream_writev 195 lsquic_stream_writef (NEW) 196 197 lsquic_stream_writef() is given an abstract reader that has function 198 pointers for size() and read() functions which the user can implement. 199 This is the most flexible way. lsquic_stream_write() and 200 lsquic_stream_writev() are now both implemented as wrappers around 201 lsquic_stream_writef(). 202 203 - [OPTIMIZATION] When writing to stream, be it within or without the 204 on_write() callback, place data directly into packet buffer, 205 bypassing auxiliary data structures. This reduces amount of memory 206 required, for the amount of data that can be written is limited 207 by the congestion window. 208 209 To support writes outside the on_write() callback, we keep N 210 outgoing packet buffers per connection which can be written to 211 by any stream. One half of these are reserved for the highest 212 priority stream(s), the other half for all other streams. This way, 213 low-priority streams cannot write instead of high-priority streams 214 and, on the other hand, low-priority streams get a chance to send 215 their packets out. 216 217 The algorithm is as follows: 218 219 - When user writes to stream outside of the callback: 220 - If this is the highest priority stream, place it onto the 221 reserved N/2 queue or fail. 222 (The actual size of this queue is dynamic -- MAX(N/2, CWND) -- 223 rather than N/2, allowing high-priority streams to write as 224 much as can be sent.) 225 - If the stream is not the highest priority, try to place the 226 data onto the reserved N/2 queue or fail. 227 - When tick occurs *and* more packets can be scheduled: 228 - Transfer packets from the high N/2 queue to the scheduled 229 queue. 230 - If more scheduling is allowed: 231 - Call on_write callbacks for highest-priority streams, 232 placing resulting packets directly onto the scheduled queue. 233 - If more scheduling is allowed: 234 - Transfer packets from the low N/2 queue to the scheduled 235 queue. 236 - If more scheduling is allowed: 237 - Call on_write callbacks for non-highest-priority streams, 238 placing resulting packets directly onto the scheduled queue 239 240 The number N is currently 20, but it could be varied based on 241 resource usage. 242 243 - If stream is created due to incoming headers, make headers readable 244 from on_new. 245 246 - Outgoing packets are no longer marked non-writeable to prevent placing 247 more than one STREAM frame from the same stream into a single packet. 248 This property is maintained via code flow and an explicit check. 249 Packets for stream data are allocated using a special function. 250 251 - STREAM frame elision is cheaper, as we only perform it if a reset 252 stream has outgoing packets referencing it. 253 254 - lsquic_packet_out_t is smaller, as stream_rec elements are now 255 inside a union. 256 2572017-10-12 258 259 - Do not send RST_STREAM when stream is closed for reading 260 - Raise maximum header size from 4K to 64K 261 - Check header name and value lengths against maximum imposed by HPACK 262 - Fix NULL dereference in stream flow controller 263 2642017-10-09 265 266 - Hide handshake implementation behind a set of function pointers 267 - Use monotonically increasing clock 268 - Make sure that retx delay is not larger than the max of 60 seconds 269 2702017-09-29 271 272 - A few fixes to code and README 273 2742017-09-28 275 276 - Add support for Q041; drop support for Q040 277 2782017-09-27 279 280 - Fix CMakeLists.txt: BoringSSL include and lib was mixed up 281 2822017-09-26 283 284 - Add support for Mac OS 285 - Add support for Raspberry Pi 286 - Fix BoringSSL compilation: include <openssl/hmac.h> explicitly 287 2882017-09-22 289 290 - Initial release 291