From owner-freebsd-arch@FreeBSD.ORG Tue Dec 27 20:19:57 2005 Return-Path: X-Original-To: arch@freebsd.org Delivered-To: freebsd-arch@FreeBSD.ORG Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 85D3F16A41F; Tue, 27 Dec 2005 20:19:57 +0000 (GMT) (envelope-from peter@wemm.org) Received: from canning.wemm.org (canning.wemm.org [192.203.228.65]) by mx1.FreeBSD.org (Postfix) with ESMTP id E029B43D5E; Tue, 27 Dec 2005 20:19:56 +0000 (GMT) (envelope-from peter@wemm.org) Received: from fw.wemm.org (canning.wemm.org [192.203.228.65]) by canning.wemm.org (Postfix) with ESMTP id 942472A905; Tue, 27 Dec 2005 12:19:56 -0800 (PST) (envelope-from peter@wemm.org) Received: from peter-laptop.wemm.org (dhcp99.wemm.org [10.0.0.99]) by fw.wemm.org (Postfix) with ESMTP id 4559BE2B3; Tue, 27 Dec 2005 12:19:56 -0800 (PST) (envelope-from peter@wemm.org) Received: from peter-laptop.wemm.org (localhost [127.0.0.1]) by peter-laptop.wemm.org (8.13.4/8.13.4) with ESMTP id jBRKI6Gh034514; Tue, 27 Dec 2005 12:18:06 -0800 (PST) (envelope-from peter@wemm.org) Received: from localhost (localhost [[UNIX: localhost]]) by peter-laptop.wemm.org (8.13.4/8.13.3/Submit) id jBRKI5AC034513; Tue, 27 Dec 2005 12:18:05 -0800 (PST) (envelope-from peter@wemm.org) X-Authentication-Warning: peter-laptop.wemm.org: peter set sender to peter@wemm.org using -f From: Peter Wemm To: freebsd-arch@freebsd.org Date: Tue, 27 Dec 2005 12:18:04 -0800 User-Agent: KMail/1.8.3 References: <20051107140451.GU91530@cell.sick.ru> <20051111140926.GC733@empiric.icir.org> <20051111141519.GE1647@cell.sick.ru> In-Reply-To: <20051111141519.GE1647@cell.sick.ru> MIME-Version: 1.0 Content-Type: text/plain; charset="koi8-r" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200512271218.05201.peter@wemm.org> Cc: Bruce M Simpson , Gleb Smirnoff , arch@freebsd.org Subject: Re: ARP request retransmitting X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 27 Dec 2005 20:19:57 -0000 On Friday 11 November 2005 06:15 am, Gleb Smirnoff wrote: > On Fri, Nov 11, 2005 at 02:09:26PM +0000, Bruce M Simpson wrote: > B> On Mon, Nov 07, 2005 at 05:04:51PM +0300, Gleb Smirnoff wrote: > B> > I suggest to keep sending ARP requests while there is a demand for > B> > this (we are trying to transmit packets to this particular IP), > B> > ratelimiting these requests to one per second. This will help in a > B> > quite common case, when some host on net is rebooting, and we are > B> > waiting for him to come up, and notice this only after 1 - 20 seconds > B> > since the time it is reachable. > B> > Any objections? > B> > B> In response to the other replies to this thread citing broadcast > B> pollution on Ethernet-based networks: > B> Please add this functionality under a sysctl where it is turned off by > default. B> > B> It is desirable in situations where ARP entries cached further upstream > are B> stale, but it may cause flooding in an environment where the layer 2 > backbone B> hasn't been split or has not been segregated well. > B> > B> Other people cited examples where vendor switch implementations were > B> retransmitting across VLANs -- this week I've been offering moral > support B> to a friend who is dealing with similar VLAN brokenness at his > $DAYJOB B> (there was an extension to 802.1d to support multiple spanning > tree instances B> across VLANs which I think not everyone supports > correctly). > > I'd like to see a proven evidence that this functionality leads to a > measurable increase in broadcast traffic. Many modern operating systems > behave in such way and no-one complains. The increase of broadcast traffic > is very theoretical, it happens only when there are downed hosts. Personally, I think that the place that this can most benefit is small home/office/business networks of a small number of hosts. People with large networks already have to deal with this sort of problem anyway. FreeBSD systems retransmit once per second for 20 seconds, then take a short break, then resume the once-per-second retransmits again. The "short break" is useless IMHO and makes such a small difference in modern networks. The saddest thing I see these days is a constant stream of ARP traffic coming in my cable modem. About 20-30 per second. 09:36:27.040649 arp who-has 67.174.245.39 tell 67.174.244.1 09:36:27.104437 arp who-has 67.188.248.237 tell 67.188.240.1 09:36:27.128126 arp who-has 67.188.240.180 tell 67.188.240.1 09:36:27.162068 arp who-has 67.174.244.30 tell 67.174.244.1 09:36:27.162313 arp who-has 67.174.244.37 tell 67.174.244.1 09:36:27.166890 arp who-has 67.174.244.48 tell 67.174.244.1 09:36:27.167550 arp who-has 67.174.244.44 tell 67.174.244.1 09:36:27.168296 arp who-has 67.174.244.45 tell 67.174.244.1 09:36:27.168735 arp who-has 67.174.244.50 tell 67.174.244.1 09:36:27.168984 arp who-has 67.174.244.91 tell 67.174.244.1 09:36:27.170819 arp who-has 67.174.244.97 tell 67.174.244.1 09:36:27.171062 arp who-has 67.174.244.101 tell 67.174.244.1 09:36:27.171226 arp who-has 67.174.244.107 tell 67.174.244.1 09:36:27.171662 arp who-has 67.174.244.110 tell 67.174.244.1 09:36:27.171909 arp who-has 67.174.244.116 tell 67.174.244.1 09:36:27.174206 arp who-has 67.174.244.92 tell 67.174.244.1 09:36:27.174447 arp who-has 67.188.248.57 tell 67.188.240.1 09:36:27.174603 arp who-has 67.174.244.112 tell 67.174.244.1 09:36:27.176663 arp who-has 67.174.244.135 tell 67.174.244.1 09:36:27.177101 arp who-has 67.174.244.158 tell 67.174.244.1 09:36:27.177352 arp who-has 67.174.244.144 tell 67.174.244.1 09:36:27.178172 arp who-has 67.174.244.141 tell 67.174.244.1 09:36:27.178413 arp who-has 67.174.244.146 tell 67.174.244.1 09:36:27.180278 arp who-has 67.174.244.148 tell 67.174.244.1 09:36:27.180948 arp who-has 67.174.244.151 tell 67.174.244.1 09:36:27.181184 arp who-has 67.174.244.152 tell 67.174.244.1 09:36:27.716214 arp who-has 67.188.247.253 tell 67.188.240.1 09:36:27.765102 arp who-has 69.181.212.233 tell 69.181.212.1 09:36:27.799458 arp who-has 67.188.113.101 tell 67.188.112.1 09:36:27.848736 arp who-has 67.188.240.194 tell 67.188.240.1 09:36:27.854934 arp who-has 67.188.240.142 tell 67.188.240.1 09:36:27.897613 arp who-has 67.188.240.195 tell 67.188.240.1 09:36:27.997441 arp who-has 67.188.240.95 tell 67.188.240.1 I'm sure most of this is comcast's self-inflicted pain, but FreeBSD doesn't even make a dent in ARP traffic like this. Most of the ARP traffic I see at work on our corp network comes from routers trying to reach down hosts or re-arping up machines. But then again, we use vlans to limit the size of broadcast domains. I suspect most well managed "large" networks will have something similar. The difference between sending 20 arps per 40 seconds or 40 arps per 40 seconds for a down host isn't going to make a dent. What does seem to hurt is when some body does an nmap and you get thousands of arps from the router... -Peter From owner-freebsd-arch@FreeBSD.ORG Tue Dec 27 20:19:57 2005 Return-Path: X-Original-To: freebsd-arch@freebsd.org Delivered-To: freebsd-arch@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 85D3F16A41F; Tue, 27 Dec 2005 20:19:57 +0000 (GMT) (envelope-from peter@wemm.org) Received: from canning.wemm.org (canning.wemm.org [192.203.228.65]) by mx1.FreeBSD.org (Postfix) with ESMTP id E029B43D5E; Tue, 27 Dec 2005 20:19:56 +0000 (GMT) (envelope-from peter@wemm.org) Received: from fw.wemm.org (canning.wemm.org [192.203.228.65]) by canning.wemm.org (Postfix) with ESMTP id 942472A905; Tue, 27 Dec 2005 12:19:56 -0800 (PST) (envelope-from peter@wemm.org) Received: from peter-laptop.wemm.org (dhcp99.wemm.org [10.0.0.99]) by fw.wemm.org (Postfix) with ESMTP id 4559BE2B3; Tue, 27 Dec 2005 12:19:56 -0800 (PST) (envelope-from peter@wemm.org) Received: from peter-laptop.wemm.org (localhost [127.0.0.1]) by peter-laptop.wemm.org (8.13.4/8.13.4) with ESMTP id jBRKI6Gh034514; Tue, 27 Dec 2005 12:18:06 -0800 (PST) (envelope-from peter@wemm.org) Received: from localhost (localhost [[UNIX: localhost]]) by peter-laptop.wemm.org (8.13.4/8.13.3/Submit) id jBRKI5AC034513; Tue, 27 Dec 2005 12:18:05 -0800 (PST) (envelope-from peter@wemm.org) X-Authentication-Warning: peter-laptop.wemm.org: peter set sender to peter@wemm.org using -f From: Peter Wemm To: freebsd-arch@freebsd.org Date: Tue, 27 Dec 2005 12:18:04 -0800 User-Agent: KMail/1.8.3 References: <20051107140451.GU91530@cell.sick.ru> <20051111140926.GC733@empiric.icir.org> <20051111141519.GE1647@cell.sick.ru> In-Reply-To: <20051111141519.GE1647@cell.sick.ru> MIME-Version: 1.0 Content-Type: text/plain; charset="koi8-r" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200512271218.05201.peter@wemm.org> Cc: Bruce M Simpson , Gleb Smirnoff , arch@freebsd.org Subject: Re: ARP request retransmitting X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 27 Dec 2005 20:19:57 -0000 On Friday 11 November 2005 06:15 am, Gleb Smirnoff wrote: > On Fri, Nov 11, 2005 at 02:09:26PM +0000, Bruce M Simpson wrote: > B> On Mon, Nov 07, 2005 at 05:04:51PM +0300, Gleb Smirnoff wrote: > B> > I suggest to keep sending ARP requests while there is a demand for > B> > this (we are trying to transmit packets to this particular IP), > B> > ratelimiting these requests to one per second. This will help in a > B> > quite common case, when some host on net is rebooting, and we are > B> > waiting for him to come up, and notice this only after 1 - 20 seconds > B> > since the time it is reachable. > B> > Any objections? > B> > B> In response to the other replies to this thread citing broadcast > B> pollution on Ethernet-based networks: > B> Please add this functionality under a sysctl where it is turned off by > default. B> > B> It is desirable in situations where ARP entries cached further upstream > are B> stale, but it may cause flooding in an environment where the layer 2 > backbone B> hasn't been split or has not been segregated well. > B> > B> Other people cited examples where vendor switch implementations were > B> retransmitting across VLANs -- this week I've been offering moral > support B> to a friend who is dealing with similar VLAN brokenness at his > $DAYJOB B> (there was an extension to 802.1d to support multiple spanning > tree instances B> across VLANs which I think not everyone supports > correctly). > > I'd like to see a proven evidence that this functionality leads to a > measurable increase in broadcast traffic. Many modern operating systems > behave in such way and no-one complains. The increase of broadcast traffic > is very theoretical, it happens only when there are downed hosts. Personally, I think that the place that this can most benefit is small home/office/business networks of a small number of hosts. People with large networks already have to deal with this sort of problem anyway. FreeBSD systems retransmit once per second for 20 seconds, then take a short break, then resume the once-per-second retransmits again. The "short break" is useless IMHO and makes such a small difference in modern networks. The saddest thing I see these days is a constant stream of ARP traffic coming in my cable modem. About 20-30 per second. 09:36:27.040649 arp who-has 67.174.245.39 tell 67.174.244.1 09:36:27.104437 arp who-has 67.188.248.237 tell 67.188.240.1 09:36:27.128126 arp who-has 67.188.240.180 tell 67.188.240.1 09:36:27.162068 arp who-has 67.174.244.30 tell 67.174.244.1 09:36:27.162313 arp who-has 67.174.244.37 tell 67.174.244.1 09:36:27.166890 arp who-has 67.174.244.48 tell 67.174.244.1 09:36:27.167550 arp who-has 67.174.244.44 tell 67.174.244.1 09:36:27.168296 arp who-has 67.174.244.45 tell 67.174.244.1 09:36:27.168735 arp who-has 67.174.244.50 tell 67.174.244.1 09:36:27.168984 arp who-has 67.174.244.91 tell 67.174.244.1 09:36:27.170819 arp who-has 67.174.244.97 tell 67.174.244.1 09:36:27.171062 arp who-has 67.174.244.101 tell 67.174.244.1 09:36:27.171226 arp who-has 67.174.244.107 tell 67.174.244.1 09:36:27.171662 arp who-has 67.174.244.110 tell 67.174.244.1 09:36:27.171909 arp who-has 67.174.244.116 tell 67.174.244.1 09:36:27.174206 arp who-has 67.174.244.92 tell 67.174.244.1 09:36:27.174447 arp who-has 67.188.248.57 tell 67.188.240.1 09:36:27.174603 arp who-has 67.174.244.112 tell 67.174.244.1 09:36:27.176663 arp who-has 67.174.244.135 tell 67.174.244.1 09:36:27.177101 arp who-has 67.174.244.158 tell 67.174.244.1 09:36:27.177352 arp who-has 67.174.244.144 tell 67.174.244.1 09:36:27.178172 arp who-has 67.174.244.141 tell 67.174.244.1 09:36:27.178413 arp who-has 67.174.244.146 tell 67.174.244.1 09:36:27.180278 arp who-has 67.174.244.148 tell 67.174.244.1 09:36:27.180948 arp who-has 67.174.244.151 tell 67.174.244.1 09:36:27.181184 arp who-has 67.174.244.152 tell 67.174.244.1 09:36:27.716214 arp who-has 67.188.247.253 tell 67.188.240.1 09:36:27.765102 arp who-has 69.181.212.233 tell 69.181.212.1 09:36:27.799458 arp who-has 67.188.113.101 tell 67.188.112.1 09:36:27.848736 arp who-has 67.188.240.194 tell 67.188.240.1 09:36:27.854934 arp who-has 67.188.240.142 tell 67.188.240.1 09:36:27.897613 arp who-has 67.188.240.195 tell 67.188.240.1 09:36:27.997441 arp who-has 67.188.240.95 tell 67.188.240.1 I'm sure most of this is comcast's self-inflicted pain, but FreeBSD doesn't even make a dent in ARP traffic like this. Most of the ARP traffic I see at work on our corp network comes from routers trying to reach down hosts or re-arping up machines. But then again, we use vlans to limit the size of broadcast domains. I suspect most well managed "large" networks will have something similar. The difference between sending 20 arps per 40 seconds or 40 arps per 40 seconds for a down host isn't going to make a dent. What does seem to hurt is when some body does an nmap and you get thousands of arps from the router... -Peter From owner-freebsd-arch@FreeBSD.ORG Wed Dec 28 14:58:25 2005 Return-Path: X-Original-To: freebsd-arch@freebsd.org Delivered-To: freebsd-arch@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id CAA3E16A41F for ; Wed, 28 Dec 2005 14:58:25 +0000 (GMT) (envelope-from jasone@freebsd.org) Received: from lh.synack.net (lh.synack.net [204.152.188.37]) by mx1.FreeBSD.org (Postfix) with ESMTP id 462C743D4C for ; Wed, 28 Dec 2005 14:58:25 +0000 (GMT) (envelope-from jasone@freebsd.org) Received: by lh.synack.net (Postfix, from userid 100) id 2FE515E48E3; Wed, 28 Dec 2005 06:58:25 -0800 (PST) Received: from [192.168.168.203] (moscow-cuda-gen2-68-64-60-20.losaca.adelphia.net [68.64.60.20]) (using TLSv1 with cipher RC4-SHA (128/128 bits)) (No client certificate requested) by lh.synack.net (Postfix) with ESMTP id 5D4865E488C for ; Wed, 28 Dec 2005 06:58:23 -0800 (PST) Mime-Version: 1.0 (Apple Message framework v746.2) Content-Transfer-Encoding: 7bit Message-Id: <0F813D59-3329-47EC-AB17-24CE53293357@freebsd.org> Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: freebsd-arch@freebsd.org From: Jason Evans Date: Wed, 28 Dec 2005 06:58:20 -0800 X-Mailer: Apple Mail (2.746.2) X-Spam-Checker-Version: SpamAssassin 3.0.4 (2005-06-05) on lh.synack.net X-Spam-Level: * X-Spam-Status: No, score=1.8 required=5.0 tests=RCVD_IN_NJABL_DUL, RCVD_IN_SORBS_DUL autolearn=no version=3.0.4 Subject: Adding RB_NFIND() to sys/tree.h X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 28 Dec 2005 14:58:26 -0000 [This is a slightly edited copy of email originally sent to - current. The only response I received was that -arch is a better list on which to ask for feedback on this issue.] I'd like to add RB_NFIND() to sys/tree.h, since I need it for the malloc implementation I've been working on. sys/tree.h comes from NetBSD, and up to now, the only changes we've made have been for the purpose of avoiding compiler warnings. RB_NFIND() is like RB_FIND(), but if an exact match isn't found, RB_NFIND() returns the next object in the tree (if there is one). Emulating RB_NFIND() with the existing RB_*() API is possible, but certainly not ideal. I would claim that RB_PFIND() isn't necessary, since it could be easily (if not quite as efficiently) emulated with RB_NFIND(), followed by RB_PREV(). However, there is no RB_PREV(), even though there is RB_NEXT(). This seems to me like an API design oversight (as is the omission of RB_FOREACH_REVERSE()), but it doesn't cause me issues, so I haven't tackled it. A patch follows (manpage changes omitted). Are there any objections to committing this? Thanks, Jason Index: sys/sys/tree.h =================================================================== RCS file: /home/ncvs/src/sys/sys/tree.h,v retrieving revision 1.3 diff -u -r1.3 tree.h --- sys/sys/tree.h 10 Jun 2005 11:44:57 -0000 1.3 +++ sys/sys/tree.h 17 Dec 2005 03:00:01 -0000 @@ -382,6 +382,7 @@ struct type *name##_RB_REMOVE(struct name *, struct type *); \ struct type *name##_RB_INSERT(struct name *, struct type *); \ struct type *name##_RB_FIND(struct name *, struct type *); \ +struct type *name##_RB_NFIND(struct name *, struct type *); \ struct type *name##_RB_NEXT(struct type *); \ struct type *name##_RB_MINMAX(struct name *, int); \ \ @@ -628,6 +629,35 @@ return (NULL); \ } \ \ +/* Finds the first node greater than or equal to the search key */ \ +struct type * \ +name##_RB_NFIND(struct name *head, struct type *elm) \ +{ \ + struct type *ret = RB_ROOT(head); \ + struct type *tmp; \ + int comp; \ + while (ret && (comp = cmp(elm, ret)) != 0) { \ + if (comp < 0) { \ + if ((tmp = RB_LEFT(ret, field)) == NULL) \ + break; \ + ret = tmp; \ + } else { \ + if ((tmp = RB_RIGHT(ret, field)) == NULL) { \ + tmp = ret; \ + ret = RB_PARENT(ret, field); \ + while (ret && tmp == RB_RIGHT(ret, \ + field)) { \ + tmp = ret; \ + ret = RB_PARENT(ret, field); \ + } \ + break; \ + } \ + ret = tmp; \ + } \ + } \ + return (ret); \ +} \ + \ /* ARGSUSED */ \ struct type * \ name##_RB_NEXT(struct type *elm) \ @@ -671,6 +701,7 @@ #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) #define RB_FIND(name, x, y) name##_RB_FIND(x, y) +#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) #define RB_NEXT(name, x, y) name##_RB_NEXT(y) #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) From owner-freebsd-arch@FreeBSD.ORG Wed Dec 28 18:39:30 2005 Return-Path: X-Original-To: freebsd-arch@freebsd.org Delivered-To: freebsd-arch@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 44E4616A41F; Wed, 28 Dec 2005 18:39:30 +0000 (GMT) (envelope-from julian@elischer.org) Received: from a50.ironport.com (a50.ironport.com [63.251.108.112]) by mx1.FreeBSD.org (Postfix) with ESMTP id 63B2043D67; Wed, 28 Dec 2005 18:39:29 +0000 (GMT) (envelope-from julian@elischer.org) Received: from unknown (HELO [10.251.17.229]) ([10.251.17.229]) by a50.ironport.com with ESMTP; 28 Dec 2005 10:39:28 -0800 X-IronPort-Anti-Spam-Filtered: true Message-ID: <43B2DBDF.8000007@elischer.org> Date: Wed, 28 Dec 2005 10:39:27 -0800 From: Julian Elischer User-Agent: Mozilla/5.0 (Macintosh; U; PPC Mac OS X Mach-O; en-US; rv:1.7.11) Gecko/20050727 X-Accept-Language: en-us, en MIME-Version: 1.0 To: Jason Evans References: <0F813D59-3329-47EC-AB17-24CE53293357@freebsd.org> In-Reply-To: <0F813D59-3329-47EC-AB17-24CE53293357@freebsd.org> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Cc: freebsd-arch@freebsd.org Subject: Re: Adding RB_NFIND() to sys/tree.h X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 28 Dec 2005 18:39:30 -0000 Jason Evans wrote: > [This is a slightly edited copy of email originally sent to - > current. The only response I received was that -arch is a better > list on which to ask for feedback on this issue.] > > I'd like to add RB_NFIND() to sys/tree.h, since I need it for the > malloc implementation I've been working on. sys/tree.h comes from > NetBSD, and up to now, the only changes we've made have been for the > purpose of avoiding compiler warnings. > > RB_NFIND() is like RB_FIND(), but if an exact match isn't found, > RB_NFIND() returns the next object in the tree (if there is one). > Emulating RB_NFIND() with the existing RB_*() API is possible, but > certainly not ideal. > > I would claim that RB_PFIND() isn't necessary, since it could be > easily (if not quite as efficiently) emulated with RB_NFIND(), > followed by RB_PREV(). However, there is no RB_PREV(), even though > there is RB_NEXT(). This seems to me like an API design oversight > (as is the omission of RB_FOREACH_REVERSE()), but it doesn't cause me > issues, so I haven't tackled it. > > A patch follows (manpage changes omitted). Are there any objections > to committing this? > > Thanks, > Jason I see no reason to not add it. From owner-freebsd-arch@FreeBSD.ORG Wed Dec 28 20:37:23 2005 Return-Path: X-Original-To: freebsd-arch@FreeBSD.org Delivered-To: freebsd-arch@FreeBSD.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id C947716A41F; Wed, 28 Dec 2005 20:37:23 +0000 (GMT) (envelope-from glebius@FreeBSD.org) Received: from cell.sick.ru (cell.sick.ru [217.72.144.68]) by mx1.FreeBSD.org (Postfix) with ESMTP id DA15A43D49; Wed, 28 Dec 2005 20:37:22 +0000 (GMT) (envelope-from glebius@FreeBSD.org) Received: from cell.sick.ru (glebius@localhost [127.0.0.1]) by cell.sick.ru (8.13.3/8.13.3) with ESMTP id jBSKbKnO035258 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Wed, 28 Dec 2005 23:37:20 +0300 (MSK) (envelope-from glebius@FreeBSD.org) Received: (from glebius@localhost) by cell.sick.ru (8.13.3/8.13.1/Submit) id jBSKbKO1035257; Wed, 28 Dec 2005 23:37:20 +0300 (MSK) (envelope-from glebius@FreeBSD.org) X-Authentication-Warning: cell.sick.ru: glebius set sender to glebius@FreeBSD.org using -f Date: Wed, 28 Dec 2005 23:37:19 +0300 From: Gleb Smirnoff To: Jason Evans Message-ID: <20051228203719.GD31008@FreeBSD.org> References: <0F813D59-3329-47EC-AB17-24CE53293357@freebsd.org> Mime-Version: 1.0 Content-Type: text/plain; charset=koi8-r Content-Disposition: inline In-Reply-To: <0F813D59-3329-47EC-AB17-24CE53293357@freebsd.org> User-Agent: Mutt/1.5.6i Cc: freebsd-arch@FreeBSD.org Subject: Re: Adding RB_NFIND() to sys/tree.h X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 28 Dec 2005 20:37:23 -0000 On Wed, Dec 28, 2005 at 06:58:20AM -0800, Jason Evans wrote: J> [This is a slightly edited copy of email originally sent to - J> current. The only response I received was that -arch is a better J> list on which to ask for feedback on this issue.] J> J> I'd like to add RB_NFIND() to sys/tree.h, since I need it for the J> malloc implementation I've been working on. sys/tree.h comes from J> NetBSD, and up to now, the only changes we've made have been for the J> purpose of avoiding compiler warnings. J> J> RB_NFIND() is like RB_FIND(), but if an exact match isn't found, J> RB_NFIND() returns the next object in the tree (if there is one). J> Emulating RB_NFIND() with the existing RB_*() API is possible, but J> certainly not ideal. J> J> I would claim that RB_PFIND() isn't necessary, since it could be J> easily (if not quite as efficiently) emulated with RB_NFIND(), J> followed by RB_PREV(). However, there is no RB_PREV(), even though J> there is RB_NEXT(). This seems to me like an API design oversight J> (as is the omission of RB_FOREACH_REVERSE()), but it doesn't cause me J> issues, so I haven't tackled it. J> J> A patch follows (manpage changes omitted). Are there any objections J> to committing this? I see it useful, and probably will utilize soon in ipfw(4). Thanks. -- Totus tuus, Glebius. GLEBIUS-RIPN GLEB-RIPE