FD.io VPP  v21.10.1-2-g0a485f517
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 #define NUM_POLICE_RESULTS 3
26 
27 typedef enum
28 {
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
91 
96 
98  u32 thread_index; // Tie policer to a thread, rather than lock
100 
101 } policer_t;
102 
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  */
policer_t::color_aware
u32 color_aware
Definition: police.h:79
policer_t::lock
u32 lock
Definition: police.h:76
policer_t::extended_bucket
u32 extended_bucket
Definition: police.h:95
vnet_police_packet
static policer_result_e vnet_police_packet(policer_t *policer, u32 packet_length, policer_result_e packet_color, u64 time)
Definition: police.h:106
ip_dscp_t
enum ip_dscp_t_ ip_dscp_t
CLIB_CACHE_LINE_ALIGN_MARK
#define CLIB_CACHE_LINE_ALIGN_MARK(mark)
Definition: cache.h:60
STATIC_ASSERT_SIZEOF
STATIC_ASSERT_SIZEOF(policer_t, CLIB_CACHE_LINE_BYTES)
policer_t::current_bucket
u32 current_bucket
Definition: police.h:93
policer_t
Definition: police.h:73
policer_t::pad32
u32 pad32
Definition: police.h:99
policer_t::current_limit
u32 current_limit
Definition: police.h:92
POLICE_VIOLATE
@ POLICE_VIOLATE
Definition: police.h:22
policer_result_e
policer_result_e
Definition: police.h:18
POLICE_EXCEED
@ POLICE_EXCEED
Definition: police.h:21
policer_t::cir_tokens_per_period
u32 cir_tokens_per_period
Definition: police.h:89
policer_t::pir_tokens_per_period
u32 pir_tokens_per_period
Definition: police.h:90
policer_t::scale
u32 scale
Definition: police.h:80
policer_t::single_rate
u32 single_rate
Definition: police.h:78
policer_t::thread_index
u32 thread_index
Definition: police.h:98
QOS_ACTION_MARK_AND_TRANSMIT
@ QOS_ACTION_MARK_AND_TRANSMIT
Definition: police.h:31
QOS_ACTION_DROP
@ QOS_ACTION_DROP
Definition: police.h:29
CLIB_CACHE_LINE_BYTES
#define CLIB_CACHE_LINE_BYTES
Definition: cache.h:58
policer_t::extended_limit
u32 extended_limit
Definition: police.h:94
u64
unsigned long u64
Definition: types.h:89
QOS_ACTION_TRANSMIT
@ QOS_ACTION_TRANSMIT
Definition: police.h:30
POLICE_CONFORM
@ POLICE_CONFORM
Definition: police.h:20
u32
unsigned int u32
Definition: types.h:88
u8
unsigned char u8
Definition: types.h:56
QOS_ACTION_HANDOFF
@ QOS_ACTION_HANDOFF
Definition: police.h:32
pad
u8 pad[3]
log2 (size of the packing page block)
Definition: bihash_doc.h:61
policer_t::last_update_time
u64 last_update_time
Definition: police.h:97
action
vl_api_mac_event_action_t action
Definition: l2.api:211