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

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

[imeevma]

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/errcode.h b/src/box/errcode.h
index a0759f8..e009524 100644
--- a/src/box/errcode.h
+++ b/src/box/errcode.h
@@ -138,7 +138,7 @@ struct errcode_record {
 	/* 83 */_(ER_ROLE_EXISTS,		"Role '%s' already exists") \
 	/* 84 */_(ER_CREATE_ROLE,		"Failed to create role '%s': %s") \
 	/* 85 */_(ER_INDEX_EXISTS,		"Index '%s' already exists") \
-	/* 86 */_(ER_TUPLE_REF_OVERFLOW,	"Tuple reference counter overflow") \
+	/* 86 */_(ER_UNUSED6,			"") \
 	/* 87 */_(ER_ROLE_LOOP,			"Granting role '%s' to role '%s' would create a loop") \
 	/* 88 */_(ER_GRANT,			"Incorrect grant arguments: %s") \
 	/* 89 */_(ER_PRIV_GRANTED,		"User '%s' already has %s access on %s '%s'") \
diff --git a/src/box/lua/tuple.c b/src/box/lua/tuple.c
index 8057331..22fe696 100644
--- a/src/box/lua/tuple.c
+++ b/src/box/lua/tuple.c
@@ -496,10 +496,7 @@ luaT_pushtuple(struct lua_State *L, box_tuple_t *tuple)
 		luaL_pushcdata(L, CTID_CONST_STRUCT_TUPLE_REF);
 	*ptr = tuple;
 	/* The order is important - first reference tuple, next set gc */
-	if (box_tuple_ref(tuple) != 0) {
-		luaT_error(L);
-		return;
-	}
+	box_tuple_ref(tuple);
 	lua_pushcfunction(L, lbox_tuple_gc);
 	luaL_setcdatagc(L, -2);
 }
diff --git a/src/box/port.c b/src/box/port.c
index 03f6be7..9b6b858 100644
--- a/src/box/port.c
+++ b/src/box/port.c
@@ -45,8 +45,7 @@ port_tuple_add(struct port *base, struct tuple *tuple)
 	struct port_tuple *port = port_tuple(base);
 	struct port_tuple_entry *e;
 	if (port->size == 0) {
-		if (tuple_ref(tuple) != 0)
-			return -1;
+		tuple_ref(tuple);
 		e = &port->first_entry;
 		port->first = port->last = e;
 	} else {
@@ -55,10 +54,7 @@ port_tuple_add(struct port *base, struct tuple *tuple)
 			diag_set(OutOfMemory, sizeof(*e), "mempool_alloc", "e");
 			return -1;
 		}
-		if (tuple_ref(tuple) != 0) {
-			mempool_free(&port_tuple_entry_pool, e);
-			return -1;
-		}
+		tuple_ref(tuple);
 		port->last->next = e;
 		port->last = e;
 	}
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
@@ -48,6 +48,25 @@ enum {
 	OBJSIZE_MIN = 16,
 };
 
+/**
+ * Container for big reference counters. Contains array of big reference
+ * counters, size of this array and number of non-zero big reference counters.
+ * When reference counter of tuple becomes more than 32767, field refs of this
+ * tuple becomes index of big reference counter in big reference counter array
+ * and field is_bigref is set true. The moment big reference becomes equal
+ * 32767 it is set to 0, refs of the tuple becomes 32767 and is_bigref becomes
+ * false. Big reference counter can be equal to 0 or be more than 32767.
+ */
+struct tuple_bigrefs
+{
+	/** Array of big reference counters */
+	uint32_t *refs;
+	/** Number of non-zero elements in the array */
+	uint16_t size;
+	/** Capacity of the array */
+	uint16_t capacity;
+};
+
 static const double ALLOC_FACTOR = 1.05;
 
 /**
@@ -58,6 +77,12 @@ struct tuple *box_tuple_last;
 
 struct tuple_format *tuple_format_runtime;
 
+/**
+* All bigrefs of tuples.
+* \sa tuple_ref_slow()
+*/
+static struct tuple_bigrefs bigrefs;
+
 static void
 runtime_tuple_delete(struct tuple_format *format, struct tuple *tuple);
 
@@ -152,6 +177,17 @@ tuple_validate_raw(struct tuple_format *format, const char *tuple)
 }
 
 /**
+ * Initialize big references container.
+ */
+static inline void
+tuple_bigrefs_create(void)
+{
+	bigrefs.size = 0;
+	bigrefs.refs = NULL;
+	bigrefs.capacity = 0;
+}
+
+/**
  * Incremented on every snapshot and is used to distinguish tuples
  * which were created after start of a snapshot (these tuples can
  * be freed right away, since they are not used for snapshot) or
@@ -211,6 +247,8 @@ tuple_init(field_name_hash_f hash)
 
 	box_tuple_last = NULL;
 
+	tuple_bigrefs_create();
+
 	if (coll_id_cache_init() != 0)
 		return -1;
 
@@ -244,6 +282,122 @@ tuple_arena_create(struct slab_arena *arena, struct quota *quota,
 	}
 }
 
+enum {
+	TUPLE_BIGREF_FACTOR = 2,
+	TUPLE_BIGREF_MAX = UINT32_MAX,
+	TUPLE_BIGREF_MIN_CAPACITY = 16,
+	TUPLE_BIGREF_MAX_CAPACITY = UINT16_MAX >> 1
+};
+
+/**
+ * Destroy big references and free memory that was allocated.
+ */
+static inline void
+tuple_bigrefs_destroy(void)
+{
+	free(bigrefs.refs);
+	bigrefs.size = 0;
+	bigrefs.refs = NULL;
+	bigrefs.capacity = 0;
+}
+
+/**
+ * Return index for new big reference counter and allocate memory if needed.
+ * @retval index for new big reference counter.
+ */
+static inline uint16_t
+tuple_bigref_retrieve(void)
+{
+	if (bigrefs.size < bigrefs.capacity) {
+		uint16_t vacant_index = 0;
+		while(bigrefs.refs[vacant_index] != 0)
+			++vacant_index;
+		return vacant_index;
+	}
+	/* Extend the array ... */
+	uint16_t capacity = bigrefs.capacity;
+	if (capacity == 0)
+		capacity = TUPLE_BIGREF_MIN_CAPACITY;
+	else
+		capacity *= TUPLE_BIGREF_FACTOR;
+	if (capacity >= TUPLE_BIGREF_MAX_CAPACITY)
+		panic("Too many big references");
+	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;
+	return bigrefs.size++;
+}
+
+void
+tuple_ref_slow(struct tuple *tuple)
+{
+	assert(tuple->is_bigref == true || tuple->refs == TUPLE_REF_MAX);
+	if (tuple->is_bigref == false) {
+		tuple->ref_index = tuple_bigref_retrieve();
+		tuple->is_bigref = true;
+		bigrefs.refs[tuple->ref_index] = TUPLE_REF_MAX;
+	}
+	if (bigrefs.refs[tuple->ref_index] == TUPLE_BIGREF_MAX)
+		panic("Tuple big reference counter overflow");
+	bigrefs.refs[tuple->ref_index]++;
+}
+
+/**
+ * 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++;
+	}
+	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;
+	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;
+}
+
+void
+tuple_unref_slow(struct tuple *tuple)
+{
+	assert(tuple->is_bigref == true &&
+	       bigrefs.refs[tuple->ref_index] > TUPLE_REF_MAX);
+	bigrefs.refs[tuple->ref_index]--;
+	if(bigrefs.refs[tuple->ref_index] == TUPLE_REF_MAX) {
+		bigrefs.refs[tuple->ref_index] = 0;
+		bigrefs.size--;
+		tuple->ref_index = TUPLE_REF_MAX;
+		tuple->is_bigref = false;
+		tuple_bigrefs_compact();
+	}
+}
+
 void
 tuple_arena_destroy(struct slab_arena *arena)
 {
@@ -265,6 +419,8 @@ tuple_free(void)
 	tuple_format_free();
 
 	coll_id_cache_destroy();
+
+	tuple_bigrefs_destroy();
 }
 
 box_tuple_format_t *
@@ -288,7 +444,8 @@ int
 box_tuple_ref(box_tuple_t *tuple)
 {
 	assert(tuple != NULL);
-	return tuple_ref(tuple);
+	tuple_ref(tuple);
+	return 0;
 }
 
 void
@@ -357,10 +514,7 @@ box_tuple_iterator(box_tuple_t *tuple)
 			 "mempool", "new slab");
 		return NULL;
 	}
-	if (tuple_ref(tuple) != 0) {
-		mempool_free(&tuple_iterator_pool, it);
-		return NULL;
-	}
+	tuple_ref(tuple);
 	tuple_rewind(it, tuple);
 	return it;
 }
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
@@ -105,8 +105,7 @@ typedef struct tuple box_tuple_t;
  * tuple will leak.
  *
  * \param tuple a tuple
- * \retval -1 on error (check box_error_last())
- * \retval 0 on success
+ * \retval 0 always
  * \sa box_tuple_unref()
  */
 int
@@ -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;
+		};
+	};
 	/** 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)
+		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) {
+		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)
 {
-	if (tuple_ref(tuple))
-		diag_raise();
+	tuple_ref(tuple);
 }
 
 /**
diff --git a/test/box/misc.result b/test/box/misc.result
index 8f94f55..f7703ba 100644
--- a/test/box/misc.result
+++ b/test/box/misc.result
@@ -332,7 +332,6 @@ t;
   - 'box.error.UNKNOWN_UPDATE_OP : 28'
   - 'box.error.WRONG_COLLATION_OPTIONS : 151'
   - 'box.error.CURSOR_NO_TRANSACTION : 80'
-  - 'box.error.TUPLE_REF_OVERFLOW : 86'
   - 'box.error.ALTER_SEQUENCE : 143'
   - 'box.error.INVALID_XLOG_NAME : 75'
   - 'box.error.SAVEPOINT_EMPTY_TX : 60'
@@ -360,7 +359,7 @@ t;
   - 'box.error.VINYL_MAX_TUPLE_SIZE : 139'
   - 'box.error.LOAD_FUNCTION : 99'
   - 'box.error.INVALID_XLOG : 74'
-  - 'box.error.PRIV_NOT_GRANTED : 91'
+  - 'box.error.READ_VIEW_ABORTED : 130'
   - 'box.error.TRANSACTION_CONFLICT : 97'
   - 'box.error.GUEST_USER_PASSWORD : 96'
   - 'box.error.PROC_C : 102'
@@ -405,7 +404,7 @@ t;
   - 'box.error.injection : table: <address>
   - 'box.error.NULLABLE_MISMATCH : 153'
   - 'box.error.LAST_DROP : 15'
-  - 'box.error.NO_SUCH_ROLE : 82'
+  - 'box.error.TUPLE_FORMAT_LIMIT : 16'
   - 'box.error.DECOMPRESSION : 124'
   - 'box.error.CREATE_SEQUENCE : 142'
   - 'box.error.CREATE_USER : 43'
@@ -414,66 +413,66 @@ t;
   - 'box.error.SEQUENCE_OVERFLOW : 147'
   - 'box.error.SYSTEM : 115'
   - 'box.error.KEY_PART_IS_TOO_LONG : 118'
-  - 'box.error.TUPLE_FORMAT_LIMIT : 16'
-  - 'box.error.BEFORE_REPLACE_RET : 53'
+  - 'box.error.INJECTION : 8'
+  - 'box.error.INVALID_MSGPACK : 20'
   - 'box.error.NO_SUCH_SAVEPOINT : 61'
   - 'box.error.TRUNCATE_SYSTEM_SPACE : 137'
   - 'box.error.VY_QUOTA_TIMEOUT : 135'
   - 'box.error.WRONG_INDEX_OPTIONS : 108'
   - 'box.error.INVALID_VYLOG_FILE : 133'
   - 'box.error.INDEX_FIELD_COUNT_LIMIT : 127'
-  - 'box.error.READ_VIEW_ABORTED : 130'
+  - 'box.error.PRIV_NOT_GRANTED : 91'
   - 'box.error.USER_MAX : 56'
-  - 'box.error.PROTOCOL : 104'
+  - 'box.error.BEFORE_REPLACE_RET : 53'
   - 'box.error.TUPLE_NOT_ARRAY : 22'
   - 'box.error.KEY_PART_COUNT : 31'
   - 'box.error.ALTER_SPACE : 12'
   - 'box.error.ACTIVE_TRANSACTION : 79'
   - 'box.error.EXACT_FIELD_COUNT : 38'
   - 'box.error.DROP_SEQUENCE : 144'
-  - 'box.error.INVALID_MSGPACK : 20'
   - 'box.error.MORE_THAN_ONE_TUPLE : 41'
-  - 'box.error.RTREE_RECT : 101'
-  - 'box.error.SUB_STMT_MAX : 121'
+  - 'box.error.UPSERT_UNIQUE_SECONDARY_KEY : 105'
   - 'box.error.UNKNOWN_REQUEST_TYPE : 48'
-  - 'box.error.SPACE_EXISTS : 10'
+  - 'box.error.SUB_STMT_MAX : 121'
   - 'box.error.PROC_LUA : 32'
+  - 'box.error.SPACE_EXISTS : 10'
   - 'box.error.ROLE_NOT_GRANTED : 92'
+  - 'box.error.UNSUPPORTED : 5'
   - 'box.error.NO_SUCH_SPACE : 36'
   - 'box.error.WRONG_INDEX_PARTS : 107'
-  - 'box.error.DROP_SPACE : 11'
   - 'box.error.MIN_FIELD_COUNT : 39'
   - 'box.error.REPLICASET_UUID_MISMATCH : 63'
   - 'box.error.UPDATE_FIELD : 29'
+  - 'box.error.INDEX_EXISTS : 85'
   - 'box.error.COMPRESSION : 119'
   - 'box.error.INVALID_ORDER : 68'
-  - 'box.error.INDEX_EXISTS : 85'
   - 'box.error.SPLICE : 25'
   - 'box.error.UNKNOWN : 0'
+  - 'box.error.IDENTIFIER : 70'
   - 'box.error.DROP_PRIMARY_KEY : 17'
   - 'box.error.NULLABLE_PRIMARY : 152'
   - 'box.error.NO_SUCH_SEQUENCE : 145'
   - 'box.error.RELOAD_CFG : 58'
   - 'box.error.INVALID_UUID : 64'
-  - 'box.error.INJECTION : 8'
+  - 'box.error.DROP_SPACE : 11'
   - 'box.error.TIMEOUT : 78'
-  - 'box.error.IDENTIFIER : 70'
   - 'box.error.ITERATOR_TYPE : 72'
   - 'box.error.REPLICA_MAX : 73'
+  - 'box.error.NO_SUCH_ROLE : 82'
   - 'box.error.MISSING_REQUEST_FIELD : 69'
   - 'box.error.MISSING_SNAPSHOT : 93'
   - 'box.error.WRONG_SPACE_OPTIONS : 111'
   - 'box.error.READONLY : 7'
-  - 'box.error.UNSUPPORTED : 5'
   - 'box.error.UPDATE_INTEGER_OVERFLOW : 95'
+  - 'box.error.RTREE_RECT : 101'
   - 'box.error.NO_CONNECTION : 77'
   - 'box.error.INVALID_XLOG_ORDER : 76'
-  - 'box.error.UPSERT_UNIQUE_SECONDARY_KEY : 105'
-  - 'box.error.ROLLBACK_IN_SUB_STMT : 123'
   - 'box.error.WRONG_SCHEMA_VERSION : 109'
-  - 'box.error.UNSUPPORTED_INDEX_FEATURE : 112'
-  - 'box.error.INDEX_PART_TYPE_MISMATCH : 24'
+  - 'box.error.ROLLBACK_IN_SUB_STMT : 123'
+  - 'box.error.PROTOCOL : 104'
   - 'box.error.INVALID_XLOG_TYPE : 125'
+  - 'box.error.INDEX_PART_TYPE_MISMATCH : 24'
+  - 'box.error.UNSUPPORTED_INDEX_FEATURE : 112'
 ...
 test_run:cmd("setopt delimiter ''");
 ---
diff --git a/test/box/select.result b/test/box/select.result
index 4aed706..6e6ccad 100644
--- a/test/box/select.result
+++ b/test/box/select.result
@@ -619,6 +619,11 @@ collectgarbage('collect')
 ---
 - 0
 ...
+-- gh-3224 resurrect tuple bigrefs
+collectgarbage('stop')
+---
+- 0
+...
 s = box.schema.space.create('select', { temporary = true })
 ---
 ...
@@ -628,22 +633,37 @@ index = s:create_index('primary', { type = 'tree' })
 a = s:insert{0}
 ---
 ...
-lots_of_links = {}
+lots_of_links = setmetatable({}, {__mode = 'v'})
+---
+...
+ref_count = 0
+---
+...
+while (ref_count < 100000) do table.insert(lots_of_links, s:get{0}) ref_count = ref_count + 1 end
 ---
 ...
+ref_count
+---
+- 100000
+...
 ref_count = 0
 ---
 ...
-while (true) do table.insert(lots_of_links, s:get{0}) ref_count = ref_count + 1 end
+for k, v in pairs(lots_of_links) do ref_count = ref_count + 1 end
 ---
-- error: Tuple reference counter overflow
 ...
 ref_count
 ---
-- 65531
+- 100000
+...
+-- check that tuples are deleted after gc is activated
+collectgarbage('collect')
+---
+- 0
 ...
-lots_of_links = {}
+lots_of_links
 ---
+- []
 ...
 s:drop()
 ---
diff --git a/test/box/select.test.lua b/test/box/select.test.lua
index 54c2ecc..f15c6e2 100644
--- a/test/box/select.test.lua
+++ b/test/box/select.test.lua
@@ -124,12 +124,21 @@ test.random(s.index[0], 48)
 s:drop()
 
 collectgarbage('collect')
+
+-- gh-3224 resurrect tuple bigrefs
+
+collectgarbage('stop')
 s = box.schema.space.create('select', { temporary = true })
 index = s:create_index('primary', { type = 'tree' })
 a = s:insert{0}
-lots_of_links = {}
+lots_of_links = setmetatable({}, {__mode = 'v'})
 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 = {}
+ref_count = 0
+for k, v in pairs(lots_of_links) do ref_count = ref_count + 1 end
+ref_count
+-- check that tuples are deleted after gc is activated
+collectgarbage('collect')
+lots_of_links
 s:drop()
-- 
2.7.4

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

[Konstantin Osipov]

* imeevma@tarantool.org <imeevma@tarantool.org> [18/06/01 18:42]:
> 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.

Please rename plural 'bigrefs' to bigref_index or bigref_map or
bigref_list.


-- 
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov

[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@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);
>   }
>   

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

[Imeev Mergen]

On 06/04/2018 02:21 PM, Vladislav Shpilevoy wrote:
> Hello. Thanks for the patch! It is almost perfect! See 6 comments
> below.
>
> On 01/06/2018 18:41, imeevma@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.
Done. Added initialization with 0 when memory is allocated.
>
>> +    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.
Done.
>
>> +    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.
Done.
>
>> +        };
>> +    };
>>       /** 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
Done.
>
>> +        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 ... }
Done.
>
>> +        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);
>>   }
Done. Also deleted tuple_bless_xc.

commit 7b7965f6c5462142a607d9db542d698fc94fbbbe
Author: Mergen Imeev <imeevma@gmail.com>
Date:   Mon May 28 19:17:51 2018 +0300

     box: create bigrefs for tuples

     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

diff --git a/src/box/errcode.h b/src/box/errcode.h
index a0759f8..e009524 100644
--- a/src/box/errcode.h
+++ b/src/box/errcode.h
@@ -138,7 +138,7 @@ struct errcode_record {
      /* 83 */_(ER_ROLE_EXISTS,        "Role '%s' already exists") \
      /* 84 */_(ER_CREATE_ROLE,        "Failed to create role '%s': %s") \
      /* 85 */_(ER_INDEX_EXISTS,        "Index '%s' already exists") \
