/*
 * This module provides a cache of authenticator successful authenticator
 * requests, allowing multiple related requests to bypass the authenticator
 * some of the time.
 *
 * For each request to the authenticator, a signature is generated
 * from the following components:
 *     client IP address
 *     local server port
 *     protection setup file, prepended with translated path if 'with document'
 *     certificate identifier header lines (if produced).
 *     authorization header lines.
 *
 * Note that this code is not threadsafe, calls into this module must
 * be serialized by the callers (normally, the same serialization used for
 * the authenticator communication will be used).
 *
 * Usage:
 *     1. Create signature context with authcache_begin_signature.
 *     2. Append header data that would be supplied to authenticator
 *	  with authcache_end_signature (one or more calls).
 *     3. Test for existing cache entry that matches signature with
 *        with authcache_check_signature.
 *     4a. (match found) allow access as username returned in step 3.
 *     4b. (not found) Call authenticator and call authcache_end_signature
 *         if authenticator allows access.
 *
 * In general, each returns the context pointer to be used in the next
 * call or NULL on error.
 *
 * Author:	David Jones
 * Date:	28-FEB-2002
 * Revised:	1-MAR-2002		Adjust memory allocation.
 */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include "tutil.h"
#include "authcache.h"			/* verify prototypes */
/*
 * The request signature is used to optimize authenticator calls by caching
 * sucessful authorization headers.
 */
struct req_signature {
    struct req_signature *next;		/* Fwd pointer in hash chain/freelist */
    struct req_signature *lru_prev;	/* Least recently used list */
    struct req_signature *lru_next;
    time_t timeout;
    int hash;				/* Index in hash table (for removal) */
    char username[40];			/* value for data storage */

    int local_port;
    unsigned char remote_addr[4];
    int data_used;			/* Used portion */
    char method[8];
    char data[1000];			/* storage for setup file name, CERT, */
					/* and authorization headers */
};

static int authcache_size=0;		/* max number of entries allowed */
static int authcache_timeout=0;
int http_log_level;
int tlog_putlog ( int, char *, ... );
static struct req_signature **hash_table;
static struct req_signature *free_list;
/*
 * The LRU list orders the non-free blocks by least recent successful lookup.
 */
static struct req_signature *lru_first;	/* least recently used. */
static struct req_signature *lru_last;	/* most recently used */
static int hash_mask;			/* size of hash_table-1 */
/*****************************************************************************/
/* Memory managment functions.
 */
struct req_signature *alloc_sig()
{
    struct req_signature *blk, *hblk, *prev;
    int i;
    /*
     * Draw from free list if possible.
     */
    blk = free_list;
    if ( free_list ) {
	free_list = blk->next;
    } else {
      /*
       * Draw from LRU list.
       */
      blk = lru_first;
      if ( !blk ) {
	tlog_putlog ( 0, 
		"BUGcheck, allocation failure in authenticator cache!/" );
	return blk;
      }
      lru_first = blk->lru_next;
      if ( !lru_first ) lru_last = lru_first;
      /*
       * Remove from hash table.
       */
      hblk = hash_table[blk->hash];
      if ( blk == hblk ) {
	/*
	 * First in list (likely case).
	 */
	hash_table[blk->hash] = blk->next;
      } else {
	/*
	 * Not first in list, find block in hash chain, saving previous block.
	 */
	do {
	    if ( !hblk ) {
		tlog_putlog ( 0, 
		    "BUGcheck, hash table corruption in authenticator cache!/");
		return hblk;
	    }
	    prev = hblk;
	    hblk = hblk->next;
	} while ( hblk != blk );
	/*
	 * Adjust chain to skip over target block.
	 */
	prev->next = blk->next;
      }
    }
    /*
     * Initiatlize fields in block.
     */
    blk->next = (struct req_signature *) 0;
    blk->lru_prev = blk->lru_next = (struct req_signature *) 0;
    blk->hash = hash_mask + 1;		/* Garanteed emtpy hash entry */
    blk->username[0] = '\0';		/* Null username */
    blk->data_used = 0;
    memset ( blk->method, 0, sizeof(blk->method) );
    return blk;
}
/*****************************************************************************/
/* Manage the LRU list.
 */
static void lru_remove ( struct req_signature *sig )
{
     if ( sig->lru_prev ) sig->lru_prev->lru_next = sig->lru_next;
     else lru_first = sig->lru_next;

     if ( sig->lru_next ) sig->lru_next->lru_prev = sig->lru_prev;
     else lru_last = sig->lru_prev;
}
static void lru_append ( struct req_signature *sig )
{
     if ( lru_first ) {
	sig->lru_prev = lru_last;
	lru_last->next = sig;
     } else {
	lru_first = sig;
	sig->lru_prev = (struct req_signature *) 0;	/* first in list */
     }
     
     sig->lru_next = (struct req_signature *) 0;	/* always last */
     lru_last = sig;
}
/*****************************************************************************/
/* The hash function computes a hash value in the range 0..hash_mask from
 * fields local_port, remote_addr, method, and data[0..data_used-1].
 *
 * Use the good old VMS logical name hash algorithm.
 */
