From: "George Spelvin" <linux@horizon.com>
To: dhowells@redhat.com, joe@perches.com, linux@horizon.com
Cc: keyrings@linux-nfs.org, linux-kernel@vger.kernel.org,
linux-nfs@vger.kernel.org, linux-security-module@vger.kernel.org
Subject: Re: [PATCH] Assoc_array: Drop leaf-type concept
Date: 18 Jul 2013 17:31:26 -0400 [thread overview]
Message-ID: <20130718213126.12710.qmail@science.horizon.com> (raw)
In-Reply-To: <21160.1374153504@warthog.procyon.org.uk>
Looks cleaner.
The larger issues that bother me:
1) The fact that the abstract daya type "index key" provides access to
a byte string "index key" is a bit confusing. I'd describe it as
follows: (Based on my current understanding.)
Each object has an associated "index key" that is used for lookup.
The index key is a string of bits which is stored "inside" the object,
however all access to it is done through method functions, so it is
not necessary to explicitly store it anywhere.
For example, it is possible to have the leading portion of the
index_key be a hash of the remainder.
Index keys may be variable-length, but must be self-delimiting.
Specifically, two different index keys must differ at some bit position
before the end of the shorter of the two.
Some index key methods take an isolated "const void *index_key"
argument, while others take an object pointer.
2) The code does not look 32-bit safe. In particular, keyring_get_key_chunk
assumes the hash is BITS_PER_LONG long, but keyring_diff_objects
assumes it's 8*8 bits...
3) I presume you looked at wider tries like Judy arrays and found that
a fan-out of 16 was better?
4) There are 3/7 unused bytes in an assoc_array_node, after parent_slot.
Would it be worth storing 16/48 bits of index key and 3/4 bits of
number of levels to skip per assoc_array_node?
Since parent_slot is actually only 4 bits, you could store 4 bits
of nubmer of levels and 56 bits (up to 14 levels, plus the one
from the famout) of index key.
With 32-way fanout, you could fit 5 bits of parent index, 25/55 bits of
index key, and encode the number of levels to skip (0-5/11) more carefully.
5) The big question: Why not use a hash table? That's what people
usually expect when you say "associative array". It would be simpler
and faster.
RCU-safe resizeable hash tables are tricky, but a solved problem,
There are universal hashing techniques for preventing hash collision
attacks.
next prev parent reply other threads:[~2013-07-18 21:31 UTC|newest]
Thread overview: 16+ messages / expand[flat|nested] mbox.gz Atom feed top
2013-07-17 20:43 [RFC][PATCH 00/10] Associative array & Massive expansion of keyring capacity David Howells
2013-07-17 20:43 ` [PATCH 01/10] KEYS: Skip key state checks when checking for possession David Howells
2013-07-17 20:43 ` [PATCH 02/10] Add a generic associative array implementation David Howells
2013-07-17 20:53 ` Joe Perches
2013-07-17 21:01 ` David Howells
2013-07-18 13:18 ` [PATCH] Assoc_array: Drop leaf-type concept David Howells
2013-07-18 21:31 ` George Spelvin [this message]
2013-07-19 14:37 ` David Howells
2013-07-17 20:43 ` [PATCH 03/10] KEYS: Use bool in make_key_ref() and is_key_possessed() David Howells
2013-07-17 20:43 ` [PATCH 04/10] KEYS: key_is_dead() should take a const key pointer argument David Howells
2013-07-17 20:43 ` [PATCH 05/10] KEYS: Consolidate the concept of an 'index key' for key access David Howells
2013-07-17 20:44 ` [PATCH 06/10] KEYS: Introduce a search context structure David Howells
2013-07-17 20:44 ` [PATCH 07/10] KEYS: Search for auth-key by name rather than targt key ID David Howells
2013-07-17 20:44 ` [PATCH 08/10] KEYS: Define a __key_get() wrapper to use rather than atomic_inc() David Howells
2013-07-17 20:44 ` [PATCH 09/10] KEYS: Drop the permissions argument from __keyring_search_one() David Howells
2013-07-17 20:44 ` [PATCH 10/10] KEYS: Expand the capacity of a keyring David Howells
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20130718213126.12710.qmail@science.horizon.com \
--to=linux@horizon.com \
--cc=dhowells@redhat.com \
--cc=joe@perches.com \
--cc=keyrings@linux-nfs.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-nfs@vger.kernel.org \
--cc=linux-security-module@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.