Apply go/hc-page-token in the implementation

* Return full page token from RecordHelper and surface it up
  - Chain: RecordHelper -> TransactionManager ->
    HealthConnectServiceImpl
  - RecordHelper is where we calculate offset
  - Wrap everything is easier than bubbling everything up separately

* Add pageToken to ReadTransactionRequest
  - This allows the TransactionManager to access page token, and pass
    it on to RecordHelper

* BackupRestore is also changed, because there are two copies of the
  same code (in TransactionManager and BackupRestore)

* Extend test coverge
  - Unit test: RecordHelperTest
  - Integration test (cts): HealthConnectManagerTest

Test: atest HealthFitnessUnitTests
Test: atest HealthConnectManagerTest
Bug: 296846629
Change-Id: I48b1b58da8d9b94e57e6f492f8fa79cb9d7c9bab
diff --git a/service/java/com/android/server/healthconnect/HealthConnectServiceImpl.java b/service/java/com/android/server/healthconnect/HealthConnectServiceImpl.java
index 9b6b60c..3a8d028 100644
--- a/service/java/com/android/server/healthconnect/HealthConnectServiceImpl.java
+++ b/service/java/com/android/server/healthconnect/HealthConnectServiceImpl.java
@@ -144,8 +144,6 @@
 import com.android.server.healthconnect.storage.request.DeleteTransactionRequest;
 import com.android.server.healthconnect.storage.request.ReadTransactionRequest;
 import com.android.server.healthconnect.storage.request.UpsertTransactionRequest;
-import com.android.server.healthconnect.storage.utils.PageTokenUtil;
-import com.android.server.healthconnect.storage.utils.PageTokenWrapper;
 import com.android.server.healthconnect.storage.utils.RecordHelperProvider;
 
 import java.io.IOException;
@@ -643,29 +641,18 @@
                             }
 
                             List<RecordInternal<?>> records;
-                            long pageToken = DEFAULT_LONG;
+                            long pageToken;
                             if (request.getRecordIdFiltersParcel() != null) {
                                 records =
                                         mTransactionManager.readRecordsByIds(
                                                 readTransactionRequest);
+                                pageToken = DEFAULT_LONG;
                             } else {
                                 Pair<List<RecordInternal<?>>, Long> readRecordsResponse =
-                                        mTransactionManager.readRecordsAndNextRecordStartTime(
+                                        mTransactionManager.readRecordsAndPageToken(
                                                 readTransactionRequest);
                                 records = readRecordsResponse.first;
-                                long timestamp = readRecordsResponse.second;
-                                if (timestamp != DEFAULT_LONG) {
-                                    boolean isAscending =
-                                            PageTokenUtil.decode(
-                                                            request.getPageToken(),
-                                                            request.isAscending())
-                                                    .isAscending();
-
-                                    PageTokenWrapper wrapper =
-                                            PageTokenWrapper.of(
-                                                    isAscending, timestamp, /* offset= */ 0);
-                                    pageToken = PageTokenUtil.encode(wrapper);
-                                }
+                                pageToken = readRecordsResponse.second;
                             }
                             logger.setNumberOfRecords(records.size());
 
diff --git a/service/java/com/android/server/healthconnect/backuprestore/BackupRestore.java b/service/java/com/android/server/healthconnect/backuprestore/BackupRestore.java
index 9bcda00..f5cb422 100644
--- a/service/java/com/android/server/healthconnect/backuprestore/BackupRestore.java
+++ b/service/java/com/android/server/healthconnect/backuprestore/BackupRestore.java
@@ -1046,10 +1046,7 @@
             TransactionManager.getInitialisedInstance()
                     .insertAll(upsertTransactionRequest.getUpsertRequests());
 
-            token = DEFAULT_LONG;
-            if (recordsToMergeAndToken.second != DEFAULT_LONG) {
-                token = recordsToMergeAndToken.second * 2;
-            }
+            token = recordsToMergeAndToken.second;
         } while (token != DEFAULT_LONG);
 
         // Once all the records of this type have been merged we can delete the table.
@@ -1091,22 +1088,18 @@
                         extraReadPermsMapping);
 
         List<RecordInternal<?>> recordInternalList;
-        long token = DEFAULT_LONG;
+        long token;
         ReadTableRequest readTableRequest = readTransactionRequest.getReadRequests().get(0);
         try (Cursor cursor = read(readTableRequest)) {
-            recordInternalList =
-                    recordHelper.getInternalRecordsPage(
+            Pair<List<RecordInternal<?>>, Long> readResult =
+                    recordHelper.getNextInternalRecordsPageAndToken(
                             cursor,
                             readTransactionRequest.getPageSize().orElse(DEFAULT_PAGE_SIZE),
+                            requireNonNull(readTransactionRequest.getPageToken()),
                             mStagedPackageNamesByAppIds);
-            String startTimeColumnName = recordHelper.getStartTimeColumnName();
-
+            recordInternalList = readResult.first;
+            token = readResult.second;
             populateInternalRecordsWithExtraData(recordInternalList, readTableRequest);
-
-            // Get the token for the next read request.
-            if (cursor.moveToNext()) {
-                token = getCursorLong(cursor, startTimeColumnName);
-            }
         }
         return Pair.create(recordInternalList, token);
     }
diff --git a/service/java/com/android/server/healthconnect/storage/TransactionManager.java b/service/java/com/android/server/healthconnect/storage/TransactionManager.java
index b3a8f84..d111eb4 100644
--- a/service/java/com/android/server/healthconnect/storage/TransactionManager.java
+++ b/service/java/com/android/server/healthconnect/storage/TransactionManager.java
@@ -24,7 +24,6 @@
 
 import static com.android.server.healthconnect.storage.datatypehelpers.RecordHelper.APP_INFO_ID_COLUMN_NAME;
 import static com.android.server.healthconnect.storage.datatypehelpers.RecordHelper.PRIMARY_COLUMN_NAME;
-import static com.android.server.healthconnect.storage.utils.StorageUtils.getCursorLong;
 
 import static com.google.common.collect.Iterables.getOnlyElement;
 
