Create shared timeline data structure and unit test cases

This change adds the necessary classes for the graphics shared timeline.

Bug: 162889810
Test: libsurfaceflinger_unittest --gtest_filter='FrameTimelineTest*'
Change-Id: I7310a8e0793b2d640d873814bb5a9ba83c76a196
diff --git a/services/surfaceflinger/Android.bp b/services/surfaceflinger/Android.bp
index b039f6e..5299a37 100644
--- a/services/surfaceflinger/Android.bp
+++ b/services/surfaceflinger/Android.bp
@@ -68,6 +68,7 @@
     },
     static_libs: [
         "libcompositionengine",
+        "libframetimeline",
         "libperfetto_client_experimental",
         "librenderengine",
         "libserviceutils",
diff --git a/services/surfaceflinger/FrameTimeline/Android.bp b/services/surfaceflinger/FrameTimeline/Android.bp
new file mode 100644
index 0000000..6ba4c43
--- /dev/null
+++ b/services/surfaceflinger/FrameTimeline/Android.bp
@@ -0,0 +1,16 @@
+cc_library_static {
+    name: "libframetimeline",
+    defaults: ["surfaceflinger_defaults"],
+    srcs: [
+        "FrameTimeline.cpp",
+    ],
+    shared_libs: [
+        "libbase",
+        "libcutils",
+        "liblog",
+        "libgui",
+        "libui",
+        "libutils",
+    ],
+    export_include_dirs: ["."],
+}
diff --git a/services/surfaceflinger/FrameTimeline/FrameTimeline.cpp b/services/surfaceflinger/FrameTimeline/FrameTimeline.cpp
new file mode 100644
index 0000000..c95440a
--- /dev/null
+++ b/services/surfaceflinger/FrameTimeline/FrameTimeline.cpp
@@ -0,0 +1,226 @@
+/*
+ * Copyright 2020 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#undef LOG_TAG
+#define LOG_TAG "FrameTimeline"
+#define ATRACE_TAG ATRACE_TAG_GRAPHICS
+
+#include "FrameTimeline.h"
+#include <android-base/stringprintf.h>
+#include <cinttypes>
+
+namespace android::frametimeline::impl {
+
+using base::StringAppendF;
+
+int64_t TokenManager::generateTokenForPredictions(TimelineItem&& predictions) {
+    std::lock_guard<std::mutex> lock(mMutex);
+    const int64_t assignedToken = mCurrentToken++;
+    mPredictions[assignedToken] = predictions;
+    mTokens.emplace_back(std::make_pair(assignedToken, systemTime()));
+    flushTokens(systemTime());
+    return assignedToken;
+}
+
+std::optional<TimelineItem> TokenManager::getPredictionsForToken(int64_t token) {
+    std::lock_guard<std::mutex> lock(mMutex);
+    flushTokens(systemTime());
+    auto predictionsIterator = mPredictions.find(token);
+    if (predictionsIterator != mPredictions.end()) {
+        return predictionsIterator->second;
+    }
+    return {};
+}
+
+void TokenManager::flushTokens(nsecs_t flushTime) {
+    for (size_t i = 0; i < mTokens.size(); i++) {
+        if (flushTime - mTokens[i].second >= kMaxRetentionTime) {
+            mPredictions.erase(mTokens[i].first);
+            mTokens.erase(mTokens.begin() + static_cast<int>(i));
+            --i;
+        } else {
+            // Tokens are ordered by time. If i'th token is within the retention time, then the
+            // i+1'th token will also be within retention time.
+            break;
+        }
+    }
+}
+
+SurfaceFrame::SurfaceFrame(const std::string& layerName, PredictionState predictionState,
+                           frametimeline::TimelineItem&& predictions)
+      : mLayerName(layerName),
+        mPresentState(PresentState::Unknown),
+        mPredictionState(predictionState),
+        mPredictions(predictions),
+        mActuals({0, 0, 0}),
+        mActualQueueTime(0) {}
+
+void SurfaceFrame::setPresentState(PresentState state) {
+    std::lock_guard<std::mutex> lock(mMutex);
+    mPresentState = state;
+}
+
+PredictionState SurfaceFrame::getPredictionState() {
+    std::lock_guard<std::mutex> lock(mMutex);
+    return mPredictionState;
+}
+
+SurfaceFrame::PresentState SurfaceFrame::getPresentState() {
+    std::lock_guard<std::mutex> lock(mMutex);
+    return mPresentState;
+}
+
+TimelineItem SurfaceFrame::getActuals() {
+    std::lock_guard<std::mutex> lock(mMutex);
+    return mActuals;
+}
+
+void SurfaceFrame::setActuals(frametimeline::TimelineItem&& actuals) {
+    std::lock_guard<std::mutex> lock(mMutex);
+    mActuals = actuals;
+}
+
+void SurfaceFrame::setPresentTime(nsecs_t presentTime) {
+    std::lock_guard<std::mutex> lock(mMutex);
+    mActuals.presentTime = presentTime;
+}
+
+void SurfaceFrame::dump(std::string& result) {
+    std::lock_guard<std::mutex> lock(mMutex);
+    StringAppendF(&result, "Predicted Start Time : %" PRId64 "\n", mPredictions.startTime);
+    StringAppendF(&result, "Actual Start Time : %" PRId64 "\n", mActuals.startTime);
+    StringAppendF(&result, "Actual Queue Time : %" PRId64 "\n", mActualQueueTime);
+    StringAppendF(&result, "Predicted Render Complete Time : %" PRId64 "\n", mPredictions.endTime);
+    StringAppendF(&result, "Actual Render Complete Time : %" PRId64 "\n", mActuals.endTime);
+    StringAppendF(&result, "Predicted Present Time : %" PRId64 "\n", mPredictions.presentTime);
+    StringAppendF(&result, "Actual Present Time : %" PRId64 "\n", mActuals.presentTime);
+}
+
+FrameTimeline::FrameTimeline() : mCurrentDisplayFrame(std::make_shared<DisplayFrame>()) {}
+
+FrameTimeline::DisplayFrame::DisplayFrame()
+      : surfaceFlingerPredictions(TimelineItem()),
+        surfaceFlingerActuals(TimelineItem()),
+        predictionState(PredictionState::None) {
+    this->surfaceFrames.reserve(kNumSurfaceFramesInitial);
+}
+
+std::unique_ptr<android::frametimeline::SurfaceFrame> FrameTimeline::createSurfaceFrameForToken(
+        const std::string& layerName, std::optional<int64_t> token) {
+    if (!token) {
+        return std::make_unique<impl::SurfaceFrame>(layerName, PredictionState::None,
+                                                    TimelineItem());
+    }
+    std::optional<TimelineItem> predictions = mTokenManager.getPredictionsForToken(*token);
+    if (predictions) {
+        return std::make_unique<impl::SurfaceFrame>(layerName, PredictionState::Valid,
+                                                    std::move(*predictions));
+    }
+    return std::make_unique<impl::SurfaceFrame>(layerName, PredictionState::Expired,
+                                                TimelineItem());
+}
+
+void FrameTimeline::addSurfaceFrame(
+        std::unique_ptr<android::frametimeline::SurfaceFrame> surfaceFrame,
+        SurfaceFrame::PresentState state) {
+    surfaceFrame->setPresentState(state);
+    std::unique_ptr<impl::SurfaceFrame> implSurfaceFrame(
+            static_cast<impl::SurfaceFrame*>(surfaceFrame.release()));
+    std::lock_guard<std::mutex> lock(mMutex);
+    mCurrentDisplayFrame->surfaceFrames.push_back(std::move(implSurfaceFrame));
+}
+
+void FrameTimeline::setSfWakeUp(int64_t token, nsecs_t wakeUpTime) {
+    const std::optional<TimelineItem> prediction = mTokenManager.getPredictionsForToken(token);
+    std::lock_guard<std::mutex> lock(mMutex);
+    if (!prediction) {
+        mCurrentDisplayFrame->predictionState = PredictionState::Expired;
+    } else {
+        mCurrentDisplayFrame->surfaceFlingerPredictions = *prediction;
+    }
+    mCurrentDisplayFrame->surfaceFlingerActuals.startTime = wakeUpTime;
+}
+
+void FrameTimeline::setSfPresent(nsecs_t sfPresentTime,
+                                 const std::shared_ptr<FenceTime>& presentFence) {
+    std::lock_guard<std::mutex> lock(mMutex);
+    mCurrentDisplayFrame->surfaceFlingerActuals.endTime = sfPresentTime;
+    mPendingPresentFences.emplace_back(std::make_pair(presentFence, mCurrentDisplayFrame));
+    flushPendingPresentFences();
+    finalizeCurrentDisplayFrame();
+}
+
+void FrameTimeline::flushPendingPresentFences() {
+    for (size_t i = 0; i < mPendingPresentFences.size(); i++) {
+        const auto& pendingPresentFence = mPendingPresentFences[i];
+        nsecs_t signalTime = Fence::SIGNAL_TIME_INVALID;
+        if (pendingPresentFence.first && pendingPresentFence.first->isValid()) {
+            signalTime = pendingPresentFence.first->getSignalTime();
+            if (signalTime == Fence::SIGNAL_TIME_PENDING) {
+                continue;
+            }
+        }
+        if (signalTime != Fence::SIGNAL_TIME_INVALID) {
+            auto& displayFrame = pendingPresentFence.second;
+            displayFrame->surfaceFlingerActuals.presentTime = signalTime;
+            for (auto& surfaceFrame : displayFrame->surfaceFrames) {
+                if (surfaceFrame->getPresentState() == SurfaceFrame::PresentState::Presented) {
+                    // Only presented SurfaceFrames need to be updated
+                    surfaceFrame->setPresentTime(signalTime);
+                }
+            }
+        }
+
+        mPendingPresentFences.erase(mPendingPresentFences.begin() + static_cast<int>(i));
+        --i;
+    }
+}
+
+void FrameTimeline::finalizeCurrentDisplayFrame() {
+    while (mDisplayFrames.size() >= kMaxDisplayFrames) {
+        // We maintain only a fixed number of frames' data. Pop older frames
+        mDisplayFrames.pop_front();
+    }
+    mDisplayFrames.push_back(mCurrentDisplayFrame);
+    mCurrentDisplayFrame.reset();
+    mCurrentDisplayFrame = std::make_shared<DisplayFrame>();
+}
+
+void FrameTimeline::dump(std::string& result) {
+    std::lock_guard<std::mutex> lock(mMutex);
+    StringAppendF(&result, "Number of display frames : %d\n", (int)mDisplayFrames.size());
+    for (const auto& displayFrame : mDisplayFrames) {
+        StringAppendF(&result, "---Display Frame---\n");
+        StringAppendF(&result, "Predicted SF wake time : %" PRId64 "\n",
+                      displayFrame->surfaceFlingerPredictions.startTime);
+        StringAppendF(&result, "Actual SF wake time : %" PRId64 "\n",
+                      displayFrame->surfaceFlingerActuals.startTime);
+        StringAppendF(&result, "Predicted SF Complete time : %" PRId64 "\n",
+                      displayFrame->surfaceFlingerPredictions.endTime);
+        StringAppendF(&result, "Actual SF Complete time : %" PRId64 "\n",
+                      displayFrame->surfaceFlingerActuals.endTime);
+        StringAppendF(&result, "Predicted Present time : %" PRId64 "\n",
+                      displayFrame->surfaceFlingerPredictions.presentTime);
+        StringAppendF(&result, "Actual Present time : %" PRId64 "\n",
+                      displayFrame->surfaceFlingerActuals.presentTime);
+        for (size_t i = 0; i < displayFrame->surfaceFrames.size(); i++) {
+            StringAppendF(&result, "Surface frame - %" PRId32 "\n", (int)i);
+            displayFrame->surfaceFrames[i]->dump(result);
+        }
+    }
+}
+
+} // namespace android::frametimeline::impl
diff --git a/services/surfaceflinger/FrameTimeline/FrameTimeline.h b/services/surfaceflinger/FrameTimeline/FrameTimeline.h
new file mode 100644
index 0000000..291e30e
--- /dev/null
+++ b/services/surfaceflinger/FrameTimeline/FrameTimeline.h
@@ -0,0 +1,232 @@
+/*
+ * Copyright 2020 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#pragma once
+
+#include <deque>
+#include <mutex>
+
+#include <ui/FenceTime.h>
+#include <utils/RefBase.h>
+#include <utils/Timers.h>
+
+namespace android::frametimeline {
+
+class FrameTimelineTest;
+
+/*
+ * Collection of timestamps that can be used for both predictions and actual times.
+ */
+struct TimelineItem {
+    TimelineItem(const nsecs_t startTime = 0, const nsecs_t endTime = 0,
+                 const nsecs_t presentTime = 0)
+          : startTime(startTime), endTime(endTime), presentTime(presentTime) {}
+
+    nsecs_t startTime;
+    nsecs_t endTime;
+    nsecs_t presentTime;
+};
+
+/*
+ * TokenManager generates a running number token for a set of predictions made by VsyncPredictor. It
+ * saves these predictions for a short period of time and returns the predictions for a given token,
+ * if it hasn't expired.
+ */
+class TokenManager {
+public:
+    virtual ~TokenManager() = default;
+
+    // Generates a token for the given set of predictions. Stores the predictions for 120ms and
+    // destroys it later.
+    virtual int64_t generateTokenForPredictions(TimelineItem&& prediction);
+};
+
+enum class PredictionState {
+    Valid,   // Predictions obtained successfully from the TokenManager
+    Expired, // TokenManager no longer has the predictions
+    None,    // Predictions are either not present or didn't come from TokenManager
+};
+
+/*
+ * Stores a set of predictions and the corresponding actual timestamps pertaining to a single frame
+ * from the app
+ */
+class SurfaceFrame {
+public:
+    enum class PresentState {
+        Presented, // Buffer was latched and presented by SurfaceFlinger
+        Dropped,   // Buffer was dropped by SurfaceFlinger
+        Unknown,   // Initial state, SurfaceFlinger hasn't seen this buffer yet
+    };
+
+    virtual ~SurfaceFrame() = default;
+
+    virtual TimelineItem getPredictions() = 0;
+    virtual TimelineItem getActuals() = 0;
+    virtual PresentState getPresentState() = 0;
+    virtual PredictionState getPredictionState() = 0;
+
+    virtual void setPresentState(PresentState state) = 0;
+    virtual void setActuals(TimelineItem&& actuals) = 0;
+
+    // There is no prediction for Queue time and it is not a part of TimelineItem. Set it
+    // separately.
+    virtual void setActualQueueTime(nsecs_t actualQueueTime) = 0;
+};
+
+/*
+ * Maintains a history of SurfaceFrames grouped together by the vsync time in which they were
+ * presented
+ */
+class FrameTimeline {
+public:
+    virtual ~FrameTimeline() = default;
+    virtual TokenManager& getTokenManager() = 0;
+
+    // Create a new surface frame, set the predictions based on a token and return it to the caller.
+    // Sets the PredictionState of SurfaceFrame.
+    virtual std::unique_ptr<SurfaceFrame> createSurfaceFrameForToken(
+            const std::string& layerName, std::optional<int64_t> token) = 0;
+
+    // Adds a new SurfaceFrame to the current DisplayFrame. Frames from multiple layers can be
+    // composited into one display frame.
+    virtual void addSurfaceFrame(std::unique_ptr<SurfaceFrame> surfaceFrame,
+                                 SurfaceFrame::PresentState state) = 0;
+
+    // The first function called by SF for the current DisplayFrame. Fetches SF predictions based on
+    // the token and sets the actualSfWakeTime for the current DisplayFrame.
+    virtual void setSfWakeUp(int64_t token, nsecs_t wakeupTime) = 0;
+
+    // Sets the sfPresentTime and finalizes the current DisplayFrame. Tracks the given present fence
+    // until it's signaled, and updates the present timestamps of all presented SurfaceFrames in
+    // that vsync.
+    virtual void setSfPresent(nsecs_t sfPresentTime,
+                              const std::shared_ptr<FenceTime>& presentFence) = 0;
+};
+
+namespace impl {
+
+using namespace std::chrono_literals;
+
+class TokenManager : public android::frametimeline::TokenManager {
+public:
+    TokenManager() : mCurrentToken(0) {}
+    ~TokenManager() = default;
+
+    int64_t generateTokenForPredictions(TimelineItem&& predictions) override;
+    std::optional<TimelineItem> getPredictionsForToken(int64_t token);
+
+private:
+    // Friend class for testing
+    friend class android::frametimeline::FrameTimelineTest;
+
+    void flushTokens(nsecs_t flushTime) REQUIRES(mMutex);
+
+    std::unordered_map<int64_t, TimelineItem> mPredictions GUARDED_BY(mMutex);
+    std::vector<std::pair<int64_t, nsecs_t>> mTokens GUARDED_BY(mMutex);
+    int64_t mCurrentToken GUARDED_BY(mMutex);
+    std::mutex mMutex;
+    static constexpr nsecs_t kMaxRetentionTime =
+            std::chrono::duration_cast<std::chrono::nanoseconds>(120ms).count();
+};
+
+class SurfaceFrame : public android::frametimeline::SurfaceFrame {
+public:
+    SurfaceFrame(const std::string& layerName, PredictionState predictionState,
+                 TimelineItem&& predictions);
+    ~SurfaceFrame() = default;
+
+    TimelineItem getPredictions() override { return mPredictions; };
+    TimelineItem getActuals() override;
+    PresentState getPresentState() override;
+    PredictionState getPredictionState() override;
+    void setActuals(TimelineItem&& actuals) override;
+    void setActualQueueTime(nsecs_t actualQueueTime) override {
+        mActualQueueTime = actualQueueTime;
+    };
+    void setPresentState(PresentState state) override;
+    void setPresentTime(nsecs_t presentTime);
+    void dump(std::string& result);
+
+private:
+    const std::string mLayerName;
+    PresentState mPresentState GUARDED_BY(mMutex);
+    PredictionState mPredictionState GUARDED_BY(mMutex);
+    const TimelineItem mPredictions;
+    TimelineItem mActuals GUARDED_BY(mMutex);
+    nsecs_t mActualQueueTime;
+    std::mutex mMutex;
+};
+
+class FrameTimeline : public android::frametimeline::FrameTimeline {
+public:
+    FrameTimeline();
+    ~FrameTimeline() = default;
+
+    frametimeline::TokenManager& getTokenManager() override { return mTokenManager; }
+    std::unique_ptr<frametimeline::SurfaceFrame> createSurfaceFrameForToken(
+            const std::string& layerName, std::optional<int64_t> token) override;
+    void addSurfaceFrame(std::unique_ptr<frametimeline::SurfaceFrame> surfaceFrame,
+                         SurfaceFrame::PresentState state) override;
+    void setSfWakeUp(int64_t token, nsecs_t wakeupTime) override;
+    void setSfPresent(nsecs_t sfPresentTime,
+                      const std::shared_ptr<FenceTime>& presentFence) override;
+    void dump(std::string& result);
+
+private:
+    // Friend class for testing
+    friend class android::frametimeline::FrameTimelineTest;
+
+    /*
+     * DisplayFrame should be used only internally within FrameTimeline.
+     */
+    struct DisplayFrame {
+        DisplayFrame();
+
+        /* Usage of TimelineItem w.r.t SurfaceFlinger
+         * startTime    Time when SurfaceFlinger wakes up to handle transactions and buffer updates
+         * endTime      Time when SurfaceFlinger sends a composited frame to Display
+         * presentTime  Time when the composited frame was presented on screen
+         */
+        TimelineItem surfaceFlingerPredictions;
+        TimelineItem surfaceFlingerActuals;
+
+        // Collection of predictions and actual values sent over by Layers
+        std::vector<std::unique_ptr<SurfaceFrame>> surfaceFrames;
+
+        PredictionState predictionState;
+    };
+
+    void flushPendingPresentFences() REQUIRES(mMutex);
+    void finalizeCurrentDisplayFrame() REQUIRES(mMutex);
+
+    // Sliding window of display frames. TODO(b/168072834): compare perf with fixed size array
+    std::deque<std::shared_ptr<DisplayFrame>> mDisplayFrames GUARDED_BY(mMutex);
+    std::vector<std::pair<std::shared_ptr<FenceTime>, std::shared_ptr<DisplayFrame>>>
+            mPendingPresentFences GUARDED_BY(mMutex);
+    std::shared_ptr<DisplayFrame> mCurrentDisplayFrame GUARDED_BY(mMutex);
+    TokenManager mTokenManager;
+    std::mutex mMutex;
+    static constexpr uint32_t kMaxDisplayFrames = 64;
+    // The initial container size for the vector<SurfaceFrames> inside display frame. Although this
+    // number doesn't represent any bounds on the number of surface frames that can go in a display
+    // frame, this is a good starting size for the vector so that we can avoid the internal vector
+    // resizing that happens with push_back.
+    static constexpr uint32_t kNumSurfaceFramesInitial = 10;
+};
+
+} // namespace impl
+} // namespace android::frametimeline
diff --git a/services/surfaceflinger/SurfaceFlinger.cpp b/services/surfaceflinger/SurfaceFlinger.cpp
index 7572be3..020f954 100644
--- a/services/surfaceflinger/SurfaceFlinger.cpp
+++ b/services/surfaceflinger/SurfaceFlinger.cpp
@@ -108,6 +108,7 @@
 #include "DisplayRenderArea.h"
 #include "EffectLayer.h"
 #include "Effects/Daltonizer.h"
