List:Commits« Previous MessageNext Message »
From:Marc Alff Date:April 13 2010 10:05am
Subject:bzr commit into mysql-6.0-codebase-bugfixing branch (marc.alff:3857)
View as plain text  
#At file:///Users/malff/BZR_TREE/mysql-6.0-codebase-bugfixing/ based on revid:alik@stripped

 3857 Marc Alff	2010-04-13 [merge]
      Manual merge, mysql-next-mr-bugfixing --> mysql-6.0-codebase-bugfixing

    modified:
      storage/perfschema/pfs_global.h
      storage/perfschema/pfs_instr.cc
      storage/perfschema/pfs_instr.h
=== modified file 'storage/perfschema/pfs_global.h'
--- a/storage/perfschema/pfs_global.h	2010-01-12 01:48:52 +0000
+++ b/storage/perfschema/pfs_global.h	2010-04-13 10:05:22 +0000
@@ -1,4 +1,4 @@
-/* Copyright (C) 2008-2009 Sun Microsystems, Inc
+/* Copyright (c) 2008, 2010, Oracle and/or its affiliates. All rights reserved.
 
   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
@@ -30,27 +30,49 @@ void pfs_free(void *ptr);
 
 inline uint randomized_index(const void *ptr, uint max_size)
 {
+  static uint seed1= 0;
+  static uint seed2= 0;
+  uint result;
+  register intptr value;
+
   if (unlikely(max_size == 0))
     return 0;
 
   /*
-    ptr is typically an aligned structure,
-    so the last bits are not really random, but this has no effect.
-    Apply a factor A*x to spread
-    close values of ptr further apart (which helps with arrays),
-    and to spread values way beyond a typical max_size.
-    Then, apply a modulo to end within [0, max_size - 1].
-    A is big prime numbers, to avoid resonating with max_size,
-    to have a uniform distribution in [0, max_size - 1].
-    The value of A is chosen so that index(ptr) and index(ptr + N) (for arrays)
-    are likely to be not similar for typical values of max_size
-    (50, 100, 1000, etc).
-    In other words, (sizeof(T)*A % max_size) should not be a small number,
-    to avoid that with 'T array[max_size]', index(array[i])
-    and index(array[i + 1]) end up pointing in the same area in [0, max_size - 1].
+    ptr is typically an aligned structure, and can be in an array.
+    - The last bits are not random because of alignment,
+      so we divide by 8.
+    - The high bits are mostly constant, especially with 64 bits architectures,
+      but we keep most of them anyway, by doing computation in intptr.
+      The high bits are significant depending on where the data is
+      stored (the data segment, the stack, the heap, ...).
+    - To spread consecutive cells in an array further, we multiply by
+      a factor A. This factor should not be too high, which would cause
+      an overflow and cause loss of randomness (droping the top high bits).
+      The factor is a prime number, to help spread the distribution.
+    - To add more noise, and to be more robust if the calling code is
+      passing a constant value instead of a random identity,
+      we add the previous results, for hysteresys, with a degree 2 polynom,
+      X^2 + X + 1.
+    - Last, a modulo is applied to be within the [0, max_size - 1] range.
+    Note that seed1 and seed2 are static, and are *not* thread safe,
+    which is even better.
+    Effect with arrays: T array[N]
+    - ptr(i) = & array[i] = & array[0] + i * sizeof(T)
+    - ptr(i+1) = ptr(i) + sizeof(T).
+    What we want here, is to have index(i) and index(i+1) fall into
+    very different areas in [0, max_size - 1], to avoid locality.
   */
-  return static_cast<uint>
-    (((reinterpret_cast<intptr> (ptr)) * 2166179) % max_size);
+  value= (reinterpret_cast<intptr> (ptr)) >> 3;
+  value*= 1789;
+  value+= seed2 + seed1 + 1;
+  value%= max_size;
+  
+  result= static_cast<uint> (value);
+  seed2= seed1*seed1;
+  seed1= result;
+
+  return result;
 }
 
 void pfs_print_error(const char *format, ...);

