Changed comments calling the code Cistron to FreeRADIUS. Corrected some

[freeradius.git] / doc / cache

FreeRADIUS Password Caching 

Acknowledgements

Thanks to Alan DeKok for the initial idea, to Dr. Bob Pilgrim for
implementation strategies, and to Miquel for putting it into FreeRADIUS.

What does this caching do?

It will add the capability to cache several of the system files that
are used often by FreeRADIUS. These include: /etc/passwd, /etc/shadow
(if necessary), and /etc/group.

By caching the information in these files and storing it in a VERY efficient
hash table, authentication lookups are sped up many times over. So, the
short answer is that your authentication requests will be faster if you use
caching, assuming you're using System authenication now. Read on for the
long answer.

How do I use it?

Compile radiusd as you normally would, and then set 'cache=yes' in your
radiusd.conf file.

Then, if you want to monitor how the caching is doing (errors and such),
'grep HASH /var/log/radius.log'.

What are the advantages?

Tremendous speed increase in authentication request handling. Orders of
magnitude, literally.

What are the disadvantages?

As with anything else, there are a couple of trade-offs. However, these are
quite modest, IMHO.

First, memory consumption of your radiusd process will go up somewhat over
normal operation. Depending on the size of your files, it could take several
megabytes of RAM to build the hash table properly. However, I have gone to
great lengths to ensure that there are no memory leaks. The size of the
daemon process should stay constant, or grow linearly with the size of your
system files. If you notice otherwise, send me an email with lots of detail
about your system and I'll see what I can find.

Second, you should kill -HUP the main radiusd process every so often out of
cron. The reason for this is because the daemon will need to rebuild the
cache to get passwords that you have changed for existing users. You will
not have to -HUP it for new users in /etc/passwd to get authenticated, as if
it can't find the user in the hash, it will automatically revert to the old
(slow) lookup methods [getpwnam()]. However, if you change the password for
a user, and the hash table contains that user but with the old password, it
will simply think that the user is supplying the wrong password and deny
them access. One thing I'd like to point out is that rebuilding the hash
with the -HUP takes less than a second with our ~1MB /etc/passwd and shadow
files. The slowest part of the -HUP is caused by the gethostby*() functions.
All in all, a -HUP reconfig is virtually instant on our solaris boxes, and
takes about 15 seconds on standard linux 2.x machines.

Why was it written?

In examining our radius servers, I noticed that there were several things
slowing down an authentication requests. Please note that some of these
things will depend on what you are doing in your raddb/users file, however,
most of the things we were doing were quite common, so I feel that others
may have similar setups. In any case, I'll go thru exactly what we were
seeing, and how caching fixes it.

Authentication Bottlenecks:
*Group check items calling getgrnam()
*DEFAULT users with System authentication calling getpwnam()
*Simultaneous use check reading file /var/log/radutmp

First, the auth request comes in, and radius (usually) forks a child to
handle it. The child will then check the raddb/users file to see if the user
is explicitly listed there. In our case, most the users were matched off of
a DEFAULT system entry, meaning they would be looked up in the /etc/passwd
and /etc/shadow files. However, first, we had to check for a couple of
groups that aren't allowed access. In our case we had two DEFAULT group
compare check items, meaning that the getgrnam() system call was called
twice for every authentication request. Considering that the /etc/group file
is not so large, that wasn't a huge factor. However, the /etc/group file is
stored on disk, and was accessed through system calls, meaning it had to be
opened and searched until a matching group was found (twice), slowing down
authentication requestions somewhat.

Ok, so we've established that there's a getgrnam() call for each DEFAULT
user you have with a group check item. If you don't have any such DEFAULTs,
no problem, you don't have those calls. However, nearly 99% of you probably
have a line like the following in your raddb/users file, leading into the
next bottleneck: DEFAULT Auth-Type = System, Simultaneous-Use = 1

