dex2oat: Pack likely-dirty objects together when generating the boot image

This introduces a new algorithm into image writer which "bins" objects
by how likely they are to be dirtied at runtime. Objects in the same bin
are placed contiguously in memory (i.e. into the same page). We try to
tune the bin selection based on how clean or how dirty the object will
likely be at runtime.

As-is, this saves about 150KB per-process (private-dirty pages) and 700KB in
zygote (shared-dirty).

There is still about 800KB of objects that are clean but located in
dirty pages, so with more analysis we can tune the bin selection and get
even more memory savings.

(cherry picked from commit 3f735bd4f9d09a0f9b2b01321e4c6917879dcae6)

Bug: 17611661
Change-Id: Ia1455e4c56ffd0a36ae2a723d35b7e06502980f7

1 files changed, 32 insertions, 0 deletions

diff --git a/runtime/utils_test.cc b/runtime/utils_test.cc
index 92323da554..a98bc909f2 100644
--- a/runtime/utils_test.cc
+++ b/runtime/utils_test.cc
@@ -402,4 +402,36 @@ TEST_F(UtilsTest, ExecError) {
   }
 }
 
+TEST_F(UtilsTest, RoundUpToPowerOfTwo) {
+  // Tests the constexpr variant since all the parameters are constexpr
+  EXPECT_EQ(0, RoundUpToPowerOfTwo(0));
+  EXPECT_EQ(1, RoundUpToPowerOfTwo(1));
+  EXPECT_EQ(2, RoundUpToPowerOfTwo(2));
+  EXPECT_EQ(4, RoundUpToPowerOfTwo(3));
+  EXPECT_EQ(8, RoundUpToPowerOfTwo(7));
+
+  EXPECT_EQ(0b10000L, RoundUpToPowerOfTwo(0b01101L));
+  EXPECT_EQ(1ULL << 63, RoundUpToPowerOfTwo(1ULL << 62 | 1ULL));
+}
+
+TEST_F(UtilsTest, MostSignificantBit) {
+  EXPECT_EQ(-1, MostSignificantBit(0));
+  EXPECT_EQ(0, MostSignificantBit(1));
+  EXPECT_EQ(31, MostSignificantBit(~static_cast<uint32_t>(0)));
+  EXPECT_EQ(2, MostSignificantBit(0b110));
+  EXPECT_EQ(2, MostSignificantBit(0b100));
+}
+
+TEST_F(UtilsTest, MinimumBitsToStore) {
+  EXPECT_EQ(0u, MinimumBitsToStore(0));
+  EXPECT_EQ(1u, MinimumBitsToStore(1));
+  EXPECT_EQ(2u, MinimumBitsToStore(0b10));
+  EXPECT_EQ(2u, MinimumBitsToStore(0b11));
+  EXPECT_EQ(3u, MinimumBitsToStore(0b100));
+  EXPECT_EQ(3u, MinimumBitsToStore(0b110));
+  EXPECT_EQ(3u, MinimumBitsToStore(0b101));
+  EXPECT_EQ(8u, MinimumBitsToStore(0xFF));
+  EXPECT_EQ(32u, MinimumBitsToStore(~static_cast<uint32_t>(0)));
+}
+
 }  // namespace art