1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2010-2014 Intel Corporation
7 #include <rte_string_fns.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>
16 #include "rte_reorder.h"
18 TAILQ_HEAD(rte_reorder_list, rte_tailq_entry);
20 static struct rte_tailq_elem rte_reorder_tailq = {
21 .name = "RTE_REORDER",
23 EAL_REGISTER_TAILQ(rte_reorder_tailq)
26 #define RTE_REORDER_PREFIX "RO_"
27 #define RTE_REORDER_NAMESIZE 32
29 /* Macros for printing using RTE_LOG */
30 #define RTE_LOGTYPE_REORDER RTE_LOGTYPE_USER1
32 #define RTE_REORDER_SEQN_DYNFIELD_NAME "rte_reorder_seqn_dynfield"
33 int rte_reorder_seqn_dynfield_offset = -1;
35 /* A generic circular 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;
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 */
52 } __rte_cache_aligned;
55 rte_reorder_free_mbufs(struct rte_reorder_buffer *b);
57 struct rte_reorder_buffer *
58 rte_reorder_init(struct rte_reorder_buffer *b, unsigned int bufsize,
59 const char *name, unsigned int size)
61 const unsigned int min_bufsize = sizeof(*b) +
62 (2 * size * sizeof(struct rte_mbuf *));
65 RTE_LOG(ERR, REORDER, "Invalid reorder buffer parameter:"
70 if (!rte_is_power_of_2(size)) {
71 RTE_LOG(ERR, REORDER, "Invalid reorder buffer size"
72 " - Not a power of 2\n");
77 RTE_LOG(ERR, REORDER, "Invalid reorder buffer name ptr:"
82 if (bufsize < min_bufsize) {
83 RTE_LOG(ERR, REORDER, "Invalid reorder buffer memory size: %u, "
84 "minimum required: %u\n", bufsize, min_bufsize);
89 memset(b, 0, bufsize);
90 strlcpy(b->name, name, sizeof(b->name));
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]));
101 struct rte_reorder_buffer*
102 rte_reorder_create(const char *name, unsigned socket_id, unsigned int size)
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),
115 reorder_list = RTE_TAILQ_CAST(rte_reorder_tailq.head, rte_reorder_list);
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");
125 RTE_LOG(ERR, REORDER, "Invalid reorder buffer name ptr:"
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");
139 rte_mcfg_tailq_write_lock();
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)
150 /* allocate tailq entry */
151 te = rte_zmalloc("REORDER_TAILQ_ENTRY", sizeof(*te), 0);
153 RTE_LOG(ERR, REORDER, "Failed to allocate tailq entry\n");
159 /* Allocate memory to store the reorder buffer structure. */
160 b = rte_zmalloc_socket("REORDER_BUFFER", bufsize, 0, socket_id);
162 RTE_LOG(ERR, REORDER, "Memzone allocation failed\n");
166 rte_reorder_init(b, bufsize, name, size);
167 te->data = (void *)b;
168 TAILQ_INSERT_TAIL(reorder_list, te, next);
172 rte_mcfg_tailq_write_unlock();
177 rte_reorder_reset(struct rte_reorder_buffer *b)
179 char name[RTE_REORDER_NAMESIZE];
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);
188 rte_reorder_free_mbufs(struct rte_reorder_buffer *b)
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]);
200 rte_reorder_free(struct rte_reorder_buffer *b)
202 struct rte_reorder_list *reorder_list;
203 struct rte_tailq_entry *te;
205 /* Check user arguments. */
209 reorder_list = RTE_TAILQ_CAST(rte_reorder_tailq.head, rte_reorder_list);
211 rte_mcfg_tailq_write_lock();
213 /* find our tailq entry */
214 TAILQ_FOREACH(te, reorder_list, next) {
215 if (te->data == (void *) b)
219 rte_mcfg_tailq_write_unlock();
223 TAILQ_REMOVE(reorder_list, te, next);
225 rte_mcfg_tailq_write_unlock();
227 rte_reorder_free_mbufs(b);
233 struct rte_reorder_buffer *
234 rte_reorder_find_existing(const char *name)
236 struct rte_reorder_buffer *b = NULL;
237 struct rte_tailq_entry *te;
238 struct rte_reorder_list *reorder_list;
245 reorder_list = RTE_TAILQ_CAST(rte_reorder_tailq.head, rte_reorder_list);
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)
253 rte_mcfg_tailq_read_unlock();
264 rte_reorder_fill_overflow(struct rte_reorder_buffer *b, unsigned n)
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
274 struct cir_buffer *order_buf = &b->order_buf,
275 *ready_buf = &b->ready_buf;
277 unsigned int order_head_adv = 0;
280 * move at least n packets to ready buffer, assuming ready buffer
281 * has room for those packets.
283 while (order_head_adv < n &&
284 ((ready_buf->head + 1) & ready_buf->mask) != ready_buf->tail) {
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;
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];
297 order_buf->entries[order_buf->head] = NULL;
300 order_buf->head = (order_buf->head + 1) & order_buf->mask;
302 if (((ready_buf->head + 1) & ready_buf->mask) == ready_buf->tail)
305 ready_buf->head = (ready_buf->head + 1) & ready_buf->mask;
309 b->min_seqn += order_head_adv;
310 /* Return the number of positions the order_buf head has moved */
311 return order_head_adv;
315 rte_reorder_insert(struct rte_reorder_buffer *b, struct rte_mbuf *mbuf)
317 uint32_t offset, position;
318 struct cir_buffer *order_buf;
320 if (b == NULL || mbuf == NULL) {
325 order_buf = &b->order_buf;
326 if (!b->is_initialized) {
327 b->min_seqn = *rte_reorder_seqn(mbuf);
328 b->is_initialized = 1;
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):
337 * offset = 0x0010 - 0xFFFD = 0x13
339 offset = *rte_reorder_seqn(mbuf) - b->min_seqn;
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.
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 */
369 offset = *rte_reorder_seqn(mbuf) - b->min_seqn;
370 position = (order_buf->head + offset) & order_buf->mask;
371 order_buf->entries[position] = mbuf;
373 /* Put in handling for enqueue straight to output */
381 rte_reorder_drain(struct rte_reorder_buffer *b, struct rte_mbuf **mbufs,
384 unsigned int drain_cnt = 0;
386 struct cir_buffer *order_buf = &b->order_buf,
387 *ready_buf = &b->ready_buf;
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;
396 * If requested number of buffers not fetched from ready buffer, fetch
397 * remaining buffers from order buffer
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;
404 order_buf->head = (order_buf->head + 1) & order_buf->mask;