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_free(struct sctp_stream *stream)
 226 {
 227         struct sctp_stream_priorities *prio, *n;
 228         LIST_HEAD(list);
 229         int i;
 230
 231         /* As we don't keep a list of priorities, to avoid multiple
 232          * frees we have to do it in 3 steps:
 233          *   1. unsched everyone, so the lists are free to use in 2.
 234          *   2. build the list of the priorities
 235          *   3. free the list
 236          */
 237         sctp_sched_prio_unsched_all(stream);
 238         for (i = 0; i < stream->outcnt; i++) {
 239                 if (!SCTP_SO(stream, i)->ext)
 240                         continue;
 241                 prio = SCTP_SO(stream, i)->ext->prio_head;
 242                 if (prio && list_empty(&prio->prio_sched))
 243                         list_add(&prio->prio_sched, &list);
 244         }
 245         list_for_each_entry_safe(prio, n, &list, prio_sched) {
 246                 list_del_init(&prio->prio_sched);
 247                 kfree(prio);
 248         }
 249 }
 250
 251 static void sctp_sched_prio_enqueue(struct sctp_outq *q,
 252                                     struct sctp_datamsg *msg)
 253 {
 254         struct sctp_stream *stream;
 255         struct sctp_chunk *ch;
 256         __u16 sid;
 257
 258         ch = list_first_entry(&msg->chunks, struct sctp_chunk, frag_list);
 259         sid = sctp_chunk_stream_no(ch);
 260         stream = &q->asoc->stream;
 261         sctp_sched_prio_sched(stream, SCTP_SO(stream, sid)->ext);
 262 }
 263
 264 static struct sctp_chunk *sctp_sched_prio_dequeue(struct sctp_outq *q)
 265 {
 266         struct sctp_stream *stream = &q->asoc->stream;
 267         struct sctp_stream_priorities *prio;
 268         struct sctp_stream_out_ext *soute;
 269         struct sctp_chunk *ch = NULL;
 270
 271         /* Bail out quickly if queue is empty */
 272         if (list_empty(&q->out_chunk_list))
 273                 goto out;
 274
 275         /* Find which chunk is next. It's easy, it's either the current
 276          * one or the first chunk on the next active stream.
 277          */
 278         if (stream->out_curr) {
 279                 soute = stream->out_curr->ext;
 280         } else {
 281                 prio = list_entry(stream->prio_list.next,
 282                                   struct sctp_stream_priorities, prio_sched);
 283                 soute = prio->next;
 284         }
 285         ch = list_entry(soute->outq.next, struct sctp_chunk, stream_list);
 286         sctp_sched_dequeue_common(q, ch);
 287
 288 out:
 289         return ch;
 290 }
 291
 292 static void sctp_sched_prio_dequeue_done(struct sctp_outq *q,
 293                                          struct sctp_chunk *ch)
 294 {
 295         struct sctp_stream_priorities *prio;
 296         struct sctp_stream_out_ext *soute;
 297         __u16 sid;
 298
 299         /* Last chunk on that msg, move to the next stream on
 300          * this priority.
 301          */
 302         sid = sctp_chunk_stream_no(ch);
 303         soute = SCTP_SO(&q->asoc->stream, sid)->ext;
 304         prio = soute->prio_head;
 305
 306         sctp_sched_prio_next_stream(prio);
 307
 308         if (list_empty(&soute->outq))
 309                 sctp_sched_prio_unsched(soute);
 310 }
 311
 312 static void sctp_sched_prio_sched_all(struct sctp_stream *stream)
 313 {
 314         struct sctp_association *asoc;
 315         struct sctp_stream_out *sout;
 316         struct sctp_chunk *ch;
 317
 318         asoc = container_of(stream, struct sctp_association, stream);
 319         list_for_each_entry(ch, &asoc->outqueue.out_chunk_list, list) {
 320                 __u16 sid;
 321
 322                 sid = sctp_chunk_stream_no(ch);
 323                 sout = SCTP_SO(stream, sid);
 324                 if (sout->ext)
 325                         sctp_sched_prio_sched(stream, sout->ext);
 326         }
 327 }
 328
 329 static void sctp_sched_prio_unsched_all(struct sctp_stream *stream)
 330 {
 331         struct sctp_stream_priorities *p, *tmp;
 332         struct sctp_stream_out_ext *soute, *souttmp;
 333
 334         list_for_each_entry_safe(p, tmp, &stream->prio_list, prio_sched)
 335                 list_for_each_entry_safe(soute, souttmp, &p->active, prio_list)
 336                         sctp_sched_prio_unsched(soute);
 337 }
 338
 339 static struct sctp_sched_ops sctp_sched_prio = {
 340         .set = sctp_sched_prio_set,
 341         .get = sctp_sched_prio_get,
 342         .init = sctp_sched_prio_init,
 343         .init_sid = sctp_sched_prio_init_sid,
 344         .free_sid = sctp_sched_prio_free_sid,
 345         .free = sctp_sched_prio_free,
 346         .enqueue = sctp_sched_prio_enqueue,
 347         .dequeue = sctp_sched_prio_dequeue,
 348         .dequeue_done = sctp_sched_prio_dequeue_done,
 349         .sched_all = sctp_sched_prio_sched_all,
 350         .unsched_all = sctp_sched_prio_unsched_all,
 351 };
 352
 353 void sctp_sched_ops_prio_init(void)
 354 {
 355         sctp_sched_ops_register(SCTP_SS_PRIO, &sctp_sched_prio);
 356 }