From BlenderWiki

Threaded Dependency Graph: Thread Safety

First step to make it possible to have multiple objects updating from separate threads at the same time is to make sure all code underneath this is thread-safe. This means no global or static variables shall be used, no write shall happen to the data which might be used by other threads and so on.

Code thread-safety

For a long time Blender had lots of non-threadsafe code, which used bunch of static and global variables.

Metaballs

Metaballs are well-known to have the bunch of static and global variables. This includes both metaball tessellation (when metaball group is already known) and metaball group detection (which implies gathering all the metaballs which belongs to the same group and finding a motherball for this group).

Perhaps ultimate long-term solution would be to re-write the whole metaballs module supporting much more features, but that's obviously out of the scope of current project.

Tessellation of metaballs already had a PROCESS structure where most of run-time data was stored. So the easiest way to make tessellation fully thread-safe is to just move all static variables into this structure and pass this structure to functions where static variables used to be used.

This is rather just a technical change, nothing terribly exciting so let's not stop here in details.

Detecting metaballs group and finding motherball uses BKE_scene_base_iter_next function, which have couple of static variables which are used to store current base, iteration state and recursion detection.

Current base and iteration state are now warped into SceneBaseIter structure:

typedef struct SceneBaseIter {
        struct ListBase *duplilist;
        struct DupliObject *dupob;
        int fase;  /* Current phase of iteration. Could be  */
} SceneBaseIter;

Structure description:

• duplilist contains list of dupli-objects when traversing object with dupligroup enabled.
• dupob Current object from duplilist which was passed to iterator callee.
• fase Current phase of iteration. Could be:
  • F_START - just started the new iteration
  • F_SCENE - iterating over scene's bases
  • F_DUPLI - iterating objects form dupli-list

Recursion detection was needed because dupli-list creating used to update all the objects from the group. It isn't needed for motherball detection because the whole group would be re-tessellated after traversal, so we might skip update when detecting motherball.

This was pretty much simple change, just use object_duplilist_ex which accepts additional argument which indicates whether objects need to be updated before they go to the duplilist.

As an additional bonus this change to BKE_scene_base_iter_next allows to use metaballs in group which is being dupli-grouped. But this requires some changes to the depsgraph system to make update happening properly.

Curves

Curves code doesn't use static variables, but it's still not safe for threading. This is mainly because pre-tesselation modifiers affects on actual Curve's spline. This means objects which shares the same Curve datablock could not be updated in parallel, otherwise one object's modifier stack would affect on other object's update.

There're also some data-structure issues which makes curves not safe for threading, but they're described in Data thread-safety section.

The solution for pre-tessellation modifiers is pretty much obvious: make a copy of splines on which modifiers are applying. This way modifier stack might do whatever it wants to with the splines without being harmful for any other process happening in Blender.

Making copy of splines might sound as increased memory consumption, but in fact this change doesn't change memory usage significantly:

• List of splines is couple order of magnitudes smaller than display list structure
• Old code used to store an array with original non-modified coordinates to restore curve datablock after modifiers evaluation. This array is not needed anymore.

Other areas

Modifier stack

Modifier stack isn't safe for threading because of virtual modifier list functions which are using static variables.

This was solved by wrapping all the static variables from modifiers_getVirtualModifierList into a VirtualModifierData structure:

typedef struct VirtualModifierData {
        ArmatureModifierData amd;
        CurveModifierData cmd;
        LatticeModifierData lmd;
        ShapeKeyModifierData smd;
} VirtualModifierData;

External user of this function shouldn't actually worry about the structure content and actually should never do direct access to it. Just everyone who're using modifiers_getVirtualModifierList now is responsible to have VirtualModifierData structure allocated (preferably in the stack because of speed issues) and pass it to VirtualModifierData. And then just use result of the function in usual way.

Another aspect of modifier stack not being safe for threading is that boolean and array modifiers are calling mesh_get_derived_final which might invoke derived mesh re-evaluation for that object. This is very much likely to run into conflict with derives mesh evaluation happening for the same object from separate thread.

For now it's solved by not calling derived mesh evaluation, just using the derived mesh from object and rely dependency graph takes care of making sure it's a correct assumption.

Fonts

Fonts aren't safe for threading as well, because they would put font into a global storage after it was loaded.

There was no other way for not than just add mutex lock to vfont_get_data function.

Draw Objects

Draw objects are pretending to be safe for threading by not doing calls to OpenGL if functions are not called from the main thread. But buffer pool management wasn't safe still - they're allocating/freeing and copying data from the global arrays.

Again, the only solution here was to have some thread locks. Straightforward change, nothing to be look into in details.

Data thread-safety

This section is currently about curves only, other areas with bad structure design are not found yet.

The issue with Curve datablock is caused by storing display list, bevel list and path in the Curve datablock itself. It wouldn't be an issue if this things didn't depend on modifier stack. Let's look into all this three guys in more details.

Bevel list is used for bevel calculation. And this thing might be used by other objects' evaluation as well (i.e. when one curve uses another one as bevel object). Historically it happened so this list needs to be affected by pre-tessellation modifiers. Different objects might have different modifiers so bevel list can not be stored in the Curve datblock.

The same story goes with the path - it's affected by pre-tessellation modifiers, it also shouldn't be stored in Curve datablock.

The solution for this two issues was to introduce a CurveCache structure which is stored in Object and looks like

typedef struct CurveCache {
        ListBase disp;
        ListBase bev;
        struct Path *path;
} CurveCache;

• disp is a final display list for the curve object. Before this structure was added, object had Object->disp field which was just simply wrapped into CurveCache structure.
• bev is a bevel list for given object
• path is a path for given object

As an additional, this change makes path and bevel behave more predictable when some objects shares the same curve datablock and one (or more) of this objects are used for bevel or path. Before this, path/bevel from the latest updated object would have been used, which is not in the artists control.

The story about display list which is stored in Curve datablock is a bit more tricky. This display list is only used to calculate curve's bounding box. This bounding box is also used for texture space calculation.

Currently, Blender uses display list created from splines affected by pre-tessellation modifiers to calculate bounding box. And again different objects might have different modifiers and calculating curve datablock's bounding box from it is not reliable at all.

We needed some reliable and predictable way to calculate curve's bounding box. And there're two ways to do it:

First idea which was expected to have less compatibility issues was to create a display list which is not affected by the modifiers and use it for bounding box.

This ended up being a bad idea because:

• This is not so much fast to create full display list
• It somehow need to deal with non-modified bevel list from objects which might be used for bevel

Trying to be smart here ended up with lots of crappy code, so final decision was to create bounding box based on control point's bounding box, which does also include curve radius into account.

This approach works really fast, predictable for artists. However it's main downside is not being backwards compatible.

This was worked around by adding an "Match texture Space" operator (see picture at the right) which will match curve's texture space to deformed display list.

For now it's the least evil, but some further tweaks are possible.

Summary

All this changes were crucial to be able to update multiple objects from separate threads, but they're also solved quite reasonable amount of issues caused by viewport render.

The most clear example are metaballs, which were crashing a lot in Blender Internal's rendered viewport.

Most of this changes were already merged to trunk.