tcp_ofo.h revision fbba0a3b
1/*
2 * Copyright (c) 2016  Intel Corporation.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at:
6 *
7 *     http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16#ifndef _TCP_OFO_H_
17#define _TCP_OFO_H_
18
19#ifdef __cplusplus
20extern "C" {
21#endif
22
23struct ofodb {
24	uint32_t nb_elem;
25	uint32_t nb_max;
26	union seqlen sl;
27	struct rte_mbuf **obj;
28};
29
30struct ofo {
31	uint32_t nb_elem;
32	uint32_t nb_max;
33	struct ofodb db[];
34};
35
36static inline void
37_ofodb_free(struct ofodb *db)
38{
39	uint32_t i;
40
41	for (i = 0; i != db->nb_elem; i++)
42		rte_pktmbuf_free(db->obj[i]);
43}
44
45static inline void
46_ofo_remove(struct ofo *ofo, uint32_t pos, uint32_t num)
47{
48	uint32_t i, n;
49
50	n = ofo->nb_elem - num - pos;
51	for (i = 0; i != n; i++)
52		ofo->db[pos + i] = ofo->db[pos + num + i];
53	ofo->nb_elem -= num;
54}
55
56static inline void
57tcp_ofo_reset(struct ofo *ofo)
58{
59	uint32_t i;
60
61	for (i = 0; i != ofo->nb_elem; i++)
62		_ofodb_free(&ofo->db[i]);
63
64	_ofo_remove(ofo, 0, ofo->nb_elem);
65}
66
67static inline uint32_t
68_ofo_insert_new(struct ofo *ofo, uint32_t pos, union seqlen *sl,
69	struct rte_mbuf *mb[], uint32_t num)
70{
71	uint32_t i, n, plen;
72	struct ofodb *db;
73
74	n = ofo->nb_elem;
75
76	/* out of space */
77	if (n == ofo->nb_max)
78		return 0;
79
80	/* allocate new one */
81	db = ofo->db + n;
82	ofo->nb_elem = n + 1;
83
84	/* insert into a proper position. */
85	for (i = n; i != pos; i--)
86		ofo->db[i] = ofo->db[i - 1];
87
88	/* fill new block */
89	n = RTE_MIN(db->nb_max, num);
90	for (i = 0; i != n; i++)
91		db->obj[i] = mb[i];
92
93	/* can't queue some packets. */
94	plen = 0;
95	for (i = n; i != num; i++)
96		plen += mb[i]->pkt_len;
97
98	db->nb_elem = n;
99	db->sl.seq = sl->seq;
100	db->sl.len = sl->len - plen;
101
102	sl->seq += db->sl.len;
103	sl->len -= db->sl.len;
104	return n;
105}
106
107static inline uint32_t
108_ofo_insert_right(struct ofo *ofo, uint32_t pos, union seqlen *sl,
109	struct rte_mbuf *mb[], uint32_t num)
110{
111	uint32_t i, j, k, n;
112	uint32_t end, plen, skip;
113	struct ofodb *db;
114
115	db = ofo->db + pos;
116	end = db->sl.seq + db->sl.len;
117
118	skip = end - sl->seq;
119
120	/* skip overlapping packets */
121	for (i = 0, n = skip; i != num && n != 0; i++, n -= plen) {
122
123		plen = mb[i]->pkt_len;
124		if (n < plen) {
125			/* adjust partially overlapped packet. */
126			rte_pktmbuf_adj(mb[i], plen - n);
127			break;
128		}
129	}
130
131	/* free totally overlapped packets. */
132	for (j = 0; j != i; j++)
133		rte_pktmbuf_free(mb[j]);
134
135	/* copy non-overlapping mbufs */
136	k = db->nb_elem;
137	n = RTE_MIN(db->nb_max - k, num - i);
138
139	plen = 0;
140	for (j = 0; j != n; j++) {
141		db->obj[k + j] = mb[i + j];
142		plen += mb[i + j]->pkt_len;
143	}
144
145	db->nb_elem += n;
146	db->sl.len += plen;
147
148	plen += skip;
149	sl->len -= plen;
150	sl->seq += plen;
151	return n + i;
152}
153
154static inline uint32_t
155_ofo_step(struct ofo *ofo, union seqlen *sl, struct rte_mbuf *mb[],
156	uint32_t num)
157{
158	uint32_t i, n, end, lo, ro;
159	struct ofodb *db;
160
161	db = NULL;
162	end = sl->seq + sl->len;
163	n = ofo->nb_elem;
164
165	/*
166	 * start from the right side, assume that after some gap,
167	 * we keep receiving packets in order.
168	 */
169	for (i = n; i-- != 0; ) {
170		db = ofo->db + i;
171		if (tcp_seq_leq(db->sl.seq, sl->seq))
172			break;
173	}
174
175	/* new db required */
176	if ((int32_t)i < 0 || tcp_seq_lt(db->sl.seq + db->sl.len, sl->seq))
177		return _ofo_insert_new(ofo, i + 1, sl, mb, num);
178
179	/* new one is right adjacent, or overlap */
180
181	ro = sl->seq - db->sl.seq;
182	lo = end - db->sl.seq;
183
184	/* new one is completely overlapped by old one */
185	if (lo <= db->sl.len)
186		return 0;
187
188	/* either overlap OR (adjacent AND some free space remains) */
189	if (ro < db->sl.len || db->nb_elem != db->nb_max)
190		return _ofo_insert_right(ofo, i, sl, mb, num);
191
192	/* adjacent, no free space in current block */
193	return _ofo_insert_new(ofo, i + 1, sl, mb, num);
194}
195
196static inline void
197_ofo_compact(struct ofo *ofo)
198{
199	uint32_t i, j, n, ro;
200	struct ofodb *db;
201
202	for (i = 0; i < ofo->nb_elem; i = j) {
203
204		for (j = i + 1; j != ofo->nb_elem; j++) {
205
206			/* no intersection */
207			ro = ofo->db[j].sl.seq - ofo->db[i].sl.seq;
208			if (ro > ofo->db[i].sl.len)
209				break;
210
211			db = ofo->db + j;
212			n = _ofo_insert_right(ofo, i, &db->sl, db->obj,
213				db->nb_elem);
214			if (n < db->nb_elem) {
215				db->nb_elem -= n;
216				break;
217			}
218		}
219
220		n = j - i - 1;
221		if (n != 0)
222			_ofo_remove(ofo, i + 1, n);
223	}
224}
225
226static inline uint32_t
227_ofodb_enqueue(struct rte_ring *r, const struct ofodb *db, union seqlen *sl)
228{
229	uint32_t n, num;
230
231	num = db->nb_elem;
232	sl->raw = db->sl.raw;
233	n = _rte_ring_enqueue_burst(r, (void * const *)db->obj, num);
234
235	sl->len -= tcp_mbuf_seq_free(db->obj + n, num - n);
236	return num - n;
237}
238
239struct ofo *
240tcp_ofo_alloc(uint32_t nbufs, int32_t socket);
241
242void
243tcp_ofo_free(struct ofo *ofo);
244
245#ifdef __cplusplus
246}
247#endif
248
249#endif /* _TCP_OFO_H_ */
250