From a1c2c274eebcc2a5275b677ebf94a8dbff380770 Mon Sep 17 00:00:00 2001 From: TSUYUSATO Kitsune Date: Wed, 19 Apr 2023 13:08:28 +0900 Subject: Refactor `Regexp#match` cache implementation (#7724) * Refactor Regexp#match cache implementation Improved variable and function names Fixed [Bug 19537] (Maybe fixed in https://github.com/ruby/ruby/pull/7694) * Add a comment of the glossary for "match cache" * Skip to reset match cache when no cache point on null check --- regexec.c | 719 +++++++++++++++++++++++++++++++++++--------------------------- 1 file changed, 408 insertions(+), 311 deletions(-) (limited to 'regexec.c') diff --git a/regexec.c b/regexec.c index f800ca9f30..8aff792a39 100644 --- a/regexec.c +++ b/regexec.c @@ -231,22 +231,48 @@ onig_get_capture_tree(OnigRegion* region) } #endif /* USE_CAPTURE_HISTORY */ -#ifdef USE_CACHE_MATCH_OPT +#ifdef USE_MATCH_CACHE -/* count number of jump-like opcodes for allocation of cache memory. */ +/* +Glossary for "match cache" + +"match cache" or "match cache optimization" +The `Regexp#match` optimization by using a cache. + +"cache opcode" +A cachable opcode (e.g. `OP_PUSH`, `OP_REPEAT`, etc). +It is corresponding to some cache points. +`OP_NULL_CHECK_START` and `OP_NULL_CHECK_END_MEMST` are exceptions. +They are counted as cache opcodes, but they have no corresponding cache points. +They are used for resetting a match cache buffer when a null loop is detected. + +"cache point" +A cachable point on matching. +Usually, one-to-one corresponding between a cache opcode and a cache point exists, +but cache opcodes between `OP_REPEAT` and `OP_REPEAT_INC` have some corresponding +cache points depending on repetition counts. + +"match cache point" +A pair of a cache point and a position on an input string. +We encode a match cache point to an integer value by the following equation: +"match cache point" = "position on input string" * "total number of cache points" + "cache point" + +"match cache buffer" +A bit-array for recording (caching) match cache points once arrived. +*/ + +/* count the total number of cache opcodes for allocating a match cache buffer. */ static OnigPosition -count_num_cache_opcode(regex_t* reg, long* num, long* table_size) +count_num_cache_opcodes(const regex_t* reg, long* num_cache_opcodes_ptr) { UChar* p = reg->p; UChar* pend = p + reg->used; LengthType len; - MemNumType mem; - MemNumType current_mem = -1; - long current_mem_num = 0; + MemNumType repeat_mem; OnigEncoding enc = reg->enc; - - *num = 0; - *table_size = 0; + MemNumType current_repeat_mem = -1; + long num_cache_opcodes = 0; + long num_cache_opcodes_at_null_check_start = -1; while (p < pend) { switch (*p++) { @@ -260,7 +286,7 @@ count_num_cache_opcode(regex_t* reg, long* num, long* table_size) case OP_EXACT4: p += 4; break; case OP_EXACT5: p += 5; break; case OP_EXACTN: - GET_LENGTH_INC(len, p); p += len; break; + GET_LENGTH_INC(len, p); p += len; break; case OP_EXACTMB2N1: p += 2; break; case OP_EXACTMB2N2: p += 4; break; case OP_EXACTMB2N3: p += 6; break; @@ -275,7 +301,7 @@ count_num_cache_opcode(regex_t* reg, long* num, long* table_size) GET_LENGTH_INC(len, p); p += mb_len * len; } - break; + break; case OP_EXACT1_IC: len = enclen(enc, p, pend); p += len; break; @@ -284,7 +310,7 @@ count_num_cache_opcode(regex_t* reg, long* num, long* table_size) case OP_CCLASS: case OP_CCLASS_NOT: - p += SIZE_BITSET; break; + p += SIZE_BITSET; break; case OP_CCLASS_MB: case OP_CCLASS_MB_NOT: GET_LENGTH_INC(len, p); p += len; break; @@ -300,10 +326,10 @@ count_num_cache_opcode(regex_t* reg, long* num, long* table_size) break; case OP_ANYCHAR_STAR: case OP_ANYCHAR_ML_STAR: - *num += 1; *table_size += 1; break; + num_cache_opcodes++;break; case OP_ANYCHAR_STAR_PEEK_NEXT: case OP_ANYCHAR_ML_STAR_PEEK_NEXT: - p++; *num += 1; *table_size += 1; break; + p++; num_cache_opcodes++; break; case OP_WORD: case OP_NOT_WORD: @@ -336,7 +362,7 @@ count_num_cache_opcode(regex_t* reg, long* num, long* table_size) case OP_BACKREF_MULTI: case OP_BACKREF_MULTI_IC: case OP_BACKREF_WITH_LEVEL: - goto fail; + goto impossible; case OP_MEMORY_START: case OP_MEMORY_START_PUSH: @@ -352,63 +378,69 @@ count_num_cache_opcode(regex_t* reg, long* num, long* table_size) case OP_FAIL: break; case OP_JUMP: - p += SIZE_RELADDR; + p += SIZE_RELADDR; break; case OP_PUSH: - p += SIZE_RELADDR; - *num += 1; - *table_size += 1; + p += SIZE_RELADDR; + num_cache_opcodes++; break; case OP_POP: break; case OP_PUSH_OR_JUMP_EXACT1: case OP_PUSH_IF_PEEK_NEXT: - p += SIZE_RELADDR + 1; *num += 1; *table_size += 1; break; + p += SIZE_RELADDR + 1; num_cache_opcodes++; break; case OP_REPEAT: case OP_REPEAT_NG: - if (current_mem != -1) { + if (current_repeat_mem != -1) { // A nested OP_REPEAT is not yet supported. - goto fail; + goto impossible; } - GET_MEMNUM_INC(mem, p); + GET_MEMNUM_INC(repeat_mem, p); p += SIZE_RELADDR; - if (reg->repeat_range[mem].lower == 0) { - *num += 1; - *table_size += 1; + if (reg->repeat_range[repeat_mem].lower == 0) { + num_cache_opcodes++; } - reg->repeat_range[mem].base_num = *num; - current_mem = mem; - current_mem_num = *num; + current_repeat_mem = repeat_mem; break; case OP_REPEAT_INC: case OP_REPEAT_INC_NG: - GET_MEMNUM_INC(mem, p); - if (mem != current_mem) { + GET_MEMNUM_INC(repeat_mem, p); + if (repeat_mem != current_repeat_mem) { // A lone or invalid OP_REPEAT_INC is found. - goto fail; + goto impossible; } { - long inner_num = *num - current_mem_num; - OnigRepeatRange *repeat_range = ®->repeat_range[mem]; - repeat_range->inner_num = inner_num; - *num -= inner_num; - *num += inner_num * repeat_range->lower + (inner_num + 1) * (repeat_range->upper == 0x7fffffff ? 1 : repeat_range->upper - repeat_range->lower); + OnigRepeatRange *repeat_range = ®->repeat_range[repeat_mem]; if (repeat_range->lower < repeat_range->upper) { - *table_size += 1; + num_cache_opcodes++; } - current_mem = -1; - current_mem_num = 0; + current_repeat_mem = -1; } break; case OP_REPEAT_INC_SG: case OP_REPEAT_INC_NG_SG: - // TODO: Support nested OP_REPEAT. - goto fail; + goto impossible; case OP_NULL_CHECK_START: + p += SIZE_MEMNUM; + if (num_cache_opcodes_at_null_check_start != -1) { + // A nested OP_NULL_CHECK_START is not yet supported. + goto impossible; + } + num_cache_opcodes_at_null_check_start = num_cache_opcodes; + break; case OP_NULL_CHECK_END: - case OP_NULL_CHECK_END_MEMST: case OP_NULL_CHECK_END_MEMST_PUSH: - p += SIZE_MEMNUM; break; + p += SIZE_MEMNUM; + num_cache_opcodes_at_null_check_start = -1; + break; + case OP_NULL_CHECK_END_MEMST: + p += SIZE_MEMNUM; + // OP_NULL_CHECK_START and OP_NULL_CHECK_END_MEMST are counted as cache opcodes. + if (num_cache_opcodes_at_null_check_start < num_cache_opcodes) { + num_cache_opcodes += 2; + } + num_cache_opcodes_at_null_check_start = -1; + break; case OP_PUSH_POS: case OP_POP_POS: @@ -422,21 +454,21 @@ count_num_cache_opcode(regex_t* reg, long* num, long* table_size) case OP_PUSH_ABSENT_POS: case OP_ABSENT_END: case OP_ABSENT: - goto fail; + goto impossible; case OP_CALL: case OP_RETURN: - goto fail; + goto impossible; case OP_CONDITION: - goto fail; + goto impossible; case OP_STATE_CHECK_PUSH: case OP_STATE_CHECK_PUSH_OR_JUMP: case OP_STATE_CHECK: case OP_STATE_CHECK_ANYCHAR_STAR: case OP_STATE_CHECK_ANYCHAR_ML_STAR: - goto fail; + goto impossible; case OP_SET_OPTION_PUSH: case OP_SET_OPTION: @@ -444,32 +476,47 @@ count_num_cache_opcode(regex_t* reg, long* num, long* table_size) break; default: - goto bytecode_error; + goto bytecode_error; } } + *num_cache_opcodes_ptr = num_cache_opcodes; return 0; -fail: - *num = NUM_CACHE_OPCODE_FAIL; +impossible: + *num_cache_opcodes_ptr = NUM_CACHE_OPCODES_IMPOSSIBLE; return 0; bytecode_error: return ONIGERR_UNDEFINED_BYTECODE; } +/* collect cache opcodes from the given regex program, and compute the total number of cache points. */ static OnigPosition -init_cache_index_table(regex_t* reg, OnigCacheIndex *table) +init_cache_opcodes(const regex_t* reg, OnigCacheOpcode* cache_opcodes, long* num_cache_points_ptr) { UChar* pbegin; UChar* p = reg->p; UChar* pend = p + reg->used; LengthType len; - MemNumType mem; - MemNumType current_mem = -1; - long num = 0; - long current_mem_num = 0; + MemNumType repeat_mem; OnigEncoding enc = reg->enc; + MemNumType current_repeat_mem = -1; + long cache_point = 0; + long num_cache_points_at_repeat = 0; + OnigCacheOpcode* cache_opcodes_at_repeat = NULL; + UChar* null_check_start_addr = NULL; + OnigCacheOpcode* cache_opcodes_at_null_check_start = NULL; + +# define INC_CACHE_OPCODES do {\ + cache_opcodes->addr = pbegin;\ + cache_opcodes->cache_point = cache_point - num_cache_points_at_repeat;\ + cache_opcodes->outer_repeat_mem = current_repeat_mem;\ + cache_opcodes->num_cache_points_at_outer_repeat = num_cache_points_at_repeat;\ + cache_opcodes->num_cache_points_in_outer_repeat = 0;\ + cache_point++;\ + cache_opcodes++;\ + } while (0) while (p < pend) { pbegin = p; @@ -484,7 +531,7 @@ init_cache_index_table(regex_t* reg, OnigCacheIndex *table) case OP_EXACT4: p += 4; break; case OP_EXACT5: p += 5; break; case OP_EXACTN: - GET_LENGTH_INC(len, p); p += len; break; + GET_LENGTH_INC(len, p); p += len; break; case OP_EXACTMB2N1: p += 2; break; case OP_EXACTMB2N2: p += 4; break; case OP_EXACTMB2N3: p += 6; break; @@ -499,7 +546,7 @@ init_cache_index_table(regex_t* reg, OnigCacheIndex *table) GET_LENGTH_INC(len, p); p += mb_len * len; } - break; + break; case OP_EXACT1_IC: len = enclen(enc, p, pend); p += len; break; @@ -508,7 +555,7 @@ init_cache_index_table(regex_t* reg, OnigCacheIndex *table) case OP_CCLASS: case OP_CCLASS_NOT: - p += SIZE_BITSET; break; + p += SIZE_BITSET; break; case OP_CCLASS_MB: case OP_CCLASS_MB_NOT: GET_LENGTH_INC(len, p); p += len; break; @@ -524,20 +571,12 @@ init_cache_index_table(regex_t* reg, OnigCacheIndex *table) break; case OP_ANYCHAR_STAR: case OP_ANYCHAR_ML_STAR: - table->addr = pbegin; - table->num = num - current_mem_num; - table->outer_repeat = current_mem; - num++; - table++; + INC_CACHE_OPCODES; break; case OP_ANYCHAR_STAR_PEEK_NEXT: case OP_ANYCHAR_ML_STAR_PEEK_NEXT: p++; - table->addr = pbegin; - table->num = num - current_mem_num; - table->outer_repeat = current_mem; - num++; - table++; + INC_CACHE_OPCODES; break; case OP_WORD: @@ -587,68 +626,84 @@ init_cache_index_table(regex_t* reg, OnigCacheIndex *table) case OP_FAIL: break; case OP_JUMP: - p += SIZE_RELADDR; + p += SIZE_RELADDR; break; case OP_PUSH: - p += SIZE_RELADDR; - table->addr = pbegin; - table->num = num - current_mem_num; - table->outer_repeat = current_mem; - num++; - table++; + p += SIZE_RELADDR; + INC_CACHE_OPCODES; break; case OP_POP: break; case OP_PUSH_OR_JUMP_EXACT1: case OP_PUSH_IF_PEEK_NEXT: p += SIZE_RELADDR + 1; - table->addr = pbegin; - table->num = num - current_mem_num; - table->outer_repeat = current_mem; - num++; - table++; + INC_CACHE_OPCODES; break; case OP_REPEAT: case OP_REPEAT_NG: - GET_MEMNUM_INC(mem, p); + GET_MEMNUM_INC(repeat_mem, p); p += SIZE_RELADDR; - if (reg->repeat_range[mem].lower == 0) { - table->addr = pbegin; - table->num = num - current_mem_num; - table->outer_repeat = -1; - num++; - table++; + if (reg->repeat_range[repeat_mem].lower == 0) { + INC_CACHE_OPCODES; } - current_mem = mem; - current_mem_num = num; + current_repeat_mem = repeat_mem; + num_cache_points_at_repeat = cache_point; + cache_opcodes_at_repeat = cache_opcodes; break; case OP_REPEAT_INC: case OP_REPEAT_INC_NG: - GET_MEMNUM_INC(mem, p); + GET_MEMNUM_INC(repeat_mem, p); { - long inner_num = num - current_mem_num; - OnigRepeatRange *repeat_range = ®->repeat_range[mem]; + long num_cache_points_in_repeat = cache_point - num_cache_points_at_repeat; + OnigRepeatRange *repeat_range = ®->repeat_range[repeat_mem]; if (repeat_range->lower < repeat_range->upper) { - table->addr = pbegin; - table->num = num - current_mem_num; - table->outer_repeat = mem; - table++; + INC_CACHE_OPCODES; + cache_point--; + } + cache_point -= num_cache_points_in_repeat; + int repeat_bounds = repeat_range->upper == 0x7fffffff ? 1 : repeat_range->upper - repeat_range->lower; + cache_point += num_cache_points_in_repeat * repeat_range->lower + (num_cache_points_in_repeat + 1) * repeat_bounds; + OnigCacheOpcode* cache_opcodes_in_repeat = cache_opcodes - 1; + while (cache_opcodes_at_repeat <= cache_opcodes_in_repeat) { + cache_opcodes_in_repeat->num_cache_points_in_outer_repeat = num_cache_points_in_repeat; + cache_opcodes_in_repeat--; } - num -= inner_num; - num += inner_num * repeat_range->lower + (inner_num + 1) * (repeat_range->upper == 0x7fffffff ? 1 : repeat_range->upper - repeat_range->lower); - current_mem = -1; - current_mem_num = 0; + current_repeat_mem = -1; + num_cache_points_at_repeat = 0; + cache_opcodes_at_repeat = NULL; } break; case OP_REPEAT_INC_SG: case OP_REPEAT_INC_NG_SG: - // TODO: support OP_REPEAT opcodes. goto unexpected_bytecode_error; case OP_NULL_CHECK_START: + if (cache_opcodes_at_null_check_start != NULL) { + goto unexpected_bytecode_error; + } + p += SIZE_MEMNUM; + null_check_start_addr = pbegin; + cache_opcodes_at_null_check_start = cache_opcodes; + break; case OP_NULL_CHECK_END: - case OP_NULL_CHECK_END_MEMST: case OP_NULL_CHECK_END_MEMST_PUSH: - p += SIZE_MEMNUM; break; + p += SIZE_MEMNUM; + cache_opcodes_at_null_check_start = NULL; + break; + case OP_NULL_CHECK_END_MEMST: + p += SIZE_MEMNUM; + { + if (cache_opcodes_at_null_check_start < cache_opcodes) { + *cache_opcodes = *(cache_opcodes - 1); + cache_opcodes->addr = pbegin; + cache_opcodes++; + long num_cache_opcodes_in_null_check = (cache_opcodes - cache_opcodes_at_null_check_start); + xmemmove(cache_opcodes_at_null_check_start + 1, cache_opcodes_at_null_check_start, sizeof(OnigCacheOpcode) * num_cache_opcodes_in_null_check); + cache_opcodes_at_null_check_start->addr = null_check_start_addr; + cache_opcodes++; + } + cache_opcodes_at_null_check_start = NULL; + } + break; case OP_PUSH_POS: case OP_POP_POS: @@ -684,10 +739,11 @@ init_cache_index_table(regex_t* reg, OnigCacheIndex *table) break; default: - goto bytecode_error; + goto bytecode_error; } } + *num_cache_points_ptr = cache_point; return 0; unexpected_bytecode_error: @@ -696,21 +752,21 @@ unexpected_bytecode_error: bytecode_error: return ONIGERR_UNDEFINED_BYTECODE; } -#else /* USE_MATCH_CACHE */ +#else static OnigPosition -count_num_cache_opcode(regex_t* reg, long* num, long* table_size) +count_num_cache_opcodes(regex_t* reg, long* num_cache_opcodes) { - *num = NUM_CACHE_OPCODE_FAIL; + *num_cache_opcodes = NUM_CACHE_OPCODES_IMPOSSIBLE; return 0; } -#endif +#endif /* USE_MATCH_CACHE */ extern int onig_check_linear_time(OnigRegexType* reg) { - long num = 0, table_size = 0; - count_num_cache_opcode(reg, &num, &table_size); - return num != NUM_CACHE_OPCODE_FAIL; + long num_cache_opcodes = 0; + count_num_cache_opcodes(reg, &num_cache_opcodes); + return num_cache_opcodes != NUM_CACHE_OPCODES_IMPOSSIBLE; } extern void @@ -895,22 +951,24 @@ onig_region_copy(OnigRegion* to, const OnigRegion* from) #define STK_MASK_TO_VOID_TARGET 0x10ff #define STK_MASK_MEM_END_OR_MARK 0x8000 /* MEM_END or MEM_END_MARK */ -#ifdef USE_CACHE_MATCH_OPT -#define MATCH_ARG_INIT_CACHE_MATCH_OPT(msa) do {\ - (msa).enable_cache_match_opt = 0;\ - (msa).num_fail = 0;\ - (msa).num_cache_opcode = NUM_CACHE_OPCODE_UNINIT;\ - (msa).num_cache_table = 0;\ - (msa).cache_index_table = (OnigCacheIndex *)0;\ - (msa).match_cache = (uint8_t *)0;\ +#ifdef USE_MATCH_CACHE +#define MATCH_ARG_INIT_MATCH_CACHE(msa) do {\ + (msa).enable_match_cache = 0;\ + (msa).num_fails = 0;\ + (msa).num_cache_opcodes = NUM_CACHE_OPCODES_UNINIT;\ + (msa).cache_opcodes = (OnigCacheOpcode*)NULL;\ + (msa).num_cache_points = 0;\ + (msa).match_cache_buf = (uint8_t*)NULL;\ } while(0) -#define MATCH_ARG_FREE_CACHE_MATCH_OPT(msa) do {\ - if ((msa).cache_index_table) xfree((msa).cache_index_table);\ - if ((msa).match_cache) xfree((msa).match_cache);\ +#define MATCH_ARG_FREE_MATCH_CACHE(msa) do {\ + if ((msa).cache_opcodes != NULL) xfree((msa).cache_opcodes);\ + if ((msa).match_cache_buf != NULL) xfree((msa).match_cache_buf);\ + (msa).cache_opcodes = (OnigCacheOpcode*)NULL;\ + (msa).match_cache_buf = (uint8_t*)NULL;\ } while(0) #else -#define MATCH_ARG_INIT_CACHE_MATCH_OPT(msa) -#define MATCH_ARG_FREE_CACHE_MATCH_OPT(msa) +#define MATCH_ARG_INIT_MATCH_CACHE(msa) +#define MATCH_ARG_FREE_MATCH_CACHE(msa) #endif #ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE @@ -923,7 +981,7 @@ onig_region_copy(OnigRegion* to, const OnigRegion* from) (msa).best_len = ONIG_MISMATCH;\ (msa).counter = 0;\ (msa).end_time = 0;\ - MATCH_ARG_INIT_CACHE_MATCH_OPT(msa);\ + MATCH_ARG_INIT_MATCH_CACHE(msa);\ } while(0) #else # define MATCH_ARG_INIT(msa, arg_option, arg_region, arg_start, arg_gpos) do {\ @@ -934,7 +992,7 @@ onig_region_copy(OnigRegion* to, const OnigRegion* from) (msa).gpos = (arg_gpos);\ (msa).counter = 0;\ (msa).end_time = 0;\ - MATCH_ARG_INIT_CACHE_MATCH_OPT(msa);\ + MATCH_ARG_INIT_MATCH_CACHE(msa);\ } while(0) #endif @@ -973,12 +1031,12 @@ onig_region_copy(OnigRegion* to, const OnigRegion* from) if ((msa).state_check_buff_size >= STATE_CHECK_BUFF_MALLOC_THRESHOLD_SIZE) { \ if ((msa).state_check_buff) xfree((msa).state_check_buff);\ }\ - MATCH_ARG_FREE_CACHE_MATCH_OPT(msa);\ + MATCH_ARG_FREE_MATCH_CACHE(msa);\ } while(0) #else /* USE_COMBINATION_EXPLOSION_CHECK */ # define MATCH_ARG_FREE(msa) do {\ if ((msa).stack_p) xfree((msa).stack_p);\ - MATCH_ARG_FREE_CACHE_MATCH_OPT(msa);\ + MATCH_ARG_FREE_MATCH_CACHE(msa);\ } while (0) #endif /* USE_COMBINATION_EXPLOSION_CHECK */ @@ -1195,126 +1253,6 @@ stack_double(OnigStackType** arg_stk_base, OnigStackType** arg_stk_end, #define STACK_PUSH_LOOK_BEHIND_NOT(pat,s,sprev,keep) \ STACK_PUSH(STK_LOOK_BEHIND_NOT,pat,s,sprev,keep) -#ifdef USE_CACHE_MATCH_OPT - -#define DO_CACHE_MATCH_OPT(reg,stk,repeat_stk,enable,p,num_cache_table,num_cache_size,table,pos,match_cache) do {\ - if (enable) {\ - long cache_index = find_cache_index_table((reg), (stk), (repeat_stk), (table), (num_cache_table), (p));\ - if (cache_index >= 0) {\ - long key = (num_cache_size) * (long)(pos) + cache_index;\ - long index = key >> 3;\ - long mask = 1 << (key & 7);\ - if ((match_cache)[index] & mask) {\ - goto fail;\ - }\ - (match_cache)[index] |= mask;\ - }\ - }\ -} while (0) - -static long -bsearch_cache_index(const OnigCacheIndex *table, long num_cache_table, const UChar* p) -{ - long l = 0, r = num_cache_table - 1, m = 0; - - while (l <= r) { - m = (l + r) / 2; - if (table[m].addr == p) break; - if (table[m].addr < p) l = m + 1; - else r = m - 1; - } - return m; -} - -static long -find_cache_index_table(regex_t* reg, const OnigStackType *stk, const OnigStackIndex *repeat_stk, const OnigCacheIndex* table, long num_cache_table, const UChar* p) -{ - long m; - const OnigCacheIndex* item; - const OnigRepeatRange* range; - const OnigStackType *stkp; - int count = 0; - int is_inc = *p == OP_REPEAT_INC || *p == OP_REPEAT_INC_NG; - - m = bsearch_cache_index(table, num_cache_table, p); - - if (!(0 <= m && m < num_cache_table && table[m].addr == p)) { - return -1; - } - - item = &table[m]; - if (item->outer_repeat == -1) { - return item->num; - } - - range = ®->repeat_range[item->outer_repeat]; - - stkp = &stk[repeat_stk[item->outer_repeat]]; - count = is_inc ? stkp->u.repeat.count - 1 : stkp->u.repeat.count; - - if (count < range->lower) { - return range->base_num + range->inner_num * count + item->num; - } - - if (range->upper == 0x7fffffff) { - return range->base_num + range->inner_num * (range->lower - (is_inc ? 1 : 0)) + (is_inc ? 0 : 1) + item->num; - } - - return range->base_num + range->inner_num * (range->lower - 1) + (range->inner_num + 1) * (count - range->lower + 1) + item->num; -} - -static void -reset_match_cache(regex_t* reg, const UChar* pbegin, const UChar* pend, long pos, uint8_t* match_cache, const OnigCacheIndex *table, long num_cache_size, long num_cache_table) -{ - long m1 = 0, m2 = 0; - int is_inc = *pend == OP_REPEAT_INC || *pend == OP_REPEAT_INC_NG; - const OnigCacheIndex *item1, *item2; - long k1, k2, base; - - m1 = bsearch_cache_index(table, num_cache_table, pbegin); - m2 = bsearch_cache_index(table, num_cache_table, pend); - - if (table[m1].addr < pbegin && m1 + 1 < num_cache_table) m1++; - if (table[m2].addr > pend && m2 - 1 > 0) m2--; - - item1 = &table[m1]; - item2 = &table[m2]; - - if (item1->outer_repeat < 0) k1 = item1->num; - else k1 = reg->repeat_range[item1->outer_repeat].base_num + item1->num; - - if (item2->outer_repeat < 0) k2 = item2->num; - else { - OnigRepeatRange *range = ®->repeat_range[item2->outer_repeat]; - if (range->upper == 0x7fffffff) k2 = range->base_num + range->inner_num * range->lower + (is_inc ? 0 : 1) + item2->num; - else k2 = range->base_num + range->inner_num * range->lower + (range->inner_num + 1) * (range->upper - range->lower - (is_inc ? 1 : 0)) + item2->num; - } - - base = pos * num_cache_size; - k1 += base; - k2 += base; - - if ((k1 >> 3) == (k2 >> 3)) { - match_cache[k1 >> 3] &= (((1 << (8 - (k2 & 7) - 1)) - 1) << ((k2 & 7) + 1)) | ((1 << (k1 & 7)) - 1); - } else { - long i = k1 >> 3; - if (k1 & 7) { - match_cache[k1 >> 3] &= (1 << ((k1 & 7) - 1)) - 1; - i++; - } - if (i < (k2 >> 3)) { - xmemset(&match_cache[i], 0, (k2 >> 3) - i); - if (k2 & 7) { - match_cache[k2 >> 3] &= (((1 << (8 - (k2 & 7) - 1)) - 1) << ((k2 & 7) + 1)); - } - } - } -} - -#else -#define DO_CACHE_MATCH_OPT(reg,stk,repeat_stk,enable,p,num_cache_table,num_cache_size,table,pos,match_cache) -#endif /* USE_CACHE_MATCH_OPT */ - #define STACK_PUSH_REPEAT(id, pat) do {\ STACK_ENSURE(1);\ stk->type = STK_REPEAT;\ @@ -2066,6 +2004,122 @@ stack_type_str(int stack_type) } } #endif +#ifdef USE_MATCH_CACHE + +static long +bsearch_cache_opcodes(const OnigCacheOpcode *cache_opcodes, long num_cache_opcodes, const UChar* p) +{ + long l = 0, r = num_cache_opcodes - 1, m = 0; + + while (l <= r) { + m = (l + r) / 2; + if (cache_opcodes[m].addr == p) break; + if (cache_opcodes[m].addr < p) l = m + 1; + else r = m - 1; + } + return m; +} + +static long +find_cache_point(regex_t* reg, const OnigCacheOpcode* cache_opcodes, long num_cache_opcodes, const UChar* p, const OnigStackType *stk, const OnigStackIndex *repeat_stk) +{ + long m; + const OnigCacheOpcode* cache_opcode; + const OnigRepeatRange* range; + const OnigStackType *stkp; + int count = 0; + int is_inc = *p == OP_REPEAT_INC || *p == OP_REPEAT_INC_NG; + long cache_point; + long num_cache_points_at_outer_repeat; + long num_cache_points_in_outer_repeat; + + m = bsearch_cache_opcodes(cache_opcodes, num_cache_opcodes, p); + + if (!(0 <= m && m < num_cache_opcodes && cache_opcodes[m].addr == p)) { + return -1; + } + + cache_opcode = &cache_opcodes[m]; + cache_point = cache_opcode->cache_point; + if (cache_opcode->outer_repeat_mem == -1) { + return cache_point; + } + + num_cache_points_at_outer_repeat = cache_opcode->num_cache_points_at_outer_repeat; + num_cache_points_in_outer_repeat = cache_opcode->num_cache_points_in_outer_repeat; + + range = ®->repeat_range[cache_opcode->outer_repeat_mem]; + + stkp = &stk[repeat_stk[cache_opcode->outer_repeat_mem]]; + count = is_inc ? stkp->u.repeat.count - 1 : stkp->u.repeat.count; + + if (count < range->lower) { + return num_cache_points_at_outer_repeat + + num_cache_points_in_outer_repeat * count + + cache_point; + } + + if (range->upper == 0x7fffffff) { + return num_cache_points_at_outer_repeat + + num_cache_points_in_outer_repeat * (range->lower - (is_inc ? 1 : 0)) + (is_inc ? 0 : 1) + + cache_point; + } + + return num_cache_points_at_outer_repeat + + num_cache_points_in_outer_repeat * (range->lower - 1) + + (num_cache_points_in_outer_repeat + 1) * (count - range->lower + 1) + + cache_point; +} + +static void +reset_match_cache_on_null_check(regex_t* reg, const UChar* pstart, const UChar* pend, long pos, uint8_t* match_cache_buf, const OnigCacheOpcode* cache_opcodes, long num_cache_opcodes, long num_cache_points, const OnigStackType *stk, const OnigStackIndex *repeat_stk) +{ + long cache_point_start, cache_point_end; + long match_cache_point_start, match_cache_point_end; + long match_cache_point_start_index, match_cache_point_end_index; + uint8_t match_cache_point_start_bit, match_cache_point_end_bit; + +#ifdef ONIG_DEBUG_MATCH_CACHE + fprintf(stderr, "MATCH CACHE: reset start=%p end=%p pos=%ld cache_opcodes=%p num_cache_opcodes=%ld\n", pstart, pend, pos, cache_opcodes, num_cache_opcodes); +#endif + + cache_point_start = find_cache_point(reg, cache_opcodes, num_cache_opcodes, pstart, stk, repeat_stk); + cache_point_end = find_cache_point(reg, cache_opcodes, num_cache_opcodes, pend, stk, repeat_stk); + // Skip to reset if `pstart` or `pend` is not found. + // This situation occurs when there is no cache point + // between OP_NULL_CHECK_START and OP_NULL_CHECK_END_MEMST. + if (cache_point_start == -1 || cache_point_end == -1) return; + + match_cache_point_start = pos * num_cache_points + cache_point_start; + match_cache_point_end = pos * num_cache_points + cache_point_end; + match_cache_point_start_index = match_cache_point_start >> 3; + match_cache_point_end_index = match_cache_point_end >> 3; + match_cache_point_start_bit = match_cache_point_start & 7; + match_cache_point_end_bit = match_cache_point_end & 7; + +#ifdef ONIG_DEBUG_MATCH_CACHE + fprintf(stderr, "MATCH CACHE: reset start %ld (%ld index=%ld bits=%d)\n", match_cache_point_start, cache_point_start, match_cache_point_start_index, match_cache_point_start_bits); + fprintf(stderr, "MATCH CACHE: reset end %ld (%ld index=%ld bits=%d)\n", match_cache_point_end, cache_point_end, match_cache_point_end_index, match_cache_point_end_bits); +#endif + + if (match_cache_point_start_index == match_cache_point_end_index) { + match_cache_buf[match_cache_point_start_index] &= + (((1 << (8 - match_cache_point_end_bit - 1)) - 1) << (match_cache_point_end_bit + 1)) | + ((1 << match_cache_point_start_bit) - 1); + } else { + if (match_cache_point_start_bit) { + match_cache_buf[match_cache_point_start_index] &= (1 << (match_cache_point_start_bit - 1)) - 1; + match_cache_point_start_index++; + } + if (match_cache_point_start_index < match_cache_point_end_index) { + xmemset(&match_cache_buf[match_cache_point_start_index], 0, match_cache_point_end_index - match_cache_point_start_index); + if (match_cache_point_end_bit) { + match_cache_buf[match_cache_point_end_index] &= (((1 << (8 - match_cache_point_end_bit - 1)) - 1) << (match_cache_point_end_bit + 1)); + } + } + } +} +#endif /* USE_MATCH_CACHE */ /* match data(str - end) from position (sstart). */ /* if sstart == str then set sprev to NULL. */ @@ -2374,6 +2428,34 @@ match_at(regex_t* reg, const UChar* str, const UChar* end, # define OPCODE_EXEC_HOOK ((void) 0) #endif +#ifdef USE_MATCH_CACHE +#ifdef ONIG_DEBUG_MATCH_CACHE +#define MATCH_CACHE_DEBUG fprintf(stderr, "MATCH CACHE: cache %ld (p=%p index=%ld mask=%d)\n", match_cache_point, pbegin, match_cache_point_index, match_cache_point_mask) +#define MATCH_CACHE_DEBUG_HIT fprintf(stderr, "MATCH CACHE: cache hit\n") +#else +#define MATCH_CACHE_DEBUG ((void) 0) +#define MATCH_CACHE_DEBUG_HIT ((void) 0) +#endif + +# define CHECK_MATCH_CACHE do {\ + if (msa->enable_match_cache) {\ + long cache_point = find_cache_point(reg, msa->cache_opcodes, msa->num_cache_opcodes, pbegin, stk_base, repeat_stk);\ + if (cache_point >= 0) {\ + long match_cache_point = msa->num_cache_points * (long)(s - str) + cache_point;\ + long match_cache_point_index = match_cache_point >> 3;\ + uint8_t match_cache_point_mask = 1 << (match_cache_point & 7);\ + MATCH_CACHE_DEBUG;\ + if (msa->match_cache_buf[match_cache_point_index] & match_cache_point_mask) {\ + MATCH_CACHE_DEBUG_HIT;\ + goto fail;\ + }\ + msa->match_cache_buf[match_cache_point_index] |= match_cache_point_mask;\ + }\ + }\ +} while (0) +#else +# define CHECK_MATCH_CACHE ((void) 0) +#endif VM_LOOP { CASE(OP_END) MOP_IN(OP_END); @@ -2801,7 +2883,7 @@ match_at(regex_t* reg, const UChar* str, const UChar* end, CASE(OP_ANYCHAR_STAR) MOP_IN(OP_ANYCHAR_STAR); while (DATA_ENSURE_CHECK1) { - DO_CACHE_MATCH_OPT(reg, stk_base, repeat_stk, msa->enable_cache_match_opt, pbegin, msa->num_cache_table, msa->num_cache_opcode, msa->cache_index_table, s - str, msa->match_cache); + CHECK_MATCH_CACHE; STACK_PUSH_ALT(p, s, sprev, pkeep); n = enclen(encode, s, end); DATA_ENSURE(n); @@ -2814,7 +2896,7 @@ match_at(regex_t* reg, const UChar* str, const UChar* end, CASE(OP_ANYCHAR_ML_STAR) MOP_IN(OP_ANYCHAR_ML_STAR); while (DATA_ENSURE_CHECK1) { - DO_CACHE_MATCH_OPT(reg, stk_base, repeat_stk, msa->enable_cache_match_opt, pbegin, msa->num_cache_table, msa->num_cache_opcode, msa->cache_index_table, s - str, msa->match_cache); + CHECK_MATCH_CACHE; STACK_PUSH_ALT(p, s, sprev, pkeep); n = enclen(encode, s, end); if (n > 1) { @@ -2832,16 +2914,16 @@ match_at(regex_t* reg, const UChar* str, const UChar* end, CASE(OP_ANYCHAR_STAR_PEEK_NEXT) MOP_IN(OP_ANYCHAR_STAR_PEEK_NEXT); while (DATA_ENSURE_CHECK1) { - DO_CACHE_MATCH_OPT(reg, stk_base, repeat_stk, msa->enable_cache_match_opt, pbegin, msa->num_cache_table, msa->num_cache_opcode, msa->cache_index_table, end - s, msa->match_cache); + CHECK_MATCH_CACHE; if (*p == *s) { STACK_PUSH_ALT(p + 1, s, sprev, pkeep); } else { - /* We need to increment num_fail here, for invoking a cache optimization correctly. */ - /* Actually, the matching will be failed if we use `OP_ANYCHAR_STAR` simply in this case.*/ -#ifdef USE_CACHE_MATCH_OPT - msa->num_fail++; +#ifdef USE_MATCH_CACHE + /* We need to increment num_fails here, for invoking a cache optimization correctly. */ + /* Actually, the matching will be failed if we use `OP_ANYCHAR_STAR` simply in this case.*/ + msa->num_fails++; #endif - } + } n = enclen(encode, s, end); DATA_ENSURE(n); if (ONIGENC_IS_MBC_NEWLINE_EX(encode, s, str, end, option, 0)) goto fail; @@ -2854,16 +2936,16 @@ match_at(regex_t* reg, const UChar* str, const UChar* end, CASE(OP_ANYCHAR_ML_STAR_PEEK_NEXT)MOP_IN(OP_ANYCHAR_ML_STAR_PEEK_NEXT); while (DATA_ENSURE_CHECK1) { - DO_CACHE_MATCH_OPT(reg, stk_base, repeat_stk, msa->enable_cache_match_opt, pbegin, msa->num_cache_table, msa->num_cache_opcode, msa->cache_index_table, s - str, msa->match_cache); + CHECK_MATCH_CACHE; if (*p == *s) { STACK_PUSH_ALT(p + 1, s, sprev, pkeep); } else { - /* We need to increment num_fail here, for invoking a cache optimization correctly. */ - /* Actually, the matching will be failed if we use `OP_ANYCHAR_STAR_ML` simply in this case.*/ -#ifdef USE_CACHE_MATCH_OPT - msa->num_fail++; +#ifdef USE_MATCH_CACHE + /* We need to increment num_fails here, for invoking a cache optimization correctly. */ + /* Actually, the matching will be failed if we use `OP_ANYCHAR_STAR_ML` simply in this case.*/ + msa->num_fails++; #endif - } + } n = enclen(encode, s, end); if (n > 1) { DATA_ENSURE(n); @@ -3460,27 +3542,29 @@ match_at(regex_t* reg, const UChar* str, const UChar* end, if (isnull == -1) goto fail; goto null_check_found; } -# ifdef USE_CACHE_MATCH_OPT - if (ischanged && msa->enable_cache_match_opt) { +# ifdef USE_MATCH_CACHE + if (ischanged && msa->enable_match_cache) { RelAddrType rel; - OnigUChar *addr; + OnigUChar *null_check_start; + OnigUChar *null_check_end = pbegin; MemNumType mem; UChar* tmp = p; switch (*tmp++) { case OP_JUMP: case OP_PUSH: GET_RELADDR_INC(rel, tmp); - addr = tmp + rel; + null_check_start = tmp + rel; break; case OP_REPEAT_INC: case OP_REPEAT_INC_NG: GET_MEMNUM_INC(mem, tmp); - addr = STACK_AT(repeat_stk[mem])->u.repeat.pcode; + // Skip OP_REPEAT (or OP_REPEAT_NG) + null_check_start = STACK_AT(repeat_stk[mem])->u.repeat.pcode; break; default: goto unexpected_bytecode_error; } - reset_match_cache(reg, addr, pbegin, (long)(s - str), msa->match_cache, msa->cache_index_table, msa->num_cache_opcode, msa->num_cache_table); + reset_match_cache_on_null_check(reg, null_check_start, null_check_end, (long)(s - str), msa->match_cache_buf, msa->cache_opcodes, msa->num_cache_opcodes, msa->num_cache_points, stk_base, repeat_stk); } # endif } @@ -3525,7 +3609,7 @@ match_at(regex_t* reg, const UChar* str, const UChar* end, CASE(OP_PUSH) MOP_IN(OP_PUSH); GET_RELADDR_INC(addr, p); - DO_CACHE_MATCH_OPT(reg, stk_base, repeat_stk, msa->enable_cache_match_opt, pbegin, msa->num_cache_table, msa->num_cache_opcode, msa->cache_index_table, s - str, msa->match_cache); + CHECK_MATCH_CACHE; STACK_PUSH_ALT(p + addr, s, sprev, pkeep); MOP_OUT; JUMP; @@ -3566,10 +3650,10 @@ match_at(regex_t* reg, const UChar* str, const UChar* end, CASE(OP_POP) MOP_IN(OP_POP); STACK_POP_ONE; - /* We need to increment num_fail here, for invoking a cache optimization correctly, */ +#ifdef USE_MATCH_CACHE + /* We need to increment num_fails here, for invoking a cache optimization correctly, */ /* because Onigmo makes a loop, which is pairwise disjoint to the following set, as atomic. */ -#ifdef USE_CACHE_MATCH_OPT - msa->num_fail++; + msa->num_fails++; #endif MOP_OUT; JUMP; @@ -3579,7 +3663,7 @@ match_at(regex_t* reg, const UChar* str, const UChar* end, GET_RELADDR_INC(addr, p); if (*p == *s && DATA_ENSURE_CHECK1) { p++; - DO_CACHE_MATCH_OPT(reg, stk_base, repeat_stk, msa->enable_cache_match_opt, pbegin, msa->num_cache_table, msa->num_cache_opcode, msa->cache_index_table, s - str, msa->match_cache); + CHECK_MATCH_CACHE; STACK_PUSH_ALT(p + addr, s, sprev, pkeep); MOP_OUT; JUMP; @@ -3593,7 +3677,7 @@ match_at(regex_t* reg, const UChar* str, const UChar* end, GET_RELADDR_INC(addr, p); if (*p == *s) { p++; - DO_CACHE_MATCH_OPT(reg, stk_base, repeat_stk, msa->enable_cache_match_opt, pbegin, msa->num_cache_table, msa->num_cache_opcode, msa->cache_index_table, s - str, msa->match_cache); + CHECK_MATCH_CACHE; STACK_PUSH_ALT(p + addr, s, sprev, pkeep); MOP_OUT; JUMP; @@ -3612,7 +3696,7 @@ match_at(regex_t* reg, const UChar* str, const UChar* end, STACK_PUSH_REPEAT(mem, p); if (reg->repeat_range[mem].lower == 0) { - DO_CACHE_MATCH_OPT(reg, stk_base, repeat_stk, msa->enable_cache_match_opt, pbegin, msa->num_cache_table, msa->num_cache_opcode, msa->cache_index_table, end - s, msa->match_cache); + CHECK_MATCH_CACHE; STACK_PUSH_ALT(p + addr, s, sprev, pkeep); } } @@ -3629,7 +3713,7 @@ match_at(regex_t* reg, const UChar* str, const UChar* end, STACK_PUSH_REPEAT(mem, p); if (reg->repeat_range[mem].lower == 0) { - DO_CACHE_MATCH_OPT(reg, stk_base, repeat_stk, msa->enable_cache_match_opt, pbegin, msa->num_cache_table, msa->num_cache_opcode, msa->cache_index_table, s - str, msa->match_cache); + CHECK_MATCH_CACHE; STACK_PUSH_ALT(p, s, sprev, pkeep); p += addr; } @@ -3649,7 +3733,7 @@ match_at(regex_t* reg, const UChar* str, const UChar* end, } else if (stkp->u.repeat.count >= reg->repeat_range[mem].lower) { if (*pbegin == OP_REPEAT_INC) { - DO_CACHE_MATCH_OPT(reg, stk_base, repeat_stk, msa->enable_cache_match_opt, pbegin, msa->num_cache_table, msa->num_cache_opcode, msa->cache_index_table, s - str, msa->match_cache); + CHECK_MATCH_CACHE; } STACK_PUSH_ALT(p, s, sprev, pkeep); p = STACK_AT(si)->u.repeat.pcode; /* Don't use stkp after PUSH. */ @@ -3682,7 +3766,7 @@ match_at(regex_t* reg, const UChar* str, const UChar* end, STACK_PUSH_REPEAT_INC(si); if (*pbegin == OP_REPEAT_INC_NG) { - DO_CACHE_MATCH_OPT(reg, stk_base, repeat_stk, msa->enable_cache_match_opt, pbegin, msa->num_cache_table, msa->num_cache_opcode, msa->cache_index_table, s - str, msa->match_cache); + CHECK_MATCH_CACHE; } STACK_PUSH_ALT(pcode, s, sprev, pkeep); } @@ -3876,45 +3960,58 @@ match_at(regex_t* reg, const UChar* str, const UChar* end, sprev = stk->u.state.pstr_prev; pkeep = stk->u.state.pkeep; -#ifdef USE_CACHE_MATCH_OPT - if (++msa->num_fail >= (long)(end - str) + 1 && msa->num_cache_opcode == NUM_CACHE_OPCODE_UNINIT) { - msa->enable_cache_match_opt = 1; - if (msa->num_cache_opcode == NUM_CACHE_OPCODE_UNINIT) { - OnigPosition r = count_num_cache_opcode(reg, &msa->num_cache_opcode, &msa->num_cache_table); - if (r < 0) goto bytecode_error; +#ifdef USE_MATCH_CACHE + if (++msa->num_fails >= (long)(end - str) + 1 && msa->num_cache_opcodes == NUM_CACHE_OPCODES_UNINIT) { + msa->enable_match_cache = 1; + if (msa->num_cache_opcodes == NUM_CACHE_OPCODES_UNINIT) { + OnigPosition r = count_num_cache_opcodes(reg, &msa->num_cache_opcodes); + if (r < 0) goto bytecode_error; } - if (msa->num_cache_opcode == NUM_CACHE_OPCODE_FAIL || msa->num_cache_opcode == 0) { - msa->enable_cache_match_opt = 0; + if (msa->num_cache_opcodes == NUM_CACHE_OPCODES_IMPOSSIBLE || msa->num_cache_opcodes == 0) { + msa->enable_match_cache = 0; goto fail_match_cache_opt; } - if (msa->cache_index_table == NULL) { - OnigCacheIndex *table = (OnigCacheIndex *)xmalloc(msa->num_cache_table * sizeof(OnigCacheIndex)); - if (table == NULL) { + if (msa->cache_opcodes == NULL) { + OnigCacheOpcode* cache_opcodes = (OnigCacheOpcode*)xmalloc(msa->num_cache_opcodes * sizeof(OnigCacheOpcode)); + if (cache_opcodes == NULL) { return ONIGERR_MEMORY; } - OnigPosition r = init_cache_index_table(reg, table); - if (r < 0) { - if (r == ONIGERR_UNEXPECTED_BYTECODE) goto unexpected_bytecode_error; - else goto bytecode_error; - } - msa->cache_index_table = table; - } - size_t len = (end - str) + 1; - size_t match_cache_size8 = (size_t)msa->num_cache_opcode * len; - /* overflow check */ - if (match_cache_size8 / len != (size_t)msa->num_cache_opcode) { - return ONIGERR_MEMORY; - } - /* Currently, int is used for the key of match_cache */ - if (match_cache_size8 >= LONG_MAX_LIMIT) { - return ONIGERR_MEMORY; + OnigPosition r = init_cache_opcodes(reg, cache_opcodes, &msa->num_cache_points); + if (r < 0) { + if (r == ONIGERR_UNEXPECTED_BYTECODE) goto unexpected_bytecode_error; + else goto bytecode_error; + } + msa->cache_opcodes = cache_opcodes; +#ifdef ONIG_DEBUG_MATCH_CACHE + fprintf(stderr, "MATCH CACHE: #cache opcodes = %ld\n", msa->num_cache_opcodes); + fprintf(stderr, "MATCH CACHE: #cache points = %ld\n", msa->num_cache_points); + fprintf(stderr, "MATCH CACHE: cache opcodes (%p):\n", msa->cache_opcodes); + for (int i = 0; i < msa->num_cache_opcodes; i++) { + fprintf(stderr, "MATCH CACHE: [%p] cache_point=%ld outer_repeat_mem=%d num_cache_opcodes_at_outer_repeat=%ld num_cache_opcodes_in_outer_repeat=%ld\n", msa->cache_opcodes[i].addr, msa->cache_opcodes[i].cache_point, msa->cache_opcodes[i].outer_repeat_mem, msa->cache_opcodes[i].num_cache_points_at_outer_repeat, msa->cache_opcodes[i].num_cache_points_in_outer_repeat); + } +#endif } - size_t match_cache_size = (match_cache_size8 >> 3) + (match_cache_size8 & 7 ? 1 : 0); - msa->match_cache = (uint8_t*)xmalloc(match_cache_size * sizeof(uint8_t)); - if (msa->match_cache == NULL) { - return ONIGERR_MEMORY; + if (msa->match_cache_buf == NULL) { + size_t length = (end - str) + 1; + size_t num_match_cache_points = (size_t)msa->num_cache_points * length; +#ifdef ONIG_DEBUG_MATCH_CACHE + fprintf(stderr, "MATCH CACHE: #match cache points = %ld (length = %zu)\n", num_match_cache_points, length); +#endif + /* Overflow check */ + if (num_match_cache_points / length != (size_t)msa->num_cache_points) { + return ONIGERR_MEMORY; + } + if (num_match_cache_points >= LONG_MAX_LIMIT) { + return ONIGERR_MEMORY; + } + size_t match_cache_buf_length = (num_match_cache_points >> 3) + (num_match_cache_points & 7 ? 1 : 0); + uint8_t* match_cache_buf = (uint8_t*)xmalloc(match_cache_buf_length * sizeof(uint8_t)); + if (match_cache_buf == NULL) { + return ONIGERR_MEMORY; + } + xmemset(match_cache_buf, 0, match_cache_buf_length * sizeof(uint8_t)); + msa->match_cache_buf = match_cache_buf; } - xmemset(msa->match_cache, 0, match_cache_size * sizeof(uint8_t)); } fail_match_cache_opt: #endif -- cgit v1.2.3