-    /* 86 */_(ER_TUPLE_REF_OVERFLOW,    "Tuple reference counter 
overflow") \
+    /* 86 */_(ER_UNUSED6,            "") \
      /* 87 */_(ER_ROLE_LOOP,            "Granting role '%s' to role 
'%s' would create a loop") \
      /* 88 */_(ER_GRANT,            "Incorrect grant arguments: %s") \
      /* 89 */_(ER_PRIV_GRANTED,        "User '%s' already has %s access 
on %s '%s'") \
diff --git a/src/box/lua/tuple.c b/src/box/lua/tuple.c
index 8057331..22fe696 100644
--- a/src/box/lua/tuple.c
+++ b/src/box/lua/tuple.c
@@ -496,10 +496,7 @@ luaT_pushtuple(struct lua_State *L, box_tuple_t *tuple)
          luaL_pushcdata(L, CTID_CONST_STRUCT_TUPLE_REF);
      *ptr = tuple;
      /* The order is important - first reference tuple, next set gc */
-    if (box_tuple_ref(tuple) != 0) {
-        luaT_error(L);
-        return;
-    }
+    box_tuple_ref(tuple);
      lua_pushcfunction(L, lbox_tuple_gc);
      luaL_setcdatagc(L, -2);
  }
diff --git a/src/box/port.c b/src/box/port.c
index 03f6be7..9b6b858 100644
--- a/src/box/port.c
+++ b/src/box/port.c
@@ -45,8 +45,7 @@ port_tuple_add(struct port *base, struct tuple *tuple)
      struct port_tuple *port = port_tuple(base);
      struct port_tuple_entry *e;
      if (port->size == 0) {
-        if (tuple_ref(tuple) != 0)
-            return -1;
+        tuple_ref(tuple);
          e = &port->first_entry;
          port->first = port->last = e;
      } else {
@@ -55,10 +54,7 @@ port_tuple_add(struct port *base, struct tuple *tuple)
              diag_set(OutOfMemory, sizeof(*e), "mempool_alloc", "e");
              return -1;
          }
-        if (tuple_ref(tuple) != 0) {
-            mempool_free(&port_tuple_entry_pool, e);
-            return -1;
-        }
+        tuple_ref(tuple);
          port->last->next = e;
          port->last = e;
      }
diff --git a/src/box/tuple.c b/src/box/tuple.c
index 014f374..6e63433 100644
--- a/src/box/tuple.c
+++ b/src/box/tuple.c
@@ -48,6 +48,26 @@ enum {
      OBJSIZE_MIN = 16,
  };

+/**
+ * Container for big reference counters. Contains array of big
+ * reference counters, size of this array and number of non-zero
+ * big reference counters. When reference counter of tuple becomes
+ * more than 32767, field refs of this tuple becomes index of big
+ * reference counter in big reference counter array and field
+ * is_bigref is set true. The moment big reference becomes equal
+ * 32767 it is set to 0, refs of the tuple becomes 32767 and
+ * is_bigref becomes false. Big reference counter can be equal to
+ * 0 or be more than 32767.
+ */
+struct bigref_list {
+    /** Array of big reference counters */
+    uint32_t *refs;
+    /** Number of non-zero elements in the array */
+    uint16_t size;
+    /** Capacity of the array */
+    uint16_t capacity;
+};
+
  static const double ALLOC_FACTOR = 1.05;

  /**
@@ -58,6 +78,12 @@ struct tuple *box_tuple_last;

  struct tuple_format *tuple_format_runtime;

+/**
+* All bigrefs of tuples.
+* \sa tuple_ref_slow()
+*/
+static struct bigref_list bigref_list;
+
  static void
  runtime_tuple_delete(struct tuple_format *format, struct tuple *tuple);

@@ -151,6 +177,15 @@ tuple_validate_raw(struct tuple_format *format, 
const char *tuple)
      return 0;
  }

+/** Initialize big references container. */
+static inline void
+bigref_list_create()
+{
+    bigref_list.size = 0;
+    bigref_list.refs = NULL;
+    bigref_list.capacity = 0;
+}
+
  /**
   * Incremented on every snapshot and is used to distinguish tuples
   * which were created after start of a snapshot (these tuples can
@@ -211,6 +246,8 @@ tuple_init(field_name_hash_f hash)

      box_tuple_last = NULL;

+    bigref_list_create();
+
      if (coll_id_cache_init() != 0)
          return -1;

@@ -244,6 +281,124 @@ tuple_arena_create(struct slab_arena *arena, 
struct quota *quota,
      }
  }

+enum {
+    TUPLE_BIGREF_FACTOR = 2,
+    TUPLE_BIGREF_MAX = UINT32_MAX,
+    TUPLE_BIGREF_MIN_CAPACITY = 16,
+    TUPLE_BIGREF_MAX_CAPACITY = UINT16_MAX >> 1
+};
+
+/** Destroy big references and free memory that was allocated. */
+static inline void
+bigref_list_destroy()
+{
+    free(bigref_list.refs);
+    bigref_list.size = 0;
+    bigref_list.refs = NULL;
+    bigref_list.capacity = 0;
+}
+
+/**
+ * Return index for new big reference counter and allocate memory
+ * if needed.
+ * @retval index for new big reference counter.
+ */
+static inline uint16_t
+tuple_bigref_retrieve()
+{
+    if (bigref_list.size < bigref_list.capacity) {
+        uint16_t vacant_index = 0;
+        while (bigref_list.refs[vacant_index] != 0)
+            ++vacant_index;
+        return vacant_index;
+    }
+    /* Extend the array. */
+    uint16_t capacity = bigref_list.capacity;
+    if (capacity == 0) {
+        capacity = TUPLE_BIGREF_MIN_CAPACITY;
+    } else {
+        capacity *= TUPLE_BIGREF_FACTOR;
+        if (capacity >= TUPLE_BIGREF_MAX_CAPACITY)
+            panic("Too many big references");
+    }
+    uint32_t *refs = (uint32_t *) realloc(bigref_list.refs, capacity *
+                          sizeof(*bigref_list.refs));
+    if (refs == NULL) {
+        panic("failed to reallocate %zu bytes: Cannot allocate"\
+              " memory.", capacity * sizeof(*bigref_list.refs));
+    }
+    bigref_list.refs = refs;
+    memset(bigref_list.refs + bigref_list.capacity, 0, capacity -
+           bigref_list.capacity);
+    bigref_list.capacity = capacity;
+    return bigref_list.size++;
+}
+
+void
+tuple_ref_slow(struct tuple *tuple)
+{
+    assert(tuple->is_bigref || tuple->refs == TUPLE_REF_MAX);
+    if (! tuple->is_bigref) {
+        tuple->ref_index = tuple_bigref_retrieve();
+        tuple->is_bigref = true;
+        bigref_list.refs[tuple->ref_index] = TUPLE_REF_MAX;
+    } else if (bigref_list.refs[tuple->ref_index] == TUPLE_BIGREF_MAX)
+        panic("Tuple big reference counter overflow");
+    bigref_list.refs[tuple->ref_index]++;
+}
+
+/**
+ * Try to decrease allocated memory if it is possible. Free memory
+ * when size == 0.
+ */
+static inline void
+bigref_list_compact()
+{
+    if (bigref_list.size == 0) {
+        bigref_list_destroy();
+        return;
+    }
+    if (bigref_list.capacity == TUPLE_BIGREF_MIN_CAPACITY ||
+        bigref_list.size > bigref_list.capacity / TUPLE_BIGREF_FACTOR)
+        return;
+    uint16_t capacity = bigref_list.capacity;
+    while (bigref_list.refs[capacity - 1] == 0)
+        capacity--;
+    if (capacity < TUPLE_BIGREF_MIN_CAPACITY)
+        capacity = TUPLE_BIGREF_MIN_CAPACITY;
+    if (capacity > bigref_list.capacity / TUPLE_BIGREF_FACTOR)
+        return;
+    /* Round up capacity to the next highest power of 2*/
+    capacity--;
+    capacity |= capacity >> 1;
+    capacity |= capacity >> 2;
+    capacity |= capacity >> 4;
+    capacity |= capacity >> 8;
+    capacity |= capacity >> 16;
+    capacity++;
+    uint32_t *refs = (uint32_t *) realloc(bigref_list.refs, capacity *
+                          sizeof(*bigref_list.refs));
+    if (refs == NULL)
+        panic("failed to reallocate %zu bytes: Cannot allocate"\
+              " memory.", capacity * sizeof(*bigref_list.refs));
+    bigref_list.refs = refs;
+    bigref_list.capacity = capacity;
+}
+
+void
+tuple_unref_slow(struct tuple *tuple)
+{
+    assert(tuple->is_bigref &&
+           bigref_list.refs[tuple->ref_index] > TUPLE_REF_MAX);
+    if(--bigref_list.refs[tuple->ref_index] == TUPLE_REF_MAX) {
+        bigref_list.refs[tuple->ref_index] = 0;
+        bigref_list.size--;
+        tuple->ref_index = TUPLE_REF_MAX;
+        tuple->is_bigref = false;
+        bigref_list_compact();
+    }
+}
+
  void
  tuple_arena_destroy(struct slab_arena *arena)
  {
@@ -265,6 +420,8 @@ tuple_free(void)
      tuple_format_free();

      coll_id_cache_destroy();
+
+    bigref_list_destroy();
  }

  box_tuple_format_t *
@@ -288,7 +445,8 @@ int
  box_tuple_ref(box_tuple_t *tuple)
  {
      assert(tuple != NULL);
-    return tuple_ref(tuple);
+    tuple_ref(tuple);
+    return 0;
  }

  void
@@ -357,10 +515,7 @@ box_tuple_iterator(box_tuple_t *tuple)
               "mempool", "new slab");
          return NULL;
      }
-    if (tuple_ref(tuple) != 0) {
-        mempool_free(&tuple_iterator_pool, it);
-        return NULL;
-    }
+    tuple_ref(tuple);
      tuple_rewind(it, tuple);
      return it;
  }
diff --git a/src/box/tuple.h b/src/box/tuple.h
index e2384dd..d2cf662 100644
--- a/src/box/tuple.h
+++ b/src/box/tuple.h
@@ -105,8 +105,7 @@ typedef struct tuple box_tuple_t;
   * tuple will leak.
   *
   * \param tuple a tuple
- * \retval -1 on error (check box_error_last())
- * \retval 0 on success
+ * \retval 0 always
   * \sa box_tuple_unref()
   */
  int
