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