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 } 338