nscd caching getpwent() and getgrent()

[mdm at google dot com]

Hi all,

I'm looking at adding the ability to cache getpwent() and getgrent() to
nscd. I've got it working, but I found a few issues that I'm hoping to get
some input about. Here's what I've done to nscd:

* Add two new query types to enum request_type in nscd-client.h
* Add entries to serve2str[] and serv2db[] in connections.c
* Update handle_request() in connections.c
* Update cache_addgr() and lookup() in grpcache.c
* Add addgrent() and readgrent() in grpcache.c
* Update cache_addpw() and lookup() in pwdcache.c
* Add addpwent() and readpwent() in pwdcache.c

I also modified the relevant bits of glibc to query nscd when getpwent_r()
and getgrent_r() are called.

What I've realized however is that nscd refreshes the entries in its cache
rather than just removing them when they expire, but it doesn't do it in
any particular order (due to the hash tables). The lookup() functions I
wrote simulate a random-access list of entries by keeping track of how far
into the list they are, and calling the end/set and get functions as
necessary to seek to the requested entry number (throwing away other
data). While this approach is fine if you ask for sequential entries, it
is O(n^2) when you ask for entries in a random order - like when nscd is
refreshing its cache.

So there are many ways this problem can be solved, and I'm curious which
sounds most correct to glibc developers since eventually I'd like to send
this patch into glibc. Here are the approaches I'm considering:

* Add all the skipped entries to the cache - this seems the most
complicated, since it requires adding things to the cache that were not
actually just requested and most of the code is not set up to make that
easy.
* Don't refresh these entries. When they expire, remove them. This
approach will remove this kind of entry much sooner than other entries,
since other entries will get refreshed several times before being removed.
Perhaps add a new timeout configuration parameter to allow these entries
to have a separate timeout to solve this.
* Don't refresh these entries. When they expire, pretend to refresh them
but actually do nothing. Don't reset their refresh count to 0 when they
are used, so they will still eventually be removed. This approach will
require a special case for users who set the refresh count limit to be
unlimited.
* Arrange for the cached entries to be refreshed in order somehow. It's
not clear what the best way to do this is.

Thoughts?

Thanks,
Mike Mammarella