/home/serif/byzantine_generals/src/clihandler.cpp

Go to the documentation of this file.

/**
 * @file clihandler.cpp
 * @author Reshen Amin <reshen@zensrc.com>
 *
 * @brief Contains the class declaration for kicking off the program
 *
 * @license Byzantine Generals Problem Coding Sample.<br>
 * Copyright (C) 2010  Reshen Amin.<br>
 * See @ref license_sec for details.<br>
 */

#include "clihandler.h"

#include <boost/interprocess/managed_shared_memory.hpp>
#include <boost/program_options.hpp>

#include <log4cpp/Category.hh>
#include <log4cpp/OstreamAppender.hh>
#include <log4cpp/PatternLayout.hh>

#include <vector>
#include <string>
#include <functional>

#include "sharedmemtypes.h"
#include "byzantinegeneralthread.h"
#include "mailbox.h"

const char* CLIHandler::kSharedMemoryName_ = "ByzGeneralsSharedMemory";
const char* CLIHandler::kMailboxVectorName_ = "ByzGeneralsMailboxVector";
const char* CLIHandler::kTraitorSetName_ = "ByzGeneralsTraitorSet";
const char* CLIHandler::kLogCategoryName_ = "ByzGeneralsLogCategory";

CLIHandler::CLIHandler()
    : log_(InitializeLogger()),
      number_rounds_(0),
      number_traitor_generals_(0),
      number_loyal_generals_(0),
      generate_dot_graph_(false),
      total_number_generals_(0),
      total_messages_per_lt_general_(0),
      byzantine_generals_(),
      segment_(NULL),
      traitor_set_(NULL),
      mailbox_vector_(NULL) {
}

CLIHandler::~CLIHandler() {
}

ByzGeneralsReturnCodes::type CLIHandler::Exec(int argc, char* argv[]) {
    /* Parse and validate input arguments */
    const ByzGeneralsReturnCodes::type result =
        ParseAndValidateArguments(argc, argv);

    switch (result) {
        case ByzGeneralsReturnCodes::kNoError:
            /* Do Nothing */
            break;

        case ByzGeneralsReturnCodes::kHelpExitNoError:
            /* User requested help, return to main and exit */
            return ByzGeneralsReturnCodes::kNoError;
            break;

        case ByzGeneralsReturnCodes::kInvalidInput:
            throw std::invalid_argument("Invalid Input");
            break;

        case ByzGeneralsReturnCodes::kIPCError:
            throw std::invalid_argument("IPC Error");
            break;

        case ByzGeneralsReturnCodes::kUnknown:
        default:
            /* Some error occured, return it to main to exit */
            throw std::exception();
            break;
    }

    /* Use input arguments, calculate how many rounds of communication will take
     * place and the cumulative number of messages that each general will
     * exchange during those rounds. */
    CalculateOrdersAndRounds();

    /* Create Shared Memory and Related Items */
    CreateSharedMemoryItems();

    /* Create Generals Threads */
    CreateGeneralThreads();

    /* Start General Threads */
    assert(byzantine_generals_.size() == total_number_generals_);
    for (unsigned int i = 0; i < total_number_generals_; ++i) {
        byzantine_generals_.at(i)->Start();
    }

    /* Wait for generals to complete their work (join) */
    for (unsigned int i = 0; i < total_number_generals_; ++i) {
        byzantine_generals_.at(i)->Stop();
    }

    /* Destroy Generals Threads */
    DestroyGeneralThreads();

    /* Destory Shared Memory and Related Items */
    DestroySharedMemoryItems();

    return result;
}

log4cpp::Category& CLIHandler::InitializeLogger() {
    /* Set up our logging library (Log4cpp) */
    log4cpp::OstreamAppender* appender =
        new log4cpp::OstreamAppender("out", &std::cout);
    assert(appender != NULL);

    log4cpp::PatternLayout* layout = new log4cpp::PatternLayout();
    assert(layout != NULL);

    log4cpp::Category& log = log4cpp::Category::getInstance(kLogCategoryName_);

    /* Set logging output pattern to "Timestamp Priority : Message" */
    layout->setConversionPattern("%d{%H:%M:%S.%l} %p : %m%n");
    appender->setLayout(layout);
    log.setAppender(appender);

    /* Set default logging level - user configurable via verbose command line
     * option */
    log.setPriority(log4cpp::Priority::NOTICE);

    return log;
}

