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_sid(struct sctp_stream *stream, __u16 sid)
 208 {
 209         struct sctp_stream_priorities *prio = SCTP_SO(stream, sid)->ext->prio_head;
 210         int i;
 211
 212         if (!prio)
 213                 return;
 214
 215         SCTP_SO(stream, sid)->ext->prio_head = NULL;
 216         for (i = 0; i < stream->outcnt; i++) {
 217                 if (SCTP_SO(stream, i)->ext &&
 218                     SCTP_SO(stream, i)->ext->prio_head == prio)
 219                         return;
 220         }
 221
 222         kfree(prio);
 223 }
 224
 225 static void sctp_sched_prio_enqueue(struct sctp_outq *q,
 226                                     struct sctp_datamsg *msg)
 227 {
 228         struct sctp_stream *stream;
 229         struct sctp_chunk *ch;
 230         __u16 sid;
 231
 232         ch = list_first_entry(&msg->chunks, struct sctp_chunk, frag_list);
 233         sid = sctp_chunk_stream_no(ch);
 234         stream = &q->asoc->stream;
 235         sctp_sched_prio_sched(stream, SCTP_SO(stream, sid)->ext);
 236 }
 237
 238 static struct sctp_chunk *sctp_sched_prio_dequeue(struct sctp_outq *q)
 239 {
 240         struct sctp_stream *stream = &q->asoc->stream;
 241         struct sctp_stream_priorities *prio;
 242         struct sctp_stream_out_ext *soute;
 243         struct sctp_chunk *ch = NULL;
 244
 245         /* Bail out quickly if queue is empty */
 246         if (list_empty(&q->out_chunk_list))
 247                 goto out;
 248
 249         /* Find which chunk is next. It's easy, it's either the current
 250          * one or the first chunk on the next active stream.
 251          */
 252         if (stream->out_curr) {
 253                 soute = stream->out_curr->ext;
 254         } else {
 255                 prio = list_entry(stream->prio_list.next,
 256                                   struct sctp_stream_priorities, prio_sched);
 257                 soute = prio->next;
 258         }
 259         ch = list_entry(soute->outq.next, struct sctp_chunk, stream_list);
 260         sctp_sched_dequeue_common(q, ch);
 261
 262 out:
 263         return ch;
 264 }
 265
 266 static void sctp_sched_prio_dequeue_done(struct sctp_outq *q,
 267                                          struct sctp_chunk *ch)
 268 {
 269         struct sctp_stream_priorities *prio;
 270         struct sctp_stream_out_ext *soute;
 271         __u16 sid;
 272
 273         /* Last chunk on that msg, move to the next stream on
 274          * this priority.
 275          */
 276         sid = sctp_chunk_stream_no(ch);
 277         soute = SCTP_SO(&q->asoc->stream, sid)->ext;
 278         prio = soute->prio_head;
 279
 280         sctp_sched_prio_next_stream(prio);
 281
 282         if (list_empty(&soute->outq))
 283                 sctp_sched_prio_unsched(soute);
 284 }
 285
 286 static void sctp_sched_prio_sched_all(struct sctp_stream *stream)
 287 {
 288         struct sctp_association *asoc;
 289         struct sctp_stream_out *sout;
 290         struct sctp_chunk *ch;
 291
 292         asoc = container_of(stream, struct sctp_association, stream);
 293         list_for_each_entry(ch, &asoc->outqueue.out_chunk_list, list) {
 294                 __u16 sid;
 295
 296                 sid = sctp_chunk_stream_no(ch);
 297                 sout = SCTP_SO(stream, sid);
 298                 if (sout->ext)
 299                         sctp_sched_prio_sched(stream, sout->ext);
 300         }
 301 }
 302
 303 static void sctp_sched_prio_unsched_all(struct sctp_stream *stream)
 304 {
 305         struct sctp_stream_priorities *p, *tmp;
 306         struct sctp_stream_out_ext *soute, *souttmp;
 307
 308         list_for_each_entry_safe(p, tmp, &stream->prio_list, prio_sched)
 309                 list_for_each_entry_safe(soute, souttmp, &p->active, prio_list)
 310                         sctp_sched_prio_unsched(soute);
 311 }
 312
 313 static struct sctp_sched_ops sctp_sched_prio = {
 314         .set = sctp_sched_prio_set,
 315         .get = sctp_sched_prio_get,
 316         .init = sctp_sched_prio_init,
 317         .init_sid = sctp_sched_prio_init_sid,
 318         .free_sid = sctp_sched_prio_free_sid,
 319         .enqueue = sctp_sched_prio_enqueue,
 320         .dequeue = sctp_sched_prio_dequeue,
 321         .dequeue_done = sctp_sched_prio_dequeue_done,
 322         .sched_all = sctp_sched_prio_sched_all,
 323         .unsched_all = sctp_sched_prio_unsched_all,
 324 };
 325
 326 void sctp_sched_ops_prio_init(void)
 327 {
 328         sctp_sched_ops_register(SCTP_SS_PRIO, &sctp_sched_prio);
 329 }