From 66b66ecf37e98d437f158d8a77afe6c0f0a374e0 Mon Sep 17 00:00:00 2001 From: Pierre-Louis Date: Mon, 27 Nov 2023 14:35:09 -0500 Subject: [PATCH 1/6] evm/kernel: add remove to linked list --- .../kernel_evm/kernel/src/linked_list.rs | 83 ++++++++++++++++++- 1 file changed, 82 insertions(+), 1 deletion(-) diff --git a/etherlink/kernel_evm/kernel/src/linked_list.rs b/etherlink/kernel_evm/kernel/src/linked_list.rs index ffd5bf1af600..170969c924c7 100644 --- a/etherlink/kernel_evm/kernel/src/linked_list.rs +++ b/etherlink/kernel_evm/kernel/src/linked_list.rs @@ -152,6 +152,13 @@ impl> Pointer { Ok(path) } + /// Path to the pointer + /// + /// This path is used when you want to read a pointer or to remove it. + fn path(&self, prefix: &impl Path) -> Result { + Self::pointer_path(&self.id, prefix) + } + /// Path to the data held by the pointer. fn data_path(&self, prefix: &impl Path) -> Result { let path = hex::encode(&self.id); @@ -168,7 +175,7 @@ impl> Pointer { /// Save the pointer in the durable storage fn save(&self, host: &mut impl Runtime, prefix: &impl Path) -> Result<()> { - storage::store_rlp(self, host, &Self::pointer_path(&self.id, prefix)?) + storage::store_rlp(self, host, &self.path(prefix)?) .context("cannot save pointer to storage") } } @@ -275,6 +282,80 @@ where let Some(pointer) = Pointer::read(host, &self.path, id)? else {return Ok(None)}; storage::read_optional_rlp(host, &pointer.data_path(&self.path)?) } + + /// Removes and returns the element at position index within the vector. + pub fn remove(&mut self, host: &mut impl Runtime, id: &Id) -> Result> { + // Check if the list is empty + let Some(LinkedListPointer { front, back }) = &self.pointers else {return Ok(None)}; + // Get the previous and the next pointer + let Some(pointer) = Pointer::read(host, &self.path, id)? else {return Ok(None)}; + let data_path = pointer.data_path(&self.path)?; + let pointer_path = pointer.path(&self.path)?; + let previous = match pointer.previous { + Some(previous) => Pointer::read(host, &self.path, &previous)?, + None => None, + }; + let next = match pointer.next { + Some(next) => Pointer::read(host, &self.path, &next)?, + None => None, + }; + + // retrieve the data + let data = storage::read_optional_rlp(host, &data_path)?; + // delete the pointer and the data + host.store_delete(&pointer_path)?; + host.store_delete(&data_path)?; + match (previous, next) { + // This case represents the list with only one element + (None, None) => { + // update the list pointers + self.pointers = None; + } + // The head of the list is being removed + (None, Some(next)) => { + let new_front = Pointer { + previous: None, // because it's the head + ..next + }; + // update the pointer + new_front.save(host, &self.path)?; + // update the list pointers + self.pointers = Some(LinkedListPointer { + front: new_front, + back: back.clone(), + }); + } + // The end of the list is being removed + (Some(previous), None) => { + let new_back = Pointer { + next: None, // because it's the end of the list + ..previous + }; + new_back.save(host, &self.path)?; + // update the list pointers + self.pointers = Some(LinkedListPointer { + front: front.clone(), + back: new_back, + }); + } + // Removes an element between two elements + (Some(previous), Some(next)) => { + let previous_id = previous.id.clone(); + let new_previous = Pointer { + next: Some(next.id.clone()), + ..previous + }; + let new_next = Pointer { + previous: Some(previous_id), + ..next + }; + new_previous.save(host, &self.path)?; + new_next.save(host, &self.path)?; + } + }; + self.save(host)?; + Ok(data) + } } #[cfg(test)] -- GitLab From 4e0f881d188660cbdef24b4ef94659937f5a4730 Mon Sep 17 00:00:00 2001 From: Pierre-Louis Date: Mon, 27 Nov 2023 15:42:59 -0500 Subject: [PATCH 2/6] evm/kernel: test remove element --- .../kernel_evm/kernel/src/linked_list.rs | 121 +++++++++++++++--- 1 file changed, 102 insertions(+), 19 deletions(-) diff --git a/etherlink/kernel_evm/kernel/src/linked_list.rs b/etherlink/kernel_evm/kernel/src/linked_list.rs index 170969c924c7..0a03c8cbffe8 100644 --- a/etherlink/kernel_evm/kernel/src/linked_list.rs +++ b/etherlink/kernel_evm/kernel/src/linked_list.rs @@ -365,6 +365,7 @@ mod tests { use rlp::{Decodable, DecoderError, Encodable}; use std::collections::HashMap; use tezos_ethereum::transaction::TRANSACTION_HASH_SIZE; + use tezos_smart_rollup_debug::Runtime; use tezos_smart_rollup_host::path::RefPath; use tezos_smart_rollup_mock::MockHost; @@ -393,6 +394,18 @@ mod tests { } } + fn assert_length(host: &MockHost, list: &LinkedList, expected_len: u64) { + // Both the linked list pointers and the element pointers lies under + // the `list.path`. + let keys = host.store_count_subkeys(&list.path).unwrap_or(0u64); + // Removes the linked list pointers to compute the actual length. + let actual_length = keys.saturating_sub(1u64); + assert_eq!( + expected_len, actual_length, + "Unexpected length for the list" + ) + } + #[test] fn test_empty() { let host = MockHost::default(); @@ -431,6 +444,39 @@ mod tests { assert_eq!(read, elt); } + #[test] + fn test_remove() { + let mut host = MockHost::default(); + let path = RefPath::assert_from(b"/list"); + let mut list = LinkedList::new(&path, &host).expect("list should be created"); + let id = Hash([0x0; TRANSACTION_HASH_SIZE]); + let elt = 0x32_u8; + + assert_length(&host, &list, 0u64); + list.push(&mut host, &id, &elt) + .expect("storage should work"); + assert_length(&host, &list, 1u64); + let _: Option = list.remove(&mut host, &id).expect("storage should work"); + assert_length(&host, &list, 0u64); + + let read: Option = list.get(&host, &id).expect("storage should work"); + + assert!(read.is_none()) + } + + #[test] + fn test_remove_nothing() { + let mut host = MockHost::default(); + let path = RefPath::assert_from(b"/list"); + let mut list = LinkedList::new(&path, &host).expect("list should be created"); + let id = Hash([0x0; TRANSACTION_HASH_SIZE]); + + let removed: Option = + list.remove(&mut host, &id).expect("storage should work"); + + assert!(removed.is_none()) + } + fn fill_list( elements: &HashMap<[u8; TRANSACTION_HASH_SIZE], u8>, ) -> (MockHost, LinkedList) { @@ -446,27 +492,60 @@ mod tests { } proptest! { - #[test] - fn test_pushed_elements_are_present(elements: HashMap<[u8; TRANSACTION_HASH_SIZE], u8>) { - let (host, list) = fill_list(&elements); - for (id, elt) in & elements { - let read: u8 = list.get(&host, &Hash(*id)).expect("storage should work").expect("element should be present"); - assert_eq!(elt, &read) + #[test] + fn test_pushed_elements_are_present(elements: HashMap<[u8; TRANSACTION_HASH_SIZE], u8>) { + let (host, list) = fill_list(&elements); + for (id, elt) in & elements { + let read: u8 = list.get(&host, &Hash(*id)).expect("storage should work").expect("element should be present"); + assert_eq!(elt, &read) + } } - } - #[test] - fn test_push_element_create_non_empty_list(elements: HashMap<[u8; TRANSACTION_HASH_SIZE], u8>) { - let mut host = MockHost::default(); - let path = RefPath::assert_from(b"/list"); - let mut list = LinkedList::new(&path, &host).expect("list should be created"); - assert!(list.is_empty()); - for (id, elt) in elements { - list.push(&mut host, &Hash(id), &elt).expect("storage should work"); - assert!(!list.is_empty()) + #[test] + fn test_push_element_create_non_empty_list(elements: HashMap<[u8; TRANSACTION_HASH_SIZE], u8>) { + let mut host = MockHost::default(); + let path = RefPath::assert_from(b"/list"); + let mut list = LinkedList::new(&path, &host).expect("list should be created"); + assert!(list.is_empty()); + for (id, elt) in elements { + list.push(&mut host, &Hash(id), &elt).expect("storage should work"); + assert!(!list.is_empty()) + } + } + + #[test] + fn test_remove_from_empty_creates_empty_list(elements: Vec<[u8; TRANSACTION_HASH_SIZE]>) { + let mut host = MockHost::default(); + let path = RefPath::assert_from(b"/list"); + let mut list = LinkedList::new(&path, &host).expect("list should be created"); + assert!(list.is_empty()); + for id in elements { + let _: Option = list.remove(&mut host, &Hash(id)).expect("storage to work"); + } + assert!(list.is_empty()); + } + + #[test] + fn test_remove_returns_the_appropriate_element(elements: HashMap<[u8; TRANSACTION_HASH_SIZE], u8>) { + let (mut host, mut list) = fill_list(&elements); + let mut length : u64 = elements.len().try_into().unwrap(); + for (id, elt) in &elements { + let removed: u8 = list.remove(&mut host, &Hash(*id)).expect("storage should work").expect("element should be present"); + length -= 1; + assert_length(&host, &list, length); + assert_eq!(elt, &removed) + } + } + + #[test] + fn test_remove_everything_creates_the_empty_list(elements: HashMap<[u8; TRANSACTION_HASH_SIZE], u8>) { + let (mut host, mut list) = fill_list(&elements); + for (id, _) in elements { + let _: u8 = list.remove(&mut host, &Hash(id)).expect("storage should work").expect("element should be present"); + } + assert!(list.is_empty()) } - } #[test] fn test_list_is_kept_between_reboots(elements: HashMap<[u8; TRANSACTION_HASH_SIZE], u8>) { @@ -474,12 +553,16 @@ mod tests { let path = RefPath::assert_from(b"/list"); for (id, elt) in &elements { let mut list = LinkedList::new(&path, &host).expect("list should be created"); - list.push(&mut host, &Hash(*id), elt).expect("storage should work"); + list.push(&mut host, &Hash(*id), elt) + .expect("storage should work"); assert!(!list.is_empty()) } for (id, elt) in &elements { let list = LinkedList::new(&path, &host).expect("list should be created"); - let read: u8 = list.get(&host, &Hash(*id)).expect("storage should work").expect("element should be present"); + let read: u8 = list + .get(&host, &Hash(*id)) + .expect("storage should work") + .expect("element should be present"); assert_eq!(elt, &read); } } -- GitLab From 3ea8e295ede715f19f3a9688405218f3c91406ec Mon Sep 17 00:00:00 2001 From: Valentin Chaboche Date: Tue, 2 Jan 2024 16:38:55 +0100 Subject: [PATCH 3/6] EVM/Kernel: linked list get is actually find --- etherlink/kernel_evm/kernel/src/linked_list.rs | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-) diff --git a/etherlink/kernel_evm/kernel/src/linked_list.rs b/etherlink/kernel_evm/kernel/src/linked_list.rs index 0a03c8cbffe8..868f563c4f55 100644 --- a/etherlink/kernel_evm/kernel/src/linked_list.rs +++ b/etherlink/kernel_evm/kernel/src/linked_list.rs @@ -278,7 +278,7 @@ where /// Returns an element at a given index. /// /// Returns None if the element is not present - pub fn get(&self, host: &impl Runtime, id: &Id) -> Result> { + pub fn find(&self, host: &impl Runtime, id: &Id) -> Result> { let Some(pointer) = Pointer::read(host, &self.path, id)? else {return Ok(None)}; storage::read_optional_rlp(host, &pointer.data_path(&self.path)?) } @@ -416,12 +416,12 @@ mod tests { } #[test] - fn test_get_returns_none_when_empty() { + fn test_find_returns_none_when_empty() { let host = MockHost::default(); let path = RefPath::assert_from(b"/list"); let list = LinkedList::new(&path, &host).expect("list should be created"); let hash = Hash([0; TRANSACTION_HASH_SIZE]); - let read: Option = list.get(&host, &hash).expect("storage should work"); + let read: Option = list.find(&host, &hash).expect("storage should work"); assert!(read.is_none()) } @@ -437,7 +437,7 @@ mod tests { .expect("storage should work"); let read: u8 = list - .get(&host, &id) + .find(&host, &id) .expect("storage should work") .expect("element should be present"); @@ -459,7 +459,7 @@ mod tests { let _: Option = list.remove(&mut host, &id).expect("storage should work"); assert_length(&host, &list, 0u64); - let read: Option = list.get(&host, &id).expect("storage should work"); + let read: Option = list.find(&host, &id).expect("storage should work"); assert!(read.is_none()) } @@ -496,7 +496,7 @@ mod tests { fn test_pushed_elements_are_present(elements: HashMap<[u8; TRANSACTION_HASH_SIZE], u8>) { let (host, list) = fill_list(&elements); for (id, elt) in & elements { - let read: u8 = list.get(&host, &Hash(*id)).expect("storage should work").expect("element should be present"); + let read: u8 = list.find(&host, &Hash(*id)).expect("storage should work").expect("element should be present"); assert_eq!(elt, &read) } } @@ -560,7 +560,7 @@ mod tests { for (id, elt) in &elements { let list = LinkedList::new(&path, &host).expect("list should be created"); let read: u8 = list - .get(&host, &Hash(*id)) + .find(&host, &Hash(*id)) .expect("storage should work") .expect("element should be present"); assert_eq!(elt, &read); -- GitLab From 6db87be6744c6f68f1a58bfae52285b49c755d47 Mon Sep 17 00:00:00 2001 From: Valentin Chaboche Date: Tue, 2 Jan 2024 17:01:18 +0100 Subject: [PATCH 4/6] EVM/Kernel: limit number of proptests It is 256 by default, it takes too long to execute everything because of these tests. --- etherlink/kernel_evm/kernel/src/linked_list.rs | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/etherlink/kernel_evm/kernel/src/linked_list.rs b/etherlink/kernel_evm/kernel/src/linked_list.rs index 868f563c4f55..9623786e41c7 100644 --- a/etherlink/kernel_evm/kernel/src/linked_list.rs +++ b/etherlink/kernel_evm/kernel/src/linked_list.rs @@ -361,6 +361,7 @@ where #[cfg(test)] mod tests { use super::LinkedList; + use proptest::prelude::*; use proptest::proptest; use rlp::{Decodable, DecoderError, Encodable}; use std::collections::HashMap; @@ -492,6 +493,9 @@ mod tests { } proptest! { + + #![proptest_config(ProptestConfig::with_cases(50))] + #[test] fn test_pushed_elements_are_present(elements: HashMap<[u8; TRANSACTION_HASH_SIZE], u8>) { let (host, list) = fill_list(&elements); -- GitLab From 8aedfd0361eaa143e15daafd629fd1e65eb644fd Mon Sep 17 00:00:00 2001 From: Valentin Chaboche Date: Tue, 2 Jan 2024 17:06:07 +0100 Subject: [PATCH 5/6] EVM/Kernel: implement save/get data for pointers --- .../kernel_evm/kernel/src/linked_list.rs | 33 ++++++++++++++----- 1 file changed, 25 insertions(+), 8 deletions(-) diff --git a/etherlink/kernel_evm/kernel/src/linked_list.rs b/etherlink/kernel_evm/kernel/src/linked_list.rs index 9623786e41c7..eb711a8f1457 100644 --- a/etherlink/kernel_evm/kernel/src/linked_list.rs +++ b/etherlink/kernel_evm/kernel/src/linked_list.rs @@ -168,6 +168,25 @@ impl> Pointer { Ok(path) } + fn save_data( + &self, + host: &mut impl Runtime, + prefix: &impl Path, + data: &impl Encodable, + ) -> Result<()> { + let path = self.data_path(prefix)?; + storage::store_rlp(data, host, &path).context("cannot save the pointer's data") + } + + fn get_data( + &self, + host: &impl Runtime, + prefix: &impl Path, + ) -> Result { + let path = self.data_path(prefix)?; + storage::read_rlp(host, &path).context("cannot read the pointer's data") + } + /// Load the pointer from the durable storage fn read(host: &impl Runtime, prefix: &impl Path, id: &Id) -> Result> { storage::read_optional_rlp(host, &Self::pointer_path(id, prefix)?) @@ -245,8 +264,7 @@ where penultimate.save(host, &self.path)?; back.save(host, &self.path)?; // And the save the data - let data_path = back.data_path(&self.path)?; - storage::store_rlp(elt, host, &data_path)?; + back.save_data(host, &self.path, elt)?; // update the back pointer of the list self.pointers = Some(LinkedListPointer { front: front.clone(), @@ -263,8 +281,7 @@ where }; // Saves the pointer and its data back.save(host, &self.path)?; - let data_path = back.data_path(&self.path)?; - storage::store_rlp(elt, host, &data_path)?; + back.save_data(host, &self.path, elt)?; // update the front and back pointers of the list self.pointers = Some(LinkedListPointer { front: back.clone(), @@ -292,16 +309,16 @@ where let data_path = pointer.data_path(&self.path)?; let pointer_path = pointer.path(&self.path)?; let previous = match pointer.previous { - Some(previous) => Pointer::read(host, &self.path, &previous)?, + Some(ref previous) => Pointer::read(host, &self.path, previous)?, None => None, }; let next = match pointer.next { - Some(next) => Pointer::read(host, &self.path, &next)?, + Some(ref next) => Pointer::read(host, &self.path, next)?, None => None, }; // retrieve the data - let data = storage::read_optional_rlp(host, &data_path)?; + let data = pointer.get_data(host, &self.path)?; // delete the pointer and the data host.store_delete(&pointer_path)?; host.store_delete(&data_path)?; @@ -354,7 +371,7 @@ where } }; self.save(host)?; - Ok(data) + Ok(Some(data)) } } -- GitLab From ec7c33572f0bcb6cbad6ca667afee013bb20dd95 Mon Sep 17 00:00:00 2001 From: Valentin Chaboche Date: Tue, 2 Jan 2024 17:10:56 +0100 Subject: [PATCH 6/6] EVM/Kernel: implement remove_with_data for pointers --- .../kernel_evm/kernel/src/linked_list.rs | 19 +++++++++++++++---- 1 file changed, 15 insertions(+), 4 deletions(-) diff --git a/etherlink/kernel_evm/kernel/src/linked_list.rs b/etherlink/kernel_evm/kernel/src/linked_list.rs index eb711a8f1457..61f1c59e5dd8 100644 --- a/etherlink/kernel_evm/kernel/src/linked_list.rs +++ b/etherlink/kernel_evm/kernel/src/linked_list.rs @@ -197,6 +197,20 @@ impl> Pointer { storage::store_rlp(self, host, &self.path(prefix)?) .context("cannot save pointer to storage") } + + /// Removes the pointer and its data frm the durable storage. + fn remove_with_data( + &self, + host: &mut impl Runtime, + prefix: &impl Path, + ) -> Result<()> { + let path = hex::encode(&self.id); + let path: Vec = format!("/{}", path).into(); + let path = OwnedPath::try_from(path)?; + let path = concat(prefix, &path)?; + host.store_delete(&path) + .context("cannot remove the pointer") + } } #[allow(dead_code)] @@ -306,8 +320,6 @@ where let Some(LinkedListPointer { front, back }) = &self.pointers else {return Ok(None)}; // Get the previous and the next pointer let Some(pointer) = Pointer::read(host, &self.path, id)? else {return Ok(None)}; - let data_path = pointer.data_path(&self.path)?; - let pointer_path = pointer.path(&self.path)?; let previous = match pointer.previous { Some(ref previous) => Pointer::read(host, &self.path, previous)?, None => None, @@ -320,8 +332,7 @@ where // retrieve the data let data = pointer.get_data(host, &self.path)?; // delete the pointer and the data - host.store_delete(&pointer_path)?; - host.store_delete(&data_path)?; + pointer.remove_with_data(host, &self.path)?; match (previous, next) { // This case represents the list with only one element (None, None) => { -- GitLab