1use 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#[derive(Debug, PartialEq, Eq)]
164pub struct CopyStep {
165 pub rows: usize,
167 pub complete: bool,
169}
170
171pub 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 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 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 #[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 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 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 self.target.map.insert(manifest_key(), checkpoint);
391 self.phase = phase;
392 Ok(CopyStep { rows, complete })
393 }
394
395 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 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 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
504pub struct RetiredSource<M: Memory = DefaultMemoryImpl> {
508 map: Map<M>,
509}
510
511impl<M: Memory> RetiredSource<M> {
512 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 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
556fn 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
575fn 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 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}