| @@ -1,14 +1,14 @@ | | | @@ -1,14 +1,14 @@ |
1 | /* $NetBSD: altq_jobs.c,v 1.6 2010/04/09 19:32:45 plunky Exp $ */ | | 1 | /* $NetBSD: altq_jobs.c,v 1.7 2014/08/18 03:14:12 riastradh Exp $ */ |
2 | /* $KAME: altq_jobs.c,v 1.11 2005/04/13 03:44:25 suz Exp $ */ | | 2 | /* $KAME: altq_jobs.c,v 1.11 2005/04/13 03:44:25 suz Exp $ */ |
3 | /* | | 3 | /* |
4 | * Copyright (c) 2001, the Rector and Board of Visitors of the | | 4 | * Copyright (c) 2001, the Rector and Board of Visitors of the |
5 | * University of Virginia. | | 5 | * University of Virginia. |
6 | * All rights reserved. | | 6 | * All rights reserved. |
7 | * | | 7 | * |
8 | * Redistribution and use in source and binary forms, | | 8 | * Redistribution and use in source and binary forms, |
9 | * with or without modification, are permitted provided | | 9 | * with or without modification, are permitted provided |
10 | * that the following conditions are met: | | 10 | * that the following conditions are met: |
11 | * | | 11 | * |
12 | * Redistributions of source code must retain the above | | 12 | * Redistributions of source code must retain the above |
13 | * copyright notice, this list of conditions and the following | | 13 | * copyright notice, this list of conditions and the following |
14 | * disclaimer. | | 14 | * disclaimer. |
| @@ -49,27 +49,27 @@ | | | @@ -49,27 +49,27 @@ |
49 | * Contributed by the Multimedia Networks Group at the University | | 49 | * Contributed by the Multimedia Networks Group at the University |
50 | * of Virginia. | | 50 | * of Virginia. |
51 | * | | 51 | * |
52 | * Papers and additional info can be found at | | 52 | * Papers and additional info can be found at |
53 | * http://qosbox.cs.virginia.edu | | 53 | * http://qosbox.cs.virginia.edu |
54 | * | | 54 | * |
55 | */ | | 55 | */ |
56 | | | 56 | |
57 | /* | | 57 | /* |
58 | * JoBS queue | | 58 | * JoBS queue |
59 | */ | | 59 | */ |
60 | | | 60 | |
61 | #include <sys/cdefs.h> | | 61 | #include <sys/cdefs.h> |
62 | __KERNEL_RCSID(0, "$NetBSD: altq_jobs.c,v 1.6 2010/04/09 19:32:45 plunky Exp $"); | | 62 | __KERNEL_RCSID(0, "$NetBSD: altq_jobs.c,v 1.7 2014/08/18 03:14:12 riastradh Exp $"); |
63 | | | 63 | |
64 | #ifdef _KERNEL_OPT | | 64 | #ifdef _KERNEL_OPT |
65 | #include "opt_altq.h" | | 65 | #include "opt_altq.h" |
66 | #include "opt_inet.h" | | 66 | #include "opt_inet.h" |
67 | #endif | | 67 | #endif |
68 | | | 68 | |
69 | #ifdef ALTQ_JOBS /* jobs is enabled by ALTQ_JOBS option in opt_altq.h */ | | 69 | #ifdef ALTQ_JOBS /* jobs is enabled by ALTQ_JOBS option in opt_altq.h */ |
70 | | | 70 | |
71 | #include <sys/param.h> | | 71 | #include <sys/param.h> |
72 | #include <sys/malloc.h> | | 72 | #include <sys/malloc.h> |
73 | #include <sys/mbuf.h> | | 73 | #include <sys/mbuf.h> |
74 | #include <sys/socket.h> | | 74 | #include <sys/socket.h> |
75 | #include <sys/sockio.h> | | 75 | #include <sys/sockio.h> |
| @@ -1148,27 +1148,27 @@ adjust_rates_rdc(struct jobs_if *jif) | | | @@ -1148,27 +1148,27 @@ adjust_rates_rdc(struct jobs_if *jif) |
1148 | && (cl->cl_rin.bytes << SCALE_SHARE)/bk < min_share) | | 1148 | && (cl->cl_rin.bytes << SCALE_SHARE)/bk < min_share) |
1149 | min_share = (cl->cl_rin.bytes << SCALE_SHARE)/bk; | | 1149 | min_share = (cl->cl_rin.bytes << SCALE_SHARE)/bk; |
1150 | if (is_backlogged && cl->concerned_rdc | | 1150 | if (is_backlogged && cl->concerned_rdc |
1151 | && cl->delay_prod_others > max_prod) | | 1151 | && cl->delay_prod_others > max_prod) |
1152 | max_prod = cl->delay_prod_others; | | 1152 | max_prod = cl->delay_prod_others; |
1153 | | | 1153 | |
1154 | if (is_backlogged && cl->concerned_rdc | | 1154 | if (is_backlogged && cl->concerned_rdc |
1155 | && cl->cl_rin.bytes > max_avg_pkt_size*cl->cl_rin.packets) | | 1155 | && cl->cl_rin.bytes > max_avg_pkt_size*cl->cl_rin.packets) |
1156 | max_avg_pkt_size = (u_int64_t)((u_int)cl->cl_rin.bytes/(u_int)cl->cl_rin.packets); | | 1156 | max_avg_pkt_size = (u_int64_t)((u_int)cl->cl_rin.bytes/(u_int)cl->cl_rin.packets); |
1157 | } | | 1157 | } |
1158 | | | 1158 | |
1159 | error = update_error(jif); | | 1159 | error = update_error(jif); |
1160 | if (!error) | | 1160 | if (!error) |
1161 | return (NULL); | | 1161 | goto fail; |
1162 | | | 1162 | |
1163 | prop_control = (upper_bound*upper_bound*min_share) | | 1163 | prop_control = (upper_bound*upper_bound*min_share) |
1164 | /(max_prod*(max_avg_pkt_size << 2)); | | 1164 | /(max_prod*(max_avg_pkt_size << 2)); |
1165 | | | 1165 | |
1166 | prop_control = bps_to_internal(ticks_to_secs(prop_control)); /* in BT-1 */ | | 1166 | prop_control = bps_to_internal(ticks_to_secs(prop_control)); /* in BT-1 */ |
1167 | | | 1167 | |
1168 | credit = 0; | | 1168 | credit = 0; |
1169 | for (i = 0; i <= jif->jif_maxpri; i++) { | | 1169 | for (i = 0; i <= jif->jif_maxpri; i++) { |
1170 | cl = jif->jif_classes[i]; | | 1170 | cl = jif->jif_classes[i]; |
1171 | class_exists = (cl != NULL); | | 1171 | class_exists = (cl != NULL); |
1172 | is_backlogged = (class_exists && !qempty(cl->cl_q)); | | 1172 | is_backlogged = (class_exists && !qempty(cl->cl_q)); |
1173 | if (is_backlogged && cl->concerned_rdc) { | | 1173 | if (is_backlogged && cl->concerned_rdc) { |
1174 | result[i] = -prop_control*error[i]; /* in BT-1 */ | | 1174 | result[i] = -prop_control*error[i]; /* in BT-1 */ |
| @@ -1242,26 +1242,29 @@ adjust_rates_rdc(struct jobs_if *jif) | | | @@ -1242,26 +1242,29 @@ adjust_rates_rdc(struct jobs_if *jif) |
1242 | if (is_backlogged && cl->concerned_rdc) { | | 1242 | if (is_backlogged && cl->concerned_rdc) { |
1243 | available = result[i] | | 1243 | available = result[i] |
1244 | + cl->service_rate-cl->min_rate_adc; | | 1244 | + cl->service_rate-cl->min_rate_adc; |
1245 | if (available >= -credit) { | | 1245 | if (available >= -credit) { |
1246 | result[i] += credit; | | 1246 | result[i] += credit; |
1247 | credit = 0; | | 1247 | credit = 0; |
1248 | } else { | | 1248 | } else { |
1249 | result[i] -= available; | | 1249 | result[i] -= available; |
1250 | credit += available; | | 1250 | credit += available; |
1251 | } | | 1251 | } |
1252 | } | | 1252 | } |
1253 | } | | 1253 | } |
1254 | return result; | | 1254 | return result; |
| | | 1255 | |
| | | 1256 | fail: free(result, M_DEVBUF); |
| | | 1257 | return NULL; |
1255 | } | | 1258 | } |
1256 | | | 1259 | |
1257 | /* | | 1260 | /* |
1258 | * assign_rate_drops_adc: returns the adjustment needed to | | 1261 | * assign_rate_drops_adc: returns the adjustment needed to |
1259 | * the service rates to meet the absolute delay/rate constraints | | 1262 | * the service rates to meet the absolute delay/rate constraints |
1260 | * (delay/throughput bounds) and drops traffic if need be. | | 1263 | * (delay/throughput bounds) and drops traffic if need be. |
1261 | * see tech. report UVA/T.R. CS-2000-24/CS-2001-21 for more info. | | 1264 | * see tech. report UVA/T.R. CS-2000-24/CS-2001-21 for more info. |
1262 | */ | | 1265 | */ |
1263 | | | 1266 | |
1264 | static int64_t * | | 1267 | static int64_t * |
1265 | assign_rate_drops_adc(struct jobs_if *jif) | | 1268 | assign_rate_drops_adc(struct jobs_if *jif) |
1266 | { | | 1269 | { |
1267 | int64_t *result; | | 1270 | int64_t *result; |
| @@ -1274,39 +1277,39 @@ assign_rate_drops_adc(struct jobs_if *ji | | | @@ -1274,39 +1277,39 @@ assign_rate_drops_adc(struct jobs_if *ji |
1274 | int lowest, highest; | | 1277 | int lowest, highest; |
1275 | int keep_going; | | 1278 | int keep_going; |
1276 | int i; | | 1279 | int i; |
1277 | u_int64_t now, oldest_arv; | | 1280 | u_int64_t now, oldest_arv; |
1278 | int64_t remaining_time; | | 1281 | int64_t remaining_time; |
1279 | struct mbuf* pkt; | | 1282 | struct mbuf* pkt; |
1280 | u_int64_t len; | | 1283 | u_int64_t len; |
1281 | | | 1284 | |
1282 | now = read_machclk(); | | 1285 | now = read_machclk(); |
1283 | oldest_arv = now; | | 1286 | oldest_arv = now; |
1284 | | | 1287 | |
1285 | result = malloc((jif->jif_maxpri+1)*sizeof(int64_t), M_DEVBUF, M_WAITOK); | | 1288 | result = malloc((jif->jif_maxpri+1)*sizeof(int64_t), M_DEVBUF, M_WAITOK); |
1286 | if (result == NULL) | | 1289 | if (result == NULL) |
1287 | return NULL; | | 1290 | goto fail0; |
1288 | c = malloc((jif->jif_maxpri+1)*sizeof(u_int64_t), M_DEVBUF, M_WAITOK); | | 1291 | c = malloc((jif->jif_maxpri+1)*sizeof(u_int64_t), M_DEVBUF, M_WAITOK); |
1289 | if (c == NULL) | | 1292 | if (c == NULL) |
1290 | return NULL; | | 1293 | goto fail1; |
1291 | n = malloc((jif->jif_maxpri+1)*sizeof(u_int64_t), M_DEVBUF, M_WAITOK); | | 1294 | n = malloc((jif->jif_maxpri+1)*sizeof(u_int64_t), M_DEVBUF, M_WAITOK); |
1292 | if (n == NULL) | | 1295 | if (n == NULL) |
1293 | return NULL; | | 1296 | goto fail2; |
1294 | k = malloc((jif->jif_maxpri+1)*sizeof(u_int64_t), M_DEVBUF, M_WAITOK); | | 1297 | k = malloc((jif->jif_maxpri+1)*sizeof(u_int64_t), M_DEVBUF, M_WAITOK); |
1295 | if (k == NULL) | | 1298 | if (k == NULL) |
1296 | return NULL; | | 1299 | goto fail3; |
1297 | available = malloc((jif->jif_maxpri+1)*sizeof(int64_t), M_DEVBUF, M_WAITOK); | | 1300 | available = malloc((jif->jif_maxpri+1)*sizeof(int64_t), M_DEVBUF, M_WAITOK); |
1298 | if (available == NULL) | | 1301 | if (available == NULL) |
1299 | return NULL; | | 1302 | goto fail4; |
1300 | | | 1303 | |
1301 | for (i = 0; i <= jif->jif_maxpri; i++) | | 1304 | for (i = 0; i <= jif->jif_maxpri; i++) |
1302 | result[i] = 0; | | 1305 | result[i] = 0; |
1303 | | | 1306 | |
1304 | keep_going = 1; | | 1307 | keep_going = 1; |
1305 | | | 1308 | |
1306 | for (i = 0; i <= jif->jif_maxpri; i++) { | | 1309 | for (i = 0; i <= jif->jif_maxpri; i++) { |
1307 | cl = jif->jif_classes[i]; | | 1310 | cl = jif->jif_classes[i]; |
1308 | class_exists = (cl != NULL); | | 1311 | class_exists = (cl != NULL); |
1309 | is_backlogged = (class_exists && !qempty(cl->cl_q)); | | 1312 | is_backlogged = (class_exists && !qempty(cl->cl_q)); |
1310 | | | 1313 | |
1311 | if (is_backlogged) { | | 1314 | if (is_backlogged) { |
1312 | if (cl->concerned_adc) { | | 1315 | if (cl->concerned_adc) { |
| @@ -1515,26 +1518,34 @@ assign_rate_drops_adc(struct jobs_if *ji | | | @@ -1515,26 +1518,34 @@ assign_rate_drops_adc(struct jobs_if *ji |
1515 | cl->min_rate_adc = n[i]; /* the best we can give */ | | 1518 | cl->min_rate_adc = n[i]; /* the best we can give */ |
1516 | else { | | 1519 | else { |
1517 | if (class_exists) | | 1520 | if (class_exists) |
1518 | cl->min_rate_adc = 0; | | 1521 | cl->min_rate_adc = 0; |
1519 | } | | 1522 | } |
1520 | } | | 1523 | } |
1521 | | | 1524 | |
1522 | free(c, M_DEVBUF); | | 1525 | free(c, M_DEVBUF); |
1523 | free(n, M_DEVBUF); | | 1526 | free(n, M_DEVBUF); |
1524 | free(k, M_DEVBUF); | | 1527 | free(k, M_DEVBUF); |
1525 | free(available, M_DEVBUF); | | 1528 | free(available, M_DEVBUF); |
1526 | | | 1529 | |
1527 | return (result); | | 1530 | return (result); |
| | | 1531 | |
| | | 1532 | fail5: __unused |
| | | 1533 | free(available, M_DEVBUF); |
| | | 1534 | fail4: free(k, M_DEVBUF); |
| | | 1535 | fail3: free(n, M_DEVBUF); |
| | | 1536 | fail2: free(c, M_DEVBUF); |
| | | 1537 | fail1: free(result, M_DEVBUF); |
| | | 1538 | fail0: return NULL; |
1528 | } | | 1539 | } |
1529 | | | 1540 | |
1530 | /* | | 1541 | /* |
1531 | * update_error: returns the difference between the mean weighted | | 1542 | * update_error: returns the difference between the mean weighted |
1532 | * delay and the weighted delay for each class. if proportional | | 1543 | * delay and the weighted delay for each class. if proportional |
1533 | * delay differentiation is perfectly achieved, it should return | | 1544 | * delay differentiation is perfectly achieved, it should return |
1534 | * zero for each class. | | 1545 | * zero for each class. |
1535 | */ | | 1546 | */ |
1536 | static int64_t * | | 1547 | static int64_t * |
1537 | update_error(struct jobs_if *jif) | | 1548 | update_error(struct jobs_if *jif) |
1538 | { | | 1549 | { |
1539 | int i; | | 1550 | int i; |
1540 | int active_classes, backlogged_classes; | | 1551 | int active_classes, backlogged_classes; |