[tac_plus] RFC: refactoring hashing algorithm (was: contributing patched to tac_plus)

[David M. Syzdek]

Heasly,

Looking at the hashing algorithm used for storing devices, users, groups, and ACLs, it appears that at most 157 entries can be stored in each hash table (less if the key strings create a collision).  My organization currently has 1,428 devices with unique keys.  So I need a method which allows more than 157 entries to be stored in each hash table.

Refer to the following code from hash.c to see the limitation:

    tac_plus.h:
    220 #define HASH_TAB_SIZE 157        /* user and group hash table sizes */

    hash.c:
     32 /* Calculate hash value from a string */
     33 static int
     34 calculate_hash(char *name)
     35 {
     36     int i;
     37     int len = strlen(name);
     38     int hashval = 0;
     39
     40     for (i = 0; i < len; i++) {
     41         hashval += name[i] * (i + 1);
     42     }
     43     hashval += name[0];
     44     hashval = hashval > 0 ? hashval : -hashval;
     45     return(hashval);
     46 }
     47
     48 /* Lookup a name in a hash table.  Return its node if it exists, else NULL *    /
     49 void *
     50 hash_lookup(void **hashtab, char *name)
     51 {
     52     ENTRY *entry;
     53     int hashval = calculate_hash(name);
     54
     55     entry = hashtab[hashval % HASH_TAB_SIZE];
     56                     
     57     while (entry) {
     58         if (STREQ(name, entry->name))
     59             /* Node exists in table. return it */
     60             return(entry);
     61         entry = entry->hash;
     62     }    
     63     return(NULL);
     64 }    


I would like refactor hash.c to use a sorted array and binary search rather than a fixed length reallocated hash table.  This would incur a performance hit on start-up and slightly increase the time required to lookup items within the hash, I can add an autoconf option which will allow tac_plus to be compiled with the old hashing methods or the new hashing methods.

Does anyone foresee an issue with the proposed change?

--David M. Syzdek

----------------------------------------------------------------------
David M. Syzdek                             david.syzdek at acsalaska.net
IP Engineering                                   Work: +1 907 550 8389
                                                 Cell: +1 907 980 1151
Alaska Communications Systems, Inc
MS #53
600 Telephone Avenue
Anchorage, Alaska  99503
----------------------------------------------------------------------

> On Dec 3, 2014, at 8:38 AM, heasley <heas at shrubbery.net> wrote:
> 
> Tue, Dec 02, 2014 at 09:20:40AM -0900, David M. Syzdek:
>> Shrubbery Networks,
>> 
>> I am a systems engineer at a telco in Alaska.  We maintain a geographically large and diverse voice and data network consisting of thousands of devices.  Our TACACS+ server recently died and we are planning to replace it with your port of tac_plus, however it is missing a few features which we require, namely allowing different keys to be assigned per network rather than per individual hosts.  We are willing and capable of modifying the code to support the features we need, however to simplify maintenance in the future, we would like to contribute the patches back into your tree so we do not have to patch the source code in the future.
>> 
>> Do you accept patches for new features in tac_plus?  If so, what patch format do you prefer and which version should I use for the baseline? What documentation/comments do you look for in patches?
> 
> certainly; bonus points and quicker response if you keep the formatting
> consistent and also update documentation :)