TAS
TCP Acceleration as an OS Service
qman.c
1 /*
2  * Copyright 2019 University of Washington, Max Planck Institute for
3  * Software Systems, and The University of Texas at Austin
4  *
5  * Permission is hereby granted, free of charge, to any person obtaining
6  * a copy of this software and associated documentation files (the
7  * "Software"), to deal in the Software without restriction, including
8  * without limitation the rights to use, copy, modify, merge, publish,
9  * distribute, sublicense, and/or sell copies of the Software, and to
10  * permit persons to whom the Software is furnished to do so, subject to
11  * the following conditions:
12  *
13  * The above copyright notice and this permission notice shall be
14  * included in all copies or substantial portions of the Software.
15  *
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
17  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
19  * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
20  * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
21  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
22  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
23  */
24 
28 #include <assert.h>
29 #include <stdlib.h>
30 #include <stdio.h>
31 #include <stdbool.h>
32 #include <unistd.h>
33 
34 #include <rte_config.h>
35 #include <rte_malloc.h>
36 #include <rte_cycles.h>
37 
38 #include <utils.h>
39 
40 #include "internal.h"
41 
42 #define dprintf(...) do { } while (0)
43 
44 #define FLAG_INSKIPLIST 1
45 #define FLAG_INNOLIMITL 2
46 
48 #define SKIPLIST_BITS 3
49 
50 #define IDXLIST_INVAL (-1U)
51 
52 #define RNG_SEED 0x12345678
53 #define TIMESTAMP_BITS 32
54 #define TIMESTAMP_MASK 0xFFFFFFFF
55 
57 struct queue {
59  uint32_t next_idxs[QMAN_SKIPLIST_LEVELS];
61  uint32_t next_ts;
63  uint32_t rate;
65  uint32_t avail;
67  uint16_t max_chunk;
69  uint16_t flags;
70 } __attribute__((packed));
71 STATIC_ASSERT((sizeof(struct queue) == 32), queue_size);
72 
73 
75 static inline void set_impl(struct qman_thread *t, uint32_t id, uint32_t rate,
76  uint32_t avail, uint16_t max_chunk, uint8_t flags);
77 
79 static inline void queue_activate_nolimit(struct qman_thread *t,
80  struct queue *q, uint32_t idx);
81 static inline unsigned poll_nolimit(struct qman_thread *t, uint32_t cur_ts,
82  unsigned num, unsigned *q_ids, uint16_t *q_bytes);
83 
85 static inline void queue_activate_skiplist(struct qman_thread *t,
86  struct queue *q, uint32_t idx);
87 static inline unsigned poll_skiplist(struct qman_thread *t, uint32_t cur_ts,
88  unsigned num, unsigned *q_ids, uint16_t *q_bytes);
89 static inline uint8_t queue_level(struct qman_thread *t);
90 
91 static inline void queue_fire(struct qman_thread *t,
92  struct queue *q, uint32_t idx, unsigned *q_id, uint16_t *q_bytes);
93 static inline void queue_activate(struct qman_thread *t, struct queue *q,
94  uint32_t idx);
95 static inline uint32_t timestamp(void);
96 static inline int timestamp_lessthaneq(struct qman_thread *t, uint32_t a,
97  uint32_t b);
98 static inline int64_t rel_time(uint32_t cur_ts, uint32_t ts_in);
99 
100 
101 int qman_thread_init(struct dataplane_context *ctx)
102 {
103  struct qman_thread *t = &ctx->qman;
104  unsigned i;
105 
106  if ((t->queues = calloc(1, sizeof(*t->queues) * FLEXNIC_NUM_QMQUEUES))
107  == NULL)
108  {
109  fprintf(stderr, "qman_thread_init: queues malloc failed\n");
110  return -1;
111  }
112 
113  for (i = 0; i < QMAN_SKIPLIST_LEVELS; i++) {
114  t->head_idx[i] = IDXLIST_INVAL;
115  }
116  t->nolimit_head_idx = t->nolimit_tail_idx = IDXLIST_INVAL;
117  utils_rng_init(&t->rng, RNG_SEED * ctx->id + ctx->id);
118 
119  t->ts_virtual = 0;
120  t->ts_real = timestamp();
121 
122  return 0;
123 }
124 
125 uint32_t qman_timestamp(uint64_t cycles)
126 {
127  static uint64_t freq = 0;
128 
129  if (freq == 0)
130  freq = rte_get_tsc_hz();
131 
132  cycles *= 1000000ULL;
133  cycles /= freq;
134  return cycles;
135 }
136 
137 uint32_t qman_next_ts(struct qman_thread *t, uint32_t cur_ts)
138 {
139  uint32_t ts = timestamp();
140  uint32_t ret_ts = t->ts_virtual + (ts - t->ts_real);
141 
142  if(t->nolimit_head_idx != IDXLIST_INVAL) {
143  // Nolimit queue has work - immediate timeout
144  fprintf(stderr, "QMan nolimit has work\n");
145  return 0;
146  }
147 
148  uint32_t idx = t->head_idx[0];
149  if(idx != IDXLIST_INVAL) {
150  struct queue *q = &t->queues[idx];
151 
152  if(timestamp_lessthaneq(t, q->next_ts, ret_ts)) {
153  // Fired in the past - immediate timeout
154  return 0;
155  } else {
156  // Timeout in the future - return difference
157  return rel_time(ret_ts, q->next_ts) / 1000;
158  }
159  }
160 
161  // List empty - no timeout
162  return -1;
163 }
164 
165 int qman_poll(struct qman_thread *t, unsigned num, unsigned *q_ids,
166  uint16_t *q_bytes)
167 {
168  unsigned x, y;
169  uint32_t ts = timestamp();
170 
171  /* poll nolimit list and skiplist alternating the order between */
172  if (t->nolimit_first) {
173  x = poll_nolimit(t, ts, num, q_ids, q_bytes);
174  y = poll_skiplist(t, ts, num - x, q_ids + x, q_bytes + x);
175  } else {
176  x = poll_skiplist(t, ts, num, q_ids, q_bytes);
177  y = poll_nolimit(t, ts, num - x, q_ids + x, q_bytes + x);
178  }
179  t->nolimit_first = !t->nolimit_first;
180 
181  return x + y;
182 }
183 
184 int qman_set(struct qman_thread *t, uint32_t id, uint32_t rate, uint32_t avail,
185  uint16_t max_chunk, uint8_t flags)
186 {
187 #ifdef FLEXNIC_TRACE_QMAN
188  struct flexnic_trace_entry_qman_set evt = {
189  .id = id, .rate = rate, .avail = avail, .max_chunk = max_chunk,
190  .flags = flags,
191  };
192  trace_event(FLEXNIC_TRACE_EV_QMSET, sizeof(evt), &evt);
193 #endif
194 
195  dprintf("qman_set: id=%u rate=%u avail=%u max_chunk=%u qidx=%u tid=%u\n",
196  id, rate, avail, max_chunk, qidx, tid);
197 
198  if (id >= FLEXNIC_NUM_QMQUEUES) {
199  fprintf(stderr, "qman_set: invalid queue id: %u >= %u\n", id,
200  FLEXNIC_NUM_QMQUEUES);
201  return -1;
202  }
203 
204  set_impl(t, id, rate, avail, max_chunk, flags);
205 
206  return 0;
207 }
208 
210 static void inline set_impl(struct qman_thread *t, uint32_t idx, uint32_t rate,
211  uint32_t avail, uint16_t max_chunk, uint8_t flags)
212 {
213  struct queue *q = &t->queues[idx];
214  int new_avail = 0;
215 
216  if ((flags & QMAN_SET_RATE) != 0) {
217  q->rate = rate;
218  }
219 
220  if ((flags & QMAN_SET_MAXCHUNK) != 0) {
221  q->max_chunk = max_chunk;
222  }
223 
224  if ((flags & QMAN_SET_AVAIL) != 0) {
225  q->avail = avail;
226  new_avail = 1;
227  } else if ((flags & QMAN_ADD_AVAIL) != 0) {
228  q->avail += avail;
229  new_avail = 1;
230  }
231 
232  dprintf("set_impl: t=%p q=%p idx=%u avail=%u rate=%u qflags=%x flags=%x\n", t, q, idx, q->avail, q->rate, q->flags, flags);
233 
234  if (new_avail && q->avail > 0
235  && ((q->flags & (FLAG_INSKIPLIST | FLAG_INNOLIMITL)) == 0)) {
236  queue_activate(t, q, idx);
237  }
238 }
239 
240 /*****************************************************************************/
241 /* Managing no-limit queues */
242 
244 static inline void queue_activate_nolimit(struct qman_thread *t,
245  struct queue *q, uint32_t idx)
246 {
247  struct queue *q_tail;
248 
249  assert((q->flags & (FLAG_INSKIPLIST | FLAG_INNOLIMITL)) == 0);
250 
251  dprintf("queue_activate_nolimit: t=%p q=%p avail=%u rate=%u flags=%x\n", t, q, q->avail, q->rate, q->flags);
252 
253  q->flags |= FLAG_INNOLIMITL;
254  q->next_idxs[0] = IDXLIST_INVAL;
255  if (t->nolimit_tail_idx == IDXLIST_INVAL) {
256  t->nolimit_head_idx = t->nolimit_tail_idx = idx;
257  return;
258  }
259 
260  q_tail = &t->queues[t->nolimit_tail_idx];
261  q_tail->next_idxs[0] = idx;
262  t->nolimit_tail_idx = idx;
263 }
264 
266 static inline unsigned poll_nolimit(struct qman_thread *t, uint32_t cur_ts,
267  unsigned num, unsigned *q_ids, uint16_t *q_bytes)
268 {
269  unsigned cnt;
270  struct queue *q;
271  uint32_t idx;
272 
273  for (cnt = 0; cnt < num && t->nolimit_head_idx != IDXLIST_INVAL;) {
274  idx = t->nolimit_head_idx;
275  q = t->queues + idx;
276 
277  t->nolimit_head_idx = q->next_idxs[0];
278  if (q->next_idxs[0] == IDXLIST_INVAL)
279  t->nolimit_tail_idx = IDXLIST_INVAL;
280 
281  q->flags &= ~FLAG_INNOLIMITL;
282  dprintf("poll_nolimit: t=%p q=%p idx=%u avail=%u rate=%u flags=%x\n", t, q, idx, q->avail, q->rate, q->flags);
283  if (q->avail > 0) {
284  queue_fire(t, q, idx, q_ids + cnt, q_bytes + cnt);
285  cnt++;
286  }
287  }
288 
289  return cnt;
290 }
291 
292 /*****************************************************************************/
293 /* Managing skiplist queues */
294 
295 static inline uint32_t queue_new_ts(struct qman_thread *t, struct queue *q,
296  uint32_t bytes)
297 {
298  return t->ts_virtual + ((uint64_t) bytes * 8 * 1000000) / q->rate;
299 }
300 
302 static inline void queue_activate_skiplist(struct qman_thread *t,
303  struct queue *q, uint32_t q_idx)
304 {
305  uint8_t level;
306  int8_t l;
307  uint32_t preds[QMAN_SKIPLIST_LEVELS];
308  uint32_t pred, idx, ts, max_ts;
309 
310  assert((q->flags & (FLAG_INSKIPLIST | FLAG_INNOLIMITL)) == 0);
311 
312  dprintf("queue_activate_skiplist: t=%p q=%p idx=%u avail=%u rate=%u flags=%x ts_virt=%u next_ts=%u\n", t, q, q_idx, q->avail, q->rate, q->flags,
313  t->ts_virtual, q->next_ts);
314 
315  /* make sure queue has a reasonable next_ts:
316  * - not in the past
317  * - not more than if it just sent max_chunk at the current rate
318  */
319  ts = q->next_ts;
320  max_ts = queue_new_ts(t, q, q->max_chunk);
321  if (timestamp_lessthaneq(t, ts, t->ts_virtual)) {
322  ts = q->next_ts = t->ts_virtual;
323  } else if (!timestamp_lessthaneq(t, ts, max_ts)) {
324  ts = q->next_ts = max_ts;
325  }
326  q->next_ts = ts;
327 
328  /* find predecessors at all levels top-down */
329  pred = IDXLIST_INVAL;
330  for (l = QMAN_SKIPLIST_LEVELS - 1; l >= 0; l--) {
331  idx = (pred != IDXLIST_INVAL ? pred : t->head_idx[l]);
332  while (idx != IDXLIST_INVAL &&
333  timestamp_lessthaneq(t, t->queues[idx].next_ts, ts))
334  {
335  pred = idx;
336  idx = t->queues[idx].next_idxs[l];
337  }
338  preds[l] = pred;
339  dprintf(" pred[%u] = %d\n", l, pred);
340  }
341 
342  /* determine level for this queue */
343  level = queue_level(t);
344  dprintf(" level = %u\n", level);
345 
346  /* insert into skip-list */
347  for (l = QMAN_SKIPLIST_LEVELS - 1; l >= 0; l--) {
348  if (l > level) {
349  q->next_idxs[l] = IDXLIST_INVAL;
350  } else {
351  idx = preds[l];
352  if (idx != IDXLIST_INVAL) {
353  q->next_idxs[l] = t->queues[idx].next_idxs[l];
354  t->queues[idx].next_idxs[l] = q_idx;
355  } else {
356  q->next_idxs[l] = t->head_idx[l];
357  t->head_idx[l] = q_idx;
358  }
359  }
360  }
361 
362  q->flags |= FLAG_INSKIPLIST;
363 }
364 
366 static inline unsigned poll_skiplist(struct qman_thread *t, uint32_t cur_ts,
367  unsigned num, unsigned *q_ids, uint16_t *q_bytes)
368 {
369  unsigned cnt;
370  uint32_t idx, max_vts;
371  int8_t l;
372  struct queue *q;
373 
374  /* maximum virtual time stamp that can be reached */
375  max_vts = t->ts_virtual + (cur_ts - t->ts_real);
376 
377  for (cnt = 0; cnt < num;) {
378  idx = t->head_idx[0];
379 
380  /* no more queues */
381  if (idx == IDXLIST_INVAL) {
382  t->ts_virtual = max_vts;
383  break;
384  }
385 
386  q = &t->queues[idx];
387 
388  /* beyond max_vts */
389  dprintf("poll_skiplist: next_ts=%u vts=%u rts=%u max_vts=%u cur_ts=%u\n",
390  q->next_ts, t->ts_virtual, t->ts_real, max_vts, cur_ts);
391  if (!timestamp_lessthaneq(t, q->next_ts, max_vts)) {
392  t->ts_virtual = max_vts;
393  break;
394  }
395 
396  /* remove queue from skiplist */
397  for (l = 0; l < QMAN_SKIPLIST_LEVELS && t->head_idx[l] == idx; l++) {
398  t->head_idx[l] = q->next_idxs[l];
399  }
400  assert((q->flags & FLAG_INSKIPLIST) != 0);
401  q->flags &= ~FLAG_INSKIPLIST;
402 
403  /* advance virtual timestamp */
404  t->ts_virtual = q->next_ts;
405 
406  dprintf("poll_skiplist: t=%p q=%p idx=%u avail=%u rate=%u flags=%x\n", t, q, idx, q->avail, q->rate, q->flags);
407 
408  if (q->avail > 0) {
409  queue_fire(t, q, idx, q_ids + cnt, q_bytes + cnt);
410  cnt++;
411  }
412  }
413 
414  /* if we reached the limit, update the virtual timestamp correctly */
415  if (cnt == num) {
416  idx = t->head_idx[0];
417  if (idx != IDXLIST_INVAL &&
418  timestamp_lessthaneq(t, t->queues[idx].next_ts, max_vts))
419  {
420  t->ts_virtual = t->queues[idx].next_ts;
421  } else {
422  t->ts_virtual = max_vts;
423  }
424  }
425 
426  t->ts_real = cur_ts;
427  return cnt;
428 }
429 
431 static inline uint8_t queue_level(struct qman_thread *t)
432 {
433  uint8_t x = (__builtin_ffs(utils_rng_gen32(&t->rng)) - 1) / SKIPLIST_BITS;
434  return (x < QMAN_SKIPLIST_LEVELS ? x : QMAN_SKIPLIST_LEVELS - 1);
435 }
436 
437 /*****************************************************************************/
438 
439 static inline void queue_fire(struct qman_thread *t,
440  struct queue *q, uint32_t idx, unsigned *q_id, uint16_t *q_bytes)
441 {
442  uint32_t bytes;
443 
444  assert(q->avail > 0);
445 
446  bytes = (q->avail <= q->max_chunk ? q->avail : q->max_chunk);
447  q->avail -= bytes;
448 
449  dprintf("queue_fire: t=%p q=%p idx=%u gidx=%u bytes=%u avail=%u rate=%u\n", t, q, idx, idx, bytes, q->avail, q->rate);
450  if (q->rate > 0) {
451  q->next_ts = queue_new_ts(t, q, bytes);
452  }
453 
454  if (q->avail > 0) {
455  queue_activate(t, q, idx);
456  }
457 
458  *q_bytes = bytes;
459  *q_id = idx;
460 
461 #ifdef FLEXNIC_TRACE_QMAN
462  struct flexnic_trace_entry_qman_event evt = {
463  .id = *q_id, .bytes = bytes,
464  };
465  trace_event(FLEXNIC_TRACE_EV_QMEVT, sizeof(evt), &evt);
466 #endif
467 }
468 
469 static inline void queue_activate(struct qman_thread *t, struct queue *q,
470  uint32_t idx)
471 {
472  if (q->rate == 0) {
473  queue_activate_nolimit(t, q, idx);
474  } else {
475  queue_activate_skiplist(t, q, idx);
476  }
477 }
478 
479 static inline uint32_t timestamp(void)
480 {
481  static uint64_t freq = 0;
482  uint64_t cycles = rte_get_tsc_cycles();
483 
484  if (freq == 0)
485  freq = rte_get_tsc_hz();
486 
487  cycles *= 1000000000ULL;
488  cycles /= freq;
489  return cycles;
490 }
491 
493 static inline int64_t rel_time(uint32_t cur_ts, uint32_t ts_in)
494 {
495  uint64_t ts = ts_in;
496  const uint64_t middle = (1ULL << (TIMESTAMP_BITS - 1));
497  uint64_t start, end;
498 
499  if (cur_ts < middle) {
500  /* negative interval is split in half */
501  start = (cur_ts - middle) & TIMESTAMP_MASK;
502  end = (1ULL << TIMESTAMP_BITS);
503  if (start <= ts && ts < end) {
504  /* in first half of negative interval, smallest timestamps */
505  return ts - start - middle;
506  } else {
507  /* in second half or in positive interval */
508  return ts - cur_ts;
509  }
510  } else if (cur_ts == middle) {
511  /* intervals not split */
512  return ts - cur_ts;
513  } else {
514  /* higher interval is split */
515  start = 0;
516  end = ((cur_ts + middle) & TIMESTAMP_MASK) + 1;
517  if (start <= cur_ts && ts < end) {
518  /* in second half of positive interval, largest timestamps */
519  return ts + ((1ULL << TIMESTAMP_BITS) - cur_ts);
520  } else {
521  /* in negative interval or first half of positive interval */
522  return ts - cur_ts;
523  }
524  }
525 }
526 
527 static inline int timestamp_lessthaneq(struct qman_thread *t, uint32_t a,
528  uint32_t b)
529 {
530  return rel_time(t->ts_virtual, a) <= rel_time(t->ts_virtual, b);
531 }
Definition: tas_trace.h:61
uint16_t flags
Definition: qman.c:69
uint32_t rate
Definition: qman.c:63
Definition: qman.c:57
Definition: tas_trace.h:70
uint32_t next_ts
Definition: qman.c:61
uint32_t avail
Definition: qman.c:65
uint16_t max_chunk
Definition: qman.c:67
uint32_t next_idxs[QMAN_SKIPLIST_LEVELS]
Definition: qman.c:59