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