Skip to content

Instantly share code, notes, and snippets.

@yodamaster

yodamaster/lockfree_hashtable.c

Forked from larytet/lockfree_hashtable.c
Created September 13, 2023 14:58
Show Gist options
  • Save yodamaster/37cd2e09b68cd3e38da4823d5bf2a1ed to your computer and use it in GitHub Desktop.
Save yodamaster/37cd2e09b68cd3e38da4823d5bf2a1ed to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. @larytet larytet revised this gist Jul 13, 2017. 1 changed file with 0 additions and 172 deletions.
    172 changes: 0 additions & 172 deletions lockfree_hashtable.c
    View file
    Original file line number Diff line number Diff line change
    @@ -385,177 +385,5 @@ static void hashtable_close(hashtable_t *hashtable)
    } \


    #include <stdio.h>
    #include <stdint.h>
    #include <stdlib.h>
    #include "hashtable.h"
    #include "linux_utils.h"


    #define HASHTABLE_BITS 8


    static hashtable_t hashtable = {"hash", HASHTABLE_BITS, hash_none};

    DECLARE_HASHTABLE(uint32, uint32_t, 4, 0, 0);

    /**
    * The hashtable does 'value & ((1 << HASHTABLE_BITS)-1)'
    * The function generates values which will cause collision
    * in the table slot 0, the values are unique
    */
    static inline uint32_t get_value_collision(int idx)
    {
    return ((1 << HASHTABLE_BITS) << idx);
    }

    static inline uint32_t get_value(int idx)
    {
    return idx;
    }

    static int thread_job(void *thread_arg)
    {
    int idx = (int)(size_t)thread_arg;

    uint32_t value_to_store = get_value(idx);


    while (1)
    {
    int rc = hashtable_uint32_insert(&hashtable, value_to_store, 0);
    if (!rc)
    {
    linux_log(LINUX_LOG_ERROR, "Thread %d failed to insert entry %u",
    idx, value_to_store);
    return 1;
    }
    rc = hashtable_uint32_remove(&hashtable, value_to_store, NULL);
    if (!rc)
    {
    linux_log(LINUX_LOG_ERROR, "Thread %d failed to remove entry %u",
    idx, value_to_store);
    return 1;
    }
    }


    return 1;
    }

    static int create_threads(int cpus)
    {
    int rc;
    for (int i = 0;i < cpus;i++)
    {
    linux_task_state_t *state = (linux_task_state_t*)calloc(1, sizeof(linux_task_state_t));
    char filename[64];
    sprintf(filename, "%d", i);
    state->properties.name = strdup(filename);
    state->properties.task = thread_job;
    state->properties.task_arg = (void*)(size_t)i;
    rc = linux_thread_start(state);
    if (!rc)
    {
    break;
    }

    }
    return rc;
    }

    static int synchronous_access(int cpus)
    {
    for (int i = 0;i < cpus;i++)
    {
    uint32_t value_to_store = get_value(i);
    int rc = hashtable_uint32_insert(&hashtable, value_to_store, 0);
    if (!rc)
    {
    linux_log(LINUX_LOG_ERROR, "Thread %d failed to insert entry %u",
    i, value_to_store);
    return 0;
    }
    }
    for (int i = 0;i < cpus;i++)
    {
    uint32_t value_to_store = get_value(i);
    int rc = hashtable_uint32_remove(&hashtable, value_to_store, NULL);
    if (!rc)
    {
    linux_log(LINUX_LOG_ERROR, "Thread %d failed to remove entry %u",
    i, value_to_store);
    return 0;
    }
    }
    return 1;
    }

    int main()
    {
    int cpus = 4; //linux_get_number_processors()
    int rc;

    do
    {

    rc = hashtable_uint32_init(&hashtable);
    if (!rc)
    {
    break;
    }

    rc = synchronous_access(cpus);
    if (!rc)
    {
    break;
    }

    rc = create_threads(cpus);
    if (!rc)
    {
    break;
    }

    while (1)
    {
    linux_ms_sleep(1000);
    char buf[4*1024];
    hashtable_show(buf, ARRAY_SIZE(buf));
    linux_log(LINUX_LOG_INFO, "%s", buf);
    }
    hashtable_close(&hashtable);
    }
    while (0);

    return 0;
    }
    =========== Makefile ============


    TARGET = hashtable_test
    CXXFLAGS = -O2 -g -Wall -fmessage-length=0 -std=c++11
    CXX = $(CROSS)g++ $(INCLUDE_DIRS)
    LIBS = -lpthread -lrt


    APP_OBJS = ./hashtable_test.o \
    ./linux_utils.o \

    APP_DEPS = ./hashtable_test.cpp \
    ./linux_utils.cpp \
    ./linux_utils.h \
    ./Makefile \
    ./hashtable.h \



    $(TARGET):: $(APP_DEPS) $(APP_OBJS)
    $(CXX) $(CXXFLAGS) -o $(TARGET) -pthread $(APP_OBJS) $(LIBS)

    all: $(TARGET)

    clean:
    $(Q)rm -f $(APP_OBJS) $(TARGET)


  2. @larytet larytet revised this gist Jul 13, 2017. 2 changed files with 561 additions and 303 deletions.
    303 changes: 0 additions & 303 deletions kernel_hashtable.c
    View file
    Original file line number Diff line number Diff line change
    @@ -1,303 +0,0 @@
    /**
    * Lockfree is a set of lockfree containers for Linux and Linux kernel
    * Copyright (C) <2017> Arkady Miasnikov
    *
    * This program is free software: you can redistribute it and/or modify
    * it under the terms of the GNU General Public License as published by
    * the Free Software Foundation, either version 3 of the License, or
    * (at your option) any later version.
    *
    * This program is distributed in the hope that it will be useful,
    * but WITHOUT ANY WARRANTY; without even the implied warranty of
    * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
    * GNU General Public License for more details.
    *
    * You should have received a copy of the GNU General Public License
    * along with this program. If not, see <http://www.gnu.org/licenses/>.
    */


    /**
    * Implementation of lockfree linear probing hashtable
    * The hashtable targets SystemTap environment where a typical key is thread ID
    * The number of probes is limited by a constant. The index is not wrapping around,
    * but instead the hashtable allocates enough memory to handle linear probing in the end
    * of the table
    *
    * Limitation: a specific entry (a specific key) can be inserted and deleted by one thread.
    *
    * Performance: a core can make above 13M add&remove operations per second, cost of a
    * single operation is under 20nano which is an equivalent of 50-100 opcodes.
    */

    #pragma once


    #if KERNEL
    # inclide "linux/vmalloc.h"
    # include "linux/printk.h"
    # define DEV_NAME "lockless"
    # define PRINTF(s, ...) printk(KERN_ALERT DEV_NAME ": %s: " s "\n", __func__, __VA_ARGS__)
    #else
    # include <stdlib.h>
    # include <stdio.h>
    # define PRINTF(s, ...) printf("%s: " s "\n", __func__, __VA_ARGS__)
    # define likely(x) __builtin_expect(!!(x), 1) // !!(x) will return 1 for any x != 0
    # define unlikely(x) __builtin_expect(!!(x), 0)
    #endif

    #define __sync_access(x) (*(volatile __typeof__(*x) *) (x))

    /**
    * My key is a thread ID (22 bits) and my data is a chunk in the
    * FIFO orgtanised in the driver shared memory
    * Th field age is a timestamp in ms when the slot
    * is populated.
    */
    typedef struct
    {
    volatile uint32_t key;
    uint32_t age;
    void *data;
    } hashtable_slot_t;

    typedef struct
    {
    size_t size;
    uint64_t insert;
    uint64_t remove;
    uint64_t collision;
    uint64_t insert_err;
    uint64_t remove_err;
    } hashtable_stat_t;

    typedef struct
    {
    const char *name;
    size_t bits;

    // Probably not necessary, because I am going to use a trivial one to one hash function
    uint32_t (*hashfunction)(uint32_t);

    size_t __size;
    size_t __memory_size;
    hashtable_slot_t *__table;
    hashtable_stat_t __stat;
    } hashtable_t;


    /**
    * Calculate number of slots in the hash table
    * I add max_tries on top to ensure that there are max_tries slots after the
    * end of the table
    */
    static size_t hashtable_memory_size(const int bits, size_t max_tries)
    {
    size_t slots = (1 << bits) + max_tries;
    return (sizeof(hashtable_slot_t) * slots);
    }

    static const size_t HASHTABLE_MAX_TRIES = 8;
    // Illegal TID can be (PID_MAX_LIMIT+1)
    static const uint32_t ILLEGAL_KEY = 0;

    /**
    * Based on https://gist.github.com/badboy/6267743
    * http://burtleburtle.net/bob/hash/integer.html
    * I replace the 'long key' by 'unsigned key' and unsigned Java right shifts
    * by regular C/C++ right shifts
    * I adopt the hash function for 22 (PID_MAX_LIMIT) bits integers
    */
    static uint32_t hash32shift(uint32_t key)
    {

    key = ~key + (key << 10); // key = (key << 15) - key - 1;
    key = key ^ (key >> 7);
    key = key + (key << 1);
    key = key ^ (key >> 2);
    key = key * 187; // key = (key + (key << 3)) + (key << 11);
    key = key ^ (key >> 11);
    return key;
    }

    static uint32_t hash_none(uint32_t key)
    {
    return key;
    }

    static void hashtable_init_slot(hashtable_slot_t *slot)
    {
    slot->key = ILLEGAL_KEY;
    slot->data = NULL;
    slot->age = 0;
    }

    static int hashtable_init(hashtable_t *hashtable)
    {
    size_t memory_size = hashtable_memory_size(hashtable->bits, HASHTABLE_MAX_TRIES);
    #ifdef KERNEL
    void *p = vmalloc(memory_size);
    #else
    void *p = malloc(memory_size);
    #endif
    size_t i;
    if (p)
    {
    if (hashtable->hashfunction == NULL)
    {
    hashtable->hashfunction = hash32shift;
    }
    hashtable->__size = (1 << hashtable->bits);
    hashtable->__memory_size = memory_size;
    hashtable->__table = (hashtable_slot_t*)p;
    for (i = 0;i < hashtable->__size;i++)
    {
    hashtable_init_slot(&hashtable->__table[i]);
    }
    return 1;
    }
    PRINTF("Failed to allocate %u for the hashtable %s", (unsigned)memory_size, hashtable->name);
    return 0;
    }

    static int hashtable_init_all(hashtable_t *hashtable)
    {
    int res = 0;

    for (;hashtable->name && hashtable->bits;hashtable++)
    {
    res = hashtable_init(hashtable);
    if (!res)
    break;
    }

    return res;
    }


    static void hashtable_close(hashtable_t *hashtable)
    {
    if (hashtable->__table)
    {
    #ifdef KERNEL
    vfree(hashtable->__table);
    #else
    free(hashtable->__table);
    #endif
    }
    else
    {
    PRINTF("Failed to free null pointer for the hashtable %s", hashtable->name);
    }
    }

    static void hashtable_close_all(hashtable_t *hashtable)
    {
    for (;hashtable->name && hashtable->bits;hashtable++)
    {
    hashtable_close(hashtable);
    }
    }

    static inline size_t hashtable_get_index(const hashtable_t *hashtable, const uint32_t hash)
    {
    return hash & (hashtable->__size - 1);
    }

    /**
    * Hash the key, get an index in the hashtable, try compare-and-set.
    * If fails (not likely) try again with the next slot (linear probing)
    * continue until success or max_tries is hit
    */
    static int hashtable_insert(hashtable_t *hashtable, const uint32_t key, void * const data)
    {
    const uint32_t hash = hashtable->hashfunction(key);
    const uint32_t index = hashtable_get_index(hashtable, hash);
    const uint32_t index_max = index+HASHTABLE_MAX_TRIES; // I can do this for the last slot too - I allocated max_tries more slots
    uint32_t i;
    hashtable->__stat.insert++;
    for (i = index;i < index_max;i++)
    {
    hashtable_slot_t *slot = &hashtable->__table[i];
    #if KERNEL
    uint32_t old_key = cmpxchg(&slot->key, ILLEGAL_KEY, key);
    #else
    uint32_t old_key = __sync_val_compare_and_swap(&slot->key, ILLEGAL_KEY, key);
    #endif
    if (likely(old_key == ILLEGAL_KEY)) // Success
    {
    slot->data = data;
    return 1;
    }
    else
    {
    hashtable->__stat.collision++;
    }
    }

    hashtable->__stat.insert_err++;
    return 0;
    }

    /**
    * Hash the key, get an index in the hashtable, find the relevant entry,
    * read the pointer, remove using atomic operation
    * Only one context is allowed to remove a specific entry
    */
    static int hashtable_remove(hashtable_t *hashtable, const uint32_t key, void **data)
    {
    const uint32_t hash = hashtable->hashfunction(key);
    const uint32_t index = hashtable_get_index(hashtable, hash);
    const uint32_t index_max = index+HASHTABLE_MAX_TRIES; // I can do this for the last slot too - I allocated max_tries more slots
    uint32_t i;
    hashtable->__stat.remove++;
    for (i = index;i < index_max;i++)
    {
    hashtable_slot_t *slot = &hashtable->__table[i];
    uint32_t old_key = slot->key;
    if (likely(old_key == key))
    {
    if (data)
    {
    *data = slot->data;
    }
    __sync_access(&slot->data) = NULL;
    #if 0 // I hope that I do not need a barrier here
    #ifdef KERNEL
    barrier();
    #else
    __sync_synchronize();
    #endif
    #endif
    __sync_access(&slot->key) = ILLEGAL_KEY;
    return 1;
    }
    }

    hashtable->__stat.remove_err++;
    return 0;
    }

    /**
    * Hash the key, get an index in the hashtable, find the relevant entry,
    * read the pointer
    */
    static int hashtable_find(const hashtable_t *hashtable, const uint32_t key, void **data)
    {
    const uint32_t hash = hashtable->hashfunction(key);
    const uint32_t index = hashtable_get_index(hashtable, hash);
    const uint32_t index_max = index+HASHTABLE_MAX_TRIES; // I can do this for the last slot too - I allocated max_tries more slots
    uint32_t i;
    for (i = index;i < index_max;i++)
    {
    hashtable_slot_t *slot = &hashtable->__table[i];
    uint32_t old_key = slot->key;
    if (old_key == key)
    {
    *data = slot->data;
    return 1;
    }
    }

    return 0;
    }
    561 changes: 561 additions & 0 deletions lockfree_hashtable.c
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,561 @@
    /**
    * Lockfree is a set of lockfree containers for Linux and Linux kernel
    * Copyright (C) <2017> Arkady Miasnikov
    *
    * This program is free software: you can redistribute it and/or modify
    * it under the terms of the GNU General Public License as published by
    * the Free Software Foundation, either version 3 of the License, or
    * (at your option) any later version.
    *
    * This program is distributed in the hope that it will be useful,
    * but WITHOUT ANY WARRANTY; without even the implied warranty of
    * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
    * GNU General Public License for more details.
    *
    * You should have received a copy of the GNU General Public License
    * along with this program. If not, see <http://www.gnu.org/licenses/>.
    */


    /**
    * Implementation of lockfree linear probing hashtable
    * The hashtable targets SystemTap environment where a typical key is thread ID
    * The number of probes is limited by a constant. The index is not wrapping around,
    * but instead the hashtable allocates enough memory to handle linear probing in the end
    * of the table
    *
    * Limitation: a specific entry (a specific key) can be inserted and deleted by one thread.
    *
    * Performance: a core can make above 13M add&remove operations per second, cost of a
    * single operation is under 20nano which is an equivalent of 50-100 opcodes.
    */

    #pragma once


    #ifdef __KERNEL__
    # include "linux/vmalloc.h"
    # include "linux/printk.h"
    # define DEV_NAME "lockless"
    # define PRINTF(s, ...) printk(KERN_ALERT DEV_NAME ": %s: " s "\n", __func__, __VA_ARGS__)
    # define PRIu64 "llu"
    #else
    # include <stdlib.h>
    # include <stdio.h>
    # include <inttypes.h>
    # define PRINTF(s, ...) printf("%s: " s "\n", __func__, __VA_ARGS__)
    # define likely(x) __builtin_expect(!!(x), 1) // !!(x) will return 1 for any x != 0
    # define unlikely(x) __builtin_expect(!!(x), 0)
    # define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
    #endif

    #define __sync_access(x) (*(volatile __typeof__(*x) *) (x))

    /**
    * Based on https://gist.github.com/badboy/6267743
    * http://burtleburtle.net/bob/hash/integer.html
    * I replace the 'long key' by 'unsigned key' and unsigned Java right shifts
    * by regular C/C++ right shifts
    * I adopt the hash function for 22 (PID_MAX_LIMIT) bits integers
    */
    static uint32_t hash32shift(uint32_t key)
    {

    key = ~key + (key << 10); // key = (key << 15) - key - 1;
    key = key ^ (key >> 7);
    key = key + (key << 1);
    key = key ^ (key >> 2);
    key = key * 187; // key = (key + (key << 3)) + (key << 11);
    key = key ^ (key >> 11);
    return key;
    }

    static uint32_t hash_none(uint32_t key)
    {
    return key;
    }

    typedef struct
    {
    uint64_t insert;
    uint64_t remove;
    uint64_t search;
    uint64_t collision;
    uint64_t insert_err;
    uint64_t remove_err;
    } hashtable_stat_t;

    typedef struct
    {
    const char *name;
    size_t bits;

    uint32_t (*hashfunction)(uint32_t);

    size_t __size;
    size_t __memory_size;
    hashtable_stat_t __stat;
    void *__table;
    } hashtable_t;

    static hashtable_t *hashtable_registry[64];

    static int hashtable_show(char *buf, size_t len)
    {
    size_t i;
    int rc;
    size_t chars = 0;
    rc = snprintf(buf+chars, len-chars, "\n%-25s %12s %12s %12s %12s %12s %12s %12s %12s %12s \n",
    "Name", "Size", "Memory", "Ops", "Insert", "Remove", "Search", "Collision", "InsertErr", "RemoveErr");

    chars += rc;
    for (i = 0;i < ARRAY_SIZE(hashtable_registry);i++)
    {
    hashtable_t *hashtable = hashtable_registry[i];
    hashtable_stat_t *stat;
    if (!hashtable)
    continue;

    stat = &hashtable->__stat;
    rc = snprintf(buf+chars, len-chars, "%-25s %12zu %12zu %12" PRIu64 " %12" PRIu64 " %12" PRIu64 " %12" PRIu64 " %12" PRIu64 " %12" PRIu64 " %12" PRIu64 "\n",
    hashtable->name, hashtable->__size, hashtable->__memory_size,
    stat->insert+stat->remove+stat->search, stat->insert, stat->remove, stat->search, stat->collision, stat->insert_err, stat->remove_err
    );
    chars += rc;
    }
    return chars;
    }

    static void hashtable_registry_add(hashtable_t *table)
    {
    size_t i;
    for (i = 0;i < ARRAY_SIZE(hashtable_registry);i++)
    {
    hashtable_t *registry = hashtable_registry[i];
    if (registry == table)
    {
    PRINTF("Hashtable %s already registered", table->name);
    break;
    }
    if (!registry)
    {
    PRINTF("Register hashtable %s", table->name);
    hashtable_registry[i] = table;
    break;
    }
    }
    }

    static void hashtable_registry_remove(hashtable_t *table)
    {
    size_t i;
    for (i = 0;i < ARRAY_SIZE(hashtable_registry);i++)
    {
    hashtable_t *registry = hashtable_registry[i];
    if (registry == table)
    {
    PRINTF("Remove hashtable %s from the registry", table->name);
    hashtable_registry[i] = NULL;
    }
    }
    }

    static inline size_t hashtable_get_index(const hashtable_t *hashtable, const uint32_t hash) \
    { \
    return hash & (hashtable->__size - 1); \
    } \

    static void *hashtable_alloc(size_t size)
    {
    #ifdef __KERNEL__
    void *p;
    size = PAGE_ALIGN(size);
    p = vmalloc(size);
    if (p)
    {
    unsigned long long adr = (unsigned long long) p;
    while (size > 0)
    {
    SetPageReserved(vmalloc_to_page((void *)adr));
    adr += PAGE_SIZE;
    size -= PAGE_SIZE;
    }
    }
    return p;
    #else
    return malloc(size);
    #endif
    }

    static void hashtable_free(void *p, size_t size)
    {
    #ifdef __KERNEL__
    if (p)
    {
    unsigned long long adr = (unsigned long long) p;
    while ((long) size > 0) {
    ClearPageReserved(vmalloc_to_page((void *)adr));
    adr += PAGE_SIZE;
    size -= PAGE_SIZE;
    }
    vfree(p);
    }
    #else
    free(p);
    #endif
    }

    static void hashtable_close(hashtable_t *hashtable)
    {
    if (hashtable->__table)
    {
    hashtable_free(hashtable->__table, hashtable->__memory_size);
    }
    else
    {
    PRINTF("Failed to free null pointer for the hashtable %s", hashtable->name);
    }
    hashtable_registry_remove(hashtable);
    }



    #ifdef __KERNEL__
    # define HASHTABLE_CMPXCHG(key, val, new_val) cmpxchg(key, val, new_val)
    #else
    # define HASHTABLE_CMPXCHG(key, val, new_val) __sync_val_compare_and_swap(key, val, new_val)
    #endif

    #if 1
    #ifdef __KERNEL__
    # define HASHTABLE_BARRIER() barrier()
    #else
    # define HASHTABLE_BARRIER() __sync_synchronize()
    #endif
    #else
    # define HASHTABLE_BARRIER()
    #endif

    #define HASHTABLE_SLOT_ADDR(hashtable, tokn, index) &(((hashtable_## tokn ##_slot_t*)hashtable->__table)[index])

    /**
    * Illegal TID can be (PID_MAX_LIMIT+1)
    * Illegal data is 0 for TID, -1 for FD, etc (this is optional)
    */
    #define DECLARE_HASHTABLE(tokn, data_type, max_tries, illegal_key, illegal_data) \
    \
    typedef struct \
    { \
    volatile uint32_t key; \
    data_type data; \
    } hashtable_## tokn ## _slot_t; \
    \
    static void hashtable_## tokn ## _init_slot(hashtable_## tokn ## _slot_t *slot) \
    { \
    slot->key = illegal_key; \
    slot->data = illegal_data; \
    } \
    \
    /** \
    * Calculate number of slots in the hash table \
    * I add max_tries on top to ensure that there are max_tries slots after the \
    * end of the table \
    */ \
    static size_t hashtable_## tokn ##_memory_size(const int bits) \
    { \
    size_t slots = (1 << bits) + max_tries; \
    return (sizeof(hashtable_## tokn ## _slot_t) * slots); \
    } \
    \
    static int hashtable_## tokn ##_init(hashtable_t *hashtable) \
    { \
    size_t memory_size = hashtable_## tokn ## _memory_size(hashtable->bits); \
    void *p = hashtable_alloc(memory_size); \
    size_t i; \
    if (p) \
    { \
    if (hashtable->hashfunction == NULL) \
    { \
    hashtable->hashfunction = hash32shift; \
    } \
    hashtable->__size = (1 << hashtable->bits); \
    hashtable->__memory_size = memory_size; \
    hashtable->__table = p; \
    for (i = 0;i < hashtable->__size;i++) \
    { \
    hashtable_## tokn ## _init_slot(HASHTABLE_SLOT_ADDR(hashtable, tokn, i)); \
    } \
    hashtable_registry_add(hashtable); \
    return 1; \
    } \
    PRINTF("Failed to allocate %zu for the hashtable %s", memory_size, hashtable->name); \
    return 0; \
    } \
    \
    /** \
    * Hash the key, get an index in the hashtable, try compare-and-set. \
    * If fails (not likely) try again with the next slot (linear probing) \
    * continue until success or max_tries is hit \
    */ \
    static int hashtable_## tokn ##_insert(hashtable_t *hashtable, const uint32_t key, const data_type data) \
    { \
    const uint32_t hash = hashtable->hashfunction(key); \
    const uint32_t index = hashtable_get_index(hashtable, hash); \
    /* I can do this for the last slot too - I allocated max_tries more slots */ \
    const uint32_t index_max = index+max_tries; \
    uint32_t i; \
    hashtable->__stat.insert++; \
    for (i = index;i < index_max;i++) \
    { \
    hashtable_## tokn ##_slot_t *slot = HASHTABLE_SLOT_ADDR(hashtable, tokn, i); \
    uint32_t old_key = HASHTABLE_CMPXCHG(&slot->key, illegal_key, key); \
    if (likely(old_key == illegal_key)) /* Success */ \
    { \
    slot->data = data; \
    return 1; \
    } \
    else \
    { \
    hashtable->__stat.collision++; \
    } \
    } \
    \
    hashtable->__stat.insert_err++; \
    return 0; \
    } \
    \
    /** \
    * Hash the key, get an index in the hashtable, find the relevant entry, \
    * read the pointer, remove using atomic operation \
    * Only one context is allowed to remove a specific entry \
    */ \
    static int hashtable_## tokn ##_remove(hashtable_t *hashtable, const uint32_t key, data_type *data) \
    { \
    const uint32_t hash = hashtable->hashfunction(key); \
    const uint32_t index = hashtable_get_index(hashtable, hash); \
    /* I can do this for the last slot too - I allocated max_tries more slots */ \
    const uint32_t index_max = index+max_tries; \
    uint32_t i; \
    hashtable->__stat.remove++; \
    for (i = index;i < index_max;i++) \
    { \
    hashtable_## tokn ##_slot_t *slot = HASHTABLE_SLOT_ADDR(hashtable, tokn, i); \
    uint32_t old_key = slot->key; \
    if (likely(old_key == key)) \
    { \
    if (data) \
    { \
    *data = slot->data; \
    } \
    __sync_access(&slot->data) = illegal_data; \
    HASHTABLE_BARRIER(); \
    __sync_access(&slot->key) = illegal_key; \
    return 1; \
    } \
    } \
    \
    hashtable->__stat.remove_err++; \
    return 0; \
    } \
    \
    /** \
    * Hash the key, get an index in the hashtable, find the relevant entry, \
    * read the pointer \
    */ \
    static int hashtable_## tokn ##_find(hashtable_t *hashtable, const uint32_t key, data_type *data) \
    { \
    const uint32_t hash = hashtable->hashfunction(key); \
    const uint32_t index = hashtable_get_index(hashtable, hash); \
    /* I can do this for the last slot too - I allocated max_tries more slots */ \
    const uint32_t index_max = index+max_tries; \
    uint32_t i; \
    hashtable->__stat.search++; \
    for (i = index;i < index_max;i++) \
    { \
    hashtable_## tokn ##_slot_t *slot = HASHTABLE_SLOT_ADDR(hashtable, tokn, i); \
    uint32_t old_key = slot->key; \
    if (old_key == key) \
    { \
    *data = slot->data; \
    return 1; \
    } \
    } \
    \
    return 0; \
    } \


    #include <stdio.h>
    #include <stdint.h>
    #include <stdlib.h>
    #include "hashtable.h"
    #include "linux_utils.h"


    #define HASHTABLE_BITS 8


    static hashtable_t hashtable = {"hash", HASHTABLE_BITS, hash_none};

    DECLARE_HASHTABLE(uint32, uint32_t, 4, 0, 0);

    /**
    * The hashtable does 'value & ((1 << HASHTABLE_BITS)-1)'
    * The function generates values which will cause collision
    * in the table slot 0, the values are unique
    */
    static inline uint32_t get_value_collision(int idx)
    {
    return ((1 << HASHTABLE_BITS) << idx);
    }

    static inline uint32_t get_value(int idx)
    {
    return idx;
    }

    static int thread_job(void *thread_arg)
    {
    int idx = (int)(size_t)thread_arg;

    uint32_t value_to_store = get_value(idx);


    while (1)
    {
    int rc = hashtable_uint32_insert(&hashtable, value_to_store, 0);
    if (!rc)
    {
    linux_log(LINUX_LOG_ERROR, "Thread %d failed to insert entry %u",
    idx, value_to_store);
    return 1;
    }
    rc = hashtable_uint32_remove(&hashtable, value_to_store, NULL);
    if (!rc)
    {
    linux_log(LINUX_LOG_ERROR, "Thread %d failed to remove entry %u",
    idx, value_to_store);
    return 1;
    }
    }


    return 1;
    }

    static int create_threads(int cpus)
    {
    int rc;
    for (int i = 0;i < cpus;i++)
    {
    linux_task_state_t *state = (linux_task_state_t*)calloc(1, sizeof(linux_task_state_t));
    char filename[64];
    sprintf(filename, "%d", i);
    state->properties.name = strdup(filename);
    state->properties.task = thread_job;
    state->properties.task_arg = (void*)(size_t)i;
    rc = linux_thread_start(state);
    if (!rc)
    {
    break;
    }

    }
    return rc;
    }

    static int synchronous_access(int cpus)
    {
    for (int i = 0;i < cpus;i++)
    {
    uint32_t value_to_store = get_value(i);
    int rc = hashtable_uint32_insert(&hashtable, value_to_store, 0);
    if (!rc)
    {
    linux_log(LINUX_LOG_ERROR, "Thread %d failed to insert entry %u",
    i, value_to_store);
    return 0;
    }
    }
    for (int i = 0;i < cpus;i++)
    {
    uint32_t value_to_store = get_value(i);
    int rc = hashtable_uint32_remove(&hashtable, value_to_store, NULL);
    if (!rc)
    {
    linux_log(LINUX_LOG_ERROR, "Thread %d failed to remove entry %u",
    i, value_to_store);
    return 0;
    }
    }
    return 1;
    }

    int main()
    {
    int cpus = 4; //linux_get_number_processors()
    int rc;

    do
    {

    rc = hashtable_uint32_init(&hashtable);
    if (!rc)
    {
    break;
    }

    rc = synchronous_access(cpus);
    if (!rc)
    {
    break;
    }

    rc = create_threads(cpus);
    if (!rc)
    {
    break;
    }

    while (1)
    {
    linux_ms_sleep(1000);
    char buf[4*1024];
    hashtable_show(buf, ARRAY_SIZE(buf));
    linux_log(LINUX_LOG_INFO, "%s", buf);
    }
    hashtable_close(&hashtable);
    }
    while (0);

    return 0;
    }
    =========== Makefile ============


    TARGET = hashtable_test
    CXXFLAGS = -O2 -g -Wall -fmessage-length=0 -std=c++11
    CXX = $(CROSS)g++ $(INCLUDE_DIRS)
    LIBS = -lpthread -lrt


    APP_OBJS = ./hashtable_test.o \
    ./linux_utils.o \

    APP_DEPS = ./hashtable_test.cpp \
    ./linux_utils.cpp \
    ./linux_utils.h \
    ./Makefile \
    ./hashtable.h \



    $(TARGET):: $(APP_DEPS) $(APP_OBJS)
    $(CXX) $(CXXFLAGS) -o $(TARGET) -pthread $(APP_OBJS) $(LIBS)

    all: $(TARGET)

    clean:
    $(Q)rm -f $(APP_OBJS) $(TARGET)


  3. @larytet larytet revised this gist Jul 12, 2017. 1 changed file with 212 additions and 137 deletions.
    349 changes: 212 additions & 137 deletions kernel_hashtable.c
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,53 @@
    /**
    * Lockfree is a set of lockfree containers for Linux and Linux kernel
    * Copyright (C) <2017> Arkady Miasnikov
    *
    * This program is free software: you can redistribute it and/or modify
    * it under the terms of the GNU General Public License as published by
    * the Free Software Foundation, either version 3 of the License, or
    * (at your option) any later version.
    *
    * This program is distributed in the hope that it will be useful,
    * but WITHOUT ANY WARRANTY; without even the implied warranty of
    * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
    * GNU General Public License for more details.
    *
    * You should have received a copy of the GNU General Public License
    * along with this program. If not, see <http://www.gnu.org/licenses/>.
    */


    /**
    * Implementation of lockfree linear probing hashtable
    * The hashtable targets SystemTap environment where a typical key is thread ID
    * The number of probes is limited by a constant. The index is not wrapping around,
    * but instead the hashtable allocates enough memory to handle linear probing in the end
    * of the table
    *
    * Limitation: a specific entry (a specific key) can be inserted and deleted by one thread.
    *
    * Performance: a core can make above 13M add&remove operations per second, cost of a
    * single operation is under 20nano which is an equivalent of 50-100 opcodes.
    */

    #pragma once


    #if KERNEL
    # inclide "linux/vmalloc.h"
    # include "linux/printk.h"
    # define DEV_NAME "lockless"
    # define PRINTF(s, ...) printk(KERN_ALERT DEV_NAME ": %s: " s "\n", __func__, __VA_ARGS__)
    #else
    # include <stdlib.h>
    # include <stdio.h>
    # define PRINTF(s, ...) printf("%s: " s "\n", __func__, __VA_ARGS__)
    # define likely(x) __builtin_expect(!!(x), 1) // !!(x) will return 1 for any x != 0
    # define unlikely(x) __builtin_expect(!!(x), 0)
    #endif

    #define __sync_access(x) (*(volatile __typeof__(*x) *) (x))

    /**
    * My key is a thread ID (22 bits) and my data is a chunk in the
    * FIFO orgtanised in the driver shared memory
    @@ -6,33 +56,33 @@
    */
    typedef struct
    {
    volatile u32 key;
    u32 age;
    void *data;
    volatile uint32_t key;
    uint32_t age;
    void *data;
    } hashtable_slot_t;

    typedef struct
    {
    size_t size;
    u64 insert;
    u64 remove;
    u64 collision;
    u64 insert_err;
    u64 remove_err;
    size_t size;
    uint64_t insert;
    uint64_t remove;
    uint64_t collision;
    uint64_t insert_err;
    uint64_t remove_err;
    } hashtable_stat_t;

    typedef struct
    {
    const char *name;
    size_t bits;
    const char *name;
    size_t bits;

    // Probably not necessary, because I am going to use a trivial one to one hash function
    u32 (*hashfunction)(u32);
    // Probably not necessary, because I am going to use a trivial one to one hash function
    uint32_t (*hashfunction)(uint32_t);

    size_t __size;
    size_t __memory_size;
    hashtable_slot_t *__table;
    hashtable_stat_t __stat;
    size_t __size;
    size_t __memory_size;
    hashtable_slot_t *__table;
    hashtable_stat_t __stat;
    } hashtable_t;


    @@ -43,13 +93,13 @@ typedef struct
    */
    static size_t hashtable_memory_size(const int bits, size_t max_tries)
    {
    size_t slots = (1 << bits) + max_tries;
    return (sizeof(hashtable_slot_t) * slots);
    size_t slots = (1 << bits) + max_tries;
    return (sizeof(hashtable_slot_t) * slots);
    }

    static const size_t HASHTABLE_MAX_TRIES = 3;
    static const size_t HASHTABLE_MAX_TRIES = 8;
    // Illegal TID can be (PID_MAX_LIMIT+1)
    static const u32 ILLEGAL_KEY = 0;
    static const uint32_t ILLEGAL_KEY = 0;

    /**
    * Based on https://gist.github.com/badboy/6267743
    @@ -58,171 +108,196 @@ static const u32 ILLEGAL_KEY = 0;
    * by regular C/C++ right shifts
    * I adopt the hash function for 22 (PID_MAX_LIMIT) bits integers
    */
    static u32 hash32shift(u32 key)
    static uint32_t hash32shift(uint32_t key)
    {

    key = ~key + (key << 10); // key = (key << 15) - key - 1;
    key = key ^ (key >> 7);
    key = key + (key << 1);
    key = key ^ (key >> 2);
    key = key * 187; // key = (key + (key << 3)) + (key << 11);
    key = key ^ (key >> 11);
    return key;
    key = ~key + (key << 10); // key = (key << 15) - key - 1;
    key = key ^ (key >> 7);
    key = key + (key << 1);
    key = key ^ (key >> 2);
    key = key * 187; // key = (key + (key << 3)) + (key << 11);
    key = key ^ (key >> 11);
    return key;
    }

    static u32 hash_none(u32 key)
    static uint32_t hash_none(uint32_t key)
    {
    return key;
    return key;
    }

    static void hashtable_init_slot(hashtable_slot_t *slot)
    {
    slot->key = ILLEGAL_KEY;
    slot->data = NULL;
    slot->age = 0;
    slot->key = ILLEGAL_KEY;
    slot->data = NULL;
    slot->age = 0;
    }

    static int hashtable_init(hashtable_t *hashtable)
    {
    size_t memory_size = hashtable_memory_size(hashtable->bits, HASHTABLE_MAX_TRIES);
    void *p = vmalloc(memory_size);
    int i;
    if (p)
    {
    if (hashtable->hashfunction == NULL)
    {
    hashtable->hashfunction = hash32shift;
    }
    hashtable->__size = (1 << hashtable->bits);
    hashtable->__memory_size = memory_size;
    memset(&hashtable->__stat, 0, sizeof(hashtable->__stat));
    hashtable->__table = (hashtable_slot_t*)p;
    for (i = 0;i < hashtable->__size;i++)
    {
    hashtable_init_slot(&hashtable->__table[i]);
    }
    return 1;
    }
    PRINTF("Failed to allocate %u for the hashtable %s", (unsigned)memory_size, hashtable->name);
    return 0;
    size_t memory_size = hashtable_memory_size(hashtable->bits, HASHTABLE_MAX_TRIES);
    #ifdef KERNEL
    void *p = vmalloc(memory_size);
    #else
    void *p = malloc(memory_size);
    #endif
    size_t i;
    if (p)
    {
    if (hashtable->hashfunction == NULL)
    {
    hashtable->hashfunction = hash32shift;
    }
    hashtable->__size = (1 << hashtable->bits);
    hashtable->__memory_size = memory_size;
    hashtable->__table = (hashtable_slot_t*)p;
    for (i = 0;i < hashtable->__size;i++)
    {
    hashtable_init_slot(&hashtable->__table[i]);
    }
    return 1;
    }
    PRINTF("Failed to allocate %u for the hashtable %s", (unsigned)memory_size, hashtable->name);
    return 0;
    }

    static int hashtable_init_all(hashtable_t *hashtable)
    {
    int res = 0;
    int res = 0;

    for (;hashtable->name && hashtable->bits;hashtable++)
    {
    res = hashtable_init(hashtable);
    if (!res)
    break;
    }
    for (;hashtable->name && hashtable->bits;hashtable++)
    {
    res = hashtable_init(hashtable);
    if (!res)
    break;
    }

    return res;
    return res;
    }


    static void hashtable_close(hashtable_t *hashtable)
    {
    if (hashtable->__table)
    {
    vfree(hashtable->__table);
    }
    else
    {
    PRINTF("Failed to free null pointer for the hashtable %s", hashtable->name);
    }
    if (hashtable->__table)
    {
    #ifdef KERNEL
    vfree(hashtable->__table);
    #else
    free(hashtable->__table);
    #endif
    }
    else
    {
    PRINTF("Failed to free null pointer for the hashtable %s", hashtable->name);
    }
    }

    static void hashtable_close_all(hashtable_t *hashtable)
    {
    for (;hashtable->name && hashtable->bits;hashtable++)
    {
    hashtable_close(hashtable);
    }
    for (;hashtable->name && hashtable->bits;hashtable++)
    {
    hashtable_close(hashtable);
    }
    }

    static inline size_t hashtable_get_index(const hashtable_t *hashtable, const uint32_t hash)
    {
    return hash & (hashtable->__size - 1);
    }

    /**
    * Hash the key, get an index in the hashtable, try compare-and-set.
    * If fails (not likely) try again with the next slot (linear probing)
    * continue until success or max_tries is hit
    */
    static int hashtable_insert(hashtable_t *hashtable, const u32 key, void * const data)
    static int hashtable_insert(hashtable_t *hashtable, const uint32_t key, void * const data)
    {
    const u32 hash = hashtable->hashfunction(key);
    const u32 index = hash & hashtable->__size;
    const u32 index_max = index+HASHTABLE_MAX_TRIES; // I can do this for the last slot too - I allocated max_tries more slots
    u32 i;
    hashtable->__stat.insert++;
    for (i = index;i < index_max;i++)
    {
    hashtable_slot_t *slot = &hashtable->__table[index];
    u32 old_key = cmpxchg(&slot->key, ILLEGAL_KEY, key);
    if (old_key == ILLEGAL_KEY) // Success
    {
    slot->data = data;
    return 1;
    }
    else
    {
    hashtable->__stat.collision++;
    }
    }

    hashtable->__stat.insert_err++;
    return 0;
    const uint32_t hash = hashtable->hashfunction(key);
    const uint32_t index = hashtable_get_index(hashtable, hash);
    const uint32_t index_max = index+HASHTABLE_MAX_TRIES; // I can do this for the last slot too - I allocated max_tries more slots
    uint32_t i;
    hashtable->__stat.insert++;
    for (i = index;i < index_max;i++)
    {
    hashtable_slot_t *slot = &hashtable->__table[i];
    #if KERNEL
    uint32_t old_key = cmpxchg(&slot->key, ILLEGAL_KEY, key);
    #else
    uint32_t old_key = __sync_val_compare_and_swap(&slot->key, ILLEGAL_KEY, key);
    #endif
    if (likely(old_key == ILLEGAL_KEY)) // Success
    {
    slot->data = data;
    return 1;
    }
    else
    {
    hashtable->__stat.collision++;
    }
    }

    hashtable->__stat.insert_err++;
    return 0;
    }

    /**
    * Hash the key, get an index in the hashtable, find the relevant entry,
    * read the pointer, remove using atomic operation
    * Only one context is allowed to remove a specific entry
    */
    static int hashtable_remove(hashtable_t *hashtable, const u32 key, void **data)
    static int hashtable_remove(hashtable_t *hashtable, const uint32_t key, void **data)
    {
    const u32 hash = hashtable->hashfunction(key);
    const u32 index = hash & hashtable->__size;
    const u32 index_max = index+HASHTABLE_MAX_TRIES; // I can do this for the last slot too - I allocated max_tries more slots
    u32 i;
    hashtable->__stat.remove++;
    for (i = index;i < index_max;i++)
    {
    hashtable_slot_t *slot = &hashtable->__table[index];
    u32 old_key = slot->key;
    if (old_key == key)
    {
    *data = slot->data;
    slot->data = NULL;
    barrier();
    slot->key = ILLEGAL_KEY;
    return 1;
    }
    }

    hashtable->__stat.remove_err++;
    return 0;
    const uint32_t hash = hashtable->hashfunction(key);
    const uint32_t index = hashtable_get_index(hashtable, hash);
    const uint32_t index_max = index+HASHTABLE_MAX_TRIES; // I can do this for the last slot too - I allocated max_tries more slots
    uint32_t i;
    hashtable->__stat.remove++;
    for (i = index;i < index_max;i++)
    {
    hashtable_slot_t *slot = &hashtable->__table[i];
    uint32_t old_key = slot->key;
    if (likely(old_key == key))
    {
    if (data)
    {
    *data = slot->data;
    }
    __sync_access(&slot->data) = NULL;
    #if 0 // I hope that I do not need a barrier here
    #ifdef KERNEL
    barrier();
    #else
    __sync_synchronize();
    #endif
    #endif
    __sync_access(&slot->key) = ILLEGAL_KEY;
    return 1;
    }
    }

    hashtable->__stat.remove_err++;
    return 0;
    }

    /**
    * Hash the key, get an index in the hashtable, find the relevant entry,
    * read the pointer
    */
    static int hashtable_find(const hashtable_t *hashtable, const u32 key, void **data)
    static int hashtable_find(const hashtable_t *hashtable, const uint32_t key, void **data)
    {
    const u32 hash = hashtable->hashfunction(key);
    const u32 index = hash & hashtable->__size;
    const u32 index_max = index+HASHTABLE_MAX_TRIES; // I can do this for the last slot too - I allocated max_tries more slots
    u32 i;
    for (i = index;i < index_max;i++)
    {
    hashtable_slot_t *slot = &hashtable->__table[index];
    u32 old_key = slot->key;
    if (old_key == key)
    {
    *data = slot->data;
    return 1;
    }
    }

    return 0;
    const uint32_t hash = hashtable->hashfunction(key);
    const uint32_t index = hashtable_get_index(hashtable, hash);
    const uint32_t index_max = index+HASHTABLE_MAX_TRIES; // I can do this for the last slot too - I allocated max_tries more slots
    uint32_t i;
    for (i = index;i < index_max;i++)
    {
    hashtable_slot_t *slot = &hashtable->__table[i];
    uint32_t old_key = slot->key;
    if (old_key == key)
    {
    *data = slot->data;
    return 1;
    }
    }

    return 0;
    }
  4. @larytet larytet revised this gist Jul 9, 2017. 1 changed file with 0 additions and 22 deletions.
    22 changes: 0 additions & 22 deletions kernel_hashtable.c
    View file
    Original file line number Diff line number Diff line change
    @@ -1,25 +1,3 @@
    /**
    * Based on https://gist.github.com/larytet/c306d470f7b032c796efad15dcd609a9
    */

    /**
    * YALAS is a Linux audit system based on SystemTap
    * Copyright (C) <2017> Arkady Miasnikov
    *
    * This program is free software: you can redistribute it and/or modify
    * it under the terms of the GNU General Public License as published by
    * the Free Software Foundation, either version 3 of the License, or
    * (at your option) any later version.
    *
    * This program is distributed in the hope that it will be useful,
    * but WITHOUT ANY WARRANTY; without even the implied warranty of
    * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
    * GNU General Public License for more details.
    *
    * You should have received a copy of the GNU General Public License
    * along with this program. If not, see <http://www.gnu.org/licenses/>.
    */

    /**
    * My key is a thread ID (22 bits) and my data is a chunk in the
    * FIFO orgtanised in the driver shared memory
  5. @larytet larytet revised this gist Jul 9, 2017. 1 changed file with 130 additions and 46 deletions.
    176 changes: 130 additions & 46 deletions kernel_hashtable.c
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,25 @@
    /**
    * Based on https://gist.github.com/larytet/c306d470f7b032c796efad15dcd609a9
    */

    /**
    * YALAS is a Linux audit system based on SystemTap
    * Copyright (C) <2017> Arkady Miasnikov
    *
    * This program is free software: you can redistribute it and/or modify
    * it under the terms of the GNU General Public License as published by
    * the Free Software Foundation, either version 3 of the License, or
    * (at your option) any later version.
    *
    * This program is distributed in the hope that it will be useful,
    * but WITHOUT ANY WARRANTY; without even the implied warranty of
    * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
    * GNU General Public License for more details.
    *
    * You should have received a copy of the GNU General Public License
    * along with this program. If not, see <http://www.gnu.org/licenses/>.
    */

    /**
    * My key is a thread ID (22 bits) and my data is a chunk in the
    * FIFO orgtanised in the driver shared memory
    @@ -14,8 +36,25 @@ typedef struct
    typedef struct
    {
    size_t size;
    size_t memory_size;
    hashtable_slot_t *table;
    u64 insert;
    u64 remove;
    u64 collision;
    u64 insert_err;
    u64 remove_err;
    } hashtable_stat_t;

    typedef struct
    {
    const char *name;
    size_t bits;

    // Probably not necessary, because I am going to use a trivial one to one hash function
    u32 (*hashfunction)(u32);

    size_t __size;
    size_t __memory_size;
    hashtable_slot_t *__table;
    hashtable_stat_t __stat;
    } hashtable_t;


    @@ -34,57 +73,95 @@ static const size_t HASHTABLE_MAX_TRIES = 3;
    // Illegal TID can be (PID_MAX_LIMIT+1)
    static const u32 ILLEGAL_KEY = 0;

    /**
    * Based on https://gist.github.com/badboy/6267743
    * http://burtleburtle.net/bob/hash/integer.html
    * I replace the 'long key' by 'unsigned key' and unsigned Java right shifts
    * by regular C/C++ right shifts
    * I adopt the hash function for 22 (PID_MAX_LIMIT) bits integers
    */
    static u32 hash32shift(u32 key)
    {

    key = ~key + (key << 10); // key = (key << 15) - key - 1;
    key = key ^ (key >> 7);
    key = key + (key << 1);
    key = key ^ (key >> 2);
    key = key * 187; // key = (key + (key << 3)) + (key << 11);
    key = key ^ (key >> 11);
    return key;
    }

    static u32 hash_none(u32 key)
    {
    return key;
    }

    static void hashtable_init_slot(hashtable_slot_t *slot)
    {
    slot->key = ILLEGAL_KEY;
    slot->data = NULL;
    slot->age = 0;

    }

    static int hashtable_init(hashtable_t *hashtable, const size_t bits)
    static int hashtable_init(hashtable_t *hashtable)
    {
    size_t memory_size = hashtable_memory_size(bits, HASHTABLE_MAX_TRIES);
    size_t memory_size = hashtable_memory_size(hashtable->bits, HASHTABLE_MAX_TRIES);
    void *p = vmalloc(memory_size);
    int i;
    if (p)
    {
    hashtable->size = (1 << bits);
    hashtable->memory_size = memory_size;
    hashtable->table = (hashtable_slot_t*)p;
    for (i = 0;i < hashtable->size;i++)
    if (hashtable->hashfunction == NULL)
    {
    hashtable_init_slot(&hashtable->table[i]);
    hashtable->hashfunction = hash32shift;
    }
    return 0;
    hashtable->__size = (1 << hashtable->bits);
    hashtable->__memory_size = memory_size;
    memset(&hashtable->__stat, 0, sizeof(hashtable->__stat));
    hashtable->__table = (hashtable_slot_t*)p;
    for (i = 0;i < hashtable->__size;i++)
    {
    hashtable_init_slot(&hashtable->__table[i]);
    }
    return 1;
    }
    return 1;
    PRINTF("Failed to allocate %u for the hashtable %s", (unsigned)memory_size, hashtable->name);
    return 0;
    }

    static void hashtable_close(hashtable_t *hashtable)
    static int hashtable_init_all(hashtable_t *hashtable)
    {
    vfree(hashtable->table);
    int res = 0;

    for (;hashtable->name && hashtable->bits;hashtable++)
    {
    res = hashtable_init(hashtable);
    if (!res)
    break;
    }

    return res;
    }

    /**
    * Based on https://gist.github.com/badboy/6267743
    * http://burtleburtle.net/bob/hash/integer.html
    * I replace the 'long key' by 'unsigned key' and unsigned Java right shifts
    * by regular C/C++ right shifts
    * I adopt the hash function for 22 (PID_MAX_LIMIT) bits integers
    * TODO For TID I can use a trivial hash function - 22 bits is an equivalent of ~64MB in the RAM
    */
    static u32 hash32shift(u32 key)

    static void hashtable_close(hashtable_t *hashtable)
    {
    if (hashtable->__table)
    {
    vfree(hashtable->__table);
    }
    else
    {
    PRINTF("Failed to free null pointer for the hashtable %s", hashtable->name);
    }
    }

    key = ~key + (key << 10); // key = (key << 15) - key - 1;
    key = key ^ (key >> 7);
    key = key + (key << 1);
    key = key ^ (key >> 2);
    key = key * 187; // key = (key + (key << 3)) + (key << 11);
    key = key ^ (key >> 11);
    return key;
    static void hashtable_close_all(hashtable_t *hashtable)
    {
    for (;hashtable->name && hashtable->bits;hashtable++)
    {
    hashtable_close(hashtable);
    }
    }

    /**
    @@ -94,22 +171,28 @@ static u32 hash32shift(u32 key)
    */
    static int hashtable_insert(hashtable_t *hashtable, const u32 key, void * const data)
    {
    const u32 hash = hash32shift(key);
    const u32 index = hash & hashtable->size;
    const u32 hash = hashtable->hashfunction(key);
    const u32 index = hash & hashtable->__size;
    const u32 index_max = index+HASHTABLE_MAX_TRIES; // I can do this for the last slot too - I allocated max_tries more slots
    u32 i;
    hashtable->__stat.insert++;
    for (i = index;i < index_max;i++)
    {
    hashtable_slot_t *slot = &hashtable->table[index];
    hashtable_slot_t *slot = &hashtable->__table[index];
    u32 old_key = cmpxchg(&slot->key, ILLEGAL_KEY, key);
    if (old_key == ILLEGAL_KEY) // Success
    {
    slot->data = data;
    return 0;
    return 1;
    }
    else
    {
    hashtable->__stat.collision++;
    }
    }

    return 1;
    hashtable->__stat.insert_err++;
    return 0;
    }

    /**
    @@ -119,25 +202,27 @@ static int hashtable_insert(hashtable_t *hashtable, const u32 key, void * const
    */
    static int hashtable_remove(hashtable_t *hashtable, const u32 key, void **data)
    {
    const u32 hash = hash32shift(key);
    const u32 index = hash & hashtable->size;
    const u32 hash = hashtable->hashfunction(key);
    const u32 index = hash & hashtable->__size;
    const u32 index_max = index+HASHTABLE_MAX_TRIES; // I can do this for the last slot too - I allocated max_tries more slots
    u32 i;
    hashtable->__stat.remove++;
    for (i = index;i < index_max;i++)
    {
    hashtable_slot_t *slot = &hashtable->table[index];
    hashtable_slot_t *slot = &hashtable->__table[index];
    u32 old_key = slot->key;
    if (old_key == key)
    {
    *data = slot->data;
    slot->data = NULL;
    barrier();
    slot->key = ILLEGAL_KEY;
    return 0;
    return 1;
    }
    }

    return 1;
    hashtable->__stat.remove_err++;
    return 0;
    }

    /**
    @@ -146,21 +231,20 @@ static int hashtable_remove(hashtable_t *hashtable, const u32 key, void **data)
    */
    static int hashtable_find(const hashtable_t *hashtable, const u32 key, void **data)
    {
    const u32 hash = hash32shift(key);
    const u32 index = hash & hashtable->size;
    const u32 hash = hashtable->hashfunction(key);
    const u32 index = hash & hashtable->__size;
    const u32 index_max = index+HASHTABLE_MAX_TRIES; // I can do this for the last slot too - I allocated max_tries more slots
    u32 i;
    for (i = index;i < index_max;i++)
    {
    hashtable_slot_t *slot = &hashtable->table[index];
    hashtable_slot_t *slot = &hashtable->__table[index];
    u32 old_key = slot->key;
    if (old_key == key)
    {
    *data = slot->data;
    return 0;
    return 1;
    }
    }

    return 1;
    return 0;
    }

  6. @larytet larytet revised this gist Jul 9, 2017. 1 changed file with 1 addition and 0 deletions.
    1 change: 1 addition & 0 deletions kernel_hashtable.c
    View file
    Original file line number Diff line number Diff line change
    @@ -73,6 +73,7 @@ static void hashtable_close(hashtable_t *hashtable)
    * I replace the 'long key' by 'unsigned key' and unsigned Java right shifts
    * by regular C/C++ right shifts
    * I adopt the hash function for 22 (PID_MAX_LIMIT) bits integers
    * TODO For TID I can use a trivial hash function - 22 bits is an equivalent of ~64MB in the RAM
    */
    static u32 hash32shift(u32 key)
    {
  7. @larytet larytet revised this gist Jul 8, 2017. 1 changed file with 23 additions and 68 deletions.
    91 changes: 23 additions & 68 deletions kernel_hashtable.c
    View file
    Original file line number Diff line number Diff line change
    @@ -26,74 +26,23 @@ typedef struct
    */
    static size_t hashtable_memory_size(const int bits, size_t max_tries)
    {
    return (sizeof(hashtable_slot_t) * ((1 << bits) + max_tries);
    size_t slots = (1 << bits) + max_tries;
    return (sizeof(hashtable_slot_t) * slots);
    }

    static const size_t HASHTABLE_MAX_TRIES = 3;
    // Illegal TID can be (PID_MAX_LIMIT+1)
    static const u32 ILLEGAL_KEY = 0;
    static int hashtable_init(hashtable_t *hashtable, const size_t bits)
    {
    size_t memory_size = hashtable_memory_size(bits, HASHTABLE_MAX_TRIES);
    void *p = vmalloc(memory_size);
    int i;
    if (p)
    {
    hashtable->size = (1 << bits);
    hashtable->memory_size = memory_size;
    for (i = 0;i < hashtable->size;i++)
    {
    hashtable->tale[i].key = ILLEGAL_KEY;
    hashtable->tale[i].data = NULL;
    hashtable->tale[i].age = 0;
    }
    hashtable->table = (hashtable_slot_t*)p;
    return 0;
    }
    return 1;
    }

    /**
    * My key is a thread ID (22 bits) and my data is a chunk in the
    * FIFO orgtanised in the driver shared memory
    * Th field age is a value of the CPU cycles counter when the slot
    * is populated.
    */
    typedef struct
    {
    volatile u32 key;
    u32 age;
    void *data;
    } hashtable_slot_t;

    typedef struct
    {
    size_t size;
    size_t memory_size;
    hashtable_slot_t *table;
    } hashtable_t;


    /**
    * Calculate number of slots in the hash table
    * I add max_tries on top to ensure that there are max_tries slots after the
    * end of the table
    */
    static size_t hashtable_memory_size(const int bits, size_t max_tries)
    {
    return (sizeof(hashtable_slot_t) * ((1 << bits) + max_tries);
    }

    static void hashtable_init_slot(hashtable_slot_t *slot)
    {
    slot->key = ILLEGAL_KEY;
    slot->data = NULL;
    slot->age = 0;

    }

    static const size_t HASHTABLE_MAX_TRIES = 3;
    // Illegal TID can be (PID_MAX_LIMIT+1)
    static const u32 ILLEGAL_KEY = 0;
    static int hashtable_init(hashtable_t *hashtable, const size_t bits)
    {
    size_t memory_size = hashtable_memory_size(bits, HASHTABLE_MAX_TRIES);
    @@ -113,14 +62,19 @@ static int hashtable_init(hashtable_t *hashtable, const size_t bits)
    return 1;
    }

    static void hashtable_close(hashtable_t *hashtable)
    {
    vfree(hashtable->table);
    }

    /**
    * Based on https://gist.github.com/badboy/6267743
    * Based on https://gist.github.com/badboy/6267743
    * http://burtleburtle.net/bob/hash/integer.html
    * I replace the 'long key' by 'unsigned key' and unsigned Java right shifts
    * by regular C/C++ right shifts
    * I adopt the hash function for 22 (PID_MAX_LIMIT) bits integers
    */
    public u32 hash32shift(u32 key)
    static u32 hash32shift(u32 key)
    {

    key = ~key + (key << 10); // key = (key << 15) - key - 1;
    @@ -137,19 +91,19 @@ public u32 hash32shift(u32 key)
    * If fails (not likely) try again with the next slot (linear probing)
    * continue until success or max_tries is hit
    */
    static int hashtable_insert(hashtable_t *hashtable, const u32 key, const void *data)
    static int hashtable_insert(hashtable_t *hashtable, const u32 key, void * const data)
    {
    const u32 hash = hash32shift(key);
    const u32 index = hash & hashtable->size;
    const u32 index_max = index+HASHTABLE_MAX_TRIES; // I can do this for the last slot too - I allocated max_tries more slots
    u32 i;
    for (i = index;i < index_max;i++)
    {
    u32 *slot_key = (u32*)&hashtable->table[index];
    u32 old_key = cmpxchg(slot_key, ILLEGAL_KEY, key);
    hashtable_slot_t *slot = &hashtable->table[index];
    u32 old_key = cmpxchg(&slot->key, ILLEGAL_KEY, key);
    if (old_key == ILLEGAL_KEY) // Success
    {
    slot_key->data = data;
    slot->data = data;
    return 0;
    }
    }
    @@ -170,14 +124,14 @@ static int hashtable_remove(hashtable_t *hashtable, const u32 key, void **data)
    u32 i;
    for (i = index;i < index_max;i++)
    {
    u32 *slot_key = (u32*)&hashtable->table[index];
    u32 old_key = slot_key->key;
    hashtable_slot_t *slot = &hashtable->table[index];
    u32 old_key = slot->key;
    if (old_key == key)
    {
    *data = slot_key->data;
    slot_key->data = NULL;
    *data = slot->data;
    slot->data = NULL;
    barrier();
    slot_key->key = ILLEGAL_KEY;
    slot->key = ILLEGAL_KEY;
    return 0;
    }
    }
    @@ -197,14 +151,15 @@ static int hashtable_find(const hashtable_t *hashtable, const u32 key, void **da
    u32 i;
    for (i = index;i < index_max;i++)
    {
    u32 *slot_key = (u32*)&hashtable->table[index];
    u32 old_key = slot_key->key;
    hashtable_slot_t *slot = &hashtable->table[index];
    u32 old_key = slot->key;
    if (old_key == key)
    {
    *data = slot_key->data;
    *data = slot->data;
    return 0;
    }
    }

    return 1;
    }

  8. @larytet larytet revised this gist Jul 6, 2017. 1 changed file with 2 additions and 1 deletion.
    3 changes: 2 additions & 1 deletion kernel_hashtable.c
    View file
    Original file line number Diff line number Diff line change
    @@ -114,7 +114,8 @@ static int hashtable_init(hashtable_t *hashtable, const size_t bits)
    }

    /**
    * Based on https://gist.github.com/badboy/6267743
    * Based on https://gist.github.com/badboy/6267743
    * http://burtleburtle.net/bob/hash/integer.html
    * I replace the 'long key' by 'unsigned key' and unsigned Java right shifts
    * by regular C/C++ right shifts
    * I adopt the hash function for 22 (PID_MAX_LIMIT) bits integers
  9. @larytet larytet revised this gist Jul 6, 2017. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion kernel_hashtable.c
    View file
    Original file line number Diff line number Diff line change
    @@ -1,7 +1,7 @@
    /**
    * My key is a thread ID (22 bits) and my data is a chunk in the
    * FIFO orgtanised in the driver shared memory
    * Th field age is a timestamp in microseconds when the slot
    * Th field age is a timestamp in ms when the slot
    * is populated.
    */
    typedef struct
  10. @larytet larytet revised this gist Jul 6, 2017. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion kernel_hashtable.c
    View file
    Original file line number Diff line number Diff line change
    @@ -1,7 +1,7 @@
    /**
    * My key is a thread ID (22 bits) and my data is a chunk in the
    * FIFO orgtanised in the driver shared memory
    * Th field age is a value of the CPU cycles counter when the slot
    * Th field age is a timestamp in microseconds when the slot
    * is populated.
    */
    typedef struct
  11. @larytet larytet revised this gist Jul 6, 2017. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion kernel_hashtable.c
    View file
    Original file line number Diff line number Diff line change
    @@ -103,11 +103,11 @@ static int hashtable_init(hashtable_t *hashtable, const size_t bits)
    {
    hashtable->size = (1 << bits);
    hashtable->memory_size = memory_size;
    hashtable->table = (hashtable_slot_t*)p;
    for (i = 0;i < hashtable->size;i++)
    {
    hashtable_init_slot(&hashtable->table[i]);
    }
    hashtable->table = (hashtable_slot_t*)p;
    return 0;
    }
    return 1;
  12. @larytet larytet revised this gist Jul 6, 2017. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion kernel_hashtable.c
    View file
    Original file line number Diff line number Diff line change
    @@ -105,7 +105,7 @@ static int hashtable_init(hashtable_t *hashtable, const size_t bits)
    hashtable->memory_size = memory_size;
    for (i = 0;i < hashtable->size;i++)
    {
    hashtable_init_slot(&hashtable->tale[i]);
    hashtable_init_slot(&hashtable->table[i]);
    }
    hashtable->table = (hashtable_slot_t*)p;
    return 0;
  13. @larytet larytet revised this gist Jul 6, 2017. 1 changed file with 65 additions and 6 deletions.
    71 changes: 65 additions & 6 deletions kernel_hashtable.c
    View file
    Original file line number Diff line number Diff line change
    @@ -21,7 +21,7 @@ typedef struct

    /**
    * Calculate number of slots in the hash table
    * I add max_tries on top to ensure that there are max_tries slots after the
    * I add max_tries on top to ensure that there are max_tries slots after the
    * end of the table
    */
    static size_t hashtable_memory_size(const int bits, size_t max_tries)
    @@ -30,7 +30,7 @@ static size_t hashtable_memory_size(const int bits, size_t max_tries)
    }

    static const size_t HASHTABLE_MAX_TRIES = 3;
    // Illegal TID can be (PID_MAX_LIMIT+1)
    // Illegal TID can be (PID_MAX_LIMIT+1)
    static const u32 ILLEGAL_KEY = 0;
    static int hashtable_init(hashtable_t *hashtable, const size_t bits)
    {
    @@ -53,24 +53,84 @@ static int hashtable_init(hashtable_t *hashtable, const size_t bits)
    return 1;
    }

    /**
    * My key is a thread ID (22 bits) and my data is a chunk in the
    * FIFO orgtanised in the driver shared memory
    * Th field age is a value of the CPU cycles counter when the slot
    * is populated.
    */
    typedef struct
    {
    volatile u32 key;
    u32 age;
    void *data;
    } hashtable_slot_t;

    typedef struct
    {
    size_t size;
    size_t memory_size;
    hashtable_slot_t *table;
    } hashtable_t;


    /**
    * Calculate number of slots in the hash table
    * I add max_tries on top to ensure that there are max_tries slots after the
    * end of the table
    */
    static size_t hashtable_memory_size(const int bits, size_t max_tries)
    {
    return (sizeof(hashtable_slot_t) * ((1 << bits) + max_tries);
    }

    static void hashtable_init_slot(hashtable_slot_t *slot)
    {
    slot->key = ILLEGAL_KEY;
    slot->data = NULL;
    slot->age = 0;
    }

    static const size_t HASHTABLE_MAX_TRIES = 3;
    // Illegal TID can be (PID_MAX_LIMIT+1)
    static const u32 ILLEGAL_KEY = 0;
    static int hashtable_init(hashtable_t *hashtable, const size_t bits)
    {
    size_t memory_size = hashtable_memory_size(bits, HASHTABLE_MAX_TRIES);
    void *p = vmalloc(memory_size);
    int i;
    if (p)
    {
    hashtable->size = (1 << bits);
    hashtable->memory_size = memory_size;
    for (i = 0;i < hashtable->size;i++)
    {
    hashtable_init_slot(&hashtable->tale[i]);
    }
    hashtable->table = (hashtable_slot_t*)p;
    return 0;
    }
    return 1;
    }

    /**
    * Based on https://gist.github.com/badboy/6267743
    * I replace the 'long key' by 'unsigned key' and unsigned Java right shifts
    * by regular C/C++ right shifts
    * I adopt the hash function for 22 (PID_MAX_LIMIT) bits integers
    * I adopt the hash function for 22 (PID_MAX_LIMIT) bits integers
    */
    public u32 hash32shift(u32 key)
    {

    key = ~key + (key << 10); // key = (key << 15) - key - 1;
    key = key ^ (key >> 7);
    key = key ^ (key >> 7);
    key = key + (key << 1);
    key = key ^ (key >> 2);
    key = key * 187; // key = (key + (key << 3)) + (key << 11);
    key = key ^ (key >> 11);
    return key;
    }

    /**
    * Hash the key, get an index in the hashtable, try compare-and-set.
    * If fails (not likely) try again with the next slot (linear probing)
    @@ -147,4 +207,3 @@ static int hashtable_find(const hashtable_t *hashtable, const u32 key, void **da

    return 1;
    }

  14. @larytet larytet revised this gist Jul 6, 2017. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion kernel_hashtable.c
    View file
    Original file line number Diff line number Diff line change
    @@ -66,7 +66,7 @@ public u32 hash32shift(u32 key)
    key = key ^ (key >> 7);
    key = key + (key << 1);
    key = key ^ (key >> 2);
    key = key * 2057; // key = (key + (key << 3)) + (key << 11);
    key = key * 187; // key = (key + (key << 3)) + (key << 11);
    key = key ^ (key >> 11);
    return key;
    }
  15. @larytet larytet revised this gist Jul 6, 2017. 1 changed file with 6 additions and 5 deletions.
    11 changes: 6 additions & 5 deletions kernel_hashtable.c
    View file
    Original file line number Diff line number Diff line change
    @@ -57,16 +57,17 @@ static int hashtable_init(hashtable_t *hashtable, const size_t bits)
    * Based on https://gist.github.com/badboy/6267743
    * I replace the 'long key' by 'unsigned key' and unsigned Java right shifts
    * by regular C/C++ right shifts
    * I adopt the hash function for 22 (PID_MAX_LIMIT) bits integers
    */
    public u32 hash32shift(u32 key)
    {

    key = ~key + (key << 15); // key = (key << 15) - key - 1;
    key = key ^ (key >> 12);
    key = key + (key << 2);
    key = key ^ (key >> 4);
    key = ~key + (key << 10); // key = (key << 15) - key - 1;
    key = key ^ (key >> 7);
    key = key + (key << 1);
    key = key ^ (key >> 2);
    key = key * 2057; // key = (key + (key << 3)) + (key << 11);
    key = key ^ (key >> 16);
    key = key ^ (key >> 11);
    return key;
    }

  16. @larytet larytet revised this gist Jul 6, 2017. 1 changed file with 2 additions and 0 deletions.
    2 changes: 2 additions & 0 deletions kernel_hashtable.c
    View file
    Original file line number Diff line number Diff line change
    @@ -1,6 +1,8 @@
    /**
    * My key is a thread ID (22 bits) and my data is a chunk in the
    * FIFO orgtanised in the driver shared memory
    * Th field age is a value of the CPU cycles counter when the slot
    * is populated.
    */
    typedef struct
    {
  17. @larytet larytet revised this gist Jul 6, 2017. 1 changed file with 2 additions and 0 deletions.
    2 changes: 2 additions & 0 deletions kernel_hashtable.c
    View file
    Original file line number Diff line number Diff line change
    @@ -5,6 +5,7 @@
    typedef struct
    {
    volatile u32 key;
    u32 age;
    void *data;
    } hashtable_slot_t;

    @@ -42,6 +43,7 @@ static int hashtable_init(hashtable_t *hashtable, const size_t bits)
    {
    hashtable->tale[i].key = ILLEGAL_KEY;
    hashtable->tale[i].data = NULL;
    hashtable->tale[i].age = 0;
    }
    hashtable->table = (hashtable_slot_t*)p;
    return 0;
  18. @larytet larytet revised this gist Jul 6, 2017. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion kernel_hashtable.c
    View file
    Original file line number Diff line number Diff line change
    @@ -81,7 +81,7 @@ static int hashtable_insert(hashtable_t *hashtable, const u32 key, const void *d
    {
    u32 *slot_key = (u32*)&hashtable->table[index];
    u32 old_key = cmpxchg(slot_key, ILLEGAL_KEY, key);
    if (old_key == ILLEGAL_KEY)
    if (old_key == ILLEGAL_KEY) // Success
    {
    slot_key->data = data;
    return 0;
  19. @larytet larytet revised this gist Jul 6, 2017. 1 changed file with 13 additions and 12 deletions.
    25 changes: 13 additions & 12 deletions kernel_hashtable.c
    View file
    Original file line number Diff line number Diff line change
    @@ -54,25 +54,26 @@ static int hashtable_init(hashtable_t *hashtable, const size_t bits)
    * I replace the 'long key' by 'unsigned key' and unsigned Java right shifts
    * by regular C/C++ right shifts
    */
    public u32 hash6432shift(u64 key)
    public u32 hash32shift(u32 key)
    {
    key = (~key) + (key << 18); // key = (key << 18) - key - 1;
    key = key ^ (key >> 31);
    key = key * 21; // key = (key + (key << 2)) + (key << 4);
    key = key ^ (key >> 11);
    key = key + (key << 6);
    key = key ^ (key >> 22);
    return (u32)key;
    }

    key = ~key + (key << 15); // key = (key << 15) - key - 1;
    key = key ^ (key >> 12);
    key = key + (key << 2);
    key = key ^ (key >> 4);
    key = key * 2057; // key = (key + (key << 3)) + (key << 11);
    key = key ^ (key >> 16);
    return key;
    }

    /**
    * Hash the key, get an index in the hashtable, try compare-and-set.
    * If fails (not likely) try again with the next slot (linear probing)
    * continue until success or max_tries is hit
    */
    static int hashtable_insert(hashtable_t *hashtable, const u32 key, const void *data)
    {
    const u32 hash = hash6432shift(key);
    const u32 hash = hash32shift(key);
    const u32 index = hash & hashtable->size;
    const u32 index_max = index+HASHTABLE_MAX_TRIES; // I can do this for the last slot too - I allocated max_tries more slots
    u32 i;
    @@ -97,7 +98,7 @@ static int hashtable_insert(hashtable_t *hashtable, const u32 key, const void *d
    */
    static int hashtable_remove(hashtable_t *hashtable, const u32 key, void **data)
    {
    const u32 hash = hash6432shift(key);
    const u32 hash = hash32shift(key);
    const u32 index = hash & hashtable->size;
    const u32 index_max = index+HASHTABLE_MAX_TRIES; // I can do this for the last slot too - I allocated max_tries more slots
    u32 i;
    @@ -124,7 +125,7 @@ static int hashtable_remove(hashtable_t *hashtable, const u32 key, void **data)
    */
    static int hashtable_find(const hashtable_t *hashtable, const u32 key, void **data)
    {
    const u32 hash = hash6432shift(key);
    const u32 hash = hash32shift(key);
    const u32 index = hash & hashtable->size;
    const u32 index_max = index+HASHTABLE_MAX_TRIES; // I can do this for the last slot too - I allocated max_tries more slots
    u32 i;
  20. @larytet larytet revised this gist Jul 6, 2017. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion kernel_hashtable.c
    View file
    Original file line number Diff line number Diff line change
    @@ -27,7 +27,7 @@ static size_t hashtable_memory_size(const int bits, size_t max_tries)
    }

    static const size_t HASHTABLE_MAX_TRIES = 3;
    // Illegal TID can (PID_MAX_LIMIT+1)
    // Illegal TID can be (PID_MAX_LIMIT+1)
    static const u32 ILLEGAL_KEY = 0;
    static int hashtable_init(hashtable_t *hashtable, const size_t bits)
    {
  21. @larytet larytet revised this gist Jul 6, 2017. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion kernel_hashtable.c
    View file
    Original file line number Diff line number Diff line change
    @@ -27,7 +27,7 @@ static size_t hashtable_memory_size(const int bits, size_t max_tries)
    }

    static const size_t HASHTABLE_MAX_TRIES = 3;
    // Illegal TID can be (1<<23)
    // Illegal TID can (PID_MAX_LIMIT+1)
    static const u32 ILLEGAL_KEY = 0;
    static int hashtable_init(hashtable_t *hashtable, const size_t bits)
    {
  22. @larytet larytet revised this gist Jul 6, 2017. 1 changed file with 1 addition and 0 deletions.
    1 change: 1 addition & 0 deletions kernel_hashtable.c
    View file
    Original file line number Diff line number Diff line change
    @@ -27,6 +27,7 @@ static size_t hashtable_memory_size(const int bits, size_t max_tries)
    }

    static const size_t HASHTABLE_MAX_TRIES = 3;
    // Illegal TID can be (1<<23)
    static const u32 ILLEGAL_KEY = 0;
    static int hashtable_init(hashtable_t *hashtable, const size_t bits)
    {
  23. @larytet larytet revised this gist Jul 6, 2017. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion kernel_hashtable.c
    View file
    Original file line number Diff line number Diff line change
    @@ -1,5 +1,5 @@
    /**
    * My key is thread ID and my data is a chunk in the
    * My key is a thread ID (22 bits) and my data is a chunk in the
    * FIFO orgtanised in the driver shared memory
    */
    typedef struct
  24. @larytet larytet revised this gist Jul 6, 2017. 1 changed file with 8 additions and 3 deletions.
    11 changes: 8 additions & 3 deletions kernel_hashtable.c
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,7 @@
    /**
    * My key is thread ID and my data is a chunk in the
    * FIFO orgtanised in the driver shared memory
    */
    typedef struct
    {
    volatile u32 key;
    @@ -14,7 +18,8 @@ typedef struct

    /**
    * Calculate number of slots in the hash table
    * I add max_tries on top to ensure that there are max_tries slots in the end of the table
    * I add max_tries on top to ensure that there are max_tries slots after the
    * end of the table
    */
    static size_t hashtable_memory_size(const int bits, size_t max_tries)
    {
    @@ -45,8 +50,8 @@ static int hashtable_init(hashtable_t *hashtable, const size_t bits)

    /**
    * Based on https://gist.github.com/badboy/6267743
    * I replace the 'long key' by 'unsigned key' and unsigned Java shifts right
    * by regular C/C++ shifts right
    * I replace the 'long key' by 'unsigned key' and unsigned Java right shifts
    * by regular C/C++ right shifts
    */
    public u32 hash6432shift(u64 key)
    {
  25. @larytet larytet created this gist Jul 5, 2017.
    138 changes: 138 additions & 0 deletions kernel_hashtable.c
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,138 @@
    typedef struct
    {
    volatile u32 key;
    void *data;
    } hashtable_slot_t;

    typedef struct
    {
    size_t size;
    size_t memory_size;
    hashtable_slot_t *table;
    } hashtable_t;


    /**
    * Calculate number of slots in the hash table
    * I add max_tries on top to ensure that there are max_tries slots in the end of the table
    */
    static size_t hashtable_memory_size(const int bits, size_t max_tries)
    {
    return (sizeof(hashtable_slot_t) * ((1 << bits) + max_tries);
    }

    static const size_t HASHTABLE_MAX_TRIES = 3;
    static const u32 ILLEGAL_KEY = 0;
    static int hashtable_init(hashtable_t *hashtable, const size_t bits)
    {
    size_t memory_size = hashtable_memory_size(bits, HASHTABLE_MAX_TRIES);
    void *p = vmalloc(memory_size);
    int i;
    if (p)
    {
    hashtable->size = (1 << bits);
    hashtable->memory_size = memory_size;
    for (i = 0;i < hashtable->size;i++)
    {
    hashtable->tale[i].key = ILLEGAL_KEY;
    hashtable->tale[i].data = NULL;
    }
    hashtable->table = (hashtable_slot_t*)p;
    return 0;
    }
    return 1;
    }

    /**
    * Based on https://gist.github.com/badboy/6267743
    * I replace the 'long key' by 'unsigned key' and unsigned Java shifts right
    * by regular C/C++ shifts right
    */
    public u32 hash6432shift(u64 key)
    {
    key = (~key) + (key << 18); // key = (key << 18) - key - 1;
    key = key ^ (key >> 31);
    key = key * 21; // key = (key + (key << 2)) + (key << 4);
    key = key ^ (key >> 11);
    key = key + (key << 6);
    key = key ^ (key >> 22);
    return (u32)key;
    }

    /**
    * Hash the key, get an index in the hashtable, try compare-and-set.
    * If fails (not likely) try again with the next slot (linear probing)
    * continue until success or max_tries is hit
    */
    static int hashtable_insert(hashtable_t *hashtable, const u32 key, const void *data)
    {
    const u32 hash = hash6432shift(key);
    const u32 index = hash & hashtable->size;
    const u32 index_max = index+HASHTABLE_MAX_TRIES; // I can do this for the last slot too - I allocated max_tries more slots
    u32 i;
    for (i = index;i < index_max;i++)
    {
    u32 *slot_key = (u32*)&hashtable->table[index];
    u32 old_key = cmpxchg(slot_key, ILLEGAL_KEY, key);
    if (old_key == ILLEGAL_KEY)
    {
    slot_key->data = data;
    return 0;
    }
    }

    return 1;
    }

    /**
    * Hash the key, get an index in the hashtable, find the relevant entry,
    * read the pointer, remove using atomic operation
    * Only one context is allowed to remove a specific entry
    */
    static int hashtable_remove(hashtable_t *hashtable, const u32 key, void **data)
    {
    const u32 hash = hash6432shift(key);
    const u32 index = hash & hashtable->size;
    const u32 index_max = index+HASHTABLE_MAX_TRIES; // I can do this for the last slot too - I allocated max_tries more slots
    u32 i;
    for (i = index;i < index_max;i++)
    {
    u32 *slot_key = (u32*)&hashtable->table[index];
    u32 old_key = slot_key->key;
    if (old_key == key)
    {
    *data = slot_key->data;
    slot_key->data = NULL;
    barrier();
    slot_key->key = ILLEGAL_KEY;
    return 0;
    }
    }

    return 1;
    }

    /**
    * Hash the key, get an index in the hashtable, find the relevant entry,
    * read the pointer
    */
    static int hashtable_find(const hashtable_t *hashtable, const u32 key, void **data)
    {
    const u32 hash = hash6432shift(key);
    const u32 index = hash & hashtable->size;
    const u32 index_max = index+HASHTABLE_MAX_TRIES; // I can do this for the last slot too - I allocated max_tries more slots
    u32 i;
    for (i = index;i < index_max;i++)
    {
    u32 *slot_key = (u32*)&hashtable->table[index];
    u32 old_key = slot_key->key;
    if (old_key == key)
    {
    *data = slot_key->data;
    return 0;
    }
    }

    return 1;
    }