1204591Sluigi# 2204591Sluigi# $FreeBSD: releng/10.2/sys/netpfil/ipfw/dummynet.txt 239124 2012-08-07 07:52:25Z luigi $ 3204591Sluigi# 4204591Sluigi 5204591SluigiNotes on the internal structure of dummynet (2010 version) 6204591Sluigiby Riccardo Panicucci and Luigi Rizzo 7204591SluigiWork supported by the EC project ONELAB2 8204591Sluigi 9204591Sluigi 10204591Sluigi********* 11204591Sluigi* INDEX * 12204591Sluigi********* 13204591SluigiImplementation of new dummynet 14204591Sluigi Internal structure 15204591Sluigi Files 16204591SluigiPacket arrival 17204591Sluigi The reconfiguration routine 18204591Sluigidummynet_task() 19204591SluigiConfiguration 20204591Sluigi Add a pipe 21204591Sluigi Add a scheduler 22204591Sluigi Add a flowset 23204591SluigiListing object 24204591SluigiDelete of object 25204591Sluigi Delete a pipe 26204591Sluigi Delete a flowset 27204591Sluigi Delete a scheduler 28204591SluigiCompatibility with FreeBSD7.2 and FreeBSD 8 ipfw binary 29204591Sluigi ip_dummynet_glue.c 30204591Sluigi ip_fw_glue.c 31204591SluigiHow to configure dummynet 32204591SluigiHow to implement a new scheduler 33204591Sluigi 34204591Sluigi 35204591Sluigi 36204591SluigiOPEN ISSUES 37204591Sluigi------------------------------ 38204591Sluigi20100131 deleting RR causes infinite loop 39204591Sluigi presumably in the rr_free_queue() call -- seems to hang 40204591Sluigi forever when deleting a live flow 41204591Sluigi------------------------------ 42204591Sluigi 43204591SluigiDummynet is a traffic shaper and network emulator. Packets are 44204591Sluigiselected by an external filter such as ipfw, and passed to the emulator 45204591Sluigiwith a tag such as "pipe 10" or "queue 5" which tells what to 46204591Sluigido with the packet. As an example 47204591Sluigi 48204591Sluigi ipfw add queue 5 icmp from 10.0.0.2 to all 49204591Sluigi 50204591SluigiAll packets with the same tag belong to a "flowset", or a set 51204591Sluigiof flows which can be further partitioned according to a mask. 52204591SluigiFlowsets are then passed to a scheduler for processing. The 53204591Sluigiassociation of flowsets and schedulers is configurable e.g. 54204591Sluigi 55204591Sluigi ipfw queue 5 config sched 10 weight 3 flow_mask xxxx 56204591Sluigi ipfw queue 8 config sched 10 weight 1 ... 57204591Sluigi ipfw queue 3 config sched 20 weight 1 ... 58204591Sluigi 59204591Sluigi"sched 10" represents one or more scheduler instances, 60204591Sluigiselected through a mask on the 5-tuple itself. 61204591Sluigi 62204591Sluigi ipfw sched 20 config type FIFO sched_mask yyy ... 63204591Sluigi 64204591SluigiThere are in fact two masks applied to each packet: 65204591Sluigi+ the "sched_mask" sends packets arriving to a scheduler_id to 66204591Sluigi one of many instances. 67204591Sluigi+ the "flow_mask" together with the flowset_id is used to 68204591Sluigi collect packets into independent flows on each scheduler. 69204591Sluigi 70204591SluigiAs an example, we can have 71204591Sluigi ipfw queue 5 config sched 10 flow_mask src-ip 0x000000ff 72204591Sluigi ipfw sched 10 config type WF2Q+ sched_mask src-ip 0xffffff00 73204591Sluigi 74204591Sluigimeans that sched 10 will have one instance per /24 source subnet, 75204591Sluigiand within that, each individual source will be a flow. 76204591Sluigi 77204591SluigiInternal structure 78204591Sluigi----------------- 79204591SluigiDummynet-related data is split into several data structures, 80204591Sluigipart of them constituting the userland-kernel API, and others 81204591Sluigispecific to the kernel. 82204591SluigiNOTE: for up-to-date details please look at the relevant source 83204591Sluigi headers (ip_dummynet.h, ip_dn_private.h, dn_sched.h) 84204591Sluigi 85204591SluigiUSERLAND-KERNEL API (ip_dummynet.h) 86204591Sluigi 87204591Sluigi struct dn_link: 88204591Sluigi contains data about the physical link such as 89204591Sluigi bandwith, delay, burst size; 90204591Sluigi 91204591Sluigi struct dn_fs: 92204591Sluigi describes a flowset, i.e. a template for queues. 93204591Sluigi Main parameters are the scheduler we attach to, a flow_mask, 94204591Sluigi buckets, queue size, plr, weight, and other scheduler-specific 95204591Sluigi parameters. 96204591Sluigi 97204591Sluigi struct dn_flow 98204591Sluigi contains information on a flow, including masks and 99204591Sluigi statistics 100204591Sluigi 101204591Sluigi struct dn_sch: 102204591Sluigi defines a scheduler (and a link attached to it). 103204591Sluigi Parameters include scheduler type, sched_mask, number of 104204591Sluigi buckets, and possibly other scheduler-specific parameters, 105204591Sluigi 106204591Sluigi struct dn_profile: 107204591Sluigi fields to simulate a delay profile 108204591Sluigi 109204591Sluigi 110204591SluigiKERNEL REPRESENTATION (ip_dn_private.h) 111204591Sluigi 112204591Sluigi struct mq 113204591Sluigi a queue of mbufs with head and tail. 114204591Sluigi 115204591Sluigi struct dn_queue 116204591Sluigi individual queue of packets, created by a flowset using 117204591Sluigi flow_mask and attached to a scheduler instance selected 118204591Sluigi through sched_mask. 119204591Sluigi A dn_queue has a pointer to the dn_fsk (which in turn counts 120204591Sluigi how many queues point to it), a pointer to the 121204591Sluigi dn_sch_inst it attaches to, and is in a hash table in the 122204591Sluigi flowset. scheduler instances also should store queues in 123204591Sluigi their own containers used for scheduling (lists, trees, etc.) 124204591Sluigi CREATE: done on packet arrivals when a flow matches a flowset. 125204591Sluigi DELETE: done only when deleting the parent dn_sch_inst 126204591Sluigi or draining memory. 127204591Sluigi 128204591Sluigi struct dn_fsk 129204591Sluigi includes a dn_fs; a pointer to the dn_schk; a link field 130204591Sluigi for the list of dn_fsk attached to the same scheduler, 131204591Sluigi or for the unlinked list; 132204591Sluigi a refcount for the number of queues pointing to it; 133204591Sluigi The dn_fsk is in a hash table, fshash. 134204591Sluigi CREATE: done on configuration commands. 135204591Sluigi DELETE: on configuration commands. 136204591Sluigi 137204591Sluigi struct dn_sch_inst 138204591Sluigi a scheduler instance, created from a dn_schk applying sched_mask. 139204591Sluigi Contains a delay line, a reference to the parent, and scheduler- 140204591Sluigi specific info. Both dn_sch_inst and its delay line can be in the 141204591Sluigi evheap if they have events to be processed. 142204591Sluigi CREATE: created from a dn_schk applying sched_mask 143204591Sluigi DELETE: configuration command delete a scheduler which in turn 144204591Sluigi sweeps the hash table of instances deleting them 145204591Sluigi 146204591Sluigi struct dn_schk 147204591Sluigi includes dn_sch, dn_link, a pointer to dn_profile, 148204591Sluigi a hash table of dn_sch_inst, a list of dn_fsk 149204591Sluigi attached to it. 150204591Sluigi CREATE: configuration command. If there are flowsets that 151204591Sluigi refer to this number, they are attached and moved 152204591Sluigi to the hash table 153204591Sluigi DELETE: manual, see dn_sch_inst 154204591Sluigi 155204591Sluigi 156204591Sluigi fshash schedhash 157204591Sluigi +---------------+ sched +--------------+ 158204591Sluigi | sched-------------------->| NEW_SCHK| 159204591Sluigi -<----*sch_chain |<-----------------*fsk_list | 160204591Sluigi |NEW_FSK |<----. | [dn_link] | 161204591Sluigi +---------------+ | +--------------+ 162204591Sluigi |qht (hash) | | | siht(hash) | 163204591Sluigi | [dn_queue] | | | [dn_si] | 164204591Sluigi | [dn_queue] | | | [dn_si] | 165204591Sluigi | ... | | | ... | 166204591Sluigi | +--------+ | | | +---------+ | 167204591Sluigi | |dn_queue| | | | |dn_si | | 168204591Sluigi | | fs *----------' | | | | 169204591Sluigi | | si *---------------------->| | | 170204591Sluigi | +---------+ | | +---------+ | 171204591Sluigi +---------------+ +--------------+ 172204591Sluigi 173204591SluigiThe following global data structures contain all 174204591Sluigischedulers and flowsets. 175204591Sluigi 176204591Sluigi- schedhash[x]: contains all scheduler templates in the system. 177204591Sluigi Looked up only on manual configurations, where flowsets 178204591Sluigi are attached to matching schedulers. 179204591Sluigi We have one entry per 'sched X config' command 180204591Sluigi (plus one for each 'pipe X config'). 181204591Sluigi 182204591Sluigi- fshash[x]: contains all flowsets. 183204591Sluigi We do a lookup on this for each packet. 184204591Sluigi We have one entry for each 'queue X config' 185204591Sluigi (plus one for each 'pipe X config'). 186204591Sluigi 187204591SluigiAdditionally, a list that contains all unlinked flowset: 188204591Sluigi- fsu: contains flowset that are not linked with any scheduler. 189204591Sluigi Flowset are put in this list when they refer to a non 190204591Sluigi existing scheduler. 191204591Sluigi We don't need an efficient data structure as we never search 192204591Sluigi here on a packet arrivals. 193204591Sluigi 194204591SluigiScheduler instances and the delay lines associated with each scheduler 195204591Sluigiinstance need to be woken up at certain times. Because we have many 196204591Sluigisuch objects, we keep them in a priority heap (system_heap). 197204591Sluigi 198204591SluigiAlmost all objects in this implementation are preceded by a structure 199204591Sluigi(struct dn_id) which makes it easier to identify them. 200204591Sluigi 201204591Sluigi 202204591SluigiFiles 203204591Sluigi----- 204204591SluigiThe dummynet code is split in several files. 205204591SluigiAll kernel code is in sys/netinet/ipfw except ip_dummynet.h 206204591SluigiAll userland code is in sbin/ipfw. 207204591SluigiFiles are 208204591Sluigi- sys/netinet/ip_dummynet.h defines the kernel-userland API 209204591Sluigi- ip_dn_private.h contains the kernel-specific APIs 210204591Sluigi and data structures 211204591Sluigi- dn_sched.h defines the scheduler API 212204591Sluigi- ip_dummynet.c cointains module glue and sockopt handlers, with all 213204591Sluigi functions to configure and list objects. 214204591Sluigi- ip_dn_io.c contains the functions directly related to packet processing, 215204591Sluigi and run in the critical path. It also contains some functions 216204591Sluigi exported to the schedulers. 217204591Sluigi- dn_heap.[ch] implement a binary heap and a generic hash table 218204591Sluigi- dn_sched_* implement the various scheduler modules 219204591Sluigi 220204591Sluigi- dummynet.c is the file used to implement the user side of dummynet. 221204591Sluigi It contains the function to parsing command line, and functions to 222204591Sluigi show the output of dummynet objects. 223204591SluigiMoreover, there are two new file (ip_dummynet_glue.c and ip_fw_glue.c) that 224204591Sluigiare used to allow compatibility with the "ipfw" binary from FreeBSD 7.2 and 225204591SluigiFreeBSD 8. 226204591Sluigi 227204591SluigiLOCKING 228204591Sluigi======= 229204591SluigiAt the moment the entire processing occurs under a single lock 230204591Sluigiwhich is expected to be acquired in exclusive mode 231204591SluigiDN_BH_WLOCK() / DN_BH_WUNLOCK(). 232204591Sluigi 233204591SluigiIn perspective we aim at the following: 234204591Sluigi- the 'busy' flag, 'pending' list and all structures modified by packet 235204591Sluigi arrivals and departures are protected by the BH_WLOCK. 236204591Sluigi This is normally acquired in exclusive mode by the packet processing 237204591Sluigi functions for short sections of code (exception -- the timer). 238204591Sluigi If 'busy' is not set, we can do regular packet processing. 239204591Sluigi If 'busy' is set, no pieces can be accessed. 240204591Sluigi We must enqueue the packet on 'pending' and return immediately. 241204591Sluigi 242204591Sluigi- the 'busy' flag is set/cleared by long sections of code as follows: 243204591Sluigi UH_WLOCK(); KASSERT(busy == 0); 244204591Sluigi BH_WLOCK(); busy=1; BH_WUNLOCK(); 245204591Sluigi ... do processing ... 246204591Sluigi BH_WLOCK(); busy=0; drain_queue(pending); BH_WUNLOCK(); 247204591Sluigi UH_WUNLOCK(); 248204591Sluigi this normally happens when the upper half has something heavy 249204591Sluigi to do. The prologue and epilogue are not in the critical path. 250204591Sluigi 251204591Sluigi- the main containers (fshash, schedhash, ...) are protected by 252204591Sluigi UH_WLOCK. 253204591Sluigi 254204591SluigiPacket processing 255204591Sluigi================= 256204591SluigiA packet enters dummynet through dummynet_io(). We first lookup 257204591Sluigithe flowset number in fshash using dn_ht_find(), then find the scheduler 258204591Sluigiinstance using ipdn_si_find(), then possibly identify the correct 259204591Sluigiqueue with ipdn_q_find(). 260204591SluigiIf successful, we call the scheduler's enqueue function(), and 261204591Sluigiif needed start I/O on the link calling serve_sched(). 262204591SluigiIf the packet can be returned immediately, this is done by 263204591Sluigileaving *m0 set. Otherwise, the packet is absorbed by dummynet 264204591Sluigiand we simply return, possibly with some appropriate error code. 265204591Sluigi 266204591SluigiReconfiguration 267204591Sluigi--------------- 268204591SluigiReconfiguration is the complex part of the system because we need to 269204591Sluigikeep track of the various objects and containers. 270204591SluigiAt the moment we do not use reference counts for objects so all 271204591Sluigiprocessing must be done under a lock. 272204591Sluigi 273204591SluigiThe main entry points for configuration is the ip_dn_ctl() handler 274204591Sluigifor the IP_DUMMYNET3 sockopt (others are provided only for backward 275204591Sluigicompatibility). Modifications to the configuration call do_config(). 276204591SluigiThe argument is a sequence of blocks each starting with a struct dn_id 277204591Sluigiwhich specifies its content. 278204591SluigiThe first dn_id must contain as obj.id the DN_API_VERSION 279204591SluigiThe obj.type is DN_CMD_CONFIG (followed by actual objects), 280204591SluigiDN_CMD_DELETE (with the correct subtype and list of objects), or 281204591SluigiDN_CMD_FLUSH. 282204591Sluigi 283204591SluigiDN_CMD_CONFIG is followed by objects to add/reconfigure. In general, 284204591Sluigiif an object already exists it is reconfigured, otherwise it is 285204591Sluigicreated in a way that keeps the structure consistent. 286204591SluigiWe have the following objects in the system, normally numbered with 287204591Sluigian identifier N between 1 and 65535. For certain objects we have 288204591Sluigi"shadow" copies numbered I+NMAX and I+ 2*NMAX which are used to 289204591Sluigiimplement certain backward compatibility features. 290204591Sluigi 291204591SluigiIn general we have the following linking 292204591Sluigi 293204591Sluigi TRADITIONAL DUMMYNET QUEUES "queue N config ... pipe M ..." 294204591Sluigi corresponds to a dn_fs object numbered N 295204591Sluigi 296204591Sluigi TRADITIONAL DUMMYNET PIPES "pipe N config ..." 297204591Sluigi dn_fs N+2*NMAX --> dn_sch N+NMAX type FIFO --> dn_link N+NMAX 298204591Sluigi 299204591Sluigi GENERIC SCHEDULER "sched N config ... " 300204591Sluigi [dn_fs N+NMAX] --> dn_sch N --> dn_link N 301204591Sluigi The flowset N+NMAX is created only if the scheduler is not 302204591Sluigi of type MULTIQUEUE. 303204591Sluigi 304204591Sluigi DELAY PROFILE "pipe N config profile ..." 305204591Sluigi it is always attached to an existing dn_link N 306204591Sluigi 307204591SluigiBecause traditional dummynet pipes actually configure both a 308204591Sluigi'standalone' instance and one that can be used by queues, 309204591Sluigiwe do the following: 310204591Sluigi 311204591Sluigi "pipe N config ..." configures: 312204591Sluigi dn_sched N type WF2Q+ 313204591Sluigi dn_sched N+NMAX type FIFO 314204591Sluigi dn_fs N+2NMAX attached to dn_sched N+NMAX 315204591Sluigi dn_pipe N 316204591Sluigi dn_pipe N+NMAX 317204591Sluigi 318204591Sluigi "queue N config" configures 319204591Sluigi dn_fs N 320204591Sluigi 321204591Sluigi "sched N config" configures 322204591Sluigi dn_sched N type as desired 323204591Sluigi dn_fs N+NMAX attached to dn_sched N 324204591Sluigi 325204591Sluigi 326204591Sluigidummynet_task() 327204591Sluigi=============== 328227458SeadlerThe dummynet_task() function is the main dummynet processing function and is 329204591Sluigicalled every tick. This function first calculate the new current time, then 330204591Sluigiit checks if it is the time to wake up object from the system_heap comparing 331204591Sluigithe current time and the key of the heap. Two types of object (really the 332204591Sluigiheap contains pointer to objects) are in the 333204591Sluigisystem_heap: 334204591Sluigi 335204591Sluigi- scheduler instance: if a scheduler instance is waked up, the dequeue() 336204591Sluigi function is called until it has credit. If the dequeue() returns packets, 337204591Sluigi the scheduler instance is inserted in the heap with a new key depending of 338204591Sluigi the data that will be send out. If the scheduler instance remains with 339204591Sluigi some credit, it means that is hasn't other packet to send and so the 340204591Sluigi instance is no longer inserted in the heap. 341204591Sluigi 342204591Sluigi If the scheduler instance extracted from the heap has the DELETE flag set, 343204591Sluigi the dequeue() is not called and the instance is destroyed now. 344204591Sluigi 345204591Sluigi- delay line: when extracting a delay line, the function transmit_event() is 346204591Sluigi called to send out packet from delay line. 347204591Sluigi 348204591Sluigi If the scheduler instance associated with this delay line doesn't exists, 349204591Sluigi the delay line will be delete now. 350204591Sluigi 351204591SluigiConfiguration 352204591Sluigi============= 353204591SluigiTo create a pipe, queue or scheduler, the user should type commands like: 354204591Sluigi"ipfw pipe x config" 355204591Sluigi"ipfw queue y config pipe x" 356204591Sluigi"ipfw pipe x config sched <type>" 357204591Sluigi 358204591SluigiThe userland side of dummynet will prepare a buffer contains data to pass to 359204591Sluigikernel side. 360204591SluigiThe buffer contains all struct needed to configure an object. In more detail, 361204591Sluigito configure a pipe all three structs (dn_link, dn_sch, dn_fs) are needed, 362204591Sluigiplus the delay profile struct if the pipe has a delay profile. 363204591Sluigi 364204591SluigiIf configuring a scheduler only the struct dn_sch is wrote in the buffer, 365204591Sluigiwhile if configuring a flowset only the dn_fs struct is wrote. 366204591Sluigi 367204591SluigiThe first struct in the buffer contains the type of command request, that is 368204591Sluigiif it is configuring a pipe, a queue, or a scheduler. Then there are structs 369204591Sluigineed to configure the object, and finally there is the struct that mark 370204591Sluigithe end of the buffer. 371204591Sluigi 372204591SluigiTo support the insertion of pipe and queue using the old syntax, when adding 373204591Sluigia pipe it's necessary to create a FIFO flowset and a FIFO scheduler, which 374204591Sluigihave a number x + DN_PIPEOFFSET. 375204591Sluigi 376204591SluigiAdd a pipe 377204591Sluigi---------- 378204591SluigiA pipe is only a template for a link. 379204591SluigiIf the pipe already exists, parameters are updated. If a delay profile exists 380204591Sluigiit is deleted and a new one is created. 381204591SluigiIf the pipe doesn't exist a new one is created. After the creation, the 382204591Sluigiflowset unlinked list is scanned to see if there are some flowset that would 383204591Sluigibe linked with this pipe. If so, these flowset will be of wf2q+ type (for 384204591Sluigicompatibility) and a new wf2q+ scheduler is created now. 385204591Sluigi 386204591SluigiAdd a scheduler 387204591Sluigi--------------- 388204591SluigiIf the scheduler already exists, and the type and the mask are the same, the 389204591Sluigischeduler is simply reconfigured calling the config_scheduler() scheduler 390204591Sluigifunction with the RECONFIGURE flag active. 391204591SluigiIf the type or the mask differ, it is necessary to delete the old scheduler 392204591Sluigiand create a new one. 393204591SluigiIf the scheduler doesn't exists, a new one is created. If the scheduler has 394204591Sluigia mask, the hash table is created to store pointers to scheduler instances. 395204591SluigiWhen a new scheduler is created, it is necessary to scan the unlinked 396204591Sluigiflowset list to search eventually flowset that would be linked with this 397204591Sluigischeduler number. If some are found, flowsets became of the type of this 398204591Sluigischeduler and they are configured properly. 399204591Sluigi 400204591SluigiAdd a flowset 401204591Sluigi------------- 402204591SluigiFlowset pointers are store in the system in two list. The unlinked flowset list 403204591Sluigicontains all flowset that aren't linked with a scheduler, the flowset list 404204591Sluigicontains flowset linked to a scheduler, and so they have a type. 405204591SluigiWhen adding a new flowset, first it is checked if the flowset exists (that is, 406204591Sluigiit is in the flowset list) and if it doesn't exists a new flowset is created 407204591Sluigiand added to unlinked flowset list if the scheduler which the flowset would be 408204591Sluigilinked doesn't exists, or added in the flowset list and configured properly if 409204591Sluigithe scheduler exists. If the flowset (before to be created) was in the 410204591Sluigiunlinked flowset list, it is removed and deleted, and then recreated. 411204591SluigiIf the flowset exists, to allow reconfiguration of this flowset, the 412204591Sluigischeduler number and types must match with the one in memory. If this isn't 413204591Sluigiso, the flowset is deleted and a new one will be created. Really, the flowset 414204591Sluigiit isn't deleted now, but it is removed from flowset list and it will be 415204591Sluigideleted later because there could be some queues that are using it. 416204591Sluigi 417204591SluigiListing of object 418204591Sluigi================= 419204591SluigiThe user can request a list of object present in dummynet through the command 420204591Sluigi"ipfw [-v] pipe|queue [x] list|show" 421204591SluigiThe kernel side of dummynet send a buffer to user side that contains all 422204591Sluigipipe, all scheduler, all flowset, plus all scheduler instances and all queues. 423204591SluigiThe dummynet user land will format the output and show only the relevant 424204591Sluigiinformation. 425204591SluigiThe buffer sent start with all pipe from the system. The entire struct dn_link 426204591Sluigiis passed, except the delay_profile struct that is useless in user space. 427204591SluigiAfter pipes, all flowset are wrote in the buffer. The struct contains 428204591Sluigischeduler flowset specific data is linked with the flowset writing the 429204591Sluigi'obj' id of the extension into the 'alg_fs' pointer. 430204591SluigiThen schedulers are wrote. If a scheduler has one or more scheduler instance, 431204591Sluigithese are linked to the parent scheduler writing the id of the parent in the 432204591Sluigi'ptr_sched' pointer. If a scheduler instance has queues, there are wrote in 433204591Sluigithe buffer and linked thorugh the 'obj' and 'sched_inst' pointer. 434204591SluigiFinally, flowsets in the unlinked flowset list are write in the buffer, and 435204591Sluigithen a struct gen in saved in the buffer to mark the last struct in the buffer. 436204591Sluigi 437204591Sluigi 438204591SluigiDelete of object 439204591Sluigi================ 440204591SluigiAn object is usually removed by user through a command like 441204591Sluigi"ipfw pipe|queue x delete". XXX sched? 442204591Sluigiipfw pass to the kernel a struct gen that contains the type and the number 443204591Sluigiof the object to remove 444204591Sluigi 445204591SluigiDelete of pipe x 446204591Sluigi---------------- 447204591SluigiA pipe can be deleted by the user throught the command 'ipfw pipe x delete'. 448204591SluigiTo delete a pipe, the pipe is removed from the pipe list, and then deleted. 449204591SluigiAlso the scheduler associated with this pipe should be deleted. 450204591SluigiFor compatibility with old dummynet syntax, the associated FIFO scheduler and 451204591SluigiFIFO flowset must be deleted. 452204591Sluigi 453204591SluigiDelete of flowset x 454204591Sluigi------------------- 455204591SluigiTo remove a flowset, we must be sure that is no loger referenced by any object. 456204591SluigiIf the flowset to remove is in the unlinked flowset list, there is not any 457204591Sluigiissue, the flowset can be safely removed calling a free() (the flowset 458204591Sluigiextension is not yet created if the flowset is in this list). 459204591SluigiIf the flowset is in the flowset list, first we remove from it so new packet 460204591Sluigiare discarded when arrive. Next, the flowset is marked as delete. 461204591SluigiNow we must check if some queue is using this flowset. 462204591SluigiTo do this, a counter (active_f) is provided. This counter indicate how many 463204591Sluigiqueues exist using this flowset. 464204591SluigiThe active_f counter is automatically incremented when a queue is created 465204591Sluigiand decremented when a queue is deleted. 466204591SluigiIf the counter is 0, the flowset can be safely deleted, and the delete_alg_fs() 467204591Sluigischeduler function is called before deallocate memory. 468204591SluigiIf the counter is not 0, the flowset remain in memory until the counter become 469204591Sluigizero. When a queue is delete (by dn_delete_queue() function) it is checked if 470204591Sluigithe linked flowset is deleting and if so the counter is decrementing. If the 471204591Sluigicounter reaches 0, the flowset is deleted. 472204591SluigiThe deletion of a queue can be done only by the scheduler, or when the scheduler 473204591Sluigiis destroyed. 474204591Sluigi 475204591SluigiDelete of scheduler x 476204591Sluigi--------------------- 477204591SluigiTo delete a scheduler we must be sure that any scheduler instance of this type 478204591Sluigiare in the system_heap. To do so, a counter (inst_counter) is provided. 479204591SluigiThis counter is managed by the system: it is incremented every time it is 480204591Sluigiinserted in the system_heap, and decremented every time it is extracted from it. 481204591SluigiTo delete the scheduler, first we remove it from the scheduler list, so new 482204591Sluigipacket are discarded when they arrive, and mark the scheduler as deleting. 483204591Sluigi 484204591SluigiIf the counter is 0, we can remove the scheduler safely calling the 485204591Sluigireally_deletescheduler() function. This function will scan all scheduler 486204591Sluigiinstances and call the delete_scheduler_instance() function that will delete 487204591Sluigithe instance. When all instance are deleted, the scheduler template is 488204591Sluigideleted calling the delete_scheduler_template(). If the delay line associate 489204591Sluigiwith the scheduler is empty, it is deleted now, else it will be deleted when 490204591Sluigiit will became empy. 491204591SluigiIf the counter was not 0, we wait for it. Every time the dummynet_task() 492204591Sluigifunction extract a scheduler from the system_heap, the counter is decremented. 493204591SluigiIf the scheduler has the delete flag enabled the dequeue() is not called and 494204591Sluigidelete_scheduler_instance() is called to delete the instance. 495204591SluigiObviously this scheduler instance is no loger inserted in the system_heap. 496204591SluigiIf the counter reaches 0, the delete_scheduler_template() function is called 497204591Sluigiall memory is released. 498204591SluigiNOTE: Flowsets that belong to this scheduler are not deleted, so if a new 499204591Sluigi scheduler with the same number is inserted will use these flowsets. 500204591Sluigi To do so, the best approach would be insert these flowset in the 501204591Sluigi unlinked flowset list, but doing this now will be very expensive. 502204591Sluigi So flowsets will remain in memory and linked with a scheduler that no 503204591Sluigi longer exists until a packet belonging to this flowset arrives. When 504204591Sluigi this packet arrives, the reconfigure() function is called because the 505204591Sluigi generation number mismatch with one contains in the flowset and so 506204591Sluigi the flowset will be moved into the flowset unlinked list, or will be 507204591Sluigi linked with the new scheduler if a new one was created. 508204591Sluigi 509204591Sluigi 510204591SluigiCOMPATIBILITY WITH FREEBSD 7.2 AND FREEBSD 8 'IPFW' BINARY 511204591Sluigi========================================================== 512204591SluigiDummynet is not compatible with old ipfw binary because internal structs are 513204591Sluigichanged. Moreover, the old ipfw binary is not compatible with new kernels 514204591Sluigibecause the struct that represents a firewall rule has changed. So, if a user 515204591Sluigiinstall a new kernel on a FreeBSD 7.2, the ipfw (and possibly many other 516204591Sluigicommands) will not work. 517204591SluigiNew dummynet uses a new socket option: IP_DUMMYNET3, used for both set and get. 518204591SluigiThe old option can be used to allow compatibility with the 'ipfw' binary of 519204591Sluigiolder version (tested with 7.2 and 8.0) of FreeBSD. 520204591SluigiTwo file are provided for this purpose: 521204591Sluigi- ip_dummynet_glue.c translates old dummynet requests to the new ones, 522204591Sluigi- ip_fw_glue.c converts the rule format between 7.2 and 8 versions. 523204591SluigiLet see in detail these two files. 524204591Sluigi 525204591SluigiIP_DUMMYNET_GLUE.C 526204591Sluigi------------------ 527204591SluigiThe internal structs of new dummynet are very different from the original. 528204591SluigiBecause of there are some difference from between dummynet in FreeBSD 7.2 and 529204591Sluigidummynet in FreeBSD 8 (the FreeBSD 8 version includes support to pipe delay 530204591Sluigiprofile and burst option), I have to include both header files. I copied 531204591Sluigithe revision 191715 (for version 7.2) and the revision 196045 (for version 8) 532204591Sluigiand I appended a number to each struct to mark them. 533204591Sluigi 534204591SluigiThe main function of this file is ip_dummynet_compat() that is called by 535204591Sluigiip_dn_ctl() when it receive a request of old socket option. 536204591Sluigi 537204591SluigiA global variabile ('is7') store the version of 'ipfw' that FreeBSD is using. 538204591SluigiThis variable is set every time a request of configuration is done, because 539204591Sluigiwith this request we receive a buffer of which size depending of ipfw version. 540204591SluigiBecause of in general the first action is a configuration, this variable is 541204591Sluigiusually set accordly. If the first action is a request of listing of pipes 542204591Sluigior queues, the system cannot know the version of ipfw, and we suppose that 543204591Sluigiversion 7.2 is used. If version is wrong, the output can be senseless, but 544204591Sluigithe application should not crash. 545204591Sluigi 546204591SluigiThere are four request for old dummynet: 547204591Sluigi- IP_DUMMYNET_FLUSH: the flush options have no parameter, so simply the 548204591Sluigi dummynet_flush() function is called; 549204591Sluigi- IP_DUMMYNET_DEL: the delete option need to be translate. 550204591Sluigi It is only necessary to extract the number and the type of the object 551204591Sluigi (pipe or queue) to delete from the buffer received and build a new struct 552204591Sluigi gen contains the right parameters, then call the delete_object() function; 553204591Sluigi- IP_DUMMYNET_CONFIGURE: the configure command receive a buffer depending of 554204591Sluigi the ipfw version. After the properly extraction of all data, that depends 555204591Sluigi by the ipfw version used, new structures are filled and then the dummynet 556204591Sluigi config_link() function is properly called. Note that the 7.2 version does 557204591Sluigi not support some parameter as burst or delay profile. 558204591Sluigi- IP_DUMMYNET_GET: The get command should send to the ipfw the correct buffer 559204591Sluigi depending of its version. There are two function that build the 560204591Sluigi corrected buffer, ip_dummynet_get7() and ip_dummynet_get8(). These 561204591Sluigi functions reproduce the buffer exactly as 'ipfw' expect. The only difference 562204591Sluigi is that the weight parameter for a queue is no loger sent by dummynet and so 563204591Sluigi it is set to 0. 564204591Sluigi Moreover, because of the internal structure has changed, the bucket size 565204591Sluigi of a queue could not be correct, because now all flowset share the hash 566204591Sluigi table. 567204591Sluigi If the version of ipfw is wrong, the output could be senseless or truncated, 568204591Sluigi but the application should not crash. 569204591Sluigi 570204591SluigiIP_FW_GLUE.C 571204591Sluigi------------ 572204591SluigiThe ipfw binary also is used to add rules to FreeBSD firewall. Because of the 573204591Sluigistruct ip_fw is changed from FreeBsd 7.2 to FreeBSD 8, it is necessary 574204591Sluigito write some glue code to allow use ipfw from FreeBSD 7.2 with the kernel 575204591Sluigiprovided with FreeBSD 8. 576204591SluigiThis file contains two functions to convert a rule from FreeBSD 7.2 format to 577204591SluigiFreeBSD 8 format, and viceversa. 578204591SluigiThe conversion should be done when a rule passes from userspace to kernel space 579204591Sluigiand viceversa. 580204591SluigiI have to modify the ip_fw2.c file to manage these two case, and added a 581204591Sluigivariable (is7) to store the ipfw version used, using an approach like the 582204591Sluigiprevious file: 583204591Sluigi- when a new rule is added (option IP_FW_ADD) the is7 variable is set if the 584204591Sluigi size of the rule received corrispond to FreeBSD 7.2 ipfw version. If so, the 585204591Sluigi rule is converted to version 8 calling the function convert_rule_to_8(). 586204591Sluigi Moreover, after the insertion of the rule, the rule is now reconverted to 587204591Sluigi version 7 because the ipfw binary will print it. 588204591Sluigi- when the user request a list of rules (option IP_FW_GET) the is7 variable 589204591Sluigi should be set correctly because we suppose that a configure command was done, 590204591Sluigi else we suppose that the FreeBSD version is 8. The function ipfw_getrules() 591204591Sluigi in ip_fw2.c file return all rules, eventually converted to version 7 (if 592204591Sluigi the is7 is set) to the ipfw binary. 593204591SluigiThe conversion of a rule is quite simple. The only difference between the 594204591Sluigitwo structures (struct ip_fw) is that in the new there is a new field 595204591Sluigi(uint32_t id). So, I copy the entire rule in a buffer and the copy the rule in 596204591Sluigithe right position in the new (or old) struct. The size of commands are not 597204591Sluigichanged, and the copy is done into a cicle. 598204591Sluigi 599204591SluigiHow to configure dummynet 600204591Sluigi========================= 601204591SluigiIt is possible to configure dummynet through two main commands: 602204591Sluigi'ipfw pipe' and 'ipfw queue'. 603204591SluigiTo allow compatibility with old version, it is possible configure dummynet 604204591Sluigiusing the old command syntax. Doing so, obviously, it is only possible to 605204591Sluigiconfigure a FIFO scheduler or a wf2q+ scheduler. 606204591SluigiA new command, 'ipfw pipe x config sched <type>' is supported to add a new 607204591Sluigischeduler to the system. 608204591Sluigi 609204591Sluigi- ipfw pipe x config ... 610204591Sluigi create a new pipe with the link parameters 611204591Sluigi create a new scheduler fifo (x + offset) 612204591Sluigi create a new flowset fifo (x + offset) 613204591Sluigi the mask is eventually stored in the FIFO scheduler 614204591Sluigi 615204591Sluigi- ipfw queue y config pipe x ... 616204591Sluigi create a new flowset y linked to sched x. 617204591Sluigi The type of flowset depends by the specified scheduler. 618204591Sluigi If the scheduler does not exist, this flowset is inserted in a special 619204591Sluigi list and will be not active. 620204591Sluigi If pipe x exists and sched does not exist, a new wf2q+ scheduler is 621204591Sluigi created and the flowset will be linked to this new scheduler (this is 622204591Sluigi done for compatibility with old syntax). 623204591Sluigi 624204591Sluigi- ipfw pipe x config sched <type> ... 625204591Sluigi create a new scheduler x of type <type>. 626204591Sluigi Search into the flowset unlinked list if there are some flowset that 627204591Sluigi should be linked with this new scheduler. 628204591Sluigi 629204591Sluigi- ipfw pipe x delete 630204591Sluigi delete the pipe x 631204591Sluigi delete the scheduler fifo (x + offset) 632204591Sluigi delete the scheduler x 633204591Sluigi delete the flowset fifo (x + offset) 634204591Sluigi 635204591Sluigi- ipfw queue x delete 636204591Sluigi delete the flowset x 637204591Sluigi 638204591Sluigi- ipfw sched x delete ///XXX 639204591Sluigi delete the scheduler x 640204591Sluigi 641204591SluigiFollow now some examples to how configure dummynet: 642204591Sluigi- Ex1: 643204591Sluigi ipfw pipe 10 config bw 1M delay 15 // create a pipe with band and delay 644204591Sluigi A FIFO flowset and scheduler is 645204591Sluigi also created 646204591Sluigi ipfw queue 5 config pipe 10 weight 56 // create a flowset. This flowset 647204591Sluigi will be of wf2q+ because a pipe 10 648204591Sluigi exists. Moreover, the wf2q+ 649204591Sluigi scheduler is created now. 650204591Sluigi- Ex2: 651204591Sluigi ipfw queue 5 config pipe 10 weight 56 // Create a flowset. Scheduler 10 652204591Sluigi does not exist, so this flowset 653204591Sluigi is inserted in the unlinked 654204591Sluigi flowset list. 655204591Sluigi ipfw pipe 10 config bw... // Create a pipe, a FIFO flowset and scheduler. 656204591Sluigi Because of a flowset with 'pipe 10' exists, 657204591Sluigi a wf2q+ scheduler is created now and that 658204591Sluigi flowset is linked with this sceduler. 659204591Sluigi 660204591Sluigi- Ex3: 661204591Sluigi ipfw pipe 10 config bw... // Create a pipe, a FIFO flowset and scheduler. 662204591Sluigi ipfw pipe 10 config sched rr // Create a scheduler of type RR, linked to 663204591Sluigi pipe 10 664204591Sluigi ipfw queue 5 config pipe 10 weight 56 // Create a flowset 5. This flowset 665204591Sluigi will belong to scheduler 10 and 666204591Sluigi it is of type RR 667204591Sluigi 668204591Sluigi- Ex4: 669204591Sluigi ipfw pipe 10 config sched rr // Create a scheduler of type RR, linked to 670204591Sluigi pipe 10 (not exist yet) 671204591Sluigi ipfw pipe 10 config bw... // Create a pipe, a FIFO flowset and scheduler. 672204591Sluigi ipfw queue 5 config pipe 10 weight 56 // Create a flowset 5.This flowset 673204591Sluigi will belong to scheduler 10 and 674204591Sluigi it is of type RR 675204591Sluigi ipfw pipe 10 config sched wf2q+ // Modify the type of scheduler 10. It 676204591Sluigi becomes a wf2q+ scheduler. 677204591Sluigi When a new packet of flowset 5 arrives, 678204591Sluigi the flowset 5 becomes to wf2q+ type. 679204591Sluigi 680204591SluigiHow to implement a new scheduler 681204591Sluigi================================ 682204591SluigiIn dummynet, a scheduler algorithm is represented by two main structs, some 683204591Sluigifunctions and other minor structs. 684204591Sluigi- A struct dn_sch_xyz (where xyz is the 'type' of scheduler algorithm 685204591Sluigi implemented) contains data relative to scheduler, as global parameter that 686204591Sluigi are common to all instances of the scheduler 687204591Sluigi- A struct dn_sch_inst_xyz contains data relative to a single scheduler 688204591Sluigi instance, as local status variable depending for example by flows that 689204591Sluigi are linked with the scheduler, and so on. 690204591SluigiTo add a scheduler to dummynet, the user should type a command like: 691204591Sluigi'ipfw pipe x config sched <type> [mask ... ...]' 692204591SluigiThis command creates a new struct dn_sch_xyz of type <type>, and 693204591Sluigistore the optional parameter in that struct. 694204591Sluigi 695204591SluigiThe parameter mask determines how many scheduler instance of this 696204591Sluigischeduler may exist. For example, it is possible to divide traffic 697204591Sluigidepending on the source port (or destination, or ip address...), 698204591Sluigiso that every scheduler instance act as an independent scheduler. 699204591SluigiIf the mask is not set, all traffic goes to the same instance. 700204591Sluigi 701204591SluigiWhen a packet arrives to a scheduler, the system search the corrected 702204591Sluigischeduler instance, and if it does not exist it is created now (the 703204591Sluigistruct dn_sch_inst_xyz is allocated by the system, and the scheduler 704204591Sluigifills the field correctly). It is a task of the scheduler to create 705204591Sluigithe struct that contains all queues for a scheduler instance. 706204591SluigiDummynet provides some function to create an hash table to store 707204591Sluigiqueues, but the schedule algorithm can choice the own struct. 708204591Sluigi 709204591SluigiTo link a flow to a scheduler, the user should type a command like: 710204591Sluigi'ipfw queue z config pipe x [mask... ...]' 711204591Sluigi 712204591SluigiThis command creates a new 'dn_fs' struct that will be inserted 713204591Sluigiin the system. If the scheduler x exists, this flowset will be 714204591Sluigilinked to that scheduler and the flowset type become the same as 715204591Sluigithe scheduler type. At this point, the function create_alg_fs_xyz() 716204591Sluigiis called to allow store eventually parameter for the flowset that 717204591Sluigidepend by scheduler (for example the 'weight' parameter for a wf2q+ 718204591Sluigischeduler, or some priority...). A parameter mask can be used for 719204591Sluigia flowset. If the mask parameter is set, the scheduler instance can 720204591Sluigiseparate packet according to its flow id (src and dst ip, ports...) 721204591Sluigiand assign it to a separate queue. This is done by the scheduler, 722204591Sluigiso it can ignore the mask if it wants. 723204591Sluigi 724204591SluigiSee now the two main structs: 725204591Sluigistruct dn_sch_xyz { 726204591Sluigi struct gen g; /* important the name g */ 727204591Sluigi /* global params */ 728204591Sluigi}; 729204591Sluigistruct dn_sch_inst_xyz { 730204591Sluigi struct gen g; /* important the name g */ 731204591Sluigi /* params of the instance */ 732204591Sluigi}; 733204591SluigiIt is important to embed the struct gen as first parameter. The struct gen 734204591Sluigicontains some values that the scheduler instance must fill (the 'type' of 735204591Sluigischeduler, the 'len' of the struct...) 736204591SluigiThe function create_scheduler_xyz() should be implemented to initialize global 737204591Sluigiparameters in the first struct, and if memory allocation is done it is 738204591Sluigimandatory to implement the delete_scheduler_template() function to free that 739204591Sluigimemory. 740204591SluigiThe function create_scheduler_instance_xyz() must be implemented even if the 741204591Sluigischeduler instance does not use extra parameters. In this function the struct 742204591Sluigigen fields must be filled with corrected infos. The 743204591Sluigidelete_scheduler_instance_xyz() function must bu implemented if the instance 744204591Sluigihas allocated some memory in the previous function. 745204591Sluigi 746204591SluigiTo store data belonging to a flowset the follow struct is used: 747204591Sluigistruct alg_fs_xyz { 748204591Sluigi struct gen g; 749204591Sluigi /* fill correctly the gen struct 750204591Sluigi g.subtype = DN_XYZ; 751204591Sluigi g.len = sizeof(struct alg_fs_xyz) 752204591Sluigi ... 753204591Sluigi */ 754204591Sluigi /* params for the flow */ 755204591Sluigi}; 756204591SluigiThe create_alg_fs_xyz() function is mandatory, because it must fill the struct 757204591Sluigigen, but the delete_alg_fs_xyz() is mandatory only if the previous function 758204591Sluigihas allocated some memory. 759204591Sluigi 760204591SluigiA struct dn_queue contains packets belonging to a queue and some statistical 761204591Sluigidata. The scheduler could have to store data in this struct, so it must define 762204591Sluigia dn_queue_xyz struct: 763204591Sluigistruct dn_queue_xyz { 764204591Sluigi struct dn_queue q; 765204591Sluigi /* parameter for a queue */ 766204591Sluigi} 767204591Sluigi 768204591SluigiAll structures are allocated by the system. To do so, the scheduler must 769204591Sluigiset the size of its structs in the scheduler descriptor: 770204591Sluigischeduler_size: sizeof(dn_sch_xyz) 771204591Sluigischeduler_i_size: sizeof(dn_sch_inst_xyz) 772204591Sluigiflowset_size: sizeof(alg_fs_xyz) 773204591Sluigiqueue_size: sizeof(dn_queue_xyz); 774204591SluigiThe scheduler_size could be 0, but other struct must have at least a struct gen. 775204591Sluigi 776204591Sluigi 777204591SluigiAfter the definition of structs, it is necessary to implement the 778204591Sluigischeduler functions. 779204591Sluigi 780204591Sluigi- int (*config_scheduler)(char *command, void *sch, int reconfigure); 781204591Sluigi Configure a scheduler, or reconfigure if 'reconfigure' == 1. 782204591Sluigi This function performs additional allocation and initialization of global 783204591Sluigi parameter for this scheduler. 784204591Sluigi If memory is allocated here, the delete_scheduler_template() function 785204591Sluigi should be implemented to remove this memory. 786204591Sluigi- int (*delete_scheduler_template)(void* sch); 787204591Sluigi Delete a scheduler template. This function is mandatory if the scheduler 788204591Sluigi uses extra data respect the struct dn_sch. 789204591Sluigi- int (*create_scheduler_instance)(void *s); 790204591Sluigi Create a new scheduler instance. The system allocate the necessary memory 791204591Sluigi and the schedulet can access it using the 's' pointer. 792204591Sluigi The scheduler instance stores all queues, and to do this can use the 793204591Sluigi hash table provided by the system. 794204591Sluigi- int (*delete_scheduler_instance)(void *s); 795204591Sluigi Delete a scheduler instance. It is important to free memory allocated 796204591Sluigi by create_scheduler_instance() function. The memory allocated by system 797204591Sluigi is freed by the system itself. The struct contains all queue also has 798204591Sluigi to be deleted. 799204591Sluigi- int (*enqueue)(void *s, struct gen *f, struct mbuf *m, 800204591Sluigi struct ipfw_flow_id *id); 801204591Sluigi Called when a packet arrives. The packet 'm' belongs to the scheduler 802204591Sluigi instance 's', has a flowset 'f' and the flowid 'id' has already been 803204591Sluigi masked. The enqueue() must call dn_queue_packet(q, m) function to really 804204591Sluigi enqueue packet in the queue q. The queue 'q' is chosen by the scheduler 805204591Sluigi and if it does not exist should be created calling the dn_create_queue() 806204591Sluigi function. If the schedule want to drop the packet, it must call the 807204591Sluigi dn_drop_packet() function and then return 1. 808204591Sluigi- struct mbuf * (*dequeue)(void *s); 809204591Sluigi Called when the timer expires (or when a packet arrives and the scheduler 810204591Sluigi instance is idle). 811204591Sluigi This function is called when at least a packet can be send out. The 812204591Sluigi scheduler choices the packet and returns it; if no packet are in the 813204591Sluigi schedulerinstance, the function must return NULL. 814204591Sluigi Before return a packet, it is important to call the function 815204591Sluigi dn_return_packet() to update some statistic of the queue and update the 816204591Sluigi queue counters. 817204591Sluigi- int (*drain_queue)(void *s, int flag); 818204591Sluigi The system request to scheduler to delete all queues that is not using 819204591Sluigi to free memory. The flag parameter indicate if a queue must be deleted 820204591Sluigi even if it is active. 821204591Sluigi 822204591Sluigi- int (*create_alg_fs)(char *command, struct gen *g, int reconfigure); 823204591Sluigi It is called when a flowset is linked with a scheduler. This is done 824204591Sluigi when the scheduler is defined, so we can know the type of flowset. 825204591Sluigi The function initialize the flowset paramenter parsing the command 826204591Sluigi line. The parameter will be stored in the g struct that have the right 827204591Sluigi size allocated by the system. If the reconfigure flag is set, it means 828204591Sluigi that the flowset is reconfiguring 829204591Sluigi- int (*delete_alg_fs)(struct gen *f); 830204591Sluigi It is called when a flowset is deleting. Must remove the memory allocate 831204591Sluigi by the create_alg_fs() function. 832204591Sluigi 833204591Sluigi- int (*create_queue_alg)(struct dn_queue *q, struct gen *f); 834204591Sluigi Called when a queue is created. The function should link the queue 835204591Sluigi to the struct used by the scheduler instance to store all queues. 836204591Sluigi- int (*delete_queue_alg)(struct dn_queue *q); 837204591Sluigi Called when a queue is deleting. The function should remove extra data 838204591Sluigi and update the struct contains all queues in the scheduler instance. 839204591Sluigi 840204591SluigiThe struct scheduler represent the scheduler descriptor that is passed to 841204591Sluigidummynet when a scheduler module is loaded. 842239124SluigiThis struct contains the type of scheduler, the length of all structs and 843204591Sluigiall function pointers. 844204591SluigiIf a function is not implemented should be initialize to NULL. Some functions 845204591Sluigiare mandatory, other are mandatory if some memory should be freed. 846204591SluigiMandatory functions: 847204591Sluigi- create_scheduler_instance() 848204591Sluigi- enqueue() 849204591Sluigi- dequeue() 850204591Sluigi- create_alg_fs() 851204591Sluigi- drain_queue() 852204591SluigiOptional functions: 853204591Sluigi- config_scheduler() 854204591Sluigi- create_queue_alg() 855204591SluigiMandatory functions if the corresponding create...() has allocated memory: 856204591Sluigi- delete_scheduler_template() 857204591Sluigi- delete_scheduler_instance() 858204591Sluigi- delete_alg_fs() 859204591Sluigi- delete_queue_alg() 860204591Sluigi 861