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 struct ofodb {
  24         uint32_t nb_elem;
  25         uint32_t nb_max;
  26         union seqlen sl;
  27         struct rte_mbuf **obj;
  28 };
  29
  30 struct ofo {
  31         uint32_t nb_elem;
  32         uint32_t nb_max;
  33         struct ofodb db[];
  34 };
  35
  36 static 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
  45 static 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
  56 static inline void
  57 tcp_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
  67 static 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
 107 static 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
 154 static 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
 196 static 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
 226 static 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
 239 struct ofo *
 240 tcp_ofo_alloc(uint32_t nbufs, int32_t socket);
 241
 242 void
 243 tcp_ofo_free(struct ofo *ofo);
 244
 245 #ifdef __cplusplus
 246 }
 247 #endif
 248
 249 #endif /* _TCP_OFO_H_ */