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 * $FreeBSD$ 323b3a8eb9SGleb Smirnoff */ 333b3a8eb9SGleb Smirnoff 343b3a8eb9SGleb Smirnoff #ifdef _KERNEL 353b3a8eb9SGleb Smirnoff #include <sys/malloc.h> 363b3a8eb9SGleb Smirnoff #include <sys/socket.h> 373b3a8eb9SGleb Smirnoff #include <sys/socketvar.h> 383b3a8eb9SGleb Smirnoff #include <sys/kernel.h> 394001fcbeSDon Lewis #include <sys/lock.h> 403b3a8eb9SGleb Smirnoff #include <sys/mbuf.h> 413b3a8eb9SGleb Smirnoff #include <sys/module.h> 424001fcbeSDon Lewis #include <sys/rwlock.h> 433b3a8eb9SGleb Smirnoff #include <net/if.h> /* IFNAMSIZ */ 443b3a8eb9SGleb Smirnoff #include <netinet/in.h> 453b3a8eb9SGleb Smirnoff #include <netinet/ip_var.h> /* ipfw_rule_ref */ 463b3a8eb9SGleb Smirnoff #include <netinet/ip_fw.h> /* flow_id */ 473b3a8eb9SGleb Smirnoff #include <netinet/ip_dummynet.h> 484001fcbeSDon Lewis #include <netpfil/ipfw/ip_fw_private.h> 493b3a8eb9SGleb Smirnoff #include <netpfil/ipfw/dn_heap.h> 503b3a8eb9SGleb Smirnoff #include <netpfil/ipfw/ip_dn_private.h> 5191336b40SDon Lewis #ifdef NEW_AQM 5291336b40SDon Lewis #include <netpfil/ipfw/dn_aqm.h> 5391336b40SDon Lewis #endif 543b3a8eb9SGleb Smirnoff #include <netpfil/ipfw/dn_sched.h> 553b3a8eb9SGleb Smirnoff #else 563b3a8eb9SGleb Smirnoff #include <dn_test.h> 573b3a8eb9SGleb Smirnoff #endif 583b3a8eb9SGleb Smirnoff 593b3a8eb9SGleb Smirnoff #ifndef MAX64 603b3a8eb9SGleb Smirnoff #define MAX64(x,y) (( (int64_t) ( (y)-(x) )) > 0 ) ? (y) : (x) 613b3a8eb9SGleb Smirnoff #endif 623b3a8eb9SGleb Smirnoff 633b3a8eb9SGleb Smirnoff /* 643b3a8eb9SGleb Smirnoff * timestamps are computed on 64 bit using fixed point arithmetic. 653b3a8eb9SGleb Smirnoff * LMAX_BITS, WMAX_BITS are the max number of bits for the packet len 663b3a8eb9SGleb Smirnoff * and sum of weights, respectively. FRAC_BITS is the number of 673b3a8eb9SGleb Smirnoff * fractional bits. We want FRAC_BITS >> WMAX_BITS to avoid too large 683b3a8eb9SGleb Smirnoff * errors when computing the inverse, FRAC_BITS < 32 so we can do 1/w 693b3a8eb9SGleb Smirnoff * using an unsigned 32-bit division, and to avoid wraparounds we need 703b3a8eb9SGleb Smirnoff * LMAX_BITS + WMAX_BITS + FRAC_BITS << 64 713b3a8eb9SGleb Smirnoff * As an example 723b3a8eb9SGleb Smirnoff * FRAC_BITS = 26, LMAX_BITS=14, WMAX_BITS = 19 733b3a8eb9SGleb Smirnoff */ 743b3a8eb9SGleb Smirnoff #ifndef FRAC_BITS 753b3a8eb9SGleb Smirnoff #define FRAC_BITS 28 /* shift for fixed point arithmetic */ 763b3a8eb9SGleb Smirnoff #define ONE_FP (1UL << FRAC_BITS) 773b3a8eb9SGleb Smirnoff #endif 783b3a8eb9SGleb Smirnoff 793b3a8eb9SGleb Smirnoff /* 803b3a8eb9SGleb Smirnoff * Private information for the scheduler instance: 813b3a8eb9SGleb Smirnoff * sch_heap (key is Finish time) returns the next queue to serve 823b3a8eb9SGleb Smirnoff * ne_heap (key is Start time) stores not-eligible queues 833b3a8eb9SGleb Smirnoff * idle_heap (key=start/finish time) stores idle flows. It must 843b3a8eb9SGleb Smirnoff * support extract-from-middle. 853b3a8eb9SGleb Smirnoff * A flow is only in 1 of the three heaps. 863b3a8eb9SGleb Smirnoff * XXX todo: use a more efficient data structure, e.g. a tree sorted 873b3a8eb9SGleb Smirnoff * by F with min_subtree(S) in each node 883b3a8eb9SGleb Smirnoff */ 893b3a8eb9SGleb Smirnoff struct wf2qp_si { 903b3a8eb9SGleb Smirnoff struct dn_heap sch_heap; /* top extract - key Finish time */ 913b3a8eb9SGleb Smirnoff struct dn_heap ne_heap; /* top extract - key Start time */ 923b3a8eb9SGleb Smirnoff struct dn_heap idle_heap; /* random extract - key Start=Finish time */ 933b3a8eb9SGleb Smirnoff uint64_t V; /* virtual time */ 943b3a8eb9SGleb Smirnoff uint32_t inv_wsum; /* inverse of sum of weights */ 953b3a8eb9SGleb Smirnoff uint32_t wsum; /* sum of weights */ 963b3a8eb9SGleb Smirnoff }; 973b3a8eb9SGleb Smirnoff 983b3a8eb9SGleb Smirnoff struct wf2qp_queue { 993b3a8eb9SGleb Smirnoff struct dn_queue _q; 1003b3a8eb9SGleb Smirnoff uint64_t S, F; /* start time, finish time */ 1013b3a8eb9SGleb Smirnoff uint32_t inv_w; /* ONE_FP / weight */ 1023b3a8eb9SGleb Smirnoff int32_t heap_pos; /* position (index) of struct in heap */ 1033b3a8eb9SGleb Smirnoff }; 1043b3a8eb9SGleb Smirnoff 1053b3a8eb9SGleb Smirnoff /* 1063b3a8eb9SGleb Smirnoff * This file implements a WF2Q+ scheduler as it has been in dummynet 1073b3a8eb9SGleb Smirnoff * since 2000. 1083b3a8eb9SGleb Smirnoff * The scheduler supports per-flow queues and has O(log N) complexity. 1093b3a8eb9SGleb Smirnoff * 1103b3a8eb9SGleb Smirnoff * WF2Q+ needs to drain entries from the idle heap so that we 1113b3a8eb9SGleb Smirnoff * can keep the sum of weights up to date. We can do it whenever 1123b3a8eb9SGleb Smirnoff * we get a chance, or periodically, or following some other 1133b3a8eb9SGleb Smirnoff * strategy. The function idle_check() drains at most N elements 1143b3a8eb9SGleb Smirnoff * from the idle heap. 1153b3a8eb9SGleb Smirnoff */ 1163b3a8eb9SGleb Smirnoff static void 1173b3a8eb9SGleb Smirnoff idle_check(struct wf2qp_si *si, int n, int force) 1183b3a8eb9SGleb Smirnoff { 1193b3a8eb9SGleb Smirnoff struct dn_heap *h = &si->idle_heap; 1203b3a8eb9SGleb Smirnoff while (n-- > 0 && h->elements > 0 && 1213b3a8eb9SGleb Smirnoff (force || DN_KEY_LT(HEAP_TOP(h)->key, si->V))) { 1223b3a8eb9SGleb Smirnoff struct dn_queue *q = HEAP_TOP(h)->object; 1233b3a8eb9SGleb Smirnoff struct wf2qp_queue *alg_fq = (struct wf2qp_queue *)q; 1243b3a8eb9SGleb Smirnoff 1253b3a8eb9SGleb Smirnoff heap_extract(h, NULL); 1263b3a8eb9SGleb Smirnoff /* XXX to let the flowset delete the queue we should 1273b3a8eb9SGleb Smirnoff * mark it as 'unused' by the scheduler. 1283b3a8eb9SGleb Smirnoff */ 1293b3a8eb9SGleb Smirnoff alg_fq->S = alg_fq->F + 1; /* Mark timestamp as invalid. */ 1303b3a8eb9SGleb Smirnoff si->wsum -= q->fs->fs.par[0]; /* adjust sum of weights */ 1313b3a8eb9SGleb Smirnoff if (si->wsum > 0) 1323b3a8eb9SGleb Smirnoff si->inv_wsum = ONE_FP/si->wsum; 1333b3a8eb9SGleb Smirnoff } 1343b3a8eb9SGleb Smirnoff } 1353b3a8eb9SGleb Smirnoff 1363b3a8eb9SGleb Smirnoff static int 1373b3a8eb9SGleb Smirnoff wf2qp_enqueue(struct dn_sch_inst *_si, struct dn_queue *q, struct mbuf *m) 1383b3a8eb9SGleb Smirnoff { 1393b3a8eb9SGleb Smirnoff struct dn_fsk *fs = q->fs; 1403b3a8eb9SGleb Smirnoff struct wf2qp_si *si = (struct wf2qp_si *)(_si + 1); 1413b3a8eb9SGleb Smirnoff struct wf2qp_queue *alg_fq; 1423b3a8eb9SGleb Smirnoff uint64_t len = m->m_pkthdr.len; 1433b3a8eb9SGleb Smirnoff 1443b3a8eb9SGleb Smirnoff if (m != q->mq.head) { 1453b3a8eb9SGleb Smirnoff if (dn_enqueue(q, m, 0)) /* packet was dropped */ 1463b3a8eb9SGleb Smirnoff return 1; 1473b3a8eb9SGleb Smirnoff if (m != q->mq.head) /* queue was already busy */ 1483b3a8eb9SGleb Smirnoff return 0; 1493b3a8eb9SGleb Smirnoff } 1503b3a8eb9SGleb Smirnoff 1513b3a8eb9SGleb Smirnoff /* If reach this point, queue q was idle */ 1523b3a8eb9SGleb Smirnoff alg_fq = (struct wf2qp_queue *)q; 1533b3a8eb9SGleb Smirnoff 1543b3a8eb9SGleb Smirnoff if (DN_KEY_LT(alg_fq->F, alg_fq->S)) { 1553b3a8eb9SGleb Smirnoff /* F<S means timestamps are invalid ->brand new queue. */ 1563b3a8eb9SGleb Smirnoff alg_fq->S = si->V; /* init start time */ 1573b3a8eb9SGleb Smirnoff si->wsum += fs->fs.par[0]; /* add weight of new queue. */ 1583b3a8eb9SGleb Smirnoff si->inv_wsum = ONE_FP/si->wsum; 1593b3a8eb9SGleb Smirnoff } else { /* if it was idle then it was in the idle heap */ 1603b3a8eb9SGleb Smirnoff heap_extract(&si->idle_heap, q); 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 * 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 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 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 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 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 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 if (q->mq.head == NULL) { 3423b3a8eb9SGleb Smirnoff heap_extract(&si->idle_heap, q); 3433b3a8eb9SGleb Smirnoff } else if (DN_KEY_LT(si->V, alg_fq->S)) { 3443b3a8eb9SGleb Smirnoff heap_extract(&si->ne_heap, q); 3453b3a8eb9SGleb Smirnoff } else { 3463b3a8eb9SGleb Smirnoff heap_extract(&si->sch_heap, q); 3473b3a8eb9SGleb Smirnoff } 3483b3a8eb9SGleb Smirnoff return 0; 3493b3a8eb9SGleb Smirnoff } 3503b3a8eb9SGleb Smirnoff 3513b3a8eb9SGleb Smirnoff /* 3523b3a8eb9SGleb Smirnoff * WF2Q+ scheduler descriptor 3533b3a8eb9SGleb Smirnoff * contains the type of the scheduler, the name, the size of the 3543b3a8eb9SGleb Smirnoff * structures and function pointers. 3553b3a8eb9SGleb Smirnoff */ 3563b3a8eb9SGleb Smirnoff static struct dn_alg wf2qp_desc = { 3573b3a8eb9SGleb Smirnoff _SI( .type = ) DN_SCHED_WF2QP, 3583b3a8eb9SGleb Smirnoff _SI( .name = ) "WF2Q+", 3593b3a8eb9SGleb Smirnoff _SI( .flags = ) DN_MULTIQUEUE, 3603b3a8eb9SGleb Smirnoff 3613b3a8eb9SGleb Smirnoff /* we need extra space in the si and the queue */ 3623b3a8eb9SGleb Smirnoff _SI( .schk_datalen = ) 0, 3633b3a8eb9SGleb Smirnoff _SI( .si_datalen = ) sizeof(struct wf2qp_si), 3643b3a8eb9SGleb Smirnoff _SI( .q_datalen = ) sizeof(struct wf2qp_queue) - 3653b3a8eb9SGleb Smirnoff sizeof(struct dn_queue), 3663b3a8eb9SGleb Smirnoff 3673b3a8eb9SGleb Smirnoff _SI( .enqueue = ) wf2qp_enqueue, 3683b3a8eb9SGleb Smirnoff _SI( .dequeue = ) wf2qp_dequeue, 3693b3a8eb9SGleb Smirnoff 3703b3a8eb9SGleb Smirnoff _SI( .config = ) NULL, 3713b3a8eb9SGleb Smirnoff _SI( .destroy = ) NULL, 3723b3a8eb9SGleb Smirnoff _SI( .new_sched = ) wf2qp_new_sched, 3733b3a8eb9SGleb Smirnoff _SI( .free_sched = ) wf2qp_free_sched, 3743b3a8eb9SGleb Smirnoff 3753b3a8eb9SGleb Smirnoff _SI( .new_fsk = ) wf2qp_new_fsk, 3763b3a8eb9SGleb Smirnoff _SI( .free_fsk = ) NULL, 3773b3a8eb9SGleb Smirnoff 3783b3a8eb9SGleb Smirnoff _SI( .new_queue = ) wf2qp_new_queue, 3793b3a8eb9SGleb Smirnoff _SI( .free_queue = ) wf2qp_free_queue, 38091336b40SDon Lewis #ifdef NEW_AQM 38191336b40SDon Lewis _SI( .getconfig = ) NULL, 38291336b40SDon Lewis #endif 38391336b40SDon Lewis 3843b3a8eb9SGleb Smirnoff }; 3853b3a8eb9SGleb Smirnoff 3863b3a8eb9SGleb Smirnoff DECLARE_DNSCHED_MODULE(dn_wf2qp, &wf2qp_desc); 387