* [PATCH v1 0/4] box: JSON preparatory patchset @ 2018-12-27 11:15 Kirill Shcherbatov 2018-12-27 11:15 ` [PATCH v1 1/4] lib: introduce json_tree_snprint_path Kirill Shcherbatov ` (4 more replies) 0 siblings, 5 replies; 18+ messages in thread From: Kirill Shcherbatov @ 2018-12-27 11:15 UTC (permalink / raw) To: tarantool-patches, vdavydov.dev; +Cc: kostja, Kirill Shcherbatov Preparatory patch set for JSON indexes: - Implemented a new json_token_path_snprint routine able to print JSON path to field by field specified working like cannonical snprintf routine - New json_token_is_leaf helper to test node is JSON tree leaf - Implemented a new bitmap_majority_test routine to check if the passed bitmap a "majorates" bitmap b (test that a contains at least all b bits). - Reworked tuple_init_field_map with required fields bitmap - a scallable approach able to work with JSON multilevel fields tree. http://github.com/tarantool/tarantool/tree/kshch/gh-3908-fix-ast-alter-memleak https://github.com/tarantool/tarantool/issues/3908 Kirill Shcherbatov (4): lib: introduce json_tree_snprint_path lib: introduce json_token_is_leaf helper box: introduce bitmap_majority_test routine box: refactor tuple_init_field_map to use bitmap src/box/errcode.h | 2 +- src/box/tuple_format.c | 103 ++++++++++++++++++++++++++-- src/box/tuple_format.h | 18 +++++ src/lib/bit/bit.h | 45 ++++++++++++ src/lib/json/json.c | 68 ++++++++++++++++++ src/lib/json/json.h | 21 ++++++ test/box/alter_limits.result | 6 +- test/box/ddl.result | 18 ++--- test/box/misc.result | 2 +- test/box/sql.result | 9 +-- test/box/tree_pk_multipart.result | 6 +- test/engine/ddl.result | 21 ++---- test/engine/null.result | 39 ++++------- test/unit/bit.c | 52 ++++++++++++++ test/unit/bit.result | 2 + test/unit/json.c | 110 +++++++++++++++++++++++++++++- test/unit/json.result | 32 ++++++++- test/vinyl/constraint.result | 9 +-- test/vinyl/errinj.result | 9 +-- test/vinyl/savepoint.result | 6 +- 20 files changed, 485 insertions(+), 93 deletions(-) -- 2.19.2 ^ permalink raw reply [flat|nested] 18+ messages in thread
* [PATCH v1 1/4] lib: introduce json_tree_snprint_path 2018-12-27 11:15 [PATCH v1 0/4] box: JSON preparatory patchset Kirill Shcherbatov @ 2018-12-27 11:15 ` Kirill Shcherbatov 2018-12-27 18:51 ` Vladimir Davydov 2018-12-27 11:15 ` [PATCH v1 2/4] lib: introduce json_token_is_leaf helper Kirill Shcherbatov ` (3 subsequent siblings) 4 siblings, 1 reply; 18+ messages in thread From: Kirill Shcherbatov @ 2018-12-27 11:15 UTC (permalink / raw) To: tarantool-patches, vdavydov.dev; +Cc: kostja, Kirill Shcherbatov Implemented a helper function for getting a path to a json_token in a json_tree. When routine is called with size=0, return value (as always) as the number of characters that would have been written in case the output string has been large enough. We will use this function for reporting tuple format violations in further patches. Needed for #1012 --- src/lib/json/json.c | 68 ++++++++++++++++++++++++++++++++++++++++ src/lib/json/json.h | 10 ++++++ test/unit/json.c | 73 ++++++++++++++++++++++++++++++++++++++++++- test/unit/json.result | 24 +++++++++++++- 4 files changed, 173 insertions(+), 2 deletions(-) diff --git a/src/lib/json/json.c b/src/lib/json/json.c index c7909fde2..6bee024a9 100644 --- a/src/lib/json/json.c +++ b/src/lib/json/json.c @@ -317,6 +317,74 @@ json_path_validate(const char *path, int path_len, int index_base) return rc; } +/** + * An snprint-style helper to print an individual token key. + */ +static int +json_token_snprint(char *buf, int size, const struct json_token *token, + int index_base) +{ + enum json_token_type type = token->type; + assert(type == JSON_TOKEN_NUM || type == JSON_TOKEN_STR); + int len = 0; + if (type == JSON_TOKEN_NUM) + len = snprintf(buf, size, "[%d]", token->num + index_base); + else if (type == JSON_TOKEN_STR) + len = snprintf(buf, size, "[\"%.*s\"]", token->len, token->str); + return len; +} + +int +json_tree_snprint_path(char *buf, int size, const struct json_token *root, + const struct json_token *token, int index_base) +{ + /* + * Calculate JSON path string length passing 0-buffer in + * json_token_snprint routine. + */ + int len = 0; + const struct json_token *ptr = token; + while (ptr != root && ptr->type != JSON_TOKEN_END) { + len += json_token_snprint(NULL, 0, ptr, index_base); + ptr = ptr->parent; + } + if (size == 0) + return len; + + /* + * Write to the memory buffer buf as many tokens, + * starting with the root, as it can fit. If the fragment + * of the token does not fit into the buffer, it would be + * truncated. + */ + int pos = len; + char last = '\0'; + ptr = token; + while (ptr != root && ptr->type != JSON_TOKEN_END) { + pos -= json_token_snprint(NULL, 0, ptr, index_base); + assert(pos >= 0); + if (pos < size) { + int rc = json_token_snprint(buf + pos, size - pos, ptr, + index_base); + rc = MIN(rc, size - pos); + /* + * The json_token_snprint writes a + * '\0'-terminated string in memory + * buffer. The first character in + * token string representation would be + * overwritten on next cycle iteration. + * Let's keep it in 'last' variable to + * restore next time. + */ + buf[pos + rc] = last; + last = buf[pos]; + } + ptr = ptr->parent; + } + assert(buf[MIN(len, size - 1)] == '\0'); + return len; +} + #define MH_SOURCE 1 #define mh_name _json #define mh_key_t struct json_token * diff --git a/src/lib/json/json.h b/src/lib/json/json.h index 7ce10ce2c..c0adca450 100644 --- a/src/lib/json/json.h +++ b/src/lib/json/json.h @@ -253,6 +253,16 @@ json_path_cmp(const char *a, int a_len, const char *b, int b_len, int json_path_validate(const char *path, int path_len, int index_base); +/** + * An snprint-style function to print path to a token in a JSON + * tree. The root node doesn't necessarily have to be the tree + * root - it may be any ascendant of the given token, in which + * case a path from the given ascendant to the token will be + * printed. + */ +int +json_tree_snprint_path(char *buf, int size, const struct json_token *root, + const struct json_token *token, int index_base); /** * Initialize a new empty JSON tree. * diff --git a/test/unit/json.c b/test/unit/json.c index e553ff23c..26cc5088b 100644 --- a/test/unit/json.c +++ b/test/unit/json.c @@ -438,16 +438,87 @@ test_path_cmp() footer(); } + +struct snprintf_test_case { + struct json_token *root; + struct json_token *token; + int buf_size; + int retval; + const char *str; + int str_len; + const char *descr; +}; + +void +test_path_snprintf() +{ + struct json_tree tree; + int rc = json_tree_create(&tree); + fail_if(rc != 0); + struct test_struct records[5]; + const char *path = "[1][20][\"file\"][8]"; + int path_len = strlen(path); // 18 + + int records_idx = 0; + struct test_struct *node, *node_tmp; + node = test_add_path(&tree, path, path_len, records, &records_idx); + fail_if(&node->node != &records[3].node); + + /* Test size estimation. */ + char buff[64]; + const struct snprintf_test_case tests[] = { + {&tree.root, &node->node, path_len + 1, path_len, path, + path_len, "Full path"}, + {&records[0].node, &node->node, path_len + 1, path_len - 3, + path + 3, path_len - 3, "Non-tree-root root token"}, + {&tree.root, &node->node, path_len - 5, path_len, path, + path_len - 6, "Not enough space in buffer, all tokens fit in"}, + {&tree.root, &node->node, path_len - 5, path_len, path, + path_len - 6, + "Not enough space in buffer, part of token doesn't fit in"}, + {&tree.root, &node->node, 2, path_len, path, 1, + "2-byte size buffer"}, + {&tree.root, &node->node, 1, path_len, path, 0, + "1-byte size buffer"}, + }; + header(); + plan(3 * lengthof(tests)); + + for (size_t i = 0; i < lengthof(tests); ++i) { + rc = json_tree_snprint_path(buff, tests[i].buf_size, + tests[i].root, tests[i].token, + INDEX_BASE); + is(memcmp(buff, tests[i].str, tests[i].str_len), 0, + "\"%s\" - correct partial JSON path: have \"%.*s\" expected \"%.*s\"", + tests[i].descr, tests[i].buf_size, buff, tests[i].str_len, + tests[i].str); + is(buff[tests[i].str_len], '\0', + "\"%s\" - terminating '\\0' at appropriate place", + tests[i].descr); + is(rc, tests[i].retval, "\"%s\" - correct rc: have %d expected %d", + tests[i].descr, rc, tests[i].retval); + } + + json_tree_foreach_entry_safe(node, &tree.root, struct test_struct, + node, node_tmp) + json_tree_del(&tree, &node->node); + json_tree_destroy(&tree); + + check_plan(); + footer(); +} + int main() { header(); - plan(4); + plan(5); test_basic(); test_errors(); test_tree(); test_path_cmp(); + test_path_snprintf(); int rc = check_plan(); footer(); diff --git a/test/unit/json.result b/test/unit/json.result index a17451099..a73203154 100644 --- a/test/unit/json.result +++ b/test/unit/json.result @@ -1,5 +1,5 @@ *** main *** -1..4 +1..5 *** test_basic *** 1..71 ok 1 - parse <[1]> @@ -169,4 +169,26 @@ ok 3 - subtests ok 7 - path Data[[1]["FIO"].fname error pos 6 expected 6 ok 4 - subtests *** test_path_cmp: done *** + *** test_path_snprintf *** + 1..18 + ok 1 - "Full path" - correct partial JSON path: have "[1][20]["file"][8]" expected "[1][20]["file"][8]" + ok 2 - "Full path" - terminating '\0' at appropriate place + ok 3 - "Full path" - correct rc: have 18 expected 18 + ok 4 - "Non-tree-root root token" - correct partial JSON path: have "[20]["file"][8]" expected "[20]["file"][8]" + ok 5 - "Non-tree-root root token" - terminating '\0' at appropriate place + ok 6 - "Non-tree-root root token" - correct rc: have 15 expected 15 + ok 7 - "Not enough space in buffer, all tokens fit in" - correct partial JSON path: have "[1][20]["fil" expected "[1][20]["fil" + ok 8 - "Not enough space in buffer, all tokens fit in" - terminating '\0' at appropriate place + ok 9 - "Not enough space in buffer, all tokens fit in" - correct rc: have 18 expected 18 + ok 10 - "Not enough space in buffer, part of token doesn't fit in" - correct partial JSON path: have "[1][20]["fil" expected "[1][20]["fil" + ok 11 - "Not enough space in buffer, part of token doesn't fit in" - terminating '\0' at appropriate place + ok 12 - "Not enough space in buffer, part of token doesn't fit in" - correct rc: have 18 expected 18 + ok 13 - "2-byte size buffer" - correct partial JSON path: have "[" expected "[" + ok 14 - "2-byte size buffer" - terminating '\0' at appropriate place + ok 15 - "2-byte size buffer" - correct rc: have 18 expected 18 + ok 16 - "1-byte size buffer" - correct partial JSON path: have "" expected "" + ok 17 - "1-byte size buffer" - terminating '\0' at appropriate place + ok 18 - "1-byte size buffer" - correct rc: have 18 expected 18 +ok 5 - subtests + *** test_path_snprintf: done *** *** main: done *** -- 2.19.2 ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH v1 1/4] lib: introduce json_tree_snprint_path 2018-12-27 11:15 ` [PATCH v1 1/4] lib: introduce json_tree_snprint_path Kirill Shcherbatov @ 2018-12-27 18:51 ` Vladimir Davydov 0 siblings, 0 replies; 18+ messages in thread From: Vladimir Davydov @ 2018-12-27 18:51 UTC (permalink / raw) To: Kirill Shcherbatov; +Cc: tarantool-patches, kostja On Thu, Dec 27, 2018 at 02:15:52PM +0300, Kirill Shcherbatov wrote: > +int > +json_tree_snprint_path(char *buf, int size, const struct json_token *root, > + const struct json_token *token, int index_base) I guess you were right and I was wrong after all - if we require to pass the root to this routine, we'll have to pass tuple_format to tuple_field_path(), which will look rather awkward. I removed the root argument altogether and pushed the patch to 2.1. ^ permalink raw reply [flat|nested] 18+ messages in thread
* [PATCH v1 2/4] lib: introduce json_token_is_leaf helper 2018-12-27 11:15 [PATCH v1 0/4] box: JSON preparatory patchset Kirill Shcherbatov 2018-12-27 11:15 ` [PATCH v1 1/4] lib: introduce json_tree_snprint_path Kirill Shcherbatov @ 2018-12-27 11:15 ` Kirill Shcherbatov 2018-12-27 18:52 ` Vladimir Davydov 2018-12-27 11:15 ` [PATCH v1 3/4] box: introduce bitmap_majority_test routine Kirill Shcherbatov ` (2 subsequent siblings) 4 siblings, 1 reply; 18+ messages in thread From: Kirill Shcherbatov @ 2018-12-27 11:15 UTC (permalink / raw) To: tarantool-patches, vdavydov.dev; +Cc: kostja, Kirill Shcherbatov A new json_token_is_leaf routine tests if the passed JSON token is a JSON tree leaf(has no child record). Needed for #1012 --- src/lib/json/json.h | 11 +++++++++++ test/unit/json.c | 39 ++++++++++++++++++++++++++++++++++++++- test/unit/json.result | 10 +++++++++- 3 files changed, 58 insertions(+), 2 deletions(-) diff --git a/src/lib/json/json.h b/src/lib/json/json.h index c0adca450..0bc99474b 100644 --- a/src/lib/json/json.h +++ b/src/lib/json/json.h @@ -30,6 +30,7 @@ * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ +#include <stdbool.h> #include <stddef.h> #include <stdint.h> #include "trivia/util.h" @@ -253,6 +254,16 @@ json_path_cmp(const char *a, int a_len, const char *b, int b_len, int json_path_validate(const char *path, int path_len, int index_base); +/** + * Test if the passed JSON token is a JSON tree leaf + * (has no child records). + */ +static inline bool +json_token_is_leaf(struct json_token *token) +{ + return token->max_child_idx == -1; +} + /** * An snprint-style function to print path to a token in a JSON * tree. The root node doesn't necessarily have to be the tree diff --git a/test/unit/json.c b/test/unit/json.c index 26cc5088b..6dac688d1 100644 --- a/test/unit/json.c +++ b/test/unit/json.c @@ -508,17 +508,54 @@ test_path_snprintf() footer(); } +void +test_json_helpers() +{ + struct json_tree tree; + int rc = json_tree_create(&tree); + fail_if(rc != 0); + struct test_struct records[5]; + const char *path0 = "[1][20][\"file\"]"; + int path0_len = strlen(path0); + const char *path = "[1][20][\"file\"][8]"; + int path_len = strlen(path); + + header(); + plan(4); + + int records_idx = 0; + struct test_struct *node, *node_tmp; + node = test_add_path(&tree, path0, path0_len, records, &records_idx); + fail_if(&node->node != &records[2].node); + is(json_token_is_leaf(&records[1].node), false, "interm node is not leaf"); + is(json_token_is_leaf(&records[2].node), true, "last node is leaf"); + + node = test_add_path(&tree, path, path_len, records, &records_idx); + fail_if(&node->node != &records[3].node); + is(json_token_is_leaf(&records[2].node), false, + "last node became interm - it can't be leaf anymore"); + is(json_token_is_leaf(&records[3].node), true, "last node is leaf"); + + json_tree_foreach_entry_safe(node, &tree.root, struct test_struct, + node, node_tmp) + json_tree_del(&tree, &node->node); + json_tree_destroy(&tree); + check_plan(); + footer(); +} + int main() { header(); - plan(5); + plan(6); test_basic(); test_errors(); test_tree(); test_path_cmp(); test_path_snprintf(); + test_json_helpers(); int rc = check_plan(); footer(); diff --git a/test/unit/json.result b/test/unit/json.result index a73203154..ea2d1af8e 100644 --- a/test/unit/json.result +++ b/test/unit/json.result @@ -1,5 +1,5 @@ *** main *** -1..5 +1..6 *** test_basic *** 1..71 ok 1 - parse <[1]> @@ -191,4 +191,12 @@ ok 4 - subtests ok 18 - "1-byte size buffer" - correct rc: have 18 expected 18 ok 5 - subtests *** test_path_snprintf: done *** + *** test_json_helpers *** + 1..4 + ok 1 - interm node is not leaf + ok 2 - last node is leaf + ok 3 - last node became interm - it can't be leaf anymore + ok 4 - last node is leaf +ok 6 - subtests + *** test_json_helpers: done *** *** main: done *** -- 2.19.2 ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH v1 2/4] lib: introduce json_token_is_leaf helper 2018-12-27 11:15 ` [PATCH v1 2/4] lib: introduce json_token_is_leaf helper Kirill Shcherbatov @ 2018-12-27 18:52 ` Vladimir Davydov 0 siblings, 0 replies; 18+ messages in thread From: Vladimir Davydov @ 2018-12-27 18:52 UTC (permalink / raw) To: Kirill Shcherbatov; +Cc: tarantool-patches, kostja On Thu, Dec 27, 2018 at 02:15:53PM +0300, Kirill Shcherbatov wrote: > int > main() > { > header(); > - plan(5); > + plan(6); > > test_basic(); > test_errors(); > test_tree(); > test_path_cmp(); > test_path_snprintf(); > + test_json_helpers(); This should be a part of test_tree(). I moved the tests there and pushed the patch to 2.1. ^ permalink raw reply [flat|nested] 18+ messages in thread
* [PATCH v1 3/4] box: introduce bitmap_majority_test routine 2018-12-27 11:15 [PATCH v1 0/4] box: JSON preparatory patchset Kirill Shcherbatov 2018-12-27 11:15 ` [PATCH v1 1/4] lib: introduce json_tree_snprint_path Kirill Shcherbatov 2018-12-27 11:15 ` [PATCH v1 2/4] lib: introduce json_token_is_leaf helper Kirill Shcherbatov @ 2018-12-27 11:15 ` Kirill Shcherbatov 2018-12-27 18:59 ` Vladimir Davydov 2018-12-27 11:15 ` [PATCH v1 4/4] box: refactor tuple_init_field_map to use bitmap Kirill Shcherbatov 2018-12-27 19:13 ` [PATCH v1 0/4] box: JSON preparatory patchset Vladimir Davydov 4 siblings, 1 reply; 18+ messages in thread From: Kirill Shcherbatov @ 2018-12-27 11:15 UTC (permalink / raw) To: tarantool-patches, vdavydov.dev; +Cc: kostja, Kirill Shcherbatov A new routine bitmap_majority_test allows to test that bitmap a "majorates" bitmap b, i.e. test that a have at least all b bits. We need it to test compatibility of required fields bitmap with another one that is built for tuple on tuple_init_field_map. Needed for #1012 --- src/lib/bit/bit.h | 45 ++++++++++++++++++++++++++++++++++++++ test/unit/bit.c | 52 ++++++++++++++++++++++++++++++++++++++++++++ test/unit/bit.result | 2 ++ 3 files changed, 99 insertions(+) diff --git a/src/lib/bit/bit.h b/src/lib/bit/bit.h index 370a0cc5d..2146a0452 100644 --- a/src/lib/bit/bit.h +++ b/src/lib/bit/bit.h @@ -614,6 +614,51 @@ bit_iterator_next(struct bit_iterator *it) return it->word_base + bit; } +/** + * Check if the passed bitmap a "majorates" bitmap b (test that + * a contains at least all b bits). Compare first len memory + * blocks of sizeof(uint32_t). + * Return 0 when a majorates b. Otherwise -1 is returned and + * diff_bit_id is set - the index of first bit that present in + * bitmap b, but doesn't present in bitmap a. + */ +static inline int +bitmap_majority_test(uint32_t *a, uint32_t *b, int len, uint32_t *diff_bit_id) +{ + int match_cnt = 0; + uint32_t *a_ptr = a, *b_ptr = b; + uint32_t neg_impl; + /* + * "Inverted material implication" ~(~x | y) = x & ~y test + * is used to find the first bit that differ + * + * Example: + * step 0 -- skip compatible bytes + * x: 0b01111101 + * y: 0b00111101 + * x & ~y: 0b00000000 == 0 -- next, goto step 0 + * + * step 1 -- the first byte that differ: + * x: 0b01011001 + * y: 0b00111101 + * x & ~y: 0b00100100 + * + * step 2 -- calculate relative bit index with ctz: + * bit_ctz_u32(0b00100100) = 2 -- return diff_bit_id + */ + while (bit_likely((neg_impl = *b_ptr & ~*a_ptr) == 0)) { + if (bit_unlikely(++match_cnt >= len)) { + return 0; + } + a_ptr++; + b_ptr++; + } + assert(neg_impl != 0); + uint32_t trailing_zeros = bit_ctz_u32(neg_impl); + *diff_bit_id = match_cnt * sizeof(uint32_t) * CHAR_BIT + trailing_zeros; + return -1; +} + #undef ITER_CTZ #undef ITER_UINT diff --git a/test/unit/bit.c b/test/unit/bit.c index beb89a7e4..10074c412 100644 --- a/test/unit/bit.c +++ b/test/unit/bit.c @@ -206,6 +206,57 @@ test_bit_iter_empty(void) footer(); } +static void +test_bitmap_majority(void) +{ + header(); + + uint32_t id; + uint32_t req_bitmap[5]; + memset(req_bitmap, 0, sizeof(req_bitmap)); + bit_set(req_bitmap, 4 * sizeof(uint32_t) * CHAR_BIT + 2); + bit_set(req_bitmap, 3 * sizeof(uint32_t) * CHAR_BIT + 1); + bit_set(req_bitmap, 2 * sizeof(uint32_t) * CHAR_BIT + 4); + bit_set(req_bitmap, 2 * sizeof(uint32_t) * CHAR_BIT + 2); + bit_set(req_bitmap, 8); + fail_if(bitmap_majority_test(req_bitmap, req_bitmap, 5, &id) != 0); + + /* + * Verify that bitmap_majority_test returns difference + * bits ids in incremental order ignoring test extra bits. + */ + uint32_t test_bitmap[5]; + memset(test_bitmap, 0, sizeof(test_bitmap)); + bit_set(test_bitmap, 4 * sizeof(uint32_t) * CHAR_BIT + 8); + bit_set(test_bitmap, 4 * sizeof(uint32_t) * CHAR_BIT + 1); + bit_set(test_bitmap, 2 * sizeof(uint32_t) * CHAR_BIT + 8); + + fail_if(bitmap_majority_test(test_bitmap, req_bitmap, 5, &id) != -1); + fail_unless(id == 8); + bit_set(&test_bitmap, 8); + + fail_if(bitmap_majority_test(test_bitmap, req_bitmap, 5, &id) != -1); + fail_unless(id == 2 * sizeof(uint32_t) * CHAR_BIT + 2); + bit_set(&test_bitmap, 2 * sizeof(uint32_t) * CHAR_BIT + 2); + + fail_if(bitmap_majority_test(test_bitmap, req_bitmap, 5, &id) != -1); + fail_unless(id == 2 * sizeof(uint32_t) * CHAR_BIT + 4); + bit_set(&test_bitmap, 2 * sizeof(uint32_t) * CHAR_BIT + 4); + + fail_if(bitmap_majority_test(test_bitmap, req_bitmap, 5, &id) != -1); + fail_unless(id == 3 * sizeof(uint32_t) * CHAR_BIT + 1); + bit_set(&test_bitmap, 3 * sizeof(uint32_t) * CHAR_BIT + 1); + + fail_if(bitmap_majority_test(test_bitmap, req_bitmap, 5, &id) != -1); + fail_unless(id == 4 * sizeof(uint32_t) * CHAR_BIT + 2); + bit_set(&test_bitmap, 4 * sizeof(uint32_t) * CHAR_BIT + 2); + + /* All different bits have been fixed. */ + fail_if(bitmap_majority_test(test_bitmap, req_bitmap, 4, &id) != 0); + + footer(); +} + int main(void) { @@ -216,4 +267,5 @@ main(void) test_index(); test_bit_iter(); test_bit_iter_empty(); + test_bitmap_majority(); } diff --git a/test/unit/bit.result b/test/unit/bit.result index e2c5601f3..6123bc58a 100644 --- a/test/unit/bit.result +++ b/test/unit/bit.result @@ -891,3 +891,5 @@ Clear: 0, 1, 2, 4, 5, 6, 7, 8, 10, 12, 13, 14, 15, 19, 20, 21, 23, 26, 28, 30, 3 *** test_bit_iter: done *** *** test_bit_iter_empty *** *** test_bit_iter_empty: done *** + *** test_bitmap_majority *** + *** test_bitmap_majority: done *** -- 2.19.2 ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH v1 3/4] box: introduce bitmap_majority_test routine 2018-12-27 11:15 ` [PATCH v1 3/4] box: introduce bitmap_majority_test routine Kirill Shcherbatov @ 2018-12-27 18:59 ` Vladimir Davydov 2018-12-29 12:58 ` [tarantool-patches] " Kirill Shcherbatov 0 siblings, 1 reply; 18+ messages in thread From: Vladimir Davydov @ 2018-12-27 18:59 UTC (permalink / raw) To: Kirill Shcherbatov; +Cc: tarantool-patches, kostja On Thu, Dec 27, 2018 at 02:15:54PM +0300, Kirill Shcherbatov wrote: > A new routine bitmap_majority_test allows to test that bitmap > a "majorates" bitmap b, i.e. test that a have at least all b bits. > We need it to test compatibility of required fields bitmap with > another one that is built for tuple on tuple_init_field_map. > > Needed for #1012 > --- > src/lib/bit/bit.h | 45 ++++++++++++++++++++++++++++++++++++++ > test/unit/bit.c | 52 ++++++++++++++++++++++++++++++++++++++++++++ > test/unit/bit.result | 2 ++ > 3 files changed, 99 insertions(+) > > diff --git a/src/lib/bit/bit.h b/src/lib/bit/bit.h > index 370a0cc5d..2146a0452 100644 > --- a/src/lib/bit/bit.h > +++ b/src/lib/bit/bit.h > @@ -614,6 +614,51 @@ bit_iterator_next(struct bit_iterator *it) > return it->word_base + bit; > } > > +/** > + * Check if the passed bitmap a "majorates" bitmap b (test that > + * a contains at least all b bits). Compare first len memory > + * blocks of sizeof(uint32_t). > + * Return 0 when a majorates b. Otherwise -1 is returned and > + * diff_bit_id is set - the index of first bit that present in > + * bitmap b, but doesn't present in bitmap a. > + */ > +static inline int > +bitmap_majority_test(uint32_t *a, uint32_t *b, int len, uint32_t *diff_bit_id) This function looks artificial to me, especially the fact that in case of error it returns the first different bit in diff_bit_id (why only the first one?). Why do you need it, anyway? All you need to do in the next patch is: 1. Allocate required_fields bitmap on region. 2. Initialize it with tuple_format->required_fields. 3. Clear bits in it as you find that corresponding tuple fields are present. 4. Finally, check that the bitmap is empty. If it is not report an error for the first set bit. To achieve that, you need a much simpler primitive, bit_find(), which would find the first set bit in a bitmap. This primitive could be reused in future, in contrast to this new function. I just looked at bit.c and I see that it already has a bit iterator. May be, we can simply use it for finding the first bit? It looks pretty efficient to me. ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [tarantool-patches] Re: [PATCH v1 3/4] box: introduce bitmap_majority_test routine 2018-12-27 18:59 ` Vladimir Davydov @ 2018-12-29 12:58 ` Kirill Shcherbatov 2018-12-29 13:19 ` Vladimir Davydov 0 siblings, 1 reply; 18+ messages in thread From: Kirill Shcherbatov @ 2018-12-29 12:58 UTC (permalink / raw) To: tarantool-patches, Vladimir Davydov > This function looks artificial to me, especially the fact that in case > of error it returns the first different bit in diff_bit_id (why only the > first one?). > > Why do you need it, anyway? All you need to do in the next patch is: > 1. Allocate required_fields bitmap on region. > 2. Initialize it with tuple_format->required_fields. > 3. Clear bits in it as you find that corresponding tuple fields are > present. > 4. Finally, check that the bitmap is empty. If it is not report an > error for the first set bit. > > To achieve that, you need a much simpler primitive, bit_find(), which > would find the first set bit in a bitmap. This primitive could be reused > in future, in contrast to this new function. > > I just looked at bit.c and I see that it already has a bit iterator. > May be, we can simply use it for finding the first bit? It looks pretty > efficient to me. You are right. Your approach is much better. ==================================== A new bit_find helper returns the index of the first bit set in bitmap, bitmap_size returns size of bitmap allocation by count of bits to work with. We need it to test compatibility of required fields bitmap with another one that is built for tuple on tuple_init_field_map. Needed for #1012 --- src/lib/bit/bit.h | 25 +++++++++++++++++++++++++ test/unit/bit.c | 33 +++++++++++++++++++++++++++++++++ test/unit/bit.result | 2 ++ 3 files changed, 60 insertions(+) diff --git a/src/lib/bit/bit.h b/src/lib/bit/bit.h index 370a0cc5d..fc3a5ba21 100644 --- a/src/lib/bit/bit.h +++ b/src/lib/bit/bit.h @@ -614,6 +614,31 @@ bit_iterator_next(struct bit_iterator *it) return it->word_base + bit; } +/** + * Return a number of a first set bit in data or SIZE_MAX + * if no bits are set in data. + */ +static inline size_t +bit_find(const void *data, size_t size) +{ + struct bit_iterator it; + bit_iterator_init(&it, data, size, true); + return bit_iterator_next(&it); +} + +/** Return size of bitmap by bit_count - count of bits to set. */ +static inline size_t +bitmap_size(size_t bit_count) +{ + /* + * Memory size must be sizeof(uint32_t)-aligned as + * bit_sit/bit_clear operations use unt32_t words to + * setup bits. + */ + return DIV_ROUND_UP(DIV_ROUND_UP(bit_count, CHAR_BIT), + sizeof(unsigned long)) * sizeof(unsigned long); +} + #undef ITER_CTZ #undef ITER_UINT diff --git a/test/unit/bit.c b/test/unit/bit.c index beb89a7e4..8f68a6a83 100644 --- a/test/unit/bit.c +++ b/test/unit/bit.c @@ -206,6 +206,38 @@ test_bit_iter_empty(void) footer(); } +static void +test_bitmap(void) +{ + header(); + + fail_if(bitmap_size(0) != 0); + fail_if(bitmap_size(1) != sizeof(unsigned long)); + fail_if(bitmap_size(4) != sizeof(unsigned long)); + fail_if(bitmap_size(CHAR_BIT * sizeof(unsigned long)) != + sizeof(unsigned long)); + fail_if(bitmap_size(CHAR_BIT * sizeof(unsigned long) + 1) != + 2 * sizeof(unsigned long)); + + uint32_t test[5]; + memset(test, 0, sizeof(test)); + bit_set(test, 2 * sizeof(uint32_t) * CHAR_BIT + 4); + bit_set(test, 2 * sizeof(uint32_t) * CHAR_BIT + 2); + bit_set(test, 8); + + fail_if(bit_find(test, 5 * sizeof(uint32_t)) != 8); + bit_clear(test, 8); + fail_if(bit_find(test, 5 * sizeof(uint32_t)) != + 2 * sizeof(uint32_t) * CHAR_BIT + 2); + bit_clear(test, 2 * sizeof(uint32_t) * CHAR_BIT + 2); + fail_if(bit_find(test, 5 * sizeof(uint32_t)) != + 2 * sizeof(uint32_t) * CHAR_BIT + 4); + bit_clear(test, 2 * sizeof(uint32_t) * CHAR_BIT + 4); + fail_if(bit_find(test, 5 * sizeof(uint32_t)) != SIZE_MAX); + + footer(); +} + int main(void) { @@ -216,4 +248,5 @@ main(void) test_index(); test_bit_iter(); test_bit_iter_empty(); + test_bitmap(); } diff --git a/test/unit/bit.result b/test/unit/bit.result index e2c5601f3..ab9ae9d92 100644 --- a/test/unit/bit.result +++ b/test/unit/bit.result @@ -891,3 +891,5 @@ Clear: 0, 1, 2, 4, 5, 6, 7, 8, 10, 12, 13, 14, 15, 19, 20, 21, 23, 26, 28, 30, 3 *** test_bit_iter: done *** *** test_bit_iter_empty *** *** test_bit_iter_empty: done *** + *** test_bitmap *** + *** test_bitmap: done *** -- 2.19.2 ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [tarantool-patches] Re: [PATCH v1 3/4] box: introduce bitmap_majority_test routine 2018-12-29 12:58 ` [tarantool-patches] " Kirill Shcherbatov @ 2018-12-29 13:19 ` Vladimir Davydov 2018-12-29 13:57 ` Kirill Shcherbatov 0 siblings, 1 reply; 18+ messages in thread From: Vladimir Davydov @ 2018-12-29 13:19 UTC (permalink / raw) To: Kirill Shcherbatov; +Cc: tarantool-patches On Sat, Dec 29, 2018 at 03:58:32PM +0300, Kirill Shcherbatov wrote: > > This function looks artificial to me, especially the fact that in case > > of error it returns the first different bit in diff_bit_id (why only the > > first one?). > > > > Why do you need it, anyway? All you need to do in the next patch is: > > 1. Allocate required_fields bitmap on region. > > 2. Initialize it with tuple_format->required_fields. > > 3. Clear bits in it as you find that corresponding tuple fields are > > present. > > 4. Finally, check that the bitmap is empty. If it is not report an > > error for the first set bit. > > > > To achieve that, you need a much simpler primitive, bit_find(), which > > would find the first set bit in a bitmap. This primitive could be reused > > in future, in contrast to this new function. > > > > I just looked at bit.c and I see that it already has a bit iterator. > > May be, we can simply use it for finding the first bit? It looks pretty > > efficient to me. > > You are right. Your approach is much better. > ==================================== > > A new bit_find helper returns the index of the first bit set in > bitmap, bitmap_size returns size of bitmap allocation by count > of bits to work with. > We need it to test compatibility of required fields bitmap with > another one that is built for tuple on tuple_init_field_map. > > Needed for #1012 > --- > src/lib/bit/bit.h | 25 +++++++++++++++++++++++++ > test/unit/bit.c | 33 +++++++++++++++++++++++++++++++++ > test/unit/bit.result | 2 ++ > 3 files changed, 60 insertions(+) > > diff --git a/src/lib/bit/bit.h b/src/lib/bit/bit.h > index 370a0cc5d..fc3a5ba21 100644 > --- a/src/lib/bit/bit.h > +++ b/src/lib/bit/bit.h > @@ -614,6 +614,31 @@ bit_iterator_next(struct bit_iterator *it) > return it->word_base + bit; > } > > +/** > + * Return a number of a first set bit in data or SIZE_MAX > + * if no bits are set in data. > + */ > +static inline size_t > +bit_find(const void *data, size_t size) > +{ > + struct bit_iterator it; > + bit_iterator_init(&it, data, size, true); > + return bit_iterator_next(&it); > +} Ouch, you seems to have misunderstood me. What I meant when I talked about the need of bit_find() was: *if* bit_iterator is not fast enough, introduce an efficient bit_find() helper, *otherwise* use bit_iterator - there's no point wrapping bit_iterator_next() in a new helper function. Sorry for misunderstanding. > + > +/** Return size of bitmap by bit_count - count of bits to set. */ > +static inline size_t > +bitmap_size(size_t bit_count) This helper should be closer to the beginning of the file, because header files are typically organized as follows: first macros and trivial inline helpers, then more complex structures and functions. > +{ > + /* > + * Memory size must be sizeof(uint32_t)-aligned as sizeof(uint32_t)? But you align by (long). Please fix the comment. I guess we can say that the size of a bitmap should be word-aligned. > + * bit_sit/bit_clear operations use unt32_t words to > + * setup bits. > + */ > + return DIV_ROUND_UP(DIV_ROUND_UP(bit_count, CHAR_BIT), > + sizeof(unsigned long)) * sizeof(unsigned long); This is correct indeed, and I guess it's OK to leave it as is, but to me first converting bit count to byte count and only then to word count looks confusing. Why not convert bit count to word count directly? size_t word_count = DIV_ROUND_UP(bit_count, CHAR_BIT * sizeof(long)); return word_count * sizeof(long); > +} > + > #undef ITER_CTZ > #undef ITER_UINT > > diff --git a/test/unit/bit.c b/test/unit/bit.c > index beb89a7e4..8f68a6a83 100644 > --- a/test/unit/bit.c > +++ b/test/unit/bit.c > @@ -206,6 +206,38 @@ test_bit_iter_empty(void) > footer(); > } > > +static void > +test_bitmap(void) > +{ > + header(); > + > + fail_if(bitmap_size(0) != 0); > + fail_if(bitmap_size(1) != sizeof(unsigned long)); > + fail_if(bitmap_size(4) != sizeof(unsigned long)); > + fail_if(bitmap_size(CHAR_BIT * sizeof(unsigned long)) != I think we should use is() for testing bitmap_size(). ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [tarantool-patches] Re: [PATCH v1 3/4] box: introduce bitmap_majority_test routine 2018-12-29 13:19 ` Vladimir Davydov @ 2018-12-29 13:57 ` Kirill Shcherbatov 2018-12-29 16:16 ` Vladimir Davydov 0 siblings, 1 reply; 18+ messages in thread From: Kirill Shcherbatov @ 2018-12-29 13:57 UTC (permalink / raw) To: tarantool-patches, Vladimir Davydov Hi! Ok... Also changed the only place in following patch. =============================== A new bitmap_size routine returns size of bitmap allocation aligned by sizeof(unsigned long) words by count of bits to work with. Memory chunk must be aligned as bit_set/bit_clear functions use unsigned long words to setup bits. We need bitmap_size to make an allocation for format:fields to test compatibility of required fields bitmap with another one that is built for parsed tuple on tuple_init_field_map. Needed for #1012 --- src/lib/bit/bit.h | 13 +++++++++++++ test/unit/CMakeLists.txt | 2 +- test/unit/bit.c | 27 +++++++++++++++++++++++++++ test/unit/bit.result | 8 ++++++++ 4 files changed, 49 insertions(+), 1 deletion(-) diff --git a/src/lib/bit/bit.h b/src/lib/bit/bit.h index 370a0cc5d..04be818b2 100644 --- a/src/lib/bit/bit.h +++ b/src/lib/bit/bit.h @@ -238,6 +238,19 @@ bit_clear(void *data, size_t pos) return prev; } +/** + * Return sizeof(unsigned long)-words aligned size of bitmap by + * bit_count - count of bits to set. Size must be aligned, as + * bit_sit/bit_clear operations use unsigned long words to setup + * bit. + */ +static inline size_t +bitmap_size(size_t bit_count) +{ + size_t word_count = DIV_ROUND_UP(bit_count, CHAR_BIT * sizeof(long)); + return word_count * sizeof(long); +} + /** * @cond false * @brief Naive implementation of ctz. diff --git a/test/unit/CMakeLists.txt b/test/unit/CMakeLists.txt index 0025d3611..5b2f152e3 100644 --- a/test/unit/CMakeLists.txt +++ b/test/unit/CMakeLists.txt @@ -36,7 +36,7 @@ add_executable(rope.test rope.c) target_link_libraries(rope.test salad) add_executable(int96.test int96.cc) add_executable(bit.test bit.c bit.c) -target_link_libraries(bit.test bit) +target_link_libraries(bit.test bit unit) add_executable(bitset_basic.test bitset_basic.c) target_link_libraries(bitset_basic.test bitset) add_executable(bitset_iterator.test bitset_iterator.c) diff --git a/test/unit/bit.c b/test/unit/bit.c index beb89a7e4..67a7ccd63 100644 --- a/test/unit/bit.c +++ b/test/unit/bit.c @@ -206,6 +206,32 @@ test_bit_iter_empty(void) footer(); } +static void +test_bitmap(void) +{ + header(); + plan(5); + + size_t rc = bitmap_size(0); + is(rc, 0, "empty bitmap: have %zu expected %d", rc, 0); + rc = bitmap_size(1); + is(rc, sizeof(unsigned long), "1-item bitmap: have %zu expected %lu", + rc, sizeof(unsigned long)); + rc = bitmap_size(4); + is(rc, sizeof(unsigned long), "4-items bitmap: have %zu expected %lu", + rc, sizeof(unsigned long)); + rc = bitmap_size(CHAR_BIT * sizeof(unsigned long)); + is(rc, sizeof(unsigned long), "%lu-items bitmap: have %zu expected %lu", + CHAR_BIT * sizeof(unsigned long), rc, sizeof(unsigned long)); + rc = bitmap_size(CHAR_BIT * sizeof(unsigned long) + 1); + is(rc, 2 * sizeof(unsigned long), + "%lu-items bitmap: have %zu expected %lu", + CHAR_BIT * sizeof(unsigned long) + 1, rc, 2 * sizeof(unsigned long)); + + check_plan(); + footer(); +} + int main(void) { @@ -216,4 +242,5 @@ main(void) test_index(); test_bit_iter(); test_bit_iter_empty(); + test_bitmap(); } diff --git a/test/unit/bit.result b/test/unit/bit.result index e2c5601f3..d99cfbf01 100644 --- a/test/unit/bit.result +++ b/test/unit/bit.result @@ -891,3 +891,11 @@ Clear: 0, 1, 2, 4, 5, 6, 7, 8, 10, 12, 13, 14, 15, 19, 20, 21, 23, 26, 28, 30, 3 *** test_bit_iter: done *** *** test_bit_iter_empty *** *** test_bit_iter_empty: done *** + *** test_bitmap *** +1..5 +ok 1 - empty bitmap: have 0 expected 0 +ok 2 - 1-item bitmap: have 8 expected 8 +ok 3 - 4-items bitmap: have 8 expected 8 +ok 4 - 64-items bitmap: have 8 expected 8 +ok 5 - 65-items bitmap: have 16 expected 16 + *** test_bitmap: done *** -- 2.19.2 ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [tarantool-patches] Re: [PATCH v1 3/4] box: introduce bitmap_majority_test routine 2018-12-29 13:57 ` Kirill Shcherbatov @ 2018-12-29 16:16 ` Vladimir Davydov 0 siblings, 0 replies; 18+ messages in thread From: Vladimir Davydov @ 2018-12-29 16:16 UTC (permalink / raw) To: Kirill Shcherbatov; +Cc: tarantool-patches On Sat, Dec 29, 2018 at 04:57:00PM +0300, Kirill Shcherbatov wrote: > +/** > + * Return sizeof(unsigned long)-words aligned size of bitmap by > + * bit_count - count of bits to set. Size must be aligned, as > + * bit_sit/bit_clear operations use unsigned long words to setup > + * bit. > + */ Changed the comment to /** * @brief Returns the size of memory needed to store a bitmap * of \a bit_count bits. * The function rounds the size up to a multiple of the word * size, which is required by bit_set() and bit_clear(). * @param bit_count number of bits in the bitmap * @retval bitmap size, in bytes */ (used doxygen, because all other comments in the file are formated in the same way) > +1..5 > +ok 1 - empty bitmap: have 0 expected 0 > +ok 2 - 1-item bitmap: have 8 expected 8 > +ok 3 - 4-items bitmap: have 8 expected 8 > +ok 4 - 64-items bitmap: have 8 expected 8 > +ok 5 - 65-items bitmap: have 16 expected 16 > + *** test_bitmap: done *** OK, now I see why you used fail_unless in the previous version - because all other tests in the file use it. Then you should've told me that instead of blindly following my instructions - I can make mistakes too. Changed the test back to fail_unless for consistency and pushed the patch to 2.1. ^ permalink raw reply [flat|nested] 18+ messages in thread
* [PATCH v1 4/4] box: refactor tuple_init_field_map to use bitmap 2018-12-27 11:15 [PATCH v1 0/4] box: JSON preparatory patchset Kirill Shcherbatov ` (2 preceding siblings ...) 2018-12-27 11:15 ` [PATCH v1 3/4] box: introduce bitmap_majority_test routine Kirill Shcherbatov @ 2018-12-27 11:15 ` Kirill Shcherbatov 2018-12-27 11:48 ` [tarantool-patches] " Konstantin Osipov 2018-12-27 19:12 ` Vladimir Davydov 2018-12-27 19:13 ` [PATCH v1 0/4] box: JSON preparatory patchset Vladimir Davydov 4 siblings, 2 replies; 18+ messages in thread From: Kirill Shcherbatov @ 2018-12-27 11:15 UTC (permalink / raw) To: tarantool-patches, vdavydov.dev; +Cc: kostja, Kirill Shcherbatov Refactored tuple_init_field_map to fill a local bitmap and compare it with template required_fields bitmap containing information about required fields. Each field is mapped to bitmap with field:id - unique field identifier. This approach to check the required fields will work even after the introduction of JSON paths, when the field tree becomes multilevel. Needed for #1012 --- src/box/errcode.h | 2 +- src/box/tuple_format.c | 103 ++++++++++++++++++++++++++++-- src/box/tuple_format.h | 18 ++++++ test/box/alter_limits.result | 6 +- test/box/ddl.result | 18 ++---- test/box/misc.result | 2 +- test/box/sql.result | 9 +-- test/box/tree_pk_multipart.result | 6 +- test/engine/ddl.result | 21 ++---- test/engine/null.result | 39 ++++------- test/vinyl/constraint.result | 9 +-- test/vinyl/errinj.result | 9 +-- test/vinyl/savepoint.result | 6 +- 13 files changed, 157 insertions(+), 91 deletions(-) diff --git a/src/box/errcode.h b/src/box/errcode.h index 94381f9f7..f7dbb948e 100644 --- a/src/box/errcode.h +++ b/src/box/errcode.h @@ -91,7 +91,7 @@ struct errcode_record { /* 36 */_(ER_NO_SUCH_SPACE, "Space '%s' does not exist") \ /* 37 */_(ER_NO_SUCH_FIELD, "Field %d was not found in the tuple") \ /* 38 */_(ER_EXACT_FIELD_COUNT, "Tuple field count %u does not match space field count %u") \ - /* 39 */_(ER_MIN_FIELD_COUNT, "Tuple field count %u is less than required by space format or defined indexes (expected at least %u)") \ + /* 39 */_(ER_FIELD_MISSING, "Tuple field %s required by space format is missing") \ /* 40 */_(ER_WAL_IO, "Failed to write to disk") \ /* 41 */_(ER_MORE_THAN_ONE_TUPLE, "Get() doesn't support partial keys and non-unique indexes") \ /* 42 */_(ER_ACCESS_DENIED, "%s access to %s '%s' is denied for user '%s'") \ diff --git a/src/box/tuple_format.c b/src/box/tuple_format.c index d7489dcd0..a2b7fc7e6 100644 --- a/src/box/tuple_format.c +++ b/src/box/tuple_format.c @@ -28,6 +28,8 @@ * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ +#include "bit/bit.h" +#include "fiber.h" #include "json/json.h" #include "tuple_format.h" #include "coll_id_cache.h" @@ -207,6 +209,30 @@ tuple_format_create(struct tuple_format *format, struct key_def * const *keys, return -1; } format->field_map_size = field_map_size; + + /* Allocate required fields bitmap. */ + uint32_t required_fields_sz = + DIV_ROUND_UP(format->total_field_count, sizeof(uint32_t)) * + sizeof(uint32_t); + format->required_fields = calloc(1, required_fields_sz); + if (format->required_fields == NULL) { + diag_set(OutOfMemory, required_fields_sz, "calloc", + "format->required_fields"); + return -1; + } + struct tuple_field *field; + struct json_token *root = (struct json_token *)&format->fields.root; + json_tree_foreach_entry_preorder(field, root, struct tuple_field, + token) { + /* + * Mark all leaf non-nullable fields as required + * setting corresponding bit 1 in format + * required_fields. + */ + if (json_token_is_leaf(&field->token) && + !tuple_field_is_nullable(field)) + bit_set(format->required_fields, field->id); + } return 0; } @@ -305,6 +331,7 @@ tuple_format_alloc(struct key_def * const *keys, uint16_t key_count, struct tuple_field *field = tuple_field_new(); if (field == NULL) goto error; + field->id = fieldno; field->token.num = fieldno; field->token.type = JSON_TOKEN_NUM; if (json_tree_add(&format->fields, &format->fields.root, @@ -324,6 +351,8 @@ tuple_format_alloc(struct key_def * const *keys, uint16_t key_count, format->dict = dict; tuple_dictionary_ref(dict); } + format->total_field_count = field_count; + format->required_fields = NULL; format->refs = 0; format->id = FORMAT_ID_NIL; format->index_field_count = index_field_count; @@ -340,6 +369,7 @@ error: static inline void tuple_format_destroy(struct tuple_format *format) { + free(format->required_fields); tuple_format_destroy_fields(format); tuple_dictionary_unref(format->dict); } @@ -421,6 +451,48 @@ tuple_format1_can_store_format2_tuples(struct tuple_format *format1, return true; } +/** + * Return meta information of a tuple field given a format + * and a unique field identifier. + * Typically used on error handling so it is not + * performance-critical and may use full-tree-traverse on lookup. + */ +static struct tuple_field * +tuple_format_field_by_id(struct tuple_format *format, uint32_t id) +{ + struct tuple_field *field; + json_tree_foreach_entry_preorder(field, &format->fields.root, + struct tuple_field, token) { + if (field->id == id) + return field; + } + return NULL; +} + +/** + * Analyze required_fields to ensure that all required fields + * present in tuple. Routine relies on required_fields is + * initialized on tuple_format_create and all required field's + * bits ids are set 1. + */ +static int +tuple_format_required_fields_test(struct tuple_format *format, + uint32_t *required_fields) +{ + uint32_t bitmap_len = + DIV_ROUND_UP(format->total_field_count, sizeof(uint32_t)); + uint32_t missed_field_id; + if (likely(bitmap_majority_test(required_fields, format->required_fields, + bitmap_len, &missed_field_id) == 0)) + return 0; + assert(missed_field_id < format->total_field_count); + struct tuple_field *missed_field = + tuple_format_field_by_id(format, missed_field_id); + assert(missed_field != NULL); + diag_set(ClientError, ER_FIELD_MISSING, tuple_field_path(missed_field)); + return -1; +} + /** @sa declaration for details. */ int tuple_init_field_map(struct tuple_format *format, uint32_t *field_map, @@ -440,15 +512,29 @@ tuple_init_field_map(struct tuple_format *format, uint32_t *field_map, (unsigned) format->exact_field_count); return -1; } - if (validate && field_count < format->min_field_count) { - diag_set(ClientError, ER_MIN_FIELD_COUNT, - (unsigned) field_count, - (unsigned) format->min_field_count); - return -1; - } /* first field is simply accessible, so we do not store offset to it */ struct tuple_field *field = tuple_format_field(format, 0); + /* + * Allocate fields_bitmap - a bitmap of fields that are + * present in tuple. + */ + struct region *region = &fiber()->gc; + uint32_t *fields_bitmap = NULL; + if (validate) { + uint32_t fields_bitmap_sz = + DIV_ROUND_UP(format->total_field_count, + sizeof(uint32_t)) * sizeof(uint32_t); + fields_bitmap = region_alloc(region, fields_bitmap_sz); + if (fields_bitmap == NULL) { + diag_set(OutOfMemory, fields_bitmap_sz, "calloc", + "required_fields"); + return -1; + } + memset(fields_bitmap, 0, fields_bitmap_sz); + if (field_count > 0) + bit_set(fields_bitmap, field->id); + } if (validate && !field_mp_type_is_compatible(field->type, mp_typeof(*pos), tuple_field_is_nullable(field))) { @@ -484,9 +570,12 @@ tuple_init_field_map(struct tuple_format *format, uint32_t *field_map, field_map[field->offset_slot] = (uint32_t) (pos - tuple); } + if (validate) + bit_set(fields_bitmap, field->id); mp_next(&pos); } - return 0; + return validate ? + tuple_format_required_fields_test(format, fields_bitmap) : 0; } uint32_t diff --git a/src/box/tuple_format.h b/src/box/tuple_format.h index 21f314126..48201c085 100644 --- a/src/box/tuple_format.h +++ b/src/box/tuple_format.h @@ -114,6 +114,8 @@ struct tuple_field { struct coll *coll; /** Collation identifier. */ uint32_t coll_id; + /** Field unique identifier in tuple_format. */ + uint32_t id; /** Link in tuple_format::fields. */ struct json_token token; }; @@ -173,6 +175,22 @@ struct tuple_format { * Shared names storage used by all formats of a space. */ struct tuple_dictionary *dict; + /** + * This bitmap of "required fields" contains information + * about fields that must present in tuple to be inserted. + * Fields are mapped in bitmap with unique identifier + * field::id used as bit index to set. + * Look for tuple_format_required_fields_test comment for + * more details. + */ + uint32_t *required_fields; + /** + * Total count of format fields in fields subtree. + * Used to allocate temporary bitmap of intialized fields + * during tuple_init_field_map call to verify that all + * required_fields are initialized. + */ + uint32_t total_field_count; /** * Fields comprising the format, organized in a tree. * First level nodes correspond to tuple fields. diff --git a/test/box/alter_limits.result b/test/box/alter_limits.result index 4fd80a374..4fb33dd67 100644 --- a/test/box/alter_limits.result +++ b/test/box/alter_limits.result @@ -842,8 +842,7 @@ index = s:create_index('string', { type = 'tree', unique = false, parts = { 2, -- create index on a non-existing field index = s:create_index('nosuchfield', { type = 'tree', unique = true, parts = { 3, 'string'}}) --- -- error: Tuple field count 2 is less than required by space format or defined indexes - (expected at least 3) +- error: Tuple field 3 required by space format is missing ... s.index.year:drop() --- @@ -864,8 +863,7 @@ s:replace{'Der Baader Meinhof Komplex'} ... index = s:create_index('year', { type = 'tree', unique = false, parts = { 2, 'unsigned'}}) --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... s:drop() --- diff --git a/test/box/ddl.result b/test/box/ddl.result index d3b0d1e0e..3d6d07f43 100644 --- a/test/box/ddl.result +++ b/test/box/ddl.result @@ -326,33 +326,27 @@ box.internal.collation.drop('test') ... box.space._collation:auto_increment{'test'} --- -- error: Tuple field count 2 is less than required by space format or defined indexes - (expected at least 6) +- error: Tuple field 3 required by space format is missing ... box.space._collation:auto_increment{'test', 0, 'ICU'} --- -- error: Tuple field count 4 is less than required by space format or defined indexes - (expected at least 6) +- error: Tuple field 5 required by space format is missing ... box.space._collation:auto_increment{'test', 'ADMIN', 'ICU', 'ru_RU'} --- -- error: Tuple field count 5 is less than required by space format or defined indexes - (expected at least 6) +- error: 'Tuple field 3 type does not match one required by operation: expected unsigned' ... box.space._collation:auto_increment{42, 0, 'ICU', 'ru_RU'} --- -- error: Tuple field count 5 is less than required by space format or defined indexes - (expected at least 6) +- error: 'Tuple field 2 type does not match one required by operation: expected string' ... box.space._collation:auto_increment{'test', 0, 42, 'ru_RU'} --- -- error: Tuple field count 5 is less than required by space format or defined indexes - (expected at least 6) +- error: 'Tuple field 4 type does not match one required by operation: expected string' ... box.space._collation:auto_increment{'test', 0, 'ICU', 42} --- -- error: Tuple field count 5 is less than required by space format or defined indexes - (expected at least 6) +- error: 'Tuple field 5 type does not match one required by operation: expected string' ... box.space._collation:auto_increment{'test', 0, 'ICU', 'ru_RU', setmap{}} --ok --- diff --git a/test/box/misc.result b/test/box/misc.result index 9fecbce76..c3cabcc8a 100644 --- a/test/box/misc.result +++ b/test/box/misc.result @@ -369,7 +369,7 @@ t; 36: box.error.NO_SUCH_SPACE 37: box.error.NO_SUCH_FIELD 38: box.error.EXACT_FIELD_COUNT - 39: box.error.MIN_FIELD_COUNT + 39: box.error.FIELD_MISSING 40: box.error.WAL_IO 41: box.error.MORE_THAN_ONE_TUPLE 42: box.error.ACCESS_DENIED diff --git a/test/box/sql.result b/test/box/sql.result index 1818b294d..78dc47167 100644 --- a/test/box/sql.result +++ b/test/box/sql.result @@ -299,8 +299,7 @@ s:truncate() -- get away with it. space:insert{'Britney'} --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... sorted(space.index.secondary:select('Anything')) --- @@ -308,8 +307,7 @@ sorted(space.index.secondary:select('Anything')) ... space:insert{'Stephanie'} --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... sorted(space.index.secondary:select('Anything')) --- @@ -638,8 +636,7 @@ sorted(space.index.secondary:select('Britney')) -- try to insert the incoplete tuple space:replace{'Spears'} --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... -- check that nothing has been updated space:select{'Spears'} diff --git a/test/box/tree_pk_multipart.result b/test/box/tree_pk_multipart.result index 28cab3f94..93219f666 100644 --- a/test/box/tree_pk_multipart.result +++ b/test/box/tree_pk_multipart.result @@ -490,13 +490,11 @@ i1 = space:create_index('primary', { type = 'tree', parts = {1, 'unsigned', 3, ' ... space:insert{1, 1} --- -- error: Tuple field count 2 is less than required by space format or defined indexes - (expected at least 3) +- error: Tuple field 3 required by space format is missing ... space:replace{1, 1} --- -- error: Tuple field count 2 is less than required by space format or defined indexes - (expected at least 3) +- error: Tuple field 3 required by space format is missing ... space:drop() --- diff --git a/test/engine/ddl.result b/test/engine/ddl.result index 272ff7618..8d34d5ef4 100644 --- a/test/engine/ddl.result +++ b/test/engine/ddl.result @@ -77,8 +77,7 @@ index = space:create_index('primary', {type = 'tree', parts = {1, 'unsigned', 2, ... space:insert({13}) --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... space:drop() --- @@ -844,13 +843,11 @@ s:replace{1, '2', {3, 3}, 4.4, -5, true, {7}, 8, 9} ... s:replace{1, '2', {3, 3}, 4.4, -5, true, {value=7}} --- -- error: Tuple field count 7 is less than required by space format or defined indexes - (expected at least 9) +- error: Tuple field 8 required by space format is missing ... s:replace{1, '2', {3, 3}, 4.4, -5, true, {value=7}, 8} --- -- error: Tuple field count 8 is less than required by space format or defined indexes - (expected at least 9) +- error: Tuple field 9 required by space format is missing ... s:truncate() --- @@ -1334,8 +1331,7 @@ s:format(format) -- Fail, not enough fields. s:replace{2, 2, 2, 2, 2} --- -- error: Tuple field count 5 is less than required by space format or defined indexes - (expected at least 6) +- error: Tuple field 6 required by space format is missing ... s:replace{2, 2, 2, 2, 2, 2, 2} --- @@ -1347,8 +1343,7 @@ format[7] = {name = 'field7', type = 'unsigned'} -- Fail, the tuple {1, ... 1} is invalid for a new format. s:format(format) --- -- error: Tuple field count 6 is less than required by space format or defined indexes - (expected at least 7) +- error: Tuple field 7 required by space format is missing ... s:drop() --- @@ -2012,8 +2007,7 @@ s:create_index('sk', {parts = {4, 'unsigned'}}) -- error: field type ... s:create_index('sk', {parts = {4, 'integer', 5, 'string'}}) -- error: field missing --- -- error: Tuple field count 4 is less than required by space format or defined indexes - (expected at least 5) +- error: Tuple field 5 required by space format is missing ... i1 = s:create_index('i1', {parts = {2, 'string'}, unique = false}) --- @@ -2065,8 +2059,7 @@ i3:alter{parts = {4, 'unsigned'}} -- error: field type ... i3:alter{parts = {4, 'integer', 5, 'string'}} -- error: field missing --- -- error: Tuple field count 4 is less than required by space format or defined indexes - (expected at least 5) +- error: Tuple field 5 required by space format is missing ... i3:alter{parts = {2, 'string', 4, 'integer'}} -- ok --- diff --git a/test/engine/null.result b/test/engine/null.result index 757e63185..d55bc05bd 100644 --- a/test/engine/null.result +++ b/test/engine/null.result @@ -458,8 +458,7 @@ sk = s:create_index('sk', {parts = {2, 'unsigned'}}) ... s:replace{1, 2} -- error --- -- error: Tuple field count 2 is less than required by space format or defined indexes - (expected at least 3) +- error: Tuple field 3 required by space format is missing ... t1 = s:replace{2, 3, 4} --- @@ -530,18 +529,15 @@ sk = s:create_index('sk', {parts = {2, 'unsigned'}}) ... s:replace{1, 2} -- error --- -- error: Tuple field count 2 is less than required by space format or defined indexes - (expected at least 5) +- error: Tuple field 3 required by space format is missing ... s:replace{2, 3, 4} -- error --- -- error: Tuple field count 3 is less than required by space format or defined indexes - (expected at least 5) +- error: Tuple field 5 required by space format is missing ... s:replace{3, 4, 5, 6} -- error --- -- error: Tuple field count 4 is less than required by space format or defined indexes - (expected at least 5) +- error: Tuple field 5 required by space format is missing ... t1 = s:replace{4, 5, 6, 7, 8} --- @@ -1069,8 +1065,7 @@ sk = s:create_index('sk', {parts = {{2, 'unsigned', is_nullable = true}}}) -- Test tuple_compare_slowpath, tuple_compare_with_key_slowpath. s:replace{} -- Fail --- -- error: Tuple field count 0 is less than required by space format or defined indexes - (expected at least 1) +- error: Tuple field 1 required by space format is missing ... -- Compare full vs not full. s:replace{2} @@ -1769,8 +1764,7 @@ s:format(format) -- Field 2 is not nullable. s:insert{5} --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... s:insert{5, box.NULL} --- @@ -1786,8 +1780,7 @@ s:insert{5, box.NULL} ... s:insert{5} --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... s.index.secondary:alter{parts={{2, 'unsigned', is_nullable=false}}} --- @@ -1805,8 +1798,7 @@ s:insert{5, box.NULL} ... s:insert{5} --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... s.index.secondary:alter{parts={{2, 'unsigned', is_nullable=true}}} --- @@ -1849,13 +1841,11 @@ _ = s:delete{5} ... s:format(format) -- Still fail. --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... s.index.secondary:alter{parts={{2, 'unsigned', is_nullable=false}}} -- Still fail. --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... -- Now check we can set nullability to false step by step. _ = s:delete{6} @@ -1873,8 +1863,7 @@ s:insert{5, box.NULL} -- Fail. ... s:insert{5} -- Fail. --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... format[2].is_nullable = true --- @@ -1891,8 +1880,7 @@ s:insert{5, box.NULL} -- Fail. ... s:insert{5} -- Fail. --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... format[2].is_nullable = false --- @@ -1906,8 +1894,7 @@ s:select{} ... s:insert{5} -- Fail. --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... s:insert{9, 10} -- Success. --- diff --git a/test/vinyl/constraint.result b/test/vinyl/constraint.result index 46ed1c9eb..520a0f8aa 100644 --- a/test/vinyl/constraint.result +++ b/test/vinyl/constraint.result @@ -83,13 +83,11 @@ index = space:create_index('primary', { type = 'tree', parts = {1,'unsigned',2,' ... space:insert{1} --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... space:replace{1} --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... space:delete{1} --- @@ -101,8 +99,7 @@ space:update(1, {{'=', 1, 101}}) ... space:upsert({1}, {{'+', 1, 10}}) --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... space:get{1} --- diff --git a/test/vinyl/errinj.result b/test/vinyl/errinj.result index a081575be..23ab845b3 100644 --- a/test/vinyl/errinj.result +++ b/test/vinyl/errinj.result @@ -1634,8 +1634,7 @@ errinj.set("ERRINJ_VY_READ_PAGE_TIMEOUT", 0.001) ... s:create_index('sk', {parts = {2, 'unsigned'}}) -- must fail --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... errinj.set("ERRINJ_VY_READ_PAGE_TIMEOUT", 0) --- @@ -2087,8 +2086,7 @@ fiber.sleep(0) ... s:format{{'key', 'unsigned'}, {'value', 'unsigned'}} -- must fail --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... s:select() --- @@ -2112,8 +2110,7 @@ fiber.sleep(0) ... s:create_index('sk', {parts = {2, 'unsigned'}}) --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... s:select() --- diff --git a/test/vinyl/savepoint.result b/test/vinyl/savepoint.result index d7b57a775..a62f2ea80 100644 --- a/test/vinyl/savepoint.result +++ b/test/vinyl/savepoint.result @@ -124,8 +124,7 @@ index2 = space:create_index('secondary', { parts = {2, 'int', 3, 'str'} }) ... space:insert({1}) --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 3) +- error: Tuple field 2 required by space format is missing ... space:insert({1, 1, 'a'}) --- @@ -623,8 +622,7 @@ space:insert({4, 2, 'b'}) ... space:upsert({2}, {{'=', 4, 1000}}) --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 3) +- error: Tuple field 2 required by space format is missing ... index3:delete({3, 'a'}) --- -- 2.19.2 ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [tarantool-patches] [PATCH v1 4/4] box: refactor tuple_init_field_map to use bitmap 2018-12-27 11:15 ` [PATCH v1 4/4] box: refactor tuple_init_field_map to use bitmap Kirill Shcherbatov @ 2018-12-27 11:48 ` Konstantin Osipov 2018-12-27 19:12 ` Vladimir Davydov 1 sibling, 0 replies; 18+ messages in thread From: Konstantin Osipov @ 2018-12-27 11:48 UTC (permalink / raw) To: tarantool-patches; +Cc: vdavydov.dev, Kirill Shcherbatov * Kirill Shcherbatov <kshcherbatov@tarantool.org> [18/12/27 14:19]: > Refactored tuple_init_field_map to fill a local bitmap and > compare it with template required_fields bitmap containing > information about required fields. Each field is mapped to > bitmap with field:id - unique field identifier. > This approach to check the required fields will work even after > the introduction of JSON paths, when the field tree becomes > multilevel. > > Needed for #1012 > --- > src/box/errcode.h | 2 +- > src/box/tuple_format.c | 103 ++++++++++++++++++++++++++++-- > src/box/tuple_format.h | 18 ++++++ > test/box/alter_limits.result | 6 +- > test/box/ddl.result | 18 ++---- > test/box/misc.result | 2 +- > test/box/sql.result | 9 +-- > test/box/tree_pk_multipart.result | 6 +- > test/engine/ddl.result | 21 ++---- > test/engine/null.result | 39 ++++------- > test/vinyl/constraint.result | 9 +-- > test/vinyl/errinj.result | 9 +-- > test/vinyl/savepoint.result | 6 +- > 13 files changed, 157 insertions(+), 91 deletions(-) > > diff --git a/src/box/errcode.h b/src/box/errcode.h > index 94381f9f7..f7dbb948e 100644 > --- a/src/box/errcode.h > +++ b/src/box/errcode.h > @@ -91,7 +91,7 @@ struct errcode_record { > /* 36 */_(ER_NO_SUCH_SPACE, "Space '%s' does not exist") \ > /* 37 */_(ER_NO_SUCH_FIELD, "Field %d was not found in the tuple") \ > /* 38 */_(ER_EXACT_FIELD_COUNT, "Tuple field count %u does not match space field count %u") \ > - /* 39 */_(ER_MIN_FIELD_COUNT, "Tuple field count %u is less than required by space format or defined indexes (expected at least %u)") \ > + /* 39 */_(ER_FIELD_MISSING, "Tuple field %s required by space format is missing") \ > /* 40 */_(ER_WAL_IO, "Failed to write to disk") \ > /* 41 */_(ER_MORE_THAN_ONE_TUPLE, "Get() doesn't support partial keys and non-unique indexes") \ > /* 42 */_(ER_ACCESS_DENIED, "%s access to %s '%s' is denied for user '%s'") \ > diff --git a/src/box/tuple_format.c b/src/box/tuple_format.c > index d7489dcd0..a2b7fc7e6 100644 > --- a/src/box/tuple_format.c > +++ b/src/box/tuple_format.c > @@ -28,6 +28,8 @@ > * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF > * SUCH DAMAGE. > */ > +#include "bit/bit.h" > +#include "fiber.h" > #include "json/json.h" > #include "tuple_format.h" > #include "coll_id_cache.h" > @@ -207,6 +209,30 @@ tuple_format_create(struct tuple_format *format, struct key_def * const *keys, > return -1; > } > format->field_map_size = field_map_size; > + > + /* Allocate required fields bitmap. */ > + uint32_t required_fields_sz = > + DIV_ROUND_UP(format->total_field_count, sizeof(uint32_t)) * > + sizeof(uint32_t); > + format->required_fields = calloc(1, required_fields_sz); > + if (format->required_fields == NULL) { > + diag_set(OutOfMemory, required_fields_sz, "calloc", > + "format->required_fields"); > + return -1; > + } > + struct tuple_field *field; > + struct json_token *root = (struct json_token *)&format->fields.root; > + json_tree_foreach_entry_preorder(field, root, struct tuple_field, > + token) { > + /* > + * Mark all leaf non-nullable fields as required > + * setting corresponding bit 1 in format > + * required_fields. > + */ > + if (json_token_is_leaf(&field->token) && > + !tuple_field_is_nullable(field)) > + bit_set(format->required_fields, field->id); > + } > return 0; > } > > @@ -305,6 +331,7 @@ tuple_format_alloc(struct key_def * const *keys, uint16_t key_count, > struct tuple_field *field = tuple_field_new(); > if (field == NULL) > goto error; > + field->id = fieldno; > field->token.num = fieldno; > field->token.type = JSON_TOKEN_NUM; > if (json_tree_add(&format->fields, &format->fields.root, > @@ -324,6 +351,8 @@ tuple_format_alloc(struct key_def * const *keys, uint16_t key_count, > format->dict = dict; > tuple_dictionary_ref(dict); > } > + format->total_field_count = field_count; > + format->required_fields = NULL; > format->refs = 0; > format->id = FORMAT_ID_NIL; > format->index_field_count = index_field_count; > @@ -340,6 +369,7 @@ error: > static inline void > tuple_format_destroy(struct tuple_format *format) > { > + free(format->required_fields); > tuple_format_destroy_fields(format); > tuple_dictionary_unref(format->dict); > } > @@ -421,6 +451,48 @@ tuple_format1_can_store_format2_tuples(struct tuple_format *format1, > return true; > } > > +/** > + * Return meta information of a tuple field given a format > + * and a unique field identifier. > + * Typically used on error handling so it is not > + * performance-critical and may use full-tree-traverse on lookup. > + */ > +static struct tuple_field * > +tuple_format_field_by_id(struct tuple_format *format, uint32_t id) > +{ > + struct tuple_field *field; > + json_tree_foreach_entry_preorder(field, &format->fields.root, > + struct tuple_field, token) { > + if (field->id == id) > + return field; > + } > + return NULL; > +} > + > +/** > + * Analyze required_fields to ensure that all required fields > + * present in tuple. Routine relies on required_fields is > + * initialized on tuple_format_create and all required field's > + * bits ids are set 1. > + */ > +static int > +tuple_format_required_fields_test(struct tuple_format *format, > + uint32_t *required_fields) > +{ > + uint32_t bitmap_len = > + DIV_ROUND_UP(format->total_field_count, sizeof(uint32_t)); > + uint32_t missed_field_id; > + if (likely(bitmap_majority_test(required_fields, format->required_fields, > + bitmap_len, &missed_field_id) == 0)) > + return 0; > + assert(missed_field_id < format->total_field_count); > + struct tuple_field *missed_field = > + tuple_format_field_by_id(format, missed_field_id); > + assert(missed_field != NULL); > + diag_set(ClientError, ER_FIELD_MISSING, tuple_field_path(missed_field)); > + return -1; > +} > + > /** @sa declaration for details. */ > int > tuple_init_field_map(struct tuple_format *format, uint32_t *field_map, > @@ -440,15 +512,29 @@ tuple_init_field_map(struct tuple_format *format, uint32_t *field_map, > (unsigned) format->exact_field_count); > return -1; > } > - if (validate && field_count < format->min_field_count) { > - diag_set(ClientError, ER_MIN_FIELD_COUNT, > - (unsigned) field_count, > - (unsigned) format->min_field_count); > - return -1; > - } > > /* first field is simply accessible, so we do not store offset to it */ > struct tuple_field *field = tuple_format_field(format, 0); > + /* > + * Allocate fields_bitmap - a bitmap of fields that are Please rename fields_bitmap to field_bitmap. When a noun is used as an adjective, it is used in singular form. -- Konstantin Osipov, Moscow, Russia, +7 903 626 22 32 http://tarantool.io - www.twitter.com/kostja_osipov ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH v1 4/4] box: refactor tuple_init_field_map to use bitmap 2018-12-27 11:15 ` [PATCH v1 4/4] box: refactor tuple_init_field_map to use bitmap Kirill Shcherbatov 2018-12-27 11:48 ` [tarantool-patches] " Konstantin Osipov @ 2018-12-27 19:12 ` Vladimir Davydov 2018-12-29 12:58 ` [tarantool-patches] " Kirill Shcherbatov 1 sibling, 1 reply; 18+ messages in thread From: Vladimir Davydov @ 2018-12-27 19:12 UTC (permalink / raw) To: Kirill Shcherbatov; +Cc: tarantool-patches, kostja On Thu, Dec 27, 2018 at 02:15:55PM +0300, Kirill Shcherbatov wrote: > Refactored tuple_init_field_map to fill a local bitmap and > compare it with template required_fields bitmap containing > information about required fields. Each field is mapped to > bitmap with field:id - unique field identifier. > This approach to check the required fields will work even after > the introduction of JSON paths, when the field tree becomes > multilevel. > > Needed for #1012 > --- > src/box/errcode.h | 2 +- > src/box/tuple_format.c | 103 ++++++++++++++++++++++++++++-- > src/box/tuple_format.h | 18 ++++++ > test/box/alter_limits.result | 6 +- > test/box/ddl.result | 18 ++---- > test/box/misc.result | 2 +- > test/box/sql.result | 9 +-- > test/box/tree_pk_multipart.result | 6 +- > test/engine/ddl.result | 21 ++---- > test/engine/null.result | 39 ++++------- > test/vinyl/constraint.result | 9 +-- > test/vinyl/errinj.result | 9 +-- > test/vinyl/savepoint.result | 6 +- > 13 files changed, 157 insertions(+), 91 deletions(-) > > diff --git a/src/box/errcode.h b/src/box/errcode.h > index 94381f9f7..f7dbb948e 100644 > --- a/src/box/errcode.h > +++ b/src/box/errcode.h > @@ -91,7 +91,7 @@ struct errcode_record { > /* 36 */_(ER_NO_SUCH_SPACE, "Space '%s' does not exist") \ > /* 37 */_(ER_NO_SUCH_FIELD, "Field %d was not found in the tuple") \ > /* 38 */_(ER_EXACT_FIELD_COUNT, "Tuple field count %u does not match space field count %u") \ > - /* 39 */_(ER_MIN_FIELD_COUNT, "Tuple field count %u is less than required by space format or defined indexes (expected at least %u)") \ > + /* 39 */_(ER_FIELD_MISSING, "Tuple field %s required by space format is missing") \ > /* 40 */_(ER_WAL_IO, "Failed to write to disk") \ > /* 41 */_(ER_MORE_THAN_ONE_TUPLE, "Get() doesn't support partial keys and non-unique indexes") \ > /* 42 */_(ER_ACCESS_DENIED, "%s access to %s '%s' is denied for user '%s'") \ > diff --git a/src/box/tuple_format.c b/src/box/tuple_format.c > index d7489dcd0..a2b7fc7e6 100644 > --- a/src/box/tuple_format.c > +++ b/src/box/tuple_format.c > @@ -28,6 +28,8 @@ > * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF > * SUCH DAMAGE. > */ > +#include "bit/bit.h" > +#include "fiber.h" > #include "json/json.h" > #include "tuple_format.h" > #include "coll_id_cache.h" > @@ -207,6 +209,30 @@ tuple_format_create(struct tuple_format *format, struct key_def * const *keys, > return -1; > } > format->field_map_size = field_map_size; > + > + /* Allocate required fields bitmap. */ > + uint32_t required_fields_sz = > + DIV_ROUND_UP(format->total_field_count, sizeof(uint32_t)) * > + sizeof(uint32_t); let total_field_count = 31 sizeof(uint32_t) = 4 DIV_ROUND_UP(total_field_count, sizeof(uint32_t)) = 8 required_fields_sz = 9 * 4 = 32 bytes while you only need 4 bytes to store the bitmap... > + format->required_fields = calloc(1, required_fields_sz); > + if (format->required_fields == NULL) { > + diag_set(OutOfMemory, required_fields_sz, "calloc", > + "format->required_fields"); > + return -1; > + } > + struct tuple_field *field; > + struct json_token *root = (struct json_token *)&format->fields.root; > + json_tree_foreach_entry_preorder(field, root, struct tuple_field, > + token) { > + /* > + * Mark all leaf non-nullable fields as required > + * setting corresponding bit 1 in format > + * required_fields. > + */ > + if (json_token_is_leaf(&field->token) && > + !tuple_field_is_nullable(field)) > + bit_set(format->required_fields, field->id); > + } > return 0; > } > > @@ -305,6 +331,7 @@ tuple_format_alloc(struct key_def * const *keys, uint16_t key_count, > struct tuple_field *field = tuple_field_new(); > if (field == NULL) > goto error; > + field->id = fieldno; > field->token.num = fieldno; > field->token.type = JSON_TOKEN_NUM; > if (json_tree_add(&format->fields, &format->fields.root, > @@ -324,6 +351,8 @@ tuple_format_alloc(struct key_def * const *keys, uint16_t key_count, > format->dict = dict; > tuple_dictionary_ref(dict); > } > + format->total_field_count = field_count; > + format->required_fields = NULL; > format->refs = 0; > format->id = FORMAT_ID_NIL; > format->index_field_count = index_field_count; > @@ -340,6 +369,7 @@ error: > static inline void > tuple_format_destroy(struct tuple_format *format) > { > + free(format->required_fields); > tuple_format_destroy_fields(format); > tuple_dictionary_unref(format->dict); > } > @@ -421,6 +451,48 @@ tuple_format1_can_store_format2_tuples(struct tuple_format *format1, > return true; > } > > +/** > + * Return meta information of a tuple field given a format > + * and a unique field identifier. > + * Typically used on error handling so it is not Typically? There's just one place where this function is used. > + * performance-critical and may use full-tree-traverse on lookup. > + */ > +static struct tuple_field * > +tuple_format_field_by_id(struct tuple_format *format, uint32_t id) > +{ > + struct tuple_field *field; > + json_tree_foreach_entry_preorder(field, &format->fields.root, > + struct tuple_field, token) { > + if (field->id == id) > + return field; > + } > + return NULL; > +} > + > +/** > + * Analyze required_fields to ensure that all required fields > + * present in tuple. Routine relies on required_fields is > + * initialized on tuple_format_create and all required field's > + * bits ids are set 1. > + */ > +static int > +tuple_format_required_fields_test(struct tuple_format *format, > + uint32_t *required_fields) > +{ > + uint32_t bitmap_len = > + DIV_ROUND_UP(format->total_field_count, sizeof(uint32_t)); This one looks different from required_fields_sz calculation in tuple_format_create(). What's going on? Looks like it would be a good idea to hide this calculation behind a helper function. > + uint32_t missed_field_id; > + if (likely(bitmap_majority_test(required_fields, format->required_fields, > + bitmap_len, &missed_field_id) == 0)) > + return 0; > + assert(missed_field_id < format->total_field_count); > + struct tuple_field *missed_field = missing_field > + tuple_format_field_by_id(format, missed_field_id); > + assert(missed_field != NULL); > + diag_set(ClientError, ER_FIELD_MISSING, tuple_field_path(missed_field)); > + return -1; > +} > + > /** @sa declaration for details. */ > int > tuple_init_field_map(struct tuple_format *format, uint32_t *field_map, > @@ -440,15 +512,29 @@ tuple_init_field_map(struct tuple_format *format, uint32_t *field_map, > (unsigned) format->exact_field_count); > return -1; > } > - if (validate && field_count < format->min_field_count) { > - diag_set(ClientError, ER_MIN_FIELD_COUNT, > - (unsigned) field_count, > - (unsigned) format->min_field_count); > - return -1; > - } > > /* first field is simply accessible, so we do not store offset to it */ > struct tuple_field *field = tuple_format_field(format, 0); > + /* > + * Allocate fields_bitmap - a bitmap of fields that are > + * present in tuple. > + */ > + struct region *region = &fiber()->gc; > + uint32_t *fields_bitmap = NULL; > + if (validate) { > + uint32_t fields_bitmap_sz = > + DIV_ROUND_UP(format->total_field_count, > + sizeof(uint32_t)) * sizeof(uint32_t); > + fields_bitmap = region_alloc(region, fields_bitmap_sz); > + if (fields_bitmap == NULL) { > + diag_set(OutOfMemory, fields_bitmap_sz, "calloc", > + "required_fields"); > + return -1; > + } > + memset(fields_bitmap, 0, fields_bitmap_sz); > + if (field_count > 0) field_count can't be 0 - otherwise we would bail out early. > + bit_set(fields_bitmap, field->id); > + } > if (validate && > !field_mp_type_is_compatible(field->type, mp_typeof(*pos), > tuple_field_is_nullable(field))) { > @@ -484,9 +570,12 @@ tuple_init_field_map(struct tuple_format *format, uint32_t *field_map, > field_map[field->offset_slot] = > (uint32_t) (pos - tuple); > } > + if (validate) > + bit_set(fields_bitmap, field->id); > mp_next(&pos); > } > - return 0; > + return validate ? > + tuple_format_required_fields_test(format, fields_bitmap) : 0; > } ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [tarantool-patches] Re: [PATCH v1 4/4] box: refactor tuple_init_field_map to use bitmap 2018-12-27 19:12 ` Vladimir Davydov @ 2018-12-29 12:58 ` Kirill Shcherbatov 2018-12-29 13:22 ` Vladimir Davydov 2018-12-29 16:25 ` Vladimir Davydov 0 siblings, 2 replies; 18+ messages in thread From: Kirill Shcherbatov @ 2018-12-29 12:58 UTC (permalink / raw) To: tarantool-patches, Vladimir Davydov Hi! Thank you for review. > let total_field_count = 31 > sizeof(uint32_t) = 4 > DIV_ROUND_UP(total_field_count, sizeof(uint32_t)) = 8 > required_fields_sz = 9 * 4 = 32 bytes > > while you only need 4 bytes to store the bitmap... > This one looks different from required_fields_sz calculation in > tuple_format_create(). What's going on? > > Looks like it would be a good idea to hide this calculation behind > a helper function. Implemented as a part of prev. patch. >> + if (field_count > 0) > > field_count can't be 0 - otherwise we would bail out early. It is not so, try paste assert here and run s = box.schema.space.create('test', {engine = engine}) pk = s:create_index('pk') sk = s:create_index('sk', {parts = {{2, 'unsigned', is_nullable = true}}}) s:replace{} -- Fail ====================================== Refactored tuple_init_field_map to fill a local bitmap and compare it with template required_fields bitmap containing information about required fields. Each field is mapped to bitmap with field:id - unique field identifier. This approach to check the required fields will work even after the introduction of JSON paths, when the field tree becomes multilevel. Needed for #1012 --- src/box/errcode.h | 2 +- src/box/tuple_format.c | 91 ++++++++++++++++++++++++++++--- src/box/tuple_format.h | 20 +++++++ test/box/alter_limits.result | 6 +- test/box/ddl.result | 18 ++---- test/box/misc.result | 2 +- test/box/sql.result | 9 +-- test/box/tree_pk_multipart.result | 6 +- test/engine/ddl.result | 21 +++---- test/engine/null.result | 39 +++++-------- test/vinyl/constraint.result | 9 +-- test/vinyl/errinj.result | 9 +-- test/vinyl/savepoint.result | 6 +- 13 files changed, 147 insertions(+), 91 deletions(-) diff --git a/src/box/errcode.h b/src/box/errcode.h index 94381f9f7..f7dbb948e 100644 --- a/src/box/errcode.h +++ b/src/box/errcode.h @@ -91,7 +91,7 @@ struct errcode_record { /* 36 */_(ER_NO_SUCH_SPACE, "Space '%s' does not exist") \ /* 37 */_(ER_NO_SUCH_FIELD, "Field %d was not found in the tuple") \ /* 38 */_(ER_EXACT_FIELD_COUNT, "Tuple field count %u does not match space field count %u") \ - /* 39 */_(ER_MIN_FIELD_COUNT, "Tuple field count %u is less than required by space format or defined indexes (expected at least %u)") \ + /* 39 */_(ER_FIELD_MISSING, "Tuple field %s required by space format is missing") \ /* 40 */_(ER_WAL_IO, "Failed to write to disk") \ /* 41 */_(ER_MORE_THAN_ONE_TUPLE, "Get() doesn't support partial keys and non-unique indexes") \ /* 42 */_(ER_ACCESS_DENIED, "%s access to %s '%s' is denied for user '%s'") \ diff --git a/src/box/tuple_format.c b/src/box/tuple_format.c index d7489dcd0..f4ac9e083 100644 --- a/src/box/tuple_format.c +++ b/src/box/tuple_format.c @@ -28,6 +28,8 @@ * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ +#include "bit/bit.h" +#include "fiber.h" #include "json/json.h" #include "tuple_format.h" #include "coll_id_cache.h" @@ -207,6 +209,26 @@ tuple_format_create(struct tuple_format *format, struct key_def * const *keys, return -1; } format->field_map_size = field_map_size; + + uint32_t required_fields_sz = bitmap_size(format->total_field_count); + format->required_fields = calloc(1, required_fields_sz); + if (format->required_fields == NULL) { + diag_set(OutOfMemory, required_fields_sz, "calloc", + "format->required_fields"); + return -1; + } + struct tuple_field *field; + json_tree_foreach_entry_preorder(field, &format->fields.root, + struct tuple_field, token) { + /* + * Mark all leaf non-nullable fields as "required" + * setting corresponding bit 1 in bitmap + * format:required_fields. + */ + if (json_token_is_leaf(&field->token) && + !tuple_field_is_nullable(field)) + bit_set(format->required_fields, field->id); + } return 0; } @@ -305,6 +327,7 @@ tuple_format_alloc(struct key_def * const *keys, uint16_t key_count, struct tuple_field *field = tuple_field_new(); if (field == NULL) goto error; + field->id = fieldno; field->token.num = fieldno; field->token.type = JSON_TOKEN_NUM; if (json_tree_add(&format->fields, &format->fields.root, @@ -324,6 +347,8 @@ tuple_format_alloc(struct key_def * const *keys, uint16_t key_count, format->dict = dict; tuple_dictionary_ref(dict); } + format->total_field_count = field_count; + format->required_fields = NULL; format->refs = 0; format->id = FORMAT_ID_NIL; format->index_field_count = index_field_count; @@ -340,6 +365,7 @@ error: static inline void tuple_format_destroy(struct tuple_format *format) { + free(format->required_fields); tuple_format_destroy_fields(format); tuple_dictionary_unref(format->dict); } @@ -421,6 +447,24 @@ tuple_format1_can_store_format2_tuples(struct tuple_format *format1, return true; } +/** + * Return meta information of a tuple field given a format + * and a unique field identifier. + * Used for error handling, so it is not performance-critical and + * may use full-tree-traverse on lookup. + */ +static struct tuple_field * +tuple_format_field_by_id(struct tuple_format *format, uint32_t id) +{ + struct tuple_field *field; + json_tree_foreach_entry_preorder(field, &format->fields.root, + struct tuple_field, token) { + if (field->id == id) + return field; + } + return NULL; +} + /** @sa declaration for details. */ int tuple_init_field_map(struct tuple_format *format, uint32_t *field_map, @@ -440,15 +484,30 @@ tuple_init_field_map(struct tuple_format *format, uint32_t *field_map, (unsigned) format->exact_field_count); return -1; } - if (validate && field_count < format->min_field_count) { - diag_set(ClientError, ER_MIN_FIELD_COUNT, - (unsigned) field_count, - (unsigned) format->min_field_count); - return -1; - } /* first field is simply accessible, so we do not store offset to it */ struct tuple_field *field = tuple_format_field(format, 0); + /* + * Allocate fields_bitmap - a copy of the initialized + * format:required_fields bitmap. The field:id bits would + * be nullified for founded fields during tuple parse to + * raise an error when some required field is missing. + */ + struct region *region = &fiber()->gc; + char *fields_bitmap = NULL; + uint32_t fields_bitmap_sz = bitmap_size(format->total_field_count); + if (validate) { + fields_bitmap = region_alloc(region, fields_bitmap_sz); + if (fields_bitmap == NULL) { + diag_set(OutOfMemory, fields_bitmap_sz, "calloc", + "required_fields"); + return -1; + } + memcpy(fields_bitmap, format->required_fields, + fields_bitmap_sz); + if (field_count > 0) + bit_clear(fields_bitmap, field->id); + } if (validate && !field_mp_type_is_compatible(field->type, mp_typeof(*pos), tuple_field_is_nullable(field))) { @@ -484,9 +543,27 @@ tuple_init_field_map(struct tuple_format *format, uint32_t *field_map, field_map[field->offset_slot] = (uint32_t) (pos - tuple); } + if (validate) + bit_clear(fields_bitmap, field->id); mp_next(&pos); } - return 0; + if (!validate) + return 0; + + /** + * Test whether all required fields bits has been + * overwritten with 0. Otherwise raise an error. + */ + size_t missing_field_id = bit_find(fields_bitmap, fields_bitmap_sz); + if (missing_field_id == SIZE_MAX) + return 0; + assert(missing_field_id < format->total_field_count); + struct tuple_field *missing_field = + tuple_format_field_by_id(format, missing_field_id); + assert(missing_field != NULL); + diag_set(ClientError, ER_FIELD_MISSING, + tuple_field_path(missing_field)); + return -1; } uint32_t diff --git a/src/box/tuple_format.h b/src/box/tuple_format.h index 21f314126..5e7cbdb8c 100644 --- a/src/box/tuple_format.h +++ b/src/box/tuple_format.h @@ -114,6 +114,8 @@ struct tuple_field { struct coll *coll; /** Collation identifier. */ uint32_t coll_id; + /** Field unique identifier in tuple_format. */ + uint32_t id; /** Link in tuple_format::fields. */ struct json_token token; }; @@ -173,6 +175,24 @@ struct tuple_format { * Shared names storage used by all formats of a space. */ struct tuple_dictionary *dict; + /** + * Bitmap of "required fields" containing information + * about fields that must present in tuple to be inserted. + * Fields are mapped in bitmap with unique identifier + * field::id used as index of bit to set. Bitmap is + * initialized on tuple_format_create for all leaf + * non-nullable fields. + */ + char *required_fields; + /** + * Total count of format fields in fields subtree. + * Used to allocate per-field memory chunks: a temporary + * modifiable copy of format:required_fields on region to + * test that all required fields are present in tuple + * setting founded fields null on tuple_init_field_map + * parse. + */ + uint32_t total_field_count; /** * Fields comprising the format, organized in a tree. * First level nodes correspond to tuple fields. diff --git a/test/box/alter_limits.result b/test/box/alter_limits.result index 4fd80a374..4fb33dd67 100644 --- a/test/box/alter_limits.result +++ b/test/box/alter_limits.result @@ -842,8 +842,7 @@ index = s:create_index('string', { type = 'tree', unique = false, parts = { 2, -- create index on a non-existing field index = s:create_index('nosuchfield', { type = 'tree', unique = true, parts = { 3, 'string'}}) --- -- error: Tuple field count 2 is less than required by space format or defined indexes - (expected at least 3) +- error: Tuple field 3 required by space format is missing ... s.index.year:drop() --- @@ -864,8 +863,7 @@ s:replace{'Der Baader Meinhof Komplex'} ... index = s:create_index('year', { type = 'tree', unique = false, parts = { 2, 'unsigned'}}) --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... s:drop() --- diff --git a/test/box/ddl.result b/test/box/ddl.result index d3b0d1e0e..3d6d07f43 100644 --- a/test/box/ddl.result +++ b/test/box/ddl.result @@ -326,33 +326,27 @@ box.internal.collation.drop('test') ... box.space._collation:auto_increment{'test'} --- -- error: Tuple field count 2 is less than required by space format or defined indexes - (expected at least 6) +- error: Tuple field 3 required by space format is missing ... box.space._collation:auto_increment{'test', 0, 'ICU'} --- -- error: Tuple field count 4 is less than required by space format or defined indexes - (expected at least 6) +- error: Tuple field 5 required by space format is missing ... box.space._collation:auto_increment{'test', 'ADMIN', 'ICU', 'ru_RU'} --- -- error: Tuple field count 5 is less than required by space format or defined indexes - (expected at least 6) +- error: 'Tuple field 3 type does not match one required by operation: expected unsigned' ... box.space._collation:auto_increment{42, 0, 'ICU', 'ru_RU'} --- -- error: Tuple field count 5 is less than required by space format or defined indexes - (expected at least 6) +- error: 'Tuple field 2 type does not match one required by operation: expected string' ... box.space._collation:auto_increment{'test', 0, 42, 'ru_RU'} --- -- error: Tuple field count 5 is less than required by space format or defined indexes - (expected at least 6) +- error: 'Tuple field 4 type does not match one required by operation: expected string' ... box.space._collation:auto_increment{'test', 0, 'ICU', 42} --- -- error: Tuple field count 5 is less than required by space format or defined indexes - (expected at least 6) +- error: 'Tuple field 5 type does not match one required by operation: expected string' ... box.space._collation:auto_increment{'test', 0, 'ICU', 'ru_RU', setmap{}} --ok --- diff --git a/test/box/misc.result b/test/box/misc.result index 9fecbce76..c3cabcc8a 100644 --- a/test/box/misc.result +++ b/test/box/misc.result @@ -369,7 +369,7 @@ t; 36: box.error.NO_SUCH_SPACE 37: box.error.NO_SUCH_FIELD 38: box.error.EXACT_FIELD_COUNT - 39: box.error.MIN_FIELD_COUNT + 39: box.error.FIELD_MISSING 40: box.error.WAL_IO 41: box.error.MORE_THAN_ONE_TUPLE 42: box.error.ACCESS_DENIED diff --git a/test/box/sql.result b/test/box/sql.result index 1818b294d..78dc47167 100644 --- a/test/box/sql.result +++ b/test/box/sql.result @@ -299,8 +299,7 @@ s:truncate() -- get away with it. space:insert{'Britney'} --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... sorted(space.index.secondary:select('Anything')) --- @@ -308,8 +307,7 @@ sorted(space.index.secondary:select('Anything')) ... space:insert{'Stephanie'} --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... sorted(space.index.secondary:select('Anything')) --- @@ -638,8 +636,7 @@ sorted(space.index.secondary:select('Britney')) -- try to insert the incoplete tuple space:replace{'Spears'} --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... -- check that nothing has been updated space:select{'Spears'} diff --git a/test/box/tree_pk_multipart.result b/test/box/tree_pk_multipart.result index 28cab3f94..93219f666 100644 --- a/test/box/tree_pk_multipart.result +++ b/test/box/tree_pk_multipart.result @@ -490,13 +490,11 @@ i1 = space:create_index('primary', { type = 'tree', parts = {1, 'unsigned', 3, ' ... space:insert{1, 1} --- -- error: Tuple field count 2 is less than required by space format or defined indexes - (expected at least 3) +- error: Tuple field 3 required by space format is missing ... space:replace{1, 1} --- -- error: Tuple field count 2 is less than required by space format or defined indexes - (expected at least 3) +- error: Tuple field 3 required by space format is missing ... space:drop() --- diff --git a/test/engine/ddl.result b/test/engine/ddl.result index 272ff7618..8d34d5ef4 100644 --- a/test/engine/ddl.result +++ b/test/engine/ddl.result @@ -77,8 +77,7 @@ index = space:create_index('primary', {type = 'tree', parts = {1, 'unsigned', 2, ... space:insert({13}) --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... space:drop() --- @@ -844,13 +843,11 @@ s:replace{1, '2', {3, 3}, 4.4, -5, true, {7}, 8, 9} ... s:replace{1, '2', {3, 3}, 4.4, -5, true, {value=7}} --- -- error: Tuple field count 7 is less than required by space format or defined indexes - (expected at least 9) +- error: Tuple field 8 required by space format is missing ... s:replace{1, '2', {3, 3}, 4.4, -5, true, {value=7}, 8} --- -- error: Tuple field count 8 is less than required by space format or defined indexes - (expected at least 9) +- error: Tuple field 9 required by space format is missing ... s:truncate() --- @@ -1334,8 +1331,7 @@ s:format(format) -- Fail, not enough fields. s:replace{2, 2, 2, 2, 2} --- -- error: Tuple field count 5 is less than required by space format or defined indexes - (expected at least 6) +- error: Tuple field 6 required by space format is missing ... s:replace{2, 2, 2, 2, 2, 2, 2} --- @@ -1347,8 +1343,7 @@ format[7] = {name = 'field7', type = 'unsigned'} -- Fail, the tuple {1, ... 1} is invalid for a new format. s:format(format) --- -- error: Tuple field count 6 is less than required by space format or defined indexes - (expected at least 7) +- error: Tuple field 7 required by space format is missing ... s:drop() --- @@ -2012,8 +2007,7 @@ s:create_index('sk', {parts = {4, 'unsigned'}}) -- error: field type ... s:create_index('sk', {parts = {4, 'integer', 5, 'string'}}) -- error: field missing --- -- error: Tuple field count 4 is less than required by space format or defined indexes - (expected at least 5) +- error: Tuple field 5 required by space format is missing ... i1 = s:create_index('i1', {parts = {2, 'string'}, unique = false}) --- @@ -2065,8 +2059,7 @@ i3:alter{parts = {4, 'unsigned'}} -- error: field type ... i3:alter{parts = {4, 'integer', 5, 'string'}} -- error: field missing --- -- error: Tuple field count 4 is less than required by space format or defined indexes - (expected at least 5) +- error: Tuple field 5 required by space format is missing ... i3:alter{parts = {2, 'string', 4, 'integer'}} -- ok --- diff --git a/test/engine/null.result b/test/engine/null.result index 757e63185..d55bc05bd 100644 --- a/test/engine/null.result +++ b/test/engine/null.result @@ -458,8 +458,7 @@ sk = s:create_index('sk', {parts = {2, 'unsigned'}}) ... s:replace{1, 2} -- error --- -- error: Tuple field count 2 is less than required by space format or defined indexes - (expected at least 3) +- error: Tuple field 3 required by space format is missing ... t1 = s:replace{2, 3, 4} --- @@ -530,18 +529,15 @@ sk = s:create_index('sk', {parts = {2, 'unsigned'}}) ... s:replace{1, 2} -- error --- -- error: Tuple field count 2 is less than required by space format or defined indexes - (expected at least 5) +- error: Tuple field 3 required by space format is missing ... s:replace{2, 3, 4} -- error --- -- error: Tuple field count 3 is less than required by space format or defined indexes - (expected at least 5) +- error: Tuple field 5 required by space format is missing ... s:replace{3, 4, 5, 6} -- error --- -- error: Tuple field count 4 is less than required by space format or defined indexes - (expected at least 5) +- error: Tuple field 5 required by space format is missing ... t1 = s:replace{4, 5, 6, 7, 8} --- @@ -1069,8 +1065,7 @@ sk = s:create_index('sk', {parts = {{2, 'unsigned', is_nullable = true}}}) -- Test tuple_compare_slowpath, tuple_compare_with_key_slowpath. s:replace{} -- Fail --- -- error: Tuple field count 0 is less than required by space format or defined indexes - (expected at least 1) +- error: Tuple field 1 required by space format is missing ... -- Compare full vs not full. s:replace{2} @@ -1769,8 +1764,7 @@ s:format(format) -- Field 2 is not nullable. s:insert{5} --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... s:insert{5, box.NULL} --- @@ -1786,8 +1780,7 @@ s:insert{5, box.NULL} ... s:insert{5} --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... s.index.secondary:alter{parts={{2, 'unsigned', is_nullable=false}}} --- @@ -1805,8 +1798,7 @@ s:insert{5, box.NULL} ... s:insert{5} --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... s.index.secondary:alter{parts={{2, 'unsigned', is_nullable=true}}} --- @@ -1849,13 +1841,11 @@ _ = s:delete{5} ... s:format(format) -- Still fail. --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... s.index.secondary:alter{parts={{2, 'unsigned', is_nullable=false}}} -- Still fail. --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... -- Now check we can set nullability to false step by step. _ = s:delete{6} @@ -1873,8 +1863,7 @@ s:insert{5, box.NULL} -- Fail. ... s:insert{5} -- Fail. --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... format[2].is_nullable = true --- @@ -1891,8 +1880,7 @@ s:insert{5, box.NULL} -- Fail. ... s:insert{5} -- Fail. --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... format[2].is_nullable = false --- @@ -1906,8 +1894,7 @@ s:select{} ... s:insert{5} -- Fail. --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... s:insert{9, 10} -- Success. --- diff --git a/test/vinyl/constraint.result b/test/vinyl/constraint.result index 46ed1c9eb..520a0f8aa 100644 --- a/test/vinyl/constraint.result +++ b/test/vinyl/constraint.result @@ -83,13 +83,11 @@ index = space:create_index('primary', { type = 'tree', parts = {1,'unsigned',2,' ... space:insert{1} --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... space:replace{1} --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... space:delete{1} --- @@ -101,8 +99,7 @@ space:update(1, {{'=', 1, 101}}) ... space:upsert({1}, {{'+', 1, 10}}) --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... space:get{1} --- diff --git a/test/vinyl/errinj.result b/test/vinyl/errinj.result index a081575be..23ab845b3 100644 --- a/test/vinyl/errinj.result +++ b/test/vinyl/errinj.result @@ -1634,8 +1634,7 @@ errinj.set("ERRINJ_VY_READ_PAGE_TIMEOUT", 0.001) ... s:create_index('sk', {parts = {2, 'unsigned'}}) -- must fail --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... errinj.set("ERRINJ_VY_READ_PAGE_TIMEOUT", 0) --- @@ -2087,8 +2086,7 @@ fiber.sleep(0) ... s:format{{'key', 'unsigned'}, {'value', 'unsigned'}} -- must fail --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... s:select() --- @@ -2112,8 +2110,7 @@ fiber.sleep(0) ... s:create_index('sk', {parts = {2, 'unsigned'}}) --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 2) +- error: Tuple field 2 required by space format is missing ... s:select() --- diff --git a/test/vinyl/savepoint.result b/test/vinyl/savepoint.result index d7b57a775..a62f2ea80 100644 --- a/test/vinyl/savepoint.result +++ b/test/vinyl/savepoint.result @@ -124,8 +124,7 @@ index2 = space:create_index('secondary', { parts = {2, 'int', 3, 'str'} }) ... space:insert({1}) --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 3) +- error: Tuple field 2 required by space format is missing ... space:insert({1, 1, 'a'}) --- @@ -623,8 +622,7 @@ space:insert({4, 2, 'b'}) ... space:upsert({2}, {{'=', 4, 1000}}) --- -- error: Tuple field count 1 is less than required by space format or defined indexes - (expected at least 3) +- error: Tuple field 2 required by space format is missing ... index3:delete({3, 'a'}) --- -- 2.19.2 ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [tarantool-patches] Re: [PATCH v1 4/4] box: refactor tuple_init_field_map to use bitmap 2018-12-29 12:58 ` [tarantool-patches] " Kirill Shcherbatov @ 2018-12-29 13:22 ` Vladimir Davydov 2018-12-29 16:25 ` Vladimir Davydov 1 sibling, 0 replies; 18+ messages in thread From: Vladimir Davydov @ 2018-12-29 13:22 UTC (permalink / raw) To: Kirill Shcherbatov; +Cc: tarantool-patches On Sat, Dec 29, 2018 at 03:58:34PM +0300, Kirill Shcherbatov wrote: > > field_count can't be 0 - otherwise we would bail out early. > It is not so, try paste assert here and run > > s = box.schema.space.create('test', {engine = engine}) > pk = s:create_index('pk') > sk = s:create_index('sk', {parts = {{2, 'unsigned', is_nullable = true}}}) > s:replace{} -- Fail OK, I confused tuple field count with format field count. ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [tarantool-patches] Re: [PATCH v1 4/4] box: refactor tuple_init_field_map to use bitmap 2018-12-29 12:58 ` [tarantool-patches] " Kirill Shcherbatov 2018-12-29 13:22 ` Vladimir Davydov @ 2018-12-29 16:25 ` Vladimir Davydov 1 sibling, 0 replies; 18+ messages in thread From: Vladimir Davydov @ 2018-12-29 16:25 UTC (permalink / raw) To: Kirill Shcherbatov; +Cc: tarantool-patches On Sat, Dec 29, 2018 at 03:58:34PM +0300, Kirill Shcherbatov wrote: > Refactored tuple_init_field_map to fill a local bitmap and It's not refactoring, it's a rework. > compare it with template required_fields bitmap containing > information about required fields. Each field is mapped to > bitmap with field:id - unique field identifier. > This approach to check the required fields will work even after > the introduction of JSON paths, when the field tree becomes > multilevel. > > Needed for #1012 > @@ -440,15 +484,30 @@ tuple_init_field_map(struct tuple_format *format, uint32_t *field_map, > (unsigned) format->exact_field_count); > return -1; > } > - if (validate && field_count < format->min_field_count) { > - diag_set(ClientError, ER_MIN_FIELD_COUNT, > - (unsigned) field_count, > - (unsigned) format->min_field_count); > - return -1; > - } > > /* first field is simply accessible, so we do not store offset to it */ > struct tuple_field *field = tuple_format_field(format, 0); > + /* > + * Allocate fields_bitmap - a copy of the initialized > + * format:required_fields bitmap. The field:id bits would > + * be nullified for founded fields during tuple parse to > + * raise an error when some required field is missing. > + */ > + struct region *region = &fiber()->gc; > + char *fields_bitmap = NULL; > + uint32_t fields_bitmap_sz = bitmap_size(format->total_field_count); > + if (validate) { > + fields_bitmap = region_alloc(region, fields_bitmap_sz); > + if (fields_bitmap == NULL) { > + diag_set(OutOfMemory, fields_bitmap_sz, "calloc", s/calloc/region Memory allocated on the region isn't freed when the function returns... > + "required_fields"); > + return -1; > + } > + memcpy(fields_bitmap, format->required_fields, > + fields_bitmap_sz); > + if (field_count > 0) > + bit_clear(fields_bitmap, field->id); > + } > if (validate && > !field_mp_type_is_compatible(field->type, mp_typeof(*pos), > tuple_field_is_nullable(field))) { If field_count is 0, then you'll access uninitialized memory here ^^^ I'm kinda tired of reviewing this simple patch so I fixed these issues by myself, fixed grammar in the comments, and pushed the patch to 2.1. ^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [PATCH v1 0/4] box: JSON preparatory patchset 2018-12-27 11:15 [PATCH v1 0/4] box: JSON preparatory patchset Kirill Shcherbatov ` (3 preceding siblings ...) 2018-12-27 11:15 ` [PATCH v1 4/4] box: refactor tuple_init_field_map to use bitmap Kirill Shcherbatov @ 2018-12-27 19:13 ` Vladimir Davydov 4 siblings, 0 replies; 18+ messages in thread From: Vladimir Davydov @ 2018-12-27 19:13 UTC (permalink / raw) To: Kirill Shcherbatov; +Cc: tarantool-patches, kostja v1? I thought it at least v2 On Thu, Dec 27, 2018 at 02:15:51PM +0300, Kirill Shcherbatov wrote: > Preparatory patch set for JSON indexes: > - Implemented a new json_token_path_snprint routine able to print > JSON path to field by field specified working like cannonical > snprintf routine > - New json_token_is_leaf helper to test node is JSON tree leaf > - Implemented a new bitmap_majority_test routine to check if the > passed bitmap a "majorates" bitmap b (test that a contains at > least all b bits). > - Reworked tuple_init_field_map with required fields bitmap - > a scallable approach able to work with JSON multilevel fields > tree. > > http://github.com/tarantool/tarantool/tree/kshch/gh-3908-fix-ast-alter-memleak Bad link. > https://github.com/tarantool/tarantool/issues/3908 > > Kirill Shcherbatov (4): > lib: introduce json_tree_snprint_path > lib: introduce json_token_is_leaf helper > box: introduce bitmap_majority_test routine > box: refactor tuple_init_field_map to use bitmap > > src/box/errcode.h | 2 +- > src/box/tuple_format.c | 103 ++++++++++++++++++++++++++-- > src/box/tuple_format.h | 18 +++++ > src/lib/bit/bit.h | 45 ++++++++++++ > src/lib/json/json.c | 68 ++++++++++++++++++ > src/lib/json/json.h | 21 ++++++ > test/box/alter_limits.result | 6 +- > test/box/ddl.result | 18 ++--- > test/box/misc.result | 2 +- > test/box/sql.result | 9 +-- > test/box/tree_pk_multipart.result | 6 +- > test/engine/ddl.result | 21 ++---- > test/engine/null.result | 39 ++++------- > test/unit/bit.c | 52 ++++++++++++++ > test/unit/bit.result | 2 + > test/unit/json.c | 110 +++++++++++++++++++++++++++++- > test/unit/json.result | 32 ++++++++- > test/vinyl/constraint.result | 9 +-- > test/vinyl/errinj.result | 9 +-- > test/vinyl/savepoint.result | 6 +- > 20 files changed, 485 insertions(+), 93 deletions(-) ^ permalink raw reply [flat|nested] 18+ messages in thread
end of thread, other threads:[~2018-12-29 16:25 UTC | newest] Thread overview: 18+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2018-12-27 11:15 [PATCH v1 0/4] box: JSON preparatory patchset Kirill Shcherbatov 2018-12-27 11:15 ` [PATCH v1 1/4] lib: introduce json_tree_snprint_path Kirill Shcherbatov 2018-12-27 18:51 ` Vladimir Davydov 2018-12-27 11:15 ` [PATCH v1 2/4] lib: introduce json_token_is_leaf helper Kirill Shcherbatov 2018-12-27 18:52 ` Vladimir Davydov 2018-12-27 11:15 ` [PATCH v1 3/4] box: introduce bitmap_majority_test routine Kirill Shcherbatov 2018-12-27 18:59 ` Vladimir Davydov 2018-12-29 12:58 ` [tarantool-patches] " Kirill Shcherbatov 2018-12-29 13:19 ` Vladimir Davydov 2018-12-29 13:57 ` Kirill Shcherbatov 2018-12-29 16:16 ` Vladimir Davydov 2018-12-27 11:15 ` [PATCH v1 4/4] box: refactor tuple_init_field_map to use bitmap Kirill Shcherbatov 2018-12-27 11:48 ` [tarantool-patches] " Konstantin Osipov 2018-12-27 19:12 ` Vladimir Davydov 2018-12-29 12:58 ` [tarantool-patches] " Kirill Shcherbatov 2018-12-29 13:22 ` Vladimir Davydov 2018-12-29 16:25 ` Vladimir Davydov 2018-12-27 19:13 ` [PATCH v1 0/4] box: JSON preparatory patchset Vladimir Davydov
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox