cachepc-linux

Fork of AMDESE/linux with modifications for CachePC side-channel attack
git clone https://git.sinitax.com/sinitax/cachepc-linux
Log | Files | Refs | README | LICENSE | sfeed.txt

codel.h (6000B)

      1#ifndef __NET_SCHED_CODEL_H
      2#define __NET_SCHED_CODEL_H
      3
      4/*
      5 * Codel - The Controlled-Delay Active Queue Management algorithm
      6 *
      7 *  Copyright (C) 2011-2012 Kathleen Nichols <nichols@pollere.com>
      8 *  Copyright (C) 2011-2012 Van Jacobson <van@pollere.net>
      9 *  Copyright (C) 2012 Michael D. Taht <dave.taht@bufferbloat.net>
     10 *  Copyright (C) 2012,2015 Eric Dumazet <edumazet@google.com>
     11 *
     12 * Redistribution and use in source and binary forms, with or without
     13 * modification, are permitted provided that the following conditions
     14 * are met:
     15 * 1. Redistributions of source code must retain the above copyright
     16 *    notice, this list of conditions, and the following disclaimer,
     17 *    without modification.
     18 * 2. Redistributions in binary form must reproduce the above copyright
     19 *    notice, this list of conditions and the following disclaimer in the
     20 *    documentation and/or other materials provided with the distribution.
     21 * 3. The names of the authors may not be used to endorse or promote products
     22 *    derived from this software without specific prior written permission.
     23 *
     24 * Alternatively, provided that this notice is retained in full, this
     25 * software may be distributed under the terms of the GNU General
     26 * Public License ("GPL") version 2, in which case the provisions of the
     27 * GPL apply INSTEAD OF those given above.
     28 *
     29 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     30 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     31 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
     32 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
     33 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     34 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
     35 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     36 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     37 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     38 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
     39 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
     40 * DAMAGE.
     41 *
     42 */
     43
     44#include <linux/types.h>
     45#include <linux/ktime.h>
     46#include <linux/skbuff.h>
     47
     48/* Controlling Queue Delay (CoDel) algorithm
     49 * =========================================
     50 * Source : Kathleen Nichols and Van Jacobson
     51 * http://queue.acm.org/detail.cfm?id=2209336
     52 *
     53 * Implemented on linux by Dave Taht and Eric Dumazet
     54 */
     55
     56
     57/* CoDel uses a 1024 nsec clock, encoded in u32
     58 * This gives a range of 2199 seconds, because of signed compares
     59 */
     60typedef u32 codel_time_t;
     61typedef s32 codel_tdiff_t;
     62#define CODEL_SHIFT 10
     63#define MS2TIME(a) ((a * NSEC_PER_MSEC) >> CODEL_SHIFT)
     64
     65static inline codel_time_t codel_get_time(void)
     66{
     67	u64 ns = ktime_get_ns();
     68
     69	return ns >> CODEL_SHIFT;
     70}
     71
     72/* Dealing with timer wrapping, according to RFC 1982, as desc in wikipedia:
     73 *  https://en.wikipedia.org/wiki/Serial_number_arithmetic#General_Solution
     74 * codel_time_after(a,b) returns true if the time a is after time b.
     75 */
     76#define codel_time_after(a, b)						\
     77	(typecheck(codel_time_t, a) &&					\
     78	 typecheck(codel_time_t, b) &&					\
     79	 ((s32)((a) - (b)) > 0))
     80#define codel_time_before(a, b) 	codel_time_after(b, a)
     81
     82#define codel_time_after_eq(a, b)					\
     83	(typecheck(codel_time_t, a) &&					\
     84	 typecheck(codel_time_t, b) &&					\
     85	 ((s32)((a) - (b)) >= 0))
     86#define codel_time_before_eq(a, b)	codel_time_after_eq(b, a)
     87
     88static inline u32 codel_time_to_us(codel_time_t val)
     89{
     90	u64 valns = ((u64)val << CODEL_SHIFT);
     91
     92	do_div(valns, NSEC_PER_USEC);
     93	return (u32)valns;
     94}
     95
     96/**
     97 * struct codel_params - contains codel parameters
     98 * @target:	target queue size (in time units)
     99 * @ce_threshold:  threshold for marking packets with ECN CE
    100 * @interval:	width of moving time window
    101 * @mtu:	device mtu, or minimal queue backlog in bytes.
    102 * @ecn:	is Explicit Congestion Notification enabled
    103 * @ce_threshold_selector: apply ce_threshold to packets matching this value
    104 *                         in the diffserv/ECN byte of the IP header
    105 * @ce_threshold_mask: mask to apply to ce_threshold_selector comparison
    106 */
    107struct codel_params {
    108	codel_time_t	target;
    109	codel_time_t	ce_threshold;
    110	codel_time_t	interval;
    111	u32		mtu;
    112	bool		ecn;
    113	u8		ce_threshold_selector;
    114	u8		ce_threshold_mask;
    115};
    116
    117/**
    118 * struct codel_vars - contains codel variables
    119 * @count:		how many drops we've done since the last time we
    120 *			entered dropping state
    121 * @lastcount:		count at entry to dropping state
    122 * @dropping:		set to true if in dropping state
    123 * @rec_inv_sqrt:	reciprocal value of sqrt(count) >> 1
    124 * @first_above_time:	when we went (or will go) continuously above target
    125 *			for interval
    126 * @drop_next:		time to drop next packet, or when we dropped last
    127 * @ldelay:		sojourn time of last dequeued packet
    128 */
    129struct codel_vars {
    130	u32		count;
    131	u32		lastcount;
    132	bool		dropping;
    133	u16		rec_inv_sqrt;
    134	codel_time_t	first_above_time;
    135	codel_time_t	drop_next;
    136	codel_time_t	ldelay;
    137};
    138
    139#define REC_INV_SQRT_BITS (8 * sizeof(u16)) /* or sizeof_in_bits(rec_inv_sqrt) */
    140/* needed shift to get a Q0.32 number from rec_inv_sqrt */
    141#define REC_INV_SQRT_SHIFT (32 - REC_INV_SQRT_BITS)
    142
    143/**
    144 * struct codel_stats - contains codel shared variables and stats
    145 * @maxpacket:	largest packet we've seen so far
    146 * @drop_count:	temp count of dropped packets in dequeue()
    147 * @drop_len:	bytes of dropped packets in dequeue()
    148 * ecn_mark:	number of packets we ECN marked instead of dropping
    149 * ce_mark:	number of packets CE marked because sojourn time was above ce_threshold
    150 */
    151struct codel_stats {
    152	u32		maxpacket;
    153	u32		drop_count;
    154	u32		drop_len;
    155	u32		ecn_mark;
    156	u32		ce_mark;
    157};
    158
    159#define CODEL_DISABLED_THRESHOLD INT_MAX
    160
    161typedef u32 (*codel_skb_len_t)(const struct sk_buff *skb);
    162typedef codel_time_t (*codel_skb_time_t)(const struct sk_buff *skb);
    163typedef void (*codel_skb_drop_t)(struct sk_buff *skb, void *ctx);
    164typedef struct sk_buff * (*codel_skb_dequeue_t)(struct codel_vars *vars,
    165						void *ctx);
    166
    167#endif