Data Structures
struct	Block

class	FastLock

struct	MetaPage

class	Mutex

struct	ProcessChannel

struct	ProcessInfo

struct	refcount_t

struct	VMem

struct	VSeg

Typedefs
typedef size_t	segaddr_t

typedef size_t	vaddr_t

typedef int	ipc_signal_t

Enumerations
enum	SignalState { Waiting = 0 , Pending = 1 , Accepted = 2 }

Functions
static void	lock_allocator ()

static void	unlock_allocator ()

static void	print_freelists ()

void	vmem_free (vaddr_t vaddr)

vaddr_t	vmem_alloc (size_t size)

void	init_flock_struct (struct flock &lock_info, size_t offset, size_t len, bool lock)

void	lock_file (int fd, size_t offset, size_t len)

void	unlock_file (int fd, size_t offset, size_t len)

void	lock_metapage ()

void	unlock_metapage ()

void	init_metapage (bool create)

static void	lock_process (int processno)

static void	unlock_process (int processno)

static ProcessInfo &	process_info (int processno)

bool	send_signal (int processno, ipc_signal_t sig, bool lock)

ipc_signal_t	check_signal (bool resume, bool lock)

void	accept_signals ()

ipc_signal_t	wait_signal (bool lock)

void	drop_pending_signals ()

Block *	block_ptr (vaddr_t vaddr)

static int	find_level (size_t size)

static segaddr_t	find_buddy (segaddr_t addr, int level)

static vaddr_t	allocated_ptr_to_vaddr (void *ptr)

Variables
size_t	config [4] = { METABLOCK_SIZE, MAX_PROCESS, SEGMENT_SIZE, MAX_SEGMENTS }

const segaddr_t	SEGADDR_NULL = ~(segaddr_t) 0

const vaddr_t	VADDR_NULL = ~(segaddr_t) 0

static const int	MAX_PROCESS = 64

static const size_t	METABLOCK_SIZE = 128 * 1024

static const int	LOG2_SEGMENT_SIZE = 28

static const int	LOG2_MAX_SEGMENTS = 10

static const size_t	MAX_SEGMENTS = 1 << LOG2_MAX_SEGMENTS

static const size_t	SEGMENT_SIZE = 1 << LOG2_SEGMENT_SIZE

static const size_t	SEGMENT_MASK = (SEGMENT_SIZE - 1)

static VMem &	vmem = VMem::vmem_global

Data Structure Documentation

◆ vspace::internals::MetaPage

struct vspace::internals::MetaPage

Definition at line 1508 of file vspace.h.

Data Fields
FastLock	allocator_lock
size_t	config_header[4]
vaddr_t	freelist[LOG2_SEGMENT_SIZE+1]
ProcessInfo	process_info[MAX_PROCESS]
int	segment_count

◆ vspace::internals::ProcessChannel

struct vspace::internals::ProcessChannel

Definition at line 1525 of file vspace.h.

Data Fields
int	fd_read
int	fd_write

◆ vspace::internals::ProcessInfo

struct vspace::internals::ProcessInfo

Definition at line 1499 of file vspace.h.

Data Fields
pid_t	pid
ipc_signal_t	signal
SignalState	sigstate

Typedef Documentation

◆ ipc_signal_t

typedef int vspace::internals::ipc_signal_t

Definition at line 1481 of file vspace.h.

◆ segaddr_t

typedef size_t vspace::internals::segaddr_t

Definition at line 1412 of file vspace.h.

◆ vaddr_t

typedef size_t vspace::internals::vaddr_t

Definition at line 1414 of file vspace.h.

Enumeration Type Documentation

◆ SignalState

enum vspace::internals::SignalState

Enumerator
Waiting
Pending
Accepted

Definition at line 1493 of file vspace.h.

                 {
  Waiting = 0,
  Pending = 1,
  Accepted = 2,
};

Function Documentation

◆ accept_signals()

void vspace::internals::accept_signals ( )

Definition at line 981 of file vspace.cc.

                      {
  lock_process(vmem.current_process);
  process_info(vmem.current_process).sigstate = Waiting;
  unlock_process(vmem.current_process);
}

◆ allocated_ptr_to_vaddr()