+#include "FrameTimeline/FrameTimeline.h"
 #include "FrameTracer/FrameTracer.h"
 #include "Layer.h"
 #include "LayerRenderArea.h"
@@ -334,6 +335,7 @@
         mInterceptor(mFactory.createSurfaceInterceptor(this)),
         mTimeStats(std::make_shared<impl::TimeStats>()),
         mFrameTracer(std::make_unique<FrameTracer>()),
+        mFrameTimeline(std::make_shared<frametimeline::impl::FrameTimeline>()),
         mEventQueue(mFactory.createMessageQueue()),
         mCompositionEngine(mFactory.createCompositionEngine()),
         mInternalDisplayDensity(getDensityFromProperty("ro.sf.lcd_density", true)),
diff --git a/services/surfaceflinger/SurfaceFlinger.h b/services/surfaceflinger/SurfaceFlinger.h
index fb79989..b9abb43 100644
--- a/services/surfaceflinger/SurfaceFlinger.h
+++ b/services/surfaceflinger/SurfaceFlinger.h
@@ -98,6 +98,10 @@
 class TimeStats;
 class FrameTracer;
 
+namespace frametimeline {
+class FrameTimeline;
+}
+
 namespace os {
     class IInputFlinger;
 }
@@ -1124,6 +1128,7 @@
 
     const std::shared_ptr<TimeStats> mTimeStats;
     const std::unique_ptr<FrameTracer> mFrameTracer;
