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