My Project
vspace.h
Go to the documentation of this file.
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 
42 namespace vspace {
43 
44 enum ErrCode {
45  ErrNone,
46  ErrGeneral,
47  ErrFile,
48  ErrMMap,
49  ErrOS,
50 };
51 
52 template <typename T>
53 struct Result {
54  bool ok;
55  T result;
56  Result(T result) : ok(true), result(result) {
57  }
59  }
60 private:
61  T& default_value() {
62  static T result;
63  return result;
64  }
65 };
66 
67 struct 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 
79 namespace internals {
80 
81 typedef size_t segaddr_t;
82 
83 typedef size_t vaddr_t;
84 
85 const segaddr_t SEGADDR_NULL = ~(segaddr_t) 0;
86 const vaddr_t VADDR_NULL = ~(segaddr_t) 0;
87 
88 static const int MAX_PROCESS = 64;
89 static const size_t METABLOCK_SIZE = 128 * 1024; // 128 KB
90 static const int LOG2_SEGMENT_SIZE = 28; // 256 MB
91 static const int LOG2_MAX_SEGMENTS = 10; // 256 GB
92 static const size_t MAX_SEGMENTS = 1 << LOG2_MAX_SEGMENTS;
93 static const size_t SEGMENT_SIZE = 1 << LOG2_SEGMENT_SIZE;
94 static 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.
100 class FastLock {
101 private:
102 #ifdef HAVE_CPP_THREADS
103  std::atomic_flag _lock;
104  short _owner, _head, _tail;
105 #else
107 #endif
108 public:
109 #ifdef HAVE_CPP_THREADS
110  FastLock(vaddr_t offset = 0) : _owner(-1), _head(-1), _tail(-1) {
111  _lock.clear();
112  }
113 #else
115  }
116 #endif
117 #ifdef HAVE_CPP_THREADS
118  // We only need to define the copy constructor 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 
139 extern size_t config[4];
140 
141 void init_flock_struct(
142  struct flock &lock_info, size_t offset, size_t len, bool lock);
143 void lock_file(int fd, size_t offset, size_t len = 1);
144 void unlock_file(int fd, size_t offset, size_t len = 1);
145 
146 void lock_metapage();
147 void unlock_metapage();
148 void init_metapage(bool create);
149 
150 typedef int ipc_signal_t;
151 
152 bool send_signal(int processno, ipc_signal_t sig = 0, bool lock = true);
153 ipc_signal_t check_signal(bool resume = false, bool lock = true);
154 void accept_signals();
155 ipc_signal_t wait_signal(bool lock = true);
156 void drop_pending_signals();
157 
158 struct Block;
159 struct MetaPage;
160 struct ProcessChannel;
161 
162 enum SignalState {
163  Waiting = 0,
164  Pending = 1,
165  Accepted = 2,
166 };
167 
168 struct ProcessInfo {
169  pid_t pid;
170  SignalState sigstate; // are there pending signals?
172 #ifdef HAVE_CPP_THREADS
173  int next; // next in queue waiting for a lock.
174 #endif
175 };
176 
177 struct MetaPage {
178  size_t config_header[4];
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 
194 struct ProcessChannel {
195  int fd_read, fd_write;
196 };
197 
198 struct 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 
235 struct 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 
253 struct 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;
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 
302 static VMem &vmem = VMem::vmem_global;
303 
304 inline Block *block_ptr(vaddr_t vaddr) {
305  return vmem.block_ptr(vaddr);
306 }
307 
308 #ifdef HAVE_CPP_THREADS
309 struct 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
323 struct 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 
348 static 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 
357 static inline segaddr_t find_buddy(segaddr_t addr, int level) {
358  return addr ^ (1 << level);
359 }
360 
361 void vmem_free(vaddr_t vaddr);
362 vaddr_t vmem_alloc(size_t size);
363 
364 static 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 
373 class Mutex {
374 private:
375  int _owner;
376  int _locklevel;
377  vaddr_t _lock;
378 
379 public:
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 {
391  _locklevel = 1;
392  }
393  }
394  void unlock() {
395  if (--_locklevel == 0) {
397  _owner = -1;
399  }
400  }
401 };
402 
403 }; // namespace internals
404 
405 static inline Status vmem_init() {
406  return internals::vmem.init();
407 }
408 
409 static inline void vmem_deinit() {
411 }
412 
413 template <typename T>
414 struct VRef {
415 private:
418  }
419 public:
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) {
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
476  }
477 };
478 
479 template <>
480 struct VRef<void> {
481 private:
484  }
485 
486 public:
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) {
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() {
530  }
531 };
532 
533 template <typename T>
534 VRef<T> vnull() {
536 }
537 
538 template <typename T>
539 VRef<T> vnew() {
540  VRef<T> result = VRef<T>::alloc();
541  new (result.to_ptr()) T();
542  return result;
543 }
544 
545 template <typename T>
546 VRef<T> vnew_uninitialized() {
547  VRef<T> result = VRef<T>::alloc();
548  return result;
549 }
550 
551 template <typename T>
552 VRef<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 
561 template <typename T>
562 VRef<T> vnew_uninitialized_array(size_t n) {
563  VRef<T> result = VRef<T>::alloc(n);
564  return result;
565 }
566 
567 template <typename T, typename Arg>
568 VRef<T> vnew(Arg arg) {
569  VRef<T> result = VRef<T>::alloc();
570  new (result.to_ptr()) T(arg);
571  return result;
572 }
573 
574 template <typename T, typename Arg1, typename Arg2>
575 VRef<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 
581 template <typename T, typename Arg1, typename Arg2, typename Arg3>
582 VRef<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 
588 template <typename T, typename Arg1, typename Arg2, typename Arg3,
589  typename Arg4>
590 VRef<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 
596 template <typename T, typename Arg1, typename Arg2, typename Arg3,
597  typename Arg4, typename Arg5>
598 VRef<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 
604 template <typename T>
605 struct ZRef {
606 private:
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  };
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 
624 public:
625  ZRef() : vaddr(internals::VADDR_NULL) {
626  }
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) {
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();
664  }
665  }
666  void free() {
667  as_ptr()->~T(); // explicitly call destructor
670  }
671  static internals::vaddr_t alloc() {
672  return internals::vmem_alloc(sizeof(RefCounted));
673  }
674 };
675 
676 template <typename T>
677 ZRef<T> znull() {
678  return ZRef<T>(internals::VADDR_NULL);
679 }
680 
681 template <typename T>
682 ZRef<T> znew() {
683  ZRef<T> result = ZRef<T>::alloc();
684  new (result.to_ptr()) T();
685  return result;
686 }
687 
688 template <typename T>
689 ZRef<T> znew_uninitialized() {
690  ZRef<T> result = ZRef<T>::alloc();
691  return result;
692 }
693 
694 template <typename T>
695 ZRef<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 
704 template <typename T>
705 ZRef<T> znew_uninitialized_array(size_t n) {
706  ZRef<T> result = ZRef<T>::alloc();
707  return result;
708 }
709 
710 template <typename T, typename Arg>
711 ZRef<T> znew(Arg arg) {
712  ZRef<T> result = ZRef<T>::alloc();
713  new (result.to_ptr()) T(arg);
714  return result;
715 }
716 
717 template <typename T, typename Arg1, typename Arg2>
718 ZRef<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 
724 template <typename T, typename Arg1, typename Arg2, typename Arg3>
725 ZRef<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 
731 class VString {
732 private:
733  VRef<char> _buffer;
734  size_t _len;
735 
736 public:
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 
768 static inline VRef<VString> vstring(const char *s) {
769  return vnew<VString>(s);
770 }
771 
772 static inline VRef<VString> vstring(const char *s, size_t len) {
773  return vnew<VString>(s, len);
774 }
775 
776 static inline VRef<VString> vstring(size_t len) {
777  return vnew<VString>(len);
778 }
779 
780 
781 template <typename Spec>
782 class VMap {
783 private:
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 
803 public:
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 
829 template <typename Spec>
830 VMap<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 
842 template <typename Spec>
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 
861 template <typename Spec>
862 bool 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 
905 template <typename Spec>
906 bool 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 
934 template <typename Spec>
935 bool 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 
962 struct 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 
1000 typedef VMap<DictSpec> VDict;
1001 
1002 pid_t fork_process();
1003 
1004 #ifdef HAVE_CPP_THREADS
1006 #else
1007 typedef internals::Mutex FastLock;
1008 #endif
1009 
1010 typedef internals::Mutex Mutex;
1011 
1012 class Semaphore {
1013 private:
1014  int _owner;
1017  int _head, _tail;
1018  void next(int &index) {
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 
1032 public:
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 
1046 template <typename T>
1047 class Queue {
1048 private:
1049  struct Node {
1050  VRef<Node> next;
1051  T data;
1052  };
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 
1101 public:
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 
1135 template <typename T>
1136 class SyncVar {
1137 private:
1138  FastLock _lock;
1139  VRef<Semaphore> _sem;
1140  bool _set;
1141  T _value;
1142  template <typename U>
1143  friend class SyncReadEvent;
1145  void stop_wait();
1146 public:
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 
1156 template <typename T>
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 
1172 template <typename T>
1173 void 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 
1183 template <typename T>
1184 T 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();
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 
1214 template <typename T>
1215 Result<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 
1222 template <typename T>
1223 bool 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 
1237 class Event {
1238 private:
1239  Event *_next;
1240  friend class EventSet;
1241 public:
1242  virtual bool start_listen(internals::ipc_signal_t sig) = 0;
1243  virtual void stop_listen() = 0;
1244 };
1245 
1246 class EventSet {
1247 private:
1248  Event *_head, *_tail;
1249 
1250 public:
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 
1268 class WaitSemaphoreEvent : public Event {
1269 private:
1270  VRef<Semaphore> _sem;
1271 
1272 public:
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 
1285 template <typename T>
1286 class EnqueueEvent : public Event {
1287 private:
1288  VRef<Queue<T> > _queue;
1289 
1290 public:
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 
1304 template <typename T>
1305 class DequeueEvent : public Event {
1306 private:
1307  VRef<Queue<T> > _queue;
1308 
1309 public:
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 
1323 template <typename T>
1324 class SyncReadEvent : public Event {
1325 private:
1326  VRef<SyncVar<T> > _syncvar;
1327 
1328 public:
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 
1373 namespace vspace {
1374 
1375 enum ErrCode {
1381 };
1382 
1383 template <typename T>
1384 struct Result {
1385  bool ok;
1388  }
1390  }
1391 private:
1393  static T result;
1394  return result;
1395  }
1396 };
1397 
1398 struct Status {
1400  bool ok() {
1401  return err == ErrNone;
1402  }
1403  operator bool() {
1404  return err == ErrNone;
1405  }
1407  }
1408 };
1409 
1410 namespace internals {
1411 
1412 typedef size_t segaddr_t;
1413 
1414 typedef size_t vaddr_t;
1415 
1418 
1419 static const int MAX_PROCESS = 64;
1420 static const size_t METABLOCK_SIZE = 128 * 1024; // 128 KB
1421 static const int LOG2_SEGMENT_SIZE = 28; // 256 MB
1422 static const int LOG2_MAX_SEGMENTS = 10; // 256 GB
1423 static const size_t MAX_SEGMENTS = 1 << LOG2_MAX_SEGMENTS;
1424 static const size_t SEGMENT_SIZE = 1 << LOG2_SEGMENT_SIZE;
1425 static 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.
1431 class FastLock {
1432 private:
1433 #ifdef HAVE_CPP_THREADS
1434  std::atomic_flag _lock;
1435  short _owner, _head, _tail;
1436 #else
1438 #endif
1439 public:
1440 #ifdef HAVE_CPP_THREADS
1441  FastLock(vaddr_t offset = 0) : _owner(-1), _head(-1), _tail(-1) {
1442  _lock.clear();
1443  }
1444 #else
1446  }
1447 #endif
1448 #ifdef HAVE_CPP_THREADS
1449  // We only need to define the copy constructor 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 
1470 extern size_t config[4];
1471 
1472 void init_flock_struct(
1473  struct flock &lock_info, size_t offset, size_t len, bool lock);
1474 void lock_file(int fd, size_t offset, size_t len = 1);
1475 void unlock_file(int fd, size_t offset, size_t len = 1);
1476 
1477 void lock_metapage();
1478 void unlock_metapage();
1479 void init_metapage(bool create);
1480 
1481 typedef int ipc_signal_t;
1482 
1483 bool send_signal(int processno, ipc_signal_t sig = 0, bool lock = true);
1484 ipc_signal_t check_signal(bool resume = false, bool lock = true);
1485 void accept_signals();
1486 ipc_signal_t wait_signal(bool lock = true);
1488 
1489 struct Block;
1490 struct MetaPage;
1491 struct ProcessChannel;
1492 
1494  Waiting = 0,
1495  Pending = 1,
1497 };
1498 
1499 struct ProcessInfo {
1500  pid_t pid;
1501  SignalState sigstate; // are there pending signals?
1503 #ifdef HAVE_CPP_THREADS
1504  int next; // next in queue waiting for a lock.
1505 #endif
1506 };
1507 
1508 struct MetaPage {
1509  size_t config_header[4];
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 
1527 };
1528 
1529 struct 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.
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 
1566 struct 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 
1587 struct VMem {
1590  int fd;
1591  std::FILE *file_handle;
1592  int current_process; // index into process table
1593  vaddr_t *freelist; // reference to metapage information
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  }
1606  if (vaddr == VADDR_NULL)
1607  return SEGADDR_NULL;
1608  return vaddr & SEGMENT_MASK;
1609  }
1611  if (vaddr == VADDR_NULL)
1612  return NULL;
1613  return (Block *) (segment(vaddr).base + segaddr(vaddr));
1614  }
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;
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 
1636 
1637 inline Block *block_ptr(vaddr_t vaddr) {
1638  return vmem.block_ptr(vaddr);
1639 }
1640 
1641 #ifdef HAVE_CPP_THREADS
1642 struct 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
1656 struct 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 
1681 static 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 
1690 static inline segaddr_t find_buddy(segaddr_t addr, int level) {
1691  return addr ^ (1 << level);
1692 }
1693 
1694 void vmem_free(vaddr_t vaddr);
1695 vaddr_t vmem_alloc(size_t size);
1696 
1697 static 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 
1706 class Mutex {
1707 private:
1708  int _owner;
1711 
1712 public:
1714  }
1716  vmem_free(_lock);
1717  }
1718  void lock() {
1719  if (_owner == vmem.current_process) {
1720  _locklevel++;
1721  } else {
1724  _locklevel = 1;
1725  }
1726  }
1727  void unlock() {
1728  if (--_locklevel == 0) {
1730  _owner = -1;
1732  }
1733  }
1734 };
1735 
1736 }; // namespace internals
1737 
1738 static inline Status vmem_init() {
1739  return internals::vmem.init();
1740 }
1741 
1742 static inline void vmem_deinit() {
1744 }
1745 
1746 template <typename T>
1747 struct VRef {
1748 private:
1751  }
1752 public:
1753  VRef() : vaddr(internals::VADDR_NULL) {
1754  }
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) {
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  }
1789  return (T *) to_ptr();
1790  }
1792  vaddr = other.vaddr;
1793  return *this;
1794  }
1795  T &operator[](size_t index) {
1796  return as_ptr()[index];
1797  }
1798  template <typename U>
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
1809  }
1810 };
1811 
1812 template <>
1813 struct VRef<void> {
1814 private:
1817  }
1818 
1819 public:
1820  VRef() : vaddr(internals::VADDR_NULL) {
1821  }
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) {
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  }
1850  vaddr = other.vaddr;
1851  return *this;
1852  }
1853  template <typename U>
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() {
1863  }
1864 };
1865 
1866 template <typename T>
1869 }
1870 
1871 template <typename T>
1874  new (result.to_ptr()) T();
1875  return result;
1876 }
1877 
1878 template <typename T>
1881  return result;
1882 }
1883 
1884 template <typename T>
1885 VRef<T> vnew_array(size_t 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 
1894 template <typename T>
1897  return result;
1898 }
1899 
1900 template <typename T, typename Arg>
1901 VRef<T> vnew(Arg arg) {
1903  new (result.to_ptr()) T(arg);
1904  return result;
1905 }
1906 
1907 template <typename T, typename Arg1, typename Arg2>
1908 VRef<T> vnew(Arg1 arg1, Arg2 arg2) {
1910  new (result.to_ptr()) T(arg1, arg2);
1911  return result;
1912 }
1913 
1914 template <typename T, typename Arg1, typename Arg2, typename Arg3>
1915 VRef<T> vnew(Arg1 arg1, Arg2 arg2, Arg3 arg3) {
1917  new (result.to_ptr()) T(arg1, arg2, arg3);
1918  return result;
1919 }
1920 
1921 template <typename T, typename Arg1, typename Arg2, typename Arg3,
1922  typename Arg4>
1923 VRef<T> vnew(Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4) {
1925  new (result.to_ptr()) T(arg1, arg2, arg3, arg4);
1926  return result;
1927 }
1928 
1929 template <typename T, typename Arg1, typename Arg2, typename Arg3,
1930  typename Arg4, typename Arg5>
1931 VRef<T> vnew(Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5 arg5) {
1933  new (result.to_ptr()) T(arg1, arg2, arg3, arg4, arg5);
1934  return result;
1935 }
1936 
1937 template <typename T>
1938 struct ZRef {
1939 private:
1940  struct RefCounted {
1942 #if __cplusplus >= 201100
1943  alignas(T)
1944 #endif
1945  char data[sizeof(T)];
1946  RefCounted() : rc(1) {
1947  }
1948  };
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 
1957 public:
1958  ZRef() : vaddr(internals::VADDR_NULL) {
1959  }
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) {
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  }
1981  return (T *) to_ptr();
1982  }
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();
1997  }
1998  }
1999  void free() {
2000  as_ptr()->~T(); // explicitly call destructor
2003  }
2005  return internals::vmem_alloc(sizeof(RefCounted));
2006  }
2007 };
2008 
2009 template <typename T>
2012 }
2013 
2014 template <typename T>
2017  new (result.to_ptr()) T();
2018  return result;
2019 }
2020 
2021 template <typename T>
2024  return result;
2025 }
2026 
2027 template <typename T>
2028 ZRef<T> znew_array(size_t n) {
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 
2037 template <typename T>
2040  return result;
2041 }
2042 
2043 template <typename T, typename Arg>
2044 ZRef<T> znew(Arg arg) {
2046  new (result.to_ptr()) T(arg);
2047  return result;
2048 }
2049 
2050 template <typename T, typename Arg1, typename Arg2>
2051 ZRef<T> znew(Arg1 arg1, Arg2 arg2) {
2053  new (result.to_ptr()) T(arg1, arg2);
2054  return result;
2055 }
2056 
2057 template <typename T, typename Arg1, typename Arg2, typename Arg3>
2058 ZRef<T> znew(Arg1 arg1, Arg2 arg2, Arg3 arg3) {
2060  new (result.to_ptr()) T(arg1, arg2, arg3);
2061  return result;
2062 }
2063 
2064 class VString {
2065 private:
2067  size_t _len;
2068 
2069 public:
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  }
2088  _buffer.free();
2089  }
2090  size_t len() const {
2091  return _len;
2092  }
2094  return vnew<VString>(_buffer.as_ptr(), _len);
2095  }
2096  const char *str() const {
2097  return _buffer.as_ptr();
2098  }
2099 };
2100 
2101 static inline VRef<VString> vstring(const char *s) {
2102  return vnew<VString>(s);
2103 }
2104 
2105 static inline VRef<VString> vstring(const char *s, size_t len) {
2106  return vnew<VString>(s, len);
2107 }
2108 
2109 static inline VRef<VString> vstring(size_t len) {
2110  return vnew<VString>(len);
2111 }
2112 
2113 
2114 template <typename Spec>
2115 class VMap {
2116 private:
2117  typedef typename Spec::Key K;
2118  typedef typename Spec::Value V;
2119  struct Node {
2121  size_t hash;
2124  };
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 
2136 public:
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);
2154  VRef<V> value;
2155  if (find(key, value))
2156  return value;
2157  else
2158  return vnull<V>();
2159  }
2160 };
2161 
2162 template <typename Spec>
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 
2175 template <typename Spec>
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 
2194 template <typename Spec>
2195 bool 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 
2238 template <typename Spec>
2239 bool 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 
2267 template <typename Spec>
2268 bool 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 
2295 struct 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 
2334 
2335 pid_t fork_process();
2336 
2337 #ifdef HAVE_CPP_THREADS
2339 #else
2341 #endif
2342 
2344 
2345 class Semaphore {
2346 private:
2347  int _owner;
2350  int _head, _tail;
2351  void next(int &index) {
2353  index = 0;
2354  else
2355  index++;
2356  }
2357  size_t _value;
2359  bool _idle() {
2360  return _head == _tail;
2361  }
2362  template <typename T>
2363  friend class SyncVar;
2364 
2365 public:
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 
2379 template <typename T>
2380 class Queue {
2381 private:
2382  struct Node {
2385  };
2388  bool _bounded;
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  }
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 
2434 public:
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  }
2457  _incoming.wait();
2458  return dequeue_nowait();
2459  }
2461  if (_incoming.try_wait())
2462  return Result<T>(dequeue_nowait());
2463  else
2464  return Result<T>();
2465  }
2466 };
2467 
2468 template <typename T>
2469 class SyncVar {
2470 private:
2473  bool _set;
2475  template <typename U>
2476  friend class SyncReadEvent;
2478  void stop_wait();
2479 public:
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 
2489 template <typename T>
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 
2505 template <typename T>
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 
2516 template <typename T>
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();
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 
2547 template <typename T>
2549  _lock.lock();
2550  Result<T> result = _set ? Result<T>(_value) : Result<T>();
2551  _lock.unlock();
2552  return result;
2553 }
2554 
2555 template <typename T>
2556 bool 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 
2570 class Event {
2571 private:
2573  friend class EventSet;
2574 public:
2575  virtual bool start_listen(internals::ipc_signal_t sig) = 0;
2576  virtual void stop_listen() = 0;
2577 };
2578 
2579 class EventSet {
2580 private:
2582 
2583 public:
2585  }
2586  void add(Event *event);
2587  void add(Event &event) {
2588  add(&event);
2589  }
2591  add(event);
2592  return *this;
2593  }
2595  add(event);
2596  return *this;
2597  }
2598  int wait();
2599 };
2600 
2601 class WaitSemaphoreEvent : public Event {
2602 private:
2604 
2605 public:
2607  }
2609  return _sem->start_wait(sig);
2610  }
2611  virtual void stop_listen() {
2612  _sem->stop_wait();
2613  }
2614  void complete() {
2615  }
2616 };
2617 
2618 template <typename T>
2619 class EnqueueEvent : public Event {
2620 private:
2622 
2623 public:
2624  EnqueueEvent(VRef<Queue<T> > queue) : _queue(queue) {
2625  }
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 
2637 template <typename T>
2638 class DequeueEvent : public Event {
2639 private:
2641 
2642 public:
2643  DequeueEvent(VRef<Queue<T> > queue) : _queue(queue) {
2644  }
2646  return _queue->_incoming.start_wait(sig);
2647  }
2648  virtual void stop_listen() {
2649  _queue->_incoming.stop_wait();
2650  }
2652  return _queue->dequeue_nowait();
2653  }
2654 };
2655 
2656 template <typename T>
2657 class SyncReadEvent : public Event {
2658 private:
2660 
2661 public:
2662  SyncReadEvent(VRef<SyncVar<T> > syncvar) : _syncvar(syncvar) {
2663  }
2665  return _syncvar->start_wait(sig);
2666  }
2667  virtual void stop_listen() {
2668  _syncvar->stop_wait();
2669  }
2671  return _syncvar->read();
2672  }
2673 };
2674 
2675 }; // namespace vspace
2676 #endif
2677 #endif
2678 #endif
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
int level(const CanonicalForm &f)
int i
Definition: cfEzgcd.cc:132
return false
Definition: cfModGcd.cc:84
bool equal
Definition: cfModGcd.cc:4126
CanonicalForm b
Definition: cfModGcd.cc:4103
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
DequeueEvent(VRef< Queue< T > > queue)
Definition: vspace.h:2643
VRef< Queue< T > > _queue
Definition: vspace.h:2640
virtual void stop_listen()
Definition: vspace.h:2648
virtual bool start_listen(internals::ipc_signal_t sig)
Definition: vspace.h:2645
virtual void stop_listen()
Definition: vspace.h:2629
void complete(T item)
Definition: vspace.h:2632
VRef< Queue< T > > _queue
Definition: vspace.h:2621
virtual bool start_listen(internals::ipc_signal_t sig)
Definition: vspace.h:2626
EnqueueEvent(VRef< Queue< T > > queue)
Definition: vspace.h:2624
void add(Event *event)
Definition: vspace.cc:1103
EventSet & operator<<(Event &event)
Definition: vspace.h:2594
void add(Event &event)
Definition: vspace.h:2587
EventSet & operator<<(Event *event)
Definition: vspace.h:2590
Event * _head
Definition: vspace.h:2581
Event * _tail
Definition: vspace.h:2581
friend class EventSet
Definition: vspace.h:2573
Event * _next
Definition: vspace.h:2572
virtual void stop_listen()=0
virtual bool start_listen(internals::ipc_signal_t sig)=0
VRef< Node > pop()
Definition: vspace.h:2391
void enqueue(T item)
Definition: vspace.h:2443
Semaphore _incoming
Definition: vspace.h:2386
Queue(size_t bound=0)
Definition: vspace.h:2435
void push(VRef< Node > node)
Definition: vspace.h:2400
T dequeue_nowait()
Definition: vspace.h:2422
VRef< Node > next
Definition: vspace.h:2383
Semaphore _outgoing
Definition: vspace.h:2387
Result< T > try_dequeue()
Definition: vspace.h:2460
friend class EnqueueEvent
Definition: vspace.h:2410
bool try_enqueue(T item)
Definition: vspace.h:2448
friend class DequeueEvent
Definition: vspace.h:2412
void enqueue_nowait(T item)
Definition: vspace.h:2414
bool _bounded
Definition: vspace.h:2388
VRef< Node > _head
Definition: vspace.h:2390
VRef< Node > _tail
Definition: vspace.h:2390
FastLock _lock
Definition: vspace.h:2389
int _waiting[internals::MAX_PROCESS+1]
Definition: vspace.h:2348
void next(int &index)
Definition: vspace.h:2351
bool start_wait(internals::ipc_signal_t sig=0)
Definition: vspace.cc:1066
internals::ipc_signal_t _signals[internals::MAX_PROCESS+1]
Definition: vspace.h:2349
FastLock _lock
Definition: vspace.h:2358
size_t value()
Definition: vspace.h:2369
Semaphore(size_t value=0)
Definition: vspace.h:2366
friend class SyncVar
Definition: vspace.h:2363
bool stop_wait()
Definition: vspace.cc:1081
virtual bool start_listen(internals::ipc_signal_t sig)
Definition: vspace.h:2664
SyncReadEvent(VRef< SyncVar< T > > syncvar)
Definition: vspace.h:2662
virtual void stop_listen()
Definition: vspace.h:2667
VRef< SyncVar< T > > _syncvar
Definition: vspace.h:2659
friend class SyncReadEvent
Definition: vspace.h:2476
VRef< Semaphore > _sem
Definition: vspace.h:2472
Result< T > try_read()
Definition: vspace.h:2548
FastLock _lock
Definition: vspace.h:2471
bool write(T value)
Definition: vspace.h:2556
bool test()
Definition: vspace.h:2484
void stop_wait()
Definition: vspace.h:2506
bool start_wait(internals::ipc_signal_t sig)
Definition: vspace.h:2490
bool remove(VRef< K > key, VRef< K > &oldkey, VRef< V > &oldvalue)
Definition: vspace.h:2239
VRef< V > value
Definition: vspace.h:2123
VRef< K > key
Definition: vspace.h:2122
bool find(VRef< K > key, VRef< V > &value)
Definition: vspace.h:2268
void _lock_bucket(size_t b)
Definition: vspace.h:2129
Spec::Value V
Definition: vspace.h:2118
bool remove(VRef< K > key)
Definition: vspace.h:2147
Spec::Key K
Definition: vspace.h:2117
VRef< VRef< Node > > _buckets
Definition: vspace.h:2125
bool add(VRef< K > key, VRef< V > value, bool replace=true)
Definition: vspace.h:2141
bool add(VRef< K > key, VRef< V > value, VRef< K > &oldkey, VRef< V > &oldvalue, bool replace=true)
Definition: vspace.h:2195
void _unlock_bucket(size_t b)
Definition: vspace.h:2132
VRef< internals::FastLock > _locks
Definition: vspace.h:2126
VRef< Node > next
Definition: vspace.h:2120
VRef< V > find(VRef< K > key)
Definition: vspace.h:2153
size_t _nbuckets
Definition: vspace.h:2127
VMap(size_t size=1024)
Definition: vspace.h:2163
VRef< char > _buffer
Definition: vspace.h:2066
VString(const char *s, size_t len)
Definition: vspace.h:2075
VRef< VString > clone() const
Definition: vspace.h:2093
VString(size_t len)
Definition: vspace.h:2082
size_t _len
Definition: vspace.h:2067
const char * str() const
Definition: vspace.h:2096
size_t len() const
Definition: vspace.h:2090
VString(const char *s)
Definition: vspace.h:2070
WaitSemaphoreEvent(VRef< Semaphore > sem)
Definition: vspace.h:2606
virtual bool start_listen(internals::ipc_signal_t sig)
Definition: vspace.h:2608
virtual void stop_listen()
Definition: vspace.h:2611
VRef< Semaphore > _sem
Definition: vspace.h:2603
FastLock(vaddr_t offset=0)
Definition: vspace.h:1445
return result
Definition: facAbsBiFact.cc:75
const CanonicalForm int s
Definition: facAbsFact.cc:51
const ExtensionInfo & info
< [in] sqrfree poly
STATIC_VAR poly last
Definition: hdegree.cc:1173
STATIC_VAR int offset
Definition: janet.cc:29
STATIC_VAR jList * T
Definition: janet.cc:30
NodeM * create()
Definition: janet.cc:757
ListNode * next
Definition: janet.h:31
char N base
Definition: ValueTraits.h:144
char * str(leftv arg)
Definition: shared.cc:704
void init()
Definition: lintree.cc:864
void drop_pending_signals()
void accept_signals()
Definition: vspace.cc:981
Block * block_ptr(vaddr_t vaddr)
Definition: vspace.h:1637
void unlock_metapage()
Definition: vspace.cc:883
const vaddr_t VADDR_NULL
Definition: vspace.h:1417
void init_flock_struct(struct flock &lock_info, size_t offset, size_t len, bool lock)
Definition: vspace.cc:858
size_t vaddr_t
Definition: vspace.h:1414
void lock_file(int fd, size_t offset, size_t len)
Definition: vspace.cc:867
void vmem_free(vaddr_t vaddr)
Definition: vspace.cc:756
vaddr_t vmem_alloc(size_t size)
Definition: vspace.cc:808
static vaddr_t allocated_ptr_to_vaddr(void *ptr)
Definition: vspace.h:1697
static const size_t MAX_SEGMENTS
Definition: vspace.h:1423
vaddr_t freelist[LOG2_SEGMENT_SIZE+1]
Definition: vspace.h:1511
static const size_t SEGMENT_SIZE
Definition: vspace.h:1424
static const size_t METABLOCK_SIZE
Definition: vspace.h:1420
static const int LOG2_SEGMENT_SIZE
Definition: vspace.h:1421
ipc_signal_t wait_signal(bool lock)
Definition: vspace.cc:987
void lock_metapage()
Definition: vspace.cc:879
static const int LOG2_MAX_SEGMENTS
Definition: vspace.h:1422
static const int MAX_PROCESS
Definition: vspace.h:1419
static VMem & vmem
Definition: vspace.h:1635
ProcessInfo process_info[MAX_PROCESS]
Definition: vspace.h:1513
static segaddr_t find_buddy(segaddr_t addr, int level)
Definition: vspace.h:1690
ipc_signal_t check_signal(bool resume, bool lock)
Definition: vspace.cc:944
void init_metapage(bool create)
Definition: vspace.cc:887
void unlock_file(int fd, size_t offset, size_t len)
Definition: vspace.cc:873
static const size_t SEGMENT_MASK
Definition: vspace.h:1425
bool send_signal(int processno, ipc_signal_t sig, bool lock)
Definition: vspace.cc:921
static int find_level(size_t size)
Definition: vspace.h:1681
const segaddr_t SEGADDR_NULL
Definition: vspace.h:1416
size_t config[4]
Definition: vspace.cc:573
size_t segaddr_t
Definition: vspace.h:1412
pid_t fork_process()
Definition: vspace.cc:993
static void vmem_deinit()
Definition: vspace.h:1742
ZRef< T > znew_uninitialized_array(size_t n)
Definition: vspace.h:2038
VRef< T > vnull()
Definition: vspace.h:1867
VRef< T > vnew_array(size_t n)
Definition: vspace.h:1885
ZRef< T > znew_uninitialized()
Definition: vspace.h:2022
ZRef< T > znew()
Definition: vspace.h:2015
ZRef< T > znull()
Definition: vspace.h:2010
ErrCode
Definition: vspace.h:1375
@ ErrGeneral
Definition: vspace.h:1377
@ ErrOS
Definition: vspace.h:1380
@ ErrNone
Definition: vspace.h:1376
@ ErrFile
Definition: vspace.h:1378
@ ErrMMap
Definition: vspace.h:1379
VRef< T > vnew_uninitialized_array(size_t n)
Definition: vspace.h:1895
internals::Mutex Mutex
Definition: vspace.h:2343
VMap< DictSpec > VDict
Definition: vspace.h:2333
VRef< T > vnew()
Definition: vspace.h:1872
static VRef< VString > vstring(const char *s)
Definition: vspace.h:2101
ZRef< T > znew_array(size_t n)
Definition: vspace.h:2028
static Status vmem_init()
Definition: vspace.h:1738
internals::Mutex FastLock
Definition: vspace.h:2340
VRef< T > vnew_uninitialized()
Definition: vspace.h:1879
#define NULL
Definition: omList.c:12
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
#define block
Definition: scanner.cc:646
int status int fd
Definition: si_signals.h:59
static void free_value(VRef< Value > value)
Definition: vspace.h:2328
VString Key
Definition: vspace.h:2296
static bool equal(const VString *s1, const VString *s2)
Definition: vspace.h:2308
static size_t hash(const VString *s)
Definition: vspace.h:2298
static void free_key(VRef< Key > key)
Definition: vspace.h:2325
VString Value
Definition: vspace.h:2297
T & default_value()
Definition: vspace.h:1392
Result(T result)
Definition: vspace.h:1387
bool ok()
Definition: vspace.h:1400
ErrCode err
Definition: vspace.h:1399
Status(ErrCode err)
Definition: vspace.h:1406
size_t offset() const
Definition: vspace.h:1825
bool operator!=(VRef< void > other)
Definition: vspace.h:1834
static VRef< void > from_vaddr(internals::vaddr_t vaddr)
Definition: vspace.h:1822
bool operator==(VRef< void > other)
Definition: vspace.h:1831
VRef< U > cast()
Definition: vspace.h:1854
void * to_ptr() const
Definition: vspace.h:1843
static VRef< void > alloc(size_t n=1)
Definition: vspace.h:1857
VRef(void *ptr)
Definition: vspace.h:1840
void * as_ptr() const
Definition: vspace.h:1846
internals::vaddr_t vaddr
Definition: vspace.h:1815
VRef(internals::vaddr_t vaddr)
Definition: vspace.h:1816
VRef< void > & operator=(VRef< void > other)
Definition: vspace.h:1849
VRef< T > & operator=(VRef< T > other)
Definition: vspace.h:1791
static VRef< T > alloc(size_t n=1)
Definition: vspace.h:1802
T & operator[](size_t index)
Definition: vspace.h:1795
size_t offset() const
Definition: vspace.h:1758
VRef(void *ptr)
Definition: vspace.h:1773
T & operator*() const
Definition: vspace.h:1785
bool is_null()
Definition: vspace.h:1770
T * as_ptr() const
Definition: vspace.h:1779
VRef(internals::vaddr_t vaddr)
Definition: vspace.h:1750
bool operator!=(VRef< T > other)
Definition: vspace.h:1764
T & as_ref() const
Definition: vspace.h:1782
VRef< U > cast()
Definition: vspace.h:1799
static VRef< T > from_vaddr(internals::vaddr_t vaddr)
Definition: vspace.h:1755
bool operator==(VRef< T > other)
Definition: vspace.h:1761
void free()
Definition: vspace.h:1805
void * to_ptr() const
Definition: vspace.h:1776
internals::vaddr_t vaddr
Definition: vspace.h:1749
T * operator->()
Definition: vspace.h:1788
internals::refcount_t rc
Definition: vspace.h:1941
char data[sizeof(T)]
Definition: vspace.h:1945
ZRef< U > cast() const
Definition: vspace.h:1987
ZRef(internals::vaddr_t vaddr)
Definition: vspace.h:1960
T * as_ptr() const
Definition: vspace.h:1971
bool is_null()
Definition: vspace.h:1965
void * to_ptr()
Definition: vspace.h:1953
T & as_ref() const
Definition: vspace.h:1974
internals::refcount_t & refcount()
Definition: vspace.h:1950
ZRef(void *ptr)
Definition: vspace.h:1968
internals::vaddr_t vaddr
Definition: vspace.h:1949
T * operator->()
Definition: vspace.h:1980
static internals::vaddr_t alloc()
Definition: vspace.h:2004
ZRef< T > & operator=(ZRef< T > other)
Definition: vspace.h:1983
void release()
Definition: vspace.h:1993
void retain()
Definition: vspace.h:1990
T & operator*() const
Definition: vspace.h:1977
void free()
Definition: vspace.h:1999
void mark_as_free(int level)
Definition: vspace.h:1561
void mark_as_allocated(vaddr_t vaddr, int level)
Definition: vspace.h:1552
void ensure_is_mapped(vaddr_t vaddr)
Definition: vspace.h:1615
std::FILE * file_handle
Definition: vspace.h:1591
size_t segment_no(vaddr_t vaddr)
Definition: vspace.h:1599
void * mmap_segment(int seg)
Definition: vspace.cc:656
Block * block_ptr(vaddr_t vaddr)
Definition: vspace.h:1610
VSeg segment(vaddr_t vaddr)
Definition: vspace.h:1596
void * to_ptr(vaddr_t vaddr)
Definition: vspace.h:1620
MetaPage * metapage
Definition: vspace.h:1589
static VMem vmem_global
Definition: vspace.h:1588
VSeg segments[MAX_SEGMENTS]
Definition: vspace.h:1594
vaddr_t vaddr(size_t segno, segaddr_t addr)
Definition: vspace.h:1602
segaddr_t segaddr(vaddr_t vaddr)
Definition: vspace.h:1605
ProcessChannel channels[MAX_PROCESS]
Definition: vspace.h:1595
Status init(int fd)
Definition: vspace.cc:589
void * ptr(segaddr_t addr)
Definition: vspace.h:1578
Block * block_ptr(segaddr_t addr)
Definition: vspace.h:1571
bool is_free(segaddr_t addr)
Definition: vspace.h:1574
unsigned char * base
Definition: vspace.h:1567
VSeg(void *base)
Definition: vspace.h:1583
static void lock(vaddr_t vaddr)
Definition: vspace.h:1658
std::ptrdiff_t dec(vaddr_t vaddr)
Definition: vspace.h:1672
refcount_t(std::ptrdiff_t init)
Definition: vspace.h:1664
std::ptrdiff_t inc(vaddr_t vaddr)
Definition: vspace.h:1666
static void unlock(vaddr_t vaddr)
Definition: vspace.h:1661
#define assert(A)
Definition: svd_si.h:3