+    const std::shared_ptr<frametimeline::FrameTimeline> mFrameTimeline;
     bool mUseHwcVirtualDisplays = false;
     // If blurs should be enabled on this device.
     bool mSupportsBlur = false;
diff --git a/services/surfaceflinger/tests/unittests/Android.bp b/services/surfaceflinger/tests/unittests/Android.bp
index 8d4aa0c..036e7e6 100644
--- a/services/surfaceflinger/tests/unittests/Android.bp
+++ b/services/surfaceflinger/tests/unittests/Android.bp
@@ -41,6 +41,7 @@
         "DisplayIdentificationTest.cpp",
         "DisplayTransactionTest.cpp",
         "EventThreadTest.cpp",
+        "FrameTimelineTest.cpp",
         "HWComposerTest.cpp",
         "OneShotTimerTest.cpp",
         "LayerHistoryTest.cpp",
@@ -81,6 +82,7 @@
         "libgmock",
         "libcompositionengine",
         "libcompositionengine_mocks",
+        "libframetimeline",
         "libgui_mocks",
         "libperfetto_client_experimental",
         "librenderengine_mocks",
diff --git a/services/surfaceflinger/tests/unittests/FrameTimelineTest.cpp b/services/surfaceflinger/tests/unittests/FrameTimelineTest.cpp
new file mode 100644
index 0000000..85d2834
--- /dev/null
+++ b/services/surfaceflinger/tests/unittests/FrameTimelineTest.cpp
@@ -0,0 +1,220 @@
+/*
+ * Copyright 2020 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#undef LOG_TAG
+#define LOG_TAG "LibSurfaceFlingerUnittests"
+
+#include <FrameTimeline/FrameTimeline.h>
+#include <gtest/gtest.h>
+#include <log/log.h>
+#include <cinttypes>
+
+using namespace std::chrono_literals;
+
+namespace android::frametimeline {
+
+class FrameTimelineTest : public testing::Test {
+public:
+    FrameTimelineTest() {
+        const ::testing::TestInfo* const test_info =
+                ::testing::UnitTest::GetInstance()->current_test_info();
+        ALOGD("**** Setting up for %s.%s\n", test_info->test_case_name(), test_info->name());
+    }
+
+    ~FrameTimelineTest() {
+        const ::testing::TestInfo* const test_info =
+                ::testing::UnitTest::GetInstance()->current_test_info();
+        ALOGD("**** Tearing down after %s.%s\n", test_info->test_case_name(), test_info->name());
+    }
+
+    void SetUp() override {
+        mFrameTimeline = std::make_unique<impl::FrameTimeline>();
+        mTokenManager = &mFrameTimeline->mTokenManager;
+        maxDisplayFrames = mFrameTimeline->kMaxDisplayFrames;
+        maxTokenRetentionTime = mTokenManager->kMaxRetentionTime;
+    }
+
+    void flushTokens(nsecs_t flushTime) {
+        std::lock_guard<std::mutex> lock(mTokenManager->mMutex);
+        mTokenManager->flushTokens(flushTime);
+    }
+
+    SurfaceFrame& getSurfaceFrame(size_t displayFrameIdx, size_t surfaceFrameIdx) {
+        std::lock_guard<std::mutex> lock(mFrameTimeline->mMutex);
+        return *(mFrameTimeline->mDisplayFrames[displayFrameIdx]->surfaceFrames[surfaceFrameIdx]);
+    }
+
+    std::shared_ptr<impl::FrameTimeline::DisplayFrame> getDisplayFrame(size_t idx) {
+        std::lock_guard<std::mutex> lock(mFrameTimeline->mMutex);
+        return mFrameTimeline->mDisplayFrames[idx];
+    }
+
+    static bool compareTimelineItems(const TimelineItem& a, const TimelineItem& b) {
+        return a.startTime == b.startTime && a.endTime == b.endTime &&
+                a.presentTime == b.presentTime;
+    }
+
+    const std::unordered_map<int64_t, TimelineItem>& getPredictions() {
+        return mTokenManager->mPredictions;
+    }
+
+    std::unique_ptr<impl::FrameTimeline> mFrameTimeline;
+    impl::TokenManager* mTokenManager;
+    FenceToFenceTimeMap fenceFactory;
+    uint64_t maxDisplayFrames;
+    nsecs_t maxTokenRetentionTime;
+};
+
+TEST_F(FrameTimelineTest, tokenManagerRemovesStalePredictions) {
+    int64_t token1 = mTokenManager->generateTokenForPredictions({0, 0, 0});
+    EXPECT_EQ(getPredictions().size(), 1);
+    flushTokens(systemTime() + maxTokenRetentionTime);
+    int64_t token2 = mTokenManager->generateTokenForPredictions({10, 20, 30});
+    std::optional<TimelineItem> predictions = mTokenManager->getPredictionsForToken(token1);
+
+    // token1 should have expired
+    EXPECT_EQ(getPredictions().size(), 1);
+    EXPECT_EQ(predictions.has_value(), false);
+
+    predictions = mTokenManager->getPredictionsForToken(token2);
+    EXPECT_EQ(compareTimelineItems(*predictions, TimelineItem(10, 20, 30)), true);
+}
+
+TEST_F(FrameTimelineTest, createSurfaceFrameForToken_noToken) {
+    auto surfaceFrame = mFrameTimeline->createSurfaceFrameForToken("layer1", std::nullopt);
+    EXPECT_EQ(surfaceFrame->getPredictionState(), PredictionState::None);
+}
+
+TEST_F(FrameTimelineTest, createSurfaceFrameForToken_expiredToken) {
+    int64_t token1 = mTokenManager->generateTokenForPredictions({0, 0, 0});
+    flushTokens(systemTime() + maxTokenRetentionTime);
+    auto surfaceFrame = mFrameTimeline->createSurfaceFrameForToken("layer1", token1);
+
+    EXPECT_EQ(surfaceFrame->getPredictionState(), PredictionState::Expired);
+}
+
+TEST_F(FrameTimelineTest, createSurfaceFrameForToken_validToken) {
+    int64_t token1 = mTokenManager->generateTokenForPredictions({10, 20, 30});
+    auto surfaceFrame = mFrameTimeline->createSurfaceFrameForToken("layer1", token1);
+
+    EXPECT_EQ(surfaceFrame->getPredictionState(), PredictionState::Valid);
+    EXPECT_EQ(compareTimelineItems(surfaceFrame->getPredictions(), TimelineItem(10, 20, 30)), true);
+}
+
+TEST_F(FrameTimelineTest, presentFenceSignaled_droppedFramesNotUpdated) {
+    auto presentFence1 = fenceFactory.createFenceTimeForTest(Fence::NO_FENCE);
+    auto presentFence2 = fenceFactory.createFenceTimeForTest(Fence::NO_FENCE);
+
+    int64_t token1 = mTokenManager->generateTokenForPredictions({10, 20, 30});
+    int64_t token2 = mTokenManager->generateTokenForPredictions({40, 50, 60});
+    auto surfaceFrame1 = mFrameTimeline->createSurfaceFrameForToken("layer1", token1);
+
+    // Set up the display frame
+    mFrameTimeline->setSfWakeUp(token1, 20);
+    mFrameTimeline->addSurfaceFrame(std::move(surfaceFrame1), SurfaceFrame::PresentState::Dropped);
+    mFrameTimeline->setSfPresent(25, presentFence1);
+    presentFence1->signalForTest(30);
+
+    // Trigger a flush by calling setSfPresent for the next frame
+    mFrameTimeline->setSfWakeUp(token2, 50);
+    mFrameTimeline->setSfPresent(55, presentFence2);
+
+    auto& droppedSurfaceFrame = getSurfaceFrame(0, 0);
+    EXPECT_EQ(droppedSurfaceFrame.getPresentState(), SurfaceFrame::PresentState::Dropped);
+    EXPECT_EQ(droppedSurfaceFrame.getActuals().presentTime, 0);
+}
+
+TEST_F(FrameTimelineTest, presentFenceSignaled_presentedFramesUpdated) {
+    auto presentFence1 = fenceFactory.createFenceTimeForTest(Fence::NO_FENCE);
+    int64_t surfaceFrameToken1 = mTokenManager->generateTokenForPredictions({10, 20, 30});
+    int64_t surfaceFrameToken2 = mTokenManager->generateTokenForPredictions({40, 50, 60});
+    int64_t sfToken1 = mTokenManager->generateTokenForPredictions({22, 26, 30});
+    int64_t sfToken2 = mTokenManager->generateTokenForPredictions({52, 56, 60});
+    auto surfaceFrame1 = mFrameTimeline->createSurfaceFrameForToken("layer1", surfaceFrameToken1);
+    auto surfaceFrame2 = mFrameTimeline->createSurfaceFrameForToken("layer2", surfaceFrameToken1);
+    mFrameTimeline->setSfWakeUp(sfToken1, 22);
+    mFrameTimeline->addSurfaceFrame(std::move(surfaceFrame1),
+                                    SurfaceFrame::PresentState::Presented);
+    mFrameTimeline->addSurfaceFrame(std::move(surfaceFrame2),
+                                    SurfaceFrame::PresentState::Presented);
+    mFrameTimeline->setSfPresent(26, presentFence1);
+    auto displayFrame = getDisplayFrame(0);
+    SurfaceFrame& presentedSurfaceFrame1 = getSurfaceFrame(0, 0);
+    SurfaceFrame& presentedSurfaceFrame2 = getSurfaceFrame(0, 1);
+    presentFence1->signalForTest(42);
+
+    // Fences haven't been flushed yet, so it should be 0
+    EXPECT_EQ(displayFrame->surfaceFlingerActuals.presentTime, 0);
+    EXPECT_EQ(presentedSurfaceFrame1.getActuals().presentTime, 0);
+    EXPECT_EQ(presentedSurfaceFrame2.getActuals().presentTime, 0);
+
+    // Trigger a flush by finalizing the next DisplayFrame
+    auto presentFence2 = fenceFactory.createFenceTimeForTest(Fence::NO_FENCE);
+    auto surfaceFrame3 = mFrameTimeline->createSurfaceFrameForToken("layer1", surfaceFrameToken2);
+    mFrameTimeline->setSfWakeUp(sfToken2, 52);
+    mFrameTimeline->addSurfaceFrame(std::move(surfaceFrame3), SurfaceFrame::PresentState::Dropped);
+    mFrameTimeline->setSfPresent(56, presentFence2);
+    displayFrame = getDisplayFrame(0);
+
+    // Fences have flushed, so the present timestamps should be updated
+    EXPECT_EQ(displayFrame->surfaceFlingerActuals.presentTime, 42);
+    EXPECT_EQ(presentedSurfaceFrame1.getActuals().presentTime, 42);
+    EXPECT_EQ(presentedSurfaceFrame2.getActuals().presentTime, 42);
+}
+
+TEST_F(FrameTimelineTest, displayFramesSlidingWindowMovesAfterLimit) {
+    // Insert kMaxDisplayFrames' count of DisplayFrames to fill the deque
+    int frameTimeFactor = 0;
+    for (size_t i = 0; i < maxDisplayFrames; i++) {
+        auto presentFence = fenceFactory.createFenceTimeForTest(Fence::NO_FENCE);
+        int64_t surfaceFrameToken = mTokenManager->generateTokenForPredictions(
+                {10 + frameTimeFactor, 20 + frameTimeFactor, 30 + frameTimeFactor});
+        int64_t sfToken = mTokenManager->generateTokenForPredictions(
+                {22 + frameTimeFactor, 26 + frameTimeFactor, 30 + frameTimeFactor});
+        auto surfaceFrame = mFrameTimeline->createSurfaceFrameForToken("layer1", surfaceFrameToken);
+        mFrameTimeline->setSfWakeUp(sfToken, 22 + frameTimeFactor);
+        mFrameTimeline->addSurfaceFrame(std::move(surfaceFrame),
+                                        SurfaceFrame::PresentState::Presented);
+        mFrameTimeline->setSfPresent(27 + frameTimeFactor, presentFence);
+        presentFence->signalForTest(32 + frameTimeFactor);
+        frameTimeFactor += 30;
+    }
+    auto displayFrame0 = getDisplayFrame(0);
+
+    // The 0th Display Frame should have actuals 22, 27, 32
+    EXPECT_EQ(compareTimelineItems(displayFrame0->surfaceFlingerActuals, TimelineItem(22, 27, 32)),
+              true);
+
+    // Add one more display frame
+    auto presentFence = fenceFactory.createFenceTimeForTest(Fence::NO_FENCE);
+    int64_t surfaceFrameToken = mTokenManager->generateTokenForPredictions(
+            {10 + frameTimeFactor, 20 + frameTimeFactor, 30 + frameTimeFactor});
+    int64_t sfToken = mTokenManager->generateTokenForPredictions(
+            {22 + frameTimeFactor, 26 + frameTimeFactor, 30 + frameTimeFactor});
+    auto surfaceFrame = mFrameTimeline->createSurfaceFrameForToken("layer1", surfaceFrameToken);
+    mFrameTimeline->setSfWakeUp(sfToken, 22 + frameTimeFactor);
+    mFrameTimeline->addSurfaceFrame(std::move(surfaceFrame), SurfaceFrame::PresentState::Presented);
+    mFrameTimeline->setSfPresent(27 + frameTimeFactor, presentFence);
+    presentFence->signalForTest(32 + frameTimeFactor);
+    displayFrame0 = getDisplayFrame(0);
+
+    // The window should have slided by 1 now and the previous 0th display frame
+    // should have been removed from the deque
+    EXPECT_EQ(compareTimelineItems(displayFrame0->surfaceFlingerActuals, TimelineItem(52, 57, 62)),
+              true);
+}
+
+} // namespace android::frametimeline