blob: 1a5e49da0e77bdaaaaebf5369a97153ff75f4918 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
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/mm.h>
13#include <linux/module.h>
14#include <linux/netdevice.h>
15#include <linux/sched.h>
16#include <linux/skbuff.h>
17#include <linux/string.h>
18#include <linux/types.h>
19
20#include <net/dst.h>
21
22/* Locking strategy:
23 * 1) Garbage collection state of dead destination cache
24 * entries is protected by dst_lock.
25 * 2) GC is run only from BH context, and is the only remover
26 * of entries.
27 * 3) Entries are added to the garbage list from both BH
28 * and non-BH context, so local BH disabling is needed.
29 * 4) All operations modify state, so a spinlock is used.
30 */
31static struct dst_entry *dst_garbage_list;
32#if RT_CACHE_DEBUG >= 2
33static atomic_t dst_total = ATOMIC_INIT(0);
34#endif
35static DEFINE_SPINLOCK(dst_lock);
36
37static unsigned long dst_gc_timer_expires;
38static unsigned long dst_gc_timer_inc = DST_GC_MAX;
39static void dst_run_gc(unsigned long);
40static void ___dst_free(struct dst_entry * dst);
41
Ingo Molnar8d06afa2005-09-09 13:10:40 -070042static DEFINE_TIMER(dst_gc_timer, dst_run_gc, DST_GC_MIN, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -070043
44static void dst_run_gc(unsigned long dummy)
45{
46 int delayed = 0;
Denis Lunevf0098f72005-07-30 17:47:25 -070047 int work_performed;
Linus Torvalds1da177e2005-04-16 15:20:36 -070048 struct dst_entry * dst, **dstp;
49
50 if (!spin_trylock(&dst_lock)) {
51 mod_timer(&dst_gc_timer, jiffies + HZ/10);
52 return;
53 }
54
Linus Torvalds1da177e2005-04-16 15:20:36 -070055 del_timer(&dst_gc_timer);
56 dstp = &dst_garbage_list;
Denis Lunevf0098f72005-07-30 17:47:25 -070057 work_performed = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -070058 while ((dst = *dstp) != NULL) {
59 if (atomic_read(&dst->__refcnt)) {
60 dstp = &dst->next;
61 delayed++;
62 continue;
63 }
64 *dstp = dst->next;
Denis Lunevf0098f72005-07-30 17:47:25 -070065 work_performed = 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -070066
67 dst = dst_destroy(dst);
68 if (dst) {
69 /* NOHASH and still referenced. Unless it is already
70 * on gc list, invalidate it and add to gc list.
71 *
72 * Note: this is temporary. Actually, NOHASH dst's
73 * must be obsoleted when parent is obsoleted.
74 * But we do not have state "obsoleted, but
75 * referenced by parent", so it is right.
76 */
77 if (dst->obsolete > 1)
78 continue;
79
80 ___dst_free(dst);
81 dst->next = *dstp;
82 *dstp = dst;
83 dstp = &dst->next;
84 }
85 }
86 if (!dst_garbage_list) {
87 dst_gc_timer_inc = DST_GC_MAX;
88 goto out;
89 }
Denis Lunevf0098f72005-07-30 17:47:25 -070090 if (!work_performed) {
91 if ((dst_gc_timer_expires += dst_gc_timer_inc) > DST_GC_MAX)
92 dst_gc_timer_expires = DST_GC_MAX;
93 dst_gc_timer_inc += DST_GC_INC;
94 } else {
95 dst_gc_timer_inc = DST_GC_INC;
96 dst_gc_timer_expires = DST_GC_MIN;
97 }
Linus Torvalds1da177e2005-04-16 15:20:36 -070098#if RT_CACHE_DEBUG >= 2
99 printk("dst_total: %d/%d %ld\n",
100 atomic_read(&dst_total), delayed, dst_gc_timer_expires);
101#endif
Dmitry Mishin7c917672006-08-09 02:25:54 -0700102 mod_timer(&dst_gc_timer, jiffies + dst_gc_timer_expires);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700103
104out:
105 spin_unlock(&dst_lock);
106}
107
108static int dst_discard_in(struct sk_buff *skb)
109{
110 kfree_skb(skb);
111 return 0;
112}
113
114static int dst_discard_out(struct sk_buff *skb)
115{
116 kfree_skb(skb);
117 return 0;
118}
119
120void * dst_alloc(struct dst_ops * ops)
121{
122 struct dst_entry * dst;
123
124 if (ops->gc && atomic_read(&ops->entries) > ops->gc_thresh) {
125 if (ops->gc())
126 return NULL;
127 }
128 dst = kmem_cache_alloc(ops->kmem_cachep, SLAB_ATOMIC);
129 if (!dst)
130 return NULL;
131 memset(dst, 0, ops->entry_size);
132 atomic_set(&dst->__refcnt, 0);
133 dst->ops = ops;
134 dst->lastuse = jiffies;
135 dst->path = dst;
136 dst->input = dst_discard_in;
137 dst->output = dst_discard_out;
138#if RT_CACHE_DEBUG >= 2
139 atomic_inc(&dst_total);
140#endif
141 atomic_inc(&ops->entries);
142 return dst;
143}
144
145static void ___dst_free(struct dst_entry * dst)
146{
147 /* The first case (dev==NULL) is required, when
148 protocol module is unloaded.
149 */
150 if (dst->dev == NULL || !(dst->dev->flags&IFF_UP)) {
151 dst->input = dst_discard_in;
152 dst->output = dst_discard_out;
153 }
154 dst->obsolete = 2;
155}
156
157void __dst_free(struct dst_entry * dst)
158{
159 spin_lock_bh(&dst_lock);
160 ___dst_free(dst);
161 dst->next = dst_garbage_list;
162 dst_garbage_list = dst;
163 if (dst_gc_timer_inc > DST_GC_INC) {
164 dst_gc_timer_inc = DST_GC_INC;
165 dst_gc_timer_expires = DST_GC_MIN;
166 mod_timer(&dst_gc_timer, jiffies + dst_gc_timer_expires);
167 }
168 spin_unlock_bh(&dst_lock);
169}
170
171struct dst_entry *dst_destroy(struct dst_entry * dst)
172{
173 struct dst_entry *child;
174 struct neighbour *neigh;
175 struct hh_cache *hh;
176
177 smp_rmb();
178
179again:
180 neigh = dst->neighbour;
181 hh = dst->hh;
182 child = dst->child;
183
184 dst->hh = NULL;
185 if (hh && atomic_dec_and_test(&hh->hh_refcnt))
186 kfree(hh);
187
188 if (neigh) {
189 dst->neighbour = NULL;
190 neigh_release(neigh);
191 }
192
193 atomic_dec(&dst->ops->entries);
194
195 if (dst->ops->destroy)
196 dst->ops->destroy(dst);
197 if (dst->dev)
198 dev_put(dst->dev);
199#if RT_CACHE_DEBUG >= 2
200 atomic_dec(&dst_total);
201#endif
202 kmem_cache_free(dst->ops->kmem_cachep, dst);
203
204 dst = child;
205 if (dst) {
Herbert Xu6775cab2005-04-16 15:24:10 -0700206 int nohash = dst->flags & DST_NOHASH;
207
Linus Torvalds1da177e2005-04-16 15:20:36 -0700208 if (atomic_dec_and_test(&dst->__refcnt)) {
209 /* We were real parent of this dst, so kill child. */
Herbert Xu6775cab2005-04-16 15:24:10 -0700210 if (nohash)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700211 goto again;
212 } else {
213 /* Child is still referenced, return it for freeing. */
Herbert Xu6775cab2005-04-16 15:24:10 -0700214 if (nohash)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700215 return dst;
216 /* Child is still in his hash table */
217 }
218 }
219 return NULL;
220}
221
222/* Dirty hack. We did it in 2.2 (in __dst_free),
223 * we have _very_ good reasons not to repeat
224 * this mistake in 2.3, but we have no choice
225 * now. _It_ _is_ _explicit_ _deliberate_
226 * _race_ _condition_.
227 *
228 * Commented and originally written by Alexey.
229 */
230static inline void dst_ifdown(struct dst_entry *dst, struct net_device *dev,
231 int unregister)
232{
233 if (dst->ops->ifdown)
234 dst->ops->ifdown(dst, dev, unregister);
235
236 if (dev != dst->dev)
237 return;
238
239 if (!unregister) {
240 dst->input = dst_discard_in;
241 dst->output = dst_discard_out;
242 } else {
243 dst->dev = &loopback_dev;
244 dev_hold(&loopback_dev);
245 dev_put(dev);
246 if (dst->neighbour && dst->neighbour->dev == dev) {
247 dst->neighbour->dev = &loopback_dev;
248 dev_put(dev);
249 dev_hold(&loopback_dev);
250 }
251 }
252}
253
254static int dst_dev_event(struct notifier_block *this, unsigned long event, void *ptr)
255{
256 struct net_device *dev = ptr;
257 struct dst_entry *dst;
258
259 switch (event) {
260 case NETDEV_UNREGISTER:
261 case NETDEV_DOWN:
262 spin_lock_bh(&dst_lock);
263 for (dst = dst_garbage_list; dst; dst = dst->next) {
264 dst_ifdown(dst, dev, event != NETDEV_DOWN);
265 }
266 spin_unlock_bh(&dst_lock);
267 break;
268 }
269 return NOTIFY_DONE;
270}
271
272static struct notifier_block dst_dev_notifier = {
273 .notifier_call = dst_dev_event,
274};
275
276void __init dst_init(void)
277{
278 register_netdevice_notifier(&dst_dev_notifier);
279}
280
281EXPORT_SYMBOL(__dst_free);
282EXPORT_SYMBOL(dst_alloc);
283EXPORT_SYMBOL(dst_destroy);