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
23#include <stdbool.h>
24
25struct ofodb {
26	uint32_t nb_elem;
27	uint32_t nb_max;
28	union seqlen sl;
29	struct rte_mbuf **obj;
30};
31
32struct ofo {
33	uint32_t nb_elem;
34	uint32_t nb_max;
35	struct ofodb db[];
36};
37
38static inline void
39_ofodb_move(struct ofodb *dst, struct ofodb *src)
40{
41	uint32_t i;
42
43	dst->nb_elem = src->nb_elem;
44	dst->sl = src->sl;
45	for (i = 0; i < src->nb_elem; i++)
46		dst->obj[i] = src->obj[i];
47}
48
49static inline void
50_ofodb_free(struct ofodb *db)
51{
52	uint32_t i;
53
54	for (i = 0; i != db->nb_elem; i++)
55		rte_pktmbuf_free(db->obj[i]);
56}
57
58static inline void
59_ofo_remove(struct ofo *ofo, uint32_t pos, uint32_t num)
60{
61	uint32_t i, n;
62
63	n = ofo->nb_elem - num - pos;
64	for (i = 0; i != n; i++)
65		_ofodb_move(&ofo->db[pos + i], &ofo->db[pos + num + i]);
66	ofo->nb_elem -= num;
67}
68
69static inline void
70tcp_ofo_reset(struct ofo *ofo)
71{
72	uint32_t i;
73
74	for (i = 0; i != ofo->nb_elem; i++)
75		_ofodb_free(&ofo->db[i]);
76
77	_ofo_remove(ofo, 0, ofo->nb_elem);
78}
79
80static inline uint32_t
81_ofo_insert_mbuf(struct ofo* ofo, uint32_t pos, union seqlen* sl,
82		 struct rte_mbuf* mb[], uint32_t num, bool is_compact) {
83	uint32_t i, k, n;
84	uint32_t end, seq;
85
86	struct ofodb* db = ofo->db + pos;
87
88	/* new pkts may overlap with right side db,
89	 * don't insert overlapped part from 'end'
90	 * function could be called from _ofo_compact,
91	 * no overlap in this condition.
92	 */
93	if (!is_compact && pos < ofo->nb_elem - 1)
94		end = ofo->db[pos + 1].sl.seq;
95	else
96		end = sl->seq + sl->len;
97
98	/* copy non-overlapping mbufs */
99	k = db->nb_elem;
100	n = RTE_MIN(db->nb_max - k, num);
101	for (i = 0, seq = sl->seq; i != n && tcp_seq_lt(seq, end); i++) {
102		seq += mb[i]->pkt_len;
103		db->obj[k + i] = mb[i];
104	}
105	if (tcp_seq_lt(end, seq))
106		rte_pktmbuf_trim(mb[i - 1], seq - end);
107
108	db->nb_elem += i;
109	db->sl.len += tcp_seq_min(seq, end) - sl->seq;
110	sl->len = sl->seq + sl->len - seq;
111	sl->seq = seq;
112	return i;
113}
114
115static inline uint32_t
116_ofo_insert_new(struct ofo *ofo, uint32_t pos, union seqlen *sl,
117		struct rte_mbuf *mb[], uint32_t num)
118{
119	uint32_t i, n;
120
121	n = ofo->nb_elem;
122
123	/* out of space */
124	if (n == ofo->nb_max)
125		return 0;
126
127	/* allocate new one */
128	ofo->nb_elem = n + 1;
129
130	/* insert into a proper position. */
131	for (i = n; i != pos; i--)
132		_ofodb_move(&ofo->db[i], &ofo->db[i - 1]);
133
134	ofo->db[pos].nb_elem = 0;
135	ofo->db[pos].sl.seq = sl->seq;
136	ofo->db[pos].sl.len = 0;
137
138	i = _ofo_insert_mbuf(ofo, pos, sl, mb, num, false);
139	return i;
140}
141
142static inline uint32_t
143_ofo_insert_right(struct ofo *ofo, uint32_t pos, union seqlen *sl,
144		  struct rte_mbuf *mb[], uint32_t num, bool is_compact)
145{
146	uint32_t i, j, n;
147	uint32_t end, plen, skip;
148	struct ofodb *db;
149
150	db = ofo->db + pos;
151	end = db->sl.seq + db->sl.len;
152
153	skip = end - sl->seq;
154
155	/* skip overlapping packets */
156	for (i = 0, n = skip; i != num && n != 0; i++, n -= plen) {
157		plen = mb[i]->pkt_len;
158		if (n < plen) {
159			/* adjust partially overlapped packet. */
160			rte_pktmbuf_adj(mb[i], n);
161			break;
162		}
163	}
164
165	/* free totally overlapped packets. */
166	for (j = 0; j != i; j++)
167		rte_pktmbuf_free(mb[j]);
168
169	sl->seq += skip;
170	sl->len -= skip;
171	j = _ofo_insert_mbuf(ofo, pos, sl, mb + i,  num - i, is_compact);
172	return i + j;
173}
174
175static inline uint32_t
176_ofo_step(struct ofo *ofo, union seqlen *sl, struct rte_mbuf *mb[],
177	  uint32_t num)
178{
179	uint32_t i, n;
180	struct ofodb *db, *nextdb;
181
182	db = NULL;
183	n = ofo->nb_elem;
184
185	/*
186	 * start from the right side, assume that after some gap,
187	 * we keep receiving packets in order.
188	 */
189	for (i = n; i-- != 0; ) {
190		db = ofo->db + i;
191		if (tcp_seq_leq(db->sl.seq, sl->seq))
192			break;
193	}
194
195	/*
196	 * if db has right consecutive dbs, find the most right one.
197	 * we should insert new packets after this db, rather than left ones.
198	 */
199	for (; i < n - 1; i++) {
200		nextdb = db + 1;
201		if (db->sl.seq + db->sl.len != nextdb->sl.seq)
202			break;
203		db = nextdb;
204	}
205
206	/* new db required */
207	if ((int32_t)i < 0 || tcp_seq_lt(db->sl.seq + db->sl.len, sl->seq))
208		return _ofo_insert_new(ofo, i + 1, sl, mb, num);
209
210	/* new one is right adjacent, or overlap */
211
212	/* new one is completely overlapped by old one */
213	if (tcp_seq_leq(sl->seq + sl->len, db->sl.seq + db->sl.len))
214		return 0;
215
216	/* either overlap OR (adjacent AND some free space remains) */
217	if (tcp_seq_lt(sl->seq, db->sl.seq + db->sl.len) ||
218	    db->nb_elem != db->nb_max)
219		return _ofo_insert_right(ofo, i, sl, mb, num, false);
220
221	/* adjacent, no free space in current block */
222	return _ofo_insert_new(ofo, i + 1, sl, mb, num);
223}
224
225static inline void
226_ofo_compact(struct ofo *ofo)
227{
228	uint32_t i, j, k, n, ro;
229	struct ofodb *db;
230
231	for (i = 0; i < ofo->nb_elem; i++) {
232
233		for (j = i + 1; j != ofo->nb_elem; j++) {
234
235			/* no intersection */
236			ro = ofo->db[j].sl.seq - ofo->db[i].sl.seq;
237			if (ro > ofo->db[i].sl.len)
238				break;
239
240			db = ofo->db + j;
241			n = _ofo_insert_right(ofo, i, &db->sl, db->obj,
242				db->nb_elem, true);
243			if (n < db->nb_elem) {
244				db->nb_elem -= n;
245				for (k = 0; k < db->nb_elem; k++)
246					db->obj[k] = db->obj[n + k];
247				break;
248			}
249		}
250
251		n = j - i - 1;
252		if (n != 0)
253			_ofo_remove(ofo, i + 1, n);
254	}
255}
256
257static inline uint32_t
258_ofodb_enqueue(struct rte_ring *r, const struct ofodb *db, uint32_t *seq)
259{
260	uint32_t i, n, num, begin, end;
261	struct rte_mbuf *pkt;
262
263	n = 0;
264	num = db->nb_elem;
265	begin = db->sl.seq;
266	i = 0;
267	pkt = db->obj[0];
268
269	/* removed overlapped part from db */
270	while (tcp_seq_lt(begin, *seq)) {
271		end = begin + pkt->pkt_len;
272		if (tcp_seq_leq(end, *seq)) {
273			/* pkt is completely overlapped */
274			begin = end;
275			rte_pktmbuf_free(pkt);
276			pkt = db->obj[++i];
277		} else {
278			/* pkt is partly overlapped */
279			db->obj[i] = _rte_pktmbuf_adj(pkt, *seq - begin);
280			break;
281		}
282	}
283
284	n = i;
285	n += _rte_ring_enqueue_burst(r, (void * const *)(db->obj + i), num - i);
286
287	*seq = db->sl.seq + db->sl.len;
288	*seq -= tcp_mbuf_seq_free(db->obj + n, num - n);
289	return num - n;
290}
291
292void
293tcp_ofo_calc_elems(uint32_t nbufs, uint32_t *nobj, uint32_t *ndb, uint32_t *sz);
294
295void
296tcp_ofo_init(struct ofo *ofo, uint32_t nobj, uint32_t ndb);
297
298#ifdef __cplusplus
299}
300#endif
301
302#endif /* _TCP_OFO_H_ */
303