1 #ifndef VSPACE_H
2 #define VSPACE_H
3 #include <fcntl.h>
4 #include <stddef.h>
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <string.h>
8 #include <sys/mman.h>
9 #include <sys/stat.h>
10 #include <unistd.h>
11 #include <assert.h>
12 #include <new> // for placement new
13 #include "kernel/mod2.h"
14
15 #ifdef HAVE_VSPACE
16
17 #if __cplusplus >= 201100
18 #define HAVE_CPP_THREADS
19 #include <atomic>
20 #else
21 #undef HAVE_CPP_THREADS
22 #endif
23
24 // vspace is a C++ library designed to allow processes in a
25 // multi-process environment to interoperate via mmapped shared memory.
26 // The library provides facilities for shared memory allocation and
27 // deallocation, shared mutexes, semaphores, queues, lists, and hash
28 // tables.
29 //
30 // The underlying file is organized starting with a block containing
31 // meta information such as free lists and process information necessary
32 // for IPC, followed by one or more segments of mmapped memory. Each
33 // address within the file is represented via its offset from the
34 // beginning of the first segment.
35 //
36 // These offsets are wrapped within the VRef<T> class, which works like
37 // a T* pointer, but transparently maps file offsets to memory
38 // locations.
39
40 namespace vspace {
41
42 enum ErrCode {
43 ErrNone,
44 ErrGeneral,
45 ErrFile,
46 ErrMMap,
47 ErrOS,
48 };
49
50 template <typename T>
51 struct Result {
52 bool ok;
53 T result;
ResultResult54 Result(T result) : ok(true), result(result) {
55 }
ResultResult56 Result() : ok(false), result(default_value()) {
57 }
58 private:
default_valueResult59 T& default_value() {
60 static T result;
61 return result;
62 }
63 };
64
65 struct Status {
66 ErrCode err;
okStatus67 bool ok() {
68 return err == ErrNone;
69 }
70 operator bool() {
71 return err == ErrNone;
72 }
StatusStatus73 Status(ErrCode err) : err(err) {
74 }
75 };
76
77 namespace internals {
78
79 typedef size_t segaddr_t;
80
81 typedef size_t vaddr_t;
82
83 const segaddr_t SEGADDR_NULL = ~(segaddr_t) 0;
84 const vaddr_t VADDR_NULL = ~(segaddr_t) 0;
85
86 static const int MAX_PROCESS = 64;
87 static const size_t METABLOCK_SIZE = 128 * 1024; // 128 KB
88 static const int LOG2_SEGMENT_SIZE = 28; // 256 MB
89 static const int LOG2_MAX_SEGMENTS = 10; // 256 GB
90 static const size_t MAX_SEGMENTS = 1 << LOG2_MAX_SEGMENTS;
91 static const size_t SEGMENT_SIZE = 1 << LOG2_SEGMENT_SIZE;
92 static const size_t SEGMENT_MASK = (SEGMENT_SIZE - 1);
93
94 // This is a very basic spinlock implementation that does not guarantee
95 // fairness.
96 //
97 // TODO: add a wait queue and/or use futexes on Linux.
98 class FastLock {
99 private:
100 #ifdef HAVE_CPP_THREADS
101 std::atomic_flag _lock;
102 short _owner, _head, _tail;
103 #else
104 vaddr_t _offset;
105 #endif
106 public:
107 #ifdef HAVE_CPP_THREADS
108 FastLock(vaddr_t offset = 0) : _owner(-1), _head(-1), _tail(-1) {
109 _lock.clear();
110 }
111 #else
112 FastLock(vaddr_t offset = 0) : _offset(offset) {
113 }
114 #endif
115 #ifdef HAVE_CPP_THREADS
116 // We only need to define the copy constructur for the
117 // atomic version, as the std::atomic_flag constructor
118 // is deleted.
FastLock(const FastLock & other)119 FastLock(const FastLock &other) {
120 _owner = other._owner;
121 _head = other._head;
122 _tail = other._tail;
123 _lock.clear();
124 }
125 FastLock &operator=(const FastLock &other) {
126 _owner = other._owner;
127 _head = other._head;
128 _tail = other._tail;
129 _lock.clear();
130 return *this;
131 }
132 #endif
133 void lock();
134 void unlock();
135 };
136
137 extern size_t config[4];
138
139 void init_flock_struct(
140 struct flock &lock_info, size_t offset, size_t len, bool lock);
141 void lock_file(int fd, size_t offset, size_t len = 1);
142 void unlock_file(int fd, size_t offset, size_t len = 1);
143
144 void lock_metapage();
145 void unlock_metapage();
146 void init_metapage(bool create);
147
148 typedef int ipc_signal_t;
149
150 bool send_signal(int processno, ipc_signal_t sig = 0, bool lock = true);
151 ipc_signal_t check_signal(bool resume = false, bool lock = true);
152 void accept_signals();
153 ipc_signal_t wait_signal(bool lock = true);
154 void drop_pending_signals();
155
156 struct Block;
157 struct MetaPage;
158 struct ProcessChannel;
159
160 enum SignalState {
161 Waiting = 0,
162 Pending = 1,
163 Accepted = 2,
164 };
165
166 struct ProcessInfo {
167 pid_t pid;
168 SignalState sigstate; // are there pending signals?
169 ipc_signal_t signal;
170 #ifdef HAVE_CPP_THREADS
171 int next; // next in queue waiting for a lock.
172 #endif
173 };
174
175 struct MetaPage {
176 size_t config_header[4];
177 FastLock allocator_lock;
178 vaddr_t freelist[LOG2_SEGMENT_SIZE + 1];
179 int segment_count;
180 ProcessInfo process_info[MAX_PROCESS];
181 };
182
183 // We use pipes/fifos to signal processes. For each process, fd_read is
184 // where the process reads from and fd_write is where other processes
185 // signal the reading process. Only single bytes are sent across each
186 // channel. Because the effect of concurrent writes is undefined, bytes
187 // must only be written by a single process at the time. This is usually
188 // the case when the sending process knows that the receiving process is
189 // waiting for a resource that the sending process currently holds. See
190 // the Semaphore implementation for an example.
191
192 struct ProcessChannel {
193 int fd_read, fd_write;
194 };
195
196 struct Block {
197 // the lowest bits of prev encode whether we are looking at an
198 // allocated or free block. For an allocared block, the lowest bits
199 // are 01. For a free block, they are 00 (for a null reference (==
200 // -1), they are 11.
201 //
202 // For allocated blocks, the higher bits encode the segment and the
203 // log2 of the block size (level). This requires LOG2_MAX_SEGMENTS +
204 // log2(sizeof(vaddr_t) * 8) + 2 bits.
205 //
206 // For free blocks, the level is stored in the data field.
207 vaddr_t prev;
208 vaddr_t next;
209 size_t data[1];
is_freeBlock210 bool is_free() {
211 return (prev & 3) != 1;
212 }
levelBlock213 int level() {
214 if (is_free())
215 return (int) data[0];
216 else
217 return (int) (prev >> (LOG2_MAX_SEGMENTS + 2));
218 }
mark_as_allocatedBlock219 void mark_as_allocated(vaddr_t vaddr, int level) {
220 vaddr_t bits = level;
221 bits <<= LOG2_MAX_SEGMENTS;
222 bits |= vaddr >> LOG2_SEGMENT_SIZE;
223 bits <<= 2;
224 bits |= 1;
225 prev = bits;
226 next = 0;
227 }
mark_as_freeBlock228 void mark_as_free(int level) {
229 data[0] = level;
230 }
231 };
232
233 struct VSeg {
234 unsigned char *base;
block_ptrVSeg235 inline Block *block_ptr(segaddr_t addr) {
236 return (Block *) (base + addr);
237 }
is_freeVSeg238 bool is_free(segaddr_t addr) {
239 Block *block = block_ptr(addr);
240 return block->is_free();
241 }
ptrVSeg242 inline void *ptr(segaddr_t addr) {
243 return (void *) (base + addr);
244 }
VSegVSeg245 VSeg() : base(NULL) {
246 }
VSegVSeg247 VSeg(void *base) : base((unsigned char *) base) {
248 }
249 };
250
251 struct VMem {
252 static VMem vmem_global;
253 MetaPage *metapage;
254 int fd;
255 FILE *file_handle;
256 int current_process; // index into process table
257 vaddr_t *freelist; // reference to metapage information
258 VSeg segments[MAX_SEGMENTS];
259 ProcessChannel channels[MAX_PROCESS];
segmentVMem260 inline VSeg segment(vaddr_t vaddr) {
261 return segments[vaddr >> LOG2_SEGMENT_SIZE];
262 }
segment_noVMem263 inline size_t segment_no(vaddr_t vaddr) {
264 return vaddr >> LOG2_SEGMENT_SIZE;
265 }
vaddrVMem266 inline vaddr_t vaddr(size_t segno, segaddr_t addr) {
267 return (segno << LOG2_SEGMENT_SIZE) | addr;
268 }
segaddrVMem269 inline segaddr_t segaddr(vaddr_t vaddr) {
270 if (vaddr == VADDR_NULL)
271 return SEGADDR_NULL;
272 return vaddr & SEGMENT_MASK;
273 }
block_ptrVMem274 inline Block *block_ptr(vaddr_t vaddr) {
275 if (vaddr == VADDR_NULL)
276 return NULL;
277 return (Block *) (segment(vaddr).base + segaddr(vaddr));
278 }
ensure_is_mappedVMem279 inline void ensure_is_mapped(vaddr_t vaddr) {
280 int seg = vaddr >> LOG2_SEGMENT_SIZE;
281 if (segments[seg].base != NULL)
282 return;
283 segments[seg] = mmap_segment(seg);
284 }
to_ptrVMem285 inline void *to_ptr(vaddr_t vaddr) {
286 if (vaddr == VADDR_NULL)
287 return NULL;
288 ensure_is_mapped(vaddr);
289 return segment(vaddr).ptr(segaddr(vaddr));
290 }
291 size_t filesize();
292 Status init(int fd);
293 Status init();
294 Status init(const char *path);
295 void deinit();
296 void *mmap_segment(int seg);
297 void add_segment();
298 };
299
300 static VMem &vmem = VMem::vmem_global;
301
block_ptr(vaddr_t vaddr)302 inline Block *block_ptr(vaddr_t vaddr) {
303 return vmem.block_ptr(vaddr);
304 }
305
306 #ifdef HAVE_CPP_THREADS
307 struct refcount_t {
308 std::atomic<ptrdiff_t> rc;
refcount_trefcount_t309 refcount_t(ptrdiff_t init) : rc(init) {
310 }
increfcount_t311 ptrdiff_t inc(vaddr_t vaddr) {
312 rc++;
313 return (ptrdiff_t) rc;
314 }
decrefcount_t315 ptrdiff_t dec(vaddr_t vaddr) {
316 rc--;
317 return (ptrdiff_t) rc;
318 }
319 };
320 #else
321 struct refcount_t {
322 ptrdiff_t rc;
lockrefcount_t323 static void lock(vaddr_t vaddr) {
324 lock_file(vmem.fd, METABLOCK_SIZE + vaddr);
325 }
unlockrefcount_t326 static void unlock(vaddr_t vaddr) {
327 unlock_file(vmem.fd, METABLOCK_SIZE + vaddr);
328 }
refcount_trefcount_t329 refcount_t(ptrdiff_t init) : rc(init) {
330 }
increfcount_t331 ptrdiff_t inc(vaddr_t vaddr) {
332 lock(vaddr);
333 ptrdiff_t result = ++rc;
334 unlock(vaddr);
335 return result;
336 }
decrefcount_t337 ptrdiff_t dec(vaddr_t vaddr) {
338 lock(vaddr);
339 ptrdiff_t result = --rc;
340 unlock(vaddr);
341 return result;
342 }
343 };
344 #endif
345
find_level(size_t size)346 static inline int find_level(size_t size) {
347 int level = 0;
348 while ((1 << (level + 8)) <= size)
349 level += 8;
350 while ((1 << level) < size)
351 level++;
352 return level;
353 }
354
find_buddy(segaddr_t addr,int level)355 static inline segaddr_t find_buddy(segaddr_t addr, int level) {
356 return addr ^ (1 << level);
357 }
358
359 void vmem_free(vaddr_t vaddr);
360 vaddr_t vmem_alloc(size_t size);
361
allocated_ptr_to_vaddr(void * ptr)362 static inline vaddr_t allocated_ptr_to_vaddr(void *ptr) {
363 char *addr = (char *) ptr - sizeof(Block);
364 vaddr_t info = ((Block *) addr)->prev;
365 int seg = info & (MAX_SEGMENTS - 1);
366 unsigned char *segstart = vmem.segments[seg].base;
367 size_t offset = (unsigned char *) ptr - segstart;
368 return (seg << LOG2_SEGMENT_SIZE) | offset;
369 }
370
371 class Mutex {
372 private:
373 int _owner;
374 int _locklevel;
375 vaddr_t _lock;
376
377 public:
Mutex()378 Mutex() : _owner(-1), _locklevel(0), _lock(vmem_alloc(1)) {
379 }
~Mutex()380 ~Mutex() {
381 vmem_free(_lock);
382 }
lock()383 void lock() {
384 if (_owner == vmem.current_process) {
385 _locklevel++;
386 } else {
387 lock_file(vmem.fd, METABLOCK_SIZE + _lock);
388 _owner = vmem.current_process;
389 _locklevel = 1;
390 }
391 }
unlock()392 void unlock() {
393 if (--_locklevel == 0) {
394 assert(_owner == vmem.current_process);
395 _owner = -1;
396 unlock_file(vmem.fd, METABLOCK_SIZE + _lock);
397 }
398 }
399 };
400
401 }; // namespace internals
402
vmem_init()403 static inline Status vmem_init() {
404 return internals::vmem.init();
405 }
406
vmem_deinit()407 static inline void vmem_deinit() {
408 internals::vmem.deinit();
409 }
410
411 template <typename T>
412 struct VRef {
413 private:
414 internals::vaddr_t vaddr;
VRefVRef415 VRef(internals::vaddr_t vaddr) : vaddr(vaddr) {
416 }
417 public:
VRefVRef418 VRef() : vaddr(internals::VADDR_NULL) {
419 }
from_vaddrVRef420 static VRef<T> from_vaddr(internals::vaddr_t vaddr) {
421 return VRef(vaddr);
422 }
offsetVRef423 size_t offset() const {
424 return vaddr;
425 }
426 bool operator==(VRef<T> other) {
427 return vaddr == other.vaddr;
428 }
429 bool operator!=(VRef<T> other) {
430 return vaddr != other.vaddr;
431 }
432 operator bool() const {
433 return vaddr != internals::VADDR_NULL;
434 }
is_nullVRef435 bool is_null() {
436 return vaddr == internals::VADDR_NULL;
437 }
VRefVRef438 VRef(void *ptr) {
439 vaddr = internals::allocated_ptr_to_vaddr(ptr);
440 }
to_ptrVRef441 void *to_ptr() const {
442 return internals::vmem.to_ptr(vaddr);
443 }
as_ptrVRef444 T *as_ptr() const {
445 return (T *) to_ptr();
446 }
as_refVRef447 T &as_ref() const {
448 return *(T *) to_ptr();
449 }
450 T &operator*() const {
451 return *(T *) to_ptr();
452 }
453 T *operator->() {
454 return (T *) to_ptr();
455 }
456 VRef<T> &operator=(VRef<T> other) {
457 vaddr = other.vaddr;
458 return *this;
459 }
460 T &operator[](size_t index) {
461 return as_ptr()[index];
462 }
463 template <typename U>
castVRef464 VRef<U> cast() {
465 return VRef<U>::from_vaddr(vaddr);
466 }
467 static VRef<T> alloc(size_t n = 1) {
468 return VRef<T>(internals::vmem_alloc(n * sizeof(T)));
469 }
freeVRef470 void free() {
471 as_ptr()->~T(); // explicitly call destructor
472 internals::vmem_free(vaddr);
473 vaddr = internals::VADDR_NULL;
474 }
475 };
476
477 template <>
478 struct VRef<void> {
479 private:
480 internals::vaddr_t vaddr;
481 VRef(internals::vaddr_t vaddr) : vaddr(vaddr) {
482 }
483
484 public:
485 VRef() : vaddr(internals::VADDR_NULL) {
486 }
487 static VRef<void> from_vaddr(internals::vaddr_t vaddr) {
488 return VRef(vaddr);
489 }
490 size_t offset() const {
491 return vaddr;
492 }
493 operator bool() const {
494 return vaddr != internals::VADDR_NULL;
495 }
496 bool operator==(VRef<void> other) {
497 return vaddr == other.vaddr;
498 }
499 bool operator!=(VRef<void> other) {
500 return vaddr != other.vaddr;
501 }
502 bool is_null() {
503 return vaddr == internals::VADDR_NULL;
504 }
505 VRef(void *ptr) {
506 vaddr = internals::allocated_ptr_to_vaddr(ptr);
507 }
508 void *to_ptr() const {
509 return internals::vmem.to_ptr(vaddr);
510 }
511 void *as_ptr() const {
512 return (void *) to_ptr();
513 }
514 VRef<void> &operator=(VRef<void> other) {
515 vaddr = other.vaddr;
516 return *this;
517 }
518 template <typename U>
519 VRef<U> cast() {
520 return VRef<U>::from_vaddr(vaddr);
521 }
522 static VRef<void> alloc(size_t n = 1) {
523 return VRef<void>(internals::vmem_alloc(n));
524 }
525 void free() {
526 internals::vmem_free(vaddr);
527 vaddr = internals::VADDR_NULL;
528 }
529 };
530
531 template <typename T>
532 VRef<T> vnull() {
533 return VRef<T>::from_vaddr(internals::VADDR_NULL);
534 }
535
536 template <typename T>
537 VRef<T> vnew() {
538 VRef<T> result = VRef<T>::alloc();
539 new (result.to_ptr()) T();
540 return result;
541 }
542
543 template <typename T>
544 VRef<T> vnew_uninitialized() {
545 VRef<T> result = VRef<T>::alloc();
546 return result;
547 }
548
549 template <typename T>
550 VRef<T> vnew_array(size_t n) {
551 VRef<T> result = VRef<T>::alloc(n);
552 T *ptr = result.as_ptr();
553 for (size_t i = 0; i < n; i++) {
554 new (ptr + i) T();
555 }
556 return result;
557 }
558
559 template <typename T>
560 VRef<T> vnew_uninitialized_array(size_t n) {
561 VRef<T> result = VRef<T>::alloc(n);
562 return result;
563 }
564
565 template <typename T, typename Arg>
566 VRef<T> vnew(Arg arg) {
567 VRef<T> result = VRef<T>::alloc();
568 new (result.to_ptr()) T(arg);
569 return result;
570 }
571
572 template <typename T, typename Arg1, typename Arg2>
573 VRef<T> vnew(Arg1 arg1, Arg2 arg2) {
574 VRef<T> result = VRef<T>::alloc();
575 new (result.to_ptr()) T(arg1, arg2);
576 return result;
577 }
578
579 template <typename T, typename Arg1, typename Arg2, typename Arg3>
580 VRef<T> vnew(Arg1 arg1, Arg2 arg2, Arg3 arg3) {
581 VRef<T> result = VRef<T>::alloc();
582 new (result.to_ptr()) T(arg1, arg2, arg3);
583 return result;
584 }
585
586 template <typename T, typename Arg1, typename Arg2, typename Arg3,
587 typename Arg4>
588 VRef<T> vnew(Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4) {
589 VRef<T> result = VRef<T>::alloc();
590 new (result.to_ptr()) T(arg1, arg2, arg3, arg4);
591 return result;
592 }
593
594 template <typename T, typename Arg1, typename Arg2, typename Arg3,
595 typename Arg4, typename Arg5>
596 VRef<T> vnew(Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5 arg5) {
597 VRef<T> result = VRef<T>::alloc();
598 new (result.to_ptr()) T(arg1, arg2, arg3, arg4, arg5);
599 return result;
600 }
601
602 template <typename T>
603 struct ZRef {
604 private:
605 struct RefCounted {
606 internals::refcount_t rc;
607 #if __cplusplus >= 201100
608 alignas(T)
609 #endif
610 char data[sizeof(T)];
611 RefCounted() : rc(1) {
612 }
613 };
614 internals::vaddr_t vaddr;
615 internals::refcount_t &refcount() {
616 return ((RefCounted *) (internals::vmem.to_ptr(vaddr)))->rc;
617 }
618 void *to_ptr() {
619 return &(((RefCounted *) (internals::vmem.to_ptr(vaddr)))->data);
620 }
621
622 public:
623 ZRef() : vaddr(internals::VADDR_NULL) {
624 }
625 ZRef(internals::vaddr_t vaddr) : vaddr(vaddr) {
626 }
627 operator bool() {
628 return vaddr != internals::VADDR_NULL;
629 }
630 bool is_null() {
631 return vaddr == internals::VADDR_NULL;
632 }
633 ZRef(void *ptr) {
634 vaddr = internals::allocated_ptr_to_vaddr(ptr);
635 }
636 T *as_ptr() const {
637 return (T *) to_ptr();
638 }
639 T &as_ref() const {
640 return *(T *) to_ptr();
641 }
642 T &operator*() const {
643 return *(T *) to_ptr();
644 }
645 T *operator->() {
646 return (T *) to_ptr();
647 }
648 ZRef<T> &operator=(ZRef<T> other) {
649 vaddr = other.vaddr;
650 }
651 template <typename U>
652 ZRef<U> cast() const {
653 return ZRef<U>(vaddr);
654 }
655 void retain() {
656 refcount().inc(vaddr);
657 }
658 void release() {
659 if (refcount().dec(vaddr) == 0) {
660 as_ref().~T();
661 internals::vmem_free(vaddr);
662 }
663 }
664 void free() {
665 as_ptr()->~T(); // explicitly call destructor
666 internals::vmem_free(vaddr);
667 vaddr = internals::VADDR_NULL;
668 }
669 static internals::vaddr_t alloc() {
670 return internals::vmem_alloc(sizeof(RefCounted));
671 }
672 };
673
674 template <typename T>
675 ZRef<T> znull() {
676 return ZRef<T>(internals::VADDR_NULL);
677 }
678
679 template <typename T>
680 ZRef<T> znew() {
681 ZRef<T> result = ZRef<T>::alloc();
682 new (result.to_ptr()) T();
683 return result;
684 }
685
686 template <typename T>
687 ZRef<T> znew_uninitialized() {
688 ZRef<T> result = ZRef<T>::alloc();
689 return result;
690 }
691
692 template <typename T>
693 ZRef<T> znew_array(size_t n) {
694 ZRef<T> result = ZRef<T>::alloc();
695 T *ptr = result.as_ptr();
696 for (size_t i = 0; i < n; i++) {
697 new (ptr + i) T();
698 }
699 return result;
700 }
701
702 template <typename T>
703 ZRef<T> znew_uninitialized_array(size_t n) {
704 ZRef<T> result = ZRef<T>::alloc();
705 return result;
706 }
707
708 template <typename T, typename Arg>
709 ZRef<T> znew(Arg arg) {
710 ZRef<T> result = ZRef<T>::alloc();
711 new (result.to_ptr()) T(arg);
712 return result;
713 }
714
715 template <typename T, typename Arg1, typename Arg2>
716 ZRef<T> znew(Arg1 arg1, Arg2 arg2) {
717 ZRef<T> result = ZRef<T>::alloc();
718 new (result.to_ptr()) T(arg1, arg2);
719 return result;
720 }
721
722 template <typename T, typename Arg1, typename Arg2, typename Arg3>
723 ZRef<T> znew(Arg1 arg1, Arg2 arg2, Arg3 arg3) {
724 ZRef<T> result = ZRef<T>::alloc();
725 new (result.to_ptr()) T(arg1, arg2, arg3);
726 return result;
727 }
728
729 class VString {
730 private:
731 VRef<char> _buffer;
732 size_t _len;
733
734 public:
735 VString(const char *s) {
736 _len = strlen(s);
737 _buffer = vnew_uninitialized_array<char>(_len + 1);
738 strcpy(_buffer.as_ptr(), s);
739 }
740 VString(const char *s, size_t len) {
741 _len = len;
742 _buffer = vnew_uninitialized_array<char>(len + 1);
743 char *buffer = _buffer.as_ptr();
744 memcpy(buffer, s, len);
745 buffer[len] = '\0';
746 }
747 VString(size_t len) {
748 _len = len;
749 _buffer = vnew_uninitialized_array<char>(len + 1);
750 _buffer[len] = '\0';
751 }
752 ~VString() {
753 _buffer.free();
754 }
755 size_t len() const {
756 return _len;
757 }
758 VRef<VString> clone() const {
759 return vnew<VString>(_buffer.as_ptr(), _len);
760 }
761 const char *str() const {
762 return _buffer.as_ptr();
763 }
764 };
765
766 static inline VRef<VString> vstring(const char *s) {
767 return vnew<VString>(s);
768 }
769
770 static inline VRef<VString> vstring(const char *s, size_t len) {
771 return vnew<VString>(s, len);
772 }
773
774 static inline VRef<VString> vstring(size_t len) {
775 return vnew<VString>(len);
776 }
777
778
779 template <typename Spec>
780 class VMap {
781 private:
782 typedef typename Spec::Key K;
783 typedef typename Spec::Value V;
784 struct Node {
785 VRef<Node> next;
786 size_t hash;
787 VRef<K> key;
788 VRef<V> value;
789 };
790 VRef<VRef<Node> > _buckets;
791 VRef<internals::FastLock> _locks;
792 size_t _nbuckets;
793
794 void _lock_bucket(size_t b) {
795 _locks[b].lock();
796 }
797 void _unlock_bucket(size_t b) {
798 _locks[b].unlock();
799 }
800
801 public:
802 VMap(size_t size = 1024);
803 ~VMap();
804 bool add(VRef<K> key, VRef<V> value, VRef<K> &oldkey, VRef<V> &oldvalue,
805 bool replace = true);
806 bool add(VRef<K> key, VRef<V> value, bool replace = true) {
807 VRef<K> oldkey;
808 VRef<V> oldvalue;
809 return add(key, value, oldkey, oldvalue, replace);
810 }
811 bool remove(VRef<K> key, VRef<K> &oldkey, VRef<V> &oldvalue);
812 bool remove(VRef<K> key) {
813 VRef<K> oldkey;
814 VRef<V> oldvalue;
815 return remove(key, oldkey, oldvalue);
816 }
817 bool find(VRef<K> key, VRef<V> &value);
818 VRef<V> find(VRef<K> key) {
819 VRef<V> value;
820 if (find(key, value))
821 return value;
822 else
823 return vnull<V>();
824 }
825 };
826
827 template <typename Spec>
828 VMap<Spec>::VMap(size_t size) {
829 using namespace internals;
830 _nbuckets = 8;
831 while (_nbuckets < size)
832 _nbuckets *= 2;
833 _buckets = vnew_array<VRef<Node> >(_nbuckets);
834 _locks = vnew_uninitialized_array<FastLock>(_nbuckets);
835 for (size_t i = 0; i < _nbuckets; i++)
836 _locks[i]
837 = FastLock(METABLOCK_SIZE + _locks.offset() + sizeof(FastLock) * i);
838 }
839
840 template <typename Spec>
841 VMap<Spec>::~VMap() {
842 for (size_t b = 0; b < _nbuckets; b++) {
843 _lock_bucket(b);
844 VRef<Node> node = _buckets[b];
845 while (node) {
846 Node *node_ptr = node.as_ptr();
847 VRef<Node> next = node_ptr->next;
848 Spec::free_key(node_ptr->key);
849 Spec::free_value(node_ptr->value);
850 node.free();
851 node = next;
852 }
853 _unlock_bucket(b);
854 }
855 _buckets.free();
856 _locks.free();
857 }
858
859 template <typename Spec>
860 bool VMap<Spec>::add(VRef<K> key, VRef<V> value, VRef<K> &oldkey,
861 VRef<V> &oldvalue, bool replace) {
862 size_t hash = Spec::hash(key.as_ptr());
863 size_t b = hash & (_nbuckets - 1);
864 _lock_bucket(b);
865 VRef<Node> node = _buckets[b];
866 VRef<Node> last = vnull<Node>();
867 while (!node.is_null()) {
868 Node *node_ptr = node.as_ptr();
869 if (hash == node_ptr->hash
870 && Spec::equal(key.as_ptr(), node_ptr->key.as_ptr())) {
871 value = node_ptr->value;
872 if (!last.is_null()) {
873 // move to front
874 last->next = node_ptr->next;
875 node_ptr->next = _buckets[b];
876 _buckets[b] = node;
877 }
878 oldkey = node_ptr->key;
879 oldvalue = node_ptr->value;
880 if (replace) {
881 node_ptr->key = key;
882 node_ptr->value = value;
883 }
884 _unlock_bucket(b);
885 return false;
886 }
887 last = node;
888 node = node->next;
889 }
890 node = vnew<Node>();
891 Node *node_ptr = node.as_ptr();
892 node_ptr->hash = hash;
893 node_ptr->key = key;
894 node_ptr->value = value;
895 node_ptr->next = _buckets[b];
896 _buckets[b] = node;
897 oldkey = key;
898 oldvalue = value;
899 _unlock_bucket(b);
900 return true;
901 }
902
903 template <typename Spec>
904 bool VMap<Spec>::remove(VRef<K> key, VRef<K> &oldkey, VRef<V> &oldvalue) {
905 size_t hash = Spec::hash(key.as_ptr());
906 size_t b = hash & (_nbuckets - 1);
907 _lock_bucket(b);
908 VRef<Node> node = _buckets[b];
909 VRef<Node> last = vnull<Node>();
910 while (!node.is_null()) {
911 Node *node_ptr = node.as_ptr();
912 if (hash == node_ptr->hash
913 && Spec::equal(key.as_ptr(), node_ptr->key.as_ptr())) {
914 oldkey = node_ptr->key;
915 oldvalue = node_ptr->value;
916 // remove from list
917 if (last.is_null()) {
918 _buckets[b] = node_ptr->next;
919 } else {
920 last->next = node_ptr->next;
921 }
922 _unlock_bucket(b);
923 return true;
924 }
925 last = node;
926 node = node->next;
927 }
928 _unlock_bucket(b);
929 return false;
930 }
931
932 template <typename Spec>
933 bool VMap<Spec>::find(VRef<K> key, VRef<V> &value) {
934 size_t hash = Spec::hash(key.as_ptr());
935 size_t b = hash & (_nbuckets - 1);
936 _lock_bucket(b);
937 VRef<Node> node = _buckets[b];
938 VRef<Node> last = vnull<Node>();
939 while (!node.is_null()) {
940 Node *node_ptr = node.as_ptr();
941 if (hash == node_ptr->hash
942 && Spec::equal(key.as_ptr(), node_ptr->key.as_ptr())) {
943 value = node_ptr->value;
944 // move to front
945 if (!last.is_null()) {
946 last->next = node_ptr->next;
947 node_ptr->next = _buckets[b];
948 }
949 _buckets[b] = node;
950 _unlock_bucket(b);
951 return true;
952 }
953 last = node;
954 node = node->next;
955 }
956 _unlock_bucket(b);
957 return false;
958 }
959
960 struct DictSpec {
961 typedef VString Key;
962 typedef VString Value;
963 static size_t hash(const VString *s) {
964 // DJB hash
965 size_t len = s->len();
966 const char *str = s->str();
967 size_t hash = 5381;
968 for (size_t i = 0; i < len; i++) {
969 hash = 33 * hash + str[i];
970 }
971 return hash;
972 }
973 static bool equal(const VString *s1, const VString *s2) {
974 if (s1->len() != s2->len())
975 return false;
976 size_t len = s1->len();
977 const char *str1 = s1->str(), *str2 = s2->str();
978 for (size_t i = 0; i < len; i++) {
979 if (str1[i] != str2[i])
980 return false;
981 }
982 return true;
983 }
984 // By default, we do not make assumptions about ownership. It is
985 // up to the caller to free keys and values if needed or to
986 // define appropriate `free_key()` and `free_value()` functions
987 // that work. Note in particular that keys and values may occur
988 // more than once in a map and if that happens, they must not
989 // be freed multiple times.
990 static void free_key(VRef<Key> key) {
991 // do nothing
992 }
993 static void free_value(VRef<Value> value) {
994 // do nothing
995 }
996 };
997
998 typedef VMap<DictSpec> VDict;
999
1000 pid_t fork_process();
1001
1002 #ifdef HAVE_CPP_THREADS
1003 typedef internals::FastLock FastLock;
1004 #else
1005 typedef internals::Mutex FastLock;
1006 #endif
1007
1008 typedef internals::Mutex Mutex;
1009
1010 class Semaphore {
1011 private:
1012 int _owner;
1013 int _waiting[internals::MAX_PROCESS + 1];
1014 internals::ipc_signal_t _signals[internals::MAX_PROCESS + 1];
1015 int _head, _tail;
1016 void next(int &index) {
1017 if (index == internals::MAX_PROCESS)
1018 index = 0;
1019 else
1020 index++;
1021 }
1022 size_t _value;
1023 FastLock _lock;
1024 bool _idle() {
1025 return _head == _tail;
1026 }
1027 template <typename T>
1028 friend class SyncVar;
1029
1030 public:
1031 Semaphore(size_t value = 0) :
1032 _owner(0), _head(0), _tail(0), _value(value), _lock() {
1033 }
1034 size_t value() {
1035 return _value;
1036 }
1037 void post();
1038 bool try_wait();
1039 void wait();
1040 bool start_wait(internals::ipc_signal_t sig = 0);
1041 bool stop_wait();
1042 };
1043
1044 template <typename T>
1045 class Queue {
1046 private:
1047 struct Node {
1048 VRef<Node> next;
1049 T data;
1050 };
1051 Semaphore _incoming;
1052 Semaphore _outgoing;
1053 bool _bounded;
1054 FastLock _lock;
1055 VRef<Node> _head, _tail;
1056 VRef<Node> pop() {
1057 VRef<Node> result = _head;
1058 if (_head->next.is_null()) {
1059 _head = _tail = vnull<Node>();
1060 } else {
1061 _head = _head->next;
1062 }
1063 return result;
1064 }
1065 void push(VRef<Node> node) {
1066 node->next = vnull<Node>();
1067 if (_tail.is_null()) {
1068 _head = _tail = node;
1069 } else {
1070 _tail->next = node;
1071 _tail = node;
1072 }
1073 }
1074 template <typename U>
1075 friend class EnqueueEvent;
1076 template <typename U>
1077 friend class DequeueEvent;
1078
1079 void enqueue_nowait(T item) {
1080 _lock.lock();
1081 VRef<Node> node = vnew<Node>();
1082 node->data = item;
1083 push(node);
1084 _lock.unlock();
1085 _incoming.post();
1086 }
1087 T dequeue_nowait() {
1088 _lock.lock();
1089 VRef<Node> node = pop();
1090 T result;
1091 result = node->data;
1092 node.free();
1093 _lock.unlock();
1094 if (_bounded)
1095 _outgoing.post();
1096 return result;
1097 }
1098
1099 public:
1100 Queue(size_t bound = 0) :
1101 _incoming(0),
1102 _outgoing(bound),
1103 _bounded(bound != 0),
1104 _head(),
1105 _tail(),
1106 _lock() {
1107 }
1108 void enqueue(T item) {
1109 if (_bounded)
1110 _outgoing.wait();
1111 enqueue_nowait(item);
1112 }
1113 bool try_enqueue(T item) {
1114 if (_bounded && _outgoing.try_wait()) {
1115 enqueue_nowait(item);
1116 return true;
1117 } else {
1118 return false;
1119 }
1120 }
1121 T dequeue() {
1122 _incoming.wait();
1123 return dequeue_nowait();
1124 }
1125 Result<T> try_dequeue() {
1126 if (_incoming.try_wait())
1127 return Result<T>(dequeue_nowait());
1128 else
1129 return Result<T>();
1130 }
1131 };
1132
1133 template <typename T>
1134 class SyncVar {
1135 private:
1136 FastLock _lock;
1137 VRef<Semaphore> _sem;
1138 bool _set;
1139 T _value;
1140 template <typename U>
1141 friend class SyncReadEvent;
1142 bool start_wait(internals::ipc_signal_t sig);
1143 void stop_wait();
1144 public:
1145 SyncVar() : _set(false) { }
1146 T read();
1147 Result<T> try_read();
1148 bool write(T value);
1149 bool test() {
1150 return _set;
1151 }
1152 };
1153
1154 template <typename T>
1155 bool SyncVar<T>::start_wait(internals::ipc_signal_t sig) {
1156 _lock.lock();
1157 if (_set) {
1158 internals::send_signal(internals::vmem.current_process, sig);
1159 _lock.unlock();
1160 return true;
1161 }
1162 if (_sem.is_null()) {
1163 _sem = vnew<Semaphore>();
1164 }
1165 bool result = _sem->start_wait(sig);
1166 _lock.unlock();
1167 return result;
1168 }
1169
1170 template <typename T>
1171 void SyncVar<T>::stop_wait() {
1172 _lock.lock();
1173 if (!_sem.is_null()) {
1174 _sem->stop_wait();
1175 if (!_sem->_idle())
1176 _sem->post();
1177 }
1178 _lock.unlock();
1179 }
1180
1181 template <typename T>
1182 T SyncVar<T>::read() {
1183 _lock.lock();
1184 if (_set) {
1185 _lock.unlock();
1186 return _value;
1187 }
1188 if (_sem.is_null()) {
1189 _sem = vnew<Semaphore>();
1190 }
1191 // We can't wait inside the lock without deadlocking; but waiting outside
1192 // could cause a race condition with _sem being freed due to being idle.
1193 // Thus, we use start_wait() to insert ourselves into the queue, then
1194 // use wait_signal() outside the lock to complete waiting.
1195 //
1196 // Note: start_wait() will not send a signal to self, as _set is
1197 // false and therefore _sem->value() must be zero.
1198 _sem->start_wait(0);
1199 _lock.unlock();
1200 internals::wait_signal();
1201 _lock.lock();
1202 if (_sem->_idle())
1203 _sem->post();
1204 else {
1205 _sem.free();
1206 _sem = vnull<Semaphore>();
1207 }
1208 _lock.unlock();
1209 return _value;
1210 }
1211
1212 template <typename T>
1213 Result<T> SyncVar<T>::try_read() {
1214 _lock.lock();
1215 Result<T> result = _set ? Result<T>(_value) : Result<T>();
1216 _lock.unlock();
1217 return result;
1218 }
1219
1220 template <typename T>
1221 bool SyncVar<T>::write(T value) {
1222 _lock.lock();
1223 if (_set) {
1224 _lock.unlock();
1225 return false;
1226 }
1227 _set = true;
1228 _value = value;
1229 if (!_sem->_idle())
1230 _sem->post();
1231 _lock.unlock();
1232 return true;
1233 }
1234
1235 class Event {
1236 private:
1237 Event *_next;
1238 friend class EventSet;
1239 public:
1240 virtual bool start_listen(internals::ipc_signal_t sig) = 0;
1241 virtual void stop_listen() = 0;
1242 };
1243
1244 class EventSet {
1245 private:
1246 Event *_head, *_tail;
1247
1248 public:
1249 EventSet() : _head(NULL), _tail(NULL) {
1250 }
1251 void add(Event *event);
1252 void add(Event &event) {
1253 add(&event);
1254 }
1255 EventSet &operator<<(Event *event) {
1256 add(event);
1257 return *this;
1258 }
1259 EventSet &operator<<(Event &event) {
1260 add(event);
1261 return *this;
1262 }
1263 int wait();
1264 };
1265
1266 class WaitSemaphoreEvent : public Event {
1267 private:
1268 VRef<Semaphore> _sem;
1269
1270 public:
1271 WaitSemaphoreEvent(VRef<Semaphore> sem) : _sem(sem) {
1272 }
1273 virtual bool start_listen(internals::ipc_signal_t sig) {
1274 return _sem->start_wait(sig);
1275 }
1276 virtual void stop_listen() {
1277 _sem->stop_wait();
1278 }
1279 void complete() {
1280 }
1281 };
1282
1283 template <typename T>
1284 class EnqueueEvent : public Event {
1285 private:
1286 VRef<Queue<T> > _queue;
1287
1288 public:
1289 EnqueueEvent(VRef<Queue<T> > queue) : _queue(queue) {
1290 }
1291 virtual bool start_listen(internals::ipc_signal_t sig) {
1292 return _queue->_outgoing.start_wait(sig);
1293 }
1294 virtual void stop_listen() {
1295 _queue->_outgoing.stop_wait();
1296 }
1297 void complete(T item) {
1298 _queue->enqueue_nowait(item);
1299 }
1300 };
1301
1302 template <typename T>
1303 class DequeueEvent : public Event {
1304 private:
1305 VRef<Queue<T> > _queue;
1306
1307 public:
1308 DequeueEvent(VRef<Queue<T> > queue) : _queue(queue) {
1309 }
1310 virtual bool start_listen(internals::ipc_signal_t sig) {
1311 return _queue->_incoming.start_wait(sig);
1312 }
1313 virtual void stop_listen() {
1314 _queue->_incoming.stop_wait();
1315 }
1316 T complete() {
1317 return _queue->dequeue_nowait();
1318 }
1319 };
1320
1321 template <typename T>
1322 class SyncReadEvent : public Event {
1323 private:
1324 VRef<SyncVar<T> > _syncvar;
1325
1326 public:
1327 SyncReadEvent(VRef<SyncVar<T> > syncvar) : _syncvar(syncvar) {
1328 }
1329 virtual bool start_listen(internals::ipc_signal_t sig) {
1330 return _syncvar->start_wait(sig);
1331 }
1332 virtual void stop_listen() {
1333 _syncvar->stop_wait();
1334 }
1335 T complete() {
1336 return _syncvar->read();
1337 }
1338 };
1339
1340 }; // namespace vspace
1341 #endif
1342 #endif
1343