From owner-freebsd-net Mon Oct 7 22:43: 7 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 43FD937B404 for ; Mon, 7 Oct 2002 22:43:05 -0700 (PDT) Received: from rootlabs.com (root.org [67.118.192.226]) by mx1.FreeBSD.org (Postfix) with SMTP id AA46843E8A for ; Mon, 7 Oct 2002 22:43:04 -0700 (PDT) (envelope-from nate@rootlabs.com) Received: (qmail 9484 invoked by uid 1000); 8 Oct 2002 05:43:06 -0000 Date: Mon, 7 Oct 2002 22:43:06 -0700 (PDT) From: Nate Lawson To: Julian Elischer Cc: Terry Lambert , Sam Leffler , freebsd-arch@freebsd.org, freebsd-net@freebsd.org Subject: Re: CFR: m_tag patch In-Reply-To: Message-ID: 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, Julian Elischer wrote: > On Mon, 7 Oct 2002, Terry Lambert wrote: > > On Mon, 7 Oct 2002, Julian Elischer wrote: > > > Your tags have a single 16 bit tag ID field. > > > This is insufficient for my needs. > > > I need to be able to store the API cookie which is a 32 bit > > > unsigned number, and on top of that, I also need a 16 bit type field > > > that specifies what the data is within teh given API and a 16 bit > > > length to allow opaque handling. > > > > This is insufficient for Alpha and other 64 bit architectures. I > > think what you are asking for is really a 'void *'. > > IT IS NOT A POINTER! > > it is a 32 bit unsigned number. Ok. > > The other issue here is that your idea of an opaque API/ABI indicator > > is in conflict, unless you say that this is a pointer, and then format > > the initial information pointed to by the pointer. Otherwise, you > > will need a small indirection structure that's pointed to the pointer, > > AND which contains the API/ABI identifier (i.e. you will need two, not > > one piece of information for that -- which is what you show, but not > > what you describe in your text). > > it is not used to look up anything.. > it is used to verify only. > > it is just working on the principal that there is not going to be > a collision in the 32 bit space. Especially when we create them from > "time since the epoch", and when teh various authors can see each > other's choices of value. There are deterministic ways to generate them. 1. A counter -- gettag() { return tag++; } 2. A LCRG -- gettag() { return (A * tag) % n; } 3. A global registry -- "Hey, gimme a major" There are non-deterministic ways as well, i.e. hash functions and PRNGs. And if code can run faster than a given time source, the output of that source or permutation thereof can produce collisions. What leads you towards the time-based option vs. the others, especially the deterministic ones? > > This is moderately bogus. > > no it is not. > > I estimate that the chance of having a collision given all the > factors is 1:2^50 or so ASSUMING THAT 1000000 PEOPLE DEVELOP THEIR OWN > MODULES AND DO NOT CHECK THEM IN BUT DO ALL SHARE THEM WITH EACH OTHER. Hmmm, if they choose them at random, the chance of a collision is sqrt(n) or 1/(2^16). If they choose them perfectly coordinated, the chance is 1/(2^32). Much less than 2^50. -Nate To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-net" in the body of the message