List:Commits« Previous MessageNext Message »
From:Kristofer Pettersson Date:September 9 2009 8:41am
Subject:bzr commit into mysql-5.1-bugteam branch (kristofer.pettersson:3048)
Bug#21074 Bug#39253
View as plain text  
#At file:///Users/thek/Development/51-bug39253/ based on revid:kristofer.pettersson@stripped

 3048 Kristofer Pettersson	2009-09-09
      Bug#39253 Large query cache still freezes server after fix for bug #21074
      
      During a cache invalidation the server will be blocked on a mutex waiting for the query cache to finish.
      This patch reduces the time for this wait by making hash delete operations more efficient.
     @ sql/qc_hash.cc
        * Implemented new hash table based on chained hash entries and Jenkins hash function.
         - The hash entry is stored in the Query cache blocks to avoid internal memory allocations.
         - Delete is now a simple pointer operation instead of a linear search.
         - Hash search reorders hash entries by attempting to move the most accessed entry first in the chain.
     @ sql/qc_hash.h
        * Implemented new hash table based on chained hash entries and Jenkins hash function
     @ sql/sql_cache.cc
        * Implemented new hash table based on chained hash entries and Jenkins hash function
         - Replaced free_query() with dettach() and free_query_internal()
     @ sql/sql_cache.h
        * Implemented new hash table based on chained hash entries and Jenkins hash function
     @ sql/sql_plist.h
        * back port of double linked list from alazea tree.

    added:
      sql/qc_hash.cc
      sql/qc_hash.h
      sql/sql_plist.h
    modified:
      sql/Makefile.am
      sql/sql_cache.cc
      sql/sql_cache.h
=== modified file 'sql/Makefile.am'
--- a/sql/Makefile.am	2009-05-15 12:57:51 +0000
+++ b/sql/Makefile.am	2009-09-09 08:41:25 +0000
@@ -76,7 +76,8 @@ noinst_HEADERS =	item.h item_func.h item
 			sql_plugin.h authors.h event_parse_data.h \
 			event_data_objects.h event_scheduler.h \
 			sql_partition.h partition_info.h partition_element.h \
-			contributors.h sql_servers.h
+			contributors.h sql_servers.h \
+      qc_hash.h
 
 mysqld_SOURCES =	sql_lex.cc sql_handler.cc sql_partition.cc \
 			item.cc item_sum.cc item_buff.cc item_func.cc \
@@ -120,7 +121,8 @@ mysqld_SOURCES =	sql_lex.cc sql_handler.
                         event_queue.cc event_db_repository.cc events.cc \
 			sql_plugin.cc sql_binlog.cc \
 			sql_builtin.cc sql_tablespace.cc partition_info.cc \
-			sql_servers.cc event_parse_data.cc
+			sql_servers.cc event_parse_data.cc \
+			qc_hash.cc
 
 nodist_mysqld_SOURCES =	mini_client_errors.c pack.c client.c my_time.c my_user.c 
 