static vaddr_t vspace::internals::allocated_ptr_to_vaddr ( void * ptr )

inlinestatic

Definition at line 1697 of file vspace.h.

                                                        {
  char *addr = (char *) ptr - sizeof(Block);
  vaddr_t info = ((Block *) addr)->prev;
  int seg = info & (MAX_SEGMENTS - 1);
  unsigned char *segstart = vmem.segments[seg].base;
  size_t offset = (unsigned char *) ptr - segstart;
  return (seg << LOG2_SEGMENT_SIZE) | offset;
}

◆ block_ptr()

Block * vspace::internals::block_ptr ( vaddr_t vaddr )

inline

Definition at line 1637 of file vspace.h.

                                       {
  return vmem.block_ptr(vaddr);
}

◆ check_signal()

ipc_signal_t vspace::internals::check_signal	(	bool	resume,
		bool	lock
	)

Definition at line 944 of file vspace.cc.

                                                  {
  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);
        while (read(fd, buf, 1) != 1) {
        }
        lock_process(vmem.current_process);
      } else {
        while (read(fd, buf, 1) != 1) {
        }
      }
      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;
}

◆ drop_pending_signals()

void vspace::internals::drop_pending_signals ( )

◆ find_buddy()

static segaddr_t vspace::internals::find_buddy	(	segaddr_t	addr,
		int	level
	)

inlinestatic

Definition at line 1690 of file vspace.h.

                                                              {
  return addr ^ (1 << level);
}

◆ find_level()

static int vspace::internals::find_level ( size_t size )

inlinestatic

Definition at line 1681 of file vspace.h.

                                          {
  int level = 0;
  while ((1 << (level + 8)) <= size)
    level += 8;
  while ((1 << level) < size)
    level++;
  return level;
}

◆ init_flock_struct()

void vspace::internals::init_flock_struct	(	struct flock &	lock_info,
		size_t	offset,
		size_t	len,
		bool	lock
	)

Definition at line 858 of file vspace.cc.

                                                                   {
  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;
}

◆ init_metapage()

void vspace::internals::init_metapage ( bool create )

Definition at line 887 of file vspace.cc.

                                {
  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);
  }
}

◆ lock_allocator()

static void vspace::internals::lock_allocator ( )

static

Definition at line 720 of file vspace.cc.

                             {
  vmem.metapage->allocator_lock.lock();
}

◆ lock_file()

void vspace::internals::lock_file	(	int	fd,
		size_t	offset,
		size_t	len
	)

Definition at line 867 of file vspace.cc.

                                                  {
  struct flock lock_info;
  init_flock_struct(lock_info, offset, len, true);
  fcntl(fd, F_SETLKW, &lock_info);
}

◆ lock_metapage()

void vspace::internals::lock_metapage ( )

Definition at line 879 of file vspace.cc.

                     {
  lock_file(vmem.fd, 0);
}

◆ lock_process()

static void vspace::internals::lock_process ( int processno )

static

Definition at line 905 of file vspace.cc.

                                        {
  lock_file(vmem.fd,
      metapageaddr(process_info)
          + sizeof(ProcessInfo) * vmem.current_process);
}

◆ print_freelists()

static void vspace::internals::print_freelists ( )

static

Definition at line 728 of file vspace.cc.

                              {
  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);
}

◆ process_info()

static ProcessInfo & vspace::internals::process_info ( int processno )

static

Definition at line 917 of file vspace.cc.

                                                {
  return vmem.metapage->process_info[processno];
}

◆ send_signal()

bool vspace::internals::send_signal	(	int	processno,
		ipc_signal_t	sig,
		bool	lock
	)

Definition at line 921 of file vspace.cc.

                                                             {
  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;
}

◆ unlock_allocator()

static void vspace::internals::unlock_allocator ( )

static

Definition at line 724 of file vspace.cc.

                               {
  vmem.metapage->allocator_lock.unlock();
}

◆ unlock_file()

void vspace::internals::unlock_file	(	int	fd,
		size_t	offset,
		size_t	len
	)

Definition at line 873 of file vspace.cc.

                                                    {
  struct flock lock_info;
  init_flock_struct(lock_info, offset, len, false);
  fcntl(fd, F_SETLKW, &lock_info);
}

