openflow-protocol-impl/src/main/java/org/opendaylight/openflowjava/protocol/impl/core/connection/AbstractStackedOutboundQueue.java

   1 /*
   2  * Copyright (c) 2015 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
   9 package org.opendaylight.openflowjava.protocol.impl.core.connection;
  10
  11 import com.google.common.base.Preconditions;
  12 import com.google.common.base.Verify;
  13 import com.google.common.util.concurrent.FutureCallback;
  14
  15 import io.netty.channel.Channel;
  16
  17 import java.util.ArrayList;
  18 import java.util.Iterator;
  19 import java.util.List;
  20 import java.util.concurrent.atomic.AtomicLongFieldUpdater;
  21 import java.util.function.Function;
  22
  23 import javax.annotation.Nonnull;
  24 import javax.annotation.concurrent.GuardedBy;
  25
  26 import org.opendaylight.openflowjava.protocol.api.connection.OutboundQueue;
  27 import org.opendaylight.openflowjava.protocol.api.connection.OutboundQueueException;
  28 import org.opendaylight.yang.gen.v1.urn.opendaylight.openflow.protocol.rev130731.MultipartReplyMessage;
  29 import org.opendaylight.yang.gen.v1.urn.opendaylight.openflow.protocol.rev130731.OfHeader;
  30
  31 import org.slf4j.Logger;
  32 import org.slf4j.LoggerFactory;
  33
  34 abstract class AbstractStackedOutboundQueue implements OutboundQueue {
  35
  36     private static final Logger LOG = LoggerFactory.getLogger(AbstractStackedOutboundQueue.class);
  37     protected static final AtomicLongFieldUpdater<AbstractStackedOutboundQueue> LAST_XID_OFFSET_UPDATER = AtomicLongFieldUpdater
  38             .newUpdater(AbstractStackedOutboundQueue.class, "lastXid");
  39
  40     @GuardedBy("unflushedSegments")
  41     protected volatile StackedSegment firstSegment;
  42     @GuardedBy("unflushedSegments")
  43     protected final List<StackedSegment> unflushedSegments = new ArrayList<>(2);
  44     @GuardedBy("unflushedSegments")
  45     protected final List<StackedSegment> uncompletedSegments = new ArrayList<>(2);
  46
  47     private volatile long lastXid = -1;
  48     private volatile long allocatedXid = -1;
  49
  50     @GuardedBy("unflushedSegments")
  51     protected Integer shutdownOffset;
  52
  53     // Accessed from Netty only
  54     protected int flushOffset;
  55
  56     protected final AbstractOutboundQueueManager<?, ?> manager;
  57
  58     AbstractStackedOutboundQueue(final AbstractOutboundQueueManager<?, ?> manager) {
  59         this.manager = Preconditions.checkNotNull(manager);
  60         firstSegment = StackedSegment.create(0L);
  61         uncompletedSegments.add(firstSegment);
  62         unflushedSegments.add(firstSegment);
  63     }
  64
  65     @Override
  66     public void commitEntry(final Long xid, final OfHeader message, final FutureCallback<OfHeader> callback) {
  67         commitEntry(xid, message, callback, OutboundQueueEntry.DEFAULT_IS_COMPLETE);
  68     }
  69
  70     @GuardedBy("unflushedSegments")
  71     protected void ensureSegment(final StackedSegment first, final int offset) {
  72         final int segmentOffset = offset / StackedSegment.SEGMENT_SIZE;
  73         LOG.debug("Queue {} slow offset {} maps to {} segments {}", this, offset, segmentOffset, unflushedSegments.size());
  74
  75         for (int i = unflushedSegments.size(); i <= segmentOffset; ++i) {
  76             final StackedSegment newSegment = StackedSegment.create(first.getBaseXid() + (StackedSegment.SEGMENT_SIZE * i));
  77             LOG.debug("Adding segment {}", newSegment);
  78             unflushedSegments.add(newSegment);
  79         }
  80
  81         allocatedXid = unflushedSegments.get(unflushedSegments.size() - 1).getEndXid();
  82     }
  83
  84     /*
  85      * This method is expected to be called from multiple threads concurrently.
  86      */
  87     @Override
  88     public Long reserveEntry() {
  89         final long xid = LAST_XID_OFFSET_UPDATER.incrementAndGet(this);
  90         final StackedSegment fastSegment = firstSegment;
  91
  92         if (xid >= fastSegment.getBaseXid() + StackedSegment.SEGMENT_SIZE) {
  93             if (xid >= allocatedXid) {
  94                 // Multiple segments, this a slow path
  95                 LOG.debug("Queue {} falling back to slow reservation for XID {}", this, xid);
  96
  97                 synchronized (unflushedSegments) {
  98                     LOG.debug("Queue {} executing slow reservation for XID {}", this, xid);
  99
 100                     // Shutdown was scheduled, need to fail the reservation
 101                     if (shutdownOffset != null) {
 102                         LOG.debug("Queue {} is being shutdown, failing reservation", this);
 103                         return null;
 104                     }
 105
 106                     // Ensure we have the appropriate segment for the specified XID
 107                     final StackedSegment slowSegment = firstSegment;
 108                     final int slowOffset = (int) (xid - slowSegment.getBaseXid());
 109                     Verify.verify(slowOffset >= 0);
 110
 111                     // Now, we let's see if we need to allocate a new segment
 112                     ensureSegment(slowSegment, slowOffset);
 113
 114                     LOG.debug("Queue {} slow reservation finished", this);
 115                 }
 116             } else {
 117                 LOG.debug("Queue {} XID {} is already backed", this, xid);
 118             }
 119         }
 120
 121         LOG.trace("Queue {} allocated XID {}", this, xid);
 122         return xid;
 123     }
 124
 125     /**
 126      * Write some entries from the queue to the channel. Guaranteed to run
 127      * in the corresponding EventLoop.
 128      *
 129      * @param channel Channel onto which we are writing
 130      * @param now
 131      * @return Number of entries written out
 132      */
 133     int writeEntries(@Nonnull final Channel channel, final long now) {
 134         // Local cache
 135         StackedSegment segment = firstSegment;
 136         int entries = 0;
 137
 138         while (channel.isWritable()) {
 139             final OutboundQueueEntry entry = segment.getEntry(flushOffset);
 140             if (!entry.isCommitted()) {
 141                 LOG.debug("Queue {} XID {} segment {} offset {} not committed yet", this, segment.getBaseXid() + flushOffset, segment, flushOffset);
 142                 break;
 143             }
 144
 145             LOG.trace("Queue {} flushing entry at offset {}", this, flushOffset);
 146             final OfHeader message = entry.takeMessage();
 147             flushOffset++;
 148             entries++;
 149
 150             if (message != null) {
 151                 manager.writeMessage(message, now);
 152             } else {
 153                 entry.complete(null);
 154             }
 155
 156             if (flushOffset >= StackedSegment.SEGMENT_SIZE) {
 157                 /*
 158                  * Slow path: purge the current segment unless it's the last one.
 159                  * If it is, we leave it for replacement when a new reservation
 160                  * is run on it.
 161                  *
 162                  * This costs us two slow paths, but hey, this should be very rare,
 163                  * so let's keep things simple.
 164                  */
 165                 synchronized (unflushedSegments) {
 166                     LOG.debug("Flush offset {} unflushed segments {}", flushOffset, unflushedSegments.size());
 167
 168                     // We may have raced ahead of reservation code and need to allocate a segment
 169                     ensureSegment(segment, flushOffset);
 170
 171                     // Remove the segment, update the firstSegment and reset flushOffset
 172                     final StackedSegment oldSegment = unflushedSegments.remove(0);
 173                     if (oldSegment.isComplete()) {
 174                         uncompletedSegments.remove(oldSegment);
 175                         oldSegment.recycle();
 176                     }
 177
 178                     // Reset the first segment and add it to the uncompleted list
 179                     segment = unflushedSegments.get(0);
 180                     uncompletedSegments.add(segment);
 181
 182                     // Update the shutdown offset
 183                     if (shutdownOffset != null) {
 184                         shutdownOffset -= StackedSegment.SEGMENT_SIZE;
 185                     }
 186
 187                     // Allow reservations back on the fast path by publishing the new first segment
 188                     firstSegment = segment;
 189
 190                     flushOffset = 0;
 191                     LOG.debug("Queue {} flush moved to segment {}", this, segment);
 192                 }
 193             }
 194         }
 195
 196         return entries;
 197     }
 198
 199     boolean pairRequest(final OfHeader message) {
 200         Iterator<StackedSegment> it = uncompletedSegments.iterator();
 201         while (it.hasNext()) {
 202             final StackedSegment queue = it.next();
 203             final OutboundQueueEntry entry = queue.pairRequest(message);
 204             if (entry == null) {
 205                 continue;
 206             }
 207
 208             LOG.trace("Queue {} accepted response {}", queue, message);
 209
 210             // This has been a barrier request, we need to flush all
 211             // previous queues
 212             if (entry.isBarrier() && uncompletedSegments.size() > 1) {
 213                 LOG.trace("Queue {} indicated request was a barrier", queue);
 214
 215                 it = uncompletedSegments.iterator();
 216                 while (it.hasNext()) {
 217                     final StackedSegment q = it.next();
 218
 219                     // We want to complete all queues before the current one, we will
 220                     // complete the current queue below
 221                     if (!queue.equals(q)) {
 222                         LOG.trace("Queue {} is implied finished", q);
 223                         q.completeAll();
 224                         it.remove();
 225                         q.recycle();
 226                     } else {
 227                         break;
 228                     }
 229                 }
 230             }
 231
 232             if (queue.isComplete()) {
 233                 LOG.trace("Queue {} is finished", queue);
 234                 it.remove();
 235                 queue.recycle();
 236             }
 237
 238             return true;
 239         }
 240
 241         LOG.debug("Failed to find completion for message {}", message);
 242         return false;
 243     }
 244
 245     boolean needsFlush() {
 246         // flushOffset always points to the first entry, which can be changed only
 247         // from Netty, so we are fine here.
 248         if (firstSegment.getBaseXid() + flushOffset > lastXid) {
 249             return false;
 250         }
 251
 252         if (shutdownOffset != null && flushOffset >= shutdownOffset) {
 253             return false;
 254         }
 255
 256         return firstSegment.getEntry(flushOffset).isCommitted();
 257     }
 258
 259     long startShutdown() {
 260         /*
 261          * We are dealing with a multi-threaded shutdown, as the user may still
 262          * be reserving entries in the queue. We are executing in a netty thread,
 263          * so neither flush nor barrier can be running, which is good news.
 264          * We will eat up all the slots in the queue here and mark the offset first
 265          * reserved offset and free up all the cached queues. We then schedule
 266          * the flush task, which will deal with the rest of the shutdown process.
 267          */
 268         synchronized (unflushedSegments) {
 269             // Increment the offset by the segment size, preventing fast path allocations,
 270             // since we are holding the slow path lock, any reservations will see the queue
 271             // in shutdown and fail accordingly.
 272             final long xid = LAST_XID_OFFSET_UPDATER.addAndGet(this, StackedSegment.SEGMENT_SIZE);
 273             shutdownOffset = (int) (xid - firstSegment.getBaseXid() - StackedSegment.SEGMENT_SIZE);
 274
 275             // Fails all uncompleted entries, because they will never be completed due to disconnected channel.
 276             return lockedFailSegments(uncompletedSegments.iterator());
 277         }
 278     }
 279
 280     /**
 281      * Checks if the shutdown is in final phase -> all allowed entries (number of entries < shutdownOffset) are flushed
 282      * and fails all not completed entries (if in final phase)
 283      * @param channel netty channel
 284      * @return true if in final phase, false if a flush is needed
 285      */
 286     boolean finishShutdown(final Channel channel) {
 287         boolean needsFlush;
 288         synchronized (unflushedSegments) {
 289             // Fails all entries, that were flushed in shutdownOffset (became uncompleted)
 290             // - they will never be completed due to disconnected channel.
 291             lockedFailSegments(uncompletedSegments.iterator());
 292             // If no further flush is needed or we are not able to write to channel anymore, then we fail all unflushed
 293             // segments, so that each enqueued entry is reported as unsuccessful due to channel disconnection.
 294             // No further entries should be enqueued by this time.
 295             needsFlush = channel.isWritable() && needsFlush();
 296             if (!needsFlush) {
 297                 lockedFailSegments(unflushedSegments.iterator());
 298             }
 299         }
 300         return !needsFlush;
 301     }
 302
 303     protected OutboundQueueEntry getEntry(final Long xid) {
 304         final StackedSegment fastSegment = firstSegment;
 305         final long calcOffset = xid - fastSegment.getBaseXid();
 306         Preconditions.checkArgument(calcOffset >= 0, "Commit of XID %s does not match up with base XID %s", xid, fastSegment.getBaseXid());
 307
 308         Verify.verify(calcOffset <= Integer.MAX_VALUE);
 309         final int fastOffset = (int) calcOffset;
 310
 311         if (fastOffset >= StackedSegment.SEGMENT_SIZE) {
 312             LOG.debug("Queue {} falling back to slow commit of XID {} at offset {}", this, xid, fastOffset);
 313
 314             final StackedSegment segment;
 315             final int slowOffset;
 316             synchronized (unflushedSegments) {
 317                 final StackedSegment slowSegment = firstSegment;
 318                 final long slowCalcOffset = xid - slowSegment.getBaseXid();
 319                 Verify.verify(slowCalcOffset >= 0 && slowCalcOffset <= Integer.MAX_VALUE);
 320                 slowOffset = (int) slowCalcOffset;
 321
 322                 LOG.debug("Queue {} recalculated offset of XID {} to {}", this, xid, slowOffset);
 323                 segment = unflushedSegments.get(slowOffset / StackedSegment.SEGMENT_SIZE);
 324             }
 325
 326             final int segOffset = slowOffset % StackedSegment.SEGMENT_SIZE;
 327             LOG.debug("Queue {} slow commit of XID {} completed at offset {} (segment {} offset {})", this, xid, slowOffset, segment, segOffset);
 328             return segment.getEntry(segOffset);
 329         }
 330         return fastSegment.getEntry(fastOffset);
 331     }
 332
 333     /**
 334      * Fails not completed entries in segments and frees completed segments
 335      * @param iterator list of segments to be failed
 336      * @return number of failed entries
 337      */
 338     @GuardedBy("unflushedSegments")
 339     private long lockedFailSegments(Iterator<StackedSegment> iterator) {
 340         long entries = 0;
 341
 342         // Fail all queues
 343         while (iterator.hasNext()) {
 344             final StackedSegment segment = iterator.next();
 345
 346             entries += segment.failAll(OutboundQueueException.DEVICE_DISCONNECTED);
 347             if (segment.isComplete()) {
 348                 LOG.trace("Cleared segment {}", segment);
 349                 iterator.remove();
 350             }
 351         }
 352
 353         return entries;
 354     }
 355
 356 }