My Project
Loading...
Searching...
No Matches
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
42namespace vspace {
43
44enum ErrCode {
45 ErrNone,
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 }
59 }
60private:
61 T& default_value() {
62 static T result;
63 return result;
64 }
65};
66
67struct Status {
69 bool ok() {
70 return err == ErrNone;
71 }
72 operator bool() {
73 return err == ErrNone;
74 }
76 }
77};
78
79namespace internals {
80
81typedef size_t segaddr_t;
82
83typedef size_t vaddr_t;
84
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
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
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
139extern size_t config[4];
140
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);
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?
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];
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.
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
261 ProcessChannel channels[MAX_PROCESS];
262 inline VSeg segment(vaddr_t vaddr) {
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 }
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
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) {
327 }
328 static void unlock(vaddr_t 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;
378
379public:
380 Mutex() : _owner(-1), _locklevel(0), _lock(vmem_alloc(1)) {
381 }
382 ~Mutex() {
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
405static inline Status vmem_init() {
406 return internals::vmem.init();
407}
408
409static inline void vmem_deinit() {
411}
412
413template <typename T>
414struct VRef {
415private:
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 {
436 }
437 bool is_null() {
439 }
440 VRef(void *ptr) {
442 }
443 void *to_ptr() const {
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() {
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
479template <>
480struct VRef<void> {
481private:
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 {
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() {
506 }
507 VRef(void *ptr) {
509 }
510 void *to_ptr() const {
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() {
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
533template <typename T>
534VRef<T> vnull() {
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 };
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 }
628 }
629 operator bool() {
631 }
632 bool is_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
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>
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;
1017 int _head, _tail;
1018 void next(int &index) {
1020 index = 0;
1021 else
1022 index++;
1023 }
1024 size_t _value;
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 };
1055 bool _bounded;
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),
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:
1139 VRef<Semaphore> _sem;
1140 bool _set;
1141 T _value;
1142 template <typename U>
1143 friend class SyncReadEvent;
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>
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>
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
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
1381};
1382
1383template <typename T>
1384struct Result {
1385 bool ok;
1388 }
1390 }
1391private:
1393 static T result;
1394 return result;
1395 }
1396};
1397
1398struct Status {
1400 bool ok() {
1401 return err == ErrNone;
1402 }
1403 operator bool() {
1404 return err == ErrNone;
1405 }
1407 }
1408};
1409
1410namespace internals {
1411
1412typedef size_t segaddr_t;
1413
1414typedef size_t vaddr_t;
1415
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.
1432private:
1433#ifdef HAVE_CPP_THREADS
1434 std::atomic_flag _lock;
1435 short _owner, _head, _tail;
1436#else
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
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
1470extern size_t config[4];
1471
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);
1488
1489struct Block;
1490struct MetaPage;
1491struct ProcessChannel;
1492
1497};
1498
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
1508struct 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
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.
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 }
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 }
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 }
1582 }
1583 VSeg(void *base) : base((unsigned char *) base) {
1584 }
1585};
1586
1587struct 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
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
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) {
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:
1711
1712public:
1714 }
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
1738static inline Status vmem_init() {
1739 return internals::vmem.init();
1740}
1741
1742static inline void vmem_deinit() {
1744}
1745
1746template <typename T>
1747struct VRef {
1748private:
1751 }
1752public:
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 {
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
1812template <>
1813struct VRef<void> {
1814private:
1817 }
1818
1819public:
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 }
1832 return vaddr == other.vaddr;
1833 }
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 {
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) {
1859 }
1860 void free() {
1863 }
1864};
1865
1866template <typename T>
1869}
1870
1871template <typename T>
1874 new (result.to_ptr()) T();
1875 return result;
1876}
1877
1878template <typename T>
1881 return result;
1882}
1883
1884template <typename T>
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>
1897 return result;
1898}
1899
1900template <typename T, typename Arg>
1901VRef<T> vnew(Arg arg) {
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) {
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) {
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) {
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) {
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 {
1942#if __cplusplus >= 201100
1943 alignas(T)
1944#endif
1945 char data[sizeof(T)];
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
1957public:
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
2009template <typename T>
2012}
2013
2014template <typename T>
2017 new (result.to_ptr()) T();
2018 return result;
2019}
2020
2021template <typename T>
2024 return result;
2025}
2026
2027template <typename T>
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>
2040 return result;
2041}
2042
2043template <typename T, typename Arg>
2044ZRef<T> znew(Arg arg) {
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) {
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) {
2060 new (result.to_ptr()) T(arg1, arg2, arg3);
2061 return result;
2062}
2063
2064class VString {
2065private:
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 }
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
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 {
2121 size_t hash;
2124 };
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);
2154 VRef<V> value;
2155 if (find(key, value))
2156 return value;
2157 else
2158 return vnull<V>();
2159 }
2160};
2161
2162template <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
2175template <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
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>
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;
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
2335pid_t fork_process();
2336
2337#ifdef HAVE_CPP_THREADS
2339#else
2341#endif
2342
2344
2346private:
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
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 {
2385 };
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
2434public:
2435 Queue(size_t bound = 0) :
2436 _incoming(0),
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
2468template <typename T>
2469class SyncVar {
2470private:
2473 bool _set;
2475 template <typename U>
2476 friend class SyncReadEvent;
2478 void stop_wait();
2479public:
2481 T read();
2483 bool write(T value);
2484 bool test() {
2485 return _set;
2486 }
2487};
2488
2489template <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
2505template <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
2516template <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
2547template <typename T>
2549 _lock.lock();
2550 Result<T> result = _set ? Result<T>(_value) : Result<T>();
2551 _lock.unlock();
2552 return result;
2553}
2554
2555template <typename T>
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:
2573 friend class EventSet;
2574public:
2576 virtual void stop_listen() = 0;
2577};
2578
2580private:
2582
2583public:
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
2602private:
2604
2605public:
2607 }
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:
2622
2623public:
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
2637template <typename T>
2638class DequeueEvent : public Event {
2639private:
2641
2642public:
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
2656template <typename T>
2657class SyncReadEvent : public Event {
2658private:
2660
2661public:
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.h:2587
Event * _head
Definition: vspace.h:2581
EventSet & operator<<(Event &event)
Definition: vspace.h:2594
EventSet & operator<<(Event *event)
Definition: vspace.h:2590
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
void enqueue(T item)
Definition: vspace.h:2443
Result< T > try_dequeue()
Definition: vspace.h:2460
VRef< Node > pop()
Definition: vspace.h:2391
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
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
VRef< V > find(VRef< K > key)
Definition: vspace.h:2153
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
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
const char * str() const
Definition: vspace.h:2096
VString(size_t len)
Definition: vspace.h:2082
size_t _len
Definition: vspace.h:2067
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
STATIC_VAR poly last
Definition: hdegree.cc:1173
NodeM * create()
Definition: janet.cc:757
STATIC_VAR int offset
Definition: janet.cc:29
STATIC_VAR jList * T
Definition: janet.cc:30
ListNode * next
Definition: janet.h:31
#define info
Definition: libparse.cc:1256
STATIC_VAR unsigned add[]
Definition: misc_ip.cc:107
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
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
Block * block_ptr(vaddr_t vaddr)
Definition: vspace.h:1637
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
VRef< T > vnew()
Definition: vspace.h:1872
pid_t fork_process()
Definition: vspace.cc:993
ZRef< T > znull()
Definition: vspace.h:2010
VRef< T > vnew_uninitialized_array(size_t n)
Definition: vspace.h:1895
ZRef< T > znew_array(size_t n)
Definition: vspace.h:2028
static void vmem_deinit()
Definition: vspace.h:1742
ZRef< T > znew()
Definition: vspace.h:2015
ZRef< T > znew_uninitialized()
Definition: vspace.h:2022
VRef< T > vnull()
Definition: vspace.h:1867
VRef< T > vnew_array(size_t n)
Definition: vspace.h:1885
ZRef< T > znew_uninitialized_array(size_t n)
Definition: vspace.h:2038
VRef< T > vnew_uninitialized()
Definition: vspace.h:1879
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
internals::Mutex Mutex
Definition: vspace.h:2343
VMap< DictSpec > VDict
Definition: vspace.h:2333
static Status vmem_init()
Definition: vspace.h:1738
static VRef< VString > vstring(const char *s)
Definition: vspace.h:2101
internals::Mutex FastLock
Definition: vspace.h:2340
#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 void size_t count write
Definition: si_signals.h:67
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
void * as_ptr() const
Definition: vspace.h:1846
VRef< void > & operator=(VRef< void > other)
Definition: vspace.h:1849
bool operator==(VRef< void > other)
Definition: vspace.h:1831
static VRef< void > from_vaddr(internals::vaddr_t vaddr)
Definition: vspace.h:1822
VRef(void *ptr)
Definition: vspace.h:1840
internals::vaddr_t vaddr
Definition: vspace.h:1815
VRef(internals::vaddr_t vaddr)
Definition: vspace.h:1816
void * to_ptr() const
Definition: vspace.h:1843
static VRef< void > alloc(size_t n=1)
Definition: vspace.h:1857
VRef< U > cast()
Definition: vspace.h:1854
VRef< U > cast()
Definition: vspace.h:1799
T & as_ref() const
Definition: vspace.h:1782
T * as_ptr() const
Definition: vspace.h:1779
T & operator*() const
Definition: vspace.h:1785
void * to_ptr() const
Definition: vspace.h:1776
T * operator->()
Definition: vspace.h:1788
size_t offset() const
Definition: vspace.h:1758
VRef< T > & operator=(VRef< T > other)
Definition: vspace.h:1791
VRef(void *ptr)
Definition: vspace.h:1773
bool is_null()
Definition: vspace.h:1770
static VRef< T > alloc(size_t n=1)
Definition: vspace.h:1802
VRef(internals::vaddr_t vaddr)
Definition: vspace.h:1750
bool operator!=(VRef< T > other)
Definition: vspace.h:1764
static VRef< T > from_vaddr(internals::vaddr_t vaddr)
Definition: vspace.h:1755
T & operator[](size_t index)
Definition: vspace.h:1795
bool operator==(VRef< T > other)
Definition: vspace.h:1761
void free()
Definition: vspace.h:1805
internals::vaddr_t vaddr
Definition: vspace.h:1749
internals::refcount_t rc
Definition: vspace.h:1941
char data[sizeof(T)]
Definition: vspace.h:1945
T & operator*() const
Definition: vspace.h:1977
T & as_ref() const
Definition: vspace.h:1974
ZRef< U > cast() const
Definition: vspace.h:1987
internals::refcount_t & refcount()
Definition: vspace.h:1950
ZRef(internals::vaddr_t vaddr)
Definition: vspace.h:1960
void * to_ptr()
Definition: vspace.h:1953
bool is_null()
Definition: vspace.h:1965
ZRef< T > & operator=(ZRef< T > other)
Definition: vspace.h:1983
ZRef(void *ptr)
Definition: vspace.h:1968
internals::vaddr_t vaddr
Definition: vspace.h:1949
T * operator->()
Definition: vspace.h:1980
T * as_ptr() const
Definition: vspace.h:1971
static internals::vaddr_t alloc()
Definition: vspace.h:2004
void release()
Definition: vspace.h:1993
void retain()
Definition: vspace.h:1990
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
Block * block_ptr(vaddr_t vaddr)
Definition: vspace.h:1610
size_t segment_no(vaddr_t vaddr)
Definition: vspace.h:1599
void * mmap_segment(int seg)
Definition: vspace.cc:656
VSeg segment(vaddr_t vaddr)
Definition: vspace.h:1596
MetaPage * metapage
Definition: vspace.h:1589
static VMem vmem_global
Definition: vspace.h:1588
void * to_ptr(vaddr_t vaddr)
Definition: vspace.h:1620
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
Block * block_ptr(segaddr_t addr)
Definition: vspace.h:1571
void * ptr(segaddr_t addr)
Definition: vspace.h:1578
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