DXR is a code search and navigation tool aimed at making sense of large projects. It supports full-text and regex searches as well as structural queries.

Line Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#ifndef mozilla_LabeledEventQueue_h
#define mozilla_LabeledEventQueue_h

#include <stdint.h>
#include "mozilla/AbstractEventQueue.h"
#include "mozilla/LinkedList.h"
#include "mozilla/SchedulerGroup.h"
#include "mozilla/Queue.h"
#include "nsClassHashtable.h"
#include "nsHashKeys.h"

namespace mozilla {

class SchedulerGroup;

// LabeledEventQueue is actually a set of queues. There is one queue for each
// SchedulerGroup, as well as one queue for unlabeled events (those with no
// associated SchedulerGroup). When an event is added to a LabeledEventQueue, we
// query its SchedulerGroup and then add it to the appropriate queue. When an
// event is fetched, we heuristically pick a SchedulerGroup and return an event
// from its queue. Ideally the heuristic should give precedence to
// SchedulerGroups corresponding to the foreground tabs. The correctness of this
// data structure relies on the invariant that events from different
// SchedulerGroups cannot affect each other.
class LabeledEventQueue final : public AbstractEventQueue
{
public:
  explicit LabeledEventQueue(EventPriority aPriority);
  ~LabeledEventQueue();

  void PutEvent(already_AddRefed<nsIRunnable>&& aEvent,
                EventPriority aPriority,
                const MutexAutoLock& aProofOfLock) final;
  already_AddRefed<nsIRunnable> GetEvent(EventPriority* aPriority,
                                         const MutexAutoLock& aProofOfLock) final;

  bool IsEmpty(const MutexAutoLock& aProofOfLock) final;
  size_t Count(const MutexAutoLock& aProofOfLock) const final;
  bool HasReadyEvent(const MutexAutoLock& aProofOfLock) final;

  void EnableInputEventPrioritization(const MutexAutoLock& aProofOfLock) final {}
  void FlushInputEventPrioritization(const MutexAutoLock& aProofOfLock) final {}
  void SuspendInputEventPrioritization(const MutexAutoLock& aProofOfLock) final {}
  void ResumeInputEventPrioritization(const MutexAutoLock& aProofOfLock) final {}

  size_t SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf) const override
  {
    return mEpochs.ShallowSizeOfExcludingThis(aMallocSizeOf) +
           mUnlabeled.ShallowSizeOfExcludingThis(aMallocSizeOf);
  }

private:

  // The basic problem here is to keep track of the ordering relationships
  // between events. As long as there are only labeled events, there can be one
  // queue per SchedulerGroup. However, if an unlabeled event is pushed, we must
  // remember that it should run after all the labeled events currently in the
  // queue. To do this, the queues are arranged in "epochs". Each time the tail
  // of the queue transitions from labeled to unlabeled (or from unlabeled to
  // labeled) a new epoch starts. Events within different epochs are ordered
  // according to which epoch happened first. Within a labeled epoch, there is
  // one queue per SchedulerGroup. So events from different SchedulerGroups
  // within the same epoch are unordered with respect to each other. Within an
  // unlabeled epoch, there is a single queue that orders all the unlabeled
  // events.
  //
  // The data structures we use are:
  // 1. A queue of epochs. For each epoch, we store its epoch number. This number
  // is odd for labeled epochs and even for unlabeled epochs. We also store the
  // number of events in the epoch.
  // 2. A single queue for all unlabeled events. For each event in the queue, we
  // store the runnable as well as the epoch number.
  // 3. For labeled events, one queue for each SchedulerGroup. Each element in
  // these queues also keeps track of the epoch it belongs to.
  //
  // To push an event, we see if we can remain in the same epoch or if we have
  // to start a new one. If we have to start a new one, we push onto the epoch
  // queue. Then, based on whether the event is labeled or not, we push the
  // runnable and the epoch number into the appopriate queue.
  //
  // To pop an event, we look at the epoch at the front of the epoch queue. If
  // it is unlabeled, then we pop the first event in the unlabeled queue. If it
  // is labeled, we can pop from any of the SchedulerGroup queues. Then we
  // decrement the number of events in the current epoch. If this number reaches
  // zero, we pop from the epoch queue.

  struct Epoch
  {
    static Epoch First(bool aIsLabeled)
    {
      // Odd numbers are labeled, even are unlabeled.
      uintptr_t number = aIsLabeled ? 1 : 0;
      return Epoch(number, aIsLabeled);
    }

    static bool EpochNumberIsLabeled(uintptr_t aEpochNumber)
    {
      // Odd numbers are labeled, even are unlabeled.
      return (aEpochNumber & 1) ? true : false;
    }

    uintptr_t mEpochNumber;
    size_t mNumEvents;

    Epoch(uintptr_t aEpochNumber, bool aIsLabeled)
      : mEpochNumber(aEpochNumber)
      , mNumEvents(0)
    {
      MOZ_ASSERT(aIsLabeled == EpochNumberIsLabeled(aEpochNumber));
    }

    bool IsLabeled() const { return EpochNumberIsLabeled(mEpochNumber); }

    Epoch NextEpoch(bool aIsLabeled) const
    {
      MOZ_ASSERT(aIsLabeled == !IsLabeled());
      return Epoch(mEpochNumber + 1, aIsLabeled);
    }
  };

  void PopEpoch();
  static SchedulerGroup* NextSchedulerGroup(SchedulerGroup* aGroup);

  using RunnableEpochQueue = SchedulerGroup::RunnableEpochQueue;
  using EpochQueue = Queue<Epoch, 8>;

  // List of SchedulerGroups that might have events. This is static, so it
  // covers all LabeledEventQueues. If a SchedulerGroup is in this list, it may
  // not have an event in *this* LabeledEventQueue (although it will have an
  // event in *some* LabeledEventQueue). sCurrentSchedulerGroup cycles through
  // the elements of sSchedulerGroups in order.
  static LinkedList<SchedulerGroup>* sSchedulerGroups;
  static size_t sLabeledEventQueueCount;
  static SchedulerGroup* sCurrentSchedulerGroup;

  RunnableEpochQueue mUnlabeled;
  EpochQueue mEpochs;
  size_t mNumEvents = 0;

  // Number of SchedulerGroups that must be processed before we prioritize a
  // visible tab. This field is designed to guarantee a 1:1 interleaving between
  // foreground and background SchedulerGroups. For details, see its usage in
  // LabeledEventQueue.cpp.
  int64_t mAvoidVisibleTabCount = 0;
  EventPriority mPriority;
};

} // namespace mozilla

#endif // mozilla_LabeledEventQueue_h