1/* 2 * nghttp3 3 * 4 * Copyright (c) 2019 nghttp3 contributors 5 * Copyright (c) 2013 nghttp2 contributors 6 * 7 * Permission is hereby granted, free of charge, to any person obtaining 8 * a copy of this software and associated documentation files (the 9 * "Software"), to deal in the Software without restriction, including 10 * without limitation the rights to use, copy, modify, merge, publish, 11 * distribute, sublicense, and/or sell copies of the Software, and to 12 * permit persons to whom the Software is furnished to do so, subject to 13 * the following conditions: 14 * 15 * The above copyright notice and this permission notice shall be 16 * included in all copies or substantial portions of the Software. 17 * 18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 19 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 21 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 22 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 23 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 24 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 25 */ 26#include "nghttp3_qpack.h" 27 28#include <string.h> 29#include <assert.h> 30#include <stdio.h> 31 32#include "nghttp3_str.h" 33#include "nghttp3_macro.h" 34#include "nghttp3_debug.h" 35 36/* NGHTTP3_QPACK_MAX_QPACK_STREAMS is the maximum number of concurrent 37 nghttp3_qpack_stream object to handle a client which never cancel 38 or acknowledge header block. After this limit, encoder stops using 39 dynamic table. */ 40#define NGHTTP3_QPACK_MAX_QPACK_STREAMS 2000 41 42/* Make scalar initialization form of nghttp3_qpack_static_entry */ 43#define MAKE_STATIC_ENT(I, T, H) \ 44 { I, T, H } 45 46/* Generated by mkstatichdtbl.py */ 47static nghttp3_qpack_static_entry token_stable[] = { 48 MAKE_STATIC_ENT(0, NGHTTP3_QPACK_TOKEN__AUTHORITY, 3153725150u), 49 MAKE_STATIC_ENT(15, NGHTTP3_QPACK_TOKEN__METHOD, 695666056u), 50 MAKE_STATIC_ENT(16, NGHTTP3_QPACK_TOKEN__METHOD, 695666056u), 51 MAKE_STATIC_ENT(17, NGHTTP3_QPACK_TOKEN__METHOD, 695666056u), 52 MAKE_STATIC_ENT(18, NGHTTP3_QPACK_TOKEN__METHOD, 695666056u), 53 MAKE_STATIC_ENT(19, NGHTTP3_QPACK_TOKEN__METHOD, 695666056u), 54 MAKE_STATIC_ENT(20, NGHTTP3_QPACK_TOKEN__METHOD, 695666056u), 55 MAKE_STATIC_ENT(21, NGHTTP3_QPACK_TOKEN__METHOD, 695666056u), 56 MAKE_STATIC_ENT(1, NGHTTP3_QPACK_TOKEN__PATH, 3292848686u), 57 MAKE_STATIC_ENT(22, NGHTTP3_QPACK_TOKEN__SCHEME, 2510477674u), 58 MAKE_STATIC_ENT(23, NGHTTP3_QPACK_TOKEN__SCHEME, 2510477674u), 59 MAKE_STATIC_ENT(24, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u), 60 MAKE_STATIC_ENT(25, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u), 61 MAKE_STATIC_ENT(26, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u), 62 MAKE_STATIC_ENT(27, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u), 63 MAKE_STATIC_ENT(28, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u), 64 MAKE_STATIC_ENT(63, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u), 65 MAKE_STATIC_ENT(64, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u), 66 MAKE_STATIC_ENT(65, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u), 67 MAKE_STATIC_ENT(66, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u), 68 MAKE_STATIC_ENT(67, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u), 69 MAKE_STATIC_ENT(68, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u), 70 MAKE_STATIC_ENT(69, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u), 71 MAKE_STATIC_ENT(70, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u), 72 MAKE_STATIC_ENT(71, NGHTTP3_QPACK_TOKEN__STATUS, 4000288983u), 73 MAKE_STATIC_ENT(29, NGHTTP3_QPACK_TOKEN_ACCEPT, 136609321u), 74 MAKE_STATIC_ENT(30, NGHTTP3_QPACK_TOKEN_ACCEPT, 136609321u), 75 MAKE_STATIC_ENT(31, NGHTTP3_QPACK_TOKEN_ACCEPT_ENCODING, 3379649177u), 76 MAKE_STATIC_ENT(72, NGHTTP3_QPACK_TOKEN_ACCEPT_LANGUAGE, 1979086614u), 77 MAKE_STATIC_ENT(32, NGHTTP3_QPACK_TOKEN_ACCEPT_RANGES, 1713753958u), 78 MAKE_STATIC_ENT(73, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_CREDENTIALS, 79 901040780u), 80 MAKE_STATIC_ENT(74, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_CREDENTIALS, 81 901040780u), 82 MAKE_STATIC_ENT(33, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_HEADERS, 83 1524311232u), 84 MAKE_STATIC_ENT(34, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_HEADERS, 85 1524311232u), 86 MAKE_STATIC_ENT(75, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_HEADERS, 87 1524311232u), 88 MAKE_STATIC_ENT(76, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_METHODS, 89 2175229868u), 90 MAKE_STATIC_ENT(77, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_METHODS, 91 2175229868u), 92 MAKE_STATIC_ENT(78, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_METHODS, 93 2175229868u), 94 MAKE_STATIC_ENT(35, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_ORIGIN, 95 2710797292u), 96 MAKE_STATIC_ENT(79, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_EXPOSE_HEADERS, 97 2449824425u), 98 MAKE_STATIC_ENT(80, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_REQUEST_HEADERS, 99 3599549072u), 100 MAKE_STATIC_ENT(81, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_REQUEST_METHOD, 101 2417078055u), 102 MAKE_STATIC_ENT(82, NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_REQUEST_METHOD, 103 2417078055u), 104 MAKE_STATIC_ENT(2, NGHTTP3_QPACK_TOKEN_AGE, 742476188u), 105 MAKE_STATIC_ENT(83, NGHTTP3_QPACK_TOKEN_ALT_SVC, 2148877059u), 106 MAKE_STATIC_ENT(84, NGHTTP3_QPACK_TOKEN_AUTHORIZATION, 2436257726u), 107 MAKE_STATIC_ENT(36, NGHTTP3_QPACK_TOKEN_CACHE_CONTROL, 1355326669u), 108 MAKE_STATIC_ENT(37, NGHTTP3_QPACK_TOKEN_CACHE_CONTROL, 1355326669u), 109 MAKE_STATIC_ENT(38, NGHTTP3_QPACK_TOKEN_CACHE_CONTROL, 1355326669u), 110 MAKE_STATIC_ENT(39, NGHTTP3_QPACK_TOKEN_CACHE_CONTROL, 1355326669u), 111 MAKE_STATIC_ENT(40, NGHTTP3_QPACK_TOKEN_CACHE_CONTROL, 1355326669u), 112 MAKE_STATIC_ENT(41, NGHTTP3_QPACK_TOKEN_CACHE_CONTROL, 1355326669u), 113 MAKE_STATIC_ENT(3, NGHTTP3_QPACK_TOKEN_CONTENT_DISPOSITION, 3889184348u), 114 MAKE_STATIC_ENT(42, NGHTTP3_QPACK_TOKEN_CONTENT_ENCODING, 65203592u), 115 MAKE_STATIC_ENT(43, NGHTTP3_QPACK_TOKEN_CONTENT_ENCODING, 65203592u), 116 MAKE_STATIC_ENT(4, NGHTTP3_QPACK_TOKEN_CONTENT_LENGTH, 1308181789u), 117 MAKE_STATIC_ENT(85, NGHTTP3_QPACK_TOKEN_CONTENT_SECURITY_POLICY, 118 1569039836u), 119 MAKE_STATIC_ENT(44, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u), 120 MAKE_STATIC_ENT(45, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u), 121 MAKE_STATIC_ENT(46, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u), 122 MAKE_STATIC_ENT(47, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u), 123 MAKE_STATIC_ENT(48, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u), 124 MAKE_STATIC_ENT(49, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u), 125 MAKE_STATIC_ENT(50, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u), 126 MAKE_STATIC_ENT(51, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u), 127 MAKE_STATIC_ENT(52, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u), 128 MAKE_STATIC_ENT(53, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u), 129 MAKE_STATIC_ENT(54, NGHTTP3_QPACK_TOKEN_CONTENT_TYPE, 4244048277u), 130 MAKE_STATIC_ENT(5, NGHTTP3_QPACK_TOKEN_COOKIE, 2007449791u), 131 MAKE_STATIC_ENT(6, NGHTTP3_QPACK_TOKEN_DATE, 3564297305u), 132 MAKE_STATIC_ENT(86, NGHTTP3_QPACK_TOKEN_EARLY_DATA, 4080895051u), 133 MAKE_STATIC_ENT(7, NGHTTP3_QPACK_TOKEN_ETAG, 113792960u), 134 MAKE_STATIC_ENT(87, NGHTTP3_QPACK_TOKEN_EXPECT_CT, 1183214960u), 135 MAKE_STATIC_ENT(88, NGHTTP3_QPACK_TOKEN_FORWARDED, 1485178027u), 136 MAKE_STATIC_ENT(8, NGHTTP3_QPACK_TOKEN_IF_MODIFIED_SINCE, 2213050793u), 137 MAKE_STATIC_ENT(9, NGHTTP3_QPACK_TOKEN_IF_NONE_MATCH, 2536202615u), 138 MAKE_STATIC_ENT(89, NGHTTP3_QPACK_TOKEN_IF_RANGE, 2340978238u), 139 MAKE_STATIC_ENT(10, NGHTTP3_QPACK_TOKEN_LAST_MODIFIED, 3226950251u), 140 MAKE_STATIC_ENT(11, NGHTTP3_QPACK_TOKEN_LINK, 232457833u), 141 MAKE_STATIC_ENT(12, NGHTTP3_QPACK_TOKEN_LOCATION, 200649126u), 142 MAKE_STATIC_ENT(90, NGHTTP3_QPACK_TOKEN_ORIGIN, 3649018447u), 143 MAKE_STATIC_ENT(91, NGHTTP3_QPACK_TOKEN_PURPOSE, 4212263681u), 144 MAKE_STATIC_ENT(55, NGHTTP3_QPACK_TOKEN_RANGE, 4208725202u), 145 MAKE_STATIC_ENT(13, NGHTTP3_QPACK_TOKEN_REFERER, 3969579366u), 146 MAKE_STATIC_ENT(92, NGHTTP3_QPACK_TOKEN_SERVER, 1085029842u), 147 MAKE_STATIC_ENT(14, NGHTTP3_QPACK_TOKEN_SET_COOKIE, 1848371000u), 148 MAKE_STATIC_ENT(56, NGHTTP3_QPACK_TOKEN_STRICT_TRANSPORT_SECURITY, 149 4138147361u), 150 MAKE_STATIC_ENT(57, NGHTTP3_QPACK_TOKEN_STRICT_TRANSPORT_SECURITY, 151 4138147361u), 152 MAKE_STATIC_ENT(58, NGHTTP3_QPACK_TOKEN_STRICT_TRANSPORT_SECURITY, 153 4138147361u), 154 MAKE_STATIC_ENT(93, NGHTTP3_QPACK_TOKEN_TIMING_ALLOW_ORIGIN, 2432297564u), 155 MAKE_STATIC_ENT(94, NGHTTP3_QPACK_TOKEN_UPGRADE_INSECURE_REQUESTS, 156 2479169413u), 157 MAKE_STATIC_ENT(95, NGHTTP3_QPACK_TOKEN_USER_AGENT, 606444526u), 158 MAKE_STATIC_ENT(59, NGHTTP3_QPACK_TOKEN_VARY, 1085005381u), 159 MAKE_STATIC_ENT(60, NGHTTP3_QPACK_TOKEN_VARY, 1085005381u), 160 MAKE_STATIC_ENT(61, NGHTTP3_QPACK_TOKEN_X_CONTENT_TYPE_OPTIONS, 161 3644557769u), 162 MAKE_STATIC_ENT(96, NGHTTP3_QPACK_TOKEN_X_FORWARDED_FOR, 2914187656u), 163 MAKE_STATIC_ENT(97, NGHTTP3_QPACK_TOKEN_X_FRAME_OPTIONS, 3993834824u), 164 MAKE_STATIC_ENT(98, NGHTTP3_QPACK_TOKEN_X_FRAME_OPTIONS, 3993834824u), 165 MAKE_STATIC_ENT(62, NGHTTP3_QPACK_TOKEN_X_XSS_PROTECTION, 2501058888u), 166}; 167 168/* Make scalar initialization form of nghttp3_qpack_static_entry */ 169#define MAKE_STATIC_HD(N, V, T) \ 170 { \ 171 {NULL, (uint8_t *)(N), sizeof((N)) - 1, -1}, \ 172 {NULL, (uint8_t *)(V), sizeof((V)) - 1, -1}, T \ 173 } 174 175static nghttp3_qpack_static_header stable[] = { 176 MAKE_STATIC_HD(":authority", "", NGHTTP3_QPACK_TOKEN__AUTHORITY), 177 MAKE_STATIC_HD(":path", "/", NGHTTP3_QPACK_TOKEN__PATH), 178 MAKE_STATIC_HD("age", "0", NGHTTP3_QPACK_TOKEN_AGE), 179 MAKE_STATIC_HD("content-disposition", "", 180 NGHTTP3_QPACK_TOKEN_CONTENT_DISPOSITION), 181 MAKE_STATIC_HD("content-length", "0", NGHTTP3_QPACK_TOKEN_CONTENT_LENGTH), 182 MAKE_STATIC_HD("cookie", "", NGHTTP3_QPACK_TOKEN_COOKIE), 183 MAKE_STATIC_HD("date", "", NGHTTP3_QPACK_TOKEN_DATE), 184 MAKE_STATIC_HD("etag", "", NGHTTP3_QPACK_TOKEN_ETAG), 185 MAKE_STATIC_HD("if-modified-since", "", 186 NGHTTP3_QPACK_TOKEN_IF_MODIFIED_SINCE), 187 MAKE_STATIC_HD("if-none-match", "", NGHTTP3_QPACK_TOKEN_IF_NONE_MATCH), 188 MAKE_STATIC_HD("last-modified", "", NGHTTP3_QPACK_TOKEN_LAST_MODIFIED), 189 MAKE_STATIC_HD("link", "", NGHTTP3_QPACK_TOKEN_LINK), 190 MAKE_STATIC_HD("location", "", NGHTTP3_QPACK_TOKEN_LOCATION), 191 MAKE_STATIC_HD("referer", "", NGHTTP3_QPACK_TOKEN_REFERER), 192 MAKE_STATIC_HD("set-cookie", "", NGHTTP3_QPACK_TOKEN_SET_COOKIE), 193 MAKE_STATIC_HD(":method", "CONNECT", NGHTTP3_QPACK_TOKEN__METHOD), 194 MAKE_STATIC_HD(":method", "DELETE", NGHTTP3_QPACK_TOKEN__METHOD), 195 MAKE_STATIC_HD(":method", "GET", NGHTTP3_QPACK_TOKEN__METHOD), 196 MAKE_STATIC_HD(":method", "HEAD", NGHTTP3_QPACK_TOKEN__METHOD), 197 MAKE_STATIC_HD(":method", "OPTIONS", NGHTTP3_QPACK_TOKEN__METHOD), 198 MAKE_STATIC_HD(":method", "POST", NGHTTP3_QPACK_TOKEN__METHOD), 199 MAKE_STATIC_HD(":method", "PUT", NGHTTP3_QPACK_TOKEN__METHOD), 200 MAKE_STATIC_HD(":scheme", "http", NGHTTP3_QPACK_TOKEN__SCHEME), 201 MAKE_STATIC_HD(":scheme", "https", NGHTTP3_QPACK_TOKEN__SCHEME), 202 MAKE_STATIC_HD(":status", "103", NGHTTP3_QPACK_TOKEN__STATUS), 203 MAKE_STATIC_HD(":status", "200", NGHTTP3_QPACK_TOKEN__STATUS), 204 MAKE_STATIC_HD(":status", "304", NGHTTP3_QPACK_TOKEN__STATUS), 205 MAKE_STATIC_HD(":status", "404", NGHTTP3_QPACK_TOKEN__STATUS), 206 MAKE_STATIC_HD(":status", "503", NGHTTP3_QPACK_TOKEN__STATUS), 207 MAKE_STATIC_HD("accept", "*/*", NGHTTP3_QPACK_TOKEN_ACCEPT), 208 MAKE_STATIC_HD("accept", "application/dns-message", 209 NGHTTP3_QPACK_TOKEN_ACCEPT), 210 MAKE_STATIC_HD("accept-encoding", "gzip, deflate, br", 211 NGHTTP3_QPACK_TOKEN_ACCEPT_ENCODING), 212 MAKE_STATIC_HD("accept-ranges", "bytes", NGHTTP3_QPACK_TOKEN_ACCEPT_RANGES), 213 MAKE_STATIC_HD("access-control-allow-headers", "cache-control", 214 NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_HEADERS), 215 MAKE_STATIC_HD("access-control-allow-headers", "content-type", 216 NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_HEADERS), 217 MAKE_STATIC_HD("access-control-allow-origin", "*", 218 NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_ORIGIN), 219 MAKE_STATIC_HD("cache-control", "max-age=0", 220 NGHTTP3_QPACK_TOKEN_CACHE_CONTROL), 221 MAKE_STATIC_HD("cache-control", "max-age=2592000", 222 NGHTTP3_QPACK_TOKEN_CACHE_CONTROL), 223 MAKE_STATIC_HD("cache-control", "max-age=604800", 224 NGHTTP3_QPACK_TOKEN_CACHE_CONTROL), 225 MAKE_STATIC_HD("cache-control", "no-cache", 226 NGHTTP3_QPACK_TOKEN_CACHE_CONTROL), 227 MAKE_STATIC_HD("cache-control", "no-store", 228 NGHTTP3_QPACK_TOKEN_CACHE_CONTROL), 229 MAKE_STATIC_HD("cache-control", "public, max-age=31536000", 230 NGHTTP3_QPACK_TOKEN_CACHE_CONTROL), 231 MAKE_STATIC_HD("content-encoding", "br", 232 NGHTTP3_QPACK_TOKEN_CONTENT_ENCODING), 233 MAKE_STATIC_HD("content-encoding", "gzip", 234 NGHTTP3_QPACK_TOKEN_CONTENT_ENCODING), 235 MAKE_STATIC_HD("content-type", "application/dns-message", 236 NGHTTP3_QPACK_TOKEN_CONTENT_TYPE), 237 MAKE_STATIC_HD("content-type", "application/javascript", 238 NGHTTP3_QPACK_TOKEN_CONTENT_TYPE), 239 MAKE_STATIC_HD("content-type", "application/json", 240 NGHTTP3_QPACK_TOKEN_CONTENT_TYPE), 241 MAKE_STATIC_HD("content-type", "application/x-www-form-urlencoded", 242 NGHTTP3_QPACK_TOKEN_CONTENT_TYPE), 243 MAKE_STATIC_HD("content-type", "image/gif", 244 NGHTTP3_QPACK_TOKEN_CONTENT_TYPE), 245 MAKE_STATIC_HD("content-type", "image/jpeg", 246 NGHTTP3_QPACK_TOKEN_CONTENT_TYPE), 247 MAKE_STATIC_HD("content-type", "image/png", 248 NGHTTP3_QPACK_TOKEN_CONTENT_TYPE), 249 MAKE_STATIC_HD("content-type", "text/css", 250 NGHTTP3_QPACK_TOKEN_CONTENT_TYPE), 251 MAKE_STATIC_HD("content-type", "text/html; charset=utf-8", 252 NGHTTP3_QPACK_TOKEN_CONTENT_TYPE), 253 MAKE_STATIC_HD("content-type", "text/plain", 254 NGHTTP3_QPACK_TOKEN_CONTENT_TYPE), 255 MAKE_STATIC_HD("content-type", "text/plain;charset=utf-8", 256 NGHTTP3_QPACK_TOKEN_CONTENT_TYPE), 257 MAKE_STATIC_HD("range", "bytes=0-", NGHTTP3_QPACK_TOKEN_RANGE), 258 MAKE_STATIC_HD("strict-transport-security", "max-age=31536000", 259 NGHTTP3_QPACK_TOKEN_STRICT_TRANSPORT_SECURITY), 260 MAKE_STATIC_HD("strict-transport-security", 261 "max-age=31536000; includesubdomains", 262 NGHTTP3_QPACK_TOKEN_STRICT_TRANSPORT_SECURITY), 263 MAKE_STATIC_HD("strict-transport-security", 264 "max-age=31536000; includesubdomains; preload", 265 NGHTTP3_QPACK_TOKEN_STRICT_TRANSPORT_SECURITY), 266 MAKE_STATIC_HD("vary", "accept-encoding", NGHTTP3_QPACK_TOKEN_VARY), 267 MAKE_STATIC_HD("vary", "origin", NGHTTP3_QPACK_TOKEN_VARY), 268 MAKE_STATIC_HD("x-content-type-options", "nosniff", 269 NGHTTP3_QPACK_TOKEN_X_CONTENT_TYPE_OPTIONS), 270 MAKE_STATIC_HD("x-xss-protection", "1; mode=block", 271 NGHTTP3_QPACK_TOKEN_X_XSS_PROTECTION), 272 MAKE_STATIC_HD(":status", "100", NGHTTP3_QPACK_TOKEN__STATUS), 273 MAKE_STATIC_HD(":status", "204", NGHTTP3_QPACK_TOKEN__STATUS), 274 MAKE_STATIC_HD(":status", "206", NGHTTP3_QPACK_TOKEN__STATUS), 275 MAKE_STATIC_HD(":status", "302", NGHTTP3_QPACK_TOKEN__STATUS), 276 MAKE_STATIC_HD(":status", "400", NGHTTP3_QPACK_TOKEN__STATUS), 277 MAKE_STATIC_HD(":status", "403", NGHTTP3_QPACK_TOKEN__STATUS), 278 MAKE_STATIC_HD(":status", "421", NGHTTP3_QPACK_TOKEN__STATUS), 279 MAKE_STATIC_HD(":status", "425", NGHTTP3_QPACK_TOKEN__STATUS), 280 MAKE_STATIC_HD(":status", "500", NGHTTP3_QPACK_TOKEN__STATUS), 281 MAKE_STATIC_HD("accept-language", "", NGHTTP3_QPACK_TOKEN_ACCEPT_LANGUAGE), 282 MAKE_STATIC_HD("access-control-allow-credentials", "FALSE", 283 NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_CREDENTIALS), 284 MAKE_STATIC_HD("access-control-allow-credentials", "TRUE", 285 NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_CREDENTIALS), 286 MAKE_STATIC_HD("access-control-allow-headers", "*", 287 NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_HEADERS), 288 MAKE_STATIC_HD("access-control-allow-methods", "get", 289 NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_METHODS), 290 MAKE_STATIC_HD("access-control-allow-methods", "get, post, options", 291 NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_METHODS), 292 MAKE_STATIC_HD("access-control-allow-methods", "options", 293 NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_METHODS), 294 MAKE_STATIC_HD("access-control-expose-headers", "content-length", 295 NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_EXPOSE_HEADERS), 296 MAKE_STATIC_HD("access-control-request-headers", "content-type", 297 NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_REQUEST_HEADERS), 298 MAKE_STATIC_HD("access-control-request-method", "get", 299 NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_REQUEST_METHOD), 300 MAKE_STATIC_HD("access-control-request-method", "post", 301 NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_REQUEST_METHOD), 302 MAKE_STATIC_HD("alt-svc", "clear", NGHTTP3_QPACK_TOKEN_ALT_SVC), 303 MAKE_STATIC_HD("authorization", "", NGHTTP3_QPACK_TOKEN_AUTHORIZATION), 304 MAKE_STATIC_HD("content-security-policy", 305 "script-src 'none'; object-src 'none'; base-uri 'none'", 306 NGHTTP3_QPACK_TOKEN_CONTENT_SECURITY_POLICY), 307 MAKE_STATIC_HD("early-data", "1", NGHTTP3_QPACK_TOKEN_EARLY_DATA), 308 MAKE_STATIC_HD("expect-ct", "", NGHTTP3_QPACK_TOKEN_EXPECT_CT), 309 MAKE_STATIC_HD("forwarded", "", NGHTTP3_QPACK_TOKEN_FORWARDED), 310 MAKE_STATIC_HD("if-range", "", NGHTTP3_QPACK_TOKEN_IF_RANGE), 311 MAKE_STATIC_HD("origin", "", NGHTTP3_QPACK_TOKEN_ORIGIN), 312 MAKE_STATIC_HD("purpose", "prefetch", NGHTTP3_QPACK_TOKEN_PURPOSE), 313 MAKE_STATIC_HD("server", "", NGHTTP3_QPACK_TOKEN_SERVER), 314 MAKE_STATIC_HD("timing-allow-origin", "*", 315 NGHTTP3_QPACK_TOKEN_TIMING_ALLOW_ORIGIN), 316 MAKE_STATIC_HD("upgrade-insecure-requests", "1", 317 NGHTTP3_QPACK_TOKEN_UPGRADE_INSECURE_REQUESTS), 318 MAKE_STATIC_HD("user-agent", "", NGHTTP3_QPACK_TOKEN_USER_AGENT), 319 MAKE_STATIC_HD("x-forwarded-for", "", NGHTTP3_QPACK_TOKEN_X_FORWARDED_FOR), 320 MAKE_STATIC_HD("x-frame-options", "deny", 321 NGHTTP3_QPACK_TOKEN_X_FRAME_OPTIONS), 322 MAKE_STATIC_HD("x-frame-options", "sameorigin", 323 NGHTTP3_QPACK_TOKEN_X_FRAME_OPTIONS), 324}; 325 326static int memeq(const void *s1, const void *s2, size_t n) { 327 return n == 0 || memcmp(s1, s2, n) == 0; 328} 329 330/* Generated by genlibtokenlookup.py */ 331static int32_t qpack_lookup_token(const uint8_t *name, size_t namelen) { 332 switch (namelen) { 333 case 2: 334 switch (name[1]) { 335 case 'e': 336 if (memeq("t", name, 1)) { 337 return NGHTTP3_QPACK_TOKEN_TE; 338 } 339 break; 340 } 341 break; 342 case 3: 343 switch (name[2]) { 344 case 'e': 345 if (memeq("ag", name, 2)) { 346 return NGHTTP3_QPACK_TOKEN_AGE; 347 } 348 break; 349 } 350 break; 351 case 4: 352 switch (name[3]) { 353 case 'e': 354 if (memeq("dat", name, 3)) { 355 return NGHTTP3_QPACK_TOKEN_DATE; 356 } 357 break; 358 case 'g': 359 if (memeq("eta", name, 3)) { 360 return NGHTTP3_QPACK_TOKEN_ETAG; 361 } 362 break; 363 case 'k': 364 if (memeq("lin", name, 3)) { 365 return NGHTTP3_QPACK_TOKEN_LINK; 366 } 367 break; 368 case 't': 369 if (memeq("hos", name, 3)) { 370 return NGHTTP3_QPACK_TOKEN_HOST; 371 } 372 break; 373 case 'y': 374 if (memeq("var", name, 3)) { 375 return NGHTTP3_QPACK_TOKEN_VARY; 376 } 377 break; 378 } 379 break; 380 case 5: 381 switch (name[4]) { 382 case 'e': 383 if (memeq("rang", name, 4)) { 384 return NGHTTP3_QPACK_TOKEN_RANGE; 385 } 386 break; 387 case 'h': 388 if (memeq(":pat", name, 4)) { 389 return NGHTTP3_QPACK_TOKEN__PATH; 390 } 391 break; 392 } 393 break; 394 case 6: 395 switch (name[5]) { 396 case 'e': 397 if (memeq("cooki", name, 5)) { 398 return NGHTTP3_QPACK_TOKEN_COOKIE; 399 } 400 break; 401 case 'n': 402 if (memeq("origi", name, 5)) { 403 return NGHTTP3_QPACK_TOKEN_ORIGIN; 404 } 405 break; 406 case 'r': 407 if (memeq("serve", name, 5)) { 408 return NGHTTP3_QPACK_TOKEN_SERVER; 409 } 410 break; 411 case 't': 412 if (memeq("accep", name, 5)) { 413 return NGHTTP3_QPACK_TOKEN_ACCEPT; 414 } 415 break; 416 } 417 break; 418 case 7: 419 switch (name[6]) { 420 case 'c': 421 if (memeq("alt-sv", name, 6)) { 422 return NGHTTP3_QPACK_TOKEN_ALT_SVC; 423 } 424 break; 425 case 'd': 426 if (memeq(":metho", name, 6)) { 427 return NGHTTP3_QPACK_TOKEN__METHOD; 428 } 429 break; 430 case 'e': 431 if (memeq(":schem", name, 6)) { 432 return NGHTTP3_QPACK_TOKEN__SCHEME; 433 } 434 if (memeq("purpos", name, 6)) { 435 return NGHTTP3_QPACK_TOKEN_PURPOSE; 436 } 437 if (memeq("upgrad", name, 6)) { 438 return NGHTTP3_QPACK_TOKEN_UPGRADE; 439 } 440 break; 441 case 'r': 442 if (memeq("refere", name, 6)) { 443 return NGHTTP3_QPACK_TOKEN_REFERER; 444 } 445 break; 446 case 's': 447 if (memeq(":statu", name, 6)) { 448 return NGHTTP3_QPACK_TOKEN__STATUS; 449 } 450 break; 451 } 452 break; 453 case 8: 454 switch (name[7]) { 455 case 'e': 456 if (memeq("if-rang", name, 7)) { 457 return NGHTTP3_QPACK_TOKEN_IF_RANGE; 458 } 459 break; 460 case 'n': 461 if (memeq("locatio", name, 7)) { 462 return NGHTTP3_QPACK_TOKEN_LOCATION; 463 } 464 break; 465 case 'y': 466 if (memeq("priorit", name, 7)) { 467 return NGHTTP3_QPACK_TOKEN_PRIORITY; 468 } 469 break; 470 } 471 break; 472 case 9: 473 switch (name[8]) { 474 case 'd': 475 if (memeq("forwarde", name, 8)) { 476 return NGHTTP3_QPACK_TOKEN_FORWARDED; 477 } 478 break; 479 case 'l': 480 if (memeq(":protoco", name, 8)) { 481 return NGHTTP3_QPACK_TOKEN__PROTOCOL; 482 } 483 break; 484 case 't': 485 if (memeq("expect-c", name, 8)) { 486 return NGHTTP3_QPACK_TOKEN_EXPECT_CT; 487 } 488 break; 489 } 490 break; 491 case 10: 492 switch (name[9]) { 493 case 'a': 494 if (memeq("early-dat", name, 9)) { 495 return NGHTTP3_QPACK_TOKEN_EARLY_DATA; 496 } 497 break; 498 case 'e': 499 if (memeq("keep-aliv", name, 9)) { 500 return NGHTTP3_QPACK_TOKEN_KEEP_ALIVE; 501 } 502 if (memeq("set-cooki", name, 9)) { 503 return NGHTTP3_QPACK_TOKEN_SET_COOKIE; 504 } 505 break; 506 case 'n': 507 if (memeq("connectio", name, 9)) { 508 return NGHTTP3_QPACK_TOKEN_CONNECTION; 509 } 510 break; 511 case 't': 512 if (memeq("user-agen", name, 9)) { 513 return NGHTTP3_QPACK_TOKEN_USER_AGENT; 514 } 515 break; 516 case 'y': 517 if (memeq(":authorit", name, 9)) { 518 return NGHTTP3_QPACK_TOKEN__AUTHORITY; 519 } 520 break; 521 } 522 break; 523 case 12: 524 switch (name[11]) { 525 case 'e': 526 if (memeq("content-typ", name, 11)) { 527 return NGHTTP3_QPACK_TOKEN_CONTENT_TYPE; 528 } 529 break; 530 } 531 break; 532 case 13: 533 switch (name[12]) { 534 case 'd': 535 if (memeq("last-modifie", name, 12)) { 536 return NGHTTP3_QPACK_TOKEN_LAST_MODIFIED; 537 } 538 break; 539 case 'h': 540 if (memeq("if-none-matc", name, 12)) { 541 return NGHTTP3_QPACK_TOKEN_IF_NONE_MATCH; 542 } 543 break; 544 case 'l': 545 if (memeq("cache-contro", name, 12)) { 546 return NGHTTP3_QPACK_TOKEN_CACHE_CONTROL; 547 } 548 break; 549 case 'n': 550 if (memeq("authorizatio", name, 12)) { 551 return NGHTTP3_QPACK_TOKEN_AUTHORIZATION; 552 } 553 break; 554 case 's': 555 if (memeq("accept-range", name, 12)) { 556 return NGHTTP3_QPACK_TOKEN_ACCEPT_RANGES; 557 } 558 break; 559 } 560 break; 561 case 14: 562 switch (name[13]) { 563 case 'h': 564 if (memeq("content-lengt", name, 13)) { 565 return NGHTTP3_QPACK_TOKEN_CONTENT_LENGTH; 566 } 567 break; 568 } 569 break; 570 case 15: 571 switch (name[14]) { 572 case 'e': 573 if (memeq("accept-languag", name, 14)) { 574 return NGHTTP3_QPACK_TOKEN_ACCEPT_LANGUAGE; 575 } 576 break; 577 case 'g': 578 if (memeq("accept-encodin", name, 14)) { 579 return NGHTTP3_QPACK_TOKEN_ACCEPT_ENCODING; 580 } 581 break; 582 case 'r': 583 if (memeq("x-forwarded-fo", name, 14)) { 584 return NGHTTP3_QPACK_TOKEN_X_FORWARDED_FOR; 585 } 586 break; 587 case 's': 588 if (memeq("x-frame-option", name, 14)) { 589 return NGHTTP3_QPACK_TOKEN_X_FRAME_OPTIONS; 590 } 591 break; 592 } 593 break; 594 case 16: 595 switch (name[15]) { 596 case 'g': 597 if (memeq("content-encodin", name, 15)) { 598 return NGHTTP3_QPACK_TOKEN_CONTENT_ENCODING; 599 } 600 break; 601 case 'n': 602 if (memeq("proxy-connectio", name, 15)) { 603 return NGHTTP3_QPACK_TOKEN_PROXY_CONNECTION; 604 } 605 if (memeq("x-xss-protectio", name, 15)) { 606 return NGHTTP3_QPACK_TOKEN_X_XSS_PROTECTION; 607 } 608 break; 609 } 610 break; 611 case 17: 612 switch (name[16]) { 613 case 'e': 614 if (memeq("if-modified-sinc", name, 16)) { 615 return NGHTTP3_QPACK_TOKEN_IF_MODIFIED_SINCE; 616 } 617 break; 618 case 'g': 619 if (memeq("transfer-encodin", name, 16)) { 620 return NGHTTP3_QPACK_TOKEN_TRANSFER_ENCODING; 621 } 622 break; 623 } 624 break; 625 case 19: 626 switch (name[18]) { 627 case 'n': 628 if (memeq("content-dispositio", name, 18)) { 629 return NGHTTP3_QPACK_TOKEN_CONTENT_DISPOSITION; 630 } 631 if (memeq("timing-allow-origi", name, 18)) { 632 return NGHTTP3_QPACK_TOKEN_TIMING_ALLOW_ORIGIN; 633 } 634 break; 635 } 636 break; 637 case 22: 638 switch (name[21]) { 639 case 's': 640 if (memeq("x-content-type-option", name, 21)) { 641 return NGHTTP3_QPACK_TOKEN_X_CONTENT_TYPE_OPTIONS; 642 } 643 break; 644 } 645 break; 646 case 23: 647 switch (name[22]) { 648 case 'y': 649 if (memeq("content-security-polic", name, 22)) { 650 return NGHTTP3_QPACK_TOKEN_CONTENT_SECURITY_POLICY; 651 } 652 break; 653 } 654 break; 655 case 25: 656 switch (name[24]) { 657 case 's': 658 if (memeq("upgrade-insecure-request", name, 24)) { 659 return NGHTTP3_QPACK_TOKEN_UPGRADE_INSECURE_REQUESTS; 660 } 661 break; 662 case 'y': 663 if (memeq("strict-transport-securit", name, 24)) { 664 return NGHTTP3_QPACK_TOKEN_STRICT_TRANSPORT_SECURITY; 665 } 666 break; 667 } 668 break; 669 case 27: 670 switch (name[26]) { 671 case 'n': 672 if (memeq("access-control-allow-origi", name, 26)) { 673 return NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_ORIGIN; 674 } 675 break; 676 } 677 break; 678 case 28: 679 switch (name[27]) { 680 case 's': 681 if (memeq("access-control-allow-header", name, 27)) { 682 return NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_HEADERS; 683 } 684 if (memeq("access-control-allow-method", name, 27)) { 685 return NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_METHODS; 686 } 687 break; 688 } 689 break; 690 case 29: 691 switch (name[28]) { 692 case 'd': 693 if (memeq("access-control-request-metho", name, 28)) { 694 return NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_REQUEST_METHOD; 695 } 696 break; 697 case 's': 698 if (memeq("access-control-expose-header", name, 28)) { 699 return NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_EXPOSE_HEADERS; 700 } 701 break; 702 } 703 break; 704 case 30: 705 switch (name[29]) { 706 case 's': 707 if (memeq("access-control-request-header", name, 29)) { 708 return NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_REQUEST_HEADERS; 709 } 710 break; 711 } 712 break; 713 case 32: 714 switch (name[31]) { 715 case 's': 716 if (memeq("access-control-allow-credential", name, 31)) { 717 return NGHTTP3_QPACK_TOKEN_ACCESS_CONTROL_ALLOW_CREDENTIALS; 718 } 719 break; 720 } 721 break; 722 } 723 return -1; 724} 725 726static size_t table_space(size_t namelen, size_t valuelen) { 727 return NGHTTP3_QPACK_ENTRY_OVERHEAD + namelen + valuelen; 728} 729 730static int qpack_nv_name_eq(const nghttp3_qpack_nv *a, const nghttp3_nv *b) { 731 return a->name->len == b->namelen && 732 memeq(a->name->base, b->name, b->namelen); 733} 734 735static int qpack_nv_value_eq(const nghttp3_qpack_nv *a, const nghttp3_nv *b) { 736 return a->value->len == b->valuelen && 737 memeq(a->value->base, b->value, b->valuelen); 738} 739 740static void qpack_map_init(nghttp3_qpack_map *map) { 741 memset(map, 0, sizeof(nghttp3_qpack_map)); 742} 743 744static void qpack_map_insert(nghttp3_qpack_map *map, nghttp3_qpack_entry *ent) { 745 nghttp3_qpack_entry **bucket; 746 747 bucket = &map->table[ent->hash & (NGHTTP3_QPACK_MAP_SIZE - 1)]; 748 749 if (*bucket == NULL) { 750 *bucket = ent; 751 return; 752 } 753 754 /* larger absidx is linked near the root */ 755 ent->map_next = *bucket; 756 *bucket = ent; 757} 758 759static void qpack_map_remove(nghttp3_qpack_map *map, nghttp3_qpack_entry *ent) { 760 nghttp3_qpack_entry **dst; 761 762 dst = &map->table[ent->hash & (NGHTTP3_QPACK_MAP_SIZE - 1)]; 763 764 for (; *dst; dst = &(*dst)->map_next) { 765 if (*dst != ent) { 766 continue; 767 } 768 769 *dst = ent->map_next; 770 ent->map_next = NULL; 771 return; 772 } 773} 774 775/* 776 * qpack_context_can_reference returns nonzero if dynamic table entry 777 * at |absidx| can be referenced. In other words, it is within 778 * ctx->max_dtable_capacity. 779 */ 780static int qpack_context_can_reference(nghttp3_qpack_context *ctx, 781 uint64_t absidx) { 782 nghttp3_qpack_entry *ent = nghttp3_qpack_context_dtable_get(ctx, absidx); 783 return ctx->dtable_sum - ent->sum <= ctx->max_dtable_capacity; 784} 785 786/* |*ppb_match| (post-base match), if it is not NULL, is always exact 787 match. */ 788static void encoder_qpack_map_find(nghttp3_qpack_encoder *encoder, 789 int *exact_match, 790 nghttp3_qpack_entry **pmatch, 791 nghttp3_qpack_entry **ppb_match, 792 const nghttp3_nv *nv, int32_t token, 793 uint32_t hash, uint64_t krcnt, 794 int allow_blocking, int name_only) { 795 nghttp3_qpack_entry *p; 796 797 *exact_match = 0; 798 *pmatch = NULL; 799 *ppb_match = NULL; 800 801 for (p = encoder->dtable_map.table[hash & (NGHTTP3_QPACK_MAP_SIZE - 1)]; p; 802 p = p->map_next) { 803 if (token != p->nv.token || 804 (token == -1 && (hash != p->hash || !qpack_nv_name_eq(&p->nv, nv))) || 805 !qpack_context_can_reference(&encoder->ctx, p->absidx)) { 806 continue; 807 } 808 if (allow_blocking || p->absidx + 1 <= krcnt) { 809 if (!*pmatch) { 810 *pmatch = p; 811 if (name_only) { 812 return; 813 } 814 } 815 if (qpack_nv_value_eq(&p->nv, nv)) { 816 *pmatch = p; 817 *exact_match = 1; 818 return; 819 } 820 } else if (!*ppb_match && qpack_nv_value_eq(&p->nv, nv)) { 821 *ppb_match = p; 822 } 823 } 824} 825 826/* 827 * qpack_context_init initializes |ctx|. |hard_max_dtable_capacity| 828 * is the upper bound of the dynamic table capacity. |mem| is a 829 * memory allocator. 830 * 831 * The maximum dynamic table size is governed by 832 * ctx->max_dtable_capacity and it is initialized to 0. 833 * |hard_max_dtable_capacity| is the upper bound of 834 * ctx->max_dtable_capacity. 835 * 836 * This function returns 0 if it succeeds, or one of the following 837 * negative error codes: 838 * 839 * NGHTTP3_ERR_NOMEM 840 * Out of memory. 841 */ 842static int qpack_context_init(nghttp3_qpack_context *ctx, 843 size_t hard_max_dtable_capacity, 844 size_t max_blocked_streams, 845 const nghttp3_mem *mem) { 846 int rv; 847 size_t len = 4096 / NGHTTP3_QPACK_ENTRY_OVERHEAD; 848 size_t len2; 849 850 for (len2 = 1; len2 < len; len2 <<= 1) 851 ; 852 853 rv = nghttp3_ringbuf_init(&ctx->dtable, len2, sizeof(nghttp3_qpack_entry *), 854 mem); 855 if (rv != 0) { 856 return rv; 857 } 858 859 ctx->mem = mem; 860 ctx->dtable_size = 0; 861 ctx->dtable_sum = 0; 862 ctx->hard_max_dtable_capacity = hard_max_dtable_capacity; 863 ctx->max_dtable_capacity = 0; 864 ctx->max_blocked_streams = max_blocked_streams; 865 ctx->next_absidx = 0; 866 ctx->bad = 0; 867 868 return 0; 869} 870 871static void qpack_context_free(nghttp3_qpack_context *ctx) { 872 nghttp3_qpack_entry *ent; 873 size_t i, len = nghttp3_ringbuf_len(&ctx->dtable); 874 875 for (i = 0; i < len; ++i) { 876 ent = *(nghttp3_qpack_entry **)nghttp3_ringbuf_get(&ctx->dtable, i); 877 nghttp3_qpack_entry_free(ent); 878 nghttp3_mem_free(ctx->mem, ent); 879 } 880 nghttp3_ringbuf_free(&ctx->dtable); 881} 882 883static int ref_min_cnt_less(const nghttp3_pq_entry *lhsx, 884 const nghttp3_pq_entry *rhsx) { 885 nghttp3_qpack_header_block_ref *lhs = 886 nghttp3_struct_of(lhsx, nghttp3_qpack_header_block_ref, min_cnts_pe); 887 nghttp3_qpack_header_block_ref *rhs = 888 nghttp3_struct_of(rhsx, nghttp3_qpack_header_block_ref, min_cnts_pe); 889 890 return lhs->min_cnt < rhs->min_cnt; 891} 892 893typedef struct nghttp3_blocked_streams_key { 894 uint64_t max_cnt; 895 uint64_t id; 896} nghttp3_blocked_streams_key; 897 898static int max_cnt_greater(const nghttp3_ksl_key *lhs, 899 const nghttp3_ksl_key *rhs) { 900 const nghttp3_blocked_streams_key *a = lhs; 901 const nghttp3_blocked_streams_key *b = rhs; 902 return a->max_cnt > b->max_cnt || (a->max_cnt == b->max_cnt && a->id < b->id); 903} 904 905int nghttp3_qpack_encoder_init(nghttp3_qpack_encoder *encoder, 906 size_t hard_max_dtable_capacity, 907 const nghttp3_mem *mem) { 908 int rv; 909 910 rv = qpack_context_init(&encoder->ctx, hard_max_dtable_capacity, 0, mem); 911 if (rv != 0) { 912 return rv; 913 } 914 915 nghttp3_map_init(&encoder->streams, mem); 916 917 nghttp3_ksl_init(&encoder->blocked_streams, max_cnt_greater, 918 sizeof(nghttp3_blocked_streams_key), mem); 919 920 qpack_map_init(&encoder->dtable_map); 921 nghttp3_pq_init(&encoder->min_cnts, ref_min_cnt_less, mem); 922 923 encoder->krcnt = 0; 924 encoder->state = NGHTTP3_QPACK_DS_STATE_OPCODE; 925 encoder->opcode = 0; 926 encoder->min_dtable_update = SIZE_MAX; 927 encoder->last_max_dtable_update = 0; 928 encoder->flags = NGHTTP3_QPACK_ENCODER_FLAG_NONE; 929 930 nghttp3_qpack_read_state_reset(&encoder->rstate); 931 932 return 0; 933} 934 935static int map_stream_free(void *data, void *ptr) { 936 const nghttp3_mem *mem = ptr; 937 nghttp3_qpack_stream *stream = data; 938 nghttp3_qpack_stream_del(stream, mem); 939 return 0; 940} 941 942void nghttp3_qpack_encoder_free(nghttp3_qpack_encoder *encoder) { 943 nghttp3_pq_free(&encoder->min_cnts); 944 nghttp3_ksl_free(&encoder->blocked_streams); 945 nghttp3_map_each_free(&encoder->streams, map_stream_free, 946 (void *)encoder->ctx.mem); 947 nghttp3_map_free(&encoder->streams); 948 qpack_context_free(&encoder->ctx); 949} 950 951void nghttp3_qpack_encoder_set_max_dtable_capacity( 952 nghttp3_qpack_encoder *encoder, size_t max_dtable_capacity) { 953 max_dtable_capacity = 954 nghttp3_min(max_dtable_capacity, encoder->ctx.hard_max_dtable_capacity); 955 956 if (encoder->ctx.max_dtable_capacity == max_dtable_capacity) { 957 return; 958 } 959 960 encoder->flags |= NGHTTP3_QPACK_ENCODER_FLAG_PENDING_SET_DTABLE_CAP; 961 962 if (encoder->min_dtable_update > max_dtable_capacity) { 963 encoder->min_dtable_update = max_dtable_capacity; 964 encoder->ctx.max_dtable_capacity = max_dtable_capacity; 965 } 966 encoder->last_max_dtable_update = max_dtable_capacity; 967} 968 969void nghttp3_qpack_encoder_set_max_blocked_streams( 970 nghttp3_qpack_encoder *encoder, size_t max_blocked_streams) { 971 encoder->ctx.max_blocked_streams = max_blocked_streams; 972} 973 974uint64_t nghttp3_qpack_encoder_get_min_cnt(nghttp3_qpack_encoder *encoder) { 975 assert(!nghttp3_pq_empty(&encoder->min_cnts)); 976 977 return nghttp3_struct_of(nghttp3_pq_top(&encoder->min_cnts), 978 nghttp3_qpack_header_block_ref, min_cnts_pe) 979 ->min_cnt; 980} 981 982void nghttp3_qpack_encoder_shrink_dtable(nghttp3_qpack_encoder *encoder) { 983 nghttp3_ringbuf *dtable = &encoder->ctx.dtable; 984 const nghttp3_mem *mem = encoder->ctx.mem; 985 uint64_t min_cnt = UINT64_MAX; 986 size_t len; 987 nghttp3_qpack_entry *ent; 988 989 if (encoder->ctx.dtable_size <= encoder->ctx.max_dtable_capacity) { 990 return; 991 } 992 993 if (!nghttp3_pq_empty(&encoder->min_cnts)) { 994 min_cnt = nghttp3_qpack_encoder_get_min_cnt(encoder); 995 } 996 997 for (; encoder->ctx.dtable_size > encoder->ctx.max_dtable_capacity;) { 998 len = nghttp3_ringbuf_len(dtable); 999 ent = *(nghttp3_qpack_entry **)nghttp3_ringbuf_get(dtable, len - 1); 1000 if (ent->absidx + 1 == min_cnt) { 1001 return; 1002 } 1003 1004 encoder->ctx.dtable_size -= 1005 table_space(ent->nv.name->len, ent->nv.value->len); 1006 1007 nghttp3_ringbuf_pop_back(dtable); 1008 qpack_map_remove(&encoder->dtable_map, ent); 1009 1010 nghttp3_qpack_entry_free(ent); 1011 nghttp3_mem_free(mem, ent); 1012 } 1013} 1014 1015/* 1016 * qpack_encoder_add_stream_ref adds another dynamic table reference 1017 * to a stream denoted by |stream_id|. |stream| must be NULL if no 1018 * stream object is not found for the given stream ID. |max_cnt| and 1019 * |min_cnt| is the maximum and minimum insert count it references 1020 * respectively. 1021 * 1022 * This function returns 0 if it succeeds, or one of the following 1023 * negative error codes: 1024 * 1025 * NGHTTP3_ERR_NOMEM 1026 * Out of memory. 1027 */ 1028static int qpack_encoder_add_stream_ref(nghttp3_qpack_encoder *encoder, 1029 int64_t stream_id, 1030 nghttp3_qpack_stream *stream, 1031 uint64_t max_cnt, uint64_t min_cnt) { 1032 nghttp3_qpack_header_block_ref *ref; 1033 const nghttp3_mem *mem = encoder->ctx.mem; 1034 uint64_t prev_max_cnt = 0; 1035 int rv; 1036 1037 if (stream == NULL) { 1038 rv = nghttp3_qpack_stream_new(&stream, stream_id, mem); 1039 if (rv != 0) { 1040 assert(rv == NGHTTP3_ERR_NOMEM); 1041 return rv; 1042 } 1043 rv = nghttp3_map_insert(&encoder->streams, 1044 (nghttp3_map_key_type)stream->stream_id, stream); 1045 if (rv != 0) { 1046 assert(rv == NGHTTP3_ERR_NOMEM); 1047 nghttp3_qpack_stream_del(stream, mem); 1048 return rv; 1049 } 1050 } else { 1051 prev_max_cnt = nghttp3_qpack_stream_get_max_cnt(stream); 1052 if (nghttp3_qpack_encoder_stream_is_blocked(encoder, stream) && 1053 max_cnt > prev_max_cnt) { 1054 nghttp3_qpack_encoder_unblock_stream(encoder, stream); 1055 } 1056 } 1057 1058 rv = nghttp3_qpack_header_block_ref_new(&ref, max_cnt, min_cnt, mem); 1059 if (rv != 0) { 1060 return rv; 1061 } 1062 1063 rv = nghttp3_qpack_stream_add_ref(stream, ref); 1064 if (rv != 0) { 1065 nghttp3_qpack_header_block_ref_del(ref, mem); 1066 return rv; 1067 } 1068 1069 if (max_cnt > prev_max_cnt && 1070 nghttp3_qpack_encoder_stream_is_blocked(encoder, stream)) { 1071 rv = nghttp3_qpack_encoder_block_stream(encoder, stream); 1072 if (rv != 0) { 1073 return rv; 1074 } 1075 } 1076 1077 return nghttp3_pq_push(&encoder->min_cnts, &ref->min_cnts_pe); 1078} 1079 1080static void qpack_encoder_remove_stream(nghttp3_qpack_encoder *encoder, 1081 nghttp3_qpack_stream *stream) { 1082 size_t i, len; 1083 nghttp3_qpack_header_block_ref *ref; 1084 1085 nghttp3_map_remove(&encoder->streams, 1086 (nghttp3_map_key_type)stream->stream_id); 1087 1088 len = nghttp3_ringbuf_len(&stream->refs); 1089 for (i = 0; i < len; ++i) { 1090 ref = *(nghttp3_qpack_header_block_ref **)nghttp3_ringbuf_get(&stream->refs, 1091 i); 1092 1093 assert(ref->min_cnts_pe.index != NGHTTP3_PQ_BAD_INDEX); 1094 1095 nghttp3_pq_remove(&encoder->min_cnts, &ref->min_cnts_pe); 1096 } 1097} 1098 1099/* 1100 * reserve_buf_internal ensures that |buf| contains at least 1101 * |extra_size| of free space. In other words, if this function 1102 * succeeds, nghttp2_buf_left(buf) >= extra_size holds. |min_size| is 1103 * the minimum size of buffer. The allocated buffer has at least 1104 * |min_size| bytes. 1105 * 1106 * This function returns 0 if it succeeds, or one of the following 1107 * negative error codes: 1108 * 1109 * NGHTTP3_ERR_NOMEM 1110 * Out of memory. 1111 */ 1112static int reserve_buf_internal(nghttp3_buf *buf, size_t extra_size, 1113 size_t min_size, const nghttp3_mem *mem) { 1114 size_t left = nghttp3_buf_left(buf); 1115 size_t n = min_size, need; 1116 1117 if (left >= extra_size) { 1118 return 0; 1119 } 1120 1121 need = nghttp3_buf_cap(buf) + extra_size - left; 1122 1123 for (; n < need; n *= 2) 1124 ; 1125 1126 return nghttp3_buf_reserve(buf, n, mem); 1127} 1128 1129static int reserve_buf_small(nghttp3_buf *buf, size_t extra_size, 1130 const nghttp3_mem *mem) { 1131 return reserve_buf_internal(buf, extra_size, 32, mem); 1132} 1133 1134static int reserve_buf(nghttp3_buf *buf, size_t extra_size, 1135 const nghttp3_mem *mem) { 1136 return reserve_buf_internal(buf, extra_size, 32, mem); 1137} 1138 1139int nghttp3_qpack_encoder_encode(nghttp3_qpack_encoder *encoder, 1140 nghttp3_buf *pbuf, nghttp3_buf *rbuf, 1141 nghttp3_buf *ebuf, int64_t stream_id, 1142 const nghttp3_nv *nva, size_t nvlen) { 1143 size_t i; 1144 uint64_t max_cnt = 0, min_cnt = UINT64_MAX; 1145 uint64_t base; 1146 int rv = 0; 1147 int allow_blocking; 1148 int blocked_stream; 1149 nghttp3_qpack_stream *stream; 1150 1151 if (encoder->ctx.bad) { 1152 return NGHTTP3_ERR_QPACK_FATAL; 1153 } 1154 1155 rv = nghttp3_qpack_encoder_process_dtable_update(encoder, ebuf); 1156 if (rv != 0) { 1157 goto fail; 1158 } 1159 1160 base = encoder->ctx.next_absidx; 1161 1162 stream = nghttp3_qpack_encoder_find_stream(encoder, stream_id); 1163 blocked_stream = 1164 stream && nghttp3_qpack_encoder_stream_is_blocked(encoder, stream); 1165 allow_blocking = 1166 blocked_stream || encoder->ctx.max_blocked_streams > 1167 nghttp3_ksl_len(&encoder->blocked_streams); 1168 1169 DEBUGF("qpack::encode: stream %ld blocked=%d allow_blocking=%d\n", stream_id, 1170 blocked_stream, allow_blocking); 1171 1172 for (i = 0; i < nvlen; ++i) { 1173 rv = nghttp3_qpack_encoder_encode_nv(encoder, &max_cnt, &min_cnt, rbuf, 1174 ebuf, &nva[i], base, allow_blocking); 1175 if (rv != 0) { 1176 goto fail; 1177 } 1178 } 1179 1180 nghttp3_qpack_encoder_write_field_section_prefix(encoder, pbuf, max_cnt, 1181 base); 1182 1183 /* TODO If max_cnt == 0, no reference is made to dtable. */ 1184 if (!max_cnt) { 1185 return 0; 1186 } 1187 1188 rv = qpack_encoder_add_stream_ref(encoder, stream_id, stream, max_cnt, 1189 min_cnt); 1190 if (rv != 0) { 1191 goto fail; 1192 } 1193 1194 return 0; 1195 1196fail: 1197 encoder->ctx.bad = 1; 1198 return rv; 1199} 1200 1201/* 1202 * qpack_write_number writes variable integer to |rbuf|. |num| is an 1203 * integer to write. |prefix| is a prefix of variable integer 1204 * encoding. 1205 * 1206 * This function returns 0 if it succeeds, or one of the following 1207 * negative error codes: 1208 * 1209 * NGHTTP3_ERR_NOMEM 1210 * Out of memory. 1211 */ 1212static int qpack_write_number(nghttp3_buf *rbuf, uint8_t fb, uint64_t num, 1213 size_t prefix, const nghttp3_mem *mem) { 1214 int rv; 1215 size_t len = nghttp3_qpack_put_varint_len(num, prefix); 1216 uint8_t *p; 1217 1218 rv = reserve_buf(rbuf, len, mem); 1219 if (rv != 0) { 1220 return rv; 1221 } 1222 1223 p = rbuf->last; 1224 1225 *p = fb; 1226 p = nghttp3_qpack_put_varint(p, num, prefix); 1227 1228 assert((size_t)(p - rbuf->last) == len); 1229 1230 rbuf->last = p; 1231 1232 return 0; 1233} 1234 1235int nghttp3_qpack_encoder_process_dtable_update(nghttp3_qpack_encoder *encoder, 1236 nghttp3_buf *ebuf) { 1237 int rv; 1238 1239 nghttp3_qpack_encoder_shrink_dtable(encoder); 1240 1241 if (encoder->ctx.max_dtable_capacity < encoder->ctx.dtable_size || 1242 !(encoder->flags & NGHTTP3_QPACK_ENCODER_FLAG_PENDING_SET_DTABLE_CAP)) { 1243 return 0; 1244 } 1245 1246 if (encoder->min_dtable_update < encoder->last_max_dtable_update) { 1247 rv = nghttp3_qpack_encoder_write_set_dtable_cap(encoder, ebuf, 1248 encoder->min_dtable_update); 1249 if (rv != 0) { 1250 return rv; 1251 } 1252 } 1253 1254 rv = nghttp3_qpack_encoder_write_set_dtable_cap( 1255 encoder, ebuf, encoder->last_max_dtable_update); 1256 if (rv != 0) { 1257 return rv; 1258 } 1259 1260 encoder->flags &= (uint8_t)~NGHTTP3_QPACK_ENCODER_FLAG_PENDING_SET_DTABLE_CAP; 1261 encoder->min_dtable_update = SIZE_MAX; 1262 encoder->ctx.max_dtable_capacity = encoder->last_max_dtable_update; 1263 1264 return 0; 1265} 1266 1267int nghttp3_qpack_encoder_write_set_dtable_cap(nghttp3_qpack_encoder *encoder, 1268 nghttp3_buf *ebuf, size_t cap) { 1269 DEBUGF("qpack::encode: Set Dynamic Table Capacity capacity=%zu\n", cap); 1270 return qpack_write_number(ebuf, 0x20, cap, 5, encoder->ctx.mem); 1271} 1272 1273nghttp3_qpack_stream * 1274nghttp3_qpack_encoder_find_stream(nghttp3_qpack_encoder *encoder, 1275 int64_t stream_id) { 1276 return nghttp3_map_find(&encoder->streams, (nghttp3_map_key_type)stream_id); 1277} 1278 1279int nghttp3_qpack_encoder_stream_is_blocked(nghttp3_qpack_encoder *encoder, 1280 nghttp3_qpack_stream *stream) { 1281 return stream && encoder->krcnt < nghttp3_qpack_stream_get_max_cnt(stream); 1282} 1283 1284/* 1285 * qpack_encoder_decide_indexing_mode determines and returns indexing 1286 * mode for header field |nv|. |token| is a token of header field 1287 * name. 1288 */ 1289static nghttp3_qpack_indexing_mode 1290qpack_encoder_decide_indexing_mode(nghttp3_qpack_encoder *encoder, 1291 const nghttp3_nv *nv, int32_t token) { 1292 if (nv->flags & NGHTTP3_NV_FLAG_NEVER_INDEX) { 1293 return NGHTTP3_QPACK_INDEXING_MODE_NEVER; 1294 } 1295 1296 switch (token) { 1297 case NGHTTP3_QPACK_TOKEN_AUTHORIZATION: 1298 return NGHTTP3_QPACK_INDEXING_MODE_NEVER; 1299 case NGHTTP3_QPACK_TOKEN_COOKIE: 1300 if (nv->valuelen < 20) { 1301 return NGHTTP3_QPACK_INDEXING_MODE_NEVER; 1302 } 1303 break; 1304 case -1: 1305 case NGHTTP3_QPACK_TOKEN__PATH: 1306 case NGHTTP3_QPACK_TOKEN_AGE: 1307 case NGHTTP3_QPACK_TOKEN_CONTENT_LENGTH: 1308 case NGHTTP3_QPACK_TOKEN_ETAG: 1309 case NGHTTP3_QPACK_TOKEN_IF_MODIFIED_SINCE: 1310 case NGHTTP3_QPACK_TOKEN_IF_NONE_MATCH: 1311 case NGHTTP3_QPACK_TOKEN_LOCATION: 1312 case NGHTTP3_QPACK_TOKEN_SET_COOKIE: 1313 return NGHTTP3_QPACK_INDEXING_MODE_LITERAL; 1314 case NGHTTP3_QPACK_TOKEN_HOST: 1315 case NGHTTP3_QPACK_TOKEN_TE: 1316 case NGHTTP3_QPACK_TOKEN__PROTOCOL: 1317 case NGHTTP3_QPACK_TOKEN_PRIORITY: 1318 break; 1319 default: 1320 if (token >= 1000) { 1321 return NGHTTP3_QPACK_INDEXING_MODE_LITERAL; 1322 } 1323 } 1324 1325 if (table_space(nv->namelen, nv->valuelen) > 1326 encoder->ctx.max_dtable_capacity * 3 / 4) { 1327 return NGHTTP3_QPACK_INDEXING_MODE_LITERAL; 1328 } 1329 1330 return NGHTTP3_QPACK_INDEXING_MODE_STORE; 1331} 1332 1333/* 1334 * qpack_encoder_can_index returns nonzero if an entry which occupies 1335 * |need| bytes can be inserted into dynamic table. |min_cnt| is the 1336 * minimum insert count which blocked stream requires. 1337 */ 1338static int qpack_encoder_can_index(nghttp3_qpack_encoder *encoder, size_t need, 1339 uint64_t min_cnt) { 1340 size_t avail = 0; 1341 size_t len; 1342 uint64_t gmin_cnt; 1343 nghttp3_qpack_entry *min_ent, *last_ent; 1344 nghttp3_ringbuf *dtable = &encoder->ctx.dtable; 1345 1346 if (encoder->ctx.max_dtable_capacity > encoder->ctx.dtable_size) { 1347 avail = encoder->ctx.max_dtable_capacity - encoder->ctx.dtable_size; 1348 if (need <= avail) { 1349 return 1; 1350 } 1351 } 1352 1353 if (!nghttp3_pq_empty(&encoder->min_cnts)) { 1354 gmin_cnt = nghttp3_qpack_encoder_get_min_cnt(encoder); 1355 min_cnt = nghttp3_min(min_cnt, gmin_cnt); 1356 } 1357 1358 if (min_cnt == UINT64_MAX) { 1359 return encoder->ctx.max_dtable_capacity >= need; 1360 } 1361 1362 min_ent = nghttp3_qpack_context_dtable_get(&encoder->ctx, min_cnt - 1); 1363 1364 len = nghttp3_ringbuf_len(&encoder->ctx.dtable); 1365 assert(len); 1366 last_ent = *(nghttp3_qpack_entry **)nghttp3_ringbuf_get(dtable, len - 1); 1367 1368 if (min_ent == last_ent) { 1369 return 0; 1370 } 1371 1372 return avail + min_ent->sum - last_ent->sum >= need; 1373} 1374 1375/* 1376 * qpack_encoder_can_index_nv returns nonzero if header field |nv| can 1377 * be inserted into dynamic table. |min_cnt| is the minimum insert 1378 * count which blocked stream requires. 1379 */ 1380static int qpack_encoder_can_index_nv(nghttp3_qpack_encoder *encoder, 1381 const nghttp3_nv *nv, uint64_t min_cnt) { 1382 return qpack_encoder_can_index( 1383 encoder, table_space(nv->namelen, nv->valuelen), min_cnt); 1384} 1385 1386/* 1387 * qpack_encoder_can_index_duplicate returns nonzero if an entry at 1388 * |absidx| in dynamic table can be inserted to dynamic table as 1389 * duplicate. |min_cnt| is the minimum insert count which blocked 1390 * stream requires. 1391 */ 1392static int qpack_encoder_can_index_duplicate(nghttp3_qpack_encoder *encoder, 1393 uint64_t absidx, 1394 uint64_t min_cnt) { 1395 nghttp3_qpack_entry *ent = 1396 nghttp3_qpack_context_dtable_get(&encoder->ctx, absidx); 1397 1398 return qpack_encoder_can_index( 1399 encoder, table_space(ent->nv.name->len, ent->nv.value->len), min_cnt); 1400} 1401 1402/* 1403 * qpack_context_check_draining returns nonzero if an entry at 1404 * |absidx| in dynamic table is one of draining entries. 1405 */ 1406static int qpack_context_check_draining(nghttp3_qpack_context *ctx, 1407 uint64_t absidx) { 1408 const size_t safe = ctx->max_dtable_capacity - 1409 nghttp3_min(512, ctx->max_dtable_capacity * 1 / 8); 1410 nghttp3_qpack_entry *ent = nghttp3_qpack_context_dtable_get(ctx, absidx); 1411 1412 return ctx->dtable_sum - ent->sum > safe; 1413} 1414 1415int nghttp3_qpack_encoder_encode_nv(nghttp3_qpack_encoder *encoder, 1416 uint64_t *pmax_cnt, uint64_t *pmin_cnt, 1417 nghttp3_buf *rbuf, nghttp3_buf *ebuf, 1418 const nghttp3_nv *nv, uint64_t base, 1419 int allow_blocking) { 1420 uint32_t hash = 0; 1421 int32_t token; 1422 nghttp3_qpack_indexing_mode indexing_mode; 1423 nghttp3_qpack_lookup_result sres = {-1, 0, -1}, dres = {-1, 0, -1}; 1424 nghttp3_qpack_entry *new_ent = NULL; 1425 int static_entry; 1426 int just_index = 0; 1427 int rv; 1428 1429 token = qpack_lookup_token(nv->name, nv->namelen); 1430 static_entry = token != -1 && (size_t)token < nghttp3_arraylen(token_stable); 1431 if (static_entry) { 1432 hash = token_stable[token].hash; 1433 } else { 1434 switch (token) { 1435 case NGHTTP3_QPACK_TOKEN_HOST: 1436 hash = 2952701295u; 1437 break; 1438 case NGHTTP3_QPACK_TOKEN_TE: 1439 hash = 1011170994u; 1440 break; 1441 case NGHTTP3_QPACK_TOKEN__PROTOCOL: 1442 hash = 1128642621u; 1443 break; 1444 case NGHTTP3_QPACK_TOKEN_PRIORITY: 1445 hash = 2498028297u; 1446 break; 1447 } 1448 } 1449 1450 indexing_mode = qpack_encoder_decide_indexing_mode(encoder, nv, token); 1451 1452 if (static_entry) { 1453 sres = nghttp3_qpack_lookup_stable(nv, token, indexing_mode); 1454 if (sres.index != -1 && sres.name_value_match) { 1455 return nghttp3_qpack_encoder_write_static_indexed(encoder, rbuf, 1456 (size_t)sres.index); 1457 } 1458 } 1459 1460 if (hash && 1461 nghttp3_map_size(&encoder->streams) < NGHTTP3_QPACK_MAX_QPACK_STREAMS) { 1462 dres = nghttp3_qpack_encoder_lookup_dtable(encoder, nv, token, hash, 1463 indexing_mode, encoder->krcnt, 1464 allow_blocking); 1465 just_index = indexing_mode == NGHTTP3_QPACK_INDEXING_MODE_STORE && 1466 dres.pb_index == -1; 1467 } 1468 1469 if (dres.index != -1 && dres.name_value_match) { 1470 if (allow_blocking && 1471 qpack_context_check_draining(&encoder->ctx, (size_t)dres.index) && 1472 qpack_encoder_can_index_duplicate(encoder, (size_t)dres.index, 1473 *pmin_cnt)) { 1474 rv = nghttp3_qpack_encoder_write_duplicate_insert(encoder, ebuf, 1475 (size_t)dres.index); 1476 if (rv != 0) { 1477 return rv; 1478 } 1479 rv = nghttp3_qpack_encoder_dtable_duplicate_add(encoder, 1480 (size_t)dres.index); 1481 if (rv != 0) { 1482 return rv; 1483 } 1484 1485 new_ent = nghttp3_qpack_context_dtable_top(&encoder->ctx); 1486 dres.index = (nghttp3_ssize)new_ent->absidx; 1487 } 1488 *pmax_cnt = nghttp3_max(*pmax_cnt, (size_t)(dres.index + 1)); 1489 *pmin_cnt = nghttp3_min(*pmin_cnt, (size_t)(dres.index + 1)); 1490 1491 return nghttp3_qpack_encoder_write_dynamic_indexed( 1492 encoder, rbuf, (size_t)dres.index, base); 1493 } 1494 1495 if (sres.index != -1) { 1496 if (just_index && qpack_encoder_can_index_nv(encoder, nv, *pmin_cnt)) { 1497 rv = nghttp3_qpack_encoder_write_static_insert(encoder, ebuf, 1498 (size_t)sres.index, nv); 1499 if (rv != 0) { 1500 return rv; 1501 } 1502 rv = nghttp3_qpack_encoder_dtable_static_add(encoder, (size_t)sres.index, 1503 nv, hash); 1504 if (rv != 0) { 1505 return rv; 1506 } 1507 if (allow_blocking) { 1508 new_ent = nghttp3_qpack_context_dtable_top(&encoder->ctx); 1509 *pmax_cnt = nghttp3_max(*pmax_cnt, new_ent->absidx + 1); 1510 *pmin_cnt = nghttp3_min(*pmin_cnt, new_ent->absidx + 1); 1511 1512 return nghttp3_qpack_encoder_write_dynamic_indexed( 1513 encoder, rbuf, new_ent->absidx, base); 1514 } 1515 } 1516 1517 return nghttp3_qpack_encoder_write_static_indexed_name( 1518 encoder, rbuf, (size_t)sres.index, nv); 1519 } 1520 1521 if (dres.index != -1) { 1522 if (just_index && 1523 qpack_encoder_can_index_nv( 1524 encoder, nv, 1525 allow_blocking ? *pmin_cnt 1526 : nghttp3_min((size_t)dres.index + 1, *pmin_cnt))) { 1527 rv = nghttp3_qpack_encoder_write_dynamic_insert(encoder, ebuf, 1528 (size_t)dres.index, nv); 1529 if (rv != 0) { 1530 return rv; 1531 } 1532 1533 if (!allow_blocking) { 1534 *pmin_cnt = nghttp3_min(*pmin_cnt, (size_t)dres.index + 1); 1535 } 1536 1537 rv = nghttp3_qpack_encoder_dtable_dynamic_add(encoder, (size_t)dres.index, 1538 nv, hash); 1539 if (rv != 0) { 1540 return rv; 1541 } 1542 1543 if (allow_blocking) { 1544 new_ent = nghttp3_qpack_context_dtable_top(&encoder->ctx); 1545 *pmax_cnt = nghttp3_max(*pmax_cnt, new_ent->absidx + 1); 1546 *pmin_cnt = nghttp3_min(*pmin_cnt, new_ent->absidx + 1); 1547 1548 return nghttp3_qpack_encoder_write_dynamic_indexed( 1549 encoder, rbuf, new_ent->absidx, base); 1550 } 1551 } 1552 1553 *pmax_cnt = nghttp3_max(*pmax_cnt, (size_t)(dres.index + 1)); 1554 *pmin_cnt = nghttp3_min(*pmin_cnt, (size_t)(dres.index + 1)); 1555 1556 return nghttp3_qpack_encoder_write_dynamic_indexed_name( 1557 encoder, rbuf, (size_t)dres.index, base, nv); 1558 } 1559 1560 if (just_index && qpack_encoder_can_index_nv(encoder, nv, *pmin_cnt)) { 1561 rv = nghttp3_qpack_encoder_dtable_literal_add(encoder, nv, token, hash); 1562 if (rv != 0) { 1563 return rv; 1564 } 1565 rv = nghttp3_qpack_encoder_write_literal_insert(encoder, ebuf, nv); 1566 if (rv != 0) { 1567 return rv; 1568 } 1569 if (allow_blocking) { 1570 new_ent = nghttp3_qpack_context_dtable_top(&encoder->ctx); 1571 *pmax_cnt = nghttp3_max(*pmax_cnt, new_ent->absidx + 1); 1572 *pmin_cnt = nghttp3_min(*pmin_cnt, new_ent->absidx + 1); 1573 1574 return nghttp3_qpack_encoder_write_dynamic_indexed(encoder, rbuf, 1575 new_ent->absidx, base); 1576 } 1577 } 1578 1579 return nghttp3_qpack_encoder_write_literal(encoder, rbuf, nv); 1580} 1581 1582nghttp3_qpack_lookup_result 1583nghttp3_qpack_lookup_stable(const nghttp3_nv *nv, int32_t token, 1584 nghttp3_qpack_indexing_mode indexing_mode) { 1585 nghttp3_qpack_lookup_result res = {(nghttp3_ssize)token_stable[token].absidx, 1586 0, -1}; 1587 nghttp3_qpack_static_entry *ent; 1588 nghttp3_qpack_static_header *hdr; 1589 size_t i; 1590 1591 assert(token >= 0); 1592 1593 if (indexing_mode == NGHTTP3_QPACK_INDEXING_MODE_NEVER) { 1594 return res; 1595 } 1596 1597 for (i = (size_t)token; 1598 i < nghttp3_arraylen(token_stable) && token_stable[i].token == token; 1599 ++i) { 1600 ent = &token_stable[i]; 1601 hdr = &stable[ent->absidx]; 1602 if (hdr->value.len == nv->valuelen && 1603 memeq(hdr->value.base, nv->value, nv->valuelen)) { 1604 res.index = (nghttp3_ssize)ent->absidx; 1605 res.name_value_match = 1; 1606 return res; 1607 } 1608 } 1609 return res; 1610} 1611 1612nghttp3_qpack_lookup_result nghttp3_qpack_encoder_lookup_dtable( 1613 nghttp3_qpack_encoder *encoder, const nghttp3_nv *nv, int32_t token, 1614 uint32_t hash, nghttp3_qpack_indexing_mode indexing_mode, uint64_t krcnt, 1615 int allow_blocking) { 1616 nghttp3_qpack_lookup_result res = {-1, 0, -1}; 1617 int exact_match = 0; 1618 nghttp3_qpack_entry *match, *pb_match; 1619 1620 encoder_qpack_map_find(encoder, &exact_match, &match, &pb_match, nv, token, 1621 hash, krcnt, allow_blocking, 1622 indexing_mode == NGHTTP3_QPACK_INDEXING_MODE_NEVER); 1623 if (match) { 1624 res.index = (nghttp3_ssize)match->absidx; 1625 res.name_value_match = exact_match; 1626 } 1627 if (pb_match) { 1628 res.pb_index = (nghttp3_ssize)pb_match->absidx; 1629 } 1630 1631 return res; 1632} 1633 1634int nghttp3_qpack_header_block_ref_new(nghttp3_qpack_header_block_ref **pref, 1635 uint64_t max_cnt, uint64_t min_cnt, 1636 const nghttp3_mem *mem) { 1637 nghttp3_qpack_header_block_ref *ref = 1638 nghttp3_mem_malloc(mem, sizeof(nghttp3_qpack_header_block_ref)); 1639 1640 if (ref == NULL) { 1641 return NGHTTP3_ERR_NOMEM; 1642 } 1643 1644 ref->max_cnts_pe.index = NGHTTP3_PQ_BAD_INDEX; 1645 ref->min_cnts_pe.index = NGHTTP3_PQ_BAD_INDEX; 1646 ref->max_cnt = max_cnt; 1647 ref->min_cnt = min_cnt; 1648 1649 *pref = ref; 1650 1651 return 0; 1652} 1653 1654void nghttp3_qpack_header_block_ref_del(nghttp3_qpack_header_block_ref *ref, 1655 const nghttp3_mem *mem) { 1656 nghttp3_mem_free(mem, ref); 1657} 1658 1659static int ref_max_cnt_greater(const nghttp3_pq_entry *lhsx, 1660 const nghttp3_pq_entry *rhsx) { 1661 const nghttp3_qpack_header_block_ref *lhs = 1662 nghttp3_struct_of(lhsx, nghttp3_qpack_header_block_ref, max_cnts_pe); 1663 const nghttp3_qpack_header_block_ref *rhs = 1664 nghttp3_struct_of(rhsx, nghttp3_qpack_header_block_ref, max_cnts_pe); 1665 1666 return lhs->max_cnt > rhs->max_cnt; 1667} 1668 1669int nghttp3_qpack_stream_new(nghttp3_qpack_stream **pstream, int64_t stream_id, 1670 const nghttp3_mem *mem) { 1671 int rv; 1672 nghttp3_qpack_stream *stream; 1673 1674 stream = nghttp3_mem_malloc(mem, sizeof(nghttp3_qpack_stream)); 1675 if (stream == NULL) { 1676 return NGHTTP3_ERR_NOMEM; 1677 } 1678 1679 rv = nghttp3_ringbuf_init(&stream->refs, 4, 1680 sizeof(nghttp3_qpack_header_block_ref *), mem); 1681 if (rv != 0) { 1682 nghttp3_mem_free(mem, stream); 1683 return rv; 1684 } 1685 1686 nghttp3_pq_init(&stream->max_cnts, ref_max_cnt_greater, mem); 1687 1688 stream->stream_id = stream_id; 1689 1690 *pstream = stream; 1691 1692 return 0; 1693} 1694 1695void nghttp3_qpack_stream_del(nghttp3_qpack_stream *stream, 1696 const nghttp3_mem *mem) { 1697 nghttp3_qpack_header_block_ref *ref; 1698 size_t i, len; 1699 1700 if (stream == NULL) { 1701 return; 1702 } 1703 1704 nghttp3_pq_free(&stream->max_cnts); 1705 1706 len = nghttp3_ringbuf_len(&stream->refs); 1707 for (i = 0; i < len; ++i) { 1708 ref = *(nghttp3_qpack_header_block_ref **)nghttp3_ringbuf_get(&stream->refs, 1709 i); 1710 nghttp3_qpack_header_block_ref_del(ref, mem); 1711 } 1712 1713 nghttp3_ringbuf_free(&stream->refs); 1714 1715 nghttp3_mem_free(mem, stream); 1716} 1717 1718uint64_t nghttp3_qpack_stream_get_max_cnt(const nghttp3_qpack_stream *stream) { 1719 nghttp3_qpack_header_block_ref *ref; 1720 1721 if (nghttp3_pq_empty(&stream->max_cnts)) { 1722 return 0; 1723 } 1724 1725 ref = nghttp3_struct_of(nghttp3_pq_top(&stream->max_cnts), 1726 nghttp3_qpack_header_block_ref, max_cnts_pe); 1727 return ref->max_cnt; 1728} 1729 1730int nghttp3_qpack_stream_add_ref(nghttp3_qpack_stream *stream, 1731 nghttp3_qpack_header_block_ref *ref) { 1732 nghttp3_qpack_header_block_ref **dest; 1733 int rv; 1734 1735 if (nghttp3_ringbuf_full(&stream->refs)) { 1736 rv = nghttp3_ringbuf_reserve(&stream->refs, 1737 nghttp3_ringbuf_len(&stream->refs) * 2); 1738 if (rv != 0) { 1739 return rv; 1740 } 1741 } 1742 1743 dest = nghttp3_ringbuf_push_back(&stream->refs); 1744 *dest = ref; 1745 1746 return nghttp3_pq_push(&stream->max_cnts, &ref->max_cnts_pe); 1747} 1748 1749void nghttp3_qpack_stream_pop_ref(nghttp3_qpack_stream *stream) { 1750 nghttp3_qpack_header_block_ref *ref; 1751 1752 assert(nghttp3_ringbuf_len(&stream->refs)); 1753 1754 ref = 1755 *(nghttp3_qpack_header_block_ref **)nghttp3_ringbuf_get(&stream->refs, 0); 1756 1757 assert(ref->max_cnts_pe.index != NGHTTP3_PQ_BAD_INDEX); 1758 1759 nghttp3_pq_remove(&stream->max_cnts, &ref->max_cnts_pe); 1760 1761 nghttp3_ringbuf_pop_front(&stream->refs); 1762} 1763 1764int nghttp3_qpack_encoder_write_static_indexed(nghttp3_qpack_encoder *encoder, 1765 nghttp3_buf *rbuf, 1766 uint64_t absidx) { 1767 DEBUGF("qpack::encode: Indexed Field Line (static) absidx=%" PRIu64 "\n", 1768 absidx); 1769 return qpack_write_number(rbuf, 0xc0, absidx, 6, encoder->ctx.mem); 1770} 1771 1772int nghttp3_qpack_encoder_write_dynamic_indexed(nghttp3_qpack_encoder *encoder, 1773 nghttp3_buf *rbuf, 1774 uint64_t absidx, 1775 uint64_t base) { 1776 DEBUGF("qpack::encode: Indexed Field Line (dynamic) absidx=%" PRIu64 1777 " base=%" PRIu64 "\n", 1778 absidx, base); 1779 1780 if (absidx < base) { 1781 return qpack_write_number(rbuf, 0x80, base - absidx - 1, 6, 1782 encoder->ctx.mem); 1783 } 1784 1785 return qpack_write_number(rbuf, 0x10, absidx - base, 4, encoder->ctx.mem); 1786} 1787 1788/* 1789 * qpack_encoder_write_indexed_name writes generic indexed name. |fb| 1790 * is the first byte. |nameidx| is an index of referenced name. 1791 * |prefix| is a prefix of variable integer encoding. |nv| is a 1792 * header field to encode. 1793 * 1794 * This function returns 0 if it succeeds, or one of the following 1795 * negative error codes: 1796 * 1797 * NGHTTP3_ERR_NOMEM 1798 * Out of memory. 1799 */ 1800static int qpack_encoder_write_indexed_name(nghttp3_qpack_encoder *encoder, 1801 nghttp3_buf *buf, uint8_t fb, 1802 uint64_t nameidx, size_t prefix, 1803 const nghttp3_nv *nv) { 1804 int rv; 1805 size_t len = nghttp3_qpack_put_varint_len(nameidx, prefix); 1806 uint8_t *p; 1807 size_t hlen; 1808 int h = 0; 1809 1810 hlen = nghttp3_qpack_huffman_encode_count(nv->value, nv->valuelen); 1811 if (hlen < nv->valuelen) { 1812 h = 1; 1813 len += nghttp3_qpack_put_varint_len(hlen, 7) + hlen; 1814 } else { 1815 len += nghttp3_qpack_put_varint_len(nv->valuelen, 7) + nv->valuelen; 1816 } 1817 1818 rv = reserve_buf(buf, len, encoder->ctx.mem); 1819 if (rv != 0) { 1820 return rv; 1821 } 1822 1823 p = buf->last; 1824 1825 *p = fb; 1826 p = nghttp3_qpack_put_varint(p, nameidx, prefix); 1827 1828 if (h) { 1829 *p = 0x80; 1830 p = nghttp3_qpack_put_varint(p, hlen, 7); 1831 p = nghttp3_qpack_huffman_encode(p, nv->value, nv->valuelen); 1832 } else { 1833 *p = 0; 1834 p = nghttp3_qpack_put_varint(p, nv->valuelen, 7); 1835 if (nv->valuelen) { 1836 p = nghttp3_cpymem(p, nv->value, nv->valuelen); 1837 } 1838 } 1839 1840 assert((size_t)(p - buf->last) == len); 1841 1842 buf->last = p; 1843 1844 return 0; 1845} 1846 1847int nghttp3_qpack_encoder_write_static_indexed_name( 1848 nghttp3_qpack_encoder *encoder, nghttp3_buf *rbuf, uint64_t absidx, 1849 const nghttp3_nv *nv) { 1850 uint8_t fb = 1851 (uint8_t)(0x50 | ((nv->flags & NGHTTP3_NV_FLAG_NEVER_INDEX) ? 0x20 : 0)); 1852 1853 DEBUGF("qpack::encode: Literal Field Line With Name Reference (static) " 1854 "absidx=%" PRIu64 " never=%d\n", 1855 absidx, (nv->flags & NGHTTP3_NV_FLAG_NEVER_INDEX) != 0); 1856 return qpack_encoder_write_indexed_name(encoder, rbuf, fb, absidx, 4, nv); 1857} 1858 1859int nghttp3_qpack_encoder_write_dynamic_indexed_name( 1860 nghttp3_qpack_encoder *encoder, nghttp3_buf *rbuf, uint64_t absidx, 1861 uint64_t base, const nghttp3_nv *nv) { 1862 uint8_t fb; 1863 1864 DEBUGF("qpack::encode: Literal Field Line With Name Reference (dynamic) " 1865 "absidx=%" PRIu64 " base=%" PRIu64 " never=%d\n", 1866 absidx, base, (nv->flags & NGHTTP3_NV_FLAG_NEVER_INDEX) != 0); 1867 1868 if (absidx < base) { 1869 fb = (uint8_t)(0x40 | 1870 ((nv->flags & NGHTTP3_NV_FLAG_NEVER_INDEX) ? 0x20 : 0)); 1871 return qpack_encoder_write_indexed_name(encoder, rbuf, fb, 1872 base - absidx - 1, 4, nv); 1873 } 1874 1875 fb = (nv->flags & NGHTTP3_NV_FLAG_NEVER_INDEX) ? 0x08 : 0; 1876 return qpack_encoder_write_indexed_name(encoder, rbuf, fb, absidx - base, 3, 1877 nv); 1878} 1879 1880/* 1881 * qpack_encoder_write_literal writes generic literal header field 1882 * representation. |fb| is a first byte. |prefix| is a prefix of 1883 * variable integer encoding for name length. |nv| is a header field 1884 * to encode. 1885 * 1886 * This function returns 0 if it succeeds, or one of the following 1887 * negative error codes: 1888 * 1889 * NGHTTP3_ERR_NOMEM 1890 * Out of memory. 1891 */ 1892static int qpack_encoder_write_literal(nghttp3_qpack_encoder *encoder, 1893 nghttp3_buf *buf, uint8_t fb, 1894 size_t prefix, const nghttp3_nv *nv) { 1895 int rv; 1896 size_t len; 1897 uint8_t *p; 1898 size_t nhlen, vhlen; 1899 int nh = 0, vh = 0; 1900 1901 nhlen = nghttp3_qpack_huffman_encode_count(nv->name, nv->namelen); 1902 if (nhlen < nv->namelen) { 1903 nh = 1; 1904 len = nghttp3_qpack_put_varint_len(nhlen, prefix) + nhlen; 1905 } else { 1906 len = nghttp3_qpack_put_varint_len(nv->namelen, prefix) + nv->namelen; 1907 } 1908 1909 vhlen = nghttp3_qpack_huffman_encode_count(nv->value, nv->valuelen); 1910 if (vhlen < nv->valuelen) { 1911 vh = 1; 1912 len += nghttp3_qpack_put_varint_len(vhlen, 7) + vhlen; 1913 } else { 1914 len += nghttp3_qpack_put_varint_len(nv->valuelen, 7) + nv->valuelen; 1915 } 1916 1917 rv = reserve_buf(buf, len, encoder->ctx.mem); 1918 if (rv != 0) { 1919 return rv; 1920 } 1921 1922 p = buf->last; 1923 1924 *p = fb; 1925 if (nh) { 1926 *p |= (uint8_t)(1 << prefix); 1927 p = nghttp3_qpack_put_varint(p, nhlen, prefix); 1928 p = nghttp3_qpack_huffman_encode(p, nv->name, nv->namelen); 1929 } else { 1930 p = nghttp3_qpack_put_varint(p, nv->namelen, prefix); 1931 if (nv->namelen) { 1932 p = nghttp3_cpymem(p, nv->name, nv->namelen); 1933 } 1934 } 1935 1936 *p = 0; 1937 1938 if (vh) { 1939 *p |= 0x80; 1940 p = nghttp3_qpack_put_varint(p, vhlen, 7); 1941 p = nghttp3_qpack_huffman_encode(p, nv->value, nv->valuelen); 1942 } else { 1943 p = nghttp3_qpack_put_varint(p, nv->valuelen, 7); 1944 if (nv->valuelen) { 1945 p = nghttp3_cpymem(p, nv->value, nv->valuelen); 1946 } 1947 } 1948 1949 assert((size_t)(p - buf->last) == len); 1950 1951 buf->last = p; 1952 1953 return 0; 1954} 1955 1956int nghttp3_qpack_encoder_write_literal(nghttp3_qpack_encoder *encoder, 1957 nghttp3_buf *rbuf, 1958 const nghttp3_nv *nv) { 1959 uint8_t fb = 1960 (uint8_t)(0x20 | ((nv->flags & NGHTTP3_NV_FLAG_NEVER_INDEX) ? 0x10 : 0)); 1961 1962 DEBUGF("qpack::encode: Literal Field Line With Literal Name\n"); 1963 return qpack_encoder_write_literal(encoder, rbuf, fb, 3, nv); 1964} 1965 1966int nghttp3_qpack_encoder_write_static_insert(nghttp3_qpack_encoder *encoder, 1967 nghttp3_buf *ebuf, 1968 uint64_t absidx, 1969 const nghttp3_nv *nv) { 1970 DEBUGF("qpack::encode: Insert With Name Reference (static) absidx=%" PRIu64 1971 "\n", 1972 absidx); 1973 return qpack_encoder_write_indexed_name(encoder, ebuf, 0xc0, absidx, 6, nv); 1974} 1975 1976int nghttp3_qpack_encoder_write_dynamic_insert(nghttp3_qpack_encoder *encoder, 1977 nghttp3_buf *ebuf, 1978 uint64_t absidx, 1979 const nghttp3_nv *nv) { 1980 DEBUGF("qpack::encode: Insert With Name Reference (dynamic) absidx=%" PRIu64 1981 "\n", 1982 absidx); 1983 return qpack_encoder_write_indexed_name( 1984 encoder, ebuf, 0x80, encoder->ctx.next_absidx - absidx - 1, 6, nv); 1985} 1986 1987int nghttp3_qpack_encoder_write_duplicate_insert(nghttp3_qpack_encoder *encoder, 1988 nghttp3_buf *ebuf, 1989 uint64_t absidx) { 1990 uint64_t idx = encoder->ctx.next_absidx - absidx - 1; 1991 size_t len = nghttp3_qpack_put_varint_len(idx, 5); 1992 uint8_t *p; 1993 int rv; 1994 1995 DEBUGF("qpack::encode: Insert duplicate absidx=%" PRIu64 "\n", absidx); 1996 1997 rv = reserve_buf(ebuf, len, encoder->ctx.mem); 1998 if (rv != 0) { 1999 return rv; 2000 } 2001 2002 p = ebuf->last; 2003 2004 *p = 0; 2005 p = nghttp3_qpack_put_varint(p, idx, 5); 2006 2007 assert((size_t)(p - ebuf->last) == len); 2008 2009 ebuf->last = p; 2010 2011 return 0; 2012} 2013 2014int nghttp3_qpack_encoder_write_literal_insert(nghttp3_qpack_encoder *encoder, 2015 nghttp3_buf *ebuf, 2016 const nghttp3_nv *nv) { 2017 DEBUGF("qpack::encode: Insert With Literal Name\n"); 2018 return qpack_encoder_write_literal(encoder, ebuf, 0x40, 5, nv); 2019} 2020 2021int nghttp3_qpack_context_dtable_add(nghttp3_qpack_context *ctx, 2022 nghttp3_qpack_nv *qnv, 2023 nghttp3_qpack_map *dtable_map, 2024 uint32_t hash) { 2025 nghttp3_qpack_entry *new_ent, **p, *ent; 2026 const nghttp3_mem *mem = ctx->mem; 2027 size_t space; 2028 size_t i; 2029 int rv; 2030 2031 space = table_space(qnv->name->len, qnv->value->len); 2032 2033 assert(space <= ctx->max_dtable_capacity); 2034 2035 while (ctx->dtable_size + space > ctx->max_dtable_capacity) { 2036 i = nghttp3_ringbuf_len(&ctx->dtable); 2037 assert(i); 2038 ent = *(nghttp3_qpack_entry **)nghttp3_ringbuf_get(&ctx->dtable, i - 1); 2039 2040 ctx->dtable_size -= table_space(ent->nv.name->len, ent->nv.value->len); 2041 2042 nghttp3_ringbuf_pop_back(&ctx->dtable); 2043 if (dtable_map) { 2044 qpack_map_remove(dtable_map, ent); 2045 } 2046 2047 nghttp3_qpack_entry_free(ent); 2048 nghttp3_mem_free(mem, ent); 2049 } 2050 2051 new_ent = nghttp3_mem_malloc(mem, sizeof(nghttp3_qpack_entry)); 2052 if (new_ent == NULL) { 2053 return NGHTTP3_ERR_NOMEM; 2054 } 2055 2056 nghttp3_qpack_entry_init(new_ent, qnv, ctx->dtable_sum, ctx->next_absidx++, 2057 hash); 2058 2059 if (nghttp3_ringbuf_full(&ctx->dtable)) { 2060 rv = nghttp3_ringbuf_reserve(&ctx->dtable, 2061 nghttp3_ringbuf_len(&ctx->dtable) * 2); 2062 if (rv != 0) { 2063 goto fail; 2064 } 2065 } 2066 2067 p = nghttp3_ringbuf_push_front(&ctx->dtable); 2068 *p = new_ent; 2069 2070 if (dtable_map) { 2071 qpack_map_insert(dtable_map, new_ent); 2072 } 2073 2074 ctx->dtable_size += space; 2075 ctx->dtable_sum += space; 2076 2077 return 0; 2078 2079fail: 2080 nghttp3_qpack_entry_free(new_ent); 2081 nghttp3_mem_free(mem, new_ent); 2082 2083 return rv; 2084} 2085 2086int nghttp3_qpack_encoder_dtable_static_add(nghttp3_qpack_encoder *encoder, 2087 uint64_t absidx, 2088 const nghttp3_nv *nv, 2089 uint32_t hash) { 2090 const nghttp3_qpack_static_header *shd; 2091 nghttp3_qpack_nv qnv; 2092 const nghttp3_mem *mem = encoder->ctx.mem; 2093 int rv; 2094 2095 rv = nghttp3_rcbuf_new2(&qnv.value, nv->value, nv->valuelen, mem); 2096 if (rv != 0) { 2097 return rv; 2098 } 2099 2100 assert(nghttp3_arraylen(stable) > absidx); 2101 2102 shd = &stable[absidx]; 2103 2104 qnv.name = (nghttp3_rcbuf *)&shd->name; 2105 qnv.token = shd->token; 2106 qnv.flags = NGHTTP3_NV_FLAG_NONE; 2107 2108 rv = nghttp3_qpack_context_dtable_add(&encoder->ctx, &qnv, 2109 &encoder->dtable_map, hash); 2110 2111 nghttp3_rcbuf_decref(qnv.value); 2112 2113 return rv; 2114} 2115 2116int nghttp3_qpack_encoder_dtable_dynamic_add(nghttp3_qpack_encoder *encoder, 2117 uint64_t absidx, 2118 const nghttp3_nv *nv, 2119 uint32_t hash) { 2120 nghttp3_qpack_nv qnv; 2121 nghttp3_qpack_entry *ent; 2122 const nghttp3_mem *mem = encoder->ctx.mem; 2123 int rv; 2124 2125 rv = nghttp3_rcbuf_new2(&qnv.value, nv->value, nv->valuelen, mem); 2126 if (rv != 0) { 2127 return rv; 2128 } 2129 2130 ent = nghttp3_qpack_context_dtable_get(&encoder->ctx, absidx); 2131 2132 qnv.name = ent->nv.name; 2133 qnv.token = ent->nv.token; 2134 qnv.flags = NGHTTP3_NV_FLAG_NONE; 2135 2136 nghttp3_rcbuf_incref(qnv.name); 2137 2138 rv = nghttp3_qpack_context_dtable_add(&encoder->ctx, &qnv, 2139 &encoder->dtable_map, hash); 2140 2141 nghttp3_rcbuf_decref(qnv.value); 2142 nghttp3_rcbuf_decref(qnv.name); 2143 2144 return rv; 2145} 2146 2147int nghttp3_qpack_encoder_dtable_duplicate_add(nghttp3_qpack_encoder *encoder, 2148 uint64_t absidx) { 2149 nghttp3_qpack_nv qnv; 2150 nghttp3_qpack_entry *ent; 2151 int rv; 2152 2153 ent = nghttp3_qpack_context_dtable_get(&encoder->ctx, absidx); 2154 2155 qnv = ent->nv; 2156 nghttp3_rcbuf_incref(qnv.name); 2157 nghttp3_rcbuf_incref(qnv.value); 2158 2159 rv = nghttp3_qpack_context_dtable_add(&encoder->ctx, &qnv, 2160 &encoder->dtable_map, ent->hash); 2161 2162 nghttp3_rcbuf_decref(qnv.name); 2163 nghttp3_rcbuf_decref(qnv.value); 2164 2165 return rv; 2166} 2167 2168int nghttp3_qpack_encoder_dtable_literal_add(nghttp3_qpack_encoder *encoder, 2169 const nghttp3_nv *nv, 2170 int32_t token, uint32_t hash) { 2171 nghttp3_qpack_nv qnv; 2172 const nghttp3_mem *mem = encoder->ctx.mem; 2173 int rv; 2174 2175 rv = nghttp3_rcbuf_new2(&qnv.name, nv->name, nv->namelen, mem); 2176 if (rv != 0) { 2177 return rv; 2178 } 2179 2180 rv = nghttp3_rcbuf_new2(&qnv.value, nv->value, nv->valuelen, mem); 2181 if (rv != 0) { 2182 nghttp3_rcbuf_decref(qnv.name); 2183 return rv; 2184 } 2185 2186 qnv.token = token; 2187 qnv.flags = NGHTTP3_NV_FLAG_NONE; 2188 2189 rv = nghttp3_qpack_context_dtable_add(&encoder->ctx, &qnv, 2190 &encoder->dtable_map, hash); 2191 2192 nghttp3_rcbuf_decref(qnv.value); 2193 nghttp3_rcbuf_decref(qnv.name); 2194 2195 return rv; 2196} 2197 2198nghttp3_qpack_entry * 2199nghttp3_qpack_context_dtable_get(nghttp3_qpack_context *ctx, uint64_t absidx) { 2200 size_t relidx; 2201 2202 assert(ctx->next_absidx > absidx); 2203 assert(ctx->next_absidx - absidx - 1 < nghttp3_ringbuf_len(&ctx->dtable)); 2204 2205 relidx = (size_t)(ctx->next_absidx - absidx - 1); 2206 2207 return *(nghttp3_qpack_entry **)nghttp3_ringbuf_get(&ctx->dtable, relidx); 2208} 2209 2210nghttp3_qpack_entry * 2211nghttp3_qpack_context_dtable_top(nghttp3_qpack_context *ctx) { 2212 assert(nghttp3_ringbuf_len(&ctx->dtable)); 2213 return *(nghttp3_qpack_entry **)nghttp3_ringbuf_get(&ctx->dtable, 0); 2214} 2215 2216void nghttp3_qpack_entry_init(nghttp3_qpack_entry *ent, nghttp3_qpack_nv *qnv, 2217 size_t sum, uint64_t absidx, uint32_t hash) { 2218 ent->nv = *qnv; 2219 ent->map_next = NULL; 2220 ent->sum = sum; 2221 ent->absidx = absidx; 2222 ent->hash = hash; 2223 2224 nghttp3_rcbuf_incref(ent->nv.name); 2225 nghttp3_rcbuf_incref(ent->nv.value); 2226} 2227 2228void nghttp3_qpack_entry_free(nghttp3_qpack_entry *ent) { 2229 nghttp3_rcbuf_decref(ent->nv.value); 2230 nghttp3_rcbuf_decref(ent->nv.name); 2231} 2232 2233int nghttp3_qpack_encoder_block_stream(nghttp3_qpack_encoder *encoder, 2234 nghttp3_qpack_stream *stream) { 2235 nghttp3_blocked_streams_key bsk = { 2236 nghttp3_struct_of(nghttp3_pq_top(&stream->max_cnts), 2237 nghttp3_qpack_header_block_ref, max_cnts_pe) 2238 ->max_cnt, 2239 (uint64_t)stream->stream_id}; 2240 2241 return nghttp3_ksl_insert(&encoder->blocked_streams, NULL, &bsk, stream); 2242} 2243 2244void nghttp3_qpack_encoder_unblock_stream(nghttp3_qpack_encoder *encoder, 2245 nghttp3_qpack_stream *stream) { 2246 nghttp3_blocked_streams_key bsk = { 2247 nghttp3_struct_of(nghttp3_pq_top(&stream->max_cnts), 2248 nghttp3_qpack_header_block_ref, max_cnts_pe) 2249 ->max_cnt, 2250 (uint64_t)stream->stream_id}; 2251 nghttp3_ksl_it it; 2252 2253 /* This is purely debugging purpose only */ 2254 it = nghttp3_ksl_lower_bound(&encoder->blocked_streams, &bsk); 2255 2256 assert(!nghttp3_ksl_it_end(&it)); 2257 assert(nghttp3_ksl_it_get(&it) == stream); 2258 2259 nghttp3_ksl_remove_hint(&encoder->blocked_streams, NULL, &it, &bsk); 2260} 2261 2262void nghttp3_qpack_encoder_unblock(nghttp3_qpack_encoder *encoder, 2263 uint64_t max_cnt) { 2264 nghttp3_blocked_streams_key bsk = {max_cnt, 0}; 2265 nghttp3_ksl_it it; 2266 2267 it = nghttp3_ksl_lower_bound(&encoder->blocked_streams, &bsk); 2268 2269 for (; !nghttp3_ksl_it_end(&it);) { 2270 bsk = *(nghttp3_blocked_streams_key *)nghttp3_ksl_it_key(&it); 2271 nghttp3_ksl_remove_hint(&encoder->blocked_streams, &it, &it, &bsk); 2272 } 2273} 2274 2275int nghttp3_qpack_encoder_ack_header(nghttp3_qpack_encoder *encoder, 2276 int64_t stream_id) { 2277 nghttp3_qpack_stream *stream = 2278 nghttp3_qpack_encoder_find_stream(encoder, stream_id); 2279 const nghttp3_mem *mem = encoder->ctx.mem; 2280 nghttp3_qpack_header_block_ref *ref; 2281 2282 if (stream == NULL) { 2283 return NGHTTP3_ERR_QPACK_DECODER_STREAM_ERROR; 2284 } 2285 2286 assert(nghttp3_ringbuf_len(&stream->refs)); 2287 2288 ref = 2289 *(nghttp3_qpack_header_block_ref **)nghttp3_ringbuf_get(&stream->refs, 0); 2290 2291 DEBUGF("qpack::encoder: Header acknowledgement stream=%ld ricnt=%" PRIu64 2292 " krcnt=%" PRIu64 "\n", 2293 stream_id, ref->max_cnt, encoder->krcnt); 2294 2295 if (encoder->krcnt < ref->max_cnt) { 2296 encoder->krcnt = ref->max_cnt; 2297 2298 nghttp3_qpack_encoder_unblock(encoder, ref->max_cnt); 2299 } 2300 2301 nghttp3_qpack_stream_pop_ref(stream); 2302 2303 assert(ref->min_cnts_pe.index != NGHTTP3_PQ_BAD_INDEX); 2304 2305 nghttp3_pq_remove(&encoder->min_cnts, &ref->min_cnts_pe); 2306 2307 nghttp3_qpack_header_block_ref_del(ref, mem); 2308 2309 if (nghttp3_ringbuf_len(&stream->refs)) { 2310 return 0; 2311 } 2312 2313 qpack_encoder_remove_stream(encoder, stream); 2314 2315 nghttp3_qpack_stream_del(stream, mem); 2316 2317 return 0; 2318} 2319 2320int nghttp3_qpack_encoder_add_icnt(nghttp3_qpack_encoder *encoder, uint64_t n) { 2321 if (n == 0 || encoder->ctx.next_absidx - encoder->krcnt < n) { 2322 return NGHTTP3_ERR_QPACK_DECODER_STREAM_ERROR; 2323 } 2324 encoder->krcnt += n; 2325 2326 nghttp3_qpack_encoder_unblock(encoder, encoder->krcnt); 2327 2328 return 0; 2329} 2330 2331void nghttp3_qpack_encoder_ack_everything(nghttp3_qpack_encoder *encoder) { 2332 encoder->krcnt = encoder->ctx.next_absidx; 2333 2334 nghttp3_ksl_clear(&encoder->blocked_streams); 2335 nghttp3_pq_clear(&encoder->min_cnts); 2336 nghttp3_map_each_free(&encoder->streams, map_stream_free, 2337 (void *)encoder->ctx.mem); 2338 nghttp3_map_clear(&encoder->streams); 2339} 2340 2341void nghttp3_qpack_encoder_cancel_stream(nghttp3_qpack_encoder *encoder, 2342 int64_t stream_id) { 2343 nghttp3_qpack_stream *stream = 2344 nghttp3_qpack_encoder_find_stream(encoder, stream_id); 2345 const nghttp3_mem *mem = encoder->ctx.mem; 2346 2347 if (stream == NULL) { 2348 return; 2349 } 2350 2351 if (nghttp3_qpack_encoder_stream_is_blocked(encoder, stream)) { 2352 nghttp3_qpack_encoder_unblock_stream(encoder, stream); 2353 } 2354 2355 qpack_encoder_remove_stream(encoder, stream); 2356 2357 nghttp3_qpack_stream_del(stream, mem); 2358} 2359 2360size_t 2361nghttp3_qpack_encoder_get_num_blocked_streams(nghttp3_qpack_encoder *encoder) { 2362 return nghttp3_ksl_len(&encoder->blocked_streams); 2363} 2364 2365int nghttp3_qpack_encoder_write_field_section_prefix( 2366 nghttp3_qpack_encoder *encoder, nghttp3_buf *pbuf, uint64_t ricnt, 2367 uint64_t base) { 2368 size_t max_ents = 2369 encoder->ctx.hard_max_dtable_capacity / NGHTTP3_QPACK_ENTRY_OVERHEAD; 2370 uint64_t encricnt = ricnt == 0 ? 0 : (ricnt % (2 * max_ents)) + 1; 2371 int sign = base < ricnt; 2372 uint64_t delta_base = sign ? ricnt - base - 1 : base - ricnt; 2373 size_t len = nghttp3_qpack_put_varint_len(encricnt, 8) + 2374 nghttp3_qpack_put_varint_len(delta_base, 7); 2375 uint8_t *p; 2376 int rv; 2377 2378 DEBUGF("qpack::encode: ricnt=%" PRIu64 " base=%" PRIu64 " icnt=%" PRIu64 "\n", 2379 ricnt, base, encoder->ctx.next_absidx); 2380 2381 rv = reserve_buf(pbuf, len, encoder->ctx.mem); 2382 if (rv != 0) { 2383 return rv; 2384 } 2385 2386 p = pbuf->last; 2387 2388 p = nghttp3_qpack_put_varint(p, encricnt, 8); 2389 if (sign) { 2390 *p = 0x80; 2391 } else { 2392 *p = 0; 2393 } 2394 p = nghttp3_qpack_put_varint(p, delta_base, 7); 2395 2396 assert((size_t)(p - pbuf->last) == len); 2397 2398 pbuf->last = p; 2399 2400 return 0; 2401} 2402 2403/* 2404 * qpack_read_varint reads |rstate->prefix| prefixed integer stored 2405 * from |begin|. The |end| represents the 1 beyond the last of the 2406 * valid contiguous memory region from |begin|. The decoded integer 2407 * must be less than or equal to NGHTTP3_QPACK_INT_MAX. 2408 * 2409 * If the |rstate->left| is nonzero, it is used as an initial value, 2410 * and this function assumes the |begin| starts with intermediate 2411 * data. |rstate->shift| is used as initial integer shift. 2412 * 2413 * If an entire integer is decoded successfully, the |*fin| is set to 2414 * nonzero. 2415 * 2416 * This function stores the decoded integer in |rstate->left| if it 2417 * succeeds, including partial decoding (in this case, number of shift 2418 * to make in the next call will be stored in |rstate->shift|) and 2419 * returns number of bytes processed, or returns negative error code 2420 * NGHTTP3_ERR_QPACK_FATAL, indicating decoding error. 2421 */ 2422static nghttp3_ssize qpack_read_varint(int *fin, 2423 nghttp3_qpack_read_state *rstate, 2424 const uint8_t *begin, 2425 const uint8_t *end) { 2426 uint64_t k = (uint8_t)((1 << rstate->prefix) - 1); 2427 uint64_t n = rstate->left; 2428 uint64_t add; 2429 const uint8_t *p = begin; 2430 size_t shift = rstate->shift; 2431 2432 rstate->shift = 0; 2433 *fin = 0; 2434 2435 if (n == 0) { 2436 if (((*p) & k) != k) { 2437 rstate->left = (*p) & k; 2438 *fin = 1; 2439 return 1; 2440 } 2441 2442 n = k; 2443 2444 if (++p == end) { 2445 rstate->left = n; 2446 return (nghttp3_ssize)(p - begin); 2447 } 2448 } 2449 2450 for (; p != end; ++p, shift += 7) { 2451 add = (*p) & 0x7f; 2452 2453 if (shift > 62) { 2454 return NGHTTP3_ERR_QPACK_FATAL; 2455 } 2456 2457 if ((NGHTTP3_QPACK_INT_MAX >> shift) < add) { 2458 return NGHTTP3_ERR_QPACK_FATAL; 2459 } 2460 2461 add <<= shift; 2462 2463 if (NGHTTP3_QPACK_INT_MAX - add < n) { 2464 return NGHTTP3_ERR_QPACK_FATAL; 2465 } 2466 2467 n += add; 2468 2469 if (((*p) & (1 << 7)) == 0) { 2470 break; 2471 } 2472 } 2473 2474 rstate->shift = shift; 2475 2476 if (p == end) { 2477 rstate->left = n; 2478 return (nghttp3_ssize)(p - begin); 2479 } 2480 2481 rstate->left = n; 2482 *fin = 1; 2483 return (nghttp3_ssize)(p + 1 - begin); 2484} 2485 2486nghttp3_ssize nghttp3_qpack_encoder_read_decoder(nghttp3_qpack_encoder *encoder, 2487 const uint8_t *src, 2488 size_t srclen) { 2489 const uint8_t *p = src, *end; 2490 int rv; 2491 nghttp3_ssize nread; 2492 int rfin; 2493 2494 if (encoder->ctx.bad) { 2495 return NGHTTP3_ERR_QPACK_FATAL; 2496 } 2497 2498 if (srclen == 0) { 2499 return 0; 2500 } 2501 2502 end = src + srclen; 2503 2504 for (; p != end;) { 2505 switch (encoder->state) { 2506 case NGHTTP3_QPACK_DS_STATE_OPCODE: 2507 if ((*p) & 0x80) { 2508 DEBUGF("qpack::encode: OPCODE_SECTION_ACK\n"); 2509 encoder->opcode = NGHTTP3_QPACK_DS_OPCODE_SECTION_ACK; 2510 encoder->rstate.prefix = 7; 2511 } else if ((*p) & 0x40) { 2512 DEBUGF("qpack::encode: OPCODE_STREAM_CANCEL\n"); 2513 encoder->opcode = NGHTTP3_QPACK_DS_OPCODE_STREAM_CANCEL; 2514 encoder->rstate.prefix = 6; 2515 } else { 2516 DEBUGF("qpack::encode: OPCODE_ICNT_INCREMENT\n"); 2517 encoder->opcode = NGHTTP3_QPACK_DS_OPCODE_ICNT_INCREMENT; 2518 encoder->rstate.prefix = 6; 2519 } 2520 encoder->state = NGHTTP3_QPACK_DS_STATE_READ_NUMBER; 2521 /* fall through */ 2522 case NGHTTP3_QPACK_DS_STATE_READ_NUMBER: 2523 nread = qpack_read_varint(&rfin, &encoder->rstate, p, end); 2524 if (nread < 0) { 2525 assert(nread == NGHTTP3_ERR_QPACK_FATAL); 2526 rv = NGHTTP3_ERR_QPACK_DECODER_STREAM_ERROR; 2527 goto fail; 2528 } 2529 2530 p += nread; 2531 2532 if (!rfin) { 2533 return p - src; 2534 } 2535 2536 switch (encoder->opcode) { 2537 case NGHTTP3_QPACK_DS_OPCODE_ICNT_INCREMENT: 2538 rv = nghttp3_qpack_encoder_add_icnt(encoder, encoder->rstate.left); 2539 if (rv != 0) { 2540 goto fail; 2541 } 2542 break; 2543 case NGHTTP3_QPACK_DS_OPCODE_SECTION_ACK: 2544 rv = nghttp3_qpack_encoder_ack_header(encoder, 2545 (int64_t)encoder->rstate.left); 2546 if (rv != 0) { 2547 goto fail; 2548 } 2549 break; 2550 case NGHTTP3_QPACK_DS_OPCODE_STREAM_CANCEL: 2551 nghttp3_qpack_encoder_cancel_stream(encoder, 2552 (int64_t)encoder->rstate.left); 2553 break; 2554 default: 2555 /* unreachable */ 2556 assert(0); 2557 break; 2558 } 2559 2560 encoder->state = NGHTTP3_QPACK_DS_STATE_OPCODE; 2561 nghttp3_qpack_read_state_reset(&encoder->rstate); 2562 break; 2563 default: 2564 /* unreachable */ 2565 assert(0); 2566 break; 2567 } 2568 } 2569 2570 return p - src; 2571 2572fail: 2573 encoder->ctx.bad = 1; 2574 return rv; 2575} 2576 2577size_t nghttp3_qpack_put_varint_len(uint64_t n, size_t prefix) { 2578 size_t k = (size_t)((1 << prefix) - 1); 2579 size_t len = 0; 2580 2581 if (n < k) { 2582 return 1; 2583 } 2584 2585 n -= k; 2586 ++len; 2587 2588 for (; n >= 128; n >>= 7, ++len) 2589 ; 2590 2591 return len + 1; 2592} 2593 2594uint8_t *nghttp3_qpack_put_varint(uint8_t *buf, uint64_t n, size_t prefix) { 2595 size_t k = (size_t)((1 << prefix) - 1); 2596 2597 *buf = (uint8_t)(*buf & ~k); 2598 2599 if (n < k) { 2600 *buf = (uint8_t)(*buf | n); 2601 return buf + 1; 2602 } 2603 2604 *buf = (uint8_t)(*buf | k); 2605 ++buf; 2606 2607 n -= k; 2608 2609 for (; n >= 128; n >>= 7) { 2610 *buf++ = (uint8_t)((1 << 7) | (n & 0x7f)); 2611 } 2612 2613 *buf++ = (uint8_t)n; 2614 2615 return buf; 2616} 2617 2618void nghttp3_qpack_read_state_free(nghttp3_qpack_read_state *rstate) { 2619 nghttp3_rcbuf_decref(rstate->value); 2620 nghttp3_rcbuf_decref(rstate->name); 2621} 2622 2623void nghttp3_qpack_read_state_reset(nghttp3_qpack_read_state *rstate) { 2624 rstate->name = NULL; 2625 rstate->value = NULL; 2626 nghttp3_buf_init(&rstate->namebuf); 2627 nghttp3_buf_init(&rstate->valuebuf); 2628 rstate->left = 0; 2629 rstate->prefix = 0; 2630 rstate->shift = 0; 2631 rstate->absidx = 0; 2632 rstate->never = 0; 2633 rstate->dynamic = 0; 2634 rstate->huffman_encoded = 0; 2635} 2636 2637int nghttp3_qpack_decoder_init(nghttp3_qpack_decoder *decoder, 2638 size_t hard_max_dtable_capacity, 2639 size_t max_blocked_streams, 2640 const nghttp3_mem *mem) { 2641 int rv; 2642 2643 rv = qpack_context_init(&decoder->ctx, hard_max_dtable_capacity, 2644 max_blocked_streams, mem); 2645 if (rv != 0) { 2646 return rv; 2647 } 2648 2649 decoder->state = NGHTTP3_QPACK_ES_STATE_OPCODE; 2650 decoder->opcode = 0; 2651 decoder->written_icnt = 0; 2652 decoder->max_concurrent_streams = 0; 2653 2654 nghttp3_qpack_read_state_reset(&decoder->rstate); 2655 nghttp3_buf_init(&decoder->dbuf); 2656 2657 return 0; 2658} 2659 2660void nghttp3_qpack_decoder_free(nghttp3_qpack_decoder *decoder) { 2661 nghttp3_buf_free(&decoder->dbuf, decoder->ctx.mem); 2662 nghttp3_qpack_read_state_free(&decoder->rstate); 2663 qpack_context_free(&decoder->ctx); 2664} 2665 2666/* 2667 * qpack_read_huffman_string decodes huffman string in buffer [begin, 2668 * end) and writes the decoded string to |dest|. This function 2669 * assumes the buffer pointed by |dest| has enough space. 2670 * 2671 * This function returns 0 if it succeeds, or one of the following 2672 * negative error codes: 2673 * 2674 * NGHTTP3_ERR_QPACK_FATAL 2675 * Could not decode huffman string. 2676 */ 2677static nghttp3_ssize qpack_read_huffman_string(nghttp3_qpack_read_state *rstate, 2678 nghttp3_buf *dest, 2679 const uint8_t *begin, 2680 const uint8_t *end) { 2681 nghttp3_ssize nwrite; 2682 size_t len = (size_t)(end - begin); 2683 int fin = 0; 2684 2685 if (len >= rstate->left) { 2686 len = (size_t)rstate->left; 2687 fin = 1; 2688 } 2689 2690 nwrite = nghttp3_qpack_huffman_decode(&rstate->huffman_ctx, dest->last, begin, 2691 len, fin); 2692 if (nwrite < 0) { 2693 return nwrite; 2694 } 2695 2696 if (nghttp3_qpack_huffman_decode_failure_state(&rstate->huffman_ctx)) { 2697 return NGHTTP3_ERR_QPACK_FATAL; 2698 } 2699 2700 dest->last += nwrite; 2701 rstate->left -= len; 2702 return (nghttp3_ssize)len; 2703} 2704 2705static nghttp3_ssize qpack_read_string(nghttp3_qpack_read_state *rstate, 2706 nghttp3_buf *dest, const uint8_t *begin, 2707 const uint8_t *end) { 2708 size_t len = (size_t)(end - begin); 2709 size_t n = (size_t)nghttp3_min((uint64_t)len, rstate->left); 2710 2711 dest->last = nghttp3_cpymem(dest->last, begin, n); 2712 2713 rstate->left -= n; 2714 return (nghttp3_ssize)n; 2715} 2716 2717/* 2718 * qpack_decoder_validate_index checks rstate->absidx is acceptable. 2719 * 2720 * It returns 0 if it succeeds, or one of the following negative error 2721 * codes: 2722 * 2723 * NGHTTP3_ERR_QPACK_FATAL 2724 * rstate->absidx is invalid. 2725 */ 2726static int qpack_decoder_validate_index(nghttp3_qpack_decoder *decoder, 2727 nghttp3_qpack_read_state *rstate) { 2728 if (rstate->dynamic) { 2729 return rstate->absidx < decoder->ctx.next_absidx && 2730 decoder->ctx.next_absidx - rstate->absidx - 1 < 2731 nghttp3_ringbuf_len(&decoder->ctx.dtable) 2732 ? 0 2733 : NGHTTP3_ERR_QPACK_FATAL; 2734 } 2735 return rstate->absidx < nghttp3_arraylen(stable) ? 0 2736 : NGHTTP3_ERR_QPACK_FATAL; 2737} 2738 2739static void qpack_read_state_check_huffman(nghttp3_qpack_read_state *rstate, 2740 const uint8_t b) { 2741 rstate->huffman_encoded = (b & (1 << rstate->prefix)) != 0; 2742} 2743 2744static void qpack_read_state_terminate_name(nghttp3_qpack_read_state *rstate) { 2745 *rstate->namebuf.last = '\0'; 2746 rstate->name->len = nghttp3_buf_len(&rstate->namebuf); 2747} 2748 2749static void qpack_read_state_terminate_value(nghttp3_qpack_read_state *rstate) { 2750 *rstate->valuebuf.last = '\0'; 2751 rstate->value->len = nghttp3_buf_len(&rstate->valuebuf); 2752} 2753 2754nghttp3_ssize nghttp3_qpack_decoder_read_encoder(nghttp3_qpack_decoder *decoder, 2755 const uint8_t *src, 2756 size_t srclen) { 2757 const uint8_t *p = src, *end; 2758 int rv; 2759 int busy = 0; 2760 const nghttp3_mem *mem = decoder->ctx.mem; 2761 nghttp3_ssize nread; 2762 int rfin; 2763 2764 if (decoder->ctx.bad) { 2765 return NGHTTP3_ERR_QPACK_FATAL; 2766 } 2767 2768 if (srclen == 0) { 2769 return 0; 2770 } 2771 2772 end = src + srclen; 2773 2774 for (; p != end || busy;) { 2775 busy = 0; 2776 switch (decoder->state) { 2777 case NGHTTP3_QPACK_ES_STATE_OPCODE: 2778 if ((*p) & 0x80) { 2779 DEBUGF("qpack::decode: OPCODE_INSERT_INDEXED\n"); 2780 decoder->opcode = NGHTTP3_QPACK_ES_OPCODE_INSERT_INDEXED; 2781 decoder->rstate.dynamic = !((*p) & 0x40); 2782 decoder->rstate.prefix = 6; 2783 decoder->state = NGHTTP3_QPACK_ES_STATE_READ_INDEX; 2784 } else if ((*p) & 0x40) { 2785 DEBUGF("qpack::decode: OPCODE_INSERT\n"); 2786 decoder->opcode = NGHTTP3_QPACK_ES_OPCODE_INSERT; 2787 decoder->rstate.dynamic = 0; 2788 decoder->rstate.prefix = 5; 2789 decoder->state = NGHTTP3_QPACK_ES_STATE_CHECK_NAME_HUFFMAN; 2790 } else if ((*p) & 0x20) { 2791 DEBUGF("qpack::decode: OPCODE_SET_DTABLE_TABLE_CAP\n"); 2792 decoder->opcode = NGHTTP3_QPACK_ES_OPCODE_SET_DTABLE_CAP; 2793 decoder->rstate.prefix = 5; 2794 decoder->state = NGHTTP3_QPACK_ES_STATE_READ_INDEX; 2795 } else if (!((*p) & 0x20)) { 2796 DEBUGF("qpack::decode: OPCODE_DUPLICATE\n"); 2797 decoder->opcode = NGHTTP3_QPACK_ES_OPCODE_DUPLICATE; 2798 decoder->rstate.dynamic = 1; 2799 decoder->rstate.prefix = 5; 2800 decoder->state = NGHTTP3_QPACK_ES_STATE_READ_INDEX; 2801 } else { 2802 DEBUGF("qpack::decode: unknown opcode %02x\n", *p); 2803 rv = NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR; 2804 goto fail; 2805 } 2806 break; 2807 case NGHTTP3_QPACK_ES_STATE_READ_INDEX: 2808 nread = qpack_read_varint(&rfin, &decoder->rstate, p, end); 2809 if (nread < 0) { 2810 assert(NGHTTP3_ERR_QPACK_FATAL == nread); 2811 rv = NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR; 2812 goto fail; 2813 } 2814 2815 p += nread; 2816 2817 if (!rfin) { 2818 return p - src; 2819 } 2820 2821 if (decoder->opcode == NGHTTP3_QPACK_ES_OPCODE_SET_DTABLE_CAP) { 2822 DEBUGF("qpack::decode: Set dtable capacity to %" PRIu64 "\n", 2823 decoder->rstate.left); 2824 rv = nghttp3_qpack_decoder_set_max_dtable_capacity( 2825 decoder, (size_t)decoder->rstate.left); 2826 if (rv != 0) { 2827 rv = NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR; 2828 goto fail; 2829 } 2830 2831 decoder->state = NGHTTP3_QPACK_ES_STATE_OPCODE; 2832 nghttp3_qpack_read_state_reset(&decoder->rstate); 2833 break; 2834 } 2835 2836 rv = nghttp3_qpack_decoder_rel2abs(decoder, &decoder->rstate); 2837 if (rv < 0) { 2838 goto fail; 2839 } 2840 2841 if (decoder->opcode == NGHTTP3_QPACK_ES_OPCODE_DUPLICATE) { 2842 rv = nghttp3_qpack_decoder_dtable_duplicate_add(decoder); 2843 if (rv != 0) { 2844 goto fail; 2845 } 2846 decoder->state = NGHTTP3_QPACK_ES_STATE_OPCODE; 2847 nghttp3_qpack_read_state_reset(&decoder->rstate); 2848 break; 2849 } 2850 2851 if (decoder->opcode == NGHTTP3_QPACK_ES_OPCODE_INSERT_INDEXED) { 2852 decoder->rstate.prefix = 7; 2853 decoder->state = NGHTTP3_QPACK_ES_STATE_CHECK_VALUE_HUFFMAN; 2854 break; 2855 } 2856 2857 /* Unreachable */ 2858 assert(0); 2859 break; 2860 case NGHTTP3_QPACK_ES_STATE_CHECK_NAME_HUFFMAN: 2861 qpack_read_state_check_huffman(&decoder->rstate, *p); 2862 decoder->state = NGHTTP3_QPACK_ES_STATE_READ_NAMELEN; 2863 decoder->rstate.left = 0; 2864 decoder->rstate.shift = 0; 2865 /* Fall through */ 2866 case NGHTTP3_QPACK_ES_STATE_READ_NAMELEN: 2867 nread = qpack_read_varint(&rfin, &decoder->rstate, p, end); 2868 if (nread < 0) { 2869 assert(NGHTTP3_ERR_QPACK_FATAL == nread); 2870 rv = NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR; 2871 goto fail; 2872 } 2873 2874 p += nread; 2875 2876 if (!rfin) { 2877 return p - src; 2878 } 2879 2880 if (decoder->rstate.left > NGHTTP3_QPACK_MAX_NAMELEN) { 2881 rv = NGHTTP3_ERR_QPACK_HEADER_TOO_LARGE; 2882 goto fail; 2883 } 2884 2885 if (decoder->rstate.huffman_encoded) { 2886 decoder->state = NGHTTP3_QPACK_ES_STATE_READ_NAME_HUFFMAN; 2887 nghttp3_qpack_huffman_decode_context_init(&decoder->rstate.huffman_ctx); 2888 rv = nghttp3_rcbuf_new(&decoder->rstate.name, 2889 (size_t)decoder->rstate.left * 2 + 1, mem); 2890 } else { 2891 decoder->state = NGHTTP3_QPACK_ES_STATE_READ_NAME; 2892 rv = nghttp3_rcbuf_new(&decoder->rstate.name, 2893 (size_t)decoder->rstate.left + 1, mem); 2894 } 2895 if (rv != 0) { 2896 goto fail; 2897 } 2898 2899 nghttp3_buf_wrap_init(&decoder->rstate.namebuf, 2900 decoder->rstate.name->base, 2901 decoder->rstate.name->len); 2902 break; 2903 case NGHTTP3_QPACK_ES_STATE_READ_NAME_HUFFMAN: 2904 nread = qpack_read_huffman_string(&decoder->rstate, 2905 &decoder->rstate.namebuf, p, end); 2906 if (nread < 0) { 2907 assert(NGHTTP3_ERR_QPACK_FATAL == nread); 2908 rv = NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR; 2909 goto fail; 2910 } 2911 2912 p += nread; 2913 2914 if (decoder->rstate.left) { 2915 return p - src; 2916 } 2917 2918 qpack_read_state_terminate_name(&decoder->rstate); 2919 2920 decoder->state = NGHTTP3_QPACK_ES_STATE_CHECK_VALUE_HUFFMAN; 2921 decoder->rstate.prefix = 7; 2922 break; 2923 case NGHTTP3_QPACK_ES_STATE_READ_NAME: 2924 nread = 2925 qpack_read_string(&decoder->rstate, &decoder->rstate.namebuf, p, end); 2926 if (nread < 0) { 2927 rv = (int)nread; 2928 goto fail; 2929 } 2930 2931 p += nread; 2932 2933 if (decoder->rstate.left) { 2934 return p - src; 2935 } 2936 2937 qpack_read_state_terminate_name(&decoder->rstate); 2938 2939 decoder->state = NGHTTP3_QPACK_ES_STATE_CHECK_VALUE_HUFFMAN; 2940 decoder->rstate.prefix = 7; 2941 break; 2942 case NGHTTP3_QPACK_ES_STATE_CHECK_VALUE_HUFFMAN: 2943 qpack_read_state_check_huffman(&decoder->rstate, *p); 2944 decoder->state = NGHTTP3_QPACK_ES_STATE_READ_VALUELEN; 2945 decoder->rstate.left = 0; 2946 decoder->rstate.shift = 0; 2947 /* Fall through */ 2948 case NGHTTP3_QPACK_ES_STATE_READ_VALUELEN: 2949 nread = qpack_read_varint(&rfin, &decoder->rstate, p, end); 2950 if (nread < 0) { 2951 assert(NGHTTP3_ERR_QPACK_FATAL == nread); 2952 rv = NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR; 2953 goto fail; 2954 } 2955 2956 p += nread; 2957 2958 if (!rfin) { 2959 return p - src; 2960 } 2961 2962 if (decoder->rstate.left > NGHTTP3_QPACK_MAX_VALUELEN) { 2963 rv = NGHTTP3_ERR_QPACK_HEADER_TOO_LARGE; 2964 goto fail; 2965 } 2966 2967 if (decoder->rstate.huffman_encoded) { 2968 decoder->state = NGHTTP3_QPACK_ES_STATE_READ_VALUE_HUFFMAN; 2969 nghttp3_qpack_huffman_decode_context_init(&decoder->rstate.huffman_ctx); 2970 rv = nghttp3_rcbuf_new(&decoder->rstate.value, 2971 (size_t)decoder->rstate.left * 2 + 1, mem); 2972 } else { 2973 decoder->state = NGHTTP3_QPACK_ES_STATE_READ_VALUE; 2974 rv = nghttp3_rcbuf_new(&decoder->rstate.value, 2975 (size_t)decoder->rstate.left + 1, mem); 2976 } 2977 if (rv != 0) { 2978 goto fail; 2979 } 2980 2981 nghttp3_buf_wrap_init(&decoder->rstate.valuebuf, 2982 decoder->rstate.value->base, 2983 decoder->rstate.value->len); 2984 2985 /* value might be 0 length */ 2986 busy = 1; 2987 break; 2988 case NGHTTP3_QPACK_ES_STATE_READ_VALUE_HUFFMAN: 2989 nread = qpack_read_huffman_string(&decoder->rstate, 2990 &decoder->rstate.valuebuf, p, end); 2991 if (nread < 0) { 2992 assert(NGHTTP3_ERR_QPACK_FATAL == nread); 2993 rv = NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR; 2994 goto fail; 2995 } 2996 2997 p += nread; 2998 2999 if (decoder->rstate.left) { 3000 return p - src; 3001 } 3002 3003 qpack_read_state_terminate_value(&decoder->rstate); 3004 3005 switch (decoder->opcode) { 3006 case NGHTTP3_QPACK_ES_OPCODE_INSERT_INDEXED: 3007 rv = nghttp3_qpack_decoder_dtable_indexed_add(decoder); 3008 break; 3009 case NGHTTP3_QPACK_ES_OPCODE_INSERT: 3010 rv = nghttp3_qpack_decoder_dtable_literal_add(decoder); 3011 break; 3012 default: 3013 /* Unreachable */ 3014 assert(0); 3015 abort(); 3016 } 3017 if (rv != 0) { 3018 goto fail; 3019 } 3020 3021 decoder->state = NGHTTP3_QPACK_ES_STATE_OPCODE; 3022 nghttp3_qpack_read_state_reset(&decoder->rstate); 3023 break; 3024 case NGHTTP3_QPACK_ES_STATE_READ_VALUE: 3025 nread = qpack_read_string(&decoder->rstate, &decoder->rstate.valuebuf, p, 3026 end); 3027 if (nread < 0) { 3028 rv = (int)nread; 3029 goto fail; 3030 } 3031 3032 p += nread; 3033 3034 if (decoder->rstate.left) { 3035 return p - src; 3036 } 3037 3038 qpack_read_state_terminate_value(&decoder->rstate); 3039 3040 switch (decoder->opcode) { 3041 case NGHTTP3_QPACK_ES_OPCODE_INSERT_INDEXED: 3042 rv = nghttp3_qpack_decoder_dtable_indexed_add(decoder); 3043 break; 3044 case NGHTTP3_QPACK_ES_OPCODE_INSERT: 3045 rv = nghttp3_qpack_decoder_dtable_literal_add(decoder); 3046 break; 3047 default: 3048 /* Unreachable */ 3049 assert(0); 3050 abort(); 3051 } 3052 if (rv != 0) { 3053 goto fail; 3054 } 3055 3056 decoder->state = NGHTTP3_QPACK_ES_STATE_OPCODE; 3057 nghttp3_qpack_read_state_reset(&decoder->rstate); 3058 break; 3059 } 3060 } 3061 3062 return p - src; 3063 3064fail: 3065 decoder->ctx.bad = 1; 3066 return rv; 3067} 3068 3069int nghttp3_qpack_decoder_set_max_dtable_capacity( 3070 nghttp3_qpack_decoder *decoder, size_t max_dtable_capacity) { 3071 nghttp3_qpack_entry *ent; 3072 size_t i; 3073 nghttp3_qpack_context *ctx = &decoder->ctx; 3074 const nghttp3_mem *mem = ctx->mem; 3075 3076 if (max_dtable_capacity > decoder->ctx.hard_max_dtable_capacity) { 3077 return NGHTTP3_ERR_INVALID_ARGUMENT; 3078 } 3079 3080 ctx->max_dtable_capacity = max_dtable_capacity; 3081 3082 while (ctx->dtable_size > max_dtable_capacity) { 3083 i = nghttp3_ringbuf_len(&ctx->dtable); 3084 assert(i); 3085 ent = *(nghttp3_qpack_entry **)nghttp3_ringbuf_get(&ctx->dtable, i - 1); 3086 3087 ctx->dtable_size -= table_space(ent->nv.name->len, ent->nv.value->len); 3088 3089 nghttp3_ringbuf_pop_back(&ctx->dtable); 3090 nghttp3_qpack_entry_free(ent); 3091 nghttp3_mem_free(mem, ent); 3092 } 3093 3094 return 0; 3095} 3096 3097int nghttp3_qpack_decoder_dtable_indexed_add(nghttp3_qpack_decoder *decoder) { 3098 DEBUGF("qpack::decode: Insert With Name Reference (%s) absidx=%" PRIu64 ": " 3099 "value=%*s\n", 3100 decoder->rstate.dynamic ? "dynamic" : "static", decoder->rstate.absidx, 3101 (int)decoder->rstate.value->len, decoder->rstate.value->base); 3102 3103 if (decoder->rstate.dynamic) { 3104 return nghttp3_qpack_decoder_dtable_dynamic_add(decoder); 3105 } 3106 3107 return nghttp3_qpack_decoder_dtable_static_add(decoder); 3108} 3109 3110int nghttp3_qpack_decoder_dtable_static_add(nghttp3_qpack_decoder *decoder) { 3111 nghttp3_qpack_nv qnv; 3112 int rv; 3113 const nghttp3_qpack_static_header *shd; 3114 3115 shd = &stable[decoder->rstate.absidx]; 3116 3117 if (table_space(shd->name.len, decoder->rstate.value->len) > 3118 decoder->ctx.max_dtable_capacity) { 3119 return NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR; 3120 } 3121 3122 qnv.name = (nghttp3_rcbuf *)&shd->name; 3123 qnv.value = decoder->rstate.value; 3124 qnv.token = shd->token; 3125 qnv.flags = NGHTTP3_NV_FLAG_NONE; 3126 3127 rv = nghttp3_qpack_context_dtable_add(&decoder->ctx, &qnv, NULL, 0); 3128 3129 nghttp3_rcbuf_decref(qnv.value); 3130 3131 return rv; 3132} 3133 3134int nghttp3_qpack_decoder_dtable_dynamic_add(nghttp3_qpack_decoder *decoder) { 3135 nghttp3_qpack_nv qnv; 3136 int rv; 3137 nghttp3_qpack_entry *ent; 3138 3139 ent = nghttp3_qpack_context_dtable_get(&decoder->ctx, decoder->rstate.absidx); 3140 3141 if (table_space(ent->nv.name->len, decoder->rstate.value->len) > 3142 decoder->ctx.max_dtable_capacity) { 3143 return NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR; 3144 } 3145 3146 qnv.name = ent->nv.name; 3147 qnv.value = decoder->rstate.value; 3148 qnv.token = ent->nv.token; 3149 qnv.flags = NGHTTP3_NV_FLAG_NONE; 3150 3151 nghttp3_rcbuf_incref(qnv.name); 3152 3153 rv = nghttp3_qpack_context_dtable_add(&decoder->ctx, &qnv, NULL, 0); 3154 3155 nghttp3_rcbuf_decref(qnv.value); 3156 nghttp3_rcbuf_decref(qnv.name); 3157 3158 return rv; 3159} 3160 3161int nghttp3_qpack_decoder_dtable_duplicate_add(nghttp3_qpack_decoder *decoder) { 3162 int rv; 3163 nghttp3_qpack_entry *ent; 3164 nghttp3_qpack_nv qnv; 3165 3166 DEBUGF("qpack::decode: Insert duplicate absidx=%" PRIu64 "\n", 3167 decoder->rstate.absidx); 3168 3169 ent = nghttp3_qpack_context_dtable_get(&decoder->ctx, decoder->rstate.absidx); 3170 3171 if (table_space(ent->nv.name->len, ent->nv.value->len) > 3172 decoder->ctx.max_dtable_capacity) { 3173 return NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR; 3174 } 3175 3176 qnv = ent->nv; 3177 nghttp3_rcbuf_incref(qnv.name); 3178 nghttp3_rcbuf_incref(qnv.value); 3179 3180 rv = nghttp3_qpack_context_dtable_add(&decoder->ctx, &qnv, NULL, 0); 3181 3182 nghttp3_rcbuf_decref(qnv.value); 3183 nghttp3_rcbuf_decref(qnv.name); 3184 3185 return rv; 3186} 3187 3188int nghttp3_qpack_decoder_dtable_literal_add(nghttp3_qpack_decoder *decoder) { 3189 nghttp3_qpack_nv qnv; 3190 int rv; 3191 3192 DEBUGF("qpack::decode: Insert With Literal Name: name=%*s value=%*s\n", 3193 (int)decoder->rstate.name->len, decoder->rstate.name->base, 3194 (int)decoder->rstate.value->len, decoder->rstate.value->base); 3195 3196 if (table_space(decoder->rstate.name->len, decoder->rstate.value->len) > 3197 decoder->ctx.max_dtable_capacity) { 3198 return NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR; 3199 } 3200 3201 qnv.name = decoder->rstate.name; 3202 qnv.value = decoder->rstate.value; 3203 qnv.token = qpack_lookup_token(qnv.name->base, qnv.name->len); 3204 qnv.flags = NGHTTP3_NV_FLAG_NONE; 3205 3206 rv = nghttp3_qpack_context_dtable_add(&decoder->ctx, &qnv, NULL, 0); 3207 3208 nghttp3_rcbuf_decref(qnv.value); 3209 nghttp3_rcbuf_decref(qnv.name); 3210 3211 return rv; 3212} 3213 3214void nghttp3_qpack_decoder_set_max_concurrent_streams( 3215 nghttp3_qpack_decoder *decoder, size_t max_concurrent_streams) { 3216 decoder->max_concurrent_streams = 3217 nghttp3_max(decoder->max_concurrent_streams, max_concurrent_streams); 3218} 3219 3220void nghttp3_qpack_stream_context_init(nghttp3_qpack_stream_context *sctx, 3221 int64_t stream_id, 3222 const nghttp3_mem *mem) { 3223 nghttp3_qpack_read_state_reset(&sctx->rstate); 3224 3225 sctx->mem = mem; 3226 sctx->rstate.prefix = 8; 3227 sctx->state = NGHTTP3_QPACK_RS_STATE_RICNT; 3228 sctx->opcode = 0; 3229 sctx->stream_id = stream_id; 3230 sctx->ricnt = 0; 3231 sctx->dbase_sign = 0; 3232 sctx->base = 0; 3233} 3234 3235void nghttp3_qpack_stream_context_free(nghttp3_qpack_stream_context *sctx) { 3236 nghttp3_qpack_read_state_free(&sctx->rstate); 3237} 3238 3239void nghttp3_qpack_stream_context_reset(nghttp3_qpack_stream_context *sctx) { 3240 nghttp3_qpack_stream_context_init(sctx, sctx->stream_id, sctx->mem); 3241} 3242 3243uint64_t 3244nghttp3_qpack_stream_context_get_ricnt(nghttp3_qpack_stream_context *sctx) { 3245 return sctx->ricnt; 3246} 3247 3248nghttp3_ssize 3249nghttp3_qpack_decoder_read_request(nghttp3_qpack_decoder *decoder, 3250 nghttp3_qpack_stream_context *sctx, 3251 nghttp3_qpack_nv *nv, uint8_t *pflags, 3252 const uint8_t *src, size_t srclen, int fin) { 3253 const uint8_t *p = src, *end = src ? src + srclen : src; 3254 int rv; 3255 int busy = 0; 3256 nghttp3_ssize nread; 3257 int rfin; 3258 const nghttp3_mem *mem = decoder->ctx.mem; 3259 3260 if (decoder->ctx.bad) { 3261 return NGHTTP3_ERR_QPACK_FATAL; 3262 } 3263 3264 *pflags = NGHTTP3_QPACK_DECODE_FLAG_NONE; 3265 3266 for (; p != end || busy;) { 3267 busy = 0; 3268 switch (sctx->state) { 3269 case NGHTTP3_QPACK_RS_STATE_RICNT: 3270 nread = qpack_read_varint(&rfin, &sctx->rstate, p, end); 3271 if (nread < 0) { 3272 assert(NGHTTP3_ERR_QPACK_FATAL == nread); 3273 rv = NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; 3274 goto fail; 3275 } 3276 3277 p += nread; 3278 3279 if (!rfin) { 3280 goto almost_ok; 3281 } 3282 3283 rv = nghttp3_qpack_decoder_reconstruct_ricnt(decoder, &sctx->ricnt, 3284 sctx->rstate.left); 3285 if (rv != 0) { 3286 goto fail; 3287 } 3288 3289 sctx->state = NGHTTP3_QPACK_RS_STATE_DBASE_SIGN; 3290 break; 3291 case NGHTTP3_QPACK_RS_STATE_DBASE_SIGN: 3292 if ((*p) & 0x80) { 3293 sctx->dbase_sign = 1; 3294 } 3295 sctx->state = NGHTTP3_QPACK_RS_STATE_DBASE; 3296 sctx->rstate.left = 0; 3297 sctx->rstate.prefix = 7; 3298 sctx->rstate.shift = 0; 3299 /* Fall through */ 3300 case NGHTTP3_QPACK_RS_STATE_DBASE: 3301 nread = qpack_read_varint(&rfin, &sctx->rstate, p, end); 3302 if (nread < 0) { 3303 assert(NGHTTP3_ERR_QPACK_FATAL == nread); 3304 rv = NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; 3305 goto fail; 3306 } 3307 3308 p += nread; 3309 3310 if (!rfin) { 3311 goto almost_ok; 3312 } 3313 3314 if (sctx->dbase_sign) { 3315 if (sctx->ricnt <= sctx->rstate.left) { 3316 rv = NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; 3317 goto fail; 3318 } 3319 sctx->base = sctx->ricnt - sctx->rstate.left - 1; 3320 } else { 3321 sctx->base = sctx->ricnt + sctx->rstate.left; 3322 } 3323 3324 DEBUGF("qpack::decode: ricnt=%" PRIu64 " base=%" PRIu64 " icnt=%" PRIu64 3325 "\n", 3326 sctx->ricnt, sctx->base, decoder->ctx.next_absidx); 3327 3328 if (sctx->ricnt > decoder->ctx.next_absidx) { 3329 DEBUGF("qpack::decode: stream blocked\n"); 3330 sctx->state = NGHTTP3_QPACK_RS_STATE_BLOCKED; 3331 *pflags |= NGHTTP3_QPACK_DECODE_FLAG_BLOCKED; 3332 return p - src; 3333 } 3334 3335 sctx->state = NGHTTP3_QPACK_RS_STATE_OPCODE; 3336 sctx->rstate.left = 0; 3337 sctx->rstate.shift = 0; 3338 break; 3339 case NGHTTP3_QPACK_RS_STATE_OPCODE: 3340 assert(sctx->rstate.left == 0); 3341 assert(sctx->rstate.shift == 0); 3342 if ((*p) & 0x80) { 3343 DEBUGF("qpack::decode: OPCODE_INDEXED\n"); 3344 sctx->opcode = NGHTTP3_QPACK_RS_OPCODE_INDEXED; 3345 sctx->rstate.dynamic = !((*p) & 0x40); 3346 sctx->rstate.prefix = 6; 3347 sctx->state = NGHTTP3_QPACK_RS_STATE_READ_INDEX; 3348 } else if ((*p) & 0x40) { 3349 DEBUGF("qpack::decode: OPCODE_INDEXED_NAME\n"); 3350 sctx->opcode = NGHTTP3_QPACK_RS_OPCODE_INDEXED_NAME; 3351 sctx->rstate.never = (*p) & 0x20; 3352 sctx->rstate.dynamic = !((*p) & 0x10); 3353 sctx->rstate.prefix = 4; 3354 sctx->state = NGHTTP3_QPACK_RS_STATE_READ_INDEX; 3355 } else if ((*p) & 0x20) { 3356 DEBUGF("qpack::decode: OPCODE_LITERAL\n"); 3357 sctx->opcode = NGHTTP3_QPACK_RS_OPCODE_LITERAL; 3358 sctx->rstate.never = (*p) & 0x10; 3359 sctx->rstate.dynamic = 0; 3360 sctx->rstate.prefix = 3; 3361 sctx->state = NGHTTP3_QPACK_RS_STATE_CHECK_NAME_HUFFMAN; 3362 } else if ((*p) & 0x10) { 3363 DEBUGF("qpack::decode: OPCODE_INDEXED_PB\n"); 3364 sctx->opcode = NGHTTP3_QPACK_RS_OPCODE_INDEXED_PB; 3365 sctx->rstate.dynamic = 1; 3366 sctx->rstate.prefix = 4; 3367 sctx->state = NGHTTP3_QPACK_RS_STATE_READ_INDEX; 3368 } else { 3369 DEBUGF("qpack::decode: OPCODE_INDEXED_NAME_PB\n"); 3370 sctx->opcode = NGHTTP3_QPACK_RS_OPCODE_INDEXED_NAME_PB; 3371 sctx->rstate.never = (*p) & 0x08; 3372 sctx->rstate.dynamic = 1; 3373 sctx->rstate.prefix = 3; 3374 sctx->state = NGHTTP3_QPACK_RS_STATE_READ_INDEX; 3375 } 3376 break; 3377 case NGHTTP3_QPACK_RS_STATE_READ_INDEX: 3378 nread = qpack_read_varint(&rfin, &sctx->rstate, p, end); 3379 if (nread < 0) { 3380 assert(NGHTTP3_ERR_QPACK_FATAL == nread); 3381 rv = NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; 3382 goto fail; 3383 } 3384 3385 p += nread; 3386 3387 if (!rfin) { 3388 goto almost_ok; 3389 } 3390 3391 switch (sctx->opcode) { 3392 case NGHTTP3_QPACK_RS_OPCODE_INDEXED: 3393 rv = nghttp3_qpack_decoder_brel2abs(decoder, sctx); 3394 if (rv != 0) { 3395 goto fail; 3396 } 3397 nghttp3_qpack_decoder_emit_indexed(decoder, sctx, nv); 3398 *pflags |= NGHTTP3_QPACK_DECODE_FLAG_EMIT; 3399 3400 sctx->state = NGHTTP3_QPACK_RS_STATE_OPCODE; 3401 nghttp3_qpack_read_state_reset(&sctx->rstate); 3402 3403 return p - src; 3404 case NGHTTP3_QPACK_RS_OPCODE_INDEXED_PB: 3405 rv = nghttp3_qpack_decoder_pbrel2abs(decoder, sctx); 3406 if (rv != 0) { 3407 goto fail; 3408 } 3409 nghttp3_qpack_decoder_emit_indexed(decoder, sctx, nv); 3410 *pflags |= NGHTTP3_QPACK_DECODE_FLAG_EMIT; 3411 3412 sctx->state = NGHTTP3_QPACK_RS_STATE_OPCODE; 3413 nghttp3_qpack_read_state_reset(&sctx->rstate); 3414 3415 return p - src; 3416 case NGHTTP3_QPACK_RS_OPCODE_INDEXED_NAME: 3417 rv = nghttp3_qpack_decoder_brel2abs(decoder, sctx); 3418 if (rv != 0) { 3419 goto fail; 3420 } 3421 sctx->rstate.prefix = 7; 3422 sctx->state = NGHTTP3_QPACK_RS_STATE_CHECK_VALUE_HUFFMAN; 3423 break; 3424 case NGHTTP3_QPACK_RS_OPCODE_INDEXED_NAME_PB: 3425 rv = nghttp3_qpack_decoder_pbrel2abs(decoder, sctx); 3426 if (rv != 0) { 3427 goto fail; 3428 } 3429 sctx->rstate.prefix = 7; 3430 sctx->state = NGHTTP3_QPACK_RS_STATE_CHECK_VALUE_HUFFMAN; 3431 break; 3432 default: 3433 /* Unreachable */ 3434 assert(0); 3435 } 3436 break; 3437 case NGHTTP3_QPACK_RS_STATE_CHECK_NAME_HUFFMAN: 3438 qpack_read_state_check_huffman(&sctx->rstate, *p); 3439 sctx->state = NGHTTP3_QPACK_RS_STATE_READ_NAMELEN; 3440 sctx->rstate.left = 0; 3441 sctx->rstate.shift = 0; 3442 /* Fall through */ 3443 case NGHTTP3_QPACK_RS_STATE_READ_NAMELEN: 3444 nread = qpack_read_varint(&rfin, &sctx->rstate, p, end); 3445 if (nread < 0) { 3446 assert(NGHTTP3_ERR_QPACK_FATAL == nread); 3447 rv = NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; 3448 goto fail; 3449 } 3450 3451 p += nread; 3452 3453 if (!rfin) { 3454 goto almost_ok; 3455 } 3456 3457 if (sctx->rstate.left > NGHTTP3_QPACK_MAX_NAMELEN) { 3458 rv = NGHTTP3_ERR_QPACK_HEADER_TOO_LARGE; 3459 goto fail; 3460 } 3461 3462 if (sctx->rstate.huffman_encoded) { 3463 sctx->state = NGHTTP3_QPACK_RS_STATE_READ_NAME_HUFFMAN; 3464 nghttp3_qpack_huffman_decode_context_init(&sctx->rstate.huffman_ctx); 3465 rv = nghttp3_rcbuf_new(&sctx->rstate.name, 3466 (size_t)sctx->rstate.left * 2 + 1, mem); 3467 } else { 3468 sctx->state = NGHTTP3_QPACK_RS_STATE_READ_NAME; 3469 rv = nghttp3_rcbuf_new(&sctx->rstate.name, 3470 (size_t)sctx->rstate.left + 1, mem); 3471 } 3472 if (rv != 0) { 3473 goto fail; 3474 } 3475 3476 nghttp3_buf_wrap_init(&sctx->rstate.namebuf, sctx->rstate.name->base, 3477 sctx->rstate.name->len); 3478 break; 3479 case NGHTTP3_QPACK_RS_STATE_READ_NAME_HUFFMAN: 3480 nread = qpack_read_huffman_string(&sctx->rstate, &sctx->rstate.namebuf, p, 3481 end); 3482 if (nread < 0) { 3483 assert(NGHTTP3_ERR_QPACK_FATAL == nread); 3484 rv = NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; 3485 goto fail; 3486 } 3487 3488 p += nread; 3489 3490 if (sctx->rstate.left) { 3491 goto almost_ok; 3492 } 3493 3494 qpack_read_state_terminate_name(&sctx->rstate); 3495 3496 sctx->state = NGHTTP3_QPACK_RS_STATE_CHECK_VALUE_HUFFMAN; 3497 sctx->rstate.prefix = 7; 3498 break; 3499 case NGHTTP3_QPACK_RS_STATE_READ_NAME: 3500 nread = qpack_read_string(&sctx->rstate, &sctx->rstate.namebuf, p, end); 3501 if (nread < 0) { 3502 rv = (int)nread; 3503 goto fail; 3504 } 3505 3506 p += nread; 3507 3508 if (sctx->rstate.left) { 3509 goto almost_ok; 3510 } 3511 3512 qpack_read_state_terminate_name(&sctx->rstate); 3513 3514 sctx->state = NGHTTP3_QPACK_RS_STATE_CHECK_VALUE_HUFFMAN; 3515 sctx->rstate.prefix = 7; 3516 break; 3517 case NGHTTP3_QPACK_RS_STATE_CHECK_VALUE_HUFFMAN: 3518 qpack_read_state_check_huffman(&sctx->rstate, *p); 3519 sctx->state = NGHTTP3_QPACK_RS_STATE_READ_VALUELEN; 3520 sctx->rstate.left = 0; 3521 sctx->rstate.shift = 0; 3522 /* Fall through */ 3523 case NGHTTP3_QPACK_RS_STATE_READ_VALUELEN: 3524 nread = qpack_read_varint(&rfin, &sctx->rstate, p, end); 3525 if (nread < 0) { 3526 assert(NGHTTP3_ERR_QPACK_FATAL == nread); 3527 rv = NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; 3528 goto fail; 3529 } 3530 3531 p += nread; 3532 3533 if (!rfin) { 3534 goto almost_ok; 3535 } 3536 3537 if (sctx->rstate.left > NGHTTP3_QPACK_MAX_VALUELEN) { 3538 rv = NGHTTP3_ERR_QPACK_HEADER_TOO_LARGE; 3539 goto fail; 3540 } 3541 3542 if (sctx->rstate.huffman_encoded) { 3543 sctx->state = NGHTTP3_QPACK_RS_STATE_READ_VALUE_HUFFMAN; 3544 nghttp3_qpack_huffman_decode_context_init(&sctx->rstate.huffman_ctx); 3545 rv = nghttp3_rcbuf_new(&sctx->rstate.value, 3546 (size_t)sctx->rstate.left * 2 + 1, mem); 3547 } else { 3548 sctx->state = NGHTTP3_QPACK_RS_STATE_READ_VALUE; 3549 rv = nghttp3_rcbuf_new(&sctx->rstate.value, 3550 (size_t)sctx->rstate.left + 1, mem); 3551 } 3552 if (rv != 0) { 3553 goto fail; 3554 } 3555 3556 nghttp3_buf_wrap_init(&sctx->rstate.valuebuf, sctx->rstate.value->base, 3557 sctx->rstate.value->len); 3558 3559 /* value might be 0 length */ 3560 busy = 1; 3561 break; 3562 case NGHTTP3_QPACK_RS_STATE_READ_VALUE_HUFFMAN: 3563 nread = qpack_read_huffman_string(&sctx->rstate, &sctx->rstate.valuebuf, 3564 p, end); 3565 if (nread < 0) { 3566 assert(NGHTTP3_ERR_QPACK_FATAL == nread); 3567 rv = NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; 3568 goto fail; 3569 } 3570 3571 p += nread; 3572 3573 if (sctx->rstate.left) { 3574 goto almost_ok; 3575 } 3576 3577 qpack_read_state_terminate_value(&sctx->rstate); 3578 3579 switch (sctx->opcode) { 3580 case NGHTTP3_QPACK_RS_OPCODE_INDEXED_NAME: 3581 case NGHTTP3_QPACK_RS_OPCODE_INDEXED_NAME_PB: 3582 rv = nghttp3_qpack_decoder_emit_indexed_name(decoder, sctx, nv); 3583 if (rv != 0) { 3584 goto fail; 3585 } 3586 3587 break; 3588 case NGHTTP3_QPACK_RS_OPCODE_LITERAL: 3589 nghttp3_qpack_decoder_emit_literal(decoder, sctx, nv); 3590 break; 3591 default: 3592 /* Unreachable */ 3593 assert(0); 3594 } 3595 3596 *pflags |= NGHTTP3_QPACK_DECODE_FLAG_EMIT; 3597 3598 sctx->state = NGHTTP3_QPACK_RS_STATE_OPCODE; 3599 nghttp3_qpack_read_state_reset(&sctx->rstate); 3600 3601 return p - src; 3602 case NGHTTP3_QPACK_RS_STATE_READ_VALUE: 3603 nread = qpack_read_string(&sctx->rstate, &sctx->rstate.valuebuf, p, end); 3604 if (nread < 0) { 3605 rv = (int)nread; 3606 goto fail; 3607 } 3608 3609 p += nread; 3610 3611 if (sctx->rstate.left) { 3612 goto almost_ok; 3613 } 3614 3615 qpack_read_state_terminate_value(&sctx->rstate); 3616 3617 switch (sctx->opcode) { 3618 case NGHTTP3_QPACK_RS_OPCODE_INDEXED_NAME: 3619 case NGHTTP3_QPACK_RS_OPCODE_INDEXED_NAME_PB: 3620 rv = nghttp3_qpack_decoder_emit_indexed_name(decoder, sctx, nv); 3621 if (rv != 0) { 3622 goto fail; 3623 } 3624 3625 break; 3626 case NGHTTP3_QPACK_RS_OPCODE_LITERAL: 3627 nghttp3_qpack_decoder_emit_literal(decoder, sctx, nv); 3628 break; 3629 default: 3630 /* Unreachable */ 3631 assert(0); 3632 } 3633 3634 *pflags |= NGHTTP3_QPACK_DECODE_FLAG_EMIT; 3635 3636 sctx->state = NGHTTP3_QPACK_RS_STATE_OPCODE; 3637 nghttp3_qpack_read_state_reset(&sctx->rstate); 3638 3639 return p - src; 3640 case NGHTTP3_QPACK_RS_STATE_BLOCKED: 3641 if (sctx->ricnt > decoder->ctx.next_absidx) { 3642 DEBUGF("qpack::decode: stream still blocked\n"); 3643 *pflags |= NGHTTP3_QPACK_DECODE_FLAG_BLOCKED; 3644 return p - src; 3645 } 3646 sctx->state = NGHTTP3_QPACK_RS_STATE_OPCODE; 3647 nghttp3_qpack_read_state_reset(&sctx->rstate); 3648 break; 3649 } 3650 } 3651 3652almost_ok: 3653 if (fin) { 3654 if (sctx->state != NGHTTP3_QPACK_RS_STATE_OPCODE) { 3655 rv = NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; 3656 goto fail; 3657 } 3658 3659 *pflags |= NGHTTP3_QPACK_DECODE_FLAG_FINAL; 3660 3661 if (sctx->ricnt) { 3662 rv = nghttp3_qpack_decoder_write_section_ack(decoder, sctx); 3663 if (rv != 0) { 3664 goto fail; 3665 } 3666 } 3667 } 3668 3669 return p - src; 3670 3671fail: 3672 decoder->ctx.bad = 1; 3673 return rv; 3674} 3675 3676static int qpack_decoder_dbuf_overflow(nghttp3_qpack_decoder *decoder) { 3677 size_t limit = nghttp3_max(decoder->max_concurrent_streams, 100); 3678 /* 10 = nghttp3_qpack_put_varint_len((1ULL << 62) - 1, 2)) */ 3679 return nghttp3_buf_len(&decoder->dbuf) > limit * 2 * 10; 3680} 3681 3682int nghttp3_qpack_decoder_write_section_ack( 3683 nghttp3_qpack_decoder *decoder, const nghttp3_qpack_stream_context *sctx) { 3684 nghttp3_buf *dbuf = &decoder->dbuf; 3685 uint8_t *p; 3686 int rv; 3687 3688 if (qpack_decoder_dbuf_overflow(decoder)) { 3689 return NGHTTP3_ERR_QPACK_FATAL; 3690 } 3691 3692 rv = reserve_buf_small( 3693 dbuf, nghttp3_qpack_put_varint_len((uint64_t)sctx->stream_id, 7), 3694 decoder->ctx.mem); 3695 if (rv != 0) { 3696 return rv; 3697 } 3698 3699 p = dbuf->last; 3700 *p = 0x80; 3701 dbuf->last = nghttp3_qpack_put_varint(p, (uint64_t)sctx->stream_id, 7); 3702 3703 if (decoder->written_icnt < sctx->ricnt) { 3704 decoder->written_icnt = sctx->ricnt; 3705 } 3706 3707 return 0; 3708} 3709 3710size_t 3711nghttp3_qpack_decoder_get_decoder_streamlen(nghttp3_qpack_decoder *decoder) { 3712 uint64_t n; 3713 size_t len = 0; 3714 3715 if (decoder->written_icnt < decoder->ctx.next_absidx) { 3716 n = decoder->ctx.next_absidx - decoder->written_icnt; 3717 len = nghttp3_qpack_put_varint_len(n, 6); 3718 } 3719 3720 return nghttp3_buf_len(&decoder->dbuf) + len; 3721} 3722 3723void nghttp3_qpack_decoder_write_decoder(nghttp3_qpack_decoder *decoder, 3724 nghttp3_buf *dbuf) { 3725 uint8_t *p; 3726 uint64_t n = 0; 3727 size_t len = 0; 3728 (void)len; 3729 3730 if (decoder->written_icnt < decoder->ctx.next_absidx) { 3731 n = decoder->ctx.next_absidx - decoder->written_icnt; 3732 len = nghttp3_qpack_put_varint_len(n, 6); 3733 } 3734 3735 assert(nghttp3_buf_left(dbuf) >= nghttp3_buf_len(&decoder->dbuf) + len); 3736 3737 if (nghttp3_buf_len(&decoder->dbuf)) { 3738 dbuf->last = nghttp3_cpymem(dbuf->last, decoder->dbuf.pos, 3739 nghttp3_buf_len(&decoder->dbuf)); 3740 } 3741 3742 if (n) { 3743 p = dbuf->last; 3744 *p = 0; 3745 dbuf->last = nghttp3_qpack_put_varint(p, n, 6); 3746 3747 decoder->written_icnt = decoder->ctx.next_absidx; 3748 } 3749 3750 nghttp3_buf_reset(&decoder->dbuf); 3751} 3752 3753int nghttp3_qpack_decoder_cancel_stream(nghttp3_qpack_decoder *decoder, 3754 int64_t stream_id) { 3755 uint8_t *p; 3756 int rv; 3757 3758 if (qpack_decoder_dbuf_overflow(decoder)) { 3759 return NGHTTP3_ERR_QPACK_FATAL; 3760 } 3761 3762 rv = reserve_buf(&decoder->dbuf, 3763 nghttp3_qpack_put_varint_len((uint64_t)stream_id, 6), 3764 decoder->ctx.mem); 3765 if (rv != 0) { 3766 return rv; 3767 } 3768 3769 p = decoder->dbuf.last; 3770 *p = 0x40; 3771 decoder->dbuf.last = nghttp3_qpack_put_varint(p, (uint64_t)stream_id, 6); 3772 3773 return 0; 3774} 3775 3776int nghttp3_qpack_decoder_reconstruct_ricnt(nghttp3_qpack_decoder *decoder, 3777 uint64_t *dest, uint64_t encricnt) { 3778 uint64_t max_ents, full, max, max_wrapped, ricnt; 3779 3780 if (encricnt == 0) { 3781 *dest = 0; 3782 return 0; 3783 } 3784 3785 max_ents = 3786 decoder->ctx.hard_max_dtable_capacity / NGHTTP3_QPACK_ENTRY_OVERHEAD; 3787 full = 2 * max_ents; 3788 3789 if (encricnt > full) { 3790 return NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; 3791 } 3792 3793 max = decoder->ctx.next_absidx + max_ents; 3794 max_wrapped = max / full * full; 3795 ricnt = max_wrapped + encricnt - 1; 3796 3797 if (ricnt > max) { 3798 if (ricnt <= full) { 3799 return NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; 3800 } 3801 ricnt -= full; 3802 } 3803 3804 if (ricnt == 0) { 3805 return NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; 3806 } 3807 3808 *dest = ricnt; 3809 3810 return 0; 3811} 3812 3813int nghttp3_qpack_decoder_rel2abs(nghttp3_qpack_decoder *decoder, 3814 nghttp3_qpack_read_state *rstate) { 3815 DEBUGF("qpack::decode: dynamic=%d relidx=%" PRIu64 " icnt=%" PRIu64 "\n", 3816 rstate->dynamic, rstate->left, decoder->ctx.next_absidx); 3817 3818 if (rstate->dynamic) { 3819 if (decoder->ctx.next_absidx < rstate->left + 1) { 3820 return NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR; 3821 } 3822 rstate->absidx = decoder->ctx.next_absidx - rstate->left - 1; 3823 } else { 3824 rstate->absidx = rstate->left; 3825 } 3826 if (qpack_decoder_validate_index(decoder, rstate) != 0) { 3827 return NGHTTP3_ERR_QPACK_ENCODER_STREAM_ERROR; 3828 } 3829 return 0; 3830} 3831 3832int nghttp3_qpack_decoder_brel2abs(nghttp3_qpack_decoder *decoder, 3833 nghttp3_qpack_stream_context *sctx) { 3834 nghttp3_qpack_read_state *rstate = &sctx->rstate; 3835 3836 DEBUGF("qpack::decode: dynamic=%d relidx=%" PRIu64 " base=%" PRIu64 3837 " icnt=%" PRIu64 "\n", 3838 rstate->dynamic, rstate->left, sctx->base, decoder->ctx.next_absidx); 3839 3840 if (rstate->dynamic) { 3841 if (sctx->base < rstate->left + 1) { 3842 return NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; 3843 } 3844 rstate->absidx = sctx->base - rstate->left - 1; 3845 3846 if (rstate->absidx >= sctx->ricnt) { 3847 return NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; 3848 } 3849 } else { 3850 rstate->absidx = rstate->left; 3851 } 3852 3853 if (qpack_decoder_validate_index(decoder, rstate) != 0) { 3854 return NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; 3855 } 3856 return 0; 3857} 3858 3859int nghttp3_qpack_decoder_pbrel2abs(nghttp3_qpack_decoder *decoder, 3860 nghttp3_qpack_stream_context *sctx) { 3861 nghttp3_qpack_read_state *rstate = &sctx->rstate; 3862 3863 DEBUGF("qpack::decode: pbidx=%" PRIu64 " base=%" PRIu64 " icnt=%" PRIu64 "\n", 3864 rstate->left, sctx->base, decoder->ctx.next_absidx); 3865 3866 assert(rstate->dynamic); 3867 3868 rstate->absidx = rstate->left + sctx->base; 3869 3870 if (rstate->absidx >= sctx->ricnt) { 3871 return NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; 3872 } 3873 3874 if (qpack_decoder_validate_index(decoder, rstate) != 0) { 3875 return NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; 3876 } 3877 return 0; 3878} 3879 3880static void 3881qpack_decoder_emit_static_indexed(nghttp3_qpack_decoder *decoder, 3882 nghttp3_qpack_stream_context *sctx, 3883 nghttp3_qpack_nv *nv) { 3884 const nghttp3_qpack_static_header *shd = &stable[sctx->rstate.absidx]; 3885 (void)decoder; 3886 3887 nv->name = (nghttp3_rcbuf *)&shd->name; 3888 nv->value = (nghttp3_rcbuf *)&shd->value; 3889 nv->token = shd->token; 3890 nv->flags = NGHTTP3_NV_FLAG_NONE; 3891} 3892 3893static void 3894qpack_decoder_emit_dynamic_indexed(nghttp3_qpack_decoder *decoder, 3895 nghttp3_qpack_stream_context *sctx, 3896 nghttp3_qpack_nv *nv) { 3897 nghttp3_qpack_entry *ent = 3898 nghttp3_qpack_context_dtable_get(&decoder->ctx, sctx->rstate.absidx); 3899 3900 *nv = ent->nv; 3901 3902 nghttp3_rcbuf_incref(nv->name); 3903 nghttp3_rcbuf_incref(nv->value); 3904} 3905 3906void nghttp3_qpack_decoder_emit_indexed(nghttp3_qpack_decoder *decoder, 3907 nghttp3_qpack_stream_context *sctx, 3908 nghttp3_qpack_nv *nv) { 3909 DEBUGF("qpack::decode: Indexed (%s) absidx=%" PRIu64 "\n", 3910 sctx->rstate.dynamic ? "dynamic" : "static", sctx->rstate.absidx); 3911 3912 if (sctx->rstate.dynamic) { 3913 qpack_decoder_emit_dynamic_indexed(decoder, sctx, nv); 3914 } else { 3915 qpack_decoder_emit_static_indexed(decoder, sctx, nv); 3916 } 3917} 3918 3919static void 3920qpack_decoder_emit_static_indexed_name(nghttp3_qpack_decoder *decoder, 3921 nghttp3_qpack_stream_context *sctx, 3922 nghttp3_qpack_nv *nv) { 3923 const nghttp3_qpack_static_header *shd = &stable[sctx->rstate.absidx]; 3924 (void)decoder; 3925 3926 nv->name = (nghttp3_rcbuf *)&shd->name; 3927 nv->value = sctx->rstate.value; 3928 nv->token = shd->token; 3929 nv->flags = 3930 sctx->rstate.never ? NGHTTP3_NV_FLAG_NEVER_INDEX : NGHTTP3_NV_FLAG_NONE; 3931 3932 sctx->rstate.value = NULL; 3933} 3934 3935static int 3936qpack_decoder_emit_dynamic_indexed_name(nghttp3_qpack_decoder *decoder, 3937 nghttp3_qpack_stream_context *sctx, 3938 nghttp3_qpack_nv *nv) { 3939 nghttp3_qpack_entry *ent; 3940 3941 /* A broken encoder might change dtable capacity while processing 3942 request stream instruction. Check the absidx again. */ 3943 if (qpack_decoder_validate_index(decoder, &sctx->rstate) != 0) { 3944 return NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED; 3945 } 3946 3947 ent = nghttp3_qpack_context_dtable_get(&decoder->ctx, sctx->rstate.absidx); 3948 3949 nv->name = ent->nv.name; 3950 nv->value = sctx->rstate.value; 3951 nv->token = ent->nv.token; 3952 nv->flags = 3953 sctx->rstate.never ? NGHTTP3_NV_FLAG_NEVER_INDEX : NGHTTP3_NV_FLAG_NONE; 3954 3955 nghttp3_rcbuf_incref(nv->name); 3956 3957 sctx->rstate.value = NULL; 3958 3959 return 0; 3960} 3961 3962int nghttp3_qpack_decoder_emit_indexed_name(nghttp3_qpack_decoder *decoder, 3963 nghttp3_qpack_stream_context *sctx, 3964 nghttp3_qpack_nv *nv) { 3965 (void)decoder; 3966 3967 DEBUGF("qpack::decode: Indexed name (%s) absidx=%" PRIu64 " value=%*s\n", 3968 sctx->rstate.dynamic ? "dynamic" : "static", sctx->rstate.absidx, 3969 (int)sctx->rstate.value->len, sctx->rstate.value->base); 3970 3971 if (sctx->rstate.dynamic) { 3972 return qpack_decoder_emit_dynamic_indexed_name(decoder, sctx, nv); 3973 } 3974 3975 qpack_decoder_emit_static_indexed_name(decoder, sctx, nv); 3976 3977 return 0; 3978} 3979 3980void nghttp3_qpack_decoder_emit_literal(nghttp3_qpack_decoder *decoder, 3981 nghttp3_qpack_stream_context *sctx, 3982 nghttp3_qpack_nv *nv) { 3983 (void)decoder; 3984 3985 DEBUGF("qpack::decode: Emit literal name=%*s value=%*s\n", 3986 (int)sctx->rstate.name->len, sctx->rstate.name->base, 3987 (int)sctx->rstate.value->len, sctx->rstate.value->base); 3988 3989 nv->name = sctx->rstate.name; 3990 nv->value = sctx->rstate.value; 3991 nv->token = qpack_lookup_token(nv->name->base, nv->name->len); 3992 nv->flags = 3993 sctx->rstate.never ? NGHTTP3_NV_FLAG_NEVER_INDEX : NGHTTP3_NV_FLAG_NONE; 3994 3995 sctx->rstate.name = NULL; 3996 sctx->rstate.value = NULL; 3997} 3998 3999int nghttp3_qpack_encoder_new(nghttp3_qpack_encoder **pencoder, 4000 size_t hard_max_dtable_capacity, 4001 const nghttp3_mem *mem) { 4002 int rv; 4003 nghttp3_qpack_encoder *p; 4004 4005 p = nghttp3_mem_malloc(mem, sizeof(nghttp3_qpack_encoder)); 4006 if (p == NULL) { 4007 return NGHTTP3_ERR_NOMEM; 4008 } 4009 4010 rv = nghttp3_qpack_encoder_init(p, hard_max_dtable_capacity, mem); 4011 if (rv != 0) { 4012 return rv; 4013 } 4014 4015 *pencoder = p; 4016 4017 return 0; 4018} 4019 4020void nghttp3_qpack_encoder_del(nghttp3_qpack_encoder *encoder) { 4021 const nghttp3_mem *mem; 4022 4023 if (encoder == NULL) { 4024 return; 4025 } 4026 4027 mem = encoder->ctx.mem; 4028 4029 nghttp3_qpack_encoder_free(encoder); 4030 nghttp3_mem_free(mem, encoder); 4031} 4032 4033int nghttp3_qpack_stream_context_new(nghttp3_qpack_stream_context **psctx, 4034 int64_t stream_id, 4035 const nghttp3_mem *mem) { 4036 nghttp3_qpack_stream_context *p; 4037 4038 p = nghttp3_mem_malloc(mem, sizeof(nghttp3_qpack_stream_context)); 4039 if (p == NULL) { 4040 return NGHTTP3_ERR_NOMEM; 4041 } 4042 4043 nghttp3_qpack_stream_context_init(p, stream_id, mem); 4044 4045 *psctx = p; 4046 4047 return 0; 4048} 4049 4050void nghttp3_qpack_stream_context_del(nghttp3_qpack_stream_context *sctx) { 4051 const nghttp3_mem *mem; 4052 4053 if (sctx == NULL) { 4054 return; 4055 } 4056 4057 mem = sctx->mem; 4058 4059 nghttp3_qpack_stream_context_free(sctx); 4060 nghttp3_mem_free(mem, sctx); 4061} 4062 4063int nghttp3_qpack_decoder_new(nghttp3_qpack_decoder **pdecoder, 4064 size_t hard_max_dtable_capacity, 4065 size_t max_blocked_streams, 4066 const nghttp3_mem *mem) { 4067 int rv; 4068 nghttp3_qpack_decoder *p; 4069 4070 p = nghttp3_mem_malloc(mem, sizeof(nghttp3_qpack_decoder)); 4071 if (p == NULL) { 4072 return NGHTTP3_ERR_NOMEM; 4073 } 4074 4075 rv = nghttp3_qpack_decoder_init(p, hard_max_dtable_capacity, 4076 max_blocked_streams, mem); 4077 if (rv != 0) { 4078 return rv; 4079 } 4080 4081 *pdecoder = p; 4082 4083 return 0; 4084} 4085 4086void nghttp3_qpack_decoder_del(nghttp3_qpack_decoder *decoder) { 4087 const nghttp3_mem *mem; 4088 4089 if (decoder == NULL) { 4090 return; 4091 } 4092 4093 mem = decoder->ctx.mem; 4094 4095 nghttp3_qpack_decoder_free(decoder); 4096 nghttp3_mem_free(mem, decoder); 4097} 4098 4099uint64_t nghttp3_qpack_decoder_get_icnt(const nghttp3_qpack_decoder *decoder) { 4100 return decoder->ctx.next_absidx; 4101} 4102