增加共享内存hash链表操作

cheliequan

2022-12-08 7e877be8fb34ab99421a2eaf3d8fb1b96ed95206

增加共享内存hash链表操作

 include/shmht.h

New file
@@ -0,0 +1,140 @@
#ifndef __HASHTABLE_CWC22_H__
#define __HASHTABLE_CWC22_H__

#include <unistd.h>

struct shmht;

/*! \mainpage lib_shmht
 *
 * \section Introduction
 *
 * The lib_shmht is a full-functionall hashtable implementation in shared memory.<BR>
 * This library is designed for high-performace caches, but it can be used for
 * many pourpouses. <BR>
 * Design principles of the lib_shmht: <BR>
 * <b>no-reallocation</b> of the shared memory. So, the HT can't grow in size from it's creation, but you
 * can define the % of older entries that can be erased when a element has not enought
 * space.<BR>
 * <b>concurrency</b>: The accesses are controlled by a semaphore R/W lock implemntation, so not concurrency
 * problem is possible.<BR>
 * <b>performance</b>: The performance is the main target of this implementation.<BR>
 *
 * It has the next <b>limitations</b>: <BR>
 *  * Key size limited by compiling time.<BR>
 *  * The erased elements are the oldests, not the less used. This is to don't write (and lock the entire ht)
 * in all the reads.<BR>
 *
 * Please, check the design file if you want more specifical data.
 * 
 */


/*!   
 * @name                    shmht_hashtable
 * @param   name            Name of the HashTable.
 * @param   number          Number of records.
 * @param   size            Size of each record.
 * @param   hashfunction    function for hashing keys.
 * @param   key_eq_fn       function for determining key equality
 * @return                  newly created hashtable or NULL on failure
 *
 * This function, takes the existing shared memory, or creates if it does not
 * exists.
 * The name is the primary key of the shared memory hash table. If it exists, 
 * the create_hashtable will asociate with the apropiate shared memory.
 *
 */

struct shmht *create_shmht(char *name,
                unsigned int number,
                size_t size,
                unsigned int (*hashfunction) (void *),
                int (*key_eq_fn) (void *, void *));

/*!   
 * @name        shmht_insert
 * @param   h   the hashtable to insert into
 * @param   k   the key - hashtable claims ownership and will free on removal
 * @param   v   the value - does not claim ownership
 * @return      > zero for successful insertion, else for error.
 *
 * This function does not check for repeated insertions with a duplicate key.
 * The value returned when using a duplicate key is undefined.
 * If in doubt, remove before insert.
 * The size of this hashtable is fixed, so if the hashtable is full, the insert
 * will fail.
 */

int
shmht_insert (struct shmht *h, void *k, size_t key_size, void *v,
                  size_t value_size);


/*!   
 * @name        shmht_search
 * @param   h   the hashtable to search
 * @param   k   the key to search for  - does not claim ownership
 * @param key_size Size of the key.
 * @param returned_size [out], the size of the returned value.
 * @return      the value associated with the key, or NULL if none found
 * 
 * You should be careful, beacause, this function returns a pointer to the 
 * shared memory area. DO NOT FREE THIS POINTER!
 */

void *shmht_search (struct shmht *h, void *k, size_t key_size,
                        size_t * returned_size);


/*!   
 * @name        shmht_remove
 * @param   h   the hashtable to remove the item from
 * @param   k   the key to search for  - does not claim ownership
 * @param returned_size  [out] returns the size of the returned void *.
 * @return      the number of items removed.
 */

int shmht_remove (struct shmht *h, void *k, size_t key_size);



/*!   
 * @name        shmht_count
 * @param   h   the hashtable
 * @return      the number of items stored in the hashtable, -1 if something
 *              nasty happens.
 */
int shmht_count (struct shmht *h);


/*!   
 * @name        shmht_flush
 * @param   h   the hashtable
 * @return      0 if not problem, <0 if error.
 */

int shmht_flush (struct shmht *h);

/*!
 * @name        shmht_remove_older_entries
 * @param   h   the hashtable
 * @param   p   the % of older values to erase
 * @return      The number of deleted entries.
 */

int shmht_remove_older_entries (struct shmht *h, int p);

/*!   
 * @name        shmht_destroy
 * @param   h   the hashtable
 * 
 * Be careful with this operation, beacause all the processes that are currently
 * using the shared memory hash table will fail (it deletes the shared memory and
 * the semaphores used as mutex). 
 * If you have any doubt, use the hashtable_flush, instead of this function.
 */

int shmht_destroy (struct shmht *h);

#endif /* __HASHTABLE_CWC22_H__ */

 include/shmht_debug.h

New file
@@ -0,0 +1,13 @@
#ifndef __HASHTABLE_DEBUG__HH__
#define __HASHTABLE_DEBUG__HH__

//#define __SHMT_DEBUG_MODE__

#ifdef __SHMT_DEBUG_MODE__
#include <stdio.h>
#define shmht_debug(a) printf a
#else
#define shmht_debug(a)
#endif

#endif //__HASHTABLE_DEBUG__HH__

 include/shmht_private.h

New file
@@ -0,0 +1,90 @@
#ifndef __HASHTABLE_PRIVATE_CWC22_H__
#define __HASHTABLE_PRIVATE_CWC22_H__

#include "shmht.h"
#include <fcntl.h>           /* For O_* constants */
#include <sys/stat.h>        /* For mode constants */
#include <semaphore.h>

//Max size of a key = > By default 512 bytes.
#define MAX_KEY_SIZE 512
/*****************************************************************************/

struct entry
{
    //Marks if the entry is used or not.
    int used;
    //Store the key in a char array, later, transform to a void *, and the 
    //compare function will be who treat it as it is. 
    // BE CAREFULL with keys with longer sizes, the behaviour is not defined!!.
    char k[MAX_KEY_SIZE];
    //key_size
    size_t key_size;
    //Hash of the key.
    unsigned int h;
    //Offset of the next. (Must be in collisions)
    unsigned int next;
    //offset of the bucket where the entry is stored on.
    int bucket;
    //The size of the stored in the bucket. (This is to allow storing variable size
    //items, maximun, the size of the bucket). We only copy to the destiny, the
    //stored size, not all the bucket. [optimization]
    int bucket_stored_size;
    //Position where the entry is stored on. In the entries and in the colisions.
    int position;
    //Seconds from epoch. This is the creation time.
    //We use this value for deleting the older values, we use seconds, beacause
    //is an aproximate cleaning (designed for cache pourposes).
    long sec;
};

