X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;f=ofproto%2Fpinsched.c;h=9053ea26718b593fba959393754971420969ed70;hb=e0edde6fee279cdbbf3c179f5f50adaf0c7c7f1e;hp=0afd22ff645958861172c51be308349deb6f6f07;hpb=d65349ea28bb67a0062a9b4b60ff97538206373b;p=sliver-openvswitch.git diff --git a/ofproto/pinsched.c b/ofproto/pinsched.c index 0afd22ff6..9053ea267 100644 --- a/ofproto/pinsched.c +++ b/ofproto/pinsched.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2008, 2009 Nicira Networks. + * Copyright (c) 2008, 2009, 2010, 2011 Nicira, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -16,28 +16,37 @@ #include #include "pinsched.h" +#include +#include #include +#include #include +#include "hash.h" +#include "hmap.h" #include "ofpbuf.h" #include "openflow/openflow.h" #include "poll-loop.h" -#include "port-array.h" -#include "queue.h" #include "random.h" #include "rconn.h" -#include "status.h" #include "timeval.h" #include "vconn.h" +struct pinqueue { + struct hmap_node node; /* In struct pinsched's 'queues' hmap. */ + uint16_t port_no; /* Port number. */ + struct list packets; /* Contains "struct ofpbuf"s. */ + int n; /* Number of packets in 'packets'. */ +}; + struct pinsched { /* Client-supplied parameters. */ int rate_limit; /* Packets added to bucket per second. */ int burst_limit; /* Maximum token bucket size, in packets. */ /* One queue per physical port. */ - struct port_array queues; /* Array of "struct ovs_queue *". */ + struct hmap queues; /* Contains "struct pinqueue"s. */ int n_queued; /* Sum over queues[*].n. */ - unsigned int last_tx_port; /* Last port checked in round-robin. */ + struct pinqueue *next_txq; /* Next pinqueue check in round-robin. */ /* Token bucket. * @@ -55,41 +64,70 @@ struct pinsched { unsigned long long n_normal; /* # txed w/o rate limit queuing. */ unsigned long long n_limited; /* # queued for rate limiting. */ unsigned long long n_queue_dropped; /* # dropped due to queue overflow. */ - - /* Switch status. */ - struct status_category *ss_cat; }; +static void +advance_txq(struct pinsched *ps) +{ + struct hmap_node *next; + + next = (ps->next_txq + ? hmap_next(&ps->queues, &ps->next_txq->node) + : hmap_first(&ps->queues)); + ps->next_txq = next ? CONTAINER_OF(next, struct pinqueue, node) : NULL; +} + static struct ofpbuf * -dequeue_packet(struct pinsched *ps, struct ovs_queue *q, - unsigned int port_no) +dequeue_packet(struct pinsched *ps, struct pinqueue *q) { - struct ofpbuf *packet = queue_pop_head(q); - if (!q->n) { - free(q); - port_array_set(&ps->queues, port_no, NULL); - } + struct ofpbuf *packet = ofpbuf_from_list(list_pop_front(&q->packets)); + q->n--; ps->n_queued--; return packet; } +/* Destroys 'q' and removes it from 'ps''s set of queues. + * (The caller must ensure that 'q' is empty.) */ +static void +pinqueue_destroy(struct pinsched *ps, struct pinqueue *q) +{ + hmap_remove(&ps->queues, &q->node); + free(q); +} + +static struct pinqueue * +pinqueue_get(struct pinsched *ps, uint16_t port_no) +{ + uint32_t hash = hash_int(port_no, 0); + struct pinqueue *q; + + HMAP_FOR_EACH_IN_BUCKET (q, node, hash, &ps->queues) { + if (port_no == q->port_no) { + return q; + } + } + + q = xmalloc(sizeof *q); + hmap_insert(&ps->queues, &q->node, hash); + q->port_no = port_no; + list_init(&q->packets); + q->n = 0; + return q; +} + /* Drop a packet from the longest queue in 'ps'. */ static void drop_packet(struct pinsched *ps) { - struct ovs_queue *longest; /* Queue currently selected as longest. */ - int n_longest; /* # of queues of same length as 'longest'. */ - unsigned int longest_port_no; - unsigned int port_no; - struct ovs_queue *q; + struct pinqueue *longest; /* Queue currently selected as longest. */ + int n_longest = 0; /* # of queues of same length as 'longest'. */ + struct pinqueue *q; ps->n_queue_dropped++; - longest = port_array_first(&ps->queues, &port_no); - longest_port_no = port_no; - n_longest = 1; - while ((q = port_array_next(&ps->queues, &port_no)) != NULL) { - if (longest->n < q->n) { + longest = NULL; + HMAP_FOR_EACH (q, node, &ps->queues) { + if (!longest || longest->n < q->n) { longest = q; n_longest = 1; } else if (longest->n == q->n) { @@ -99,24 +137,36 @@ drop_packet(struct pinsched *ps) * distribution (Knuth algorithm 3.4.2R). */ if (!random_range(n_longest)) { longest = q; - longest_port_no = port_no; } } } /* FIXME: do we want to pop the tail instead? */ - ofpbuf_delete(dequeue_packet(ps, longest, longest_port_no)); + ofpbuf_delete(dequeue_packet(ps, longest)); + if (longest->n == 0) { + pinqueue_destroy(ps, longest); + } } /* Remove and return the next packet to transmit (in round-robin order). */ static struct ofpbuf * get_tx_packet(struct pinsched *ps) { - struct ovs_queue *q = port_array_next(&ps->queues, &ps->last_tx_port); - if (!q) { - q = port_array_first(&ps->queues, &ps->last_tx_port); + struct ofpbuf *packet; + struct pinqueue *q; + + if (!ps->next_txq) { + advance_txq(ps); + } + + q = ps->next_txq; + packet = dequeue_packet(ps, q); + advance_txq(ps); + if (q->n == 0) { + pinqueue_destroy(ps, q); } - return dequeue_packet(ps, q, ps->last_tx_port); + + return packet; } /* Add tokens to the bucket based on elapsed time. */ @@ -158,39 +208,25 @@ pinsched_send(struct pinsched *ps, uint16_t port_no, cb(packet, aux); } else { /* Otherwise queue it up for the periodic callback to drain out. */ - struct ovs_queue *q; + struct pinqueue *q; - /* We are called with a buffer obtained from dpif_recv() that has much - * more allocated space than actual content most of the time. Since - * we're going to store the packet for some time, free up that + /* We might be called with a buffer obtained from dpif_recv() that has + * much more allocated space than actual content most of the time. + * Since we're going to store the packet for some time, free up that * otherwise wasted space. */ ofpbuf_trim(packet); if (ps->n_queued >= ps->burst_limit) { drop_packet(ps); } - q = port_array_get(&ps->queues, port_no); - if (!q) { - q = xmalloc(sizeof *q); - queue_init(q); - port_array_set(&ps->queues, port_no, q); - } - queue_push_tail(q, packet); + q = pinqueue_get(ps, port_no); + list_push_back(&q->packets, &packet->list_node); + q->n++; ps->n_queued++; ps->n_limited++; } } -static void -pinsched_status_cb(struct status_reply *sr, void *ps_) -{ - struct pinsched *ps = ps_; - - status_reply_put(sr, "normal=%llu", ps->n_normal); - status_reply_put(sr, "limited=%llu", ps->n_limited); - status_reply_put(sr, "queue-dropped=%llu", ps->n_queue_dropped); -} - void pinsched_run(struct pinsched *ps, pinsched_tx_cb *cb, void *aux) { @@ -223,14 +259,14 @@ pinsched_wait(struct pinsched *ps) /* Creates and returns a scheduler for sending packet-in messages. */ struct pinsched * -pinsched_create(int rate_limit, int burst_limit, struct switch_status *ss) +pinsched_create(int rate_limit, int burst_limit) { struct pinsched *ps; - ps = xcalloc(1, sizeof *ps); - port_array_init(&ps->queues); + ps = xzalloc(sizeof *ps); + hmap_init(&ps->queues); ps->n_queued = 0; - ps->last_tx_port = PORT_ARRAY_SIZE; + ps->next_txq = NULL; ps->last_fill = time_msec(); ps->tokens = rate_limit * 100; ps->n_txq = 0; @@ -239,11 +275,6 @@ pinsched_create(int rate_limit, int burst_limit, struct switch_status *ss) ps->n_queue_dropped = 0; pinsched_set_limits(ps, rate_limit, burst_limit); - if (ss) { - ps->ss_cat = switch_status_register(ss, "rate-limit", - pinsched_status_cb, ps); - } - return ps; } @@ -251,19 +282,26 @@ void pinsched_destroy(struct pinsched *ps) { if (ps) { - struct ovs_queue *queue; - unsigned int port_no; + struct pinqueue *q, *next; - PORT_ARRAY_FOR_EACH (queue, &ps->queues, port_no) { - queue_destroy(queue); - free(queue); + HMAP_FOR_EACH_SAFE (q, next, node, &ps->queues) { + hmap_remove(&ps->queues, &q->node); + ofpbuf_list_delete(&q->packets); + free(q); } - port_array_destroy(&ps->queues); - switch_status_unregister(ps->ss_cat); + hmap_destroy(&ps->queues); free(ps); } } +void +pinsched_get_limits(const struct pinsched *ps, + int *rate_limit, int *burst_limit) +{ + *rate_limit = ps->rate_limit; + *burst_limit = ps->burst_limit; +} + void pinsched_set_limits(struct pinsched *ps, int rate_limit, int burst_limit) {