source: git/kernel/oswrapper/vspace.h @ 86edf6

fieker-DuValspielwiese
Last change on this file since 86edf6 was 86edf6, checked in by Hans Schoenemann <hannes@…>, 3 years ago
vspace: add __clang__
  • Property mode set to 100644
File size: 59.7 KB
Line 
1#ifndef VSPACE_H
2#define VSPACE_H
3#include "kernel/mod2.h"
4
5#ifdef HAVE_VSPACE
6
7#if defined(__GNUC__) && (__GNUC__<9) && !defined(__clang__)
8#include <fcntl.h>
9#include <stddef.h>
10#include <stdio.h>
11#include <stdlib.h>
12#include <string.h>
13#include <sys/mman.h>
14#include <sys/stat.h>
15#include <unistd.h>
16#include <assert.h>
17#include <new> // for placement new
18
19#if __cplusplus >= 201100
20#define HAVE_CPP_THREADS
21#include <atomic>
22#else
23#undef HAVE_CPP_THREADS
24#endif
25
26// vspace is a C++ library designed to allow processes in a
27// multi-process environment to interoperate via mmapped shared memory.
28// The library provides facilities for shared memory allocation and
29// deallocation, shared mutexes, semaphores, queues, lists, and hash
30// tables.
31//
32// The underlying file is organized starting with a block containing
33// meta information such as free lists and process information necessary
34// for IPC, followed by one or more segments of mmapped memory. Each
35// address within the file is represented via its offset from the
36// beginning of the first segment.
37//
38// These offsets are wrapped within the VRef<T> class, which works like
39// a T* pointer, but transparently maps file offsets to memory
40// locations.
41
42namespace vspace {
43
44enum ErrCode {
45  ErrNone,
46  ErrGeneral,
47  ErrFile,
48  ErrMMap,
49  ErrOS,
50};
51
52template <typename T>
53struct Result {
54  bool ok;
55  T result;
56  Result(T result) : ok(true), result(result) {
57  }
58  Result() : ok(false), result(default_value()) {
59  }
60private:
61  T& default_value() {
62    static T result;
63    return result;
64  }
65};
66
67struct Status {
68  ErrCode err;
69  bool ok() {
70    return err == ErrNone;
71  }
72  operator bool() {
73    return err == ErrNone;
74  }
75  Status(ErrCode err) : err(err) {
76  }
77};
78
79namespace internals {
80
81typedef size_t segaddr_t;
82
83typedef size_t vaddr_t;
84
85const segaddr_t SEGADDR_NULL = ~(segaddr_t) 0;
86const vaddr_t VADDR_NULL = ~(segaddr_t) 0;
87
88static const int MAX_PROCESS = 64;
89static const size_t METABLOCK_SIZE = 128 * 1024; // 128 KB
90static const int LOG2_SEGMENT_SIZE = 28; // 256 MB
91static const int LOG2_MAX_SEGMENTS = 10; // 256 GB
92static const size_t MAX_SEGMENTS = 1 << LOG2_MAX_SEGMENTS;
93static const size_t SEGMENT_SIZE = 1 << LOG2_SEGMENT_SIZE;
94static const size_t SEGMENT_MASK = (SEGMENT_SIZE - 1);
95
96// This is a very basic spinlock implementation that does not guarantee
97// fairness.
98//
99// TODO: add a wait queue and/or use futexes on Linux.
100class FastLock {
101private:
102#ifdef HAVE_CPP_THREADS
103  std::atomic_flag _lock;
104  short _owner, _head, _tail;
105#else
106  vaddr_t _offset;
107#endif
108public:
109#ifdef HAVE_CPP_THREADS
110  FastLock(vaddr_t offset = 0) : _owner(-1), _head(-1), _tail(-1) {
111    _lock.clear();
112  }
113#else
114  FastLock(vaddr_t offset = 0) : _offset(offset) {
115  }
116#endif
117#ifdef HAVE_CPP_THREADS
118  // We only need to define the copy constructur for the
119  // atomic version, as the std::atomic_flag constructor
120  // is deleted.
121  FastLock(const FastLock &other) {
122    _owner = other._owner;
123    _head = other._head;
124    _tail = other._tail;
125    _lock.clear();
126  }
127  FastLock &operator=(const FastLock &other) {
128    _owner = other._owner;
129    _head = other._head;
130    _tail = other._tail;
131    _lock.clear();
132    return *this;
133  }
134#endif
135  void lock();
136  void unlock();
137};
138
139extern size_t config[4];
140
141void init_flock_struct(
142    struct flock &lock_info, size_t offset, size_t len, bool lock);
143void lock_file(int fd, size_t offset, size_t len = 1);
144void unlock_file(int fd, size_t offset, size_t len = 1);
145
146void lock_metapage();
147void unlock_metapage();
148void init_metapage(bool create);
149
150typedef int ipc_signal_t;
151
152bool send_signal(int processno, ipc_signal_t sig = 0, bool lock = true);
153ipc_signal_t check_signal(bool resume = false, bool lock = true);
154void accept_signals();
155ipc_signal_t wait_signal(bool lock = true);
156void drop_pending_signals();
157
158struct Block;
159struct MetaPage;
160struct ProcessChannel;
161
162enum SignalState {
163  Waiting = 0,
164  Pending = 1,
165  Accepted = 2,
166};
167
168struct ProcessInfo {
169  pid_t pid;
170  SignalState sigstate; // are there pending signals?
171  ipc_signal_t signal;
172#ifdef HAVE_CPP_THREADS
173  int next; // next in queue waiting for a lock.
174#endif
175};
176
177struct MetaPage {
178  size_t config_header[4];
179  FastLock allocator_lock;
180  vaddr_t freelist[LOG2_SEGMENT_SIZE + 1];
181  int segment_count;
182  ProcessInfo process_info[MAX_PROCESS];
183};
184
185// We use pipes/fifos to signal processes. For each process, fd_read is
186// where the process reads from and fd_write is where other processes
187// signal the reading process. Only single bytes are sent across each
188// channel. Because the effect of concurrent writes is undefined, bytes
189// must only be written by a single process at the time. This is usually
190// the case when the sending process knows that the receiving process is
191// waiting for a resource that the sending process currently holds. See
192// the Semaphore implementation for an example.
193
194struct ProcessChannel {
195  int fd_read, fd_write;
196};
197
198struct Block {
199  // the lowest bits of prev encode whether we are looking at an
200  // allocated or free block. For an allocared block, the lowest bits
201  // are 01. For a free block, they are 00 (for a null reference (==
202  // -1), they are 11.
203  //
204  // For allocated blocks, the higher bits encode the segment and the
205  // log2 of the block size (level). This requires LOG2_MAX_SEGMENTS +
206  // log2(sizeof(vaddr_t) * 8) + 2 bits.
207  //
208  // For free blocks, the level is stored in the data field.
209  vaddr_t prev;
210  vaddr_t next;
211  size_t data[1];
212  bool is_free() {
213    return (prev & 3) != 1;
214  }
215  int level() {
216    if (is_free())
217      return (int) data[0];
218    else
219      return (int) (prev >> (LOG2_MAX_SEGMENTS + 2));
220  }
221  void mark_as_allocated(vaddr_t vaddr, int level) {
222    vaddr_t bits = level;
223    bits <<= LOG2_MAX_SEGMENTS;
224    bits |= vaddr >> LOG2_SEGMENT_SIZE;
225    bits <<= 2;
226    bits |= 1;
227    prev = bits;
228    next = 0;
229  }
230  void mark_as_free(int level) {
231    data[0] = level;
232  }
233};
234
235struct VSeg {
236  unsigned char *base;
237  inline Block *block_ptr(segaddr_t addr) {
238    return (Block *) (base + addr);
239  }
240  bool is_free(segaddr_t addr) {
241    Block *block = block_ptr(addr);
242    return block->is_free();
243  }
244  inline void *ptr(segaddr_t addr) {
245    return (void *) (base + addr);
246  }
247  VSeg() : base(NULL) {
248  }
249  VSeg(void *base) : base((unsigned char *) base) {
250  }
251};
252
253struct VMem {
254  static VMem vmem_global;
255  MetaPage *metapage;
256  int fd;
257  FILE *file_handle;
258  int current_process; // index into process table
259  vaddr_t *freelist; // reference to metapage information
260  VSeg segments[MAX_SEGMENTS];
261  ProcessChannel channels[MAX_PROCESS];
262  inline VSeg segment(vaddr_t vaddr) {
263    return segments[vaddr >> LOG2_SEGMENT_SIZE];
264  }
265  inline size_t segment_no(vaddr_t vaddr) {
266    return vaddr >> LOG2_SEGMENT_SIZE;
267  }
268  inline vaddr_t vaddr(size_t segno, segaddr_t addr) {
269    return (segno << LOG2_SEGMENT_SIZE) | addr;
270  }
271  inline segaddr_t segaddr(vaddr_t vaddr) {
272    if (vaddr == VADDR_NULL)
273      return SEGADDR_NULL;
274    return vaddr & SEGMENT_MASK;
275  }
276  inline Block *block_ptr(vaddr_t vaddr) {
277    if (vaddr == VADDR_NULL)
278      return NULL;
279    return (Block *) (segment(vaddr).base + segaddr(vaddr));
280  }
281  inline void ensure_is_mapped(vaddr_t vaddr) {
282    int seg = vaddr >> LOG2_SEGMENT_SIZE;
283    if (segments[seg].base != NULL)
284      return;
285    segments[seg] = mmap_segment(seg);
286  }
287  inline void *to_ptr(vaddr_t vaddr) {
288    if (vaddr == VADDR_NULL)
289      return NULL;
290    ensure_is_mapped(vaddr);
291    return segment(vaddr).ptr(segaddr(vaddr));
292  }
293  size_t filesize();
294  Status init(int fd);
295  Status init();
296  Status init(const char *path);
297  void deinit();
298  void *mmap_segment(int seg);
299  void add_segment();
300};
301
302static VMem &vmem = VMem::vmem_global;
303
304inline Block *block_ptr(vaddr_t vaddr) {
305  return vmem.block_ptr(vaddr);
306}
307
308#ifdef HAVE_CPP_THREADS
309struct refcount_t {
310  std::atomic<ptrdiff_t> rc;
311  refcount_t(ptrdiff_t init) : rc(init) {
312  }
313  ptrdiff_t inc(vaddr_t vaddr) {
314    rc++;
315    return (ptrdiff_t) rc;
316  }
317  ptrdiff_t dec(vaddr_t vaddr) {
318    rc--;
319    return (ptrdiff_t) rc;
320  }
321};
322#else
323struct refcount_t {
324  ptrdiff_t rc;
325  static void lock(vaddr_t vaddr) {
326    lock_file(vmem.fd, METABLOCK_SIZE + vaddr);
327  }
328  static void unlock(vaddr_t vaddr) {
329    unlock_file(vmem.fd, METABLOCK_SIZE + vaddr);
330  }
331  refcount_t(ptrdiff_t init) : rc(init) {
332  }
333  ptrdiff_t inc(vaddr_t vaddr) {
334    lock(vaddr);
335    ptrdiff_t result = ++rc;
336    unlock(vaddr);
337    return result;
338  }
339  ptrdiff_t dec(vaddr_t vaddr) {
340    lock(vaddr);
341    ptrdiff_t result = --rc;
342    unlock(vaddr);
343    return result;
344  }
345};
346#endif
347
348static inline int find_level(size_t size) {
349  int level = 0;
350  while ((1 << (level + 8)) <= size)
351    level += 8;
352  while ((1 << level) < size)
353    level++;
354  return level;
355}
356
357static inline segaddr_t find_buddy(segaddr_t addr, int level) {
358  return addr ^ (1 << level);
359}
360
361void vmem_free(vaddr_t vaddr);
362vaddr_t vmem_alloc(size_t size);
363
364static inline vaddr_t allocated_ptr_to_vaddr(void *ptr) {
365  char *addr = (char *) ptr - sizeof(Block);
366  vaddr_t info = ((Block *) addr)->prev;
367  int seg = info & (MAX_SEGMENTS - 1);
368  unsigned char *segstart = vmem.segments[seg].base;
369  size_t offset = (unsigned char *) ptr - segstart;
370  return (seg << LOG2_SEGMENT_SIZE) | offset;
371}
372
373class Mutex {
374private:
375  int _owner;
376  int _locklevel;
377  vaddr_t _lock;
378
379public:
380  Mutex() : _owner(-1), _locklevel(0), _lock(vmem_alloc(1)) {
381  }
382  ~Mutex() {
383    vmem_free(_lock);
384  }
385  void lock() {
386    if (_owner == vmem.current_process) {
387      _locklevel++;
388    } else {
389      lock_file(vmem.fd, METABLOCK_SIZE + _lock);
390      _owner = vmem.current_process;
391      _locklevel = 1;
392    }
393  }
394  void unlock() {
395    if (--_locklevel == 0) {
396      assert(_owner == vmem.current_process);
397      _owner = -1;
398      unlock_file(vmem.fd, METABLOCK_SIZE + _lock);
399    }
400  }
401};
402
403}; // namespace internals
404
405static inline Status vmem_init() {
406  return internals::vmem.init();
407}
408
409static inline void vmem_deinit() {
410  internals::vmem.deinit();
411}
412
413template <typename T>
414struct VRef {
415private:
416  internals::vaddr_t vaddr;
417  VRef(internals::vaddr_t vaddr) : vaddr(vaddr) {
418  }
419public:
420  VRef() : vaddr(internals::VADDR_NULL) {
421  }
422  static VRef<T> from_vaddr(internals::vaddr_t vaddr) {
423    return VRef(vaddr);
424  }
425  size_t offset() const {
426    return vaddr;
427  }
428  bool operator==(VRef<T> other) {
429    return vaddr == other.vaddr;
430  }
431  bool operator!=(VRef<T> other) {
432    return vaddr != other.vaddr;
433  }
434  operator bool() const {
435    return vaddr != internals::VADDR_NULL;
436  }
437  bool is_null() {
438    return vaddr == internals::VADDR_NULL;
439  }
440  VRef(void *ptr) {
441    vaddr = internals::allocated_ptr_to_vaddr(ptr);
442  }
443  void *to_ptr() const {
444    return internals::vmem.to_ptr(vaddr);
445  }
446  T *as_ptr() const {
447    return (T *) to_ptr();
448  }
449  T &as_ref() const {
450    return *(T *) to_ptr();
451  }
452  T &operator*() const {
453    return *(T *) to_ptr();
454  }
455  T *operator->() {
456    return (T *) to_ptr();
457  }
458  VRef<T> &operator=(VRef<T> other) {
459    vaddr = other.vaddr;
460    return *this;
461  }
462  T &operator[](size_t index) {
463    return as_ptr()[index];
464  }
465  template <typename U>
466  VRef<U> cast() {
467    return VRef<U>::from_vaddr(vaddr);
468  }
469  static VRef<T> alloc(size_t n = 1) {
470    return VRef<T>(internals::vmem_alloc(n * sizeof(T)));
471  }
472  void free() {
473    as_ptr()->~T(); // explicitly call destructor
474    internals::vmem_free(vaddr);
475    vaddr = internals::VADDR_NULL;
476  }
477};
478
479template <>
480struct VRef<void> {
481private:
482  internals::vaddr_t vaddr;
483  VRef(internals::vaddr_t vaddr) : vaddr(vaddr) {
484  }
485
486public:
487  VRef() : vaddr(internals::VADDR_NULL) {
488  }
489  static VRef<void> from_vaddr(internals::vaddr_t vaddr) {
490    return VRef(vaddr);
491  }
492  size_t offset() const {
493    return vaddr;
494  }
495  operator bool() const {
496    return vaddr != internals::VADDR_NULL;
497  }
498  bool operator==(VRef<void> other) {
499    return vaddr == other.vaddr;
500  }
501  bool operator!=(VRef<void> other) {
502    return vaddr != other.vaddr;
503  }
504  bool is_null() {
505    return vaddr == internals::VADDR_NULL;
506  }
507  VRef(void *ptr) {
508    vaddr = internals::allocated_ptr_to_vaddr(ptr);
509  }
510  void *to_ptr() const {
511    return internals::vmem.to_ptr(vaddr);
512  }
513  void *as_ptr() const {
514    return (void *) to_ptr();
515  }
516  VRef<void> &operator=(VRef<void> other) {
517    vaddr = other.vaddr;
518    return *this;
519  }
520  template <typename U>
521  VRef<U> cast() {
522    return VRef<U>::from_vaddr(vaddr);
523  }
524  static VRef<void> alloc(size_t n = 1) {
525    return VRef<void>(internals::vmem_alloc(n));
526  }
527  void free() {
528    internals::vmem_free(vaddr);
529    vaddr = internals::VADDR_NULL;
530  }
531};
532
533template <typename T>
534VRef<T> vnull() {
535  return VRef<T>::from_vaddr(internals::VADDR_NULL);
536}
537
538template <typename T>
539VRef<T> vnew() {
540  VRef<T> result = VRef<T>::alloc();
541  new (result.to_ptr()) T();
542  return result;
543}
544
545template <typename T>
546VRef<T> vnew_uninitialized() {
547  VRef<T> result = VRef<T>::alloc();
548  return result;
549}
550
551template <typename T>
552VRef<T> vnew_array(size_t n) {
553  VRef<T> result = VRef<T>::alloc(n);
554  T *ptr = result.as_ptr();
555  for (size_t i = 0; i < n; i++) {
556    new (ptr + i) T();
557  }
558  return result;
559}
560
561template <typename T>
562VRef<T> vnew_uninitialized_array(size_t n) {
563  VRef<T> result = VRef<T>::alloc(n);
564  return result;
565}
566
567template <typename T, typename Arg>
568VRef<T> vnew(Arg arg) {
569  VRef<T> result = VRef<T>::alloc();
570  new (result.to_ptr()) T(arg);
571  return result;
572}
573
574template <typename T, typename Arg1, typename Arg2>
575VRef<T> vnew(Arg1 arg1, Arg2 arg2) {
576  VRef<T> result = VRef<T>::alloc();
577  new (result.to_ptr()) T(arg1, arg2);
578  return result;
579}
580
581template <typename T, typename Arg1, typename Arg2, typename Arg3>
582VRef<T> vnew(Arg1 arg1, Arg2 arg2, Arg3 arg3) {
583  VRef<T> result = VRef<T>::alloc();
584  new (result.to_ptr()) T(arg1, arg2, arg3);
585  return result;
586}
587
588template <typename T, typename Arg1, typename Arg2, typename Arg3,
589    typename Arg4>
590VRef<T> vnew(Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4) {
591  VRef<T> result = VRef<T>::alloc();
592  new (result.to_ptr()) T(arg1, arg2, arg3, arg4);
593  return result;
594}
595
596template <typename T, typename Arg1, typename Arg2, typename Arg3,
597    typename Arg4, typename Arg5>
598VRef<T> vnew(Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5 arg5) {
599  VRef<T> result = VRef<T>::alloc();
600  new (result.to_ptr()) T(arg1, arg2, arg3, arg4, arg5);
601  return result;
602}
603
604template <typename T>
605struct ZRef {
606private:
607  struct RefCounted {
608    internals::refcount_t rc;
609#if __cplusplus >= 201100
610    alignas(T)
611#endif
612        char data[sizeof(T)];
613    RefCounted() : rc(1) {
614    }
615  };
616  internals::vaddr_t vaddr;
617  internals::refcount_t &refcount() {
618    return ((RefCounted *) (internals::vmem.to_ptr(vaddr)))->rc;
619  }
620  void *to_ptr() {
621    return &(((RefCounted *) (internals::vmem.to_ptr(vaddr)))->data);
622  }
623
624public:
625  ZRef() : vaddr(internals::VADDR_NULL) {
626  }
627  ZRef(internals::vaddr_t vaddr) : vaddr(vaddr) {
628  }
629  operator bool() {
630    return vaddr != internals::VADDR_NULL;
631  }
632  bool is_null() {
633    return vaddr == internals::VADDR_NULL;
634  }
635  ZRef(void *ptr) {
636    vaddr = internals::allocated_ptr_to_vaddr(ptr);
637  }
638  T *as_ptr() const {
639    return (T *) to_ptr();
640  }
641  T &as_ref() const {
642    return *(T *) to_ptr();
643  }
644  T &operator*() const {
645    return *(T *) to_ptr();
646  }
647  T *operator->() {
648    return (T *) to_ptr();
649  }
650  ZRef<T> &operator=(ZRef<T> other) {
651    vaddr = other.vaddr;
652  }
653  template <typename U>
654  ZRef<U> cast() const {
655    return ZRef<U>(vaddr);
656  }
657  void retain() {
658    refcount().inc(vaddr);
659  }
660  void release() {
661    if (refcount().dec(vaddr) == 0) {
662      as_ref().~T();
663      internals::vmem_free(vaddr);
664    }
665  }
666  void free() {
667    as_ptr()->~T(); // explicitly call destructor
668    internals::vmem_free(vaddr);
669    vaddr = internals::VADDR_NULL;
670  }
671  static internals::vaddr_t alloc() {
672    return internals::vmem_alloc(sizeof(RefCounted));
673  }
674};
675
676template <typename T>
677ZRef<T> znull() {
678  return ZRef<T>(internals::VADDR_NULL);
679}
680
681template <typename T>
682ZRef<T> znew() {
683  ZRef<T> result = ZRef<T>::alloc();
684  new (result.to_ptr()) T();
685  return result;
686}
687
688template <typename T>
689ZRef<T> znew_uninitialized() {
690  ZRef<T> result = ZRef<T>::alloc();
691  return result;
692}
693
694template <typename T>
695ZRef<T> znew_array(size_t n) {
696  ZRef<T> result = ZRef<T>::alloc();
697  T *ptr = result.as_ptr();
698  for (size_t i = 0; i < n; i++) {
699    new (ptr + i) T();
700  }
701  return result;
702}
703
704template <typename T>
705ZRef<T> znew_uninitialized_array(size_t n) {
706  ZRef<T> result = ZRef<T>::alloc();
707  return result;
708}
709
710template <typename T, typename Arg>
711ZRef<T> znew(Arg arg) {
712  ZRef<T> result = ZRef<T>::alloc();
713  new (result.to_ptr()) T(arg);
714  return result;
715}
716
717template <typename T, typename Arg1, typename Arg2>
718ZRef<T> znew(Arg1 arg1, Arg2 arg2) {
719  ZRef<T> result = ZRef<T>::alloc();
720  new (result.to_ptr()) T(arg1, arg2);
721  return result;
722}
723
724template <typename T, typename Arg1, typename Arg2, typename Arg3>
725ZRef<T> znew(Arg1 arg1, Arg2 arg2, Arg3 arg3) {
726  ZRef<T> result = ZRef<T>::alloc();
727  new (result.to_ptr()) T(arg1, arg2, arg3);
728  return result;
729}
730
731class VString {
732private:
733  VRef<char> _buffer;
734  size_t _len;
735
736public:
737  VString(const char *s) {
738    _len = strlen(s);
739    _buffer = vnew_uninitialized_array<char>(_len + 1);
740    strcpy(_buffer.as_ptr(), s);
741  }
742  VString(const char *s, size_t len) {
743    _len = len;
744    _buffer = vnew_uninitialized_array<char>(len + 1);
745    char *buffer = _buffer.as_ptr();
746    memcpy(buffer, s, len);
747    buffer[len] = '\0';
748  }
749  VString(size_t len) {
750    _len = len;
751    _buffer = vnew_uninitialized_array<char>(len + 1);
752    _buffer[len] = '\0';
753  }
754  ~VString() {
755    _buffer.free();
756  }
757  size_t len() const {
758    return _len;
759  }
760  VRef<VString> clone() const {
761    return vnew<VString>(_buffer.as_ptr(), _len);
762  }
763  const char *str() const {
764    return _buffer.as_ptr();
765  }
766};
767
768static inline VRef<VString> vstring(const char *s) {
769  return vnew<VString>(s);
770}
771
772static inline VRef<VString> vstring(const char *s, size_t len) {
773  return vnew<VString>(s, len);
774}
775
776static inline VRef<VString> vstring(size_t len) {
777  return vnew<VString>(len);
778}
779
780
781template <typename Spec>
782class VMap {
783private:
784  typedef typename Spec::Key K;
785  typedef typename Spec::Value V;
786  struct Node {
787    VRef<Node> next;
788    size_t hash;
789    VRef<K> key;
790    VRef<V> value;
791  };
792  VRef<VRef<Node> > _buckets;
793  VRef<internals::FastLock> _locks;
794  size_t _nbuckets;
795
796  void _lock_bucket(size_t b) {
797    _locks[b].lock();
798  }
799  void _unlock_bucket(size_t b) {
800    _locks[b].unlock();
801  }
802
803public:
804  VMap(size_t size = 1024);
805  ~VMap();
806  bool add(VRef<K> key, VRef<V> value, VRef<K> &oldkey, VRef<V> &oldvalue,
807      bool replace = true);
808  bool add(VRef<K> key, VRef<V> value, bool replace = true) {
809    VRef<K> oldkey;
810    VRef<V> oldvalue;
811    return add(key, value, oldkey, oldvalue, replace);
812  }
813  bool remove(VRef<K> key, VRef<K> &oldkey, VRef<V> &oldvalue);
814  bool remove(VRef<K> key) {
815    VRef<K> oldkey;
816    VRef<V> oldvalue;
817    return remove(key, oldkey, oldvalue);
818  }
819  bool find(VRef<K> key, VRef<V> &value);
820  VRef<V> find(VRef<K> key) {
821    VRef<V> value;
822    if (find(key, value))
823      return value;
824    else
825      return vnull<V>();
826  }
827};
828
829template <typename Spec>
830VMap<Spec>::VMap(size_t size) {
831  using namespace internals;
832  _nbuckets = 8;
833  while (_nbuckets < size)
834    _nbuckets *= 2;
835  _buckets = vnew_array<VRef<Node> >(_nbuckets);
836  _locks = vnew_uninitialized_array<FastLock>(_nbuckets);
837  for (size_t i = 0; i < _nbuckets; i++)
838    _locks[i]
839        = FastLock(METABLOCK_SIZE + _locks.offset() + sizeof(FastLock) * i);
840}
841
842template <typename Spec>
843VMap<Spec>::~VMap() {
844  for (size_t b = 0; b < _nbuckets; b++) {
845    _lock_bucket(b);
846    VRef<Node> node = _buckets[b];
847    while (node) {
848      Node *node_ptr = node.as_ptr();
849      VRef<Node> next = node_ptr->next;
850      Spec::free_key(node_ptr->key);
851      Spec::free_value(node_ptr->value);
852      node.free();
853      node = next;
854    }
855    _unlock_bucket(b);
856  }
857  _buckets.free();
858  _locks.free();
859}
860
861template <typename Spec>
862bool VMap<Spec>::add(VRef<K> key, VRef<V> value, VRef<K> &oldkey,
863    VRef<V> &oldvalue, bool replace) {
864  size_t hash = Spec::hash(key.as_ptr());
865  size_t b = hash & (_nbuckets - 1);
866  _lock_bucket(b);
867  VRef<Node> node = _buckets[b];
868  VRef<Node> last = vnull<Node>();
869  while (!node.is_null()) {
870    Node *node_ptr = node.as_ptr();
871    if (hash == node_ptr->hash
872        && Spec::equal(key.as_ptr(), node_ptr->key.as_ptr())) {
873      value = node_ptr->value;
874      if (!last.is_null()) {
875        // move to front
876        last->next = node_ptr->next;
877        node_ptr->next = _buckets[b];
878        _buckets[b] = node;
879      }
880      oldkey = node_ptr->key;
881      oldvalue = node_ptr->value;
882      if (replace) {
883        node_ptr->key = key;
884        node_ptr->value = value;
885      }
886      _unlock_bucket(b);
887      return false;
888    }
889    last = node;
890    node = node->next;
891  }
892  node = vnew<Node>();
893  Node *node_ptr = node.as_ptr();
894  node_ptr->hash = hash;
895  node_ptr->key = key;
896  node_ptr->value = value;
897  node_ptr->next = _buckets[b];
898  _buckets[b] = node;
899  oldkey = key;
900  oldvalue = value;
901  _unlock_bucket(b);
902  return true;
903}
904
905template <typename Spec>
906bool VMap<Spec>::remove(VRef<K> key, VRef<K> &oldkey, VRef<V> &oldvalue) {
907  size_t hash = Spec::hash(key.as_ptr());
908  size_t b = hash & (_nbuckets - 1);
909  _lock_bucket(b);
910  VRef<Node> node = _buckets[b];
911  VRef<Node> last = vnull<Node>();
912  while (!node.is_null()) {
913    Node *node_ptr = node.as_ptr();
914    if (hash == node_ptr->hash
915        && Spec::equal(key.as_ptr(), node_ptr->key.as_ptr())) {
916      oldkey = node_ptr->key;
917      oldvalue = node_ptr->value;
918      // remove from list
919      if (last.is_null()) {
920        _buckets[b] = node_ptr->next;
921      } else {
922        last->next = node_ptr->next;
923      }
924      _unlock_bucket(b);
925      return true;
926    }
927    last = node;
928    node = node->next;
929  }
930  _unlock_bucket(b);
931  return false;
932}
933
934template <typename Spec>
935bool VMap<Spec>::find(VRef<K> key, VRef<V> &value) {
936  size_t hash = Spec::hash(key.as_ptr());
937  size_t b = hash & (_nbuckets - 1);
938  _lock_bucket(b);
939  VRef<Node> node = _buckets[b];
940  VRef<Node> last = vnull<Node>();
941  while (!node.is_null()) {
942    Node *node_ptr = node.as_ptr();
943    if (hash == node_ptr->hash
944        && Spec::equal(key.as_ptr(), node_ptr->key.as_ptr())) {
945      value = node_ptr->value;
946      // move to front
947      if (!last.is_null()) {
948        last->next = node_ptr->next;
949        node_ptr->next = _buckets[b];
950      }
951      _buckets[b] = node;
952      _unlock_bucket(b);
953      return true;
954    }
955    last = node;
956    node = node->next;
957  }
958  _unlock_bucket(b);
959  return false;
960}
961
962struct DictSpec {
963  typedef VString Key;
964  typedef VString Value;
965  static size_t hash(const VString *s) {
966    // DJB hash
967    size_t len = s->len();
968    const char *str = s->str();
969    size_t hash = 5381;
970    for (size_t i = 0; i < len; i++) {
971      hash = 33 * hash + str[i];
972    }
973    return hash;
974  }
975  static bool equal(const VString *s1, const VString *s2) {
976    if (s1->len() != s2->len())
977      return false;
978    size_t len = s1->len();
979    const char *str1 = s1->str(), *str2 = s2->str();
980    for (size_t i = 0; i < len; i++) {
981      if (str1[i] != str2[i])
982        return false;
983    }
984    return true;
985  }
986  // By default, we do not make assumptions about ownership. It is
987  // up to the caller to free keys and values if needed or to
988  // define appropriate `free_key()` and `free_value()` functions
989  // that work. Note in particular that keys and values may occur
990  // more than once in a map and if that happens, they must not
991  // be freed multiple times.
992  static void free_key(VRef<Key> key) {
993    // do nothing
994  }
995  static void free_value(VRef<Value> value) {
996    // do nothing
997  }
998};
999
1000typedef VMap<DictSpec> VDict;
1001
1002pid_t fork_process();
1003
1004#ifdef HAVE_CPP_THREADS
1005typedef internals::FastLock FastLock;
1006#else
1007typedef internals::Mutex FastLock;
1008#endif
1009
1010typedef internals::Mutex Mutex;
1011
1012class Semaphore {
1013private:
1014  int _owner;
1015  int _waiting[internals::MAX_PROCESS + 1];
1016  internals::ipc_signal_t _signals[internals::MAX_PROCESS + 1];
1017  int _head, _tail;
1018  void next(int &index) {
1019    if (index == internals::MAX_PROCESS)
1020      index = 0;
1021    else
1022      index++;
1023  }
1024  size_t _value;
1025  FastLock _lock;
1026  bool _idle() {
1027    return _head == _tail;
1028  }
1029  template <typename T>
1030  friend class SyncVar;
1031
1032public:
1033  Semaphore(size_t value = 0) :
1034      _owner(0), _head(0), _tail(0), _value(value), _lock() {
1035  }
1036  size_t value() {
1037    return _value;
1038  }
1039  void post();
1040  bool try_wait();
1041  void wait();
1042  bool start_wait(internals::ipc_signal_t sig = 0);
1043  bool stop_wait();
1044};
1045
1046template <typename T>
1047class Queue {
1048private:
1049  struct Node {
1050    VRef<Node> next;
1051    T data;
1052  };
1053  Semaphore _incoming;
1054  Semaphore _outgoing;
1055  bool _bounded;
1056  FastLock _lock;
1057  VRef<Node> _head, _tail;
1058  VRef<Node> pop() {
1059    VRef<Node> result = _head;
1060    if (_head->next.is_null()) {
1061      _head = _tail = vnull<Node>();
1062    } else {
1063      _head = _head->next;
1064    }
1065    return result;
1066  }
1067  void push(VRef<Node> node) {
1068    node->next = vnull<Node>();
1069    if (_tail.is_null()) {
1070      _head = _tail = node;
1071    } else {
1072      _tail->next = node;
1073      _tail = node;
1074    }
1075  }
1076  template <typename U>
1077  friend class EnqueueEvent;
1078  template <typename U>
1079  friend class DequeueEvent;
1080
1081  void enqueue_nowait(T item) {
1082    _lock.lock();
1083    VRef<Node> node = vnew<Node>();
1084    node->data = item;
1085    push(node);
1086    _lock.unlock();
1087    _incoming.post();
1088  }
1089  T dequeue_nowait() {
1090    _lock.lock();
1091    VRef<Node> node = pop();
1092    T result;
1093    result = node->data;
1094    node.free();
1095    _lock.unlock();
1096    if (_bounded)
1097      _outgoing.post();
1098    return result;
1099  }
1100
1101public:
1102  Queue(size_t bound = 0) :
1103      _incoming(0),
1104      _outgoing(bound),
1105      _bounded(bound != 0),
1106      _head(),
1107      _tail(),
1108      _lock() {
1109  }
1110  void enqueue(T item) {
1111    if (_bounded)
1112      _outgoing.wait();
1113    enqueue_nowait(item);
1114  }
1115  bool try_enqueue(T item) {
1116    if (_bounded && _outgoing.try_wait()) {
1117      enqueue_nowait(item);
1118      return true;
1119    } else {
1120      return false;
1121    }
1122  }
1123  T dequeue() {
1124    _incoming.wait();
1125    return dequeue_nowait();
1126  }
1127  Result<T> try_dequeue() {
1128    if (_incoming.try_wait())
1129      return Result<T>(dequeue_nowait());
1130    else
1131      return Result<T>();
1132  }
1133};
1134
1135template <typename T>
1136class SyncVar {
1137private:
1138  FastLock _lock;
1139  VRef<Semaphore> _sem;
1140  bool _set;
1141  T _value;
1142  template <typename U>
1143  friend class SyncReadEvent;
1144  bool start_wait(internals::ipc_signal_t sig);
1145  void stop_wait();
1146public:
1147  SyncVar() : _set(false) { }
1148  T read();
1149  Result<T> try_read();
1150  bool write(T value);
1151  bool test() {
1152    return _set;
1153  }
1154};
1155
1156template <typename T>
1157bool SyncVar<T>::start_wait(internals::ipc_signal_t sig) {
1158  _lock.lock();
1159  if (_set) {
1160    internals::send_signal(internals::vmem.current_process, sig);
1161    _lock.unlock();
1162    return true;
1163  }
1164  if (_sem.is_null()) {
1165    _sem = vnew<Semaphore>();
1166  }
1167  bool result = _sem->start_wait(sig);
1168  _lock.unlock();
1169  return result;
1170}
1171
1172template <typename T>
1173void SyncVar<T>::stop_wait() {
1174  _lock.lock();
1175  if (!_sem.is_null()) {
1176    _sem->stop_wait();
1177    if (!_sem->_idle())
1178      _sem->post();
1179  }
1180  _lock.unlock();
1181}
1182
1183template <typename T>
1184T SyncVar<T>::read() {
1185  _lock.lock();
1186  if (_set) {
1187    _lock.unlock();
1188    return _value;
1189  }
1190  if (_sem.is_null()) {
1191    _sem = vnew<Semaphore>();
1192  }
1193  // We can't wait inside the lock without deadlocking; but waiting outside
1194  // could cause a race condition with _sem being freed due to being idle.
1195  // Thus, we use start_wait() to insert ourselves into the queue, then
1196  // use wait_signal() outside the lock to complete waiting.
1197  //
1198  // Note: start_wait() will not send a signal to self, as _set is
1199  // false and therefore _sem->value() must be zero.
1200  _sem->start_wait(0);
1201  _lock.unlock();
1202  internals::wait_signal();
1203  _lock.lock();
1204  if (_sem->_idle())
1205    _sem->post();
1206  else {
1207    _sem.free();
1208    _sem = vnull<Semaphore>();
1209  }
1210  _lock.unlock();
1211  return _value;
1212}
1213
1214template <typename T>
1215Result<T> SyncVar<T>::try_read() {
1216  _lock.lock();
1217  Result<T> result = _set ? Result<T>(_value) : Result<T>();
1218  _lock.unlock();
1219  return result;
1220}
1221
1222template <typename T>
1223bool SyncVar<T>::write(T value) {
1224  _lock.lock();
1225  if (_set) {
1226    _lock.unlock();
1227    return false;
1228  }
1229  _set = true;
1230  _value = value;
1231  if (!_sem->_idle())
1232    _sem->post();
1233  _lock.unlock();
1234  return true;
1235}
1236
1237class Event {
1238private:
1239  Event *_next;
1240  friend class EventSet;
1241public:
1242  virtual bool start_listen(internals::ipc_signal_t sig) = 0;
1243  virtual void stop_listen() = 0;
1244};
1245
1246class EventSet {
1247private:
1248  Event *_head, *_tail;
1249
1250public:
1251  EventSet() : _head(NULL), _tail(NULL) {
1252  }
1253  void add(Event *event);
1254  void add(Event &event) {
1255    add(&event);
1256  }
1257  EventSet &operator<<(Event *event) {
1258    add(event);
1259    return *this;
1260  }
1261  EventSet &operator<<(Event &event) {
1262    add(event);
1263    return *this;
1264  }
1265  int wait();
1266};
1267
1268class WaitSemaphoreEvent : public Event {
1269private:
1270  VRef<Semaphore> _sem;
1271
1272public:
1273  WaitSemaphoreEvent(VRef<Semaphore> sem) : _sem(sem) {
1274  }
1275  virtual bool start_listen(internals::ipc_signal_t sig) {
1276    return _sem->start_wait(sig);
1277  }
1278  virtual void stop_listen() {
1279    _sem->stop_wait();
1280  }
1281  void complete() {
1282  }
1283};
1284
1285template <typename T>
1286class EnqueueEvent : public Event {
1287private:
1288  VRef<Queue<T> > _queue;
1289
1290public:
1291  EnqueueEvent(VRef<Queue<T> > queue) : _queue(queue) {
1292  }
1293  virtual bool start_listen(internals::ipc_signal_t sig) {
1294    return _queue->_outgoing.start_wait(sig);
1295  }
1296  virtual void stop_listen() {
1297    _queue->_outgoing.stop_wait();
1298  }
1299  void complete(T item) {
1300    _queue->enqueue_nowait(item);
1301  }
1302};
1303
1304template <typename T>
1305class DequeueEvent : public Event {
1306private:
1307  VRef<Queue<T> > _queue;
1308
1309public:
1310  DequeueEvent(VRef<Queue<T> > queue) : _queue(queue) {
1311  }
1312  virtual bool start_listen(internals::ipc_signal_t sig) {
1313    return _queue->_incoming.start_wait(sig);
1314  }
1315  virtual void stop_listen() {
1316    _queue->_incoming.stop_wait();
1317  }
1318  T complete() {
1319    return _queue->dequeue_nowait();
1320  }
1321};
1322
1323template <typename T>
1324class SyncReadEvent : public Event {
1325private:
1326  VRef<SyncVar<T> > _syncvar;
1327
1328public:
1329  SyncReadEvent(VRef<SyncVar<T> > syncvar) : _syncvar(syncvar) {
1330  }
1331  virtual bool start_listen(internals::ipc_signal_t sig) {
1332    return _syncvar->start_wait(sig);
1333  }
1334  virtual void stop_listen() {
1335    _syncvar->stop_wait();
1336  }
1337  T complete() {
1338    return _syncvar->read();
1339  }
1340};
1341
1342}; // namespace vspace
1343#else
1344#include <fcntl.h>
1345#include <cstdio>
1346#include <cstring>
1347#include <assert.h>
1348#include <new> // for placement new
1349
1350#if __cplusplus >= 201100
1351#define HAVE_CPP_THREADS
1352#include <atomic>
1353#else
1354#undef HAVE_CPP_THREADS
1355#endif
1356
1357// VSpace is a C++ library designed to allow processes in a
1358// multi-process environment to interoperate via mmapped shared memory.
1359// The library provides facilities for shared memory allocation and
1360// deallocation, shared mutexes, semaphores, queues, lists, and hash
1361// tables.
1362//
1363// The underlying file is organized starting with a block containing
1364// meta information such as free lists and process information necessary
1365// for IPC, followed by one or more segments of mmapped memory. Each
1366// address within the file is represented via its offset from the
1367// beginning of the first segment.
1368//
1369// These offsets are wrapped within the VRef<T> class, which works like
1370// a T* pointer, but transparently maps file offsets to memory
1371// locations.
1372
1373namespace vspace {
1374
1375enum ErrCode {
1376  ErrNone,
1377  ErrGeneral,
1378  ErrFile,
1379  ErrMMap,
1380  ErrOS,
1381};
1382
1383template <typename T>
1384struct Result {
1385  bool ok;
1386  T result;
1387  Result(T result) : ok(true), result(result) {
1388  }
1389  Result() : ok(false), result(default_value()) {
1390  }
1391private:
1392  T& default_value() {
1393    static T result;
1394    return result;
1395  }
1396};
1397
1398struct Status {
1399  ErrCode err;
1400  bool ok() {
1401    return err == ErrNone;
1402  }
1403  operator bool() {
1404    return err == ErrNone;
1405  }
1406  Status(ErrCode err) : err(err) {
1407  }
1408};
1409
1410namespace internals {
1411
1412typedef size_t segaddr_t;
1413
1414typedef size_t vaddr_t;
1415
1416const segaddr_t SEGADDR_NULL = ~(segaddr_t) 0;
1417const vaddr_t VADDR_NULL = ~(segaddr_t) 0;
1418
1419static const int MAX_PROCESS = 64;
1420static const size_t METABLOCK_SIZE = 128 * 1024; // 128 KB
1421static const int LOG2_SEGMENT_SIZE = 28; // 256 MB
1422static const int LOG2_MAX_SEGMENTS = 10; // 256 GB
1423static const size_t MAX_SEGMENTS = 1 << LOG2_MAX_SEGMENTS;
1424static const size_t SEGMENT_SIZE = 1 << LOG2_SEGMENT_SIZE;
1425static const size_t SEGMENT_MASK = (SEGMENT_SIZE - 1);
1426
1427// This is a very basic spinlock implementation that does not guarantee
1428// fairness.
1429//
1430// TODO: add a wait queue and/or use futexes on Linux.
1431class FastLock {
1432private:
1433#ifdef HAVE_CPP_THREADS
1434  std::atomic_flag _lock;
1435  short _owner, _head, _tail;
1436#else
1437  vaddr_t _offset;
1438#endif
1439public:
1440#ifdef HAVE_CPP_THREADS
1441  FastLock(vaddr_t offset = 0) : _owner(-1), _head(-1), _tail(-1) {
1442    _lock.clear();
1443  }
1444#else
1445  FastLock(vaddr_t offset = 0) : _offset(offset) {
1446  }
1447#endif
1448#ifdef HAVE_CPP_THREADS
1449  // We only need to define the copy constructur for the
1450  // atomic version, as the std::atomic_flag constructor
1451  // is deleted.
1452  FastLock(const FastLock &other) {
1453    _owner = other._owner;
1454    _head = other._head;
1455    _tail = other._tail;
1456    _lock.clear();
1457  }
1458  FastLock &operator=(const FastLock &other) {
1459    _owner = other._owner;
1460    _head = other._head;
1461    _tail = other._tail;
1462    _lock.clear();
1463    return *this;
1464  }
1465#endif
1466  void lock();
1467  void unlock();
1468};
1469
1470extern size_t config[4];
1471
1472void init_flock_struct(
1473    struct flock &lock_info, size_t offset, size_t len, bool lock);
1474void lock_file(int fd, size_t offset, size_t len = 1);
1475void unlock_file(int fd, size_t offset, size_t len = 1);
1476
1477void lock_metapage();
1478void unlock_metapage();
1479void init_metapage(bool create);
1480
1481typedef int ipc_signal_t;
1482
1483bool send_signal(int processno, ipc_signal_t sig = 0, bool lock = true);
1484ipc_signal_t check_signal(bool resume = false, bool lock = true);
1485void accept_signals();
1486ipc_signal_t wait_signal(bool lock = true);
1487void drop_pending_signals();
1488
1489struct Block;
1490struct MetaPage;
1491struct ProcessChannel;
1492
1493enum SignalState {
1494  Waiting = 0,
1495  Pending = 1,
1496  Accepted = 2,
1497};
1498
1499struct ProcessInfo {
1500  pid_t pid;
1501  SignalState sigstate; // are there pending signals?
1502  ipc_signal_t signal;
1503#ifdef HAVE_CPP_THREADS
1504  int next; // next in queue waiting for a lock.
1505#endif
1506};
1507
1508struct MetaPage {
1509  size_t config_header[4];
1510  FastLock allocator_lock;
1511  vaddr_t freelist[LOG2_SEGMENT_SIZE + 1];
1512  int segment_count;
1513  ProcessInfo process_info[MAX_PROCESS];
1514};
1515
1516// We use pipes/fifos to signal processes. For each process, fd_read is
1517// where the process reads from and fd_write is where other processes
1518// signal the reading process. Only single bytes are sent across each
1519// channel. Because the effect of concurrent writes is undefined, bytes
1520// must only be written by a single process at the time. This is usually
1521// the case when the sending process knows that the receiving process is
1522// waiting for a resource that the sending process currently holds. See
1523// the Semaphore implementation for an example.
1524
1525struct ProcessChannel {
1526  int fd_read, fd_write;
1527};
1528
1529struct Block {
1530  // the lowest bits of prev encode whether we are looking at an
1531  // allocated or free block. For an allocared block, the lowest bits
1532  // are 01. For a free block, they are 00 (for a null reference (==
1533  // -1), they are 11.
1534  //
1535  // For allocated blocks, the higher bits encode the segment and the
1536  // log2 of the block size (level). This requires LOG2_MAX_SEGMENTS +
1537  // log2(sizeof(vaddr_t) * 8) + 2 bits.
1538  //
1539  // For free blocks, the level is stored in the data field.
1540  vaddr_t prev;
1541  vaddr_t next;
1542  size_t data[1];
1543  bool is_free() {
1544    return (prev & 3) != 1;
1545  }
1546  int level() {
1547    if (is_free())
1548      return (int) data[0];
1549    else
1550      return (int) (prev >> (LOG2_MAX_SEGMENTS + 2));
1551  }
1552  void mark_as_allocated(vaddr_t vaddr, int level) {
1553    vaddr_t bits = level;
1554    bits <<= LOG2_MAX_SEGMENTS;
1555    bits |= vaddr >> LOG2_SEGMENT_SIZE;
1556    bits <<= 2;
1557    bits |= 1;
1558    prev = bits;
1559    next = 0;
1560  }
1561  void mark_as_free(int level) {
1562    data[0] = level;
1563  }
1564};
1565
1566struct VSeg {
1567  unsigned char *base;
1568  inline bool is_free() {
1569    return base == NULL;
1570  }
1571  inline Block *block_ptr(segaddr_t addr) {
1572    return (Block *) (base + addr);
1573  }
1574  bool is_free(segaddr_t addr) {
1575    Block *block = block_ptr(addr);
1576    return block->is_free();
1577  }
1578  inline void *ptr(segaddr_t addr) {
1579    return (void *) (base + addr);
1580  }
1581  VSeg() : base(NULL) {
1582  }
1583  VSeg(void *base) : base((unsigned char *) base) {
1584  }
1585};
1586
1587struct VMem {
1588  static VMem vmem_global;
1589  MetaPage *metapage;
1590  int fd;
1591  std::FILE *file_handle;
1592  int current_process; // index into process table
1593  vaddr_t *freelist; // reference to metapage information
1594  VSeg segments[MAX_SEGMENTS];
1595  ProcessChannel channels[MAX_PROCESS];
1596  inline VSeg segment(vaddr_t vaddr) {
1597    return segments[vaddr >> LOG2_SEGMENT_SIZE];
1598  }
1599  inline size_t segment_no(vaddr_t vaddr) {
1600    return vaddr >> LOG2_SEGMENT_SIZE;
1601  }
1602  inline vaddr_t vaddr(size_t segno, segaddr_t addr) {
1603    return (segno << LOG2_SEGMENT_SIZE) | addr;
1604  }
1605  inline segaddr_t segaddr(vaddr_t vaddr) {
1606    if (vaddr == VADDR_NULL)
1607      return SEGADDR_NULL;
1608    return vaddr & SEGMENT_MASK;
1609  }
1610  inline Block *block_ptr(vaddr_t vaddr) {
1611    if (vaddr == VADDR_NULL)
1612      return NULL;
1613    return (Block *) (segment(vaddr).base + segaddr(vaddr));
1614  }
1615  inline void ensure_is_mapped(vaddr_t vaddr) {
1616    int seg = vaddr >> LOG2_SEGMENT_SIZE;
1617    if (segments[seg].is_free())
1618      segments[seg] = mmap_segment(seg);
1619  }
1620  inline void *to_ptr(vaddr_t vaddr) {
1621    if (vaddr == VADDR_NULL)
1622      return NULL;
1623    ensure_is_mapped(vaddr);
1624    return segment(vaddr).ptr(segaddr(vaddr));
1625  }
1626  size_t filesize();
1627  Status init(int fd);
1628  Status init();
1629  Status init(const char *path);
1630  void deinit();
1631  void *mmap_segment(int seg);
1632  void add_segment();
1633};
1634
1635static VMem &vmem = VMem::vmem_global;
1636
1637inline Block *block_ptr(vaddr_t vaddr) {
1638  return vmem.block_ptr(vaddr);
1639}
1640
1641#ifdef HAVE_CPP_THREADS
1642struct refcount_t {
1643  std::atomic<std::ptrdiff_t> rc;
1644  refcount_t(std::ptrdiff_t init) : rc(init) {
1645  }
1646  std::ptrdiff_t inc(vaddr_t vaddr) {
1647    rc++;
1648    return (std::ptrdiff_t) rc;
1649  }
1650  std::ptrdiff_t dec(vaddr_t vaddr) {
1651    rc--;
1652    return (std::ptrdiff_t) rc;
1653  }
1654};
1655#else
1656struct refcount_t {
1657  std::ptrdiff_t rc;
1658  static void lock(vaddr_t vaddr) {
1659    lock_file(vmem.fd, METABLOCK_SIZE + vaddr);
1660  }
1661  static void unlock(vaddr_t vaddr) {
1662    unlock_file(vmem.fd, METABLOCK_SIZE + vaddr);
1663  }
1664  refcount_t(std::ptrdiff_t init) : rc(init) {
1665  }
1666  std::ptrdiff_t inc(vaddr_t vaddr) {
1667    lock(vaddr);
1668    std::ptrdiff_t result = ++rc;
1669    unlock(vaddr);
1670    return result;
1671  }
1672  std::ptrdiff_t dec(vaddr_t vaddr) {
1673    lock(vaddr);
1674    std::ptrdiff_t result = --rc;
1675    unlock(vaddr);
1676    return result;
1677  }
1678};
1679#endif
1680
1681static inline int find_level(size_t size) {
1682  int level = 0;
1683  while ((1 << (level + 8)) <= size)
1684    level += 8;
1685  while ((1 << level) < size)
1686    level++;
1687  return level;
1688}
1689
1690static inline segaddr_t find_buddy(segaddr_t addr, int level) {
1691  return addr ^ (1 << level);
1692}
1693
1694void vmem_free(vaddr_t vaddr);
1695vaddr_t vmem_alloc(size_t size);
1696
1697static inline vaddr_t allocated_ptr_to_vaddr(void *ptr) {
1698  char *addr = (char *) ptr - sizeof(Block);
1699  vaddr_t info = ((Block *) addr)->prev;
1700  int seg = info & (MAX_SEGMENTS - 1);
1701  unsigned char *segstart = vmem.segments[seg].base;
1702  size_t offset = (unsigned char *) ptr - segstart;
1703  return (seg << LOG2_SEGMENT_SIZE) | offset;
1704}
1705
1706class Mutex {
1707private:
1708  int _owner;
1709  int _locklevel;
1710  vaddr_t _lock;
1711
1712public:
1713  Mutex() : _owner(-1), _locklevel(0), _lock(vmem_alloc(1)) {
1714  }
1715  ~Mutex() {
1716    vmem_free(_lock);
1717  }
1718  void lock() {
1719    if (_owner == vmem.current_process) {
1720      _locklevel++;
1721    } else {
1722      lock_file(vmem.fd, METABLOCK_SIZE + _lock);
1723      _owner = vmem.current_process;
1724      _locklevel = 1;
1725    }
1726  }
1727  void unlock() {
1728    if (--_locklevel == 0) {
1729      assert(_owner == vmem.current_process);
1730      _owner = -1;
1731      unlock_file(vmem.fd, METABLOCK_SIZE + _lock);
1732    }
1733  }
1734};
1735
1736}; // namespace internals
1737
1738static inline Status vmem_init() {
1739  return internals::vmem.init();
1740}
1741
1742static inline void vmem_deinit() {
1743  internals::vmem.deinit();
1744}
1745
1746template <typename T>
1747struct VRef {
1748private:
1749  internals::vaddr_t vaddr;
1750  VRef(internals::vaddr_t vaddr) : vaddr(vaddr) {
1751  }
1752public:
1753  VRef() : vaddr(internals::VADDR_NULL) {
1754  }
1755  static VRef<T> from_vaddr(internals::vaddr_t vaddr) {
1756    return VRef(vaddr);
1757  }
1758  size_t offset() const {
1759    return vaddr;
1760  }
1761  bool operator==(VRef<T> other) {
1762    return vaddr == other.vaddr;
1763  }
1764  bool operator!=(VRef<T> other) {
1765    return vaddr != other.vaddr;
1766  }
1767  operator bool() const {
1768    return vaddr != internals::VADDR_NULL;
1769  }
1770  bool is_null() {
1771    return vaddr == internals::VADDR_NULL;
1772  }
1773  VRef(void *ptr) {
1774    vaddr = internals::allocated_ptr_to_vaddr(ptr);
1775  }
1776  void *to_ptr() const {
1777    return internals::vmem.to_ptr(vaddr);
1778  }
1779  T *as_ptr() const {
1780    return (T *) to_ptr();
1781  }
1782  T &as_ref() const {
1783    return *(T *) to_ptr();
1784  }
1785  T &operator*() const {
1786    return *(T *) to_ptr();
1787  }
1788  T *operator->() {
1789    return (T *) to_ptr();
1790  }
1791  VRef<T> &operator=(VRef<T> other) {
1792    vaddr = other.vaddr;
1793    return *this;
1794  }
1795  T &operator[](size_t index) {
1796    return as_ptr()[index];
1797  }
1798  template <typename U>
1799  VRef<U> cast() {
1800    return VRef<U>::from_vaddr(vaddr);
1801  }
1802  static VRef<T> alloc(size_t n = 1) {
1803    return VRef<T>(internals::vmem_alloc(n * sizeof(T)));
1804  }
1805  void free() {
1806    as_ptr()->~T(); // explicitly call destructor
1807    internals::vmem_free(vaddr);
1808    vaddr = internals::VADDR_NULL;
1809  }
1810};
1811
1812template <>
1813struct VRef<void> {
1814private:
1815  internals::vaddr_t vaddr;
1816  VRef(internals::vaddr_t vaddr) : vaddr(vaddr) {
1817  }
1818
1819public:
1820  VRef() : vaddr(internals::VADDR_NULL) {
1821  }
1822  static VRef<void> from_vaddr(internals::vaddr_t vaddr) {
1823    return VRef(vaddr);
1824  }
1825  size_t offset() const {
1826    return vaddr;
1827  }
1828  operator bool() const {
1829    return vaddr != internals::VADDR_NULL;
1830  }
1831  bool operator==(VRef<void> other) {
1832    return vaddr == other.vaddr;
1833  }
1834  bool operator!=(VRef<void> other) {
1835    return vaddr != other.vaddr;
1836  }
1837  bool is_null() {
1838    return vaddr == internals::VADDR_NULL;
1839  }
1840  VRef(void *ptr) {
1841    vaddr = internals::allocated_ptr_to_vaddr(ptr);
1842  }
1843  void *to_ptr() const {
1844    return internals::vmem.to_ptr(vaddr);
1845  }
1846  void *as_ptr() const {
1847    return (void *) to_ptr();
1848  }
1849  VRef<void> &operator=(VRef<void> other) {
1850    vaddr = other.vaddr;
1851    return *this;
1852  }
1853  template <typename U>
1854  VRef<U> cast() {
1855    return VRef<U>::from_vaddr(vaddr);
1856  }
1857  static VRef<void> alloc(size_t n = 1) {
1858    return VRef<void>(internals::vmem_alloc(n));
1859  }
1860  void free() {
1861    internals::vmem_free(vaddr);
1862    vaddr = internals::VADDR_NULL;
1863  }
1864};
1865
1866template <typename T>
1867VRef<T> vnull() {
1868  return VRef<T>::from_vaddr(internals::VADDR_NULL);
1869}
1870
1871template <typename T>
1872VRef<T> vnew() {
1873  VRef<T> result = VRef<T>::alloc();
1874  new (result.to_ptr()) T();
1875  return result;
1876}
1877
1878template <typename T>
1879VRef<T> vnew_uninitialized() {
1880  VRef<T> result = VRef<T>::alloc();
1881  return result;
1882}
1883
1884template <typename T>
1885VRef<T> vnew_array(size_t n) {
1886  VRef<T> result = VRef<T>::alloc(n);
1887  T *ptr = result.as_ptr();
1888  for (size_t i = 0; i < n; i++) {
1889    new (ptr + i) T();
1890  }
1891  return result;
1892}
1893
1894template <typename T>
1895VRef<T> vnew_uninitialized_array(size_t n) {
1896  VRef<T> result = VRef<T>::alloc(n);
1897  return result;
1898}
1899
1900template <typename T, typename Arg>
1901VRef<T> vnew(Arg arg) {
1902  VRef<T> result = VRef<T>::alloc();
1903  new (result.to_ptr()) T(arg);
1904  return result;
1905}
1906
1907template <typename T, typename Arg1, typename Arg2>
1908VRef<T> vnew(Arg1 arg1, Arg2 arg2) {
1909  VRef<T> result = VRef<T>::alloc();
1910  new (result.to_ptr()) T(arg1, arg2);
1911  return result;
1912}
1913
1914template <typename T, typename Arg1, typename Arg2, typename Arg3>
1915VRef<T> vnew(Arg1 arg1, Arg2 arg2, Arg3 arg3) {
1916  VRef<T> result = VRef<T>::alloc();
1917  new (result.to_ptr()) T(arg1, arg2, arg3);
1918  return result;
1919}
1920
1921template <typename T, typename Arg1, typename Arg2, typename Arg3,
1922    typename Arg4>
1923VRef<T> vnew(Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4) {
1924  VRef<T> result = VRef<T>::alloc();
1925  new (result.to_ptr()) T(arg1, arg2, arg3, arg4);
1926  return result;
1927}
1928
1929template <typename T, typename Arg1, typename Arg2, typename Arg3,
1930    typename Arg4, typename Arg5>
1931VRef<T> vnew(Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5 arg5) {
1932  VRef<T> result = VRef<T>::alloc();
1933  new (result.to_ptr()) T(arg1, arg2, arg3, arg4, arg5);
1934  return result;
1935}
1936
1937template <typename T>
1938struct ZRef {
1939private:
1940  struct RefCounted {
1941    internals::refcount_t rc;
1942#if __cplusplus >= 201100
1943    alignas(T)
1944#endif
1945        char data[sizeof(T)];
1946    RefCounted() : rc(1) {
1947    }
1948  };
1949  internals::vaddr_t vaddr;
1950  internals::refcount_t &refcount() {
1951    return ((RefCounted *) (internals::vmem.to_ptr(vaddr)))->rc;
1952  }
1953  void *to_ptr() {
1954    return &(((RefCounted *) (internals::vmem.to_ptr(vaddr)))->data);
1955  }
1956
1957public:
1958  ZRef() : vaddr(internals::VADDR_NULL) {
1959  }
1960  ZRef(internals::vaddr_t vaddr) : vaddr(vaddr) {
1961  }
1962  operator bool() {
1963    return vaddr != internals::VADDR_NULL;
1964  }
1965  bool is_null() {
1966    return vaddr == internals::VADDR_NULL;
1967  }
1968  ZRef(void *ptr) {
1969    vaddr = internals::allocated_ptr_to_vaddr(ptr);
1970  }
1971  T *as_ptr() const {
1972    return (T *) to_ptr();
1973  }
1974  T &as_ref() const {
1975    return *(T *) to_ptr();
1976  }
1977  T &operator*() const {
1978    return *(T *) to_ptr();
1979  }
1980  T *operator->() {
1981    return (T *) to_ptr();
1982  }
1983  ZRef<T> &operator=(ZRef<T> other) {
1984    vaddr = other.vaddr;
1985  }
1986  template <typename U>
1987  ZRef<U> cast() const {
1988    return ZRef<U>(vaddr);
1989  }
1990  void retain() {
1991    refcount().inc(vaddr);
1992  }
1993  void release() {
1994    if (refcount().dec(vaddr) == 0) {
1995      as_ref().~T();
1996      internals::vmem_free(vaddr);
1997    }
1998  }
1999  void free() {
2000    as_ptr()->~T(); // explicitly call destructor
2001    internals::vmem_free(vaddr);
2002    vaddr = internals::VADDR_NULL;
2003  }
2004  static internals::vaddr_t alloc() {
2005    return internals::vmem_alloc(sizeof(RefCounted));
2006  }
2007};
2008
2009template <typename T>
2010ZRef<T> znull() {
2011  return ZRef<T>(internals::VADDR_NULL);
2012}
2013
2014template <typename T>
2015ZRef<T> znew() {
2016  ZRef<T> result = ZRef<T>::alloc();
2017  new (result.to_ptr()) T();
2018  return result;
2019}
2020
2021template <typename T>
2022ZRef<T> znew_uninitialized() {
2023  ZRef<T> result = ZRef<T>::alloc();
2024  return result;
2025}
2026
2027template <typename T>
2028ZRef<T> znew_array(size_t n) {
2029  ZRef<T> result = ZRef<T>::alloc();
2030  T *ptr = result.as_ptr();
2031  for (size_t i = 0; i < n; i++) {
2032    new (ptr + i) T();
2033  }
2034  return result;
2035}
2036
2037template <typename T>
2038ZRef<T> znew_uninitialized_array(size_t n) {
2039  ZRef<T> result = ZRef<T>::alloc();
2040  return result;
2041}
2042
2043template <typename T, typename Arg>
2044ZRef<T> znew(Arg arg) {
2045  ZRef<T> result = ZRef<T>::alloc();
2046  new (result.to_ptr()) T(arg);
2047  return result;
2048}
2049
2050template <typename T, typename Arg1, typename Arg2>
2051ZRef<T> znew(Arg1 arg1, Arg2 arg2) {
2052  ZRef<T> result = ZRef<T>::alloc();
2053  new (result.to_ptr()) T(arg1, arg2);
2054  return result;
2055}
2056
2057template <typename T, typename Arg1, typename Arg2, typename Arg3>
2058ZRef<T> znew(Arg1 arg1, Arg2 arg2, Arg3 arg3) {
2059  ZRef<T> result = ZRef<T>::alloc();
2060  new (result.to_ptr()) T(arg1, arg2, arg3);
2061  return result;
2062}
2063
2064class VString {
2065private:
2066  VRef<char> _buffer;
2067  size_t _len;
2068
2069public:
2070  VString(const char *s) {
2071    _len = std::strlen(s);
2072    _buffer = vnew_uninitialized_array<char>(_len + 1);
2073    std::strcpy(_buffer.as_ptr(), s);
2074  }
2075  VString(const char *s, size_t len) {
2076    _len = len;
2077    _buffer = vnew_uninitialized_array<char>(len + 1);
2078    char *buffer = _buffer.as_ptr();
2079    std::memcpy(buffer, s, len);
2080    buffer[len] = '\0';
2081  }
2082  VString(size_t len) {
2083    _len = len;
2084    _buffer = vnew_uninitialized_array<char>(len + 1);
2085    _buffer[len] = '\0';
2086  }
2087  ~VString() {
2088    _buffer.free();
2089  }
2090  size_t len() const {
2091    return _len;
2092  }
2093  VRef<VString> clone() const {
2094    return vnew<VString>(_buffer.as_ptr(), _len);
2095  }
2096  const char *str() const {
2097    return _buffer.as_ptr();
2098  }
2099};
2100
2101static inline VRef<VString> vstring(const char *s) {
2102  return vnew<VString>(s);
2103}
2104
2105static inline VRef<VString> vstring(const char *s, size_t len) {
2106  return vnew<VString>(s, len);
2107}
2108
2109static inline VRef<VString> vstring(size_t len) {
2110  return vnew<VString>(len);
2111}
2112
2113
2114template <typename Spec>
2115class VMap {
2116private:
2117  typedef typename Spec::Key K;
2118  typedef typename Spec::Value V;
2119  struct Node {
2120    VRef<Node> next;
2121    size_t hash;
2122    VRef<K> key;
2123    VRef<V> value;
2124  };
2125  VRef<VRef<Node> > _buckets;
2126  VRef<internals::FastLock> _locks;
2127  size_t _nbuckets;
2128
2129  void _lock_bucket(size_t b) {
2130    _locks[b].lock();
2131  }
2132  void _unlock_bucket(size_t b) {
2133    _locks[b].unlock();
2134  }
2135
2136public:
2137  VMap(size_t size = 1024);
2138  ~VMap();
2139  bool add(VRef<K> key, VRef<V> value, VRef<K> &oldkey, VRef<V> &oldvalue,
2140      bool replace = true);
2141  bool add(VRef<K> key, VRef<V> value, bool replace = true) {
2142    VRef<K> oldkey;
2143    VRef<V> oldvalue;
2144    return add(key, value, oldkey, oldvalue, replace);
2145  }
2146  bool remove(VRef<K> key, VRef<K> &oldkey, VRef<V> &oldvalue);
2147  bool remove(VRef<K> key) {
2148    VRef<K> oldkey;
2149    VRef<V> oldvalue;
2150    return remove(key, oldkey, oldvalue);
2151  }
2152  bool find(VRef<K> key, VRef<V> &value);
2153  VRef<V> find(VRef<K> key) {
2154    VRef<V> value;
2155    if (find(key, value))
2156      return value;
2157    else
2158      return vnull<V>();
2159  }
2160};
2161
2162template <typename Spec>
2163VMap<Spec>::VMap(size_t size) {
2164  using namespace internals;
2165  _nbuckets = 8;
2166  while (_nbuckets < size)
2167    _nbuckets *= 2;
2168  _buckets = vnew_array<VRef<Node> >(_nbuckets);
2169  _locks = vnew_uninitialized_array<FastLock>(_nbuckets);
2170  for (size_t i = 0; i < _nbuckets; i++)
2171    _locks[i]
2172        = FastLock(METABLOCK_SIZE + _locks.offset() + sizeof(FastLock) * i);
2173}
2174
2175template <typename Spec>
2176VMap<Spec>::~VMap() {
2177  for (size_t b = 0; b < _nbuckets; b++) {
2178    _lock_bucket(b);
2179    VRef<Node> node = _buckets[b];
2180    while (node) {
2181      Node *node_ptr = node.as_ptr();
2182      VRef<Node> next = node_ptr->next;
2183      Spec::free_key(node_ptr->key);
2184      Spec::free_value(node_ptr->value);
2185      node.free();
2186      node = next;
2187    }
2188    _unlock_bucket(b);
2189  }
2190  _buckets.free();
2191  _locks.free();
2192}
2193
2194template <typename Spec>
2195bool VMap<Spec>::add(VRef<K> key, VRef<V> value, VRef<K> &oldkey,
2196    VRef<V> &oldvalue, bool replace) {
2197  size_t hash = Spec::hash(key.as_ptr());
2198  size_t b = hash & (_nbuckets - 1);
2199  _lock_bucket(b);
2200  VRef<Node> node = _buckets[b];
2201  VRef<Node> last = vnull<Node>();
2202  while (!node.is_null()) {
2203    Node *node_ptr = node.as_ptr();
2204    if (hash == node_ptr->hash
2205        && Spec::equal(key.as_ptr(), node_ptr->key.as_ptr())) {
2206      value = node_ptr->value;
2207      if (!last.is_null()) {
2208        // move to front
2209        last->next = node_ptr->next;
2210        node_ptr->next = _buckets[b];
2211        _buckets[b] = node;
2212      }
2213      oldkey = node_ptr->key;
2214      oldvalue = node_ptr->value;
2215      if (replace) {
2216        node_ptr->key = key;
2217        node_ptr->value = value;
2218      }
2219      _unlock_bucket(b);
2220      return false;
2221    }
2222    last = node;
2223    node = node->next;
2224  }
2225  node = vnew<Node>();
2226  Node *node_ptr = node.as_ptr();
2227  node_ptr->hash = hash;
2228  node_ptr->key = key;
2229  node_ptr->value = value;
2230  node_ptr->next = _buckets[b];
2231  _buckets[b] = node;
2232  oldkey = key;
2233  oldvalue = value;
2234  _unlock_bucket(b);
2235  return true;
2236}
2237
2238template <typename Spec>
2239bool VMap<Spec>::remove(VRef<K> key, VRef<K> &oldkey, VRef<V> &oldvalue) {
2240  size_t hash = Spec::hash(key.as_ptr());
2241  size_t b = hash & (_nbuckets - 1);
2242  _lock_bucket(b);
2243  VRef<Node> node = _buckets[b];
2244  VRef<Node> last = vnull<Node>();
2245  while (!node.is_null()) {
2246    Node *node_ptr = node.as_ptr();
2247    if (hash == node_ptr->hash
2248        && Spec::equal(key.as_ptr(), node_ptr->key.as_ptr())) {
2249      oldkey = node_ptr->key;
2250      oldvalue = node_ptr->value;
2251      // remove from list
2252      if (last.is_null()) {
2253        _buckets[b] = node_ptr->next;
2254      } else {
2255        last->next = node_ptr->next;
2256      }
2257      _unlock_bucket(b);
2258      return true;
2259    }
2260    last = node;
2261    node = node->next;
2262  }
2263  _unlock_bucket(b);
2264  return false;
2265}
2266
2267template <typename Spec>
2268bool VMap<Spec>::find(VRef<K> key, VRef<V> &value) {
2269  size_t hash = Spec::hash(key.as_ptr());
2270  size_t b = hash & (_nbuckets - 1);
2271  _lock_bucket(b);
2272  VRef<Node> node = _buckets[b];
2273  VRef<Node> last = vnull<Node>();
2274  while (!node.is_null()) {
2275    Node *node_ptr = node.as_ptr();
2276    if (hash == node_ptr->hash
2277        && Spec::equal(key.as_ptr(), node_ptr->key.as_ptr())) {
2278      value = node_ptr->value;
2279      // move to front
2280      if (!last.is_null()) {
2281        last->next = node_ptr->next;
2282        node_ptr->next = _buckets[b];
2283      }
2284      _buckets[b] = node;
2285      _unlock_bucket(b);
2286      return true;
2287    }
2288    last = node;
2289    node = node->next;
2290  }
2291  _unlock_bucket(b);
2292  return false;
2293}
2294
2295struct DictSpec {
2296  typedef VString Key;
2297  typedef VString Value;
2298  static size_t hash(const VString *s) {
2299    // DJB hash
2300    size_t len = s->len();
2301    const char *str = s->str();
2302    size_t hash = 5381;
2303    for (size_t i = 0; i < len; i++) {
2304      hash = 33 * hash + str[i];
2305    }
2306    return hash;
2307  }
2308  static bool equal(const VString *s1, const VString *s2) {
2309    if (s1->len() != s2->len())
2310      return false;
2311    size_t len = s1->len();
2312    const char *str1 = s1->str(), *str2 = s2->str();
2313    for (size_t i = 0; i < len; i++) {
2314      if (str1[i] != str2[i])
2315        return false;
2316    }
2317    return true;
2318  }
2319  // By default, we do not make assumptions about ownership. It is
2320  // up to the caller to free keys and values if needed or to
2321  // define appropriate `free_key()` and `free_value()` functions
2322  // that work. Note in particular that keys and values may occur
2323  // more than once in a map and if that happens, they must not
2324  // be freed multiple times.
2325  static void free_key(VRef<Key> key) {
2326    // do nothing
2327  }
2328  static void free_value(VRef<Value> value) {
2329    // do nothing
2330  }
2331};
2332
2333typedef VMap<DictSpec> VDict;
2334
2335pid_t fork_process();
2336
2337#ifdef HAVE_CPP_THREADS
2338typedef internals::FastLock FastLock;
2339#else
2340typedef internals::Mutex FastLock;
2341#endif
2342
2343typedef internals::Mutex Mutex;
2344
2345class Semaphore {
2346private:
2347  int _owner;
2348  int _waiting[internals::MAX_PROCESS + 1];
2349  internals::ipc_signal_t _signals[internals::MAX_PROCESS + 1];
2350  int _head, _tail;
2351  void next(int &index) {
2352    if (index == internals::MAX_PROCESS)
2353      index = 0;
2354    else
2355      index++;
2356  }
2357  size_t _value;
2358  FastLock _lock;
2359  bool _idle() {
2360    return _head == _tail;
2361  }
2362  template <typename T>
2363  friend class SyncVar;
2364
2365public:
2366  Semaphore(size_t value = 0) :
2367      _owner(0), _head(0), _tail(0), _value(value), _lock() {
2368  }
2369  size_t value() {
2370    return _value;
2371  }
2372  void post();
2373  bool try_wait();
2374  void wait();
2375  bool start_wait(internals::ipc_signal_t sig = 0);
2376  bool stop_wait();
2377};
2378
2379template <typename T>
2380class Queue {
2381private:
2382  struct Node {
2383    VRef<Node> next;
2384    T data;
2385  };
2386  Semaphore _incoming;
2387  Semaphore _outgoing;
2388  bool _bounded;
2389  FastLock _lock;
2390  VRef<Node> _head, _tail;
2391  VRef<Node> pop() {
2392    VRef<Node> result = _head;
2393    if (_head->next.is_null()) {
2394      _head = _tail = vnull<Node>();
2395    } else {
2396      _head = _head->next;
2397    }
2398    return result;
2399  }
2400  void push(VRef<Node> node) {
2401    node->next = vnull<Node>();
2402    if (_tail.is_null()) {
2403      _head = _tail = node;
2404    } else {
2405      _tail->next = node;
2406      _tail = node;
2407    }
2408  }
2409  template <typename U>
2410  friend class EnqueueEvent;
2411  template <typename U>
2412  friend class DequeueEvent;
2413
2414  void enqueue_nowait(T item) {
2415    _lock.lock();
2416    VRef<Node> node = vnew<Node>();
2417    node->data = item;
2418    push(node);
2419    _lock.unlock();
2420    _incoming.post();
2421  }
2422  T dequeue_nowait() {
2423    _lock.lock();
2424    VRef<Node> node = pop();
2425    T result;
2426    result = node->data;
2427    node.free();
2428    _lock.unlock();
2429    if (_bounded)
2430      _outgoing.post();
2431    return result;
2432  }
2433
2434public:
2435  Queue(size_t bound = 0) :
2436      _incoming(0),
2437      _outgoing(bound),
2438      _bounded(bound != 0),
2439      _head(),
2440      _tail(),
2441      _lock() {
2442  }
2443  void enqueue(T item) {
2444    if (_bounded)
2445      _outgoing.wait();
2446    enqueue_nowait(item);
2447  }
2448  bool try_enqueue(T item) {
2449    if (_bounded && _outgoing.try_wait()) {
2450      enqueue_nowait(item);
2451      return true;
2452    } else {
2453      return false;
2454    }
2455  }
2456  T dequeue() {
2457    _incoming.wait();
2458    return dequeue_nowait();
2459  }
2460  Result<T> try_dequeue() {
2461    if (_incoming.try_wait())
2462      return Result<T>(dequeue_nowait());
2463    else
2464      return Result<T>();
2465  }
2466};
2467
2468template <typename T>
2469class SyncVar {
2470private:
2471  FastLock _lock;
2472  VRef<Semaphore> _sem;
2473  bool _set;
2474  T _value;
2475  template <typename U>
2476  friend class SyncReadEvent;
2477  bool start_wait(internals::ipc_signal_t sig);
2478  void stop_wait();
2479public:
2480  SyncVar() : _set(false) { }
2481  T read();
2482  Result<T> try_read();
2483  bool write(T value);
2484  bool test() {
2485    return _set;
2486  }
2487};
2488
2489template <typename T>
2490bool SyncVar<T>::start_wait(internals::ipc_signal_t sig) {
2491  _lock.lock();
2492  if (_set) {
2493    internals::send_signal(internals::vmem.current_process, sig);
2494    _lock.unlock();
2495    return true;
2496  }
2497  if (_sem.is_null()) {
2498    _sem = vnew<Semaphore>();
2499  }
2500  bool result = _sem->start_wait(sig);
2501  _lock.unlock();
2502  return result;
2503}
2504
2505template <typename T>
2506void SyncVar<T>::stop_wait() {
2507  _lock.lock();
2508  if (!_sem.is_null()) {
2509    _sem->stop_wait();
2510    if (!_sem->_idle())
2511      _sem->post();
2512  }
2513  _lock.unlock();
2514}
2515
2516template <typename T>
2517T SyncVar<T>::read() {
2518  _lock.lock();
2519  if (_set) {
2520    _lock.unlock();
2521    return _value;
2522  }
2523  if (_sem.is_null()) {
2524    _sem = vnew<Semaphore>();
2525  }
2526  // We can't wait inside the lock without deadlocking; but waiting outside
2527  // could cause a race condition with _sem being freed due to being idle.
2528  // Thus, we use start_wait() to insert ourselves into the queue, then
2529  // use wait_signal() outside the lock to complete waiting.
2530  //
2531  // Note: start_wait() will not send a signal to self, as _set is
2532  // false and therefore _sem->value() must be zero.
2533  _sem->start_wait(0);
2534  _lock.unlock();
2535  internals::wait_signal();
2536  _lock.lock();
2537  if (_sem->_idle())
2538    _sem->post();
2539  else {
2540    _sem.free();
2541    _sem = vnull<Semaphore>();
2542  }
2543  _lock.unlock();
2544  return _value;
2545}
2546
2547template <typename T>
2548Result<T> SyncVar<T>::try_read() {
2549  _lock.lock();
2550  Result<T> result = _set ? Result<T>(_value) : Result<T>();
2551  _lock.unlock();
2552  return result;
2553}
2554
2555template <typename T>
2556bool SyncVar<T>::write(T value) {
2557  _lock.lock();
2558  if (_set) {
2559    _lock.unlock();
2560    return false;
2561  }
2562  _set = true;
2563  _value = value;
2564  if (!_sem->_idle())
2565    _sem->post();
2566  _lock.unlock();
2567  return true;
2568}
2569
2570class Event {
2571private:
2572  Event *_next;
2573  friend class EventSet;
2574public:
2575  virtual bool start_listen(internals::ipc_signal_t sig) = 0;
2576  virtual void stop_listen() = 0;
2577};
2578
2579class EventSet {
2580private:
2581  Event *_head, *_tail;
2582
2583public:
2584  EventSet() : _head(NULL), _tail(NULL) {
2585  }
2586  void add(Event *event);
2587  void add(Event &event) {
2588    add(&event);
2589  }
2590  EventSet &operator<<(Event *event) {
2591    add(event);
2592    return *this;
2593  }
2594  EventSet &operator<<(Event &event) {
2595    add(event);
2596    return *this;
2597  }
2598  int wait();
2599};
2600
2601class WaitSemaphoreEvent : public Event {
2602private:
2603  VRef<Semaphore> _sem;
2604
2605public:
2606  WaitSemaphoreEvent(VRef<Semaphore> sem) : _sem(sem) {
2607  }
2608  virtual bool start_listen(internals::ipc_signal_t sig) {
2609    return _sem->start_wait(sig);
2610  }
2611  virtual void stop_listen() {
2612    _sem->stop_wait();
2613  }
2614  void complete() {
2615  }
2616};
2617
2618template <typename T>
2619class EnqueueEvent : public Event {
2620private:
2621  VRef<Queue<T> > _queue;
2622
2623public:
2624  EnqueueEvent(VRef<Queue<T> > queue) : _queue(queue) {
2625  }
2626  virtual bool start_listen(internals::ipc_signal_t sig) {
2627    return _queue->_outgoing.start_wait(sig);
2628  }
2629  virtual void stop_listen() {
2630    _queue->_outgoing.stop_wait();
2631  }
2632  void complete(T item) {
2633    _queue->enqueue_nowait(item);
2634  }
2635};
2636
2637template <typename T>
2638class DequeueEvent : public Event {
2639private:
2640  VRef<Queue<T> > _queue;
2641
2642public:
2643  DequeueEvent(VRef<Queue<T> > queue) : _queue(queue) {
2644  }
2645  virtual bool start_listen(internals::ipc_signal_t sig) {
2646    return _queue->_incoming.start_wait(sig);
2647  }
2648  virtual void stop_listen() {
2649    _queue->_incoming.stop_wait();
2650  }
2651  T complete() {
2652    return _queue->dequeue_nowait();
2653  }
2654};
2655
2656template <typename T>
2657class SyncReadEvent : public Event {
2658private:
2659  VRef<SyncVar<T> > _syncvar;
2660
2661public:
2662  SyncReadEvent(VRef<SyncVar<T> > syncvar) : _syncvar(syncvar) {
2663  }
2664  virtual bool start_listen(internals::ipc_signal_t sig) {
2665    return _syncvar->start_wait(sig);
2666  }
2667  virtual void stop_listen() {
2668    _syncvar->stop_wait();
2669  }
2670  T complete() {
2671    return _syncvar->read();
2672  }
2673};
2674
2675}; // namespace vspace
2676#endif
2677#endif
2678#endif
Note: See TracBrowser for help on using the repository browser.