bsc-s2 / lua-sharedtable

Table of Content

• Name
• Status
• Description
  • Module List
• Install
• Usage
• Configuration
• Test
• Author

Name

lua-sharedtable:

lua-sharetable is a key value store table and can shared between processes.

Features:

• Table is associative array, that can be indexed not only with number but also with string.

• Table value can not only be integer, string, float, but also table reference.

• No fixed size, you can add as many elements as you want to a table dynamically. memory space is dynamic extended.

• Low memory fragment, in bottom layer, memory space split into region, pages, slab chunk. it can choose the best fit size to allocate.

• High memory allocation performance

  • memory space is occupied in init phase, but not bind physical page, so no memory use. when table use space, it just trigger page fault to bind virtual memory with physical page, so no system call to delay.

  • there are some kind of chunks in slab pool, and some kind of pages in page pool, so alloc memory to user, just to search in array or tree data structure.

• No redundant memory occupied, when free memory reach threshold, the memory will release to system through unbind virtual memory from physical page.

• No afraid process died, if process died, it's share memory will be release. even the died process hold the lock, the lock will be recovered.

Status

This library is in development phase.

It has been used in our object storage service.

Description

Module List

There is a README.md for each module.

name	description
array	dynamic and static array
atomic	atomic operation
btree	btree operation
binary	binary operation
bitmap	bitmap operation
list	double linked list operation
rbtree	red–black tree operation
robustlock	robustlock can avoid dead lock
str	string utility
region	manage system alloced big memory
pagepool	manage pages which split from region

Install

It requires gcc 4.9+ and c11 standard.

For now the latest centos still has no gcc-4.9 included. We need to install gcc-4.9 with devtoolset-3.

To install gcc 4.9 on centos:

yum install centos-release-scl-rh -y
yum install devtoolset-3-gcc -y

To use gcc-4.9 in devtoolset-3, start a new bash with devtoolset-3 enabled:

scl enable devtoolset-3 bash

To enable devtoolset-3 for ever, add the following line into .bashrc:

source /opt/rh/devtoolset-3/enable

Usage

Configuration

Contribute

Preprocessor

• st_assert(expr, fmt...): is used to detect unsolvable problems, Such as operating on a NULL pointer.

  If expr is evaluated to 0, it kills the entire process by sending a signal. A failure assert means there is severe problem happening, nothing else should be done.

  In our project we assume arguments passed in are always valid. Otherwise, there must be a programming mistake.

  Invalid input should be filtered out in upper layer.

• st_dassert(expr, fmt...): is the same as st_assert, except without debug enabled, it will be stripped.

• st_must(expr, optional_return_value): is used to check non-critical invalid input, such as:

  • freeing a NULL pointer(this is can be just ignored and return),

Code style

• Use astyle to format .c and .h source code.

  There is an astylerc that defines code style for this project.

  Usage:

  1. Using env variable to specify config file:

     export ARTISTIC_STYLE_OPTIONS=$PWD/util/astylerc
     astyle src/str/str.c
     

  2. Or copy it to home folder then astyle always use it.

     copy util/astylerc ~/.astylerc
     astyle src/str/str.c
     

Test

Author

• Zhang Yanpo (张炎泼) [email protected]
• Chen Chuang (陈闯) [email protected]
• Li Shulong (李树龙) [email protected]

lua-sharedtable's Issues

原子操作函数

回调封装,支持指定回调函数和参数

类似这样?

typedef struct {
    int rc;
    /* other */
} callback_rst_t; 

typedef struct {
    callback_rst_t (*func)(void *arg);
    void *arg;
} callback_t;

add-doc: README.md 添加项目介绍, 模块目录

makefile增加valgrind检查选项.

add: mempool: 支持自定义的内存分配.

typedef struct {
     void* (*mp_alloc)(st_mempool_t *p, size_t size);
     void* (*mp_realloc)(st_mempool_t *p, void *ptr, size_t size);
     void   (*mp_free)(st_mempool_t *p, void *ptr);
} st_mempool_t;

rbtree 增加replace函数: 直接替换一个rb节点, 前提是必须保证替换前后的节点在rbtree里相等.

refine unittest files: no more empty fmt is required

//before
st_ut_eq(32, st_bit_cnt1_before((uint32_t)(0ULL - 1), 33), "");
//now
st_ut_eq(32, st_bit_cnt1_before((uint32_t)(0ULL - 1), 33));

add share_table lua module support

增加astyle自动格式化配置.

提供一份table benchmark的报告

简单点...

需要:
测试机型 和 测试结果.

放到doc目录中作为日后参考.

slab性能测试

add-doc: src/array.md

代码规范统一

为luaapi模块添加文档

