vnet/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     POLICE_CONFORM = 0,
  20     POLICE_EXCEED  = 1,
  21     POLICE_VIOLATE = 2,
  22 } policer_result_e;
  23
  24 // This is the hardware representation of the policer.
  25 // To be multithread-safe, the policer is accessed through a spin-lock
  26 // on the lock field. (For a policer update operation, 24B needs to be
  27 // modified and this would be a challenge to do with atomic instructions.)
  28 // The structure is padded so that no other data is put into the same
  29 // 64B cache-line. This reduces cache-thrashing between threads.
  30 //
  31 // A note on scale:
  32 // The HW TSC tick is roughly one CPU clock cycle.
  33 // This is shifted to create a larger period, with a goal to be around 50usec.
  34 // The period time will vary based on CPU clock speed.
  35 // CPU speeds of 1Ghz to 8Ghz are targetted.
  36 // The shift amount is a constant 17 bits, resulting in a period between
  37 // 16usec (8Ghz CPU) and 131usec (1Ghz CPU).
  38 // The token_per_period computation takes into account the clock speed.
  39 //
  40 // The 32-bit bucket/limit supports about 850ms of burst on a 40GE port,
  41 // or 340ms on a 100GE port. If a larger burst is configued, then the
  42 // programmed value is simply capped at 2^32-1. If we needed to support
  43 // more than that, the bucket and limit fields could be expanded.
  44 //
  45 // tokens_per_period should be > 1000 to support 0.1% granularity.
  46 // To support lower rates (which would not meet this requirement), the packet
  47 // length, bucket, and limit values can be scaled. The scale is a power of 2
  48 // so the multiplication can be implemented as a shift. The control plane
  49 // computes the shift amount be the largest possible that still supports the
  50 // burst size. This makes the rate accuracy as high as possible.
  51 //
  52 // The 64-bit last_update_time supports a 4Ghz CPU without rollover for 100 years
  53 //
  54 // The lock field should be used for a spin-lock on the struct.
  55
  56 #define POLICER_TICKS_PER_PERIOD_SHIFT 17
  57 #define POLICER_TICKS_PER_PERIOD       (1 << POLICER_TICKS_PER_PERIOD_SHIFT)
  58
  59 typedef struct {
  60
  61     uint32_t lock;           // for exclusive access to the struct
  62
  63     uint32_t single_rate;    // 1 = single rate policer, 0 = two rate policer
  64     uint32_t color_aware;    // for hierarchical policing
  65     uint32_t scale;          // power-of-2 shift amount for lower rates
  66     uint8_t action[3];
  67     uint8_t mark_dscp[3];
  68     uint8_t pad[2];
  69
  70     // Fields are marked as 2R if they are only used for a 2-rate policer,
  71     // and MOD if they are modified as part of the update operation.
  72     // 1 token = 1 byte.
  73
  74     uint32_t cir_tokens_per_period;      // # of tokens for each period
  75     uint32_t pir_tokens_per_period;      // 2R
  76
  77     uint32_t current_limit;
  78     uint32_t current_bucket;             // MOD
  79     uint32_t extended_limit;
  80     uint32_t extended_bucket;            // MOD
  81
  82     uint64_t last_update_time;           // MOD
  83     uint64_t pad64;
  84
  85 } policer_read_response_type_st;
  86
  87 static inline policer_result_e
  88 vnet_police_packet (policer_read_response_type_st *policer,
  89                     uint32_t packet_length,
  90                     policer_result_e packet_color,
  91                     uint64_t time)
  92 {
  93   uint64_t n_periods;
  94   uint64_t current_tokens, extended_tokens;
  95   policer_result_e result;
  96
  97   // Scale packet length to support a wide range of speeds
  98   packet_length = packet_length << policer->scale;
  99
 100   // Compute the number of policer periods that have passed since the last
 101   // operation.
 102   n_periods = time - policer->last_update_time;
 103   policer->last_update_time = time;
 104
 105   // Since there is no background last-update-time adjustment, n_periods
 106   // could grow large if the policer is idle for a long time. This could
 107   // cause a 64-bit overflow when computing tokens_per_period * num_periods.
 108   // It will overflow if log2(n_periods) + log2(tokens_per_period) > 64.
 109   //
 110   // To mitigate this, the policer configuration algorithm insures that
 111   // tokens_per_period is less than 2^22, i.e. this is a 22 bit value not
 112   // a 32-bit value. Thus overflow will only occur if n_periods > 64-22 or
 113   // 42. 2^42 min-sized periods is 16us * 2^42, or 2 years. So this can
 114   // rarely occur. If overflow does happen, the only effect will be that
 115   // fewer tokens than the max burst will be added to the bucket for this
 116   // packet. This constraint on tokens_per_period lets the ucode omit
 117   // code to dynamically check for or prevent the overflow.
 118
 119   if (policer->single_rate) {
 120
 121     // Compute number of tokens for this time period
 122     current_tokens = policer->current_bucket + n_periods * policer->cir_tokens_per_period;
 123     if (current_tokens > policer->current_limit) {
 124       current_tokens = policer->current_limit;
 125     }
 126
 127     extended_tokens = policer->extended_bucket + n_periods * policer->cir_tokens_per_period;
 128     if (extended_tokens > policer->extended_limit) {
 129       extended_tokens = policer->extended_limit;
 130     }
 131
 132     // Determine color
 133
 134     if ((!policer->color_aware || (packet_color == POLICE_CONFORM)) && (current_tokens >= packet_length)) {
 135       policer->current_bucket = current_tokens - packet_length;
 136       policer->extended_bucket = extended_tokens - packet_length;
 137       result = POLICE_CONFORM;
 138     } else if ((!policer->color_aware || (packet_color != POLICE_VIOLATE)) && (extended_tokens >= packet_length)) {
 139       policer->current_bucket = current_tokens;
 140       policer->extended_bucket = extended_tokens - packet_length;
 141       result = POLICE_EXCEED;
 142     } else {
 143       policer->current_bucket = current_tokens;
 144       policer->extended_bucket = extended_tokens;
 145       result = POLICE_VIOLATE;
 146     }
 147
 148   } else {
 149     // Two-rate policer
 150
 151     // Compute number of tokens for this time period
 152     current_tokens = policer->current_bucket + n_periods * policer->cir_tokens_per_period;
 153     extended_tokens = policer->extended_bucket + n_periods * policer->pir_tokens_per_period;
 154     if (current_tokens > policer->current_limit) {
 155       current_tokens = policer->current_limit;
 156     }
 157     if (extended_tokens > policer->extended_limit) {
 158       extended_tokens = policer->extended_limit;
 159     }
 160
 161     // Determine color
 162
 163     if ((policer->color_aware && (packet_color == POLICE_VIOLATE)) || (extended_tokens < packet_length)) {
 164       policer->current_bucket = current_tokens;
 165       policer->extended_bucket = extended_tokens;
 166       result = POLICE_VIOLATE;
 167     } else if ((policer->color_aware && (packet_color == POLICE_EXCEED)) || (current_tokens < packet_length)) {
 168       policer->current_bucket = current_tokens;
 169       policer->extended_bucket = extended_tokens - packet_length;
 170       result = POLICE_EXCEED;
 171     } else {
 172       policer->current_bucket = current_tokens - packet_length;
 173       policer->extended_bucket = extended_tokens - packet_length;
 174       result = POLICE_CONFORM;
 175     }
 176   }
 177   return result;
 178 }
 179
 180 #endif // __POLICE_H__