1// SPDX-License-Identifier: GPL-2.0-or-later
2/*
3 * ALSA sequencer Priority Queue
4 * Copyright (c) 1998-1999 by Frank van de Pol <fvdpol@coil.demon.nl>
5 */
6
7#include <linux/time.h>
8#include <linux/slab.h>
9#include <sound/core.h>
10#include "seq_timer.h"
11#include "seq_prioq.h"
12
13
14/* Implementation is a simple linked list for now...
15
16 This priority queue orders the events on timestamp. For events with an
17 equeal timestamp the queue behaves as a FIFO.
18
19 *
20 * +-------+
21 * Head --> | first |
22 * +-------+
23 * |next
24 * +-----v-+
25 * | |
26 * +-------+
27 * |
28 * +-----v-+
29 * | |
30 * +-------+
31 * |
32 * +-----v-+
33 * Tail --> | last |
34 * +-------+
35 *
36
37 */
38
39
40
41/* create new prioq (constructor) */
42struct snd_seq_prioq *snd_seq_prioq_new(void)
43{
44 struct snd_seq_prioq *f;
45
46 f = kzalloc(sizeof(*f), GFP_KERNEL);
47 if (!f)
48 return NULL;
49
50 spin_lock_init(&f->lock);
51 f->head = NULL;
52 f->tail = NULL;
53 f->cells = 0;
54
55 return f;
56}
57
58/* delete prioq (destructor) */
59void snd_seq_prioq_delete(struct snd_seq_prioq **fifo)
60{
61 struct snd_seq_prioq *f = *fifo;
62 *fifo = NULL;
63
64 if (f == NULL) {
65 pr_debug("ALSA: seq: snd_seq_prioq_delete() called with NULL prioq\n");
66 return;
67 }
68
69 /* release resources...*/
70 /*....................*/
71
72 if (f->cells > 0) {
73 /* drain prioQ */
74 while (f->cells > 0)
75 snd_seq_cell_free(cell: snd_seq_prioq_cell_out(f, NULL));
76 }
77
78 kfree(objp: f);
79}
80
81
82
83
84/* compare timestamp between events */
85/* return 1 if a >= b; 0 */
86static inline int compare_timestamp(struct snd_seq_event *a,
87 struct snd_seq_event *b)
88{
89 if ((a->flags & SNDRV_SEQ_TIME_STAMP_MASK) == SNDRV_SEQ_TIME_STAMP_TICK) {
90 /* compare ticks */
91 return (snd_seq_compare_tick_time(a: &a->time.tick, b: &b->time.tick));
92 } else {
93 /* compare real time */
94 return (snd_seq_compare_real_time(a: &a->time.time, b: &b->time.time));
95 }
96}
97
98/* compare timestamp between events */
99/* return negative if a < b;
100 * zero if a = b;
101 * positive if a > b;
102 */
103static inline int compare_timestamp_rel(struct snd_seq_event *a,
104 struct snd_seq_event *b)
105{
106 if ((a->flags & SNDRV_SEQ_TIME_STAMP_MASK) == SNDRV_SEQ_TIME_STAMP_TICK) {
107 /* compare ticks */
108 if (a->time.tick > b->time.tick)
109 return 1;
110 else if (a->time.tick == b->time.tick)
111 return 0;
112 else
113 return -1;
114 } else {
115 /* compare real time */
116 if (a->time.time.tv_sec > b->time.time.tv_sec)
117 return 1;
118 else if (a->time.time.tv_sec == b->time.time.tv_sec) {
119 if (a->time.time.tv_nsec > b->time.time.tv_nsec)
120 return 1;
121 else if (a->time.time.tv_nsec == b->time.time.tv_nsec)
122 return 0;
123 else
124 return -1;
125 } else
126 return -1;
127 }
128}
129
130/* enqueue cell to prioq */
131int snd_seq_prioq_cell_in(struct snd_seq_prioq * f,
132 struct snd_seq_event_cell * cell)
133{
134 struct snd_seq_event_cell *cur, *prev;
135 int count;
136 int prior;
137
138 if (snd_BUG_ON(!f || !cell))
139 return -EINVAL;
140
141 /* check flags */
142 prior = (cell->event.flags & SNDRV_SEQ_PRIORITY_MASK);
143
144 guard(spinlock_irqsave)(l: &f->lock);
145
146 /* check if this element needs to inserted at the end (ie. ordered
147 data is inserted) This will be very likeley if a sequencer
148 application or midi file player is feeding us (sequential) data */
149 if (f->tail && !prior) {
150 if (compare_timestamp(a: &cell->event, b: &f->tail->event)) {
151 /* add new cell to tail of the fifo */
152 f->tail->next = cell;
153 f->tail = cell;
154 cell->next = NULL;
155 f->cells++;
156 return 0;
157 }
158 }
159 /* traverse list of elements to find the place where the new cell is
160 to be inserted... Note that this is a order n process ! */
161
162 prev = NULL; /* previous cell */
163 cur = f->head; /* cursor */
164
165 count = 10000; /* FIXME: enough big, isn't it? */
166 while (cur != NULL) {
167 /* compare timestamps */
168 int rel = compare_timestamp_rel(a: &cell->event, b: &cur->event);
169 if (rel < 0)
170 /* new cell has earlier schedule time, */
171 break;
172 else if (rel == 0 && prior)
173 /* equal schedule time and prior to others */
174 break;
175 /* new cell has equal or larger schedule time, */
176 /* move cursor to next cell */
177 prev = cur;
178 cur = cur->next;
179 if (! --count) {
180 pr_err("ALSA: seq: cannot find a pointer.. infinite loop?\n");
181 return -EINVAL;
182 }
183 }
184
185 /* insert it before cursor */
186 if (prev != NULL)
187 prev->next = cell;
188 cell->next = cur;
189
190 if (f->head == cur) /* this is the first cell, set head to it */
191 f->head = cell;
192 if (cur == NULL) /* reached end of the list */
193 f->tail = cell;
194 f->cells++;
195 return 0;
196}
197
198/* return 1 if the current time >= event timestamp */
199static int event_is_ready(struct snd_seq_event *ev, void *current_time)
200{
201 if ((ev->flags & SNDRV_SEQ_TIME_STAMP_MASK) == SNDRV_SEQ_TIME_STAMP_TICK)
202 return snd_seq_compare_tick_time(a: current_time, b: &ev->time.tick);
203 else
204 return snd_seq_compare_real_time(a: current_time, b: &ev->time.time);
205}
206
207/* dequeue cell from prioq */
208struct snd_seq_event_cell *snd_seq_prioq_cell_out(struct snd_seq_prioq *f,
209 void *current_time)
210{
211 struct snd_seq_event_cell *cell;
212
213 if (f == NULL) {
214 pr_debug("ALSA: seq: snd_seq_prioq_cell_in() called with NULL prioq\n");
215 return NULL;
216 }
217
218 guard(spinlock_irqsave)(l: &f->lock);
219 cell = f->head;
220 if (cell && current_time && !event_is_ready(ev: &cell->event, current_time))
221 cell = NULL;
222 if (cell) {
223 f->head = cell->next;
224
225 /* reset tail if this was the last element */
226 if (f->tail == cell)
227 f->tail = NULL;
228
229 cell->next = NULL;
230 f->cells--;
231 }
232
233 return cell;
234}
235
236/* return number of events available in prioq */
237int snd_seq_prioq_avail(struct snd_seq_prioq * f)
238{
239 if (f == NULL) {
240 pr_debug("ALSA: seq: snd_seq_prioq_cell_in() called with NULL prioq\n");
241 return 0;
242 }
243 return f->cells;
244}
245
246/* remove cells matching with the condition */
247static void prioq_remove_cells(struct snd_seq_prioq *f,
248 bool (*match)(struct snd_seq_event_cell *cell,
249 void *arg),
250 void *arg)
251{
252 register struct snd_seq_event_cell *cell, *next;
253 struct snd_seq_event_cell *prev = NULL;
254 struct snd_seq_event_cell *freefirst = NULL, *freeprev = NULL, *freenext;
255
256 /* collect all removed cells */
257 scoped_guard(spinlock_irqsave, &f->lock) {
258 for (cell = f->head; cell; cell = next) {
259 next = cell->next;
260 if (!match(cell, arg)) {
261 prev = cell;
262 continue;
263 }
264
265 /* remove cell from prioq */
266 if (cell == f->head)
267 f->head = cell->next;
268 else
269 prev->next = cell->next;
270 if (cell == f->tail)
271 f->tail = cell->next;
272 f->cells--;
273
274 /* add cell to free list */
275 cell->next = NULL;
276 if (freefirst == NULL)
277 freefirst = cell;
278 else
279 freeprev->next = cell;
280 freeprev = cell;
281 }
282 }
283
284 /* remove selected cells */
285 while (freefirst) {
286 freenext = freefirst->next;
287 snd_seq_cell_free(cell: freefirst);
288 freefirst = freenext;
289 }
290}
291
292struct prioq_match_arg {
293 int client;
294 int timestamp;
295};
296
297static inline bool prioq_match(struct snd_seq_event_cell *cell, void *arg)
298{
299 struct prioq_match_arg *v = arg;
300
301 if (cell->event.source.client == v->client ||
302 cell->event.dest.client == v->client)
303 return true;
304 if (!v->timestamp)
305 return false;
306 switch (cell->event.flags & SNDRV_SEQ_TIME_STAMP_MASK) {
307 case SNDRV_SEQ_TIME_STAMP_TICK:
308 if (cell->event.time.tick)
309 return true;
310 break;
311 case SNDRV_SEQ_TIME_STAMP_REAL:
312 if (cell->event.time.time.tv_sec ||
313 cell->event.time.time.tv_nsec)
314 return true;
315 break;
316 }
317 return false;
318}
319
320/* remove cells for left client */
321void snd_seq_prioq_leave(struct snd_seq_prioq *f, int client, int timestamp)
322{
323 struct prioq_match_arg arg = { client, timestamp };
324
325 return prioq_remove_cells(f, match: prioq_match, arg: &arg);
326}
327
328struct prioq_remove_match_arg {
329 int client;
330 struct snd_seq_remove_events *info;
331};
332
333static bool prioq_remove_match(struct snd_seq_event_cell *cell, void *arg)
334{
335 struct prioq_remove_match_arg *v = arg;
336 struct snd_seq_event *ev = &cell->event;
337 struct snd_seq_remove_events *info = v->info;
338 int res;
339
340 if (ev->source.client != v->client)
341 return false;
342
343 if (info->remove_mode & SNDRV_SEQ_REMOVE_DEST) {
344 if (ev->dest.client != info->dest.client ||
345 ev->dest.port != info->dest.port)
346 return false;
347 }
348 if (info->remove_mode & SNDRV_SEQ_REMOVE_DEST_CHANNEL) {
349 if (! snd_seq_ev_is_channel_type(ev))
350 return false;
351 /* data.note.channel and data.control.channel are identical */
352 if (ev->data.note.channel != info->channel)
353 return false;
354 }
355 if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_AFTER) {
356 if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_TICK)
357 res = snd_seq_compare_tick_time(a: &ev->time.tick, b: &info->time.tick);
358 else
359 res = snd_seq_compare_real_time(a: &ev->time.time, b: &info->time.time);
360 if (!res)
361 return false;
362 }
363 if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_BEFORE) {
364 if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_TICK)
365 res = snd_seq_compare_tick_time(a: &ev->time.tick, b: &info->time.tick);
366 else
367 res = snd_seq_compare_real_time(a: &ev->time.time, b: &info->time.time);
368 if (res)
369 return false;
370 }
371 if (info->remove_mode & SNDRV_SEQ_REMOVE_EVENT_TYPE) {
372 if (ev->type != info->type)
373 return false;
374 }
375 if (info->remove_mode & SNDRV_SEQ_REMOVE_IGNORE_OFF) {
376 /* Do not remove off events */
377 switch (ev->type) {
378 case SNDRV_SEQ_EVENT_NOTEOFF:
379 /* case SNDRV_SEQ_EVENT_SAMPLE_STOP: */
380 return false;
381 default:
382 break;
383 }
384 }
385 if (info->remove_mode & SNDRV_SEQ_REMOVE_TAG_MATCH) {
386 if (info->tag != ev->tag)
387 return false;
388 }
389
390 return true;
391}
392
393/* remove cells matching remove criteria */
394void snd_seq_prioq_remove_events(struct snd_seq_prioq * f, int client,
395 struct snd_seq_remove_events *info)
396{
397 struct prioq_remove_match_arg arg = { client, info };
398
399 return prioq_remove_cells(f, match: prioq_remove_match, arg: &arg);
400}
401