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