1/*
2 * Copyright 2015, Hamish Morrison, hamishm53@gmail.com.
3 * Copyright 2023, Haiku, Inc. All rights reserved.
4 * Distributed under the terms of the MIT License.
5 */
6
7#include <event_queue.h>
8
9#include <OS.h>
10
11#include <AutoDeleter.h>
12
13#include <fs/fd.h>
14#include <port.h>
15#include <sem.h>
16#include <syscalls.h>
17#include <syscall_restart.h>
18#include <thread.h>
19#include <util/AutoLock.h>
20#include <util/AVLTree.h>
21#include <util/DoublyLinkedList.h>
22#include <AutoDeleterDrivers.h>
23#include <StackOrHeapArray.h>
24#include <wait_for_objects.h>
25
26#include "select_ops.h"
27#include "select_sync.h"
28
29
30enum {
31	B_EVENT_QUEUED			= (1 << 28),
32	B_EVENT_SELECTING		= (1 << 29),
33	B_EVENT_DELETING		= (1 << 30),
34	/* (signed) */
35	B_EVENT_PRIVATE_MASK	= (0xf0000000)
36};
37
38
39#define EVENT_BEHAVIOR(events) ((events) & (B_EVENT_LEVEL_TRIGGERED | B_EVENT_ONE_SHOT))
40#define USER_EVENTS(events) ((events) & ~B_EVENT_PRIVATE_MASK)
41
42#define B_EVENT_NON_MASKABLE (B_EVENT_INVALID | B_EVENT_ERROR | B_EVENT_DISCONNECTED)
43
44
45
46struct select_event : select_info, AVLTreeNode,
47		DoublyLinkedListLinkImpl<select_event> {
48	int32				object;
49	uint16				type;
50	uint32				behavior;
51	void*				user_data;
52};
53
54
55struct EventQueueTreeDefinition {
56	typedef struct {
57		int32 object;
58		uint16 type;
59	} 						Key;
60	typedef select_event	Value;
61
62	AVLTreeNode* GetAVLTreeNode(Value* value) const
63	{
64		return value;
65	}
66
67	Value* GetValue(AVLTreeNode* node) const
68	{
69		return static_cast<Value*>(node);
70	}
71
72	int Compare(Key a, const Value* b) const
73	{
74		if (a.object != b->object)
75			return a.object - b->object;
76		else
77			return a.type - b->type;
78	}
79
80	int Compare(const Value* a, const Value* b) const
81	{
82		if (a->object != b->object)
83			return a->object - b->object;
84		else
85			return a->type - b->type;
86	}
87};
88
89
90//	#pragma mark -- EventQueue implementation
91
92
93class EventQueue : public select_sync {
94public:
95						EventQueue(bool kernel);
96						~EventQueue();
97
98	void				Closed();
99
100	status_t			Select(int32 object, uint16 type, uint32 events, void* userData);
101	status_t			Query(int32 object, uint16 type, uint32* selectedEvents, void** userData);
102	status_t			Deselect(int32 object, uint16 type);
103
104	status_t			Notify(select_info* info, uint16 events);
105
106	ssize_t				Wait(event_wait_info* infos, int numInfos,
107							int32 flags, bigtime_t timeout);
108
109private:
110	void				_Notify(select_event* event, uint16 events);
111	status_t			_DeselectEvent(select_event* event);
112
113	ssize_t				_DequeueEvents(event_wait_info* infos, int numInfos);
114
115	select_event*		_GetEvent(int32 object, uint16 type);
116
117private:
118	typedef AVLTree<EventQueueTreeDefinition> EventTree;
119	typedef DoublyLinkedList<select_event> EventList;
120
121	bool				fKernel;
122	bool				fClosing;
123
124	/*
125	 * This flag is set in _DequeueEvents when we have to drop the lock to
126	 * deselect an object to prevent another _DequeueEvents call concurrently
127	 * modifying the list.
128	 */
129	bool				fDequeueing;
130
131	EventList			fEventList;
132	EventTree			fEventTree;
133
134	/*
135	 * Protects the queue. We cannot call select or deselect while holding
136	 * this, because it will invert the locking order with EventQueue::Notify.
137	 */
138	mutex				fQueueLock;
139
140	/*
141	 * Notified when events are available on the queue.
142	 */
143	ConditionVariable	fQueueCondition;
144
145	/*
146	 * Used to wait on a changing select_event while the queue lock is dropped
147	 * during a call to select/deselect.
148	 */
149	ConditionVariable	fEventCondition;
150};
151
152
153EventQueue::EventQueue(bool kernel)
154	:
155	fKernel(kernel),
156	fClosing(false),
157	fDequeueing(false)
158{
159	mutex_init(&fQueueLock, "event_queue lock");
160	fQueueCondition.Init(this, "evtq wait");
161	fEventCondition.Init(this, "event_queue event change wait");
162}
163
164
165EventQueue::~EventQueue()
166{
167	mutex_lock(&fQueueLock);
168	ASSERT(fClosing && !fDequeueing);
169
170	EventTree::Iterator iter = fEventTree.GetIterator();
171	while (iter.HasNext()) {
172		select_event* event = iter.Next();
173		event->events |= B_EVENT_DELETING;
174
175		mutex_unlock(&fQueueLock);
176		_DeselectEvent(event);
177		mutex_lock(&fQueueLock);
178
179		iter.Remove();
180		if ((event->events & B_EVENT_QUEUED) != 0)
181			fEventList.Remove(event);
182		delete event;
183	}
184
185	EventList::Iterator listIter = fEventList.GetIterator();
186	while (listIter.HasNext()) {
187		select_event* event = listIter.Next();
188
189		// We already removed all events in the tree from this list.
190		// The only remaining events will be INVALID ones already deselected.
191		delete event;
192	}
193
194	mutex_destroy(&fQueueLock);
195}
196
197
198void
199EventQueue::Closed()
200{
201	MutexLocker locker(&fQueueLock);
202
203	fClosing = true;
204	locker.Unlock();
205
206	// Wake up all waiters
207	fQueueCondition.NotifyAll(B_FILE_ERROR);
208}
209
210
211status_t
212EventQueue::Select(int32 object, uint16 type, uint32 events, void* userData)
213{
214	MutexLocker locker(&fQueueLock);
215
216	select_event* event = _GetEvent(object, type);
217	if (event != NULL) {
218		if ((event->selected_events | event->behavior)
219				== (USER_EVENTS(events) | B_EVENT_NON_MASKABLE))
220			return B_OK;
221
222		// Rather than try to reuse the event object, which would be complicated
223		// and error-prone, perform a full de-selection and then re-selection.
224		locker.Unlock();
225		status_t status = Deselect(object, type);
226		if (status != B_OK)
227			return status;
228		locker.Lock();
229
230		// Make sure nothing else re-selected before we reacquired the lock.
231		event = _GetEvent(object, type);
232		if (event != NULL)
233			return EEXIST;
234	}
235
236	event = new(std::nothrow) select_event;
237	if (event == NULL)
238		return B_NO_MEMORY;
239	ObjectDeleter<select_event> eventDeleter(event);
240
241	event->sync = this;
242	event->object = object;
243	event->type = type;
244	event->behavior = EVENT_BEHAVIOR(events);
245	event->user_data = userData;
246	event->events = 0;
247
248	status_t result = fEventTree.Insert(event);
249	if (result != B_OK)
250		return result;
251
252	// We drop the lock before calling select() to avoid inverting the
253	// locking order with Notify(). Setting the B_EVENT_SELECTING flag prevents
254	// the event from being used or even deleted before it is ready.
255	event->events |= B_EVENT_SELECTING;
256	event->selected_events = USER_EVENTS(events) | B_EVENT_NON_MASKABLE;
257
258	locker.Unlock();
259
260	status_t status = select_object(event->type, event->object, event, fKernel);
261	if (status < 0) {
262		locker.Lock();
263		fEventTree.Remove(event);
264		fEventCondition.NotifyAll();
265		return status;
266	}
267
268	eventDeleter.Detach();
269
270	atomic_and(&event->events, ~B_EVENT_SELECTING);
271	fEventCondition.NotifyAll();
272
273	return B_OK;
274}
275
276
277status_t
278EventQueue::Query(int32 object, uint16 type, uint32* selectedEvents, void** userData)
279{
280	MutexLocker locker(&fQueueLock);
281
282	select_event* event = _GetEvent(object, type);
283	if (event == NULL)
284		return B_ENTRY_NOT_FOUND;
285
286	*selectedEvents = event->selected_events | event->behavior;
287	*userData = event->user_data;
288
289	return B_OK;
290}
291
292
293status_t
294EventQueue::Deselect(int32 object, uint16 type)
295{
296	MutexLocker locker(&fQueueLock);
297
298	select_event* event = _GetEvent(object, type);
299	if (event == NULL)
300		return B_ENTRY_NOT_FOUND;
301
302	if ((atomic_or(&event->events, B_EVENT_DELETING) & B_EVENT_DELETING) != 0)
303		return B_OK;
304
305	locker.Unlock();
306	_DeselectEvent(event);
307	locker.Lock();
308
309	if ((event->events & B_EVENT_INVALID) == 0)
310		fEventTree.Remove(event);
311	if ((event->events & B_EVENT_QUEUED) != 0)
312		fEventList.Remove(event);
313
314	delete event;
315
316	locker.Unlock();
317	fEventCondition.NotifyAll();
318	return B_OK;
319}
320
321
322status_t
323EventQueue::_DeselectEvent(select_event* event)
324{
325	return deselect_object(event->type, event->object, event, fKernel);
326}
327
328
329status_t
330EventQueue::Notify(select_info* info, uint16 events)
331{
332	select_event* event = static_cast<select_event*>(info);
333	_Notify(event, events);
334	return B_OK;
335}
336
337
338void
339EventQueue::_Notify(select_event* event, uint16 events)
340{
341	if ((events & event->selected_events) == 0)
342		return;
343
344	const int32 previousEvents = atomic_or(&event->events, (events & ~B_EVENT_INVALID));
345
346	// If the event is already being deleted, we should ignore this notification.
347	if ((previousEvents & B_EVENT_DELETING) != 0)
348		return;
349
350	// If the event is already queued, and it is not becoming invalid,
351	// we don't need to do anything more.
352	if ((previousEvents & B_EVENT_QUEUED) != 0 && (events & B_EVENT_INVALID) == 0)
353		return;
354
355	{
356		MutexLocker _(&fQueueLock);
357
358		// We need to recheck B_EVENT_DELETING now we have the lock.
359		if ((event->events & B_EVENT_DELETING) != 0)
360			return;
361
362		// If we get B_EVENT_INVALID it means the object we were monitoring was
363		// deleted. The object's ID may now be reused, so we must remove it
364		// from the event tree.
365		if ((events & B_EVENT_INVALID) != 0) {
366			atomic_or(&event->events, B_EVENT_INVALID);
367			fEventTree.Remove(event);
368		}
369
370		// If it's not already queued, it's our responsibility to queue it.
371		if ((atomic_or(&event->events, B_EVENT_QUEUED) & B_EVENT_QUEUED) == 0) {
372			fEventList.Add(event);
373			fQueueCondition.NotifyAll();
374		}
375	}
376}
377
378
379ssize_t
380EventQueue::Wait(event_wait_info* infos, int numInfos,
381	int32 flags, bigtime_t timeout)
382{
383	ASSERT((flags & B_ABSOLUTE_TIMEOUT) != 0
384		|| (timeout == B_INFINITE_TIMEOUT || timeout == 0));
385
386	MutexLocker queueLocker(&fQueueLock);
387
388	ssize_t count = 0;
389	while (timeout == 0 || (system_time() < timeout)) {
390		while ((fDequeueing || fEventList.IsEmpty()) && !fClosing) {
391			status_t status = fQueueCondition.Wait(queueLocker.Get(),
392				flags | B_CAN_INTERRUPT, timeout);
393			if (status != B_OK)
394				return status;
395		}
396
397		if (fClosing)
398			return B_FILE_ERROR;
399
400		if (numInfos == 0)
401			return B_OK;
402
403		fDequeueing = true;
404		count = _DequeueEvents(infos, numInfos);
405		fDequeueing = false;
406
407		if (count != 0)
408			break;
409
410		// Due to level-triggered events, it is possible for the event list to have
411		// been not empty and _DequeueEvents() still returns nothing. Hence, we loop.
412	}
413
414	return count;
415}
416
417
418ssize_t
419EventQueue::_DequeueEvents(event_wait_info* infos, int numInfos)
420{
421	ssize_t count = 0;
422
423	const int32 kMaxToDeselect = 8;
424	select_event* deselect[kMaxToDeselect];
425	int32 deselectCount = 0;
426
427	// Add a marker element, so we don't loop forever after unlocking the list.
428	// (There is only one invocation of _DequeueEvents() at a time.)
429	select_event marker = {};
430	fEventList.Add(&marker);
431
432	for (select_event* event = NULL; count < numInfos; ) {
433		if (fEventList.Head() == NULL || fEventList.Head() == &marker)
434			break;
435
436		event = fEventList.RemoveHead();
437		int32 events = atomic_and(&event->events,
438			~(event->selected_events | B_EVENT_QUEUED));
439
440		if ((events & B_EVENT_DELETING) != 0)
441			continue;
442
443		if ((events & B_EVENT_INVALID) == 0
444				&& (event->behavior & B_EVENT_LEVEL_TRIGGERED) != 0) {
445			// This event is level-triggered. We need to deselect and reselect it,
446			// as its state may have changed since we were notified.
447			const select_event tmp = *event;
448
449			mutex_unlock(&fQueueLock);
450			status_t status = Deselect(tmp.object, tmp.type);
451			if (status == B_OK) {
452				event = NULL;
453				status = Select(tmp.object, tmp.type,
454					tmp.selected_events | tmp.behavior, tmp.user_data);
455			}
456			mutex_lock(&fQueueLock);
457
458			if (status == B_OK) {
459				// Is the event still queued?
460				event = _GetEvent(tmp.object, tmp.type);
461				if (event == NULL)
462					continue;
463				events = atomic_get(&event->events);
464				if ((events & B_EVENT_QUEUED) == 0)
465					continue;
466			} else if (event == NULL) {
467				continue;
468			}
469		}
470
471		infos[count].object = event->object;
472		infos[count].type = event->type;
473		infos[count].user_data = event->user_data;
474		infos[count].events = USER_EVENTS(events);
475		count++;
476
477		// All logic past this point has to do with deleting events.
478		if ((events & B_EVENT_INVALID) == 0 && (event->behavior & B_EVENT_ONE_SHOT) == 0)
479			continue;
480
481		// Check if the event was requeued.
482		if ((atomic_and(&event->events, ~B_EVENT_QUEUED) & B_EVENT_QUEUED) != 0)
483			fEventList.Remove(event);
484
485		if ((events & B_EVENT_INVALID) != 0) {
486			// The event will already have been removed from the tree.
487			delete event;
488		} else if ((event->behavior & B_EVENT_ONE_SHOT) != 0) {
489			// We already checked B_EVENT_INVALID above, so we don't need to again.
490			fEventTree.Remove(event);
491			event->events = B_EVENT_DELETING;
492
493			deselect[deselectCount++] = event;
494			if (deselectCount == kMaxToDeselect)
495				break;
496		}
497	}
498
499	fEventList.Remove(&marker);
500
501	if (deselectCount != 0) {
502		mutex_unlock(&fQueueLock);
503		for (int32 i = 0; i < deselectCount; i++) {
504			select_event* event = deselect[i];
505
506			_DeselectEvent(event);
507			delete event;
508		}
509		mutex_lock(&fQueueLock);
510
511		// We don't need to notify waiters, as we removed the events
512		// from anywhere they could be found before dropping the lock.
513	}
514
515	return count;
516}
517
518
519/*
520 * Get the select_event for the given object and type. Must be called with the
521 * queue lock held. This method will sleep if the event is undergoing selection
522 * or deletion.
523 */
524select_event*
525EventQueue::_GetEvent(int32 object, uint16 type)
526{
527	EventQueueTreeDefinition::Key key = { object, type };
528
529	while (true) {
530		select_event* event = fEventTree.Find(key);
531		if (event == NULL)
532			return NULL;
533
534		if ((event->events & (B_EVENT_SELECTING | B_EVENT_DELETING)) == 0)
535			return event;
536
537		fEventCondition.Wait(&fQueueLock);
538
539		// At this point the select_event might have been deleted, so we
540		// need to refetch it.
541	}
542}
543
544
545//	#pragma mark -- File descriptor ops
546
547
548
549static status_t
550event_queue_close(file_descriptor* descriptor)
551{
552	EventQueue* queue = (EventQueue*)descriptor->u.queue;
553	queue->Closed();
554	return B_OK;
555}
556
557
558static void
559event_queue_free(file_descriptor* descriptor)
560{
561	EventQueue* queue = (EventQueue*)descriptor->u.queue;
562	put_select_sync(queue);
563}
564
565
566static status_t
567get_queue_descriptor(int fd, bool kernel, file_descriptor*& descriptor)
568{
569	if (fd < 0)
570		return B_FILE_ERROR;
571
572	descriptor = get_fd(get_current_io_context(kernel), fd);
573	if (descriptor == NULL)
574		return B_FILE_ERROR;
575
576	if (descriptor->type != FDTYPE_EVENT_QUEUE) {
577		put_fd(descriptor);
578		return B_BAD_VALUE;
579	}
580
581	return B_OK;
582}
583
584
585#define GET_QUEUE_FD_OR_RETURN(fd, kernel, descriptor)	\
586	do {												\
587		status_t getError = get_queue_descriptor(fd, kernel, descriptor); \
588		if (getError != B_OK)							\
589			return getError;							\
590	} while (false)
591
592
593static struct fd_ops sEventQueueFDOps = {
594	NULL,	// fd_read
595	NULL,	// fd_write
596	NULL,	// fd_seek
597	NULL,	// fd_ioctl
598	NULL,	// fd_set_flags
599	NULL,	// fd_select
600	NULL,	// fd_deselect
601	NULL,	// fd_read_dir
602	NULL,	// fd_rewind_dir
603	NULL,	// fd_read_stat
604	NULL,	// fd_write_stat
605	&event_queue_close,
606	&event_queue_free
607};
608
609
610//	#pragma mark - User syscalls
611
612
613int
614_user_event_queue_create(int openFlags)
615{
616	EventQueue* queue = new(std::nothrow) EventQueue(false);
617	if (queue == NULL)
618		return B_NO_MEMORY;
619
620	ObjectDeleter<EventQueue> deleter(queue);
621
622	file_descriptor* descriptor = alloc_fd();
623	if (descriptor == NULL)
624		return B_NO_MEMORY;
625
626	descriptor->type = FDTYPE_EVENT_QUEUE;
627	descriptor->ops = &sEventQueueFDOps;
628	descriptor->u.queue = (struct event_queue*)queue;
629	descriptor->open_mode = O_RDWR | openFlags;
630
631	io_context* context = get_current_io_context(false);
632	int fd = new_fd(context, descriptor);
633	if (fd < 0) {
634		free(descriptor);
635		return fd;
636	}
637
638	mutex_lock(&context->io_mutex);
639	fd_set_close_on_exec(context, fd, (openFlags & O_CLOEXEC) != 0);
640	mutex_unlock(&context->io_mutex);
641
642	deleter.Detach();
643	return fd;
644}
645
646
647status_t
648_user_event_queue_select(int queue, event_wait_info* userInfos, int numInfos)
649{
650	if (numInfos <= 0)
651		return B_BAD_VALUE;
652	if (userInfos == NULL || !IS_USER_ADDRESS(userInfos))
653		return B_BAD_ADDRESS;
654
655	BStackOrHeapArray<event_wait_info, 16> infos(numInfos);
656	if (!infos.IsValid())
657		return B_NO_MEMORY;
658
659	file_descriptor* descriptor;
660	GET_QUEUE_FD_OR_RETURN(queue, false, descriptor);
661	FileDescriptorPutter _(descriptor);
662
663	EventQueue* eventQueue = (EventQueue*)descriptor->u.queue;
664
665	if (user_memcpy(infos, userInfos, sizeof(event_wait_info) * numInfos) != B_OK)
666		return B_BAD_ADDRESS;
667
668	status_t result = B_OK;
669
670	for (int i = 0; i < numInfos; i++) {
671		status_t error;
672		if (infos[i].events > 0) {
673			error = eventQueue->Select(infos[i].object, infos[i].type,
674				infos[i].events, infos[i].user_data);
675		} else if (infos[i].events < 0) {
676			uint32 selectedEvents = 0;
677			error = eventQueue->Query(infos[i].object, infos[i].type,
678				&selectedEvents, &infos[i].user_data);
679			if (error == B_OK) {
680				infos[i].events = selectedEvents;
681				error = user_memcpy(&userInfos[i], &infos[i], sizeof(event_wait_info));
682			}
683		} else /* == 0 */ {
684			error = eventQueue->Deselect(infos[i].object, infos[i].type);
685		}
686
687		if (error != B_OK) {
688			user_memcpy(&userInfos[i].events, &error, sizeof(&userInfos[i].events));
689			result = B_ERROR;
690		}
691	}
692
693	return result;
694}
695
696
697ssize_t
698_user_event_queue_wait(int queue, event_wait_info* userInfos, int numInfos,
699	uint32 flags, bigtime_t timeout)
700{
701	syscall_restart_handle_timeout_pre(flags, timeout);
702
703	if (numInfos < 0)
704		return B_BAD_VALUE;
705	if (numInfos > 0 && (userInfos == NULL || !IS_USER_ADDRESS(userInfos)))
706		return B_BAD_ADDRESS;
707
708	BStackOrHeapArray<event_wait_info, 16> infos(numInfos);
709	if (!infos.IsValid())
710		return B_NO_MEMORY;
711
712	file_descriptor* descriptor;
713	GET_QUEUE_FD_OR_RETURN(queue, false, descriptor);
714	FileDescriptorPutter _(descriptor);
715
716	EventQueue* eventQueue = (EventQueue*)descriptor->u.queue;
717
718	ssize_t result = eventQueue->Wait(infos, numInfos, flags, timeout);
719	if (result < 0)
720		return syscall_restart_handle_timeout_post(result, timeout);
721
722	status_t status = B_OK;
723	if (numInfos != 0)
724		status = user_memcpy(userInfos, infos, sizeof(event_wait_info) * numInfos);
725
726	return status == B_OK ? result : status;
727}
728