Skip to main content

ic_db/store/maintenance/
copy.rs

1//! Whole-database copy with private target admission and message-atomic checkpoints.
2use super::{Maintenance, SchemaTransition, decode as decode_source};
3use crate::{
4    Batch, Database, Entity, EntitySchema, Error, PrimaryKey, QueryCursor, Schema,
5    codec::{Decoder, Encoder},
6    primary::RowKey,
7    store::{
8        EntityState, Map, collect_references, entity_state_key, index_entries, live_manifest,
9        manifest_key, read_entity_state, row_key, validate_index_entry, validate_reference_target,
10    },
11    store_key::StoreKey,
12};
13use ic_storage::{DefaultMemoryImpl, Memory, RuntimeMemory};
14use std::{collections::BTreeSet, ops::Bound};
15
16pub(super) const MAGIC: &[u8; 8] = b"ICDBCP02";
17const MAX_FRAME: usize = 8 + 4 + super::MAX_FRAME + 20 + 2 + 4 + QueryCursor::MAX_ENCODED_BYTES;
18
19#[derive(Clone, Debug, PartialEq, Eq)]
20pub(super) struct Identity {
21    transition: SchemaTransition,
22    source: [u8; 16],
23    target: [u8; 16],
24}
25pub(super) enum Phase {
26    Source,
27    Copying(u8, Option<QueryCursor>),
28    Copied,
29    Cancelling,
30    Cancelled,
31    ValidatingSource(Option<StoreKey>),
32    ValidatingTarget(Option<StoreKey>),
33    Ready,
34    Retired,
35}
36impl Identity {
37    fn encode(&self, phase: &Phase) -> Result<Vec<u8>, Error> {
38        let mut writer = Encoder::new();
39        writer.bytes(&self.transition.freeze(self.source)?)?;
40        writer.bytes(&self.target)?;
41        writer.nat8(match phase {
42            Phase::Source => 0,
43            Phase::Copying(0, _) => 1,
44            Phase::Copying(_, _) => 9,
45            Phase::Copied => 2,
46            Phase::Cancelling => 3,
47            Phase::Cancelled => 4,
48            Phase::ValidatingSource(_) => 5,
49            Phase::ValidatingTarget(_) => 6,
50            Phase::Ready => 7,
51            Phase::Retired => 8,
52        })?;
53        if let Phase::Copying(entity, cursor) = phase {
54            if *entity != 0 {
55                writer.nat8(*entity)?;
56            }
57            writer.bytes(&cursor.as_ref().map_or_else(Vec::new, QueryCursor::to_bytes))?;
58        }
59        if let Phase::ValidatingSource(cursor) | Phase::ValidatingTarget(cursor) = phase {
60            writer.bytes(cursor.as_ref().map_or(&[], |key| &key[..]))?;
61        }
62        let mut bytes = MAGIC.to_vec();
63        bytes.extend(writer.finish());
64        Ok(bytes)
65    }
66}
67
68pub(super) fn decode(bytes: &[u8]) -> Result<(Identity, Phase), Error> {
69    if !bytes.starts_with(MAGIC) || bytes.len() > MAX_FRAME {
70        return Err(Error::InvalidTransition);
71    }
72    let mut reader = Decoder::new(&bytes[8..])?;
73    let (transition, source) = decode_source(reader.blob_ref(super::MAX_FRAME)?)?;
74    let target = reader
75        .blob_ref(16)?
76        .try_into()
77        .map_err(|_| Error::Corrupt)?;
78    if target == [0; 16] || target == source {
79        return Err(Error::Corrupt);
80    }
81    let phase = match reader.nat8()? {
82        0 => Phase::Source,
83        tag @ (1 | 9) => {
84            let entity = if tag == 1 {
85                0
86            } else {
87                let entity = reader.nat8()?;
88                if !(1..32).contains(&entity) {
89                    return Err(Error::Corrupt);
90                }
91                entity
92            };
93            let cursor = reader.blob_ref(QueryCursor::MAX_ENCODED_BYTES)?;
94            Phase::Copying(
95                entity,
96                if cursor.is_empty() {
97                    None
98                } else {
99                    Some(QueryCursor::from_bytes(cursor)?)
100                },
101            )
102        }
103        2 => Phase::Copied,
104        3 => Phase::Cancelling,
105        4 => Phase::Cancelled,
106        tag @ (5 | 6) => {
107            let bytes = reader.blob_ref(crate::MAX_INDEX_KEY_BYTES)?;
108            let cursor = if bytes.is_empty() {
109                None
110            } else {
111                Some(StoreKey::new(bytes.to_vec())?)
112            };
113            if tag == 5 {
114                Phase::ValidatingSource(cursor)
115            } else {
116                Phase::ValidatingTarget(cursor)
117            }
118        }
119        7 => Phase::Ready,
120        8 => Phase::Retired,
121        _ => return Err(Error::IncompatibleSchema),
122    };
123    reader.finish()?;
124    Ok((
125        Identity {
126            transition,
127            source,
128            target,
129        },
130        phase,
131    ))
132}
133
134fn admit(source: &Schema, target: &Schema, transition: &SchemaTransition) -> Result<(), Error> {
135    if source.fingerprint() != transition.source || target.fingerprint() != transition.target {
136        return Err(Error::IncompatibleSchema);
137    }
138    if source.entities().len() != target.entities().len() {
139        return Err(Error::InvalidTransition);
140    }
141    for (source, target) in source.entities().iter().zip(target.entities()) {
142        if source.name != target.name
143            || source.primary_key != target.primary_key
144            || source.key_type()? != target.key_type()?
145            || managed_roles(source) != managed_roles(target)
146        {
147            return Err(Error::InvalidTransition);
148        }
149    }
150    Ok(())
151}
152
153fn managed_roles(entity: &EntitySchema) -> [bool; 2] {
154    let mut roles = [false; 2];
155    for policy in entity.fields.iter().filter_map(|field| field.managed) {
156        roles[policy.slot()] = true;
157    }
158    roles
159}
160
161/// A bounded copy result. Completion means all source rows were copied, not
162/// that the target is validated for publication or available for ordinary access.
163#[derive(Debug, PartialEq, Eq)]
164pub struct CopyStep {
165    /// Rows transformed and inserted by this call.
166    pub rows: usize,
167    /// Every entity in the frozen source has been copied.
168    pub complete: bool,
169}
170
171/// Exclusive source/target custody for a key-preserving whole-database transformation.
172/// Both allocations remain closed to ordinary access. Dropping preserves progress.
173/// Publication requires completed validation. Allocation reuse remains unsupported.
174pub struct SchemaCopy<M: Memory = DefaultMemoryImpl> {
175    source: Maintenance<M>,
176    source_schema: Schema,
177    target: Database<M>,
178    identity: Identity,
179    phase: Phase,
180}
181
182impl<M: Memory> Maintenance<M> {
183    /// Bind a fresh target allocation to this frozen source and initialize copying.
184    /// The host supplies a fresh nonzero target incarnation, distinct from the source.
185    /// The schemas must contain the same named entities, each retaining its primary
186    /// key declaration and managed timestamp roles. References validate only after
187    /// all entities are copied, including unchanged entities. All values
188    /// and target indexes use ordinary codecs and shared batch validation.
189    /// # Errors
190    /// Refuses unsupported shapes, wrong schemas/identity or nonempty target memory
191    /// before mutation. Initial supplier growth may also refuse.
192    /// # Panics
193    /// Failures after target initialization trap; never catch and continue.
194    pub fn begin_copy(
195        mut self,
196        memory: RuntimeMemory<M>,
197        source: Schema,
198        target: Schema,
199        incarnation: [u8; 16],
200    ) -> Result<SchemaCopy<M>, Error> {
201        admit(&source, &target, &self.transition)?;
202        if incarnation == [0; 16] || incarnation == self.incarnation {
203            return Err(Error::InvalidTransition);
204        }
205        let identity = Identity {
206            transition: self.transition.clone(),
207            source: self.incarnation,
208            target: incarnation,
209        };
210        let source_gate = identity.encode(&Phase::Source)?;
211        let phase = Phase::Copying(0, None);
212        let target_gate = identity.encode(&phase)?;
213        let metadata: Vec<_> = target
214            .entities()
215            .iter()
216            .map(|entity| entity_state_key(entity.id))
217            .collect();
218        if memory.size() != 0 {
219            return Err(Error::Exists);
220        }
221        let mut map = Map::create(memory);
222        map.insert(manifest_key(), target_gate);
223        for key in metadata {
224            map.insert(key, EntityState::default().encode());
225        }
226        self.map.insert(manifest_key(), source_gate);
227        Ok(SchemaCopy {
228            source: self,
229            source_schema: source,
230            target: Database {
231                map,
232                schema: target,
233                incarnation,
234            },
235            identity,
236            phase,
237        })
238    }
239}
240
241impl<M: Memory> SchemaCopy<M> {
242    /// Resume only the recorded source/target pair and exact transformation.
243    /// # Errors
244    /// Refuses swapped, unrelated, live, cancelled or corrupt allocations intact.
245    /// # Panics
246    /// Supplier corruption traps without repair.
247    pub fn resume(
248        source_memory: RuntimeMemory<M>,
249        target_memory: RuntimeMemory<M>,
250        source_schema: Schema,
251        target_schema: Schema,
252        expected: &SchemaTransition,
253    ) -> Result<Self, Error> {
254        admit(&source_schema, &target_schema, expected)?;
255        if source_memory.size() == 0 {
256            return Err(Error::Corrupt);
257        }
258        let source = Map::load(source_memory);
259        if target_memory.size() == 0 {
260            return Err(Error::Corrupt);
261        }
262        let target = Map::load(target_memory);
263        let (identity, role) = decode(&source.get(&manifest_key()).ok_or(Error::Corrupt)?)?;
264        let (target_identity, phase) = decode(&target.get(&manifest_key()).ok_or(Error::Corrupt)?)?;
265        if !matches!(role, Phase::Source)
266            || matches!(phase, Phase::Source | Phase::Cancelled | Phase::Retired)
267            || identity != target_identity
268            || identity.transition != *expected
269        {
270            return Err(Error::InvalidTransition);
271        }
272        if matches!(&phase, Phase::Copying(entity, _) if usize::from(*entity) >= source_schema.entities().len())
273        {
274            return Err(Error::Corrupt);
275        }
276        Ok(Self {
277            source: Maintenance {
278                map: source,
279                transition: expected.clone(),
280                incarnation: identity.source,
281            },
282            source_schema,
283            target: Database {
284                map: target,
285                schema: target_schema,
286                incarnation: identity.target,
287            },
288            identity,
289            phase,
290        })
291    }
292
293    /// Name of the next entity to copy, in canonical schema-name order.
294    /// Returns `None` after copying or once cancellation/validation has started.
295    #[must_use]
296    pub fn next_entity(&self) -> Option<&'static str> {
297        if let Phase::Copying(entity, _) = &self.phase {
298            Some(self.source_schema.entities()[usize::from(*entity)].name)
299        } else {
300            None
301        }
302    }
303
304    /// Explicitly preserve an unchanged entity through the same bounded copy path.
305    /// The entity's complete declaration must be admitted by both schemas.
306    /// # Errors
307    /// Refuses changed declarations, wrong copy order, bounds or corrupt source rows.
308    /// # Panics
309    /// Supplier mutation failures trap and roll back the whole IC message.
310    pub fn copy_unchanged<E: Entity>(
311        &mut self,
312        limit: usize,
313        bytes: usize,
314    ) -> Result<CopyStep, Error> {
315        self.copy_next::<E, E>(limit, bytes, |row, _| Ok(row))
316    }
317
318    /// Transform the next bounded source page and checkpoint its target inserts.
319    /// The function must be deterministic for the declared version/fixed inputs,
320    /// synchronous and free of external effects or reentrant database mutations.
321    /// Limits match source paging: 1..=32 candidates, 1 byte..=128 KiB source output.
322    /// Target preparation additionally enforces the ordinary batch/index envelope.
323    /// Managed timestamp roles and their values must be preserved; field renames
324    /// are allowed through the explicit transformation. No insertion clock runs.
325    /// Call for `next_entity()` only. Completion advances to the next schema entity;
326    /// `complete` becomes true only after all entities have been copied.
327    /// Repeated calls after completion return zero rows and `complete = true`.
328    /// # Errors
329    /// Refusals (including transform errors, changed keys and cross-page uniqueness
330    /// collisions) leave both rows and progress unchanged. Cancelling refuses copying.
331    /// # Panics
332    /// Mutation failures or a later enclosing-message trap roll back the whole chunk
333    /// on the IC. Native callers must discard the runtime after a mutation panic.
334    pub fn copy_next<S: Entity, T: Entity>(
335        &mut self,
336        limit: usize,
337        bytes: usize,
338        transform: fn(S, &[u8]) -> Result<T, Error>,
339    ) -> Result<CopyStep, Error> {
340        self.source_schema.admits(S::SCHEMA)?;
341        self.target.schema.admits(T::SCHEMA)?;
342        let (entity, cursor) = match &self.phase {
343            Phase::Copying(entity, cursor) => (*entity, cursor.as_ref()),
344            Phase::Copied => {
345                return Ok(CopyStep {
346                    rows: 0,
347                    complete: true,
348                });
349            }
350            _ => return Err(Error::InvalidTransition),
351        };
352        if S::SCHEMA.name != self.source_schema.entities()[usize::from(entity)].name
353            || S::SCHEMA.name != T::SCHEMA.name
354        {
355            return Err(Error::InvalidTransition);
356        }
357        let page = self
358            .source
359            .source_page::<S>(&self.source_schema, cursor, limit, bytes)?;
360        let rows = page.rows.len();
361        let phase = if page.next.is_none() {
362            if usize::from(entity) + 1 == self.source_schema.entities().len() {
363                Phase::Copied
364            } else {
365                Phase::Copying(entity + 1, None)
366            }
367        } else {
368            Phase::Copying(entity, page.next)
369        };
370        let complete = matches!(phase, Phase::Copied);
371        let checkpoint = self.identity.encode(&phase)?;
372        let mut batch = Batch::new();
373        for row in page.rows {
374            let key = row.key().into_row_key();
375            let times = if S::SCHEMA.has_managed() {
376                crate::managed::values(S::SCHEMA, &row.encode()?)?
377            } else {
378                [None; 2]
379            };
380            let result = transform(row, self.identity.transition.inputs())?;
381            if result.key().into_row_key() != key {
382                return Err(Error::InvalidTransition);
383            }
384            batch.put(&result, |bytes, info| {
385                crate::store::Kind::CopyInsert(bytes, info, times)
386            })?;
387        }
388        self.target.commit(batch)?;
389        // No recoverable refusal after commit begins. The IC message owns rollback.
390        self.target.map.insert(manifest_key(), checkpoint);
391        self.phase = phase;
392        Ok(CopyStep { rows, complete })
393    }
394
395    /// Remove at most 1..=32 target entries, retaining its ownership tombstone.
396    /// Copying cannot resume once cleanup starts. Return true only after cleanup
397    /// and restoration of the source live manifest; drop this handle before reopen.
398    /// No physical shrink or target allocation reuse is promised.
399    /// # Errors
400    /// Refuses invalid limits before mutation.
401    /// # Panics
402    /// Supplier mutation failures trap and roll back the entire IC message.
403    pub fn cancel_step(&mut self, limit: usize) -> Result<bool, Error> {
404        let (keys, complete) = cleanup_keys(&self.target.map, limit)?;
405        if matches!(self.phase, Phase::Cancelled) {
406            return Ok(true);
407        }
408        let phase = if complete {
409            Phase::Cancelled
410        } else {
411            Phase::Cancelling
412        };
413        let checkpoint = self.identity.encode(&phase)?;
414        let live = live_manifest(self.identity.transition.source, self.identity.source);
415        for key in &keys {
416            self.target.map.remove(key);
417        }
418        self.target.map.insert(manifest_key(), checkpoint);
419        if complete {
420            self.source.map.insert(manifest_key(), live);
421        }
422        self.phase = phase;
423        Ok(complete)
424    }
425
426    /// Validate at most 1..=32 physical source or target entries in one call.
427    /// Checks complete row framing, exact key coverage in both directions, revision
428    /// metadata, expected index membership and every stored index's owner/key.
429    /// Each row has at most eight indexes and sixteen references. Each pass first
430    /// checks all declared revisions (at most 32), including empty entities. No writes to
431    /// rows/indexes occur; only successful bounded progress is checkpointed.
432    /// Return true only after both passes finish. Copying cannot resume afterward.
433    /// # Errors
434    /// Refuses before copy completion, during cancellation, or on limits/corruption.
435    /// A refused chunk leaves its durable validation position unchanged.
436    /// # Panics
437    /// Supplier failures trap; an IC trap rolls back checkpoint advancement.
438    pub fn validate_next(&mut self, limit: usize) -> Result<bool, Error> {
439        if !(1..=32).contains(&limit) {
440            return Err(Error::Limit);
441        }
442        let phase = match &self.phase {
443            Phase::Copied | Phase::ValidatingSource(_) => {
444                let cursor = if let Phase::ValidatingSource(cursor) = &self.phase {
445                    cursor.as_ref()
446                } else {
447                    None
448                };
449                let next = validate_page(
450                    &self.source.map,
451                    &self.source_schema,
452                    (&self.target.map, &self.target.schema),
453                    cursor,
454                    limit,
455                )?;
456                match next {
457                    Some(key) => Phase::ValidatingSource(Some(key)),
458                    None => Phase::ValidatingTarget(None),
459                }
460            }
461            Phase::ValidatingTarget(cursor) => {
462                let next = validate_page(
463                    &self.target.map,
464                    &self.target.schema,
465                    (&self.source.map, &self.source_schema),
466                    cursor.as_ref(),
467                    limit,
468                )?;
469                match next {
470                    Some(key) => Phase::ValidatingTarget(Some(key)),
471                    None => Phase::Ready,
472                }
473            }
474            Phase::Ready => return Ok(true),
475            _ => return Err(Error::InvalidTransition),
476        };
477        let checkpoint = self.identity.encode(&phase)?;
478        let complete = matches!(phase, Phase::Ready);
479        self.target.map.insert(manifest_key(), checkpoint);
480        self.phase = phase;
481        Ok(complete)
482    }
483
484    /// Atomically retire source admission and publish the fully validated target.
485    /// The host selects the target allocation for subsequent ordinary opens.
486    /// Source rows remain preserved but closed: this is not an operational rollback
487    /// promise after target writes. Explicit `RetiredSource` cleanup may remove them.
488    /// # Errors
489    /// Refuses unless both validation passes have completed.
490    /// # Panics
491    /// Mutation failures or a later enclosing-message trap roll back both manifests.
492    pub fn publish(mut self) -> Result<Database<M>, Error> {
493        if !matches!(self.phase, Phase::Ready) {
494            return Err(Error::InvalidTransition);
495        }
496        let retired = self.identity.encode(&Phase::Retired)?;
497        let live = live_manifest(self.identity.transition.target, self.identity.target);
498        self.source.map.insert(manifest_key(), retired);
499        self.target.map.insert(manifest_key(), live);
500        Ok(self.target)
501    }
502}
503
504/// Exclusive cleanup authority for an entire source collection retired by cutover.
505/// Admission binds the exact transition and both database incarnations. Cleanup
506/// never opens the target and never clears the source's retired manifest.
507pub struct RetiredSource<M: Memory = DefaultMemoryImpl> {
508    map: Map<M>,
509}
510
511impl<M: Memory> RetiredSource<M> {
512    /// Admit only the expected retired allocation, without decoding historical rows.
513    /// The host decides when preservation/recovery obligations permit deletion.
514    /// # Errors
515    /// Refuses live, copying, cancelled, foreign or malformed allocations intact.
516    /// # Panics
517    /// Supplier corruption traps without repair.
518    pub fn resume(
519        memory: RuntimeMemory<M>,
520        expected: &SchemaTransition,
521        source_incarnation: [u8; 16],
522        target_incarnation: [u8; 16],
523    ) -> Result<Self, Error> {
524        if memory.size() == 0 {
525            return Err(Error::Corrupt);
526        }
527        let map = Map::load(memory);
528        let (identity, phase) = decode(&map.get(&manifest_key()).ok_or(Error::Corrupt)?)?;
529        if !matches!(phase, Phase::Retired)
530            || identity.transition != *expected
531            || identity.source != source_incarnation
532            || identity.target != target_incarnation
533        {
534            return Err(Error::InvalidTransition);
535        }
536        Ok(Self { map })
537    }
538
539    /// Delete at most 1..=32 retired entries, preserving the ownership manifest.
540    /// Return true when only that manifest remains. Repeated completion is a no-op.
541    /// Deletion itself records progress; no additional cursor or phase is stored.
542    /// This does not shrink physical memory, reset the allocation or reopen source.
543    /// # Errors
544    /// Refuses invalid limits before mutation.
545    /// # Panics
546    /// Supplier mutation failures trap; the IC rolls back the whole cleanup chunk.
547    pub fn cleanup_step(&mut self, limit: usize) -> Result<bool, Error> {
548        let (keys, complete) = cleanup_keys(&self.map, limit)?;
549        for key in &keys {
550            self.map.remove(key);
551        }
552        Ok(complete)
553    }
554}
555
556// Cancellation and retired cleanup share bounded selection, keeping their
557// different authority changes at the caller. Values are not decoded for deletion.
558fn cleanup_keys<M: Memory>(map: &Map<M>, limit: usize) -> Result<(Vec<StoreKey>, bool), Error> {
559    if !(1..=32).contains(&limit) {
560        return Err(Error::Limit);
561    }
562    let manifest = manifest_key();
563    let mut keys: Vec<_> = map
564        .keys()
565        .filter(|key| *key != manifest)
566        .take(limit + 1)
567        .collect();
568    let complete = keys.len() <= limit;
569    if !complete {
570        keys.pop();
571    }
572    Ok((keys, complete))
573}
574
575// Validate the physical collection in both directions. Forward row checks find
576// missing/wrong-owner indexes; reverse index checks find stale/extra entries.
577fn validate_page<M: Memory>(
578    map: &Map<M>,
579    schema: &Schema,
580    peer: (&Map<M>, &Schema),
581    after: Option<&StoreKey>,
582    limit: usize,
583) -> Result<Option<StoreKey>, Error> {
584    // At most 32 entities. Check missing metadata and equal counts for this
585    // key-preserving copy; target counts were rebuilt by atomic private inserts.
586    // Frozen allocations cannot change mid-pass.
587    if after.is_none() {
588        for entity in schema.entities() {
589            if read_entity_state(map, entity.id)?.count
590                != read_entity_state(peer.0, entity.id)?.count
591            {
592                return Err(Error::Corrupt);
593            }
594        }
595    }
596    let lower = after.map_or(Bound::Unbounded, |key| Bound::Excluded(key.clone()));
597    let mut last = None;
598    let mut examined = 0;
599    for entry in map.range((lower, Bound::Unbounded)).take(limit) {
600        let key = entry.key();
601        if *key != manifest_key() {
602            let bytes = entry.value();
603            let id = u32::from_be_bytes(
604                key.get(1..5)
605                    .ok_or(Error::Corrupt)?
606                    .try_into()
607                    .map_err(|_| Error::Corrupt)?,
608            );
609            let entity = schema
610                .entities()
611                .iter()
612                .find(|entity| entity.id == id)
613                .ok_or(Error::Corrupt)?;
614            match key.first() {
615                Some(1) if *key == entity_state_key(entity.id) => {
616                    if bytes.len() != 16 {
617                        return Err(Error::Corrupt);
618                    }
619                }
620                Some(2) => {
621                    let peer_entity = peer
622                        .1
623                        .entities()
624                        .iter()
625                        .find(|entity| entity.id == id)
626                        .ok_or(Error::Corrupt)?;
627                    let info = entity.inspect_row(&bytes)?;
628                    let owner = RowKey::decode(&key[5..], entity.key_type()?)?;
629                    if info.key != owner || !peer.0.contains_key(&row_key(peer_entity.id, owner)) {
630                        return Err(Error::Corrupt);
631                    }
632                    if entity.has_managed() {
633                        let other = peer
634                            .0
635                            .get(&row_key(peer_entity.id, owner))
636                            .ok_or(Error::Corrupt)?;
637                        if crate::managed::values(entity, &bytes)?
638                            != crate::managed::values(peer_entity, &other)?
639                        {
640                            return Err(Error::ManagedField);
641                        }
642                    }
643                    for (index, _) in index_entries(entity, &info)? {
644                        let stored = map.get(&index).ok_or(Error::Corrupt)?;
645                        if RowKey::decode(&stored, entity.key_type()?)? != owner {
646                            return Err(Error::Corrupt);
647                        }
648                    }
649                    let mut required = BTreeSet::new();
650                    collect_references(entity, &info, &mut required)?;
651                    for (target, id) in required {
652                        validate_reference_target(map, schema, target, id)?;
653                    }
654                }
655                Some(3) => {
656                    let owner = RowKey::decode(&bytes, entity.key_type()?)?;
657                    let row = map.get(&row_key(entity.id, owner)).ok_or(Error::Corrupt)?;
658                    validate_index_entry(entity, &entity.inspect_row(&row)?, owner, key)?;
659                }
660                _ => return Err(Error::Corrupt),
661            }
662        }
663        last = Some(key.clone());
664        examined += 1;
665    }
666    Ok(if examined == limit { last } else { None })
667}