=== added file 'sql/qc_hash.cc'
--- a/sql/qc_hash.cc	1970-01-01 00:00:00 +0000
+++ b/sql/qc_hash.cc	2009-09-09 08:41:25 +0000
@@ -0,0 +1,232 @@
+
+/* Copyright 2000-2008 MySQL AB, 2008 Sun Microsystems, Inc.
+
+   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; version 2 of the License.
+
+   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 <m_string.h>
+#include <m_ctype.h>
+#include "qc_hash.h"
+#include <sql_plist.h>
+
+/**
+  Hash function
+
+  @param str Pointer to characters to be hashed.
+  @param str_len The number of characters
+*/
+
+static ulong hash_func(const uchar *key, uint key_len)
+{
+  uint hash = 0;
+  uchar *end= (uchar *)(key+key_len-1);
+  while (key < end)
+  {
+    hash+= *key;
+    hash+= (hash << 10);
+    hash^= (hash >> 6);
+    ++key;
+  }
+  hash+= (hash << 3);
+  hash^= (hash >> 11);
+  hash+= (hash << 15);
+  return hash;
+}
+
+
+/**
+  @brief Initialize the hash
+
+  @details
+
+  Initialize the hash, by defining and giving valid values for
+  its elements. The failure to allocate memory for the
+  hash->array element will not result in a fatal failure. The
+  dynamic array that is part of the hash will allocate memory
+  as required during insertion.
+
+  @param[in,out] hash         The hash that is initialized
+  @param[in]     size         The number of buckets
+  @param[in]     get_key      get the key for the hash
+  @param[in]     get_meta_record get a pointer to the hash entry
+
+  @return        inidicates success or failure of initialization
+    @retval 0 success
+    @retval 1 failure
+*/
+
+bool
+qc_hash_init(QC_Hash *hash,
+             ulong size,
+             qc_hash_get_key get_key,
+             qc_hash_get_meta_record get_meta_record)
+{
+  hash->m_max_hash_buckets= size;
+  hash->m_hash_array= new Hash_bucket[hash->m_max_hash_buckets];
+  if (hash->m_hash_array == NULL)
+    return TRUE;
+  hash->get_meta_record= get_meta_record;
+  hash->get_key= get_key;
+  hash->m_hash_search_ct= 0;
+  hash->m_memcmp_ct= 0;
+  return FALSE;
+}
+
+
+/**
+  Free memory used by hash.
+
+  @param hash Pointer to the hash table we want to flush
+
+  @note qc_hash_init() must be called to reinitialize the hash after this
+    function is executed.
+
+*/
+
+void qc_hash_free(QC_Hash *hash)
+{
+  if (hash->m_hash_array == NULL)
+    return;
+
+  /* Free all individual elements */
+  qc_hash_reset(hash);
+
+  /* Free array of buckets  */
+  delete [] hash->m_hash_array;
+
+  /* Reset pointer as a matter of good form */
+  hash->m_hash_array= NULL;
+}
+
+
+/**
+  Delete all elements from the hash (the hash itself is to be reused).
+
+  @param hash Pointer to the hash
+*/
+
+void qc_hash_reset(QC_Hash *hash)
+{
+  if (hash->m_hash_array == NULL)
+    return;
+
+  for(int i=0; i< hash->m_max_hash_buckets; i++)
+  {
+    Hash_bucket *bucket= &hash->m_hash_array[i];
+    while (!bucket->is_empty())
+    {
+      Meta_record *mrec= bucket->head();
+      bucket->remove(mrec);
+    }
+  }
+}
+
+
+/**
+  Find key in hash.
+
+  @param hash Pointer to hash table
+  @param key Pointer to the key
+  @param length The number of characters in the key
+
+  @return A record
+    @retval NULL Failure to find an record associated with key.
+*/
+
+Query_cache_block* qc_hash_search(QC_Hash *hash, uchar *key, size_t length)
+{
+  ulong idx= hash_func(key, length) & (hash->m_max_hash_buckets - 1);
+  Hash_bucket *bucket= &hash->m_hash_array[idx];
+  Hash_bucket::Iterator it(*bucket);
+  uint iteration_count= 0;
+  ++hash->m_hash_search_ct;
+  while( Meta_record *mrec= it++ )
+  {
+    ++iteration_count;
+    size_t rec_key_len;
+    uchar *rec_key= hash->get_key((uchar*)mrec->record,&rec_key_len, FALSE);
+    if (memcmp((const char*)rec_key,(const char*)key,length) == 0)
+    {
+      ++mrec->access_count;
+      Meta_record *hottest_record= bucket->head();
+      if (mrec->access_count > hottest_record->access_count)
+      {
+        bucket->remove(mrec);
+        bucket->push_front(mrec);
+      }
+      hash->m_memcmp_ct+= iteration_count;
+      return mrec->record;
+    }
+  }
+  return NULL;
+}
+
+
+/**
+  Write a hash-key to the hash-index
+*/
+
+Meta_record *qc_hash_insert(QC_Hash *info,Query_cache_block *record)
+{
+  size_t key_length;
+  uchar *key= info->get_key((uchar *)record,&key_length, FALSE);
+  ulong idx= hash_func(key, key_length) & (info->m_max_hash_buckets - 1);
+  Hash_bucket *bucket= &info->m_hash_array[idx];
+
+  /*
+    Query_cache_block might be either a Query_cache_query
+    or a Query_cache table object. To find the right members
+    we use a function pointer stored in the cache meta data.
+  */
+  Meta_record *mrec= info->get_meta_record(record);
+  if (!mrec)
+    return NULL;
+  mrec->init(record);
+  bucket->push_front(mrec);
+  return mrec;
+}
+
+#ifndef DBUG_OFF
+bool qc_check_hash(QC_Hash *hash)
+{
+  DBUG_ENTER("qc_check_hash");
+  for (int idx=0; idx< hash->m_max_hash_buckets; idx++)
+  {
+    Hash_bucket *bucket= &hash->m_hash_array[idx];
+    Hash_bucket::Iterator it(*bucket);
+    uint iteration_count= 0;
+    DBUG_PRINT("qc_check_hash",("hash search ct=%lu, memcmp ct= %lu",
+               hash->m_hash_search_ct, hash->m_memcmp_ct));
+    Meta_record *old_next=0;
+    while( Meta_record *mrec= it++ )
+    {
+      if (old_next)
+      {
+        DBUG_ASSERT(*mrec->prev_next_ptr==old_next);
+        DBUG_ASSERT(*mrec->prev_next_ptr == mrec);
+        DBUG_ASSERT(old_next== mrec);
+        old_next= mrec->next;
+
+      }
+      DBUG_PRINT("qc_check_hash",("0x%lx bucket=%u mrec[%u]= {first= 0x%lx,"
+                 "mrec= 0x%lx, access_count= %lu, next= 0x%lx, prev next="
+                 " 0x%lx (0x%lx), record= 0x%lx }",
+                 hash,idx,++iteration_count,bucket->first,mrec,
+                 mrec->access_count, mrec->next, *mrec->prev_next_ptr,
+                 mrec->prev_next_ptr, mrec->record));
+    }
+  }
+  DBUG_RETURN(false);
+}
+#endif