@@ -307,9 +306,17 @@ box_tuple_upsert(const box_tuple_t *tuple, const 
char *expr, const
   */
  struct PACKED tuple
  {
-    /** reference counter */
-    uint16_t refs;
-    /** format identifier */
+    union {
+        /** Reference counter. */
+        uint16_t refs;
+        struct {
+            /** Index of big reference counter. */
+            uint16_t ref_index : 15;
+            /** Big reference flag. */
+            bool is_bigref : 1;
+        };
+    };
+    /** Format identifier. */
      uint16_t format_id;
      /**
       * Length of the MessagePack data in raw part of the
@@ -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 (unlikely(tuple->refs >= TUPLE_REF_MAX))
+        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 (unlikely(tuple->is_bigref)) {
+        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 */
@@ -849,35 +863,11 @@ tuple_to_buf(const struct tuple *tuple, char *buf, 
size_t size);
  #include "tuple_update.h"
  #include "errinj.h"

-/**
- * \copydoc tuple_ref()
- * \throws if overflow detected.
- */
-static inline void
-tuple_ref_xc(struct tuple *tuple)
-{
-    if (tuple_ref(tuple))
-        diag_raise();
-}
-
-/**
- * \copydoc tuple_bless
- * \throw ER_TUPLE_REF_OVERFLOW
- */
-static inline box_tuple_t *
-tuple_bless_xc(struct tuple *tuple)
-{
-    box_tuple_t *blessed = tuple_bless(tuple);
-    if (blessed == NULL)
-        diag_raise();
-    return blessed;
-}
-
  /** Make tuple references exception-friendly in absence of @finally. */
  struct TupleRefNil {
      struct tuple *tuple;
      TupleRefNil (struct tuple *arg) :tuple(arg)
-    { if (tuple) tuple_ref_xc(tuple); }
+    { if (tuple) tuple_ref(tuple); }
      ~TupleRefNil() { if (tuple) tuple_unref(tuple); }

      TupleRefNil(const TupleRefNil&) = delete;
diff --git a/test/box/misc.result b/test/box/misc.result
index 8f94f55..f7703ba 100644
--- a/test/box/misc.result
+++ b/test/box/misc.result
@@ -332,7 +332,6 @@ t;
    - 'box.error.UNKNOWN_UPDATE_OP : 28'
    - 'box.error.WRONG_COLLATION_OPTIONS : 151'
    - 'box.error.CURSOR_NO_TRANSACTION : 80'
-  - 'box.error.TUPLE_REF_OVERFLOW : 86'
    - 'box.error.ALTER_SEQUENCE : 143'
    - 'box.error.INVALID_XLOG_NAME : 75'
    - 'box.error.SAVEPOINT_EMPTY_TX : 60'
@@ -360,7 +359,7 @@ t;
    - 'box.error.VINYL_MAX_TUPLE_SIZE : 139'
    - 'box.error.LOAD_FUNCTION : 99'
    - 'box.error.INVALID_XLOG : 74'
-  - 'box.error.PRIV_NOT_GRANTED : 91'
+  - 'box.error.READ_VIEW_ABORTED : 130'
    - 'box.error.TRANSACTION_CONFLICT : 97'
    - 'box.error.GUEST_USER_PASSWORD : 96'
    - 'box.error.PROC_C : 102'
@@ -405,7 +404,7 @@ t;
    - 'box.error.injection : table: <address>
    - 'box.error.NULLABLE_MISMATCH : 153'
    - 'box.error.LAST_DROP : 15'
-  - 'box.error.NO_SUCH_ROLE : 82'
+  - 'box.error.TUPLE_FORMAT_LIMIT : 16'
    - 'box.error.DECOMPRESSION : 124'
    - 'box.error.CREATE_SEQUENCE : 142'
    - 'box.error.CREATE_USER : 43'
@@ -414,66 +413,66 @@ t;
    - 'box.error.SEQUENCE_OVERFLOW : 147'
    - 'box.error.SYSTEM : 115'
    - 'box.error.KEY_PART_IS_TOO_LONG : 118'
-  - 'box.error.TUPLE_FORMAT_LIMIT : 16'
-  - 'box.error.BEFORE_REPLACE_RET : 53'
+  - 'box.error.INJECTION : 8'
+  - 'box.error.INVALID_MSGPACK : 20'
    - 'box.error.NO_SUCH_SAVEPOINT : 61'
    - 'box.error.TRUNCATE_SYSTEM_SPACE : 137'
    - 'box.error.VY_QUOTA_TIMEOUT : 135'
    - 'box.error.WRONG_INDEX_OPTIONS : 108'
    - 'box.error.INVALID_VYLOG_FILE : 133'
    - 'box.error.INDEX_FIELD_COUNT_LIMIT : 127'
-  - 'box.error.READ_VIEW_ABORTED : 130'
+  - 'box.error.PRIV_NOT_GRANTED : 91'
    - 'box.error.USER_MAX : 56'
-  - 'box.error.PROTOCOL : 104'
+  - 'box.error.BEFORE_REPLACE_RET : 53'
    - 'box.error.TUPLE_NOT_ARRAY : 22'
    - 'box.error.KEY_PART_COUNT : 31'
    - 'box.error.ALTER_SPACE : 12'
    - 'box.error.ACTIVE_TRANSACTION : 79'
    - 'box.error.EXACT_FIELD_COUNT : 38'
    - 'box.error.DROP_SEQUENCE : 144'
-  - 'box.error.INVALID_MSGPACK : 20'
    - 'box.error.MORE_THAN_ONE_TUPLE : 41'
-  - 'box.error.RTREE_RECT : 101'
-  - 'box.error.SUB_STMT_MAX : 121'
+  - 'box.error.UPSERT_UNIQUE_SECONDARY_KEY : 105'
    - 'box.error.UNKNOWN_REQUEST_TYPE : 48'
-  - 'box.error.SPACE_EXISTS : 10'
+  - 'box.error.SUB_STMT_MAX : 121'
    - 'box.error.PROC_LUA : 32'
+  - 'box.error.SPACE_EXISTS : 10'
    - 'box.error.ROLE_NOT_GRANTED : 92'
+  - 'box.error.UNSUPPORTED : 5'
    - 'box.error.NO_SUCH_SPACE : 36'
    - 'box.error.WRONG_INDEX_PARTS : 107'
-  - 'box.error.DROP_SPACE : 11'
    - 'box.error.MIN_FIELD_COUNT : 39'
    - 'box.error.REPLICASET_UUID_MISMATCH : 63'
    - 'box.error.UPDATE_FIELD : 29'
+  - 'box.error.INDEX_EXISTS : 85'
    - 'box.error.COMPRESSION : 119'
    - 'box.error.INVALID_ORDER : 68'
-  - 'box.error.INDEX_EXISTS : 85'
    - 'box.error.SPLICE : 25'
    - 'box.error.UNKNOWN : 0'
+  - 'box.error.IDENTIFIER : 70'
    - 'box.error.DROP_PRIMARY_KEY : 17'
    - 'box.error.NULLABLE_PRIMARY : 152'
    - 'box.error.NO_SUCH_SEQUENCE : 145'
    - 'box.error.RELOAD_CFG : 58'
    - 'box.error.INVALID_UUID : 64'
-  - 'box.error.INJECTION : 8'
+  - 'box.error.DROP_SPACE : 11'
    - 'box.error.TIMEOUT : 78'
-  - 'box.error.IDENTIFIER : 70'
    - 'box.error.ITERATOR_TYPE : 72'
    - 'box.error.REPLICA_MAX : 73'
+  - 'box.error.NO_SUCH_ROLE : 82'
    - 'box.error.MISSING_REQUEST_FIELD : 69'
    - 'box.error.MISSING_SNAPSHOT : 93'
    - 'box.error.WRONG_SPACE_OPTIONS : 111'
    - 'box.error.READONLY : 7'
-  - 'box.error.UNSUPPORTED : 5'
    - 'box.error.UPDATE_INTEGER_OVERFLOW : 95'
+  - 'box.error.RTREE_RECT : 101'
    - 'box.error.NO_CONNECTION : 77'
    - 'box.error.INVALID_XLOG_ORDER : 76'
-  - 'box.error.UPSERT_UNIQUE_SECONDARY_KEY : 105'
-  - 'box.error.ROLLBACK_IN_SUB_STMT : 123'
    - 'box.error.WRONG_SCHEMA_VERSION : 109'
-  - 'box.error.UNSUPPORTED_INDEX_FEATURE : 112'
-  - 'box.error.INDEX_PART_TYPE_MISMATCH : 24'
+  - 'box.error.ROLLBACK_IN_SUB_STMT : 123'
+  - 'box.error.PROTOCOL : 104'
    - 'box.error.INVALID_XLOG_TYPE : 125'
+  - 'box.error.INDEX_PART_TYPE_MISMATCH : 24'
+  - 'box.error.UNSUPPORTED_INDEX_FEATURE : 112'
  ...
  test_run:cmd("setopt delimiter ''");
  ---
diff --git a/test/box/select.result b/test/box/select.result
index 4aed706..6e6ccad 100644
--- a/test/box/select.result
+++ b/test/box/select.result
@@ -619,6 +619,11 @@ collectgarbage('collect')
  ---
  - 0
  ...
+-- gh-3224 resurrect tuple bigrefs
+collectgarbage('stop')
+---
+- 0
+...
  s = box.schema.space.create('select', { temporary = true })
  ---
  ...
@@ -628,22 +633,37 @@ index = s:create_index('primary', { type = 'tree' })
  a = s:insert{0}
  ---
  ...
-lots_of_links = {}
+lots_of_links = setmetatable({}, {__mode = 'v'})
+---
+...
+ref_count = 0
+---
+...
+while (ref_count < 100000) do table.insert(lots_of_links, s:get{0}) 
ref_count = ref_count + 1 end
  ---
  ...
+ref_count
+---
+- 100000
+...
  ref_count = 0
  ---
  ...
-while (true) do table.insert(lots_of_links, s:get{0}) ref_count = 
ref_count + 1 end
+for k, v in pairs(lots_of_links) do ref_count = ref_count + 1 end
  ---
-- error: Tuple reference counter overflow
  ...
  ref_count
  ---
-- 65531
+- 100000
+...
+-- check that tuples are deleted after gc is activated
+collectgarbage('collect')
+---
+- 0
  ...
-lots_of_links = {}
+lots_of_links
  ---
+- []
  ...
  s:drop()
  ---
diff --git a/test/box/select.test.lua b/test/box/select.test.lua
index 54c2ecc..f15c6e2 100644
--- a/test/box/select.test.lua
+++ b/test/box/select.test.lua
@@ -124,12 +124,21 @@ test.random(s.index[0], 48)
  s:drop()

  collectgarbage('collect')
+
+-- gh-3224 resurrect tuple bigrefs
+
+collectgarbage('stop')
  s = box.schema.space.create('select', { temporary = true })
  index = s:create_index('primary', { type = 'tree' })
  a = s:insert{0}
-lots_of_links = {}
+lots_of_links = setmetatable({}, {__mode = 'v'})
  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 = {}
+ref_count = 0
+for k, v in pairs(lots_of_links) do ref_count = ref_count + 1 end
+ref_count
+-- check that tuples are deleted after gc is activated
+collectgarbage('collect')
+lots_of_links
  s:drop()

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

[Vladislav Shpilevoy]

Thanks for the patch, Mergen! Please look at my 5 comments.

Vova, please, take a look on the patch. I have pasted it at the end
of the letter.

On 04/06/2018 17:21, Imeev Mergen wrote:
> 
> 
> On 06/04/2018 02:21 PM, Vladislav Shpilevoy wrote:
>> Hello. Thanks for the patch! It is almost perfect! See 6 comments
>> below.
>>
>> On 01/06/2018 18:41, imeevma@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
>>>
> 
> commit 7b7965f6c5462142a607d9db542d698fc94fbbbe
> Author: Mergen Imeev <imeevma@gmail.com>
> Date:   Mon May 28 19:17:51 2018 +0300
> 
>      box: create bigrefs for tuples
> 
>      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
> 
> diff --git a/src/box/tuple.c b/src/box/tuple.c
> index 014f374..6e63433 100644
> --- a/src/box/tuple.c
> +++ b/src/box/tuple.c
> @@ -48,6 +48,26 @@ enum {
>       OBJSIZE_MIN = 16,
>   };
> 
> +/**
> + * Container for big reference counters. Contains array of big
> + * reference counters, size of this array and number of non-zero
> + * big reference counters. When reference counter of tuple becomes
> + * more than 32767, field refs of this tuple becomes index of big
> + * reference counter in big reference counter array and field
> + * is_bigref is set true. The moment big reference becomes equal
> + * 32767 it is set to 0, refs of the tuple becomes 32767 and
> + * is_bigref becomes false. Big reference counter can be equal to
> + * 0 or be more than 32767.
> + */
> +struct bigref_list {
> +    /** Array of big reference counters */
> +    uint32_t *refs;
> +    /** Number of non-zero elements in the array */
> +    uint16_t size;
> +    /** Capacity of the array */
> +    uint16_t capacity;
> +};

1. Instead of

     struct name {
         ...
     };
     static struct name name;

you can do this

     static struct name {
         ...
     } name;

> +
>   static const double ALLOC_FACTOR = 1.05;
> 
>   /**
> @@ -151,6 +177,15 @@ tuple_validate_raw(struct tuple_format *format, const char *tuple)
>       return 0;
>   }
> 
> +/** Initialize big references container. */
> +static inline void
> +bigref_list_create()
> +{
> +    bigref_list.size = 0;
> +    bigref_list.refs = NULL;
> +    bigref_list.capacity = 0;

2. Memset is faster than per-member resetting. We with
Vladimir Davydov have benched it.

> +/**
> + * Return index for new big reference counter and allocate memory
> + * if needed.
> + * @retval index for new big reference counter.
> + */
> +static inline uint16_t
> +tuple_bigref_retrieve()
> +{
> +    if (bigref_list.size < bigref_list.capacity) {
> +        uint16_t vacant_index = 0;
> +        while (bigref_list.refs[vacant_index] != 0)
> +            ++vacant_index;
> +        return vacant_index;
> +    }
> +    /* Extend the array. */
> +    uint16_t capacity = bigref_list.capacity;
> +    if (capacity == 0) {
> +        capacity = TUPLE_BIGREF_MIN_CAPACITY;
> +    } else {
> +        capacity *= TUPLE_BIGREF_FACTOR;
> +        if (capacity >= TUPLE_BIGREF_MAX_CAPACITY)

3. By such check you have limited the capacity with 16384 bigrefs instead of
32k. Capacity here is always a power of 2. TUPLE_BIGREF_MAX_CAPACITY is
2^15. So here after 2^14 you get overflow. 2^14 = 16384. I have fixed it on
the branch.

> +            panic("Too many big references");
> +    }
> +    uint32_t *refs = (uint32_t *) realloc(bigref_list.refs, capacity *
> +                          sizeof(*bigref_list.refs));
> +    if (refs == NULL) {
> +        panic("failed to reallocate %zu bytes: Cannot allocate"\
> +              " memory.", capacity * sizeof(*bigref_list.refs));
> +    }
> +    bigref_list.refs = refs;
> +    memset(bigref_list.refs + bigref_list.capacity, 0, capacity -
> +           bigref_list.capacity);
> +    bigref_list.capacity = capacity;
> +    return bigref_list.size++;
> +}
> +
> +/**
> + * Try to decrease allocated memory if it is possible. Free memory
> + * when size == 0.
> + */
> +static inline void
> +bigref_list_compact()
> +{
> +    if (bigref_list.size == 0) {
> +        bigref_list_destroy();
> +        return;
> +    }
> +    if (bigref_list.capacity == TUPLE_BIGREF_MIN_CAPACITY ||
> +        bigref_list.size > bigref_list.capacity / TUPLE_BIGREF_FACTOR)
> +        return;
> +    uint16_t capacity = bigref_list.capacity;
> +    while (bigref_list.refs[capacity - 1] == 0)
> +        capacity--;
> +    if (capacity < TUPLE_BIGREF_MIN_CAPACITY)
> +        capacity = TUPLE_BIGREF_MIN_CAPACITY;
> +    if (capacity > bigref_list.capacity / TUPLE_BIGREF_FACTOR)
> +        return;
> +    /* Round up capacity to the next highest power of 2*/
> +    capacity--;
> +    capacity |= capacity >> 1;
> +    capacity |= capacity >> 2;
> +    capacity |= capacity >> 4;
> +    capacity |= capacity >> 8;
> +    capacity |= capacity >> 16;

4. This is because blind copy and paste is bad. The algorithm implementation
I provided to you was for 32 bit unsigned integers, but here you have 16 bits
only, so capacity >> 16 is always 0.

> +    capacity++;
> +    uint32_t *refs = (uint32_t *) realloc(bigref_list.refs, capacity *
> +                          sizeof(*bigref_list.refs));
> +    if (refs == NULL)
> +        panic("failed to reallocate %zu bytes: Cannot allocate"\
> +              " memory.", capacity * sizeof(*bigref_list.refs));
> +    bigref_list.refs = refs;
> +    bigref_list.capacity = capacity;
> +}
> +

5. I have removed tuple_bless == NULL checks from all the code.

Here the patch:

============================================================================

commit 9d82fa9f9ae24c7dc91cf9dd7a416ec533fb8147
Author: Mergen Imeev <imeevma@gmail.com>
Date:   Mon May 28 19:17:51 2018 +0300

     box: create bigrefs for tuples
     
     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

diff --git a/src/box/box.cc b/src/box/box.cc
index c728a4c53..42578613d 100644
--- a/src/box/box.cc
+++ b/src/box/box.cc
@@ -174,20 +174,22 @@ process_rw(struct request *request, struct space *space, struct tuple **result)
  		txn_rollback_stmt();
  		return -1;
  	}
+	if (result == NULL)
+		return txn_commit_stmt(txn, request);
+	*result = tuple;
+	if (tuple == NULL)
+		return txn_commit_stmt(txn, request);
  	/*
  	 * Pin the tuple locally before the commit,
  	 * otherwise it may go away during yield in
  	 * when WAL is written in autocommit mode.
  	 */
-	TupleRefNil ref(tuple);
-	if (txn_commit_stmt(txn, request) != 0)
-		return -1;
-	if (result != NULL) {
-		if (tuple != NULL && tuple_bless(tuple) == NULL)
-			return -1;
-		*result = tuple;
-	}
-	return 0;
+	tuple_ref(tuple);
+	int rc = txn_commit_stmt(txn, request);
+	if (rc == 0)
+		tuple_bless(tuple);
+	tuple_unref(tuple);
+	return rc;
  }
  
  void
diff --git a/src/box/errcode.h b/src/box/errcode.h
index a0759f8f4..e009524ad 100644
--- a/src/box/errcode.h
+++ b/src/box/errcode.h
@@ -138,7 +138,7 @@ struct errcode_record {
  	/* 83 */_(ER_ROLE_EXISTS,		"Role '%s' already exists") \
  	/* 84 */_(ER_CREATE_ROLE,		"Failed to create role '%s': %s") \
  	/* 85 */_(ER_INDEX_EXISTS,		"Index '%s' already exists") \
-	/* 86 */_(ER_TUPLE_REF_OVERFLOW,	"Tuple reference counter overflow") \
+	/* 86 */_(ER_UNUSED6,			"") \
  	/* 87 */_(ER_ROLE_LOOP,			"Granting role '%s' to role '%s' would create a loop") \
  	/* 88 */_(ER_GRANT,			"Incorrect grant arguments: %s") \
  	/* 89 */_(ER_PRIV_GRANTED,		"User '%s' already has %s access on %s '%s'") \
diff --git a/src/box/index.cc b/src/box/index.cc
index 3c62ec1cc..f992bc94c 100644
--- a/src/box/index.cc
+++ b/src/box/index.cc
@@ -220,8 +220,8 @@ box_index_random(uint32_t space_id, uint32_t index_id, uint32_t rnd,
  	/* No tx management, random() is for approximation anyway. */
  	if (index_random(index, rnd, result) != 0)
  		return -1;
-	if (*result != NULL && tuple_bless(*result) == NULL)
-		return -1;
+	if (*result != NULL)
+		tuple_bless(*result);
  	return 0;
  }
  
@@ -253,8 +253,8 @@ box_index_get(uint32_t space_id, uint32_t index_id, const char *key,
  	txn_commit_ro_stmt(txn);
  	/* Count statistics. */
  	rmean_collect(rmean_box, IPROTO_SELECT, 1);
-	if (*result != NULL && tuple_bless(*result) == NULL)
-		return -1;
+	if (*result != NULL)
+		tuple_bless(*result);
  	return 0;
  }
  
@@ -285,8 +285,8 @@ box_index_min(uint32_t space_id, uint32_t index_id, const char *key,
  		return -1;
  	}
  	txn_commit_ro_stmt(txn);
-	if (*result != NULL && tuple_bless(*result) == NULL)
-		return -1;
+	if (*result != NULL)
+		tuple_bless(*result);
  	return 0;
  }
  
@@ -317,8 +317,8 @@ box_index_max(uint32_t space_id, uint32_t index_id, const char *key,
  		return -1;
  	}
  	txn_commit_ro_stmt(txn);
-	if (*result != NULL && tuple_bless(*result) == NULL)
-		return -1;
+	if (*result != NULL)
+		tuple_bless(*result);
  	return 0;
  }
  
@@ -397,8 +397,8 @@ box_iterator_next(box_iterator_t *itr, box_tuple_t **result)
  	assert(result != NULL);
  	if (iterator_next(itr, result) != 0)
  		return -1;
-	if (*result != NULL && tuple_bless(*result) == NULL)
-		return -1;
+	if (*result != NULL)
+		tuple_bless(*result);
  	return 0;
  }
  
diff --git a/src/box/lua/tuple.c b/src/box/lua/tuple.c
index 80573313d..22fe69611 100644
--- a/src/box/lua/tuple.c
+++ b/src/box/lua/tuple.c
@@ -496,10 +496,7 @@ luaT_pushtuple(struct lua_State *L, box_tuple_t *tuple)
  		luaL_pushcdata(L, CTID_CONST_STRUCT_TUPLE_REF);
  	*ptr = tuple;
  	/* The order is important - first reference tuple, next set gc */
-	if (box_tuple_ref(tuple) != 0) {
-		luaT_error(L);
-		return;
-	}
+	box_tuple_ref(tuple);
  	lua_pushcfunction(L, lbox_tuple_gc);
  	luaL_setcdatagc(L, -2);
  }
diff --git a/src/box/port.c b/src/box/port.c
index 03f6be79d..9b6b8580c 100644
--- a/src/box/port.c
+++ b/src/box/port.c
@@ -45,8 +45,7 @@ port_tuple_add(struct port *base, struct tuple *tuple)
  	struct port_tuple *port = port_tuple(base);
  	struct port_tuple_entry *e;
  	if (port->size == 0) {
-		if (tuple_ref(tuple) != 0)
-			return -1;
+		tuple_ref(tuple);
  		e = &port->first_entry;
  		port->first = port->last = e;
  	} else {
@@ -55,10 +54,7 @@ port_tuple_add(struct port *base, struct tuple *tuple)
  			diag_set(OutOfMemory, sizeof(*e), "mempool_alloc", "e");
  			return -1;
  		}
-		if (tuple_ref(tuple) != 0) {
-			mempool_free(&port_tuple_entry_pool, e);
-			return -1;
-		}
+		tuple_ref(tuple);
  		port->last->next = e;
  		port->last = e;
  	}
diff --git a/src/box/tuple.c b/src/box/tuple.c
index 014f37406..5fc1c1283 100644
--- a/src/box/tuple.c
+++ b/src/box/tuple.c
@@ -48,6 +48,26 @@ enum {
  	OBJSIZE_MIN = 16,
  };
  
+/**
+ * Container for big reference counters. Contains array of big
+ * reference counters, size of this array and number of non-zero
+ * big reference counters. When reference counter of tuple becomes
+ * more than 32767, field refs of this tuple becomes index of big
+ * reference counter in big reference counter array and field
+ * is_bigref is set true. The moment big reference becomes equal
+ * 32767 it is set to 0, refs of the tuple becomes 32767 and
+ * is_bigref becomes false. Big reference counter can be equal to
+ * 0 or be more than 32767.
+ */
+static struct bigref_list {
+	/** Array of big reference counters. */
+	uint32_t *refs;
+	/** Number of non-zero elements in the array. */
+	uint16_t size;
+	/** Capacity of the array. */
+	uint16_t capacity;
+} bigref_list;
+
  static const double ALLOC_FACTOR = 1.05;
  
  /**
@@ -151,6 +171,13 @@ tuple_validate_raw(struct tuple_format *format, const char *tuple)
  	return 0;
  }
  
+/** Initialize big references container. */
+static inline void
+bigref_list_create()
+{
+	memset(&bigref_list, 0, sizeof(bigref_list));
+}
+
  /**
   * Incremented on every snapshot and is used to distinguish tuples
   * which were created after start of a snapshot (these tuples can
@@ -211,6 +238,8 @@ tuple_init(field_name_hash_f hash)
  
  	box_tuple_last = NULL;
  
+	bigref_list_create();
+
  	if (coll_id_cache_init() != 0)
  		return -1;
  
@@ -244,6 +273,131 @@ tuple_arena_create(struct slab_arena *arena, struct quota *quota,
  	}
  }
  
+enum {
+	BIGREF_FACTOR = 2,
+	BIGREF_MAX = UINT32_MAX,
+	BIGREF_MIN_CAPACITY = 16,
+	/**
+	 * Only 15 bits are available for bigref list index in
+	 * struct tuple.
+	 */
+	BIGREF_MAX_CAPACITY = UINT16_MAX >> 1
+};
+
+/** Destroy big references and free memory that was allocated. */
+static inline void
+bigref_list_destroy()
+{
+	free(bigref_list.refs);
+	bigref_list_create();
+}
+
+/**
+ * Return index for new big reference counter and allocate memory
+ * if needed.
+ * @retval index for new big reference counter.
+ */
+static inline uint16_t
+bigref_list_new_index()
+{
+	if (bigref_list.size < bigref_list.capacity) {
+		uint16_t vacant_index = 0;
+		while (bigref_list.refs[vacant_index] != 0)
+			++vacant_index;
+		return vacant_index;
+	}
+	/* Extend the array. */
+	uint16_t capacity = bigref_list.capacity;
+	if (capacity == 0)
+		capacity = BIGREF_MIN_CAPACITY;
+	else if (capacity < BIGREF_MAX_CAPACITY)
+		capacity = MIN(capacity * BIGREF_FACTOR, BIGREF_MAX_CAPACITY);
+	else
+		panic("Too many big references");
+	uint32_t *refs = (uint32_t *) realloc(bigref_list.refs, capacity *
+					      sizeof(*bigref_list.refs));
+	if (refs == NULL) {
+		panic("failed to reallocate %zu bytes: Cannot allocate "\
+		      "memory.", capacity * sizeof(*bigref_list.refs));
+	}
+	bigref_list.refs = refs;
+	memset(bigref_list.refs + bigref_list.capacity, 0, capacity -
+	       bigref_list.capacity);
+	bigref_list.capacity = capacity;
+	return bigref_list.size++;
+}
+
+void
+tuple_ref_slow(struct tuple *tuple)
+{
+	assert(tuple->is_bigref || tuple->refs == TUPLE_REF_MAX);
+	if (! tuple->is_bigref) {
+		tuple->ref_index = bigref_list_new_index();
+		tuple->is_bigref = true;
+		bigref_list.refs[tuple->ref_index] = TUPLE_REF_MAX;
+	} else if (bigref_list.refs[tuple->ref_index] == BIGREF_MAX) {
+		panic("Tuple big reference counter overflow");
+	}
+	bigref_list.refs[tuple->ref_index]++;
+}
+
+/**
+ * Try to decrease allocated memory if it is possible. Free memory
+ * when size == 0.
+ */
+static inline void
+bigref_list_delete_index(uint16_t index)
+{
+	bigref_list.refs[index] = 0;
+	if (--bigref_list.size == 0) {
+		bigref_list_destroy();
+		return;
+	}
+	if (bigref_list.capacity == BIGREF_MIN_CAPACITY ||
+	    bigref_list.size > bigref_list.capacity / BIGREF_FACTOR)
+		return;
+
+	uint16_t top_index = bigref_list.capacity - 1;
+	while (bigref_list.refs[top_index] == 0)
+		top_index--;
+
+	uint16_t needed_capacity = top_index + 1;
+	if (needed_capacity < BIGREF_MIN_CAPACITY)
+		needed_capacity = BIGREF_MIN_CAPACITY;
+	if (needed_capacity > bigref_list.capacity / BIGREF_FACTOR)
+		return;
+	/* Round up capacity to the next highest power of 2. */
+	assert(sizeof(needed_capacity) == sizeof(uint16_t));
+	needed_capacity--;
+	needed_capacity |= needed_capacity >> 1;
+	needed_capacity |= needed_capacity >> 2;
+	needed_capacity |= needed_capacity >> 4;
+	needed_capacity |= needed_capacity >> 8;
+	assert(needed_capacity < UINT16_MAX);
+	needed_capacity++;
+	uint32_t *refs =
+		(uint32_t *) realloc(bigref_list.refs, needed_capacity *
+				     sizeof(*bigref_list.refs));
+	if (refs == NULL) {
+		panic("failed to reallocate %zu bytes: Cannot allocate "\
+		      "memory.", needed_capacity * sizeof(*bigref_list.refs));
+	}
+	bigref_list.refs = refs;
+	bigref_list.capacity = needed_capacity;
+}
+
+void
+tuple_unref_slow(struct tuple *tuple)
+{
+	assert(tuple->is_bigref &&
+	       bigref_list.refs[tuple->ref_index] > TUPLE_REF_MAX);
+	if(--bigref_list.refs[tuple->ref_index] == TUPLE_REF_MAX) {
+		bigref_list_delete_index(tuple->ref_index);
+		tuple->ref_index = TUPLE_REF_MAX;
+		tuple->is_bigref = false;
+	}
+}
+
  void
  tuple_arena_destroy(struct slab_arena *arena)
  {
@@ -265,6 +419,8 @@ tuple_free(void)
  	tuple_format_free();
  
  	coll_id_cache_destroy();
+
+	bigref_list_destroy();
  }
  
  box_tuple_format_t *
@@ -288,7 +444,8 @@ int
  box_tuple_ref(box_tuple_t *tuple)
  {
  	assert(tuple != NULL);
-	return tuple_ref(tuple);
+	tuple_ref(tuple);
+	return 0;
  }
  
  void
@@ -357,10 +514,7 @@ box_tuple_iterator(box_tuple_t *tuple)
  			 "mempool", "new slab");
  		return NULL;
  	}
-	if (tuple_ref(tuple) != 0) {
-		mempool_free(&tuple_iterator_pool, it);
-		return NULL;
-	}
+	tuple_ref(tuple);
  	tuple_rewind(it, tuple);
  	return it;
  }
@@ -451,7 +605,6 @@ box_tuple_new(box_tuple_format_t *format, const char *data, const char *end)
  	struct tuple *ret = tuple_new(format, data, end);
  	if (ret == NULL)
  		return NULL;
-	/* Can't fail on zero refs. */
  	return tuple_bless(ret);
  }
  
diff --git a/src/box/tuple.h b/src/box/tuple.h
index e2384dda0..14dbd4094 100644
--- a/src/box/tuple.h
+++ b/src/box/tuple.h
@@ -105,8 +105,7 @@ typedef struct tuple box_tuple_t;
   * tuple will leak.
   *
   * \param tuple a tuple
- * \retval -1 on error (check box_error_last())
- * \retval 0 on success
+ * \retval 0 always
   * \sa box_tuple_unref()
   */
  int