static int hash_signature ( struct req_signature *sig )
{
    int hash, i, octet;
    char *ptr;

    hash = ((sig->local_port&255)*577) & hash_mask;
    hash = hash_mask & (577*(sig->local_port>>8) ^ hash*3);

    for ( i = 0; i < sizeof(sig->remote_addr); i++ ) {
	octet = sig->remote_addr[i];
	hash = hash_mask & (octet*577 ^ hash*3);
    }

    for ( ptr = sig->method; *ptr; ptr++ ) {
	octet = (unsigned) *ptr;
	hash = hash_mask & (octet*577 ^ hash*3);
    }

    ptr = sig->data;
    for ( i = 0; i < sig->data_used; i++ ) {
	octet = (unsigned) *ptr; ptr++;
	hash = hash_mask & (octet*577 ^ hash*3);
    }

    return hash;
}
/*
 * Return true if 2 signature blocks holds the same signature.
 */
static int sigs_equal ( struct req_signature *sig1, 
	struct req_signature *sig2 )
{
    int i;
    /*
     * Most likely difference is in remote address, followed by length, 
     * check them first.  Return nomatch status on first difference.
     */
    for ( i = 0; i < sizeof(sig1->remote_addr); i++ ) {
	if ( sig1->remote_addr[i] != sig2->remote_addr[i] ) return 0;
    }
    if ( sig1->data_used != sig2->data_used ) return 0;
    if ( sig1->local_port != sig2->local_port ) return 0;
    /*
     * Check general data (setup file) and finally method (almost always GET).
     */
    if ( memcmp ( sig1->data, sig2->data, sig1->data_used ) != 0 ) return 0;
    if ( tu_strncmp ( sig1->method, sig2->method, sizeof(sig1->method) ) != 0 )
	return 0;
    /*
     * Getting here means everything equal, so return a match status.
     */
    return 1;
}
/*****************************************************************************/
/* The initialize function is called at program startup to create the
 * cache.
 */
int authcache_initialize ( int size, int timeout_seconds )
{
    int i, ht_size;;
    /*
     * Ensure only called once.
     */
    if ( authcache_size != 0 ) {
	tlog_putlog ( 0, 
		"Attempt to multiply initialize authenticator cache!/");
    } else if ( size == 0 ) {
	tlog_putlog ( 0, "Authenticator cache disabled!/" );
	return 1;
    }
    /*
     * Allocate storage for cache entries in 1 large block and build free list.
     * Allocate 1 extra struct to use as the client's cache context.
     */
    free_list = malloc ( (size+1) * sizeof(struct req_signature) );
    if ( !free_list ) {
	tlog_putlog ( 0, 
	    "Error allocating authenticator cache (!SL entries)!/",
	    size );
	return 0;
    }
    for ( i = 1; i <= size; i++ ) free_list[i-1].next = &free_list[i];
    free_list[size].next = (struct req_signature *) 0;
    /*
     * Size hash table to largest power of 2 less than cache size.
     * Allocate an extra entry we can use as a placeholder.
     */
    for ( ht_size=2; (ht_size+ht_size) < size; ht_size = ht_size+ht_size );

    hash_table = malloc ( (1+ht_size) * sizeof(struct req_signature *) );
    if ( !hash_table ) {
	tlog_putlog ( 0, 
	    "Error allocating authenticator cache hash_table (!SL entries)!/",
	    ht_size );
	free ( free_list );
	return 0;
    }
    hash_mask = ht_size - 1;
    for (i = 0; i <= ht_size; i++) hash_table[i] = (struct req_signature *) 0;
    /*
     * Set initial LRU list to emtpy since hash table is empty.
     */
    lru_first = (struct req_signature *) 0;
    lru_last = (struct req_signature *) 0;
    /*
     * Save size as indicator that initialization was successful.
     */
    authcache_size = size;
    authcache_timeout = timeout_seconds;

    if ( http_log_level > 0 ) tlog_putlog ( 1, 
	"Authenticator cache initialized with size of !SL and timeout of !SL.!/",
	authcache_size, authcache_timeout );
    return 1;
}

