Tarantool development patches archive
 help / color / mirror / Atom feed
* [tarantool-patches] [PATCH box 1/1] box: create bigrefs for tuples
@ 2018-05-29 12:11 Mergen Imeev
  2018-05-29 16:27 ` [tarantool-patches] " Vladislav Shpilevoy
  0 siblings, 1 reply; 2+ messages in thread
From: Mergen Imeev @ 2018-05-29 12:11 UTC (permalink / raw)
  To: tarantool-patches; +Cc: Mergen Imeev

From: Mergen Imeev <imeevma@gmail.com>

Due to limitation of number of bigrefs being only 65535 it
was possible to reach this limitation. This patch increases
capacity of referance counter to 4 billions.

Closes #3224
---
 src/box/tuple.c          |  18 +++++++
 src/box/tuple.h          | 135 +++++++++++++++++++++++++++++++++++++++++++----
 test/box/select.result   |   5 +-
 test/box/select.test.lua |   2 +-
 4 files changed, 146 insertions(+), 14 deletions(-)

diff --git a/src/box/tuple.c b/src/box/tuple.c
index 014f374..f4e1829 100644
--- a/src/box/tuple.c
+++ b/src/box/tuple.c
@@ -58,6 +58,12 @@ struct tuple *box_tuple_last;
 
 struct tuple_format *tuple_format_runtime;
 
+/**
+ * All bigrefs of tuples
+ * \sa tuple_ref
+ */
+struct tuple_bigrefs bigrefs;
+
 static void
 runtime_tuple_delete(struct tuple_format *format, struct tuple *tuple);
 
@@ -211,6 +217,16 @@ tuple_init(field_name_hash_f hash)
 
 	box_tuple_last = NULL;
 
+	bigrefs.size = 0;
+	bigrefs.capacity = TUPLE_BIGREF_MIN_CAPACITY;
+	bigrefs.refs = (uint32_t *) malloc(bigrefs.capacity * sizeof(uint32_t));
+	if (bigrefs.refs == NULL) {
+		diag_set(OutOfMemory, bigrefs.capacity *
+			sizeof(uint32_t), "malloc", "bigrefs.refs");
+		return -1;
+	}
+
+
 	if (coll_id_cache_init() != 0)
 		return -1;
 
@@ -265,6 +281,8 @@ tuple_free(void)
 	tuple_format_free();
 
 	coll_id_cache_destroy();
+
+	free(bigrefs.refs);
 }
 
 box_tuple_format_t *
diff --git a/src/box/tuple.h b/src/box/tuple.h
index e2384dd..c7dbe3b 100644
--- a/src/box/tuple.h
+++ b/src/box/tuple.h
@@ -327,6 +327,19 @@ struct PACKED tuple
 	 */
 };
 
+/**
+ * @brief Container for bigrefs.
+ */
+struct tuple_bigrefs
+{
+	/** reference counter */
+	uint32_t *refs;
+	/** index of last non-zero element */
+	uint16_t size;
+	/** capacity of container */
+	uint16_t capacity;
+};
+
 /** Size of the tuple including size of struct tuple. */
 static inline size_t
 tuple_size(const struct tuple *tuple)
@@ -774,7 +787,41 @@ tuple_field_uuid(const struct tuple *tuple, int fieldno,
 	return 0;
 }
 
-enum { TUPLE_REF_MAX = UINT16_MAX };
+enum {
+	TUPLE_BIGREFS_FACTOR = 2,
+	TUPLE_BIGREF_MAX = UINT32_MAX,
+	TUPLE_REF_MAX = UINT16_MAX >> 1,
+	TUPLE_REF_FLAG = UINT16_MAX ^ TUPLE_REF_MAX,
+	TUPLE_BIGREF_MIN_CAPACITY = 16
+};
+
+extern struct tuple_bigrefs bigrefs;
+
+/**
+ * Return index for new bigref
+ * @retval Number less than or equal 0x7fff Success.
+ * @retval Number more than 0x7fff Too many refs error.
+ */
+static inline uint16_t
+get_bigref_index(void)
+{
+	for(uint16_t i = 0; i < bigrefs.size; ++i)
+		if(bigrefs.refs[i] == 0)
+			return i;
+	if(bigrefs.size == bigrefs.capacity - 1) {
+		if(bigrefs.capacity > TUPLE_REF_MAX / TUPLE_BIGREFS_FACTOR)
+			return TUPLE_REF_FLAG;
+		bigrefs.capacity *= TUPLE_BIGREFS_FACTOR;
+		bigrefs.refs = (uint32_t *) realloc(bigrefs.refs,
+				bigrefs.capacity * sizeof(uint32_t));
+		if (bigrefs.refs == NULL) {
+			diag_set(OutOfMemory, bigrefs.capacity *
+				sizeof(uint32_t), "realloc", "bigrefs.refs");
+			return TUPLE_REF_FLAG;
+		}
+	}
+	return bigrefs.size++;
+}
 
 /**
  * Increment tuple reference counter.
@@ -785,15 +832,55 @@ enum { TUPLE_REF_MAX = UINT16_MAX };
 static inline int
 tuple_ref(struct tuple *tuple)
 {
-	if (tuple->refs + 1 > TUPLE_REF_MAX) {
-		diag_set(ClientError, ER_TUPLE_REF_OVERFLOW);
-		return -1;
+	if(tuple->refs == TUPLE_REF_MAX) {
+		uint16_t index = get_bigref_index();
+		if(index > TUPLE_REF_MAX) {
+			diag_set(ClientError, ER_TUPLE_REF_OVERFLOW);
+			return -1;
+		}
+		tuple->refs = TUPLE_REF_FLAG | index;
+		bigrefs.refs[index] = TUPLE_REF_MAX;
 	}
-	tuple->refs++;
+	if((tuple->refs & TUPLE_REF_FLAG) > 0) {
+		uint16_t index = tuple->refs ^ TUPLE_REF_FLAG;
+		if (bigrefs.refs[index] > TUPLE_BIGREF_MAX - 1) {
+			diag_set(ClientError, ER_TUPLE_REF_OVERFLOW);
+			return -1;
+		}
+		bigrefs.refs[index]++;
+	} else tuple->refs++;
 	return 0;
 }
 
 /**
+ * Check if capacity of bigrefs can be reduced
+ */
+static inline void
+bigrefs_check_capacity(void)
+{
+	uint16_t tmp_size;
+	uint16_t tmp_capacity = bigrefs.capacity;
+	for(uint16_t i = 0; i < bigrefs.capacity; ++i)
+		if(bigrefs.refs[i] > 0)
+			tmp_size = i;
+	while(tmp_capacity > TUPLE_BIGREF_MIN_CAPACITY &&
+	      tmp_size < tmp_capacity / TUPLE_BIGREFS_FACTOR) {
+		tmp_capacity /= TUPLE_BIGREFS_FACTOR;
+		if(tmp_capacity < TUPLE_BIGREF_MIN_CAPACITY)
+			tmp_capacity = TUPLE_BIGREF_MIN_CAPACITY;
+	}
+	bigrefs.size = tmp_size;
+	if(tmp_capacity < bigrefs.capacity) {
+		bigrefs.capacity = tmp_capacity;
+		bigrefs.refs = (uint32_t *) realloc(bigrefs.refs,
+				bigrefs.capacity * sizeof(uint32_t));
+		if (bigrefs.refs == NULL)
+			diag_set(OutOfMemory, bigrefs.capacity *
+				 sizeof(uint32_t), "malloc", "bigrefs.refs");
+	}
+}
+
+/**
  * Decrement tuple reference counter. If it has reached zero, free the tuple.
  *
  * @pre tuple->refs + count >= 0
@@ -802,8 +889,20 @@ static inline void
 tuple_unref(struct tuple *tuple)
 {
 	assert(tuple->refs - 1 >= 0);
+	uint16_t index = tuple->refs ^ TUPLE_REF_FLAG;
 
-	tuple->refs--;
+	if((tuple->refs & TUPLE_REF_FLAG) > 0) {
+		bigrefs.refs[index]--;
+	} else {
+		tuple->refs--;
+	}
+
+	if((tuple->refs & TUPLE_REF_FLAG) > 0 &&
+	   (bigrefs.refs[index] < TUPLE_REF_MAX)) {
+		tuple->refs = bigrefs.refs[index];
+		bigrefs.refs[index] = 0;
+		bigrefs_check_capacity();
+	}
 
 	if (tuple->refs == 0)
 		tuple_delete(tuple);
@@ -824,11 +923,27 @@ 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;
+
+	if(tuple->refs == TUPLE_REF_MAX) {
+		uint16_t index = get_bigref_index();
+		if(index > TUPLE_REF_MAX) {
+			diag_set(ClientError, ER_TUPLE_REF_OVERFLOW);
+			return NULL;
+		}
+		tuple->refs = TUPLE_REF_FLAG | index;
+		bigrefs.refs[index] = TUPLE_REF_MAX;
+	}
+	if((tuple->refs & TUPLE_REF_FLAG) > 0) {
+		uint16_t index = tuple->refs ^ TUPLE_REF_FLAG;
+		if (bigrefs.refs[index] > TUPLE_BIGREF_MAX - 2) {
+			diag_set(ClientError, ER_TUPLE_REF_OVERFLOW);
+			return NULL;
+		}
+		bigrefs.refs[index]++;
+	} else {
+		tuple->refs++;
 	}
-	tuple->refs++;
+
 	/* Remove previous tuple */
 	if (likely(box_tuple_last != NULL))
 		tuple_unref(box_tuple_last); /* do not throw */
diff --git a/test/box/select.result b/test/box/select.result
index 4aed706..d2beb9e 100644
--- a/test/box/select.result
+++ b/test/box/select.result
@@ -634,13 +634,12 @@ lots_of_links = {}
 ref_count = 0
 ---
 ...
-while (true) do table.insert(lots_of_links, s:get{0}) ref_count = ref_count + 1 end
+while (ref_count < 100000) do table.insert(lots_of_links, s:get{0}) ref_count = ref_count + 1 end
 ---
-- error: Tuple reference counter overflow
 ...
 ref_count
 ---
-- 65531
+- 100000
 ...
 lots_of_links = {}
 ---
diff --git a/test/box/select.test.lua b/test/box/select.test.lua
index 54c2ecc..5e3071d 100644
--- a/test/box/select.test.lua
+++ b/test/box/select.test.lua
@@ -129,7 +129,7 @@ index = s:create_index('primary', { type = 'tree' })
 a = s:insert{0}
 lots_of_links = {}
 ref_count = 0
-while (true) do table.insert(lots_of_links, s:get{0}) ref_count = ref_count + 1 end
+while (ref_count < 100000) do table.insert(lots_of_links, s:get{0}) ref_count = ref_count + 1 end
 ref_count
 lots_of_links = {}
 s:drop()
-- 
2.7.4

^ permalink raw reply	[flat|nested] 2+ messages in thread

* [tarantool-patches] Re: [PATCH box 1/1] box: create bigrefs for tuples
  2018-05-29 12:11 [tarantool-patches] [PATCH box 1/1] box: create bigrefs for tuples Mergen Imeev
@ 2018-05-29 16:27 ` Vladislav Shpilevoy
  0 siblings, 0 replies; 2+ messages in thread
