Re: [PATCH v1 4/4] box: refactor tuple_init_field_map to use bitmap

[Vladimir Davydov <vdavydov.dev@gmail.com>]

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;
>  }