Line data    Source code

       1             : /* SPDX-License-Identifier: GPL-2.0 */
       2             : /*
       3             :  * Dynamic queue limits (dql) - Definitions
       4             :  *
       5             :  * Copyright (c) 2011, Tom Herbert <therbert@google.com>
       6             :  *
       7             :  * This header file contains the definitions for dynamic queue limits (dql).
       8             :  * dql would be used in conjunction with a producer/consumer type queue
       9             :  * (possibly a HW queue).  Such a queue would have these general properties:
      10             :  *
      11             :  *   1) Objects are queued up to some limit specified as number of objects.
      12             :  *   2) Periodically a completion process executes which retires consumed
      13             :  *      objects.
      14             :  *   3) Starvation occurs when limit has been reached, all queued data has
      15             :  *      actually been consumed, but completion processing has not yet run
      16             :  *      so queuing new data is blocked.
      17             :  *   4) Minimizing the amount of queued data is desirable.
      18             :  *
      19             :  * The goal of dql is to calculate the limit as the minimum number of objects
      20             :  * needed to prevent starvation.
      21             :  *
      22             :  * The primary functions of dql are:
      23             :  *    dql_queued - called when objects are enqueued to record number of objects
      24             :  *    dql_avail - returns how many objects are available to be queued based
      25             :  *      on the object limit and how many objects are already enqueued
      26             :  *    dql_completed - called at completion time to indicate how many objects
      27             :  *      were retired from the queue
      28             :  *
      29             :  * The dql implementation does not implement any locking for the dql data
      30             :  * structures, the higher layer should provide this.  dql_queued should
      31             :  * be serialized to prevent concurrent execution of the function; this
      32             :  * is also true for  dql_completed.  However, dql_queued and dlq_completed  can
      33             :  * be executed concurrently (i.e. they can be protected by different locks).
      34             :  */
      35             : 
      36             : #ifndef _LINUX_DQL_H
      37             : #define _LINUX_DQL_H
      38             : 
      39             : #ifdef __KERNEL__
      40             : 
      41             : #include <asm/bug.h>
      42             : 
      43             : struct dql {
      44             :         /* Fields accessed in enqueue path (dql_queued) */
      45             :         unsigned int    num_queued;             /* Total ever queued */
      46             :         unsigned int    adj_limit;              /* limit + num_completed */
      47             :         unsigned int    last_obj_cnt;           /* Count at last queuing */
      48             : 
      49             :         /* Fields accessed only by completion path (dql_completed) */
      50             : 
      51             :         unsigned int    limit ____cacheline_aligned_in_smp; /* Current limit */
      52             :         unsigned int    num_completed;          /* Total ever completed */
      53             : 
      54             :         unsigned int    prev_ovlimit;           /* Previous over limit */
      55             :         unsigned int    prev_num_queued;        /* Previous queue total */
      56             :         unsigned int    prev_last_obj_cnt;      /* Previous queuing cnt */
      57             : 
      58             :         unsigned int    lowest_slack;           /* Lowest slack found */
      59             :         unsigned long   slack_start_time;       /* Time slacks seen */
      60             : 
      61             :         /* Configuration */
      62             :         unsigned int    max_limit;              /* Max limit */
      63             :         unsigned int    min_limit;              /* Minimum limit */
      64             :         unsigned int    slack_hold_time;        /* Time to measure slack */
      65             : };
      66             : 
      67             : /* Set some static maximums */
      68             : #define DQL_MAX_OBJECT (UINT_MAX / 16)
      69             : #define DQL_MAX_LIMIT ((UINT_MAX / 2) - DQL_MAX_OBJECT)
      70             : 
      71             : /*
      72             :  * Record number of objects queued. Assumes that caller has already checked
      73             :  * availability in the queue with dql_avail.
      74             :  */
      75             : static inline void dql_queued(struct dql *dql, unsigned int count)
      76             : {
      77             :         BUG_ON(count > DQL_MAX_OBJECT);
      78             : 
      79             :         dql->last_obj_cnt = count;
      80             : 
      81             :         /* We want to force a write first, so that cpu do not attempt
      82             :          * to get cache line containing last_obj_cnt, num_queued, adj_limit
      83             :          * in Shared state, but directly does a Request For Ownership
      84             :          * It is only a hint, we use barrier() only.
      85             :          */
      86             :         barrier();
      87             : 
      88             :         dql->num_queued += count;
      89             : }
      90             : 
      91             : /* Returns how many objects can be queued, < 0 indicates over limit. */
      92         448 : static inline int dql_avail(const struct dql *dql)
      93             : {
      94         448 :         return READ_ONCE(dql->adj_limit) - READ_ONCE(dql->num_queued);
      95             : }
      96             : 
      97             : /* Record number of completed objects and recalculate the limit. */
      98             : void dql_completed(struct dql *dql, unsigned int count);
      99             : 
     100             : /* Reset dql state */
     101             : void dql_reset(struct dql *dql);
     102             : 
     103             : /* Initialize dql state */
     104             : void dql_init(struct dql *dql, unsigned int hold_time);
     105             : 
     106             : #endif /* _KERNEL_ */
     107             : 
     108             : #endif /* _LINUX_DQL_H */