lib/reorder/rte_reorder.c

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2010-2014 Intel Corporation
   3  */
   4
   5 #include <string.h>
   6
   7 #include <rte_string_fns.h>
   8 #include <rte_log.h>
   9 #include <rte_mbuf.h>
  10 #include <rte_mbuf_dyn.h>
  11 #include <rte_eal_memconfig.h>
  12 #include <rte_errno.h>
  13 #include <rte_malloc.h>
  14 #include <rte_tailq.h>
  15
  16 #include "rte_reorder.h"
  17
  18 TAILQ_HEAD(rte_reorder_list, rte_tailq_entry);
  19
  20 static struct rte_tailq_elem rte_reorder_tailq = {
  21         .name = "RTE_REORDER",
  22 };
  23 EAL_REGISTER_TAILQ(rte_reorder_tailq)
  24
  25 #define NO_FLAGS 0
  26 #define RTE_REORDER_PREFIX "RO_"
  27 #define RTE_REORDER_NAMESIZE 32
  28
  29 /* Macros for printing using RTE_LOG */
  30 #define RTE_LOGTYPE_REORDER     RTE_LOGTYPE_USER1
  31
  32 #define RTE_REORDER_SEQN_DYNFIELD_NAME "rte_reorder_seqn_dynfield"
  33 int rte_reorder_seqn_dynfield_offset = -1;
  34
  35 /* A generic circular buffer */
  36 struct cir_buffer {
  37         unsigned int size;   /**< Number of entries that can be stored */
  38         unsigned int mask;   /**< [buffer_size - 1]: used for wrap-around */
  39         unsigned int head;   /**< insertion point in buffer */
  40         unsigned int tail;   /**< extraction point in buffer */
  41         struct rte_mbuf **entries;
  42 } __rte_cache_aligned;
  43
  44 /* The reorder buffer data structure itself */
  45 struct rte_reorder_buffer {
  46         char name[RTE_REORDER_NAMESIZE];
  47         uint32_t min_seqn;  /**< Lowest seq. number that can be in the buffer */
  48         unsigned int memsize; /**< memory area size of reorder buffer */
  49         struct cir_buffer ready_buf; /**< temp buffer for dequeued entries */
  50         struct cir_buffer order_buf; /**< buffer used to reorder entries */
  51         int is_initialized;
  52 } __rte_cache_aligned;
  53
  54 static void
  55 rte_reorder_free_mbufs(struct rte_reorder_buffer *b);
  56
  57 struct rte_reorder_buffer *
  58 rte_reorder_init(struct rte_reorder_buffer *b, unsigned int bufsize,
  59                 const char *name, unsigned int size)
  60 {
  61         const unsigned int min_bufsize = sizeof(*b) +
  62                                         (2 * size * sizeof(struct rte_mbuf *));
  63
  64         if (b == NULL) {
  65                 RTE_LOG(ERR, REORDER, "Invalid reorder buffer parameter:"
  66                                         " NULL\n");
  67                 rte_errno = EINVAL;
  68                 return NULL;
  69         }
  70         if (!rte_is_power_of_2(size)) {
  71                 RTE_LOG(ERR, REORDER, "Invalid reorder buffer size"
  72                                 " - Not a power of 2\n");
  73                 rte_errno = EINVAL;
  74                 return NULL;
  75         }
  76         if (name == NULL) {
  77                 RTE_LOG(ERR, REORDER, "Invalid reorder buffer name ptr:"
  78                                         " NULL\n");
  79                 rte_errno = EINVAL;
  80                 return NULL;
  81         }
  82         if (bufsize < min_bufsize) {
  83                 RTE_LOG(ERR, REORDER, "Invalid reorder buffer memory size: %u, "
  84                         "minimum required: %u\n", bufsize, min_bufsize);
  85                 rte_errno = EINVAL;
  86                 return NULL;
  87         }
  88
  89         memset(b, 0, bufsize);
  90         strlcpy(b->name, name, sizeof(b->name));
  91         b->memsize = bufsize;
  92         b->order_buf.size = b->ready_buf.size = size;
  93         b->order_buf.mask = b->ready_buf.mask = size - 1;
  94         b->ready_buf.entries = (void *)&b[1];
  95         b->order_buf.entries = RTE_PTR_ADD(&b[1],
  96                         size * sizeof(b->ready_buf.entries[0]));
  97
  98         return b;
  99 }
 100
 101 struct rte_reorder_buffer*
 102 rte_reorder_create(const char *name, unsigned socket_id, unsigned int size)
 103 {
 104         struct rte_reorder_buffer *b = NULL;
 105         struct rte_tailq_entry *te;
 106         struct rte_reorder_list *reorder_list;
 107         const unsigned int bufsize = sizeof(struct rte_reorder_buffer) +
 108                                         (2 * size * sizeof(struct rte_mbuf *));
 109         static const struct rte_mbuf_dynfield reorder_seqn_dynfield_desc = {
 110                 .name = RTE_REORDER_SEQN_DYNFIELD_NAME,
 111                 .size = sizeof(rte_reorder_seqn_t),
 112                 .align = __alignof__(rte_reorder_seqn_t),
 113         };
 114
 115         reorder_list = RTE_TAILQ_CAST(rte_reorder_tailq.head, rte_reorder_list);
 116
 117         /* Check user arguments. */
 118         if (!rte_is_power_of_2(size)) {
 119                 RTE_LOG(ERR, REORDER, "Invalid reorder buffer size"
 120                                 " - Not a power of 2\n");
 121                 rte_errno = EINVAL;
 122                 return NULL;
 123         }
 124         if (name == NULL) {
 125                 RTE_LOG(ERR, REORDER, "Invalid reorder buffer name ptr:"
 126                                         " NULL\n");
 127                 rte_errno = EINVAL;
 128                 return NULL;
 129         }
 130
 131         rte_reorder_seqn_dynfield_offset =
 132                 rte_mbuf_dynfield_register(&reorder_seqn_dynfield_desc);
 133         if (rte_reorder_seqn_dynfield_offset < 0) {
 134                 RTE_LOG(ERR, REORDER, "Failed to register mbuf field for reorder sequence number\n");
 135                 rte_errno = ENOMEM;
 136                 return NULL;
 137         }
 138
 139         rte_mcfg_tailq_write_lock();
 140
 141         /* guarantee there's no existing */
 142         TAILQ_FOREACH(te, reorder_list, next) {
 143                 b = (struct rte_reorder_buffer *) te->data;
 144                 if (strncmp(name, b->name, RTE_REORDER_NAMESIZE) == 0)
 145                         break;
 146         }
 147         if (te != NULL)
 148                 goto exit;
 149
 150         /* allocate tailq entry */
 151         te = rte_zmalloc("REORDER_TAILQ_ENTRY", sizeof(*te), 0);
 152         if (te == NULL) {
 153                 RTE_LOG(ERR, REORDER, "Failed to allocate tailq entry\n");
 154                 rte_errno = ENOMEM;
 155                 b = NULL;
 156                 goto exit;
 157         }
 158
 159         /* Allocate memory to store the reorder buffer structure. */
 160         b = rte_zmalloc_socket("REORDER_BUFFER", bufsize, 0, socket_id);
 161         if (b == NULL) {
 162                 RTE_LOG(ERR, REORDER, "Memzone allocation failed\n");
 163                 rte_errno = ENOMEM;
 164                 rte_free(te);
 165         } else {
 166                 rte_reorder_init(b, bufsize, name, size);
 167                 te->data = (void *)b;
 168                 TAILQ_INSERT_TAIL(reorder_list, te, next);
 169         }
 170
 171 exit:
 172         rte_mcfg_tailq_write_unlock();
 173         return b;
 174 }
 175
 176 void
 177 rte_reorder_reset(struct rte_reorder_buffer *b)
 178 {
 179         char name[RTE_REORDER_NAMESIZE];
 180
 181         rte_reorder_free_mbufs(b);
 182         strlcpy(name, b->name, sizeof(name));
 183         /* No error checking as current values should be valid */
 184         rte_reorder_init(b, b->memsize, name, b->order_buf.size);
 185 }
 186
 187 static void
 188 rte_reorder_free_mbufs(struct rte_reorder_buffer *b)
 189 {
 190         unsigned i;
 191
 192         /* Free up the mbufs of order buffer & ready buffer */
 193         for (i = 0; i < b->order_buf.size; i++) {
 194                 rte_pktmbuf_free(b->order_buf.entries[i]);
 195                 rte_pktmbuf_free(b->ready_buf.entries[i]);
 196         }
 197 }
 198
 199 void
 200 rte_reorder_free(struct rte_reorder_buffer *b)
 201 {
 202         struct rte_reorder_list *reorder_list;
 203         struct rte_tailq_entry *te;
 204
 205         /* Check user arguments. */
 206         if (b == NULL)
 207                 return;
 208
 209         reorder_list = RTE_TAILQ_CAST(rte_reorder_tailq.head, rte_reorder_list);
 210
 211         rte_mcfg_tailq_write_lock();
 212
 213         /* find our tailq entry */
 214         TAILQ_FOREACH(te, reorder_list, next) {
 215                 if (te->data == (void *) b)
 216                         break;
 217         }
 218         if (te == NULL) {
 219                 rte_mcfg_tailq_write_unlock();
 220                 return;
 221         }
 222
 223         TAILQ_REMOVE(reorder_list, te, next);
 224
 225         rte_mcfg_tailq_write_unlock();
 226
 227         rte_reorder_free_mbufs(b);
 228
 229         rte_free(b);
 230         rte_free(te);
 231 }
 232
 233 struct rte_reorder_buffer *
 234 rte_reorder_find_existing(const char *name)
 235 {
 236         struct rte_reorder_buffer *b = NULL;
 237         struct rte_tailq_entry *te;
 238         struct rte_reorder_list *reorder_list;
 239
 240         if (name == NULL) {
 241                 rte_errno = EINVAL;
 242                 return NULL;
 243         }
 244
 245         reorder_list = RTE_TAILQ_CAST(rte_reorder_tailq.head, rte_reorder_list);
 246
 247         rte_mcfg_tailq_read_lock();
 248         TAILQ_FOREACH(te, reorder_list, next) {
 249                 b = (struct rte_reorder_buffer *) te->data;
 250                 if (strncmp(name, b->name, RTE_REORDER_NAMESIZE) == 0)
 251                         break;
 252         }
 253         rte_mcfg_tailq_read_unlock();
 254
 255         if (te == NULL) {
 256                 rte_errno = ENOENT;
 257                 return NULL;
 258         }
 259
 260         return b;
 261 }
 262
 263 static unsigned
 264 rte_reorder_fill_overflow(struct rte_reorder_buffer *b, unsigned n)
 265 {
 266         /*
 267          * 1. Move all ready entries that fit to the ready_buf
 268          * 2. check if we meet the minimum needed (n).
 269          * 3. If not, then skip any gaps and keep moving.
 270          * 4. If at any point the ready buffer is full, stop
 271          * 5. Return the number of positions the order_buf head has moved
 272          */
 273
 274         struct cir_buffer *order_buf = &b->order_buf,
 275                         *ready_buf = &b->ready_buf;
 276
 277         unsigned int order_head_adv = 0;
 278
 279         /*
 280          * move at least n packets to ready buffer, assuming ready buffer
 281          * has room for those packets.
 282          */
 283         while (order_head_adv < n &&
 284                         ((ready_buf->head + 1) & ready_buf->mask) != ready_buf->tail) {
 285
 286                 /* if we are blocked waiting on a packet, skip it */
 287                 if (order_buf->entries[order_buf->head] == NULL) {
 288                         order_buf->head = (order_buf->head + 1) & order_buf->mask;
 289                         order_head_adv++;
 290                 }
 291
 292                 /* Move all ready entries that fit to the ready_buf */
 293                 while (order_buf->entries[order_buf->head] != NULL) {
 294                         ready_buf->entries[ready_buf->head] =
 295                                         order_buf->entries[order_buf->head];
 296
 297                         order_buf->entries[order_buf->head] = NULL;
 298                         order_head_adv++;
 299
 300                         order_buf->head = (order_buf->head + 1) & order_buf->mask;
 301
 302                         if (((ready_buf->head + 1) & ready_buf->mask) == ready_buf->tail)
 303                                 break;
 304
 305                         ready_buf->head = (ready_buf->head + 1) & ready_buf->mask;
 306                 }
 307         }
 308
 309         b->min_seqn += order_head_adv;
 310         /* Return the number of positions the order_buf head has moved */
 311         return order_head_adv;
 312 }
 313
 314 int
 315 rte_reorder_insert(struct rte_reorder_buffer *b, struct rte_mbuf *mbuf)
 316 {
 317         uint32_t offset, position;
 318         struct cir_buffer *order_buf;
 319
 320         if (b == NULL || mbuf == NULL) {
 321                 rte_errno = EINVAL;
 322                 return -1;
 323         }
 324
 325         order_buf = &b->order_buf;
 326         if (!b->is_initialized) {
 327                 b->min_seqn = *rte_reorder_seqn(mbuf);
 328                 b->is_initialized = 1;
 329         }
 330
 331         /*
 332          * calculate the offset from the head pointer we need to go.
 333          * The subtraction takes care of the sequence number wrapping.
 334          * For example (using 16-bit for brevity):
 335          *      min_seqn  = 0xFFFD
 336          *      mbuf_seqn = 0x0010
 337          *      offset    = 0x0010 - 0xFFFD = 0x13
 338          */
 339         offset = *rte_reorder_seqn(mbuf) - b->min_seqn;
 340
 341         /*
 342          * action to take depends on offset.
 343          * offset < buffer->size: the mbuf fits within the current window of
 344          *    sequence numbers we can reorder. EXPECTED CASE.
 345          * offset > buffer->size: the mbuf is outside the current window. There
 346          *    are a number of cases to consider:
 347          *    1. The packet sequence is just outside the window, then we need
 348          *       to see about shifting the head pointer and taking any ready
 349          *       to return packets out of the ring. If there was a delayed
 350          *       or dropped packet preventing drains from shifting the window
 351          *       this case will skip over the dropped packet instead, and any
 352          *       packets dequeued here will be returned on the next drain call.
 353          *    2. The packet sequence number is vastly outside our window, taken
 354          *       here as having offset greater than twice the buffer size. In
 355          *       this case, the packet is probably an old or late packet that
 356          *       was previously skipped, so just enqueue the packet for
 357          *       immediate return on the next drain call, or else return error.
 358          */
 359         if (offset < b->order_buf.size) {
 360                 position = (order_buf->head + offset) & order_buf->mask;
 361                 order_buf->entries[position] = mbuf;
 362         } else if (offset < 2 * b->order_buf.size) {
 363                 if (rte_reorder_fill_overflow(b, offset + 1 - order_buf->size)
 364                                 < (offset + 1 - order_buf->size)) {
 365                         /* Put in handling for enqueue straight to output */
 366                         rte_errno = ENOSPC;
 367                         return -1;
 368                 }
 369                 offset = *rte_reorder_seqn(mbuf) - b->min_seqn;
 370                 position = (order_buf->head + offset) & order_buf->mask;
 371                 order_buf->entries[position] = mbuf;
 372         } else {
 373                 /* Put in handling for enqueue straight to output */
 374                 rte_errno = ERANGE;
 375                 return -1;
 376         }
 377         return 0;
 378 }
 379
 380 unsigned int
 381 rte_reorder_drain(struct rte_reorder_buffer *b, struct rte_mbuf **mbufs,
 382                 unsigned max_mbufs)
 383 {
 384         unsigned int drain_cnt = 0;
 385
 386         struct cir_buffer *order_buf = &b->order_buf,
 387                         *ready_buf = &b->ready_buf;
 388
 389         /* Try to fetch requested number of mbufs from ready buffer */
 390         while ((drain_cnt < max_mbufs) && (ready_buf->tail != ready_buf->head)) {
 391                 mbufs[drain_cnt++] = ready_buf->entries[ready_buf->tail];
 392                 ready_buf->tail = (ready_buf->tail + 1) & ready_buf->mask;
 393         }
 394
 395         /*
 396          * If requested number of buffers not fetched from ready buffer, fetch
 397          * remaining buffers from order buffer
 398          */
 399         while ((drain_cnt < max_mbufs) &&
 400                         (order_buf->entries[order_buf->head] != NULL)) {
 401                 mbufs[drain_cnt++] = order_buf->entries[order_buf->head];
 402                 order_buf->entries[order_buf->head] = NULL;
 403                 b->min_seqn++;
 404                 order_buf->head = (order_buf->head + 1) & order_buf->mask;
 405         }
 406
 407         return drain_cnt;
 408 }