@@ -279,37 +278,37 @@
 
     /**
      * Reads the records {@link RecordInternal} stored in the HealthConnect database and returns the
-     * start time of the next record as part of next page token.
+     * next page token.
      *
      * @param request a read request. Only one {@link ReadTableRequest} is expected in the {@link
      *     ReadTransactionRequest request}.
-     * @return Pair containing records list read {@link RecordInternal} from the table and a
-     *     timestamp for pagination
+     * @return Pair containing records list read {@link RecordInternal} from the table and a page
+     *     token for pagination.
      */
-    public Pair<List<RecordInternal<?>>, Long> readRecordsAndNextRecordStartTime(
+    public Pair<List<RecordInternal<?>>, Long> readRecordsAndPageToken(
             @NonNull ReadTransactionRequest request) throws SQLiteException {
         ReadTableRequest readTableRequest = getOnlyElement(request.getReadRequests());
         List<RecordInternal<?>> recordInternalList;
-        long timestamp = DEFAULT_LONG;
         RecordHelper<?> helper = readTableRequest.getRecordHelper();
         requireNonNull(helper);
         if (!helper.isRecordOperationsEnabled()) {
             recordInternalList = new ArrayList<>(0);
-            return Pair.create(recordInternalList, timestamp);
+            return Pair.create(recordInternalList, DEFAULT_LONG);
         }
 
+        long pageToken;
         try (Cursor cursor = read(readTableRequest)) {
-            recordInternalList =
-                    helper.getInternalRecordsPage(
-                            cursor, request.getPageSize().orElse(DEFAULT_PAGE_SIZE));
-            String startTimeColumnName = helper.getStartTimeColumnName();
-
+            Pair<List<RecordInternal<?>>, Long> readResult =
+                    helper.getNextInternalRecordsPageAndToken(
+                            cursor,
+                            request.getPageSize().orElse(DEFAULT_PAGE_SIZE),
+                            // pageToken is never null for read by filter requests
+                            requireNonNull(request.getPageToken()));
+            recordInternalList = readResult.first;
+            pageToken = readResult.second;
             populateInternalRecordsWithExtraData(recordInternalList, readTableRequest);
-            if (cursor.moveToNext()) {
-                timestamp = getCursorLong(cursor, startTimeColumnName);
-            }
         }
-        return Pair.create(recordInternalList, timestamp);
+        return Pair.create(recordInternalList, pageToken);
     }
 
     /**
diff --git a/service/java/com/android/server/healthconnect/storage/datatypehelpers/RecordHelper.java b/service/java/com/android/server/healthconnect/storage/datatypehelpers/RecordHelper.java
index 38937ed..e0ec59b 100644
--- a/service/java/com/android/server/healthconnect/storage/datatypehelpers/RecordHelper.java
+++ b/service/java/com/android/server/healthconnect/storage/datatypehelpers/RecordHelper.java
@@ -417,89 +417,89 @@
      * Returns a list of Internal records from the cursor up to the requested size, with pagination
      * handled.
      *
-     * @see #getInternalRecordsPage(Cursor, int, Map)
+     * @see #getNextInternalRecordsPageAndToken(Cursor, int, PageTokenWrapper, Map)
      */
-    public List<RecordInternal<?>> getInternalRecordsPage(Cursor cursor, int requestSize) {
-        return getInternalRecordsPage(cursor, requestSize, /* packageNamesByAppIds= */ null);
+    public Pair<List<RecordInternal<?>>, Long> getNextInternalRecordsPageAndToken(
+            Cursor cursor, int requestSize, PageTokenWrapper pageToken) {
+        return getNextInternalRecordsPageAndToken(
+                cursor, requestSize, pageToken, /* packageNamesByAppIds= */ null);
     }
 
     /**
      * Returns List of Internal records from the cursor up to the requested size, with pagination
      * handled.
+     *
+     * <p>Note that the cursor limit is set to {@code requestSize + offset + 1},
+     * <li>+ offset: {@code offset} records has already been returned in previous page(s). See
+     *     go/hc-page-token for details.
+     * <li>+ 1: if number of records queried is more than pageSize we know there are more records
+     *     available to return for the next read.
+     *
+     *     <p>Note that the cursor may contain more records that we need to return. Cursor limit set
+     *     to sum of the following:
+     * <li>offset: {@code offset} records have already been returned in previous page(s), and should
+     *     be skipped from this current page. In rare occasions (e.g. records deleted in between two
+     *     reads), there are less than {@code offset} records, an empty list is returned, with no
+     *     page token.
+     * <li>requestSize: {@code requestSize} records to return in the response.
+     * <li>one extra record: If there are more records than (offset+requestSize), a page token is
+     *     returned for the next page. If not, then a default token is returned.
+     *
+     * @see #getLimitSize(ReadRecordsRequestParcel)
      */
-    public List<RecordInternal<?>> getInternalRecordsPage(
-            Cursor cursor, int requestSize, @Nullable Map<Long, String> packageNamesByAppIds) {
-        Trace.traceBegin(TRACE_TAG_RECORD_HELPER, TAG_RECORD_HELPER.concat("GetInternalRecords"));
-        List<RecordInternal<?>> recordInternalList = new ArrayList<>();
+    public Pair<List<RecordInternal<?>>, Long> getNextInternalRecordsPageAndToken(
+            Cursor cursor,
+            int requestSize,
+            PageTokenWrapper prevPageToken,
+            @Nullable Map<Long, String> packageNamesByAppIds) {
+        Trace.traceBegin(
+                TRACE_TAG_RECORD_HELPER,
+                TAG_RECORD_HELPER.concat("getNextInternalRecordsPageAndToken"));
 
-        int count = 0;
+        // Ignore <offset> records of the same start time, because it was returned in previous
+        // page(s).
+        // If the offset is greater than number of records in the cursor, it'll move to the last
+        // index and will not enter the while loop below.
         long prevStartTime;
         long currentStartTime = DEFAULT_LONG;
-        int tempCount = 0;
-        List<RecordInternal<?>> tempList = new ArrayList<>();
-        while (cursor.moveToNext()) {
-            T record = getRecord(cursor, packageNamesByAppIds);
-
+        for (int i = 0; i < prevPageToken.offset(); i++) {
+            if (!cursor.moveToNext()) {
+                break;
+            }
             prevStartTime = currentStartTime;
             currentStartTime = getCursorLong(cursor, getStartTimeColumnName());
-            if (prevStartTime == DEFAULT_LONG || prevStartTime == currentStartTime) {
-                // Fetch and add records with same startTime to tempList
-                tempList.add(record);
-                tempCount++;
-            } else {
-                if (count == 0) {
-                    // items in tempList having startTime same as the first record from cursor
-                    // is added to final list.
-                    // This makes sure that we return at least 1 record if the count of
-                    // records with startTime same as second record exceeds requestSize.
-                    recordInternalList.addAll(tempList);
-                    count = tempCount;
-                    tempList.clear();
-                    tempCount = 0;
-                    if (count >= requestSize) {
-                        // startTime of current record should be fetched for pageToken
-                        cursor.moveToPrevious();
-                        break;
-                    }
-                    tempList.add(record);
-                    tempCount = 1;
-                } else if (tempCount + count <= requestSize) {
-                    // Makes sure after adding records in tempList with same starTime
-                    // the count does not exceed requestSize
-                    recordInternalList.addAll(tempList);
-                    count += tempCount;
-                    tempList.clear();
-                    tempCount = 0;
-                    if (count >= requestSize) {
-                        // After adding records if count is equal to requestSize then startTime
-                        // of current fetched record should be the next page token.
-                        cursor.moveToPrevious();
-                        break;
-                    }
-                    tempList.add(record);
-                    tempCount = 1;
-                } else {
-                    // If adding records in tempList makes count > requestSize, then ignore temp
-                    // list and startTime of records in temp list should be the next page token.
-                    tempList.clear();
-                    int lastposition = cursor.getPosition();
-                    cursor.moveToPosition(lastposition - 2);
-                    break;
-                }
+            if (prevStartTime != DEFAULT_LONG && prevStartTime != currentStartTime) {
+                // The current record should not be skipped
+                cursor.moveToPrevious();
+                break;
             }
         }
-        if (!tempList.isEmpty()) {
-            if (tempCount + count <= requestSize) {
-                // If reached end of cursor while fetching records then add it to final list
-                recordInternalList.addAll(tempList);
+
+        currentStartTime = DEFAULT_LONG;
+        int offset = 0;
+        List<RecordInternal<?>> recordInternalList = new ArrayList<>();
+        long nextToken = DEFAULT_LONG;
+        while (cursor.moveToNext()) {
+            prevStartTime = currentStartTime;
+            currentStartTime = getCursorLong(cursor, getStartTimeColumnName());
+            if (currentStartTime != prevStartTime) {
+                offset = 0;
+            }
+
+            if (recordInternalList.size() >= requestSize) {
+                PageTokenWrapper nextPageToken =
+                        PageTokenWrapper.of(prevPageToken.isAscending(), currentStartTime, offset);
+                nextToken = PageTokenUtil.encode(nextPageToken);
+                break;
             } else {
-                // If reached end of cursor while fetching and adding it will exceed requestSize
-                // then ignore them,startTime of the last record will be pageToken for next read.
-                cursor.moveToPosition(cursor.getCount() - 2);
+                T record = getRecord(cursor, packageNamesByAppIds);
+                recordInternalList.add(record);
+                offset++;
             }
         }
+
         Trace.traceEnd(TRACE_TAG_RECORD_HELPER);
-        return recordInternalList;
+        return Pair.create(recordInternalList, nextToken);
     }
 
     @SuppressWarnings("unchecked") // uncheck cast to T
@@ -642,10 +642,14 @@
 
     private static int getLimitSize(ReadRecordsRequestParcel request) {
         // Querying extra records on top of page size
+        // + pageOffset: <pageOffset> records has already been returned in previous page(s). See
+        //               go/hc-page-token for details.
         // + 1: if number of records queried is more than pageSize we know there are more records
         //      available to return for the next read.
         if (request.getRecordIdFiltersParcel() == null) {
-            return request.getPageSize() + 1;
+            int pageOffset =
+                    PageTokenUtil.decode(request.getPageToken(), request.isAscending()).offset();
+            return request.getPageSize() + pageOffset + 1;
         } else {
             return MAXIMUM_PAGE_SIZE;
         }
@@ -732,7 +736,8 @@
         PageTokenWrapper pageToken =
                 PageTokenUtil.decode(request.getPageToken(), request.isAscending());
         return new OrderByClause()
-                .addOrderByClause(getStartTimeColumnName(), pageToken.isAscending());
+                .addOrderByClause(getStartTimeColumnName(), pageToken.isAscending())
+                .addOrderByClause(PRIMARY_COLUMN_NAME, /* isAscending= */ true);
     }
 
     @NonNull
diff --git a/service/java/com/android/server/healthconnect/storage/request/ReadTransactionRequest.java b/service/java/com/android/server/healthconnect/storage/request/ReadTransactionRequest.java
index de54a1c..f25fe2a 100644
--- a/service/java/com/android/server/healthconnect/storage/request/ReadTransactionRequest.java
+++ b/service/java/com/android/server/healthconnect/storage/request/ReadTransactionRequest.java
@@ -19,9 +19,12 @@
 import static android.health.connect.Constants.DEFAULT_INT;
 
 import android.annotation.NonNull;
+import android.annotation.Nullable;
 import android.health.connect.aidl.ReadRecordsRequestParcel;
 
 import com.android.server.healthconnect.storage.datatypehelpers.RecordHelper;
+import com.android.server.healthconnect.storage.utils.PageTokenUtil;
+import com.android.server.healthconnect.storage.utils.PageTokenWrapper;
 import com.android.server.healthconnect.storage.utils.RecordHelperProvider;
 
 import java.util.ArrayList;
@@ -42,6 +45,8 @@
 public class ReadTransactionRequest {
     public static final String TYPE_NOT_PRESENT_PACKAGE_NAME = "package_name";
     private final List<ReadTableRequest> mReadTableRequests;
+    @Nullable // page token is null for read by id requests
+    private final PageTokenWrapper mPageToken;
     private final int mPageSize;
 
     public ReadTransactionRequest(
@@ -60,6 +65,7 @@
                                 enforceSelfRead,
                                 startDateAccess,
                                 extraPermsState));
+        mPageToken = PageTokenUtil.decode(request.getPageToken(), request.isAscending());
         mPageSize = request.getPageSize();
     }
 
@@ -80,6 +86,7 @@
                                                 startDateAccess,
                                                 extraPermsState)));
         mPageSize = DEFAULT_INT;
+        mPageToken = null;
     }
 
     @NonNull
@@ -87,6 +94,11 @@
         return mReadTableRequests;
     }
 
+    @Nullable
+    public PageTokenWrapper getPageToken() {
+        return mPageToken;
+    }
+
     /**
      * Returns optional of page size in the {@link android.health.connect.ReadRecordsRequest}
      * refined by this {@link ReadTransactionRequest}.
diff --git a/tests/cts/src/android/healthconnect/cts/HealthConnectManagerTest.java b/tests/cts/src/android/healthconnect/cts/HealthConnectManagerTest.java
index 26d0833..a0fda91 100644
--- a/tests/cts/src/android/healthconnect/cts/HealthConnectManagerTest.java
+++ b/tests/cts/src/android/healthconnect/cts/HealthConnectManagerTest.java
@@ -49,7 +49,10 @@
 import android.health.connect.HealthConnectManager;
 import android.health.connect.HealthPermissions;
 import android.health.connect.LocalTimeRangeFilter;
+import android.health.connect.ReadRecordsRequest;
+import android.health.connect.ReadRecordsRequestUsingFilters;
 import android.health.connect.ReadRecordsRequestUsingIds;
+import android.health.connect.ReadRecordsResponse;
 import android.health.connect.RecordTypeInfoResponse;
 import android.health.connect.TimeInstantRangeFilter;
 import android.health.connect.changelog.ChangeLogTokenRequest;
@@ -163,7 +166,7 @@
     }
 
     @Test
-    public void testIsHealthPermission_forHealthPermission_returnsTrue() throws Exception {
+    public void testIsHealthPermission_forHealthPermission_returnsTrue() {
         Context context = ApplicationProvider.getApplicationContext();
         assertThat(isHealthPermission(context, HealthPermissions.READ_ACTIVE_CALORIES_BURNED))
                 .isTrue();
@@ -172,7 +175,7 @@
     }
 
     @Test
-    public void testIsHealthPermission_forNonHealthGroupPermission_returnsFalse() throws Exception {
+    public void testIsHealthPermission_forNonHealthGroupPermission_returnsFalse() {
         Context context = ApplicationProvider.getApplicationContext();
         assertThat(isHealthPermission(context, HealthPermissions.MANAGE_HEALTH_PERMISSIONS))
                 .isFalse();
@@ -195,12 +198,7 @@
      * <p>Insert a sample record of each dataType, update them and check by reading them.
      */
     @Test
-    public void testUpdateRecords_validInput_dataBaseUpdatedSuccessfully()
-            throws InterruptedException,
-                    InvocationTargetException,
-                    InstantiationException,
-                    IllegalAccessException,
-                    NoSuchMethodException {
+    public void testUpdateRecords_validInput_dataBaseUpdatedSuccessfully() throws Exception {
 
         Context context = ApplicationProvider.getApplicationContext();
         CountDownLatch latch = new CountDownLatch(1);
@@ -265,12 +263,7 @@
      * valid inputs) should not be modified either.
      */
     @Test
-    public void testUpdateRecords_invalidInputRecords_noChangeInDataBase()
-            throws InterruptedException,
-                    InvocationTargetException,
-                    InstantiationException,
-                    IllegalAccessException,
-                    NoSuchMethodException {
+    public void testUpdateRecords_invalidInputRecords_noChangeInDataBase() throws Exception {
 
         Context context = ApplicationProvider.getApplicationContext();
         CountDownLatch latch = new CountDownLatch(1);
@@ -341,11 +334,7 @@
      */
     @Test
     public void testUpdateRecords_recordWithInvalidPackageName_noChangeInDataBase()
-            throws InterruptedException,
-                    InvocationTargetException,
-                    InstantiationException,
-                    IllegalAccessException,
-                    NoSuchMethodException {
+            throws Exception {
 
         Context context = ApplicationProvider.getApplicationContext();
         CountDownLatch latch = new CountDownLatch(1);
@@ -660,6 +649,64 @@
     }
 
     @Test
+    public void testReadRecords_multiplePagesSameStartTimeRecords_paginatedCorrectly()
+            throws Exception {
+        Instant startTime = Instant.now().minus(1, ChronoUnit.DAYS);
+
+        insertRecords(
+                List.of(
+                        getStepsRecord(
+                                "client.id1",
+                                "package.name",
+                                /* count= */ 100,
+                                startTime,
+                                startTime.plusSeconds(500)),
+                        getStepsRecord(
+                                "client.id2",
+                                "package.name",
+                                /* count= */ 100,
+                                startTime,
+                                startTime.plusSeconds(200)),
+                        getStepsRecord(
+                                "client.id3",
+                                "package.name",
+                                /* count= */ 100,
+                                startTime,
+                                startTime.plusSeconds(400)),
+                        getStepsRecord(
+                                "client.id4",
+                                "package.name",
+                                /* count= */ 100,
+                                startTime,
+                                startTime.plusSeconds(300))));
+
+        ReadRecordsRequest<StepsRecord> request1 =
+                new ReadRecordsRequestUsingFilters.Builder<>(StepsRecord.class)
+                        .setPageSize(2)
+                        .setAscending(false)
+                        .build();
+        ReadRecordsResponse<StepsRecord> result1 = TestUtils.readRecordsWithPagination(request1);
+        assertThat(result1.getRecords()).hasSize(2);
+        assertThat(result1.getRecords().get(0).getMetadata().getClientRecordId())
+                .isEqualTo("client.id1");
+        assertThat(result1.getRecords().get(1).getMetadata().getClientRecordId())
+                .isEqualTo("client.id2");
+
+        ReadRecordsRequest<StepsRecord> request2 =
+                new ReadRecordsRequestUsingFilters.Builder<>(StepsRecord.class)
+                        .setPageSize(2)
+                        .setPageToken(result1.getNextPageToken())
+                        .build();
+        ReadRecordsResponse<StepsRecord> result2 = TestUtils.readRecordsWithPagination(request2);
+        assertThat(result2.getRecords()).hasSize(2);
+        assertThat(result2.getRecords().get(0).getMetadata().getClientRecordId())
+                .isEqualTo("client.id3");
+        assertThat(result2.getRecords().get(1).getMetadata().getClientRecordId())
+                .isEqualTo("client.id4");
+        assertThat(result2.getNextPageToken()).isEqualTo(-1);
+    }
+
+    @Test
     public void testAutoDeleteApis() throws InterruptedException {
         UiAutomation uiAutomation = InstrumentationRegistry.getInstrumentation().getUiAutomation();
 
@@ -1467,7 +1514,8 @@
                         @Override
                         public void onError(@NonNull HealthConnectException e) {
                             returnedException.set(e);
-                            latch.countDown();}
+                            latch.countDown();
+                        }
                     });
         } catch (Exception e) {
             throw new RuntimeException(e);
diff --git a/tests/unittests/src/com/android/server/healthconnect/storage/TransactionManagerExerciseRoutesTest.java b/tests/unittests/src/com/android/server/healthconnect/storage/TransactionManagerExerciseRoutesTest.java
index 377b301..0173fca 100644
--- a/tests/unittests/src/com/android/server/healthconnect/storage/TransactionManagerExerciseRoutesTest.java
+++ b/tests/unittests/src/com/android/server/healthconnect/storage/TransactionManagerExerciseRoutesTest.java
@@ -196,7 +196,7 @@
     }
 
     @Test
-    public void readRecordsAndNextRecordStartTime_byFilters_doesNotReturnRoutesOfOtherApps() {
+    public void readRecordsAndPageToken_byFilters_doesNotReturnRoutesOfOtherApps() {
         ExerciseSessionRecordInternal fooSession =
                 createExerciseSessionRecordWithRoute(Instant.ofEpochSecond(10000));
         ExerciseSessionRecordInternal barSession =
@@ -222,7 +222,7 @@
                         NO_EXTRA_PERMS);
 
         List<RecordInternal<?>> returnedRecords =
-                mTransactionManager.readRecordsAndNextRecordStartTime(request).first;
+                mTransactionManager.readRecordsAndPageToken(request).first;
 
         Map<String, ExerciseSessionRecordInternal> idToSessionMap =
                 returnedRecords.stream()
@@ -240,7 +240,7 @@
     }
 
     @Test
-    public void readRecordsAndNextRecordStartTime_byFilters_unknownApp_doesNotReturnRoute() {
+    public void readRecordsAndPageToken_byFilters_unknownApp_doesNotReturnRoute() {
         ExerciseSessionRecordInternal session =
                 createExerciseSessionRecordWithRoute(Instant.ofEpochSecond(12000));
         mTransactionTestUtils.insertRecords(TEST_PACKAGE_NAME, session);
@@ -260,7 +260,7 @@
                         NO_EXTRA_PERMS);
 
         List<RecordInternal<?>> returnedRecords =
-                mTransactionManager.readRecordsAndNextRecordStartTime(request).first;
+                mTransactionManager.readRecordsAndPageToken(request).first;
 
         assertThat(returnedRecords).hasSize(1);
         ExerciseSessionRecordInternal returnedRecord =
@@ -270,7 +270,7 @@
     }
 
     @Test
-    public void readRecordsAndNextRecordStartTime_byFilters_nullPackageName_doesNotReturnRoute() {
+    public void readRecordsAndPageToken_byFilters_nullPackageName_doesNotReturnRoute() {
         ExerciseSessionRecordInternal session =
                 createExerciseSessionRecordWithRoute(Instant.ofEpochSecond(12000));
         mTransactionTestUtils.insertRecords(TEST_PACKAGE_NAME, session);
@@ -290,7 +290,7 @@
                         NO_EXTRA_PERMS);
 
         List<RecordInternal<?>> returnedRecords =
-                mTransactionManager.readRecordsAndNextRecordStartTime(request).first;
+                mTransactionManager.readRecordsAndPageToken(request).first;
 
         assertThat(returnedRecords).hasSize(1);
         ExerciseSessionRecordInternal returnedRecord =
@@ -300,7 +300,7 @@
     }
 
     @Test
-    public void readRecordsAndNextRecordStartTime_byFilters_withReadRoutePermission_returnsRoute() {
+    public void readRecordsAndPageToken_byFilters_withReadRoutePermission_returnsRoute() {
         ExerciseSessionRecordInternal session =
                 createExerciseSessionRecordWithRoute(Instant.ofEpochSecond(12000));
         mTransactionTestUtils.insertRecords(TEST_PACKAGE_NAME, session);
@@ -320,7 +320,7 @@
                         Map.of(HealthPermissions.READ_EXERCISE_ROUTE, true));
 
         List<RecordInternal<?>> returnedRecords =
-                mTransactionManager.readRecordsAndNextRecordStartTime(request).first;
+                mTransactionManager.readRecordsAndPageToken(request).first;
 
         assertThat(returnedRecords).hasSize(1);
         ExerciseSessionRecordInternal returnedRecord =
@@ -330,7 +330,7 @@
     }
 
     @Test
-    public void readRecordsAndNextRecordStartTime_byIds_doesNotReturnRoutesOfOtherApps() {
+    public void readRecordsAndPageToken_byIds_doesNotReturnRoutesOfOtherApps() {
         ExerciseSessionRecordInternal fooSession =
                 createExerciseSessionRecordWithRoute(Instant.ofEpochSecond(10000));
         ExerciseSessionRecordInternal barSession =
@@ -354,7 +354,7 @@
                         NO_EXTRA_PERMS);
 
         List<RecordInternal<?>> returnedRecords =
-                mTransactionManager.readRecordsAndNextRecordStartTime(request).first;
+                mTransactionManager.readRecordsAndPageToken(request).first;
 
         Map<String, ExerciseSessionRecordInternal> idToSessionMap =
                 returnedRecords.stream()
@@ -371,7 +371,7 @@
     }
 
     @Test
-    public void readRecordsAndNextRecordStartTime_byIds_unknownApp_doesNotReturnRoute() {
+    public void readRecordsAndPageToken_byIds_unknownApp_doesNotReturnRoute() {
         ExerciseSessionRecordInternal session =
                 createExerciseSessionRecordWithRoute(Instant.ofEpochSecond(12000));
         String uuid = mTransactionTestUtils.insertRecords(TEST_PACKAGE_NAME, session).get(0);
@@ -387,7 +387,7 @@
                         NO_EXTRA_PERMS);
 
         List<RecordInternal<?>> returnedRecords =
-                mTransactionManager.readRecordsAndNextRecordStartTime(request).first;
+                mTransactionManager.readRecordsAndPageToken(request).first;
 
         assertThat(returnedRecords).hasSize(1);
         ExerciseSessionRecordInternal returnedRecord =
@@ -397,7 +397,7 @@
     }
 
     @Test
-    public void readRecordsAndNextRecordStartTime_byIds_nullPackageName_doesNotReturnRoute() {
+    public void readRecordsAndPageToken_byIds_nullPackageName_doesNotReturnRoute() {
         ExerciseSessionRecordInternal session =
                 createExerciseSessionRecordWithRoute(Instant.ofEpochSecond(12000));
         String uuid = mTransactionTestUtils.insertRecords(TEST_PACKAGE_NAME, session).get(0);
@@ -413,7 +413,7 @@
                         NO_EXTRA_PERMS);
 
         List<RecordInternal<?>> returnedRecords =
-                mTransactionManager.readRecordsAndNextRecordStartTime(request).first;
+                mTransactionManager.readRecordsAndPageToken(request).first;
 
         assertThat(returnedRecords).hasSize(1);
         ExerciseSessionRecordInternal returnedRecord =
@@ -423,7 +423,7 @@
     }
 
     @Test
-    public void readRecordsAndNextRecordStartTime_byIds_withReadRoutePermission_returnsRoute() {
+    public void readRecordsAndPageToken_byIds_withReadRoutePermission_returnsRoute() {
         ExerciseSessionRecordInternal session =
                 createExerciseSessionRecordWithRoute(Instant.ofEpochSecond(12000));
         String uuid = mTransactionTestUtils.insertRecords(TEST_PACKAGE_NAME, session).get(0);
@@ -439,7 +439,7 @@
                         Map.of(HealthPermissions.READ_EXERCISE_ROUTE, true));
 
         List<RecordInternal<?>> returnedRecords =
-                mTransactionManager.readRecordsAndNextRecordStartTime(request).first;
+                mTransactionManager.readRecordsAndPageToken(request).first;
 
         assertThat(returnedRecords).hasSize(1);
         ExerciseSessionRecordInternal returnedRecord =
diff --git a/tests/unittests/src/com/android/server/healthconnect/storage/TransactionManagerTest.java b/tests/unittests/src/com/android/server/healthconnect/storage/TransactionManagerTest.java
index d536e87..c4295a1 100644
--- a/tests/unittests/src/com/android/server/healthconnect/storage/TransactionManagerTest.java
+++ b/tests/unittests/src/com/android/server/healthconnect/storage/TransactionManagerTest.java
@@ -40,6 +40,8 @@
 import com.android.server.healthconnect.storage.datatypehelpers.HealthConnectDatabaseTestRule;
 import com.android.server.healthconnect.storage.datatypehelpers.TransactionTestUtils;
 import com.android.server.healthconnect.storage.request.ReadTransactionRequest;
+import com.android.server.healthconnect.storage.utils.PageTokenUtil;
+import com.android.server.healthconnect.storage.utils.PageTokenWrapper;
 
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
@@ -133,7 +135,7 @@
     }
 
     @Test
-    public void readRecordsAndNextRecordStartTime_returnsRecordsAndTimestamp() {
+    public void readRecordsAndPageToken_returnsRecordsAndPageToken() {
         List<String> uuids =
                 mTransactionTestUtils.insertRecords(
                         TEST_PACKAGE_NAME,
@@ -149,6 +151,10 @@
                                         .build())
                         .setPageSize(1)
                         .build();
+        long expectedToken =
+                PageTokenUtil.encode(
+                        PageTokenWrapper.of(
+                                /* isAscending= */ true, /* timeMillis= */ 500, /* offset= */ 0));
 
         ReadTransactionRequest readTransactionRequest =
                 new ReadTransactionRequest(
@@ -157,16 +163,16 @@
                         /* startDateAccess= */ 0,
                         /* enforceSelfRead= */ false,
                         /* extraReadPermsMapping= */ new ArrayMap<>());
-        Pair<List<RecordInternal<?>>, Long> blah =
-                mTransactionManager.readRecordsAndNextRecordStartTime(readTransactionRequest);
-        List<RecordInternal<?>> records = blah.first;
+        Pair<List<RecordInternal<?>>, Long> result =
+                mTransactionManager.readRecordsAndPageToken(readTransactionRequest);
+        List<RecordInternal<?>> records = result.first;
         assertThat(records).hasSize(1);
-        assertThat(blah.first.get(0).getUuid()).isEqualTo(UUID.fromString(uuids.get(0)));
-        assertThat(blah.second).isEqualTo(500);
+        assertThat(result.first.get(0).getUuid()).isEqualTo(UUID.fromString(uuids.get(0)));
+        assertThat(result.second).isEqualTo(expectedToken);
     }
 
     @Test
-    public void readRecordsAndNextRecordStartTime_multipleRecordTypes_throws() {
+    public void readRecordsAndPageToken_multipleRecordTypes_throws() {
         ReadTransactionRequest request =
                 new ReadTransactionRequest(
                         TEST_PACKAGE_NAME,
@@ -181,7 +187,7 @@
         Throwable thrown =
                 assertThrows(
                         IllegalArgumentException.class,
-                        () -> mTransactionManager.readRecordsAndNextRecordStartTime(request));
+                        () -> mTransactionManager.readRecordsAndPageToken(request));
         assertThat(thrown.getMessage()).contains("expected one element");
     }
 }
diff --git a/tests/unittests/src/com/android/server/healthconnect/storage/datatypehelpers/RecordHelperTest.java b/tests/unittests/src/com/android/server/healthconnect/storage/datatypehelpers/RecordHelperTest.java
index 755879c..e47d3a4 100644
--- a/tests/unittests/src/com/android/server/healthconnect/storage/datatypehelpers/RecordHelperTest.java
+++ b/tests/unittests/src/com/android/server/healthconnect/storage/datatypehelpers/RecordHelperTest.java
@@ -16,20 +16,31 @@
 
 package com.android.server.healthconnect.storage.datatypehelpers;
 
+import static android.health.connect.Constants.DEFAULT_LONG;
+
 import static com.android.server.healthconnect.storage.datatypehelpers.StepsRecordHelper.STEPS_TABLE_NAME;
 import static com.android.server.healthconnect.storage.datatypehelpers.TransactionTestUtils.createStepsRecord;
 
 import static com.google.common.truth.Truth.assertThat;
 
 import android.database.Cursor;
+import android.health.connect.ReadRecordsRequestUsingFilters;
+import android.health.connect.TimeInstantRangeFilter;
+import android.health.connect.aidl.ReadRecordsRequestParcel;
+import android.health.connect.datatypes.StepsRecord;
 import android.health.connect.internal.datatypes.RecordInternal;
 import android.health.connect.internal.datatypes.StepsRecordInternal;
+import android.util.Pair;
 
 import androidx.test.runner.AndroidJUnit4;
 
 import com.android.server.healthconnect.HealthConnectUserContext;
 import com.android.server.healthconnect.storage.TransactionManager;
 import com.android.server.healthconnect.storage.request.ReadTableRequest;
+import com.android.server.healthconnect.storage.utils.OrderByClause;
+import com.android.server.healthconnect.storage.utils.PageTokenUtil;
+import com.android.server.healthconnect.storage.utils.PageTokenWrapper;
+import com.android.server.healthconnect.storage.utils.WhereClauses;
 
 import org.junit.After;
 import org.junit.Before;
@@ -37,6 +48,7 @@
 import org.junit.Test;
 import org.junit.runner.RunWith;
 
+import java.time.Instant;
 import java.util.List;
 import java.util.UUID;
 
@@ -53,6 +65,7 @@
     public void setup() throws Exception {
         HealthConnectUserContext context = testRule.getUserContext();
         mTransactionManager = TransactionManager.getInstance(context);
+        DatabaseHelper.clearAllData(mTransactionManager);
         mTransactionTestUtils = new TransactionTestUtils(context, mTransactionManager);
         mTransactionTestUtils.insertApp(TEST_PACKAGE_NAME);
     }
@@ -115,4 +128,177 @@
             assertThat(records.get(0).getUuid()).isEqualTo(UUID.fromString(uids.get(0)));
         }
     }
+
+    @Test
+    public void getNextInternalRecordsPageAndToken_zeroOffsetDesc_correctResults() {
+        RecordHelper<?> helper = new StepsRecordHelper();
+        int pageSize = 1;
+        boolean isAscending = false;
+        mTransactionTestUtils.insertRecords(
+                TEST_PACKAGE_NAME,
+                createStepsRecord(
+                        "client.id1",
+                        /* startTimeMillis= */ 4000,
+                        /* endTimeMillis= */ 4500,
+                        /* stepsCount= */ 1000),
+                createStepsRecord(
+                        "client.id2",
+                        /* startTimeMillis= */ 6000,
+                        /* endTimeMillis= */ 7000,
+                        /* stepsCount= */ 500));
+
+        long expectedTimestamp = 4000L;
+        int expectedOffset = 0;
+        PageTokenWrapper expectedPageToken =
+                PageTokenWrapper.of(isAscending, expectedTimestamp, expectedOffset);
+
+        OrderByClause orderByStartTime =
+                new OrderByClause().addOrderByClause(helper.getStartTimeColumnName(), isAscending);
+        ReadTableRequest request1 =
+                new ReadTableRequest(STEPS_TABLE_NAME)
+                        .setOrderBy(orderByStartTime)
+                        .setLimit(pageSize + 1);
+        try (Cursor cursor = mTransactionManager.read(request1)) {
+            Pair<List<RecordInternal<?>>, Long> page1 =
+                    helper.getNextInternalRecordsPageAndToken(
+                            cursor, pageSize, PageTokenWrapper.of(isAscending));
+            assertThat(page1.first).hasSize(pageSize);
+            assertThat(page1.first.get(0).getClientRecordId()).isEqualTo("client.id2");
+            assertThat(page1.second).isEqualTo(PageTokenUtil.encode(expectedPageToken));
+        }
+
+        WhereClauses whereClause =
+                new WhereClauses()
+                        .addWhereLessThanOrEqualClause(
+                                helper.getStartTimeColumnName(), expectedTimestamp);
+        ReadTableRequest request2 =
+                new ReadTableRequest(STEPS_TABLE_NAME)
+                        .setOrderBy(orderByStartTime)
+                        .setWhereClause(whereClause)
+                        .setLimit(pageSize + 1 + expectedOffset);
+        try (Cursor cursor = mTransactionManager.read(request2)) {
+            Pair<List<RecordInternal<?>>, Long> page2 =
+                    helper.getNextInternalRecordsPageAndToken(cursor, pageSize, expectedPageToken);
+            assertThat(page2.first).hasSize(pageSize);
+            assertThat(page2.first.get(0).getClientRecordId()).isEqualTo("client.id1");
+            assertThat(page2.second).isEqualTo(DEFAULT_LONG);
+        }
+    }
+
+    @Test
+    public void getNextInternalRecordsPageAndToken_sameStartTimeAsc_correctResults() {
+        RecordHelper<?> helper = new StepsRecordHelper();
+        int pageSize = 3;
+        boolean isAscending = true;
+        mTransactionTestUtils.insertRecords(
+                TEST_PACKAGE_NAME,
+                // in page 1
+                createStepsRecord(
+                        "id1",
+                        /* startTimeMillis= */ 3000,
+                        /* endTimeMillis= */ 45000,
+                        /* stepsCount= */ 1000),
+                createStepsRecord(
+                        "id2",
+                        /* startTimeMillis= */ 4000,
+                        /* endTimeMillis= */ 5000,
+                        /* stepsCount= */ 100),
+                createStepsRecord(
+                        "id3",
+                        /* startTimeMillis= */ 4000,
+                        /* endTimeMillis= */ 6000,
+                        /* stepsCount= */ 200),
+                // in page 2
+                createStepsRecord(
+                        "id4",
+                        /* startTimeMillis= */ 4000,
+                        /* endTimeMillis= */ 7000,
+                        /* stepsCount= */ 300),
+                createStepsRecord(
+                        "id5",
+                        /* startTimeMillis= */ 5000,
+                        /* endTimeMillis= */ 6000,
+                        /* stepsCount= */ 400),
+                createStepsRecord(
+                        "id6",
+                        /* startTimeMillis= */ 6000,
+                        /* endTimeMillis= */ 7000,
+                        /* stepsCount= */ 500));
+
+        long expectedTimestamp = 4000L;
+        int expectedOffset = 2;
+        PageTokenWrapper expectedPageToken =
+                PageTokenWrapper.of(isAscending, expectedTimestamp, expectedOffset);
+
+        TimeInstantRangeFilter filter =
+                new TimeInstantRangeFilter.Builder()
+                        .setStartTime(Instant.ofEpochMilli(3000))
+                        .setEndTime(Instant.ofEpochMilli(10000))
+                        .build();
+        ReadRecordsRequestUsingFilters<StepsRecord> readRequest1 =
+                new ReadRecordsRequestUsingFilters.Builder<>(StepsRecord.class)
+                        .setTimeRangeFilter(filter)
+                        .setPageSize(pageSize)
+                        .build();
+        ReadTableRequest request1 =
+                getReadTableRequest(helper, readRequest1.toReadRecordsRequestParcel());
+        try (Cursor cursor = mTransactionManager.read(request1)) {
+            Pair<List<RecordInternal<?>>, Long> page1 =
+                    helper.getNextInternalRecordsPageAndToken(
+                            cursor, pageSize, PageTokenWrapper.of(isAscending));
+            assertThat(page1.first).hasSize(3);
+            assertThat(page1.first.get(0).getClientRecordId()).isEqualTo("id1");
+            assertThat(page1.first.get(1).getClientRecordId()).isEqualTo("id2");
+            assertThat(page1.first.get(2).getClientRecordId()).isEqualTo("id3");
+            assertThat(page1.second).isEqualTo(PageTokenUtil.encode(expectedPageToken));
+        }
+
+        ReadRecordsRequestUsingFilters<StepsRecord> readRequest2 =
+                new ReadRecordsRequestUsingFilters.Builder<>(StepsRecord.class)
+                        .setTimeRangeFilter(filter)
+                        .setPageSize(pageSize)
+                        .setPageToken(PageTokenUtil.encode(expectedPageToken))
+                        .build();
+        ReadTableRequest request2 =
+                getReadTableRequest(helper, readRequest2.toReadRecordsRequestParcel());
+        try (Cursor cursor = mTransactionManager.read(request2)) {
+            Pair<List<RecordInternal<?>>, Long> page2 =
+                    helper.getNextInternalRecordsPageAndToken(cursor, pageSize, expectedPageToken);
+            assertThat(page2.first).hasSize(pageSize);
+            assertThat(page2.first.get(0).getClientRecordId()).isEqualTo("id4");
+            assertThat(page2.first.get(1).getClientRecordId()).isEqualTo("id5");
+            assertThat(page2.first.get(2).getClientRecordId()).isEqualTo("id6");
+            assertThat(page2.second).isEqualTo(DEFAULT_LONG);
+        }
+    }
+
+    @Test
+    public void getNextInternalRecordsPageAndToken_wrongOffsetPageToken_skipSameStartTimeRecords() {
+        RecordHelper<?> helper = new StepsRecordHelper();
+        mTransactionTestUtils.insertRecords(
+                TEST_PACKAGE_NAME,
+                createStepsRecord("id1", 4000, 5000, 100),
+                createStepsRecord("id2", 5000, 6000, 100));
+        PageTokenWrapper incorrectToken = PageTokenWrapper.of(true, 4000, 2);
+        ReadTableRequest request = new ReadTableRequest(STEPS_TABLE_NAME);
+        try (Cursor cursor = mTransactionManager.read(request)) {
+            Pair<List<RecordInternal<?>>, Long> result =
+                    helper.getNextInternalRecordsPageAndToken(
+                            cursor, /* requestSize= */ 2, incorrectToken);
+            // skip the first record, but preserve the second because start time is different
+            assertThat(result.first).hasSize(1);
+            assertThat(result.first.get(0).getClientRecordId()).isEqualTo("id2");
+            assertThat(result.second).isEqualTo(DEFAULT_LONG);
+        }
+    }
+
+    private static ReadTableRequest getReadTableRequest(
+            RecordHelper<?> helper, ReadRecordsRequestParcel request) {
+        return helper.getReadTableRequest(
+                request,
+                TEST_PACKAGE_NAME,
+                /* enforceSelfRead= */ false,
+                /* startDateAccess= */ 0,
+                /* extraPermsState= */ null);
+    }
 }
