Repository: stellar/rs-soroban-env
Pull request #690 (2023-02-17 04:34:19)

Reform metering for value cloning and memory allocation
### What

Resolves https://github.com/stellar/rs-soroban-env/issues/604 and https://github.com/stellar/rs-soroban-env/issues/680.

This PR reforms `metered_clone`.
- Splits memory allocation from shallow copying
- Define the "shallow size" of `MeteredClone` types. 

A `metered_clone` consist of shallow copying of the type's memory footprint (for a `Vec` it's 24), plus recursively (deep) cloning any of the substructures. 
A `HostMemAlloc` charge occurs only when memory is allocated. I.e. types involving `alloc` -- `Box`, `Vec`, `Rc` etc.
The shallow copying of a type is charged the amount `ELT_SIZE` defined by the implementer, and there is a runtime check to ensure that amount is the upper bound of the actual memory size of the type `mem::size_of<T>`.
Adds a test in `budget_metering.rs` to demonstrate the metered cloning of a deep structure. 


### Why

[TODO: Why this change is being made. Include any context required to understand the why.]

### Known limitations

[TODO or N/A]


jayz22: @graydon I have reformed it once again after our discussion. All the previous double-charging of shallow copies should be eliminated. I believe this is ready for merge. Please take another look. 

Patch:
diff --git a/soroban-env-host/src/budget.rs b/soroban-env-host/src/budget.rs
index 4518ed29..abe18810 100644
--- a/soroban-env-host/src/budget.rs
+++ b/soroban-env-host/src/budget.rs
@@ -95,6 +95,8 @@ pub enum CostType {
     // here for exploring calibration, not a long-term cost we surface
     // separately from signature verification.
     EdwardsPointCurve25519ScalarMul = 35,
+    HostMemAlloc = 36,
+    HostMemCpy = 37,
 }
 
 // TODO: add XDR support for iterating over all the elements of an enum
@@ -137,6 +139,8 @@ impl CostType {
             CostType::BytesCmp,
             CostType::ChargeBudget,
             CostType::EdwardsPointCurve25519ScalarMul,
+            CostType::HostMemAlloc,
+            CostType::HostMemCpy,
         ];
         VARIANTS.iter()
     }
@@ -497,6 +501,7 @@ impl Default for BudgetImpl {
                 CostType::BytesCmp => cpu.lin_param = 1,
                 CostType::ChargeBudget => cpu.const_param = 50,
                 CostType::EdwardsPointCurve25519ScalarMul => cpu.const_param = 10,
+                CostType::HostMemAlloc | CostType::HostMemCpy => cpu.lin_param = 1,
             }
 
             let mem = b.mem_bytes.get_cost_model_mut(*ct);
@@ -532,6 +537,7 @@ impl Default for BudgetImpl {
                 CostType::BytesCmp => (),
                 CostType::ChargeBudget => (),
                 CostType::EdwardsPointCurve25519ScalarMul => mem.const_param = 1,
+                CostType::HostMemAlloc | CostType::HostMemCpy => mem.lin_param = 1,
             }
         }
 