=== added file 'sql/qc_hash.h'
--- a/sql/qc_hash.h	1970-01-01 00:00:00 +0000
+++ b/sql/qc_hash.h	2009-09-09 08:41:25 +0000
@@ -0,0 +1,93 @@
+/* Copyright 2000-2008 MySQL AB, 2008 Sun Microsystems, Inc.
+
+   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; version 2 of the License.
+
+   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 _QC_QC_Hash_H
+#define	_QC_QC_Hash_H
+#include <my_sys.h>
+#include <sql_plist.h>
+
+class Query_cache_block;
+
+class Meta_record
+{
+public:
+  Query_cache_block *record;
+  ulong access_count;
+  Meta_record *next;
+  Meta_record **prev_next_ptr;
+
+  void init(Query_cache_block *block= NULL)
+  {
+      access_count= 0;
+      next= 0;
+      prev_next_ptr= 0;
+      record= block;
+  }
+
+  void dettach()
+  {
+    if (next)
+      next->prev_next_ptr= prev_next_ptr;
+    *prev_next_ptr= next;
+    next= 0;
+    prev_next_ptr= 0;
+  }
+
+  Meta_record() { init(); }
+};
+
+typedef I_P_List<Meta_record, I_P_List_adapter<Meta_record,
+                 &Meta_record::next,
+                 &Meta_record::prev_next_ptr> > Hash_bucket;
+
+typedef Meta_record *(*qc_hash_get_meta_record)(Query_cache_block *);
+typedef uchar *(*qc_hash_get_key)(const uchar *, size_t *, my_bool);
+
+class QC_Hash
+{
+public:
+    /** Hash is assumed to be of a power of 2 */
+    uint m_max_hash_buckets;
+
+    /** Total number of memcmps */
+    ulong m_memcmp_ct;
+
+    /** Total number of calls to hash_search */
+    ulong m_hash_search_ct;
+
+    /** Pointer to a static array of chained lists */
+    Hash_bucket *m_hash_array;
+
+    /** Method for getting the meta record from a record */
+    qc_hash_get_meta_record get_meta_record;
+
+    /** Method for getting the key from a record */
+    qc_hash_get_key get_key;
+};
+
+
+bool
+qc_hash_init(QC_Hash *hash,
+              unsigned long size,
+              qc_hash_get_key get_key,
+              qc_hash_get_meta_record get_mrec);
+
+void qc_hash_free(QC_Hash *hash);
+void qc_hash_reset(QC_Hash *hash);
+Query_cache_block* qc_hash_search(QC_Hash *hash, uchar *key, size_t key_length);
+Meta_record *qc_hash_insert(QC_Hash *info, Query_cache_block *block);
+bool qc_check_hash(QC_Hash *hash);
+#endif	/* _QC_QC_Hash_H */
+

=== modified file 'sql/sql_cache.cc'
--- a/sql/sql_cache.cc	2009-06-16 08:34:47 +0000
+++ b/sql/sql_cache.cc	2009-09-09 08:41:25 +0000
@@ -327,12 +327,14 @@ TODO list:
 */
 
 #include "mysql_priv.h"
+#define HAVE_QUERY_CACHE
 #ifdef HAVE_QUERY_CACHE
 #include <m_ctype.h>
 #include <my_dir.h>
-#include <hash.h>
+#include <qc_hash.h>
 #include "../storage/myisammrg/ha_myisammrg.h"
 #include "../storage/myisammrg/myrg_def.h"
