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/src/database/tests.rs b/keystore2/src/database/tests.rs
index 5f882cd..381a45a 100644
--- a/keystore2/src/database/tests.rs
+++ b/keystore2/src/database/tests.rs
@@ -2429,6 +2429,20 @@
.unwrap()
}
+fn blob_count_in_state(db: &mut KeystoreDB, sc_type: SubComponentType, state: BlobState) -> usize {
+ db.with_transaction(TransactionBehavior::Deferred, |tx| {
+ tx.query_row(
+ "SELECT COUNT(*) FROM persistent.blobentry
+ WHERE subcomponent_type = ? AND state = ?;",
+ params![sc_type, state],
+ |row| row.get(0),
+ )
+ .context(ks_err!("Failed to count number of {sc_type:?} blobs"))
+ .no_gc()
+ })
+ .unwrap()
+}
+
#[test]
fn test_blobentry_gc() -> Result<()> {
let mut db = new_test_db()?;
@@ -2439,6 +2453,9 @@
let key_id5 = make_test_key_entry(&mut db, Domain::APP, 5, "key5", None)?.0;
assert_eq!(5, blob_count(&mut db, SubComponentType::KEY_BLOB));
+ assert_eq!(5, blob_count_in_state(&mut db, SubComponentType::KEY_BLOB, BlobState::Current));
+ assert_eq!(0, blob_count_in_state(&mut db, SubComponentType::KEY_BLOB, BlobState::Superseded));
+ assert_eq!(0, blob_count_in_state(&mut db, SubComponentType::KEY_BLOB, BlobState::Orphaned));
assert_eq!(5, blob_count(&mut db, SubComponentType::CERT));
assert_eq!(5, blob_count(&mut db, SubComponentType::CERT_CHAIN));
@@ -2447,6 +2464,9 @@
db.set_blob(&key_guard3, SubComponentType::KEY_BLOB, Some(&[1, 2, 3]), None)?;
assert_eq!(7, blob_count(&mut db, SubComponentType::KEY_BLOB));
+ assert_eq!(5, blob_count_in_state(&mut db, SubComponentType::KEY_BLOB, BlobState::Current));
+ assert_eq!(2, blob_count_in_state(&mut db, SubComponentType::KEY_BLOB, BlobState::Superseded));
+ assert_eq!(0, blob_count_in_state(&mut db, SubComponentType::KEY_BLOB, BlobState::Orphaned));
assert_eq!(5, blob_count(&mut db, SubComponentType::CERT));
assert_eq!(5, blob_count(&mut db, SubComponentType::CERT_CHAIN));
@@ -2459,6 +2479,9 @@
.unwrap();
assert_eq!(7, blob_count(&mut db, SubComponentType::KEY_BLOB));
+ assert_eq!(3, blob_count_in_state(&mut db, SubComponentType::KEY_BLOB, BlobState::Current));
+ assert_eq!(2, blob_count_in_state(&mut db, SubComponentType::KEY_BLOB, BlobState::Superseded));
+ assert_eq!(2, blob_count_in_state(&mut db, SubComponentType::KEY_BLOB, BlobState::Orphaned));
assert_eq!(5, blob_count(&mut db, SubComponentType::CERT));
assert_eq!(5, blob_count(&mut db, SubComponentType::CERT_CHAIN));
@@ -2468,6 +2491,9 @@
let superseded_ids: Vec<i64> = superseded.iter().map(|v| v.blob_id).collect();
assert_eq!(4, superseded.len());
assert_eq!(7, blob_count(&mut db, SubComponentType::KEY_BLOB));
+ assert_eq!(3, blob_count_in_state(&mut db, SubComponentType::KEY_BLOB, BlobState::Current));
+ assert_eq!(2, blob_count_in_state(&mut db, SubComponentType::KEY_BLOB, BlobState::Superseded));
+ assert_eq!(2, blob_count_in_state(&mut db, SubComponentType::KEY_BLOB, BlobState::Orphaned));
assert_eq!(5, blob_count(&mut db, SubComponentType::CERT));
assert_eq!(5, blob_count(&mut db, SubComponentType::CERT_CHAIN));
@@ -2477,6 +2503,9 @@
let superseded_ids: Vec<i64> = superseded.iter().map(|v| v.blob_id).collect();
assert_eq!(0, superseded.len());
assert_eq!(3, blob_count(&mut db, SubComponentType::KEY_BLOB));
+ assert_eq!(3, blob_count_in_state(&mut db, SubComponentType::KEY_BLOB, BlobState::Current));
+ assert_eq!(0, blob_count_in_state(&mut db, SubComponentType::KEY_BLOB, BlobState::Superseded));
+ assert_eq!(0, blob_count_in_state(&mut db, SubComponentType::KEY_BLOB, BlobState::Orphaned));
assert_eq!(3, blob_count(&mut db, SubComponentType::CERT));
assert_eq!(3, blob_count(&mut db, SubComponentType::CERT_CHAIN));
@@ -2484,6 +2513,9 @@
let superseded = db.handle_next_superseded_blobs(&superseded_ids, 20).unwrap();
assert_eq!(0, superseded.len());
assert_eq!(3, blob_count(&mut db, SubComponentType::KEY_BLOB));
+ assert_eq!(3, blob_count_in_state(&mut db, SubComponentType::KEY_BLOB, BlobState::Current));
+ assert_eq!(0, blob_count_in_state(&mut db, SubComponentType::KEY_BLOB, BlobState::Superseded));
+ assert_eq!(0, blob_count_in_state(&mut db, SubComponentType::KEY_BLOB, BlobState::Orphaned));
assert_eq!(3, blob_count(&mut db, SubComponentType::CERT));
assert_eq!(3, blob_count(&mut db, SubComponentType::CERT_CHAIN));
@@ -2491,6 +2523,55 @@
}
#[test]
+fn test_upgrade_1_to_2() -> Result<()> {
+ let mut db = new_test_db()?;
+ let _key_id1 = make_test_key_entry(&mut db, Domain::APP, 1, "key1", None)?.0;
+ let key_guard2 = make_test_key_entry(&mut db, Domain::APP, 2, "key2", None)?;
+ let key_guard3 = make_test_key_entry(&mut db, Domain::APP, 3, "key3", None)?;
+ let key_id4 = make_test_key_entry(&mut db, Domain::APP, 4, "key4", None)?.0;
+ let key_id5 = make_test_key_entry(&mut db, Domain::APP, 5, "key5", None)?.0;
+
+ // Replace the keyblobs for keys 2 and 3. The previous blobs will still exist.
+ db.set_blob(&key_guard2, SubComponentType::KEY_BLOB, Some(&[1, 2, 3]), None)?;
+ db.set_blob(&key_guard3, SubComponentType::KEY_BLOB, Some(&[1, 2, 3]), None)?;
+
+ // Delete keys 4 and 5. The keyblobs aren't removed yet.
+ db.with_transaction(Immediate("TX_delete_test_keys"), |tx| {
+ KeystoreDB::mark_unreferenced(tx, key_id4)?;
+ KeystoreDB::mark_unreferenced(tx, key_id5)?;
+ Ok(()).no_gc()
+ })
+ .unwrap();
+ assert_eq!(7, blob_count(&mut db, SubComponentType::KEY_BLOB));
+ assert_eq!(5, blob_count(&mut db, SubComponentType::CERT));
+ assert_eq!(5, blob_count(&mut db, SubComponentType::CERT_CHAIN));
+
+ // Manually downgrade the database to the v1 schema.
+ db.with_transaction(Immediate("TX_downgrade_2_to_1"), |tx| {
+ tx.execute("DROP INDEX persistent.keyentry_state_index;", params!())?;
+ tx.execute("DROP INDEX persistent.blobentry_state_index;", params!())?;
+ tx.execute("ALTER TABLE persistent.blobentry DROP COLUMN state;", params!())?;
+ Ok(()).no_gc()
+ })?;
+
+ // Run the upgrade process.
+ let version = db.with_transaction(Immediate("TX_upgrade_1_to_2"), |tx| {
+ KeystoreDB::from_1_to_2(tx).no_gc()
+ })?;
+ assert_eq!(version, 2);
+
+ // Check blobs have acquired the right `state` values.
+ assert_eq!(7, blob_count(&mut db, SubComponentType::KEY_BLOB));
+ assert_eq!(3, blob_count_in_state(&mut db, SubComponentType::KEY_BLOB, BlobState::Current));
+ assert_eq!(2, blob_count_in_state(&mut db, SubComponentType::KEY_BLOB, BlobState::Superseded));
+ assert_eq!(2, blob_count_in_state(&mut db, SubComponentType::KEY_BLOB, BlobState::Orphaned));
+ assert_eq!(5, blob_count(&mut db, SubComponentType::CERT));
+ assert_eq!(5, blob_count(&mut db, SubComponentType::CERT_CHAIN));
+
+ Ok(())
+}
+
+#[test]
fn test_load_key_descriptor() -> Result<()> {
let mut db = new_test_db()?;
let key_id = make_test_key_entry(&mut db, Domain::APP, 1, TEST_ALIAS, None)?.0;
@@ -2652,6 +2733,16 @@
where
F: Fn(&mut KeystoreDB) -> T,
{
+ prep_and_run_with_many_keys(max_count, |_db| (), test_fn)
+}
+
+/// Run the provided `test_fn` against the database at various increasing stages of
+/// database population.
+fn prep_and_run_with_many_keys<F, T, P>(max_count: usize, prep_fn: P, test_fn: F) -> Result<()>
+where
+ F: Fn(&mut KeystoreDB) -> T,
+ P: Fn(&mut KeystoreDB),
+{
android_logger::init_once(
android_logger::Config::default()
.with_tag("keystore2_test")
@@ -2670,6 +2761,10 @@
db_populate_keys(&mut db, next_keyid, key_count);
assert_eq!(db_key_count(&mut db), key_count);
+ // Perform any test-specific preparation
+ prep_fn(&mut db);
+
+ // Time execution of the test function.
let start = std::time::Instant::now();
let _result = test_fn(&mut db);
println!("{key_count}, {}", start.elapsed().as_secs_f64());
@@ -2753,3 +2848,27 @@
}
})
}
+
+#[test]
+fn test_upgrade_1_to_2_with_many_keys() -> Result<()> {
+ prep_and_run_with_many_keys(
+ 1_000_000,
+ |db: &mut KeystoreDB| {
+ // Manually downgrade the database to the v1 schema.
+ db.with_transaction(Immediate("TX_downgrade_2_to_1"), |tx| {
+ tx.execute("DROP INDEX persistent.keyentry_state_index;", params!())?;
+ tx.execute("DROP INDEX persistent.blobentry_state_index;", params!())?;
+ tx.execute("ALTER TABLE persistent.blobentry DROP COLUMN state;", params!())?;
+ Ok(()).no_gc()
+ })
+ .unwrap();
+ },
+ |db: &mut KeystoreDB| -> Result<()> {
+ // Run the upgrade process.
+ db.with_transaction(Immediate("TX_upgrade_1_to_2"), |tx| {
+ KeystoreDB::from_1_to_2(tx).no_gc()
+ })?;
+ Ok(())
+ },
+ )
+}