Avoid linear scans of database tables
Some places in Keystore perform linear scans of all rows in a database
table. This can cause slowdown and ANRs if the device has an excessive
number of keys.
Problem areas:
- The GC process (in `handle_next_superseded_blobs`) does a linear scan
of the `blobentry` table for rows where the corresponding key either
has a newer `blobentry` (of the same type), or has been deleted.
- The GC process (in `cleanup_unreferenced`) does a linear scan of
the `keyentry` table to find entries in the `Unreferenced` state,
and repeats this for several dependent tables.
- Listing an app's keys allows for batching, but the retrieval for
each batch queries the database for every key (even though only a
subset will be returned).
Update the database schema to avoid the need for these linear scans:
- Add a `state INTEGER` column to the `blobentry` table, used to
mark whether a row is current, superseded, or orphaned.
- Add an index on the new `state` column in the `blobentry` table.
- Add an index on the (existing) `state` column in the `keyentry` table.
- Add a 1->2 upgrade step that adds the column and the indices, and
sets the `state` value according to whether the blobentry
is the most recent of its type. This is essentially the same
logic/query as was previously in `handle_next_superseded_blob`,
only happening once at upgrade time.
Note that the schema changes are *not* flag-controlled, because that
would require additional code to downgrade the schema if the flag were
to be flipped back.
Update behaviour as follows:
- Add a limit of 10,000 rows when retrieving a batch of keys/aliases for
an app.
- On deleting a `keyentry`, mark any corresponding `blobentry`
rows as superseded.
- On adding a new `blobentry` for a key, mark any already-existing
`blobentry` rows for the same (key, subcomponent_type) as superseded.
- To perform garbage collection in `handle_next_superseded_blobs`, just
- query for N keyblob rows that are not current, ready to delete them
via KeyMint.
- query for all non-keyblob rows that are not current, and delete them
there and then.
Note that the flag only affects the last of these (the GC process).
Bug: 319563050
Test: keystore2_test
Test: keystore2_client_tests
Test: modified CtsVerifier to create and use lots of keys
Test: force SPL upgrade and check keys usable
Flag: android.security.keystore2.use_blob_state_column
Change-Id: I7019bb530cce195d4a7a290c8c43f078d8fe8a76
diff --git a/keystore2/aconfig/flags.aconfig b/keystore2/aconfig/flags.aconfig
index 05dae46..bf4ed51 100644
--- a/keystore2/aconfig/flags.aconfig
+++ b/keystore2/aconfig/flags.aconfig
@@ -32,3 +32,11 @@
bug: "283077822"
is_fixed_read_only: true
}
+
+flag {
+ name: "use_blob_state_column"
+ namespace: "hardware_backed_security"
+ description: "Use state database column to track superseded blobentry rows"
+ bug: "319563050"
+ is_fixed_read_only: true
+}