Line data Source code
1 : // SPDX-License-Identifier: GPL-2.0-or-later
2 : /* QUIC kernel implementation
3 : * (C) Copyright Red Hat Corp. 2023
4 : *
5 : * This file is part of the QUIC kernel implementation
6 : *
7 : * Initialization/cleanup for QUIC protocol support.
8 : *
9 : * Written or modified by:
10 : * Xin Long <lucien.xin@gmail.com>
11 : */
12 :
13 : #include "common.h"
14 :
15 : #define QUIC_VARINT_1BYTE_MAX 0x3fULL
16 : #define QUIC_VARINT_2BYTE_MAX 0x3fffULL
17 : #define QUIC_VARINT_4BYTE_MAX 0x3fffffffULL
18 :
19 : #define QUIC_VARINT_2BYTE_PREFIX 0x40
20 : #define QUIC_VARINT_4BYTE_PREFIX 0x80
21 : #define QUIC_VARINT_8BYTE_PREFIX 0xc0
22 :
23 : #define QUIC_VARINT_LENGTH(p) BIT((*(p)) >> 6)
24 : #define QUIC_VARINT_VALUE_MASK 0x3f
25 :
26 : static struct quic_hash_table quic_hash_tables[QUIC_HT_MAX_TABLES];
27 :
28 1536 : struct quic_hash_head *quic_sock_hash(u32 hash)
29 : {
30 1536 : return &quic_hash_tables[QUIC_HT_SOCK].hash[hash];
31 : }
32 :
33 6362 : struct quic_hash_head *quic_sock_head(struct net *net, union quic_addr *s, union quic_addr *d)
34 : {
35 6362 : struct quic_hash_table *ht = &quic_hash_tables[QUIC_HT_SOCK];
36 :
37 6362 : return &ht->hash[quic_ahash(net, s, d) & (ht->size - 1)];
38 : }
39 :
40 1331 : struct quic_hash_head *quic_listen_sock_head(struct net *net, u16 port)
41 : {
42 1331 : struct quic_hash_table *ht = &quic_hash_tables[QUIC_HT_LISTEN_SOCK];
43 :
44 1331 : return &ht->hash[port & (ht->size - 1)];
45 : }
46 :
47 6587223 : struct quic_hash_head *quic_source_conn_id_head(struct net *net, u8 *scid)
48 : {
49 6587223 : struct quic_hash_table *ht = &quic_hash_tables[QUIC_HT_CONNECTION_ID];
50 :
51 6587223 : return &ht->hash[jhash(scid, 4, 0) & (ht->size - 1)];
52 : }
53 :
54 3883 : struct quic_hash_head *quic_udp_sock_head(struct net *net, u16 port)
55 : {
56 3883 : struct quic_hash_table *ht = &quic_hash_tables[QUIC_HT_UDP_SOCK];
57 :
58 3883 : return &ht->hash[port & (ht->size - 1)];
59 : }
60 :
61 8630162 : struct quic_hash_head *quic_stream_head(struct quic_hash_table *ht, s64 stream_id)
62 : {
63 8630162 : return &ht->hash[stream_id & (ht->size - 1)];
64 : }
65 :
66 0 : void quic_hash_tables_destroy(void)
67 : {
68 0 : struct quic_hash_table *ht;
69 0 : int table;
70 :
71 0 : for (table = 0; table < QUIC_HT_MAX_TABLES; table++) {
72 0 : ht = &quic_hash_tables[table];
73 0 : ht->size = QUIC_HT_SIZE;
74 0 : kfree(ht->hash);
75 : }
76 0 : }
77 :
78 1 : int quic_hash_tables_init(void)
79 : {
80 1 : struct quic_hash_head *head;
81 1 : struct quic_hash_table *ht;
82 1 : int table, i;
83 :
84 5 : for (table = 0; table < QUIC_HT_MAX_TABLES; table++) {
85 4 : ht = &quic_hash_tables[table];
86 4 : ht->size = QUIC_HT_SIZE;
87 4 : head = kmalloc_array(ht->size, sizeof(*head), GFP_KERNEL);
88 4 : if (!head) {
89 0 : quic_hash_tables_destroy();
90 0 : return -ENOMEM;
91 : }
92 260 : for (i = 0; i < ht->size; i++) {
93 256 : INIT_HLIST_HEAD(&head[i].head);
94 256 : if (table == QUIC_HT_UDP_SOCK) {
95 64 : mutex_init(&head[i].m_lock);
96 64 : continue;
97 : }
98 256 : spin_lock_init(&head[i].s_lock);
99 : }
100 4 : ht->hash = head;
101 : }
102 :
103 : return 0;
104 : }
105 :
106 : union quic_var {
107 : u8 u8;
108 : __be16 be16;
109 : __be32 be32;
110 : __be64 be64;
111 : };
112 :
113 : /* Returns the number of bytes required to encode a QUIC variable-length integer. */
114 32256039 : u8 quic_var_len(u64 n)
115 : {
116 32247183 : if (n <= QUIC_VARINT_1BYTE_MAX)
117 : return 1;
118 21275079 : if (n <= QUIC_VARINT_2BYTE_MAX)
119 : return 2;
120 10421571 : if (n <= QUIC_VARINT_4BYTE_MAX)
121 10412645 : return 4;
122 : return 8;
123 : }
124 :
125 : /* Decodes a QUIC variable-length integer from a buffer. */
126 22169476 : u8 quic_get_var(u8 **pp, u32 *plen, u64 *val)
127 : {
128 22169476 : union quic_var n = {};
129 22169476 : u8 *p = *pp, len;
130 22169476 : u64 v = 0;
131 :
132 22169476 : if (!*plen)
133 : return 0;
134 :
135 22169476 : len = QUIC_VARINT_LENGTH(p);
136 22169476 : if (*plen < len)
137 : return 0;
138 :
139 22169476 : switch (len) {
140 8188079 : case 1:
141 8188079 : v = *p;
142 8188079 : break;
143 7103296 : case 2:
144 7103296 : memcpy(&n.be16, p, 2);
145 7103296 : n.u8 &= QUIC_VARINT_VALUE_MASK;
146 7103296 : v = be16_to_cpu(n.be16);
147 7103296 : break;
148 6877273 : case 4:
149 6877273 : memcpy(&n.be32, p, 4);
150 6877273 : n.u8 &= QUIC_VARINT_VALUE_MASK;
151 6877273 : v = be32_to_cpu(n.be32);
152 6877273 : break;
153 828 : case 8:
154 828 : memcpy(&n.be64, p, 8);
155 828 : n.u8 &= QUIC_VARINT_VALUE_MASK;
156 828 : v = be64_to_cpu(n.be64);
157 828 : break;
158 : default:
159 : return 0;
160 : }
161 :
162 22169476 : *plen -= len;
163 22169476 : *pp = p + len;
164 22169476 : *val = v;
165 22169476 : return len;
166 : }
167 :
168 : /* Reads a fixed-length integer from the buffer. */
169 6610889 : u32 quic_get_int(u8 **pp, u32 *plen, u64 *val, u32 len)
170 : {
171 6610889 : union quic_var n;
172 6610889 : u8 *p = *pp;
173 6610889 : u64 v = 0;
174 :
175 6610889 : if (*plen < len)
176 : return 0;
177 6610889 : *plen -= len;
178 :
179 6610889 : switch (len) {
180 144039 : case 1:
181 144039 : v = *p;
182 144039 : break;
183 7571 : case 2:
184 7571 : memcpy(&n.be16, p, 2);
185 7571 : v = be16_to_cpu(n.be16);
186 7571 : break;
187 907 : case 3:
188 907 : n.be32 = 0;
189 907 : memcpy(((u8 *)&n.be32) + 1, p, 3);
190 907 : v = be32_to_cpu(n.be32);
191 907 : break;
192 6458372 : case 4:
193 6458372 : memcpy(&n.be32, p, 4);
194 6458372 : v = be32_to_cpu(n.be32);
195 6458372 : break;
196 0 : case 8:
197 0 : memcpy(&n.be64, p, 8);
198 0 : v = be64_to_cpu(n.be64);
199 0 : break;
200 : default:
201 : return 0;
202 : }
203 6610889 : *pp = p + len;
204 6610889 : *val = v;
205 6610889 : return len;
206 : }
207 :
208 56 : u32 quic_get_data(u8 **pp, u32 *plen, u8 *data, u32 len)
209 : {
210 56 : if (*plen < len)
211 : return 0;
212 :
213 112 : memcpy(data, *pp, len);
214 56 : *pp += len;
215 56 : *plen -= len;
216 :
217 56 : return len;
218 : }
219 :
220 : /* Encodes a value into the QUIC variable-length integer format. */
221 37207030 : u8 *quic_put_var(u8 *p, u64 num)
222 : {
223 37207030 : union quic_var n;
224 :
225 37207030 : if (num <= QUIC_VARINT_1BYTE_MAX) {
226 19406304 : *p++ = (u8)(num & 0xff);
227 19406304 : return p;
228 : }
229 17800726 : if (num <= QUIC_VARINT_2BYTE_MAX) {
230 9004566 : n.be16 = cpu_to_be16((u16)num);
231 9004566 : *((__be16 *)p) = n.be16;
232 9004566 : *p |= QUIC_VARINT_2BYTE_PREFIX;
233 9004566 : return p + 2;
234 : }
235 8796160 : if (num <= QUIC_VARINT_4BYTE_MAX) {
236 8787000 : n.be32 = cpu_to_be32((u32)num);
237 8787000 : *((__be32 *)p) = n.be32;
238 8787000 : *p |= QUIC_VARINT_4BYTE_PREFIX;
239 8787000 : return p + 4;
240 : }
241 9160 : n.be64 = cpu_to_be64(num);
242 9160 : *((__be64 *)p) = n.be64;
243 9160 : *p |= QUIC_VARINT_8BYTE_PREFIX;
244 9160 : return p + 8;
245 : }
246 :
247 : /* Writes a fixed-length integer to the buffer in network byte order. */
248 6577159 : u8 *quic_put_int(u8 *p, u64 num, u8 len)
249 : {
250 6577159 : union quic_var n;
251 :
252 6577159 : switch (len) {
253 12106 : case 1:
254 12106 : *p++ = (u8)(num & 0xff);
255 12106 : return p;
256 0 : case 2:
257 0 : n.be16 = cpu_to_be16((u16)(num & 0xffff));
258 0 : *((__be16 *)p) = n.be16;
259 0 : return p + 2;
260 6565053 : case 4:
261 6565053 : n.be32 = cpu_to_be32((u32)num);
262 6565053 : *((__be32 *)p) = n.be32;
263 6565053 : return p + 4;
264 : default:
265 : return NULL;
266 : }
267 : }
268 :
269 : /* Encodes a value as a variable-length integer with explicit length. */
270 5583 : u8 *quic_put_varint(u8 *p, u64 num, u8 len)
271 : {
272 5583 : union quic_var n;
273 :
274 5583 : switch (len) {
275 0 : case 1:
276 0 : *p++ = (u8)(num & 0xff);
277 0 : return p;
278 0 : case 2:
279 0 : n.be16 = cpu_to_be16((u16)(num & 0xffff));
280 0 : *((__be16 *)p) = n.be16;
281 0 : *p |= QUIC_VARINT_2BYTE_PREFIX;
282 0 : return p + 2;
283 5583 : case 4:
284 5583 : n.be32 = cpu_to_be32((u32)num);
285 5583 : *((__be32 *)p) = n.be32;
286 5583 : *p |= QUIC_VARINT_4BYTE_PREFIX;
287 5583 : return p + 4;
288 : default:
289 : return NULL;
290 : }
291 : }
292 :
293 22043437 : u8 *quic_put_data(u8 *p, u8 *data, u32 len)
294 : {
295 22043437 : if (!len)
296 : return p;
297 :
298 43880996 : memcpy(p, data, len);
299 21940498 : return p + len;
300 : }
301 :
302 : /* Writes a transport parameter as two varints: ID and value length, followed by value. */
303 8856 : u8 *quic_put_param(u8 *p, u16 id, u64 value)
304 : {
305 8856 : p = quic_put_var(p, id);
306 15871 : p = quic_put_var(p, quic_var_len(value));
307 8856 : return quic_put_var(p, value);
308 : }
309 :
310 : /* Reads a QUIC transport parameter value. */
311 8459 : u8 quic_get_param(u64 *pdest, u8 **pp, u32 *plen)
312 : {
313 8459 : u64 valuelen;
314 :
315 8459 : if (!quic_get_var(pp, plen, &valuelen))
316 : return 0;
317 :
318 8459 : if (*plen < valuelen)
319 : return 0;
320 :
321 8459 : if (!quic_get_var(pp, plen, pdest))
322 : return 0;
323 :
324 8459 : return (u8)valuelen;
325 : }
326 :
327 : /* rfc9000#section-a.3: DecodePacketNumber()
328 : *
329 : * Reconstructs the full packet number from a truncated one.
330 : */
331 6575216 : s64 quic_get_num(s64 max_pkt_num, s64 pkt_num, u32 n)
332 : {
333 6575216 : s64 expected = max_pkt_num + 1;
334 6575216 : s64 win = BIT_ULL(n * 8);
335 6575216 : s64 hwin = win / 2;
336 6575216 : s64 mask = win - 1;
337 6575216 : s64 cand;
338 :
339 6575216 : cand = (expected & ~mask) | pkt_num;
340 6575216 : if (cand <= expected - hwin && cand < (1ULL << 62) - win)
341 7 : return cand + win;
342 6575209 : if (cand > expected + hwin && cand >= win)
343 0 : return cand - win;
344 : return cand;
345 : }
346 :
347 897 : int quic_data_dup(struct quic_data *to, u8 *data, u32 len)
348 : {
349 897 : if (!len)
350 : return 0;
351 :
352 887 : data = kmemdup(data, len, GFP_ATOMIC);
353 887 : if (!data)
354 : return -ENOMEM;
355 :
356 887 : kfree(to->data);
357 887 : to->data = data;
358 887 : to->len = len;
359 887 : return 0;
360 : }
361 :
362 471 : int quic_data_append(struct quic_data *to, u8 *data, u32 len)
363 : {
364 471 : u8 *p;
365 :
366 471 : if (!len)
367 : return 0;
368 :
369 471 : p = kzalloc(to->len + len, GFP_ATOMIC);
370 471 : if (!p)
371 : return -ENOMEM;
372 471 : p = quic_put_data(p, to->data, to->len);
373 471 : p = quic_put_data(p, data, len);
374 :
375 471 : kfree(to->data);
376 471 : to->len = to->len + len;
377 471 : to->data = p - to->len;
378 471 : return 0;
379 : }
380 :
381 : /* Check whether 'd2' is equal to any element inside the list 'd1'.
382 : *
383 : * 'd1' is assumed to be a sequence of length-prefixed elements. Each element
384 : * is compared to 'd2' using 'quic_data_cmp()'.
385 : *
386 : * Returns 1 if a match is found, 0 otherwise.
387 : */
388 362 : int quic_data_has(struct quic_data *d1, struct quic_data *d2)
389 : {
390 362 : struct quic_data d;
391 362 : u64 length;
392 362 : u32 len;
393 362 : u8 *p;
394 :
395 386 : for (p = d1->data, len = d1->len; len; len -= length, p += length) {
396 386 : quic_get_int(&p, &len, &length, 1);
397 386 : quic_data(&d, p, length);
398 386 : if (!quic_data_cmp(&d, d2))
399 : return 1;
400 : }
401 : return 0;
402 : }
403 :
404 : /* Check if any element of 'd1' is present in the list 'd2'.
405 : *
406 : * Iterates through each element in 'd1', and uses 'quic_data_has()' to check
407 : * for its presence in 'd2'.
408 : *
409 : * Returns 1 if any match is found, 0 otherwise.
410 : */
411 0 : int quic_data_match(struct quic_data *d1, struct quic_data *d2)
412 : {
413 0 : struct quic_data d;
414 0 : u64 length;
415 0 : u32 len;
416 0 : u8 *p;
417 :
418 0 : for (p = d1->data, len = d1->len; len; len -= length, p += length) {
419 0 : quic_get_int(&p, &len, &length, 1);
420 0 : quic_data(&d, p, length);
421 0 : if (quic_data_has(d2, &d))
422 : return 1;
423 : }
424 : return 0;
425 : }
426 :
427 : /* Serialize a list of 'quic_data' elements into a comma-separated string.
428 : *
429 : * Each element in 'from' is length-prefixed. This function copies their raw
430 : * content into the output buffer 'to', inserting commas in between. The
431 : * resulting string length is written to '*plen'.
432 : */
433 16 : void quic_data_to_string(u8 *to, u32 *plen, struct quic_data *from)
434 : {
435 16 : struct quic_data d;
436 16 : u8 *data = to, *p;
437 16 : u64 length;
438 16 : u32 len;
439 :
440 32 : for (p = from->data, len = from->len; len; len -= length, p += length) {
441 16 : quic_get_int(&p, &len, &length, 1);
442 16 : quic_data(&d, p, length);
443 16 : data = quic_put_data(data, d.data, d.len);
444 16 : if (len - length)
445 0 : data = quic_put_int(data, ',', 1);
446 : }
447 16 : *plen = data - to;
448 16 : }
449 :
450 : /* Parse a comma-separated string into a 'quic_data' list format.
451 : *
452 : * Each comma-separated token is turned into a length-prefixed element. The
453 : * first byte of each element stores the length (minus one). Elements are
454 : * stored in 'to->data', and 'to->len' is updated.
455 : */
456 126 : void quic_data_from_string(struct quic_data *to, u8 *from, u32 len)
457 : {
458 126 : struct quic_data d;
459 126 : u8 *p = to->data;
460 :
461 126 : to->len = 0;
462 270 : while (len) {
463 144 : d.data = p++;
464 144 : d.len = 1;
465 162 : while (len && *from == ' ') {
466 18 : from++;
467 18 : len--;
468 : }
469 1214 : while (len) {
470 1088 : if (*from == ',') {
471 18 : from++;
472 18 : len--;
473 18 : break;
474 : }
475 1070 : *p++ = *from++;
476 1070 : len--;
477 1070 : d.len++;
478 : }
479 144 : *d.data = (u8)(d.len - 1);
480 144 : to->len += d.len;
481 : }
482 126 : }
|