+#include "sql_cache.h"
 
 #ifdef EMBEDDED_LIBRARY
 #include "emb_qcache.h"
@@ -411,7 +413,6 @@ TYPELIB query_cache_type_typelib=
   array_elements(query_cache_type_names)-1,"", query_cache_type_names, NULL
 };
 
-
 /**
   Serialize access to the query cache.
   If the lock cannot be granted the thread hangs in a conditional wait which
@@ -680,6 +681,12 @@ uchar *query_cache_table_get_key(const u
   return (((uchar *) table_block->data()) +
 	  ALIGN_SIZE(sizeof(Query_cache_table)));
 }
+
+Meta_record *query_cache_table_get_mrec(Query_cache_block *block)
+{
+  Query_cache_table *table= block->table();
+  return &table->m_hash_entry;
+}
 }
 
 /*****************************************************************************
@@ -742,6 +749,7 @@ void Query_cache_query::init_n_lock()
 {
   DBUG_ENTER("Query_cache_query::init_n_lock");
   res=0; wri = 0; len = 0;
+  m_hash_entry.init();
   my_rwlock_init(&lock, NULL);
   lock_writing();
   DBUG_PRINT("qcache", ("inited & locked query for block 0x%lx",
@@ -778,6 +786,12 @@ uchar *query_cache_query_get_key(const u
   return (((uchar *) query_block->data()) +
 	  ALIGN_SIZE(sizeof(Query_cache_query)));
 }
+
+Meta_record *query_cache_query_get_mrec(Query_cache_block *block)
+{
+  Query_cache_query *query= block->query();
+  return &query->m_hash_entry;
+}
 }
 
 /*****************************************************************************
@@ -873,7 +887,8 @@ void query_cache_insert(NET *net, const 
     header->result(result);
     DBUG_PRINT("qcache", ("free query 0x%lx", (ulong) query_block));
     // The following call will remove the lock on query_block
-    query_cache.free_query(query_block);
+    query_block->query()->m_hash_entry.dettach();
+    query_cache.free_query_internal(query_block);
     query_cache.refused++;
     // append_result_data no success => we need unlock
     query_cache.unlock();
@@ -913,7 +928,8 @@ void query_cache_abort(NET *net)
     DUMP(&query_cache);
     BLOCK_LOCK_WR(query_block);
     // The following call will remove the lock on query_block
-    query_cache.free_query(query_block);
+    query_block->query()->m_hash_entry.dettach();
+    query_cache.free_query_internal(query_block);
     net->query_cache_query= 0;
     DBUG_EXECUTE("check_querycache",query_cache.check_integrity(1););
   }
@@ -1056,32 +1072,35 @@ ulong Query_cache::resize(ulong query_ca
 
   lock_and_suspend();
 
-  /*
-    Wait for all readers and writers to exit. When the list of all queries
-    is iterated over with a block level lock, we are done.
-  */
-  Query_cache_block *block= queries_blocks;
-  if (block)
+  if (query_cache_size > 0)
   {
-    do
+    /*
+      Wait for all readers and writers to exit. When the list of all queries
+      is iterated over with a block level lock, we are done.
+    */
+    Query_cache_block *block= queries_blocks;
+    if (block)
     {
-      BLOCK_LOCK_WR(block);
-      Query_cache_query *query= block->query();
-      if (query && query->writer())
+      do
       {
-        /*
-           Drop the writer; this will cancel any attempts to store 
-           the processed statement associated with this writer.
-         */
-        query->writer()->query_cache_query= 0;
-        query->writer(0);
-        refused++;
-      }
-      BLOCK_UNLOCK_WR(block);
-      block= block->next;
-    } while (block != queries_blocks);
-  }
-  free_cache();
+        BLOCK_LOCK_WR(block);
+        Query_cache_query *query= block->query();
+        if (query && query->writer())
+        {
+          /*
+             Drop the writer; this will cancel any attempts to store
+             the processed statement associated with this writer.
+           */
+          query->writer()->query_cache_query= 0;
+          query->writer(0);
+          refused++;
+        }
+        BLOCK_UNLOCK_WR(block);
+        block= block->next;
+      } while (block != queries_blocks);
+    }
+    free_cache();
+ }
 
   query_cache_size= query_cache_size_arg;
   new_query_cache_size= init_cache();
@@ -1229,7 +1248,7 @@ def_week_frmt: %lu, in_trans: %d, autoco
 
     /* Check if another thread is processing the same query? */
     Query_cache_block *competitor = (Query_cache_block *)
