C++ version of faskrelprimes.pl

fsckrelprimes.cpp

/***********************************************************************
 fsckrelprime.cpp - A simulator for fsck frequency on ext[234] sytems
    which shows that using relatively-prime max-mount-count values
    gives a lower chance of multi-volume checks on reboot.  See the
    usage message for more details.
***********************************************************************/

#include <cstring>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <vector>

using namespace std;


//// usage ///////////////////////////////////////////////////////////
// Tells how to run the program, then exits.

void
usage(const char* appname)
{
    cerr << "usage: " << appname << " [-v] <numbers>\n"
"\n"
"    Multiplies all passed numbers together, then iterates from 1 to\n"
"    their product looking for values that have two or more values in\n"
"    the passed set that are evenly divisible by two or more of those\n"
"    same values.\n"
"\n"
"    You will find that if you pass purely random numbers that you will\n"
"    get a higher collision rate than if you pass prime numbers or\n"
"    /relatively/ prime numbers: http://goo.gl/bQbu5Z\n"
"\n"
"    The application is ext[234] fsck frequency on a system with multiple\n"
"    volumes that are set to be checked periodically.  With the same\n"
"    value, they all have to be checked when any has to be checked, as\n"
"    long as the mount/check frequency is the same for all.  With random\n"
"    values, you can get into cases where two or more volumes have to be\n"
"    checked at the same time uncomfortably often.  With relatively prime\n"
"    values, you minimize the chance of two or more volumes needing to be\n"
"    checked at the same time.\n"
"\n"
"    You must pass at least two positive integers.\n"
"\n";

    exit(1);
}


//// count_divs ////////////////////////////////////////////////////////
// Returns the number of elements in vals that divide evenly into n.
// In Perl, this is just: my $divs = grep { $i % $_ == 0 } @vals;

static inline size_t
count_divs(uint64_t n, const vector<int>& vals)
{
    size_t divs = 0;
    for (auto it = vals.begin(); it != vals.end(); ++it) {
        if (n % *it == 0) ++divs;
    }
    return divs;
}


//// main //////////////////////////////////////////////////////////////

int
main(int argc, char* argv[])
{
    // Does caller want a verbose visual version of the simulation?
    bool verbose = argc > 1 && strcmp(argv[1], "-v") == 0;

    // Parse the value set from the command line
    uint64_t max = 1; 
    size_t nvals = argc - 1 - verbose;
    vector<int> vals(nvals);
    for (int i = 0; i < nvals; ++i) {
        int n = vals[i] = atoi(argv[i + 1]);
        if (n <= 2) usage(argv[0]);
        max *= n;
    }

    // The simulator core
    vector<int> buckets(nvals - 1, 0);
    size_t prevpctreport = 0;
    time_t start = time(0);
    for (uint64_t i = 0; i < max; ++i) {
        // Count the number of times i divides evenly into vals, and
        // keep track of how many times each multi-volume event occurs.
        size_t divs = count_divs(i, vals);
        if (divs >= 2) ++buckets[divs - 2];

        // Report the percentage done if this will take a long time.  Do
        // every 1% for billions of iterations, 10% for millions.
        if (max > 1e6) {
            size_t pctdone = float(i) / max * 100.0;
            if ((pctdone != prevpctreport) && 
                    ((pctdone % 10 == 0) || (max > 1e9))) {
                time_t now = time(0);
                int eta = float(now - start) / i * (max - i);
                cout << pctdone << "% done, finished in ~" << eta <<
                        " seconds.\n";
                prevpctreport = pctdone;
            }
        }

        // Emit a visual analog of the simulation.  Primarily useful for
        // debugging and small numbers of disks.
        if (verbose) {
                 if (divs == 0) cout << '.';    // no fsck this time
            else if (divs == 1) cout << '*';    // one volume fscks this time
            else cout << '[' << divs << ']';    // multi-volume fsck!
        }
    }
    if (verbose) cout << "\n\n";

    char pctstr[10];
    double total = 0;
    cout << "Results:\n\n";
    cout.imbue(locale(""));
    cout << "    period:   " << fixed << max << "\n";
    for (size_t i = 2; i <= nvals; ++i) {
        double pct = double(buckets[i - 2]) / max * 100.0;
        snprintf(pctstr, sizeof(pctstr), "%3.1f", pct);
        cout << "    " << i << "-volume: " << pctstr << "%\n";
        total += pct;
    }
    snprintf(pctstr, sizeof(pctstr), "%.1f", total);
    cout << "    total:    " << pctstr << "%\n\n";

    return 0;
}