What does that mean? It means, for every auth request that comes in for
which we don't have an explicit match in our raddb/users file, lookup the
user in /etc/passwd and/or /etc/shadow using getpwnam() and getspwnam()
system calls. So what's so bad about that? It works right? Well, yes, but
it's inefficient because of the way getpwnam() works.

Think for a second about what getpwnam() has to do. It is a linear search
algorithm through an unsorted list stored on disk. It is an O(N) algorithm,
for you computer science folks (barring any caching build into the function
by particular OSs). So, basically, what it does is open the /etc/passwd
file, start at line one, compare that user to the user we're looking for,
and if there's no match, go to the next line and repeat. That means that on
average, every auth request you're taking requires opening and reading half
of your /etc/passwd file. Worst case is when a user not in the file is
looked up, as you search the entire file without a match. Best case is when
the user is the first one in the file, and average is in the middle
somewhere.

Are you saying, that doesn't sound so bad? Well, then perhaps caching
isn't for you. In our case, we had a ~15,000 line passwd file, and anywhere
from 20-40,000 logins daily. The getpwnam() call was taking by far the
majority of the radius daemon's time, resulting in fairly poor
authentication performance.

NOTE:  radutmp caching is disabled for now until we can find a better way 
to do it.  Still, this next paragraph indicates why it needs doing.

Lastly, if you're using the wonderful simultaneous-use check item in 
FreeRADIUS, you have another disk lookup to perform on your /var/log/radutmp
file (actually, caching of this file just came available in b17. glad
somebody else noticed it :) What happens is, if the user is authenticated
properly, the daemon then opens the radutmp file, reads until it hits a line
matching the user currently requesting authentication, and then either
allows or denies access based on the presense or absense of a match. Thus,
in the majority of cases, you read the entire file in for every
authentication request (assuming that most of your users aren't trying to
steal service from you :) .

So, we've identified the problems. If you really care about how caching
addresses those problems, keep reading.

How does it work?

The code will first open your /etc/passwd file and runs through it hashing
all the usernames into a numeric index into my hash table. It then creates
an entry into the hashtable at that index for every user in the file.
Currently, it caches username, password, gid, and uid in the entry. Then, if
you have shadow passwords, it will open your /etc/shadow file and put the
passwords into the entry corresponding with the appropriate user. It is this
hash table that allows us to eliminate the getpwnam() bottleneck. Read below
for how to test it.

Next, it will read the /etc/group file and build a singly linked list of it.
It's not as fast as the hash, but the group file is usually small enough
that it wouldn't make a difference. Just brining it into RAM should be good
enough. This takes care of the getgrnam() bottleneck.

NOTE:  Again, radutmp caching is disabled.  Disregard this next paragraph.

Finally, it reads the /var/log/radutmp file and marks every user listed as
logged in with a login variable stored in their hash entry. Then, every time
a user logs in or out, that variable is updated so that we can avoid reading
in /var/log/radutmp.

So what, right? Well, understand that for every user lookup done on a
system, you have currently to read half of your passwd file. Thus, the
number of comparisons done per getpwnam() is the number of lines in your
passwd file divided by two. So do 'wc -l /etc/passwd', divide that by two,
and that's the number of comparisons done per user lookup on your system
right now.

Using the hash table method, I have achieved user lookups in RAM in near
constant time. That is, using my passwd files (everyone's is different,
obviously), I could find a user in the hash in 1.0673 comparisons (on
average). Being that 1.0 is the lowest number of comparisons possible,
that's a pretty significant thing. Again, for the computer science people,
the hash function and table are wide enough such that 87.4% of users are
stored singly in a bucket, 11.7% are stored with two users in a bucket, 0.8%
are stored with 3 users in the bucket, and 0.03% are stored with more than 3
users per bucket. That means that 87% of your lookups are done in one
comparison, versus the number you got when you did the 'wc -l /etc/passwd' /
2 above. This discussion has also neglected the fact that RAM searches are
many, many times faster than disk searches. We'll let it speak for itself.

