\n";
+
+ size_t idx = 0;
+ for(size_t r = 0ul; r < rows; r++) {
+ os << "
\n";
+ for(size_t c = 0ul; c < columns; c++) {
+ os << "
\n";
+ idx++;
+ }
+ os << "
\n";
+ }
+
+ os << "
\n";
+ os << "\n";
+ os << "\n";
+ os << std::endl;
+}
+
+#include
+#include
+
+/*
+void save_fairness(const int data[], int factor, unsigned nthreads, size_t columns, size_t rows, const std::string & output) {
+ int width = columns * factor;
+ int height = rows / factor;
+
+ int code = 0;
+ int idx = 0;
+ FILE *fp = NULL;
+ png_structp png_ptr = NULL;
+ png_infop info_ptr = NULL;
+ png_bytep row = NULL;
+
+ // Open file for writing (binary mode)
+ fp = fopen(output.c_str(), "wb");
+ if (fp == NULL) {
+ fprintf(stderr, "Could not open file %s for writing\n", output.c_str());
+ code = 1;
+ goto finalise;
+ }
+
+ // Initialize write structure
+ png_ptr = png_create_write_struct(PNG_LIBPNG_VER_STRING, NULL, NULL, NULL);
+ if (png_ptr == NULL) {
+ fprintf(stderr, "Could not allocate write struct\n");
+ code = 1;
+ goto finalise;
+ }
+
+ // Initialize info structure
+ info_ptr = png_create_info_struct(png_ptr);
+ if (info_ptr == NULL) {
+ fprintf(stderr, "Could not allocate info struct\n");
+ code = 1;
+ goto finalise;
+ }
+
+ // Setup Exception handling
+ if (setjmp(png_jmpbuf(png_ptr))) {
+ fprintf(stderr, "Error during png creation\n");
+ code = 1;
+ goto finalise;
+ }
+
+ png_init_io(png_ptr, fp);
+
+ // Write header (8 bit colour depth)
+ png_set_IHDR(png_ptr, info_ptr, width, height,
+ 8, PNG_COLOR_TYPE_RGB, PNG_INTERLACE_NONE,
+ PNG_COMPRESSION_TYPE_BASE, PNG_FILTER_TYPE_BASE);
+
+ png_write_info(png_ptr, info_ptr);
+
+ // Allocate memory for one row (3 bytes per pixel - RGB)
+ row = (png_bytep) malloc(3 * width * sizeof(png_byte));
+
+ // Write image data
+ int x, y;
+ for (y=0 ; y= 0);
+ idx++;
+
+ double angle = double(color) / double(nthreads);
+
+ auto c = hsv2rgb({ 360.0 * angle, 0.8, 0.8 });
+
+ r = char(c.r * 255.0);
+ g = char(c.g * 255.0);
+ b = char(c.b * 255.0);
+
+ }
+ png_write_row(png_ptr, row);
+ }
+
+ assert(idx == (rows * columns));
+
+ // End write
+ png_write_end(png_ptr, NULL);
+
+ finalise:
+ if (fp != NULL) fclose(fp);
+ if (info_ptr != NULL) png_free_data(png_ptr, info_ptr, PNG_FREE_ALL, -1);
+ if (png_ptr != NULL) png_destroy_write_struct(&png_ptr, (png_infopp)NULL);
+ if (row != NULL) free(row);
+}
+*/
Index: doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp
===================================================================
--- doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -37,4 +37,35 @@
};
+static inline bool bts(std::atomic_size_t & target, size_t bit ) {
+ //*
+ int result = 0;
+ asm volatile(
+ "LOCK btsq %[bit], %[target]\n\t"
+ :"=@ccc" (result)
+ : [target] "m" (target), [bit] "r" (bit)
+ );
+ return result != 0;
+ /*/
+ size_t mask = 1ul << bit;
+ size_t ret = target.fetch_or(mask, std::memory_order_relaxed);
+ return (ret & mask) != 0;
+ //*/
+}
+
+static inline bool btr(std::atomic_size_t & target, size_t bit ) {
+ //*
+ int result = 0;
+ asm volatile(
+ "LOCK btrq %[bit], %[target]\n\t"
+ :"=@ccc" (result)
+ : [target] "m" (target), [bit] "r" (bit)
+ );
+ return result != 0;
+ /*/
+ size_t mask = 1ul << bit;
+ size_t ret = target.fetch_and(~mask, std::memory_order_relaxed);
+ return (ret & mask) != 0;
+ //*/
+}
extern bool enable_stats;
@@ -48,4 +79,16 @@
size_t attempt = 0;
size_t success = 0;
+ size_t mask_attempt = 0;
+ } pop;
+};
+
+struct empty_stat {
+ struct {
+ size_t value = 0;
+ size_t count = 0;
+ } push;
+ struct {
+ size_t value = 0;
+ size_t count = 0;
} pop;
};
@@ -62,19 +105,22 @@
static_assert(std::is_same>::value, "Node must have a links field");
-
public:
relaxed_list(unsigned numLists)
- : numNonEmpty{0}
- , lists(new intrusive_queue_t[numLists])
+ : lists(new intrusive_queue_t[numLists])
, numLists(numLists)
- {}
+ {
+ assertf(7 * 8 * 8 >= numLists, "List currently only supports 448 sublists");
+ // assert(sizeof(*this) == 128);
+ std::cout << "Constructing Relaxed List with " << numLists << std::endl;
+
+ #ifndef NO_STATS
+ if(head) this->next = head;
+ head = this;
+ #endif
+ }
~relaxed_list() {
+ std::cout << "Destroying Relaxed List" << std::endl;
lists.reset();
- #ifndef NO_STATS
- std::cout << "Difference : "
- << ssize_t(double(intrusive_queue_t::stat::dif.value) / intrusive_queue_t::stat::dif.num ) << " avg\t"
- << intrusive_queue_t::stat::dif.max << "max" << std::endl;
- #endif
}
@@ -84,5 +130,5 @@
while(true) {
// Pick a random list
- int i = tls.rng.next() % numLists;
+ unsigned i = tls.rng.next() % numLists;
#ifndef NO_STATS
@@ -93,6 +139,16 @@
if( !lists[i].lock.try_lock() ) continue;
+ __attribute__((unused)) int num = numNonEmpty;
+
// Actually push it
- lists[i].push(node, numNonEmpty);
+ if(lists[i].push(node)) {
+ numNonEmpty++;
+ size_t qword = i >> 6ull;
+ size_t bit = i & 63ull;
+ assertf((list_mask[qword] & (1ul << bit)) == 0, "Before set %zu:%zu (%u), %zx & %zx", qword, bit, i, list_mask[qword].load(), (1ul << bit));
+ __attribute__((unused)) bool ret = bts(list_mask[qword], bit);
+ assert(!ret);
+ assertf((list_mask[qword] & (1ul << bit)) != 0, "After set %zu:%zu (%u), %zx & %zx", qword, bit, i, list_mask[qword].load(), (1ul << bit));
+ }
assert(numNonEmpty <= (int)numLists);
@@ -102,4 +158,6 @@
#ifndef NO_STATS
tls.pick.push.success++;
+ tls.empty.push.value += num;
+ tls.empty.push.count += 1;
#endif
return;
@@ -108,47 +166,121 @@
__attribute__((noinline, hot)) node_t * pop() {
- while(numNonEmpty != 0) {
- // Pick two lists at random
- int i = tls.rng.next() % numLists;
- int j = tls.rng.next() % numLists;
-
- #ifndef NO_STATS
- tls.pick.pop.attempt++;
- #endif
-
- // Pick the bet list
- int w = i;
- if( __builtin_expect(lists[j].ts() != 0, true) ) {
- w = (lists[i].ts() < lists[j].ts()) ? i : j;
- }
-
- auto & list = lists[w];
- // If list looks empty retry
- if( list.ts() == 0 ) continue;
-
- // If we can't get the lock retry
- if( !list.lock.try_lock() ) continue;
-
- // If list is empty, unlock and retry
- if( list.ts() == 0 ) {
- list.lock.unlock();
- continue;
- }
-
- // Actually pop the list
- auto node = list.pop(numNonEmpty);
- assert(node);
-
- // Unlock and return
- list.lock.unlock();
- assert(numNonEmpty >= 0);
- #ifndef NO_STATS
- tls.pick.pop.success++;
- #endif
- return node;
- }
+ #if !defined(NO_BITMASK)
+ // for(int r = 0; r < 10 && numNonEmpty != 0; r++) {
+ // // Pick two lists at random
+ // unsigned i = tls.rng.next() % numLists;
+ // unsigned j = tls.rng.next() % numLists;
+
+ // if(auto node = try_pop(i, j)) return node;
+ // }
+ int nnempty;
+ while(0 != (nnempty = numNonEmpty)) {
+ tls.pick.pop.mask_attempt++;
+ unsigned i, j;
+ // if( numLists < 4 || (numLists / nnempty) < 4 ) {
+ // // Pick two lists at random
+ // i = tls.rng.next() % numLists;
+ // j = tls.rng.next() % numLists;
+ // } else
+ {
+ #ifndef NO_STATS
+ // tls.pick.push.mask_attempt++;
+ #endif
+
+ // Pick two lists at random
+ unsigned num = ((numLists - 1) >> 6) + 1;
+
+ unsigned ri = tls.rng.next();
+ unsigned rj = tls.rng.next();
+
+ unsigned wdxi = (ri >> 6u) % num;
+ unsigned wdxj = (rj >> 6u) % num;
+
+ size_t maski = list_mask[wdxi].load(std::memory_order_relaxed);
+ size_t maskj = list_mask[wdxj].load(std::memory_order_relaxed);
+
+ if(maski == 0 && maskj == 0) continue;
+
+ unsigned bi = rand_bit(ri, maski);
+ unsigned bj = rand_bit(rj, maskj);
+
+ assertf(bi < 64, "%zu %u", maski, bi);
+ assertf(bj < 64, "%zu %u", maskj, bj);
+
+ i = bi | (wdxi << 6);
+ j = bj | (wdxj << 6);
+
+ assertf(i < numLists, "%u", wdxi << 6);
+ assertf(j < numLists, "%u", wdxj << 6);
+ }
+
+ if(auto node = try_pop(i, j)) return node;
+ }
+ #else
+ while(numNonEmpty != 0) {
+ // Pick two lists at random
+ int i = tls.rng.next() % numLists;
+ int j = tls.rng.next() % numLists;
+
+ if(auto node = try_pop(i, j)) return node;
+ }
+ #endif
return nullptr;
}
+
+private:
+ node_t * try_pop(unsigned i, unsigned j) {
+ #ifndef NO_STATS
+ tls.pick.pop.attempt++;
+ #endif
+
+ // Pick the bet list
+ int w = i;
+ if( __builtin_expect(lists[j].ts() != 0, true) ) {
+ w = (lists[i].ts() < lists[j].ts()) ? i : j;
+ }
+
+ auto & list = lists[w];
+ // If list looks empty retry
+ if( list.ts() == 0 ) return nullptr;
+
+ // If we can't get the lock retry
+ if( !list.lock.try_lock() ) return nullptr;
+
+ __attribute__((unused)) int num = numNonEmpty;
+
+ // If list is empty, unlock and retry
+ if( list.ts() == 0 ) {
+ list.lock.unlock();
+ return nullptr;
+ }
+
+ // Actually pop the list
+ node_t * node;
+ bool emptied;
+ std::tie(node, emptied) = list.pop();
+ assert(node);
+
+ if(emptied) {
+ numNonEmpty--;
+ size_t qword = w >> 6ull;
+ size_t bit = w & 63ull;
+ assert((list_mask[qword] & (1ul << bit)) != 0);
+ __attribute__((unused)) bool ret = btr(list_mask[qword], bit);
+ assert(ret);
+ assert((list_mask[qword] & (1ul << bit)) == 0);
+ }
+
+ // Unlock and return
+ list.lock.unlock();
+ assert(numNonEmpty >= 0);
+ #ifndef NO_STATS
+ tls.pick.pop.success++;
+ tls.empty.pop.value += num;
+ tls.empty.pop.count += 1;
+ #endif
+ return node;
+ }
private:
@@ -162,10 +294,8 @@
struct stat {
ssize_t diff = 0;
-
- static struct Dif {
- ssize_t value = 0;
- size_t num = 0;
- ssize_t max = 0;
- } dif;
+ size_t push = 0;
+ size_t pop = 0;
+ // size_t value = 0;
+ // size_t count = 0;
};
@@ -178,7 +308,12 @@
sentinel_t before;
sentinel_t after;
- stat s;
-
+ #ifndef NO_STATS
+ stat s;
+ #endif
+
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Winvalid-offsetof"
static constexpr auto fields_offset = offsetof( node_t, _links );
+#pragma GCC diagnostic pop
public:
intrusive_queue_t()
@@ -186,21 +321,15 @@
, after {{ head(), nullptr }}
{
- assert((reinterpret_cast( head() ) + fields_offset) == reinterpret_cast(&before));
- assert((reinterpret_cast( tail() ) + fields_offset) == reinterpret_cast(&after ));
- assert(head()->_links.prev == nullptr);
- assert(head()->_links.next == tail() );
- assert(tail()->_links.next == nullptr);
- assert(tail()->_links.prev == head() );
- assert(sizeof(*this) == 128);
- assert((intptr_t(this) % 128) == 0);
- }
-
- ~intrusive_queue_t() {
- #ifndef NO_STATS
- stat::dif.value+= s.diff;
- stat::dif.num ++;
- stat::dif.max = std::abs(stat::dif.max) > std::abs(s.diff) ? stat::dif.max : s.diff;
- #endif
- }
+ /* paranoid */ assert((reinterpret_cast( head() ) + fields_offset) == reinterpret_cast(&before));
+ /* paranoid */ assert((reinterpret_cast( tail() ) + fields_offset) == reinterpret_cast(&after ));
+ /* paranoid */ assert(head()->_links.prev == nullptr);
+ /* paranoid */ assert(head()->_links.next == tail() );
+ /* paranoid */ assert(tail()->_links.next == nullptr);
+ /* paranoid */ assert(tail()->_links.prev == head() );
+ /* paranoid */ assert(sizeof(*this) == 128);
+ /* paranoid */ assert((intptr_t(this) % 128) == 0);
+ }
+
+ ~intrusive_queue_t() = default;
inline node_t * head() const {
@@ -220,5 +349,5 @@
}
- inline void push(node_t * node, std::atomic_int & nonEmpty) {
+ inline bool push(node_t * node) {
assert(lock);
assert(node->_links.ts != 0);
@@ -232,14 +361,19 @@
prev->_links.next = node;
tail->_links.prev = node;
+ #ifndef NO_STATS
+ if(enable_stats) {
+ s.diff++;
+ s.push++;
+ }
+ #endif
if(before._links.ts == 0l) {
- nonEmpty += 1;
before._links.ts = node->_links.ts;
- }
- #ifndef NO_STATS
- if(enable_stats) s.diff++;
- #endif
- }
-
- inline node_t * pop(std::atomic_int & nonEmpty) {
+ assert(node->_links.prev == this->head());
+ return true;
+ }
+ return false;
+ }
+
+ inline std::pair pop() {
assert(lock);
node_t * head = this->head();
@@ -248,12 +382,18 @@
node_t * node = head->_links.next;
node_t * next = node->_links.next;
- if(node == tail) return nullptr;
+ if(node == tail) return {nullptr, false};
head->_links.next = next;
next->_links.prev = head;
+ #ifndef NO_STATS
+ if(enable_stats) {
+ s.diff--;
+ s.pop ++;
+ }
+ #endif
if(next == tail) {
before._links.ts = 0l;
- nonEmpty -= 1;
+ return {node, true};
}
else {
@@ -261,9 +401,6 @@
before._links.ts = next->_links.ts;
assert(before._links.ts != 0);
- }
- #ifndef NO_STATS
- if(enable_stats) s.diff--;
- #endif
- return node;
+ return {node, false};
+ }
}
@@ -277,10 +414,13 @@
static __attribute__((aligned(128))) thread_local struct TLS {
- Random rng = { int(rdtscl()) };
- pick_stat pick;
+ Random rng = { int(rdtscl()) };
+ pick_stat pick;
+ empty_stat empty;
} tls;
+public:
+ std::atomic_int numNonEmpty = { 0 }; // number of non-empty lists
+ std::atomic_size_t list_mask[7] = { {0}, {0}, {0}, {0}, {0}, {0}, {0} }; // which queues are empty
private:
- std::atomic_int numNonEmpty; // number of non-empty lists
__attribute__((aligned(64))) std::unique_ptr lists;
const unsigned numLists;
@@ -288,3 +428,92 @@
public:
static const constexpr size_t sizeof_queue = sizeof(intrusive_queue_t);
+
+#ifndef NO_STATS
+ static void stats_print(std::ostream & os) {
+ auto it = head;
+ while(it) {
+ it->stats_print_local(os);
+ it = it->next;
+ }
+ }
+
+ static void stats_tls_tally() {
+ global_stats.pick.push.attempt += tls.pick.push.attempt;
+ global_stats.pick.push.success += tls.pick.push.success;
+ global_stats.pick.pop .attempt += tls.pick.pop.attempt;
+ global_stats.pick.pop .success += tls.pick.pop.success;
+ global_stats.pick.pop .mask_attempt += tls.pick.pop.mask_attempt;
+
+ global_stats.qstat.push.value += tls.empty.push.value;
+ global_stats.qstat.push.count += tls.empty.push.count;
+ global_stats.qstat.pop .value += tls.empty.pop .value;
+ global_stats.qstat.pop .count += tls.empty.pop .count;
+ }
+
+private:
+ static struct GlobalStats {
+ struct {
+ struct {
+ std::atomic_size_t attempt = { 0 };
+ std::atomic_size_t success = { 0 };
+ } push;
+ struct {
+ std::atomic_size_t attempt = { 0 };
+ std::atomic_size_t success = { 0 };
+ std::atomic_size_t mask_attempt = { 0 };
+ } pop;
+ } pick;
+ struct {
+ struct {
+ std::atomic_size_t value = { 0 };
+ std::atomic_size_t count = { 0 };
+ } push;
+ struct {
+ std::atomic_size_t value = { 0 };
+ std::atomic_size_t count = { 0 };
+ } pop;
+ } qstat;
+ } global_stats;
+
+ // Link list of all lists for stats
+ __attribute__((aligned(64))) relaxed_list * next = nullptr;
+
+ static relaxed_list * head;
+
+ void stats_print_local(std::ostream & os ) {
+ std::cout << "----- Relaxed List Stats -----" << std::endl;
+ {
+ ssize_t diff = 0;
+ size_t num = 0;
+ ssize_t max = 0;
+
+ for(size_t i = 0; i < numLists; i++) {
+ const auto & list = lists[i];
+ diff+= list.s.diff;
+ num ++;
+ max = std::abs(max) > std::abs(list.s.diff) ? max : list.s.diff;
+ os << "Local Q ops : " << (list.s.push + list.s.pop) << "(" << list.s.push << "i, " << list.s.pop << "o)\n";
+ }
+
+ os << "Difference : " << ssize_t(double(diff) / num ) << " avg\t" << max << "max" << std::endl;
+ }
+
+ const auto & global = global_stats;
+
+ double push_sur = (100.0 * double(global.pick.push.success) / global.pick.push.attempt);
+ double pop_sur = (100.0 * double(global.pick.pop .success) / global.pick.pop .attempt);
+ double mpop_sur = (100.0 * double(global.pick.pop .success) / global.pick.pop .mask_attempt);
+
+ os << "Push Pick % : " << push_sur << "(" << global.pick.push.success << " / " << global.pick.push.attempt << ")\n";
+ os << "Pop Pick % : " << pop_sur << "(" << global.pick.pop .success << " / " << global.pick.pop .attempt << ")\n";
+ os << "TryPop Pick % : " << mpop_sur << "(" << global.pick.pop .success << " / " << global.pick.pop .mask_attempt << ")\n";
+
+ double avgQ_push = double(global.qstat.push.value) / global.qstat.push.count;
+ double avgQ_pop = double(global.qstat.pop .value) / global.qstat.pop .count;
+ double avgQ = double(global.qstat.push.value + global.qstat.pop .value) / (global.qstat.push.count + global.qstat.pop .count);
+ os << "Push Avg Qs : " << avgQ_push << " (" << global.qstat.push.count << "ops)\n";
+ os << "Pop Avg Qs : " << avgQ_pop << " (" << global.qstat.pop .count << "ops)\n";
+ os << "Global Avg Qs : " << avgQ << " (" << (global.qstat.push.count + global.qstat.pop .count) << "ops)\n";
+ }
+#endif
};
Index: doc/theses/thierry_delisle_PhD/code/relaxed_list_layout.cpp
===================================================================
--- doc/theses/thierry_delisle_PhD/code/relaxed_list_layout.cpp (revision a50502128f8eabae54ded84a8ab9885411aad583)
+++ doc/theses/thierry_delisle_PhD/code/relaxed_list_layout.cpp (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -0,0 +1,23 @@
+#define NO_IO
+#define NDEBUG
+#include "relaxed_list.hpp"
+
+struct __attribute__((aligned(64))) Node {
+ static std::atomic_size_t creates;
+ static std::atomic_size_t destroys;
+
+ _LinksFields_t _links;
+
+ int value;
+ Node(int value): value(value) {
+ creates++;
+ }
+
+ ~Node() {
+ destroys++;
+ }
+};
+
+int main() {
+ return sizeof(relaxed_list) + relaxed_list::sizeof_queue;
+}
Index: doc/theses/thierry_delisle_PhD/code/scale.sh
===================================================================
--- doc/theses/thierry_delisle_PhD/code/scale.sh (revision a50502128f8eabae54ded84a8ab9885411aad583)
+++ doc/theses/thierry_delisle_PhD/code/scale.sh (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -0,0 +1,7 @@
+#!/bin/bash
+taskset -c 24-31 ./a.out -t 1 -b churn | grep --color -E "(ns|Ops|Running)"
+taskset -c 24-31 ./a.out -t 2 -b churn | grep --color -E "(ns|Ops|Running)"
+taskset -c 24-31 ./a.out -t 4 -b churn | grep --color -E "(ns|Ops|Running)"
+taskset -c 24-31 ./a.out -t 8 -b churn | grep --color -E "(ns|Ops|Running)"
+taskset -c 16-31 ./a.out -t 16 -b churn | grep --color -E "(ns|Ops|Running)"
+taskset -c 0-31 ./a.out -t 32 -b churn | grep --color -E "(ns|Ops|Running)"
Index: doc/theses/thierry_delisle_PhD/code/utils.hpp
===================================================================
--- doc/theses/thierry_delisle_PhD/code/utils.hpp (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ doc/theses/thierry_delisle_PhD/code/utils.hpp (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,4 +10,6 @@
#include
#include
+
+#include
// Barrier from
@@ -56,5 +58,5 @@
}
-void affinity(int tid) {
+static inline void affinity(int tid) {
static int cpus = get_nprocs();
@@ -70,5 +72,5 @@
static const constexpr std::size_t cache_line_size = 64;
-void check_cache_line_size() {
+static inline void check_cache_line_size() {
std::cout << "Checking cache line size" << std::endl;
const std::string cache_file = "/sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size";
@@ -103,2 +105,40 @@
return std::chrono::duration_cast>(std::chrono::duration(seconds)).count();
}
+
+static inline unsigned rand_bit(unsigned rnum, size_t mask) {
+ unsigned bit = mask ? rnum % __builtin_popcountl(mask) : 0;
+#if !defined(__BMI2__)
+ uint64_t v = mask; // Input value to find position with rank r.
+ unsigned int r = bit + 1;// Input: bit's desired rank [1-64].
+ unsigned int s; // Output: Resulting position of bit with rank r [1-64]
+ uint64_t a, b, c, d; // Intermediate temporaries for bit count.
+ unsigned int t; // Bit count temporary.
+
+ // Do a normal parallel bit count for a 64-bit integer,
+ // but store all intermediate steps.
+ a = v - ((v >> 1) & ~0UL/3);
+ b = (a & ~0UL/5) + ((a >> 2) & ~0UL/5);
+ c = (b + (b >> 4)) & ~0UL/0x11;
+ d = (c + (c >> 8)) & ~0UL/0x101;
+
+
+ t = (d >> 32) + (d >> 48);
+ // Now do branchless select!
+ s = 64;
+ s -= ((t - r) & 256) >> 3; r -= (t & ((t - r) >> 8));
+ t = (d >> (s - 16)) & 0xff;
+ s -= ((t - r) & 256) >> 4; r -= (t & ((t - r) >> 8));
+ t = (c >> (s - 8)) & 0xf;
+ s -= ((t - r) & 256) >> 5; r -= (t & ((t - r) >> 8));
+ t = (b >> (s - 4)) & 0x7;
+ s -= ((t - r) & 256) >> 6; r -= (t & ((t - r) >> 8));
+ t = (a >> (s - 2)) & 0x3;
+ s -= ((t - r) & 256) >> 7; r -= (t & ((t - r) >> 8));
+ t = (v >> (s - 1)) & 0x1;
+ s -= ((t - r) & 256) >> 8;
+ return s - 1;
+#else
+ uint64_t picked = _pdep_u64(1ul << bit, mask);
+ return picked ? __builtin_ctzl(picked) : 0;
+#endif
+}
Index: doc/theses/thierry_delisle_PhD/comp_II/Makefile
===================================================================
--- doc/theses/thierry_delisle_PhD/comp_II/Makefile (revision a50502128f8eabae54ded84a8ab9885411aad583)
+++ doc/theses/thierry_delisle_PhD/comp_II/Makefile (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -0,0 +1,84 @@
+## Define the configuration variables.
+
+Build = build
+Figures = figures
+Macros = ../../../LaTeXmacros
+TeXLIB = .:${Macros}:${Build}:../../../bibliography:
+LaTeX = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build}
+BibTeX = BIBINPUTS=${TeXLIB} && export BIBINPUTS && bibtex
+
+MAKEFLAGS = --no-print-directory --silent #
+VPATH = ${Build} ${Figures}
+
+## Define the text source files.
+
+SOURCES = ${addsuffix .tex, \
+comp_II \
+}
+
+FIGURES = ${addsuffix .tex, \
+}
+
+PICTURES = ${addsuffix .pstex, \
+}
+
+PROGRAMS = ${addsuffix .tex, \
+}
+
+GRAPHS = ${addsuffix .tex, \
+}
+
+## Define the documents that need to be made.
+
+DOCUMENT = comp_II.pdf
+BASE = ${basename ${DOCUMENT}}
+
+# Directives #
+
+.PHONY : all clean # not file names
+
+all : ${DOCUMENT}
+
+clean :
+ @rm -frv ${DOCUMENT} ${BASE}.ps ${Build}
+
+# File Dependencies #
+
+${DOCUMENT} : ${BASE}.ps
+ ps2pdf $<
+
+${BASE}.ps : ${BASE}.dvi
+ dvips ${Build}/$< -o $@
+
+${BASE}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \
+ ${Macros}/common.tex ${Macros}/indexstyle ../../../bibliography/pl.bib \
+ local.bib glossary.tex | ${Build}
+ # Must have *.aux file containing citations for bibtex
+ if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi
+ -${BibTeX} ${Build}/${basename $@}
+ # Some citations reference others so run again to resolve these citations
+ ${LaTeX} ${basename $@}.tex
+ -${BibTeX} ${Build}/${basename $@}
+ # Make index from *.aux entries and input index at end of document
+ makeglossaries -q -s ${Build}/${basename $@}.ist ${Build}/${basename $@}
+ # Run again to finish citations
+ ${LaTeX} ${basename $@}.tex
+
+## Define the default recipes.
+
+${Build}:
+ mkdir -p ${Build}
+
+%.tex : %.fig ${Build}
+ fig2dev -L eepic $< > ${Build}/$@
+
+%.ps : %.fig | ${Build}
+ fig2dev -L ps $< > ${Build}/$@
+
+%.pstex : %.fig | ${Build}
+ fig2dev -L pstex $< > ${Build}/$@
+ fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t
+
+# Local Variables: #
+# compile-command: "make" #
+# End: #
Index: doc/theses/thierry_delisle_PhD/comp_II/comp_II.tex
===================================================================
--- doc/theses/thierry_delisle_PhD/comp_II/comp_II.tex (revision a50502128f8eabae54ded84a8ab9885411aad583)
+++ doc/theses/thierry_delisle_PhD/comp_II/comp_II.tex (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -0,0 +1,191 @@
+\documentclass[11pt,fullpage]{article}
+\usepackage[T1]{fontenc}
+\usepackage[utf8]{inputenc}
+\usepackage{listings} % for code listings
+\usepackage{xspace}
+\usepackage{xcolor}
+\usepackage{graphicx}
+\usepackage[hidelinks]{hyperref}
+\usepackage{glossaries}
+\usepackage{textcomp}
+\usepackage{geometry}
+
+% cfa macros used in the document
+\input{common}
+\input{glossary}
+
+\CFAStyle % use default CFA format-style
+
+\title{
+ \Huge \vspace*{1in} The \CFA Scheduler\\
+ \huge \vspace*{0.25in} PhD Comprehensive II Research Proposal
+ \vspace*{1in}
+}
+
+\author{
+ \huge Thierry Delisle \\
+ \Large \vspace*{0.1in} \texttt{tdelisle@uwaterloo.ca} \\
+ \Large Cheriton School of Computer Science \\
+ \Large University of Waterloo
+}
+
+\date{
+ \today
+}
+
+\begin{document}
+\maketitle
+\cleardoublepage
+
+\newcommand{\cit}{\textsuperscript{[Citation Needed]}\xspace}
+\newcommand{\TODO}{~\newline{\large\bf\color{red} TODO :}\xspace}
+
+% ===============================================================================
+% ===============================================================================
+
+\tableofcontents
+
+% ===============================================================================
+% ===============================================================================
+\newpage
+\section{Introduction}
+\subsection{\CFA and the \CFA concurrency package}
+\CFA\cit is a modern, polymorphic, non-object-oriented, backwards-compatible extension of the C programming language. It aims to add high productivity features while maintaning the predictible performance of C. As such concurrency in \CFA\cit aims to offer simple and safe high-level tools while still allowing performant code. Concurrent code is written in the syncrhonous programming paradigm but uses \glspl{uthrd} in order to achieve the simplicity and maintainability of synchronous programming without sacrificing the efficiency of asynchronous programing. As such the \CFA scheduler is a user-level scheduler that maps \glspl{uthrd} onto \glspl{kthrd}.
+
+The goal of this research is to produce a scheduler that is simple to use and offers acceptable performance in all cases. Here simplicity does not refer to the API but to how much scheduling concerns programmers need to take into account when using the \CFA concurrency package. Therefore, the main goal of this proposal is as follows :
+\begin{quote}
+The \CFA scheduler should be \emph{viable} for any workload.
+\end{quote}
+
+This objective includes producing a scheduling strategy with minimal fairness guarantees, creating an abstraction layer over the operating system to handle kernel-threads spinning unnecessarily and hide blocking I/O operations and, writing sufficient library tools to allow developpers to properly use the scheduler.
+
+% ===============================================================================
+% ===============================================================================
+
+\section{Scheduling for \CFA}
+While the \CFA concurrency package doesn't have any particular scheduling needs beyond those of any concurrency package which uses \glspl{uthrd}, it is important that the default \CFA Scheduler be viable in general. Indeed, since the \CFA Scheduler does not target any specific workloads, it is unrealistic to demand that it use the best scheduling strategy in all cases. However, it should offer a viable ``out of the box'' solution for most scheduling problems so that programmers can quickly write performant concurrent without needed to think about which scheduling strategy is more appropriate for their workload. Indeed, only programmers with exceptionnaly high performance requirements should need to write their own scheduler. More specifically, two broad types of schedulering strategies should be avoided in order to avoid penalizing certain types of workloads : feedback-based and priority schedulers.
+
+\subsection{Feedback-Based Schedulers}
+Many operating systems use schedulers based on feadback loops in some form, they measure how much CPU a particular thread has used\footnote{Different metrics can be used to here but it is not relevant to the discussion.} and schedule threads based on this metric. These strategies are sensible for operating systems but rely on two assumptions on the workload :
+
+\begin{enumerate}
+ \item Threads live long enough to be scheduled many times.
+ \item Cooperation among all threads is not simply infeasible, it is a security risk.
+\end{enumerate}
+
+While these two assumptions generally hold for operating systems, they may not for \CFA programs. In fact, \CFA uses \glspl{uthrd} which have the explicit goal of reducing the cost of threading primitives to allow many smaller threads. This can naturally lead to have threads with much shorter lifetime and only being scheduled a few times. Scheduling strategies based on feadback loops cannot be effective in these cases because they will not have the opportunity to measure the metrics that underlay the algorithm. Note that the problem of feadback loop convergence (reacting too slowly to scheduling events) is not specific to short lived threads but can also occur with threads that show drastic changes in scheduling event, e.g., threads running for long periods of time and then suddenly blocking and unblocking quickly and repeatedly.
+
+In the context of operating systems, these concerns can be overshadowed by a more pressing concern : security. When multiple users are involved, it is possible that some users are malevolent and try to exploit the scheduling strategy in order to achieve some nefarious objective. Security concerns mean that more precise and robust fairness metrics must be used. In the case of the \CFA scheduler, every thread runs in the same user-space and are controlled from the same user. It is then possible to safely ignore the possibility that threads are malevolent and assume that all threads will ignore or cooperate with each other. This allows for a much simpler fairness metric and in this proposal ``fairness'' will be considered as equal opportunities to run once scheduled.
+
+Since feadback is not necessarily feasible within the lifetime of all threads and a simple fairness metric can be used, the scheduling strategy proposed for the \CFA runtime does not user per-threads feedback. Feedback loops in general are not rejected for secondary concerns like idle sleep, but no feedback loop is used to decide which thread to run next.
+
+\subsection{Priority Schedulers}
+Another broad category of schedulers are priority schedulers. In these scheduling strategies threads have priorities and the runtime schedules the threads with the highest priority before scheduling other threads. Threads with equal priority are scheduled using a secondary strategy, often something simple like round-robin or FIFO. These priority mean that, as long as there is a thread with a higher priority that desires to run, a thread with a lower priority will not run. This possible starving of threads can dramatically increase programming complexity since starving threads and priority inversion (prioritising a lower priority thread) can both lead to serious problems, leaving programmers between a rock and a hard place.
+
+An important observation to make is that threads do not need to have explicit priorities for problems to be possible. Indeed, any system with multiple ready-queues and attempts to exhaust one queue before accessing the other queues, could encounter starvation problems. A popular scheduling strategy that suffers from implicit priorities is work-stealing. Work-stealing is generally presented as follows :
+
+\begin{itemize}
+ \item Each processor has a list of threads.
+\end{itemize}
+\begin{enumerate}
+ \item Run threads from ``this'' processor's list.
+ \item If ``this'' processor's list is empty, run threads from some other processor's list.
+\end{enumerate}
+
+In a loaded system\footnote{A loaded system is a system where threads are being run at the same rate they are scheduled}, if a thread does not yield or block for an extended period of time, threads on the same processor list will starve if no other processors can exhaust their list.
+
+Since priorities can be complex to handle for programmers, the scheduling strategy proposed for the \CFA runtime does not use a strategy with either implicit or explicit thread priorities.
+
+\subsection{Schedulers without feadback or priorities}
+I claim that the ideal default scheduler for the \CFA runtime is a scheduler that offers good scalability and a simple fairness guarantee that is easy for programmers to reason about. The simplest fairness guarantee is to guarantee FIFO ordering, i.e., threads scheduled first will run first. However, enforcing FIFO ordering generally conflicts with scalability across multiple processors because of the additionnal synchronization. Thankfully, strict FIFO is not needed for scheduling. Since concurrency is inherently non-deterministic, fairness concerns in scheduling are only a problem if a thread repeatedly runs before another thread can run\footnote{This is because the non-determinism means that programmers must already handle ordering problems in order to produce correct code and already must rely on weak guarantees, for example that a specific thread will \emph{eventually} run.}. This need for unfairness to persist before problems occur means that the FIFO fairness guarantee can be significantly relaxed without causing problems. For this proposal, the target guarantee is that the \CFA scheduler guarantees \emph{probable} FIFO ordering, which is defined as follows :
+\begin{itemize}
+ \item Given two threads $X$ and $Y$, the odds that thread $X$ runs $N$ times \emph{after} thread $Y$ is scheduled but \emph{before} it is run, decreases exponentially with regards to $N$.
+\end{itemize}
+
+While this is not a strong guarantee, the probability that problems persist for long period of times decreases exponentially, making persisting problems virtually impossible.
+
+\subsection{Real-Time}
+While the objective of this proposed scheduler is similar to the objective of real-time scheduling, this proposal is not a proposal for real-time scheduler and as such makes no attempt to offer either soft or hard guarantees on scheduling delays.
+
+% ===============================================================================
+% ===============================================================================
+\section{Proposal}
+
+\subsection{Ready-Queue}
+Using trevor's paper\cit as basis, it is simple to build a relaxed FIFO list that is fast and scalable for loaded or overloaded systems. The described queue uses an array of underlying strictly FIFO queue. Pushing new data is done by selecting one of these underlying queues at random, recording a timestamp for the push and pushing to the selected queue. Popping is done by selecting two queues at random and popping from the queue for which the head has the oldest timestamp. In loaded or overloaded systems, it is higly likely that the queues is far from empty, e.i., several tasks are on each of the underlying queues. This means that selecting a queue at random to pop from is higly likely to yield a queue that is not empty.
+
+When the ready queue is "more empty", i.e., several of the inner queues are empty, selecting a random queue for popping is less likely to yield a valid selection and more attempts need to be made, resulting in a performance degradation. In cases, with few elements on the ready queue and few processors running, performance can be improved by adding information to help processors find which inner queues are used. Preliminary performance tests indicate that with few processors, a bitmask can be used to identify which inner queues are currently in use. This is especially effective in the single-thread case, where the bitmask will always be up-to-date. Furthermore, modern x86 CPUs have a BMI2 extension which allow using the bitmask with very little overhead over directly accessing the readyqueue offerring decent performance even in cases with many empty inner queues. This technique does not solve the problem completely, it randomly attempts to find a block of 64 queues where at least one is used, instead of attempting to find a used queue. For systems with a large number of cores this does not completely solve the problem, but it is a fixed improvement. The size of the blocks are limited by the maximum size atomic instruction can operate on, therefore atomic instructions on large words would increase the 64 queues per block limit.
+
+\TODO double check the next sentence
+Preliminary result indicate that the bitmask approach with the BMI2 extension can lead to multi-threaded performance that is contention agnostic in the worst case.
+This result suggests that the contention penalty and the increase performance for additionnal thread cancel each other exactly. This may indicate that a relatively small reduction in contention may tip the performance into positive scalling even for the worst case. It can be noted that in cases of high-contention, the use of the bitmask to find queues that are not empty is much less reliable. Indeed, if contention on the bitmask is high, it means it probably changes significantly between the moment it is read and the actual operation on the queues it represents. Furthermore, the objective of the bitmask is to avoid probing queues that are empty. Therefore, in cases where the bitmask is highly contented, it may be preferrable to probe queues randomly, either until contention decreases or until a prior prefetch of the bitmask completes. Ideally, the scheduler would be able to observe that the bitmask is highly contented and adjust its behaviour appropriately. However, I am not aware of any mechanism to query whether a cacheline is in cache or to run other instructions until a cacheline is fetch without blocking on the cacheline. As such, an alternative that may have a similar impact would be for each thread to have their own bitmask, which would be updated both after each scheduler action and after a certain number of failed probing. If the bitmask has little contention, the local bitmask will be mostly up-to-date and several threads won't need to contend as much on the global bitmask. If the bitmask has significant contention, then fetching it becomes more expensive and threads may as well probe randomly. This solution claims that probing randomly or against an out-of-date bitmask is equivalent.
+
+In cases where this is insufficient, another approach is to use a hiearchical data structure. Creating a tree of nodes to reduce contention has been shown to work in similar cases\cit(SNZI: Scalable NonZero Indicators)\footnote{This particular paper seems to be patented in the US. How does that affect \CFA? Can I use it in my work?}. However, this approach may lead to poorer single-threaded performance due to the inherent pointer chasing, as such, it was not considered as the first approach but as a fallback in case the bitmask approach does not satisfy the performance goals.
+
+Part of this performance relies on contention being low when there are few threads on the readyqueue. However, this can be assumed reliably if the system handles putting idle processors to sleep, which is addressed in section \ref{sleep}.
+
+\paragraph{Objectives and Existing Work}
+How much scalability is actually needed is highly debatable, libfibre\cit is has compared favorably to other schedulers in webserver tests\cit and uses a single atomic counter in its scheduling algorithm similarly to the proposed bitmask. As such the single atomic instruction on a shared cacheline may be sufficiently performant.
+
+I have built a prototype of this ready-queue (including the bitmask and BMI2 usage, but not the sharded bitmask) and ran performance experiments on it but it is difficult to compare this prototype to a thread scheduler as the prototype is used as a data-queue. I have also integrated this prototype into the \CFA runtime, but have not yet created performance experiments to compare results. I believe that the bitmask approach is currently one of the larger risks of the proposal, early tests lead me to believe it may work but it is not clear that the contention problem can be overcome. The worst-case scenario is a case where the number of processors and the number of ready threads are similar, yet scheduling events are very frequent. Fewer threads should lead to the Idle Sleep mechanism reducing contention while having many threads ready leads to optimal performance. It is difficult to evaluate the likeliness of this worst-case scenario in real workloads. I believe, frequent scheduling events suggest a more ``bursty'' workload where new work is finely divided among many threads which race to completion. This type of workload would only see a peek of contention close to the end of the work, but no sustained contention. Very fine-grained pipelines are less ``bursty'', these may lead to more sustained contention. However, they could also easily benefit from a direct hand-off strategy which would circumvent the problem entirely.
+
+\subsection{Dynamic Resizing}
+The \CFA runtime system currently handles dynamically adding and removing processors from clusters at any time. Since this is part of the existing design, the proposed scheduler must also support this behaviour. However, dynamicly resizing the clusters is considered a rare event associated with setup, teardown and major configuration changes. This assumptions is made both in the design of the proposed scheduler as well as in the original design of the \CFA runtime system. As such, the proposed scheduler must honor the correctness of these behaviour but does not have any performance objectives with regards to resizing a cluster. How long adding or removing processors take and how much this disrupts the performance of other threads is considered a secondary concern since it should be amortized over long period of times. This description effectively matches with te description of a Reader-Writer lock, in frequent but invasive updates among frequent (mostly) read operations. In the case of the Ready-Queue described above, read operations are operations that push or pop from the ready-queue but do not invalidate any references to the ready queue data structures. Writes on the other-hand would add or remove inner queues, invalidating references to the array of inner queues in the process. Therefore, the current proposed approach to this problem is the add a per-cluster Reader Writer lock around the ready queue to prevent restructuring of the ready-queue data structure while threads are being pushed or popped.
+
+There are possible alternatives to the Reader Writer lock solution. This problem is effectively a memory reclamation problem and as such there is a large body of research on the subject. However, the RWlock solution is simple and can be leveraged to solve other problems (e.g. processor ordering and memory reclamation of threads) which makes it an attractive solution.
+
+\paragraph{Objectives and Existing Work}
+The lock must offer scalability and performance on par with the actual ready-queue in order not to introduce a new bottle neck. I have already built a lock that fits the desired requirements and preliminary testing show scalability and performance that exceed the target. As such, I do not consider this lock to be a risk on this project.
+
+\subsection{Idle Sleep} \label{sleep}
+As mentionned above, idle sleep is the process of putting processors to sleep while they do not have threads to execute. In this context processors are kernel-threads and sleeping refers to asking the kernel to block a thread. This can be achieved with either thread synchronization operations like pthread\_cond\_wait or using signal operations like sigsuspend.
+
+Support for idle sleep broadly involves calling the operating system to block the kernel thread but also handling the race between the sleeping and the waking up, and handling which kernel thread should sleep or wake-up.
+
+When a processor decides to sleep, there is a race that occurs between it signalling that it will go to sleep (so other processors can find sleeping processors) and actually blocking the kernel thread. This is equivalent to the classic problem of missing signals when using condition variables, the ``sleepy'' processor indicates that it will sleep but has not yet gone to sleep, if another processor attempts to wake it up, the waking-up operation may claim nothing needs to be done and the signal will have been missed. In cases where threads are scheduled from processors on the current cluster, loosing signals is not necessarily critical, because at least some processors on the cluster are awake. Individual processors always finish shceduling threads before looking for new work, which means that the last processor to go to sleep cannot miss threads scheduled from inside the cluster (if they do, that demonstrates the ready-queue is not linearizable). However, this guarantee does not hold if threads are shceduled from outside the cluster, either due to an external event like timers and I/O, or due to a thread migrating from a different cluster. In this case, missed signals can lead to the cluster deadlocking where it should not\footnote{Clusters ``should'' never deadlock, but for this proposal, cases where \CFA users \emph{actually} wrote \CFA code that leads to a deadlock it is considered as a deadlock that ``should'' happen. }. Therefore, it is important that the scheduling of threads include a mechanism where signals \emph{cannot} be missed. For performance reasons, it can be advantageous to have a secondary mechanism that allows signals to be missed in cases where it cannot lead to a deadlock. To be safe, this process must include a ``handshake'' where it is guaranteed that either~: the sleepy processor notices that a thread was scheduled after it signalled its intent to block or code scheduling threads well see the intent to sleep before scheduling and be able to wake-up the processor. This matter is complicated by the fact that pthread offers few tools to implement this solution and offers no guarantee of ordering of threads waking up for most of these tools.
+
+Another issues is trying to avoid kernel sleeping and waking frequently. A possible partial solution is to order the processors so that the one which most recently went to sleep is woken up. This allows other sleeping processors to reach deeper sleep state (when these are available) while keeping ``hot'' processors warmer. Note that while this generally means organising the processors in a stack, I believe that the unique index provided by the ReaderWriter lock can be reused to strictly order the waking order of processors, causing a LIFO like waking order. While a strict LIFO stack is probably better, using the processor index could proove useful and offer a sufficiently LIFO ordering.
+
+Finally, another important aspect of Idle Sleep is when should processors make the decision to sleep and when it is appropriate for sleeping processors to be woken up. Processors that are unnecessarily awake lead to unnecessary contention and power consumption, while too many sleeping processors can lead to sub-optimal throughput. Furthermore, transitions from sleeping to awake and vice-versa also add unnecessary latency. There is already a wealth of research on the subject and I do not plan to implement a novel idea for the Idle Sleep heuristic in this project.
+
+\subsection{Asynchronous I/O}
+The final aspect of this proposal is asynchronous I/O. Without it, user threads that execute I/O operations will block the underlying kernel thread. This leads to poor throughput, it would be preferrable to block the user-thread and reuse the underlying kernel-thread to run other ready threads. This requires intercepting the user-threads' calls to I/O operations, redirecting them to an asynchronous I/O interface and handling the multiplexing between the synchronous and asynchronous API. As such, these are the three components needed to implemented to support asynchronous I/O : an OS abstraction layer over the asynchronous interface, an event-engine to (de)multiplex the operations and a synchronous interface for users to use. None of these components currently exist in \CFA and I will need to build all three for this project.
+
+\paragraph{OS Abstraction}
+One of the fundamental part of this converting blocking I/O operations into non-blocking ones. This relies on having an underlying asynchronous I/O interface to which to direct the I/O operations. While there exists many different APIs for asynchronous I/O, it is not part of this proposal to create a novel API, simply to use an existing one that is sufficient. uC++ uses the \texttt{select} as its interface, which handles pipes and sockets. It entails significant complexity and has performances problems which make it a less interesting alternative. Another interface which is becoming popular recently\cit is \texttt{epoll}. However, epoll also does not handle file system and seems to have problem to linux pipes and \texttt{TTY}s\cit. A very recent alternative that must still be investigated is \texttt{io\_uring}. It claims to address some of the issues with \texttt{epoll} but is too recent to be confident that it does. Finally, a popular cross-platform alternative is \texttt{libuv}, which offers asynchronous sockets and asynchronous file system operations (among other features). However, as a full-featured library it includes much more than what is needed and could conflict with other features of \CFA unless significant efforts are made to merge them together.
+
+\paragraph{Event-Engine}
+Laying on top of the asynchronous interface layer is the event-engine. This engine is responsible for multiplexing (batching) the synchronous I/O requests into an asynchronous I/O request and demultiplexing the results onto appropriate blocked threads. This can be straightforward for the simple cases, but can become quite complex. Decisions that will need to be made include : whether to poll from a seperate kernel thread or a regularly scheduled user thread, what should be the ordering used when results satisfy many requests, how to handle threads waiting for multiple operations, etc.
+
+\paragraph{Interface}
+Finally, for these components to be available, it is necessary to expose them through a synchronous interface. This can be a novel interface but it is preferrable to attempt to intercept the existing POSIX interface in order to be compatible with existing code. This will allow C programs written using this interface to be transparently converted to \CFA with minimal effeort. Where this is not applicable, a novel interface will be created to fill the gaps.
+
+
+% ===============================================================================
+% ===============================================================================
+\section{Discussion}
+
+
+% ===============================================================================
+% ===============================================================================
+\section{Timeline}
+
+
+\cleardoublepage
+
+% B I B L I O G R A P H Y
+% -----------------------------
+\addcontentsline{toc}{chapter}{Bibliography}
+\bibliographystyle{plain}
+\bibliography{pl,local}
+\cleardoublepage
+\phantomsection % allows hyperref to link to the correct page
+
+% G L O S S A R Y
+% -----------------------------
+\addcontentsline{toc}{chapter}{Glossary}
+\printglossary
+\cleardoublepage
+\phantomsection % allows hyperref to link to the correct page
+
+\end{document}
Index: doc/theses/thierry_delisle_PhD/comp_II/comp_II_too_big.tex
===================================================================
--- doc/theses/thierry_delisle_PhD/comp_II/comp_II_too_big.tex (revision a50502128f8eabae54ded84a8ab9885411aad583)
+++ doc/theses/thierry_delisle_PhD/comp_II/comp_II_too_big.tex (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -0,0 +1,316 @@
+\documentclass[11pt,fullpage]{article}
+\usepackage[T1]{fontenc}
+\usepackage[utf8]{inputenc}
+\usepackage{listings} % for code listings
+\usepackage{xspace}
+\usepackage{xcolor}
+\usepackage{graphicx}
+\usepackage[hidelinks]{hyperref}
+\usepackage{glossaries}
+\usepackage{textcomp}
+\usepackage{geometry}
+
+% cfa macros used in the document
+\input{common}
+\input{glossary}
+
+\CFAStyle % use default CFA format-style
+
+\title{
+ \Huge \vspace*{1in} The \CFA Scheduler\\
+ \huge \vspace*{0.25in} PhD Comprehensive II Research Proposal
+ \vspace*{1in}
+}
+
+\author{
+ \huge Thierry Delisle \\
+ \Large \vspace*{0.1in} \texttt{tdelisle@uwaterloo.ca} \\
+ \Large Cheriton School of Computer Science \\
+ \Large University of Waterloo
+}
+
+\date{
+ \today
+}
+
+\begin{document}
+\maketitle
+\cleardoublepage
+
+\newcommand{\cit}{\textsuperscript{[Citation Needed]}\xspace}
+\newcommand{\TODO}{\newline{\large\bf\color{red} TODO :}\xspace}
+
+% ===============================================================================
+% ===============================================================================
+
+\tableofcontents
+
+% ===============================================================================
+% ===============================================================================
+\section{Introduction}
+\subsection{\CFA and the \CFA concurrency package}
+\CFA\cit is a modern, polymorphic, non-object-oriented, backwards-compatible extension of the C programming language. It aims to add high productivity features while maintaning the predictible performance of C. As such concurrency in \CFA\cit aims to offer . Concurrent code is written in the syncrhonous programming paradigm but uses \glspl{uthrd} in order to achieve the simplicity and maintainability of synchronous programming without sacrificing the efficiency of asynchronous programing. As such the \CFA scheduler is a user-level scheduler that maps \glspl{uthrd} onto \glspl{kthrd}
+
+\subsection{Scheduling for \CFA}
+While the \CFA concurrency package doesn't have any particular scheduling needs beyond those of any concurrency package which uses \glspl{uthrd}, it is important that the default \CFA Scheduler be viable in general. Indeed, since the \CFA Scheduler does not target any specific workloads, it is unrealistic to demand that it use the best scheduling strategy in all cases. However, it should offer a viable ``out of the box'' solution for most scheduling problems so that programmers can quickly write performant concurrent without needed to think about which scheduling strategy is more appropriate for their workload. Indeed, only programmers with exceptionnaly high performance requirements should need to write their own scheduler.
+
+As detailed in Section~\ref{metrics}, schedulers can be evaluated according to multiple metrics. It is therefore important to set objective goals for scheduling according to a high-level direction. As such the design goal for the scheduling strategy can be phrased as follows :
+\begin{quote}
+The \CFA scheduling strategy should be \emph{viable} for any workload.
+\end{quote}
+
+% ===============================================================================
+% ===============================================================================
+\section{Scheduling terms}
+Before going into details about scheduling, it is important to define the terms used in this document, especially since many of these terms are often overloaded and may have subtlely different meaning. All scheduling terms used are defined in the Glossary but the following terms are worth explaining now. \TODO fix the glossary ref
+
+\paragraph{\Gls{proc}:} Designates the abstract worker on which the work will be scheduled. The nature of the \gls{proc} can vary depending on the level at which the mapping is done. For example, OS scheduling maps \glspl{kthrd} onto \glspl{hthrd} and therefore in this context the \gls{proc} refers to the \gls{hthrd}. However, in the context of user space scheduling, the scheduler maps \glspl{uthrd}, \glspl{fiber} or \glspl{job} onto \glspl{kthrd}, at this level the \gls{kthrd} becomes the \gls{proc}.
+
+\paragraph{\Gls{at}:} This document uses the term \gls{at} to designate the units of work that are to be scheduled. Like \glspl{proc}, the nature of a \gls{at} varies depending on the level at which the scheduler operates. The \glspl{at} in OS schedulers are \glspl{kthrd}, while the \glspl{at} in user-space scheduling can be \glspl{uthrd}, \glspl{fiber} or \glspl{job}. The term \gls{at} was chosen specifically to avoid collisions with specific types of \gls{at}, \eg thread, \glspl{uthrd} and \glspl{fiber}.
+
+\paragraph{\Gls{Q}:} A \gls{Q} is a list of \glspl{at} that have been \glslink{at}{scheduled} but have yet to be \glslink{atrun}{run}. The number and nature of the \gls{Q} is scheduler specific and is generally a significant portion of the scheduler design.
+
+\paragraph{\Gls{atsched}:} Designates the act of signalling to the scheduler that some \gls{at} is ready to be executed and should eventually be assigned to a \gls{proc}.
+
+\paragraph{\Gls{atrun}:} Designates the act of act of actually running a \gls{at} that was scheduled. That is mapping the \gls{at} onto a specific \gls{proc} and having the \gls{proc} execute its code.
+
+\paragraph{\Gls{atblock}:} A blocked \gls{at} is an \gls{at} that exists outside of any \gls{Q}. Unless some external entity unblocks it (by \glslink{atsched}{scheduling} it), it will never run and will stay in this suspended state. Not all schedulers support blocking. \eg \gls{job} schedulers do not, a new \gls{job} must be created if the current one would need to wait for an external event.
+
+\paragraph{\Gls{atmig}:} A \gls{at} is generally considered to have migrated when it is \glslink{atrun}{run} from a different different \gls{proc} then the previous time it \glslink{atrun}{ran}. This concept is relevant because migration can often come at a performance cost which is mostly due to caching. However, some amount of migration is generally required to achieve load balancing. In the context of \glspl{job}, since \glspl{job} only run once, migration is define as being \glslink{atrun}{run} from a different different \gls{proc} the the one it was created on.
+
+\paragraph{\Gls{atpass}:} A \gls{at} as overtaken another \gls{at} when it was \glslink{atsched}{scheduled} later but \glslink{atrun}{run} before the other \gls{at}. Overtaking can have performance benefits but has obvious fairness concerns.
+
+% =================================================================================================
+% =================================================================================================
+\section{Previous Work}
+
+\subsection{Publications}
+\subsubsection{Work Stealing}
+A populer scheduling algorithm is \emph{Work Stealing}, which was used by \cite{burton1981executing, halstead1984implementation} to divide work among threads to be done in parallel. This specific flavor of work stealing, which maps units of work to be executed once\footnote{This single execution is what fundamentally distinguishes \emph{Jobs} from \emph{Threads}} onto kernel-threads.
+
+There are countless examples of work-stealing variations \cit, all of which shared the same basic idea : each worker has its own set of work units, referred to as work-queue in this document, and once it runs out, it ``steals'' from other worker. Many variations of the algorithm exist but they generally have the following characteristics :
+
+\begin{itemize}
+ \item There exists a one-to-one mapping between \glspl{proc} and \glspl{Q}, \eg every thread has exactly one queue of jobs to execute.
+ \item Once added to a \gls{Q}, \glspl{at} can \glslink{atmig}{migrate} to another \gls{proc} only as a result of the \gls{proc}'s \gls{Q} being empty.
+\end{itemize}
+
+Where \glspl{at} are initially enqueued and what to do with unblocking \glspl{at} (which must be requeued) is generally where the variations occur in the algorithms.
+
+Distributing the \glspl{at} improves fairness\cit, while enqueuing new and recurring \glspl{at} on the same work-queue as they creator and previous \glspl{atrun} respectively improves locality\cit.
+
+
+It is worth pointing out that while both strategy can be very effective for certain workloads\cit
+
+\subsubsection{Other-Schedulers}
+
+\subsubsection{Theoretical Bounds}
+
+
+\subsection{In practice}
+In practive meany implementations seem to have converge towards schedulers which use a one to one mapping between \glspl{proc} and \glspl{Q}, often with one or several lower-priority shared \glspl{Q}. This is generally perceived as an improvement over schedulers with a single \glspl{Q} which can lead to contention problems. As mentionned further into this document, this is due to the implicit assumption that the \gls{Q} data structure cannot scale to many cores.
+
+Schedulers with multiple \glspl{Q} generally achieve better throughput can also introduce fairness related problems. The underlying problem is that these \glspl{Q} lead to priorities based on placement rather than per \gls{at}.
+
+\paragraph{Indefinite Starvation}
+A scheduler can have starve a \gls{at} indefinetely. In practice, schedulers without support for priorities can starve \glspl{at} if it does not have preemption and can fall in a stable state where a \gls{at} never \glslink{atblock}{blocks} and other \glspl{at} can get stuck behind it. If these \glspl{at} are never stolen (taken from a \gls{proc} which isn't the one mapped to that \gls{Q}) then they will be indefinetely starved.
+
+\paragraph{Poor load-balancing}
+If the scheduler reaches a stable state where per-\gls{proc} \glspl{Q} have significantly different average lengths (and are never-empty), this can lead to significant unfairness. Indeed, if load-balancing only occurs when a \gls{proc} runs out of work, any stable state where no \gls{proc} runs out of work means that there is no longer any load-balancing while in that state.
+
+\paragraph{Aggressive ``Nice'' \glspl{at}}
+Certain workloads can have ``Nice'' \glspl{at}, that is \glspl{at} which run in the background. These \glspl{at} generally have low amount of work and can run when the system isn't too busy. In systems without priorities, There are several techniques to implement background \glspl{at}, but not every technique may work with every scheduler.
+
+One approach is for the background task to yield every time it makes some small progress. If the yielding \gls{at} is put on a higher-priority \gls{Q} than workstealing, this can cause unfairness and can even cause the background task to fully utilize \gls{hthrd}
+
+A similar approach is to sleep for a short duration instead. However, depending on the details of the sleep, this can also cause problems. It is more likely that sleeping will cause a \gls{proc} to steal because the \gls{at} probably transitions out of the ready state. However, not all system support fine grain sleeping. If the sleeping is to coarse, relying on sleep can cause latency issues.
+
+Finally, this can be solve with explicit synchronization, however not all background tasks can be implemented this way since they don't necessarily have to wait for any ressource.
+
+\subsubsection*{Linux's CFS}
+\subsubsection*{FreeBSD scheduler}
+\subsubsection*{Windows OS Scheduler}
+Windows seems to use priority based scheduling, where the priorities can vary dynamically within some limit. Load-balancing across processors is handle using a work-sharing approch and has different rules based on whether or not there are idle processors.
+
+\subsubsection*{Windows User-Mode Scheduler}
+Windows seems to have M:N scheduling support but does not provide a default user-mode scheduler.
+
+\subsubsection*{Go}
+Go's scheduler uses a work-stealing algorithm without preemption that has a global runqueue(\emph{GRQ}) and each processor(\emph{P}) has a fixed-size runqueue(\emph{LRQ}).
+
+The algorithm is as follows :
+\begin{enumerate}
+ \item Once out of 61 times, directly pick 1 element from the \emph{GRQ}.
+ \item If there is a local next pick it.
+ \item Else pick an item from the \emph{LRQ}.
+ \item If it was empty steal (len(\emph{GRQ}) / \#of\emph{P}) + 1 items (max 256) from the \emph{GRQ}.
+ \item If it was empty steal \emph{half} the \emph{LRQ} of an other \emph{P}.
+\end{enumerate}
+
+Ignoring concerns of power consumption, this structure can lead to odd behaviour. Obviously, the fact that it is non-preemptable means that given a set of goroutines where $N$ of these never block (\eg CPU-bound producers) running on $P$ Processors (\emph{P}'s using the Go naming), if $N >= P$ than not all goroutines are guaranteed to ever make progress. However, this can also be the case even if $N < P$. Indeed, if $P - N$ processors can find a sustained amount of work without needing to steal, then indefinite starvation can still occur.
+
+Excluding cases due to the lack of preemption still leads to odd behavior. The fact that the LRQs have a fixed size can also effect the fairness of scheduling in drastic ways. The separation between \emph{LRQ} and \emph{GRQ} can lead to significant unfairness both in homogenous workloads and more heterogenous workloads.
+
+\subsubsection*{Erlang}
+Erlang uses a work-stealing schedulers with the addition that ``underloaded schedulers will also steal jobs from heavily overloaded schedulers in their migration paths''. Depending on the specifics of this heuristic
+
+\subsubsection*{Haskell}
+
+\subsubsection*{D}
+D does not appear to have an M:N threading model.
+\subsubsection*{Intel\textregistered ~Threading Building Blocks}
+https://software.intel.com/en-us/node/506295
+Intel's concurrency and parallelism library uses a more complicated scheduler which has multiple \glspl{Q} with various priority. However, these \glspl{Q} have a strict priority ordering meaning it is subject to tasks indefinetely starving lower priority tasks if programmers are not careful.
+\TODO test it
+
+\subsubsection*{Quasar}
+
+\subsubsection*{Grand Central Dispatch}
+
+\subsubsection*{LibFiber}
+
+\subsubsection*{Fiber Tasking Lib}
+Advertized in GDC and also uses work-stealing.
+
+
+\subsection{Scheduling Needs}
+Things to look at
+
+libuv : polling loop used for async I/O
+
+julia : uses libuv and has multi-threading
+
+
+
+Direction to look at :
+Static web-servers : mostly-I/O bound
+ - single or few thread, event driven
+ - thread per connections
+
+ examples:
+ - memcached
+ - apache
+ - nodejs stuff
+
+
+HPC workloads : compute bound
+
+
+% ===============================================================================
+% ===============================================================================
+
+\section{Overview of Scheduling for \CFA}
+
+\subsection{Scheduling : Core goals}
+
+\subsection{Requirements of the Scheduler Context}
+
+\subsection{Integration with I/O}
+
+\subsection{Blocking in Style}
+
+
+% ===============================================================================
+% ===============================================================================
+\section{Metrics of Scheduling} \label{metrics}
+Before starting to look into the design of the best scheduler for \CFA, it is important to take some time to detail what metrics to pick for scheduling.
+
+Here are a few metrics that should be considered.
+
+\paragraph{Throughput} is a fairly straightforward metric, it can be measured either in terms of how much time was spent to \glslink{atcomplet}{run to completion} for a fix number of \gls{at} or how many \gls{at} where \glslink{atrun}{ran} for a fix number of work.
+
+These two definitions are virtually interchangeable. However, since scheduling can affect application performance getting valid empirical measures for throughput can be difficult.
+
+\paragraph{Latency} measures how long an individual \gls{at} waited between when it was \glslink{atsched}{scheduled} and it was \glslink{atrun}{run}
+
+\paragraph{Fairness}
+
+\paragraph{Ressource Utilization}
+
+\paragraph{Application Performance}
+
+\section{The Core : Multi-Lane Scheduling}
+\subsection{Objectives}
+While work-stealing works well for both trivial cases, \ie all new \glspl{at} distributed evenly or all on a single work-queue, it handles poorly inbetween cases. As mentionned above, the goal is therefore to create a scheduler that is \emph{viable} for any workloads. More concretely, this means a scheduler that has good scalability and offers guarantees eventual progress. For the purpose of this document, eventual progress is defined as follows:
+
+\begin{itemize}
+ \item Any \Gls{at} that is \glslink{atsched}{scheduled} should eventually \glslink{atrun}{run}, regardless\footnote{In the context of guaranteeing eventual progress, we consider only normal program execution. . Depending on the chosen semantics, normal system shutdown can also prevent \glspl{at} from eventually running without considering the guarantee violated. } of any other \glspl{at} being scheduled (prior or otherwise).
+\end{itemize}
+
+Eventual progress is not guaranteed by work-stealing or work-sharing schedulers in every context. Indeed, as mentionned in \cit, when the system is \glslink{load}{loaded} neither work-stealing nor work-sharing guarantee eventual progress. These aberrant cases can be fixed with \gls{preemption}, they still show a fundamental fairness problem in the algorithm. We can offer a stricter guarantee of eventual progress by limitting the amount of \gls{at} \emph{\glslink{atpass}{overtaking}}. Indeed, cases where eventual progress is lost are cases that show \emph{unbounded} \glslink{atpass}{overtaking} and a such, a scheduler that limits \glslink{atpass}{overtaking} in general guarantees eventual progress.
+
+We can then define the first concrete goal of the \CFA scheduler as :
+\begin{itemize}
+ \item The odds that a \gls{at} is overtaken by $N$ other \glspl{at} decreases rapidly when $N$ increases.
+\end{itemize}
+
+As a second, more fuzzy, objective, the Cforall scheduler should also perform no worst than most existing scheduler for any workload.
+
+\subsection{Ideal description}
+The ideal scheduler should similarly to a multi-lane highway. If all lanes are equally fast, lane changes are to be avoided because they induce traffic jam. However, if some lanes are faster than others than lane changes will help balance the traffic.
+
+Similarly, a task should migrate in two cases:
+\begin{itemize}
+ \item When a worker just emptied its work-queue. (like work-stealing)
+ \item \emph{When a work-unit was overtaken too many times by work units in a different lane}.
+\end{itemize}
+
+
+\subsection{Practical terms}
+In practice, the highway lane analogy has to be adjusted slightly to make it practical. First, the \glspl{at} should always respect the order within a given lane. This means only the task at the front can migrate. This both enforces a stronger FIFO order and means that the scheduler can ignore all \glspl{at} that aren't at the front, simplifying processing. Furthermore, migrating \glspl{at} is only usefull when at least one worker is available, \ie looking for a task to run, because any migration made at any other time will only take effect at that moment.
+
+\subsection{Existing Work}
+
+\subsection{Cforall Today}
+
+
+
+% ===============================================================================
+% ===============================================================================
+\section{The Context : Scheduling in \CFA}
+\subsection{Dynamic Clusters}
+
+\subsection{Idle Sleep}
+
+\subsection{Locality}
+
+% ===============================================================================
+% ===============================================================================
+\section{Asynchronous IO}
+\subsection{Cooperation with the OS}
+
+\subsection{Framework Integration}
+
+% ===============================================================================
+% ===============================================================================
+\section{Blocking in Style}
+\subsection{Monitors and Baton-Passing}
+
+\subsection{Futures and Promises}
+
+
+% ===============================================================================
+% ===============================================================================
+\section{Current Work}
+
+\section{Conclusion}
+
+
+\cleardoublepage
+
+% B I B L I O G R A P H Y
+% -----------------------------
+\addcontentsline{toc}{chapter}{Bibliography}
+\bibliographystyle{plain}
+\bibliography{pl,local}
+\cleardoublepage
+\phantomsection % allows hyperref to link to the correct page
+
+% G L O S S A R Y
+% -----------------------------
+\addcontentsline{toc}{chapter}{Glossary}
+\printglossary
+\cleardoublepage
+\phantomsection % allows hyperref to link to the correct page
+
+\end{document}
Index: doc/theses/thierry_delisle_PhD/comp_II/glossary.tex
===================================================================
--- doc/theses/thierry_delisle_PhD/comp_II/glossary.tex (revision a50502128f8eabae54ded84a8ab9885411aad583)
+++ doc/theses/thierry_delisle_PhD/comp_II/glossary.tex (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -0,0 +1,137 @@
+\makeglossaries
+
+\longnewglossaryentry{hthrd}
+{name={hardware thread}}
+{
+Threads representing the underlying hardware directly.
+
+\textit{Synonyms : User threads, Lightweight threads, Green threads, Virtual threads, Tasks.}
+}
+
+\longnewglossaryentry{uthrd}
+{name={user-level thread}}
+{
+Threads created and managed inside user-space. Each thread has its own stack and its own thread of execution. User-level threads are invisible to the underlying operating system.
+
+\textit{Synonyms : User threads, Lightweight threads, Green threads, Virtual threads, Tasks.}
+}
+
+\longnewglossaryentry{kthrd}
+{name={kernel-level thread}}
+{
+Threads created and managed inside kernel-space. Each thread has its own stack and its own thread of execution. Kernel-level threads are owned, managed and scheduled by the underlying operating system.
+
+\textit{Synonyms : OS threads, Hardware threads, Physical threads.}
+}
+
+\longnewglossaryentry{fiber}
+{name={fiber}}
+{
+Fibers are non-preemptive user-level threads. They share most of the caracteristics of user-level threads except that they cannot be preempted by another fiber.
+
+\textit{Synonyms : Tasks.}
+}
+
+\longnewglossaryentry{job}
+{name={job}}
+{
+Unit of work, often sent to a thread pool or worker pool to be executed. Has neither its own stack nor its own thread of execution.
+
+\textit{Synonyms : Tasks.}
+}
+
+\longnewglossaryentry{pool}
+{name={thread-pool}}
+{
+Group of homogeneuous threads that loop executing units of works after another.
+
+\textit{Synonyms : }
+}
+
+\longnewglossaryentry{preemption}
+{name={preemption}}
+{
+Involuntary context switch imposed on threads at a given rate.
+
+\textit{Synonyms : None.}
+}
+
+\longnewglossaryentry{proc}
+{name={virtual processor}}
+{
+
+}
+
+\longnewglossaryentry{Q}
+{name={work-queue}}
+{
+
+}
+
+\longnewglossaryentry{at}
+{name={fred}}
+{
+Abstract object representing an unit of work. Systems will offer one or more concrete implementations of this concept (\eg \gls{kthrd}, \gls{job}), however, most of the concept of schedulings are independent of the particular implementations of the work representation. For this reason, this document use the term \Gls{at} to mean any representation and not one in particular.
+}
+
+\longnewglossaryentry{atsched}
+{name={Scheduling a \gls{at}}}
+{
+Scheduling an \gls{at} refers to the act of notifying the scheduler that a task is ready to be ran. When representing the scheduler as a queue of tasks, scheduling is the act of pushing a task onto the end of the queue. This doesn't necesserily means the task will ever be allocated CPU time (\gls{atrun}), for example, if the system terminates abruptly, scheduled \glspl{at} will probably never run.
+
+\textit{Synonyms : None.}
+}
+
+\longnewglossaryentry{atrun}
+{name={Running a \gls{at}}}
+{
+Running an \gls{at} refers to the act of allocating CPU time to a task that is ready to run. When representing the scheduler as a queue of tasks, running is the act of poping a task from the front of the queue and putting it onto a \gls{proc}. The \gls{at} can than accomplish some or all of the work it is programmed to do.
+
+\textit{Synonyms : None.}
+}
+
+\longnewglossaryentry{atmig}
+{name={migration of \gls{at}}}
+{
+Migration refers to the idea of an \gls{at} running on a different worker/processor than the last time it was run. It is generally preferable to minimise migration as it incurs cost but any load balancing among workers requires some amount of migration.
+
+\textit{Synonyms : None.}
+}
+
+\longnewglossaryentry{atpass}
+{name={overtaking \gls{at}}}
+{
+When representing the scheduler as a queue of \glspl{at}, overtaking is the act breaking the FIFO-ness of the queue by moving a \gls{at} in front of some other \gls{at} when it arrived after. This remains true for schedulers that do not use a FIFO queue, when the order in which the \glspl{at} are \glslink{atsched}{scheduled} and \glslink{atrun}{run} in a different order. A \gls{at} is said to \emph{overtake} another if it is run \emph{before} but was \emph{scheduled} after the other \gls{at}.
+
+\textit{Synonyms : None.}
+}
+
+\longnewglossaryentry{atblock}
+{name={Blocking an \gls{at}}}
+{
+Blocking an abstract task refers to the act of taking a task that us running on a CPU off the CPU. Unless no other task is ready, this action is generally immediately followed by running an other task.
+
+\textit{Synonyms : None.}
+}
+
+\longnewglossaryentry{atcomplet}
+{name={Running to completion}}
+{
+Running to completion refers to the entire sequence of : being scheduled, running and blocking, for a given task.
+
+See also \gls{atsched}, \gls{atrun}, \gls{atblock}
+
+\textit{Synonyms : None.}
+}
+
+\longnewglossaryentry{load}
+{name={System Load}}
+{
+The load is refers to the rate at which \glspl{at} are \glslink{atsched}{scheduled} versus the rate at which they are \glslink{atrun}{run}. When \glspl{at} are being scheduled faster than they are run, the system is considered \emph{overloaded}. When \glspl{at} are being run faster than they are scheduled, the system is considered \emph{underloaded}. Conrrespondingly, if both rates are equal, the system is considered \emph{loaded}. Note that the system is considered loaded only of the rate at which \glspl{at} are scheduled/run is non-zero, otherwise the system is empty, it has no load.
+}
+
+
+\newacronym{tls}{TLS}{Thread Local Storage}
+\newacronym{api}{API}{Application Program Interface}
+\newacronym{raii}{RAII}{Resource Acquisition Is Initialization}
+\newacronym{numa}{NUMA}{Non-Uniform Memory Access}
Index: doc/theses/thierry_delisle_PhD/comp_II/local.bib
===================================================================
--- doc/theses/thierry_delisle_PhD/comp_II/local.bib (revision a50502128f8eabae54ded84a8ab9885411aad583)
+++ doc/theses/thierry_delisle_PhD/comp_II/local.bib (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -0,0 +1,222 @@
+
+Scheduling Multithreaded Computations by Work Stealing
+
+% ===============================================================================
+% Work stealing examples
+% ===============================================================================
+
+% Cilk [4],
+@article{frigo1998implementation,
+ title={The implementation of the Cilk-5 multithreaded language},
+ author={Frigo, Matteo and Leiserson, Charles E and Randall, Keith H},
+ journal={ACM Sigplan Notices},
+ volume={33},
+ number={5},
+ pages={212--223},
+ year={1998},
+ publisher={ACM}
+}
+
+% Cilk-NOW
+@inproceedings{blumofe1997adaptive,
+ title={Adaptive and reliable parallel computing on networks of workstations},
+ author={Blumofe, Robert D and Lisiecki, Philip A and others},
+ booktitle={USENIX 1997 Annual Technical Conference on UNIX and Advanced Computing Systems},
+ pages={133--147},
+ year={1997}
+}
+
+% Intel Threading Building Blocks (TBB)
+@article{intelTBB,
+ title={Intel R Threading Building Blocks Documentation. Sept. 2013},
+ author={Intel, R},
+ journal={URL: https://www.threadingbuildingblocks.org/docs/help/index.htm}
+}
+
+% Java's Fork-join Framework
+@inproceedings{lea2000java,
+ title={A Java fork/join framework},
+ author={Lea, Doug},
+ booktitle={Proceedings of the ACM 2000 conference on Java Grande},
+ pages={36--43},
+ year={2000},
+ organization={ACM}
+}
+
+% Microsoft Task Parallel Library
+@article{leijen2009design,
+ title={The design of a task parallel library},
+ author={Leijen, Daan and Schulte, Wolfram and Burckhardt, Sebastian},
+ journal={Acm Sigplan Notices},
+ volume={44},
+ number={10},
+ pages={227--242},
+ year={2009},
+ publisher={ACM}
+}
+
+% StackThreads/MP
+@book{taura1999stackthreads,
+ title={Stackthreads/mp: integrating futures into calling standards},
+ author={Taura, Kenjiro and Tabata, Kunio and Yonezawa, Akinori},
+ volume={34},
+ number={8},
+ year={1999},
+ publisher={ACM}
+}
+
+@article{feldmann1993game,
+ title={Game tree search on massively parallel systems},
+ author={Feldmann, Rainer and Mysliwietz, P and Monien, B},
+ journal={Advances in Computer Chess},
+ volume={7},
+ year={1993},
+ publisher={Citeseer}
+}
+
+@article{finkel1987dib,
+ title={DIB—a distributed implementation of backtracking},
+ author={Finkel, Raphael and Manber, Udi},
+ journal={ACM Transactions on Programming Languages and Systems (TOPLAS)},
+ volume={9},
+ number={2},
+ pages={235--256},
+ year={1987},
+ publisher={ACM}
+}
+
+@phdthesis{halbherr1994mimd,
+ title={MIMD-style parallel programming based on continuation-passing threads},
+ author={Halbherr, Michael Roland Sven},
+ year={1994},
+ school={ETH Zurich}
+}
+
+@phdthesis{kuszmaul1994synchronized,
+ title={Synchronized MIMD computing},
+ author={Kuszmaul, Bradley Clair},
+ year={1994},
+ school={Massachusetts Institute of Technology}
+}
+
+@article{mohr1991lazy,
+ title={Lazy task creation: A technique for increasing the granularity of parallel programs},
+ author={Mohr, Eric and Kranz, David A and Halstead, Robert H},
+ journal={IEEE transactions on Parallel and Distributed Systems},
+ volume={2},
+ number={3},
+ pages={264--280},
+ year={1991},
+ publisher={IEEE}
+}
+
+@article{vandevoorde1988workcrews,
+ title={WorkCrews: An abstraction for controlling parallelism},
+ author={Vandevoorde, Mark T and Roberts, Eric S},
+ journal={International Journal of Parallel Programming},
+ volume={17},
+ number={4},
+ pages={347--366},
+ year={1988},
+ publisher={Springer}
+}
+
+
+% ===============================================================================
+% Work stealing examples
+% ===============================================================================
+
+%----------
+% discussion about best case and worst case for full computation
+% cited by 1720
+@article{blumofe1999scheduling,
+ title={Scheduling multithreaded computations by work stealing},
+ author={Blumofe, Robert D and Leiserson, Charles E},
+ journal={Journal of the ACM (JACM)},
+ volume={46},
+ number={5},
+ pages={720--748},
+ year={1999},
+ publisher={ACM}
+}
+
+%----------
+% executing process trees in parallel
+% mostly used with lazy evaluation and dependency graphs
+% cited by 267
+% cited by blumofe1999scheduling as first 'work-stealing idea'
+@inproceedings{burton1981executing,
+ title={Executing functional programs on a virtual tree of processors},
+ author={Burton, F Warren and Sleep, M Ronan},
+ booktitle={Proceedings of the 1981 conference on Functional programming languages and computer architecture},
+ pages={187--194},
+ year={1981},
+ organization={ACM}
+}
+
+
+%----------
+% work-stealing used for multilisp.
+% "unfair scheduling policy"
+% cited by 285
+% cited by blumofe1999scheduling as first 'work-stealing idea' implementation
+@inproceedings{halstead1984implementation,
+ title={Implementation of Multilisp: Lisp on a multiprocessor},
+ author={Halstead Jr, Robert H},
+ booktitle={Proceedings of the 1984 ACM Symposium on LISP and functional programming},
+ pages={9--17},
+ year={1984},
+ organization={ACM}
+}
+
+
+% ===============================================================================
+% HPC schedulers with bounds
+% ===============================================================================
+
+%----------
+% discussion about bounds
+% cited by blumofe1999scheduling
+% mentionned as not practical
+% CAN'T find it
+@article{burton1996guaranteeing,
+ title={Guaranteeing good memory bounds for parallel programs},
+ author={Burton, F Warren},
+ journal={IEEE Transactions on software engineering},
+ number={10},
+ pages={762--773},
+ year={1996},
+ publisher={IEEE}
+}
+
+%----------
+% discussion about bounds
+% cited by blumofe1999scheduling
+% mentionned as not practical
+% - from abstract
+% talks about implicit concurrency
+% does not work online or for something other than HPC
+@inproceedings{blelloch1995provably,
+ title={Provably efficient scheduling for languages with fine-grained parallelism},
+ author={Blelloch, Guy E and Gibbons, Phillip B and Matias, Yossi},
+ booktitle={Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures},
+ pages={1--12},
+ year={1995},
+ organization={ACM}
+}
+
+%----------
+% discussion about bounds
+% cited by blumofe1999scheduling
+% mentionned as not practical
+% - from abstract
+% talks about bound on total time and space
+% no concept of fairness or latency among tasks
+@inproceedings{blelloch1997space,
+ title={Space-efficient scheduling of parallelism with synchronization variables},
+ author={Blelloch, Guy E and Gibbons, Phillip B and Matias, Yossi and Narlikar, Girija J},
+ booktitle={Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures},
+ pages={12--23},
+ year={1997},
+ organization={ACM}
+}
Index: driver/cfa.cc
===================================================================
--- driver/cfa.cc (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ driver/cfa.cc (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -411,5 +411,7 @@
args[nargs++] = "-lcfathread";
args[nargs++] = "-Wl,--pop-state";
+ args[nargs++] = "-Wl,--push-state,--no-as-needed";
args[nargs++] = "-lcfa";
+ args[nargs++] = "-Wl,--pop-state";
args[nargs++] = "-pthread";
args[nargs++] = "-ldl";
Index: libcfa/prelude/Makefile.am
===================================================================
--- libcfa/prelude/Makefile.am (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/prelude/Makefile.am (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -11,6 +11,6 @@
## Created On : Sun May 31 08:54:01 2015
## Last Modified By : Peter A. Buhr
-## Last Modified On : Wed Dec 14 15:00:35 2016
-## Update Count : 205
+## Last Modified On : Mon Feb 3 21:27:18 2020
+## Update Count : 208
###############################################################################
@@ -36,4 +36,5 @@
extras.cf : ${srcdir}/extras.regx ${srcdir}/extras.c
${AM_V_GEN}gcc ${AM_CFLAGS} -E ${srcdir}/extras.c | grep -f ${srcdir}/extras.regx > extras.cf
+ ${AM_V_GEN}gcc ${AM_CFLAGS} -E ${srcdir}/extras.c | grep -zo -f ${srcdir}/extras.regx2 | tr '\0' '\n' >> extras.cf
# create forward declarations for gcc builtins
Index: libcfa/prelude/Makefile.in
===================================================================
--- libcfa/prelude/Makefile.in (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/prelude/Makefile.in (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -1,6 +1,6 @@
-# Makefile.in generated by automake 1.15 from Makefile.am.
+# Makefile.in generated by automake 1.16.1 from Makefile.am.
# @configure_input@
-# Copyright (C) 1994-2014 Free Software Foundation, Inc.
+# Copyright (C) 1994-2018 Free Software Foundation, Inc.
# This Makefile.in is free software; the Free Software Foundation
@@ -331,6 +331,6 @@
cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh;; \
*) \
- echo ' cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__depfiles_maybe)'; \
- cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__depfiles_maybe);; \
+ echo ' cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__maybe_remake_depfiles)'; \
+ cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__maybe_remake_depfiles);; \
esac;
@@ -377,5 +377,8 @@
-distdir: $(DISTFILES)
+distdir: $(BUILT_SOURCES)
+ $(MAKE) $(AM_MAKEFLAGS) distdir-am
+
+distdir-am: $(DISTFILES)
@srcdirstrip=`echo "$(srcdir)" | sed 's/[].[^$$\\*]/\\\\&/g'`; \
topsrcdirstrip=`echo "$(top_srcdir)" | sed 's/[].[^$$\\*]/\\\\&/g'`; \
@@ -540,4 +543,5 @@
extras.cf : ${srcdir}/extras.regx ${srcdir}/extras.c
${AM_V_GEN}gcc ${AM_CFLAGS} -E ${srcdir}/extras.c | grep -f ${srcdir}/extras.regx > extras.cf
+ ${AM_V_GEN}gcc ${AM_CFLAGS} -E ${srcdir}/extras.c | grep -zo -f ${srcdir}/extras.regx2 | tr '\0' '\n' >> extras.cf
# create forward declarations for gcc builtins
Index: libcfa/prelude/extras.regx
===================================================================
--- libcfa/prelude/extras.regx (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/prelude/extras.regx (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -24,8 +24,2 @@
typedef.* char32_t;
typedef.* wchar_t;
-extern.*\*malloc\(.*\).*
-extern.* free\(.*\).*
-extern.* exit\(.*\).*
-extern.* atexit\(.*\).*
-extern.* abort\(.*\).*
-extern.* printf\(.*\).*
Index: libcfa/prelude/extras.regx2
===================================================================
--- libcfa/prelude/extras.regx2 (revision a50502128f8eabae54ded84a8ab9885411aad583)
+++ libcfa/prelude/extras.regx2 (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -0,0 +1,6 @@
+extern void \*malloc[^;]*;
+extern void free[^;]*;
+extern void exit[^;]*;
+extern int atexit[^;]*;
+extern void abort[^;]*;
+extern int printf[^;]*;
Index: libcfa/prelude/prototypes.awk
===================================================================
--- libcfa/prelude/prototypes.awk (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/prelude/prototypes.awk (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,6 +10,6 @@
# Created On : Sat May 16 07:57:37 2015
# Last Modified By : Peter A. Buhr
-# Last Modified On : Thu Jun 6 20:46:28 2019
-# Update Count : 34
+# Last Modified On : Sat Feb 8 09:46:58 2020
+# Update Count : 36
#
@@ -17,5 +17,5 @@
BEGIN {
- FS = "[( )]"
+ FS = "[( )]"
# order so string search is longest string
i=-1
@@ -84,10 +84,10 @@
/BT_FN/ {
- for (i = 1; i <= NF; i++) {
- if( match($i, "BT_FN") != 0 ) {
- prototypes[$i] = $i
- }
+ for (i = 1; i <= NF; i += 1 ) {
+ if ( match($i, "BT_FN") != 0 ) {
+ prototypes[$i] = $i
+ }
}
- }
+}
END {
@@ -103,47 +103,47 @@
for ( prototype in prototypes ) {
- # printf( "//\"%s\"\n", prototype )
- if ( index( "BT_LAST", prototype ) == 1 ) {
- continue
- } # if
+ # printf( "//\"%s\"\n", prototype )
+ if ( index( "BT_LAST", prototype ) == 1 ) {
+ continue
+ } # if
- printf( "#define %s(NAME) FUNC_SIMPLE(", prototype )
+ printf( "#define %s(NAME) FUNC_SIMPLE(", prototype )
- if ( sub( "BT_FN_", "", prototype ) == 0 ) {
- printf( "\n********** BAD MACRO NAME \"%s\" **********\n", prototype )
- exit 0
- } # if
+ if ( sub( "BT_FN_", "", prototype ) == 0 ) {
+ printf( "\n********** BAD MACRO NAME \"%s\" **********\n", prototype )
+ exit 0
+ } # if
- # generate function return type as macro
- for ( t = 0; t < N; t += 1 ) { # find longest match
- type = types[t];
- if ( index( prototype, type ) == 1 ) { # found match
- printf( "BT_%s, NAME", type )
- sub( type, "", prototype )
- break;
+ # generate function return type as macro
+ for ( t = 0; t < N; t += 1 ) { # find longest match
+ type = types[t];
+ if ( index( prototype, type ) == 1 ) { # found match
+ printf( "BT_%s, NAME", type )
+ sub( type, "", prototype )
+ break;
+ } # if
+ } # for
+
+ # generate function parameter types as macro
+ if ( index( prototype, "VAR" ) != 2 ) { # C-style empty parameters ?
+ for ( p = 0; length( prototype ) > 0; p += 1 ) { # until all parameters types are removed
+ sub( "_", "", prototype) # remove "_"
+ printf( ", ", type )
+ temp = prototype
+ for ( t = 0; t < N; t += 1 ) { # find longest match
+ type = types[t];
+ if ( index( prototype, type ) == 1 ) { # found match
+ printf( "BT_%s", type )
+ sub( type, "", prototype )
+ break;
+ } # if
+ } # for
+ if ( temp == prototype ) { # no match found for parameter in macro table
+ printf( "\n********** MISSING TYPE \"%s\" **********\n", prototype )
+ exit 0
+ } # if
+ } # for
} # if
- } # for
-
- # generate function parameter types as macro
- if ( index( prototype, "VAR" ) != 2 ) { # C-style empty parameters ?
- for ( p = 0; length( prototype ) > 0; p += 1 ) { # until all parameters types are removed
- sub( "_", "", prototype) # remove "_"
- printf( ", ", type )
- temp = prototype
- for ( t = 0; t < N; t += 1 ) { # find longest match
- type = types[t];
- if ( index( prototype, type ) == 1 ) { # found match
- printf( "BT_%s", type )
- sub( type, "", prototype )
- break;
- } # if
- } # for
- if ( temp == prototype ) { # no match found for parameter in macro table
- printf( "\n********** MISSING TYPE \"%s\" **********\n", prototype )
- exit 0
- } # if
- } # for
- } # if
- printf( ")\n" )
+ printf( ")\n" )
} # for
Index: libcfa/src/assert.cfa
===================================================================
--- libcfa/src/assert.cfa (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/assert.cfa (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,6 +10,6 @@
// Created On : Mon Nov 28 12:27:26 2016
// Last Modified By : Peter A. Buhr
-// Last Modified On : Thu Nov 21 17:09:26 2019
-// Update Count : 5
+// Last Modified On : Tue Feb 4 13:00:18 2020
+// Update Count : 6
//
@@ -26,5 +26,5 @@
// called by macro assert in assert.h
- void __assert_fail( const char *assertion, const char *file, unsigned int line, const char *function ) {
+ void __assert_fail( const char assertion[], const char file[], unsigned int line, const char function[] ) {
__cfaabi_bits_print_safe( STDERR_FILENO, CFA_ASSERT_FMT ".\n", assertion, __progname, function, line, file );
abort();
@@ -32,5 +32,5 @@
// called by macro assertf
- void __assert_fail_f( const char *assertion, const char *file, unsigned int line, const char *function, const char *fmt, ... ) {
+ void __assert_fail_f( const char assertion[], const char file[], unsigned int line, const char function[], const char fmt[], ... ) {
__cfaabi_bits_acquire();
__cfaabi_bits_print_nolock( STDERR_FILENO, CFA_ASSERT_FMT ": ", assertion, __progname, function, line, file );
Index: libcfa/src/bits/debug.cfa
===================================================================
--- libcfa/src/bits/debug.cfa (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/bits/debug.cfa (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,6 +10,6 @@
// Created On : Thu Mar 30 12:30:01 2017
// Last Modified By : Peter A. Buhr
-// Last Modified On : Thu Nov 21 17:16:30 2019
-// Update Count : 10
+// Last Modified On : Tue Feb 4 13:03:16 2020
+// Update Count : 11
//
@@ -27,6 +27,5 @@
extern "C" {
-
- void __cfaabi_bits_write( int fd, const char *in_buffer, int len ) {
+ void __cfaabi_bits_write( int fd, const char in_buffer[], int len ) {
// ensure all data is written
for ( int count = 0, retcode; count < len; count += retcode ) {
Index: libcfa/src/bits/debug.hfa
===================================================================
--- libcfa/src/bits/debug.hfa (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/bits/debug.hfa (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,6 +10,6 @@
// Created On : Mon Nov 28 12:27:26 2016
// Last Modified By : Peter A. Buhr
-// Last Modified On : Thu Nov 21 17:06:58 2019
-// Update Count : 8
+// Last Modified On : Tue Feb 4 12:29:21 2020
+// Update Count : 9
//
@@ -21,6 +21,6 @@
#define __cfaabi_dbg_ctx __PRETTY_FUNCTION__
#define __cfaabi_dbg_ctx2 , __PRETTY_FUNCTION__
- #define __cfaabi_dbg_ctx_param const char * caller
- #define __cfaabi_dbg_ctx_param2 , const char * caller
+ #define __cfaabi_dbg_ctx_param const char caller[]
+ #define __cfaabi_dbg_ctx_param2 , const char caller[]
#else
#define __cfaabi_dbg_debug_do(...)
@@ -38,5 +38,5 @@
#include
- extern void __cfaabi_bits_write( int fd, const char *buffer, int len );
+ extern void __cfaabi_bits_write( int fd, const char buffer[], int len );
extern void __cfaabi_bits_acquire();
extern void __cfaabi_bits_release();
Index: libcfa/src/bits/locks.hfa
===================================================================
--- libcfa/src/bits/locks.hfa (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/bits/locks.hfa (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,6 +10,6 @@
// Created On : Tue Oct 31 15:14:38 2017
// Last Modified By : Peter A. Buhr
-// Last Modified On : Sat Aug 11 15:42:24 2018
-// Update Count : 10
+// Last Modified On : Tue Feb 4 13:03:19 2020
+// Update Count : 11
//
@@ -54,5 +54,5 @@
#ifdef __CFA_DEBUG__
- void __cfaabi_dbg_record(__spinlock_t & this, const char * prev_name);
+ void __cfaabi_dbg_record(__spinlock_t & this, const char prev_name[]);
#else
#define __cfaabi_dbg_record(x, y)
Index: libcfa/src/concurrency/coroutine.cfa
===================================================================
--- libcfa/src/concurrency/coroutine.cfa (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/concurrency/coroutine.cfa (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,6 +10,6 @@
// Created On : Mon Nov 28 12:27:26 2016
// Last Modified By : Peter A. Buhr
-// Last Modified On : Thu Dec 5 14:37:29 2019
-// Update Count : 15
+// Last Modified On : Tue Feb 4 12:29:25 2020
+// Update Count : 16
//
@@ -89,5 +89,5 @@
}
-void ?{}( coroutine_desc & this, const char * name, void * storage, size_t storageSize ) with( this ) {
+void ?{}( coroutine_desc & this, const char name[], void * storage, size_t storageSize ) with( this ) {
(this.context){0p, 0p};
(this.stack){storage, storageSize};
Index: libcfa/src/concurrency/coroutine.hfa
===================================================================
--- libcfa/src/concurrency/coroutine.hfa (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/concurrency/coroutine.hfa (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,6 +10,6 @@
// Created On : Mon Nov 28 12:27:26 2016
// Last Modified By : Peter A. Buhr
-// Last Modified On : Tue Dec 3 22:47:58 2019
-// Update Count : 10
+// Last Modified On : Tue Feb 4 12:29:26 2020
+// Update Count : 11
//
@@ -35,5 +35,5 @@
// void ^?{}( coStack_t & this );
-void ?{}( coroutine_desc & this, const char * name, void * storage, size_t storageSize );
+void ?{}( coroutine_desc & this, const char name[], void * storage, size_t storageSize );
void ^?{}( coroutine_desc & this );
@@ -41,6 +41,6 @@
static inline void ?{}( coroutine_desc & this, size_t stackSize) { this{ "Anonymous Coroutine", 0p, stackSize }; }
static inline void ?{}( coroutine_desc & this, void * storage, size_t storageSize ) { this{ "Anonymous Coroutine", storage, storageSize }; }
-static inline void ?{}( coroutine_desc & this, const char * name) { this{ name, 0p, 0 }; }
-static inline void ?{}( coroutine_desc & this, const char * name, size_t stackSize ) { this{ name, 0p, stackSize }; }
+static inline void ?{}( coroutine_desc & this, const char name[]) { this{ name, 0p, 0 }; }
+static inline void ?{}( coroutine_desc & this, const char name[], size_t stackSize ) { this{ name, 0p, stackSize }; }
//-----------------------------------------------------------------------------
Index: libcfa/src/concurrency/kernel.cfa
===================================================================
--- libcfa/src/concurrency/kernel.cfa (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/concurrency/kernel.cfa (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,6 +10,6 @@
// Created On : Tue Jan 17 12:27:26 2017
// Last Modified By : Peter A. Buhr
-// Last Modified On : Thu Jan 30 22:55:50 2020
-// Update Count : 56
+// Last Modified On : Tue Feb 4 13:03:15 2020
+// Update Count : 58
//
@@ -210,5 +210,5 @@
static void * CtxInvokeProcessor(void * arg);
-void ?{}(processor & this, const char * name, cluster & cltr) with( this ) {
+void ?{}(processor & this, const char name[], cluster & cltr) with( this ) {
this.name = name;
this.cltr = &cltr;
@@ -244,5 +244,5 @@
}
-void ?{}(cluster & this, const char * name, Duration preemption_rate) with( this ) {
+void ?{}(cluster & this, const char name[], Duration preemption_rate) with( this ) {
this.name = name;
this.preemption_rate = preemption_rate;
@@ -459,5 +459,5 @@
}
-static void Abort( int ret, const char * func ) {
+static void Abort( int ret, const char func[] ) {
if ( ret ) { // pthread routines return errno values
abort( "%s : internal error, error(%d) %s.", func, ret, strerror( ret ) );
@@ -960,5 +960,5 @@
__cfaabi_dbg_debug_do(
extern "C" {
- void __cfaabi_dbg_record(__spinlock_t & this, const char * prev_name) {
+ void __cfaabi_dbg_record(__spinlock_t & this, const char prev_name[]) {
this.prev_name = prev_name;
this.prev_thrd = kernelTLS.this_thread;
Index: libcfa/src/concurrency/kernel.hfa
===================================================================
--- libcfa/src/concurrency/kernel.hfa (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/concurrency/kernel.hfa (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,6 +10,6 @@
// Created On : Tue Jan 17 12:27:26 2017
// Last Modified By : Peter A. Buhr
-// Last Modified On : Wed Dec 4 07:54:51 2019
-// Update Count : 18
+// Last Modified On : Tue Feb 4 12:29:26 2020
+// Update Count : 22
//
@@ -101,10 +101,10 @@
};
-void ?{}(processor & this, const char * name, struct cluster & cltr);
+void ?{}(processor & this, const char name[], struct cluster & cltr);
void ^?{}(processor & this);
static inline void ?{}(processor & this) { this{ "Anonymous Processor", *mainCluster}; }
static inline void ?{}(processor & this, struct cluster & cltr) { this{ "Anonymous Processor", cltr}; }
-static inline void ?{}(processor & this, const char * name) { this{name, *mainCluster }; }
+static inline void ?{}(processor & this, const char name[]) { this{name, *mainCluster }; }
static inline [processor *&, processor *& ] __get( processor & this ) /*__attribute__((const))*/ { return this.node.[next, prev]; }
@@ -144,10 +144,10 @@
extern Duration default_preemption();
-void ?{} (cluster & this, const char * name, Duration preemption_rate);
+void ?{} (cluster & this, const char name[], Duration preemption_rate);
void ^?{}(cluster & this);
static inline void ?{} (cluster & this) { this{"Anonymous Cluster", default_preemption()}; }
static inline void ?{} (cluster & this, Duration preemption_rate) { this{"Anonymous Cluster", preemption_rate}; }
-static inline void ?{} (cluster & this, const char * name) { this{name, default_preemption()}; }
+static inline void ?{} (cluster & this, const char name[]) { this{name, default_preemption()}; }
static inline [cluster *&, cluster *& ] __get( cluster & this ) /*__attribute__((const))*/ { return this.node.[next, prev]; }
Index: libcfa/src/exception.c
===================================================================
--- libcfa/src/exception.c (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/exception.c (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -248,13 +248,7 @@
}
-#if defined(PIC)
-#warning Exceptions not yet supported when using Position-Independent Code
-__attribute__((noinline))
-void __cfaabi_ehm__try_terminate(void (*try_block)(),
- void (*catch_block)(int index, exception_t * except),
- __attribute__((unused)) int (*match_block)(exception_t * except)) {
- abort();
-}
-#else // PIC
+#pragma GCC push_options
+#pragma GCC optimize("O0")
+
// This is our personality routine. For every stack frame annotated with
// ".cfi_personality 0x3,__gcfa_personality_v0" this function will be called twice when unwinding.
@@ -431,6 +425,11 @@
// Setup the personality routine and exception table.
+#ifdef __PIC__
+ asm volatile (".cfi_personality 0x9b,CFA.ref.__gcfa_personality_v0");
+ asm volatile (".cfi_lsda 0x1b, .LLSDACFA2");
+#else
asm volatile (".cfi_personality 0x3,__gcfa_personality_v0");
asm volatile (".cfi_lsda 0x3, .LLSDACFA2");
+#endif
// Label which defines the start of the area for which the handler is setup.
@@ -464,4 +463,55 @@
// have a single call to the try routine.
+#ifdef __PIC__
+#if defined( __i386 ) || defined( __x86_64 )
+asm (
+ // HEADER
+ ".LFECFA1:\n"
+ " .globl __gcfa_personality_v0\n"
+ " .section .gcc_except_table,\"a\",@progbits\n"
+ // TABLE HEADER (important field is the BODY length at the end)
+ ".LLSDACFA2:\n"
+ " .byte 0xff\n"
+ " .byte 0xff\n"
+ " .byte 0x1\n"
+ " .uleb128 .LLSDACSECFA2-.LLSDACSBCFA2\n"
+ // BODY (language specific data)
+ // This uses language specific data and can be modified arbitrarily
+ // We use handled area offset, handled area length,
+ // handler landing pad offset and 1 (action code, gcc seems to use 0).
+ ".LLSDACSBCFA2:\n"
+ " .uleb128 .TRYSTART-__cfaabi_ehm__try_terminate\n"
+ " .uleb128 .TRYEND-.TRYSTART\n"
+ " .uleb128 .CATCH-__cfaabi_ehm__try_terminate\n"
+ " .uleb128 1\n"
+ ".LLSDACSECFA2:\n"
+ // TABLE FOOTER
+ " .text\n"
+ " .size __cfaabi_ehm__try_terminate, .-__cfaabi_ehm__try_terminate\n"
+);
+
+// Somehow this piece of helps with the resolution of debug symbols.
+__attribute__((unused)) static const int dummy = 0;
+
+asm (
+ // Add a hidden symbol which points at the function.
+ " .hidden CFA.ref.__gcfa_personality_v0\n"
+ " .weak CFA.ref.__gcfa_personality_v0\n"
+ // No clue what this does specifically
+ " .section .data.rel.local.CFA.ref.__gcfa_personality_v0,\"awG\",@progbits,CFA.ref.__gcfa_personality_v0,comdat\n"
+ " .align 8\n"
+ " .type CFA.ref.__gcfa_personality_v0, @object\n"
+ " .size CFA.ref.__gcfa_personality_v0, 8\n"
+ "CFA.ref.__gcfa_personality_v0:\n"
+#if defined( __x86_64 )
+ " .quad __gcfa_personality_v0\n"
+#else // then __i386
+ " .long __gcfa_personality_v0\n"
+#endif
+);
+#else
+#error Exception Handling: unknown architecture for position independent code.
+#endif // __i386 || __x86_64
+#else // __PIC__
#if defined( __i386 ) || defined( __x86_64 )
asm (
@@ -491,6 +541,10 @@
" .size __cfaabi_ehm__try_terminate, .-__cfaabi_ehm__try_terminate\n"
" .ident \"GCC: (Ubuntu 6.2.0-3ubuntu11~16.04) 6.2.0 20160901\"\n"
-// " .section .note.GNU-stack,\"x\",@progbits\n"
+ " .section .note.GNU-stack,\"x\",@progbits\n"
);
+#else
+#error Exception Handling: unknown architecture for position dependent code.
#endif // __i386 || __x86_64
-#endif // PIC
+#endif // __PIC__
+
+#pragma GCC pop_options
Index: libcfa/src/fstream.cfa
===================================================================
--- libcfa/src/fstream.cfa (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/fstream.cfa (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,6 +10,6 @@
// Created On : Wed May 27 17:56:53 2015
// Last Modified By : Peter A. Buhr
-// Last Modified On : Fri Nov 29 06:56:46 2019
-// Update Count : 355
+// Last Modified On : Fri Feb 7 19:01:01 2020
+// Update Count : 363
//
@@ -32,35 +32,35 @@
void ?{}( ofstream & os, void * file ) {
- os.file = file;
- os.sepDefault = true;
- os.sepOnOff = false;
- os.nlOnOff = true;
- os.prt = false;
- os.sawNL = false;
+ os.$file = file;
+ os.$sepDefault = true;
+ os.$sepOnOff = false;
+ os.$nlOnOff = true;
+ os.$prt = false;
+ os.$sawNL = false;
+ $sepSetCur( os, sepGet( os ) );
sepSet( os, " " );
- sepSetCur( os, sepGet( os ) );
sepSetTuple( os, ", " );
} // ?{}
// private
-bool sepPrt( ofstream & os ) { setNL( os, false ); return os.sepOnOff; }
-void sepReset( ofstream & os ) { os.sepOnOff = os.sepDefault; }
-void sepReset( ofstream & os, bool reset ) { os.sepDefault = reset; os.sepOnOff = os.sepDefault; }
-const char * sepGetCur( ofstream & os ) { return os.sepCur; }
-void sepSetCur( ofstream & os, const char * sepCur ) { os.sepCur = sepCur; }
-bool getNL( ofstream & os ) { return os.sawNL; }
-void setNL( ofstream & os, bool state ) { os.sawNL = state; }
-bool getANL( ofstream & os ) { return os.nlOnOff; }
-bool getPrt( ofstream & os ) { return os.prt; }
-void setPrt( ofstream & os, bool state ) { os.prt = state; }
+bool $sepPrt( ofstream & os ) { $setNL( os, false ); return os.$sepOnOff; }
+void $sepReset( ofstream & os ) { os.$sepOnOff = os.$sepDefault; }
+void $sepReset( ofstream & os, bool reset ) { os.$sepDefault = reset; os.$sepOnOff = os.$sepDefault; }
+const char * $sepGetCur( ofstream & os ) { return os.$sepCur; }
+void $sepSetCur( ofstream & os, const char sepCur[] ) { os.$sepCur = sepCur; }
+bool $getNL( ofstream & os ) { return os.$sawNL; }
+void $setNL( ofstream & os, bool state ) { os.$sawNL = state; }
+bool $getANL( ofstream & os ) { return os.$nlOnOff; }
+bool $getPrt( ofstream & os ) { return os.$prt; }
+void $setPrt( ofstream & os, bool state ) { os.$prt = state; }
// public
-void ?{}( ofstream & os ) { os.file = 0; }
-
-void ?{}( ofstream & os, const char * name, const char * mode ) {
+void ?{}( ofstream & os ) { os.$file = 0p; }
+
+void ?{}( ofstream & os, const char name[], const char mode[] ) {
open( os, name, mode );
} // ?{}
-void ?{}( ofstream & os, const char * name ) {
+void ?{}( ofstream & os, const char name[] ) {
open( os, name, "w" );
} // ?{}
@@ -70,41 +70,41 @@
} // ^?{}
-void sepOn( ofstream & os ) { os.sepOnOff = ! getNL( os ); }
-void sepOff( ofstream & os ) { os.sepOnOff = false; }
+void sepOn( ofstream & os ) { os.$sepOnOff = ! $getNL( os ); }
+void sepOff( ofstream & os ) { os.$sepOnOff = false; }
bool sepDisable( ofstream & os ) {
- bool temp = os.sepDefault;
- os.sepDefault = false;
- sepReset( os );
+ bool temp = os.$sepDefault;
+ os.$sepDefault = false;
+ $sepReset( os );
return temp;
} // sepDisable
bool sepEnable( ofstream & os ) {
- bool temp = os.sepDefault;
- os.sepDefault = true;
- if ( os.sepOnOff ) sepReset( os ); // start of line ?
+ bool temp = os.$sepDefault;
+ os.$sepDefault = true;
+ if ( os.$sepOnOff ) $sepReset( os ); // start of line ?
return temp;
} // sepEnable
-void nlOn( ofstream & os ) { os.nlOnOff = true; }
-void nlOff( ofstream & os ) { os.nlOnOff = false; }
-
-const char * sepGet( ofstream & os ) { return os.separator; }
-void sepSet( ofstream & os, const char * s ) {
+void nlOn( ofstream & os ) { os.$nlOnOff = true; }
+void nlOff( ofstream & os ) { os.$nlOnOff = false; }
+
+const char * sepGet( ofstream & os ) { return os.$separator; }
+void sepSet( ofstream & os, const char s[] ) {
assert( s );
- strncpy( os.separator, s, sepSize - 1 );
- os.separator[sepSize - 1] = '\0';
+ strncpy( os.$separator, s, sepSize - 1 );
+ os.$separator[sepSize - 1] = '\0';
} // sepSet
-const char * sepGetTuple( ofstream & os ) { return os.tupleSeparator; }
-void sepSetTuple( ofstream & os, const char * s ) {
+const char * sepGetTuple( ofstream & os ) { return os.$tupleSeparator; }
+void sepSetTuple( ofstream & os, const char s[] ) {
assert( s );
- strncpy( os.tupleSeparator, s, sepSize - 1 );
- os.tupleSeparator[sepSize - 1] = '\0';
+ strncpy( os.$tupleSeparator, s, sepSize - 1 );
+ os.$tupleSeparator[sepSize - 1] = '\0';
} // sepSet
void ends( ofstream & os ) {
- if ( getANL( os ) ) nl( os );
- else setPrt( os, false ); // turn off
+ if ( $getANL( os ) ) nl( os );
+ else $setPrt( os, false ); // turn off
if ( &os == &exit ) exit( EXIT_FAILURE );
if ( &os == &abort ) abort();
@@ -112,15 +112,15 @@
int fail( ofstream & os ) {
- return os.file == 0 || ferror( (FILE *)(os.file) );
+ return os.$file == 0 || ferror( (FILE *)(os.$file) );
} // fail
int flush( ofstream & os ) {
- return fflush( (FILE *)(os.file) );
+ return fflush( (FILE *)(os.$file) );
} // flush
-void open( ofstream & os, const char * name, const char * mode ) {
+void open( ofstream & os, const char name[], const char mode[] ) {
FILE * file = fopen( name, mode );
#ifdef __CFA_DEBUG__
- if ( file == 0 ) {
+ if ( file == 0p ) {
abort | IO_MSG "open output file \"" | name | "\"" | nl | strerror( errno );
} // if
@@ -129,22 +129,22 @@
} // open
-void open( ofstream & os, const char * name ) {
+void open( ofstream & os, const char name[] ) {
open( os, name, "w" );
} // open
void close( ofstream & os ) {
- if ( (FILE *)(os.file) == stdout || (FILE *)(os.file) == stderr ) return;
-
- if ( fclose( (FILE *)(os.file) ) == EOF ) {
+ if ( (FILE *)(os.$file) == stdout || (FILE *)(os.$file) == stderr ) return;
+
+ if ( fclose( (FILE *)(os.$file) ) == EOF ) {
abort | IO_MSG "close output" | nl | strerror( errno );
} // if
} // close
-ofstream & write( ofstream & os, const char * data, size_t size ) {
+ofstream & write( ofstream & os, const char data[], size_t size ) {
if ( fail( os ) ) {
abort | IO_MSG "attempt write I/O on failed stream";
} // if
- if ( fwrite( data, 1, size, (FILE *)(os.file) ) != size ) {
+ if ( fwrite( data, 1, size, (FILE *)(os.$file) ) != size ) {
abort | IO_MSG "write" | nl | strerror( errno );
} // if
@@ -155,7 +155,7 @@
va_list args;
va_start( args, format );
- int len = vfprintf( (FILE *)(os.file), format, args );
+ int len = vfprintf( (FILE *)(os.$file), format, args );
if ( len == EOF ) {
- if ( ferror( (FILE *)(os.file) ) ) {
+ if ( ferror( (FILE *)(os.$file) ) ) {
abort | IO_MSG "invalid write";
} // if
@@ -163,6 +163,6 @@
va_end( args );
- setPrt( os, true ); // called in output cascade
- sepReset( os ); // reset separator
+ $setPrt( os, true ); // called in output cascade
+ $sepReset( os ); // reset separator
return len;
} // fmt
@@ -184,16 +184,16 @@
// private
void ?{}( ifstream & is, void * file ) {
- is.file = file;
- is.nlOnOff = false;
+ is.$file = file;
+ is.$nlOnOff = false;
} // ?{}
// public
-void ?{}( ifstream & is ) { is.file = 0; }
-
-void ?{}( ifstream & is, const char * name, const char * mode ) {
+void ?{}( ifstream & is ) { is.$file = 0p; }
+
+void ?{}( ifstream & is, const char name[], const char mode[] ) {
open( is, name, mode );
} // ?{}
-void ?{}( ifstream & is, const char * name ) {
+void ?{}( ifstream & is, const char name[] ) {
open( is, name, "r" );
} // ?{}
@@ -203,34 +203,34 @@
} // ^?{}
-void nlOn( ifstream & os ) { os.nlOnOff = true; }
-void nlOff( ifstream & os ) { os.nlOnOff = false; }
-bool getANL( ifstream & os ) { return os.nlOnOff; }
+void nlOn( ifstream & os ) { os.$nlOnOff = true; }
+void nlOff( ifstream & os ) { os.$nlOnOff = false; }
+bool getANL( ifstream & os ) { return os.$nlOnOff; }
int fail( ifstream & is ) {
- return is.file == 0 || ferror( (FILE *)(is.file) );
+ return is.$file == 0p || ferror( (FILE *)(is.$file) );
} // fail
int eof( ifstream & is ) {
- return feof( (FILE *)(is.file) );
+ return feof( (FILE *)(is.$file) );
} // eof
-void open( ifstream & is, const char * name, const char * mode ) {
+void open( ifstream & is, const char name[], const char mode[] ) {
FILE * file = fopen( name, mode );
#ifdef __CFA_DEBUG__
- if ( file == 0 ) {
+ if ( file == 0p ) {
abort | IO_MSG "open input file \"" | name | "\"" | nl | strerror( errno );
} // if
#endif // __CFA_DEBUG__
- is.file = file;
-} // open
-
-void open( ifstream & is, const char * name ) {
+ is.$file = file;
+} // open
+
+void open( ifstream & is, const char name[] ) {
open( is, name, "r" );
} // open
void close( ifstream & is ) {
- if ( (FILE *)(is.file) == stdin ) return;
-
- if ( fclose( (FILE *)(is.file) ) == EOF ) {
+ if ( (FILE *)(is.$file) == stdin ) return;
+
+ if ( fclose( (FILE *)(is.$file) ) == EOF ) {
abort | IO_MSG "close input" | nl | strerror( errno );
} // if
@@ -242,5 +242,5 @@
} // if
- if ( fread( data, size, 1, (FILE *)(is.file) ) == 0 ) {
+ if ( fread( data, size, 1, (FILE *)(is.$file) ) == 0 ) {
abort | IO_MSG "read" | nl | strerror( errno );
} // if
@@ -253,5 +253,5 @@
} // if
- if ( ungetc( c, (FILE *)(is.file) ) == EOF ) {
+ if ( ungetc( c, (FILE *)(is.$file) ) == EOF ) {
abort | IO_MSG "ungetc" | nl | strerror( errno );
} // if
@@ -263,7 +263,7 @@
va_start( args, format );
- int len = vfscanf( (FILE *)(is.file), format, args );
+ int len = vfscanf( (FILE *)(is.$file), format, args );
if ( len == EOF ) {
- if ( ferror( (FILE *)(is.file) ) ) {
+ if ( ferror( (FILE *)(is.$file) ) ) {
abort | IO_MSG "invalid read";
} // if
Index: libcfa/src/fstream.hfa
===================================================================
--- libcfa/src/fstream.hfa (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/fstream.hfa (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,6 +10,6 @@
// Created On : Wed May 27 17:56:53 2015
// Last Modified By : Peter A. Buhr
-// Last Modified On : Fri Nov 29 06:56:02 2019
-// Update Count : 168
+// Last Modified On : Mon Feb 17 08:29:23 2020
+// Update Count : 175
//
@@ -24,26 +24,26 @@
enum { sepSize = 16 };
struct ofstream {
- void * file;
- bool sepDefault;
- bool sepOnOff;
- bool nlOnOff;
- bool prt; // print text
- bool sawNL;
- const char * sepCur;
- char separator[sepSize];
- char tupleSeparator[sepSize];
+ void * $file;
+ bool $sepDefault;
+ bool $sepOnOff;
+ bool $nlOnOff;
+ bool $prt; // print text
+ bool $sawNL;
+ const char * $sepCur;
+ char $separator[sepSize];
+ char $tupleSeparator[sepSize];
}; // ofstream
// private
-bool sepPrt( ofstream & );
-void sepReset( ofstream & );
-void sepReset( ofstream &, bool );
-const char * sepGetCur( ofstream & );
-void sepSetCur( ofstream &, const char * );
-bool getNL( ofstream & );
-void setNL( ofstream &, bool );
-bool getANL( ofstream & );
-bool getPrt( ofstream & );
-void setPrt( ofstream &, bool );
+bool $sepPrt( ofstream & );
+void $sepReset( ofstream & );
+void $sepReset( ofstream &, bool );
+const char * $sepGetCur( ofstream & );
+void $sepSetCur( ofstream &, const char [] );
+bool $getNL( ofstream & );
+void $setNL( ofstream &, bool );
+bool $getANL( ofstream & );
+bool $getPrt( ofstream & );
+void $setPrt( ofstream &, bool );
// public
@@ -56,20 +56,20 @@
const char * sepGet( ofstream & );
-void sepSet( ofstream &, const char * );
+void sepSet( ofstream &, const char [] );
const char * sepGetTuple( ofstream & );
-void sepSetTuple( ofstream &, const char * );
+void sepSetTuple( ofstream &, const char [] );
void ends( ofstream & os );
int fail( ofstream & );
int flush( ofstream & );
-void open( ofstream &, const char * name, const char * mode );
-void open( ofstream &, const char * name );
+void open( ofstream &, const char name[], const char mode[] );
+void open( ofstream &, const char name[] );
void close( ofstream & );
-ofstream & write( ofstream &, const char * data, size_t size );
-int fmt( ofstream &, const char format[], ... );
+ofstream & write( ofstream &, const char data[], size_t size );
+int fmt( ofstream &, const char format[], ... ) __attribute__(( format(printf, 2, 3) ));
void ?{}( ofstream & os );
-void ?{}( ofstream & os, const char * name, const char * mode );
-void ?{}( ofstream & os, const char * name );
+void ?{}( ofstream & os, const char name[], const char mode[] );
+void ?{}( ofstream & os, const char name[] );
void ^?{}( ofstream & os );
@@ -82,6 +82,6 @@
struct ifstream {
- void * file;
- bool nlOnOff;
+ void * $file;
+ bool $nlOnOff;
}; // ifstream
@@ -92,14 +92,14 @@
int fail( ifstream & is );
int eof( ifstream & is );
-void open( ifstream & is, const char * name, const char * mode );
-void open( ifstream & is, const char * name );
+void open( ifstream & is, const char name[], const char mode[] );
+void open( ifstream & is, const char name[] );
void close( ifstream & is );
ifstream & read( ifstream & is, char * data, size_t size );
ifstream & ungetc( ifstream & is, char c );
-int fmt( ifstream &, const char format[], ... );
+int fmt( ifstream &, const char format[], ... ) __attribute__(( format(scanf, 2, 3) ));
void ?{}( ifstream & is );
-void ?{}( ifstream & is, const char * name, const char * mode );
-void ?{}( ifstream & is, const char * name );
+void ?{}( ifstream & is, const char name[], const char mode[] );
+void ?{}( ifstream & is, const char name[] );
void ^?{}( ifstream & is );
Index: libcfa/src/gmp.hfa
===================================================================
--- libcfa/src/gmp.hfa (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/gmp.hfa (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,6 +10,6 @@
// Created On : Tue Apr 19 08:43:43 2016
// Last Modified By : Peter A. Buhr
-// Last Modified On : Sat Jul 13 15:25:05 2019
-// Update Count : 27
+// Last Modified On : Sun Feb 9 09:56:54 2020
+// Update Count : 31
//
@@ -24,12 +24,10 @@
static inline {
- // constructor
+ // constructor, zero_t/one_t are unnecessary because of relationship with signed/unsigned int
void ?{}( Int & this ) { mpz_init( this.mpz ); }
void ?{}( Int & this, Int init ) { mpz_init_set( this.mpz, init.mpz ); }
- void ?{}( Int & this, zero_t ) { mpz_init_set_si( this.mpz, 0 ); }
- void ?{}( Int & this, one_t ) { mpz_init_set_si( this.mpz, 1 ); }
void ?{}( Int & this, signed long int init ) { mpz_init_set_si( this.mpz, init ); }
void ?{}( Int & this, unsigned long int init ) { mpz_init_set_ui( this.mpz, init ); }
- void ?{}( Int & this, const char * val ) { if ( mpz_init_set_str( this.mpz, val, 0 ) ) abort(); }
+ void ?{}( Int & this, const char val[] ) { if ( mpz_init_set_str( this.mpz, val, 0 ) ) abort(); }
void ^?{}( Int & this ) { mpz_clear( this.mpz ); }
@@ -37,5 +35,5 @@
Int ?`mp( signed long int init ) { return (Int){ init }; }
Int ?`mp( unsigned long int init ) { return (Int){ init }; }
- Int ?`mp( const char * init ) { return (Int){ init }; }
+ Int ?`mp( const char init[] ) { return (Int){ init }; }
// assignment
@@ -43,5 +41,5 @@
Int ?=?( Int & lhs, long int rhs ) { mpz_set_si( lhs.mpz, rhs ); return lhs; }
Int ?=?( Int & lhs, unsigned long int rhs ) { mpz_set_ui( lhs.mpz, rhs ); return lhs; }
- Int ?=?( Int & lhs, const char * rhs ) { if ( mpz_set_str( lhs.mpz, rhs, 0 ) ) { abort | "invalid string conversion"; } return lhs; }
+ Int ?=?( Int & lhs, const char rhs[] ) { if ( mpz_set_str( lhs.mpz, rhs, 0 ) ) { abort | "invalid string conversion"; } return lhs; }
char ?=?( char & lhs, Int rhs ) { char val = mpz_get_si( rhs.mpz ); lhs = val; return lhs; }
@@ -265,5 +263,5 @@
forall( dtype ostype | ostream( ostype ) ) {
ostype & ?|?( ostype & os, Int mp ) {
- if ( sepPrt( os ) ) fmt( os, "%s", sepGetCur( os ) );
+ if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) );
gmp_printf( "%Zd", mp.mpz );
sepOn( os );
Index: libcfa/src/heap.cfa
===================================================================
--- libcfa/src/heap.cfa (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/heap.cfa (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,6 +10,6 @@
// Created On : Tue Dec 19 21:58:35 2017
// Last Modified By : Peter A. Buhr
-// Last Modified On : Sun Dec 8 21:01:31 2019
-// Update Count : 647
+// Last Modified On : Tue Feb 4 10:04:51 2020
+// Update Count : 648
//
@@ -380,5 +380,5 @@
-static inline void checkHeader( bool check, const char * name, void * addr ) {
+static inline void checkHeader( bool check, const char name[], void * addr ) {
if ( unlikely( check ) ) { // bad address ?
abort( "Attempt to %s storage %p with address outside the heap.\n"
@@ -418,5 +418,5 @@
-static inline bool headers( const char * name __attribute__(( unused )), void * addr, HeapManager.Storage.Header *& header, HeapManager.FreeHeader *& freeElem, size_t & size, size_t & alignment ) with ( heapManager ) {
+static inline bool headers( const char name[] __attribute__(( unused )), void * addr, HeapManager.Storage.Header *& header, HeapManager.FreeHeader *& freeElem, size_t & size, size_t & alignment ) with ( heapManager ) {
header = headerAddr( addr );
Index: libcfa/src/interpose.cfa
===================================================================
--- libcfa/src/interpose.cfa (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/interpose.cfa (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,6 +10,6 @@
// Created On : Wed Mar 29 16:10:31 2017
// Last Modified By : Peter A. Buhr
-// Last Modified On : Thu Jan 30 17:47:32 2020
-// Update Count : 156
+// Last Modified On : Mon Feb 17 10:18:53 2020
+// Update Count : 166
//
@@ -29,4 +29,5 @@
#include "bits/signal.hfa" // sigHandler_?
#include "startup.hfa" // STARTUP_PRIORITY_CORE
+#include
//=============================================================================================
@@ -40,5 +41,5 @@
typedef void (* generic_fptr_t)(void);
-generic_fptr_t interpose_symbol( const char * symbol, const char * version ) {
+generic_fptr_t interpose_symbol( const char symbol[], const char version[] ) {
const char * error;
@@ -145,5 +146,5 @@
extern "C" {
void abort( void ) __attribute__(( __nothrow__, __leaf__, __noreturn__ )) {
- abort( false, NULL ); // FIX ME: 0p does not work
+ abort( false, "%s", "" );
}
@@ -161,5 +162,5 @@
void * kernel_abort( void ) __attribute__(( __nothrow__, __leaf__, __weak__ )) { return 0p; }
-void kernel_abort_msg( void * data, char * buffer, int size ) __attribute__(( __nothrow__, __leaf__, __weak__ )) {}
+void kernel_abort_msg( void * data, char buffer[], int size ) __attribute__(( __nothrow__, __leaf__, __weak__ )) {}
// See concurrency/kernel.cfa for strong definition used in multi-processor mode.
int kernel_abort_lastframe( void ) __attribute__(( __nothrow__, __leaf__, __weak__ )) { return 4; }
@@ -169,12 +170,10 @@
static void __cfaabi_backtrace( int start ) {
- enum {
- Frames = 50, // maximum number of stack frames
- };
+ enum { Frames = 50, }; // maximum number of stack frames
int last = kernel_abort_lastframe(); // skip last N stack frames
void * array[Frames];
size_t size = backtrace( array, Frames );
- char ** messages = backtrace_symbols( array, size );
+ char ** messages = backtrace_symbols( array, size ); // does not demangle names
*index( messages[0], '(' ) = '\0'; // find executable name
@@ -184,5 +183,5 @@
char * name = 0p, * offset_begin = 0p, * offset_end = 0p;
- for ( char * p = messages[i]; *p; ++p ) { // find parantheses and +offset
+ for ( char * p = messages[i]; *p; p += 1 ) { // find parantheses and +offset
//__cfaabi_bits_print_nolock( "X %s\n", p);
if ( *p == '(' ) {
@@ -228,19 +227,18 @@
__cfaabi_bits_write( STDERR_FILENO, abort_text, len );
- if ( fmt ) {
- va_list args;
- va_start( args, fmt );
-
- len = vsnprintf( abort_text, abort_text_size, fmt, args );
- va_end( args );
- __cfaabi_bits_write( STDERR_FILENO, abort_text, len );
-
- if ( fmt[strlen( fmt ) - 1] != '\n' ) { // add optional newline if missing at the end of the format text
- __cfaabi_dbg_write( "\n", 1 );
- }
- }
-
+ assert( fmt );
+ va_list args;
+ va_start( args, fmt );
+
+ len = vsnprintf( abort_text, abort_text_size, fmt, args );
+ va_end( args );
+ __cfaabi_bits_write( STDERR_FILENO, abort_text, len );
+
+ if ( fmt[strlen( fmt ) - 1] != '\n' ) { // add optional newline if missing at the end of the format text
+ __cfaabi_dbg_write( "\n", 1 );
+ } // if
kernel_abort_msg( kernel_data, abort_text, abort_text_size );
- __cfaabi_backtrace( signalAbort ? 4 : 3 );
+
+ __cfaabi_backtrace( signalAbort ? 4 : 2 );
__cabi_libc.abort(); // print stack trace in handler
Index: libcfa/src/iostream.cfa
===================================================================
--- libcfa/src/iostream.cfa (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/iostream.cfa (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,6 +10,6 @@
// Created On : Wed May 27 17:56:53 2015
// Last Modified By : Peter A. Buhr
-// Last Modified On : Sat Jul 13 08:07:59 2019
-// Update Count : 821
+// Last Modified On : Thu Feb 20 15:53:23 2020
+// Update Count : 829
//
@@ -19,4 +19,5 @@
#include
#include // true/false
+#include // UINT64_MAX
//#include // strlen, strcmp
extern size_t strlen (const char *__s) __attribute__ ((__nothrow__ , __leaf__)) __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1)));
@@ -35,5 +36,5 @@
forall( dtype ostype | ostream( ostype ) ) {
ostype & ?|?( ostype & os, zero_t ) {
- if ( sepPrt( os ) ) fmt( os, "%s", sepGetCur( os ) );
+ if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) );
fmt( os, "%d", 0n );
return os;
@@ -44,5 +45,5 @@
ostype & ?|?( ostype & os, one_t ) {
- if ( sepPrt( os ) ) fmt( os, "%s", sepGetCur( os ) );
+ if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) );
fmt( os, "%d", 1n );
return os;
@@ -53,5 +54,5 @@
ostype & ?|?( ostype & os, bool b ) {
- if ( sepPrt( os ) ) fmt( os, "%s", sepGetCur( os ) );
+ if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) );
fmt( os, "%s", b ? "true" : "false" );
return os;
@@ -63,5 +64,5 @@
ostype & ?|?( ostype & os, char c ) {
fmt( os, "%c", c );
- if ( c == '\n' ) setNL( os, true );
+ if ( c == '\n' ) $setNL( os, true );
return sepOff( os );
} // ?|?
@@ -71,5 +72,5 @@
ostype & ?|?( ostype & os, signed char sc ) {
- if ( sepPrt( os ) ) fmt( os, "%s", sepGetCur( os ) );
+ if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) );
fmt( os, "%hhd", sc );
return os;
@@ -80,5 +81,5 @@
ostype & ?|?( ostype & os, unsigned char usc ) {
- if ( sepPrt( os ) ) fmt( os, "%s", sepGetCur( os ) );
+ if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) );
fmt( os, "%hhu", usc );
return os;
@@ -89,5 +90,5 @@
ostype & ?|?( ostype & os, short int si ) {
- if ( sepPrt( os ) ) fmt( os, "%s", sepGetCur( os ) );
+ if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) );
fmt( os, "%hd", si );
return os;
@@ -98,5 +99,5 @@
ostype & ?|?( ostype & os, unsigned short int usi ) {
- if ( sepPrt( os ) ) fmt( os, "%s", sepGetCur( os ) );
+ if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) );
fmt( os, "%hu", usi );
return os;
@@ -107,5 +108,5 @@
ostype & ?|?( ostype & os, int i ) {
- if ( sepPrt( os ) ) fmt( os, "%s", sepGetCur( os ) );
+ if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) );
fmt( os, "%d", i );
return os;
@@ -116,5 +117,5 @@
ostype & ?|?( ostype & os, unsigned int ui ) {
- if ( sepPrt( os ) ) fmt( os, "%s", sepGetCur( os ) );
+ if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) );
fmt( os, "%u", ui );
return os;
@@ -125,5 +126,5 @@
ostype & ?|?( ostype & os, long int li ) {
- if ( sepPrt( os ) ) fmt( os, "%s", sepGetCur( os ) );
+ if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) );
fmt( os, "%ld", li );
return os;
@@ -134,5 +135,5 @@
ostype & ?|?( ostype & os, unsigned long int uli ) {
- if ( sepPrt( os ) ) fmt( os, "%s", sepGetCur( os ) );
+ if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) );
fmt( os, "%lu", uli );
return os;
@@ -143,5 +144,5 @@
ostype & ?|?( ostype & os, long long int lli ) {
- if ( sepPrt( os ) ) fmt( os, "%s", sepGetCur( os ) );
+ if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) );
fmt( os, "%lld", lli );
return os;
@@ -152,5 +153,5 @@
ostype & ?|?( ostype & os, unsigned long long int ulli ) {
- if ( sepPrt( os ) ) fmt( os, "%s", sepGetCur( os ) );
+ if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) );
fmt( os, "%llu", ulli );
return os;
@@ -159,4 +160,44 @@
(ostype &)(os | ulli); ends( os );
} // ?|?
+
+#if defined( __SIZEOF_INT128__ )
+ // UINT64_MAX 18_446_744_073_709_551_615_ULL
+ #define P10_UINT64 10_000_000_000_000_000_000_ULL // 19 zeroes
+
+ static void base10_128( ostype & os, unsigned int128 val ) {
+ if ( val > UINT64_MAX ) {
+ base10_128( os, val / P10_UINT64 ); // recursive
+ fmt( os, "%.19lu", (uint64_t)(val % P10_UINT64) );
+ } else {
+ fmt( os, "%lu", (uint64_t)val );
+ } // if
+ } // base10_128
+
+ static void base10_128( ostype & os, int128 val ) {
+ if ( val < 0 ) {
+ fmt( os, "-" ); // leading negative sign
+ val = -val;
+ } // if
+ base10_128( os, (unsigned int128)val ); // print zero/positive value
+ } // base10_128
+
+ ostype & ?|?( ostype & os, int128 llli ) {
+ if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) );
+ base10_128( os, llli );
+ return os;
+ } // ?|?
+ void & ?|?( ostype & os, int128 llli ) {
+ (ostype &)(os | llli); ends( os );
+ } // ?|?
+
+ ostype & ?|?( ostype & os, unsigned int128 ullli ) {
+ if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) );
+ base10_128( os, ullli );
+ return os;
+ } // ?|?
+ void & ?|?( ostype & os, unsigned int128 ullli ) {
+ (ostype &)(os | ullli); ends( os );
+ } // ?|?
+#endif // __SIZEOF_INT128__
#define PrintWithDP( os, format, val, ... ) \
@@ -175,5 +216,5 @@
ostype & ?|?( ostype & os, float f ) {
- if ( sepPrt( os ) ) fmt( os, "%s", sepGetCur( os ) );
+ if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) );
PrintWithDP( os, "%g", f );
return os;
@@ -184,5 +225,5 @@
ostype & ?|?( ostype & os, double d ) {
- if ( sepPrt( os ) ) fmt( os, "%s", sepGetCur( os ) );
+ if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) );
PrintWithDP( os, "%.*lg", d, DBL_DIG );
return os;
@@ -193,5 +234,5 @@
ostype & ?|?( ostype & os, long double ld ) {
- if ( sepPrt( os ) ) fmt( os, "%s", sepGetCur( os ) );
+ if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) );
PrintWithDP( os, "%.*Lg", ld, LDBL_DIG );
return os;
@@ -202,5 +243,5 @@
ostype & ?|?( ostype & os, float _Complex fc ) {
- if ( sepPrt( os ) ) fmt( os, "%s", sepGetCur( os ) );
+ if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) );
// os | crealf( fc ) | nonl;
PrintWithDP( os, "%g", crealf( fc ) );
@@ -214,5 +255,5 @@
ostype & ?|?( ostype & os, double _Complex dc ) {
- if ( sepPrt( os ) ) fmt( os, "%s", sepGetCur( os ) );
+ if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) );
// os | creal( dc ) | nonl;
PrintWithDP( os, "%.*lg", creal( dc ), DBL_DIG );
@@ -226,5 +267,5 @@
ostype & ?|?( ostype & os, long double _Complex ldc ) {
- if ( sepPrt( os ) ) fmt( os, "%s", sepGetCur( os ) );
+ if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) );
// os | creall( ldc ) || nonl;
PrintWithDP( os, "%.*Lg", creall( ldc ), LDBL_DIG );
@@ -237,5 +278,5 @@
} // ?|?
- ostype & ?|?( ostype & os, const char * str ) {
+ ostype & ?|?( ostype & os, const char str[] ) {
enum { Open = 1, Close, OpenClose };
static const unsigned char mask[256] @= {
@@ -257,28 +298,29 @@
// first character IS NOT spacing or closing punctuation => add left separator
unsigned char ch = str[0]; // must make unsigned
- if ( sepPrt( os ) && mask[ ch ] != Close && mask[ ch ] != OpenClose ) {
- fmt( os, "%s", sepGetCur( os ) );
+ if ( $sepPrt( os ) && mask[ ch ] != Close && mask[ ch ] != OpenClose ) {
+ fmt( os, "%s", $sepGetCur( os ) );
} // if
// if string starts line, must reset to determine open state because separator is off
- sepReset( os ); // reset separator
+ $sepReset( os ); // reset separator
// last character IS spacing or opening punctuation => turn off separator for next item
size_t len = strlen( str );
ch = str[len - 1]; // must make unsigned
- if ( sepPrt( os ) && mask[ ch ] != Open && mask[ ch ] != OpenClose ) {
+ if ( $sepPrt( os ) && mask[ ch ] != Open && mask[ ch ] != OpenClose ) {
sepOn( os );
} else {
sepOff( os );
} // if
- if ( ch == '\n' ) setNL( os, true ); // check *AFTER* sepPrt call above as it resets NL flag
+ if ( ch == '\n' ) $setNL( os, true ); // check *AFTER* $sepPrt call above as it resets NL flag
return write( os, str, len );
} // ?|?
- void ?|?( ostype & os, const char * str ) {
+
+ void ?|?( ostype & os, const char str[] ) {
(ostype &)(os | str); ends( os );
} // ?|?
// ostype & ?|?( ostype & os, const char16_t * str ) {
-// if ( sepPrt( os ) ) fmt( os, "%s", sepGetCur( os ) );
+// if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) );
// fmt( os, "%ls", str );
// return os;
@@ -287,5 +329,5 @@
// #if ! ( __ARM_ARCH_ISA_ARM == 1 && __ARM_32BIT_STATE == 1 ) // char32_t == wchar_t => ambiguous
// ostype & ?|?( ostype & os, const char32_t * str ) {
-// if ( sepPrt( os ) ) fmt( os, "%s", sepGetCur( os ) );
+// if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) );
// fmt( os, "%ls", str );
// return os;
@@ -294,5 +336,5 @@
// ostype & ?|?( ostype & os, const wchar_t * str ) {
-// if ( sepPrt( os ) ) fmt( os, "%s", sepGetCur( os ) );
+// if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) );
// fmt( os, "%ls", str );
// return os;
@@ -300,5 +342,5 @@
ostype & ?|?( ostype & os, const void * p ) {
- if ( sepPrt( os ) ) fmt( os, "%s", sepGetCur( os ) );
+ if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) );
fmt( os, "%p", p );
return os;
@@ -315,6 +357,6 @@
void ?|?( ostype & os, ostype & (* manip)( ostype & ) ) {
(ostype &)(manip( os ));
- if ( getPrt( os ) ) ends( os ); // something printed ?
- setPrt( os, false ); // turn off
+ if ( $getPrt( os ) ) ends( os ); // something printed ?
+ $setPrt( os, false ); // turn off
} // ?|?
@@ -329,6 +371,6 @@
ostype & nl( ostype & os ) {
(ostype &)(os | '\n');
- setPrt( os, false ); // turn off
- setNL( os, true );
+ $setPrt( os, false ); // turn off
+ $setNL( os, true );
flush( os );
return sepOff( os ); // prepare for next line
@@ -336,5 +378,5 @@
ostype & nonl( ostype & os ) {
- setPrt( os, false ); // turn off
+ $setPrt( os, false ); // turn off
return os;
} // nonl
@@ -375,7 +417,7 @@
ostype & ?|?( ostype & os, T arg, Params rest ) {
(ostype &)(os | arg); // print first argument
- sepSetCur( os, sepGetTuple( os ) ); // switch to tuple separator
+ $sepSetCur( os, sepGetTuple( os ) ); // switch to tuple separator
(ostype &)(os | rest); // print remaining arguments
- sepSetCur( os, sepGet( os ) ); // switch to regular separator
+ $sepSetCur( os, sepGet( os ) ); // switch to regular separator
return os;
} // ?|?
@@ -383,7 +425,7 @@
// (ostype &)(?|?( os, arg, rest )); ends( os );
(ostype &)(os | arg); // print first argument
- sepSetCur( os, sepGetTuple( os ) ); // switch to tuple separator
+ $sepSetCur( os, sepGetTuple( os ) ); // switch to tuple separator
(ostype &)(os | rest); // print remaining arguments
- sepSetCur( os, sepGet( os ) ); // switch to regular separator
+ $sepSetCur( os, sepGet( os ) ); // switch to regular separator
ends( os );
} // ?|?
@@ -414,5 +456,5 @@
forall( dtype ostype | ostream( ostype ) ) { \
ostype & ?|?( ostype & os, _Ostream_Manip(T) f ) { \
- if ( sepPrt( os ) ) fmt( os, "%s", sepGetCur( os ) ); \
+ if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) ); \
\
if ( f.base == 'b' || f.base == 'B' ) { /* bespoke binary format */ \
@@ -463,10 +505,10 @@
\
if ( ! f.flags.pc ) { /* no precision */ \
- /* printf( "%s\n", &fmtstr[star] ); */ \
fmtstr[sizeof(IFMTNP)-2] = f.base; /* sizeof includes '\0' */ \
+ /* printf( "%s %c %c\n", &fmtstr[star], f.base, CODE ); */ \
fmt( os, &fmtstr[star], f.wd, f.val ); \
} else { /* precision */ \
fmtstr[sizeof(IFMTP)-2] = f.base; /* sizeof includes '\0' */ \
- /* printf( "%s\n", &fmtstr[star] ); */ \
+ /* printf( "%s %c %c\n", &fmtstr[star], f.base, CODE ); */ \
fmt( os, &fmtstr[star], f.wd, f.pc, f.val ); \
} /* if */ \
@@ -486,4 +528,74 @@
IntegralFMTImpl( signed long long int, 'd', "% *ll ", "% *.*ll " )
IntegralFMTImpl( unsigned long long int, 'u', "% *ll ", "% *.*ll " )
+
+
+#if defined( __SIZEOF_INT128__ )
+// Default prefix for non-decimal prints is 0b, 0, 0x.
+#define IntegralFMTImpl128( T, SIGNED, CODE, IFMTNP, IFMTP ) \
+forall( dtype ostype | ostream( ostype ) ) \
+static void base10_128( ostype & os, _Ostream_Manip(T) fmt ) { \
+ if ( fmt.val > UINT64_MAX ) { \
+ fmt.val /= P10_UINT64; \
+ base10_128( os, fmt ); /* recursive */ \
+ _Ostream_Manip(unsigned long long int) fmt2 @= { (uint64_t)(fmt.val % P10_UINT64), 0, 19, 'u', { .all : 0 } }; \
+ fmt2.flags.nobsdp = true; \
+ printf( "fmt2 %c %lld %d\n", fmt2.base, fmt2.val, fmt2.all ); \
+ sepOff( os ); \
+ (ostype &)(os | fmt2); \
+ } else { \
+ printf( "fmt %c %lld %d\n", fmt.base, fmt.val, fmt.all ); \
+ (ostype &)(os | fmt); \
+ } /* if */ \
+} /* base10_128 */ \
+forall( dtype ostype | ostream( ostype ) ) { \
+ ostype & ?|?( ostype & os, _Ostream_Manip(T) f ) { \
+ if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) ); \
+\
+ if ( f.base == 'b' | f.base == 'o' | f.base == 'x' | f.base == 'X' ) { \
+ unsigned long long int msig = (unsigned long long int)(f.val >> 64); \
+ unsigned long long int lsig = (unsigned long long int)(f.val); \
+ _Ostream_Manip(SIGNED long long int) fmt @= { msig, f.wd, f.pc, f.base, { .all : f.all } }; \
+ _Ostream_Manip(unsigned long long int) fmt2 @= { lsig, 0, 0, f.base, { .all : 0 } }; \
+ if ( msig == 0 ) { \
+ fmt.val = lsig; \
+ (ostype &)(os | fmt); \
+ } else { \
+ fmt2.flags.pad0 = fmt2.flags.nobsdp = true; \
+ if ( f.base == 'b' ) { \
+ if ( f.wd > 64 ) fmt.wd = f.wd - 64; \
+ fmt2.wd = 64; \
+ (ostype &)(os | fmt | "" | fmt2); \
+ } else if ( f.base == 'o' ) { \
+ fmt.val = (unsigned long long int)fmt.val >> 2; \
+ if ( f.wd > 21 ) fmt.wd = f.wd - 21; \
+ fmt2.wd = 1; \
+ fmt2.val = ((msig & 0x3) << 1) + 1; \
+ (ostype &)(os | fmt | "" | fmt2); \
+ sepOff( os ); \
+ fmt2.wd = 21; \
+ fmt2.val = lsig & 0x7fffffffffffffff; \
+ (ostype &)(os | fmt2); \
+ } else { \
+ if ( f.flags.left ) { \
+ if ( f.wd > 16 ) fmt2.wd = f.wd - 16; \
+ fmt.wd = 16; \
+ } else { \
+ if ( f.wd > 16 ) fmt.wd = f.wd - 16; \
+ fmt2.wd = 16; \
+ } /* if */ \
+ (ostype &)(os | fmt | "" | fmt2); \
+ } /* if */ \
+ } /* if */ \
+ } else { \
+ base10_128( os, f ); \
+ } /* if */ \
+ return os; \
+ } /* ?|? */ \
+ void ?|?( ostype & os, _Ostream_Manip(T) f ) { (ostype &)(os | f); ends( os ); } \
+} // distribution
+
+IntegralFMTImpl128( int128, signed, 'd', "% *ll ", "% *.*ll " )
+IntegralFMTImpl128( unsigned int128, unsigned, 'u', "% *ll ", "% *.*ll " )
+#endif // __SIZEOF_INT128__
//*********************************** floating point ***********************************
@@ -513,5 +625,5 @@
forall( dtype ostype | ostream( ostype ) ) { \
ostype & ?|?( ostype & os, _Ostream_Manip(T) f ) { \
- if ( sepPrt( os ) ) fmt( os, "%s", sepGetCur( os ) ); \
+ if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) ); \
char fmtstr[sizeof(DFMTP)]; /* sizeof includes '\0' */ \
if ( ! f.flags.pc ) memcpy( &fmtstr, DFMTNP, sizeof(DFMTNP) ); \
@@ -536,4 +648,5 @@
return os; \
} /* ?|? */ \
+\
void ?|?( ostype & os, _Ostream_Manip(T) f ) { (ostype &)(os | f); ends( os ); } \
} // distribution
@@ -555,5 +668,5 @@
} // if
- if ( sepPrt( os ) ) fmt( os, "%s", sepGetCur( os ) );
+ if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) );
#define CFMTNP "% * "
@@ -571,4 +684,5 @@
return os;
} // ?|?
+
void ?|?( ostype & os, _Ostream_Manip(char) f ) { (ostype &)(os | f); ends( os ); }
} // distribution
@@ -592,5 +706,5 @@
} // if
- if ( sepPrt( os ) ) fmt( os, "%s", sepGetCur( os ) );
+ if ( $sepPrt( os ) ) fmt( os, "%s", $sepGetCur( os ) );
#define SFMTNP "% * "
@@ -616,4 +730,5 @@
return os;
} // ?|?
+
void ?|?( ostype & os, _Ostream_Manip(const char *) f ) { (ostype &)(os | f); ends( os ); }
} // distribution
@@ -735,5 +850,5 @@
} // ?|?
- // istype & ?|?( istype & is, const char * fmt ) {
+ // istype & ?|?( istype & is, const char fmt[] ) {
// fmt( is, fmt, "" );
// return is;
Index: libcfa/src/iostream.hfa
===================================================================
--- libcfa/src/iostream.hfa (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/iostream.hfa (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,6 +10,6 @@
// Created On : Wed May 27 17:56:53 2015
// Last Modified By : Peter A. Buhr
-// Last Modified On : Fri Jul 12 12:08:38 2019
-// Update Count : 334
+// Last Modified On : Thu Feb 20 15:30:56 2020
+// Update Count : 337
//
@@ -24,14 +24,14 @@
trait ostream( dtype ostype ) {
// private
- bool sepPrt( ostype & ); // get separator state (on/off)
- void sepReset( ostype & ); // set separator state to default state
- void sepReset( ostype &, bool ); // set separator and default state
- const char * sepGetCur( ostype & ); // get current separator string
- void sepSetCur( ostype &, const char * ); // set current separator string
- bool getNL( ostype & ); // check newline
- void setNL( ostype &, bool ); // saw newline
- bool getANL( ostype & ); // get auto newline (on/off)
- bool getPrt( ostype & ); // get fmt called in output cascade
- void setPrt( ostype &, bool ); // set fmt called in output cascade
+ bool $sepPrt( ostype & ); // get separator state (on/off)
+ void $sepReset( ostype & ); // set separator state to default state
+ void $sepReset( ostype &, bool ); // set separator and default state
+ const char * $sepGetCur( ostype & ); // get current separator string
+ void $sepSetCur( ostype &, const char [] ); // set current separator string
+ bool $getNL( ostype & ); // check newline
+ void $setNL( ostype &, bool ); // saw newline
+ bool $getANL( ostype & ); // get auto newline (on/off)
+ bool $getPrt( ostype & ); // get fmt called in output cascade
+ void $setPrt( ostype &, bool ); // set fmt called in output cascade
// public
void sepOn( ostype & ); // turn separator state on
@@ -43,14 +43,14 @@
const char * sepGet( ostype & ); // get separator string
- void sepSet( ostype &, const char * ); // set separator to string (15 character maximum)
+ void sepSet( ostype &, const char [] ); // set separator to string (15 character maximum)
const char * sepGetTuple( ostype & ); // get tuple separator string
- void sepSetTuple( ostype &, const char * ); // set tuple separator to string (15 character maximum)
+ void sepSetTuple( ostype &, const char [] ); // set tuple separator to string (15 character maximum)
void ends( ostype & os ); // end of output statement
int fail( ostype & );
int flush( ostype & );
- void open( ostype & os, const char * name, const char * mode );
+ void open( ostype & os, const char name[], const char mode[] );
void close( ostype & os );
- ostype & write( ostype &, const char *, size_t );
+ ostype & write( ostype &, const char [], size_t );
int fmt( ostype &, const char format[], ... ) __attribute__(( format(printf, 2, 3) ));
}; // ostream
@@ -98,4 +98,10 @@
ostype & ?|?( ostype &, unsigned long long int );
void ?|?( ostype &, unsigned long long int );
+#if defined( __SIZEOF_INT128__ )
+ ostype & ?|?( ostype &, int128 );
+ void ?|?( ostype &, int128 );
+ ostype & ?|?( ostype &, unsigned int128 );
+ void ?|?( ostype &, unsigned int128 );
+#endif // __SIZEOF_INT128__
ostype & ?|?( ostype &, float );
@@ -113,6 +119,6 @@
void ?|?( ostype &, long double _Complex );
- ostype & ?|?( ostype &, const char * );
- void ?|?( ostype &, const char * );
+ ostype & ?|?( ostype &, const char [] );
+ void ?|?( ostype &, const char [] );
// ostype & ?|?( ostype &, const char16_t * );
#if ! ( __ARM_ARCH_ISA_ARM == 1 && __ARM_32BIT_STATE == 1 ) // char32_t == wchar_t => ambiguous
@@ -206,4 +212,8 @@
IntegralFMTDecl( signed long long int, 'd' )
IntegralFMTDecl( unsigned long long int, 'u' )
+#if defined( __SIZEOF_INT128__ )
+IntegralFMTDecl( int128, 'd' )
+IntegralFMTDecl( unsigned int128, 'u' )
+#endif
//*********************************** floating point ***********************************
@@ -256,9 +266,9 @@
static inline {
- _Ostream_Manip(const char *) bin( const char * s ) { return (_Ostream_Manip(const char *))@{ s, 1, 0, 'b', { .all : 0 } }; }
- _Ostream_Manip(const char *) oct( const char * s ) { return (_Ostream_Manip(const char *))@{ s, 1, 0, 'o', { .all : 0 } }; }
- _Ostream_Manip(const char *) hex( const char * s ) { return (_Ostream_Manip(const char *))@{ s, 1, 0, 'x', { .all : 0 } }; }
- _Ostream_Manip(const char *) wd( unsigned int w, const char * s ) { return (_Ostream_Manip(const char *))@{ s, w, 0, 's', { .all : 0 } }; }
- _Ostream_Manip(const char *) wd( unsigned int w, unsigned char pc, const char * s ) { return (_Ostream_Manip(const char *))@{ s, w, pc, 's', { .flags.pc : true } }; }
+ _Ostream_Manip(const char *) bin( const char s[] ) { return (_Ostream_Manip(const char *))@{ s, 1, 0, 'b', { .all : 0 } }; }
+ _Ostream_Manip(const char *) oct( const char s[] ) { return (_Ostream_Manip(const char *))@{ s, 1, 0, 'o', { .all : 0 } }; }
+ _Ostream_Manip(const char *) hex( const char s[] ) { return (_Ostream_Manip(const char *))@{ s, 1, 0, 'x', { .all : 0 } }; }
+ _Ostream_Manip(const char *) wd( unsigned int w, const char s[] ) { return (_Ostream_Manip(const char *))@{ s, w, 0, 's', { .all : 0 } }; }
+ _Ostream_Manip(const char *) wd( unsigned int w, unsigned char pc, const char s[] ) { return (_Ostream_Manip(const char *))@{ s, w, pc, 's', { .flags.pc : true } }; }
_Ostream_Manip(const char *) & wd( unsigned int w, _Ostream_Manip(const char *) & fmt ) { fmt.wd = w; return fmt; }
_Ostream_Manip(const char *) & wd( unsigned int w, unsigned char pc, _Ostream_Manip(const char *) & fmt ) { fmt.wd = w; fmt.pc = pc; fmt.flags.pc = true; return fmt; }
@@ -281,5 +291,5 @@
int fail( istype & );
int eof( istype & );
- void open( istype & is, const char * name );
+ void open( istype & is, const char name[] );
void close( istype & is );
istype & read( istype &, char *, size_t );
@@ -316,5 +326,5 @@
istype & ?|?( istype &, long double _Complex & );
-// istype & ?|?( istype &, const char * );
+// istype & ?|?( istype &, const char [] );
istype & ?|?( istype &, char * );
@@ -343,12 +353,12 @@
static inline {
_Istream_Cstr skip( unsigned int n ) { return (_Istream_Cstr){ 0p, 0p, n, { .all : 0 } }; }
- _Istream_Cstr skip( const char * scanset ) { return (_Istream_Cstr){ 0p, scanset, -1, { .all : 0 } }; }
- _Istream_Cstr incl( const char * scanset, char * s ) { return (_Istream_Cstr){ s, scanset, -1, { .flags.inex : false } }; }
- _Istream_Cstr & incl( const char * scanset, _Istream_Cstr & fmt ) { fmt.scanset = scanset; fmt.flags.inex = false; return fmt; }
- _Istream_Cstr excl( const char * scanset, char * s ) { return (_Istream_Cstr){ s, scanset, -1, { .flags.inex : true } }; }
- _Istream_Cstr & excl( const char * scanset, _Istream_Cstr & fmt ) { fmt.scanset = scanset; fmt.flags.inex = true; return fmt; }
- _Istream_Cstr ignore( const char * s ) { return (_Istream_Cstr)@{ s, 0p, -1, { .flags.ignore : true } }; }
+ _Istream_Cstr skip( const char scanset[] ) { return (_Istream_Cstr){ 0p, scanset, -1, { .all : 0 } }; }
+ _Istream_Cstr incl( const char scanset[], char * s ) { return (_Istream_Cstr){ s, scanset, -1, { .flags.inex : false } }; }
+ _Istream_Cstr & incl( const char scanset[], _Istream_Cstr & fmt ) { fmt.scanset = scanset; fmt.flags.inex = false; return fmt; }
+ _Istream_Cstr excl( const char scanset[], char * s ) { return (_Istream_Cstr){ s, scanset, -1, { .flags.inex : true } }; }
+ _Istream_Cstr & excl( const char scanset[], _Istream_Cstr & fmt ) { fmt.scanset = scanset; fmt.flags.inex = true; return fmt; }
+ _Istream_Cstr ignore( const char s[] ) { return (_Istream_Cstr)@{ s, 0p, -1, { .flags.ignore : true } }; }
_Istream_Cstr & ignore( _Istream_Cstr & fmt ) { fmt.flags.ignore = true; return fmt; }
- _Istream_Cstr wdi( unsigned int w, char * s ) { return (_Istream_Cstr)@{ s, 0p, w, { .all : 0 } }; }
+ _Istream_Cstr wdi( unsigned int w, char s[] ) { return (_Istream_Cstr)@{ s, 0p, w, { .all : 0 } }; }
_Istream_Cstr & wdi( unsigned int w, _Istream_Cstr & fmt ) { fmt.wd = w; return fmt; }
} // distribution
Index: libcfa/src/math.hfa
===================================================================
--- libcfa/src/math.hfa (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/math.hfa (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,6 +10,6 @@
// Created On : Mon Apr 18 23:37:04 2016
// Last Modified By : Peter A. Buhr
-// Last Modified On : Fri Jul 13 11:02:15 2018
-// Update Count : 116
+// Last Modified On : Tue Feb 4 10:27:11 2020
+// Update Count : 117
//
@@ -51,7 +51,7 @@
static inline long double fdim( long double x, long double y ) { return fdiml( x, y ); }
-static inline float nan( const char * tag ) { return nanf( tag ); }
-// extern "C" { double nan( const char * ); }
-static inline long double nan( const char * tag ) { return nanl( tag ); }
+static inline float nan( const char tag[] ) { return nanf( tag ); }
+// extern "C" { double nan( const char [] ); }
+static inline long double nan( const char tag[] ) { return nanl( tag ); }
//---------------------- Exponential ----------------------
Index: libcfa/src/rational.cfa
===================================================================
--- libcfa/src/rational.cfa (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/rational.cfa (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,6 +10,6 @@
// Created On : Wed Apr 6 17:54:28 2016
// Last Modified By : Peter A. Buhr
-// Last Modified On : Fri Jul 12 18:12:08 2019
-// Update Count : 184
+// Last Modified On : Sat Feb 8 17:56:36 2020
+// Update Count : 187
//
@@ -56,4 +56,11 @@
} // rational
+ void ?{}( Rational(RationalImpl) & r, zero_t ) {
+ r{ (RationalImpl){0}, (RationalImpl){1} };
+ } // rational
+
+ void ?{}( Rational(RationalImpl) & r, one_t ) {
+ r{ (RationalImpl){1}, (RationalImpl){1} };
+ } // rational
// getter for numerator/denominator
Index: libcfa/src/startup.cfa
===================================================================
--- libcfa/src/startup.cfa (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/startup.cfa (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,6 +10,6 @@
// Created On : Tue Jul 24 16:21:57 2018
// Last Modified By : Peter A. Buhr
-// Last Modified On : Fri Dec 13 13:16:45 2019
-// Update Count : 29
+// Last Modified On : Tue Feb 4 13:03:18 2020
+// Update Count : 30
//
@@ -41,5 +41,5 @@
struct __spinlock_t;
extern "C" {
- void __cfaabi_dbg_record(struct __spinlock_t & this, const char * prev_name) __attribute__(( weak )) {}
+ void __cfaabi_dbg_record(struct __spinlock_t & this, const char prev_name[]) __attribute__(( weak )) {}
}
Index: libcfa/src/stdhdr/assert.h
===================================================================
--- libcfa/src/stdhdr/assert.h (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/stdhdr/assert.h (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,6 +10,6 @@
// Created On : Mon Jul 4 23:25:26 2016
// Last Modified By : Peter A. Buhr
-// Last Modified On : Mon Jul 31 23:09:32 2017
-// Update Count : 13
+// Last Modified On : Tue Feb 4 12:58:49 2020
+// Update Count : 15
//
@@ -27,5 +27,5 @@
#define assertf( expr, fmt, ... ) ((expr) ? ((void)0) : __assert_fail_f(__VSTRINGIFY__(expr), __FILE__, __LINE__, __PRETTY_FUNCTION__, fmt, ## __VA_ARGS__ ))
- void __assert_fail_f( const char *assertion, const char *file, unsigned int line, const char *function, const char *fmt, ... ) __attribute__((noreturn, format( printf, 5, 6) ));
+ void __assert_fail_f( const char assertion[], const char file[], unsigned int line, const char function[], const char fmt[], ... ) __attribute__((noreturn, format( printf, 5, 6) ));
#endif
Index: libcfa/src/stdhdr/bfdlink.h
===================================================================
--- libcfa/src/stdhdr/bfdlink.h (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/stdhdr/bfdlink.h (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,11 +10,11 @@
// Created On : Tue Jul 18 07:26:04 2017
// Last Modified By : Peter A. Buhr
-// Last Modified On : Sat Feb 1 07:15:29 2020
-// Update Count : 5
+// Last Modified On : Fri Feb 7 19:05:08 2020
+// Update Count : 6
//
// include file uses the CFA keyword "with".
#if ! defined( with ) // nesting ?
-#define with ``with`` // make keyword an identifier
+#define with ``with // make keyword an identifier
#define __CFA_BFDLINK_H__
#endif
Index: libcfa/src/stdhdr/hwloc.h
===================================================================
--- libcfa/src/stdhdr/hwloc.h (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/stdhdr/hwloc.h (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,11 +10,11 @@
// Created On : Tue Jul 18 07:45:00 2017
// Last Modified By : Peter A. Buhr
-// Last Modified On : Sat Feb 1 07:15:39 2020
-// Update Count : 5
+// Last Modified On : Fri Feb 7 19:05:18 2020
+// Update Count : 6
//
// include file uses the CFA keyword "thread".
#if ! defined( thread ) // nesting ?
-#define thread ``thread`` // make keyword an identifier
+#define thread ``thread // make keyword an identifier
#define __CFA_HWLOC_H__
#endif
Index: libcfa/src/stdhdr/krb5.h
===================================================================
--- libcfa/src/stdhdr/krb5.h (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/stdhdr/krb5.h (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,11 +10,11 @@
// Created On : Tue Jul 18 07:55:44 2017
// Last Modified By : Peter A. Buhr
-// Last Modified On : Sat Feb 1 07:15:47 2020
-// Update Count : 5
+// Last Modified On : Fri Feb 7 19:05:35 2020
+// Update Count : 6
//
// include file uses the CFA keyword "enable".
#if ! defined( enable ) // nesting ?
-#define enable ``enable`` // make keyword an identifier
+#define enable ``enable // make keyword an identifier
#define __CFA_KRB5_H__
#endif
Index: libcfa/src/stdhdr/math.h
===================================================================
--- libcfa/src/stdhdr/math.h (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/stdhdr/math.h (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,11 +10,11 @@
// Created On : Mon Jul 4 23:25:26 2016
// Last Modified By : Peter A. Buhr
-// Last Modified On : Sat Feb 1 07:15:58 2020
-// Update Count : 14
+// Last Modified On : Fri Feb 7 19:05:27 2020
+// Update Count : 15
//
extern "C" {
#if ! defined( exception ) // nesting ?
-#define exception ``exception`` // make keyword an identifier
+#define exception ``exception // make keyword an identifier
#define __CFA_MATH_H__
#endif
Index: libcfa/src/stdhdr/sys/ucontext.h
===================================================================
--- libcfa/src/stdhdr/sys/ucontext.h (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/stdhdr/sys/ucontext.h (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,10 +10,10 @@
// Created On : Thu Feb 8 23:48:16 2018
// Last Modified By : Peter A. Buhr
-// Last Modified On : Sat Feb 1 07:16:05 2020
-// Update Count : 5
+// Last Modified On : Fri Feb 7 19:05:41 2020
+// Update Count : 6
//
#if ! defined( ftype ) // nesting ?
-#define ftype ``ftype`` // make keyword an identifier
+#define ftype ``ftype // make keyword an identifier
#define __CFA_UCONTEXT_H__
#endif
Index: libcfa/src/stdlib.cfa
===================================================================
--- libcfa/src/stdlib.cfa (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/stdlib.cfa (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,6 +10,6 @@
// Created On : Thu Jan 28 17:10:29 2016
// Last Modified By : Peter A. Buhr
-// Last Modified On : Wed Nov 20 17:22:47 2019
-// Update Count : 485
+// Last Modified On : Tue Feb 4 08:27:08 2020
+// Update Count : 486
//
@@ -107,5 +107,5 @@
//---------------------------------------
-float _Complex strto( const char * sptr, char ** eptr ) {
+float _Complex strto( const char sptr[], char ** eptr ) {
float re, im;
char * eeptr;
@@ -118,5 +118,5 @@
} // strto
-double _Complex strto( const char * sptr, char ** eptr ) {
+double _Complex strto( const char sptr[], char ** eptr ) {
double re, im;
char * eeptr;
@@ -129,5 +129,5 @@
} // strto
-long double _Complex strto( const char * sptr, char ** eptr ) {
+long double _Complex strto( const char sptr[], char ** eptr ) {
long double re, im;
char * eeptr;
Index: libcfa/src/stdlib.hfa
===================================================================
--- libcfa/src/stdlib.hfa (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/stdlib.hfa (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,6 +10,6 @@
// Created On : Thu Jan 28 17:12:35 2016
// Last Modified By : Peter A. Buhr
-// Last Modified On : Fri Nov 29 23:08:02 2019
-// Update Count : 400
+// Last Modified On : Tue Feb 4 08:27:01 2020
+// Update Count : 401
//
@@ -193,35 +193,35 @@
static inline {
- int strto( const char * sptr, char ** eptr, int base ) { return (int)strtol( sptr, eptr, base ); }
- unsigned int strto( const char * sptr, char ** eptr, int base ) { return (unsigned int)strtoul( sptr, eptr, base ); }
- long int strto( const char * sptr, char ** eptr, int base ) { return strtol( sptr, eptr, base ); }
- unsigned long int strto( const char * sptr, char ** eptr, int base ) { return strtoul( sptr, eptr, base ); }
- long long int strto( const char * sptr, char ** eptr, int base ) { return strtoll( sptr, eptr, base ); }
- unsigned long long int strto( const char * sptr, char ** eptr, int base ) { return strtoull( sptr, eptr, base ); }
-
- float strto( const char * sptr, char ** eptr ) { return strtof( sptr, eptr ); }
- double strto( const char * sptr, char ** eptr ) { return strtod( sptr, eptr ); }
- long double strto( const char * sptr, char ** eptr ) { return strtold( sptr, eptr ); }
-} // distribution
-
-float _Complex strto( const char * sptr, char ** eptr );
-double _Complex strto( const char * sptr, char ** eptr );
-long double _Complex strto( const char * sptr, char ** eptr );
+ int strto( const char sptr[], char ** eptr, int base ) { return (int)strtol( sptr, eptr, base ); }
+ unsigned int strto( const char sptr[], char ** eptr, int base ) { return (unsigned int)strtoul( sptr, eptr, base ); }
+ long int strto( const char sptr[], char ** eptr, int base ) { return strtol( sptr, eptr, base ); }
+ unsigned long int strto( const char sptr[], char ** eptr, int base ) { return strtoul( sptr, eptr, base ); }
+ long long int strto( const char sptr[], char ** eptr, int base ) { return strtoll( sptr, eptr, base ); }
+ unsigned long long int strto( const char sptr[], char ** eptr, int base ) { return strtoull( sptr, eptr, base ); }
+
+ float strto( const char sptr[], char ** eptr ) { return strtof( sptr, eptr ); }
+ double strto( const char sptr[], char ** eptr ) { return strtod( sptr, eptr ); }
+ long double strto( const char sptr[], char ** eptr ) { return strtold( sptr, eptr ); }
+} // distribution
+
+float _Complex strto( const char sptr[], char ** eptr );
+double _Complex strto( const char sptr[], char ** eptr );
+long double _Complex strto( const char sptr[], char ** eptr );
static inline {
- int ato( const char * sptr ) { return (int)strtol( sptr, 0p, 10 ); }
- unsigned int ato( const char * sptr ) { return (unsigned int)strtoul( sptr, 0p, 10 ); }
- long int ato( const char * sptr ) { return strtol( sptr, 0p, 10 ); }
- unsigned long int ato( const char * sptr ) { return strtoul( sptr, 0p, 10 ); }
- long long int ato( const char * sptr ) { return strtoll( sptr, 0p, 10 ); }
- unsigned long long int ato( const char * sptr ) { return strtoull( sptr, 0p, 10 ); }
-
- float ato( const char * sptr ) { return strtof( sptr, 0p ); }
- double ato( const char * sptr ) { return strtod( sptr, 0p ); }
- long double ato( const char * sptr ) { return strtold( sptr, 0p ); }
-
- float _Complex ato( const char * sptr ) { return strto( sptr, 0p ); }
- double _Complex ato( const char * sptr ) { return strto( sptr, 0p ); }
- long double _Complex ato( const char * sptr ) { return strto( sptr, 0p ); }
+ int ato( const char sptr[] ) { return (int)strtol( sptr, 0p, 10 ); }
+ unsigned int ato( const char sptr[] ) { return (unsigned int)strtoul( sptr, 0p, 10 ); }
+ long int ato( const char sptr[] ) { return strtol( sptr, 0p, 10 ); }
+ unsigned long int ato( const char sptr[] ) { return strtoul( sptr, 0p, 10 ); }
+ long long int ato( const char sptr[] ) { return strtoll( sptr, 0p, 10 ); }
+ unsigned long long int ato( const char sptr[] ) { return strtoull( sptr, 0p, 10 ); }
+
+ float ato( const char sptr[] ) { return strtof( sptr, 0p ); }
+ double ato( const char sptr[] ) { return strtod( sptr, 0p ); }
+ long double ato( const char sptr[] ) { return strtold( sptr, 0p ); }
+
+ float _Complex ato( const char sptr[] ) { return strto( sptr, 0p ); }
+ double _Complex ato( const char sptr[] ) { return strto( sptr, 0p ); }
+ long double _Complex ato( const char sptr[] ) { return strto( sptr, 0p ); }
} // distribution
Index: libcfa/src/time.cfa
===================================================================
--- libcfa/src/time.cfa (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/time.cfa (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,6 +10,6 @@
// Created On : Tue Mar 27 13:33:14 2018
// Last Modified By : Peter A. Buhr
-// Last Modified On : Sun Jan 5 17:27:40 2020
-// Update Count : 69
+// Last Modified On : Tue Feb 4 08:24:18 2020
+// Update Count : 70
//
@@ -129,5 +129,5 @@
} // dd_mm_yy
-size_t strftime( char * buf, size_t size, const char * fmt, Time time ) with( time ) {
+size_t strftime( char buf[], size_t size, const char fmt[], Time time ) with( time ) {
time_t s = tn / TIMEGRAN;
tm tm;
Index: libcfa/src/time.hfa
===================================================================
--- libcfa/src/time.hfa (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ libcfa/src/time.hfa (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,6 +10,6 @@
// Created On : Wed Mar 14 23:18:57 2018
// Last Modified By : Peter A. Buhr
-// Last Modified On : Mon Jan 6 12:50:16 2020
-// Update Count : 653
+// Last Modified On : Tue Feb 4 08:24:32 2020
+// Update Count : 654
//
@@ -191,5 +191,5 @@
} // dmy
-size_t strftime( char * buf, size_t size, const char * fmt, Time time );
+size_t strftime( char buf[], size_t size, const char fmt[], Time time );
//------------------------- timeval (cont) -------------------------
Index: longrun_tests/Makefile.in
===================================================================
--- longrun_tests/Makefile.in (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ longrun_tests/Makefile.in (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -502,11 +502,15 @@
am__v_GOC_0 = @echo " GOC " $@;
am__v_GOC_1 =
+AM_V_PY = $(am__v_PY_@AM_V@)
+am__v_PY_ = $(am__v_PY_@AM_DEFAULT_V@)
+am__v_PY_0 = @echo " PYTHON " $@;
+am__v_PY_1 =
AM_V_RUST = $(am__v_RUST_@AM_V@)
am__v_RUST_ = $(am__v_RUST_@AM_DEFAULT_V@)
-am__v_RUST_0 = @echo " RUST " $@;
+am__v_RUST_0 = @echo " RUST " $@;
am__v_RUST_1 =
AM_V_NODEJS = $(am__v_NODEJS_@AM_V@)
am__v_NODEJS_ = $(am__v_NODEJS_@AM_DEFAULT_V@)
-am__v_NODEJS_0 = @echo " NODEJS " $@;
+am__v_NODEJS_0 = @echo " NODEJS " $@;
am__v_NODEJS_1 =
AM_V_JAVAC = $(am__v_JAVAC_@AM_V@)
Index: src/CodeGen/CodeGenerator.cc
===================================================================
--- src/CodeGen/CodeGenerator.cc (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ src/CodeGen/CodeGenerator.cc (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,6 +10,6 @@
// Created On : Mon May 18 07:44:20 2015
// Last Modified By : Peter A. Buhr
-// Last Modified On : Fri Dec 13 23:13:28 2019
-// Update Count : 508
+// Last Modified On : Sun Feb 16 08:32:48 2020
+// Update Count : 532
//
#include "CodeGenerator.h"
@@ -39,5 +39,5 @@
int CodeGenerator::tabsize = 4;
- // the kinds of statements that would ideally be followed by whitespace
+ // The kinds of statements that would ideally be followed by whitespace.
bool wantSpacing( Statement * stmt) {
return dynamic_cast< IfStmt * >( stmt ) || dynamic_cast< CompoundStmt * >( stmt ) ||
@@ -78,7 +78,5 @@
}
- /* Using updateLocation at the beginning of a node and endl
- * within a node should become the method of formating.
- */
+ // Using updateLocation at the beginning of a node and endl within a node should become the method of formating.
void CodeGenerator::updateLocation( CodeLocation const & to ) {
// skip if linemarks shouldn't appear or if codelocation is unset
@@ -95,5 +93,5 @@
} else {
output << "\n# " << to.first_line << " \"" << to.filename
- << "\"\n" << indent;
+ << "\"\n" << indent;
currentLocation = to;
}
@@ -131,5 +129,5 @@
void CodeGenerator::genAttributes( list< Attribute * > & attributes ) {
- if ( attributes.empty() ) return;
+ if ( attributes.empty() ) return;
output << "__attribute__ ((";
for ( list< Attribute * >::iterator attr( attributes.begin() );; ) {
@@ -140,5 +138,5 @@
output << ")";
} // if
- if ( ++attr == attributes.end() ) break;
+ if ( ++attr == attributes.end() ) break;
output << ","; // separator
} // for
@@ -165,8 +163,8 @@
previsit( (BaseSyntaxNode *)node );
GuardAction( [this, node](){
- if ( options.printExprTypes && node->result ) {
- output << " /* " << genType( node->result, "", options ) << " */ ";
- }
- } );
+ if ( options.printExprTypes && node->result ) {
+ output << " /* " << genType( node->result, "", options ) << " */ ";
+ }
+ } );
}
@@ -399,8 +397,8 @@
extension( applicationExpr );
if ( VariableExpr * varExpr = dynamic_cast< VariableExpr* >( applicationExpr->get_function() ) ) {
- OperatorInfo opInfo;
- if ( varExpr->get_var()->get_linkage() == LinkageSpec::Intrinsic && operatorLookup( varExpr->get_var()->get_name(), opInfo ) ) {
+ const OperatorInfo * opInfo;
+ if ( varExpr->get_var()->get_linkage() == LinkageSpec::Intrinsic && ( opInfo = operatorLookup( varExpr->get_var()->get_name() ) ) ) {
std::list< Expression* >::iterator arg = applicationExpr->get_args().begin();
- switch ( opInfo.type ) {
+ switch ( opInfo->type ) {
case OT_INDEX:
assert( applicationExpr->get_args().size() == 2 );
@@ -423,12 +421,12 @@
output << "(";
(*arg++)->accept( *visitor );
- output << ") /* " << opInfo.inputName << " */";
+ output << ") /* " << opInfo->inputName << " */";
} else if ( applicationExpr->get_args().size() == 2 ) {
// intrinsic two parameter constructors are essentially bitwise assignment
output << "(";
(*arg++)->accept( *visitor );
- output << opInfo.symbol;
+ output << opInfo->symbol;
(*arg)->accept( *visitor );
- output << ") /* " << opInfo.inputName << " */";
+ output << ") /* " << opInfo->inputName << " */";
} else {
// no constructors with 0 or more than 2 parameters
@@ -441,5 +439,5 @@
assert( applicationExpr->get_args().size() == 1 );
output << "(";
- output << opInfo.symbol;
+ output << opInfo->symbol;
(*arg)->accept( *visitor );
output << ")";
@@ -450,5 +448,5 @@
assert( applicationExpr->get_args().size() == 1 );
(*arg)->accept( *visitor );
- output << opInfo.symbol;
+ output << opInfo->symbol;
break;
@@ -459,5 +457,5 @@
output << "(";
(*arg++)->accept( *visitor );
- output << opInfo.symbol;
+ output << opInfo->symbol;
(*arg)->accept( *visitor );
output << ")";
@@ -486,8 +484,8 @@
extension( untypedExpr );
if ( NameExpr * nameExpr = dynamic_cast< NameExpr* >( untypedExpr->function ) ) {
- OperatorInfo opInfo;
- if ( operatorLookup( nameExpr->name, opInfo ) ) {
+ const OperatorInfo * opInfo = operatorLookup( nameExpr->name );
+ if ( opInfo ) {
std::list< Expression* >::iterator arg = untypedExpr->args.begin();
- switch ( opInfo.type ) {
+ switch ( opInfo->type ) {
case OT_INDEX:
assert( untypedExpr->args.size() == 2 );
@@ -508,12 +506,12 @@
output << "(";
(*arg++)->accept( *visitor );
- output << ") /* " << opInfo.inputName << " */";
+ output << ") /* " << opInfo->inputName << " */";
} else if ( untypedExpr->get_args().size() == 2 ) {
// intrinsic two parameter constructors are essentially bitwise assignment
output << "(";
(*arg++)->accept( *visitor );
- output << opInfo.symbol;
+ output << opInfo->symbol;
(*arg)->accept( *visitor );
- output << ") /* " << opInfo.inputName << " */";
+ output << ") /* " << opInfo->inputName << " */";
} else {
// no constructors with 0 or more than 2 parameters
@@ -521,7 +519,7 @@
output << "(";
(*arg++)->accept( *visitor );
- output << opInfo.symbol << "{ ";
+ output << opInfo->symbol << "{ ";
genCommaList( arg, untypedExpr->args.end() );
- output << "}) /* " << opInfo.inputName << " */";
+ output << "}) /* " << opInfo->inputName << " */";
} // if
break;
@@ -532,5 +530,5 @@
assert( untypedExpr->args.size() == 1 );
output << "(";
- output << opInfo.symbol;
+ output << opInfo->symbol;
(*arg)->accept( *visitor );
output << ")";
@@ -541,5 +539,5 @@
assert( untypedExpr->args.size() == 1 );
(*arg)->accept( *visitor );
- output << opInfo.symbol;
+ output << opInfo->symbol;
break;
@@ -549,5 +547,5 @@
output << "(";
(*arg++)->accept( *visitor );
- output << opInfo.symbol;
+ output << opInfo->symbol;
(*arg)->accept( *visitor );
output << ")";
@@ -581,10 +579,10 @@
void CodeGenerator::postvisit( NameExpr * nameExpr ) {
extension( nameExpr );
- OperatorInfo opInfo;
- if ( operatorLookup( nameExpr->name, opInfo ) ) {
- if ( opInfo.type == OT_CONSTANT ) {
- output << opInfo.symbol;
+ const OperatorInfo * opInfo = operatorLookup( nameExpr->name );
+ if ( opInfo ) {
+ if ( opInfo->type == OT_CONSTANT ) {
+ output << opInfo->symbol;
} else {
- output << opInfo.outputName;
+ output << opInfo->outputName;
}
} else {
@@ -654,7 +652,7 @@
void CodeGenerator::postvisit( VariableExpr * variableExpr ) {
extension( variableExpr );
- OperatorInfo opInfo;
- if ( variableExpr->get_var()->get_linkage() == LinkageSpec::Intrinsic && operatorLookup( variableExpr->get_var()->get_name(), opInfo ) && opInfo.type == OT_CONSTANT ) {
- output << opInfo.symbol;
+ const OperatorInfo * opInfo;
+ if ( variableExpr->get_var()->get_linkage() == LinkageSpec::Intrinsic && (opInfo = operatorLookup( variableExpr->get_var()->get_name() )) && opInfo->type == OT_CONSTANT ) {
+ output << opInfo->symbol;
} else {
output << mangleName( variableExpr->get_var() );
@@ -1011,5 +1009,5 @@
case BranchStmt::FallThroughDefault:
assertf( ! options.genC, "fallthru should not reach code generation." );
- output << "fallthru";
+ output << "fallthru";
break;
} // switch
@@ -1035,5 +1033,5 @@
output << ((throwStmt->get_kind() == ThrowStmt::Terminate) ?
- "throw" : "throwResume");
+ "throw" : "throwResume");
if (throwStmt->get_expr()) {
output << " ";
@@ -1050,5 +1048,5 @@
output << ((stmt->get_kind() == CatchStmt::Terminate) ?
- "catch" : "catchResume");
+ "catch" : "catchResume");
output << "( ";
stmt->decl->accept( *visitor );
@@ -1187,7 +1185,7 @@
std::string genName( DeclarationWithType * decl ) {
- CodeGen::OperatorInfo opInfo;
- if ( operatorLookup( decl->get_name(), opInfo ) ) {
- return opInfo.outputName;
+ const OperatorInfo * opInfo = operatorLookup( decl->get_name() );
+ if ( opInfo ) {
+ return opInfo->outputName;
} else {
return decl->get_name();
Index: src/CodeGen/CodeGenerator.h
===================================================================
--- src/CodeGen/CodeGenerator.h (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ src/CodeGen/CodeGenerator.h (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -9,7 +9,7 @@
// Author : Richard C. Bilson
// Created On : Mon May 18 07:44:20 2015
-// Last Modified By : Andrew Beach
-// Last Modified On : Tue Apr 30 12:01:00 2019
-// Update Count : 57
+// Last Modified By : Peter A. Buhr
+// Last Modified On : Sun Feb 16 03:58:31 2020
+// Update Count : 62
//
@@ -29,5 +29,5 @@
namespace CodeGen {
struct CodeGenerator : public WithShortCircuiting, public WithGuards, public WithVisitorRef {
- static int tabsize;
+ static int tabsize;
CodeGenerator( std::ostream &os, bool pretty = false, bool genC = false, bool lineMarks = false, bool printExprTypes = false );
@@ -104,5 +104,5 @@
void postvisit( AsmStmt * );
void postvisit( DirectiveStmt * );
- void postvisit( AsmDecl * ); // special: statement in declaration context
+ void postvisit( AsmDecl * ); // special: statement in declaration context
void postvisit( IfStmt * );
void postvisit( SwitchStmt * );
@@ -147,7 +147,7 @@
LabelPrinter printLabels;
Options options;
- public:
+ public:
LineEnder endl;
- private:
+ private:
CodeLocation currentLocation;
@@ -162,8 +162,8 @@
template< class Iterator >
void CodeGenerator::genCommaList( Iterator begin, Iterator end ) {
- if ( begin == end ) return;
+ if ( begin == end ) return;
for ( ;; ) {
(*begin++)->accept( *visitor );
- if ( begin == end ) break;
+ if ( begin == end ) break;
output << ", "; // separator
} // for
Index: src/CodeGen/FixMain.h
===================================================================
--- src/CodeGen/FixMain.h (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ src/CodeGen/FixMain.h (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,6 +10,6 @@
// Created On : Thr Jan 12 14:11:09 2017
// Last Modified By : Peter A. Buhr
-// Last Modified On : Fri Dec 13 23:12:21 2019
-// Update Count : 3
+// Last Modified On : Sun Feb 16 03:24:32 2020
+// Update Count : 5
//
@@ -42,3 +42,3 @@
static std::unique_ptr main_signature;
};
-};
+} // namespace CodeGen
Index: src/CodeGen/GenType.h
===================================================================
--- src/CodeGen/GenType.h (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ src/CodeGen/GenType.h (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -9,7 +9,7 @@
// Author : Richard C. Bilson
// Created On : Mon May 18 07:44:20 2015
-// Last Modified By : Andrew Beach
-// Last Modified On : Tue Apr 30 11:47:00 2019
-// Update Count : 3
+// Last Modified By : Peter A. Buhr
+// Last Modified On : Sun Feb 16 04:11:40 2020
+// Update Count : 5
//
@@ -25,5 +25,5 @@
std::string genType( Type *type, const std::string &baseString, const Options &options );
std::string genType( Type *type, const std::string &baseString, bool pretty = false, bool genC = false, bool lineMarks = false );
- std::string genPrettyType( Type * type, const std::string & baseString );
+ std::string genPrettyType( Type * type, const std::string & baseString );
} // namespace CodeGen
Index: src/CodeGen/Generate.cc
===================================================================
--- src/CodeGen/Generate.cc (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ src/CodeGen/Generate.cc (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,6 +10,6 @@
// Created On : Mon May 18 07:44:20 2015
// Last Modified By : Peter A. Buhr
-// Last Modified On : Fri Dec 13 23:38:56 2019
-// Update Count : 8
+// Last Modified On : Sun Feb 16 03:01:51 2020
+// Update Count : 9
//
#include "Generate.h"
@@ -64,5 +64,5 @@
void generate( BaseSyntaxNode * node, std::ostream & os ) {
if ( Type * type = dynamic_cast< Type * >( node ) ) {
- os << CodeGen::genPrettyType( type, "" );
+ os << genPrettyType( type, "" );
} else {
PassVisitor cgv( os, true, false, false, false );
Index: src/CodeGen/OperatorTable.cc
===================================================================
--- src/CodeGen/OperatorTable.cc (revision 8c50aed95a361f33369903cfdf38ceaaefeffddf)
+++ src/CodeGen/OperatorTable.cc (revision a50502128f8eabae54ded84a8ab9885411aad583)
@@ -10,6 +10,6 @@
// Created On : Mon May 18 07:44:20 2015
// Last Modified By : Peter A. Buhr
-// Last Modified On : Sat Jul 15 17:12:22 2017
-// Update Count : 15
+// Last Modified On : Tue Feb 18 15:55:01 2020
+// Update Count : 55
//
@@ -17,4 +17,5 @@
#include