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 
9 namespace vspace {
10 namespace internals {
11 
12 size_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 
23 size_t VMem::filesize() {
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  }
45  lock_metapage();
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;
57  current_process = 0;
58  file_handle = fp;
59  metapage->process_info[0].pid = getpid();
60  return Status(ErrNone);
61 }
62 
63 Status 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);
68  lock_metapage();
69  // TODO: enter process in meta table
71  return Status(ErrNone);
72 }
73 
74 void VMem::deinit() {
75  if (file_handle) {
76  fclose(file_handle);
77  file_handle = NULL;
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 
95 void *VMem::mmap_segment(int seg) {
96  lock_metapage();
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  }
105  unlock_metapage();
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 
159 static void lock_allocator() {
161 }
162 
163 static void unlock_allocator() {
165 }
166 
167 static 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 
195 void vmem_free(vaddr_t vaddr) {
196  lock_allocator();
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 
244  lock_allocator();
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) {
251  vmem.add_segment();
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)
278  vmem.block_ptr(block->next)->prev = 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 
294 void 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 
300 void 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 
314 void init_metapage(bool create) {
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  }
325  vmem.metapage->allocator_lock = FastLock(metapageaddr(allocator_lock));
326  } else {
327  assert(memcmp(vmem.metapage->config_header, config, sizeof(config)) != 0);
328  }
329 }
330 
331 static void lock_process(int processno) {
332  lock_file(vmem.fd,
334  + sizeof(ProcessInfo) * vmem.current_process);
335 }
336 
337 static void unlock_process(int processno) {
340  + sizeof(ProcessInfo) * vmem.current_process);
341 }
342 
343 static ProcessInfo &process_info(int processno) {
344  return vmem.metapage->process_info[processno];
345 }
346 
347 bool 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 
370 ipc_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 
419 pid_t fork_process() {
420  using namespace internals;
421  lock_metapage();
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;
432  lock_metapage();
433  vmem.metapage->process_info[p].pid = getpid();
434  unlock_metapage();
435  send_signal(parent);
436  } else {
437  // parent process
438  unlock_metapage();
439  wait_signal();
440  // child has unlocked metapage, so we don't need to.
441  }
442  return pid;
443  }
444  }
445  unlock_metapage();
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) {
515  _waiting[last] = _waiting[i];
516  _signals[last] = _signals[i];
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 
529 void 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
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:4078
CanonicalForm fp
Definition: cfModGcd.cc:4102
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
STATIC_VAR poly last
Definition: hdegree.cc:1151
STATIC_VAR int offset
Definition: janet.cc:29
NodeM * create()
Definition: janet.cc:757
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
Block * block_ptr(vaddr_t vaddr)
Definition: vspace.h:302
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
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
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 ProcessInfo & process_info(int processno)
Definition: vspace.cc:343
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 NULL
Definition: omList.c:12
#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 * buf
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
size_t segment_no(vaddr_t vaddr)
Definition: vspace.h:263
void * mmap_segment(int seg)
Definition: vspace.cc:95
Block * block_ptr(vaddr_t vaddr)
Definition: vspace.h:274
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