kernel-shark: Have "stop" button for multi-threaded searches
v2 cover kernel-shark: Have "stop" button for multi-threaded searches
So far "stop" button was available only during the single-threaded searches. In order to make the multi-threaded searches stoppable and restartable we are changing the searching mechanism making all searching threads to progress in the data in parallel.
Changes is v2:
- Fix of the deadlock in the multi-threaded searche that occurs when the total number of entries is exactly multiple of the number of entries to be searched before updating the progress bar.
Yordan Karadzhov (VMware) (3):
kernel-shark: Simplify the search methods in class KsTraceViewer
kernel-shark: Change the mechanism of the multi-threaded search
kernel-shark: Make the "stop search" button always visible
kernel-shark/src/KsModels.cpp | 89 ++++++++++++------ kernel-shark/src/KsModels.hpp | 16 ++-- kernel-shark/src/KsSearchFSM.cpp | 11 ++- kernel-shark/src/KsSearchFSM.hpp | 5 +- kernel-shark/src/KsTraceViewer.cpp | 141 +++++++++++++++++++++++------ kernel-shark/src/KsTraceViewer.hpp | 5 +- 6 files changed, 195 insertions(+), 72 deletions(-)
Signature · 1 line
2.20.1
PATCH v2 1/3 kernel-shark: Simplify the search methods in class KsTraceViewer
This patch defines two identical private methods for single-threaded and multi-threaded search inside the data table. This is done as a preparation for the following patch that will change the mechanism of the multi-threaded search.
--- kernel-shark/src/KsTraceViewer.cpp | 12 ++++++------ kernel-shark/src/KsTraceViewer.hpp | 5 +++-- 2 files changed, 9 insertions(+), 8 deletions(-)
kernel-shark/src/KsTraceViewer.cpp +6 -6
@@ -621,9 +621,9 @@ size_t KsTraceViewer::_searchItems() if (column == KsViewModel::TRACE_VIEW_COL_INFO || column == KsViewModel::TRACE_VIEW_COL_LAT) - _proxyModel.search(&_searchFSM, &_matchList); + _searchItemsST(); else - _searchItemsMapReduce(column, searchText, _searchFSM.condition()); + _searchItemsMT(); } count = _matchList.count();
@@ -673,9 +673,7 @@ void KsTraceViewer::_setSearchIterator(int row) } } -void KsTraceViewer::_searchItemsMapReduce(int column, - const QString &searchText, - search_condition_func cond) +void KsTraceViewer::_searchItemsMT() { int nThreads = std::thread::hardware_concurrency(); std::vector<QPair<int, int>> ranges(nThreads);
@@ -685,7 +683,9 @@ void KsTraceViewer::_searchItemsMapReduce(int column, auto lamSearchMap = [&] (const QPair<int, int> &range, bool notify) { - return _proxyModel.searchMap(column, searchText, cond, + return _proxyModel.searchMap(_searchFSM._columnComboBox.currentIndex(), + _searchFSM._searchLineEdit.text(), + _searchFSM.condition(), range.first, range.second, notify); };
kernel-shark/src/KsTraceViewer.hpp +3 -2
@@ -132,8 +132,9 @@ private: size_t _searchItems(); - void _searchItemsMapReduce(int column, const QString &searchText, - search_condition_func cond); + void _searchItemsST() {_proxyModel.search(&_searchFSM, &_matchList);} + + void _searchItemsMT(); void _searchEditText(const QString &);
Signature · 1 line
2.20.1
Re: [PATCH v2 1/3] kernel-shark: Simplify the search methods in class KsTraceViewer
kernel-shark/src/KsTraceViewer.hpp private: · line 139
Quoted 12 lines · On Mon, 4 May 2020 20:43:40 +0300 "Yordan Karadzhov (VMware)"…
+++ b/kernel-shark/src/KsTraceViewer.hpp
kernel-shark/src/KsTraceViewer.hpp +3
-2@@ -132,8 +132,9 @@ private: size_t _searchItems(); - void _searchItemsMapReduce(int column, const QString &searchText, - search_condition_func cond); + void _searchItemsST() {_proxyModel.search(&_searchFSM, &_matchList);} + + void _searchItemsMT(); void _searchEditText(const QString &);
I'll pull this in as-is, but the above should definitely have comments stating one is "Single threaded" and the other is "Multi threaded", otherwise who would know what they mean?
-- Steve
PATCH v2 2/3 kernel-shark: Change the mechanism of the multi-threaded search
In reply to Yordan Karadzhov (VMware)We switch from classical Map-Reduce approach in which the data is divided in sub-sets and each thread searches into its own sub-set to a solution in which all thread are progressing in the data in parallel. Note that the Map-Reduce solution is more efficient because at the end when we merge the searching results we simply have to append the outputs of the threads, while in the case of a parallel search we hare to also sort the merged outputs of the threads. However, the parallel search allows the user to stop and later restart the search at any time. The GUI buttons, needed to stop and restart the multi-threaded search will be enabled in the following patch.
--- kernel-shark/src/KsModels.cpp | 89 +++++++++++++------ kernel-shark/src/KsModels.hpp | 16 ++-- kernel-shark/src/KsSearchFSM.hpp | 5 +- kernel-shark/src/KsTraceViewer.cpp | 135 +++++++++++++++++++++++------ 4 files changed, 183 insertions(+), 62 deletions(-)
kernel-shark/src/KsModels.cpp +62 -27
@@ -52,22 +52,25 @@ size_t KsFilterProxyModel::_search(int column, const QString &searchText, search_condition_func cond, QList<int> *matchList, + int step, int first, int last, QProgressBar *pb, QLabel *l, + int *lastRowSearched, bool notify) { int index, row, nRows(last - first + 1); - int pbCount(1); + int milestone(1), pbCount(1); QString item; if (nRows > KS_PROGRESS_BAR_MAX) - pbCount = nRows / (KS_PROGRESS_BAR_MAX - _searchProgress); + milestone = pbCount = nRows / (KS_PROGRESS_BAR_MAX - step - + _searchProgress); else _searchProgress = KS_PROGRESS_BAR_MAX - nRows; /* Loop over the items of the proxy model. */ - for (index = first; index <= last; ++index) { + for (index = first; index <= last; index += step) { /* * Use the index of the proxy model to retrieve the value * of the row number in the base model.
@@ -78,17 +81,23 @@ size_t KsFilterProxyModel::_search(int column, matchList->append(row); if (_searchStop) { - if (notify) { - _searchProgress = KS_PROGRESS_BAR_MAX; + if (lastRowSearched) + *lastRowSearched = index; + + if (notify) _pbCond.notify_one(); - } break; } /* Deal with the Progress bar of the seatch. */ - if ((index - first) % pbCount == 0) { + if ((index - first) >= milestone) { + milestone += pbCount; if (notify) { + /* + * This is a multi-threaded search. Notify + * the main thread to update the progress bar. + */ std::lock_guard<std::mutex> lk(_mutex); ++_searchProgress; _pbCond.notify_one();
@@ -100,6 +109,7 @@ size_t KsFilterProxyModel::_search(int column, if (l) l->setText(QString(" %1").arg(matchList->count())); + QApplication::processEvents(); } }
@@ -130,8 +140,17 @@ size_t KsFilterProxyModel::search(int column, QLabel *l) { int nRows = rowCount({}); - _search(column, searchText, cond, matchList, - 0, nRows - 1, pb, l, false); + _search(column, + searchText, + cond, + matchList, + 1, // step + 0, // first + nRows - 1, // last + pb, + l, + nullptr, + false); return matchList->count(); }
@@ -148,16 +167,17 @@ size_t KsFilterProxyModel::search(KsSearchFSM *sm, QList<int> *matchList) { int nRows = rowCount({}); - sm->_lastRowSearched = - _search(sm->column(), - sm->searchText(), - sm->condition(), - matchList, - sm->_lastRowSearched + 1, - nRows - 1, - &sm->_searchProgBar, - &sm->_searchCountLabel, - false); + _search(sm->column(), + sm->searchText(), + sm->condition(), + matchList, + 1, // step + sm->_lastRowSearched + 1, // first + nRows - 1, // last + &sm->_searchProgBar, + &sm->_searchCountLabel, + &sm->_lastRowSearched, + false); return matchList->count(); }
@@ -168,26 +188,41 @@ size_t KsFilterProxyModel::search(KsSearchFSM *sm, QList<int> *matchList) * @param column: The number of the column to search in. * @param searchText: The text to search for. * @param cond: Matching condition function. + * @param step: The step used by the thread of the search when looping over + * the data. * @param first: Row index specifying the position inside the table from * where the search starts. * @param last: Row index specifying the position inside the table from * where the search ends. + * @param lastRowSearched: Output location for parameter showing the index of + * the last searched item (data row). * @param notify: Input location for flag specifying if the search has to * notify the main thread when to update the progress bar. * * @returns A list containing the row indexes of the cells satisfying matching * condition. */ -QList<int> KsFilterProxyModel::searchMap(int column, - const QString &searchText, - search_condition_func cond, - int first, - int last, - bool notify) +QList<int> KsFilterProxyModel::searchThread(int column, + const QString &searchText, + search_condition_func cond, + int step, + int first, + int last, + int *lastRowSearched, + bool notify) { QList<int> matchList; - _search(column, searchText, cond, &matchList, first, last, - nullptr, nullptr, notify); + _search(column, + searchText, + cond, + &matchList, + step, + first, + last, + nullptr, + nullptr, + lastRowSearched, + notify); return matchList; }
kernel-shark/src/KsModels.hpp +10 -6
@@ -170,12 +170,14 @@ public: size_t search(KsSearchFSM *sm, QList<int> *matchList); - QList<int> searchMap(int column, - const QString &searchText, - search_condition_func cond, - int first, - int last, - bool notify); + QList<int> searchThread(int column, + const QString &searchText, + search_condition_func cond, + int step, + int first, + int last, + int *lastRowSearched, + bool notify); /** Get the progress of the search. */ int searchProgress() const {return _searchProgress;}
@@ -223,9 +225,11 @@ private: const QString &searchText, search_condition_func cond, QList<int> *matchList, + int step, int first, int last, QProgressBar *pb, QLabel *l, + int *lastRowSearched, bool notify); };
kernel-shark/src/KsSearchFSM.hpp +3 -2
@@ -168,9 +168,10 @@ public: /** * Last row, tested for matching. To be used when restarting the - * search. + * search. Note that the field uses "int" as a type because this + * is the type supported by the Qt widget (QTableView). */ - ssize_t _lastRowSearched; + int _lastRowSearched; //! @cond Doxygen_Suppress
kernel-shark/src/KsTraceViewer.cpp +108 -27
163 lines not on this page · raw message
Signature · 1 line
2.20.1
PATCH v2 3/3 kernel-shark: Make the "stop search" button always visible
In reply to Yordan Karadzhov (VMware)So far the button was showing up only when we do a single-threaded search in the data. Stopping the multi-threaded searches became possible after the modification of the parallel search introduced in the previous commit. When the multi-threaded search is restarted (after being stopped) the label showing the number of matches found is reset to show nothing. It will show the count again when the search finishes or is stopped.
--- kernel-shark/src/KsSearchFSM.cpp | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-)
kernel-shark/src/KsSearchFSM.cpp +6 -5
@@ -142,11 +142,7 @@ void NotDone::handleInput(KsSearchFSM* sm, sm_input_t input) sm->lockSearchPanel(); sm->updateCondition(); sm->progressBarVisible(true); - - if (sm->column() == KsViewModel::TRACE_VIEW_COL_INFO || - sm->column() == KsViewModel::TRACE_VIEW_COL_LAT) - sm->searchStopVisible(true); - + sm->searchStopVisible(true); sm->changeState(std::shared_ptr<InProgress>(new InProgress)); break;
@@ -168,6 +164,11 @@ void Paused::handleInput(KsSearchFSM* sm, sm_input_t input) sm->lockSearchPanel(); sm->searchStopVisible(true); sm->searchRestartVisible(false); + + if (sm->column() != KsViewModel::TRACE_VIEW_COL_INFO && + sm->column() != KsViewModel::TRACE_VIEW_COL_LAT) + sm->_searchCountLabel.setText(""); + sm->changeState(std::shared_ptr<InProgress>(new InProgress)); break;
Signature · 1 line
2.20.1
Re: [PATCH v2 3/3] kernel-shark: Make the "stop search" button always visible
Quoted 8 lines · On Mon, 4 May 2020 20:43:42 +0300 "Yordan Karadzhov (VMware)"…
So far the button was showing up only when we do a single-threaded search in the data. Stopping the multi-threaded searches became possible after the modification of the parallel search introduced in the previous commit. When the multi-threaded search is restarted (after being stopped) the label showing the number of matches found is reset to show nothing. It will show the count again when the search finishes or is stopped.
I'm pulling in this series. But more of an FYI, it's best to avoid statements like "previous commit" because when developing with git, it may not be a previous commit, when it goes into a tree. Especially if a commit gets cherry-picked.
Instead, use phrases like "With the parallel search changes that were made, it is now possible to stop the multi-threaded searches and still be at the correct percentage of the search that is displayed to the user".
It is frowned upon to mention "this commit" or "last commit" in change logs. I catch myself doing it once in a while, and try to conform as well ;-)
-- Steve