My Project
Loading...
Searching...
No Matches
Namespaces | Macros | Functions | Variables
vspace.cc File Reference
#include "vspace.h"
#include "kernel/mod2.h"
#include <cstddef>
#include <cstdlib>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/stat.h>

Go to the source code of this file.

Namespaces

namespace  vspace
 
namespace  vspace::internals
 

Macros

#define metapageaddr(field)    ((char *) &vmem.metapage->field - (char *) vmem.metapage)
 

Functions

static void vspace::internals::lock_allocator ()
 
static void vspace::internals::unlock_allocator ()
 
static void vspace::internals::print_freelists ()
 
void vspace::internals::vmem_free (vaddr_t vaddr)
 
vaddr_t vspace::internals::vmem_alloc (size_t size)
 
void vspace::internals::init_flock_struct (struct flock &lock_info, size_t offset, size_t len, bool lock)
 
void vspace::internals::lock_file (int fd, size_t offset, size_t len)
 
void vspace::internals::unlock_file (int fd, size_t offset, size_t len)
 
void vspace::internals::lock_metapage ()
 
void vspace::internals::unlock_metapage ()
 
void vspace::internals::init_metapage (bool create)
 
static void vspace::internals::lock_process (int processno)
 
static void vspace::internals::unlock_process (int processno)
 
static ProcessInfovspace::internals::process_info (int processno)
 
bool vspace::internals::send_signal (int processno, ipc_signal_t sig, bool lock)
 
ipc_signal_t vspace::internals::check_signal (bool resume, bool lock)
 
void vspace::internals::accept_signals ()
 
ipc_signal_t vspace::internals::wait_signal (bool lock)
 
pid_t vspace::fork_process ()
 

Variables

size_t vspace::internals::config [4] = { METABLOCK_SIZE, MAX_PROCESS, SEGMENT_SIZE, MAX_SEGMENTS }
 

Macro Definition Documentation

◆ metapageaddr

#define metapageaddr (   field)     ((char *) &vmem.metapage->field - (char *) vmem.metapage)

Definition at line 580 of file vspace.cc.

