Rewrite of CursorWindow internals.

The original CursorWindow implementation was created in Android 1.0
and has remained relatively unchanged since then.  Unfortunately that
design results in very poor performance on large windows, since
reading or writing each FieldSlot is O(row/100) to traverse through
a chain of RowSlotChunks.  It's also memory-inefficient due to how
it allocates RowSlotChunks in 404 byte chunks, even when there's only
a single row to store.

This change is a complete redesign of the CursorWindow internals to
use a "heap-and-stack" style approach, where a "heap" of strings
and blobs increment up from the bottom of the window while a "stack"
of FieldSlots increment down from the top of the window.

The included benchmarks show the following improvements, ensuring
no regressions for small windows, while offering very dramatic
improvements for larger windows:

                Big cores      Little cores
4x4 cursor      no regression  no regression
1024x4 cursor   2.2x faster    2.0x faster
16384x4 cursor  48.5x faster   24.4x faster

Detailed unit testing is also included to ensure that the rewrite
behaves correctly.

Bug: 169251528
Test: atest libandroidfw_tests
Test: atest CtsDatabaseTestCases
Test: atest FrameworksCoreTests:android.database
Test: ./frameworks/base/libs/hwui/tests/scripts/prep_generic.sh little && atest libandroidfw_benchmarks
Test: ./frameworks/base/libs/hwui/tests/scripts/prep_generic.sh little && atest CorePerfTests:android.database.CrossProcessCursorPerfTest
Change-Id: I90dff31fd550130dae917a33e0e1fa684e15c107

1 files changed, 359 insertions, 0 deletions

