2 * Copyright (c) 2013 Cisco Systems, Inc. and others. All rights reserved.
4 * This program and the accompanying materials are made available under the
5 * terms of the Eclipse Public License v1.0 which accompanies this distribution,
6 * and is available at http://www.eclipse.org/legal/epl-v10.html
8 package org.opendaylight.protocol.bgp.rib.spi;
10 import com.google.common.base.Objects;
11 import com.google.common.base.Objects.ToStringHelper;
12 import com.google.common.base.Preconditions;
13 import java.util.HashMap;
14 import java.util.Iterator;
16 import java.util.Map.Entry;
17 import javax.annotation.Nullable;
18 import javax.annotation.concurrent.GuardedBy;
19 import javax.annotation.concurrent.ThreadSafe;
20 import org.opendaylight.protocol.bgp.parser.BgpTableTypeImpl;
21 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.message.rev130919.PathAttributes;
22 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.message.rev130919.Update;
23 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.message.rev130919.UpdateBuilder;
24 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.message.rev130919.update.PathAttributesBuilder;
25 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.multiprotocol.rev130919.BgpTableType;
26 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.multiprotocol.rev130919.PathAttributes1;
27 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.multiprotocol.rev130919.PathAttributes1Builder;
28 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.multiprotocol.rev130919.PathAttributes2;
29 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.multiprotocol.rev130919.PathAttributes2Builder;
30 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.multiprotocol.rev130919.update.path.attributes.MpReachNlriBuilder;
31 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.multiprotocol.rev130919.update.path.attributes.MpUnreachNlriBuilder;
32 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev130925.Route;
33 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev130925.rib.Tables;
34 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev130925.rib.TablesKey;
35 import org.opendaylight.yangtools.yang.binding.Identifiable;
36 import org.opendaylight.yangtools.yang.binding.Identifier;
37 import org.opendaylight.yangtools.yang.binding.InstanceIdentifier;
38 import org.opendaylight.yangtools.yang.binding.KeyedInstanceIdentifier;
39 import org.slf4j.Logger;
40 import org.slf4j.LoggerFactory;
43 public abstract class AbstractAdjRIBs<I, D extends Identifiable<K> & Route, K extends Identifier<D>> implements AdjRIBsIn<I, D>, RouteEncoder {
44 protected abstract static class RIBEntryData<I, D extends Identifiable<K> & Route, K extends Identifier<D>> {
45 private final PathAttributes attributes;
46 private final Peer peer;
48 protected RIBEntryData(final Peer peer, final PathAttributes attributes) {
49 this.attributes = Preconditions.checkNotNull(attributes);
50 this.peer = Preconditions.checkNotNull(peer);
53 public PathAttributes getPathAttributes() {
54 return this.attributes;
57 public Peer getPeer() {
62 * Create a data object given the key and target instance identifier.
64 * @param key Route key
65 * @param id Data store target identifier
66 * @return Data object to be written to the data store.
68 protected abstract D getDataObject(I key, K id);
71 public final String toString() {
72 return addToStringAttributes(Objects.toStringHelper(this)).toString();
75 protected ToStringHelper addToStringAttributes(final ToStringHelper toStringHelper) {
76 return toStringHelper.add("attributes", this.attributes);
81 * A single RIB table entry, which holds multiple versions of the entry's state and elects the authoritative based
82 * on ordering specified by the supplied comparator.
85 private final class RIBEntry {
87 * TODO: we could dramatically optimize performance by using the comparator
88 * to retain the candidate states ordered -- thus selection would occur
89 * automatically through insertion, without the need of a second walk.
91 private final Map<Peer, RIBEntryData<I, D, K>> candidates = new HashMap<>();
95 private KeyedInstanceIdentifier<D, K> name;
97 private RIBEntryData<I, D, K> currentState;
99 RIBEntry(final I key) {
100 this.key = Preconditions.checkNotNull(key);
103 private KeyedInstanceIdentifier<D, K> getName() {
104 if (this.name == null) {
105 this.name = identifierForKey(AbstractAdjRIBs.this.basePath, this.key);
106 LOG.trace("Entry {} grew key {}", this, this.name);
112 * Based on given comparator, finds a new best candidate for initial route.
118 private RIBEntryData<I, D, K> findCandidate(final BGPObjectComparator comparator, final RIBEntryData<I, D, K> initial) {
119 RIBEntryData<I, D, K> newState = initial;
120 for (final RIBEntryData<I, D, K> s : this.candidates.values()) {
121 if (newState == null || comparator.compare(newState, s) > 0) {
130 * Advertize newly elected best candidate to datastore.
135 private void electCandidate(final AdjRIBsTransaction transaction, final RIBEntryData<I, D, K> candidate) {
136 LOG.trace("Electing state {} to supersede {}", candidate, this.currentState);
138 if (this.currentState == null || !this.currentState.equals(candidate)) {
139 LOG.trace("Elected new state for {}: {}", getName(), candidate);
140 transaction.advertise(AbstractAdjRIBs.this, this.key, getName(), candidate.getPeer(), candidate.getDataObject(this.key, getName().getKey()));
141 this.currentState = candidate;
146 * Removes RIBEntry from database. If we are removing best path, elect another candidate (using BPS).
147 * If there are no other candidates, remove the path completely.
150 * @return true if the list of the candidates for this path is empty
152 synchronized boolean removeState(final AdjRIBsTransaction transaction, final Peer peer) {
153 final RIBEntryData<I, D, K> data = this.candidates.remove(peer);
154 LOG.trace("Removed data {}", data);
156 final RIBEntryData<I, D, K> candidate = findCandidate(transaction.comparator(), null);
157 if (candidate != null) {
158 electCandidate(transaction, candidate);
160 LOG.trace("Final candidate disappeared, removing entry {}", getName());
161 transaction.withdraw(AbstractAdjRIBs.this, this.key, getName());
164 return this.candidates.isEmpty();
167 synchronized void setState(final AdjRIBsTransaction transaction, final Peer peer, final RIBEntryData<I, D, K> state) {
168 this.candidates.put(Preconditions.checkNotNull(peer), Preconditions.checkNotNull(state));
169 electCandidate(transaction, findCandidate(transaction.comparator(), state));
173 private static final Logger LOG = LoggerFactory.getLogger(AbstractAdjRIBs.class);
174 private final KeyedInstanceIdentifier<Tables, TablesKey> basePath;
175 private final BgpTableType tableType;
176 private final Update eor;
179 private final Map<I, RIBEntry> entries = new HashMap<>();
182 private final Map<Peer, Boolean> peers = new HashMap<>();
184 protected AbstractAdjRIBs(final KeyedInstanceIdentifier<Tables, TablesKey> basePath) {
185 this.basePath = Preconditions.checkNotNull(basePath);
186 this.tableType = new BgpTableTypeImpl(basePath.getKey().getAfi(), basePath.getKey().getSafi());
187 this.eor = new UpdateBuilder().setPathAttributes(new PathAttributesBuilder().addAugmentation(
188 PathAttributes1.class, new PathAttributes1Builder().setMpReachNlri(new MpReachNlriBuilder(this.tableType)
189 .build()).build()).build()).build();
193 public final synchronized void clear(final AdjRIBsTransaction trans, final Peer peer) {
194 final Iterator<Entry<I, RIBEntry>> i = this.entries.entrySet().iterator();
195 while (i.hasNext()) {
196 final Entry<I, RIBEntry> e = i.next();
198 if (e.getValue().removeState(trans, peer)) {
203 this.peers.remove(peer);
204 trans.setUptodate(this.basePath, !this.peers.values().contains(Boolean.FALSE));
207 public final synchronized void addAllEntries(final AdjRIBsTransaction trans) {
208 for (final Entry<I, RIBEntry> e : this.entries.entrySet()) {
209 final RIBEntry entry = e.getValue();
210 final RIBEntryData<I, D, K> state = entry.currentState;
211 trans.advertise(this, e.getKey(), entry.name, state.peer, state.getDataObject(entry.key, entry.name.getKey()));
216 * Construct a datastore identifier for an entry key.
218 * @param basePath datastore base path under which the entry to be stored
219 * @param id object identifier
220 * @return Data store identifier, may not be null
222 protected abstract KeyedInstanceIdentifier<D, K> identifierForKey(InstanceIdentifier<Tables> basePath, I id);
224 public void addWith(final MpUnreachNlriBuilder builder, final InstanceIdentifier<?> key) {
225 this.addWithdrawal(builder, keyForIdentifier(this.routeIdentifier(key)));
229 * Transform a withdrawn identifier into a the corresponding NLRI in MP_UNREACH attribute.
231 * @param id Route key
233 protected abstract void addWithdrawal(MpUnreachNlriBuilder builder, I id);
236 * Creates router identifier out of instance identifier
237 * @param id instance identifier
238 * @return router identifier
240 public abstract @Nullable KeyedInstanceIdentifier<D, K> routeIdentifier(InstanceIdentifier<?> id);
243 * Craates route key out of instance identifier
244 * @param id instance identifier
247 public abstract I keyForIdentifier(KeyedInstanceIdentifier<D, K> id);
250 * Common backend for {@link AdjRIBsIn#addRoutes()} implementations.
251 * If a new route is added, check first for its existence in Map of entries.
252 * If the route is already there, change it's state. Then check for peer in
253 * Map of peers, if it's not there, add it.
255 * @param trans Transaction context
256 * @param peer Originating peer
257 * @param id Data store instance identifier
258 * @param data Data object to be written
260 protected final synchronized void add(final AdjRIBsTransaction trans, final Peer peer, final I id, final RIBEntryData<I, D, K> data) {
261 LOG.debug("Adding state {} for {} peer {}", data, id, peer);
263 RIBEntry e = this.entries.get(Preconditions.checkNotNull(id));
265 e = new RIBEntry(id);
266 this.entries.put(id, e);
269 e.setState(trans, peer, data);
270 if (!this.peers.containsKey(peer)) {
271 this.peers.put(peer, Boolean.FALSE);
272 trans.setUptodate(this.basePath, Boolean.FALSE);
277 * Common backend for {@link AdjRIBsIn#removeRoutes()} implementations.
279 * @param trans Transaction context
280 * @param peer Originating peer
281 * @param id Data store instance identifier
283 protected final synchronized void remove(final AdjRIBsTransaction trans, final Peer peer, final I id) {
284 final RIBEntry e = this.entries.get(id);
285 if (e != null && e.removeState(trans, peer)) {
286 LOG.debug("Removed last state, removing entry for {}", id);
287 this.entries.remove(id);
292 public final void markUptodate(final AdjRIBsTransaction trans, final Peer peer) {
293 this.peers.put(peer, Boolean.TRUE);
294 trans.setUptodate(this.basePath, !this.peers.values().contains(Boolean.FALSE));
298 public final Update endOfRib() {
303 public Update updateMessageFor(final Object key, final Route route) {
304 final UpdateBuilder ub = new UpdateBuilder();
305 final PathAttributesBuilder pab = new PathAttributesBuilder();
308 final MpReachNlriBuilder reach = new MpReachNlriBuilder(this.tableType);
310 addAdvertisement(reach, (D)route);
311 pab.fieldsFrom(route.getAttributes());
312 pab.addAugmentation(PathAttributes1.class, new PathAttributes1Builder().setMpReachNlri(reach.build()).build()).build();
314 final MpUnreachNlriBuilder unreach = new MpUnreachNlriBuilder(this.tableType);
315 addWithdrawal(unreach, (I)key);
316 pab.addAugmentation(PathAttributes2.class, new PathAttributes2Builder().setMpUnreachNlri(unreach.build()).build()).build();
319 ub.setPathAttributes(pab.build());