From owner-freebsd-net Tue Oct 8 1:20:17 2002 Delivered-To: freebsd-net@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id B72D837B401; Tue, 8 Oct 2002 01:20:15 -0700 (PDT) Received: from mailhub.fokus.gmd.de (mailhub.fokus.gmd.de [193.174.154.14]) by mx1.FreeBSD.org (Postfix) with ESMTP id 49CA943E4A; Tue, 8 Oct 2002 01:20:14 -0700 (PDT) (envelope-from brandt@fokus.gmd.de) Received: from beagle (beagle [193.175.132.100]) by mailhub.fokus.gmd.de (8.11.6/8.11.6) with ESMTP id g988Jqe07033; Tue, 8 Oct 2002 10:19:52 +0200 (MEST) Date: Tue, 8 Oct 2002 10:19:52 +0200 (CEST) From: Harti Brandt To: Don Lewis Cc: nate@root.org, , , , , Subject: Re: CFR: m_tag patch In-Reply-To: <200210080606.g9866OvU034411@gw.catspoiler.org> Message-ID: <20021008100826.H77302-100000@beagle.fokus.gmd.de> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-freebsd-net@FreeBSD.ORG Precedence: bulk List-ID: List-Archive: (Web Archive) List-Help: (List Instructions) List-Subscribe: List-Unsubscribe: X-Loop: FreeBSD.org On Mon, 7 Oct 2002, Don Lewis wrote: DL>On 7 Oct, Nate Lawson wrote: DL>> On Mon, 7 Oct 2002, Julian Elischer wrote: DL> DL>>> it is just working on the principal that there is not going to be DL>>> a collision in the 32 bit space. Especially when we create them from DL>>> "time since the epoch", and when teh various authors can see each DL>>> other's choices of value. DL>> DL>> There are deterministic ways to generate them. DL>> 1. A counter -- gettag() { return tag++; } DL>> 2. A LCRG -- gettag() { return (A * tag) % n; } DL>> 3. A global registry -- "Hey, gimme a major" DL>> DL>> There are non-deterministic ways as well, i.e. hash functions and DL>> PRNGs. And if code can run faster than a given time source, the output of DL>> that source or permutation thereof can produce collisions. DL>> DL>> What leads you towards the time-based option vs. the others, especially DL>> the deterministic ones? DL> DL>Why not name them? At boot or module load time stuff the name in a DL>table and use the table index as the 16 bit ID. Is there any reason the DL>ID has to be the same each time the system is booted? Well, the point is that you need a common name between netgraph nodes and their controling application. As it is now this common name is the 32-bit cookie generated by issuing "date -u +'%s'" (so no timezone problem here). I have, for example, an user space ILMI daemon for ATM. This daemon needs to talk to the call control netgraph node. To do this the header file for the call control node contains #define NGM_CCATM_COOKIE 984046139 both, the netgraph node and the daemon include this file and the daemon addresses messages to the node by filling in the cookie into the appropriate field in the message. The node filters out the messages by compare the cookie field with the above cookie. If you use a dynamically generated cookie (be it a ++tags or a hash over a string or the address of a kernel structure) both the user space application and the node would need to call the code that generates these cookies with just another cookie (for example a string). So what you would do is to replace the 32-bit cookie with, for example, a string cookie. The question is, would a string cookie reduce the probability of conflicts on cookies? This question is rather hard to answer, because on one hand strings may contain more bits, but people would try to use descriptive and short cookie. I see a very high probability of two people that develop a ppp node to use the same string "ppp". This would be bad, because the actual API they implement would for sure be different. With the above method to choose the 32-bit cookie, this wouldn't happen. Given that the netgraph-hype is not of the dimensions of the Java-hype two people starting to develop netgraph node at the same moment of UTC is rather improbable. The only option that would make sense would be a assigned numbers authority, but again, given the dimensions of the netgraph-hype - is it worth the effort? harti -- harti brandt, http://www.fokus.gmd.de/research/cc/cats/employees/hartmut.brandt/private brandt@fokus.gmd.de, brandt@fokus.fhg.de To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-net" in the body of the message