monotone

monotone Mtn Source Tree

Root/database_check.cc

1// copyright (C) 2005 derek scherger <derek@echologic.com>
2// all rights reserved.
3// licensed to the public under the terms of the GNU GPL (>= 2)
4// see the file COPYING for details
5
6#include <map>
7#include <set>
8
9#include "app_state.hh"
10#include "constants.hh"
11#include "database_check.hh"
12#include "keys.hh"
13#include "revision.hh"
14#include "ui.hh"
15#include "vocab.hh"
16
17// the database has roughly the following structure
18//
19// certs
20// |
21// +---+---+
22// | |
23// keys revisions
24// |
25// manifests
26// |
27// files
28//
29
30struct checked_cert {
31 revision<cert> rcert;
32 bool found_key;
33 bool good_sig;
34
35 checked_cert(revision<cert> const & c): rcert(c), found_key(false), good_sig(false) {}
36};
37
38struct checked_key {
39 bool found; // found public keypair id in db
40 size_t sigs; // number of signatures by this key
41
42 base64<rsa_pub_key> pub_encoded;
43
44 checked_key(): found(false), sigs(0) {}
45};
46
47struct checked_file {
48 bool found; // found in db, retrieved and verified sha1 hash
49 size_t manifest_refs; // number of manifest references to this file
50
51 checked_file(): found(false), manifest_refs(0) {}
52};
53
54struct checked_manifest {
55 bool found; // found in db, retrieved and verified sha1 hash
56 size_t revision_refs; // number of revision references to this manifest
57 size_t missing_files; // number of missing files referenced by this manifest
58
59 checked_manifest(): found(false), revision_refs(0), missing_files(0) {}
60};
61
62// the number of times a revision is referenced (revision_refs)
63// should match the number of times it is listed as a parent in
64// the ancestry cache (ancestry_parent_refs)
65//
66// the number of parents a revision has should match the number
67// of times it is listed as a child in the ancestry cache
68// (ancestry_child_refs)
69
70struct checked_revision {
71 bool found; // found in db, retrieved and verified sha1 hash
72 size_t revision_refs; // number of references to this revision from other revisions
73 size_t ancestry_parent_refs; // number of references to this revision by ancestry parent
74 size_t ancestry_child_refs; // number of references to this revision by ancestry child
75
76 size_t missing_manifests; // number of missing manifests referenced by this revision
77 size_t missing_revisions; // number of missing revisions referenced by this revision
78 size_t incomplete_manifests; // number of manifests missing files referenced by this revision
79
80 size_t cert_refs; // number of references to this revision by revision certs;
81
82 std::string history_error;
83
84 std::set<revision_id> parents;
85 std::vector<checked_cert> checked_certs;
86
87 checked_revision():
88 found(false),
89 revision_refs(0), ancestry_parent_refs(0), ancestry_child_refs(0),
90 missing_manifests(0), missing_revisions(0), incomplete_manifests(0),
91 cert_refs(0) {}
92};
93
94static void
95check_files(app_state & app, std::map<file_id, checked_file> & checked_files)
96{
97 std::set<file_id> files;
98
99 app.db.get_file_ids(files);
100 L(F("checking %d files\n") % files.size());
101
102 ticker ticks("files", "f", files.size()/70+1);
103
104 for (std::set<file_id>::const_iterator i = files.begin();
105 i != files.end(); ++i)
106 {
107 L(F("checking file %s\n") % *i);
108 file_data data;
109 app.db.get_file_version(*i, data);
110 checked_files[*i].found = true;
111 ++ticks;
112 }
113
114 I(checked_files.size() == files.size());
115}
116
117static void
118check_manifests(app_state & app,
119 std::map<manifest_id, checked_manifest> & checked_manifests,
120 std::map<file_id, checked_file> & checked_files)
121{
122 std::set<manifest_id> manifests;
123
124 app.db.get_manifest_ids(manifests);
125 L(F("checking %d manifests\n") % manifests.size());
126
127 ticker ticks("manifests", "m", manifests.size()/70+1);
128
129 for (std::set<manifest_id>::const_iterator i = manifests.begin();
130 i != manifests.end(); ++i)
131 {
132 L(F("checking manifest %s\n") % *i);
133 manifest_data data;
134 app.db.get_manifest_version(*i, data);
135 checked_manifests[*i].found = true;
136
137 manifest_map man;
138 read_manifest_map(data, man);
139
140 for (manifest_map::const_iterator entry = man.begin(); entry != man.end();
141 ++entry)
142 {
143 checked_files[manifest_entry_id(entry)].manifest_refs++;
144
145 if (!checked_files[manifest_entry_id(entry)].found)
146 checked_manifests[*i].missing_files++;
147 }
148
149 ++ticks;
150 }
151
152 I(checked_manifests.size() == manifests.size());
153}
154
155static void
156check_revisions(app_state & app,
157 std::map<revision_id, checked_revision> & checked_revisions,
158 std::map<manifest_id, checked_manifest> & checked_manifests)
159{
160 std::set<revision_id> revisions;
161
162 app.db.get_revision_ids(revisions);
163 L(F("checking %d revisions\n") % revisions.size());
164
165 ticker ticks("revisions", "r", revisions.size()/70+1);
166
167 for (std::set<revision_id>::const_iterator i = revisions.begin();
168 i != revisions.end(); ++i)
169 {
170 L(F("checking revision %s\n") % *i);
171 revision_data data;
172 app.db.get_revision(*i, data);
173 checked_revisions[*i].found = true;
174
175 revision_set rev;
176 read_revision_set(data, rev);
177
178 checked_manifests[rev.new_manifest].revision_refs++;
179
180 if (!checked_manifests[rev.new_manifest].found)
181 checked_revisions[*i].missing_manifests++;
182
183 if (checked_manifests[rev.new_manifest].missing_files > 0)
184 checked_revisions[*i].incomplete_manifests++;
185
186 for (edge_map::const_iterator edge = rev.edges.begin();
187 edge != rev.edges.end(); ++edge)
188 {
189 // ignore [] -> [...] manifests
190
191 if (!null_id(edge_old_manifest(edge)))
192 {
193 checked_manifests[edge_old_manifest(edge)].revision_refs++;
194
195 if (!checked_manifests[edge_old_manifest(edge)].found)
196 checked_revisions[*i].missing_manifests++;
197
198 if (checked_manifests[edge_old_manifest(edge)].missing_files > 0)
199 checked_revisions[*i].incomplete_manifests++;
200 }
201
202 // ignore [] -> [...] revisions
203
204 // delay checking parents until we've processed all revisions
205 if (!null_id(edge_old_revision(edge)))
206 {
207 checked_revisions[edge_old_revision(edge)].revision_refs++;
208 checked_revisions[*i].parents.insert(edge_old_revision(edge));
209 }
210
211 // also check that change_sets applied to old manifests == new
212 // manifests (which might be a merge)
213 }
214
215 ++ticks;
216 }
217
218 // now check for parent revision existence and problems
219
220 for (std::map<revision_id, checked_revision>::iterator
221 revision = checked_revisions.begin();
222 revision != checked_revisions.end(); ++revision)
223 {
224 for (std::set<revision_id>::const_iterator p = revision->second.parents.begin();
225 p != revision->second.parents.end(); ++p)
226 {
227 if (!checked_revisions[*p].found)
228 revision->second.missing_revisions++;
229 }
230 }
231
232 L(F("checked %d revisions after starting with %d\n")
233 % checked_revisions.size()
234 % revisions.size());
235}
236
237static void
238check_ancestry(app_state & app,
239 std::map<revision_id, checked_revision> & checked_revisions)
240{
241 std::multimap<revision_id, revision_id> graph;
242
243 app.db.get_revision_ancestry(graph);
244 L(F("checking %d ancestry edges\n") % graph.size());
245
246 ticker ticks("ancestry", "a", graph.size()/70+1);
247
248 // checked revision has set of parents
249 // graph has revision and associated parents
250 // these two representations of the graph should agree!
251
252 std::set<revision_id> seen;
253 for (std::multimap<revision_id, revision_id>::const_iterator i = graph.begin();
254 i != graph.end(); ++i)
255 {
256 // ignore the [] -> [...] edges here too
257 if (!null_id(i->first))
258 {
259 checked_revisions[i->first].ancestry_parent_refs++;
260
261 if (!null_id(i->second))
262 checked_revisions[i->second].ancestry_child_refs++;
263 }
264
265 ++ticks;
266 }
267}
268
269static void
270check_keys(app_state & app,
271 std::map<rsa_keypair_id, checked_key> & checked_keys)
272{
273 std::vector<rsa_keypair_id> pubkeys;
274
275 app.db.get_public_keys(pubkeys);
276
277 L(F("checking %d public keys\n") % pubkeys.size());
278
279 ticker ticks("keys", "k", 1);
280
281 for (std::vector<rsa_keypair_id>::const_iterator i = pubkeys.begin();
282 i != pubkeys.end(); ++i)
283 {
284 app.db.get_key(*i, checked_keys[*i].pub_encoded);
285 checked_keys[*i].found = true;
286 ++ticks;
287 }
288
289}
290
291static void
292check_certs(app_state & app,
293 std::map<revision_id, checked_revision> & checked_revisions,
294 std::map<rsa_keypair_id, checked_key> & checked_keys,
295 size_t & total_certs)
296{
297
298 std::vector< revision<cert> > certs;
299 app.db.get_revision_certs(certs);
300
301 total_certs = certs.size();
302
303 L(F("checking %d revision certs\n") % certs.size());
304
305 ticker ticks("certs", "c", certs.size()/70+1);
306
307 for (std::vector< revision<cert> >::const_iterator i = certs.begin();
308 i != certs.end(); ++i)
309 {
310 checked_cert checked(*i);
311 checked.found_key = checked_keys[i->inner().key].found;
312
313 if (checked.found_key)
314 {
315 std::string signed_text;
316 cert_signable_text(i->inner(), signed_text);
317 checked.good_sig = check_signature(app.lua, i->inner().key,
318 checked_keys[i->inner().key].pub_encoded,
319 signed_text, i->inner().sig);
320 }
321
322 checked_keys[i->inner().key].sigs++;
323 checked_revisions[i->inner().ident].checked_certs.push_back(checked);
324
325 ++ticks;
326 }
327}
328
329static void
330check_sane(app_state & app,
331 std::map<revision_id, checked_revision> & checked_revisions)
332{
333 L(F("checking local history of %d revisions\n") % checked_revisions.size());
334
335 ticker ticks("revisions", "r", 1);
336
337 for (std::map<revision_id, checked_revision>::iterator
338 i = checked_revisions.begin(); i != checked_revisions.end(); ++i)
339 {
340 if (i->second.found)
341 {
342 try
343 {
344 check_sane_history(i->first, constants::verify_depth, app);
345 }
346 catch (std::exception & e)
347 {
348 i->second.history_error = e.what();
349 }
350 }
351 ++ticks;
352 }
353}
354
355static void
356report_files(std::map<file_id, checked_file> const & checked_files,
357 size_t & missing_files,
358 size_t & unreferenced_files)
359{
360 for (std::map<file_id, checked_file>::const_iterator
361 i = checked_files.begin(); i != checked_files.end(); ++i)
362 {
363 checked_file file = i->second;
364
365 if (!file.found)
366 {
367 missing_files++;
368 P(F("file %s missing (%d manifest references)\n")
369 % i->first % file.manifest_refs);
370 }
371
372 if (file.manifest_refs == 0)
373 {
374 unreferenced_files++;
375 P(F("file %s unreferenced\n") % i->first);
376 }
377
378 }
379}
380
381static void
382report_manifests(std::map<manifest_id, checked_manifest> const & checked_manifests,
383 size_t & missing_manifests,
384 size_t & unreferenced_manifests,
385 size_t & incomplete_manifests)
386{
387 for (std::map<manifest_id, checked_manifest>::const_iterator
388 i = checked_manifests.begin(); i != checked_manifests.end(); ++i)
389 {
390 checked_manifest manifest = i->second;
391
392 if (!manifest.found)
393 {
394 missing_manifests++;
395 P(F("manifest %s missing (%d revision references)\n")
396 % i->first % manifest.revision_refs);
397 }
398
399 if (manifest.revision_refs == 0)
400 {
401 unreferenced_manifests++;
402 P(F("manifest %s unreferenced\n") % i->first);
403 }
404
405 if (manifest.missing_files > 0)
406 {
407 incomplete_manifests++;
408 P(F("manifest %s incomplete (%d missing files)\n")
409 % i->first % manifest.missing_files);
410 }
411 }
412}
413
414static void
415report_revisions(std::map<revision_id, checked_revision> const & checked_revisions,
416 size_t & missing_revisions,
417 size_t & incomplete_revisions,
418 size_t & mismatched_parents,
419 size_t & mismatched_children,
420 size_t & bad_history)
421{
422 for (std::map<revision_id, checked_revision>::const_iterator
423 i = checked_revisions.begin(); i != checked_revisions.end(); ++i)
424 {
425 checked_revision revision = i->second;
426
427 if (!revision.found)
428 {
429 missing_revisions++;
430 P(F("revision %s missing (%d revision references; %d cert references)\n")
431 % i->first % revision.revision_refs % revision.cert_refs);
432 }
433
434 if (revision.missing_manifests > 0)
435 {
436 incomplete_revisions++;
437 P(F("revision %s incomplete (%d missing manifests)\n")
438 % i->first % revision.missing_manifests);
439 }
440
441 if (revision.missing_revisions > 0)
442 {
443 incomplete_revisions++;
444 P(F("revision %s incomplete (%d missing revisions)\n")
445 % i->first % revision.missing_revisions);
446 }
447
448 if (revision.incomplete_manifests > 0)
449 {
450 incomplete_revisions++;
451 P(F("revision %s incomplete (%d incomplete manifests)\n")
452 % i->first % revision.incomplete_manifests);
453 }
454
455 if (revision.ancestry_parent_refs != revision.revision_refs)
456 {
457 mismatched_parents++;
458 P(F("revision %s mismatched parents (%d ancestry parents; %d revision refs)\n")
459 % i->first
460 % revision.ancestry_parent_refs
461 % revision.revision_refs );
462 }
463
464 if (revision.ancestry_child_refs != revision.parents.size())
465 {
466 mismatched_children++;
467 P(F("revision %s mismatched children (%d ancestry children; %d parents)\n")
468 % i->first
469 % revision.ancestry_child_refs
470 % revision.parents.size() );
471 }
472
473 if (!revision.history_error.empty())
474 {
475 bad_history++;
476 P(F("revision %s has bad history (%s)\n")
477 % i->first
478 % revision.history_error);
479 }
480 }
481}
482
483static void
484report_keys(std::map<rsa_keypair_id, checked_key> const & checked_keys,
485 size_t & missing_keys)
486{
487 for (std::map<rsa_keypair_id, checked_key>::const_iterator
488 i = checked_keys.begin(); i != checked_keys.end(); ++i)
489 {
490 checked_key key = i->second;
491
492 if (key.found)
493 {
494 L(F("key %s signed %d certs\n")
495 % i->first
496 % key.sigs);
497 }
498 else
499 {
500 missing_keys++;
501 P(F("key %s missing (signed %d certs)\n")
502 % i->first
503 % key.sigs);
504 }
505 }
506}
507
508static void
509report_certs(std::map<revision_id, checked_revision> const & checked_revisions,
510 size_t & missing_certs,
511 size_t & mismatched_certs,
512 size_t & unchecked_sigs,
513 size_t & bad_sigs)
514{
515 std::set<cert_name> cnames;
516
517 cnames.insert(cert_name(author_cert_name));
518 cnames.insert(cert_name(branch_cert_name));
519 cnames.insert(cert_name(changelog_cert_name));
520 cnames.insert(cert_name(date_cert_name));
521
522 for (std::map<revision_id, checked_revision>::const_iterator
523 i = checked_revisions.begin(); i != checked_revisions.end(); ++i)
524 {
525 checked_revision revision = i->second;
526 std::map<cert_name, size_t> cert_counts;
527
528 for (std::vector<checked_cert>::const_iterator checked = revision.checked_certs.begin();
529 checked != revision.checked_certs.end(); ++checked)
530 {
531 if (!checked->found_key)
532 {
533 unchecked_sigs++;
534 P(F("revision %s unchecked signature in %s cert from missing key %s\n")
535 % i->first
536 % checked->rcert.inner().name
537 % checked->rcert.inner().key);
538 }
539 else if (!checked->good_sig)
540 {
541 bad_sigs++;
542 P(F("revision %s bad signature in %s cert from key %s\n")
543 % i->first
544 % checked->rcert.inner().name
545 % checked->rcert.inner().key);
546 }
547
548 cert_counts[checked->rcert.inner().name]++;
549 }
550
551 for (std::set<cert_name>::const_iterator n = cnames.begin();
552 n != cnames.end(); ++n)
553 {
554 if (revision.found && cert_counts[*n] == 0)
555 {
556 missing_certs++;
557 P(F("revision %s missing %s cert\n") % i->first % *n);
558 }
559 }
560
561 if (cert_counts[cert_name(author_cert_name)] != cert_counts[cert_name(changelog_cert_name)] ||
562 cert_counts[cert_name(author_cert_name)] != cert_counts[cert_name(date_cert_name)] ||
563 cert_counts[cert_name(date_cert_name)] != cert_counts[cert_name(changelog_cert_name)])
564 {
565 mismatched_certs++;
566 P(F("revision %s mismatched certs (%d authors %d dates %d changelogs)\n")
567 % i->first
568 % cert_counts[cert_name(author_cert_name)]
569 % cert_counts[cert_name(date_cert_name)]
570 % cert_counts[cert_name(changelog_cert_name)]);
571 }
572
573 }
574}
575
576void
577check_db(app_state & app)
578{
579 std::map<file_id, checked_file> checked_files;
580 std::map<manifest_id, checked_manifest> checked_manifests;
581 std::map<revision_id, checked_revision> checked_revisions;
582 std::map<rsa_keypair_id, checked_key> checked_keys;
583
584 size_t missing_files = 0;
585 size_t unreferenced_files = 0;
586
587 size_t missing_manifests = 0;
588 size_t unreferenced_manifests = 0;
589 size_t incomplete_manifests = 0;
590
591 size_t missing_revisions = 0;
592 size_t incomplete_revisions = 0;
593 size_t mismatched_parents = 0;
594 size_t mismatched_children = 0;
595 size_t bad_history = 0;
596
597 size_t missing_keys = 0;
598
599 size_t total_certs = 0;
600 size_t missing_certs = 0;
601 size_t mismatched_certs = 0;
602 size_t unchecked_sigs = 0;
603 size_t bad_sigs = 0;
604
605 check_files(app, checked_files);
606 check_manifests(app, checked_manifests, checked_files);
607 check_revisions(app, checked_revisions, checked_manifests);
608 check_ancestry(app, checked_revisions);
609 check_sane(app, checked_revisions);
610 check_keys(app, checked_keys);
611 check_certs(app, checked_revisions, checked_keys, total_certs);
612
613 report_files(checked_files, missing_files, unreferenced_files);
614
615 report_manifests(checked_manifests,
616 missing_manifests, unreferenced_manifests, incomplete_manifests);
617
618 report_revisions(checked_revisions,
619 missing_revisions, incomplete_revisions,
620 mismatched_parents, mismatched_children,
621 bad_history);
622
623 report_keys(checked_keys, missing_keys);
624
625 report_certs(checked_revisions,
626 missing_certs, mismatched_certs,
627 unchecked_sigs, bad_sigs);
628
629 if (missing_files > 0)
630 W(F("%d missing files\n") % missing_files);
631 if (unreferenced_files > 0)
632 W(F("%d unreferenced files\n") % unreferenced_files);
633
634 if (missing_manifests > 0)
635 W(F("%d missing manifests\n") % missing_manifests);
636 if (unreferenced_manifests > 0)
637 W(F("%d unreferenced manifests\n") % unreferenced_manifests);
638 if (incomplete_manifests > 0)
639 W(F("%d incomplete manifests\n") % incomplete_manifests);
640
641 if (missing_revisions > 0)
642 W(F("%d missing revisions\n") % missing_revisions);
643 if (incomplete_revisions > 0)
644 W(F("%d incomplete revisions\n") % incomplete_revisions);
645 if (mismatched_parents > 0)
646 W(F("%d mismatched parents\n") % mismatched_parents);
647 if (mismatched_children > 0)
648 W(F("%d mismatched children\n") % mismatched_children);
649 if (bad_history > 0)
650 W(F("%d revisions with bad history\n") % bad_history);
651
652 if (missing_keys > 0)
653 W(F("%d missing keys\n") % missing_keys);
654
655 if (missing_certs > 0)
656 W(F("%d missing certs\n") % missing_certs);
657 if (mismatched_certs > 0)
658 W(F("%d mismatched certs\n") % mismatched_certs);
659 if (unchecked_sigs > 0)
660 W(F("%d unchecked signatures due to missing keys\n") % unchecked_sigs);
661 if (bad_sigs > 0)
662 W(F("%d bad signatures\n") % bad_sigs);
663
664 size_t total = missing_files + unreferenced_files +
665 missing_manifests + unreferenced_manifests + incomplete_manifests +
666 missing_revisions + incomplete_revisions +
667 mismatched_parents + mismatched_children +
668 bad_history +
669 missing_certs + mismatched_certs +
670 unchecked_sigs + bad_sigs +
671 missing_keys;
672 // unreferenced files and manifests and mismatched certs are not actually
673 // serious errors; odd, but nothing will break.
674 size_t serious = missing_files +
675 missing_manifests + incomplete_manifests +
676 missing_revisions + incomplete_revisions +
677 mismatched_parents + mismatched_children +
678 bad_history +
679 missing_certs +
680 unchecked_sigs + bad_sigs +
681 missing_keys;
682
683 P(F("check complete: %d files; %d manifests; %d revisions; %d keys; %d certs\n")
684 % checked_files.size()
685 % checked_manifests.size()
686 % checked_revisions.size()
687 % checked_keys.size()
688 % total_certs);
689 P(F("total problems detected: %d (%d serious)\n") % total % serious);
690 if (serious)
691 E(false, F("serious problems detected"));
692 else if (total)
693 P(F("minor problems detected\n"));
694 else
695 P(F("database is good\n"));
696}

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status