1 /*-
2  * SPDX-License-Identifier: BSD-2-Clause
5  * Copyright (c) 2000-2002 Luigi Rizzo, Universita` di Pisa
20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
59 #define MAX64(x,y)  (( (int64_t) ( (y)-(x) )) > 0 ) ? (y) : (x)
63  * timestamps are computed on 64 bit using fixed point arithmetic.
68  * using an unsigned 32-bit division, and to avoid wraparounds we need
81  * ne_heap (key is Start time) stores not-eligible queues
82  * idle_heap (key=start/finish time) stores idle flows. It must
83  *	support extract-from-middle.
89     struct dn_heap sch_heap;	/* top extract - key Finish  time */
90     struct dn_heap ne_heap;	/* top extract - key Start   time */
91     struct dn_heap idle_heap;	/* random extract - key Start=Finish time */
107  * The scheduler supports per-flow queues and has O(log N) complexity.
109  * WF2Q+ needs to drain entries from the idle heap so that we
113  * from the idle heap.
118     struct dn_heap *h = &si->idle_heap;  in idle_check()
119     while (n-- > 0 && h->elements > 0 &&  in idle_check()
120 		(force || DN_KEY_LT(HEAP_TOP(h)->key, si->V))) {  in idle_check()
121 	struct dn_queue *q = HEAP_TOP(h)->object;  in idle_check()
128         alg_fq->S = alg_fq->F + 1; /* Mark timestamp as invalid. */  in idle_check()
129         si->wsum -= q->fs->fs.par[0];	/* adjust sum of weights */  in idle_check()
130 	if (si->wsum > 0)  in idle_check()
131 		si->inv_wsum = ONE_FP/si->wsum;  in idle_check()
138     struct dn_fsk *fs = q->fs;  in wf2qp_enqueue()
141     uint64_t len = m->m_pkthdr.len;  in wf2qp_enqueue()
143     if (m != q->mq.head) {  in wf2qp_enqueue()
146 	if (m != q->mq.head)	/* queue was already busy */  in wf2qp_enqueue()
150     /* If reach this point, queue q was idle */  in wf2qp_enqueue()
153     if (DN_KEY_LT(alg_fq->F, alg_fq->S)) {  in wf2qp_enqueue()
154         /* F<S means timestamps are invalid ->brand new queue. */  in wf2qp_enqueue()
155         alg_fq->S = si->V;		/* init start time */  in wf2qp_enqueue()
156         si->wsum += fs->fs.par[0];	/* add weight of new queue. */  in wf2qp_enqueue()
157 	si->inv_wsum = ONE_FP/si->wsum;  in wf2qp_enqueue()
158     } else { /* if it was idle then it was in the idle heap */  in wf2qp_enqueue()
159         if (! heap_extract(&si->idle_heap, q))  in wf2qp_enqueue()
161         alg_fq->S = MAX64(alg_fq->F, si->V);	/* compute new S */  in wf2qp_enqueue()
163     alg_fq->F = alg_fq->S + len * alg_fq->inv_w;  in wf2qp_enqueue()
166     if (si->ne_heap.elements == 0 && si->sch_heap.elements == 0)  in wf2qp_enqueue()
167         si->V = MAX64(alg_fq->S, si->V);  in wf2qp_enqueue()
180     if (DN_KEY_LT(si->V, alg_fq->S)) {  in wf2qp_enqueue()
182         if (si->sch_heap.elements == 0)  in wf2qp_enqueue()
184         heap_insert(&si->ne_heap, alg_fq->S, q);  in wf2qp_enqueue()
186         heap_insert(&si->sch_heap, alg_fq->F, q);  in wf2qp_enqueue()
199 	struct dn_heap *sch = &si->sch_heap;  in wf2qp_dequeue()
200 	struct dn_heap *neh = &si->ne_heap;  in wf2qp_dequeue()
203 	if (sch->elements == 0 && neh->elements == 0) {  in wf2qp_dequeue()
204 		/* we have nothing to do. We could kill the idle heap  in wf2qp_dequeue()
208 		si->V = 0;  in wf2qp_dequeue()
209 		si->wsum = 0;	/* should be set already */  in wf2qp_dequeue()
212 	idle_check(si, 1, 0);	/* drain something from the idle heap */  in wf2qp_dequeue()
230 	if (sch->elements == 0 && neh->elements > 0) {  in wf2qp_dequeue()
231 		si->V = MAX64(si->V, HEAP_TOP(neh)->key);  in wf2qp_dequeue()
233 	while (neh->elements > 0 &&  in wf2qp_dequeue()
234 		    DN_KEY_LEQ(HEAP_TOP(neh)->key, si->V)) {  in wf2qp_dequeue()
235 		q = HEAP_TOP(neh)->object;  in wf2qp_dequeue()
238 		heap_insert(sch, alg_fq->F, q);  in wf2qp_dequeue()
243 	q = HEAP_TOP(sch)->object;  in wf2qp_dequeue()
249 	si->V += (uint64_t)(m->m_pkthdr.len) * si->inv_wsum;  in wf2qp_dequeue()
250 	alg_fq->S = alg_fq->F;  /* Update start time. */  in wf2qp_dequeue()
251 	if (q->mq.head == 0) {	/* not backlogged any more. */  in wf2qp_dequeue()
252 		heap_insert(&si->idle_heap, alg_fq->F, q);  in wf2qp_dequeue()
255 		uint64_t len = q->mq.head->m_pkthdr.len;  in wf2qp_dequeue()
256 		alg_fq->F += len * alg_fq->inv_w;  in wf2qp_dequeue()
257 		if (DN_KEY_LEQ(alg_fq->S, si->V)) {  in wf2qp_dequeue()
258 			heap_insert(sch, alg_fq->F, q);  in wf2qp_dequeue()
260 			heap_insert(neh, alg_fq->S, q);  in wf2qp_dequeue()
274 	if (heap_init(&si->idle_heap, 16, ofs) ||  in wf2qp_new_sched()
275 	    heap_init(&si->sch_heap, 16, ofs) ||  in wf2qp_new_sched()
276 	    heap_init(&si->ne_heap, 16, ofs)) {  in wf2qp_new_sched()
277 		heap_free(&si->ne_heap);  in wf2qp_new_sched()
278 		heap_free(&si->sch_heap);  in wf2qp_new_sched()
279 		heap_free(&si->idle_heap);  in wf2qp_new_sched()
290 	heap_free(&si->sch_heap);  in wf2qp_free_sched()
291 	heap_free(&si->ne_heap);  in wf2qp_free_sched()
292 	heap_free(&si->idle_heap);  in wf2qp_free_sched()
300 	ipdn_bound_var(&fs->fs.par[0], 1,  in wf2qp_new_fsk()
310 	_q->ni.oid.subtype = DN_SCHED_WF2QP;  in wf2qp_new_queue()
311 	q->F = 0;	/* not strictly necessary */  in wf2qp_new_queue()
312 	q->S = q->F + 1;    /* mark timestamp as invalid. */  in wf2qp_new_queue()
313         q->inv_w = ONE_FP / _q->fs->fs.par[0];  in wf2qp_new_queue()
314 	if (_q->mq.head != NULL) {  in wf2qp_new_queue()
315 		wf2qp_enqueue(_q->_si, _q, _q->mq.head);  in wf2qp_new_queue()
330 	struct wf2qp_si *si = (struct wf2qp_si *)(q->_si + 1);  in wf2qp_free_queue()
332 	if (alg_fq->S >= alg_fq->F + 1)  in wf2qp_free_queue()
334 	si->wsum -= q->fs->fs.par[0];  in wf2qp_free_queue()
335 	if (si->wsum > 0)  in wf2qp_free_queue()
336 		si->inv_wsum = ONE_FP/si->wsum;  in wf2qp_free_queue()
341 	heap_extract(&si->idle_heap, q);  in wf2qp_free_queue()
342 	heap_extract(&si->ne_heap, q);  in wf2qp_free_queue()
343 	heap_extract(&si->sch_heap, q);  in wf2qp_free_queue()
361 	_SI( .q_datalen = ) sizeof(struct wf2qp_queue) -