1use 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#[derive(Debug, PartialEq, Eq)]
165pub struct CopyStep {
166 pub rows: usize,
168 pub complete: bool,
170}
171
172pub 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 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 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 #[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 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 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 self.target.map.insert(manifest_key(), checkpoint);
392 self.phase = phase;
393 Ok(CopyStep { rows, complete })
394 }
395
396 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 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 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
505pub struct RetiredSource<M: Memory> {
509 map: Map<M>,
510}
511
512impl<M: Memory> RetiredSource<M> {
513 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 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
557fn 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
576fn 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 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}