programming/impl/src/main/java/org/opendaylight/bgpcep/programming/impl/DefaultInstructionScheduler.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.bgpcep.programming.impl;
   9
  10 import static java.util.Objects.requireNonNull;
  11
  12 import com.google.common.annotations.VisibleForTesting;
  13 import com.google.common.collect.ImmutableClassToInstanceMap;
  14 import com.google.common.util.concurrent.FluentFuture;
  15 import com.google.common.util.concurrent.FutureCallback;
  16 import com.google.common.util.concurrent.Futures;
  17 import com.google.common.util.concurrent.ListenableFuture;
  18 import com.google.common.util.concurrent.MoreExecutors;
  19 import com.google.common.util.concurrent.SettableFuture;
  20 import io.netty.util.Timeout;
  21 import io.netty.util.Timer;
  22 import java.math.BigInteger;
  23 import java.util.ArrayList;
  24 import java.util.HashMap;
  25 import java.util.HashSet;
  26 import java.util.Iterator;
  27 import java.util.List;
  28 import java.util.Map;
  29 import java.util.Set;
  30 import java.util.concurrent.Executor;
  31 import java.util.concurrent.TimeUnit;
  32 import org.checkerframework.checker.lock.qual.GuardedBy;
  33 import org.opendaylight.bgpcep.programming.NanotimeUtil;
  34 import org.opendaylight.bgpcep.programming.spi.ExecutionResult;
  35 import org.opendaylight.bgpcep.programming.spi.Instruction;
  36 import org.opendaylight.bgpcep.programming.spi.InstructionScheduler;
  37 import org.opendaylight.bgpcep.programming.spi.SchedulerException;
  38 import org.opendaylight.bgpcep.programming.spi.SuccessfulRpcResult;
  39 import org.opendaylight.mdsal.binding.api.DataBroker;
  40 import org.opendaylight.mdsal.binding.api.NotificationPublishService;
  41 import org.opendaylight.mdsal.binding.api.RpcProviderService;
  42 import org.opendaylight.mdsal.binding.api.WriteTransaction;
  43 import org.opendaylight.mdsal.common.api.CommitInfo;
  44 import org.opendaylight.mdsal.common.api.LogicalDatastoreType;
  45 import org.opendaylight.mdsal.singleton.api.ClusterSingletonService;
  46 import org.opendaylight.mdsal.singleton.api.ClusterSingletonServiceProvider;
  47 import org.opendaylight.mdsal.singleton.api.ServiceGroupIdentifier;
  48 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.programming.rev150720.CancelInstruction;
  49 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.programming.rev150720.CancelInstructionInput;
  50 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.programming.rev150720.CancelInstructionOutput;
  51 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.programming.rev150720.CancelInstructionOutputBuilder;
  52 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.programming.rev150720.CleanInstructions;
  53 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.programming.rev150720.CleanInstructionsInput;
  54 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.programming.rev150720.CleanInstructionsOutput;
  55 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.programming.rev150720.CleanInstructionsOutputBuilder;
  56 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.programming.rev150720.DeadOnArrival;
  57 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.programming.rev150720.DuplicateInstructionId;
  58 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.programming.rev150720.InstructionId;
  59 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.programming.rev150720.InstructionStatus;
  60 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.programming.rev150720.InstructionStatusChangedBuilder;
  61 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.programming.rev150720.InstructionsQueue;
  62 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.programming.rev150720.InstructionsQueueBuilder;
  63 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.programming.rev150720.InstructionsQueueKey;
  64 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.programming.rev150720.Nanotime;
  65 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.programming.rev150720.SubmitInstructionInput;
  66 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.programming.rev150720.UnknownInstruction;
  67 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.programming.rev150720.UnknownPreconditionId;
  68 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.programming.rev150720.instruction.queue.InstructionBuilder;
  69 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.programming.rev150720.instruction.queue.InstructionKey;
  70 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.programming.rev150720.instruction.status.changed.Details;
  71 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.programming.rev150720.submit.instruction.output.result.failure._case.FailureBuilder;
  72 import org.opendaylight.yangtools.concepts.Registration;
  73 import org.opendaylight.yangtools.yang.binding.InstanceIdentifier;
  74 import org.opendaylight.yangtools.yang.binding.KeyedInstanceIdentifier;
  75 import org.opendaylight.yangtools.yang.binding.Rpc;
  76 import org.opendaylight.yangtools.yang.common.RpcResult;
  77 import org.slf4j.Logger;
  78 import org.slf4j.LoggerFactory;
  79
  80 final class DefaultInstructionScheduler implements ClusterSingletonService, InstructionScheduler {
  81     private static final Logger LOG = LoggerFactory.getLogger(DefaultInstructionScheduler.class);
  82
  83     private final Map<InstructionId, InstructionImpl> insns = new HashMap<>();
  84     private final InstanceIdentifier<InstructionsQueue> qid;
  85     private final NotificationPublishService notifs;
  86     private final Executor executor;
  87     private final DataBroker dataProvider;
  88     private final Timer timer;
  89     private final String instructionId;
  90     private final ServiceGroupIdentifier sgi;
  91     private final Registration csspReg;
  92     private final RpcProviderService rpcProviderRegistry;
  93     @GuardedBy("this")
  94     private Registration reg;
  95
  96     private final class InstructionPusher implements QueueInstruction {
  97         private final InstructionBuilder builder = new InstructionBuilder();
  98
  99         InstructionPusher(final InstructionId id, final Nanotime deadline) {
 100             builder.setDeadline(deadline);
 101             builder.setId(id);
 102             builder.withKey(new InstructionKey(id));
 103             builder.setStatus(InstructionStatus.Queued);
 104         }
 105
 106         @Override
 107         public void instructionUpdated(final InstructionStatus status, final Details details) {
 108             if (!status.equals(builder.getStatus())) {
 109                 builder.setStatus(status);
 110
 111                 final WriteTransaction wt = dataProvider.newWriteOnlyTransaction();
 112                 wt.put(LogicalDatastoreType.OPERATIONAL,
 113                         qid.child(
 114                                 org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.programming
 115                                         .rev150720.instruction.queue.Instruction.class,
 116                                 new InstructionKey(builder.getId())), builder.build());
 117                 wt.commit().addCallback(new FutureCallback<CommitInfo>() {
 118                     @Override
 119                     public void onSuccess(final CommitInfo result) {
 120                         LOG.debug("Instruction Queue {} updated", qid);
 121                     }
 122
 123                     @Override
 124                     public void onFailure(final Throwable trw) {
 125                         LOG.error("Failed to update Instruction Queue {}", qid, trw);
 126                     }
 127                 }, MoreExecutors.directExecutor());
 128             }
 129
 130             try {
 131                 notifs.putNotification(new InstructionStatusChangedBuilder()
 132                         .setId(builder.getId()).setStatus(status).setDetails(details).build());
 133             } catch (final InterruptedException e) {
 134                 LOG.debug("Failed to publish notification", e);
 135             }
 136         }
 137
 138         @Override
 139         public void instructionRemoved() {
 140             final WriteTransaction wt = dataProvider.newWriteOnlyTransaction();
 141             wt.delete(LogicalDatastoreType.OPERATIONAL, qid.child(
 142                     org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.programming.rev150720.instruction
 143                             .queue.Instruction.class,
 144                     new InstructionKey(builder.getId())));
 145             wt.commit().addCallback(new FutureCallback<CommitInfo>() {
 146                 @Override
 147                 public void onSuccess(final CommitInfo result) {
 148                     LOG.debug("Instruction Queue {} removed", qid);
 149                 }
 150
 151                 @Override
 152                 public void onFailure(final Throwable trw) {
 153                     LOG.error("Failed to remove Instruction Queue {}", qid, trw);
 154                 }
 155             }, MoreExecutors.directExecutor());
 156         }
 157     }
 158
 159     DefaultInstructionScheduler(final DataBroker dataProvider, final NotificationPublishService notifs,
 160             final Executor executor, final RpcProviderService rpcProviderRegistry,
 161             final ClusterSingletonServiceProvider cssp, final Timer timer, final String instructionId) {
 162         this.dataProvider = requireNonNull(dataProvider);
 163         this.instructionId = requireNonNull(instructionId);
 164         this.notifs = requireNonNull(notifs);
 165         this.executor = requireNonNull(executor);
 166         this.rpcProviderRegistry = requireNonNull(rpcProviderRegistry);
 167         this.timer = requireNonNull(timer);
 168         qid = KeyedInstanceIdentifier.builder(InstructionsQueue.class,
 169                 new InstructionsQueueKey(this.instructionId)).build();
 170         sgi = new ServiceGroupIdentifier(this.instructionId + "-service-group");
 171         LOG.info("Creating Programming Service {}.", sgi.value());
 172         csspReg = cssp.registerClusterSingletonService(this);
 173     }
 174
 175     @Override
 176     public synchronized void instantiateServiceInstance() {
 177         LOG.info("Instruction Queue service {} instantiated", sgi.value());
 178         reg = rpcProviderRegistry.registerRpcImplementations(ImmutableClassToInstanceMap.<Rpc<?, ?>>builder()
 179             .put(CancelInstruction.class, this::cancelInstruction)
 180             .put(CleanInstructions.class, this::cleanInstructions)
 181             .build());
 182
 183         final WriteTransaction wt = dataProvider.newWriteOnlyTransaction();
 184         wt.put(LogicalDatastoreType.OPERATIONAL, qid, new InstructionsQueueBuilder()
 185                 .withKey(new InstructionsQueueKey(instructionId)).setInstruction(Map.of()).build());
 186         wt.commit().addCallback(new FutureCallback<CommitInfo>() {
 187             @Override
 188             public void onSuccess(final CommitInfo result) {
 189                 LOG.debug("Instruction Queue {} added", qid);
 190             }
 191
 192             @Override
 193             public void onFailure(final Throwable trw) {
 194                 LOG.error("Failed to add Instruction Queue {}", qid, trw);
 195             }
 196         }, MoreExecutors.directExecutor());
 197     }
 198
 199     @Override
 200     public ServiceGroupIdentifier getIdentifier() {
 201         return sgi;
 202     }
 203
 204     @VisibleForTesting
 205     ListenableFuture<RpcResult<CancelInstructionOutput>> cancelInstruction(final CancelInstructionInput input) {
 206         return Futures.submit(() -> realCancelInstruction(input), executor);
 207     }
 208
 209     @VisibleForTesting
 210     ListenableFuture<RpcResult<CleanInstructionsOutput>> cleanInstructions(final CleanInstructionsInput input) {
 211         return Futures.submit(() -> realCleanInstructions(input), executor);
 212     }
 213
 214     private synchronized RpcResult<CancelInstructionOutput> realCancelInstruction(final CancelInstructionInput input) {
 215         final InstructionImpl instruction = insns.get(input.getId());
 216         if (instruction == null) {
 217             LOG.debug("Instruction {} not present in the graph", input.getId());
 218
 219             final CancelInstructionOutput out = new CancelInstructionOutputBuilder()
 220                     .setFailure(UnknownInstruction.VALUE).build();
 221             return SuccessfulRpcResult.create(out);
 222         }
 223
 224         return SuccessfulRpcResult.create(new CancelInstructionOutputBuilder()
 225                 .setFailure(instruction.tryCancel(null)).build());
 226     }
 227
 228     private synchronized RpcResult<CleanInstructionsOutput> realCleanInstructions(final CleanInstructionsInput input) {
 229         final Set<InstructionId> failed = new HashSet<>();
 230
 231         for (final InstructionId id : input.getId()) {
 232             // Find the instruction
 233             final InstructionImpl instruction = insns.get(id);
 234             if (instruction == null) {
 235                 LOG.debug("Instruction {} not present in the graph", input.getId());
 236                 failed.add(id);
 237                 continue;
 238             }
 239
 240             // Check its status
 241             switch (instruction.getStatus()) {
 242                 case Cancelled:
 243                 case Failed:
 244                 case Successful:
 245                     break;
 246                 case Executing:
 247                 case Queued:
 248                 case Scheduled:
 249                 case Unknown:
 250                     LOG.debug("Instruction {} cannot be cleaned because of it's in state {}",
 251                             id, instruction.getStatus());
 252                     failed.add(id);
 253                     continue;
 254                 default:
 255                     break;
 256             }
 257
 258             // The instruction is in a terminal state, we need to just unlink
 259             // it from its dependencies and dependents
 260             instruction.clean();
 261
 262             insns.remove(id);
 263             LOG.debug("Instruction {} cleaned successfully", id);
 264         }
 265
 266         final CleanInstructionsOutputBuilder ob = new CleanInstructionsOutputBuilder();
 267         ob.setUnflushed(failed);
 268
 269         return SuccessfulRpcResult.create(ob.build());
 270     }
 271
 272     private List<InstructionImpl> checkDependencies(final SubmitInstructionInput input) throws SchedulerException {
 273         final List<InstructionImpl> dependencies = collectDependencies(input);
 274         // Check if all dependencies are non-failed
 275         final Set<InstructionId> unmet = checkIfUnfailed(dependencies);
 276         /*
 277          *  Some dependencies have failed, declare the request dead-on-arrival
 278          *  and fail the operation.
 279          */
 280         if (!unmet.isEmpty()) {
 281             throw new SchedulerException("Instruction's dependencies are already unsuccessful", new FailureBuilder()
 282                     .setType(DeadOnArrival.VALUE).setFailedPreconditions(unmet).build());
 283         }
 284         return dependencies;
 285     }
 286
 287     private List<InstructionImpl> collectDependencies(final SubmitInstructionInput input) throws SchedulerException {
 288         final List<InstructionImpl> dependencies = new ArrayList<>();
 289         for (final InstructionId pid : input.getPreconditions()) {
 290             final InstructionImpl instruction = insns.get(pid);
 291             if (instruction == null) {
 292                 LOG.info("Instruction {} depends on {}, which is not a known instruction", input.getId(), pid);
 293                 throw new SchedulerException("Unknown dependency ID specified",
 294                         new FailureBuilder().setType(UnknownPreconditionId.VALUE).build());
 295             }
 296             dependencies.add(instruction);
 297         }
 298         return dependencies;
 299     }
 300
 301     private static Set<InstructionId> checkIfUnfailed(final List<InstructionImpl> dependencies) {
 302         final Set<InstructionId> unmet = new HashSet<>();
 303         for (final InstructionImpl d : dependencies) {
 304             switch (d.getStatus()) {
 305                 case Cancelled:
 306                 case Failed:
 307                 case Unknown:
 308                     unmet.add(d.getId());
 309                     break;
 310                 case Executing:
 311                 case Queued:
 312                 case Scheduled:
 313                 case Successful:
 314                     break;
 315                 default:
 316                     break;
 317             }
 318         }
 319         return unmet;
 320     }
 321
 322     @Override
 323     public synchronized ListenableFuture<Instruction> scheduleInstruction(final SubmitInstructionInput input) throws
 324             SchedulerException {
 325         final InstructionId id = input.getId();
 326         if (insns.get(id) != null) {
 327             LOG.info("Instruction ID {} already present", id);
 328             throw new SchedulerException("Instruction ID currently in use",
 329                     new FailureBuilder().setType(DuplicateInstructionId.VALUE).build());
 330         }
 331
 332         // First things first: check the deadline
 333         final Nanotime now = NanotimeUtil.currentTime();
 334         final BigInteger left = input.getDeadline().getValue().toJava().subtract(now.getValue().toJava());
 335
 336         if (left.compareTo(BigInteger.ZERO) <= 0) {
 337             LOG.debug("Instruction {} deadline has already passed by {}ns", id, left);
 338             throw new SchedulerException("Instruction arrived after specified deadline",
 339                     new FailureBuilder().setType(DeadOnArrival.VALUE).build());
 340         }
 341
 342         // Resolve dependencies
 343         final List<InstructionImpl> dependencies = checkDependencies(input);
 344
 345         /*
 346          * All pre-flight checks done are at this point, the following
 347          * steps can only fail in catastrophic scenarios (OOM and the
 348          * like).
 349          */
 350
 351         // Schedule a timeout for the instruction
 352         final Timeout t = timer.newTimeout(timeout -> timeoutInstruction(input.getId()), left.longValue(),
 353                 TimeUnit.NANOSECONDS);
 354
 355         // Put it into the instruction list
 356         final SettableFuture<Instruction> ret = SettableFuture.create();
 357         final InstructionImpl instruction = new InstructionImpl(new InstructionPusher(id, input.getDeadline()), ret, id,
 358                 dependencies, t);
 359         insns.put(id, instruction);
 360
 361         // Attach it into its dependencies
 362         for (final InstructionImpl d : dependencies) {
 363             d.addDependant(instruction);
 364         }
 365
 366         /*
 367          * All done. The next part is checking whether the instruction can
 368          * run, which we can figure out after sending out the acknowledgement.
 369          * This task should be ingress-weighed, so we reinsert it into the
 370          * same execution service.
 371          */
 372         executor.execute(() -> tryScheduleInstruction(instruction));
 373
 374         return ret;
 375     }
 376
 377     @Override
 378     public String getInstructionID() {
 379         return instructionId;
 380     }
 381
 382     private synchronized void timeoutInstruction(final InstructionId id) {
 383         final InstructionImpl instruction = insns.get(id);
 384         if (instruction == null) {
 385             LOG.warn("Instruction {} timed out, but not found in the queue", id);
 386             return;
 387         }
 388
 389         instruction.timeout();
 390     }
 391
 392     private synchronized void tryScheduleDependants(final InstructionImpl instruction) {
 393         // Walk all dependants and try to schedule them
 394         final Iterator<InstructionImpl> it = instruction.getDependants();
 395         while (it.hasNext()) {
 396             tryScheduleInstruction(it.next());
 397         }
 398     }
 399
 400     private synchronized void tryScheduleInstruction(final InstructionImpl instruction) {
 401         final ListenableFuture<ExecutionResult<Details>> f = instruction.ready();
 402         if (f != null) {
 403             Futures.addCallback(f, new FutureCallback<>() {
 404                 @Override
 405                 public void onSuccess(final ExecutionResult<Details> result) {
 406                     tryScheduleDependants(instruction);
 407                 }
 408
 409                 @Override
 410                 public void onFailure(final Throwable trw) {
 411                     LOG.error("Instruction {} failed to execute", instruction.getId(), trw);
 412                 }
 413             }, MoreExecutors.directExecutor());
 414         }
 415     }
 416
 417     @Override
 418     public synchronized FluentFuture<? extends CommitInfo> closeServiceInstance() {
 419         LOG.info("Closing Instruction Queue service {}", sgi.value());
 420
 421         if (reg != null) {
 422             reg.close();
 423             reg = null;
 424         }
 425         for (final InstructionImpl instruction : insns.values()) {
 426             instruction.tryCancel(null);
 427         }
 428         // Workaround for BUG-2283
 429         final WriteTransaction wt = dataProvider.newWriteOnlyTransaction();
 430         wt.delete(LogicalDatastoreType.OPERATIONAL, qid);
 431
 432         final FluentFuture<? extends CommitInfo> future = wt.commit();
 433         future.addCallback(new FutureCallback<CommitInfo>() {
 434             @Override
 435             public void onSuccess(final CommitInfo result) {
 436                 LOG.debug("Instruction Queue {} removed", qid);
 437             }
 438
 439             @Override
 440             public void onFailure(final Throwable trw) {
 441                 LOG.error("Failed to shutdown Instruction Queue {}", qid, trw);
 442             }
 443         }, MoreExecutors.directExecutor());
 444
 445         return future;
 446     }
 447
 448     @Override
 449     public synchronized void close() {
 450         csspReg.close();
 451     }
 452 }