diff options
45 files changed, 3059 insertions, 181 deletions
diff --git a/configure.in b/configure.in index 968f7e0a8f8..6ef804cd36d 100644 --- a/configure.in +++ b/configure.in @@ -2261,9 +2261,9 @@ AC_ARG_WITH(man, if test "$with_man" = "yes" then man_dirs="man" - man1_files=`ls -1 $srcdir/man/*.1 | sed -e 's;^.*man/;;'` + man1_files=`ls -1 $srcdir/man/*.1 2>/dev/null| sed -e 's;^.*man/;;'` man1_files=`echo $man1_files` - man8_files=`ls -1 $srcdir/man/*.8 | sed -e 's;^.*man/;;'` + man8_files=`ls -1 $srcdir/man/*.8 2>/dev/null| sed -e 's;^.*man/;;'` man8_files=`echo $man8_files` else man_dirs="" 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..a696e008f03 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_prefix "" +# else +# define LOCK_prefix "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..0be8fdf9244 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_prefix "-no-xadd" +# else +# define MY_ATOMIC_MODE "gcc-amd64" LOCK_prefix +# endif #else -#define MY_ATOMIC_MODE "gcc-x86" LOCK +# ifdef MY_ATOMIC_NO_XADD +# define MY_ATOMIC_MODE "gcc-x86" LOCK_prefix "-no-xadd" +# else +# define MY_ATOMIC_MODE "gcc-x86" LOCK_prefix +# endif #endif /* fix -ansi errors while maintaining readability */ @@ -33,12 +41,12 @@ #ifndef MY_ATOMIC_NO_XADD #define make_atomic_add_body(S) \ - asm volatile (LOCK "; xadd %0, %1;" : "+r" (v) , "+m" (*a)) + asm volatile (LOCK_prefix "; xadd %0, %1;" : "+r" (v) , "+m" (*a)) #endif #define make_atomic_swap_body(S) \ - asm volatile ("; xchg %0, %1;" : "+r" (v) , "+m" (*a)) + asm volatile ("xchg %0, %1;" : "+r" (v) , "+m" (*a)) #define make_atomic_cas_body(S) \ - asm volatile (LOCK "; cmpxchg %3, %0; setz %2;" \ + asm volatile (LOCK_prefix "; cmpxchg %3, %0; setz %2;" \ : "+m" (*a), "+a" (*cmp), "=q" (ret): "r" (set)) #ifdef MY_ATOMIC_MODE_DUMMY @@ -47,13 +55,16 @@ #else /* Actually 32-bit reads/writes are always atomic on x86 - But we add LOCK here anyway to force memory barriers + But we add LOCK_prefix here anyway to force memory barriers */ #define make_atomic_load_body(S) \ ret=0; \ - asm volatile (LOCK "; cmpxchg %2, %0" \ + asm volatile (LOCK_prefix "; 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/atomic/x86-msvc.h b/include/atomic/x86-msvc.h index d4024a854fb..8f3e55aaed7 100644 --- a/include/atomic/x86-msvc.h +++ b/include/atomic/x86-msvc.h @@ -26,19 +26,19 @@ #ifndef _atomic_h_cleanup_ #define _atomic_h_cleanup_ "atomic/x86-msvc.h" -#define MY_ATOMIC_MODE "msvc-x86" LOCK +#define MY_ATOMIC_MODE "msvc-x86" LOCK_prefix #define make_atomic_add_body(S) \ _asm { \ _asm mov reg_ ## S, v \ - _asm LOCK xadd *a, reg_ ## S \ + _asm LOCK_prefix xadd *a, reg_ ## S \ _asm movzx v, reg_ ## S \ } #define make_atomic_cas_body(S) \ _asm { \ _asm mov areg_ ## S, *cmp \ _asm mov reg2_ ## S, set \ - _asm LOCK cmpxchg *a, reg2_ ## S \ + _asm LOCK_prefix cmpxchg *a, reg2_ ## S \ _asm mov *cmp, areg_ ## S \ _asm setz al \ _asm movzx ret, al \ @@ -56,13 +56,13 @@ #else /* Actually 32-bit reads/writes are always atomic on x86 - But we add LOCK here anyway to force memory barriers + But we add LOCK_prefix here anyway to force memory barriers */ #define make_atomic_load_body(S) \ _asm { \ _asm mov areg_ ## S, 0 \ _asm mov reg2_ ## S, areg_ ## S \ - _asm LOCK cmpxchg *a, reg2_ ## S \ + _asm LOCK_prefix cmpxchg *a, reg2_ ## S \ _asm mov ret, areg_ ## S \ } #define make_atomic_store_body(S) \ diff --git a/include/lf.h b/include/lf.h new file mode 100644 index 00000000000..4c6765b2d40 --- /dev/null +++ b/include/lf.h @@ -0,0 +1,240 @@ + +/* + 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 4 +#define LF_PURGATORY_SIZE 10 + +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_rwlock_by_pins(PINS) \ + my_atomic_rwlock_wrlock(&(PINS)->pinbox->pinstack.lock) +#define lf_rwunlock_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_rwlock_by_pins(PINS); \ + _lf_pin(PINS, PIN, ADDR); \ + lf_rwunlock_by_pins(PINS); \ + } while (0) +#define lf_unpin(PINS, PIN) lf_pin(PINS, PIN, NULL) +#define _lf_assert_pin(PINS, PIN) assert((PINS)->pin[PIN] != 0) +#define _lf_assert_unpin(PINS, PIN) assert((PINS)->pin[PIN]==0) + +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..921b55e68a2 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); \ @@ -118,6 +118,11 @@ make_atomic_swap(16) make_atomic_swap(32) make_atomic_swap(ptr) +#ifdef _atomic_h_cleanup_ +#include _atomic_h_cleanup_ +#undef _atomic_h_cleanup_ +#endif + #undef make_atomic_add #undef make_atomic_cas #undef make_atomic_load @@ -130,9 +135,8 @@ make_atomic_swap(ptr) #undef make_atomic_swap_body #undef intptr -#ifdef _atomic_h_cleanup_ -#include _atomic_h_cleanup_ -#undef _atomic_h_cleanup_ +#ifndef LF_BACKOFF +#define LF_BACKOFF (1) #endif #if SIZEOF_CHARP == SIZEOF_INT diff --git a/include/my_bit.h b/include/my_bit.h new file mode 100644 index 00000000000..58e8bb39683 --- /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(uint32 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(uint32 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 579379e7506..7f57b43f89f 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 115183bf9c2..fc83c583201 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..ade1c28d51c --- /dev/null +++ b/mysys/lf_dynarray.c @@ -0,0 +1,168 @@ +/* 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_prev_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; idx < dynarray_idxes_in_prev_level[i]; i--) /* no-op */; + ptr_ptr= &array->level[i]; + idx-= dynarray_idxes_in_prev_level[i]; + for (; i > 0; i--) + { + if (!(ptr= *ptr_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_prev_level[i]; + idx%= dynarray_idxes_in_prev_level[i]; + } + if (!(ptr= *ptr_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; idx < dynarray_idxes_in_prev_level[i]; i--) /* no-op */; + ptr_ptr= &array->level[i]; + idx-= dynarray_idxes_in_prev_level[i]; + for (; i > 0; i--) + { + if (!(ptr= *ptr_ptr)) + return(NULL); + ptr_ptr= ((void **)ptr) + idx / dynarray_idxes_in_prev_level[i]; + idx %= dynarray_idxes_in_prev_level[i]; + } + if (!(ptr= *ptr_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..a0425e89556 --- /dev/null +++ b/mysys/lf_hash.c @@ -0,0 +1,356 @@ +/* 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 ? + for non-unique hash, count only _distinct_ values +*/ +#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(LF_SLIST * 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=(intptr *)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 (not pinned and thus unusable) + + 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(head, node->hashnr, node->key, node->keylen, + &cursor, pins) && + (flags & LF_HASH_UNIQUE)) + res=0; /* duplicate found */ + 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; /* inserted ok */ + } + } 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(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(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(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.0 +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_rwlock_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_rwunlock_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_rwunlock_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_rwlock_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_rwunlock_by_pins(pins); + return 1; + } + my_atomic_add32(&hash->count, -1); + lf_rwunlock_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_rwlock_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_rwunlock_by_pins(pins); + return found ? found+1 : 0; +} + +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))) + { + my_free((void *)dummy, MYF(0)); + 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..fbeb3d63bef 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> @@ -36,7 +35,7 @@ */ int my_atomic_initialize() { - DBUG_ASSERT(sizeof(intptr) == sizeof(void *)); + char assert_the_size[sizeof(intptr) == sizeof(void *) ? 1 : -1]; /* currently the only thing worth checking is SMP/UP issue */ #ifdef MY_ATOMIC_MODE_DUMMY return my_getncpus() == 1 ? MY_ATOMIC_OK : MY_ATOMIC_NOT_1CPU; 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 4a069e662f9..449ff3e33c2 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 4545ce99159..b3106c59a40 100644 --- a/sql/mysql_priv.h +++ b/sql/mysql_priv.h @@ -1544,7 +1544,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 9dfc725773a..ad8cadfef7a 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" @@ -463,7 +464,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; @@ -2127,7 +2128,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) { @@ -2259,9 +2260,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 @@ -3493,9 +3494,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 { @@ -3506,15 +3507,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 } } @@ -6269,8 +6270,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 c41f3afae60..ff02a1d24b1 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 fc7ed7ff673..76554f2ae79 100644 --- a/sql/sql_parse.cc +++ b/sql/sql_parse.cc @@ -5762,10 +5762,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 ed91719fd46..8574c2ea0d3 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 c4c40ea63c8..ff7f45bf10a 100644 --- a/sql/sql_test.cc +++ b/sql/sql_test.cc @@ -457,7 +457,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(); @@ -532,7 +532,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 Events::get_instance()->dump_internal_status(); diff --git a/storage/maria/Makefile.am b/storage/maria/Makefile.am index eb8cdfa3aba..ee5f6238b46 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 trnman.h lockman.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 trnman.c lockman.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 4cdf0c4c086..d9e42467351 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/lockman.c b/storage/maria/lockman.c new file mode 100644 index 00000000000..e8ddbd1a25a --- /dev/null +++ b/storage/maria/lockman.c @@ -0,0 +1,681 @@ +// TODO lock escalation, instant duration locks +// automatically place S instead of LS if possible +/* + TODO optimization: table locks - they have completely + different characteristics. long lists, few distinct resources - + slow to scan, [possibly] high retry rate +*/ +/* 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 */ + +#include <my_global.h> +#include <my_sys.h> +#include <my_bit.h> +#include <lf.h> +#include "lockman.h" + +/* + Lock compatibility matrix. + + It's asymmetric. Read it as "Somebody has the lock <value in the row + label>, can I set the lock <value in the column label> ?" + + ') Though you can take LS lock while somebody has S lock, it makes no + sense - it's simpler to take S lock too. + + ") Strictly speaking you can take LX lock while somebody has S lock. + But in this case you lock no rows, because all rows are locked by this + somebody. So we prefer to define that LX cannot be taken when S + exists. Same about LX and X. + + 1 - compatible + 0 - incompatible + -1 - "impossible", so that we can assert the impossibility. +*/ +static int lock_compatibility_matrix[10][10]= +{ /* N S X IS IX SIX LS LX SLX LSIX */ + { -1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, /* N */ + { -1, 1, 0, 1, 0, 0, 1, 0, 0, 0 }, /* S */ + { -1, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, /* X */ + { -1, 1, 0, 1, 1, 1, 1, 1, 1, 1 }, /* IS */ + { -1, 0, 0, 1, 1, 0, 1, 1, 0, 1 }, /* IX */ + { -1, 0, 0, 1, 0, 0, 1, 0, 0, 0 }, /* SIX */ + { -1, 1, 0, 1, 0, 0, 1, 0, 0, 0 }, /* LS */ + { -1, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, /* LX */ + { -1, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, /* SLX */ + { -1, 0, 0, 1, 0, 0, 1, 0, 0, 0 } /* LSIX */ +}; + +/* + Lock combining matrix. + + It's symmetric. Read it as "what lock level L is identical to the + set of two locks A and B" + + One should never get N from it, we assert the impossibility +*/ +static enum lock_type lock_combining_matrix[10][10]= +{/* N S X IS IX SIX LS LX SLX LSIX */ + { N, S, X, IS, IX, SIX, S, SLX, SLX, SIX}, /* N */ + { S, S, X, S, SIX, SIX, S, SLX, SLX, SIX}, /* S */ + { X, X, X, X, X, X, X, X, X, X}, /* X */ + { IS, S, X, IS, IX, SIX, LS, LX, SLX, LSIX}, /* IS */ + { IX, SIX, X, IX, IX, SIX, LSIX, LX, SLX, LSIX}, /* IX */ + { SIX, SIX, X, SIX, SIX, SIX, SIX, SLX, SLX, SIX}, /* SIX */ + { LS, S, X, LS, LSIX, SIX, LS, LX, SLX, LSIX}, /* LS */ + { LX, SLX, X, LX, LX, SLX, LX, LX, SLX, LX}, /* LX */ + { SLX, SLX, X, SLX, SLX, SLX, SLX, SLX, SLX, SLX}, /* SLX */ + { LSIX, SIX, X, LSIX, LSIX, SIX, LSIX, LX, SLX, LSIX} /* LSIX */ +}; + +#define REPEAT_ONCE_MORE 0 +#define OK_TO_PLACE_THE_LOCK 1 +#define OK_TO_PLACE_THE_REQUEST 2 +#define ALREADY_HAVE_THE_LOCK 4 +#define ALREADY_HAVE_THE_REQUEST 8 +#define PLACE_NEW_DISABLE_OLD 16 +#define REQUEST_NEW_DISABLE_OLD 32 +#define RESOURCE_WAS_UNLOCKED 64 + +#define NEED_TO_WAIT (OK_TO_PLACE_THE_REQUEST | ALREADY_HAVE_THE_REQUEST |\ + REQUEST_NEW_DISABLE_OLD) +#define ALREADY_HAVE (ALREADY_HAVE_THE_LOCK | ALREADY_HAVE_THE_REQUEST) +#define LOCK_UPGRADE (PLACE_NEW_DISABLE_OLD | REQUEST_NEW_DISABLE_OLD) + + +/* + the return codes for lockman_getlock + + It's asymmetric. Read it as "I have the lock <value in the row label>, + what value should be returned for <value in the column label> ?" + + 0 means impossible combination (assert!) + + Defines below help to preserve the table structure. + I/L/A values are self explanatory + x means the combination is possible (assert should not crash) + but cannot happen in row locks, only in table locks (S,X), or + lock escalations (LS,LX) +*/ +#define I GOT_THE_LOCK_NEED_TO_LOCK_A_SUBRESOURCE +#define L GOT_THE_LOCK_NEED_TO_INSTANT_LOCK_A_SUBRESOURCE +#define A GOT_THE_LOCK +#define x GOT_THE_LOCK +static enum lockman_getlock_result getlock_result[10][10]= +{/* N S X IS IX SIX LS LX SLX LSIX */ + { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, /* N */ + { 0, x, 0, A, 0, 0, x, 0, 0, 0}, /* S */ + { 0, x, x, A, A, 0, x, x, 0, 0}, /* X */ + { 0, 0, 0, I, 0, 0, 0, 0, 0, 0}, /* IS */ + { 0, 0, 0, I, I, 0, 0, 0, 0, 0}, /* IX */ + { 0, x, 0, A, I, 0, x, 0, 0, 0}, /* SIX */ + { 0, 0, 0, L, 0, 0, x, 0, 0, 0}, /* LS */ + { 0, 0, 0, L, L, 0, x, x, 0, 0}, /* LX */ + { 0, x, 0, A, L, 0, x, x, 0, 0}, /* SLX */ + { 0, 0, 0, L, I, 0, x, 0, 0, 0} /* LSIX */ +}; +#undef I +#undef L +#undef A +#undef x + +LF_REQUIRE_PINS(4); + +typedef struct lockman_lock { + uint64 resource; + struct lockman_lock *lonext; + intptr volatile link; + uint32 hashnr; +//#warning TODO - remove hashnr from LOCK + uint16 loid; + uchar lock; /* sizeof(uchar) <= sizeof(enum) */ + uchar flags; +} LOCK; + +#define IGNORE_ME 1 +#define UPGRADED 2 + +typedef struct { + intptr volatile *prev; + LOCK *curr, *next; + LOCK *blocker, *upgrade_from; +} CURSOR; + +#define PTR(V) (LOCK *)((V) & (~(intptr)1)) +#define DELETED(V) ((V) & 1) + +/* + NOTE + cursor is positioned in either case + pins[0..3] are used, they are NOT removed on return +*/ +static int lockfind(LOCK * volatile *head, LOCK *node, + CURSOR *cursor, LF_PINS *pins) +{ + uint32 hashnr, cur_hashnr; + uint64 resource, cur_resource; + intptr link; + my_bool cur_active, compatible, upgrading, prev_active; + enum lock_type lock, prev_lock, cur_lock; + uint16 loid, cur_loid; + int upgraded_pairs, cur_flags, flags; + + hashnr= node->hashnr; + resource= node->resource; + lock= node->lock; + loid= node->loid; + flags= node->flags; + +retry: + cursor->prev= (intptr *)head; + prev_lock= N; + cur_active= TRUE; + compatible= TRUE; + upgrading= FALSE; + cursor->blocker= cursor->upgrade_from= 0; + _lf_unpin(pins, 3); + upgraded_pairs= 0; + do { + cursor->curr= PTR(*cursor->prev); + _lf_pin(pins,1,cursor->curr); + } while(*cursor->prev != (intptr)cursor->curr && LF_BACKOFF); + for (;;) + { + if (!cursor->curr) + break; + do { + 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_resource= cursor->curr->resource; + cur_lock= cursor->curr->lock; + cur_loid= cursor->curr->loid; + cur_flags= cursor->curr->flags; + if (*cursor->prev != (intptr)cursor->curr) + { + LF_BACKOFF; + goto retry; + } + if (!DELETED(link)) + { + if (cur_hashnr > hashnr || + (cur_hashnr == hashnr && cur_resource >= resource)) + { + if (cur_hashnr > hashnr || cur_resource > resource) + { + if (upgraded_pairs != 0) + goto retry; + break; + } + /* ok, we have a lock for this resource */ + DBUG_ASSERT(lock_compatibility_matrix[prev_lock][cur_lock] >= 0); + DBUG_ASSERT(lock_compatibility_matrix[cur_lock][lock] >= 0); + if (cur_flags & UPGRADED) + upgraded_pairs++; + if ((cur_flags & IGNORE_ME) && ! (flags & IGNORE_ME)) + { + DBUG_ASSERT(cur_active); + upgraded_pairs--; + if (cur_loid == loid) + cursor->upgrade_from= cursor->curr; + } + else + { + prev_active= cur_active; + cur_active&= lock_compatibility_matrix[prev_lock][cur_lock]; + if (upgrading && !cur_active && upgraded_pairs == 0) + break; + if (prev_active && !cur_active) + { + cursor->blocker= cursor->curr; + _lf_pin(pins, 3, cursor->curr); + } + if (cur_loid == loid) + { + /* we already have a lock on this resource */ + DBUG_ASSERT(lock_combining_matrix[cur_lock][lock] != N); + DBUG_ASSERT(!upgrading); /* can happen only once */ + if (lock_combining_matrix[cur_lock][lock] == cur_lock) + { + /* new lock is compatible */ + return cur_active ? ALREADY_HAVE_THE_LOCK + : ALREADY_HAVE_THE_REQUEST; + } + /* not compatible, upgrading */ + upgrading= TRUE; + cursor->upgrade_from= cursor->curr; + } + else + { + if (!lock_compatibility_matrix[cur_lock][lock]) + { + compatible= FALSE; + cursor->blocker= cursor->curr; + _lf_pin(pins, 3, cursor->curr); + } + prev_lock= lock_combining_matrix[prev_lock][cur_lock]; + DBUG_ASSERT(prev_lock != N); + } + } + } + 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); + } + /* + either the end of lock list - no more locks for this resource, + or upgrading and the end of active lock list + */ + if (upgrading) + { + if (compatible) + return PLACE_NEW_DISABLE_OLD; + else + return REQUEST_NEW_DISABLE_OLD; + } + if (cur_active && compatible) + { + /* + either no locks for this resource or all are compatible. + ok to place the lock in any case. + */ + return prev_lock == N ? RESOURCE_WAS_UNLOCKED + : OK_TO_PLACE_THE_LOCK; + } + /* we have a lock conflict. ok to place a lock request. And wait */ + return OK_TO_PLACE_THE_REQUEST; +} + +/* + NOTE + it uses pins[0..3], on return pins 0..2 are removed, pin 3 (blocker) stays +*/ +static int lockinsert(LOCK * volatile *head, LOCK *node, LF_PINS *pins, + LOCK **blocker) +{ + CURSOR cursor; + int res; + + do + { + res= lockfind(head, node, &cursor, pins); + DBUG_ASSERT(res != ALREADY_HAVE_THE_REQUEST); + if (!(res & ALREADY_HAVE)) + { + if (res & LOCK_UPGRADE) + { + node->flags|= UPGRADED; + node->lock= lock_combining_matrix[cursor.upgrade_from->lock][node->lock]; + } + node->link= (intptr)cursor.curr; + DBUG_ASSERT(node->link != (intptr)node); + DBUG_ASSERT(cursor.prev != &node->link); + if (!my_atomic_casptr((void **)cursor.prev, (void **)&cursor.curr, node)) + res= REPEAT_ONCE_MORE; + if (res & LOCK_UPGRADE) + cursor.upgrade_from->flags|= IGNORE_ME; + } + + } while (res == REPEAT_ONCE_MORE); + _lf_unpin(pins, 0); + _lf_unpin(pins, 1); + _lf_unpin(pins, 2); + /* + note that cursor.curr is NOT pinned on return. + this is ok as it's either a dummy node for initialize_bucket + and dummy nodes don't need pinning, + or it's a lock of the same transaction for lockman_getlock, + and it cannot be removed by another thread + */ + *blocker= cursor.blocker ? cursor.blocker : cursor.curr; + return res; +} + +/* + NOTE + it uses pins[0..3], on return pins 0..2 are removed, pin 3 (blocker) stays +*/ +static int lockpeek(LOCK * volatile *head, LOCK *node, LF_PINS *pins, + LOCK **blocker) +{ + CURSOR cursor; + int res; + + res= lockfind(head, node, &cursor, pins); + + _lf_unpin(pins, 0); + _lf_unpin(pins, 1); + _lf_unpin(pins, 2); + if (blocker) + *blocker= cursor.blocker; + return res; +} + +/* + NOTE + it uses pins[0..3], on return all pins are removed. + + One _must_ have the lock (or request) to call this +*/ +static int lockdelete(LOCK * volatile *head, LOCK *node, LF_PINS *pins) +{ + CURSOR cursor; + int res; + + do + { + res= lockfind(head, node, &cursor, pins); + DBUG_ASSERT(res & ALREADY_HAVE); + + if (cursor.upgrade_from) + cursor.upgrade_from->flags&= ~IGNORE_ME; + + 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 + lockfind(head, node, &cursor, pins); + } + else + res= REPEAT_ONCE_MORE; + } while (res == REPEAT_ONCE_MORE); + _lf_unpin(pins, 0); + _lf_unpin(pins, 1); + _lf_unpin(pins, 2); + _lf_unpin(pins, 3); + return res; +} + +void lockman_init(LOCKMAN *lm, loid_to_lo_func *func, uint timeout) +{ + lf_alloc_init(&lm->alloc,sizeof(LOCK)); + lf_dynarray_init(&lm->array, sizeof(LOCK **)); + lm->size= 1; + lm->count= 0; + lm->loid_to_lo= func; + lm->lock_timeout= timeout; +} + +void lockman_destroy(LOCKMAN *lm) +{ + LOCK *el= *(LOCK **)_lf_dynarray_lvalue(&lm->array, 0); + while (el) + { + intptr next= el->link; + if (el->hashnr & 1) + lf_alloc_real_free(&lm->alloc, el); + else + my_free((void *)el, MYF(0)); + el= (LOCK *)next; + } + lf_alloc_destroy(&lm->alloc); + lf_dynarray_destroy(&lm->array); +} + +/* TODO: optimize it */ +#define MAX_LOAD 1 + +static void initialize_bucket(LOCKMAN *lm, LOCK * volatile *node, + uint bucket, LF_PINS *pins) +{ + int res; + uint parent= my_clear_highest_bit(bucket); + LOCK *dummy= (LOCK *)my_malloc(sizeof(LOCK), MYF(MY_WME)); + LOCK **tmp= 0, *cur; + LOCK * volatile *el= _lf_dynarray_lvalue(&lm->array, parent); + + if (*el == NULL && bucket) + initialize_bucket(lm, el, parent, pins); + dummy->hashnr= my_reverse_bits(bucket); + dummy->loid= 0; + dummy->lock= X; /* doesn't matter, in fact */ + dummy->resource= 0; + dummy->flags= 0; + res= lockinsert(el, dummy, pins, &cur); + DBUG_ASSERT(res & (ALREADY_HAVE_THE_LOCK | RESOURCE_WAS_UNLOCKED)); + if (res & ALREADY_HAVE_THE_LOCK) + { + my_free((void *)dummy, MYF(0)); + dummy= cur; + } + my_atomic_casptr((void **)node, (void **)&tmp, dummy); +} + +static inline uint calc_hash(uint64 resource) +{ + const uchar *pos= (uchar *)&resource; + ulong nr1= 1, nr2= 4, i; + for (i= 0; i < sizeof(resource) ; i++, pos++) + { + nr1^= (ulong) ((((uint) nr1 & 63)+nr2) * ((uint)*pos)) + (nr1 << 8); + nr2+= 3; + } + return nr1 & INT_MAX32; +} + +/* + RETURN + see enum lockman_getlock_result + NOTE + uses pins[0..3], they're removed on return +*/ +enum lockman_getlock_result lockman_getlock(LOCKMAN *lm, LOCK_OWNER *lo, + uint64 resource, + enum lock_type lock) +{ + int res; + uint csize, bucket, hashnr; + LOCK *node, * volatile *el, *blocker; + LF_PINS *pins= lo->pins; + enum lock_type old_lock; + + DBUG_ASSERT(lo->loid); + lf_rwlock_by_pins(pins); + node= (LOCK *)_lf_alloc_new(pins); + node->flags= 0; + node->lock= lock; + node->loid= lo->loid; + node->resource= resource; + hashnr= calc_hash(resource); + bucket= hashnr % lm->size; + el= _lf_dynarray_lvalue(&lm->array, bucket); + if (*el == NULL) + initialize_bucket(lm, el, bucket, pins); + node->hashnr= my_reverse_bits(hashnr) | 1; + res= lockinsert(el, node, pins, &blocker); + if (res & ALREADY_HAVE) + { + old_lock= blocker->lock; + _lf_assert_unpin(pins, 3); /* unpin should not be needed */ + _lf_alloc_free(pins, node); + lf_rwunlock_by_pins(pins); + res= getlock_result[old_lock][lock]; + DBUG_ASSERT(res); + return res; + } + /* a new value was added to the hash */ + csize= lm->size; + if ((my_atomic_add32(&lm->count, 1)+1.0) / csize > MAX_LOAD) + my_atomic_cas32(&lm->size, &csize, csize*2); + node->lonext= lo->all_locks; + lo->all_locks= node; + for ( ; res & NEED_TO_WAIT; res= lockpeek(el, node, pins, &blocker)) + { + LOCK_OWNER *wait_for_lo; + ulonglong deadline; + struct timespec timeout; + + _lf_assert_pin(pins, 3); /* blocker must be pinned here */ + lf_rwunlock_by_pins(pins); + + wait_for_lo= lm->loid_to_lo(blocker->loid); + /* + now, this is tricky. blocker is not necessarily a LOCK + we're waiting for. If it's compatible with what we want, + then we're waiting for a lock that blocker is waiting for + (see two places where blocker is set in lockfind) + In the latter case, let's "dereference" it + */ + if (lock_compatibility_matrix[blocker->lock][lock]) + { + blocker= wait_for_lo->all_locks; + lf_pin(pins, 3, blocker); + if (blocker != wait_for_lo->all_locks) + { + lf_rwlock_by_pins(pins); + continue; + } + wait_for_lo= wait_for_lo->waiting_for; + } + + /* + note that the blocker transaction may have ended by now, + its LOCK_OWNER and short id were reused, so 'wait_for_lo' may point + to an unrelated - albeit valid - LOCK_OWNER + */ + if (!wait_for_lo) + { + /* blocker transaction has ended, short id was released */ + lf_rwlock_by_pins(pins); + continue; + } + /* + We lock a mutex - it may belong to a wrong LOCK_OWNER, but it must + belong to _some_ LOCK_OWNER. It means, we can never free() a LOCK_OWNER, + if there're other active LOCK_OWNERs. + */ +#warning race condition here + pthread_mutex_lock(wait_for_lo->mutex); + if (DELETED(blocker->link)) + { + /* + blocker transaction was ended, or a savepoint that owned + the lock was rolled back. Either way - the lock was removed + */ + pthread_mutex_unlock(wait_for_lo->mutex); + lf_rwlock_by_pins(pins); + continue; + } + /* yuck. waiting */ + lo->waiting_for= wait_for_lo; + + deadline= my_getsystime() + lm->lock_timeout * 10000; + timeout.tv_sec= deadline/10000000; + timeout.tv_nsec= (deadline % 10000000) * 100; + do + { + pthread_cond_timedwait(wait_for_lo->cond, wait_for_lo->mutex, &timeout); + } while (!DELETED(blocker->link) && my_getsystime() < deadline); + pthread_mutex_unlock(wait_for_lo->mutex); + lf_rwlock_by_pins(pins); + if (!DELETED(blocker->link)) + { + /* + timeout. + note that we _don't_ release the lock request here. + Instead we're relying on the caller to abort the transaction, + and release all locks at once - see lockman_release_locks() + */ + lf_rwunlock_by_pins(pins); + return DIDNT_GET_THE_LOCK; + } + lo->waiting_for= 0; + } + _lf_assert_unpin(pins, 3); /* unpin should not be needed */ + lf_rwunlock_by_pins(pins); + return getlock_result[lock][lock]; +} + +/* + RETURN + 0 - deleted + 1 - didn't (not found) + NOTE + see lockdelete() for pin usage notes +*/ +int lockman_release_locks(LOCKMAN *lm, LOCK_OWNER *lo) +{ + LOCK * volatile *el, *node; + uint bucket; + LF_PINS *pins= lo->pins; + + pthread_mutex_lock(lo->mutex); + lf_rwlock_by_pins(pins); + for (node= lo->all_locks; node; node= node->lonext) + { + bucket= calc_hash(node->resource) % lm->size; + el= _lf_dynarray_lvalue(&lm->array, bucket); + if (*el == NULL) + initialize_bucket(lm, el, bucket, pins); + lockdelete(el, node, pins); + my_atomic_add32(&lm->count, -1); + } + lf_rwunlock_by_pins(pins); + lo->all_locks= 0; + /* now signal all waiters */ + pthread_cond_broadcast(lo->cond); + pthread_mutex_unlock(lo->mutex); + return 0; +} + +#ifdef MY_LF_EXTRA_DEBUG +/* + NOTE + the function below is NOT thread-safe !!! +*/ +static char *lock2str[]= +{ "N", "S", "X", "IS", "IX", "SIX", "LS", "LX", "SLX", "LSIX" }; +void print_lockhash(LOCKMAN *lm) +{ + LOCK *el= *(LOCK **)_lf_dynarray_lvalue(&lm->array, 0); + printf("hash: size=%u count=%u\n", lm->size, lm->count); + while (el) + { + intptr next= el->link; + if (el->hashnr & 1) + printf("0x%08x { resource %llu, loid %u, lock %s", + el->hashnr, el->resource, el->loid, lock2str[el->lock]); + else + { + printf("0x%08x { dummy ", el->hashnr); + DBUG_ASSERT(el->resource == 0 && el->loid == 0 && el->lock == X); + } + if (el->flags & IGNORE_ME) printf(" IGNORE_ME"); + if (el->flags & UPGRADED) printf(" UPGRADED"); + printf("}\n"); + el= (LOCK *)next; + } +} +#endif + diff --git a/storage/maria/lockman.h b/storage/maria/lockman.h new file mode 100644 index 00000000000..a3c96786935 --- /dev/null +++ b/storage/maria/lockman.h @@ -0,0 +1,73 @@ +/* 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 */ + +#ifndef _lockman_h +#define _lockman_h + +/* + N - "no lock", not a lock, used sometimes to simplify the code + S - Shared + X - eXclusive + IS - Intention Shared + IX - Intention eXclusive + SIX - Shared + Intention eXclusive + LS - Loose Shared + LX - Loose eXclusive + SLX - Shared + Loose eXclusive + LSIX - Loose Shared + Intention eXclusive +*/ +enum lock_type { N, S, X, IS, IX, SIX, LS, LX, SLX, LSIX }; + +struct lockman_lock; + +typedef struct st_lock_owner LOCK_OWNER; +struct st_lock_owner { + LF_PINS *pins; + struct lockman_lock *all_locks; + LOCK_OWNER *waiting_for; + pthread_cond_t *cond; /* transactions waiting for this, wait on 'cond' */ + pthread_mutex_t *mutex; /* mutex is required to use 'cond' */ + uint16 loid; +}; + +typedef LOCK_OWNER *loid_to_lo_func(uint16); +typedef struct { + LF_DYNARRAY array; /* hash itself */ + LF_ALLOCATOR alloc; /* allocator for elements */ + int32 volatile size; /* size of array */ + int32 volatile count; /* number of elements in the hash */ + uint lock_timeout; + loid_to_lo_func *loid_to_lo; +} LOCKMAN; + +enum lockman_getlock_result { + DIDNT_GET_THE_LOCK=0, GOT_THE_LOCK, + GOT_THE_LOCK_NEED_TO_LOCK_A_SUBRESOURCE, + GOT_THE_LOCK_NEED_TO_INSTANT_LOCK_A_SUBRESOURCE +}; + +void lockman_init(LOCKMAN *, loid_to_lo_func *, uint); +void lockman_destroy(LOCKMAN *); +enum lockman_getlock_result lockman_getlock(LOCKMAN *lm, LOCK_OWNER *lo, + uint64 resource, + enum lock_type lock); +int lockman_release_locks(LOCKMAN *, LOCK_OWNER *); + +#ifdef EXTRA_DEBUG +void print_lockhash(LOCKMAN *lm); +#endif + +#endif 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/trnman.c b/storage/maria/trnman.c new file mode 100644 index 00000000000..49f49a3e26b --- /dev/null +++ b/storage/maria/trnman.c @@ -0,0 +1,332 @@ +/* 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 */ + + +#include <my_global.h> +#include <my_sys.h> +#include <lf.h> +#include "trnman.h" + +uint trnman_active_transactions, trnman_allocated_transactions; + +static TRN active_list_min, active_list_max, + committed_list_min, committed_list_max, *pool; + +static pthread_mutex_t LOCK_trn_list; +static TrID global_trid_generator; + +static LF_HASH trid_to_trn; +static LOCKMAN maria_lockman; + +static TRN **short_trid_to_trn; +static my_atomic_rwlock_t LOCK_short_trid_to_trn, LOCK_pool; + +static byte *trn_get_hash_key(const byte *trn,uint* len, my_bool unused) +{ + *len= sizeof(TrID); + return (byte *) & ((*((TRN **)trn))->trid); +} + +static LOCK_OWNER *trnman_short_trid_to_TRN(uint16 short_trid) +{ + TRN *trn; + my_atomic_rwlock_rdlock(&LOCK_short_trid_to_trn); + trn= my_atomic_loadptr((void **)&short_trid_to_trn[short_trid]); + my_atomic_rwlock_rdunlock(&LOCK_short_trid_to_trn); + return (LOCK_OWNER *)trn; +} + +int trnman_init() +{ + pthread_mutex_init(&LOCK_trn_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; + trnman_active_transactions= 0; + trnman_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_trn, sizeof(TRN*), LF_HASH_UNIQUE, + 0, 0, trn_get_hash_key, 0); + my_atomic_rwlock_init(&LOCK_short_trid_to_trn); + my_atomic_rwlock_init(&LOCK_pool); + short_trid_to_trn= (TRN **)my_malloc(SHORT_TRID_MAX*sizeof(TRN*), + MYF(MY_WME|MY_ZEROFILL)); + if (!short_trid_to_trn) + return 1; + short_trid_to_trn--; /* min short_trid is 1 */ + + lockman_init(&maria_lockman, &trnman_short_trid_to_TRN, 10000); + + return 0; +} + +int trnman_destroy() +{ + DBUG_ASSERT(trid_to_trn.count == 0); + DBUG_ASSERT(trnman_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) + { + TRN *trn= pool; + pool= pool->next; + DBUG_ASSERT(trn->locks.mutex == 0); + DBUG_ASSERT(trn->locks.cond == 0); + my_free((void *)trn, MYF(0)); + } + lf_hash_destroy(&trid_to_trn); + pthread_mutex_destroy(&LOCK_trn_list); + my_atomic_rwlock_destroy(&LOCK_short_trid_to_trn); + my_atomic_rwlock_destroy(&LOCK_pool); + my_free((void *)(short_trid_to_trn+1), MYF(0)); + lockman_destroy(&maria_lockman); +} + +static TrID new_trid() +{ + DBUG_ASSERT(global_trid_generator < 0xffffffffffffLL); + safe_mutex_assert_owner(&LOCK_trn_list); + return ++global_trid_generator; +} + +static void set_short_trid(TRN *trn) +{ + int i= (global_trid_generator + (intptr)trn) * 312089 % SHORT_TRID_MAX; + my_atomic_rwlock_wrlock(&LOCK_short_trid_to_trn); + for ( ; ; i= i % SHORT_TRID_MAX + 1) /* the range is [1..SHORT_TRID_MAX] */ + { + void *tmp= NULL; + if (short_trid_to_trn[i] == NULL && + my_atomic_casptr((void **)&short_trid_to_trn[i], &tmp, trn)) + break; + } + my_atomic_rwlock_wrunlock(&LOCK_short_trid_to_trn); + trn->locks.loid= i; +} + +TRN *trnman_new_trn(pthread_mutex_t *mutex, pthread_cond_t *cond) +{ + TRN *trn; + + /* + see trnman_end_trn to see why we need a mutex here + + and as we have a mutex, we can as well do everything + under it - allocating a TRN, incrementing trnman_active_transactions, + setting trn->min_read_from. + + Note that all the above is fast. generating short_trid may be slow, + as it involves scanning a big array - so it's still done + outside of the mutex. + */ + + pthread_mutex_lock(&LOCK_trn_list); + trnman_active_transactions++; + + trn= pool; + my_atomic_rwlock_wrlock(&LOCK_pool); + while (trn && !my_atomic_casptr((void **)&pool, (void **)&trn, + (void *)trn->next)) + /* no-op */; + my_atomic_rwlock_wrunlock(&LOCK_pool); + + if (!trn) + { + trn= (TRN *)my_malloc(sizeof(TRN), MYF(MY_WME)); + if (!trn) + { + pthread_mutex_unlock(&LOCK_trn_list); + return 0; + } + trnman_allocated_transactions++; + } + + trn->min_read_from= active_list_min.next->trid; + + trn->trid= new_trid(); + trn->locks.loid= 0; + + trn->next= &active_list_max; + trn->prev= active_list_max.prev; + active_list_max.prev= trn->prev->next= trn; + pthread_mutex_unlock(&LOCK_trn_list); + + trn->pins= lf_hash_get_pins(&trid_to_trn); + + if (!trn->min_read_from) + trn->min_read_from= trn->trid; + + trn->locks.mutex= mutex; + trn->locks.cond= cond; + trn->commit_trid= 0; + trn->locks.waiting_for= 0; + trn->locks.all_locks= 0; + trn->locks.pins= lf_alloc_get_pins(&maria_lockman.alloc); + + set_short_trid(trn); /* this must be the last! */ + + return trn; +} + +/* + remove a trn from the active list, + move to committed list, + set commit_trid + + TODO + integrate with 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 ???) XXX - why did I think it must be done atomically ? + + trid_to_trn, active_list_*, and committed_list_* can be + updated asyncronously. +*/ +void trnman_end_trn(TRN *trn, my_bool commit) +{ + int res; + TRN *free_me= 0; + LF_PINS *pins= trn->pins; + + pthread_mutex_lock(&LOCK_trn_list); + trn->next->prev= trn->prev; + trn->prev->next= trn->next; + + if (trn->prev == &active_list_min) + { + TRN *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; + } + } + + if (commit && active_list_min.next != &active_list_max) + { + trn->commit_trid= global_trid_generator; + + trn->next= &committed_list_max; + trn->prev= committed_list_max.prev; + committed_list_max.prev= trn->prev->next= trn; + + res= lf_hash_insert(&trid_to_trn, pins, &trn); + DBUG_ASSERT(res == 0); + } + else + { + trn->next= free_me; + free_me= trn; + } + trnman_active_transactions--; + pthread_mutex_unlock(&LOCK_trn_list); + + lockman_release_locks(&maria_lockman, &trn->locks); + trn->locks.mutex= 0; + trn->locks.cond= 0; + my_atomic_rwlock_rdlock(&LOCK_short_trid_to_trn); + my_atomic_storeptr((void **)&short_trid_to_trn[trn->locks.loid], 0); + my_atomic_rwlock_rdunlock(&LOCK_short_trid_to_trn); + + + while (free_me) // XXX send them to the purge thread + { + int res; + TRN *t= free_me; + free_me= free_me->next; + + res= lf_hash_delete(&trid_to_trn, pins, &t->trid, sizeof(TrID)); + + trnman_free_trn(t); + } + + lf_hash_put_pins(pins); + lf_pinbox_put_pins(trn->locks.pins); +} + +/* + free a trn (add to the pool, that is) + note - we can never really free() a TRN if there's at least one + other running transaction - see, e.g., how lock waits are implemented + in lockman.c +*/ +void trnman_free_trn(TRN *trn) +{ + TRN *tmp= pool; + + my_atomic_rwlock_wrlock(&LOCK_pool); + do + { + /* + without volatile cast gcc-3.4.4 moved the assignment + down after the loop at -O2 + */ + *(TRN * volatile *)&(trn->next)= tmp; + } while (!my_atomic_casptr((void **)&pool, (void **)&tmp, trn)); + my_atomic_rwlock_wrunlock(&LOCK_pool); +} + +/* + NOTE + here we access the hash in a lock-free manner. + It's safe, a 'found' TRN can never be freed/reused before we access it. + In fact, it cannot be freed before 'trn' ends, because a 'found' TRN + can only be removed from the hash when: + found->commit_trid < ALL (trn->min_read_from) + that is, at least + found->commit_trid < trn->min_read_from + but + found->trid >= trn->min_read_from + and + found->commit_trid > found->trid +*/ +my_bool trnman_can_read_from(TRN *trn, TrID trid) +{ + TRN **found; + my_bool can; + LF_REQUIRE_PINS(3); + + if (trid < trn->min_read_from) + return TRUE; + if (trid > trn->trid) + return FALSE; + + found= lf_hash_search(&trid_to_trn, trn->pins, &trid, sizeof(trid)); + if (!found) + return FALSE; /* not in the hash of committed transactions = cannot read*/ + + can= (*found)->commit_trid < trn->trid; + lf_unpin(trn->pins, 2); + return can; +} + diff --git a/storage/maria/trnman.h b/storage/maria/trnman.h new file mode 100644 index 00000000000..9470678f3b2 --- /dev/null +++ b/storage/maria/trnman.h @@ -0,0 +1,48 @@ +/* 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 */ + +#ifndef _trnman_h +#define _trnman_h + +#include "lockman.h" + +typedef uint64 TrID; /* our TrID is 6 bytes */ +typedef struct st_transaction TRN; + +struct st_transaction +{ + LOCK_OWNER locks; + LF_PINS *pins; + TrID trid, min_read_from, commit_trid; + TRN *next, *prev; + /* Note! if locks.loid is 0, trn is NOT initialized */ +}; + +#define SHORT_TRID_MAX 65535 + +extern uint trnman_active_transactions, trnman_allocated_transactions; + +int trnman_init(void); +int trnman_destroy(void); +TRN *trnman_new_trn(pthread_mutex_t *mutex, pthread_cond_t *cond); +void trnman_end_trn(TRN *trn, my_bool commit); +#define trnman_commit_trn(T) trnman_end_trn(T, TRUE) +#define trnman_abort_trn(T) trnman_end_trn(T, FALSE) +void trnman_free_trn(TRN *trn); +my_bool trnman_can_read_from(TRN *trn, TrID trid); + +#endif + diff --git a/storage/maria/unittest/Makefile.am b/storage/maria/unittest/Makefile.am index 8a5ca3d669f..e29bc7f86cb 100644 --- a/storage/maria/unittest/Makefile.am +++ b/storage/maria/unittest/Makefile.am @@ -25,5 +25,5 @@ LDADD= $(top_builddir)/unittest/mytap/libmytap.a \ $(top_builddir)/mysys/libmysys.a \ $(top_builddir)/dbug/libdbug.a \ $(top_builddir)/strings/libmystrings.a @ZLIB_LIBS@ -noinst_PROGRAMS = ma_control_file-t +noinst_PROGRAMS = ma_control_file-t trnman-t lockman-t CLEANFILES = maria_control diff --git a/storage/maria/unittest/lockman-t.c b/storage/maria/unittest/lockman-t.c new file mode 100644 index 00000000000..8b62ccfe094 --- /dev/null +++ b/storage/maria/unittest/lockman-t.c @@ -0,0 +1,246 @@ +/* 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 */ + +//#define EXTRA_VERBOSE + +#include <tap.h> + +#include <my_global.h> +#include <my_sys.h> +#include <my_atomic.h> +#include <lf.h> +#include "../lockman.h" + +#define Nlos 10 +LOCK_OWNER loarray[Nlos]; +pthread_mutex_t mutexes[Nlos]; +pthread_cond_t conds[Nlos]; +LOCKMAN lockman; + +#ifndef EXTRA_VERBOSE +#define print_lockhash(X) /* no-op */ +#define DIAG(X) /* no-op */ +#else +#define DIAG(X) diag X +#endif + +LOCK_OWNER *loid2lo(uint16 loid) +{ + return loarray+loid-1; +} + +#define unlock_all(O) diag("lo" #O "> release all locks"); \ + lockman_release_locks(&lockman, loid2lo(O));print_lockhash(&lockman) +#define test_lock(O, R, L, S, RES) \ + ok(lockman_getlock(&lockman, loid2lo(O), R, L) == RES, \ + "lo" #O "> " S " lock resource " #R " with " #L "-lock"); \ + print_lockhash(&lockman) +#define lock_ok_a(O,R,L) test_lock(O,R,L,"",GOT_THE_LOCK) +#define lock_ok_i(O,R,L) test_lock(O,R,L,"",GOT_THE_LOCK_NEED_TO_LOCK_A_SUBRESOURCE) +#define lock_ok_l(O,R,L) test_lock(O,R,L,"",GOT_THE_LOCK_NEED_TO_INSTANT_LOCK_A_SUBRESOURCE) +#define lock_conflict(O,R,L) test_lock(O,R,L,"cannot ",DIDNT_GET_THE_LOCK); \ + unlock_all(O) + +void test_lockman_simple() +{ + /* simple */ + lock_ok_a(1, 1, S); + lock_ok_i(2, 2, IS); + lock_ok_i(1, 2, IX); + /* lock escalation */ + lock_ok_a(1, 1, X); + lock_ok_i(2, 2, IX); + /* failures */ + lock_conflict(2,1,X); /* this removes all locks of lo2 */ + lock_ok_a(1,2,S); + lock_ok_a(1,2,IS); + lock_ok_a(1,2,LS); + lock_ok_i(1,3,IX); + lock_ok_a(2,3,LS); + lock_ok_i(1,3,IX); + lock_ok_l(2,3,IS); + lockman_release_locks(&lockman, loid2lo(1)); + lockman_release_locks(&lockman, loid2lo(2)); + +} + +pthread_attr_t rt_attr; +pthread_mutex_t rt_mutex; +pthread_cond_t rt_cond; +int rt_num_threads; +int litmus; +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 thread_number= 0, timeouts=0; +#define Nrows 1000 +#define Ntables 10 +#define TABLE_LOCK_RATIO 10 +enum lock_type lock_array[6]={S,X,LS,LX,IS,IX}; +char *lock2str[6]={"S","X","LS","LX","IS","IX"}; +char *res2str[6]={ + "DIDN'T GET THE LOCK", + "GOT THE LOCK", + "GOT THE LOCK NEED TO LOCK A SUBRESOURCE", + "GOT THE LOCK NEED TO INSTANT LOCK A SUBRESOURCE"}; +pthread_handler_t test_lockman(void *arg) +{ + int m= (*(int *)arg); + uint x, loid, row, table, res, locklevel, timeout= 0; + LOCK_OWNER *lo; + + pthread_mutex_lock(&rt_mutex); + loid= ++thread_number; + pthread_mutex_unlock(&rt_mutex); + lo= loid2lo(loid); + + for (x= ((int)(intptr)(&m)); m > 0; m--) + { + x= (x*3628273133 + 1500450271) % 9576890767; /* three prime numbers */ + row= x % Nrows + Ntables; + table= row % Ntables; + locklevel= (x/Nrows) & 3; + if ((x/Nrows/4) % TABLE_LOCK_RATIO == 0) + { /* table lock */ + res= lockman_getlock(&lockman, lo, table, lock_array[locklevel]); + DIAG(("loid=%2d, table %d lock %s, res=%s", loid, table, lock2str[locklevel], res2str[res])); + if (res == DIDNT_GET_THE_LOCK) + { + lockman_release_locks(&lockman, lo); + DIAG(("loid=%2d, release all locks", loid)); + timeout++; + continue; + } + DBUG_ASSERT(res == GOT_THE_LOCK); + } + else + { /* row lock */ + locklevel&= 1; + res= lockman_getlock(&lockman, lo, table, lock_array[locklevel + 4]); + DIAG(("loid=%2d, row %d lock %s, res=%s", loid, row, lock2str[locklevel+4], res2str[res])); + switch (res) + { + case DIDNT_GET_THE_LOCK: + lockman_release_locks(&lockman, lo); + DIAG(("loid=%2d, release all locks", loid)); + timeout++; + continue; + case GOT_THE_LOCK: + continue; + case GOT_THE_LOCK_NEED_TO_INSTANT_LOCK_A_SUBRESOURCE: + /* not implemented, so take a regular lock */ + case GOT_THE_LOCK_NEED_TO_LOCK_A_SUBRESOURCE: + res= lockman_getlock(&lockman, lo, row, lock_array[locklevel]); + DIAG(("loid=%2d, ROW %d lock %s, res=%s", loid, row, lock2str[locklevel], res2str[res])); + if (res == DIDNT_GET_THE_LOCK) + { + lockman_release_locks(&lockman, lo); + DIAG(("loid=%2d, release all locks", loid)); + timeout++; + continue; + } + DBUG_ASSERT(res == GOT_THE_LOCK); + continue; + default: + DBUG_ASSERT(0); + } + } + } + + lockman_release_locks(&lockman, lo); + + pthread_mutex_lock(&rt_mutex); + rt_num_threads--; + timeouts+= timeout; + if (!rt_num_threads) + { + pthread_cond_signal(&rt_cond); + diag("number of timeouts: %d", timeouts); + } + pthread_mutex_unlock(&rt_mutex); + + return 0; +} + +int main() +{ + int i; + + my_init(); + + plan(14); + + if (my_atomic_initialize()) + return exit_status(); + + 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); + + lockman_init(&lockman, &loid2lo, 50); + + for (i= 0; i < Nlos; i++) + { + loarray[i].pins= lf_alloc_get_pins(&lockman.alloc); + loarray[i].all_locks= 0; + loarray[i].waiting_for= 0; + pthread_mutex_init(&mutexes[i], MY_MUTEX_INIT_FAST); + pthread_cond_init (&conds[i], 0); + loarray[i].mutex= &mutexes[i]; + loarray[i].cond= &conds[i]; + loarray[i].loid= i+1; + } + + test_lockman_simple(); + +#define CYCLES 100 +#define THREADS Nlos /* don't change this line */ + + run_test("lockman", test_lockman, THREADS,CYCLES); + + for (i= 0; i < Nlos; i++) + { + lockman_release_locks(&lockman, &loarray[i]); + pthread_mutex_destroy(loarray[i].mutex); + pthread_cond_destroy(loarray[i].cond); + lf_pinbox_put_pins(loarray[i].pins); + } + + lockman_destroy(&lockman); + + pthread_mutex_destroy(&rt_mutex); + pthread_cond_destroy(&rt_cond); + pthread_attr_destroy(&rt_attr); + my_end(0); + return exit_status(); +} + diff --git a/storage/maria/unittest/trnman-t.c b/storage/maria/unittest/trnman-t.c new file mode 100644 index 00000000000..6d4b48c6d3d --- /dev/null +++ b/storage/maria/unittest/trnman-t.c @@ -0,0 +1,177 @@ +/* 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 "../trnman.h" + +pthread_attr_t rt_attr; +pthread_mutex_t rt_mutex; +pthread_cond_t rt_cond; +int rt_num_threads; + +int litmus; + +/* + create and end (commit or rollback) transactions randomly +*/ +#define MAX_ITER 100 +pthread_handler_t test_trnman(void *arg) +{ + int m= (*(int *)arg); + uint x, y, i, j, n; + TRN *trn[MAX_ITER]; + pthread_mutex_t mutexes[MAX_ITER]; + pthread_cond_t conds[MAX_ITER]; + + for (i=0; i < MAX_ITER; i++) + { + pthread_mutex_init(&mutexes[i], MY_MUTEX_INIT_FAST); + pthread_cond_init(&conds[i], 0); + } + + 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++) + trn[i]= trnman_new_trn(&mutexes[i], &conds[i]); + for (i= 0; i < n; i++) + { + y= (y*19 + 7) % 31; + trnman_end_trn(trn[i], y & 1); + } + } + + for (i=0; i < MAX_ITER; i++) + { + pthread_mutex_destroy(&mutexes[i]); + pthread_cond_destroy(&conds[i]); + } + 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); +} + +#define ok_read_from(T1, T2, RES) \ + i=trnman_can_read_from(trn[T1], trid[T2]); \ + ok(i == RES, "trn" #T1 " %s read from trn" #T2, i ? "can" : "cannot") +#define start_transaction(T) \ + trn[T]= trnman_new_trn(&mutexes[T], &conds[T]); \ + trid[T]= trn[T]->trid +#define commit(T) trnman_commit_trn(trn[T]) +#define abort(T) trnman_abort_trn(trn[T]) + +#define Ntrns 4 +void test_trnman_read_from() +{ + TRN *trn[Ntrns]; + TrID trid[Ntrns]; + pthread_mutex_t mutexes[Ntrns]; + pthread_cond_t conds[Ntrns]; + int i; + + for (i=0; i < Ntrns; i++) + { + pthread_mutex_init(&mutexes[i], MY_MUTEX_INIT_FAST); + pthread_cond_init(&conds[i], 0); + } + + start_transaction(0); /* start trn1 */ + start_transaction(1); /* start trn2 */ + ok_read_from(1,0,0); + commit(0); /* commit trn1 */ + start_transaction(2); /* start trn4 */ + abort(2); /* abort trn4 */ + start_transaction(3); /* start trn5 */ + ok_read_from(3,0,1); + ok_read_from(3,1,0); + ok_read_from(3,2,0); + commit(1); /* commit trn2 */ + ok_read_from(3,1,0); + commit(3); /* commit trn5 */ + + for (i=0; i < Ntrns; i++) + { + pthread_mutex_destroy(&mutexes[i]); + pthread_cond_destroy(&conds[i]); + } +} + +int main() +{ + my_init(); + + plan(6); + + if (my_atomic_initialize()) + return exit_status(); + + 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 + + trnman_init(); + + test_trnman_read_from(); + run_test("trnman", test_trnman, THREADS,CYCLES); + + diag("mallocs: %d", trnman_allocated_transactions); + { + ulonglong now= my_getsystime(); + trnman_destroy(); + now= my_getsystime()-now; + diag("trnman_destroy: %g", ((double)now)/1e7); + } + + pthread_mutex_destroy(&rt_mutex); + pthread_cond_destroy(&rt_cond); + pthread_attr_destroy(&rt_attr); + my_end(0); + return exit_status(); +} + diff --git a/storage/myisam/ha_myisam.cc b/storage/myisam/ha_myisam.cc index a42af7da33c..773dea209cc 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 7f1dd525d3b..c42398001c0 100644 --- a/unittest/Makefile.am +++ b/unittest/Makefile.am @@ -1,4 +1,4 @@ -SUBDIRS = mytap . mysys examples +SUBDIRS = mytap mysys examples EXTRA_DIST = unit.pl CLEANFILES = unit diff --git a/unittest/mysys/my_atomic-t.c b/unittest/mysys/my_atomic-t.c index fe93b0942ce..881f80a66f8 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)((long)(&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)((long)(&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; @@ -148,24 +268,25 @@ void test_atomic(const char *test, pthread_handler handler, int n, int m) goto err; } } - pthread_mutex_lock(&mutex); while (N) pthread_cond_wait(&cond, &mutex); pthread_mutex_unlock(&mutex); now=my_getsystime()-now; err: - 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); @@ -173,21 +294,32 @@ 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); - /* - workaround until we know why it crashes randomly on some machine - (BUG#22320). - */ - sleep(2); + 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(); } |