//Struct only with the flag of used / not.
struct bucket
{
    int used;
};



struct internal_hashtable
{
    unsigned int tablelength;
    unsigned int registry_max_size;
        char  * sem_name; 	
        sem_t * sem; 	
    unsigned int fd;
    unsigned int entrycount;
    unsigned int primeindex;
};


struct shmht
{
    //Those values are updated at creation time, so, they MUST be pointers.
    //Are process related values, so to each process return his pointers.
    void *internal_ht;
    void *entrypoint;
    void *collisionentries;
    void *bucketmarket;

    // Functions related to the data type stored.
    unsigned int (*hashfn) (void *k);
    int (*eqfn) (void *k1, void *k2);

};

/*****************************************************************************/
static unsigned int hash (struct shmht *h, void *k);

/*****************************************************************************/
/* indexFor */
static inline unsigned int
indexFor (unsigned int tablelength, unsigned int hashvalue)
{
    return (hashvalue % tablelength);
};


/*****************************************************************************/

#endif /* __HASHTABLE_PRIVATE_CWC22_H__ */

 include/shmht_sem.h

New file
@@ -0,0 +1,79 @@
/*
 * This is a R/W lock implementation using the SYS semaphores.
 * Based on http://www.experts-exchange.com/Programming/Languages/C/Q_23939132.html
 */


#ifndef __HASHTABLE_SEM__
#define __HASHTABLE_SEM__

#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>
#include <stdio.h>

#define SEM_READER 0
#define SEM_WRITER 1

struct sembuf read_start[] =
    { {SEM_READER, 1, SEM_UNDO}, {SEM_WRITER, 0, SEM_UNDO} };
struct sembuf read_end[] = { {SEM_READER, -1, SEM_UNDO} };

struct sembuf write_start1[] = { {SEM_WRITER, 1, SEM_UNDO} };
struct sembuf write_start2[] =
    { {SEM_READER, 0, SEM_UNDO}, {SEM_READER, 1, SEM_UNDO} };
struct sembuf write_fail_end[] = { {SEM_WRITER, -1, SEM_UNDO} };
struct sembuf write_end[] =
    { {SEM_READER, -1, SEM_UNDO}, {SEM_WRITER, -1, SEM_UNDO} };

#define SEMOP(semid,tbl,exc) { if(0>semop (semid, tbl, sizeof(tbl)/sizeof(struct sembuf) )){perror("semop: ");return exc;}}

//Necessary stuff for locking.
int
write_end_proc (int semid)
{
    SEMOP (semid, write_fail_end, 0);
    return -1;
}

#define READ_LOCK(semid) SEMOP(semid,read_start,-1)
#define READ_UNLOCK(semid) SEMOP(semid,read_end,-1)

#define WRITE_LOCK_READERS(semid) (SEMOP(semid,write_start1,-1))
#define WRITE_LOCK_TO_WRITE(semid) (SEMOP(semid,write_start2,write_end_proc(semid)))

//This macro returns a 0 different value if something goes wrong with the locking.
#define WRITE_LOCK(semid) (WRITE_LOCK_READERS(semid) && WRITE_LOCK_TO_WRITE(semid))

#define WRITE_UNLOCK(semid) SEMOP(semid,write_end, -1)

int
read_lock (int semid)
{
    READ_LOCK (semid);
    return 0;
}

int
read_unlock (int semid)
{
    READ_UNLOCK (semid);
    return 0;
}

int
write_lock (int semid)
{
    WRITE_LOCK_READERS (semid);
    WRITE_LOCK_TO_WRITE (semid);
    return 0;
}

int
write_unlock (int semid)
{
    WRITE_UNLOCK (semid);
    return 0;
}

#endif // __HASHTABLE_SEM__

 sample/CMakeLists.txt

@@ -7,6 +7,7 @@
add_executable(sample_create sample_create.c)
add_executable(sample_open sample_open.c)
add_executable(test_list_in_shm test_list_in_shm.c)
add_executable(shmht_mytests shmht_mytests.c)

target_link_libraries(sample_create
                  PRIVATE 
@@ -23,3 +24,9 @@
              pthread
             )

target_link_libraries(shmht_mytests
                  PRIVATE 
                  memfd
              pthread
             )


 sample/shmht_mytests.c

New file
@@ -0,0 +1,495 @@
//#include <cgreen/cgreen.h>
#include "shmht.h"
#include <string.h>
#include<stdlib.h>
#include <stdio.h>
#include <math.h>
#include <assert.h>

/*dbj2 hash function:*/
unsigned int
dbj2_hash (void *str_)
{
    unsigned long hash = 5381;
    char *str = (char *) str_;
    int c;

    while (0 != (c = *str++))
        hash = ((hash << 5) + hash) + c;    /* hash * 33 + c */

    return (unsigned int) hash;
}

/* comparison function: */
int
str_compar (void *c1, void *c2)
{
    char *c1_str = (char *) c1;
    return !bcmp (c1, c2, strlen (c1_str));
}


/*
 * \test-name check_create_from_NotExistentFile
 * \test-function test_check_create_from_NotExistentFile
 */
void
test_check_create_from_NotExistentFile ()
{
    size_t key_size = 100;
    struct shmht *h1 =
        create_shmht ("Not_Exists_file", 16, key_size, dbj2_hash, str_compar);
    assert(h1 == NULL);
}                                // test_check_create_from_NotExistentFile


/*
 * \test-name check_create_HTs
 * \test-function test_check_create_HTs
 */
void
test_check_create_HTs ()
{
    struct shmht *h1 = NULL;
    struct shmht *h2 = NULL;
    size_t key_size = 100;

    h1 = create_shmht ("run_tests", 16, key_size, dbj2_hash, str_compar);
    //assert_not_equal (h1, NULL);
    assert (h1 != NULL);
        
    h2 = create_shmht ("run_tests", 16, key_size, dbj2_hash, str_compar);
    //assert_not_equal (h2, NULL);
    assert (h2 != NULL);

    //Destroy the global shmht
    shmht_destroy (h1);
    shmht_destroy (h2);

    //Free the two references
    free (h1);
    free (h2);
}                                // test_check_create_HTs


