Line data    Source code

       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 single_rate;              // 1 = single rate policer, 0 = two rate policer
      77             :   u32 color_aware;              // for hierarchical policing
      78             :   u32 scale;                    // power-of-2 shift amount for lower rates
      79             :   qos_action_type_en action[3];
      80             :   ip_dscp_t mark_dscp[3];
      81             :   u8 pad[2];
      82             : 
      83             :   // Fields are marked as 2R if they are only used for a 2-rate policer,
      84             :   // and MOD if they are modified as part of the update operation.
      85             :   // 1 token = 1 byte.
      86             : 
      87             :   u32 cir_tokens_per_period;    // # of tokens for each period
      88             :   u32 pir_tokens_per_period;    // 2R
      89             : 
      90             :   u32 current_limit;
      91             :   u32 current_bucket;           // MOD
      92             :   u32 extended_limit;
      93             :   u32 extended_bucket;          // MOD
      94             :   u32 thread_index;             // Tie policer to a thread, rather than lock
      95             :   u64 last_update_time;         // MOD
      96             :   u8 *name;
      97             : } policer_t;
      98             : 
      99             : STATIC_ASSERT_SIZEOF (policer_t, CLIB_CACHE_LINE_BYTES);
     100             : 
     101             : static inline policer_result_e
     102      265244 : vnet_police_packet (policer_t *policer, u32 packet_length,
     103             :                     policer_result_e packet_color, u64 time)
     104             : {
     105             :   u64 n_periods;
     106             :   u64 current_tokens, extended_tokens;
     107             :   policer_result_e result;
     108             : 
     109             :   // Scale packet length to support a wide range of speeds
     110      265244 :   packet_length = packet_length << policer->scale;
     111             : 
     112             :   // Compute the number of policer periods that have passed since the last
     113             :   // operation.
     114      265244 :   n_periods = time - policer->last_update_time;
     115      265244 :   policer->last_update_time = time;
     116             : 
     117             :   // Since there is no background last-update-time adjustment, n_periods
     118             :   // could grow large if the policer is idle for a long time. This could
     119             :   // cause a 64-bit overflow when computing tokens_per_period * num_periods.
     120             :   // It will overflow if log2(n_periods) + log2(tokens_per_period) > 64.
     121             :   //
     122             :   // To mitigate this, the policer configuration algorithm insures that
     123             :   // tokens_per_period is less than 2^22, i.e. this is a 22 bit value not
     124             :   // a 32-bit value. Thus overflow will only occur if n_periods > 64-22 or
     125             :   // 42. 2^42 min-sized periods is 16us * 2^42, or 2 years. So this can
     126             :   // rarely occur. If overflow does happen, the only effect will be that
     127             :   // fewer tokens than the max burst will be added to the bucket for this
     128             :   // packet. This constraint on tokens_per_period lets the ucode omit
     129             :   // code to dynamically check for or prevent the overflow.
     130             : 
     131      265244 :   if (policer->single_rate)
     132             :     {
     133             : 
     134             :       // Compute number of tokens for this time period
     135      145244 :       current_tokens =
     136      145244 :         policer->current_bucket + n_periods * policer->cir_tokens_per_period;
     137      145244 :       if (current_tokens > policer->current_limit)
     138             :         {
     139      100042 :           current_tokens = policer->current_limit;
     140             :         }
     141             : 
     142      145244 :       extended_tokens =
     143      145244 :         policer->extended_bucket + n_periods * policer->cir_tokens_per_period;
     144      145244 :       if (extended_tokens > policer->extended_limit)
     145             :         {
     146      100517 :           extended_tokens = policer->extended_limit;
     147             :         }
     148             : 
     149             :       // Determine color
     150             : 
     151      145244 :       if ((!policer->color_aware || (packet_color == POLICE_CONFORM))
     152       85244 :           && (current_tokens >= packet_length))
     153             :         {
     154       75858 :           policer->current_bucket = current_tokens - packet_length;
     155       75858 :           policer->extended_bucket = extended_tokens - packet_length;
     156       75858 :           result = POLICE_CONFORM;
     157             :         }
     158       69386 :       else if ((!policer->color_aware || (packet_color != POLICE_VIOLATE))
     159       29386 :                && (extended_tokens >= packet_length))
     160             :         {
     161       18099 :           policer->current_bucket = current_tokens;
     162       18099 :           policer->extended_bucket = extended_tokens - packet_length;
     163       18099 :           result = POLICE_EXCEED;
     164             :         }
     165             :       else
     166             :         {
     167       51287 :           policer->current_bucket = current_tokens;
     168       51287 :           policer->extended_bucket = extended_tokens;
     169       51287 :           result = POLICE_VIOLATE;
     170             :         }
     171             : 
     172             :     }
     173             :   else
     174             :     {
     175             :       // Two-rate policer
     176             : 
     177             :       // Compute number of tokens for this time period
     178      120000 :       current_tokens =
     179      120000 :         policer->current_bucket + n_periods * policer->cir_tokens_per_period;
     180      120000 :       extended_tokens =
     181      120000 :         policer->extended_bucket + n_periods * policer->pir_tokens_per_period;
     182      120000 :       if (current_tokens > policer->current_limit)
     183             :         {
     184       80002 :           current_tokens = policer->current_limit;
     185             :         }
     186      120000 :       if (extended_tokens > policer->extended_limit)
     187             :         {
     188       80002 :           extended_tokens = policer->extended_limit;
     189             :         }
     190             : 
     191             :       // Determine color
     192             : 
     193      120000 :       if ((policer->color_aware && (packet_color == POLICE_VIOLATE))
     194      100000 :           || (extended_tokens < packet_length))
     195             :         {
     196       21702 :           policer->current_bucket = current_tokens;
     197       21702 :           policer->extended_bucket = extended_tokens;
     198       21702 :           result = POLICE_VIOLATE;
     199             :         }
     200       98298 :       else if ((policer->color_aware && (packet_color == POLICE_EXCEED))
     201       59149 :                || (current_tokens < packet_length))
     202             :         {
     203       42900 :           policer->current_bucket = current_tokens;
     204       42900 :           policer->extended_bucket = extended_tokens - packet_length;
     205       42900 :           result = POLICE_EXCEED;
     206             :         }
     207             :       else
     208             :         {
     209       55398 :           policer->current_bucket = current_tokens - packet_length;
     210       55398 :           policer->extended_bucket = extended_tokens - packet_length;
     211       55398 :           result = POLICE_CONFORM;
     212             :         }
     213             :     }
     214      265244 :   return result;
     215             : }
     216             : 
     217             : #endif // __POLICE_H__
     218             : 
     219             : /*
     220             :  * fd.io coding-style-patch-verification: ON
     221             :  *
     222             :  * Local Variables:
     223             :  * eval: (c-set-style "gnu")
     224             :  * End:
     225             :  */