Discussion:
nscd caching getpwent() and getgrent()
(too old to reply)
m***@google.com
2006-08-02 22:15:35 UTC
Permalink
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
2006-08-02 22:21:15 UTC
Permalink
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.
--
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖
Petter Reinholdtsen
2006-08-03 07:11:30 UTC
Permalink
[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,
--
Petter Reinholdtsen
Nicholas Miell
2006-08-04 01:08:32 UTC
Permalink
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
2006-08-04 01:33:48 UTC
Permalink
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
2006-08-04 02:23:32 UTC
Permalink
Post by 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.
Ah ha! A valid use case!

Of course, what you really want is method of doing pattern-based
queries on the account database and a bash patch to use that.
Unfortunately, this is probably straying into the domain of a more
specialized account management library.

OTOH, if such a function were added to glibc, it would make sense to
add nscd caching, (conceptually) it wouldn't be any different than
caching a series of get{pw,gr}nam{,_r} calls, with the caveat that you
need to also keep track of whether your cached result set for a query
is still complete after any garbage collection.

As to the original question, well, Ulrich has already made up his mind
and that's notoriously hard to change, 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").
Mike Frysinger
2006-08-04 16:00:26 UTC
Permalink
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
2006-08-05 00:35:18 UTC
Permalink
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
2006-08-05 01:45:24 UTC
Permalink
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
2006-08-07 18:22:50 UTC
Permalink
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
2006-08-07 18:45:04 UTC
Permalink
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.

Loading...