/*
 * \test-name check_create_when_inserted
 * \test-function test_check_create_when_inserted
 */
void
test_check_create_when_inserted ()
{
    struct shmht *h1 = NULL;
    struct shmht *h2 = NULL;
    char *key = "Key_for_test_check_find";
    char *stored_value = "This is the stored Value!";
    size_t key_size = 100;

    h1 = create_shmht ("run_tests", 16, key_size, dbj2_hash, str_compar);
    assert(h1 != NULL);

    int shmht_insert_ret = shmht_insert (h1, key, strlen (key)
                                         , stored_value,
                                         strlen (stored_value) + 1);
    assert(shmht_insert_ret > 0);

    h2 = create_shmht ("run_tests", 16, key_size, dbj2_hash, str_compar);
    assert (h2 != NULL);

    //Check that after creation the existing entries are still there.
    assert(shmht_count (h2) == 0);
    assert(shmht_count (h1) == 1);

    //Destroy the global shmht
    shmht_destroy (h1);
    shmht_destroy (h2);

    //Free the two references
    free (h1);
    free (h2);

}                                // test_check_create_when_inserted

/*
 * \test-name check_find
 * \test-function test_check_find
 */
void
test_check_find ()
{
    struct shmht *h1 = NULL;
    struct shmht *h2 = NULL;
    struct shmht *h3 = NULL;
    struct shmht *h4 = NULL;
    char *key = "Key_for_test_check_find";
    char *stored_value = "This is the stored Value!";
    size_t key_size = 100;

    h1 = create_shmht ("run_tests", 16, key_size, dbj2_hash, str_compar);
    assert(h1 != NULL);

    h2 = create_shmht ("run_tests", 16, key_size, dbj2_hash, str_compar);
    assert(h2 != NULL);

    h3 = create_shmht ("run_tests", 16, key_size, dbj2_hash, str_compar);
    assert(h3 != NULL);

    h4 = create_shmht ("run_tests", 16, key_size, dbj2_hash, str_compar);
    assert(h4 != NULL);

    int shmht_insert_ret = shmht_insert (h1, key, strlen (key) , stored_value, strlen (stored_value) + 1);
    assert(shmht_insert_ret > 0);

    size_t ret_size;
    void *ret = shmht_search (h1, key, strlen (key), &ret_size);

    assert(ret != NULL);
    assert(strlen (stored_value) + 1 == ret_size);
    assert(!strncmp (ret, stored_value, strlen (stored_value) + 1));

    shmht_insert_ret = shmht_insert (h2, key, strlen (key), stored_value, strlen (stored_value) + 1);
    assert(shmht_insert_ret > 0);
    ret = shmht_search(h2, key, strlen (key), &ret_size);

    assert(ret !=  NULL);
    assert(strlen (stored_value) + 1 == ret_size);
    assert(!strncmp (ret, stored_value, strlen (stored_value)));

    shmht_insert_ret = shmht_insert (h3, key, strlen (key), stored_value, strlen (stored_value) + 1);
    assert(shmht_insert_ret > 0);
    ret = shmht_search(h3, key, strlen (key), &ret_size);

    assert(ret !=  NULL);
    assert(strlen (stored_value) + 1 == ret_size);
    assert(!strncmp (ret, stored_value, strlen (stored_value)));

    shmht_insert_ret = shmht_insert (h4, key, strlen (key), stored_value, strlen (stored_value) + 1);
    assert(shmht_insert_ret > 0);
    ret = shmht_search(h4, key, strlen (key), &ret_size);

    assert(ret !=  NULL);
    assert(strlen (stored_value) + 1 == ret_size);
    assert(!strncmp (ret, stored_value, strlen (stored_value)));

	
    //Destroy the global shmht
    shmht_destroy (h1);
    shmht_destroy (h2);
    shmht_destroy (h3);
    shmht_destroy (h4);

    //Free the two references
    free (h1);
    free (h2);
    free (h3);
    free (h4);

}                                // test_check_find

/*
 * \test-name check_count
 * \test-function test_check_count
 */
void
test_check_count ()
{
    char *key = "Key_for_test_check_count";
    char *stored_value = "This is the stored Value!";
    size_t key_size = 100;

    //Create a shmht.
    struct shmht *h =
        create_shmht ("run_tests", 16, key_size, dbj2_hash, str_compar);
    assert(h != NULL);


    //Insert a value into.
    int shmht_insert_ret = shmht_insert (h, key, strlen (key)
                                         , stored_value,
                                         strlen (stored_value) + 1);
    assert(shmht_insert_ret > 0);

    //Count
    assert(shmht_count (h) ==  1);

    //Destroy the global shmht
    shmht_destroy (h);

    assert(shmht_count (h) < 0);

    free (h);
}                                // test_check_count


/*
 * \test-name check_long_insertions
 * \test-function test_check_long_insertions
 */
void
test_check_long_insertions ()
{
    char *key = "Key_for_test_check_count";
    char *stored_value = "This is the stored Value!";
    size_t key_size = 100;
    int i;

    //Create a shmht.
    struct shmht *h =
        create_shmht ("run_tests", 16, key_size, dbj2_hash, str_compar);
    assert(h != NULL);


    //Insert a value until all is over.
    for (i = 0; i < 100; i++) {
        int shmht_insert_ret = shmht_insert (h, key, strlen (key)
                                             , stored_value,
                                             strlen (stored_value) + 1);
        if (shmht_insert_ret < 0) {
            //Insert until there is no more space.
            break;
        }
    }

    int shmht_insert_ret = shmht_insert (h, key, strlen (key)
                                         , stored_value,
                                         strlen (stored_value) + 1);
    assert(shmht_insert_ret < 0);

    //Destroy the global shmht
    shmht_destroy (h);

    assert(shmht_count (h) < 0);
    free (h);

}                                // test_check_long_insertions

/*
 * \test-name check_flush
 * \test-function test_check_flush
 */
