1 /*
2  * This is free and unencumbered software released into the public domain.
3  *
4  * Anyone is free to copy, modify, publish, use, compile, sell, or
5  * distribute this software, either in source code form or as a compiled
6  * binary, for any purpose, commercial or non-commercial, and by any
7  * means.
8  *
9  * In jurisdictions that recognize copyright laws, the author or authors
10  * of this software dedicate any and all copyright interest in the
11  * software to the public domain. We make this dedication for the benefit
12  * of the public at large and to the detriment of our heirs and
13  * successors. We intend this dedication to be an overt act of
14  * relinquishment in perpetuity of all present and future rights to this
15  * software under copyright law.
16  *
17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
20  * IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
21  * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
22  * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
23  * OTHER DEALINGS IN THE SOFTWARE.
24  */
25 
26 #include "compat.h"
27 
28 #include <sys/time.h>
29 
30 #include <errno.h>
31 #include <fcntl.h>
32 #include <limits.h>
33 #include <poll.h>
34 #include <signal.h>
35 #include <stdlib.h>
36 #include <string.h>
37 #include <time.h>
38 #include <unistd.h>
39 
40 #include "ev.h"
41 
42 struct evcb {
43 	void		(*cb)(int, int, void *);
44 	void		*udata;
45 };
46 
47 struct evtimer {
48 	unsigned int	 id;
49 	struct timeval	 tv;
50 	struct evcb	 cb;
51 };
52 
53 struct evbase {
54 	size_t		 len;
55 
56 	struct pollfd	*pfds;
57 	size_t		 pfdlen;
58 
59 	struct evcb	*cbs;
60 	size_t		 cblen;
61 
62 	int		 sigpipe[2];
63 	struct evcb	 sigcb;
64 
65 	unsigned int	 tid;
66 
67 	/*
68 	 * Binary heap of timers.  At runtime, new timers are added in
69 	 * the ``reserve'', a space after the caninocal end of the
70 	 * array, and at the end of every tick they're added to the
71 	 * heap.
72 	 */
73 	struct evtimer	*timers;
74 	size_t		 ntimers;
75 	size_t		 reserve_from;
76 	size_t		 reserve_till;
77 	size_t		 timerscap;
78 };
79 
80 static struct evbase	*base;
81 static int		 ev_stop;
82 
83 static int
84 ev_resize(size_t len)
85 {
86 	void	*t;
87 	size_t	 i;
88 
89 	t = recallocarray(base->pfds, base->pfdlen, len, sizeof(*base->pfds));
90 	if (t == NULL)
91 		return -1;
92 	base->pfds = t;
93 	base->pfdlen = len;
94 
95 	for (i = base->len; i < len; ++i)
96 		base->pfds[i].fd = -1;
97 
98 	t = recallocarray(base->cbs, base->cblen, len, sizeof(*base->cbs));
99 	if (t == NULL)
100 		return -1;
101 	base->cbs = t;
102 	base->cblen = len;
103 
104 	base->len = len;
105 	return 0;
106 }
107 
108 int
109 ev_init(void)
110 {
111 	if (base != NULL) {
112 		errno = EINVAL;
113 		return -1;
114 	}
115 
116 	if ((base = calloc(1, sizeof(*base))) == NULL)
117 		return -1;
118 
119 	base->sigpipe[0] = -1;
120 	base->sigpipe[1] = -1;
121 
122 	if (ev_resize(16) == -1) {
123 		free(base->pfds);
124 		free(base->cbs);
125 		free(base);
126 		base = NULL;
127 		return -1;
128 	}
129 
130 	return 0;
131 }
132 
133 static inline int
134 ev2poll(int ev)
135 {
136 	int	 ret = 0;
137 
138 	if (ev & EV_READ)
139 		ret |= POLLIN;
140 	if (ev & EV_WRITE)
141 		ret |= POLLOUT;
142 
143 	return (ret);
144 }
145 
146 int
147 ev_add(int fd, int ev, void (*cb)(int, int, void *), void *udata)
148 {
149 	if (fd < 0) {
150 		errno = EBADF;
151 		return -1;
152 	}
153 
154 	if ((size_t)fd >= base->len) {
155 		if (ev_resize(fd + 1) == -1)
156 			return -1;
157 	}
158 
159 	base->pfds[fd].fd = fd;
160 	base->pfds[fd].events = ev2poll(ev);
161 	base->pfds[fd].revents = 0;
162 
163 	base->cbs[fd].cb = cb;
164 	base->cbs[fd].udata = udata;
165 
166 	return 0;
167 }
168 
169 static void
170 ev_sigcatch(int signo)
171 {
172 	unsigned char	 s;
173 	int		 err;
174 
175 	err = errno;
176 
177 	/*
178 	 * We should be able to write up to PIPE_BUF bytes without
179 	 * blocking.
180 	 */
181 	s = signo;
182 	(void) write(base->sigpipe[1], &s, sizeof(s));
183 
184 	errno = err;
185 }
186 
187 static void
188 ev_sigdispatch(int fd, int ev, void *data)
189 {
190 	unsigned char	 signo;
191 
192 	if (read(fd, &signo, sizeof(signo)) != sizeof(signo))
193 		return;
194 
195 	base->sigcb.cb(signo, EV_SIGNAL, base->sigcb.udata);
196 }
197 
198 int
199 ev_signal(int sig, void (*cb)(int, int, void *), void *udata)
200 {
201 	int		 flags;
202 
203 	if (base->sigpipe[0] == -1) {
204 		/* pipe2(2) is not available everywhere... sigh */
205 		if (pipe(base->sigpipe) == -1)
206 			return -1;
207 
208 		if ((flags = fcntl(base->sigpipe[1], F_GETFL)) == -1 ||
209 		    fcntl(base->sigpipe[1], F_SETFL, flags | O_NONBLOCK) == -1)
210 			return -1;
211 
212 		if (ev_add(base->sigpipe[0], EV_READ, ev_sigdispatch, NULL)
213 		    == -1)
214 			return -1;
215 	}
216 
217 	base->sigcb.cb = cb;
218 	base->sigcb.udata = udata;
219 
220 	signal(sig, ev_sigcatch);
221 	return 0;
222 }
223 
224 unsigned int
225 ev_timer(const struct timeval *tv, void (*cb)(int, int, void*), void *udata)
226 {
227 	struct evtimer	*evt;
228 	void		*t;
229 	size_t		 newcap;
230 	unsigned int	 nextid;
231 
232 	if (tv == NULL) {
233 		errno = EINVAL;
234 		return 0;
235 	}
236 
237 	if (base->reserve_till == base->timerscap) {
238 		newcap = base->timerscap + 8;
239 		t = recallocarray(base->timers, base->timerscap, newcap,
240 		    sizeof(*base->timers));
241 		if (t == NULL)
242 			return 0;
243 		base->timers = t;
244 		base->timerscap = newcap;
245 	}
246 
247 	if ((nextid = ++base->tid) == 0)
248 		nextid = ++base->tid;
249 
250 	evt = &base->timers[base->reserve_till];
251 	evt->id = nextid;
252 	memcpy(&evt->tv, tv, sizeof(*tv));
253 	evt->cb.cb = cb;
254 	evt->cb.udata = udata;
255 
256 	base->reserve_till++;
257 	return (nextid);
258 }
259 
260 static int
261 find_timer(unsigned int id, size_t *pos)
262 {
263 	size_t		 i;
264 
265 	if (id == 0)
266 		return (0);
267 
268 	for (i = 0; i < base->ntimers; ++i) {
269 		if (base->timers[i].id == id) {
270 			*pos = i;
271 			return (1);
272 		}
273 	}
274 
275 	for (i = base->reserve_from; i < base->reserve_till; ++i) {
276 		if (base->timers[i].id == id) {
277 			*pos = i;
278 			return (1);
279 		}
280 	}
281 
282 	return (0);
283 }
284 
285 int
286 ev_timer_pending(unsigned int id)
287 {
288 	size_t		 i;
289 
290 	return (find_timer(id, &i));
291 }
292 
293 static void
294 bubbledown(size_t i)
295 {
296 	struct evtimer	 tmp;
297 	size_t		 l, r, s;
298 
299 	for (;;) {
300 		l = 2 * i + 1;
301 		r = 2 * i + 2;
302 
303 		/* base case: there are no children */
304 		if (l >= base->ntimers)
305 			return;
306 
307 		/* find the smaller child */
308 		s = r;
309 		if (r >= base->ntimers ||
310 		    timercmp(&base->timers[l].tv, &base->timers[r].tv, <))
311 			s = l;
312 
313 		/* other base case: it's at the right place */
314 		if (timercmp(&base->timers[i].tv, &base->timers[s].tv, <))
315 			return;
316 
317 		/* swap */
318 		memcpy(&tmp, &base->timers[s], sizeof(tmp));
319 		memcpy(&base->timers[s], &base->timers[i], sizeof(tmp));
320 		memcpy(&base->timers[i], &tmp, sizeof(tmp));
321 
322 		i = s;
323 	}
324 }
325 
326 static inline void
327 cancel_timer(size_t i)
328 {
329 	base->ntimers--;
330 	if (i != base->ntimers) {
331 		memcpy(&base->timers[i], &base->timers[base->ntimers],
332 		    sizeof(*base->timers));
333 		bubbledown(i);
334 	}
335 }
336 
337 int
338 ev_timer_cancel(unsigned int id)
339 {
340 	size_t		 i;
341 
342 	if (!find_timer(id, &i))
343 		return (-1);
344 
345 	if (i < base->ntimers) {
346 		cancel_timer(i);
347 		return (0);
348 	}
349 
350 	base->reserve_till--;
351 	if (i != base->reserve_till)
352 		memcpy(&base->timers[i], &base->timers[base->reserve_till],
353 		    sizeof(*base->timers));
354 	return (0);
355 }
356 
357 int
358 ev_del(int fd)
359 {
360 	if (fd < 0) {
361 		errno = EBADF;
362 		return -1;
363 	}
364 
365 	if ((size_t)fd >= base->len) {
366 		errno = ERANGE;
367 		return -1;
368 	}
369 
370 	base->pfds[fd].fd = -1;
371 	base->pfds[fd].events = 0;
372 
373 	base->cbs[fd].cb = NULL;
374 	base->cbs[fd].udata = NULL;
375 
376 	return 0;
377 }
378 
379 static void
380 timerheapify(void)
381 {
382 	size_t		 i, reserve, gap;
383 
384 	reserve = base->reserve_till - base->reserve_from;
385 	if (reserve == 0)
386 		return;
387 
388 	gap = base->reserve_from - base->ntimers;
389 	if (gap != 0) {
390 		memmove(&base->timers[base->ntimers],
391 		    &base->timers[base->reserve_from],
392 		    reserve * sizeof(*base->timers));
393 		base->reserve_from -= gap;
394 		base->reserve_till -= gap;
395 	}
396 
397 	base->ntimers = base->reserve_till;
398 
399 	if (base->ntimers < 2)
400 		return;
401 
402 	i = base->ntimers / 2 - 1;
403 	for (;;) {
404 		bubbledown(i);
405 		if (i == 0)
406 			break;
407 		i--;
408 	}
409 }
410 
411 static inline int
412 poll2ev(int ev)
413 {
414 	int r = 0;
415 
416 	if (ev & (POLLIN|POLLHUP))
417 		r |= EV_READ;
418 	if (ev & (POLLOUT|POLLWRNORM|POLLWRBAND))
419 		r |= EV_WRITE;
420 
421 	return (r);
422 }
423 
424 int
425 ev_loop(void)
426 {
427 	struct timespec	 elapsed, beg, end;
428 	struct timeval	 tv, sub, *min;
429 	struct evcb	 cb;
430 	int		 n, msec;
431 	size_t		 i;
432 
433 	while (!ev_stop) {
434 		timerheapify();
435 		base->reserve_from = base->ntimers;
436 		base->reserve_till = base->ntimers;
437 
438 		min = NULL;
439 		msec = -1;
440 		if (base->ntimers) {
441 			min = &base->timers[0].tv;
442 			msec = min->tv_sec * 1000 + (min->tv_usec + 999) / 1000;
443 		}
444 
445 		clock_gettime(CLOCK_MONOTONIC, &beg);
446 		if ((n = poll(base->pfds, base->len, msec)) == -1) {
447 			if (errno != EINTR)
448 				return -1;
449 		}
450 
451 		if (n == 0 && min)
452 			memcpy(&tv, min, sizeof(tv));
453 		else {
454 			clock_gettime(CLOCK_MONOTONIC, &end);
455 			timespecsub(&end, &beg, &elapsed);
456 			TIMESPEC_TO_TIMEVAL(&tv, &elapsed);
457 		}
458 
459 		for (i = 0; i < base->ntimers && !ev_stop; /* nop */) {
460 			timersub(&base->timers[i].tv, &tv, &sub);
461 			if (sub.tv_sec <= 0) {
462 				/*
463 				 * delete the timer before calling its
464 				 * callback; protects from timer that
465 				 * attempt to delete themselves.
466 				 */
467 				memcpy(&cb, &base->timers[i].cb, sizeof(cb));
468 				cancel_timer(i);
469 				cb.cb(-1, EV_TIMEOUT, cb.udata);
470 				continue;
471 			}
472 
473 			memcpy(&base->timers[i].tv, &sub, sizeof(sub));
474 			i++;
475 		}
476 
477 		for (i = 0; i < base->len && n > 0 && !ev_stop; ++i) {
478 			if (base->pfds[i].fd == -1)
479 				continue;
480 			if (base->pfds[i].revents & (POLLIN|POLLOUT|POLLHUP)) {
481 				n--;
482 				base->cbs[i].cb(base->pfds[i].fd,
483 				    poll2ev(base->pfds[i].revents),
484 				    base->cbs[i].udata);
485 			}
486 		}
487 	}
488 
489 	return 0;
490 }
491 
492 void
493 ev_break(void)
494 {
495 	ev_stop = 1;
496 }