| /* |
| * Copyright 2017 Google Inc. |
| * |
| * Use of this source code is governed by a BSD-style license that can |
| * be found in the LICENSE file. |
| * |
| */ |
| |
| #pragma once |
| |
| // |
| // |
| // |
| |
| #include <string.h> |
| #include <assert.h> |
| #include <stdbool.h> |
| |
| #include "grid.h" |
| #include "macros.h" |
| #include "runtime_cl_12.h" |
| |
| // |
| // SKC grid dependencies can be represented with a DAG. |
| // |
| // This dependency graph may be modified to include some sort of block |
| // pool barrier to make block recovery explicit (and guaranteed safe). |
| // |
| // |
| // PATH BUILDER |
| // | |
| // | |
| // | |
| // v |
| // RASTER BUILDER |
| // | |
| // +----+ | +----+ |
| // Set Ops | | | | | Set Ops |
| // | v v v | |
| // +--COMPOSITION STYLING--+ |
| // | | |
| // | +--------+ |
| // | | |
| // v v |
| // SURFACE |
| // |
| // |
| // STAGE DEPENDENCIES |
| // ============== ============================ |
| // PATH BUILDER - |
| // RASTER BUILDER PATH BUILDER |
| // COMPOSITION RASTER BUILDER, *COMPOSITION |
| // STYLING -, *STYLING |
| // SURFACE COMPOSITION, STYLING |
| // |
| |
| // |
| // How many active grids can/should we have? |
| // |
| // FIXME -- we'll need to provide a small level of indirection if we |
| // want to support a much larger number of work-in-progress grids |
| // |
| // For now and for simplicity, unify all grid ids in one set. |
| // |
| |
| typedef skc_uchar skc_grid_id_t; // 256 values |
| #define SKC_GRID_ID_INVALID SKC_UCHAR_MAX // 255 |
| |
| #define SKC_GRID_SIZE_IDS (SKC_GRID_ID_INVALID-1) |
| #define SKC_GRID_SIZE_WORDS ((SKC_GRID_SIZE_IDS+31)/32) |
| |
| // |
| // |
| // |
| |
| typedef enum skc_grid_state_e { |
| |
| SKC_GRID_STATE_READY, |
| SKC_GRID_STATE_WAITING, |
| SKC_GRID_STATE_FORCED, |
| SKC_GRID_STATE_EXECUTING, |
| SKC_GRID_STATE_COMPLETE, |
| SKC_GRID_STATE_DETACHED, |
| |
| SKC_GRID_STATE_COUNT |
| |
| } skc_grid_state_e; |
| |
| // |
| // |
| // |
| |
| struct skc_grid_pfn_name |
| { |
| skc_grid_pfn pfn; |
| char const * name; |
| }; |
| |
| // |
| // |
| // |
| |
| struct skc_grid |
| { |
| skc_grid_state_e state; |
| skc_uint id; |
| |
| struct skc_grid_deps * deps; // backpointer to deps |
| void * * addr; // pointer to invalidate |
| |
| void * data; |
| |
| struct skc_grid_pfn_name waiting; // optional - if defined, typically used to yank the grid away from host |
| struct skc_grid_pfn_name execute; // optional - starts execution of waiting grid |
| struct skc_grid_pfn_name dispose; // optional - invoked when grid is complete |
| |
| struct { |
| skc_uint words[SKC_GRID_SIZE_WORDS]; // 0:inactive, 1:active |
| skc_uint count; |
| } before; |
| |
| struct { |
| skc_uint words[SKC_GRID_SIZE_WORDS]; // 0:inactive, 1:active |
| skc_uint count; |
| } after; |
| }; |
| |
| // |
| // |
| // |
| |
| struct skc_grid_deps |
| { |
| struct skc_runtime * runtime; |
| struct skc_scheduler * scheduler; |
| |
| skc_grid_id_t * handle_map; |
| |
| struct skc_grid grids [SKC_GRID_SIZE_IDS]; // deps + pfns + data |
| skc_uint active[SKC_GRID_SIZE_WORDS]; // 1:inactive, 0:active |
| |
| skc_uint count; // number of active ids |
| }; |
| |
| // |
| // |
| // |
| |
| static |
| void |
| skc_grid_call(skc_grid_t const grid, struct skc_grid_pfn_name const * const pn) |
| { |
| if (pn->pfn != NULL) { |
| pn->pfn(grid); |
| } |
| } |
| |
| static |
| void |
| skc_grid_schedule(skc_grid_t const grid, struct skc_grid_pfn_name const * const pn) |
| { |
| if (pn->pfn != NULL) { |
| skc_scheduler_schedule(grid->deps->scheduler,pn->pfn,grid,pn->name); |
| } |
| } |
| |
| // |
| // |
| // |
| |
| static |
| void |
| skc_grid_invalidate(skc_grid_t const grid) |
| { |
| if (grid->addr != NULL) { |
| *grid->addr = NULL; |
| } |
| } |
| |
| // |
| // |
| // |
| |
| #if 0 |
| skc_grid_t |
| skc_grid_move(skc_grid_t const grid, |
| skc_grid_state_e * const state, |
| skc_grid_t * const addr, |
| void * const data) |
| { |
| skc_grid_invalidate(grid); |
| |
| grid->state = state; |
| grid->addr = addr; |
| grid->data = data; |
| |
| return grid; |
| } |
| #endif |
| |
| void * |
| skc_grid_get_data(skc_grid_t const grid) |
| { |
| return grid->data; |
| } |
| |
| void |
| skc_grid_set_data(skc_grid_t const grid, void * const data) |
| { |
| grid->data = data; |
| } |
| |
| // |
| // |
| // |
| |
| skc_grid_deps_t |
| skc_grid_deps_create(struct skc_runtime * const runtime, |
| struct skc_scheduler * const scheduler, |
| skc_uint const handle_pool_size) |
| { |
| struct skc_grid_deps * const deps = skc_runtime_host_perm_alloc(runtime,SKC_MEM_FLAGS_READ_WRITE,sizeof(*deps)); |
| |
| // save runtime |
| deps->runtime = runtime; |
| deps->scheduler = scheduler; |
| |
| size_t const handle_map_size = sizeof(*deps->handle_map) * handle_pool_size; |
| |
| // allocate handle map |
| deps->handle_map = skc_runtime_host_perm_alloc(runtime,SKC_MEM_FLAGS_READ_WRITE,handle_map_size); |
| |
| // initialize handle map |
| memset(deps->handle_map,0xFF,handle_map_size); |
| |
| // grids |
| struct skc_grid * const grids = deps->grids; |
| |
| #if 0 // DELETE ME LATER |
| // initalize ids once -- could always infer id using offsetof() |
| for (skc_uint id=0; id < SKC_GRID_SIZE_IDS; id++) |
| grids[id].id = id; |
| #endif |
| |
| // mark all grids inactive except for last bit -- 1:inactive / 0:active |
| for (skc_uint ii=0; ii < SKC_GRID_SIZE_WORDS-1; ii++) |
| deps->active[ii] = 0xFFFFFFFF; |
| |
| // last bit is marked active so that it is never allocated |
| deps->active[SKC_GRID_SIZE_WORDS-1] = 0x7FFFFFFF; |
| |
| // nothing active |
| deps->count = 1; |
| |
| return deps; |
| } |
| |
| void |
| skc_grid_deps_dispose(skc_grid_deps_t const deps) |
| { |
| // |
| // FIXME -- debug checks for active grids |
| // |
| skc_runtime_host_perm_free(deps->runtime,deps->handle_map); |
| skc_runtime_host_perm_free(deps->runtime,deps); |
| } |
| |
| // |
| // |
| // |
| |
| #ifndef NDEBUG |
| |
| void |
| skc_grid_deps_debug(struct skc_grid_deps const * const deps) |
| { |
| fprintf(stderr, |
| "00000000000000001111111111111111\n" |
| "0123456789ABCDEF0123456789ABCDEF\n" |
| "--------------------------------\n"); |
| |
| for (skc_uint ii=0; ii<SKC_GRID_SIZE_WORDS; ii++) |
| { |
| skc_uint const a = deps->active[ii]; |
| fprintf(stderr, |
| "%1u%1u%1u%1u%1u%1u%1u%1u%1u%1u%1u%1u%1u%1u%1u%1u" |
| "%1u%1u%1u%1u%1u%1u%1u%1u%1u%1u%1u%1u%1u%1u%1u%1u\n", |
| (a>>0x00)&1,(a>>0x01)&1,(a>>0x02)&1,(a>>0x03)&1, |
| (a>>0x04)&1,(a>>0x05)&1,(a>>0x06)&1,(a>>0x07)&1, |
| (a>>0x08)&1,(a>>0x09)&1,(a>>0x0A)&1,(a>>0x0B)&1, |
| (a>>0x0C)&1,(a>>0x0D)&1,(a>>0x0E)&1,(a>>0x0F)&1, |
| (a>>0x10)&1,(a>>0x11)&1,(a>>0x12)&1,(a>>0x13)&1, |
| (a>>0x14)&1,(a>>0x15)&1,(a>>0x16)&1,(a>>0x17)&1, |
| (a>>0x18)&1,(a>>0x19)&1,(a>>0x1A)&1,(a>>0x1B)&1, |
| (a>>0x1C)&1,(a>>0x1D)&1,(a>>0x1E)&1,(a>>0x1F)&1); |
| } |
| |
| fprintf(stderr,"\n"); |
| } |
| |
| #endif |
| |
| // |
| // |
| // |
| |
| skc_grid_t |
| skc_grid_deps_attach(skc_grid_deps_t const deps, |
| skc_grid_t * const addr, |
| void * const data, |
| skc_grid_pfn waiting_pfn, // upon READY > WAITING |
| skc_grid_pfn execute_pfn, // upon READY/WAITING > EXECUTING |
| skc_grid_pfn dispose_pfn, // upon EXECUTING > COMPLETE |
| char const * const waiting_name, |
| char const * const execute_name, |
| char const * const dispose_name) |
| { |
| // |
| // FIXME -- no more ids -- either fatal or flush & wait for grids to be released |
| // |
| // assert(deps->count < SKC_GRID_SIZE_IDS); |
| // |
| while (deps->count == SKC_GRID_SIZE_IDS) |
| skc_scheduler_wait_one(deps->scheduler); |
| |
| // otherwise, an id exists so decrement count |
| deps->count += 1; |
| |
| // find first set bit (1:inactive) |
| skc_uint * active = deps->active; |
| skc_uint first = 0; |
| |
| while (1) |
| { |
| skc_uint const idx = SKC_LZCNT_32(*active); |
| |
| first += idx; |
| |
| if (idx < 32) |
| { |
| // make inactive bit active: 1 -> 0 |
| *active &= ~(0x80000000 >> idx); // 0:active |
| break; |
| } |
| |
| // otherwise, inspect next word for inactive bit |
| active += 1; |
| } |
| |
| struct skc_grid * const grid = deps->grids + first; |
| |
| // save grid pointer |
| if (addr != NULL) |
| *addr = grid; |
| |
| // initialize elem |
| *grid = (struct skc_grid){ |
| .state = SKC_GRID_STATE_READY, |
| .id = first, |
| .deps = deps, |
| .addr = addr, |
| .data = data, |
| .waiting = { .pfn = waiting_pfn, .name = waiting_name }, |
| .execute = { .pfn = execute_pfn, .name = execute_name }, |
| .dispose = { .pfn = dispose_pfn, .name = dispose_name }, |
| .before = { { 0 }, 0 }, |
| .after = { { 0 }, 0 } |
| }; |
| |
| return grid; |
| } |
| |
| // |
| // |
| // |
| |
| static |
| skc_bool |
| skc_grid_words_set(skc_uint ids[SKC_GRID_SIZE_WORDS], skc_uint const id) |
| { |
| skc_uint * const ptr = ids + (id/32); |
| skc_uint const pre = *ptr; |
| skc_uint const post = pre | (0x80000000 >> (id & 0x1F)); // set |
| |
| *ptr = post; |
| |
| return pre != post; |
| } |
| |
| static |
| skc_bool |
| skc_grid_words_clear(skc_uint ids[SKC_GRID_SIZE_WORDS], skc_uint const id) |
| { |
| skc_uint * const ptr = ids + (id/32); |
| skc_uint const pre = *ptr; |
| skc_uint const post = pre & ~(0x80000000 >> (id & 0x1F)); // clear |
| |
| *ptr = post; |
| |
| return pre != post; |
| } |
| |
| // |
| // we may want to allow the host to detach a grid |
| // |
| |
| static |
| void |
| skc_grid_detach(skc_grid_t const grid) |
| { |
| // for now make sure grid is complete |
| // assert(grid->state == SKC_GRID_STATE_COMPLETE); |
| |
| // transition state |
| grid->state = SKC_GRID_STATE_DETACHED; |
| |
| // |
| // FIXME -- save profiling info |
| // |
| |
| // cleanup |
| if (skc_grid_words_set(grid->deps->active,grid->id)) // 1:inactive |
| grid->deps->count -= 1; |
| } |
| |
| // |
| // |
| // |
| |
| void |
| skc_grid_map(skc_grid_t const grid, skc_handle_t const handle) |
| { |
| grid->deps->handle_map[handle] = grid->id; |
| } |
| |
| // |
| // |
| // |
| |
| void |
| skc_grid_deps_force(skc_grid_deps_t const deps, |
| skc_handle_t const * const handles, |
| skc_uint const count) |
| { |
| // |
| // FIXME -- test to make sure handles aren't completely out of range integers |
| // |
| skc_grid_id_t * const handle_map = deps->handle_map; |
| |
| for (skc_uint ii=0; ii<count; ii++) |
| { |
| skc_grid_id_t grid_id = handle_map[SKC_TYPED_HANDLE_TO_HANDLE(handles[ii])]; |
| |
| if (grid_id < SKC_GRID_ID_INVALID) |
| { |
| skc_grid_t const grid = deps->grids + grid_id; |
| |
| skc_grid_force(grid); |
| |
| while (grid->state >= SKC_GRID_STATE_COMPLETE) |
| skc_scheduler_wait_one(deps->scheduler); |
| } |
| } |
| } |
| |
| void |
| skc_grid_deps_unmap(skc_grid_deps_t const deps, |
| skc_handle_t const * const handles, |
| skc_uint const count) |
| { |
| skc_grid_id_t * const handle_map = deps->handle_map; |
| |
| for (skc_uint ii=0; ii<count; ii++) |
| handle_map[handles[ii]] = SKC_GRID_ID_INVALID; |
| } |
| |
| // |
| // NOTE: We want this routine to be very very fast. The array of bit |
| // flags is probably as fast as we can go for a modest number of |
| // grids. |
| // |
| // NOTE: The before grid should never be NULL. This means the grid's |
| // lifecycle should match the lifetime of the object it represents. |
| // This also means the grid "invalidation upon start" feature should |
| // be well understood before using it to clear the skc_grid_t. |
| // |
| |
| void |
| skc_grid_happens_after_grid(skc_grid_t const after, |
| skc_grid_t const before) |
| { |
| // declarations can't be made on non-ready grids |
| assert(after->state == SKC_GRID_STATE_READY); |
| |
| if (before->state >= SKC_GRID_STATE_COMPLETE) |
| return; |
| |
| if (skc_grid_words_set(after->before.words,before->id)) |
| after->before.count += 1; |
| |
| if (skc_grid_words_set(before->after.words,after->id)) |
| before->after.count += 1; |
| } |
| |
| void |
| skc_grid_happens_after_handle(skc_grid_t const after, skc_handle_t const before) |
| { |
| assert(after->state == SKC_GRID_STATE_READY); |
| |
| skc_uint const id_before = after->deps->handle_map[before]; |
| |
| if (id_before >= SKC_GRID_ID_INVALID) |
| return; |
| |
| if (skc_grid_words_set(after->before.words,id_before)) |
| after->before.count += 1; |
| |
| skc_grid_t const grid_before = after->deps->grids + id_before; |
| |
| if (skc_grid_words_set(grid_before->after.words,after->id)) |
| grid_before->after.count += 1; |
| } |
| |
| // |
| // Remove dependency from grid |
| // |
| |
| static |
| void |
| skc_grid_clear_dependency(skc_grid_t const after, skc_uint const before) |
| { |
| skc_bool const is_change = skc_grid_words_clear(after->before.words,before); |
| |
| assert(is_change); // for now let's make sure this is a rising edge |
| |
| after->before.count -= 1; |
| |
| if ((after->before.count == 0) && ((after->state == SKC_GRID_STATE_WAITING) || |
| (after->state == SKC_GRID_STATE_FORCED))) |
| { |
| // schedule grid for execution |
| after->state = SKC_GRID_STATE_EXECUTING; |
| skc_grid_schedule(after,&after->execute); |
| } |
| } |
| |
| // |
| // Start the ready grid and wait for dependencies to complete |
| // |
| |
| void |
| skc_grid_start(skc_grid_t const grid) |
| { |
| // nothing to do if this grid isn't in a ready state |
| if (grid->state != SKC_GRID_STATE_READY) |
| return; |
| |
| // record transition through waiting state |
| grid->state = SKC_GRID_STATE_WAITING; |
| |
| // the waiting pfn may be null -- e.g. the path builder |
| // skc_grid_schedule(grid,&grid->waiting); |
| skc_grid_call(grid,&grid->waiting); |
| |
| // clear the reference |
| skc_grid_invalidate(grid); |
| |
| // execute if there are no dependencies |
| if (grid->before.count == 0) |
| { |
| // tell grid it can execute |
| grid->state = SKC_GRID_STATE_EXECUTING; |
| skc_grid_schedule(grid,&grid->execute); |
| } |
| } |
| |
| // |
| // Start this grid and all its ready dependencies |
| // |
| |
| void |
| skc_grid_force(skc_grid_t const grid) |
| { |
| // return if this grid was forced, executing or complete |
| if (grid->state >= SKC_GRID_STATE_FORCED) |
| return; |
| |
| // if ready then move to waiting state |
| if (grid->state == SKC_GRID_STATE_READY) |
| { |
| // tell grid to wait for execution |
| grid->state = SKC_GRID_STATE_WAITING; |
| |
| // the waiting pfn may be null -- e.g. the path builder |
| // skc_grid_schedule(grid,&grid->waiting); |
| skc_grid_call(grid,&grid->waiting); |
| |
| // clear the reference |
| skc_grid_invalidate(grid); |
| } |
| |
| skc_uint before_count = grid->before.count; |
| |
| // if there are no grid dependencies then execute |
| if (before_count == 0) |
| { |
| // tell grid it can execute |
| grid->state = SKC_GRID_STATE_EXECUTING; |
| skc_grid_schedule(grid,&grid->execute); |
| } |
| else // otherwise, start or make waiting all dependencies |
| { |
| grid->state = SKC_GRID_STATE_FORCED; |
| |
| struct skc_grid * before = grid->deps->grids; |
| skc_uint * before_words = grid->before.words; |
| skc_uint active = *before_words++; |
| |
| while (true) |
| { |
| // find first active |
| skc_uint const idx = SKC_LZCNT_32(active); |
| |
| // no bits set so inspect next word |
| if (idx == 32) |
| { |
| active = *before_words++; |
| before += 1; |
| continue; |
| } |
| else // clear active |
| { |
| active &= ~(0x80000000 >> idx); |
| before_count -= 1; |
| } |
| |
| // otherwise, force this elem with dependent |
| skc_grid_force(before+idx); |
| |
| // no more bits? |
| if (before_count == 0) |
| break; |
| } |
| } |
| } |
| |
| // |
| // Notify grids dependent on this grid that this grid is complete |
| // |
| |
| void |
| skc_grid_complete(skc_grid_t const grid) |
| { |
| // debug: grid was executing |
| assert(grid->state == SKC_GRID_STATE_EXECUTING); |
| |
| // move grid to completion and dispose after notifying dependents |
| grid->state = SKC_GRID_STATE_COMPLETE; |
| |
| skc_uint after_count = grid->after.count; |
| |
| if (after_count > 0) |
| { |
| // find set bits |
| struct skc_grid * after = grid->deps->grids; |
| skc_uint * after_words = grid->after.words; |
| skc_uint active = *after_words++; |
| |
| while (true) |
| { |
| // find first active |
| skc_uint const idx = SKC_LZCNT_32(active); |
| |
| // no bits set so inspect next word |
| if (idx == 32) |
| { |
| active = *after_words++; |
| after += 32; |
| continue; |
| } |
| else // clear active |
| { |
| active &= ~(0x80000000 >> idx); |
| after_count -= 1; |
| } |
| |
| // otherwise, clear this dependency |
| skc_grid_clear_dependency(after+idx,grid->id); |
| |
| // no more bits? |
| if (after_count == 0) |
| break; |
| } |
| } |
| |
| // dispose of resources |
| skc_grid_call(grid,&grid->dispose); |
| |
| // we don't need to hang on to this grid id any longer |
| skc_grid_detach(grid); |
| } |
| |
| /////////////////////////////////////////////////////////////////////////// |
| // |
| // ALTERNATIVE IMPLEMENTATION WOULD SUPPORT A VARIABLE NUMBER OF |
| // ACTIVE GRIDS PER STAGE PRESUMABLY RESULTING IN SLIGHTLY LESS MEMORY |
| // USAGE. |
| // |
| // THE #1 OBJECTIVE OF THE GRID IMPLEMENTATION IS TO ENSURE THAT THE |
| // "HAPPENS-BEFORE" DECLARATION REMAINS ***FAST*** SINCE IT WILL BE |
| // CALLED FREQUENTLY. THUS THE |GRIDS|^2 BIT ARRAY... |
| // |
| // WE DON'T NEED THIS RIGHT NOW... |
| // |
| |
| #if 0 |
| |
| // |
| // For now, make them all the same size |
| // |
| |
| #define SKC_GRID_STAGE_WORDS_PATH_BUILDER SKC_GRID_MASK_WORDS |
| #define SKC_GRID_STAGE_WORDS_RASTER_BUILDER SKC_GRID_MASK_WORDS |
| #define SKC_GRID_STAGE_WORDS_COMPOSITION SKC_GRID_MASK_WORDS |
| #define SKC_GRID_STAGE_WORDS_STYLING SKC_GRID_MASK_WORDS |
| #define SKC_GRID_STAGE_WORDS_SURFACE_COMPOSITION SKC_GRID_MASK_WORDS |
| #define SKC_GRID_STAGE_WORDS_SURFACE_STYLING SKC_GRID_MASK_WORDS |
| |
| // |
| // |
| // |
| |
| typedef enum skc_grid_stage_type { |
| |
| SKC_GRID_STAGE_TYPE_PATH_BUILDER, |
| SKC_GRID_STAGE_TYPE_RASTER_BUILDER, |
| SKC_GRID_STAGE_TYPE_COMPOSITION, |
| SKC_GRID_STAGE_TYPE_STYLING, |
| SKC_GRID_STAGE_TYPE_SURFACE_COMPOSITION, |
| SKC_GRID_STAGE_TYPE_SURFACE_STYLING, |
| |
| SKC_GRID_STAGE_TYPE_COUNT |
| |
| } skc_grid_stage_type; |
| |
| // |
| // |
| // |
| |
| union skc_grid_id |
| { |
| skc_grid_id_t u32; |
| |
| struct { |
| skc_ushort index; |
| skc_ushort stage; |
| }; |
| } |
| |
| SKC_STATIC_ASSERT(sizeof(union skc_grid_id) == sizeof(skc_uint)); |
| |
| // |
| // |
| // |
| |
| #endif |
| |
| // |
| // |
| // |