src/vnet/policer/police.h

   1 /*
   2  * Copyright (c) 2015 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15 #ifndef __POLICE_H__
  16 #define __POLICE_H__
  17
  18 typedef enum
  19 {
  20   POLICE_CONFORM = 0,
  21   POLICE_EXCEED = 1,
  22   POLICE_VIOLATE = 2,
  23 } policer_result_e;
  24
  25 #define NUM_POLICE_RESULTS 3
  26
  27 typedef enum
  28 {
  29   QOS_ACTION_DROP = 0,
  30   QOS_ACTION_TRANSMIT,
  31   QOS_ACTION_MARK_AND_TRANSMIT,
  32   QOS_ACTION_HANDOFF
  33 } __clib_packed qos_action_type_en;
  34
  35 // This is the hardware representation of the policer.
  36 // To be multithread-safe, the policer is accessed through a spin-lock
  37 // on the lock field. (For a policer update operation, 24B needs to be
  38 // modified and this would be a challenge to do with atomic instructions.)
  39 // The structure is padded so that no other data is put into the same
  40 // 64B cache-line. This reduces cache-thrashing between threads.
  41 //
  42 // A note on scale:
  43 // The HW TSC tick is roughly one CPU clock cycle.
  44 // This is shifted to create a larger period, with a goal to be around 50usec.
  45 // The period time will vary based on CPU clock speed.
  46 // CPU speeds of 1Ghz to 8Ghz are targetted.
  47 // The shift amount is a constant 17 bits, resulting in a period between
  48 // 16usec (8Ghz CPU) and 131usec (1Ghz CPU).
  49 // The token_per_period computation takes into account the clock speed.
  50 //
  51 // The 32-bit bucket/limit supports about 850ms of burst on a 40GE port,
  52 // or 340ms on a 100GE port. If a larger burst is configured, then the
  53 // programmed value is simply capped at 2^32-1. If we needed to support
  54 // more than that, the bucket and limit fields could be expanded.
  55 //
  56 // tokens_per_period should be > 1000 to support 0.1% granularity.
  57 // To support lower rates (which would not meet this requirement), the packet
  58 // length, bucket, and limit values can be scaled. The scale is a power of 2
  59 // so the multiplication can be implemented as a shift. The control plane
  60 // computes the shift amount be the largest possible that still supports the
  61 // burst size. This makes the rate accuracy as high as possible.
  62 //
  63 // The 64-bit last_update_time supports a 4Ghz CPU without rollover for 100
  64 // years
  65 //
  66 // The lock field should be used for a spin-lock on the struct. Alternatively,
  67 // a thread index field is provided so that policed packets may be handed
  68 // off to a single worker thread.
  69
  70 #define POLICER_TICKS_PER_PERIOD_SHIFT 17
  71 #define POLICER_TICKS_PER_PERIOD       (1 << POLICER_TICKS_PER_PERIOD_SHIFT)
  72
  73 typedef struct
  74 {
  75   CLIB_CACHE_LINE_ALIGN_MARK (cacheline0);
  76   u32 lock;                     // for exclusive access to the struct
  77
  78   u32 single_rate;              // 1 = single rate policer, 0 = two rate policer
  79   u32 color_aware;              // for hierarchical policing
  80   u32 scale;                    // power-of-2 shift amount for lower rates
  81   qos_action_type_en action[3];
  82   ip_dscp_t mark_dscp[3];
  83   u8 pad[2];
  84
  85   // Fields are marked as 2R if they are only used for a 2-rate policer,
  86   // and MOD if they are modified as part of the update operation.
  87   // 1 token = 1 byte.
  88
  89   u32 cir_tokens_per_period;    // # of tokens for each period
  90   u32 pir_tokens_per_period;    // 2R
  91
  92   u32 current_limit;
  93   u32 current_bucket;           // MOD
  94   u32 extended_limit;
  95   u32 extended_bucket;          // MOD
  96
  97   u64 last_update_time;         // MOD
  98   u32 thread_index;             // Tie policer to a thread, rather than lock
  99   u32 pad32;
 100
 101 } policer_t;
 102
 103 STATIC_ASSERT_SIZEOF (policer_t, CLIB_CACHE_LINE_BYTES);
 104
 105 static inline policer_result_e
 106 vnet_police_packet (policer_t *policer, u32 packet_length,
 107                     policer_result_e packet_color, u64 time)
 108 {
 109   u64 n_periods;
 110   u64 current_tokens, extended_tokens;
 111   policer_result_e result;
 112
 113   // Scale packet length to support a wide range of speeds
 114   packet_length = packet_length << policer->scale;
 115
 116   // Compute the number of policer periods that have passed since the last
 117   // operation.
 118   n_periods = time - policer->last_update_time;
 119   policer->last_update_time = time;
 120
 121   // Since there is no background last-update-time adjustment, n_periods
 122   // could grow large if the policer is idle for a long time. This could
 123   // cause a 64-bit overflow when computing tokens_per_period * num_periods.
 124   // It will overflow if log2(n_periods) + log2(tokens_per_period) > 64.
 125   //
 126   // To mitigate this, the policer configuration algorithm insures that
 127   // tokens_per_period is less than 2^22, i.e. this is a 22 bit value not
 128   // a 32-bit value. Thus overflow will only occur if n_periods > 64-22 or
 129   // 42. 2^42 min-sized periods is 16us * 2^42, or 2 years. So this can
 130   // rarely occur. If overflow does happen, the only effect will be that
 131   // fewer tokens than the max burst will be added to the bucket for this
 132   // packet. This constraint on tokens_per_period lets the ucode omit
 133   // code to dynamically check for or prevent the overflow.
 134
 135   if (policer->single_rate)
 136     {
 137
 138       // Compute number of tokens for this time period
 139       current_tokens =
 140         policer->current_bucket + n_periods * policer->cir_tokens_per_period;
 141       if (current_tokens > policer->current_limit)
 142         {
 143           current_tokens = policer->current_limit;
 144         }
 145
 146       extended_tokens =
 147         policer->extended_bucket + n_periods * policer->cir_tokens_per_period;
 148       if (extended_tokens > policer->extended_limit)
 149         {
 150           extended_tokens = policer->extended_limit;
 151         }
 152
 153       // Determine color
 154
 155       if ((!policer->color_aware || (packet_color == POLICE_CONFORM))
 156           && (current_tokens >= packet_length))
 157         {
 158           policer->current_bucket = current_tokens - packet_length;
 159           policer->extended_bucket = extended_tokens - packet_length;
 160           result = POLICE_CONFORM;
 161         }
 162       else if ((!policer->color_aware || (packet_color != POLICE_VIOLATE))
 163                && (extended_tokens >= packet_length))
 164         {
 165           policer->current_bucket = current_tokens;
 166           policer->extended_bucket = extended_tokens - packet_length;
 167           result = POLICE_EXCEED;
 168         }
 169       else
 170         {
 171           policer->current_bucket = current_tokens;
 172           policer->extended_bucket = extended_tokens;
 173           result = POLICE_VIOLATE;
 174         }
 175
 176     }
 177   else
 178     {
 179       // Two-rate policer
 180
 181       // Compute number of tokens for this time period
 182       current_tokens =
 183         policer->current_bucket + n_periods * policer->cir_tokens_per_period;
 184       extended_tokens =
 185         policer->extended_bucket + n_periods * policer->pir_tokens_per_period;
 186       if (current_tokens > policer->current_limit)
 187         {
 188           current_tokens = policer->current_limit;
 189         }
 190       if (extended_tokens > policer->extended_limit)
 191         {
 192           extended_tokens = policer->extended_limit;
 193         }
 194
 195       // Determine color
 196
 197       if ((policer->color_aware && (packet_color == POLICE_VIOLATE))
 198           || (extended_tokens < packet_length))
 199         {
 200           policer->current_bucket = current_tokens;
 201           policer->extended_bucket = extended_tokens;
 202           result = POLICE_VIOLATE;
 203         }
 204       else if ((policer->color_aware && (packet_color == POLICE_EXCEED))
 205                || (current_tokens < packet_length))
 206         {
 207           policer->current_bucket = current_tokens;
 208           policer->extended_bucket = extended_tokens - packet_length;
 209           result = POLICE_EXCEED;
 210         }
 211       else
 212         {
 213           policer->current_bucket = current_tokens - packet_length;
 214           policer->extended_bucket = extended_tokens - packet_length;
 215           result = POLICE_CONFORM;
 216         }
 217     }
 218   return result;
 219 }
 220
 221 #endif // __POLICE_H__
 222
 223 /*
 224  * fd.io coding-style-patch-verification: ON
 225  *
 226  * Local Variables:
 227  * eval: (c-set-style "gnu")
 228  * End:
 229  */