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