1 /* 2 * Copyright 1994, 1995 Massachusetts Institute of Technology 3 * 4 * Permission to use, copy, modify, and distribute this software and 5 * its documentation for any purpose and without fee is hereby 6 * granted, provided that both the above copyright notice and this 7 * permission notice appear in all copies, that both the above 8 * copyright notice and this permission notice appear in all 9 * supporting documentation, and that the name of M.I.T. not be used 10 * in advertising or publicity pertaining to distribution of the 11 * software without specific, written prior permission. M.I.T. makes 12 * no representations about the suitability of this software for any 13 * purpose. It is provided "as is" without express or implied 14 * warranty. 15 * 16 * THIS SOFTWARE IS PROVIDED BY M.I.T. ``AS IS''. M.I.T. DISCLAIMS 17 * ALL EXPRESS OR IMPLIED WARRANTIES WITH REGARD TO THIS SOFTWARE, 18 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 19 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. IN NO EVENT 20 * SHALL M.I.T. BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF 23 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 24 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 25 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 26 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27 * SUCH DAMAGE. 28 * 29 * $Id: in_rmx.c,v 1.22 1995/12/19 20:46:13 wollman Exp $ 30 */ 31 32 /* 33 * This code does two things necessary for the enhanced TCP metrics to 34 * function in a useful manner: 35 * 1) It marks all non-host routes as `cloning', thus ensuring that 36 * every actual reference to such a route actually gets turned 37 * into a reference to a host route to the specific destination 38 * requested. 39 * 2) When such routes lose all their references, it arranges for them 40 * to be deleted in some random collection of circumstances, so that 41 * a large quantity of stale routing data is not kept in kernel memory 42 * indefinitely. See in_rtqtimo() below for the exact mechanism. 43 */ 44 45 #include <sys/param.h> 46 #include <sys/systm.h> 47 #include <sys/kernel.h> 48 #include <sys/sysctl.h> 49 #include <sys/queue.h> 50 #include <sys/socket.h> 51 #include <sys/socketvar.h> 52 #include <sys/mbuf.h> 53 #include <sys/syslog.h> 54 55 #include <net/if.h> 56 #include <net/route.h> 57 #include <netinet/in.h> 58 #include <netinet/in_systm.h> 59 #include <netinet/in_var.h> 60 61 #include <netinet/ip.h> 62 #include <netinet/ip_var.h> 63 64 #include <netinet/tcp.h> 65 #include <netinet/tcp_seq.h> 66 #include <netinet/tcp_timer.h> 67 #include <netinet/tcp_var.h> 68 #if 0 69 #include <netinet/tcpip.h> 70 #endif 71 72 extern int in_inithead __P((void **head, int off)); 73 74 #define RTPRF_OURS RTF_PROTO3 /* set on routes we manage */ 75 76 /* 77 * Do what we need to do when inserting a route. 78 */ 79 static struct radix_node * 80 in_addroute(void *v_arg, void *n_arg, struct radix_node_head *head, 81 struct radix_node *treenodes) 82 { 83 struct rtentry *rt = (struct rtentry *)treenodes; 84 struct sockaddr_in *sin = (struct sockaddr_in *)rt_key(rt); 85 struct radix_node *ret; 86 87 /* 88 * For IP, all unicast non-host routes are automatically cloning. 89 */ 90 if(!(rt->rt_flags & (RTF_HOST | RTF_CLONING))) { 91 if(!IN_MULTICAST(ntohl(sin->sin_addr.s_addr))) { 92 rt->rt_flags |= RTF_PRCLONING; 93 } 94 } 95 96 /* 97 * We also specify a send and receive pipe size for every 98 * route added, to help TCP a bit. TCP doesn't actually 99 * want a true pipe size, which would be prohibitive in memory 100 * costs and is hard to compute anyway; it simply uses these 101 * values to size its buffers. So, we fill them in with the 102 * same values that TCP would have used anyway, and allow the 103 * installing program or the link layer to override these values 104 * as it sees fit. This will hopefully allow TCP more 105 * opportunities to save its ssthresh value. 106 */ 107 if (!rt->rt_rmx.rmx_sendpipe && !(rt->rt_rmx.rmx_locks & RTV_SPIPE)) 108 rt->rt_rmx.rmx_sendpipe = tcp_sendspace; 109 110 if (!rt->rt_rmx.rmx_recvpipe && !(rt->rt_rmx.rmx_locks & RTV_RPIPE)) 111 rt->rt_rmx.rmx_recvpipe = tcp_recvspace; 112 113 #if 0 114 /* 115 * Finally, set an MTU, again duplicating logic in TCP. 116 * The in_localaddr() business will go away when we have 117 * proper PMTU discovery. 118 */ 119 #endif 120 if (!rt->rt_rmx.rmx_mtu && !(rt->rt_rmx.rmx_locks & RTV_MTU) 121 && rt->rt_ifp) 122 #if 0 123 rt->rt_rmx.rmx_mtu = (in_localaddr(sin->sin_addr) 124 ? rt->rt_ifp->if_mtu 125 : tcp_mssdflt + sizeof(struct tcpiphdr)); 126 #else 127 rt->rt_rmx.rmx_mtu = rt->rt_ifp->if_mtu; 128 #endif 129 130 ret = rn_addroute(v_arg, n_arg, head, treenodes); 131 if (ret == NULL && rt->rt_flags & RTF_HOST) { 132 struct rtentry *rt2; 133 /* 134 * We are trying to add a host route, but can't. 135 * Find out if it is because of an 136 * ARP entry and delete it if so. 137 */ 138 rt2 = rtalloc1((struct sockaddr *)sin, 0, 139 RTF_CLONING | RTF_PRCLONING); 140 if (rt2) { 141 if (rt2->rt_flags & RTF_LLINFO && 142 rt2->rt_flags & RTF_HOST && 143 rt2->rt_gateway && 144 rt2->rt_gateway->sa_family == AF_LINK) { 145 rtrequest(RTM_DELETE, 146 (struct sockaddr *)rt_key(rt2), 147 rt2->rt_gateway, 148 rt_mask(rt2), rt2->rt_flags, 0); 149 ret = rn_addroute(v_arg, n_arg, head, 150 treenodes); 151 } 152 RTFREE(rt2); 153 } 154 } 155 return ret; 156 } 157 158 /* 159 * This code is the inverse of in_clsroute: on first reference, if we 160 * were managing the route, stop doing so and set the expiration timer 161 * back off again. 162 */ 163 static struct radix_node * 164 in_matroute(void *v_arg, struct radix_node_head *head) 165 { 166 struct radix_node *rn = rn_match(v_arg, head); 167 struct rtentry *rt = (struct rtentry *)rn; 168 169 if(rt && rt->rt_refcnt == 0) { /* this is first reference */ 170 if(rt->rt_flags & RTPRF_OURS) { 171 rt->rt_flags &= ~RTPRF_OURS; 172 rt->rt_rmx.rmx_expire = 0; 173 } 174 } 175 return rn; 176 } 177 178 static int rtq_reallyold = 60*60; 179 /* one hour is ``really old'' */ 180 SYSCTL_INT(_net_inet_ip, IPCTL_RTEXPIRE, rtexpire, 181 CTLFLAG_RW, &rtq_reallyold , 0, ""); 182 183 static int rtq_minreallyold = 10; 184 /* never automatically crank down to less */ 185 SYSCTL_INT(_net_inet_ip, IPCTL_RTMINEXPIRE, rtminexpire, 186 CTLFLAG_RW, &rtq_minreallyold , 0, ""); 187 188 static int rtq_toomany = 128; 189 /* 128 cached routes is ``too many'' */ 190 SYSCTL_INT(_net_inet_ip, IPCTL_RTMAXCACHE, rtmaxcache, 191 CTLFLAG_RW, &rtq_toomany , 0, ""); 192 193 194 /* 195 * On last reference drop, mark the route as belong to us so that it can be 196 * timed out. 197 */ 198 static void 199 in_clsroute(struct radix_node *rn, struct radix_node_head *head) 200 { 201 struct rtentry *rt = (struct rtentry *)rn; 202 203 if(!(rt->rt_flags & RTF_UP)) 204 return; /* prophylactic measures */ 205 206 if((rt->rt_flags & (RTF_LLINFO | RTF_HOST)) != RTF_HOST) 207 return; 208 209 if((rt->rt_flags & (RTF_WASCLONED | RTPRF_OURS)) 210 != RTF_WASCLONED) 211 return; 212 213 /* 214 * As requested by David Greenman: 215 * If rtq_reallyold is 0, just delete the route without 216 * waiting for a timeout cycle to kill it. 217 */ 218 if(rtq_reallyold != 0) { 219 rt->rt_flags |= RTPRF_OURS; 220 rt->rt_rmx.rmx_expire = time.tv_sec + rtq_reallyold; 221 } else { 222 rtrequest(RTM_DELETE, 223 (struct sockaddr *)rt_key(rt), 224 rt->rt_gateway, rt_mask(rt), 225 rt->rt_flags, 0); 226 } 227 } 228 229 struct rtqk_arg { 230 struct radix_node_head *rnh; 231 int draining; 232 int killed; 233 int found; 234 int updating; 235 time_t nextstop; 236 }; 237 238 /* 239 * Get rid of old routes. When draining, this deletes everything, even when 240 * the timeout is not expired yet. When updating, this makes sure that 241 * nothing has a timeout longer than the current value of rtq_reallyold. 242 */ 243 static int 244 in_rtqkill(struct radix_node *rn, void *rock) 245 { 246 struct rtqk_arg *ap = rock; 247 struct rtentry *rt = (struct rtentry *)rn; 248 int err; 249 250 if(rt->rt_flags & RTPRF_OURS) { 251 ap->found++; 252 253 if(ap->draining || rt->rt_rmx.rmx_expire <= time.tv_sec) { 254 if(rt->rt_refcnt > 0) 255 panic("rtqkill route really not free"); 256 257 err = rtrequest(RTM_DELETE, 258 (struct sockaddr *)rt_key(rt), 259 rt->rt_gateway, rt_mask(rt), 260 rt->rt_flags, 0); 261 if(err) { 262 log(LOG_WARNING, "in_rtqkill: error %d\n", err); 263 } else { 264 ap->killed++; 265 } 266 } else { 267 if(ap->updating 268 && (rt->rt_rmx.rmx_expire - time.tv_sec 269 > rtq_reallyold)) { 270 rt->rt_rmx.rmx_expire = time.tv_sec 271 + rtq_reallyold; 272 } 273 ap->nextstop = lmin(ap->nextstop, 274 rt->rt_rmx.rmx_expire); 275 } 276 } 277 278 return 0; 279 } 280 281 #define RTQ_TIMEOUT 60*10 /* run no less than once every ten minutes */ 282 static int rtq_timeout = RTQ_TIMEOUT; 283 284 static void 285 in_rtqtimo(void *rock) 286 { 287 struct radix_node_head *rnh = rock; 288 struct rtqk_arg arg; 289 struct timeval atv; 290 static time_t last_adjusted_timeout = 0; 291 int s; 292 293 arg.found = arg.killed = 0; 294 arg.rnh = rnh; 295 arg.nextstop = time.tv_sec + rtq_timeout; 296 arg.draining = arg.updating = 0; 297 s = splnet(); 298 rnh->rnh_walktree(rnh, in_rtqkill, &arg); 299 splx(s); 300 301 /* 302 * Attempt to be somewhat dynamic about this: 303 * If there are ``too many'' routes sitting around taking up space, 304 * then crank down the timeout, and see if we can't make some more 305 * go away. However, we make sure that we will never adjust more 306 * than once in rtq_timeout seconds, to keep from cranking down too 307 * hard. 308 */ 309 if((arg.found - arg.killed > rtq_toomany) 310 && (time.tv_sec - last_adjusted_timeout >= rtq_timeout) 311 && rtq_reallyold > rtq_minreallyold) { 312 rtq_reallyold = 2*rtq_reallyold / 3; 313 if(rtq_reallyold < rtq_minreallyold) { 314 rtq_reallyold = rtq_minreallyold; 315 } 316 317 last_adjusted_timeout = time.tv_sec; 318 log(LOG_DEBUG, "in_rtqtimo: adjusted rtq_reallyold to %d\n", 319 rtq_reallyold); 320 arg.found = arg.killed = 0; 321 arg.updating = 1; 322 s = splnet(); 323 rnh->rnh_walktree(rnh, in_rtqkill, &arg); 324 splx(s); 325 } 326 327 atv.tv_usec = 0; 328 atv.tv_sec = arg.nextstop; 329 timeout(in_rtqtimo, rock, hzto(&atv)); 330 } 331 332 void 333 in_rtqdrain(void) 334 { 335 struct radix_node_head *rnh = rt_tables[AF_INET]; 336 struct rtqk_arg arg; 337 int s; 338 arg.found = arg.killed = 0; 339 arg.rnh = rnh; 340 arg.nextstop = 0; 341 arg.draining = 1; 342 arg.updating = 0; 343 s = splnet(); 344 rnh->rnh_walktree(rnh, in_rtqkill, &arg); 345 splx(s); 346 } 347 348 /* 349 * Initialize our routing tree. 350 */ 351 int 352 in_inithead(void **head, int off) 353 { 354 struct radix_node_head *rnh; 355 356 if(!rn_inithead(head, off)) 357 return 0; 358 359 if(head != (void **)&rt_tables[AF_INET]) /* BOGUS! */ 360 return 1; /* only do this for the real routing table */ 361 362 rnh = *head; 363 rnh->rnh_addaddr = in_addroute; 364 rnh->rnh_matchaddr = in_matroute; 365 rnh->rnh_close = in_clsroute; 366 in_rtqtimo(rnh); /* kick off timeout first time */ 367 return 1; 368 } 369 370