[tarantool-patches] Re: [PATCH v2 1/1] box: create bigrefs for tuples

[Vladislav Shpilevoy]

Hello. Thanks for the patch! It is almost perfect! See 6 comments
below.

On 01/06/2018 18:41, imeevma at tarantool.org wrote:
> Due to limitation of reference counters for tuple being only
> 65535 it was possible to reach this limitation. This patch
> increases capacity of reference counters to 4 billions.
> 
> Closes #3224
> ---
> Branch: https://github.com/tarantool/tarantool/tree/imeevma/gh-3224-tuple-bigrefs
> Issue: https://github.com/tarantool/tarantool/issues/3224
> 
>   src/box/errcode.h        |   2 +-
>   src/box/lua/tuple.c      |   5 +-
>   src/box/port.c           |   8 +--
>   src/box/tuple.c          | 164 +++++++++++++++++++++++++++++++++++++++++++++--
>   src/box/tuple.h          |  63 ++++++++++--------
>   test/box/misc.result     |  39 ++++++-----
>   test/box/select.result   |  30 +++++++--
>   test/box/select.test.lua |  15 ++++-
>   8 files changed, 257 insertions(+), 69 deletions(-)
> 
> diff --git a/src/box/tuple.c b/src/box/tuple.c
> index 014f374..f59b27e 100644
> --- a/src/box/tuple.c
> +++ b/src/box/tuple.c> +
> +/**
> + * Try to decrease allocated memory if it is possible. Free memory when
> + * size == 0.
> + */
> +static inline void
> +tuple_bigrefs_compact(void)
> +{
> +	if (bigrefs.size == 0) {
> +		tuple_bigrefs_destroy();
> +		return;
> +	}
> +	if (bigrefs.capacity == TUPLE_BIGREF_MIN_CAPACITY ||
> +	    bigrefs.size > bigrefs.capacity / TUPLE_BIGREF_FACTOR)
> +		return;
> +	uint16_t size = bigrefs.size;
> +	uint16_t reserved = 0;
> +	uint16_t capacity = bigrefs.capacity;
> +	while(size > 0 && reserved <= capacity / TUPLE_BIGREF_FACTOR) {
> +		if (bigrefs.refs[reserved] != 0)
> +			--size;
> +		reserved++;
> +	}

1. Why do you iterate from the beginning? As far as I remember, we have
decided to iterate from the end. Here you try to find such the biggest
index, that refs[index] != 0. So when you iterate from the beginning, you
always need to go through capacity, but when you iterate from the end,
it is enough to stop on the first non-zero element.

And here you use reserved both as a count and as an index. It is incorrect:
count is 1-based value, index is 0 based.

> +	if (reserved < TUPLE_BIGREF_MIN_CAPACITY)
> +		reserved = TUPLE_BIGREF_MIN_CAPACITY;
> +	if (reserved > capacity / TUPLE_BIGREF_FACTOR)
> +		return;
> +	while(reserved <= capacity / TUPLE_BIGREF_FACTOR)
> +		capacity /= TUPLE_BIGREF_MIN_CAPACITY;

2. I see that capacity is always a power of 2. And you can calculate
the capacity as a next power of 2 starting from 'reserved'. See this
algorithm: http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2Float,
paragraph "Round up to the next highest power of 2". It has O(1) as I can see
versus O(N) with N - bit count in your algorithm.

> +	uint32_t *refs = (uint32_t *) realloc(bigrefs.refs, capacity *
> +					      sizeof(*bigrefs.refs));
> +	if (refs == NULL)
> +		panic("failed to reallocate %zu bytes: Cannot allocate"\
> +		      " memory.", capacity * sizeof(*bigrefs.refs));
> +	bigrefs.refs = refs;
> +	bigrefs.capacity = capacity;
> +}
> +
> diff --git a/src/box/tuple.h b/src/box/tuple.h
> index e2384dd..6921124 100644
> --- a/src/box/tuple.h
> +++ b/src/box/tuple.h
> @@ -307,8 +306,16 @@ box_tuple_upsert(const box_tuple_t *tuple, const char *expr, const
>    */
>   struct PACKED tuple
>   {
> -	/** reference counter */
> -	uint16_t refs;
> +	union {
> +		/** reference counter */
> +		uint16_t refs;
> +		struct {
> +			/** index of big reference counter */
> +			uint16_t ref_index : 15;
> +			/** big reference flag */
> +			bool is_bigref : 1;

3. Please. Start a sentence with a capital letter, and finish with
dot. I see comments in other struct tuple fields, but they are incorrect too.
Lets fix them alongside.

> +		};
> +	};
>   	/** format identifier */
>   	uint16_t format_id;
>   	/**
> @@ -774,26 +781,36 @@ tuple_field_uuid(const struct tuple *tuple, int fieldno,
>   	return 0;
>   }
>   
> -enum { TUPLE_REF_MAX = UINT16_MAX };
> +enum { TUPLE_REF_MAX = UINT16_MAX >> 1 };
> +
> +/**
> + * Increase tuple big reference counter.
> + * @param tuple Tuple to reference.
> + */
> +void
> +tuple_ref_slow(struct tuple *tuple);
>   
>   /**
>    * Increment tuple reference counter.
>    * @param tuple Tuple to reference.
> - * @retval  0 Success.
> - * @retval -1 Too many refs error.
>    */
> -static inline int
> +static inline void
>   tuple_ref(struct tuple *tuple)
>   {
> -	if (tuple->refs + 1 > TUPLE_REF_MAX) {
> -		diag_set(ClientError, ER_TUPLE_REF_OVERFLOW);
> -		return -1;
> -	}
> -	tuple->refs++;
> -	return 0;
> +	if (tuple->is_bigref || tuple->refs == TUPLE_REF_MAX)

4. Is it the same as 'tuple->refs >= TUPLE_REF_MAX'? I would prefer
that because single check is better than two. Tuple_ref is very hot
path and must be very optimized. Maybe we should even wrap this
condition with unlikely() macro.

if (unlikely(tuple->refs >= TUPLE_REF_MAX))
	ref_slow
else
	ref_fast

> +		tuple_ref_slow(tuple);
> +	else
> +		tuple->refs++;
>   }
>   
>   /**
> + * Decrease tuple big reference counter.
> + * @param tuple Tuple to reference.
> + */
> +void
> +tuple_unref_slow(struct tuple *tuple);
> +
> +/**
>    * Decrement tuple reference counter. If it has reached zero, free the tuple.
>    *
>    * @pre tuple->refs + count >= 0
> @@ -802,6 +819,10 @@ static inline void
>   tuple_unref(struct tuple *tuple)
>   {
>   	assert(tuple->refs - 1 >= 0);
> +	if (tuple->is_bigref) {

5. Same. Lets do if (unlikely(tuple->is_bigref)) { unref_slow ... }

> +		tuple_unref_slow(tuple);
> +		return;
> +	}
>   
>   	tuple->refs--;
>   
> @@ -813,22 +834,15 @@ extern struct tuple *box_tuple_last;
>   
>   /**
>    * Convert internal `struct tuple` to public `box_tuple_t`.
> - * \retval tuple on success
> - * \retval NULL on error, check diag
> + * \retval tuple
>    * \post \a tuple ref counted until the next call.
> - * \post tuple_ref() doesn't fail at least once
>    * \sa tuple_ref
>    */
>   static inline box_tuple_t *
>   tuple_bless(struct tuple *tuple)
>   {
>   	assert(tuple != NULL);
> -	/* Ensure tuple can be referenced at least once after return */
> -	if (tuple->refs + 2 > TUPLE_REF_MAX) {
> -		diag_set(ClientError, ER_TUPLE_REF_OVERFLOW);
> -		return NULL;
> -	}
> -	tuple->refs++;
> +	tuple_ref(tuple);
>   	/* Remove previous tuple */
>   	if (likely(box_tuple_last != NULL))
>   		tuple_unref(box_tuple_last); /* do not throw */
> @@ -856,8 +870,7 @@ tuple_to_buf(const struct tuple *tuple, char *buf, size_t size);
>   static inline void
>   tuple_ref_xc(struct tuple *tuple)

6. Lets remove tuple_ref_xc now. 'XC' here means 'eXCeption on an error'. No an error
is impossible, so tuple_ref_xc === tuple_ref.

>   {
> -	if (tuple_ref(tuple))
> -		diag_raise();
> +	tuple_ref(tuple);
>   }
>