Re: [RFC PATCH 5/6] KEYS: Replace assoc_array with struct keyring_index

Jarkko Sakkinen [off-list ref] wrote:

Maintain two linked lists in the index:

- all: enumerate committed links without retrying hash table walks when
  the table resizes.
- keyrings: visit nested keyrings during recursive search without scanning
  links to other key types.

Do you actually need two lists?  Can you just "sort" the list to put all the
keyrings first?

+			struct keyring_index __rcu *links;

Does that actually need an __rcu mark?  Is it going to get replaced once
allocated?

+struct keyring_link;
+

Somewhere near the top of internal.h, please, not sandwiched in the middle of
some func declarations.

Why #include user-type.h here?

Given key->serial is 1-INT_MAX, nr probably doesn't need to be unsigned long -
otoh, it's not likely to leave a hole, I guess.

+struct keyring_link {

I wonder if keyring_entry would be a better name, but the docs do mention
making and removing links.

+	unsigned long		hash;
...
+	struct rcu_head		rcu;

Can they be in a union?  And I would put rcu first as I think there are (or
maybe used to be) some things that required it to be first.

+	struct list_head	keyrings_link;	/* in keyring_index::keyrings */

This may be unnecessary if you can put keyrings at the front of the list.

+	struct keyring_link	*replaces;	/* Link this one replaces, or NULL */

Please don't put this in keyring_link.  It's only needed by __key_link() and
friends and could be passed around in a context struct as the edit script is
done now:

	struct keyring_link_context {
		struct keyring_link *spare;	/* Spare link block */
		struct keyring_link *replace;	/* Link being replaced */
	};

then:

	 int __key_link_begin(struct key *keyring,
			     const struct keyring_index_key *index_key,
	-		     struct assoc_array_edit **_edit)
	+		     struct keyring_link_context **_edit)

+/*
+ * Remove every link from a keyring.  The caller holds keyring->sem
+ * write-locked.  A concurrent RCU reader can see some of the links gone and
+ * others not yet.
+ */
+static void keyring_remove_all_links(struct key *keyring)
+{
+	struct keyring_index *links = keyring_index_locked(keyring);
+	struct keyring_link *link, *tmp;
+
+	if (!links)
+		return;
+	list_for_each_entry_safe(link, tmp, &links->all, all_link)
+		keyring_remove_link(links, link);
 }
...
 int keyring_clear(struct key *keyring)
 {
...
+	keyring_remove_all_links(keyring);

This can be made atomic by replacing the key->links pointer value with NULL
(since key->links is marked __rcu), then destroying the content afterwards.

David