1aa97dd1cSKonstantin Ananyev/*
2aa97dd1cSKonstantin Ananyev * Copyright (c) 2016  Intel Corporation.
3aa97dd1cSKonstantin Ananyev * Licensed under the Apache License, Version 2.0 (the "License");
4aa97dd1cSKonstantin Ananyev * you may not use this file except in compliance with the License.
5aa97dd1cSKonstantin Ananyev * You may obtain a copy of the License at:
6aa97dd1cSKonstantin Ananyev *
7aa97dd1cSKonstantin Ananyev *     http://www.apache.org/licenses/LICENSE-2.0
8aa97dd1cSKonstantin Ananyev *
9aa97dd1cSKonstantin Ananyev * Unless required by applicable law or agreed to in writing, software
10aa97dd1cSKonstantin Ananyev * distributed under the License is distributed on an "AS IS" BASIS,
11aa97dd1cSKonstantin Ananyev * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12aa97dd1cSKonstantin Ananyev * See the License for the specific language governing permissions and
13aa97dd1cSKonstantin Ananyev * limitations under the License.
14aa97dd1cSKonstantin Ananyev */
15aa97dd1cSKonstantin Ananyev
16aa97dd1cSKonstantin Ananyev#ifndef _TCP_OFO_H_
17aa97dd1cSKonstantin Ananyev#define _TCP_OFO_H_
18aa97dd1cSKonstantin Ananyev
19aa97dd1cSKonstantin Ananyev#ifdef __cplusplus
20aa97dd1cSKonstantin Ananyevextern "C" {
21aa97dd1cSKonstantin Ananyev#endif
22aa97dd1cSKonstantin Ananyev
2317f6b7adSJielong Zhou#include <stdbool.h>
2417f6b7adSJielong Zhou
25aa97dd1cSKonstantin Ananyevstruct ofodb {
26aa97dd1cSKonstantin Ananyev	uint32_t nb_elem;
27aa97dd1cSKonstantin Ananyev	uint32_t nb_max;
28aa97dd1cSKonstantin Ananyev	union seqlen sl;
29aa97dd1cSKonstantin Ananyev	struct rte_mbuf **obj;
30aa97dd1cSKonstantin Ananyev};
31aa97dd1cSKonstantin Ananyev
32aa97dd1cSKonstantin Ananyevstruct ofo {
33aa97dd1cSKonstantin Ananyev	uint32_t nb_elem;
34aa97dd1cSKonstantin Ananyev	uint32_t nb_max;
35aa97dd1cSKonstantin Ananyev	struct ofodb db[];
36aa97dd1cSKonstantin Ananyev};
37aa97dd1cSKonstantin Ananyev
3817f6b7adSJielong Zhoustatic inline void
3917f6b7adSJielong Zhou_ofodb_move(struct ofodb *dst, struct ofodb *src)
4017f6b7adSJielong Zhou{
4117f6b7adSJielong Zhou	uint32_t i;
4217f6b7adSJielong Zhou
4317f6b7adSJielong Zhou	dst->nb_elem = src->nb_elem;
4417f6b7adSJielong Zhou	dst->sl = src->sl;
4517f6b7adSJielong Zhou	for (i = 0; i < src->nb_elem; i++)
4617f6b7adSJielong Zhou		dst->obj[i] = src->obj[i];
4717f6b7adSJielong Zhou}
4817f6b7adSJielong Zhou
49aa97dd1cSKonstantin Ananyevstatic inline void
50aa97dd1cSKonstantin Ananyev_ofodb_free(struct ofodb *db)
51aa97dd1cSKonstantin Ananyev{
52aa97dd1cSKonstantin Ananyev	uint32_t i;
53aa97dd1cSKonstantin Ananyev
54aa97dd1cSKonstantin Ananyev	for (i = 0; i != db->nb_elem; i++)
55aa97dd1cSKonstantin Ananyev		rte_pktmbuf_free(db->obj[i]);
56aa97dd1cSKonstantin Ananyev}
57aa97dd1cSKonstantin Ananyev
58aa97dd1cSKonstantin Ananyevstatic inline void
59aa97dd1cSKonstantin Ananyev_ofo_remove(struct ofo *ofo, uint32_t pos, uint32_t num)
60aa97dd1cSKonstantin Ananyev{
61aa97dd1cSKonstantin Ananyev	uint32_t i, n;
62aa97dd1cSKonstantin Ananyev
63aa97dd1cSKonstantin Ananyev	n = ofo->nb_elem - num - pos;
64aa97dd1cSKonstantin Ananyev	for (i = 0; i != n; i++)
6517f6b7adSJielong Zhou		_ofodb_move(&ofo->db[pos + i], &ofo->db[pos + num + i]);
66aa97dd1cSKonstantin Ananyev	ofo->nb_elem -= num;
67aa97dd1cSKonstantin Ananyev}
68aa97dd1cSKonstantin Ananyev
69aa97dd1cSKonstantin Ananyevstatic inline void
70aa97dd1cSKonstantin Ananyevtcp_ofo_reset(struct ofo *ofo)
71aa97dd1cSKonstantin Ananyev{
72aa97dd1cSKonstantin Ananyev	uint32_t i;
73aa97dd1cSKonstantin Ananyev
74aa97dd1cSKonstantin Ananyev	for (i = 0; i != ofo->nb_elem; i++)
75aa97dd1cSKonstantin Ananyev		_ofodb_free(&ofo->db[i]);
76aa97dd1cSKonstantin Ananyev
77aa97dd1cSKonstantin Ananyev	_ofo_remove(ofo, 0, ofo->nb_elem);
78aa97dd1cSKonstantin Ananyev}
79aa97dd1cSKonstantin Ananyev
8017f6b7adSJielong Zhoustatic inline uint32_t
8117f6b7adSJielong Zhou_ofo_insert_mbuf(struct ofo* ofo, uint32_t pos, union seqlen* sl,
8217f6b7adSJielong Zhou		 struct rte_mbuf* mb[], uint32_t num, bool is_compact) {
8317f6b7adSJielong Zhou	uint32_t i, k, n;
8417f6b7adSJielong Zhou	uint32_t end, seq;
8517f6b7adSJielong Zhou
8617f6b7adSJielong Zhou	struct ofodb* db = ofo->db + pos;
8717f6b7adSJielong Zhou
8817f6b7adSJielong Zhou	/* new pkts may overlap with right side db,
8917f6b7adSJielong Zhou	 * don't insert overlapped part from 'end'
9017f6b7adSJielong Zhou	 * function could be called from _ofo_compact,
9117f6b7adSJielong Zhou	 * no overlap in this condition.
9217f6b7adSJielong Zhou	 */
9317f6b7adSJielong Zhou	if (!is_compact && pos < ofo->nb_elem - 1)
9417f6b7adSJielong Zhou		end = ofo->db[pos + 1].sl.seq;
9517f6b7adSJielong Zhou	else
9617f6b7adSJielong Zhou		end = sl->seq + sl->len;
9717f6b7adSJielong Zhou
9817f6b7adSJielong Zhou	/* copy non-overlapping mbufs */
9917f6b7adSJielong Zhou	k = db->nb_elem;
10017f6b7adSJielong Zhou	n = RTE_MIN(db->nb_max - k, num);
10117f6b7adSJielong Zhou	for (i = 0, seq = sl->seq; i != n && tcp_seq_lt(seq, end); i++) {
10217f6b7adSJielong Zhou		seq += mb[i]->pkt_len;
10317f6b7adSJielong Zhou		db->obj[k + i] = mb[i];
10417f6b7adSJielong Zhou	}
10517f6b7adSJielong Zhou	if (tcp_seq_lt(end, seq))
10617f6b7adSJielong Zhou		rte_pktmbuf_trim(mb[i - 1], seq - end);
10717f6b7adSJielong Zhou
10817f6b7adSJielong Zhou	db->nb_elem += i;
10917f6b7adSJielong Zhou	db->sl.len += tcp_seq_min(seq, end) - sl->seq;
11017f6b7adSJielong Zhou	sl->len = sl->seq + sl->len - seq;
11117f6b7adSJielong Zhou	sl->seq = seq;
11217f6b7adSJielong Zhou	return i;
11317f6b7adSJielong Zhou}
11417f6b7adSJielong Zhou
115aa97dd1cSKonstantin Ananyevstatic inline uint32_t
116aa97dd1cSKonstantin Ananyev_ofo_insert_new(struct ofo *ofo, uint32_t pos, union seqlen *sl,
11717f6b7adSJielong Zhou		struct rte_mbuf *mb[], uint32_t num)
118aa97dd1cSKonstantin Ananyev{
11917f6b7adSJielong Zhou	uint32_t i, n;
120aa97dd1cSKonstantin Ananyev
121aa97dd1cSKonstantin Ananyev	n = ofo->nb_elem;
122aa97dd1cSKonstantin Ananyev
123aa97dd1cSKonstantin Ananyev	/* out of space */
124aa97dd1cSKonstantin Ananyev	if (n == ofo->nb_max)
125aa97dd1cSKonstantin Ananyev		return 0;
126aa97dd1cSKonstantin Ananyev
127aa97dd1cSKonstantin Ananyev	/* allocate new one */
128aa97dd1cSKonstantin Ananyev	ofo->nb_elem = n + 1;
129aa97dd1cSKonstantin Ananyev
130aa97dd1cSKonstantin Ananyev	/* insert into a proper position. */
131aa97dd1cSKonstantin Ananyev	for (i = n; i != pos; i--)
13217f6b7adSJielong Zhou		_ofodb_move(&ofo->db[i], &ofo->db[i - 1]);
133aa97dd1cSKonstantin Ananyev
13417f6b7adSJielong Zhou	ofo->db[pos].nb_elem = 0;
13517f6b7adSJielong Zhou	ofo->db[pos].sl.seq = sl->seq;
13617f6b7adSJielong Zhou	ofo->db[pos].sl.len = 0;
137aa97dd1cSKonstantin Ananyev
13817f6b7adSJielong Zhou	i = _ofo_insert_mbuf(ofo, pos, sl, mb, num, false);
13917f6b7adSJielong Zhou	return i;
140aa97dd1cSKonstantin Ananyev}
141aa97dd1cSKonstantin Ananyev
142aa97dd1cSKonstantin Ananyevstatic inline uint32_t
143aa97dd1cSKonstantin Ananyev_ofo_insert_right(struct ofo *ofo, uint32_t pos, union seqlen *sl,
14417f6b7adSJielong Zhou		  struct rte_mbuf *mb[], uint32_t num, bool is_compact)
145aa97dd1cSKonstantin Ananyev{
14617f6b7adSJielong Zhou	uint32_t i, j, n;
147aa97dd1cSKonstantin Ananyev	uint32_t end, plen, skip;
148aa97dd1cSKonstantin Ananyev	struct ofodb *db;
149aa97dd1cSKonstantin Ananyev
150aa97dd1cSKonstantin Ananyev	db = ofo->db + pos;
151aa97dd1cSKonstantin Ananyev	end = db->sl.seq + db->sl.len;
152aa97dd1cSKonstantin Ananyev
153aa97dd1cSKonstantin Ananyev	skip = end - sl->seq;
154aa97dd1cSKonstantin Ananyev
155aa97dd1cSKonstantin Ananyev	/* skip overlapping packets */
156aa97dd1cSKonstantin Ananyev	for (i = 0, n = skip; i != num && n != 0; i++, n -= plen) {
157aa97dd1cSKonstantin Ananyev		plen = mb[i]->pkt_len;
158aa97dd1cSKonstantin Ananyev		if (n < plen) {
159aa97dd1cSKonstantin Ananyev			/* adjust partially overlapped packet. */
16017f6b7adSJielong Zhou			rte_pktmbuf_adj(mb[i], n);
161aa97dd1cSKonstantin Ananyev			break;
162aa97dd1cSKonstantin Ananyev		}
163aa97dd1cSKonstantin Ananyev	}
164aa97dd1cSKonstantin Ananyev
165aa97dd1cSKonstantin Ananyev	/* free totally overlapped packets. */
166aa97dd1cSKonstantin Ananyev	for (j = 0; j != i; j++)
167aa97dd1cSKonstantin Ananyev		rte_pktmbuf_free(mb[j]);
168aa97dd1cSKonstantin Ananyev
16917f6b7adSJielong Zhou	sl->seq += skip;
17017f6b7adSJielong Zhou	sl->len -= skip;
17117f6b7adSJielong Zhou	j = _ofo_insert_mbuf(ofo, pos, sl, mb + i,  num - i, is_compact);
17217f6b7adSJielong Zhou	return i + j;
173aa97dd1cSKonstantin Ananyev}
174aa97dd1cSKonstantin Ananyev
175aa97dd1cSKonstantin Ananyevstatic inline uint32_t
176aa97dd1cSKonstantin Ananyev_ofo_step(struct ofo *ofo, union seqlen *sl, struct rte_mbuf *mb[],
17717f6b7adSJielong Zhou	  uint32_t num)
178aa97dd1cSKonstantin Ananyev{
17917f6b7adSJielong Zhou	uint32_t i, n;
18017f6b7adSJielong Zhou	struct ofodb *db, *nextdb;
181aa97dd1cSKonstantin Ananyev
182aa97dd1cSKonstantin Ananyev	db = NULL;
183aa97dd1cSKonstantin Ananyev	n = ofo->nb_elem;
184aa97dd1cSKonstantin Ananyev
185aa97dd1cSKonstantin Ananyev	/*
186aa97dd1cSKonstantin Ananyev	 * start from the right side, assume that after some gap,
187aa97dd1cSKonstantin Ananyev	 * we keep receiving packets in order.
188aa97dd1cSKonstantin Ananyev	 */
189aa97dd1cSKonstantin Ananyev	for (i = n; i-- != 0; ) {
190aa97dd1cSKonstantin Ananyev		db = ofo->db + i;
191aa97dd1cSKonstantin Ananyev		if (tcp_seq_leq(db->sl.seq, sl->seq))
192aa97dd1cSKonstantin Ananyev			break;
193aa97dd1cSKonstantin Ananyev	}
194aa97dd1cSKonstantin Ananyev
19517f6b7adSJielong Zhou	/*
19617f6b7adSJielong Zhou	 * if db has right consecutive dbs, find the most right one.
19717f6b7adSJielong Zhou	 * we should insert new packets after this db, rather than left ones.
19817f6b7adSJielong Zhou	 */
19917f6b7adSJielong Zhou	for (; i < n - 1; i++) {
20017f6b7adSJielong Zhou		nextdb = db + 1;
20117f6b7adSJielong Zhou		if (db->sl.seq + db->sl.len != nextdb->sl.seq)
20217f6b7adSJielong Zhou			break;
20317f6b7adSJielong Zhou		db = nextdb;
20417f6b7adSJielong Zhou	}
20517f6b7adSJielong Zhou
206aa97dd1cSKonstantin Ananyev	/* new db required */
207aa97dd1cSKonstantin Ananyev	if ((int32_t)i < 0 || tcp_seq_lt(db->sl.seq + db->sl.len, sl->seq))
208aa97dd1cSKonstantin Ananyev		return _ofo_insert_new(ofo, i + 1, sl, mb, num);
209aa97dd1cSKonstantin Ananyev
210aa97dd1cSKonstantin Ananyev	/* new one is right adjacent, or overlap */
211aa97dd1cSKonstantin Ananyev
212aa97dd1cSKonstantin Ananyev	/* new one is completely overlapped by old one */
21317f6b7adSJielong Zhou	if (tcp_seq_leq(sl->seq + sl->len, db->sl.seq + db->sl.len))
214aa97dd1cSKonstantin Ananyev		return 0;
215aa97dd1cSKonstantin Ananyev
216aa97dd1cSKonstantin Ananyev	/* either overlap OR (adjacent AND some free space remains) */
21717f6b7adSJielong Zhou	if (tcp_seq_lt(sl->seq, db->sl.seq + db->sl.len) ||
21817f6b7adSJielong Zhou	    db->nb_elem != db->nb_max)
21917f6b7adSJielong Zhou		return _ofo_insert_right(ofo, i, sl, mb, num, false);
220aa97dd1cSKonstantin Ananyev
221aa97dd1cSKonstantin Ananyev	/* adjacent, no free space in current block */
222aa97dd1cSKonstantin Ananyev	return _ofo_insert_new(ofo, i + 1, sl, mb, num);
223aa97dd1cSKonstantin Ananyev}
224aa97dd1cSKonstantin Ananyev
225aa97dd1cSKonstantin Ananyevstatic inline void
226aa97dd1cSKonstantin Ananyev_ofo_compact(struct ofo *ofo)
227aa97dd1cSKonstantin Ananyev{
22817f6b7adSJielong Zhou	uint32_t i, j, k, n, ro;
229aa97dd1cSKonstantin Ananyev	struct ofodb *db;
230aa97dd1cSKonstantin Ananyev
23117f6b7adSJielong Zhou	for (i = 0; i < ofo->nb_elem; i++) {
232aa97dd1cSKonstantin Ananyev
233aa97dd1cSKonstantin Ananyev		for (j = i + 1; j != ofo->nb_elem; j++) {
234aa97dd1cSKonstantin Ananyev
235aa97dd1cSKonstantin Ananyev			/* no intersection */
236aa97dd1cSKonstantin Ananyev			ro = ofo->db[j].sl.seq - ofo->db[i].sl.seq;
237aa97dd1cSKonstantin Ananyev			if (ro > ofo->db[i].sl.len)
238aa97dd1cSKonstantin Ananyev				break;
239aa97dd1cSKonstantin Ananyev
240aa97dd1cSKonstantin Ananyev			db = ofo->db + j;
241aa97dd1cSKonstantin Ananyev			n = _ofo_insert_right(ofo, i, &db->sl, db->obj,
24217f6b7adSJielong Zhou				db->nb_elem, true);
243aa97dd1cSKonstantin Ananyev			if (n < db->nb_elem) {
244aa97dd1cSKonstantin Ananyev				db->nb_elem -= n;
24517f6b7adSJielong Zhou				for (k = 0; k < db->nb_elem; k++)
24617f6b7adSJielong Zhou					db->obj[k] = db->obj[n + k];
247aa97dd1cSKonstantin Ananyev				break;
248aa97dd1cSKonstantin Ananyev			}
249aa97dd1cSKonstantin Ananyev		}
250aa97dd1cSKonstantin Ananyev
251aa97dd1cSKonstantin Ananyev		n = j - i - 1;
252aa97dd1cSKonstantin Ananyev		if (n != 0)
253aa97dd1cSKonstantin Ananyev			_ofo_remove(ofo, i + 1, n);
254aa97dd1cSKonstantin Ananyev	}
255aa97dd1cSKonstantin Ananyev}
256aa97dd1cSKonstantin Ananyev
257aa97dd1cSKonstantin Ananyevstatic inline uint32_t
25817f6b7adSJielong Zhou_ofodb_enqueue(struct rte_ring *r, const struct ofodb *db, uint32_t *seq)
259aa97dd1cSKonstantin Ananyev{
26017f6b7adSJielong Zhou	uint32_t i, n, num, begin, end;
26117f6b7adSJielong Zhou	struct rte_mbuf *pkt;
262aa97dd1cSKonstantin Ananyev
26317f6b7adSJielong Zhou	n = 0;
264aa97dd1cSKonstantin Ananyev	num = db->nb_elem;
26517f6b7adSJielong Zhou	begin = db->sl.seq;
26617f6b7adSJielong Zhou	i = 0;
26717f6b7adSJielong Zhou	pkt = db->obj[0];
26817f6b7adSJielong Zhou
26917f6b7adSJielong Zhou	/* removed overlapped part from db */
27017f6b7adSJielong Zhou	while (tcp_seq_lt(begin, *seq)) {
27117f6b7adSJielong Zhou		end = begin + pkt->pkt_len;
27217f6b7adSJielong Zhou		if (tcp_seq_leq(end, *seq)) {
27317f6b7adSJielong Zhou			/* pkt is completely overlapped */
27417f6b7adSJielong Zhou			begin = end;
27517f6b7adSJielong Zhou			rte_pktmbuf_free(pkt);
27617f6b7adSJielong Zhou			pkt = db->obj[++i];
27717f6b7adSJielong Zhou		} else {
27817f6b7adSJielong Zhou			/* pkt is partly overlapped */
279e4380f48SJielong Zhou			db->obj[i] = _rte_pktmbuf_adj(pkt, *seq - begin);
28017f6b7adSJielong Zhou			break;
28117f6b7adSJielong Zhou		}
28217f6b7adSJielong Zhou	}
28317f6b7adSJielong Zhou
28417f6b7adSJielong Zhou	n = i;
28517f6b7adSJielong Zhou	n += _rte_ring_enqueue_burst(r, (void * const *)(db->obj + i), num - i);
286aa97dd1cSKonstantin Ananyev
28717f6b7adSJielong Zhou	*seq = db->sl.seq + db->sl.len;
28817f6b7adSJielong Zhou	*seq -= tcp_mbuf_seq_free(db->obj + n, num - n);
289aa97dd1cSKonstantin Ananyev	return num - n;
290aa97dd1cSKonstantin Ananyev}
291aa97dd1cSKonstantin Ananyev
29247eb00f2SKonstantin Ananyevvoid
29347eb00f2SKonstantin Ananyevtcp_ofo_calc_elems(uint32_t nbufs, uint32_t *nobj, uint32_t *ndb, uint32_t *sz);
294aa97dd1cSKonstantin Ananyev
295aa97dd1cSKonstantin Ananyevvoid
29647eb00f2SKonstantin Ananyevtcp_ofo_init(struct ofo *ofo, uint32_t nobj, uint32_t ndb);
297aa97dd1cSKonstantin Ananyev
298aa97dd1cSKonstantin Ananyev#ifdef __cplusplus
299aa97dd1cSKonstantin Ananyev}
300aa97dd1cSKonstantin Ananyev#endif
301aa97dd1cSKonstantin Ananyev
302aa97dd1cSKonstantin Ananyev#endif /* _TCP_OFO_H_ */