ipv4: Kill RT_CACHE_DEBUG
[linux-2.6.git] / net / core / dst.c
1 /*
2  * net/core/dst.c       Protocol independent destination cache.
3  *
4  * Authors:             Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
5  *
6  */
7
8 #include <linux/bitops.h>
9 #include <linux/errno.h>
10 #include <linux/init.h>
11 #include <linux/kernel.h>
12 #include <linux/workqueue.h>
13 #include <linux/mm.h>
14 #include <linux/module.h>
15 #include <linux/slab.h>
16 #include <linux/netdevice.h>
17 #include <linux/skbuff.h>
18 #include <linux/string.h>
19 #include <linux/types.h>
20 #include <net/net_namespace.h>
21 #include <linux/sched.h>
22
23 #include <net/dst.h>
24
25 /*
26  * Theory of operations:
27  * 1) We use a list, protected by a spinlock, to add
28  *    new entries from both BH and non-BH context.
29  * 2) In order to keep spinlock held for a small delay,
30  *    we use a second list where are stored long lived
31  *    entries, that are handled by the garbage collect thread
32  *    fired by a workqueue.
33  * 3) This list is guarded by a mutex,
34  *    so that the gc_task and dst_dev_event() can be synchronized.
35  */
36
37 /*
38  * We want to keep lock & list close together
39  * to dirty as few cache lines as possible in __dst_free().
40  * As this is not a very strong hint, we dont force an alignment on SMP.
41  */
42 static struct {
43         spinlock_t              lock;
44         struct dst_entry        *list;
45         unsigned long           timer_inc;
46         unsigned long           timer_expires;
47 } dst_garbage = {
48         .lock = __SPIN_LOCK_UNLOCKED(dst_garbage.lock),
49         .timer_inc = DST_GC_MAX,
50 };
51 static void dst_gc_task(struct work_struct *work);
52 static void ___dst_free(struct dst_entry *dst);
53
54 static DECLARE_DELAYED_WORK(dst_gc_work, dst_gc_task);
55
56 static DEFINE_MUTEX(dst_gc_mutex);
57 /*
58  * long lived entries are maintained in this list, guarded by dst_gc_mutex
59  */
60 static struct dst_entry         *dst_busy_list;
61
62 static void dst_gc_task(struct work_struct *work)
63 {
64         int    delayed = 0;
65         int    work_performed = 0;
66         unsigned long expires = ~0L;
67         struct dst_entry *dst, *next, head;
68         struct dst_entry *last = &head;
69
70         mutex_lock(&dst_gc_mutex);
71         next = dst_busy_list;
72
73 loop:
74         while ((dst = next) != NULL) {
75                 next = dst->next;
76                 prefetch(&next->next);
77                 cond_resched();
78                 if (likely(atomic_read(&dst->__refcnt))) {
79                         last->next = dst;
80                         last = dst;
81                         delayed++;
82                         continue;
83                 }
84                 work_performed++;
85
86                 dst = dst_destroy(dst);
87                 if (dst) {
88                         /* NOHASH and still referenced. Unless it is already
89                          * on gc list, invalidate it and add to gc list.
90                          *
91                          * Note: this is temporary. Actually, NOHASH dst's
92                          * must be obsoleted when parent is obsoleted.
93                          * But we do not have state "obsoleted, but
94                          * referenced by parent", so it is right.
95                          */
96                         if (dst->obsolete > 1)
97                                 continue;
98
99                         ___dst_free(dst);
100                         dst->next = next;
101                         next = dst;
102                 }
103         }
104
105         spin_lock_bh(&dst_garbage.lock);
106         next = dst_garbage.list;
107         if (next) {
108                 dst_garbage.list = NULL;
109                 spin_unlock_bh(&dst_garbage.lock);
110                 goto loop;
111         }
112         last->next = NULL;
113         dst_busy_list = head.next;
114         if (!dst_busy_list)
115                 dst_garbage.timer_inc = DST_GC_MAX;
116         else {
117                 /*
118                  * if we freed less than 1/10 of delayed entries,
119                  * we can sleep longer.
120                  */
121                 if (work_performed <= delayed/10) {
122                         dst_garbage.timer_expires += dst_garbage.timer_inc;
123                         if (dst_garbage.timer_expires > DST_GC_MAX)
124                                 dst_garbage.timer_expires = DST_GC_MAX;
125                         dst_garbage.timer_inc += DST_GC_INC;
126                 } else {
127                         dst_garbage.timer_inc = DST_GC_INC;
128                         dst_garbage.timer_expires = DST_GC_MIN;
129                 }
130                 expires = dst_garbage.timer_expires;
131                 /*
132                  * if the next desired timer is more than 4 seconds in the
133                  * future then round the timer to whole seconds
134                  */
135                 if (expires > 4*HZ)
136                         expires = round_jiffies_relative(expires);
137                 schedule_delayed_work(&dst_gc_work, expires);
138         }
139
140         spin_unlock_bh(&dst_garbage.lock);
141         mutex_unlock(&dst_gc_mutex);
142 }
143
144 int dst_discard(struct sk_buff *skb)
145 {
146         kfree_skb(skb);
147         return 0;
148 }
149 EXPORT_SYMBOL(dst_discard);
150
151 const u32 dst_default_metrics[RTAX_MAX];
152
153 void *dst_alloc(struct dst_ops *ops, struct net_device *dev,
154                 int initial_ref, int initial_obsolete, int flags)
155 {
156         struct dst_entry *dst;
157
158         if (ops->gc && dst_entries_get_fast(ops) > ops->gc_thresh) {
159                 if (ops->gc(ops))
160                         return NULL;
161         }
162         dst = kmem_cache_alloc(ops->kmem_cachep, GFP_ATOMIC);
163         if (!dst)
164                 return NULL;
165         dst->child = NULL;
166         dst->dev = dev;
167         if (dev)
168                 dev_hold(dev);
169         dst->ops = ops;
170         dst_init_metrics(dst, dst_default_metrics, true);
171         dst->expires = 0UL;
172         dst->path = dst;
173         dst->neighbour = NULL;
174         dst->hh = NULL;
175 #ifdef CONFIG_XFRM
176         dst->xfrm = NULL;
177 #endif
178         dst->input = dst_discard;
179         dst->output = dst_discard;
180         dst->error = 0;
181         dst->obsolete = initial_obsolete;
182         dst->header_len = 0;
183         dst->trailer_len = 0;
184 #ifdef CONFIG_IP_ROUTE_CLASSID
185         dst->tclassid = 0;
186 #endif
187         atomic_set(&dst->__refcnt, initial_ref);
188         dst->__use = 0;
189         dst->lastuse = jiffies;
190         dst->flags = flags;
191         dst->next = NULL;
192         dst_entries_add(ops, 1);
193         return dst;
194 }
195 EXPORT_SYMBOL(dst_alloc);
196
197 static void ___dst_free(struct dst_entry *dst)
198 {
199         /* The first case (dev==NULL) is required, when
200            protocol module is unloaded.
201          */
202         if (dst->dev == NULL || !(dst->dev->flags&IFF_UP))
203                 dst->input = dst->output = dst_discard;
204         dst->obsolete = 2;
205 }
206
207 void __dst_free(struct dst_entry *dst)
208 {
209         spin_lock_bh(&dst_garbage.lock);
210         ___dst_free(dst);
211         dst->next = dst_garbage.list;
212         dst_garbage.list = dst;
213         if (dst_garbage.timer_inc > DST_GC_INC) {
214                 dst_garbage.timer_inc = DST_GC_INC;
215                 dst_garbage.timer_expires = DST_GC_MIN;
216                 cancel_delayed_work(&dst_gc_work);
217                 schedule_delayed_work(&dst_gc_work, dst_garbage.timer_expires);
218         }
219         spin_unlock_bh(&dst_garbage.lock);
220 }
221 EXPORT_SYMBOL(__dst_free);
222
223 struct dst_entry *dst_destroy(struct dst_entry * dst)
224 {
225         struct dst_entry *child;
226         struct neighbour *neigh;
227         struct hh_cache *hh;
228
229         smp_rmb();
230
231 again:
232         neigh = dst->neighbour;
233         hh = dst->hh;
234         child = dst->child;
235
236         dst->hh = NULL;
237         if (hh)
238                 hh_cache_put(hh);
239
240         if (neigh) {
241                 dst->neighbour = NULL;
242                 neigh_release(neigh);
243         }
244
245         dst_entries_add(dst->ops, -1);
246
247         if (dst->ops->destroy)
248                 dst->ops->destroy(dst);
249         if (dst->dev)
250                 dev_put(dst->dev);
251         kmem_cache_free(dst->ops->kmem_cachep, dst);
252
253         dst = child;
254         if (dst) {
255                 int nohash = dst->flags & DST_NOHASH;
256
257                 if (atomic_dec_and_test(&dst->__refcnt)) {
258                         /* We were real parent of this dst, so kill child. */
259                         if (nohash)
260                                 goto again;
261                 } else {
262                         /* Child is still referenced, return it for freeing. */
263                         if (nohash)
264                                 return dst;
265                         /* Child is still in his hash table */
266                 }
267         }
268         return NULL;
269 }
270 EXPORT_SYMBOL(dst_destroy);
271
272 void dst_release(struct dst_entry *dst)
273 {
274         if (dst) {
275                 int newrefcnt;
276
277                 newrefcnt = atomic_dec_return(&dst->__refcnt);
278                 WARN_ON(newrefcnt < 0);
279                 if (unlikely(dst->flags & DST_NOCACHE) && !newrefcnt) {
280                         dst = dst_destroy(dst);
281                         if (dst)
282                                 __dst_free(dst);
283                 }
284         }
285 }
286 EXPORT_SYMBOL(dst_release);
287
288 u32 *dst_cow_metrics_generic(struct dst_entry *dst, unsigned long old)
289 {
290         u32 *p = kmalloc(sizeof(u32) * RTAX_MAX, GFP_ATOMIC);
291
292         if (p) {
293                 u32 *old_p = __DST_METRICS_PTR(old);
294                 unsigned long prev, new;
295
296                 memcpy(p, old_p, sizeof(u32) * RTAX_MAX);
297
298                 new = (unsigned long) p;
299                 prev = cmpxchg(&dst->_metrics, old, new);
300
301                 if (prev != old) {
302                         kfree(p);
303                         p = __DST_METRICS_PTR(prev);
304                         if (prev & DST_METRICS_READ_ONLY)
305                                 p = NULL;
306                 }
307         }
308         return p;
309 }
310 EXPORT_SYMBOL(dst_cow_metrics_generic);
311
312 /* Caller asserts that dst_metrics_read_only(dst) is false.  */
313 void __dst_destroy_metrics_generic(struct dst_entry *dst, unsigned long old)
314 {
315         unsigned long prev, new;
316
317         new = (unsigned long) dst_default_metrics;
318         prev = cmpxchg(&dst->_metrics, old, new);
319         if (prev == old)
320                 kfree(__DST_METRICS_PTR(old));
321 }
322 EXPORT_SYMBOL(__dst_destroy_metrics_generic);
323
324 /**
325  * skb_dst_set_noref - sets skb dst, without a reference
326  * @skb: buffer
327  * @dst: dst entry
328  *
329  * Sets skb dst, assuming a reference was not taken on dst
330  * skb_dst_drop() should not dst_release() this dst
331  */
332 void skb_dst_set_noref(struct sk_buff *skb, struct dst_entry *dst)
333 {
334         WARN_ON(!rcu_read_lock_held() && !rcu_read_lock_bh_held());
335         /* If dst not in cache, we must take a reference, because
336          * dst_release() will destroy dst as soon as its refcount becomes zero
337          */
338         if (unlikely(dst->flags & DST_NOCACHE)) {
339                 dst_hold(dst);
340                 skb_dst_set(skb, dst);
341         } else {
342                 skb->_skb_refdst = (unsigned long)dst | SKB_DST_NOREF;
343         }
344 }
345 EXPORT_SYMBOL(skb_dst_set_noref);
346
347 /* Dirty hack. We did it in 2.2 (in __dst_free),
348  * we have _very_ good reasons not to repeat
349  * this mistake in 2.3, but we have no choice
350  * now. _It_ _is_ _explicit_ _deliberate_
351  * _race_ _condition_.
352  *
353  * Commented and originally written by Alexey.
354  */
355 static void dst_ifdown(struct dst_entry *dst, struct net_device *dev,
356                        int unregister)
357 {
358         if (dst->ops->ifdown)
359                 dst->ops->ifdown(dst, dev, unregister);
360
361         if (dev != dst->dev)
362                 return;
363
364         if (!unregister) {
365                 dst->input = dst->output = dst_discard;
366         } else {
367                 dst->dev = dev_net(dst->dev)->loopback_dev;
368                 dev_hold(dst->dev);
369                 dev_put(dev);
370                 if (dst->neighbour && dst->neighbour->dev == dev) {
371                         dst->neighbour->dev = dst->dev;
372                         dev_hold(dst->dev);
373                         dev_put(dev);
374                 }
375         }
376 }
377
378 static int dst_dev_event(struct notifier_block *this, unsigned long event,
379                          void *ptr)
380 {
381         struct net_device *dev = ptr;
382         struct dst_entry *dst, *last = NULL;
383
384         switch (event) {
385         case NETDEV_UNREGISTER:
386         case NETDEV_DOWN:
387                 mutex_lock(&dst_gc_mutex);
388                 for (dst = dst_busy_list; dst; dst = dst->next) {
389                         last = dst;
390                         dst_ifdown(dst, dev, event != NETDEV_DOWN);
391                 }
392
393                 spin_lock_bh(&dst_garbage.lock);
394                 dst = dst_garbage.list;
395                 dst_garbage.list = NULL;
396                 spin_unlock_bh(&dst_garbage.lock);
397
398                 if (last)
399                         last->next = dst;
400                 else
401                         dst_busy_list = dst;
402                 for (; dst; dst = dst->next)
403                         dst_ifdown(dst, dev, event != NETDEV_DOWN);
404                 mutex_unlock(&dst_gc_mutex);
405                 break;
406         }
407         return NOTIFY_DONE;
408 }
409
410 static struct notifier_block dst_dev_notifier = {
411         .notifier_call  = dst_dev_event,
412         .priority = -10, /* must be called after other network notifiers */
413 };
414
415 void __init dst_init(void)
416 {
417         register_netdevice_notifier(&dst_dev_notifier);
418 }