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#if RT_CACHE_DEBUG >= 2 37static atomic_t dst_total = ATOMIC_INIT(0); 38#endif 39 40/* 41 * We want to keep lock & list close together 42 * to dirty as few cache lines as possible in __dst_free(). 43 * As this is not a very strong hint, we dont force an alignment on SMP. 44 */ 45static struct { 46 spinlock_t lock; 47 struct dst_entry *list; 48 unsigned long timer_inc; 49 unsigned long timer_expires; 50} dst_garbage = { 51 .lock = __SPIN_LOCK_UNLOCKED(dst_garbage.lock), 52 .timer_inc = DST_GC_MAX, 53}; 54static void dst_gc_task(struct work_struct *work); 55static void ___dst_free(struct dst_entry *dst); 56 57static DECLARE_DELAYED_WORK(dst_gc_work, dst_gc_task); 58 59static DEFINE_MUTEX(dst_gc_mutex); 60/* 61 * long lived entries are maintained in this list, guarded by dst_gc_mutex 62 */ 63static struct dst_entry *dst_busy_list; 64 65static void dst_gc_task(struct work_struct *work) 66{ 67 int delayed = 0; 68 int work_performed = 0; 69 unsigned long expires = ~0L; 70 struct dst_entry *dst, *next, head; 71 struct dst_entry *last = &head; 72#if RT_CACHE_DEBUG >= 2 73 ktime_t time_start = ktime_get(); 74 struct timespec elapsed; 75#endif 76 77 mutex_lock(&dst_gc_mutex); 78 next = dst_busy_list; 79 80loop: 81 while ((dst = next) != NULL) { 82 next = dst->next; 83 prefetch(&next->next); 84 cond_resched(); 85 if (likely(atomic_read(&dst->__refcnt))) { 86 last->next = dst; 87 last = dst; 88 delayed++; 89 continue; 90 } 91 work_performed++; 92 93 dst = dst_destroy(dst); 94 if (dst) { 95 /* NOHASH and still referenced. Unless it is already 96 * on gc list, invalidate it and add to gc list. 97 * 98 * Note: this is temporary. Actually, NOHASH dst's 99 * must be obsoleted when parent is obsoleted. 100 * But we do not have state "obsoleted, but 101 * referenced by parent", so it is right. 102 */ 103 if (dst->obsolete > 1) 104 continue; 105 106 ___dst_free(dst); 107 dst->next = next; 108 next = dst; 109 } 110 } 111 112 spin_lock_bh(&dst_garbage.lock); 113 next = dst_garbage.list; 114 if (next) { 115 dst_garbage.list = NULL; 116 spin_unlock_bh(&dst_garbage.lock); 117 goto loop; 118 } 119 last->next = NULL; 120 dst_busy_list = head.next; 121 if (!dst_busy_list) 122 dst_garbage.timer_inc = DST_GC_MAX; 123 else { 124 /* 125 * if we freed less than 1/10 of delayed entries, 126 * we can sleep longer. 127 */ 128 if (work_performed <= delayed/10) { 129 dst_garbage.timer_expires += dst_garbage.timer_inc; 130 if (dst_garbage.timer_expires > DST_GC_MAX) 131 dst_garbage.timer_expires = DST_GC_MAX; 132 dst_garbage.timer_inc += DST_GC_INC; 133 } else { 134 dst_garbage.timer_inc = DST_GC_INC; 135 dst_garbage.timer_expires = DST_GC_MIN; 136 } 137 expires = dst_garbage.timer_expires; 138 /* 139 * if the next desired timer is more than 4 seconds in the 140 * future then round the timer to whole seconds 141 */ 142 if (expires > 4*HZ) 143 expires = round_jiffies_relative(expires); 144 schedule_delayed_work(&dst_gc_work, expires); 145 } 146 147 spin_unlock_bh(&dst_garbage.lock); 148 mutex_unlock(&dst_gc_mutex); 149#if RT_CACHE_DEBUG >= 2 150 elapsed = ktime_to_timespec(ktime_sub(ktime_get(), time_start)); 151 printk(KERN_DEBUG "dst_total: %d delayed: %d work_perf: %d" 152 " expires: %lu elapsed: %lu us\n", 153 atomic_read(&dst_total), delayed, work_performed, 154 expires, 155 elapsed.tv_sec * USEC_PER_SEC + 156 elapsed.tv_nsec / NSEC_PER_USEC); 157#endif 158} 159 160int dst_discard(struct sk_buff *skb) 161{ 162 kfree_skb(skb); 163 return 0; 164} 165EXPORT_SYMBOL(dst_discard); 166 167void *dst_alloc(struct dst_ops *ops) 168{ 169 struct dst_entry *dst; 170 171 if (ops->gc && atomic_read(&ops->entries) > ops->gc_thresh) { 172 if (ops->gc(ops)) 173 return NULL; 174 } 175 dst = kmem_cache_zalloc(ops->kmem_cachep, GFP_ATOMIC); 176 if (!dst) 177 return NULL; 178 atomic_set(&dst->__refcnt, 0); 179 dst->ops = ops; 180 dst->lastuse = jiffies; 181 dst->path = dst; 182 dst->input = dst->output = dst_discard; 183#if RT_CACHE_DEBUG >= 2 184 atomic_inc(&dst_total); 185#endif 186 atomic_inc(&ops->entries); 187 return dst; 188} 189EXPORT_SYMBOL(dst_alloc); 190 191static void ___dst_free(struct dst_entry *dst) 192{ 193 /* The first case (dev==NULL) is required, when 194 protocol module is unloaded. 195 */ 196 if (dst->dev == NULL || !(dst->dev->flags&IFF_UP)) 197 dst->input = dst->output = dst_discard; 198 dst->obsolete = 2; 199} 200 201void __dst_free(struct dst_entry *dst) 202{ 203 spin_lock_bh(&dst_garbage.lock); 204 ___dst_free(dst); 205 dst->next = dst_garbage.list; 206 dst_garbage.list = dst; 207 if (dst_garbage.timer_inc > DST_GC_INC) { 208 dst_garbage.timer_inc = DST_GC_INC; 209 dst_garbage.timer_expires = DST_GC_MIN; 210 cancel_delayed_work(&dst_gc_work); 211 schedule_delayed_work(&dst_gc_work, dst_garbage.timer_expires); 212 } 213 spin_unlock_bh(&dst_garbage.lock); 214} 215EXPORT_SYMBOL(__dst_free); 216 217struct dst_entry *dst_destroy(struct dst_entry * dst) 218{ 219 struct dst_entry *child; 220 struct neighbour *neigh; 221 struct hh_cache *hh; 222 223 smp_rmb(); 224 225again: 226 neigh = dst->neighbour; 227 hh = dst->hh; 228 child = dst->child; 229 230 dst->hh = NULL; 231 if (hh && atomic_dec_and_test(&hh->hh_refcnt)) 232 kfree(hh); 233 234 if (neigh) { 235 dst->neighbour = NULL; 236 neigh_release(neigh); 237 } 238 239 atomic_dec(&dst->ops->entries); 240 241 if (dst->ops->destroy) 242 dst->ops->destroy(dst); 243 if (dst->dev) 244 dev_put(dst->dev); 245#if RT_CACHE_DEBUG >= 2 246 atomic_dec(&dst_total); 247#endif 248 kmem_cache_free(dst->ops->kmem_cachep, dst); 249 250 dst = child; 251 if (dst) { 252 int nohash = dst->flags & DST_NOHASH; 253 254 if (atomic_dec_and_test(&dst->__refcnt)) { 255 /* We were real parent of this dst, so kill child. */ 256 if (nohash) 257 goto again; 258 } else { 259 /* Child is still referenced, return it for freeing. */ 260 if (nohash) 261 return dst; 262 /* Child is still in his hash table */ 263 } 264 } 265 return NULL; 266} 267EXPORT_SYMBOL(dst_destroy); 268 269void dst_release(struct dst_entry *dst) 270{ 271 if (dst) { 272 int newrefcnt; 273 274 smp_mb__before_atomic_dec(); 275 newrefcnt = atomic_dec_return(&dst->__refcnt); 276 WARN_ON(newrefcnt < 0); 277 } 278} 279EXPORT_SYMBOL(dst_release); 280 281/* Dirty hack. We did it in 2.2 (in __dst_free), 282 * we have _very_ good reasons not to repeat 283 * this mistake in 2.3, but we have no choice 284 * now. _It_ _is_ _explicit_ _deliberate_ 285 * _race_ _condition_. 286 * 287 * Commented and originally written by Alexey. 288 */ 289static void dst_ifdown(struct dst_entry *dst, struct net_device *dev, 290 int unregister) 291{ 292 if (dst->ops->ifdown) 293 dst->ops->ifdown(dst, dev, unregister); 294 295 if (dev != dst->dev) 296 return; 297 298 if (!unregister) { 299 dst->input = dst->output = dst_discard; 300 } else { 301 dst->dev = dev_net(dst->dev)->loopback_dev; 302 dev_hold(dst->dev); 303 dev_put(dev); 304 if (dst->neighbour && dst->neighbour->dev == dev) { 305 dst->neighbour->dev = dst->dev; 306 dev_hold(dst->dev); 307 dev_put(dev); 308 } 309 } 310} 311 312static int dst_dev_event(struct notifier_block *this, unsigned long event, 313 void *ptr) 314{ 315 struct net_device *dev = ptr; 316 struct dst_entry *dst, *last = NULL; 317 318 switch (event) { 319 case NETDEV_UNREGISTER: 320 case NETDEV_DOWN: 321 mutex_lock(&dst_gc_mutex); 322 for (dst = dst_busy_list; dst; dst = dst->next) { 323 last = dst; 324 dst_ifdown(dst, dev, event != NETDEV_DOWN); 325 } 326 327 spin_lock_bh(&dst_garbage.lock); 328 dst = dst_garbage.list; 329 dst_garbage.list = NULL; 330 spin_unlock_bh(&dst_garbage.lock); 331 332 if (last) 333 last->next = dst; 334 else 335 dst_busy_list = dst; 336 for (; dst; dst = dst->next) 337 dst_ifdown(dst, dev, event != NETDEV_DOWN); 338 mutex_unlock(&dst_gc_mutex); 339 break; 340 } 341 return NOTIFY_DONE; 342} 343 344static struct notifier_block dst_dev_notifier = { 345 .notifier_call = dst_dev_event, 346 .priority = -10, /* must be called after other network notifiers */ 347}; 348 349void __init dst_init(void) 350{ 351 register_netdevice_notifier(&dst_dev_notifier); 352} 353