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 #include <net/dst_metadata.h> 26 27 /* 28 * Theory of operations: 29 * 1) We use a list, protected by a spinlock, to add 30 * new entries from both BH and non-BH context. 31 * 2) In order to keep spinlock held for a small delay, 32 * we use a second list where are stored long lived 33 * entries, that are handled by the garbage collect thread 34 * fired by a workqueue. 35 * 3) This list is guarded by a mutex, 36 * so that the gc_task and dst_dev_event() can be synchronized. 37 */ 38 39 /* 40 * We want to keep lock & list close together 41 * to dirty as few cache lines as possible in __dst_free(). 42 * As this is not a very strong hint, we dont force an alignment on SMP. 43 */ 44 static struct { 45 spinlock_t lock; 46 struct dst_entry *list; 47 unsigned long timer_inc; 48 unsigned long timer_expires; 49 } dst_garbage = { 50 .lock = __SPIN_LOCK_UNLOCKED(dst_garbage.lock), 51 .timer_inc = DST_GC_MAX, 52 }; 53 static void dst_gc_task(struct work_struct *work); 54 static void ___dst_free(struct dst_entry *dst); 55 56 static DECLARE_DELAYED_WORK(dst_gc_work, dst_gc_task); 57 58 static DEFINE_MUTEX(dst_gc_mutex); 59 /* 60 * long lived entries are maintained in this list, guarded by dst_gc_mutex 61 */ 62 static struct dst_entry *dst_busy_list; 63 64 static void dst_gc_task(struct work_struct *work) 65 { 66 int delayed = 0; 67 int work_performed = 0; 68 unsigned long expires = ~0L; 69 struct dst_entry *dst, *next, head; 70 struct dst_entry *last = &head; 71 72 mutex_lock(&dst_gc_mutex); 73 next = dst_busy_list; 74 75 loop: 76 while ((dst = next) != NULL) { 77 next = dst->next; 78 prefetch(&next->next); 79 cond_resched(); 80 if (likely(atomic_read(&dst->__refcnt))) { 81 last->next = dst; 82 last = dst; 83 delayed++; 84 continue; 85 } 86 work_performed++; 87 88 dst = dst_destroy(dst); 89 if (dst) { 90 /* NOHASH and still referenced. Unless it is already 91 * on gc list, invalidate it and add to gc list. 92 * 93 * Note: this is temporary. Actually, NOHASH dst's 94 * must be obsoleted when parent is obsoleted. 95 * But we do not have state "obsoleted, but 96 * referenced by parent", so it is right. 97 */ 98 if (dst->obsolete > 0) 99 continue; 100 101 ___dst_free(dst); 102 dst->next = next; 103 next = dst; 104 } 105 } 106 107 spin_lock_bh(&dst_garbage.lock); 108 next = dst_garbage.list; 109 if (next) { 110 dst_garbage.list = NULL; 111 spin_unlock_bh(&dst_garbage.lock); 112 goto loop; 113 } 114 last->next = NULL; 115 dst_busy_list = head.next; 116 if (!dst_busy_list) 117 dst_garbage.timer_inc = DST_GC_MAX; 118 else { 119 /* 120 * if we freed less than 1/10 of delayed entries, 121 * we can sleep longer. 122 */ 123 if (work_performed <= delayed/10) { 124 dst_garbage.timer_expires += dst_garbage.timer_inc; 125 if (dst_garbage.timer_expires > DST_GC_MAX) 126 dst_garbage.timer_expires = DST_GC_MAX; 127 dst_garbage.timer_inc += DST_GC_INC; 128 } else { 129 dst_garbage.timer_inc = DST_GC_INC; 130 dst_garbage.timer_expires = DST_GC_MIN; 131 } 132 expires = dst_garbage.timer_expires; 133 /* 134 * if the next desired timer is more than 4 seconds in the 135 * future then round the timer to whole seconds 136 */ 137 if (expires > 4*HZ) 138 expires = round_jiffies_relative(expires); 139 schedule_delayed_work(&dst_gc_work, expires); 140 } 141 142 spin_unlock_bh(&dst_garbage.lock); 143 mutex_unlock(&dst_gc_mutex); 144 } 145 146 int dst_discard_sk(struct sock *sk, struct sk_buff *skb) 147 { 148 kfree_skb(skb); 149 return 0; 150 } 151 EXPORT_SYMBOL(dst_discard_sk); 152 153 const u32 dst_default_metrics[RTAX_MAX + 1] = { 154 /* This initializer is needed to force linker to place this variable 155 * into const section. Otherwise it might end into bss section. 156 * We really want to avoid false sharing on this variable, and catch 157 * any writes on it. 158 */ 159 [RTAX_MAX] = 0xdeadbeef, 160 }; 161 162 void dst_init(struct dst_entry *dst, struct dst_ops *ops, 163 struct net_device *dev, int initial_ref, int initial_obsolete, 164 unsigned short flags) 165 { 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->from = NULL; 175 #ifdef CONFIG_XFRM 176 dst->xfrm = NULL; 177 #endif 178 dst->input = dst_discard; 179 dst->output = dst_discard_sk; 180 dst->error = 0; 181 dst->obsolete = initial_obsolete; 182 dst->header_len = 0; 183 dst->trailer_len = 0; 184 #ifdef CONFIG_IP_ROUTE_CLASSID 185 dst->tclassid = 0; 186 #endif 187 atomic_set(&dst->__refcnt, initial_ref); 188 dst->__use = 0; 189 dst->lastuse = jiffies; 190 dst->flags = flags; 191 dst->pending_confirm = 0; 192 dst->next = NULL; 193 if (!(flags & DST_NOCOUNT)) 194 dst_entries_add(ops, 1); 195 } 196 EXPORT_SYMBOL(dst_init); 197 198 void *dst_alloc(struct dst_ops *ops, struct net_device *dev, 199 int initial_ref, int initial_obsolete, unsigned short flags) 200 { 201 struct dst_entry *dst; 202 203 if (ops->gc && dst_entries_get_fast(ops) > ops->gc_thresh) { 204 if (ops->gc(ops)) 205 return NULL; 206 } 207 208 dst = kmem_cache_alloc(ops->kmem_cachep, GFP_ATOMIC); 209 if (!dst) 210 return NULL; 211 212 dst_init(dst, ops, dev, initial_ref, initial_obsolete, flags); 213 214 return dst; 215 } 216 EXPORT_SYMBOL(dst_alloc); 217 218 static void ___dst_free(struct dst_entry *dst) 219 { 220 /* The first case (dev==NULL) is required, when 221 protocol module is unloaded. 222 */ 223 if (dst->dev == NULL || !(dst->dev->flags&IFF_UP)) { 224 dst->input = dst_discard; 225 dst->output = dst_discard_sk; 226 } 227 dst->obsolete = DST_OBSOLETE_DEAD; 228 } 229 230 void __dst_free(struct dst_entry *dst) 231 { 232 spin_lock_bh(&dst_garbage.lock); 233 ___dst_free(dst); 234 dst->next = dst_garbage.list; 235 dst_garbage.list = dst; 236 if (dst_garbage.timer_inc > DST_GC_INC) { 237 dst_garbage.timer_inc = DST_GC_INC; 238 dst_garbage.timer_expires = DST_GC_MIN; 239 mod_delayed_work(system_wq, &dst_gc_work, 240 dst_garbage.timer_expires); 241 } 242 spin_unlock_bh(&dst_garbage.lock); 243 } 244 EXPORT_SYMBOL(__dst_free); 245 246 struct dst_entry *dst_destroy(struct dst_entry * dst) 247 { 248 struct dst_entry *child; 249 250 smp_rmb(); 251 252 again: 253 child = dst->child; 254 255 if (!(dst->flags & DST_NOCOUNT)) 256 dst_entries_add(dst->ops, -1); 257 258 if (dst->ops->destroy) 259 dst->ops->destroy(dst); 260 if (dst->dev) 261 dev_put(dst->dev); 262 263 if (dst->flags & DST_METADATA) 264 kfree(dst); 265 else 266 kmem_cache_free(dst->ops->kmem_cachep, dst); 267 268 dst = child; 269 if (dst) { 270 int nohash = dst->flags & DST_NOHASH; 271 272 if (atomic_dec_and_test(&dst->__refcnt)) { 273 /* We were real parent of this dst, so kill child. */ 274 if (nohash) 275 goto again; 276 } else { 277 /* Child is still referenced, return it for freeing. */ 278 if (nohash) 279 return dst; 280 /* Child is still in his hash table */ 281 } 282 } 283 return NULL; 284 } 285 EXPORT_SYMBOL(dst_destroy); 286 287 static void dst_destroy_rcu(struct rcu_head *head) 288 { 289 struct dst_entry *dst = container_of(head, struct dst_entry, rcu_head); 290 291 dst = dst_destroy(dst); 292 if (dst) 293 __dst_free(dst); 294 } 295 296 void dst_release(struct dst_entry *dst) 297 { 298 if (dst) { 299 int newrefcnt; 300 301 newrefcnt = atomic_dec_return(&dst->__refcnt); 302 if (unlikely(newrefcnt < 0)) 303 net_warn_ratelimited("%s: dst:%p refcnt:%d\n", 304 __func__, dst, newrefcnt); 305 if (unlikely(dst->flags & DST_NOCACHE) && !newrefcnt) 306 call_rcu(&dst->rcu_head, dst_destroy_rcu); 307 } 308 } 309 EXPORT_SYMBOL(dst_release); 310 311 u32 *dst_cow_metrics_generic(struct dst_entry *dst, unsigned long old) 312 { 313 u32 *p = kmalloc(sizeof(u32) * RTAX_MAX, GFP_ATOMIC); 314 315 if (p) { 316 u32 *old_p = __DST_METRICS_PTR(old); 317 unsigned long prev, new; 318 319 memcpy(p, old_p, sizeof(u32) * RTAX_MAX); 320 321 new = (unsigned long) p; 322 prev = cmpxchg(&dst->_metrics, old, new); 323 324 if (prev != old) { 325 kfree(p); 326 p = __DST_METRICS_PTR(prev); 327 if (prev & DST_METRICS_READ_ONLY) 328 p = NULL; 329 } 330 } 331 return p; 332 } 333 EXPORT_SYMBOL(dst_cow_metrics_generic); 334 335 /* Caller asserts that dst_metrics_read_only(dst) is false. */ 336 void __dst_destroy_metrics_generic(struct dst_entry *dst, unsigned long old) 337 { 338 unsigned long prev, new; 339 340 new = ((unsigned long) dst_default_metrics) | DST_METRICS_READ_ONLY; 341 prev = cmpxchg(&dst->_metrics, old, new); 342 if (prev == old) 343 kfree(__DST_METRICS_PTR(old)); 344 } 345 EXPORT_SYMBOL(__dst_destroy_metrics_generic); 346 347 static struct dst_ops md_dst_ops = { 348 .family = AF_UNSPEC, 349 }; 350 351 static int dst_md_discard_sk(struct sock *sk, struct sk_buff *skb) 352 { 353 WARN_ONCE(1, "Attempting to call output on metadata dst\n"); 354 kfree_skb(skb); 355 return 0; 356 } 357 358 static int dst_md_discard(struct sk_buff *skb) 359 { 360 WARN_ONCE(1, "Attempting to call input on metadata dst\n"); 361 kfree_skb(skb); 362 return 0; 363 } 364 365 static void __metadata_dst_init(struct metadata_dst *md_dst, u8 optslen) 366 { 367 struct dst_entry *dst; 368 369 dst = &md_dst->dst; 370 dst_init(dst, &md_dst_ops, NULL, 1, DST_OBSOLETE_NONE, 371 DST_METADATA | DST_NOCACHE | DST_NOCOUNT); 372 373 dst->input = dst_md_discard; 374 dst->output = dst_md_discard_sk; 375 376 memset(dst + 1, 0, sizeof(*md_dst) + optslen - sizeof(*dst)); 377 md_dst->opts_len = optslen; 378 } 379 380 struct metadata_dst *metadata_dst_alloc(u8 optslen, gfp_t flags) 381 { 382 struct metadata_dst *md_dst; 383 384 md_dst = kmalloc(sizeof(*md_dst) + optslen, flags); 385 if (!md_dst) 386 return NULL; 387 388 __metadata_dst_init(md_dst, optslen); 389 390 return md_dst; 391 } 392 EXPORT_SYMBOL_GPL(metadata_dst_alloc); 393 394 struct metadata_dst __percpu *metadata_dst_alloc_percpu(u8 optslen, gfp_t flags) 395 { 396 int cpu; 397 struct metadata_dst __percpu *md_dst; 398 399 md_dst = __alloc_percpu_gfp(sizeof(struct metadata_dst) + optslen, 400 __alignof__(struct metadata_dst), flags); 401 if (!md_dst) 402 return NULL; 403 404 for_each_possible_cpu(cpu) 405 __metadata_dst_init(per_cpu_ptr(md_dst, cpu), optslen); 406 407 return md_dst; 408 } 409 EXPORT_SYMBOL_GPL(metadata_dst_alloc_percpu); 410 411 /* Dirty hack. We did it in 2.2 (in __dst_free), 412 * we have _very_ good reasons not to repeat 413 * this mistake in 2.3, but we have no choice 414 * now. _It_ _is_ _explicit_ _deliberate_ 415 * _race_ _condition_. 416 * 417 * Commented and originally written by Alexey. 418 */ 419 static void dst_ifdown(struct dst_entry *dst, struct net_device *dev, 420 int unregister) 421 { 422 if (dst->ops->ifdown) 423 dst->ops->ifdown(dst, dev, unregister); 424 425 if (dev != dst->dev) 426 return; 427 428 if (!unregister) { 429 dst->input = dst_discard; 430 dst->output = dst_discard_sk; 431 } else { 432 dst->dev = dev_net(dst->dev)->loopback_dev; 433 dev_hold(dst->dev); 434 dev_put(dev); 435 } 436 } 437 438 static int dst_dev_event(struct notifier_block *this, unsigned long event, 439 void *ptr) 440 { 441 struct net_device *dev = netdev_notifier_info_to_dev(ptr); 442 struct dst_entry *dst, *last = NULL; 443 444 switch (event) { 445 case NETDEV_UNREGISTER_FINAL: 446 case NETDEV_DOWN: 447 mutex_lock(&dst_gc_mutex); 448 for (dst = dst_busy_list; dst; dst = dst->next) { 449 last = dst; 450 dst_ifdown(dst, dev, event != NETDEV_DOWN); 451 } 452 453 spin_lock_bh(&dst_garbage.lock); 454 dst = dst_garbage.list; 455 dst_garbage.list = NULL; 456 spin_unlock_bh(&dst_garbage.lock); 457 458 if (last) 459 last->next = dst; 460 else 461 dst_busy_list = dst; 462 for (; dst; dst = dst->next) 463 dst_ifdown(dst, dev, event != NETDEV_DOWN); 464 mutex_unlock(&dst_gc_mutex); 465 break; 466 } 467 return NOTIFY_DONE; 468 } 469 470 static struct notifier_block dst_dev_notifier = { 471 .notifier_call = dst_dev_event, 472 .priority = -10, /* must be called after other network notifiers */ 473 }; 474 475 void __init dst_subsys_init(void) 476 { 477 register_netdevice_notifier(&dst_dev_notifier); 478 } 479