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