epoll idea

This article provides a good introduction to epoll. The man page referred are epoll_create, epoll_ctl and epoll_wait.

General roadmap for epoll

The design below are assumed to be non-blocking. Among all the epoll syscalls, only epoll_wait can potentially block, but it is possible to make it non-blocking by setting 0 as timeout. In the first iteration only socketpair and eventfd can be monitored with epoll, but it can be extend to other file description afterwards.

• Step 1: Complete epoll_ctl: Add, update and delete fd from the interest list of epoll instance, throw error when appropriate.
• Step 2: "Poll" behaviour: Add functions to check if the events we supported occured in the file description. (relevant to event field of epoll_event struct below)
  1. EPOLLIN/EPOLLOUT: Check if input or output happened for eventfd and socketpair file description.
  2. EPOLLRDHUP: Check if the peer of socketpair is dropped.
• Step 3: Complete implementation for epoll_wait (This should be achievable after the two steps above are completed)

epoll_ctl shim idea

Introduction

pub unsafe extern "C" fn epoll_ctl(
    epfd: c_int,
    op: c_int,
    fd: c_int,
    event: *mut epoll_event
) -> c_int
// source: https://docs.rs/libc/latest/libc/fn.epoll_ctl.html

#[repr(C, packed(1))]
pub struct epoll_event {
    pub events: u32, /*epoll event (bitmasks)*/
    pub u64: u64,
}
//source: https://docs.rs/libc/latest/libc/struct.epoll_event.html

General description
epoll_ctl modifies the the interest list stored in the epoll instance pointed by epfd.

Function parameters for epoll_ctl

• epfd: The file descriptor of a epoll instance. An epoll instance can be created using epoll_create1.
• op: Operation to be performed, and either of the three flags below will be used here:
  • EPOLL_CTL_ADD: Add the file descriptor fd to the interest list, the set of events that we are interested in monitoring is pointed to by event.
  • EPOLL_CTL_MOD: Modify the event setting for fd, which means replacing original epoll_event associated with fd with event.
  • EPOLL_CTL_DEL: Remove fd from the interest list.
• fd: File descriptor in the interest list that should be modified.
• event: A pointer to epoll_event.
  • When EPOLL_CTL_ADD is used, the fd will be stored in the interest list together with this epoll_event
  • When EPOLL_CTL_MOD is used, the old epoll_event associated with fd will be replaced with this.
  • When EPOLL_CTL_DEL is used, event will be ignored.

Field description for epoll_event:

• events: A bit mask specifying events that we are interested in monitoring for fd.
  • EPOLLIN: read is possible on the file description.
  • EPOLLOUT: write is possible on the file description.
  • EPOLLRDHUP: Stream socket peer closed connection, or shut down writing half of connection.
  • EPOLLET: Employ edge-triggered event notification. (Explained in this section)
  • Unsupported by Miri: EPOLLONESHOT, EPOLLERR, EPOLLHUP… (TODO: add the remaining unsupported flags)
• u64: User can freely decide what to store in it, but it should only be a u64 (pointer will be rejected).

Edge triggered event notification

There are two models of notification for epoll:

• Edge-triggered event notification: Notification is provided if there has been I/O activity since the previous call to epoll_wait.
• Level-triggered event notification: Notification is provided if it is possible to do I/O without blocking.

By default, epoll employs level-triggered event notification, and edge-triggered event notification can be enabled using the EPOLLET flag. Since tokio use EPOLLET, only edge-triggered event notification will be implemented in the first iteration.

Epoll usage example in C

#include <sys/epoll.h>
#include <stdio.h>
#include <fcntl.h>
#include <unistd.h>
#include <errno.h>
#include <sys/socket.h>
#include <stdlib.h>

#define MAX_BUF     1000        /* Maximum bytes fetched by a single read() */
#define MAX_EVENTS     5        /* Maximum number of events to be returned from
                                   a single epoll_wait() call */
int main(int argc, char *argv[]) {

  int epfd;
  struct epoll_event ev;
  struct epoll_event evlist[MAX_EVENTS];
  int ready;
  char buf[MAX_BUF];

  epfd = epoll_create1(0);
  if (epfd == -1) {
    printf("error:epoll_create");
    return -1;
  }

  /* Open a socketpair, and add it to the "interest
     list" for the epoll instance */

  int sv[2]; // socketpair file descriptor 
  if (socketpair(AF_UNIX, SOCK_STREAM | SOCK_NONBLOCK, 0, sv) == -1) {
    perror("socketpair");
    exit(EXIT_FAILURE);
  }
  printf("opened a socketpair \n");

  write(sv[1], "a", 1);
  printf("write to socketpair \n");

  int fd = sv[0];
  // Set as edge-triggered 
  // Check if input happens. 
  ev.events = EPOLLIN | EPOLLET;            
  // libc has two definition for epoll_event, this is basically the u64 field specified above
  // https://man7.org/linux/man-pages/man3/epoll_event.3type.html
  ev.data.fd = fd;

  if (epoll_ctl(epfd, EPOLL_CTL_ADD, fd, &ev) == -1) {
    printf("err: epoll_ctl\n");
    printf("errno is %d \n", errno);
    return -1;
  }

  /* Fetch up to MAX_EVENTS items from the ready list */

  printf("About to epoll_wait \n");
  // ready returns number of events ready and stored in evlist. 
  ready = epoll_wait(epfd, evlist, MAX_EVENTS, 0);
  if (ready == -1) {
    printf("epoll_wait");
    return -1;
  }

  printf("Ready: %d\n", ready);

  /* Deal with returned list of events */

  for (int j = 0; j < ready; j++) {
      // If there is input, read from the fd. 
    if (evlist[j].events & EPOLLIN) {
      int s = read(evlist[j].data.fd, buf, MAX_BUF);
      if (s == -1) {
        printf("read \n");
        return -1;
      }
      printf("read %d bytes: %.*s\n", s, s, buf);

    }            
  }
  return 0;
}

