bsd/kern/kern_callout.c

   1 /*
   2  * Copyright (c) 2004-2007 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28
  29 /*
  30  * Kernel callout related functions, including moving average calculation
  31  * to permit the kernel to know about insufficiently responsive user space
  32  * processes.
  33  */
  34
  35 #include <string.h>             /* memove, memset */
  36 #include <stdint.h>             /* uint64_t */
  37 #include <sys/kern_callout.h>
  38
  39 /*
  40  * kco_ma_init
  41  *
  42  * Initialize a moving average structure for use
  43  *
  44  * Parameters:  map                     Pointer to the moving average state
  45  *              threshold               Threshold % at which to trigger (>100)
  46  *              kind                    Kind of trigger(s) to set
  47  *
  48  * Returns:     (void)
  49  *
  50  * Notes:       The number of samples in a simple moving average is not
  51  *              controllable; this might be a future direction.
  52  *
  53  *              The simple and weighted thresholds are not separately
  54  *              controllable; this might be a future direction, but
  55  *              will likely be unnecessary due to one type being in use
  56  *              at a time in the most likely scenarios.
  57  */
  58 void
  59 kco_ma_init(struct kco_moving_average *map, int32_t threshold, int kind)
  60 {
  61         memset(map, 0, sizeof(*map));
  62
  63         /* per algorithm init required */
  64         map->ma_flags |= KCO_MA_F_NEEDS_INIT;
  65
  66         /* set algorithm selector flags */
  67         map->ma_flags |= kind;
  68
  69         /* set thresholds */
  70         map->ma_sma_threshold = threshold;
  71         map->ma_wma_threshold = threshold;
  72 }
  73
  74
  75 /*
  76  * kco_ma_info
  77  *
  78  * Report on the current moving average information; this is typically only
  79  * called after a trigger event.
  80  *
  81  * Parameters:  map                     Pointer to the moving average state
  82  *              kind                    Kind of trigger to report on
  83  *              averagep                Pointer to area to receive current
  84  *              old_averagep            Pointer to area to receive previous
  85  *              thresholdp              Pointer to area to receive threshold
  86  *
  87  * Returns:     0                       Information not available
  88  *              1                       Information retrieved
  89  *
  90  * Notes:       You can only retrieve one kind of average information at a
  91  *              time; if you are collecting multiple types, then you must
  92  *              call this function one time for each type you are interested
  93  *              in obtaining.
  94  */
  95 int
  96 kco_ma_info(struct kco_moving_average *map, int kind, uint64_t *averagep, uint64_t *old_averagep, int32_t *thresholdp, int *countp)
  97 {
  98         uint64_t        average;
  99         uint64_t        old_average;
 100         int32_t         threshold;
 101         int             count;
 102
 103         /* Not collecting this type of data  or no data yet*/
 104         if (!(map->ma_flags & kind) || (map->ma_flags & KCO_MA_F_NEEDS_INIT))
 105                 return(0);
 106
 107         switch(kind) {
 108         case KCO_MA_F_SMA:
 109                 average = map->ma_sma;
 110                 old_average = map->ma_old_sma;
 111                 threshold = map->ma_sma_threshold;
 112                 count = map->ma_sma_trigger_count;
 113                 break;
 114
 115         case KCO_MA_F_WMA:
 116                 average = map->ma_wma;
 117                 old_average = map->ma_old_wma;
 118                 threshold = map->ma_wma_threshold;
 119                 count = map->ma_wma_trigger_count;
 120                 break;
 121
 122         default:
 123                 /*
 124                  * Asking for data we don't have or more than one kind of
 125                  * data at the same time.
 126                  */
 127                 return(0);
 128         }
 129
 130         if (averagep != NULL)
 131                 *averagep = average;
 132         if (old_averagep != NULL)
 133                 *old_averagep = old_average;
 134         if (thresholdp != NULL)
 135                 *thresholdp = threshold;
 136         if (countp != NULL)
 137                 *countp = count;
 138
 139         return(1);
 140 }
 141
 142
 143 /*
 144  * kco_ma_addsample
 145  *
 146  * Accumulate a sample into a moving average
 147  *
 148  * Parameters:  map                     Pointer to the moving average state
 149  *              sample_time             latency delta time
 150  *
 151  * Returns:     0                       Nothing triggered
 152  *              !0                      Bitmap of KCO_MA_F_* flags for the
 153  *                                              algorithms which triggered
 154  *
 155  * Notes:       Add a delta time sample to the moving average; this function
 156  *              will return bits for each algorithm which went over its
 157  *              trigger threshold as a result of receiving the sample.
 158  *              Callers can then log/complain/panic over the unresponsive
 159  *              process to which they are calling out.
 160  */
 161 int
 162 kco_ma_addsample(struct kco_moving_average *map, uint64_t sample_time)
 163 {
 164         int     triggered = 0;
 165         int     do_init = (map->ma_flags & KCO_MA_F_NEEDS_INIT);
 166
 167         /*
 168          * SIMPLE MOVING AVERAGE
 169          *
 170          * Compute simple moving average over MA_SMA_SAMPLES; incremental is
 171          * cheaper than re-sum.
 172          */
 173         if (map->ma_flags & KCO_MA_F_SMA) {
 174                 map->ma_old_sma = map->ma_sma;
 175
 176                 map->ma_sma = ((map->ma_sma * MA_SMA_SAMPLES) - map->ma_sma_samples[0] + sample_time) / MA_SMA_SAMPLES;
 177                 memmove(&map->ma_sma_samples[1], &map->ma_sma_samples[0], sizeof(map->ma_sma_samples[0]) *(MA_SMA_SAMPLES - 1));
 178                 map->ma_sma_samples[0] = sample_time;
 179                 /*
 180                  * Check if percentage change exceeds the allowed trigger
 181                  * threshold; this will only happen if the sample time
 182                  * increases more than an acceptable amount; decreases will
 183                  * not cause a trigger (but will decrease the overall average,
 184                  * which can cause a trigger the next time).
 185                  *
 186                  * Note:        We don't start triggering on the simple moving
 187                  *              average until after we have enough samples for
 188                  *              the delta to be statistically valid; this is
 189                  *              defined to be MA_SMA_SAMPLES.
 190                  */
 191                 if (map->ma_sma_samples[MA_SMA_SAMPLES-1] && ((int)((map->ma_sma * 100) / map->ma_old_sma)) > map->ma_sma_threshold) {
 192                         triggered |= KCO_MA_F_SMA;
 193                         map->ma_sma_trigger_count++;
 194                 }
 195         }
 196
 197         /*
 198          * WEIGHTED MOVING AVERAGE
 199          *
 200          * Compute the weighted moving average.  Do this by averaging over
 201          * two values, one with a lesser weighting than the other; the lesser
 202          * weighted value is the persistent historical value, whose sample
 203          * weight decreases over time, the older the samples get.  Be careful
 204          * here to permit strict integer artimatic.
 205          */
 206         if (map->ma_flags & KCO_MA_F_WMA) {
 207                 map->ma_old_wma = map->ma_wma;
 208
 209                 /* Prime the pump, if necessary */
 210                 if (do_init)
 211                         map->ma_old_wma = sample_time;
 212
 213                 map->ma_wma = ((((map->ma_wma * 90) + sample_time * ((100*2) - 90))/100) / 2);
 214
 215                 /*
 216                  * Check if percentage change exceeds the allowed trigger
 217                  * threshold; this will only happen if the sample time
 218                  * increases more than an acceptable amount; decreases will
 219                  * not cause a trigger (but will decrease the overall average,
 220                  * which can cause a trigger the next time).
 221                  */
 222                 if (((int)(((map->ma_wma * 100) / map->ma_old_wma))) > map->ma_wma_threshold) {
 223                         triggered |= KCO_MA_F_WMA;
 224                         map->ma_wma_trigger_count++;
 225                 }
 226         }
 227
 228         if (do_init)
 229                 map->ma_flags &= ~KCO_MA_F_NEEDS_INIT;
 230
 231         return (triggered);
 232 }