2 * Distributed under the terms of the GNU GPL version 2.
3 * Copyright (c) 2007, 2008 The Board of Trustees of The Leland
4 * Stanford Junior University
11 #include <linux/rcupdate.h>
12 #include <linux/slab.h>
13 #include <linux/list.h>
15 struct sw_table_linear {
19 unsigned int max_flows;
21 struct list_head flows;
24 static struct sw_flow *table_linear_lookup(struct sw_table *swt,
25 const struct sw_flow_key *key)
27 struct sw_table_linear *tl = (struct sw_table_linear *) swt;
29 list_for_each_entry_rcu (flow, &tl->flows, u.node) {
30 if (flow_matches(&flow->key, key))
36 static int table_linear_insert(struct sw_table *swt, struct sw_flow *flow)
38 struct sw_table_linear *tl = (struct sw_table_linear *) swt;
39 unsigned long int flags;
42 /* Replace flows that match exactly. */
43 spin_lock_irqsave(&tl->lock, flags);
44 list_for_each_entry_rcu (f, &tl->flows, u.node) {
45 if (f->key.wildcards == flow->key.wildcards
46 && flow_matches(&f->key, &flow->key)
48 list_replace_rcu(&f->u.node, &flow->u.node);
49 spin_unlock_irqrestore(&tl->lock, flags);
50 flow_deferred_free(f);
56 if (atomic_read(&tl->n_flows) >= tl->max_flows) {
57 spin_unlock_irqrestore(&tl->lock, flags);
60 atomic_inc(&tl->n_flows);
62 /* FIXME: need to order rules from most to least specific. */
63 list_add_rcu(&flow->u.node, &tl->flows);
64 spin_unlock_irqrestore(&tl->lock, flags);
68 static int do_delete(struct sw_table *swt, struct sw_flow *flow)
71 list_del_rcu(&flow->u.node);
72 flow_deferred_free(flow);
78 static int table_linear_delete(struct sw_table *swt,
79 const struct sw_flow_key *key, int strict)
81 struct sw_table_linear *tl = (struct sw_table_linear *) swt;
82 struct list_head *pos, *n;
83 unsigned int count = 0;
85 list_for_each_safe_rcu (pos, n, &tl->flows) {
86 struct sw_flow *flow = list_entry(pos, struct sw_flow, u.node);
87 if (flow_del_matches(&flow->key, key, strict))
88 count += do_delete(swt, flow);
91 atomic_sub(count, &tl->n_flows);
95 static int table_linear_timeout(struct datapath *dp, struct sw_table *swt)
97 struct sw_table_linear *tl = (struct sw_table_linear *) swt;
98 struct list_head *pos, *n;
101 list_for_each_safe_rcu (pos, n, &tl->flows) {
102 struct sw_flow *flow = list_entry(pos, struct sw_flow, u.node);
103 if (flow_timeout(flow)) {
104 count += do_delete(swt, flow);
105 if (dp->hello_flags & OFP_CHELLO_SEND_FLOW_EXP)
106 dp_send_flow_expired(dp, flow);
110 atomic_sub(count, &tl->n_flows);
114 static void table_linear_destroy(struct sw_table *swt)
116 struct sw_table_linear *tl = (struct sw_table_linear *) swt;
118 while (!list_empty(&tl->flows)) {
119 struct sw_flow *flow = list_entry(tl->flows.next,
120 struct sw_flow, u.node);
121 list_del(&flow->u.node);
127 /* Linear table's private data is just a pointer to the table */
129 static int table_linear_iterator(struct sw_table *swt,
130 struct swt_iterator *swt_iter)
132 struct sw_table_linear *tl = (struct sw_table_linear *) swt;
134 swt_iter->private = tl;
136 if (atomic_read(&tl->n_flows) == 0)
137 swt_iter->flow = NULL;
139 swt_iter->flow = list_entry(tl->flows.next,
140 struct sw_flow, u.node);
145 static void table_linear_next(struct swt_iterator *swt_iter)
147 struct sw_table_linear *tl;
148 struct list_head *next;
150 if (swt_iter->flow == NULL)
153 tl = (struct sw_table_linear *) swt_iter->private;
155 next = swt_iter->flow->u.node.next;
156 if (next == &tl->flows)
157 swt_iter->flow = NULL;
159 swt_iter->flow = list_entry(next, struct sw_flow, u.node);
162 static void table_linear_iterator_destroy(struct swt_iterator *swt_iter)
165 static void table_linear_stats(struct sw_table *swt,
166 struct sw_table_stats *stats)
168 struct sw_table_linear *tl = (struct sw_table_linear *) swt;
169 stats->name = "linear";
170 stats->n_flows = atomic_read(&tl->n_flows);
171 stats->max_flows = tl->max_flows;
175 struct sw_table *table_linear_create(unsigned int max_flows)
177 struct sw_table_linear *tl;
178 struct sw_table *swt;
180 tl = kzalloc(sizeof *tl, GFP_KERNEL);
185 swt->lookup = table_linear_lookup;
186 swt->insert = table_linear_insert;
187 swt->delete = table_linear_delete;
188 swt->timeout = table_linear_timeout;
189 swt->destroy = table_linear_destroy;
190 swt->stats = table_linear_stats;
192 swt->iterator = table_linear_iterator;
193 swt->iterator_next = table_linear_next;
194 swt->iterator_destroy = table_linear_iterator_destroy;
196 tl->max_flows = max_flows;
197 atomic_set(&tl->n_flows, 0);
198 INIT_LIST_HEAD(&tl->flows);
199 spin_lock_init(&tl->lock);