/*
- * Copyright (c) 2008, 2009, 2010 Nicira Networks.
+ * Copyright (c) 2008, 2009, 2010, 2011, 2012 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 <arpa/inet.h>
#include <stdint.h>
#include <stdlib.h>
+#include "flow.h"
+#include "hash.h"
#include "hmap.h"
#include "ofpbuf.h"
#include "openflow/openflow.h"
#include "poll-loop.h"
#include "random.h"
#include "rconn.h"
-#include "status.h"
+#include "sat-math.h"
#include "timeval.h"
+#include "token-bucket.h"
#include "vconn.h"
struct pinqueue {
struct hmap_node node; /* In struct pinsched's 'queues' hmap. */
- uint16_t port_no; /* Port number. */
+ ofp_port_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. */
+ struct token_bucket token_bucket;
/* One queue per physical port. */
struct hmap queues; /* Contains "struct pinqueue"s. */
int n_queued; /* Sum over queues[*].n. */
struct pinqueue *next_txq; /* Next pinqueue check in round-robin. */
- /* Token bucket.
- *
- * It costs 1000 tokens to send a single packet_in message. A single token
- * per message would be more straightforward, but this choice lets us avoid
- * round-off error in refill_bucket()'s calculation of how many tokens to
- * add to the bucket, since no division step is needed. */
- long long int last_fill; /* Time at which we last added tokens. */
- int tokens; /* Current number of tokens. */
-
/* Transmission queue. */
int n_txq; /* No. of packets waiting in rconn for tx. */
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
return packet;
}
+static void
+adjust_limits(int *rate_limit, int *burst_limit)
+{
+ if (*rate_limit <= 0) {
+ *rate_limit = 1000;
+ }
+ if (*burst_limit <= 0) {
+ *burst_limit = *rate_limit / 4;
+ }
+ if (*burst_limit < 1) {
+ *burst_limit = 1;
+ }
+}
+
/* Destroys 'q' and removes it from 'ps''s set of queues.
* (The caller must ensure that 'q' is empty.) */
static void
}
static struct pinqueue *
-pinqueue_get(struct pinsched *ps, uint16_t port_no)
+pinqueue_get(struct pinsched *ps, ofp_port_t port_no)
{
- uint32_t hash = hash_int(port_no, 0);
+ uint32_t hash = hash_ofp_port(port_no);
struct pinqueue *q;
HMAP_FOR_EACH_IN_BUCKET (q, node, hash, &ps->queues) {
drop_packet(struct pinsched *ps)
{
struct pinqueue *longest; /* Queue currently selected as longest. */
- int n_longest; /* # of queues of same length as 'longest'. */
+ int n_longest = 0; /* # of queues of same length as 'longest'. */
struct pinqueue *q;
ps->n_queue_dropped++;
return packet;
}
-/* Add tokens to the bucket based on elapsed time. */
-static void
-refill_bucket(struct pinsched *ps)
-{
- long long int now = time_msec();
- long long int tokens = (now - ps->last_fill) * ps->rate_limit + ps->tokens;
- if (tokens >= 1000) {
- ps->last_fill = now;
- ps->tokens = MIN(tokens, ps->burst_limit * 1000);
- }
-}
-
/* Attempts to remove enough tokens from 'ps' to transmit a packet. Returns
* true if successful, false otherwise. (In the latter case no tokens are
* removed.) */
static bool
get_token(struct pinsched *ps)
{
- if (ps->tokens >= 1000) {
- ps->tokens -= 1000;
- return true;
- } else {
- return false;
- }
+ return token_bucket_withdraw(&ps->token_bucket, 1000);
}
void
-pinsched_send(struct pinsched *ps, uint16_t port_no,
+pinsched_send(struct pinsched *ps, ofp_port_t port_no,
struct ofpbuf *packet, pinsched_tx_cb *cb, void *aux)
{
if (!ps) {
/* Otherwise queue it up for the periodic callback to drain out. */
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) {
+ if (ps->n_queued * 1000 >= ps->token_bucket.burst) {
drop_packet(ps);
}
q = pinqueue_get(ps, port_no);
}
}
-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)
{
/* Drain some packets out of the bucket if possible, but limit the
* number of iterations to allow other code to get work done too. */
- refill_bucket(ps);
for (i = 0; ps->n_queued && get_token(ps) && i < 50; i++) {
cb(get_tx_packet(ps), aux);
}
pinsched_wait(struct pinsched *ps)
{
if (ps && ps->n_queued) {
- if (ps->tokens >= 1000) {
- /* We can transmit more packets as soon as we're called again. */
- poll_immediate_wake();
- } else {
- /* We have to wait for the bucket to re-fill. We could calculate
- * the exact amount of time here for increased smoothness. */
- poll_timer_wait(TIME_UPDATE_INTERVAL / 2);
- }
+ token_bucket_wait(&ps->token_bucket, 1000);
}
}
/* 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 = xzalloc(sizeof *ps);
+
+ adjust_limits(&rate_limit, &burst_limit);
+ token_bucket_init(&ps->token_bucket,
+ rate_limit, sat_mul(burst_limit, 1000));
+
hmap_init(&ps->queues);
ps->n_queued = 0;
ps->next_txq = NULL;
- ps->last_fill = time_msec();
- ps->tokens = rate_limit * 100;
ps->n_txq = 0;
ps->n_normal = 0;
ps->n_limited = 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;
}
free(q);
}
hmap_destroy(&ps->queues);
- switch_status_unregister(ps->ss_cat);
free(ps);
}
}
pinsched_get_limits(const struct pinsched *ps,
int *rate_limit, int *burst_limit)
{
- *rate_limit = ps->rate_limit;
- *burst_limit = ps->burst_limit;
+ *rate_limit = ps->token_bucket.rate;
+ *burst_limit = ps->token_bucket.burst / 1000;
}
void
pinsched_set_limits(struct pinsched *ps, int rate_limit, int burst_limit)
{
- if (rate_limit <= 0) {
- rate_limit = 1000;
- }
- if (burst_limit <= 0) {
- burst_limit = rate_limit / 4;
- }
- burst_limit = MAX(burst_limit, 1);
- burst_limit = MIN(burst_limit, INT_MAX / 1000);
-
- ps->rate_limit = rate_limit;
- ps->burst_limit = burst_limit;
+ adjust_limits(&rate_limit, &burst_limit);
+ token_bucket_set(&ps->token_bucket,
+ rate_limit, sat_mul(burst_limit, 1000));
while (ps->n_queued > burst_limit) {
drop_packet(ps);
}
}
+
+/* Returns the number of packets scheduled to be sent eventually by 'ps'.
+ * Returns 0 if 'ps' is null. */
+unsigned int
+pinsched_count_txqlen(const struct pinsched *ps)
+{
+ return ps ? ps->n_txq : 0;
+}