net/sctp/stream_sched_prio.c

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /* SCTP kernel implementation
   3  * (C) Copyright Red Hat Inc. 2017
   4  *
   5  * This file is part of the SCTP kernel implementation
   6  *
   7  * These functions manipulate sctp stream queue/scheduling.
   8  *
   9  * Please send any bug reports or fixes you make to the
  10  * email addresched(es):
  11  *    lksctp developers <linux-sctp@vger.kernel.org>
  12  *
  13  * Written or modified by:
  14  *    Marcelo Ricardo Leitner <marcelo.leitner@gmail.com>
  15  */
  16
  17 #include <linux/list.h>
  18 #include <net/sctp/sctp.h>
  19 #include <net/sctp/sm.h>
  20 #include <net/sctp/stream_sched.h>
  21
  22 /* Priority handling
  23  * RFC DRAFT ndata section 3.4
  24  */
  25
  26 static void sctp_sched_prio_unsched_all(struct sctp_stream *stream);
  27
  28 static struct sctp_stream_priorities *sctp_sched_prio_head_get(struct sctp_stream_priorities *p)
  29 {
  30         p->users++;
  31         return p;
  32 }
  33
  34 static void sctp_sched_prio_head_put(struct sctp_stream_priorities *p)
  35 {
  36         if (p && --p->users == 0)
  37                 kfree(p);
  38 }
  39
  40 static struct sctp_stream_priorities *sctp_sched_prio_new_head(
  41                         struct sctp_stream *stream, int prio, gfp_t gfp)
  42 {
  43         struct sctp_stream_priorities *p;
  44
  45         p = kmalloc(sizeof(*p), gfp);
  46         if (!p)
  47                 return NULL;
  48
  49         INIT_LIST_HEAD(&p->prio_sched);
  50         INIT_LIST_HEAD(&p->active);
  51         p->next = NULL;
  52         p->prio = prio;
  53         p->users = 1;
  54
  55         return p;
  56 }
  57
  58 static struct sctp_stream_priorities *sctp_sched_prio_get_head(
  59                         struct sctp_stream *stream, int prio, gfp_t gfp)
  60 {
  61         struct sctp_stream_priorities *p;
  62         int i;
  63
  64         /* Look into scheduled priorities first, as they are sorted and
  65          * we can find it fast IF it's scheduled.
  66          */
  67         list_for_each_entry(p, &stream->prio_list, prio_sched) {
  68                 if (p->prio == prio)
  69                         return sctp_sched_prio_head_get(p);
  70                 if (p->prio > prio)
  71                         break;
  72         }
  73
  74         /* No luck. So we search on all streams now. */
  75         for (i = 0; i < stream->outcnt; i++) {
  76                 if (!SCTP_SO(stream, i)->ext)
  77                         continue;
  78
  79                 p = SCTP_SO(stream, i)->ext->prio_head;
  80                 if (!p)
  81                         /* Means all other streams won't be initialized
  82                          * as well.
  83                          */
  84                         break;
  85                 if (p->prio == prio)
  86                         return sctp_sched_prio_head_get(p);
  87         }
  88
  89         /* If not even there, allocate a new one. */
  90         return sctp_sched_prio_new_head(stream, prio, gfp);
  91 }
  92
  93 static void sctp_sched_prio_next_stream(struct sctp_stream_priorities *p)
  94 {
  95         struct list_head *pos;
  96
  97         pos = p->next->prio_list.next;
  98         if (pos == &p->active)
  99                 pos = pos->next;
 100         p->next = list_entry(pos, struct sctp_stream_out_ext, prio_list);
 101 }
 102
 103 static bool sctp_sched_prio_unsched(struct sctp_stream_out_ext *soute)
 104 {
 105         bool scheduled = false;
 106
 107         if (!list_empty(&soute->prio_list)) {
 108                 struct sctp_stream_priorities *prio_head = soute->prio_head;
 109
 110                 /* Scheduled */
 111                 scheduled = true;
 112
 113                 if (prio_head->next == soute)
 114                         /* Try to move to the next stream */
 115                         sctp_sched_prio_next_stream(prio_head);
 116
 117                 list_del_init(&soute->prio_list);
 118
 119                 /* Also unsched the priority if this was the last stream */
 120                 if (list_empty(&prio_head->active)) {
 121                         list_del_init(&prio_head->prio_sched);
 122                         /* If there is no stream left, clear next */
 123                         prio_head->next = NULL;
 124                 }
 125         }
 126
 127         return scheduled;
 128 }
 129
 130 static void sctp_sched_prio_sched(struct sctp_stream *stream,
 131                                   struct sctp_stream_out_ext *soute)
 132 {
 133         struct sctp_stream_priorities *prio, *prio_head;
 134
 135         prio_head = soute->prio_head;
 136
 137         /* Nothing to do if already scheduled */
 138         if (!list_empty(&soute->prio_list))
 139                 return;
 140
 141         /* Schedule the stream. If there is a next, we schedule the new
 142          * one before it, so it's the last in round robin order.
 143          * If there isn't, we also have to schedule the priority.
 144          */
 145         if (prio_head->next) {
 146                 list_add(&soute->prio_list, prio_head->next->prio_list.prev);
 147                 return;
 148         }
 149
 150         list_add(&soute->prio_list, &prio_head->active);
 151         prio_head->next = soute;
 152
 153         list_for_each_entry(prio, &stream->prio_list, prio_sched) {
 154                 if (prio->prio > prio_head->prio) {
 155                         list_add(&prio_head->prio_sched, prio->prio_sched.prev);
 156                         return;
 157                 }
 158         }
 159
 160         list_add_tail(&prio_head->prio_sched, &stream->prio_list);
 161 }
 162
 163 static int sctp_sched_prio_set(struct sctp_stream *stream, __u16 sid,
 164                                __u16 prio, gfp_t gfp)
 165 {
 166         struct sctp_stream_out *sout = SCTP_SO(stream, sid);
 167         struct sctp_stream_out_ext *soute = sout->ext;
 168         struct sctp_stream_priorities *prio_head, *old;
 169         bool reschedule = false;
 170
 171         old = soute->prio_head;
 172         if (old && old->prio == prio)
 173                 return 0;
 174
 175         prio_head = sctp_sched_prio_get_head(stream, prio, gfp);
 176         if (!prio_head)
 177                 return -ENOMEM;
 178
 179         reschedule = sctp_sched_prio_unsched(soute);
 180         soute->prio_head = prio_head;
 181         if (reschedule)
 182                 sctp_sched_prio_sched(stream, soute);
 183
 184         sctp_sched_prio_head_put(old);
 185         return 0;
 186 }
 187
 188 static int sctp_sched_prio_get(struct sctp_stream *stream, __u16 sid,
 189                                __u16 *value)
 190 {
 191         *value = SCTP_SO(stream, sid)->ext->prio_head->prio;
 192         return 0;
 193 }
 194
 195 static int sctp_sched_prio_init(struct sctp_stream *stream)
 196 {
 197         INIT_LIST_HEAD(&stream->prio_list);
 198
 199         return 0;
 200 }
 201
 202 static int sctp_sched_prio_init_sid(struct sctp_stream *stream, __u16 sid,
 203                                     gfp_t gfp)
 204 {
 205         INIT_LIST_HEAD(&SCTP_SO(stream, sid)->ext->prio_list);
 206         return sctp_sched_prio_set(stream, sid, 0, gfp);
 207 }
 208
 209 static void sctp_sched_prio_free_sid(struct sctp_stream *stream, __u16 sid)
 210 {
 211         sctp_sched_prio_head_put(SCTP_SO(stream, sid)->ext->prio_head);
 212         SCTP_SO(stream, sid)->ext->prio_head = NULL;
 213 }
 214
 215 static void sctp_sched_prio_free(struct sctp_stream *stream)
 216 {
 217         struct sctp_stream_priorities *prio, *n;
 218         LIST_HEAD(list);
 219         int i;
 220
 221         /* As we don't keep a list of priorities, to avoid multiple
 222          * frees we have to do it in 3 steps:
 223          *   1. unsched everyone, so the lists are free to use in 2.
 224          *   2. build the list of the priorities
 225          *   3. free the list
 226          */
 227         sctp_sched_prio_unsched_all(stream);
 228         for (i = 0; i < stream->outcnt; i++) {
 229                 if (!SCTP_SO(stream, i)->ext)
 230                         continue;
 231                 prio = SCTP_SO(stream, i)->ext->prio_head;
 232                 if (prio && list_empty(&prio->prio_sched))
 233                         list_add(&prio->prio_sched, &list);
 234         }
 235         list_for_each_entry_safe(prio, n, &list, prio_sched) {
 236                 list_del_init(&prio->prio_sched);
 237                 kfree(prio);
 238         }
 239 }
 240
 241 static void sctp_sched_prio_enqueue(struct sctp_outq *q,
 242                                     struct sctp_datamsg *msg)
 243 {
 244         struct sctp_stream *stream;
 245         struct sctp_chunk *ch;
 246         __u16 sid;
 247
 248         ch = list_first_entry(&msg->chunks, struct sctp_chunk, frag_list);
 249         sid = sctp_chunk_stream_no(ch);
 250         stream = &q->asoc->stream;
 251         sctp_sched_prio_sched(stream, SCTP_SO(stream, sid)->ext);
 252 }
 253
 254 static struct sctp_chunk *sctp_sched_prio_dequeue(struct sctp_outq *q)
 255 {
 256         struct sctp_stream *stream = &q->asoc->stream;
 257         struct sctp_stream_priorities *prio;
 258         struct sctp_stream_out_ext *soute;
 259         struct sctp_chunk *ch = NULL;
 260
 261         /* Bail out quickly if queue is empty */
 262         if (list_empty(&q->out_chunk_list))
 263                 goto out;
 264
 265         /* Find which chunk is next. It's easy, it's either the current
 266          * one or the first chunk on the next active stream.
 267          */
 268         if (stream->out_curr) {
 269                 soute = stream->out_curr->ext;
 270         } else {
 271                 prio = list_entry(stream->prio_list.next,
 272                                   struct sctp_stream_priorities, prio_sched);
 273                 soute = prio->next;
 274         }
 275         ch = list_entry(soute->outq.next, struct sctp_chunk, stream_list);
 276         sctp_sched_dequeue_common(q, ch);
 277
 278 out:
 279         return ch;
 280 }
 281
 282 static void sctp_sched_prio_dequeue_done(struct sctp_outq *q,
 283                                          struct sctp_chunk *ch)
 284 {
 285         struct sctp_stream_priorities *prio;
 286         struct sctp_stream_out_ext *soute;
 287         __u16 sid;
 288
 289         /* Last chunk on that msg, move to the next stream on
 290          * this priority.
 291          */
 292         sid = sctp_chunk_stream_no(ch);
 293         soute = SCTP_SO(&q->asoc->stream, sid)->ext;
 294         prio = soute->prio_head;
 295
 296         sctp_sched_prio_next_stream(prio);
 297
 298         if (list_empty(&soute->outq))
 299                 sctp_sched_prio_unsched(soute);
 300 }
 301
 302 static void sctp_sched_prio_sched_all(struct sctp_stream *stream)
 303 {
 304         struct sctp_association *asoc;
 305         struct sctp_stream_out *sout;
 306         struct sctp_chunk *ch;
 307
 308         asoc = container_of(stream, struct sctp_association, stream);
 309         list_for_each_entry(ch, &asoc->outqueue.out_chunk_list, list) {
 310                 __u16 sid;
 311
 312                 sid = sctp_chunk_stream_no(ch);
 313                 sout = SCTP_SO(stream, sid);
 314                 if (sout->ext)
 315                         sctp_sched_prio_sched(stream, sout->ext);
 316         }
 317 }
 318
 319 static void sctp_sched_prio_unsched_all(struct sctp_stream *stream)
 320 {
 321         struct sctp_stream_priorities *p, *tmp;
 322         struct sctp_stream_out_ext *soute, *souttmp;
 323
 324         list_for_each_entry_safe(p, tmp, &stream->prio_list, prio_sched)
 325                 list_for_each_entry_safe(soute, souttmp, &p->active, prio_list)
 326                         sctp_sched_prio_unsched(soute);
 327 }
 328
 329 static struct sctp_sched_ops sctp_sched_prio = {
 330         .set = sctp_sched_prio_set,
 331         .get = sctp_sched_prio_get,
 332         .init = sctp_sched_prio_init,
 333         .init_sid = sctp_sched_prio_init_sid,
 334         .free_sid = sctp_sched_prio_free_sid,
 335         .free = sctp_sched_prio_free,
 336         .enqueue = sctp_sched_prio_enqueue,
 337         .dequeue = sctp_sched_prio_dequeue,
 338         .dequeue_done = sctp_sched_prio_dequeue_done,
 339         .sched_all = sctp_sched_prio_sched_all,
 340         .unsched_all = sctp_sched_prio_unsched_all,
 341 };
 342
 343 void sctp_sched_ops_prio_init(void)
 344 {
 345         sctp_sched_ops_register(SCTP_SS_PRIO, &sctp_sched_prio);
 346 }