void
test_check_flush ()
{
    char *key = "Key_for_test_check_count";
    char *stored_value = "This is the stored Value!";
    size_t key_size = 100;
    int i;

    //Create a shmht.
    struct shmht *h =
        create_shmht ("run_tests", 16, key_size, dbj2_hash, str_compar);
    assert(h != NULL);

    //Create a shmht.
    struct shmht *h2 =
        create_shmht ("run_tests", 16, key_size, dbj2_hash, str_compar);
    assert(h !=  NULL);


    //Insert a value until all is over.
    for (i = 0; i < 100; i++) {
        int shmht_insert_ret = shmht_insert (h, key, strlen (key)
                                             , stored_value,
                                             strlen (stored_value) + 1);
        if (shmht_insert_ret < 0) {
            //Insert until there is no more space.
            break;
        }
    }

    //Check that we flush all the entries.
    assert(shmht_flush (h2) == 0);
    assert(shmht_count (h) !=  0);
    assert(shmht_count (h2) == 0);

    //Destroy the global shmht
    shmht_destroy (h);
    shmht_destroy (h2);

    assert(shmht_count (h) < 0);
    assert(shmht_count (h2) < 0);

    free (h);
    free (h2);

}                                // test_check_flush

/*
 * \test-name check_remove_older_entries
 * \test-function test_check_remove_older_entries
 */
void
test_check_remove_older_entries ()
{
    char *key = "Key_for_test_check_count";
    char *stored_value = "This is the stored Value!";
    size_t key_size = 100;
    int i;

    //Create a shmht.
    struct shmht *h =
        create_shmht ("run_tests", 16, key_size, dbj2_hash, str_compar);
    assert(h !=  NULL);


    //Insert a value 10000 times erasing the older entries.
    for (i = 0; i < 10000; i++) {
        int shmht_insert_ret = shmht_insert (h, key, strlen (key)
                                             , stored_value,
                                             strlen (stored_value) + 1);
        if (shmht_insert_ret < 0) {
            //remove the 30% of the older entries.
            if (shmht_remove_older_entries (h, 30) == 0) {
                assert(1);
                break;
            }
        }
    }

    //Destroy the global shmht
    shmht_destroy (h);

    assert (shmht_count (h) < 0);
    free (h);

}                                // test_check_remove_older_entries


/*
 * \test-name check_number_of_removed_with_remove_older
 * \test-function test_check_number_of_removed_with_remove_older
 */
void
test_check_number_of_removed_with_remove_older ()
{
    char *key = "Key_for_test_remove_older";
    char *stored_value = "This is the stored Value!";
    size_t key_size = 100;
    int i;

    //Create a shmht.
    struct shmht *h =
        create_shmht ("run_tests", 16, key_size, dbj2_hash, str_compar);
    assert (h !=  NULL);

    //Insert a value until all is over.
    for (i = 0; i < 100; i++) {
        int shmht_insert_ret = shmht_insert (h, key, strlen (key)
                                             , stored_value,
                                             strlen (stored_value) + 1);
        if (shmht_insert_ret < 0) {
            //Insert until there is no more space.
            break;
        }
    }

    //Store the deletion of the 30% of the entries.
    int number_of_destroyed_30 = shmht_remove_older_entries (h, 30);

    //Fill the ht again:

    //Insert a value until all is over.
    for (i = 0; i < 100; i++) {
        int shmht_insert_ret = shmht_insert (h, key, strlen (key)
                                             , stored_value,
                                             strlen (stored_value) + 1);
        if (shmht_insert_ret < 0) {
            //Insert until there is no more space.
            break;
        }
    }
    //Get the number of destroyed entries with 50%
    int number_of_destroyed_50 = shmht_remove_older_entries (h, 50);
    //Check that with the 50% we destroy more than with the 30%
    assert(number_of_destroyed_50 > number_of_destroyed_30);

    //Destroy the global shmht
    shmht_destroy (h);

    assert(shmht_count (h) < 0);

    free (h);

}                                // test_check_flush

/*
 * \test-name check_create_huge_number_ht
 * \test-function test_check_create_huge_number_ht
 */
void
test_check_create_huge_number_ht ()
{
    size_t key_size = 100;
    char *key = "Key_for_huge_ht";
    char *stored_value = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
    int i;
       #define MAX 1000

    struct shmht **h = (struct shmht**)malloc(sizeof(struct shmht *) * MAX);
	
    //Create a shmht.
    for (i = 0; i < MAX; i++) {
        h[i] =
            create_shmht("run_tests", 16, key_size, dbj2_hash, str_compar);
        if (h[i] == NULL) {
            assert(1);
            break;
        }
    }

    assert(shmht_insert (h[0], key, strlen (key) , stored_value, strlen (stored_value) + 1) > 0);
    //assert(shmht_insert (h[10], key, strlen (key) , stored_value, strlen (stored_value) + 1) > 0);

    //assert(shmht_count (h[10]) == 1);
    assert(shmht_count (h[0]) == 1);


    int ret_size;
    void *ret = shmht_search(h[0], key, strlen (key), &ret_size);

    assert(ret !=  NULL);
    assert(strlen (stored_value) + 1 == ret_size);
    assert(!strncmp (ret, stored_value, strlen (stored_value)));
/*
    assert(strncmp 
                 ((char *)
                 shmht_search (h[10], key, strlen (key), (size_t *)&ret_size),
                 stored_value, strlen(stored_value)) == 0);*/


    //Destroy the global shmht
    for (i = 0; i < MAX; i++) {
            shmht_destroy (h[i]);
    }

//    assert(shmht_count (h[MAX/2]) == 0);
        

    for (i = 0; i < MAX; i++) {
        free (h[i]);
    }
    free(h);

}                                // test_check_create_huge_number_ht


int main (int argc, char * argv [])
{	
//TestSuite *suite = create_test_suite();

//    test_check_create_from_NotExistentFile();
        test_check_create_HTs();

        test_check_create_when_inserted();
    test_check_find();
    test_check_count();
    test_check_long_insertions();
    test_check_flush();
    test_check_remove_older_entries();
    test_check_number_of_removed_with_remove_older();
    test_check_create_huge_number_ht();
	
//return run_test_suite(suite, create_text_reporter());
    return 0;
}


 src/CMakeLists.txt

