To: vim_dev@googlegroups.com Subject: Patch 8.2.5115 Fcc: outbox From: Bram Moolenaar Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit ------------ Patch 8.2.5115 Problem: Search timeout is overrun with some patterns. Solution: Check for timeout in more places. Make the flag volatile and atomic. Use assert_inrange() to see what happened. Files: src/regexp_nfa.c, src/regexp_bt.c, src/regexp.c, src/os_unix.c, src/proto/os_unix.pro, src/testdir/test_search.vim *** ../vim-8.2.5114/src/regexp_nfa.c 2022-06-05 16:55:50.698774344 +0100 --- src/regexp_nfa.c 2022-06-17 15:15:19.100633619 +0100 *************** *** 4237,4242 **** --- 4237,4263 ---- return TRUE; } + #ifdef FEAT_RELTIME + /* + * Check if we are past the time limit, if there is one. + */ + static int + nfa_did_time_out(void) + { + if (*timeout_flag) + { + if (nfa_timed_out != NULL) + { + if (!*nfa_timed_out) + ch_log(NULL, "NFA regexp timed out"); + *nfa_timed_out = TRUE; + } + return TRUE; + } + return FALSE; + } + #endif + #ifdef ENABLE_LOG static void open_debug_log(int result) *************** *** 4451,4457 **** /* * Add "state" and possibly what follows to state list ".". * Returns "subs_arg", possibly copied into temp_subs. ! * Returns NULL when recursiveness is too deep. */ static regsubs_T * addstate( --- 4472,4478 ---- /* * Add "state" and possibly what follows to state list ".". * Returns "subs_arg", possibly copied into temp_subs. ! * Returns NULL when recursiveness is too deep or timed out. */ static regsubs_T * addstate( *************** *** 4480,4485 **** --- 4501,4511 ---- #endif static int depth = 0; + #ifdef FEAT_RELTIME + if (nfa_did_time_out()) + return NULL; + #endif + // This function is called recursively. When the depth is too much we run // out of stack and crash, limit recursiveness here. if (++depth >= 5000 || subs == NULL) *************** *** 5643,5666 **** return 0L; } - #ifdef FEAT_RELTIME - /* - * Check if we are past the time limit, if there is one. - * To reduce overhead, only check one in "count" times. - */ - static int - nfa_did_time_out(void) - { - if (*timeout_flag) - { - if (nfa_timed_out != NULL) - *nfa_timed_out = TRUE; - return TRUE; - } - return FALSE; - } - #endif - /* * Main matching routine. * --- 5669,5674 ---- *************** *** 5708,5714 **** if (got_int) return FALSE; #ifdef FEAT_RELTIME - // Check relatively often here, since this is the toplevel matching. if (nfa_did_time_out()) return FALSE; #endif --- 5716,5721 ---- *************** *** 7109,7115 **** if (got_int) break; #ifdef FEAT_RELTIME - // Check for timeout once in a twenty times to avoid overhead. if (nfa_did_time_out()) break; #endif --- 7116,7121 ---- *** ../vim-8.2.5114/src/regexp_bt.c 2022-06-05 16:55:50.698774344 +0100 --- src/regexp_bt.c 2022-06-17 15:13:46.460843217 +0100 *************** *** 3152,3157 **** --- 3152,3178 ---- regstack.ga_len -= sizeof(regitem_T); } + #ifdef FEAT_RELTIME + /* + * Check if the timer expired, return TRUE if so. + */ + static int + bt_did_time_out(int *timed_out) + { + if (*timeout_flag) + { + if (timed_out != NULL) + { + if (!*timed_out) + ch_log(NULL, "BT regexp timed out"); + *timed_out = TRUE; + } + return TRUE; + } + return FALSE; + } + #endif + /* * Save the current subexpr to "bp", so that they can be restored * later by restore_subexpr(). *************** *** 3267,3276 **** break; } #ifdef FEAT_RELTIME ! if (*timeout_flag) { - if (timed_out != NULL) - *timed_out = TRUE; status = RA_FAIL; break; } --- 3288,3295 ---- break; } #ifdef FEAT_RELTIME ! if (bt_did_time_out(timed_out)) { status = RA_FAIL; break; } *************** *** 4687,4692 **** --- 4706,4719 ---- if (status == RA_CONT || rp == (regitem_T *) ((char *)regstack.ga_data + regstack.ga_len) - 1) break; + + #ifdef FEAT_RELTIME + if (bt_did_time_out(timed_out)) + { + status = RA_FAIL; + break; + } + #endif } // May need to continue with the inner loop, starting at "scan". *************** *** 4976,4987 **** else ++col; #ifdef FEAT_RELTIME ! if (*timeout_flag) ! { ! if (timed_out != NULL) ! *timed_out = TRUE; break; - } #endif } } --- 5003,5010 ---- else ++col; #ifdef FEAT_RELTIME ! if (bt_did_time_out(timed_out)) break; #endif } } *** ../vim-8.2.5114/src/regexp.c 2022-06-05 16:55:50.698774344 +0100 --- src/regexp.c 2022-06-17 15:07:41.469775254 +0100 *************** *** 22,28 **** #ifdef FEAT_RELTIME static int dummy_timeout_flag = 0; ! static const int *timeout_flag = &dummy_timeout_flag; #endif /* --- 22,28 ---- #ifdef FEAT_RELTIME static int dummy_timeout_flag = 0; ! static volatile int *timeout_flag = &dummy_timeout_flag; #endif /* *** ../vim-8.2.5114/src/os_unix.c 2022-06-16 18:47:16.917378701 +0100 --- src/os_unix.c 2022-06-17 15:08:51.197580357 +0100 *************** *** 8251,8257 **** /* * Implement timeout with timer_create() and timer_settime(). */ ! static int timeout_flag = FALSE; static timer_t timer_id; static int timer_created = FALSE; --- 8251,8257 ---- /* * Implement timeout with timer_create() and timer_settime(). */ ! static volatile int timeout_flag = FALSE; static timer_t timer_id; static int timer_created = FALSE; *************** *** 8296,8302 **** * This function is not expected to fail, but if it does it will still return a * valid flag pointer; the flag will remain stuck as FALSE . */ ! const int * start_timeout(long msec) { struct itimerspec interval = { --- 8296,8302 ---- * This function is not expected to fail, but if it does it will still return a * valid flag pointer; the flag will remain stuck as FALSE . */ ! volatile int * start_timeout(long msec) { struct itimerspec interval = { *************** *** 8324,8329 **** --- 8324,8331 ---- timer_created = TRUE; } + ch_log(NULL, "setting timeout timer to %d sec %ld nsec", + (int)interval.it_value.tv_sec, (long)interval.it_value.tv_nsec); ret = timer_settime(timer_id, 0, &interval, NULL); if (ret < 0) semsg(_(e_could_not_set_timeout_str), strerror(errno)); *************** *** 8351,8357 **** */ static struct itimerval prev_interval; static struct sigaction prev_sigaction; ! static int timeout_flag = FALSE; static int timer_active = FALSE; static int timer_handler_active = FALSE; static int alarm_pending = FALSE; --- 8353,8359 ---- */ static struct itimerval prev_interval; static struct sigaction prev_sigaction; ! static volatile int timeout_flag = FALSE; static int timer_active = FALSE; static int timer_handler_active = FALSE; static int alarm_pending = FALSE; *************** *** 8409,8415 **** * This function is not expected to fail, but if it does it will still return a * valid flag pointer; the flag will remain stuck as FALSE . */ ! const int * start_timeout(long msec) { struct itimerval interval = { --- 8411,8417 ---- * This function is not expected to fail, but if it does it will still return a * valid flag pointer; the flag will remain stuck as FALSE . */ ! volatile int * start_timeout(long msec) { struct itimerval interval = { *** ../vim-8.2.5114/src/proto/os_unix.pro 2022-06-16 18:47:16.917378701 +0100 --- src/proto/os_unix.pro 2022-06-17 15:08:58.505560483 +0100 *************** *** 87,92 **** void xsmp_init(void); void xsmp_close(void); void stop_timeout(void); ! const int *start_timeout(long msec); void delete_timer(void); /* vim: set ft=c : */ --- 87,92 ---- void xsmp_init(void); void xsmp_close(void); void stop_timeout(void); ! volatile int *start_timeout(long msec); void delete_timer(void); /* vim: set ft=c : */ *** ../vim-8.2.5114/src/testdir/test_search.vim 2022-06-16 21:20:43.392236854 +0100 --- src/testdir/test_search.vim 2022-06-17 14:57:14.564231636 +0100 *************** *** 1576,1585 **** func Test_search_timeout() new let pattern = '\%#=1a*.*X\@<=b*' ! let search_timeout = 0.02 let slow_target_timeout = search_timeout * 15.0 for n in range(40, 400, 30) call setline(1, ['aaa', repeat('abc ', n), 'ccc']) let start = reltime() --- 1576,1592 ---- func Test_search_timeout() new + " use a complicated pattern that should be slow with the BT engine let pattern = '\%#=1a*.*X\@<=b*' ! ! " use a timeout of 50 msec ! let search_timeout = 0.05 ! ! " fill the buffer so that it takes 15 times the timeout to search let slow_target_timeout = search_timeout * 15.0 + " Fill the buffer with more and more text until searching takes more time + " than slow_target_timeout. for n in range(40, 400, 30) call setline(1, ['aaa', repeat('abc ', n), 'ccc']) let start = reltime() *************** *** 1591,1601 **** endfor call assert_true(elapsed > slow_target_timeout) let max_time = elapsed / 2.0 let start = reltime() call search(pattern, '', 0, float2nr(search_timeout * 1000)) let elapsed = reltimefloat(reltime(start)) ! call assert_true(elapsed < max_time) bwipe! endfunc --- 1598,1611 ---- endfor call assert_true(elapsed > slow_target_timeout) + " Check that the timeout kicks in, the time should be less than half of what + " we measured without the timeout. This is permissive, because the timer is + " known to overrun, especially when using valgrind. let max_time = elapsed / 2.0 let start = reltime() call search(pattern, '', 0, float2nr(search_timeout * 1000)) let elapsed = reltimefloat(reltime(start)) ! call assert_inrange(search_timeout * 0.9, max_time, elapsed) bwipe! endfunc *** ../vim-8.2.5114/src/version.c 2022-06-16 21:20:43.392236854 +0100 --- src/version.c 2022-06-17 15:12:23.905037536 +0100 *************** *** 736,737 **** --- 736,739 ---- { /* Add new patch number below this line */ + /**/ + 5115, /**/ -- System administrators are just like women: You can't live with them and you can't live without them. /// Bram Moolenaar -- Bram@Moolenaar.net -- http://www.Moolenaar.net \\\ /// \\\ \\\ sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ /// \\\ help me help AIDS victims -- http://ICCF-Holland.org ///