But, you don't have to take my word for it. I have a test program that I've
written that can show you the difference on your own system between the
speed in lookups using the hash and getpwnam().  You can find the program
cachetest.c at this end of this file.  Simply save it to cachetest.c and
and compile it with: 

gcc -o cachetest ./cachetest.c

What it does is read in your passwd file, build a hash of it, and then
perform the number of lookups you specify either with getpwnam() or using
the hash lookup functions.

Before performing tests, please note that the larger the passwd file, the
larger the disparity between the two test methods. So you'll get a more
accurate depiction of what the code will do for your system by running it
on a passwd file on your radius server.

I'd recommend doing the following tests with it:

# Perform 1,000 lookups using getpwnam()
./cachetest 1000 -s

# Perform 1,000 lookups using the hash
./cachetest 1000

My guess, no real significant difference in the time taken to complete each
of those. Next test.

# Perform 10,000 lookups using getpwnam()
./cachetest 10000 -s

# Perform 10,000 lookups using the hash
./cachetest 10000

Unless you've got a real fast machine, you should have noticed a little bit
of difference between the two that time. Next test

# Perform 50,000 lookups using getpwnam()
./cachetest 50000 -s

# Perform 50,000 lookups using the hash
./cachetest 50000

Unless you have a cray, I'm real confident you noticed a difference that
time. If the 50,000 user lookup didn't extraordinarily long on your system,
try this last test.

# Perform 100,000 lookups using getpwnam()
./cachetest 100000 -s

# Perform 100,000 lookups using the hash
./cachetest 100000

No doubt, you saw the difference here. Unless you want to be old and gray
when you finish the getpwnam() tests, I'd recommend not going higher than
100,000. Still, it's up to you. Go as high as you want on the hash test.
1,000,000 hash lookups are done in about a second on my pentium 400 running
linux.

How will it help my radius server?

Well, assuming you can live with the disadvantages listed above, it'll make
it faster. If you haven't run the tests in the above section, I'd recommend
doing so.

Is it stable?

As far as I can tell, yes. We've run it on both linux and solaris maches for
about two weeks now, and had zero problems. If you notice a bug, by all
means, let me know and I'll see if I can get a fix out. However, if you
notice system degrading problems with it, you can always turn it off in
your radiusd.conf file.

Ok, that's it. If you made it this far, I'm impressed. Let me know what you
think...

jeff@apex.net

--------------------------------------------------------------------------

/*
 * cachetest.c:  Tests performance difference between user lookups in
 * the hash table vs. getpwnam()
 *
 * All users in the passwd/shadow files are stored in a hash table.
 * the hash lookup is VERY fast,  generally 1.0673 comparisons per
 * lookup.  For the unitiated, that's blazing.  You can't have less
 * than one comparison, for example.
 *
 *      (c) 1999 Author - Jeff Carneal, Apex Internet Services, Inc.
 */    
/* 
        COMPILE:  gcc -o cachetest cachetest.c
*/
#include<stdio.h>
#include<fcntl.h>
#include<grp.h>
#include<unistd.h>
#include<stdlib.h>
#include<errno.h>
#include<ctype.h>
#include<sys/stat.h>
#include<sys/types.h>
#include<string.h>

/* Misc definitions */
#define BUFSIZE  1024
#define MAXUSERNAME 20
#define HASHTABLESIZE 100000
#define PASSWDFILE "/etc/passwd"

/* Structure definitions */
struct mypasswd {
        char    *pw_name;       /* user name */
        char    *pw_passwd;     /* user password */
        uid_t   pw_uid;         /* user id */
        gid_t   pw_gid;         /* group id */
        int     loggedin;       /* number of logins */
        struct mypasswd *next;  /* next */
};

