Mercurial > hg > nginx-quic

comparison src/http/v3/ngx_http_v3_tables.c @ 7951:c9538aef3211 quic

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
HTTP/3: refactored dynamic table implementation. Previously dynamic table was not functional because of zero limit on its size set by default. Now the following changes enable it: - new directives to set SETTINGS_QPACK_MAX_TABLE_CAPACITY and SETTINGS_QPACK_BLOCKED_STREAMS - send settings with SETTINGS_QPACK_MAX_TABLE_CAPACITY and SETTINGS_QPACK_BLOCKED_STREAMS to the client - send Insert Count Increment to the client - send Header Acknowledgement to the client - evict old dynamic table entries on overflow - decode Required Insert Count from client - block stream if Required Insert Count is not reached
author Roman Arutyunyan <arut@nginx.com>
date Thu, 02 Jul 2020 15:34:05 +0300
parents 26cb2f3259b1
children 72f9ff4e0a88
comparison
equal deleted inserted replaced
7950:b0e81f49d7c0 7951:c9538aef3211
8 #include <ngx_config.h> 8 #include <ngx_config.h>
9 #include <ngx_core.h> 9 #include <ngx_core.h>
10 #include <ngx_http.h> 10 #include <ngx_http.h>
11 11
12 12
13 static ngx_array_t *ngx_http_v3_get_dynamic_table(ngx_connection_t *c); 13 #define ngx_http_v3_table_entry_size(n, v) ((n)->len + (v)->len + 32)
14
15
16 static ngx_int_t ngx_http_v3_evict(ngx_connection_t *c, size_t need);
17 static void ngx_http_v3_cleanup_table(void *data);
18 static void ngx_http_v3_unblock(void *data);
14 static ngx_int_t ngx_http_v3_new_header(ngx_connection_t *c); 19 static ngx_int_t ngx_http_v3_new_header(ngx_connection_t *c);
20
21
22 typedef struct {
23 ngx_queue_t queue;
24 ngx_connection_t *connection;
25 ngx_uint_t *nblocked;
26 } ngx_http_v3_block_t;
15 27
16 28
17 static ngx_http_v3_header_t ngx_http_v3_static_table[] = { 29 static ngx_http_v3_header_t ngx_http_v3_static_table[] = {
18 30
19 { ngx_string(":authority"), ngx_string("") }, 31 { ngx_string(":authority"), ngx_string("") },
146 158
147 ngx_int_t 159 ngx_int_t
148 ngx_http_v3_ref_insert(ngx_connection_t *c, ngx_uint_t dynamic, 160 ngx_http_v3_ref_insert(ngx_connection_t *c, ngx_uint_t dynamic,
149 ngx_uint_t index, ngx_str_t *value) 161 ngx_uint_t index, ngx_str_t *value)
150 { 162 {
151 ngx_array_t *dt; 163 ngx_str_t name;
152 ngx_connection_t *pc; 164
153 ngx_http_v3_header_t *ref, *h; 165 if (dynamic) {
154 166 ngx_log_debug2(NGX_LOG_DEBUG_HTTP, c->log, 0,
155 ngx_log_debug3(NGX_LOG_DEBUG_HTTP, c->log, 0, 167 "http3 ref insert dynamic[%ui] \"%V\"", index, value);
156 "http3 ref insert %s[$ui] \"%V\"", 168
157 dynamic ? "dynamic" : "static", index, value); 169 if (ngx_http_v3_lookup(c, index, &name, NULL) != NGX_OK) {
158 170 return NGX_ERROR;
159 pc = c->qs->parent; 171 }
160 172
161 ref = ngx_http_v3_lookup_table(c, dynamic, index); 173 } else {
162 if (ref == NULL) { 174 ngx_log_debug2(NGX_LOG_DEBUG_HTTP, c->log, 0,
163 return NGX_ERROR; 175 "http3 ref insert static[%ui] \"%V\"", index, value);
164 } 176
165 177 if (ngx_http_v3_lookup_static(c, index, &name, NULL) != NGX_OK) {
166 dt = ngx_http_v3_get_dynamic_table(c); 178 return NGX_ERROR;
167 if (dt == NULL) { 179 }
168 return NGX_ERROR; 180 }
169 } 181
170 182 return ngx_http_v3_insert(c, &name, value);
171 h = ngx_array_push(dt); 183 }
172 if (h == NULL) { 184
173 return NGX_ERROR; 185
174 } 186 ngx_int_t
175 187 ngx_http_v3_insert(ngx_connection_t *c, ngx_str_t *name, ngx_str_t *value)
176 h->name = ref->name; 188 {
177 189 u_char *p;
178 h->value.data = ngx_pstrdup(pc->pool, value); 190 size_t size;
179 if (h->value.data == NULL) { 191 ngx_http_v3_header_t *h;
180 h->value.len = 0; 192 ngx_http_v3_connection_t *h3c;
181 return NGX_ERROR; 193 ngx_http_v3_dynamic_table_t *dt;
182 } 194
183 195 size = ngx_http_v3_table_entry_size(name, value);
196
197 if (ngx_http_v3_evict(c, size) != NGX_OK) {
198 return NGX_ERROR;
199 }
200
201 h3c = c->qs->parent->data;
202 dt = &h3c->table;
203
204 ngx_log_debug4(NGX_LOG_DEBUG_HTTP, c->log, 0,
205 "http3 insert [%ui] \"%V\":\"%V\", size:%uz",
206 dt->base + dt->nelts, name, value, size);
207
208 p = ngx_alloc(sizeof(ngx_http_v3_header_t) + name->len + value->len,
209 c->log);
210 if (p == NULL) {
211 return NGX_ERROR;
212 }
213
214 h = (ngx_http_v3_header_t *) p;
215
216 h->name.data = p + sizeof(ngx_http_v3_header_t);
217 h->name.len = name->len;
218 h->value.data = ngx_cpymem(h->name.data, name->data, name->len);
184 h->value.len = value->len; 219 h->value.len = value->len;
220 ngx_memcpy(h->value.data, value->data, value->len);
221
222 dt->elts[dt->nelts++] = h;
223 dt->size += size;
224
225 /* TODO increment can be sent less often */
226
227 if (ngx_http_v3_client_inc_insert_count(c, 1) != NGX_OK) {
228 return NGX_ERROR;
229 }
185 230
186 if (ngx_http_v3_new_header(c) != NGX_OK) { 231 if (ngx_http_v3_new_header(c) != NGX_OK) {
187 return NGX_ERROR; 232 return NGX_ERROR;
188 } 233 }
189 234
190 return NGX_OK; 235 return NGX_OK;
191 } 236 }
192 237
193 238
194 ngx_int_t 239 ngx_int_t
195 ngx_http_v3_insert(ngx_connection_t *c, ngx_str_t *name,
196 ngx_str_t *value)
197 {
198 ngx_array_t *dt;
199 ngx_connection_t *pc;
200 ngx_http_v3_header_t *h;
201
202 ngx_log_debug2(NGX_LOG_DEBUG_HTTP, c->log, 0,
203 "http3 insert \"%V\":\"%V\"", name, value);
204
205 pc = c->qs->parent;
206
207 dt = ngx_http_v3_get_dynamic_table(c);
208 if (dt == NULL) {
209 return NGX_ERROR;
210 }
211
212 h = ngx_array_push(dt);
213 if (h == NULL) {
214 return NGX_ERROR;
215 }
216
217 h->name.data = ngx_pstrdup(pc->pool, name);
218 if (h->name.data == NULL) {
219 h->name.len = 0;
220 h->value.len = 0;
221 return NGX_ERROR;
222 }
223
224 h->name.len = name->len;
225
226 h->value.data = ngx_pstrdup(pc->pool, value);
227 if (h->value.data == NULL) {
228 h->value.len = 0;
229 return NGX_ERROR;
230 }
231
232 h->value.len = value->len;
233
234 if (ngx_http_v3_new_header(c) != NGX_OK) {
235 return NGX_ERROR;
236 }
237
238 return NGX_OK;
239 }
240
241
242 ngx_int_t
243 ngx_http_v3_set_capacity(ngx_connection_t *c, ngx_uint_t capacity) 240 ngx_http_v3_set_capacity(ngx_connection_t *c, ngx_uint_t capacity)
244 { 241 {
242 ngx_uint_t max, prev_max;
243 ngx_connection_t *pc;
244 ngx_pool_cleanup_t *cln;
245 ngx_http_v3_header_t **elts;
246 ngx_http_v3_srv_conf_t *v3cf;
247 ngx_http_v3_connection_t *h3c;
248 ngx_http_v3_dynamic_table_t *dt;
249
245 ngx_log_debug1(NGX_LOG_DEBUG_HTTP, c->log, 0, 250 ngx_log_debug1(NGX_LOG_DEBUG_HTTP, c->log, 0,
246 "http3 set capacity %ui", capacity); 251 "http3 set capacity %ui", capacity);
247 252
248 /* XXX ignore capacity */ 253 pc = c->qs->parent;
254 h3c = pc->data;
255 v3cf = ngx_http_get_module_srv_conf(h3c->hc.conf_ctx, ngx_http_v3_module);
256
257 if (capacity > v3cf->max_table_capacity) {
258 ngx_log_error(NGX_LOG_INFO, c->log, 0,
259 "client exceeded http3_max_table_capacity limit");
260 return NGX_ERROR;
261 }
262
263 dt = &h3c->table;
264
265 if (dt->size > capacity) {
266 if (ngx_http_v3_evict(c, dt->size - capacity) != NGX_OK) {
267 return NGX_ERROR;
268 }
269 }
270
271 max = capacity / 32;
272 prev_max = dt->capacity / 32;
273
274 if (max > prev_max) {
275 elts = ngx_alloc(max * sizeof(void *), c->log);
276 if (elts == NULL) {
277 return NGX_ERROR;
278 }
279
280 if (dt->elts == NULL) {
281 cln = ngx_pool_cleanup_add(pc->pool, 0);
282 if (cln == NULL) {
283 return NGX_ERROR;
284 }
285
286 cln->handler = ngx_http_v3_cleanup_table;
287 cln->data = dt;
288
289 } else {
290 ngx_memcpy(elts, dt->elts, dt->nelts * sizeof(void *));
291 ngx_free(dt->elts);
292 }
293
294 dt->elts = elts;
295 }
296
297 dt->capacity = capacity;
298
299 return NGX_OK;
300 }
301
302
303 static void
304 ngx_http_v3_cleanup_table(void *data)
305 {
306 ngx_http_v3_dynamic_table_t *dt = data;
307
308 ngx_uint_t n;
309
310 for (n = 0; n < dt->nelts; n++) {
311 ngx_free(dt->elts[n]);
312 }
313
314 ngx_free(dt->elts);
315 }
316
317
318 static ngx_int_t
319 ngx_http_v3_evict(ngx_connection_t *c, size_t need)
320 {
321 size_t size, target;
322 ngx_uint_t n;
323 ngx_http_v3_header_t *h;
324 ngx_http_v3_connection_t *h3c;
325 ngx_http_v3_dynamic_table_t *dt;
326
327 h3c = c->qs->parent->data;
328 dt = &h3c->table;
329
330 if (need > dt->capacity) {
331 ngx_log_error(NGX_LOG_ERR, c->log, 0,
332 "not enough dynamic table capacity");
333 return NGX_ERROR;
334 }
335
336 target = dt->capacity - need;
337 n = 0;
338
339 while (dt->size > target) {
340 h = dt->elts[n++];
341 size = ngx_http_v3_table_entry_size(&h->name, &h->value);
342
343 ngx_log_debug4(NGX_LOG_DEBUG_HTTP, c->log, 0,
344 "http3 evict [%ui] \"%V\":\"%V\" size:%uz",
345 dt->base, &h->name, &h->value, size);
346
347 ngx_free(h);
348 dt->size -= size;
349 }
350
351 if (n) {
352 dt->nelts -= n;
353 dt->base += n;
354 ngx_memmove(dt->elts, &dt->elts[n], dt->nelts * sizeof(void *));
355 }
249 356
250 return NGX_OK; 357 return NGX_OK;
251 } 358 }
252 359
253 360
254 ngx_int_t 361 ngx_int_t
255 ngx_http_v3_duplicate(ngx_connection_t *c, ngx_uint_t index) 362 ngx_http_v3_duplicate(ngx_connection_t *c, ngx_uint_t index)
256 { 363 {
257 ngx_array_t *dt; 364 ngx_str_t name, value;
258 ngx_http_v3_header_t *ref, *h; 365 ngx_http_v3_connection_t *h3c;
366 ngx_http_v3_dynamic_table_t *dt;
259 367
260 ngx_log_debug1(NGX_LOG_DEBUG_HTTP, c->log, 0, "http3 duplicate %ui", index); 368 ngx_log_debug1(NGX_LOG_DEBUG_HTTP, c->log, 0, "http3 duplicate %ui", index);
261 369
262 ref = ngx_http_v3_lookup_table(c, 1, index); 370 h3c = c->qs->parent->data;
263 if (ref == NULL) { 371 dt = &h3c->table;
264 return NGX_ERROR; 372
265 } 373 if (dt->base + dt->nelts <= index) {
266 374 return NGX_ERROR;
267 dt = ngx_http_v3_get_dynamic_table(c); 375 }
268 if (dt == NULL) { 376
269 return NGX_ERROR; 377 index = dt->base + dt->nelts - 1 - index;
270 } 378
271 379 if (ngx_http_v3_lookup(c, index, &name, &value) != NGX_OK) {
272 h = ngx_array_push(dt); 380 return NGX_ERROR;
273 if (h == NULL) { 381 }
274 return NGX_ERROR; 382
275 } 383 return ngx_http_v3_insert(c, &name, &value);
276
277 *h = *ref;
278
279 if (ngx_http_v3_new_header(c) != NGX_OK) {
280 return NGX_ERROR;
281 }
282
283 return NGX_OK;
284 } 384 }
285 385
286 386
287 ngx_int_t 387 ngx_int_t
288 ngx_http_v3_ack_header(ngx_connection_t *c, ngx_uint_t stream_id) 388 ngx_http_v3_ack_header(ngx_connection_t *c, ngx_uint_t stream_id)
318 418
319 return NGX_OK; 419 return NGX_OK;
320 } 420 }
321 421
322 422
323 static ngx_array_t * 423 ngx_int_t
324 ngx_http_v3_get_dynamic_table(ngx_connection_t *c) 424 ngx_http_v3_lookup_static(ngx_connection_t *c, ngx_uint_t index,
325 { 425 ngx_str_t *name, ngx_str_t *value)
326 ngx_connection_t *pc; 426 {
327 ngx_http_v3_connection_t *h3c; 427 ngx_uint_t nelts;
428 ngx_http_v3_header_t *h;
429
430 nelts = sizeof(ngx_http_v3_static_table)
431 / sizeof(ngx_http_v3_static_table[0]);
432
433 if (index >= nelts) {
434 ngx_log_debug2(NGX_LOG_DEBUG_HTTP, c->log, 0,
435 "http3 static[%ui] lookup out of bounds: %ui",
436 index, nelts);
437 return NGX_ERROR;
438 }
439
440 h = &ngx_http_v3_static_table[index];
441
442 ngx_log_debug3(NGX_LOG_DEBUG_HTTP, c->log, 0,
443 "http3 static[%ui] lookup \"%V\":\"%V\"",
444 index, &h->name, &h->value);
445
446 if (name) {
447 *name = h->name;
448 }
449
450 if (value) {
451 *value = h->value;
452 }
453
454 return NGX_OK;
455 }
456
457
458 ngx_int_t
459 ngx_http_v3_lookup(ngx_connection_t *c, ngx_uint_t index, ngx_str_t *name,
460 ngx_str_t *value)
461 {
462 ngx_http_v3_header_t *h;
463 ngx_http_v3_connection_t *h3c;
464 ngx_http_v3_dynamic_table_t *dt;
465
466 h3c = c->qs->parent->data;
467 dt = &h3c->table;
468
469 if (index < dt->base || index - dt->base >= dt->nelts) {
470 ngx_log_debug3(NGX_LOG_DEBUG_HTTP, c->log, 0,
471 "http3 dynamic[%ui] lookup out of bounds: [%ui,%ui]",
472 index, dt->base, dt->base + dt->nelts);
473 return NGX_ERROR;
474 }
475
476 h = dt->elts[index - dt->base];
477
478 ngx_log_debug3(NGX_LOG_DEBUG_HTTP, c->log, 0,
479 "http3 dynamic[%ui] lookup \"%V\":\"%V\"",
480 index, &h->name, &h->value);
481
482 if (name) {
483 *name = h->name;
484 }
485
486 if (value) {
487 *value = h->value;
488 }
489
490 return NGX_OK;
491 }
492
493
494 ngx_int_t
495 ngx_http_v3_decode_insert_count(ngx_connection_t *c, ngx_uint_t *insert_count)
496 {
497 ngx_uint_t max_entries, full_range, max_value,
498 max_wrapped, req_insert_count;
499 ngx_http_v3_srv_conf_t *v3cf;
500 ngx_http_v3_connection_t *h3c;
501 ngx_http_v3_dynamic_table_t *dt;
502
503 /* QPACK 4.5.1.1. Required Insert Count */
504
505 if (*insert_count == 0) {
506 return NGX_OK;
507 }
508
509 h3c = c->qs->parent->data;
510 dt = &h3c->table;
511
512 v3cf = ngx_http_get_module_srv_conf(h3c->hc.conf_ctx, ngx_http_v3_module);
513
514 max_entries = v3cf->max_table_capacity / 32;
515 full_range = 2 * max_entries;
516
517 if (*insert_count > full_range) {
518 return NGX_ERROR;
519 }
520
521 max_value = dt->base + dt->nelts + max_entries;
522 max_wrapped = (max_value / full_range) * full_range;
523 req_insert_count = max_wrapped + *insert_count - 1;
524
525 if (req_insert_count > max_value) {
526 if (req_insert_count <= full_range) {
527 return NGX_ERROR;
528 }
529
530 req_insert_count -= full_range;
531 }
532
533 if (req_insert_count == 0) {
534 return NGX_ERROR;
535 }
536
537 ngx_log_debug2(NGX_LOG_DEBUG_HTTP, c->log, 0,
538 "http3 decode insert_count %ui -> %ui",
539 *insert_count, req_insert_count);
540
541 *insert_count = req_insert_count;
542
543 return NGX_OK;
544 }
545
546
547 ngx_int_t
548 ngx_http_v3_check_insert_count(ngx_connection_t *c, ngx_uint_t insert_count)
549 {
550 size_t n;
551 ngx_connection_t *pc;
552 ngx_pool_cleanup_t *cln;
553 ngx_http_v3_block_t *block;
554 ngx_http_v3_srv_conf_t *v3cf;
555 ngx_http_v3_connection_t *h3c;
556 ngx_http_v3_dynamic_table_t *dt;
328 557
329 pc = c->qs->parent; 558 pc = c->qs->parent;
330 h3c = pc->data; 559 h3c = pc->data;
331 560 dt = &h3c->table;
332 if (h3c->dynamic) { 561
333 return h3c->dynamic; 562 n = dt->base + dt->nelts;
334 }
335
336 ngx_log_debug0(NGX_LOG_DEBUG_HTTP, c->log, 0, "http3 create dynamic table");
337
338 h3c->dynamic = ngx_array_create(pc->pool, 1, sizeof(ngx_http_v3_header_t));
339
340 return h3c->dynamic;
341 }
342
343
344 ngx_http_v3_header_t *
345 ngx_http_v3_lookup_table(ngx_connection_t *c, ngx_uint_t dynamic,
346 ngx_uint_t index)
347 {
348 ngx_uint_t nelts;
349 ngx_array_t *dt;
350 ngx_http_v3_header_t *table;
351
352 ngx_log_debug2(NGX_LOG_DEBUG_HTTP, c->log, 0, "http3 lookup %s[%ui]",
353 dynamic ? "dynamic" : "static", index);
354
355 if (dynamic) {
356 dt = ngx_http_v3_get_dynamic_table(c);
357 if (dt == NULL) {
358 return NULL;
359 }
360
361 table = dt->elts;
362 nelts = dt->nelts;
363
364 } else {
365 table = ngx_http_v3_static_table;
366 nelts = sizeof(ngx_http_v3_static_table)
367 / sizeof(ngx_http_v3_static_table[0]);
368 }
369
370 if (index >= nelts) {
371 ngx_log_debug1(NGX_LOG_DEBUG_HTTP, c->log, 0,
372 "http3 lookup out of bounds: %ui", nelts);
373 return NULL;
374 }
375
376 ngx_log_debug2(NGX_LOG_DEBUG_HTTP, c->log, 0, "http3 lookup \"%V\":\"%V\"",
377 &table[index].name, &table[index].value);
378
379 return &table[index];
380 }
381
382
383 ngx_int_t
384 ngx_http_v3_check_insert_count(ngx_connection_t *c, ngx_uint_t insert_count)
385 {
386 size_t n;
387 ngx_http_v3_connection_t *h3c;
388
389 h3c = c->qs->parent->data;
390 n = h3c->dynamic ? h3c->dynamic->nelts : 0;
391 563
392 ngx_log_debug2(NGX_LOG_DEBUG_HTTP, c->log, 0, 564 ngx_log_debug2(NGX_LOG_DEBUG_HTTP, c->log, 0,
393 "http3 check insert count %ui/%ui", insert_count, n); 565 "http3 check insert count req:%ui, have:%ui",
394 566 insert_count, n);
395 if (n < insert_count) { 567
396 /* XXX how to get notified? */ 568 if (n >= insert_count) {
397 /* XXX wake all streams on any arrival to the encoder stream? */ 569 return NGX_OK;
398 return NGX_AGAIN; 570 }
399 } 571
400 572 ngx_log_debug0(NGX_LOG_DEBUG_HTTP, c->log, 0, "http3 block stream");
401 return NGX_OK; 573
574 block = NULL;
575
576 for (cln = c->pool->cleanup; cln; cln = cln->next) {
577 if (cln->handler == ngx_http_v3_unblock) {
578 block = cln->data;
579 break;
580 }
581 }
582
583 if (block == NULL) {
584 cln = ngx_pool_cleanup_add(c->pool, sizeof(ngx_http_v3_block_t));
585 if (cln == NULL) {
586 return NGX_ERROR;
587 }
588
589 cln->handler = ngx_http_v3_unblock;
590
591 block = cln->data;
592 block->queue.prev = NULL;
593 block->connection = c;
594 block->nblocked = &h3c->nblocked;
595 }
596
597 if (block->queue.prev == NULL) {
598 v3cf = ngx_http_get_module_srv_conf(h3c->hc.conf_ctx,
599 ngx_http_v3_module);
600
601 if (h3c->nblocked == v3cf->max_blocked_streams) {
602 ngx_log_error(NGX_LOG_INFO, c->log, 0,
603 "client exceeded http3_max_blocked_streams limit");
604 return NGX_ERROR;
605 }
606
607 h3c->nblocked++;
608 ngx_queue_insert_tail(&h3c->blocked, &block->queue);
609 }
610
611 ngx_log_debug1(NGX_LOG_DEBUG_HTTP, c->log, 0,
612 "http3 blocked:%ui", h3c->nblocked);
613
614 return NGX_BUSY;
615 }
616
617
618 static void
619 ngx_http_v3_unblock(void *data)
620 {
621 ngx_http_v3_block_t *block = data;
622
623 if (block->queue.prev) {
624 ngx_queue_remove(&block->queue);
625 block->queue.prev = NULL;
626 (*block->nblocked)--;
627 }
402 } 628 }
403 629
404 630
405 static ngx_int_t 631 static ngx_int_t
406 ngx_http_v3_new_header(ngx_connection_t *c) 632 ngx_http_v3_new_header(ngx_connection_t *c)
407 { 633 {
408 ngx_log_debug0(NGX_LOG_DEBUG_HTTP, c->log, 0, "http3 new dynamic header"); 634 ngx_queue_t *q;
409 635 ngx_connection_t *bc;
410 /* XXX report all waiting streams of a new header */ 636 ngx_http_v3_block_t *block;
637 ngx_http_v3_connection_t *h3c;
638
639 h3c = c->qs->parent->data;
640
641 ngx_log_debug1(NGX_LOG_DEBUG_HTTP, c->log, 0,
642 "http3 new dynamic header, blocked:%ui", h3c->nblocked);
643
644 while (!ngx_queue_empty(&h3c->blocked)) {
645 q = ngx_queue_head(&h3c->blocked);
646 block = (ngx_http_v3_block_t *) q;
647 bc = block->connection;
648
649 ngx_log_debug0(NGX_LOG_DEBUG_HTTP, bc->log, 0, "http3 unblock stream");
650
651 ngx_http_v3_unblock(block);
652 ngx_post_event(bc->read, &ngx_posted_events);
653 }
411 654
412 return NGX_OK; 655 return NGX_OK;
413 } 656 }
414 657
415 658