This example is written to give a brief idea on how epoll is used and will be converted to a test after epoll_wait is completed.

Epoll semantics

1. If both EPOLLIN and EPOLLOUT is set, it will be considered ready if either input or output happens.

2. If an event is added in ready list, but did not return as ready by epoll_wait, then notification should be provided for the next epoll_wait call.

3. If a fd is dupped, and the intial file descriptor value is closed, as long as it is not removed from interest list through epoll_ctl, notification will still be provided.

4. edge case for epollrdhup:

   1. open a socketpair
   2. close one side
   3. register another side with EPOLLIN, EPOLLOUT, EPOLLRDHUP, EPOLLET
   4. call epoll_wait
   5. EPOLLIN, EPOLLOUT, EPOLLRDHUP reported.

5. The readiness of the file description will be check during insertion or when any event happened. Setting: register using EPOLLIN EPOLLOUT EPOLLRDHUP EPOLLET

   • Test: don't do anything on socketpair.

     • Result: EPOLLOUT triggered

   • Test: write to socketpair

     • Result: Both EPOLLIN and EPOLLOUT triggered

   • Test case: register -> write -> epoll_wait -> deregister -> epoll_wait

     • Result: Both epoll_wait returns EPOLLIN and EPOLLOUT (if without deregister, nothing will be returned in the second epoll_wait)

   • Test case: write to one side, epoll_wait, then close another side.

     • Result: First epoll_wait both EPOLLIN and EPOLLOUT is triggered, second epoll_wait EPOLLIN EPOLLOUT EPOLLRDUP is triggered. (On hold: this example is unexplainable)

6. Every time a file descriptor is registered / epoll_event is modified, we should return the flags representing the current state.

   • Test case: write then read then register.
     • Result: Only EPOLLOUT is triggered.
   • Test case: register -> write -> epoll_wait -> epoll_ctl_mod -> epoll_wait
     • Result: notification is provided for the second epoll_wait even though there is no event happened between two epoll_wait

7. We only return epoll_return only if there is event since the last return.

   • Test case: write to eventfd then epoll_wait, then epoll_wait again
     • Result: First time return both EPOLLIN and EPOLLOUT, second time return nothing.
   • Test case: write to socketpair then epoll_wait, then epoll_wait again
     • Result: First time return both EPOLLIN and EPOLLOUT, second time return nothing.
   • Test case: write to eventfd then epoll_wait, write again then epoll_wait
     • Result: Both epoll_wait returns EPOLLIN and EPOLLOUT (If an event occured, the readiness of all flags is checked again)

8. In socketpair, only the peer fd will be notified for all events (read/write/close).

9. In socketpair, read will trigger notification when the read call emptied the buffer. Although it is possible to have notification when the buffer is not completely empty. https://rust-lang.zulipchat.com/#narrow/stream/269128-miri/topic/epoll.20notification.20on.20socketpair.20write.20unblock/near/459694798

10. In edge-triggreed, The moment a file description is registered with epoll, it will trigger a notification. But if there is multiple epfd registered this file description, it will only wake up the one that registered it.

11. If multiple threads (or processes, if child processes have inherited the epoll file descriptor across fork(2)) are blocked in epoll_wait(2) waiting on the same epoll file descriptor and a file descriptor in the interest list that is marked for edge- triggered (EPOLLET) notification becomes ready, just one of the threads (or processes) is awoken from epoll_wait(2). This provides a useful optimization for avoiding "thundering herd" wake-ups in some scenarios.

12. To be perhaps clearer, epoll_wait() won't return an fd unless something changed on that socket, but if something did change, it returns all the flags representing the current state.

    • https://stackoverflow.com/questions/59288735/epoll-wait-return-epollout-even-with-epollet-flag

13. EPOLLER:

    • Socketpair register sv[0], write to sv[1], close sv[1]
    • won't trigger:
      • Write until eventfd blocks

14. Weird case

    • Register sv[0], close(sv[1]), write to sv[0], no notification?

Design overview

Step 1: epoll_ctl design

Unsupported operation
Only edge-triggered notification is supported, so if the EPOLLET flag is not used, throw_unsup_format will be used.

