From 425ec7a92099817e0791dc26afca0f005efa8763 Mon Sep 17 00:00:00 2001
From: Junyu Lai <junyulai@google.com>
Date: Tue, 25 Jul 2023 13:48:26 +0800
Subject: Read files in increasing timestamp order in FileRotator

The current design of the readMatching() function reads all
files that match a given prefix, but does not guarantee
the order in which they are read. This could cause
performance problems because the caller is optimized for
inserting files in ascending timestamp order but the files
are read in a reversed order.

This change sorts the list by the timestamp in the file name,
which is more natural since the files are written based on
timestamp. Benchmarking result shows that
testReadFromRecorder_manyUids improved from 1.5s to 1.0s
compares to the worst case.

Also, this is safe because all callers of the
readMatching() function only pass a list of less than 20 files.
None of these callers rely on the order in which the
files are read.

Test: atest ConnectivityBenchmarkTests FileRotatorTest
Bug: 269409485
Change-Id: I73f10890e8f454ee98e7d92fa754d1affe598df4
---
 .../com/android/internal/util/FileRotator.java     | 24 +++++++++++++++-------
 .../com/android/internal/util/FileRotatorTest.java | 21 ++++++++++---------
 2 files changed, 28 insertions(+), 17 deletions(-)

diff --git a/core/java/com/android/internal/util/FileRotator.java b/core/java/com/android/internal/util/FileRotator.java
index 5bc48c5172f0..c9d9926ba75a 100644
--- a/core/java/com/android/internal/util/FileRotator.java
+++ b/core/java/com/android/internal/util/FileRotator.java
@@ -19,6 +19,9 @@ package com.android.internal.util;
 import android.annotation.NonNull;
 import android.os.FileUtils;
 import android.util.Log;
+import android.util.Pair;
+
+import libcore.io.IoUtils;
 
 import java.io.BufferedInputStream;
 import java.io.BufferedOutputStream;
@@ -28,12 +31,12 @@ import java.io.FileOutputStream;
 import java.io.IOException;
 import java.io.InputStream;
 import java.io.OutputStream;
+import java.util.Comparator;
 import java.util.Objects;
+import java.util.TreeSet;
 import java.util.zip.ZipEntry;
 import java.util.zip.ZipOutputStream;
 
-import libcore.io.IoUtils;
-
 /**
  * Utility that rotates files over time, similar to {@code logrotate}. There is
  * a single "active" file, which is periodically rotated into historical files,
@@ -302,17 +305,24 @@ public class FileRotator {
     public void readMatching(Reader reader, long matchStartMillis, long matchEndMillis)
             throws IOException {
         final FileInfo info = new FileInfo(mPrefix);
+        final TreeSet<Pair<Long, String>> readSet = new TreeSet<>(
+                Comparator.comparingLong(o -> o.first));
         for (String name : mBasePath.list()) {
             if (!info.parse(name)) continue;
 
-            // read file when it overlaps
+            // Add file to set when it overlaps.
             if (info.startMillis <= matchEndMillis && matchStartMillis <= info.endMillis) {
-                if (LOGD) Log.d(TAG, "reading matching " + name);
-
-                final File file = new File(mBasePath, name);
-                readFile(file, reader);
+                readSet.add(new Pair(info.startMillis, name));
             }
         }
+
+        // Read files in ascending order of start timestamp.
+        for (Pair<Long, String> pair : readSet) {
+            final String name = pair.second;
+            if (LOGD) Log.d(TAG, "reading matching " + name);
+            final File file = new File(mBasePath, name);
+            readFile(file, reader);
+        }
     }
 
     /**
diff --git a/core/tests/utiltests/src/com/android/internal/util/FileRotatorTest.java b/core/tests/utiltests/src/com/android/internal/util/FileRotatorTest.java
index 952721320c90..73e47e1635b4 100644
--- a/core/tests/utiltests/src/com/android/internal/util/FileRotatorTest.java
+++ b/core/tests/utiltests/src/com/android/internal/util/FileRotatorTest.java
@@ -366,6 +366,16 @@ public class FileRotatorTest extends AndroidTestCase {
         assertReadAll(rotate, "bar");
     }
 
+    public void testReadSorted() throws Exception {
+        write("rotator.1024-2048", "2");
+        write("rotator.2048-4096", "3");
+        write("rotator.512-1024", "1");
+
+        final FileRotator rotate = new FileRotator(
+                mBasePath, PREFIX, SECOND_IN_MILLIS, SECOND_IN_MILLIS);
+        assertReadAll(rotate, "1", "2", "3");
+    }
+
     public void testFileSystemInaccessible() throws Exception {
         File inaccessibleDir = null;
         String dirPath = getContext().getFilesDir() + File.separator + "inaccessible";
@@ -422,16 +432,7 @@ public class FileRotatorTest extends AndroidTestCase {
         }
 
         public void assertRead(String... expected) {
-            assertEquals(expected.length, mActual.size());
-
-            final ArrayList<String> actualCopy = new ArrayList<String>(mActual);
-            for (String value : expected) {
-                if (!actualCopy.remove(value)) {
-                    final String expectedString = Arrays.toString(expected);
-                    final String actualString = Arrays.toString(mActual.toArray());
-                    fail("expected: " + expectedString + " but was: " + actualString);
-                }
-            }
+            assertEquals(Arrays.asList(expected), mActual);
         }
     }
 }
-- 
cgit v1.2.3-59-g8ed1b