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