1 /* SPDX-License-Identifier: GPL-2.0-only */ 2 /* 3 * Copyright (c) 2016 Qualcomm Atheros, Inc 4 * 5 * Based on net/sched/sch_fq_codel.c 6 */ 7 #ifndef __NET_SCHED_FQ_IMPL_H 8 #define __NET_SCHED_FQ_IMPL_H 9 10 #include <net/fq.h> 11 12 /* functions that are embedded into includer */ 13 14 15 static void 16 __fq_adjust_removal(struct fq *fq, struct fq_flow *flow, unsigned int packets, 17 unsigned int bytes, unsigned int truesize) 18 { 19 struct fq_tin *tin = flow->tin; 20 21 tin->backlog_bytes -= bytes; 22 tin->backlog_packets -= packets; 23 flow->backlog -= bytes; 24 fq->backlog -= packets; 25 fq->memory_usage -= truesize; 26 } 27 28 static void fq_adjust_removal(struct fq *fq, 29 struct fq_flow *flow, 30 struct sk_buff *skb) 31 { 32 __fq_adjust_removal(fq, flow, 1, skb->len, skb->truesize); 33 } 34 35 static void fq_rejigger_backlog(struct fq *fq, struct fq_flow *flow) 36 { 37 struct fq_flow *i; 38 39 if (flow->backlog == 0) { 40 list_del_init(&flow->backlogchain); 41 } else { 42 i = flow; 43 44 list_for_each_entry_continue(i, &fq->backlogs, backlogchain) 45 if (i->backlog < flow->backlog) 46 break; 47 48 list_move_tail(&flow->backlogchain, 49 &i->backlogchain); 50 } 51 } 52 53 static struct sk_buff *fq_flow_dequeue(struct fq *fq, 54 struct fq_flow *flow) 55 { 56 struct sk_buff *skb; 57 58 lockdep_assert_held(&fq->lock); 59 60 skb = __skb_dequeue(&flow->queue); 61 if (!skb) 62 return NULL; 63 64 fq_adjust_removal(fq, flow, skb); 65 fq_rejigger_backlog(fq, flow); 66 67 return skb; 68 } 69 70 static int fq_flow_drop(struct fq *fq, struct fq_flow *flow, 71 fq_skb_free_t free_func) 72 { 73 unsigned int packets = 0, bytes = 0, truesize = 0; 74 struct fq_tin *tin = flow->tin; 75 struct sk_buff *skb; 76 int pending; 77 78 lockdep_assert_held(&fq->lock); 79 80 pending = min_t(int, 32, skb_queue_len(&flow->queue) / 2); 81 do { 82 skb = __skb_dequeue(&flow->queue); 83 if (!skb) 84 break; 85 86 packets++; 87 bytes += skb->len; 88 truesize += skb->truesize; 89 free_func(fq, tin, flow, skb); 90 } while (packets < pending); 91 92 __fq_adjust_removal(fq, flow, packets, bytes, truesize); 93 fq_rejigger_backlog(fq, flow); 94 95 return packets; 96 } 97 98 static struct sk_buff *fq_tin_dequeue(struct fq *fq, 99 struct fq_tin *tin, 100 fq_tin_dequeue_t dequeue_func) 101 { 102 struct fq_flow *flow; 103 struct list_head *head; 104 struct sk_buff *skb; 105 106 lockdep_assert_held(&fq->lock); 107 108 begin: 109 head = &tin->new_flows; 110 if (list_empty(head)) { 111 head = &tin->old_flows; 112 if (list_empty(head)) 113 return NULL; 114 } 115 116 flow = list_first_entry(head, struct fq_flow, flowchain); 117 118 if (flow->deficit <= 0) { 119 flow->deficit += fq->quantum; 120 list_move_tail(&flow->flowchain, 121 &tin->old_flows); 122 goto begin; 123 } 124 125 skb = dequeue_func(fq, tin, flow); 126 if (!skb) { 127 /* force a pass through old_flows to prevent starvation */ 128 if ((head == &tin->new_flows) && 129 !list_empty(&tin->old_flows)) { 130 list_move_tail(&flow->flowchain, &tin->old_flows); 131 } else { 132 list_del_init(&flow->flowchain); 133 flow->tin = NULL; 134 } 135 goto begin; 136 } 137 138 flow->deficit -= skb->len; 139 tin->tx_bytes += skb->len; 140 tin->tx_packets++; 141 142 return skb; 143 } 144 145 static u32 fq_flow_idx(struct fq *fq, struct sk_buff *skb) 146 { 147 u32 hash = skb_get_hash(skb); 148 149 return reciprocal_scale(hash, fq->flows_cnt); 150 } 151 152 static struct fq_flow *fq_flow_classify(struct fq *fq, 153 struct fq_tin *tin, u32 idx, 154 struct sk_buff *skb, 155 fq_flow_get_default_t get_default_func) 156 { 157 struct fq_flow *flow; 158 159 lockdep_assert_held(&fq->lock); 160 161 flow = &fq->flows[idx]; 162 if (flow->tin && flow->tin != tin) { 163 flow = get_default_func(fq, tin, idx, skb); 164 tin->collisions++; 165 fq->collisions++; 166 } 167 168 if (!flow->tin) 169 tin->flows++; 170 171 return flow; 172 } 173 174 static void fq_recalc_backlog(struct fq *fq, 175 struct fq_tin *tin, 176 struct fq_flow *flow) 177 { 178 struct fq_flow *i; 179 180 if (list_empty(&flow->backlogchain)) 181 list_add_tail(&flow->backlogchain, &fq->backlogs); 182 183 i = flow; 184 list_for_each_entry_continue_reverse(i, &fq->backlogs, 185 backlogchain) 186 if (i->backlog > flow->backlog) 187 break; 188 189 list_move(&flow->backlogchain, &i->backlogchain); 190 } 191 192 static void fq_tin_enqueue(struct fq *fq, 193 struct fq_tin *tin, u32 idx, 194 struct sk_buff *skb, 195 fq_skb_free_t free_func, 196 fq_flow_get_default_t get_default_func) 197 { 198 struct fq_flow *flow; 199 bool oom; 200 201 lockdep_assert_held(&fq->lock); 202 203 flow = fq_flow_classify(fq, tin, idx, skb, get_default_func); 204 205 flow->tin = tin; 206 flow->backlog += skb->len; 207 tin->backlog_bytes += skb->len; 208 tin->backlog_packets++; 209 fq->memory_usage += skb->truesize; 210 fq->backlog++; 211 212 fq_recalc_backlog(fq, tin, flow); 213 214 if (list_empty(&flow->flowchain)) { 215 flow->deficit = fq->quantum; 216 list_add_tail(&flow->flowchain, 217 &tin->new_flows); 218 } 219 220 __skb_queue_tail(&flow->queue, skb); 221 oom = (fq->memory_usage > fq->memory_limit); 222 while (fq->backlog > fq->limit || oom) { 223 flow = list_first_entry_or_null(&fq->backlogs, 224 struct fq_flow, 225 backlogchain); 226 if (!flow) 227 return; 228 229 if (!fq_flow_drop(fq, flow, free_func)) 230 return; 231 232 flow->tin->overlimit++; 233 fq->overlimit++; 234 if (oom) { 235 fq->overmemory++; 236 oom = (fq->memory_usage > fq->memory_limit); 237 } 238 } 239 } 240 241 static void fq_flow_filter(struct fq *fq, 242 struct fq_flow *flow, 243 fq_skb_filter_t filter_func, 244 void *filter_data, 245 fq_skb_free_t free_func) 246 { 247 struct fq_tin *tin = flow->tin; 248 struct sk_buff *skb, *tmp; 249 250 lockdep_assert_held(&fq->lock); 251 252 skb_queue_walk_safe(&flow->queue, skb, tmp) { 253 if (!filter_func(fq, tin, flow, skb, filter_data)) 254 continue; 255 256 __skb_unlink(skb, &flow->queue); 257 fq_adjust_removal(fq, flow, skb); 258 free_func(fq, tin, flow, skb); 259 } 260 261 fq_rejigger_backlog(fq, flow); 262 } 263 264 static void fq_tin_filter(struct fq *fq, 265 struct fq_tin *tin, 266 fq_skb_filter_t filter_func, 267 void *filter_data, 268 fq_skb_free_t free_func) 269 { 270 struct fq_flow *flow; 271 272 lockdep_assert_held(&fq->lock); 273 274 list_for_each_entry(flow, &tin->new_flows, flowchain) 275 fq_flow_filter(fq, flow, filter_func, filter_data, free_func); 276 list_for_each_entry(flow, &tin->old_flows, flowchain) 277 fq_flow_filter(fq, flow, filter_func, filter_data, free_func); 278 } 279 280 static void fq_flow_reset(struct fq *fq, 281 struct fq_flow *flow, 282 fq_skb_free_t free_func) 283 { 284 struct sk_buff *skb; 285 286 while ((skb = fq_flow_dequeue(fq, flow))) 287 free_func(fq, flow->tin, flow, skb); 288 289 if (!list_empty(&flow->flowchain)) 290 list_del_init(&flow->flowchain); 291 292 if (!list_empty(&flow->backlogchain)) 293 list_del_init(&flow->backlogchain); 294 295 flow->tin = NULL; 296 297 WARN_ON_ONCE(flow->backlog); 298 } 299 300 static void fq_tin_reset(struct fq *fq, 301 struct fq_tin *tin, 302 fq_skb_free_t free_func) 303 { 304 struct list_head *head; 305 struct fq_flow *flow; 306 307 for (;;) { 308 head = &tin->new_flows; 309 if (list_empty(head)) { 310 head = &tin->old_flows; 311 if (list_empty(head)) 312 break; 313 } 314 315 flow = list_first_entry(head, struct fq_flow, flowchain); 316 fq_flow_reset(fq, flow, free_func); 317 } 318 319 WARN_ON_ONCE(tin->backlog_bytes); 320 WARN_ON_ONCE(tin->backlog_packets); 321 } 322 323 static void fq_flow_init(struct fq_flow *flow) 324 { 325 INIT_LIST_HEAD(&flow->flowchain); 326 INIT_LIST_HEAD(&flow->backlogchain); 327 __skb_queue_head_init(&flow->queue); 328 } 329 330 static void fq_tin_init(struct fq_tin *tin) 331 { 332 INIT_LIST_HEAD(&tin->new_flows); 333 INIT_LIST_HEAD(&tin->old_flows); 334 } 335 336 static int fq_init(struct fq *fq, int flows_cnt) 337 { 338 int i; 339 340 memset(fq, 0, sizeof(fq[0])); 341 INIT_LIST_HEAD(&fq->backlogs); 342 spin_lock_init(&fq->lock); 343 fq->flows_cnt = max_t(u32, flows_cnt, 1); 344 fq->quantum = 300; 345 fq->limit = 8192; 346 fq->memory_limit = 16 << 20; /* 16 MBytes */ 347 348 fq->flows = kvcalloc(fq->flows_cnt, sizeof(fq->flows[0]), GFP_KERNEL); 349 if (!fq->flows) 350 return -ENOMEM; 351 352 for (i = 0; i < fq->flows_cnt; i++) 353 fq_flow_init(&fq->flows[i]); 354 355 return 0; 356 } 357 358 static void fq_reset(struct fq *fq, 359 fq_skb_free_t free_func) 360 { 361 int i; 362 363 for (i = 0; i < fq->flows_cnt; i++) 364 fq_flow_reset(fq, &fq->flows[i], free_func); 365 366 kvfree(fq->flows); 367 fq->flows = NULL; 368 } 369 370 #endif 371