blob: 7deef483c79f263959c0c1dac148529ecc80d73c [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;
206 schedule_delayed_work(&dst_gc_work, dst_garbage.timer_expires);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700207 }
Eric Dumazet86bba262007-09-12 14:29:01 +0200208 spin_unlock_bh(&dst_garbage.lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700209}
210
211struct dst_entry *dst_destroy(struct dst_entry * dst)
212{
213 struct dst_entry *child;
214 struct neighbour *neigh;
215 struct hh_cache *hh;
216
217 smp_rmb();
218
219again:
220 neigh = dst->neighbour;
221 hh = dst->hh;
222 child = dst->child;
223
224 dst->hh = NULL;
225 if (hh && atomic_dec_and_test(&hh->hh_refcnt))
226 kfree(hh);
227
228 if (neigh) {
229 dst->neighbour = NULL;
230 neigh_release(neigh);
231 }
232
233 atomic_dec(&dst->ops->entries);
234
235 if (dst->ops->destroy)
236 dst->ops->destroy(dst);
237 if (dst->dev)
238 dev_put(dst->dev);
YOSHIFUJI Hideaki4ec93ed2007-02-09 23:24:36 +0900239#if RT_CACHE_DEBUG >= 2
Linus Torvalds1da177e2005-04-16 15:20:36 -0700240 atomic_dec(&dst_total);
241#endif
242 kmem_cache_free(dst->ops->kmem_cachep, dst);
243
244 dst = child;
245 if (dst) {
Herbert Xu6775cab2005-04-16 15:24:10 -0700246 int nohash = dst->flags & DST_NOHASH;
247
Linus Torvalds1da177e2005-04-16 15:20:36 -0700248 if (atomic_dec_and_test(&dst->__refcnt)) {
249 /* We were real parent of this dst, so kill child. */
Herbert Xu6775cab2005-04-16 15:24:10 -0700250 if (nohash)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700251 goto again;
252 } else {
253 /* Child is still referenced, return it for freeing. */
Herbert Xu6775cab2005-04-16 15:24:10 -0700254 if (nohash)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700255 return dst;
256 /* Child is still in his hash table */
257 }
258 }
259 return NULL;
260}
261
262/* Dirty hack. We did it in 2.2 (in __dst_free),
263 * we have _very_ good reasons not to repeat
264 * this mistake in 2.3, but we have no choice
265 * now. _It_ _is_ _explicit_ _deliberate_
266 * _race_ _condition_.
267 *
268 * Commented and originally written by Alexey.
269 */
270static inline void dst_ifdown(struct dst_entry *dst, struct net_device *dev,
271 int unregister)
272{
273 if (dst->ops->ifdown)
274 dst->ops->ifdown(dst, dev, unregister);
275
276 if (dev != dst->dev)
277 return;
278
279 if (!unregister) {
Denis Chengc4b10102007-06-05 00:06:57 -0700280 dst->input = dst->output = dst_discard;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700281 } else {
Denis V. Lunev5a3e55d2007-12-07 00:38:10 -0800282 dst->dev = dst->dev->nd_net->loopback_dev;
Daniel Lezcanode3cb742007-09-25 19:16:28 -0700283 dev_hold(dst->dev);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700284 dev_put(dev);
285 if (dst->neighbour && dst->neighbour->dev == dev) {
Denis V. Lunev5a3e55d2007-12-07 00:38:10 -0800286 dst->neighbour->dev = dst->dev;
Eric Dumazet64b7d962007-12-11 02:00:30 -0800287 dev_hold(dst->dev);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700288 dev_put(dev);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700289 }
290 }
291}
292
293static int dst_dev_event(struct notifier_block *this, unsigned long event, void *ptr)
294{
295 struct net_device *dev = ptr;
Eric Dumazet86bba262007-09-12 14:29:01 +0200296 struct dst_entry *dst, *last = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700297
Eric W. Biedermane9dc8652007-09-12 13:02:17 +0200298 if (dev->nd_net != &init_net)
299 return NOTIFY_DONE;
300
Linus Torvalds1da177e2005-04-16 15:20:36 -0700301 switch (event) {
302 case NETDEV_UNREGISTER:
303 case NETDEV_DOWN:
Eric Dumazet86bba262007-09-12 14:29:01 +0200304 mutex_lock(&dst_gc_mutex);
305 for (dst = dst_busy_list; dst; dst = dst->next) {
306 last = dst;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700307 dst_ifdown(dst, dev, event != NETDEV_DOWN);
308 }
Eric Dumazet86bba262007-09-12 14:29:01 +0200309
310 spin_lock_bh(&dst_garbage.lock);
311 dst = dst_garbage.list;
312 dst_garbage.list = NULL;
313 spin_unlock_bh(&dst_garbage.lock);
314
315 if (last)
316 last->next = dst;
317 else
318 dst_busy_list = dst;
319 for (; dst; dst = dst->next) {
320 dst_ifdown(dst, dev, event != NETDEV_DOWN);
321 }
322 mutex_unlock(&dst_gc_mutex);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700323 break;
324 }
325 return NOTIFY_DONE;
326}
327
328static struct notifier_block dst_dev_notifier = {
329 .notifier_call = dst_dev_event,
330};
331
332void __init dst_init(void)
333{
334 register_netdevice_notifier(&dst_dev_notifier);
335}
336
337EXPORT_SYMBOL(__dst_free);
338EXPORT_SYMBOL(dst_alloc);
339EXPORT_SYMBOL(dst_destroy);