@@ -5,7 +5,7 @@
include_directories(../include)

# add library
add_library(memfd SHARED memfd.c list_in_shm.c)
add_library(memfd SHARED memfd.c list_in_shm.c shmht.c)
target_link_libraries(memfd PRIVATE pthread)



 src/Makefile

@@ -1,6 +1,21 @@
all:
    gcc -g -c -Wall -Werror -fpic list_in_shm.c  memfd.c -lpthread
CC=gcc
AR=ar
CFLAGS=-g -D __SHMT_DEBUG_MODE__=1 -Wall  -I${INCLUDE}  
INCLUDE=-I. -I ../include
all:shmht shmht_mytests
    gcc -g -c -Wall -Werror -I${INCLUDE} -fpic list_in_shm.c  memfd.c -lpthread
    gcc -shared -o liblistInShm.so list_in_shm.o memfd.o
    gcc test_list_in_shm.c liblistInShm.so -lpthread
#    gcc test_list_in_shm.c liblistInShm.so -lpthread
shmht: shmht.o memfd.o
    $(CC) -o libshmht.so $(CFLAGS) -shared $^
    $(AR) rcs libshmht.a  $^
shmht.o: shmht.c shmht.h
    $(CC) $(CFLAGS) $(INCLUDE) -fPIC -c shmht.c
shmht_mytests: shmht_mytests.o shmht.o memfd.o 
    $(CC) $(CFLAGS) $(INCLUDE)   -L .  -pthread  -o $@ $^ 
shmht_mytests.o: shmht.h
    $(CC) $(CFLAGS) $(INCLUDE) -fPIC -c shmht_mytests.c
memfd.o:
    $(CC) $(CFLAGS) $(INCLUDE) -fPIC -c memfd.c
clean:
    rm -rf *.so *.o a.out
    rm -rf *.so *.o a.out shmht_mytests *.a

 src/core

Binary files differ

 src/list_in_shm.h

File was deleted

 src/memfd.c

@@ -70,12 +70,16 @@
  struct stat st;

  /* Create an anonymous file in tmpfs; */
  if(0 >= len)
  {
      return -1;
  }

  fd = sys_memfd_create(name, MFD_CLOEXEC);

  if (fd == -1)
  {
    errExit("memfd_create");
      errExit("memfd_create");
  }

  /* Size the file as specified on the command line */
@@ -83,7 +87,7 @@
  mydebug("length: %zu\n", len);
  if (ftruncate(fd, len) == -1)
  {
      errExit("truncate");
      errExit("ftruncate");
  }

  if (fstat (fd, &st))
@@ -174,12 +178,12 @@
    }
    len = st.st_size;

    ret = munmap(*ppaddr, len);
    ret = munmap((void *)*ppaddr, len);
    if (ret == -1)
    {
        errExit("munmap()");
    }

    *ppaddr = NULL;
    mydebug("length: %zu, atime: %lu.%lu\n", len, st.st_atim.tv_sec, st.st_atim.tv_nsec);
    return len;
}

 src/memfd.h

File was deleted

 src/shmht.c

New file
@@ -0,0 +1,704 @@
#include "shmht.h"
//#include "shmht_sem.h"
#include "shmht_private.h"
#include "shmht_debug.h"
#include <limits.h>
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <sys/sem.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <sys/time.h>
#include <assert.h>
#include <errno.h>
#include <fcntl.h>           /* For O_* constants */
#include <sys/stat.h>        /* For mode constants */
#include <semaphore.h>
#include "memfd.h"

/*
Credit for primes table: Aaron Krowne
 http://br.endernet.org/~akrowne/
 http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
*/
static const unsigned int primes[] = {
    53, 97, 193, 389,
    769, 1543, 3079, 6151,
    12289, 24593, 49157, 98317,
    196613, 393241, 786433, 1572869,
    3145739, 6291469, 12582917, 25165843,
    50331653, 100663319, 201326611, 402653189,
    805306457, 1610612741
};

const unsigned int prime_table_length = sizeof (primes) / sizeof (primes[0]);
const float max_load_factor = 0.65;

/*Necessary union for the semaphore*/
union semun
{
    int val;                    /* value for SETVAL */
    struct semid_ds *buf;        /* buffer for IPC_STAT, IPC_SET */
    unsigned short *array;        /* array for GETALL, SETALL */
    struct seminfo *__buf;        /* buffer for IPC_INFO */
};


