Branch data     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                 :            : struct dql {
      42                 :            :         /* Fields accessed in enqueue path (dql_queued) */
      43                 :            :         unsigned int    num_queued;             /* Total ever queued */
      44                 :            :         unsigned int    adj_limit;              /* limit + num_completed */
      45                 :            :         unsigned int    last_obj_cnt;           /* Count at last queuing */
      46                 :            : 
      47                 :            :         /* Fields accessed only by completion path (dql_completed) */
      48                 :            : 
      49                 :            :         unsigned int    limit ____cacheline_aligned_in_smp; /* Current limit */
      50                 :            :         unsigned int    num_completed;          /* Total ever completed */
      51                 :            : 
      52                 :            :         unsigned int    prev_ovlimit;           /* Previous over limit */
      53                 :            :         unsigned int    prev_num_queued;        /* Previous queue total */
      54                 :            :         unsigned int    prev_last_obj_cnt;      /* Previous queuing cnt */
      55                 :            : 
      56                 :            :         unsigned int    lowest_slack;           /* Lowest slack found */
      57                 :            :         unsigned long   slack_start_time;       /* Time slacks seen */
      58                 :            : 
      59                 :            :         /* Configuration */
      60                 :            :         unsigned int    max_limit;              /* Max limit */
      61                 :            :         unsigned int    min_limit;              /* Minimum limit */
      62                 :            :         unsigned int    slack_hold_time;        /* Time to measure slack */
      63                 :            : };
      64                 :            : 
      65                 :            : /* Set some static maximums */
      66                 :            : #define DQL_MAX_OBJECT (UINT_MAX / 16)
      67                 :            : #define DQL_MAX_LIMIT ((UINT_MAX / 2) - DQL_MAX_OBJECT)
      68                 :            : 
      69                 :            : /*
      70                 :            :  * Record number of objects queued. Assumes that caller has already checked
      71                 :            :  * availability in the queue with dql_avail.
      72                 :            :  */
      73                 :            : static inline void dql_queued(struct dql *dql, unsigned int count)
      74                 :            : {
      75                 :            :         BUG_ON(count > DQL_MAX_OBJECT);
      76                 :            : 
      77                 :            :         dql->last_obj_cnt = count;
      78                 :            : 
      79                 :            :         /* We want to force a write first, so that cpu do not attempt
      80                 :            :          * to get cache line containing last_obj_cnt, num_queued, adj_limit
      81                 :            :          * in Shared state, but directly does a Request For Ownership
      82                 :            :          * It is only a hint, we use barrier() only.
      83                 :            :          */
      84                 :            :         barrier();
      85                 :            : 
      86                 :            :         dql->num_queued += count;
      87                 :            : }
      88                 :            : 
      89                 :            : /* Returns how many objects can be queued, < 0 indicates over limit. */
      90                 :            : static inline int dql_avail(const struct dql *dql)
      91                 :            : {
      92                 :      21108 :         return READ_ONCE(dql->adj_limit) - READ_ONCE(dql->num_queued);
      93                 :            : }
      94                 :            : 
      95                 :            : /* Record number of completed objects and recalculate the limit. */
      96                 :            : void dql_completed(struct dql *dql, unsigned int count);
      97                 :            : 
      98                 :            : /* Reset dql state */
      99                 :            : void dql_reset(struct dql *dql);
     100                 :            : 
     101                 :            : /* Initialize dql state */
     102                 :            : void dql_init(struct dql *dql, unsigned int hold_time);
     103                 :            : 
     104                 :            : #endif /* _KERNEL_ */
     105                 :            : 
     106                 :            : #endif /* _LINUX_DQL_H */