xref: /freebsd/sys/netpfil/ipfw/dummynet.txt (revision c697fb7f)

#
# $FreeBSD$
#

Notes on the internal structure of dummynet (2010 version)
by Riccardo Panicucci and Luigi Rizzo
Work supported by the EC project ONELAB2


*********
* INDEX *
*********
Implementation of new dummynet
    Internal structure
    Files
Packet arrival
    The reconfiguration routine
dummynet_task()
Configuration
    Add a pipe
    Add a scheduler
    Add a flowset
Listing object
Delete of object
    Delete a pipe
    Delete a flowset
    Delete a scheduler
Compatibility with FreeBSD7.2 and FreeBSD 8 ipfw binary
    ip_dummynet_glue.c
    ip_fw_glue.c
How to configure dummynet
How to implement a new scheduler



OPEN ISSUES
------------------------------
20100131 deleting RR causes infinite loop
	presumably in the rr_free_queue() call -- seems to hang
	forever when deleting a live flow
------------------------------

Dummynet is a traffic shaper and network emulator. Packets are
selected by an external filter such as ipfw, and passed to the emulator
with a tag such as "pipe 10" or "queue 5" which tells what to
do with the packet. As an example

	ipfw add queue 5 icmp from 10.0.0.2 to all

All packets with the same tag belong to a "flowset", or a set
of flows which can be further partitioned according to a mask.
Flowsets are then passed to a scheduler for processing. The
association of flowsets and schedulers is configurable e.g.

	ipfw queue 5 config sched 10 weight 3 flow_mask xxxx
	ipfw queue 8 config sched 10 weight 1 ...
	ipfw queue 3 config sched 20 weight 1 ...

"sched 10" represents one or more scheduler instances,
selected through a mask on the 5-tuple itself.

	ipfw sched 20 config type FIFO sched_mask yyy ...

There are in fact two masks applied to each packet:
+ the "sched_mask" sends packets arriving to a scheduler_id to
  one of many instances.
+ the "flow_mask" together with the flowset_id is used to
  collect packets into independent flows on each scheduler.

As an example, we can have
	ipfw queue 5 config sched 10 flow_mask src-ip 0x000000ff
	ipfw sched 10 config type WF2Q+ sched_mask src-ip 0xffffff00

means that sched 10 will have one instance per /24 source subnet,
and within that, each individual source will be a flow.

Internal structure
-----------------
Dummynet-related data is split into several data structures,
part of them constituting the userland-kernel API, and others
specific to the kernel.
NOTE: for up-to-date details please look at the relevant source
	headers (ip_dummynet.h, ip_dn_private.h, dn_sched.h)

USERLAND-KERNEL API	(ip_dummynet.h)

    struct dn_link:
	contains data about the physical link such as
	bandwidth, delay, burst size;

    struct dn_fs:
	describes a flowset, i.e. a template for queues.
	Main parameters are the scheduler we attach to, a flow_mask,
	buckets, queue size, plr, weight, and other scheduler-specific
	parameters.

    struct dn_flow
	contains information on a flow, including masks and
	statistics

    struct dn_sch:
	defines a scheduler (and a link attached to it).
	Parameters include scheduler type, sched_mask, number of
	buckets, and possibly other scheduler-specific parameters,

    struct dn_profile:
	fields to simulate a delay profile


