- commits - lists.mariadb.org

[Commits] a30776d: MDEV-17631 select_handler for a full query pushdown.
by IgorBabaev 25 Jan '19

25 Jan '19

revision-id: a30776dd98d8e7b44e8b3e2bc07c23c0beed2434 (mariadb-10.3.6-131-ga30776d) parent(s): 5dc4ca6554c9bb4685b64c35f345c06d28c8d3f9 author: Igor Babaev committer: Igor Babaev timestamp: 2019-01-25 03:08:46 -0800 message: MDEV-17631 select_handler for a full query pushdown. Interface + Proof of Concept for federatedx with a test case. --- libmysqld/CMakeLists.txt | 1 + .../federated/federatedx_create_handlers.result | 92 +++++++++++++++ .../federated/federatedx_create_handlers.test | 68 +++++++++++ sql/CMakeLists.txt | 2 +- sql/handler.h | 7 ++ sql/select_handler.cc | 131 +++++++++++++++++++++ sql/select_handler.h | 48 ++++++++ sql/sql_lex.cc | 2 + sql/sql_lex.h | 10 +- sql/sql_select.cc | 52 +++++++- sql/sql_select.h | 27 +++++ storage/federatedx/ha_federatedx.cc | 122 +++++++++++++++++++ storage/federatedx/ha_federatedx.h | 20 ++++ 13 files changed, 578 insertions(+), 4 deletions(-) diff --git a/libmysqld/CMakeLists.txt b/libmysqld/CMakeLists.txt index dc3d190..5936c4e 100644 --- a/libmysqld/CMakeLists.txt +++ b/libmysqld/CMakeLists.txt @@ -78,6 +78,7 @@ SET(SQL_EMBEDDED_SOURCES emb_qcache.cc libmysqld.c lib_sql.cc ../sql/sql_prepare.cc ../sql/sql_rename.cc ../sql/sql_repl.cc ../sql/sql_select.cc ../sql/sql_servers.cc ../sql/group_by_handler.cc ../sql/derived_handler.cc + ../sql/select_handler.cc ../sql/sql_show.cc ../sql/sql_state.c ../sql/sql_statistics.cc ../sql/sql_string.cc ../sql/sql_tablespace.cc ../sql/sql_table.cc ../sql/sql_test.cc diff --git a/mysql-test/suite/federated/federatedx_create_handlers.result b/mysql-test/suite/federated/federatedx_create_handlers.result new file mode 100644 index 0000000..d32853e --- /dev/null +++ b/mysql-test/suite/federated/federatedx_create_handlers.result @@ -0,0 +1,92 @@ +connect master,127.0.0.1,root,,test,$MASTER_MYPORT,; +connect slave,127.0.0.1,root,,test,$SLAVE_MYPORT,; +connection master; +CREATE DATABASE federated; +connection slave; +CREATE DATABASE federated; +connection slave; +DROP TABLE IF EXISTS federated.t1; +Warnings: +Note 1051 Unknown table 'federated.t1' +CREATE TABLE federated.t1 ( +id int(20) NOT NULL, +name varchar(16) NOT NULL default '' +) +DEFAULT CHARSET=latin1; +INSERT INTO federated.t1 VALUES +(3,'xxx'), (7,'yyy'), (4,'xxx'), (1,'zzz'), (5,'yyy'); +CREATE TABLE federated.t2 ( +name varchar(16) NOT NULL default '' +) +DEFAULT CHARSET=latin1; +INSERT INTO federated.t2 VALUES +('yyy'), ('www'), ('yyy'), ('xxx'), ('www'), ('yyy'), ('www'); +connection master; +DROP TABLE IF EXISTS federated.t1; +Warnings: +Note 1051 Unknown table 'federated.t1' +CREATE TABLE federated.t1 ( +id int(20) NOT NULL, +name varchar(16) NOT NULL default '' +) +ENGINE="FEDERATED" DEFAULT CHARSET=latin1 +CONNECTION='mysql://root@127.0.0.1:SLAVE_PORT/federated/t1'; +CREATE TABLE federated.t2 ( +name varchar(16) NOT NULL default '' +) +ENGINE="FEDERATED" DEFAULT CHARSET=latin1 +CONNECTION='mysql://root@127.0.0.1:SLAVE_PORT/federated/t2'; +SELECT * FROM federated.t1; +id name +3 xxx +7 yyy +4 xxx +1 zzz +5 yyy +SELECT id FROM federated.t1 WHERE id < 5; +id +3 +4 +1 +SELECT count(*), name FROM federated.t1 WHERE id < 5 GROUP BY name; +count(*) name +2 xxx +1 zzz +SELECT * FROM federated.t1, federated.t2 +WHERE federated.t1.name = federated.t2.name; +id name name +7 yyy yyy +5 yyy yyy +7 yyy yyy +5 yyy yyy +3 xxx xxx +4 xxx xxx +7 yyy yyy +5 yyy yyy +SELECT * FROM federated.t1 LEFT JOIN federated.t2 +ON federated.t1.name = federated.t2.name +WHERE federated.t1.id > 1; +id name name +7 yyy yyy +5 yyy yyy +7 yyy yyy +5 yyy yyy +3 xxx xxx +4 xxx xxx +7 yyy yyy +5 yyy yyy +SELECT * FROM federated.t1 +WHERE id IN (SELECT count(*) FROM federated.t2 GROUP BY name); +id name +3 xxx +1 zzz +DROP TABLE federated.t1, federated.t2; +connection slave; +DROP TABLE federated.t1, federated.t2; +connection default; +connection master; +DROP TABLE IF EXISTS federated.t1; +DROP DATABASE IF EXISTS federated; +connection slave; +DROP TABLE IF EXISTS federated.t1; +DROP DATABASE IF EXISTS federated; diff --git a/mysql-test/suite/federated/federatedx_create_handlers.test b/mysql-test/suite/federated/federatedx_create_handlers.test new file mode 100644 index 0000000..92a6f3c --- /dev/null +++ b/mysql-test/suite/federated/federatedx_create_handlers.test @@ -0,0 +1,68 @@ +--source have_federatedx.inc +--source include/federated.inc + +connection slave; +DROP TABLE IF EXISTS federated.t1; + +CREATE TABLE federated.t1 ( + id int(20) NOT NULL, + name varchar(16) NOT NULL default '' +) +DEFAULT CHARSET=latin1; + +INSERT INTO federated.t1 VALUES + (3,'xxx'), (7,'yyy'), (4,'xxx'), (1,'zzz'), (5,'yyy'); + +CREATE TABLE federated.t2 ( + name varchar(16) NOT NULL default '' +) +DEFAULT CHARSET=latin1; + +INSERT INTO federated.t2 VALUES + ('yyy'), ('www'), ('yyy'), ('xxx'), ('www'), ('yyy'), ('www'); + + +connection master; +DROP TABLE IF EXISTS federated.t1; + +--replace_result $SLAVE_MYPORT SLAVE_PORT +eval +CREATE TABLE federated.t1 ( + id int(20) NOT NULL, + name varchar(16) NOT NULL default '' +) +ENGINE="FEDERATED" DEFAULT CHARSET=latin1 +CONNECTION='mysql://root@127.0.0.1:$SLAVE_MYPORT/federated/t1'; + +--replace_result $SLAVE_MYPORT SLAVE_PORT +eval +CREATE TABLE federated.t2 ( + name varchar(16) NOT NULL default '' +) +ENGINE="FEDERATED" DEFAULT CHARSET=latin1 +CONNECTION='mysql://root@127.0.0.1:$SLAVE_MYPORT/federated/t2'; + +SELECT * FROM federated.t1; + +SELECT id FROM federated.t1 WHERE id < 5; + +SELECT count(*), name FROM federated.t1 WHERE id < 5 GROUP BY name; + +SELECT * FROM federated.t1, federated.t2 + WHERE federated.t1.name = federated.t2.name; + +SELECT * FROM federated.t1 LEFT JOIN federated.t2 + ON federated.t1.name = federated.t2.name + WHERE federated.t1.id > 1; + +SELECT * FROM federated.t1 + WHERE id IN (SELECT count(*) FROM federated.t2 GROUP BY name); + +DROP TABLE federated.t1, federated.t2; + +connection slave; +DROP TABLE federated.t1, federated.t2; + +connection default; + +source include/federated_cleanup.inc; diff --git a/sql/CMakeLists.txt b/sql/CMakeLists.txt index f76753a..0c0851e 100644 --- a/sql/CMakeLists.txt +++ b/sql/CMakeLists.txt @@ -96,7 +96,7 @@ SET (SQL_SOURCE sql_partition.cc sql_plugin.cc sql_prepare.cc sql_rename.cc debug_sync.cc sql_repl.cc sql_select.cc sql_show.cc sql_state.c - group_by_handler.cc derived_handler.cc + group_by_handler.cc derived_handler.cc select_handler.cc sql_statistics.cc sql_string.cc lex_string.h sql_table.cc sql_test.cc sql_trigger.cc sql_udf.cc sql_union.cc sql_update.cc sql_view.cc strfunc.cc table.cc thr_malloc.cc diff --git a/sql/handler.h b/sql/handler.h index ce6dd35..346dbd6 100644 --- a/sql/handler.h +++ b/sql/handler.h @@ -1184,6 +1184,7 @@ struct handler_iterator { class handler; class group_by_handler; class derived_handler; +class select_handler; struct Query; typedef class st_select_lex SELECT_LEX; typedef struct st_order ORDER; @@ -1511,6 +1512,12 @@ struct handlerton the function create_group_by has to return NULL. */ derived_handler *(*create_derived)(THD *thd, TABLE_LIST *derived); + + /* + Create and return a select_handler if the storage engine can execute + the select statement 'select, otherwise return NULL + */ + select_handler *(*create_select) (THD *thd, SELECT_LEX *select); /********************************************************************* Table discovery API. diff --git a/sql/select_handler.cc b/sql/select_handler.cc new file mode 100644 index 0000000..f196678 --- /dev/null +++ b/sql/select_handler.cc @@ -0,0 +1,131 @@ +#include "mariadb.h" +#include "sql_priv.h" +#include "sql_select.h" +#include "select_handler.h" + +Pushdown_select::~Pushdown_select() +{ + delete handler; +} + +bool Pushdown_select::init() +{ + List<Item> types; + TMP_TABLE_PARAM tmp_table_param; + THD *thd= handler->thd; + DBUG_ENTER("Pushdown_select::init"); + if (select->master_unit()->join_union_item_types(thd, types, 1)) + DBUG_RETURN(true); + tmp_table_param.init(); + tmp_table_param.field_count= types.elements; + + handler->table= create_tmp_table(thd, &tmp_table_param, types, + (ORDER *) 0, false, 0, + TMP_TABLE_ALL_COLUMNS, 1, + &empty_clex_str, true, false); + if (!handler->table) + DBUG_RETURN(true); + if (handler->table->fill_item_list(&result_columns)) + DBUG_RETURN(true); + DBUG_RETURN(false); +} + +bool Pushdown_select::send_result_set_metadata() +{ + THD *thd= handler->thd; + Protocol *protocol= thd->protocol; + DBUG_ENTER("Pushdown_select::send_result_set_metadata"); + +#ifdef WITH_WSREP + if (WSREP(thd) && thd->wsrep_retry_query) + { + WSREP_DEBUG("skipping select metadata"); + DBUG_RETURN(false); + } + #endif /* WITH_WSREP */ + if (protocol->send_result_set_metadata(&result_columns, + Protocol::SEND_NUM_ROWS | + Protocol::SEND_EOF)) + DBUG_RETURN(true); + + DBUG_RETURN(false); +} + +bool Pushdown_select::send_data() +{ + THD *thd= handler->thd; + Protocol *protocol= thd->protocol; + DBUG_ENTER("Pushdown_select::send_data"); + + if (thd->killed == ABORT_QUERY) + DBUG_RETURN(false); + + protocol->prepare_for_resend(); + if (protocol->send_result_set_row(&result_columns)) + { + protocol->remove_last_row(); + DBUG_RETURN(true); + } + + thd->inc_sent_row_count(1); + + if (thd->vio_ok()) + DBUG_RETURN(protocol->write()); + + DBUG_RETURN(false); +} + +bool Pushdown_select::send_eof() +{ + THD *thd= handler->thd; + DBUG_ENTER("Pushdown_select::send_eof"); + + /* + Don't send EOF if we're in error condition (which implies we've already + sent or are sending an error) + */ + if (thd->is_error()) + DBUG_RETURN(true); + ::my_eof(thd); + DBUG_RETURN(false); +} + +int Pushdown_select::execute() +{ + int err; + THD *thd= handler->thd; + + DBUG_ENTER("Pushdown_select::execute"); + + if ((err= handler->init_scan())) + goto error; + + if (send_result_set_metadata()) + DBUG_RETURN(-1); + + while (!(err= handler->next_row())) + { + if (thd->check_killed() || send_data()) + { + handler->end_scan(); + DBUG_RETURN(-1); + } + } + + if (err != 0 && err != HA_ERR_END_OF_FILE) + goto error; + + if ((err= handler->end_scan())) + goto error_2; + + if (send_eof()) + DBUG_RETURN(-1); + + DBUG_RETURN(0); + +error: + handler->end_scan(); +error_2: + handler->print_error(err, MYF(0)); + DBUG_RETURN(-1); // Error not sent to client +} diff --git a/sql/select_handler.h b/sql/select_handler.h new file mode 100644 index 0000000..68fca03 --- /dev/null +++ b/sql/select_handler.h @@ -0,0 +1,48 @@ +#ifndef SELECT_HANDLER_INCLUDED +#define SELECT_HANDLER_INCLUDED + +#include "mariadb.h" +#include "sql_priv.h" + +class select_handler +{ + public: + THD *thd; + handlerton *ht; + + SELECT_LEX *select; + + /* + Temporary table where all results should be stored in record[0] + The table has a field for every item from the select_lex::item_list. + */ + TABLE *table; + + select_handler(THD *thd_arg, handlerton *ht_arg) + : thd(thd_arg), ht(ht_arg), table(0) {} + + virtual ~select_handler() {} + + /* + Functions to scan the select result set. + All these returns 0 if ok, error code in case of error. + */ + + /* Initialize the process of producing rows of result set */ + virtual int init_scan()= 0; + + /* + Put the next produced row of the result set in table->record[0] + and return 0. Return HA_ERR_END_OF_FILE if there are no more rows, + return other error number in case of fatal error. + */ + virtual int next_row()= 0; + + /* Finish scanning */ + virtual int end_scan()=0; + + /* Report errors */ + virtual void print_error(int error, myf errflag)=0; +}; + +#endif /* SELECT_HANDLER_INCLUDED */ diff --git a/sql/sql_lex.cc b/sql/sql_lex.cc index b309a0a..4c33091 100644 --- a/sql/sql_lex.cc +++ b/sql/sql_lex.cc @@ -2354,6 +2354,7 @@ void st_select_lex::init_query() tvc= 0; in_tvc= false; versioned_tables= 0; + pushdown_select= 0; } void st_select_lex::init_select() @@ -9462,3 +9463,4 @@ bool SELECT_LEX::make_unique_derived_name(THD *thd, LEX_CSTRING *alias) alias->str= thd->strmake(buff, alias->length); return !alias->str; } + diff --git a/sql/sql_lex.h b/sql/sql_lex.h index 2478815..8fa28ff 100644 --- a/sql/sql_lex.h +++ b/sql/sql_lex.h @@ -225,6 +225,8 @@ class Item_window_func; struct sql_digest_state; class With_clause; class my_var; +class select_handler; +class Pushdown_select; #define ALLOC_ROOT_SET 1024 @@ -812,12 +814,13 @@ class st_select_lex_unit: public st_select_lex_node { bool prepare_join(THD *thd, SELECT_LEX *sl, select_result *result, ulong additional_options, bool is_union_select); - bool join_union_item_types(THD *thd, List<Item> &types, uint count); bool join_union_type_handlers(THD *thd, class Type_holder *holders, uint count); bool join_union_type_attributes(THD *thd, class Type_holder *holders, uint count); public: + bool join_union_item_types(THD *thd, List<Item> &types, uint count); +public: // Ensures that at least all members used during cleanup() are initialized. st_select_lex_unit() : union_result(NULL), table(NULL), result(NULL), @@ -1240,6 +1243,9 @@ class st_select_lex: public st_select_lex_node table_value_constr *tvc; bool in_tvc; + select_handler *select_h; + Pushdown_select *pushdown_select; + /** System Versioning */ public: uint versioned_tables; @@ -1471,6 +1477,8 @@ class st_select_lex: public st_select_lex_node Item_transformer transformer, uchar *arg); + select_handler *find_select_handler(THD *thd); + private: bool m_non_agg_field_used; bool m_agg_func_used; diff --git a/sql/sql_select.cc b/sql/sql_select.cc index d0acbef..4ac5ea1 100644 --- a/sql/sql_select.cc +++ b/sql/sql_select.cc @@ -64,6 +64,7 @@ #include "sys_vars_shared.h" #include "sp_head.h" #include "sp_rcontext.h" +#include "select_handler.h" /* A key part number that means we're using a fulltext scan. @@ -1437,7 +1438,12 @@ int JOIN::optimize() { int res= 0; join_optimization_state init_state= optimization_state; - if (optimization_state == JOIN::OPTIMIZATION_PHASE_1_DONE) + if (select_lex->pushdown_select) + { + res= select_lex->pushdown_select->init(); + with_two_phase_optimization= false; + } + else if (optimization_state == JOIN::OPTIMIZATION_PHASE_1_DONE) res= optimize_stage2(); else { @@ -3935,6 +3941,12 @@ void JOIN::exec_inner() select_describe(this, FALSE, FALSE, FALSE, (zero_result_cause?zero_result_cause:"No tables used")); + else if (select_lex->pushdown_select) + { + error= select_lex->pushdown_select->execute(); + delete select_lex->pushdown_select; + DBUG_VOID_RETURN; + } else { if (result->send_result_set_metadata(*columns_list, @@ -4033,7 +4045,8 @@ void JOIN::exec_inner() not the case. */ if (exec_const_order_group_cond.elements && - !(select_options & SELECT_DESCRIBE)) + !(select_options & SELECT_DESCRIBE) && + !select_lex->pushdown_select) { List_iterator_fast<Item> const_item_it(exec_const_order_group_cond); Item *cur_const_item; @@ -4060,6 +4073,12 @@ void JOIN::exec_inner() !table_count ? "No tables used" : NullS); DBUG_VOID_RETURN; } + else if (select_lex->pushdown_select) + { + error= select_lex->pushdown_select->execute(); + delete select_lex->pushdown_select; + DBUG_VOID_RETURN; + } else { /* it's a const select, materialize it. */ @@ -4271,6 +4290,15 @@ mysql_select(THD *thd, } } + select_lex->select_h= select_lex->find_select_handler(thd); + if (select_lex->select_h) + { + if (!(select_lex->pushdown_select= + new (thd->mem_root) Pushdown_select(select_lex, + select_lex->select_h))) + DBUG_RETURN(TRUE); + } + if ((err= join->optimize())) { goto err; // 1 @@ -27371,6 +27399,26 @@ Item *remove_pushed_top_conjuncts(THD *thd, Item *cond) return cond; } +select_handler *SELECT_LEX::find_select_handler(THD *thd) +{ + if (next_select()) + return 0; + if (master_unit()->outer_select()) + return 0; + for (TABLE_LIST *tbl= join->tables_list; tbl; tbl= tbl->next_local) + { + if (!tbl->table) + continue; + handlerton *ht= tbl->table->file->partition_ht(); + if (!ht->create_select) + continue; + select_handler *sh= ht->create_select(thd, this); + return sh; + } + return 0; +} + + /** @} (end of group Query_Optimizer) */ diff --git a/sql/sql_select.h b/sql/sql_select.h index e51367c..e9cf51b 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -2461,6 +2461,33 @@ class Pushdown_derived: public Sql_alloc int execute(); }; + +class select_handler; + + +class Pushdown_select: public Sql_alloc +{ +private: + List<Item> result_columns; + bool send_result_set_metadata(); + bool send_data(); + bool send_eof(); + +public: + SELECT_LEX *select; + select_handler *handler; + + Pushdown_select(SELECT_LEX *sel, select_handler *h) + : select(sel), handler(h) {} + + ~Pushdown_select(); + + bool init(); + + int execute(); +}; + + bool test_if_order_compatible(SQL_I_List<ORDER> &a, SQL_I_List<ORDER> &b); int test_if_group_changed(List<Cached_item> &list); int create_sort_index(THD *thd, JOIN *join, JOIN_TAB *tab, Filesort *fsort); diff --git a/storage/federatedx/ha_federatedx.cc b/storage/federatedx/ha_federatedx.cc index 45cd14e..ec96a24 100644 --- a/storage/federatedx/ha_federatedx.cc +++ b/storage/federatedx/ha_federatedx.cc @@ -406,6 +406,8 @@ handlerton* federatedx_hton; static derived_handler* create_federatedx_derived_handler(THD* thd, TABLE_LIST *derived); +static select_handler* +create_federatedx_select_handler(THD* thd, SELECT_LEX *sel); /* Initialize the federatedx handler. @@ -438,6 +440,7 @@ int federatedx_db_init(void *p) federatedx_hton->create= federatedx_create_handler; federatedx_hton->flags= HTON_ALTER_NOT_SUPPORTED; federatedx_hton->create_derived= create_federatedx_derived_handler; + federatedx_hton->create_select= create_federatedx_select_handler; if (mysql_mutex_init(fe_key_mutex_federatedx, &federatedx_mutex, MY_MUTEX_INIT_FAST)) @@ -3795,6 +3798,125 @@ void ha_federatedx_derived_handler::print_error(int, unsigned long) { } + +static select_handler* +create_federatedx_select_handler(THD* thd, SELECT_LEX *sel) +{ + ha_federatedx_select_handler* handler = NULL; + handlerton *ht= 0; + + for (TABLE_LIST *tbl= thd->lex->query_tables; tbl; tbl= tbl->next_global) + { + if (!tbl->table) + return 0; + if (!ht) + ht= tbl->table->file->partition_ht(); + else if (ht != tbl->table->file->partition_ht()) + return 0; + } + + handler= new ha_federatedx_select_handler(thd, sel); + + return handler; +} + +ha_federatedx_select_handler::ha_federatedx_select_handler(THD *thd, + SELECT_LEX *sel) + : select_handler(thd, federatedx_hton) +{ + select= sel; +} + +ha_federatedx_select_handler::~ha_federatedx_select_handler() {} + +int ha_federatedx_select_handler::init_scan() +{ + int rc= 0; + + DBUG_ENTER("ha_federatedx_select_handler::init_scan"); + + TABLE *table= 0; + for (TABLE_LIST *tbl= thd->lex->query_tables; tbl; tbl= tbl->next_global) + { + if (!tbl->table) + continue; + table= tbl->table; + break; + } + ha_federatedx *h= (ha_federatedx *) table->file; + io= h->io; + share= get_share(table->s->table_name.str, table); + txn= h->get_txn(thd); + if ((rc= txn->acquire(share, thd, TRUE, &io))) + DBUG_RETURN(rc); + + if (io->query(thd->query(), thd->query_length())) + goto err; + + stored_result= io->store_result(); + if (!stored_result) + goto err; + + DBUG_RETURN(0); + +err: + DBUG_RETURN(HA_FEDERATEDX_ERROR_WITH_REMOTE_SYSTEM); +} + +int ha_federatedx_select_handler::next_row() +{ + int rc; + FEDERATEDX_IO_ROW *row; + ulong *lengths; + Field **field; + int column= 0; + Time_zone *saved_time_zone= table->in_use->variables.time_zone; + DBUG_ENTER("ha_federatedx_select_handler::next_row"); + + if ((rc= txn->acquire(share, table->in_use, TRUE, &io))) + DBUG_RETURN(rc); + + if (!(row= io->fetch_row(stored_result))) + DBUG_RETURN(HA_ERR_END_OF_FILE); + + /* Convert row to internal format */ + table->in_use->variables.time_zone= UTC; + lengths= io->fetch_lengths(stored_result); + + for (field= table->field; *field; field++, column++) + { + if (io->is_column_null(row, column)) + (*field)->set_null(); + else + { + (*field)->set_notnull(); + (*field)->store(io->get_column_data(row, column), + lengths[column], &my_charset_bin); + } + } + table->in_use->variables.time_zone= saved_time_zone; + + DBUG_RETURN(rc); +} + +int ha_federatedx_select_handler::end_scan() +{ + DBUG_ENTER("ha_federatedx_derived_handler::end_scan"); + + free_tmp_table(thd, table); + table= 0; + + txn->release(&io); + DBUG_ASSERT(io == NULL); + + DBUG_RETURN(0); +} + +void ha_federatedx_select_handler::print_error(int, unsigned long) +{ +} + + struct st_mysql_storage_engine federatedx_storage_engine= { MYSQL_HANDLERTON_INTERFACE_VERSION }; diff --git a/storage/federatedx/ha_federatedx.h b/storage/federatedx/ha_federatedx.h index 61c7029..4c721e5 100644 --- a/storage/federatedx/ha_federatedx.h +++ b/storage/federatedx/ha_federatedx.h @@ -43,6 +43,7 @@ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. #include <thr_lock.h> #include "handler.h" #include "derived_handler.h" +#include "select_handler.h" class federatedx_io; @@ -450,6 +451,7 @@ class ha_federatedx: public handler int free_result(void); friend class ha_federatedx_derived_handler; + friend class ha_federatedx_select_handler; }; extern const char ident_quote_char; // Character for quoting @@ -483,4 +485,22 @@ class ha_federatedx_derived_handler: public derived_handler void print_error(int, unsigned long); }; + +class ha_federatedx_select_handler: public select_handler +{ +private: + FEDERATEDX_SHARE *share; + federatedx_txn *txn; + federatedx_io *io; + FEDERATEDX_IO_RESULT *stored_result; + +public: + ha_federatedx_select_handler(THD* thd_arg, SELECT_LEX *sel); + ~ha_federatedx_select_handler(); + int init_scan(); + int next_row(); + int end_scan(); + void print_error(int, unsigned long); +}; + #endif /* HA_FEDERATEDX_INCLUDED */

1 0

[Commits] 12d09c1a4a8: MDEV-18369: Crash at wsrep_handle_SR_rollback(THD*, THD*): Assertion `victim_thd' failed.
by jan 25 Jan '19

25 Jan '19

revision-id: 12d09c1a4a8917d345bfd0645d5f6767a4bedcca (mariadb-10.4.1-111-g12d09c1a4a8) parent(s): c3a1cd35554fb9bbd5b2086516678d2b7a7b1e48 author: Jan Lindström committer: Jan Lindström timestamp: 2019-01-25 07:56:57 +0200 message: MDEV-18369: Crash at wsrep_handle_SR_rollback(THD*, THD*): Assertion `victim_thd' failed. Call to wsrep_handle_SR_rollback was missing check that wsrep_on is true. --- storage/innobase/lock/lock0lock.cc | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) diff --git a/storage/innobase/lock/lock0lock.cc b/storage/innobase/lock/lock0lock.cc index 493f73cc148..a8877ab8a33 100644 --- a/storage/innobase/lock/lock0lock.cc +++ b/storage/innobase/lock/lock0lock.cc @@ -1,7 +1,7 @@ /***************************************************************************** Copyright (c) 1996, 2017, Oracle and/or its affiliates. All Rights Reserved. -Copyright (c) 2014, 2018, MariaDB Corporation. +Copyright (c) 2014, 2019, MariaDB Corporation. 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 @@ -6995,7 +6995,9 @@ DeadlockChecker::trx_rollback() print("*** WE ROLL BACK TRANSACTION (1)\n"); #ifdef WITH_WSREP - wsrep_handle_SR_rollback(m_start->mysql_thd, trx->mysql_thd); + if (wsrep_on(trx->mysql_thd)) { + wsrep_handle_SR_rollback(m_start->mysql_thd, trx->mysql_thd); + } #endif trx_mutex_enter(trx);

1 0

[Commits] 3262afc6c50: 5.6.42-84.2
by Oleksandr Byelkin 24 Jan '19

24 Jan '19

revision-id: 3262afc6c50bdee489dd35feb8c5254dbc93494b (release-5-103-g3262afc6c50) parent(s): bbcb1734365b0e81d7d82e1d3d9e37074048970e author: Oleksandr Byelkin committer: Oleksandr Byelkin timestamp: 2019-01-24 16:48:39 +0100 message: 5.6.42-84.2 --- storage/xtradb/handler/ha_innodb.cc | 5 ++++ storage/xtradb/handler/handler0alter.cc | 35 ++++++++++++++++++++++------ storage/xtradb/include/os0file.h | 6 ++++- storage/xtradb/include/univ.i | 2 +- storage/xtradb/log/log0online.cc | 41 ++++++++++++++++++++++++++++++++- storage/xtradb/row/row0merge.cc | 17 ++++++++++++-- storage/xtradb/row/row0mysql.cc | 15 +++--------- storage/xtradb/row/row0sel.cc | 4 ++-- 8 files changed, 99 insertions(+), 26 deletions(-) diff --git a/storage/xtradb/handler/ha_innodb.cc b/storage/xtradb/handler/ha_innodb.cc index 053a181e26c..1ff50136859 100644 --- a/storage/xtradb/handler/ha_innodb.cc +++ b/storage/xtradb/handler/ha_innodb.cc @@ -2322,6 +2322,11 @@ innobase_get_lower_case_table_names(void) { return(lower_case_table_names); } +/** return one of the tmpdir path +@return tmpdir path*/ +UNIV_INTERN +char* +innobase_mysql_tmpdir(void) { return (mysql_tmpdir); } /** Create a temporary file in the location specified by the parameter path. If the path is null, then it will be created in tmpdir. diff --git a/storage/xtradb/handler/handler0alter.cc b/storage/xtradb/handler/handler0alter.cc index 517dd30410b..856f8bac8de 100644 --- a/storage/xtradb/handler/handler0alter.cc +++ b/storage/xtradb/handler/handler0alter.cc @@ -4056,11 +4056,23 @@ oom: table. Either way, we should be seeing and reporting a bogus duplicate key error. */ dup_key = NULL; - } else { - DBUG_ASSERT(prebuilt->trx->error_key_num - < ha_alter_info->key_count); + } else if (prebuilt->trx->error_key_num == 0) { dup_key = &ha_alter_info->key_info_buffer[ prebuilt->trx->error_key_num]; + } else { + /* Check if there is generated cluster index column */ + if (ctx->num_to_add_index > ha_alter_info->key_count) { + DBUG_ASSERT(prebuilt->trx->error_key_num + <= ha_alter_info->key_count); + dup_key = &ha_alter_info->key_info_buffer[ + prebuilt->trx->error_key_num - 1]; + } + else { + DBUG_ASSERT(prebuilt->trx->error_key_num + < ha_alter_info->key_count); + dup_key = &ha_alter_info->key_info_buffer[ + prebuilt->trx->error_key_num]; + } } print_keydup_error(altered_table, dup_key, MYF(0)); break; @@ -4981,11 +4993,20 @@ commit_try_rebuild( FTS_DOC_ID. */ dup_key = NULL; } else { - DBUG_ASSERT(err_key < - ha_alter_info->key_count); - dup_key = &ha_alter_info - ->key_info_buffer[err_key]; + if (ctx->num_to_add_index > ha_alter_info->key_count) { + DBUG_ASSERT(err_key <= + ha_alter_info->key_count); + dup_key = &ha_alter_info + ->key_info_buffer[err_key - 1]; + } + else { + DBUG_ASSERT(err_key < + ha_alter_info->key_count); + dup_key = &ha_alter_info + ->key_info_buffer[err_key]; + } } + print_keydup_error(altered_table, dup_key, MYF(0)); DBUG_RETURN(true); case DB_ONLINE_LOG_TOO_BIG: diff --git a/storage/xtradb/include/os0file.h b/storage/xtradb/include/os0file.h index f7531d99f38..bc7e468b776 100644 --- a/storage/xtradb/include/os0file.h +++ b/storage/xtradb/include/os0file.h @@ -1,6 +1,6 @@ /*********************************************************************** -Copyright (c) 1995, 2017, Oracle and/or its affiliates. All Rights Reserved. +Copyright (c) 1995, 2018, Oracle and/or its affiliates. All Rights Reserved. Copyright (c) 2009, Percona Inc. Portions of this file contain modifications contributed and copyrighted @@ -1531,6 +1531,10 @@ os_file_get_status( file can be opened in RW mode */ #if !defined(UNIV_HOTBACKUP) + +/** return one of the tmpdir path + @return tmpdir path*/ +char *innobase_mysql_tmpdir(void); /** Create a temporary file in the location specified by the parameter path. If the path is null, then it will be created in tmpdir. @param[in] path location for creating temporary file diff --git a/storage/xtradb/include/univ.i b/storage/xtradb/include/univ.i index f625ea46433..4904e174b87 100644 --- a/storage/xtradb/include/univ.i +++ b/storage/xtradb/include/univ.i @@ -47,7 +47,7 @@ Created 1/20/1994 Heikki Tuuri #define INNODB_VERSION_BUGFIX MYSQL_VERSION_PATCH #ifndef PERCONA_INNODB_VERSION -#define PERCONA_INNODB_VERSION 84.1 +#define PERCONA_INNODB_VERSION 84.2 #endif /* Enable UNIV_LOG_ARCHIVE in XtraDB */ diff --git a/storage/xtradb/log/log0online.cc b/storage/xtradb/log/log0online.cc index e3cfbfc2088..a3d76e79b2a 100644 --- a/storage/xtradb/log/log0online.cc +++ b/storage/xtradb/log/log0online.cc @@ -1880,6 +1880,8 @@ log_online_purge_changed_page_bitmaps( for (i = 0; i < bitmap_files.count; i++) { + char full_bmp_file_name[2 * FN_REFLEN + 2]; + /* We consider the end LSN of the current bitmap, derived from the start LSN of the subsequent bitmap file, to determine whether to remove the current bitmap. Note that bitmap_files @@ -1895,8 +1897,45 @@ log_online_purge_changed_page_bitmaps( break; } + + /* In some non-trivial cases the sequence of .xdb files may + have gaps. For instance: + ib_modified_log_1_0.xdb + ib_modified_log_2_<mmm>.xdb + ib_modified_log_4_<nnn>.xdb + Adding this check as a safety precaution. */ + if (bitmap_files.files[i].name[0] == '\0') + continue; + + /* If redo log tracking is enabled, reuse 'bmp_file_home' + from 'log_bmp_sys'. Otherwise, compose the full '.xdb' file + path from 'srv_data_home', adding a path separator if + necessary. */ + if (log_bmp_sys != NULL) { + ut_snprintf(full_bmp_file_name, + sizeof(full_bmp_file_name), + "%s%s", log_bmp_sys->bmp_file_home, + bitmap_files.files[i].name); + } + else { + char separator[2] = {0, 0}; + const size_t srv_data_home_len = + strlen(srv_data_home); + + ut_a(srv_data_home_len < FN_REFLEN); + if (srv_data_home_len != 0 && + srv_data_home[srv_data_home_len - 1] != + SRV_PATH_SEPARATOR) { + separator[0] = SRV_PATH_SEPARATOR; + } + ut_snprintf(full_bmp_file_name, + sizeof(full_bmp_file_name), "%s%s%s", + srv_data_home, separator, + bitmap_files.files[i].name); + } + if (!os_file_delete_if_exists(innodb_file_bmp_key, - bitmap_files.files[i].name)) { + full_bmp_file_name)) { os_file_get_last_error(TRUE); result = TRUE; diff --git a/storage/xtradb/row/row0merge.cc b/storage/xtradb/row/row0merge.cc index b000f313d67..507709ce12b 100644 --- a/storage/xtradb/row/row0merge.cc +++ b/storage/xtradb/row/row0merge.cc @@ -1,6 +1,6 @@ /***************************************************************************** -Copyright (c) 2005, 2017, Oracle and/or its affiliates. All Rights Reserved. +Copyright (c) 2005, 2018, 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 the Free Software @@ -3129,15 +3129,27 @@ row_merge_file_create_low( const char* path) { int fd; + char filename[] = "Innodb Merge Temp File\0"; + char* filepath = NULL; + int path_len; + if (path == NULL) { + path = innobase_mysql_tmpdir(); + } #ifdef UNIV_PFS_IO /* This temp file open does not go through normal file APIs, add instrumentation to register with performance schema */ + path_len = strlen(path) + sizeof "/" + strlen(filename)+1; + filepath = static_cast<char*>(mem_alloc(path_len)); + memcpy(filepath,path,strlen(path)); + ut_snprintf(filepath + strlen(path),path_len - strlen(path), + "%c%s",'/',filename); struct PSI_file_locker* locker = NULL; + PSI_file_locker_state state; locker = PSI_FILE_CALL(get_thread_file_name_locker)( &state, innodb_file_temp_key, PSI_FILE_OPEN, - "Innodb Merge Temp File", &locker); + filepath, &locker); if (locker != NULL) { PSI_FILE_CALL(start_file_open_wait)(locker, __FILE__, @@ -3150,6 +3162,7 @@ row_merge_file_create_low( PSI_FILE_CALL(end_file_open_wait_and_bind_to_descriptor)( locker, fd); } + mem_free(filepath); #endif if (fd < 0) { diff --git a/storage/xtradb/row/row0mysql.cc b/storage/xtradb/row/row0mysql.cc index ddde8b8f730..9fc5c669ba0 100644 --- a/storage/xtradb/row/row0mysql.cc +++ b/storage/xtradb/row/row0mysql.cc @@ -5500,18 +5500,6 @@ row_rename_table_for_mysql( goto funct_exit; } - /* Wait for background fts sync to finish */ - for (retry = 1; dict_fts_index_syncing(table); ++retry) { - DICT_BG_YIELD(trx); - if (retry % 100 == 0) { - ib_logf(IB_LOG_LEVEL_INFO, - "Unable to rename table %s to new name" - " %s because FTS sync is running on table." - " Retrying\n", - old_name, new_name); - } - } - /* We use the private SQL parser of Innobase to generate the query graphs needed in updating the dictionary data from system tables. */ @@ -5669,6 +5657,9 @@ row_rename_table_for_mysql( " = TO_BINARY(:old_table_name);\n" "END;\n" , FALSE, trx); + if (err != DB_SUCCESS) { + goto end; + } } else if (n_constraints_to_drop > 0) { /* Drop some constraints of tmp tables. */ diff --git a/storage/xtradb/row/row0sel.cc b/storage/xtradb/row/row0sel.cc index 5db61ecdd56..0edad710d79 100644 --- a/storage/xtradb/row/row0sel.cc +++ b/storage/xtradb/row/row0sel.cc @@ -1,6 +1,6 @@ /***************************************************************************** -Copyright (c) 1997, 2017, Oracle and/or its affiliates. All Rights Reserved. +Copyright (c) 1997, 2018, Oracle and/or its affiliates. All Rights Reserved. Copyright (c) 2008, Google Inc. Portions of this file contain modifications contributed and copyrighted by @@ -4416,7 +4416,7 @@ rec_loop: passed to InnoDB when there is no ICP and number of loops in row_search_for_mysql for rows found but not reporting due to search views etc. */ - if (prev_rec != NULL + if (prev_rec != NULL && !prebuilt->innodb_api && prebuilt->mysql_handler->end_range != NULL && prebuilt->idx_cond == NULL && end_loop >= 100) {

2 1

[Commits] 13802fef831: 5.6.42-84.2
by Oleksandr Byelkin 24 Jan '19

24 Jan '19

revision-id: 13802fef831790c4b63a3ddbf96e516eff422464 () parent(s): a816eac92ac2381e1b9cd4d655e733bdeafb173e author: Oleksandr Byelkin committer: Oleksandr Byelkin timestamp: 2019-01-24 17:31:13 +0100 message: 5.6.42-84.2 --- storage/tokudb/PerconaFT/COPYING.APACHEv2 | 174 ++ storage/tokudb/PerconaFT/README.md | 5 +- storage/tokudb/PerconaFT/ft/txn/txn_manager.h | 4 +- .../tokudb/PerconaFT/locktree/concurrent_tree.cc | 14 + .../tokudb/PerconaFT/locktree/concurrent_tree.h | 14 + storage/tokudb/PerconaFT/locktree/keyrange.cc | 13 + storage/tokudb/PerconaFT/locktree/keyrange.h | 13 + storage/tokudb/PerconaFT/locktree/lock_request.cc | 13 + storage/tokudb/PerconaFT/locktree/lock_request.h | 13 + storage/tokudb/PerconaFT/locktree/locktree.cc | 13 + storage/tokudb/PerconaFT/locktree/locktree.h | 13 + storage/tokudb/PerconaFT/locktree/manager.cc | 13 + storage/tokudb/PerconaFT/locktree/range_buffer.cc | 13 + storage/tokudb/PerconaFT/locktree/range_buffer.h | 13 + storage/tokudb/PerconaFT/locktree/treenode.cc | 13 + storage/tokudb/PerconaFT/locktree/treenode.h | 13 + storage/tokudb/PerconaFT/locktree/txnid_set.cc | 13 + storage/tokudb/PerconaFT/locktree/txnid_set.h | 13 + storage/tokudb/PerconaFT/locktree/wfg.cc | 13 + storage/tokudb/PerconaFT/locktree/wfg.h | 13 + .../PerconaFT/portability/toku_instr_mysql.cc | 12 +- .../PerconaFT/portability/toku_instr_mysql.h | 11 +- .../tokudb/PerconaFT/portability/toku_pthread.h | 78 +- storage/tokudb/PerconaFT/tools/CMakeLists.txt | 8 +- storage/tokudb/PerconaFT/util/growable_array.h | 13 + storage/tokudb/PerconaFT/util/omt.cc | 2261 +++++++++++--------- storage/tokudb/PerconaFT/util/omt.h | 13 + storage/tokudb/ha_tokudb.cc | 10 + storage/tokudb/hatoku_hton.cc | 4 +- storage/tokudb/hatoku_hton.h | 1 - .../tokudb/mysql-test/tokudb_bugs/r/PS-4979.result | 2 + .../tokudb/mysql-test/tokudb_bugs/t/PS-4979.test | 12 + storage/tokudb/tokudb_background.cc | 4 +- storage/tokudb/tokudb_sysvars.cc | 14 +- storage/tokudb/tokudb_sysvars.h | 4 +- 35 files changed, 1778 insertions(+), 1075 deletions(-) diff --git a/storage/tokudb/PerconaFT/COPYING.APACHEv2 b/storage/tokudb/PerconaFT/COPYING.APACHEv2 new file mode 100644 index 00000000000..ecbfc770fa9 --- /dev/null +++ b/storage/tokudb/PerconaFT/COPYING.APACHEv2 @@ -0,0 +1,174 @@ +Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + + TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + + 1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + + 2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + + 3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + + 4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + + 5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + + 6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + + 7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + + 8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + + 9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. diff --git a/storage/tokudb/PerconaFT/README.md b/storage/tokudb/PerconaFT/README.md index ffb646b67af..26333df877e 100644 --- a/storage/tokudb/PerconaFT/README.md +++ b/storage/tokudb/PerconaFT/README.md @@ -104,11 +104,14 @@ All source code and test contributions must be provided under a [BSD 2-Clause][b License ------- +Portions of the PerconaFT library (the 'locktree' and 'omt') are available under the Apache version 2 license. PerconaFT is available under the GPL version 2, and AGPL version 3. -See [COPYING.AGPLv3][agpllicense], +See [COPYING.APACHEv2][apachelicense], +[COPYING.AGPLv3][agpllicense], [COPYING.GPLv2][gpllicense], and [PATENTS][patents]. +[apachelicense]: http://github.com/Percona/PerconaFT/blob/master/COPYING.APACHEv2 [agpllicense]: http://github.com/Percona/PerconaFT/blob/master/COPYING.AGPLv3 [gpllicense]: http://github.com/Percona/PerconaFT/blob/master/COPYING.GPLv2 [patents]: http://github.com/Percona/PerconaFT/blob/master/PATENTS diff --git a/storage/tokudb/PerconaFT/ft/txn/txn_manager.h b/storage/tokudb/PerconaFT/ft/txn/txn_manager.h index 7cdc52c4f43..25fa6032112 100644 --- a/storage/tokudb/PerconaFT/ft/txn/txn_manager.h +++ b/storage/tokudb/PerconaFT/ft/txn/txn_manager.h @@ -46,11 +46,11 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. void set_test_txn_sync_callback(void (*) (pthread_t, void*), void*); #define toku_test_txn_sync_callback(a) ((test_txn_sync_callback)? test_txn_sync_callback( a,test_txn_sync_callback_extra) : (void) 0) -#if TOKU_DEBUG_TXN_SYNC +#if defined(TOKU_DEBUG_TXN_SYNC) #define toku_debug_txn_sync(a) toku_test_txn_sync_callback(a) #else #define toku_debug_txn_sync(a) ((void) 0) -#endif +#endif // defined(TOKU_DEBUG_TXN_SYNC) typedef struct txn_manager *TXN_MANAGER; diff --git a/storage/tokudb/PerconaFT/locktree/concurrent_tree.cc b/storage/tokudb/PerconaFT/locktree/concurrent_tree.cc index 9347267db49..e07f32c98fb 100644 --- a/storage/tokudb/PerconaFT/locktree/concurrent_tree.cc +++ b/storage/tokudb/PerconaFT/locktree/concurrent_tree.cc @@ -32,6 +32,20 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/concurrent_tree.h b/storage/tokudb/PerconaFT/locktree/concurrent_tree.h index 1eb339b7317..66a7ff176bb 100644 --- a/storage/tokudb/PerconaFT/locktree/concurrent_tree.h +++ b/storage/tokudb/PerconaFT/locktree/concurrent_tree.h @@ -32,6 +32,20 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/keyrange.cc b/storage/tokudb/PerconaFT/locktree/keyrange.cc index 8c2a69d4703..2b4b3bbd4fd 100644 --- a/storage/tokudb/PerconaFT/locktree/keyrange.cc +++ b/storage/tokudb/PerconaFT/locktree/keyrange.cc @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/keyrange.h b/storage/tokudb/PerconaFT/locktree/keyrange.h index 079ac3d7a80..a454287cbc8 100644 --- a/storage/tokudb/PerconaFT/locktree/keyrange.h +++ b/storage/tokudb/PerconaFT/locktree/keyrange.h @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/lock_request.cc b/storage/tokudb/PerconaFT/locktree/lock_request.cc index 8d49ccf8a1f..3d4d43b9e25 100644 --- a/storage/tokudb/PerconaFT/locktree/lock_request.cc +++ b/storage/tokudb/PerconaFT/locktree/lock_request.cc @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/lock_request.h b/storage/tokudb/PerconaFT/locktree/lock_request.h index a8d8cb7785b..91a6ff12b52 100644 --- a/storage/tokudb/PerconaFT/locktree/lock_request.h +++ b/storage/tokudb/PerconaFT/locktree/lock_request.h @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/locktree.cc b/storage/tokudb/PerconaFT/locktree/locktree.cc index 069aae26f66..8ba3f0f00ae 100644 --- a/storage/tokudb/PerconaFT/locktree/locktree.cc +++ b/storage/tokudb/PerconaFT/locktree/locktree.cc @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/locktree.h b/storage/tokudb/PerconaFT/locktree/locktree.h index 1ba7a51b124..7006b6fb01d 100644 --- a/storage/tokudb/PerconaFT/locktree/locktree.h +++ b/storage/tokudb/PerconaFT/locktree/locktree.h @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/manager.cc b/storage/tokudb/PerconaFT/locktree/manager.cc index 6bb5c77bf32..21f8dc6cf01 100644 --- a/storage/tokudb/PerconaFT/locktree/manager.cc +++ b/storage/tokudb/PerconaFT/locktree/manager.cc @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/range_buffer.cc b/storage/tokudb/PerconaFT/locktree/range_buffer.cc index 3ddfd0faf97..d1f14fc4a52 100644 --- a/storage/tokudb/PerconaFT/locktree/range_buffer.cc +++ b/storage/tokudb/PerconaFT/locktree/range_buffer.cc @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/range_buffer.h b/storage/tokudb/PerconaFT/locktree/range_buffer.h index b0e36968e73..811b0f85e69 100644 --- a/storage/tokudb/PerconaFT/locktree/range_buffer.h +++ b/storage/tokudb/PerconaFT/locktree/range_buffer.h @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/treenode.cc b/storage/tokudb/PerconaFT/locktree/treenode.cc index cc3a4969643..0247242f975 100644 --- a/storage/tokudb/PerconaFT/locktree/treenode.cc +++ b/storage/tokudb/PerconaFT/locktree/treenode.cc @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/treenode.h b/storage/tokudb/PerconaFT/locktree/treenode.h index 08aad2b6636..981e8b5a9cf 100644 --- a/storage/tokudb/PerconaFT/locktree/treenode.h +++ b/storage/tokudb/PerconaFT/locktree/treenode.h @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/txnid_set.cc b/storage/tokudb/PerconaFT/locktree/txnid_set.cc index 82b59453156..bd4e9723155 100644 --- a/storage/tokudb/PerconaFT/locktree/txnid_set.cc +++ b/storage/tokudb/PerconaFT/locktree/txnid_set.cc @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/txnid_set.h b/storage/tokudb/PerconaFT/locktree/txnid_set.h index 109d7f798e4..81fd45b6dde 100644 --- a/storage/tokudb/PerconaFT/locktree/txnid_set.h +++ b/storage/tokudb/PerconaFT/locktree/txnid_set.h @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/wfg.cc b/storage/tokudb/PerconaFT/locktree/wfg.cc index 9a234f50060..26b7a3b5295 100644 --- a/storage/tokudb/PerconaFT/locktree/wfg.cc +++ b/storage/tokudb/PerconaFT/locktree/wfg.cc @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/wfg.h b/storage/tokudb/PerconaFT/locktree/wfg.h index c56886e1362..5c1599592e6 100644 --- a/storage/tokudb/PerconaFT/locktree/wfg.h +++ b/storage/tokudb/PerconaFT/locktree/wfg.h @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/portability/toku_instr_mysql.cc b/storage/tokudb/PerconaFT/portability/toku_instr_mysql.cc index 6f69c3c31b9..b5305ffaff4 100644 --- a/storage/tokudb/PerconaFT/portability/toku_instr_mysql.cc +++ b/storage/tokudb/PerconaFT/portability/toku_instr_mysql.cc @@ -184,9 +184,9 @@ void toku_instr_file_io_end(toku_io_instrumentation &io_instr, ssize_t count) { void toku_instr_mutex_init(const toku_instr_key &key, toku_mutex_t &mutex) { mutex.psi_mutex = PSI_MUTEX_CALL(init_mutex)(key.id(), &mutex.pmutex); -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) mutex.instr_key_id = key.id(); -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) } void toku_instr_mutex_destroy(PSI_mutex *&mutex_instr) { @@ -242,9 +242,9 @@ void toku_instr_mutex_unlock(PSI_mutex *mutex_instr) { void toku_instr_cond_init(const toku_instr_key &key, toku_cond_t &cond) { cond.psi_cond = PSI_COND_CALL(init_cond)(key.id(), &cond.pcond); -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) cond.instr_key_id = key.id(); -#endif +#endif // // defined(TOKU_PTHREAD_DEBUG) } void toku_instr_cond_destroy(PSI_cond *&cond_instr) { @@ -295,9 +295,9 @@ void toku_instr_cond_broadcast(const toku_cond_t &cond) { void toku_instr_rwlock_init(const toku_instr_key &key, toku_pthread_rwlock_t &rwlock) { rwlock.psi_rwlock = PSI_RWLOCK_CALL(init_rwlock)(key.id(), &rwlock.rwlock); -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) rwlock.instr_key_id = key.id(); -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) } void toku_instr_rwlock_destroy(PSI_rwlock *&rwlock_instr) { diff --git a/storage/tokudb/PerconaFT/portability/toku_instr_mysql.h b/storage/tokudb/PerconaFT/portability/toku_instr_mysql.h index d6b0ed35ce9..695624acd6d 100644 --- a/storage/tokudb/PerconaFT/portability/toku_instr_mysql.h +++ b/storage/tokudb/PerconaFT/portability/toku_instr_mysql.h @@ -12,8 +12,15 @@ // undefine them here to avoid compilation errors. #undef __STDC_FORMAT_MACROS #undef __STDC_LIMIT_MACROS -#include <mysql/psi/mysql_file.h> // PSI_file -#include <mysql/psi/mysql_thread.h> // PSI_mutex +#include "mysql/psi/mysql_file.h" // PSI_file +#include "mysql/psi/mysql_thread.h" // PSI_mutex +#include "mysql/psi/mysql_stage.h" // PSI_stage + +#if (MYSQL_VERSION_ID >= 80000) +#include "mysql/psi/mysql_cond.h" +#include "mysql/psi/mysql_mutex.h" +#include "mysql/psi/mysql_rwlock.h" +#endif // (MYSQL_VERSION_ID >= nn) #ifndef HAVE_PSI_MUTEX_INTERFACE #error HAVE_PSI_MUTEX_INTERFACE required diff --git a/storage/tokudb/PerconaFT/portability/toku_pthread.h b/storage/tokudb/PerconaFT/portability/toku_pthread.h index e3bd3bce598..da956097d05 100644 --- a/storage/tokudb/PerconaFT/portability/toku_pthread.h +++ b/storage/tokudb/PerconaFT/portability/toku_pthread.h @@ -64,23 +64,23 @@ struct toku_mutex_t { pthread_mutex_t pmutex; struct PSI_mutex *psi_mutex; /* The performance schema instrumentation hook */ -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) pthread_t owner; // = pthread_self(); // for debugging bool locked; bool valid; pfs_key_t instr_key_id; -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) }; struct toku_cond_t { pthread_cond_t pcond; struct PSI_cond *psi_cond; -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) pfs_key_t instr_key_id; -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) }; -#ifdef TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) #define TOKU_COND_INITIALIZER \ { \ .pcond = PTHREAD_COND_INITIALIZER, .psi_cond = nullptr, \ @@ -89,14 +89,14 @@ struct toku_cond_t { #else #define TOKU_COND_INITIALIZER \ { .pcond = PTHREAD_COND_INITIALIZER, .psi_cond = nullptr } -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) struct toku_pthread_rwlock_t { pthread_rwlock_t rwlock; struct PSI_rwlock *psi_rwlock; -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) pfs_key_t instr_key_id; -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) }; typedef struct toku_mutex_aligned { @@ -117,7 +117,7 @@ typedef struct toku_mutex_aligned { #define ZERO_MUTEX_INITIALIZER \ {} -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) #define TOKU_MUTEX_INITIALIZER \ { \ .pmutex = PTHREAD_MUTEX_INITIALIZER, .psi_mutex = nullptr, .owner = 0, \ @@ -126,12 +126,12 @@ typedef struct toku_mutex_aligned { #else #define TOKU_MUTEX_INITIALIZER \ { .pmutex = PTHREAD_MUTEX_INITIALIZER, .psi_mutex = nullptr } -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) // Darwin doesn't provide adaptive mutexes #if defined(__APPLE__) #define TOKU_MUTEX_ADAPTIVE PTHREAD_MUTEX_DEFAULT -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) #define TOKU_ADAPTIVE_MUTEX_INITIALIZER \ { \ .pmutex = PTHREAD_MUTEX_INITIALIZER, .psi_mutex = nullptr, .owner = 0, \ @@ -140,10 +140,10 @@ typedef struct toku_mutex_aligned { #else #define TOKU_ADAPTIVE_MUTEX_INITIALIZER \ { .pmutex = PTHREAD_MUTEX_INITIALIZER, .psi_mutex = nullptr } -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) #else // __FreeBSD__, __linux__, at least #define TOKU_MUTEX_ADAPTIVE PTHREAD_MUTEX_ADAPTIVE_NP -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) #define TOKU_ADAPTIVE_MUTEX_INITIALIZER \ { \ .pmutex = PTHREAD_ADAPTIVE_MUTEX_INITIALIZER_NP, .psi_mutex = nullptr, \ @@ -152,8 +152,8 @@ typedef struct toku_mutex_aligned { #else #define TOKU_ADAPTIVE_MUTEX_INITIALIZER \ { .pmutex = PTHREAD_ADAPTIVE_MUTEX_INITIALIZER_NP, .psi_mutex = nullptr } -#endif -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) +#endif // defined(__APPLE__) // Different OSes implement mutexes as different amounts of nested structs. // C++ will fill out all missing values with zeroes if you provide at least one @@ -188,7 +188,7 @@ toku_mutexattr_destroy(toku_pthread_mutexattr_t *attr) { assert_zero(r); } -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) static inline void toku_mutex_assert_locked(const toku_mutex_t *mutex) { invariant(mutex->locked); invariant(mutex->owner == pthread_self()); @@ -197,7 +197,7 @@ static inline void toku_mutex_assert_locked(const toku_mutex_t *mutex) { static inline void toku_mutex_assert_locked(const toku_mutex_t *mutex __attribute__((unused))) { } -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) // asserting that a mutex is unlocked only makes sense // if the calling thread can guaruntee that no other threads @@ -207,7 +207,7 @@ toku_mutex_assert_locked(const toku_mutex_t *mutex __attribute__((unused))) { // when a node is locked the caller knows that no other threads // can be trying to lock its childrens' mutexes. the children // are in one of two fixed states: locked or unlocked. -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) static inline void toku_mutex_assert_unlocked(toku_mutex_t *mutex) { invariant(mutex->owner == 0); @@ -216,7 +216,7 @@ toku_mutex_assert_unlocked(toku_mutex_t *mutex) { #else static inline void toku_mutex_assert_unlocked(toku_mutex_t *mutex __attribute__((unused))) {} -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) #define toku_mutex_lock(M) \ toku_mutex_lock_with_source_location(M, __FILE__, __LINE__) @@ -231,13 +231,13 @@ static inline void toku_cond_init(toku_cond_t *cond, toku_mutex_trylock_with_source_location(M, __FILE__, __LINE__) inline void toku_mutex_unlock(toku_mutex_t *mutex) { -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) invariant(mutex->owner == pthread_self()); invariant(mutex->valid); invariant(mutex->locked); mutex->locked = false; mutex->owner = 0; -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) toku_instr_mutex_unlock(mutex->psi_mutex); int r = pthread_mutex_unlock(&mutex->pmutex); assert_zero(r); @@ -254,13 +254,13 @@ inline void toku_mutex_lock_with_source_location(toku_mutex_t *mutex, toku_instr_mutex_lock_end(mutex_instr, r); assert_zero(r); -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) invariant(mutex->valid); invariant(!mutex->locked); invariant(mutex->owner == 0); mutex->locked = true; mutex->owner = pthread_self(); -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) } inline int toku_mutex_trylock_with_source_location(toku_mutex_t *mutex, @@ -273,7 +273,7 @@ inline int toku_mutex_trylock_with_source_location(toku_mutex_t *mutex, const int r = pthread_mutex_lock(&mutex->pmutex); toku_instr_mutex_lock_end(mutex_instr, r); -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) if (r == 0) { invariant(mutex->valid); invariant(!mutex->locked); @@ -281,7 +281,7 @@ inline int toku_mutex_trylock_with_source_location(toku_mutex_t *mutex, mutex->locked = true; mutex->owner = pthread_self(); } -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) return r; } @@ -310,11 +310,11 @@ inline void toku_cond_wait_with_source_location(toku_cond_t *cond, const char *src_file, uint src_line) { -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) invariant(mutex->locked); mutex->locked = false; mutex->owner = 0; -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) /* Instrumentation start */ toku_cond_instrumentation cond_instr; @@ -332,11 +332,11 @@ inline void toku_cond_wait_with_source_location(toku_cond_t *cond, toku_instr_cond_wait_end(cond_instr, r); assert_zero(r); -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) invariant(!mutex->locked); mutex->locked = true; mutex->owner = pthread_self(); -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) } inline int toku_cond_timedwait_with_source_location(toku_cond_t *cond, @@ -344,11 +344,11 @@ inline int toku_cond_timedwait_with_source_location(toku_cond_t *cond, toku_timespec_t *wakeup_at, const char *src_file, uint src_line) { -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) invariant(mutex->locked); mutex->locked = false; mutex->owner = 0; -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) /* Instrumentation start */ toku_cond_instrumentation cond_instr; @@ -366,11 +366,11 @@ inline int toku_cond_timedwait_with_source_location(toku_cond_t *cond, /* Instrumentation end */ toku_instr_cond_wait_end(cond_instr, r); -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) invariant(!mutex->locked); mutex->locked = true; mutex->owner = pthread_self(); -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) return r; } @@ -389,26 +389,26 @@ inline void toku_cond_broadcast(toku_cond_t *cond) { inline void toku_mutex_init(const toku_instr_key &key, toku_mutex_t *mutex, const toku_pthread_mutexattr_t *attr) { -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) mutex->valid = true; -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) toku_instr_mutex_init(key, *mutex); const int r = pthread_mutex_init(&mutex->pmutex, attr); assert_zero(r); -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) mutex->locked = false; invariant(mutex->valid); mutex->valid = true; mutex->owner = 0; -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) } inline void toku_mutex_destroy(toku_mutex_t *mutex) { -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) invariant(mutex->valid); mutex->valid = false; invariant(!mutex->locked); -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) toku_instr_mutex_destroy(mutex->psi_mutex); int r = pthread_mutex_destroy(&mutex->pmutex); assert_zero(r); diff --git a/storage/tokudb/PerconaFT/tools/CMakeLists.txt b/storage/tokudb/PerconaFT/tools/CMakeLists.txt index d54c2c21827..710a55a5957 100644 --- a/storage/tokudb/PerconaFT/tools/CMakeLists.txt +++ b/storage/tokudb/PerconaFT/tools/CMakeLists.txt @@ -15,16 +15,12 @@ foreach(tool ${tools}) if ((CMAKE_BUILD_TYPE MATCHES "Debug") AND (CMAKE_CXX_FLAGS_DEBUG MATCHES " -DENABLED_DEBUG_SYNC")) if (MYSQL_BASE_VERSION VERSION_EQUAL "8.0") - target_link_libraries(${tool} sql_main sql_gis sql_main binlog rpl master slave ${ICU_LIBRARIES}) + target_link_libraries(${tool} sql_main sql_gis sql_main sql_dd sql_gis binlog rpl master slave ${ICU_LIBRARIES}) else () target_link_libraries(${tool} sql binlog rpl master slave) endif () else () - if (MYSQL_BASE_VERSION VERSION_EQUAL "8.0") - target_link_libraries(${tool} mysqlclient) - else () - target_link_libraries(${tool} perconaserverclient) - endif () + target_link_libraries(${tool} perconaserverclient) endif () endif () diff --git a/storage/tokudb/PerconaFT/util/growable_array.h b/storage/tokudb/PerconaFT/util/growable_array.h index e8873ae4abd..ad60ea6395b 100644 --- a/storage/tokudb/PerconaFT/util/growable_array.h +++ b/storage/tokudb/PerconaFT/util/growable_array.h @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/util/omt.cc b/storage/tokudb/PerconaFT/util/omt.cc index 1fae0712c77..846c4df7f54 100644 --- a/storage/tokudb/PerconaFT/util/omt.cc +++ b/storage/tokudb/PerconaFT/util/omt.cc @@ -32,1105 +32,1356 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ -#ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." +#ident \ + "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." -#include <string.h> #include <db.h> +#include <string.h> #include <portability/memory.h> namespace toku { -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::create(void) { - this->create_internal(2); - if (supports_marks) { - this->convert_to_tree(); + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::create(void) { + this->create_internal(2); + if (supports_marks) { + this->convert_to_tree(); + } } -} -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::create_no_array(void) { - if (!supports_marks) { - this->create_internal_no_array(0); - } else { - this->is_array = false; - this->capacity = 0; - this->d.t.nodes = nullptr; - this->d.t.root.set_to_null(); - this->d.t.free_idx = 0; - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::create_from_sorted_array(const omtdata_t *const values, const uint32_t numvalues) { - this->create_internal(numvalues); - memcpy(this->d.a.values, values, numvalues * (sizeof values[0])); - this->d.a.num_values = numvalues; - if (supports_marks) { - this->convert_to_tree(); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::create_steal_sorted_array(omtdata_t **const values, const uint32_t numvalues, const uint32_t new_capacity) { - paranoid_invariant_notnull(values); - this->create_internal_no_array(new_capacity); - this->d.a.num_values = numvalues; - this->d.a.values = *values; - *values = nullptr; - if (supports_marks) { - this->convert_to_tree(); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -int omt<omtdata_t, omtdataout_t, supports_marks>::split_at(omt *const newomt, const uint32_t idx) { - barf_if_marked(*this); - paranoid_invariant_notnull(newomt); - if (idx > this->size()) { return EINVAL; } - this->convert_to_array(); - const uint32_t newsize = this->size() - idx; - newomt->create_from_sorted_array(&this->d.a.values[this->d.a.start_idx + idx], newsize); - this->d.a.num_values = idx; - this->maybe_resize_array(idx); - if (supports_marks) { - this->convert_to_tree(); - } - return 0; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::merge(omt *const leftomt, omt *const rightomt) { - barf_if_marked(*this); - paranoid_invariant_notnull(leftomt); - paranoid_invariant_notnull(rightomt); - const uint32_t leftsize = leftomt->size(); - const uint32_t rightsize = rightomt->size(); - const uint32_t newsize = leftsize + rightsize; - - if (leftomt->is_array) { - if (leftomt->capacity - (leftomt->d.a.start_idx + leftomt->d.a.num_values) >= rightsize) { - this->create_steal_sorted_array(&leftomt->d.a.values, leftomt->d.a.num_values, leftomt->capacity); - this->d.a.start_idx = leftomt->d.a.start_idx; + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::create_no_array(void) { + if (!supports_marks) { + this->create_internal_no_array(0); + } else { + this->is_array = false; + this->capacity = 0; + this->d.t.nodes = nullptr; + this->d.t.root.set_to_null(); + this->d.t.free_idx = 0; + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::create_from_sorted_array( + const omtdata_t *const values, + const uint32_t numvalues) { + this->create_internal(numvalues); + memcpy(this->d.a.values, values, numvalues * (sizeof values[0])); + this->d.a.num_values = numvalues; + if (supports_marks) { + this->convert_to_tree(); + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void + omt<omtdata_t, omtdataout_t, supports_marks>::create_steal_sorted_array( + omtdata_t **const values, + const uint32_t numvalues, + const uint32_t new_capacity) { + paranoid_invariant_notnull(values); + this->create_internal_no_array(new_capacity); + this->d.a.num_values = numvalues; + this->d.a.values = *values; + *values = nullptr; + if (supports_marks) { + this->convert_to_tree(); + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + int omt<omtdata_t, omtdataout_t, supports_marks>::split_at( + omt *const newomt, + const uint32_t idx) { + barf_if_marked(*this); + paranoid_invariant_notnull(newomt); + if (idx > this->size()) { + return EINVAL; + } + this->convert_to_array(); + const uint32_t newsize = this->size() - idx; + newomt->create_from_sorted_array( + &this->d.a.values[this->d.a.start_idx + idx], newsize); + this->d.a.num_values = idx; + this->maybe_resize_array(idx); + if (supports_marks) { + this->convert_to_tree(); + } + return 0; + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::merge( + omt *const leftomt, + omt *const rightomt) { + barf_if_marked(*this); + paranoid_invariant_notnull(leftomt); + paranoid_invariant_notnull(rightomt); + const uint32_t leftsize = leftomt->size(); + const uint32_t rightsize = rightomt->size(); + const uint32_t newsize = leftsize + rightsize; + + if (leftomt->is_array) { + if (leftomt->capacity - + (leftomt->d.a.start_idx + leftomt->d.a.num_values) >= + rightsize) { + this->create_steal_sorted_array(&leftomt->d.a.values, + leftomt->d.a.num_values, + leftomt->capacity); + this->d.a.start_idx = leftomt->d.a.start_idx; + } else { + this->create_internal(newsize); + memcpy(&this->d.a.values[0], + &leftomt->d.a.values[leftomt->d.a.start_idx], + leftomt->d.a.num_values * (sizeof this->d.a.values[0])); + } } else { this->create_internal(newsize); + leftomt->fill_array_with_subtree_values(&this->d.a.values[0], + leftomt->d.t.root); + } + leftomt->destroy(); + this->d.a.num_values = leftsize; + + if (rightomt->is_array) { + memcpy( + &this->d.a.values[this->d.a.start_idx + this->d.a.num_values], + &rightomt->d.a.values[rightomt->d.a.start_idx], + rightomt->d.a.num_values * (sizeof this->d.a.values[0])); + } else { + rightomt->fill_array_with_subtree_values( + &this->d.a.values[this->d.a.start_idx + this->d.a.num_values], + rightomt->d.t.root); + } + rightomt->destroy(); + this->d.a.num_values += rightsize; + paranoid_invariant(this->size() == newsize); + if (supports_marks) { + this->convert_to_tree(); + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::clone(const omt &src) { + barf_if_marked(*this); + this->create_internal(src.size()); + if (src.is_array) { memcpy(&this->d.a.values[0], - &leftomt->d.a.values[leftomt->d.a.start_idx], - leftomt->d.a.num_values * (sizeof this->d.a.values[0])); - } - } else { - this->create_internal(newsize); - leftomt->fill_array_with_subtree_values(&this->d.a.values[0], leftomt->d.t.root); - } - leftomt->destroy(); - this->d.a.num_values = leftsize; - - if (rightomt->is_array) { - memcpy(&this->d.a.values[this->d.a.start_idx + this->d.a.num_values], - &rightomt->d.a.values[rightomt->d.a.start_idx], - rightomt->d.a.num_values * (sizeof this->d.a.values[0])); - } else { - rightomt->fill_array_with_subtree_values(&this->d.a.values[this->d.a.start_idx + this->d.a.num_values], - rightomt->d.t.root); - } - rightomt->destroy(); - this->d.a.num_values += rightsize; - paranoid_invariant(this->size() == newsize); - if (supports_marks) { - this->convert_to_tree(); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::clone(const omt &src) { - barf_if_marked(*this); - this->create_internal(src.size()); - if (src.is_array) { - memcpy(&this->d.a.values[0], &src.d.a.values[src.d.a.start_idx], src.d.a.num_values * (sizeof this->d.a.values[0])); - } else { - src.fill_array_with_subtree_values(&this->d.a.values[0], src.d.t.root); - } - this->d.a.num_values = src.size(); - if (supports_marks) { - this->convert_to_tree(); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::clear(void) { - if (this->is_array) { - this->d.a.start_idx = 0; - this->d.a.num_values = 0; - } else { - this->d.t.root.set_to_null(); - this->d.t.free_idx = 0; - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::destroy(void) { - this->clear(); - this->capacity = 0; - if (this->is_array) { - if (this->d.a.values != nullptr) { - toku_free(this->d.a.values); + &src.d.a.values[src.d.a.start_idx], + src.d.a.num_values * (sizeof this->d.a.values[0])); + } else { + src.fill_array_with_subtree_values(&this->d.a.values[0], + src.d.t.root); } - this->d.a.values = nullptr; - } else { - if (this->d.t.nodes != nullptr) { - toku_free(this->d.t.nodes); + this->d.a.num_values = src.size(); + if (supports_marks) { + this->convert_to_tree(); + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::clear(void) { + if (this->is_array) { + this->d.a.start_idx = 0; + this->d.a.num_values = 0; + } else { + this->d.t.root.set_to_null(); + this->d.t.free_idx = 0; + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::destroy(void) { + this->clear(); + this->capacity = 0; + if (this->is_array) { + if (this->d.a.values != nullptr) { + toku_free(this->d.a.values); + } + this->d.a.values = nullptr; + } else { + if (this->d.t.nodes != nullptr) { + toku_free(this->d.t.nodes); + } + this->d.t.nodes = nullptr; } - this->d.t.nodes = nullptr; } -} -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -uint32_t omt<omtdata_t, omtdataout_t, supports_marks>::size(void) const { - if (this->is_array) { - return this->d.a.num_values; - } else { - return this->nweight(this->d.t.root); + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + uint32_t omt<omtdata_t, omtdataout_t, supports_marks>::size(void) const { + if (this->is_array) { + return this->d.a.num_values; + } else { + return this->nweight(this->d.t.root); + } } -} + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template <typename omtcmp_t, int (*h)(const omtdata_t &, const omtcmp_t &)> + int omt<omtdata_t, omtdataout_t, supports_marks>::insert( + const omtdata_t &value, + const omtcmp_t &v, + uint32_t *const idx) { + int r; + uint32_t insert_idx; -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename omtcmp_t, int (*h)(const omtdata_t &, const omtcmp_t &)> -int omt<omtdata_t, omtdataout_t, supports_marks>::insert(const omtdata_t &value, const omtcmp_t &v, uint32_t *const idx) { - int r; - uint32_t insert_idx; + r = this->find_zero<omtcmp_t, h>(v, nullptr, &insert_idx); + if (r == 0) { + if (idx) + *idx = insert_idx; + return DB_KEYEXIST; + } + if (r != DB_NOTFOUND) + return r; - r = this->find_zero<omtcmp_t, h>(v, nullptr, &insert_idx); - if (r==0) { - if (idx) *idx = insert_idx; - return DB_KEYEXIST; + if ((r = this->insert_at(value, insert_idx))) + return r; + if (idx) + *idx = insert_idx; + + return 0; } - if (r != DB_NOTFOUND) return r; - if ((r = this->insert_at(value, insert_idx))) return r; - if (idx) *idx = insert_idx; + // The following 3 functions implement a static if for us. + template <typename omtdata_t, typename omtdataout_t> + static void barf_if_marked( + const omt<omtdata_t, omtdataout_t, false> &UU(omt)) {} - return 0; -} + template <typename omtdata_t, typename omtdataout_t> + static void barf_if_marked(const omt<omtdata_t, omtdataout_t, true> &omt) { + invariant(!omt.has_marks()); + } -// The following 3 functions implement a static if for us. -template<typename omtdata_t, typename omtdataout_t> -static void barf_if_marked(const omt<omtdata_t, omtdataout_t, false> &UU(omt)) { -} + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + bool omt<omtdata_t, omtdataout_t, supports_marks>::has_marks(void) const { + static_assert(supports_marks, "Does not support marks"); + if (this->d.t.root.is_null()) { + return false; + } + const omt_node &node = this->d.t.nodes[this->d.t.root.get_index()]; + return node.get_marks_below() || node.get_marked(); + } -template<typename omtdata_t, typename omtdataout_t> -static void barf_if_marked(const omt<omtdata_t, omtdataout_t, true> &omt) { - invariant(!omt.has_marks()); -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -bool omt<omtdata_t, omtdataout_t, supports_marks>::has_marks(void) const { - static_assert(supports_marks, "Does not support marks"); - if (this->d.t.root.is_null()) { - return false; - } - const omt_node &node = this->d.t.nodes[this->d.t.root.get_index()]; - return node.get_marks_below() || node.get_marked(); -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -int omt<omtdata_t, omtdataout_t, supports_marks>::insert_at(const omtdata_t &value, const uint32_t idx) { - barf_if_marked(*this); - if (idx > this->size()) { return EINVAL; } - - this->maybe_resize_or_convert(this->size() + 1); - if (this->is_array && idx != this->d.a.num_values && - (idx != 0 || this->d.a.start_idx == 0)) { - this->convert_to_tree(); - } - if (this->is_array) { - if (idx == this->d.a.num_values) { - this->d.a.values[this->d.a.start_idx + this->d.a.num_values] = value; - } - else { - this->d.a.values[--this->d.a.start_idx] = value; - } - this->d.a.num_values++; - } - else { - subtree *rebalance_subtree = nullptr; - this->insert_internal(&this->d.t.root, value, idx, &rebalance_subtree); - if (rebalance_subtree != nullptr) { - this->rebalance(rebalance_subtree); - } - } - return 0; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -int omt<omtdata_t, omtdataout_t, supports_marks>::set_at(const omtdata_t &value, const uint32_t idx) { - barf_if_marked(*this); - if (idx >= this->size()) { return EINVAL; } - - if (this->is_array) { - this->set_at_internal_array(value, idx); - } else { - this->set_at_internal(this->d.t.root, value, idx); - } - return 0; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -int omt<omtdata_t, omtdataout_t, supports_marks>::delete_at(const uint32_t idx) { - barf_if_marked(*this); - if (idx >= this->size()) { return EINVAL; } - - this->maybe_resize_or_convert(this->size() - 1); - if (this->is_array && idx != 0 && idx != this->d.a.num_values - 1) { - this->convert_to_tree(); - } - if (this->is_array) { - //Testing for 0 does not rule out it being the last entry. - //Test explicitly for num_values-1 - if (idx != this->d.a.num_values - 1) { - this->d.a.start_idx++; - } - this->d.a.num_values--; - } else { - subtree *rebalance_subtree = nullptr; - this->delete_internal(&this->d.t.root, idx, nullptr, &rebalance_subtree); - if (rebalance_subtree != nullptr) { - this->rebalance(rebalance_subtree); - } - } - return 0; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename iterate_extra_t, - int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> -int omt<omtdata_t, omtdataout_t, supports_marks>::iterate(iterate_extra_t *const iterate_extra) const { - return this->iterate_on_range<iterate_extra_t, f>(0, this->size(), iterate_extra); -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename iterate_extra_t, - int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> -int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_on_range(const uint32_t left, const uint32_t right, iterate_extra_t *const iterate_extra) const { - if (right > this->size()) { return EINVAL; } - if (left == right) { return 0; } - if (this->is_array) { - return this->iterate_internal_array<iterate_extra_t, f>(left, right, iterate_extra); - } - return this->iterate_internal<iterate_extra_t, f>(left, right, this->d.t.root, 0, iterate_extra); -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename iterate_extra_t, - int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> -int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_and_mark_range(const uint32_t left, const uint32_t right, iterate_extra_t *const iterate_extra) { - static_assert(supports_marks, "does not support marks"); - if (right > this->size()) { return EINVAL; } - if (left == right) { return 0; } - paranoid_invariant(!this->is_array); - return this->iterate_and_mark_range_internal<iterate_extra_t, f>(left, right, this->d.t.root, 0, iterate_extra); -} - -//TODO: We can optimize this if we steal 3 bits. 1 bit: this node is marked. 1 bit: left subtree has marks. 1 bit: right subtree has marks. -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename iterate_extra_t, - int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> -int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_over_marked(iterate_extra_t *const iterate_extra) const { - static_assert(supports_marks, "does not support marks"); - paranoid_invariant(!this->is_array); - return this->iterate_over_marked_internal<iterate_extra_t, f>(this->d.t.root, 0, iterate_extra); -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::unmark(const subtree &subtree, const uint32_t index, GrowableArray<node_idx> *const indexes) { - if (subtree.is_null()) { return; } - omt_node &n = this->d.t.nodes[subtree.get_index()]; - const uint32_t index_root = index + this->nweight(n.left); - - const bool below = n.get_marks_below(); - if (below) { - this->unmark(n.left, index, indexes); - } - if (n.get_marked()) { - indexes->push(index_root); - } - n.clear_stolen_bits(); - if (below) { - this->unmark(n.right, index_root + 1, indexes); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::delete_all_marked(void) { - static_assert(supports_marks, "does not support marks"); - if (!this->has_marks()) { - return; - } - paranoid_invariant(!this->is_array); - GrowableArray<node_idx> marked_indexes; - marked_indexes.init(); - - // Remove all marks. - // We need to delete all the stolen bits before calling delete_at to prevent barfing. - this->unmark(this->d.t.root, 0, &marked_indexes); - - for (uint32_t i = 0; i < marked_indexes.get_size(); i++) { - // Delete from left to right, shift by number already deleted. - // Alternative is delete from right to left. - int r = this->delete_at(marked_indexes.fetch_unchecked(i) - i); - lazy_assert_zero(r); - } - marked_indexes.deinit(); - barf_if_marked(*this); -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -uint32_t omt<omtdata_t, omtdataout_t, supports_marks>::verify_marks_consistent_internal(const subtree &subtree, const bool UU(allow_marks)) const { - if (subtree.is_null()) { + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + int omt<omtdata_t, omtdataout_t, supports_marks>::insert_at( + const omtdata_t &value, + const uint32_t idx) { + barf_if_marked(*this); + if (idx > this->size()) { + return EINVAL; + } + + this->maybe_resize_or_convert(this->size() + 1); + if (this->is_array && idx != this->d.a.num_values && + (idx != 0 || this->d.a.start_idx == 0)) { + this->convert_to_tree(); + } + if (this->is_array) { + if (idx == this->d.a.num_values) { + this->d.a.values[this->d.a.start_idx + this->d.a.num_values] = + value; + } else { + this->d.a.values[--this->d.a.start_idx] = value; + } + this->d.a.num_values++; + } else { + subtree *rebalance_subtree = nullptr; + this->insert_internal( + &this->d.t.root, value, idx, &rebalance_subtree); + if (rebalance_subtree != nullptr) { + this->rebalance(rebalance_subtree); + } + } return 0; } - const omt_node &node = this->d.t.nodes[subtree.get_index()]; - uint32_t num_marks = verify_marks_consistent_internal(node.left, node.get_marks_below()); - num_marks += verify_marks_consistent_internal(node.right, node.get_marks_below()); - if (node.get_marks_below()) { - paranoid_invariant(allow_marks); - paranoid_invariant(num_marks > 0); - } else { - // redundant with invariant below, but nice to have explicitly - paranoid_invariant(num_marks == 0); - } - if (node.get_marked()) { - paranoid_invariant(allow_marks); - ++num_marks; - } - return num_marks; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::verify_marks_consistent(void) const { - static_assert(supports_marks, "does not support marks"); - paranoid_invariant(!this->is_array); - this->verify_marks_consistent_internal(this->d.t.root, true); -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename iterate_extra_t, - int (*f)(omtdata_t *, const uint32_t, iterate_extra_t *const)> -void omt<omtdata_t, omtdataout_t, supports_marks>::iterate_ptr(iterate_extra_t *const iterate_extra) { - if (this->is_array) { - this->iterate_ptr_internal_array<iterate_extra_t, f>(0, this->size(), iterate_extra); - } else { - this->iterate_ptr_internal<iterate_extra_t, f>(0, this->size(), this->d.t.root, 0, iterate_extra); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -int omt<omtdata_t, omtdataout_t, supports_marks>::fetch(const uint32_t idx, omtdataout_t *const value) const { - if (idx >= this->size()) { return EINVAL; } - if (this->is_array) { - this->fetch_internal_array(idx, value); - } else { - this->fetch_internal(this->d.t.root, idx, value); - } - return 0; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename omtcmp_t, - int (*h)(const omtdata_t &, const omtcmp_t &)> -int omt<omtdata_t, omtdataout_t, supports_marks>::find_zero(const omtcmp_t &extra, omtdataout_t *const value, uint32_t *const idxp) const { - uint32_t tmp_index; - uint32_t *const child_idxp = (idxp != nullptr) ? idxp : &tmp_index; - int r; - if (this->is_array) { - r = this->find_internal_zero_array<omtcmp_t, h>(extra, value, child_idxp); - } - else { - r = this->find_internal_zero<omtcmp_t, h>(this->d.t.root, extra, value, child_idxp); - } - return r; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename omtcmp_t, - int (*h)(const omtdata_t &, const omtcmp_t &)> -int omt<omtdata_t, omtdataout_t, supports_marks>::find(const omtcmp_t &extra, int direction, omtdataout_t *const value, uint32_t *const idxp) const { - uint32_t tmp_index; - uint32_t *const child_idxp = (idxp != nullptr) ? idxp : &tmp_index; - paranoid_invariant(direction != 0); - if (direction < 0) { + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + int omt<omtdata_t, omtdataout_t, supports_marks>::set_at( + const omtdata_t &value, + const uint32_t idx) { + barf_if_marked(*this); + if (idx >= this->size()) { + return EINVAL; + } + if (this->is_array) { - return this->find_internal_minus_array<omtcmp_t, h>(extra, value, child_idxp); + this->set_at_internal_array(value, idx); } else { - return this->find_internal_minus<omtcmp_t, h>(this->d.t.root, extra, value, child_idxp); + this->set_at_internal(this->d.t.root, value, idx); + } + return 0; + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + int omt<omtdata_t, omtdataout_t, supports_marks>::delete_at( + const uint32_t idx) { + barf_if_marked(*this); + if (idx >= this->size()) { + return EINVAL; + } + + this->maybe_resize_or_convert(this->size() - 1); + if (this->is_array && idx != 0 && idx != this->d.a.num_values - 1) { + this->convert_to_tree(); } - } else { if (this->is_array) { - return this->find_internal_plus_array<omtcmp_t, h>(extra, value, child_idxp); + // Testing for 0 does not rule out it being the last entry. + // Test explicitly for num_values-1 + if (idx != this->d.a.num_values - 1) { + this->d.a.start_idx++; + } + this->d.a.num_values--; } else { - return this->find_internal_plus<omtcmp_t, h>(this->d.t.root, extra, value, child_idxp); + subtree *rebalance_subtree = nullptr; + this->delete_internal( + &this->d.t.root, idx, nullptr, &rebalance_subtree); + if (rebalance_subtree != nullptr) { + this->rebalance(rebalance_subtree); + } } + return 0; } -} -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -size_t omt<omtdata_t, omtdataout_t, supports_marks>::memory_size(void) { - if (this->is_array) { - return (sizeof *this) + this->capacity * (sizeof this->d.a.values[0]); + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template < + typename iterate_extra_t, + int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> + int omt<omtdata_t, omtdataout_t, supports_marks>::iterate( + iterate_extra_t *const iterate_extra) const { + return this->iterate_on_range<iterate_extra_t, f>( + 0, this->size(), iterate_extra); + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template < + typename iterate_extra_t, + int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> + int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_on_range( + const uint32_t left, + const uint32_t right, + iterate_extra_t *const iterate_extra) const { + if (right > this->size()) { + return EINVAL; + } + if (left == right) { + return 0; + } + if (this->is_array) { + return this->iterate_internal_array<iterate_extra_t, f>( + left, right, iterate_extra); + } + return this->iterate_internal<iterate_extra_t, f>( + left, right, this->d.t.root, 0, iterate_extra); + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template < + typename iterate_extra_t, + int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> + int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_and_mark_range( + const uint32_t left, + const uint32_t right, + iterate_extra_t *const iterate_extra) { + static_assert(supports_marks, "does not support marks"); + if (right > this->size()) { + return EINVAL; + } + if (left == right) { + return 0; + } + paranoid_invariant(!this->is_array); + return this->iterate_and_mark_range_internal<iterate_extra_t, f>( + left, right, this->d.t.root, 0, iterate_extra); + } + + // TODO: We can optimize this if we steal 3 bits. 1 bit: this node is + // marked. 1 bit: left subtree has marks. 1 bit: right subtree has marks. + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template < + typename iterate_extra_t, + int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> + int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_over_marked( + iterate_extra_t *const iterate_extra) const { + static_assert(supports_marks, "does not support marks"); + paranoid_invariant(!this->is_array); + return this->iterate_over_marked_internal<iterate_extra_t, f>( + this->d.t.root, 0, iterate_extra); + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::unmark( + const subtree &st, + const uint32_t index, + GrowableArray<node_idx> *const indexes) { + if (st.is_null()) { + return; + } + omt_node &n = this->d.t.nodes[st.get_index()]; + const uint32_t index_root = index + this->nweight(n.left); + + const bool below = n.get_marks_below(); + if (below) { + this->unmark(n.left, index, indexes); + } + if (n.get_marked()) { + indexes->push(index_root); + } + n.clear_stolen_bits(); + if (below) { + this->unmark(n.right, index_root + 1, indexes); + } } - return (sizeof *this) + this->capacity * (sizeof this->d.t.nodes[0]); -} + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::delete_all_marked(void) { + static_assert(supports_marks, "does not support marks"); + if (!this->has_marks()) { + return; + } + paranoid_invariant(!this->is_array); + GrowableArray<node_idx> marked_indexes; + marked_indexes.init(); + + // Remove all marks. + // We need to delete all the stolen bits before calling delete_at to + // prevent barfing. + this->unmark(this->d.t.root, 0, &marked_indexes); + + for (uint32_t i = 0; i < marked_indexes.get_size(); i++) { + // Delete from left to right, shift by number already deleted. + // Alternative is delete from right to left. + int r = this->delete_at(marked_indexes.fetch_unchecked(i) - i); + lazy_assert_zero(r); + } + marked_indexes.deinit(); + barf_if_marked(*this); + } -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::create_internal_no_array(const uint32_t new_capacity) { - this->is_array = true; - this->d.a.start_idx = 0; - this->d.a.num_values = 0; - this->d.a.values = nullptr; - this->capacity = new_capacity; -} + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + uint32_t omt<omtdata_t, omtdataout_t, supports_marks>:: + verify_marks_consistent_internal(const subtree &st, + const bool UU(allow_marks)) const { + if (st.is_null()) { + return 0; + } + const omt_node &node = this->d.t.nodes[st.get_index()]; + uint32_t num_marks = + verify_marks_consistent_internal(node.left, node.get_marks_below()); + num_marks += verify_marks_consistent_internal(node.right, + node.get_marks_below()); + if (node.get_marks_below()) { + paranoid_invariant(allow_marks); + paranoid_invariant(num_marks > 0); + } else { + // redundant with invariant below, but nice to have explicitly + paranoid_invariant(num_marks == 0); + } + if (node.get_marked()) { + paranoid_invariant(allow_marks); + ++num_marks; + } + return num_marks; + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::verify_marks_consistent( + void) const { + static_assert(supports_marks, "does not support marks"); + paranoid_invariant(!this->is_array); + this->verify_marks_consistent_internal(this->d.t.root, true); + } -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::create_internal(const uint32_t new_capacity) { - this->create_internal_no_array(new_capacity); - XMALLOC_N(this->capacity, this->d.a.values); -} + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template <typename iterate_extra_t, + int (*f)(omtdata_t *, const uint32_t, iterate_extra_t *const)> + void omt<omtdata_t, omtdataout_t, supports_marks>::iterate_ptr( + iterate_extra_t *const iterate_extra) { + if (this->is_array) { + this->iterate_ptr_internal_array<iterate_extra_t, f>( + 0, this->size(), iterate_extra); + } else { + this->iterate_ptr_internal<iterate_extra_t, f>( + 0, this->size(), this->d.t.root, 0, iterate_extra); + } + } -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -uint32_t omt<omtdata_t, omtdataout_t, supports_marks>::nweight(const subtree &subtree) const { - if (subtree.is_null()) { + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + int omt<omtdata_t, omtdataout_t, supports_marks>::fetch( + const uint32_t idx, + omtdataout_t *const value) const { + if (idx >= this->size()) { + return EINVAL; + } + if (this->is_array) { + this->fetch_internal_array(idx, value); + } else { + this->fetch_internal(this->d.t.root, idx, value); + } return 0; - } else { - return this->d.t.nodes[subtree.get_index()].weight; - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -typename omt<omtdata_t, omtdataout_t, supports_marks>::node_idx omt<omtdata_t, omtdataout_t, supports_marks>::node_malloc(void) { - paranoid_invariant(this->d.t.free_idx < this->capacity); - omt_node &n = this->d.t.nodes[this->d.t.free_idx]; - n.clear_stolen_bits(); - return this->d.t.free_idx++; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::node_free(const node_idx UU(idx)) { - paranoid_invariant(idx < this->capacity); -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::maybe_resize_array(const uint32_t n) { - const uint32_t new_size = n<=2 ? 4 : 2*n; - const uint32_t room = this->capacity - this->d.a.start_idx; - - if (room < n || this->capacity / 2 >= new_size) { - omtdata_t *XMALLOC_N(new_size, tmp_values); - memcpy(tmp_values, &this->d.a.values[this->d.a.start_idx], - this->d.a.num_values * (sizeof tmp_values[0])); + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template <typename omtcmp_t, int (*h)(const omtdata_t &, const omtcmp_t &)> + int omt<omtdata_t, omtdataout_t, supports_marks>::find_zero( + const omtcmp_t &extra, + omtdataout_t *const value, + uint32_t *const idxp) const { + uint32_t tmp_index; + uint32_t *const child_idxp = (idxp != nullptr) ? idxp : &tmp_index; + int r; + if (this->is_array) { + r = this->find_internal_zero_array<omtcmp_t, h>( + extra, value, child_idxp); + } else { + r = this->find_internal_zero<omtcmp_t, h>( + this->d.t.root, extra, value, child_idxp); + } + return r; + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template <typename omtcmp_t, int (*h)(const omtdata_t &, const omtcmp_t &)> + int omt<omtdata_t, omtdataout_t, supports_marks>::find( + const omtcmp_t &extra, + int direction, + omtdataout_t *const value, + uint32_t *const idxp) const { + uint32_t tmp_index; + uint32_t *const child_idxp = (idxp != nullptr) ? idxp : &tmp_index; + paranoid_invariant(direction != 0); + if (direction < 0) { + if (this->is_array) { + return this->find_internal_minus_array<omtcmp_t, h>( + extra, value, child_idxp); + } else { + return this->find_internal_minus<omtcmp_t, h>( + this->d.t.root, extra, value, child_idxp); + } + } else { + if (this->is_array) { + return this->find_internal_plus_array<omtcmp_t, h>( + extra, value, child_idxp); + } else { + return this->find_internal_plus<omtcmp_t, h>( + this->d.t.root, extra, value, child_idxp); + } + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + size_t omt<omtdata_t, omtdataout_t, supports_marks>::memory_size(void) { + if (this->is_array) { + return (sizeof *this) + + this->capacity * (sizeof this->d.a.values[0]); + } + return (sizeof *this) + this->capacity * (sizeof this->d.t.nodes[0]); + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::create_internal_no_array( + const uint32_t new_capacity) { + this->is_array = true; this->d.a.start_idx = 0; - this->capacity = new_size; - toku_free(this->d.a.values); - this->d.a.values = tmp_values; - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::fill_array_with_subtree_values(omtdata_t *const array, const subtree &subtree) const { - if (subtree.is_null()) return; - const omt_node &tree = this->d.t.nodes[subtree.get_index()]; - this->fill_array_with_subtree_values(&array[0], tree.left); - array[this->nweight(tree.left)] = tree.value; - this->fill_array_with_subtree_values(&array[this->nweight(tree.left) + 1], tree.right); -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::convert_to_array(void) { - if (!this->is_array) { - const uint32_t num_values = this->size(); - uint32_t new_size = 2*num_values; - new_size = new_size < 4 ? 4 : new_size; - - omtdata_t *XMALLOC_N(new_size, tmp_values); - this->fill_array_with_subtree_values(tmp_values, this->d.t.root); - toku_free(this->d.t.nodes); - this->is_array = true; - this->capacity = new_size; - this->d.a.num_values = num_values; - this->d.a.values = tmp_values; - this->d.a.start_idx = 0; - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::rebuild_from_sorted_array(subtree *const subtree, const omtdata_t *const values, const uint32_t numvalues) { - if (numvalues==0) { - subtree->set_to_null(); - } else { - const uint32_t halfway = numvalues/2; - const node_idx newidx = this->node_malloc(); - omt_node *const newnode = &this->d.t.nodes[newidx]; - newnode->weight = numvalues; - newnode->value = values[halfway]; - subtree->set_index(newidx); - // update everything before the recursive calls so the second call can be a tail call. - this->rebuild_from_sorted_array(&newnode->left, &values[0], halfway); - this->rebuild_from_sorted_array(&newnode->right, &values[halfway+1], numvalues - (halfway+1)); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::convert_to_tree(void) { - if (this->is_array) { - const uint32_t num_nodes = this->size(); - uint32_t new_size = num_nodes*2; - new_size = new_size < 4 ? 4 : new_size; - - omt_node *XMALLOC_N(new_size, new_nodes); - omtdata_t *const values = this->d.a.values; - omtdata_t *const tmp_values = &values[this->d.a.start_idx]; - this->is_array = false; - this->d.t.nodes = new_nodes; - this->capacity = new_size; - this->d.t.free_idx = 0; - this->d.t.root.set_to_null(); - this->rebuild_from_sorted_array(&this->d.t.root, tmp_values, num_nodes); - toku_free(values); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::maybe_resize_or_convert(const uint32_t n) { - if (this->is_array) { - this->maybe_resize_array(n); - } else { - const uint32_t new_size = n<=2 ? 4 : 2*n; - const uint32_t num_nodes = this->nweight(this->d.t.root); - if ((this->capacity/2 >= new_size) || - (this->d.t.free_idx >= this->capacity && num_nodes < n) || - (this->capacity<n)) { - this->convert_to_array(); - // if we had a free list, the "supports_marks" version could - // just resize, as it is now, we have to convert to and back - // from an array. - if (supports_marks) { - this->convert_to_tree(); + this->d.a.num_values = 0; + this->d.a.values = nullptr; + this->capacity = new_capacity; + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::create_internal( + const uint32_t new_capacity) { + this->create_internal_no_array(new_capacity); + XMALLOC_N(this->capacity, this->d.a.values); + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + uint32_t omt<omtdata_t, omtdataout_t, supports_marks>::nweight( + const subtree &st) const { + if (st.is_null()) { + return 0; + } else { + return this->d.t.nodes[st.get_index()].weight; + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + typename omt<omtdata_t, omtdataout_t, supports_marks>::node_idx + omt<omtdata_t, omtdataout_t, supports_marks>::node_malloc(void) { + paranoid_invariant(this->d.t.free_idx < this->capacity); + omt_node &n = this->d.t.nodes[this->d.t.free_idx]; + n.clear_stolen_bits(); + return this->d.t.free_idx++; + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::node_free( + const node_idx UU(idx)) { + paranoid_invariant(idx < this->capacity); + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::maybe_resize_array( + const uint32_t n) { + const uint32_t new_size = n <= 2 ? 4 : 2 * n; + const uint32_t room = this->capacity - this->d.a.start_idx; + + if (room < n || this->capacity / 2 >= new_size) { + omtdata_t *XMALLOC_N(new_size, tmp_values); + memcpy(tmp_values, + &this->d.a.values[this->d.a.start_idx], + this->d.a.num_values * (sizeof tmp_values[0])); + this->d.a.start_idx = 0; + this->capacity = new_size; + toku_free(this->d.a.values); + this->d.a.values = tmp_values; + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>:: + fill_array_with_subtree_values(omtdata_t *const array, + const subtree &st) const { + if (st.is_null()) + return; + const omt_node &tree = this->d.t.nodes[st.get_index()]; + this->fill_array_with_subtree_values(&array[0], tree.left); + array[this->nweight(tree.left)] = tree.value; + this->fill_array_with_subtree_values( + &array[this->nweight(tree.left) + 1], tree.right); + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::convert_to_array(void) { + if (!this->is_array) { + const uint32_t num_values = this->size(); + uint32_t new_size = 2 * num_values; + new_size = new_size < 4 ? 4 : new_size; + + omtdata_t *XMALLOC_N(new_size, tmp_values); + this->fill_array_with_subtree_values(tmp_values, this->d.t.root); + toku_free(this->d.t.nodes); + this->is_array = true; + this->capacity = new_size; + this->d.a.num_values = num_values; + this->d.a.values = tmp_values; + this->d.a.start_idx = 0; + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void + omt<omtdata_t, omtdataout_t, supports_marks>::rebuild_from_sorted_array( + subtree *const st, + const omtdata_t *const values, + const uint32_t numvalues) { + if (numvalues == 0) { + st->set_to_null(); + } else { + const uint32_t halfway = numvalues / 2; + const node_idx newidx = this->node_malloc(); + omt_node *const newnode = &this->d.t.nodes[newidx]; + newnode->weight = numvalues; + newnode->value = values[halfway]; + st->set_index(newidx); + // update everything before the recursive calls so the second call + // can be a tail call. + this->rebuild_from_sorted_array( + &newnode->left, &values[0], halfway); + this->rebuild_from_sorted_array(&newnode->right, + &values[halfway + 1], + numvalues - (halfway + 1)); + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::convert_to_tree(void) { + if (this->is_array) { + const uint32_t num_nodes = this->size(); + uint32_t new_size = num_nodes * 2; + new_size = new_size < 4 ? 4 : new_size; + + omt_node *XMALLOC_N(new_size, new_nodes); + omtdata_t *const values = this->d.a.values; + omtdata_t *const tmp_values = &values[this->d.a.start_idx]; + this->is_array = false; + this->d.t.nodes = new_nodes; + this->capacity = new_size; + this->d.t.free_idx = 0; + this->d.t.root.set_to_null(); + this->rebuild_from_sorted_array( + &this->d.t.root, tmp_values, num_nodes); + toku_free(values); + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::maybe_resize_or_convert( + const uint32_t n) { + if (this->is_array) { + this->maybe_resize_array(n); + } else { + const uint32_t new_size = n <= 2 ? 4 : 2 * n; + const uint32_t num_nodes = this->nweight(this->d.t.root); + if ((this->capacity / 2 >= new_size) || + (this->d.t.free_idx >= this->capacity && num_nodes < n) || + (this->capacity < n)) { + this->convert_to_array(); + // if we had a free list, the "supports_marks" version could + // just resize, as it is now, we have to convert to and back + // from an array. + if (supports_marks) { + this->convert_to_tree(); + } } } } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -bool omt<omtdata_t, omtdataout_t, supports_marks>::will_need_rebalance(const subtree &subtree, const int leftmod, const int rightmod) const { - if (subtree.is_null()) { return false; } - const omt_node &n = this->d.t.nodes[subtree.get_index()]; - // one of the 1's is for the root. - // the other is to take ceil(n/2) - const uint32_t weight_left = this->nweight(n.left) + leftmod; - const uint32_t weight_right = this->nweight(n.right) + rightmod; - return ((1+weight_left < (1+1+weight_right)/2) - || - (1+weight_right < (1+1+weight_left)/2)); -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::insert_internal(subtree *const subtreep, const omtdata_t &value, const uint32_t idx, subtree **const rebalance_subtree) { - if (subtreep->is_null()) { - paranoid_invariant_zero(idx); - const node_idx newidx = this->node_malloc(); - omt_node *const newnode = &this->d.t.nodes[newidx]; - newnode->weight = 1; - newnode->left.set_to_null(); - newnode->right.set_to_null(); - newnode->value = value; - subtreep->set_index(newidx); - } else { + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + bool omt<omtdata_t, omtdataout_t, supports_marks>::will_need_rebalance( + const subtree &st, + const int leftmod, + const int rightmod) const { + if (st.is_null()) { + return false; + } + const omt_node &n = this->d.t.nodes[st.get_index()]; + // one of the 1's is for the root. + // the other is to take ceil(n/2) + const uint32_t weight_left = this->nweight(n.left) + leftmod; + const uint32_t weight_right = this->nweight(n.right) + rightmod; + return ((1 + weight_left < (1 + 1 + weight_right) / 2) || + (1 + weight_right < (1 + 1 + weight_left) / 2)); + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::insert_internal( + subtree *const subtreep, + const omtdata_t &value, + const uint32_t idx, + subtree **const rebalance_subtree) { + if (subtreep->is_null()) { + paranoid_invariant_zero(idx); + const node_idx newidx = this->node_malloc(); + omt_node *const newnode = &this->d.t.nodes[newidx]; + newnode->weight = 1; + newnode->left.set_to_null(); + newnode->right.set_to_null(); + newnode->value = value; + subtreep->set_index(newidx); + } else { + omt_node &n = this->d.t.nodes[subtreep->get_index()]; + n.weight++; + if (idx <= this->nweight(n.left)) { + if (*rebalance_subtree == nullptr && + this->will_need_rebalance(*subtreep, 1, 0)) { + *rebalance_subtree = subtreep; + } + this->insert_internal(&n.left, value, idx, rebalance_subtree); + } else { + if (*rebalance_subtree == nullptr && + this->will_need_rebalance(*subtreep, 0, 1)) { + *rebalance_subtree = subtreep; + } + const uint32_t sub_index = idx - this->nweight(n.left) - 1; + this->insert_internal( + &n.right, value, sub_index, rebalance_subtree); + } + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::set_at_internal_array( + const omtdata_t &value, + const uint32_t idx) { + this->d.a.values[this->d.a.start_idx + idx] = value; + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::set_at_internal( + const subtree &st, + const omtdata_t &value, + const uint32_t idx) { + paranoid_invariant(!st.is_null()); + omt_node &n = this->d.t.nodes[st.get_index()]; + const uint32_t leftweight = this->nweight(n.left); + if (idx < leftweight) { + this->set_at_internal(n.left, value, idx); + } else if (idx == leftweight) { + n.value = value; + } else { + this->set_at_internal(n.right, value, idx - leftweight - 1); + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::delete_internal( + subtree *const subtreep, + const uint32_t idx, + omt_node *const copyn, + subtree **const rebalance_subtree) { + paranoid_invariant_notnull(subtreep); + paranoid_invariant_notnull(rebalance_subtree); + paranoid_invariant(!subtreep->is_null()); omt_node &n = this->d.t.nodes[subtreep->get_index()]; - n.weight++; - if (idx <= this->nweight(n.left)) { - if (*rebalance_subtree == nullptr && this->will_need_rebalance(*subtreep, 1, 0)) { + const uint32_t leftweight = this->nweight(n.left); + if (idx < leftweight) { + n.weight--; + if (*rebalance_subtree == nullptr && + this->will_need_rebalance(*subtreep, -1, 0)) { *rebalance_subtree = subtreep; } - this->insert_internal(&n.left, value, idx, rebalance_subtree); + this->delete_internal(&n.left, idx, copyn, rebalance_subtree); + } else if (idx == leftweight) { + if (n.left.is_null()) { + const uint32_t oldidx = subtreep->get_index(); + *subtreep = n.right; + if (copyn != nullptr) { + copyn->value = n.value; + } + this->node_free(oldidx); + } else if (n.right.is_null()) { + const uint32_t oldidx = subtreep->get_index(); + *subtreep = n.left; + if (copyn != nullptr) { + copyn->value = n.value; + } + this->node_free(oldidx); + } else { + if (*rebalance_subtree == nullptr && + this->will_need_rebalance(*subtreep, 0, -1)) { + *rebalance_subtree = subtreep; + } + // don't need to copy up value, it's only used by this + // next call, and when that gets to the bottom there + // won't be any more recursion + n.weight--; + this->delete_internal(&n.right, 0, &n, rebalance_subtree); + } } else { - if (*rebalance_subtree == nullptr && this->will_need_rebalance(*subtreep, 0, 1)) { + n.weight--; + if (*rebalance_subtree == nullptr && + this->will_need_rebalance(*subtreep, 0, -1)) { *rebalance_subtree = subtreep; } - const uint32_t sub_index = idx - this->nweight(n.left) - 1; - this->insert_internal(&n.right, value, sub_index, rebalance_subtree); - } - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::set_at_internal_array(const omtdata_t &value, const uint32_t idx) { - this->d.a.values[this->d.a.start_idx + idx] = value; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::set_at_internal(const subtree &subtree, const omtdata_t &value, const uint32_t idx) { - paranoid_invariant(!subtree.is_null()); - omt_node &n = this->d.t.nodes[subtree.get_index()]; - const uint32_t leftweight = this->nweight(n.left); - if (idx < leftweight) { - this->set_at_internal(n.left, value, idx); - } else if (idx == leftweight) { - n.value = value; - } else { - this->set_at_internal(n.right, value, idx - leftweight - 1); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::delete_internal(subtree *const subtreep, const uint32_t idx, omt_node *const copyn, subtree **const rebalance_subtree) { - paranoid_invariant_notnull(subtreep); - paranoid_invariant_notnull(rebalance_subtree); - paranoid_invariant(!subtreep->is_null()); - omt_node &n = this->d.t.nodes[subtreep->get_index()]; - const uint32_t leftweight = this->nweight(n.left); - if (idx < leftweight) { - n.weight--; - if (*rebalance_subtree == nullptr && this->will_need_rebalance(*subtreep, -1, 0)) { - *rebalance_subtree = subtreep; - } - this->delete_internal(&n.left, idx, copyn, rebalance_subtree); - } else if (idx == leftweight) { - if (n.left.is_null()) { - const uint32_t oldidx = subtreep->get_index(); - *subtreep = n.right; - if (copyn != nullptr) { - copyn->value = n.value; + this->delete_internal( + &n.right, idx - leftweight - 1, copyn, rebalance_subtree); + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template < + typename iterate_extra_t, + int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> + int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_internal_array( + const uint32_t left, + const uint32_t right, + iterate_extra_t *const iterate_extra) const { + int r; + for (uint32_t i = left; i < right; ++i) { + r = f(this->d.a.values[this->d.a.start_idx + i], i, iterate_extra); + if (r != 0) { + return r; } - this->node_free(oldidx); - } else if (n.right.is_null()) { - const uint32_t oldidx = subtreep->get_index(); - *subtreep = n.left; - if (copyn != nullptr) { - copyn->value = n.value; + } + return 0; + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template <typename iterate_extra_t, + int (*f)(omtdata_t *, const uint32_t, iterate_extra_t *const)> + void omt<omtdata_t, omtdataout_t, supports_marks>::iterate_ptr_internal( + const uint32_t left, + const uint32_t right, + const subtree &st, + const uint32_t idx, + iterate_extra_t *const iterate_extra) { + if (!st.is_null()) { + omt_node &n = this->d.t.nodes[st.get_index()]; + const uint32_t idx_root = idx + this->nweight(n.left); + if (left < idx_root) { + this->iterate_ptr_internal<iterate_extra_t, f>( + left, right, n.left, idx, iterate_extra); } - this->node_free(oldidx); - } else { - if (*rebalance_subtree == nullptr && this->will_need_rebalance(*subtreep, 0, -1)) { - *rebalance_subtree = subtreep; + if (left <= idx_root && idx_root < right) { + int r = f(&n.value, idx_root, iterate_extra); + lazy_assert_zero(r); + } + if (idx_root + 1 < right) { + this->iterate_ptr_internal<iterate_extra_t, f>( + left, right, n.right, idx_root + 1, iterate_extra); } - // don't need to copy up value, it's only used by this - // next call, and when that gets to the bottom there - // won't be any more recursion - n.weight--; - this->delete_internal(&n.right, 0, &n, rebalance_subtree); - } - } else { - n.weight--; - if (*rebalance_subtree == nullptr && this->will_need_rebalance(*subtreep, 0, -1)) { - *rebalance_subtree = subtreep; - } - this->delete_internal(&n.right, idx - leftweight - 1, copyn, rebalance_subtree); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename iterate_extra_t, - int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> -int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_internal_array(const uint32_t left, const uint32_t right, - iterate_extra_t *const iterate_extra) const { - int r; - for (uint32_t i = left; i < right; ++i) { - r = f(this->d.a.values[this->d.a.start_idx + i], i, iterate_extra); - if (r != 0) { - return r; } } - return 0; -} -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename iterate_extra_t, - int (*f)(omtdata_t *, const uint32_t, iterate_extra_t *const)> -void omt<omtdata_t, omtdataout_t, supports_marks>::iterate_ptr_internal(const uint32_t left, const uint32_t right, - const subtree &subtree, const uint32_t idx, - iterate_extra_t *const iterate_extra) { - if (!subtree.is_null()) { - omt_node &n = this->d.t.nodes[subtree.get_index()]; + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template <typename iterate_extra_t, + int (*f)(omtdata_t *, const uint32_t, iterate_extra_t *const)> + void + omt<omtdata_t, omtdataout_t, supports_marks>::iterate_ptr_internal_array( + const uint32_t left, + const uint32_t right, + iterate_extra_t *const iterate_extra) { + for (uint32_t i = left; i < right; ++i) { + int r = + f(&this->d.a.values[this->d.a.start_idx + i], i, iterate_extra); + lazy_assert_zero(r); + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template < + typename iterate_extra_t, + int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> + int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_internal( + const uint32_t left, + const uint32_t right, + const subtree &st, + const uint32_t idx, + iterate_extra_t *const iterate_extra) const { + if (st.is_null()) { + return 0; + } + int r; + const omt_node &n = this->d.t.nodes[st.get_index()]; const uint32_t idx_root = idx + this->nweight(n.left); if (left < idx_root) { - this->iterate_ptr_internal<iterate_extra_t, f>(left, right, n.left, idx, iterate_extra); + r = this->iterate_internal<iterate_extra_t, f>( + left, right, n.left, idx, iterate_extra); + if (r != 0) { + return r; + } } if (left <= idx_root && idx_root < right) { - int r = f(&n.value, idx_root, iterate_extra); - lazy_assert_zero(r); + r = f(n.value, idx_root, iterate_extra); + if (r != 0) { + return r; + } } if (idx_root + 1 < right) { - this->iterate_ptr_internal<iterate_extra_t, f>(left, right, n.right, idx_root + 1, iterate_extra); - } - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename iterate_extra_t, - int (*f)(omtdata_t *, const uint32_t, iterate_extra_t *const)> -void omt<omtdata_t, omtdataout_t, supports_marks>::iterate_ptr_internal_array(const uint32_t left, const uint32_t right, - iterate_extra_t *const iterate_extra) { - for (uint32_t i = left; i < right; ++i) { - int r = f(&this->d.a.values[this->d.a.start_idx + i], i, iterate_extra); - lazy_assert_zero(r); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename iterate_extra_t, - int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> -int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_internal(const uint32_t left, const uint32_t right, - const subtree &subtree, const uint32_t idx, - iterate_extra_t *const iterate_extra) const { - if (subtree.is_null()) { return 0; } - int r; - const omt_node &n = this->d.t.nodes[subtree.get_index()]; - const uint32_t idx_root = idx + this->nweight(n.left); - if (left < idx_root) { - r = this->iterate_internal<iterate_extra_t, f>(left, right, n.left, idx, iterate_extra); - if (r != 0) { return r; } - } - if (left <= idx_root && idx_root < right) { - r = f(n.value, idx_root, iterate_extra); - if (r != 0) { return r; } - } - if (idx_root + 1 < right) { - return this->iterate_internal<iterate_extra_t, f>(left, right, n.right, idx_root + 1, iterate_extra); - } - return 0; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename iterate_extra_t, - int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> -int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_and_mark_range_internal(const uint32_t left, const uint32_t right, - const subtree &subtree, const uint32_t idx, - iterate_extra_t *const iterate_extra) { - paranoid_invariant(!subtree.is_null()); - int r; - omt_node &n = this->d.t.nodes[subtree.get_index()]; - const uint32_t idx_root = idx + this->nweight(n.left); - if (left < idx_root && !n.left.is_null()) { - n.set_marks_below_bit(); - r = this->iterate_and_mark_range_internal<iterate_extra_t, f>(left, right, n.left, idx, iterate_extra); - if (r != 0) { return r; } - } - if (left <= idx_root && idx_root < right) { - n.set_marked_bit(); - r = f(n.value, idx_root, iterate_extra); - if (r != 0) { return r; } - } - if (idx_root + 1 < right && !n.right.is_null()) { - n.set_marks_below_bit(); - return this->iterate_and_mark_range_internal<iterate_extra_t, f>(left, right, n.right, idx_root + 1, iterate_extra); - } - return 0; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename iterate_extra_t, - int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> -int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_over_marked_internal(const subtree &subtree, const uint32_t idx, - iterate_extra_t *const iterate_extra) const { - if (subtree.is_null()) { return 0; } - int r; - const omt_node &n = this->d.t.nodes[subtree.get_index()]; - const uint32_t idx_root = idx + this->nweight(n.left); - if (n.get_marks_below()) { - r = this->iterate_over_marked_internal<iterate_extra_t, f>(n.left, idx, iterate_extra); - if (r != 0) { return r; } - } - if (n.get_marked()) { - r = f(n.value, idx_root, iterate_extra); - if (r != 0) { return r; } - } - if (n.get_marks_below()) { - return this->iterate_over_marked_internal<iterate_extra_t, f>(n.right, idx_root + 1, iterate_extra); - } - return 0; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::fetch_internal_array(const uint32_t i, omtdataout_t *const value) const { - if (value != nullptr) { - copyout(value, &this->d.a.values[this->d.a.start_idx + i]); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::fetch_internal(const subtree &subtree, const uint32_t i, omtdataout_t *const value) const { - omt_node &n = this->d.t.nodes[subtree.get_index()]; - const uint32_t leftweight = this->nweight(n.left); - if (i < leftweight) { - this->fetch_internal(n.left, i, value); - } else if (i == leftweight) { - if (value != nullptr) { - copyout(value, &n); - } - } else { - this->fetch_internal(n.right, i - leftweight - 1, value); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::fill_array_with_subtree_idxs(node_idx *const array, const subtree &subtree) const { - if (!subtree.is_null()) { - const omt_node &tree = this->d.t.nodes[subtree.get_index()]; - this->fill_array_with_subtree_idxs(&array[0], tree.left); - array[this->nweight(tree.left)] = subtree.get_index(); - this->fill_array_with_subtree_idxs(&array[this->nweight(tree.left) + 1], tree.right); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::rebuild_subtree_from_idxs(subtree *const subtree, const node_idx *const idxs, const uint32_t numvalues) { - if (numvalues==0) { - subtree->set_to_null(); - } else { - uint32_t halfway = numvalues/2; - subtree->set_index(idxs[halfway]); - //node_idx newidx = idxs[halfway]; - omt_node &newnode = this->d.t.nodes[subtree->get_index()]; - newnode.weight = numvalues; - // value is already in there. - this->rebuild_subtree_from_idxs(&newnode.left, &idxs[0], halfway); - this->rebuild_subtree_from_idxs(&newnode.right, &idxs[halfway+1], numvalues-(halfway+1)); - //n_idx = newidx; - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::rebalance(subtree *const subtree) { - node_idx idx = subtree->get_index(); - if (idx==this->d.t.root.get_index()) { - //Try to convert to an array. - //If this fails, (malloc) nothing will have changed. - //In the failure case we continue on to the standard rebalance - //algorithm. - this->convert_to_array(); - if (supports_marks) { - this->convert_to_tree(); + return this->iterate_internal<iterate_extra_t, f>( + left, right, n.right, idx_root + 1, iterate_extra); } - } else { - const omt_node &n = this->d.t.nodes[idx]; - node_idx *tmp_array; - size_t mem_needed = n.weight * (sizeof tmp_array[0]); - size_t mem_free = (this->capacity - this->d.t.free_idx) * (sizeof this->d.t.nodes[0]); - bool malloced; - if (mem_needed<=mem_free) { - //There is sufficient free space at the end of the nodes array - //to hold enough node indexes to rebalance. - malloced = false; - tmp_array = reinterpret_cast<node_idx *>(&this->d.t.nodes[this->d.t.free_idx]); - } - else { - malloced = true; - XMALLOC_N(n.weight, tmp_array); - } - this->fill_array_with_subtree_idxs(tmp_array, *subtree); - this->rebuild_subtree_from_idxs(subtree, tmp_array, n.weight); - if (malloced) toku_free(tmp_array); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::copyout(omtdata_t *const out, const omt_node *const n) { - *out = n->value; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::copyout(omtdata_t **const out, omt_node *const n) { - *out = &n->value; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::copyout(omtdata_t *const out, const omtdata_t *const stored_value_ptr) { - *out = *stored_value_ptr; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::copyout(omtdata_t **const out, omtdata_t *const stored_value_ptr) { - *out = stored_value_ptr; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename omtcmp_t, - int (*h)(const omtdata_t &, const omtcmp_t &)> -int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_zero_array(const omtcmp_t &extra, omtdataout_t *const value, uint32_t *const idxp) const { - paranoid_invariant_notnull(idxp); - uint32_t min = this->d.a.start_idx; - uint32_t limit = this->d.a.start_idx + this->d.a.num_values; - uint32_t best_pos = subtree::NODE_NULL; - uint32_t best_zero = subtree::NODE_NULL; - - while (min!=limit) { - uint32_t mid = (min + limit) / 2; - int hv = h(this->d.a.values[mid], extra); - if (hv<0) { - min = mid+1; - } - else if (hv>0) { - best_pos = mid; - limit = mid; - } - else { - best_zero = mid; - limit = mid; - } - } - if (best_zero!=subtree::NODE_NULL) { - //Found a zero - if (value != nullptr) { - copyout(value, &this->d.a.values[best_zero]); + return 0; + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template < + typename iterate_extra_t, + int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> + int omt<omtdata_t, omtdataout_t, supports_marks>:: + iterate_and_mark_range_internal(const uint32_t left, + const uint32_t right, + const subtree &st, + const uint32_t idx, + iterate_extra_t *const iterate_extra) { + paranoid_invariant(!st.is_null()); + int r; + omt_node &n = this->d.t.nodes[st.get_index()]; + const uint32_t idx_root = idx + this->nweight(n.left); + if (left < idx_root && !n.left.is_null()) { + n.set_marks_below_bit(); + r = this->iterate_and_mark_range_internal<iterate_extra_t, f>( + left, right, n.left, idx, iterate_extra); + if (r != 0) { + return r; + } + } + if (left <= idx_root && idx_root < right) { + n.set_marked_bit(); + r = f(n.value, idx_root, iterate_extra); + if (r != 0) { + return r; + } + } + if (idx_root + 1 < right && !n.right.is_null()) { + n.set_marks_below_bit(); + return this->iterate_and_mark_range_internal<iterate_extra_t, f>( + left, right, n.right, idx_root + 1, iterate_extra); } - *idxp = best_zero - this->d.a.start_idx; return 0; } - if (best_pos!=subtree::NODE_NULL) *idxp = best_pos - this->d.a.start_idx; - else *idxp = this->d.a.num_values; - return DB_NOTFOUND; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename omtcmp_t, - int (*h)(const omtdata_t &, const omtcmp_t &)> -int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_zero(const subtree &subtree, const omtcmp_t &extra, omtdataout_t *const value, uint32_t *const idxp) const { - paranoid_invariant_notnull(idxp); - if (subtree.is_null()) { - *idxp = 0; - return DB_NOTFOUND; + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template < + typename iterate_extra_t, + int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> + int + omt<omtdata_t, omtdataout_t, supports_marks>::iterate_over_marked_internal( + const subtree &st, + const uint32_t idx, + iterate_extra_t *const iterate_extra) const { + if (st.is_null()) { + return 0; + } + int r; + const omt_node &n = this->d.t.nodes[st.get_index()]; + const uint32_t idx_root = idx + this->nweight(n.left); + if (n.get_marks_below()) { + r = this->iterate_over_marked_internal<iterate_extra_t, f>( + n.left, idx, iterate_extra); + if (r != 0) { + return r; + } + } + if (n.get_marked()) { + r = f(n.value, idx_root, iterate_extra); + if (r != 0) { + return r; + } + } + if (n.get_marks_below()) { + return this->iterate_over_marked_internal<iterate_extra_t, f>( + n.right, idx_root + 1, iterate_extra); + } + return 0; } - omt_node &n = this->d.t.nodes[subtree.get_index()]; - int hv = h(n.value, extra); - if (hv<0) { - int r = this->find_internal_zero<omtcmp_t, h>(n.right, extra, value, idxp); - *idxp += this->nweight(n.left)+1; - return r; - } else if (hv>0) { - return this->find_internal_zero<omtcmp_t, h>(n.left, extra, value, idxp); - } else { - int r = this->find_internal_zero<omtcmp_t, h>(n.left, extra, value, idxp); - if (r==DB_NOTFOUND) { - *idxp = this->nweight(n.left); + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::fetch_internal_array( + const uint32_t i, + omtdataout_t *const value) const { + if (value != nullptr) { + copyout(value, &this->d.a.values[this->d.a.start_idx + i]); + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::fetch_internal( + const subtree &st, + const uint32_t i, + omtdataout_t *const value) const { + omt_node &n = this->d.t.nodes[st.get_index()]; + const uint32_t leftweight = this->nweight(n.left); + if (i < leftweight) { + this->fetch_internal(n.left, i, value); + } else if (i == leftweight) { if (value != nullptr) { copyout(value, &n); } - r = 0; + } else { + this->fetch_internal(n.right, i - leftweight - 1, value); } - return r; } -} -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename omtcmp_t, - int (*h)(const omtdata_t &, const omtcmp_t &)> -int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_plus_array(const omtcmp_t &extra, omtdataout_t *const value, uint32_t *const idxp) const { - paranoid_invariant_notnull(idxp); - uint32_t min = this->d.a.start_idx; - uint32_t limit = this->d.a.start_idx + this->d.a.num_values; - uint32_t best = subtree::NODE_NULL; + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void + omt<omtdata_t, omtdataout_t, supports_marks>::fill_array_with_subtree_idxs( + node_idx *const array, + const subtree &st) const { + if (!st.is_null()) { + const omt_node &tree = this->d.t.nodes[st.get_index()]; + this->fill_array_with_subtree_idxs(&array[0], tree.left); + array[this->nweight(tree.left)] = st.get_index(); + this->fill_array_with_subtree_idxs( + &array[this->nweight(tree.left) + 1], tree.right); + } + } - while (min != limit) { - const uint32_t mid = (min + limit) / 2; - const int hv = h(this->d.a.values[mid], extra); - if (hv > 0) { - best = mid; - limit = mid; + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void + omt<omtdata_t, omtdataout_t, supports_marks>::rebuild_subtree_from_idxs( + subtree *const st, + const node_idx *const idxs, + const uint32_t numvalues) { + if (numvalues == 0) { + st->set_to_null(); } else { - min = mid + 1; + uint32_t halfway = numvalues / 2; + st->set_index(idxs[halfway]); + // node_idx newidx = idxs[halfway]; + omt_node &newnode = this->d.t.nodes[st->get_index()]; + newnode.weight = numvalues; + // value is already in there. + this->rebuild_subtree_from_idxs(&newnode.left, &idxs[0], halfway); + this->rebuild_subtree_from_idxs( + &newnode.right, &idxs[halfway + 1], numvalues - (halfway + 1)); + // n_idx = newidx; } } - if (best == subtree::NODE_NULL) { return DB_NOTFOUND; } - if (value != nullptr) { - copyout(value, &this->d.a.values[best]); - } - *idxp = best - this->d.a.start_idx; - return 0; -} -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename omtcmp_t, - int (*h)(const omtdata_t &, const omtcmp_t &)> -int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_plus(const subtree &subtree, const omtcmp_t &extra, omtdataout_t *const value, uint32_t *const idxp) const { - paranoid_invariant_notnull(idxp); - if (subtree.is_null()) { - return DB_NOTFOUND; + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::rebalance( + subtree *const st) { + node_idx idx = st->get_index(); + if (idx == this->d.t.root.get_index()) { + // Try to convert to an array. + // If this fails, (malloc) nothing will have changed. + // In the failure case we continue on to the standard rebalance + // algorithm. + this->convert_to_array(); + if (supports_marks) { + this->convert_to_tree(); + } + } else { + const omt_node &n = this->d.t.nodes[idx]; + node_idx *tmp_array; + size_t mem_needed = n.weight * (sizeof tmp_array[0]); + size_t mem_free = (this->capacity - this->d.t.free_idx) * + (sizeof this->d.t.nodes[0]); + bool malloced; + if (mem_needed <= mem_free) { + // There is sufficient free space at the end of the nodes array + // to hold enough node indexes to rebalance. + malloced = false; + tmp_array = reinterpret_cast<node_idx *>( + &this->d.t.nodes[this->d.t.free_idx]); + } else { + malloced = true; + XMALLOC_N(n.weight, tmp_array); + } + this->fill_array_with_subtree_idxs(tmp_array, *st); + this->rebuild_subtree_from_idxs(st, tmp_array, n.weight); + if (malloced) + toku_free(tmp_array); + } } - omt_node *const n = &this->d.t.nodes[subtree.get_index()]; - int hv = h(n->value, extra); - int r; - if (hv > 0) { - r = this->find_internal_plus<omtcmp_t, h>(n->left, extra, value, idxp); - if (r == DB_NOTFOUND) { - *idxp = this->nweight(n->left); - if (value != nullptr) { - copyout(value, n); + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::copyout( + omtdata_t *const out, + const omt_node *const n) { + *out = n->value; + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::copyout( + omtdata_t **const out, + omt_node *const n) { + *out = &n->value; + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::copyout( + omtdata_t *const out, + const omtdata_t *const stored_value_ptr) { + *out = *stored_value_ptr; + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::copyout( + omtdata_t **const out, + omtdata_t *const stored_value_ptr) { + *out = stored_value_ptr; + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template <typename omtcmp_t, int (*h)(const omtdata_t &, const omtcmp_t &)> + int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_zero_array( + const omtcmp_t &extra, + omtdataout_t *const value, + uint32_t *const idxp) const { + paranoid_invariant_notnull(idxp); + uint32_t min = this->d.a.start_idx; + uint32_t limit = this->d.a.start_idx + this->d.a.num_values; + uint32_t best_pos = subtree::NODE_NULL; + uint32_t best_zero = subtree::NODE_NULL; + + while (min != limit) { + uint32_t mid = (min + limit) / 2; + int hv = h(this->d.a.values[mid], extra); + if (hv < 0) { + min = mid + 1; + } else if (hv > 0) { + best_pos = mid; + limit = mid; + } else { + best_zero = mid; + limit = mid; } - r = 0; } - } else { - r = this->find_internal_plus<omtcmp_t, h>(n->right, extra, value, idxp); - if (r == 0) { - *idxp += this->nweight(n->left) + 1; + if (best_zero != subtree::NODE_NULL) { + // Found a zero + if (value != nullptr) { + copyout(value, &this->d.a.values[best_zero]); + } + *idxp = best_zero - this->d.a.start_idx; + return 0; } + if (best_pos != subtree::NODE_NULL) + *idxp = best_pos - this->d.a.start_idx; + else + *idxp = this->d.a.num_values; + return DB_NOTFOUND; } - return r; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename omtcmp_t, - int (*h)(const omtdata_t &, const omtcmp_t &)> -int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_minus_array(const omtcmp_t &extra, omtdataout_t *const value, uint32_t *const idxp) const { - paranoid_invariant_notnull(idxp); - uint32_t min = this->d.a.start_idx; - uint32_t limit = this->d.a.start_idx + this->d.a.num_values; - uint32_t best = subtree::NODE_NULL; - while (min != limit) { - const uint32_t mid = (min + limit) / 2; - const int hv = h(this->d.a.values[mid], extra); + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template <typename omtcmp_t, int (*h)(const omtdata_t &, const omtcmp_t &)> + int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_zero( + const subtree &st, + const omtcmp_t &extra, + omtdataout_t *const value, + uint32_t *const idxp) const { + paranoid_invariant_notnull(idxp); + if (st.is_null()) { + *idxp = 0; + return DB_NOTFOUND; + } + omt_node &n = this->d.t.nodes[st.get_index()]; + int hv = h(n.value, extra); if (hv < 0) { - best = mid; - min = mid + 1; + int r = this->find_internal_zero<omtcmp_t, h>( + n.right, extra, value, idxp); + *idxp += this->nweight(n.left) + 1; + return r; + } else if (hv > 0) { + return this->find_internal_zero<omtcmp_t, h>( + n.left, extra, value, idxp); } else { - limit = mid; + int r = this->find_internal_zero<omtcmp_t, h>( + n.left, extra, value, idxp); + if (r == DB_NOTFOUND) { + *idxp = this->nweight(n.left); + if (value != nullptr) { + copyout(value, &n); + } + r = 0; + } + return r; } } - if (best == subtree::NODE_NULL) { return DB_NOTFOUND; } - if (value != nullptr) { - copyout(value, &this->d.a.values[best]); - } - *idxp = best - this->d.a.start_idx; - return 0; -} -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename omtcmp_t, - int (*h)(const omtdata_t &, const omtcmp_t &)> -int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_minus(const subtree &subtree, const omtcmp_t &extra, omtdataout_t *const value, uint32_t *const idxp) const { - paranoid_invariant_notnull(idxp); - if (subtree.is_null()) { - return DB_NOTFOUND; + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template <typename omtcmp_t, int (*h)(const omtdata_t &, const omtcmp_t &)> + int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_plus_array( + const omtcmp_t &extra, + omtdataout_t *const value, + uint32_t *const idxp) const { + paranoid_invariant_notnull(idxp); + uint32_t min = this->d.a.start_idx; + uint32_t limit = this->d.a.start_idx + this->d.a.num_values; + uint32_t best = subtree::NODE_NULL; + + while (min != limit) { + const uint32_t mid = (min + limit) / 2; + const int hv = h(this->d.a.values[mid], extra); + if (hv > 0) { + best = mid; + limit = mid; + } else { + min = mid + 1; + } + } + if (best == subtree::NODE_NULL) { + return DB_NOTFOUND; + } + if (value != nullptr) { + copyout(value, &this->d.a.values[best]); + } + *idxp = best - this->d.a.start_idx; + return 0; } - omt_node *const n = &this->d.t.nodes[subtree.get_index()]; - int hv = h(n->value, extra); - if (hv < 0) { - int r = this->find_internal_minus<omtcmp_t, h>(n->right, extra, value, idxp); - if (r == 0) { - *idxp += this->nweight(n->left) + 1; - } else if (r == DB_NOTFOUND) { - *idxp = this->nweight(n->left); - if (value != nullptr) { - copyout(value, n); + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template <typename omtcmp_t, int (*h)(const omtdata_t &, const omtcmp_t &)> + int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_plus( + const subtree &st, + const omtcmp_t &extra, + omtdataout_t *const value, + uint32_t *const idxp) const { + paranoid_invariant_notnull(idxp); + if (st.is_null()) { + return DB_NOTFOUND; + } + omt_node *const n = &this->d.t.nodes[st.get_index()]; + int hv = h(n->value, extra); + int r; + if (hv > 0) { + r = this->find_internal_plus<omtcmp_t, h>( + n->left, extra, value, idxp); + if (r == DB_NOTFOUND) { + *idxp = this->nweight(n->left); + if (value != nullptr) { + copyout(value, n); + } + r = 0; + } + } else { + r = this->find_internal_plus<omtcmp_t, h>( + n->right, extra, value, idxp); + if (r == 0) { + *idxp += this->nweight(n->left) + 1; } - r = 0; } return r; - } else { - return this->find_internal_minus<omtcmp_t, h>(n->left, extra, value, idxp); } -} -} // namespace toku + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template <typename omtcmp_t, int (*h)(const omtdata_t &, const omtcmp_t &)> + int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_minus_array( + const omtcmp_t &extra, + omtdataout_t *const value, + uint32_t *const idxp) const { + paranoid_invariant_notnull(idxp); + uint32_t min = this->d.a.start_idx; + uint32_t limit = this->d.a.start_idx + this->d.a.num_values; + uint32_t best = subtree::NODE_NULL; + + while (min != limit) { + const uint32_t mid = (min + limit) / 2; + const int hv = h(this->d.a.values[mid], extra); + if (hv < 0) { + best = mid; + min = mid + 1; + } else { + limit = mid; + } + } + if (best == subtree::NODE_NULL) { + return DB_NOTFOUND; + } + if (value != nullptr) { + copyout(value, &this->d.a.values[best]); + } + *idxp = best - this->d.a.start_idx; + return 0; + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template <typename omtcmp_t, int (*h)(const omtdata_t &, const omtcmp_t &)> + int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_minus( + const subtree &st, + const omtcmp_t &extra, + omtdataout_t *const value, + uint32_t *const idxp) const { + paranoid_invariant_notnull(idxp); + if (st.is_null()) { + return DB_NOTFOUND; + } + omt_node *const n = &this->d.t.nodes[st.get_index()]; + int hv = h(n->value, extra); + if (hv < 0) { + int r = this->find_internal_minus<omtcmp_t, h>( + n->right, extra, value, idxp); + if (r == 0) { + *idxp += this->nweight(n->left) + 1; + } else if (r == DB_NOTFOUND) { + *idxp = this->nweight(n->left); + if (value != nullptr) { + copyout(value, n); + } + r = 0; + } + return r; + } else { + return this->find_internal_minus<omtcmp_t, h>( + n->left, extra, value, idxp); + } + } +} // namespace toku diff --git a/storage/tokudb/PerconaFT/util/omt.h b/storage/tokudb/PerconaFT/util/omt.h index c7ed2ca546f..dc2fd9b7162 100644 --- a/storage/tokudb/PerconaFT/util/omt.h +++ b/storage/tokudb/PerconaFT/util/omt.h @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/ha_tokudb.cc b/storage/tokudb/ha_tokudb.cc index 548ac5c7b09..babbe825f2e 100644 --- a/storage/tokudb/ha_tokudb.cc +++ b/storage/tokudb/ha_tokudb.cc @@ -7252,6 +7252,16 @@ int ha_tokudb::create( tokudb_trx_data *trx = NULL; THD* thd = ha_thd(); + String database_name, table_name, dictionary_name; + tokudb_split_dname(name, database_name, table_name, dictionary_name); + if (database_name.is_empty() || table_name.is_empty()) { + push_warning_printf(thd, + Sql_condition::WARN_LEVEL_WARN, + ER_TABLE_NAME, + "TokuDB: Table Name or Database Name is empty"); + DBUG_RETURN(ER_TABLE_NAME); + } + memset(&kc_info, 0, sizeof(kc_info)); #if 100000 <= MYSQL_VERSION_ID && MYSQL_VERSION_ID <= 100999 diff --git a/storage/tokudb/hatoku_hton.cc b/storage/tokudb/hatoku_hton.cc index 610c9e07be0..a1d6597e33a 100644 --- a/storage/tokudb/hatoku_hton.cc +++ b/storage/tokudb/hatoku_hton.cc @@ -575,10 +575,10 @@ static int tokudb_init_func(void *p) { db_env->set_update(db_env, tokudb_update_fun); - db_env_set_direct_io(tokudb::sysvars::directio == TRUE); + db_env_set_direct_io(tokudb::sysvars::directio); db_env_set_compress_buffers_before_eviction( - tokudb::sysvars::compress_buffers_before_eviction == TRUE); + tokudb::sysvars::compress_buffers_before_eviction); db_env->change_fsync_log_period(db_env, tokudb::sysvars::fsync_log_period); diff --git a/storage/tokudb/hatoku_hton.h b/storage/tokudb/hatoku_hton.h index c5b6aab1769..e90af067b00 100644 --- a/storage/tokudb/hatoku_hton.h +++ b/storage/tokudb/hatoku_hton.h @@ -190,7 +190,6 @@ inline bool tokudb_killed_thd_callback(void* extra, return thd_killed(thd) != 0; } -extern HASH tokudb_open_tables; extern const char* tokudb_hton_name; extern int tokudb_hton_initialized; extern tokudb::thread::rwlock_t tokudb_hton_initialized_lock; diff --git a/storage/tokudb/mysql-test/tokudb_bugs/r/PS-4979.result b/storage/tokudb/mysql-test/tokudb_bugs/r/PS-4979.result new file mode 100644 index 00000000000..f0d2f93f630 --- /dev/null +++ b/storage/tokudb/mysql-test/tokudb_bugs/r/PS-4979.result @@ -0,0 +1,2 @@ +CREATE TABLE `#mysql50#q.q`(f1 INT KEY) ENGINE=TOKUDB; +ERROR HY000: Got error 1632 from storage engine diff --git a/storage/tokudb/mysql-test/tokudb_bugs/t/PS-4979.test b/storage/tokudb/mysql-test/tokudb_bugs/t/PS-4979.test new file mode 100644 index 00000000000..1e4b5d11922 --- /dev/null +++ b/storage/tokudb/mysql-test/tokudb_bugs/t/PS-4979.test @@ -0,0 +1,12 @@ +--source include/have_tokudb.inc +# PS-4979 : Dropping TokuDB table with non-alphanumeric characters could lead +# to a crash +# +# `#mysql50#q.q` is an invalid table name, but the server side doesn't detect it +# and complain. Instead it passes in an empty table name to the engine. The +# engine expects a table name in the form of a relative path like +# "./databasename/tablename". InnoDB detects this in parsing the table name +# during the creation and returns an error. + +--error ER_GET_ERRNO +CREATE TABLE `#mysql50#q.q`(f1 INT KEY) ENGINE=TOKUDB; diff --git a/storage/tokudb/tokudb_background.cc b/storage/tokudb/tokudb_background.cc index 13e0e9321cc..19f03dbca65 100644 --- a/storage/tokudb/tokudb_background.cc +++ b/storage/tokudb/tokudb_background.cc @@ -182,14 +182,14 @@ void* job_manager_t::real_thread_func() { if (res == tokudb::thread::semaphore_t::E_INTERRUPTED || _shutdown) { break; } else if (res == tokudb::thread::semaphore_t::E_SIGNALLED) { -#if TOKUDB_DEBUG +#if defined(TOKUDB_DEBUG) if (TOKUDB_UNLIKELY( tokudb::sysvars::debug_pause_background_job_manager)) { _sem.signal(); tokudb::time::sleep_microsec(250000); continue; } -#endif // TOKUDB_DEBUG +#endif // defined(TOKUDB_DEBUG) mutex_t_lock(_mutex); assert_debug(_background_jobs.size() > 0); diff --git a/storage/tokudb/tokudb_sysvars.cc b/storage/tokudb/tokudb_sysvars.cc index e8e9f908275..d1f58d012ec 100644 --- a/storage/tokudb/tokudb_sysvars.cc +++ b/storage/tokudb/tokudb_sysvars.cc @@ -662,13 +662,13 @@ static MYSQL_THDVAR_ULONGLONG( ~0ULL, 1); -static MYSQL_THDVAR_STR( - last_lock_timeout, - PLUGIN_VAR_MEMALLOC, - "last lock timeout", - NULL, - NULL, - NULL); +static MYSQL_THDVAR_STR(last_lock_timeout, + PLUGIN_VAR_MEMALLOC | PLUGIN_VAR_NOCMDOPT | + PLUGIN_VAR_READONLY, + "last lock timeout", + NULL, + NULL, + NULL); static MYSQL_THDVAR_BOOL( load_save_space, diff --git a/storage/tokudb/tokudb_sysvars.h b/storage/tokudb/tokudb_sysvars.h index d81d5fd7999..6f09f296a80 100644 --- a/storage/tokudb/tokudb_sysvars.h +++ b/storage/tokudb/tokudb_sysvars.h @@ -93,10 +93,10 @@ extern my_bool gdb_on_fatal; extern my_bool check_jemalloc; -#if TOKUDB_DEBUG +#if defined(TOKUDB_DEBUG) // used to control background job manager extern my_bool debug_pause_background_job_manager; -#endif // TOKUDB_DEBUG +#endif // defined(TOKUDB_DEBUG) // session/thread my_bool alter_print_error(THD* thd);

1 0

[Commits] 1abdc0e435e: 5.6.43
by Oleksandr Byelkin 24 Jan '19

24 Jan '19

revision-id: 1abdc0e435e4e7e71257e246972a3b3015df287c () parent(s): a9a0d0c3729ad3c6e295f68b6d4d5552b999a2e5 author: Oleksandr Byelkin committer: Oleksandr Byelkin timestamp: 2019-01-24 15:47:27 +0100 message: 5.6.43 --- mysql-test/suite/perfschema/r/dml_setup_instruments.result | 4 +++- mysql-test/suite/perfschema/t/dml_setup_instruments.test | 5 ++++- 2 files changed, 7 insertions(+), 2 deletions(-) diff --git a/mysql-test/suite/perfschema/r/dml_setup_instruments.result b/mysql-test/suite/perfschema/r/dml_setup_instruments.result index 310ff60aa5b..7bc7ca785d6 100644 --- a/mysql-test/suite/perfschema/r/dml_setup_instruments.result +++ b/mysql-test/suite/perfschema/r/dml_setup_instruments.result @@ -16,7 +16,9 @@ wait/synch/mutex/sql/LOCK_crypt YES YES wait/synch/mutex/sql/LOCK_delayed_create YES YES select * from performance_schema.setup_instruments where name like 'Wait/Synch/Rwlock/sql/%' - and name not in ('wait/synch/rwlock/sql/CRYPTO_dynlock_value::lock') + and name not in ( +'wait/synch/rwlock/sql/CRYPTO_dynlock_value::lock', +'wait/synch/rwlock/sql/LOCK_named_pipe_full_access_group') order by name limit 10; NAME ENABLED TIMED wait/synch/rwlock/sql/Binlog_relay_IO_delegate::lock YES YES diff --git a/mysql-test/suite/perfschema/t/dml_setup_instruments.test b/mysql-test/suite/perfschema/t/dml_setup_instruments.test index 8a4f11ba51f..18c260e1555 100644 --- a/mysql-test/suite/perfschema/t/dml_setup_instruments.test +++ b/mysql-test/suite/perfschema/t/dml_setup_instruments.test @@ -22,10 +22,13 @@ select * from performance_schema.setup_instruments order by name limit 10; # CRYPTO_dynlock_value::lock is dependent on the build (SSL) +# LOCK_named_pipe_full_access_group is dependent on the build (Windows) select * from performance_schema.setup_instruments where name like 'Wait/Synch/Rwlock/sql/%' - and name not in ('wait/synch/rwlock/sql/CRYPTO_dynlock_value::lock') + and name not in ( + 'wait/synch/rwlock/sql/CRYPTO_dynlock_value::lock', + 'wait/synch/rwlock/sql/LOCK_named_pipe_full_access_group') order by name limit 10; # COND_handler_count is dependent on the build (Windows only)

1 0

[Commits] 720f7ad1776: Merge branch '5.5' into 10.0
by Oleksandr Byelkin 24 Jan '19

24 Jan '19

revision-id: 720f7ad17762f5c7e17096b883bca626e064bb0d (mariadb-10.0.37-54-g720f7ad1776) parent(s): edeba0c8733409865c3abcab881af0d48b7be94f ad220b96fb01dbb6acf7e51bdd8d4d6362d96ea7 author: Oleksandr Byelkin committer: Oleksandr Byelkin timestamp: 2019-01-24 12:28:54 +0100 message: Merge branch '5.5' into 10.0 client/mysqltest.cc | 5 +++ cmake/ssl.cmake | 11 +++++- include/my_valgrind.h | 4 +- mysql-test/r/row-checksum-old.result | 16 ++++++++ mysql-test/r/row-checksum.result | 16 ++++++++ mysql-test/r/subselect2.result | 22 +++++++++++ mysql-test/t/row-checksum.test | 17 +++++++++ mysql-test/t/subselect2.test | 20 ++++++++++ scripts/mysql_install_db.sh | 19 +++++++--- sql/CMakeLists.txt | 2 +- sql/log.cc | 6 +-- sql/mysql_install_db.cc | 72 +++++++++++++++++++++++++++++++++--- sql/sql_repl.cc | 6 +-- sql/sql_table.cc | 5 ++- sql/sql_yacc.yy | 22 ++++++----- support-files/mysql.server.sh | 6 ++- unittest/mysys/thr_template.c | 4 +- win/packaging/heidisql.cmake | 2 +- 18 files changed, 219 insertions(+), 36 deletions(-) diff --cc cmake/ssl.cmake index c76e73927c0,60d2cb48387..6985932d165 --- a/cmake/ssl.cmake +++ b/cmake/ssl.cmake @@@ -84,121 -62,35 +84,130 @@@ MACRO (MYSQL_CHECK_SSL ENDIF() ENDIF() + # See if WITH_SSL is of the form </path/to/custom/installation> + FILE(GLOB WITH_SSL_HEADER ${WITH_SSL}/include/openssl/ssl.h) + IF (WITH_SSL_HEADER) + SET(WITH_SSL_PATH ${WITH_SSL} CACHE PATH "path to custom SSL installation") + ENDIF() + IF(WITH_SSL STREQUAL "bundled") MYSQL_USE_BUNDLED_SSL() - ELSEIF(WITH_SSL STREQUAL "system" OR WITH_SSL STREQUAL "yes") - # Check for system library - SET(OPENSSL_FIND_QUIETLY TRUE) - INCLUDE(FindOpenSSL) - FIND_LIBRARY(CRYPTO_LIBRARY crypto) - MARK_AS_ADVANCED(CRYPTO_LIBRARY) - INCLUDE(CheckSymbolExists) - INCLUDE(CheckCSourceCompiles) - SET(CMAKE_REQUIRED_INCLUDES ${OPENSSL_INCLUDE_DIR}) - SET(CMAKE_REQUIRED_LIBRARIES ${OPENSSL_LIBRARIES}) - CHECK_SYMBOL_EXISTS(SHA512_DIGEST_LENGTH "openssl/sha.h" - HAVE_SHA512_DIGEST_LENGTH) - CHECK_SYMBOL_EXISTS(ERR_remove_thread_state "openssl/err.h" - HAVE_ERR_remove_thread_state) - CHECK_C_SOURCE_COMPILES(" - #include <openssl/dh.h> - int main() - { - DH dh; - return sizeof(dh.version); - }" OLD_OPENSSL_API) - SET(CMAKE_REQUIRED_INCLUDES) - SET(CMAKE_REQUIRED_LIBRARIES) + # Reset some variables, in case we switch from /path/to/ssl to "bundled". + IF (WITH_SSL_PATH) + UNSET(WITH_SSL_PATH) + UNSET(WITH_SSL_PATH CACHE) + ENDIF() + IF (OPENSSL_ROOT_DIR) + UNSET(OPENSSL_ROOT_DIR) + UNSET(OPENSSL_ROOT_DIR CACHE) + ENDIF() + IF (OPENSSL_INCLUDE_DIR) + UNSET(OPENSSL_INCLUDE_DIR) + UNSET(OPENSSL_INCLUDE_DIR CACHE) + ENDIF() + IF (WIN32 AND OPENSSL_APPLINK_C) + UNSET(OPENSSL_APPLINK_C) + UNSET(OPENSSL_APPLINK_C CACHE) + ENDIF() + IF (OPENSSL_LIBRARIES) + UNSET(OPENSSL_LIBRARIES) + UNSET(OPENSSL_LIBRARIES CACHE) + ENDIF() + ELSEIF(WITH_SSL STREQUAL "system" OR + WITH_SSL STREQUAL "yes" OR + WITH_SSL_PATH + ) + # First search in WITH_SSL_PATH. + FIND_PATH(OPENSSL_ROOT_DIR + NAMES include/openssl/ssl.h + NO_CMAKE_PATH + NO_CMAKE_ENVIRONMENT_PATH + HINTS ${WITH_SSL_PATH} + ) + # Then search in standard places (if not found above). + FIND_PATH(OPENSSL_ROOT_DIR + NAMES include/openssl/ssl.h + ) + + FIND_PATH(OPENSSL_INCLUDE_DIR + NAMES openssl/ssl.h + HINTS ${OPENSSL_ROOT_DIR}/include + ) + + IF (WIN32) + FIND_FILE(OPENSSL_APPLINK_C + NAMES openssl/applink.c + HINTS ${OPENSSL_ROOT_DIR}/include + ) + MESSAGE(STATUS "OPENSSL_APPLINK_C ${OPENSSL_APPLINK_C}") + ENDIF() + + # On mac this list is <.dylib;.so;.a> + # We prefer static libraries, so we revert it here. + IF (WITH_SSL_PATH) + LIST(REVERSE CMAKE_FIND_LIBRARY_SUFFIXES) + ENDIF() + MESSAGE(STATUS "suffixes <${CMAKE_FIND_LIBRARY_SUFFIXES}>") + FIND_LIBRARY(OPENSSL_LIBRARIES + NAMES ssl ssleay32 ssleay32MD + HINTS ${OPENSSL_ROOT_DIR}/lib) + FIND_LIBRARY(CRYPTO_LIBRARY + NAMES crypto libeay32 + HINTS ${OPENSSL_ROOT_DIR}/lib) + IF (WITH_SSL_PATH) + LIST(REVERSE CMAKE_FIND_LIBRARY_SUFFIXES) + ENDIF() + + IF(OPENSSL_INCLUDE_DIR AND + OPENSSL_LIBRARIES AND + CRYPTO_LIBRARY + ) + # Verify version number. Version information looks like: + # #define OPENSSL_VERSION_NUMBER 0x1000103fL + # Encoded as MNNFFPPS: major minor fix patch status + FILE(STRINGS "${OPENSSL_INCLUDE_DIR}/openssl/opensslv.h" + OPENSSL_VERSION_NUMBER + REGEX "^#define[\t ]+OPENSSL_VERSION_NUMBER[\t ]+0x[0-9].*" + ) + STRING(REGEX REPLACE + "^.*OPENSSL_VERSION_NUMBER[\t ]+0x([0-9][0-9][0-9]).*$" "\\1" + OPENSSL_MAJOR_VERSION "${OPENSSL_VERSION_NUMBER}" + ) + INCLUDE(CheckSymbolExists) ++ INCLUDE(CheckCSourceCompiles) + SET(CMAKE_REQUIRED_INCLUDES ${OPENSSL_INCLUDE_DIR}) + CHECK_SYMBOL_EXISTS(SHA512_DIGEST_LENGTH "openssl/sha.h" + HAVE_SHA512_DIGEST_LENGTH) ++ CHECK_C_SOURCE_COMPILES(" ++ #include <openssl/dh.h> ++ int main() ++ { ++ DH dh; ++ return sizeof(dh.version); ++ }" OLD_OPENSSL_API) ++ + SET(OPENSSL_FOUND TRUE) + ELSE() + SET(OPENSSL_FOUND FALSE) + ENDIF() + - IF(OPENSSL_FOUND AND OPENSSL_MAJOR_VERSION STRLESS "101" AND + IF(OPENSSL_FOUND AND OLD_OPENSSL_API AND - CRYPTO_LIBRARY AND HAVE_SHA512_DIGEST_LENGTH) + HAVE_SHA512_DIGEST_LENGTH) + MESSAGE(STATUS "OPENSSL_INCLUDE_DIR = ${OPENSSL_INCLUDE_DIR}") + MESSAGE(STATUS "OPENSSL_LIBRARIES = ${OPENSSL_LIBRARIES}") + MESSAGE(STATUS "CRYPTO_LIBRARY = ${CRYPTO_LIBRARY}") + MESSAGE(STATUS "OPENSSL_MAJOR_VERSION = ${OPENSSL_MAJOR_VERSION}") + + SET(SSL_SOURCES "") SET(SSL_LIBRARIES ${OPENSSL_LIBRARIES} ${CRYPTO_LIBRARY}) + IF(CMAKE_SYSTEM_NAME MATCHES "SunOS") + SET(SSL_LIBRARIES ${SSL_LIBRARIES} ${LIBSOCKET}) + ENDIF() + IF(CMAKE_SYSTEM_NAME MATCHES "Linux") + SET(SSL_LIBRARIES ${SSL_LIBRARIES} ${LIBDL}) + ENDIF() + MESSAGE(STATUS "SSL_LIBRARIES = ${SSL_LIBRARIES}") SET(SSL_INCLUDE_DIRS ${OPENSSL_INCLUDE_DIR}) SET(SSL_INTERNAL_INCLUDE_DIRS "") SET(SSL_DEFINES "-DHAVE_OPENSSL") diff --cc sql/CMakeLists.txt index 60e9f05542a,6648b7a2612..187f021599c --- a/sql/CMakeLists.txt +++ b/sql/CMakeLists.txt @@@ -425,8 -351,7 +425,8 @@@ IF(WIN32 ${CMAKE_CURRENT_BINARY_DIR}/mysql_bootstrap_sql.c COMPONENT Server ) + SET_TARGET_PROPERTIES(mysql_install_db PROPERTIES COMPILE_FLAGS -DINSTALL_PLUGINDIR=${INSTALL_PLUGINDIR}) - TARGET_LINK_LIBRARIES(mysql_install_db mysys) + TARGET_LINK_LIBRARIES(mysql_install_db mysys shlwapi) ADD_LIBRARY(winservice STATIC winservice.c) TARGET_LINK_LIBRARIES(winservice shell32)

1 0

[Commits] c3a1cd35554: Silence "WSREP: Server initial position ..." message when wsrep-debug=OFF
by jan 24 Jan '19

24 Jan '19

revision-id: c3a1cd35554fb9bbd5b2086516678d2b7a7b1e48 (mariadb-10.4.1-110-gc3a1cd35554) parent(s): f7a511fb7a6c48a9d2c05d370d564c86e80bc2da author: Jan Lindström committer: Jan Lindström timestamp: 2019-01-24 10:47:19 +0200 message: Silence "WSREP: Server initial position ..." message when wsrep-debug=OFF --- sql/wsrep_mysqld.cc | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/sql/wsrep_mysqld.cc b/sql/wsrep_mysqld.cc index 73f201f12ca..2bb350cd45d 100644 --- a/sql/wsrep_mysqld.cc +++ b/sql/wsrep_mysqld.cc @@ -593,7 +593,7 @@ static std::string wsrep_server_working_dir() static wsrep::gtid wsrep_server_initial_position() { wsrep::gtid ret; - WSREP_INFO("Server initial position: %s", wsrep_start_position); + WSREP_DEBUG("Server initial position: %s", wsrep_start_position); std::istringstream is(wsrep_start_position); is >> ret; return ret;

1 0

[Commits] 501f5c98b2a: Move Galera disabled.def files from test directory to correct suite directory.
by jan 24 Jan '19

24 Jan '19

revision-id: 501f5c98b2aa4f46f39dae785ea9000921a48bc2 (mariadb-10.4.1-108-g501f5c98b2a) parent(s): 3238f2a6e93e0ed41f69badcc80af6f2618a810d author: Jan Lindström committer: Jan Lindström timestamp: 2019-01-24 09:14:30 +0200 message: Move Galera disabled.def files from test directory to correct suite directory. --- mysql-test/suite/galera_3nodes_sr/{t => }/disabled.def | 0 mysql-test/suite/galera_sr/{t => }/disabled.def | 0 2 files changed, 0 insertions(+), 0 deletions(-) diff --git a/mysql-test/suite/galera_3nodes_sr/t/disabled.def b/mysql-test/suite/galera_3nodes_sr/disabled.def similarity index 100% rename from mysql-test/suite/galera_3nodes_sr/t/disabled.def rename to mysql-test/suite/galera_3nodes_sr/disabled.def diff --git a/mysql-test/suite/galera_sr/t/disabled.def b/mysql-test/suite/galera_sr/disabled.def similarity index 100% rename from mysql-test/suite/galera_sr/t/disabled.def rename to mysql-test/suite/galera_sr/disabled.def

1 0

[Commits] b58448b10ed: MDEV-10963 Fragmented BINLOG query
by andrei.elkin＠pp.inet.fi 23 Jan '19

23 Jan '19

revision-id: b58448b10ed890d5cc0752a0bd3d9274673d1116 (mariadb-10.1.37-31-gb58448b10ed) parent(s): 541500295abdba7fa619065069291ac9c1dd6e83 author: Andrei Elkin committer: Andrei Elkin timestamp: 2019-01-23 13:49:38 +0200 message: MDEV-10963 Fragmented BINLOG query The problem was originally stated in http://bugs.mysql.com/bug.php?id=82212 The size of an base64-encoded Rows_log_event exceeds its vanilla byte representation in 4/3 times. When a binlogged event size is about 1GB mysqlbinlog generates a BINLOG query that can't be send out due to its size. It is fixed with fragmenting the BINLOG argument C-string into (approximate) halves when the base64 encoded event is over 1GB size. The mysqlbinlog in such case puts out SET @binlog_fragment_0='base64-encoded-fragment_0'; SET @binlog_fragment_1='base64-encoded-fragment_1'; BINLOG @binlog_fragment_0, @binlog_fragment_1; to represent a big BINLOG. For prompt memory release BINLOG handler is made to reset the BINLOG argument user variables in the middle of processing, as if @binlog_fragment_{0,1} = NULL is assigned. Notice the 2 fragments are enough, though the client and server still may need to tweak their @@max_allowed_packet to satisfy to the fragment size (which they would have to do anyway with greater number of fragments, should that be desired). On the lower level the following changes are made: Log_event::print_base64() remains to call encoder and store the encoded data into a cache but now *without* doing any formatting. The latter is left for time when the cache is copied to an output file (e.g mysqlbinlog output). No formatting behavior is also reflected by the change in the meaning of the last argument which specifies whether to cache the encoded data. Rows_log_event::print_helper() is made to invoke a specialized fragmented cache-to-file copying function which is copy_cache_to_file_wrapped() that takes care of fragmenting also optionally wraps encoded strings (fragments) into SQL stanzas. my_b_copy_to_file() is refactored to into my_b_copy_all_to_file(). The former function is generalized to accepts more a limit argument to constraint the copying and does not reinitialize anymore the cache into reading mode. The limit does not do any effect on the fully read cache. --- client/mysqlbinlog.cc | 21 ++- include/my_sys.h | 4 +- .../suite/binlog/r/binlog_base64_flag.result | 19 +++ .../binlog/r/binlog_mysqlbinlog_row_frag.result | 24 +++ mysql-test/suite/binlog/t/binlog_base64_flag.test | 22 +++ .../binlog/t/binlog_mysqlbinlog_row_frag.test | 45 ++++++ mysys/mf_iocache2.c | 61 ++++---- sql/item_func.cc | 2 +- sql/item_func.h | 4 + sql/log_event.cc | 169 +++++++++++++++++++-- sql/log_event.h | 13 +- sql/log_event_old.cc | 16 +- sql/sql_binlog.cc | 94 ++++++++++-- sql/sql_lex.h | 4 + sql/sql_yacc.yy | 11 +- unittest/sql/mf_iocache-t.cc | 70 ++++++++- 16 files changed, 511 insertions(+), 68 deletions(-) diff --git a/client/mysqlbinlog.cc b/client/mysqlbinlog.cc index bc13aa6c2cc..2c05bb806a9 100644 --- a/client/mysqlbinlog.cc +++ b/client/mysqlbinlog.cc @@ -72,6 +72,7 @@ ulong mysqld_net_retry_count = 10L; ulong open_files_limit; ulong opt_binlog_rows_event_max_size; ulonglong test_flags = 0; +ulong opt_binlog_rows_event_max_encoded_size= MAX_MAX_ALLOWED_PACKET; static uint opt_protocol= 0; static FILE *result_file; static char *result_file_name= 0; @@ -813,7 +814,12 @@ write_event_header_and_base64(Log_event *ev, FILE *result_file, /* Write header and base64 output to cache */ ev->print_header(head, print_event_info, FALSE); - ev->print_base64(body, print_event_info, FALSE); + + DBUG_ASSERT(print_event_info->base64_output_mode == BASE64_OUTPUT_ALWAYS); + + ev->print_base64(body, print_event_info, + print_event_info->base64_output_mode != + BASE64_OUTPUT_DECODE_ROWS); /* Read data from cache and write to result file */ if (copy_event_cache_to_file_and_reinit(head, result_file) || @@ -852,7 +858,9 @@ static bool print_base64(PRINT_EVENT_INFO *print_event_info, Log_event *ev) return 1; } ev->print(result_file, print_event_info); - return print_event_info->head_cache.error == -1; + return + print_event_info->head_cache.error == -1 || + print_event_info->body_cache.error == -1; } @@ -1472,6 +1480,15 @@ that may lead to an endless loop.", "This value must be a multiple of 256.", &opt_binlog_rows_event_max_size, &opt_binlog_rows_event_max_size, 0, GET_ULONG, REQUIRED_ARG, UINT_MAX, 256, ULONG_MAX, 0, 256, 0}, +#ifndef DBUG_OFF + {"debug-binlog-row-event-max-encoded-size", 0, + "The maximum size of base64-encoded rows-event in one BINLOG pseudo-query " + "instance. When the computed actual size exceeds the limit " + "the BINLOG's argument string is fragmented in two.", + &opt_binlog_rows_event_max_encoded_size, + &opt_binlog_rows_event_max_encoded_size, 0, + GET_ULONG, REQUIRED_ARG, UINT_MAX/4, 256, ULONG_MAX, 0, 256, 0}, +#endif {"verify-binlog-checksum", 'c', "Verify checksum binlog events.", (uchar**) &opt_verify_binlog_checksum, (uchar**) &opt_verify_binlog_checksum, 0, GET_BOOL, NO_ARG, 0, 0, 0, 0, 0, 0}, diff --git a/include/my_sys.h b/include/my_sys.h index 110a2ee9af3..c30580a8c06 100644 --- a/include/my_sys.h +++ b/include/my_sys.h @@ -602,7 +602,9 @@ static inline size_t my_b_bytes_in_cache(const IO_CACHE *info) return *info->current_end - *info->current_pos; } -int my_b_copy_to_file(IO_CACHE *cache, FILE *file); +int my_b_copy_to_file (IO_CACHE *cache, FILE *file, size_t count); +int my_b_copy_all_to_file(IO_CACHE *cache, FILE *file); + my_off_t my_b_append_tell(IO_CACHE* info); my_off_t my_b_safe_tell(IO_CACHE* info); /* picks the correct tell() */ int my_b_pread(IO_CACHE *info, uchar *Buffer, size_t Count, my_off_t pos); diff --git a/mysql-test/suite/binlog/r/binlog_base64_flag.result b/mysql-test/suite/binlog/r/binlog_base64_flag.result index d13e13c97b0..b97cf9072fa 100644 --- a/mysql-test/suite/binlog/r/binlog_base64_flag.result +++ b/mysql-test/suite/binlog/r/binlog_base64_flag.result @@ -28,6 +28,25 @@ a 1 1 3 +DELETE FROM t1 WHERE a=3; +BINLOG ' +ODdYRw8BAAAAZgAAAGoAAAABAAQANS4xLjIzLXJjLWRlYnVnLWxvZwAAAAAAAAAAAAAAAAAAAAAA +AAAAAAAAAAAAAAAAAAA4N1hHEzgNAAgAEgAEBAQEEgAAUwAEGggAAAAICAgC +'; +SET @binlog_fragment_0=' +TFtYRxMBAAAAKQAAAH8BAAAAABAAAAAAAAAABHRlc3QAAnQxAAEDAAE= +TFtYRxcBAAAAIgAAAKEBAAAQABAAAAAAAAEAAf/+AwAAAA== +'; +SET @binlog_fragment_1=''; +BINLOG @binlog_fragment_0, @binlog_fragment_1; +select * from t1; +a +1 +1 +3 +SELECT @binlog_fragment_0, @binlog_fragment_1 as 'NULL','NULL'; +@binlog_fragment_0 NULL NULL +NULL NULL NULL ==== Test --base64-output=never on a binlog with row events ==== /*!50530 SET @@SESSION.PSEUDO_SLAVE_MODE=1*/; /*!40019 SET @@session.max_insert_delayed_threads=0*/; diff --git a/mysql-test/suite/binlog/r/binlog_mysqlbinlog_row_frag.result b/mysql-test/suite/binlog/r/binlog_mysqlbinlog_row_frag.result new file mode 100644 index 00000000000..041be5ed09f --- /dev/null +++ b/mysql-test/suite/binlog/r/binlog_mysqlbinlog_row_frag.result @@ -0,0 +1,24 @@ +CREATE TABLE t (a TEXT); +RESET MASTER; +INSERT INTO t SET a=repeat('a', 1024); +SELECT a from t into @a; +FLUSH LOGS; +DELETE FROM t; +FOUND /BINLOG @binlog_fragment_0, @binlog_fragment_1/ in mysqlbinlog.sql +SELECT a LIKE @a as 'true' FROM t; +true +1 +BINLOG number-of-fragments must be exactly two +BINLOG @binlog_fragment; +ERROR 42000: You have an error in your SQL syntax; check the manual that corresponds to your MariaDB server version for the right syntax to use near '' at line 1 +BINLOG @binlog_fragment, @binlog_fragment, @binlog_fragment; +ERROR 42000: You have an error in your SQL syntax; check the manual that corresponds to your MariaDB server version for the right syntax to use near ' @binlog_fragment' at line 1 +SET @binlog_fragment_0='012345'; +SET @binlog_fragment_1='012345'; +BINLOG @binlog_fragment_0, @binlog_fragment_1; +ERROR 42000: You have an error in your SQL syntax; check the manual that corresponds to your MariaDB server version for the right syntax to use +SET @binlog_fragment_0='012345'; +BINLOG @binlog_fragment_0, @binlog_fragment_not_exist; +ERROR 42000: Incorrect argument type to variable 'binlog_fragment_not_exist' +# Cleanup +DROP TABLE t; diff --git a/mysql-test/suite/binlog/t/binlog_base64_flag.test b/mysql-test/suite/binlog/t/binlog_base64_flag.test index f8333315088..575a7307665 100644 --- a/mysql-test/suite/binlog/t/binlog_base64_flag.test +++ b/mysql-test/suite/binlog/t/binlog_base64_flag.test @@ -67,6 +67,28 @@ TFtYRxcBAAAAIgAAAKEBAAAQABAAAAAAAAEAAf/+AwAAAA== # The above line should succeed and 3 should be in the table select * from t1; +# The same as above with one-fragment BINLOG to prove +# equivalency with the fragmented BINLOG @frag_0, @frag_1. +DELETE FROM t1 WHERE a=3; +# This is a binlog statement containing a Format_description_log_event +# from the same version as the Table_map and Write_rows_log_event. +BINLOG ' +ODdYRw8BAAAAZgAAAGoAAAABAAQANS4xLjIzLXJjLWRlYnVnLWxvZwAAAAAAAAAAAAAAAAAAAAAA +AAAAAAAAAAAAAAAAAAA4N1hHEzgNAAgAEgAEBAQEEgAAUwAEGggAAAAICAgC +'; + +# This is a Table_map_log_event+Write_rows_log_event corresponding to: +# INSERT INTO TABLE test.t1 VALUES (3) +SET @binlog_fragment_0=' +TFtYRxMBAAAAKQAAAH8BAAAAABAAAAAAAAAABHRlc3QAAnQxAAEDAAE= +TFtYRxcBAAAAIgAAAKEBAAAQABAAAAAAAAEAAf/+AwAAAA== +'; +SET @binlog_fragment_1=''; +BINLOG @binlog_fragment_0, @binlog_fragment_1; +# The above line should succeed and 3 should be in the table: +select * from t1; +# show "one-shot" feature of binlog_fragment variables +SELECT @binlog_fragment_0, @binlog_fragment_1 as 'NULL','NULL'; # Test that mysqlbinlog stops with an error message when the # --base64-output=never flag is used on a binlog with base64 events. diff --git a/mysql-test/suite/binlog/t/binlog_mysqlbinlog_row_frag.test b/mysql-test/suite/binlog/t/binlog_mysqlbinlog_row_frag.test new file mode 100644 index 00000000000..f0317ef1219 --- /dev/null +++ b/mysql-test/suite/binlog/t/binlog_mysqlbinlog_row_frag.test @@ -0,0 +1,45 @@ +--source include/have_debug.inc +--source include/have_binlog_format_row.inc + +--let $MYSQLD_DATADIR= `select @@datadir` + +CREATE TABLE t (a TEXT); +# events of interest are guaranteed to stay in 000001 log +RESET MASTER; +--eval INSERT INTO t SET a=repeat('a', 1024) +SELECT a from t into @a; +FLUSH LOGS; +DELETE FROM t; + +--exec $MYSQL_BINLOG --debug-binlog-row-event-max-encoded-size=256 $MYSQLD_DATADIR/master-bin.000001 > $MYSQLTEST_VARDIR/tmp/mysqlbinlog.sql + +--let SEARCH_PATTERN= BINLOG @binlog_fragment_0, @binlog_fragment_1 +--let SEARCH_FILE= $MYSQLTEST_VARDIR/tmp/mysqlbinlog.sql +--source include/search_pattern_in_file.inc + +--exec $MYSQL test < $MYSQLTEST_VARDIR/tmp/mysqlbinlog.sql + +SELECT a LIKE @a as 'true' FROM t; + +# improper syntax error +--echo BINLOG number-of-fragments must be exactly two +--error ER_PARSE_ERROR +BINLOG @binlog_fragment; +--error ER_PARSE_ERROR +BINLOG @binlog_fragment, @binlog_fragment, @binlog_fragment; + +# corrupted fragments error check (to the expected error code notice, +# the same error code occurs in a similar unfragmented case) +SET @binlog_fragment_0='012345'; +SET @binlog_fragment_1='012345'; +--error ER_SYNTAX_ERROR +BINLOG @binlog_fragment_0, @binlog_fragment_1; + +# Not existing fragment is not allowed +SET @binlog_fragment_0='012345'; +--error ER_WRONG_TYPE_FOR_VAR +BINLOG @binlog_fragment_0, @binlog_fragment_not_exist; + +--echo # Cleanup +--remove_file $MYSQLTEST_VARDIR/tmp/mysqlbinlog.sql +DROP TABLE t; diff --git a/mysys/mf_iocache2.c b/mysys/mf_iocache2.c index fa3b6e672d7..f3877331664 100644 --- a/mysys/mf_iocache2.c +++ b/mysys/mf_iocache2.c @@ -23,51 +23,56 @@ #include <stdarg.h> #include <m_ctype.h> -/* - Copy contents of an IO_CACHE to a file. - - SYNOPSIS - my_b_copy_to_file() - cache IO_CACHE to copy from - file File to copy to - - DESCRIPTION - Copy the contents of the cache to the file. The cache will be - re-inited to a read cache and will read from the beginning of the - cache. - - If a failure to write fully occurs, the cache is only copied - partially. +/** + Copy the cache to the file. Copying can be constrained to @c count + number of bytes when the parameter is less than SIZE_T_MAX. The + cache will be optionally re-inited to a read cache and will read + from the beginning of the cache. If a failure to write fully + occurs, the cache is only copied partially. TODO - Make this function solid by handling partial reads from the cache - in a correct manner: it should be atomic. - - RETURN VALUE - 0 All OK - 1 An error occurred + Make this function solid by handling partial reads from the cache + in a correct manner: it should be atomic. + + @param cache IO_CACHE to copy from + @param file File to copy to + @param count the copied size or the max of the type + when the whole cache is to be copied. + @return + 0 All OK + 1 An error occurred */ int -my_b_copy_to_file(IO_CACHE *cache, FILE *file) +my_b_copy_to_file(IO_CACHE *cache, FILE *file, + size_t count) { - size_t bytes_in_cache; + size_t curr_write, bytes_in_cache; DBUG_ENTER("my_b_copy_to_file"); - /* Reinit the cache to read from the beginning of the cache */ - if (reinit_io_cache(cache, READ_CACHE, 0L, FALSE, FALSE)) - DBUG_RETURN(1); bytes_in_cache= my_b_bytes_in_cache(cache); do { - if (my_fwrite(file, cache->read_pos, bytes_in_cache, + curr_write= MY_MIN(bytes_in_cache, count); + if (my_fwrite(file, cache->read_pos, curr_write, MYF(MY_WME | MY_NABP)) == (size_t) -1) DBUG_RETURN(1); - } while ((bytes_in_cache= my_b_fill(cache))); + + cache->read_pos += curr_write; + count -= curr_write; + } while (count && (bytes_in_cache= my_b_fill(cache))); if(cache->error == -1) DBUG_RETURN(1); DBUG_RETURN(0); } +int my_b_copy_all_to_file(IO_CACHE *cache, FILE *file) +{ + DBUG_ENTER("my_b_copy_all_to_file"); + /* Reinit the cache to read from the beginning of the cache */ + if (reinit_io_cache(cache, READ_CACHE, 0L, FALSE, FALSE)) + DBUG_RETURN(1); + DBUG_RETURN(my_b_copy_to_file(cache, file, SIZE_T_MAX)); +} my_off_t my_b_append_tell(IO_CACHE* info) { diff --git a/sql/item_func.cc b/sql/item_func.cc index 8b1c7b3bc61..169eb76d802 100644 --- a/sql/item_func.cc +++ b/sql/item_func.cc @@ -4828,7 +4828,7 @@ bool Item_func_set_user_var::register_field_in_bitmap(uchar *arg) true failure */ -static bool +bool update_hash(user_var_entry *entry, bool set_null, void *ptr, uint length, Item_result type, CHARSET_INFO *cs, bool unsigned_arg) diff --git a/sql/item_func.h b/sql/item_func.h index 2c0e3a62f6a..e3eab02f213 100644 --- a/sql/item_func.h +++ b/sql/item_func.h @@ -2283,4 +2283,8 @@ bool eval_const_cond(COND *cond); extern bool volatile mqh_used; +bool update_hash(user_var_entry *entry, bool set_null, void *ptr, uint length, + Item_result type, CHARSET_INFO *cs, + bool unsigned_arg); + #endif /* ITEM_FUNC_INCLUDED */ diff --git a/sql/log_event.cc b/sql/log_event.cc index 883f1863ac4..1369ba2d687 100644 --- a/sql/log_event.cc +++ b/sql/log_event.cc @@ -2783,9 +2783,23 @@ void free_table_map_log_event(Table_map_log_event *event) delete event; } +/** + Encode the event, optionally per 'do_print_encoded' arg store the + result into the argument cache; optionally per event_info's + 'verbose' print into the cache a verbose representation of the event. + Note, no extra wrapping is done to the being io-cached data, like + to producing a BINLOG query. It's left for a routine that extracts from + the cache. + + @param file pointer to IO_CACHE + @param print_event_info pointer to print_event_info specializing + what out of and how to print the event + @param do_print_encoded whether to store base64-encoded event + into @file. +*/ void Log_event::print_base64(IO_CACHE* file, PRINT_EVENT_INFO* print_event_info, - bool more) + bool do_print_encoded) { const uchar *ptr= (const uchar *)temp_buf; uint32 size= uint4korr(ptr + EVENT_LEN_OFFSET); @@ -2804,17 +2818,9 @@ void Log_event::print_base64(IO_CACHE* file, DBUG_ASSERT(0); } - if (print_event_info->base64_output_mode != BASE64_OUTPUT_DECODE_ROWS) - { - if (my_b_tell(file) == 0) - my_b_write_string(file, "\nBINLOG '\n"); - + if (do_print_encoded) my_b_printf(file, "%s\n", tmp_str); - if (!more) - my_b_printf(file, "'%s\n", print_event_info->delimiter); - } - if (print_event_info->verbose) { Rows_log_event *ev= NULL; @@ -4851,9 +4857,17 @@ void Start_log_event_v3::print(FILE* file, PRINT_EVENT_INFO* print_event_info) print_event_info->base64_output_mode != BASE64_OUTPUT_NEVER && !print_event_info->short_form) { - if (print_event_info->base64_output_mode != BASE64_OUTPUT_DECODE_ROWS) + /* BINLOG is matched with the delimiter below on the same level */ + bool do_print_encoded= + print_event_info->base64_output_mode != BASE64_OUTPUT_DECODE_ROWS; + if (do_print_encoded) my_b_printf(&cache, "BINLOG '\n"); - print_base64(&cache, print_event_info, FALSE); + + print_base64(&cache, print_event_info, do_print_encoded); + + if (do_print_encoded) + my_b_printf(&cache, "'%s\n", print_event_info->delimiter); + print_event_info->printed_fd_event= TRUE; } DBUG_VOID_RETURN; @@ -10491,12 +10505,128 @@ void Rows_log_event::pack_info(Protocol *protocol) #endif #ifdef MYSQL_CLIENT +/** + Print an event "body" cache to @c file possibly in two fragments. + Each fragement is optionally per @c do_wrap to produce an SQL statement. + + @param file a file to print to + @param body the "body" IO_CACHE of event + @param do_wrap whether to wrap base64-encoded strings with + SQL cover. + @param delimiter delimiter string + + The function signals on any error through setting @c body->error to -1. +*/ +void copy_cache_to_file_wrapped(FILE *file, + IO_CACHE *body, + bool do_wrap, + const char *delimiter) +{ + const char str_binlog[]= "\nBINLOG '\n"; + const char fmt_delim[]= "'%s\n"; + const char fmt_n_delim[]= "\n'%s"; + const my_off_t cache_size= my_b_tell(body); + + if (reinit_io_cache(body, READ_CACHE, 0L, FALSE, FALSE)) + { + body->error= -1; + goto end; + } + + if (!do_wrap) + { + my_b_copy_to_file(body, file, SIZE_T_MAX); + } + else if (4 + sizeof(str_binlog) + cache_size + sizeof(fmt_delim) > + opt_binlog_rows_event_max_encoded_size) + { + /* + 2 fragments can always represent near 1GB row-based + base64-encoded event as two strings each of size less than + max(max_allowed_packet). Greater number of fragments does not + save from potential need to tweak (increase) @@max_allowed_packet + before to process the fragments. So 2 is safe and enough. + + Split the big query when its packet size's estimation exceeds a + limit. The estimate includes the maximum packet header + contribution of non-compressed packet. + */ + const char fmt_frag[]= "\nSET @binlog_fragment_%d ='\n"; + + my_fprintf(file, fmt_frag, 0); + if (my_b_copy_to_file(body, file, cache_size/2 + 1)) + { + body->error= -1; + goto end; + } + my_fprintf(file, fmt_n_delim, delimiter); + + my_fprintf(file, fmt_frag, 1); + if (my_b_copy_to_file(body, file, SIZE_T_MAX)) + { + body->error= -1; + goto end; + } + my_fprintf(file, fmt_delim, delimiter); + + my_fprintf(file, "BINLOG @binlog_fragment_0, @binlog_fragment_1%s\n", + delimiter); + } + else + { + my_fprintf(file, str_binlog); + if (my_b_copy_to_file(body, file, SIZE_T_MAX)) + { + body->error= -1; + goto end; + } + my_fprintf(file, fmt_delim, delimiter); + } + reinit_io_cache(body, WRITE_CACHE, 0, FALSE, TRUE); + +end: + return; +} + +/** + The function invokes base64 encoder to run on the current + event string and store the result into two caches. + When the event ends the current statement the caches are is copied into + the argument file. + Copying is also concerned how to wrap the event, specifically to produce + a valid SQL syntax. + When the encoded data size is within max(MAX_ALLOWED_PACKET) + a regular BINLOG query is composed. Otherwise it is build as fragmented + + SET @binlog_fragment_0='...'; + SET @binlog_fragment_1='...'; + BINLOG @binlog_fragment_0, @binlog_fragment_1; + + where fragments are represented by a pair of indexed user + "one shot" variables. + + @note + If any changes made don't forget to duplicate them to + Old_rows_log_event as long as it's supported. + + @param file pointer to IO_CACHE + @param print_event_info pointer to print_event_info specializing + what out of and how to print the event + @param name the name of a table that the event operates on + + The function signals on any error of cache access through setting + that cache's @c error to -1. +*/ void Rows_log_event::print_helper(FILE *file, PRINT_EVENT_INFO *print_event_info, char const *const name) { IO_CACHE *const head= &print_event_info->head_cache; IO_CACHE *const body= &print_event_info->body_cache; + bool do_print_encoded= + print_event_info->base64_output_mode != BASE64_OUTPUT_DECODE_ROWS && + !print_event_info->short_form; + if (!print_event_info->short_form) { bool const last_stmt_event= get_flags(STMT_END_F); @@ -10504,13 +10634,18 @@ void Rows_log_event::print_helper(FILE *file, my_b_printf(head, "\t%s: table id %lu%s\n", name, m_table_id, last_stmt_event ? " flags: STMT_END_F" : ""); - print_base64(body, print_event_info, !last_stmt_event); + print_base64(body, print_event_info, do_print_encoded); } if (get_flags(STMT_END_F)) { - copy_event_cache_to_file_and_reinit(head, file); - copy_event_cache_to_file_and_reinit(body, file); + if (copy_event_cache_to_file_and_reinit(head, file)) + { + head->error= -1; + return; + } + copy_cache_to_file_wrapped(file, body, do_print_encoded, + print_event_info->delimiter); } } #endif @@ -11379,7 +11514,9 @@ void Table_map_log_event::print(FILE *file, PRINT_EVENT_INFO *print_event_info) m_dbnam, m_tblnam, m_table_id, ((m_flags & TM_BIT_HAS_TRIGGERS_F) ? " (has triggers)" : "")); - print_base64(&print_event_info->body_cache, print_event_info, TRUE); + print_base64(&print_event_info->body_cache, print_event_info, + print_event_info->base64_output_mode != + BASE64_OUTPUT_DECODE_ROWS); copy_event_cache_to_file_and_reinit(&print_event_info->head_cache, file); } } diff --git a/sql/log_event.h b/sql/log_event.h index 90900f63533..446bd8cb827 100644 --- a/sql/log_event.h +++ b/sql/log_event.h @@ -1157,7 +1157,7 @@ class Log_event void print_header(IO_CACHE* file, PRINT_EVENT_INFO* print_event_info, bool is_more); void print_base64(IO_CACHE* file, PRINT_EVENT_INFO* print_event_info, - bool is_more); + bool do_print_encoded); #endif /* read_log_event() functions read an event from a binlog or relay @@ -4891,15 +4891,22 @@ class Ignorable_log_event : public Log_event { virtual int get_data_size() { return IGNORABLE_HEADER_LEN; } }; +#ifdef MYSQL_CLIENT +void copy_cache_to_file_wrapped(FILE *file, + PRINT_EVENT_INFO *print_event_info, + IO_CACHE *body, + bool do_wrap); +#endif static inline bool copy_event_cache_to_file_and_reinit(IO_CACHE *cache, FILE *file) { - return - my_b_copy_to_file(cache, file) || + return + my_b_copy_all_to_file(cache, file) || reinit_io_cache(cache, WRITE_CACHE, 0, FALSE, TRUE); } + #ifdef MYSQL_SERVER /***************************************************************************** diff --git a/sql/log_event_old.cc b/sql/log_event_old.cc index d2b4470bbf9..a6f2ed3f416 100644 --- a/sql/log_event_old.cc +++ b/sql/log_event_old.cc @@ -1850,12 +1850,17 @@ void Old_rows_log_event::pack_info(Protocol *protocol) #ifdef MYSQL_CLIENT +/* Method duplicates Rows_log_event's one */ void Old_rows_log_event::print_helper(FILE *file, PRINT_EVENT_INFO *print_event_info, char const *const name) { IO_CACHE *const head= &print_event_info->head_cache; IO_CACHE *const body= &print_event_info->body_cache; + bool do_print_encoded= + print_event_info->base64_output_mode != BASE64_OUTPUT_DECODE_ROWS && + !print_event_info->short_form; + if (!print_event_info->short_form) { bool const last_stmt_event= get_flags(STMT_END_F); @@ -1863,13 +1868,18 @@ void Old_rows_log_event::print_helper(FILE *file, my_b_printf(head, "\t%s: table id %lu%s\n", name, m_table_id, last_stmt_event ? " flags: STMT_END_F" : ""); - print_base64(body, print_event_info, !last_stmt_event); + print_base64(body, print_event_info, do_print_encoded); } if (get_flags(STMT_END_F)) { - copy_event_cache_to_file_and_reinit(head, file); - copy_event_cache_to_file_and_reinit(body, file); + if (copy_event_cache_to_file_and_reinit(head, file)) + { + head->error= -1; + return; + } + copy_cache_to_file_wrapped(file, body, do_print_encoded, + print_event_info->delimiter); } } #endif diff --git a/sql/sql_binlog.cc b/sql/sql_binlog.cc index 91cf038907e..2e861d00f10 100644 --- a/sql/sql_binlog.cc +++ b/sql/sql_binlog.cc @@ -28,6 +28,65 @@ // START_EVENT_V3, // Log_event_type, // Log_event + +/** + Copy fragments into the standard placeholder thd->lex->comment.str. + + Compute the size of the (still) encoded total, + allocate and then copy fragments one after another. + The size can exceed max(max_allowed_packet) which is not a + problem as no String instance is created off this char array. + + @param thd THD handle + @return + 0 at success, + -1 otherwise. +*/ +int binlog_defragment(THD *thd) +{ + user_var_entry *entry[2]; + LEX_STRING name[2]= { thd->lex->comment, thd->lex->ident }; + + /* compute the total size */ + thd->lex->comment.str= NULL; + thd->lex->comment.length= 0; + for (uint k= 0; k < 2; k++) + { + entry[k]= + (user_var_entry*) my_hash_search(&thd->user_vars, (uchar*) name[k].str, + name[k].length); + if (!entry[k] || entry[k]->type != STRING_RESULT) + { + my_error(ER_WRONG_TYPE_FOR_VAR, MYF(0), name[k].str); + return -1; + } + thd->lex->comment.length += entry[k]->length; + } + + thd->lex->comment.str= // to be freed by the caller + (char *) my_malloc(thd->lex->comment.length, MYF(MY_WME)); + if (!thd->lex->comment.str) + { + my_error(ER_OUTOFMEMORY, MYF(ME_FATALERROR), 1); + return -1; + } + + /* fragments are merged into allocated buf while the user var:s get reset */ + size_t gathered_length= 0; + for (uint k=0; k < 2; k++) + { + memcpy(thd->lex->comment.str + gathered_length, entry[k]->value, + entry[k]->length); + gathered_length += entry[k]->length; + update_hash(entry[k], true, NULL, 0, STRING_RESULT, &my_charset_bin, 0); + } + + DBUG_ASSERT(gathered_length == thd->lex->comment.length); + + return 0; +} + + /** Execute a BINLOG statement. @@ -53,14 +112,6 @@ void mysql_client_binlog_statement(THD* thd) if (check_global_access(thd, SUPER_ACL)) DBUG_VOID_RETURN; - size_t coded_len= thd->lex->comment.length; - if (!coded_len) - { - my_error(ER_SYNTAX_ERROR, MYF(0)); - DBUG_VOID_RETURN; - } - size_t decoded_len= base64_needed_decoded_length(coded_len); - /* option_bits will be changed when applying the event. But we don't expect it be changed permanently after BINLOG statement, so backup it first. @@ -81,6 +132,8 @@ void mysql_client_binlog_statement(THD* thd) int err; Relay_log_info *rli; rpl_group_info *rgi; + char *buf= NULL; + size_t coded_len= 0, decoded_len= 0; rli= thd->rli_fake; if (!rli) @@ -102,15 +155,13 @@ void mysql_client_binlog_statement(THD* thd) rgi->thd= thd; const char *error= 0; - char *buf= (char *) my_malloc(decoded_len, MYF(MY_WME)); Log_event *ev = 0; + my_bool is_fragmented= FALSE; /* Out of memory check */ - if (!(rli && - rli->relay_log.description_event_for_exec && - buf)) + if (!(rli && rli->relay_log.description_event_for_exec)) { my_error(ER_OUTOFMEMORY, MYF(ME_FATALERROR), 1); /* needed 1 bytes */ goto end; @@ -119,6 +170,23 @@ void mysql_client_binlog_statement(THD* thd) rli->sql_driver_thd= thd; rli->no_storage= TRUE; + if (unlikely(is_fragmented= thd->lex->comment.str && thd->lex->ident.str)) + if (binlog_defragment(thd)) + goto end; + + if (!(coded_len= thd->lex->comment.length)) + { + my_error(ER_SYNTAX_ERROR, MYF(0)); + goto end; + } + + decoded_len= base64_needed_decoded_length(coded_len); + if (!(buf= (char *) my_malloc(decoded_len, MYF(MY_WME)))) + { + my_error(ER_OUTOFMEMORY, MYF(ME_FATALERROR), 1); + goto end; + } + for (char const *strptr= thd->lex->comment.str ; strptr < thd->lex->comment.str + thd->lex->comment.length ; ) { @@ -272,6 +340,8 @@ void mysql_client_binlog_statement(THD* thd) my_ok(thd); end: + if (unlikely(is_fragmented)) + my_free(thd->lex->comment.str); thd->variables.option_bits= thd_options; rgi->slave_close_thread_tables(thd); my_free(buf); diff --git a/sql/sql_lex.h b/sql/sql_lex.h index f1edc809579..edc647522d3 100644 --- a/sql/sql_lex.h +++ b/sql/sql_lex.h @@ -2459,6 +2459,10 @@ struct LEX: public Query_tables_list String *wild; /* Wildcard in SHOW {something} LIKE 'wild'*/ sql_exchange *exchange; select_result *result; + /** + @c the two may also hold BINLOG arguments: either comment holds a + base64-char string or both represent the BINLOG fragment user variables. + */ LEX_STRING comment, ident; LEX_USER *grant_user; XID *xid; diff --git a/sql/sql_yacc.yy b/sql/sql_yacc.yy index 0b85b597baf..bfaa0a60a24 100644 --- a/sql/sql_yacc.yy +++ b/sql/sql_yacc.yy @@ -7950,8 +7950,17 @@ binlog_base64_event: { Lex->sql_command = SQLCOM_BINLOG_BASE64_EVENT; Lex->comment= $2; + Lex->ident.str= NULL; + Lex->ident.length= 0; } - ; + | + BINLOG_SYM '@' ident_or_text ',' '@' ident_or_text + { + Lex->sql_command = SQLCOM_BINLOG_BASE64_EVENT; + Lex->comment= $3; + Lex->ident= $6; + } + ; check_view_or_table: table_or_tables table_list opt_mi_check_type diff --git a/unittest/sql/mf_iocache-t.cc b/unittest/sql/mf_iocache-t.cc index 1eef8365074..fca5ec5014d 100644 --- a/unittest/sql/mf_iocache-t.cc +++ b/unittest/sql/mf_iocache-t.cc @@ -370,10 +370,77 @@ void mdev17133() } +void mdev10963() +{ + int res; + uint n_checks= 8; + uchar buf[1024 * 512]; + uint n_frag= sizeof(buf)/(2 * CACHE_SIZE); + FILE *file; + myf my_flags= MYF(MY_WME); + const char *file_name="cache.log"; + + memset(buf, FILL, sizeof(buf)); + diag("MDEV-10963 Fragmented BINLOG query"); + + init_io_cache_encryption(); + srand((uint) time(NULL)); + + /* copying source */ + res= open_cached_file(&info, 0, 0, CACHE_SIZE, 0); + ok(res == 0, "open_cached_file" INFO_TAIL); + res= my_b_write(&info, buf, sizeof(buf)); + + ulong total_size= my_b_tell(&info); + ok(res == 0 && total_size == sizeof(buf), "cache is written"); + + /* destination */ + file= my_fopen(file_name, O_RDWR | O_TRUNC | O_CREAT, my_flags); + ok(my_fileno(file) > 0, "opened file fd = %d", my_fileno(file)); + + /* + For n_checks times verify a sequence of copying with random fragment + size ranging from zero to about the double of the cache read buffer size. + */ + for (; n_checks; n_checks--, rewind(file)) + { + // copied size is an estimate can be incremeneted to greater than total_size + ulong copied_size= 0; + + res= reinit_io_cache(&info, READ_CACHE, 0L, FALSE, FALSE); + ok(res == 0, "cache turned to read"); + + for (ulong i= 0, curr_size= 0; i < n_frag; i++, copied_size += curr_size) + { + curr_size= rand() % (2 * (total_size - copied_size) / (n_frag - i)); + + DBUG_ASSERT(curr_size <= total_size - copied_size || i == n_frag - 1); + + res= my_b_copy_to_file(&info, file, curr_size); + ok(res == 0, "%lu of the cache copied to file", curr_size); + } + /* + Regardless of total_size <> copied_size the function succeeds: + when total_size < copied_size the huge overflowed value of the last + argument is ignored because nothing already left uncopied in the cache. + */ + res= my_b_copy_to_file(&info, file, total_size - copied_size); + ok(res == 0, "%lu of the cache copied to file", total_size - copied_size); + ok(my_ftell(file, my_flags) == sizeof(buf), + "file written in %d fragments", n_frag+1); + + res= reinit_io_cache(&info, WRITE_CACHE, total_size, 0, 0); + ok(res == 0 && my_b_tell(&info) == sizeof(buf), "cache turned to write"); + } + close_cached_file(&info); + my_fclose(file, my_flags); + my_delete(file_name, MYF(MY_WME)); +} + int main(int argc __attribute__((unused)),char *argv[]) { MY_INIT(argv[0]); - plan(114); + plan(277); /* temp files with and without encryption */ encrypt_tmp_files= 1; @@ -391,6 +458,7 @@ int main(int argc __attribute__((unused)),char *argv[]) mdev14014(); mdev17133(); + mdev10963(); my_end(0); return exit_status();

1 0

[Commits] 01d466b: support issue 25102.
by holyfoot＠askmonty.org 22 Jan '19

22 Jan '19

revision-id: 01d466bf124abffa67fe812e24148608b52ef47b (mariadb-10.2.21-28-g01d466b) parent(s): 37ffdb44ef96bacac8981cf180bb47be5da486df committer: Alexey Botchkov timestamp: 2019-01-22 15:59:08 +0400 message: support issue 25102. audit plugin modified to see the reason of performance drop. --- mysql-test/disabled.def | 1 + plugin/server_audit/server_audit.c | 136 +++++-------------------------------- 2 files changed, 17 insertions(+), 120 deletions(-) diff --git a/mysql-test/disabled.def b/mysql-test/disabled.def index b489139..c3aff7d 100644 --- a/mysql-test/disabled.def +++ b/mysql-test/disabled.def @@ -21,3 +21,4 @@ innodb-wl5522-debug-zip : broken upstream innodb_bug12902967 : broken upstream file_contents : MDEV-6526 these files are not installed anymore max_statement_time : cannot possibly work, depends on timing +server_audit : cannot possibly work diff --git a/plugin/server_audit/server_audit.c b/plugin/server_audit/server_audit.c index 612e9e9..4fdb7b9 100644 --- a/plugin/server_audit/server_audit.c +++ b/plugin/server_audit/server_audit.c @@ -515,15 +515,17 @@ static int is_active= 0; static long log_write_failures= 0; static char current_log_buf[FN_REFLEN]= ""; static char last_error_buf[512]= ""; +static long n_connects= 0; +static long n_cur_connects= 0; +static long max_cur_connects= 0; extern void *mysql_v4_descriptor; static struct st_mysql_show_var audit_status[]= { {"server_audit_active", (char *)&is_active, SHOW_BOOL}, - {"server_audit_current_log", current_log_buf, SHOW_CHAR}, - {"server_audit_writes_failed", (char *)&log_write_failures, SHOW_LONG}, - {"server_audit_last_error", last_error_buf, SHOW_CHAR}, + {"server_audit_connections", (char *)&n_connects, SHOW_LONG}, + {"server_audit_max_connections", (char *)&max_cur_connects, SHOW_LONG}, {0,0,0} }; @@ -1975,137 +1977,31 @@ struct connection_info cn_error_buffer; #define FILTER(MASK) (events == 0 || (events & MASK)) void auditing(MYSQL_THD thd, unsigned int event_class, const void *ev) { - struct connection_info *cn= 0; - int after_action= 0; - - /* That one is important as this function can be called with */ - /* &lock_operations locked when the server logs an error reported */ - /* by this plugin. */ - if (!thd || internal_stop_logging) - return; - - flogger_mutex_lock(&lock_operations); - - if (maria_55_started && debug_server_started && - event_class == MYSQL_AUDIT_GENERAL_CLASS) - { - /* - There's a bug in MariaDB 5.5 that prevents using thread local - variables in some cases. - The 'select * from notexisting_table;' query produces such case. - So just use the static buffer in this case. - */ - const struct mysql_event_general *event = - (const struct mysql_event_general *) ev; - - if (event->event_subclass == MYSQL_AUDIT_GENERAL_ERROR || - (event->event_subclass == MYSQL_AUDIT_GENERAL_STATUS && - event->general_query_length == 0 && - cn_error_buffer.query_id == event->query_id)) - { - cn= &cn_error_buffer; - cn->header= 1; - } - else - cn= get_loc_info(thd); - } - else - { - cn= get_loc_info(thd); - } - - update_connection_info(cn, event_class, ev, &after_action); - if (!logging) - goto exit_func; - - if (event_class == MYSQL_AUDIT_GENERAL_CLASS && FILTER(EVENT_QUERY) && - cn && do_log_user(cn->user)) - { - const struct mysql_event_general *event = - (const struct mysql_event_general *) ev; + return; - /* - Only one subclass is logged. - */ - if (event->event_subclass == MYSQL_AUDIT_GENERAL_STATUS && - event_query_command(event)) - { - log_statement(cn, event, "QUERY"); - cn->query_length= 0; /* So the log_current_query() won't log this again. */ - } - } - else if (event_class == MYSQL_AUDIT_TABLE_CLASS && FILTER(EVENT_TABLE) && cn) - { - const struct mysql_event_table *event = - (const struct mysql_event_table *) ev; - if (do_log_user(event->user)) - { - switch (event->event_subclass) - { - case MYSQL_AUDIT_TABLE_LOCK: - log_table(cn, event, event->read_only ? "READ" : "WRITE"); - break; - case MYSQL_AUDIT_TABLE_CREATE: - log_table(cn, event, "CREATE"); - break; - case MYSQL_AUDIT_TABLE_DROP: - log_table(cn, event, "DROP"); - break; - case MYSQL_AUDIT_TABLE_RENAME: - log_rename(cn, event); - break; - case MYSQL_AUDIT_TABLE_ALTER: - log_table(cn, event, "ALTER"); - break; - default: - break; - } - } - } - else if (event_class == MYSQL_AUDIT_CONNECTION_CLASS && - FILTER(EVENT_CONNECT) && cn) + if (event_class == MYSQL_AUDIT_CONNECTION_CLASS) { const struct mysql_event_connection *event = (const struct mysql_event_connection *) ev; switch (event->event_subclass) { case MYSQL_AUDIT_CONNECTION_CONNECT: - log_connection(cn, event, event->status ? "FAILED_CONNECT": "CONNECT"); + n_connects++; + n_cur_connects++; + if (n_cur_connects > max_cur_connects) + max_cur_connects= n_cur_connects; break; + case MYSQL_AUDIT_CONNECTION_DISCONNECT: - if (use_event_data_for_disconnect) - log_connection_event(event, "DISCONNECT"); - else - log_connection(&ci_disconnect_buffer, event, "DISCONNECT"); + n_cur_connects--; break; - case MYSQL_AUDIT_CONNECTION_CHANGE_USER: - log_connection(cn, event, "CHANGEUSER"); + + default: break; - default:; - } - } -exit_func: - /* - This must work always, whether logging is ON or not. - */ - if (after_action) - { - switch (after_action) { - case AA_CHANGE_USER: - { - const struct mysql_event_connection *event = - (const struct mysql_event_connection *) ev; - change_connection(cn, event); - break; - } - default: - break; } } - if (cn) - cn->log_always= 0; - flogger_mutex_unlock(&lock_operations); + }

1 0