/* Function prototypes */
int buildHashTable(void);
struct mypasswd *findHashUser(const char *user);
int storeHashUser(struct mypasswd *new, int index);
int hashUserName(const char *s);
int doHashTest(int numusers, unsigned long numlookups);
int usage(void);

/* Make the tables global since so many functions rely on them */
static struct mypasswd *hashtable[HASHTABLESIZE];
static struct mygroup *grphead = NULL;

char allusers[HASHTABLESIZE][MAXUSERNAME];
int usegetpwnam=0;

int main(int argc, char** argv) {
        int numusers=0;
        unsigned long numlookups=0;
        
        if(argc<2) {
                usage();
        }
                
        if(isdigit(argv[1][0])) {
                numlookups = atoi(argv[1]);     
        } else {
                usage();
        }
        if((argv[2] != NULL) && !strncmp(argv[2],"-s",2)) {
                usegetpwnam = 1;
        }
        
        memset((char *)allusers, 0, MAXUSERNAME*HASHTABLESIZE);

        numusers = buildHashTable();
        if(numusers < 0) {
                printf("HASH:  Error building hash table!  Quitting...\n");
                exit(1);
        }

        doHashTest(numusers, numlookups);
        printf("Done!\n\n");

}

/* Builds the hash table up by storing passwd/shadow fields
 * in memory.  Returns -1 on failure, 0 on success.
 */
int buildHashTable(void) {
        FILE *passwd, *shadow;
        char buffer[BUFSIZE];
        char idtmp[10];
        char username[MAXUSERNAME];
        char *ptr, *bufptr;
        int len, hashindex, numread=0;
        struct mypasswd *new, *cur, *next;

        memset((char *)username, 0, MAXUSERNAME);

        /* Init hash array */
        memset((struct mypasswd *)hashtable, 0, (HASHTABLESIZE*(sizeof(struct mypasswd *))));

        if( (passwd = fopen(PASSWDFILE, "r")) == NULL) {
                printf("HASH:  Can't open file %s:  %s", PASSWDFILE, strerror(errno));
                return -1;
        } else {
                while(fgets(buffer, BUFSIZE , passwd) != (char *)NULL) {
                        numread++;

                        bufptr = buffer;
                        /* Get usernames from password file */
                        for(ptr = bufptr; *ptr!=':'; ptr++);
                        len = ptr - bufptr;
                        if((len+1) > MAXUSERNAME) {
                                printf("HASH:  Username too long in line: %s", buffer);
                        }
                        strncpy(username, buffer, len);
                        username[len] = '\0';
                        if(numread < HASHTABLESIZE) {
                                strncpy(allusers[numread-1], username, MAXUSERNAME);
                        }

                        /* Hash the username */
                        hashindex = hashUserName(username);     
                        /*printf("%s:%d\n", username, hashindex);*/
        
                        /* Allocate space for structure to go in hashtable */
                        if((new = (struct mypasswd *)malloc(sizeof(struct mypasswd))) == NULL) {
                                printf("HASH:  Out of memory!");
                                return -1;
                        }
                        memset((struct mypasswd *)new, 0, sizeof(struct mypasswd));

                        /* Put username into new structure */
                        if((new->pw_name = (char *)malloc(strlen(username)+1)) == NULL) {
                                printf("HASH:  Out of memory!");
                                return -1;
                        }
                        strncpy(new->pw_name, username, strlen(username)+1);

                        /* Put passwords into array, if not shadowed */
                        /* Get passwords from password file (shadow comes later) */
                        ptr++;
                        bufptr = ptr;
                        while(*ptr!=':')
                                ptr++;

                        #if defined(NOSHADOW)
                        /* Put passwords into new structure (*/
                        len = ptr - bufptr;
                        if((new->pw_passwd = (char *)malloc(len+1)) == NULL) {
                                printf("HASH:  Out of memory!");
                                return -1;
                        }
                        strncpy(new->pw_passwd, bufptr, len);
                        new->pw_passwd[len] = '\0';
                        #endif /* NOSHADOW */  

                        /* 
                    * Put uid into structure.  Not sure why, but 
                         * at least we'll have it later if we need it
                         */
                        ptr++;
                        bufptr = ptr;
                        while(*ptr!=':')
                                ptr++;
                        len = ptr - bufptr;
                        strncpy(idtmp, bufptr, len);
                        idtmp[len] = '\0';
                        new->pw_uid = (uid_t)atoi(idtmp);       

                        /* 
                    * Put gid into structure.  
                         */
                        ptr++;
                        bufptr = ptr;
                        while(*ptr!=':')
                                ptr++;
                        len = ptr - bufptr;
                        strncpy(idtmp, bufptr, len);
                        idtmp[len] = '\0';
                        new->pw_gid = (gid_t)atoi(idtmp);       

                        /* 
                         * We're skipping name, home dir, and shell
                         * as I can't think of any use for storing them
                         */

                        /*printf("User:  %s, UID:  %d, GID:  %d\n", new->pw_name, new->pw_uid, new->pw_gid);*/
                        /* Store user in the hash */
                        storeHashUser(new, hashindex);
                }       /* End while(fgets(buffer, BUFSIZE , passwd) != (char *)NULL) { */
        } /* End if */
        fclose(passwd);

        return numread;
}

