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;
43 /* Loop through the existing list of entries. New entries will
44 * always be placed behind those with equal priority. Just replace
45 * any flows that match exactly.
47 spin_lock_irqsave(&tl->lock, flags);
48 list_for_each_entry_rcu (f, &tl->flows, u.node) {
49 if (f->priority == flow->priority
50 && f->key.wildcards == flow->key.wildcards
51 && flow_matches(&f->key, &flow->key)
53 list_replace_rcu(&f->u.node, &flow->u.node);
54 spin_unlock_irqrestore(&tl->lock, flags);
55 flow_deferred_free(f);
59 if (f->priority < flow->priority)
63 /* Make sure there's room in the table. */
64 if (atomic_read(&tl->n_flows) >= tl->max_flows) {
65 spin_unlock_irqrestore(&tl->lock, flags);
68 atomic_inc(&tl->n_flows);
70 /* Insert the entry immediately in front of where we're pointing. */
71 list_add_tail_rcu(&flow->u.node, &f->u.node);
72 spin_unlock_irqrestore(&tl->lock, flags);
76 static int do_delete(struct sw_table *swt, struct sw_flow *flow)
79 list_del_rcu(&flow->u.node);
80 flow_deferred_free(flow);
86 static int table_linear_delete(struct sw_table *swt,
87 const struct sw_flow_key *key, int strict)
89 struct sw_table_linear *tl = (struct sw_table_linear *) swt;
90 struct list_head *pos, *n;
91 unsigned int count = 0;
93 list_for_each_safe_rcu (pos, n, &tl->flows) {
94 struct sw_flow *flow = list_entry(pos, struct sw_flow, u.node);
95 if (flow_del_matches(&flow->key, key, strict))
96 count += do_delete(swt, flow);
99 atomic_sub(count, &tl->n_flows);
103 static int table_linear_timeout(struct datapath *dp, struct sw_table *swt)
105 struct sw_table_linear *tl = (struct sw_table_linear *) swt;
106 struct list_head *pos, *n;
109 list_for_each_safe_rcu (pos, n, &tl->flows) {
110 struct sw_flow *flow = list_entry(pos, struct sw_flow, u.node);
111 if (flow_timeout(flow)) {
112 count += do_delete(swt, flow);
113 if (dp->flags & OFPC_SEND_FLOW_EXP)
114 dp_send_flow_expired(dp, flow);
118 atomic_sub(count, &tl->n_flows);
122 static void table_linear_destroy(struct sw_table *swt)
124 struct sw_table_linear *tl = (struct sw_table_linear *) swt;
126 while (!list_empty(&tl->flows)) {
127 struct sw_flow *flow = list_entry(tl->flows.next,
128 struct sw_flow, u.node);
129 list_del(&flow->u.node);
135 /* Linear table's private data is just a pointer to the table */
137 static int table_linear_iterator(struct sw_table *swt,
138 struct swt_iterator *swt_iter)
140 struct sw_table_linear *tl = (struct sw_table_linear *) swt;
142 swt_iter->private = tl;
144 if (atomic_read(&tl->n_flows) == 0)
145 swt_iter->flow = NULL;
147 swt_iter->flow = list_entry(tl->flows.next,
148 struct sw_flow, u.node);
153 static void table_linear_next(struct swt_iterator *swt_iter)
155 struct sw_table_linear *tl;
156 struct list_head *next;
158 if (swt_iter->flow == NULL)
161 tl = (struct sw_table_linear *) swt_iter->private;
163 next = swt_iter->flow->u.node.next;
164 if (next == &tl->flows)
165 swt_iter->flow = NULL;
167 swt_iter->flow = list_entry(next, struct sw_flow, u.node);
170 static void table_linear_iterator_destroy(struct swt_iterator *swt_iter)
173 static void table_linear_stats(struct sw_table *swt,
174 struct sw_table_stats *stats)
176 struct sw_table_linear *tl = (struct sw_table_linear *) swt;
177 stats->name = "linear";
178 stats->n_flows = atomic_read(&tl->n_flows);
179 stats->max_flows = tl->max_flows;
183 struct sw_table *table_linear_create(unsigned int max_flows)
185 struct sw_table_linear *tl;
186 struct sw_table *swt;
188 tl = kzalloc(sizeof *tl, GFP_KERNEL);
193 swt->lookup = table_linear_lookup;
194 swt->insert = table_linear_insert;
195 swt->delete = table_linear_delete;
196 swt->timeout = table_linear_timeout;
197 swt->destroy = table_linear_destroy;
198 swt->stats = table_linear_stats;
200 swt->iterator = table_linear_iterator;
201 swt->iterator_next = table_linear_next;
202 swt->iterator_destroy = table_linear_iterator_destroy;
204 tl->max_flows = max_flows;
205 atomic_set(&tl->n_flows, 0);
206 INIT_LIST_HEAD(&tl->flows);
207 spin_lock_init(&tl->lock);