lib/librte_reorder/rte_reorder.c

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