[PATCH v1 4/4] box: refactor tuple_init_field_map to use bitmap
Vladimir Davydov
vdavydov.dev at gmail.com
Thu Dec 27 22:12:49 MSK 2018
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;
> }
More information about the Tarantool-patches
mailing list