1 /* SPDX-License-Identifier: BSD-3-Clause 2 * Copyright(c) 2010-2014 Intel Corporation 3 */ 4 5 #include <string.h> 6 #include <sys/queue.h> 7 8 #include <rte_string_fns.h> 9 #include <rte_log.h> 10 #include <rte_mbuf.h> 11 #include <rte_mbuf_dyn.h> 12 #include <rte_eal_memconfig.h> 13 #include <rte_errno.h> 14 #include <rte_malloc.h> 15 #include <rte_tailq.h> 16 17 #include "rte_reorder.h" 18 19 TAILQ_HEAD(rte_reorder_list, rte_tailq_entry); 20 21 static struct rte_tailq_elem rte_reorder_tailq = { 22 .name = "RTE_REORDER", 23 }; 24 EAL_REGISTER_TAILQ(rte_reorder_tailq) 25 26 #define NO_FLAGS 0 27 #define RTE_REORDER_PREFIX "RO_" 28 #define RTE_REORDER_NAMESIZE 32 29 30 /* Macros for printing using RTE_LOG */ 31 #define RTE_LOGTYPE_REORDER RTE_LOGTYPE_USER1 32 33 #define RTE_REORDER_SEQN_DYNFIELD_NAME "rte_reorder_seqn_dynfield" 34 int rte_reorder_seqn_dynfield_offset = -1; 35 36 /* A generic circular buffer */ 37 struct cir_buffer { 38 unsigned int size; /**< Number of entries that can be stored */ 39 unsigned int mask; /**< [buffer_size - 1]: used for wrap-around */ 40 unsigned int head; /**< insertion point in buffer */ 41 unsigned int tail; /**< extraction point in buffer */ 42 struct rte_mbuf **entries; 43 } __rte_cache_aligned; 44 45 /* The reorder buffer data structure itself */ 46 struct rte_reorder_buffer { 47 char name[RTE_REORDER_NAMESIZE]; 48 uint32_t min_seqn; /**< Lowest seq. number that can be in the buffer */ 49 unsigned int memsize; /**< memory area size of reorder buffer */ 50 bool is_initialized; /**< flag indicates that buffer was initialized */ 51 52 struct cir_buffer ready_buf; /**< temp buffer for dequeued entries */ 53 struct cir_buffer order_buf; /**< buffer used to reorder entries */ 54 } __rte_cache_aligned; 55 56 static void 57 rte_reorder_free_mbufs(struct rte_reorder_buffer *b); 58 59 unsigned int 60 rte_reorder_memory_footprint_get(unsigned int size) 61 { 62 return sizeof(struct rte_reorder_buffer) + (2 * size * sizeof(struct rte_mbuf *)); 63 } 64 65 struct rte_reorder_buffer * 66 rte_reorder_init(struct rte_reorder_buffer *b, unsigned int bufsize, 67 const char *name, unsigned int size) 68 { 69 const unsigned int min_bufsize = rte_reorder_memory_footprint_get(size); 70 static const struct rte_mbuf_dynfield reorder_seqn_dynfield_desc = { 71 .name = RTE_REORDER_SEQN_DYNFIELD_NAME, 72 .size = sizeof(rte_reorder_seqn_t), 73 .align = __alignof__(rte_reorder_seqn_t), 74 }; 75 76 if (b == NULL) { 77 RTE_LOG(ERR, REORDER, "Invalid reorder buffer parameter:" 78 " NULL\n"); 79 rte_errno = EINVAL; 80 return NULL; 81 } 82 if (!rte_is_power_of_2(size)) { 83 RTE_LOG(ERR, REORDER, "Invalid reorder buffer size" 84 " - Not a power of 2\n"); 85 rte_errno = EINVAL; 86 return NULL; 87 } 88 if (name == NULL) { 89 RTE_LOG(ERR, REORDER, "Invalid reorder buffer name ptr:" 90 " NULL\n"); 91 rte_errno = EINVAL; 92 return NULL; 93 } 94 if (bufsize < min_bufsize) { 95 RTE_LOG(ERR, REORDER, "Invalid reorder buffer memory size: %u, " 96 "minimum required: %u\n", bufsize, min_bufsize); 97 rte_errno = EINVAL; 98 return NULL; 99 } 100 101 rte_reorder_seqn_dynfield_offset = rte_mbuf_dynfield_register(&reorder_seqn_dynfield_desc); 102 if (rte_reorder_seqn_dynfield_offset < 0) { 103 RTE_LOG(ERR, REORDER, 104 "Failed to register mbuf field for reorder sequence number, rte_errno: %i\n", 105 rte_errno); 106 rte_errno = ENOMEM; 107 return NULL; 108 } 109 110 memset(b, 0, bufsize); 111 strlcpy(b->name, name, sizeof(b->name)); 112 b->memsize = bufsize; 113 b->order_buf.size = b->ready_buf.size = size; 114 b->order_buf.mask = b->ready_buf.mask = size - 1; 115 b->ready_buf.entries = (void *)&b[1]; 116 b->order_buf.entries = RTE_PTR_ADD(&b[1], 117 size * sizeof(b->ready_buf.entries[0])); 118 119 return b; 120 } 121 122 /* 123 * Insert new entry into global list. 124 * Returns pointer to already inserted entry if such exists, or to newly inserted one. 125 */ 126 static struct rte_tailq_entry * 127 rte_reorder_entry_insert(struct rte_tailq_entry *new_te) 128 { 129 struct rte_reorder_list *reorder_list; 130 struct rte_reorder_buffer *b, *nb; 131 struct rte_tailq_entry *te; 132 133 rte_mcfg_tailq_write_lock(); 134 135 reorder_list = RTE_TAILQ_CAST(rte_reorder_tailq.head, rte_reorder_list); 136 /* guarantee there's no existing */ 137 TAILQ_FOREACH(te, reorder_list, next) { 138 b = (struct rte_reorder_buffer *) te->data; 139 nb = (struct rte_reorder_buffer *) new_te->data; 140 if (strncmp(nb->name, b->name, RTE_REORDER_NAMESIZE) == 0) 141 break; 142 } 143 144 if (te == NULL) { 145 TAILQ_INSERT_TAIL(reorder_list, new_te, next); 146 te = new_te; 147 } 148 149 rte_mcfg_tailq_write_unlock(); 150 151 return te; 152 } 153 154 struct rte_reorder_buffer* 155 rte_reorder_create(const char *name, unsigned socket_id, unsigned int size) 156 { 157 struct rte_reorder_buffer *b = NULL; 158 struct rte_tailq_entry *te, *te_inserted; 159 160 const unsigned int bufsize = rte_reorder_memory_footprint_get(size); 161 162 /* Check user arguments. */ 163 if (!rte_is_power_of_2(size)) { 164 RTE_LOG(ERR, REORDER, "Invalid reorder buffer size" 165 " - Not a power of 2\n"); 166 rte_errno = EINVAL; 167 return NULL; 168 } 169 if (name == NULL) { 170 RTE_LOG(ERR, REORDER, "Invalid reorder buffer name ptr:" 171 " NULL\n"); 172 rte_errno = EINVAL; 173 return NULL; 174 } 175 176 /* allocate tailq entry */ 177 te = rte_zmalloc("REORDER_TAILQ_ENTRY", sizeof(*te), 0); 178 if (te == NULL) { 179 RTE_LOG(ERR, REORDER, "Failed to allocate tailq entry\n"); 180 rte_errno = ENOMEM; 181 return NULL; 182 } 183 184 /* Allocate memory to store the reorder buffer structure. */ 185 b = rte_zmalloc_socket("REORDER_BUFFER", bufsize, 0, socket_id); 186 if (b == NULL) { 187 RTE_LOG(ERR, REORDER, "Memzone allocation failed\n"); 188 rte_errno = ENOMEM; 189 rte_free(te); 190 return NULL; 191 } else { 192 if (rte_reorder_init(b, bufsize, name, size) == NULL) { 193 rte_free(b); 194 rte_free(te); 195 return NULL; 196 } 197 te->data = (void *)b; 198 } 199 200 te_inserted = rte_reorder_entry_insert(te); 201 if (te_inserted != te) { 202 rte_free(b); 203 rte_free(te); 204 return te_inserted->data; 205 } 206 207 return b; 208 } 209 210 void 211 rte_reorder_reset(struct rte_reorder_buffer *b) 212 { 213 char name[RTE_REORDER_NAMESIZE]; 214 215 rte_reorder_free_mbufs(b); 216 strlcpy(name, b->name, sizeof(name)); 217 /* No error checking as current values should be valid */ 218 rte_reorder_init(b, b->memsize, name, b->order_buf.size); 219 } 220 221 static void 222 rte_reorder_free_mbufs(struct rte_reorder_buffer *b) 223 { 224 unsigned i; 225 226 /* Free up the mbufs of order buffer & ready buffer */ 227 for (i = 0; i < b->order_buf.size; i++) { 228 rte_pktmbuf_free(b->order_buf.entries[i]); 229 rte_pktmbuf_free(b->ready_buf.entries[i]); 230 } 231 } 232 233 void 234 rte_reorder_free(struct rte_reorder_buffer *b) 235 { 236 struct rte_reorder_list *reorder_list; 237 struct rte_tailq_entry *te; 238 239 /* Check user arguments. */ 240 if (b == NULL) 241 return; 242 243 reorder_list = RTE_TAILQ_CAST(rte_reorder_tailq.head, rte_reorder_list); 244 245 rte_mcfg_tailq_write_lock(); 246 247 /* find our tailq entry */ 248 TAILQ_FOREACH(te, reorder_list, next) { 249 if (te->data == (void *) b) 250 break; 251 } 252 if (te == NULL) { 253 rte_mcfg_tailq_write_unlock(); 254 return; 255 } 256 257 TAILQ_REMOVE(reorder_list, te, next); 258 259 rte_mcfg_tailq_write_unlock(); 260 261 rte_reorder_free_mbufs(b); 262 263 rte_free(b); 264 rte_free(te); 265 } 266 267 struct rte_reorder_buffer * 268 rte_reorder_find_existing(const char *name) 269 { 270 struct rte_reorder_buffer *b = NULL; 271 struct rte_tailq_entry *te; 272 struct rte_reorder_list *reorder_list; 273 274 if (name == NULL) { 275 rte_errno = EINVAL; 276 return NULL; 277 } 278 279 reorder_list = RTE_TAILQ_CAST(rte_reorder_tailq.head, rte_reorder_list); 280 281 rte_mcfg_tailq_read_lock(); 282 TAILQ_FOREACH(te, reorder_list, next) { 283 b = (struct rte_reorder_buffer *) te->data; 284 if (strncmp(name, b->name, RTE_REORDER_NAMESIZE) == 0) 285 break; 286 } 287 rte_mcfg_tailq_read_unlock(); 288 289 if (te == NULL) { 290 rte_errno = ENOENT; 291 return NULL; 292 } 293 294 return b; 295 } 296 297 static unsigned 298 rte_reorder_fill_overflow(struct rte_reorder_buffer *b, unsigned n) 299 { 300 /* 301 * 1. Move all ready entries that fit to the ready_buf 302 * 2. check if we meet the minimum needed (n). 303 * 3. If not, then skip any gaps and keep moving. 304 * 4. If at any point the ready buffer is full, stop 305 * 5. Return the number of positions the order_buf head has moved 306 */ 307 308 struct cir_buffer *order_buf = &b->order_buf, 309 *ready_buf = &b->ready_buf; 310 311 unsigned int order_head_adv = 0; 312 313 /* 314 * move at least n packets to ready buffer, assuming ready buffer 315 * has room for those packets. 316 */ 317 while (order_head_adv < n && 318 ((ready_buf->head + 1) & ready_buf->mask) != ready_buf->tail) { 319 320 /* if we are blocked waiting on a packet, skip it */ 321 if (order_buf->entries[order_buf->head] == NULL) { 322 order_buf->head = (order_buf->head + 1) & order_buf->mask; 323 order_head_adv++; 324 } 325 326 /* Move all ready entries that fit to the ready_buf */ 327 while (order_buf->entries[order_buf->head] != NULL) { 328 ready_buf->entries[ready_buf->head] = 329 order_buf->entries[order_buf->head]; 330 331 order_buf->entries[order_buf->head] = NULL; 332 order_head_adv++; 333 334 order_buf->head = (order_buf->head + 1) & order_buf->mask; 335 336 if (((ready_buf->head + 1) & ready_buf->mask) == ready_buf->tail) 337 break; 338 339 ready_buf->head = (ready_buf->head + 1) & ready_buf->mask; 340 } 341 } 342 343 b->min_seqn += order_head_adv; 344 /* Return the number of positions the order_buf head has moved */ 345 return order_head_adv; 346 } 347 348 int 349 rte_reorder_insert(struct rte_reorder_buffer *b, struct rte_mbuf *mbuf) 350 { 351 uint32_t offset, position; 352 struct cir_buffer *order_buf; 353 354 if (b == NULL || mbuf == NULL) { 355 rte_errno = EINVAL; 356 return -1; 357 } 358 359 order_buf = &b->order_buf; 360 if (!b->is_initialized) { 361 b->min_seqn = *rte_reorder_seqn(mbuf); 362 b->is_initialized = 1; 363 } 364 365 /* 366 * calculate the offset from the head pointer we need to go. 367 * The subtraction takes care of the sequence number wrapping. 368 * For example (using 16-bit for brevity): 369 * min_seqn = 0xFFFD 370 * mbuf_seqn = 0x0010 371 * offset = 0x0010 - 0xFFFD = 0x13 372 */ 373 offset = *rte_reorder_seqn(mbuf) - b->min_seqn; 374 375 /* 376 * action to take depends on offset. 377 * offset < buffer->size: the mbuf fits within the current window of 378 * sequence numbers we can reorder. EXPECTED CASE. 379 * offset > buffer->size: the mbuf is outside the current window. There 380 * are a number of cases to consider: 381 * 1. The packet sequence is just outside the window, then we need 382 * to see about shifting the head pointer and taking any ready 383 * to return packets out of the ring. If there was a delayed 384 * or dropped packet preventing drains from shifting the window 385 * this case will skip over the dropped packet instead, and any 386 * packets dequeued here will be returned on the next drain call. 387 * 2. The packet sequence number is vastly outside our window, taken 388 * here as having offset greater than twice the buffer size. In 389 * this case, the packet is probably an old or late packet that 390 * was previously skipped, so just enqueue the packet for 391 * immediate return on the next drain call, or else return error. 392 */ 393 if (offset < b->order_buf.size) { 394 position = (order_buf->head + offset) & order_buf->mask; 395 order_buf->entries[position] = mbuf; 396 } else if (offset < 2 * b->order_buf.size) { 397 if (rte_reorder_fill_overflow(b, offset + 1 - order_buf->size) 398 < (offset + 1 - order_buf->size)) { 399 /* Put in handling for enqueue straight to output */ 400 rte_errno = ENOSPC; 401 return -1; 402 } 403 offset = *rte_reorder_seqn(mbuf) - b->min_seqn; 404 position = (order_buf->head + offset) & order_buf->mask; 405 order_buf->entries[position] = mbuf; 406 } else { 407 /* Put in handling for enqueue straight to output */ 408 rte_errno = ERANGE; 409 return -1; 410 } 411 return 0; 412 } 413 414 unsigned int 415 rte_reorder_drain(struct rte_reorder_buffer *b, struct rte_mbuf **mbufs, 416 unsigned max_mbufs) 417 { 418 unsigned int drain_cnt = 0; 419 420 struct cir_buffer *order_buf = &b->order_buf, 421 *ready_buf = &b->ready_buf; 422 423 /* Try to fetch requested number of mbufs from ready buffer */ 424 while ((drain_cnt < max_mbufs) && (ready_buf->tail != ready_buf->head)) { 425 mbufs[drain_cnt++] = ready_buf->entries[ready_buf->tail]; 426 ready_buf->entries[ready_buf->tail] = NULL; 427 ready_buf->tail = (ready_buf->tail + 1) & ready_buf->mask; 428 } 429 430 /* 431 * If requested number of buffers not fetched from ready buffer, fetch 432 * remaining buffers from order buffer 433 */ 434 while ((drain_cnt < max_mbufs) && 435 (order_buf->entries[order_buf->head] != NULL)) { 436 mbufs[drain_cnt++] = order_buf->entries[order_buf->head]; 437 order_buf->entries[order_buf->head] = NULL; 438 b->min_seqn++; 439 order_buf->head = (order_buf->head + 1) & order_buf->mask; 440 } 441 442 return drain_cnt; 443 } 444 445 /* Binary search seqn in ready buffer */ 446 static inline uint32_t 447 ready_buffer_seqn_find(const struct cir_buffer *ready_buf, const uint32_t seqn) 448 { 449 uint32_t mid, value, position, high; 450 uint32_t low = 0; 451 452 if (ready_buf->tail > ready_buf->head) 453 high = ready_buf->tail - ready_buf->head; 454 else 455 high = ready_buf->head - ready_buf->tail; 456 457 while (low <= high) { 458 mid = low + (high - low) / 2; 459 position = (ready_buf->tail + mid) & ready_buf->mask; 460 value = *rte_reorder_seqn(ready_buf->entries[position]); 461 if (seqn == value) 462 return mid; 463 else if (seqn > value) 464 low = mid + 1; 465 else 466 high = mid - 1; 467 } 468 469 return low; 470 } 471 472 unsigned int 473 rte_reorder_drain_up_to_seqn(struct rte_reorder_buffer *b, struct rte_mbuf **mbufs, 474 const unsigned int max_mbufs, const rte_reorder_seqn_t seqn) 475 { 476 uint32_t i, position, offset; 477 unsigned int drain_cnt = 0; 478 479 struct cir_buffer *order_buf = &b->order_buf, 480 *ready_buf = &b->ready_buf; 481 482 /* Seqn in Ready buffer */ 483 if (seqn < b->min_seqn) { 484 /* All sequence numbers are higher then given */ 485 if ((ready_buf->tail == ready_buf->head) || 486 (*rte_reorder_seqn(ready_buf->entries[ready_buf->tail]) > seqn)) 487 return 0; 488 489 offset = ready_buffer_seqn_find(ready_buf, seqn); 490 491 for (i = 0; (i < offset) && (drain_cnt < max_mbufs); i++) { 492 position = (ready_buf->tail + i) & ready_buf->mask; 493 mbufs[drain_cnt++] = ready_buf->entries[position]; 494 ready_buf->entries[position] = NULL; 495 } 496 ready_buf->tail = (ready_buf->tail + i) & ready_buf->mask; 497 498 return drain_cnt; 499 } 500 501 /* Seqn in Order buffer, add all buffers from Ready buffer */ 502 while ((drain_cnt < max_mbufs) && (ready_buf->tail != ready_buf->head)) { 503 mbufs[drain_cnt++] = ready_buf->entries[ready_buf->tail]; 504 ready_buf->entries[ready_buf->tail] = NULL; 505 ready_buf->tail = (ready_buf->tail + 1) & ready_buf->mask; 506 } 507 508 /* Fetch buffers from Order buffer up to given sequence number (exclusive) */ 509 offset = RTE_MIN(seqn - b->min_seqn, b->order_buf.size); 510 for (i = 0; (i < offset) && (drain_cnt < max_mbufs); i++) { 511 position = (order_buf->head + i) & order_buf->mask; 512 if (order_buf->entries[position] == NULL) 513 continue; 514 mbufs[drain_cnt++] = order_buf->entries[position]; 515 order_buf->entries[position] = NULL; 516 } 517 b->min_seqn += i; 518 order_buf->head = (order_buf->head + i) & order_buf->mask; 519 520 return drain_cnt; 521 } 522 523 static bool 524 rte_reorder_is_empty(const struct rte_reorder_buffer *b) 525 { 526 const struct cir_buffer *order_buf = &b->order_buf, *ready_buf = &b->ready_buf; 527 unsigned int i; 528 529 /* Ready buffer does not have gaps */ 530 if (ready_buf->tail != ready_buf->head) 531 return false; 532 533 /* Order buffer could have gaps, iterate */ 534 for (i = 0; i < order_buf->size; i++) { 535 if (order_buf->entries[i] != NULL) 536 return false; 537 } 538 539 return true; 540 } 541 542 unsigned int 543 rte_reorder_min_seqn_set(struct rte_reorder_buffer *b, rte_reorder_seqn_t min_seqn) 544 { 545 if (!rte_reorder_is_empty(b)) 546 return -ENOTEMPTY; 547 548 b->min_seqn = min_seqn; 549 b->is_initialized = true; 550 551 return 0; 552 } 553