diff options
41 files changed, 1936 insertions, 160 deletions
diff --git a/configure.in b/configure.in index f0cdcde1abb..61ae233be06 100644 --- a/configure.in +++ b/configure.in @@ -2481,7 +2481,7 @@ AC_SUBST(MAKE_BINARY_DISTRIBUTION_OPTIONS) # Output results AC_CONFIG_FILES(Makefile extra/Makefile mysys/Makefile dnl unittest/Makefile unittest/mytap/Makefile unittest/mytap/t/Makefile dnl - unittest/mysys/Makefile unittest/examples/Makefile dnl + unittest/mysys/Makefile unittest/examples/Makefile unittest/maria/Makefile dnl strings/Makefile regex/Makefile storage/Makefile dnl man/Makefile BUILD/Makefile vio/Makefile dnl libmysql/Makefile client/Makefile dnl diff --git a/include/Makefile.am b/include/Makefile.am index bf7dcd265be..d5e75d31593 100644 --- a/include/Makefile.am +++ b/include/Makefile.am @@ -23,7 +23,7 @@ pkginclude_HEADERS = my_dbug.h m_string.h my_sys.h my_list.h my_xml.h \ my_getopt.h sslopt-longopts.h my_dir.h typelib.h \ sslopt-vars.h sslopt-case.h sql_common.h keycache.h \ mysql_time.h mysql/plugin.h $(BUILT_SOURCES) -noinst_HEADERS = config-win.h config-netware.h \ +noinst_HEADERS = config-win.h config-netware.h lf.h \ heap.h maria.h myisamchk.h my_bitmap.h my_uctype.h \ myisam.h myisampack.h myisammrg.h ft_global.h\ mysys_err.h my_base.h help_start.h help_end.h \ diff --git a/include/atomic/nolock.h b/include/atomic/nolock.h index 1151a334b06..21f41484ac9 100644 --- a/include/atomic/nolock.h +++ b/include/atomic/nolock.h @@ -14,19 +14,20 @@ along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ -#if defined(__i386__) || defined(_M_IX86) - -#ifdef MY_ATOMIC_MODE_DUMMY -# define LOCK "" -#else -# define LOCK "lock" -#endif - -#ifdef __GNUC__ -#include "x86-gcc.h" -#elif defined(_MSC_VER) -#include "x86-msvc.h" -#endif +#if defined(__i386__) || defined(_M_IX86) || defined(__x86_64__) + +# ifdef MY_ATOMIC_MODE_DUMMY +# define LOCK "" +# else +# define LOCK "lock" +# endif + +# ifdef __GNUC__ +# include "x86-gcc.h" +# elif defined(_MSC_VER) +# error Broken! +# include "x86-msvc.h" +# endif #endif #ifdef make_atomic_cas_body diff --git a/include/atomic/rwlock.h b/include/atomic/rwlock.h index 12d0dd3f069..3d8edb9e27e 100644 --- a/include/atomic/rwlock.h +++ b/include/atomic/rwlock.h @@ -14,7 +14,7 @@ along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ -typedef struct {pthread_rwlock_t rw;} my_atomic_rwlock_t; +typedef struct {pthread_mutex_t rw;} my_atomic_rwlock_t; #ifdef MY_ATOMIC_MODE_DUMMY /* @@ -32,13 +32,18 @@ typedef struct {pthread_rwlock_t rw;} my_atomic_rwlock_t; #define my_atomic_rwlock_wrunlock(name) #define MY_ATOMIC_MODE "dummy (non-atomic)" #else -#define my_atomic_rwlock_destroy(name) pthread_rwlock_destroy(& (name)->rw) -#define my_atomic_rwlock_init(name) pthread_rwlock_init(& (name)->rw, 0) -#define my_atomic_rwlock_rdlock(name) pthread_rwlock_rdlock(& (name)->rw) -#define my_atomic_rwlock_wrlock(name) pthread_rwlock_wrlock(& (name)->rw) -#define my_atomic_rwlock_rdunlock(name) pthread_rwlock_unlock(& (name)->rw) -#define my_atomic_rwlock_wrunlock(name) pthread_rwlock_unlock(& (name)->rw) -#define MY_ATOMIC_MODE "rwlocks" +/* + we're using read-write lock macros but map them to mutex locks, and they're + faster. Still, having semantically rich API we can change the + underlying implementation, if necessary. +*/ +#define my_atomic_rwlock_destroy(name) pthread_mutex_destroy(& (name)->rw) +#define my_atomic_rwlock_init(name) pthread_mutex_init(& (name)->rw, 0) +#define my_atomic_rwlock_rdlock(name) pthread_mutex_lock(& (name)->rw) +#define my_atomic_rwlock_wrlock(name) pthread_mutex_lock(& (name)->rw) +#define my_atomic_rwlock_rdunlock(name) pthread_mutex_unlock(& (name)->rw) +#define my_atomic_rwlock_wrunlock(name) pthread_mutex_unlock(& (name)->rw) +#define MY_ATOMIC_MODE "mutex" #endif #define make_atomic_add_body(S) int ## S sav; sav= *a; *a+= v; v=sav; diff --git a/include/atomic/x86-gcc.h b/include/atomic/x86-gcc.h index 5a72f318a61..3f0a82a9400 100644 --- a/include/atomic/x86-gcc.h +++ b/include/atomic/x86-gcc.h @@ -20,10 +20,18 @@ architectures support double-word (128-bit) cas. */ -#ifdef MY_ATOMIC_NO_XADD -#define MY_ATOMIC_MODE "gcc-x86" LOCK "-no-xadd" +#ifdef __x86_64__ +# ifdef MY_ATOMIC_NO_XADD +# define MY_ATOMIC_MODE "gcc-amd64" LOCK "-no-xadd" +# else +# define MY_ATOMIC_MODE "gcc-amd64" LOCK +# endif #else -#define MY_ATOMIC_MODE "gcc-x86" LOCK +# ifdef MY_ATOMIC_NO_XADD +# define MY_ATOMIC_MODE "gcc-x86" LOCK "-no-xadd" +# else +# define MY_ATOMIC_MODE "gcc-x86" LOCK +# endif #endif /* fix -ansi errors while maintaining readability */ @@ -54,6 +62,9 @@ asm volatile (LOCK "; cmpxchg %2, %0" \ : "+m" (*a), "+a" (ret): "r" (ret)) #define make_atomic_store_body(S) \ - asm volatile ("; xchg %0, %1;" : "+m" (*a) : "r" (v)) + asm volatile ("; xchg %0, %1;" : "+m" (*a), "+r" (v)) #endif +/* TODO test on intel whether the below helps. on AMD it makes no difference */ +//#define LF_BACKOFF ({asm volatile ("rep; nop"); 1; }) + diff --git a/include/lf.h b/include/lf.h new file mode 100644 index 00000000000..6a5047f6052 --- /dev/null +++ b/include/lf.h @@ -0,0 +1,238 @@ + +/* + TODO + 1. copyright + 6. reduce the number of memory barriers +*/ + +#ifndef _lf_h +#define _lf_h + +#include <my_atomic.h> + +/* + Generic helpers +*/ + +#define lock_wrap(f,t,proto_args, args, lock) \ +t _ ## f proto_args; \ +static inline t f proto_args \ +{ \ + t ret; \ + my_atomic_rwlock_wrlock(lock); \ + ret= _ ## f args; \ + my_atomic_rwlock_wrunlock(lock); \ + return ret; \ +} + +#define lock_wrap_void(f,proto_args, args, lock) \ +void _ ## f proto_args; \ +static inline void f proto_args \ +{ \ + my_atomic_rwlock_wrlock(lock); \ + _ ## f args; \ + my_atomic_rwlock_wrunlock(lock); \ +} + +#define nolock_wrap(f,t,proto_args, args) \ +t _ ## f proto_args; \ +static inline t f proto_args \ +{ \ + return _ ## f args; \ +} + +#define nolock_wrap_void(f,proto_args, args) \ +void _ ## f proto_args; \ +static inline void f proto_args \ +{ \ + _ ## f args; \ +} + +/* + dynamic array + + 4 levels of 256 elements each mean 4311810304 elements in an array - it + should be enough for a while +*/ +#define LF_DYNARRAY_LEVEL_LENGTH 256 +#define LF_DYNARRAY_LEVELS 4 + +typedef struct { + void * volatile level[LF_DYNARRAY_LEVELS]; + uint size_of_element; + my_atomic_rwlock_t lock; +} LF_DYNARRAY; + +typedef int (*lf_dynarray_func)(void *, void *); + +void lf_dynarray_init(LF_DYNARRAY *array, uint element_size); +void lf_dynarray_destroy(LF_DYNARRAY *array); + +nolock_wrap(lf_dynarray_nr, int, + (LF_DYNARRAY *array, void *el), + (array,el)); + +nolock_wrap(lf_dynarray_value, void *, + (LF_DYNARRAY *array, uint idx), + (array,idx)); + +lock_wrap(lf_dynarray_lvalue, void *, + (LF_DYNARRAY *array, uint idx), + (array,idx), + &array->lock); +nolock_wrap(lf_dynarray_iterate, int, + (LF_DYNARRAY *array, lf_dynarray_func func, void *arg), + (array,func,arg)); + +/* + pin manager for memory allocator +*/ + +#define LF_PINBOX_PINS 3 +#define LF_PURGATORY_SIZE 11 + +typedef void lf_pinbox_free_func(void *, void *); + +typedef struct { + LF_DYNARRAY pinstack; + lf_pinbox_free_func *free_func; + void * free_func_arg; + uint32 volatile pinstack_top_ver; /* this is a versioned pointer */ + uint32 volatile pins_in_stack; /* number of elements in array */ +} LF_PINBOX; + +/* we want sizeof(LF_PINS) to be close to 128 to avoid false sharing */ +typedef struct { + void * volatile pin[LF_PINBOX_PINS]; + void * purgatory[LF_PURGATORY_SIZE]; + LF_PINBOX *pinbox; + uint32 purgatory_count; + uint32 volatile link; + char pad[128-sizeof(uint32)*2 + -sizeof(void *)*(LF_PINBOX_PINS+LF_PURGATORY_SIZE+1)]; +} LF_PINS; + +#define lf_lock_by_pins(PINS) \ + my_atomic_rwlock_wrlock(&(PINS)->pinbox->pinstack.lock) +#define lf_unlock_by_pins(PINS) \ + my_atomic_rwlock_wrunlock(&(PINS)->pinbox->pinstack.lock) + +/* + compile-time assert, to require "no less than N" pins + it's enough if it'll fail on at least one compiler, so + we'll enable it on GCC only, which supports zero-length arrays. +*/ +#if defined(__GNUC__) && defined(MY_LF_EXTRA_DEBUG) +#define LF_REQUIRE_PINS(N) \ + static const char require_pins[LF_PINBOX_PINS-N]; \ + static const int LF_NUM_PINS_IN_THIS_FILE=N; +#define _lf_pin(PINS, PIN, ADDR) \ + ( \ + my_atomic_storeptr(&(PINS)->pin[PIN], (ADDR)), \ + assert(PIN < LF_NUM_PINS_IN_THIS_FILE) \ + ) +#else +#define LF_REQUIRE_PINS(N) +#define _lf_pin(PINS, PIN, ADDR) my_atomic_storeptr(&(PINS)->pin[PIN], (ADDR)) +#endif + +#define _lf_unpin(PINS, PIN) _lf_pin(PINS, PIN, NULL) +#define lf_pin(PINS, PIN, ADDR) \ + do { \ + lf_lock_by_pins(PINS); \ + _lf_pin(PINS, PIN, ADDR); \ + lf_unlock_by_pins(PINS); \ + } while (0) +#define lf_unpin(PINS, PIN) lf_pin(PINS, PIN, NULL) + +void lf_pinbox_init(LF_PINBOX *pinbox, lf_pinbox_free_func *free_func, + void * free_func_arg); +void lf_pinbox_destroy(LF_PINBOX *pinbox); + +lock_wrap(lf_pinbox_get_pins, LF_PINS *, + (LF_PINBOX *pinbox), + (pinbox), + &pinbox->pinstack.lock); +lock_wrap_void(lf_pinbox_put_pins, + (LF_PINS *pins), + (pins), + &pins->pinbox->pinstack.lock); +#if 0 +lock_wrap_void(lf_pinbox_real_free, + (LF_PINS *pins), + (pins), + &pins->pinbox->pinstack.lock); +#endif +lock_wrap_void(lf_pinbox_free, + (LF_PINS *pins, void *addr), + (pins,addr), + &pins->pinbox->pinstack.lock); + +/* + memory allocator +*/ + +typedef struct st_lf_allocator { + LF_PINBOX pinbox; + void * volatile top; + uint element_size; + uint32 volatile mallocs; +} LF_ALLOCATOR; + +void lf_alloc_init(LF_ALLOCATOR *allocator, uint size); +void lf_alloc_destroy(LF_ALLOCATOR *allocator); +uint lf_alloc_in_pool(LF_ALLOCATOR *allocator); +#define _lf_alloc_free(PINS, PTR) _lf_pinbox_free((PINS), (PTR)) +#define lf_alloc_free(PINS, PTR) lf_pinbox_free((PINS), (PTR)) +#define _lf_alloc_get_pins(ALLOC) _lf_pinbox_get_pins(&(ALLOC)->pinbox) +#define lf_alloc_get_pins(ALLOC) lf_pinbox_get_pins(&(ALLOC)->pinbox) +#define _lf_alloc_put_pins(PINS) _lf_pinbox_put_pins(PINS) +#define lf_alloc_put_pins(PINS) lf_pinbox_put_pins(PINS) +#define lf_alloc_real_free(ALLOC,ADDR) my_free((gptr)(ADDR), MYF(0)) + +lock_wrap(lf_alloc_new, void *, + (LF_PINS *pins), + (pins), + &pins->pinbox->pinstack.lock); + +/* + extendible hash +*/ +#include <hash.h> + +#define LF_HASH_UNIQUE 1 + +typedef struct { + LF_DYNARRAY array; /* hash itself */ + LF_ALLOCATOR alloc; /* allocator for elements */ + hash_get_key get_key; /* see HASH */ + CHARSET_INFO *charset; /* see HASH */ + uint key_offset, key_length; /* see HASH */ + uint element_size, flags; /* LF_HASH_UNIQUE, etc */ + int32 volatile size; /* size of array */ + int32 volatile count; /* number of elements in the hash */ +} LF_HASH; + +void lf_hash_init(LF_HASH *hash, uint element_size, uint flags, + uint key_offset, uint key_length, hash_get_key get_key, + CHARSET_INFO *charset); +void lf_hash_destroy(LF_HASH *hash); +int lf_hash_insert(LF_HASH *hash, LF_PINS *pins, const void *data); +void *lf_hash_search(LF_HASH *hash, LF_PINS *pins, const void *key, uint keylen); +int lf_hash_delete(LF_HASH *hash, LF_PINS *pins, const void *key, uint keylen); +#define _lf_hash_get_pins(HASH) _lf_alloc_get_pins(&(HASH)->alloc) +#define lf_hash_get_pins(HASH) lf_alloc_get_pins(&(HASH)->alloc) +#define _lf_hash_put_pins(PINS) _lf_pinbox_put_pins(PINS) +#define lf_hash_put_pins(PINS) lf_pinbox_put_pins(PINS) + +/* + cleanup +*/ + +#undef lock_wrap_void +#undef lock_wrap +#undef nolock_wrap_void +#undef nolock_wrap + +#endif + diff --git a/include/my_atomic.h b/include/my_atomic.h index 9a319f84451..d3e4e0055d3 100644 --- a/include/my_atomic.h +++ b/include/my_atomic.h @@ -36,7 +36,7 @@ #ifdef HAVE_INLINE #define make_atomic_add(S) \ -static inline int ## S my_atomic_add ## S( \ +STATIC_INLINE int ## S my_atomic_add ## S( \ int ## S volatile *a, int ## S v) \ { \ make_atomic_add_body(S); \ @@ -44,7 +44,7 @@ static inline int ## S my_atomic_add ## S( \ } #define make_atomic_swap(S) \ -static inline int ## S my_atomic_swap ## S( \ +STATIC_INLINE int ## S my_atomic_swap ## S( \ int ## S volatile *a, int ## S v) \ { \ make_atomic_swap_body(S); \ @@ -52,7 +52,7 @@ static inline int ## S my_atomic_swap ## S( \ } #define make_atomic_cas(S) \ -static inline int my_atomic_cas ## S(int ## S volatile *a, \ +STATIC_INLINE int my_atomic_cas ## S(int ## S volatile *a, \ int ## S *cmp, int ## S set) \ { \ int8 ret; \ @@ -61,7 +61,7 @@ static inline int my_atomic_cas ## S(int ## S volatile *a, \ } #define make_atomic_load(S) \ -static inline int ## S my_atomic_load ## S(int ## S volatile *a) \ +STATIC_INLINE int ## S my_atomic_load ## S(int ## S volatile *a) \ { \ int ## S ret; \ make_atomic_load_body(S); \ @@ -69,7 +69,7 @@ static inline int ## S my_atomic_load ## S(int ## S volatile *a) \ } #define make_atomic_store(S) \ -static inline void my_atomic_store ## S( \ +STATIC_INLINE void my_atomic_store ## S( \ int ## S volatile *a, int ## S v) \ { \ make_atomic_store_body(S); \ @@ -135,6 +135,10 @@ make_atomic_swap(ptr) #undef _atomic_h_cleanup_ #endif +#ifndef LF_BACKOFF +#define LF_BACKOFF (1) +#endif + #if SIZEOF_CHARP == SIZEOF_INT typedef int intptr; #elif SIZEOF_CHARP == SIZEOF_LONG diff --git a/include/my_bit.h b/include/my_bit.h new file mode 100644 index 00000000000..71bbe2d4ba3 --- /dev/null +++ b/include/my_bit.h @@ -0,0 +1,107 @@ +/* + Some useful bit functions +*/ + +#ifdef HAVE_INLINE + +extern const char _my_bits_nbits[256]; +extern const uchar _my_bits_reverse_table[256]; + +/* + Find smallest X in 2^X >= value + This can be used to divide a number with value by doing a shift instead +*/ + +STATIC_INLINE uint my_bit_log2(ulong value) +{ + uint bit; + for (bit=0 ; value > 1 ; value>>=1, bit++) ; + return bit; +} + +STATIC_INLINE uint my_count_bits(ulonglong v) +{ +#if SIZEOF_LONG_LONG > 4 + /* The following code is a bit faster on 16 bit machines than if we would + only shift v */ + ulong v2=(ulong) (v >> 32); + return (uint) (uchar) (_my_bits_nbits[(uchar) v] + + _my_bits_nbits[(uchar) (v >> 8)] + + _my_bits_nbits[(uchar) (v >> 16)] + + _my_bits_nbits[(uchar) (v >> 24)] + + _my_bits_nbits[(uchar) (v2)] + + _my_bits_nbits[(uchar) (v2 >> 8)] + + _my_bits_nbits[(uchar) (v2 >> 16)] + + _my_bits_nbits[(uchar) (v2 >> 24)]); +#else + return (uint) (uchar) (_my_bits_nbits[(uchar) v] + + _my_bits_nbits[(uchar) (v >> 8)] + + _my_bits_nbits[(uchar) (v >> 16)] + + _my_bits_nbits[(uchar) (v >> 24)]); +#endif +} + +STATIC_INLINE uint my_count_bits_ushort(ushort v) +{ + return _my_bits_nbits[v]; +} + + +/* + Next highest power of two + + SYNOPSIS + my_round_up_to_next_power() + v Value to check + + RETURN + Next or equal power of 2 + Note: 0 will return 0 + + NOTES + Algorithm by Sean Anderson, according to: + http://graphics.stanford.edu/~seander/bithacks.html + (Orignal code public domain) + + Comments shows how this works with 01100000000000000000000000001011 +*/ + +STATIC_INLINE uint32 my_round_up_to_next_power(uint32 v) +{ + v--; /* 01100000000000000000000000001010 */ + v|= v >> 1; /* 01110000000000000000000000001111 */ + v|= v >> 2; /* 01111100000000000000000000001111 */ + v|= v >> 4; /* 01111111110000000000000000001111 */ + v|= v >> 8; /* 01111111111111111100000000001111 */ + v|= v >> 16; /* 01111111111111111111111111111111 */ + return v+1; /* 10000000000000000000000000000000 */ +} + +STATIC_INLINE uint32 my_clear_highest_bit(uint32 v) +{ + uint32 w=v >> 1; + w|= w >> 1; + w|= w >> 2; + w|= w >> 4; + w|= w >> 8; + w|= w >> 16; + return v & w; +} + +STATIC_INLINE uint32 my_reverse_bits(uint key) +{ + return + (_my_bits_reverse_table[ key & 255] << 24) | + (_my_bits_reverse_table[(key>> 8) & 255] << 16) | + (_my_bits_reverse_table[(key>>16) & 255] << 8) | + _my_bits_reverse_table[(key>>24) ]; +} + +#else +extern uint my_bit_log2(ulong value); +extern uint32 my_round_up_to_next_power(uint32 v); +uint32 my_clear_highest_bit(uint32 v); +uint32 my_reverse_bits(uint key); +extern uint my_count_bits(ulonglong v); +extern uint my_count_bits_ushort(ushort v); +#endif diff --git a/include/my_global.h b/include/my_global.h index 539a2ea644f..85fa92663fa 100644 --- a/include/my_global.h +++ b/include/my_global.h @@ -192,6 +192,8 @@ #endif #undef inline_test_2 #undef inline_test_1 +/* helper macro for "instantiating" inline functions */ +#define STATIC_INLINE static inline /* The following macros are used to control inlining a bit more than diff --git a/include/my_sys.h b/include/my_sys.h index 4b31f6bcd2b..c0698d0640e 100644 --- a/include/my_sys.h +++ b/include/my_sys.h @@ -216,6 +216,7 @@ extern int (*error_handler_hook)(uint my_err, const char *str,myf MyFlags); extern int (*fatal_error_handler_hook)(uint my_err, const char *str, myf MyFlags); extern uint my_file_limit; +extern ulong my_thread_stack_size; #ifdef HAVE_LARGE_PAGES extern my_bool my_use_large_pages; @@ -821,10 +822,6 @@ extern int packfrm(const void *, uint, const void **, uint *); extern int unpackfrm(const void **, uint *, const void *); extern ha_checksum my_checksum(ha_checksum crc, const byte *mem, uint count); -extern uint my_bit_log2(ulong value); -extern uint32 my_round_up_to_next_power(uint32 v); -extern uint my_count_bits(ulonglong v); -extern uint my_count_bits_ushort(ushort v); extern void my_sleep(ulong m_seconds); extern ulong crc32(ulong crc, const uchar *buf, uint len); extern uint my_set_max_open_files(uint files); @@ -840,7 +837,7 @@ extern int my_getncpus(); #ifndef MAP_NOSYNC #define MAP_NOSYNC 0 #endif -#ifndef MAP_NORESERVE +#ifndef MAP_NORESERVE #define MAP_NORESERVE 0 /* For irix and AIX */ #endif diff --git a/mysys/Makefile.am b/mysys/Makefile.am index edafd128eb0..2f8b34dc301 100644 --- a/mysys/Makefile.am +++ b/mysys/Makefile.am @@ -32,7 +32,8 @@ libmysys_a_SOURCES = my_init.c my_getwd.c mf_getdate.c my_mmap.c \ mf_tempdir.c my_lock.c mf_brkhant.c my_alarm.c \ my_malloc.c my_realloc.c my_once.c mulalloc.c \ my_alloc.c safemalloc.c my_new.cc \ - my_vle.c my_atomic.c \ + my_vle.c my_atomic.c lf_hash.c \ + lf_dynarray.c lf_alloc-pin.c \ my_fopen.c my_fstream.c my_getsystime.c \ my_error.c errors.c my_div.c my_messnc.c \ mf_format.c mf_same.c mf_dirname.c mf_fn_ext.c \ diff --git a/mysys/lf_alloc-pin.c b/mysys/lf_alloc-pin.c new file mode 100644 index 00000000000..cf1612b73d1 --- /dev/null +++ b/mysys/lf_alloc-pin.c @@ -0,0 +1,319 @@ +/* Copyright (C) 2000 MySQL AB + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ + +/* + concurrent allocator based on pinning addresses + + strictly speaking it's not lock-free, as it can be blocked + if a thread's purgatory is full and all addresses from there + are pinned. + + But until the above happens, it's wait-free. + + It can be made strictly wait-free by increasing purgatory size. + If it's larger than pins_in_stack*LF_PINBOX_PINS, then apocalyptical + condition above will never happen. But than the memory requirements + will be O(pins_in_stack^2). + + Note, that for large purgatory sizes it makes sense to remove + purgatory array, and link objects in a list using embedded pointer. + + TODO test with more than 256 threads + TODO test w/o alloca +*/ + +#include <my_global.h> +#include <my_sys.h> +#include <lf.h> + +#define LF_PINBOX_MAX_PINS 65536 + +static void _lf_pinbox_real_free(LF_PINS *pins); + +void lf_pinbox_init(LF_PINBOX *pinbox, lf_pinbox_free_func *free_func, + void *free_func_arg) +{ + DBUG_ASSERT(sizeof(LF_PINS) == 128); + lf_dynarray_init(&pinbox->pinstack, sizeof(LF_PINS)); + pinbox->pinstack_top_ver=0; + pinbox->pins_in_stack=0; + pinbox->free_func=free_func; + pinbox->free_func_arg=free_func_arg; +} + +void lf_pinbox_destroy(LF_PINBOX *pinbox) +{ + lf_dynarray_destroy(&pinbox->pinstack); +} + +LF_PINS *_lf_pinbox_get_pins(LF_PINBOX *pinbox) +{ + uint32 pins, next, top_ver; + LF_PINS *el; + + top_ver=pinbox->pinstack_top_ver; + do + { + if (!(pins=top_ver % LF_PINBOX_MAX_PINS)) + { + pins=my_atomic_add32(&pinbox->pins_in_stack, 1)+1; + el=(LF_PINS *)_lf_dynarray_lvalue(&pinbox->pinstack, pins); + break; + } + el=(LF_PINS *)_lf_dynarray_value(&pinbox->pinstack, pins); + next=el->link; + } while (!my_atomic_cas32(&pinbox->pinstack_top_ver, &top_ver, + top_ver-pins+next+LF_PINBOX_MAX_PINS)); + el->link=pins; + el->purgatory_count=0; + el->pinbox=pinbox; + return el; +} + +void _lf_pinbox_put_pins(LF_PINS *pins) +{ + LF_PINBOX *pinbox=pins->pinbox; + uint32 top_ver, nr; + nr=pins->link; +#ifdef MY_LF_EXTRA_DEBUG + { + int i; + for (i=0; i < LF_PINBOX_PINS; i++) + assert(pins->pin[i] == 0); + } +#endif + while (pins->purgatory_count) + { + _lf_pinbox_real_free(pins); + if (pins->purgatory_count && my_getncpus() == 1) + { + my_atomic_rwlock_wrunlock(&pins->pinbox->pinstack.lock); + pthread_yield(); + my_atomic_rwlock_wrlock(&pins->pinbox->pinstack.lock); + } + } + top_ver=pinbox->pinstack_top_ver; + if (nr == pinbox->pins_in_stack) + { + int32 tmp=nr; + if (my_atomic_cas32(&pinbox->pins_in_stack, &tmp, tmp-1)) + goto ret; + } + + do + { + pins->link=top_ver % LF_PINBOX_MAX_PINS; + } while (!my_atomic_cas32(&pinbox->pinstack_top_ver, &top_ver, + top_ver-pins->link+nr+LF_PINBOX_MAX_PINS)); +ret: + return; +} + +static int ptr_cmp(void **a, void **b) +{ + return *a < *b ? -1 : *a == *b ? 0 : 1; +} + +void _lf_pinbox_free(LF_PINS *pins, void *addr) +{ + while (pins->purgatory_count == LF_PURGATORY_SIZE) + { + _lf_pinbox_real_free(pins); + if (pins->purgatory_count == LF_PURGATORY_SIZE && my_getncpus() == 1) + { + my_atomic_rwlock_wrunlock(&pins->pinbox->pinstack.lock); + pthread_yield(); + my_atomic_rwlock_wrlock(&pins->pinbox->pinstack.lock); + } + } + pins->purgatory[pins->purgatory_count++]=addr; +} + +struct st_harvester { + void **granary; + int npins; +}; + +static int harvest_pins(LF_PINS *el, struct st_harvester *hv) +{ + int i; + LF_PINS *el_end= el+min(hv->npins, LF_DYNARRAY_LEVEL_LENGTH); + for (; el < el_end; el++) + { + for (i= 0; i < LF_PINBOX_PINS; i++) + { + void *p= el->pin[i]; + if (p) + *hv->granary++= p; + } + } + hv->npins-= LF_DYNARRAY_LEVEL_LENGTH; + return 0; +} + +static int match_pins(LF_PINS *el, void *addr) +{ + int i; + LF_PINS *el_end= el+LF_DYNARRAY_LEVEL_LENGTH; + for (; el < el_end; el++) + for (i= 0; i < LF_PINBOX_PINS; i++) + if (el->pin[i] == addr) + return 1; + return 0; +} + +static void _lf_pinbox_real_free(LF_PINS *pins) +{ + int npins; + void **addr=0; + void **start, **cur, **end=pins->purgatory+pins->purgatory_count; + LF_PINBOX *pinbox=pins->pinbox; + + npins=pinbox->pins_in_stack+1; + +#ifdef HAVE_ALLOCA + /* create a sorted list of pinned addresses, to speed up searches */ + if (sizeof(void *)*LF_PINBOX_PINS*npins < my_thread_stack_size) + { + struct st_harvester hv; + addr= (void **) alloca(sizeof(void *)*LF_PINBOX_PINS*npins); + hv.granary=addr; + hv.npins=npins; + _lf_dynarray_iterate(&pinbox->pinstack, + (lf_dynarray_func)harvest_pins, &hv); + + npins=hv.granary-addr; + if (npins) + qsort(addr, npins, sizeof(void *), (qsort_cmp)ptr_cmp); + } +#endif + + start= cur= pins->purgatory; + end= start+pins->purgatory_count; + for (; cur < end; cur++) + { + if (npins) + { + if (addr) + { + void **a,**b,**c; + for (a=addr, b=addr+npins-1, c=a+(b-a)/2; b-a>1; c=a+(b-a)/2) + if (*cur == *c) + a=b=c; + else if (*cur > *c) + a=c; + else + b=c; + if (*cur == *a || *cur == *b) + goto found; + } + else + { + if (_lf_dynarray_iterate(&pinbox->pinstack, + (lf_dynarray_func)match_pins, *cur)) + goto found; + } + } + /* not pinned - freeing */ + pinbox->free_func(*cur, pinbox->free_func_arg); + continue; +found: + /* pinned - keeping */ + *start++=*cur; + } + pins->purgatory_count=start-pins->purgatory; +#ifdef MY_LF_EXTRA_DEBUG + while (start < pins->purgatory + LF_PURGATORY_SIZE) + *start++=0; +#endif +} + +static void alloc_free(void *node, LF_ALLOCATOR *allocator) +{ + void *tmp; + tmp=allocator->top; + do + { + (*(void **)node)=tmp; + } while (!my_atomic_casptr((void **)&allocator->top, (void **)&tmp, node) && + LF_BACKOFF); +} + +LF_REQUIRE_PINS(1); +void *_lf_alloc_new(LF_PINS *pins) +{ + LF_ALLOCATOR *allocator=(LF_ALLOCATOR *)(pins->pinbox->free_func_arg); + void *node; + for (;;) + { + do + { + node=allocator->top; + _lf_pin(pins, 0, node); + } while (node !=allocator->top && LF_BACKOFF); + if (!node) + { + if (!(node=my_malloc(allocator->element_size, MYF(MY_WME|MY_ZEROFILL)))) + goto ret; +#ifdef MY_LF_EXTRA_DEBUG + my_atomic_add32(&allocator->mallocs, 1); +#endif + goto ret; + } + if (my_atomic_casptr((void **)&allocator->top, + (void *)&node, *(void **)node)) + goto ret; + } +ret: + _lf_unpin(pins, 0); + return node; +} + +void lf_alloc_init(LF_ALLOCATOR *allocator, uint size) +{ + lf_pinbox_init(&allocator->pinbox, + (lf_pinbox_free_func *)alloc_free, allocator); + allocator->top=0; + allocator->mallocs=0; + allocator->element_size=size; + DBUG_ASSERT(size >= (int)sizeof(void *)); +} + +void lf_alloc_destroy(LF_ALLOCATOR *allocator) +{ + void *el=allocator->top; + while (el) + { + void *tmp=*(void **)el; + my_free(el, MYF(0)); + el=tmp; + } + lf_pinbox_destroy(&allocator->pinbox); + allocator->top=0; +} + +/* + NOTE + this is NOT thread-safe !!! +*/ +uint lf_alloc_in_pool(LF_ALLOCATOR *allocator) +{ + uint i; + void *node; + for (node=allocator->top, i=0; node; node=*(void **)node, i++) /* no op */; + return i; +} + diff --git a/mysys/lf_dynarray.c b/mysys/lf_dynarray.c new file mode 100644 index 00000000000..0fa04ab095c --- /dev/null +++ b/mysys/lf_dynarray.c @@ -0,0 +1,186 @@ +/* Copyright (C) 2000 MySQL AB + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ + +/* + Analog of DYNAMIC_ARRAY that never reallocs + (so no pointer into the array may ever become invalid). + + Memory is allocated in non-contiguous chunks. + This data structure is not space efficient for sparce arrays. + + The number of elements is limited to 2^16 + + Every element is aligned to sizeof(element) boundary + (to avoid false sharing if element is big enough). + + Actually, it's wait-free, not lock-free ;-) +*/ + +#undef DBUG_OFF +#include <my_global.h> +#include <strings.h> +#include <my_sys.h> +#include <lf.h> + +void lf_dynarray_init(LF_DYNARRAY *array, uint element_size) +{ + bzero(array, sizeof(*array)); + array->size_of_element=element_size; + my_atomic_rwlock_init(&array->lock); +} + +static void recursive_free(void **alloc, int level) +{ + if (!alloc) return; + + if (level) + { + int i; + for (i=0; i < LF_DYNARRAY_LEVEL_LENGTH; i++) + recursive_free(alloc[i], level-1); + my_free((void *)alloc, MYF(0)); + } + else + my_free(alloc[-1], MYF(0)); +} + +void lf_dynarray_destroy(LF_DYNARRAY *array) +{ + int i; + for (i=0; i < LF_DYNARRAY_LEVELS; i++) + recursive_free(array->level[i], i); + my_atomic_rwlock_destroy(&array->lock); + bzero(array, sizeof(*array)); +} + +static const int dynarray_idxes_in_level[LF_DYNARRAY_LEVELS]= +{ + 0, /* +1 here to to avoid -1's below */ + LF_DYNARRAY_LEVEL_LENGTH, + LF_DYNARRAY_LEVEL_LENGTH * LF_DYNARRAY_LEVEL_LENGTH, + LF_DYNARRAY_LEVEL_LENGTH * LF_DYNARRAY_LEVEL_LENGTH * + LF_DYNARRAY_LEVEL_LENGTH +}; + +void *_lf_dynarray_lvalue(LF_DYNARRAY *array, uint idx) +{ + void * ptr, * volatile * ptr_ptr=0; + int i; + + for (i=3; i > 0; i--) + { + if (ptr_ptr || idx >= dynarray_idxes_in_level[i]) + { + if (!ptr_ptr) + { + ptr_ptr=&array->level[i]; + idx-= dynarray_idxes_in_level[i]; + } + ptr=*ptr_ptr; + if (!ptr) + { + void *alloc=my_malloc(LF_DYNARRAY_LEVEL_LENGTH * sizeof(void *), + MYF(MY_WME|MY_ZEROFILL)); + if (!alloc) + return(NULL); + if (my_atomic_casptr(ptr_ptr, &ptr, alloc)) + ptr= alloc; + else + my_free(alloc, MYF(0)); + } + ptr_ptr=((void **)ptr) + idx / dynarray_idxes_in_level[i]; + idx%= dynarray_idxes_in_level[i]; + } + } + if (!ptr_ptr) + ptr_ptr=&array->level[0]; + ptr=*ptr_ptr; + if (!ptr) + { + void *alloc, *data; + alloc=my_malloc(LF_DYNARRAY_LEVEL_LENGTH * array->size_of_element + + max(array->size_of_element, sizeof(void *)), + MYF(MY_WME|MY_ZEROFILL)); + if (!alloc) + return(NULL); + /* reserve the space for free() address */ + data= alloc + sizeof(void *); + { /* alignment */ + intptr mod= ((intptr)data) % array->size_of_element; + if (mod) + data+= array->size_of_element - mod; + } + ((void **)data)[-1]=alloc; /* free() will need the original pointer */ + if (my_atomic_casptr(ptr_ptr, &ptr, data)) + ptr= data; + else + my_free(alloc, MYF(0)); + } + return ptr + array->size_of_element * idx; +} + +void *_lf_dynarray_value(LF_DYNARRAY *array, uint idx) +{ + void * ptr, * volatile * ptr_ptr=0; + int i; + + for (i=3; i > 0; i--) + { + if (ptr_ptr || idx >= dynarray_idxes_in_level[i]) + { + if (!ptr_ptr) + { + ptr_ptr=&array->level[i]; + idx-= dynarray_idxes_in_level[i]; + } + ptr=*ptr_ptr; + if (!ptr) + return(NULL); + ptr_ptr=((void **)ptr) + idx / dynarray_idxes_in_level[i]; + idx %= dynarray_idxes_in_level[i]; + } + } + if (!ptr_ptr) + ptr_ptr=&array->level[0]; + ptr=*ptr_ptr; + if (!ptr) + return(NULL); + return ptr + array->size_of_element * idx; +} + +static int recursive_iterate(LF_DYNARRAY *array, void *ptr, int level, + lf_dynarray_func func, void *arg) +{ + int res, i; + if (!ptr) + return 0; + if (!level) + return func(ptr, arg); + for (i=0; i < LF_DYNARRAY_LEVEL_LENGTH; i++) + if ((res=recursive_iterate(array, ((void **)ptr)[i], level-1, func, arg))) + return res; + return 0; +} + +int _lf_dynarray_iterate(LF_DYNARRAY *array, lf_dynarray_func func, void *arg) +{ + int i, res; + for (i=0; i < LF_DYNARRAY_LEVELS; i++) + if ((res=recursive_iterate(array, array->level[i], i, func, arg))) + return res; + return 0; +} + diff --git a/mysys/lf_hash.c b/mysys/lf_hash.c new file mode 100644 index 00000000000..736c3ea4887 --- /dev/null +++ b/mysys/lf_hash.c @@ -0,0 +1,355 @@ +/* Copyright (C) 2000 MySQL AB + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ + +/* + extensible hash + + TODO + try to get rid of dummy nodes ? +*/ +#include <my_global.h> +#include <my_sys.h> +#include <my_bit.h> +#include <lf.h> + +LF_REQUIRE_PINS(3); + +typedef struct { + intptr volatile link; + uint32 hashnr; + const uchar *key; + uint keylen; +} LF_SLIST; + +typedef struct { + intptr volatile *prev; + LF_SLIST *curr, *next; +} CURSOR; + +#define PTR(V) (LF_SLIST *)((V) & (~(intptr)1)) +#define DELETED(V) ((V) & 1) + +/* + RETURN + 0 - not found + 1 - found + + NOTE + cursor is positioned in either case + pins[0..2] are used, they are NOT removed on return +*/ +static int lfind(intptr volatile *head, uint32 hashnr, + const uchar *key, uint keylen, CURSOR *cursor, LF_PINS *pins) +{ + uint32 cur_hashnr; + const uchar *cur_key; + uint cur_keylen; + intptr link; + +retry: + cursor->prev=head; + do { + cursor->curr=PTR(*cursor->prev); + _lf_pin(pins,1,cursor->curr); + } while(*cursor->prev != (intptr)cursor->curr && LF_BACKOFF); + for (;;) + { + if (!cursor->curr) + return 0; + do { // XXX or goto retry ? + link=cursor->curr->link; + cursor->next=PTR(link); + _lf_pin(pins, 0, cursor->next); + } while(link != cursor->curr->link && LF_BACKOFF); + cur_hashnr=cursor->curr->hashnr; + cur_key=cursor->curr->key; + cur_keylen=cursor->curr->keylen; + if (*cursor->prev != (intptr)cursor->curr) + { + LF_BACKOFF; + goto retry; + } + if (!DELETED(link)) + { + if (cur_hashnr >= hashnr) + { + int r=1; + if (cur_hashnr > hashnr || (r=memcmp(cur_key, key, keylen)) >= 0) + return !r; + } + cursor->prev=&(cursor->curr->link); + _lf_pin(pins, 2, cursor->curr); + } + else + { + if (my_atomic_casptr((void **)cursor->prev, + (void **)&cursor->curr, cursor->next)) + _lf_alloc_free(pins, cursor->curr); + else + { + LF_BACKOFF; + goto retry; + } + } + cursor->curr=cursor->next; + _lf_pin(pins, 1, cursor->curr); + } +} + +/* + RETURN + 0 - inserted + not 0 - a pointer to a conflict + + NOTE + it uses pins[0..2], on return all pins are removed. +*/ +static LF_SLIST *linsert(LF_SLIST * volatile *head, LF_SLIST *node, + LF_PINS *pins, uint flags) +{ + CURSOR cursor; + int res=-1; + + do + { + if (lfind((intptr*)head, node->hashnr, node->key, node->keylen, + &cursor, pins) && + (flags & LF_HASH_UNIQUE)) + res=0; + else + { + node->link=(intptr)cursor.curr; + assert(node->link != (intptr)node); + assert(cursor.prev != &node->link); + if (my_atomic_casptr((void **)cursor.prev, (void **)&cursor.curr, node)) + res=1; + } + } while (res == -1); + _lf_unpin(pins, 0); + _lf_unpin(pins, 1); + _lf_unpin(pins, 2); + return res ? 0 : cursor.curr; +} + +/* + RETURN + 0 - ok + 1 - not found + NOTE + it uses pins[0..2], on return all pins are removed. +*/ +static int ldelete(LF_SLIST * volatile *head, uint32 hashnr, + const uchar *key, uint keylen, LF_PINS *pins) +{ + CURSOR cursor; + int res=-1; + + do + { + if (!lfind((intptr *)head, hashnr, key, keylen, &cursor, pins)) + res= 1; + else + if (my_atomic_casptr((void **)&(cursor.curr->link), + (void **)&cursor.next, 1+(char *)cursor.next)) + { + if (my_atomic_casptr((void **)cursor.prev, + (void **)&cursor.curr, cursor.next)) + _lf_alloc_free(pins, cursor.curr); + else + lfind((intptr *)head, hashnr, key, keylen, &cursor, pins); + res= 0; + } + } while (res == -1); + _lf_unpin(pins, 0); + _lf_unpin(pins, 1); + _lf_unpin(pins, 2); + return res; +} + +/* + RETURN + 0 - not found + node - found + NOTE + it uses pins[0..2], on return the pin[2] keeps the node found + all other pins are removed. +*/ +static LF_SLIST *lsearch(LF_SLIST * volatile *head, uint32 hashnr, + const uchar *key, uint keylen, LF_PINS *pins) +{ + CURSOR cursor; + int res=lfind((intptr *)head, hashnr, key, keylen, &cursor, pins); + if (res) _lf_pin(pins, 2, cursor.curr); + _lf_unpin(pins, 0); + _lf_unpin(pins, 1); + return res ? cursor.curr : 0; +} + +static inline const uchar* hash_key(const LF_HASH *hash, + const uchar *record, uint *length) +{ + if (hash->get_key) + return (*hash->get_key)(record,length,0); + *length=hash->key_length; + return record + hash->key_offset; +} + +static inline uint calc_hash(LF_HASH *hash, const uchar *key, uint keylen) +{ + ulong nr1=1, nr2=4; + hash->charset->coll->hash_sort(hash->charset,key,keylen,&nr1,&nr2); + return nr1 & INT_MAX32; +} + +#define MAX_LOAD 1 +static void initialize_bucket(LF_HASH *, LF_SLIST * volatile*, uint, LF_PINS *); + +void lf_hash_init(LF_HASH *hash, uint element_size, uint flags, + uint key_offset, uint key_length, hash_get_key get_key, + CHARSET_INFO *charset) +{ + lf_alloc_init(&hash->alloc,sizeof(LF_SLIST)+element_size); + lf_dynarray_init(&hash->array, sizeof(LF_SLIST **)); + hash->size=1; + hash->count=0; + hash->element_size=element_size; + hash->flags=flags; + hash->charset=charset ? charset : &my_charset_bin; + hash->key_offset=key_offset; + hash->key_length=key_length; + hash->get_key=get_key; + DBUG_ASSERT(get_key ? !key_offset && !key_length : key_length); +} + +void lf_hash_destroy(LF_HASH *hash) +{ + LF_SLIST *el=*(LF_SLIST **)_lf_dynarray_lvalue(&hash->array, 0); + while (el) + { + intptr next=el->link; + if (el->hashnr & 1) + lf_alloc_real_free(&hash->alloc, el); + else + my_free((void *)el, MYF(0)); + el=(LF_SLIST *)next; + } + lf_alloc_destroy(&hash->alloc); + lf_dynarray_destroy(&hash->array); +} + +/* + RETURN + 0 - inserted + 1 - didn't (unique key conflict) + NOTE + see linsert() for pin usage notes +*/ +int lf_hash_insert(LF_HASH *hash, LF_PINS *pins, const void *data) +{ + uint csize, bucket, hashnr; + LF_SLIST *node, * volatile *el; + + lf_lock_by_pins(pins); + node=(LF_SLIST *)_lf_alloc_new(pins); + memcpy(node+1, data, hash->element_size); + node->key= hash_key(hash, (uchar *)(node+1), &node->keylen); + hashnr= calc_hash(hash, node->key, node->keylen); + bucket= hashnr % hash->size; + el=_lf_dynarray_lvalue(&hash->array, bucket); + if (*el == NULL) + initialize_bucket(hash, el, bucket, pins); + node->hashnr=my_reverse_bits(hashnr) | 1; + if (linsert(el, node, pins, hash->flags)) + { + _lf_alloc_free(pins, node); + lf_unlock_by_pins(pins); + return 1; + } + csize= hash->size; + if ((my_atomic_add32(&hash->count, 1)+1.0) / csize > MAX_LOAD) + my_atomic_cas32(&hash->size, &csize, csize*2); + lf_unlock_by_pins(pins); + return 0; +} + +/* + RETURN + 0 - deleted + 1 - didn't (not found) + NOTE + see ldelete() for pin usage notes +*/ +int lf_hash_delete(LF_HASH *hash, LF_PINS *pins, const void *key, uint keylen) +{ + LF_SLIST * volatile *el; + uint bucket, hashnr=calc_hash(hash, (uchar *)key, keylen); + + bucket= hashnr % hash->size; + lf_lock_by_pins(pins); + el=_lf_dynarray_lvalue(&hash->array, bucket); + if (*el == NULL) + initialize_bucket(hash, el, bucket, pins); + if (ldelete(el, my_reverse_bits(hashnr) | 1, (uchar *)key, keylen, pins)) + { + lf_unlock_by_pins(pins); + return 1; + } + my_atomic_add32(&hash->count, -1); + lf_unlock_by_pins(pins); + return 0; +} + +/* + NOTE + see lsearch() for pin usage notes +*/ +void *lf_hash_search(LF_HASH *hash, LF_PINS *pins, const void *key, uint keylen) +{ + LF_SLIST * volatile *el, *found; + uint bucket, hashnr=calc_hash(hash, (uchar *)key, keylen); + + bucket= hashnr % hash->size; + lf_lock_by_pins(pins); + el=_lf_dynarray_lvalue(&hash->array, bucket); + if (*el == NULL) + initialize_bucket(hash, el, bucket, pins); + found= lsearch(el, my_reverse_bits(hashnr) | 1, (uchar *)key, keylen, pins); + lf_unlock_by_pins(pins); + return found+1; +} + +static char *dummy_key=""; + +static void initialize_bucket(LF_HASH *hash, LF_SLIST * volatile *node, + uint bucket, LF_PINS *pins) +{ + uint parent= my_clear_highest_bit(bucket); + LF_SLIST *dummy=(LF_SLIST *)my_malloc(sizeof(LF_SLIST), MYF(MY_WME)); + LF_SLIST **tmp=0, *cur; + LF_SLIST * volatile *el=_lf_dynarray_lvalue(&hash->array, parent); + if (*el == NULL && bucket) + initialize_bucket(hash, el, parent, pins); + dummy->hashnr=my_reverse_bits(bucket); + dummy->key=dummy_key; + dummy->keylen=0; + if ((cur= linsert(el, dummy, pins, 0))) + { + _lf_alloc_free(pins, dummy); + dummy= cur; + } + my_atomic_casptr((void **)node, (void **)&tmp, dummy); +} + diff --git a/mysys/mf_keycache.c b/mysys/mf_keycache.c index e6f4348968f..9a99a278bc5 100644 --- a/mysys/mf_keycache.c +++ b/mysys/mf_keycache.c @@ -43,6 +43,7 @@ #include <keycache.h> #include "my_static.h" #include <m_string.h> +#include <my_bit.h> #include <errno.h> #include <stdarg.h> diff --git a/mysys/my_atomic.c b/mysys/my_atomic.c index 6f56d76e6b8..2908a44961a 100644 --- a/mysys/my_atomic.c +++ b/mysys/my_atomic.c @@ -18,11 +18,10 @@ #include <my_pthread.h> #ifndef HAVE_INLINE -/* - the following will cause all inline functions to be instantiated -*/ +/* the following will cause all inline functions to be instantiated */ #define HAVE_INLINE -#define static extern +#undef STATIC_INLINE +#define STATIC_INLINE extern #endif #include <my_atomic.h> diff --git a/mysys/my_bit.c b/mysys/my_bit.c index 6ef0e171695..11d98f5f6ae 100644 --- a/mysys/my_bit.c +++ b/mysys/my_bit.c @@ -14,23 +14,18 @@ along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ -/* Some useful bit functions */ +#include <my_global.h> -#include "mysys_priv.h" - -/* - Find smallest X in 2^X >= value - This can be used to divide a number with value by doing a shift instead -*/ +#ifndef HAVE_INLINE +/* the following will cause all inline functions to be instantiated */ +#define HAVE_INLINE +#undef STATIC_INLINE +#define STATIC_INLINE extern +#endif -uint my_bit_log2(ulong value) -{ - uint bit; - for (bit=0 ; value > 1 ; value>>=1, bit++) ; - return bit; -} +#include <my_bit.h> -static char nbits[256] = { +const char _my_bits_nbits[256] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, @@ -49,60 +44,29 @@ static char nbits[256] = { 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, }; -uint my_count_bits(ulonglong v) -{ -#if SIZEOF_LONG_LONG > 4 - /* The following code is a bit faster on 16 bit machines than if we would - only shift v */ - ulong v2=(ulong) (v >> 32); - return (uint) (uchar) (nbits[(uchar) v] + - nbits[(uchar) (v >> 8)] + - nbits[(uchar) (v >> 16)] + - nbits[(uchar) (v >> 24)] + - nbits[(uchar) (v2)] + - nbits[(uchar) (v2 >> 8)] + - nbits[(uchar) (v2 >> 16)] + - nbits[(uchar) (v2 >> 24)]); -#else - return (uint) (uchar) (nbits[(uchar) v] + - nbits[(uchar) (v >> 8)] + - nbits[(uchar) (v >> 16)] + - nbits[(uchar) (v >> 24)]); -#endif -} - -uint my_count_bits_ushort(ushort v) -{ - return nbits[v]; -} - - /* - Next highest power of two - - SYNOPSIS - my_round_up_to_next_power() - v Value to check - - RETURN - Next or equal power of 2 - Note: 0 will return 0 - - NOTES - Algorithm by Sean Anderson, according to: - http://graphics.stanford.edu/~seander/bithacks.html - (Orignal code public domain) - - Comments shows how this works with 01100000000000000000000000001011 + perl -e 'print map{", 0x".unpack H2,pack B8,unpack b8,chr$_}(0..255)' */ +const uchar _my_bits_reverse_table[256]={ +0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, +0xB0, 0x70, 0xF0, 0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, +0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8, 0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, +0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4, 0x0C, 0x8C, 0x4C, 0xCC, +0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC, 0x02, +0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, +0x72, 0xF2, 0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, +0xDA, 0x3A, 0xBA, 0x7A, 0xFA, 0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, +0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6, 0x0E, 0x8E, 0x4E, 0xCE, 0x2E, +0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE, 0x01, 0x81, +0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, +0xF1, 0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, +0x39, 0xB9, 0x79, 0xF9, 0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, +0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5, 0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, +0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD, 0x03, 0x83, 0x43, +0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3, +0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, +0xBB, 0x7B, 0xFB, 0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, +0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7, 0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, +0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF +}; -uint32 my_round_up_to_next_power(uint32 v) -{ - v--; /* 01100000000000000000000000001010 */ - v|= v >> 1; /* 01110000000000000000000000001111 */ - v|= v >> 2; /* 01111100000000000000000000001111 */ - v|= v >> 4; /* 01111111110000000000000000001111 */ - v|= v >> 8; /* 01111111111111111100000000001111 */ - v|= v >> 16; /* 01111111111111111111111111111111 */ - return v+1; /* 10000000000000000000000000000000 */ -} diff --git a/mysys/my_bitmap.c b/mysys/my_bitmap.c index 2c85ce0bf04..8cf8ac0e97c 100644 --- a/mysys/my_bitmap.c +++ b/mysys/my_bitmap.c @@ -39,6 +39,7 @@ #include "mysys_priv.h" #include <my_bitmap.h> #include <m_string.h> +#include <my_bit.h> void create_last_word_mask(MY_BITMAP *map) { diff --git a/mysys/my_init.c b/mysys/my_init.c index dca68637161..a1dca635054 100644 --- a/mysys/my_init.c +++ b/mysys/my_init.c @@ -44,6 +44,7 @@ static void netware_init(); my_bool my_init_done= 0; uint mysys_usage_id= 0; /* Incremented for each my_init() */ +ulong my_thread_stack_size= 65536; static ulong atoi_octal(const char *str) { diff --git a/sql/item_func.cc b/sql/item_func.cc index c4361663873..9b7d76bf670 100644 --- a/sql/item_func.cc +++ b/sql/item_func.cc @@ -27,6 +27,7 @@ #include <hash.h> #include <time.h> #include <ft_global.h> +#include <my_bit.h> #include "sp_head.h" #include "sp_rcontext.h" diff --git a/sql/mysql_priv.h b/sql/mysql_priv.h index fa687e02b59..092543216f4 100644 --- a/sql/mysql_priv.h +++ b/sql/mysql_priv.h @@ -1525,7 +1525,7 @@ extern ulong max_connections,max_connect_errors, connect_timeout; extern ulong slave_net_timeout, slave_trans_retries; extern uint max_user_connections; extern ulong what_to_log,flush_time; -extern ulong query_buff_size, thread_stack; +extern ulong query_buff_size; extern ulong max_prepared_stmt_count, prepared_stmt_count; extern ulong binlog_cache_size, max_binlog_cache_size, open_files_limit; extern ulong max_binlog_size, max_relay_log_size; diff --git a/sql/mysqld.cc b/sql/mysqld.cc index f1d550d0ff1..5b1a03f5564 100644 --- a/sql/mysqld.cc +++ b/sql/mysqld.cc @@ -17,6 +17,7 @@ #include "mysql_priv.h" #include <m_ctype.h> #include <my_dir.h> +#include <my_bit.h> #include "slave.h" #include "sql_repl.h" #include "rpl_filter.h" @@ -457,7 +458,7 @@ uint volatile thread_count, thread_running; ulonglong thd_startup_options; ulong back_log, connect_timeout, concurrency, server_id; ulong table_cache_size, table_def_size; -ulong thread_stack, what_to_log; +ulong what_to_log; ulong query_buff_size, slow_launch_time, slave_open_temp_tables; ulong open_files_limit, max_binlog_size, max_relay_log_size; ulong slave_net_timeout, slave_trans_retries; @@ -2120,7 +2121,7 @@ the thread stack. Please read http://www.mysql.com/doc/en/Linux.html\n\n", { fprintf(stderr,"thd=%p\n",thd); print_stacktrace(thd ? (gptr) thd->thread_stack : (gptr) 0, - thread_stack); + my_thread_stack_size); } if (thd) { @@ -2252,9 +2253,9 @@ static void start_signal_handler(void) Peculiar things with ia64 platforms - it seems we only have half the stack size in reality, so we have to double it here */ - pthread_attr_setstacksize(&thr_attr,thread_stack*2); + pthread_attr_setstacksize(&thr_attr,my_thread_stack_size*2); #else - pthread_attr_setstacksize(&thr_attr,thread_stack); + pthread_attr_setstacksize(&thr_attr,my_thread_stack_size); #endif #endif @@ -3482,9 +3483,9 @@ int main(int argc, char **argv) Peculiar things with ia64 platforms - it seems we only have half the stack size in reality, so we have to double it here */ - pthread_attr_setstacksize(&connection_attrib,thread_stack*2); + pthread_attr_setstacksize(&connection_attrib,my_thread_stack_size*2); #else - pthread_attr_setstacksize(&connection_attrib,thread_stack); + pthread_attr_setstacksize(&connection_attrib,my_thread_stack_size); #endif #ifdef HAVE_PTHREAD_ATTR_GETSTACKSIZE { @@ -3495,15 +3496,15 @@ int main(int argc, char **argv) stack_size/= 2; #endif /* We must check if stack_size = 0 as Solaris 2.9 can return 0 here */ - if (stack_size && stack_size < thread_stack) + if (stack_size && stack_size < my_thread_stack_size) { if (global_system_variables.log_warnings) sql_print_warning("Asked for %ld thread stack, but got %ld", - thread_stack, stack_size); + my_thread_stack_size, stack_size); #if defined(__ia64__) || defined(__ia64) - thread_stack= stack_size*2; + my_thread_stack_size= stack_size*2; #else - thread_stack= stack_size; + my_thread_stack_size= stack_size; #endif } } @@ -6252,8 +6253,8 @@ The minimum value for this variable is 4096.", (gptr*) &concurrency, (gptr*) &concurrency, 0, GET_ULONG, REQUIRED_ARG, DEFAULT_CONCURRENCY, 1, 512, 0, 1, 0}, {"thread_stack", OPT_THREAD_STACK, - "The stack size for each thread.", (gptr*) &thread_stack, - (gptr*) &thread_stack, 0, GET_ULONG, REQUIRED_ARG,DEFAULT_THREAD_STACK, + "The stack size for each thread.", (gptr*) &my_thread_stack_size, + (gptr*) &my_thread_stack_size, 0, GET_ULONG, REQUIRED_ARG,DEFAULT_THREAD_STACK, 1024L*128L, ~0L, 0, 1024, 0}, { "time_format", OPT_TIME_FORMAT, "The TIME format (for future).", diff --git a/sql/set_var.cc b/sql/set_var.cc index 777d84bd337..e734eb670a2 100644 --- a/sql/set_var.cc +++ b/sql/set_var.cc @@ -1054,10 +1054,10 @@ SHOW_VAR init_vars[]= { #ifdef HAVE_THR_SETCONCURRENCY {"thread_concurrency", (char*) &concurrency, SHOW_LONG}, #endif - {"thread_stack", (char*) &thread_stack, SHOW_LONG}, + {"thread_stack", (char*) &my_thread_stack_size, SHOW_LONG}, {sys_time_format.name, (char*) &sys_time_format, SHOW_SYS}, {"time_zone", (char*) &sys_time_zone, SHOW_SYS}, - {sys_timed_mutexes.name, (char*) &sys_timed_mutexes, SHOW_SYS}, + {sys_timed_mutexes.name, (char*) &sys_timed_mutexes, SHOW_SYS}, {sys_tmp_table_size.name, (char*) &sys_tmp_table_size, SHOW_SYS}, {sys_tmpdir.name, (char*) &sys_tmpdir, SHOW_SYS}, {sys_trans_alloc_block_size.name, (char*) &sys_trans_alloc_block_size, diff --git a/sql/sql_parse.cc b/sql/sql_parse.cc index 2aceccd1c92..ae4420026c8 100644 --- a/sql/sql_parse.cc +++ b/sql/sql_parse.cc @@ -5780,10 +5780,10 @@ bool check_stack_overrun(THD *thd, long margin, long stack_used; DBUG_ASSERT(thd == current_thd); if ((stack_used=used_stack(thd->thread_stack,(char*) &stack_used)) >= - (long) (thread_stack - margin)) + (long) (my_thread_stack_size - margin)) { sprintf(errbuff[0],ER(ER_STACK_OVERRUN_NEED_MORE), - stack_used,thread_stack,margin); + stack_used,my_thread_stack_size,margin); my_message(ER_STACK_OVERRUN_NEED_MORE,errbuff[0],MYF(0)); thd->fatal_error(); return 1; diff --git a/sql/sql_select.cc b/sql/sql_select.cc index e048271ed3a..7077e30e1e9 100644 --- a/sql/sql_select.cc +++ b/sql/sql_select.cc @@ -26,6 +26,7 @@ #include "sql_cursor.h" #include <m_ctype.h> +#include <my_bit.h> #include <hash.h> #include <ft_global.h> diff --git a/sql/sql_test.cc b/sql/sql_test.cc index b28aa4a1ce5..77bbee0bf69 100644 --- a/sql/sql_test.cc +++ b/sql/sql_test.cc @@ -455,7 +455,7 @@ void mysql_print_status() VOID(my_getwd(current_dir, sizeof(current_dir),MYF(0))); printf("Current dir: %s\n", current_dir); printf("Running threads: %d Stack size: %ld\n", thread_count, - (long) thread_stack); + (long) my_thread_stack_size); thr_print_locks(); // Write some debug info #ifndef DBUG_OFF print_cached_tables(); @@ -530,7 +530,7 @@ Estimated memory (with thread stack): %ld\n", (int) info.uordblks, (int) info.fordblks, (int) info.keepcost, - (long) (thread_count * thread_stack + info.hblkhd + info.arena)); + (long) (thread_count * my_thread_stack_size + info.hblkhd + info.arena)); #endif puts(""); } diff --git a/storage/maria/Makefile.am b/storage/maria/Makefile.am index 100000fa6cd..54fd70d7ae5 100644 --- a/storage/maria/Makefile.am +++ b/storage/maria/Makefile.am @@ -52,7 +52,8 @@ maria_pack_LDADD= @CLIENT_EXTRA_LDFLAGS@ libmaria.a \ $(top_builddir)/strings/libmystrings.a @ZLIB_LIBS@ noinst_PROGRAMS = ma_test1 ma_test2 ma_test3 ma_rt_test ma_sp_test noinst_HEADERS = maria_def.h ma_rt_index.h ma_rt_key.h ma_rt_mbr.h \ - ma_sp_defs.h ma_fulltext.h ma_ftdefs.h ma_ft_test1.h ma_ft_eval.h \ + ma_sp_defs.h ma_fulltext.h ma_ftdefs.h ma_ft_test1.h \ + ma_ft_eval.h trxman.h \ ma_control_file.h ha_maria.h ma_test1_DEPENDENCIES= $(LIBRARIES) ma_test1_LDADD= @CLIENT_EXTRA_LDFLAGS@ libmaria.a \ @@ -107,7 +108,7 @@ libmaria_a_SOURCES = ma_init.c ma_open.c ma_extra.c ma_info.c ma_rkey.c \ ma_keycache.c ma_preload.c ma_ft_parser.c \ ma_ft_update.c ma_ft_boolean_search.c \ ma_ft_nlq_search.c ft_maria.c ma_sort.c \ - ha_maria.cc \ + ha_maria.cc trxman.c \ ma_rt_index.c ma_rt_key.c ma_rt_mbr.c ma_rt_split.c \ ma_sp_key.c ma_control_file.c CLEANFILES = test?.MA? FT?.MA? isam.log ma_test_all ma_rt_test.MA? sp_test.MA? diff --git a/storage/maria/ha_maria.cc b/storage/maria/ha_maria.cc index a0084ef5e9c..26fcdf91d26 100644 --- a/storage/maria/ha_maria.cc +++ b/storage/maria/ha_maria.cc @@ -24,6 +24,7 @@ #include <mysql/plugin.h> #include <m_ctype.h> #include <myisampack.h> +#include <my_bit.h> #include "ha_maria.h" #include "maria_def.h" diff --git a/storage/maria/ma_create.c b/storage/maria/ma_create.c index b9fb4eb0d5b..5926bba9406 100644 --- a/storage/maria/ma_create.c +++ b/storage/maria/ma_create.c @@ -18,6 +18,7 @@ #include "ma_ftdefs.h" #include "ma_sp_defs.h" +#include <my_bit.h> #if defined(MSDOS) || defined(__WIN__) #ifdef __WIN__ diff --git a/storage/maria/ma_test2.c b/storage/maria/ma_test2.c index 840ecb2eeb7..40f7d2aaffb 100644 --- a/storage/maria/ma_test2.c +++ b/storage/maria/ma_test2.c @@ -27,6 +27,7 @@ #endif #include "maria_def.h" #include <m_ctype.h> +#include <my_bit.h> #define STANDARD_LENGTH 37 #define MARIA_KEYS 6 diff --git a/storage/maria/maria_chk.c b/storage/maria/maria_chk.c index e423a3f5c36..89858ee2d07 100644 --- a/storage/maria/maria_chk.c +++ b/storage/maria/maria_chk.c @@ -18,6 +18,7 @@ #include "ma_fulltext.h" #include <myisamchk.h> +#include <my_bit.h> #include <m_ctype.h> #include <stdarg.h> #include <my_getopt.h> diff --git a/storage/maria/trxman.c b/storage/maria/trxman.c new file mode 100644 index 00000000000..a3e746af9ca --- /dev/null +++ b/storage/maria/trxman.c @@ -0,0 +1,258 @@ + +#include <my_global.h> +#include <my_sys.h> +#include <lf.h> +#include "trxman.h" + +TRX active_list_min, active_list_max, + committed_list_min, committed_list_max, *pool; + +pthread_mutex_t LOCK_trx_list; +uint trxman_active_transactions, trxman_allocated_transactions; +TrID global_trid_generator; + +TRX **short_id_to_trx; +my_atomic_rwlock_t LOCK_short_id_to_trx; + +LF_HASH trid_to_trx; + +static byte *trx_get_hash_key(const byte *trx,uint* len, my_bool unused) +{ + *len= sizeof(TrID); + return (byte *) & ((*((TRX **)trx))->trid); +} + +int trxman_init() +{ + pthread_mutex_init(&LOCK_trx_list, MY_MUTEX_INIT_FAST); + active_list_max.trid= active_list_min.trid= 0; + active_list_max.min_read_from=~0; + active_list_max.next= active_list_min.prev= 0; + active_list_max.prev= &active_list_min; + active_list_min.next= &active_list_max; + trxman_active_transactions= 0; + trxman_allocated_transactions= 0; + + committed_list_max.commit_trid= ~0; + committed_list_max.next= committed_list_min.prev= 0; + committed_list_max.prev= &committed_list_min; + committed_list_min.next= &committed_list_max; + + pool=0; + global_trid_generator=0; /* set later by recovery code */ + lf_hash_init(&trid_to_trx, sizeof(TRX*), LF_HASH_UNIQUE, + 0, 0, trx_get_hash_key, 0); + my_atomic_rwlock_init(&LOCK_short_id_to_trx); + short_id_to_trx=(TRX **)my_malloc(SHORT_ID_MAX*sizeof(TRX*), + MYF(MY_WME|MY_ZEROFILL)); + if (!short_id_to_trx) + return 1; + short_id_to_trx--; /* min short_id is 1 */ + + return 0; +} + +int trxman_destroy() +{ + DBUG_ASSERT(trid_to_trx.count == 0); + DBUG_ASSERT(trxman_active_transactions == 0); + DBUG_ASSERT(active_list_max.prev == &active_list_min); + DBUG_ASSERT(active_list_min.next == &active_list_max); + DBUG_ASSERT(committed_list_max.prev == &committed_list_min); + DBUG_ASSERT(committed_list_min.next == &committed_list_max); + while (pool) + { + TRX *tmp=pool->next; + my_free((void *)pool, MYF(0)); + pool=tmp; + } + lf_hash_destroy(&trid_to_trx); + pthread_mutex_destroy(&LOCK_trx_list); + my_atomic_rwlock_destroy(&LOCK_short_id_to_trx); + my_free((void *)(short_id_to_trx+1), MYF(0)); +} + +static TrID new_trid() +{ + DBUG_ASSERT(global_trid_generator < 0xffffffffffffLL); + safe_mutex_assert_owner(&LOCK_trx_list); + return ++global_trid_generator; +} + +static void set_short_id(TRX *trx) +{ + int i= (global_trid_generator + (intptr)trx) * 312089 % SHORT_ID_MAX; + my_atomic_rwlock_wrlock(&LOCK_short_id_to_trx); + for ( ; ; i= i % SHORT_ID_MAX + 1) /* the range is [1..SHORT_ID_MAX] */ + { + void *tmp=NULL; + if (short_id_to_trx[i] == NULL && + my_atomic_casptr((void **)&short_id_to_trx[i], &tmp, trx)) + break; + } + my_atomic_rwlock_wrunlock(&LOCK_short_id_to_trx); + trx->short_id= i; +} + +TRX *trxman_new_trx() +{ + TRX *trx; + + my_atomic_add32(&trxman_active_transactions, 1); + + /* + see trxman_end_trx to see why we need a mutex here + + and as we have a mutex, we can as well do everything + under it - allocating a TRX, incrementing trxman_active_transactions, + setting trx->min_read_from. + + Note that all the above is fast. generating short_id may be slow, + as it involves scanning a big array - so it's still done + outside of the mutex. + */ + + pthread_mutex_lock(&LOCK_trx_list); + trx=pool; + while (trx && !my_atomic_casptr((void **)&pool, (void **)&trx, trx->next)) + /* no-op */; + + if (!trx) + { + trx=(TRX *)my_malloc(sizeof(TRX), MYF(MY_WME)); + trxman_allocated_transactions++; + } + if (!trx) + return 0; + + trx->min_read_from= active_list_min.next->trid; + + trx->trid= new_trid(); + trx->short_id= 0; + + trx->next= &active_list_max; + trx->prev= active_list_max.prev; + active_list_max.prev= trx->prev->next= trx; + pthread_mutex_unlock(&LOCK_trx_list); + + trx->pins=lf_hash_get_pins(&trid_to_trx); + + if (!trx->min_read_from) + trx->min_read_from= trx->trid; + + trx->commit_trid=0; + + set_short_id(trx); /* this must be the last! */ + + + return trx; +} + +/* + remove a trx from the active list, + move to committed list, + set commit_trid + + TODO + integrate with lock manager, log manager. That means: + a common "commit" mutex - forcing the log and setting commit_trid + must be done atomically (QQ how the heck it could be done with + group commit ???) + + trid_to_trx, active_list_*, and committed_list_* can be + updated asyncronously. +*/ +void trxman_end_trx(TRX *trx, my_bool commit) +{ + int res; + TRX *free_me= 0; + LF_PINS *pins= trx->pins; + + pthread_mutex_lock(&LOCK_trx_list); + trx->next->prev= trx->prev; + trx->prev->next= trx->next; + + if (trx->prev == &active_list_min) + { + TRX *t; + for (t= committed_list_min.next; + t->commit_trid < active_list_min.next->min_read_from; + t= t->next) /* no-op */; + + if (t != committed_list_min.next) + { + free_me= committed_list_min.next; + committed_list_min.next= t; + t->prev->next=0; + t->prev= &committed_list_min; + } + } + + my_atomic_rwlock_wrlock(&LOCK_short_id_to_trx); + my_atomic_storeptr((void **)&short_id_to_trx[trx->short_id], 0); + my_atomic_rwlock_wrunlock(&LOCK_short_id_to_trx); + + if (commit && active_list_min.next != &active_list_max) + { + trx->commit_trid= global_trid_generator; + + trx->next= &committed_list_max; + trx->prev= committed_list_max.prev; + committed_list_max.prev= trx->prev->next= trx; + + res= lf_hash_insert(&trid_to_trx, pins, &trx); + DBUG_ASSERT(res == 0); + } + else + { + trx->next=free_me; + free_me=trx; + } + pthread_mutex_unlock(&LOCK_trx_list); + + my_atomic_add32(&trxman_active_transactions, -1); + + while (free_me) + { + int res; + TRX *t= free_me; + free_me= free_me->next; + + res= lf_hash_delete(&trid_to_trx, pins, &t->trid, sizeof(TrID)); + + trxman_free_trx(t); + } + + lf_hash_put_pins(pins); +} + +/* free a trx (add to the pool, that is */ +void trxman_free_trx(TRX *trx) +{ + TRX *tmp=pool; + + do + { + trx->next=tmp; + } while (!my_atomic_casptr((void **)&pool, (void **)&tmp, trx)); +} + +my_bool trx_can_read_from(TRX *trx, TrID trid) +{ + TRX *found; + my_bool can; + + if (trid < trx->min_read_from) + return TRUE; + if (trid > trx->trid) + return FALSE; + + found= lf_hash_search(&trid_to_trx, trx->pins, &trid, sizeof(trid)); + if (!found) + return FALSE; /* not in the hash = cannot read */ + + can= found->commit_trid < trx->trid; + lf_unpin(trx->pins, 2); + return can; +} + diff --git a/storage/maria/trxman.h b/storage/maria/trxman.h new file mode 100644 index 00000000000..5ac989d03a4 --- /dev/null +++ b/storage/maria/trxman.h @@ -0,0 +1,28 @@ + +typedef uint64 TrID; /* our TrID is 6 bytes */ + +typedef struct st_transaction +{ + TrID trid, min_read_from, commit_trid; + struct st_transaction *next, *prev; + /* Note! if short_id is 0, trx is NOT initialized */ + uint16 short_id; + LF_PINS *pins; +} TRX; + +#define SHORT_ID_MAX 65535 + +extern uint trxman_active_transactions, trxman_allocated_transactions; + +extern TRX **short_id_to_trx; +extern my_atomic_rwlock_t LOCK_short_id_to_trx; + +int trxman_init(); +int trxman_end(); +TRX *trxman_new_trx(); +void trxman_end_trx(TRX *trx, my_bool commit); +#define trxman_commit_trx(T) trxman_end_trx(T, TRUE) +#define trxman_abort_trx(T) trxman_end_trx(T, FALSE) +void trxman_free_trx(TRX *trx); +my_bool trx_can_read_from(TRX *trx, TrID trid); + diff --git a/storage/myisam/ha_myisam.cc b/storage/myisam/ha_myisam.cc index e86f98d3d7d..d9f6cc55392 100644 --- a/storage/myisam/ha_myisam.cc +++ b/storage/myisam/ha_myisam.cc @@ -23,6 +23,7 @@ #include "mysql_priv.h" #include <mysql/plugin.h> #include <m_ctype.h> +#include <my_bit.h> #include <myisampack.h> #include "ha_myisam.h" #include <stdarg.h> diff --git a/storage/myisam/mi_create.c b/storage/myisam/mi_create.c index ad824bef009..42e341b2b83 100644 --- a/storage/myisam/mi_create.c +++ b/storage/myisam/mi_create.c @@ -18,6 +18,7 @@ #include "ftdefs.h" #include "sp_defs.h" +#include <my_bit.h> #if defined(MSDOS) || defined(__WIN__) #ifdef __WIN__ @@ -432,7 +433,7 @@ int mi_create(const char *name,uint keys,MI_KEYDEF *keydefs, share.state.rec_per_key_part[key_segs-1]=1L; length+=key_length; /* Get block length for key, if defined by user */ - block_length= (keydef->block_length ? + block_length= (keydef->block_length ? my_round_up_to_next_power(keydef->block_length) : myisam_block_size); block_length= max(block_length, MI_MIN_KEY_BLOCK_LENGTH); diff --git a/storage/myisam/mi_test2.c b/storage/myisam/mi_test2.c index 357128b7a40..498b433f846 100644 --- a/storage/myisam/mi_test2.c +++ b/storage/myisam/mi_test2.c @@ -27,6 +27,7 @@ #endif #include "myisamdef.h" #include <m_ctype.h> +#include <my_bit.h> #define STANDARD_LENGTH 37 #define MYISAM_KEYS 6 diff --git a/storage/myisam/myisamchk.c b/storage/myisam/myisamchk.c index 6f6a52406f2..d48db21c1a7 100644 --- a/storage/myisam/myisamchk.c +++ b/storage/myisam/myisamchk.c @@ -20,6 +20,7 @@ #include <m_ctype.h> #include <stdarg.h> #include <my_getopt.h> +#include <my_bit.h> #ifdef HAVE_SYS_VADVICE_H #include <sys/vadvise.h> #endif diff --git a/unittest/Makefile.am b/unittest/Makefile.am index 7323ef5fb77..a41d737ec59 100644 --- a/unittest/Makefile.am +++ b/unittest/Makefile.am @@ -1,4 +1,4 @@ -SUBDIRS = mytap . mysys examples +SUBDIRS = mytap mysys examples noinst_SCRIPTS = unit EXTRA_DIST = unit.pl diff --git a/unittest/maria/Makefile.am b/unittest/maria/Makefile.am new file mode 100644 index 00000000000..667d1e09a07 --- /dev/null +++ b/unittest/maria/Makefile.am @@ -0,0 +1,12 @@ + +AM_CPPFLAGS = @ZLIB_INCLUDES@ -I$(top_builddir)/include +AM_CPPFLAGS += -I$(top_srcdir)/include -I$(top_srcdir)/unittest/mytap + +LDADD = $(top_builddir)/unittest/mytap/libmytap.a \ + $(top_builddir)/storage/maria/libmaria.a \ + $(top_builddir)/mysys/libmysys.a \ + $(top_builddir)/dbug/libdbug.a \ + $(top_builddir)/strings/libmystrings.a + +noinst_PROGRAMS = trxman-t + diff --git a/unittest/maria/trxman-t.c b/unittest/maria/trxman-t.c new file mode 100644 index 00000000000..7536e5534bf --- /dev/null +++ b/unittest/maria/trxman-t.c @@ -0,0 +1,137 @@ +/* Copyright (C) 2006 MySQL AB + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ + +#include <tap.h> + +#include <my_global.h> +#include <my_sys.h> +#include <my_atomic.h> +#include <lf.h> +#include "../../storage/maria/trxman.h" + +pthread_attr_t rt_attr; +pthread_mutex_t rt_mutex; +pthread_cond_t rt_cond; +int rt_num_threads; + +int litmus; + +/* template for a test: the goal is to have litmus==0 if the test passed + +#define ITER nnn +pthread_handler_t test_XXXXXXXX(void *arg) +{ + int m=(*(int *)arg)/ITER, x; + + for (x=((int)(intptr)(&m)); m ; m--) + { + // do something with litmus + } + // do something more with litmus + + pthread_mutex_lock(&rt_mutex); + rt_num_threads--; + if (!rt_num_threads) + { + diag("whatever diagnostics we want", blabla, foobar); + pthread_cond_signal(&rt_cond); + } + pthread_mutex_unlock(&rt_mutex); + return 0; +} +#undef ITER + +*/ + +/* + create and end (commit or rollback) transactions randomly +*/ +#define MAX_ITER 100 +pthread_handler_t test_trxman(void *arg) +{ + int m=(*(int *)arg); + uint x, y, i, j, n; + TRX *trx[MAX_ITER]; + + for (x=((int)(intptr)(&m)); m > 0; ) + { + y= x= (x*3628273133 + 1500450271) % 9576890767; /* three prime numbers */ + m-= n= x % MAX_ITER; + for (i=0; i < n; i++) + trx[i]=trxman_new_trx(); + for (i=0; i < n; i++) + { + y=(y*19 + 7) % 31; + trxman_end_trx(trx[i], y & 1); + } + } + + pthread_mutex_lock(&rt_mutex); + rt_num_threads--; + if (!rt_num_threads) + pthread_cond_signal(&rt_cond); + pthread_mutex_unlock(&rt_mutex); + return 0; +} +#undef MAX_ITER + +void run_test(const char *test, pthread_handler handler, int n, int m) +{ + pthread_t t; + ulonglong now=my_getsystime(); + + litmus= 0; + + diag("Testing %s with %d threads, %d iterations... ", test, n, m); + for (rt_num_threads=n ; n ; n--) + pthread_create(&t, &rt_attr, handler, &m); + pthread_mutex_lock(&rt_mutex); + while (rt_num_threads) + pthread_cond_wait(&rt_cond, &rt_mutex); + pthread_mutex_unlock(&rt_mutex); + now=my_getsystime()-now; + ok(litmus == 0, "tested %s in %g secs (%d)", test, ((double)now)/1e7, litmus); +} + +int main() +{ + plan(1); + + if (my_atomic_initialize()) + return exit_status(); + + my_init(); + + pthread_attr_init(&rt_attr); + pthread_attr_setdetachstate(&rt_attr,PTHREAD_CREATE_DETACHED); + pthread_mutex_init(&rt_mutex, 0); + pthread_cond_init(&rt_cond, 0); + +#define CYCLES 10000 +#define THREADS 10 + + trxman_init(); + run_test("trxman", test_trxman, THREADS,CYCLES); + trxman_destroy(); + diag("mallocs: %d\n", trxman_allocated_transactions); + + pthread_mutex_destroy(&rt_mutex); + pthread_cond_destroy(&rt_cond); + pthread_attr_destroy(&rt_attr); + my_end(0); + return exit_status(); +} + diff --git a/unittest/mysys/my_atomic-t.c b/unittest/mysys/my_atomic-t.c index 4e2e496c3b1..8962131d45a 100644 --- a/unittest/mysys/my_atomic-t.c +++ b/unittest/mysys/my_atomic-t.c @@ -14,13 +14,17 @@ along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ -#include <my_global.h> #include <tap.h> + +#include <my_global.h> #include <my_sys.h> #include <my_atomic.h> +#include <lf.h> -int32 a32,b32,c32; +volatile uint32 a32,b32,c32; my_atomic_rwlock_t rwl; +LF_ALLOCATOR lf_allocator; +LF_HASH lf_hash; pthread_attr_t thr_attr; pthread_mutex_t mutex; @@ -30,11 +34,11 @@ int N; /* add and sub a random number in a loop. Must get 0 at the end */ pthread_handler_t test_atomic_add_handler(void *arg) { - int m=*(int *)arg; + int m=(*(int *)arg)/2; int32 x; - for (x=((int)(&m)); m ; m--) + for (x=((int)(intptr)(&m)); m ; m--) { - x=x*m+0x87654321; + x=(x*m+0x87654321) & INT_MAX32; my_atomic_rwlock_wrlock(&rwl); my_atomic_add32(&a32, x); my_atomic_rwlock_wrunlock(&rwl); @@ -61,15 +65,9 @@ pthread_handler_t test_atomic_add_handler(void *arg) pthread_handler_t test_atomic_swap_handler(void *arg) { int m=*(int *)arg; - int32 x; - - my_atomic_rwlock_wrlock(&rwl); - x=my_atomic_add32(&b32, 1); - my_atomic_rwlock_wrunlock(&rwl); + uint32 x=my_atomic_add32(&b32, 1); - my_atomic_rwlock_wrlock(&rwl); my_atomic_add32(&a32, x); - my_atomic_rwlock_wrunlock(&rwl); for (; m ; m--) { @@ -98,29 +96,29 @@ pthread_handler_t test_atomic_swap_handler(void *arg) /* same as test_atomic_add_handler, but my_atomic_add32 is emulated with - (slower) my_atomic_cas32 + my_atomic_cas32 - notice that the slowdown is proportional to the + number of CPUs */ pthread_handler_t test_atomic_cas_handler(void *arg) { - int m=*(int *)arg, ok; - int32 x,y; - for (x=((int)(&m)); m ; m--) + int m=(*(int *)arg)/2, ok=0; + int32 x, y; + for (x=((int)(intptr)(&m)); m ; m--) { my_atomic_rwlock_wrlock(&rwl); y=my_atomic_load32(&a32); my_atomic_rwlock_wrunlock(&rwl); - - x=x*m+0x87654321; + x=(x*m+0x87654321) & INT_MAX32; do { my_atomic_rwlock_wrlock(&rwl); ok=my_atomic_cas32(&a32, &y, y+x); my_atomic_rwlock_wrunlock(&rwl); - } while (!ok); + } while (!ok) ; do { my_atomic_rwlock_wrlock(&rwl); ok=my_atomic_cas32(&a32, &y, y-x); my_atomic_rwlock_wrunlock(&rwl); - } while (!ok); + } while (!ok) ; } pthread_mutex_lock(&mutex); N--; @@ -129,6 +127,128 @@ pthread_handler_t test_atomic_cas_handler(void *arg) return 0; } +/* + pin allocator - alloc and release an element in a loop +*/ +pthread_handler_t test_lf_pinbox(void *arg) +{ + int m=*(int *)arg; + int32 x=0; + LF_PINS *pins; + + pins=lf_pinbox_get_pins(&lf_allocator.pinbox); + + for (x=((int)(intptr)(&m)); m ; m--) + { + lf_pinbox_put_pins(pins); + pins=lf_pinbox_get_pins(&lf_allocator.pinbox); + } + lf_pinbox_put_pins(pins); + pthread_mutex_lock(&mutex); + N--; + if (!N) + pthread_cond_signal(&cond); + pthread_mutex_unlock(&mutex); + return 0; +} + +typedef union { + int32 data; + void *not_used; /* to guarantee sizeof(TLA) >= sizeof(void *) */ +} TLA; + +pthread_handler_t test_lf_alloc(void *arg) +{ + int m=(*(int *)arg)/2; + int32 x,y=0; + LF_PINS *pins; + + pins=lf_alloc_get_pins(&lf_allocator); + + for (x=((int)(intptr)(&m)); m ; m--) + { + TLA *node1, *node2; + x=(x*m+0x87654321) & INT_MAX32; + node1=(TLA *)lf_alloc_new(pins); + node1->data=x; + y+=node1->data; + node1->data=0; + node2=(TLA *)lf_alloc_new(pins); + node2->data=x; + y-=node2->data; + node2->data=0; + lf_alloc_free(pins, node1); + lf_alloc_free(pins, node2); + } + lf_alloc_put_pins(pins); + my_atomic_rwlock_wrlock(&rwl); + my_atomic_add32(&a32, y); + my_atomic_rwlock_wrunlock(&rwl); + pthread_mutex_lock(&mutex); + N--; + if (!N) + { + diag("%d mallocs, %d pins in stack", + lf_allocator.mallocs, lf_allocator.pinbox.pins_in_stack); +#ifdef MY_LF_EXTRA_DEBUG + a32|=lf_allocator.mallocs - lf_alloc_in_pool(&lf_allocator); +#endif + pthread_cond_signal(&cond); + } + pthread_mutex_unlock(&mutex); + return 0; +} + +#define N_TLH 1000 +pthread_handler_t test_lf_hash(void *arg) +{ + int m=(*(int *)arg)/(2*N_TLH); + int32 x,y,z,sum=0, ins=0; + LF_PINS *pins; + + pins=lf_hash_get_pins(&lf_hash); + + for (x=((int)(intptr)(&m)); m ; m--) + { + int i; + y=x; + for (i=0; i < N_TLH; i++) + { + x=(x*(m+i)+0x87654321) & INT_MAX32; + z=(x<0) ? -x : x; + if (lf_hash_insert(&lf_hash, pins, &z)) + { + sum+=z; + ins++; + } + } + for (i=0; i < N_TLH; i++) + { + y=(y*(m+i)+0x87654321) & INT_MAX32; + z=(y<0) ? -y : y; + if (lf_hash_delete(&lf_hash, pins, (uchar *)&z, sizeof(z))) + sum-=z; + } + } + lf_hash_put_pins(pins); + my_atomic_rwlock_wrlock(&rwl); + my_atomic_add32(&a32, sum); + my_atomic_add32(&b32, ins); + my_atomic_rwlock_wrunlock(&rwl); + pthread_mutex_lock(&mutex); + N--; + if (!N) + { + diag("%d mallocs, %d pins in stack, %d hash size, %d inserts", + lf_hash.alloc.mallocs, lf_hash.alloc.pinbox.pins_in_stack, + lf_hash.size, b32); + a32|=lf_hash.count; + pthread_cond_signal(&cond); + } + pthread_mutex_unlock(&mutex); + return 0; +} + void test_atomic(const char *test, pthread_handler handler, int n, int m) { pthread_t t; @@ -141,23 +261,24 @@ void test_atomic(const char *test, pthread_handler handler, int n, int m) diag("Testing %s with %d threads, %d iterations... ", test, n, m); for (N=n ; n ; n--) pthread_create(&t, &thr_attr, handler, &m); - pthread_mutex_lock(&mutex); while (N) pthread_cond_wait(&cond, &mutex); pthread_mutex_unlock(&mutex); now=my_getsystime()-now; - ok(a32 == 0, "tested %s in %g secs", test, ((double)now)/1e7); + ok(a32 == 0, "tested %s in %g secs (%d)", test, ((double)now)/1e7, a32); } int main() { int err; - diag("N CPUs: %d", my_getncpus()); + my_init(); + + diag("N CPUs: %d, atomic ops: %s", my_getncpus(), MY_ATOMIC_MODE); err= my_atomic_initialize(); - plan(4); + plan(7); ok(err == 0, "my_atomic_initialize() returned %d", err); pthread_attr_init(&thr_attr); @@ -165,15 +286,31 @@ int main() pthread_mutex_init(&mutex, 0); pthread_cond_init(&cond, 0); my_atomic_rwlock_init(&rwl); + lf_alloc_init(&lf_allocator, sizeof(TLA)); + lf_hash_init(&lf_hash, sizeof(int), LF_HASH_UNIQUE, 0, sizeof(int), 0, + &my_charset_bin); + +#ifdef MY_ATOMIC_MODE_RWLOCKS +#define CYCLES 10000 +#else +#define CYCLES 1000000 +#endif +#define THREADS 100 - test_atomic("my_atomic_add32", test_atomic_add_handler, 100,10000); - test_atomic("my_atomic_swap32", test_atomic_swap_handler, 100,10000); - test_atomic("my_atomic_cas32", test_atomic_cas_handler, 100,10000); + test_atomic("my_atomic_add32", test_atomic_add_handler, THREADS,CYCLES); + test_atomic("my_atomic_swap32", test_atomic_swap_handler, THREADS,CYCLES); + test_atomic("my_atomic_cas32", test_atomic_cas_handler, THREADS,CYCLES); + test_atomic("lf_pinbox", test_lf_pinbox, THREADS,CYCLES); + test_atomic("lf_alloc", test_lf_alloc, THREADS,CYCLES); + test_atomic("lf_hash", test_lf_hash, THREADS,CYCLES); + lf_hash_destroy(&lf_hash); + lf_alloc_destroy(&lf_allocator); pthread_mutex_destroy(&mutex); pthread_cond_destroy(&cond); pthread_attr_destroy(&thr_attr); my_atomic_rwlock_destroy(&rwl); + my_end(0); return exit_status(); } |