From afaf9310f9d53654b62eec6d1e161a930b48ec6c Mon Sep 17 00:00:00 2001 From: luigi Date: Fri, 2 Feb 2001 00:18:00 +0000 Subject: MFS: bridge/ipfw/dummynet fixes (bridge.c will be committed separately) --- sys/netinet/ip_dummynet.c | 86 ++++++++++++++++++++++++----------------------- sys/netinet/ip_dummynet.h | 3 +- sys/netinet/ip_fw.c | 6 ++-- sys/netinet/ip_fw.h | 1 + sys/netinet/ip_input.c | 15 +++++++-- sys/netinet/ip_output.c | 20 ++++++++--- 6 files changed, 77 insertions(+), 54 deletions(-) (limited to 'sys/netinet') diff --git a/sys/netinet/ip_dummynet.c b/sys/netinet/ip_dummynet.c index 908c064..8060437 100644 --- a/sys/netinet/ip_dummynet.c +++ b/sys/netinet/ip_dummynet.c @@ -313,8 +313,10 @@ heap_extract(struct dn_heap *h, void *obj) } } +#if 0 /* * change object position and update references + * XXX this one is never used! */ static void heap_move(struct dn_heap *h, dn_key new_key, void *object) @@ -350,6 +352,7 @@ heap_move(struct dn_heap *h, dn_key new_key, void *object) } SET_OFFSET(h, i); } +#endif /* heap_move, unused */ /* * heapify() will reorganize data inside an array to maintain the @@ -450,7 +453,7 @@ transmit_event(struct dn_pipe *pipe) * (originally pkt->dn_m, but could be something else now) if * it has not consumed it. */ - bdg_forward(&m, eh, pkt->ifp); + m = bdg_forward(&m, eh, pkt->ifp); if (m) m_freem(m); } @@ -577,7 +580,6 @@ ready_event_wfq(struct dn_pipe *p) { int p_was_empty = (p->head == NULL) ; struct dn_heap *sch = &(p->scheduler_heap); - struct dn_heap *blh = &(p->backlogged_heap); struct dn_heap *neh = &(p->not_eligible_heap) ; if (p->if_name[0] == 0) /* tx clock is simulated */ @@ -595,7 +597,7 @@ ready_event_wfq(struct dn_pipe *p) * While we have backlogged traffic AND credit, we need to do * something on the queue. */ - while ( blh->elements>0 && p->numbytes >= 0 ) { + while ( p->numbytes >=0 && (sch->elements>0 || neh->elements >0) ) { if (sch->elements > 0) { /* have some eligible pkts to send out */ struct dn_flow_queue *q = sch->p[0].object ; struct dn_pkt *pkt = q->head; @@ -610,7 +612,6 @@ ready_event_wfq(struct dn_pipe *p) p->V += (len<sum ; /* update V */ q->S = q->F ; /* update start time */ if (q->len == 0) { /* Flow not backlogged any more */ - heap_extract(blh, q); fs->backlogged-- ; heap_insert(&(p->idle_heap), q->F, q); } else { /* still backlogged */ @@ -620,13 +621,21 @@ ready_event_wfq(struct dn_pipe *p) */ len = (q->head)->dn_m->m_pkthdr.len; q->F += (len<weight ; - heap_move(blh, q->S, q); - heap_insert(neh, q->S, q); + if (DN_KEY_LEQ(q->S, p->V)) + heap_insert(neh, q->S, q); + else + heap_insert(sch, q->F, q); } } - if (blh->elements > 0) - p->V = MAX64 ( p->V, blh->p[0].key ); - /* move from not_eligible_heap to scheduler_heap */ + /* + * now compute V = max(V, min(S_i)). Remember that all elements in sch + * have by definition S_i <= V so if sch is not empty, V is surely + * the max and we must not update it. Conversely, if sch is empty + * we only need to look at neh. + */ + if (sch->elements == 0 && neh->elements > 0) + p->V = MAX64 ( p->V, neh->p[0].key ); + /* move from neh to sch any packets that have become eligible */ while (neh->elements > 0 && DN_KEY_LEQ(neh->p[0].key, p->V) ) { struct dn_flow_queue *q = neh->p[0].object ; heap_extract(neh, NULL); @@ -638,7 +647,8 @@ ready_event_wfq(struct dn_pipe *p) break ; } } - if (blh->elements == 0 && p->numbytes >= 0 && p->idle_heap.elements > 0) { + if (sch->elements == 0 && neh->elements == 0 && p->numbytes >= 0 + && p->idle_heap.elements > 0) { /* * no traffic and no events scheduled. We can get rid of idle-heap. */ @@ -760,7 +770,7 @@ if_tx_rdy(struct ifnet *ifp) p->numbytes = 0 ; /* mark ready for I/O */ ready_event_wfq(p); } - return 0 ; + return 0; } /* @@ -1064,7 +1074,7 @@ dummynet_io(int pipe_nr, int dir, /* pipe_nr can also be a fs_nr */ goto dropit ; /* random pkt drop */ if ( fs->flags_fs & DN_QSIZE_IS_BYTES) { if (q->len_bytes > fs->qsize) - goto dropit ; /* queue size overflow */ + goto dropit ; /* queue size overflow */ } else { if (q->len >= fs->qsize) goto dropit ; /* queue count overflow */ @@ -1108,13 +1118,8 @@ dummynet_io(int pipe_nr, int dir, /* pipe_nr can also be a fs_nr */ q->len++; q->len_bytes += len ; - if ( q->head != pkt ) { /* flow was not idle, we are done */ - static int errors = 0 ; - if (q->blh_pos >= 0 ) /* good... */ - goto done; - printf("+++ hey [%d] flow 0x%8p not idle but not in heap\n", - ++errors, q); - } + if ( q->head != pkt ) /* 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 @@ -1134,12 +1139,13 @@ dummynet_io(int pipe_nr, int dir, /* pipe_nr can also be a fs_nr */ heap_insert(&ready_heap, curr_time + t , q ); } else { /* - * WF2Q: first compute start time S. If the flow was not in the - * idle_heap (denoted by S=F+1), S is set to the virtual time V - * for that pipe, and we update the sum of weights for the pipe. - * Otherwise, remove flow from idle_heap and set S to max(F,V). - * Then compute finish time F = S + len/weight, and insert into - * backlogged_heap according to S. + * 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 ; @@ -1150,18 +1156,22 @@ dummynet_io(int pipe_nr, int dir, /* pipe_nr can also be a fs_nr */ } q->F = q->S + ( len<weight; - heap_insert(&(pipe->backlogged_heap), q->S, q); - fs->backlogged++ ; - if (pipe->backlogged_heap.elements == 1) + 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 - * appropriate heap. Otherwise, we store in the scheduler_heap + * 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) @@ -1254,7 +1264,6 @@ purge_pipe(struct dn_pipe *pipe) heap_free( &(pipe->scheduler_heap) ); heap_free( &(pipe->not_eligible_heap) ); - heap_free( &(pipe->backlogged_heap) ); heap_free( &(pipe->idle_heap) ); } @@ -1478,14 +1487,10 @@ config_pipe(struct dn_pipe *p) } x->pipe_nr = p->pipe_nr; x->fs.pipe = x ; - /* a flowset is backlogged only if it has packets queued. - * Otherwise it becomes idle, so we can use the same variable - * to store the position in either heap. + /* idle_heap is the only one from which we extract from the middle. */ - x->backlogged_heap.size = x->backlogged_heap.elements = 0 ; - x->backlogged_heap.offset=OFFSET_OF(struct dn_flow_queue, blh_pos); x->idle_heap.size = x->idle_heap.elements = 0 ; - x->idle_heap.offset=OFFSET_OF(struct dn_flow_queue, blh_pos); + x->idle_heap.offset=OFFSET_OF(struct dn_flow_queue, heap_pos); } else x = b; @@ -1562,7 +1567,7 @@ config_pipe(struct dn_pipe *p) /* * Helper function to remove from a heap queues which are linked to * a flow_set about to be deleted. -*/ + */ static void fs_remove_from_heap(struct dn_heap *h, struct dn_flow_set *fs) { @@ -1694,7 +1699,6 @@ delete_pipe(struct dn_pipe *p) if (b->pipe != NULL) { /* Update total weight on parent pipe and cleanup parent heaps */ b->pipe->sum -= b->weight * b->backlogged ; - fs_remove_from_heap(&(b->pipe->backlogged_heap), b); fs_remove_from_heap(&(b->pipe->not_eligible_heap), b); fs_remove_from_heap(&(b->pipe->scheduler_heap), b); #if 1 /* XXX should i remove from idle_heap as well ? */ @@ -1856,12 +1860,10 @@ ip_dn_init(void) all_pipes = NULL ; all_flow_sets = NULL ; ready_heap.size = ready_heap.elements = 0 ; - /* ready_heap.offset = 0 ; */ - ready_heap.offset=OFFSET_OF(struct dn_flow_queue, blh_pos); + ready_heap.offset = 0 ; wfq_ready_heap.size = wfq_ready_heap.elements = 0 ; - /* wfq_ready_heap.offset = 0 ; */ - wfq_ready_heap.offset=OFFSET_OF(struct dn_flow_queue, blh_pos); + wfq_ready_heap.offset = 0 ; extract_heap.size = extract_heap.elements = 0 ; extract_heap.offset = 0 ; diff --git a/sys/netinet/ip_dummynet.h b/sys/netinet/ip_dummynet.h index 5578525..fe80718 100644 --- a/sys/netinet/ip_dummynet.h +++ b/sys/netinet/ip_dummynet.h @@ -224,7 +224,7 @@ struct dn_flow_queue { /* WF2Q+ support */ struct dn_flow_set *fs ; /* parent flow set */ - int blh_pos ; /* position in backlogged_heap */ + int heap_pos ; /* position (index) of struct in heap */ dn_key sched_time ; /* current time when queue enters ready_heap */ dn_key S,F ; /* start-time, finishing time */ @@ -319,7 +319,6 @@ struct dn_pipe { /* a pipe */ /* WF2Q+ */ struct dn_heap scheduler_heap ; /* top extract - key Finish time*/ struct dn_heap not_eligible_heap; /* top extract- key Start time */ - struct dn_heap backlogged_heap ; /* random extract - key Start time */ struct dn_heap idle_heap ; /* random extract - key Start=Finish time */ dn_key V ; /* virtual time */ diff --git a/sys/netinet/ip_fw.c b/sys/netinet/ip_fw.c index ca112d5..1aefb7a 100644 --- a/sys/netinet/ip_fw.c +++ b/sys/netinet/ip_fw.c @@ -1445,10 +1445,8 @@ dropit: /* * Finally, drop the packet. */ - if (*m) { - m_freem(*m); - *m = NULL; - } + if (*m) + return(IP_FW_PORT_DENY_FLAG); return(0); #undef BRIDGED } diff --git a/sys/netinet/ip_fw.h b/sys/netinet/ip_fw.h index a642d72..3d639d1 100644 --- a/sys/netinet/ip_fw.h +++ b/sys/netinet/ip_fw.h @@ -283,6 +283,7 @@ struct ipfw_dyn_rule { #define IP_FW_PORT_DYNT_FLAG 0x10000 #define IP_FW_PORT_TEE_FLAG 0x20000 +#define IP_FW_PORT_DENY_FLAG 0x40000 /* * Function definitions. diff --git a/sys/netinet/ip_input.c b/sys/netinet/ip_input.c index 63e10c8..c73db86 100644 --- a/sys/netinet/ip_input.c +++ b/sys/netinet/ip_input.c @@ -419,8 +419,19 @@ iphack: */ i = (*ip_fw_chk_ptr)(&ip, hlen, NULL, &divert_cookie, &m, &rule, &ip_fw_fwd_addr); - if (m == NULL) /* Packet discarded by firewall */ - return; + if (i & IP_FW_PORT_DENY_FLAG) { /* XXX new interface-denied */ + if (m) + m_freem(m); + return ; + } + if (m == NULL) { /* Packet discarded by firewall */ + static int __debug=10; + if (__debug >0) { + printf("firewall returns NULL, please update!\n"); + __debug-- ; + } + return; + } if (i == 0 && ip_fw_fwd_addr == NULL) /* common case */ goto pass; #ifdef DUMMYNET diff --git a/sys/netinet/ip_output.c b/sys/netinet/ip_output.c index 4eff375..1b19fd7 100644 --- a/sys/netinet/ip_output.c +++ b/sys/netinet/ip_output.c @@ -465,7 +465,8 @@ sendit: hlen, ifp, &divert_cookie, &m, &rule, &dst); /* * On return we must do the following: - * m == NULL -> drop the pkt + * m == NULL -> drop the pkt (old interface, deprecated) + * (off & 0x40000) -> drop the pkt (new interface) * 1<=off<= 0xffff -> DIVERT * (off & 0x10000) -> send to a DUMMYNET pipe * (off & 0x20000) -> TEE the packet @@ -477,9 +478,20 @@ sendit: * unsupported rules), but better play safe and drop * packets in case of doubt. */ + if (off & IP_FW_PORT_DENY_FLAG) { /* XXX new interface-denied */ + if (m) + m_freem(m); + error = EACCES ; + goto done; + } if (!m) { /* firewall said to reject */ - error = EACCES; - goto done; + static int __debug=10; + if (__debug >0) { + printf("firewall returns NULL, please update!\n"); + __debug-- ; + } + error = EACCES; + goto done; } if (off == 0 && dst == old) /* common case */ goto pass ; @@ -495,7 +507,7 @@ sendit: * while a pkt is in dummynet, we are in trouble! */ error = dummynet_io(off & 0xffff, DN_TO_IP_OUT, m, - ifp, ro, dst, rule, flags); + ifp,ro,dst,rule, flags); goto done; } #endif -- cgit v1.1