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