lib/librte_reorder/rte_reorder.c

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