[PATCH 0/3] Have "stop" button for multi-threaded searches

[PATCH 0/3] Have "stop" button for multi-threaded searches

[Yordan Karadzhov (VMware)]

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.

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(-)

-- 
2.20.1

[PATCH 1/3] kernel-shark: Simplify the search methods in class KsTraceViewer

[Yordan Karadzhov (VMware)]

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.

Signed-off-by: Yordan Karadzhov (VMware) <y.karadz@gmail.com>
---
 kernel-shark/src/KsTraceViewer.cpp | 12 ++++++------
 kernel-shark/src/KsTraceViewer.hpp |  5 +++--
 2 files changed, 9 insertions(+), 8 deletions(-)

diff --git a/kernel-shark/src/KsTraceViewer.cpp b/kernel-shark/src/KsTraceViewer.cpp
index c176cef..0694532 100644
--- a/kernel-shark/src/KsTraceViewer.cpp
+++ b/kernel-shark/src/KsTraceViewer.cpp
@@ -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);
 	};
diff --git a/kernel-shark/src/KsTraceViewer.hpp b/kernel-shark/src/KsTraceViewer.hpp
index cf529ba..6080d0d 100644
--- a/kernel-shark/src/KsTraceViewer.hpp
+++ b/kernel-shark/src/KsTraceViewer.hpp
@@ -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 &);
 
-- 
2.20.1

[PATCH 2/3] kernel-shark: Change the mechanism of the multi-threaded search

[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.

Signed-off-by: Yordan Karadzhov (VMware) <y.karadz@gmail.com>
---
 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(-)

diff --git a/kernel-shark/src/KsModels.cpp b/kernel-shark/src/KsModels.cpp
index b89fee8..ac58ca0 100644
--- a/kernel-shark/src/KsModels.cpp
+++ b/kernel-shark/src/KsModels.cpp
@@ -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;
 }
diff --git a/kernel-shark/src/KsModels.hpp b/kernel-shark/src/KsModels.hpp
index 3faaf4a..d360ad6 100644
--- a/kernel-shark/src/KsModels.hpp
+++ b/kernel-shark/src/KsModels.hpp
@@ -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);
 };
 
diff --git a/kernel-shark/src/KsSearchFSM.hpp b/kernel-shark/src/KsSearchFSM.hpp
index 2089912..6a01d61 100644
--- a/kernel-shark/src/KsSearchFSM.hpp
+++ b/kernel-shark/src/KsSearchFSM.hpp
@@ -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
 
diff --git a/kernel-shark/src/KsTraceViewer.cpp b/kernel-shark/src/KsTraceViewer.cpp
index 0694532..12371ad 100644
--- a/kernel-shark/src/KsTraceViewer.cpp
+++ b/kernel-shark/src/KsTraceViewer.cpp
@@ -12,6 +12,7 @@
 // C++11
 #include <thread>
 #include <future>
+#include <queue>
 
 // KernelShark
 #include "KsQuickContextMenu.hpp"
