1fe267a55SPedro F. Giffuni /*-
24d846d26SWarner Losh * SPDX-License-Identifier: BSD-2-Clause
3fe267a55SPedro F. Giffuni *
43b3a8eb9SGleb Smirnoff * Copyright (c) 2010 Riccardo Panicucci, Universita` di Pisa
53b3a8eb9SGleb Smirnoff * Copyright (c) 2000-2002 Luigi Rizzo, Universita` di Pisa
63b3a8eb9SGleb Smirnoff * All rights reserved
73b3a8eb9SGleb Smirnoff *
83b3a8eb9SGleb Smirnoff * Redistribution and use in source and binary forms, with or without
93b3a8eb9SGleb Smirnoff * modification, are permitted provided that the following conditions
103b3a8eb9SGleb Smirnoff * are met:
113b3a8eb9SGleb Smirnoff * 1. Redistributions of source code must retain the above copyright
123b3a8eb9SGleb Smirnoff * notice, this list of conditions and the following disclaimer.
133b3a8eb9SGleb Smirnoff * 2. Redistributions in binary form must reproduce the above copyright
143b3a8eb9SGleb Smirnoff * notice, this list of conditions and the following disclaimer in the
153b3a8eb9SGleb Smirnoff * documentation and/or other materials provided with the distribution.
163b3a8eb9SGleb Smirnoff *
173b3a8eb9SGleb Smirnoff * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
183b3a8eb9SGleb Smirnoff * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
193b3a8eb9SGleb Smirnoff * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
203b3a8eb9SGleb Smirnoff * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
213b3a8eb9SGleb Smirnoff * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
223b3a8eb9SGleb Smirnoff * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
233b3a8eb9SGleb Smirnoff * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
243b3a8eb9SGleb Smirnoff * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
253b3a8eb9SGleb Smirnoff * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
263b3a8eb9SGleb Smirnoff * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
273b3a8eb9SGleb Smirnoff * SUCH DAMAGE.
283b3a8eb9SGleb Smirnoff */
293b3a8eb9SGleb Smirnoff
303b3a8eb9SGleb Smirnoff /*
313b3a8eb9SGleb Smirnoff */
323b3a8eb9SGleb Smirnoff
333b3a8eb9SGleb Smirnoff #ifdef _KERNEL
343b3a8eb9SGleb Smirnoff #include <sys/malloc.h>
353b3a8eb9SGleb Smirnoff #include <sys/socket.h>
363b3a8eb9SGleb Smirnoff #include <sys/socketvar.h>
373b3a8eb9SGleb Smirnoff #include <sys/kernel.h>
384001fcbeSDon Lewis #include <sys/lock.h>
393b3a8eb9SGleb Smirnoff #include <sys/mbuf.h>
403b3a8eb9SGleb Smirnoff #include <sys/module.h>
414001fcbeSDon Lewis #include <sys/rwlock.h>
423b3a8eb9SGleb Smirnoff #include <net/if.h> /* IFNAMSIZ */
433b3a8eb9SGleb Smirnoff #include <netinet/in.h>
443b3a8eb9SGleb Smirnoff #include <netinet/ip_var.h> /* ipfw_rule_ref */
453b3a8eb9SGleb Smirnoff #include <netinet/ip_fw.h> /* flow_id */
463b3a8eb9SGleb Smirnoff #include <netinet/ip_dummynet.h>
474001fcbeSDon Lewis #include <netpfil/ipfw/ip_fw_private.h>
483b3a8eb9SGleb Smirnoff #include <netpfil/ipfw/dn_heap.h>
493b3a8eb9SGleb Smirnoff #include <netpfil/ipfw/ip_dn_private.h>
5091336b40SDon Lewis #ifdef NEW_AQM
5191336b40SDon Lewis #include <netpfil/ipfw/dn_aqm.h>
5291336b40SDon Lewis #endif
533b3a8eb9SGleb Smirnoff #include <netpfil/ipfw/dn_sched.h>
543b3a8eb9SGleb Smirnoff #else
553b3a8eb9SGleb Smirnoff #include <dn_test.h>
563b3a8eb9SGleb Smirnoff #endif
573b3a8eb9SGleb Smirnoff
583b3a8eb9SGleb Smirnoff #ifndef MAX64
593b3a8eb9SGleb Smirnoff #define MAX64(x,y) (( (int64_t) ( (y)-(x) )) > 0 ) ? (y) : (x)
603b3a8eb9SGleb Smirnoff #endif
613b3a8eb9SGleb Smirnoff
623b3a8eb9SGleb Smirnoff /*
633b3a8eb9SGleb Smirnoff * timestamps are computed on 64 bit using fixed point arithmetic.
643b3a8eb9SGleb Smirnoff * LMAX_BITS, WMAX_BITS are the max number of bits for the packet len
653b3a8eb9SGleb Smirnoff * and sum of weights, respectively. FRAC_BITS is the number of
663b3a8eb9SGleb Smirnoff * fractional bits. We want FRAC_BITS >> WMAX_BITS to avoid too large
673b3a8eb9SGleb Smirnoff * errors when computing the inverse, FRAC_BITS < 32 so we can do 1/w
683b3a8eb9SGleb Smirnoff * using an unsigned 32-bit division, and to avoid wraparounds we need
693b3a8eb9SGleb Smirnoff * LMAX_BITS + WMAX_BITS + FRAC_BITS << 64
703b3a8eb9SGleb Smirnoff * As an example
713b3a8eb9SGleb Smirnoff * FRAC_BITS = 26, LMAX_BITS=14, WMAX_BITS = 19
723b3a8eb9SGleb Smirnoff */
733b3a8eb9SGleb Smirnoff #ifndef FRAC_BITS
743b3a8eb9SGleb Smirnoff #define FRAC_BITS 28 /* shift for fixed point arithmetic */
753b3a8eb9SGleb Smirnoff #define ONE_FP (1UL << FRAC_BITS)
763b3a8eb9SGleb Smirnoff #endif
773b3a8eb9SGleb Smirnoff
783b3a8eb9SGleb Smirnoff /*
793b3a8eb9SGleb Smirnoff * Private information for the scheduler instance:
803b3a8eb9SGleb Smirnoff * sch_heap (key is Finish time) returns the next queue to serve
813b3a8eb9SGleb Smirnoff * ne_heap (key is Start time) stores not-eligible queues
823b3a8eb9SGleb Smirnoff * idle_heap (key=start/finish time) stores idle flows. It must
833b3a8eb9SGleb Smirnoff * support extract-from-middle.
843b3a8eb9SGleb Smirnoff * A flow is only in 1 of the three heaps.
853b3a8eb9SGleb Smirnoff * XXX todo: use a more efficient data structure, e.g. a tree sorted
863b3a8eb9SGleb Smirnoff * by F with min_subtree(S) in each node
873b3a8eb9SGleb Smirnoff */
883b3a8eb9SGleb Smirnoff struct wf2qp_si {
893b3a8eb9SGleb Smirnoff struct dn_heap sch_heap; /* top extract - key Finish time */
903b3a8eb9SGleb Smirnoff struct dn_heap ne_heap; /* top extract - key Start time */
913b3a8eb9SGleb Smirnoff struct dn_heap idle_heap; /* random extract - key Start=Finish time */
923b3a8eb9SGleb Smirnoff uint64_t V; /* virtual time */
933b3a8eb9SGleb Smirnoff uint32_t inv_wsum; /* inverse of sum of weights */
943b3a8eb9SGleb Smirnoff uint32_t wsum; /* sum of weights */
953b3a8eb9SGleb Smirnoff };
963b3a8eb9SGleb Smirnoff
973b3a8eb9SGleb Smirnoff struct wf2qp_queue {
983b3a8eb9SGleb Smirnoff struct dn_queue _q;
993b3a8eb9SGleb Smirnoff uint64_t S, F; /* start time, finish time */
1003b3a8eb9SGleb Smirnoff uint32_t inv_w; /* ONE_FP / weight */
1013b3a8eb9SGleb Smirnoff int32_t heap_pos; /* position (index) of struct in heap */
1023b3a8eb9SGleb Smirnoff };
1033b3a8eb9SGleb Smirnoff
1043b3a8eb9SGleb Smirnoff /*
1053b3a8eb9SGleb Smirnoff * This file implements a WF2Q+ scheduler as it has been in dummynet
1063b3a8eb9SGleb Smirnoff * since 2000.
1073b3a8eb9SGleb Smirnoff * The scheduler supports per-flow queues and has O(log N) complexity.
1083b3a8eb9SGleb Smirnoff *
1093b3a8eb9SGleb Smirnoff * WF2Q+ needs to drain entries from the idle heap so that we
1103b3a8eb9SGleb Smirnoff * can keep the sum of weights up to date. We can do it whenever
1113b3a8eb9SGleb Smirnoff * we get a chance, or periodically, or following some other
1123b3a8eb9SGleb Smirnoff * strategy. The function idle_check() drains at most N elements
1133b3a8eb9SGleb Smirnoff * from the idle heap.
1143b3a8eb9SGleb Smirnoff */
1153b3a8eb9SGleb Smirnoff static void
idle_check(struct wf2qp_si * si,int n,int force)1163b3a8eb9SGleb Smirnoff idle_check(struct wf2qp_si *si, int n, int force)
1173b3a8eb9SGleb Smirnoff {
1183b3a8eb9SGleb Smirnoff struct dn_heap *h = &si->idle_heap;
1193b3a8eb9SGleb Smirnoff while (n-- > 0 && h->elements > 0 &&
1203b3a8eb9SGleb Smirnoff (force || DN_KEY_LT(HEAP_TOP(h)->key, si->V))) {
1213b3a8eb9SGleb Smirnoff struct dn_queue *q = HEAP_TOP(h)->object;
1223b3a8eb9SGleb Smirnoff struct wf2qp_queue *alg_fq = (struct wf2qp_queue *)q;
1233b3a8eb9SGleb Smirnoff
1243b3a8eb9SGleb Smirnoff heap_extract(h, NULL);
1253b3a8eb9SGleb Smirnoff /* XXX to let the flowset delete the queue we should
1263b3a8eb9SGleb Smirnoff * mark it as 'unused' by the scheduler.
1273b3a8eb9SGleb Smirnoff */
1283b3a8eb9SGleb Smirnoff alg_fq->S = alg_fq->F + 1; /* Mark timestamp as invalid. */
1293b3a8eb9SGleb Smirnoff si->wsum -= q->fs->fs.par[0]; /* adjust sum of weights */
1303b3a8eb9SGleb Smirnoff if (si->wsum > 0)
1313b3a8eb9SGleb Smirnoff si->inv_wsum = ONE_FP/si->wsum;
1323b3a8eb9SGleb Smirnoff }
1333b3a8eb9SGleb Smirnoff }
1343b3a8eb9SGleb Smirnoff
1353b3a8eb9SGleb Smirnoff static int
wf2qp_enqueue(struct dn_sch_inst * _si,struct dn_queue * q,struct mbuf * m)1363b3a8eb9SGleb Smirnoff wf2qp_enqueue(struct dn_sch_inst *_si, struct dn_queue *q, struct mbuf *m)
1373b3a8eb9SGleb Smirnoff {
1383b3a8eb9SGleb Smirnoff struct dn_fsk *fs = q->fs;
1393b3a8eb9SGleb Smirnoff struct wf2qp_si *si = (struct wf2qp_si *)(_si + 1);
1403b3a8eb9SGleb Smirnoff struct wf2qp_queue *alg_fq;
1413b3a8eb9SGleb Smirnoff uint64_t len = m->m_pkthdr.len;
1423b3a8eb9SGleb Smirnoff
1433b3a8eb9SGleb Smirnoff if (m != q->mq.head) {
1443b3a8eb9SGleb Smirnoff if (dn_enqueue(q, m, 0)) /* packet was dropped */
1453b3a8eb9SGleb Smirnoff return 1;
1463b3a8eb9SGleb Smirnoff if (m != q->mq.head) /* queue was already busy */
1473b3a8eb9SGleb Smirnoff return 0;
1483b3a8eb9SGleb Smirnoff }
1493b3a8eb9SGleb Smirnoff
1503b3a8eb9SGleb Smirnoff /* If reach this point, queue q was idle */
1513b3a8eb9SGleb Smirnoff alg_fq = (struct wf2qp_queue *)q;
1523b3a8eb9SGleb Smirnoff
1533b3a8eb9SGleb Smirnoff if (DN_KEY_LT(alg_fq->F, alg_fq->S)) {
1543b3a8eb9SGleb Smirnoff /* F<S means timestamps are invalid ->brand new queue. */
1553b3a8eb9SGleb Smirnoff alg_fq->S = si->V; /* init start time */
1563b3a8eb9SGleb Smirnoff si->wsum += fs->fs.par[0]; /* add weight of new queue. */
1573b3a8eb9SGleb Smirnoff si->inv_wsum = ONE_FP/si->wsum;
1583b3a8eb9SGleb Smirnoff } else { /* if it was idle then it was in the idle heap */
1590ba9cb5eSKristof Provost if (! heap_extract(&si->idle_heap, q))
1600ba9cb5eSKristof Provost return 1;
1613b3a8eb9SGleb Smirnoff alg_fq->S = MAX64(alg_fq->F, si->V); /* compute new S */
1623b3a8eb9SGleb Smirnoff }
1633b3a8eb9SGleb Smirnoff alg_fq->F = alg_fq->S + len * alg_fq->inv_w;
1643b3a8eb9SGleb Smirnoff
1653b3a8eb9SGleb Smirnoff /* if nothing is backlogged, make sure this flow is eligible */
1663b3a8eb9SGleb Smirnoff if (si->ne_heap.elements == 0 && si->sch_heap.elements == 0)
1673b3a8eb9SGleb Smirnoff si->V = MAX64(alg_fq->S, si->V);
1683b3a8eb9SGleb Smirnoff
1693b3a8eb9SGleb Smirnoff /*
1703b3a8eb9SGleb Smirnoff * Look at eligibility. A flow is not eligibile if S>V (when
1713b3a8eb9SGleb Smirnoff * this happens, it means that there is some other flow already
1723b3a8eb9SGleb Smirnoff * scheduled for the same pipe, so the sch_heap cannot be
1733b3a8eb9SGleb Smirnoff * empty). If the flow is not eligible we just store it in the
1743b3a8eb9SGleb Smirnoff * ne_heap. Otherwise, we store in the sch_heap.
1753b3a8eb9SGleb Smirnoff * Note that for all flows in sch_heap (SCH), S_i <= V,
1763b3a8eb9SGleb Smirnoff * and for all flows in ne_heap (NEH), S_i > V.
1773b3a8eb9SGleb Smirnoff * So when we need to compute max(V, min(S_i)) forall i in
1783b3a8eb9SGleb Smirnoff * SCH+NEH, we only need to look into NEH.
1793b3a8eb9SGleb Smirnoff */
1803b3a8eb9SGleb Smirnoff if (DN_KEY_LT(si->V, alg_fq->S)) {
1813b3a8eb9SGleb Smirnoff /* S>V means flow Not eligible. */
1823b3a8eb9SGleb Smirnoff if (si->sch_heap.elements == 0)
1833b3a8eb9SGleb Smirnoff D("++ ouch! not eligible but empty scheduler!");
1843b3a8eb9SGleb Smirnoff heap_insert(&si->ne_heap, alg_fq->S, q);
1853b3a8eb9SGleb Smirnoff } else {
1863b3a8eb9SGleb Smirnoff heap_insert(&si->sch_heap, alg_fq->F, q);
1873b3a8eb9SGleb Smirnoff }
1883b3a8eb9SGleb Smirnoff return 0;
1893b3a8eb9SGleb Smirnoff }
1903b3a8eb9SGleb Smirnoff
1913b3a8eb9SGleb Smirnoff /* XXX invariant: sch > 0 || V >= min(S in neh) */
1923b3a8eb9SGleb Smirnoff static struct mbuf *
wf2qp_dequeue(struct dn_sch_inst * _si)1933b3a8eb9SGleb Smirnoff wf2qp_dequeue(struct dn_sch_inst *_si)
1943b3a8eb9SGleb Smirnoff {
1953b3a8eb9SGleb Smirnoff /* Access scheduler instance private data */
1963b3a8eb9SGleb Smirnoff struct wf2qp_si *si = (struct wf2qp_si *)(_si + 1);
1973b3a8eb9SGleb Smirnoff struct mbuf *m;
1983b3a8eb9SGleb Smirnoff struct dn_queue *q;
1993b3a8eb9SGleb Smirnoff struct dn_heap *sch = &si->sch_heap;
2003b3a8eb9SGleb Smirnoff struct dn_heap *neh = &si->ne_heap;
2013b3a8eb9SGleb Smirnoff struct wf2qp_queue *alg_fq;
2023b3a8eb9SGleb Smirnoff
2033b3a8eb9SGleb Smirnoff if (sch->elements == 0 && neh->elements == 0) {
2043b3a8eb9SGleb Smirnoff /* we have nothing to do. We could kill the idle heap
2053b3a8eb9SGleb Smirnoff * altogether and reset V
2063b3a8eb9SGleb Smirnoff */
2073b3a8eb9SGleb Smirnoff idle_check(si, 0x7fffffff, 1);
2083b3a8eb9SGleb Smirnoff si->V = 0;
2093b3a8eb9SGleb Smirnoff si->wsum = 0; /* should be set already */
2103b3a8eb9SGleb Smirnoff return NULL; /* quick return if nothing to do */
2113b3a8eb9SGleb Smirnoff }
2123b3a8eb9SGleb Smirnoff idle_check(si, 1, 0); /* drain something from the idle heap */
2133b3a8eb9SGleb Smirnoff
2143b3a8eb9SGleb Smirnoff /* make sure at least one element is eligible, bumping V
2153b3a8eb9SGleb Smirnoff * and moving entries that have become eligible.
2163b3a8eb9SGleb Smirnoff * We need to repeat the first part twice, before and
2173b3a8eb9SGleb Smirnoff * after extracting the candidate, or enqueue() will
2183b3a8eb9SGleb Smirnoff * find the data structure in a wrong state.
2193b3a8eb9SGleb Smirnoff */
2203b3a8eb9SGleb Smirnoff m = NULL;
2213b3a8eb9SGleb Smirnoff for(;;) {
2223b3a8eb9SGleb Smirnoff /*
2233b3a8eb9SGleb Smirnoff * Compute V = max(V, min(S_i)). Remember that all elements
2243b3a8eb9SGleb Smirnoff * in sch have by definition S_i <= V so if sch is not empty,
2253b3a8eb9SGleb Smirnoff * V is surely the max and we must not update it. Conversely,
2263b3a8eb9SGleb Smirnoff * if sch is empty we only need to look at neh.
2273b3a8eb9SGleb Smirnoff * We don't need to move the queues, as it will be done at the
2283b3a8eb9SGleb Smirnoff * next enqueue
2293b3a8eb9SGleb Smirnoff */
2303b3a8eb9SGleb Smirnoff if (sch->elements == 0 && neh->elements > 0) {
2313b3a8eb9SGleb Smirnoff si->V = MAX64(si->V, HEAP_TOP(neh)->key);
2323b3a8eb9SGleb Smirnoff }
2333b3a8eb9SGleb Smirnoff while (neh->elements > 0 &&
2343b3a8eb9SGleb Smirnoff DN_KEY_LEQ(HEAP_TOP(neh)->key, si->V)) {
2353b3a8eb9SGleb Smirnoff q = HEAP_TOP(neh)->object;
2363b3a8eb9SGleb Smirnoff alg_fq = (struct wf2qp_queue *)q;
2373b3a8eb9SGleb Smirnoff heap_extract(neh, NULL);
2383b3a8eb9SGleb Smirnoff heap_insert(sch, alg_fq->F, q);
2393b3a8eb9SGleb Smirnoff }
2403b3a8eb9SGleb Smirnoff if (m) /* pkt found in previous iteration */
2413b3a8eb9SGleb Smirnoff break;
2423b3a8eb9SGleb Smirnoff /* ok we have at least one eligible pkt */
2433b3a8eb9SGleb Smirnoff q = HEAP_TOP(sch)->object;
2443b3a8eb9SGleb Smirnoff alg_fq = (struct wf2qp_queue *)q;
2453b3a8eb9SGleb Smirnoff m = dn_dequeue(q);
2469dac0268SKristof Provost if (m == NULL)
2479dac0268SKristof Provost return NULL;
2483b3a8eb9SGleb Smirnoff heap_extract(sch, NULL); /* Remove queue from heap. */
2493b3a8eb9SGleb Smirnoff si->V += (uint64_t)(m->m_pkthdr.len) * si->inv_wsum;
2503b3a8eb9SGleb Smirnoff alg_fq->S = alg_fq->F; /* Update start time. */
2513b3a8eb9SGleb Smirnoff if (q->mq.head == 0) { /* not backlogged any more. */
2523b3a8eb9SGleb Smirnoff heap_insert(&si->idle_heap, alg_fq->F, q);
2533b3a8eb9SGleb Smirnoff } else { /* Still backlogged. */
2543b3a8eb9SGleb Smirnoff /* Update F, store in neh or sch */
2553b3a8eb9SGleb Smirnoff uint64_t len = q->mq.head->m_pkthdr.len;
2563b3a8eb9SGleb Smirnoff alg_fq->F += len * alg_fq->inv_w;
2573b3a8eb9SGleb Smirnoff if (DN_KEY_LEQ(alg_fq->S, si->V)) {
2583b3a8eb9SGleb Smirnoff heap_insert(sch, alg_fq->F, q);
2593b3a8eb9SGleb Smirnoff } else {
2603b3a8eb9SGleb Smirnoff heap_insert(neh, alg_fq->S, q);
2613b3a8eb9SGleb Smirnoff }
2623b3a8eb9SGleb Smirnoff }
2633b3a8eb9SGleb Smirnoff }
2643b3a8eb9SGleb Smirnoff return m;
2653b3a8eb9SGleb Smirnoff }
2663b3a8eb9SGleb Smirnoff
2673b3a8eb9SGleb Smirnoff static int
wf2qp_new_sched(struct dn_sch_inst * _si)2683b3a8eb9SGleb Smirnoff wf2qp_new_sched(struct dn_sch_inst *_si)
2693b3a8eb9SGleb Smirnoff {
2703b3a8eb9SGleb Smirnoff struct wf2qp_si *si = (struct wf2qp_si *)(_si + 1);
2713b3a8eb9SGleb Smirnoff int ofs = offsetof(struct wf2qp_queue, heap_pos);
2723b3a8eb9SGleb Smirnoff
2733b3a8eb9SGleb Smirnoff /* all heaps support extract from middle */
2743b3a8eb9SGleb Smirnoff if (heap_init(&si->idle_heap, 16, ofs) ||
2753b3a8eb9SGleb Smirnoff heap_init(&si->sch_heap, 16, ofs) ||
2763b3a8eb9SGleb Smirnoff heap_init(&si->ne_heap, 16, ofs)) {
2773b3a8eb9SGleb Smirnoff heap_free(&si->ne_heap);
2783b3a8eb9SGleb Smirnoff heap_free(&si->sch_heap);
2793b3a8eb9SGleb Smirnoff heap_free(&si->idle_heap);
2803b3a8eb9SGleb Smirnoff return ENOMEM;
2813b3a8eb9SGleb Smirnoff }
2823b3a8eb9SGleb Smirnoff return 0;
2833b3a8eb9SGleb Smirnoff }
2843b3a8eb9SGleb Smirnoff
2853b3a8eb9SGleb Smirnoff static int
wf2qp_free_sched(struct dn_sch_inst * _si)2863b3a8eb9SGleb Smirnoff wf2qp_free_sched(struct dn_sch_inst *_si)
2873b3a8eb9SGleb Smirnoff {
2883b3a8eb9SGleb Smirnoff struct wf2qp_si *si = (struct wf2qp_si *)(_si + 1);
2893b3a8eb9SGleb Smirnoff
2903b3a8eb9SGleb Smirnoff heap_free(&si->sch_heap);
2913b3a8eb9SGleb Smirnoff heap_free(&si->ne_heap);
2923b3a8eb9SGleb Smirnoff heap_free(&si->idle_heap);
2933b3a8eb9SGleb Smirnoff
2943b3a8eb9SGleb Smirnoff return 0;
2953b3a8eb9SGleb Smirnoff }
2963b3a8eb9SGleb Smirnoff
2973b3a8eb9SGleb Smirnoff static int
wf2qp_new_fsk(struct dn_fsk * fs)2983b3a8eb9SGleb Smirnoff wf2qp_new_fsk(struct dn_fsk *fs)
2993b3a8eb9SGleb Smirnoff {
3003b3a8eb9SGleb Smirnoff ipdn_bound_var(&fs->fs.par[0], 1,
3013b3a8eb9SGleb Smirnoff 1, 100, "WF2Q+ weight");
3023b3a8eb9SGleb Smirnoff return 0;
3033b3a8eb9SGleb Smirnoff }
3043b3a8eb9SGleb Smirnoff
3053b3a8eb9SGleb Smirnoff static int
wf2qp_new_queue(struct dn_queue * _q)3063b3a8eb9SGleb Smirnoff wf2qp_new_queue(struct dn_queue *_q)
3073b3a8eb9SGleb Smirnoff {
3083b3a8eb9SGleb Smirnoff struct wf2qp_queue *q = (struct wf2qp_queue *)_q;
3093b3a8eb9SGleb Smirnoff
3103b3a8eb9SGleb Smirnoff _q->ni.oid.subtype = DN_SCHED_WF2QP;
3113b3a8eb9SGleb Smirnoff q->F = 0; /* not strictly necessary */
3123b3a8eb9SGleb Smirnoff q->S = q->F + 1; /* mark timestamp as invalid. */
3133b3a8eb9SGleb Smirnoff q->inv_w = ONE_FP / _q->fs->fs.par[0];
3143b3a8eb9SGleb Smirnoff if (_q->mq.head != NULL) {
3153b3a8eb9SGleb Smirnoff wf2qp_enqueue(_q->_si, _q, _q->mq.head);
3163b3a8eb9SGleb Smirnoff }
3173b3a8eb9SGleb Smirnoff return 0;
3183b3a8eb9SGleb Smirnoff }
3193b3a8eb9SGleb Smirnoff
3203b3a8eb9SGleb Smirnoff /*
3213b3a8eb9SGleb Smirnoff * Called when the infrastructure removes a queue (e.g. flowset
3223b3a8eb9SGleb Smirnoff * is reconfigured). Nothing to do if we did not 'own' the queue,
3233b3a8eb9SGleb Smirnoff * otherwise remove it from the right heap and adjust the sum
3243b3a8eb9SGleb Smirnoff * of weights.
3253b3a8eb9SGleb Smirnoff */
3263b3a8eb9SGleb Smirnoff static int
wf2qp_free_queue(struct dn_queue * q)3273b3a8eb9SGleb Smirnoff wf2qp_free_queue(struct dn_queue *q)
3283b3a8eb9SGleb Smirnoff {
3293b3a8eb9SGleb Smirnoff struct wf2qp_queue *alg_fq = (struct wf2qp_queue *)q;
3303b3a8eb9SGleb Smirnoff struct wf2qp_si *si = (struct wf2qp_si *)(q->_si + 1);
3313b3a8eb9SGleb Smirnoff
3323b3a8eb9SGleb Smirnoff if (alg_fq->S >= alg_fq->F + 1)
3333b3a8eb9SGleb Smirnoff return 0; /* nothing to do, not in any heap */
3343b3a8eb9SGleb Smirnoff si->wsum -= q->fs->fs.par[0];
3353b3a8eb9SGleb Smirnoff if (si->wsum > 0)
3363b3a8eb9SGleb Smirnoff si->inv_wsum = ONE_FP/si->wsum;
3373b3a8eb9SGleb Smirnoff
3383b3a8eb9SGleb Smirnoff /* extract from the heap. XXX TODO we may need to adjust V
3393b3a8eb9SGleb Smirnoff * to make sure the invariants hold.
3403b3a8eb9SGleb Smirnoff */
3413b3a8eb9SGleb Smirnoff heap_extract(&si->idle_heap, q);
3423b3a8eb9SGleb Smirnoff heap_extract(&si->ne_heap, q);
3433b3a8eb9SGleb Smirnoff heap_extract(&si->sch_heap, q);
3440ba9cb5eSKristof Provost
3453b3a8eb9SGleb Smirnoff return 0;
3463b3a8eb9SGleb Smirnoff }
3473b3a8eb9SGleb Smirnoff
3483b3a8eb9SGleb Smirnoff /*
3493b3a8eb9SGleb Smirnoff * WF2Q+ scheduler descriptor
3503b3a8eb9SGleb Smirnoff * contains the type of the scheduler, the name, the size of the
3513b3a8eb9SGleb Smirnoff * structures and function pointers.
3523b3a8eb9SGleb Smirnoff */
3533b3a8eb9SGleb Smirnoff static struct dn_alg wf2qp_desc = {
3543b3a8eb9SGleb Smirnoff _SI( .type = ) DN_SCHED_WF2QP,
3553b3a8eb9SGleb Smirnoff _SI( .name = ) "WF2Q+",
3563b3a8eb9SGleb Smirnoff _SI( .flags = ) DN_MULTIQUEUE,
3573b3a8eb9SGleb Smirnoff
3583b3a8eb9SGleb Smirnoff /* we need extra space in the si and the queue */
3593b3a8eb9SGleb Smirnoff _SI( .schk_datalen = ) 0,
3603b3a8eb9SGleb Smirnoff _SI( .si_datalen = ) sizeof(struct wf2qp_si),
3613b3a8eb9SGleb Smirnoff _SI( .q_datalen = ) sizeof(struct wf2qp_queue) -
3623b3a8eb9SGleb Smirnoff sizeof(struct dn_queue),
3633b3a8eb9SGleb Smirnoff
3643b3a8eb9SGleb Smirnoff _SI( .enqueue = ) wf2qp_enqueue,
3653b3a8eb9SGleb Smirnoff _SI( .dequeue = ) wf2qp_dequeue,
3663b3a8eb9SGleb Smirnoff
3673b3a8eb9SGleb Smirnoff _SI( .config = ) NULL,
3683b3a8eb9SGleb Smirnoff _SI( .destroy = ) NULL,
3693b3a8eb9SGleb Smirnoff _SI( .new_sched = ) wf2qp_new_sched,
3703b3a8eb9SGleb Smirnoff _SI( .free_sched = ) wf2qp_free_sched,
3713b3a8eb9SGleb Smirnoff
3723b3a8eb9SGleb Smirnoff _SI( .new_fsk = ) wf2qp_new_fsk,
3733b3a8eb9SGleb Smirnoff _SI( .free_fsk = ) NULL,
3743b3a8eb9SGleb Smirnoff
3753b3a8eb9SGleb Smirnoff _SI( .new_queue = ) wf2qp_new_queue,
3763b3a8eb9SGleb Smirnoff _SI( .free_queue = ) wf2qp_free_queue,
37791336b40SDon Lewis #ifdef NEW_AQM
37891336b40SDon Lewis _SI( .getconfig = ) NULL,
37991336b40SDon Lewis #endif
38091336b40SDon Lewis
3813b3a8eb9SGleb Smirnoff };
3823b3a8eb9SGleb Smirnoff
3833b3a8eb9SGleb Smirnoff DECLARE_DNSCHED_MODULE(dn_wf2qp, &wf2qp_desc);
384