Line data Source code
1 : /*
2 : * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved.
3 : * Copyright Contributors to the OpenSDN project
4 : */
5 :
6 : #ifndef SRC_BGP_BGP_ATTR_BASE_H_
7 : #define SRC_BGP_BGP_ATTR_BASE_H_
8 :
9 : #include <boost/functional/hash.hpp>
10 : #include <boost/scoped_array.hpp>
11 :
12 : #include <set>
13 : #include <string>
14 : #include <utility>
15 : #include <vector>
16 : #include <mutex>
17 :
18 : #include "base/parse_object.h"
19 : #include "base/task.h"
20 :
21 : class BgpAttr;
22 :
23 : class BgpAttribute : public ParseObject {
24 : public:
25 : enum Flag {
26 : Optional = 1 << 7,
27 : Transitive = 1 << 6,
28 : Partial = 1 << 5,
29 : ExtendedLength = 1 << 4
30 : };
31 : enum Code {
32 : Reserved = 0,
33 : Origin = 1,
34 : AsPath = 2,
35 : NextHop = 3,
36 : MultiExitDisc = 4,
37 : LocalPref = 5,
38 : AtomicAggregate = 6,
39 : Aggregator = 7,
40 : Communities = 8,
41 : OriginatorId = 9,
42 : ClusterList = 10,
43 : MPReachNlri = 14,
44 : MPUnreachNlri = 15,
45 : ExtendedCommunities = 16,
46 : As4Path = 17,
47 : As4Aggregator = 18,
48 : PmsiTunnel = 22,
49 : LargeCommunities = 32,
50 : McastEdgeDiscovery = 241,
51 : McastEdgeForwarding = 242,
52 : OriginVnPath = 243,
53 : };
54 : enum Subcode {
55 : OList = 1,
56 : LabelBlock = 2,
57 : SourceRd = 3,
58 : Esi = 4,
59 : Params = 5,
60 : LeafOList = 6,
61 : SubProtocol = 7
62 : };
63 :
64 633042 : BgpAttribute() : code(0), subcode(0), flags(0) { }
65 2612694 : BgpAttribute(uint8_t code, uint8_t flags)
66 2612694 : : code(code), subcode(0), flags(flags) { }
67 121471 : BgpAttribute(uint8_t code, uint8_t subcode, uint8_t flags)
68 121471 : : code(code), subcode(subcode), flags(flags) { }
69 : static const uint8_t FLAG_MASK = Optional|Transitive;
70 : uint8_t code;
71 : uint8_t subcode;
72 : uint8_t flags;
73 : /*
74 : * Variable length attributes should return the size of the attribute
75 : * for encoding purposes in order to set the ExtendedLength flag.
76 : */
77 : virtual size_t EncodeLength() const;
78 : /*
79 : * Helper method to compute flags used when encoding attributes.
80 : */
81 : uint8_t GetEncodeFlags() const;
82 :
83 : virtual std::string ToString() const;
84 : virtual int CompareTo(const BgpAttribute &rhs) const;
85 1 : virtual void ToCanonical(BgpAttr *attr) { }
86 : };
87 :
88 : //
89 : // Canonical structure used to exchange a single NLRI prefix between the
90 : // common parser and the address family specific BGP code.
91 : //
92 : // ReadLabel and WriteLabel need a label offset because the label is at
93 : // different locations in different NLRI.
94 : //
95 : // The prefix length is in bits.
96 : // The type is relevant only for NLRI that have multiple route types e.g.
97 : // erm-vpn and e-vpn.
98 : //
99 : struct BgpProtoPrefix : public ParseObject {
100 : static const size_t kLabelSize;
101 :
102 : BgpProtoPrefix();
103 :
104 : uint32_t ReadLabel(size_t label_offset, bool is_vni = false) const;
105 : void WriteLabel(size_t label_offset, uint32_t label, bool is_vni = false);
106 :
107 : std::vector<uint8_t> prefix;
108 : int prefixlen;
109 : uint8_t type;
110 : };
111 :
112 : //
113 : // Base class to manage BGP Path Attributes database. This class provides
114 : // thread safe access to the data base.
115 : //
116 : // Lock contention can be tuned by varying the hash table size passed to the
117 : // constructor.
118 : //
119 : // Attribute contents must be hashable via hash_value() and hashed using
120 : // boost::hash_combine() to partition the attribute database.
121 : //
122 : template <class Type, class TypePtr, class TypeSpec, typename TypeCompare,
123 : class TypeDB>
124 : class BgpPathAttributeDB {
125 : public:
126 126659 : explicit BgpPathAttributeDB(int hash_size = GetHashSize())
127 126659 : : hash_size_(hash_size),
128 253318 : set_(new Set[hash_size]),
129 253318 : mutex_(new std::mutex[hash_size]) {
130 126659 : }
131 :
132 10697 : size_t Size() {
133 10697 : size_t size = 0;
134 :
135 21474 : for (size_t i = 0; i < hash_size_; i++) {
136 10694 : std::scoped_lock lock(mutex_[i]);
137 10787 : size += set_[i].size();
138 : }
139 10780 : return size;
140 : }
141 :
142 661826 : void Delete(Type *attr) {
143 661826 : size_t hash = HashCompute(attr);
144 :
145 661826 : std::scoped_lock lock(mutex_[hash]);
146 661830 : assert(set_[hash].erase(attr));
147 661801 : }
148 :
149 : // Locate passed in attribute in the data base based on the attr ptr.
150 3805140 : TypePtr Locate(Type *attr) {
151 3805140 : return LocateInternal(attr);
152 : }
153 :
154 : // Locate passed in attribute in the data base, based on the attr spec.
155 1159936 : TypePtr Locate(const TypeSpec &spec) {
156 1159936 : Type *attr = new Type(static_cast<TypeDB *>(this), spec);
157 1160024 : return LocateInternal(attr);
158 : }
159 :
160 : private:
161 5626691 : const size_t HashCompute(Type *attr) const {
162 5626691 : if (hash_size_ <= 1) return 0;
163 :
164 9 : size_t hash = 0;
165 9 : boost::hash_combine(hash, *attr);
166 0 : return hash % hash_size_;
167 : }
168 :
169 126659 : static size_t GetHashSize() {
170 126659 : char *str = getenv("BGP_PATH_ATTRIBUTE_DB_HASH_SIZE");
171 :
172 : // Use just one bucket for now.
173 126659 : if (!str) return 1;
174 0 : return strtoul(str, NULL, 0);
175 : }
176 :
177 : // This template safely retrieves an attribute entry from its data base.
178 : // If the entry is not found, it is inserted into the database.
179 : //
180 : // If the entry is already present, then passed in entry is freed and
181 : // existing entry is returned.
182 4965002 : TypePtr LocateInternal(Type *attr) {
183 : // Hash attribute contents to to avoid potential mutex contention.
184 4965002 : size_t hash = HashCompute(attr);
185 10169714 : while (true) {
186 : // Grab mutex to keep db access thread safe.
187 7564748 : std::scoped_lock lock(mutex_[hash]);
188 7569888 : std::pair<typename Set::iterator, bool> ret;
189 :
190 : // Try to insert the passed entry into the database.
191 7569742 : ret = set_[hash].insert(attr);
192 :
193 : // Take a reference to prevent this entry from getting deleted.
194 : // Counter is automatically incremented, hence we get thread safety
195 : // here.
196 7569806 : int prev = intrusive_ptr_add_ref(*ret.first);
197 :
198 : // Check if passed in entry did get into the data base.
199 7569674 : if (ret.second) {
200 : // Take intrusive pointer, thereby incrementing the refcount.
201 661827 : TypePtr ptr = TypePtr(*ret.first);
202 :
203 : // Release redundant refcount taken above to protect this entry
204 : // from getting deleted, as we have now bumped up refcount above
205 661828 : intrusive_ptr_del_ref(*ret.first);
206 661830 : return ptr;
207 661829 : }
208 :
209 : // Make sure that this entry, though in the database is not
210 : // undergoing deletion. This can happen because attribute intrusive
211 : // pointer is released without taking the mutex.
212 : //
213 : // If the previous refcount is 0, it implies that this entry is
214 : // about to get deleted (after we release the mutex). In such
215 : // cases, we retry inserting the passed attribute pointer into the
216 : // data base.
217 6907847 : if (prev > 0) {
218 : // Free passed in attribute, as it is already in the database.
219 4304052 : delete attr;
220 :
221 : // Take intrusive pointer, thereby incrementing the refcount.
222 4304095 : TypePtr ptr = TypePtr(*ret.first);
223 :
224 : // Release redundant refcount taken above to protect this entry
225 : // from getting deleted, as we have now bumped up refcount above
226 4304352 : intrusive_ptr_del_ref(*ret.first);
227 4304439 : return ptr;
228 4304326 : }
229 :
230 : // Decrement the counter bumped up above as we can't use this entry
231 : // which is about to be deleted. Instead, retry inserting the passed
232 : // entry again, into the database.
233 2603795 : intrusive_ptr_del_ref(*ret.first);
234 : }
235 :
236 : assert(false);
237 : return NULL;
238 : }
239 :
240 : typedef std::set<Type *, TypeCompare> Set;
241 : size_t hash_size_;
242 : boost::scoped_array<Set> set_;
243 : boost::scoped_array<std::mutex> mutex_;
244 : };
245 :
246 : #endif // SRC_BGP_BGP_ATTR_BASE_H_
|
