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) */ 42 struct 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) */ 59 void 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(snd_seq_prioq_cell_out(f, NULL)); 76 } 77 78 kfree(f); 79 } 80 81 82 83 84 /* compare timestamp between events */ 85 /* return 1 if a >= b; 0 */ 86 static 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->time.tick, &b->time.tick)); 92 } else { 93 /* compare real time */ 94 return (snd_seq_compare_real_time(&a->time.time, &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 */ 103 static 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 */ 131 int 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)(&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(&cell->event, &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(&cell->event, &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 */ 199 static 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(current_time, &ev->time.tick); 203 else 204 return snd_seq_compare_real_time(current_time, &ev->time.time); 205 } 206 207 /* dequeue cell from prioq */ 208 struct 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)(&f->lock); 219 cell = f->head; 220 if (cell && current_time && !event_is_ready(&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 */ 237 int 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 */ 247 static 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(freefirst); 288 freefirst = freenext; 289 } 290 } 291 292 struct prioq_match_arg { 293 int client; 294 int timestamp; 295 }; 296 297 static 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 */ 321 void 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, prioq_match, &arg); 326 } 327 328 struct prioq_remove_match_arg { 329 int client; 330 struct snd_seq_remove_events *info; 331 }; 332 333 static 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(&ev->time.tick, &info->time.tick); 358 else 359 res = snd_seq_compare_real_time(&ev->time.time, &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(&ev->time.tick, &info->time.tick); 366 else 367 res = snd_seq_compare_real_time(&ev->time.time, &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 */ 394 void 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, prioq_remove_match, &arg); 400 } 401