Branch data     Line data    Source code

       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                 :          0 : struct snd_seq_prioq *snd_seq_prioq_new(void)
      43                 :            : {
      44                 :          0 :         struct snd_seq_prioq *f;
      45                 :            : 
      46                 :          0 :         f = kzalloc(sizeof(*f), GFP_KERNEL);
      47         [ #  # ]:          0 :         if (!f)
      48                 :            :                 return NULL;
      49                 :            :         
      50                 :          0 :         spin_lock_init(&f->lock);
      51                 :          0 :         f->head = NULL;
      52                 :          0 :         f->tail = NULL;
      53                 :          0 :         f->cells = 0;
      54                 :            :         
      55                 :          0 :         return f;
      56                 :            : }
      57                 :            : 
      58                 :            : /* delete prioq (destructor) */
      59                 :          0 : void snd_seq_prioq_delete(struct snd_seq_prioq **fifo)
      60                 :            : {
      61                 :          0 :         struct snd_seq_prioq *f = *fifo;
      62                 :          0 :         *fifo = NULL;
      63                 :            : 
      64         [ #  # ]:          0 :         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         [ #  # ]:          0 :         if (f->cells > 0) {
      73                 :            :                 /* drain prioQ */
      74         [ #  # ]:          0 :                 while (f->cells > 0)
      75                 :          0 :                         snd_seq_cell_free(snd_seq_prioq_cell_out(f, NULL));
      76                 :            :         }
      77                 :            :         
      78                 :          0 :         kfree(f);
      79                 :            : }
      80                 :            : 
      81                 :            : 
      82                 :            : 
      83                 :            : 
      84                 :            : /* compare timestamp between events */
      85                 :            : /* return 1 if a >= b; 0 */
      86                 :          0 : static inline int compare_timestamp(struct snd_seq_event *a,
      87                 :            :                                     struct snd_seq_event *b)
      88                 :            : {
      89                 :          0 :         if ((a->flags & SNDRV_SEQ_TIME_STAMP_MASK) == SNDRV_SEQ_TIME_STAMP_TICK) {
      90                 :            :                 /* compare ticks */
      91         [ #  # ]:          0 :                 return (snd_seq_compare_tick_time(&a->time.tick, &b->time.tick));
      92                 :            :         } else {
      93                 :            :                 /* compare real time */
      94         [ #  # ]:          0 :                 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                 :          0 : static inline int compare_timestamp_rel(struct snd_seq_event *a,
     104                 :            :                                         struct snd_seq_event *b)
     105                 :            : {
     106                 :          0 :         if ((a->flags & SNDRV_SEQ_TIME_STAMP_MASK) == SNDRV_SEQ_TIME_STAMP_TICK) {
     107                 :            :                 /* compare ticks */
     108         [ #  # ]:          0 :                 if (a->time.tick > b->time.tick)
     109                 :            :                         return 1;
     110         [ #  # ]:          0 :                 else if (a->time.tick == b->time.tick)
     111                 :            :                         return 0;
     112                 :            :                 else
     113                 :            :                         return -1;
     114                 :            :         } else {
     115                 :            :                 /* compare real time */
     116         [ #  # ]:          0 :                 if (a->time.time.tv_sec > b->time.time.tv_sec)
     117                 :            :                         return 1;
     118         [ #  # ]:          0 :                 else if (a->time.time.tv_sec == b->time.time.tv_sec) {
     119         [ #  # ]:          0 :                         if (a->time.time.tv_nsec > b->time.time.tv_nsec)
     120                 :            :                                 return 1;
     121         [ #  # ]:          0 :                         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                 :          0 : int snd_seq_prioq_cell_in(struct snd_seq_prioq * f,
     132                 :            :                           struct snd_seq_event_cell * cell)
     133                 :            : {
     134                 :          0 :         struct snd_seq_event_cell *cur, *prev;
     135                 :          0 :         unsigned long flags;
     136                 :          0 :         int count;
     137                 :          0 :         int prior;
     138                 :            : 
     139         [ #  # ]:          0 :         if (snd_BUG_ON(!f || !cell))
     140                 :            :                 return -EINVAL;
     141                 :            :         
     142                 :            :         /* check flags */
     143                 :          0 :         prior = (cell->event.flags & SNDRV_SEQ_PRIORITY_MASK);
     144                 :            : 
     145                 :          0 :         spin_lock_irqsave(&f->lock, flags);
     146                 :            : 
     147                 :            :         /* check if this element needs to inserted at the end (ie. ordered 
     148                 :            :            data is inserted) This will be very likeley if a sequencer 
     149                 :            :            application or midi file player is feeding us (sequential) data */
     150   [ #  #  #  # ]:          0 :         if (f->tail && !prior) {
     151   [ #  #  #  # ]:          0 :                 if (compare_timestamp(&cell->event, &f->tail->event)) {
     152                 :            :                         /* add new cell to tail of the fifo */
     153                 :          0 :                         f->tail->next = cell;
     154                 :          0 :                         f->tail = cell;
     155                 :          0 :                         cell->next = NULL;
     156                 :          0 :                         f->cells++;
     157                 :          0 :                         spin_unlock_irqrestore(&f->lock, flags);
     158                 :          0 :                         return 0;
     159                 :            :                 }
     160                 :            :         }
     161                 :            :         /* traverse list of elements to find the place where the new cell is
     162                 :            :            to be inserted... Note that this is a order n process ! */
     163                 :            : 
     164                 :          0 :         prev = NULL;            /* previous cell */
     165                 :          0 :         cur = f->head;               /* cursor */
     166                 :            : 
     167                 :          0 :         count = 10000; /* FIXME: enough big, isn't it? */
     168         [ #  # ]:          0 :         while (cur != NULL) {
     169                 :            :                 /* compare timestamps */
     170         [ #  # ]:          0 :                 int rel = compare_timestamp_rel(&cell->event, &cur->event);
     171                 :            :                 if (rel < 0)
     172                 :            :                         /* new cell has earlier schedule time, */
     173                 :            :                         break;
     174         [ #  # ]:          0 :                 else if (rel == 0 && prior)
     175                 :            :                         /* equal schedule time and prior to others */
     176                 :            :                         break;
     177                 :            :                 /* new cell has equal or larger schedule time, */
     178                 :            :                 /* move cursor to next cell */
     179                 :          0 :                 prev = cur;
     180                 :          0 :                 cur = cur->next;
     181         [ #  # ]:          0 :                 if (! --count) {
     182                 :          0 :                         spin_unlock_irqrestore(&f->lock, flags);
     183                 :          0 :                         pr_err("ALSA: seq: cannot find a pointer.. infinite loop?\n");
     184                 :          0 :                         return -EINVAL;
     185                 :            :                 }
     186                 :            :         }
     187                 :            : 
     188                 :            :         /* insert it before cursor */
     189         [ #  # ]:          0 :         if (prev != NULL)
     190                 :          0 :                 prev->next = cell;
     191                 :          0 :         cell->next = cur;
     192                 :            : 
     193         [ #  # ]:          0 :         if (f->head == cur) /* this is the first cell, set head to it */
     194                 :          0 :                 f->head = cell;
     195         [ #  # ]:          0 :         if (cur == NULL) /* reached end of the list */
     196                 :          0 :                 f->tail = cell;
     197                 :          0 :         f->cells++;
     198                 :          0 :         spin_unlock_irqrestore(&f->lock, flags);
     199                 :          0 :         return 0;
     200                 :            : }
     201                 :            : 
     202                 :            : /* return 1 if the current time >= event timestamp */
     203                 :          0 : static int event_is_ready(struct snd_seq_event *ev, void *current_time)
     204                 :            : {
     205         [ #  # ]:          0 :         if ((ev->flags & SNDRV_SEQ_TIME_STAMP_MASK) == SNDRV_SEQ_TIME_STAMP_TICK)
     206         [ #  # ]:          0 :                 return snd_seq_compare_tick_time(current_time, &ev->time.tick);
     207                 :            :         else
     208         [ #  # ]:          0 :                 return snd_seq_compare_real_time(current_time, &ev->time.time);
     209                 :            : }
     210                 :            : 
     211                 :            : /* dequeue cell from prioq */
     212                 :          0 : struct snd_seq_event_cell *snd_seq_prioq_cell_out(struct snd_seq_prioq *f,
     213                 :            :                                                   void *current_time)
     214                 :            : {
     215                 :          0 :         struct snd_seq_event_cell *cell;
     216                 :          0 :         unsigned long flags;
     217                 :            : 
     218         [ #  # ]:          0 :         if (f == NULL) {
     219                 :            :                 pr_debug("ALSA: seq: snd_seq_prioq_cell_in() called with NULL prioq\n");
     220                 :            :                 return NULL;
     221                 :            :         }
     222                 :          0 :         spin_lock_irqsave(&f->lock, flags);
     223                 :            : 
     224                 :          0 :         cell = f->head;
     225   [ #  #  #  # ]:          0 :         if (cell && current_time && !event_is_ready(&cell->event, current_time))
     226                 :            :                 cell = NULL;
     227         [ #  # ]:          0 :         if (cell) {
     228                 :          0 :                 f->head = cell->next;
     229                 :            : 
     230                 :            :                 /* reset tail if this was the last element */
     231         [ #  # ]:          0 :                 if (f->tail == cell)
     232                 :          0 :                         f->tail = NULL;
     233                 :            : 
     234                 :          0 :                 cell->next = NULL;
     235                 :          0 :                 f->cells--;
     236                 :            :         }
     237                 :            : 
     238                 :          0 :         spin_unlock_irqrestore(&f->lock, flags);
     239                 :          0 :         return cell;
     240                 :            : }
     241                 :            : 
     242                 :            : /* return number of events available in prioq */
     243                 :          0 : int snd_seq_prioq_avail(struct snd_seq_prioq * f)
     244                 :            : {
     245         [ #  # ]:          0 :         if (f == NULL) {
     246                 :            :                 pr_debug("ALSA: seq: snd_seq_prioq_cell_in() called with NULL prioq\n");
     247                 :            :                 return 0;
     248                 :            :         }
     249                 :          0 :         return f->cells;
     250                 :            : }
     251                 :            : 
     252                 :          0 : static inline int prioq_match(struct snd_seq_event_cell *cell,
     253                 :            :                               int client, int timestamp)
     254                 :            : {
     255                 :          0 :         if (cell->event.source.client == client ||
     256         [ #  # ]:          0 :             cell->event.dest.client == client)
     257                 :            :                 return 1;
     258         [ #  # ]:          0 :         if (!timestamp)
     259                 :            :                 return 0;
     260         [ #  # ]:          0 :         switch (cell->event.flags & SNDRV_SEQ_TIME_STAMP_MASK) {
     261                 :          0 :         case SNDRV_SEQ_TIME_STAMP_TICK:
     262         [ #  # ]:          0 :                 if (cell->event.time.tick)
     263                 :            :                         return 1;
     264                 :            :                 break;
     265                 :          0 :         case SNDRV_SEQ_TIME_STAMP_REAL:
     266         [ #  # ]:          0 :                 if (cell->event.time.time.tv_sec ||
     267         [ #  # ]:          0 :                     cell->event.time.time.tv_nsec)
     268                 :            :                         return 1;
     269                 :            :                 break;
     270                 :            :         }
     271                 :            :         return 0;
     272                 :            : }
     273                 :            : 
     274                 :            : /* remove cells for left client */
     275                 :          0 : void snd_seq_prioq_leave(struct snd_seq_prioq * f, int client, int timestamp)
     276                 :            : {
     277                 :          0 :         register struct snd_seq_event_cell *cell, *next;
     278                 :          0 :         unsigned long flags;
     279                 :          0 :         struct snd_seq_event_cell *prev = NULL;
     280                 :          0 :         struct snd_seq_event_cell *freefirst = NULL, *freeprev = NULL, *freenext;
     281                 :            : 
     282                 :            :         /* collect all removed cells */
     283                 :          0 :         spin_lock_irqsave(&f->lock, flags);
     284                 :          0 :         cell = f->head;
     285         [ #  # ]:          0 :         while (cell) {
     286                 :          0 :                 next = cell->next;
     287         [ #  # ]:          0 :                 if (prioq_match(cell, client, timestamp)) {
     288                 :            :                         /* remove cell from prioq */
     289         [ #  # ]:          0 :                         if (cell == f->head) {
     290                 :          0 :                                 f->head = cell->next;
     291                 :            :                         } else {
     292                 :          0 :                                 prev->next = cell->next;
     293                 :            :                         }
     294         [ #  # ]:          0 :                         if (cell == f->tail)
     295                 :          0 :                                 f->tail = cell->next;
     296                 :          0 :                         f->cells--;
     297                 :            :                         /* add cell to free list */
     298                 :          0 :                         cell->next = NULL;
     299         [ #  # ]:          0 :                         if (freefirst == NULL) {
     300                 :            :                                 freefirst = cell;
     301                 :            :                         } else {
     302                 :          0 :                                 freeprev->next = cell;
     303                 :            :                         }
     304                 :            :                         freeprev = cell;
     305                 :            :                 } else {
     306                 :            : #if 0
     307                 :            :                         pr_debug("ALSA: seq: type = %i, source = %i, dest = %i, "
     308                 :            :                                "client = %i\n",
     309                 :            :                                 cell->event.type,
     310                 :            :                                 cell->event.source.client,
     311                 :            :                                 cell->event.dest.client,
     312                 :            :                                 client);
     313                 :            : #endif
     314                 :            :                         prev = cell;
     315                 :            :                 }
     316                 :            :                 cell = next;            
     317                 :            :         }
     318                 :          0 :         spin_unlock_irqrestore(&f->lock, flags); 
     319                 :            : 
     320                 :            :         /* remove selected cells */
     321         [ #  # ]:          0 :         while (freefirst) {
     322                 :          0 :                 freenext = freefirst->next;
     323                 :          0 :                 snd_seq_cell_free(freefirst);
     324                 :          0 :                 freefirst = freenext;
     325                 :            :         }
     326                 :          0 : }
     327                 :            : 
     328                 :          0 : static int prioq_remove_match(struct snd_seq_remove_events *info,
     329                 :            :                               struct snd_seq_event *ev)
     330                 :            : {
     331                 :          0 :         int res;
     332                 :            : 
     333         [ #  # ]:          0 :         if (info->remove_mode & SNDRV_SEQ_REMOVE_DEST) {
     334         [ #  # ]:          0 :                 if (ev->dest.client != info->dest.client ||
     335                 :            :                                 ev->dest.port != info->dest.port)
     336                 :            :                         return 0;
     337                 :            :         }
     338         [ #  # ]:          0 :         if (info->remove_mode & SNDRV_SEQ_REMOVE_DEST_CHANNEL) {
     339         [ #  # ]:          0 :                 if (! snd_seq_ev_is_channel_type(ev))
     340                 :            :                         return 0;
     341                 :            :                 /* data.note.channel and data.control.channel are identical */
     342         [ #  # ]:          0 :                 if (ev->data.note.channel != info->channel)
     343                 :            :                         return 0;
     344                 :            :         }
     345         [ #  # ]:          0 :         if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_AFTER) {
     346         [ #  # ]:          0 :                 if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_TICK)
     347         [ #  # ]:          0 :                         res = snd_seq_compare_tick_time(&ev->time.tick, &info->time.tick);
     348                 :            :                 else
     349         [ #  # ]:          0 :                         res = snd_seq_compare_real_time(&ev->time.time, &info->time.time);
     350         [ #  # ]:          0 :                 if (!res)
     351                 :            :                         return 0;
     352                 :            :         }
     353         [ #  # ]:          0 :         if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_BEFORE) {
     354         [ #  # ]:          0 :                 if (info->remove_mode & SNDRV_SEQ_REMOVE_TIME_TICK)
     355         [ #  # ]:          0 :                         res = snd_seq_compare_tick_time(&ev->time.tick, &info->time.tick);
     356                 :            :                 else
     357         [ #  # ]:          0 :                         res = snd_seq_compare_real_time(&ev->time.time, &info->time.time);
     358         [ #  # ]:          0 :                 if (res)
     359                 :            :                         return 0;
     360                 :            :         }
     361         [ #  # ]:          0 :         if (info->remove_mode & SNDRV_SEQ_REMOVE_EVENT_TYPE) {
     362         [ #  # ]:          0 :                 if (ev->type != info->type)
     363                 :            :                         return 0;
     364                 :            :         }
     365         [ #  # ]:          0 :         if (info->remove_mode & SNDRV_SEQ_REMOVE_IGNORE_OFF) {
     366                 :            :                 /* Do not remove off events */
     367         [ #  # ]:          0 :                 switch (ev->type) {
     368                 :            :                 case SNDRV_SEQ_EVENT_NOTEOFF:
     369                 :            :                 /* case SNDRV_SEQ_EVENT_SAMPLE_STOP: */
     370                 :            :                         return 0;
     371                 :            :                 default:
     372                 :            :                         break;
     373                 :            :                 }
     374                 :          0 :         }
     375         [ #  # ]:          0 :         if (info->remove_mode & SNDRV_SEQ_REMOVE_TAG_MATCH) {
     376         [ #  # ]:          0 :                 if (info->tag != ev->tag)
     377                 :          0 :                         return 0;
     378                 :            :         }
     379                 :            : 
     380                 :            :         return 1;
     381                 :            : }
     382                 :            : 
     383                 :            : /* remove cells matching remove criteria */
     384                 :          0 : void snd_seq_prioq_remove_events(struct snd_seq_prioq * f, int client,
     385                 :            :                                  struct snd_seq_remove_events *info)
     386                 :            : {
     387                 :          0 :         struct snd_seq_event_cell *cell, *next;
     388                 :          0 :         unsigned long flags;
     389                 :          0 :         struct snd_seq_event_cell *prev = NULL;
     390                 :          0 :         struct snd_seq_event_cell *freefirst = NULL, *freeprev = NULL, *freenext;
     391                 :            : 
     392                 :            :         /* collect all removed cells */
     393                 :          0 :         spin_lock_irqsave(&f->lock, flags);
     394                 :          0 :         cell = f->head;
     395                 :            : 
     396         [ #  # ]:          0 :         while (cell) {
     397                 :          0 :                 next = cell->next;
     398         [ #  # ]:          0 :                 if (cell->event.source.client == client &&
     399         [ #  # ]:          0 :                         prioq_remove_match(info, &cell->event)) {
     400                 :            : 
     401                 :            :                         /* remove cell from prioq */
     402         [ #  # ]:          0 :                         if (cell == f->head) {
     403                 :          0 :                                 f->head = cell->next;
     404                 :            :                         } else {
     405                 :          0 :                                 prev->next = cell->next;
     406                 :            :                         }
     407                 :            : 
     408         [ #  # ]:          0 :                         if (cell == f->tail)
     409                 :          0 :                                 f->tail = cell->next;
     410                 :          0 :                         f->cells--;
     411                 :            : 
     412                 :            :                         /* add cell to free list */
     413                 :          0 :                         cell->next = NULL;
     414         [ #  # ]:          0 :                         if (freefirst == NULL) {
     415                 :            :                                 freefirst = cell;
     416                 :            :                         } else {
     417                 :          0 :                                 freeprev->next = cell;
     418                 :            :                         }
     419                 :            : 
     420                 :            :                         freeprev = cell;
     421                 :            :                 } else {
     422                 :            :                         prev = cell;
     423                 :            :                 }
     424                 :            :                 cell = next;            
     425                 :            :         }
     426                 :          0 :         spin_unlock_irqrestore(&f->lock, flags); 
     427                 :            : 
     428                 :            :         /* remove selected cells */
     429         [ #  # ]:          0 :         while (freefirst) {
     430                 :          0 :                 freenext = freefirst->next;
     431                 :          0 :                 snd_seq_cell_free(freefirst);
     432                 :          0 :                 freefirst = freenext;
     433                 :            :         }
     434                 :          0 : }
     435                 :            : 
     436                 :            :