void *authcache_begin_signature ( int local_port, unsigned char *remaddr,
	char *method, char *setup_filename, char *ident )
{
    struct req_signature *sig;
    int length, i;
    /*
     * Don't do anything if cache not created.
     */
    if ( authcache_size <= 0 ) return (void *) 0;
    /*
     * Allocate a signature block and initiatlize with caller's data.
     */
    sig = alloc_sig();
    if ( sig ) {
	sig->local_port = local_port;
	memcpy ( sig->remote_addr, remaddr, sizeof(sig->remote_addr) );
	tu_strnzcpy ( sig->method, method, sizeof(sig->method)-1 );

	if ( *setup_filename == '.' ) {
	    /*
	     * Support the special authenticator hack of 'with directory'
	     * setup files.  Prepend ident string.
	     */
	    for ( length = i = 0; ident[i]; i++ ) 
		if ( ident[i] == '/' ) length = i + 1;

	    if ( (length + sig->data_used) >= sizeof(sig->data) ) {
		sig->next = free_list;
		free_list = sig;
		return (void *) 0;		/* failure */
	    }
	    tu_strncpy ( &sig->data[sig->data_used], ident, length );
	    sig->data_used += length;
	}

	length = tu_strlen ( setup_filename );
	if ( (length + sig->data_used) >= sizeof(sig->data) ) {
	    sig->next = free_list;
	    free_list = sig;
	    return (void *) 0;		/* failure */
	}
	tu_strcpy ( &sig->data[sig->data_used], setup_filename );
	sig->data_used += (length+1);		/* include terminating NUL */
    }
    return (void *) sig;
}
/*
 * Failure causes the context to be destroyed and a null value returned,
 * otherwise ctx is the return value.
 */
void *authcache_add_signature ( void *ctx, char *hdr, int hdrlen )
{
    struct req_signature *sig;

    if ( !ctx ) return 0;
    sig = (struct req_signature *) ctx;

    if ( (hdrlen+sig->data_used) >= sizeof(sig->data) ) {
	/*
	 * Not enough room in signature block, kill it.
	 */
	sig->next = free_list;
	free_list = sig;
	return (void *) 0;
    }
    /*
     * Copy data raw (if header lines, should inlcude line feeds).
     */
    memcpy ( &sig->data[sig->data_used], hdr, hdrlen );
    sig->data_used += hdrlen;

    return sig;
}

/*
 * Return value is handle to signature block added to cache or
 * null if match found.
 */
void *authcache_check_signature ( void *ctx, char *username, int usize )
{
    struct req_signature *sig, *hblk, *prev;

    if ( !ctx ) return 0;
    sig = (struct req_signature *) ctx;
    /*
     * Finalize the signature block (compute hash) and search for matching 
     * block in cache.
     */
    sig->hash = hash_signature ( sig );

    prev = (struct req_signature *) 0;		/* initially no previous */
    for ( hblk = hash_table[sig->hash]; hblk; hblk = hblk->next ) {
	if ( sigs_equal ( hblk, sig ) ) break;
	prev = hblk;
    }

    if ( hblk ) {
	/*
	 * Match found, see if stale and remove if so.
	 */
	time_t now, x;
	now = time ( &x );
	if ( now > hblk->timeout ) {
	    /*
	     * Must remove from both hash table and LRU list.
	     */
	    if ( http_log_level > 9 ) tlog_putlog(10,
		"Matched authenticator cache entry expired, deleting...!/" );
	    if ( prev ) {
		prev->next = hblk->next;
	    } else {
		/* First in list */
		hash_table[sig->hash] = hblk->next;
	    }
	    lru_remove ( hblk );
	    /*
	     * Place removed block on free list
	     */
	    hblk->next = free_list;
	    free_list = hblk;
	    hblk = (struct req_signature *) 0;
	}
    }

    if ( hblk ) {
	/*
	 * Match found, move block to end of lru list, return username to
	 * caller, and deallocate signature block.
	 */
	if ( hblk != lru_last ) {
	    lru_remove ( hblk );		/* delete from old position */
	    lru_append ( hblk );		/* add to end */
	}

	tu_strnzcpy ( username, hblk->username, usize-1 );
	sig->next = free_list;
	free_list = sig;

	return (void *) 0;

    }
    return (void *) sig;
}

void authcache_end_signature ( void *ctx, int status, char *username )
{
    struct req_signature *sig;
    time_t now;

    if ( !ctx ) return;
    sig = (struct req_signature *) ctx;
    if ( !sig ) return;

    if ( status ) {
	/*
	 * Keep the block, fill in username data and insert in hash table.
	 */
	int ndx;
	tu_strnzcpy ( sig->username, username, sizeof(sig->username)-1 );

	ndx = sig->hash;
	if ( (ndx < 0) || (ndx > hash_mask) ) {
	    /*
	     * Proper hash value not computed for this block.
	     */
	    tlog_putlog ( 0, "BUGcheck, invalid signature block on end!" );
	} else {
	    sig->next = hash_table[ndx];
	    hash_table[ndx] = sig;
	    /*
	     * Compute timeout value that gets checked by '_check_signature.
	     */
	    sig->timeout = time ( &now ) + authcache_timeout;
	    /*
	     * Add to end of LRU list.
	     */
	    lru_append ( sig );
	}
    } else {
	/*
	 * Don't keep this block (authenticator rejected request), put
	 * block on free list.
	 */
	sig->next = free_list;
	free_list = sig;
    }
}
