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 <linux/slab.h>
14 :
15 : #include "pnspace.h"
16 :
17 3357 : int quic_pnspace_init(struct quic_pnspace *space)
18 : {
19 3357 : if (!space->pn_map) {
20 3357 : space->pn_map = kzalloc(BITS_TO_BYTES(QUIC_PN_MAP_INITIAL), GFP_KERNEL);
21 3357 : if (!space->pn_map)
22 : return -ENOMEM;
23 3357 : space->pn_map_len = QUIC_PN_MAP_INITIAL;
24 : } else {
25 0 : bitmap_zero(space->pn_map, space->pn_map_len);
26 : }
27 :
28 3357 : space->max_time_limit = QUIC_PNSPACE_TIME_LIMIT;
29 3357 : space->next_pn = QUIC_PNSPACE_NEXT_PN;
30 3357 : space->base_pn = -1;
31 3357 : return 0;
32 : }
33 :
34 3354 : void quic_pnspace_free(struct quic_pnspace *space)
35 : {
36 3354 : space->pn_map_len = 0;
37 3354 : kfree(space->pn_map);
38 3354 : }
39 :
40 : /* Expand the bitmap tracking received packet numbers. Ensures the pn_map bitmap can
41 : * cover at least @size packet numbers. Allocates a larger bitmap, copies existing
42 : * data, and updates metadata.
43 : *
44 : * Returns: 1 if the bitmap was successfully grown, 0 on failure or if the requested
45 : * size exceeds QUIC_PN_MAP_SIZE.
46 : */
47 144 : static int quic_pnspace_grow(struct quic_pnspace *space, u16 size)
48 : {
49 144 : u16 len, inc, offset;
50 144 : unsigned long *new;
51 :
52 144 : if (size > QUIC_PN_MAP_SIZE)
53 : return 0;
54 :
55 144 : inc = ALIGN((size - space->pn_map_len), BITS_PER_LONG) + QUIC_PN_MAP_INCREMENT;
56 144 : len = (u16)min(space->pn_map_len + inc, QUIC_PN_MAP_SIZE);
57 :
58 144 : new = kzalloc(BITS_TO_BYTES(len), GFP_ATOMIC);
59 144 : if (!new)
60 : return 0;
61 :
62 144 : offset = (u16)(space->max_pn_seen + 1 - space->base_pn);
63 144 : bitmap_copy(new, space->pn_map, offset);
64 144 : kfree(space->pn_map);
65 144 : space->pn_map = new;
66 144 : space->pn_map_len = len;
67 :
68 144 : return 1;
69 : }
70 :
71 : /* Check if a packet number has been received.
72 : *
73 : * Returns: 0 if the packet number has not been received. 1 if it has already
74 : * been received. -1 if the packet number is too old or too far in the future
75 : * to track.
76 : */
77 6574707 : int quic_pnspace_check(struct quic_pnspace *space, s64 pn)
78 : {
79 6574707 : if (space->base_pn == -1) /* No any packet number received yet. */
80 : return 0;
81 :
82 6571727 : if (pn < space->min_pn_seen || pn >= space->base_pn + QUIC_PN_MAP_SIZE)
83 : return -1;
84 :
85 6571727 : if (pn < space->base_pn || (pn - space->base_pn < space->pn_map_len &&
86 13143200 : test_bit(pn - space->base_pn, space->pn_map)))
87 0 : return 1;
88 :
89 : return 0;
90 : }
91 :
92 : /* Advance base_pn past contiguous received packet numbers. Finds the next gap
93 : * (unreceived packet) beyond @pn, shifts the bitmap, and updates base_pn
94 : * accordingly.
95 : */
96 6490043 : static void quic_pnspace_move(struct quic_pnspace *space, s64 pn)
97 : {
98 6490043 : u16 offset;
99 :
100 6490043 : offset = (u16)(pn + 1 - space->base_pn);
101 6490043 : offset = (u16)find_next_zero_bit(space->pn_map, space->pn_map_len, offset);
102 6490040 : space->base_pn += offset;
103 6490040 : bitmap_shift_right(space->pn_map, space->pn_map, offset, space->pn_map_len);
104 6489999 : }
105 :
106 : /* Mark a packet number as received. Updates the packet number map to record
107 : * reception of @pn. Advances base_pn if possible, and updates max/min/last seen
108 : * fields as needed.
109 : *
110 : * Returns: 0 on success or if the packet was already marked. -ENOMEM if bitmap
111 : * allocation failed during growth.
112 : */
113 6575154 : int quic_pnspace_mark(struct quic_pnspace *space, s64 pn)
114 : {
115 6575154 : s64 last_max_pn_seen;
116 6575154 : u16 gap;
117 :
118 6575154 : if (space->base_pn == -1) {
119 : /* Initialize base_pn based on the peer's first packet number since peer's
120 : * packet numbers may start at a non-zero value.
121 : */
122 2980 : quic_pnspace_set_base_pn(space, pn + 1);
123 2980 : return 0;
124 : }
125 :
126 : /* Ignore packets with number less than current base (already processed). */
127 6572174 : if (pn < space->base_pn)
128 : return 0;
129 :
130 : /* If gap is beyond current map length, try to grow the bitmap to accommodate. */
131 6572174 : gap = (u16)(pn - space->base_pn);
132 6572174 : if (gap >= space->pn_map_len && !quic_pnspace_grow(space, gap + 1))
133 : return -ENOMEM;
134 :
135 6572174 : if (space->max_pn_seen < pn) {
136 6570929 : space->max_pn_seen = pn;
137 6570929 : space->max_pn_time = space->time;
138 : }
139 :
140 6572174 : if (space->base_pn == pn) { /* If packet is exactly at base_pn (next expected packet). */
141 6489084 : if (quic_pnspace_has_gap(space)) /* Advance base_pn to next unacked packet. */
142 6489084 : quic_pnspace_move(space, pn);
143 : else /* Fast path: increment base_pn if no gaps. */
144 0 : space->base_pn++;
145 : } else { /* Mark this packet as received in the bitmap. */
146 83090 : set_bit(gap, space->pn_map);
147 : }
148 :
149 : /* Only update min and last_max_pn_seen if this packet is the current max_pn. */
150 6572122 : if (space->max_pn_seen != pn)
151 : return 0;
152 :
153 : /* Check if enough time has elapsed or enough packets have been received to
154 : * update tracking.
155 : */
156 6570878 : last_max_pn_seen = min_t(s64, space->last_max_pn_seen, space->base_pn);
157 6570878 : if (space->max_pn_time < space->last_max_pn_time + space->max_time_limit &&
158 6565744 : space->max_pn_seen <= last_max_pn_seen + QUIC_PN_MAP_LIMIT)
159 : return 0;
160 :
161 : /* Advance base_pn if last_max_pn_seen is ahead of current base_pn. This is
162 : * needed because QUIC doesn't retransmit packets; retransmitted frames are
163 : * carried in new packets, so we move forward.
164 : */
165 7141 : if (space->last_max_pn_seen + 1 > space->base_pn)
166 959 : quic_pnspace_move(space, space->last_max_pn_seen);
167 :
168 7141 : space->min_pn_seen = space->last_max_pn_seen;
169 7141 : space->last_max_pn_seen = space->max_pn_seen;
170 7141 : space->last_max_pn_time = space->max_pn_time;
171 7141 : return 0;
172 : }
173 :
174 : /* Find the next gap in received packet numbers. Scans pn_map for a gap starting from
175 : * *@iter. A gap is a contiguous block of unreceived packets between received ones.
176 : *
177 : * Returns: 1 if a gap was found, 0 if no more gaps exist or are relevant.
178 : */
179 326003 : static int quic_pnspace_next_gap_ack(const struct quic_pnspace *space,
180 : s64 *iter, u16 *start, u16 *end)
181 : {
182 326003 : u16 start_ = 0, end_ = 0, offset = (u16)(*iter - space->base_pn);
183 :
184 326003 : start_ = (u16)find_next_zero_bit(space->pn_map, space->pn_map_len, offset);
185 326003 : if (space->max_pn_seen <= space->base_pn + start_)
186 : return 0;
187 :
188 304909 : end_ = (u16)find_next_bit(space->pn_map, space->pn_map_len, start_);
189 304909 : if (space->max_pn_seen <= space->base_pn + end_ - 1)
190 : return 0;
191 :
192 304909 : *start = start_ + 1;
193 304909 : *end = end_;
194 304909 : *iter = space->base_pn + *end;
195 304909 : return 1;
196 : }
197 :
198 : /* Generate gap acknowledgment blocks (GABs). GABs describe ranges of unacknowledged
199 : * packets between received ones, and are used in ACK frames.
200 : *
201 : * Returns: Number of generated GABs (up to QUIC_PN_MAX_GABS).
202 : */
203 378481 : u16 quic_pnspace_num_gabs(struct quic_pnspace *space, struct quic_gap_ack_block *gabs)
204 : {
205 378481 : u16 start, end, ngaps = 0;
206 378481 : s64 iter;
207 :
208 378481 : if (!quic_pnspace_has_gap(space))
209 : return 0;
210 :
211 23920 : iter = space->base_pn;
212 : /* Loop through all gaps until the end of the window or max allowed gaps. */
213 326003 : while (quic_pnspace_next_gap_ack(space, &iter, &start, &end)) {
214 304909 : gabs[ngaps].start = start;
215 304909 : if (ngaps == QUIC_PN_MAX_GABS - 1) {
216 2826 : gabs[ngaps].end = (u16)(space->max_pn_seen - space->base_pn);
217 2826 : ngaps++;
218 2826 : break;
219 : }
220 302083 : gabs[ngaps].end = end;
221 302083 : ngaps++;
222 : }
223 : return ngaps;
224 : }
|
