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 : #include "bgp/bgp_update.h" 7 : 8 : #include "bgp/bgp_route.h" 9 : #include "bgp/bgp_table.h" 10 : 11 : // 12 : // Find the UpdateInfo element with matching RibOutAttr. 13 : // 14 0 : const UpdateInfo *UpdateInfoSList::FindUpdateInfo( 15 : const RibOutAttr &roattr) const { 16 0 : for (List::const_iterator iter = list_.begin(); 17 0 : iter != list_.end(); ++iter) { 18 0 : if (iter->roattr == roattr) return iter.operator->(); 19 : } 20 0 : return NULL; 21 : } 22 : 23 64044 : RouteUpdate::RouteUpdate(BgpRoute *route, int queue_id) 24 : : UpdateEntry(UpdateEntry::UPDATE), 25 64019 : route_(route), 26 64019 : queue_id_(queue_id), 27 64044 : flags_(0) { 28 63958 : } 29 : 30 128065 : RouteUpdate::~RouteUpdate() { 31 64031 : ClearUpdateInfo(); 32 64019 : ClearHistory(); 33 128044 : } 34 : 35 : // 36 : // Set the given UpdateInfoSList in the RouteUpdate to the given value. 37 : // 38 : // Note that the back pointers from the individual UpdateInfo elements 39 : // to the RouteUpdate will be set up when the RouteUpdate gets enqueued 40 : // to an UpdateQueue. 41 : // 42 63859 : void RouteUpdate::SetUpdateInfo(UpdateInfoSList &uinfo_slist) { 43 63859 : assert(updates_->empty()); 44 63852 : updates_.swap(uinfo_slist); 45 63847 : } 46 : 47 : // 48 : // Get rid of all the UpdateInfo elements in the RouteUpdate. Each element 49 : // is also deleted. 50 : // 51 64033 : void RouteUpdate::ClearUpdateInfo() { 52 64033 : updates_->clear_and_dispose(UpdateInfoDisposer()); 53 64020 : } 54 : 55 : // 56 : // Remove the UpdateInfo element from the UpdateInfoSList and delete the 57 : // element. 58 : // 59 : // Return true if the UpdateInfoSList is now empty. 60 : // 61 61436 : bool RouteUpdate::RemoveUpdateInfo(UpdateInfo *uinfo) { 62 61436 : updates_->erase_and_dispose(updates_->iterator_to(*uinfo), 63 : UpdateInfoDisposer()); 64 61476 : return updates_->empty(); 65 : } 66 : 67 : // 68 : // Find the UpdateInfo element with matching RibOutAttr. 69 : // 70 0 : UpdateInfo *RouteUpdate::FindUpdateInfo(const RibOutAttr &roattr) { 71 0 : for (UpdateInfoSList::List::iterator iter = updates_->begin(); 72 0 : iter != updates_->end(); ++iter) { 73 0 : if (iter->roattr == roattr) return iter.operator->(); 74 : } 75 0 : return NULL; 76 : } 77 : 78 : // 79 : // Find the UpdateInfo element with matching RibOutAttr, full of const 80 : // goodness so it can be used by CompareUpdateInfo. 81 : // 82 0 : const UpdateInfo *RouteUpdate::FindUpdateInfo(const RibOutAttr &roattr) const { 83 0 : for (UpdateInfoSList::List::const_iterator iter = updates_->begin(); 84 0 : iter != updates_->end(); ++iter) { 85 0 : if (iter->roattr == roattr) return iter.operator->(); 86 : } 87 0 : return NULL; 88 : } 89 : 90 : // 91 : // Reset the given RibPeerSet from the target of all UpdateInfo elements. Get 92 : // rid of any elements whose target becomes empty. 93 : // 94 0 : void RouteUpdate::ResetUpdateInfo(const RibPeerSet &peerset) { 95 0 : for (UpdateInfoSList::List::iterator iter = updates_->begin(); 96 0 : iter != updates_->end(); ) { 97 0 : iter->target.Reset(peerset); 98 0 : if (iter->target.empty()) { 99 0 : iter = updates_->erase_and_dispose(iter, UpdateInfoDisposer()); 100 : } else { 101 : ++iter; 102 : } 103 : } 104 0 : } 105 : 106 : // 107 : // Compare this RouteUpdate with the UpdateInfo elements in the given list. 108 : // The UpdateInfos and AdvertiseInfos in the RouteUpdate represent the old 109 : // state and the UpdateInfoSList represents the new state. 110 : // 111 : // Uses brute force since the UpdateInfo and AdvertiseInfo lists typically 112 : // contain just a single element. 113 : // 114 : // Return true if the information in the RouteUpdate is logically the same 115 : // as that in the UpdateInfoSList. 116 : // 117 0 : bool RouteUpdate::CompareUpdateInfo(const UpdateInfoSList &uinfo_slist) const { 118 : // Handle the special case where the given UpdateInfoSList is empty. 119 : // 120 : // If we already have withdraws scheduled to all peers to which the 121 : // route was sent earlier, and there are no other scheduled updates, 122 : // we can safely consider the RouteUpdate to have the same state as 123 : // an empty UpdateInfoSList. 124 0 : RibOutAttr roattr_null; 125 0 : if (uinfo_slist->empty() && 126 0 : updates_->size() == 1 && updates_->begin()->roattr == roattr_null) { 127 0 : RibPeerSet withdraw_peerset = updates_->begin()->target; 128 0 : for (AdvertiseSList::List::const_iterator iter = history_->begin(); 129 0 : iter != history_->end(); ++iter) { 130 0 : if (!withdraw_peerset.Contains(iter->bitset)) 131 0 : return false; 132 : } 133 0 : return true; 134 0 : } 135 : 136 : // All the peers that we sent the route to previously must be covered 137 : // by the UpdateInfos in the given UpdateInfoSList. If this is not the 138 : // case, we would need to schedule withdraws to the peers that are not 139 : // covered. 140 0 : RibPeerSet old_peerset, new_peerset; 141 0 : for (AdvertiseSList::List::const_iterator iter = history_->begin(); 142 0 : iter != history_->end(); ++iter) { 143 0 : old_peerset.Set(iter->bitset); 144 : } 145 0 : for (UpdateInfoSList::List::const_iterator iter = uinfo_slist->begin(); 146 0 : iter != uinfo_slist->end(); ++iter) { 147 0 : new_peerset.Set(iter->target); 148 : } 149 0 : if (!new_peerset.Contains(old_peerset)) 150 0 : return false; 151 : 152 : // Compare the peerset for each UpdateInfo in the UpdateInfoSList to 153 : // the peerset for the corresponding UpdateInfo and AdvertiseInfo in 154 : // in the RouteUpdate i.e. the ones for the same RibOutAttr. Each 155 : // peer in the new UpdateInfo must either be in the old UpdateInfo or 156 : // AdvertiseInfo. 157 0 : for (UpdateInfoSList::List::const_iterator iter = uinfo_slist->begin(); 158 0 : iter != uinfo_slist->end(); ++iter) { 159 0 : RibPeerSet attr_peerset; 160 0 : const UpdateInfo *uinfo = FindUpdateInfo(iter->roattr); 161 0 : if (uinfo) 162 0 : attr_peerset.Set(uinfo->target); 163 0 : const AdvertiseInfo *ainfo = FindHistory(iter->roattr); 164 0 : if (ainfo) 165 0 : attr_peerset.Set(ainfo->bitset); 166 0 : if (iter->target != attr_peerset) 167 0 : return false; 168 0 : } 169 : 170 : // Compare the peerset for each UpdateInfo in the RouteUpdate to the 171 : // corresponding UpdateInfo in the given UpdateInfoSList. The peerset 172 : // from the old UpdateInfo needs to be a subset of the peerset from 173 : // the new UpdateInfo. It need not be equal since we may already have 174 : // sent the old state to some peers and moved them to the history. 175 0 : for (UpdateInfoSList::List::const_iterator iter = updates_->begin(); 176 0 : iter != updates_->end(); ++iter) { 177 0 : const UpdateInfo *uinfo = uinfo_slist.FindUpdateInfo(iter->roattr); 178 0 : if (!uinfo || !uinfo->target.Contains(iter->target)) 179 0 : return false; 180 : } 181 : 182 0 : return true; 183 0 : } 184 : 185 : // 186 : // Merge the list of UpdateInfo elements into the RouteUpdate. If we find 187 : // an UpdateInfo with the same RibOutAttr, we modify it's target in place. 188 : // Otherwise, we reset the target bits in any existing UpdateInfos in the 189 : // RouteUpdate and move the UpdateInfo from the list into the RouteUpdate. 190 : // 191 0 : void RouteUpdate::MergeUpdateInfo(UpdateInfoSList &uinfo_slist) { 192 0 : for (UpdateInfoSList::List::iterator iter = uinfo_slist->begin(); 193 0 : iter != uinfo_slist->end(); ) { 194 0 : UpdateInfo *uinfo = FindUpdateInfo(iter->roattr); 195 0 : if (uinfo) { 196 0 : uinfo->target |= iter->target; 197 0 : iter = uinfo_slist->erase_and_dispose(iter, UpdateInfoDisposer()); 198 : } else { 199 0 : UpdateInfo &temp_uinfo = *iter; 200 0 : ResetUpdateInfo(temp_uinfo.target); 201 0 : iter = uinfo_slist->erase(iter); 202 0 : updates_->push_front(temp_uinfo); 203 : } 204 : } 205 0 : } 206 : 207 : // 208 : // The AdvertiseSList in the history contains state that has been sent to 209 : // a set of peers, and the given UpdateInfoSList represents state that we 210 : // intend to send to a possibly different set of peers. 211 : // 212 : // If there are peers in any AdvertiseInfo in the history for which there 213 : // is no state in the UpdateInfoSList, create an UpdateInfo with negative 214 : // state to withdraw what we sent out previously. This UpdateInfo has null 215 : // RibOutAttr and a RibPeerSet of all peers from which we need to withdraw 216 : // the route. 217 : // 218 28600 : void RouteUpdate::BuildNegativeUpdateInfo(UpdateInfoSList &uinfo_slist) const { 219 28600 : RibPeerSet peerset; 220 : 221 : // Build the bitset of peers to which we previously advertised something. 222 28594 : for (AdvertiseSList::List::const_iterator iter = history_->begin(); 223 114115 : iter != history_->end(); ++iter) { 224 28561 : peerset.Set(iter->bitset); 225 : } 226 : 227 : // Remove the peers to which we are going to send updated state. 228 56995 : for (UpdateInfoSList::List::const_iterator iter = uinfo_slist->begin(); 229 61429 : iter != uinfo_slist->end(); ++iter) { 230 2168 : peerset.Reset(iter->target); 231 : } 232 : 233 : // Push an UpdateInfo for a withdraw if the bitset is non-empty. 234 28540 : if (!peerset.empty()) { 235 26768 : UpdateInfo *uinfo = new UpdateInfo(peerset); 236 26768 : uinfo_slist->push_front(*uinfo); 237 : } 238 28568 : } 239 : 240 : // 241 : // If any UpdateInfo element in the UpdateInfoSList describes state that's 242 : // already in one of the AdvertiseInfos in the history, trim that state to 243 : // avoid sending duplicate information. 244 : // 245 : // The RibPeerSet in the UpdateInfo need not be exactly the same as that in 246 : // the AdevrtiseInfo. If the RibOutAttrs match, we can trim the RibPeerSet 247 : // in the UpdateInfo. 248 : // 249 28564 : void RouteUpdate::TrimRedundantUpdateInfo(UpdateInfoSList &uinfo_slist) const { 250 28564 : for (AdvertiseSList::List::const_iterator iter = history_->begin(); 251 114115 : iter != history_->end(); ++iter) { 252 28552 : const AdvertiseInfo *ainfo = iter.operator->(); 253 : 254 28552 : for (UpdateInfoSList::List::iterator iter = uinfo_slist->begin(); 255 114945 : iter != uinfo_slist->end(); ++iter) { 256 : // Keep going if the attributes are different. 257 57868 : if (iter->roattr != ainfo->roattr) 258 28931 : continue; 259 : 260 : // Found one with matching attributes. Reset the target bits in 261 : // the UpdateInfo. Get rid of the UpdateInfo if the target is now 262 : // empty. 263 0 : iter->target.Reset(ainfo->bitset); 264 0 : if (iter->target.empty()) { 265 0 : uinfo_slist->erase_and_dispose(iter, UpdateInfoDisposer()); 266 : } 267 : 268 : // Since a given UpdateInfoSList can have at most one UpdateInfo 269 : // with any given attributes, there's no point in looking at any 270 : // more UpdateInfos. 271 0 : break; 272 : } 273 : } 274 28491 : } 275 : 276 : // 277 : // Set the given AdvertiseSList in the RouteUpdate to the given value. 278 : // 279 : // Should be used only for testing. 280 : // 281 0 : void RouteUpdate::SetHistory(AdvertiseSList &history) { 282 0 : assert(history_->empty()); 283 0 : history_.swap(history); 284 0 : } 285 : 286 : // 287 : // Get rid of all the AdvertiseInfo elements in the RouteUpdate. Each element 288 : // is also deleted. 289 : // 290 64018 : void RouteUpdate::ClearHistory() { 291 64018 : history_->clear_and_dispose(AdvertiseInfoDisposer()); 292 64012 : } 293 : 294 : // 295 : // Move history from RouteUpdate to RouteState. 296 : // 297 37489 : void RouteUpdate::MoveHistory(RouteState *rstate) { 298 37489 : AdvertiseSList adv_slist; 299 37491 : SwapHistory(adv_slist); 300 37493 : rstate->SwapHistory(adv_slist); 301 37496 : } 302 : 303 : // 304 : // Find the history element with matching RibOutAttr. 305 : // 306 0 : const AdvertiseInfo *RouteUpdate::FindHistory(const RibOutAttr &roattr) const { 307 0 : for (AdvertiseSList::List::const_iterator iter = history_->begin(); 308 0 : iter != history_->end(); ++iter) { 309 0 : if (iter->roattr == roattr) return iter.operator->(); 310 : } 311 0 : return NULL; 312 : } 313 : 314 : // 315 : // Update the history information for the RouteUpdate to include the given 316 : // RibOutAttr and the RibPeerSet. This may entail an update to an existing 317 : // AdvertiseInfo or the creation of a new one, as well as possible deletion 318 : // of an existing one. 319 : // 320 61404 : void RouteUpdate::UpdateHistory(RibOut *ribout, const RibOutAttr *roattr, 321 : const RibPeerSet &bits) { 322 : // The history information may reside in the RouteUpdate itself or in 323 : // the associated UpdateList if the RouteUpdate in on an UpdateList. 324 : AdvertiseSList &adv_slist = 325 61404 : (OnUpdateList() ? GetUpdateList(ribout)->History() : history_); 326 : 327 : // Traipse through all the AdvertiseInfo elements in the history. We 328 : // obviously need to find one with a matching RibOutAttr if it exists 329 : // and update it's RibPeerSet. Additionally, we also want to reset 330 : // the RibPeerSet in all other elements since we may have previously 331 : // advertised different attributes to some of the peers in the set. 332 61409 : AdvertiseInfo *ainfo = NULL; 333 61409 : for (AdvertiseSList::List::iterator iter = adv_slist->begin(); 334 175037 : iter != adv_slist->end(); ) { 335 : // Remember if we find the matching element, and move on to the 336 : // next one. 337 26094 : if (iter->roattr == *roattr) { 338 0 : assert(ainfo == NULL); 339 0 : ainfo = iter.operator->(); 340 : ++iter; 341 0 : continue; 342 : } 343 : 344 : // TBD: optimize to reuse an element with the same RibPeerSet but 345 : // different attributes. 346 : 347 : // Reset the bits in the current element. If the RibPeerSet in the 348 : // element becomes empty, get rid of it. 349 26092 : iter->bitset.Reset(bits); 350 26083 : if (iter->bitset.empty()) { 351 : AdvertiseSList::List::iterator prev_iter = iter++; 352 51407 : adv_slist->erase_and_dispose(prev_iter, AdvertiseInfoDisposer()); 353 : } else { 354 : ++iter; 355 : } 356 : } 357 : 358 : // Update an existing element if we found one or create a new one with 359 : // the appropriate state. 360 61411 : if (roattr->IsReachable()) { 361 37491 : if (ainfo == NULL) { 362 37491 : ainfo = new AdvertiseInfo(roattr); 363 37505 : adv_slist->push_front(*ainfo); 364 : } 365 37504 : ainfo->bitset |= bits; 366 : } else { 367 23933 : assert(ainfo == NULL); 368 : } 369 61423 : } 370 : 371 : // 372 : // Return true if this RouteUpdate has been advertised to anyone. We simply 373 : // go through all the AdvertiseInfo elements in the history and check if we 374 : // have at least one that's reachable. 375 : // 376 61005 : bool RouteUpdate::IsAdvertised() const { 377 61005 : for (AdvertiseSList::List::const_iterator iter = history_->begin(); 378 122006 : iter != history_->end(); ++iter) { 379 37135 : if (iter->roattr.IsReachable()) { 380 37140 : return true; 381 : } 382 : } 383 23864 : return false; 384 : } 385 : 386 : // 387 : // Upgrade this RouteUpdate to an UpdateList. Creates a new UpdateList and 388 : // adds the RouteUpdate to it. Also moves the history from the RouteUpdate 389 : // to the UpdateList. 390 : // 391 : // Returns the new UpdateList. 392 : // 393 0 : UpdateList *RouteUpdate::MakeUpdateList() { 394 0 : UpdateList *uplist = new UpdateList; 395 0 : AdvertiseSList history; 396 0 : SwapHistory(history); 397 0 : uplist->SwapHistory(history); 398 0 : uplist->AddUpdate(this); 399 0 : return uplist; 400 0 : } 401 : 402 : // 403 : // Return the UpdateList that contains this RouteUpdate. Assumes that the 404 : // RouteUpdate is on an UpdateList. 405 : // 406 0 : UpdateList *RouteUpdate::GetUpdateList(RibOut *ribout) { 407 0 : assert(FlagIsSet(RouteUpdate::F_LIST)); 408 0 : DBState *dbstate = route_->GetState(ribout->table(), ribout->listener_id()); 409 0 : UpdateList *uplist = dynamic_cast<UpdateList *>(dbstate); 410 0 : assert(uplist); 411 0 : return uplist; 412 : } 413 : 414 : // 415 : // Set the given AdvertiseSList in the UpdateList to the given value. 416 : // 417 : // Should be used only for testing. 418 : // 419 0 : void UpdateList::SetHistory(AdvertiseSList &history) { 420 0 : assert(history_->empty()); 421 0 : history_.swap(history); 422 0 : } 423 : 424 : // 425 : // Move history from UpdateList to RouteState. 426 : // 427 0 : void UpdateList::MoveHistory(RouteState *rstate) { 428 0 : AdvertiseSList adv_slist; 429 0 : SwapHistory(adv_slist); 430 0 : rstate->SwapHistory(adv_slist); 431 0 : } 432 : 433 : // 434 : // Move history from UpdateList to RouteUpdate. 435 : // 436 0 : void UpdateList::MoveHistory(RouteUpdate *rt_update) { 437 0 : AdvertiseSList adv_slist; 438 0 : SwapHistory(adv_slist); 439 0 : rt_update->SwapHistory(adv_slist); 440 0 : } 441 : 442 : // 443 : // Find the history element with matching RibOutAttr. 444 : // 445 0 : const AdvertiseInfo *UpdateList::FindHistory(const RibOutAttr &roattr) const { 446 0 : for (AdvertiseSList::List::const_iterator iter = history_->begin(); 447 0 : iter != history_->end(); ++iter) { 448 0 : if (iter->roattr == roattr) return iter.operator->(); 449 : } 450 0 : return NULL; 451 : } 452 : 453 : // 454 : // Add a RouteUpdate to this UpdateList. Sets up the association between 455 : // the RouteUpdate and the UpdateList. 456 : // 457 : // Assumes that RouteUpdate has no history i.e. AdvertiseSList is empty. 458 : // 459 0 : void UpdateList::AddUpdate(RouteUpdate *rt_update) { 460 0 : list_.push_back(rt_update); 461 0 : rt_update->set_update_list(); 462 0 : } 463 : 464 : // 465 : // Remove a RouteUpdate from this UpdateList. Takes care of removing the 466 : // linkage between the UpdateList and the RouteUpdate. 467 : // 468 0 : void UpdateList::RemoveUpdate(RouteUpdate *rt_update) { 469 0 : rt_update->clear_update_list(); 470 0 : list_.remove(rt_update); 471 0 : } 472 : 473 : // 474 : // Find the RouteUpdate for the given queue. 475 : // 476 0 : RouteUpdate *UpdateList::FindUpdate(int queue_id) { 477 0 : for (List::iterator iter = list_.begin(); iter != list_.end(); ++iter) { 478 0 : if ((*iter)->queue_id() == queue_id) 479 0 : return *iter; 480 : } 481 0 : return NULL; 482 : } 483 : 484 : // 485 : // Downgrade this UpdateList to a RouteUpdate if there's only 1 RouteUpdate 486 : // on it. Takes care of removing the linkage between the UpdateList and the 487 : // last RouteUpdate and moves history from the UpdateList to the RouteUpdate. 488 : // 489 : // Note that the caller is responsible for deleting the UpdateList. 490 : // 491 : // Returns the last/only RouteUpdate if successful, NULL otherwise. 492 : // 493 0 : RouteUpdate *UpdateList::MakeRouteUpdate() { 494 0 : assert(list_.size() != 0); 495 : 496 0 : if (list_.size() > 1) 497 0 : return NULL; 498 : 499 0 : RouteUpdate *rt_update = list_.front(); 500 0 : rt_update->clear_update_list(); 501 0 : MoveHistory(rt_update); 502 0 : return rt_update; 503 : }