/****************************************************/
struct shmht *
create_shmht (char *name,
              unsigned int number,
              size_t register_size,
              unsigned int (*hashf) (void *), int (*eqf) (void *, void *))
{

    unsigned char *primary_pointer;
    struct shmht *h;
    int created = 0;
    unsigned int pindex, size = primes[0];
    //Stuff for the semaphore.
    //union semun arg;
    //arg.val = 0;

    /* Check requested hashtable isn't too large */
    if (number > (1u << 30))
        return NULL;
    /* Enforce size as prime */

    for (pindex = 0; pindex < prime_table_length; pindex++) {
        if (primes[pindex] > number) {
            size = primes[pindex];
            break;
        }
    }


    /*Calcule the necessary size for the hash table */
    //hashtable structure + 2* entry size + buckets.
    int all_ht_size =
        sizeof (struct internal_hashtable) +
        2 * sizeof (struct entry) * size + (sizeof (struct bucket) +
                                            register_size) * size;

    shmht_debug(("create_shmht size=%d, register_size:%u, all_ht_size=%d\n", size,  register_size, all_ht_size));
    int fd = basic_shm_create(name, all_ht_size);
    if ( 0 >= fd )
    {
       printf("\nbasic_shm_create failed errono %u\n",errno);
       return NULL;
    }
    else
    {
        created = 1;
    }
     
    shmht_debug (("create_shmht: The shmem fd is: %d\n The size is %d \n",
                  fd, all_ht_size));

    char fd_str[16] = {0};
    int sem_len = strlen(name) + sizeof(fd_str);
    char * sem_name = (char *)malloc(sem_len+1);
    memset(sem_name, 0 , sem_len);
    snprintf(sem_name, sem_len, "%s%d", name, fd);
    /* Change umask temporarily to make sure the correct permission */
    mode_t mask = umask(0);
    sem_t * sem  = sem_open(sem_name, O_CREAT | O_RDWR, 0666, 1);
    umask(mask);
    if (NULL  == sem )
    {
       basic_shm_close(fd);
       printf("\nsem_open failed for name %s  %u\n", name, errno);
       return NULL ;
    }

    int len = basic_shm_mmap(fd, &primary_pointer);
    if(0 >= len || (void *) -1 == primary_pointer)
    {
       printf("\nbasic_shm_open failed  %u\n",errno);
       basic_shm_close(fd);
       sem_close(sem);
       return  NULL;
    }

    h = (struct shmht *) malloc (sizeof (struct shmht));

    if (created) {
        shmht_debug(("create_shmht: As created, clean all the shm!\n"));
        bzero (primary_pointer, all_ht_size);
    }

    //Check if the shmat has worked.
    if (h == NULL)
        return h;

    //The created structure:
    //------------------------------------------------------------
    //| internal_hashtable | entries | colision entries | buckets |
    //------------------------------------------------------------
    //Entries point, use the void* to do the pointer arithmetic:
    h->internal_ht = (void *)primary_pointer;
    h->entrypoint = h->internal_ht + sizeof (struct internal_hashtable);
    //Collision entries:
    h->collisionentries = h->entrypoint + sizeof (struct entry) * size;
    //Bucket entries:
    h->bucketmarket = h->entrypoint + 2 * sizeof (struct entry) * size;


    //Store the necessary values:
    struct internal_hashtable *iht = (struct internal_hashtable *)h->internal_ht;

    if (created) {
            iht->sem_name = sem_name;
        iht->sem  = sem;
        iht->fd = fd;
    }

    //The register_size
    if (!created)
        assert
            ("Logical Error: initiated with different length the hash table"
             || iht->registry_max_size != register_size);

    iht->registry_max_size = register_size;
    //The number of registers
    if (!created)
        assert
            ("Logical Error: initiated with different length the hash table"
             || iht->tablelength != size);
    iht->tablelength = size;
    //Index in the prime array.
    iht->primeindex = pindex;
    //Number of entries.
    if (created)
        iht->entrycount = 0;
    //Its possible to update in runtime the hash functions of the HT.
    //hash function.
    h->hashfn = hashf;
    //equal funcion.
    h->eqfn = eqf;
    return h;
}                                //create_shmht

/*****************************************************************************/
static unsigned int
hash (struct shmht *h, void *k)
{
    /* Aim to protect against poor hash functions by adding logic here
     * - logic taken from java 1.4 hashtable source */
    unsigned int i = h->hashfn (k);
    i += ~(i << 9);
    i ^= ((i >> 14) | (i << 18));    /* >>> */
    i += (i << 4);
    i ^= ((i >> 10) | (i << 22));    /* >>> */
    return i;
}


/*****************************************************************************/
int
shmht_count (struct shmht *h)
{
    int value = -1;
    struct internal_hashtable *iht = (struct internal_hashtable *)h->internal_ht;
    if(NULL == iht)
    {
        return -1;
    }
    sem_wait(iht->sem);
    value = iht->entrycount;
        sem_post(iht->sem);	
    return value;
}                                // hashtable_count


/****************************************************************************/

//This function looks for free colision entries in the hash table.
static int
locate_free_colision_entry (struct shmht *h)
{
    int i;
    struct internal_hashtable *iht = (struct internal_hashtable *)h->internal_ht;
    for (i = 0; i < iht->tablelength; i++) {
        struct entry *aux = h->collisionentries + (i * sizeof (struct entry));
        if (!aux->used)
            return i;
    }
    return -1;
}                                // locate_free_colision_entry


/*****************************************************************************/

//This function looks for free buckets in the shm.
static int
locate_free_bucket (struct shmht *h)
{
    int i;
    struct internal_hashtable *iht = (struct internal_hashtable *)h->internal_ht;
    for (i = 0; i < iht->tablelength; i++) {
        struct bucket *aux =
            h->bucketmarket +
            (i * (sizeof (struct bucket) + iht->registry_max_size));
        if (!aux->used)
            return i;
    }
    return -1;
}                                // locate_free_bucket

/*****************************************************************************/
int
shmht_insert (struct shmht *h, void *k, size_t key_size,
                  void *v, size_t value_size)
{

    //first acquire the lock.
    //If it fails return -ECANCELED.
    struct internal_hashtable *iht = (struct internal_hashtable *)h->internal_ht;

    sem_wait(iht->sem);

    int index = -1;
    unsigned int key_hash;
    struct timeval tv;

    if (value_size > iht->registry_max_size) {
        sem_post(iht->sem);
        return -EINVAL;
    }

    if (key_size > MAX_KEY_SIZE) {
        sem_post(iht->sem);
        return -EINVAL;
    }

    //Test if we have reached the max size of the HT. This is FIXED.
    if (iht->tablelength <= iht->entrycount) {
        sem_post(iht->sem);
        return -1;
    }

    //By default if there is size, should be free buckets, but check is almost free.
    index = locate_free_bucket (h);
    if (index < 0) {
        sem_post(iht->sem);
        return -1;
    }

    //Get the seconds from epoch:
    gettimeofday (&tv, NULL);

    //Set to used.
    struct bucket *bucket_ptr =
        h->bucketmarket +
        (index * (sizeof (struct bucket) + iht->registry_max_size));
    bucket_ptr->used = 1;
    //Copy the value in the bucket.
    memcpy (h->bucketmarket +
            (index * (sizeof (struct bucket) + iht->registry_max_size)) +
            sizeof (struct bucket)
            , v, value_size);
    shmht_debug (("shmht_insert: Located free bucket in %d\n", index));
    key_hash = hash (h, k);
    int entryIndex = indexFor (iht->tablelength, key_hash);
    shmht_debug (("shmht_insert: Generated Entry Index: %d \n",
                  entryIndex));
    struct entry *index_Entry =
        h->entrypoint + (entryIndex * sizeof (struct entry));

    if (!index_Entry->used) {
        //!Colision
        index_Entry->used = 1;

        memcpy (index_Entry->k, k, key_size);
        index_Entry->key_size = key_size;
        index_Entry->h = key_hash;
        index_Entry->next = -1;
        index_Entry->bucket = index;
        index_Entry->position = entryIndex;
        index_Entry->bucket_stored_size = value_size;
        index_Entry->sec = tv.tv_sec;

    }
    else {
        //Colision
        shmht_debug (("shmht_insert: Collision in the entry %d \n",
                      entryIndex));
        int colision_index = locate_free_colision_entry (h);

        //Paranoid check.
        assert (colision_index == -1
                || "Logical Error: Not free colision entries");
        shmht_debug (("shmht_insert: Located free colision entry : %d\n",
                      colision_index));
        struct entry *colision_Entry =
            h->collisionentries + (colision_index * sizeof (struct entry));
        //Paranoid check.
        assert (colision_Entry->used
                ||
                "Logical Error: locate_free_colision_entry returns a used entry!");
        colision_Entry->used = 1;
        memcpy (colision_Entry->k, k, key_size);
        colision_Entry->key_size = key_size;
        colision_Entry->h = key_hash;
        colision_Entry->next = -1;
        colision_Entry->position = colision_index;
        colision_Entry->bucket = index;
        colision_Entry->bucket_stored_size = value_size;
        colision_Entry->sec = tv.tv_sec;
        //Look for the previous one.
        if (index_Entry->next == -1) {
            //There are not more colisions.
            index_Entry->next = colision_index;
            colision_Entry->next = -1;
        }
        else {
            //Look for the previous!
            struct entry *aux = index_Entry;
            while (aux->next != -1)
                aux =
                    h->collisionentries + (aux->next * sizeof (struct entry));
            //Set all the stuff of entries:
            aux->next = colision_index;
            colision_Entry->next = -1;
        }
    }
    // Add 1 to the entrycount.
    iht->entrycount++;
    //unlock the write sem.
    sem_post(iht->sem);

    return 1;
}                                // shmht_insert

