Date: Tue, 8 Oct 2002 10:19:52 +0200 (CEST) From: Harti Brandt <brandt@fokus.gmd.de> To: Don Lewis <dl-freebsd@catspoiler.org> Cc: nate@root.org, <julian@elischer.org>, <tlambert2@mindspring.com>, <sam@errno.com>, <freebsd-arch@FreeBSD.ORG>, <freebsd-net@FreeBSD.ORG> Subject: Re: CFR: m_tag patch Message-ID: <20021008100826.H77302-100000@beagle.fokus.gmd.de> In-Reply-To: <200210080606.g9866OvU034411@gw.catspoiler.org>
next in thread | previous in thread | raw e-mail | index | archive | help
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-arch" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20021008100826.H77302-100000>