@@ -676,49 +677,129 @@ void KsTraceViewer::_setSearchIterator(int row)
 void KsTraceViewer::_searchItemsMT()
 {
 	int nThreads = std::thread::hardware_concurrency();
+	int startFrom, nRows(_proxyModel.rowCount({}));
 	std::vector<QPair<int, int>> ranges(nThreads);
 	std::vector<std::future<QList<int>>> maps;
-	int i(0), nRows(_proxyModel.rowCount({}));
-	int delta(nRows / nThreads);
-
-	auto lamSearchMap = [&] (const QPair<int, int> &range,
-				 bool notify) {
-		return _proxyModel.searchMap(_searchFSM._columnComboBox.currentIndex(),
-					     _searchFSM._searchLineEdit.text(),
-					     _searchFSM.condition(),
-					     range.first, range.second,
-					     notify);
+	std::mutex lrs_mtx;
+
+	auto lamLRSUpdate = [&] (int lastRowSearched) {
+		std::lock_guard<std::mutex> lock(lrs_mtx);
+
+		if (_searchFSM._lastRowSearched > lastRowSearched ||
+		    _searchFSM._lastRowSearched < 0) {
+			/*
+			 * This thread has been slower and processed
+			 * less data. Take the place where it stopped
+			 * as a starting point of the next search.
+			 */
+			_searchFSM._lastRowSearched = lastRowSearched;
+		}
 	};
 
-	auto lamSearchReduce = [&] (QList<int> &resultList,
-				    const QList<int> &mapList) {
-		resultList << mapList;
-		_searchFSM.incrementProgress();
+	auto lamSearchMap = [&] (const int first, bool notify) {
+		int lastRowSearched;
+		QList<int> list;
+
+		list = _proxyModel.searchThread(_searchFSM._columnComboBox.currentIndex(),
+						_searchFSM._searchLineEdit.text(),
+						_searchFSM.condition(),
+						nThreads,
+						first, nRows - 1,
+						&lastRowSearched,
+						notify);
+
+		lamLRSUpdate(lastRowSearched);
+
+		return list;
 	};
 
-	for (auto &r: ranges) {
-		r.first = (i++) * delta;
-		r.second = r.first + delta - 1;
-	}
+	using merge_pair_t = std::pair<int, int>;
+	using merge_container_t = std::vector<merge_pair_t>;
 
-	/*
-	 * If the range is not multiple of the number of threads, adjust
-	 * the last range interval.
-	 */
-	ranges.back().second = nRows - 1;
-	maps.push_back(std::async(lamSearchMap, ranges[0], true));
+	auto lamComp = [] (const merge_pair_t& itemA, const merge_pair_t& itemB) {
+		return itemA.second > itemB.second;
+	};
+
+	using merge_queue_t = std::priority_queue<merge_pair_t,
+						  merge_container_t,
+						  decltype(lamComp)>;
+
+	auto lamSearchMerge = [&] (QList<int> &resultList,
+				   QVector< QList<int> >&mapList) {
+		merge_queue_t queue(lamComp);
+		int id, stop(-1);
+
+		auto pop = [&] () {
+			if (queue.size() == 0)
+				return stop;
+
+			auto item = queue.top();
+			queue.pop();
+
+			if (!mapList[item.first].empty()) {
+				/*
+				 * Replace the popped item with the next
+				 * matching item fron the same search thread.
+				 */
+				queue.push(std::make_pair(item.first,
+							  mapList[item.first].front()));
+				mapList[item.first].pop_front();
+			}
+
+			if (_searchFSM.getState() == search_state_t::Paused_s &&
+			    item.second > _searchFSM._lastRowSearched) {
+				/*
+				 * The search has been paused and we already
+				 * passed the last row searched by the slowest
+				 * search thread. Stop here and ignore all
+				 * following matches found by faster threads.
+				 */
+				return stop;
+			}
+
+			return item.second;
+		};
+
+		for (int i = 0; i < mapList.size(); ++i)
+			if ( mapList[i].count()) {
+				queue.push(std::make_pair(i, mapList[i].front()));
+				mapList[i].pop_front();
+			}
+
+		id = pop();
+		while (id >= 0) {
+			resultList.append(id);
+			id = pop();
+		}
+	};
+
+	startFrom = _searchFSM._lastRowSearched + 1;
+	_searchFSM._lastRowSearched = -1;
+
+	/* Start the thread that will update the progress bar. */
+	maps.push_back(std::async(lamSearchMap,
+				  startFrom,
+				  true)); // notify = true
+
+	/* Start all other threads. */
 	for (int r = 1; r < nThreads; ++r)
-		maps.push_back(std::async(lamSearchMap, ranges[r], false));
+		maps.push_back(std::async(lamSearchMap,
+					  startFrom + r,
+					  false)); // notify = false
 
-	while (_proxyModel.searchProgress() < KS_PROGRESS_BAR_MAX - nThreads) {
+	while (_searchFSM.getState() == search_state_t::InProgress_s &&
+	       _proxyModel.searchProgress() < KS_PROGRESS_BAR_MAX - nThreads) {
 		std::unique_lock<std::mutex> lk(_proxyModel._mutex);
 		_proxyModel._pbCond.wait(lk);
 		_searchFSM.setProgress(_proxyModel.searchProgress());
 		QApplication::processEvents();
 	}
 
+	QVector<QList<int>> res;
 	for (auto &m: maps)
-		lamSearchReduce(_matchList, m.get());
+		res.append(std::move(m.get()));
+
+	lamSearchMerge(_matchList, res);
 }
 
 /**
-- 
2.20.1

Re: [PATCH 2/3] kernel-shark: Change the mechanism of the multi-threaded search

[Steven Rostedt]

After applying this patch, I was hitting a lockup with this file:

http://rostedt.org/private/trace-all.dat.xz

By selecting "Event" and searching for "sched" it would hang at %87

I found the bug below.

On Mon, 30 Mar 2020 19:17:22 +0300
"Yordan Karadzhov (VMware)" <y.karadz@gmail.com> wrote:

> --- a/kernel-shark/src/KsModels.cpp
> +++ b/kernel-shark/src/KsModels.cpp
> @@ -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) {

Changing the above to:

		if ((index - first) >= milestone) {

fixes it.

> +			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();
>  			}
>  		}


 Otherwise it looks like it leaves out the final update and the
code hangs here:

	/* Start all other threads. */
	for (int r = 1; r < nThreads; ++r)
		maps.push_back(std::async(lamSearchMap,
					  startFrom + r,
					  false)); // notify = false

	while (_searchFSM.getState() == search_state_t::InProgress_s &&
	       _proxyModel.searchProgress() < KS_PROGRESS_BAR_MAX - nThreads) {
		std::unique_lock<std::mutex> lk(_proxyModel._mutex);
		_proxyModel._pbCond.wait(lk);

< It's stuck above >

		_searchFSM.setProgress(_proxyModel.searchProgress());
		QApplication::processEvents();
	}


-- Steve

Re: [PATCH 2/3] kernel-shark: Change the mechanism of the multi-threaded search

[Yordan Karadzhov (VMware)]

On 24.04.20 г. 23:12 ч., Steven Rostedt wrote:
> 
> After applying this patch, I was hitting a lockup with this file:
> 
> http://rostedt.org/private/trace-all.dat.xz
> 
> By selecting "Event" and searching for "sched" it would hang at %87
> 

Hi Steven,
Very well spotted. I am not able to reproduce the bug directly, but I 
guess this is because you are running this on a machine that has 24 CPU 
cores (or 12 and hyper-trading enabled).

> I found the bug below.
> 
> On Mon, 30 Mar 2020 19:17:22 +0300
> "Yordan Karadzhov (VMware)" <y.karadz@gmail.com> wrote:
> 
>> --- a/kernel-shark/src/KsModels.cpp
>> +++ b/kernel-shark/src/KsModels.cpp
>> @@ -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);

The problem will show up if this division has no remainder.

>>   	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) {
> 
> Changing the above to:
> 
> 		if ((index - first) >= milestone) {
> 
> fixes it.

Correct.

> 
>> +			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();
>>   			}
>>   		}
> 
> 
>   Otherwise it looks like it leaves out the final update and the
> code hangs here:
> 
> 	/* Start all other threads. */
> 	for (int r = 1; r < nThreads; ++r)
> 		maps.push_back(std::async(lamSearchMap,
> 					  startFrom + r,
> 					  false)); // notify = false
> 
> 	while (_searchFSM.getState() == search_state_t::InProgress_s &&
> 	       _proxyModel.searchProgress() < KS_PROGRESS_BAR_MAX - nThreads) {

Alternative fix can be to changing the above to:
	       _proxyModel.searchProgress() < KS_PROGRESS_BAR_MAX - nThreads - 1) {

I would say we can apply both. What do you think?

Thanks!
Yordan

> 		std::unique_lock<std::mutex> lk(_proxyModel._mutex);
> 		_proxyModel._pbCond.wait(lk);
> 
> < It's stuck above >
> 
> 		_searchFSM.setProgress(_proxyModel.searchProgress());
> 		QApplication::processEvents();
> 	}
> 
> 
> -- Steve
> 

Re: [PATCH 2/3] kernel-shark: Change the mechanism of the multi-threaded search

[Steven Rostedt]

On Mon, 27 Apr 2020 17:44:49 +0300
"Yordan Karadzhov (VMware)" <y.karadz@gmail.com> wrote:

> On 24.04.20 г. 23:12 ч., Steven Rostedt wrote:
> > 
> > After applying this patch, I was hitting a lockup with this file:
> > 
> > http://rostedt.org/private/trace-all.dat.xz
> > 
> > By selecting "Event" and searching for "sched" it would hang at %87
> >   
> 
> Hi Steven,
> Very well spotted. I am not able to reproduce the bug directly, but I 
> guess this is because you are running this on a machine that has 24 CPU 
> cores (or 12 and hyper-trading enabled).

Yep (12 and hyperthreading).

> 
> > I found the bug below.
> > 
> > On Mon, 30 Mar 2020 19:17:22 +0300
> > "Yordan Karadzhov (VMware)" <y.karadz@gmail.com> wrote:
> >   
> >> --- a/kernel-shark/src/KsModels.cpp
> >> +++ b/kernel-shark/src/KsModels.cpp
> >> @@ -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);  
> 
> The problem will show up if this division has no remainder.