KERNEL REPRESENTATION	(ip_dn_private.h)

    struct mq
	a queue of mbufs with head and tail.

    struct dn_queue
	individual queue of packets, created by a flowset using
	flow_mask and attached to a scheduler instance selected
	through sched_mask.
	A dn_queue has a pointer to the dn_fsk (which in turn counts
	how many queues point to it), a pointer to the
	dn_sch_inst it attaches to, and is in a hash table in the
	flowset. scheduler instances also should store queues in
	their own containers used for scheduling (lists, trees, etc.)
	CREATE: done on packet arrivals when a flow matches a flowset.
	DELETE: done only when deleting the parent dn_sch_inst
		or draining memory.

    struct dn_fsk
	includes a dn_fs; a pointer to the dn_schk; a link field
	for the list of dn_fsk attached to the same scheduler,
	or for the unlinked list;
	a refcount for the number of queues pointing to it;
	The dn_fsk is in a hash table, fshash.
	CREATE: done on configuration commands.
	DELETE: on configuration commands.

    struct dn_sch_inst
	a scheduler instance, created from a dn_schk applying sched_mask.
	Contains a delay line, a reference to the parent, and scheduler-
	specific info.  Both dn_sch_inst and its delay line can be in the
	evheap if they have events to be processed.
	CREATE: created from a dn_schk applying sched_mask
	DELETE: configuration command delete a scheduler which in turn
		sweeps the hash table of instances deleting them

    struct dn_schk
	includes dn_sch, dn_link, a pointer to dn_profile,
	a hash table of dn_sch_inst, a list of dn_fsk
	attached to it.
	CREATE: configuration command. If there are flowsets that
		refer to this number, they are attached and moved
		to the hash table
	DELETE: manual, see dn_sch_inst


	fshash                            schedhash
      +---------------+   sched        +--------------+
      |      sched-------------------->|      NEW_SCHK|
  -<----*sch_chain    |<-----------------*fsk_list    |
      |NEW_FSK        |<----.          | [dn_link]    |
      +---------------+     |          +--------------+
      |qht (hash)     |     |          |  siht(hash)  |
      |   [dn_queue]  |     |          |  [dn_si]     |
      |   [dn_queue]  |     |          |  [dn_si]     |
      |     ...       |     |          |   ...        |
      |   +--------+  |     |          | +---------+  |
      |   |dn_queue|  |     |          | |dn_si    |  |
      |  |    fs *----------'          | |         |  |
      |  |    si *---------------------->|         |  |
      |  +---------+  |                | +---------+  |
      +---------------+                +--------------+

The following global data structures contain all
schedulers and flowsets.

- schedhash[x]: contains all scheduler templates in the system.
	Looked up only on manual configurations, where flowsets
	are attached to matching schedulers.
	We have one entry per 'sched X config' command
	(plus one for each 'pipe X config').

- fshash[x]: contains all flowsets.
	We do a lookup on this for each packet.
	We have one entry for each 'queue X config'
	(plus one for each 'pipe X config').

Additionally, a list that contains all unlinked flowset:
- fsu:  contains flowset that are not linked with any scheduler.
	Flowset are put in this list when they refer to a non
	existing scheduler.
	We don't need an efficient data structure as we never search
	here on a packet arrivals.

Scheduler instances and the delay lines associated with each scheduler
instance need to be woken up at certain times. Because we have many
such objects, we keep them in a priority heap (system_heap).

Almost all objects in this implementation are preceded by a structure
(struct dn_id) which makes it easier to identify them.


Files
-----
The dummynet code is split in several files.
All kernel code is in sys/netpfil/ipfw except ip_dummynet.h
All userland code is in sbin/ipfw.
Files are
- sys/netpfil/ip_dummynet.h defines the kernel-userland API
- ip_dn_private.h contains the kernel-specific APIs
  and data structures
- dn_sched.h defines the scheduler API
- ip_dummynet.c cointains module glue and sockopt handlers, with all
  functions to configure and list objects.
- ip_dn_io.c contains the functions directly related to packet processing,
  and run in the critical path. It also contains some functions
  exported to the schedulers.
- dn_heap.[ch] implement a binary heap and a generic hash table
- dn_sched_* implement the various scheduler modules

- dummynet.c is the file used to implement the user side of dummynet.
  It contains the function to parsing command line, and functions to
  show the output of dummynet objects.
Moreover, there are two new file (ip_dummynet_glue.c and ip_fw_glue.c) that
are used to allow compatibility with the "ipfw" binary from FreeBSD 7.2 and
FreeBSD 8.

LOCKING
=======
At the moment the entire processing occurs under a single lock
which is expected to be acquired in exclusive mode
DN_BH_WLOCK() / DN_BH_WUNLOCK().

In perspective we aim at the following:
- the 'busy' flag, 'pending' list and all structures modified by packet
  arrivals and departures are protected by the BH_WLOCK.
  This is normally acquired in exclusive mode by the packet processing
  functions for short sections of code (exception -- the timer).
  If 'busy' is not set, we can do regular packet processing.
  If 'busy' is set, no pieces can be accessed.
  We must enqueue the packet on 'pending' and return immediately.

- the 'busy' flag is set/cleared by long sections of code as follows:
	UH_WLOCK(); KASSERT(busy == 0);
	BH_WLOCK(); busy=1; BH_WUNLOCK();
	... do processing ...
	BH_WLOCK(); busy=0; drain_queue(pending); BH_WUNLOCK();
	UH_WUNLOCK();
  this normally happens when the upper half has something heavy
  to do. The prologue and epilogue are not in the critical path.

- the main containers (fshash, schedhash, ...) are protected by
  UH_WLOCK.

Packet processing
=================
A packet enters dummynet through dummynet_io(). We first lookup
the flowset number in fshash using dn_ht_find(), then find the scheduler
instance using ipdn_si_find(), then possibly identify the correct
queue with ipdn_q_find().
If successful, we call the scheduler's enqueue function(), and
if needed start I/O on the link calling serve_sched().
If the packet can be returned immediately, this is done by
leaving *m0 set. Otherwise, the packet is absorbed by dummynet
and we simply return, possibly with some appropriate error code.

Reconfiguration
---------------
Reconfiguration is the complex part of the system because we need to
keep track of the various objects and containers.
At the moment we do not use reference counts for objects so all
processing must be done under a lock.

The main entry points for configuration is the ip_dn_ctl() handler
for the IP_DUMMYNET3 sockopt (others are provided only for backward
compatibility). Modifications to the configuration call do_config().
The argument is a sequence of blocks each starting with a  struct dn_id
which specifies its content.
The first dn_id must contain as obj.id the DN_API_VERSION
The obj.type is DN_CMD_CONFIG (followed by actual objects),
DN_CMD_DELETE (with the correct subtype and list of objects), or
DN_CMD_FLUSH.

DN_CMD_CONFIG is followed by objects to add/reconfigure. In general,
if an object already exists it is reconfigured, otherwise it is
created in a way that keeps the structure consistent.
We have the following objects in the system, normally numbered with
an identifier N between 1 and 65535. For certain objects we have
"shadow" copies numbered I+NMAX and I+ 2*NMAX which are used to
implement certain backward compatibility features.

In general we have the following linking

  TRADITIONAL DUMMYNET QUEUES "queue N config ... pipe M ..."
	corresponds to a dn_fs object numbered N

  TRADITIONAL DUMMYNET PIPES "pipe N config ..."
	dn_fs N+2*NMAX --> dn_sch N+NMAX type FIFO --> dn_link N+NMAX

  GENERIC SCHEDULER "sched N config ... "
	[dn_fs N+NMAX] --> dn_sch N --> dn_link N
	The flowset N+NMAX is created only if the scheduler is not
	of type MULTIQUEUE.

  DELAY PROFILE	"pipe N config profile ..."
	it is always attached to an existing dn_link N

Because traditional dummynet pipes actually configure both a
'standalone' instance and one that can be used by queues,
we do the following:

    "pipe N config ..." configures:
	dn_sched N type WF2Q+
	dn_sched N+NMAX type FIFO
	dn_fs N+2NMAX attached to dn_sched N+NMAX
	dn_pipe N
	dn_pipe N+NMAX

    "queue N config" configures
	dn_fs N

    "sched N config" configures
	dn_sched N type as desired
	dn_fs N+NMAX attached to dn_sched N


dummynet_task()
===============
The dummynet_task() function is the main dummynet processing function and is
called every tick. This function first calculate the new current time, then
it checks if it is the time to wake up object from the system_heap comparing
the current time and the key of the heap. Two types of object (really the
heap contains pointer to objects) are in the
system_heap:

- scheduler instance: if a scheduler instance is waked up, the dequeue()
  function is called until it has credit. If the dequeue() returns packets,
  the scheduler instance is inserted in the heap with a new key depending of
  the data that will be send out. If the scheduler instance remains with
  some credit, it means that is hasn't other packet to send and so the
  instance is no longer inserted in the heap.

  If the scheduler instance extracted from the heap has the DELETE flag set,
  the dequeue() is not called and the instance is destroyed now.

- delay line: when extracting a delay line, the function transmit_event() is
  called to send out packet from delay line.

  If the scheduler instance associated with this delay line doesn't exists,
  the delay line will be delete now.

Configuration
=============
To create a pipe, queue or scheduler, the user should type commands like:
"ipfw pipe x config"
"ipfw queue y config pipe x"
"ipfw pipe x config sched <type>"

The userland side of dummynet will prepare a buffer contains data to pass to
kernel side.
The buffer contains all struct needed to configure an object. In more detail,
to configure a pipe all three structs (dn_link, dn_sch, dn_fs) are needed,
plus the delay profile struct if the pipe has a delay profile.

If configuring a scheduler only the struct dn_sch is wrote in the buffer,
while if configuring a flowset only the dn_fs struct is wrote.

The first struct in the buffer contains the type of command request, that is
if it is configuring a pipe, a queue, or a scheduler. Then there are structs
need to configure the object, and finally there is the struct that mark
the end of the buffer.

To support the insertion of pipe and queue using the old syntax, when adding
a pipe it's necessary to create a FIFO flowset and a FIFO scheduler, which
have a number x + DN_PIPEOFFSET.

Add a pipe
----------
A pipe is only a template for a link.
If the pipe already exists, parameters are updated. If a delay profile exists
it is deleted and a new one is created.
If the pipe doesn't exist a new one is created. After the creation, the
flowset unlinked list is scanned to see if there are some flowset that would
be linked with this pipe. If so, these flowset will be of wf2q+ type (for
compatibility) and a new wf2q+ scheduler is created now.

Add a scheduler
---------------
If the scheduler already exists, and the type and the mask are the same, the
scheduler is simply reconfigured calling the config_scheduler() scheduler
function with the RECONFIGURE flag active.
If the type or the mask differ, it is necessary to delete the old scheduler
and create a new one.
If the scheduler doesn't exists, a new one is created. If the scheduler has
a mask, the hash table is created to store pointers to scheduler instances.
When a new scheduler is created, it is necessary to scan the unlinked
flowset list to search eventually flowset that would be linked with this
scheduler number. If some are found, flowsets became of the type of this
scheduler and they are configured properly.

Add a flowset
-------------
Flowset pointers are store in the system in two list. The unlinked flowset list
contains all flowset that aren't linked with a scheduler, the flowset list
contains flowset linked to a scheduler, and so they have a type.
When adding a new flowset, first it is checked if the flowset exists (that is,
it is in the flowset list) and if it doesn't exists a new flowset is created
and added to unlinked flowset list if the scheduler which the flowset would be
linked doesn't exists, or added in the flowset list and configured properly if
the scheduler exists. If the flowset (before to be created) was in the
unlinked flowset list, it is removed and deleted, and then recreated.
If the flowset exists, to allow reconfiguration of this flowset, the
scheduler number and types must match with the one in memory. If this isn't
so, the flowset is deleted and a new one will be created. Really, the flowset
it isn't deleted now, but it is removed from flowset list and it will be
deleted later because there could be some queues that are using it.

Listing of object
=================
The user can request a list of object present in dummynet through the command
"ipfw [-v] pipe|queue [x] list|show"
The kernel side of dummynet send a buffer to user side that contains all
pipe, all scheduler, all flowset, plus all scheduler instances and all queues.
The dummynet user land will format the output and show only the relevant
information.
The buffer sent start with all pipe from the system. The entire struct dn_link
is passed, except the delay_profile struct that is useless in user space.
After pipes, all flowset are wrote in the buffer. The struct contains
scheduler flowset specific data is linked with the flowset writing the
'obj' id of the extension into the 'alg_fs' pointer.
Then schedulers are wrote. If a scheduler has one or more scheduler instance,
these are linked to the parent scheduler writing the id of the parent in the
'ptr_sched' pointer. If a scheduler instance has queues, there are wrote in
the buffer and linked thorugh the 'obj' and 'sched_inst' pointer.
Finally, flowsets in the unlinked flowset list  are write in the buffer, and
then a struct gen in saved in the buffer to mark the last struct in the buffer.


Delete of object
================
An object is usually removed by user through a command like
"ipfw pipe|queue x delete". XXX sched?
ipfw pass to the kernel a struct gen that contains the type and the number
of the object to remove

Delete of pipe x
----------------
A pipe can be deleted by the user through the command 'ipfw pipe x delete'.
To delete a pipe, the pipe is removed from the pipe list, and then deleted.
Also the scheduler associated with this pipe should be deleted.
For compatibility with old dummynet syntax, the associated FIFO scheduler and
FIFO flowset must be deleted.

Delete of flowset x
-------------------
To remove a flowset, we must be sure that is no longer referenced by any object.
If the flowset to remove is in the unlinked flowset list, there is not any
issue, the flowset can be safely removed calling a free() (the flowset
extension is not yet created if the flowset is in this list).
If the flowset is in the flowset list, first we remove from it so new packet
are discarded when arrive. Next, the flowset is marked as delete.
Now we must check if some queue is using this flowset.
To do this, a counter (active_f) is provided. This counter indicate how many
queues exist using this flowset.
The active_f counter is automatically incremented when a queue is created
and decremented when a queue is deleted.
If the counter is 0, the flowset can be safely deleted, and the delete_alg_fs()
scheduler function is called before deallocate memory.
If the counter is not 0, the flowset remain in memory until the counter become
zero. When a queue is delete (by dn_delete_queue() function) it is checked if
the linked flowset is deleting and if so the counter is decrementing. If the
counter reaches 0, the flowset is deleted.
The deletion of a queue can be done only by the scheduler, or when the scheduler
is destroyed.

Delete of scheduler x
---------------------
To delete a scheduler we must be sure that any scheduler instance of this type
are in the system_heap. To do so, a counter (inst_counter) is provided.
This counter is managed by the system: it is incremented every time it is
inserted in the system_heap, and decremented every time it is extracted from it.
To delete the scheduler, first we remove it from the scheduler list, so new
packet are discarded when they arrive, and mark the scheduler as deleting.

If the counter is 0, we can remove the scheduler safely calling the
really_deletescheduler() function. This function will scan all scheduler
instances and call the delete_scheduler_instance() function that will delete
the instance. When all instance are deleted, the scheduler template is
deleted calling the delete_scheduler_template(). If the delay line associate
with the scheduler is empty, it is deleted now, else it will be deleted when
it will became empy.
If the counter was not 0, we wait for it. Every time the dummynet_task()
function extract a scheduler from the system_heap, the counter is decremented.
If the scheduler has the delete flag enabled the dequeue() is not called and
delete_scheduler_instance() is called to delete the instance.
Obviously this scheduler instance is no longer inserted in the system_heap.
If the counter reaches 0, the delete_scheduler_template() function is called
all memory is released.
NOTE: Flowsets that belong to this scheduler are not deleted, so if a new
      scheduler with the same number is inserted will use these flowsets.
      To do so, the best approach would be insert these flowset in the
      unlinked flowset list, but doing this now will be very expensive.
      So flowsets will remain in memory and linked with a scheduler that no
      longer exists until a packet belonging to this flowset arrives. When
      this packet arrives, the reconfigure() function is called because the
      generation number mismatch with one contains in the flowset and so
      the flowset will be moved into the flowset unlinked list, or will be
      linked with the new scheduler if a new one was created.


COMPATIBILITY WITH FREEBSD 7.2 AND FREEBSD 8 'IPFW' BINARY
==========================================================
Dummynet is not compatible with old ipfw binary because internal structs are
changed. Moreover, the old ipfw binary is not compatible with new kernels
because the struct that represents a firewall rule has changed. So, if a user
install a new kernel on a FreeBSD 7.2, the ipfw (and possibly many other
commands) will not work.
New dummynet uses a new socket option: IP_DUMMYNET3, used for both set and get.
The old option can be used to allow compatibility with the 'ipfw' binary of
older version (tested with 7.2 and 8.0) of FreeBSD.
Two file are provided for this purpose:
- ip_dummynet_glue.c translates old dummynet requests to the new ones,
- ip_fw_glue.c converts the rule format between 7.2 and 8 versions.
Let see in detail these two files.

IP_DUMMYNET_GLUE.C
------------------
The internal structs of new dummynet are very different from the original.
Because of there are some difference from between dummynet in FreeBSD 7.2 and
dummynet in FreeBSD 8 (the FreeBSD 8 version includes support to pipe delay
profile and burst option), I have to include both header files. I copied
the revision 191715 (for version 7.2) and the revision 196045 (for version 8)
and I appended a number to each struct to mark them.

The main function of this file is ip_dummynet_compat() that is called by
ip_dn_ctl() when it receive a request of old socket option.

A global variabile ('is7') store the version of 'ipfw' that FreeBSD is using.
This variable is set every time a request of configuration is done, because
with this request we receive a buffer of which size depending of ipfw version.
Because of in general the first action is a configuration, this variable is
usually set accordly. If the first action is a request of listing of pipes
or queues, the system cannot know the version of ipfw, and we suppose that
version 7.2 is used. If version is wrong, the output can be senseless, but
the application should not crash.

There are four request for old dummynet:
- IP_DUMMYNET_FLUSH: the flush options have no parameter, so simply the
  dummynet_flush() function is called;
- IP_DUMMYNET_DEL: the delete option need to be translate.
  It is only necessary to extract the number and the type of the object
  (pipe or queue) to delete from the buffer received and build a new struct
  gen contains the right parameters, then call the delete_object() function;
- IP_DUMMYNET_CONFIGURE: the configure command receive a buffer depending of
  the ipfw version. After the properly extraction of all data, that depends
  by the ipfw version used, new structures are filled and then the dummynet
  config_link() function is properly called. Note that the 7.2 version does
  not support some parameter as burst or delay profile.
- IP_DUMMYNET_GET: The get command should send to the ipfw the correct buffer
  depending of its version. There are two function that build the
  corrected buffer, ip_dummynet_get7() and ip_dummynet_get8(). These
  functions reproduce the buffer exactly as 'ipfw' expect. The only difference
  is that the weight parameter for a queue is no longer sent by dummynet and so
  it is set to 0.
  Moreover, because of the internal structure has changed, the bucket size
  of a queue could not be correct, because now all flowset share the hash
  table.
  If the version of ipfw is wrong, the output could be senseless or truncated,
  but the application should not crash.

IP_FW_GLUE.C
------------
The ipfw binary also is used to add rules to FreeBSD firewall. Because of the
struct ip_fw is changed from FreeBsd 7.2 to FreeBSD 8, it is necessary
to write some glue code to allow use ipfw from FreeBSD 7.2 with the kernel
provided with FreeBSD 8.
This file contains two functions to convert a rule from FreeBSD 7.2 format to
FreeBSD 8 format, and viceversa.
The conversion should be done when a rule passes from userspace to kernel space
and viceversa.
I have to modify the ip_fw2.c file to manage these two case, and added a
variable (is7) to store the ipfw version used, using an approach like the
previous file:
- when a new rule is added (option IP_FW_ADD) the is7 variable is set if the
  size of the rule received correspond to FreeBSD 7.2 ipfw version. If so, the
  rule is converted to version 8 calling the function convert_rule_to_8().
  Moreover, after the insertion of the rule, the rule is now reconverted to
  version 7 because the ipfw binary will print it.
- when the user request a list of rules (option IP_FW_GET) the is7 variable
  should be set correctly because we suppose that a configure command was done,
  else we suppose that the FreeBSD version is 8. The function ipfw_getrules()
  in ip_fw2.c file return all rules, eventually converted to version 7 (if
  the is7 is set) to the ipfw binary.
The conversion of a rule is quite simple. The only difference between the
two structures (struct ip_fw) is that in the new there is a new field
(uint32_t id). So, I copy the entire rule in a buffer and the copy the rule in
the right position in the new (or old) struct. The size of commands are not
changed, and the copy is done into a cicle.

How to configure dummynet
=========================
It is possible to configure dummynet through two main commands:
'ipfw pipe' and 'ipfw queue'.
To allow compatibility with old version, it is possible configure dummynet
using the old command syntax. Doing so, obviously, it is only possible to
configure a FIFO scheduler or a wf2q+ scheduler.
A new command, 'ipfw pipe x config sched <type>' is supported to add a new
scheduler to the system.

- ipfw pipe x config ...
  create a new pipe with the link parameters
  create a new scheduler fifo (x + offset)
  create a new flowset fifo (x + offset)
  the mask is eventually stored in the FIFO scheduler

- ipfw queue y config pipe x ...
  create a new flowset y linked to sched x.
    The type of flowset depends by the specified scheduler.
    If the scheduler does not exist, this flowset is inserted in a special
    list and will be not active.
    If pipe x exists and sched does not exist, a new wf2q+ scheduler is
    created and the flowset will be linked to this new scheduler (this is
    done for compatibility with old syntax).

- ipfw pipe x config sched <type> ...
  create a new scheduler x of type <type>.
  Search into the flowset unlinked list if there are some flowset that
  should be linked with this new scheduler.

- ipfw pipe x delete
  delete the pipe x
  delete the scheduler fifo (x + offset)
  delete the scheduler x
  delete the flowset fifo (x + offset)

- ipfw queue x delete
  delete the flowset x

- ipfw sched x delete ///XXX
  delete the scheduler x

Follow now some examples to how configure dummynet:
- Ex1:
  ipfw pipe 10 config bw 1M delay 15 // create a pipe with band and delay
                                        A FIFO flowset and scheduler is
                                        also created
  ipfw queue 5 config pipe 10 weight 56 // create a flowset. This flowset
                                           will be of wf2q+ because a pipe 10
                                           exists. Moreover, the wf2q+
                                           scheduler is created now.
- Ex2:
  ipfw queue 5 config pipe 10 weight 56 // Create a flowset. Scheduler 10
                                           does not exist, so this flowset
                                           is inserted in the unlinked
                                           flowset list.
  ipfw pipe 10 config bw... // Create a pipe, a FIFO flowset and scheduler.
                               Because of a flowset with 'pipe 10' exists,
                               a wf2q+ scheduler is created now and that
                               flowset is linked with this sceduler.

- Ex3:
  ipfw pipe 10 config bw...    // Create a pipe, a FIFO flowset and scheduler.
  ipfw pipe 10 config sched rr // Create a scheduler of type RR, linked to
                                  pipe 10
  ipfw queue 5 config pipe 10 weight 56 // Create a flowset 5. This flowset
                                           will belong to scheduler 10 and
                                           it is of type RR

- Ex4:
  ipfw pipe 10 config sched rr // Create a scheduler of type RR, linked to
                                  pipe 10 (not exist yet)
  ipfw pipe 10 config bw... // Create a pipe, a FIFO flowset and scheduler.
  ipfw queue 5 config pipe 10 weight 56 // Create a flowset 5.This flowset
                                           will belong to scheduler 10 and
                                           it is of type RR
  ipfw pipe 10 config sched wf2q+ // Modify the type of scheduler 10. It
                                     becomes a wf2q+ scheduler.
                                     When a new packet of flowset 5 arrives,
                                     the flowset 5 becomes to wf2q+ type.

How to implement a new scheduler
================================
In dummynet, a scheduler algorithm is represented by two main structs, some
functions and other minor structs.
- A struct dn_sch_xyz (where xyz is the 'type' of scheduler algorithm
  implemented) contains data relative to scheduler, as global parameter that
  are common to all instances of the scheduler
- A struct dn_sch_inst_xyz contains data relative to a single scheduler
  instance, as local status variable depending for example by flows that
  are linked with the scheduler, and so on.
To add a scheduler to dummynet, the user should type a command like:
'ipfw pipe x config sched <type> [mask ... ...]'
This command creates a new struct dn_sch_xyz of type <type>, and
store the optional parameter in that struct.

The parameter mask determines how many scheduler instance of this
scheduler may exist. For example, it is possible to divide traffic
depending on the source port (or destination, or ip address...),
so that every scheduler instance act as an independent scheduler.
If the mask is not set, all traffic goes to the same instance.

When a packet arrives to a scheduler, the system search the corrected
scheduler instance, and if it does not exist it is created now (the
struct dn_sch_inst_xyz is allocated by the system, and the scheduler
fills the field correctly). It is a task of the scheduler to create
the struct that contains all queues for a scheduler instance.
Dummynet provides some function to create an hash table to store
queues, but the schedule algorithm can choice the own struct.

To link a flow to a scheduler, the user should type a command like:
'ipfw queue z config pipe x [mask... ...]'

This command creates a new 'dn_fs' struct that will be inserted
in the system.  If the scheduler x exists, this flowset will be
linked to that scheduler and the flowset type become the same as
the scheduler type. At this point, the function create_alg_fs_xyz()
is called to allow store eventually parameter for the flowset that
depend by scheduler (for example the 'weight' parameter for a wf2q+
scheduler, or some priority...). A parameter mask can be used for
a flowset. If the mask parameter is set, the scheduler instance can
separate packet according to its flow id (src and dst ip, ports...)
and assign it to a separate queue. This is done by the scheduler,
so it can ignore the mask if it wants.

See now the two main structs:
struct dn_sch_xyz {
    struct gen g; /* important the name g */
    /* global params */
};
struct dn_sch_inst_xyz {
    struct gen g; /* important the name g */
    /* params of the instance */
};
It is important to embed the struct gen as first parameter. The struct gen
contains some values that the scheduler instance must fill (the 'type' of
scheduler, the 'len' of the struct...)
The function create_scheduler_xyz() should be implemented to initialize global
parameters in the first struct, and if memory allocation is done it is
mandatory to implement the delete_scheduler_template() function to free that
memory.
The function create_scheduler_instance_xyz() must be implemented even if the
scheduler instance does not use extra parameters. In this function the struct
gen fields must be filled with corrected infos. The
delete_scheduler_instance_xyz() function must bu implemented if the instance
has allocated some memory in the previous function.

To store data belonging to a flowset the follow struct is used:
struct alg_fs_xyz {
    struct gen g;
    /* fill correctly the gen struct
     g.subtype = DN_XYZ;
     g.len = sizeof(struct alg_fs_xyz)
     ...
     */
    /* params for the flow */
};
The create_alg_fs_xyz() function is mandatory, because it must fill the struct
gen, but the delete_alg_fs_xyz() is mandatory only if the previous function
has allocated some memory.