1. 删除luaapi.c中不必要的注释
   2.描述接口行为

add rbtree

编译出现 error: ‘_Generic’ specifies two compatible types

add slab_pool support

add benchmark

cd: can't cd to sharetable

BASE_DIR := $(CURDIR)
export BASE_DIR

submod = binary     \
         btree      \
         robustlock \
         list       \
         rbtree     \
         array      \
         bitmap     \
         atomic     \
         region     \
         pagepool   \
         slab       \
         table      \
         gc         \
         version    \
         sharetable

test:
    for mod in $(submod); do ( cd $$mod && $(MAKE) test; ) done

dylib:
    cd sharetable && make dylib && cd -

clean:
    for mod in $(submod); do ( cd $$mod && $(MAKE) clean; ) done

hi 我在debian系统下使用make test， 看见有

/bin/sh: 1: cd: can't cd to sharetable
Makefile:25: recipe for target 'test' failed

请问下 sharetable在哪儿呢？

基于防死锁互斥锁，实现读写锁。

添加专门处理多值编译宏的头文件

需求：
只处理可以出现多值的编译宏，-D MEM=[LOW | NORMAL]这种。
对于-D DEBUG=1这种，不需要在此头文件中处理，源文件中可以直接使用。

目标：

# cat x.c
#define mem_small 1
#define mem_normal 2

#define concat(a, b) a ## b
#define eval(x, ...) x __VA_ARGS__
#define mem_mode eval(concat, (mem_, MEM))
\\\\\\\\\\\\\\\\\\\\\\\ 以上功能代码应该放在头文件中  \\\\\\\\\\\\\\\\\\\\\\
int main(int argc, char **argv) {
#if mem_mode == mem_small
    printf("small");
#else
    printf("normal");
#endif
    return 0;
}


# gcc -E x.c -D MEM=normal


int main(int argc, char **argv) {

    printf("normal");

    return 0;
}


# gcc -E x.c -D MEM=small


int main(int argc, char **argv) {

    printf("small");

    return 0;
}

pagepool结构调整

• chunk_size 改成 obj_size, 和slab保持统一.
• union里只放1个slab. pagepool自身要用到的rbnode不放在userdata的union里.
• addr转成2个指针的union: 直接slab里面的概念.

struct st_pagepool_page_s {
    union {
        struct {
            /* store slab chunk state */
            uint64_t bitmap[ST_PAGEPOOL_MAX_SLAB_CHUNK_CNT];
            int32_t chunk_size;
            /**
             * set value when slab alloc pages from pagepool.
             * clear value when slab free pages to pagepool.
             *
             * master page: addr of slab group which it belongs to
             * slave pages: addr of master page
             *
             * Note:
             *    size of [rbnode] is smaller than [bitmap],
             *    so [addr] is fully controlled by slab
             */
            void *addr;
        } slab; /* for slab module use */

        st_rbtree_node_t rbnode; /* pool free_pages tree node
                                  * only master use */
    };

    st_list_t lnode; /* same compound_page_cnt pages list
                      * if page in tree, lnode is list's head
                      * else lnode is list's node
                      * only master use */

    uint8_t *region; /* region start address */

    int8_t state; /* page free or allocated */
    int8_t type; /* master or slave page */

    int16_t compound_page_cnt;
};

去掉rbtree中st_rbtree_search_*的函数,使用st_rbtree_search

README 需要更新一下了...

add-doc REAMD.md 添加makefile使用说明

test web hook

test

bitmap的set/clear返回值的修改独立1个pr先merge吧.

add share_table_pool support

多进程间可见共享内存分配，类mmap。

add skiplist support

gc: 避免频繁取clocktime影响性能, 通过上次执行的时间估算每次gc的步数.

array模块中编程错误的检查使用`st_assert` 替代 `st_must` 减少不必要的错误返回.

例如下面3个参数检查是不必要的, 只有编程错误会引起这些问题.

int st_array_indexof(st_array_t *array, void *element,
                     st_array_compare_f compare, ssize_t *idx) {
    st_must(array != NULL, ST_ARG_INVALID);
    st_must(array->inited == 1, ST_UNINITED);
    st_must(element != NULL, ST_ARG_INVALID);

    st_array_compare_f cmp = compare != NULL ? compare : array->compare;
    st_must(cmp != NULL, ST_ARG_INVALID);

    for (ssize_t i = 0; i < array->current_cnt; i++) {

        if (cmp(element, st_array_get(array, i)) == 0) {
            *idx = i;
            return ST_OK;
        }
    }

    return ST_NOT_FOUND;
}

add-doc: src/region.md

add string support

add gc

atomic添加测试

add pages_pool support