Yeah, I figured.

> 
> >>   	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) {  
> > 
> > Changing the above to:
> > 
> > 		if ((index - first) >= milestone) {
> > 
> > fixes it.  
> 
> Correct.
> 
> >   
> >> +			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();
> >>   			}
> >>   		}  
> > 
> > 
> >   Otherwise it looks like it leaves out the final update and the
> > code hangs here:
> > 
> > 	/* Start all other threads. */
> > 	for (int r = 1; r < nThreads; ++r)
> > 		maps.push_back(std::async(lamSearchMap,
> > 					  startFrom + r,
> > 					  false)); // notify = false
> > 
> > 	while (_searchFSM.getState() == search_state_t::InProgress_s &&
> > 	       _proxyModel.searchProgress() < KS_PROGRESS_BAR_MAX - nThreads) {  
> 
> Alternative fix can be to changing the above to:
> 	       _proxyModel.searchProgress() < KS_PROGRESS_BAR_MAX - nThreads - 1) {
> 
> I would say we can apply both. What do you think?

I'll try it out and let you know.

Thanks Yordan!

-- Steve

> 
> Thanks!
> Yordan
> 
> > 		std::unique_lock<std::mutex> lk(_proxyModel._mutex);
> > 		_proxyModel._pbCond.wait(lk);
> > 
> > < It's stuck above >
> > 
> > 		_searchFSM.setProgress(_proxyModel.searchProgress());
> > 		QApplication::processEvents();
> > 	}
> > 
> > 
> > -- Steve
> >   

Re: [PATCH 2/3] kernel-shark: Change the mechanism of the multi-threaded search

[Steven Rostedt]

On Mon, 27 Apr 2020 15:18:02 -0400
Steven Rostedt <rostedt@goodmis.org> wrote:

> > I would say we can apply both. What do you think?  
> 
> I'll try it out and let you know.

Want to resend this patch with this change?

-- Steve

diff --git a/kernel-shark/src/KsModels.cpp b/kernel-shark/src/KsModels.cpp
index ac58ca0a..51a7b79f 100644
--- a/kernel-shark/src/KsModels.cpp
+++ b/kernel-shark/src/KsModels.cpp
@@ -91,7 +91,7 @@ size_t KsFilterProxyModel::_search(int column,
 		}
 
 		/* Deal with the Progress bar of the seatch. */
-		if ((index - first) > milestone) {
+		if ((index - first) >= milestone) {
 			milestone += pbCount;
 			if (notify) {
 				/*
diff --git a/kernel-shark/src/KsTraceViewer.cpp b/kernel-shark/src/KsTraceViewer.cpp
index 12371ad7..0e0e3d4e 100644
--- a/kernel-shark/src/KsTraceViewer.cpp
+++ b/kernel-shark/src/KsTraceViewer.cpp
@@ -788,7 +788,7 @@ void KsTraceViewer::_searchItemsMT()
 					  false)); // notify = false
 
 	while (_searchFSM.getState() == search_state_t::InProgress_s &&
-	       _proxyModel.searchProgress() < KS_PROGRESS_BAR_MAX - nThreads) {
+	       _proxyModel.searchProgress() < KS_PROGRESS_BAR_MAX - nThreads - 1) {
 		std::unique_lock<std::mutex> lk(_proxyModel._mutex);
 		_proxyModel._pbCond.wait(lk);
 		_searchFSM.setProgress(_proxyModel.searchProgress());

Re: [PATCH 2/3] kernel-shark: Change the mechanism of the multi-threaded search

[Steven Rostedt]

On Thu, 30 Apr 2020 22:56:37 -0400
Steven Rostedt <rostedt@goodmis.org> wrote:

> On Mon, 27 Apr 2020 15:18:02 -0400
> Steven Rostedt <rostedt@goodmis.org> wrote:
> 
> > > I would say we can apply both. What do you think?    
> > 
> > I'll try it out and let you know.  
> 
> Want to resend this patch with this change?
> 

BTW, I had to test this on my laptop (which doesn't have 24 logical
CPUs), but was able to reproduce it with the following patch. Perhaps
we should try various numbers to make sure it works for other strange
combinations.

-- Steve

diff --git a/kernel-shark/src/KsTraceViewer.cpp b/kernel-shark/src/KsTraceViewer.cpp
index 12371ad7..6e2b5fc6 100644
--- a/kernel-shark/src/KsTraceViewer.cpp
+++ b/kernel-shark/src/KsTraceViewer.cpp
@@ -676,7 +676,7 @@ void KsTraceViewer::_setSearchIterator(int row)
 
 void KsTraceViewer::_searchItemsMT()
 {
-	int nThreads = std::thread::hardware_concurrency();
+	int nThreads = 24; //std::thread::hardware_concurrency();
 	int startFrom, nRows(_proxyModel.rowCount({}));
 	std::vector<QPair<int, int>> ranges(nThreads);
 	std::vector<std::future<QList<int>>> maps;

Re: [PATCH 2/3] kernel-shark: Change the mechanism of the multi-threaded search

[Yordan Karadzhov]

On 2.05.20 г. 4:03 ч., Steven Rostedt wrote:
> On Thu, 30 Apr 2020 22:56:37 -0400
> Steven Rostedt <rostedt@goodmis.org> wrote:
>
>> On Mon, 27 Apr 2020 15:18:02 -0400
>> Steven Rostedt <rostedt@goodmis.org> wrote:
>>
>>>> I would say we can apply both. What do you think?
>>> I'll try it out and let you know.
>> Want to resend this patch with this change?
>>
> BTW, I had to test this on my laptop (which doesn't have 24 logical
> CPUs), but was able to reproduce it with the following patch. Perhaps
> we should try various numbers to make sure it works for other strange
> combinations.
>
> -- Steve
>
> diff --git a/kernel-shark/src/KsTraceViewer.cpp b/kernel-shark/src/KsTraceViewer.cpp
> index 12371ad7..6e2b5fc6 100644
> --- a/kernel-shark/src/KsTraceViewer.cpp
> +++ b/kernel-shark/src/KsTraceViewer.cpp
> @@ -676,7 +676,7 @@ void KsTraceViewer::_setSearchIterator(int row)
>   
>   void KsTraceViewer::_searchItemsMT()
>   {
> -	int nThreads = std::thread::hardware_concurrency();
> +	int nThreads = 24; //std::thread::hardware_concurrency();
Yes, I did the same.
Y.


>   	int startFrom, nRows(_proxyModel.rowCount({}));
>   	std::vector<QPair<int, int>> ranges(nThreads);
>   	std::vector<std::future<QList<int>>> maps;

Re: [PATCH 2/3] kernel-shark: Change the mechanism of the multi-threaded search

[Yordan Karadzhov]

On 1.05.20 г. 5:56 ч., Steven Rostedt wrote:
> On Mon, 27 Apr 2020 15:18:02 -0400
> Steven Rostedt <rostedt@goodmis.org> wrote:
>
>>> I would say we can apply both. What do you think?
>> I'll try it out and let you know.
> Want to resend this patch with this change?

OK, Thanks!

Yordan

>
> -- Steve
>
> diff --git a/kernel-shark/src/KsModels.cpp b/kernel-shark/src/KsModels.cpp
> index ac58ca0a..51a7b79f 100644
> --- a/kernel-shark/src/KsModels.cpp
> +++ b/kernel-shark/src/KsModels.cpp
> @@ -91,7 +91,7 @@ size_t KsFilterProxyModel::_search(int column,
>   		}
>   
>   		/* Deal with the Progress bar of the seatch. */
> -		if ((index - first) > milestone) {
> +		if ((index - first) >= milestone) {
>   			milestone += pbCount;
>   			if (notify) {
>   				/*
> diff --git a/kernel-shark/src/KsTraceViewer.cpp b/kernel-shark/src/KsTraceViewer.cpp
> index 12371ad7..0e0e3d4e 100644
> --- a/kernel-shark/src/KsTraceViewer.cpp
> +++ b/kernel-shark/src/KsTraceViewer.cpp
> @@ -788,7 +788,7 @@ void KsTraceViewer::_searchItemsMT()
>   					  false)); // notify = false
>   
>   	while (_searchFSM.getState() == search_state_t::InProgress_s &&
> -	       _proxyModel.searchProgress() < KS_PROGRESS_BAR_MAX - nThreads) {
> +	       _proxyModel.searchProgress() < KS_PROGRESS_BAR_MAX - nThreads - 1) {
>   		std::unique_lock<std::mutex> lk(_proxyModel._mutex);
>   		_proxyModel._pbCond.wait(lk);
>   		_searchFSM.setProgress(_proxyModel.searchProgress());

[PATCH 3/3] kernel-shark: Make the "stop search" button always visible

[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.

Signed-off-by: Yordan Karadzhov (VMware) <y.karadz@gmail.com>
---
 kernel-shark/src/KsSearchFSM.cpp | 11 ++++++-----
 1 file changed, 6 insertions(+), 5 deletions(-)

diff --git a/kernel-shark/src/KsSearchFSM.cpp b/kernel-shark/src/KsSearchFSM.cpp
index 4f01cc8..6a93ca7 100644
--- a/kernel-shark/src/KsSearchFSM.cpp
+++ b/kernel-shark/src/KsSearchFSM.cpp
@@ -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;
 
-- 
2.20.1