Related structs

struct Epoll {
    /// This is the list of file descriptions 
    // that we are interested in monitoring.
    // Each entry is identified using file descriptor value and 
    // rc address of file description. 
    interest_list: BTreeMap<(WeakFileDescriptor, i32), Rc<EpollEvent>>,
    // This is a list of events that is "ready"
    // Same as interest list, each entry of ready list
    // is identified using file descriptor value and 
    // the Rc address of file description. 
    ready_list: Rc<RefCell<BTreeMap<(WeakFileDescriptor, i32), EpollReturn>>>
}

struct EpollEvent {
    pub file_descriptor: i32,
    pub weak_file_descriptor: WeakFileDescriptor,
    // The file description associated with this epoll event.
    // Bitmask of the event type.
    events: u32,
    pub data: u64,
    // Ready list inherited from associated epoll instance.
    // This will enable us to update the ready list during 
    // read/write/close
    ready_list: Rc<RefCell<BTreeMap<(WeakFileDescriptor, i32), EpollReturn>>>
}

// This contains information that will be returned by epoll_wait, 
// and stored in ready list. 
// This is created because returned event don't have the same 
// event bitmask as EpollEvent. 
struct EpollReturn {
    // Events that happened to the file description
    events: u32,
    // Original data retrieved from ``epoll_event``
    data: u64,
}


struct SocketPair {
    writebuf: Weak<RefCell<Buffer>>,
    readbuf: Rc<RefCell<Buffer>>,
    // This is needed to notify peer file description
    // when a socketpair file description is closed. 
    peer_fd: WeakFileDescriptor,
    is_nonblock: bool,
    peer_closed: bool,
    // This is a list of ``epoll_events`` associated with 
    // this file description, registered under any epoll instance. 
    epoll_events: Vec<Weak<EpollEvent>>,
}

struct Event {
    counter: u64,
    is_nonblock: bool,
    clock: VClock,
    epoll_events: Vec<Weak<EpollEvent>>,
}

epoll_ctl_add

• If the entry is already in the interest list, fail with EEXIST.
  • Add a new epoll_event to the interest list.
• Add the epoll_event to the file description.
• Check the readiness of current file descripion and add epoll_return to ready list if applicable.

epoll_ctl_mod

• If the entry is not in the interest list, fail with ENOENT.
• Check the readiness of current file descripion and add epoll_return to ready list if applicable.

epoll_ctl_del

• If the entry is not in the interest list, fail with ENOENT.
• Delete related entry in interest list and ready list.

Step 2: "poll" operation

"poll" operation here means checking the "readiness" of the file description (not the poll syscall).

For edge-triggered notification, we need to add EpollReturn to the ready list immediately event occured to the file description. To achieve this, during read/write/close, iterate through epoll_events in the file description, and add a new EpollReturn into the ready list if applicable. If the EpollReturn entry already exists, modify the event mask of that entry.

Notification should not be returned if there is no event between two epoll_wait call on the same epoll instance. So a epoll_return entry will be removed after being returned by epoll_wait

A list of details:

• Two different file descriptor value can point to the same file description.
• For every successful EPOLL_CTL_ADD call, exactly one epoll_event will be inserted to the interest list of that epoll instance.
• Every epoll_event in the same epoll instance must have a unique file descriptor value. But it is valid to have two epoll_event with same file descriptor value to exist in two different epoll instance.
• An epoll instance will be only be created during a epoll_create1 call.
• EpollReturn and EpollEvent has one to one relationship. An EpollEvent can only generate or update one and only oneEpollEvent in the ready list.
• EpollEvent of same Epoll interest will share the same ready_list.
• ready_list only contains the EpollReturn only if the epoll_event is considered "ready".
• A file description registered twice under an epoll instance should receive two notification at once if there is events on the file description.

Step 3: epoll_wait

pub unsafe extern "C" fn epoll_wait(
    epfd: c_int,
    events: *mut epoll_event,
    maxevents: c_int,
    timeout: c_int
) -> c_int

//source: https://docs.rs/libc/latest/libc/fn.epoll_wait.html

Function parameters:

• epfd: File descriptor of the epoll instance
• events: Ready events will be stored here
• maxevents: Maximum events that can be returned
• timeout: The maximum time that epoll_wait can block, currently only 0 will be supported.

When epoll_wait is called, we just return the ready list, but the operations below need to be done too:

• If there exists no file descriptor pointing to a file description in the interest list, that event should never be returned as ready. To achieve this, in epoll_wait, before returning, we can attempt to upgrade the file description in EpollReturn to check if the file description is closed. If it is closed, that particular EpollReturn entry will be discarded.

• After a an epoll_return is successfully return, it will be cleared from the ready_list, so no notification would be provided for the next epoll_wait if there is no event happened between the two epoll_wait. (We do this instead of clearing the whole ready_list because it is possible for some epoll_return to be not returned due to the limit imposed by max_events)

• If number of ready event > maxevents, we will only return the first maxevents number of them.

Enhancement:

• level-triggered notification
• Randomly wake up threads in edge-triggered mode