# epoll idea
[This article](https://copyconstruct.medium.com/the-method-to-epolls-madness-d9d2d6378642) provides a good introduction to ``epoll``. The man page referred are [epoll_create](https://man7.org/linux/man-pages/man2/epoll_create.2.html), [epoll_ctl](https://man7.org/linux/man-pages/man2/epoll_ctl.2.html) and [epoll_wait](https://man7.org/linux/man-pages/man2/epoll_wait.2.html).
## 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.
- [x] **Step 1:** Complete ``epoll_ctl``: Add, update and delete ``fd`` from the interest list of ``epoll`` instance, throw error when appropriate.
- [x] **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.
- [x] **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](#Edge-triggered-event-notification))
- 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.
1. 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.
1. 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.
1. 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.
1. 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)
1. 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
1. 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)
1. 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 one``EpollEvent`` 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