blob: 57bc4d5b8d084c053cded6ebddfe66bf6255d9f5 [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>
Eric Dumazet86bba262007-09-12 14:29:01 +020012#include <linux/workqueue.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070013#include <linux/mm.h>
14#include <linux/module.h>
15#include <linux/netdevice.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070016#include <linux/skbuff.h>
17#include <linux/string.h>
18#include <linux/types.h>
Eric W. Biedermane9dc8652007-09-12 13:02:17 +020019#include <net/net_namespace.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070020
21#include <net/dst.h>
22
Eric Dumazet86bba262007-09-12 14:29:01 +020023/*
24 * Theory of operations:
25 * 1) We use a list, protected by a spinlock, to add
26 * new entries from both BH and non-BH context.
27 * 2) In order to keep spinlock held for a small delay,
28 * we use a second list where are stored long lived
29 * entries, that are handled by the garbage collect thread
30 * fired by a workqueue.
31 * 3) This list is guarded by a mutex,
32 * so that the gc_task and dst_dev_event() can be synchronized.
Linus Torvalds1da177e2005-04-16 15:20:36 -070033 */
YOSHIFUJI Hideaki4ec93ed2007-02-09 23:24:36 +090034#if RT_CACHE_DEBUG >= 2
Linus Torvalds1da177e2005-04-16 15:20:36 -070035static atomic_t dst_total = ATOMIC_INIT(0);
36#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -070037
Eric Dumazet86bba262007-09-12 14:29:01 +020038/*
39 * We want to keep lock & list close together
40 * to dirty as few cache lines as possible in __dst_free().
41 * As this is not a very strong hint, we dont force an alignment on SMP.
42 */
43static struct {
44 spinlock_t lock;
45 struct dst_entry *list;
46 unsigned long timer_inc;
47 unsigned long timer_expires;
48} dst_garbage = {
49 .lock = __SPIN_LOCK_UNLOCKED(dst_garbage.lock),
50 .timer_inc = DST_GC_MAX,
51};
52static void dst_gc_task(struct work_struct *work);
Linus Torvalds1da177e2005-04-16 15:20:36 -070053static void ___dst_free(struct dst_entry * dst);
54
Eric Dumazet86bba262007-09-12 14:29:01 +020055static DECLARE_DELAYED_WORK(dst_gc_work, dst_gc_task);
Linus Torvalds1da177e2005-04-16 15:20:36 -070056
Eric Dumazet86bba262007-09-12 14:29:01 +020057static DEFINE_MUTEX(dst_gc_mutex);
58/*
59 * long lived entries are maintained in this list, guarded by dst_gc_mutex
60 */
61static struct dst_entry *dst_busy_list;
62
63static void dst_gc_task(struct work_struct *work)
Linus Torvalds1da177e2005-04-16 15:20:36 -070064{
65 int delayed = 0;
Eric Dumazet86bba262007-09-12 14:29:01 +020066 int work_performed = 0;
67 unsigned long expires = ~0L;
68 struct dst_entry *dst, *next, head;
69 struct dst_entry *last = &head;
70#if RT_CACHE_DEBUG >= 2
71 ktime_t time_start = ktime_get();
72 struct timespec elapsed;
73#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -070074
Eric Dumazet86bba262007-09-12 14:29:01 +020075 mutex_lock(&dst_gc_mutex);
76 next = dst_busy_list;
Linus Torvalds1da177e2005-04-16 15:20:36 -070077
Eric Dumazet86bba262007-09-12 14:29:01 +020078loop:
79 while ((dst = next) != NULL) {
80 next = dst->next;
81 prefetch(&next->next);
82 if (likely(atomic_read(&dst->__refcnt))) {
83 last->next = dst;
84 last = dst;
Linus Torvalds1da177e2005-04-16 15:20:36 -070085 delayed++;
86 continue;
87 }
Eric Dumazet86bba262007-09-12 14:29:01 +020088 work_performed++;
Linus Torvalds1da177e2005-04-16 15:20:36 -070089
90 dst = dst_destroy(dst);
91 if (dst) {
92 /* NOHASH and still referenced. Unless it is already
93 * on gc list, invalidate it and add to gc list.
94 *
95 * Note: this is temporary. Actually, NOHASH dst's
96 * must be obsoleted when parent is obsoleted.
97 * But we do not have state "obsoleted, but
98 * referenced by parent", so it is right.
99 */
100 if (dst->obsolete > 1)
101 continue;
102
103 ___dst_free(dst);
Eric Dumazet86bba262007-09-12 14:29:01 +0200104 dst->next = next;
105 next = dst;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700106 }
107 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700108
Eric Dumazet86bba262007-09-12 14:29:01 +0200109 spin_lock_bh(&dst_garbage.lock);
110 next = dst_garbage.list;
111 if (next) {
112 dst_garbage.list = NULL;
113 spin_unlock_bh(&dst_garbage.lock);
114 goto loop;
115 }
116 last->next = NULL;
117 dst_busy_list = head.next;
118 if (!dst_busy_list)
119 dst_garbage.timer_inc = DST_GC_MAX;
120 else {
121 /*
122 * if we freed less than 1/10 of delayed entries,
123 * we can sleep longer.
124 */
125 if (work_performed <= delayed/10) {
126 dst_garbage.timer_expires += dst_garbage.timer_inc;
127 if (dst_garbage.timer_expires > DST_GC_MAX)
128 dst_garbage.timer_expires = DST_GC_MAX;
129 dst_garbage.timer_inc += DST_GC_INC;
130 } else {
131 dst_garbage.timer_inc = DST_GC_INC;
132 dst_garbage.timer_expires = DST_GC_MIN;
133 }
134 expires = dst_garbage.timer_expires;
135 /*
136 * if the next desired timer is more than 4 seconds in the future
137 * then round the timer to whole seconds
138 */
139 if (expires > 4*HZ)
140 expires = round_jiffies_relative(expires);
141 schedule_delayed_work(&dst_gc_work, expires);
142 }
143
144 spin_unlock_bh(&dst_garbage.lock);
145 mutex_unlock(&dst_gc_mutex);
146#if RT_CACHE_DEBUG >= 2
147 elapsed = ktime_to_timespec(ktime_sub(ktime_get(), time_start));
148 printk(KERN_DEBUG "dst_total: %d delayed: %d work_perf: %d"
149 " expires: %lu elapsed: %lu us\n",
150 atomic_read(&dst_total), delayed, work_performed,
151 expires,
152 elapsed.tv_sec * USEC_PER_SEC + elapsed.tv_nsec / NSEC_PER_USEC);
153#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -0700154}
155
Herbert Xu352e5122007-11-13 21:34:06 -0800156int dst_discard(struct sk_buff *skb)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700157{
158 kfree_skb(skb);
159 return 0;
160}
Herbert Xu352e5122007-11-13 21:34:06 -0800161EXPORT_SYMBOL(dst_discard);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700162
163void * dst_alloc(struct dst_ops * ops)
164{
165 struct dst_entry * dst;
166
167 if (ops->gc && atomic_read(&ops->entries) > ops->gc_thresh) {
Daniel Lezcano569d3642008-01-18 03:56:57 -0800168 if (ops->gc(ops))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700169 return NULL;
170 }
Robert P. J. Dayc3762222007-02-10 01:45:03 -0800171 dst = kmem_cache_zalloc(ops->kmem_cachep, GFP_ATOMIC);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700172 if (!dst)
173 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700174 atomic_set(&dst->__refcnt, 0);
175 dst->ops = ops;
176 dst->lastuse = jiffies;
177 dst->path = dst;
Denis Chengc4b10102007-06-05 00:06:57 -0700178 dst->input = dst->output = dst_discard;
YOSHIFUJI Hideaki4ec93ed2007-02-09 23:24:36 +0900179#if RT_CACHE_DEBUG >= 2
Linus Torvalds1da177e2005-04-16 15:20:36 -0700180 atomic_inc(&dst_total);
181#endif
182 atomic_inc(&ops->entries);
183 return dst;
184}
185
186static void ___dst_free(struct dst_entry * dst)
187{
188 /* The first case (dev==NULL) is required, when
189 protocol module is unloaded.
190 */
191 if (dst->dev == NULL || !(dst->dev->flags&IFF_UP)) {
Denis Chengc4b10102007-06-05 00:06:57 -0700192 dst->input = dst->output = dst_discard;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700193 }
194 dst->obsolete = 2;
195}
196
197void __dst_free(struct dst_entry * dst)
198{
Eric Dumazet86bba262007-09-12 14:29:01 +0200199 spin_lock_bh(&dst_garbage.lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700200 ___dst_free(dst);
Eric Dumazet86bba262007-09-12 14:29:01 +0200201 dst->next = dst_garbage.list;
202 dst_garbage.list = dst;
203 if (dst_garbage.timer_inc > DST_GC_INC) {
204 dst_garbage.timer_inc = DST_GC_INC;
205 dst_garbage.timer_expires = DST_GC_MIN;
Benjamin Theryf262b592008-09-12 16:16:37 -0700206 cancel_delayed_work(&dst_gc_work);
Eric Dumazet86bba262007-09-12 14:29:01 +0200207 schedule_delayed_work(&dst_gc_work, dst_garbage.timer_expires);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700208 }
Eric Dumazet86bba262007-09-12 14:29:01 +0200209 spin_unlock_bh(&dst_garbage.lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700210}
211
212struct dst_entry *dst_destroy(struct dst_entry * dst)
213{
214 struct dst_entry *child;
215 struct neighbour *neigh;
216 struct hh_cache *hh;
217
218 smp_rmb();
219
220again:
221 neigh = dst->neighbour;
222 hh = dst->hh;
223 child = dst->child;
224
225 dst->hh = NULL;
226 if (hh && atomic_dec_and_test(&hh->hh_refcnt))
227 kfree(hh);
228
229 if (neigh) {
230 dst->neighbour = NULL;
231 neigh_release(neigh);
232 }
233
234 atomic_dec(&dst->ops->entries);
235
236 if (dst->ops->destroy)
237 dst->ops->destroy(dst);
238 if (dst->dev)
239 dev_put(dst->dev);
YOSHIFUJI Hideaki4ec93ed2007-02-09 23:24:36 +0900240#if RT_CACHE_DEBUG >= 2
Linus Torvalds1da177e2005-04-16 15:20:36 -0700241 atomic_dec(&dst_total);
242#endif
243 kmem_cache_free(dst->ops->kmem_cachep, dst);
244
245 dst = child;
246 if (dst) {
Herbert Xu6775cab2005-04-16 15:24:10 -0700247 int nohash = dst->flags & DST_NOHASH;
248
Linus Torvalds1da177e2005-04-16 15:20:36 -0700249 if (atomic_dec_and_test(&dst->__refcnt)) {
250 /* We were real parent of this dst, so kill child. */
Herbert Xu6775cab2005-04-16 15:24:10 -0700251 if (nohash)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700252 goto again;
253 } else {
254 /* Child is still referenced, return it for freeing. */
Herbert Xu6775cab2005-04-16 15:24:10 -0700255 if (nohash)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700256 return dst;
257 /* Child is still in his hash table */
258 }
259 }
260 return NULL;
261}
262
Ilpo Järvinen8d330862008-03-27 17:53:31 -0700263void dst_release(struct dst_entry *dst)
264{
265 if (dst) {
Eric Dumazetef711cf2008-11-14 00:53:54 -0800266 int newrefcnt;
267
Ilpo Järvinen8d330862008-03-27 17:53:31 -0700268 smp_mb__before_atomic_dec();
Eric Dumazetef711cf2008-11-14 00:53:54 -0800269 newrefcnt = atomic_dec_return(&dst->__refcnt);
270 WARN_ON(newrefcnt < 0);
Ilpo Järvinen8d330862008-03-27 17:53:31 -0700271 }
272}
273EXPORT_SYMBOL(dst_release);
274
Linus Torvalds1da177e2005-04-16 15:20:36 -0700275/* Dirty hack. We did it in 2.2 (in __dst_free),
276 * we have _very_ good reasons not to repeat
277 * this mistake in 2.3, but we have no choice
278 * now. _It_ _is_ _explicit_ _deliberate_
279 * _race_ _condition_.
280 *
281 * Commented and originally written by Alexey.
282 */
283static inline void dst_ifdown(struct dst_entry *dst, struct net_device *dev,
284 int unregister)
285{
286 if (dst->ops->ifdown)
287 dst->ops->ifdown(dst, dev, unregister);
288
289 if (dev != dst->dev)
290 return;
291
292 if (!unregister) {
Denis Chengc4b10102007-06-05 00:06:57 -0700293 dst->input = dst->output = dst_discard;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700294 } else {
YOSHIFUJI Hideakic346dca2008-03-25 21:47:49 +0900295 dst->dev = dev_net(dst->dev)->loopback_dev;
Daniel Lezcanode3cb742007-09-25 19:16:28 -0700296 dev_hold(dst->dev);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700297 dev_put(dev);
298 if (dst->neighbour && dst->neighbour->dev == dev) {
Denis V. Lunev5a3e55d2007-12-07 00:38:10 -0800299 dst->neighbour->dev = dst->dev;
Eric Dumazet64b7d962007-12-11 02:00:30 -0800300 dev_hold(dst->dev);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700301 dev_put(dev);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700302 }
303 }
304}
305
306static int dst_dev_event(struct notifier_block *this, unsigned long event, void *ptr)
307{
308 struct net_device *dev = ptr;
Eric Dumazet86bba262007-09-12 14:29:01 +0200309 struct dst_entry *dst, *last = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700310
Linus Torvalds1da177e2005-04-16 15:20:36 -0700311 switch (event) {
312 case NETDEV_UNREGISTER:
313 case NETDEV_DOWN:
Eric Dumazet86bba262007-09-12 14:29:01 +0200314 mutex_lock(&dst_gc_mutex);
315 for (dst = dst_busy_list; dst; dst = dst->next) {
316 last = dst;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700317 dst_ifdown(dst, dev, event != NETDEV_DOWN);
318 }
Eric Dumazet86bba262007-09-12 14:29:01 +0200319
320 spin_lock_bh(&dst_garbage.lock);
321 dst = dst_garbage.list;
322 dst_garbage.list = NULL;
323 spin_unlock_bh(&dst_garbage.lock);
324
325 if (last)
326 last->next = dst;
327 else
328 dst_busy_list = dst;
329 for (; dst; dst = dst->next) {
330 dst_ifdown(dst, dev, event != NETDEV_DOWN);
331 }
332 mutex_unlock(&dst_gc_mutex);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700333 break;
334 }
335 return NOTIFY_DONE;
336}
337
338static struct notifier_block dst_dev_notifier = {
339 .notifier_call = dst_dev_event,
340};
341
342void __init dst_init(void)
343{
344 register_netdevice_notifier(&dst_dev_notifier);
345}
346
347EXPORT_SYMBOL(__dst_free);
348EXPORT_SYMBOL(dst_alloc);
349EXPORT_SYMBOL(dst_destroy);