lib/libtle_l4p/tcp_ofo.h

   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
  20 extern "C" {
  21 #endif
  22
  23 #include <stdbool.h>
  24
  25 struct ofodb {
  26         uint32_t nb_elem;
  27         uint32_t nb_max;
  28         union seqlen sl;
  29         struct rte_mbuf **obj;
  30 };
  31
  32 struct ofo {
  33         uint32_t nb_elem;
  34         uint32_t nb_max;
  35         struct ofodb db[];
  36 };
  37
  38 static 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
  49 static 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
  58 static 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
  69 static inline void
  70 tcp_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
  80 static 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
 115 static 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
 142 static 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
 175 static 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
 225 static 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
 257 static 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
 292 void
 293 tcp_ofo_calc_elems(uint32_t nbufs, uint32_t *nobj, uint32_t *ndb, uint32_t *sz);
 294
 295 void
 296 tcp_ofo_init(struct ofo *ofo, uint32_t nobj, uint32_t ndb);
 297
 298 #ifdef __cplusplus
 299 }
 300 #endif
 301
 302 #endif /* _TCP_OFO_H_ */