Implement 802.1D Spanning Tree Protocol.
[sliver-openvswitch.git] / datapath / table-linear.c
1 /*
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
5  */
6
7 #include "table.h"
8 #include "flow.h"
9 #include "datapath.h"
10
11 #include <linux/rcupdate.h>
12 #include <linux/slab.h>
13 #include <linux/rculist.h>
14
15 struct sw_table_linear {
16         struct sw_table swt;
17
18         unsigned int max_flows;
19         unsigned int n_flows;
20         struct list_head flows;
21         struct list_head iter_flows;
22         unsigned long int next_serial;
23 };
24
25 static struct sw_flow *table_linear_lookup(struct sw_table *swt,
26                                          const struct sw_flow_key *key)
27 {
28         struct sw_table_linear *tl = (struct sw_table_linear *) swt;
29         struct sw_flow *flow;
30         list_for_each_entry_rcu (flow, &tl->flows, node) {
31                 if (flow_matches_1wild(key, &flow->key))
32                         return flow;
33         }
34         return NULL;
35 }
36
37 static int table_linear_insert(struct sw_table *swt, struct sw_flow *flow)
38 {
39         struct sw_table_linear *tl = (struct sw_table_linear *) swt;
40         struct sw_flow *f;
41
42
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.
46          */
47         list_for_each_entry (f, &tl->flows, node) {
48                 if (f->priority == flow->priority
49                                 && f->key.wildcards == flow->key.wildcards
50                                 && flow_matches_2wild(&f->key, &flow->key)) {
51                         flow->serial = f->serial;
52                         list_replace_rcu(&f->node, &flow->node);
53                         list_replace_rcu(&f->iter_node, &flow->iter_node);
54                         flow_deferred_free(f);
55                         return 1;
56                 }
57
58                 if (f->priority < flow->priority)
59                         break;
60         }
61
62         /* Make sure there's room in the table. */
63         if (tl->n_flows >= tl->max_flows) {
64                 return 0;
65         }
66         tl->n_flows++;
67
68         /* Insert the entry immediately in front of where we're pointing. */
69         flow->serial = tl->next_serial++;
70         list_add_tail_rcu(&flow->node, &f->node);
71         list_add_rcu(&flow->iter_node, &tl->iter_flows);
72         return 1;
73 }
74
75 static int do_delete(struct sw_table *swt, struct sw_flow *flow) 
76 {
77         list_del_rcu(&flow->node);
78         list_del_rcu(&flow->iter_node);
79         flow_deferred_free(flow);
80         return 1;
81 }
82
83 static int table_linear_delete(struct sw_table *swt,
84                                 const struct sw_flow_key *key, uint16_t priority, int strict)
85 {
86         struct sw_table_linear *tl = (struct sw_table_linear *) swt;
87         struct sw_flow *flow;
88         unsigned int count = 0;
89
90         list_for_each_entry (flow, &tl->flows, node) {
91                 if (flow_del_matches(&flow->key, key, strict)
92                                 && (!strict || (flow->priority == priority)))
93                         count += do_delete(swt, flow);
94         }
95         tl->n_flows -= count;
96         return count;
97 }
98
99 static int table_linear_timeout(struct datapath *dp, struct sw_table *swt)
100 {
101         struct sw_table_linear *tl = (struct sw_table_linear *) swt;
102         struct sw_flow *flow;
103         int count = 0;
104
105         mutex_lock(&dp_mutex);
106         list_for_each_entry (flow, &tl->flows, node) {
107                 int reason = flow_timeout(flow);
108                 if (reason >= 0) {
109                         count += do_delete(swt, flow);
110                         dp_send_flow_expired(dp, flow, reason);
111                 }
112         }
113         tl->n_flows -= count;
114         mutex_unlock(&dp_mutex);
115         return count;
116 }
117
118 static void table_linear_destroy(struct sw_table *swt)
119 {
120         struct sw_table_linear *tl = (struct sw_table_linear *) swt;
121
122         while (!list_empty(&tl->flows)) {
123                 struct sw_flow *flow = list_entry(tl->flows.next,
124                                                   struct sw_flow, node);
125                 list_del(&flow->node);
126                 flow_free(flow);
127         }
128         kfree(tl);
129 }
130
131 static int table_linear_iterate(struct sw_table *swt,
132                                 const struct sw_flow_key *key,
133                                 struct sw_table_position *position,
134                                 int (*callback)(struct sw_flow *, void *),
135                                 void *private)
136 {
137         struct sw_table_linear *tl = (struct sw_table_linear *) swt;
138         struct sw_flow *flow;
139         unsigned long start;
140
141         start = position->private[0];
142         list_for_each_entry (flow, &tl->iter_flows, iter_node) {
143                 if (flow->serial >= start
144                     && flow_matches_2wild(key, &flow->key)) {
145                         int error = callback(flow, private);
146                         if (error) {
147                                 position->private[0] = flow->serial;
148                                 return error;
149                         }
150                 }
151         }
152         return 0;
153 }
154
155 static void table_linear_stats(struct sw_table *swt,
156                                 struct sw_table_stats *stats)
157 {
158         struct sw_table_linear *tl = (struct sw_table_linear *) swt;
159         stats->name = "linear";
160         stats->n_flows = tl->n_flows;
161         stats->max_flows = tl->max_flows;
162         stats->n_matched = swt->n_matched;
163 }
164
165
166 struct sw_table *table_linear_create(unsigned int max_flows)
167 {
168         struct sw_table_linear *tl;
169         struct sw_table *swt;
170
171         tl = kzalloc(sizeof *tl, GFP_KERNEL);
172         if (tl == NULL)
173                 return NULL;
174
175         swt = &tl->swt;
176         swt->lookup = table_linear_lookup;
177         swt->insert = table_linear_insert;
178         swt->delete = table_linear_delete;
179         swt->timeout = table_linear_timeout;
180         swt->destroy = table_linear_destroy;
181         swt->iterate = table_linear_iterate;
182         swt->stats = table_linear_stats;
183
184         tl->max_flows = max_flows;
185         tl->n_flows = 0;
186         INIT_LIST_HEAD(&tl->flows);
187         INIT_LIST_HEAD(&tl->iter_flows);
188         tl->next_serial = 0;
189
190         return swt;
191 }