/*****************************************************************************/
//Compare two keys :D
//Return 0 if equal, 1 if not.

static int
compareBinaryKeys (size_t sk1, void *k1, size_t sk2, void *k2)
{
    //First compare key sizes:
    if (sk1 != sk2)
        return 1;

    return bcmp (k1, k2, sk1);
}                                // compareBinaryKeys

/*****************************************************************************/
void *                            /* returns the fist value associated with key */
shmht_search (struct shmht *h, void *k, size_t key_size,
                  size_t * returned_size)
{
    struct internal_hashtable *iht = (struct internal_hashtable *)h->internal_ht;
    sem_wait(iht->sem);
    void *retValue = NULL;
    struct entry *index_Entry;
    unsigned int hashvalue, index;

    //Calcule the hash
    hashvalue = hash (h, k);
    //Look for the index in the hashtable.
    index = indexFor (iht->tablelength, hashvalue);
    shmht_debug (("shmht_search: Index for this key: %d", index));
    //Calcule the offset:
    index_Entry = h->entrypoint + (index * sizeof (struct entry));
    while (index_Entry != NULL && index_Entry->used) {
        /* Check hash value to short circuit heavier comparison */
        if (hashvalue == index_Entry->h
            &&
            !compareBinaryKeys (index_Entry->key_size,
                                (void *) index_Entry->k, key_size, k)) {
            shmht_debug (("shmht_search: finded shmht_search!\n"));
            //Look for the bucket. 
            //Calcule it as: buckets offset + number * sizeof(complete bucket) 
            //+ sizeof(bucket structure)
            retValue = h->bucketmarket +
                (index_Entry->bucket *
                 (sizeof (struct bucket) + iht->registry_max_size))
                + sizeof (struct bucket);
            (*returned_size) = index_Entry->bucket_stored_size;

            //Paranoid check ;)
            struct bucket *target_bucket = h->bucketmarket +
                (index_Entry->bucket *
                 (sizeof (struct bucket) + iht->registry_max_size));
            assert (target_bucket->used == 1
                    || "Logical Error: found an entry with Empty bucket");

            break;
        }

        //If there is not in the entries... look in colisions :D
        index_Entry = (index_Entry->next != -1) ?
            h->collisionentries + (index_Entry->next * sizeof (struct entry))
            : NULL;
    }
    sem_post(iht->sem);	

    return retValue;
}                                // shmht_search

/*****************************************************************************/


/*
  Since hashtable_remove can be called from a locked context, I've extracted the logic
  into an internal function, and left only the lock/unlock logic in the hastable_remove
  function.
  To call from a locked context, call __shmht_remove__ instead hashtable_remove
 */
static int
__shmht_remove__ (struct shmht *h, void *k, size_t key_size)
{
    struct internal_hashtable *iht = (struct internal_hashtable *)h->internal_ht;
    struct entry *index_Entry = NULL;
    struct entry *previous_Entry = NULL;    // previous Entry
    int retValue = 0;
    unsigned int hashvalue, index;

    hashvalue = hash (h, k);
    index = indexFor (iht->tablelength, hash (h, k));

    shmht_debug (("__shmht_remove__: Index for this key: %d\n", index));
    //Calcule the offset:
    index_Entry = h->entrypoint + (index * sizeof (struct entry));
    while (index_Entry != NULL && index_Entry->used) {
        /* Check hash value to short circuit heavier comparison */
        if (hashvalue == index_Entry->h
            &&
            !compareBinaryKeys (index_Entry->key_size,
                                (void *) index_Entry->k, key_size, k)) {
            shmht_debug (("__shmht_remove__: finded hashtable_remove!\n"));
            break;
        }

        //If there is not in the entries... look in colisions :D
        previous_Entry = index_Entry;
        index_Entry = (index_Entry->next != -1) ?
            h->collisionentries + (index_Entry->next * sizeof (struct entry))
            : NULL;
    }

    //If the key has been found:
    if (index_Entry != NULL && index_Entry->used) {
        //First, mark the bucket as not used.
        struct bucket *target_bucket = h->bucketmarket +
            (index_Entry->bucket *
             (sizeof (struct bucket) + iht->registry_max_size));
        target_bucket->used = 0;
        //+1 to the retValue (by default 0)
        retValue += 1;
        //Decrease the hash table entry count.
        iht->entrycount -= 1;
        if (!previous_Entry) {
            //The found instance is NOT stored in Colision.
            //So, we must copy to Entries the first of Colision.
            if (index_Entry->next != -1) {
                //Found the copy
                struct entry *next_Entry =
                    h->collisionentries +
                    (index_Entry->next * sizeof (struct entry));
                //Direct copy of the context of the next entry into entries.
                int aux_position = index_Entry->position;
                (*index_Entry) = (*next_Entry);
                //Delete the "used" from the entry
                next_Entry->used = 0;
                //Set the correct position
                index_Entry->position = aux_position;
            }
            else                //There is not colision.
                index_Entry->used = 0;
        }
        else {
            //The found instance is stored in Colision:
            previous_Entry->next = index_Entry->next;
            //Mark the entry as not used.
            index_Entry->used = 0;
        }
    }
    // Now we're in a consistent state.

    return retValue;
}                                // __shmht_remove__


