From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Subject: Re: [tarantool-patches] Re: [PATCH v1 4/4] box: refactor tuple_init_field_map to use bitmap References: <20181227191249.vojcr2jl3ugnm5pw@esperanza> From: Kirill Shcherbatov Message-ID: Date: Sat, 29 Dec 2018 15:58:34 +0300 MIME-Version: 1.0 In-Reply-To: <20181227191249.vojcr2jl3ugnm5pw@esperanza> Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 7bit To: tarantool-patches@freelists.org, Vladimir Davydov List-ID: 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