@@ -269,8 +268,7 @@ box_tuple_next(box_tuple_iterator_t *it);
   * Use box_tuple_format_default() to create space-independent tuple.
   * \param data tuple data in MsgPack Array format ([field1, field2, ...]).
   * \param end the end of \a data
- * \retval NULL on out of memory
- * \retval tuple otherwise
+ * \retval tuple
   * \pre data, end is valid MsgPack Array
   * \sa \code box.tuple.new(data) \endcode
   */
@@ -307,9 +305,17 @@ box_tuple_upsert(const box_tuple_t *tuple, const char *expr, const
   */
  struct PACKED tuple
  {
-	/** reference counter */
-	uint16_t refs;
-	/** format identifier */
+	union {
+		/** Reference counter. */
+		uint16_t refs;
+		struct {
+			/** Index of big reference counter. */
+			uint16_t ref_index : 15;
+			/** Big reference flag. */
+			bool is_bigref : 1;
+		};
+	};
+	/** Format identifier. */
  	uint16_t format_id;
  	/**
  	 * Length of the MessagePack data in raw part of the
@@ -774,25 +780,35 @@ 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 (unlikely(tuple->refs >= TUPLE_REF_MAX))
+		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.
   *
@@ -802,10 +818,9 @@ static inline void
  tuple_unref(struct tuple *tuple)
  {
  	assert(tuple->refs - 1 >= 0);
-
-	tuple->refs--;
-
-	if (tuple->refs == 0)
+	if (unlikely(tuple->is_bigref))
+		tuple_unref_slow(tuple);
+	else if (--tuple->refs == 0)
  		tuple_delete(tuple);
  }
  
@@ -813,25 +828,18 @@ 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 */
+		tuple_unref(box_tuple_last);
  	/* Remember current tuple */
  	box_tuple_last = tuple;
  	return tuple;
@@ -849,41 +857,6 @@ tuple_to_buf(const struct tuple *tuple, char *buf, size_t size);
  #include "tuple_update.h"
  #include "errinj.h"
  
-/**
- * \copydoc tuple_ref()
- * \throws if overflow detected.
- */
-static inline void
-tuple_ref_xc(struct tuple *tuple)
-{
-	if (tuple_ref(tuple))
-		diag_raise();
-}
-
-/**
- * \copydoc tuple_bless
- * \throw ER_TUPLE_REF_OVERFLOW
- */
-static inline box_tuple_t *
-tuple_bless_xc(struct tuple *tuple)
-{
-	box_tuple_t *blessed = tuple_bless(tuple);
-	if (blessed == NULL)
-		diag_raise();
-	return blessed;
-}
-
-/** Make tuple references exception-friendly in absence of @finally. */
-struct TupleRefNil {
-	struct tuple *tuple;
-	TupleRefNil (struct tuple *arg) :tuple(arg)
-	{ if (tuple) tuple_ref_xc(tuple); }
-	~TupleRefNil() { if (tuple) tuple_unref(tuple); }
-
-	TupleRefNil(const TupleRefNil&) = delete;
-	void operator=(const TupleRefNil&) = delete;
-};
-
  /* @copydoc tuple_field_with_type() */
  static inline const char *
  tuple_field_with_type_xc(const struct tuple *tuple, uint32_t fieldno,
diff --git a/src/box/vinyl.c b/src/box/vinyl.c
index f0d26874e..dc0d02054 100644
--- a/src/box/vinyl.c
+++ b/src/box/vinyl.c
@@ -3822,7 +3822,6 @@ vinyl_iterator_primary_next(struct iterator *base, struct tuple **ret)
  	assert(base->next = vinyl_iterator_primary_next);
  	struct vinyl_iterator *it = (struct vinyl_iterator *)base;
  	assert(it->lsm->index_id == 0);
-	struct tuple *tuple;
  
  	if (it->tx == NULL) {
  		diag_set(ClientError, ER_CURSOR_NO_TRANSACTION);
@@ -3833,18 +3832,15 @@ vinyl_iterator_primary_next(struct iterator *base, struct tuple **ret)
  		goto fail;
  	}
  
-	if (vy_read_iterator_next(&it->iterator, &tuple) != 0)
+	if (vy_read_iterator_next(&it->iterator, ret) != 0)
  		goto fail;
-
-	if (tuple == NULL) {
+	if (*ret == NULL) {
  		/* EOF. Close the iterator immediately. */
  		vinyl_iterator_close(it);
-		*ret = NULL;
-		return 0;
+	} else {
+		tuple_bless(*ret);
  	}
-	*ret = tuple_bless(tuple);
-	if (*ret != NULL)
-		return 0;
+	return 0;
  fail:
  	vinyl_iterator_close(it);
  	return -1;
@@ -3890,11 +3886,10 @@ next:
  	 * Note, there's no need in vy_tx_track() as the
  	 * tuple is already tracked in the secondary index.
  	 */
-	struct tuple *full_tuple;
  	if (vy_point_lookup(it->lsm->pk, it->tx, vy_tx_read_view(it->tx),
-			    tuple, &full_tuple) != 0)
+			    tuple, ret) != 0)
  		goto fail;
-	if (full_tuple == NULL) {
+	if (*ret == NULL) {
  		/*
  		 * All indexes of a space must be consistent, i.e.
  		 * if a tuple is present in one index, it must be
@@ -3908,10 +3903,9 @@ next:
  			 vy_lsm_name(it->lsm), vy_stmt_str(tuple));
  		goto next;
  	}
-	*ret = tuple_bless(full_tuple);
-	tuple_unref(full_tuple);
-	if (*ret != NULL)
-		return 0;
+	tuple_bless(*ret);
+	tuple_unref(*ret);
+	return 0;
  fail:
  	vinyl_iterator_close(it);
  	return -1;
@@ -3997,16 +3991,12 @@ vinyl_index_get(struct index *index, const char *key,
  	const struct vy_read_view **rv = (tx != NULL ? vy_tx_read_view(tx) :
  					  &env->xm->p_global_read_view);
  
-	struct tuple *tuple;
-	if (vy_lsm_full_by_key(lsm, tx, rv, key, part_count, &tuple) != 0)
+	if (vy_lsm_full_by_key(lsm, tx, rv, key, part_count, ret) != 0)
  		return -1;
-
-	if (tuple != NULL) {
-		*ret = tuple_bless(tuple);
-		tuple_unref(tuple);
-		return *ret == NULL ? -1 : 0;
+	if (*ret != NULL) {
+		tuple_bless(*ret);
+		tuple_unref(*ret);
  	}
-	*ret = NULL;
  	return 0;
  }
  
diff --git a/test/box/misc.result b/test/box/misc.result
index 8f94f5513..f7703ba8d 100644
--- a/test/box/misc.result
+++ b/test/box/misc.result
@@ -332,7 +332,6 @@ t;
    - 'box.error.UNKNOWN_UPDATE_OP : 28'
    - 'box.error.WRONG_COLLATION_OPTIONS : 151'
    - 'box.error.CURSOR_NO_TRANSACTION : 80'
-  - 'box.error.TUPLE_REF_OVERFLOW : 86'
    - 'box.error.ALTER_SEQUENCE : 143'
    - 'box.error.INVALID_XLOG_NAME : 75'
    - 'box.error.SAVEPOINT_EMPTY_TX : 60'
@@ -360,7 +359,7 @@ t;
    - 'box.error.VINYL_MAX_TUPLE_SIZE : 139'
    - 'box.error.LOAD_FUNCTION : 99'
    - 'box.error.INVALID_XLOG : 74'
-  - 'box.error.PRIV_NOT_GRANTED : 91'
+  - 'box.error.READ_VIEW_ABORTED : 130'
    - 'box.error.TRANSACTION_CONFLICT : 97'
    - 'box.error.GUEST_USER_PASSWORD : 96'
    - 'box.error.PROC_C : 102'
@@ -405,7 +404,7 @@ t;
    - 'box.error.injection : table: <address>
    - 'box.error.NULLABLE_MISMATCH : 153'
    - 'box.error.LAST_DROP : 15'
-  - 'box.error.NO_SUCH_ROLE : 82'
+  - 'box.error.TUPLE_FORMAT_LIMIT : 16'
    - 'box.error.DECOMPRESSION : 124'
    - 'box.error.CREATE_SEQUENCE : 142'
    - 'box.error.CREATE_USER : 43'
@@ -414,66 +413,66 @@ t;
    - 'box.error.SEQUENCE_OVERFLOW : 147'
    - 'box.error.SYSTEM : 115'
    - 'box.error.KEY_PART_IS_TOO_LONG : 118'
-  - 'box.error.TUPLE_FORMAT_LIMIT : 16'
-  - 'box.error.BEFORE_REPLACE_RET : 53'
+  - 'box.error.INJECTION : 8'
+  - 'box.error.INVALID_MSGPACK : 20'
    - 'box.error.NO_SUCH_SAVEPOINT : 61'
    - 'box.error.TRUNCATE_SYSTEM_SPACE : 137'
    - 'box.error.VY_QUOTA_TIMEOUT : 135'
    - 'box.error.WRONG_INDEX_OPTIONS : 108'
    - 'box.error.INVALID_VYLOG_FILE : 133'
    - 'box.error.INDEX_FIELD_COUNT_LIMIT : 127'
-  - 'box.error.READ_VIEW_ABORTED : 130'
+  - 'box.error.PRIV_NOT_GRANTED : 91'
    - 'box.error.USER_MAX : 56'
-  - 'box.error.PROTOCOL : 104'
+  - 'box.error.BEFORE_REPLACE_RET : 53'
    - 'box.error.TUPLE_NOT_ARRAY : 22'
    - 'box.error.KEY_PART_COUNT : 31'
    - 'box.error.ALTER_SPACE : 12'
    - 'box.error.ACTIVE_TRANSACTION : 79'
    - 'box.error.EXACT_FIELD_COUNT : 38'
    - 'box.error.DROP_SEQUENCE : 144'
-  - 'box.error.INVALID_MSGPACK : 20'
    - 'box.error.MORE_THAN_ONE_TUPLE : 41'
-  - 'box.error.RTREE_RECT : 101'
-  - 'box.error.SUB_STMT_MAX : 121'
+  - 'box.error.UPSERT_UNIQUE_SECONDARY_KEY : 105'
    - 'box.error.UNKNOWN_REQUEST_TYPE : 48'
-  - 'box.error.SPACE_EXISTS : 10'
+  - 'box.error.SUB_STMT_MAX : 121'
    - 'box.error.PROC_LUA : 32'
+  - 'box.error.SPACE_EXISTS : 10'
    - 'box.error.ROLE_NOT_GRANTED : 92'
+  - 'box.error.UNSUPPORTED : 5'
    - 'box.error.NO_SUCH_SPACE : 36'
    - 'box.error.WRONG_INDEX_PARTS : 107'
-  - 'box.error.DROP_SPACE : 11'
    - 'box.error.MIN_FIELD_COUNT : 39'
    - 'box.error.REPLICASET_UUID_MISMATCH : 63'
    - 'box.error.UPDATE_FIELD : 29'
+  - 'box.error.INDEX_EXISTS : 85'
    - 'box.error.COMPRESSION : 119'
    - 'box.error.INVALID_ORDER : 68'
-  - 'box.error.INDEX_EXISTS : 85'
    - 'box.error.SPLICE : 25'
    - 'box.error.UNKNOWN : 0'
+  - 'box.error.IDENTIFIER : 70'
    - 'box.error.DROP_PRIMARY_KEY : 17'
    - 'box.error.NULLABLE_PRIMARY : 152'
    - 'box.error.NO_SUCH_SEQUENCE : 145'
    - 'box.error.RELOAD_CFG : 58'
    - 'box.error.INVALID_UUID : 64'
-  - 'box.error.INJECTION : 8'
+  - 'box.error.DROP_SPACE : 11'
    - 'box.error.TIMEOUT : 78'
-  - 'box.error.IDENTIFIER : 70'
    - 'box.error.ITERATOR_TYPE : 72'
    - 'box.error.REPLICA_MAX : 73'
+  - 'box.error.NO_SUCH_ROLE : 82'
    - 'box.error.MISSING_REQUEST_FIELD : 69'
    - 'box.error.MISSING_SNAPSHOT : 93'
    - 'box.error.WRONG_SPACE_OPTIONS : 111'
    - 'box.error.READONLY : 7'
-  - 'box.error.UNSUPPORTED : 5'
    - 'box.error.UPDATE_INTEGER_OVERFLOW : 95'
+  - 'box.error.RTREE_RECT : 101'
    - 'box.error.NO_CONNECTION : 77'
    - 'box.error.INVALID_XLOG_ORDER : 76'
-  - 'box.error.UPSERT_UNIQUE_SECONDARY_KEY : 105'
-  - 'box.error.ROLLBACK_IN_SUB_STMT : 123'
    - 'box.error.WRONG_SCHEMA_VERSION : 109'
-  - 'box.error.UNSUPPORTED_INDEX_FEATURE : 112'
-  - 'box.error.INDEX_PART_TYPE_MISMATCH : 24'
+  - 'box.error.ROLLBACK_IN_SUB_STMT : 123'
+  - 'box.error.PROTOCOL : 104'
    - 'box.error.INVALID_XLOG_TYPE : 125'
+  - 'box.error.INDEX_PART_TYPE_MISMATCH : 24'
+  - 'box.error.UNSUPPORTED_INDEX_FEATURE : 112'
  ...
  test_run:cmd("setopt delimiter ''");
  ---
diff --git a/test/box/select.result b/test/box/select.result
index 4aed70630..6e6ccade1 100644
--- a/test/box/select.result
+++ b/test/box/select.result
@@ -619,6 +619,11 @@ collectgarbage('collect')
  ---
  - 0
  ...
+-- gh-3224 resurrect tuple bigrefs
+collectgarbage('stop')
+---
+- 0
+...
  s = box.schema.space.create('select', { temporary = true })
  ---
  ...
@@ -628,22 +633,37 @@ index = s:create_index('primary', { type = 'tree' })
  a = s:insert{0}
  ---
  ...
-lots_of_links = {}
+lots_of_links = setmetatable({}, {__mode = 'v'})
+---
+...
+ref_count = 0
+---
+...
+while (ref_count < 100000) do table.insert(lots_of_links, s:get{0}) ref_count = ref_count + 1 end
  ---
  ...
+ref_count
+---
+- 100000
+...
  ref_count = 0
  ---
  ...
-while (true) do table.insert(lots_of_links, s:get{0}) ref_count = ref_count + 1 end
+for k, v in pairs(lots_of_links) do ref_count = ref_count + 1 end
  ---
-- error: Tuple reference counter overflow
  ...
  ref_count
  ---
-- 65531
+- 100000
+...
+-- check that tuples are deleted after gc is activated
+collectgarbage('collect')
+---
+- 0
  ...
-lots_of_links = {}
+lots_of_links
  ---
+- []
  ...
  s:drop()
  ---
diff --git a/test/box/select.test.lua b/test/box/select.test.lua
index 54c2ecc1c..f15c6e275 100644
--- a/test/box/select.test.lua
+++ b/test/box/select.test.lua
@@ -124,12 +124,21 @@ test.random(s.index[0], 48)
  s:drop()
  
  collectgarbage('collect')
+
+-- gh-3224 resurrect tuple bigrefs
+
+collectgarbage('stop')
  s = box.schema.space.create('select', { temporary = true })
  index = s:create_index('primary', { type = 'tree' })
  a = s:insert{0}
-lots_of_links = {}
+lots_of_links = setmetatable({}, {__mode = 'v'})
  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 = {}
+ref_count = 0
+for k, v in pairs(lots_of_links) do ref_count = ref_count + 1 end
+ref_count
+-- check that tuples are deleted after gc is activated
+collectgarbage('collect')
+lots_of_links
  s:drop()

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

[Vladislav Shpilevoy]

Sorry, Vladimir. Please, disregard it. I have found and fixed a crash.
Looks like Mergen must implement unit tests.

Test bigrefs via Lua is not possible because of its memory limitation.

Mergen, please, implement unit tests on C for your patch and for my
follow up. You must cover each branch in each new function.


On 04/06/2018 23:57, Vladislav Shpilevoy wrote:
> Thanks for the patch, Mergen! Please look at my 5 comments.
> 
> Vova, please, take a look on the patch. I have pasted it at the end
> of the letter.
> 
> On 04/06/2018 17:21, Imeev Mergen wrote:
>>
>>
>> On 06/04/2018 02:21 PM, Vladislav Shpilevoy wrote:
>>> Hello. Thanks for the patch! It is almost perfect! See 6 comments
>>> below.
>>>
>>> On 01/06/2018 18:41, imeevma@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
>>>>
>>
>> commit 7b7965f6c5462142a607d9db542d698fc94fbbbe
>> Author: Mergen Imeev <imeevma@gmail.com>
>> Date:   Mon May 28 19:17:51 2018 +0300
>>
>>      box: create bigrefs for tuples
>>
>>      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
>>
>> diff --git a/src/box/tuple.c b/src/box/tuple.c
>> index 014f374..6e63433 100644
>> --- a/src/box/tuple.c
>> +++ b/src/box/tuple.c
>> @@ -48,6 +48,26 @@ enum {
>>       OBJSIZE_MIN = 16,
>>   };
>>
>> +/**
>> + * Container for big reference counters. Contains array of big
>> + * reference counters, size of this array and number of non-zero
>> + * big reference counters. When reference counter of tuple becomes
>> + * more than 32767, field refs of this tuple becomes index of big
>> + * reference counter in big reference counter array and field
>> + * is_bigref is set true. The moment big reference becomes equal
>> + * 32767 it is set to 0, refs of the tuple becomes 32767 and
>> + * is_bigref becomes false. Big reference counter can be equal to
>> + * 0 or be more than 32767.
>> + */
>> +struct bigref_list {
>> +    /** Array of big reference counters */
>> +    uint32_t *refs;
>> +    /** Number of non-zero elements in the array */
>> +    uint16_t size;
>> +    /** Capacity of the array */
>> +    uint16_t capacity;
>> +};
> 
> 1. Instead of
> 
>      struct name {
>          ...
>      };
>      static struct name name;
> 
> you can do this
> 
>      static struct name {
>          ...
>      } name;
> 
>> +
>>   static const double ALLOC_FACTOR = 1.05;
>>
>>   /**
>> @@ -151,6 +177,15 @@ tuple_validate_raw(struct tuple_format *format, const char *tuple)
>>       return 0;
>>   }
>>
>> +/** Initialize big references container. */
>> +static inline void
>> +bigref_list_create()
>> +{
>> +    bigref_list.size = 0;
>> +    bigref_list.refs = NULL;
>> +    bigref_list.capacity = 0;
> 
> 2. Memset is faster than per-member resetting. We with
> Vladimir Davydov have benched it.
> 
>> +/**
>> + * Return index for new big reference counter and allocate memory
>> + * if needed.
>> + * @retval index for new big reference counter.
>> + */
>> +static inline uint16_t
>> +tuple_bigref_retrieve()
>> +{
>> +    if (bigref_list.size < bigref_list.capacity) {
>> +        uint16_t vacant_index = 0;
>> +        while (bigref_list.refs[vacant_index] != 0)
>> +            ++vacant_index;
>> +        return vacant_index;
>> +    }
>> +    /* Extend the array. */
>> +    uint16_t capacity = bigref_list.capacity;
>> +    if (capacity == 0) {
>> +        capacity = TUPLE_BIGREF_MIN_CAPACITY;
>> +    } else {
>> +        capacity *= TUPLE_BIGREF_FACTOR;
>> +        if (capacity >= TUPLE_BIGREF_MAX_CAPACITY)
> 
> 3. By such check you have limited the capacity with 16384 bigrefs instead of
> 32k. Capacity here is always a power of 2. TUPLE_BIGREF_MAX_CAPACITY is
> 2^15. So here after 2^14 you get overflow. 2^14 = 16384. I have fixed it on
> the branch.
> 
>> +            panic("Too many big references");
>> +    }
>> +    uint32_t *refs = (uint32_t *) realloc(bigref_list.refs, capacity *
>> +                          sizeof(*bigref_list.refs));
>> +    if (refs == NULL) {
>> +        panic("failed to reallocate %zu bytes: Cannot allocate"\
>> +              " memory.", capacity * sizeof(*bigref_list.refs));
>> +    }
>> +    bigref_list.refs = refs;
>> +    memset(bigref_list.refs + bigref_list.capacity, 0, capacity -
>> +           bigref_list.capacity);
>> +    bigref_list.capacity = capacity;
>> +    return bigref_list.size++;
>> +}
>> +
>> +/**
>> + * Try to decrease allocated memory if it is possible. Free memory
>> + * when size == 0.
>> + */
>> +static inline void
>> +bigref_list_compact()
>> +{
>> +    if (bigref_list.size == 0) {
>> +        bigref_list_destroy();
>> +        return;
>> +    }
>> +    if (bigref_list.capacity == TUPLE_BIGREF_MIN_CAPACITY ||
>> +        bigref_list.size > bigref_list.capacity / TUPLE_BIGREF_FACTOR)
>> +        return;
>> +    uint16_t capacity = bigref_list.capacity;
>> +    while (bigref_list.refs[capacity - 1] == 0)
>> +        capacity--;
>> +    if (capacity < TUPLE_BIGREF_MIN_CAPACITY)
>> +        capacity = TUPLE_BIGREF_MIN_CAPACITY;
>> +    if (capacity > bigref_list.capacity / TUPLE_BIGREF_FACTOR)
>> +        return;
>> +    /* Round up capacity to the next highest power of 2*/
>> +    capacity--;
>> +    capacity |= capacity >> 1;
>> +    capacity |= capacity >> 2;
>> +    capacity |= capacity >> 4;
>> +    capacity |= capacity >> 8;
>> +    capacity |= capacity >> 16;
> 
> 4. This is because blind copy and paste is bad. The algorithm implementation
> I provided to you was for 32 bit unsigned integers, but here you have 16 bits
> only, so capacity >> 16 is always 0.
> 
>> +    capacity++;
>> +    uint32_t *refs = (uint32_t *) realloc(bigref_list.refs, capacity *
>> +                          sizeof(*bigref_list.refs));
>> +    if (refs == NULL)
>> +        panic("failed to reallocate %zu bytes: Cannot allocate"\
>> +              " memory.", capacity * sizeof(*bigref_list.refs));
>> +    bigref_list.refs = refs;
>> +    bigref_list.capacity = capacity;
>> +}
>> +
> 
> 5. I have removed tuple_bless == NULL checks from all the code.
> 
> Here the patch:
> 
> ============================================================================
> 
> commit 9d82fa9f9ae24c7dc91cf9dd7a416ec533fb8147
> Author: Mergen Imeev <imeevma@gmail.com>
> Date:   Mon May 28 19:17:51 2018 +0300
> 
>      box: create bigrefs for tuples
>      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
> 
> diff --git a/src/box/box.cc b/src/box/box.cc
> index c728a4c53..42578613d 100644
> --- a/src/box/box.cc
> +++ b/src/box/box.cc
> @@ -174,20 +174,22 @@ process_rw(struct request *request, struct space *space, struct tuple **result)
>           txn_rollback_stmt();
>           return -1;
>       }
> +    if (result == NULL)
> +        return txn_commit_stmt(txn, request);
> +    *result = tuple;
> +    if (tuple == NULL)
> +        return txn_commit_stmt(txn, request);
>       /*
>        * Pin the tuple locally before the commit,
>        * otherwise it may go away during yield in
>        * when WAL is written in autocommit mode.
>        */
> -    TupleRefNil ref(tuple);
> -    if (txn_commit_stmt(txn, request) != 0)
> -        return -1;
> -    if (result != NULL) {
> -        if (tuple != NULL && tuple_bless(tuple) == NULL)
> -            return -1;
> -        *result = tuple;
> -    }
> -    return 0;
> +    tuple_ref(tuple);
> +    int rc = txn_commit_stmt(txn, request);
> +    if (rc == 0)
> +        tuple_bless(tuple);
> +    tuple_unref(tuple);
> +    return rc;
>   }
> 
>   void
> diff --git a/src/box/errcode.h b/src/box/errcode.h
> index a0759f8f4..e009524ad 100644
> --- a/src/box/errcode.h
> +++ b/src/box/errcode.h
> @@ -138,7 +138,7 @@ struct errcode_record {
>       /* 83 */_(ER_ROLE_EXISTS,        "Role '%s' already exists") \
>       /* 84 */_(ER_CREATE_ROLE,        "Failed to create role '%s': %s") \
>       /* 85 */_(ER_INDEX_EXISTS,        "Index '%s' already exists") \
> -    /* 86 */_(ER_TUPLE_REF_OVERFLOW,    "Tuple reference counter overflow") \
> +    /* 86 */_(ER_UNUSED6,            "") \
>       /* 87 */_(ER_ROLE_LOOP,            "Granting role '%s' to role '%s' would create a loop") \
>       /* 88 */_(ER_GRANT,            "Incorrect grant arguments: %s") \
>       /* 89 */_(ER_PRIV_GRANTED,        "User '%s' already has %s access on %s '%s'") \
> diff --git a/src/box/index.cc b/src/box/index.cc
> index 3c62ec1cc..f992bc94c 100644
> --- a/src/box/index.cc
> +++ b/src/box/index.cc
> @@ -220,8 +220,8 @@ box_index_random(uint32_t space_id, uint32_t index_id, uint32_t rnd,
>       /* No tx management, random() is for approximation anyway. */
>       if (index_random(index, rnd, result) != 0)
>           return -1;
> -    if (*result != NULL && tuple_bless(*result) == NULL)
> -        return -1;
> +    if (*result != NULL)
> +        tuple_bless(*result);
>       return 0;
>   }
> 
> @@ -253,8 +253,8 @@ box_index_get(uint32_t space_id, uint32_t index_id, const char *key,
>       txn_commit_ro_stmt(txn);
>       /* Count statistics. */
>       rmean_collect(rmean_box, IPROTO_SELECT, 1);
> -    if (*result != NULL && tuple_bless(*result) == NULL)
> -        return -1;
> +    if (*result != NULL)
> +        tuple_bless(*result);
>       return 0;
>   }
> 
> @@ -285,8 +285,8 @@ box_index_min(uint32_t space_id, uint32_t index_id, const char *key,
>           return -1;
>       }
>       txn_commit_ro_stmt(txn);
> -    if (*result != NULL && tuple_bless(*result) == NULL)
> -        return -1;
> +    if (*result != NULL)
> +        tuple_bless(*result);
>       return 0;
>   }
> 
> @@ -317,8 +317,8 @@ box_index_max(uint32_t space_id, uint32_t index_id, const char *key,
>           return -1;
>       }
>       txn_commit_ro_stmt(txn);
> -    if (*result != NULL && tuple_bless(*result) == NULL)
> -        return -1;
> +    if (*result != NULL)
> +        tuple_bless(*result);
>       return 0;
>   }
> 
> @@ -397,8 +397,8 @@ box_iterator_next(box_iterator_t *itr, box_tuple_t **result)
>       assert(result != NULL);
>       if (iterator_next(itr, result) != 0)
>           return -1;
> -    if (*result != NULL && tuple_bless(*result) == NULL)
> -        return -1;
> +    if (*result != NULL)
> +        tuple_bless(*result);
>       return 0;
>   }
> 
> diff --git a/src/box/lua/tuple.c b/src/box/lua/tuple.c
> index 80573313d..22fe69611 100644
> --- a/src/box/lua/tuple.c
> +++ b/src/box/lua/tuple.c
> @@ -496,10 +496,7 @@ luaT_pushtuple(struct lua_State *L, box_tuple_t *tuple)
>           luaL_pushcdata(L, CTID_CONST_STRUCT_TUPLE_REF);
>       *ptr = tuple;
>       /* The order is important - first reference tuple, next set gc */
> -    if (box_tuple_ref(tuple) != 0) {
> -        luaT_error(L);
> -        return;
> -    }
> +    box_tuple_ref(tuple);
>       lua_pushcfunction(L, lbox_tuple_gc);
>       luaL_setcdatagc(L, -2);
>   }
> diff --git a/src/box/port.c b/src/box/port.c
> index 03f6be79d..9b6b8580c 100644
> --- a/src/box/port.c
> +++ b/src/box/port.c
> @@ -45,8 +45,7 @@ port_tuple_add(struct port *base, struct tuple *tuple)
>       struct port_tuple *port = port_tuple(base);
>       struct port_tuple_entry *e;
>       if (port->size == 0) {
> -        if (tuple_ref(tuple) != 0)
> -            return -1;
> +        tuple_ref(tuple);
>           e = &port->first_entry;
>           port->first = port->last = e;
>       } else {
> @@ -55,10 +54,7 @@ port_tuple_add(struct port *base, struct tuple *tuple)
>               diag_set(OutOfMemory, sizeof(*e), "mempool_alloc", "e");
>               return -1;
>           }
> -        if (tuple_ref(tuple) != 0) {
> -            mempool_free(&port_tuple_entry_pool, e);
> -            return -1;
> -        }
> +        tuple_ref(tuple);
>           port->last->next = e;
>           port->last = e;
>       }
> diff --git a/src/box/tuple.c b/src/box/tuple.c
> index 014f37406..5fc1c1283 100644
> --- a/src/box/tuple.c
> +++ b/src/box/tuple.c
> @@ -48,6 +48,26 @@ enum {
>       OBJSIZE_MIN = 16,
>   };
> 
> +/**
> + * Container for big reference counters. Contains array of big
> + * reference counters, size of this array and number of non-zero
> + * big reference counters. When reference counter of tuple becomes
> + * more than 32767, field refs of this tuple becomes index of big
> + * reference counter in big reference counter array and field
> + * is_bigref is set true. The moment big reference becomes equal
> + * 32767 it is set to 0, refs of the tuple becomes 32767 and
> + * is_bigref becomes false. Big reference counter can be equal to
> + * 0 or be more than 32767.
> + */
> +static struct bigref_list {
> +    /** Array of big reference counters. */
> +    uint32_t *refs;
> +    /** Number of non-zero elements in the array. */
> +    uint16_t size;
> +    /** Capacity of the array. */
> +    uint16_t capacity;
> +} bigref_list;
> +
>   static const double ALLOC_FACTOR = 1.05;
> 
>   /**
> @@ -151,6 +171,13 @@ tuple_validate_raw(struct tuple_format *format, const char *tuple)
>       return 0;
>   }
> 
> +/** Initialize big references container. */
> +static inline void
> +bigref_list_create()
> +{
> +    memset(&bigref_list, 0, sizeof(bigref_list));
> +}
> +
>   /**
>    * Incremented on every snapshot and is used to distinguish tuples
>    * which were created after start of a snapshot (these tuples can
> @@ -211,6 +238,8 @@ tuple_init(field_name_hash_f hash)
> 
>       box_tuple_last = NULL;
> 
> +    bigref_list_create();
> +
>       if (coll_id_cache_init() != 0)
>           return -1;
> 
> @@ -244,6 +273,131 @@ tuple_arena_create(struct slab_arena *arena, struct quota *quota,
>       }
>   }
> 
> +enum {
> +    BIGREF_FACTOR = 2,
> +    BIGREF_MAX = UINT32_MAX,
> +    BIGREF_MIN_CAPACITY = 16,
> +    /**
> +     * Only 15 bits are available for bigref list index in
> +     * struct tuple.
> +     */
> +    BIGREF_MAX_CAPACITY = UINT16_MAX >> 1
> +};
> +
> +/** Destroy big references and free memory that was allocated. */
> +static inline void
> +bigref_list_destroy()
> +{
> +    free(bigref_list.refs);
> +    bigref_list_create();
> +}
> +
> +/**
> + * Return index for new big reference counter and allocate memory
> + * if needed.
> + * @retval index for new big reference counter.
> + */
> +static inline uint16_t
> +bigref_list_new_index()
> +{
> +    if (bigref_list.size < bigref_list.capacity) {
> +        uint16_t vacant_index = 0;
> +        while (bigref_list.refs[vacant_index] != 0)
> +            ++vacant_index;
> +        return vacant_index;
> +    }
> +    /* Extend the array. */
> +    uint16_t capacity = bigref_list.capacity;
> +    if (capacity == 0)
> +        capacity = BIGREF_MIN_CAPACITY;
> +    else if (capacity < BIGREF_MAX_CAPACITY)
> +        capacity = MIN(capacity * BIGREF_FACTOR, BIGREF_MAX_CAPACITY);
> +    else
> +        panic("Too many big references");
> +    uint32_t *refs = (uint32_t *) realloc(bigref_list.refs, capacity *
> +                          sizeof(*bigref_list.refs));
> +    if (refs == NULL) {
> +        panic("failed to reallocate %zu bytes: Cannot allocate "\
> +              "memory.", capacity * sizeof(*bigref_list.refs));
> +    }
> +    bigref_list.refs = refs;
> +    memset(bigref_list.refs + bigref_list.capacity, 0, capacity -
> +           bigref_list.capacity);
> +    bigref_list.capacity = capacity;
> +    return bigref_list.size++;
> +}
> +
> +void
> +tuple_ref_slow(struct tuple *tuple)
> +{
> +    assert(tuple->is_bigref || tuple->refs == TUPLE_REF_MAX);
> +    if (! tuple->is_bigref) {
> +        tuple->ref_index = bigref_list_new_index();
> +        tuple->is_bigref = true;
> +        bigref_list.refs[tuple->ref_index] = TUPLE_REF_MAX;
> +    } else if (bigref_list.refs[tuple->ref_index] == BIGREF_MAX) {
> +        panic("Tuple big reference counter overflow");
> +    }
> +    bigref_list.refs[tuple->ref_index]++;
> +}
> +
> +/**
> + * Try to decrease allocated memory if it is possible. Free memory
> + * when size == 0.
> + */
> +static inline void
> +bigref_list_delete_index(uint16_t index)
> +{
> +    bigref_list.refs[index] = 0;
> +    if (--bigref_list.size == 0) {
> +        bigref_list_destroy();
> +        return;
> +    }
> +    if (bigref_list.capacity == BIGREF_MIN_CAPACITY ||
> +        bigref_list.size > bigref_list.capacity / BIGREF_FACTOR)
> +        return;
> +
> +    uint16_t top_index = bigref_list.capacity - 1;
> +    while (bigref_list.refs[top_index] == 0)
> +        top_index--;
> +
> +    uint16_t needed_capacity = top_index + 1;
> +    if (needed_capacity < BIGREF_MIN_CAPACITY)
> +        needed_capacity = BIGREF_MIN_CAPACITY;
> +    if (needed_capacity > bigref_list.capacity / BIGREF_FACTOR)
> +        return;
> +    /* Round up capacity to the next highest power of 2. */
> +    assert(sizeof(needed_capacity) == sizeof(uint16_t));
> +    needed_capacity--;
> +    needed_capacity |= needed_capacity >> 1;
> +    needed_capacity |= needed_capacity >> 2;
> +    needed_capacity |= needed_capacity >> 4;
> +    needed_capacity |= needed_capacity >> 8;
> +    assert(needed_capacity < UINT16_MAX);
> +    needed_capacity++;
> +    uint32_t *refs =
> +        (uint32_t *) realloc(bigref_list.refs, needed_capacity *
> +                     sizeof(*bigref_list.refs));
> +    if (refs == NULL) {
> +        panic("failed to reallocate %zu bytes: Cannot allocate "\
> +              "memory.", needed_capacity * sizeof(*bigref_list.refs));
> +    }
> +    bigref_list.refs = refs;
> +    bigref_list.capacity = needed_capacity;
> +}
> +
> +void
> +tuple_unref_slow(struct tuple *tuple)
> +{
> +    assert(tuple->is_bigref &&
> +           bigref_list.refs[tuple->ref_index] > TUPLE_REF_MAX);
> +    if(--bigref_list.refs[tuple->ref_index] == TUPLE_REF_MAX) {
> +        bigref_list_delete_index(tuple->ref_index);
> +        tuple->ref_index = TUPLE_REF_MAX;
> +        tuple->is_bigref = false;
> +    }
> +}
> +
>   void
>   tuple_arena_destroy(struct slab_arena *arena)
>   {
> @@ -265,6 +419,8 @@ tuple_free(void)
>       tuple_format_free();
> 
>       coll_id_cache_destroy();
> +
> +    bigref_list_destroy();
>   }
> 
>   box_tuple_format_t *
> @@ -288,7 +444,8 @@ int
>   box_tuple_ref(box_tuple_t *tuple)
>   {
>       assert(tuple != NULL);
> -    return tuple_ref(tuple);
> +    tuple_ref(tuple);
> +    return 0;
>   }
> 
>   void
> @@ -357,10 +514,7 @@ box_tuple_iterator(box_tuple_t *tuple)
>                "mempool", "new slab");
>           return NULL;
>       }
> -    if (tuple_ref(tuple) != 0) {
> -        mempool_free(&tuple_iterator_pool, it);
> -        return NULL;
> -    }
> +    tuple_ref(tuple);
>       tuple_rewind(it, tuple);
>       return it;
>   }
> @@ -451,7 +605,6 @@ box_tuple_new(box_tuple_format_t *format, const char *data, const char *end)
>       struct tuple *ret = tuple_new(format, data, end);
>       if (ret == NULL)
>           return NULL;
> -    /* Can't fail on zero refs. */
>       return tuple_bless(ret);
>   }
> 
> diff --git a/src/box/tuple.h b/src/box/tuple.h
> index e2384dda0..14dbd4094 100644
> --- a/src/box/tuple.h
> +++ b/src/box/tuple.h
> @@ -105,8 +105,7 @@ typedef struct tuple box_tuple_t;
>    * tuple will leak.
>    *
>    * \param tuple a tuple
> - * \retval -1 on error (check box_error_last())
> - * \retval 0 on success
> + * \retval 0 always
>    * \sa box_tuple_unref()
>    */
>   int
> @@ -269,8 +268,7 @@ box_tuple_next(box_tuple_iterator_t *it);
>    * Use box_tuple_format_default() to create space-independent tuple.
>    * \param data tuple data in MsgPack Array format ([field1, field2, ...]).
>    * \param end the end of \a data
> - * \retval NULL on out of memory
> - * \retval tuple otherwise
> + * \retval tuple
>    * \pre data, end is valid MsgPack Array
>    * \sa \code box.tuple.new(data) \endcode
>    */
> @@ -307,9 +305,17 @@ box_tuple_upsert(const box_tuple_t *tuple, const char *expr, const
>    */
>   struct PACKED tuple
>   {
> -    /** reference counter */
> -    uint16_t refs;
> -    /** format identifier */
> +    union {
> +        /** Reference counter. */
> +        uint16_t refs;
> +        struct {
> +            /** Index of big reference counter. */
> +            uint16_t ref_index : 15;
> +            /** Big reference flag. */
> +            bool is_bigref : 1;
> +        };
> +    };
> +    /** Format identifier. */
>       uint16_t format_id;
>       /**
>        * Length of the MessagePack data in raw part of the
> @@ -774,25 +780,35 @@ 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 (unlikely(tuple->refs >= TUPLE_REF_MAX))
> +        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.
>    *
> @@ -802,10 +818,9 @@ static inline void
>   tuple_unref(struct tuple *tuple)
>   {
>       assert(tuple->refs - 1 >= 0);
> -
> -    tuple->refs--;
> -
> -    if (tuple->refs == 0)
> +    if (unlikely(tuple->is_bigref))
> +        tuple_unref_slow(tuple);
> +    else if (--tuple->refs == 0)
>           tuple_delete(tuple);
>   }
> 
> @@ -813,25 +828,18 @@ 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 */
> +        tuple_unref(box_tuple_last);
>       /* Remember current tuple */
>       box_tuple_last = tuple;
>       return tuple;
> @@ -849,41 +857,6 @@ tuple_to_buf(const struct tuple *tuple, char *buf, size_t size);
>   #include "tuple_update.h"
>   #include "errinj.h"
> 
> -/**
> - * \copydoc tuple_ref()
> - * \throws if overflow detected.
> - */
> -static inline void
> -tuple_ref_xc(struct tuple *tuple)
> -{
> -    if (tuple_ref(tuple))
> -        diag_raise();
> -}
> -
> -/**
> - * \copydoc tuple_bless
> - * \throw ER_TUPLE_REF_OVERFLOW
> - */
> -static inline box_tuple_t *
> -tuple_bless_xc(struct tuple *tuple)
> -{
> -    box_tuple_t *blessed = tuple_bless(tuple);
> -    if (blessed == NULL)
> -        diag_raise();
> -    return blessed;
> -}
> -
> -/** Make tuple references exception-friendly in absence of @finally. */
> -struct TupleRefNil {
> -    struct tuple *tuple;
> -    TupleRefNil (struct tuple *arg) :tuple(arg)
> -    { if (tuple) tuple_ref_xc(tuple); }
> -    ~TupleRefNil() { if (tuple) tuple_unref(tuple); }
> -
> -    TupleRefNil(const TupleRefNil&) = delete;
> -    void operator=(const TupleRefNil&) = delete;
> -};
> -
>   /* @copydoc tuple_field_with_type() */
>   static inline const char *
>   tuple_field_with_type_xc(const struct tuple *tuple, uint32_t fieldno,
> diff --git a/src/box/vinyl.c b/src/box/vinyl.c
> index f0d26874e..dc0d02054 100644
> --- a/src/box/vinyl.c
> +++ b/src/box/vinyl.c
> @@ -3822,7 +3822,6 @@ vinyl_iterator_primary_next(struct iterator *base, struct tuple **ret)
>       assert(base->next = vinyl_iterator_primary_next);
>       struct vinyl_iterator *it = (struct vinyl_iterator *)base;
>       assert(it->lsm->index_id == 0);
> -    struct tuple *tuple;
> 
>       if (it->tx == NULL) {
>           diag_set(ClientError, ER_CURSOR_NO_TRANSACTION);
> @@ -3833,18 +3832,15 @@ vinyl_iterator_primary_next(struct iterator *base, struct tuple **ret)
>           goto fail;
>       }
> 
> -    if (vy_read_iterator_next(&it->iterator, &tuple) != 0)
> +    if (vy_read_iterator_next(&it->iterator, ret) != 0)
>           goto fail;
> -
> -    if (tuple == NULL) {
> +    if (*ret == NULL) {
>           /* EOF. Close the iterator immediately. */
>           vinyl_iterator_close(it);
> -        *ret = NULL;
> -        return 0;
> +    } else {
> +        tuple_bless(*ret);
>       }
> -    *ret = tuple_bless(tuple);
> -    if (*ret != NULL)
> -        return 0;
> +    return 0;
>   fail:
>       vinyl_iterator_close(it);
>       return -1;
> @@ -3890,11 +3886,10 @@ next:
>        * Note, there's no need in vy_tx_track() as the
>        * tuple is already tracked in the secondary index.
>        */
> -    struct tuple *full_tuple;
>       if (vy_point_lookup(it->lsm->pk, it->tx, vy_tx_read_view(it->tx),
> -                tuple, &full_tuple) != 0)
> +                tuple, ret) != 0)
>           goto fail;
> -    if (full_tuple == NULL) {
> +    if (*ret == NULL) {
>           /*
>            * All indexes of a space must be consistent, i.e.
>            * if a tuple is present in one index, it must be
> @@ -3908,10 +3903,9 @@ next:
>                vy_lsm_name(it->lsm), vy_stmt_str(tuple));
>           goto next;
>       }
> -    *ret = tuple_bless(full_tuple);
> -    tuple_unref(full_tuple);
> -    if (*ret != NULL)
> -        return 0;
> +    tuple_bless(*ret);
> +    tuple_unref(*ret);
> +    return 0;
>   fail:
>       vinyl_iterator_close(it);
>       return -1;
> @@ -3997,16 +3991,12 @@ vinyl_index_get(struct index *index, const char *key,
>       const struct vy_read_view **rv = (tx != NULL ? vy_tx_read_view(tx) :
>                         &env->xm->p_global_read_view);
> 
> -    struct tuple *tuple;
> -    if (vy_lsm_full_by_key(lsm, tx, rv, key, part_count, &tuple) != 0)
> +    if (vy_lsm_full_by_key(lsm, tx, rv, key, part_count, ret) != 0)
>           return -1;
> -
> -    if (tuple != NULL) {
> -        *ret = tuple_bless(tuple);
> -        tuple_unref(tuple);
> -        return *ret == NULL ? -1 : 0;
> +    if (*ret != NULL) {
> +        tuple_bless(*ret);
> +        tuple_unref(*ret);
>       }
> -    *ret = NULL;
>       return 0;
>   }
> 
> diff --git a/test/box/misc.result b/test/box/misc.result
> index 8f94f5513..f7703ba8d 100644
> --- a/test/box/misc.result
> +++ b/test/box/misc.result
> @@ -332,7 +332,6 @@ t;
>     - 'box.error.UNKNOWN_UPDATE_OP : 28'
>     - 'box.error.WRONG_COLLATION_OPTIONS : 151'
>     - 'box.error.CURSOR_NO_TRANSACTION : 80'
> -  - 'box.error.TUPLE_REF_OVERFLOW : 86'
>     - 'box.error.ALTER_SEQUENCE : 143'
>     - 'box.error.INVALID_XLOG_NAME : 75'
>     - 'box.error.SAVEPOINT_EMPTY_TX : 60'
> @@ -360,7 +359,7 @@ t;
>     - 'box.error.VINYL_MAX_TUPLE_SIZE : 139'
>     - 'box.error.LOAD_FUNCTION : 99'
>     - 'box.error.INVALID_XLOG : 74'
> -  - 'box.error.PRIV_NOT_GRANTED : 91'
> +  - 'box.error.READ_VIEW_ABORTED : 130'
>     - 'box.error.TRANSACTION_CONFLICT : 97'
>     - 'box.error.GUEST_USER_PASSWORD : 96'
>     - 'box.error.PROC_C : 102'
> @@ -405,7 +404,7 @@ t;
>     - 'box.error.injection : table: <address>
>     - 'box.error.NULLABLE_MISMATCH : 153'
>     - 'box.error.LAST_DROP : 15'
> -  - 'box.error.NO_SUCH_ROLE : 82'
> +  - 'box.error.TUPLE_FORMAT_LIMIT : 16'
>     - 'box.error.DECOMPRESSION : 124'
>     - 'box.error.CREATE_SEQUENCE : 142'
>     - 'box.error.CREATE_USER : 43'
> @@ -414,66 +413,66 @@ t;
>     - 'box.error.SEQUENCE_OVERFLOW : 147'
>     - 'box.error.SYSTEM : 115'
>     - 'box.error.KEY_PART_IS_TOO_LONG : 118'
> -  - 'box.error.TUPLE_FORMAT_LIMIT : 16'
> -  - 'box.error.BEFORE_REPLACE_RET : 53'
> +  - 'box.error.INJECTION : 8'
> +  - 'box.error.INVALID_MSGPACK : 20'
>     - 'box.error.NO_SUCH_SAVEPOINT : 61'
>     - 'box.error.TRUNCATE_SYSTEM_SPACE : 137'
>     - 'box.error.VY_QUOTA_TIMEOUT : 135'
>     - 'box.error.WRONG_INDEX_OPTIONS : 108'
>     - 'box.error.INVALID_VYLOG_FILE : 133'
>     - 'box.error.INDEX_FIELD_COUNT_LIMIT : 127'
> -  - 'box.error.READ_VIEW_ABORTED : 130'
> +  - 'box.error.PRIV_NOT_GRANTED : 91'
>     - 'box.error.USER_MAX : 56'
> -  - 'box.error.PROTOCOL : 104'
> +  - 'box.error.BEFORE_REPLACE_RET : 53'
>     - 'box.error.TUPLE_NOT_ARRAY : 22'
>     - 'box.error.KEY_PART_COUNT : 31'
>     - 'box.error.ALTER_SPACE : 12'
>     - 'box.error.ACTIVE_TRANSACTION : 79'
>     - 'box.error.EXACT_FIELD_COUNT : 38'
>     - 'box.error.DROP_SEQUENCE : 144'
> -  - 'box.error.INVALID_MSGPACK : 20'
>     - 'box.error.MORE_THAN_ONE_TUPLE : 41'
> -  - 'box.error.RTREE_RECT : 101'
> -  - 'box.error.SUB_STMT_MAX : 121'
> +  - 'box.error.UPSERT_UNIQUE_SECONDARY_KEY : 105'
>     - 'box.error.UNKNOWN_REQUEST_TYPE : 48'
> -  - 'box.error.SPACE_EXISTS : 10'
> +  - 'box.error.SUB_STMT_MAX : 121'
>     - 'box.error.PROC_LUA : 32'
> +  - 'box.error.SPACE_EXISTS : 10'
>     - 'box.error.ROLE_NOT_GRANTED : 92'
> +  - 'box.error.UNSUPPORTED : 5'
>     - 'box.error.NO_SUCH_SPACE : 36'
>     - 'box.error.WRONG_INDEX_PARTS : 107'
> -  - 'box.error.DROP_SPACE : 11'
>     - 'box.error.MIN_FIELD_COUNT : 39'
>     - 'box.error.REPLICASET_UUID_MISMATCH : 63'
>     - 'box.error.UPDATE_FIELD : 29'
> +  - 'box.error.INDEX_EXISTS : 85'
>     - 'box.error.COMPRESSION : 119'
>     - 'box.error.INVALID_ORDER : 68'
> -  - 'box.error.INDEX_EXISTS : 85'
>     - 'box.error.SPLICE : 25'
>     - 'box.error.UNKNOWN : 0'
> +  - 'box.error.IDENTIFIER : 70'
>     - 'box.error.DROP_PRIMARY_KEY : 17'
>     - 'box.error.NULLABLE_PRIMARY : 152'
>     - 'box.error.NO_SUCH_SEQUENCE : 145'
>     - 'box.error.RELOAD_CFG : 58'
>     - 'box.error.INVALID_UUID : 64'
> -  - 'box.error.INJECTION : 8'
> +  - 'box.error.DROP_SPACE : 11'
>     - 'box.error.TIMEOUT : 78'
> -  - 'box.error.IDENTIFIER : 70'
>     - 'box.error.ITERATOR_TYPE : 72'
>     - 'box.error.REPLICA_MAX : 73'
> +  - 'box.error.NO_SUCH_ROLE : 82'
>     - 'box.error.MISSING_REQUEST_FIELD : 69'
>     - 'box.error.MISSING_SNAPSHOT : 93'
>     - 'box.error.WRONG_SPACE_OPTIONS : 111'
>     - 'box.error.READONLY : 7'
> -  - 'box.error.UNSUPPORTED : 5'
>     - 'box.error.UPDATE_INTEGER_OVERFLOW : 95'
> +  - 'box.error.RTREE_RECT : 101'
>     - 'box.error.NO_CONNECTION : 77'
>     - 'box.error.INVALID_XLOG_ORDER : 76'
> -  - 'box.error.UPSERT_UNIQUE_SECONDARY_KEY : 105'
> -  - 'box.error.ROLLBACK_IN_SUB_STMT : 123'
>     - 'box.error.WRONG_SCHEMA_VERSION : 109'
> -  - 'box.error.UNSUPPORTED_INDEX_FEATURE : 112'
> -  - 'box.error.INDEX_PART_TYPE_MISMATCH : 24'
> +  - 'box.error.ROLLBACK_IN_SUB_STMT : 123'
> +  - 'box.error.PROTOCOL : 104'
>     - 'box.error.INVALID_XLOG_TYPE : 125'
> +  - 'box.error.INDEX_PART_TYPE_MISMATCH : 24'
> +  - 'box.error.UNSUPPORTED_INDEX_FEATURE : 112'
>   ...
>   test_run:cmd("setopt delimiter ''");
>   ---
> diff --git a/test/box/select.result b/test/box/select.result
> index 4aed70630..6e6ccade1 100644
> --- a/test/box/select.result
> +++ b/test/box/select.result
> @@ -619,6 +619,11 @@ collectgarbage('collect')
>   ---
>   - 0
>   ...
> +-- gh-3224 resurrect tuple bigrefs
> +collectgarbage('stop')
> +---
> +- 0
> +...
>   s = box.schema.space.create('select', { temporary = true })
>   ---
>   ...
> @@ -628,22 +633,37 @@ index = s:create_index('primary', { type = 'tree' })
>   a = s:insert{0}
>   ---
>   ...
> -lots_of_links = {}
> +lots_of_links = setmetatable({}, {__mode = 'v'})
> +---
> +...
> +ref_count = 0
> +---
> +...
> +while (ref_count < 100000) do table.insert(lots_of_links, s:get{0}) ref_count = ref_count + 1 end
>   ---
>   ...
> +ref_count
> +---
> +- 100000
> +...
>   ref_count = 0
>   ---
>   ...
> -while (true) do table.insert(lots_of_links, s:get{0}) ref_count = ref_count + 1 end
> +for k, v in pairs(lots_of_links) do ref_count = ref_count + 1 end
>   ---
> -- error: Tuple reference counter overflow
>   ...
>   ref_count
>   ---
> -- 65531
> +- 100000
> +...
> +-- check that tuples are deleted after gc is activated
> +collectgarbage('collect')
> +---
> +- 0
>   ...
> -lots_of_links = {}
> +lots_of_links
>   ---
> +- []
>   ...
>   s:drop()
>   ---
> diff --git a/test/box/select.test.lua b/test/box/select.test.lua
> index 54c2ecc1c..f15c6e275 100644
> --- a/test/box/select.test.lua
> +++ b/test/box/select.test.lua
> @@ -124,12 +124,21 @@ test.random(s.index[0], 48)
>   s:drop()
> 
>   collectgarbage('collect')
> +
> +-- gh-3224 resurrect tuple bigrefs
> +
> +collectgarbage('stop')
>   s = box.schema.space.create('select', { temporary = true })
>   index = s:create_index('primary', { type = 'tree' })
>   a = s:insert{0}
> -lots_of_links = {}
> +lots_of_links = setmetatable({}, {__mode = 'v'})
>   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 = {}
> +ref_count = 0
> +for k, v in pairs(lots_of_links) do ref_count = ref_count + 1 end
> +ref_count
> +-- check that tuples are deleted after gc is activated
> +collectgarbage('collect')
> +lots_of_links
>   s:drop()
> 
> 

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

[Konstantin Osipov]

* Vladislav Shpilevoy <v.shpilevoy@tarantool.org> [18/06/05 00:21]:
> Sorry, Vladimir. Please, disregard it. I have found and fixed a crash.
> Looks like Mergen must implement unit tests.

Just sent my email and read this one :)


-- 
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov

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

[Konstantin Osipov]

* Vladislav Shpilevoy <v.shpilevoy@tarantool.org> [18/06/05 00:01]:
> > +/** Initialize big references container. */
> > +static inline void
> > +bigref_list_create()
> > +{
> > +    bigref_list.size = 0;
> > +    bigref_list.refs = NULL;
> > +    bigref_list.capacity = 0;
> 
> 2. Memset is faster than per-member resetting. We with
> Vladimir Davydov have benched it.

This code runs only once at program startup. Please do not apply
memset() optimization to it.

I have been using memset() myself for things I have seen take a
lot of CPU time with a profiler and  on a very common workload. 

Thanks,

-- 
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov

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

[Konstantin Osipov]

* Vladislav Shpilevoy <v.shpilevoy@tarantool.org> [18/06/05 00:01]:
> +static inline void
> +bigref_list_delete_index(uint16_t index)
> +{
> +	bigref_list.refs[index] = 0;
> +	if (--bigref_list.size == 0) {
> +		bigref_list_destroy();
> +		return;
> +	}
> +	if (bigref_list.capacity == BIGREF_MIN_CAPACITY ||
> +	    bigref_list.size > bigref_list.capacity / BIGREF_FACTOR)
> +		return;
> +
> +	uint16_t top_index = bigref_list.capacity - 1;
> +	while (bigref_list.refs[top_index] == 0)
> +		top_index--;
> +
> +	uint16_t needed_capacity = top_index + 1;
> +	if (needed_capacity < BIGREF_MIN_CAPACITY)
> +		needed_capacity = BIGREF_MIN_CAPACITY;
> +	if (needed_capacity > bigref_list.capacity / BIGREF_FACTOR)
> +		return;
> +	/* Round up capacity to the next highest power of 2. */
> +	assert(sizeof(needed_capacity) == sizeof(uint16_t));
> +	needed_capacity--;
> +	needed_capacity |= needed_capacity >> 1;
> +	needed_capacity |= needed_capacity >> 2;
> +	needed_capacity |= needed_capacity >> 4;
> +	needed_capacity |= needed_capacity >> 8;
> +	assert(needed_capacity < UINT16_MAX);
> +	needed_capacity++;

This is perhaps a very elegant piece of code, but it 
has no test. And a functional test for it would be difficult.
Could you please write a unit test?

-- 
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov

[tarantool-patches] [PATCH v2 2/1] tuple: introduce bigref hints

[Vladislav Shpilevoy]

commit 3237caac5f436dab34dddabb53cd9b6c4ed8fa0b
Author: Vladislav Shpilevoy <v.shpilevoy@tarantool.org>
Date:   Mon Jun 4 23:27:54 2018 +0300

     tuple: introduce bigref hints
     
     Typical usage of bigrefs: allocate many bigrefs in Lua in a row,
     reach memory threshold and delete many bigrefs in a row.
     
     Hits allow to make multiple refs deletions or creations be
     faster. For example, before the patch complexity of N refs with
     C capacity in a row: O(C) * N.
     After the patch:     O(C) + N.
     
     Same about unrefs.
     
     Follow up #3224

diff --git a/src/box/tuple.c b/src/box/tuple.c
index 5fc1c1283..a030b6eb8 100644
--- a/src/box/tuple.c
+++ b/src/box/tuple.c
@@ -66,6 +66,14 @@ static struct bigref_list {
  	uint16_t size;
  	/** Capacity of the array. */
  	uint16_t capacity;
+	/**
+	 * On next bigref index retrieval start from this index.
+	 * It is either 0 and it is the same as its absence, or
+	 * it is > 0 and all the previous indexes are occupied.
+	 */
+	uint16_t hint_index_to_take;
+	/** Same hint but for bigref list compaction. */
+	uint16_t hint_index_to_free;
  } bigref_list;
  
  static const double ALLOC_FACTOR = 1.05;
@@ -300,10 +308,13 @@ bigref_list_destroy()
  static inline uint16_t
  bigref_list_new_index()
  {
+	/* Drop the 'free' hint. */
+	bigref_list.hint_index_to_free = bigref_list.capacity - 1;
  	if (bigref_list.size < bigref_list.capacity) {
-		uint16_t vacant_index = 0;
+		uint16_t vacant_index = bigref_list.hint_index_to_take;
  		while (bigref_list.refs[vacant_index] != 0)
  			++vacant_index;
+		bigref_list.hint_index_to_take = vacant_index + 1;
  		return vacant_index;
  	}
  	/* Extend the array. */
@@ -324,7 +335,9 @@ bigref_list_new_index()
  	memset(bigref_list.refs + bigref_list.capacity, 0, capacity -
  	       bigref_list.capacity);
  	bigref_list.capacity = capacity;
-	return bigref_list.size++;
+	uint16_t vacant_index = bigref_list.size++;
+	bigref_list.hint_index_to_take = bigref_list.size;
+	return vacant_index;
  }
  
  void
@@ -353,13 +366,16 @@ bigref_list_delete_index(uint16_t index)
  		bigref_list_destroy();
  		return;
  	}
+	/* Drop the 'take' hint. */
+	bigref_list.hint_index_to_take = 0;
  	if (bigref_list.capacity == BIGREF_MIN_CAPACITY ||
  	    bigref_list.size > bigref_list.capacity / BIGREF_FACTOR)
  		return;
  
-	uint16_t top_index = bigref_list.capacity - 1;
+	uint16_t top_index = bigref_list.hint_index_to_free;
  	while (bigref_list.refs[top_index] == 0)
  		top_index--;
+	bigref_list.hint_index_to_free = top_index;
  
  	uint16_t needed_capacity = top_index + 1;
  	if (needed_capacity < BIGREF_MIN_CAPACITY)

Re: [tarantool-patches] [PATCH v2 2/1] tuple: introduce bigref hints

[Konstantin Osipov]

* Vladislav Shpilevoy <v.shpilevoy@tarantool.org> [18/06/05 00:01]:
>     tuple: introduce bigref hints
>     Typical usage of bigrefs: allocate many bigrefs in Lua in a row,
>     reach memory threshold and delete many bigrefs in a row.
>     Hits allow to make multiple refs deletions or creations be
>     faster. For example, before the patch complexity of N refs with
>     C capacity in a row: O(C) * N.
>     After the patch:     O(C) + N.
>     Same about unrefs.
>     Follow up #3224

Why not chain up all free links into a free list, similarly to
what we do in the slab allocator?


-- 
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov

Re: [tarantool-patches] Re: [PATCH v2 2/1] tuple: introduce bigref hints

[Vladislav Shpilevoy]

On 08/06/2018 06:28, Konstantin Osipov wrote:
> * Vladislav Shpilevoy <v.shpilevoy@tarantool.org> [18/06/05 00:01]:
>>      tuple: introduce bigref hints
>>      Typical usage of bigrefs: allocate many bigrefs in Lua in a row,
>>      reach memory threshold and delete many bigrefs in a row.
>>      Hits allow to make multiple refs deletions or creations be
>>      faster. For example, before the patch complexity of N refs with
>>      C capacity in a row: O(C) * N.
>>      After the patch:     O(C) + N.
>>      Same about unrefs.
>>      Follow up #3224
> 
> Why not chain up all free links into a free list, similarly to
> what we do in the slab allocator?
> 
> 

True list of uint16 has to big overhead on next/prev pointer.

If we use array instead of list, then we face with the same problem
as original bigref array has. Removal from the array produces gaps.

I have decided that the pair of simple hints is enough since the
typical bigref usage follows the scenario: create many bigrefs in Lua in
a row, that triggers lua GC, that frees many bigrefs in a row. My
hints graceful deal with it.