From: Vladislav Shpilevoy @ 2018-05-29 16:27 UTC (permalink / raw)
  To: tarantool-patches, Mergen Imeev; +Cc: Mergen Imeev

Hello. Thanks for the patch! See my 14 comments below.

On 29/05/2018 15:11, Mergen Imeev wrote:
> From: Mergen Imeev <imeevma@gmail.com>

1. Why do I see the SMTP 'From:' in the message body?

> 
> Due to limitation of number of bigrefs being only 65535 it
> was possible to reach this limitation. This patch increases
> capacity of referance counter to 4 billions.

2. reference

> 
> Closes #3224
> ---

3. Please, specify branch and issue web links. And you have to prefix
a branch name with your gh login.

>   src/box/tuple.c          |  18 +++++++
>   src/box/tuple.h          | 135 +++++++++++++++++++++++++++++++++++++++++++----
>   test/box/select.result   |   5 +-
>   test/box/select.test.lua |   2 +-
>   4 files changed, 146 insertions(+), 14 deletions(-)
> 
> diff --git a/src/box/tuple.c b/src/box/tuple.c
> index 014f374..f4e1829 100644
> --- a/src/box/tuple.c
> +++ b/src/box/tuple.c
> @@ -58,6 +58,12 @@ struct tuple *box_tuple_last;
>   
>   struct tuple_format *tuple_format_runtime;
>   
> +/**
> + * All bigrefs of tuples

4. Please, finish a sentence with dot. And describe here shortly
why bigrefs are needed, what the limits are, and how it works.

> + * \sa tuple_ref
> + */
> +struct tuple_bigrefs bigrefs;
> +
>   static void
>   runtime_tuple_delete(struct tuple_format *format, struct tuple *tuple);
>   
> @@ -211,6 +217,16 @@ tuple_init(field_name_hash_f hash)
>   
>   	box_tuple_last = NULL;
>   
> +	bigrefs.size = 0;
> +	bigrefs.capacity = TUPLE_BIGREF_MIN_CAPACITY;
> +	bigrefs.refs = (uint32_t *) malloc(bigrefs.capacity * sizeof(uint32_t));

5. Please, try to do not allocate anything until it is really needed. In the
most cases bigrefs will be unused.

> +	if (bigrefs.refs == NULL) {
> +		diag_set(OutOfMemory, bigrefs.capacity *
> +			sizeof(uint32_t), "malloc", "bigrefs.refs");
> +		return -1;
> +	}
> +
> +
>   	if (coll_id_cache_init() != 0)
>   		return -1;
>   
> @@ -265,6 +281,8 @@ tuple_free(void)
>   	tuple_format_free();
>   
>   	coll_id_cache_destroy();
> +
> +	free(bigrefs.refs);
>   }
>   
>   box_tuple_format_t *
> diff --git a/src/box/tuple.h b/src/box/tuple.h
> index e2384dd..c7dbe3b 100644
> --- a/src/box/tuple.h
> +++ b/src/box/tuple.h
> @@ -327,6 +327,19 @@ struct PACKED tuple
>   	 */
>   };
>   
> +/**
> + * @brief Container for bigrefs.

6. Bigref is an internal structure, and it must be declared in tuple.c only.
So you will have two versions of tuple_ref - static inline tuple_ref in the
header and tuple_ref_slow declared in tuple.h, but implemented in tuple.c.

Static inline tuple_ref calls tuple_ref_slow when sees ref counter is
overflowed already. As examples see region_reserve and region_reserve_slow.

Same about tuple_unref.

> + */
> +struct tuple_bigrefs
> +{
> +	/** reference counter */
> +	uint32_t *refs;
> +	/** index of last non-zero element */
> +	uint16_t size;
> +	/** capacity of container */
> +	uint16_t capacity;
> +};
> +
>   /** Size of the tuple including size of struct tuple. */
>   static inline size_t
>   tuple_size(const struct tuple *tuple)
> @@ -774,7 +787,41 @@ tuple_field_uuid(const struct tuple *tuple, int fieldno,
>   	return 0;
>   }
>   
> -enum { TUPLE_REF_MAX = UINT16_MAX };
> +enum {
> +	TUPLE_BIGREFS_FACTOR = 2,
> +	TUPLE_BIGREF_MAX = UINT32_MAX,
> +	TUPLE_REF_MAX = UINT16_MAX >> 1,
> +	TUPLE_REF_FLAG = UINT16_MAX ^ TUPLE_REF_MAX,
> +	TUPLE_BIGREF_MIN_CAPACITY = 16
> +};
> +
> +extern struct tuple_bigrefs bigrefs;
> +
> +/**
> + * Return index for new bigref
> + * @retval Number less than or equal 0x7fff Success.
> + * @retval Number more than 0x7fff Too many refs error.
> + */
> +static inline uint16_t
> +get_bigref_index(void)

