/*
- * 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.
#include <config.h>
#include "pinsched.h"
+#include <sys/types.h>
+#include <netinet/in.h>
#include <arpa/inet.h>
+#include <stdint.h>
#include <stdlib.h>
+#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.
*
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) {
* 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. */
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)
{
/* 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;
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;
}
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)
{
git://git.onelab.eu / sliver-openvswitch.git / blobdiff