From: Mauritz Sundell Date: February 7 2012 3:44pm Subject: bzr push into mysql-5.1-telco-7.0 branch (mauritz.sundell:4849 to 4853) List-Archive: http://lists.mysql.com/commits/142785 Message-Id: <201202071545.q17Fj4Ii010613@acsmt358.oracle.com> MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit 4853 Mauritz Sundell 2012-02-07 ndb - added truncate to dynarr256 replaces release. truncate releases nodes from high index downwards and can stop at given index. modified: storage/ndb/src/kernel/vm/DynArr256.cpp storage/ndb/src/kernel/vm/DynArr256.hpp 4852 Mauritz Sundell 2012-02-07 ndb - dynarr256 refactoring made inline div15() for shift arithmetic expression for x / 15. dont use it for new code, write x / 15 instead. added get() to get a value ptr in a DA256Page, and use for some DynArr256-methods. modified: storage/ndb/src/kernel/vm/DynArr256.cpp 4851 Mauritz Sundell 2012-02-07 ndb - add unit tests for DynArr256 Tests available in testDynArr256 are now also available in DynArr256-t. Replace micro() based on gettimeofday() with my_micro_time(). modified: storage/ndb/src/kernel/vm/DynArr256.cpp 4850 Mauritz Sundell 2012-02-07 ndb - reversed bit scanning The BitmaskImpl class had functions for finding the least significant bit set in word and array of words (ffs(), find_first(), find_next()). Now functions for finding also the most significant set bit are added. fls() - find most significant bit in Uint32, index 0-31 ctz() - count trailing (least sign.) zeros, equal to ffs() clz() - count leading (most sign.) zeros. That is the number of bits preceding the most significant set bit. That is: fls(x) + clz(x) = 31 if x!=0. All these function are undefined for zero words. find_last() and find_prev() are added to find the most significant set bits in an array of words, corresponding to find_first() and find_next(). find_last()/find_prev() allows one bit outside word array, better would probably be to exclude the given start bit, but that would mean update all current uses of find_last(). modified: storage/ndb/cmake/os/WindowsCache.cmake storage/ndb/include/ndb_config.h.in storage/ndb/include/util/Bitmask.hpp storage/ndb/ndb_configure.cmake storage/ndb/ndb_configure.m4 storage/ndb/src/common/util/Bitmask.cpp 4849 jonas oreland 2012-02-03 ndb - fix upgrade for lqh > 4 modified: storage/ndb/include/ndb_version.h.in storage/ndb/src/kernel/blocks/dbdih/Dbdih.hpp storage/ndb/src/kernel/blocks/dbdih/DbdihMain.cpp === modified file 'storage/ndb/cmake/os/WindowsCache.cmake' --- a/storage/ndb/cmake/os/WindowsCache.cmake 2011-05-24 08:45:38 +0000 +++ b/storage/ndb/cmake/os/WindowsCache.cmake 2012-02-07 15:41:33 +0000 @@ -43,7 +43,10 @@ SET(HAVE_PTHREAD_MUTEXATTR_SETTYPE CACHE SET(HAVE_PTHREAD_SETSCHEDPARAM CACHE INTERNAL "") SET(HAVE_SUN_PREFETCH_H CACHE INTERNAL "") SET(HAVE___BUILTIN_FFS CACHE INTERNAL "") +SET(HAVE___BUILTIN_CTZ CACHE INTERNAL "") +SET(HAVE___BUILTIN_CLZ CACHE INTERNAL "") SET(HAVE__BITSCANFORWARD 1 CACHE INTERNAL "") +SET(HAVE__BITSCANREVERSE 1 CACHE INTERNAL "") SET(HAVE_LINUX_SCHEDULING CACHE INTERNAL "") SET(HAVE_SOLARIS_AFFINITY CACHE INTERNAL "") SET(HAVE_LINUX_FUTEX CACHE INTERNAL "") === modified file 'storage/ndb/include/ndb_config.h.in' --- a/storage/ndb/include/ndb_config.h.in 2011-03-15 15:50:34 +0000 +++ b/storage/ndb/include/ndb_config.h.in 2012-02-07 15:41:33 +0000 @@ -38,7 +38,10 @@ #cmakedefine HAVE_MLOCK 1 #cmakedefine HAVE_FFS 1 #cmakedefine HAVE___BUILTIN_FFS 1 +#cmakedefine HAVE___BUILTIN_CTZ 1 +#cmakedefine HAVE___BUILTIN_CLZ 1 #cmakedefine HAVE__BITSCANFORWARD 1 +#cmakedefine HAVE__BITSCANREVERSE 1 #cmakedefine HAVE_PTHREAD_MUTEXATTR_INIT 1 #cmakedefine HAVE_PTHREAD_MUTEXATTR_SETTYPE 1 #cmakedefine HAVE_PTHREAD_SETSCHEDPARAM 1 === modified file 'storage/ndb/include/util/Bitmask.hpp' --- a/storage/ndb/include/util/Bitmask.hpp 2011-02-01 23:27:25 +0000 +++ b/storage/ndb/include/util/Bitmask.hpp 2012-02-07 15:41:33 +0000 @@ -20,7 +20,7 @@ #include -#ifdef HAVE__BITSCANFORWARD +#if defined(HAVE__BITSCANFORWARD) || defined(HAVE__BITSCANREVERSE) #include #endif @@ -93,24 +93,54 @@ public: static unsigned count(unsigned size, const Uint32 data[]); /** + * return count trailing zero bits inside a word + * undefined behaviour if non set + */ + static unsigned ctz(Uint32 x); + + /** + * return count leading zero bits inside a word + * undefined behaviour if non set + */ + static unsigned clz(Uint32 x); + + /** * return index of first bit set inside a word * undefined behaviour if non set */ static unsigned ffs(Uint32 x); /** + * return index of last bit set inside a word + * undefined behaviour if non set + */ + static unsigned fls(Uint32 x); + + /** * find - Find first set bit, starting from 0 * Returns NotFound when not found. */ static unsigned find_first(unsigned size, const Uint32 data[]); /** + * find - Find last set bit, starting from 0 + * Returns NotFound when not found. + */ + static unsigned find_last(unsigned size, const Uint32 data[]); + + /** * find - Find first set bit, starting at given position. * Returns NotFound when not found. */ static unsigned find_next(unsigned size, const Uint32 data[], unsigned n); /** + * find - Find last set bit, starting at given position. + * Returns NotFound when not found. + */ + static unsigned find_prev(unsigned size, const Uint32 data[], unsigned n); + + /** * find - Find first set bit, starting at given position. * Returns NotFound when not found. */ @@ -358,6 +388,68 @@ BitmaskImpl::count(unsigned size, const } /** + * return count trailing zero bits inside a word + * undefined behaviour if non set + */ +inline +Uint32 +BitmaskImpl::ctz(Uint32 x) +{ + return ffs(x); +} + +/** + * return count leading bits inside a word + * undefined behaviour if non set + */ +inline +Uint32 +BitmaskImpl::clz(Uint32 x) +{ +#if defined HAVE___BUILTIN_CLZ + return __builtin_clz(x); +#elif defined(__GNUC__) && (defined(__x86_64__) || defined (__i386__)) + asm("bsr %1,%0" + : "=r" (x) + : "rm" (x)); + return 31 - x; +#elif defined HAVE__BITSCANREVERSE + unsigned long r; + unsigned char res = _BitScanReverse(&r, (unsigned long)x); + assert(res > 0); + return 31 - (Uint32)r; +#else + int b = 0; + if (!(x & 0xffff0000)) + { + x <<= 16; + b += 16; + } + if (!(x & 0xff000000)) + { + x <<= 8; + b += 8; + } + if (!(x & 0xf0000000)) + { + x <<= 4; + b += 4; + } + if (!(x & 0xc0000000)) + { + x <<= 2; + b += 2; + } + if (!(x & 0x80000000)) + { + x <<= 1; + b += 1; + } + return b; +#endif +} + +/** * return index of first bit set inside a word * undefined behaviour if non set */ @@ -365,7 +457,9 @@ inline Uint32 BitmaskImpl::ffs(Uint32 x) { -#if defined(__GNUC__) && (defined(__x86_64__) || defined (__i386__)) +#if defined HAVE___BUILTIN_CTZ + return __builtin_ctz(x); +#elif defined(__GNUC__) && (defined(__x86_64__) || defined (__i386__)) asm("bsf %1,%0" : "=r" (x) : "rm" (x)); @@ -413,6 +507,57 @@ BitmaskImpl::ffs(Uint32 x) #endif } +/** + * return index of last bit set inside a word + * undefined behaviour if non set + */ +inline +Uint32 +BitmaskImpl::fls(Uint32 x) +{ +#if defined(__GNUC__) && (defined(__x86_64__) || defined (__i386__)) + asm("bsr %1,%0" + : "=r" (x) + : "rm" (x)); + return x; +#elif defined HAVE___BUILTIN_CLZ + return 31 - __builtin_clz(x); +#elif defined HAVE__BITSCANREVERSE + unsigned long r; + unsigned char res = _BitScanReverse(&r, (unsigned long)x); + assert(res > 0); + return (Uint32)r; +#else + int b = 31; + if (!(x & 0xffff0000)) + { + x <<= 16; + b -= 16; + } + if (!(x & 0xff000000)) + { + x <<= 8; + b -= 8; + } + if (!(x & 0xf0000000)) + { + x <<= 4; + b -= 4; + } + if (!(x & 0xc0000000)) + { + x <<= 2; + b -= 2; + } + if (!(x & 0x80000000)) + { + x <<= 1; + b -= 1; + } + return b; +#endif +} + inline unsigned BitmaskImpl::find_first(unsigned size, const Uint32 data[]) { @@ -430,8 +575,29 @@ BitmaskImpl::find_first(unsigned size, c } inline unsigned +BitmaskImpl::find_last(unsigned size, const Uint32 data[]) +{ + if (size == 0) + return NotFound; + Uint32 n = (size << 5) - 1; + do + { + Uint32 val = data[n >> 5]; + if (val) + { + return n - clz(val); + } + n -= 32; + } while (n != 0xffffffff); + return NotFound; +} + +inline unsigned BitmaskImpl::find_next(unsigned size, const Uint32 data[], unsigned n) { + assert(n <= (size << 5)); + if (n == (size << 5)) // allow one step utside for easier use + return NotFound; Uint32 val = data[n >> 5]; Uint32 b = n & 31; if (b) @@ -457,6 +623,35 @@ BitmaskImpl::find_next(unsigned size, co } inline unsigned +BitmaskImpl::find_prev(unsigned size, const Uint32 data[], unsigned n) +{ + if (n >= (Uint32) 0xffffffff /* -1 */) // allow one bit outside array for easier use + return NotFound; + assert(n < (size << 5)); + Uint32 val = data[n >> 5]; + Uint32 b = n & 31; + if (b < 31) + { + val <<= 31 - b; + if (val) + { + return n - clz(val); + } + n -= b + 1; + } + + while (n != NotFound) { + val = data[n >> 5]; + if (val) + { + return n - clz(val); + } + n -= 32; + } + return NotFound; +} + +inline unsigned BitmaskImpl::find(unsigned size, const Uint32 data[], unsigned n) { return find_next(size, data, n); @@ -742,6 +937,20 @@ public: unsigned find_next(unsigned n) const; /** + * find - Find last set bit, starting at 0 + * Returns NotFound when not found. + */ + static unsigned find_last(const Uint32 data[]); + unsigned find_last() const; + + /** + * find - Find previous set bit, starting at n + * Returns NotFound when not found. + */ + static unsigned find_prev(const Uint32 data[], unsigned n); + unsigned find_prev(unsigned n) const; + + /** * find - Find first set bit, starting at given position. * Returns NotFound when not found. */ @@ -1024,6 +1233,34 @@ BitmaskPOD::find_next(unsigned n) } template +inline unsigned +BitmaskPOD::find_last(const Uint32 data[]) +{ + return BitmaskImpl::find_last(size, data); +} + +template +inline unsigned +BitmaskPOD::find_last() const +{ + return BitmaskPOD::find_last(rep.data); +} + +template +inline unsigned +BitmaskPOD::find_prev(const Uint32 data[], unsigned n) +{ + return BitmaskImpl::find_prev(size, data, n); +} + +template +inline unsigned +BitmaskPOD::find_prev(unsigned n) const +{ + return BitmaskPOD::find_prev(rep.data, n); +} + +template inline unsigned BitmaskPOD::find(const Uint32 data[], unsigned n) { === modified file 'storage/ndb/ndb_configure.cmake' --- a/storage/ndb/ndb_configure.cmake 2011-05-24 08:45:38 +0000 +++ b/storage/ndb/ndb_configure.cmake 2012-02-07 15:41:33 +0000 @@ -76,6 +76,24 @@ int main() }" HAVE___BUILTIN_FFS) +CHECK_CXX_SOURCE_COMPILES(" +unsigned A = 7; +int main() +{ + unsigned a = __builtin_ctz(A); + return 0; +}" +HAVE___BUILTIN_CTZ) + +CHECK_CXX_SOURCE_COMPILES(" +unsigned A = 7; +int main() +{ + unsigned a = __builtin_clz(A); + return 0; +}" +HAVE___BUILTIN_CLZ) + CHECK_C_SOURCE_COMPILES(" #include unsigned long A = 7; @@ -87,6 +105,17 @@ int main() }" HAVE__BITSCANFORWARD) +CHECK_C_SOURCE_COMPILES(" +#include +unsigned long A = 7; +int main() +{ + unsigned long a; + unsigned char res = _BitScanReverse(&a, A); + return (int)a; +}" +HAVE__BITSCANREVERSE) + # Linux scheduling and locking support CHECK_C_SOURCE_COMPILES(" #ifndef _GNU_SOURCE === modified file 'storage/ndb/ndb_configure.m4' --- a/storage/ndb/ndb_configure.m4 2012-01-16 06:43:47 +0000 +++ b/storage/ndb/ndb_configure.m4 2012-02-07 15:41:33 +0000 @@ -186,6 +186,22 @@ AC_DEFUN([NDB_COMPILER_FEATURES], AC_MSG_RESULT([no]) ) + AC_MSG_CHECKING([checking __builtin_ctz(unsigned)]) + AC_TRY_COMPILE([unsigned A = 7;],[ unsigned a = __builtin_ctz(A)], + [ AC_MSG_RESULT([yes]) + AC_DEFINE([HAVE___BUILTIN_CTZ], [1], + [Compiler supports __builtin_ctz])], + AC_MSG_RESULT([no]) + ) + + AC_MSG_CHECKING([checking __builtin_clz(unsigned)]) + AC_TRY_COMPILE([unsigned A = 7;],[ unsigned a = __builtin_clz(A)], + [ AC_MSG_RESULT([yes]) + AC_DEFINE([HAVE___BUILTIN_CLZ], [1], + [Compiler supports __builtin_clz])], + AC_MSG_RESULT([no]) + ) + AC_LANG_POP([C++]) ]) === modified file 'storage/ndb/src/common/util/Bitmask.cpp' --- a/storage/ndb/src/common/util/Bitmask.cpp 2011-02-01 23:27:25 +0000 +++ b/storage/ndb/src/common/util/Bitmask.cpp 2012-02-07 15:41:33 +0000 @@ -368,6 +368,28 @@ test_find_fast(Result& res, const Bitmas template inline void +test_find_fast_reversed(Result& res, const Bitmask & mask, unsigned iter, FUNC func) +{ + Uint32 sum = 0; + Uint64 start = NdbTick_CurrentMillisecond(); + for (Uint32 j = 0; j +inline +void test_toArray(Result& res, const Bitmask & mask, unsigned iter, FUNC func) { Uint32 sum = 0; @@ -412,7 +434,7 @@ do_test(Uint32 len, FUNC func, const cha if (func == slow) iter = 3000; - Result res_find, res_fast, res_toArray, res_empty; + Result res_find, res_fast, res_fast_reversed, res_toArray, res_empty; for (Uint32 i = 0; i < (10000 / len); i++) { Bitmask<8> tmp; @@ -437,6 +459,7 @@ do_test(Uint32 len, FUNC func, const cha } test_find(res_find, tmp, iter, func); test_find_fast(res_fast, tmp, iter, func); + test_find_fast_reversed(res_fast_reversed, tmp, iter, func); test_toArray(res_toArray, tmp, iter, func); test_empty(res_empty, len, iter, func); } @@ -444,7 +467,8 @@ do_test(Uint32 len, FUNC func, const cha res_find.elapsed = sub0(res_find.elapsed, res_empty.elapsed); res_toArray.elapsed = sub0(res_toArray.elapsed, res_empty.elapsed); res_fast.elapsed = sub0(res_fast.elapsed, res_empty.elapsed); - Uint64 m = x_min(res_find.elapsed, res_toArray.elapsed, res_fast.elapsed); + res_fast_reversed.elapsed = sub0(res_fast_reversed.elapsed, res_empty.elapsed); + Uint64 m = x_min(res_find.elapsed, res_toArray.elapsed, res_fast_reversed.elapsed); if (m == 0) m = 1; @@ -466,6 +490,16 @@ do_test(Uint32 len, FUNC func, const cha printf("toArray(%s,%s, %u) : %llu ns/iter (%.3u%%), (sum: %u)\n", dist, name, len, (1000000 * res_toArray.elapsed / div), + Uint32((100 * res_toArray.elapsed) / m), + res_toArray.sum); + printf("reversed(%s,%s, %u) : %llu ns/iter (%.3u%%), (sum: %u)\n", + dist, name, len, + (1000000 * res_fast_reversed.elapsed / div), + Uint32((100 * res_fast_reversed.elapsed) / m), + res_fast_reversed.sum); + printf("toArray(%s,%s, %u) : %llu ns/iter (%.3u%%), (sum: %u)\n", + dist, name, len, + (1000000 * res_toArray.elapsed / div), Uint32((100 * res_toArray.elapsed) / m), res_toArray.sum); printf("\n"); === modified file 'storage/ndb/src/kernel/vm/DynArr256.cpp' --- a/storage/ndb/src/kernel/vm/DynArr256.cpp 2011-12-23 08:28:23 +0000 +++ b/storage/ndb/src/kernel/vm/DynArr256.cpp 2012-02-07 15:43:54 +0000 @@ -44,6 +44,8 @@ struct DA256Page { struct DA256CL m_header[2]; struct DA256Node m_nodes[30]; + + bool get(Uint32 node, Uint32 idx, Uint32 type_id, Uint32*& val_ptr) const; }; #undef require @@ -52,18 +54,31 @@ struct DA256Page //#define DA256_USE_PREFETCH #define DA256_EXTRA_SAFE +#ifdef TAP_TEST +#define UNIT_TEST +#include "NdbTap.hpp" +#endif #ifdef UNIT_TEST +#include "my_sys.h" #ifdef USE_CALLGRIND #include #else #define CALLGRIND_TOGGLE_COLLECT() #endif +Uint32 verbose = 0; Uint32 allocatedpages = 0; Uint32 allocatednodes = 0; Uint32 releasednodes = 0; #endif +static +inline +Uint32 div15(Uint32 x) +{ + return ((x << 8) + (x << 4) + x + 255) >> 12; +} + inline void require_impl(bool x, int line) @@ -97,6 +112,35 @@ DynArr256Pool::init(NdbMutex* m, Uint32 m_mutex = m; } +inline +bool +DA256Page::get(Uint32 node, Uint32 idx, Uint32 type_id, Uint32*& val_ptr) const +{ + Uint32 *magic_ptr, p; + if (idx != 255) + { + Uint32 line = div15(idx); + Uint32* ptr = (Uint32*)(m_nodes + node); + + p = 0; + val_ptr = (ptr + 1 + idx + line); + magic_ptr =(ptr + (idx & ~15)); + } + else + { + Uint32 b = (node + 1) >> 4; + Uint32 * ptr = (Uint32*)(m_header+b); + + p = node - (b << 4) + b; + val_ptr = (ptr + 1 + p); + magic_ptr = ptr; + } + + Uint32 magic = *magic_ptr; + + return ((magic & (1 << p)) && (magic >> 16) == type_id); +} + static const Uint32 g_max_sizes[5] = { 0, 256, 65536, 16777216, ~0 }; /** @@ -142,34 +186,13 @@ DynArr256::get(Uint32 pos) const Uint32 page_no = ptrI >> DA256_BITS; Uint32 page_idx = ptrI & DA256_MASK; DA256Page * page = memroot + page_no; - - Uint32 *magic_ptr, p; - if (p0 != 255) - { - Uint32 line = ((p0 << 8) + (p0 << 4) + p0 + 255) >> 12; - Uint32 * ptr = (Uint32*)(page->m_nodes + page_idx); - - p = 0; - retVal = (ptr + 1 + p0 + line); - magic_ptr =(ptr + (p0 & ~15)); - } - else - { - Uint32 b = (page_idx + 1) >> 4; - Uint32 * ptr = (Uint32*)(page->m_header+b); - - p = page_idx - (b << 4) + b; - retVal = (ptr + 1 + p); - magic_ptr = ptr; - } - - ptrI = *retVal; - Uint32 magic = *magic_ptr; - - if (unlikely(! ((magic & (1 << p)) && (magic >> 16) == type_id))) + + if (unlikely(! page->get(page_idx, p0, type_id, retVal))) goto err; + + ptrI = *retVal; } - + return retVal; err: require(false); @@ -222,31 +245,10 @@ DynArr256::set(Uint32 pos) Uint32 page_idx = ptrI & DA256_MASK; DA256Page * page = memroot + page_no; - Uint32 *magic_ptr, p; - if (p0 != 255) - { - Uint32 line = ((p0 << 8) + (p0 << 4) + p0 + 255) >> 12; - Uint32 * ptr = (Uint32*)(page->m_nodes + page_idx); + if (unlikely(! page->get(page_idx, p0, type_id, retVal))) + goto err; - p = 0; - magic_ptr = (ptr + (p0 & ~15)); - retVal = (ptr + 1 + p0 + line); - } - else - { - Uint32 b = (page_idx + 1) >> 4; - Uint32 * ptr = (Uint32*)(page->m_header+b); - - p = page_idx - (b << 4) + b; - magic_ptr = ptr; - retVal = (ptr + 1 + p); - } - ptrI = * retVal; - Uint32 magic = *magic_ptr; - - if (unlikely(! ((magic & (1 << p)) && (magic >> 16) == type_id))) - goto err; } return retVal; @@ -355,8 +357,7 @@ void DynArr256::init(ReleaseIterator &iter) { iter.m_sz = 1; - iter.m_pos = 0; - iter.m_ptr_i[0] = RNIL; + iter.m_pos = ~(~0U << (8 * m_head.m_sz)); iter.m_ptr_i[1] = m_head.m_ptr_i; iter.m_ptr_i[2] = RNIL; iter.m_ptr_i[3] = RNIL; @@ -371,92 +372,83 @@ DynArr256::init(ReleaseIterator &iter) * 2 - no data */ Uint32 -DynArr256::release(ReleaseIterator &iter, Uint32 * retptr) +DynArr256::truncate(Uint32 keep_pos, ReleaseIterator& iter, Uint32* ptrVal) { - Uint32 sz = iter.m_sz; - Uint32 ptrI = iter.m_ptr_i[sz]; - Uint32 page_no = ptrI >> DA256_BITS; - Uint32 page_idx = ptrI & DA256_MASK; Uint32 type_id = (~m_pool.m_type_id) & 0xFFFF; DA256Page * memroot = m_pool.m_memroot; - DA256Page * page = memroot + page_no; - if (ptrI != RNIL) + for (;;) { - Uint32 p0 = iter.m_pos & 255; - for (; p0<256; p0++) + if (iter.m_sz == 0 || + iter.m_pos < keep_pos || + m_head.m_sz == 0) { - Uint32 *retVal, *magic_ptr, p; - if (p0 != 255) + return 0; + } + + Uint32* refPtr; + Uint32 ptrI = iter.m_ptr_i[iter.m_sz]; + Uint32 page_no = ptrI >> DA256_BITS; + Uint32 page_idx = (ptrI & DA256_MASK) ; + DA256Page* page = memroot + page_no; + Uint32 node_index = (iter.m_pos >> (8 * (m_head.m_sz - iter.m_sz))) & 255; + bool is_value = (iter.m_sz == m_head.m_sz); + + if (unlikely(! page->get(page_idx, node_index, type_id, refPtr))) + { + require(false); + } + assert(refPtr != NULL); + *ptrVal = *refPtr; + + if (iter.m_sz == 1 && + (iter.m_pos >> (8 * (m_head.m_sz - iter.m_sz))) == 0) + { + assert(iter.m_ptr_i[iter.m_sz] == m_head.m_ptr_i); + assert(iter.m_ptr_i[iter.m_sz + 1] == RNIL); + iter.m_ptr_i[iter.m_sz] = is_value ? RNIL : *refPtr; + m_pool.release(m_head.m_ptr_i); + m_head.m_sz --; + m_head.m_ptr_i = iter.m_ptr_i[iter.m_sz]; + return is_value ? 1 : 2; + } + + if (is_value || iter.m_ptr_i[iter.m_sz + 1] == *refPtr) + { // sz-- + Uint32 ptrI = *refPtr; + if (!is_value) { - Uint32 line = ((p0 << 8) + (p0 << 4) + p0 + 255) >> 12; - Uint32 * ptr = (Uint32*)(page->m_nodes + page_idx); - - p = 0; - retVal = (ptr + 1 + p0 + line); - magic_ptr =(ptr + (p0 & ~15)); + if (ptrI != RNIL) + { + m_pool.release(ptrI); + *refPtr = iter.m_ptr_i[iter.m_sz+1] = RNIL; + } } - else + if (node_index == 0) { - Uint32 b = (page_idx + 1) >> 4; - Uint32 * ptr = (Uint32*)(page->m_header+b); - - p = page_idx - (b << 4) + b; - retVal = (ptr + 1 + p); - magic_ptr = ptr; + iter.m_sz --; } - - Uint32 magic = *magic_ptr; - Uint32 val = *retVal; - if (unlikely(! ((magic & (1 << p)) && (magic >> 16) == type_id))) - goto err; - - if (sz == m_head.m_sz) + else if (!is_value && ptrI == RNIL) { - * retptr = val; - p0++; - if (p0 != 256) - { - /** - * Move next - */ - iter.m_pos &= ~(Uint32)255; - iter.m_pos |= p0; - } - else - { - /** - * Move up - */ - m_pool.release(ptrI); - iter.m_sz --; - iter.m_pos >>= 8; - } - return 1; + assert((~iter.m_pos & ~(0xffffffff << (8 * (m_head.m_sz - iter.m_sz)))) == 0); + iter.m_pos -= 1U << (8 * (m_head.m_sz - iter.m_sz)); } - else if (val != RNIL) + else { - iter.m_sz++; - iter.m_ptr_i[iter.m_sz] = val; - iter.m_pos = (p0 << 8); - * retVal = RNIL; - return 2; + assert((iter.m_pos & ~(0xffffffff << (8 * (m_head.m_sz - iter.m_sz)))) == 0); + iter.m_pos --; } + if (is_value) + return 1; + } + else + { // sz++ + assert(iter.m_ptr_i[iter.m_sz + 1] == RNIL); + iter.m_sz ++; + iter.m_ptr_i[iter.m_sz] = *refPtr; + return 2; } - - assert(p0 == 256); - m_pool.release(ptrI); - iter.m_sz --; - iter.m_pos >>= 8; - return 2; } - - new (&m_head) Head(); - return 0; - -err: - require(false); - return false; } static @@ -638,10 +630,10 @@ DynArr256Pool::release(Uint32 ptrI) #ifdef UNIT_TEST static -void +bool simple(DynArr256 & arr, int argc, char* argv[]) { - ndbout_c("argc: %d", argc); + if (verbose) ndbout_c("argc: %d", argc); for (Uint32 i = 1; i<(Uint32)argc; i++) { Uint32 * s = arr.set(atoi(argv[i])); @@ -661,12 +653,13 @@ simple(DynArr256 & arr, int argc, char* Uint32 * g = arr.get(atoi(argv[i])); Uint32 v = g ? *g : ~0; - ndbout_c("p: %p %p %d", s, g, v); + if (verbose) ndbout_c("p: %p %p %d", s, g, v); } + return true; } static -void +bool basic(DynArr256& arr, int argc, char* argv[]) { #define MAXLEN 65536 @@ -723,29 +716,19 @@ basic(DynArr256& arr, int argc, char* ar } } } -} - -unsigned long long -micro() -{ - struct timeval tv; - gettimeofday(&tv, 0); - unsigned long long ret = tv.tv_sec; - ret *= 1000000; - ret += tv.tv_usec; - return ret; + return true; } static -void +bool read(DynArr256& arr, int argc, char ** argv) { Uint32 cnt = 100000; Uint64 mbytes = 16*1024; - Uint32 seed = time(0); + Uint32 seed = (Uint32) time(0); Uint32 seq = 0, seqmask = 0; - for (Uint32 i = 1; i %d entries (%dkb)", + if (verbose) + ndbout_c("%lldmb data -> %d entries (%dkb)", mbytes, maxidx, 32*pages); for (Uint32 i = 0; i %f us/get", start, sum0 - sum1, uspg); + start = my_micro_time() - start; + float uspg = (float)start; uspg /= cnt; + if (verbose) + ndbout_c("Elapsed %lldus diff: %d -> %f us/get", start, sum0 - sum1, uspg); } + return true; } static -void +bool write(DynArr256& arr, int argc, char ** argv) { Uint32 seq = 0, seqmask = 0; Uint32 cnt = 100000; Uint64 mbytes = 16*1024; - Uint32 seed = time(0); + Uint32 seed = (Uint32) time(0); - for (Uint32 i = 1; i %d entries (%dkb)", + if (verbose) + ndbout_c("%lldmb data -> %d entries (%dkb)", mbytes, maxidx, 32*pages); srand(seed); @@ -853,25 +853,28 @@ write(DynArr256& arr, int argc, char ** seqmask = ~(Uint32)0; } - ndbout_c("Timing %d %s writes (seed: %u)", cnt, + if (verbose) + ndbout_c("Timing %d %s writes (seed: %u)", cnt, seq ? "sequential" : "random", seed); for (Uint32 i = 0; i<10; i++) { - Uint64 start = micro(); + Uint64 start = my_micro_time(); for (Uint32 i = 0; i %f us/set", start, uspg); + start = my_micro_time() - start; + float uspg = (float)start; uspg /= cnt; + if (verbose) + ndbout_c("Elapsed %lldus -> %f us/set", start, uspg); DynArr256::ReleaseIterator iter; arr.init(iter); Uint32 val; while(arr.release(iter, &val)); } + return true; } static @@ -889,13 +892,37 @@ usage(FILE *f, int argc, char **argv) # include "test_context.hpp" +#ifdef TAP_TEST +static +char* flatten(int argc, char** argv) /* NOT MT-SAFE */ +{ + static char buf[10000]; + size_t off = 0; + for (; argc > 0; argc--, argv++) + { + int i = 0; + if (off > 0 && (off + 1 < sizeof(buf))) + buf[off++] = ' '; + for (i = 0; (off + 1 < sizeof(buf)) && argv[0][i] != 0; i++, off++) + buf[off] = argv[0][i]; + buf[off] = 0; + } + return buf; +} +#endif + int main(int argc, char** argv) { +#ifndef TAP_TEST + verbose = 1; if (argc == 1) { usage(stderr, argc, argv); exit(2); } +#else + verbose = 0; +#endif Pool_context pc = test_context(10000 /* pages */); @@ -905,6 +932,42 @@ main(int argc, char** argv) DynArr256::Head head; DynArr256 arr(pool, head); +#ifdef TAP_TEST + if (argc == 1) + { + char *argv[2] = { (char*)"dummy", NULL }; + plan(5); + ok(simple(arr, 1, argv), "simple"); + ok(basic(arr, 1, argv), "basic"); + ok(read(arr, 1, argv), "read"); + ok(write(arr, 1, argv), "write"); + } + else if (strcmp(argv[1], "--simple") == 0) + { + plan(2); + ok(simple(arr, argc - 1, argv + 1), "simple %s", flatten(argc - 1, argv + 1)); + } + else if (strcmp(argv[1], "--basic") == 0) + { + plan(2); + ok(basic(arr, argc - 1, argv + 1), "basic %s", flatten(argc - 1, argv + 1)); + } + else if (strcmp(argv[1], "--read") == 0) + { + plan(2); + ok(read(arr, argc - 1, argv + 1), "read %s", flatten(argc - 1, argv + 1)); + } + else if (strcmp(argv[1], "--write") == 0) + { + plan(2); + ok(write(arr, argc - 1, argv + 1), "write %s", flatten(argc - 1, argv + 1)); + } + else + { + usage(stderr, argc, argv); + BAIL_OUT("Bad usage: %s %s", argv[0], flatten(argc - 1, argv + 1)); + } +#else if (strcmp(argv[1], "--simple") == 0) simple(arr, argc - 1, argv + 1); else if (strcmp(argv[1], "--basic") == 0) @@ -918,34 +981,26 @@ main(int argc, char** argv) usage(stderr, argc, argv); exit(2); } +#endif DynArr256::ReleaseIterator iter; arr.init(iter); Uint32 cnt = 0, val; while (arr.release(iter, &val)) cnt++; - ndbout_c("allocatedpages: %d allocatednodes: %d releasednodes: %d" + if (verbose) + ndbout_c("allocatedpages: %d allocatednodes: %d releasednodes: %d" " releasecnt: %d", allocatedpages, allocatednodes, releasednodes, cnt); - +#ifdef TAP_TEST + ok(allocatednodes == releasednodes, "release"); + return exit_status(); +#else return 0; -} - #endif - -#ifdef TAP_TEST -#include -#include "test_context.hpp" - -TAPTEST(DynArr256) -{ - Pool_context pc = test_context(10000); - - OK(true); - - return 1; } + #endif === modified file 'storage/ndb/src/kernel/vm/DynArr256.hpp' --- a/storage/ndb/src/kernel/vm/DynArr256.hpp 2011-06-30 15:55:35 +0000 +++ b/storage/ndb/src/kernel/vm/DynArr256.hpp 2012-02-07 15:43:54 +0000 @@ -79,6 +79,7 @@ public: * 2 - nodata */ Uint32 release(ReleaseIterator&, Uint32* retptr); + Uint32 truncate(Uint32 keep_pos, ReleaseIterator&, Uint32* retptr); protected: Head & m_head; DynArr256Pool & m_pool; @@ -87,4 +88,10 @@ protected: void handle_invalid_ptr(Uint32 pos, Uint32 ptrI, Uint32 p0); }; +inline +Uint32 DynArr256::release(ReleaseIterator& iter, Uint32* retptr) +{ + return truncate(0, iter, retptr); +} + #endif No bundle (reason: useless for push emails).