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