7. This function is actually a method of tuple_bigref structure,
and it not only gets - it may extend refs array, so lets better
call it tuple_bigref_retrieve().

> +{
> +	for(uint16_t i = 0; i < bigrefs.size; ++i)
> +		if(bigrefs.refs[i] == 0)
> +			return i;

8. This cycle is useless when you know all the refs are occupied.
As far as I understand size is a count of occupied bigrefs. Size
is incremented on each new bigref and decremented on each removed
one. And here you at first should check if size < capacity. If it
is, you are sure to find a free bigref in the cycle. Else it
makes no sense to search a free ref.

tuple_bigref_new() {
	if (size < capacity) {
		for (uint16_t i = 0; i < capacity; ++i) {
			if (refs[i] == 0) {
				++size;
				return i;
			}
		}
		unreachable();
	}
	/* Extend the array ... */
}

9. When a 'for' consists of multiple lines, please, put it in
brackets.

> +	if(bigrefs.size == bigrefs.capacity - 1) {
> +		if(bigrefs.capacity > TUPLE_REF_MAX / TUPLE_BIGREFS_FACTOR)
> +			return TUPLE_REF_FLAG;

10. What is TUPLE_REF_FLAG in the get_bigref_index? If it means error,
lets better change the function signature:

/**
  * Get or allocate a new free bigref counter.
  * @param[out] new_ref New reference counter index.
  * @retval 0 Success.
  * @retval -1 Error.
  */
int
tuple_bigref_retrieve(uint16_t *new_ref);

> +		bigrefs.capacity *= TUPLE_BIGREFS_FACTOR;
> +		bigrefs.refs = (uint32_t *) realloc(bigrefs.refs,
> +				bigrefs.capacity * sizeof(uint32_t));

11. If realloc has returned NULL, the original refs would leak.

> +		if (bigrefs.refs == NULL) {
> +			diag_set(OutOfMemory, bigrefs.capacity *
> +				sizeof(uint32_t), "realloc", "bigrefs.refs");
> +			return TUPLE_REF_FLAG;
> +		}
> +	}
> +	return bigrefs.size++;
> +}
>   
>   /**
>    * Increment tuple reference counter.
> @@ -785,15 +832,55 @@ enum { TUPLE_REF_MAX = UINT16_MAX };
>   static inline int
>   tuple_ref(struct tuple *tuple)
>   {
> -	if (tuple->refs + 1 > TUPLE_REF_MAX) {
> -		diag_set(ClientError, ER_TUPLE_REF_OVERFLOW);
> -		return -1;
> +	if(tuple->refs == TUPLE_REF_MAX) {
> +		uint16_t index = get_bigref_index();
> +		if(index > TUPLE_REF_MAX) {
> +			diag_set(ClientError, ER_TUPLE_REF_OVERFLOW);
> +			return -1;
> +		}
> +		tuple->refs = TUPLE_REF_FLAG | index;
> +		bigrefs.refs[index] = TUPLE_REF_MAX;
>   	}
> -	tuple->refs++;
> +	if((tuple->refs & TUPLE_REF_FLAG) > 0) {
> +		uint16_t index = tuple->refs ^ TUPLE_REF_FLAG;
> +		if (bigrefs.refs[index] > TUPLE_BIGREF_MAX - 1) {
> +			diag_set(ClientError, ER_TUPLE_REF_OVERFLOW);

12. I remember Kostja has asked to replace this error with panic(). But I
do not like panic(). Lets ask in the product team chat what to do. In theory
this error is unreachable now but who knows for sure?

> +			return -1;
> +		}
> +		bigrefs.refs[index]++;
> +	} else tuple->refs++;

13. When 'if' body is in {}, the 'else' body must be too.

>   	return 0;
>   }
>   
> diff --git a/test/box/select.test.lua b/test/box/select.test.lua
> index 54c2ecc..5e3071d 100644
> --- a/test/box/select.test.lua
> +++ b/test/box/select.test.lua
> @@ -129,7 +129,7 @@ index = s:create_index('primary', { type = 'tree' })
>   a = s:insert{0}
>   lots_of_links = {}
>   ref_count = 0
> -while (true) do table.insert(lots_of_links, s:get{0}) ref_count = ref_count + 1 end
> +while (ref_count < 100000) do table.insert(lots_of_links, s:get{0}) ref_count = ref_count + 1 end

14. Please, write before the test a comment like
--
-- gh-####: issue description, test description.
--

^ permalink raw reply	[flat|nested] 2+ messages in thread

end of thread, other threads:[~2018-05-29 16:27 UTC | newest]

Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-05-29 12:11 [tarantool-patches] [PATCH box 1/1] box: create bigrefs for tuples Mergen Imeev
2018-05-29 16:27 ` [tarantool-patches] " Vladislav Shpilevoy

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox