FreeBSD kernel netgraph code
ng_pipe.c
Go to the documentation of this file.
1/*-
2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
3 *
4 * Copyright (c) 2004-2010 University of Zagreb
5 * Copyright (c) 2007-2008 FreeBSD Foundation
6 *
7 * This software was developed by the University of Zagreb and the
8 * FreeBSD Foundation under sponsorship by the Stichting NLnet and the
9 * FreeBSD Foundation.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * SUCH DAMAGE.
31 *
32 * $FreeBSD$
33 */
34
35/*
36 * This node permits simple traffic shaping by emulating bandwidth
37 * and delay, as well as random packet losses.
38 * The node has two hooks, upper and lower. Traffic flowing from upper to
39 * lower hook is referenced as downstream, and vice versa. Parameters for
40 * both directions can be set separately, except for delay.
41 */
42
43#include <sys/param.h>
44#include <sys/errno.h>
45#include <sys/systm.h>
46#include <sys/kernel.h>
47#include <sys/malloc.h>
48#include <sys/mbuf.h>
49#include <sys/time.h>
50
51#include <vm/uma.h>
52
53#include <net/vnet.h>
54
55#include <netinet/in.h>
56#include <netinet/in_systm.h>
57#include <netinet/ip.h>
58
59#include <netgraph/ng_message.h>
60#include <netgraph/netgraph.h>
61#include <netgraph/ng_parse.h>
62#include <netgraph/ng_pipe.h>
63
64static MALLOC_DEFINE(M_NG_PIPE, "ng_pipe", "ng_pipe");
65
66/* Packet header struct */
67struct ngp_hdr {
68 TAILQ_ENTRY(ngp_hdr) ngp_link; /* next pkt in queue */
69 struct timeval when; /* this packet's due time */
70 struct mbuf *m; /* ptr to the packet data */
71};
73
74/* FIFO queue struct */
75struct ngp_fifo {
76 TAILQ_ENTRY(ngp_fifo) fifo_le; /* list of active queues only */
77 struct p_head packet_head; /* FIFO queue head */
78 u_int32_t hash; /* flow signature */
79 struct timeval vtime; /* virtual time, for WFQ */
80 u_int32_t rr_deficit; /* for DRR */
81 u_int32_t packets; /* # of packets in this queue */
82};
83
84/* Per hook info */
85struct hookinfo {
87 int noqueue; /* bypass any processing */
88 TAILQ_HEAD(, ngp_fifo) fifo_head; /* FIFO queues */
89 TAILQ_HEAD(, ngp_hdr) qout_head; /* delay queue head */
90 struct timeval qin_utime;
91 struct ng_pipe_hookcfg cfg;
92 struct ng_pipe_hookrun run;
94 uint64_t *ber_p; /* loss_p(BER,psize) map */
95};
96
97/* Per node info */
98struct node_priv {
99 u_int64_t delay;
100 u_int32_t overhead;
101 u_int32_t header_offset;
104 struct callout timer;
106};
107typedef struct node_priv *priv_p;
108
109/* Macro for calculating the virtual time for packet dequeueing in WFQ */
110#define FIFO_VTIME_SORT(plen) \
111 if (hinfo->cfg.wfq && hinfo->cfg.bandwidth) { \
112 ngp_f->vtime.tv_usec = now->tv_usec + ((uint64_t) (plen) \
113 + priv->overhead ) * hinfo->run.fifo_queues * \
114 8000000 / hinfo->cfg.bandwidth; \
115 ngp_f->vtime.tv_sec = now->tv_sec + \
116 ngp_f->vtime.tv_usec / 1000000; \
117 ngp_f->vtime.tv_usec = ngp_f->vtime.tv_usec % 1000000; \
118 TAILQ_FOREACH(ngp_f1, &hinfo->fifo_head, fifo_le) \
119 if (ngp_f1->vtime.tv_sec > ngp_f->vtime.tv_sec || \
120 (ngp_f1->vtime.tv_sec == ngp_f->vtime.tv_sec && \
121 ngp_f1->vtime.tv_usec > ngp_f->vtime.tv_usec)) \
122 break; \
123 if (ngp_f1 == NULL) \
124 TAILQ_INSERT_TAIL(&hinfo->fifo_head, ngp_f, fifo_le); \
125 else \
126 TAILQ_INSERT_BEFORE(ngp_f1, ngp_f, fifo_le); \
127 } else \
128 TAILQ_INSERT_TAIL(&hinfo->fifo_head, ngp_f, fifo_le); \
129
130static void parse_cfg(struct ng_pipe_hookcfg *, struct ng_pipe_hookcfg *,
131 struct hookinfo *, priv_p);
132static void pipe_dequeue(struct hookinfo *, struct timeval *);
133static void ngp_callout(node_p, hook_p, void *, int);
134static int ngp_modevent(module_t, int, void *);
135
136/* zone for storing ngp_hdr-s */
137static uma_zone_t ngp_zone;
138
139/* Netgraph methods */
146
147/* Parse type for struct ng_pipe_hookstat */
148static const struct ng_parse_struct_field
153};
154
155/* Parse type for struct ng_pipe_stats */
158static const struct ng_parse_type ng_pipe_stats_type = {
161};
162
163/* Parse type for struct ng_pipe_hookrun */
164static const struct ng_parse_struct_field
166static const struct ng_parse_type ng_pipe_hookrun_type = {
169};
170
171/* Parse type for struct ng_pipe_run */
172static const struct ng_parse_struct_field
174static const struct ng_parse_type ng_pipe_run_type = {
177};
178
179/* Parse type for struct ng_pipe_hookcfg */
180static const struct ng_parse_struct_field
182static const struct ng_parse_type ng_pipe_hookcfg_type = {
185};
186
187/* Parse type for struct ng_pipe_cfg */
188static const struct ng_parse_struct_field
190static const struct ng_parse_type ng_pipe_cfg_type = {
193};
194
195/* List of commands and how to convert arguments to/from ASCII */
196static const struct ng_cmdlist ngp_cmds[] = {
197 {
199 .cmd = NGM_PIPE_GET_STATS,
200 .name = "getstats",
201 .respType = &ng_pipe_stats_type
202 },
203 {
204 .cookie = NGM_PIPE_COOKIE,
205 .cmd = NGM_PIPE_CLR_STATS,
206 .name = "clrstats"
207 },
208 {
209 .cookie = NGM_PIPE_COOKIE,
211 .name = "getclrstats",
212 .respType = &ng_pipe_stats_type
213 },
214 {
215 .cookie = NGM_PIPE_COOKIE,
216 .cmd = NGM_PIPE_GET_RUN,
217 .name = "getrun",
218 .respType = &ng_pipe_run_type
219 },
220 {
221 .cookie = NGM_PIPE_COOKIE,
222 .cmd = NGM_PIPE_GET_CFG,
223 .name = "getcfg",
224 .respType = &ng_pipe_cfg_type
225 },
226 {
227 .cookie = NGM_PIPE_COOKIE,
228 .cmd = NGM_PIPE_SET_CFG,
229 .name = "setcfg",
230 .mesgType = &ng_pipe_cfg_type,
231 },
232 { 0 }
233};
234
235/* Netgraph type descriptor */
238 .name = NG_PIPE_NODE_TYPE,
239 .mod_event = ngp_modevent,
240 .constructor = ngp_constructor,
241 .shutdown = ngp_shutdown,
242 .rcvmsg = ngp_rcvmsg,
243 .newhook = ngp_newhook,
244 .rcvdata = ngp_rcvdata,
245 .disconnect = ngp_disconnect,
246 .cmdlist = ngp_cmds
247};
249
250/* Node constructor */
251static int
253{
254 priv_p priv;
255
256 priv = malloc(sizeof(*priv), M_NG_PIPE, M_ZERO | M_WAITOK);
258
259 /* Mark node as single-threaded */
261
262 ng_callout_init(&priv->timer);
263
264 return (0);
265}
266
267/* Add a hook */
268static int
269ngp_newhook(node_p node, hook_p hook, const char *name)
270{
271 const priv_p priv = NG_NODE_PRIVATE(node);
272 struct hookinfo *hinfo;
273
274 if (strcmp(name, NG_PIPE_HOOK_UPPER) == 0) {
275 bzero(&priv->upper, sizeof(priv->upper));
276 priv->upper.hook = hook;
278 } else if (strcmp(name, NG_PIPE_HOOK_LOWER) == 0) {
279 bzero(&priv->lower, sizeof(priv->lower));
280 priv->lower.hook = hook;
282 } else
283 return (EINVAL);
284
285 /* Load non-zero initial cfg values */
286 hinfo = NG_HOOK_PRIVATE(hook);
287 hinfo->cfg.qin_size_limit = 50;
288 hinfo->cfg.fifo = 1;
289 hinfo->cfg.droptail = 1;
290 TAILQ_INIT(&hinfo->fifo_head);
291 TAILQ_INIT(&hinfo->qout_head);
292 return (0);
293}
294
295/* Receive a control message */
296static int
297ngp_rcvmsg(node_p node, item_p item, hook_p lasthook)
298{
299 const priv_p priv = NG_NODE_PRIVATE(node);
300 struct ng_mesg *resp = NULL;
301 struct ng_mesg *msg, *flow_msg;
302 struct ng_pipe_stats *stats;
303 struct ng_pipe_run *run;
304 struct ng_pipe_cfg *cfg;
305 int error = 0;
306 int prev_down, now_down, cmd;
307
308 NGI_GET_MSG(item, msg);
309 switch (msg->header.typecookie) {
310 case NGM_PIPE_COOKIE:
311 switch (msg->header.cmd) {
315 if (msg->header.cmd != NGM_PIPE_CLR_STATS) {
316 NG_MKRESPONSE(resp, msg,
317 sizeof(*stats), M_NOWAIT);
318 if (resp == NULL) {
319 error = ENOMEM;
320 break;
321 }
322 stats = (struct ng_pipe_stats *) resp->data;
323 bcopy(&priv->upper.stats, &stats->downstream,
324 sizeof(stats->downstream));
325 bcopy(&priv->lower.stats, &stats->upstream,
326 sizeof(stats->upstream));
327 }
328 if (msg->header.cmd != NGM_PIPE_GET_STATS) {
329 bzero(&priv->upper.stats,
330 sizeof(priv->upper.stats));
331 bzero(&priv->lower.stats,
332 sizeof(priv->lower.stats));
333 }
334 break;
335 case NGM_PIPE_GET_RUN:
336 NG_MKRESPONSE(resp, msg, sizeof(*run), M_NOWAIT);
337 if (resp == NULL) {
338 error = ENOMEM;
339 break;
340 }
341 run = (struct ng_pipe_run *) resp->data;
342 bcopy(&priv->upper.run, &run->downstream,
343 sizeof(run->downstream));
344 bcopy(&priv->lower.run, &run->upstream,
345 sizeof(run->upstream));
346 break;
347 case NGM_PIPE_GET_CFG:
348 NG_MKRESPONSE(resp, msg, sizeof(*cfg), M_NOWAIT);
349 if (resp == NULL) {
350 error = ENOMEM;
351 break;
352 }
353 cfg = (struct ng_pipe_cfg *) resp->data;
354 bcopy(&priv->upper.cfg, &cfg->downstream,
355 sizeof(cfg->downstream));
356 bcopy(&priv->lower.cfg, &cfg->upstream,
357 sizeof(cfg->upstream));
358 cfg->delay = priv->delay;
359 cfg->overhead = priv->overhead;
360 cfg->header_offset = priv->header_offset;
361 if (cfg->upstream.bandwidth ==
362 cfg->downstream.bandwidth) {
363 cfg->bandwidth = cfg->upstream.bandwidth;
364 cfg->upstream.bandwidth = 0;
365 cfg->downstream.bandwidth = 0;
366 } else
367 cfg->bandwidth = 0;
368 break;
369 case NGM_PIPE_SET_CFG:
370 cfg = (struct ng_pipe_cfg *) msg->data;
371 if (msg->header.arglen != sizeof(*cfg)) {
372 error = EINVAL;
373 break;
374 }
375
376 if (cfg->delay == -1)
377 priv->delay = 0;
378 else if (cfg->delay > 0 && cfg->delay < 10000000)
379 priv->delay = cfg->delay;
380
381 if (cfg->bandwidth == -1) {
382 priv->upper.cfg.bandwidth = 0;
383 priv->lower.cfg.bandwidth = 0;
384 priv->overhead = 0;
385 } else if (cfg->bandwidth >= 100 &&
386 cfg->bandwidth <= 1000000000) {
387 priv->upper.cfg.bandwidth = cfg->bandwidth;
388 priv->lower.cfg.bandwidth = cfg->bandwidth;
389 if (cfg->bandwidth >= 10000000)
390 priv->overhead = 8+4+12; /* Ethernet */
391 else
392 priv->overhead = 10; /* HDLC */
393 }
394
395 if (cfg->overhead == -1)
396 priv->overhead = 0;
397 else if (cfg->overhead > 0 &&
398 cfg->overhead < MAX_OHSIZE)
399 priv->overhead = cfg->overhead;
400
401 if (cfg->header_offset == -1)
402 priv->header_offset = 0;
403 else if (cfg->header_offset > 0 &&
404 cfg->header_offset < 64)
405 priv->header_offset = cfg->header_offset;
406
407 prev_down = priv->upper.cfg.ber == 1 ||
408 priv->lower.cfg.ber == 1;
409 parse_cfg(&priv->upper.cfg, &cfg->downstream,
410 &priv->upper, priv);
411 parse_cfg(&priv->lower.cfg, &cfg->upstream,
412 &priv->lower, priv);
413 now_down = priv->upper.cfg.ber == 1 ||
414 priv->lower.cfg.ber == 1;
415
416 if (prev_down != now_down) {
417 if (now_down)
419 else
421
422 if (priv->lower.hook != NULL) {
424 cmd, 0, M_NOWAIT);
425 if (flow_msg != NULL)
426 NG_SEND_MSG_HOOK(error, node,
427 flow_msg, priv->lower.hook,
428 0);
429 }
430 if (priv->upper.hook != NULL) {
432 cmd, 0, M_NOWAIT);
433 if (flow_msg != NULL)
434 NG_SEND_MSG_HOOK(error, node,
435 flow_msg, priv->upper.hook,
436 0);
437 }
438 }
439 break;
440 default:
441 error = EINVAL;
442 break;
443 }
444 break;
445 default:
446 error = EINVAL;
447 break;
448 }
449 NG_RESPOND_MSG(error, node, item, resp);
450 NG_FREE_MSG(msg);
451
452 return (error);
453}
454
455static void
456parse_cfg(struct ng_pipe_hookcfg *current, struct ng_pipe_hookcfg *new,
457 struct hookinfo *hinfo, priv_p priv)
458{
459
460 if (new->ber == -1) {
461 current->ber = 0;
462 if (hinfo->ber_p) {
463 free(hinfo->ber_p, M_NG_PIPE);
464 hinfo->ber_p = NULL;
465 }
466 } else if (new->ber >= 1 && new->ber <= 1000000000000) {
467 static const uint64_t one = 0x1000000000000; /* = 2^48 */
468 uint64_t p0, p;
469 uint32_t fsize, i;
470
471 if (hinfo->ber_p == NULL)
472 hinfo->ber_p =
473 malloc((MAX_FSIZE + MAX_OHSIZE) * sizeof(uint64_t),
474 M_NG_PIPE, M_WAITOK);
475 current->ber = new->ber;
476
477 /*
478 * For given BER and each frame size N (in bytes) calculate
479 * the probability P_OK that the frame is clean:
480 *
481 * P_OK(BER,N) = (1 - 1/BER)^(N*8)
482 *
483 * We use a 64-bit fixed-point format with decimal point
484 * positioned between bits 47 and 48.
485 */
486 p0 = one - one / new->ber;
487 p = one;
488 for (fsize = 0; fsize < MAX_FSIZE + MAX_OHSIZE; fsize++) {
489 hinfo->ber_p[fsize] = p;
490 for (i = 0; i < 8; i++)
491 p = (p * (p0 & 0xffff) >> 48) +
492 (p * ((p0 >> 16) & 0xffff) >> 32) +
493 (p * (p0 >> 32) >> 16);
494 }
495 }
496
497 if (new->qin_size_limit == -1)
498 current->qin_size_limit = 0;
499 else if (new->qin_size_limit >= 5)
500 current->qin_size_limit = new->qin_size_limit;
501
502 if (new->qout_size_limit == -1)
503 current->qout_size_limit = 0;
504 else if (new->qout_size_limit >= 5)
505 current->qout_size_limit = new->qout_size_limit;
506
507 if (new->duplicate == -1)
508 current->duplicate = 0;
509 else if (new->duplicate > 0 && new->duplicate <= 50)
510 current->duplicate = new->duplicate;
511
512 if (new->fifo) {
513 current->fifo = 1;
514 current->wfq = 0;
515 current->drr = 0;
516 }
517
518 if (new->wfq) {
519 current->fifo = 0;
520 current->wfq = 1;
521 current->drr = 0;
522 }
523
524 if (new->drr) {
525 current->fifo = 0;
526 current->wfq = 0;
527 /* DRR quantum */
528 if (new->drr >= 32)
529 current->drr = new->drr;
530 else
531 current->drr = 2048; /* default quantum */
532 }
533
534 if (new->droptail) {
535 current->droptail = 1;
536 current->drophead = 0;
537 }
538
539 if (new->drophead) {
540 current->droptail = 0;
541 current->drophead = 1;
542 }
543
544 if (new->bandwidth == -1) {
545 current->bandwidth = 0;
546 current->fifo = 1;
547 current->wfq = 0;
548 current->drr = 0;
549 } else if (new->bandwidth >= 100 && new->bandwidth <= 1000000000)
550 current->bandwidth = new->bandwidth;
551
552 if (current->bandwidth | priv->delay |
553 current->duplicate | current->ber)
554 hinfo->noqueue = 0;
555 else
556 hinfo->noqueue = 1;
557}
558
559/*
560 * Compute a hash signature for a packet. This function suffers from the
561 * NIH sindrome, so probably it would be wise to look around what other
562 * folks have found out to be a good and efficient IP hash function...
563 */
564static int
565ip_hash(struct mbuf *m, int offset)
566{
567 u_int64_t i;
568 struct ip *ip = (struct ip *)(mtod(m, u_char *) + offset);
569
570 if (m->m_len < sizeof(struct ip) + offset ||
571 ip->ip_v != 4 || ip->ip_hl << 2 != sizeof(struct ip))
572 return 0;
573
574 i = ((u_int64_t) ip->ip_src.s_addr ^
575 ((u_int64_t) ip->ip_src.s_addr << 13) ^
576 ((u_int64_t) ip->ip_dst.s_addr << 7) ^
577 ((u_int64_t) ip->ip_dst.s_addr << 19));
578 return (i ^ (i >> 32));
579}
580
581/*
582 * Receive data on a hook - both in upstream and downstream direction.
583 * We put the frame on the inbound queue, and try to initiate dequeuing
584 * sequence immediately. If inbound queue is full, discard one frame
585 * depending on dropping policy (from the head or from the tail of the
586 * queue).
587 */
588static int
590{
591 struct hookinfo *const hinfo = NG_HOOK_PRIVATE(hook);
593 struct timeval uuptime;
594 struct timeval *now = &uuptime;
595 struct ngp_fifo *ngp_f = NULL, *ngp_f1;
596 struct ngp_hdr *ngp_h = NULL;
597 struct mbuf *m;
598 int hash, plen;
599 int error = 0;
600
601 /*
602 * Shortcut from inbound to outbound hook when neither of
603 * bandwidth, delay, BER or duplication probability is
604 * configured, nor we have queued frames to drain.
605 */
606 if (hinfo->run.qin_frames == 0 && hinfo->run.qout_frames == 0 &&
607 hinfo->noqueue) {
608 struct hookinfo *dest;
609 if (hinfo == &priv->lower)
610 dest = &priv->upper;
611 else
612 dest = &priv->lower;
613
614 /* Send the frame. */
615 plen = NGI_M(item)->m_pkthdr.len;
616 NG_FWD_ITEM_HOOK(error, item, dest->hook);
617
618 /* Update stats. */
619 if (error) {
620 hinfo->stats.out_disc_frames++;
621 hinfo->stats.out_disc_octets += plen;
622 } else {
623 hinfo->stats.fwd_frames++;
624 hinfo->stats.fwd_octets += plen;
625 }
626
627 return (error);
628 }
629
630 microuptime(now);
631
632 /*
633 * If this was an empty queue, update service deadline time.
634 */
635 if (hinfo->run.qin_frames == 0) {
636 struct timeval *when = &hinfo->qin_utime;
637 if (when->tv_sec < now->tv_sec || (when->tv_sec == now->tv_sec
638 && when->tv_usec < now->tv_usec)) {
639 when->tv_sec = now->tv_sec;
640 when->tv_usec = now->tv_usec;
641 }
642 }
643
644 /* Populate the packet header */
645 ngp_h = uma_zalloc(ngp_zone, M_NOWAIT);
646 KASSERT((ngp_h != NULL), ("ngp_h zalloc failed (1)"));
647 NGI_GET_M(item, m);
648 KASSERT(m != NULL, ("NGI_GET_M failed"));
649 ngp_h->m = m;
650 NG_FREE_ITEM(item);
651
652 if (hinfo->cfg.fifo)
653 hash = 0; /* all packets go into a single FIFO queue */
654 else
655 hash = ip_hash(m, priv->header_offset);
656
657 /* Find the appropriate FIFO queue for the packet and enqueue it*/
658 TAILQ_FOREACH(ngp_f, &hinfo->fifo_head, fifo_le)
659 if (hash == ngp_f->hash)
660 break;
661 if (ngp_f == NULL) {
662 ngp_f = uma_zalloc(ngp_zone, M_NOWAIT);
663 KASSERT(ngp_h != NULL, ("ngp_h zalloc failed (2)"));
664 TAILQ_INIT(&ngp_f->packet_head);
665 ngp_f->hash = hash;
666 ngp_f->packets = 1;
667 ngp_f->rr_deficit = hinfo->cfg.drr; /* DRR quantum */
668 hinfo->run.fifo_queues++;
669 TAILQ_INSERT_TAIL(&ngp_f->packet_head, ngp_h, ngp_link);
670 FIFO_VTIME_SORT(m->m_pkthdr.len);
671 } else {
672 TAILQ_INSERT_TAIL(&ngp_f->packet_head, ngp_h, ngp_link);
673 ngp_f->packets++;
674 }
675 hinfo->run.qin_frames++;
676 hinfo->run.qin_octets += m->m_pkthdr.len;
677
678 /* Discard a frame if inbound queue limit has been reached */
679 if (hinfo->run.qin_frames > hinfo->cfg.qin_size_limit) {
680 struct mbuf *m1;
681 int longest = 0;
682
683 /* Find the longest queue */
684 TAILQ_FOREACH(ngp_f1, &hinfo->fifo_head, fifo_le)
685 if (ngp_f1->packets > longest) {
686 longest = ngp_f1->packets;
687 ngp_f = ngp_f1;
688 }
689
690 /* Drop a frame from the queue head/tail, depending on cfg */
691 if (hinfo->cfg.drophead)
692 ngp_h = TAILQ_FIRST(&ngp_f->packet_head);
693 else
694 ngp_h = TAILQ_LAST(&ngp_f->packet_head, p_head);
695 TAILQ_REMOVE(&ngp_f->packet_head, ngp_h, ngp_link);
696 m1 = ngp_h->m;
697 uma_zfree(ngp_zone, ngp_h);
698 hinfo->run.qin_octets -= m1->m_pkthdr.len;
699 hinfo->stats.in_disc_octets += m1->m_pkthdr.len;
700 m_freem(m1);
701 if (--(ngp_f->packets) == 0) {
702 TAILQ_REMOVE(&hinfo->fifo_head, ngp_f, fifo_le);
703 uma_zfree(ngp_zone, ngp_f);
704 hinfo->run.fifo_queues--;
705 }
706 hinfo->run.qin_frames--;
707 hinfo->stats.in_disc_frames++;
708 }
709
710 /*
711 * Try to start the dequeuing process immediately.
712 */
713 pipe_dequeue(hinfo, now);
714
715 return (0);
716}
717
718/*
719 * Dequeueing sequence - we basically do the following:
720 * 1) Try to extract the frame from the inbound (bandwidth) queue;
721 * 2) In accordance to BER specified, discard the frame randomly;
722 * 3) If the frame survives BER, prepend it with delay info and move it
723 * to outbound (delay) queue;
724 * 4) Loop to 2) until bandwidth quota for this timeslice is reached, or
725 * inbound queue is flushed completely;
726 * 5) Dequeue frames from the outbound queue and send them downstream until
727 * outbound queue is flushed completely, or the next frame in the queue
728 * is not due to be dequeued yet
729 */
730static void
731pipe_dequeue(struct hookinfo *hinfo, struct timeval *now) {
732 static uint64_t rand, oldrand;
733 const node_p node = NG_HOOK_NODE(hinfo->hook);
734 const priv_p priv = NG_NODE_PRIVATE(node);
735 struct hookinfo *dest;
736 struct ngp_fifo *ngp_f, *ngp_f1;
737 struct ngp_hdr *ngp_h;
738 struct timeval *when;
739 struct mbuf *m;
740 int plen, error = 0;
741
742 /* Which one is the destination hook? */
743 if (hinfo == &priv->lower)
744 dest = &priv->upper;
745 else
746 dest = &priv->lower;
747
748 /* Bandwidth queue processing */
749 while ((ngp_f = TAILQ_FIRST(&hinfo->fifo_head))) {
750 when = &hinfo->qin_utime;
751 if (when->tv_sec > now->tv_sec || (when->tv_sec == now->tv_sec
752 && when->tv_usec > now->tv_usec))
753 break;
754
755 ngp_h = TAILQ_FIRST(&ngp_f->packet_head);
756 m = ngp_h->m;
757
758 /* Deficit Round Robin (DRR) processing */
759 if (hinfo->cfg.drr) {
760 if (ngp_f->rr_deficit >= m->m_pkthdr.len) {
761 ngp_f->rr_deficit -= m->m_pkthdr.len;
762 } else {
763 ngp_f->rr_deficit += hinfo->cfg.drr;
764 TAILQ_REMOVE(&hinfo->fifo_head, ngp_f, fifo_le);
765 TAILQ_INSERT_TAIL(&hinfo->fifo_head,
766 ngp_f, fifo_le);
767 continue;
768 }
769 }
770
771 /*
772 * Either create a duplicate and pass it on, or dequeue
773 * the original packet...
774 */
775 if (hinfo->cfg.duplicate &&
776 random() % 100 <= hinfo->cfg.duplicate) {
777 ngp_h = uma_zalloc(ngp_zone, M_NOWAIT);
778 KASSERT(ngp_h != NULL, ("ngp_h zalloc failed (3)"));
779 m = m_dup(m, M_NOWAIT);
780 KASSERT(m != NULL, ("m_dup failed"));
781 ngp_h->m = m;
782 } else {
783 TAILQ_REMOVE(&ngp_f->packet_head, ngp_h, ngp_link);
784 hinfo->run.qin_frames--;
785 hinfo->run.qin_octets -= m->m_pkthdr.len;
786 ngp_f->packets--;
787 }
788
789 /* Calculate the serialization delay */
790 if (hinfo->cfg.bandwidth) {
791 hinfo->qin_utime.tv_usec +=
792 ((uint64_t) m->m_pkthdr.len + priv->overhead ) *
793 8000000 / hinfo->cfg.bandwidth;
794 hinfo->qin_utime.tv_sec +=
795 hinfo->qin_utime.tv_usec / 1000000;
796 hinfo->qin_utime.tv_usec =
797 hinfo->qin_utime.tv_usec % 1000000;
798 }
799 when = &ngp_h->when;
800 when->tv_sec = hinfo->qin_utime.tv_sec;
801 when->tv_usec = hinfo->qin_utime.tv_usec;
802
803 /* Sort / rearrange inbound queues */
804 if (ngp_f->packets) {
805 if (hinfo->cfg.wfq) {
806 TAILQ_REMOVE(&hinfo->fifo_head, ngp_f, fifo_le);
807 FIFO_VTIME_SORT(TAILQ_FIRST(
808 &ngp_f->packet_head)->m->m_pkthdr.len)
809 }
810 } else {
811 TAILQ_REMOVE(&hinfo->fifo_head, ngp_f, fifo_le);
812 uma_zfree(ngp_zone, ngp_f);
813 hinfo->run.fifo_queues--;
814 }
815
816 /* Randomly discard the frame, according to BER setting */
817 if (hinfo->cfg.ber) {
818 oldrand = rand;
819 rand = random();
820 if (((oldrand ^ rand) << 17) >=
821 hinfo->ber_p[priv->overhead + m->m_pkthdr.len]) {
822 hinfo->stats.out_disc_frames++;
823 hinfo->stats.out_disc_octets += m->m_pkthdr.len;
824 uma_zfree(ngp_zone, ngp_h);
825 m_freem(m);
826 continue;
827 }
828 }
829
830 /* Discard frame if outbound queue size limit exceeded */
831 if (hinfo->cfg.qout_size_limit &&
832 hinfo->run.qout_frames>=hinfo->cfg.qout_size_limit) {
833 hinfo->stats.out_disc_frames++;
834 hinfo->stats.out_disc_octets += m->m_pkthdr.len;
835 uma_zfree(ngp_zone, ngp_h);
836 m_freem(m);
837 continue;
838 }
839
840 /* Calculate the propagation delay */
841 when->tv_usec += priv->delay;
842 when->tv_sec += when->tv_usec / 1000000;
843 when->tv_usec = when->tv_usec % 1000000;
844
845 /* Put the frame into the delay queue */
846 TAILQ_INSERT_TAIL(&hinfo->qout_head, ngp_h, ngp_link);
847 hinfo->run.qout_frames++;
848 hinfo->run.qout_octets += m->m_pkthdr.len;
849 }
850
851 /* Delay queue processing */
852 while ((ngp_h = TAILQ_FIRST(&hinfo->qout_head))) {
853 when = &ngp_h->when;
854 m = ngp_h->m;
855 if (when->tv_sec > now->tv_sec ||
856 (when->tv_sec == now->tv_sec &&
857 when->tv_usec > now->tv_usec))
858 break;
859
860 /* Update outbound queue stats */
861 plen = m->m_pkthdr.len;
862 hinfo->run.qout_frames--;
863 hinfo->run.qout_octets -= plen;
864
865 /* Dequeue the packet from qout */
866 TAILQ_REMOVE(&hinfo->qout_head, ngp_h, ngp_link);
867 uma_zfree(ngp_zone, ngp_h);
868
869 NG_SEND_DATA(error, dest->hook, m, meta);
870 if (error) {
871 hinfo->stats.out_disc_frames++;
872 hinfo->stats.out_disc_octets += plen;
873 } else {
874 hinfo->stats.fwd_frames++;
875 hinfo->stats.fwd_octets += plen;
876 }
877 }
878
879 if ((hinfo->run.qin_frames != 0 || hinfo->run.qout_frames != 0) &&
880 !priv->timer_scheduled) {
881 ng_callout(&priv->timer, node, NULL, 1, ngp_callout, NULL, 0);
882 priv->timer_scheduled = 1;
883 }
884}
885
886/*
887 * This routine is called on every clock tick. We poll connected hooks
888 * for queued frames by calling pipe_dequeue().
889 */
890static void
891ngp_callout(node_p node, hook_p hook, void *arg1, int arg2)
892{
893 const priv_p priv = NG_NODE_PRIVATE(node);
894 struct timeval now;
895
896 priv->timer_scheduled = 0;
897 microuptime(&now);
898 if (priv->upper.hook != NULL)
899 pipe_dequeue(&priv->upper, &now);
900 if (priv->lower.hook != NULL)
901 pipe_dequeue(&priv->lower, &now);
902}
903
904/*
905 * Shutdown processing
906 *
907 * This is tricky. If we have both a lower and upper hook, then we
908 * probably want to extricate ourselves and leave the two peers
909 * still linked to each other. Otherwise we should just shut down as
910 * a normal node would.
911 */
912static int
914{
915 const priv_p priv = NG_NODE_PRIVATE(node);
916
917 if (priv->timer_scheduled)
918 ng_uncallout(&priv->timer, node);
919 if (priv->lower.hook && priv->upper.hook)
920 ng_bypass(priv->lower.hook, priv->upper.hook);
921 else {
922 if (priv->upper.hook != NULL)
924 if (priv->lower.hook != NULL)
926 }
927 NG_NODE_UNREF(node);
928 free(priv, M_NG_PIPE);
929 return (0);
930}
931
932/*
933 * Hook disconnection
934 */
935static int
937{
938 struct hookinfo *const hinfo = NG_HOOK_PRIVATE(hook);
939 struct ngp_fifo *ngp_f;
940 struct ngp_hdr *ngp_h;
941
942 KASSERT(hinfo != NULL, ("%s: null info", __FUNCTION__));
943 hinfo->hook = NULL;
944
945 /* Flush all fifo queues associated with the hook */
946 while ((ngp_f = TAILQ_FIRST(&hinfo->fifo_head))) {
947 while ((ngp_h = TAILQ_FIRST(&ngp_f->packet_head))) {
948 TAILQ_REMOVE(&ngp_f->packet_head, ngp_h, ngp_link);
949 m_freem(ngp_h->m);
950 uma_zfree(ngp_zone, ngp_h);
951 }
952 TAILQ_REMOVE(&hinfo->fifo_head, ngp_f, fifo_le);
953 uma_zfree(ngp_zone, ngp_f);
954 }
955
956 /* Flush the delay queue */
957 while ((ngp_h = TAILQ_FIRST(&hinfo->qout_head))) {
958 TAILQ_REMOVE(&hinfo->qout_head, ngp_h, ngp_link);
959 m_freem(ngp_h->m);
960 uma_zfree(ngp_zone, ngp_h);
961 }
962
963 /* Release the packet loss probability table (BER) */
964 if (hinfo->ber_p)
965 free(hinfo->ber_p, M_NG_PIPE);
966
967 return (0);
968}
969
970static int
971ngp_modevent(module_t mod, int type, void *unused)
972{
973 int error = 0;
974
975 switch (type) {
976 case MOD_LOAD:
977 ngp_zone = uma_zcreate("ng_pipe", max(sizeof(struct ngp_hdr),
978 sizeof (struct ngp_fifo)), NULL, NULL, NULL, NULL,
979 UMA_ALIGN_PTR, 0);
980 if (ngp_zone == NULL)
981 panic("ng_pipe: couldn't allocate descriptor zone");
982 break;
983 case MOD_UNLOAD:
984 uma_zdestroy(ngp_zone);
985 break;
986 default:
987 error = EOPNOTSUPP;
988 break;
989 }
990
991 return (error);
992}
uint32_t packets
Definition: netflow.h:5
#define NGI_M(i)
Definition: netgraph.h:833
#define NG_HOOK_NODE(hook)
Definition: netgraph.h:339
int ng_rcvmsg_t(node_p node, item_p item, hook_p lasthook)
Definition: netgraph.h:105
#define NG_FWD_ITEM_HOOK(error, item, hook)
Definition: netgraph.h:898
int ng_disconnect_t(hook_p hook)
Definition: netgraph.h:107
#define NG_NODE_SET_PRIVATE(node, val)
Definition: netgraph.h:608
#define NG_RESPOND_MSG(error, here, item, resp)
Definition: netgraph.h:1025
int ng_rmhook_self(hook_p hook)
Definition: ng_base.c:1631
#define NG_NODE_FORCE_WRITER(node)
Definition: netgraph.h:612
#define NG_NODE_UNREF(node)
Definition: netgraph.h:607
#define NG_HOOK_SET_PRIVATE(hook, val)
Definition: netgraph.h:333
#define ng_callout_init(c)
Definition: netgraph.h:1168
int ng_rcvdata_t(hook_p hook, item_p item)
Definition: netgraph.h:106
int ng_shutdown_t(node_p node)
Definition: netgraph.h:101
int ng_uncallout(struct callout *c, node_p node)
Definition: ng_base.c:3840
#define NG_FREE_ITEM(item)
Definition: netgraph.h:847
int ng_constructor_t(node_p node)
Definition: netgraph.h:99
#define NGI_GET_M(i, m)
Definition: netgraph.h:852
#define NG_FREE_MSG(msg)
Definition: netgraph.h:938
#define NG_ABI_VERSION
Definition: netgraph.h:77
#define NG_SEND_DATA(error, hook, m, x)
Definition: netgraph.h:935
int ng_bypass(hook_p hook1, hook_p hook2)
Definition: ng_base.c:1241
#define NGI_GET_MSG(i, m)
Definition: netgraph.h:858
#define NG_NODE_PRIVATE(node)
Definition: netgraph.h:609
#define NG_SEND_MSG_HOOK(error, here, msg, hook, retaddr)
Definition: netgraph.h:958
int ng_callout(struct callout *c, node_p node, hook_p hook, int ticks, ng_item_fn *fn, void *arg1, int arg2)
Definition: ng_base.c:3789
int ng_newhook_t(node_p node, hook_p hook, const char *name)
Definition: netgraph.h:102
#define NG_HOOK_PRIVATE(hook)
Definition: netgraph.h:336
u_int8_t type
#define NG_MKRESPONSE(rsp, msg, len, how)
Definition: ng_message.h:396
#define NGM_LINK_IS_DOWN
Definition: ng_message.h:156
#define NGM_FLOW_COOKIE
Definition: ng_message.h:152
#define NGM_LINK_IS_UP
Definition: ng_message.h:155
#define NG_MKMESSAGE(msg, cookie, cmdid, len, how)
Definition: ng_message.h:378
const struct ng_parse_type ng_parse_struct_type
Definition: ng_parse.c:222
static ng_constructor_t ngp_constructor
Definition: ng_pipe.c:140
static const struct ng_parse_struct_field ng_pipe_hookrun_type_fields[]
Definition: ng_pipe.c:165
static ng_newhook_t ngp_newhook
Definition: ng_pipe.c:143
static const struct ng_parse_type ng_pipe_hookrun_type
Definition: ng_pipe.c:166
static const struct ng_parse_struct_field ng_pipe_run_type_fields[]
Definition: ng_pipe.c:173
static void pipe_dequeue(struct hookinfo *, struct timeval *)
Definition: ng_pipe.c:731
static const struct ng_parse_type ng_pipe_run_type
Definition: ng_pipe.c:174
static void parse_cfg(struct ng_pipe_hookcfg *, struct ng_pipe_hookcfg *, struct hookinfo *, priv_p)
Definition: ng_pipe.c:456
static const struct ng_parse_type ng_pipe_hookcfg_type
Definition: ng_pipe.c:182
static const struct ng_parse_type ng_pipe_cfg_type
Definition: ng_pipe.c:190
static ng_disconnect_t ngp_disconnect
Definition: ng_pipe.c:145
static MALLOC_DEFINE(M_NG_PIPE, "ng_pipe", "ng_pipe")
struct node_priv * priv_p
Definition: ng_pipe.c:107
static const struct ng_parse_struct_field ng_pipe_stats_type_fields[]
Definition: ng_pipe.c:156
TAILQ_HEAD(p_head, ngp_hdr)
static const struct ng_parse_struct_field ng_pipe_cfg_type_fields[]
Definition: ng_pipe.c:189
static ng_rcvdata_t ngp_rcvdata
Definition: ng_pipe.c:144
static struct ng_type ng_pipe_typestruct
Definition: ng_pipe.c:236
static const struct ng_parse_struct_field ng_pipe_hookstat_type_fields[]
Definition: ng_pipe.c:149
static int ip_hash(struct mbuf *m, int offset)
Definition: ng_pipe.c:565
static ng_shutdown_t ngp_shutdown
Definition: ng_pipe.c:142
static const struct ng_cmdlist ngp_cmds[]
Definition: ng_pipe.c:196
#define FIFO_VTIME_SORT(plen)
Definition: ng_pipe.c:110
static uma_zone_t ngp_zone
Definition: ng_pipe.c:137
static void ngp_callout(node_p, hook_p, void *, int)
Definition: ng_pipe.c:891
static ng_rcvmsg_t ngp_rcvmsg
Definition: ng_pipe.c:141
static int ngp_modevent(module_t, int, void *)
Definition: ng_pipe.c:971
static const struct ng_parse_type ng_pipe_stats_type
Definition: ng_pipe.c:158
static const struct ng_parse_type ng_pipe_hookstat_type
Definition: ng_pipe.c:150
NETGRAPH_INIT(pipe, &ng_pipe_typestruct)
static const struct ng_parse_struct_field ng_pipe_hookcfg_type_fields[]
Definition: ng_pipe.c:181
#define MAX_OHSIZE
Definition: ng_pipe.h:47
#define NG_PIPE_HOOK_LOWER
Definition: ng_pipe.h:44
#define NG_PIPE_HOOKSTAT_INFO
Definition: ng_pipe.h:60
@ NGM_PIPE_GET_CFG
Definition: ng_pipe.h:171
@ NGM_PIPE_GET_STATS
Definition: ng_pipe.h:167
@ NGM_PIPE_CLR_STATS
Definition: ng_pipe.h:168
@ NGM_PIPE_SET_CFG
Definition: ng_pipe.h:172
@ NGM_PIPE_GET_RUN
Definition: ng_pipe.h:170
@ NGM_PIPE_GETCLR_STATS
Definition: ng_pipe.h:169
#define NG_PIPE_NODE_TYPE
Definition: ng_pipe.h:39
#define NG_PIPE_HOOKCFG_INFO
Definition: ng_pipe.h:130
#define MAX_FSIZE
Definition: ng_pipe.h:46
#define NG_PIPE_HOOK_UPPER
Definition: ng_pipe.h:43
#define NG_PIPE_HOOKRUN_INFO
Definition: ng_pipe.h:93
#define NG_PIPE_STATS_INFO(hstype)
Definition: ng_pipe.h:77
#define NG_PIPE_CFG_INFO(hstype)
Definition: ng_pipe.h:155
#define NG_PIPE_RUN_INFO(hstype)
Definition: ng_pipe.h:109
#define NGM_PIPE_COOKIE
Definition: ng_pipe.h:40
char *const name
Definition: ng_ppp.c:261
cmd
Definition: ng_pppoe.h:74
typedef TAILQ_ENTRY(sscfu_sig) sscfu_sigq_link_t
hook_p dest
Definition: ng_car.c:62
hook_p hook
Definition: ng_car.c:61
struct ng_car_hookstats stats
Definition: ng_car.c:69
int noqueue
Definition: ng_pipe.c:87
u_int32_t cookie
Definition: netgraph.h:1056
u_int32_t arglen
Definition: ng_message.h:62
u_int32_t typecookie
Definition: ng_message.h:66
struct ng_mesg::ng_msghdr header
char data[]
Definition: ng_message.h:69
struct ng_pipe_hookcfg upstream
Definition: ng_pipe.h:151
u_int64_t bandwidth
Definition: ng_pipe.h:146
u_int32_t header_offset
Definition: ng_pipe.h:148
struct ng_pipe_hookcfg downstream
Definition: ng_pipe.h:150
u_int64_t delay
Definition: ng_pipe.h:147
u_int32_t overhead
Definition: ng_pipe.h:149
u_int64_t bandwidth
Definition: ng_pipe.h:117
u_int32_t droptail
Definition: ng_pipe.h:125
u_int32_t drr
Definition: ng_pipe.h:123
u_int32_t wfq
Definition: ng_pipe.h:124
u_int32_t fifo
Definition: ng_pipe.h:122
u_int64_t ber
Definition: ng_pipe.h:118
u_int32_t duplicate
Definition: ng_pipe.h:121
u_int32_t drophead
Definition: ng_pipe.h:126
u_int32_t qin_size_limit
Definition: ng_pipe.h:119
u_int32_t qout_size_limit
Definition: ng_pipe.h:120
struct ng_pipe_hookrun upstream
Definition: ng_pipe.h:105
struct ng_pipe_hookrun downstream
Definition: ng_pipe.h:104
u_int32_t version
Definition: netgraph.h:1077
u_int64_t delay
Definition: ng_pipe.c:99
u_int32_t overhead
Definition: ng_pipe.c:100
struct hookinfo lower
Definition: ng_pipe.c:102
int timer_scheduled
Definition: ng_pipe.c:105
struct callout timer
Definition: ng_pipe.c:104
u_int32_t header_offset
Definition: ng_pipe.c:101
struct hookinfo upper
Definition: ng_pipe.c:103
Definition: ng_sscfu.c:66
hook_p lower
Definition: ng_sscfu.c:68
hook_p upper
Definition: ng_sscfu.c:67
Definition: ng_sscop.c:74