Loading...
Searching...
No Matches
vspace.cc
Go to the documentation of this file.
// https://github.com/rbehrends/vspace
#include "vspace.h"
#include "kernel/mod2.h"
#ifdef HAVE_VSPACE
#ifdef HAVE_CPP_THREADS
#include <thread>
#endif
#ifdef HAVE_POLL
#include <poll.h>
#endif
#include <cstddef>
#include "reporter/si_signals.h"
#if defined(__GNUC__) && (__GNUC__<9) &&!defined(__clang__)
namespace vspace {
namespace internals {
size_t config[4]
= { METABLOCK_SIZE, MAX_PROCESS, SEGMENT_SIZE, MAX_SEGMENTS };
VMem VMem::vmem_global;
// offsetof() only works for POD types, so we need to construct
// a portable version of it for metapage fields.
#define metapageaddr(field) \
((char *) &vmem.metapage->field - (char *) vmem.metapage)
size_t VMem::filesize() {
struct stat stat;
fstat(fd, &stat);
return stat.st_size;
}
Status VMem::init(int fd) {
this->fd = fd;
for (int i = 0; i < MAX_SEGMENTS; i++)
segments[i] = VSeg(NULL);
for (int i = 0; i < MAX_PROCESS; i++) {
int channel[2];
if (pipe(channel) < 0) {
for (int j = 0; j < i; j++) {
close(channels[j].fd_read);
close(channels[j].fd_write);
}
return Status(ErrOS);
}
channels[i].fd_read = channel[0];
channels[i].fd_write = channel[1];
}
lock_metapage();
init_metapage(filesize() == 0);
unlock_metapage();
freelist = metapage->freelist;
return Status(ErrNone);
}
Status VMem::init() {
FILE *fp = tmpfile();
Status result = init(fileno(fp));
if (!result.ok())
return result;
current_process = 0;
file_handle = fp;
metapage->process_info[0].pid = getpid();
return Status(ErrNone);
}
Status VMem::init(const char *path) {
int fd = open(path, O_RDWR | O_CREAT, 0600);
if (fd < 0)
return Status(ErrFile);
init(fd);
lock_metapage();
// TODO: enter process in meta table
unlock_metapage();
return Status(ErrNone);
}
void VMem::deinit() {
if (file_handle) {
fclose(file_handle);
file_handle = NULL;
} else {
close(fd);
}
munmap(metapage, METABLOCK_SIZE);
metapage = NULL;
current_process = -1;
freelist = NULL;
for (int i = 0; i < MAX_SEGMENTS; i++) {
if (segments[i].base) munmap(segments[i].base, SEGMENT_SIZE);
segments[i] = NULL;
}
for (int i = 0; i < MAX_PROCESS; i++) {
close(channels[i].fd_read);
close(channels[i].fd_write);
}
}
void *VMem::mmap_segment(int seg) {
lock_metapage();
void *map = mmap(NULL, SEGMENT_SIZE, PROT_READ | PROT_WRITE, MAP_SHARED, fd,
METABLOCK_SIZE + seg * SEGMENT_SIZE);
if (map == MAP_FAILED) {
// This is an "impossible to proceed from here, because system state
// is impossible to proceed from" situation, so we abort the program.
perror("mmap");
abort();
}
unlock_metapage();
return map;
}
void VMem::add_segment() {
int seg = metapage->segment_count++;
ftruncate(fd, METABLOCK_SIZE + metapage->segment_count * SEGMENT_SIZE);
void *map_addr = mmap_segment(seg);
segments[seg] = VSeg(map_addr);
Block *top = block_ptr(seg * SEGMENT_SIZE);
top->next = freelist[LOG2_SEGMENT_SIZE];
top->prev = VADDR_NULL;
freelist[LOG2_SEGMENT_SIZE] = seg * SEGMENT_SIZE;
}
void FastLock::lock() {
#ifdef HAVE_CPP_THREADS
while (_lock.test_and_set()) {
}
bool empty = _owner < 0;
if (empty) {
_owner = vmem.current_process;
} else {
int p = vmem.current_process;
vmem.metapage->process_info[p].next = -1;
if (_head < 0)
_head = p;
else
vmem.metapage->process_info[_tail].next = p;
_tail = p;
}
_lock.clear();
if (!empty)
wait_signal(false);
#else
lock_file(vmem.fd, _offset);
#endif
}
void FastLock::unlock() {
#ifdef HAVE_CPP_THREADS
while (_lock.test_and_set()) {
}
_owner = _head;
if (_owner >= 0)
_head = vmem.metapage->process_info[_head].next;
_lock.clear();
if (_owner >= 0)
send_signal(_owner, 0, false);
#else
unlock_file(vmem.fd, _offset);
#endif
}
static void lock_allocator() {
vmem.metapage->allocator_lock.lock();
}
static void unlock_allocator() {
vmem.metapage->allocator_lock.unlock();
}
static void print_freelists() {
for (int i = 0; i <= LOG2_SEGMENT_SIZE; i++) {
vaddr_t vaddr = vmem.freelist[i];
if (vaddr != VADDR_NULL) {
printf("%2d: %ld", i, (long)vaddr);
vaddr_t prev = block_ptr(vaddr)->prev;
if (prev != VADDR_NULL) {
printf("(%ld)", (long)prev);
}
assert(block_ptr(vaddr)->prev == VADDR_NULL);
for (;;) {
vaddr_t last_vaddr = vaddr;
Block *block = block_ptr(vaddr);
vaddr = block->next;
if (vaddr == VADDR_NULL)
break;
printf(" -> %ld", (long)vaddr);
vaddr_t prev = block_ptr(vaddr)->prev;
if (prev != last_vaddr) {
printf("(%ld)", (long)prev);
}
}
printf("\n");
}
}
fflush(stdout);
}
void vmem_free(vaddr_t vaddr) {
lock_allocator();
vaddr -= offsetof(Block, data);
vmem.ensure_is_mapped(vaddr);
size_t segno = vmem.segment_no(vaddr);
VSeg seg = vmem.segment(vaddr);
segaddr_t addr = vmem.segaddr(vaddr);
int level = seg.block_ptr(addr)->level();
assert(!seg.is_free(addr));
while (level < LOG2_SEGMENT_SIZE) {
segaddr_t buddy = find_buddy(addr, level);
Block *block = seg.block_ptr(buddy);
// is buddy free and at the same level?
if (!block->is_free() || block->level() != level)
break;
// remove buddy from freelist.
Block *prev = vmem.block_ptr(block->prev);
Block *next = vmem.block_ptr(block->next);
block->data[0] = level;
if (prev) {
assert(prev->next == vmem.vaddr(segno, buddy));
prev->next = block->next;
} else {
// head of freelist.
assert(vmem.freelist[level] == vmem.vaddr(segno, buddy));
vmem.freelist[level] = block->next;
}
if (next) {
assert(next->prev == vmem.vaddr(segno, buddy));
next->prev = block->prev;
}
// coalesce block with buddy
level++;
if (buddy < addr)
addr = buddy;
}
// Add coalesced block to free list
Block *block = seg.block_ptr(addr);
block->prev = VADDR_NULL;
block->next = vmem.freelist[level];
block->mark_as_free(level);
vaddr_t blockaddr = vmem.vaddr(segno, addr);
if (block->next != VADDR_NULL)
vmem.block_ptr(block->next)->prev = blockaddr;
vmem.freelist[level] = blockaddr;
unlock_allocator();
}
vaddr_t vmem_alloc(size_t size) {
lock_allocator();
size_t alloc_size = size + offsetof(Block, data);
int level = find_level(alloc_size);
int flevel = level;
while (flevel < LOG2_SEGMENT_SIZE && vmem.freelist[flevel] == VADDR_NULL)
flevel++;
if (vmem.freelist[flevel] == VADDR_NULL) {
vmem.add_segment();
}
vmem.ensure_is_mapped(vmem.freelist[flevel]);
while (flevel > level) {
// get and split a block
vaddr_t blockaddr = vmem.freelist[flevel];
assert((blockaddr & ((1 << flevel) - 1)) == 0);
Block *block = vmem.block_ptr(blockaddr);
vmem.freelist[flevel] = block->next;
if (vmem.freelist[flevel] != VADDR_NULL)
vmem.block_ptr(vmem.freelist[flevel])->prev = VADDR_NULL;
vaddr_t blockaddr2 = blockaddr + (1 << (flevel - 1));
Block *block2 = vmem.block_ptr(blockaddr2);
flevel--;
block2->next = vmem.freelist[flevel];
block2->prev = blockaddr;
block->next = blockaddr2;
block->prev = VADDR_NULL;
// block->prev == VADDR_NULL already.
vmem.freelist[flevel] = blockaddr;
}
assert(vmem.freelist[level] != VADDR_NULL);
Block *block = vmem.block_ptr(vmem.freelist[level]);
vaddr_t vaddr = vmem.freelist[level];
#if defined(__GNUC__) && (__GNUC__>11)
vaddr_t result = vaddr + (sizeof(vaddr_t)*2);
#else
vaddr_t result = vaddr + offsetof(Block, data);
#endif
vmem.freelist[level] = block->next;
if (block->next != VADDR_NULL)
vmem.block_ptr(block->next)->prev = VADDR_NULL;
block->mark_as_allocated(vaddr, level);
unlock_allocator();
memset(block->data, 0, size);
return result;
}
void init_flock_struct(
struct flock &lock_info, size_t offset, size_t len, bool lock) {
lock_info.l_start = offset;
lock_info.l_len = len;
lock_info.l_pid = 0;
lock_info.l_type = lock ? F_WRLCK : F_UNLCK;
lock_info.l_whence = SEEK_SET;
}
void lock_file(int fd, size_t offset, size_t len) {
struct flock lock_info;
init_flock_struct(lock_info, offset, len, true);
fcntl(fd, F_SETLKW, &lock_info);
}
void unlock_file(int fd, size_t offset, size_t len) {
struct flock lock_info;
init_flock_struct(lock_info, offset, len, false);
fcntl(fd, F_SETLKW, &lock_info);
}
void lock_metapage() {
lock_file(vmem.fd, 0);
}
void unlock_metapage() {
unlock_file(vmem.fd, 0);
}
void init_metapage(bool create) {
if (create)
ftruncate(vmem.fd, METABLOCK_SIZE);
vmem.metapage = (MetaPage *) mmap(
NULL, METABLOCK_SIZE, PROT_READ | PROT_WRITE, MAP_SHARED, vmem.fd, 0);
if (create) {
memcpy(vmem.metapage->config_header, config, sizeof(config));
for (int i = 0; i <= LOG2_SEGMENT_SIZE; i++) {
vmem.metapage->freelist[i] = VADDR_NULL;
}
vmem.metapage->segment_count = 0;
vmem.metapage->allocator_lock = FastLock(metapageaddr(allocator_lock));
} else {
assert(memcmp(vmem.metapage->config_header, config, sizeof(config)) != 0);
}
}
static void lock_process(int processno) {
lock_file(vmem.fd,
metapageaddr(process_info)
+ sizeof(ProcessInfo) * vmem.current_process);
}
static void unlock_process(int processno) {
unlock_file(vmem.fd,
metapageaddr(process_info)
+ sizeof(ProcessInfo) * vmem.current_process);
}
static ProcessInfo &process_info(int processno) {
return vmem.metapage->process_info[processno];
}
bool send_signal(int processno, ipc_signal_t sig, bool lock) {
if (lock)
lock_process(processno);
if (process_info(processno).sigstate != Waiting) {
unlock_process(processno);
return false;
}
if (processno == vmem.current_process) {
process_info(processno).sigstate = Accepted;
process_info(processno).signal = sig;
} else {
process_info(processno).sigstate = Pending;
process_info(processno).signal = sig;
int fd = vmem.channels[processno].fd_write;
char buf[1] = { 0 };
while (write(fd, buf, 1) != 1) {
}
}
if (lock)
unlock_process(processno);
return true;
}
ipc_signal_t check_signal(bool resume, bool lock) {
ipc_signal_t result;
if (lock)
lock_process(vmem.current_process);
SignalState sigstate = process_info(vmem.current_process).sigstate;
switch (sigstate) {
case Waiting:
case Pending: {
int fd = vmem.channels[vmem.current_process].fd_read;
char buf[1];
if (lock && sigstate == Waiting) {
unlock_process(vmem.current_process);
loop
{
#if defined(HAVE_POLL) && !defined(__APPLE__)
// fd is restricted on OsX by ulimit "file descriptors" (256)
pollfd pfd;
pfd.fd = fd;
pfd.events = POLLIN;
int rv = poll(&pfd, 1, 500000); /* msec*/
#else
// fd is restricted to <=1024
fd_set set;
FD_ZERO(&set); /* clear the set */
FD_SET(fd, &set); /* add our file descriptor to the set */
struct timeval timeout;
timeout.tv_sec = 500;
timeout.tv_usec = 0;
int rv = si_select(fd + 1, &set, NULL, NULL, &timeout);
#endif
if (rv== -1) continue; /* an error occurred */
if (rv== 0) break; /* timeout */
while(read(fd, buf, 1)!=1) {}
break;
}
lock_process(vmem.current_process);
} else {
loop
{
#if defined(HAVE_POLL) && !defined(__APPLE__)
// fd is restricted on OsX by ulimit "file descriptors" (256)
pollfd pfd;
pfd.fd = fd;
pfd.events = POLLIN;
int rv = poll(&pfd, 1, 500000); /* msec*/
#else
// fd is restricted to <=1024
fd_set set;
FD_ZERO(&set); /* clear the set */
FD_SET(fd, &set); /* add our file descriptor to the set */
struct timeval timeout;
timeout.tv_sec = 500;
timeout.tv_usec = 0;
int rv = si_select(fd + 1, &set, NULL, NULL, &timeout);
#endif
if (rv== -1) continue; /* an error occurred */
if (rv== 0) break; /* timeout */
while(read(fd, buf, 1)!=1) {}
break;
}
}
result = process_info(vmem.current_process).signal;
process_info(vmem.current_process).sigstate
= resume ? Waiting : Accepted;
if (lock)
unlock_process(vmem.current_process);
break;
}
case Accepted:
result = process_info(vmem.current_process).signal;
if (resume)
process_info(vmem.current_process).sigstate = Waiting;
if (lock)
unlock_process(vmem.current_process);
break;
}
return result;
}
void accept_signals() {
lock_process(vmem.current_process);
process_info(vmem.current_process).sigstate = Waiting;
unlock_process(vmem.current_process);
}
ipc_signal_t wait_signal(bool lock) {
return check_signal(true, lock);
}
} // namespace internals
pid_t fork_process() {
using namespace internals;
lock_metapage();
for (int p = 0; p < MAX_PROCESS; p++) {
if (vmem.metapage->process_info[p].pid == 0) {
pid_t pid = fork();
if (pid < 0) {
// error
return -1;
} else if (pid == 0) {
// child process
int parent = vmem.current_process;
vmem.current_process = p;
lock_metapage();
vmem.metapage->process_info[p].pid = getpid();
unlock_metapage();
send_signal(parent);
} else {
// parent process
unlock_metapage();
wait_signal();
// child has unlocked metapage, so we don't need to.
}
return pid;
}
}
unlock_metapage();
return -1;
}
void Semaphore::post() {
int wakeup = -1;
internals::ipc_signal_t sig;
_lock.lock();
if (_head == _tail) {
_value++;
} else {
// don't increment value, as we'll pass that on to the next process.
wakeup = _waiting[_head];
sig = _signals[_head];
next(_head);
}
_lock.unlock();
if (wakeup >= 0) {
internals::send_signal(wakeup, sig);
}
}
bool Semaphore::try_wait() {
bool result = false;
_lock.lock();
if (_value > 0) {
_value--;
result = true;
}
_lock.unlock();
return result;
}
void Semaphore::wait() {
_lock.lock();
if (_value > 0) {
_value--;
_lock.unlock();
return;
}
_waiting[_tail] = internals::vmem.current_process;
_signals[_tail] = 0;
next(_tail);
_lock.unlock();
internals::wait_signal();
}
bool Semaphore::start_wait(internals::ipc_signal_t sig) {
_lock.lock();
if (_value > 0) {
if (internals::send_signal(internals::vmem.current_process, sig))
_value--;
_lock.unlock();
return false;
}
_waiting[_tail] = internals::vmem.current_process;
_signals[_tail] = sig;
next(_tail);
_lock.unlock();
return true;
}
bool Semaphore::stop_wait() {
bool result = false;
_lock.lock();
for (int i = _head; i != _tail; next(i)) {
if (_waiting[i] == internals::vmem.current_process) {
int last = i;
next(i);
while (i != _tail) {
_waiting[last] = _waiting[i];
_signals[last] = _signals[i];
last = i;
next(i);
}
_tail = last;
result = true;
break;
}
}
_lock.unlock();
return result;
}
void EventSet::add(Event *event) {
event->_next = NULL;
if (_head == NULL) {
_head = _tail = event;
} else {
_tail->_next = event;
_tail = event;
}
}
int EventSet::wait() {
size_t n = 0;
for (Event *event = _head; event; event = event->_next) {
if (!event->start_listen((int) (n++))) {
break;
}
}
internals::ipc_signal_t result = internals::check_signal();
for (Event *event = _head; event; event = event->_next) {
event->stop_listen();
}
internals::accept_signals();
return (int) result;
}
} // namespace vspace
#else // gcc>9
#include <cstdlib>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/stat.h>
namespace vspace {
namespace internals {
size_t config[4]
= { METABLOCK_SIZE, MAX_PROCESS, SEGMENT_SIZE, MAX_SEGMENTS };
VMem VMem::vmem_global;
// offsetof() only works for POD types, so we need to construct
// a portable version of it for metapage fields.
#define metapageaddr(field) \
((char *) &vmem.metapage->field - (char *) vmem.metapage)
size_t VMem::filesize() {
struct stat stat;
fstat(fd, &stat);
return stat.st_size;
}
Status VMem::init(int fd) {
this->fd = fd;
for (int i = 0; i < MAX_SEGMENTS; i++)
segments[i] = VSeg(NULL);
for (int i = 0; i < MAX_PROCESS; i++) {
int channel[2];
if (pipe(channel) < 0) {
for (int j = 0; j < i; j++) {
close(channels[j].fd_read);
close(channels[j].fd_write);
}
return Status(ErrOS);
}
channels[i].fd_read = channel[0];
channels[i].fd_write = channel[1];
}
lock_metapage();
init_metapage(filesize() == 0);
unlock_metapage();
freelist = metapage->freelist;
return Status(ErrNone);
}
Status VMem::init() {
FILE *fp = tmpfile();
Status result = init(fileno(fp));
if (!result.ok())
return result;
current_process = 0;
file_handle = fp;
metapage->process_info[0].pid = getpid();
return Status(ErrNone);
}
Status VMem::init(const char *path) {
int fd = open(path, O_RDWR | O_CREAT, 0600);
if (fd < 0)
return Status(ErrFile);
init(fd);
lock_metapage();
// TODO: enter process in meta table
unlock_metapage();
return Status(ErrNone);
}
void VMem::deinit() {
if (file_handle) {
fclose(file_handle);
file_handle = NULL;
} else {
close(fd);
}
munmap(metapage, METABLOCK_SIZE);
metapage = NULL;
current_process = -1;
freelist = NULL;
for (int i = 0; i < MAX_SEGMENTS; i++) {
if (!segments[i].is_free())
munmap(segments[i].base, SEGMENT_SIZE);
segments[i] = VSeg(NULL);
}
for (int i = 0; i < MAX_PROCESS; i++) {
close(channels[i].fd_read);
close(channels[i].fd_write);
}
}
void *VMem::mmap_segment(int seg) {
lock_metapage();
void *map = mmap(NULL, SEGMENT_SIZE, PROT_READ | PROT_WRITE, MAP_SHARED, fd,
METABLOCK_SIZE + seg * SEGMENT_SIZE);
if (map == MAP_FAILED) {
// This is an "impossible to proceed from here, because system state
// is impossible to proceed from" situation, so we abort the program.
perror("mmap");
abort();
}
unlock_metapage();
return map;
}
void VMem::add_segment() {
int seg = metapage->segment_count++;
ftruncate(fd, METABLOCK_SIZE + metapage->segment_count * SEGMENT_SIZE);
void *map_addr = mmap_segment(seg);
segments[seg] = VSeg(map_addr);
Block *top = block_ptr(seg * SEGMENT_SIZE);
top->next = freelist[LOG2_SEGMENT_SIZE];
top->prev = VADDR_NULL;
freelist[LOG2_SEGMENT_SIZE] = seg * SEGMENT_SIZE;
}
void FastLock::lock() {
#ifdef HAVE_CPP_THREADS
while (_lock.test_and_set()) {
}
bool empty = _owner < 0;
if (empty) {
_owner = vmem.current_process;
} else {
int p = vmem.current_process;
vmem.metapage->process_info[p].next = -1;
if (_head < 0)
_head = p;
else
vmem.metapage->process_info[_tail].next = p;
_tail = p;
}
_lock.clear();
if (!empty)
wait_signal(false);
#else
lock_file(vmem.fd, _offset);
#endif
}
void FastLock::unlock() {
#ifdef HAVE_CPP_THREADS
while (_lock.test_and_set()) {
}
_owner = _head;
if (_owner >= 0)
_head = vmem.metapage->process_info[_head].next;
_lock.clear();
if (_owner >= 0)
send_signal(_owner, 0, false);
#else
unlock_file(vmem.fd, _offset);
#endif
}
static void lock_allocator() {
vmem.metapage->allocator_lock.lock();
}
static void unlock_allocator() {
vmem.metapage->allocator_lock.unlock();
}
static void print_freelists() {
for (int i = 0; i <= LOG2_SEGMENT_SIZE; i++) {
vaddr_t vaddr = vmem.freelist[i];
if (vaddr != VADDR_NULL) {
std::printf("%2d: %ld", i, (long)vaddr);
vaddr_t prev = block_ptr(vaddr)->prev;
if (prev != VADDR_NULL) {
std::printf("(%ld)", (long)prev);
}
assert(block_ptr(vaddr)->prev == VADDR_NULL);
for (;;) {
vaddr_t last_vaddr = vaddr;
Block *block = block_ptr(vaddr);
vaddr = block->next;
if (vaddr == VADDR_NULL)
break;
std::printf(" -> %ld", (long)vaddr);
vaddr_t prev = block_ptr(vaddr)->prev;
if (prev != last_vaddr) {
std::printf("(%ld)", (long)prev);
}
}
std::printf("\n");
}
}
std::fflush(stdout);
}
void vmem_free(vaddr_t vaddr) {
lock_allocator();
#if defined(__GNUC__) && (__GNUC__>11)
vaddr -= (sizeof(vaddr_t)*2);
#else
vaddr -= offsetof(Block, data);
#endif
vmem.ensure_is_mapped(vaddr);
size_t segno = vmem.segment_no(vaddr);
VSeg seg = vmem.segment(vaddr);
segaddr_t addr = vmem.segaddr(vaddr);
int level = seg.block_ptr(addr)->level();
assert(!seg.is_free(addr));
while (level < LOG2_SEGMENT_SIZE) {
segaddr_t buddy = find_buddy(addr, level);
Block *block = seg.block_ptr(buddy);
// is buddy free and at the same level?
if (!block->is_free() || block->level() != level)
break;
// remove buddy from freelist.
Block *prev = vmem.block_ptr(block->prev);
Block *next = vmem.block_ptr(block->next);
block->data[0] = level;
if (prev) {
assert(prev->next == vmem.vaddr(segno, buddy));
prev->next = block->next;
} else {
// head of freelist.
assert(vmem.freelist[level] == vmem.vaddr(segno, buddy));
vmem.freelist[level] = block->next;
}
if (next) {
assert(next->prev == vmem.vaddr(segno, buddy));
next->prev = block->prev;
}
// coalesce block with buddy
level++;
if (buddy < addr)
addr = buddy;
}
// Add coalesced block to free list
Block *block = seg.block_ptr(addr);
block->prev = VADDR_NULL;
block->next = vmem.freelist[level];
block->mark_as_free(level);
vaddr_t blockaddr = vmem.vaddr(segno, addr);
if (block->next != VADDR_NULL)
vmem.block_ptr(block->next)->prev = blockaddr;
vmem.freelist[level] = blockaddr;
unlock_allocator();
}
vaddr_t vmem_alloc(size_t size) {
lock_allocator();
#if defined(__GNUC__) && (__GNUC__>11)
size_t alloc_size = size + (sizeof(vaddr_t)*2);
#else
size_t alloc_size = size + offsetof(Block, data);
#endif
int level = find_level(alloc_size);
int flevel = level;
while (flevel < LOG2_SEGMENT_SIZE && vmem.freelist[flevel] == VADDR_NULL)
flevel++;
if (vmem.freelist[flevel] == VADDR_NULL) {
vmem.add_segment();
}
vmem.ensure_is_mapped(vmem.freelist[flevel]);
while (flevel > level) {
// get and split a block
vaddr_t blockaddr = vmem.freelist[flevel];
assert((blockaddr & ((1 << flevel) - 1)) == 0);
Block *block = vmem.block_ptr(blockaddr);
vmem.freelist[flevel] = block->next;
if (vmem.freelist[flevel] != VADDR_NULL)
vmem.block_ptr(vmem.freelist[flevel])->prev = VADDR_NULL;
vaddr_t blockaddr2 = blockaddr + (1 << (flevel - 1));
Block *block2 = vmem.block_ptr(blockaddr2);
flevel--;
block2->next = vmem.freelist[flevel];
block2->prev = blockaddr;
block->next = blockaddr2;
block->prev = VADDR_NULL;
// block->prev == VADDR_NULL already.
vmem.freelist[flevel] = blockaddr;
}
assert(vmem.freelist[level] != VADDR_NULL);
Block *block = vmem.block_ptr(vmem.freelist[level]);
vaddr_t vaddr = vmem.freelist[level];
#if defined(__GNUC__) && (__GNUC__>11)
vaddr_t result = vaddr + (sizeof(vaddr_t)*2);
#else
vaddr_t result = vaddr + offsetof(Block, data);
#endif
vmem.freelist[level] = block->next;
if (block->next != VADDR_NULL)
vmem.block_ptr(block->next)->prev = VADDR_NULL;
block->mark_as_allocated(vaddr, level);
unlock_allocator();
memset(block->data, 0, size);
return result;
}
void init_flock_struct(
struct flock &lock_info, size_t offset, size_t len, bool lock) {
lock_info.l_start = offset;
lock_info.l_len = len;
lock_info.l_pid = 0;
lock_info.l_type = lock ? F_WRLCK : F_UNLCK;
lock_info.l_whence = SEEK_SET;
}
void lock_file(int fd, size_t offset, size_t len) {
struct flock lock_info;
init_flock_struct(lock_info, offset, len, true);
fcntl(fd, F_SETLKW, &lock_info);
}
void unlock_file(int fd, size_t offset, size_t len) {
struct flock lock_info;
init_flock_struct(lock_info, offset, len, false);
fcntl(fd, F_SETLKW, &lock_info);
}
void lock_metapage() {
lock_file(vmem.fd, 0);
}
void unlock_metapage() {
unlock_file(vmem.fd, 0);
}
void init_metapage(bool create) {
if (create)
ftruncate(vmem.fd, METABLOCK_SIZE);
vmem.metapage = (MetaPage *) mmap(
NULL, METABLOCK_SIZE, PROT_READ | PROT_WRITE, MAP_SHARED, vmem.fd, 0);
if (create) {
std::memcpy(vmem.metapage->config_header, config, sizeof(config));
for (int i = 0; i <= LOG2_SEGMENT_SIZE; i++) {
vmem.metapage->freelist[i] = VADDR_NULL;
}
vmem.metapage->segment_count = 0;
vmem.metapage->allocator_lock = FastLock(metapageaddr(allocator_lock));
} else {
assert(std::memcmp(vmem.metapage->config_header, config,
sizeof(config)) != 0);
}
}
static void lock_process(int processno) {
lock_file(vmem.fd,
metapageaddr(process_info)
+ sizeof(ProcessInfo) * vmem.current_process);
}
static void unlock_process(int processno) {
unlock_file(vmem.fd,
metapageaddr(process_info)
+ sizeof(ProcessInfo) * vmem.current_process);
}
static ProcessInfo &process_info(int processno) {
return vmem.metapage->process_info[processno];
}
bool send_signal(int processno, ipc_signal_t sig, bool lock) {
if (lock)
lock_process(processno);
if (process_info(processno).sigstate != Waiting) {
unlock_process(processno);
return false;
}
if (processno == vmem.current_process) {
process_info(processno).sigstate = Accepted;
process_info(processno).signal = sig;
} else {
process_info(processno).sigstate = Pending;
process_info(processno).signal = sig;
int fd = vmem.channels[processno].fd_write;
char buf[1] = { 0 };
while (write(fd, buf, 1) != 1) {
}
}
if (lock)
unlock_process(processno);
return true;
}
ipc_signal_t check_signal(bool resume, bool lock) {
ipc_signal_t result;
if (lock)
lock_process(vmem.current_process);
SignalState sigstate = process_info(vmem.current_process).sigstate;
switch (sigstate) {
case Waiting:
case Pending: {
int fd = vmem.channels[vmem.current_process].fd_read;
char buf[1];
if (lock && sigstate == Waiting) {
unlock_process(vmem.current_process);
loop
{
#if defined(HAVE_POLL) && !defined(__APPLE__)
// fd is restricted on OsX by ulimit "file descriptors" (256)
pollfd pfd;
pfd.fd = fd;
pfd.events = POLLIN;
int rv = poll(&pfd, 1, 500000); /* msec*/
#else
// fd is restricted to <=1024
fd_set set;
FD_ZERO(&set); /* clear the set */
FD_SET(fd, &set); /* add our file descriptor to the set */
struct timeval timeout;
timeout.tv_sec = 500;
timeout.tv_usec = 0;
int rv = si_select(fd + 1, &set, NULL, NULL, &timeout);
#endif
if (rv== -1) continue; /* an error occurred */
if (rv== 0) break; /* timeout */
while(read(fd, buf, 1)!=1) {}
break;
}
lock_process(vmem.current_process);
} else {
loop
{
#if defined(HAVE_POLL) && !defined(__APPLE__)
// fd is restricted on OsX by ulimit "file descriptors" (256)
pollfd pfd;
pfd.fd = fd;
pfd.events = POLLIN;
int rv = poll(&pfd, 1, 500000); /* msec*/
#else
// fd is restricted to <=1024
fd_set set;
FD_ZERO(&set); /* clear the set */
FD_SET(fd, &set); /* add our file descriptor to the set */
struct timeval timeout;
timeout.tv_sec = 500;
timeout.tv_usec = 0;
int rv = si_select(fd + 1, &set, NULL, NULL, &timeout);
#endif
if (rv== -1) continue; /* an error occurred */
if (rv== 0) break;/* timeout */
while(read(fd, buf, 1)!=1) {}
break;
}
}
result = process_info(vmem.current_process).signal;
process_info(vmem.current_process).sigstate
= resume ? Waiting : Accepted;
if (lock)
unlock_process(vmem.current_process);
break;
}
case Accepted:
result = process_info(vmem.current_process).signal;
if (resume)
process_info(vmem.current_process).sigstate = Waiting;
if (lock)
unlock_process(vmem.current_process);
break;
}
return result;
}
void accept_signals() {
lock_process(vmem.current_process);
process_info(vmem.current_process).sigstate = Waiting;
unlock_process(vmem.current_process);
}
ipc_signal_t wait_signal(bool lock) {
return check_signal(true, lock);
}
} // namespace internals
pid_t fork_process() {
using namespace internals;
lock_metapage();
for (int p = 0; p < MAX_PROCESS; p++) {
if (vmem.metapage->process_info[p].pid == 0) {
pid_t pid = fork();
if (pid < 0) {
// error
return -1;
} else if (pid == 0) {
// child process
int parent = vmem.current_process;
vmem.current_process = p;
lock_metapage();
vmem.metapage->process_info[p].pid = getpid();
unlock_metapage();
send_signal(parent);
} else {
// parent process
unlock_metapage();
wait_signal();
// child has unlocked metapage, so we don't need to.
}
return pid;
}
}
unlock_metapage();
return -1;
}
void Semaphore::post() {
int wakeup = -1;
internals::ipc_signal_t sig;
_lock.lock();
if (_head == _tail) {
_value++;
} else {
// don't increment value, as we'll pass that on to the next process.
wakeup = _waiting[_head];
sig = _signals[_head];
next(_head);
}
_lock.unlock();
if (wakeup >= 0) {
internals::send_signal(wakeup, sig);
}
}
bool Semaphore::try_wait() {
bool result = false;
_lock.lock();
if (_value > 0) {
_value--;
result = true;
}
_lock.unlock();
return result;
}
void Semaphore::wait() {
_lock.lock();
if (_value > 0) {
_value--;
_lock.unlock();
return;
}
_waiting[_tail] = internals::vmem.current_process;
_signals[_tail] = 0;
next(_tail);
_lock.unlock();
internals::wait_signal();
}
bool Semaphore::start_wait(internals::ipc_signal_t sig) {
_lock.lock();
if (_value > 0) {
if (internals::send_signal(internals::vmem.current_process, sig))
_value--;
_lock.unlock();
return false;
}
_waiting[_tail] = internals::vmem.current_process;
_signals[_tail] = sig;
next(_tail);
_lock.unlock();
return true;
}
bool Semaphore::stop_wait() {
bool result = false;
_lock.lock();
for (int i = _head; i != _tail; next(i)) {
if (_waiting[i] == internals::vmem.current_process) {
int last = i;
next(i);
while (i != _tail) {
_waiting[last] = _waiting[i];
_signals[last] = _signals[i];
last = i;
next(i);
}
_tail = last;
result = true;
break;
}
}
_lock.unlock();
return result;
}
void EventSet::add(Event *event) {
event->_next = NULL;
if (_head == NULL) {
_head = _tail = event;
} else {
_tail->_next = event;
_tail = event;
}
}
int EventSet::wait() {
size_t n = 0;
for (Event *event = _head; event; event = event->_next) {
if (!event->start_listen((int) (n++))) {
break;
}
}
internals::ipc_signal_t result = internals::check_signal();
for (Event *event = _head; event; event = event->_next) {
event->stop_listen();
}
internals::accept_signals();
return (int) result;
}
} // namespace vspace
#endif
#endif
size
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition cf_ops.cc:600
level
int level(const CanonicalForm &f)
Definition canonicalform.h:331
i
int i
Definition cfEzgcd.cc:132
p
int p
Definition cfModGcd.cc:4086
fp
CanonicalForm fp
Definition cfModGcd.cc:4110
map
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:505
vspace::EventSet::add
void add(Event *event)
Definition vspace.cc:1191
vspace::EventSet::_head
Event * _head
Definition vspace.h:2581
vspace::EventSet::_tail
Event * _tail
Definition vspace.h:2581
vspace::EventSet::wait
int wait()
Definition vspace.cc:1201
vspace::Event
Definition vspace.h:2570
vspace::Semaphore::_waiting
int _waiting[internals::MAX_PROCESS+1]
Definition vspace.h:2348
vspace::Semaphore::start_wait
bool start_wait(internals::ipc_signal_t sig=0)
Definition vspace.cc:1154
vspace::Semaphore::_head
int _head
Definition vspace.h:2350
vspace::Semaphore::_signals
internals::ipc_signal_t _signals[internals::MAX_PROCESS+1]
Definition vspace.h:2349
vspace::Semaphore::_value
size_t _value
Definition vspace.h:2357
vspace::Semaphore::_lock
FastLock _lock
Definition vspace.h:2358
vspace::Semaphore::wait
void wait()
Definition vspace.cc:1140
vspace::Semaphore::try_wait
bool try_wait()
Definition vspace.cc:1129
vspace::Semaphore::post
void post()
Definition vspace.cc:1111
vspace::Semaphore::_tail
int _tail
Definition vspace.h:2350
vspace::Semaphore::stop_wait
bool stop_wait()
Definition vspace.cc:1169
vspace::internals::FastLock::_offset
vaddr_t _offset
Definition vspace.h:1437
vspace::internals::Mutex::lock
void lock()
Definition vspace.h:1718
vspace::internals::Mutex::_lock
vaddr_t _lock
Definition vspace.h:1710
vspace::internals::Mutex::_owner
int _owner
Definition vspace.h:1708
vspace::internals::Mutex::unlock
void unlock()
Definition vspace.h:1727
result
return result
Definition facAbsBiFact.cc:76
j
int j
Definition facHensel.cc:110
last
STATIC_VAR poly last
Definition hdegree.cc:1138
create
NodeM * create()
Definition janet.cc:757
offset
STATIC_VAR int offset
Definition janet.cc:29
next
ListNode * next
Definition janet.h:31
mod2.h
SEEK_SET
#define SEEK_SET
Definition mod2.h:115
vspace::internals
Definition vspace.cc:616
vspace::internals::SignalState
SignalState
Definition vspace.h:1493
vspace::internals::Accepted
@ Accepted
Definition vspace.h:1496
vspace::internals::Pending
@ Pending
Definition vspace.h:1495
vspace::internals::Waiting
@ Waiting
Definition vspace.h:1494
vspace::internals::accept_signals
void accept_signals()
Definition vspace.cc:1069
vspace::internals::ipc_signal_t
int ipc_signal_t
Definition vspace.h:1481
vspace::internals::unlock_metapage
void unlock_metapage()
Definition vspace.cc:929
vspace::internals::VADDR_NULL
const vaddr_t VADDR_NULL
Definition vspace.h:1417
vspace::internals::init_flock_struct
void init_flock_struct(struct flock &lock_info, size_t offset, size_t len, bool lock)
Definition vspace.cc:904
vspace::internals::vaddr_t
size_t vaddr_t
Definition vspace.h:1414
vspace::internals::process_info
static ProcessInfo & process_info(int processno)
Definition vspace.cc:963
vspace::internals::lock_file
void lock_file(int fd, size_t offset, size_t len)
Definition vspace.cc:913
vspace::internals::vmem_free
void vmem_free(vaddr_t vaddr)
Definition vspace.cc:802
vspace::internals::block_ptr
Block * block_ptr(vaddr_t vaddr)
Definition vspace.h:1637
vspace::internals::vmem_alloc
vaddr_t vmem_alloc(size_t size)
Definition vspace.cc:854
vspace::internals::unlock_process
static void unlock_process(int processno)
Definition vspace.cc:957
vspace::internals::MAX_SEGMENTS
static const size_t MAX_SEGMENTS
Definition vspace.h:1423
vspace::internals::SEGMENT_SIZE
static const size_t SEGMENT_SIZE
Definition vspace.h:1424
vspace::internals::ProcessInfo::sigstate
SignalState sigstate
Definition vspace.h:1501
vspace::internals::METABLOCK_SIZE
static const size_t METABLOCK_SIZE
Definition vspace.h:1420
vspace::internals::lock_process
static void lock_process(int processno)
Definition vspace.cc:951
vspace::internals::LOG2_SEGMENT_SIZE
static const int LOG2_SEGMENT_SIZE
Definition vspace.h:1421
vspace::internals::wait_signal
ipc_signal_t wait_signal(bool lock)
Definition vspace.cc:1075
vspace::internals::lock_metapage
void lock_metapage()
Definition vspace.cc:925
vspace::internals::MAX_PROCESS
static const int MAX_PROCESS
Definition vspace.h:1419
vspace::internals::vmem
static VMem & vmem
Definition vspace.h:1635
vspace::internals::MetaPage::process_info
ProcessInfo process_info[MAX_PROCESS]
Definition vspace.h:1513
vspace::internals::lock_allocator
static void lock_allocator()
Definition vspace.cc:766
vspace::internals::find_buddy
static segaddr_t find_buddy(segaddr_t addr, int level)
Definition vspace.h:1690
vspace::internals::check_signal
ipc_signal_t check_signal(bool resume, bool lock)
Definition vspace.cc:990
vspace::internals::init_metapage
void init_metapage(bool create)
Definition vspace.cc:933
vspace::internals::unlock_file
void unlock_file(int fd, size_t offset, size_t len)
Definition vspace.cc:919
vspace::internals::send_signal
bool send_signal(int processno, ipc_signal_t sig, bool lock)
Definition vspace.cc:967
vspace::internals::find_level
static int find_level(size_t size)
Definition vspace.h:1681
vspace::internals::config
size_t config[4]
Definition vspace.cc:619
vspace::internals::segaddr_t
size_t segaddr_t
Definition vspace.h:1412
vspace::internals::unlock_allocator
static void unlock_allocator()
Definition vspace.cc:770
vspace::internals::print_freelists
static void print_freelists()
Definition vspace.cc:774
vspace::internals::ProcessInfo::signal
ipc_signal_t signal
Definition vspace.h:1502
vspace::internals::MetaPage
Definition vspace.h:1508
vspace::internals::ProcessInfo
Definition vspace.h:1499
vspace
Definition vspace.cc:615
vspace::fork_process
pid_t fork_process()
Definition vspace.cc:1081
vspace::ErrOS
@ ErrOS
Definition vspace.h:1380
vspace::ErrNone
@ ErrNone
Definition vspace.h:1376
vspace::ErrFile
@ ErrFile
Definition vspace.h:1378
vspace::FastLock
internals::Mutex FastLock
Definition vspace.h:2340
NULL
#define NULL
Definition omList.c:12
block
#define block
Definition scanner.cc:646
si_signals.h
read
int status read
Definition si_signals.h:69
fd
int status int fd
Definition si_signals.h:69
open
int status int void size_t count open
Definition si_signals.h:83
buf
int status int void * buf
Definition si_signals.h:69
loop
#define loop
Definition structs.h:71
vspace::Status
Definition vspace.h:1398
vspace::internals::Block
Definition vspace.h:1529
vspace::internals::Block::next
vaddr_t next
Definition vspace.h:1541
vspace::internals::Block::prev
vaddr_t prev
Definition vspace.h:1540
vspace::internals::Block::level
int level()
Definition vspace.h:1546
vspace::internals::VMem
Definition vspace.h:1587
vspace::internals::VMem::file_handle
std::FILE * file_handle
Definition vspace.h:1591
vspace::internals::VMem::block_ptr
Block * block_ptr(vaddr_t vaddr)
Definition vspace.h:1610
vspace::internals::VMem::mmap_segment
void * mmap_segment(int seg)
Definition vspace.cc:702
vspace::internals::VMem::init
Status init()
Definition vspace.cc:658
vspace::internals::VMem::filesize
size_t filesize()
Definition vspace.cc:629
vspace::internals::VMem::metapage
MetaPage * metapage
Definition vspace.h:1589
vspace::internals::VMem::fd
int fd
Definition vspace.h:1590
vspace::internals::VMem::current_process
int current_process
Definition vspace.h:1592
vspace::internals::VMem::vmem_global
static VMem vmem_global
Definition vspace.h:1588
vspace::internals::VMem::freelist
vaddr_t * freelist
Definition vspace.h:1593
vspace::internals::VMem::segments
VSeg segments[MAX_SEGMENTS]
Definition vspace.h:1594
vspace::internals::VMem::add_segment
void add_segment()
Definition vspace.cc:716
vspace::internals::VMem::channels
ProcessChannel channels[MAX_PROCESS]
Definition vspace.h:1595
vspace::internals::VMem::deinit
void deinit()
Definition vspace.cc:680
vspace::internals::VSeg
Definition vspace.h:1566
vspace::internals::VSeg::is_free
bool is_free()
Definition vspace.h:1568
vspace::internals::VSeg::block_ptr
Block * block_ptr(segaddr_t addr)
Definition vspace.h:1571
assert
#define assert(A)
Definition svd_si.h:3
metapageaddr
#define metapageaddr(field)
Definition vspace.cc:626
vspace.h