Concurrent mutation of isolated object graphs

Patent metadata

Field	Value
Publication number	US-9569282-B2
Application number	US-42987409-A
Country	US
Kind code	B2
Filing date	Apr 24, 2009
Priority date	Apr 24, 2009
Publication date	Feb 14, 2017
Grant date	Feb 14, 2017

Abstract

Fine-grained parallelism within isolated object graphs is used to provide safe concurrent operations within the isolated object graphs. One example provides an abstraction labeled IsolatedObjectGraph that encapsulates at least one object graph, but often two or more object graphs, rooted by an instance of a type member. By encapsulating the object graph, no references from outside of the object graph are allowed to objects inside of the object graph. Also, the encapsulated object graph does not contain references to objects outside of the graphs. The isolated object graphs provide for safe data parallel operations, including safe data parallel mutations such as for each loops. In an example, the ability to isolate the object graph is provided through type permissions.

First claim

What is claimed is:

1. A method in an imperative framework, comprising:
encapsulating an object graph that is rooted by an instance of a data type with an isolation modifier of a plurality of isolation modifiers to control access to members such that the object graph does not have references to objects outside of the object graph and references outside of the object graph do not have references to objects within the object graph including specifying an isolation modifier notation representative of the isolation modifier with a type name in a formal parameter declaration that can be used in a universal syntax;
each of the plurality of isolation modifiers defining a different access permission to restrict operations on the object to which a reference points including:

an immutable permission for accessing an immutable field in which an immutable reference points at objects shared between concurrent threads where state that does not change is accessed through the object;
a read permission in which a read reference points at objects shared between concurrent threads for which there are no concurrent writes and the read reference implies immutable access and allows reads of mutable fields; and
a write permission in which a write reference points to an object that is one of not shared or shared but includes an exclusive access in which a write to the reference can be done with safe concurrency;
statically proving the object graph to be isolated;
running, reading, and/or writing objects within the object graph; and
statically proving the object graph continues to be isolated after running, reading, and/or writing the objects such that mutations of state within an isolated region of the object graph are not made available outside of the isolated region to enable a safe data parallel operation within the object graph.

2. The method of claim 1 and further comprising:
permitting a first state to be read and extracted from a first isolated region;
providing a function to create a second state to replace the first state in the isolated region;
replacing a third state from a second isolated region with the second state; and
returning an immutable reference from the first isolated region.

3. The method of claim 2 and further comprising accepting a factory function to create and return an object root wherein accepting the factory function includes invoking a delegate and storing a result of the factory function in a selected field.

4. The method of claim 3 wherein the delegate is an isolated delegate that binds to isolated methods that execute in the first and second isolated regions.

5. The method of claim 4 wherein the delegate is marked with an immutable permission and binds to static methods and instance methods that have immutable access to the region.

6. The method of claim 2 wherein the first and third states are not read directly from the first and second isolated regions.

7. The method of claim 2 wherein the permitting, providing, and replacing, do not keep a record of the first state.

8. The method of claim 1 and further comprising another isolated object graph, where in the object graph and the another isolated object graph support constructs to for safe parallel operations of data.

9. The method of claim 1 wherein the object graph does not contain references to objects outside of the object graph, and objects outside of the object graph do not contain references within the object graph.

10. The method of claim 1 and further including using type permissions to encapsulate the object graph.

11. A computer readable storage medium, which does not include a transitory propagating signals to store computer executable instructions to control a computing device to:
define a plurality of type modifiers to control access to type members of a data type through references pointing at an object such that each type modifier includes a type modifier notation, the plurality of type modifiers comprising:
an immutable permission for accessing an immutable field in which an immutable reference points at objects shared between concurrent threads where state that does not change is accessed through the object;
a read permission in which a read reference points at objects shared between concurrent threads for which there are no concurrent writes and the read reference implies immutable access and allows reads of mutable fields; and
a write permission in which a write reference points to an object that is one of not shared or shared but includes an exclusive access in which a write to the reference can be done with safe concurrency;
associate one of the plurality of type modifiers as a type modifier notation with a type name for all occurrence of the type name including specify an isolation modifier with the type name in a formal parameter declaration that can be used in a universal syntax, wherein each of the plurality of type modifiers defines a different access permission to restrict operations on the object to which the reference points;
encapsulate an object graph rooted by an instance of the type members by specifying the immutable modifier to control access to members such that the object graph does not contain references to objects outside of the object graph and references outside of the object graph do not have references to objects within the object graph; and
enable a safe data parallel operation within the object graph such that mutations of state within an isolated region of the object graph are not made available outside of the isolated region.

12. The computer readable storage medium of claim 11 wherein the encapsulate the object graph includes create a fully generic type permission.

13. The computer readable storage medium of claim 12 wherein the fully generic type permissions includes create an immutable graph and at least one of a read-only graph and a write-read graph.

14. The computer readable storage medium of claim 11 wherein the method is performed in a managed environment including combinators.

15. The computer readable storage medium of claim 14 wherein the combinators include: Enter, Extract, Replace, ReplaceFrom, and Compute.

16. The computer readable storage medium of claim 11 wherein the enable safe data parallel operation within the object graph includes enable safe data parallel mutation of a plurality of object graphs.

17. The computer readable storage medium of claim 16 where the safe data parallel operation includes parallel for each loops.

18. The computer readable storage medium of claim 16 including wherein the plurality of objects graphs are included in separate threads, and the safe data parallel operation concurrently enters the object graphs isolated regions with at least one of static and dynamic partitioning.

19. The computer readable storage medium of claim 18 including computer readable code that is statically verified in the managed environment, the plurality of object graphs is statically verified, and partitioning does not assign duplicate elements to separate dynamic threads.

20. A system comprising:
a memory to store a set of instructions;
and a processor to execute the set of instructions to:

define at least three type modifiers to control access to type members for data types through references pointing at an object;
associate one of the plurality of type modifiers with a type name for a respective data type for all occurrence of the type name including specifying an isolation modifier notation with the type name in a formal parameter declara

Assignees

• Duffy John J
• Gustafsson Niklas
• Morrison Vance
• Microsoft Technology Licensing Llc

Inventors

• Duffy John J
• Gustafsson Niklas
• Morrison Vance

Classifications

• G06F21/78

  to assure secure storage of data (address-based protection against unauthorised use of memory G06F12/14; record carriers for use with machines and with at least a part designed to carry digital markings G06K19/00) · CPC title

• G06F9/526 Primary

  Mutual exclusion algorithms · CPC title

• G06F9/468

  Specific access rights for resources, e.g. using capability register · CPC title