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 #include <linux/prefetch.h> 23 24 #include <net/dst.h> 25 26 /* 27 * Theory of operations: 28 * 1) We use a list, protected by a spinlock, to add 29 * new entries from both BH and non-BH context. 30 * 2) In order to keep spinlock held for a small delay, 31 * we use a second list where are stored long lived 32 * entries, that are handled by the garbage collect thread 33 * fired by a workqueue. 34 * 3) This list is guarded by a mutex, 35 * so that the gc_task and dst_dev_event() can be synchronized. 36 */ 37 38 /* 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 */ 43 static 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 }; 52 static void dst_gc_task(struct work_struct *work); 53 static void ___dst_free(struct dst_entry *dst); 54 55 static DECLARE_DELAYED_WORK(dst_gc_work, dst_gc_task); 56 57 static DEFINE_MUTEX(dst_gc_mutex); 58 /* 59 * long lived entries are maintained in this list, guarded by dst_gc_mutex 60 */ 61 static struct dst_entry *dst_busy_list; 62 63 static void dst_gc_task(struct work_struct *work) 64 { 65 int delayed = 0; 66 int work_performed = 0; 67 unsigned long expires = ~0L; 68 struct dst_entry *dst, *next, head; 69 struct dst_entry *last = &head; 70 71 mutex_lock(&dst_gc_mutex); 72 next = dst_busy_list; 73 74 loop: 75 while ((dst = next) != NULL) { 76 next = dst->next; 77 prefetch(&next->next); 78 cond_resched(); 79 if (likely(atomic_read(&dst->__refcnt))) { 80 last->next = dst; 81 last = dst; 82 delayed++; 83 continue; 84 } 85 work_performed++; 86 87 dst = dst_destroy(dst); 88 if (dst) { 89 /* NOHASH and still referenced. Unless it is already 90 * on gc list, invalidate it and add to gc list. 91 * 92 * Note: this is temporary. Actually, NOHASH dst's 93 * must be obsoleted when parent is obsoleted. 94 * But we do not have state "obsoleted, but 95 * referenced by parent", so it is right. 96 */ 97 if (dst->obsolete > 1) 98 continue; 99 100 ___dst_free(dst); 101 dst->next = next; 102 next = dst; 103 } 104 } 105 106 spin_lock_bh(&dst_garbage.lock); 107 next = dst_garbage.list; 108 if (next) { 109 dst_garbage.list = NULL; 110 spin_unlock_bh(&dst_garbage.lock); 111 goto loop; 112 } 113 last->next = NULL; 114 dst_busy_list = head.next; 115 if (!dst_busy_list) 116 dst_garbage.timer_inc = DST_GC_MAX; 117 else { 118 /* 119 * if we freed less than 1/10 of delayed entries, 120 * we can sleep longer. 121 */ 122 if (work_performed <= delayed/10) { 123 dst_garbage.timer_expires += dst_garbage.timer_inc; 124 if (dst_garbage.timer_expires > DST_GC_MAX) 125 dst_garbage.timer_expires = DST_GC_MAX; 126 dst_garbage.timer_inc += DST_GC_INC; 127 } else { 128 dst_garbage.timer_inc = DST_GC_INC; 129 dst_garbage.timer_expires = DST_GC_MIN; 130 } 131 expires = dst_garbage.timer_expires; 132 /* 133 * if the next desired timer is more than 4 seconds in the 134 * future then round the timer to whole seconds 135 */ 136 if (expires > 4*HZ) 137 expires = round_jiffies_relative(expires); 138 schedule_delayed_work(&dst_gc_work, expires); 139 } 140 141 spin_unlock_bh(&dst_garbage.lock); 142 mutex_unlock(&dst_gc_mutex); 143 } 144 145 int dst_discard(struct sk_buff *skb) 146 { 147 kfree_skb(skb); 148 return 0; 149 } 150 EXPORT_SYMBOL(dst_discard); 151 152 const u32 dst_default_metrics[RTAX_MAX]; 153 154 void *dst_alloc(struct dst_ops *ops, struct net_device *dev, 155 int initial_ref, int initial_obsolete, int flags) 156 { 157 struct dst_entry *dst; 158 159 if (ops->gc && dst_entries_get_fast(ops) > ops->gc_thresh) { 160 if (ops->gc(ops)) 161 return NULL; 162 } 163 dst = kmem_cache_alloc(ops->kmem_cachep, GFP_ATOMIC); 164 if (!dst) 165 return NULL; 166 dst->child = NULL; 167 dst->dev = dev; 168 if (dev) 169 dev_hold(dev); 170 dst->ops = ops; 171 dst_init_metrics(dst, dst_default_metrics, true); 172 dst->expires = 0UL; 173 dst->path = dst; 174 dst->neighbour = NULL; 175 dst->hh = NULL; 176 #ifdef CONFIG_XFRM 177 dst->xfrm = NULL; 178 #endif 179 dst->input = dst_discard; 180 dst->output = dst_discard; 181 dst->error = 0; 182 dst->obsolete = initial_obsolete; 183 dst->header_len = 0; 184 dst->trailer_len = 0; 185 #ifdef CONFIG_IP_ROUTE_CLASSID 186 dst->tclassid = 0; 187 #endif 188 atomic_set(&dst->__refcnt, initial_ref); 189 dst->__use = 0; 190 dst->lastuse = jiffies; 191 dst->flags = flags; 192 dst->next = NULL; 193 if (!(flags & DST_NOCOUNT)) 194 dst_entries_add(ops, 1); 195 return dst; 196 } 197 EXPORT_SYMBOL(dst_alloc); 198 199 static void ___dst_free(struct dst_entry *dst) 200 { 201 /* The first case (dev==NULL) is required, when 202 protocol module is unloaded. 203 */ 204 if (dst->dev == NULL || !(dst->dev->flags&IFF_UP)) 205 dst->input = dst->output = dst_discard; 206 dst->obsolete = 2; 207 } 208 209 void __dst_free(struct dst_entry *dst) 210 { 211 spin_lock_bh(&dst_garbage.lock); 212 ___dst_free(dst); 213 dst->next = dst_garbage.list; 214 dst_garbage.list = dst; 215 if (dst_garbage.timer_inc > DST_GC_INC) { 216 dst_garbage.timer_inc = DST_GC_INC; 217 dst_garbage.timer_expires = DST_GC_MIN; 218 cancel_delayed_work(&dst_gc_work); 219 schedule_delayed_work(&dst_gc_work, dst_garbage.timer_expires); 220 } 221 spin_unlock_bh(&dst_garbage.lock); 222 } 223 EXPORT_SYMBOL(__dst_free); 224 225 struct dst_entry *dst_destroy(struct dst_entry * dst) 226 { 227 struct dst_entry *child; 228 struct neighbour *neigh; 229 struct hh_cache *hh; 230 231 smp_rmb(); 232 233 again: 234 neigh = dst->neighbour; 235 hh = dst->hh; 236 child = dst->child; 237 238 dst->hh = NULL; 239 if (hh) 240 hh_cache_put(hh); 241 242 if (neigh) { 243 dst->neighbour = NULL; 244 neigh_release(neigh); 245 } 246 247 if (!(dst->flags & DST_NOCOUNT)) 248 dst_entries_add(dst->ops, -1); 249 250 if (dst->ops->destroy) 251 dst->ops->destroy(dst); 252 if (dst->dev) 253 dev_put(dst->dev); 254 kmem_cache_free(dst->ops->kmem_cachep, dst); 255 256 dst = child; 257 if (dst) { 258 int nohash = dst->flags & DST_NOHASH; 259 260 if (atomic_dec_and_test(&dst->__refcnt)) { 261 /* We were real parent of this dst, so kill child. */ 262 if (nohash) 263 goto again; 264 } else { 265 /* Child is still referenced, return it for freeing. */ 266 if (nohash) 267 return dst; 268 /* Child is still in his hash table */ 269 } 270 } 271 return NULL; 272 } 273 EXPORT_SYMBOL(dst_destroy); 274 275 void dst_release(struct dst_entry *dst) 276 { 277 if (dst) { 278 int newrefcnt; 279 280 newrefcnt = atomic_dec_return(&dst->__refcnt); 281 WARN_ON(newrefcnt < 0); 282 if (unlikely(dst->flags & DST_NOCACHE) && !newrefcnt) { 283 dst = dst_destroy(dst); 284 if (dst) 285 __dst_free(dst); 286 } 287 } 288 } 289 EXPORT_SYMBOL(dst_release); 290 291 u32 *dst_cow_metrics_generic(struct dst_entry *dst, unsigned long old) 292 { 293 u32 *p = kmalloc(sizeof(u32) * RTAX_MAX, GFP_ATOMIC); 294 295 if (p) { 296 u32 *old_p = __DST_METRICS_PTR(old); 297 unsigned long prev, new; 298 299 memcpy(p, old_p, sizeof(u32) * RTAX_MAX); 300 301 new = (unsigned long) p; 302 prev = cmpxchg(&dst->_metrics, old, new); 303 304 if (prev != old) { 305 kfree(p); 306 p = __DST_METRICS_PTR(prev); 307 if (prev & DST_METRICS_READ_ONLY) 308 p = NULL; 309 } 310 } 311 return p; 312 } 313 EXPORT_SYMBOL(dst_cow_metrics_generic); 314 315 /* Caller asserts that dst_metrics_read_only(dst) is false. */ 316 void __dst_destroy_metrics_generic(struct dst_entry *dst, unsigned long old) 317 { 318 unsigned long prev, new; 319 320 new = ((unsigned long) dst_default_metrics) | DST_METRICS_READ_ONLY; 321 prev = cmpxchg(&dst->_metrics, old, new); 322 if (prev == old) 323 kfree(__DST_METRICS_PTR(old)); 324 } 325 EXPORT_SYMBOL(__dst_destroy_metrics_generic); 326 327 /** 328 * skb_dst_set_noref - sets skb dst, without a reference 329 * @skb: buffer 330 * @dst: dst entry 331 * 332 * Sets skb dst, assuming a reference was not taken on dst 333 * skb_dst_drop() should not dst_release() this dst 334 */ 335 void skb_dst_set_noref(struct sk_buff *skb, struct dst_entry *dst) 336 { 337 WARN_ON(!rcu_read_lock_held() && !rcu_read_lock_bh_held()); 338 /* If dst not in cache, we must take a reference, because 339 * dst_release() will destroy dst as soon as its refcount becomes zero 340 */ 341 if (unlikely(dst->flags & DST_NOCACHE)) { 342 dst_hold(dst); 343 skb_dst_set(skb, dst); 344 } else { 345 skb->_skb_refdst = (unsigned long)dst | SKB_DST_NOREF; 346 } 347 } 348 EXPORT_SYMBOL(skb_dst_set_noref); 349 350 /* Dirty hack. We did it in 2.2 (in __dst_free), 351 * we have _very_ good reasons not to repeat 352 * this mistake in 2.3, but we have no choice 353 * now. _It_ _is_ _explicit_ _deliberate_ 354 * _race_ _condition_. 355 * 356 * Commented and originally written by Alexey. 357 */ 358 static void dst_ifdown(struct dst_entry *dst, struct net_device *dev, 359 int unregister) 360 { 361 if (dst->ops->ifdown) 362 dst->ops->ifdown(dst, dev, unregister); 363 364 if (dev != dst->dev) 365 return; 366 367 if (!unregister) { 368 dst->input = dst->output = dst_discard; 369 } else { 370 dst->dev = dev_net(dst->dev)->loopback_dev; 371 dev_hold(dst->dev); 372 dev_put(dev); 373 if (dst->neighbour && dst->neighbour->dev == dev) { 374 dst->neighbour->dev = dst->dev; 375 dev_hold(dst->dev); 376 dev_put(dev); 377 } 378 } 379 } 380 381 static int dst_dev_event(struct notifier_block *this, unsigned long event, 382 void *ptr) 383 { 384 struct net_device *dev = ptr; 385 struct dst_entry *dst, *last = NULL; 386 387 switch (event) { 388 case NETDEV_UNREGISTER: 389 case NETDEV_DOWN: 390 mutex_lock(&dst_gc_mutex); 391 for (dst = dst_busy_list; dst; dst = dst->next) { 392 last = dst; 393 dst_ifdown(dst, dev, event != NETDEV_DOWN); 394 } 395 396 spin_lock_bh(&dst_garbage.lock); 397 dst = dst_garbage.list; 398 dst_garbage.list = NULL; 399 spin_unlock_bh(&dst_garbage.lock); 400 401 if (last) 402 last->next = dst; 403 else 404 dst_busy_list = dst; 405 for (; dst; dst = dst->next) 406 dst_ifdown(dst, dev, event != NETDEV_DOWN); 407 mutex_unlock(&dst_gc_mutex); 408 break; 409 } 410 return NOTIFY_DONE; 411 } 412 413 static struct notifier_block dst_dev_notifier = { 414 .notifier_call = dst_dev_event, 415 .priority = -10, /* must be called after other network notifiers */ 416 }; 417 418 void __init dst_init(void) 419 { 420 register_netdevice_notifier(&dst_dev_notifier); 421 } 422