Blender V5.3
lazy_function_graph_executor_generic.hh
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
45
46#pragma once
47
48#include <atomic>
49
51#include "BLI_function_ref.hh"
52#include "BLI_mutex.hh"
53#include "BLI_stack.hh"
54#include "BLI_task.hh"
55#include "BLI_task_c.hh"
56
59
61
84
106
136
192
217
218class GenericGraphExecutor;
219class GraphExecutorLFParams;
220
226 private:
230
231 public:
232 void schedule(const FunctionNode &node, const bool is_priority)
233 {
234 if (is_priority) {
235 this->priority_.append(&node);
236 }
237 else {
238 this->normal_.append(&node);
239 }
240 }
241
243 {
244 if (!this->priority_.is_empty()) {
245 return this->priority_.pop_last();
246 }
247 if (!this->normal_.is_empty()) {
248 return this->normal_.pop_last();
249 }
250 return nullptr;
251 }
252
253 bool is_empty() const
254 {
255 return this->priority_.is_empty() && this->normal_.is_empty();
256 }
257
259 {
260 return priority_.size() + normal_.size();
261 }
262
267 {
268 BLI_assert(this != &other);
269 const int64_t priority_split = priority_.size() / 2;
270 const int64_t normal_split = normal_.size() / 2;
271 other.priority_.extend(priority_.as_span().drop_front(priority_split));
272 other.normal_.extend(normal_.as_span().drop_front(normal_split));
273 priority_.resize(priority_split);
274 normal_.resize(normal_split);
275 }
276};
277
293
295 private:
296 const GraphExecutor &self_;
301 MutableSpan<std::atomic<uint8_t>> loaded_inputs_;
305 MutableSpan<NodeState *> node_states_;
309 Params *params_ = nullptr;
310 const Context *context_ = nullptr;
315 std::atomic<TaskPool *> task_pool_ = nullptr;
316#ifdef FN_LAZY_FUNCTION_DEBUG_THREADS
317 std::thread::id current_main_thread_;
318#endif
319
320 GraphExecutorLogger::LoggingEnabledState logging_enabled_state_{false};
321
322 struct ThreadLocalStorage {
327 LinearAllocator<> allocator;
328 std::optional<destruct_ptr<LocalUserData>> local_user_data;
329 };
330 std::unique_ptr<threading::EnumerableThreadSpecific<ThreadLocalStorage>> thread_locals_;
331 LinearAllocator<> main_allocator_;
335 bool is_first_execution_ = true;
336
337 friend GraphExecutorLFParams;
338
345 struct LocalData {
346 LinearAllocator<> *allocator;
347 LocalUserData *local_user_data;
348 };
349
350 public:
351 GenericGraphExecutor(const GraphExecutor &self) : self_(self)
352 {
353 /* The indices are necessary, because they are used as keys in #node_states_. */
354 BLI_assert(self_.graph_.node_indices_are_valid());
355 }
356
358 {
359 if (TaskPool *task_pool = task_pool_.load()) {
360 BLI_task_pool_free(task_pool);
361 }
362 threading::parallel_for(node_states_.index_range(), 1024, [&](const IndexRange range) {
363 for (const int node_index : range) {
364 const Node &node = *self_.graph_.nodes()[node_index];
365 NodeState &node_state = *node_states_[node_index];
366 this->destruct_node_state(node, node_state);
367 }
368 });
369 }
370
374 void execute(Params &params, const Context &context)
375 {
376 params_ = &params;
377 context_ = &context;
378#ifdef FN_LAZY_FUNCTION_DEBUG_THREADS
379 current_main_thread_ = std::this_thread::get_id();
380#endif
381 const auto deferred_func = [&]() {
382 /* Make sure the pointers are not dangling, even when it shouldn't be accessed by anyone. */
383 params_ = nullptr;
384 context_ = nullptr;
385 is_first_execution_ = false;
386#ifdef FN_LAZY_FUNCTION_DEBUG_THREADS
387 current_main_thread_ = {};
388#endif
389 };
390 BLI_SCOPED_DEFER(deferred_func);
391
392 const LocalData local_data = this->get_local_data();
393
394 CurrentTask current_task;
395 if (is_first_execution_) {
396 if (self_.logger_) {
397 logging_enabled_state_ = self_.logger_->get_logging_enabled_state(context);
398 }
399
400 /* Allocate a single large buffer instead of making many smaller allocations below. */
401 char *buffer = static_cast<char *>(
402 local_data.allocator->allocate(self_.preprocess_data_.total_size, alignof(void *)));
403 this->initialize_node_states(buffer);
404
405 loaded_inputs_ = MutableSpan{reinterpret_cast<std::atomic<uint8_t> *>(
406 buffer + self_.preprocess_data_.loaded_inputs_array_offset),
407 self_.graph_inputs_.size()};
408 /* Initialize atomics to zero. */
409 memset(static_cast<void *>(loaded_inputs_.data()), 0, loaded_inputs_.size() * sizeof(bool));
410
411 this->set_always_unused_graph_inputs();
412 this->set_defaulted_graph_outputs(local_data);
413
414 /* Retrieve and tag side effect nodes. */
415 Vector<const FunctionNode *> side_effect_nodes;
416 if (self_.side_effect_provider_ != nullptr) {
417 side_effect_nodes = self_.side_effect_provider_->get_nodes_with_side_effects(context);
418 for (const FunctionNode *node : side_effect_nodes) {
419 BLI_assert(self_.graph_.nodes().contains(node));
420 const int node_index = node->index_in_graph();
421 NodeState &node_state = *node_states_[node_index];
422 node_state.has_side_effects = true;
423 }
424 }
425
426 this->initialize_static_value_usages(side_effect_nodes);
427 this->schedule_side_effect_nodes(side_effect_nodes, current_task, local_data);
428 }
429
430 this->schedule_for_new_output_usages(current_task, local_data);
431 this->forward_newly_provided_inputs(current_task, local_data);
432
433 this->run_task(current_task, local_data);
434
435 if (TaskPool *task_pool = task_pool_.load()) {
437 }
438 }
439
441 {
442 PreprocessData &r_data = self.preprocess_data_;
443
444 /* Preprocess buffer offsets. */
445 int offset = 0;
446 const Span<const Node *> nodes = self.graph_.nodes();
447 r_data.node_states_array_offset = offset;
448 offset += sizeof(NodeState *) * nodes.size();
449 r_data.loaded_inputs_array_offset = offset;
450 offset += sizeof(std::atomic<uint8_t>) * self.graph_inputs_.size();
451 /* Align offset. */
452 offset = (offset + sizeof(void *) - 1) & ~(sizeof(void *) - 1);
453
454 r_data.node_states_offsets.reinitialize(self.graph_.nodes().size());
455 for (const int i : nodes.index_range()) {
456 const Node &node = *nodes[i];
457 r_data.node_states_offsets[i] = offset;
458 offset += sizeof(NodeState);
459 offset += sizeof(InputState) * node.inputs().size();
460 offset += sizeof(OutputState) * node.outputs().size();
461 /* Make sure we don't have to worry about alignment. */
462 static_assert(sizeof(NodeState) % sizeof(void *) == 0);
463 static_assert(sizeof(InputState) % sizeof(void *) == 0);
464 static_assert(sizeof(OutputState) % sizeof(void *) == 0);
465 }
466
467 r_data.total_size = offset;
468 }
469
470 private:
471 void initialize_node_states(char *buffer)
472 {
473 Span<const Node *> nodes = self_.graph_.nodes();
474 node_states_ = MutableSpan{
475 reinterpret_cast<NodeState **>(buffer + self_.preprocess_data_.node_states_array_offset),
476 nodes.size()};
477
478 threading::parallel_for(nodes.index_range(), 1024, [&](const IndexRange range) {
479 for (const int i : range) {
480 const Node &node = *nodes[i];
481 char *memory = buffer + self_.preprocess_data_.node_states_offsets[i];
482
483 /* Initialize node state. */
484 NodeState *node_state = reinterpret_cast<NodeState *>(memory);
485 memory += sizeof(NodeState);
486 new (node_state) NodeState();
487
488 /* Initialize socket states. */
489 const int num_inputs = node.inputs().size();
490 const int num_outputs = node.outputs().size();
491 node_state->inputs = reinterpret_cast<InputState *>(memory);
492 memory += sizeof(InputState) * num_inputs;
493 node_state->outputs = reinterpret_cast<OutputState *>(memory);
494
495 default_construct_n(node_state->inputs, num_inputs);
496 default_construct_n(node_state->outputs, num_outputs);
497
498 node_states_[i] = node_state;
499 }
500 });
501 }
502
503 void destruct_node_state(const Node &node, NodeState &node_state)
504 {
505 if (node.is_function()) {
506 const LazyFunction &fn = static_cast<const FunctionNode &>(node).function();
507 if (node_state.storage != nullptr) {
508 fn.destruct_storage(node_state.storage);
509 }
510 }
511 for (const int i : node.inputs().index_range()) {
512 InputState &input_state = node_state.inputs[i];
513 const InputSocket &input_socket = node.input(i);
514 this->destruct_input_value_if_exists(input_state, input_socket.type());
515 }
516 std::destroy_at(&node_state);
517 }
518
522 void schedule_for_new_output_usages(CurrentTask &current_task, const LocalData &local_data)
523 {
524 for (const int graph_output_index : self_.graph_outputs_.index_range()) {
525 if (params_->output_was_set(graph_output_index)) {
526 continue;
527 }
528 const ValueUsage output_usage = params_->get_output_usage(graph_output_index);
529 if (output_usage == ValueUsage::Maybe) {
530 continue;
531 }
532 const InputSocket &socket = *self_.graph_outputs_[graph_output_index];
533 const Node &node = socket.node();
534 NodeState &node_state = *node_states_[node.index_in_graph()];
535 this->with_locked_node(
536 node, node_state, current_task, local_data, [&](LockedNode &locked_node) {
537 if (output_usage == ValueUsage::Used) {
538 this->set_input_required(locked_node, socket);
539 }
540 else {
541 this->set_input_unused(locked_node, socket);
542 }
543 });
544 }
545 }
546
547 void set_defaulted_graph_outputs(const LocalData &local_data)
548 {
549 for (const int graph_output_index : self_.graph_outputs_.index_range()) {
550 const InputSocket &socket = *self_.graph_outputs_[graph_output_index];
551 if (socket.origin() != nullptr) {
552 continue;
553 }
554 const CPPType &type = socket.type();
555 const void *default_value = socket.default_value();
556 BLI_assert(default_value != nullptr);
557
558 if (logging_enabled_state_.socket_values) {
559 const Context context{context_->storage, context_->user_data, local_data.local_user_data};
560 self_.logger_->log_socket_value(socket, {type, default_value}, context);
561 }
562
563 void *output_ptr = params_->get_output_data_ptr(graph_output_index);
564 type.copy_construct(default_value, output_ptr);
565 params_->output_set(graph_output_index);
566 }
567 }
568
569 void set_always_unused_graph_inputs()
570 {
571 for (const int i : self_.graph_inputs_.index_range()) {
572 const OutputSocket &socket = *self_.graph_inputs_[i];
573 const Node &node = socket.node();
574 const NodeState &node_state = *node_states_[node.index_in_graph()];
575 const OutputState &output_state = node_state.outputs[socket.index()];
576 if (output_state.usage == ValueUsage::Unused) {
577 params_->set_input_unused(i);
578 }
579 }
580 }
581
589 void initialize_static_value_usages(const Span<const FunctionNode *> side_effect_nodes)
590 {
591 const Span<const Node *> all_nodes = self_.graph_.nodes();
592
593 /* Used for a search through all nodes that outputs depend on. */
594 Stack<const Node *> reachable_nodes_to_check;
595 Array<bool> reachable_node_flags(all_nodes.size(), false);
596
597 /* Graph outputs are always reachable. */
598 for (const InputSocket *socket : self_.graph_outputs_) {
599 const Node &node = socket->node();
600 const int node_index = node.index_in_graph();
601 if (!reachable_node_flags[node_index]) {
602 reachable_node_flags[node_index] = true;
603 reachable_nodes_to_check.push(&node);
604 }
605 }
606
607 /* Side effect nodes are always reachable. */
608 for (const FunctionNode *node : side_effect_nodes) {
609 const int node_index = node->index_in_graph();
610 reachable_node_flags[node_index] = true;
611 reachable_nodes_to_check.push(node);
612 }
613
614 /* Tag every node that reachable nodes depend on using depth-first-search. */
615 while (!reachable_nodes_to_check.is_empty()) {
616 const Node &node = *reachable_nodes_to_check.pop();
617 for (const InputSocket *input_socket : node.inputs()) {
618 const OutputSocket *origin_socket = input_socket->origin();
619 if (origin_socket != nullptr) {
620 const Node &origin_node = origin_socket->node();
621 const int origin_node_index = origin_node.index_in_graph();
622 if (!reachable_node_flags[origin_node_index]) {
623 reachable_node_flags[origin_node_index] = true;
624 reachable_nodes_to_check.push(&origin_node);
625 }
626 }
627 }
628 }
629
630 for (const int node_index : reachable_node_flags.index_range()) {
631 const Node &node = *all_nodes[node_index];
632 NodeState &node_state = *node_states_[node_index];
633 const bool node_is_reachable = reachable_node_flags[node_index];
634 if (node_is_reachable) {
635 for (const int output_index : node.outputs().index_range()) {
636 const OutputSocket &output_socket = node.output(output_index);
637 OutputState &output_state = node_state.outputs[output_index];
638 int use_count = 0;
639 for (const InputSocket *target_socket : output_socket.targets()) {
640 const Node &target_node = target_socket->node();
641 const bool target_is_reachable = reachable_node_flags[target_node.index_in_graph()];
642 /* Only count targets that are reachable. */
643 if (target_is_reachable) {
644 use_count++;
645 }
646 }
647 output_state.potential_target_sockets = use_count;
648 if (use_count == 0) {
649 output_state.usage = ValueUsage::Unused;
650 }
651 }
652 }
653 else {
654 /* Inputs of unreachable nodes are unused. */
655 for (const int input_index : node.inputs().index_range()) {
656 node_state.inputs[input_index].usage = ValueUsage::Unused;
657 }
658 }
659 }
660 }
661
662 void schedule_side_effect_nodes(const Span<const FunctionNode *> side_effect_nodes,
663 CurrentTask &current_task,
664 const LocalData &local_data)
665 {
666 for (const FunctionNode *node : side_effect_nodes) {
667 NodeState &node_state = *node_states_[node->index_in_graph()];
668 this->with_locked_node(
669 *node, node_state, current_task, local_data, [&](LockedNode &locked_node) {
670 this->schedule_node(locked_node, current_task, false);
671 });
672 }
673 }
674
675 void forward_newly_provided_inputs(CurrentTask &current_task, const LocalData &local_data)
676 {
677 for (const int graph_input_index : self_.graph_inputs_.index_range()) {
678 std::atomic<uint8_t> &was_loaded = loaded_inputs_[graph_input_index];
679 if (was_loaded.load()) {
680 continue;
681 }
682 void *input_data = params_->try_get_input_data_ptr(graph_input_index);
683 if (input_data == nullptr) {
684 continue;
685 }
686 if (was_loaded.fetch_or(1)) {
687 /* The value was forwarded before. */
688 continue;
689 }
690 this->forward_newly_provided_input(current_task, local_data, graph_input_index, input_data);
691 }
692 }
693
694 void forward_newly_provided_input(CurrentTask &current_task,
695 const LocalData &local_data,
696 const int graph_input_index,
697 void *input_data)
698 {
699 const OutputSocket &socket = *self_.graph_inputs_[graph_input_index];
700 const CPPType &type = socket.type();
701 void *buffer = local_data.allocator->allocate(type);
702 type.move_construct(input_data, buffer);
703 this->forward_value_to_linked_inputs(socket, {type, buffer}, current_task, local_data);
704 }
705
706 void notify_output_required(const OutputSocket &socket,
707 CurrentTask &current_task,
708 const LocalData &local_data)
709 {
710 const Node &node = socket.node();
711 const int index_in_node = socket.index();
712 NodeState &node_state = *node_states_[node.index_in_graph()];
713 OutputState &output_state = node_state.outputs[index_in_node];
714
715 /* The notified output socket might be an input of the entire graph. In this case, notify the
716 * caller that the input is required. */
717 if (node.is_interface()) {
718 const int graph_input_index = self_.graph_input_index_by_socket_index_[socket.index()];
719 std::atomic<uint8_t> &was_loaded = loaded_inputs_[graph_input_index];
720 if (was_loaded.load()) {
721 return;
722 }
723 void *input_data = params_->try_get_input_data_ptr_or_request(graph_input_index);
724 if (input_data == nullptr) {
725 return;
726 }
727 if (was_loaded.fetch_or(1)) {
728 /* The value was forwarded already. */
729 return;
730 }
731 this->forward_newly_provided_input(current_task, local_data, graph_input_index, input_data);
732 return;
733 }
734
735 BLI_assert(node.is_function());
736 this->with_locked_node(
737 node, node_state, current_task, local_data, [&](LockedNode &locked_node) {
738 if (output_state.usage == ValueUsage::Used) {
739 return;
740 }
741 output_state.usage = ValueUsage::Used;
742 this->schedule_node(locked_node, current_task, false);
743 });
744 }
745
746 void notify_output_unused(const OutputSocket &socket,
747 CurrentTask &current_task,
748 const LocalData &local_data)
749 {
750 const Node &node = socket.node();
751 const int index_in_node = socket.index();
752 NodeState &node_state = *node_states_[node.index_in_graph()];
753 OutputState &output_state = node_state.outputs[index_in_node];
754
755 this->with_locked_node(
756 node, node_state, current_task, local_data, [&](LockedNode &locked_node) {
757 output_state.potential_target_sockets -= 1;
758 if (output_state.potential_target_sockets == 0) {
759 BLI_assert(output_state.usage != ValueUsage::Unused);
760 if (output_state.usage == ValueUsage::Maybe) {
761 output_state.usage = ValueUsage::Unused;
762 if (node.is_interface()) {
763 const int graph_input_index =
764 self_.graph_input_index_by_socket_index_[socket.index()];
765 params_->set_input_unused(graph_input_index);
766 }
767 else {
768 /* Schedule as priority node. This allows freeing up memory earlier which results
769 * in better memory reuse and fewer implicit sharing copies. */
770 this->schedule_node(locked_node, current_task, true);
771 }
772 }
773 }
774 });
775 }
776
777 void schedule_node(LockedNode &locked_node, CurrentTask &current_task, const bool is_priority)
778 {
779 BLI_assert(locked_node.node.is_function());
780 switch (locked_node.node_state.schedule_state) {
781 case NodeScheduleState::NotScheduled: {
782 locked_node.node_state.schedule_state = NodeScheduleState::Scheduled;
783 const FunctionNode &node = static_cast<const FunctionNode &>(locked_node.node);
784 if (this->use_multi_threading()) {
785 std::lock_guard lock{current_task.mutex};
786 current_task.scheduled_nodes.schedule(node, is_priority);
787 }
788 else {
789 current_task.scheduled_nodes.schedule(node, is_priority);
790 }
791 current_task.has_scheduled_nodes.store(true, std::memory_order_relaxed);
792 break;
793 }
794 case NodeScheduleState::Scheduled: {
795 break;
796 }
797 case NodeScheduleState::Running: {
798 locked_node.node_state.schedule_state = NodeScheduleState::RunningAndRescheduled;
799 break;
800 }
801 case NodeScheduleState::RunningAndRescheduled: {
802 break;
803 }
804 }
805 }
806
807 void with_locked_node(const Node &node,
808 NodeState &node_state,
809 CurrentTask &current_task,
810 const LocalData &local_data,
811 const FunctionRef<void(LockedNode &)> f)
812 {
813 BLI_assert(&node_state == node_states_[node.index_in_graph()]);
814
815 LockedNode locked_node{node, node_state};
816 if (this->use_multi_threading()) {
817 std::lock_guard lock{node_state.mutex};
818 threading::isolate_task([&]() { f(locked_node); });
819 }
820 else {
821 f(locked_node);
822 }
823
824 this->send_output_required_notifications(
825 locked_node.delayed_required_outputs, current_task, local_data);
826 this->send_output_unused_notifications(
827 locked_node.delayed_unused_outputs, current_task, local_data);
828 }
829
830 void send_output_required_notifications(const Span<const OutputSocket *> sockets,
831 CurrentTask &current_task,
832 const LocalData &local_data)
833 {
834 for (const OutputSocket *socket : sockets) {
835 this->notify_output_required(*socket, current_task, local_data);
836 }
837 }
838
839 void send_output_unused_notifications(const Span<const OutputSocket *> sockets,
840 CurrentTask &current_task,
841 const LocalData &local_data)
842 {
843 for (const OutputSocket *socket : sockets) {
844 this->notify_output_unused(*socket, current_task, local_data);
845 }
846 }
847
848 void run_task(CurrentTask &current_task, const LocalData &local_data)
849 {
850 while (const FunctionNode *node = current_task.scheduled_nodes.pop_next_node()) {
851 if (current_task.scheduled_nodes.is_empty()) {
852 current_task.has_scheduled_nodes.store(false, std::memory_order_relaxed);
853 }
854 this->run_node_task(*node, current_task, local_data);
855
856 /* If there are many nodes scheduled at the same time, it's beneficial to let multiple
857 * threads work on those. */
858 if (current_task.scheduled_nodes.nodes_num() > 128) {
859 if (this->try_enable_multi_threading()) {
860 std::unique_ptr<ScheduledNodes> split_nodes = std::make_unique<ScheduledNodes>();
861 current_task.scheduled_nodes.split_into(*split_nodes);
862 this->push_to_task_pool(std::move(split_nodes));
863 }
864 }
865 }
866 }
867
868 void run_node_task(const FunctionNode &node,
869 CurrentTask &current_task,
870 const LocalData &local_data)
871 {
872 NodeState &node_state = *node_states_[node.index_in_graph()];
873 LinearAllocator<> &allocator = *local_data.allocator;
874 Context local_context{context_->storage, context_->user_data, local_data.local_user_data};
875 const LazyFunction &fn = node.function();
876
877 bool node_needs_execution = false;
878 this->with_locked_node(
879 node, node_state, current_task, local_data, [&](LockedNode &locked_node) {
880 BLI_assert(node_state.schedule_state == NodeScheduleState::Scheduled);
881 node_state.schedule_state = NodeScheduleState::Running;
882
883 if (node_state.node_has_finished) {
884 return;
885 }
886
887 bool required_uncomputed_output_exists = false;
888 for (const int output_index : node.outputs().index_range()) {
889 OutputState &output_state = node_state.outputs[output_index];
890 output_state.usage_for_execution = output_state.usage;
891 if (output_state.usage == ValueUsage::Used && !output_state.has_been_computed) {
892 required_uncomputed_output_exists = true;
893 }
894 }
895 if (!required_uncomputed_output_exists && !node_state.has_side_effects) {
896 return;
897 }
898
899 if (!node_state.always_used_inputs_requested) {
900 /* Request linked inputs that are always needed. */
901 const Span<Input> fn_inputs = fn.inputs();
902 for (const int input_index : fn_inputs.index_range()) {
903 const Input &fn_input = fn_inputs[input_index];
904 if (fn_input.usage == ValueUsage::Used) {
905 const InputSocket &input_socket = node.input(input_index);
906 if (input_socket.origin() != nullptr) {
907 this->set_input_required(locked_node, input_socket);
908 }
909 }
910 }
911
912 node_state.always_used_inputs_requested = true;
913 }
914
915 for (const int input_index : node.inputs().index_range()) {
916 InputState &input_state = node_state.inputs[input_index];
917 if (input_state.was_ready_for_execution) {
918 continue;
919 }
920 if (input_state.value != nullptr) {
921 input_state.was_ready_for_execution = true;
922 continue;
923 }
924 if (!fn.allow_missing_requested_inputs()) {
925 if (input_state.usage == ValueUsage::Used) {
926 return;
927 }
928 }
929 }
930
931 node_needs_execution = true;
932 });
933
934 if (node_needs_execution) {
935 if (!node_state.storage_and_defaults_initialized) {
936 /* Initialize storage. */
937 node_state.storage = fn.init_storage(allocator);
938
939 /* Load unlinked inputs. */
940 for (const int input_index : node.inputs().index_range()) {
941 const InputSocket &input_socket = node.input(input_index);
942 if (input_socket.origin() != nullptr) {
943 continue;
944 }
945 InputState &input_state = node_state.inputs[input_index];
946 const CPPType &type = input_socket.type();
947 const void *default_value = input_socket.default_value();
948 BLI_assert(default_value != nullptr);
949 if (logging_enabled_state_.socket_values) {
950 self_.logger_->log_socket_value(input_socket, {type, default_value}, local_context);
951 }
952 BLI_assert(input_state.value == nullptr);
953 input_state.value = allocator.allocate(type);
954 type.copy_construct(default_value, input_state.value);
955 input_state.was_ready_for_execution = true;
956 }
957
958 node_state.storage_and_defaults_initialized = true;
959 }
960
961 /* Importantly, the node must not be locked when it is executed. That would result in locks
962 * being hold very long in some cases and results in multiple locks being hold by the same
963 * thread in the same graph which can lead to deadlocks. */
964 this->execute_node(node, node_state, current_task, local_data);
965 }
966
967 this->with_locked_node(
968 node, node_state, current_task, local_data, [&](LockedNode &locked_node) {
969#ifndef NDEBUG
970 if (node_needs_execution) {
971 this->assert_expected_outputs_have_been_computed(locked_node, local_data);
972 }
973#endif
974 this->finish_node_if_possible(locked_node);
975 const bool reschedule_requested = node_state.schedule_state ==
976 NodeScheduleState::RunningAndRescheduled;
977 node_state.schedule_state = NodeScheduleState::NotScheduled;
978 if (reschedule_requested && !node_state.node_has_finished) {
979 this->schedule_node(locked_node, current_task, false);
980 }
981 });
982 }
983
984 void assert_expected_outputs_have_been_computed(LockedNode &locked_node,
985 const LocalData &local_data)
986 {
987 const FunctionNode &node = static_cast<const FunctionNode &>(locked_node.node);
988 const NodeState &node_state = locked_node.node_state;
989
990 if (node_state.missing_required_inputs > 0) {
991 return;
992 }
993 if (node_state.schedule_state == NodeScheduleState::RunningAndRescheduled) {
994 return;
995 }
996 Vector<const OutputSocket *> missing_outputs;
997 for (const int i : node.outputs().index_range()) {
998 const OutputState &output_state = node_state.outputs[i];
999 if (output_state.usage_for_execution == ValueUsage::Used) {
1000 if (!output_state.has_been_computed) {
1001 missing_outputs.append(&node.output(i));
1002 }
1003 }
1004 }
1005 if (!missing_outputs.is_empty()) {
1006 if (self_.logger_ != nullptr) {
1007 const Context context{context_->storage, context_->user_data, local_data.local_user_data};
1008 self_.logger_->dump_when_outputs_are_missing(node, missing_outputs, context);
1009 }
1011 }
1012 }
1013
1014 void finish_node_if_possible(LockedNode &locked_node)
1015 {
1016 const Node &node = locked_node.node;
1017 NodeState &node_state = locked_node.node_state;
1018
1019 if (node_state.node_has_finished) {
1020 /* Was finished already. */
1021 return;
1022 }
1023 /* If there are outputs that may still be used, the node is not done yet. */
1024 for (const int output_index : node.outputs().index_range()) {
1025 const OutputState &output_state = node_state.outputs[output_index];
1026 if (output_state.usage != ValueUsage::Unused && !output_state.has_been_computed) {
1027 return;
1028 }
1029 }
1030 /* If the node is still waiting for inputs, it is not done yet. */
1031 for (const int input_index : node.inputs().index_range()) {
1032 const InputState &input_state = node_state.inputs[input_index];
1033 if (input_state.usage == ValueUsage::Used && !input_state.was_ready_for_execution) {
1034 return;
1035 }
1036 }
1037
1038 node_state.node_has_finished = true;
1039
1040 for (const int input_index : node.inputs().index_range()) {
1041 const InputSocket &input_socket = node.input(input_index);
1042 InputState &input_state = node_state.inputs[input_index];
1043 if (input_state.usage == ValueUsage::Maybe) {
1044 this->set_input_unused(locked_node, input_socket);
1045 }
1046 else if (input_state.usage == ValueUsage::Used) {
1047 this->destruct_input_value_if_exists(input_state, input_socket.type());
1048 }
1049 }
1050
1051 if (node_state.storage != nullptr) {
1052 if (node.is_function()) {
1053 const FunctionNode &fn_node = static_cast<const FunctionNode &>(node);
1054 fn_node.function().destruct_storage(node_state.storage);
1055 }
1056 node_state.storage = nullptr;
1057 }
1058 }
1059
1060 void destruct_input_value_if_exists(InputState &input_state, const CPPType &type)
1061 {
1062 if (input_state.value != nullptr) {
1063 type.destruct(input_state.value);
1064 input_state.value = nullptr;
1065 }
1066 }
1067
1068 void execute_node(const FunctionNode &node,
1069 NodeState &node_state,
1070 CurrentTask &current_task,
1071 const LocalData &local_data);
1072
1073 void set_input_unused_during_execution(const Node &node,
1074 NodeState &node_state,
1075 const int input_index,
1076 CurrentTask &current_task,
1077 const LocalData &local_data)
1078 {
1079 const InputSocket &input_socket = node.input(input_index);
1080 this->with_locked_node(
1081 node, node_state, current_task, local_data, [&](LockedNode &locked_node) {
1082 this->set_input_unused(locked_node, input_socket);
1083 });
1084 }
1085
1086 void set_input_unused(LockedNode &locked_node, const InputSocket &input_socket)
1087 {
1088 NodeState &node_state = locked_node.node_state;
1089 const int input_index = input_socket.index();
1090 InputState &input_state = node_state.inputs[input_index];
1091
1092 BLI_assert(input_state.usage != ValueUsage::Used);
1093 if (input_state.usage == ValueUsage::Unused) {
1094 return;
1095 }
1096 input_state.usage = ValueUsage::Unused;
1097
1098 this->destruct_input_value_if_exists(input_state, input_socket.type());
1099 if (input_state.was_ready_for_execution) {
1100 return;
1101 }
1102 const OutputSocket *origin = input_socket.origin();
1103 if (origin != nullptr) {
1104 locked_node.delayed_unused_outputs.append(origin);
1105 }
1106 }
1107
1108 void *set_input_required_during_execution(const Node &node,
1109 NodeState &node_state,
1110 const int input_index,
1111 CurrentTask &current_task,
1112 const LocalData &local_data)
1113 {
1114 const InputSocket &input_socket = node.input(input_index);
1115 void *result;
1116 this->with_locked_node(
1117 node, node_state, current_task, local_data, [&](LockedNode &locked_node) {
1118 result = this->set_input_required(locked_node, input_socket);
1119 });
1120 return result;
1121 }
1122
1123 void *set_input_required(LockedNode &locked_node, const InputSocket &input_socket)
1124 {
1125 BLI_assert(&locked_node.node == &input_socket.node());
1126 NodeState &node_state = locked_node.node_state;
1127 const int input_index = input_socket.index();
1128 InputState &input_state = node_state.inputs[input_index];
1129
1130 BLI_assert(input_state.usage != ValueUsage::Unused);
1131
1132 if (input_state.value != nullptr) {
1133 input_state.was_ready_for_execution = true;
1134 return input_state.value;
1135 }
1136 if (input_state.usage == ValueUsage::Used) {
1137 return nullptr;
1138 }
1139 input_state.usage = ValueUsage::Used;
1140 node_state.missing_required_inputs += 1;
1141
1142 const OutputSocket *origin_socket = input_socket.origin();
1143 /* Unlinked inputs are always loaded in advance. */
1144 BLI_assert(origin_socket != nullptr);
1145 locked_node.delayed_required_outputs.append(origin_socket);
1146 return nullptr;
1147 }
1148
1149 void forward_value_to_linked_inputs(const OutputSocket &from_socket,
1150 GMutablePointer value_to_forward,
1151 CurrentTask &current_task,
1152 const LocalData &local_data)
1153 {
1154 BLI_assert(value_to_forward.get() != nullptr);
1155 const CPPType &type = *value_to_forward.type();
1156 const Context local_context{
1157 context_->storage, context_->user_data, local_data.local_user_data};
1158
1159 if (logging_enabled_state_.socket_values) {
1160 self_.logger_->log_socket_value(from_socket, value_to_forward, local_context);
1161 }
1162
1163 const Span<const InputSocket *> targets = from_socket.targets();
1164 for (const InputSocket *target_socket : targets) {
1165 const Node &target_node = target_socket->node();
1166 NodeState &node_state = *node_states_[target_node.index_in_graph()];
1167 const int input_index = target_socket->index();
1168 InputState &input_state = node_state.inputs[input_index];
1169 const bool is_last_target = target_socket == targets.last();
1170#ifndef NDEBUG
1171 if (input_state.value != nullptr) {
1172 if (self_.logger_ != nullptr) {
1173 self_.logger_->dump_when_input_is_set_twice(*target_socket, from_socket, local_context);
1174 }
1176 }
1177#endif
1178 BLI_assert(!input_state.was_ready_for_execution);
1179 BLI_assert(target_socket->type() == type);
1180 BLI_assert(target_socket->origin() == &from_socket);
1181
1182 if (logging_enabled_state_.socket_values) {
1183 self_.logger_->log_socket_value(*target_socket, value_to_forward, local_context);
1184 }
1185 if (target_node.is_interface()) {
1186 /* Forward the value to the outside of the graph. */
1187 const int graph_output_index =
1188 self_.graph_output_index_by_socket_index_[target_socket->index()];
1189 if (graph_output_index != -1 &&
1190 params_->get_output_usage(graph_output_index) != ValueUsage::Unused)
1191 {
1192 void *dst_buffer = params_->get_output_data_ptr(graph_output_index);
1193 if (is_last_target) {
1194 type.move_construct(value_to_forward.get(), dst_buffer);
1195 }
1196 else {
1197 type.copy_construct(value_to_forward.get(), dst_buffer);
1198 }
1199 params_->output_set(graph_output_index);
1200 }
1201 continue;
1202 }
1203 this->with_locked_node(
1204 target_node, node_state, current_task, local_data, [&](LockedNode &locked_node) {
1205 if (input_state.usage == ValueUsage::Unused) {
1206 return;
1207 }
1208 if (is_last_target) {
1209 /* No need to make a copy if this is the last target. */
1210 this->forward_value_to_input(
1211 locked_node, input_state, value_to_forward, current_task);
1212 value_to_forward = {};
1213 }
1214 else {
1215 void *buffer = local_data.allocator->allocate(type);
1216 type.copy_construct(value_to_forward.get(), buffer);
1217 this->forward_value_to_input(locked_node, input_state, {type, buffer}, current_task);
1218 }
1219 });
1220 }
1221 if (value_to_forward.get() != nullptr) {
1222 value_to_forward.destruct();
1223 }
1224 }
1225
1226 void forward_value_to_input(LockedNode &locked_node,
1227 InputState &input_state,
1228 GMutablePointer value,
1229 CurrentTask &current_task)
1230 {
1231 NodeState &node_state = locked_node.node_state;
1232
1233 BLI_assert(input_state.value == nullptr);
1234 BLI_assert(!input_state.was_ready_for_execution);
1235 input_state.value = value.get();
1236
1237 if (input_state.usage == ValueUsage::Used) {
1238 node_state.missing_required_inputs -= 1;
1239 if (node_state.missing_required_inputs == 0 ||
1240 (locked_node.node.is_function() && static_cast<const FunctionNode &>(locked_node.node)
1241 .function()
1242 .allow_missing_requested_inputs()))
1243 {
1244 this->schedule_node(locked_node, current_task, false);
1245 }
1246 }
1247 }
1248
1249 bool use_multi_threading() const
1250 {
1251 return task_pool_.load() != nullptr;
1252 }
1253
1254 bool try_enable_multi_threading()
1255 {
1256#ifndef WITH_TBB
1257 /* The non-TBB task pool has the property that it immediately executes tasks under some
1258 * circumstances. This is not supported here because tasks might be scheduled while another
1259 * node is in the middle of being executed on the same thread. */
1260 return false;
1261#endif
1262 if (this->use_multi_threading()) {
1263 return true;
1264 }
1265#ifdef FN_LAZY_FUNCTION_DEBUG_THREADS
1266 /* Only the current main thread is allowed to enabled multi-threading, because the executor is
1267 * still in single-threaded mode. */
1268 if (current_main_thread_ != std::this_thread::get_id()) {
1270 }
1271#endif
1272 /* Check of the caller supports multi-threading. */
1273 if (!params_->try_enable_multi_threading()) {
1274 return false;
1275 }
1276 /* Avoid using multiple threads when only one thread can be used anyway. */
1277 if (BLI_system_thread_count() <= 1) {
1278 return false;
1279 }
1280 this->ensure_thread_locals();
1281 task_pool_.store(BLI_task_pool_create(this, TASK_PRIORITY_HIGH));
1282 return true;
1283 }
1284
1285 void ensure_thread_locals()
1286 {
1287#ifdef FN_LAZY_FUNCTION_DEBUG_THREADS
1288 if (current_main_thread_ != std::this_thread::get_id()) {
1290 }
1291#endif
1292 if (!thread_locals_) {
1293 thread_locals_ = std::make_unique<threading::EnumerableThreadSpecific<ThreadLocalStorage>>();
1294 }
1295 }
1296
1300 void push_all_scheduled_nodes_to_task_pool(CurrentTask &current_task)
1301 {
1302 BLI_assert(this->use_multi_threading());
1303 std::unique_ptr<ScheduledNodes> scheduled_nodes = std::make_unique<ScheduledNodes>();
1304 {
1305 std::lock_guard lock{current_task.mutex};
1306 if (current_task.scheduled_nodes.is_empty()) {
1307 return;
1308 }
1309 *scheduled_nodes = std::move(current_task.scheduled_nodes);
1310 current_task.has_scheduled_nodes.store(false, std::memory_order_relaxed);
1311 }
1312 this->push_to_task_pool(std::move(scheduled_nodes));
1313 }
1314
1315 void push_to_task_pool(std::unique_ptr<ScheduledNodes> scheduled_nodes)
1316 {
1317 /* All nodes are pushed as a single task in the pool. This avoids unnecessary threading
1318 * overhead when the nodes are fast to compute. */
1320 task_pool_.load(),
1321 [](TaskPool *pool, void *data) {
1322 GenericGraphExecutor &executor = *static_cast<GenericGraphExecutor *>(
1323 BLI_task_pool_user_data(pool));
1324 ScheduledNodes &scheduled_nodes = *static_cast<ScheduledNodes *>(data);
1325 CurrentTask new_current_task;
1326 new_current_task.scheduled_nodes = std::move(scheduled_nodes);
1327 new_current_task.has_scheduled_nodes.store(true, std::memory_order_relaxed);
1328 const LocalData local_data = executor.get_local_data();
1329 executor.run_task(new_current_task, local_data);
1330 },
1331 scheduled_nodes.release(),
1332 true,
1333 [](TaskPool * /*pool*/, void *data) { delete static_cast<ScheduledNodes *>(data); });
1334 }
1335
1336 LocalData get_local_data()
1337 {
1338 if (!this->use_multi_threading()) {
1339 return {&main_allocator_, context_->local_user_data};
1340 }
1341 ThreadLocalStorage &local_storage = thread_locals_->local();
1342 if (!local_storage.local_user_data.has_value()) {
1343 local_storage.local_user_data = context_->user_data->get_local(local_storage.allocator);
1344 }
1345 return {&local_storage.allocator, local_storage.local_user_data->get()};
1346 }
1347};
1348
1350 private:
1351 GenericGraphExecutor &executor_;
1352 const Node &node_;
1353 NodeState &node_state_;
1354 CurrentTask &current_task_;
1356 const GenericGraphExecutor::LocalData &caller_local_data_;
1357
1358 public:
1360 GenericGraphExecutor &executor,
1361 const Node &node,
1362 NodeState &node_state,
1363 CurrentTask &current_task,
1364 const GenericGraphExecutor::LocalData &local_data)
1365 : Params(fn, node_state.enabled_multi_threading),
1366 executor_(executor),
1367 node_(node),
1368 node_state_(node_state),
1369 current_task_(current_task),
1370 caller_local_data_(local_data)
1371 {
1372 }
1373
1374 private:
1375 GenericGraphExecutor::LocalData get_local_data()
1376 {
1377 if (!node_state_.enabled_multi_threading) {
1378 /* Can use the data from the thread-local data from the calling thread. */
1379 return caller_local_data_;
1380 }
1381 /* Need to retrieve the thread-local data for the current thread. */
1382 return executor_.get_local_data();
1383 }
1384
1385 void *try_get_input_data_ptr_impl(const int index) const override
1386 {
1387 const InputState &input_state = node_state_.inputs[index];
1388 if (input_state.was_ready_for_execution) {
1389 return input_state.value;
1390 }
1391 return nullptr;
1392 }
1393
1394 void *try_get_input_data_ptr_or_request_impl(const int index) override
1395 {
1396 const InputState &input_state = node_state_.inputs[index];
1397 if (input_state.was_ready_for_execution) {
1398 return input_state.value;
1399 }
1400 return executor_.set_input_required_during_execution(
1401 node_, node_state_, index, current_task_, this->get_local_data());
1402 }
1403
1404 void *get_output_data_ptr_impl(const int index) override
1405 {
1406 OutputState &output_state = node_state_.outputs[index];
1407 BLI_assert(!output_state.has_been_computed);
1408 if (output_state.value == nullptr) {
1409 LinearAllocator<> &allocator = *this->get_local_data().allocator;
1410 const CPPType &type = node_.output(index).type();
1411 output_state.value = allocator.allocate(type);
1412 }
1413 return output_state.value;
1414 }
1415
1416 void output_set_impl(const int index) override
1417 {
1418 OutputState &output_state = node_state_.outputs[index];
1419 BLI_assert(!output_state.has_been_computed);
1420 BLI_assert(output_state.value != nullptr);
1421 const OutputSocket &output_socket = node_.output(index);
1422 executor_.forward_value_to_linked_inputs(output_socket,
1423 {output_socket.type(), output_state.value},
1424 current_task_,
1425 this->get_local_data());
1426 output_state.value = nullptr;
1427 output_state.has_been_computed = true;
1428 }
1429
1430 bool output_was_set_impl(const int index) const override
1431 {
1432 const OutputState &output_state = node_state_.outputs[index];
1433 return output_state.has_been_computed;
1434 }
1435
1436 ValueUsage get_output_usage_impl(const int index) const override
1437 {
1438 const OutputState &output_state = node_state_.outputs[index];
1439 return output_state.usage_for_execution;
1440 }
1441
1442 void set_input_unused_impl(const int index) override
1443 {
1444 executor_.set_input_unused_during_execution(
1445 node_, node_state_, index, current_task_, this->get_local_data());
1446 }
1447
1448 bool try_enable_multi_threading_impl() override
1449 {
1450 const bool success = executor_.try_enable_multi_threading();
1451 if (success) {
1452 node_state_.enabled_multi_threading = true;
1453 }
1454 return success;
1455 }
1456};
1457
1463inline void GenericGraphExecutor::execute_node(const FunctionNode &node,
1464 NodeState &node_state,
1465 CurrentTask &current_task,
1466 const LocalData &local_data)
1467{
1468 const LazyFunction &fn = node.function();
1469 GraphExecutorLFParams node_params{fn, *this, node, node_state, current_task, local_data};
1470
1471 Context fn_context(node_state.storage, context_->user_data, local_data.local_user_data);
1472
1473 if (logging_enabled_state_.before_node_execute) {
1474 self_.logger_->log_before_node_execute(node, node_params, fn_context);
1475 }
1476
1477 /* This is run when the execution of the node calls `lazy_threading::send_hint` to indicate that
1478 * the execution will take a while. In this case, other tasks waiting on this thread should be
1479 * allowed to be picked up by another thread. */
1480 auto blocking_hint_fn = [&]() {
1481 if (!current_task.has_scheduled_nodes.load()) {
1482 return;
1483 }
1484 if (!this->try_enable_multi_threading()) {
1485 return;
1486 }
1487 this->push_all_scheduled_nodes_to_task_pool(current_task);
1488 };
1489
1490 lazy_threading::HintReceiver blocking_hint_receiver{blocking_hint_fn};
1491 if (self_.node_execute_wrapper_) {
1492 self_.node_execute_wrapper_->execute_node(node, node_params, fn_context);
1493 }
1494 else {
1495 fn.execute(node_params, fn_context);
1496 }
1497
1498 if (logging_enabled_state_.after_node_execute) {
1499 self_.logger_->log_after_node_execute(node, node_params, fn_context);
1500 }
1501}
1502
1503} // namespace blender::fn::lazy_function::generic_graph_executor
#define final(a, b, c)
Definition BLI_hash_c.hh:21
#define BLI_SCOPED_DEFER(function_to_defer)
volatile int lock
#define BLI_assert_unreachable()
#define BLI_assert(a)
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
void reinitialize(const int64_t new_size)
Definition BLI_array.hh:430
void * allocate(const int64_t size, const int64_t alignment)
void append(const T &value)
bool is_empty() const
const OutputSocket & output(int index) const
Params(const LazyFunction &fn, bool allow_multi_threading_initially)
GraphExecutorLFParams(const LazyFunction &fn, GenericGraphExecutor &executor, const Node &node, NodeState &node_state, CurrentTask &current_task, const GenericGraphExecutor::LocalData &local_data)
#define index(i)
static Local & get_local_data()
int context(const bContext *C, const char *member, bContextDataResult *result)
void parallel_for(const IndexRange range, const int64_t grain_size, const Function &function, const TaskSizeHints &size_hints=detail::TaskSizeHints_Static(1))
Definition BLI_task.hh:69
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
__int64 int64_t
Definition BKE_text.h:90
void BLI_task_pool_work_and_wait(TaskPool *pool)
Definition task_pool.cc:455
int BLI_system_thread_count()
Definition threads.cc:258
unsigned char uint8_t
Definition BKE_text.h:79
void BLI_task_pool_free(TaskPool *pool)
Definition task_pool.cc:441
TaskPool * BLI_task_pool_create(void *userdata, eTaskPriority priority)
Definition task_pool.cc:404
std::mutex Mutex
Definition BLI_mutex.hh:51
void BLI_task_pool_push(TaskPool *pool, TaskRunFunction run, void *taskdata, bool free_taskdata, TaskFreeFunction freedata)
Definition task_pool.cc:446