FD.io VPP  v19.04.2-12-g66b1689
Vector Packet Processing
throttle.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2018 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 #ifndef __THROTTLE_H__
17 #define __THROTTLE_H__
18 
19 #include <vlib/vlib.h>
20 #include <vppinfra/xxhash.h>
21 
22 /**
23  * @brief A throttle
24  * Used in the data plane to decide if a given hash should be throttled,
25  * i.e. that the hash has been seen already 'recently'. Recent is the time
26  * given in the throttle's initialisation.
27  */
28 typedef struct throttle_t_
29 {
34 } throttle_t;
35 
36 #define THROTTLE_BITS (512)
37 
38 extern void throttle_init (throttle_t * t, u32 n_threads, f64 time);
39 
41 throttle_seed (throttle_t * t, u32 thread_index, f64 time_now)
42 {
43  if (time_now - t->last_seed_change_time[thread_index] > t->time)
44  {
45  (void) random_u64 (&t->seeds[thread_index]);
46  clib_memset (t->bitmaps[thread_index], 0, THROTTLE_BITS / BITS (u8));
47 
48  t->last_seed_change_time[thread_index] = time_now;
49  }
50  return t->seeds[thread_index];
51 }
52 
53 always_inline int
54 throttle_check (throttle_t * t, u32 thread_index, u64 hash, u64 seed)
55 {
56  int drop;
57  uword m;
58  u32 w;
59 
60  hash = clib_xxhash (hash ^ seed);
61 
62  /* Select bit number */
63  hash &= THROTTLE_BITS - 1;
64  w = hash / BITS (uword);
65  m = (uword) 1 << (hash % BITS (uword));
66 
67  drop = (t->bitmaps[thread_index][w] & m) != 0;
68  t->bitmaps[thread_index][w] |= m;
69 
70  return (drop);
71 }
72 
73 #endif
74 
75 /*
76  * fd.io coding-style-patch-verification: ON
77  *
78  * Local Variables:
79  * eval: (c-set-style "gnu")
80  * End:
81  */
f64 time
Definition: throttle.h:30
unsigned long u64
Definition: types.h:89
static u64 clib_xxhash(u64 key)
Definition: xxhash.h:58
clib_memset(h->entries, 0, sizeof(h->entries[0])*entries)
static u64 random_u64(u64 *seed)
64-bit random number generator Again, constants courtesy of Donald Knuth.
Definition: random.h:126
unsigned char u8
Definition: types.h:56
double f64
Definition: types.h:142
#define always_inline
Definition: clib.h:98
u64 * seeds
Definition: throttle.h:32
unsigned int u32
Definition: types.h:88
static u64 throttle_seed(throttle_t *t, u32 thread_index, f64 time_now)
Definition: throttle.h:41
A throttle Used in the data plane to decide if a given hash should be throttled, i.e.
Definition: throttle.h:28
uword ** bitmaps
Definition: throttle.h:31
#define THROTTLE_BITS
Definition: throttle.h:36
f64 * last_seed_change_time
Definition: throttle.h:33
void throttle_init(throttle_t *t, u32 n_threads, f64 time)
Definition: throttle.c:19
u64 uword
Definition: types.h:112
struct throttle_t_ throttle_t
A throttle Used in the data plane to decide if a given hash should be throttled, i.e.
#define BITS(x)
Definition: clib.h:61
static int throttle_check(throttle_t *t, u32 thread_index, u64 hash, u64 seed)
Definition: throttle.h:54