diff --git a/soroban-env-host/src/events/internal.rs b/soroban-env-host/src/events/internal.rs
index fcd8aa1e..70031476 100644
--- a/soroban-env-host/src/events/internal.rs
+++ b/soroban-env-host/src/events/internal.rs
@@ -1,7 +1,6 @@
 use super::{DebugEvent, Events, HostEvent};
 use crate::{
     budget::{AsBudget, Budget},
-    host::metered_clone::MeteredClone,
     xdr,
     xdr::ScObject,
     Host, HostError, MeteredVector, Object, RawVal,
@@ -49,8 +48,6 @@ pub(crate) enum InternalEvent {
     None,
 }
 
-impl MeteredClone for InternalEvent {}
-
 /// The events buffer. Stores `InternalEvent`s in the chronological order.
 #[derive(Clone, Default)]
 pub(crate) struct InternalEventsBuffer {
diff --git a/soroban-env-host/src/host.rs b/soroban-env-host/src/host.rs
index 1faad31f..800018cb 100644
--- a/soroban-env-host/src/host.rs
+++ b/soroban-env-host/src/host.rs
@@ -2290,7 +2290,7 @@ impl VmCallerEnv for Host {
                 #[cfg(any(test, feature = "testutils"))]
                 Frame::TestContract(tc) => get_host_val_tuple(&tc.id, &tc.func)?,
             };
-            let inner = MeteredVector::from_array(vals, self.as_budget())?;
+            let inner = MeteredVector::from_array(&vals, self.as_budget())?;
             outer.push(self.add_host_object(inner)?.into());
         }
         Ok(self.add_host_object(HostVec::from_vec(outer)?)?.into())
diff --git a/soroban-env-host/src/host/metered_clone.rs b/soroban-env-host/src/host/metered_clone.rs
index e3f620ac..6d73aef4 100644
--- a/soroban-env-host/src/host/metered_clone.rs
+++ b/soroban-env-host/src/host/metered_clone.rs
@@ -1,31 +1,43 @@
-use std::rc::Rc;
+use std::{mem, rc::Rc};
 
 use soroban_env_common::{
-    xdr::{BytesM, LedgerEntry, LedgerKey, ScAddress, ScMap, ScObject, ScVal},
+    xdr::{
+        BytesM, ContractEvent, ContractEventBody, LedgerEntry, LedgerKey, ScAddress, ScMap,
+        ScMapEntry, ScObject, ScVal,
+    },
     RawVal,
 };
 
 use crate::{
     budget::{Budget, CostType},
+    events::{DebugArg, DebugEvent, HostEvent, InternalContractEvent, InternalEvent},
     host::Events,
     storage::AccessType,
     xdr::{AccountId, Hash, ScContractCode, ScVec, Uint256},
     HostError,
 };
 
-// Charge for an N-element "shallow copy" of some type, not cloning any
-// substructure. In a better world we would multiply this by size_of<Self> but
-// that's not guaranteed to be stable. Also this has a fairly serious level of
-// inaccuracy since we call the same charge for any shallow type, whether it's a
-// simple byte-copy or a sequence of Rc<>.clone calls (each of which bumps a
-// refcount -- shallow but not as cheap as memcpy).
-//
-// TODO: this is correct for CPU-cost but not memory-cost, since there's no heap
-// allocation implied by a shallow clone. We should (maybe) split BytesClone
-// into ByteCopy (the CPU byte-copying part) and HeapAlloc (the heap-allocating
-// part). See https://github.com/stellar/rs-soroban-env/issues/604.
-fn charge_shallow_copy(n_elts: usize, budget: &Budget) -> Result<(), HostError> {
-    budget.charge(CostType::BytesClone, n_elts as u64)
+// Charge for an N-element "shallow copy" of some type, not cloning any substructure. The charge
+// unit is number of elements `n_elts` multiplied by a declared size of each element. In a better
+// world we would multiply by `size_of<Self>` instead but that's not guaranteed to be stable, which
+// might cause metering to differ across compilations, causing problems in concensus and replay.
+fn charge_shallow_copy<T: MeteredClone>(n_elts: u64, budget: &Budget) -> Result<(), HostError> {
+    // Ideally we would want a static assertion. However, it does not work due to rust restrictions
+    // (e.g. see https://github.com/rust-lang/rust/issues/57775). Here we make a runtime assertion
+    // that the type's size is below its promised element size for budget charging. This assertion
+    // only happens in debug build. In optimized build, not satisfying the asserted condition just
+    // means an underestimation of the cost.
+    debug_assert!(mem::size_of::<T>() as u64 <= T::ELT_SIZE);
+    budget.charge(CostType::HostMemCpy, n_elts.saturating_mul(T::ELT_SIZE))
+}
+
+// Let it be a free function instead of a trait because charge_heap_alloc maybe called elsewhere,
+// not just metered clone, e.g. Box::<T>::new().
+fn charge_heap_alloc<T: MeteredClone>(n_elts: u64, budget: &Budget) -> Result<(), HostError> {
+    // Here we make a runtime assertion that the type's size is below its promised element size for
+    // budget charging.
+    debug_assert!(mem::size_of::<T>() as u64 <= T::ELT_SIZE);
+    budget.charge(CostType::HostMemAlloc, n_elts.saturating_mul(T::ELT_SIZE))
 }
 
 pub trait MeteredClone: Clone {
@@ -35,70 +47,132 @@ pub trait MeteredClone: Clone {
     // `charge_for_clone` (correctly charging for cloning the substructure).
     const IS_SHALLOW: bool = true;
 
-    // Called to clone a single element of type Self, a default implementation
-    // that charges for a 1-unit memcpy and is _only_ appropriate when Self is
-    // a shallow type (with no substructure). If you override Self::IS_SHALLOW
-    // and set it to false, you should override this method also (it will actually
-    // panic if you don't).
-    fn charge_for_clone(&self, budget: &Budget) -> Result<(), HostError> {
+    // Size (bytes) of a single element. This value determines the input for budget charging.
+    // It should be the upperbound (across various compilations and platforms) of the actual type's
+    // size. Implementer of the trait needs to decide this value based on Rust's guideline on type
+    // layout: https://doc.rust-lang.org/reference/type-layout.html
+    const ELT_SIZE: u64;
+
+    // Called to clone the substructures of Self. The default implementation is a no-op and is
+    // _only_ appropriate when Self is a shallow type (with no substructure). If you override
+    // Self::IS_SHALLOW and set it to false, you should override this method also (it will actually
+    // panic if you don't). This charge does not include shallow copying of `Self` because that
+    // should be taken care of by the caller beforehand, e.g. in `metered_clone`.
+    fn charge_for_substructure(&self, budget: &Budget) -> Result<(), HostError> {
         assert!(Self::IS_SHALLOW);
-        charge_shallow_copy(1, budget)
+        Ok(())
     }
 
-    // Called when cloning a slice of elements of type Self. Can be more
-    // efficient than cloning element-by-element when Self::IS_SHALLOW, because
-    // it's acceptable to charge once for the whole slice -- a single charge for
-    // the cost of a memcpy -- followed by copying the slice via memcpy (or
-    // something similar to a memcpy, eg. cloning a bunch of Rc<>s). If
-    // Self::IS_SHALLOW is false, this method will do element-wise charging,
-    // assuming it is paired with element-wise cloning.
-    fn charge_for_clones(clones: &[Self], budget: &Budget) -> Result<(), HostError> {
+    // Called when cloning the substructures of a slice of Self. When Self::IS_SHALLOW, this is a
+    // no-op. If Self::IS_SHALLOW is false, this method will do element-wise charging for
+    // substructure, assuming it is paired with element-wise cloning.
+    fn bulk_charge_for_substructure(clones: &[Self], budget: &Budget) -> Result<(), HostError> {
         if Self::IS_SHALLOW {
-            // If we're shallow, we're allowed to batch our charges.
-            charge_shallow_copy(clones.len(), budget)
+            // If we're shallow, just return.
+            Ok(())
         } else {
             for elt in clones {
-                elt.charge_for_clone(budget)?;
+                elt.charge_for_substructure(budget)?;
             }
             Ok(())
         }
     }
-    // Composite helper that just does a charge_for_clone followed by a clone. Some types
-    // might choose to do these two steps separately (eg. if they have a separate nontrivial and non-metered clone).
+
+    // Convenience method for charging for a deep clone knowing the type is not shallow.
+    fn charge_deep_clone(&self, budget: &Budget) -> Result<(), HostError> {
+        debug_assert!(!Self::IS_SHALLOW);
+        charge_shallow_copy::<Self>(1, budget)?;
+        self.charge_for_substructure(budget)
+    }
+
+    // Composite helper handles metering before clone. It first charges for the shallow footprint
+    // of the type, followed by charging the substructure clone. The reason
+    // `charge_for_substructure` does not include shallow copying of `Self` is because it is taken
+    // care of here. Typically overriding `IS_SHALLOW` and `charge_for_substructure` should
+    // propertly take care of custom non-trivial cloning. Thus this method should not need to be
+    // overriden.
     fn metered_clone(&self, budget: &Budget) -> Result<Self, HostError> {
-        self.charge_for_clone(budget)?;
+        charge_shallow_copy::<Self>(1, budget)?;
+        self.charge_for_substructure(budget)?;
         Ok(self.clone())
     }
 }
 
-impl<T> MeteredClone for Rc<T> {}
-impl MeteredClone for Hash {}
-impl MeteredClone for RawVal {}
-impl MeteredClone for AccessType {}
-impl MeteredClone for AccountId {}
-impl MeteredClone for ScContractCode {}
-impl MeteredClone for Uint256 {}
-impl MeteredClone for ScAddress {}
-impl<const N: usize> MeteredClone for [u8; N] {}
+macro_rules! impl_metered_clone_for_shallow_types {
+    ($name:ident, $size:literal) => {
+        impl MeteredClone for $name {
+            const ELT_SIZE: u64 = $size;
+        }
+    };
+}
+
+impl_metered_clone_for_shallow_types!(u8, 1);
+impl_metered_clone_for_shallow_types!(u32, 4);
+impl_metered_clone_for_shallow_types!(i32, 4);
+impl_metered_clone_for_shallow_types!(u64, 8);
+impl_metered_clone_for_shallow_types!(i64, 8);
+impl_metered_clone_for_shallow_types!(Hash, 32);
+impl_metered_clone_for_shallow_types!(RawVal, 8);
+impl_metered_clone_for_shallow_types!(AccessType, 1);
+impl_metered_clone_for_shallow_types!(AccountId, 32);
+impl_metered_clone_for_shallow_types!(ScContractCode, 33);
+impl_metered_clone_for_shallow_types!(Uint256, 32);
+impl_metered_clone_for_shallow_types!(ScAddress, 33);
+impl_metered_clone_for_shallow_types!(DebugArg, 16);
+impl_metered_clone_for_shallow_types!(InternalContractEvent, 40);
+
+// Rc is an exception, nothing is being cloned. We approximate ref counter bump with the cost of
+// cloning 16 bytes. Also it can't be below 16 since that's the size of an `Rc` structure.
+impl<T> MeteredClone for Rc<T> {
+    const ELT_SIZE: u64 = 16;
+}
+
+// Cloning a slice only clones the reference without deep cloning its contents.
+impl<T> MeteredClone for &[T] {
+    const ELT_SIZE: u64 = 16;
+}
+
+impl<K, V> MeteredClone for (K, V)
+where
+    K: MeteredClone,
+    V: MeteredClone,
+{
+    const ELT_SIZE: u64 = <K as MeteredClone>::ELT_SIZE + <V as MeteredClone>::ELT_SIZE;
+}
 
 // TODO: this isn't correct: these two have substructure to account for;
 // probably they should never be cloned in the middle of a contract at all (the
 // storage maps are Rc<> now) but changing that means changing the storage
 // interface. See https://github.com/stellar/rs-soroban-env/issues/603
-impl MeteredClone for LedgerKey {}
-impl MeteredClone for LedgerEntry {}
+impl MeteredClone for LedgerKey {
+    const ELT_SIZE: u64 = 80;
+}
+impl MeteredClone for LedgerEntry {
+    const ELT_SIZE: u64 = 264;
+}
+
+impl<C: MeteredClone, const N: usize> MeteredClone for [C; N] {
+    const IS_SHALLOW: bool = C::IS_SHALLOW;
+
+    const ELT_SIZE: u64 = C::ELT_SIZE.saturating_mul(N as u64);
+
+    fn charge_for_substructure(&self, budget: &Budget) -> Result<(), HostError> {
+        C::bulk_charge_for_substructure(self.as_slice(), budget)
+    }
+}
 
 impl MeteredClone for ScVal {
     const IS_SHALLOW: bool = false;
 
-    fn charge_for_clone(&self, budget: &Budget) -> Result<(), HostError> {
-        charge_shallow_copy(1, budget)?;
+    const ELT_SIZE: u64 = 40;
+
+    fn charge_for_substructure(&self, budget: &Budget) -> Result<(), HostError> {
         match self {
             ScVal::Object(Some(obj)) => {
                 match obj {
-                    ScObject::Vec(v) => ScVec::charge_for_clone(v, budget),
-                    ScObject::Map(m) => ScMap::charge_for_clone(m, budget),
-                    ScObject::Bytes(b) => BytesM::charge_for_clone(b, budget),
+                    ScObject::Vec(v) => ScVec::charge_for_substructure(v, budget),
+                    ScObject::Map(m) => ScMap::charge_for_substructure(m, budget),
+                    ScObject::Bytes(b) => BytesM::charge_for_substructure(b, budget),
                     // Everything else was handled by the memcpy above.
                     ScObject::U64(_)
                     | ScObject::I64(_)
@@ -121,82 +195,246 @@ impl MeteredClone for ScVal {
     }
 }
 
-impl MeteredClone for ScVec {
+impl MeteredClone for ScMapEntry {
     const IS_SHALLOW: bool = false;
-    fn charge_for_clone(&self, budget: &Budget) -> Result<(), HostError> {
-        for elt in self.0.iter() {
-            elt.charge_for_clone(budget)?
-        }
-        Ok(())
+
+    const ELT_SIZE: u64 = 80;
+
+    fn charge_for_substructure(&self, budget: &Budget) -> Result<(), HostError> {
+        self.key.charge_for_substructure(budget)?;
+        self.val.charge_for_substructure(budget)
     }
 }
 
-impl MeteredClone for ScMap {
+impl MeteredClone for ScVec {
     const IS_SHALLOW: bool = false;
-    fn charge_for_clone(&self, budget: &Budget) -> Result<(), HostError> {
-        for elt in self.0.iter() {
-            elt.key.charge_for_clone(budget)?;
-            elt.val.charge_for_clone(budget)?;
-        }
-        Ok(())
+
+    const ELT_SIZE: u64 = 24;
+
+    fn charge_for_substructure(&self, budget: &Budget) -> Result<(), HostError> {
+        self.0.charge_for_substructure(budget) // self.0 will be deref'ed into Vec
     }
 }
 
-impl<const C: u32> MeteredClone for BytesM<C> {
+impl MeteredClone for ScMap {
     const IS_SHALLOW: bool = false;
 
-    fn charge_for_clone(&self, budget: &Budget) -> Result<(), HostError> {
-        charge_shallow_copy(1, budget)?;
-        budget.charge(CostType::BytesClone, self.len() as u64)
+    const ELT_SIZE: u64 = 24;
+
+    fn charge_for_substructure(&self, budget: &Budget) -> Result<(), HostError> {
+        self.0.charge_for_substructure(budget) // self.0 will be deref'ed into Vec
     }
 }
 
-impl MeteredClone for Vec<u8> {
+impl<const C: u32> MeteredClone for BytesM<C> {
     const IS_SHALLOW: bool = false;
 
-    fn charge_for_clone(&self, budget: &Budget) -> Result<(), HostError> {
-        charge_shallow_copy(1, budget)?;
-        budget.charge(CostType::BytesClone, self.len() as u64)
+    const ELT_SIZE: u64 = 24;
+
+    fn charge_for_substructure(&self, budget: &Budget) -> Result<(), HostError> {
+        <Self as AsRef<Vec<u8>>>::as_ref(self).charge_for_substructure(budget)
     }
 }
 
 impl<C: MeteredClone> MeteredClone for Vec<C> {
     const IS_SHALLOW: bool = false;
-    fn metered_clone(&self, budget: &Budget) -> Result<Self, HostError> {
-        if C::IS_SHALLOW {
-            // Shallow types we can batch-up our charging for.
-            budget.charge(CostType::BytesClone, self.len() as u64)?;
-            Ok(self.clone())
-        } else {
-            self.iter().map(|elt| elt.metered_clone(budget)).collect()
-        }
+
+    const ELT_SIZE: u64 = 24;
+
+    fn charge_for_substructure(&self, budget: &Budget) -> Result<(), HostError> {
+        // first take care of Vec clone, which involves allocating memory and shallowly cloning the
+        // data type into it, then deep clone any substructure.
+        charge_heap_alloc::<C>(self.len() as u64, budget)?;
+        charge_shallow_copy::<C>(self.len() as u64, budget)?;
+        C::bulk_charge_for_substructure(self.as_slice(), budget)?;
+        Ok(())
     }
 }
 
 impl<C: MeteredClone> MeteredClone for Box<C> {
     const IS_SHALLOW: bool = false;
 
-    fn metered_clone(&self, budget: &Budget) -> Result<Self, HostError> {
+    const ELT_SIZE: u64 = 8;
+
+    fn charge_for_substructure(&self, budget: &Budget) -> Result<(), HostError> {
+        // first take care of the Box clone: allocating memory and shallow cloning of data type.
+        charge_heap_alloc::<C>(1, budget)?;
+        charge_shallow_copy::<C>(1, budget)?;
+        // then take care of any substructure clone (recursively)
         let inner: &C = &**self;
-        Ok(Box::new(inner.metered_clone(budget)?))
+        inner.charge_for_substructure(budget)
     }
 }
 
 impl<C: MeteredClone> MeteredClone for Option<C> {
     const IS_SHALLOW: bool = C::IS_SHALLOW;
 
-    fn metered_clone(&self, budget: &Budget) -> Result<Self, HostError> {
+    // Size of C plus an 8 byte alignment overhead. If we need to handle types with larger
+    // alignment size, we need to increase the overhead.
+    const ELT_SIZE: u64 = C::ELT_SIZE + 8;
+
+    fn charge_for_substructure(&self, budget: &Budget) -> Result<(), HostError> {
+        match self {
+            Some(elt) => elt.charge_for_substructure(budget),
+            None => Ok(()),
+        }
+    }
+}
+
+impl MeteredClone for DebugEvent {
+    const IS_SHALLOW: bool = false;
+
+    const ELT_SIZE: u64 = 80;
+
+    fn charge_for_substructure(&self, budget: &Budget) -> Result<(), HostError> {
+        if self.args.is_heap() {
+            // equivalent to charging for a `Vec` clone except we already know there is no
+            // substructure. `TinyVec` doesn't let us retrieve the `Vec` directly.
+            charge_heap_alloc::<Vec<DebugArg>>(self.args.len() as u64, budget)?;
+            charge_shallow_copy::<Vec<DebugArg>>(self.args.len() as u64, budget)
+        } else {
+            // equivalent to charging for a slice clone.
+            // Here the size is limited to the `tiny_vec`'s limit we defined.
+            DebugArg::bulk_charge_for_substructure(self.args.as_slice(), budget)
+        }
+    }
+}
+
+impl MeteredClone for ContractEvent {
+    const IS_SHALLOW: bool = false;
+
+    const ELT_SIZE: u64 = 104;
+
+    fn charge_for_substructure(&self, budget: &Budget) -> Result<(), HostError> {
+        let ContractEventBody::V0(event) = &self.body;
+        event.topics.charge_for_substructure(budget)?;
+        event.data.charge_for_substructure(budget)
+    }
+}
+
+impl MeteredClone for HostEvent {
+    const IS_SHALLOW: bool = false;
+
+    const ELT_SIZE: u64 = 112;
+
+    fn charge_for_substructure(&self, budget: &Budget) -> Result<(), HostError> {
         match self {
-            Some(elt) => Ok(Some(elt.metered_clone(budget)?)),
-            None => Ok(None),
+            HostEvent::Contract(c) => c.charge_for_substructure(budget),
+            HostEvent::Debug(d) => d.charge_for_substructure(budget),
         }
     }
 }
 
 impl MeteredClone for Events {
     const IS_SHALLOW: bool = false;
-    fn metered_clone(&self, budget: &Budget) -> Result<Self, HostError> {
-        budget.charge(CostType::CloneEvents, self.0.len() as u64)?;
-        Ok(self.clone())
+
+    const ELT_SIZE: u64 = 24;
+
+    fn charge_for_substructure(&self, budget: &Budget) -> Result<(), HostError> {
+        self.0.charge_for_substructure(budget)
+    }
+}
+
+impl MeteredClone for InternalEvent {
+    const IS_SHALLOW: bool = false;
+
+    const ELT_SIZE: u64 = 80;
+
+    fn charge_for_substructure(&self, budget: &Budget) -> Result<(), HostError> {
+        match self {
+            InternalEvent::Contract(c) => c.charge_for_substructure(budget),
+            InternalEvent::Debug(d) => d.charge_for_substructure(budget),
+            InternalEvent::None => Ok(()),
+        }
+    }
+}
+
+mod test {
+    #[allow(unused)]
+    use super::*;
+
+    #[test]
+    fn test_elt_size() {
+        use expect_test::expect;
+        // This section is for outputting the actual size of types. They are for informational use.
+        // They might become outdated due to Rust type changes. Run `UPDATE_EXPECT=true cargo test`
+        // to update this.
+        expect!["32"].assert_eq(std::mem::size_of::<Hash>().to_string().as_str());
+        expect!["8"].assert_eq(std::mem::size_of::<RawVal>().to_string().as_str());
+        expect!["1"].assert_eq(std::mem::size_of::<AccessType>().to_string().as_str());
+        expect!["32"].assert_eq(std::mem::size_of::<AccountId>().to_string().as_str());
+        expect!["33"].assert_eq(std::mem::size_of::<ScContractCode>().to_string().as_str());
+        expect!["32"].assert_eq(std::mem::size_of::<Uint256>().to_string().as_str());
+        expect!["33"].assert_eq(std::mem::size_of::<ScAddress>().to_string().as_str());
+        expect!["80"].assert_eq(std::mem::size_of::<LedgerKey>().to_string().as_str());
+        expect!["264"].assert_eq(std::mem::size_of::<LedgerEntry>().to_string().as_str());
+        expect!["40"].assert_eq(std::mem::size_of::<ScVal>().to_string().as_str());
+        expect!["24"].assert_eq(std::mem::size_of::<ScVec>().to_string().as_str());
+        expect!["80"].assert_eq(std::mem::size_of::<ScMapEntry>().to_string().as_str());
+        expect!["24"].assert_eq(std::mem::size_of::<ScMap>().to_string().as_str());
+        expect!["24"].assert_eq(std::mem::size_of::<Vec<u8>>().to_string().as_str());
+        expect!["24"].assert_eq(std::mem::size_of::<Vec<ScVal>>().to_string().as_str());
+        expect!["24"].assert_eq(std::mem::size_of::<BytesM<10000>>().to_string().as_str());
+        expect!["8"].assert_eq(std::mem::size_of::<Box<u8>>().to_string().as_str());
+        expect!["8"].assert_eq(std::mem::size_of::<Box<ScVal>>().to_string().as_str());
+        expect!["80"].assert_eq(std::mem::size_of::<DebugEvent>().to_string().as_str());
+        expect!["104"].assert_eq(std::mem::size_of::<ContractEvent>().to_string().as_str());
+        expect!["112"].assert_eq(std::mem::size_of::<HostEvent>().to_string().as_str());
+        expect!["24"].assert_eq(std::mem::size_of::<Events>().to_string().as_str());
+        expect!["80"].assert_eq(std::mem::size_of::<InternalEvent>().to_string().as_str());
+        expect!["40"].assert_eq(
+            std::mem::size_of::<InternalContractEvent>()
+                .to_string()
+                .as_str(),
+        );
+
+        // These are the actual tests. We use a tighter condition (==) than the actual code (<=).
+        // For any new `MeteredClone` type, a new test case needs to be added below.
+        macro_rules! assert_mem_size_equals_elt_size {
+            ($name:ident) => {
+                assert_eq!(
+                    std::mem::size_of::<$name>() as u64,
+                    <$name as MeteredClone>::ELT_SIZE
+                );
+            };
+        }
+        assert_mem_size_equals_elt_size!(Hash);
+        assert_mem_size_equals_elt_size!(RawVal);
+        assert_mem_size_equals_elt_size!(AccessType);
+        assert_mem_size_equals_elt_size!(AccountId);
+        assert_mem_size_equals_elt_size!(ScContractCode);
+        assert_mem_size_equals_elt_size!(Uint256);
+        assert_mem_size_equals_elt_size!(ScAddress);
+        assert_mem_size_equals_elt_size!(LedgerKey);
+        assert_mem_size_equals_elt_size!(LedgerEntry);
+        assert_mem_size_equals_elt_size!(ScVal);
+        assert_mem_size_equals_elt_size!(ScVec);
+        assert_mem_size_equals_elt_size!(ScMapEntry);
+        assert_mem_size_equals_elt_size!(ScMap);
+        assert_mem_size_equals_elt_size!(DebugEvent);
+        assert_mem_size_equals_elt_size!(ContractEvent);
+        assert_mem_size_equals_elt_size!(HostEvent);
+        assert_mem_size_equals_elt_size!(Events);
+        assert_mem_size_equals_elt_size!(InternalEvent);
+        assert_eq!(
+            std::mem::size_of::<Vec<u8>>() as u64,
+            <Vec<u8> as MeteredClone>::ELT_SIZE
+        );
+        assert_eq!(
+            std::mem::size_of::<Vec<ScVal>>() as u64,
+            <Vec<ScVal> as MeteredClone>::ELT_SIZE
+        );
+        assert_eq!(
+            std::mem::size_of::<BytesM<10000>>() as u64,
+            <BytesM<10000> as MeteredClone>::ELT_SIZE
+        );
+        assert_eq!(
+            std::mem::size_of::<Box<u8>>() as u64,
+            <Box<u8> as MeteredClone>::ELT_SIZE
+        );
+        assert_eq!(
+            std::mem::size_of::<Box<ScVal>>() as u64,
+            <Box<ScVal> as MeteredClone>::ELT_SIZE
+        );
     }
 }
diff --git a/soroban-env-host/src/host/metered_map.rs b/soroban-env-host/src/host/metered_map.rs
index c5b50064..28f5446a 100644
--- a/soroban-env-host/src/host/metered_map.rs
+++ b/soroban-env-host/src/host/metered_map.rs
@@ -18,6 +18,8 @@ where
     ctx: PhantomData<Ctx>,
 }
 
+/// `Clone` should not be used directly, used `MeteredClone` instead if possible. It is defined to
+/// satisfy trait requirements.
 impl<K, V, Ctx> Clone for MeteredOrdMap<K, V, Ctx>
 where
     K: MeteredClone,
@@ -38,8 +40,9 @@ where
     V: MeteredClone,
     Ctx: AsBudget + Compare<K, Error = HostError> + Compare<V, Error = HostError>,
 {
-    fn charge_new<B: AsBudget>(&self, size: usize, b: &B) -> Result<(), HostError> {
-        b.as_budget().charge(CostType::MapNew, size as u64)
+    fn charge_new<B: AsBudget>(n_elts: u64, b: &B) -> Result<(), HostError> {
+        let n_bytes = <Vec<(K, V)> as MeteredClone>::ELT_SIZE * n_elts;
+        b.as_budget().charge(CostType::MapNew, n_bytes)
     }
 
     fn charge_access<B: AsBudget>(&self, count: usize, b: &B) -> Result<(), HostError> {
@@ -84,7 +87,7 @@ where
     Ctx: AsBudget + Compare<K, Error = HostError> + Compare<V, Error = HostError>,
 {
     pub fn new(ctx: &Ctx) -> Result<Self, HostError> {
-        ctx.as_budget().charge(CostType::MapNew, 1)?;
+        Self::charge_new(0, ctx)?;
         Ok(MeteredOrdMap {
             map: Vec::new(),
             ctx: Default::default(),
@@ -120,10 +123,12 @@ where
         ctx: &Ctx,
     ) -> Result<Self, HostError> {
         if let (_, Some(sz)) = iter.size_hint() {
-            ctx.as_budget().charge(CostType::MapNew, sz as u64)?;
-            // TODO need to do a metered_clone bulk-charge here as well.
-            // ctx.as_budget().charge(CostType::BytesClone, nbytes)?;
+            // It's possible we temporarily go over-budget here before charging, but
+            // only by the cost of temporarily allocating twice the size of our largest
+            // possible object. In exchange we get to batch all charges associated with
+            // the clone into one (when A::IS_SHALLOW==true).
             let map: Vec<(K, V)> = iter.collect();
+            map.charge_deep_clone(ctx.as_budget())?;
             Ok(Self {
                 map,
                 ctx: Default::default(),
@@ -322,9 +327,10 @@ where
     V: MeteredClone,
     Ctx: AsBudget + Compare<K, Error = HostError> + Compare<V, Error = HostError>,
 {
-    fn metered_clone(&self, budget: &Budget) -> Result<Self, HostError> {
-        self.charge_new(self.map.len(), budget)?;
-        Ok(self.clone())
+    const ELT_SIZE: u64 = <Vec<(K, V)> as MeteredClone>::ELT_SIZE;
+
+    fn charge_for_substructure(&self, budget: &Budget) -> Result<(), HostError> {
+        self.map.charge_for_substructure(budget)
     }
 }
 
diff --git a/soroban-env-host/src/host/metered_vector.rs b/soroban-env-host/src/host/metered_vector.rs
index b3012dfb..86df8054 100644
--- a/soroban-env-host/src/host/metered_vector.rs
+++ b/soroban-env-host/src/host/metered_vector.rs
@@ -20,8 +20,9 @@ impl<A> MeteredVector<A>
 where
     A: MeteredClone,
 {
-    fn charge_new(size: usize, budget: &Budget) -> Result<(), HostError> {
-        budget.charge(CostType::VecNew, size as u64)
+    /// Covers the cost of allocating a new Vec<A> with size in number of elements.
+    fn charge_new(n_elts: u64, budget: &Budget) -> Result<(), HostError> {
+        budget.charge(CostType::VecNew, n_elts * A::ELT_SIZE)
     }
 
     fn charge_access(&self, count: usize, budget: &Budget) -> Result<(), HostError> {
@@ -47,8 +48,10 @@ where
         Self::from_vec(Vec::new())
     }
 
-    pub fn from_array<const N: usize>(buf: [A; N], budget: &Budget) -> Result<Self, HostError> {
-        Self::charge_new(N, budget)?;
+    pub fn from_array(buf: &[A], budget: &Budget) -> Result<Self, HostError> {
+        // we may temporarily go over budget here.
+        let vec: Vec<A> = buf.into();
+        vec.charge_deep_clone(budget)?;
         Self::from_vec(buf.into())
     }
 
@@ -66,14 +69,13 @@ where
         budget: &Budget,
     ) -> Result<Self, HostError> {
         if let (_, Some(sz)) = iter.size_hint() {
-            Self::charge_new(sz, budget)?;
             // It's possible we temporarily go over-budget here before charging, but
             // only by the cost of temporarily allocating twice the size of our largest
             // possible object. In exchange we get to batch all charges associated with
             // the clone into one (when A::IS_SHALLOW==true).
             let vec: Vec<A> = iter.collect();
-            A::charge_for_clones(vec.as_slice(), budget)?;
-            Ok(Self { vec })
+            vec.charge_deep_clone(budget)?;
+            Self::from_vec(vec)
         } else {
             // TODO use a better error code for "unbounded input iterators"
             Err(ScHostFnErrorCode::UnknownError.into())
@@ -267,15 +269,16 @@ where
     where
         F: FnMut(usize, &mut A) -> Result<bool, HostError>,
     {
-        Self::charge_new(self.len(), budget)?;
+        // The closure evaluation is not metered here, it is assumed to be taken care of outside.
+        // Here just covers the cost of cloning a Vec.
         let mut vec = Vec::with_capacity(self.len());
         for (i, v) in self.vec.iter_mut().enumerate() {
             if f(i, v)? {
                 vec.push(v.clone());
             }
         }
-        A::charge_for_clones(vec.as_slice(), budget)?;
-        Ok(Self { vec })
+        vec.charge_deep_clone(budget)?;
+        Self::from_vec(vec)
     }
 
     pub fn iter(&self) -> std::slice::Iter<'_, A> {
@@ -291,8 +294,10 @@ impl<A> MeteredClone for MeteredVector<A>
 where
     A: MeteredClone,
 {
-    fn charge_for_clone(&self, budget: &Budget) -> Result<(), HostError> {
-        Self::charge_new(self.len(), budget)
+    const ELT_SIZE: u64 = <Vec<A> as MeteredClone>::ELT_SIZE;
+
+    fn charge_for_substructure(&self, budget: &Budget) -> Result<(), HostError> {
+        self.vec.charge_for_substructure(budget)
     }
 }
 


Test patch:
diff --git a/soroban-env-host/src/test/budget_metering.rs b/soroban-env-host/src/test/budget_metering.rs
index bcc6e3e5..1789e418 100644
--- a/soroban-env-host/src/test/budget_metering.rs
+++ b/soroban-env-host/src/test/budget_metering.rs
@@ -1,8 +1,10 @@
 use crate::{
-    budget::CostType,
+    budget::{AsBudget, CostType},
+    host::metered_clone::MeteredClone,
     xdr::{ScMap, ScMapEntry, ScObject, ScVal, ScVmErrorCode},
     Env, Host, HostError, RawVal, Symbol,
 };
+use expect_test::{self, expect};
 use soroban_test_wasms::VEC;
 
 #[test]
@@ -142,3 +144,52 @@ fn map_insert_key_vec_obj() -> Result<(), HostError> {
 
     Ok(())
 }
+
+#[test]
+fn test_recursive_type_clone() -> Result<(), HostError> {
+    let host = Host::test_host()
+        .test_budget(100000, 100000)
+        .enable_model(CostType::HostMemAlloc)
+        .enable_model(CostType::HostMemCpy);
+    let scmap: ScMap = host.map_err(
+        vec![
+            ScMapEntry {
+                key: ScVal::U32(1),
+                val: ScVal::U32(2),
+            },
+            ScMapEntry {
+                key: ScVal::U32(2),
+                val: ScVal::U32(4),
+            },
+        ]
+        .try_into(),
+    )?;
+    let v: Vec<Box<ScMap>> = vec![
+        Box::new(scmap.clone()),
+        Box::new(scmap.clone()),
+        Box::new(scmap.clone()),
+    ];
+
+    v.metered_clone(host.as_budget())?;
+
+    //*********************************************************************************************************************************************/
+    /* Type(size, count) | Vec(24,1) ---> Box(8,3) ----> ScMap(24,3) --> Vec(24,3) ----> ScMapEntry(80,6) --> ScVal(40, 12) --> U32(4, 12)        */
+    /* MemAlloc          |            8x3      +    24x3              +             80x6                                                    = 576 */
+    /* MemCpy            |  24    +   8x3      +    24x3              +             80x6                                                    = 600 */
+    //*********************************************************************************************************************************************/
+    expect!["576"].assert_eq(
+        host.as_budget()
+            .get_input(CostType::HostMemAlloc)
+            .to_string()
+            .as_str(),
+    );
+    // 600 = 576 + 24 is correct because we need to copy all the memory allocated, as well as the
+    // memory layout of the top level type (Vec).
+    expect!["600"].assert_eq(
+        host.as_budget()
+            .get_input(CostType::HostMemCpy)
+            .to_string()
+            .as_str(),
+    );
+    Ok(())
+}
diff --git a/soroban-env-host/src/test/event.rs b/soroban-env-host/src/test/event.rs
index 02e6e52e..3ba87b56 100644
--- a/soroban-env-host/src/test/event.rs
+++ b/soroban-env-host/src/test/event.rs
@@ -96,7 +96,7 @@ fn test_event_rollback() -> Result<(), HostError> {
         RawVal::from_void().get_payload()
     );
     host.0.events.borrow_mut().rollback(1, &host)?;
-
+    // run `UPDATE_EXPECT=true cargo test` to update this.
     let expected = expect![[
         r#"Events([Contract(ContractEvent { ext: V0, contract_id: Some(Hash(0000000000000000000000000000000000000000000000000000000000000000)), type_: Contract, body: V0(ContractEventV0 { topics: ScVec(VecM([I32(0), I32(1)])), data: U32(0) }) }), Debug(DebugEvent { msg: Some("debug event 0"), args: [] }), Debug(DebugEvent { msg: Some("rolled-back contract event: type {}, id {}, topics {}, data {}"), args: [Val(I32(0)), Val(Object(Bytes(#4))), Val(Object(Vec(#2))), Val(U32(0))] }), Debug(DebugEvent { msg: Some("{} contract events rolled back. Rollback start pos = {}"), args: [Val(U32(1)), Val(U32(1))] })])"#
     ]];