2 * Copyright (C) 2019 Collabora, Ltd.
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
11 * The above copyright notice and this permission notice (including the next
12 * paragraph) shall be included in all copies or substantial portions of the
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
25 #include "pan_context.h"
27 #include "pan_allocate.h"
28 #include "util/bitset.h"
31 * Within a batch (panfrost_job), there are various types of Mali jobs:
33 * - WRITE_VALUE: generic write primitive, used to zero tiler field
34 * - VERTEX: runs a vertex shader
35 * - TILER: runs tiling and sets up a fragment shader
36 * - FRAGMENT: runs fragment shaders and writes out
37 * - COMPUTE: runs a compute shader
38 * - FUSED: vertex+tiler fused together, implicit intradependency (Bifrost)
39 * - GEOMETRY: runs a geometry shader (unimplemented)
40 * - CACHE_FLUSH: unseen in the wild, theoretically cache flush
42 * In between a full batch and a single Mali job is the "job chain", a series
43 * of Mali jobs together forming a linked list. Within the job chain, each Mali
44 * job can set (up to) two dependencies on other earlier jobs in the chain.
45 * This dependency graph forms a scoreboard. The general idea of a scoreboard
46 * applies: when there is a data dependency of job B on job A, job B sets one
47 * of its dependency indices to job A, ensuring that job B won't start until
50 * More specifically, here are a set of rules:
52 * - A set value job must appear if and only if there is at least one tiler job.
54 * - Vertex jobs and tiler jobs are independent.
56 * - A tiler job must have a dependency on its data source. If it's getting
57 * data from a vertex job, it depends on the vertex job. If it's getting data
58 * from software, this is null.
60 * - The first vertex job used as the input to tiling must depend on the set
61 * value job, if it is present.
63 * - Tiler jobs must be strictly ordered. So each tiler job must depend on the
64 * previous job in the chain.
66 * - Jobs linking via next_job has no bearing on order of execution, rather it
67 * just establishes the linked list of jobs, EXCEPT:
69 * - A job's dependencies must appear earlier in the linked list (job chain).
71 * Justification for each rule:
73 * - Set value jobs set up tiling, essentially. If tiling occurs, they are
74 * needed; if it does not, we cannot emit them since then tiling partially
75 * occurs and it's bad.
77 * - The hardware has no notion of a "vertex/tiler job" (at least not our
78 * hardware -- other revs have fused jobs, but --- crap, this just got even
79 * more complicated). They are independent units that take in data, process
80 * it, and spit out data.
82 * - Any job must depend on its data source, in fact, or risk a
83 * read-before-write hazard. Tiler jobs get their data from vertex jobs, ergo
84 * tiler jobs depend on the corresponding vertex job (if it's there).
86 * - In fact, tiling depends on the set value job, but tiler jobs depend on the
87 * corresponding vertex jobs and each other, so this rule ensures each tiler
88 * job automatically depends on the set value job.
90 * - The tiler is not thread-safe; this dependency prevents race conditions
91 * between two different jobs trying to write to the tiler outputs at the
94 * - Internally, jobs are scoreboarded; the next job fields just form a linked
95 * list to allow the jobs to be read in; the execution order is from
96 * resolving the dependency fields instead.
98 * - The hardware cannot set a dependency on a job it doesn't know about yet,
99 * and dependencies are processed in-order of the next job fields.
103 /* Coerce a panfrost_transfer to a header */
105 static inline struct mali_job_descriptor_header
*
106 job_descriptor_header(struct panfrost_transfer t
)
108 return (struct mali_job_descriptor_header
*) t
.cpu
;
112 panfrost_assign_index(
113 struct panfrost_batch
*batch
,
114 struct panfrost_transfer transfer
)
116 /* Assign the index */
117 unsigned index
= ++batch
->job_index
;
118 job_descriptor_header(transfer
)->job_index
= index
;
121 /* Helper to add a dependency to a job */
124 panfrost_add_dependency(
125 struct panfrost_transfer depender
,
126 struct panfrost_transfer dependent
)
129 struct mali_job_descriptor_header
*first
=
130 job_descriptor_header(dependent
);
132 struct mali_job_descriptor_header
*second
=
133 job_descriptor_header(depender
);
135 /* Look for an open slot */
137 if (!second
->job_dependency_index_1
)
138 second
->job_dependency_index_1
= first
->job_index
;
139 else if (!second
->job_dependency_index_2
)
140 second
->job_dependency_index_2
= first
->job_index
;
142 unreachable("No available slot for new dependency");
145 /* Queues a job WITHOUT updating pointers. Be careful. */
148 panfrost_scoreboard_queue_job_internal(
149 struct panfrost_batch
*batch
,
150 struct panfrost_transfer job
)
152 panfrost_assign_index(batch
, job
);
154 /* Queue a pointer to the job */
155 util_dynarray_append(&batch
->headers
, void*, job
.cpu
);
156 util_dynarray_append(&batch
->gpu_headers
, mali_ptr
, job
.gpu
);
160 /* Queues a compute job, with no special dependencies. This is a bit of a
161 * misnomer -- internally, all job types are queued with this function, but
162 * outside of this file, it's for pure compute jobs */
165 panfrost_scoreboard_queue_compute_job(
166 struct panfrost_batch
*batch
,
167 struct panfrost_transfer job
)
169 panfrost_scoreboard_queue_job_internal(batch
, job
);
171 /* Update the linked list metadata as appropriate */
172 batch
->last_job
= job
;
174 if (!batch
->first_job
.gpu
)
175 batch
->first_job
= job
;
178 /* Queues a vertex job. There are no special dependencies yet, but if
179 * tiling is required (anytime 'rasterize discard' is disabled), we have
180 * some extra bookkeeping for later */
183 panfrost_scoreboard_queue_vertex_job(
184 struct panfrost_batch
*batch
,
185 struct panfrost_transfer vertex
,
186 bool requires_tiling
)
188 panfrost_scoreboard_queue_compute_job(batch
, vertex
);
190 if (requires_tiling
&& !batch
->first_vertex_for_tiler
.gpu
)
191 batch
->first_vertex_for_tiler
= vertex
;
194 /* Queues a tiler job, respecting the dependency of each tiler job on the
198 panfrost_scoreboard_queue_tiler_job(
199 struct panfrost_batch
*batch
,
200 struct panfrost_transfer tiler
)
202 panfrost_scoreboard_queue_compute_job(batch
, tiler
);
204 if (!batch
->first_tiler
.gpu
)
205 batch
->first_tiler
= tiler
;
207 if (batch
->last_tiler
.gpu
)
208 panfrost_add_dependency(tiler
, batch
->last_tiler
);
210 batch
->last_tiler
= tiler
;
213 /* Queues a fused (vertex/tiler) job, or a pair of vertex/tiler jobs if
214 * fused jobs are not supported (the default until Bifrost rolls out) */
217 panfrost_scoreboard_queue_fused_job(
218 struct panfrost_batch
*batch
,
219 struct panfrost_transfer vertex
,
220 struct panfrost_transfer tiler
)
222 panfrost_scoreboard_queue_vertex_job(batch
, vertex
, true);
223 panfrost_scoreboard_queue_tiler_job(batch
, tiler
);
224 panfrost_add_dependency(tiler
, vertex
);
227 /* Queues a fused (vertex/tiler) job prepended *before* the usual set, used for
231 panfrost_scoreboard_queue_fused_job_prepend(
232 struct panfrost_batch
*batch
,
233 struct panfrost_transfer vertex
,
234 struct panfrost_transfer tiler
)
237 assert(batch
->last_tiler
.gpu
);
238 assert(batch
->first_tiler
.gpu
);
240 /* First, we add the vertex job directly to the queue, forcing it to
243 panfrost_scoreboard_queue_job_internal(batch
, vertex
);
244 batch
->first_job
= vertex
;
245 batch
->first_vertex_for_tiler
= vertex
;
247 /* Similarly, we add the tiler job directly to the queue, forcing it to
248 * the front (second place), manually setting the tiler on vertex
249 * dependency (since this is pseudofused) and forcing a dependency of
250 * the now-second tiler on us (since all tiler jobs are linked in order
251 * and we're injecting ourselves at the front) */
253 panfrost_scoreboard_queue_job_internal(batch
, tiler
);
254 panfrost_add_dependency(tiler
, vertex
);
255 panfrost_add_dependency(batch
->first_tiler
, tiler
);
256 batch
->first_tiler
= tiler
;
259 /* Generates a write value job, used to initialize the tiler structures. */
261 static struct panfrost_transfer
262 panfrost_write_value_job(struct panfrost_batch
*batch
, mali_ptr polygon_list
)
264 struct mali_job_descriptor_header job
= {
265 .job_type
= JOB_TYPE_WRITE_VALUE
,
266 .job_descriptor_size
= 1,
269 struct mali_payload_write_value payload
= {
270 .address
= polygon_list
,
271 .value_descriptor
= MALI_WRITE_VALUE_ZERO
,
274 struct panfrost_transfer transfer
= panfrost_allocate_transient(batch
, sizeof(job
) + sizeof(payload
));
275 memcpy(transfer
.cpu
, &job
, sizeof(job
));
276 memcpy(transfer
.cpu
+ sizeof(job
), &payload
, sizeof(payload
));
281 /* If there are any tiler jobs, we need to initialize the tiler by writing
282 * zeroes to a magic tiler structure. We do so via a WRITE_VALUE job linked to
283 * the first vertex job feeding into tiling. */
286 panfrost_scoreboard_initialize_tiler(struct panfrost_batch
*batch
)
288 /* Check if we even need tiling */
289 if (!batch
->last_tiler
.gpu
)
292 /* Okay, we do. Let's generate it. We'll need the job's polygon list
293 * regardless of size. */
295 mali_ptr polygon_list
= panfrost_batch_get_polygon_list(batch
,
296 MALI_TILER_MINIMUM_HEADER_SIZE
);
298 struct panfrost_transfer job
=
299 panfrost_write_value_job(batch
, polygon_list
);
302 panfrost_scoreboard_queue_compute_job(batch
, job
);
304 /* Tiler jobs need us */
305 panfrost_add_dependency(batch
->first_tiler
, job
);
308 /* Once all jobs have been added to a batch and we're ready to submit, we need
309 * to order them to set each of the next_job fields, obeying the golden rule:
310 * "A job's dependencies must appear earlier in the job chain than itself".
311 * Fortunately, computing this job chain is a well-studied graph theory problem
312 * known as "topological sorting", which has linear time algorithms. We let
313 * each job represent a node, each dependency a directed edge, and the entire
314 * set of jobs to be a dependency graph. This graph is inherently acyclic, as
315 * otherwise there are unresolveable dependencies.
317 * We implement Kahn's algorithm here to compute the next_job chain:
318 * https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm
320 * A few implementation notes: we represent S explicitly with a bitset, L
321 * implicitly in the next_job fields. The indices of the bitset are off-by-one:
322 * nodes are numbered [0, node_count - 1], whereas in reality job_index in the
323 * hardware and dependencies are [1, node_count].
325 * We represent edge removal implicitly with another pair of bitsets, rather
326 * than explicitly removing the edges, since we need to keep the dependencies
327 * there for the hardware.
330 #define DESCRIPTOR_FOR_NODE(count) \
331 *(util_dynarray_element(&batch->headers, \
332 struct mali_job_descriptor_header*, count))
334 #define GPU_ADDRESS_FOR_NODE(count) \
335 *(util_dynarray_element(&batch->gpu_headers, \
339 panfrost_scoreboard_link_batch(struct panfrost_batch
*batch
)
341 /* Finalize the batch */
342 panfrost_scoreboard_initialize_tiler(batch
);
344 /* Let no_incoming represent the set S described. */
346 unsigned node_count
= batch
->job_index
;
348 size_t sz
= BITSET_WORDS(node_count
) * sizeof(BITSET_WORD
);
349 BITSET_WORD
*no_incoming
= calloc(sz
, 1);
351 /* Sets for edges being removed in dep 1 or 2 respectively */
353 BITSET_WORD
*edge_removal_1
= calloc(sz
, 1);
354 BITSET_WORD
*edge_removal_2
= calloc(sz
, 1);
356 /* We compute no_incoming by traversing the batch. Simultaneously, we
357 * would like to keep track of a parity-reversed version of the
358 * dependency graph. Dependency indices are 16-bit and in practice (for
359 * ES3.0, at least), we can guarantee a given node will be depended on
360 * by no more than one other nodes. P.f:
362 * Proposition: Given a node N of type T, no more than one other node
365 * If type is WRITE_VALUE: The only dependency added against us is from
366 * the first tiler job, so there is 1 dependent.
368 * If type is VERTEX: If there is a tiler node, that tiler node depends
369 * on us; if there is not (transform feedback), nothing depends on us.
370 * Therefore there is at most 1 dependent.
372 * If type is TILER: If there is another TILER job in succession, that
373 * node depends on us. No other job type depends on us. Therefore there
374 * is at most 1 dependent.
376 * If type is FRAGMENT: This type cannot be in a primary chain, so it
377 * is irrelevant. Just for kicks, nobody would depend on us, so there
378 * are zero dependents, so it holds anyway.
380 * TODO: Revise this logic for ES3.1 and above. This result may not
381 * hold for COMPUTE/FUSED/GEOMETRY jobs; we might need to special case
382 * those. Can FBO dependencies be expressed within a chain?
385 * Point is, we only need to hold a single dependent, which is a pretty
389 unsigned *dependents
= calloc(node_count
, sizeof(unsigned));
391 for (unsigned i
= 0; i
< node_count
; ++i
) {
392 struct mali_job_descriptor_header
*node
= DESCRIPTOR_FOR_NODE(i
);
394 unsigned dep_1
= node
->job_dependency_index_1
;
395 unsigned dep_2
= node
->job_dependency_index_2
;
397 /* Record no_incoming info for this node */
399 if (!(dep_1
|| dep_2
))
400 BITSET_SET(no_incoming
, i
);
402 /* Record this node as the dependent of each of its
406 assert(!dependents
[dep_1
- 1]);
407 dependents
[dep_1
- 1] = i
+ 1;
411 assert(!dependents
[dep_2
- 1]);
412 dependents
[dep_2
- 1] = i
+ 1;
416 /* No next_job fields are set at the beginning, so L is implciitly the
417 * empty set. As next_job fields are filled, L is implicitly set. Tail
418 * is the tail of L, however. */
420 struct mali_job_descriptor_header
*tail
= NULL
;
422 /* We iterate, popping off elements of S. A simple foreach won't do,
423 * since we mutate S as we go (even adding elements) */
425 unsigned arr_size
= BITSET_WORDS(node_count
);
427 for (unsigned node_n_1
= __bitset_ffs(no_incoming
, arr_size
);
429 node_n_1
= __bitset_ffs(no_incoming
, arr_size
)) {
431 unsigned node_n
= node_n_1
- 1;
433 /* We've got a node n, pop it off */
434 BITSET_CLEAR(no_incoming
, node_n
);
436 /* Add it to the list */
437 struct mali_job_descriptor_header
*n
=
438 DESCRIPTOR_FOR_NODE(node_n
);
440 mali_ptr addr
= GPU_ADDRESS_FOR_NODE(node_n
);
443 /* Link us to the last node */
444 tail
->next_job
= addr
;
446 /* We are the first/last node */
447 batch
->first_job
.cpu
= (uint8_t *) n
;
448 batch
->first_job
.gpu
= addr
;
453 /* Grab the dependent, if there is one */
454 unsigned node_m_1
= dependents
[node_n
];
457 unsigned node_m
= node_m_1
- 1;
459 struct mali_job_descriptor_header
*m
=
460 DESCRIPTOR_FOR_NODE(node_m
);
462 /* Get the deps, accounting for removal */
463 unsigned dep_1
= m
->job_dependency_index_1
;
464 unsigned dep_2
= m
->job_dependency_index_2
;
466 if (BITSET_TEST(edge_removal_1
, node_m
))
469 if (BITSET_TEST(edge_removal_2
, node_m
))
472 /* Pretend to remove edges */
473 if (dep_1
== node_n_1
) {
474 BITSET_SET(edge_removal_1
, node_m
);
476 } else if (dep_2
== node_n_1
) {
477 BITSET_SET(edge_removal_2
, node_m
);
480 /* This node has no relevant dependencies */
484 /* Are there edges left? If not, add us to S */
485 bool has_edges
= dep_1
|| dep_2
;
488 BITSET_SET(no_incoming
, node_m
);
495 free(edge_removal_1
);
496 free(edge_removal_2
);