◆ unlock_metapage()

void vspace::internals::unlock_metapage ( )

Definition at line 883 of file vspace.cc.

                       {
  unlock_file(vmem.fd, 0);
}

◆ unlock_process()

static void vspace::internals::unlock_process ( int processno )

static

Definition at line 911 of file vspace.cc.

                                          {
  unlock_file(vmem.fd,
      metapageaddr(process_info)
          + sizeof(ProcessInfo) * vmem.current_process);
}

◆ vmem_alloc()

vaddr_t vspace::internals::vmem_alloc ( size_t size )

Definition at line 808 of file vspace.cc.

                                {
  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;
}

◆ vmem_free()

void vspace::internals::vmem_free ( vaddr_t vaddr )

Definition at line 756 of file vspace.cc.

                              {
  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();
}

◆ wait_signal()

ipc_signal_t vspace::internals::wait_signal ( bool lock )

Definition at line 987 of file vspace.cc.

                                    {
  return check_signal(true, lock);
}

Variable Documentation

◆ config

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

Definition at line 572 of file vspace.cc.

◆ LOG2_MAX_SEGMENTS

const int vspace::internals::LOG2_MAX_SEGMENTS = 10

static

Definition at line 1422 of file vspace.h.

◆ LOG2_SEGMENT_SIZE

const int vspace::internals::LOG2_SEGMENT_SIZE = 28

static

Definition at line 1421 of file vspace.h.

◆ MAX_PROCESS

const int vspace::internals::MAX_PROCESS = 64

static

Definition at line 1419 of file vspace.h.

◆ MAX_SEGMENTS

const size_t vspace::internals::MAX_SEGMENTS = 1 << LOG2_MAX_SEGMENTS

static

Definition at line 1423 of file vspace.h.

◆ METABLOCK_SIZE

const size_t vspace::internals::METABLOCK_SIZE = 128 * 1024

static

Definition at line 1420 of file vspace.h.

◆ SEGADDR_NULL

const segaddr_t vspace::internals::SEGADDR_NULL = ~(segaddr_t) 0

Definition at line 1416 of file vspace.h.

◆ SEGMENT_MASK

const size_t vspace::internals::SEGMENT_MASK = (SEGMENT_SIZE - 1)

static

Definition at line 1425 of file vspace.h.

◆ SEGMENT_SIZE

const size_t vspace::internals::SEGMENT_SIZE = 1 << LOG2_SEGMENT_SIZE

static

Definition at line 1424 of file vspace.h.

◆ VADDR_NULL

const vaddr_t vspace::internals::VADDR_NULL = ~(segaddr_t) 0

Definition at line 1417 of file vspace.h.

◆ vmem

VMem& vspace::internals::vmem = VMem::vmem_global

static

Definition at line 1635 of file vspace.h.

Data Structures

Typedefs

Enumerations

Functions

Variables

Data Structure Documentation

◆ vspace::internals::MetaPage

◆ vspace::internals::ProcessChannel

◆ vspace::internals::ProcessInfo

Typedef Documentation

◆ ipc_signal_t

◆ segaddr_t

◆ vaddr_t

Enumeration Type Documentation

◆ SignalState

Function Documentation

◆ accept_signals()

◆ allocated_ptr_to_vaddr()

◆ block_ptr()

◆ check_signal()

◆ drop_pending_signals()

◆ find_buddy()

◆ find_level()

◆ init_flock_struct()

◆ init_metapage()

◆ lock_allocator()

◆ lock_file()

◆ lock_metapage()

◆ lock_process()

◆ print_freelists()

◆ process_info()

◆ send_signal()

◆ unlock_allocator()

◆ unlock_file()

◆ unlock_metapage()

◆ unlock_process()

◆ vmem_alloc()

◆ vmem_free()

◆ wait_signal()

Variable Documentation

◆ config

◆ LOG2_MAX_SEGMENTS

◆ LOG2_SEGMENT_SIZE

◆ MAX_PROCESS

◆ MAX_SEGMENTS

◆ METABLOCK_SIZE

◆ SEGADDR_NULL

◆ SEGMENT_MASK

◆ SEGMENT_SIZE

◆ VADDR_NULL

◆ vmem