FD.io VPP  v18.11-rc0-18-g2a3fb1a
Vector Packet Processing
ip4_forward.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 /*
16  * ip/ip4_forward.h: IP v4 forwarding
17  *
18  * Copyright (c) 2008 Eliot Dresselhaus
19  *
20  * Permission is hereby granted, free of charge, to any person obtaining
21  * a copy of this software and associated documentation files (the
22  * "Software"), to deal in the Software without restriction, including
23  * without limitation the rights to use, copy, modify, merge, publish,
24  * distribute, sublicense, and/or sell copies of the Software, and to
25  * permit persons to whom the Software is furnished to do so, subject to
26  * the following conditions:
27  *
28  * The above copyright notice and this permission notice shall be
29  * included in all copies or substantial portions of the Software.
30  *
31  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
32  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
33  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
34  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
35  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
36  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
37  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
38  */
39 
40 #ifndef __included_ip4_forward_h__
41 #define __included_ip4_forward_h__
42 
43 #include <vnet/fib/ip4_fib.h>
45 
46 /**
47  * @file
48  * @brief IPv4 Forwarding.
49  *
50  * This file contains the source code for IPv4 forwarding.
51  */
52 
55  vlib_node_runtime_t * node,
56  vlib_frame_t * frame,
57  int lookup_for_responses_to_locally_received_packets)
58 {
59  ip4_main_t *im = &ip4_main;
61  u32 n_left_from, n_left_to_next, *from, *to_next;
62  ip_lookup_next_t next;
63  u32 thread_index = vm->thread_index;
64 
65  from = vlib_frame_vector_args (frame);
66  n_left_from = frame->n_vectors;
67  next = node->cached_next_index;
68 
69  while (n_left_from > 0)
70  {
71  vlib_get_next_frame (vm, node, next, to_next, n_left_to_next);
72 
73  while (n_left_from >= 8 && n_left_to_next >= 4)
74  {
75  vlib_buffer_t *p0, *p1, *p2, *p3;
76  ip4_header_t *ip0, *ip1, *ip2, *ip3;
77  ip_lookup_next_t next0, next1, next2, next3;
78  const load_balance_t *lb0, *lb1, *lb2, *lb3;
79  ip4_fib_mtrie_t *mtrie0, *mtrie1, *mtrie2, *mtrie3;
80  ip4_fib_mtrie_leaf_t leaf0, leaf1, leaf2, leaf3;
81  ip4_address_t *dst_addr0, *dst_addr1, *dst_addr2, *dst_addr3;
82  u32 pi0, pi1, pi2, pi3, lb_index0, lb_index1, lb_index2, lb_index3;
83  flow_hash_config_t flow_hash_config0, flow_hash_config1;
84  flow_hash_config_t flow_hash_config2, flow_hash_config3;
85  u32 hash_c0, hash_c1, hash_c2, hash_c3;
86  const dpo_id_t *dpo0, *dpo1, *dpo2, *dpo3;
87 
88  /* Prefetch next iteration. */
89  {
90  vlib_buffer_t *p4, *p5, *p6, *p7;
91 
92  p4 = vlib_get_buffer (vm, from[4]);
93  p5 = vlib_get_buffer (vm, from[5]);
94  p6 = vlib_get_buffer (vm, from[6]);
95  p7 = vlib_get_buffer (vm, from[7]);
96 
97  vlib_prefetch_buffer_header (p4, LOAD);
98  vlib_prefetch_buffer_header (p5, LOAD);
99  vlib_prefetch_buffer_header (p6, LOAD);
100  vlib_prefetch_buffer_header (p7, LOAD);
101 
102  CLIB_PREFETCH (p4->data, sizeof (ip0[0]), LOAD);
103  CLIB_PREFETCH (p5->data, sizeof (ip0[0]), LOAD);
104  CLIB_PREFETCH (p6->data, sizeof (ip0[0]), LOAD);
105  CLIB_PREFETCH (p7->data, sizeof (ip0[0]), LOAD);
106  }
107 
108  pi0 = to_next[0] = from[0];
109  pi1 = to_next[1] = from[1];
110  pi2 = to_next[2] = from[2];
111  pi3 = to_next[3] = from[3];
112 
113  from += 4;
114  to_next += 4;
115  n_left_to_next -= 4;
116  n_left_from -= 4;
117 
118  p0 = vlib_get_buffer (vm, pi0);
119  p1 = vlib_get_buffer (vm, pi1);
120  p2 = vlib_get_buffer (vm, pi2);
121  p3 = vlib_get_buffer (vm, pi3);
122 
123  ip0 = vlib_buffer_get_current (p0);
124  ip1 = vlib_buffer_get_current (p1);
125  ip2 = vlib_buffer_get_current (p2);
126  ip3 = vlib_buffer_get_current (p3);
127 
128  dst_addr0 = &ip0->dst_address;
129  dst_addr1 = &ip1->dst_address;
130  dst_addr2 = &ip2->dst_address;
131  dst_addr3 = &ip3->dst_address;
132 
137 
138  if (!lookup_for_responses_to_locally_received_packets)
139  {
140  mtrie0 = &ip4_fib_get (vnet_buffer (p0)->ip.fib_index)->mtrie;
141  mtrie1 = &ip4_fib_get (vnet_buffer (p1)->ip.fib_index)->mtrie;
142  mtrie2 = &ip4_fib_get (vnet_buffer (p2)->ip.fib_index)->mtrie;
143  mtrie3 = &ip4_fib_get (vnet_buffer (p3)->ip.fib_index)->mtrie;
144 
145  leaf0 = ip4_fib_mtrie_lookup_step_one (mtrie0, dst_addr0);
146  leaf1 = ip4_fib_mtrie_lookup_step_one (mtrie1, dst_addr1);
147  leaf2 = ip4_fib_mtrie_lookup_step_one (mtrie2, dst_addr2);
148  leaf3 = ip4_fib_mtrie_lookup_step_one (mtrie3, dst_addr3);
149  }
150 
151  if (!lookup_for_responses_to_locally_received_packets)
152  {
153  leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, dst_addr0, 2);
154  leaf1 = ip4_fib_mtrie_lookup_step (mtrie1, leaf1, dst_addr1, 2);
155  leaf2 = ip4_fib_mtrie_lookup_step (mtrie2, leaf2, dst_addr2, 2);
156  leaf3 = ip4_fib_mtrie_lookup_step (mtrie3, leaf3, dst_addr3, 2);
157  }
158 
159  if (!lookup_for_responses_to_locally_received_packets)
160  {
161  leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, dst_addr0, 3);
162  leaf1 = ip4_fib_mtrie_lookup_step (mtrie1, leaf1, dst_addr1, 3);
163  leaf2 = ip4_fib_mtrie_lookup_step (mtrie2, leaf2, dst_addr2, 3);
164  leaf3 = ip4_fib_mtrie_lookup_step (mtrie3, leaf3, dst_addr3, 3);
165  }
166 
167  if (lookup_for_responses_to_locally_received_packets)
168  {
169  lb_index0 = vnet_buffer (p0)->ip.adj_index[VLIB_RX];
170  lb_index1 = vnet_buffer (p1)->ip.adj_index[VLIB_RX];
171  lb_index2 = vnet_buffer (p2)->ip.adj_index[VLIB_RX];
172  lb_index3 = vnet_buffer (p3)->ip.adj_index[VLIB_RX];
173  }
174  else
175  {
176  lb_index0 = ip4_fib_mtrie_leaf_get_adj_index (leaf0);
177  lb_index1 = ip4_fib_mtrie_leaf_get_adj_index (leaf1);
178  lb_index2 = ip4_fib_mtrie_leaf_get_adj_index (leaf2);
179  lb_index3 = ip4_fib_mtrie_leaf_get_adj_index (leaf3);
180  }
181 
182  ASSERT (lb_index0 && lb_index1 && lb_index2 && lb_index3);
183  lb0 = load_balance_get (lb_index0);
184  lb1 = load_balance_get (lb_index1);
185  lb2 = load_balance_get (lb_index2);
186  lb3 = load_balance_get (lb_index3);
187 
188  ASSERT (lb0->lb_n_buckets > 0);
189  ASSERT (is_pow2 (lb0->lb_n_buckets));
190  ASSERT (lb1->lb_n_buckets > 0);
191  ASSERT (is_pow2 (lb1->lb_n_buckets));
192  ASSERT (lb2->lb_n_buckets > 0);
193  ASSERT (is_pow2 (lb2->lb_n_buckets));
194  ASSERT (lb3->lb_n_buckets > 0);
195  ASSERT (is_pow2 (lb3->lb_n_buckets));
196 
197  /* Use flow hash to compute multipath adjacency. */
198  hash_c0 = vnet_buffer (p0)->ip.flow_hash = 0;
199  hash_c1 = vnet_buffer (p1)->ip.flow_hash = 0;
200  hash_c2 = vnet_buffer (p2)->ip.flow_hash = 0;
201  hash_c3 = vnet_buffer (p3)->ip.flow_hash = 0;
202  if (PREDICT_FALSE (lb0->lb_n_buckets > 1))
203  {
204  flow_hash_config0 = lb0->lb_hash_config;
205  hash_c0 = vnet_buffer (p0)->ip.flow_hash =
206  ip4_compute_flow_hash (ip0, flow_hash_config0);
207  dpo0 =
209  (hash_c0 &
210  (lb0->lb_n_buckets_minus_1)));
211  }
212  else
213  {
214  dpo0 = load_balance_get_bucket_i (lb0, 0);
215  }
216  if (PREDICT_FALSE (lb1->lb_n_buckets > 1))
217  {
218  flow_hash_config1 = lb1->lb_hash_config;
219  hash_c1 = vnet_buffer (p1)->ip.flow_hash =
220  ip4_compute_flow_hash (ip1, flow_hash_config1);
221  dpo1 =
223  (hash_c1 &
224  (lb1->lb_n_buckets_minus_1)));
225  }
226  else
227  {
228  dpo1 = load_balance_get_bucket_i (lb1, 0);
229  }
230  if (PREDICT_FALSE (lb2->lb_n_buckets > 1))
231  {
232  flow_hash_config2 = lb2->lb_hash_config;
233  hash_c2 = vnet_buffer (p2)->ip.flow_hash =
234  ip4_compute_flow_hash (ip2, flow_hash_config2);
235  dpo2 =
237  (hash_c2 &
238  (lb2->lb_n_buckets_minus_1)));
239  }
240  else
241  {
242  dpo2 = load_balance_get_bucket_i (lb2, 0);
243  }
244  if (PREDICT_FALSE (lb3->lb_n_buckets > 1))
245  {
246  flow_hash_config3 = lb3->lb_hash_config;
247  hash_c3 = vnet_buffer (p3)->ip.flow_hash =
248  ip4_compute_flow_hash (ip3, flow_hash_config3);
249  dpo3 =
251  (hash_c3 &
252  (lb3->lb_n_buckets_minus_1)));
253  }
254  else
255  {
256  dpo3 = load_balance_get_bucket_i (lb3, 0);
257  }
258 
259  next0 = dpo0->dpoi_next_node;
260  vnet_buffer (p0)->ip.adj_index[VLIB_TX] = dpo0->dpoi_index;
261  next1 = dpo1->dpoi_next_node;
262  vnet_buffer (p1)->ip.adj_index[VLIB_TX] = dpo1->dpoi_index;
263  next2 = dpo2->dpoi_next_node;
264  vnet_buffer (p2)->ip.adj_index[VLIB_TX] = dpo2->dpoi_index;
265  next3 = dpo3->dpoi_next_node;
266  vnet_buffer (p3)->ip.adj_index[VLIB_TX] = dpo3->dpoi_index;
267 
269  (cm, thread_index, lb_index0, 1,
270  vlib_buffer_length_in_chain (vm, p0));
272  (cm, thread_index, lb_index1, 1,
273  vlib_buffer_length_in_chain (vm, p1));
275  (cm, thread_index, lb_index2, 1,
276  vlib_buffer_length_in_chain (vm, p2));
278  (cm, thread_index, lb_index3, 1,
279  vlib_buffer_length_in_chain (vm, p3));
280 
281  vlib_validate_buffer_enqueue_x4 (vm, node, next,
282  to_next, n_left_to_next,
283  pi0, pi1, pi2, pi3,
284  next0, next1, next2, next3);
285  }
286 
287  while (n_left_from > 0 && n_left_to_next > 0)
288  {
289  vlib_buffer_t *p0;
290  ip4_header_t *ip0;
291  ip_lookup_next_t next0;
292  const load_balance_t *lb0;
293  ip4_fib_mtrie_t *mtrie0;
294  ip4_fib_mtrie_leaf_t leaf0;
295  ip4_address_t *dst_addr0;
296  u32 pi0, lbi0;
297  flow_hash_config_t flow_hash_config0;
298  const dpo_id_t *dpo0;
299  u32 hash_c0;
300 
301  pi0 = from[0];
302  to_next[0] = pi0;
303 
304  p0 = vlib_get_buffer (vm, pi0);
305  ip0 = vlib_buffer_get_current (p0);
306  dst_addr0 = &ip0->dst_address;
308 
309  if (!lookup_for_responses_to_locally_received_packets)
310  {
311  mtrie0 = &ip4_fib_get (vnet_buffer (p0)->ip.fib_index)->mtrie;
312  leaf0 = ip4_fib_mtrie_lookup_step_one (mtrie0, dst_addr0);
313  }
314 
315  if (!lookup_for_responses_to_locally_received_packets)
316  leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, dst_addr0, 2);
317 
318  if (!lookup_for_responses_to_locally_received_packets)
319  leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, dst_addr0, 3);
320 
321  if (lookup_for_responses_to_locally_received_packets)
322  lbi0 = vnet_buffer (p0)->ip.adj_index[VLIB_RX];
323  else
324  {
325  /* Handle default route. */
326  lbi0 = ip4_fib_mtrie_leaf_get_adj_index (leaf0);
327  }
328 
329  ASSERT (lbi0);
330  lb0 = load_balance_get (lbi0);
331 
332  ASSERT (lb0->lb_n_buckets > 0);
333  ASSERT (is_pow2 (lb0->lb_n_buckets));
334 
335  /* Use flow hash to compute multipath adjacency. */
336  hash_c0 = vnet_buffer (p0)->ip.flow_hash = 0;
337  if (PREDICT_FALSE (lb0->lb_n_buckets > 1))
338  {
339  flow_hash_config0 = lb0->lb_hash_config;
340 
341  hash_c0 = vnet_buffer (p0)->ip.flow_hash =
342  ip4_compute_flow_hash (ip0, flow_hash_config0);
343  dpo0 =
345  (hash_c0 &
346  (lb0->lb_n_buckets_minus_1)));
347  }
348  else
349  {
350  dpo0 = load_balance_get_bucket_i (lb0, 0);
351  }
352 
353  next0 = dpo0->dpoi_next_node;
354  vnet_buffer (p0)->ip.adj_index[VLIB_TX] = dpo0->dpoi_index;
355 
356  vlib_increment_combined_counter (cm, thread_index, lbi0, 1,
358  p0));
359 
360  from += 1;
361  to_next += 1;
362  n_left_to_next -= 1;
363  n_left_from -= 1;
364 
365  if (PREDICT_FALSE (next0 != next))
366  {
367  n_left_to_next += 1;
368  vlib_put_next_frame (vm, node, next, n_left_to_next);
369  next = next0;
370  vlib_get_next_frame (vm, node, next, to_next, n_left_to_next);
371  to_next[0] = pi0;
372  to_next += 1;
373  n_left_to_next -= 1;
374  }
375  }
376 
377  vlib_put_next_frame (vm, node, next, n_left_to_next);
378  }
379 
380  if (node->flags & VLIB_NODE_FLAG_TRACE)
381  ip4_forward_next_trace (vm, node, frame, VLIB_TX);
382 
383  return frame->n_vectors;
384 }
385 
386 #endif /* __included_ip4_forward_h__ */
387 
388 /*
389  * fd.io coding-style-patch-verification: ON
390  *
391  * Local Variables:
392  * eval: (c-set-style "gnu")
393  * End:
394  */
u16 lb_n_buckets
number of buckets in the load-balance.
Definition: load_balance.h:94
vlib_combined_counter_main_t lbm_to_counters
Definition: load_balance.h:46
static void vlib_increment_combined_counter(vlib_combined_counter_main_t *cm, u32 thread_index, u32 index, u64 n_packets, u64 n_bytes)
Increment a combined counter.
Definition: counter.h:213
The mutiway-TRIE.
Definition: ip4_mtrie.h:129
static ip4_fib_mtrie_leaf_t ip4_fib_mtrie_lookup_step(const ip4_fib_mtrie_t *m, ip4_fib_mtrie_leaf_t current_leaf, const ip4_address_t *dst_address, u32 dst_address_byte_index)
Lookup step.
Definition: ip4_mtrie.h:202
static u32 ip4_compute_flow_hash(const ip4_header_t *ip, flow_hash_config_t flow_hash_config)
Definition: ip4.h:287
flow_hash_config_t lb_hash_config
the hash config to use when selecting a bucket.
Definition: load_balance.h:134
static const dpo_id_t * load_balance_get_fwd_bucket(const load_balance_t *lb, u16 bucket)
u32 thread_index
Definition: main.h:176
#define vlib_validate_buffer_enqueue_x4(vm, node, next_index, to_next, n_left_to_next, bi0, bi1, bi2, bi3, next0, next1, next2, next3)
Finish enqueueing four buffers forward in the graph.
Definition: buffer_node.h:138
u32 * fib_index_by_sw_if_index
Table index indexed by software interface.
Definition: ip4.h:111
static uword ip4_lookup_inline(vlib_main_t *vm, vlib_node_runtime_t *node, vlib_frame_t *frame, int lookup_for_responses_to_locally_received_packets)
Definition: ip4_forward.h:54
static uword vlib_buffer_length_in_chain(vlib_main_t *vm, vlib_buffer_t *b)
Get length in bytes of the buffer chain.
Definition: buffer_funcs.h:250
ip_lookup_next_t
An adjacency is a representation of an attached L3 peer.
Definition: adj.h:50
#define always_inline
Definition: clib.h:92
u16 lb_n_buckets_minus_1
number of buckets in the load-balance - 1.
Definition: load_balance.h:99
ip4_address_t dst_address
Definition: ip4_packet.h:169
#define vlib_prefetch_buffer_header(b, type)
Prefetch buffer metadata.
Definition: buffer.h:184
u32 ip4_fib_mtrie_leaf_t
Definition: ip4_mtrie.h:52
unsigned int u32
Definition: types.h:88
static u32 ip4_fib_mtrie_leaf_get_adj_index(ip4_fib_mtrie_leaf_t n)
From the stored slot value extract the LB index value.
Definition: ip4_mtrie.h:192
The identity of a DPO is a combination of its type and its instance number/index of objects of that t...
Definition: dpo.h:168
static void ip_lookup_set_buffer_fib_index(u32 *fib_index_by_sw_if_index, vlib_buffer_t *b)
Definition: lookup.h:215
static const dpo_id_t * load_balance_get_bucket_i(const load_balance_t *lb, u32 bucket)
Definition: load_balance.h:209
static void * vlib_buffer_get_current(vlib_buffer_t *b)
Get pointer to current data to process.
Definition: buffer.h:202
The FIB DPO provieds;.
Definition: load_balance.h:84
#define PREDICT_FALSE(x)
Definition: clib.h:105
load_balance_main_t load_balance_main
The one instance of load-balance main.
Definition: load_balance.c:56
#define vlib_get_next_frame(vm, node, next_index, vectors, n_vectors_left)
Get pointer to next frame vector data by (vlib_node_runtime_t, next_index).
Definition: node_funcs.h:364
ip4_fib_mtrie_t mtrie
Mtrie for fast lookups.
Definition: ip4_fib.h:48
u16 n_vectors
Definition: node.h:380
#define CLIB_PREFETCH(addr, size, type)
Definition: cache.h:77
vlib_main_t * vm
Definition: buffer.c:294
static ip4_fib_t * ip4_fib_get(u32 index)
Get the FIB at the given index.
Definition: ip4_fib.h:113
void vlib_put_next_frame(vlib_main_t *vm, vlib_node_runtime_t *r, u32 next_index, u32 n_vectors_left)
Release pointer to next frame vector data.
Definition: main.c:454
u16 cached_next_index
Next frame index that vector arguments were last enqueued to last time this node ran.
Definition: node.h:492
#define ASSERT(truth)
static ip4_fib_mtrie_leaf_t ip4_fib_mtrie_lookup_step_one(const ip4_fib_mtrie_t *m, const ip4_address_t *dst_address)
Lookup step number 1.
Definition: ip4_mtrie.h:224
static load_balance_t * load_balance_get(index_t lbi)
Definition: load_balance.h:200
IPv4 main type.
Definition: ip4.h:95
u32 flow_hash_config_t
A flow hash configuration is a mask of the flow hash options.
Definition: lookup.h:82
static uword is_pow2(uword x)
Definition: clib.h:229
Definition: defs.h:47
index_t dpoi_index
the index of objects of that type
Definition: dpo.h:184
void ip4_forward_next_trace(vlib_main_t *vm, vlib_node_runtime_t *node, vlib_frame_t *frame, vlib_rx_or_tx_t which_adj_index)
Definition: ip4_forward.c:967
u64 uword
Definition: types.h:112
static void * vlib_frame_vector_args(vlib_frame_t *f)
Get pointer to frame vector data.
Definition: node_funcs.h:267
A collection of combined counters.
Definition: counter.h:181
#define vnet_buffer(b)
Definition: buffer.h:359
ip4_main_t ip4_main
Global ip4 main structure.
Definition: ip4_forward.c:832
u8 data[0]
Packet data.
Definition: buffer.h:172
u16 flags
Copy of main node flags.
Definition: node.h:486
u16 dpoi_next_node
The next VLIB node to follow.
Definition: dpo.h:180
#define VLIB_NODE_FLAG_TRACE
Definition: node.h:295
static vlib_buffer_t * vlib_get_buffer(vlib_main_t *vm, u32 buffer_index)
Translate buffer index into buffer pointer.
Definition: buffer_funcs.h:57
Definition: defs.h:46