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