582 {
583 struct stat stat;
584 fstat(fd, &stat);
585 return stat.st_size;
586}
587
588Status VMem::init(int fd) {
589 this->fd = fd;
590 for (int i = 0; i < MAX_SEGMENTS; i++)
591 segments[i] = VSeg(NULL);
592 for (int i = 0; i < MAX_PROCESS; i++) {
593 int channel[2];
594 if (pipe(channel) < 0) {
595 for (int j = 0; j < i; j++) {
596 close(channels[j].fd_read);
597 close(channels[j].fd_write);
598 }
599 return Status(ErrOS);
600 }
601 channels[i].fd_read = channel[0];
602 channels[i].fd_write = channel[1];
603 }
605 init_metapage(filesize() == 0);
607 freelist = metapage->freelist;
608 return Status(ErrNone);
609}
610
611Status VMem::init() {
612 FILE *fp = tmpfile();
613 Status result = init(fileno(fp));
614 if (!result.ok())
615 return result;
616 current_process = 0;
617 file_handle = fp;
618 metapage->process_info[0].pid = getpid();
619 return Status(ErrNone);
620}
621
622Status VMem::init(const char *path) {
623 int fd = open(path, O_RDWR | O_CREAT, 0600);
624 if (fd < 0)
625 return Status(ErrFile);
626 init(fd);
628 // TODO: enter process in meta table
630 return Status(ErrNone);
631}
632
633void VMem::deinit() {
634 if (file_handle) {
635 fclose(file_handle);
636 file_handle = NULL;
637 } else {
638 close(fd);
639 }
640 munmap(metapage, METABLOCK_SIZE);
641 metapage = NULL;
642 current_process = -1;
643 freelist = NULL;
644 for (int i = 0; i < MAX_SEGMENTS; i++) {
645 if (!segments[i].is_free())
646 munmap(segments[i].base, SEGMENT_SIZE);
647 segments[i] = VSeg(NULL);
648 }
649 for (int i = 0; i < MAX_PROCESS; i++) {
650 close(channels[i].fd_read);
651 close(channels[i].fd_write);
652 }
653}
654
655void *VMem::mmap_segment(int seg) {
657 void *map = mmap(NULL, SEGMENT_SIZE, PROT_READ | PROT_WRITE, MAP_SHARED, fd,
658 METABLOCK_SIZE + seg * SEGMENT_SIZE);
659 if (map == MAP_FAILED) {
660 // This is an "impossible to proceed from here, because system state
661 // is impossible to proceed from" situation, so we abort the program.
662 perror("mmap");
663 abort();
664 }
666 return map;
667}
668
669void VMem::add_segment() {
670 int seg = metapage->segment_count++;
671 ftruncate(fd, METABLOCK_SIZE + metapage->segment_count * SEGMENT_SIZE);
672 void *map_addr = mmap_segment(seg);
673 segments[seg] = VSeg(map_addr);
674 Block *top = block_ptr(seg * SEGMENT_SIZE);
675 top->next = freelist[LOG2_SEGMENT_SIZE];
676 top->prev = VADDR_NULL;
677 freelist[LOG2_SEGMENT_SIZE] = seg * SEGMENT_SIZE;
678}
679
680void FastLock::lock() {
681#ifdef HAVE_CPP_THREADS
682 while (_lock.test_and_set()) {
683 }
684 bool empty = _owner < 0;
685 if (empty) {
686 _owner = vmem.current_process;
687 } else {
688 int p = vmem.current_process;
689 vmem.metapage->process_info[p].next = -1;
690 if (_head < 0)
691 _head = p;
692 else
693 vmem.metapage->process_info[_tail].next = p;
694 _tail = p;
695 }
696 _lock.clear();
697 if (!empty)
698 wait_signal(false);
699#else
700 lock_file(vmem.fd, _offset);
701#endif
702}
703
704void FastLock::unlock() {
705#ifdef HAVE_CPP_THREADS
706 while (_lock.test_and_set()) {
707 }
708 _owner = _head;
709 if (_owner >= 0)
710 _head = vmem.metapage->process_info[_head].next;
711 _lock.clear();
712 if (_owner >= 0)
713 send_signal(_owner, 0, false);
714#else
715 unlock_file(vmem.fd, _offset);
716#endif
717}
718
719static void lock_allocator() {
720 vmem.metapage->allocator_lock.lock();
721}
722
723static void unlock_allocator() {
724 vmem.metapage->allocator_lock.unlock();
725}
726
727static void print_freelists() {
728 for (int i = 0; i <= LOG2_SEGMENT_SIZE; i++) {
729 vaddr_t vaddr = vmem.freelist[i];
730 if (vaddr != VADDR_NULL) {
731 std::printf("%2d: %ld", i, (long)vaddr);
732 vaddr_t prev = block_ptr(vaddr)->prev;
733 if (prev != VADDR_NULL) {
734 std::printf("(%ld)", (long)prev);
735 }
736 assert(block_ptr(vaddr)->prev == VADDR_NULL);
737 for (;;) {
738 vaddr_t last_vaddr = vaddr;
739 Block *block = block_ptr(vaddr);
740 vaddr = block->next;
741 if (vaddr == VADDR_NULL)
742 break;
743 std::printf(" -> %ld", (long)vaddr);
744 vaddr_t prev = block_ptr(vaddr)->prev;
745 if (prev != last_vaddr) {
746 std::printf("(%ld)", (long)prev);
747 }
748 }
749 std::printf("\n");
750 }
751 }
752 std::fflush(stdout);
753}
754
755void vmem_free(vaddr_t vaddr) {
757 #if defined(__GNUC__) && (__GNUC__>11)
758 vaddr -= (sizeof(vaddr_t)*2);
759 #else
760 vaddr -= offsetof(Block, data);
761 #endif
762 vmem.ensure_is_mapped(vaddr);
763 size_t segno = vmem.segment_no(vaddr);
764 VSeg seg = vmem.segment(vaddr);
765 segaddr_t addr = vmem.segaddr(vaddr);
766 int level = seg.block_ptr(addr)->level();
767 assert(!seg.is_free(addr));
768 while (level < LOG2_SEGMENT_SIZE) {
769 segaddr_t buddy = find_buddy(addr, level);
770 Block *block = seg.block_ptr(buddy);
771 // is buddy free and at the same level?
772 if (!block->is_free() || block->level() != level)
773 break;
774 // remove buddy from freelist.
775 Block *prev = vmem.block_ptr(block->prev);
776 Block *next = vmem.block_ptr(block->next);
777 block->data[0] = level;
778 if (prev) {
779 assert(prev->next == vmem.vaddr(segno, buddy));
780 prev->next = block->next;
781 } else {
782 // head of freelist.
783 assert(vmem.freelist[level] == vmem.vaddr(segno, buddy));
784 vmem.freelist[level] = block->next;
785 }
786 if (next) {
787 assert(next->prev == vmem.vaddr(segno, buddy));
788 next->prev = block->prev;
789 }
790 // coalesce block with buddy
791 level++;
792 if (buddy < addr)
793 addr = buddy;
794 }
795 // Add coalesced block to free list
796 Block *block = seg.block_ptr(addr);
797 block->prev = VADDR_NULL;
798 block->next = vmem.freelist[level];
799 block->mark_as_free(level);
800 vaddr_t blockaddr = vmem.vaddr(segno, addr);
801 if (block->next != VADDR_NULL)
802 vmem.block_ptr(block->next)->prev = blockaddr;
803 vmem.freelist[level] = blockaddr;
805}
806
807vaddr_t vmem_alloc(size_t size) {
809 #if defined(__GNUC__) && (__GNUC__>11)
810 size_t alloc_size = size + (sizeof(vaddr_t)*2);
811 #else
812 size_t alloc_size = size + offsetof(Block, data);
813 #endif
814 int level = find_level(alloc_size);
815 int flevel = level;
816 while (flevel < LOG2_SEGMENT_SIZE && vmem.freelist[flevel] == VADDR_NULL)
817 flevel++;
818 if (vmem.freelist[flevel] == VADDR_NULL) {
819 vmem.add_segment();
820 }
821 vmem.ensure_is_mapped(vmem.freelist[flevel]);
822 while (flevel > level) {
823 // get and split a block
824 vaddr_t blockaddr = vmem.freelist[flevel];
825 assert((blockaddr & ((1 << flevel) - 1)) == 0);
826 Block *block = vmem.block_ptr(blockaddr);
827 vmem.freelist[flevel] = block->next;
828 if (vmem.freelist[flevel] != VADDR_NULL)
829 vmem.block_ptr(vmem.freelist[flevel])->prev = VADDR_NULL;
830 vaddr_t blockaddr2 = blockaddr + (1 << (flevel - 1));
831 Block *block2 = vmem.block_ptr(blockaddr2);
832 flevel--;
833 block2->next = vmem.freelist[flevel];
834 block2->prev = blockaddr;
835 block->next = blockaddr2;
836 block->prev = VADDR_NULL;
837 // block->prev == VADDR_NULL already.
838 vmem.freelist[flevel] = blockaddr;
839 }
840 assert(vmem.freelist[level] != VADDR_NULL);
841 Block *block = vmem.block_ptr(vmem.freelist[level]);
842 vaddr_t vaddr = vmem.freelist[level];
843 #if defined(__GNUC__) && (__GNUC__>11)
844 vaddr_t result = vaddr + (sizeof(vaddr_t)*2);
845 #else
846 vaddr_t result = vaddr + offsetof(Block, data);
847 #endif
848 vmem.freelist[level] = block->next;
849 if (block->next != VADDR_NULL)
850 vmem.block_ptr(block->next)->prev = VADDR_NULL;
851 block->mark_as_allocated(vaddr, level);
853 memset(block->data, 0, size);
854 return result;
855}
856
858 struct flock &lock_info, size_t offset, size_t len, bool lock) {
859 lock_info.l_start = offset;
860 lock_info.l_len = len;
861 lock_info.l_pid = 0;
862 lock_info.l_type = lock ? F_WRLCK : F_UNLCK;
863 lock_info.l_whence = SEEK_SET;
864}
865
866void lock_file(int fd, size_t offset, size_t len) {
867 struct flock lock_info;
870}
871
872void unlock_file(int fd, size_t offset, size_t len) {
873 struct flock lock_info;
874 init_flock_struct(lock_info, offset, len, false);
876}
877
878void lock_metapage() {
879 lock_file(vmem.fd, 0);
880}
881
882void unlock_metapage() {
883 unlock_file(vmem.fd, 0);
884}
885
886void init_metapage(bool create) {
887 if (create)
888 ftruncate(vmem.fd, METABLOCK_SIZE);
889 vmem.metapage = (MetaPage *) mmap(
890 NULL, METABLOCK_SIZE, PROT_READ | PROT_WRITE, MAP_SHARED, vmem.fd, 0);
891 if (create) {
892 std::memcpy(vmem.metapage->config_header, config, sizeof(config));
893 for (int i = 0; i <= LOG2_SEGMENT_SIZE; i++) {
894 vmem.metapage->freelist[i] = VADDR_NULL;
895 }
896 vmem.metapage->segment_count = 0;
897 vmem.metapage->allocator_lock = FastLock(metapageaddr(allocator_lock));
898 } else {
899 assert(std::memcmp(vmem.metapage->config_header, config,
900 sizeof(config)) != 0);
901 }
902}
903
904static void lock_process(int processno) {
905 lock_file(vmem.fd,
906 metapageaddr(process_info)
907 + sizeof(ProcessInfo) * vmem.current_process);
908}
909
910static void unlock_process(int processno) {
911 unlock_file(vmem.fd,
912 metapageaddr(process_info)
913 + sizeof(ProcessInfo) * vmem.current_process);
914}
915
916static ProcessInfo &process_info(int processno) {
917 return vmem.metapage->process_info[processno];
918}
919
920bool send_signal(int processno, ipc_signal_t sig, bool lock) {
921 if (lock)
923 if (process_info(processno).sigstate != Waiting) {
925 return false;
926 }
927 if (processno == vmem.current_process) {
928 process_info(processno).sigstate = Accepted;
929 process_info(processno).signal = sig;
930 } else {
931 process_info(processno).sigstate = Pending;
932 process_info(processno).signal = sig;
933 int fd = vmem.channels[processno].fd_write;
934 char buf[1] = { 0 };
935 while (write(fd, buf, 1) != 1) {
936 }
937 }
938 if (lock)
940 return true;
941}
942
943ipc_signal_t check_signal(bool resume, bool lock) {
945 if (lock)
946 lock_process(vmem.current_process);
947 SignalState sigstate = process_info(vmem.current_process).sigstate;
948 switch (sigstate) {
949 case Waiting:
950 case Pending: {
951 int fd = vmem.channels[vmem.current_process].fd_read;
952 char buf[1];
953 if (lock && sigstate == Waiting) {
954 unlock_process(vmem.current_process);
955 while (read(fd, buf, 1) != 1) {
956 }
957 lock_process(vmem.current_process);
958 } else {
959 while (read(fd, buf, 1) != 1) {
960 }
961 }
962 result = process_info(vmem.current_process).signal;
963 process_info(vmem.current_process).sigstate
964 = resume ? Waiting : Accepted;
965 if (lock)
966 unlock_process(vmem.current_process);
967 break;
968 }
969 case Accepted:
970 result = process_info(vmem.current_process).signal;
971 if (resume)
972 process_info(vmem.current_process).sigstate = Waiting;
973 if (lock)
974 unlock_process(vmem.current_process);
975 break;
976 }
977 return result;
978}
979
980void accept_signals() {
981 lock_process(vmem.current_process);
982 process_info(vmem.current_process).sigstate = Waiting;
983 unlock_process(vmem.current_process);
984}
985
986ipc_signal_t wait_signal(bool lock) {
987 return check_signal(true, lock);
988}
989
990} // namespace internals
991
993 using namespace internals;
995 for (int p = 0; p < MAX_PROCESS; p++) {
996 if (vmem.metapage->process_info[p].pid == 0) {
997 pid_t pid = fork();
998 if (pid < 0) {
999 // error
1000 return -1;
1001 } else if (pid == 0) {
1002 // child process
1003 int parent = vmem.current_process;
1004 vmem.current_process = p;
1005 lock_metapage();
1006 vmem.metapage->process_info[p].pid = getpid();
1008 send_signal(parent);
1009 } else {
1010 // parent process
1012 wait_signal();
1013 // child has unlocked metapage, so we don't need to.
1014 }
1015 return pid;
1016 }
1017 }
1019 return -1;
1020}
1021
1022void Semaphore::post() {
1023 int wakeup = -1;
1024 internals::ipc_signal_t sig;
1025 _lock.lock();
1026 if (_head == _tail) {
1027 _value++;
1028 } else {
1029 // don't increment value, as we'll pass that on to the next process.
1030 wakeup = _waiting[_head];
1031 sig = _signals[_head];
1032 next(_head);
1033 }
1034 _lock.unlock();
1035 if (wakeup >= 0) {
1036 internals::send_signal(wakeup, sig);
1037 }
1038}
1039
1040bool Semaphore::try_wait() {
1041 bool result = false;
1042 _lock.lock();
1043 if (_value > 0) {
1044 _value--;
1045 result = true;
1046 }
1047 _lock.unlock();
1048 return result;
1049}
1050
1051void Semaphore::wait() {
1052 _lock.lock();
1053 if (_value > 0) {
1054 _value--;
1055 _lock.unlock();
1056 return;
1057 }
1058 _waiting[_tail] = internals::vmem.current_process;
1059 _signals[_tail] = 0;
1060 next(_tail);
1061 _lock.unlock();
1062 internals::wait_signal();
1063}
1064
1065bool Semaphore::start_wait(internals::ipc_signal_t sig) {
1066 _lock.lock();
1067 if (_value > 0) {
1068 if (internals::send_signal(internals::vmem.current_process, sig))
1069 _value--;
1070 _lock.unlock();
1071 return false;
1072 }
1073 _waiting[_tail] = internals::vmem.current_process;
1074 _signals[_tail] = sig;
1075 next(_tail);
1076 _lock.unlock();
1077 return true;
1078}
1079
1080bool Semaphore::stop_wait() {
1081 bool result = false;
1082 _lock.lock();
1083 for (int i = _head; i != _tail; next(i)) {
1084 if (_waiting[i] == internals::vmem.current_process) {
1085 int last = i;
1086 next(i);
1087 while (i != _tail) {
1088 _waiting[last] = _waiting[i];
1089 _signals[last] = _signals[i];
1090 last = i;
1091 next(i);
1092 }
1093 _tail = last;
1094 result = true;
1095 break;
1096 }
1097 }
1098 _lock.unlock();
1099 return result;
1100}
1101
1102void EventSet::add(Event *event) {
1103 event->_next = NULL;
1104 if (_head == NULL) {
1105 _head = _tail = event;
1106 } else {
1107 _tail->_next = event;
1108 _tail = event;
1109 }
1110}
1111
1112int EventSet::wait() {
1113 size_t n = 0;
1114 for (Event *event = _head; event; event = event->_next) {
1115 if (!event->start_listen((int) (n++))) {
1116 break;
1117 }
1118 }
1119 internals::ipc_signal_t result = internals::check_signal();
1120 for (Event *event = _head; event; event = event->_next) {
1121 event->stop_listen();
1122 }
1123 internals::accept_signals();
1124 return (int) result;
1125}
1126
1127} // namespace vspace
1128#endif
1129#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
void wait()
Definition thread.cc:23
void post()
Definition thread.cc:33
return result
int j
Definition facHensel.cc:110
STATIC_VAR poly last
Definition hdegree.cc:1172
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:115
void init()
Definition lintree.cc:864
void accept_signals()
Definition vspace.cc:981
void unlock_metapage()
Definition vspace.cc:883
const vaddr_t VADDR_NULL
Definition vspace.h:1417
void init_flock_struct(struct flock &lock_info, size_t offset, size_t len, bool lock)
Definition vspace.cc:858
static ProcessInfo & process_info(int processno)
Definition vspace.cc:917
void lock_file(int fd, size_t offset, size_t len)
Definition vspace.cc:867
void vmem_free(vaddr_t vaddr)
Definition vspace.cc:756
Block * block_ptr(vaddr_t vaddr)
Definition vspace.h:1637
vaddr_t vmem_alloc(size_t size)
Definition vspace.cc:808
static void unlock_process(int processno)
Definition vspace.cc:911
static void lock_process(int processno)
Definition vspace.cc:905
ipc_signal_t wait_signal(bool lock)
Definition vspace.cc:987
void lock_metapage()
Definition vspace.cc:879
static void lock_allocator()
Definition vspace.cc:720
ipc_signal_t check_signal(bool resume, bool lock)
Definition vspace.cc:944
void init_metapage(bool create)
Definition vspace.cc:887
void unlock_file(int fd, size_t offset, size_t len)
Definition vspace.cc:873
bool send_signal(int processno, ipc_signal_t sig, bool lock)
Definition vspace.cc:921
static void unlock_allocator()
Definition vspace.cc:724
static void print_freelists()
Definition vspace.cc:728
pid_t fork_process()
Definition vspace.cc:993
internals::Mutex FastLock
Definition vspace.h:2340
#define NULL
Definition omList.c:12
#define block
Definition scanner.cc:646
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
#define assert(A)
Definition svd_si.h:3
#define metapageaddr(field)
Definition vspace.cc:580