/* * Copyright (c) 2003 Patrick McHardy, <[email protected]> * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License * as published by the Free Software Foundation; either version 2 * of the License, or (at your option) any later version. * * 2003-10-17 - Ported from altq */ /* * Copyright (c) 1997-1999 Carnegie Mellon University. All Rights Reserved. * * Permission to use, copy, modify, and distribute this software and * its documentation is hereby granted (including for commercial or * for-profit use), provided that both the copyright notice and this * permission notice appear in all copies of the software, derivative * works, or modified versions, and any portions thereof. * * THIS SOFTWARE IS EXPERIMENTAL AND IS KNOWN TO HAVE BUGS, SOME OF * WHICH MAY HAVE SERIOUS CONSEQUENCES. CARNEGIE MELLON PROVIDES THIS * SOFTWARE IN ITS ``AS IS'' CONDITION, AND ANY EXPRESS OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH * DAMAGE. * * Carnegie Mellon encourages (but does not require) users of this * software to return any improvements or extensions that they make, * and to grant Carnegie Mellon the rights to redistribute these * changes without encumbrance. */ /* * H-FSC is described in Proceedings of SIGCOMM'97, * "A Hierarchical Fair Service Curve Algorithm for Link-Sharing, * Real-Time and Priority Service" * by Ion Stoica, Hui Zhang, and T. S. Eugene Ng. * * Oleg Cherevko <[email protected]> added the upperlimit for link-sharing. * when a class has an upperlimit, the fit-time is computed from the * upperlimit service curve. the link-sharing scheduler does not schedule * a class whose fit-time exceeds the current time. */ #include <linux/kernel.h> #include <linux/module.h> #include <linux/types.h> #include <linux/errno.h> #include <linux/compiler.h> #include <linux/spinlock.h> #include <linux/skbuff.h> #include <linux/string.h> #include <linux/slab.h> #include <linux/list.h> #include <linux/rbtree.h> #include <linux/init.h> #include <linux/rtnetlink.h> #include <linux/pkt_sched.h> #include <net/netlink.h> #include <net/pkt_sched.h> #include <net/pkt_cls.h> #include <asm/div64.h> /* * kernel internal service curve representation: * coordinates are given by 64 bit unsigned integers. * x-axis: unit is clock count. * y-axis: unit is byte. * * The service curve parameters are converted to the internal * representation. The slope values are scaled to avoid overflow. * the inverse slope values as well as the y-projection of the 1st * segment are kept in order to avoid 64-bit divide operations * that are expensive on 32-bit architectures. */ struct internal_sc { … }; /* runtime service curve */ struct runtime_sc { … }; enum hfsc_class_flags { … }; struct hfsc_class { … }; struct hfsc_sched { … }; #define HT_INFINITY … /* * eligible tree holds backlogged classes being sorted by their eligible times. * there is one eligible tree per hfsc instance. */ static void eltree_insert(struct hfsc_class *cl) { … } static inline void eltree_remove(struct hfsc_class *cl) { … } static inline void eltree_update(struct hfsc_class *cl) { … } /* find the class with the minimum deadline among the eligible classes */ static inline struct hfsc_class * eltree_get_mindl(struct hfsc_sched *q, u64 cur_time) { … } /* find the class with minimum eligible time among the eligible classes */ static inline struct hfsc_class * eltree_get_minel(struct hfsc_sched *q) { … } /* * vttree holds holds backlogged child classes being sorted by their virtual * time. each intermediate class has one vttree. */ static void vttree_insert(struct hfsc_class *cl) { … } static inline void vttree_remove(struct hfsc_class *cl) { … } static inline void vttree_update(struct hfsc_class *cl) { … } static inline struct hfsc_class * vttree_firstfit(struct hfsc_class *cl, u64 cur_time) { … } /* * get the leaf class with the minimum vt in the hierarchy */ static struct hfsc_class * vttree_get_minvt(struct hfsc_class *cl, u64 cur_time) { … } static void cftree_insert(struct hfsc_class *cl) { … } static inline void cftree_remove(struct hfsc_class *cl) { … } static inline void cftree_update(struct hfsc_class *cl) { … } /* * service curve support functions * * external service curve parameters * m: bps * d: us * internal service curve parameters * sm: (bytes/psched_us) << SM_SHIFT * ism: (psched_us/byte) << ISM_SHIFT * dx: psched_us * * The clock source resolution with ktime and PSCHED_SHIFT 10 is 1.024us. * * sm and ism are scaled in order to keep effective digits. * SM_SHIFT and ISM_SHIFT are selected to keep at least 4 effective * digits in decimal using the following table. * * bits/sec 100Kbps 1Mbps 10Mbps 100Mbps 1Gbps * ------------+------------------------------------------------------- * bytes/1.024us 12.8e-3 128e-3 1280e-3 12800e-3 128000e-3 * * 1.024us/byte 78.125 7.8125 0.78125 0.078125 0.0078125 * * So, for PSCHED_SHIFT 10 we need: SM_SHIFT 20, ISM_SHIFT 18. */ #define SM_SHIFT … #define ISM_SHIFT … #define SM_MASK … #define ISM_MASK … static inline u64 seg_x2y(u64 x, u64 sm) { … } static inline u64 seg_y2x(u64 y, u64 ism) { … } /* Convert m (bps) into sm (bytes/psched us) */ static u64 m2sm(u32 m) { … } /* convert m (bps) into ism (psched us/byte) */ static u64 m2ism(u32 m) { … } /* convert d (us) into dx (psched us) */ static u64 d2dx(u32 d) { … } /* convert sm (bytes/psched us) into m (bps) */ static u32 sm2m(u64 sm) { … } /* convert dx (psched us) into d (us) */ static u32 dx2d(u64 dx) { … } static void sc2isc(struct tc_service_curve *sc, struct internal_sc *isc) { … } /* * initialize the runtime service curve with the given internal * service curve starting at (x, y). */ static void rtsc_init(struct runtime_sc *rtsc, struct internal_sc *isc, u64 x, u64 y) { … } /* * calculate the y-projection of the runtime service curve by the * given x-projection value */ static u64 rtsc_y2x(struct runtime_sc *rtsc, u64 y) { … } static u64 rtsc_x2y(struct runtime_sc *rtsc, u64 x) { … } /* * update the runtime service curve by taking the minimum of the current * runtime service curve and the service curve starting at (x, y). */ static void rtsc_min(struct runtime_sc *rtsc, struct internal_sc *isc, u64 x, u64 y) { … } static void init_ed(struct hfsc_class *cl, unsigned int next_len) { … } static void update_ed(struct hfsc_class *cl, unsigned int next_len) { … } static inline void update_d(struct hfsc_class *cl, unsigned int next_len) { … } static inline void update_cfmin(struct hfsc_class *cl) { … } static void init_vf(struct hfsc_class *cl, unsigned int len) { … } static void update_vf(struct hfsc_class *cl, unsigned int len, u64 cur_time) { … } static unsigned int qdisc_peek_len(struct Qdisc *sch) { … } static void hfsc_adjust_levels(struct hfsc_class *cl) { … } static inline struct hfsc_class * hfsc_find_class(u32 classid, struct Qdisc *sch) { … } static void hfsc_change_rsc(struct hfsc_class *cl, struct tc_service_curve *rsc, u64 cur_time) { … } static void hfsc_change_fsc(struct hfsc_class *cl, struct tc_service_curve *fsc) { … } static void hfsc_change_usc(struct hfsc_class *cl, struct tc_service_curve *usc, u64 cur_time) { … } static void hfsc_upgrade_rt(struct hfsc_class *cl) { … } static const struct nla_policy hfsc_policy[TCA_HFSC_MAX + 1] = …; static int hfsc_change_class(struct Qdisc *sch, u32 classid, u32 parentid, struct nlattr **tca, unsigned long *arg, struct netlink_ext_ack *extack) { … } static void hfsc_destroy_class(struct Qdisc *sch, struct hfsc_class *cl) { … } static int hfsc_delete_class(struct Qdisc *sch, unsigned long arg, struct netlink_ext_ack *extack) { … } static struct hfsc_class * hfsc_classify(struct sk_buff *skb, struct Qdisc *sch, int *qerr) { … } static int hfsc_graft_class(struct Qdisc *sch, unsigned long arg, struct Qdisc *new, struct Qdisc **old, struct netlink_ext_ack *extack) { … } static struct Qdisc * hfsc_class_leaf(struct Qdisc *sch, unsigned long arg) { … } static void hfsc_qlen_notify(struct Qdisc *sch, unsigned long arg) { … } static unsigned long hfsc_search_class(struct Qdisc *sch, u32 classid) { … } static unsigned long hfsc_bind_tcf(struct Qdisc *sch, unsigned long parent, u32 classid) { … } static void hfsc_unbind_tcf(struct Qdisc *sch, unsigned long arg) { … } static struct tcf_block *hfsc_tcf_block(struct Qdisc *sch, unsigned long arg, struct netlink_ext_ack *extack) { … } static int hfsc_dump_sc(struct sk_buff *skb, int attr, struct internal_sc *sc) { … } static int hfsc_dump_curves(struct sk_buff *skb, struct hfsc_class *cl) { … } static int hfsc_dump_class(struct Qdisc *sch, unsigned long arg, struct sk_buff *skb, struct tcmsg *tcm) { … } static int hfsc_dump_class_stats(struct Qdisc *sch, unsigned long arg, struct gnet_dump *d) { … } static void hfsc_walk(struct Qdisc *sch, struct qdisc_walker *arg) { … } static void hfsc_schedule_watchdog(struct Qdisc *sch) { … } static int hfsc_init_qdisc(struct Qdisc *sch, struct nlattr *opt, struct netlink_ext_ack *extack) { … } static int hfsc_change_qdisc(struct Qdisc *sch, struct nlattr *opt, struct netlink_ext_ack *extack) { … } static void hfsc_reset_class(struct hfsc_class *cl) { … } static void hfsc_reset_qdisc(struct Qdisc *sch) { … } static void hfsc_destroy_qdisc(struct Qdisc *sch) { … } static int hfsc_dump_qdisc(struct Qdisc *sch, struct sk_buff *skb) { … } static int hfsc_enqueue(struct sk_buff *skb, struct Qdisc *sch, struct sk_buff **to_free) { … } static struct sk_buff * hfsc_dequeue(struct Qdisc *sch) { … } static const struct Qdisc_class_ops hfsc_class_ops = …; static struct Qdisc_ops hfsc_qdisc_ops __read_mostly = …; MODULE_ALIAS_NET_SCH(…) …; static int __init hfsc_init(void) { … } static void __exit hfsc_cleanup(void) { … } MODULE_LICENSE(…) …; MODULE_DESCRIPTION(…) …; module_init(…) …; module_exit(hfsc_cleanup);
Codebase Browser
linux