My Project
vspace.cc
Go to the documentation of this file.
1// https://github.com/rbehrends/vspace
2#include "vspace.h"
3#include "kernel/mod2.h"
4#ifdef HAVE_VSPACE
5#ifdef HAVE_CPP_THREADS
6#include <thread>
7#endif
8
9namespace vspace {
10namespace internals {
11
12size_t config[4]
14
16
17// offsetof() only works for POD types, so we need to construct
18// a portable version of it for metapage fields.
19
20#define metapageaddr(field) \
21 ((char *) &vmem.metapage->field - (char *) vmem.metapage)
22
24 struct stat stat;
25 fstat(fd, &stat);
26 return stat.st_size;
27}
28
30 this->fd = fd;
31 for (int i = 0; i < MAX_SEGMENTS; i++)
32 segments[i] = VSeg(NULL);
33 for (int i = 0; i < MAX_PROCESS; i++) {
34 int channel[2];
35 if (pipe(channel) < 0) {
36 for (int j = 0; j < i; j++) {
37 close(channels[j].fd_read);
38 close(channels[j].fd_write);
39 }
40 return Status(ErrOS);
41 }
42 channels[i].fd_read = channel[0];
43 channels[i].fd_write = channel[1];
44 }
46 init_metapage(filesize() == 0);
49 return Status(ErrNone);
50}
51
53 FILE *fp = tmpfile();
54 Status result = init(fileno(fp));
55 if (!result.ok())
56 return result;
59 metapage->process_info[0].pid = getpid();
60 return Status(ErrNone);
61}
62
63Status VMem::init(const char *path) {
64 int fd = open(path, O_RDWR | O_CREAT, 0600);
65 if (fd < 0)
66 return Status(ErrFile);
67 init(fd);
69 // TODO: enter process in meta table
71 return Status(ErrNone);
72}
73
75 if (file_handle) {
76 fclose(file_handle);
78 } else {
79 close(fd);
80 }
81 munmap(metapage, METABLOCK_SIZE);
82 metapage = NULL;
83 current_process = -1;
84 freelist = NULL;
85 for (int i = 0; i < MAX_SEGMENTS; i++) {
86 if (segments[i].base) munmap(segments[i].base, SEGMENT_SIZE);
87 segments[i] = NULL;
88 }
89 for (int i = 0; i < MAX_PROCESS; i++) {
90 close(channels[i].fd_read);
91 close(channels[i].fd_write);
92 }
93}
94
95void *VMem::mmap_segment(int seg) {
97 void *map = mmap(NULL, SEGMENT_SIZE, PROT_READ | PROT_WRITE, MAP_SHARED, fd,
99 if (map == MAP_FAILED) {
100 // This is an "impossible to proceed from here, because system state
101 // is impossible to proceed from" situation, so we abort the program.
102 perror("mmap");
103 abort();
104 }
106 return map;
107}
108
110 int seg = metapage->segment_count++;
112 void *map_addr = mmap_segment(seg);
113 segments[seg] = VSeg(map_addr);
114 Block *top = block_ptr(seg * SEGMENT_SIZE);
116 top->prev = VADDR_NULL;
118}
119
121#ifdef HAVE_CPP_THREADS
122 while (_lock.test_and_set()) {
123 }
124 bool empty = _owner < 0;
125 if (empty) {
126 _owner = vmem.current_process;
127 } else {
128 int p = vmem.current_process;
129 vmem.metapage->process_info[p].next = -1;
130 if (_head < 0)
131 _head = p;
132 else
133 vmem.metapage->process_info[_tail].next = p;
134 _tail = p;
135 }
136 _lock.clear();
137 if (!empty)
138 wait_signal(false);
139#else
141#endif
142}
143
145#ifdef HAVE_CPP_THREADS
146 while (_lock.test_and_set()) {
147 }
148 _owner = _head;
149 if (_owner >= 0)
150 _head = vmem.metapage->process_info[_head].next;
151 _lock.clear();
152 if (_owner >= 0)
153 send_signal(_owner, 0, false);
154#else
156#endif
157}
158
159static void lock_allocator() {
161}
162
163static void unlock_allocator() {
165}
166
167static void print_freelists() {
168 for (int i = 0; i <= LOG2_SEGMENT_SIZE; i++) {
169 vaddr_t vaddr = vmem.freelist[i];
170 if (vaddr != VADDR_NULL) {
171 printf("%2d: %ld", i, vaddr);
172 vaddr_t prev = block_ptr(vaddr)->prev;
173 if (prev != VADDR_NULL) {
174 printf("(%ld)", prev);
175 }
176 assert(block_ptr(vaddr)->prev == VADDR_NULL);
177 for (;;) {
178 vaddr_t last_vaddr = vaddr;
179 Block *block = block_ptr(vaddr);
180 vaddr = block->next;
181 if (vaddr == VADDR_NULL)
182 break;
183 printf(" -> %ld", vaddr);
184 vaddr_t prev = block_ptr(vaddr)->prev;
185 if (prev != last_vaddr) {
186 printf("(%ld)", prev);
187 }
188 }
189 printf("\n");
190 }
191 }
192 fflush(stdout);
193}
194
195void vmem_free(vaddr_t vaddr) {
197 vaddr -= offsetof(Block, data);
198 vmem.ensure_is_mapped(vaddr);
199 size_t segno = vmem.segment_no(vaddr);
200 VSeg seg = vmem.segment(vaddr);
201 segaddr_t addr = vmem.segaddr(vaddr);
202 int level = seg.block_ptr(addr)->level();
203 assert(!seg.is_free(addr));
204 while (level < LOG2_SEGMENT_SIZE) {
205 segaddr_t buddy = find_buddy(addr, level);
206 Block *block = seg.block_ptr(buddy);
207 // is buddy free and at the same level?
208 if (!block->is_free() || block->level() != level)
209 break;
210 // remove buddy from freelist.
211 Block *prev = vmem.block_ptr(block->prev);
212 Block *next = vmem.block_ptr(block->next);
213 block->data[0] = level;
214 if (prev) {
215 assert(prev->next == vmem.vaddr(segno, buddy));
216 prev->next = block->next;
217 } else {
218 // head of freelist.
219 assert(vmem.freelist[level] == vmem.vaddr(segno, buddy));
220 vmem.freelist[level] = block->next;
221 }
222 if (next) {
223 assert(next->prev == vmem.vaddr(segno, buddy));
224 next->prev = block->prev;
225 }
226 // coalesce block with buddy
227 level++;
228 if (buddy < addr)
229 addr = buddy;
230 }
231 // Add coalesced block to free list
232 Block *block = seg.block_ptr(addr);
233 block->prev = VADDR_NULL;
234 block->next = vmem.freelist[level];
235 block->mark_as_free(level);
236 vaddr_t blockaddr = vmem.vaddr(segno, addr);
237 if (block->next != VADDR_NULL)
238 vmem.block_ptr(block->next)->prev = blockaddr;
239 vmem.freelist[level] = blockaddr;
241}
242
245 size_t alloc_size = size + offsetof(Block, data);
246 int level = find_level(alloc_size);
247 int flevel = level;
248 while (flevel < LOG2_SEGMENT_SIZE && vmem.freelist[flevel] == VADDR_NULL)
249 flevel++;
250 if (vmem.freelist[flevel] == VADDR_NULL) {
252 }
254 while (flevel > level) {
255 // get and split a block
256 vaddr_t blockaddr = vmem.freelist[flevel];
257 assert((blockaddr & ((1 << flevel) - 1)) == 0);
258 Block *block = vmem.block_ptr(blockaddr);
259 vmem.freelist[flevel] = block->next;
260 if (vmem.freelist[flevel] != VADDR_NULL)
262 vaddr_t blockaddr2 = blockaddr + (1 << (flevel - 1));
263 Block *block2 = vmem.block_ptr(blockaddr2);
264 flevel--;
265 block2->next = vmem.freelist[flevel];
266 block2->prev = blockaddr;
267 block->next = blockaddr2;
268 block->prev = VADDR_NULL;
269 // block->prev == VADDR_NULL already.
270 vmem.freelist[flevel] = blockaddr;
271 }
274 vaddr_t vaddr = vmem.freelist[level];
275 vaddr_t result = vaddr + offsetof(Block, data);
276 vmem.freelist[level] = block->next;
277 if (block->next != VADDR_NULL)
279 block->mark_as_allocated(vaddr, level);
281 memset(block->data, 0, size);
282 return result;
283}
284
286 struct flock &lock_info, size_t offset, size_t len, bool lock) {
287 lock_info.l_start = offset;
288 lock_info.l_len = len;
289 lock_info.l_pid = 0;
290 lock_info.l_type = lock ? F_WRLCK : F_UNLCK;
291 lock_info.l_whence = SEEK_SET;
292}
293
294void lock_file(int fd, size_t offset, size_t len) {
295 struct flock lock_info;
296 init_flock_struct(lock_info, offset, len, true);
297 fcntl(fd, F_SETLKW, &lock_info);
298}
299
300void unlock_file(int fd, size_t offset, size_t len) {
301 struct flock lock_info;
302 init_flock_struct(lock_info, offset, len, false);
303 fcntl(fd, F_SETLKW, &lock_info);
304}
305
307 lock_file(vmem.fd, 0);
308}
309
311 unlock_file(vmem.fd, 0);
312}
313
315 if (create)
316 ftruncate(vmem.fd, METABLOCK_SIZE);
317 vmem.metapage = (MetaPage *) mmap(
318 NULL, METABLOCK_SIZE, PROT_READ | PROT_WRITE, MAP_SHARED, vmem.fd, 0);
319 if (create) {
320 memcpy(vmem.metapage->config_header, config, sizeof(config));
321 for (int i = 0; i <= LOG2_SEGMENT_SIZE; i++) {
323 }
326 } else {
327 assert(memcmp(vmem.metapage->config_header, config, sizeof(config)) != 0);
328 }
329}
330
331static void lock_process(int processno) {
334 + sizeof(ProcessInfo) * vmem.current_process);
335}
336
337static void unlock_process(int processno) {
340 + sizeof(ProcessInfo) * vmem.current_process);
341}
342
343static ProcessInfo &process_info(int processno) {
344 return vmem.metapage->process_info[processno];
345}
346
347bool send_signal(int processno, ipc_signal_t sig, bool lock) {
348 if (lock)
349 lock_process(processno);
350 if (process_info(processno).sigstate != Waiting) {
351 unlock_process(processno);
352 return false;
353 }
354 if (processno == vmem.current_process) {
355 process_info(processno).sigstate = Accepted;
356 process_info(processno).signal = sig;
357 } else {
358 process_info(processno).sigstate = Pending;
359 process_info(processno).signal = sig;
360 int fd = vmem.channels[processno].fd_write;
361 char buf[1] = { 0 };
362 while (write(fd, buf, 1) != 1) {
363 }
364 }
365 if (lock)
366 unlock_process(processno);
367 return true;
368}
369
370ipc_signal_t check_signal(bool resume, bool lock) {
372 if (lock)
375 switch (sigstate) {
376 case Waiting:
377 case Pending: {
379 char buf[1];
380 if (lock && sigstate == Waiting) {
382 while (read(fd, buf, 1) != 1) {
383 }
385 } else {
386 while (read(fd, buf, 1) != 1) {
387 }
388 }
391 = resume ? Waiting : Accepted;
392 if (lock)
394 break;
395 }
396 case Accepted:
398 if (resume)
400 if (lock)
402 break;
403 }
404 return result;
405}
406
411}
412
414 return check_signal(true, lock);
415}
416
417} // namespace internals
418
420 using namespace internals;
422 for (int p = 0; p < MAX_PROCESS; p++) {
423 if (vmem.metapage->process_info[p].pid == 0) {
424 pid_t pid = fork();
425 if (pid < 0) {
426 // error
427 return -1;
428 } else if (pid == 0) {
429 // child process
430 int parent = vmem.current_process;
433 vmem.metapage->process_info[p].pid = getpid();
435 send_signal(parent);
436 } else {
437 // parent process
439 wait_signal();
440 // child has unlocked metapage, so we don't need to.
441 }
442 return pid;
443 }
444 }
446 return -1;
447}
448
450 int wakeup = -1;
452 _lock.lock();
453 if (_head == _tail) {
454 _value++;
455 } else {
456 // don't increment value, as we'll pass that on to the next process.
457 wakeup = _waiting[_head];
458 sig = _signals[_head];
459 next(_head);
460 }
461 _lock.unlock();
462 if (wakeup >= 0) {
463 internals::send_signal(wakeup, sig);
464 }
465}
466
468 bool result = false;
469 _lock.lock();
470 if (_value > 0) {
471 _value--;
472 result = true;
473 }
474 _lock.unlock();
475 return result;
476}
477
479 _lock.lock();
480 if (_value > 0) {
481 _value--;
482 _lock.unlock();
483 return;
484 }
486 _signals[_tail] = 0;
487 next(_tail);
488 _lock.unlock();
490}
491
493 _lock.lock();
494 if (_value > 0) {
495 if (internals::send_signal(internals::vmem.current_process, sig))
496 _value--;
497 _lock.unlock();
498 return false;
499 }
501 _signals[_tail] = sig;
502 next(_tail);
503 _lock.unlock();
504 return true;
505}
506
508 bool result = false;
509 _lock.lock();
510 for (int i = _head; i != _tail; next(i)) {
511 if (_waiting[i] == internals::vmem.current_process) {
512 int last = i;
513 next(i);
514 while (i != _tail) {
517 last = i;
518 next(i);
519 }
520 _tail = last;
521 result = true;
522 break;
523 }
524 }
525 _lock.unlock();
526 return result;
527}
528
529void EventSet::add(Event *event) {
530 event->_next = NULL;
531 if (_head == NULL) {
532 _head = _tail = event;
533 } else {
534 _tail->_next = event;
535 _tail = event;
536 }
537}
538
540 size_t n = 0;
541 for (Event *event = _head; event; event = event->_next) {
542 if (!event->start_listen((int) (n++))) {
543 break;
544 }
545 }
547 for (Event *event = _head; event; event = event->_next) {
548 event->stop_listen();
549 }
551 return (int) result;
552}
553
554} // namespace vspace
555#endif
#define NULL
Definition: auxiliary.h:104
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
int p
Definition: cfModGcd.cc:4080
CanonicalForm fp
Definition: cfModGcd.cc:4104
CanonicalForm map(const CanonicalForm &primElem, const Variable &alpha, const CanonicalForm &F, const Variable &beta)
map from to such that is mapped onto
Definition: cf_map_ext.cc:504
void add(Event *event)
Definition: vspace.cc:529
Event * _head
Definition: vspace.h:1246
Event * _tail
Definition: vspace.h:1246
Event * _next
Definition: vspace.h:1237
int _waiting[internals::MAX_PROCESS+1]
Definition: vspace.h:1013
void next(int &index)
Definition: vspace.h:1016
bool start_wait(internals::ipc_signal_t sig=0)
Definition: vspace.cc:492
internals::ipc_signal_t _signals[internals::MAX_PROCESS+1]
Definition: vspace.h:1014
FastLock _lock
Definition: vspace.h:1023
bool try_wait()
Definition: vspace.cc:467
bool stop_wait()
Definition: vspace.cc:507
return result
Definition: facAbsBiFact.cc:75
int j
Definition: facHensel.cc:110
fq_nmod_t buf
Definition: facHensel.cc:101
STATIC_VAR poly last
Definition: hdegree.cc:1150
NodeM * create()
Definition: janet.cc:757
STATIC_VAR int offset
Definition: janet.cc:29
ListNode * next
Definition: janet.h:31
#define SEEK_SET
Definition: mod2.h:113
char N base
Definition: ValueTraits.h:144
void accept_signals()
Definition: vspace.cc:407
void unlock_metapage()
Definition: vspace.cc:310
const vaddr_t VADDR_NULL
Definition: vspace.h:84
void init_flock_struct(struct flock &lock_info, size_t offset, size_t len, bool lock)
Definition: vspace.cc:285
size_t vaddr_t
Definition: vspace.h:81
static ProcessInfo & process_info(int processno)
Definition: vspace.cc:343
void lock_file(int fd, size_t offset, size_t len)
Definition: vspace.cc:294
void vmem_free(vaddr_t vaddr)
Definition: vspace.cc:195
Block * block_ptr(vaddr_t vaddr)
Definition: vspace.h:302
vaddr_t vmem_alloc(size_t size)
Definition: vspace.cc:243
static void unlock_process(int processno)
Definition: vspace.cc:337
static const size_t MAX_SEGMENTS
Definition: vspace.h:90
vaddr_t freelist[LOG2_SEGMENT_SIZE+1]
Definition: vspace.h:178
static const size_t SEGMENT_SIZE
Definition: vspace.h:91
static const size_t METABLOCK_SIZE
Definition: vspace.h:87
static void lock_process(int processno)
Definition: vspace.cc:331
static const int LOG2_SEGMENT_SIZE
Definition: vspace.h:88
ipc_signal_t wait_signal(bool lock)
Definition: vspace.cc:413
void lock_metapage()
Definition: vspace.cc:306
static const int MAX_PROCESS
Definition: vspace.h:86
static VMem & vmem
Definition: vspace.h:300
ProcessInfo process_info[MAX_PROCESS]
Definition: vspace.h:180
static void lock_allocator()
Definition: vspace.cc:159
static segaddr_t find_buddy(segaddr_t addr, int level)
Definition: vspace.h:355
ipc_signal_t check_signal(bool resume, bool lock)
Definition: vspace.cc:370
void init_metapage(bool create)
Definition: vspace.cc:314
void unlock_file(int fd, size_t offset, size_t len)
Definition: vspace.cc:300
bool send_signal(int processno, ipc_signal_t sig, bool lock)
Definition: vspace.cc:347
static int find_level(size_t size)
Definition: vspace.h:346
size_t config[4]
Definition: vspace.cc:13
size_t segaddr_t
Definition: vspace.h:79
static void unlock_allocator()
Definition: vspace.cc:163
static void print_freelists()
Definition: vspace.cc:167
Definition: vspace.cc:9
pid_t fork_process()
Definition: vspace.cc:419
@ ErrOS
Definition: vspace.h:47
@ ErrNone
Definition: vspace.h:43
@ ErrFile
Definition: vspace.h:45
internals::Mutex FastLock
Definition: vspace.h:1005
#define block
Definition: scanner.cc:666
int status int void size_t count write
Definition: si_signals.h:67
int status read
Definition: si_signals.h:59
int status int void size_t count int const void size_t count open
Definition: si_signals.h:73
int status int fd
Definition: si_signals.h:59
void ensure_is_mapped(vaddr_t vaddr)
Definition: vspace.h:279
Block * block_ptr(vaddr_t vaddr)
Definition: vspace.h:274
size_t segment_no(vaddr_t vaddr)
Definition: vspace.h:263
void * mmap_segment(int seg)
Definition: vspace.cc:95
VSeg segment(vaddr_t vaddr)
Definition: vspace.h:260
MetaPage * metapage
Definition: vspace.h:253
static VMem vmem_global
Definition: vspace.h:252
vaddr_t * freelist
Definition: vspace.h:257
VSeg segments[MAX_SEGMENTS]
Definition: vspace.h:258
vaddr_t vaddr(size_t segno, segaddr_t addr)
Definition: vspace.h:266
segaddr_t segaddr(vaddr_t vaddr)
Definition: vspace.h:269
ProcessChannel channels[MAX_PROCESS]
Definition: vspace.h:259
Block * block_ptr(segaddr_t addr)
Definition: vspace.h:235
bool is_free(segaddr_t addr)
Definition: vspace.h:238
#define assert(A)
Definition: svd_si.h:3
#define metapageaddr(field)
Definition: vspace.cc:20