1 // Copyright 2020, The Android Open Source Project 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 //! This module implements the key garbage collector. 16 //! The key garbage collector has one public function `notify_gc()`. This will create 17 //! a thread on demand which will query the database for unreferenced key entries, 18 //! optionally dispose of sensitive key material appropriately, and then delete 19 //! the key entry from the database. 20 21 use crate::ks_err; 22 use crate::{ 23 async_task, 24 database::{KeystoreDB, SupersededBlob, Uuid}, 25 super_key::SuperKeyManager, 26 }; 27 use anyhow::{Context, Result}; 28 use async_task::AsyncTask; 29 use std::sync::{ 30 atomic::{AtomicU8, Ordering}, 31 Arc, RwLock, 32 }; 33 34 pub struct Gc { 35 async_task: Arc<AsyncTask>, 36 notified: Arc<AtomicU8>, 37 } 38 39 impl Gc { 40 /// Creates a garbage collector using the given async_task. 41 /// The garbage collector needs a function to invalidate key blobs, a database connection, 42 /// and a reference to the `SuperKeyManager`. They are obtained from the init function. 43 /// The function is only called if this is first time a garbage collector was initialized 44 /// with the given AsyncTask instance. 45 /// Note: It is a logical error to initialize different Gc instances with the same `AsyncTask`. new_init_with<F>(async_task: Arc<AsyncTask>, init: F) -> Self where F: FnOnce() -> ( Box<dyn Fn(&Uuid, &[u8]) -> Result<()> + Send + 'static>, KeystoreDB, Arc<RwLock<SuperKeyManager>>, ) + Send + 'static,46 pub fn new_init_with<F>(async_task: Arc<AsyncTask>, init: F) -> Self 47 where 48 F: FnOnce() -> ( 49 Box<dyn Fn(&Uuid, &[u8]) -> Result<()> + Send + 'static>, 50 KeystoreDB, 51 Arc<RwLock<SuperKeyManager>>, 52 ) + Send 53 + 'static, 54 { 55 let weak_at = Arc::downgrade(&async_task); 56 let notified = Arc::new(AtomicU8::new(0)); 57 let notified_clone = notified.clone(); 58 // Initialize the task's shelf. 59 async_task.queue_hi(move |shelf| { 60 let (invalidate_key, db, super_key) = init(); 61 let notified = notified_clone; 62 shelf.get_or_put_with(|| GcInternal { 63 deleted_blob_ids: vec![], 64 superseded_blobs: vec![], 65 invalidate_key, 66 db, 67 async_task: weak_at, 68 super_key, 69 notified, 70 }); 71 }); 72 Self { async_task, notified } 73 } 74 75 /// Notifies the key garbage collector to iterate through orphaned and superseded blobs and 76 /// attempts their deletion. We only process one key at a time and then schedule another 77 /// attempt by queueing it in the async_task (low priority) queue. notify_gc(&self)78 pub fn notify_gc(&self) { 79 if let Ok(0) = self.notified.compare_exchange(0, 1, Ordering::Relaxed, Ordering::Relaxed) { 80 self.async_task.queue_lo(|shelf| shelf.get_downcast_mut::<GcInternal>().unwrap().step()) 81 } 82 } 83 } 84 85 struct GcInternal { 86 deleted_blob_ids: Vec<i64>, 87 superseded_blobs: Vec<SupersededBlob>, 88 invalidate_key: Box<dyn Fn(&Uuid, &[u8]) -> Result<()> + Send + 'static>, 89 db: KeystoreDB, 90 async_task: std::sync::Weak<AsyncTask>, 91 super_key: Arc<RwLock<SuperKeyManager>>, 92 notified: Arc<AtomicU8>, 93 } 94 95 impl GcInternal { 96 /// Attempts to process one blob from the database. 97 /// We process one key at a time, because deleting a key is a time consuming process which 98 /// may involve calling into the KeyMint backend and we don't want to hog neither the backend 99 /// nor the database for extended periods of time. 100 /// To limit the number of database transactions, which are also expensive and competing 101 /// with threads on the critical path, deleted blobs are loaded in batches. process_one_key(&mut self) -> Result<()>102 fn process_one_key(&mut self) -> Result<()> { 103 if self.superseded_blobs.is_empty() { 104 let blobs = self 105 .db 106 .handle_next_superseded_blobs(&self.deleted_blob_ids, 20) 107 .context(ks_err!("Trying to handle superseded blob."))?; 108 self.deleted_blob_ids = vec![]; 109 self.superseded_blobs = blobs; 110 } 111 112 if let Some(SupersededBlob { blob_id, blob, metadata }) = self.superseded_blobs.pop() { 113 // Add the next blob_id to the deleted blob ids list. So it will be 114 // removed from the database regardless of whether the following 115 // succeeds or not. 116 self.deleted_blob_ids.push(blob_id); 117 118 // If the key has a km_uuid we try to get the corresponding device 119 // and delete the key, unwrapping if necessary and possible. 120 // (At this time keys may get deleted without having the super encryption 121 // key in this case we can only delete the key from the database.) 122 if let Some(uuid) = metadata.km_uuid() { 123 let blob = self 124 .super_key 125 .read() 126 .unwrap() 127 .unwrap_key_if_required(&metadata, &blob) 128 .context(ks_err!("Trying to unwrap to-be-deleted blob.",))?; 129 (self.invalidate_key)(uuid, &blob).context(ks_err!("Trying to invalidate key."))?; 130 } 131 } 132 Ok(()) 133 } 134 135 /// Processes one key and then schedules another attempt until it runs out of blobs to delete. step(&mut self)136 fn step(&mut self) { 137 self.notified.store(0, Ordering::Relaxed); 138 if let Err(e) = self.process_one_key() { 139 log::error!("Error trying to delete blob entry. {:?}", e); 140 } 141 // Schedule the next step. This gives high priority requests a chance to interleave. 142 if !self.deleted_blob_ids.is_empty() { 143 if let Some(at) = self.async_task.upgrade() { 144 if let Ok(0) = 145 self.notified.compare_exchange(0, 1, Ordering::Relaxed, Ordering::Relaxed) 146 { 147 at.queue_lo(move |shelf| { 148 shelf.get_downcast_mut::<GcInternal>().unwrap().step() 149 }); 150 } 151 } 152 } 153 } 154 } 155