1 /*
2  * Copyright 2017 Google Inc.
3  *
4  * Use of this source code is governed by a BSD-style license that can be
5  * found in the LICENSE file.
6  */
7 
8 #ifndef SkTaskGroup2D_DEFINED
9 #define SkTaskGroup2D_DEFINED
10 
11 #include "SkTaskGroup.h"
12 
13 #include <mutex>
14 #include <vector>
15 
16 // The interface for doing work on a 2D grid with possible initialization on columns.
17 class SkWorkKernel2D {
18 public:
19     // Return false iff the column needs initialization and such initialization is not finished yet.
20     virtual bool work2D(int row, int column, int thread) = 0;
21 
22     // Return false if no initialization is done for this colum (e.g., it's already initialized; or
23     // maybe some other thread is initializing the column).
24     virtual bool initColumn(int column, int thread) = 0;
25 
~SkWorkKernel2D()26     virtual ~SkWorkKernel2D() {}
27 };
28 
29 // A 2D grid (height rows x width columns) of tasks to be executed on a given executor with
30 // threadCnt number of threads.
31 //
32 // The height (number of rows) is fixed. The width (number of columns) may be dynamically expanded.
33 //
34 // The task on row i and column j is abstracted as work2D(i, j, t). Parameter t is the thread id and
35 // it shouldn't affect the work to be done. It's only used to allow some variables that are not
36 // thread safe and should be used exclusively by one thread (e.g., thread allocators). We guarantee
37 // that the task on the same row will be executed in order (i.e., work2D(1, 1, t) is guaranteed to
38 // finish before calling work2D(1, 2, t)). Tasks in different rows can happen in any order.
39 //
40 // There are also width number of init calls, one per column. work2D(i, j, t) may return false if
41 // column j requires initialization but it's not initialized yet. In that case, a thread t needs to
42 // call initColumn(j, t) once to unblock all rows that depend on the initialization of column j.
43 // (Again, t shouldn't affect the init work to be done; it's just for some non-thread-safe
44 // variables). The init calls have no order requirement so we can call them in any order.
45 //
46 // Multiple therads may try to init the same column j at the same time. InitFn is expected to handle
47 // this gracefully (e.g., let only one thread do the init and return immediately for other threads).
48 class SkTaskGroup2D {
49 public:
SkTaskGroup2D(SkWorkKernel2D * kernel,int height,SkExecutor * executor,int threadCnt)50     SkTaskGroup2D(SkWorkKernel2D* kernel, int height, SkExecutor* executor, int threadCnt)
51             : fKernel(kernel), fHeight(height), fThreadCnt(threadCnt), fIsFinishing(false)
52             , fWidth(0), fThreadsGroup(new SkTaskGroup(*executor)) {}
53 
~SkTaskGroup2D()54     virtual ~SkTaskGroup2D() {}
55 
56     virtual void addColumn(); // Add a new column of tasks.
57 
58     void start(); // start threads to execute tasks
59     void finish(); // wait and finish all tasks (no more tasks can be added after calling this)
60 
isFinishing()61     SK_ALWAYS_INLINE bool isFinishing() const {
62         return fIsFinishing.load(std::memory_order_relaxed);
63     }
64 
65 protected:
66     static constexpr int MAX_CACHE_LINE = 64;
67 
68     // Finish all tasks on the threadId and then return.
69     virtual void work(int threadId) = 0;
70 
71     // Initialize a column that needs to be initialized. The parameter initCol is not thread safe
72     // and should only be exclusively accessed by the working thread which will modify it to the
73     // column that may need to be initialized next.
initAnUninitializedColumn(int & initCol,int threadId)74     void initAnUninitializedColumn(int& initCol, int threadId) {
75         bool didSomeInit = false;
76         while (initCol < fWidth && !didSomeInit) {
77             didSomeInit = fKernel->initColumn(initCol++, threadId);
78         }
79     }
80 
81     SkWorkKernel2D*     fKernel;
82     const int           fHeight;
83     const int           fThreadCnt;
84 
85     std::atomic<bool>   fIsFinishing;
86     std::atomic<int>    fWidth;
87 
88     std::unique_ptr<SkTaskGroup> fThreadsGroup;
89 };
90 
91 // A simple spinning task group that assumes height equals threadCnt.
92 class SkSpinningTaskGroup2D final : public SkTaskGroup2D {
93 public:
SkSpinningTaskGroup2D(SkWorkKernel2D * kernel,int h,SkExecutor * x,int t)94     SkSpinningTaskGroup2D(SkWorkKernel2D* kernel, int h, SkExecutor* x, int t)
95             : SkTaskGroup2D(kernel, h, x, t) {
96         SkASSERT(h == t); // height must be equal to threadCnt
97     }
98 
99 protected:
100     void work(int threadId) override;
101 };
102 
103 class SkFlexibleTaskGroup2D final : public SkTaskGroup2D {
104 public:
SkFlexibleTaskGroup2D(SkWorkKernel2D * kernel,int h,SkExecutor * x,int t)105     SkFlexibleTaskGroup2D(SkWorkKernel2D* kernel, int h, SkExecutor* x, int t)
106             : SkTaskGroup2D(kernel, h, x, t), fRowData(h) {}
107 
108 protected:
109     void work(int threadId) override;
110 
111 private:
112     // alignas(MAX_CACHE_LINE) to avoid false sharing by cache lines
113     struct alignas(MAX_CACHE_LINE) RowData {
RowDataRowData114         RowData() : fNextColumn(0) {}
115 
116         int         fNextColumn; // next column index to work
117         std::mutex  fMutex;      // the mutex for the thread to acquire
118     };
119 
120     std::vector<RowData>    fRowData;
121 };
122 
123 #endif//SkTaskGroup2D_DEFINED
124