* [tarantool-patches] [PATCH v2 1/1] box: create bigrefs for tuples
@ 2018-06-01 15:41 imeevma
2018-06-01 19:11 ` [tarantool-patches] " Konstantin Osipov
` (2 more replies)
0 siblings, 3 replies; 14+ messages in thread
From: imeevma @ 2018-06-01 15:41 UTC (permalink / raw)
To: tarantool-patches
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
^ permalink raw reply [flat|nested] 14+ messages in thread
* [tarantool-patches] Re: [PATCH v2 1/1] box: create bigrefs for tuples
2018-06-01 15:41 [tarantool-patches] [PATCH v2 1/1] box: create bigrefs for tuples imeevma
@ 2018-06-01 19:11 ` Konstantin Osipov
2018-06-04 11:21 ` Vladislav Shpilevoy
2018-06-04 20:57 ` [tarantool-patches] [PATCH v2 2/1] tuple: introduce bigref hints Vladislav Shpilevoy
2 siblings, 0 replies; 14+ messages in thread
From: Konstantin Osipov @ 2018-06-01 19:11 UTC (permalink / raw)
To: tarantool-patches
* 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
^ permalink raw reply [flat|nested] 14+ messages in thread
* [tarantool-patches] Re: [PATCH v2 1/1] box: create bigrefs for tuples
2018-06-01 15:41 [tarantool-patches] [PATCH v2 1/1] box: create bigrefs for tuples imeevma
2018-06-01 19:11 ` [tarantool-patches] " Konstantin Osipov
@ 2018-06-04 11:21 ` Vladislav Shpilevoy
2018-06-04 14:21 ` Imeev Mergen
2018-06-04 20:57 ` [tarantool-patches] [PATCH v2 2/1] tuple: introduce bigref hints Vladislav Shpilevoy
2 siblings, 1 reply; 14+ messages in thread
From: Vladislav Shpilevoy @ 2018-06-04 11:21 UTC (permalink / raw)
To: tarantool-patches, imeevma
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);
> }
>
^ permalink raw reply [flat|nested] 14+ messages in thread
* [tarantool-patches] Re: [PATCH v2 1/1] box: create bigrefs for tuples
2018-06-04 11:21 ` Vladislav Shpilevoy
@ 2018-06-04 14:21 ` Imeev Mergen
2018-06-04 20:57 ` Vladislav Shpilevoy
0 siblings, 1 reply; 14+ messages in thread
From: Imeev Mergen @ 2018-06-04 14:21 UTC (permalink / raw)
To: Vladislav Shpilevoy, tarantool-patches
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()
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [tarantool-patches] Re: [PATCH v2 1/1] box: create bigrefs for tuples
2018-06-04 14:21 ` Imeev Mergen
@ 2018-06-04 20:57 ` Vladislav Shpilevoy
2018-06-04 21:20 ` Vladislav Shpilevoy
` (2 more replies)
0 siblings, 3 replies; 14+ messages in thread
From: Vladislav Shpilevoy @ 2018-06-04 20:57 UTC (permalink / raw)
To: tarantool-patches, Vladimir Davydov; +Cc: Imeev Mergen
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()
^ permalink raw reply [flat|nested] 14+ messages in thread
* [tarantool-patches] [PATCH v2 2/1] tuple: introduce bigref hints
2018-06-01 15:41 [tarantool-patches] [PATCH v2 1/1] box: create bigrefs for tuples imeevma
2018-06-01 19:11 ` [tarantool-patches] " Konstantin Osipov
2018-06-04 11:21 ` Vladislav Shpilevoy
@ 2018-06-04 20:57 ` Vladislav Shpilevoy
2018-06-08 3:28 ` Konstantin Osipov
2 siblings, 1 reply; 14+ messages in thread
From: Vladislav Shpilevoy @ 2018-06-04 20:57 UTC (permalink / raw)
To: tarantool-patches, Vladimir Davydov
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)
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [tarantool-patches] Re: [PATCH v2 1/1] box: create bigrefs for tuples
2018-06-04 20:57 ` Vladislav Shpilevoy
@ 2018-06-04 21:20 ` Vladislav Shpilevoy
2018-06-08 3:27 ` Konstantin Osipov
2018-06-08 3:18 ` Konstantin Osipov
2018-06-08 3:26 ` Konstantin Osipov
2 siblings, 1 reply; 14+ messages in thread
From: Vladislav Shpilevoy @ 2018-06-04 21:20 UTC (permalink / raw)
To: tarantool-patches, Vladimir Davydov; +Cc: Imeev Mergen
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()
>
>
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [tarantool-patches] Re: [PATCH v2 1/1] box: create bigrefs for tuples
2018-06-04 20:57 ` Vladislav Shpilevoy
2018-06-04 21:20 ` Vladislav Shpilevoy
@ 2018-06-08 3:18 ` Konstantin Osipov
2018-06-08 3:26 ` Konstantin Osipov
2 siblings, 0 replies; 14+ messages in thread
From: Konstantin Osipov @ 2018-06-08 3:18 UTC (permalink / raw)
To: tarantool-patches; +Cc: Vladimir Davydov, Imeev Mergen
* 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
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [tarantool-patches] Re: [PATCH v2 1/1] box: create bigrefs for tuples
2018-06-04 20:57 ` Vladislav Shpilevoy
2018-06-04 21:20 ` Vladislav Shpilevoy
2018-06-08 3:18 ` Konstantin Osipov
@ 2018-06-08 3:26 ` Konstantin Osipov
2 siblings, 0 replies; 14+ messages in thread
From: Konstantin Osipov @ 2018-06-08 3:26 UTC (permalink / raw)
To: tarantool-patches; +Cc: Vladimir Davydov, Imeev Mergen
* 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
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [tarantool-patches] Re: [PATCH v2 1/1] box: create bigrefs for tuples
2018-06-04 21:20 ` Vladislav Shpilevoy
@ 2018-06-08 3:27 ` Konstantin Osipov
0 siblings, 0 replies; 14+ messages in thread
From: Konstantin Osipov @ 2018-06-08 3:27 UTC (permalink / raw)
To: tarantool-patches; +Cc: Vladimir Davydov, Imeev Mergen
* 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
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [tarantool-patches] [PATCH v2 2/1] tuple: introduce bigref hints
2018-06-04 20:57 ` [tarantool-patches] [PATCH v2 2/1] tuple: introduce bigref hints Vladislav Shpilevoy
@ 2018-06-08 3:28 ` Konstantin Osipov
2018-06-08 10:36 ` [tarantool-patches] " Vladislav Shpilevoy
0 siblings, 1 reply; 14+ messages in thread
From: Konstantin Osipov @ 2018-06-08 3:28 UTC (permalink / raw)
To: tarantool-patches; +Cc: Vladimir Davydov
* 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
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [tarantool-patches] Re: [PATCH v2 2/1] tuple: introduce bigref hints
2018-06-08 3:28 ` Konstantin Osipov
@ 2018-06-08 10:36 ` Vladislav Shpilevoy
0 siblings, 0 replies; 14+ messages in thread
From: Vladislav Shpilevoy @ 2018-06-08 10:36 UTC (permalink / raw)
To: tarantool-patches, Konstantin Osipov; +Cc: Vladimir Davydov
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.
^ permalink raw reply [flat|nested] 14+ messages in thread
* [tarantool-patches] [PATCH v2 1/1] box: create bigrefs for tuples
@ 2018-05-30 15:26 imeevma
0 siblings, 0 replies; 14+ messages in thread
From: imeevma @ 2018-05-30 15:26 UTC (permalink / raw)
To: tarantool-patches
Due to limitation of number of bigrefs being only 65535 it
was possible to reach this limitation. This patch increases
capacity of reference counter to 4 billions.
Closes #3224
---
Branch: https://github.com/tarantool/tarantool/tree/gh-3224-tuple-bigrefs
Issue: https://github.com/tarantool/tarantool/issues/3224
src/box/errcode.h | 2 +-
src/box/tuple.c | 168 +++++++++++++++++++++++++++++++++++++++++++++++
src/box/tuple.h | 36 ++++++----
test/box/misc.result | 39 ++++++-----
test/box/select.result | 32 ++++++++-
test/box/select.test.lua | 15 ++++-
6 files changed, 256 insertions(+), 36 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/tuple.c b/src/box/tuple.c
index 014f374..60280e4 100644
--- a/src/box/tuple.c
+++ b/src/box/tuple.c
@@ -48,6 +48,16 @@ enum {
OBJSIZE_MIN = 16,
};
+/**
+* @brief Container for bigrefs.
+*/
+struct tuple_bigrefs
+{
+ uint32_t *refs;
+ uint16_t size;
+ uint16_t capacity;
+};
+
static const double ALLOC_FACTOR = 1.05;
/**
@@ -58,6 +68,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);
@@ -211,6 +227,10 @@ tuple_init(field_name_hash_f hash)
box_tuple_last = NULL;
+ bigrefs.size = 0;
+ bigrefs.refs = NULL;
+ bigrefs.capacity = 0;
+
if (coll_id_cache_init() != 0)
return -1;
@@ -244,6 +264,152 @@ tuple_arena_create(struct slab_arena *arena, struct quota *quota,
}
}
+enum {
+ TUPLE_BIGREF_FACTOR = 2,
+ TUPLE_BIGREF_MAX = UINT32_MAX,
+ TUPLE_BIGREF_ERROR = UINT16_MAX,
+ TUPLE_BIGREF_FLAG = UINT16_MAX ^ (UINT16_MAX >> 1),
+ TUPLE_BIGREF_MIN_CAPACITY = 16,
+ TUPLE_BIGREF_MAX_CAPACITY = UINT16_MAX >> 1
+};
+
+/**
+ * Free memory that was allocated for big references.
+ */
+static inline void
+tuple_bigrefs_free(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) {
+ for (uint16_t i = 0; i < bigrefs.capacity; ++i) {
+ if (bigrefs.refs[i] == 0) {
+ ++bigrefs.size;
+ return i;
+ }
+ }
+ unreachable();
+ }
+ /* Extend the array ... */
+ uint16_t capacity = bigrefs.capacity;
+ if(bigrefs.refs == NULL) {
+ assert(bigrefs.size == 0 && bigrefs.capacity == 0);
+ capacity = TUPLE_BIGREF_MIN_CAPACITY;
+ bigrefs.refs = (uint32_t *) malloc(capacity *
+ sizeof(*bigrefs.refs));
+ if(bigrefs.refs == NULL) {
+ diag_set(OutOfMemory, capacity * sizeof(*bigrefs.refs),
+ "malloc", "bigrefs.refs");
+ return TUPLE_BIGREF_ERROR;
+ }
+ bigrefs.capacity = capacity;
+ return bigrefs.size++;
+ }
+ if(capacity >= TUPLE_BIGREF_MAX_CAPACITY) {
+ tuple_bigrefs_free();
+ return TUPLE_BIGREF_ERROR;
+ }
+ if(capacity > TUPLE_BIGREF_MAX_CAPACITY / TUPLE_BIGREF_FACTOR)
+ capacity = TUPLE_BIGREF_MAX_CAPACITY;
+ else
+ capacity *= TUPLE_BIGREF_FACTOR;
+ uint32_t *refs = (uint32_t *) realloc(bigrefs.refs, capacity *
+ sizeof(*bigrefs.refs));
+ if (refs == NULL) {
+ tuple_bigrefs_free();
+ diag_set(OutOfMemory, capacity * sizeof(*bigrefs.refs),
+ "realloc", "bigrefs.refs");
+ return TUPLE_BIGREF_ERROR;
+ }
+ bigrefs.refs = refs;
+ bigrefs.capacity = capacity;
+ return bigrefs.size++;
+}
+
+int
+tuple_ref_slow(struct tuple *tuple)
+{
+ if(tuple->refs == TUPLE_REF_MAX) {
+ uint16_t index = tuple_bigref_retrieve();
+ if(index > TUPLE_BIGREF_MAX_CAPACITY) {
+ panic("Tuple reference counter overflow");
+ return -1;
+ }
+ tuple->refs = TUPLE_BIGREF_FLAG | index;
+ bigrefs.refs[index] = TUPLE_REF_MAX;
+ }
+ uint16_t index = tuple->refs ^ TUPLE_BIGREF_FLAG;
+ if (bigrefs.refs[index] > TUPLE_BIGREF_MAX - 1) {
+ panic("Tuple reference counter overflow");
+ return -1;
+ }
+ bigrefs.refs[index]++;
+ return 0;
+}
+
+/**
+ * Try to decrease allocated memory if it is possible. Free memory when
+ * size == 0.
+ */
+static inline void
+tuple_bigrefs_release(void)
+{
+ if(bigrefs.size == 0) {
+ tuple_bigrefs_free();
+ return;
+ }
+ if(bigrefs.capacity == TUPLE_BIGREF_MIN_CAPACITY)
+ return;
+ uint16_t reserved_bigrefs = 0;
+ uint16_t capacity = bigrefs.capacity;
+ for(uint16_t i = 0; i < capacity; ++i) {
+ if(bigrefs.refs[i] != 0)
+ reserved_bigrefs = i + 1;
+ }
+ if(reserved_bigrefs >= capacity / TUPLE_BIGREF_FACTOR) {
+ return;
+ } else if(reserved_bigrefs < TUPLE_BIGREF_MIN_CAPACITY) {
+ capacity = TUPLE_BIGREF_MIN_CAPACITY;
+ } else {
+ while(reserved_bigrefs < capacity / TUPLE_BIGREF_FACTOR)
+ capacity /= TUPLE_BIGREF_FACTOR;
+ }
+ uint32_t *refs = (uint32_t *) realloc(bigrefs.refs, capacity *
+ sizeof(*bigrefs.refs));
+ if(refs == NULL) {
+ tuple_bigrefs_free();
+ diag_set(OutOfMemory, capacity, "realloc", "bigrefs.refs");
+ return;
+ }
+ bigrefs.refs = refs;
+ bigrefs.capacity = capacity;
+}
+
+void
+tuple_unref_slow(struct tuple *tuple)
+{
+ uint16_t index = tuple->refs ^ TUPLE_BIGREF_FLAG;
+ bigrefs.refs[index]--;
+ if(bigrefs.refs[index] <= TUPLE_REF_MAX) {
+ tuple->refs = bigrefs.refs[index];
+ bigrefs.refs[index] = 0;
+ bigrefs.size--;
+ if(bigrefs.size < bigrefs.capacity / TUPLE_BIGREF_FACTOR)
+ tuple_bigrefs_release();
+ }
+}
+
void
tuple_arena_destroy(struct slab_arena *arena)
{
@@ -265,6 +431,8 @@ tuple_free(void)
tuple_format_free();
coll_id_cache_destroy();
+
+ tuple_bigrefs_free();
}
box_tuple_format_t *
diff --git a/src/box/tuple.h b/src/box/tuple.h
index e2384dd..dd5e11e 100644
--- a/src/box/tuple.h
+++ b/src/box/tuple.h
@@ -774,26 +774,40 @@ 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.
+ * @retval 0 Success.
+ * @retval -1 Error.
+ */
+int
+tuple_ref_slow(struct tuple *tuple);
/**
* Increment tuple reference counter.
* @param tuple Tuple to reference.
* @retval 0 Success.
- * @retval -1 Too many refs error.
+ * @retval -1 Error.
*/
static inline int
tuple_ref(struct tuple *tuple)
{
- if (tuple->refs + 1 > TUPLE_REF_MAX) {
- diag_set(ClientError, ER_TUPLE_REF_OVERFLOW);
- return -1;
- }
+ if (tuple->refs >= TUPLE_REF_MAX)
+ return tuple_ref_slow(tuple);
tuple->refs++;
return 0;
}
/**
+ * 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 +816,10 @@ static inline void
tuple_unref(struct tuple *tuple)
{
assert(tuple->refs - 1 >= 0);
+ if (tuple->refs > TUPLE_REF_MAX) {
+ tuple_unref_slow(tuple);
+ return;
+ }
tuple->refs--;
@@ -823,12 +841,8 @@ 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);
+ if(tuple_ref(tuple) < 0)
return NULL;
- }
- tuple->refs++;
/* Remove previous tuple */
if (likely(box_tuple_last != NULL))
tuple_unref(box_tuple_last); /* do not throw */
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..3d3a0d3 100644
--- a/test/box/select.result
+++ b/test/box/select.result
@@ -619,6 +619,7 @@ collectgarbage('collect')
---
- 0
...
+-- gh-3224 resurrect tuple bigrefs
s = box.schema.space.create('select', { temporary = true })
---
...
@@ -634,13 +635,19 @@ lots_of_links = {}
ref_count = 0
---
...
-while (true) do table.insert(lots_of_links, s:get{0}) ref_count = ref_count + 1 end
+while (ref_count < 100000) do table.insert(lots_of_links, s:get{0}) ref_count = ref_count + 1 end
---
-- error: Tuple reference counter overflow
...
ref_count
---
-- 65531
+- 100000
+...
+for k, v in pairs(lots_of_links) do ref_count = ref_count - 1 end
+---
+...
+ref_count
+---
+- 0
...
lots_of_links = {}
---
@@ -648,3 +655,22 @@ lots_of_links = {}
s:drop()
---
...
+-- Check that tuple deleted when ref counter = 0
+weak_tuple = setmetatable({}, {__mode = 'v'})
+---
+...
+table.insert(weak_tuple, box.tuple.new(1))
+---
+...
+weak_tuple
+---
+- - [1]
+...
+collectgarbage('collect')
+---
+- 0
+...
+weak_tuple
+---
+- []
+...
diff --git a/test/box/select.test.lua b/test/box/select.test.lua
index 54c2ecc..910d4f7 100644
--- a/test/box/select.test.lua
+++ b/test/box/select.test.lua
@@ -124,12 +124,25 @@ test.random(s.index[0], 48)
s:drop()
collectgarbage('collect')
+
+-- gh-3224 resurrect tuple bigrefs
+
s = box.schema.space.create('select', { temporary = true })
index = s:create_index('primary', { type = 'tree' })
a = s:insert{0}
lots_of_links = {}
ref_count = 0
-while (true) do table.insert(lots_of_links, s:get{0}) ref_count = ref_count + 1 end
+while (ref_count < 100000) do table.insert(lots_of_links, s:get{0}) ref_count = ref_count + 1 end
+ref_count
+for k, v in pairs(lots_of_links) do ref_count = ref_count - 1 end
ref_count
lots_of_links = {}
s:drop()
+
+-- Check that tuple deleted when ref counter = 0
+
+weak_tuple = setmetatable({}, {__mode = 'v'})
+table.insert(weak_tuple, box.tuple.new(1))
+weak_tuple
+collectgarbage('collect')
+weak_tuple
--
2.7.4
^ permalink raw reply [flat|nested] 14+ messages in thread
* [tarantool-patches] [PATCH v2 1/1] box: create bigrefs for tuples
@ 2018-05-30 14:14 imeevma
0 siblings, 0 replies; 14+ messages in thread
From: imeevma @ 2018-05-30 14:14 UTC (permalink / raw)
To: tarantool-patches
Due to limitation of number of bigrefs being only 65535 it
was possible to reach this limitation. This patch increases
capacity of reference counter to 4 billions.
Closes #3224
---
Branch: https://github.com/tarantool/tarantool/tree/gh-3224-tuple-bigrefs
Issue: https://github.com/tarantool/tarantool/issues/3224
src/box/errcode.h | 2 +-
src/box/tuple.c | 168 +++++++++++++++++++++++++++++++++++++++++++++++
src/box/tuple.h | 36 ++++++----
test/box/select.result | 32 ++++++++-
test/box/select.test.lua | 15 ++++-
5 files changed, 237 insertions(+), 16 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/tuple.c b/src/box/tuple.c
index 014f374..60280e4 100644
--- a/src/box/tuple.c
+++ b/src/box/tuple.c
@@ -48,6 +48,16 @@ enum {
OBJSIZE_MIN = 16,
};
+/**
+* @brief Container for bigrefs.
+*/
+struct tuple_bigrefs
+{
+ uint32_t *refs;
+ uint16_t size;
+ uint16_t capacity;
+};
+
static const double ALLOC_FACTOR = 1.05;
/**
@@ -58,6 +68,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);
@@ -211,6 +227,10 @@ tuple_init(field_name_hash_f hash)
box_tuple_last = NULL;
+ bigrefs.size = 0;
+ bigrefs.refs = NULL;
+ bigrefs.capacity = 0;
+
if (coll_id_cache_init() != 0)
return -1;
@@ -244,6 +264,152 @@ tuple_arena_create(struct slab_arena *arena, struct quota *quota,
}
}
+enum {
+ TUPLE_BIGREF_FACTOR = 2,
+ TUPLE_BIGREF_MAX = UINT32_MAX,
+ TUPLE_BIGREF_ERROR = UINT16_MAX,
+ TUPLE_BIGREF_FLAG = UINT16_MAX ^ (UINT16_MAX >> 1),
+ TUPLE_BIGREF_MIN_CAPACITY = 16,
+ TUPLE_BIGREF_MAX_CAPACITY = UINT16_MAX >> 1
+};
+
+/**
+ * Free memory that was allocated for big references.
+ */
+static inline void
+tuple_bigrefs_free(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) {
+ for (uint16_t i = 0; i < bigrefs.capacity; ++i) {
+ if (bigrefs.refs[i] == 0) {
+ ++bigrefs.size;
+ return i;
+ }
+ }
+ unreachable();
+ }
+ /* Extend the array ... */
+ uint16_t capacity = bigrefs.capacity;
+ if(bigrefs.refs == NULL) {
+ assert(bigrefs.size == 0 && bigrefs.capacity == 0);
+ capacity = TUPLE_BIGREF_MIN_CAPACITY;
+ bigrefs.refs = (uint32_t *) malloc(capacity *
+ sizeof(*bigrefs.refs));
+ if(bigrefs.refs == NULL) {
+ diag_set(OutOfMemory, capacity * sizeof(*bigrefs.refs),
+ "malloc", "bigrefs.refs");
+ return TUPLE_BIGREF_ERROR;
+ }
+ bigrefs.capacity = capacity;
+ return bigrefs.size++;
+ }
+ if(capacity >= TUPLE_BIGREF_MAX_CAPACITY) {
+ tuple_bigrefs_free();
+ return TUPLE_BIGREF_ERROR;
+ }
+ if(capacity > TUPLE_BIGREF_MAX_CAPACITY / TUPLE_BIGREF_FACTOR)
+ capacity = TUPLE_BIGREF_MAX_CAPACITY;
+ else
+ capacity *= TUPLE_BIGREF_FACTOR;
+ uint32_t *refs = (uint32_t *) realloc(bigrefs.refs, capacity *
+ sizeof(*bigrefs.refs));
+ if (refs == NULL) {
+ tuple_bigrefs_free();
+ diag_set(OutOfMemory, capacity * sizeof(*bigrefs.refs),
+ "realloc", "bigrefs.refs");
+ return TUPLE_BIGREF_ERROR;
+ }
+ bigrefs.refs = refs;
+ bigrefs.capacity = capacity;
+ return bigrefs.size++;
+}
+
+int
+tuple_ref_slow(struct tuple *tuple)
+{
+ if(tuple->refs == TUPLE_REF_MAX) {
+ uint16_t index = tuple_bigref_retrieve();
+ if(index > TUPLE_BIGREF_MAX_CAPACITY) {
+ panic("Tuple reference counter overflow");
+ return -1;
+ }
+ tuple->refs = TUPLE_BIGREF_FLAG | index;
+ bigrefs.refs[index] = TUPLE_REF_MAX;
+ }
+ uint16_t index = tuple->refs ^ TUPLE_BIGREF_FLAG;
+ if (bigrefs.refs[index] > TUPLE_BIGREF_MAX - 1) {
+ panic("Tuple reference counter overflow");
+ return -1;
+ }
+ bigrefs.refs[index]++;
+ return 0;
+}
+
+/**
+ * Try to decrease allocated memory if it is possible. Free memory when
+ * size == 0.
+ */
+static inline void
+tuple_bigrefs_release(void)
+{
+ if(bigrefs.size == 0) {
+ tuple_bigrefs_free();
+ return;
+ }
+ if(bigrefs.capacity == TUPLE_BIGREF_MIN_CAPACITY)
+ return;
+ uint16_t reserved_bigrefs = 0;
+ uint16_t capacity = bigrefs.capacity;
+ for(uint16_t i = 0; i < capacity; ++i) {
+ if(bigrefs.refs[i] != 0)
+ reserved_bigrefs = i + 1;
+ }
+ if(reserved_bigrefs >= capacity / TUPLE_BIGREF_FACTOR) {
+ return;
+ } else if(reserved_bigrefs < TUPLE_BIGREF_MIN_CAPACITY) {
+ capacity = TUPLE_BIGREF_MIN_CAPACITY;
+ } else {
+ while(reserved_bigrefs < capacity / TUPLE_BIGREF_FACTOR)
+ capacity /= TUPLE_BIGREF_FACTOR;
+ }
+ uint32_t *refs = (uint32_t *) realloc(bigrefs.refs, capacity *
+ sizeof(*bigrefs.refs));
+ if(refs == NULL) {
+ tuple_bigrefs_free();
+ diag_set(OutOfMemory, capacity, "realloc", "bigrefs.refs");
+ return;
+ }
+ bigrefs.refs = refs;
+ bigrefs.capacity = capacity;
+}
+
+void
+tuple_unref_slow(struct tuple *tuple)
+{
+ uint16_t index = tuple->refs ^ TUPLE_BIGREF_FLAG;
+ bigrefs.refs[index]--;
+ if(bigrefs.refs[index] <= TUPLE_REF_MAX) {
+ tuple->refs = bigrefs.refs[index];
+ bigrefs.refs[index] = 0;
+ bigrefs.size--;
+ if(bigrefs.size < bigrefs.capacity / TUPLE_BIGREF_FACTOR)
+ tuple_bigrefs_release();
+ }
+}
+
void
tuple_arena_destroy(struct slab_arena *arena)
{
@@ -265,6 +431,8 @@ tuple_free(void)
tuple_format_free();
coll_id_cache_destroy();
+
+ tuple_bigrefs_free();
}
box_tuple_format_t *
diff --git a/src/box/tuple.h b/src/box/tuple.h
index e2384dd..dd5e11e 100644
--- a/src/box/tuple.h
+++ b/src/box/tuple.h
@@ -774,26 +774,40 @@ 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.
+ * @retval 0 Success.
+ * @retval -1 Error.
+ */
+int
+tuple_ref_slow(struct tuple *tuple);
/**
* Increment tuple reference counter.
* @param tuple Tuple to reference.
* @retval 0 Success.
- * @retval -1 Too many refs error.
+ * @retval -1 Error.
*/
static inline int
tuple_ref(struct tuple *tuple)
{
- if (tuple->refs + 1 > TUPLE_REF_MAX) {
- diag_set(ClientError, ER_TUPLE_REF_OVERFLOW);
- return -1;
- }
+ if (tuple->refs >= TUPLE_REF_MAX)
+ return tuple_ref_slow(tuple);
tuple->refs++;
return 0;
}
/**
+ * 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 +816,10 @@ static inline void
tuple_unref(struct tuple *tuple)
{
assert(tuple->refs - 1 >= 0);
+ if (tuple->refs > TUPLE_REF_MAX) {
+ tuple_unref_slow(tuple);
+ return;
+ }
tuple->refs--;
@@ -823,12 +841,8 @@ 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);
+ if(tuple_ref(tuple) < 0)
return NULL;
- }
- tuple->refs++;
/* Remove previous tuple */
if (likely(box_tuple_last != NULL))
tuple_unref(box_tuple_last); /* do not throw */
diff --git a/test/box/select.result b/test/box/select.result
index 4aed706..3d3a0d3 100644
--- a/test/box/select.result
+++ b/test/box/select.result
@@ -619,6 +619,7 @@ collectgarbage('collect')
---
- 0
...
+-- gh-3224 resurrect tuple bigrefs
s = box.schema.space.create('select', { temporary = true })
---
...
@@ -634,13 +635,19 @@ lots_of_links = {}
ref_count = 0
---
...
-while (true) do table.insert(lots_of_links, s:get{0}) ref_count = ref_count + 1 end
+while (ref_count < 100000) do table.insert(lots_of_links, s:get{0}) ref_count = ref_count + 1 end
---
-- error: Tuple reference counter overflow
...
ref_count
---
-- 65531
+- 100000
+...
+for k, v in pairs(lots_of_links) do ref_count = ref_count - 1 end
+---
+...
+ref_count
+---
+- 0
...
lots_of_links = {}
---
@@ -648,3 +655,22 @@ lots_of_links = {}
s:drop()
---
...
+-- Check that tuple deleted when ref counter = 0
+weak_tuple = setmetatable({}, {__mode = 'v'})
+---
+...
+table.insert(weak_tuple, box.tuple.new(1))
+---
+...
+weak_tuple
+---
+- - [1]
+...
+collectgarbage('collect')
+---
+- 0
+...
+weak_tuple
+---
+- []
+...
diff --git a/test/box/select.test.lua b/test/box/select.test.lua
index 54c2ecc..910d4f7 100644
--- a/test/box/select.test.lua
+++ b/test/box/select.test.lua
@@ -124,12 +124,25 @@ test.random(s.index[0], 48)
s:drop()
collectgarbage('collect')
+
+-- gh-3224 resurrect tuple bigrefs
+
s = box.schema.space.create('select', { temporary = true })
index = s:create_index('primary', { type = 'tree' })
a = s:insert{0}
lots_of_links = {}
ref_count = 0
-while (true) do table.insert(lots_of_links, s:get{0}) ref_count = ref_count + 1 end
+while (ref_count < 100000) do table.insert(lots_of_links, s:get{0}) ref_count = ref_count + 1 end
+ref_count
+for k, v in pairs(lots_of_links) do ref_count = ref_count - 1 end
ref_count
lots_of_links = {}
s:drop()
+
+-- Check that tuple deleted when ref counter = 0
+
+weak_tuple = setmetatable({}, {__mode = 'v'})
+table.insert(weak_tuple, box.tuple.new(1))
+weak_tuple
+collectgarbage('collect')
+weak_tuple
--
2.7.4
^ permalink raw reply [flat|nested] 14+ messages in thread
end of thread, other threads:[~2018-06-08 10:36 UTC | newest]
Thread overview: 14+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-06-01 15:41 [tarantool-patches] [PATCH v2 1/1] box: create bigrefs for tuples imeevma
2018-06-01 19:11 ` [tarantool-patches] " Konstantin Osipov
2018-06-04 11:21 ` Vladislav Shpilevoy
2018-06-04 14:21 ` Imeev Mergen
2018-06-04 20:57 ` Vladislav Shpilevoy
2018-06-04 21:20 ` Vladislav Shpilevoy
2018-06-08 3:27 ` Konstantin Osipov
2018-06-08 3:18 ` Konstantin Osipov
2018-06-08 3:26 ` Konstantin Osipov
2018-06-04 20:57 ` [tarantool-patches] [PATCH v2 2/1] tuple: introduce bigref hints Vladislav Shpilevoy
2018-06-08 3:28 ` Konstantin Osipov
2018-06-08 10:36 ` [tarantool-patches] " Vladislav Shpilevoy
-- strict thread matches above, loose matches on Subject: below --
2018-05-30 15:26 [tarantool-patches] [PATCH v2 1/1] box: create bigrefs for tuples imeevma
2018-05-30 14:14 imeevma
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox