• Tom Herbert's avatar
    dql: Dynamic queue limits · 75957ba3
    Tom Herbert authored
    Implementation of dynamic queue limits (dql).  This is a libary which
    allows a queue limit to be dynamically managed.  The goal of dql is
    to set the queue limit, number of objects to the queue, to be minimized
    without allowing the queue to be starved.
    
    dql would be used with a queue which has these properties:
    
    1) Objects are queued up to some limit which can be expressed as a
       count of objects.
    2) Periodically a completion process executes which retires consumed
       objects.
    3) Starvation occurs when limit has been reached, all queued data has
       actually been consumed but completion processing has not yet run,
       so queuing new data is blocked.
    4) Minimizing the amount of queued data is desirable.
    
    A canonical example of such a queue would be a NIC HW transmit queue.
    
    The queue limit is dynamic, it will increase or decrease over time
    depending on the workload.  The queue limit is recalculated each time
    completion processing is done.  Increases occur when the queue is
    starved and can exponentially increase over successive intervals.
    Decreases occur when more data is being maintained in the queue than
    needed to prevent starvation.  The number of extra objects, or "slack",
    is measured over successive intervals, and to avoid hysteresis the
    limit is only reduced by the miminum slack seen over a configurable
    time period.
    
    dql API provides routines to manage the queue:
    - dql_init is called to intialize the dql structure
    - dql_reset is called to reset dynamic values
    - dql_queued called when objects are being enqueued
    - dql_avail returns availability in the queue
    - dql_completed is called when objects have be consumed in the queue
    
    Configuration consists of:
    - max_limit, maximum limit
    - min_limit, minimum limit
    - slack_hold_time, time to measure instances of slack before reducing
      queue limit
    Signed-off-by: default avatarTom Herbert <therbert@google.com>
    Acked-by: default avatarEric Dumazet <eric.dumazet@gmail.com>
    Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
    75957ba3
Makefile 3.8 KB