ByzGeneralsReturnCodes::type
CLIHandler::ParseAndValidateArguments(int argc, char* argv[]) {
    /* Parse and validate input arguments */

    /* We use Boost's excellent program_options library to elegantly parse
     * program arguments */
    namespace po = boost::program_options;

    po::options_description description("Allowed options");
    description.add_options()
        ("help", "Produce help message")
        ("graph", po::value<bool>()->default_value(false),
         "Generate a DOT graph for the first general.")
        ("loyalists", po::value<int>()->default_value(3),
         "Number of loyal generals.")
        ("traitors", po::value<int>()->default_value(1),
         "Number of traitor generals.")
        ("verbose", po::value<bool>()->default_value(false),
         "Verbose debugging information.");

    po::variables_map variables_map;
    po::store(po::parse_command_line(argc, argv, description), variables_map);
    po::notify(variables_map);

    if (variables_map.count("help")) {
        /* User asked for help, print usage options here then exit */
        log_.noticeStream() << description;
        return ByzGeneralsReturnCodes::kHelpExitNoError;
    }

    if (variables_map.count("traitors")) {
        /* Parse the number of traitor generals */
        number_traitor_generals_ = variables_map["traitors"].as<int>();
        log_.noticeStream() << "Number of traitor generals set to "
                            << number_traitor_generals_ << ".";
    }

    if (variables_map.count("loyalists")) {
        /* Parse the number of loyal generals */
        number_loyal_generals_ = variables_map["loyalists"].as<int>();
        log_.noticeStream() << "Number of loyal generals set to "
                            << number_loyal_generals_ << ".";
    }

    if (variables_map.count("graph")) {
        /* Parse DOT graph generation */
        generate_dot_graph_ = variables_map["graph"].as<bool>();
        log_.noticeStream() << "Graph output is "
                            << (generate_dot_graph_ ?
                                    std::string("enabled.") :
                                    std::string("disabled."));
    }

    if (variables_map.count("verbose")) {
        /* Verbose debugging information */
        bool verbose = variables_map["verbose"].as<bool>();
        log_.noticeStream() << "Verbose debugging is "
                            << (verbose ?
                                    std::string("enabled.") :
                                    std::string("disabled."));

        if (verbose == true) {
            log_.setPriority(log4cpp::Priority::INFO);
        }
        // else default to NOTICE
    }

    if ((number_loyal_generals_ + number_traitor_generals_) <
            ((3 * number_traitor_generals_) + 1)) {
        /* Validate that we have the correct ratio of loyal generals
         * to traitor generals [Number of Total Generals >= (Number of
         * Loyal Generals * 3 + 1)].  If we don't have enough, then we
         * won't be able to guarantee that our loyal generals reach
         * consensus. */

        log_.error("We need at least (3n + 1) total generals, where n"
                   "is the number of traitor generals.");

        return ByzGeneralsReturnCodes::kInvalidInput;
    }

    total_number_generals_ = number_loyal_generals_ + number_traitor_generals_;

    if (total_number_generals_ <= 0) {
        log_.error("We need at least 1 loyal general to begin.");

        return ByzGeneralsReturnCodes::kInvalidInput;
    }

    return ByzGeneralsReturnCodes::kNoError;
}

void CLIHandler::CalculateOrdersAndRounds() {
    /* Calculate the number of orders (aka messages) each general should expect.
     *
     * Round 0 begins by the commanding general sending the initial order out to
     * each of his lieutenant generals.
     *
     * In Round 1, N-1 messages will be received, where N = total number of
     * generals.
     *
     * In Round 2, (N - 1) * (N - 2) messages will be received.
     *
     * This progression continues until we reach M rounds, where M = number of
     * traitor generals.  The total number of orders that each general should
     * expect is the summation of all of these rounds of orders (messages):
     */

    /* If this asserts, we have a coding error for input arguments */
    assert(total_number_generals_ > 0);

    number_rounds_ = number_traitor_generals_ + 1;

    /* In our base case, round 0, we should expect 1 message */
    unsigned int curr_round_number_messages = 1;
    total_messages_per_lt_general_ = curr_round_number_messages;

    for (unsigned int round = 1; round < number_rounds_; ++round) {
        /* Calculate the number of messages that will be received in this
         * round */
        curr_round_number_messages =
            (curr_round_number_messages * (total_number_generals_ - round));

        /* Keep a running count of the total number of messages each general
         * should expect to receive */
        total_messages_per_lt_general_ += curr_round_number_messages;
    }

    log_.infoStream()
        << "Each general should receive "
        << total_messages_per_lt_general_ << " messages in all.";
}

void CLIHandler::CreateSharedMemoryItems() {
    namespace bi = boost::interprocess;

    /* Remove any previously resident shared memory objects that we've
     * created.  This should only have an effect if we previously terminated
     * prematurely. */
    bi::shared_memory_object::remove(kSharedMemoryName_);

    /* Create a shared memory area for communication amongst the threads */
    assert(segment_ == NULL);
    segment_ = new bi::managed_shared_memory(bi::create_only,
                                             kSharedMemoryName_,
                                             kSharedMemoryMaxSize_);
    assert(segment_ != NULL);

    SharedMemoryMailboxAllocator
        mailbox_allocator(segment_->get_segment_manager());

    /* Create a shared memory area where each general has an inbox for their
     * mail (the messages they receive during the rounds of communication from
     * the other generals).  */
    assert(mailbox_vector_ == NULL);
    mailbox_vector_ = segment_->construct<SharedMemoryMailboxVector>
        (kMailboxVectorName_)(mailbox_allocator);
    assert(mailbox_vector_ != NULL);

    OrderAllocator order_allocator(segment_->get_segment_manager());

    for (unsigned int i = 0; i < total_number_generals_; ++i) {
        Mailbox* inbox = segment_->construct<Mailbox>
            (bi::anonymous_instance)(order_allocator);
        assert(inbox != NULL);
        mailbox_vector_->push_back(inbox);
    }

    /* Set that stores the unique IDs of all of the traitors.  We use this set
     * for coloring nodes in our order tree when we generate graphs */
    SharedMemoryUIntAllocator int_allocator(segment_->get_segment_manager());

    assert(traitor_set_ == NULL);
    traitor_set_ = segment_->construct<SharedMemoryUIntSet>
        (kTraitorSetName_)(std::less<unsigned int>(), int_allocator);
    assert(traitor_set_ != NULL);
}

void CLIHandler::DestroySharedMemoryItems() {
    namespace bi = boost::interprocess;

    /* Saftey check previous creation */
    assert(segment_ != NULL);
    assert(mailbox_vector_ != NULL);

    /* Once all generals have been shut down, we can begin deallocation */
    while (mailbox_vector_->size() > 0) {
        segment_->destroy_ptr(mailbox_vector_->back());
        mailbox_vector_->pop_back();
    }

    assert(segment_->destroy<SharedMemoryMailboxVector>(kMailboxVectorName_) ==
           true);
    mailbox_vector_ = NULL;

    delete segment_;
    segment_ = NULL;

    /* Clean up shared memory objects */
    bi::shared_memory_object::remove(kSharedMemoryName_);
}

void CLIHandler::CreateGeneralThreads() {
    /* Seed for psuedo-random number generator */
    unsigned int seed = time(0);

    /* Number of traitors we need to pick */
    int traitors_needed = number_traitor_generals_;

    /* Safety check previous creation of used objects */
    assert(traitor_set_ != NULL);

    /* Safety check to ensure this function doesn't get
     * called multiple times prior to destruction */
    assert(byzantine_generals_.size() == 0);

    for (unsigned int i = 0; i < total_number_generals_; ++i) {
        bool is_loyal = true;

        /* Determine if this general will be a traitor.  We can do this in O(N)
         * complexity by calculating the probablity that this general will be a
         * traitor using (number of traitors needed) / (number of generals left
         * to choose from). As we get closer to the end of the list, the
         * probability that the general will be chosen converges to 100%.
         *
         * Reference <http://stackoverflow.com/questions/48087/select-a-random-n-elements-from-listt-in-c>
         */
        if (traitors_needed > 0) {
            double number_generals_remaining = total_number_generals_ - i;
            double random_double =
                static_cast<double>(rand_r(&seed)) / RAND_MAX;
            double probability_of_selection =
                (static_cast<double>(traitors_needed)) /
                number_generals_remaining;

            if (random_double < probability_of_selection) {
                /* This general was selected to be a traitor */
                --traitors_needed;
                is_loyal = false;
                log_.noticeStream()
                    << "General " << i << " randomly chosen to be disloyal.";
                traitor_set_->insert(i);
            }
        }

        /* Create general threads */
        ByzantineGeneralThread* nextGeneral =
            new ByzantineGeneralThread(i,
                                       kSharedMemoryName_,
                                       kMailboxVectorName_,
                                       is_loyal,
                                       total_number_generals_,
                                       total_messages_per_lt_general_,
                                       number_rounds_,
                                       kLogCategoryName_,
                                       generate_dot_graph_,
                                       kTraitorSetName_);

        /* Safety check allocation */
        assert(nextGeneral != NULL);

        /* Place thread in a vector to keep track of it */
        byzantine_generals_.push_back(nextGeneral);
    }

    /* Safety check to ensure we picked enough traitors */
    assert(traitors_needed == 0);
}

void CLIHandler::DestroyGeneralThreads() {
    while (byzantine_generals_.size() > 0) {
        delete (byzantine_generals_.back());
        byzantine_generals_.pop_back();
    }
}

---