A struct dn_queue contains packets belonging to a queue and some statistical
data. The scheduler could have to store data in this struct, so it must define
a dn_queue_xyz struct:
struct dn_queue_xyz {
    struct dn_queue q;
    /* parameter for a queue */
}

All structures are allocated by the system. To do so, the scheduler must
set the size of its structs in the scheduler descriptor:
scheduler_size:     sizeof(dn_sch_xyz)
scheduler_i_size:   sizeof(dn_sch_inst_xyz)
flowset_size:       sizeof(alg_fs_xyz)
queue_size:         sizeof(dn_queue_xyz);
The scheduler_size could be 0, but other struct must have at least a struct gen.


After the definition of structs, it is necessary to implement the
scheduler functions.

- int (*config_scheduler)(char *command, void *sch, int reconfigure);
    Configure a scheduler, or reconfigure if 'reconfigure' == 1.
    This function performs additional allocation and initialization of global
    parameter for this scheduler.
    If memory is allocated here, the delete_scheduler_template() function
    should be implemented to remove this memory.
- int (*delete_scheduler_template)(void* sch);
    Delete a scheduler template. This function is mandatory if the scheduler
    uses extra data respect the struct dn_sch.
- int (*create_scheduler_instance)(void *s);
    Create a new scheduler instance. The system allocate the necessary memory
    and the schedulet can access it using the 's' pointer.
    The scheduler instance stores all queues, and to do this can use the
    hash table provided by the system.
- int (*delete_scheduler_instance)(void *s);
    Delete a scheduler instance. It is important to free memory allocated
    by create_scheduler_instance() function. The memory allocated by system
    is freed by the system itself. The struct contains all queue also has
    to be deleted.
- int (*enqueue)(void *s, struct gen *f, struct mbuf *m,
                 struct ipfw_flow_id *id);
    Called when a packet arrives. The packet 'm' belongs to the scheduler
    instance 's', has a flowset 'f' and the flowid 'id' has already been
    masked. The enqueue() must call dn_queue_packet(q, m) function to really
    enqueue packet in the queue q. The queue 'q' is chosen by the scheduler
    and if it does not exist should be created calling the dn_create_queue()
    function. If the schedule want to drop the packet, it must call the
    dn_drop_packet() function and then return 1.
- struct mbuf * (*dequeue)(void *s);
    Called when the timer expires (or when a packet arrives and the scheduler
    instance is idle).
    This function is called when at least a packet can be send out. The
    scheduler choices the packet and returns it; if no packet are in the
    schedulerinstance, the function must return NULL.
    Before return a packet, it is important to call the function
    dn_return_packet() to update some statistic of the queue and update the
    queue counters.
- int (*drain_queue)(void *s, int flag);
    The system request to scheduler to delete all queues that is not using
    to free memory. The flag parameter indicate if a queue must be deleted
    even if it is active.

- int (*create_alg_fs)(char *command, struct gen *g, int reconfigure);
    It is called when a flowset is linked with a scheduler. This is done
    when the scheduler is defined, so we can know the type of flowset.
    The function initialize the flowset paramenter parsing the command
    line. The parameter will be stored in the g struct that have the right
    size allocated by the system. If the reconfigure flag is set, it means
    that the flowset is reconfiguring
- int (*delete_alg_fs)(struct gen *f);
    It is called when a flowset is deleting. Must remove the memory allocate
    by the create_alg_fs() function.

- int (*create_queue_alg)(struct dn_queue *q, struct gen *f);
    Called when a queue is created. The function should link the queue
    to the struct used by the scheduler instance to store all queues.
- int (*delete_queue_alg)(struct dn_queue *q);
    Called when a queue is deleting. The function should remove extra data
    and update the struct contains all queues in the scheduler instance.

The struct scheduler represent the scheduler descriptor that is passed to
dummynet when a scheduler module is loaded.
This struct contains the type of scheduler, the length of all structs and
all function pointers.
If a function is not implemented should be initialize to NULL. Some functions
are mandatory, other are mandatory if some memory should be freed.
Mandatory functions:
- create_scheduler_instance()
- enqueue()
- dequeue()
- create_alg_fs()
- drain_queue()
Optional functions:
- config_scheduler()
- create_queue_alg()
Mandatory functions if the corresponding create...() has allocated memory:
- delete_scheduler_template()
- delete_scheduler_instance()
- delete_alg_fs()
- delete_queue_alg()