diff --git a/tests/unittests/src/com/android/server/healthconnect/storage/datatypehelpers/TransactionTestUtils.java b/tests/unittests/src/com/android/server/healthconnect/storage/datatypehelpers/TransactionTestUtils.java
index 3283851..c437e67 100644
--- a/tests/unittests/src/com/android/server/healthconnect/storage/datatypehelpers/TransactionTestUtils.java
+++ b/tests/unittests/src/com/android/server/healthconnect/storage/datatypehelpers/TransactionTestUtils.java
@@ -83,10 +83,16 @@
 
     public static RecordInternal<StepsRecord> createStepsRecord(
             long startTimeMillis, long endTimeMillis, int stepsCount) {
+        return createStepsRecord(/* clientId= */ null, startTimeMillis, endTimeMillis, stepsCount);
+    }
+
+    public static RecordInternal<StepsRecord> createStepsRecord(
+            String clientId, long startTimeMillis, long endTimeMillis, int stepsCount) {
         return new StepsRecordInternal()
                 .setCount(stepsCount)
                 .setStartTime(startTimeMillis)
-                .setEndTime(endTimeMillis);
+                .setEndTime(endTimeMillis)
+                .setClientRecordId(clientId);
     }
 
     public static RecordInternal<BloodPressureRecord> createBloodPressureRecord(