/*
 * Looks up user in hashtable.  If user can't be found, returns 0.  
 * Otherwise returns a pointer to the structure for the user
 */
struct mypasswd *findHashUser(const char *user) {

        struct mypasswd *cur;
        int index;

        /* first hash the username and get the index into the hashtable */
        index = hashUserName(user);

        cur = hashtable[index];

        while((cur != NULL) && (strcmp(cur->pw_name, user))) {
                cur = cur->next;
        }

        if(cur) {
                return cur;
        }

        return (struct mypasswd *)0;

}

/* Stores the username sent into the hashtable */
int storeHashUser(struct mypasswd *new, int index) {

        /* store new record at beginning of list */
        new->next = hashtable[index];
        hashtable[index] = new;

        return 1;
}

/* Hashes the username sent to it and returns index into hashtable */
int hashUserName(const char *s) {
     unsigned long hash = 0;

     while (*s != '\0') {
         hash = hash * 7907 + (unsigned char)*s++;
                }

     return (hash % HASHTABLESIZE);
}              

int doHashTest(int numusers, unsigned long numlookups) {
        int i, numlookedup = 0;

        /* Use pokey getpwnam() syscall to find users */
        if(usegetpwnam) {
                printf("\nUsing getpwnam() lookup for %d user lookups over %d users found\n\n", numlookups, numusers);
                while(numlookedup < numlookups) {
                        for(i=0; i<numusers; i++) {
                                if(numlookedup >= numlookups) 
                                        return 0;

                                if(allusers[i] != NULL)  {
                                        getpwnam(allusers[i]);
                                        numlookedup++;
                                }
                        }
                }

        /* Use blazing fast hash method to find user */
        } else {
                printf("\nUsing hash lookup for %d user lookups over %d users found\n\n", numlookups, numusers);
                while(numlookedup < numlookups) {
                        for(i=0; i<numusers; i++) {
                                if(numlookedup >= numlookups) 
                                        return 0;

                                if(allusers[i] != NULL)  {
                                        findHashUser(allusers[i]);
                                        numlookedup++;
                                }
                        }
                }
        }
        return 0;
}

int usage() {
        printf("\nUsage:  ./cachetest #lookups [-s]\n");
        printf("\n\tPerform 50,000 lookups using the hash method");
        printf("\n\tEx:  ./cachetest 50000\n");
        printf("\n\tPerform 50,000 lookups using the getpwnam() syscall");
        printf("\n\tEx:  ./cachetest 50000 -s\n\n");
        exit(1);

}