-      hash_search(&queries, (uchar*) thd->query, tot_length);
+      qc_hash_search(&queries, (uchar*) thd->query, tot_length);
     DBUG_PRINT("qcache", ("competitor 0x%lx", (ulong) competitor));
     if (competitor == 0)
     {
@@ -1245,7 +1264,8 @@ def_week_frmt: %lu, in_trans: %d, autoco
 
 	Query_cache_query *header = query_block->query();
 	header->init_n_lock();
-	if (my_hash_insert(&queries, (uchar*) query_block))
+	Meta_record *mrec= qc_hash_insert(&queries, query_block);
+	if (mrec == NULL)
 	{
 	  refused++;
 	  DBUG_PRINT("qcache", ("insertion in query hash"));
@@ -1258,7 +1278,10 @@ def_week_frmt: %lu, in_trans: %d, autoco
 	{
 	  refused++;
 	  DBUG_PRINT("warning", ("tables list including failed"));
-	  hash_delete(&queries, (uchar *) query_block);
+          /*
+	    Unlink the record from the hash table
+	  */
+	  header->m_hash_entry.dettach();
 	  header->unlock_n_destroy();
 	  free_memory_block(query_block);
           unlock();
@@ -1462,7 +1485,7 @@ def_week_frmt: %lu, in_trans: %d, autoco
                           (int)flags.autocommit));
   memcpy((uchar *)(sql + (tot_length - QUERY_CACHE_FLAGS_SIZE)),
 	 (uchar*) &flags, QUERY_CACHE_FLAGS_SIZE);
-  query_block = (Query_cache_block *)  hash_search(&queries, (uchar*) sql,
+  query_block = (Query_cache_block *)  qc_hash_search(&queries, (uchar*) sql,
 						   tot_length);
   /* Quick abort on unlocked data */
   if (query_block == 0 ||
@@ -2066,8 +2089,8 @@ ulong Query_cache::init_cache()
 
   DUMP(this);
 
-  VOID(hash_init(&queries, &my_charset_bin, def_query_hash_size, 0, 0,
-		 query_cache_query_get_key, 0, 0));
+  VOID(qc_hash_init(&queries, QUERY_CACHE_DEF_QUERY_HASH_SIZE,
+		    query_cache_query_get_key, query_cache_query_get_mrec));
 #ifndef FN_NO_CASE_SENCE
   /*
     If lower_case_table_names!=0 then db and table names are already 
@@ -2077,8 +2100,8 @@ ulong Query_cache::init_cache()
     lower_case_table_names == 0 then we should distinguish my_table
     and MY_TABLE cases and so again can use binary collation.
   */
-  VOID(hash_init(&tables, &my_charset_bin, def_table_hash_size, 0, 0,
-		 query_cache_table_get_key, 0, 0));
+  VOID(qc_hash_init(&tables, QUERY_CACHE_DEF_TABLE_HASH_SIZE,
+		 query_cache_table_get_key, query_cache_table_get_mrec));
 #else
   /*
     On windows, OS/2, MacOS X with HFS+ or any other case insensitive
@@ -2088,10 +2111,8 @@ ulong Query_cache::init_cache()
     file system) and so should use case insensitive collation for
     comparison.
   */
-  VOID(hash_init(&tables,
-		 lower_case_table_names ? &my_charset_bin :
-		 files_charset_info,
-		 def_table_hash_size, 0, 0,query_cache_table_get_key, 0, 0));
+  VOID(qc_hash_init(&tables, def_table_hash_size, query_cache_table_get_key,
+                    query_cache_table_get_mrec));
 #endif
 
   queries_in_cache = 0;
@@ -2139,10 +2160,10 @@ void Query_cache::free_cache()
 {
   DBUG_ENTER("Query_cache::free_cache");
 
-  my_free((uchar*) cache, MYF(MY_ALLOW_ZERO_PTR));
   make_disabled();
-  hash_free(&queries);
-  hash_free(&tables);
+  qc_hash_free(&queries);
+  qc_hash_free(&tables);
+  my_free((uchar*) cache, MYF(MY_ALLOW_ZERO_PTR));
   DBUG_VOID_RETURN;
 }
 
@@ -2170,7 +2191,10 @@ void Query_cache::flush_cache()
   DBUG_EXECUTE_IF("wait_in_query_cache_flush2",
                   debug_wait_for_kill("wait_in_query_cache_flush2"););
 
-  my_hash_reset(&queries);
+  /* If the query cache is disabled there is nothing to do */
+  if (query_cache_size == 0)
+    return;
+  qc_hash_reset(&queries);
   while (queries_blocks != 0)
   {
     BLOCK_LOCK_WR(queries_blocks);
@@ -2213,7 +2237,10 @@ my_bool Query_cache::free_old_query()
 
     if (query_block != 0)
     {
-      free_query(query_block);
+      /* Unlink the query lookup entry from the hash table */
+      Query_cache_query *query_header_data= query_block->query();
+      query_header_data->m_hash_entry.dettach();
+      free_query_internal(query_block);
       lowmem_prunes++;
       DBUG_RETURN(0);
     }
@@ -2317,7 +2344,7 @@ void Query_cache::free_query(Query_cache
 		      (ulong) query_block,
 		      query_block->query()->length() ));
 
-  hash_delete(&queries,(uchar *) query_block);
+  query_block->query()->m_hash_entry.dettach();
   free_query_internal(query_block);
 
   DBUG_VOID_RETURN;
@@ -2646,7 +2673,7 @@ void
 Query_cache::invalidate_table_internal(THD *thd, uchar *key, uint32 key_length)
 {
   Query_cache_block *table_block=
-    (Query_cache_block*)hash_search(&tables, key, key_length);
+    (Query_cache_block*)qc_hash_search(&tables, key, key_length);
   if (table_block)
   {
     Query_cache_block_table *list_root= table_block->table(0);
@@ -2673,8 +2700,11 @@ Query_cache::invalidate_query_block_list
   while (list_root->next != list_root)
   {
     Query_cache_block *query_block= list_root->next->block();
+    Query_cache_query *header= query_block->query();
+    /* Remove the query from the hash table */
+    header->m_hash_entry.dettach();
     BLOCK_LOCK_WR(query_block);
-    free_query(query_block);
+    free_query_internal(query_block);
     DBUG_EXECUTE_IF("debug_cache_locks", sleep(10););
   }
 }
@@ -2844,7 +2874,7 @@ Query_cache::insert_table(uint key_len, 
   THD *thd= current_thd;
 
   Query_cache_block *table_block= 
-    (Query_cache_block *)hash_search(&tables, (uchar*) key, key_len);
+    (Query_cache_block *)qc_hash_search(&tables, (uchar*) key, key_len);
 
   if (table_block &&
       table_block->table()->engine_data() != engine_data)
@@ -2894,7 +2924,7 @@ Query_cache::insert_table(uint key_len, 
     */
     list_root->next= list_root->prev= list_root;
 
-    if (my_hash_insert(&tables, (const uchar *) table_block))
+    if (qc_hash_insert(&tables, table_block) == NULL)
     {
       DBUG_PRINT("qcache", ("Can't insert table to hash"));
       // write_block_data return locked block
@@ -2960,7 +2990,7 @@ void Query_cache::unlink_table(Query_cac
     Query_cache_block *table_block= neighbour->block();
     double_linked_list_exclude(table_block,
                                &tables_blocks);
-    hash_delete(&tables,(uchar *) table_block);
+    table_block->table()->m_hash_entry.dettach();
     free_memory_block(table_block);
   }
   DBUG_VOID_RETURN;
@@ -3626,7 +3656,6 @@ my_bool Query_cache::move_by_type(uchar 
   }
   case Query_cache_block::TABLE:
   {
-    HASH_SEARCH_STATE record_idx;
     DBUG_PRINT("qcache", ("block 0x%lx TABLE", (ulong) block));
     if (*border == 0)
       break;
@@ -3641,10 +3670,12 @@ my_bool Query_cache::move_by_type(uchar 
 		      *new_block =(Query_cache_block *) *border;
     uint tablename_offset = block->table()->table() - block->table()->db();
     char *data = (char*) block->data();
-    uchar *key;
-    size_t key_length;
-    key=query_cache_table_get_key((uchar*) block, &key_length, 0);
-    hash_first(&tables, (uchar*) key, key_length, &record_idx);
+
+    /*
+     Dettach the object from the hash
+    */
+    ulong access_count= tables.get_meta_record(block)->access_count;
+    tables.get_meta_record(block)->dettach();
 
     block->destroy();
     new_block->init(len);
@@ -3675,18 +3706,14 @@ my_bool Query_cache::move_by_type(uchar 
       tnext->parent= new_block_table;
     *border += len;
     *before = new_block;
-    /* Fix pointer to table name */
-    new_block->table()->table(new_block->table()->db() + tablename_offset);
-    /* Fix hash to point at moved block */
-    hash_replace(&tables, &record_idx, (uchar*) new_block);
-
+    qc_hash_insert(&tables,new_block);
+    tables.get_meta_record(new_block)->access_count= access_count;
     DBUG_PRINT("qcache", ("moved %lu bytes to 0x%lx, new gap at 0x%lx",
 			len, (ulong) new_block, (ulong) *border));
     break;
   }
   case Query_cache_block::QUERY:
   {
-    HASH_SEARCH_STATE record_idx;
     DBUG_PRINT("qcache", ("block 0x%lx QUERY", (ulong) block));
     if (*border == 0)
       break;
@@ -3701,10 +3728,13 @@ my_bool Query_cache::move_by_type(uchar 
     char *data = (char*) block->data();
     Query_cache_block *first_result_block = ((Query_cache_query *)
 					     block->data())->result();
-    uchar *key;
-    size_t key_length;
-    key=query_cache_query_get_key((uchar*) block, &key_length, 0);
-    hash_first(&queries, (uchar*) key, key_length, &record_idx);
+
+    /*
+     Dettach the object from the hash
+    */
+    ulong access_count= queries.get_meta_record(block)->access_count;
+    queries.get_meta_record(block)->dettach();
+     
     // Move table of used tables 
     memmove((char*) new_block->table(0), (char*) block->table(0),
 	   ALIGN_SIZE(n_tables*sizeof(Query_cache_block_table)));
@@ -3771,8 +3801,9 @@ my_bool Query_cache::move_by_type(uchar 
     {
       net->query_cache_query= (uchar*) new_block;
     }
-    /* Fix hash to point at moved block */
-    hash_replace(&queries, &record_idx, (uchar*) new_block);
+    qc_hash_insert(&queries,new_block);
+    queries.get_meta_record(new_block)->access_count= access_count;
+
     DBUG_PRINT("qcache", ("moved %lu bytes to 0x%lx, new gap at 0x%lx",
 			len, (ulong) new_block, (ulong) *border));
     break;
@@ -4183,20 +4214,12 @@ my_bool Query_cache::check_integrity(boo
   if (!locked)
     lock_and_suspend();
 
-  if (hash_check(&queries))
-  {
-    DBUG_PRINT("error", ("queries hash is damaged"));
-    result = 1;
-  }
-
-  if (hash_check(&tables))
-  {
-    DBUG_PRINT("error", ("tables hash is damaged"));
-    result = 1;
-  }
-
   DBUG_PRINT("qcache", ("physical address check ..."));
   ulong free=0, used=0;
+
+  qc_check_hash(&queries);
+  qc_check_hash(&tables);
+  
   Query_cache_block * block = first_block;
   do
   {
@@ -4356,7 +4379,7 @@ my_bool Query_cache::check_integrity(boo
 			    (ulong) block, (uint) block->type));
       size_t length;
       uchar *key = query_cache_query_get_key((uchar*) block, &length, 0);
-      uchar* val = hash_search(&queries, key, length);
+      uchar *val = (uchar *)qc_hash_search(&queries, key, length);
       if (((uchar*)block) != val)
       {
 	DBUG_PRINT("error", ("block 0x%lx found in queries hash like 0x%lx",
@@ -4391,7 +4414,7 @@ my_bool Query_cache::check_integrity(boo
 			    (ulong) block, (uint) block->type));
       size_t length;
       uchar *key = query_cache_table_get_key((uchar*) block, &length, 0);
-      uchar* val = hash_search(&tables, key, length);
+      uchar *val = (uchar *)qc_hash_search(&tables, key, length);
       if (((uchar*)block) != val)
       {
 	DBUG_PRINT("error", ("block 0x%lx found in tables hash like 0x%lx",

=== modified file 'sql/sql_cache.h'
--- a/sql/sql_cache.h	2009-06-16 08:34:47 +0000
+++ b/sql/sql_cache.h	2009-09-09 08:41:25 +0000
@@ -27,7 +27,7 @@
 #define QUERY_CACHE_MIN_ALLOCATION_UNIT		512
 
 /* inittial size of hashes */
-#define QUERY_CACHE_DEF_QUERY_HASH_SIZE		1024
+#define QUERY_CACHE_DEF_QUERY_HASH_SIZE		2048
 #define QUERY_CACHE_DEF_TABLE_HASH_SIZE		1024
 
 /* minimal result data size when data allocated */
@@ -64,6 +64,7 @@ struct Query_cache_table;
 struct Query_cache_query;
 struct Query_cache_result;
 class Query_cache;
+#include <qc_hash.h>
 
 /**
   This class represents a node in the linked chain of queries
@@ -134,6 +135,7 @@ struct Query_cache_block
 
 struct Query_cache_query
 {
+  Meta_record m_hash_entry;
   ulonglong limit_found_rows;
   rw_lock_t lock;
   Query_cache_block *res;
@@ -171,6 +173,7 @@ struct Query_cache_query
 struct Query_cache_table
 {
   Query_cache_table() {}                      /* Remove gcc warning */
+  Meta_record m_hash_entry;
   char *tbl;
   uint32 key_len;
   uint8 table_type;
@@ -305,7 +308,7 @@ protected:
 
   Query_cache_memory_bin *bins;			// free block lists
   Query_cache_memory_bin_step *steps;		// bins spacing info
-  HASH queries, tables;
+  QC_Hash queries, tables;
   /* options */
   ulong min_allocation_unit, min_result_data_size;
   uint def_query_hash_size, def_table_hash_size;

=== added file 'sql/sql_plist.h'
--- a/sql/sql_plist.h	1970-01-01 00:00:00 +0000
+++ b/sql/sql_plist.h	2009-09-09 08:41:25 +0000
@@ -0,0 +1,141 @@
+#ifndef SQL_PLIST_H
+#define SQL_PLIST_H
+/* Copyright (C) 2008 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; version 2 of the License.
+
+   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>
+
+template <typename T, typename B> class I_P_List_iterator;
+
+
+/**
+   Intrusive parameterized list.
+
+   Unlike I_List does not require its elements to be descendant of ilink
+   class and therefore allows them to participate in several such lists
+   simultaneously.
+
+   Unlike List is doubly-linked list and thus supports efficient deletion
+   of element without iterator.
+
+   @param T  Type of elements which will belong to list.
+   @param B  Class which via its methods specifies which members
+             of T should be used for participating in this list.
+             Here is typical layout of such class:
+
+             struct B
+             {
+               static inline T **next_ptr(T *el)
+               {
+                 return &el->next;
+               }
+               static inline T ***prev_ptr(T *el)
+               {
+                 return &el->prev;
+               }
+             };
+*/
+
+template <typename T, typename B>
+class I_P_List
+{
+public:
+    T *first;
+
+  /*
+    Do not prohibit copying of I_P_List object to simplify their usage in
+    backup/restore scenarios. Note that performing any operations on such
+    is a bad idea.
+  */
+public:
+  I_P_List() : first(NULL) { };
+  inline void empty()      { first= NULL; }
+  inline bool is_empty() const { return (first == NULL); }
+  inline void push_front(T* a)
+  {
+    *B::next_ptr(a)= first;
+    if (first)
+      *B::prev_ptr(first)= B::next_ptr(a);
+    first= a;
+    *B::prev_ptr(a)= &first;
+  }
+  inline void remove(T *a)
+  {
+    T *next= *B::next_ptr(a);
+    if (next)
+      *B::prev_ptr(next)= *B::prev_ptr(a);
+    **B::prev_ptr(a)= next;
+  }
+  inline T* head() { return first; }
+  inline const T *head() const { return first; }
+  void swap(I_P_List<T,B> &rhs)
+  {
+    swap_variables(T *, first, rhs.first);
+    if (first)
+      *B::prev_ptr(first)= &first;
+    if (rhs.first)
+      *B::prev_ptr(rhs.first)= &rhs.first;
+  }
+#ifndef _lint
+  friend class I_P_List_iterator<T, B>;
+#endif
+  typedef I_P_List_iterator<T, B> Iterator;
+};
+
+
+/**
+   Iterator for I_P_List.
+*/
+
+template <typename T, typename B>
+class I_P_List_iterator
+{
+  I_P_List<T, B> *list;
+  T *current;
+public:
+  I_P_List_iterator(I_P_List<T, B> &a) : list(&a), current(a.first) {}
+  inline void init(I_P_List<T, B> &a)
+  {
+    list= &a;
+    current= a.first;
+  }
+  inline T* operator++(int)
+  {
+    T *result= current;
+    if (result)
+      current= *B::next_ptr(current);
+    return result;
+  }
+  inline void rewind()
+  {
+    current= list->first;
+  }
+};
+
+
+/**
+  Hook class which via its methods specifies which members
+  of T should be used for participating in MDL lists.
+*/
+
+template <typename T, T* T::*next, T** T::*prev>
+struct I_P_List_adapter
+{
+  static inline T **next_ptr(T *el) { return &(el->*next); }
+
+  static inline T ***prev_ptr(T *el) { return &(el->*prev); }
+};
+#endif


Attachment: [text/bzr-bundle]
Thread
bzr commit into mysql-5.1-bugteam branch (kristofer.pettersson:3048)Bug#21074 Bug#39253Kristofer Pettersson9 Sep