diff --git a/libs/androidfw/tests/CursorWindow_test.cpp b/libs/androidfw/tests/CursorWindow_test.cpp
new file mode 100644
index 000000000000..dfcf76e6edf6
--- /dev/null
+++ b/libs/androidfw/tests/CursorWindow_test.cpp
@@ -0,0 +1,359 @@
+/*
+ * Copyright (C) 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.
+ */
+
+#include <utility>
+
+#include "androidfw/CursorWindow.h"
+
+#include "TestHelpers.h"
+
+#define CREATE_WINDOW_1K \
+    CursorWindow* w; \
+    CursorWindow::create(String8("test"), 1 << 10, &w);
+
+#define CREATE_WINDOW_1K_3X3 \
+    CursorWindow* w; \
+    CursorWindow::create(String8("test"), 1 << 10, &w); \
+    ASSERT_EQ(w->setNumColumns(3), OK); \
+    ASSERT_EQ(w->allocRow(), OK); \
+    ASSERT_EQ(w->allocRow(), OK); \
+    ASSERT_EQ(w->allocRow(), OK);
+
+#define CREATE_WINDOW_2M \
+    CursorWindow* w; \
+    CursorWindow::create(String8("test"), 1 << 21, &w);
+
+static constexpr const size_t kHalfInlineSize = 8192;
+static constexpr const size_t kGiantSize = 1048576;
+
+namespace android {
+
+TEST(CursorWindowTest, Empty) {
+    CREATE_WINDOW_1K;
+
+    ASSERT_EQ(w->getNumRows(), 0);
+    ASSERT_EQ(w->getNumColumns(), 0);
+    ASSERT_EQ(w->size(), 1 << 10);
+    ASSERT_EQ(w->freeSpace(), 1 << 10);
+}
+
+TEST(CursorWindowTest, SetNumColumns) {
+    CREATE_WINDOW_1K;
+
+    // Once we've locked in columns, we can't adjust
+    ASSERT_EQ(w->getNumColumns(), 0);
+    ASSERT_EQ(w->setNumColumns(4), OK);
+    ASSERT_NE(w->setNumColumns(5), OK);
+    ASSERT_NE(w->setNumColumns(3), OK);
+    ASSERT_EQ(w->getNumColumns(), 4);
+}
+
+TEST(CursorWindowTest, SetNumColumnsAfterRow) {
+    CREATE_WINDOW_1K;
+
+    // Once we've locked in a row, we can't adjust columns
+    ASSERT_EQ(w->getNumColumns(), 0);
+    ASSERT_EQ(w->allocRow(), OK);
+    ASSERT_NE(w->setNumColumns(4), OK);
+    ASSERT_EQ(w->getNumColumns(), 0);
+}
+
+TEST(CursorWindowTest, AllocRow) {
+    CREATE_WINDOW_1K;
+
+    ASSERT_EQ(w->setNumColumns(4), OK);
+
+    // Rolling forward means we have less free space
+    ASSERT_EQ(w->getNumRows(), 0);
+    auto before = w->freeSpace();
+    ASSERT_EQ(w->allocRow(), OK);
+    ASSERT_LT(w->freeSpace(), before);
+    ASSERT_EQ(w->getNumRows(), 1);
+
+    // Verify we can unwind
+    ASSERT_EQ(w->freeLastRow(), OK);
+    ASSERT_EQ(w->freeSpace(), before);
+    ASSERT_EQ(w->getNumRows(), 0);
+
+    // Can't unwind when no rows left
+    ASSERT_NE(w->freeLastRow(), OK);
+}
+
+TEST(CursorWindowTest, AllocRowBounds) {
+    CREATE_WINDOW_1K;
+
+    // 60 columns is 960 bytes, which means only a single row can fit
+    ASSERT_EQ(w->setNumColumns(60), OK);
+    ASSERT_EQ(w->allocRow(), OK);
+    ASSERT_NE(w->allocRow(), OK);
+}
+
+TEST(CursorWindowTest, StoreNull) {
+    CREATE_WINDOW_1K_3X3;
+
+    ASSERT_EQ(w->putNull(1, 1), OK);
+    ASSERT_EQ(w->putNull(0, 0), OK);
+
+    {
+        auto field = w->getFieldSlot(1, 1);
+        ASSERT_EQ(w->getFieldSlotType(field), CursorWindow::FIELD_TYPE_NULL);
+    }
+    {
+        auto field = w->getFieldSlot(0, 0);
+        ASSERT_EQ(w->getFieldSlotType(field), CursorWindow::FIELD_TYPE_NULL);
+    }
+}
+
+TEST(CursorWindowTest, StoreLong) {
+    CREATE_WINDOW_1K_3X3;
+
+    ASSERT_EQ(w->putLong(1, 1, 0xf00d), OK);
+    ASSERT_EQ(w->putLong(0, 0, 0xcafe), OK);
+
+    {
+        auto field = w->getFieldSlot(1, 1);
+        ASSERT_EQ(w->getFieldSlotType(field), CursorWindow::FIELD_TYPE_INTEGER);
+        ASSERT_EQ(w->getFieldSlotValueLong(field), 0xf00d);
+    }
+    {
+        auto field = w->getFieldSlot(0, 0);
+        ASSERT_EQ(w->getFieldSlotType(field), CursorWindow::FIELD_TYPE_INTEGER);
+        ASSERT_EQ(w->getFieldSlotValueLong(field), 0xcafe);
+    }
+}
+
+TEST(CursorWindowTest, StoreString) {
+    CREATE_WINDOW_1K_3X3;
+
+    ASSERT_EQ(w->putString(1, 1, "food", 5), OK);
+    ASSERT_EQ(w->putString(0, 0, "cafe", 5), OK);
+
+    size_t size;
+    {
+        auto field = w->getFieldSlot(1, 1);
+        ASSERT_EQ(w->getFieldSlotType(field), CursorWindow::FIELD_TYPE_STRING);
+        auto actual = w->getFieldSlotValueString(field, &size);
+        ASSERT_EQ(std::string(actual), "food");
+    }
+    {
+        auto field = w->getFieldSlot(0, 0);
+        ASSERT_EQ(w->getFieldSlotType(field), CursorWindow::FIELD_TYPE_STRING);
+        auto actual = w->getFieldSlotValueString(field, &size);
+        ASSERT_EQ(std::string(actual), "cafe");
+    }
+}
+
+TEST(CursorWindowTest, StoreBounds) {
+    CREATE_WINDOW_1K_3X3;
+
+    // Can't work with values beyond bounds
+    ASSERT_NE(w->putLong(0, 3, 0xcafe), OK);
+    ASSERT_NE(w->putLong(3, 0, 0xcafe), OK);
+    ASSERT_NE(w->putLong(3, 3, 0xcafe), OK);
+    ASSERT_EQ(w->getFieldSlot(0, 3), nullptr);
+    ASSERT_EQ(w->getFieldSlot(3, 0), nullptr);
+    ASSERT_EQ(w->getFieldSlot(3, 3), nullptr);
+}
+
+TEST(CursorWindowTest, Inflate) {
+    CREATE_WINDOW_2M;
+
+    auto before = w->size();
+    ASSERT_EQ(w->setNumColumns(4), OK);
+    ASSERT_EQ(w->allocRow(), OK);
+
+    // Scratch buffer that will fit before inflation
+    void* buf = malloc(kHalfInlineSize);
+
+    // Store simple value
+    ASSERT_EQ(w->putLong(0, 0, 0xcafe), OK);
+
+    // Store first object that fits inside
+    memset(buf, 42, kHalfInlineSize);
+    ASSERT_EQ(w->putBlob(0, 1, buf, kHalfInlineSize), OK);
+    ASSERT_EQ(w->size(), before);
+
+    // Store second simple value
+    ASSERT_EQ(w->putLong(0, 2, 0xface), OK);
+
+    // Store second object that requires inflation
+    memset(buf, 84, kHalfInlineSize);
+    ASSERT_EQ(w->putBlob(0, 3, buf, kHalfInlineSize), OK);
+    ASSERT_GT(w->size(), before);
+
+    // Verify data is intact
+    {
+        auto field = w->getFieldSlot(0, 0);
+        ASSERT_EQ(w->getFieldSlotType(field), CursorWindow::FIELD_TYPE_INTEGER);
+        ASSERT_EQ(w->getFieldSlotValueLong(field), 0xcafe);
+    }
+    {
+        auto field = w->getFieldSlot(0, 1);
+        ASSERT_EQ(w->getFieldSlotType(field), CursorWindow::FIELD_TYPE_BLOB);
+        size_t actualSize;
+        auto actual = w->getFieldSlotValueBlob(field, &actualSize);
+        ASSERT_EQ(actualSize, kHalfInlineSize);
+        memset(buf, 42, kHalfInlineSize);
+        ASSERT_NE(actual, buf);
+        ASSERT_EQ(memcmp(buf, actual, kHalfInlineSize), 0);
+    }
+    {
+        auto field = w->getFieldSlot(0, 2);
+        ASSERT_EQ(w->getFieldSlotType(field), CursorWindow::FIELD_TYPE_INTEGER);
+        ASSERT_EQ(w->getFieldSlotValueLong(field), 0xface);
+    }
+    {
+        auto field = w->getFieldSlot(0, 3);
+        ASSERT_EQ(w->getFieldSlotType(field), CursorWindow::FIELD_TYPE_BLOB);
+        size_t actualSize;
+        auto actual = w->getFieldSlotValueBlob(field, &actualSize);
+        ASSERT_EQ(actualSize, kHalfInlineSize);
+        memset(buf, 84, kHalfInlineSize);
+        ASSERT_NE(actual, buf);
+        ASSERT_EQ(memcmp(buf, actual, kHalfInlineSize), 0);
+    }
+}
+
+TEST(CursorWindowTest, ParcelEmpty) {
+    CREATE_WINDOW_2M;
+
+    Parcel p;
+    w->writeToParcel(&p);
+    p.setDataPosition(0);
+    w = nullptr;
+
+    ASSERT_EQ(CursorWindow::createFromParcel(&p, &w), OK);
+    ASSERT_EQ(w->getNumRows(), 0);
+    ASSERT_EQ(w->getNumColumns(), 0);
+    ASSERT_EQ(w->size(), 0);
+    ASSERT_EQ(w->freeSpace(), 0);
+
+    // We can't mutate the window after parceling
+    ASSERT_NE(w->setNumColumns(4), OK);
+    ASSERT_NE(w->allocRow(), OK);
+}
+
+TEST(CursorWindowTest, ParcelSmall) {
+    CREATE_WINDOW_2M;
+
+    auto before = w->size();
+    ASSERT_EQ(w->setNumColumns(4), OK);
+    ASSERT_EQ(w->allocRow(), OK);
+
+    // Scratch buffer that will fit before inflation
+    void* buf = malloc(kHalfInlineSize);
+
+    // Store simple value
+    ASSERT_EQ(w->putLong(0, 0, 0xcafe), OK);
+
+    // Store first object that fits inside
+    memset(buf, 42, kHalfInlineSize);
+    ASSERT_EQ(w->putBlob(0, 1, buf, kHalfInlineSize), OK);
+    ASSERT_EQ(w->size(), before);
+
+    // Store second object with zero length
+    ASSERT_EQ(w->putBlob(0, 2, buf, 0), OK);
+    ASSERT_EQ(w->size(), before);
+
+    // Force through a parcel
+    Parcel p;
+    w->writeToParcel(&p);
+    p.setDataPosition(0);
+    w = nullptr;
+
+    ASSERT_EQ(CursorWindow::createFromParcel(&p, &w), OK);
+    ASSERT_EQ(w->getNumRows(), 1);
+    ASSERT_EQ(w->getNumColumns(), 4);
+
+    // Verify data is intact
+    {
+        auto field = w->getFieldSlot(0, 0);
+        ASSERT_EQ(w->getFieldSlotType(field), CursorWindow::FIELD_TYPE_INTEGER);
+        ASSERT_EQ(w->getFieldSlotValueLong(field), 0xcafe);
+    }
+    {
+        auto field = w->getFieldSlot(0, 1);
+        ASSERT_EQ(w->getFieldSlotType(field), CursorWindow::FIELD_TYPE_BLOB);
+        size_t actualSize;
+        auto actual = w->getFieldSlotValueBlob(field, &actualSize);
+        ASSERT_EQ(actualSize, kHalfInlineSize);
+        memset(buf, 42, kHalfInlineSize);
+        ASSERT_NE(actual, buf);
+        ASSERT_EQ(memcmp(buf, actual, kHalfInlineSize), 0);
+    }
+    {
+        auto field = w->getFieldSlot(0, 2);
+        ASSERT_EQ(w->getFieldSlotType(field), CursorWindow::FIELD_TYPE_BLOB);
+        size_t actualSize;
+        auto actual = w->getFieldSlotValueBlob(field, &actualSize);
+        ASSERT_EQ(actualSize, 0);
+        ASSERT_NE(actual, nullptr);
+    }
+}
+
+TEST(CursorWindowTest, ParcelLarge) {
+    CREATE_WINDOW_2M;
+
+    ASSERT_EQ(w->setNumColumns(4), OK);
+    ASSERT_EQ(w->allocRow(), OK);
+
+    // Store simple value
+    ASSERT_EQ(w->putLong(0, 0, 0xcafe), OK);
+
+    // Store object that forces inflation
+    void* buf = malloc(kGiantSize);
+    memset(buf, 42, kGiantSize);
+    ASSERT_EQ(w->putBlob(0, 1, buf, kGiantSize), OK);
+
+    // Store second object with zero length
+    ASSERT_EQ(w->putBlob(0, 2, buf, 0), OK);
+
+    // Force through a parcel
+    Parcel p;
+    w->writeToParcel(&p);
+    p.setDataPosition(0);
+    w = nullptr;
+
+    ASSERT_EQ(CursorWindow::createFromParcel(&p, &w), OK);
+    ASSERT_EQ(w->getNumRows(), 1);
+    ASSERT_EQ(w->getNumColumns(), 4);
+
+    // Verify data is intact
+    {
+        auto field = w->getFieldSlot(0, 0);
+        ASSERT_EQ(w->getFieldSlotType(field), CursorWindow::FIELD_TYPE_INTEGER);
+        ASSERT_EQ(w->getFieldSlotValueLong(field), 0xcafe);
+    }
+    {
+        auto field = w->getFieldSlot(0, 1);
+        ASSERT_EQ(w->getFieldSlotType(field), CursorWindow::FIELD_TYPE_BLOB);
+        size_t actualSize;
+        auto actual = w->getFieldSlotValueBlob(field, &actualSize);
+        ASSERT_EQ(actualSize, kGiantSize);
+        memset(buf, 42, kGiantSize);
+        ASSERT_EQ(memcmp(buf, actual, kGiantSize), 0);
+    }
+    {
+        auto field = w->getFieldSlot(0, 2);
+        ASSERT_EQ(w->getFieldSlotType(field), CursorWindow::FIELD_TYPE_BLOB);
+        size_t actualSize;
+        auto actual = w->getFieldSlotValueBlob(field, &actualSize);
+        ASSERT_EQ(actualSize, 0);
+        ASSERT_NE(actual, nullptr);
+    }
+}
+
+} // android