+
+ pipe_nr &= 0xffff ;
+
+ lck_mtx_lock(dn_mutex);
+
+ /*
+ * This is a dummynet rule, so we expect an O_PIPE or O_QUEUE rule.
+ */
+ fs = locate_flowset(pipe_nr, fwa->rule);
+ if (fs == NULL)
+ goto dropit ; /* this queue/pipe does not exist! */
+ pipe = fs->pipe ;
+ if (pipe == NULL) { /* must be a queue, try find a matching pipe */
+ for (pipe = all_pipes; pipe && pipe->pipe_nr != fs->parent_nr;
+ pipe = pipe->next)
+ ;
+ if (pipe != NULL)
+ fs->pipe = pipe ;
+ else {
+ printf("dummynet: no pipe %d for queue %d, drop pkt\n",
+ fs->parent_nr, fs->fs_nr);
+ goto dropit ;
+ }
+ }
+ q = find_queue(fs, &(fwa->f_id));
+ if ( q == NULL )
+ goto dropit ; /* cannot allocate queue */
+ /*
+ * update statistics, then check reasons to drop pkt
+ */
+ q->tot_bytes += len ;
+ q->tot_pkts++ ;
+ if ( fs->plr && random() < fs->plr )
+ goto dropit ; /* random pkt drop */
+ if ( fs->flags_fs & DN_QSIZE_IS_BYTES) {
+ if (q->len_bytes > fs->qsize)
+ goto dropit ; /* queue size overflow */
+ } else {
+ if (q->len >= fs->qsize)
+ goto dropit ; /* queue count overflow */
+ }
+ if ( fs->flags_fs & DN_IS_RED && red_drops(fs, q, len) )
+ goto dropit ;
+
+ /* XXX expensive to zero, see if we can remove it*/
+ mtag = m_tag_alloc(KERNEL_MODULE_TAG_ID, KERNEL_TAG_TYPE_DUMMYNET,
+ sizeof(struct dn_pkt_tag), M_NOWAIT|M_ZERO);
+ if ( mtag == NULL )
+ goto dropit ; /* cannot allocate packet header */
+ m_tag_prepend(m, mtag); /* attach to mbuf chain */
+
+ pkt = (struct dn_pkt_tag *)(mtag+1);
+ /* ok, i can handle the pkt now... */
+ /* build and enqueue packet + parameters */
+ pkt->rule = fwa->rule ;
+ pkt->dn_dir = dir ;
+
+ pkt->ifp = fwa->oif;
+ if (dir == DN_TO_IP_OUT) {
+ /*
+ * We need to copy *ro because for ICMP pkts (and maybe others)
+ * the caller passed a pointer into the stack; dst might also be
+ * a pointer into *ro so it needs to be updated.
+ */
+ lck_mtx_lock(rt_mtx);
+ pkt->ro = *(fwa->ro);
+ if (fwa->ro->ro_rt)
+ fwa->ro->ro_rt->rt_refcnt++ ;
+ if (fwa->dst == (struct sockaddr_in *)&fwa->ro->ro_dst) /* dst points into ro */
+ fwa->dst = (struct sockaddr_in *)&(pkt->ro.ro_dst) ;
+ lck_mtx_unlock(rt_mtx);
+
+ pkt->dn_dst = fwa->dst;
+ pkt->flags = fwa->flags;
+ }
+ if (q->head == NULL)
+ q->head = m;
+ else
+ q->tail->m_nextpkt = m;
+ q->tail = m;
+ q->len++;
+ q->len_bytes += len ;
+
+ if ( q->head != m ) /* flow was not idle, we are done */
+ goto done;
+ /*
+ * If we reach this point the flow was previously idle, so we need
+ * to schedule it. This involves different actions for fixed-rate or
+ * WF2Q queues.
+ */
+ if (is_pipe) {
+ /*
+ * Fixed-rate queue: just insert into the ready_heap.
+ */
+ dn_key t = 0 ;
+ if (pipe->bandwidth)
+ t = SET_TICKS(m, q, pipe);
+ q->sched_time = curr_time ;
+ if (t == 0) /* must process it now */
+ ready_event( q );
+ else
+ heap_insert(&ready_heap, curr_time + t , q );
+ } else {
+ /*
+ * WF2Q. First, compute start time S: if the flow was idle (S=F+1)
+ * set S to the virtual time V for the controlling pipe, and update
+ * the sum of weights for the pipe; otherwise, remove flow from
+ * idle_heap and set S to max(F,V).
+ * Second, compute finish time F = S + len/weight.
+ * Third, if pipe was idle, update V=max(S, V).
+ * Fourth, count one more backlogged flow.
+ */
+ if (DN_KEY_GT(q->S, q->F)) { /* means timestamps are invalid */
+ q->S = pipe->V ;
+ pipe->sum += fs->weight ; /* add weight of new queue */
+ } else {
+ heap_extract(&(pipe->idle_heap), q);
+ q->S = MAX64(q->F, pipe->V ) ;
+ }
+ q->F = q->S + ( len<<MY_M )/(u_int64_t) fs->weight;
+
+ if (pipe->not_eligible_heap.elements == 0 &&
+ pipe->scheduler_heap.elements == 0)
+ pipe->V = MAX64 ( q->S, pipe->V );
+ fs->backlogged++ ;
+ /*
+ * Look at eligibility. A flow is not eligibile if S>V (when
+ * this happens, it means that there is some other flow already
+ * scheduled for the same pipe, so the scheduler_heap cannot be
+ * empty). If the flow is not eligible we just store it in the
+ * not_eligible_heap. Otherwise, we store in the scheduler_heap
+ * and possibly invoke ready_event_wfq() right now if there is
+ * leftover credit.
+ * Note that for all flows in scheduler_heap (SCH), S_i <= V,
+ * and for all flows in not_eligible_heap (NEH), S_i > V .
+ * So when we need to compute max( V, min(S_i) ) forall i in SCH+NEH,
+ * we only need to look into NEH.
+ */
+ if (DN_KEY_GT(q->S, pipe->V) ) { /* not eligible */
+ if (pipe->scheduler_heap.elements == 0)
+ printf("dummynet: ++ ouch! not eligible but empty scheduler!\n");
+ heap_insert(&(pipe->not_eligible_heap), q->S, q);
+ } else {
+ heap_insert(&(pipe->scheduler_heap), q->F, q);
+ if (pipe->numbytes >= 0) { /* pipe is idle */
+ if (pipe->scheduler_heap.elements != 1)
+ printf("dummynet: OUCH! pipe should have been idle!\n");
+ DPRINTF(("dummynet: waking up pipe %d at %d\n",
+ pipe->pipe_nr, (int)(q->F >> MY_M)));
+ pipe->sched_time = curr_time ;
+ ready_event_wfq(pipe);
+ }
+ }
+ }
+done:
+ lck_mtx_unlock(dn_mutex);
+ return 0;
+
+dropit:
+ if (q)
+ q->drops++ ;
+ lck_mtx_unlock(dn_mutex);
+ m_freem(m);
+ return ( (fs && (fs->flags_fs & DN_NOERROR)) ? 0 : ENOBUFS);
+}
+
+/*
+ * Below, the rtfree is only needed when (pkt->dn_dir == DN_TO_IP_OUT)
+ * Doing this would probably save us the initial bzero of dn_pkt
+ */
+#define DN_FREE_PKT(_m) do { \
+ struct m_tag *tag = m_tag_locate(m, KERNEL_MODULE_TAG_ID, KERNEL_TAG_TYPE_DUMMYNET, NULL); \
+ if (tag) { \
+ struct dn_pkt_tag *n = (struct dn_pkt_tag *)(tag+1); \
+ if (n->ro.ro_rt) \
+ rtfree(n->ro.ro_rt); \
+ } \
+ m_tag_delete(_m, tag); \
+ m_freem(_m); \
+} while (0)
+
+/*
+ * Dispose all packets and flow_queues on a flow_set.
+ * If all=1, also remove red lookup table and other storage,
+ * including the descriptor itself.
+ * For the one in dn_pipe MUST also cleanup ready_heap...
+ */
+static void
+purge_flow_set(struct dn_flow_set *fs, int all)
+{
+ struct dn_flow_queue *q, *qn ;
+ int i ;
+
+ lck_mtx_assert(dn_mutex, LCK_MTX_ASSERT_OWNED);
+
+ for (i = 0 ; i <= fs->rq_size ; i++ ) {
+ for (q = fs->rq[i] ; q ; q = qn ) {
+ struct mbuf *m, *mnext;
+
+ mnext = q->head;
+ while ((m = mnext) != NULL) {
+ mnext = m->m_nextpkt;
+ DN_FREE_PKT(m);
+ }
+ qn = q->next ;
+ FREE(q, M_DUMMYNET);
+ }
+ fs->rq[i] = NULL ;
+ }
+ fs->rq_elements = 0 ;
+ if (all) {
+ /* RED - free lookup table */
+ if (fs->w_q_lookup)
+ FREE(fs->w_q_lookup, M_DUMMYNET);
+ if (fs->rq)
+ FREE(fs->rq, M_DUMMYNET);
+ /* if this fs is not part of a pipe, free it */
+ if (fs->pipe && fs != &(fs->pipe->fs) )
+ FREE(fs, M_DUMMYNET);
+ }
+}
+
+/*
+ * Dispose all packets queued on a pipe (not a flow_set).
+ * Also free all resources associated to a pipe, which is about
+ * to be deleted.
+ */
+static void
+purge_pipe(struct dn_pipe *pipe)
+{
+ struct mbuf *m, *mnext;
+
+ purge_flow_set( &(pipe->fs), 1 );
+
+ mnext = pipe->head;
+ while ((m = mnext) != NULL) {
+ mnext = m->m_nextpkt;
+ DN_FREE_PKT(m);
+ }
+
+ heap_free( &(pipe->scheduler_heap) );
+ heap_free( &(pipe->not_eligible_heap) );
+ heap_free( &(pipe->idle_heap) );
+}
+
+/*
+ * Delete all pipes and heaps returning memory. Must also
+ * remove references from all ipfw rules to all pipes.
+ */
+static void
+dummynet_flush()
+{
+ struct dn_pipe *curr_p, *p ;
+ struct dn_flow_set *fs, *curr_fs;
+
+ lck_mtx_lock(dn_mutex);
+
+ /* remove all references to pipes ...*/
+ flush_pipe_ptrs(NULL);
+ /* prevent future matches... */
+ p = all_pipes ;
+ all_pipes = NULL ;
+ fs = all_flow_sets ;
+ all_flow_sets = NULL ;
+ /* and free heaps so we don't have unwanted events */
+ heap_free(&ready_heap);
+ heap_free(&wfq_ready_heap);
+ heap_free(&extract_heap);
+
+ /*
+ * Now purge all queued pkts and delete all pipes
+ */
+ /* scan and purge all flow_sets. */
+ for ( ; fs ; ) {
+ curr_fs = fs ;
+ fs = fs->next ;
+ purge_flow_set(curr_fs, 1);
+ }
+ for ( ; p ; ) {
+ purge_pipe(p);
+ curr_p = p ;
+ p = p->next ;
+ FREE(curr_p, M_DUMMYNET);
+ }
+ lck_mtx_unlock(dn_mutex);
+}
+
+
+extern struct ip_fw *ip_fw_default_rule ;
+static void
+dn_rule_delete_fs(struct dn_flow_set *fs, void *r)
+{
+ int i ;
+ struct dn_flow_queue *q ;
+ struct mbuf *m ;
+
+ for (i = 0 ; i <= fs->rq_size ; i++) /* last one is ovflow */
+ for (q = fs->rq[i] ; q ; q = q->next )
+ for (m = q->head ; m ; m = m->m_nextpkt ) {
+ struct dn_pkt_tag *pkt = dn_tag_get(m) ;
+ if (pkt->rule == r)
+ pkt->rule = ip_fw_default_rule ;
+ }
+}
+/*
+ * when a firewall rule is deleted, scan all queues and remove the flow-id
+ * from packets matching this rule.
+ */
+void
+dn_rule_delete(void *r)
+{
+ struct dn_pipe *p ;
+ struct dn_flow_set *fs ;
+ struct dn_pkt_tag *pkt ;
+ struct mbuf *m ;
+
+ lck_mtx_lock(dn_mutex);
+
+ /*
+ * If the rule references a queue (dn_flow_set), then scan
+ * the flow set, otherwise scan pipes. Should do either, but doing
+ * both does not harm.
+ */
+ for ( fs = all_flow_sets ; fs ; fs = fs->next )
+ dn_rule_delete_fs(fs, r);
+ for ( p = all_pipes ; p ; p = p->next ) {
+ fs = &(p->fs) ;
+ dn_rule_delete_fs(fs, r);
+ for (m = p->head ; m ; m = m->m_nextpkt ) {
+ pkt = dn_tag_get(m) ;
+ if (pkt->rule == r)
+ pkt->rule = ip_fw_default_rule ;
+ }
+ }
+ lck_mtx_unlock(dn_mutex);
+}
+
+/*
+ * setup RED parameters
+ */
+static int
+config_red(struct dn_flow_set *p, struct dn_flow_set * x)
+{
+ int i;
+
+ x->w_q = p->w_q;
+ x->min_th = SCALE(p->min_th);
+ x->max_th = SCALE(p->max_th);
+ x->max_p = p->max_p;
+
+ x->c_1 = p->max_p / (p->max_th - p->min_th);
+ x->c_2 = SCALE_MUL(x->c_1, SCALE(p->min_th));
+ if (x->flags_fs & DN_IS_GENTLE_RED) {
+ x->c_3 = (SCALE(1) - p->max_p) / p->max_th;
+ x->c_4 = (SCALE(1) - 2 * p->max_p);
+ }
+
+ /* if the lookup table already exist, free and create it again */
+ if (x->w_q_lookup) {
+ FREE(x->w_q_lookup, M_DUMMYNET);
+ x->w_q_lookup = NULL ;
+ }
+ if (red_lookup_depth == 0) {
+ printf("\ndummynet: net.inet.ip.dummynet.red_lookup_depth must be > 0\n");
+ FREE(x, M_DUMMYNET);
+ return EINVAL;
+ }
+ x->lookup_depth = red_lookup_depth;
+ x->w_q_lookup = (u_int *) _MALLOC(x->lookup_depth * sizeof(int),
+ M_DUMMYNET, M_DONTWAIT);
+ if (x->w_q_lookup == NULL) {
+ printf("dummynet: sorry, cannot allocate red lookup table\n");
+ FREE(x, M_DUMMYNET);
+ return ENOSPC;
+ }
+
+ /* fill the lookup table with (1 - w_q)^x */
+ x->lookup_step = p->lookup_step ;
+ x->lookup_weight = p->lookup_weight ;
+ x->w_q_lookup[0] = SCALE(1) - x->w_q;
+ for (i = 1; i < x->lookup_depth; i++)
+ x->w_q_lookup[i] = SCALE_MUL(x->w_q_lookup[i - 1], x->lookup_weight);
+ if (red_avg_pkt_size < 1)
+ red_avg_pkt_size = 512 ;
+ x->avg_pkt_size = red_avg_pkt_size ;
+ if (red_max_pkt_size < 1)
+ red_max_pkt_size = 1500 ;
+ x->max_pkt_size = red_max_pkt_size ;
+ return 0 ;
+}
+
+static int
+alloc_hash(struct dn_flow_set *x, struct dn_flow_set *pfs)
+{
+ if (x->flags_fs & DN_HAVE_FLOW_MASK) { /* allocate some slots */
+ int l = pfs->rq_size;
+
+ if (l == 0)
+ l = dn_hash_size;
+ if (l < 4)
+ l = 4;
+ else if (l > DN_MAX_HASH_SIZE)
+ l = DN_MAX_HASH_SIZE;
+ x->rq_size = l;
+ } else /* one is enough for null mask */
+ x->rq_size = 1;
+ x->rq = _MALLOC((1 + x->rq_size) * sizeof(struct dn_flow_queue *),
+ M_DUMMYNET, M_DONTWAIT | M_ZERO);
+ if (x->rq == NULL) {
+ printf("dummynet: sorry, cannot allocate queue\n");
+ return ENOSPC;
+ }
+ x->rq_elements = 0;
+ return 0 ;
+}
+
+static void
+set_fs_parms(struct dn_flow_set *x, struct dn_flow_set *src)
+{
+ x->flags_fs = src->flags_fs;
+ x->qsize = src->qsize;
+ x->plr = src->plr;
+ x->flow_mask = src->flow_mask;
+ if (x->flags_fs & DN_QSIZE_IS_BYTES) {
+ if (x->qsize > 1024*1024)
+ x->qsize = 1024*1024 ;
+ } else {
+ if (x->qsize == 0)
+ x->qsize = 50 ;
+ if (x->qsize > 100)
+ x->qsize = 50 ;
+ }
+ /* configuring RED */
+ if ( x->flags_fs & DN_IS_RED )
+ config_red(src, x) ; /* XXX should check errors */
+}
+
+/*
+ * setup pipe or queue parameters.
+ */
+
+static int
+config_pipe(struct dn_pipe *p)
+{
+ int i, r;
+ struct dn_flow_set *pfs = &(p->fs);
+ struct dn_flow_queue *q;
+
+ /*
+ * The config program passes parameters as follows:
+ * bw = bits/second (0 means no limits),
+ * delay = ms, must be translated into ticks.
+ * qsize = slots/bytes
+ */
+ p->delay = ( p->delay * hz ) / 1000 ;
+ /* We need either a pipe number or a flow_set number */
+ if (p->pipe_nr == 0 && pfs->fs_nr == 0)
+ return EINVAL ;
+ if (p->pipe_nr != 0 && pfs->fs_nr != 0)
+ return EINVAL ;
+ if (p->pipe_nr != 0) { /* this is a pipe */
+ struct dn_pipe *x, *a, *b;
+
+ lck_mtx_lock(dn_mutex);
+/* locate pipe */
+ for (a = NULL , b = all_pipes ; b && b->pipe_nr < p->pipe_nr ;
projects / apple / xnu.git / blobdiff