Provide support for epoll
[akaros.git] / user / iplib / epoll.c
1 /* Copyright (c) 2015 Google Inc.
2  * Barret Rhoden <brho@cs.berkeley.edu>
3  * See LICENSE for details.
4  *
5  * Epoll, built on FD taps, CEQs, and blocking uthreads on event queues.
6  *
7  * TODO: There are a few incompatibilities with Linux's epoll, some of which are
8  * artifacts of the implementation, and other issues:
9  *      - you can't epoll on an epoll fd (or any user fd).  you can only epoll on a
10  *      kernel FD that accepts your FD taps.
11  *      - there's no EPOLLONESHOT or level-triggered support.
12  *      - you can only tap one FD at a time, so you can't add the same FD to
13  *      multiple epoll sets.
14  *      - there is no support for growing the epoll set.
15  *      - closing the epoll is a little dangerous, if there are outstanding INDIR
16  *      events.  this will only pop up if you're yielding cores, maybe getting
17  *      preempted, and are unlucky.
18  *      - epoll_create1 does not support CLOEXEC.  That'd need some work in glibc's
19  *      exec and flags in struct user_fd.
20  *      - EPOLL_CTL_MOD is just a DEL then an ADD.  There might be races associated
21  *      with that.
22  *      - If you close a tracked FD without removing it from the epoll set, the
23  *      kernel will turn off the FD tap.  You may still have an epoll event that was
24  *      concurrently sent.  Likewise, that FD may be used again by your program, and
25  *      if you add *that* one to another epoll set before removing it from the
26  *      current one, weird things may happen (like having two epoll ctlrs turning on
27  *      and off taps).
28  *      - epoll_pwait is probably racy.
29  *      - Using spin locks instead of mutexes during syscalls that could block.  The
30  *      process won't deadlock, but it will busy wait on something like an RPC,
31  *      depending on the device being tapped.
32  *      - You can't dup an epoll fd (same as other user FDs).
33  * */
34
35 #include <sys/epoll.h>
36 #include <parlib/parlib.h>
37 #include <parlib/event.h>
38 #include <parlib/ceq.h>
39 #include <parlib/uthread.h>
40 #include <parlib/spinlock.h>
41 #include <parlib/timing.h>
42 #include <sys/user_fd.h>
43 #include <stdio.h>
44 #include <errno.h>
45
46 /* Sanity check, so we can ID our own FDs */
47 #define EPOLL_UFD_MAGIC                 0xe9011
48
49 struct epoll_ctlr {
50         struct event_queue                      *ceq_evq;
51         struct ceq                                      *ceq;   /* convenience pointer */
52         unsigned int                            size;
53         struct spin_pdr_lock            lock;
54         struct user_fd                          ufd;
55 };
56
57 /* There's some bookkeeping we need to maintain on every FD.  Right now, the FD
58  * is the index into the CEQ event array, so we can just hook this into the user
59  * data blob in the ceq_event.
60  *
61  * If we ever do not maintain a 1:1 mapping from FDs to CEQ IDs, we can use this
62  * to track the CEQ ID and FD. */
63 struct ep_fd_data {
64         struct epoll_event                      ep_event;
65         int                                                     fd;
66         int                                                     filter;
67 };
68
69 /* Converts epoll events to FD taps. */
70 static int ep_events_to_taps(uint32_t ep_ev)
71 {
72         int taps = 0;
73         if (ep_ev & EPOLLIN)
74                 taps |= FDTAP_FILT_READABLE;
75         if (ep_ev & EPOLLOUT)
76                 taps |= FDTAP_FILT_WRITABLE;
77         if (ep_ev & EPOLLRDHUP)
78                 taps |= FDTAP_FILT_RDHUP;
79         if (ep_ev & EPOLLPRI)
80                 taps |= FDTAP_FILT_PRIORITY;
81         if (ep_ev & EPOLLERR)
82                 taps |= FDTAP_FILT_ERROR;
83         if (ep_ev & EPOLLHUP)
84                 taps |= FDTAP_FILT_HANGUP;
85         return taps;
86 }
87
88 /* Converts corresponding FD Taps to epoll events.  There are other taps that do
89  * not make sense for epoll. */
90 static uint32_t taps_to_ep_events(int taps)
91 {
92         uint32_t ep_ev = 0;
93         if (taps & FDTAP_FILT_READABLE)
94                 ep_ev |= EPOLLIN;
95         if (taps & FDTAP_FILT_WRITABLE)
96                 ep_ev |= EPOLLOUT;
97         if (taps & FDTAP_FILT_RDHUP)
98                 ep_ev |= EPOLLRDHUP;
99         if (taps & FDTAP_FILT_PRIORITY)
100                 ep_ev |= EPOLLPRI;
101         if (taps & FDTAP_FILT_ERROR)
102                 ep_ev |= EPOLLERR;
103         if (taps & FDTAP_FILT_HANGUP)
104                 ep_ev |= EPOLLHUP;
105         return ep_ev;
106 }
107
108 static struct ceq_event *ep_get_ceq_ev(struct epoll_ctlr *ep, size_t idx)
109 {
110         if (ep->ceq_evq->ev_mbox->ceq.nr_events <= idx)
111                 return 0;
112         return &ep->ceq_evq->ev_mbox->ceq.events[idx];
113 }
114
115 static struct epoll_ctlr *fd_to_cltr(int fd)
116 {
117         struct user_fd *ufd = ufd_lookup(fd);
118         if (!ufd)
119                 return 0;
120         if (ufd->magic != EPOLL_UFD_MAGIC) {
121                 errno = EBADF;
122                 return 0;
123         }
124         return container_of(ufd, struct epoll_ctlr, ufd);
125 }
126
127 /* Event queue helpers: */
128 static struct event_queue *ep_get_ceq_evq(unsigned int ceq_size)
129 {
130         struct event_queue *ceq_evq = get_eventq_raw();
131         ceq_evq->ev_mbox->type = EV_MBOX_CEQ;
132         ceq_init(&ceq_evq->ev_mbox->ceq, CEQ_OR, ceq_size, ceq_size);
133         ceq_evq->ev_flags = EVENT_INDIR | EVENT_SPAM_INDIR | EVENT_WAKEUP;
134         evq_attach_wakeup_ctlr(ceq_evq);
135         return ceq_evq;
136 }
137
138 static struct event_queue *ep_get_alarm_evq(void)
139 {
140         /* Don't care about the actual message, just using it for a wakeup */
141         struct event_queue *alarm_evq = get_eventq(EV_MBOX_BITMAP);
142         alarm_evq->ev_flags = EVENT_INDIR | EVENT_SPAM_INDIR | EVENT_WAKEUP;
143         evq_attach_wakeup_ctlr(alarm_evq);
144         return alarm_evq;
145 }
146
147 /* Once we've closed our sources of events, we can try to clean up the event
148  * queues.  These are actually dangerous, since there could be INDIRs floating
149  * around for these evqs still, which are basically pointers.  We'll need to run
150  * some sort of user deferred destruction. (TODO). */
151 static void ep_put_ceq_evq(struct event_queue *ceq_evq)
152 {
153         ceq_cleanup(&ceq_evq->ev_mbox->ceq);
154         evq_remove_wakeup_ctlr(ceq_evq);
155         put_eventq_raw(ceq_evq);
156 }
157
158 static void ep_put_alarm_evq(struct event_queue *alarm_evq)
159 {
160         evq_remove_wakeup_ctlr(alarm_evq);
161         put_eventq(alarm_evq);
162 }
163
164 static void epoll_close(struct user_fd *ufd)
165 {
166         struct epoll_ctlr *ep = container_of(ufd, struct epoll_ctlr, ufd);
167         struct fd_tap_req *tap_reqs, *tap_req_i;
168         struct ceq_event *ceq_ev_i;
169         struct ep_fd_data *ep_fd_i;
170         int nr_tap_req = 0;
171         int nr_done = 0;
172
173         tap_reqs = malloc(sizeof(struct fd_tap_req) * ep->size);
174         memset(tap_reqs, 0, sizeof(struct fd_tap_req) * ep->size);
175         /* Slightly painful, O(n) with no escape hatch */
176         for (int i = 0; i < ep->size; i++) {
177                 ceq_ev_i = ep_get_ceq_ev(ep, i);
178                 /* CEQ should have been big enough for our size */
179                 assert(ceq_ev_i);
180                 ep_fd_i = (struct ep_fd_data*)ceq_ev_i->user_data;
181                 if (!ep_fd_i)
182                         continue;
183                 tap_req_i = &tap_reqs[nr_tap_req++];
184                 tap_req_i->fd = i;
185                 tap_req_i->cmd = FDTAP_CMD_REM;
186                 free(ep_fd_i);
187         }
188         /* Requests could fail if the tapped files are already closed.  We need to
189          * skip the failed one (the +1) and untap the rest. */
190         do {
191                 nr_done += sys_tap_fds(tap_reqs + nr_done, nr_tap_req - nr_done);
192                 nr_done += 1;   /* nr_done could be more than nr_tap_req now */
193         } while (nr_done < nr_tap_req);
194         free(tap_reqs);
195         ep_put_ceq_evq(ep->ceq_evq);
196 }
197
198 static int init_ep_ctlr(struct epoll_ctlr *ep, int size)
199 {
200         unsigned int ceq_size = ROUNDUPPWR2(size);
201         /* TODO: we don't grow yet.  Until then, we help out a little. */
202         if (size == 1)
203                 size = 128;
204         ep->size = ceq_size;
205         spin_pdr_init(&ep->lock);
206         ep->ufd.magic = EPOLL_UFD_MAGIC;
207         ep->ufd.close = epoll_close;
208         ep->ceq_evq = ep_get_ceq_evq(ceq_size);
209         return 0;
210 }
211
212 int epoll_create(int size)
213 {
214         int fd;
215         struct epoll_ctlr *ep;
216         /* good thing the arg is a signed int... */
217         if (size < 0) {
218                 errno = EINVAL;
219                 return -1;
220         }
221         ep = malloc(sizeof(struct epoll_ctlr));
222         memset(ep, 0, sizeof(struct epoll_ctlr));
223         if (init_ep_ctlr(ep, size)) {
224                 free(ep);
225                 return -1;
226         }
227         fd = ufd_get_fd(&ep->ufd);
228         if (fd < 0)
229                 free(ep);
230         return fd;
231 }
232
233 int epoll_create1(int flags)
234 {
235         /* TODO: we're supposed to support CLOEXEC.  Our FD is a user_fd, so that'd
236          * require some support in glibc's exec to close our epoll ctlr. */
237         return epoll_create(1);
238 }
239
240 static int __epoll_ctl_add(struct epoll_ctlr *ep, int fd,
241                            struct epoll_event *event)
242 {
243         struct ceq_event *ceq_ev;
244         struct ep_fd_data *ep_fd;
245         struct fd_tap_req tap_req = {0};
246         int ret, filter;
247
248         /* Only support ET.  Also, we just ignore EPOLLONESHOT.  That might work,
249          * logically, just with spurious events firing. */
250         if (!(event->events & EPOLLET)) {
251                 errno = EPERM;
252                 werrstr("Epoll level-triggered not supported");
253                 return -1;
254         }
255         ceq_ev = ep_get_ceq_ev(ep, fd);
256         if (!ceq_ev) {
257                 errno = ENOMEM;
258                 werrstr("Epoll set cannot grow yet!");
259                 return -1;
260         }
261         ep_fd = (struct ep_fd_data*)ceq_ev->user_data;
262         if (ep_fd) {
263                 errno = EEXIST;
264                 return -1;
265         }
266         tap_req.fd = fd;
267         tap_req.cmd = FDTAP_CMD_ADD;
268         /* EPOLLHUP is implicitly set for all epolls. */
269         filter = ep_events_to_taps(event->events | EPOLLHUP);
270         tap_req.filter = filter;
271         tap_req.ev_q = ep->ceq_evq;
272         tap_req.ev_id = fd;     /* using FD as the CEQ ID */
273         ret = sys_tap_fds(&tap_req, 1);
274         if (ret != 1)
275                 return -1;
276         ep_fd = malloc(sizeof(struct ep_fd_data));
277         ep_fd->fd = fd;
278         ep_fd->filter = filter;
279         ep_fd->ep_event = *event;
280         ep_fd->ep_event.events |= EPOLLHUP;
281         ceq_ev->user_data = (uint64_t)ep_fd;
282         return 0;
283 }
284
285 static int __epoll_ctl_del(struct epoll_ctlr *ep, int fd,
286                            struct epoll_event *event)
287 {
288         struct ceq_event *ceq_ev;
289         struct ep_fd_data *ep_fd;
290         struct fd_tap_req tap_req = {0};
291         int ret;
292
293         ceq_ev = ep_get_ceq_ev(ep, fd);
294         if (!ceq_ev) {
295                 errno = ENOENT;
296                 return -1;
297         }
298         ep_fd = (struct ep_fd_data*)ceq_ev->user_data;
299         if (!ep_fd) {
300                 errno = ENOENT;
301                 return -1;
302         }
303         assert(ep_fd->fd == fd);
304         tap_req.fd = fd;
305         tap_req.cmd = FDTAP_CMD_REM;
306         /* ignoring the return value; we could have failed to remove it if the FD
307          * has already closed and the kernel removed the tap. */
308         sys_tap_fds(&tap_req, 1);
309         ceq_ev->user_data = 0;
310         free(ep_fd);
311         return 0;
312 }
313
314 int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event)
315 {
316         int ret;
317         struct epoll_ctlr *ep = fd_to_cltr(epfd);
318         if (!ep) {
319                 errno = EBADF;/* or EINVAL */
320                 return -1;
321         }
322         if (fd >= USER_FD_BASE) {
323                 errno = EINVAL;
324                 werrstr("Epoll can't track User FDs");
325                 return -1;
326         }
327         /* TODO: don't use a spinlock, use a mutex.  sys_tap_fds can block. */
328         spin_pdr_lock(&ep->lock);
329         switch (op) {
330                 case (EPOLL_CTL_MOD):
331                         /* In lieu of a proper MOD, just remove and readd.  The errors might
332                          * not work out well, and there could be a missed event in the
333                          * middle.  Not sure what the guarantees are, but we can fake a
334                          * poke. (TODO). */
335                         ret = __epoll_ctl_del(ep, fd, 0);
336                         if (ret)
337                                 break;
338                         ret = __epoll_ctl_add(ep, fd, event);
339                         break;
340                 case (EPOLL_CTL_ADD):
341                         ret = __epoll_ctl_add(ep, fd, event);
342                         break;
343                 case (EPOLL_CTL_DEL):
344                         ret = __epoll_ctl_del(ep, fd, event);
345                         break;
346                 default:
347                         errno = EINVAL;
348                         ret = -1;
349         }
350         spin_pdr_unlock(&ep->lock);
351         return ret;
352 }
353
354 static bool get_ep_event_from_msg(struct epoll_ctlr *ep, struct event_msg *msg,
355                                   struct epoll_event *ep_ev)
356 {
357         struct ceq_event *ceq_ev;
358         struct ep_fd_data *ep_fd;
359
360         ceq_ev = ep_get_ceq_ev(ep, msg->ev_type);
361         /* should never get a tap FD > size of the epoll set */
362         assert(ceq_ev);
363         ep_fd = (struct ep_fd_data*)ceq_ev->user_data;
364         if (!ep_fd) {
365                 /* it's possible the FD was unregistered and this was an old
366                  * event sent to this epoll set. */
367                 return FALSE;
368         }
369         ep_ev->data = ep_fd->ep_event.data;
370         ep_ev->events = taps_to_ep_events(msg->ev_arg2);
371         return TRUE;
372 }
373
374 /* We should be able to have multiple waiters.  ep shouldn't be closed or
375  * anything, since we have the FD (that'd be bad programming on the user's
376  * behalf).  We could have concurrent ADD/MOD/DEL operations (which lock). */
377 static int __epoll_wait(struct epoll_ctlr *ep, struct epoll_event *events,
378                         int maxevents, int timeout)
379 {
380         struct event_msg msg = {0};
381         struct event_msg dummy_msg;
382         struct event_queue *which_evq;
383         struct event_queue *alarm_evq;
384         int nr_ret = 0;
385         int recurse_ret;
386         struct syscall sysc;
387
388         /* Locking to protect get_ep_event_from_msg, specifically that the ep_fd
389          * stored at ceq_ev->user_data does not get concurrently removed and
390          * freed. */
391         spin_pdr_lock(&ep->lock);
392         for (int i = 0; i < maxevents; i++) {
393                 if (uth_check_evqs(&msg, &which_evq, 1, ep->ceq_evq)) {
394                         if (get_ep_event_from_msg(ep, &msg, &events[i]))
395                                 nr_ret++;
396                 }
397         }
398         spin_pdr_unlock(&ep->lock);
399         if (nr_ret)
400                 return nr_ret;
401         if (timeout == 0)
402                 return 0;
403         if (timeout != -1) {
404                 alarm_evq = ep_get_alarm_evq();
405                 syscall_async(&sysc, SYS_block, timeout * 1000);
406                 if (!register_evq(&sysc, alarm_evq)) {
407                         /* timeout occurred before we could even block! */
408                         ep_put_alarm_evq(alarm_evq);
409                         return 0;
410                 }
411                 uth_blockon_evqs(&msg, &which_evq, 2, ep->ceq_evq, alarm_evq);
412                 if (which_evq != alarm_evq) {
413                         /* sysc may or may not have finished yet.  this will force it to
414                          * *start* to finish iff it is still a submitted syscall. */
415                         sys_abort_sysc(&sysc);
416                         /* But we still need to wait until the syscall completed.  Need a
417                          * dummy msg, since we don't want to clobber the real msg. */
418                         uth_blockon_evqs(&dummy_msg, 0, 1, alarm_evq);
419                 }
420                 /* TODO: Slightly dangerous, due to spammed INDIRs */
421                 ep_put_alarm_evq(alarm_evq);
422                 if (which_evq == alarm_evq)
423                         return 0;
424         } else {
425                 uth_blockon_evqs(&msg, &which_evq, 1, ep->ceq_evq);
426         }
427         spin_pdr_lock(&ep->lock);
428         if (get_ep_event_from_msg(ep, &msg, &events[0]))
429                 nr_ret++;
430         spin_pdr_unlock(&ep->lock);
431         /* We might not have gotten one yet.  And regardless, there might be more
432          * available.  Let's try again, with timeout == 0 to ensure no blocking.  We
433          * use nr_ret (0 or 1 now) to adjust maxevents and events accordingly. */
434         recurse_ret = __epoll_wait(ep, events + nr_ret, maxevents - nr_ret, 0);
435         if (recurse_ret > 0)
436                 nr_ret += recurse_ret;
437         return nr_ret;
438 }
439
440 int epoll_wait(int epfd, struct epoll_event *events, int maxevents,
441                int timeout)
442 {
443         struct epoll_ctlr *ep = fd_to_cltr(epfd);
444         int ret;
445         if (!ep) {
446                 errno = EBADF;/* or EINVAL */
447                 return -1;
448         }
449         if (maxevents <= 0) {
450                 errno = EINVAL;
451                 return -1;
452         }
453         ret = __epoll_wait(ep, events, maxevents, timeout);
454         return ret;
455 }
456
457 int epoll_pwait(int epfd, struct epoll_event *events, int maxevents,
458                 int timeout, const sigset_t *sigmask)
459 {
460         int ready;
461         sigset_t origmask;
462         /* TODO: this is probably racy */
463         sigprocmask(SIG_SETMASK, sigmask, &origmask);
464         ready = epoll_wait(epfd, events, maxevents, timeout);
465         sigprocmask(SIG_SETMASK, &origmask, NULL);
466         return ready;
467 }