altq_jobs.c revision 1.14
1 1.14 joe /* $NetBSD: altq_jobs.c,v 1.14 2025/01/08 13:00:04 joe Exp $ */ 2 1.2 peter /* $KAME: altq_jobs.c,v 1.11 2005/04/13 03:44:25 suz Exp $ */ 3 1.2 peter /* 4 1.2 peter * Copyright (c) 2001, the Rector and Board of Visitors of the 5 1.2 peter * University of Virginia. 6 1.2 peter * All rights reserved. 7 1.2 peter * 8 1.2 peter * Redistribution and use in source and binary forms, 9 1.2 peter * with or without modification, are permitted provided 10 1.2 peter * that the following conditions are met: 11 1.2 peter * 12 1.2 peter * Redistributions of source code must retain the above 13 1.2 peter * copyright notice, this list of conditions and the following 14 1.2 peter * disclaimer. 15 1.2 peter * 16 1.2 peter * Redistributions in binary form must reproduce the above 17 1.2 peter * copyright notice, this list of conditions and the following 18 1.2 peter * disclaimer in the documentation and/or other materials provided 19 1.2 peter * with the distribution. 20 1.2 peter * 21 1.2 peter * Neither the name of the University of Virginia nor the names 22 1.2 peter * of its contributors may be used to endorse or promote products 23 1.2 peter * derived from this software without specific prior written 24 1.2 peter * permission. 25 1.2 peter * 26 1.2 peter * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND 27 1.2 peter * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, 28 1.2 peter * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 29 1.2 peter * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 30 1.2 peter * DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE 31 1.2 peter * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, 32 1.2 peter * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 33 1.2 peter * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 34 1.2 peter * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 35 1.2 peter * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 36 1.2 peter * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING 37 1.2 peter * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 38 1.2 peter * THE POSSIBILITY OF SUCH DAMAGE. 39 1.2 peter */ 40 1.2 peter /* 41 1.2 peter * JoBS - altq prototype implementation 42 1.2 peter * 43 1.2 peter * Author: Nicolas Christin <nicolas (at) cs.virginia.edu> 44 1.2 peter * 45 1.2 peter * JoBS algorithms originally devised and proposed by 46 1.2 peter * Nicolas Christin and Jorg Liebeherr. 47 1.2 peter * Grateful acknowledgments to Tarek Abdelzaher for his help and 48 1.2 peter * comments, and to Kenjiro Cho for some helpful advice. 49 1.2 peter * Contributed by the Multimedia Networks Group at the University 50 1.2 peter * of Virginia. 51 1.2 peter * 52 1.2 peter * Papers and additional info can be found at 53 1.2 peter * http://qosbox.cs.virginia.edu 54 1.2 peter * 55 1.2 peter */ 56 1.2 peter 57 1.2 peter /* 58 1.2 peter * JoBS queue 59 1.2 peter */ 60 1.2 peter 61 1.2 peter #include <sys/cdefs.h> 62 1.14 joe __KERNEL_RCSID(0, "$NetBSD: altq_jobs.c,v 1.14 2025/01/08 13:00:04 joe Exp $"); 63 1.2 peter 64 1.2 peter #ifdef _KERNEL_OPT 65 1.2 peter #include "opt_altq.h" 66 1.2 peter #include "opt_inet.h" 67 1.2 peter #endif 68 1.2 peter 69 1.2 peter #ifdef ALTQ_JOBS /* jobs is enabled by ALTQ_JOBS option in opt_altq.h */ 70 1.2 peter 71 1.2 peter #include <sys/param.h> 72 1.2 peter #include <sys/malloc.h> 73 1.2 peter #include <sys/mbuf.h> 74 1.2 peter #include <sys/socket.h> 75 1.2 peter #include <sys/sockio.h> 76 1.2 peter #include <sys/systm.h> 77 1.2 peter #include <sys/proc.h> 78 1.2 peter #include <sys/errno.h> 79 1.2 peter #include <sys/kernel.h> 80 1.2 peter #include <sys/queue.h> 81 1.2 peter #include <sys/kauth.h> 82 1.2 peter 83 1.2 peter #ifdef __FreeBSD__ 84 1.2 peter #include <sys/limits.h> 85 1.2 peter #endif 86 1.2 peter 87 1.2 peter #include <net/if.h> 88 1.2 peter #include <net/if_types.h> 89 1.2 peter 90 1.2 peter #include <altq/altq.h> 91 1.2 peter #include <altq/altq_conf.h> 92 1.2 peter #include <altq/altq_jobs.h> 93 1.2 peter 94 1.2 peter #ifdef ALTQ3_COMPAT 95 1.2 peter /* 96 1.2 peter * function prototypes 97 1.2 peter */ 98 1.2 peter static struct jobs_if *jobs_attach(struct ifaltq *, u_int, u_int, u_int); 99 1.8 christos static void jobs_detach(struct jobs_if *); 100 1.2 peter static int jobs_clear_interface(struct jobs_if *); 101 1.2 peter static int jobs_request(struct ifaltq *, int, void *); 102 1.2 peter static void jobs_purge(struct jobs_if *); 103 1.2 peter static struct jobs_class *jobs_class_create(struct jobs_if *, 104 1.2 peter int, int64_t, int64_t, int64_t, int64_t, int64_t, int); 105 1.2 peter static int jobs_class_destroy(struct jobs_class *); 106 1.9 knakahar static int jobs_enqueue(struct ifaltq *, struct mbuf *); 107 1.2 peter static struct mbuf *jobs_dequeue(struct ifaltq *, int); 108 1.2 peter 109 1.2 peter static int jobs_addq(struct jobs_class *, struct mbuf *, struct jobs_if*); 110 1.2 peter static struct mbuf *jobs_getq(struct jobs_class *); 111 1.2 peter static struct mbuf *jobs_pollq(struct jobs_class *); 112 1.2 peter static void jobs_purgeq(struct jobs_class *); 113 1.2 peter 114 1.2 peter static int jobscmd_if_attach(struct jobs_attach *); 115 1.2 peter static int jobscmd_if_detach(struct jobs_interface *); 116 1.2 peter static int jobscmd_add_class(struct jobs_add_class *); 117 1.2 peter static int jobscmd_delete_class(struct jobs_delete_class *); 118 1.2 peter static int jobscmd_modify_class(struct jobs_modify_class *); 119 1.2 peter static int jobscmd_add_filter(struct jobs_add_filter *); 120 1.2 peter static int jobscmd_delete_filter(struct jobs_delete_filter *); 121 1.2 peter static int jobscmd_class_stats(struct jobs_class_stats *); 122 1.2 peter static void get_class_stats(struct class_stats *, struct jobs_class *); 123 1.2 peter static struct jobs_class *clh_to_clp(struct jobs_if *, u_long); 124 1.2 peter static u_long clp_to_clh(struct jobs_class *); 125 1.2 peter 126 1.2 peter static TSLIST *tslist_alloc(void); 127 1.2 peter static void tslist_destroy(struct jobs_class *); 128 1.2 peter static int tslist_enqueue(struct jobs_class *, u_int64_t); 129 1.2 peter static void tslist_dequeue(struct jobs_class *); 130 1.2 peter static void tslist_drop(struct jobs_class *); 131 1.2 peter 132 1.2 peter static int enforce_wc(struct jobs_if *); 133 1.2 peter static int64_t* adjust_rates_rdc(struct jobs_if *); 134 1.2 peter static int64_t* assign_rate_drops_adc(struct jobs_if *); 135 1.2 peter static int64_t* update_error(struct jobs_if *); 136 1.2 peter static int min_rates_adc(struct jobs_if *); 137 1.2 peter static int64_t proj_delay(struct jobs_if *, int); 138 1.2 peter static int pick_dropped_rlc(struct jobs_if *); 139 1.2 peter 140 1.2 peter altqdev_decl(jobs); 141 1.2 peter 142 1.2 peter /* jif_list keeps all jobs_if's allocated. */ 143 1.2 peter static struct jobs_if *jif_list = NULL; 144 1.2 peter 145 1.2 peter typedef unsigned long long ull; 146 1.2 peter 147 1.2 peter /* setup functions */ 148 1.2 peter 149 1.2 peter static struct jobs_if * 150 1.2 peter jobs_attach(struct ifaltq *ifq, u_int bandwidth, u_int qlimit, u_int separate) 151 1.2 peter { 152 1.2 peter struct jobs_if *jif; 153 1.2 peter 154 1.2 peter jif = malloc(sizeof(struct jobs_if), M_DEVBUF, M_WAITOK|M_ZERO); 155 1.2 peter if (jif == NULL) 156 1.14 joe return NULL; 157 1.2 peter 158 1.2 peter jif->jif_bandwidth = bandwidth; 159 1.2 peter jif->jif_qlimit = qlimit; 160 1.2 peter jif->jif_separate = separate; 161 1.2 peter #ifdef ALTQ_DEBUG 162 1.2 peter printf("JoBS bandwidth = %d bps\n", (int)bandwidth); 163 1.2 peter printf("JoBS buffer size = %d pkts [%s]\n", 164 1.2 peter (int)qlimit, separate?"separate buffers":"shared buffer"); 165 1.2 peter #endif 166 1.2 peter jif->jif_maxpri = -1; 167 1.2 peter jif->jif_ifq = ifq; 168 1.2 peter 169 1.2 peter jif->wc_cycles_enqueue = 0; 170 1.2 peter jif->avg_cycles_enqueue = 0; 171 1.2 peter jif->avg_cycles2_enqueue = 0; 172 1.6 plunky jif->bc_cycles_enqueue = ALTQ_INFINITY; 173 1.2 peter jif->wc_cycles_dequeue = 0; 174 1.2 peter jif->avg_cycles_dequeue = 0; 175 1.2 peter jif->avg_cycles2_dequeue = 0; 176 1.6 plunky jif->bc_cycles_dequeue = ALTQ_INFINITY; 177 1.2 peter jif->total_enqueued = 0; 178 1.2 peter jif->total_dequeued = 0; 179 1.2 peter 180 1.2 peter /* add this state to the jobs list */ 181 1.2 peter jif->jif_next = jif_list; 182 1.2 peter jif_list = jif; 183 1.2 peter 184 1.14 joe return jif; 185 1.2 peter } 186 1.2 peter 187 1.8 christos static void 188 1.2 peter jobs_detach(struct jobs_if *jif) 189 1.2 peter { 190 1.2 peter (void)jobs_clear_interface(jif); 191 1.2 peter 192 1.2 peter /* remove this interface from the jif list */ 193 1.2 peter if (jif_list == jif) 194 1.2 peter jif_list = jif->jif_next; 195 1.2 peter else { 196 1.2 peter struct jobs_if *p; 197 1.2 peter 198 1.2 peter for (p = jif_list; p != NULL; p = p->jif_next) 199 1.2 peter if (p->jif_next == jif) { 200 1.2 peter p->jif_next = jif->jif_next; 201 1.2 peter break; 202 1.2 peter } 203 1.2 peter ASSERT(p != NULL); 204 1.2 peter } 205 1.2 peter free(jif, M_DEVBUF); 206 1.2 peter } 207 1.2 peter 208 1.2 peter /* 209 1.2 peter * bring the interface back to the initial state by discarding 210 1.2 peter * all the filters and classes. 211 1.2 peter */ 212 1.2 peter static int 213 1.2 peter jobs_clear_interface(struct jobs_if *jif) 214 1.2 peter { 215 1.2 peter struct jobs_class *cl; 216 1.2 peter int pri; 217 1.2 peter 218 1.2 peter /* free the filters for this interface */ 219 1.2 peter acc_discard_filters(&jif->jif_classifier, NULL, 1); 220 1.2 peter 221 1.2 peter /* clear out the classes */ 222 1.2 peter for (pri = 0; pri <= jif->jif_maxpri; pri++) 223 1.2 peter if ((cl = jif->jif_classes[pri]) != NULL) 224 1.2 peter jobs_class_destroy(cl); 225 1.2 peter 226 1.14 joe return 0; 227 1.2 peter } 228 1.2 peter 229 1.2 peter static int 230 1.4 christos jobs_request(struct ifaltq *ifq, int req, void *arg) 231 1.2 peter { 232 1.2 peter struct jobs_if *jif = (struct jobs_if *)ifq->altq_disc; 233 1.2 peter 234 1.2 peter switch (req) { 235 1.2 peter case ALTRQ_PURGE: 236 1.2 peter jobs_purge(jif); 237 1.2 peter break; 238 1.2 peter } 239 1.14 joe return 0; 240 1.2 peter } 241 1.2 peter 242 1.2 peter /* discard all the queued packets on the interface */ 243 1.2 peter static void 244 1.2 peter jobs_purge(struct jobs_if *jif) 245 1.2 peter { 246 1.2 peter struct jobs_class *cl; 247 1.2 peter int pri; 248 1.2 peter 249 1.2 peter for (pri = 0; pri <= jif->jif_maxpri; pri++) { 250 1.2 peter if ((cl = jif->jif_classes[pri]) != NULL && !qempty(cl->cl_q)) 251 1.2 peter jobs_purgeq(cl); 252 1.2 peter } 253 1.2 peter if (ALTQ_IS_ENABLED(jif->jif_ifq)) 254 1.2 peter jif->jif_ifq->ifq_len = 0; 255 1.2 peter } 256 1.2 peter 257 1.2 peter static struct jobs_class * 258 1.2 peter jobs_class_create(struct jobs_if *jif, int pri, int64_t adc, int64_t rdc, 259 1.2 peter int64_t alc, int64_t rlc, int64_t arc, int flags) 260 1.2 peter { 261 1.2 peter struct jobs_class *cl, *scan1, *scan2; 262 1.2 peter int s; 263 1.2 peter int class_exists1, class_exists2; 264 1.2 peter int i, j; 265 1.2 peter int64_t tmp[JOBS_MAXPRI]; 266 1.2 peter u_int64_t now; 267 1.2 peter 268 1.2 peter if ((cl = jif->jif_classes[pri]) != NULL) { 269 1.2 peter /* modify the class instead of creating a new one */ 270 1.2 peter s = splnet(); 271 1.2 peter if (!qempty(cl->cl_q)) 272 1.2 peter jobs_purgeq(cl); 273 1.2 peter splx(s); 274 1.2 peter } else { 275 1.2 peter cl = malloc(sizeof(struct jobs_class), M_DEVBUF, 276 1.2 peter M_WAITOK|M_ZERO); 277 1.2 peter if (cl == NULL) 278 1.14 joe return NULL; 279 1.2 peter 280 1.2 peter cl->cl_q = malloc(sizeof(class_queue_t), M_DEVBUF, 281 1.2 peter M_WAITOK|M_ZERO); 282 1.2 peter if (cl->cl_q == NULL) 283 1.2 peter goto err_ret; 284 1.2 peter 285 1.2 peter cl->arv_tm = tslist_alloc(); 286 1.2 peter if (cl->arv_tm == NULL) 287 1.2 peter goto err_ret; 288 1.2 peter } 289 1.2 peter 290 1.2 peter jif->jif_classes[pri] = cl; 291 1.2 peter 292 1.2 peter if (flags & JOCF_DEFAULTCLASS) 293 1.2 peter jif->jif_default = cl; 294 1.2 peter 295 1.2 peter qtype(cl->cl_q) = Q_DROPTAIL; 296 1.2 peter qlen(cl->cl_q) = 0; 297 1.2 peter cl->service_rate = 0; 298 1.2 peter cl->min_rate_adc = 0; 299 1.2 peter cl->current_loss = 0; 300 1.2 peter cl->cl_period = 0; 301 1.2 peter PKTCNTR_RESET(&cl->cl_arrival); 302 1.2 peter PKTCNTR_RESET(&cl->cl_rin); 303 1.2 peter PKTCNTR_RESET(&cl->cl_rout); 304 1.2 peter PKTCNTR_RESET(&cl->cl_rout_th); 305 1.2 peter PKTCNTR_RESET(&cl->cl_dropcnt); 306 1.2 peter PKTCNTR_RESET(&cl->st_arrival); 307 1.2 peter PKTCNTR_RESET(&cl->st_rin); 308 1.2 peter PKTCNTR_RESET(&cl->st_rout); 309 1.2 peter PKTCNTR_RESET(&cl->st_dropcnt); 310 1.2 peter cl->st_service_rate = 0; 311 1.2 peter cl->cl_lastdel = 0; 312 1.2 peter cl->cl_avgdel = 0; 313 1.2 peter cl->adc_violations = 0; 314 1.2 peter 315 1.2 peter if (adc == -1) { 316 1.2 peter cl->concerned_adc = 0; 317 1.6 plunky adc = ALTQ_INFINITY; 318 1.2 peter } else 319 1.2 peter cl->concerned_adc = 1; 320 1.2 peter 321 1.2 peter if (alc == -1) { 322 1.2 peter cl->concerned_alc = 0; 323 1.6 plunky alc = ALTQ_INFINITY; 324 1.2 peter } else 325 1.2 peter cl->concerned_alc = 1; 326 1.2 peter 327 1.2 peter if (rdc == -1) { 328 1.2 peter rdc = 0; 329 1.2 peter cl->concerned_rdc = 0; 330 1.2 peter } else 331 1.2 peter cl->concerned_rdc = 1; 332 1.2 peter 333 1.2 peter if (rlc == -1) { 334 1.2 peter rlc = 0; 335 1.2 peter cl->concerned_rlc = 0; 336 1.2 peter } else 337 1.2 peter cl->concerned_rlc = 1; 338 1.2 peter 339 1.2 peter if (arc == -1) { 340 1.2 peter arc = 0; 341 1.2 peter cl->concerned_arc = 0; 342 1.2 peter } else 343 1.2 peter cl->concerned_arc = 1; 344 1.2 peter 345 1.2 peter cl->cl_rdc=rdc; 346 1.2 peter 347 1.2 peter if (cl->concerned_adc) { 348 1.2 peter /* adc is given in us, convert it to clock ticks */ 349 1.2 peter cl->cl_adc = (u_int64_t)(adc*machclk_freq/GRANULARITY); 350 1.2 peter } else 351 1.2 peter cl->cl_adc = adc; 352 1.2 peter 353 1.2 peter if (cl->concerned_arc) { 354 1.2 peter /* arc is given in bps, convert it to internal unit */ 355 1.2 peter cl->cl_arc = (u_int64_t)(bps_to_internal(arc)); 356 1.2 peter } else 357 1.2 peter cl->cl_arc = arc; 358 1.2 peter 359 1.2 peter cl->cl_rlc=rlc; 360 1.2 peter cl->cl_alc=alc; 361 1.2 peter cl->delay_prod_others = 0; 362 1.2 peter cl->loss_prod_others = 0; 363 1.2 peter cl->cl_flags = flags; 364 1.2 peter cl->cl_pri = pri; 365 1.2 peter if (pri > jif->jif_maxpri) 366 1.2 peter jif->jif_maxpri = pri; 367 1.2 peter cl->cl_jif = jif; 368 1.2 peter cl->cl_handle = (u_long)cl; /* just a pointer to this class */ 369 1.2 peter 370 1.2 peter /* 371 1.2 peter * update delay_prod_others and loss_prod_others 372 1.2 peter * in all classes if needed 373 1.2 peter */ 374 1.2 peter 375 1.2 peter if (cl->concerned_rdc) { 376 1.2 peter for (i = 0; i <= jif->jif_maxpri; i++) { 377 1.2 peter scan1 = jif->jif_classes[i]; 378 1.2 peter class_exists1 = (scan1 != NULL); 379 1.2 peter if (class_exists1) { 380 1.2 peter tmp[i] = 1; 381 1.2 peter for (j = 0; j <= i-1; j++) { 382 1.2 peter scan2 = jif->jif_classes[j]; 383 1.2 peter class_exists2 = (scan2 != NULL); 384 1.2 peter if (class_exists2 385 1.2 peter && scan2->concerned_rdc) 386 1.2 peter tmp[i] *= scan2->cl_rdc; 387 1.2 peter } 388 1.2 peter } else 389 1.2 peter tmp[i] = 0; 390 1.2 peter } 391 1.2 peter 392 1.2 peter for (i = 0; i <= jif->jif_maxpri; i++) { 393 1.2 peter scan1 = jif->jif_classes[i]; 394 1.2 peter class_exists1 = (scan1 != NULL); 395 1.2 peter if (class_exists1) { 396 1.2 peter scan1->delay_prod_others = 1; 397 1.2 peter for (j = 0; j <= jif->jif_maxpri; j++) { 398 1.2 peter scan2 = jif->jif_classes[j]; 399 1.2 peter class_exists2 = (scan2 != NULL); 400 1.2 peter if (class_exists2 && j != i 401 1.2 peter && scan2->concerned_rdc) 402 1.2 peter scan1->delay_prod_others *= tmp[j]; 403 1.2 peter } 404 1.2 peter } 405 1.2 peter } 406 1.2 peter } 407 1.2 peter 408 1.2 peter if (cl->concerned_rlc) { 409 1.2 peter for (i = 0; i <= jif->jif_maxpri; i++) { 410 1.2 peter scan1 = jif->jif_classes[i]; 411 1.2 peter class_exists1 = (scan1 != NULL); 412 1.2 peter if (class_exists1) { 413 1.2 peter tmp[i] = 1; 414 1.2 peter for (j = 0; j <= i-1; j++) { 415 1.2 peter scan2 = jif->jif_classes[j]; 416 1.2 peter class_exists2 = (scan2 != NULL); 417 1.2 peter if (class_exists2 418 1.2 peter && scan2->concerned_rlc) 419 1.2 peter tmp[i] *= scan2->cl_rlc; 420 1.2 peter } 421 1.2 peter } else 422 1.2 peter tmp[i] = 0; 423 1.2 peter } 424 1.2 peter 425 1.2 peter for (i = 0; i <= jif->jif_maxpri; i++) { 426 1.2 peter scan1 = jif->jif_classes[i]; 427 1.2 peter class_exists1 = (scan1 != NULL); 428 1.2 peter if (class_exists1) { 429 1.2 peter scan1->loss_prod_others = 1; 430 1.2 peter for (j = 0; j <= jif->jif_maxpri; j++) { 431 1.2 peter scan2 = jif->jif_classes[j]; 432 1.2 peter class_exists2 = (scan2 != NULL); 433 1.2 peter if (class_exists2 && j != i 434 1.2 peter && scan2->concerned_rlc) 435 1.2 peter scan1->loss_prod_others *= tmp[j]; 436 1.2 peter } 437 1.2 peter } 438 1.2 peter } 439 1.2 peter } 440 1.2 peter 441 1.2 peter now = read_machclk(); 442 1.2 peter cl->idletime = now; 443 1.14 joe return cl; 444 1.2 peter 445 1.2 peter err_ret: 446 1.2 peter if (cl->cl_q != NULL) 447 1.2 peter free(cl->cl_q, M_DEVBUF); 448 1.2 peter if (cl->arv_tm != NULL) 449 1.2 peter free(cl->arv_tm, M_DEVBUF); 450 1.2 peter 451 1.2 peter free(cl, M_DEVBUF); 452 1.14 joe return NULL; 453 1.2 peter } 454 1.2 peter 455 1.2 peter static int 456 1.2 peter jobs_class_destroy(struct jobs_class *cl) 457 1.2 peter { 458 1.2 peter struct jobs_if *jif; 459 1.2 peter int s, pri; 460 1.2 peter 461 1.2 peter s = splnet(); 462 1.2 peter 463 1.2 peter /* delete filters referencing to this class */ 464 1.2 peter acc_discard_filters(&cl->cl_jif->jif_classifier, cl, 0); 465 1.2 peter 466 1.2 peter if (!qempty(cl->cl_q)) 467 1.2 peter jobs_purgeq(cl); 468 1.2 peter 469 1.2 peter jif = cl->cl_jif; 470 1.2 peter jif->jif_classes[cl->cl_pri] = NULL; 471 1.2 peter if (jif->jif_maxpri == cl->cl_pri) { 472 1.2 peter for (pri = cl->cl_pri; pri >= 0; pri--) 473 1.2 peter if (jif->jif_classes[pri] != NULL) { 474 1.2 peter jif->jif_maxpri = pri; 475 1.2 peter break; 476 1.2 peter } 477 1.2 peter if (pri < 0) 478 1.2 peter jif->jif_maxpri = -1; 479 1.2 peter } 480 1.2 peter splx(s); 481 1.2 peter 482 1.2 peter tslist_destroy(cl); 483 1.2 peter free(cl->cl_q, M_DEVBUF); 484 1.2 peter free(cl, M_DEVBUF); 485 1.14 joe return 0; 486 1.2 peter } 487 1.2 peter 488 1.2 peter /* 489 1.2 peter * jobs_enqueue is an enqueue function to be registered to 490 1.2 peter * (*altq_enqueue) in struct ifaltq. 491 1.2 peter */ 492 1.2 peter static int 493 1.9 knakahar jobs_enqueue(struct ifaltq *ifq, struct mbuf *m) 494 1.2 peter { 495 1.2 peter struct jobs_if *jif = (struct jobs_if *)ifq->altq_disc; 496 1.2 peter struct jobs_class *cl, *scan; 497 1.2 peter int len; 498 1.2 peter int return_flag; 499 1.2 peter int pri; 500 1.2 peter u_int64_t now; 501 1.2 peter u_int64_t old_arv; 502 1.2 peter int64_t* delta_rate; 503 1.2 peter u_int64_t tstamp1, tstamp2, cycles; /* used for benchmarking only */ 504 1.2 peter 505 1.2 peter jif->total_enqueued++; 506 1.2 peter now = read_machclk(); 507 1.2 peter tstamp1 = now; 508 1.2 peter 509 1.2 peter return_flag = 0; 510 1.2 peter 511 1.2 peter /* proceed with packet enqueuing */ 512 1.2 peter 513 1.2 peter if (IFQ_IS_EMPTY(ifq)) { 514 1.2 peter for (pri=0; pri <= jif->jif_maxpri; pri++) { 515 1.2 peter scan = jif->jif_classes[pri]; 516 1.2 peter if (scan != NULL) { 517 1.2 peter /* 518 1.2 peter * reset all quantities, except: 519 1.2 peter * average delay, number of violations 520 1.2 peter */ 521 1.2 peter PKTCNTR_RESET(&scan->cl_rin); 522 1.2 peter PKTCNTR_RESET(&scan->cl_rout); 523 1.2 peter PKTCNTR_RESET(&scan->cl_rout_th); 524 1.2 peter PKTCNTR_RESET(&scan->cl_arrival); 525 1.2 peter PKTCNTR_RESET(&scan->cl_dropcnt); 526 1.2 peter scan->cl_lastdel = 0; 527 1.2 peter scan->current_loss = 0; 528 1.2 peter scan->service_rate = 0; 529 1.2 peter scan->idletime = now; 530 1.2 peter scan->cl_last_rate_update = now; 531 1.2 peter } 532 1.2 peter } 533 1.2 peter } 534 1.2 peter 535 1.2 peter /* grab class set by classifier */ 536 1.9 knakahar if ((cl = m->m_pkthdr.pattr_class) == NULL) 537 1.2 peter cl = jif->jif_default; 538 1.2 peter 539 1.2 peter len = m_pktlen(m); 540 1.2 peter old_arv = cl->cl_arrival.bytes; 541 1.2 peter PKTCNTR_ADD(&cl->cl_arrival, (int)len); 542 1.2 peter PKTCNTR_ADD(&cl->cl_rin, (int)len); 543 1.2 peter PKTCNTR_ADD(&cl->st_arrival, (int)len); 544 1.2 peter PKTCNTR_ADD(&cl->st_rin, (int)len); 545 1.2 peter 546 1.2 peter if (cl->cl_arrival.bytes < old_arv) { 547 1.2 peter /* deals w/ overflow */ 548 1.2 peter for (pri=0; pri <= jif->jif_maxpri; pri++) { 549 1.2 peter scan = jif->jif_classes[pri]; 550 1.2 peter if (scan != NULL) { 551 1.2 peter /* 552 1.2 peter * reset all quantities, except: 553 1.2 peter * average delay, number of violations 554 1.2 peter */ 555 1.2 peter PKTCNTR_RESET(&scan->cl_rin); 556 1.2 peter PKTCNTR_RESET(&scan->cl_rout); 557 1.2 peter PKTCNTR_RESET(&scan->cl_rout_th); 558 1.2 peter PKTCNTR_RESET(&scan->cl_arrival); 559 1.2 peter PKTCNTR_RESET(&scan->cl_dropcnt); 560 1.2 peter scan->current_loss = 0; 561 1.2 peter scan->service_rate = 0; 562 1.2 peter scan->idletime = now; 563 1.2 peter scan->cl_last_rate_update = now; 564 1.2 peter } 565 1.2 peter } 566 1.2 peter PKTCNTR_ADD(&cl->cl_arrival, (int)len); 567 1.2 peter PKTCNTR_ADD(&cl->cl_rin, (int)len); 568 1.2 peter } 569 1.2 peter 570 1.2 peter if (cl->cl_arrival.bytes > cl->cl_rin.bytes) 571 1.2 peter cl->current_loss = 572 1.2 peter ((cl->cl_arrival.bytes - cl->cl_rin.bytes) << SCALE_LOSS) 573 1.2 peter / cl->cl_arrival.bytes; 574 1.2 peter else 575 1.2 peter cl->current_loss = 0; 576 1.2 peter 577 1.2 peter /* for MDRR: update theoretical value of the output curve */ 578 1.2 peter 579 1.2 peter for (pri=0; pri <= jif->jif_maxpri; pri++) { 580 1.2 peter scan = jif->jif_classes[pri]; 581 1.2 peter if (scan != NULL) { 582 1.2 peter if (scan->cl_last_rate_update == scan->idletime 583 1.2 peter || scan->cl_last_rate_update == 0) 584 1.2 peter scan->cl_last_rate_update = now; /* initial case */ 585 1.2 peter else 586 1.2 peter scan->cl_rout_th.bytes += 587 1.2 peter delay_diff(now, scan->cl_last_rate_update) 588 1.2 peter * scan->service_rate; 589 1.2 peter 590 1.2 peter /* 591 1.2 peter * we don't really care about packets here 592 1.2 peter * WARNING: rout_th is SCALED 593 1.2 peter * (b/c of the service rate) 594 1.2 peter * for precision, as opposed to rout. 595 1.2 peter */ 596 1.2 peter 597 1.2 peter scan->cl_last_rate_update = now; 598 1.2 peter } 599 1.2 peter } 600 1.2 peter 601 1.2 peter if (jobs_addq(cl, m, jif) != 0) 602 1.2 peter return_flag = ENOBUFS; /* signals there's a buffer overflow */ 603 1.2 peter else 604 1.2 peter IFQ_INC_LEN(ifq); 605 1.2 peter 606 1.2 peter /* successfully queued. */ 607 1.2 peter 608 1.2 peter enforce_wc(jif); 609 1.2 peter 610 1.2 peter if (!min_rates_adc(jif)) { 611 1.2 peter delta_rate = assign_rate_drops_adc(jif); 612 1.2 peter if (delta_rate != NULL) { 613 1.2 peter for (pri = 0; pri <= jif->jif_maxpri; pri++) 614 1.2 peter if ((cl = jif->jif_classes[pri]) != NULL && 615 1.2 peter !qempty(cl->cl_q)) 616 1.2 peter cl->service_rate += delta_rate[pri]; 617 1.2 peter free(delta_rate, M_DEVBUF); 618 1.2 peter } 619 1.2 peter } 620 1.2 peter 621 1.2 peter delta_rate = adjust_rates_rdc(jif); 622 1.2 peter 623 1.2 peter if (delta_rate != NULL) { 624 1.2 peter for (pri = 0; pri <= jif->jif_maxpri; pri++) 625 1.2 peter if ((cl = jif->jif_classes[pri]) != NULL && 626 1.2 peter !qempty(cl->cl_q)) 627 1.2 peter cl->service_rate += delta_rate[pri]; 628 1.2 peter free(delta_rate, M_DEVBUF); 629 1.2 peter } 630 1.2 peter 631 1.2 peter tstamp2 = read_machclk(); 632 1.2 peter cycles = delay_diff(tstamp2, tstamp1); 633 1.2 peter if (cycles > jif->wc_cycles_enqueue) 634 1.2 peter jif->wc_cycles_enqueue=cycles; 635 1.2 peter if (cycles < jif->bc_cycles_enqueue) 636 1.2 peter jif->bc_cycles_enqueue=cycles; 637 1.2 peter 638 1.2 peter jif->avg_cycles_enqueue += cycles; 639 1.2 peter jif->avg_cycles2_enqueue += cycles * cycles; 640 1.2 peter 641 1.14 joe return return_flag; 642 1.2 peter } 643 1.2 peter 644 1.2 peter /* 645 1.2 peter * jobs_dequeue is a dequeue function to be registered to 646 1.2 peter * (*altq_dequeue) in struct ifaltq. 647 1.2 peter * 648 1.2 peter * note: ALTDQ_POLL returns the next packet without removing the packet 649 1.2 peter * from the queue. ALTDQ_REMOVE is a normal dequeue operation. 650 1.2 peter * ALTDQ_REMOVE must return the same packet if called immediately 651 1.2 peter * after ALTDQ_POLL. 652 1.2 peter */ 653 1.2 peter 654 1.2 peter static struct mbuf * 655 1.2 peter jobs_dequeue(struct ifaltq *ifq, int op) 656 1.2 peter { 657 1.2 peter struct jobs_if *jif = (struct jobs_if *)ifq->altq_disc; 658 1.2 peter struct jobs_class *cl; 659 1.2 peter struct mbuf *m; 660 1.2 peter int pri; 661 1.2 peter int svc_class; 662 1.2 peter int64_t max_error; 663 1.2 peter int64_t error; 664 1.2 peter u_int64_t now; 665 1.2 peter u_int64_t tstamp1, tstamp2, cycles; 666 1.2 peter 667 1.2 peter jif->total_dequeued++; 668 1.2 peter 669 1.2 peter now = read_machclk(); 670 1.2 peter tstamp1 = now; 671 1.2 peter 672 1.2 peter if (IFQ_IS_EMPTY(ifq)) { 673 1.2 peter /* no packet in the queue */ 674 1.2 peter for (pri=0; pri <= jif->jif_maxpri; pri++) { 675 1.2 peter cl = jif->jif_classes[pri]; 676 1.2 peter if (cl != NULL) 677 1.2 peter cl->idletime = now; 678 1.2 peter } 679 1.2 peter 680 1.2 peter tstamp2 = read_machclk(); 681 1.2 peter cycles = delay_diff(tstamp2, tstamp1); 682 1.2 peter if (cycles > jif->wc_cycles_dequeue) 683 1.2 peter jif->wc_cycles_dequeue = cycles; 684 1.2 peter if (cycles < jif->bc_cycles_dequeue) 685 1.2 peter jif->bc_cycles_dequeue = cycles; 686 1.2 peter 687 1.2 peter jif->avg_cycles_dequeue += cycles; 688 1.2 peter jif->avg_cycles2_dequeue += cycles * cycles; 689 1.2 peter 690 1.14 joe return NULL; 691 1.2 peter } 692 1.2 peter 693 1.2 peter /* 694 1.2 peter * select the class whose actual tranmissions are the furthest 695 1.2 peter * from the promised transmissions 696 1.2 peter */ 697 1.2 peter 698 1.2 peter max_error = -1; 699 1.2 peter svc_class = -1; 700 1.2 peter 701 1.2 peter for (pri=0; pri <= jif->jif_maxpri; pri++) { 702 1.2 peter if (((cl = jif->jif_classes[pri]) != NULL) 703 1.2 peter && !qempty(cl->cl_q)) { 704 1.2 peter error = (int64_t)cl->cl_rout_th.bytes 705 1.2 peter -(int64_t)scale_rate(cl->cl_rout.bytes); 706 1.2 peter if (max_error == -1) { 707 1.2 peter max_error = error; 708 1.2 peter svc_class = pri; 709 1.2 peter } else if (error > max_error) { 710 1.2 peter max_error = error; 711 1.2 peter svc_class = pri; 712 1.2 peter } 713 1.2 peter } 714 1.2 peter } 715 1.2 peter 716 1.2 peter if (svc_class != -1) 717 1.2 peter cl = jif->jif_classes[svc_class]; 718 1.2 peter else 719 1.2 peter cl = NULL; 720 1.2 peter 721 1.2 peter if (op == ALTDQ_POLL) { 722 1.2 peter tstamp2 = read_machclk(); 723 1.2 peter cycles = delay_diff(tstamp2, tstamp1); 724 1.2 peter if (cycles > jif->wc_cycles_dequeue) 725 1.2 peter jif->wc_cycles_dequeue = cycles; 726 1.2 peter if (cycles < jif->bc_cycles_dequeue) 727 1.2 peter jif->bc_cycles_dequeue = cycles; 728 1.2 peter 729 1.2 peter jif->avg_cycles_dequeue += cycles; 730 1.2 peter jif->avg_cycles2_dequeue += cycles * cycles; 731 1.2 peter 732 1.2 peter return (jobs_pollq(cl)); 733 1.2 peter } 734 1.2 peter 735 1.2 peter if (cl != NULL) 736 1.2 peter m = jobs_getq(cl); 737 1.2 peter else 738 1.2 peter m = NULL; 739 1.2 peter 740 1.2 peter if (m != NULL) { 741 1.2 peter IFQ_DEC_LEN(ifq); 742 1.2 peter if (qempty(cl->cl_q)) 743 1.2 peter cl->cl_period++; 744 1.2 peter 745 1.2 peter cl->cl_lastdel = (u_int64_t)delay_diff(now, 746 1.2 peter tslist_first(cl->arv_tm)->timestamp); 747 1.2 peter if (cl->concerned_adc 748 1.2 peter && (int64_t)cl->cl_lastdel > cl->cl_adc) 749 1.2 peter cl->adc_violations++; 750 1.2 peter cl->cl_avgdel += ticks_to_secs(GRANULARITY*cl->cl_lastdel); 751 1.2 peter 752 1.2 peter PKTCNTR_ADD(&cl->cl_rout, m_pktlen(m)); 753 1.2 peter PKTCNTR_ADD(&cl->st_rout, m_pktlen(m)); 754 1.2 peter } 755 1.2 peter if (cl != NULL) 756 1.2 peter tslist_dequeue(cl); /* dequeue the timestamp */ 757 1.2 peter 758 1.2 peter tstamp2 = read_machclk(); 759 1.2 peter cycles = delay_diff(tstamp2, tstamp1); 760 1.2 peter if (cycles > jif->wc_cycles_dequeue) 761 1.2 peter jif->wc_cycles_dequeue = cycles; 762 1.2 peter if (cycles < jif->bc_cycles_dequeue) 763 1.2 peter jif->bc_cycles_dequeue = cycles; 764 1.2 peter 765 1.2 peter jif->avg_cycles_dequeue += cycles; 766 1.2 peter jif->avg_cycles2_dequeue += cycles * cycles; 767 1.2 peter 768 1.14 joe return m; 769 1.2 peter } 770 1.2 peter 771 1.2 peter static int 772 1.2 peter jobs_addq(struct jobs_class *cl, struct mbuf *m, struct jobs_if *jif) 773 1.2 peter { 774 1.2 peter int victim; 775 1.2 peter u_int64_t len; 776 1.2 peter u_int64_t now; 777 1.2 peter struct jobs_class* victim_class; 778 1.2 peter 779 1.2 peter victim = -1; 780 1.2 peter victim_class = NULL; 781 1.2 peter len = 0; 782 1.2 peter 783 1.2 peter now = read_machclk(); 784 1.2 peter 785 1.2 peter if (jif->jif_separate && qlen(cl->cl_q) >= jif->jif_qlimit) { 786 1.2 peter /* 787 1.2 peter * separate buffers: no guarantees on packet drops 788 1.2 peter * can be offered 789 1.2 peter * thus we drop the incoming packet 790 1.2 peter */ 791 1.2 peter len = (u_int64_t)m_pktlen(m); 792 1.2 peter PKTCNTR_ADD(&cl->cl_dropcnt, (int)len); 793 1.2 peter PKTCNTR_SUB(&cl->cl_rin, (int)len); 794 1.2 peter PKTCNTR_ADD(&cl->st_dropcnt, (int)len); 795 1.2 peter PKTCNTR_SUB(&cl->st_rin, (int)len); 796 1.2 peter cl->current_loss += (len << SCALE_LOSS) 797 1.2 peter /cl->cl_arrival.bytes; 798 1.2 peter m_freem(m); 799 1.2 peter return (-1); 800 1.2 peter 801 1.2 peter } else if (!jif->jif_separate 802 1.2 peter && jif->jif_ifq->ifq_len >= jif->jif_qlimit) { 803 1.2 peter /* shared buffer: supports guarantees on losses */ 804 1.2 peter if (!cl->concerned_rlc) { 805 1.2 peter if (!cl->concerned_alc) { 806 1.2 peter /* 807 1.2 peter * no ALC, no RLC on this class: 808 1.2 peter * drop the incoming packet 809 1.2 peter */ 810 1.2 peter len = (u_int64_t)m_pktlen(m); 811 1.2 peter PKTCNTR_ADD(&cl->cl_dropcnt, (int)len); 812 1.2 peter PKTCNTR_SUB(&cl->cl_rin, (int)len); 813 1.2 peter PKTCNTR_ADD(&cl->st_dropcnt, (int)len); 814 1.2 peter PKTCNTR_SUB(&cl->st_rin, (int)len); 815 1.2 peter cl->current_loss += (len << SCALE_LOSS)/cl->cl_arrival.bytes; 816 1.2 peter m_freem(m); 817 1.2 peter return (-1); 818 1.2 peter } else { 819 1.2 peter /* 820 1.2 peter * no RLC, but an ALC: 821 1.2 peter * drop the incoming packet if possible 822 1.2 peter */ 823 1.2 peter len = (u_int64_t)m_pktlen(m); 824 1.2 peter if (cl->current_loss + (len << SCALE_LOSS) 825 1.2 peter / cl->cl_arrival.bytes <= cl->cl_alc) { 826 1.2 peter PKTCNTR_ADD(&cl->cl_dropcnt, (int)len); 827 1.2 peter PKTCNTR_SUB(&cl->cl_rin, (int)len); 828 1.2 peter PKTCNTR_ADD(&cl->st_dropcnt, (int)len); 829 1.2 peter PKTCNTR_SUB(&cl->st_rin, (int)len); 830 1.2 peter cl->current_loss += (len << SCALE_LOSS)/cl->cl_arrival.bytes; 831 1.2 peter m_freem(m); 832 1.2 peter return (-1); 833 1.2 peter } else { 834 1.2 peter /* 835 1.2 peter * the ALC would be violated: 836 1.2 peter * pick another class 837 1.2 peter */ 838 1.2 peter _addq(cl->cl_q, m); 839 1.2 peter tslist_enqueue(cl, now); 840 1.2 peter 841 1.2 peter victim = pick_dropped_rlc(jif); 842 1.2 peter 843 1.2 peter if (victim == -1) { 844 1.2 peter /* 845 1.2 peter * something went wrong 846 1.2 peter * let us discard 847 1.2 peter * the incoming packet, 848 1.2 peter * regardless of what 849 1.2 peter * may happen... 850 1.2 peter */ 851 1.2 peter victim_class = cl; 852 1.2 peter } else 853 1.2 peter victim_class = jif->jif_classes[victim]; 854 1.2 peter 855 1.2 peter if (victim_class != NULL) { 856 1.2 peter /* 857 1.2 peter * test for safety 858 1.2 peter * purposes... 859 1.2 peter * it must be true 860 1.2 peter */ 861 1.2 peter m = _getq_tail(victim_class->cl_q); 862 1.2 peter len = (u_int64_t)m_pktlen(m); 863 1.2 peter PKTCNTR_ADD(&victim_class->cl_dropcnt, (int)len); 864 1.2 peter PKTCNTR_SUB(&victim_class->cl_rin, (int)len); 865 1.2 peter PKTCNTR_ADD(&victim_class->st_dropcnt, (int)len); 866 1.2 peter PKTCNTR_SUB(&victim_class->st_rin, (int)len); 867 1.2 peter victim_class->current_loss += (len << SCALE_LOSS)/victim_class->cl_arrival.bytes; 868 1.2 peter m_freem(m); /* the packet is trashed here */ 869 1.2 peter tslist_drop(victim_class); /* and its timestamp as well */ 870 1.2 peter } 871 1.2 peter return (-1); 872 1.2 peter } 873 1.2 peter } 874 1.2 peter } else { 875 1.2 peter /* 876 1.2 peter * RLC on that class: 877 1.2 peter * pick class according to RLCs 878 1.2 peter */ 879 1.2 peter _addq(cl->cl_q, m); 880 1.2 peter tslist_enqueue(cl, now); 881 1.2 peter 882 1.2 peter victim = pick_dropped_rlc(jif); 883 1.2 peter if (victim == -1) { 884 1.2 peter /* 885 1.2 peter * something went wrong 886 1.2 peter * let us discard the incoming packet, 887 1.2 peter * regardless of what may happen... 888 1.2 peter */ 889 1.2 peter victim_class = cl; 890 1.2 peter } else 891 1.2 peter victim_class = jif->jif_classes[victim]; 892 1.2 peter 893 1.2 peter if (victim_class != NULL) { 894 1.2 peter /* 895 1.2 peter * test for safety purposes... 896 1.2 peter * it must be true 897 1.2 peter */ 898 1.2 peter m = _getq_tail(victim_class->cl_q); 899 1.2 peter len = (u_int64_t)m_pktlen(m); 900 1.2 peter PKTCNTR_ADD(&victim_class->cl_dropcnt, (int)len); 901 1.2 peter PKTCNTR_SUB(&victim_class->cl_rin, (int)len); 902 1.2 peter PKTCNTR_ADD(&victim_class->st_dropcnt, (int)len); 903 1.2 peter PKTCNTR_SUB(&victim_class->st_rin, (int)len); 904 1.2 peter victim_class->current_loss += (len << SCALE_LOSS)/victim_class->cl_arrival.bytes; 905 1.2 peter m_freem(m); /* the packet is trashed here */ 906 1.2 peter tslist_drop(victim_class); /* and its timestamp as well */ 907 1.2 peter } 908 1.14 joe return -1; 909 1.2 peter } 910 1.2 peter } 911 1.2 peter /* else: no drop */ 912 1.2 peter 913 1.2 peter _addq(cl->cl_q, m); 914 1.2 peter tslist_enqueue(cl, now); 915 1.2 peter 916 1.14 joe return 0; 917 1.2 peter } 918 1.2 peter 919 1.2 peter static struct mbuf * 920 1.2 peter jobs_getq(struct jobs_class *cl) 921 1.2 peter { 922 1.2 peter return _getq(cl->cl_q); 923 1.2 peter } 924 1.2 peter 925 1.2 peter static struct mbuf * 926 1.2 peter jobs_pollq(struct jobs_class *cl) 927 1.2 peter { 928 1.2 peter return qhead(cl->cl_q); 929 1.2 peter } 930 1.2 peter 931 1.2 peter static void 932 1.2 peter jobs_purgeq(struct jobs_class *cl) 933 1.2 peter { 934 1.2 peter struct mbuf *m; 935 1.2 peter 936 1.2 peter if (qempty(cl->cl_q)) 937 1.2 peter return; 938 1.2 peter 939 1.2 peter while ((m = _getq(cl->cl_q)) != NULL) { 940 1.2 peter PKTCNTR_ADD(&cl->cl_dropcnt, m_pktlen(m)); 941 1.2 peter PKTCNTR_ADD(&cl->st_dropcnt, m_pktlen(m)); 942 1.2 peter m_freem(m); 943 1.2 peter tslist_drop(cl); 944 1.2 peter } 945 1.2 peter ASSERT(qlen(cl->cl_q) == 0); 946 1.2 peter } 947 1.2 peter 948 1.2 peter /* 949 1.2 peter * timestamp list support routines 950 1.2 peter * 951 1.2 peter * this implementation has been revamped and 952 1.2 peter * now uses a TAILQ structure. 953 1.2 peter * timestamp list holds class timestamps 954 1.2 peter * there is one timestamp list per class. 955 1.2 peter */ 956 1.2 peter static TSLIST * 957 1.2 peter tslist_alloc(void) 958 1.2 peter { 959 1.2 peter TSLIST *list_init; 960 1.2 peter 961 1.2 peter list_init = malloc(sizeof(TSLIST), M_DEVBUF, M_WAITOK); 962 1.2 peter TAILQ_INIT(list_init); 963 1.14 joe return list_init; 964 1.2 peter } 965 1.2 peter 966 1.2 peter static void 967 1.2 peter tslist_destroy(struct jobs_class *cl) 968 1.2 peter { 969 1.2 peter while (tslist_first(cl->arv_tm) != NULL) 970 1.2 peter tslist_dequeue(cl); 971 1.2 peter 972 1.2 peter free(cl->arv_tm, M_DEVBUF); 973 1.2 peter } 974 1.2 peter 975 1.2 peter static int 976 1.2 peter tslist_enqueue(struct jobs_class *cl, u_int64_t arv) 977 1.2 peter { 978 1.2 peter TSENTRY *pushed; 979 1.2 peter pushed = malloc(sizeof(TSENTRY), M_DEVBUF, M_WAITOK); 980 1.2 peter if (pushed == NULL) 981 1.14 joe return 0; 982 1.2 peter 983 1.2 peter pushed->timestamp = arv; 984 1.2 peter TAILQ_INSERT_TAIL(cl->arv_tm, pushed, ts_list); 985 1.14 joe return 1; 986 1.2 peter } 987 1.2 peter 988 1.2 peter static void 989 1.2 peter tslist_dequeue(struct jobs_class *cl) 990 1.2 peter { 991 1.2 peter TSENTRY *popped; 992 1.2 peter popped = tslist_first(cl->arv_tm); 993 1.2 peter if (popped != NULL) { 994 1.2 peter TAILQ_REMOVE(cl->arv_tm, popped, ts_list); 995 1.2 peter free(popped, M_DEVBUF); 996 1.2 peter } 997 1.2 peter return; 998 1.2 peter } 999 1.2 peter 1000 1.2 peter static void 1001 1.2 peter tslist_drop(struct jobs_class *cl) 1002 1.2 peter { 1003 1.2 peter TSENTRY *popped; 1004 1.2 peter popped = tslist_last(cl->arv_tm); 1005 1.2 peter if (popped != NULL) { 1006 1.2 peter TAILQ_REMOVE(cl->arv_tm, popped, ts_list); 1007 1.2 peter free(popped, M_DEVBUF); 1008 1.2 peter } 1009 1.2 peter return; 1010 1.2 peter } 1011 1.2 peter 1012 1.2 peter /* 1013 1.2 peter * rate allocation support routines 1014 1.2 peter */ 1015 1.2 peter /* 1016 1.2 peter * enforce_wc: enforce that backlogged classes have non-zero 1017 1.2 peter * service rate, and that non-backlogged classes have zero 1018 1.2 peter * service rate. 1019 1.2 peter */ 1020 1.2 peter 1021 1.2 peter static int 1022 1.2 peter enforce_wc(struct jobs_if *jif) 1023 1.2 peter { 1024 1.2 peter struct jobs_class *cl; 1025 1.2 peter 1026 1.2 peter int64_t active_classes; 1027 1.2 peter int pri; 1028 1.2 peter int is_backlogged, class_exists, updated; 1029 1.2 peter 1030 1.2 peter updated = 0; 1031 1.2 peter active_classes = 0; 1032 1.2 peter 1033 1.2 peter for (pri = 0; pri <= jif->jif_maxpri; pri++) { 1034 1.2 peter cl = jif->jif_classes[pri]; 1035 1.2 peter class_exists = (cl != NULL); 1036 1.2 peter is_backlogged = (class_exists && !qempty(cl->cl_q)); 1037 1.2 peter 1038 1.2 peter if (is_backlogged) 1039 1.2 peter active_classes++; 1040 1.2 peter if ((is_backlogged && cl->service_rate <= 0) 1041 1.2 peter ||(class_exists 1042 1.2 peter && !is_backlogged && cl->service_rate > 0)) 1043 1.2 peter updated = 1; 1044 1.2 peter } 1045 1.2 peter 1046 1.2 peter if (updated) { 1047 1.2 peter for (pri = 0; pri <= jif->jif_maxpri; pri++) { 1048 1.2 peter cl = jif->jif_classes[pri]; 1049 1.2 peter class_exists = (cl != NULL); 1050 1.2 peter is_backlogged = (class_exists && !qempty(cl->cl_q)); 1051 1.2 peter 1052 1.2 peter if (class_exists && !is_backlogged) 1053 1.2 peter cl->service_rate = 0; 1054 1.2 peter else if (is_backlogged) 1055 1.2 peter cl->service_rate = (int64_t)(bps_to_internal((u_int64_t)jif->jif_bandwidth)/active_classes); 1056 1.2 peter } 1057 1.2 peter } 1058 1.2 peter 1059 1.2 peter return (updated); 1060 1.2 peter } 1061 1.2 peter 1062 1.2 peter /* 1063 1.2 peter * adjust_rates_rdc: compute the service rates adjustments 1064 1.2 peter * needed to realize the desired proportional delay differentiation. 1065 1.2 peter * essentially, the rate adjustement delta_rate = prop_control*error, 1066 1.2 peter * where error is the difference between the measured "weighted" 1067 1.2 peter * delay and the mean of the weighted delays. see paper for more 1068 1.2 peter * information. 1069 1.2 peter * prop_control has slightly changed since the INFOCOM paper, 1070 1.2 peter * this condition seems to provide better results. 1071 1.2 peter */ 1072 1.2 peter 1073 1.2 peter static int64_t * 1074 1.2 peter adjust_rates_rdc(struct jobs_if *jif) 1075 1.2 peter { 1076 1.2 peter int64_t *result; 1077 1.2 peter int64_t credit, available, lower_bound, upper_bound; 1078 1.2 peter int64_t bk; 1079 1.2 peter int i, j; 1080 1.2 peter int rdc_classes, active_classes; 1081 1.2 peter int class_exists, is_backlogged; 1082 1.2 peter struct jobs_class *cl; 1083 1.2 peter int64_t *error; 1084 1.2 peter int64_t prop_control; 1085 1.2 peter u_int64_t max_prod; 1086 1.2 peter u_int64_t min_share; 1087 1.2 peter u_int64_t max_avg_pkt_size; 1088 1.2 peter 1089 1.2 peter /* 1090 1.2 peter * min_share is scaled 1091 1.2 peter * to avoid dealing with doubles 1092 1.2 peter */ 1093 1.2 peter active_classes = 0; 1094 1.2 peter rdc_classes = 0; 1095 1.2 peter max_prod = 0; 1096 1.2 peter max_avg_pkt_size = 0; 1097 1.2 peter 1098 1.2 peter upper_bound = (int64_t)jif->jif_bandwidth; 1099 1.2 peter 1100 1.2 peter for (i = 0; i <= jif->jif_maxpri; i++) { 1101 1.2 peter cl = jif->jif_classes[i]; 1102 1.2 peter class_exists = (cl != NULL); 1103 1.2 peter is_backlogged = (class_exists && !qempty(cl->cl_q)); 1104 1.2 peter if (is_backlogged) { 1105 1.2 peter active_classes++; 1106 1.2 peter if (cl->concerned_rdc) 1107 1.2 peter rdc_classes++; 1108 1.2 peter else 1109 1.2 peter upper_bound -= 1110 1.2 peter internal_to_bps(cl->service_rate); 1111 1.2 peter } 1112 1.2 peter } 1113 1.2 peter 1114 1.2 peter result = malloc((jif->jif_maxpri+1)*sizeof(int64_t), 1115 1.2 peter M_DEVBUF, M_WAITOK); 1116 1.2 peter 1117 1.2 peter if (result == NULL) 1118 1.2 peter return NULL; 1119 1.2 peter 1120 1.2 peter for (i = 0; i <= jif->jif_maxpri; i++) 1121 1.2 peter result[i] = 0; 1122 1.2 peter 1123 1.2 peter if (upper_bound <= 0 || rdc_classes == 0) 1124 1.2 peter return result; 1125 1.2 peter 1126 1.2 peter credit = 0; 1127 1.2 peter lower_bound = 0; 1128 1.2 peter min_share = ((u_int64_t)1 << SCALE_SHARE); 1129 1.2 peter bk = 0; 1130 1.2 peter 1131 1.2 peter for (i = 0; i <= jif->jif_maxpri; i++) { 1132 1.2 peter cl = jif->jif_classes[i]; 1133 1.2 peter class_exists = (cl != NULL); 1134 1.2 peter is_backlogged = (class_exists && !qempty(cl->cl_q)); 1135 1.2 peter if (is_backlogged && cl->concerned_rdc) 1136 1.2 peter bk += cl->cl_rin.bytes; 1137 1.2 peter } 1138 1.2 peter 1139 1.2 peter if (bk == 0) 1140 1.14 joe return result; 1141 1.2 peter 1142 1.2 peter for (i = 0; i <= jif->jif_maxpri; i++) { 1143 1.2 peter cl = jif->jif_classes[i]; 1144 1.2 peter class_exists = (cl != NULL); 1145 1.2 peter is_backlogged = (class_exists && !qempty(cl->cl_q)); 1146 1.2 peter if (is_backlogged 1147 1.2 peter && (cl->cl_rin.bytes << SCALE_SHARE)/bk < min_share) 1148 1.2 peter min_share = (cl->cl_rin.bytes << SCALE_SHARE)/bk; 1149 1.2 peter if (is_backlogged && cl->concerned_rdc 1150 1.2 peter && cl->delay_prod_others > max_prod) 1151 1.2 peter max_prod = cl->delay_prod_others; 1152 1.2 peter 1153 1.2 peter if (is_backlogged && cl->concerned_rdc 1154 1.2 peter && cl->cl_rin.bytes > max_avg_pkt_size*cl->cl_rin.packets) 1155 1.2 peter max_avg_pkt_size = (u_int64_t)((u_int)cl->cl_rin.bytes/(u_int)cl->cl_rin.packets); 1156 1.2 peter } 1157 1.2 peter 1158 1.2 peter error = update_error(jif); 1159 1.2 peter if (!error) 1160 1.7 riastrad goto fail; 1161 1.2 peter 1162 1.2 peter prop_control = (upper_bound*upper_bound*min_share) 1163 1.2 peter /(max_prod*(max_avg_pkt_size << 2)); 1164 1.2 peter 1165 1.2 peter prop_control = bps_to_internal(ticks_to_secs(prop_control)); /* in BT-1 */ 1166 1.2 peter 1167 1.2 peter credit = 0; 1168 1.2 peter for (i = 0; i <= jif->jif_maxpri; i++) { 1169 1.2 peter cl = jif->jif_classes[i]; 1170 1.2 peter class_exists = (cl != NULL); 1171 1.2 peter is_backlogged = (class_exists && !qempty(cl->cl_q)); 1172 1.2 peter if (is_backlogged && cl->concerned_rdc) { 1173 1.2 peter result[i] = -prop_control*error[i]; /* in BT-1 */ 1174 1.2 peter result[i] >>= (SCALE_SHARE); 1175 1.2 peter } 1176 1.2 peter } 1177 1.2 peter 1178 1.2 peter free(error, M_DEVBUF); /* we don't need these anymore */ 1179 1.2 peter 1180 1.2 peter /* saturation */ 1181 1.2 peter 1182 1.2 peter for (i = 0; i <= jif->jif_maxpri; i++) { 1183 1.2 peter cl = jif->jif_classes[i]; 1184 1.2 peter class_exists = (cl != NULL); 1185 1.2 peter is_backlogged = (class_exists && !qempty(cl->cl_q)); 1186 1.2 peter 1187 1.2 peter if (is_backlogged && cl->concerned_rdc) 1188 1.2 peter lower_bound += cl->min_rate_adc; 1189 1.2 peter /* 1190 1.2 peter * note: if there's no ADC or ARC on cl, 1191 1.2 peter * this is equal to zero, which is fine 1192 1.2 peter */ 1193 1.2 peter } 1194 1.2 peter 1195 1.2 peter for (i = 0; i <= jif->jif_maxpri; i++) { 1196 1.2 peter cl = jif->jif_classes[i]; 1197 1.2 peter class_exists = (cl != NULL); 1198 1.2 peter is_backlogged = (class_exists && !qempty(cl->cl_q)); 1199 1.2 peter 1200 1.2 peter if (is_backlogged && cl->concerned_rdc 1201 1.2 peter && result[i] + cl->service_rate > upper_bound) { 1202 1.2 peter for (j = 0; j <= jif->jif_maxpri; j++) { 1203 1.2 peter cl = jif->jif_classes[j]; 1204 1.2 peter class_exists = (cl != NULL); 1205 1.2 peter is_backlogged = (class_exists 1206 1.2 peter && !qempty(cl->cl_q)); 1207 1.2 peter if (is_backlogged && cl->concerned_rdc) { 1208 1.2 peter if (j == i) 1209 1.2 peter result[j] = upper_bound 1210 1.2 peter -cl->service_rate 1211 1.2 peter + cl->min_rate_adc 1212 1.2 peter - lower_bound; 1213 1.2 peter else 1214 1.2 peter result[j] = 1215 1.2 peter -cl->service_rate 1216 1.2 peter +cl->min_rate_adc; 1217 1.2 peter } 1218 1.2 peter } 1219 1.2 peter return result; 1220 1.2 peter } 1221 1.2 peter 1222 1.2 peter cl = jif->jif_classes[i]; 1223 1.2 peter /* do this again since it may have been modified */ 1224 1.2 peter class_exists = (cl != NULL); 1225 1.2 peter is_backlogged = (class_exists && !qempty(cl->cl_q)); 1226 1.2 peter 1227 1.2 peter if (is_backlogged && cl->concerned_rdc 1228 1.2 peter && result[i] + cl->service_rate < cl->min_rate_adc) { 1229 1.2 peter credit += cl->service_rate+result[i] 1230 1.2 peter -cl->min_rate_adc; 1231 1.2 peter /* "credit" is in fact a negative number */ 1232 1.2 peter result[i] = -cl->service_rate+cl->min_rate_adc; 1233 1.2 peter } 1234 1.2 peter } 1235 1.2 peter 1236 1.2 peter for (i = jif->jif_maxpri; (i >= 0 && credit < 0); i--) { 1237 1.2 peter cl = jif->jif_classes[i]; 1238 1.2 peter class_exists = (cl != NULL); 1239 1.2 peter is_backlogged = (class_exists && !qempty(cl->cl_q)); 1240 1.2 peter 1241 1.2 peter if (is_backlogged && cl->concerned_rdc) { 1242 1.2 peter available = result[i] 1243 1.2 peter + cl->service_rate-cl->min_rate_adc; 1244 1.2 peter if (available >= -credit) { 1245 1.2 peter result[i] += credit; 1246 1.2 peter credit = 0; 1247 1.2 peter } else { 1248 1.2 peter result[i] -= available; 1249 1.2 peter credit += available; 1250 1.2 peter } 1251 1.2 peter } 1252 1.2 peter } 1253 1.2 peter return result; 1254 1.7 riastrad 1255 1.7 riastrad fail: free(result, M_DEVBUF); 1256 1.7 riastrad return NULL; 1257 1.2 peter } 1258 1.2 peter 1259 1.2 peter /* 1260 1.2 peter * assign_rate_drops_adc: returns the adjustment needed to 1261 1.2 peter * the service rates to meet the absolute delay/rate constraints 1262 1.2 peter * (delay/throughput bounds) and drops traffic if need be. 1263 1.2 peter * see tech. report UVA/T.R. CS-2000-24/CS-2001-21 for more info. 1264 1.2 peter */ 1265 1.2 peter 1266 1.2 peter static int64_t * 1267 1.2 peter assign_rate_drops_adc(struct jobs_if *jif) 1268 1.2 peter { 1269 1.2 peter int64_t *result; 1270 1.2 peter int class_exists, is_backlogged; 1271 1.2 peter struct jobs_class *cl; 1272 1.2 peter 1273 1.2 peter int64_t *c, *n, *k; 1274 1.2 peter int64_t *available; 1275 1.2 peter 1276 1.2 peter int lowest, highest; 1277 1.2 peter int keep_going; 1278 1.2 peter int i; 1279 1.2 peter u_int64_t now, oldest_arv; 1280 1.2 peter int64_t remaining_time; 1281 1.2 peter struct mbuf* pkt; 1282 1.2 peter u_int64_t len; 1283 1.2 peter 1284 1.2 peter now = read_machclk(); 1285 1.2 peter oldest_arv = now; 1286 1.2 peter 1287 1.2 peter result = malloc((jif->jif_maxpri+1)*sizeof(int64_t), M_DEVBUF, M_WAITOK); 1288 1.2 peter if (result == NULL) 1289 1.7 riastrad goto fail0; 1290 1.2 peter c = malloc((jif->jif_maxpri+1)*sizeof(u_int64_t), M_DEVBUF, M_WAITOK); 1291 1.2 peter if (c == NULL) 1292 1.7 riastrad goto fail1; 1293 1.2 peter n = malloc((jif->jif_maxpri+1)*sizeof(u_int64_t), M_DEVBUF, M_WAITOK); 1294 1.2 peter if (n == NULL) 1295 1.7 riastrad goto fail2; 1296 1.2 peter k = malloc((jif->jif_maxpri+1)*sizeof(u_int64_t), M_DEVBUF, M_WAITOK); 1297 1.2 peter if (k == NULL) 1298 1.7 riastrad goto fail3; 1299 1.2 peter available = malloc((jif->jif_maxpri+1)*sizeof(int64_t), M_DEVBUF, M_WAITOK); 1300 1.2 peter if (available == NULL) 1301 1.7 riastrad goto fail4; 1302 1.2 peter 1303 1.2 peter for (i = 0; i <= jif->jif_maxpri; i++) 1304 1.2 peter result[i] = 0; 1305 1.2 peter 1306 1.2 peter keep_going = 1; 1307 1.2 peter 1308 1.2 peter for (i = 0; i <= jif->jif_maxpri; i++) { 1309 1.2 peter cl = jif->jif_classes[i]; 1310 1.2 peter class_exists = (cl != NULL); 1311 1.2 peter is_backlogged = (class_exists && !qempty(cl->cl_q)); 1312 1.2 peter 1313 1.2 peter if (is_backlogged) { 1314 1.2 peter if (cl->concerned_adc) { 1315 1.2 peter /* 1316 1.2 peter * get the arrival time of the oldest 1317 1.2 peter * class-i packet 1318 1.2 peter */ 1319 1.2 peter if (tslist_first(cl->arv_tm) == NULL) 1320 1.2 peter oldest_arv = now; /* NOTREACHED */ 1321 1.2 peter else 1322 1.2 peter oldest_arv = (tslist_first(cl->arv_tm))->timestamp; 1323 1.2 peter 1324 1.2 peter n[i] = cl->service_rate; 1325 1.2 peter k[i] = scale_rate((int64_t)(cl->cl_rin.bytes - cl->cl_rout.bytes)); 1326 1.2 peter 1327 1.2 peter remaining_time = cl->cl_adc 1328 1.2 peter - (int64_t)delay_diff(now, oldest_arv); 1329 1.2 peter if (remaining_time > 0) { 1330 1.2 peter c[i] = remaining_time; 1331 1.2 peter /* 1332 1.2 peter * c is the remaining time before 1333 1.2 peter * the deadline is violated 1334 1.2 peter * (in ticks) 1335 1.2 peter */ 1336 1.2 peter available[i] = n[i]-k[i]/c[i]; 1337 1.2 peter } else { 1338 1.2 peter /* 1339 1.2 peter * deadline has passed... 1340 1.2 peter * we allocate the whole link 1341 1.2 peter * capacity to hopefully 1342 1.2 peter * solve the problem 1343 1.2 peter */ 1344 1.2 peter c[i] = 0; 1345 1.2 peter available[i] = -((int64_t)bps_to_internal((u_int64_t)jif->jif_bandwidth)); 1346 1.2 peter } 1347 1.2 peter if (cl->concerned_arc) { 1348 1.2 peter /* 1349 1.2 peter * there's an ARC in addition 1350 1.2 peter * to the ADC 1351 1.2 peter */ 1352 1.2 peter if (n[i] - cl->cl_arc < available[i]) 1353 1.2 peter available[i] = n[i] 1354 1.2 peter - cl->cl_arc; 1355 1.2 peter } 1356 1.2 peter } else if (cl->concerned_arc) { 1357 1.2 peter /* 1358 1.2 peter * backlogged, concerned by ARC 1359 1.2 peter * but not by ADC 1360 1.2 peter */ 1361 1.2 peter n[i] = cl->service_rate; 1362 1.2 peter available[i] = n[i] - cl->cl_arc; 1363 1.2 peter } else { 1364 1.2 peter /* 1365 1.2 peter * backlogged but not concerned by ADC 1366 1.2 peter * or ARC -> can give everything 1367 1.2 peter */ 1368 1.2 peter n[i] = cl->service_rate; 1369 1.2 peter available[i] = n[i]; 1370 1.2 peter } 1371 1.2 peter } else { 1372 1.2 peter /* not backlogged */ 1373 1.2 peter n[i] = 0; 1374 1.2 peter k[i] = 0; 1375 1.2 peter c[i] = 0; 1376 1.2 peter if (class_exists) 1377 1.2 peter available[i] = cl->service_rate; 1378 1.2 peter else 1379 1.2 peter available[i] = 0; 1380 1.2 peter } 1381 1.2 peter } 1382 1.2 peter 1383 1.2 peter /* step 1: adjust rates (greedy algorithm) */ 1384 1.2 peter 1385 1.2 peter highest = 0; 1386 1.2 peter lowest = jif->jif_maxpri; 1387 1.2 peter 1388 1.2 peter while (highest < jif->jif_maxpri+1 && available[highest] >= 0) 1389 1.2 peter highest++; /* which is the highest class that needs more service? */ 1390 1.2 peter while (lowest > 0 && available[lowest] <= 0) 1391 1.2 peter lowest--; /* which is the lowest class that needs less service? */ 1392 1.2 peter 1393 1.2 peter while (highest != jif->jif_maxpri+1 && lowest != -1) { 1394 1.2 peter /* give the excess service from lowest to highest */ 1395 1.2 peter if (available[lowest]+available[highest] > 0) { 1396 1.2 peter /* 1397 1.2 peter * still some "credit" left 1398 1.2 peter * give all that is needed by "highest" 1399 1.2 peter */ 1400 1.2 peter n[lowest] += available[highest]; 1401 1.2 peter n[highest] -= available[highest]; 1402 1.2 peter available[lowest] += available[highest]; 1403 1.2 peter available[highest] = 0; 1404 1.2 peter 1405 1.2 peter while (highest < jif->jif_maxpri+1 1406 1.2 peter && available[highest] >= 0) 1407 1.2 peter highest++; /* which is the highest class that needs more service now? */ 1408 1.2 peter 1409 1.2 peter } else if (available[lowest]+available[highest] == 0) { 1410 1.2 peter /* no more credit left but it's fine */ 1411 1.2 peter n[lowest] += available[highest]; 1412 1.2 peter n[highest] -= available[highest]; 1413 1.2 peter available[highest] = 0; 1414 1.2 peter available[lowest] = 0; 1415 1.2 peter 1416 1.2 peter while (highest < jif->jif_maxpri+1 1417 1.2 peter && available[highest] >= 0) 1418 1.2 peter highest++; /* which is the highest class that needs more service? */ 1419 1.2 peter while (lowest >= 0 && available[lowest] <= 0) 1420 1.2 peter lowest--; /* which is the lowest class that needs less service? */ 1421 1.2 peter 1422 1.2 peter } else if (available[lowest]+available[highest] < 0) { 1423 1.2 peter /* 1424 1.2 peter * no more credit left and we need to switch 1425 1.2 peter * to another class 1426 1.2 peter */ 1427 1.2 peter n[lowest] -= available[lowest]; 1428 1.2 peter n[highest] += available[lowest]; 1429 1.2 peter available[highest] += available[lowest]; 1430 1.2 peter available[lowest] = 0; 1431 1.2 peter 1432 1.2 peter while ((lowest >= 0)&&(available[lowest] <= 0)) 1433 1.2 peter lowest--; /* which is the lowest class that needs less service? */ 1434 1.2 peter } 1435 1.2 peter } 1436 1.2 peter 1437 1.2 peter for (i = 0; i <= jif->jif_maxpri; i++) { 1438 1.2 peter cl = jif->jif_classes[i]; 1439 1.2 peter class_exists = (cl != NULL); 1440 1.2 peter is_backlogged = (class_exists && !qempty(cl->cl_q)); 1441 1.2 peter if (is_backlogged) { 1442 1.2 peter result[i] = n[i] - cl->service_rate; 1443 1.2 peter } else { 1444 1.2 peter if (class_exists) 1445 1.2 peter result[i] = - cl->service_rate; 1446 1.2 peter else 1447 1.2 peter result[i] = 0; 1448 1.2 peter } 1449 1.2 peter } 1450 1.2 peter 1451 1.2 peter /* step 2: adjust drops (for ADC) */ 1452 1.2 peter 1453 1.2 peter if (highest != jif->jif_maxpri+1) { 1454 1.2 peter /* some class(es) still need(s) additional service */ 1455 1.2 peter for (i = 0; i <= jif->jif_maxpri; i++) { 1456 1.2 peter cl = jif->jif_classes[i]; 1457 1.2 peter class_exists = (cl != NULL); 1458 1.2 peter is_backlogged = (class_exists 1459 1.2 peter && !qempty(cl->cl_q)); 1460 1.2 peter if (is_backlogged && available[i] < 0) { 1461 1.2 peter if (cl->concerned_adc) { 1462 1.2 peter k[i] = c[i]*n[i]; 1463 1.2 peter while (keep_going && scale_rate((int64_t)(cl->cl_rin.bytes-cl->cl_rout.bytes)) > k[i]) { 1464 1.2 peter pkt = qtail(cl->cl_q); 1465 1.2 peter if (pkt != NULL) { 1466 1.2 peter /* "safeguard" test (a packet SHOULD be in there) */ 1467 1.2 peter len = (u_int64_t)m_pktlen(pkt); 1468 1.2 peter /* access packet at the tail */ 1469 1.2 peter if (cl->concerned_alc 1470 1.2 peter && cl->current_loss+(len << SCALE_LOSS)/cl->cl_arrival.bytes > cl->cl_alc) { 1471 1.2 peter keep_going = 0; /* relax ADC in favor of ALC */ 1472 1.2 peter } else { 1473 1.2 peter /* drop packet at the tail of the class-i queue, update values */ 1474 1.2 peter pkt = _getq_tail(cl->cl_q); 1475 1.2 peter len = (u_int64_t)m_pktlen(pkt); 1476 1.2 peter PKTCNTR_ADD(&cl->cl_dropcnt, (int)len); 1477 1.2 peter PKTCNTR_SUB(&cl->cl_rin, (int)len); 1478 1.2 peter PKTCNTR_ADD(&cl->st_dropcnt, (int)len); 1479 1.2 peter PKTCNTR_SUB(&cl->st_rin, (int)len); 1480 1.2 peter cl->current_loss += (len << SCALE_LOSS)/cl->cl_arrival.bytes; 1481 1.2 peter m_freem(pkt); /* the packet is trashed here */ 1482 1.2 peter tslist_drop(cl); 1483 1.2 peter IFQ_DEC_LEN(cl->cl_jif->jif_ifq); 1484 1.2 peter } 1485 1.2 peter } else 1486 1.2 peter keep_going = 0; /* NOTREACHED */ 1487 1.2 peter } 1488 1.2 peter k[i] = scale_rate((int64_t)(cl->cl_rin.bytes-cl->cl_rout.bytes)); 1489 1.2 peter } 1490 1.2 peter /* 1491 1.2 peter * n[i] is the max rate we can give. 1492 1.2 peter * the above drops as much as possible 1493 1.2 peter * to respect a delay bound. 1494 1.2 peter * for throughput bounds, 1495 1.2 peter * there's nothing that can be done 1496 1.2 peter * after the greedy reallocation. 1497 1.2 peter */ 1498 1.2 peter } 1499 1.2 peter } 1500 1.2 peter } 1501 1.2 peter 1502 1.2 peter /* update the values of min_rate_adc */ 1503 1.2 peter for (i = 0; i <= jif->jif_maxpri; i++) { 1504 1.2 peter cl = jif->jif_classes[i]; 1505 1.2 peter class_exists = (cl != NULL); 1506 1.2 peter is_backlogged = (class_exists && !qempty(cl->cl_q)); 1507 1.2 peter if (is_backlogged && cl->concerned_adc) { 1508 1.2 peter if (c[i] != 0) { 1509 1.2 peter if (cl->concerned_adc 1510 1.2 peter && !cl->concerned_arc) 1511 1.2 peter cl->min_rate_adc = k[i]/c[i]; 1512 1.2 peter else 1513 1.2 peter cl->min_rate_adc = n[i]; 1514 1.2 peter } else 1515 1.2 peter cl->min_rate_adc = (int64_t)bps_to_internal((u_int64_t)jif->jif_bandwidth); 1516 1.2 peter } else if (is_backlogged && cl->concerned_arc) 1517 1.2 peter cl->min_rate_adc = n[i]; /* the best we can give */ 1518 1.2 peter else { 1519 1.2 peter if (class_exists) 1520 1.2 peter cl->min_rate_adc = 0; 1521 1.2 peter } 1522 1.2 peter } 1523 1.2 peter 1524 1.2 peter free(c, M_DEVBUF); 1525 1.2 peter free(n, M_DEVBUF); 1526 1.2 peter free(k, M_DEVBUF); 1527 1.2 peter free(available, M_DEVBUF); 1528 1.2 peter 1529 1.14 joe return result; 1530 1.7 riastrad 1531 1.7 riastrad fail5: __unused 1532 1.7 riastrad free(available, M_DEVBUF); 1533 1.7 riastrad fail4: free(k, M_DEVBUF); 1534 1.7 riastrad fail3: free(n, M_DEVBUF); 1535 1.7 riastrad fail2: free(c, M_DEVBUF); 1536 1.7 riastrad fail1: free(result, M_DEVBUF); 1537 1.7 riastrad fail0: return NULL; 1538 1.2 peter } 1539 1.2 peter 1540 1.2 peter /* 1541 1.2 peter * update_error: returns the difference between the mean weighted 1542 1.2 peter * delay and the weighted delay for each class. if proportional 1543 1.2 peter * delay differentiation is perfectly achieved, it should return 1544 1.2 peter * zero for each class. 1545 1.2 peter */ 1546 1.2 peter static int64_t * 1547 1.2 peter update_error(struct jobs_if *jif) 1548 1.2 peter { 1549 1.2 peter int i; 1550 1.10 dholland int active_classes; 1551 1.2 peter u_int64_t mean_weighted_delay; 1552 1.2 peter u_int64_t delays[JOBS_MAXPRI]; 1553 1.2 peter int64_t* error; 1554 1.2 peter int class_exists, is_backlogged; 1555 1.2 peter struct jobs_class *cl; 1556 1.2 peter 1557 1.2 peter error = malloc(sizeof(int64_t)*(jif->jif_maxpri+1), M_DEVBUF, 1558 1.2 peter M_WAITOK|M_ZERO); 1559 1.2 peter 1560 1.2 peter if (error == NULL) 1561 1.2 peter return NULL; 1562 1.2 peter 1563 1.2 peter mean_weighted_delay = 0; 1564 1.2 peter active_classes = 0; 1565 1.2 peter 1566 1.2 peter for (i = 0; i <= jif->jif_maxpri; i++) { 1567 1.2 peter cl = jif->jif_classes[i]; 1568 1.2 peter class_exists = (cl != NULL); 1569 1.2 peter is_backlogged = (class_exists && !qempty(cl->cl_q)); 1570 1.2 peter 1571 1.2 peter if (is_backlogged) { 1572 1.2 peter if (cl->concerned_rdc) { 1573 1.2 peter delays[i] = proj_delay(jif, i); 1574 1.2 peter mean_weighted_delay += cl->delay_prod_others*delays[i]; 1575 1.2 peter active_classes ++; 1576 1.2 peter } 1577 1.2 peter } 1578 1.2 peter } 1579 1.2 peter 1580 1.2 peter if (active_classes == 0) 1581 1.2 peter return error; 1582 1.2 peter else 1583 1.2 peter mean_weighted_delay /= active_classes; 1584 1.2 peter 1585 1.2 peter for (i = 0; i <= jif->jif_maxpri; i++) { 1586 1.2 peter cl = jif->jif_classes[i]; 1587 1.2 peter class_exists = (cl != NULL); 1588 1.2 peter is_backlogged = (class_exists && !qempty(cl->cl_q)); 1589 1.2 peter 1590 1.2 peter if (is_backlogged && cl->concerned_rdc) 1591 1.2 peter error[i] = ((int64_t)mean_weighted_delay)-((int64_t)cl->delay_prod_others*delays[i]); 1592 1.2 peter else 1593 1.2 peter error[i] = 0; /* 1594 1.2 peter * either the class isn't concerned, 1595 1.2 peter * or it's not backlogged. 1596 1.2 peter * in any case, the rate shouldn't 1597 1.2 peter * be adjusted. 1598 1.2 peter */ 1599 1.2 peter } 1600 1.2 peter return error; 1601 1.2 peter } 1602 1.2 peter 1603 1.2 peter /* 1604 1.2 peter * min_rates_adc: computes the minimum service rates needed in 1605 1.2 peter * each class to meet the absolute delay bounds. if, for any 1606 1.2 peter * class i, the current service rate of class i is less than 1607 1.2 peter * the computed minimum service rate, this function returns 1608 1.2 peter * false, true otherwise. 1609 1.2 peter */ 1610 1.2 peter static int 1611 1.2 peter min_rates_adc(struct jobs_if *jif) 1612 1.2 peter { 1613 1.2 peter int result; 1614 1.2 peter int i; 1615 1.2 peter int class_exists, is_backlogged; 1616 1.2 peter int64_t remaining_time; 1617 1.2 peter struct jobs_class *cl; 1618 1.2 peter result = 1; 1619 1.2 peter 1620 1.2 peter for (i = 0; i <= jif->jif_maxpri; i++) { 1621 1.2 peter cl = jif->jif_classes[i]; 1622 1.2 peter class_exists = (cl != NULL); 1623 1.2 peter is_backlogged = (class_exists && !qempty(cl->cl_q)); 1624 1.2 peter if (is_backlogged && cl->concerned_adc) { 1625 1.2 peter remaining_time = cl->cl_adc - proj_delay(jif, i); 1626 1.2 peter if (remaining_time > 0 ) { 1627 1.2 peter /* min rate needed for ADC */ 1628 1.2 peter cl->min_rate_adc = scale_rate((int64_t)(cl->cl_rin.bytes-cl->cl_rout.bytes))/remaining_time; 1629 1.2 peter if (cl->concerned_arc 1630 1.2 peter && cl->cl_arc > cl->min_rate_adc) { 1631 1.2 peter /* min rate needed for ADC + ARC */ 1632 1.2 peter cl->min_rate_adc = cl->cl_arc; 1633 1.2 peter } 1634 1.2 peter } else { 1635 1.2 peter /* the deadline has been exceeded: give the whole link capacity to hopefully fix the situation */ 1636 1.2 peter cl->min_rate_adc = (int64_t)bps_to_internal((u_int64_t)jif->jif_bandwidth); 1637 1.2 peter } 1638 1.2 peter } else if (is_backlogged && cl->concerned_arc) 1639 1.2 peter cl->min_rate_adc = cl->cl_arc; /* no ADC, an ARC */ 1640 1.2 peter else if (class_exists) 1641 1.2 peter cl->min_rate_adc = 0; /* 1642 1.2 peter * either the class is not 1643 1.2 peter * backlogged 1644 1.2 peter * or there is no ADC and 1645 1.2 peter * no ARC 1646 1.2 peter */ 1647 1.2 peter if (is_backlogged && cl->min_rate_adc > cl->service_rate) 1648 1.2 peter result = 0; 1649 1.2 peter } 1650 1.2 peter 1651 1.2 peter return result; 1652 1.2 peter } 1653 1.2 peter 1654 1.2 peter /* 1655 1.2 peter * proj_delay: computes the difference between the current time 1656 1.2 peter * and the time the oldest class-i packet still in the class-i 1657 1.2 peter * queue i arrived in the system. 1658 1.2 peter */ 1659 1.2 peter static int64_t 1660 1.2 peter proj_delay(struct jobs_if *jif, int i) 1661 1.2 peter { 1662 1.2 peter u_int64_t now; 1663 1.2 peter int class_exists, is_backlogged; 1664 1.2 peter struct jobs_class *cl; 1665 1.2 peter 1666 1.2 peter now = read_machclk(); 1667 1.2 peter cl = jif->jif_classes[i]; 1668 1.2 peter class_exists = (cl != NULL); 1669 1.2 peter is_backlogged = (class_exists && !qempty(cl->cl_q)); 1670 1.2 peter 1671 1.2 peter if (is_backlogged) 1672 1.2 peter return ((int64_t)delay_diff(now, tslist_first(cl->arv_tm)->timestamp)); 1673 1.2 peter 1674 1.14 joe return 0; /* NOTREACHED */ 1675 1.2 peter } 1676 1.2 peter 1677 1.2 peter /* 1678 1.2 peter * pick_dropped_rlc: returns the class index of the class to be 1679 1.2 peter * dropped for meeting the relative loss constraints. 1680 1.2 peter */ 1681 1.2 peter static int 1682 1.2 peter pick_dropped_rlc(struct jobs_if *jif) 1683 1.2 peter { 1684 1.2 peter int64_t mean; 1685 1.2 peter int64_t* loss_error; 1686 1.10 dholland int i, active_classes; 1687 1.2 peter int class_exists, is_backlogged; 1688 1.2 peter int class_dropped; 1689 1.2 peter int64_t max_error; 1690 1.2 peter int64_t max_alc; 1691 1.2 peter struct mbuf* pkt; 1692 1.2 peter struct jobs_class *cl; 1693 1.2 peter u_int64_t len; 1694 1.2 peter 1695 1.2 peter loss_error = malloc(sizeof(int64_t)*(jif->jif_maxpri+1), 1696 1.2 peter M_DEVBUF, M_WAITOK); 1697 1.2 peter 1698 1.2 peter if (loss_error == NULL) 1699 1.2 peter return -1; 1700 1.2 peter 1701 1.2 peter class_dropped = -1; 1702 1.2 peter max_error = 0; 1703 1.2 peter mean = 0; 1704 1.2 peter active_classes = 0; 1705 1.2 peter 1706 1.2 peter for (i = 0; i <= jif->jif_maxpri; i++) { 1707 1.2 peter cl = jif->jif_classes[i]; 1708 1.2 peter class_exists = (cl != NULL); 1709 1.2 peter is_backlogged = (class_exists && !qempty(cl->cl_q)); 1710 1.2 peter if (is_backlogged) { 1711 1.2 peter if (cl->concerned_rlc) { 1712 1.2 peter mean += cl->loss_prod_others 1713 1.2 peter * cl->current_loss; 1714 1.2 peter active_classes++; 1715 1.2 peter } 1716 1.2 peter } 1717 1.2 peter } 1718 1.2 peter 1719 1.2 peter if (active_classes > 0) 1720 1.2 peter mean /= active_classes; 1721 1.2 peter 1722 1.2 peter if (active_classes == 0) 1723 1.2 peter class_dropped = JOBS_MAXPRI+1; /* 1724 1.2 peter * no classes are concerned 1725 1.2 peter * by RLCs (JOBS_MAXPRI+1 1726 1.2 peter * means "ignore RLC" here) 1727 1.2 peter */ 1728 1.2 peter else { 1729 1.2 peter for (i = 0; i <= jif->jif_maxpri; i++) { 1730 1.2 peter cl = jif->jif_classes[i]; 1731 1.2 peter class_exists = (cl != NULL); 1732 1.2 peter is_backlogged = (class_exists 1733 1.2 peter && !qempty(cl->cl_q)); 1734 1.2 peter 1735 1.2 peter if ((is_backlogged)&&(cl->cl_rlc)) 1736 1.2 peter loss_error[i]=cl->loss_prod_others 1737 1.2 peter *cl->current_loss-mean; 1738 1.2 peter else 1739 1.6 plunky loss_error[i] = ALTQ_INFINITY; 1740 1.2 peter } 1741 1.2 peter 1742 1.2 peter for (i = 0; i <= jif->jif_maxpri; i++) { 1743 1.2 peter cl = jif->jif_classes[i]; 1744 1.2 peter class_exists = (cl != NULL); 1745 1.2 peter is_backlogged = (class_exists 1746 1.2 peter && !qempty(cl->cl_q)); 1747 1.2 peter if (is_backlogged && loss_error[i] <= max_error) { 1748 1.2 peter /* 1749 1.2 peter * find out which class is the most 1750 1.2 peter * below the mean. 1751 1.2 peter * it's the one that needs to be dropped 1752 1.2 peter * ties are broken in favor of the higher 1753 1.2 peter * priority classes (i.e., if two classes 1754 1.2 peter * present the same deviation, the lower 1755 1.2 peter * priority class will get dropped). 1756 1.2 peter */ 1757 1.2 peter max_error = loss_error[i]; 1758 1.2 peter class_dropped = i; 1759 1.2 peter } 1760 1.2 peter } 1761 1.2 peter 1762 1.2 peter if (class_dropped != -1) { 1763 1.2 peter cl = jif->jif_classes[class_dropped]; 1764 1.2 peter pkt = qtail(cl->cl_q); 1765 1.2 peter if (pkt != NULL) { 1766 1.2 peter /* 1767 1.2 peter * "safeguard" test (a packet SHOULD be 1768 1.2 peter * in there) 1769 1.2 peter */ 1770 1.2 peter len = (u_int64_t)m_pktlen(pkt); 1771 1.2 peter /* access packet at the tail */ 1772 1.2 peter if (cl->current_loss+(len << SCALE_LOSS)/cl->cl_arrival.bytes > cl->cl_alc) { 1773 1.2 peter /* 1774 1.2 peter * the class to drop for meeting 1775 1.2 peter * the RLC will defeat the ALC: 1776 1.2 peter * ignore RLC. 1777 1.2 peter */ 1778 1.2 peter class_dropped = JOBS_MAXPRI+1; 1779 1.2 peter } 1780 1.2 peter } else 1781 1.2 peter class_dropped = JOBS_MAXPRI+1; /* NOTREACHED */ 1782 1.2 peter } else 1783 1.2 peter class_dropped = JOBS_MAXPRI+1; 1784 1.2 peter } 1785 1.2 peter 1786 1.2 peter if (class_dropped == JOBS_MAXPRI+1) { 1787 1.2 peter max_alc = -((int64_t)1 << SCALE_LOSS); 1788 1.2 peter for (i = jif->jif_maxpri; i >= 0; i--) { 1789 1.2 peter cl = jif->jif_classes[i]; 1790 1.2 peter class_exists = (cl != NULL); 1791 1.2 peter is_backlogged = (class_exists 1792 1.2 peter && !qempty(cl->cl_q)); 1793 1.2 peter if (is_backlogged) { 1794 1.2 peter if (cl->concerned_alc && cl->cl_alc - cl->current_loss > max_alc) { 1795 1.2 peter max_alc = cl->cl_alc-cl->current_loss; /* pick the class which is the furthest from its ALC */ 1796 1.2 peter class_dropped = i; 1797 1.2 peter } else if (!cl->concerned_alc && ((int64_t) 1 << SCALE_LOSS)-cl->current_loss > max_alc) { 1798 1.2 peter max_alc = ((int64_t) 1 << SCALE_LOSS)-cl->current_loss; 1799 1.2 peter class_dropped = i; 1800 1.2 peter } 1801 1.2 peter } 1802 1.2 peter } 1803 1.2 peter } 1804 1.2 peter 1805 1.2 peter free(loss_error, M_DEVBUF); 1806 1.2 peter return (class_dropped); 1807 1.2 peter } 1808 1.2 peter 1809 1.2 peter /* 1810 1.2 peter * ALTQ binding/setup functions 1811 1.2 peter */ 1812 1.2 peter /* 1813 1.2 peter * jobs device interface 1814 1.2 peter */ 1815 1.2 peter int 1816 1.4 christos jobsopen(dev_t dev, int flag, int fmt, 1817 1.4 christos struct lwp *l) 1818 1.2 peter { 1819 1.2 peter if (machclk_freq == 0) 1820 1.2 peter init_machclk(); 1821 1.2 peter 1822 1.2 peter if (machclk_freq == 0) { 1823 1.2 peter printf("jobs: no CPU clock available!\n"); 1824 1.14 joe return ENXIO; 1825 1.2 peter } 1826 1.2 peter /* everything will be done when the queueing scheme is attached. */ 1827 1.2 peter return 0; 1828 1.2 peter } 1829 1.2 peter 1830 1.2 peter int 1831 1.4 christos jobsclose(dev_t dev, int flag, int fmt, 1832 1.4 christos struct lwp *l) 1833 1.2 peter { 1834 1.2 peter struct jobs_if *jif; 1835 1.2 peter 1836 1.2 peter while ((jif = jif_list) != NULL) { 1837 1.2 peter /* destroy all */ 1838 1.2 peter if (ALTQ_IS_ENABLED(jif->jif_ifq)) 1839 1.2 peter altq_disable(jif->jif_ifq); 1840 1.2 peter 1841 1.13 joe int error = altq_detach(jif->jif_ifq); 1842 1.8 christos switch (error) { 1843 1.8 christos case 0: 1844 1.8 christos case ENXIO: /* already disabled */ 1845 1.8 christos break; 1846 1.8 christos default: 1847 1.8 christos return error; 1848 1.8 christos } 1849 1.8 christos jobs_detach(jif); 1850 1.2 peter } 1851 1.2 peter 1852 1.13 joe return 0; 1853 1.2 peter } 1854 1.2 peter 1855 1.2 peter int 1856 1.5 christos jobsioctl(dev_t dev, ioctlcmd_t cmd, void *addr, int flag, 1857 1.2 peter struct lwp *l) 1858 1.2 peter { 1859 1.2 peter struct jobs_if *jif; 1860 1.2 peter struct jobs_interface *ifacep; 1861 1.2 peter int error = 0; 1862 1.2 peter 1863 1.2 peter /* check super-user privilege */ 1864 1.2 peter switch (cmd) { 1865 1.2 peter case JOBS_GETSTATS: 1866 1.2 peter break; 1867 1.2 peter default: 1868 1.12 christos if ((error = kauth_authorize_network(l->l_cred, 1869 1.3 elad KAUTH_NETWORK_ALTQ, KAUTH_REQ_NETWORK_ALTQ_JOBS, NULL, 1870 1.3 elad NULL, NULL)) != 0) 1871 1.2 peter return (error); 1872 1.2 peter break; 1873 1.2 peter } 1874 1.2 peter 1875 1.2 peter switch (cmd) { 1876 1.2 peter 1877 1.2 peter case JOBS_IF_ATTACH: 1878 1.2 peter error = jobscmd_if_attach((struct jobs_attach *)addr); 1879 1.2 peter break; 1880 1.2 peter 1881 1.2 peter case JOBS_IF_DETACH: 1882 1.2 peter error = jobscmd_if_detach((struct jobs_interface *)addr); 1883 1.2 peter break; 1884 1.2 peter 1885 1.2 peter case JOBS_ENABLE: 1886 1.2 peter case JOBS_DISABLE: 1887 1.2 peter case JOBS_CLEAR: 1888 1.2 peter ifacep = (struct jobs_interface *)addr; 1889 1.2 peter if ((jif = altq_lookup(ifacep->jobs_ifname, 1890 1.2 peter ALTQT_JOBS)) == NULL) { 1891 1.2 peter error = EBADF; 1892 1.2 peter break; 1893 1.2 peter } 1894 1.2 peter 1895 1.2 peter switch (cmd) { 1896 1.2 peter case JOBS_ENABLE: 1897 1.2 peter if (jif->jif_default == NULL) { 1898 1.2 peter #if 1 1899 1.2 peter printf("jobs: no default class\n"); 1900 1.2 peter #endif 1901 1.2 peter error = EINVAL; 1902 1.2 peter break; 1903 1.2 peter } 1904 1.2 peter error = altq_enable(jif->jif_ifq); 1905 1.2 peter break; 1906 1.2 peter 1907 1.2 peter case JOBS_DISABLE: 1908 1.2 peter error = altq_disable(jif->jif_ifq); 1909 1.2 peter break; 1910 1.2 peter 1911 1.2 peter case JOBS_CLEAR: 1912 1.2 peter jobs_clear_interface(jif); 1913 1.2 peter break; 1914 1.2 peter } 1915 1.2 peter break; 1916 1.2 peter 1917 1.2 peter case JOBS_ADD_CLASS: 1918 1.2 peter error = jobscmd_add_class((struct jobs_add_class *)addr); 1919 1.2 peter break; 1920 1.2 peter 1921 1.2 peter case JOBS_DEL_CLASS: 1922 1.2 peter error = jobscmd_delete_class((struct jobs_delete_class *)addr); 1923 1.2 peter break; 1924 1.2 peter 1925 1.2 peter case JOBS_MOD_CLASS: 1926 1.2 peter error = jobscmd_modify_class((struct jobs_modify_class *)addr); 1927 1.2 peter break; 1928 1.2 peter 1929 1.2 peter case JOBS_ADD_FILTER: 1930 1.2 peter error = jobscmd_add_filter((struct jobs_add_filter *)addr); 1931 1.2 peter break; 1932 1.2 peter 1933 1.2 peter case JOBS_DEL_FILTER: 1934 1.2 peter error = jobscmd_delete_filter((struct jobs_delete_filter *)addr); 1935 1.2 peter break; 1936 1.2 peter 1937 1.2 peter case JOBS_GETSTATS: 1938 1.2 peter error = jobscmd_class_stats((struct jobs_class_stats *)addr); 1939 1.2 peter break; 1940 1.2 peter 1941 1.2 peter default: 1942 1.2 peter error = EINVAL; 1943 1.2 peter break; 1944 1.2 peter } 1945 1.2 peter return error; 1946 1.2 peter } 1947 1.2 peter 1948 1.2 peter static int 1949 1.2 peter jobscmd_if_attach(struct jobs_attach *ap) 1950 1.2 peter { 1951 1.2 peter struct jobs_if *jif; 1952 1.2 peter struct ifnet *ifp; 1953 1.2 peter int error; 1954 1.2 peter 1955 1.2 peter if ((ifp = ifunit(ap->iface.jobs_ifname)) == NULL) 1956 1.14 joe return ENXIO; 1957 1.2 peter if ((jif = jobs_attach(&ifp->if_snd, ap->bandwidth, ap->qlimit, ap->separate)) == NULL) 1958 1.14 joe return ENOMEM; 1959 1.2 peter 1960 1.2 peter /* 1961 1.2 peter * set JOBS to this ifnet structure. 1962 1.2 peter */ 1963 1.2 peter if ((error = altq_attach(&ifp->if_snd, ALTQT_JOBS, jif, 1964 1.2 peter jobs_enqueue, jobs_dequeue, jobs_request, 1965 1.2 peter &jif->jif_classifier, acc_classify)) != 0) 1966 1.8 christos jobs_detach(jif); 1967 1.2 peter 1968 1.14 joe return error; 1969 1.2 peter } 1970 1.2 peter 1971 1.2 peter static int 1972 1.2 peter jobscmd_if_detach(struct jobs_interface *ap) 1973 1.2 peter { 1974 1.2 peter struct jobs_if *jif; 1975 1.2 peter int error; 1976 1.2 peter 1977 1.2 peter if ((jif = altq_lookup(ap->jobs_ifname, ALTQT_JOBS)) == NULL) 1978 1.14 joe return EBADF; 1979 1.2 peter 1980 1.2 peter if (ALTQ_IS_ENABLED(jif->jif_ifq)) 1981 1.2 peter altq_disable(jif->jif_ifq); 1982 1.2 peter 1983 1.2 peter if ((error = altq_detach(jif->jif_ifq))) 1984 1.14 joe return error; 1985 1.2 peter 1986 1.8 christos jobs_detach(jif); 1987 1.8 christos return 0; 1988 1.2 peter } 1989 1.2 peter 1990 1.2 peter static int 1991 1.2 peter jobscmd_add_class(struct jobs_add_class *ap) 1992 1.2 peter { 1993 1.2 peter struct jobs_if *jif; 1994 1.2 peter struct jobs_class *cl; 1995 1.2 peter 1996 1.2 peter if ((jif = altq_lookup(ap->iface.jobs_ifname, ALTQT_JOBS)) == NULL) 1997 1.14 joe return EBADF; 1998 1.2 peter 1999 1.2 peter if (ap->pri < 0 || ap->pri >= JOBS_MAXPRI) 2000 1.14 joe return EINVAL; 2001 1.2 peter 2002 1.2 peter if ((cl = jobs_class_create(jif, ap->pri, 2003 1.2 peter ap->cl_adc, ap->cl_rdc, 2004 1.2 peter ap->cl_alc, ap->cl_rlc, ap-> cl_arc, 2005 1.2 peter ap->flags)) == NULL) 2006 1.14 joe return ENOMEM; 2007 1.2 peter 2008 1.2 peter /* return a class handle to the user */ 2009 1.2 peter ap->class_handle = clp_to_clh(cl); 2010 1.14 joe return 0; 2011 1.2 peter } 2012 1.2 peter 2013 1.2 peter static int 2014 1.2 peter jobscmd_delete_class(struct jobs_delete_class *ap) 2015 1.2 peter { 2016 1.2 peter struct jobs_if *jif; 2017 1.2 peter struct jobs_class *cl; 2018 1.2 peter 2019 1.2 peter if ((jif = altq_lookup(ap->iface.jobs_ifname, ALTQT_JOBS)) == NULL) 2020 1.14 joe return EBADF; 2021 1.2 peter 2022 1.2 peter if ((cl = clh_to_clp(jif, ap->class_handle)) == NULL) 2023 1.14 joe return EINVAL; 2024 1.2 peter 2025 1.2 peter return jobs_class_destroy(cl); 2026 1.2 peter } 2027 1.2 peter 2028 1.2 peter static int 2029 1.2 peter jobscmd_modify_class(struct jobs_modify_class *ap) 2030 1.2 peter { 2031 1.2 peter struct jobs_if *jif; 2032 1.2 peter struct jobs_class *cl; 2033 1.2 peter 2034 1.2 peter if ((jif = altq_lookup(ap->iface.jobs_ifname, ALTQT_JOBS)) == NULL) 2035 1.14 joe return EBADF; 2036 1.2 peter 2037 1.2 peter if (ap->pri < 0 || ap->pri >= JOBS_MAXPRI) 2038 1.14 joe return EINVAL; 2039 1.2 peter 2040 1.2 peter if ((cl = clh_to_clp(jif, ap->class_handle)) == NULL) 2041 1.14 joe return EINVAL; 2042 1.2 peter 2043 1.2 peter /* 2044 1.2 peter * if priority is changed, move the class to the new priority 2045 1.2 peter */ 2046 1.2 peter if (jif->jif_classes[ap->pri] != cl) { 2047 1.2 peter if (jif->jif_classes[ap->pri] != NULL) 2048 1.14 joe return EEXIST; 2049 1.2 peter jif->jif_classes[cl->cl_pri] = NULL; 2050 1.2 peter jif->jif_classes[ap->pri] = cl; 2051 1.2 peter cl->cl_pri = ap->pri; 2052 1.2 peter } 2053 1.2 peter 2054 1.2 peter /* call jobs_class_create to change class parameters */ 2055 1.2 peter if ((cl = jobs_class_create(jif, ap->pri, 2056 1.2 peter ap->cl_adc, ap->cl_rdc, 2057 1.2 peter ap->cl_alc, ap->cl_rlc, ap->cl_arc, 2058 1.2 peter ap->flags)) == NULL) 2059 1.14 joe return ENOMEM; 2060 1.2 peter return 0; 2061 1.2 peter } 2062 1.2 peter 2063 1.2 peter static int 2064 1.2 peter jobscmd_add_filter(struct jobs_add_filter *ap) 2065 1.2 peter { 2066 1.2 peter struct jobs_if *jif; 2067 1.2 peter struct jobs_class *cl; 2068 1.2 peter 2069 1.2 peter if ((jif = altq_lookup(ap->iface.jobs_ifname, ALTQT_JOBS)) == NULL) 2070 1.14 joe return EBADF; 2071 1.2 peter 2072 1.2 peter if ((cl = clh_to_clp(jif, ap->class_handle)) == NULL) 2073 1.14 joe return EINVAL; 2074 1.2 peter 2075 1.2 peter return acc_add_filter(&jif->jif_classifier, &ap->filter, 2076 1.2 peter cl, &ap->filter_handle); 2077 1.2 peter } 2078 1.2 peter 2079 1.2 peter static int 2080 1.2 peter jobscmd_delete_filter(struct jobs_delete_filter *ap) 2081 1.2 peter { 2082 1.2 peter struct jobs_if *jif; 2083 1.2 peter 2084 1.2 peter if ((jif = altq_lookup(ap->iface.jobs_ifname, ALTQT_JOBS)) == NULL) 2085 1.14 joe return EBADF; 2086 1.2 peter 2087 1.2 peter return acc_delete_filter(&jif->jif_classifier, ap->filter_handle); 2088 1.2 peter } 2089 1.2 peter 2090 1.2 peter static int 2091 1.2 peter jobscmd_class_stats(struct jobs_class_stats *ap) 2092 1.2 peter { 2093 1.2 peter struct jobs_if *jif; 2094 1.2 peter struct jobs_class *cl; 2095 1.2 peter struct class_stats stats, *usp; 2096 1.2 peter int pri, error; 2097 1.2 peter 2098 1.2 peter if ((jif = altq_lookup(ap->iface.jobs_ifname, ALTQT_JOBS)) == NULL) 2099 1.14 joe return EBADF; 2100 1.2 peter 2101 1.2 peter ap->maxpri = jif->jif_maxpri; 2102 1.2 peter 2103 1.2 peter /* then, read the next N classes */ 2104 1.2 peter usp = ap->stats; 2105 1.2 peter for (pri = 0; pri <= jif->jif_maxpri; pri++) { 2106 1.2 peter cl = jif->jif_classes[pri]; 2107 1.11 riastrad (void)memset(&stats, 0, sizeof(stats)); 2108 1.2 peter if (cl != NULL) 2109 1.2 peter get_class_stats(&stats, cl); 2110 1.5 christos if ((error = copyout((void *)&stats, (void *)usp++, 2111 1.2 peter sizeof(stats))) != 0) 2112 1.14 joe return error; 2113 1.2 peter } 2114 1.14 joe return 0; 2115 1.2 peter } 2116 1.2 peter 2117 1.2 peter static void 2118 1.2 peter get_class_stats(struct class_stats *sp, struct jobs_class *cl) 2119 1.2 peter { 2120 1.2 peter u_int64_t now; 2121 1.2 peter now = read_machclk(); 2122 1.2 peter 2123 1.2 peter sp->class_handle = clp_to_clh(cl); 2124 1.2 peter sp->qlength = qlen(cl->cl_q); 2125 1.2 peter 2126 1.2 peter sp->period = cl->cl_period; 2127 1.2 peter sp->rin = cl->st_rin; 2128 1.2 peter sp->arrival = cl->st_arrival; 2129 1.2 peter sp->arrivalbusy = cl->cl_arrival; 2130 1.2 peter sp->rout = cl->st_rout; 2131 1.2 peter sp->dropcnt = cl->cl_dropcnt; 2132 1.2 peter 2133 1.2 peter /* PKTCNTR_RESET(&cl->st_arrival);*/ 2134 1.2 peter PKTCNTR_RESET(&cl->st_rin); 2135 1.2 peter PKTCNTR_RESET(&cl->st_rout); 2136 1.2 peter 2137 1.2 peter sp->totallength = cl->cl_jif->jif_ifq->ifq_len; 2138 1.2 peter sp->lastdel = ticks_to_secs(GRANULARITY*cl->cl_lastdel); 2139 1.2 peter sp->avgdel = cl->cl_avgdel; 2140 1.2 peter 2141 1.2 peter cl->cl_avgdel = 0; 2142 1.2 peter 2143 1.2 peter sp->busylength = ticks_to_secs(1000*delay_diff(now, cl->idletime)); 2144 1.2 peter sp->adc_violations = cl->adc_violations; 2145 1.2 peter 2146 1.2 peter sp->wc_cycles_enqueue = cl->cl_jif->wc_cycles_enqueue; 2147 1.2 peter sp->wc_cycles_dequeue = cl->cl_jif->wc_cycles_dequeue; 2148 1.2 peter sp->bc_cycles_enqueue = cl->cl_jif->bc_cycles_enqueue; 2149 1.2 peter sp->bc_cycles_dequeue = cl->cl_jif->bc_cycles_dequeue; 2150 1.2 peter sp->avg_cycles_enqueue = cl->cl_jif->avg_cycles_enqueue; 2151 1.2 peter sp->avg_cycles_dequeue = cl->cl_jif->avg_cycles_dequeue; 2152 1.2 peter sp->avg_cycles2_enqueue = cl->cl_jif->avg_cycles2_enqueue; 2153 1.2 peter sp->avg_cycles2_dequeue = cl->cl_jif->avg_cycles2_dequeue; 2154 1.2 peter sp->total_enqueued = cl->cl_jif->total_enqueued; 2155 1.2 peter sp->total_dequeued = cl->cl_jif->total_dequeued; 2156 1.2 peter } 2157 1.2 peter 2158 1.2 peter /* convert a class handle to the corresponding class pointer */ 2159 1.2 peter static struct jobs_class * 2160 1.2 peter clh_to_clp(struct jobs_if *jif, u_long chandle) 2161 1.2 peter { 2162 1.2 peter struct jobs_class *cl; 2163 1.2 peter 2164 1.2 peter cl = (struct jobs_class *)chandle; 2165 1.2 peter if (chandle != ALIGN(cl)) { 2166 1.2 peter #if 1 2167 1.2 peter printf("clh_to_cl: unaligned pointer %p\n", cl); 2168 1.2 peter #endif 2169 1.14 joe return NULL; 2170 1.2 peter } 2171 1.2 peter 2172 1.2 peter if (cl == NULL || cl->cl_handle != chandle || cl->cl_jif != jif) 2173 1.14 joe return NULL; 2174 1.14 joe return cl; 2175 1.2 peter } 2176 1.2 peter 2177 1.2 peter /* convert a class pointer to the corresponding class handle */ 2178 1.2 peter static u_long 2179 1.2 peter clp_to_clh(struct jobs_class *cl) 2180 1.2 peter { 2181 1.2 peter return (cl->cl_handle); 2182 1.2 peter } 2183 1.2 peter 2184 1.2 peter #ifdef KLD_MODULE 2185 1.2 peter 2186 1.2 peter static struct altqsw jobs_sw = 2187 1.2 peter {"jobs", jobsopen, jobsclose, jobsioctl}; 2188 1.2 peter 2189 1.2 peter ALTQ_MODULE(altq_jobs, ALTQT_JOBS, &jobs_sw); 2190 1.2 peter 2191 1.2 peter #endif /* KLD_MODULE */ 2192 1.2 peter 2193 1.2 peter #endif /* ALTQ3_COMPAT */ 2194 1.2 peter #endif /* ALTQ_JOBS */ 2195
Indexes created Tue Sep 30 17:09:57 GMT 2025