/****************************************************************************/
int
shmht_remove (struct shmht *h, void *k, size_t key_size)
{
    struct internal_hashtable *iht = (struct internal_hashtable *)h->internal_ht;
    sem_wait(iht->sem);		
    int retValue = __shmht_remove__ (h, k, key_size);
    sem_post(iht->sem);	
    return retValue;
}                                // hashtable_remove

/*****************************************************************************/

int
shmht_flush (struct shmht *h)
{

    struct internal_hashtable *iht = (struct internal_hashtable *)h->internal_ht;
    sem_wait(iht->sem);		
    int i;
    //First, clear all the buckets:
    for (i = 0; i < iht->tablelength; i++) {
        struct bucket *target_bucket = h->bucketmarket +
            (i * (sizeof (struct bucket) + iht->registry_max_size));
        target_bucket->used = 0;
    }

    struct entry *target_entry;
    //Second, clear all the entries:
    for (i = 0; i < iht->tablelength; i++) {
        target_entry = h->entrypoint + (i * sizeof (struct entry));
        target_entry->used = 0;
    }

    //Last, clear all the colisions.
    for (i = 0; i < iht->tablelength; i++) {
        target_entry = h->collisionentries + (i * sizeof (struct entry));
        target_entry->used = 0;
    }
    iht->entrycount = 0;
    sem_post(iht->sem);	
    return 0;

}                                // shmht_flush

/****************************************************************************/

int
shmht_remove_older_entries (struct shmht *h, int p)
{
    //Define a local aux structure ;D
    struct finder_aux_struct
    {
        long sec;
        int is_in_col;
        int index;
    };
    //Define a local function.
    void insert_older_if_necessary (struct entry *e,
                                    struct finder_aux_struct *into,
                                    unsigned int size_of_into, int is_in_col)
    {

        int i;
        //Var that points to the place to replace.
        struct finder_aux_struct *aux = NULL;
        for (i = 0; i < size_of_into; i++){
          //x          printf ("Comparison => entry: %ld, struct: %ld \n", e->sec, into[i].sec);
            if (e->sec < into[i].sec) {
                //If it's -1, it's not initiated, stop.
                aux = &into[i];
                break;
            }
        }

        if (aux != NULL) {
            //In aux, we have the element to replace.
            shmht_debug (("insert_older_if_necessary: Inserted Entry : secs %ld, is_in_col: %d, position: %d \n"
                          , e->sec, is_in_col, e->position));
            aux->sec = e->sec;
            aux->is_in_col = is_in_col;
            aux->index = e->position;
        }
    }                            // insert_older_if_necessary



    //Check before lock:
    if (p > 100)
        return -EINVAL;

    struct internal_hashtable *iht = (struct internal_hashtable *)h->internal_ht;

    sem_wait(iht->sem);		

    //Start the stuff
    int retValue = 0;
    //Calcule the number of entries to delete:
    int deleteEntries = iht->tablelength * p / 100;

    shmht_debug (("shmht_remove_older_entries: Number of entries to Delete: %d\n", deleteEntries));

    struct finder_aux_struct older_storage[deleteEntries];

    int i;
    //Init the struct:
    for (i = 0; i < deleteEntries; i++) {
        older_storage[i].sec = LONG_MAX;
        older_storage[i].is_in_col = -1;
        older_storage[i].index = -1;
    }

    //Go around the structs:
    //Mantain ordered the structure.
    struct entry *target_entry;
    //Second, clear all the entries:
    for (i = 0; i < iht->tablelength; i++) {
        target_entry = h->entrypoint + (i * sizeof (struct entry));
        if (target_entry->used)
            insert_older_if_necessary (target_entry, older_storage,
                                       deleteEntries, 0);
    }

    //Last, clear all the colisions.
    for (i = 0; i < iht->tablelength; i++) {
        target_entry = h->collisionentries + (i * sizeof (struct entry));
        if (target_entry->used)
            insert_older_if_necessary (target_entry, older_storage,
                                       deleteEntries, 1);
    }


    //Now, delete the entries stored in older_storage:
    for (i = 0; i < deleteEntries; i++) {
        if (older_storage[i].index != LONG_MAX) {
            if (!older_storage[i].is_in_col)
                target_entry =
                    h->entrypoint +
                    (older_storage[i].index * sizeof (struct entry));
            else
                target_entry =
                    h->collisionentries +
                    (older_storage[i].index * sizeof (struct entry));
            __shmht_remove__ (h, target_entry->k, target_entry->key_size);
            retValue++;
        }
        else
            break;
    }                            //for

    sem_post(iht->sem);	
    return retValue;
}                                // shmht_remove_older_entries


/****************************************************************************/

/* destroy, it destroys all the shared memory and the semaphores :P*/
int
shmht_destroy (struct shmht *h)
{
    struct internal_hashtable *iht = (struct internal_hashtable *)(h->internal_ht);
    //Wait untill there are not more processess.
    //Delete the shared memory.
     sem_wait(iht->sem);
     sem_post(iht->sem);

     int fd = iht->fd;
     sem_close(iht->sem);
     sem_unlink(iht->sem_name);
     free(iht->sem_name);
     basic_shm_unmmap(fd, (unsigned char **)&iht);
     basic_shm_close(fd);
     h->internal_ht = NULL;
     return 0;
}                                // shmht_destroy