Efficient and secure data structure synchronization

摘要

One embodiment of a computer-implemented data structure synchronization mechanism comprises an interface for accessing a data structure and storing ownership data in a shared memory location. The method further comprises denying write operations if the thread attempting the write operation is not designated as the owner thread by said ownership data. The method further comprises denying requests to modify the ownership data if the thread making the request is not designated as the owner thread by said ownership data. The method further comprises effecting a write fence in the context of the thread making the request to modify ownership data prior to modifying the ownership data. Other embodiments are described.

主权项

1. A computer-implemented method for detecting and preventing potentially harmful concurrent modification of a data structure accessed by multiple threads, comprising:
(a) providing a memory-safe execution environment, said memory-safe execution environment being generated by a type-safe virtual machine, said type-safe virtual machine having a compiler optimization, said compiler optimization being capable of pulling code out of loops in one or more cases; (b) configuring said type-safe virtual machine with a cacheable owner thread identifier variable, said cacheable owner thread identifier variable being logically associated with said data structure; (c) configuring said type-safe virtual machine with an interface, said interface comprising a write function capable of effecting a write operation on said data structure, said write function being formulated to require a write access check before effecting said write operation, said write access check being formulated to determine a first thread identifier, said first thread identifier belonging to a first thread, said first thread having invoked said write function, said write access check being formulated to allow said write operation only if a first cacheable load of said cacheable owner thread identifier variable designates said first thread as currently owning said data structure, said write function being formulated to permit said compiler optimization to pull said write access check out of loops in one or more cases; (d) a first storing of a second thread identifier to said cacheable owner thread identifier variable, said second thread identifier belonging to a second thread, said second thread preparing said data structure for use; (e) a first processing of a request to transfer exclusive access to said data structure, said request supplying a supplied thread identifier, said request being made by a third thread, said first processing being performed by said third thread, said first processing including a second storing of said supplied thread identifier in said cacheable owner thread identifier variable, said second storing being performed only if said cacheable owner thread identifier variable designates said third thread as currently owning said data structure, said first processing including issuing a write fence prior to said second storing; (f) a second processing of a first query of whether reads from said data structure will be repeatable, said first query being made by a fourth thread, said second processing being performed by said fourth thread, said second processing including issuing a first read fence, said second processing including reporting a first positive result only if said cacheable owner thread identifier variable designates said fourth thread as currently owning said data structure or equals a frozen value, said frozen value being distinct from any values that indicate operable threads.