bgp/rib-spi/src/main/java/org/opendaylight/protocol/bgp/rib/spi/AbstractAdjRIBs.java

   1 /*
   2  * Copyright (c) 2013 Cisco Systems, Inc. and others.  All rights reserved.
   3  *
   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
   7  */
   8 package org.opendaylight.protocol.bgp.rib.spi;
   9
  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;
  15 import java.util.Map;
  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;
  41
  42 @ThreadSafe
  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;
  47
  48         protected RIBEntryData(final Peer peer, final PathAttributes attributes) {
  49             this.attributes = Preconditions.checkNotNull(attributes);
  50             this.peer = Preconditions.checkNotNull(peer);
  51         }
  52
  53         public PathAttributes getPathAttributes() {
  54             return this.attributes;
  55         }
  56
  57         public Peer getPeer() {
  58             return this.peer;
  59         }
  60
  61         /**
  62          * Create a data object given the key and target instance identifier.
  63          *
  64          * @param key Route key
  65          * @param id Data store target identifier
  66          * @return Data object to be written to the data store.
  67          */
  68         protected abstract D getDataObject(I key, K id);
  69
  70         @Override
  71         public final String toString() {
  72             return addToStringAttributes(Objects.toStringHelper(this)).toString();
  73         }
  74
  75         protected ToStringHelper addToStringAttributes(final ToStringHelper toStringHelper) {
  76             return toStringHelper.add("attributes", this.attributes);
  77         }
  78     }
  79
  80     /**
  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.
  83      *
  84      */
  85     private final class RIBEntry {
  86         /*
  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.
  90          */
  91         private final Map<Peer, RIBEntryData<I, D, K>> candidates = new HashMap<>();
  92         private final I key;
  93
  94         @GuardedBy("this")
  95         private KeyedInstanceIdentifier<D, K> name;
  96         @GuardedBy("this")
  97         private RIBEntryData<I, D, K> currentState;
  98
  99         RIBEntry(final I key) {
 100             this.key = Preconditions.checkNotNull(key);
 101         }
 102
 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);
 107             }
 108             return this.name;
 109         }
 110
 111         /**
 112          * Based on given comparator, finds a new best candidate for initial route.
 113          *
 114          * @param comparator
 115          * @param initial
 116          * @return
 117          */
 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) {
 122                     newState = s;
 123                 }
 124             }
 125
 126             return newState;
 127         }
 128
 129         /**
 130          * Advertize newly elected best candidate to datastore.
 131          *
 132          * @param transaction
 133          * @param candidate
 134          */
 135         private void electCandidate(final AdjRIBsTransaction transaction, final RIBEntryData<I, D, K> candidate) {
 136             LOG.trace("Electing state {} to supersede {}", candidate, this.currentState);
 137
 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;
 142             }
 143         }
 144
 145         /**
 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.
 148          * @param transaction
 149          * @param peer
 150          * @return true if the list of the candidates for this path is empty
 151          */
 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);
 155
 156             final RIBEntryData<I, D, K> candidate = findCandidate(transaction.comparator(), null);
 157             if (candidate != null) {
 158                 electCandidate(transaction, candidate);
 159             } else {
 160                 LOG.trace("Final candidate disappeared, removing entry {}", getName());
 161                 transaction.withdraw(AbstractAdjRIBs.this, this.key, getName());
 162             }
 163
 164             return this.candidates.isEmpty();
 165         }
 166
 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));
 170         }
 171     }
 172
 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;
 177
 178     @GuardedBy("this")
 179     private final Map<I, RIBEntry> entries = new HashMap<>();
 180
 181     @GuardedBy("this")
 182     private final Map<Peer, Boolean> peers = new HashMap<>();
 183
 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();
 190     }
 191
 192     @Override
 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();
 197
 198             if (e.getValue().removeState(trans, peer)) {
 199                 i.remove();
 200             }
 201         }
 202
 203         this.peers.remove(peer);
 204         trans.setUptodate(this.basePath, !this.peers.values().contains(Boolean.FALSE));
 205     }
 206
 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()));
 212         }
 213     }
 214
 215     /**
 216      * Construct a datastore identifier for an entry key.
 217      *
 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
 221      */
 222     protected abstract KeyedInstanceIdentifier<D, K> identifierForKey(InstanceIdentifier<Tables> basePath, I id);
 223
 224     public void addWith(final MpUnreachNlriBuilder builder, final InstanceIdentifier<?> key) {
 225         this.addWithdrawal(builder, keyForIdentifier(this.routeIdentifier(key)));
 226     }
 227
 228     /**
 229      * Transform a withdrawn identifier into a the corresponding NLRI in MP_UNREACH attribute.
 230      *
 231      * @param id Route key
 232      */
 233     protected abstract void addWithdrawal(MpUnreachNlriBuilder builder, I id);
 234
 235     /**
 236      * Creates router identifier out of instance identifier
 237      * @param id instance identifier
 238      * @return router identifier
 239      */
 240     public abstract @Nullable KeyedInstanceIdentifier<D, K> routeIdentifier(InstanceIdentifier<?> id);
 241
 242     /**
 243      * Craates route key out of instance identifier
 244      * @param id instance identifier
 245      * @return route key
 246      */
 247     public abstract I keyForIdentifier(KeyedInstanceIdentifier<D, K> id);
 248
 249     /**
 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.
 254      *
 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
 259      */
 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);
 262
 263         RIBEntry e = this.entries.get(Preconditions.checkNotNull(id));
 264         if (e == null) {
 265             e = new RIBEntry(id);
 266             this.entries.put(id, e);
 267         }
 268
 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);
 273         }
 274     }
 275
 276     /**
 277      * Common backend for {@link AdjRIBsIn#removeRoutes()} implementations.
 278      *
 279      * @param trans Transaction context
 280      * @param peer Originating peer
 281      * @param id Data store instance identifier
 282      */
 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);
 288         }
 289     }
 290
 291     @Override
 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));
 295     }
 296
 297     @Override
 298     public final Update endOfRib() {
 299         return this.eor;
 300     }
 301
 302     @Override
 303     public Update updateMessageFor(final Object key, final Route route) {
 304         final UpdateBuilder ub = new UpdateBuilder();
 305         final PathAttributesBuilder pab = new PathAttributesBuilder();
 306
 307         if (route != null) {
 308             final MpReachNlriBuilder reach = new MpReachNlriBuilder(this.tableType);
 309
 310             addAdvertisement(reach, (D)route);
 311             pab.fieldsFrom(route.getAttributes());
 312             pab.addAugmentation(PathAttributes1.class, new PathAttributes1Builder().setMpReachNlri(reach.build()).build()).build();
 313         } else {
 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();
 317         }
 318
 319         ub.setPathAttributes(pab.build());
 320         return ub.build();
 321     }
 322
 323 }