From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from localhost (localhost [127.0.0.1]) by turing.freelists.org (Avenir Technologies Mail Multiplex) with ESMTP id 53BD22151D for ; Tue, 29 May 2018 08:11:26 -0400 (EDT) Received: from turing.freelists.org ([127.0.0.1]) by localhost (turing.freelists.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id uFQwnAdk-zS2 for ; Tue, 29 May 2018 08:11:26 -0400 (EDT) Received: from smtp5.mail.ru (smtp5.mail.ru [94.100.179.24]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by turing.freelists.org (Avenir Technologies Mail Multiplex) with ESMTPS id 0FD6A211A8 for ; Tue, 29 May 2018 08:11:25 -0400 (EDT) From: Mergen Imeev Subject: [tarantool-patches] [PATCH box 1/1] box: create bigrefs for tuples Date: Tue, 29 May 2018 15:11:13 +0300 Message-Id: <7a17a3937f7729796eac617e5041722d9f0d07a4.1527595851.git.imeevma@tarantool.org> Sender: tarantool-patches-bounce@freelists.org Errors-to: tarantool-patches-bounce@freelists.org Reply-To: tarantool-patches@freelists.org List-help: List-unsubscribe: List-software: Ecartis version 1.0.0 List-Id: tarantool-patches List-subscribe: List-owner: List-post: List-archive: To: tarantool-patches@freelists.org Cc: Mergen Imeev From: Mergen Imeev Due to limitation of number of bigrefs being only 65535 it was possible to reach this limitation. This patch increases capacity of referance counter to 4 billions. Closes #3224 --- src/box/tuple.c | 18 +++++++ src/box/tuple.h | 135 +++++++++++++++++++++++++++++++++++++++++++---- test/box/select.result | 5 +- test/box/select.test.lua | 2 +- 4 files changed, 146 insertions(+), 14 deletions(-) diff --git a/src/box/tuple.c b/src/box/tuple.c index 014f374..f4e1829 100644 --- a/src/box/tuple.c +++ b/src/box/tuple.c @@ -58,6 +58,12 @@ struct tuple *box_tuple_last; struct tuple_format *tuple_format_runtime; +/** + * All bigrefs of tuples + * \sa tuple_ref + */ +struct tuple_bigrefs bigrefs; + static void runtime_tuple_delete(struct tuple_format *format, struct tuple *tuple); @@ -211,6 +217,16 @@ tuple_init(field_name_hash_f hash) box_tuple_last = NULL; + bigrefs.size = 0; + bigrefs.capacity = TUPLE_BIGREF_MIN_CAPACITY; + bigrefs.refs = (uint32_t *) malloc(bigrefs.capacity * sizeof(uint32_t)); + if (bigrefs.refs == NULL) { + diag_set(OutOfMemory, bigrefs.capacity * + sizeof(uint32_t), "malloc", "bigrefs.refs"); + return -1; + } + + if (coll_id_cache_init() != 0) return -1; @@ -265,6 +281,8 @@ tuple_free(void) tuple_format_free(); coll_id_cache_destroy(); + + free(bigrefs.refs); } box_tuple_format_t * diff --git a/src/box/tuple.h b/src/box/tuple.h index e2384dd..c7dbe3b 100644 --- a/src/box/tuple.h +++ b/src/box/tuple.h @@ -327,6 +327,19 @@ struct PACKED tuple */ }; +/** + * @brief Container for bigrefs. + */ +struct tuple_bigrefs +{ + /** reference counter */ + uint32_t *refs; + /** index of last non-zero element */ + uint16_t size; + /** capacity of container */ + uint16_t capacity; +}; + /** Size of the tuple including size of struct tuple. */ static inline size_t tuple_size(const struct tuple *tuple) @@ -774,7 +787,41 @@ tuple_field_uuid(const struct tuple *tuple, int fieldno, return 0; } -enum { TUPLE_REF_MAX = UINT16_MAX }; +enum { + TUPLE_BIGREFS_FACTOR = 2, + TUPLE_BIGREF_MAX = UINT32_MAX, + TUPLE_REF_MAX = UINT16_MAX >> 1, + TUPLE_REF_FLAG = UINT16_MAX ^ TUPLE_REF_MAX, + TUPLE_BIGREF_MIN_CAPACITY = 16 +}; + +extern struct tuple_bigrefs bigrefs; + +/** + * Return index for new bigref + * @retval Number less than or equal 0x7fff Success. + * @retval Number more than 0x7fff Too many refs error. + */ +static inline uint16_t +get_bigref_index(void) +{ + for(uint16_t i = 0; i < bigrefs.size; ++i) + if(bigrefs.refs[i] == 0) + return i; + if(bigrefs.size == bigrefs.capacity - 1) { + if(bigrefs.capacity > TUPLE_REF_MAX / TUPLE_BIGREFS_FACTOR) + return TUPLE_REF_FLAG; + bigrefs.capacity *= TUPLE_BIGREFS_FACTOR; + bigrefs.refs = (uint32_t *) realloc(bigrefs.refs, + bigrefs.capacity * sizeof(uint32_t)); + if (bigrefs.refs == NULL) { + diag_set(OutOfMemory, bigrefs.capacity * + sizeof(uint32_t), "realloc", "bigrefs.refs"); + return TUPLE_REF_FLAG; + } + } + return bigrefs.size++; +} /** * Increment tuple reference counter. @@ -785,15 +832,55 @@ enum { TUPLE_REF_MAX = UINT16_MAX }; static inline int tuple_ref(struct tuple *tuple) { - if (tuple->refs + 1 > TUPLE_REF_MAX) { - diag_set(ClientError, ER_TUPLE_REF_OVERFLOW); - return -1; + if(tuple->refs == TUPLE_REF_MAX) { + uint16_t index = get_bigref_index(); + if(index > TUPLE_REF_MAX) { + diag_set(ClientError, ER_TUPLE_REF_OVERFLOW); + return -1; + } + tuple->refs = TUPLE_REF_FLAG | index; + bigrefs.refs[index] = TUPLE_REF_MAX; } - tuple->refs++; + if((tuple->refs & TUPLE_REF_FLAG) > 0) { + uint16_t index = tuple->refs ^ TUPLE_REF_FLAG; + if (bigrefs.refs[index] > TUPLE_BIGREF_MAX - 1) { + diag_set(ClientError, ER_TUPLE_REF_OVERFLOW); + return -1; + } + bigrefs.refs[index]++; + } else tuple->refs++; return 0; } /** + * Check if capacity of bigrefs can be reduced + */ +static inline void +bigrefs_check_capacity(void) +{ + uint16_t tmp_size; + uint16_t tmp_capacity = bigrefs.capacity; + for(uint16_t i = 0; i < bigrefs.capacity; ++i) + if(bigrefs.refs[i] > 0) + tmp_size = i; + while(tmp_capacity > TUPLE_BIGREF_MIN_CAPACITY && + tmp_size < tmp_capacity / TUPLE_BIGREFS_FACTOR) { + tmp_capacity /= TUPLE_BIGREFS_FACTOR; + if(tmp_capacity < TUPLE_BIGREF_MIN_CAPACITY) + tmp_capacity = TUPLE_BIGREF_MIN_CAPACITY; + } + bigrefs.size = tmp_size; + if(tmp_capacity < bigrefs.capacity) { + bigrefs.capacity = tmp_capacity; + bigrefs.refs = (uint32_t *) realloc(bigrefs.refs, + bigrefs.capacity * sizeof(uint32_t)); + if (bigrefs.refs == NULL) + diag_set(OutOfMemory, bigrefs.capacity * + sizeof(uint32_t), "malloc", "bigrefs.refs"); + } +} + +/** * Decrement tuple reference counter. If it has reached zero, free the tuple. * * @pre tuple->refs + count >= 0 @@ -802,8 +889,20 @@ static inline void tuple_unref(struct tuple *tuple) { assert(tuple->refs - 1 >= 0); + uint16_t index = tuple->refs ^ TUPLE_REF_FLAG; - tuple->refs--; + if((tuple->refs & TUPLE_REF_FLAG) > 0) { + bigrefs.refs[index]--; + } else { + tuple->refs--; + } + + if((tuple->refs & TUPLE_REF_FLAG) > 0 && + (bigrefs.refs[index] < TUPLE_REF_MAX)) { + tuple->refs = bigrefs.refs[index]; + bigrefs.refs[index] = 0; + bigrefs_check_capacity(); + } if (tuple->refs == 0) tuple_delete(tuple); @@ -824,11 +923,27 @@ tuple_bless(struct tuple *tuple) { assert(tuple != NULL); /* Ensure tuple can be referenced at least once after return */ - if (tuple->refs + 2 > TUPLE_REF_MAX) { - diag_set(ClientError, ER_TUPLE_REF_OVERFLOW); - return NULL; + + if(tuple->refs == TUPLE_REF_MAX) { + uint16_t index = get_bigref_index(); + if(index > TUPLE_REF_MAX) { + diag_set(ClientError, ER_TUPLE_REF_OVERFLOW); + return NULL; + } + tuple->refs = TUPLE_REF_FLAG | index; + bigrefs.refs[index] = TUPLE_REF_MAX; + } + if((tuple->refs & TUPLE_REF_FLAG) > 0) { + uint16_t index = tuple->refs ^ TUPLE_REF_FLAG; + if (bigrefs.refs[index] > TUPLE_BIGREF_MAX - 2) { + diag_set(ClientError, ER_TUPLE_REF_OVERFLOW); + return NULL; + } + bigrefs.refs[index]++; + } else { + tuple->refs++; } - tuple->refs++; + /* Remove previous tuple */ if (likely(box_tuple_last != NULL)) tuple_unref(box_tuple_last); /* do not throw */ diff --git a/test/box/select.result b/test/box/select.result index 4aed706..d2beb9e 100644 --- a/test/box/select.result +++ b/test/box/select.result @@ -634,13 +634,12 @@ lots_of_links = {} ref_count = 0 --- ... -while (true) do table.insert(lots_of_links, s:get{0}) ref_count = ref_count + 1 end +while (ref_count < 100000) do table.insert(lots_of_links, s:get{0}) ref_count = ref_count + 1 end --- -- error: Tuple reference counter overflow ... ref_count --- -- 65531 +- 100000 ... lots_of_links = {} --- diff --git a/test/box/select.test.lua b/test/box/select.test.lua index 54c2ecc..5e3071d 100644 --- a/test/box/select.test.lua +++ b/test/box/select.test.lua @@ -129,7 +129,7 @@ index = s:create_index('primary', { type = 'tree' }) a = s:insert{0} lots_of_links = {} ref_count = 0 -while (true) do table.insert(lots_of_links, s:get{0}) ref_count = ref_count + 1 end +while (ref_count < 100000) do table.insert(lots_of_links, s:get{0}) ref_count = ref_count + 1 end ref_count lots_of_links = {} s:drop() -- 2.7.4