teems/Enclave/sort.hpp

#ifndef __SORT_HPP__
#define __SORT_HPP__

#include <functional>

#include "WaksmanNetwork.hpp"

// We have Nr elements to sort, at the beginning of an array of
// allocated size Na items.  Nr and Na are _not_ secret.  The strategy
// is to get the smallest (precomputed) WaksmanNetwork (on a random
// permutation) and WNEvalPlan, each of size Nw, where Nr <= Nw <= Na.
// Nw is also not secret.  Then mark the Nw-Nr items following the given
// elements as padding, use the WaksmanNetwork and WNEvalPlan to shuffle
// the Nw items, then non-obliviously sort the non-padding items.  The
// sort itself is done by making an index array holding just the sort
// keys and original indices into the array, but only of the non-padding
// items.  Sort the index array, and call back a std::function with the
// sorted index array and the shuffled array so that it can read out the
// elements in sorted order.  This function does not have to be
// oblivious to what elements it is reading, because they've already
// been obliviously shuffled.

// Precompute a WaksmanNetwork of size N for a random permutation.  This
// call does not itself use threads, but may be called from a background
// thread.  These are consumed as they are used, so you need to keep
// making more.  Returns the number of WaksmanNetworks available at that
// size.
size_t sort_precompute(uint32_t N);

// Precompute a WNEvalPlan for a given size and number of threads.
// These are not consumed as they are used, so you only need to call
// this once for each (size,nthreads) pair you need.  The precomputation
// itself only uses a single thread, but also may be called from a
// background thread.
void sort_precompute_evalplan(uint32_t N, threadid_t nthreads);

// Shuffle Nr items at the beginning of an allocated array of Na items
// using up to nthreads threads.  The items to shuffle are byte arrays
// of size msg_size.  Return Nw, the size of the Waksman network we
// used, which must satisfy Nr <= Nw <= Na.
uint32_t shuffle_mtobliv(threadid_t nthreads, uint8_t* items, uint16_t msg_size,
    uint32_t Nr, uint32_t Na);

// Perform the sort using up to nthreads threads.  The items to sort are
// byte arrays of size msg_size.  The key is the 10-bit storage server
// id concatenated with the 22-bit uid at the storage server.
void sort_mtobliv(threadid_t nthreads, uint8_t* items, uint16_t msg_size,
    uint32_t Nr, uint32_t Na,
    // the arguments to the callback are items, the sorted indices, and
    // the number of non-padding items
    std::function<void(const uint8_t*, const uint64_t*, uint32_t Nr)>);

#endif