diff options
Diffstat (limited to 'src/fluent-bit/lib/monkey/deps')
24 files changed, 3353 insertions, 0 deletions
diff --git a/src/fluent-bit/lib/monkey/deps/deps.txt b/src/fluent-bit/lib/monkey/deps/deps.txt new file mode 100644 index 000000000..9957e6850 --- /dev/null +++ b/src/fluent-bit/lib/monkey/deps/deps.txt @@ -0,0 +1,3 @@ +1) Jemalloc v3.5.0-git-5f60afa01eb2cf7d44024d162a1ecc6cceedcca1 + + https://github.com/jemalloc/jemalloc diff --git a/src/fluent-bit/lib/monkey/deps/flb_libco/CMakeLists.txt b/src/fluent-bit/lib/monkey/deps/flb_libco/CMakeLists.txt new file mode 100644 index 000000000..1f0c55395 --- /dev/null +++ b/src/fluent-bit/lib/monkey/deps/flb_libco/CMakeLists.txt @@ -0,0 +1,28 @@ +set(src + libco.c + ) + +include(CheckSymbolExists) + +# Check for posix_memalign so that Apple Silicon can be supported +check_symbol_exists(posix_memalign "stdlib.h" HAVE_POSIX_MEMALIGN_IN_STDLIB) + +IF(HAVE_POSIX_MEMALIGN_IN_STDLIB) + # We need HAVE_POSIX_MEMALIGN for the ifdefs to use posix_memalign + # We defined HAVE_POSIX_MEMALIGN_IN_STDLIB in order to avoid including in malloc.h + add_definitions(-DHAVE_POSIX_MEMALIGN_IN_STDLIB -DHAVE_POSIX_MEMALIGN) + MESSAGE("Found posix_memalign in stdlib.h -DHAVE_POSIX_MEMALIGN_IN_STDLIB -DHAVE_POSIX_MEMALIGN") +ENDIF(HAVE_POSIX_MEMALIGN_IN_STDLIB) + +# Check for posix_memalign so that FreeBSD can be supported +check_symbol_exists(posix_memalign "malloc_np.h" HAVE_POSIX_MEMALIGN_IN_PTHREAD_NP) + +IF(HAVE_POSIX_MEMALIGN_IN_PTHREAD_NP) + # We need HAVE_POSIX_MEMALIGN for the ifdefs to use posix_memalign + # We defined DHAVE_POSIX_MEMALIGN_IN_PTHREAD_NP in order to include malloc_np.h + add_definitions(-DHAVE_POSIX_MEMALIGN_IN_PTHREAD_NP -DHAVE_POSIX_MEMALIGN) + MESSAGE("Found posix_memalign in malloc_np.h -DHAVE_POSIX_MEMALIGN_IN_PTHREAD_NP -DHAVE_POSIX_MEMALIGN") +ENDIF(HAVE_POSIX_MEMALIGN_IN_PTHREAD_NP) + +add_definitions(-DLIBCO_MP) +add_library(co STATIC ${src}) diff --git a/src/fluent-bit/lib/monkey/deps/flb_libco/README.md b/src/fluent-bit/lib/monkey/deps/flb_libco/README.md new file mode 100644 index 000000000..4d934d740 --- /dev/null +++ b/src/fluent-bit/lib/monkey/deps/flb_libco/README.md @@ -0,0 +1,14 @@ +# Fork of libco for Fluent Bit + +This repository is a fork of the original library [libco](https://byuu.org/library/libco/) v18 created by Byuu. Compared to the original version it have the following changes: + +- Core + - ARMv8: workaround for [GCC bug](https://gcc.gnu.org/bugzilla/show_bug.cgi?id=90907). + - Added [aarch64.c](aarch64.c) backend file created by [webgeek1234](https://github.com/webgeek1234). + - Fixes on settings.h to get MacOS support. +- API + - co_create() have a third argument to retrieve the real size of the stack created. + +This library is used inside [Fluent Bit](http://github.com/fluent/fluent-bit) project, so this repo aims to keep aligned with latest releases but including our required patches. + +Eduardo Silva <eduardo@monkey.io> diff --git a/src/fluent-bit/lib/monkey/deps/flb_libco/aarch64.c b/src/fluent-bit/lib/monkey/deps/flb_libco/aarch64.c new file mode 100644 index 000000000..d01b2ca00 --- /dev/null +++ b/src/fluent-bit/lib/monkey/deps/flb_libco/aarch64.c @@ -0,0 +1,138 @@ +/* + libco.aarch64 (2017-06-26) + author: webgeek1234 + license: public domain +*/ + +#define LIBCO_C +#include "libco.h" +#include "settings.h" +#include <assert.h> +#include <stdlib.h> +#include <string.h> +#include <stdint.h> + +#if defined(HAVE_POSIX_MEMALIGN_IN_STDLIB) +/* stdlib is already included */ +#elif defined(HAVE_POSIX_MEMALIGN_IN_PTHREAD_NP) +#include <malloc_np.h> +#else +#include <malloc.h> +#endif + +#ifdef __cplusplus +extern "C" { +#endif + +static thread_local uint64_t co_active_buffer[64]; +static thread_local cothread_t co_active_handle; + +asm ( + ".text\n" + ".globl co_switch_aarch64\n" + ".globl _co_switch_aarch64\n" + "co_switch_aarch64:\n" + "_co_switch_aarch64:\n" + " stp x8, x9, [x1]\n" + " stp x10, x11, [x1, #16]\n" + " stp x12, x13, [x1, #32]\n" + " stp x14, x15, [x1, #48]\n" + " str x19, [x1, #72]\n" + " stp x20, x21, [x1, #80]\n" + " stp x22, x23, [x1, #96]\n" + " stp x24, x25, [x1, #112]\n" + " stp x26, x27, [x1, #128]\n" + " stp x28, x29, [x1, #144]\n" + " mov x16, sp\n" + " stp x16, x30, [x1, #160]\n" + + " ldp x8, x9, [x0]\n" + " ldp x10, x11, [x0, #16]\n" + " ldp x12, x13, [x0, #32]\n" + " ldp x14, x15, [x0, #48]\n" + " ldr x19, [x0, #72]\n" + " ldp x20, x21, [x0, #80]\n" + " ldp x22, x23, [x0, #96]\n" + " ldp x24, x25, [x0, #112]\n" + " ldp x26, x27, [x0, #128]\n" + " ldp x28, x29, [x0, #144]\n" + " ldp x16, x17, [x0, #160]\n" + " mov sp, x16\n" + " br x17\n" + ".previous\n" + ); + +/* ASM */ +void co_switch_aarch64(cothread_t handle, cothread_t current); + +static void crash(void) +{ + /* Called only if cothread_t entrypoint returns. */ + assert(0); +} + +cothread_t co_create(unsigned int size, void (*entrypoint)(void), + size_t *out_size) +{ + size = (size + 1023) & ~1023; + cothread_t handle = 0; +#if HAVE_POSIX_MEMALIGN >= 1 + if (posix_memalign(&handle, 1024, size + 512) < 0) + return 0; +#else + handle = memalign(1024, size + 512); +#endif + + if (!handle) + return handle; + + uint64_t *ptr = (uint64_t*)handle; + /* Non-volatiles. */ + ptr[0] = 0; /* x8 */ + ptr[1] = 0; /* x9 */ + ptr[2] = 0; /* x10 */ + ptr[3] = 0; /* x11 */ + ptr[4] = 0; /* x12 */ + ptr[5] = 0; /* x13 */ + ptr[6] = 0; /* x14 */ + ptr[7] = 0; /* x15 */ + ptr[8] = 0; /* padding */ + ptr[9] = 0; /* x19 */ + ptr[10] = 0; /* x20 */ + ptr[11] = 0; /* x21 */ + ptr[12] = 0; /* x22 */ + ptr[13] = 0; /* x23 */ + ptr[14] = 0; /* x24 */ + ptr[15] = 0; /* x25 */ + ptr[16] = 0; /* x26 */ + ptr[17] = 0; /* x27 */ + ptr[18] = 0; /* x28 */ + ptr[20] = (uintptr_t)ptr + size + 512 - 16; /* x30, stack pointer */ + ptr[19] = ptr[20]; /* x29, frame pointer */ + ptr[21] = (uintptr_t)entrypoint; /* PC (link register x31 gets saved here). */ + + *out_size = size + 512; + return handle; +} + +cothread_t co_active(void) +{ + if (!co_active_handle) + co_active_handle = co_active_buffer; + return co_active_handle; +} + +void co_delete(cothread_t handle) +{ + free(handle); +} + +void co_switch(cothread_t handle) +{ + cothread_t co_previous_handle = co_active(); + co_switch_aarch64(co_active_handle = handle, co_previous_handle); +} + +#ifdef __cplusplus +} +#endif diff --git a/src/fluent-bit/lib/monkey/deps/flb_libco/amd64.c b/src/fluent-bit/lib/monkey/deps/flb_libco/amd64.c new file mode 100644 index 000000000..ae127e80c --- /dev/null +++ b/src/fluent-bit/lib/monkey/deps/flb_libco/amd64.c @@ -0,0 +1,163 @@ +/* + libco.amd64 (2016-09-14) + author: byuu + license: public domain +*/ + +#define LIBCO_C +#include "libco.h" +#include "settings.h" + +#include <assert.h> +#include <stdlib.h> + +#ifdef __cplusplus +extern "C" { +#endif + +static thread_local long long co_active_buffer[64]; +static thread_local cothread_t co_active_handle = 0; +static void (*co_swap)(cothread_t, cothread_t) = 0; + +#ifdef LIBCO_MPROTECT + alignas(4096) +#else + text_section +#endif +#ifdef _WIN32 + /* ABI: Win64 */ + static const unsigned char co_swap_function[4096] = { + 0x48, 0x89, 0x22, /* mov [rdx],rsp */ + 0x48, 0x8b, 0x21, /* mov rsp,[rcx] */ + 0x58, /* pop rax */ + 0x48, 0x89, 0x6a, 0x08, /* mov [rdx+ 8],rbp */ + 0x48, 0x89, 0x72, 0x10, /* mov [rdx+16],rsi */ + 0x48, 0x89, 0x7a, 0x18, /* mov [rdx+24],rdi */ + 0x48, 0x89, 0x5a, 0x20, /* mov [rdx+32],rbx */ + 0x4c, 0x89, 0x62, 0x28, /* mov [rdx+40],r12 */ + 0x4c, 0x89, 0x6a, 0x30, /* mov [rdx+48],r13 */ + 0x4c, 0x89, 0x72, 0x38, /* mov [rdx+56],r14 */ + 0x4c, 0x89, 0x7a, 0x40, /* mov [rdx+64],r15 */ + #if !defined(LIBCO_NO_SSE) + 0x0f, 0x29, 0x72, 0x50, /* movaps [rdx+ 80],xmm6 */ + 0x0f, 0x29, 0x7a, 0x60, /* movaps [rdx+ 96],xmm7 */ + 0x44, 0x0f, 0x29, 0x42, 0x70, /* movaps [rdx+112],xmm8 */ + 0x48, 0x83, 0xc2, 0x70, /* add rdx,112 */ + 0x44, 0x0f, 0x29, 0x4a, 0x10, /* movaps [rdx+ 16],xmm9 */ + 0x44, 0x0f, 0x29, 0x52, 0x20, /* movaps [rdx+ 32],xmm10 */ + 0x44, 0x0f, 0x29, 0x5a, 0x30, /* movaps [rdx+ 48],xmm11 */ + 0x44, 0x0f, 0x29, 0x62, 0x40, /* movaps [rdx+ 64],xmm12 */ + 0x44, 0x0f, 0x29, 0x6a, 0x50, /* movaps [rdx+ 80],xmm13 */ + 0x44, 0x0f, 0x29, 0x72, 0x60, /* movaps [rdx+ 96],xmm14 */ + 0x44, 0x0f, 0x29, 0x7a, 0x70, /* movaps [rdx+112],xmm15 */ + #endif + 0x48, 0x8b, 0x69, 0x08, /* mov rbp,[rcx+ 8] */ + 0x48, 0x8b, 0x71, 0x10, /* mov rsi,[rcx+16] */ + 0x48, 0x8b, 0x79, 0x18, /* mov rdi,[rcx+24] */ + 0x48, 0x8b, 0x59, 0x20, /* mov rbx,[rcx+32] */ + 0x4c, 0x8b, 0x61, 0x28, /* mov r12,[rcx+40] */ + 0x4c, 0x8b, 0x69, 0x30, /* mov r13,[rcx+48] */ + 0x4c, 0x8b, 0x71, 0x38, /* mov r14,[rcx+56] */ + 0x4c, 0x8b, 0x79, 0x40, /* mov r15,[rcx+64] */ + #if !defined(LIBCO_NO_SSE) + 0x0f, 0x28, 0x71, 0x50, /* movaps xmm6, [rcx+ 80] */ + 0x0f, 0x28, 0x79, 0x60, /* movaps xmm7, [rcx+ 96] */ + 0x44, 0x0f, 0x28, 0x41, 0x70, /* movaps xmm8, [rcx+112] */ + 0x48, 0x83, 0xc1, 0x70, /* add rcx,112 */ + 0x44, 0x0f, 0x28, 0x49, 0x10, /* movaps xmm9, [rcx+ 16] */ + 0x44, 0x0f, 0x28, 0x51, 0x20, /* movaps xmm10,[rcx+ 32] */ + 0x44, 0x0f, 0x28, 0x59, 0x30, /* movaps xmm11,[rcx+ 48] */ + 0x44, 0x0f, 0x28, 0x61, 0x40, /* movaps xmm12,[rcx+ 64] */ + 0x44, 0x0f, 0x28, 0x69, 0x50, /* movaps xmm13,[rcx+ 80] */ + 0x44, 0x0f, 0x28, 0x71, 0x60, /* movaps xmm14,[rcx+ 96] */ + 0x44, 0x0f, 0x28, 0x79, 0x70, /* movaps xmm15,[rcx+112] */ + #endif + 0xff, 0xe0, /* jmp rax */ + }; + + #include <windows.h> + + static void co_init() { + #ifdef LIBCO_MPROTECT + DWORD old_privileges; + VirtualProtect((void*)co_swap_function, sizeof co_swap_function, PAGE_EXECUTE_READ, &old_privileges); + #endif + } +#else + /* ABI: SystemV */ + static const unsigned char co_swap_function[4096] = { + 0x48, 0x89, 0x26, /* mov [rsi],rsp */ + 0x48, 0x8b, 0x27, /* mov rsp,[rdi] */ + 0x58, /* pop rax */ + 0x48, 0x89, 0x6e, 0x08, /* mov [rsi+ 8],rbp */ + 0x48, 0x89, 0x5e, 0x10, /* mov [rsi+16],rbx */ + 0x4c, 0x89, 0x66, 0x18, /* mov [rsi+24],r12 */ + 0x4c, 0x89, 0x6e, 0x20, /* mov [rsi+32],r13 */ + 0x4c, 0x89, 0x76, 0x28, /* mov [rsi+40],r14 */ + 0x4c, 0x89, 0x7e, 0x30, /* mov [rsi+48],r15 */ + 0x48, 0x8b, 0x6f, 0x08, /* mov rbp,[rdi+ 8] */ + 0x48, 0x8b, 0x5f, 0x10, /* mov rbx,[rdi+16] */ + 0x4c, 0x8b, 0x67, 0x18, /* mov r12,[rdi+24] */ + 0x4c, 0x8b, 0x6f, 0x20, /* mov r13,[rdi+32] */ + 0x4c, 0x8b, 0x77, 0x28, /* mov r14,[rdi+40] */ + 0x4c, 0x8b, 0x7f, 0x30, /* mov r15,[rdi+48] */ + 0xff, 0xe0, /* jmp rax */ + }; + + #include <unistd.h> + #include <sys/mman.h> + + static void co_init() { + #ifdef LIBCO_MPROTECT + unsigned long long addr = (unsigned long long)co_swap_function; + unsigned long long base = addr - (addr % sysconf(_SC_PAGESIZE)); + unsigned long long size = (addr - base) + sizeof co_swap_function; + mprotect((void*)base, size, PROT_READ | PROT_EXEC); + #endif + } +#endif + +static void crash() { + assert(0); /* called only if cothread_t entrypoint returns */ +} + +cothread_t co_active() { + if(!co_active_handle) co_active_handle = &co_active_buffer; + return co_active_handle; +} + +cothread_t co_create(unsigned int size, void (*entrypoint)(void), + size_t *out_size){ + cothread_t handle; + if(!co_swap) { + co_init(); + co_swap = (void (*)(cothread_t, cothread_t))co_swap_function; + } + + if(!co_active_handle) co_active_handle = &co_active_buffer; + size += 512; /* allocate additional space for storage */ + size &= ~15; /* align stack to 16-byte boundary */ + *out_size = size; + + if((handle = (cothread_t)malloc(size))) { + long long *p = (long long*)((char*)handle + size); /* seek to top of stack */ + *--p = (long long)crash; /* crash if entrypoint returns */ + *--p = (long long)entrypoint; /* start of function */ + *(long long*)handle = (long long)p; /* stack pointer */ + } + + return handle; +} + +void co_delete(cothread_t handle) { + free(handle); +} + +void co_switch(cothread_t handle) { + register cothread_t co_previous_handle = co_active_handle; + co_swap(co_active_handle = handle, co_previous_handle); +} + +#ifdef __cplusplus +} +#endif diff --git a/src/fluent-bit/lib/monkey/deps/flb_libco/arm.c b/src/fluent-bit/lib/monkey/deps/flb_libco/arm.c new file mode 100644 index 000000000..1bd8c043d --- /dev/null +++ b/src/fluent-bit/lib/monkey/deps/flb_libco/arm.c @@ -0,0 +1,81 @@ +/* + libco.arm (2016-09-14) + author: byuu + license: public domain +*/ + +#define LIBCO_C +#include "libco.h" +#include "settings.h" + +#include <assert.h> +#include <stdlib.h> +#include <unistd.h> +#include <sys/mman.h> + +#ifdef __cplusplus +extern "C" { +#endif + +static thread_local unsigned long co_active_buffer[64]; +static thread_local cothread_t co_active_handle = 0; +static void (*co_swap)(cothread_t, cothread_t) = 0; + +#ifdef LIBCO_MPROTECT + alignas(4096) +#else + text_section +#endif +static const unsigned long co_swap_function[1024] = { + 0xe8a16ff0, /* stmia r1!, {r4-r11,sp,lr} */ + 0xe8b0aff0, /* ldmia r0!, {r4-r11,sp,pc} */ + 0xe12fff1e, /* bx lr */ +}; + +static void co_init() { + #ifdef LIBCO_MPROTECT + unsigned long addr = (unsigned long)co_swap_function; + unsigned long base = addr - (addr % sysconf(_SC_PAGESIZE)); + unsigned long size = (addr - base) + sizeof co_swap_function; + mprotect((void*)base, size, PROT_READ | PROT_EXEC); + #endif +} + +cothread_t co_active() { + if(!co_active_handle) co_active_handle = &co_active_buffer; + return co_active_handle; +} + +cothread_t co_create(unsigned int size, void (*entrypoint)(void), + size_t *out_size) { + unsigned long* handle = 0; + if(!co_swap) { + co_init(); + co_swap = (void (*)(cothread_t, cothread_t))co_swap_function; + } + if(!co_active_handle) co_active_handle = &co_active_buffer; + size += 256; + size &= ~15; + *out_size = size; + + if(handle = (unsigned long*)malloc(size)) { + unsigned long* p = (unsigned long*)((unsigned char*)handle + size); + handle[8] = (unsigned long)p; + handle[9] = (unsigned long)entrypoint; + } + + return handle; +} + +void co_delete(cothread_t handle) { + free(handle); +} + +void co_switch(cothread_t handle) { + cothread_t co_previous_handle = co_active_handle; + co_swap(co_active_handle = handle, co_previous_handle); +} + +#ifdef __cplusplus +} +#endif diff --git a/src/fluent-bit/lib/monkey/deps/flb_libco/doc/style.css b/src/fluent-bit/lib/monkey/deps/flb_libco/doc/style.css new file mode 100755 index 000000000..5181afde6 --- /dev/null +++ b/src/fluent-bit/lib/monkey/deps/flb_libco/doc/style.css @@ -0,0 +1,8 @@ +body { + background: #333; + color: #fff; +} + +code { + background: #444; +} diff --git a/src/fluent-bit/lib/monkey/deps/flb_libco/doc/targets.html b/src/fluent-bit/lib/monkey/deps/flb_libco/doc/targets.html new file mode 100755 index 000000000..d6211a15d --- /dev/null +++ b/src/fluent-bit/lib/monkey/deps/flb_libco/doc/targets.html @@ -0,0 +1,89 @@ +<html> +<head> + <title></title> + <link href="style.css" rel="stylesheet" type="text/css"> +</head> +<body> + +<b>Supported targets:</b><br/><br/> + +Note that supported targets are only those that have been tested and confirmed +working. It is quite possible that libco will work on more processors, compilers +and operating systems than those listed below. +<hr/> + +<b>libco.x86</b><br/> +Overhead: ~5x<br/> +Supported processor(s): 32-bit x86<br/> +Supported compiler(s): any<br/> +Supported operating system(s):<ul> +<li>Windows</li> +<li>Mac OS X</li> +<li>Linux</li> +<li>BSD</li> +</ul> +<hr/> + +<b>libco.amd64</b><br/> +Overhead: ~10x (Windows), ~6x (all other platforms)<br/> +Supported processor(s): 64-bit amd64<br/> +Supported compiler(s): any<br/> +Supported operating system(s):<ul> +<li>Windows</li> +<li>Mac OS X</li> +<li>Linux</li> +<li>BSD</li> +</ul> +<hr/> + +<b>libco.ppc</b><br/> +Overhead: ~20x<br/> +Supported processor(s): 32-bit PowerPC, 64-bit PowerPC<br/> +Supported compiler(s): GNU GCC<br/> +Supported operating system(s):<ul> +</ul> +<li>Mac OS X</li> +<li>Linux</li> +<li>BSD</li> +<li>Playstation 3</li> +</ul> +<br/> + +Note: this module contains compiler flags to enable/disable FPU and Altivec +support. + +<hr/> + +<b>libco.fiber</b><br/> +Overhead: ~15x<br/> +Supported processor(s): Processor independent<br/> +Supported compiler(s): any<br/> +Supported operating system(s):<ul> +<li>Windows</li> +</ul> +<hr/> + +<b>libco.sjlj</b><br/> +Overhead: ~30x<br/> +Supported processor(s): Processor independent<br/> +Supported compiler(s): any<br/> +Supported operating system(s):<ul> +<li>Mac OS X</li> +<li>Linux</li> +<li>BSD</li> +<li>Solaris</li> +</ul> +<hr/> + +<b>libco.ucontext</b><br/> +Overhead: <b><font color="#ff0000">~300x</font></b><br/> +Supported processor(s): Processor independent<br/> +Supported compiler(s): any<br/> +Supported operating system(s):<ul> +<li>Linux</li> +<li>BSD</li> +</ul> +<hr/> + +</body> +</html> diff --git a/src/fluent-bit/lib/monkey/deps/flb_libco/doc/usage.html b/src/fluent-bit/lib/monkey/deps/flb_libco/doc/usage.html new file mode 100755 index 000000000..3f0d81ccd --- /dev/null +++ b/src/fluent-bit/lib/monkey/deps/flb_libco/doc/usage.html @@ -0,0 +1,107 @@ +<html> +<head> + <title></title> + <link href="style.css" rel="stylesheet" type="text/css"> +</head> +<body> + +<b>License:</b><br/><br/> +libco is released to the public domain. +<hr/> + +<b>Contact:</b><br/><br/> +At present, you may contact me at setsunakun0 at hotmail dot com.<br/> +I am interested in knowing of any projects that make use of this library, +though this is only a courtesy. +<hr/> + +<b>Foreword:</b><br/><br/> +libco is a cross-platform, public domain implementation of +cooperative-multithreading; a feature that is sorely lacking +from the ISO C/C++ standard.<br/> +The library is designed for maximum speed and portability, and +not for safety or features. If safety or extra functionality is desired, +a wrapper API can easily be written to encapsulate all library functions.<br/> +Behavior of executing operations that are listed as not permitted +below result in undefined behavior. They may work anyway, they +may cause undesired / unknown behavior, or they may crash the +program entirely.<br/> +The goal of this library was to simplify the base API as much as possible, +implementing only that which cannot be implemented using pure C. Additional +functionality after this would only complicate ports of this library to new +platforms. +<hr/> + +<b>Porting:</b><br/><br/> +This document is included as a reference for porting libco. Please submit any +ports you create to me, so that libco can become more useful. Please note that +since libco is public domain, you must submit your code as a work of the +public domain in order for it to be included in the official distribution. +Full credit will be given in the source code of the official release. Please +do not bother submitting code to me under any other license -- including GPL, +LGPL, BSD or CC -- I am not interested in creating a library with multiple +different licenses depending on which targets are used. +<hr/> + +<b>Synopsis:</b><br/><br/> +<code> +typedef void* cothread_t;<br/> +<br/> +cothread_t co_active();<br/> +cothread_t co_create(unsigned int heapsize, void (*coentry)(void));<br/> +void co_delete(cothread_t cothread);<br/> +void co_switch(cothread_t cothread);<br/> +</code> +<hr/> + +<b>Usage:</b> +<hr/> + +<code>typedef void* cothread_t;</code><br/><br/> +Handle to cothread.<br/> +Handle must be of type void*.<br/> +A value of null (0) indicates an uninitialized or invalid +handle, whereas a non-zero value indicates a valid handle. +<hr/> + +<code>cothread_t co_active();</code><br/><br/> +Return handle to current cothread. Always returns a valid handle, even when +called from the main program thread. +<hr/> + +<code>cothread_t co_create(unsigned int heapsize, void (*coentry)(void));</code><br/><br/> +Create new cothread.<br/> +Heapsize is the amount of memory allocated for the cothread stack, specified +in bytes. This is unfortunately impossible to make fully portable. It is +recommended to specify sizes using `n * sizeof(void*)'. It is better to err +on the side of caution and allocate more memory than will be needed to ensure +compatibility with other platforms, within reason. A typical heapsize for a +32-bit architecture is ~1MB.<br/> +When the new cothread is first called, program execution jumps to coentry. +This function does not take any arguments, due to portability issues with +passing function arguments. However, arguments can be simulated by the use +of global variables, which can be set before the first call to each cothread.<br/> +coentry() must not return, and should end with an appropriate co_switch() +statement. Behavior is undefined if entry point returns normally.<br/> +Library is responsible for allocating cothread stack memory, to free +the user from needing to allocate special memory capable of being used +as program stack memory on platforms where this is required.<br/> +User is always responsible for deleting cothreads with co_delete().<br/> +Return value of null (0) indicates cothread creation failed. +<hr/> + +<code>void co_delete(cothread_t cothread);</code><br/><br/> +Delete specified cothread.<br/> +Null (0) or invalid cothread handle is not allowed.<br/> +Passing handle of active cothread to this function is not allowed.<br/> +Passing handle of primary cothread is not allowed. +<hr/> + +<code>void co_switch(cothread_t cothread);</code><br/><br/> +Switch to specified cothread.<br/> +Null (0) or invalid cothread handle is not allowed.<br/> +Passing handle of active cothread to this function is not allowed. +<hr/> + +</body> +</html> diff --git a/src/fluent-bit/lib/monkey/deps/flb_libco/fiber.c b/src/fluent-bit/lib/monkey/deps/flb_libco/fiber.c new file mode 100644 index 000000000..f91b912b7 --- /dev/null +++ b/src/fluent-bit/lib/monkey/deps/flb_libco/fiber.c @@ -0,0 +1,54 @@ +/* + libco.win (2008-01-28) + authors: Nach, byuu + license: public domain +*/ + +#define LIBCO_C +#include "libco.h" +#include "settings.h" + +#define WINVER 0x0400 +#define _WIN32_WINNT 0x0400 +#include <windows.h> + +#ifdef __cplusplus +extern "C" { +#endif + +static thread_local cothread_t co_active_ = 0; + +static void __stdcall co_thunk(void* coentry) { + ((void (*)(void))coentry)(); +} + +cothread_t co_active() { + if(!co_active_) { + ConvertThreadToFiber(0); + co_active_ = GetCurrentFiber(); + } + return co_active_; +} + +cothread_t co_create(unsigned int heapsize, void (*coentry)(void), + size_t *out_size) { + if(!co_active_) { + ConvertThreadToFiber(0); + co_active_ = GetCurrentFiber(); + } + *out_size = heapsize; + return (cothread_t)CreateFiber(heapsize, co_thunk, (void*)coentry); +} + +void co_delete(cothread_t cothread) { + DeleteFiber(cothread); +} + +void co_switch(cothread_t cothread) { + co_active_ = cothread; + SwitchToFiber(cothread); +} + +#ifdef __cplusplus +} +#endif diff --git a/src/fluent-bit/lib/monkey/deps/flb_libco/libco.c b/src/fluent-bit/lib/monkey/deps/flb_libco/libco.c new file mode 100644 index 000000000..e0101d238 --- /dev/null +++ b/src/fluent-bit/lib/monkey/deps/flb_libco/libco.c @@ -0,0 +1,37 @@ +/* + libco + license: public domain +*/ + +#if defined(__clang__) + #pragma clang diagnostic ignored "-Wparentheses" +#endif + +#if defined(__clang__) || defined(__GNUC__) + #if defined(__i386__) + #include "x86.c" + #elif defined(__amd64__) + #include "amd64.c" + #elif defined(__arm__) + #include "arm.c" + #elif defined(__aarch64__) + #include "aarch64.c" + #elif defined(_ARCH_PPC) + #include "ppc.c" + #elif defined(_WIN32) + #include "fiber.c" + #else + #include "sjlj.c" + #endif +#elif defined(_MSC_VER) + #if defined(_M_IX86) + #include "x86.c" +// Commented out due to SIGSEGV bug +// #elif defined(_M_AMD64) +// #include "amd64.c" + #else + #include "fiber.c" + #endif +#else + #error "libco: unsupported processor, compiler or operating system" +#endif diff --git a/src/fluent-bit/lib/monkey/deps/flb_libco/libco.h b/src/fluent-bit/lib/monkey/deps/flb_libco/libco.h new file mode 100644 index 000000000..f2e2487aa --- /dev/null +++ b/src/fluent-bit/lib/monkey/deps/flb_libco/libco.h @@ -0,0 +1,28 @@ +/* + libco v18 (2016-09-14) + author: byuu + license: public domain +*/ + +#ifndef LIBCO_H +#define LIBCO_H + +#include <stddef.h> + +#ifdef __cplusplus +extern "C" { +#endif + +typedef void* cothread_t; + +cothread_t co_active(); +cothread_t co_create(unsigned int, void (*)(void), size_t *); +void co_delete(cothread_t); +void co_switch(cothread_t); + +#ifdef __cplusplus +} +#endif + +/* ifndef LIBCO_H */ +#endif diff --git a/src/fluent-bit/lib/monkey/deps/flb_libco/ppc.c b/src/fluent-bit/lib/monkey/deps/flb_libco/ppc.c new file mode 100644 index 000000000..533256b34 --- /dev/null +++ b/src/fluent-bit/lib/monkey/deps/flb_libco/ppc.c @@ -0,0 +1,369 @@ +/* + libco.ppc (2016-09-14) + author: blargg + license: public domain +*/ + +#define LIBCO_C +#include "libco.h" +#include "settings.h" + +#include <stdlib.h> +#include <stdint.h> +#include <string.h> + +#if LIBCO_MPROTECT + #include <unistd.h> + #include <sys/mman.h> +#endif + +/* state format (offsets in 32-bit words) + + +0 pointer to swap code + rest of function descriptor for entry function + +8 PC ++10 SP + special registers + GPRs + FPRs + VRs + stack +*/ + +enum { state_size = 1024 }; +enum { above_stack = 2048 }; +enum { stack_align = 256 }; + +static thread_local cothread_t co_active_handle = 0; + +/* determine environment */ + +#define LIBCO_PPC64 (_ARCH_PPC64 || __PPC64__ || __ppc64__ || __powerpc64__) + +/* whether function calls are indirect through a descriptor, or are directly to function */ +#ifndef LIBCO_PPCDESC + #if !_CALL_SYSV && (_CALL_AIX || _CALL_AIXDESC || LIBCO_PPC64) + #define LIBCO_PPCDESC 1 + #endif +#endif + +#ifdef LIBCO_MPROTECT + alignas(4096) +#else + text_section +#endif +static const uint32_t libco_ppc_code[1024] = { + #if LIBCO_PPC64 + 0x7d000026, /* mfcr r8 */ + 0xf8240028, /* std r1,40(r4) */ + 0x7d2802a6, /* mflr r9 */ + 0xf9c40048, /* std r14,72(r4) */ + 0xf9e40050, /* std r15,80(r4) */ + 0xfa040058, /* std r16,88(r4) */ + 0xfa240060, /* std r17,96(r4) */ + 0xfa440068, /* std r18,104(r4) */ + 0xfa640070, /* std r19,112(r4) */ + 0xfa840078, /* std r20,120(r4) */ + 0xfaa40080, /* std r21,128(r4) */ + 0xfac40088, /* std r22,136(r4) */ + 0xfae40090, /* std r23,144(r4) */ + 0xfb040098, /* std r24,152(r4) */ + 0xfb2400a0, /* std r25,160(r4) */ + 0xfb4400a8, /* std r26,168(r4) */ + 0xfb6400b0, /* std r27,176(r4) */ + 0xfb8400b8, /* std r28,184(r4) */ + 0xfba400c0, /* std r29,192(r4) */ + 0xfbc400c8, /* std r30,200(r4) */ + 0xfbe400d0, /* std r31,208(r4) */ + 0xf9240020, /* std r9,32(r4) */ + 0xe8e30020, /* ld r7,32(r3) */ + 0xe8230028, /* ld r1,40(r3) */ + 0x48000009, /* bl 1 */ + 0x7fe00008, /* trap */ + 0x91040030, /*1:stw r8,48(r4) */ + 0x80c30030, /* lwz r6,48(r3) */ + 0x7ce903a6, /* mtctr r7 */ + 0xe9c30048, /* ld r14,72(r3) */ + 0xe9e30050, /* ld r15,80(r3) */ + 0xea030058, /* ld r16,88(r3) */ + 0xea230060, /* ld r17,96(r3) */ + 0xea430068, /* ld r18,104(r3) */ + 0xea630070, /* ld r19,112(r3) */ + 0xea830078, /* ld r20,120(r3) */ + 0xeaa30080, /* ld r21,128(r3) */ + 0xeac30088, /* ld r22,136(r3) */ + 0xeae30090, /* ld r23,144(r3) */ + 0xeb030098, /* ld r24,152(r3) */ + 0xeb2300a0, /* ld r25,160(r3) */ + 0xeb4300a8, /* ld r26,168(r3) */ + 0xeb6300b0, /* ld r27,176(r3) */ + 0xeb8300b8, /* ld r28,184(r3) */ + 0xeba300c0, /* ld r29,192(r3) */ + 0xebc300c8, /* ld r30,200(r3) */ + 0xebe300d0, /* ld r31,208(r3) */ + 0x7ccff120, /* mtcr r6 */ + #else + 0x7d000026, /* mfcr r8 */ + 0x90240028, /* stw r1,40(r4) */ + 0x7d2802a6, /* mflr r9 */ + 0x91a4003c, /* stw r13,60(r4) */ + 0x91c40040, /* stw r14,64(r4) */ + 0x91e40044, /* stw r15,68(r4) */ + 0x92040048, /* stw r16,72(r4) */ + 0x9224004c, /* stw r17,76(r4) */ + 0x92440050, /* stw r18,80(r4) */ + 0x92640054, /* stw r19,84(r4) */ + 0x92840058, /* stw r20,88(r4) */ + 0x92a4005c, /* stw r21,92(r4) */ + 0x92c40060, /* stw r22,96(r4) */ + 0x92e40064, /* stw r23,100(r4) */ + 0x93040068, /* stw r24,104(r4) */ + 0x9324006c, /* stw r25,108(r4) */ + 0x93440070, /* stw r26,112(r4) */ + 0x93640074, /* stw r27,116(r4) */ + 0x93840078, /* stw r28,120(r4) */ + 0x93a4007c, /* stw r29,124(r4) */ + 0x93c40080, /* stw r30,128(r4) */ + 0x93e40084, /* stw r31,132(r4) */ + 0x91240020, /* stw r9,32(r4) */ + 0x80e30020, /* lwz r7,32(r3) */ + 0x80230028, /* lwz r1,40(r3) */ + 0x48000009, /* bl 1 */ + 0x7fe00008, /* trap */ + 0x91040030, /*1:stw r8,48(r4) */ + 0x80c30030, /* lwz r6,48(r3) */ + 0x7ce903a6, /* mtctr r7 */ + 0x81a3003c, /* lwz r13,60(r3) */ + 0x81c30040, /* lwz r14,64(r3) */ + 0x81e30044, /* lwz r15,68(r3) */ + 0x82030048, /* lwz r16,72(r3) */ + 0x8223004c, /* lwz r17,76(r3) */ + 0x82430050, /* lwz r18,80(r3) */ + 0x82630054, /* lwz r19,84(r3) */ + 0x82830058, /* lwz r20,88(r3) */ + 0x82a3005c, /* lwz r21,92(r3) */ + 0x82c30060, /* lwz r22,96(r3) */ + 0x82e30064, /* lwz r23,100(r3) */ + 0x83030068, /* lwz r24,104(r3) */ + 0x8323006c, /* lwz r25,108(r3) */ + 0x83430070, /* lwz r26,112(r3) */ + 0x83630074, /* lwz r27,116(r3) */ + 0x83830078, /* lwz r28,120(r3) */ + 0x83a3007c, /* lwz r29,124(r3) */ + 0x83c30080, /* lwz r30,128(r3) */ + 0x83e30084, /* lwz r31,132(r3) */ + 0x7ccff120, /* mtcr r6 */ + #endif + + #ifndef LIBCO_PPC_NOFP + 0xd9c400e0, /* stfd f14,224(r4) */ + 0xd9e400e8, /* stfd f15,232(r4) */ + 0xda0400f0, /* stfd f16,240(r4) */ + 0xda2400f8, /* stfd f17,248(r4) */ + 0xda440100, /* stfd f18,256(r4) */ + 0xda640108, /* stfd f19,264(r4) */ + 0xda840110, /* stfd f20,272(r4) */ + 0xdaa40118, /* stfd f21,280(r4) */ + 0xdac40120, /* stfd f22,288(r4) */ + 0xdae40128, /* stfd f23,296(r4) */ + 0xdb040130, /* stfd f24,304(r4) */ + 0xdb240138, /* stfd f25,312(r4) */ + 0xdb440140, /* stfd f26,320(r4) */ + 0xdb640148, /* stfd f27,328(r4) */ + 0xdb840150, /* stfd f28,336(r4) */ + 0xdba40158, /* stfd f29,344(r4) */ + 0xdbc40160, /* stfd f30,352(r4) */ + 0xdbe40168, /* stfd f31,360(r4) */ + 0xc9c300e0, /* lfd f14,224(r3) */ + 0xc9e300e8, /* lfd f15,232(r3) */ + 0xca0300f0, /* lfd f16,240(r3) */ + 0xca2300f8, /* lfd f17,248(r3) */ + 0xca430100, /* lfd f18,256(r3) */ + 0xca630108, /* lfd f19,264(r3) */ + 0xca830110, /* lfd f20,272(r3) */ + 0xcaa30118, /* lfd f21,280(r3) */ + 0xcac30120, /* lfd f22,288(r3) */ + 0xcae30128, /* lfd f23,296(r3) */ + 0xcb030130, /* lfd f24,304(r3) */ + 0xcb230138, /* lfd f25,312(r3) */ + 0xcb430140, /* lfd f26,320(r3) */ + 0xcb630148, /* lfd f27,328(r3) */ + 0xcb830150, /* lfd f28,336(r3) */ + 0xcba30158, /* lfd f29,344(r3) */ + 0xcbc30160, /* lfd f30,352(r3) */ + 0xcbe30168, /* lfd f31,360(r3) */ + #endif + + #ifdef __ALTIVEC__ + 0x7ca042a6, /* mfvrsave r5 */ + 0x39040180, /* addi r8,r4,384 */ + 0x39240190, /* addi r9,r4,400 */ + 0x70a00fff, /* andi. r0,r5,4095 */ + 0x90a40034, /* stw r5,52(r4) */ + 0x4182005c, /* beq- 2 */ + 0x7e8041ce, /* stvx v20,r0,r8 */ + 0x39080020, /* addi r8,r8,32 */ + 0x7ea049ce, /* stvx v21,r0,r9 */ + 0x39290020, /* addi r9,r9,32 */ + 0x7ec041ce, /* stvx v22,r0,r8 */ + 0x39080020, /* addi r8,r8,32 */ + 0x7ee049ce, /* stvx v23,r0,r9 */ + 0x39290020, /* addi r9,r9,32 */ + 0x7f0041ce, /* stvx v24,r0,r8 */ + 0x39080020, /* addi r8,r8,32 */ + 0x7f2049ce, /* stvx v25,r0,r9 */ + 0x39290020, /* addi r9,r9,32 */ + 0x7f4041ce, /* stvx v26,r0,r8 */ + 0x39080020, /* addi r8,r8,32 */ + 0x7f6049ce, /* stvx v27,r0,r9 */ + 0x39290020, /* addi r9,r9,32 */ + 0x7f8041ce, /* stvx v28,r0,r8 */ + 0x39080020, /* addi r8,r8,32 */ + 0x7fa049ce, /* stvx v29,r0,r9 */ + 0x39290020, /* addi r9,r9,32 */ + 0x7fc041ce, /* stvx v30,r0,r8 */ + 0x7fe049ce, /* stvx v31,r0,r9 */ + 0x80a30034, /*2:lwz r5,52(r3) */ + 0x39030180, /* addi r8,r3,384 */ + 0x39230190, /* addi r9,r3,400 */ + 0x70a00fff, /* andi. r0,r5,4095 */ + 0x7ca043a6, /* mtvrsave r5 */ + 0x4d820420, /* beqctr */ + 0x7e8040ce, /* lvx v20,r0,r8 */ + 0x39080020, /* addi r8,r8,32 */ + 0x7ea048ce, /* lvx v21,r0,r9 */ + 0x39290020, /* addi r9,r9,32 */ + 0x7ec040ce, /* lvx v22,r0,r8 */ + 0x39080020, /* addi r8,r8,32 */ + 0x7ee048ce, /* lvx v23,r0,r9 */ + 0x39290020, /* addi r9,r9,32 */ + 0x7f0040ce, /* lvx v24,r0,r8 */ + 0x39080020, /* addi r8,r8,32 */ + 0x7f2048ce, /* lvx v25,r0,r9 */ + 0x39290020, /* addi r9,r9,32 */ + 0x7f4040ce, /* lvx v26,r0,r8 */ + 0x39080020, /* addi r8,r8,32 */ + 0x7f6048ce, /* lvx v27,r0,r9 */ + 0x39290020, /* addi r9,r9,32 */ + 0x7f8040ce, /* lvx v28,r0,r8 */ + 0x39080020, /* addi r8,r8,32 */ + 0x7fa048ce, /* lvx v29,r0,r9 */ + 0x39290020, /* addi r9,r9,32 */ + 0x7fc040ce, /* lvx v30,r0,r8 */ + 0x7fe048ce, /* lvx v31,r0,r9 */ + #endif + + 0x4e800420, /* bctr */ +}; + +#if LIBCO_PPCDESC + /* function call goes through indirect descriptor */ + #define CO_SWAP_ASM(x, y) ((void (*)(cothread_t, cothread_t))(uintptr_t)x)(x, y) +#else + /* function call goes directly to code */ + #define CO_SWAP_ASM(x, y) ((void (*)(cothread_t, cothread_t))(uintptr_t)libco_ppc_code)(x, y) +#endif + +static uint32_t* co_create_(unsigned size, uintptr_t entry) { + (void)entry; + + uint32_t* t = (uint32_t*)malloc(size); + + #if LIBCO_PPCDESC + if(t) { + memcpy(t, (void*)entry, sizeof(void*) * 3); /* copy entry's descriptor */ + *(const void**)t = libco_ppc_code; /* set function pointer to swap routine */ + } + #endif + + return t; +} + +cothread_t co_create(unsigned int size, void (*entry_)(void), + size_t *out_size) { + + uintptr_t entry = (uintptr_t)entry_; + uint32_t* t = 0; + + /* be sure main thread was successfully allocated */ + if(co_active()) { + size += state_size + above_stack + stack_align; + t = co_create_(size, entry); + } + + if(t) { + uintptr_t sp; + int shift; + + /* save current registers into new thread, so that any special ones will have proper values when thread is begun */ + CO_SWAP_ASM(t, t); + + #if LIBCO_PPCDESC + entry = (uintptr_t)*(void**)entry; /* get real address */ + #endif + + /* put stack near end of block, and align */ + sp = (uintptr_t)t + size - above_stack; + sp -= sp % stack_align; + + /* on PPC32, we save and restore GPRs as 32 bits. for PPC64, we + save and restore them as 64 bits, regardless of the size the ABI + uses. so, we manually write pointers at the proper size. we always + save and restore at the same address, and since PPC is big-endian, + we must put the low byte first on PPC32. */ + + /* if uintptr_t is 32 bits, >>32 is undefined behavior, + so we do two shifts and don't have to care how many bits uintptr_t is. */ + #if LIBCO_PPC64 + shift = 16; + #else + shift = 0; + #endif + + /* set up so entry will be called on next swap */ + t[ 8] = (uint32_t)(entry >> shift >> shift); + t[ 9] = (uint32_t)entry; + + t[10] = (uint32_t)(sp >> shift >> shift); + t[11] = (uint32_t)sp; + } + *out_size = size; + return t; +} + +void co_delete(cothread_t t) { + free(t); +} + +static void co_init_(void) { + #if LIBCO_MPROTECT + long page_size = sysconf(_SC_PAGESIZE); + if(page_size > 0) { + uintptr_t align = page_size; + uintptr_t begin = (uintptr_t)libco_ppc_code; + uintptr_t end = begin + sizeof libco_ppc_code; + + /* align beginning and end */ + end += align - 1; + end -= end % align; + begin -= begin % align; + + mprotect((void*)begin, end - begin, PROT_READ | PROT_EXEC); + } + #endif + + co_active_handle = co_create_(state_size, (uintptr_t)&co_switch); +} + +cothread_t co_active() { + if(!co_active_handle) co_init_(); + + return co_active_handle; +} + +void co_switch(cothread_t t) { + cothread_t old = co_active_handle; + co_active_handle = t; + + CO_SWAP_ASM(t, old); +} diff --git a/src/fluent-bit/lib/monkey/deps/flb_libco/settings.h b/src/fluent-bit/lib/monkey/deps/flb_libco/settings.h new file mode 100644 index 000000000..0c3db68e0 --- /dev/null +++ b/src/fluent-bit/lib/monkey/deps/flb_libco/settings.h @@ -0,0 +1,52 @@ +#ifdef LIBCO_C + +/*[amd64, arm, ppc, x86]: + by default, co_swap_function is marked as a text (code) section + if not supported, uncomment the below line to use mprotect instead */ + +/* + * Testing Fluent Bit on Windows when doing co_swap it crash if the + * option LIBCO_MPROTECT is not defined. + */ +#ifdef _WIN32 +#define LIBCO_MPROTECT +#endif + +/*[amd64]: + Win64 only: provides a substantial speed-up, but will thrash XMM regs + do not use this unless you are certain your application won't use SSE */ +/* #define LIBCO_NO_SSE */ + +#ifdef LIBCO_C + #ifdef LIBCO_MP + #ifdef _MSC_VER + #define thread_local __declspec (thread) + #else + #define thread_local __thread + #endif + #else + #define thread_local + #endif +#endif + +#if __STDC_VERSION__ >= 201112L + #ifndef _MSC_VER + #include <stdalign.h> + #endif +#else + #define alignas(bytes) +#endif + +#if defined(_MSC_VER) + #pragma data_seg(".text") + #define text_section __declspec(allocate(".text")) +#elif defined(__APPLE__) && defined(__MACH__) + #define text_section __attribute__((section("__TEXT,__text"))) +#elif defined(__clang__) + #define text_section __attribute__((section(".text"))) +#else + #define text_section __attribute__((section(".text#"))) +#endif + +/* ifdef LIBCO_C */ +#endif diff --git a/src/fluent-bit/lib/monkey/deps/flb_libco/sjlj.c b/src/fluent-bit/lib/monkey/deps/flb_libco/sjlj.c new file mode 100644 index 000000000..36d110b71 --- /dev/null +++ b/src/fluent-bit/lib/monkey/deps/flb_libco/sjlj.c @@ -0,0 +1,105 @@ +/* + libco.sjlj (2008-01-28) + author: Nach + license: public domain +*/ + +/* + note this was designed for UNIX systems. Based on ideas expressed in a paper by Ralf Engelschall. + for SJLJ on other systems, one would want to rewrite springboard() and co_create() and hack the jmb_buf stack pointer. +*/ + +#define LIBCO_C +#include "libco.h" + +#include <stdlib.h> +#include <signal.h> +#include <setjmp.h> +#include "settings.h" + +#ifdef __cplusplus +extern "C" { +#endif + +typedef struct { + sigjmp_buf context; + void (*coentry)(void); + void* stack; +} cothread_struct; + +static thread_local cothread_struct co_primary; +static thread_local cothread_struct* creating; +static thread_local cothread_struct* co_running = 0; + +static void springboard(int ignored) { + if(sigsetjmp(creating->context, 0)) { + co_running->coentry(); + } +} + +cothread_t co_active() { + if(!co_running) co_running = &co_primary; + return (cothread_t)co_running; +} + +cothread_t co_create(unsigned int size, void (*coentry)(void), + size_t *out_size) { + if(!co_running) co_running = &co_primary; + + cothread_struct *thread = (cothread_struct*)malloc(sizeof(cothread_struct)); + if(thread) { + struct sigaction handler; + struct sigaction old_handler; + + stack_t stack; + stack_t old_stack; + + thread->coentry = thread->stack = 0; + + stack.ss_flags = 0; + stack.ss_size = size; + thread->stack = stack.ss_sp = malloc(size); + if(stack.ss_sp && !sigaltstack(&stack, &old_stack)) { + handler.sa_handler = springboard; + handler.sa_flags = SA_ONSTACK; + sigemptyset(&handler.sa_mask); + creating = thread; + + if(!sigaction(SIGUSR1, &handler, &old_handler)) { + if(!raise(SIGUSR1)) { + thread->coentry = coentry; + } + sigaltstack(&old_stack, 0); + sigaction(SIGUSR1, &old_handler, 0); + } + } + + if(thread->coentry != coentry) { + co_delete(thread); + thread = 0; + } + } + + *out_size = size; + return (cothread_t)thread; +} + +void co_delete(cothread_t cothread) { + if(cothread) { + if(((cothread_struct*)cothread)->stack) { + free(((cothread_struct*)cothread)->stack); + } + free(cothread); + } +} + +void co_switch(cothread_t cothread) { + if(!sigsetjmp(co_running->context, 0)) { + co_running = (cothread_struct*)cothread; + siglongjmp(co_running->context, 1); + } +} + +#ifdef __cplusplus +} +#endif diff --git a/src/fluent-bit/lib/monkey/deps/flb_libco/ucontext.c b/src/fluent-bit/lib/monkey/deps/flb_libco/ucontext.c new file mode 100644 index 000000000..b252cb2d8 --- /dev/null +++ b/src/fluent-bit/lib/monkey/deps/flb_libco/ucontext.c @@ -0,0 +1,72 @@ +/* + libco.ucontext (2008-01-28) + author: Nach + license: public domain +*/ + +/* + WARNING: the overhead of POSIX ucontext is very high, + assembly versions of libco or libco_sjlj should be much faster + + this library only exists for two reasons: + 1: as an initial test for the viability of a ucontext implementation + 2: to demonstrate the power and speed of libco over existing implementations, + such as pth (which defaults to wrapping ucontext on unix targets) + + use this library only as a *last resort* +*/ + +#define LIBCO_C +#include "libco.h" +#include "settings.h" + +#define _BSD_SOURCE +#include <stdlib.h> +#include <ucontext.h> + +#ifdef __cplusplus +extern "C" { +#endif + +static thread_local ucontext_t co_primary; +static thread_local ucontext_t* co_running = 0; + +cothread_t co_active() { + if(!co_running) co_running = &co_primary; + return (cothread_t)co_running; +} + +cothread_t co_create(unsigned int heapsize, void (*coentry)(void), + size_t *out_size) { + if(!co_running) co_running = &co_primary; + ucontext_t* thread = (ucontext_t*)malloc(sizeof(ucontext_t)); + if(thread) { + if((!getcontext(thread) && !(thread->uc_stack.ss_sp = 0)) && (thread->uc_stack.ss_sp = malloc(heapsize))) { + thread->uc_link = co_running; + thread->uc_stack.ss_size = heapsize; + *out_size = heapsize; + makecontext(thread, coentry, 0); + } else { + co_delete((cothread_t)thread); + thread = 0; + } + } + return (cothread_t)thread; +} + +void co_delete(cothread_t cothread) { + if(cothread) { + if(((ucontext_t*)cothread)->uc_stack.ss_sp) { free(((ucontext_t*)cothread)->uc_stack.ss_sp); } + free(cothread); + } +} + +void co_switch(cothread_t cothread) { + ucontext_t* old_thread = co_running; + co_running = (ucontext_t*)cothread; + swapcontext(old_thread, co_running); +} + +#ifdef __cplusplus +} +#endif diff --git a/src/fluent-bit/lib/monkey/deps/flb_libco/x86.c b/src/fluent-bit/lib/monkey/deps/flb_libco/x86.c new file mode 100644 index 000000000..bfa50b84d --- /dev/null +++ b/src/fluent-bit/lib/monkey/deps/flb_libco/x86.c @@ -0,0 +1,116 @@ +/* + libco.x86 (2016-09-14) + author: byuu + license: public domain +*/ + +#define LIBCO_C +#include "libco.h" +#include "settings.h" + +#include <assert.h> +#include <stdlib.h> + +#ifdef __cplusplus +extern "C" { +#endif + +#if defined(__clang__) || defined(__GNUC__) + #define fastcall __attribute__((fastcall)) +#elif defined(_MSC_VER) + #define fastcall __fastcall +#else + #error "libco: please define fastcall macro" +#endif + +static thread_local long co_active_buffer[64]; +static thread_local cothread_t co_active_handle = 0; +static void (fastcall *co_swap)(cothread_t, cothread_t) = 0; + +#ifdef LIBCO_MPROTECT + alignas(4096) +#else + text_section +#endif +/* ABI: fastcall */ +static const unsigned char co_swap_function[4096] = { + 0x89, 0x22, /* mov [edx],esp */ + 0x8b, 0x21, /* mov esp,[ecx] */ + 0x58, /* pop eax */ + 0x89, 0x6a, 0x04, /* mov [edx+ 4],ebp */ + 0x89, 0x72, 0x08, /* mov [edx+ 8],esi */ + 0x89, 0x7a, 0x0c, /* mov [edx+12],edi */ + 0x89, 0x5a, 0x10, /* mov [edx+16],ebx */ + 0x8b, 0x69, 0x04, /* mov ebp,[ecx+ 4] */ + 0x8b, 0x71, 0x08, /* mov esi,[ecx+ 8] */ + 0x8b, 0x79, 0x0c, /* mov edi,[ecx+12] */ + 0x8b, 0x59, 0x10, /* mov ebx,[ecx+16] */ + 0xff, 0xe0, /* jmp eax */ +}; + +#ifdef _WIN32 + #include <windows.h> + + static void co_init() { + #ifdef LIBCO_MPROTECT + DWORD old_privileges; + VirtualProtect((void*)co_swap_function, sizeof co_swap_function, PAGE_EXECUTE_READ, &old_privileges); + #endif + } +#else + #include <unistd.h> + #include <sys/mman.h> + + static void co_init() { + #ifdef LIBCO_MPROTECT + unsigned long addr = (unsigned long)co_swap_function; + unsigned long base = addr - (addr % sysconf(_SC_PAGESIZE)); + unsigned long size = (addr - base) + sizeof co_swap_function; + mprotect((void*)base, size, PROT_READ | PROT_EXEC); + #endif + } +#endif + +static void crash() { + assert(0); /* called only if cothread_t entrypoint returns */ +} + +cothread_t co_active() { + if(!co_active_handle) co_active_handle = &co_active_buffer; + return co_active_handle; +} + +cothread_t co_create(unsigned int size, void (*entrypoint)(void), + size_t *out_size) { + cothread_t handle; + if(!co_swap) { + co_init(); + co_swap = (void (fastcall*)(cothread_t, cothread_t))co_swap_function; + } + if(!co_active_handle) co_active_handle = &co_active_buffer; + size += 256; /* allocate additional space for storage */ + size &= ~15; /* align stack to 16-byte boundary */ + *out_size = size; + + if(handle = (cothread_t)malloc(size)) { + long *p = (long*)((char*)handle + size); /* seek to top of stack */ + *--p = (long)crash; /* crash if entrypoint returns */ + *--p = (long)entrypoint; /* start of function */ + *(long*)handle = (long)p; /* stack pointer */ + } + + return handle; +} + +void co_delete(cothread_t handle) { + free(handle); +} + +void co_switch(cothread_t handle) { + register cothread_t co_previous_handle = co_active_handle; + co_swap(co_active_handle = handle, co_previous_handle); +} + +#ifdef __cplusplus +} +#endif diff --git a/src/fluent-bit/lib/monkey/deps/rbtree/CMakeLists.txt b/src/fluent-bit/lib/monkey/deps/rbtree/CMakeLists.txt new file mode 100644 index 000000000..739260e2c --- /dev/null +++ b/src/fluent-bit/lib/monkey/deps/rbtree/CMakeLists.txt @@ -0,0 +1,5 @@ +set(src + rbtree.c + ) + +add_library(rbtree STATIC ${src}) diff --git a/src/fluent-bit/lib/monkey/deps/rbtree/README.md b/src/fluent-bit/lib/monkey/deps/rbtree/README.md new file mode 100644 index 000000000..00851601e --- /dev/null +++ b/src/fluent-bit/lib/monkey/deps/rbtree/README.md @@ -0,0 +1,7 @@ +[Taken from: https://github.com/pvachon/rbtree] + +A simple, intrusive, zero-allocation Red-Black tree implementation. + +Designed exclusively for systems where determinism is needed. + +Licensed under a 2-clause BSD license for the sake of simplicity. diff --git a/src/fluent-bit/lib/monkey/deps/rbtree/rbtree.c b/src/fluent-bit/lib/monkey/deps/rbtree/rbtree.c new file mode 100644 index 000000000..99e56e0c8 --- /dev/null +++ b/src/fluent-bit/lib/monkey/deps/rbtree/rbtree.c @@ -0,0 +1,811 @@ +/* + Copyright (c) 2013, Phil Vachon <phil@cowpig.ca> + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions + are met: + + - Redistributions of source code must retain the above copyright notice, + this list of conditions and the following disclaimer. + + - Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR + CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; + OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, + WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR + OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** \defgroup rb_tree_implementation Implementation Details + * All the implementation details for the red-black tree, including functions for + * the maintenance of tree properties. + * @{ + */ + +/** \file rbtree.c + * An implementation of an intrusive red-black self-balancing tree, that can + * be used to implement red-black trees in situations where memory allocation + * is not an option. + * + * This file exclusively contains implementation details for the red-black tree, so + * probably is not of much interest to most people. + * + * \see rbtree.h + * \see rb_tree + * \see rb_tree_node + */ + +#include <rbtree.h> + +#include <stdlib.h> +#include <string.h> + +/** \defgroup rb_tree_colors Colors for the red-black tree nodes + * @{ + */ + +/** + * Node is black + */ +#define COLOR_BLACK 0x0 + +/** + * Node is red + */ +#define COLOR_RED 0x1 +/**@}*/ + +static +int __rb_tree_cmp_mapper(void *state, const void *lhs, const void *rhs) +{ + rb_cmp_func_t cmp = state; + return cmp(lhs, rhs); +} + +rb_result_t rb_tree_new_ex(struct rb_tree *tree, + rb_cmp_func_ex_t compare, + void *state) +{ + rb_result_t ret = RB_OK; + + RB_ASSERT_ARG(tree != NULL); + RB_ASSERT_ARG(compare != NULL); + + tree->root = NULL; + tree->compare = compare; + tree->state = state; + tree->rightmost = NULL; + + return ret; +} + +rb_result_t rb_tree_new(struct rb_tree *tree, + rb_cmp_func_t compare) +{ + RB_ASSERT_ARG(tree != NULL); + RB_ASSERT_ARG(compare != NULL); + + return rb_tree_new_ex(tree, __rb_tree_cmp_mapper, (void *)compare); +} + +rb_result_t rb_tree_destroy(struct rb_tree *tree) +{ + rb_result_t ret = RB_OK; + + RB_ASSERT_ARG(tree != NULL); + + memset(tree, 0, sizeof(struct rb_tree)); + + return ret; +} + +rb_result_t rb_tree_empty(struct rb_tree *tree, + int *is_empty) +{ + rb_result_t ret = RB_OK; + + RB_ASSERT_ARG(tree != NULL); + RB_ASSERT_ARG(is_empty != NULL); + + *is_empty = !!(tree->root == NULL); + + return ret; +} + +rb_result_t rb_tree_find(struct rb_tree *tree, + const void *key, + struct rb_tree_node **value) +{ + rb_result_t ret = RB_OK; + + RB_ASSERT_ARG(tree != NULL); + RB_ASSERT_ARG(value != NULL); + + *value = NULL; + + if (RB_UNLIKELY(tree->root == NULL)) { + ret = RB_NOT_FOUND; + goto done; + } + + struct rb_tree_node *node = tree->root; + + while (node != NULL) { + int compare = tree->compare(tree->state, key, node->key); + + if (compare < 0) { + node = node->left; + } else if (compare == 0) { + break; /* We found our node */ + } else { + /* Otherwise, we want the right node, and continue iteration */ + node = node->right; + } + } + + if (node == NULL) { + ret = RB_NOT_FOUND; + goto done; + } + + /* Return the node we found */ + *value = node; + +done: + return ret; +} + +/* Helper function to get a node's sibling */ +static inline +struct rb_tree_node *__helper_get_sibling(struct rb_tree_node *node) +{ + if (node->parent == NULL) { + return NULL; + } + + struct rb_tree_node *parent = node->parent; + + if (node == parent->left) { + return parent->right; + } else { + return parent->left; + } +} + +/* Helper function to get a node's grandparent */ +static inline +struct rb_tree_node *__helper_get_grandparent(struct rb_tree_node *node) +{ + if (node->parent == NULL) { + return NULL; + } + + struct rb_tree_node *parent_node = node->parent; + + return parent_node->parent; +} + +/* Helper function to get a node's uncle */ +static inline +struct rb_tree_node *__helper_get_uncle(struct rb_tree_node *node) +{ + struct rb_tree_node *grandparent = __helper_get_grandparent(node); + + if (grandparent == NULL) { + return NULL; + } + + if (node->parent == grandparent->left) { + return grandparent->right; + } else { + return grandparent->left; + } +} + +/* Helper function to do a left rotation of a given node */ +static inline +void __helper_rotate_left(struct rb_tree *tree, + struct rb_tree_node *node) +{ + struct rb_tree_node *x = node; + struct rb_tree_node *y = x->right; + + x->right = y->left; + + if (y->left != NULL) { + struct rb_tree_node *yleft = y->left; + yleft->parent = x; + } + + y->parent = x->parent; + + if (x->parent == NULL) { + tree->root = y; + } else { + struct rb_tree_node *xp = x->parent; + if (x == xp->left) { + xp->left = y; + } else { + xp->right = y; + } + } + + y->left = x; + x->parent = y; +} + +/* Helper function to do a right rotation of a given node */ +static inline +void __helper_rotate_right(struct rb_tree *tree, + struct rb_tree_node *node) +{ + struct rb_tree_node *x = node; + struct rb_tree_node *y = x->left; + + x->left = y->right; + + if (y->right != NULL) { + struct rb_tree_node *yright = y->right; + yright->parent = x; + } + + y->parent = x->parent; + + if (x->parent == NULL) { + tree->root = y; + } else { + struct rb_tree_node *xp = x->parent; + if (x == xp->left) { + xp->left = y; + } else { + xp->right = y; + } + } + + y->right = x; + x->parent = y; +} + +/* Function to perform a RB tree rebalancing after an insertion */ +static +void __helper_rb_tree_insert_rebalance(struct rb_tree *tree, + struct rb_tree_node *node) +{ + struct rb_tree_node *new_node_parent = node->parent; + + if (new_node_parent != NULL && new_node_parent->color != COLOR_BLACK) { + struct rb_tree_node *pnode = node; + + /* Iterate until we're at the root (which we just color black) or + * until we the parent node is no longer red. + */ + while ((tree->root != pnode) && (pnode->parent != NULL) && + (pnode->parent->color == COLOR_RED)) + { + struct rb_tree_node *parent = pnode->parent; + struct rb_tree_node *grandparent = __helper_get_grandparent(pnode); + struct rb_tree_node *uncle = NULL; + int uncle_is_left; + + assert(pnode->color == COLOR_RED); + + if (parent == grandparent->left) { + uncle_is_left = 0; + uncle = grandparent->right; + } else { + uncle_is_left = 1; + uncle = grandparent->left; + } + + /* Case 1: Uncle is not black */ + if (uncle && uncle->color == COLOR_RED) { + /* Color parent and uncle black */ + parent->color = COLOR_BLACK; + uncle->color = COLOR_BLACK; + + /* Color Grandparent as Black */ + grandparent->color = COLOR_RED; + pnode = grandparent; + /* Continue iteration, processing grandparent */ + } else { + /* Case 2 - node's parent is red, but uncle is black */ + if (!uncle_is_left && parent->right == pnode) { + pnode = pnode->parent; + __helper_rotate_left(tree, pnode); + } else if (uncle_is_left && parent->left == pnode) { + pnode = pnode->parent; + __helper_rotate_right(tree, pnode); + } + + /* Case 3 - Recolor and rotate*/ + parent = pnode->parent; + parent->color = COLOR_BLACK; + + grandparent = __helper_get_grandparent(pnode); + grandparent->color = COLOR_RED; + if (!uncle_is_left) { + __helper_rotate_right(tree, grandparent); + } else { + __helper_rotate_left(tree, grandparent); + } + } + } + + /* Make sure the tree root is black (Case 1: Continued) */ + struct rb_tree_node *tree_root = tree->root; + tree_root->color = COLOR_BLACK; + } +} + +rb_result_t rb_tree_insert(struct rb_tree *tree, + const void *key, + struct rb_tree_node *node) +{ + rb_result_t ret = RB_OK; + + int rightmost = 1; + struct rb_tree_node *nd = NULL; + + RB_ASSERT_ARG(tree != NULL); + RB_ASSERT_ARG(node != NULL); + + node->left = NULL; + node->right = NULL; + node->parent = NULL; + node->key = key; + + /* Case 1: Simplest case -- tree is empty */ + if (RB_UNLIKELY(tree->root == NULL)) { + tree->root = node; + tree->rightmost = node; + node->color = COLOR_BLACK; + goto done; + } + + /* Otherwise, insert the node as you would typically in a BST */ + nd = tree->root; + node->color = COLOR_RED; + + rightmost = 1; + + /* Insert a node into the tree as you normally would */ + while (nd != NULL) { + int compare = tree->compare(tree->state, node->key, nd->key); + + if (compare == 0) { + ret = RB_DUPLICATE; + goto done; + } + + if (compare < 0) { + rightmost = 0; + if (nd->left == NULL) { + nd->left = node; + break; + } else { + nd = nd->left; + } + } else { + if (nd->right == NULL) { + nd->right = node; + break; + } else { + nd = nd->right; + } + } + } + + node->parent = nd; + + if (1 == rightmost) { + tree->rightmost = node; + } + + /* Rebalance the tree about the node we just added */ + __helper_rb_tree_insert_rebalance(tree, node); + +done: + return ret; +} + +rb_result_t rb_tree_find_or_insert(struct rb_tree *tree, + void *key, + struct rb_tree_node *new_candidate, + struct rb_tree_node **value) +{ + rb_result_t ret = RB_OK; + + RB_ASSERT_ARG(tree != NULL); + RB_ASSERT_ARG(value != NULL); + RB_ASSERT_ARG(new_candidate != NULL); + + *value = NULL; + new_candidate->key = key; + + struct rb_tree_node *node = tree->root; + + /* Case 1: Tree is empty, so we just insert the node */ + if (RB_UNLIKELY(tree->root == NULL)) { + tree->root = new_candidate; + tree->rightmost = new_candidate; + new_candidate->color = COLOR_BLACK; + node = new_candidate; + goto done; + } + + struct rb_tree_node *node_prev = NULL; + int dir = 0, rightmost = 1; + while (node != NULL) { + int compare = tree->compare(tree->state, key, node->key); + + if (compare < 0) { + node_prev = node; + dir = 0; + node = node->left; + rightmost = 0; + } else if (compare == 0) { + break; /* We found our node */ + } else { + /* Otherwise, we want the right node, and continue iteration */ + node_prev = node; + dir = 1; + node = node->right; + } + } + + /* Case 2 - we didn't find the node, so insert the candidate */ + if (node == NULL) { + if (dir == 0) { + rightmost = 0; + node_prev->left = new_candidate; + } else { + node_prev->right = new_candidate; + } + + new_candidate->parent = node_prev; + + node = new_candidate; + node->color = COLOR_RED; + + if (1 == rightmost) { + tree->rightmost = new_candidate; + } + + /* Rebalance the tree, preserving rb properties */ + __helper_rb_tree_insert_rebalance(tree, node); + } + +done: + /* Return the node we found */ + *value = node; + + return ret; +} + +/** + * Find the minimum of the subtree starting at node + */ +static +struct rb_tree_node *__helper_rb_tree_find_minimum(struct rb_tree_node *node) +{ + struct rb_tree_node *x = node; + + while (x->left != NULL) { + x = x->left; + } + + return x; +} + +static +struct rb_tree_node *__helper_rb_tree_find_maximum(struct rb_tree_node *node) +{ + struct rb_tree_node *x = node; + + while (x->right != NULL) { + x = x->right; + } + + return x; +} + +static +struct rb_tree_node *__helper_rb_tree_find_successor(struct rb_tree_node *node) +{ + struct rb_tree_node *x = node; + + if (x->right != NULL) { + return __helper_rb_tree_find_minimum(x->right); + } + + struct rb_tree_node *y = x->parent; + + while (y != NULL && x == y->right) { + x = y; + y = y->parent; + } + + return y; +} + +static +struct rb_tree_node *__helper_rb_tree_find_predecessor(struct rb_tree_node *node) +{ + struct rb_tree_node *x = node; + + if (x->left != NULL) { + return __helper_rb_tree_find_maximum(x->left); + } + + struct rb_tree_node *y = x->parent; + + while (y != NULL && x == y->left) { + x = y; + y = y->parent; + } + + return y; +} + + +/* Replace x with y, inserting y where x previously was */ +static +void __helper_rb_tree_swap_node(struct rb_tree *tree, + struct rb_tree_node *x, + struct rb_tree_node *y) +{ + struct rb_tree_node *left = x->left; + struct rb_tree_node *right = x->right; + struct rb_tree_node *parent = x->parent; + + y->parent = parent; + + if (parent != NULL) { + if (parent->left == x) { + parent->left = y; + } else { + parent->right = y; + } + } else { + if (tree->root == x) { + tree->root = y; + } + } + + y->right = right; + if (right != NULL) { + right->parent = y; + } + x->right = NULL; + + y->left = left; + if (left != NULL) { + left->parent = y; + } + x->left = NULL; + + y->color = x->color; + x->parent = NULL; +} + +static +void __helper_rb_tree_delete_rebalance(struct rb_tree *tree, + struct rb_tree_node *node, + struct rb_tree_node *parent, + int node_is_left) +{ + struct rb_tree_node *x = node; + struct rb_tree_node *xp = parent; + int is_left = node_is_left; + + while (x != tree->root && (x == NULL || x->color == COLOR_BLACK)) { + struct rb_tree_node *w = is_left ? xp->right : xp->left; /* Sibling */ + + if (w != NULL && w->color == COLOR_RED) { + /* Case 1: */ + w->color = COLOR_BLACK; + xp->color = COLOR_RED; + if (is_left) { + __helper_rotate_left(tree, xp); + } else { + __helper_rotate_right(tree, xp); + } + w = is_left ? xp->right : xp->left; + } + + struct rb_tree_node *wleft = w != NULL ? w->left : NULL; + struct rb_tree_node *wright = w != NULL ? w->right : NULL; + if ( (wleft == NULL || wleft->color == COLOR_BLACK) && + (wright == NULL || wright->color == COLOR_BLACK) ) + { + /* Case 2: */ + if (w != NULL) { + w->color = COLOR_RED; + } + x = xp; + xp = x->parent; + is_left = xp && (x == xp->left); + } else { + if (is_left && (wright == NULL || wright->color == COLOR_BLACK)) { + /* Case 3a: */ + w->color = COLOR_RED; + if (wleft) { + wleft->color = COLOR_BLACK; + } + __helper_rotate_right(tree, w); + w = xp->right; + } else if (!is_left && (wleft == NULL || wleft->color == COLOR_BLACK)) { + /* Case 3b: */ + w->color = COLOR_RED; + if (wright) { + wright->color = COLOR_BLACK; + } + __helper_rotate_left(tree, w); + w = xp->left; + } + + /* Case 4: */ + wleft = w->left; + wright = w->right; + + w->color = xp->color; + xp->color = COLOR_BLACK; + + if (is_left && wright != NULL) { + wright->color = COLOR_BLACK; + __helper_rotate_left(tree, xp); + } else if (!is_left && wleft != NULL) { + wleft->color = COLOR_BLACK; + __helper_rotate_right(tree, xp); + } + x = tree->root; + } + } + + if (x != NULL) { + x->color = COLOR_BLACK; + } +} + +rb_result_t rb_tree_remove(struct rb_tree *tree, + struct rb_tree_node *node) +{ + rb_result_t ret = RB_OK; + + RB_ASSERT_ARG(tree != NULL); + RB_ASSERT_ARG(node != NULL); + + struct rb_tree_node *y; + + + if (node->left == NULL || node->right == NULL) { + y = node; + if (node == tree->rightmost) { + /* The new rightmost item is our successor */ + tree->rightmost = __helper_rb_tree_find_predecessor(node); + } + } else { + y = __helper_rb_tree_find_successor(node); + } + + struct rb_tree_node *x, *xp; + + if (y->left != NULL) { + x = y->left; + } else { + x = y->right; + } + + if (x != NULL) { + x->parent = y->parent; + xp = x->parent; + } else { + xp = y->parent; + } + + int is_left = 0; + if (y->parent == NULL) { + tree->root = x; + xp = NULL; + } else { + struct rb_tree_node *yp = y->parent; + if (y == yp->left) { + yp->left = x; + is_left = 1; + } else { + yp->right = x; + is_left = 0; + } + } + + int y_color = y->color; + + /* Swap in the node */ + if (y != node) { + __helper_rb_tree_swap_node(tree, node, y); + if (xp == node) { + xp = y; + } + } + + if (y_color == COLOR_BLACK) { + __helper_rb_tree_delete_rebalance(tree, x, xp, is_left); + } + + node->parent = NULL; + node->left = NULL; + node->right = NULL; + + return ret; +} + +/** + * \mainpage An Intrusive Red-Black Tree + * + * The goal of this implementation is to be both easy to use, but also + * sufficiently powerful enough to perform all the operations that one might + * typically want to do with a red-black tree. + * + * To make a structure usable with an rb_tree, you must embed the structure + * struct rb_tree_node. + * \code + struct my_sample_struct { + const char *name; + int data; + struct rb_tree_node rnode; + }; + * \endcode + * \note `rb_tree_node` need not be initialized -- it is initialized during the + * insertion operation. + * + * Next, you must declare a comparison function that, given a pointer to two + * keys, returns a value less than 0 if the left-hand side is less than the + * right-hand side, 0 if the left-hand side is equal to the right-hand side, + * or greater than 0 if the left-hand side is greater than the left-hand side. + * + * A simple example for a string might use the `strcmp(3)` function directly, + * as such: + * + * \code + int my_sample_struct_compare_keys(void *lhs, void *rhs) + { + return strcmp((const char *)lhs, (const char *)rhs); + } + * \endcode + * \note the function you create for your comparison function must conform to + * rb_cmp_func_t, or the compiler will generate a warning and, if you're + * unlucky, you will fail catastrophically at a later date. + * + * Then, to create a new, empty red-black tree, call rb_tree_new, as so: + * \code + struct rb_tree my_rb_tree; + if (rb_tree_new(&my_rb_tree, my_sample_struct_compare_keys) != RB_OK) { + exit(EXIT_FAILURE); + } + * \endcode + * + * Items can be added to the red-black tree using the function `rb_tree_insert`: + * \code + struct my_sample_struct node = { .name = "test1", .date = 42 }; + if (rb_tree_insert(&my_rb_tree, node.name, &(node.rnode)) != RB_OK) { + printf("Failed to insert a node into the RB tree!\n"); + exit(EXIT_FAILURE); + } + * \endcode + * + * \see rb_tree + * \see rb_tree_node + * \see rb_functions + * \see rbtree.h + */ + diff --git a/src/fluent-bit/lib/monkey/deps/rbtree/rbtree.h b/src/fluent-bit/lib/monkey/deps/rbtree/rbtree.h new file mode 100644 index 000000000..e85b274c6 --- /dev/null +++ b/src/fluent-bit/lib/monkey/deps/rbtree/rbtree.h @@ -0,0 +1,459 @@ +#ifndef __INCLUDED_RBTREE_H__ +#define __INCLUDED_RBTREE_H__ + +/** \file rbtree.h + * Declaration of associated structures and functions for a simple, intrusive + * red-black tree implementation. + */ + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +#include <stdlib.h> +#include <assert.h> + +/** \defgroup rb_tree_compiler_prims Compiler Abstractions + * Primitives used to abstract compiler-specific syntax for common details used in + * providing hints to the compiler for optimization or linker details. + * @{ + */ + +/** + * Macro to check if a given assertion about an argument is true + */ +#define RB_ASSERT_ARG(x) \ + do { \ + if (RB_UNLIKELY(!(x))) { \ + assert(#x && 0); \ + return RB_BAD_ARG; \ + } \ + } while (0) + +/** + * The tagged branch is unlikely to be taken + */ +#ifdef _WIN32 +#define RB_UNLIKELY(x) x +#else +#define RB_UNLIKELY(x) __builtin_expect(!!(x), 0) +#endif +/**@}*/ + +/** \defgroup rb_tree_state State Structures + * Structures that are used to represent state of a red-black tree, including the + * state of the tree itself, comparison functions used to determine how the tree + * is to be traversed, and representations of red-black tree nodes themselves. + * @{ + */ + +/** + * Structure that represents a node in a red-black tree. Embed this in your own + * structure in order to add your structure to the given red-black tree. + * Users of the rb_tree_node would embed it something like + * \code{.c} + struct my_sample_struct { + char *name; + int data; + struct rb_tree_node rnode; + }; + * \endcode + * + * \note No user of `struct rb_tree_node` should ever modify or inspect any + * members of the structure. + */ +struct rb_tree_node { + /** + * The left child (`NULL` if empty) + */ + struct rb_tree_node *left; + + /** + * The right child (`NULL` if empty) + */ + struct rb_tree_node *right; + + /** + * The parent of this node (`NULL` if at root) + */ + struct rb_tree_node *parent; + + /** + * The key for this node + */ + const void *key; + + /** + * The color of the node + */ + int color; +}; + +/** + * Pointer to a function to compare two keys, and returns as follows: + * - (0, +inf] if lhs > rhs + * - 0 if lhs == rhs + * - [-inf, 0) if lhs < rhs + */ +typedef int (*rb_cmp_func_t)(const void *lhs, const void *rhs); + +/** + * Pointer to a comparison function that allows passing along state. + * Return values are interpreted as follows: + * (0, +inf] if lhs > rhs + * 0 if lhs == rhs + * [-inf, 0) if lhs < rhs + */ +typedef int (*rb_cmp_func_ex_t)(void *state, const void *lhs, const void *rhs); + +/** + * Structure representing an RB tree's associated state. Contains all + * the information needed to manage the lifecycle of a RB tree. + * \note Typically users should not directly manipulate the structure, + * but rather use the provided accessor functions. + */ +struct rb_tree { + /** + * The root of the tree + */ + struct rb_tree_node *root; + + /** + * Predicate used for traversing the tree + */ + rb_cmp_func_ex_t compare; + + /** + * The right-most node of the rb-tree + */ + struct rb_tree_node *rightmost; + + /** + * Private state that can be used by the rb-tree owner + */ + void *state; +}; + +/**@} rb_tree_state */ + +/** \defgroup rb_result Function Results and Error Handling + * @{ + */ +/** \typedef rb_result_t + * Value of a returned result code from a red-black tree function. + */ +typedef int rb_result_t; + +/** \defgroup rb_result_code Result Codes + * Error codes that can be returned from any function that returns an rb_result_t. + * @{ + */ + +/** + * Function was successful + */ +#define RB_OK 0x0 +/** + * Element was not found + */ +#define RB_NOT_FOUND 0x1 +/** + * Bad argument provided to function (typically unexpected NULL) + */ +#define RB_BAD_ARG 0x2 +/** + * Node is a duplicate of an existing node + */ +#define RB_DUPLICATE 0x3 + +/**@} rb_result_code */ +/**@} rb_result */ + +/** \brief Helper to get a pointer to a containing structure. + * Given a pointer to an rb_tree_node, a target type and a member name, + * return a pointer to the structure containing the `struct rb_tree_node`. + * \code{.c} + struct sample { + const char *name; + struct rb_tree_node node; + }; + + void test(void) + { + struct sample samp = { .name = "Test 123" }; + struct rb_tree_node *samp_node = &(samp.node); + struct sample *samp2 = RB_CONTAINER_OF(samp_node, struct sample, node); + + assert(&samp == samp2); + } + * \endcode + * \param x The pointer to the node + * \param type The type of the containing structure + * \param memb The name of the `struct rb_tree_node` in the containing structure + * \return Pointer to the containing structure of the specified type + */ +#define RB_CONTAINER_OF(x, type, memb) \ + ({ \ + const __typeof__( ((type *)0)->memb ) *__member = (x); \ + (type *)( (char *)__member - __offsetof__(type, memb) ); \ + }) + + +/** \defgroup rb_functions Functions for Manipulating Red-Black Trees + * All functions associated with manipulating Red-Black trees using `struct rb_tree`, + * inluding lifecycle functions and member manipulation and state checking functions. + * @{ + */ + +/** + * \brief Construct a new, empty red-black tree, with extended state + * Given a region of memory at least the size of a struct rb_tree to + * store the red-black tree metadata, update it to contain an initialized, empty + * red-black tree, with given private state. + * \param tree Pointer to the new tree. + * \param compare Function used to traverse the tree. + * \param state The private state to be passed to the compare function + * \return RB_OK on success, an error code otherwise + */ +rb_result_t rb_tree_new_ex(struct rb_tree *tree, rb_cmp_func_ex_t compare, void *state); + +/** + * \brief Construct a new, empty red-black tree. + * Given a region of memory at least the size of a struct rb_tree to + * store the red-black tree metadata, update it to contain an initialized, empty + * red-black tree. + * \param tree Pointer to the new tree. + * \param compare Function used to traverse the tree. + * \return RB_OK on success, an error code otherwise + */ +rb_result_t rb_tree_new(struct rb_tree *tree, + rb_cmp_func_t compare); + +/** + * \brief Destroy a Red-Black tree. + * Clean up the state structure, clearing out the state of the tree + * so that it no longer can be used. + * \note Assumes that external callers will deallocate all nodes through + * some application-specific mechanism. + * \param tree The reference to the pointer to the tree itself. + * \return RB_OK on success, an error code otherwise + */ +rb_result_t rb_tree_destroy(struct rb_tree *tree); + +/** + * \brief Check if an red-black tree is empty (has no nodes). + * If no nodes are present, returns a non-zero value in `is_empty` -- returns + * 0 if there are nodes present. + * \param tree The tree to check + * \param is_empty nonzero on true, 0 otherwise + * \return RB_OK on success, an error code otherwise + */ +rb_result_t rb_tree_empty(struct rb_tree *tree, int *is_empty); + +/** + * \brief Find a node in the Red-Black tree given the specified key. + * Given a key, search the RB-tree iteratively until the specified key is found. + * This traversal is in O(log n) time, per the properties of a binary search tree. + * \param tree The RB-tree to search + * \param key The key to search for + * \param value a reference to a pointer to receive the pointer to the rb_tree_node if key is found + * \return RB_OK on success, an error code otherwise + */ +rb_result_t rb_tree_find(struct rb_tree *tree, + const void *key, + struct rb_tree_node **value); + +/** + * \brief Insert a node into the tree. + * Given a node and key, insert the node into the red-black tree and rebalance + * the tree if appropriate. Insertion is O(log n) time, with two tree traversals + * possible -- one for insertion (guaranteed) and one for rebalancing. + * \param tree the RB tree to insert the node into + * \param key The key for the node (must live as long as the node itself is in the tree) + * \param node the node to be inserted into the tree + * \return RB_OK on sucess, an error code otherwise + */ +rb_result_t rb_tree_insert(struct rb_tree *tree, + const void *key, + struct rb_tree_node *node); + +/** + * \brief Remove the specified node from the Red-Black tree. + * Given a pointer to the node, splice the node out of the tree, then, if applicable + * rebalance the tree so the Red-Black properties are maintained. + * \param tree The tree we want to remove the node from + * \param node The the node we want to remove + * \return RB_OK on success, an error code otherwise + */ +rb_result_t rb_tree_remove(struct rb_tree *tree, + struct rb_tree_node *node); + +/** + * \brief Find a node. If not found, insert the candidate. + * Find a node with the given key. If the node is found, return it by + * reference, without modifying the tree. If the node is not found, + * insert the provided candidate node. + * \note This function always will return in *value the node inserted + * or the existing node. If you want to check if the candidate + * node was inserted, check if `*value == new_candidate` + * + * \param tree The tree in question + * \param key The key to search for + * \param new_candidate The candidate node to insert + * \param value The value at the given location + * \return RB_OK on success, an error code otherwise + */ +rb_result_t rb_tree_find_or_insert(struct rb_tree *tree, + void *key, + struct rb_tree_node *new_candidate, + struct rb_tree_node **value); + +/** + * \brief Find a node. If not found, insert the candidate. + * Find a node with the given key. If the node is found, return it by + * reference, without modifying the tree. If the node is not found, + * insert the provided candidate node. + * \note This function always will return in *value the node inserted + * or the existing node. If you want to check if the candidate + * node was inserted, check if `*value == new_candidate` + * + * \param tree The tree in question + * \param key The key to search for + * \param new_candidate The candidate node to insert + * \param value The value at the given location + * + * \return RB_OK on success, an error code otherwise + */ +rb_result_t rb_tree_find_or_insert(struct rb_tree *tree, + void *key, + struct rb_tree_node *new_candidate, + struct rb_tree_node **value); +/** + * \brief Get the rightmost (greatest relative to predicate) node. + * Return the rightmost (i.e. greatest relative to predicate) node of the Red-Black tree. + */ +static inline +rb_result_t rb_tree_get_rightmost(struct rb_tree *tree, + struct rb_tree_node **rightmost) +{ + if ( (NULL == tree) || (NULL == rightmost) ) { + return RB_BAD_ARG; + } + + *rightmost = tree->rightmost; + + return RB_OK; +} + + +/** + * Find the minimum of the given tree/subtree rooted at the given node. + */ +static inline +rb_result_t __rb_tree_find_minimum(struct rb_tree_node *root, + struct rb_tree_node **min) +{ + struct rb_tree_node *x = root; + + while (x->left != NULL) { + x = x->left; + } + + *min = x; + + return RB_OK; +} + +/** + * Find the maximum of the given tree/subtree rooted at the given node. + */ +static inline +rb_result_t __rb_tree_find_maximum(struct rb_tree_node *root, + struct rb_tree_node **max) +{ + struct rb_tree_node *x = root; + + while (x->right != NULL) { + x = x->right; + } + + *max = x; + + return RB_OK; +} + +/** + * Find the successor (greater than, relative to predicate) node of the given node. + */ +static inline +rb_result_t rb_tree_find_successor(struct rb_tree *tree, + struct rb_tree_node *node, + struct rb_tree_node **successor) +{ + rb_result_t ret = RB_OK; + + RB_ASSERT_ARG(tree != NULL); + RB_ASSERT_ARG(node != NULL); + RB_ASSERT_ARG(successor != NULL); + + struct rb_tree_node *x = node; + + if (x->right != NULL) { + __rb_tree_find_minimum(x->right, successor); + goto done; + } + + struct rb_tree_node *y = x->parent; + + while (y != NULL && (x == y->right)) { + x = y; + y = y->parent; + } + + *successor = y; + +done: + return ret; +} + +/** + * Find the predecessor (less than, relative to predicate) node of the given node. + */ +static inline +rb_result_t rb_tree_find_predecessor(struct rb_tree *tree, + struct rb_tree_node *node, + struct rb_tree_node **pred) +{ + rb_result_t ret = RB_OK; + struct rb_tree_node *x = node; + + RB_ASSERT_ARG(tree != NULL); + RB_ASSERT_ARG(node != NULL); + RB_ASSERT_ARG(pred != NULL); + + if (x->left != NULL) { + __rb_tree_find_maximum(x->left, pred); + goto done; + } + + struct rb_tree_node *y = x->parent; + + while (y != NULL && (x == y->left)) { + x = y; + y = y->parent; + } + + *pred = y; + +done: + return ret; +} + +/**@} rb_functions */ + +#ifdef __cplusplus +} // extern "C" +#endif /* __cplusplus */ + +#endif /* __INCLUDED_RBTREE_H__ */ + diff --git a/src/fluent-bit/lib/monkey/deps/regex/CMakeLists.txt b/src/fluent-bit/lib/monkey/deps/regex/CMakeLists.txt new file mode 100644 index 000000000..ce1e9a3e6 --- /dev/null +++ b/src/fluent-bit/lib/monkey/deps/regex/CMakeLists.txt @@ -0,0 +1,5 @@ +set(src + re.c + ) + +add_library(regex STATIC ${src}) diff --git a/src/fluent-bit/lib/monkey/deps/regex/re.c b/src/fluent-bit/lib/monkey/deps/regex/re.c new file mode 100644 index 000000000..a93177f0a --- /dev/null +++ b/src/fluent-bit/lib/monkey/deps/regex/re.c @@ -0,0 +1,515 @@ +/* + * + * Mini regex-module inspired by Rob Pike's regex code described in: + * + * http://www.cs.princeton.edu/courses/archive/spr09/cos333/beautiful.html + * + * + * + * Supports: + * --------- + * '.' Dot, matches any character + * '^' Start anchor, matches beginning of string + * '$' End anchor, matches end of string + * '*' Asterisk, match zero or more (greedy) + * '+' Plus, match one or more (greedy) + * '?' Question, match zero or one (non-greedy) + * '[abc]' Character class, match if one of {'a', 'b', 'c'} + * '[^abc]' Inverted class, match if NOT one of {'a', 'b', 'c'} -- NOTE: feature is currently broken! + * '[a-zA-Z]' Character ranges, the character set of the ranges { a-z | A-Z } + * '\s' Whitespace, \t \f \r \n \v and spaces + * '\S' Non-whitespace + * '\w' Alphanumeric, [a-zA-Z0-9_] + * '\W' Non-alphanumeric + * '\d' Digits, [0-9] + * '\D' Non-digits + * + * + */ + + + +#include "re.h" +#include <stdio.h> +#include <ctype.h> + +/* Private function declarations: */ +static int matchpattern(regex_t* pattern, const char* text, int* matchlength); +static int matchcharclass(char c, const char* str); +static int matchstar(regex_t p, regex_t* pattern, const char* text, int* matchlength); +static int matchplus(regex_t p, regex_t* pattern, const char* text, int* matchlength); +static int matchone(regex_t p, char c); +static int matchdigit(char c); +static int matchalpha(char c); +static int matchwhitespace(char c); +static int matchmetachar(char c, const char* str); +static int matchrange(char c, const char* str); +static int matchdot(char c); +static int ismetachar(char c); + + + +/* Public functions: */ +int re_match(const char* pattern, const char* text, int* matchlength) +{ + return re_matchp(re_compile(pattern), text, matchlength); +} + +int re_matchp(re_t pattern, const char* text, int* matchlength) +{ + int matchlength_; + + if(NULL == matchlength) + { + matchlength = &matchlength_; + } + + *matchlength = 0; + if (pattern != 0) + { + if (pattern[0].type == BEGIN) + { + return ((matchpattern(&pattern[1], text, matchlength)) ? 0 : -1); + } + else + { + int idx = -1; + + do + { + idx += 1; + + if (matchpattern(pattern, text, matchlength)) + { + if (text[0] == '\0') + return -1; + + return idx; + } + } + while (*text++ != '\0'); + } + } + return -1; +} + +re_t re_compile(const char* pattern) +{ + /* The sizes of the two static arrays below substantiates the static RAM usage of this module. + MAX_REGEXP_OBJECTS is the max number of symbols in the expression. + MAX_CHAR_CLASS_LEN determines the size of buffer for chars in all char-classes in the expression. */ + static regex_t re_compiled[MAX_REGEXP_OBJECTS]; + static unsigned char ccl_buf[MAX_CHAR_CLASS_LEN]; + int ccl_bufidx = 1; + + char c; /* current char in pattern */ + int i = 0; /* index into pattern */ + int j = 0; /* index into re_compiled */ + + while (pattern[i] != '\0' && (j+1 < MAX_REGEXP_OBJECTS)) + { + c = pattern[i]; + + switch (c) + { + /* Meta-characters: */ + case '^': { re_compiled[j].type = BEGIN; } break; + case '$': { re_compiled[j].type = END; } break; + case '.': { re_compiled[j].type = DOT; } break; + case '*': { re_compiled[j].type = STAR; } break; + case '+': { re_compiled[j].type = PLUS; } break; + case '?': { re_compiled[j].type = QUESTIONMARK; } break; +/* case '|': { re_compiled[j].type = BRANCH; } break; <-- not working properly */ + + /* Escaped character-classes (\s \w ...): */ + case '\\': + { + if (pattern[i+1] != '\0') + { + /* Skip the escape-char '\\' */ + i += 1; + /* ... and check the next */ + switch (pattern[i]) + { + /* Meta-character: */ + case 'd': { re_compiled[j].type = DIGIT; } break; + case 'D': { re_compiled[j].type = NOT_DIGIT; } break; + case 'w': { re_compiled[j].type = ALPHA; } break; + case 'W': { re_compiled[j].type = NOT_ALPHA; } break; + case 's': { re_compiled[j].type = WHITESPACE; } break; + case 'S': { re_compiled[j].type = NOT_WHITESPACE; } break; + + /* Escaped character, e.g. '.' or '$' */ + default: + { + re_compiled[j].type = RE_CHAR; + re_compiled[j].u.ch = pattern[i]; + } break; + } + } + /* '\\' as last char in pattern -> invalid regular expression. */ +/* + else + { + re_compiled[j].type = RE_CHAR; + re_compiled[j].ch = pattern[i]; + } +*/ + } break; + + /* Character class: */ + case '[': + { + /* Remember where the char-buffer starts. */ + int buf_begin = ccl_bufidx; + + /* Look-ahead to determine if negated */ + if (pattern[i+1] == '^') + { + re_compiled[j].type = INV_CHAR_CLASS; + i += 1; /* Increment i to avoid including '^' in the char-buffer */ + if (pattern[i+1] == 0) /* incomplete pattern, missing non-zero char after '^' */ + { + return 0; + } + } + else + { + re_compiled[j].type = CHAR_CLASS; + } + + /* Copy characters inside [..] to buffer */ + while ( (pattern[++i] != ']') + && (pattern[i] != '\0')) /* Missing ] */ + { + if (pattern[i] == '\\') + { + if (ccl_bufidx >= MAX_CHAR_CLASS_LEN - 1) + { + //fputs("exceeded internal buffer!\n", stderr); + return 0; + } + if (pattern[i+1] == 0) /* incomplete pattern, missing non-zero char after '\\' */ + { + return 0; + } + ccl_buf[ccl_bufidx++] = pattern[i++]; + } + else if (ccl_bufidx >= MAX_CHAR_CLASS_LEN) + { + //fputs("exceeded internal buffer!\n", stderr); + return 0; + } + ccl_buf[ccl_bufidx++] = pattern[i]; + } + if (ccl_bufidx >= MAX_CHAR_CLASS_LEN) + { + /* Catches cases such as [00000000000000000000000000000000000000][ */ + //fputs("exceeded internal buffer!\n", stderr); + return 0; + } + /* Null-terminate string end */ + ccl_buf[ccl_bufidx++] = 0; + re_compiled[j].u.ccl = &ccl_buf[buf_begin]; + } break; + + /* Other characters: */ + default: + { + re_compiled[j].type = RE_CHAR; + re_compiled[j].u.ch = c; + } break; + } + /* no buffer-out-of-bounds access on invalid patterns - see https://github.com/kokke/tiny-regex-c/commit/1a279e04014b70b0695fba559a7c05d55e6ee90b */ + if (pattern[i] == 0) + { + return 0; + } + + i += 1; + j += 1; + } + /* 'UNUSED' is a sentinel used to indicate end-of-pattern */ + re_compiled[j].type = UNUSED; + + return (re_t) re_compiled; +} + +void re_print(regex_t* pattern) +{ + const char* types[] = { "UNUSED", "DOT", "BEGIN", "END", "QUESTIONMARK", "STAR", "PLUS", "RE_CHAR", "CHAR_CLASS", "INV_CHAR_CLASS", "DIGIT", "NOT_DIGIT", "ALPHA", "NOT_ALPHA", "WHITESPACE", "NOT_WHITESPACE", "BRANCH" }; + + int i; + int j; + char c; + for (i = 0; i < MAX_REGEXP_OBJECTS; ++i) + { + if (pattern[i].type == UNUSED) + { + break; + } + + printf("type: %s", types[pattern[i].type]); + if (pattern[i].type == CHAR_CLASS || pattern[i].type == INV_CHAR_CLASS) + { + printf(" ["); + for (j = 0; j < MAX_CHAR_CLASS_LEN; ++j) + { + c = pattern[i].u.ccl[j]; + if ((c == '\0') || (c == ']')) + { + break; + } + printf("%c", c); + } + printf("]"); + } + else if (pattern[i].type == RE_CHAR) + { + printf(" '%c'", pattern[i].u.ch); + } + printf("\n"); + } +} + + + +/* Private functions: */ +static int matchdigit(char c) +{ + return isdigit(c); +} +static int matchalpha(char c) +{ + return isalpha(c); +} +static int matchwhitespace(char c) +{ + return isspace(c); +} +static int matchalphanum(char c) +{ + return ((c == '_') || matchalpha(c) || matchdigit(c)); +} +static int matchrange(char c, const char* str) +{ + return ( (c != '-') + && (str[0] != '\0') + && (str[0] != '-') + && (str[1] == '-') + && (str[2] != '\0') + && ( (c >= str[0]) + && (c <= str[2]))); +} +static int matchdot(char c) +{ +#if defined(RE_DOT_MATCHES_NEWLINE) && (RE_DOT_MATCHES_NEWLINE == 1) + (void)c; + return 1; +#else + return c != '\n' && c != '\r'; +#endif +} +static int ismetachar(char c) +{ + return ((c == 's') || (c == 'S') || (c == 'w') || (c == 'W') || (c == 'd') || (c == 'D')); +} + +static int matchmetachar(char c, const char* str) +{ + switch (str[0]) + { + case 'd': return matchdigit(c); + case 'D': return !matchdigit(c); + case 'w': return matchalphanum(c); + case 'W': return !matchalphanum(c); + case 's': return matchwhitespace(c); + case 'S': return !matchwhitespace(c); + default: return (c == str[0]); + } +} + +static int matchcharclass(char c, const char* str) +{ + do + { + if (matchrange(c, str)) + { + return 1; + } + else if (str[0] == '\\') + { + /* Escape-char: increment str-ptr and match on next char */ + str += 1; + if (matchmetachar(c, str)) + { + return 1; + } + else if ((c == str[0]) && !ismetachar(c)) + { + return 1; + } + } + else if (c == str[0]) + { + if (c == '-') + { + return ((str[-1] == '\0') || (str[1] == '\0')); + } + else + { + return 1; + } + } + } + while (*str++ != '\0'); + + return 0; +} + +static int matchone(regex_t p, char c) +{ + switch (p.type) + { + case DOT: return matchdot(c); + case CHAR_CLASS: return matchcharclass(c, (const char*)p.u.ccl); + case INV_CHAR_CLASS: return !matchcharclass(c, (const char*)p.u.ccl); + case DIGIT: return matchdigit(c); + case NOT_DIGIT: return !matchdigit(c); + case ALPHA: return matchalphanum(c); + case NOT_ALPHA: return !matchalphanum(c); + case WHITESPACE: return matchwhitespace(c); + case NOT_WHITESPACE: return !matchwhitespace(c); + default: return (p.u.ch == c); + } +} + +static int matchstar(regex_t p, regex_t* pattern, const char* text, int* matchlength) +{ + int prelen = *matchlength; + const char* prepoint = text; + while ((text[0] != '\0') && matchone(p, *text)) + { + text++; + (*matchlength)++; + } + while (text >= prepoint) + { + if (matchpattern(pattern, text--, matchlength)) + return 1; + (*matchlength)--; + } + + *matchlength = prelen; + return 0; +} + +static int matchplus(regex_t p, regex_t* pattern, const char* text, int* matchlength) +{ + const char* prepoint = text; + while ((text[0] != '\0') && matchone(p, *text)) + { + text++; + (*matchlength)++; + } + while (text > prepoint) + { + if (matchpattern(pattern, text--, matchlength)) + return 1; + (*matchlength)--; + } + + return 0; +} + +static int matchquestion(regex_t p, regex_t* pattern, const char* text, int* matchlength) +{ + if (p.type == UNUSED) + return 1; + if (matchpattern(pattern, text, matchlength)) + return 1; + if (*text && matchone(p, *text++)) + { + if (matchpattern(pattern, text, matchlength)) + { + (*matchlength)++; + return 1; + } + } + return 0; +} + + +#if 0 + +/* Recursive matching */ +static int matchpattern(regex_t* pattern, const char* text, int *matchlength) +{ + int pre = *matchlength; + if ((pattern[0].type == UNUSED) || (pattern[1].type == QUESTIONMARK)) + { + return matchquestion(pattern[1], &pattern[2], text, matchlength); + } + else if (pattern[1].type == STAR) + { + return matchstar(pattern[0], &pattern[2], text, matchlength); + } + else if (pattern[1].type == PLUS) + { + return matchplus(pattern[0], &pattern[2], text, matchlength); + } + else if ((pattern[0].type == END) && pattern[1].type == UNUSED) + { + return text[0] == '\0'; + } + else if ((text[0] != '\0') && matchone(pattern[0], text[0])) + { + (*matchlength)++; + return matchpattern(&pattern[1], text+1); + } + else + { + *matchlength = pre; + return 0; + } +} + +#else + +/* Iterative matching */ +static int matchpattern(regex_t* pattern, const char* text, int* matchlength) +{ + int pre = *matchlength; + do + { + if ((pattern[0].type == UNUSED) || (pattern[1].type == QUESTIONMARK)) + { + return matchquestion(pattern[0], &pattern[2], text, matchlength); + } + else if (pattern[1].type == STAR) + { + return matchstar(pattern[0], &pattern[2], text, matchlength); + } + else if (pattern[1].type == PLUS) + { + return matchplus(pattern[0], &pattern[2], text, matchlength); + } + else if ((pattern[0].type == END) && pattern[1].type == UNUSED) + { + return (text[0] == '\0'); + } +/* Branching is not working properly + else if (pattern[1].type == BRANCH) + { + return (matchpattern(pattern, text) || matchpattern(&pattern[2], text)); + } +*/ + (*matchlength)++; + } + while ((text[0] != '\0') && matchone(*pattern++, *text++)); + + *matchlength = pre; + return 0; +} + +#endif diff --git a/src/fluent-bit/lib/monkey/deps/regex/re.h b/src/fluent-bit/lib/monkey/deps/regex/re.h new file mode 100644 index 000000000..34363e86b --- /dev/null +++ b/src/fluent-bit/lib/monkey/deps/regex/re.h @@ -0,0 +1,87 @@ +/* + * + * Mini regex-module inspired by Rob Pike's regex code described in: + * + * http://www.cs.princeton.edu/courses/archive/spr09/cos333/beautiful.html + * + * + * + * Supports: + * --------- + * '.' Dot, matches any character + * '^' Start anchor, matches beginning of string + * '$' End anchor, matches end of string + * '*' Asterisk, match zero or more (greedy) + * '+' Plus, match one or more (greedy) + * '?' Question, match zero or one (non-greedy) + * '[abc]' Character class, match if one of {'a', 'b', 'c'} + * '[^abc]' Inverted class, match if NOT one of {'a', 'b', 'c'} -- NOTE: feature is currently broken! + * '[a-zA-Z]' Character ranges, the character set of the ranges { a-z | A-Z } + * '\s' Whitespace, \t \f \r \n \v and spaces + * '\S' Non-whitespace + * '\w' Alphanumeric, [a-zA-Z0-9_] + * '\W' Non-alphanumeric + * '\d' Digits, [0-9] + * '\D' Non-digits + * + * + */ + +#ifndef _TINY_REGEX_C +#define _TINY_REGEX_C + + +#ifndef RE_DOT_MATCHES_NEWLINE +/* Define to 0 if you DON'T want '.' to match '\r' + '\n' */ +#define RE_DOT_MATCHES_NEWLINE 1 +#endif + +#ifdef __cplusplus +extern "C"{ +#endif + + +/* Definitions: */ + +/* This was incremented because everything counts as a symbol, even literals and because + * of that the longer regular expressions matched wrong input text because they were only + * partially compiled + */ +#define MAX_REGEXP_OBJECTS 512 /* Max number of regex symbols in expression. */ +#define MAX_CHAR_CLASS_LEN 40 /* Max length of character-class buffer in. */ + + +enum { UNUSED, DOT, BEGIN, END, QUESTIONMARK, STAR, PLUS, RE_CHAR, CHAR_CLASS, INV_CHAR_CLASS, DIGIT, NOT_DIGIT, ALPHA, NOT_ALPHA, WHITESPACE, NOT_WHITESPACE, /* BRANCH */ }; + +typedef struct regex_t +{ + unsigned char type; /* CHAR, STAR, etc. */ + union + { + unsigned char ch; /* the character itself */ + unsigned char* ccl; /* OR a pointer to characters in class */ + } u; +} regex_t; + +/* Typedef'd pointer to get abstract datatype. */ +typedef struct regex_t* re_t; + +#define REGEXP_SIZE (MAX_REGEXP_OBJECTS * sizeof(struct regex_t)) + +/* Compile regex string pattern to a regex_t-array. */ +re_t re_compile(const char* pattern); + + +/* Find matches of the compiled pattern inside text. */ +int re_matchp(re_t pattern, const char* text, int* matchlength); + + +/* Find matches of the txt pattern inside text (will compile automatically first). */ +int re_match(const char* pattern, const char* text, int* matchlength); + + +#ifdef __cplusplus +} +#endif + +#endif /* ifndef _TINY_REGEX_C */ |