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