=== modified file 'storage/perfschema/pfs_instr.cc'
--- a/storage/perfschema/pfs_instr.cc	2010-04-08 10:50:40 +0000
+++ b/storage/perfschema/pfs_instr.cc	2010-04-13 10:05:22 +0000
@@ -18,13 +18,15 @@
   Performance schema instruments (implementation).
 */
 
+#include <string.h>
+
 #include "my_global.h"
-#include "m_string.h"
 #include "sql_priv.h"
 #include "my_sys.h"
 #include "pfs_stat.h"
 #include "pfs_instr.h"
 #include "pfs_global.h"
+#include "m_string.h"                           // strmov
 
 /**
   @addtogroup Performance_schema_buffers
@@ -446,6 +448,75 @@ void cleanup_file_hash(void)
   }
 }
 
+void PFS_scan::init(uint random, uint max_size)
+{
+  m_pass= 0;
+
+  if (max_size == 0)
+  {
+    /* Degenerated case, no buffer */
+    m_pass_max= 0;
+    return;
+  }
+
+  DBUG_ASSERT(random < max_size);
+
+  if (PFS_MAX_ALLOC_RETRY < max_size)
+  {
+    /*
+      The buffer is big compared to PFS_MAX_ALLOC_RETRY,
+      scan it only partially.
+    */
+    if (random + PFS_MAX_ALLOC_RETRY < max_size)
+    {
+      /*
+        Pass 1: [random, random + PFS_MAX_ALLOC_RETRY - 1]
+        Pass 2: not used.
+      */
+      m_pass_max= 1;
+      m_first[0]= random;
+      m_last[0]= random + PFS_MAX_ALLOC_RETRY;
+      m_first[1]= 0;
+      m_last[1]= 0;
+    }
+    else
+    {
+      /*
+        Pass 1: [random, max_size - 1]
+        Pass 2: [0, ...]
+        The combined length of pass 1 and 2 is PFS_MAX_ALLOC_RETRY.
+      */
+      m_pass_max= 2;
+      m_first[0]= random;
+      m_last[0]= max_size;
+      m_first[1]= 0;
+      m_last[1]= PFS_MAX_ALLOC_RETRY - (max_size - random);
+    }
+  }
+  else
+  {
+    /*
+      The buffer is small compared to PFS_MAX_ALLOC_RETRY,
+      scan it in full in two passes.
+      Pass 1: [random, max_size - 1]
+      Pass 2: [0, random - 1]
+    */
+    m_pass_max= 2;
+    m_first[0]= random;
+    m_last[0]= max_size;
+    m_first[1]= 0;
+    m_last[1]= random;
+  }
+
+  DBUG_ASSERT(m_first[0] < max_size);
+  DBUG_ASSERT(m_first[1] < max_size);
+  DBUG_ASSERT(m_last[1] <= max_size);
+  DBUG_ASSERT(m_last[1] <= max_size);
+  /* The combined length of all passes should not exceed PFS_MAX_ALLOC_RETRY. */
+  DBUG_ASSERT((m_last[0] - m_first[0]) +
+              (m_last[1] - m_first[1]) <= PFS_MAX_ALLOC_RETRY);
+}
+
 /**
   Create instrumentation for a mutex instance.
   @param klass                        the mutex class
@@ -454,17 +525,15 @@ void cleanup_file_hash(void)
 */
 PFS_mutex* create_mutex(PFS_mutex_class *klass, const void *identity)
 {
-  int pass;
-  uint i= randomized_index(identity, mutex_max);
+  PFS_scan scan;
+  uint random= randomized_index(identity, mutex_max);
 
-  /*
-    Pass 1: [random, mutex_max - 1]
-    Pass 2: [0, mutex_max - 1]
-  */
-  for (pass= 1; pass <= 2; i=0, pass++)
+  for (scan.init(random, mutex_max);
+       scan.has_pass();
+       scan.next_pass())
   {
-    PFS_mutex *pfs= mutex_array + i;
-    PFS_mutex *pfs_last= mutex_array + mutex_max;
+    PFS_mutex *pfs= mutex_array + scan.first();
+    PFS_mutex *pfs_last= mutex_array + scan.last();
     for ( ; pfs < pfs_last; pfs++)
     {
       if (pfs->m_lock.is_free())
@@ -512,17 +581,15 @@ void destroy_mutex(PFS_mutex *pfs)
 */
 PFS_rwlock* create_rwlock(PFS_rwlock_class *klass, const void *identity)
 {
-  int pass;
-  uint i= randomized_index(identity, rwlock_max);
+  PFS_scan scan;
+  uint random= randomized_index(identity, rwlock_max);
 
-  /*
-    Pass 1: [random, rwlock_max - 1]
-    Pass 2: [0, rwlock_max - 1]
-  */
-  for (pass= 1; pass <= 2; i=0, pass++)
+  for (scan.init(random, rwlock_max);
+       scan.has_pass();
+       scan.next_pass())
   {
-    PFS_rwlock *pfs= rwlock_array + i;
-    PFS_rwlock *pfs_last= rwlock_array + rwlock_max;
+    PFS_rwlock *pfs= rwlock_array + scan.first();
+    PFS_rwlock *pfs_last= rwlock_array + scan.last();
     for ( ; pfs < pfs_last; pfs++)
     {
       if (pfs->m_lock.is_free())
@@ -576,17 +643,15 @@ void destroy_rwlock(PFS_rwlock *pfs)
 */
 PFS_cond* create_cond(PFS_cond_class *klass, const void *identity)
 {
-  int pass;
-  uint i= randomized_index(identity, cond_max);
+  PFS_scan scan;
+  uint random= randomized_index(identity, cond_max);
 
-  /*
-    Pass 1: [random, cond_max - 1]
-    Pass 2: [0, cond_max - 1]
-  */
-  for (pass= 1; pass <= 2; i=0, pass++)
+  for (scan.init(random, cond_max);
+       scan.has_pass();
+       scan.next_pass())
   {
-    PFS_cond *pfs= cond_array + i;
-    PFS_cond *pfs_last= cond_array + cond_max;
+    PFS_cond *pfs= cond_array + scan.first();
+    PFS_cond *pfs_last= cond_array + scan.last();
     for ( ; pfs < pfs_last; pfs++)
     {
       if (pfs->m_lock.is_free())
@@ -634,17 +699,15 @@ void destroy_cond(PFS_cond *pfs)
 PFS_thread* create_thread(PFS_thread_class *klass, const void *identity,
                           ulong thread_id)
 {
-  int pass;
-  uint i= randomized_index(identity, thread_max);
+  PFS_scan scan;
+  uint random= randomized_index(identity, thread_max);
 
-  /*
-    Pass 1: [random, thread_max - 1]
-    Pass 2: [0, thread_max - 1]
-  */
-  for (pass= 1; pass <= 2; i=0, pass++)
+  for (scan.init(random, thread_max);
+       scan.has_pass();
+       scan.next_pass())
   {
-    PFS_thread *pfs= thread_array + i;
-    PFS_thread *pfs_last= thread_array + thread_max;
+    PFS_thread *pfs= thread_array + scan.first();
+    PFS_thread *pfs_last= thread_array + scan.last();
     for ( ; pfs < pfs_last; pfs++)
     {
       if (pfs->m_lock.is_free())
@@ -728,7 +791,7 @@ find_or_create_file(PFS_thread *thread, 
                     const char *filename, uint len)
 {
   PFS_file *pfs;
-  int pass;
+  PFS_scan scan;
 
   if (! filename_hash_inited)
   {
@@ -840,17 +903,14 @@ search:
   }
 
   /* filename is not constant, just using it for noise on create */
-  uint i= randomized_index(filename, file_max);
+  uint random= randomized_index(filename, file_max);
 
-  /*
-    Pass 1: [random, file_max - 1]
-    Pass 2: [0, file_max - 1]
-  */
-  for (pass= 1; pass <= 2; i=0, pass++)
+  for (scan.init(random, file_max);
+       scan.has_pass();
+       scan.next_pass())
   {
-    pfs= file_array + i;
-    PFS_file *pfs_last= file_array + file_max;
-
+    pfs= file_array + scan.first();
+    PFS_file *pfs_last= file_array + scan.last();
     for ( ; pfs < pfs_last; pfs++)
     {
       if (pfs->m_lock.is_free())
@@ -935,17 +995,15 @@ void destroy_file(PFS_thread *thread, PF
 */
 PFS_table* create_table(PFS_table_share *share, const void *identity)
 {
-  int pass;
-  uint i= randomized_index(identity, table_max);
+  PFS_scan scan;
+  uint random= randomized_index(identity, table_max);
 
-  /*
-    Pass 1: [random, table_max - 1]
-    Pass 2: [0, table_max - 1]
-  */
-  for (pass= 1; pass <= 2; i=0, pass++)
+  for (scan.init(random, table_max);
+       scan.has_pass();
+       scan.next_pass())
   {
-    PFS_table *pfs= table_array + i;
-    PFS_table *pfs_last= table_array + table_max;
+    PFS_table *pfs= table_array + scan.first();
+    PFS_table *pfs_last= table_array + scan.last();
     for ( ; pfs < pfs_last; pfs++)
     {
       if (pfs->m_lock.is_free())

=== modified file 'storage/perfschema/pfs_instr.h'
--- a/storage/perfschema/pfs_instr.h	2010-04-09 08:22:10 +0000
+++ b/storage/perfschema/pfs_instr.h	2010-04-13 10:05:22 +0000
@@ -21,7 +21,6 @@
   Performance schema instruments (declarations).
 */
 
-#include <my_global.h>
 #include <sql_priv.h>
 #include "pfs_lock.h"
 #include "pfs_instr_class.h"
@@ -137,6 +136,48 @@ struct PFS_table : public PFS_instr
 */
 #define LOCKER_STACK_SIZE 3
 
+/**
+  @def PFS_MAX_ALLOC_RETRY
+  Maximum number of times the code attempts to allocate an item
+  from internal buffers, before giving up.
+*/
+#define PFS_MAX_ALLOC_RETRY 1000
+
+#define PFS_MAX_SCAN_PASS 2
+
+/**
+  Helper to scan circular buffers.
+  Given a buffer of size [0, max_size - 1],
+  and a random starting point in the buffer,
+  this helper returns up to two [first, last -1] intervals that:
+  - fit into the [0, max_size - 1] range,
+  - have a maximum combined length of at most PFS_MAX_ALLOC_RETRY.
+*/
+struct PFS_scan
+{
+public:
+  void init(uint random, uint max_size);
+
+  bool has_pass() const
+  { return (m_pass < m_pass_max); }
+
+  void next_pass()
+  { m_pass++; }
+  
+  uint first() const
+  { return m_first[m_pass]; }
+
+  uint last() const
+  { return m_last[m_pass]; }
+
+private:
+  uint m_pass;
+  uint m_pass_max;
+  uint m_first[PFS_MAX_SCAN_PASS];
+  uint m_last[PFS_MAX_SCAN_PASS];
+};
+
+
 /** Instrumented thread implementation. @see PSI_thread. */
 struct PFS_thread
 {


Attachment: [text/bzr-bundle] bzr/marc.alff@oracle.com-20100413100522-1y4xngmqjljedqo5.bundle
Thread
bzr commit into mysql-6.0-codebase-bugfixing branch (marc.alff:3857)Marc Alff13 Apr