gc.h

#ifndef INCLUDED_RTS_GC_H
#define INCLUDED_RTS_GC_H

#include <cassert>
#include <cstdint>
#include <mutex>
#include <queue>
#include <unordered_set>
#include "rts/thread_local.h"
#include <boost/lockfree/queue.hpp>

namespace rts {

using std::uint16_t;
using std::uint32_t;
using std::uint64_t;
using std::uintptr_t;
using std::mutex;
using std::unordered_set;
using std::unique_lock;

namespace spaces {
  enum {
    external = 0,   
    local_min = 1,  
    local_max = 7,  
    global_min = 8, 
    global_max = 15 
  };
}

namespace triggers {
  enum {
    nmt         = 1, 
    relocation  = 2, 
    contraction = 4  
  };
}

namespace types {
  enum {
    constructor = 0, 
    closure     = 1, 
    indirection = 2, 
    blackhole   = 3  
  };
}

class hec;

struct gc_ptr;

// global garbage collector configuration

extern mutex gc_mutex;

// contents under the gc_mutex
extern uint32_t regions_begin;    // lo <= x < hi
extern uint32_t regions_end;
extern uint64_t * mapped_regions; // 1 bit per region, packed
extern unordered_set<hec*> hecs;
// end contents under the gc_mutex

extern boost::lockfree::queue<gc_ptr> global_mark_queue[8];

static inline bool protected_region(uint32_t r) {
  assert(regions_begin <= r && r < regions_end);
  return mapped_regions[r>>6]&(1<<((r-regions_begin)&0x3f));
}


struct gc_ptr {
  union {
    // layout chosen so that a 0-extended 32 bit integer is a legal 'gc_ptr' as are legal native c pointers
    // TODO: consider setting space 15 to also be a native pointer that way 0 and 1 extended pointers would
    // be legal.
    uint64_t unique   : 1,  
             type     : 2,  
             offset   : 9,  
             segment  : 9,  
             region   : 19, 
             nmt      : 1,  
             space    : 4,  
             tag      : 19; 
    uint64_t addr;
  };

  static const uint64_t mask = 0x7ffffffff8;

  template <typename T> T & operator * () {
    return *reinterpret_cast<T *>(addr&mask);
  };

  template <typename T> T * operator -> () {
    return reinterpret_cast<T *>(addr&mask);
  };

  template <typename T> T & operator [] (std::ptrdiff_t i) {
    return *reinterpret_cast<T *>((addr&mask) + (i * sizeof(T)));
  }

  // TODO: partially template specialize these to make it so gc_ptr loads from those addresses automatically apply the

  void lvb(uint64_t * address, bool unique_context = true);

  private:
    void lvb_slow_path(uint64_t * address, int trigger);
};

inline bool operator==(const gc_ptr& lhs, const gc_ptr& rhs){ return lhs.addr == rhs.addr; }
inline bool operator!=(const gc_ptr& lhs, const gc_ptr& rhs){ return lhs.addr != rhs.addr; }

class hec {
  public:
    static thread_local hec * current; 
    uint16_t expected_nmt; 
    std::queue<gc_ptr> local_mark_queue[8]; 

  private:
    hec(hec const &);               
    hec & operator = (hec const &); 

  public:
    hec() {
      current = this;
      unique_lock<mutex> lock(gc_mutex);
      hecs.insert(this);
    }
    ~hec() {
      current = nullptr;
      unique_lock<mutex> lock(gc_mutex);
      hecs.erase(this);
    }

    inline bool get_expected_nmt(int i) { return expected_nmt & (1 << i); }
};

inline void gc_ptr::lvb(uint64_t * address, bool unique_context) {
  if (space != 0) {
    int trigger = 0;
    if (nmt != hec::current->get_expected_nmt(space)) trigger |= triggers::nmt;
    if (protected_region(region))                     trigger |= triggers::relocation;
    if (!unique_context && unique)                    trigger |= triggers::contraction;
    if (trigger != 0) lvb_slow_path(address, trigger);
  }
}

} // namespace rts

#endif