de59bdb21e320fb7c342bfc3e60ac19607ca3b80
[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  *      - epoll_pwait is probably racy.
23  *      - You can't dup an epoll fd (same as other user FDs).
24  *      - If you add a BSD socket FD to an epoll set, you'll get taps on both the
25  *      data FD and the listen FD.
26  *      - If you add the same BSD socket listener to multiple epoll sets, you will
27  *      likely fail.  This is in addition to being able to tap only one FD at a
28  *      time.
29  * */
30
31 #include <sys/epoll.h>
32 #include <parlib/parlib.h>
33 #include <parlib/event.h>
34 #include <parlib/ceq.h>
35 #include <parlib/uthread.h>
36 #include <parlib/timing.h>
37 #include <sys/user_fd.h>
38 #include <sys/close_cb.h>
39 #include <stdio.h>
40 #include <errno.h>
41 #include <unistd.h>
42 #include <malloc.h>
43 #include <sys/queue.h>
44 #include <sys/plan9_helpers.h>
45
46 /* Sanity check, so we can ID our own FDs */
47 #define EPOLL_UFD_MAGIC                 0xe9011
48
49 struct epoll_ctlr {
50         TAILQ_ENTRY(epoll_ctlr)         link;
51         struct event_queue                      *ceq_evq;
52         struct ceq                                      *ceq;   /* convenience pointer */
53         unsigned int                            size;
54         uth_mutex_t                                     mtx;
55         struct user_fd                          ufd;
56 };
57
58 TAILQ_HEAD(epoll_ctlrs, epoll_ctlr);
59 static struct epoll_ctlrs all_ctlrs = TAILQ_HEAD_INITIALIZER(all_ctlrs);
60 static uth_mutex_t ctlrs_mtx;
61
62 /* There's some bookkeeping we need to maintain on every FD.  Right now, the FD
63  * is the index into the CEQ event array, so we can just hook this into the user
64  * data blob in the ceq_event.
65  *
66  * If we ever do not maintain a 1:1 mapping from FDs to CEQ IDs, we can use this
67  * to track the CEQ ID and FD. */
68 struct ep_fd_data {
69         struct epoll_event                      ep_event;
70         int                                                     fd;
71         int                                                     filter;
72 };
73
74 /* Converts epoll events to FD taps. */
75 static int ep_events_to_taps(uint32_t ep_ev)
76 {
77         int taps = 0;
78         if (ep_ev & EPOLLIN)
79                 taps |= FDTAP_FILT_READABLE;
80         if (ep_ev & EPOLLOUT)
81                 taps |= FDTAP_FILT_WRITABLE;
82         if (ep_ev & EPOLLRDHUP)
83                 taps |= FDTAP_FILT_RDHUP;
84         if (ep_ev & EPOLLPRI)
85                 taps |= FDTAP_FILT_PRIORITY;
86         if (ep_ev & EPOLLERR)
87                 taps |= FDTAP_FILT_ERROR;
88         if (ep_ev & EPOLLHUP)
89                 taps |= FDTAP_FILT_HANGUP;
90         return taps;
91 }
92
93 /* Converts corresponding FD Taps to epoll events.  There are other taps that do
94  * not make sense for epoll. */
95 static uint32_t taps_to_ep_events(int taps)
96 {
97         uint32_t ep_ev = 0;
98         if (taps & FDTAP_FILT_READABLE)
99                 ep_ev |= EPOLLIN;
100         if (taps & FDTAP_FILT_WRITABLE)
101                 ep_ev |= EPOLLOUT;
102         if (taps & FDTAP_FILT_RDHUP)
103                 ep_ev |= EPOLLRDHUP;
104         if (taps & FDTAP_FILT_PRIORITY)
105                 ep_ev |= EPOLLPRI;
106         if (taps & FDTAP_FILT_ERROR)
107                 ep_ev |= EPOLLERR;
108         if (taps & FDTAP_FILT_HANGUP)
109                 ep_ev |= EPOLLHUP;
110         return ep_ev;
111 }
112
113 static struct ceq_event *ep_get_ceq_ev(struct epoll_ctlr *ep, size_t idx)
114 {
115         if (ep->ceq_evq->ev_mbox->ceq.nr_events <= idx)
116                 return 0;
117         return &ep->ceq_evq->ev_mbox->ceq.events[idx];
118 }
119
120 static struct epoll_ctlr *fd_to_cltr(int fd)
121 {
122         struct user_fd *ufd = ufd_lookup(fd);
123         if (!ufd)
124                 return 0;
125         if (ufd->magic != EPOLL_UFD_MAGIC) {
126                 errno = EBADF;
127                 return 0;
128         }
129         return container_of(ufd, struct epoll_ctlr, ufd);
130 }
131
132 /* Event queue helpers: */
133 static struct event_queue *ep_get_ceq_evq(unsigned int ceq_size)
134 {
135         struct event_queue *ceq_evq = get_eventq_raw();
136         ceq_evq->ev_mbox->type = EV_MBOX_CEQ;
137         ceq_init(&ceq_evq->ev_mbox->ceq, CEQ_OR, ceq_size, ceq_size);
138         ceq_evq->ev_flags = EVENT_INDIR | EVENT_SPAM_INDIR | EVENT_WAKEUP;
139         evq_attach_wakeup_ctlr(ceq_evq);
140         return ceq_evq;
141 }
142
143 static struct event_queue *ep_get_alarm_evq(void)
144 {
145         /* Don't care about the actual message, just using it for a wakeup */
146         struct event_queue *alarm_evq = get_eventq(EV_MBOX_BITMAP);
147         alarm_evq->ev_flags = EVENT_INDIR | EVENT_SPAM_INDIR | EVENT_WAKEUP;
148         evq_attach_wakeup_ctlr(alarm_evq);
149         return alarm_evq;
150 }
151
152 /* Once we've closed our sources of events, we can try to clean up the event
153  * queues.  These are actually dangerous, since there could be INDIRs floating
154  * around for these evqs still, which are basically pointers.  We'll need to run
155  * some sort of user deferred destruction. (TODO). */
156 static void ep_put_ceq_evq(struct event_queue *ceq_evq)
157 {
158 #if 0 /* TODO: EVQ/INDIR Cleanup */
159         ceq_cleanup(&ceq_evq->ev_mbox->ceq);
160         evq_remove_wakeup_ctlr(ceq_evq);
161         put_eventq_raw(ceq_evq);
162 #endif
163 }
164
165 static void ep_put_alarm_evq(struct event_queue *alarm_evq)
166 {
167 #if 0 /* TODO: EVQ/INDIR Cleanup */
168         evq_remove_wakeup_ctlr(alarm_evq);
169         put_eventq(alarm_evq);
170 #endif
171 }
172
173 static void epoll_close(struct user_fd *ufd)
174 {
175         struct epoll_ctlr *ep = container_of(ufd, struct epoll_ctlr, ufd);
176         struct fd_tap_req *tap_reqs, *tap_req_i;
177         struct ceq_event *ceq_ev_i;
178         struct ep_fd_data *ep_fd_i;
179         int nr_tap_req = 0;
180         int nr_done = 0;
181
182         tap_reqs = malloc(sizeof(struct fd_tap_req) * ep->size);
183         memset(tap_reqs, 0, sizeof(struct fd_tap_req) * ep->size);
184         /* Slightly painful, O(n) with no escape hatch */
185         for (int i = 0; i < ep->size; i++) {
186                 ceq_ev_i = ep_get_ceq_ev(ep, i);
187                 /* CEQ should have been big enough for our size */
188                 assert(ceq_ev_i);
189                 ep_fd_i = (struct ep_fd_data*)ceq_ev_i->user_data;
190                 if (!ep_fd_i)
191                         continue;
192                 tap_req_i = &tap_reqs[nr_tap_req++];
193                 tap_req_i->fd = i;
194                 tap_req_i->cmd = FDTAP_CMD_REM;
195                 free(ep_fd_i);
196         }
197         /* Requests could fail if the tapped files are already closed.  We need to
198          * skip the failed one (the +1) and untap the rest. */
199         do {
200                 nr_done += sys_tap_fds(tap_reqs + nr_done, nr_tap_req - nr_done);
201                 nr_done += 1;   /* nr_done could be more than nr_tap_req now */
202         } while (nr_done < nr_tap_req);
203         free(tap_reqs);
204         ep_put_ceq_evq(ep->ceq_evq);
205         uth_mutex_lock(ctlrs_mtx);
206         TAILQ_REMOVE(&all_ctlrs, ep, link);
207         uth_mutex_unlock(ctlrs_mtx);
208         uth_mutex_free(ep->mtx);
209         free(ep);
210 }
211
212 static int init_ep_ctlr(struct epoll_ctlr *ep, int size)
213 {
214         unsigned int ceq_size;
215
216         /* TODO: we don't grow yet.  Until then, we help out a little. */
217         if (size == 1)
218                 size = 128;
219         ceq_size = ROUNDUPPWR2(size);
220         ep->size = ceq_size;
221         ep->mtx = uth_mutex_alloc();
222         ep->ufd.magic = EPOLL_UFD_MAGIC;
223         ep->ufd.close = epoll_close;
224         ep->ceq_evq = ep_get_ceq_evq(ceq_size);
225         return 0;
226 }
227
228 static void epoll_fd_closed(int fd)
229 {
230         struct epoll_ctlr *ep;
231
232         /* Lockless peek, avoid locking for every close() */
233         if (TAILQ_EMPTY(&all_ctlrs))
234                 return;
235         uth_mutex_lock(ctlrs_mtx);
236         TAILQ_FOREACH(ep, &all_ctlrs, link)
237                 epoll_ctl(ep->ufd.fd, EPOLL_CTL_DEL, fd, 0);
238         uth_mutex_unlock(ctlrs_mtx);
239 }
240
241 static void epoll_init(void)
242 {
243         static struct close_cb epoll_close_cb = {.func = epoll_fd_closed};
244
245         register_close_cb(&epoll_close_cb);
246         ctlrs_mtx = uth_mutex_alloc();
247 }
248
249 int epoll_create(int size)
250 {
251         int fd;
252         struct epoll_ctlr *ep;
253
254         run_once(epoll_init());
255         /* good thing the arg is a signed int... */
256         if (size < 0) {
257                 errno = EINVAL;
258                 return -1;
259         }
260         ep = malloc(sizeof(struct epoll_ctlr));
261         memset(ep, 0, sizeof(struct epoll_ctlr));
262         if (init_ep_ctlr(ep, size)) {
263                 free(ep);
264                 return -1;
265         }
266         fd = ufd_get_fd(&ep->ufd);
267         if (fd < 0)
268                 free(ep);
269         uth_mutex_lock(ctlrs_mtx);
270         TAILQ_INSERT_TAIL(&all_ctlrs, ep, link);
271         uth_mutex_unlock(ctlrs_mtx);
272         return fd;
273 }
274
275 int epoll_create1(int flags)
276 {
277         /* TODO: we're supposed to support CLOEXEC.  Our FD is a user_fd, so that'd
278          * require some support in glibc's exec to close our epoll ctlr. */
279         return epoll_create(1);
280 }
281
282 static int __epoll_ctl_add(struct epoll_ctlr *ep, int fd,
283                            struct epoll_event *event)
284 {
285         struct ceq_event *ceq_ev;
286         struct ep_fd_data *ep_fd;
287         struct fd_tap_req tap_req = {0};
288         int ret, filter, sock_listen_fd;
289         struct epoll_event listen_event;
290
291         /* Only support ET.  Also, we just ignore EPOLLONESHOT.  That might work,
292          * logically, just with spurious events firing. */
293         if (!(event->events & EPOLLET)) {
294                 errno = EPERM;
295                 werrstr("Epoll level-triggered not supported");
296                 return -1;
297         }
298         /* The sockets-to-plan9 networking shims are a bit inconvenient.  The user
299          * asked us to epoll on an FD, but that FD is actually a Qdata FD.  We might
300          * need to actually epoll on the listen_fd.  Further, we don't know yet
301          * whether or not they want the listen FD.  They could epoll on the socket,
302          * then listen later and want to wake up on the listen.
303          *
304          * So in the case we have a socket FD, we'll actually open the listen FD
305          * regardless (glibc handles this), and we'll epoll on both FDs.
306          * Technically, either FD could fire and they'd get an epoll event for it,
307          * but I think socket users will use only listen or data.
308          *
309          * As far as tracking the FD goes for epoll_wait() reporting, if the app
310          * wants to track the FD they think we are using, then they already passed
311          * that in event->data. */
312         sock_listen_fd = _sock_lookup_listen_fd(fd);
313         if (sock_listen_fd >= 0) {
314                 listen_event.events = EPOLLET | EPOLLIN | EPOLLHUP;
315                 listen_event.data = event->data;
316                 ret = __epoll_ctl_add(ep, sock_listen_fd, &listen_event);
317                 if (ret < 0)
318                         return ret;
319         }
320         ceq_ev = ep_get_ceq_ev(ep, fd);
321         if (!ceq_ev) {
322                 errno = ENOMEM;
323                 werrstr("Epoll set cannot grow yet!");
324                 return -1;
325         }
326         ep_fd = (struct ep_fd_data*)ceq_ev->user_data;
327         if (ep_fd) {
328                 errno = EEXIST;
329                 return -1;
330         }
331         tap_req.fd = fd;
332         tap_req.cmd = FDTAP_CMD_ADD;
333         /* EPOLLHUP is implicitly set for all epolls. */
334         filter = ep_events_to_taps(event->events | EPOLLHUP);
335         tap_req.filter = filter;
336         tap_req.ev_q = ep->ceq_evq;
337         tap_req.ev_id = fd;     /* using FD as the CEQ ID */
338         ret = sys_tap_fds(&tap_req, 1);
339         if (ret != 1)
340                 return -1;
341         ep_fd = malloc(sizeof(struct ep_fd_data));
342         ep_fd->fd = fd;
343         ep_fd->filter = filter;
344         ep_fd->ep_event = *event;
345         ep_fd->ep_event.events |= EPOLLHUP;
346         ceq_ev->user_data = (uint64_t)ep_fd;
347         return 0;
348 }
349
350 static int __epoll_ctl_del(struct epoll_ctlr *ep, int fd,
351                            struct epoll_event *event)
352 {
353         struct ceq_event *ceq_ev;
354         struct ep_fd_data *ep_fd;
355         struct fd_tap_req tap_req = {0};
356         int ret, sock_listen_fd;
357
358         /* If we were dealing with a socket shim FD, we tapped both the listen and
359          * the data file and need to untap both of them. */
360         sock_listen_fd = _sock_lookup_listen_fd(fd);
361         if (sock_listen_fd >= 0) {
362                 /* It's possible to fail here.  Even though we tapped it already, if the
363                  * deletion was triggered from close callbacks, it's possible for the
364                  * sock_listen_fd to be closed first, which would have triggered an
365                  * epoll_ctl_del.  When we get around to closing the Rock FD, the listen
366                  * FD was already closed. */
367                 __epoll_ctl_del(ep, sock_listen_fd, event);
368         }
369         ceq_ev = ep_get_ceq_ev(ep, fd);
370         if (!ceq_ev) {
371                 errno = ENOENT;
372                 return -1;
373         }
374         ep_fd = (struct ep_fd_data*)ceq_ev->user_data;
375         if (!ep_fd) {
376                 errno = ENOENT;
377                 return -1;
378         }
379         assert(ep_fd->fd == fd);
380         tap_req.fd = fd;
381         tap_req.cmd = FDTAP_CMD_REM;
382         /* ignoring the return value; we could have failed to remove it if the FD
383          * has already closed and the kernel removed the tap. */
384         sys_tap_fds(&tap_req, 1);
385         ceq_ev->user_data = 0;
386         free(ep_fd);
387         return 0;
388 }
389
390 int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event)
391 {
392         int ret;
393         struct epoll_ctlr *ep = fd_to_cltr(epfd);
394         if (!ep) {
395                 errno = EBADF;/* or EINVAL */
396                 return -1;
397         }
398         if (fd >= USER_FD_BASE) {
399                 errno = EINVAL;
400                 werrstr("Epoll can't track User FDs");
401                 return -1;
402         }
403         uth_mutex_lock(ep->mtx);
404         switch (op) {
405                 case (EPOLL_CTL_MOD):
406                         /* In lieu of a proper MOD, just remove and readd.  The errors might
407                          * not work out well, and there could be a missed event in the
408                          * middle.  Not sure what the guarantees are, but we can fake a
409                          * poke. (TODO). */
410                         ret = __epoll_ctl_del(ep, fd, 0);
411                         if (ret)
412                                 break;
413                         ret = __epoll_ctl_add(ep, fd, event);
414                         break;
415                 case (EPOLL_CTL_ADD):
416                         ret = __epoll_ctl_add(ep, fd, event);
417                         break;
418                 case (EPOLL_CTL_DEL):
419                         ret = __epoll_ctl_del(ep, fd, event);
420                         break;
421                 default:
422                         errno = EINVAL;
423                         ret = -1;
424         }
425         uth_mutex_unlock(ep->mtx);
426         return ret;
427 }
428
429 static bool get_ep_event_from_msg(struct epoll_ctlr *ep, struct event_msg *msg,
430                                   struct epoll_event *ep_ev)
431 {
432         struct ceq_event *ceq_ev;
433         struct ep_fd_data *ep_fd;
434
435         ceq_ev = ep_get_ceq_ev(ep, msg->ev_type);
436         /* should never get a tap FD > size of the epoll set */
437         assert(ceq_ev);
438         ep_fd = (struct ep_fd_data*)ceq_ev->user_data;
439         if (!ep_fd) {
440                 /* it's possible the FD was unregistered and this was an old
441                  * event sent to this epoll set. */
442                 return FALSE;
443         }
444         ep_ev->data = ep_fd->ep_event.data;
445         /* The events field was initialized to 0 in epoll_wait() */
446         ep_ev->events |= taps_to_ep_events(msg->ev_arg2);
447         return TRUE;
448 }
449
450 /* Helper: extracts as many epoll_events as possible from the ep. */
451 static int __epoll_wait_poll(struct epoll_ctlr *ep, struct epoll_event *events,
452                              int maxevents)
453 {
454         struct event_msg msg = {0};
455         int nr_ret = 0;
456
457         if (maxevents <= 0)
458                 return 0;
459         /* Locking to protect get_ep_event_from_msg, specifically that the ep_fd
460          * stored at ceq_ev->user_data does not get concurrently removed and
461          * freed. */
462         uth_mutex_lock(ep->mtx);
463         for (int i = 0; i < maxevents; i++) {
464 retry:
465                 if (!uth_check_evqs(&msg, NULL, 1, ep->ceq_evq))
466                         break;
467                 if (!get_ep_event_from_msg(ep, &msg, &events[i]))
468                         goto retry;
469                 nr_ret++;
470         }
471         uth_mutex_unlock(ep->mtx);
472         return nr_ret;
473 }
474
475 /* We should be able to have multiple waiters.  ep shouldn't be closed or
476  * anything, since we have the FD (that'd be bad programming on the user's
477  * behalf).  We could have concurrent ADD/MOD/DEL operations (which lock). */
478 static int __epoll_wait(struct epoll_ctlr *ep, struct epoll_event *events,
479                         int maxevents, int timeout)
480 {
481         struct event_msg msg = {0};
482         struct event_msg dummy_msg;
483         struct event_queue *which_evq;
484         struct event_queue *alarm_evq;
485         int nr_ret;
486         struct syscall sysc;
487
488         nr_ret = __epoll_wait_poll(ep, events, maxevents);
489         if (nr_ret)
490                 return nr_ret;
491         if (timeout == 0)
492                 return 0;
493         /* From here on down, we're going to block until there is some activity */
494         if (timeout != -1) {
495                 alarm_evq = ep_get_alarm_evq();
496                 syscall_async(&sysc, SYS_block, timeout * 1000);
497                 if (!register_evq(&sysc, alarm_evq)) {
498                         /* timeout occurred before we could even block! */
499                         ep_put_alarm_evq(alarm_evq);
500                         return 0;
501                 }
502                 uth_blockon_evqs(&msg, &which_evq, 2, ep->ceq_evq, alarm_evq);
503                 if (which_evq != alarm_evq) {
504                         /* sysc may or may not have finished yet.  this will force it to
505                          * *start* to finish iff it is still a submitted syscall. */
506                         sys_abort_sysc(&sysc);
507                         /* But we still need to wait until the syscall completed.  Need a
508                          * dummy msg, since we don't want to clobber the real msg. */
509                         uth_blockon_evqs(&dummy_msg, 0, 1, alarm_evq);
510                 }
511                 /* TODO: Slightly dangerous, due to spammed INDIRs */
512                 ep_put_alarm_evq(alarm_evq);
513                 if (which_evq == alarm_evq)
514                         return 0;
515         } else {
516                 uth_blockon_evqs(&msg, &which_evq, 1, ep->ceq_evq);
517         }
518         uth_mutex_lock(ep->mtx);
519         if (get_ep_event_from_msg(ep, &msg, &events[0]))
520                 nr_ret = 1;
521         uth_mutex_unlock(ep->mtx);
522         /* We had to extract one message already as part of the blocking process.
523          * We might be able to get more. */
524         nr_ret += __epoll_wait_poll(ep, events + nr_ret, maxevents - nr_ret);
525         /* This is a little nasty and hopefully a rare race.  We still might not
526          * have a ret, but we expected to block until we had something.  We didn't
527          * time out yet, but we spuriously woke up.  We need to try again (ideally,
528          * we'd subtract the time left from the original timeout). */
529         if (!nr_ret)
530                 return __epoll_wait(ep, events, maxevents, timeout);
531         return nr_ret;
532 }
533
534 int epoll_wait(int epfd, struct epoll_event *events, int maxevents,
535                int timeout)
536 {
537         struct epoll_ctlr *ep = fd_to_cltr(epfd);
538
539         if (!ep) {
540                 errno = EBADF;/* or EINVAL */
541                 return -1;
542         }
543         if (maxevents <= 0) {
544                 errno = EINVAL;
545                 return -1;
546         }
547         for (int i = 0; i < maxevents; i++)
548                 events[i].events = 0;
549         return __epoll_wait(ep, events, maxevents, timeout);
550 }
551
552 int epoll_pwait(int epfd, struct epoll_event *events, int maxevents,
553                 int timeout, const sigset_t *sigmask)
554 {
555         int ready;
556         sigset_t origmask;
557         /* TODO: this is probably racy */
558         sigprocmask(SIG_SETMASK, sigmask, &origmask);
559         ready = epoll_wait(epfd, events, maxevents, timeout);
560         sigprocmask(SIG_SETMASK, &origmask, NULL);
561         return ready;
562 }