From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: From: Kirill Shcherbatov Subject: [PATCH v1 4/4] box: refactor tuple_init_field_map to use bitmap Date: Thu, 27 Dec 2018 14:15:55 +0300 Message-Id: In-Reply-To: References: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit To: tarantool-patches@freelists.org, vdavydov.dev@gmail.com Cc: kostja@tarantool.org, Kirill Shcherbatov List-ID: 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