nscd caching getpwent() and getgrent()

[m***@google.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

[Ulrich Drepper]

since eventually I'd like to send this patch into glibc.

Don't bother. That is one of the most stupid ideas I've read in a while
and it won't be added.

[Petter Reinholdtsen]

[Ulrich Drepper]

Post by Ulrich Drepper
Don't bother. That is one of the most stupid ideas I've read in a
while and it won't be added.

Can you explain why? Caching a bit more in nscd do not appear like
one of the stupid ideas I've read, so I wonder why it appear so stupid
to you.

BTW: Are you aware that your message appear very hostile? Reading
your messages make me wonder if my time would be better spend
elsewhere. Is this intended? It is not the first message from you
having this effect on me, so I thought it best to make you aware of
it.

Friendly,

[Nicholas Miell]

Post by Petter Reinholdtsen
[Ulrich Drepper]

Post by Ulrich Drepper
Don't bother. That is one of the most stupid ideas I've read in a
while and it won't be added.

Can you explain why? Caching a bit more in nscd do not appear like
one of the stupid ideas I've read, so I wonder why it appear so stupid
to you.

If I had to guess, I'd say that getpwent() and getgrent() are terribly
designed interfaces that aren't threadsafe, aren't generally usable for
systems with more than a handful of accounts accessed via nss_files, and
are only included because POSIX requires them and ugly old code expects
them to exist. Furthermore, they aren't ever (or certainly shouldn't be)
used in performance critical situations.

Adding caching support to nscd increases complexity with
basically no gain, especially considering that nscd is designed for fast
random read-only access to specific datums, and not writable linear
traversals over an entire dataset.

For the kinds of things that getpwent() and getgrent() are used for,
you're better off using your directory service's native interface (LDAP,
Kerberos, BigTable?, etc.) or something generic like libuser (assuming
that has a sensible interface).

Post by Petter Reinholdtsen
BTW: Are you aware that your message appear very hostile? Reading
your messages make me wonder if my time would be better spend
elsewhere. Is this intended? It is not the first message from you
having this effect on me, so I thought it best to make you aware of
it.
Friendly,

[m***@google.com]

Post by Nicholas Miell

Post by Petter Reinholdtsen
Can you explain why? Caching a bit more in nscd do not appear like
one of the stupid ideas I've read, so I wonder why it appear so stupid
to you.

If I had to guess, I'd say that getpwent() and getgrent() are terribly
designed interfaces that aren't threadsafe, aren't generally usable for
systems with more than a handful of accounts accessed via nss_files, and
are only included because POSIX requires them and ugly old code expects
them to exist. Furthermore, they aren't ever (or certainly shouldn't be)
used in performance critical situations.

I'll agree with all of those statements.

Post by Nicholas Miell
Adding caching support to nscd increases complexity with
basically no gain, especially considering that nscd is designed for fast
random read-only access to specific datums, and not writable linear
traversals over an entire dataset.

Compared to how complex the rest of nscd is, it's not really that much
complexity to add this. But I wouldn't say that nscd is only for fast
access to specific data - that's thinking about it like a hardware cache.
It's a software cache, so we don't have as hard a limit on the amount of
data we can cache. If it speeds something up, and the amount of memory
used is reasonable, it's a good trade.

Post by Nicholas Miell
For the kinds of things that getpwent() and getgrent() are used for,
you're better off using your directory service's native interface (LDAP,
Kerberos, BigTable?, etc.) or something generic like libuser (assuming
that has a sensible interface).

The thing we'd like to speed up is tab-completion of usernames in bash,
and bash uses the getpwent() interface to do this. Adding this support to
nscd reduces the time required to tab complete ~ from several minutes to a
few seconds. It also decreases the network traffic, even if you only do
the tab completion only once, since bash (via readline) only counts the
users the first time it walks the user list - it walks the list again to
display them.

Mike Mammarella

[Nicholas Miell]

This post might be inappropriate. Click to display it.

[Mike Frysinger]

Post by Nicholas Miell
however I'd like to point out
that bash does have programmable completion and you may be able to
work up some hack to do user/group name caching at that level
(unfortunately, I don't think you can override builtin completion
methods, which means you can't just say "instead of using builtin user
completion, call this shell function instead").

but that wouldnt work on nearly the same scale as nscd ... you'd get a cache
for the active shell, but every new shell would have the same initial
(minutes long) penalty when doing user completion
-mike

[Nicholas Miell]

Post by Mike Frysinger

Post by Nicholas Miell
however I'd like to point out
that bash does have programmable completion and you may be able to
work up some hack to do user/group name caching at that level
(unfortunately, I don't think you can override builtin completion
methods, which means you can't just say "instead of using builtin user
completion, call this shell function instead").

but that wouldnt work on nearly the same scale as nscd ... you'd get a cache
for the active shell, but every new shell would have the same initial
(minutes long) penalty when doing user completion
-mike

Nothing stops you from maintaining a global cache shared by all shell processes.

I'd also like to point out that zsh's programmable completion does
allow you to override the default completion methods, which means you
could actually replace the default -tilde- context completion function
with one of your own choosing. I'm told that zsh is also superior to
bash in many other ways.

[Mike Frysinger]

Post by Nicholas Miell

Post by Mike Frysinger

Post by Nicholas Miell
however I'd like to point out
that bash does have programmable completion and you may be able to
work up some hack to do user/group name caching at that level
(unfortunately, I don't think you can override builtin completion
methods, which means you can't just say "instead of using builtin user
completion, call this shell function instead").

but that wouldnt work on nearly the same scale as nscd ... you'd get a
cache for the active shell, but every new shell would have the same
initial (minutes long) penalty when doing user completion

Nothing stops you from maintaining a global cache shared by all shell processes.

huh ? and how would you go about doing that ? shells are sep processes that
share no such data
-mike

[m***@google.com]

Post by Mike Frysinger

Post by Nicholas Miell
Nothing stops you from maintaining a global cache shared by all shell processes.

huh ? and how would you go about doing that ? shells are sep processes that
share no such data
-mike

Well, you could use some sort of Name Service Caching Daemon...

I've got it working fine now with my changes to nscd. I had asked about it
on this list to see what approach would be preferred by glibc maintainers,
but it sounds like they don't want it at all. So we'll just keep it
locally here, since nscd does what we want now.

Cheers all,
Mike Mammarella

[Nicholas Miell]

Post by m***@google.com

Post by Mike Frysinger

Post by Nicholas Miell
Nothing stops you from maintaining a global cache shared by all shell processes.

huh ? and how would you go about doing that ? shells are sep processes that
share no such data
-mike

Well, you could use some sort of Name Service Caching Daemon...
I've got it working fine now with my changes to nscd. I had asked about it
on this list to see what approach would be preferred by glibc maintainers,
but it sounds like they don't want it at all. So we'll just keep it
locally here, since nscd does what we want now.

There's no sense in not posting the patch somewhere so other people
can benefit from your work, even if it won't go upstream.