Electronic garbage collection moves objects within memory to consolidate the objects thereby reducing access time and improving memory performance. Transactions occurring in an atomic transactional memory appear to occur instantaneously—such that the transaction completes in its entirety or is aborted. A garbage collection circuit attempts to move a memory object from a first memory location to a second memory location using a transactional fast-path move operation. If the transactional fast-path move operation is unsuccessful after a number of attempts, the garbage collection circuit attempts to move the object using a non-transactional slow-path move.

TECHNICAL FIELD

The present disclosure relates to garbage collection in transactional memory systems.

BACKGROUND

Garbage collection is an important feature of modern programming languages that removes the burden of manual memory management from the programmer. Such electronic garbage collection may be classified as either concurrent or stop-the-world. In a stop-the-world garbage collection system, to reclaim memory, all threads are stopped while the garbage collector thread walks all live objects. The process of walking all live threads can take tens of milliseconds, rendering stop-the-world type garbage collection unsuitable for applications having real-time requirements such as video conferencing or telephony. In contrast, concurrent garbage collectors do the work of reclaiming free memory while the other threads in the system continue working. Such concurrent garbage collection systems have reduced “pause” times suitable for use with real-time applications.

Garbage collection systems are further classified as moving or non-moving. Non-moving garbage collection systems do not move objects, resulting in memory fragmentation. Such fragmentation leads to increased allocation overhead, poorer cache locality, and impedes the allocation of large objects in the memory.

A concurrent and moving garbage collection system may create “lost update” issues. With a concurrent and moving garbage collection system, an application thread (mutator) may attempt to write to an object that the garbage collection system is in the process of moving to a new location. If the garbage collection system copies an object's field to a new location and an application thread then attempts to write to the field prior to learning that the object has been moved, the application thread writes to the old location of the object. The garbage collection system will not know the application thread has written to the moved object's old location and will not know to update the new location of the moved object to reflect the update. In such circumstances the update provided to the old location will be “lost” and may result in an error or incorrect execution of the application.

Solutions to the “lost update” problem have been implemented non-transactionally, using software transactional memory, and using hardware transactional memory. The problem with the non-transactional and software transactional memory solutions is that such solutions are inefficient and place a high level of overhead on an application.

DETAILED DESCRIPTION

A concurrent, moving garbage collector can use hardware transactional memory to move objects. By using such a garbage collection system, application threads remain efficient and need not use transactions to perform object updates. A concurrent, moving, garbage collector can take advantage of the strong atomicity property of the hardware transactional memory system to detect contention between an application thread and a garbage collection thread to prevent the lost-update issue by having the garbage collection thread repeat the contended transaction. The high efficiency and low overhead of such a solution offers a marked improvement over non-transactional and software transactional memory system solutions.

Concurrent, moving, garbage collector systems frequently operate in multiple phases. For example, a phase in which the garbage collector determines reachable objects; a phase that moves or compacts the reachable objects; and a phase that ensures all application threads begin working with the new locations of moved objects. Threads that perform the work of the concurrent garbage collection system are referred to as “GC threads.” Threads that perform the work of the application are referred to as “mutators.” In the systems and methods disclosed herein the GC threads and mutators work synergistically to collaborate and safely move objects. Each memory object includes a “forwarding” field that is used to indicate the current state of the object and provides a new location if the object has been moved. The systems and methods disclosed herein take advantage of the strong atomicity of hardware transactional memory and also accommodate that there is no guarantee of transaction success even after repeated tries (called “eventual success”). GC threads use transactions while mutators do not.

To move an object, a GC thread first attempts a fast-path move in which the GC thread first touches the object to prevent transaction aborting page faults. The GC thread then starts the transaction and determines where to move the object. The GC thread writes the new location to the forwarding field logically associated with the first memory location and ends the transaction. If this fast-path transaction aborts for any reason (e.g., an attempted mutator write to the object), it is retried a defined number of times. If a mutator writes to the object during the attempted transactional fast-path move, strong atomicity causes the garbage collection operation to abort. If the object is updated prior to the transactional fast-path reattempt, the reattempt will copy the updated object that the mutator created. Since eventual success is not guaranteed, the systems and methods disclosed herein also makes use of a default, non-transactional, “fall-back” slow path.

To execute the non-transactional slow path, the GC thread writes data representative of a first logic state (e.g., FORWARDING) to the forwarding field logically associated with the first memory location where the object is stored and performs a handshake with each mutator to confirm that the mutator is able to see the first logic state. If a mutator attempts to write to an object for which the logically associated forwarding field indicates the first logic state, the mutator atomically writes data representative of a second logic state (e.g., WRITTEN) to the forwarding field logically associated with the first memory location. The atomic nature of the transactional memory causes the non-transactional slow-path move to fail upon when the mutator updates the object in the first memory location. Upon failure of the non-transactional slow-path move, the GC thread will retry the non-transactional slow-path move and the now updated object in the first memory location is moved to the second memory location. In such a manner, the lost-update issue is avoided in the circumstance where the mutator writes to the object while the GC thread is attempting a slow-path move. If a mutator does not attempt to update the object in first memory location, the GC thread simply determines a second memory location to move the object and copies the object to the second memory location. The GC thread then atomically sets the forwarding field logically associated with the second memory location to a third logic state (e.g., FORWARDED) that may include data representative of the second memory location. Any future attempt by the mutator to write to the first memory location are redirected to the second memory location.

During the move phase of the GC thread, the mutators may execute a second machine-readable instruction set that includes a GC collaboration code when reading a pointer or writing to an object. The second machine-executable instruction set may, at times, include one or more collaboration codes that are referred to as a READ barrier and a WRITE barrier. The portion of the second machine-readable instruction set that includes the READ barrier collaboration code reads the forwarding field logically associated with an object to determine whether the object has been moved by a GC thread to a new location. If the forwarding field indicates the GC thread has moved the logically associated object, the mutator uses the object in the new location.

The portion of the second machine-readable instruction set that includes the WRITE barrier collaboration code assists in protecting against the lost update issue. The WRITE barrier looks to the forwarding field logically associated with an object to determine whether the forwarding field logically associated with the first memory location is in the first logic state. If the forwarding field logically associated with the first memory location is in the first logic state, the mutator changes the contents of the forwarding field to the second logic state. These steps prevent the lost-update issue during a slow-path move. If the forwarding field logically associated with the first memory location is not in the first logic state, the WRITE barrier collaboration code determines whether the forwarding field logically associated with the first memory location is in the third logic state. If the forwarding field logically associated with the first memory location is in the third logic state, the mutator begins using the object in the new location by applying the update to the object in the new location.

Since the mutator write and the GC thread move operations are not performed transactionally, the potential exists for a “race” between the mutator and the GC thread. Such a race has three potential outcomes: the mutator writes to the object prior to the GC thread moving the object; the mutator writes to the object in the old location while the GC thread moves the object to the new location; or the mutator writes to the object in the old location after the GC thread has moved the object to the new location. If the mutator completes the write operation prior to the GC thread moving the updated object, the GC thread moves the updated object to the new location and no additional action is needed. If the mutator attempts to update the object in the old location while the GC thread is moving the object to the new location, the strong atomicity of the hardware transactional memory will cause the GC move transaction to abort and on a retry by the GC thread, the GC copies the modified object in the old location to the new location.

If the mutator writes to the object in the old location after the GC has completed a move to the new location, the WRITE barrier collaboration code determines whether the forwarding field logically associated with the first memory location contains data representative of the third logic state. If the WRITE barrier collaboration code did not previously detect the forwarding field logically associated with the first memory location included data representative of the third logic state, the WRITE barrier collaboration code determines whether the forwarding field logically associated with the first memory location includes data representative of the third logic state. If the mutator detects the forwarding field logically associated with the first memory location includes data representative of the third logic state, the mutator updates itself to use the new location of the object and performs the write operation on the object in the new location.

The lost update issue is resolved in three ways. First, on the transactional fast-path, the lost update issue is avoided by the strong atomicity induced aborts of the hardware transactional memory that causes the GC thread to retry the transactional fast-path. Second, if the mutator update and the GC transaction occur contemporaneously, the lost update problem is avoided by repeatedly checking the forwarding field logically associated with the first memory location and a repeated update to the new location of the object. Finally, the lost update problem is solved on the slow path by repeatedly attempting to update and move the updated object to the new location selected by the GC thread.

FIG. 1illustrates an example concurrent, moving garbage collection system100that assists in the prevention of lost updates, in accordance with at least one embodiment of the present disclosure. The system100includes one or more applications102attempting to update a number of objects106, each stored in a respective location110A-110Z (collectively, “locations110”) in a transactional memory156. In at least some implementations, the transactional memory156may be realized at least in part as hardware transactional memory156. In embodiments, the transactional memory156demonstrates strong atomicity and provides no guarantee of ultimate success of a particular transaction even upon repeated retries (“eventual success”). A strongly atomic memory protects transactions from interference from non-transactional code. Transactional Synchronization Extensions (TSX) developed by INTEL® Corp. (Santa Clara, Calif.) is an extension to the x86 instruction set that provides an example instruction set supporting transactional memory that demonstrates strong atomicity and no guarantee of eventual success of the transaction.

The application(s)102operate on the locations110via number of mutator threads104A-104C (collectively “mutators104”) that may operate on a non-transactional basis to alter or update at least some of the objects106stored or otherwise retained in the transactional memory156. Such object updates may be caused by user interaction with a device such as a personal computer, a laptop computer, a netbook computer, a portable computer, a wearable computer, a smartphone, or handheld computer (collectively, “computing systems”) that includes transactional memory156. Such object updates may be autonomously initiated by one or more applications executed by the computing system, for example by an operating system executing on the computing system.

The concurrent, moving garbage collection system100also includes one or more circuits152executing one or more machine-readable instruction sets stored in one or more storage devices154. In embodiments, the one or more machine readable instruction sets causes the one or more circuits152to provide a specific machine in the form of a garbage collection circuit152. The garbage collection circuit152causes one or more garbage collection (“GC”) threads120A-120C (collectively “GC threads120”) to move and copy objects from a first memory location to a second memory location to compact or consolidate stored objects and to free larger blocks of memory locations that are able to serially store larger object blocks and, in so doing, reduce object fragmentation and also improve data access times in the memory156.

In embodiments, GC threads120are generally transactional in nature while mutators104are generally non-transactional in nature. A transaction, such as those performed by the GC threads120may be considered a sequence of operations such as loads and stores that are performed on an all-or-nothing basis, i.e., the transaction commits and atomically completes the sequence of operations or aborts the sequence of operations in their entirety. The strong atomicity of the transactional memory156may also require that the non-transactional accesses of the mutators104be serialized with respect to the transactional accesses of the GC threads120.

Each object106is stored in a respective location110within the transactional memory156. During execution, the application(s)102may modify the objects stored in the transactional memory156. Contemporaneous with the execution of the application(s)102, the garbage collection circuit152may cause garbage collection threads120to move and copy the objects in the transactional memory156to improve one or more operating characteristics, such as access time, of the transactional memory156.

Each of the objects stored in the transactional memory156includes a respective forwarding field114A-114Z (collectively, “forwarding field114”). The forwarding field114may store or otherwise retain information to the mutators104on the status of the object106logically associated with a respective forwarding field114. For example, the forwarding field114A logically associated with a first transactional memory location110A that stores an object106A, may store or retain an address corresponding to a second transactional memory location110B to which a GC thread120has moved the object106A. The timing of GC thread120object moves and mutator104object writes thus impacts the operational efficiency of the transactional memory156.

Transactions by the GC threads120are attempted a number of times using a transactional fast-path. As a fallback, the GC threads120attempt a transactional slow-path if the transactional fast path is aborted each of the number of times. The GC threads120are thus able to perform fast-path transactions whenever possible, but have the added security of a slow-path transaction to complete the transaction after the fast-path transaction is aborted a number of times. Such fast-path aborts may be caused for any reason, including a mutator104attempting to write to or update the object106A in the original memory location110A while the GC thread is moving the object106A from the original memory location110A to a destination memory location110X.

Various transactional scenarios involving the timing between a mutator104operation and a GC thread120operation are depicted inFIG. 1. In the first transaction, application102causes mutator104A to write a new object106A to a first memory location110A at a time T=1. GC thread120A moves the new object106A in the first memory location110A to a second memory location110X at a subsequent time T=2. After moving the new object106A to the second memory location110X, the GC thread120A may write an address corresponding to the second memory location110X in forwarding field114A which is logically associated with first memory location110A. On subsequent operations involving new object106A, the mutator104A will read the pointer (i.e., the address corresponding to the second memory location110X) in the forwarding field114A and instead of writing to the new object106A stored in the first memory location110A, will instead write to the new object106A stored in the second memory location110X.

In a second transaction, application102causes mutator104B to write updated object106B′ to a first memory location110B that previously held object106B at T=3. Contemporaneous with mutator102B writing the updated object106B′ to first memory location110B (i.e., at T=3), GC thread120B moves the object in the first memory location110B to a second memory location110Y. A conflict between the mutator104B and the GC thread120B may occur depending of the relative timing between mutator104B writing the updated object106B′ and GC thread120B moving the object stored in the first memory location110B. In some instances, the GC thread120B may perform the transaction subsequent to mutator104B writing the updated object106B′ to the first memory location110B. In such instances, the transaction executes normally and the updated object106B′ is stored in the second memory location110Y at the conclusion of the transaction.

In some instances, the mutator104B may attempt to write an updated object106B′ to the first memory location while the GC thread120B performs the transaction. In such instances, the conflict between the mutator104B and the GC thread120B causes the GC thread120B to abort and reattempt the transaction. Upon reattempting the transaction, the mutator104B may have completed writing the updated object106B′ in the first memory location110B. In such instances, on the transaction reattempt the GC thread120B moves the updated object106B′ to the second memory location110Y.

In some instances, the mutator104B may attempt to update object106B in the first memory location110B after the GC thread120B has moved the object106B to the second memory location110Y. In such instances, as part of the transactional fast-path move, the GC thread102B writes data representative of an address of the second memory location110Y in the forwarding field114B logically associated with the first memory location110B. Thus, the mutator104B observes the address of the second memory location110Y and will then update the object in the second memory location110Y. In such instances, the updated object106B′ is therefore not lost.

In a third transaction, application102causes mutator104C to write updated object106C′ to a first memory location110C at T=5 that is subsequent to the time at T=4 when the GC thread120C moved the object106C to the second memory location110Z. In such instances, the GC thread120C updates the information in the forwarding field114C logically associated with the first memory location110C to reflect the address of the second memory location110Z where the GC thread120C moved the object106C. The mutator104C reads the pointer information in the forwarding field114C logically associated with the first memory location110C and, at T=6 writes the updated object106C′ to the second memory location110Z.

The garbage collection circuit152includes any number or combination of systems and devices capable of providing GC threads120capable of collaboration with one or more mutators104generated by application(s)102. At times, some or all of the one or more mutators104may execute a second machine-readable instruction set that may include collaboration code impacting mutator functionality during a read operation (e.g., a READ barrier collaboration) and impacting mutator functionality during a write operation (e.g., a WRITE barrier collaboration). Such collaboration code is described in detail below with regard toFIGS. 3 and 5-7.

In at least some implementations, the garbage collection circuit152may be represented by processor executing at least a first machine-readable instruction set retrieved from a communicably coupled storage device154. In such instances, the first machine-readable instruction set retrieved from the storage device154by the processor transform the processor to a particular and specialized garbage collection circuit152. Such a transformation improves the functionality and usefulness of the circuit by providing garbage collection capabilities absent from the circuit prior to executing the first machine-readable instruction set. In embodiments, the first machine-readable instruction set executed by the circuit creates a physical configuration of components within the circuit to form or otherwise provide the specialized garbage collection circuit152and cause the garbage collection circuit152to function as described herein.

The storage device154includes any number or combination of systems and devices capable of storing or otherwise retaining information, for example in the form of machine-readable instruction sets that when executed by a circuit, cause the processor to provide the garbage collection circuit152.

FIG. 2depicts an illustrative system200capable of executing application(s)102and in which a garbage collection circuit152can be used to improve system speed and efficiency by consolidating objects within memory using transactional fast-path and fallback slow-path moves in collaboration with mutators104provided by the application(s)102, in accordance with at least one embodiment of the present disclosure.

The system200may include one or more circuits212, that transform into one or more particular machines, such as the garbage collection circuit152described inFIG. 1, when executing machine-readable instruction sets retrieved from the storage device154. The system200also includes a system memory214and a system bus216that couples various system components including the system memory214to the circuit212. In embodiments, the circuit212may include any number or combination of processing units, such as one or more single- or multi-core microprocessors, one or more controllers, one or more digital signal processors, one or more application-specific integrated circuits (ASICs), one or more systems on a chip (SoCs), one or more reduced instruction set computers (RISCs); one or more field programmable gate arrays (FPGAs), etc. The system bus216can employ any known bus structures or architectures, including a memory bus with memory controller, a peripheral bus, and/or a local bus. The system memory214includes read-only memory (“ROM”)218and random access memory (“RAM”)220. In at least some implementations, the RAM220may include some or all of the transactional memory156. A basic input/output system (“BIOS”)222, which can form part of the ROM218, contains basic routines that facilitate system operations, such as I/O handling.

The system200may include one or more disk storage devices224, one or more optical storage devices228, one or more removable storage devices230, one or more atomic or quantum storage devices232, or combinations thereof. The one or more disk storage devices224, one or more optical storage devices228, one or more removable storage devices230, one or more atomic or quantum storage devices232may communicate with the circuit212via the system bus216. The one or more disk storage devices224, one or more optical storage devices228, one or more removable storage devices230, one or more atomic or quantum storage devices232may include interfaces or controllers (not shown) coupled between such drives and the system bus216, as is known by those skilled in the relevant art. The storage devices224,228,230, and232provide nonvolatile storage of computer-readable instructions, data structures, program modules and other data generated, created, and/or used by the system200.

Machine-readable Instruction sets can be stored in the system memory214. Such machine-readable instruction sets may include, but are not limited to, an operating system236, one or more application programs238, housekeeping programs240and program data242. In at least some implementations, the circuit212can load machine-readable instruction sets from the storage device154into system memory214for execution. In implementations, one or more machine-readable instruction sets that transform all or a portion of the circuit212into the garbage collection system152may be retained in whole or in part into the system memory214. Program data including one or more applications102generating one or more mutators104may be stored in whole or in part in a cache244communicably coupled to the circuit212, in system memory214, or any combination thereof. Application programs238may include, but are not limited to one or more sets of collaboration code executed by the mutator application. The collaboration code facilitates the collaboration between the mutators104and the GC threads120such that in combination with the atomic properties of hardware transactional memory156, lost updates are reduced in frequency of occurrence.

While shown inFIG. 2as being stored in the system memory214, the operating system236, application programs238, other programs/modules240, program data242and browser244can be stored in whole or in part on the one or more disk storage devices224, the one or more optical storage devices228, the one or more removable storage devices230, the one or more atomic or quantum storage devices232or combinations thereof.

An operator may provide commands and information to the system200using one or more physical input devices250. Example physical input devices may include, but are not limited to, one or more keyboards251, one or more touchscreen devices252, one or more audio devices253, or combinations thereof. The physical input devices250communicably couple and provide input to the circuit212via one or more hardware input/output (I/O) interfaces. Example hardware I/O interfaces can include, but are not limited to, one or more serial interfaces, one or more parallel interfaces, one or more universal serial bus (USB) interfaces, one or more THUNDERBOLT® interfaces, one or more wireless interfaces (e.g., BLUETOOTH®, near field communication, or any similar current or future developed wireless communication technology).

An operator may receive or otherwise perceive system output via one or more physical output devices254. Example physical output devices254may include, but are not limited to, one or more visual output devices255, one or more tactile output devices256, one or more audio output devices257, or any combination thereof. The physical output devices254communicably couple and output from the circuit212via one or more hardware input/output (I/O) interfaces. Example hardware I/O interfaces can include, but are not limited to, one or more serial interfaces, one or more parallel interfaces, one or more universal serial bus (USB) interfaces, one or more THUNDERBOLT® interfaces, one or more wireless interfaces (e.g., BLUETOOTH®, near field communication, or any similar current or future developed wireless communication technology). One or more modems or similar communications devices may be communicably coupled to the I/O interface.

The system200can, at times, operate in a networked computing environment using logical connections to one or more remote computers and/or devices. Such networking may be tethered or wireless and may employ any number, type or combination of wired and/or wireless network architecture, for instance wired and wireless enterprise-wide computer networks, intranets, extranets, and/or the Internet. Other embodiments may include other types of communications networks including telecommunications networks, cellular networks, paging networks, and other mobile networks.

Using memory location110A as the origin memory location and memory location110X as an example, to perform a fast-path transaction, the GC thread120A first touches the object106A in the origin memory location110A to prevent transaction aborting page faults. The GC thread120A then determines the destination memory location110X for the object106A. The GC thread120A starts a transaction. The GC thread120A copies the object106A to the destination memory location110X. The GC thread120A writes the address of the destination memory location110A in the forwarding field114A of the origin memory location110A. The GC thread120A finally terminates the transaction. The GC thread120A will attempt this fast-path transaction a number of times prior to falling back to a slow-path transaction.

Note the GC thread120A atomically performs the fast-path transaction such that any interruption or failure of the transaction causes the transaction to abort. For example, if a mutator104A attempts to update the object106A in the original memory location110A while the GC thread120A is performing the fast-path transaction to move the object106A from the original memory location110A to the destination memory location110X, the GC thread120will abort the transaction. In such an instance, the mutator104A will update the object106in the original memory location110A and the GC thread120A on a subsequent fast-path transaction attempt will move the updated object106A from the original memory location110A to the destination memory location110X.

If the GC thread120unsuccessfully attempts to move the object106A a number of times via a fast-path transaction, the GC thread120A autonomously falls-back to a slow-path transaction. At times, for example during the garbage collection move phase, the mutator104A may execute a second machine-readable instruction set that includes collaboration code. At various times, the mutator104A reads a pointer (e.g., the forwarding field114A logically associated with the original memory location106A) or writes to an object106A. For clarity, the portion of the second machine-readable instruction set providing the collaboration code executed by the mutator104A during a read operation may be referred to as a “READ barrier” and the portion of the second machine-readable instruction set providing the collaboration code executed by the mutator104A during a write operation may be referred to as a “WRITE barrier.”

FIG. 3is a high-level flow diagram of an illustrative garbage collection method300, in accordance with at least one embodiment of the present disclosure. The garbage collection circuit152moves objects within the transactional memory156to consolidate objects106, improving access times and memory usage efficiency. The garbage collection circuit152uses a garbage collection thread120to move an object106from a first memory location110A to a second memory location110B. In embodiments, the garbage collection circuit152will attempt to move an object106a defined number of times using a transactional fast-path move operation. If after unsuccessfully attempting to move the object the defined number of times via the transactional fast-path, the garbage collection circuit152will default or fallback to a non-transactional slow-path move operation. The collaboration codes executed by the mutators during the garbage collection move phase may assist in preventing “lost updates” from occurring. A lost update may occur when a mutator updates an object in a memory location that has been moved to a new location by a garbage collection thread. The method300commences at302.

At304, a mutator executes a collaboration code that permits the mutator104A and a garbage collection thread120A to operate cooperatively such that the possibility of a lost update is reduced or eliminated. The collaboration code permits the mutator104A and the garbage collection thread120A to cooperatively ensure the object in the second memory location110X represents the updated object106A and not the original (i.e., non-updated) object106A.

At306, a transactional fast-path counter (“N”) is reset to a zero value.

At308, the garbage collection circuit152attempts a transactional fast-path move of an object106A from a first (origin) memory location110A to a second (destination) memory location110X. The transactional fast-path move may be aborted responsive to one or more events that upset the atomicity of the move operation by the garbage collection thread120A. For example, if a mutator104A attempts to write to the object106A in the first memory location110A while the garbage collection thread120A is moving the object to the second memory location110X, the strongly atomic nature of the transactional memory156may cause the transaction to abort.

At310, if the garbage collection thread120A successfully moved the object106A via the transactional fast-path move at306, the method300concludes at316. If the garbage collection thread120A was unsuccessful in moving the object106A to the second memory location110X at306, the transactional fast-path move attempt counter is incremented at312.

At312, the garbage collection thread120A compares the number of transactional fast-path move attempts against the defined number of permissible transactional fast-path move attempts to determine whether the number of permissible transactional fast-path move attempts has been made. In embodiments, the number of permissible transactional fast-path move attempts may be 1 transactional fast-path move attempt (N=1); 3 or fewer transactional fast-path move attempts (N≦3); 5 or fewer transactional fast-path move attempts (N≦5); 7 or fewer transactional fast-path move attempts (N≦7); or 10 or fewer transactional fast-path move attempts (N≦10). If the number of permissible transactional fast-path move attempts has been reached at314, method300proceeds to318.

At314, the mutator104A executes a collaboration code that permits the mutator104A and the garbage collection thread120A to operate cooperatively such that the possibility of a lost update is reduced or eliminated. The collaboration code permits the mutator104A and the garbage collection thread120A to cooperatively ensure the object in the second memory location110X represents the updated object106A and not the original (i.e., non-updated) object106A.

At318, the garbage collection circuit152attempts a non-transactional slow-path move of the object106A from the first memory location110A to the second memory location110X.

At320, if the garbage collection thread120A successfully moved the object106A via the non-transactional slow-path move at318, the method300concludes at322. If the garbage collection thread120A was unsuccessful in moving the object106A to the second memory location110X via the non-transactional slow-path move at318, the garbage collection circuit152returns to318and reattempts the non-transactional slow-path move. Upon successful completion of the non-transactional slow-path move, the method300concludes at322.

FIG. 4is a high-level flow diagram of an illustrative transactional fast-path method400used by the garbage collection circuit152to move an object106A from a first memory location110A to a second memory location110X, in accordance with at least one embodiment of the present disclosure. In embodiments, the garbage collection circuit152causes a garbage collection thread152A to perform a transactional high-level move of an object106A from a first memory location110A to a second memory location110X. The garbage collection circuit152in306as described above with regard toFIG. 3may, at times, use such a transactional fast-path move. The method400commences at402.

At404, a transactional fast-path attempt counter (“N”) is reset to a zero value.

At406, the garbage collection circuit152causes a garbage collection thread120A to touch an object106A in a first memory location110A. At times, causing the garbage collection thread120A to touch an object106A in a first memory location110A may assist in preventing transaction aborting page faults.

At408, the garbage collection circuit152determines the second (i.e., destination) memory location110X to which the garbage collection thread120A will move object106A. At410, the transactional portion of the fast-path move starts.

At412, the garbage collection thread120A copies the object106A to the second (i.e., destination) memory location110X.

If, at414, the garbage collection thread120A aborts and is consequently unsuccessful in moving the object to the second memory location110X, the transactional fast-path move attempt counter (“N”) is incremented at410. The transactional fast-path move may abort for any one of a number of reasons. For example, if mutator106A attempts to update object106A in the first memory location110A contemporaneous with the garbage collection thread120A moving object106A to the second memory location.

At416, responsive to the garbage collection thread120A aborting the fast-path move, the transactional fast-path move attempt counter (“N”) is incremented.

At418, the garbage collection circuit152compares the number of transactional fast-path move attempts against the defined number of permissible transactional fast-path move attempts to determine whether the number of permissible transactional fast-path move attempts has been made. In embodiments, the number of permissible transactional fast-path move attempts may be 1 transactional fast-path move attempt (N=1); 3 or fewer transactional fast-path move attempts (N≦3); 5 or fewer transactional fast-path move attempts (N≦5); 7 or fewer transactional fast-path move attempts (N≦7); or 10 or fewer transactional fast-path move attempts (N≦10). If the number of permissible transactional fast-path move attempts has been reached at418, method400proceeds to426and terminates the transactional fast-path move. If the number of permissible transactional fast-path move attempts have not been reached, the garbage collection circuit152causes the garbage collection thread120A to reattempt the transactional fast-path move by returning to406.

At420, the garbage collection thread120A writes data indicative of the address of the second memory location110X to which the object106A has been moved to the forwarding field114A logically associated with the first memory location110A where the object106A was originally stored. By writing the data indicative of the address of the second memory location110X in the forwarding field114A of the first memory location110A, a mutator104A attempting to update the object106A in the first memory location110A will be redirected to update the object in the second memory location110X. If, at422, the garbage collection thread120A aborts while writing the address of the second memory location in the forwarding field114A logically associated with the first memory location110A, the transactional fast-path move attempt counter (“N”) is incremented at416and the method400either returns to406if the number of permissible transactional fast-path move attempts have not been reached, or proceeds to426and ends the fast-path move at426if the number of permissible transactional fast-path move attempts has been reached.

At424, the transactional portion of the fast-path move concludes and the method400terminates at426.

FIG. 5is a high-level flow diagram of an illustrative non-transactional slow-path method500used by the garbage collection circuit152and the garbage collection thread120B, in accordance with at least one embodiment of the present disclosure. In embodiments, if the garbage collection circuit152is unable to complete the transactional fast-path move of object106A after a defined number of attempts, the garbage collection circuit152causes the mutator104B to execute a collaboration code (SeeFIGS. 6 and 7). The garbage collection circuit152at318as described above with regard toFIG. 3may, at times, cause the mutator104A to execute a collaboration code and use such a non-transactional slow-path move. The example method500for performing a non-transactional slow-path move commences at502.

At504, the garbage collection circuit152causes the garbage collection thread120B to write or otherwise insert data indicative of a first logic state (e.g., FORWARDING state) in forwarding field114B logically associated with the first memory location110B.

At506, the garbage collection circuit152causes the garbage collection thread120B to perform a handshake with at least some of the mutators104writing objects106in the transactional memory156. In embodiments, the garbage collection thread120B performs the handshake with each of the mutators104to ensure the mutators104are able to observe the first logic state logically associated with the first memory location110B. At510, the garbage collection circuit152determines the second memory location110Y in the transactional memory156to which the garbage collection thread120B will move the object106B in the first memory location110B.

At512, the garbage collection circuit152causes the garbage collection thread120B to move the object106B to the second memory location110Y.

At514, the garbage collection circuit152causes the garbage collection thread120B to atomically set the forwarding field114B logically associated with the first memory location110B to a third logic state (e.g., a FORWARDED state).

At516, if the garbage collection thread120B aborts atomically setting the forwarding field114B logically associated with the first memory location110B to the third logic state, the method500returns to504. If the garbage collection thread120B does not abort atomically setting the forwarding field114B logically associated with the first memory location110B to the third logic state, the method500concludes at518. The garbage collection thread120B may abort setting the forwarding field114B logically associated with the first memory location110B to the third logic state for any of a number of reasons. For example, responsive to a mutator104B writing data indicative of a second logic state (e.g., a WRITTEN logic state) to the forwarding field114B logically associated with the first memory location110B prior to the garbage collection thread120B setting the forwarding field114B logically associated with the first memory location110B to the third logic state.

FIG. 6is a high-level flow diagram of an illustrative method600of a first portion of collaboration code used by the mutator104to cooperate with a GC thread120to move an object106in a transactional memory156while reducing the possibility of a lost update, in accordance with at least one embodiment of the present disclosure. IN embodiments, the mutator104executes a first portion of a collaboration code. In some implementations, the application102, the garbage collection circuit152, or a combination thereof may cause the execution of at least some of the first portion of the collaboration code. In embodiments, the collaboration code may cause the mutator104to operate cooperatively with the garbage collection thread120to move an object from a first memory location in the transactional memory156to a second memory location in the transactional memory156using a non-transactional slow-path move that minimizes the possibility of a lost update. The example method600commences at602.

At604, the mutator104B reads data representative of an address of a second memory location110Y in the transactional memory156from a forwarding field114B logically associated with a first memory location110B in the transactional memory156. When an object106B is moved in within the transactional memory156, the entity moving the object106(e.g., the GC thread120B) may insert data indicative of the relocation (e.g., the third logic state, FORWARDED) into the forwarding field logically associated with the first memory location in transactional memory156and representative of the address of the second memory location in transactional memory156where the object106has been moved. By accessing this information, the mutator106is made aware of object relocations.

At606, the mutator104B examines the forwarding field114Y logically associated with the second memory location110Y in the transactional memory156to determine whether the forwarding field114Y includes data indicative of the third logic state (i.e., FORWARDED). The presence of data indicative of the third logic state in forwarding field114Y provides an indication to the mutator104B that the object106B has been moved to a third memory location in the transactional memory106. If the forwarding field114Y logically associated with the second memory location110Y in the transactional memory156does NOT include data indicative of the third logic state, the method600continues at614.

At608, responsive to determining the forwarding field114Y logically associated with the second memory location110Y in the transactional memory156includes data indicative of the third logic state, the mutator104B reads data representative of the address corresponding to the third memory location from the forwarding field114Y. At610, responsive to reading the data representative of the second address corresponding to the third memory location from the forwarding field114Y logically associated with the second memory location110Y in the transactional memory156, the mutator writes data indicative of the address corresponding to the third memory location to the forwarding field114B logically associated with the first memory location110B. After writing the data representative of the third memory location in the forwarding field114B logically associated with the first memory location110B, any future operations directed to the first memory location110B will be pointed to the third memory location in the transactional memory156where the object106B currently resides.

At612, the mutator104B updates the object106B in the third memory location in the transactional memory. The method600concludes at616.

At614, responsive to determining the forwarding field114Y logically associated with the second memory location110Y in the transactional memory156does NOT include data indicative of the third logic state, the mutator104B updates object106B in the second memory location110Y. The method600then concludes at616.FIG. 7is a high-level flow diagram of an illustrative method700used by the mutator104executing a second collaboration code useful for updating an object106B in transactional memory156, in accordance with at least one embodiment of the present disclosure. The method700commences at702.

At704, the garbage collection circuit152causes the mutator104B to determine whether the forwarding field114B logically associated with the first memory location110B contains data representative of a first logic state (e.g., a FORWARDING logic state).

At706, responsive to determining the forwarding field114B logically associated with the first memory location110B contains data representative of a first logic state, the mutator104B changes the data in the forwarding field114B logically associated with the first memory location110B to data representative of a second logic state (e.g., a WRITTEN logic state). After atomically changing the forwarding field114B logically associated with the first memory location110B to the second logic state, method700proceeds at708.

At708, responsive to determining the forwarding field114B logically associated with the first memory location110B does not contain data representative of the first logic state, the garbage collection circuit152causes the mutator104B to determine whether the forwarding field114B logically associated with the first memory location110B contains data representative of a third logic state (e.g., a FORWARDED logic state).

At710, responsive to determining the forwarding field114B logically associated with the first memory location110B contains data representative of the third logic state, the mutator104B updates the object106B at the address of the second memory location110Y that is contained in the forwarding field114B logically associated with the first memory location110B. After updating the object106B at the address of the second memory location110Y that is contained in the forwarding field114B logically associated with the first memory location110B, the method700continues at712.

At712, responsive to determining the forwarding field114B logically associated with the first memory location110B does not contain data representative of the first logic state or the third logic state, the mutator104B updates the object106B in the first memory location110B. At the conclusion of the update, the updated object106B′ resides in the first memory location110B.

One of three possible scenarios exist when the mutator104B updates the object106B in the first memory location110B. In the first scenario, the mutator106B updates the object prior to the garbage collection thread120B moving the updated object106B′ to the second memory location110Y. In the second scenario, the mutator104B updates the object106B in the first memory location110B contemporaneous with the garbage collection thread120B moving the object106B to the second memory location110Y. In the final scenario, the mutator104B updates the object106B in the first memory location110B after the garbage collection thread120B has moved the object106B (i.e., the non-updated object) from the first memory location110B to the second memory location110Y.

In the first scenario, where the mutator106B updates the object prior to the garbage collection thread120B moving the updated object106B′ to the second memory location110Y, the garbage collection thread120B moves the updated object106B′ from the first memory location110B to the second memory location110Y. After moving the updated object106B′, the garbage collection thread120B updates the forwarding field114B logically associated with the first memory location110B to include a pointer to an address logically associated with the second memory location110Y to which the updated object106B′ was moved. Any subsequent attempts by the mutator104B to update the object106B in the first memory location110B are redirected to the second memory location110Y.

In the second scenario, where the mutator updates the object106B in the first memory location110B contemporaneous with the garbage collection thread120B moving the object106B to the second memory location110Y, the mutator104B uses blocks704and706to collaborate with the GC if the GC is moving the object with the slow-path and the mutator uses blocks714,716, and718to collaborate with the GC if the GC is moving the object using the fast path. Blocks708and710handle when the GC has previously moved the object. The mutator104B detects that the GC is moving the object using the slow-path by the presence of the first logic state and if that state is detected then the mutator104B will write data representative of the second logic state (e.g., WRITTEN) to the forwarding field114B logically associated with the first memory location110B. The change from the first logic state (e.g., FORWARDING) to the second logic state causes the garbage collection thread120B to fail the non-transactional, slow-path move operation. Upon reattempting the non-transactional, slow-path move operation, the garbage collection thread120B moves the now updated object106B′ from the first memory location110B to the second memory location110Y. After moving the updated object106B′, the garbage collection thread120B updates the forwarding field114B logically associated with the first memory location110B to include a pointer to an address logically associated with the second memory location110Y to which the updated object106B′ was moved. Any subsequent attempts by the mutator104B to update the object106B in the first memory location110B are redirected to the second memory location110Y.

The third scenario is addressed at714to720.

At714, the collaboration code executed by the mutator104B causes the mutator104B to determine whether the forwarding field114B logically associated with the first memory location110B previously contained data representative of the third logic state. If the forwarding field114B logically associated with the first memory location110B DID previously contain data representative of the third logic state, the method700concludes at720. If the forwarding field114B logically associated with the first memory location110B DID NOT previously contain data representative of the third logic state, the method700proceeds to716.

At716, the collaboration code executed by the mutator104B causes the mutator104B to determine whether the forwarding field114B logically associated with the first memory location110B currently contains data representative of the third logic state. If the forwarding field114B logically associated with the first memory location110B DOES NOT currently contain data representative of the third logic state, the method700concludes at720. If the forwarding field114B logically associated with the first memory location110B DOES currently contain data representative of the third logic state, the method continues at718.

At718, responsive to the mutator104B determining the forwarding field114B logically associated with the first memory location110B DOES currently contain data representative of the third logic state at716, the collaboration code executed by the mutator updates the object106B in the second memory location. The method700concludes at720.

The following examples pertain to further embodiments. The following examples of the present disclosure may comprise subject material such as a device, a method, at least one machine-readable medium for storing instructions that when executed cause a machine to perform acts based on the method, means for performing acts based on the method and/or a system for binding a trusted input session to a trusted output session to prevent the reuse of encrypted data obtained from prior trusted output sessions.

According to example 1 there is provided an electronic garbage collection system for improving memory usage and access. The electronic garbage collection system may include an atomic transactional memory to provide data storage for objects accessible by a number of mutators. The system may include a circuit communicably coupled to the atomic transactional memory. The system may further include a storage device coupled to the circuit and containing a first machine-readable instruction set that, when executed, cause the circuit to operate as a garbage collection circuit, the garbage collection circuit to: attempt a first number of transactional fast path moves of an object from a first memory location in the transactional memory to a second memory location in the transactional memory; and attempt a non-transactional slow-path move of the object from the first memory location to the second memory location responsive to failing to move the object after attempting the first number of transactional fast-path moves.

Example 2 may include elements of example 1 where the storage device includes a second machine-readable instruction set that may cause at least one mutator to read data representative of an address corresponding to the second memory location from a forwarding field logically associated with the first memory location. The second machine-readable instruction set may further cause the at least one mutator to determine, at a first time, the content of a forwarding field logically associated with the second memory location and update the object in the second memory location responsive to the presence of data indicative of at least one of: no logic state, a first logic state, or a second logic state in the forwarding field logically associated with the second memory location.

Example 3 may include elements of example 2 where the second machine-readable instruction set may further cause the at least one mutator to read data representative of an address corresponding to a third memory location in the transactional memory from a forwarding field logically associated with the second memory location responsive to the presence of data indicative of a third logic state in the forwarding field logically associated with the second memory location. The second machine-readable instruction set may further cause the at least one mutator to write data representative of the address corresponding to the third memory location in the forwarding field logically associated with the first memory location and update the object in the third memory location.

Example 4 may include the elements of example 3 where the second machine-readable instruction set may further cause the at least one mutator to read data indicative of a logic state in a forwarding field logically associated with the first memory location and write data indicative of a second logic state in the forwarding field of the object responsive to determining the data presently in the forwarding field logically associated with the first memory location is representative of a first logic state.

Example 5 may include the elements of example 4 where the first machine-readable instruction set may further cause the garbage collection circuit to cause a garbage collection thread to copy an updated object in the first memory location to the second memory location responsive to a mutator updating the object in the first memory location prior to the garbage collection thread moving the updated object from the first memory location to the second memory location.

Example 6 may include the elements of example 5 where the first machine-readable instruction set may further cause the garbage collection circuit to cause a garbage collection thread to abort, based at least in part on the atomic properties of the transactional memory, the move of the object in the first memory location to the second memory location responsive to the mutator updating the object in the first memory location contemporaneous with the garbage collection thread moving the updated object from the first memory location to the second memory location.

Example 7 may include the elements of example 6, where the first machine-readable instruction set may further cause the garbage collection circuit to cause the garbage collection thread to attempt another non-transactional slow-path move to copy an updated object from the first memory location to the second memory location responsive to aborting the move of the object in the first memory location to the second memory location.

Example 8 may include elements of example 4, where the second machine-readable instruction set may further cause the at least one mutator to write the updated object in the second memory location upon detecting the forwarding field logically associated with the first memory location includes data indicative of a third logical state and data indicative of an address of the second memory location.

Example 9 may include elements of example 4, where the second machine-readable instruction set further causes the at least one mutator to determine whether the forwarding field logically associated with the first memory location was previously in the third logic state and terminate the non-transactional slow-path move responsive to determining the forwarding field logically associated with the first memory location was previously in the third logic state.

Example 10 may include elements of example 9 where the second machine-readable instruction set further causes the at least one mutator to determine whether the forwarding field logically associated with the first memory location is currently in the third logic state and update the object in the second memory location responsive to determining the forwarding field logically associated with the first memory location is currently in the third logic state.

According to example 11, there is provided an electronic garbage collection method. The method may include a garbage collection circuit attempting, via a garbage collection thread, a first number of transactional fast-path moves to copy an object from a first memory location in a transactional memory to a second memory location in the transactional memory. The method may additionally include the garbage collection circuit aborting the respective transactional fast-path move responsive to an interruption of the transactional fast-path move. The method may further include the garbage collection circuit attempting, via the garbage collection thread, a non-transactional slow-path move to copy the object from the first memory location to the second memory location responsive to failing to move the object after the first number of transactional fast-path moves. The method may also include the garbage collection circuit repeating the non-transactional slow path-move responsive to a failure of the non-transactional slow-path move.

Example 12 may include elements of example 11 where attempting a non-transactional slow-path move to copy the object from the first memory location to the second memory location may include causing, by the garbage collection circuit, the garbage collection thread to write data representative of a first logic state in a forwarding field logically associated with the first memory location and causing, by the garbage collection circuit, the garbage collection thread to perform a handshake operation with at least one mutator.

Example 13 may include the elements of example 12 where attempting a non-transactional slow-path move to copy the object from the first memory location to the second memory location may include atomically setting, by the garbage collection circuit, the forwarding field logically associated with the first memory location to a third logic state responsive to the garbage collection thread successfully moving the object from the first memory location to the second memory location.

Example 14 may include elements of example 13 where repeating the non-transactional slow-path move responsive to a failure of the non-transactional slow-path move may include failing, by the garbage collection circuit via the garbage collection thread, to atomically set the forwarding field logically associated with the first memory location to the third logic state responsive to the at least one mutator writing data representative of a second logic state to the forwarding field logically associated with the first memory location during the non-transactional slow-path move and repeating, by the garbage collection circuit via the garbage collection thread, the non-transactional slow-path move responsive to failing to atomically set the forwarding field logically associated with the first memory location to the third logic state.

Example 15 may include elements of example 11 and may further include reading, by the at least one mutator, data representative of an address corresponding to the second memory location from a forwarding field logically associated with the first memory location. The method may also include determining, by the at least one mutator, the content of a forwarding field logically associated with the second memory location and updating, by the at least one mutator, the object in the second memory location responsive to determining the content of the a forwarding field logically associated with the second memory location does not include data indicative of the third logic state.

Example 16 may include elements of example 15 and may further include reading, by the at least one mutator, data representative of an address corresponding to a third memory location in the transactional memory from a forwarding field logically associated with the second memory location responsive to the presence of data indicative of a third logic state in the forwarding field logically associated with the second memory location. The method may additionally include writing, by the at least one mutator, data representative of the address corresponding to the third memory location in the forwarding field logically associated with the first memory location and updating, by the at least one mutator, the object in the third memory location.

Example 17 may include elements of example 16 and may further include reading, by the at least one mutator, data indicative of a logic state in a forwarding field logically associated with the first memory location and writing, by the at least one mutator, data indicative of a second logic state in the forwarding field of the object responsive to determining the data presently in the forwarding field logically associated with the first memory location is representative of a first logic state.

Example 18 may include elements of example 17 where attempting, by the garbage collection circuit via the garbage collection thread, a non-transactional slow-path move to copy the object from the first memory location to the second memory location may include copying, by the garbage collection thread, an updated object in the first memory location to the second memory location responsive to the at least one mutator updating the object in the first memory location prior to the garbage collection thread moving the updated object from the first memory location to the second memory location.

Example 19 may include elements of example 17 where attempting, by the garbage collection circuit via the garbage collection thread, a non-transactional slow-path move to copy the object from the first memory location to the second memory location may include aborting, by a garbage collection thread, the move of the object in the first memory location to the second memory location responsive to the mutator updating the object in the first memory location contemporaneous with the garbage collection thread moving the updated object from the first memory location to the second memory location.

Example 20 may include elements of example 19 where attempting, by the garbage collection circuit via the garbage collection thread, a non-transactional slow-path move to copy the object from the first memory location to the second memory location comprises attempting, by the garbage collection thread, another non-transactional slow-path move to copy the updated object from the first memory location to the second memory location responsive to aborting the move of the object in the first memory location to the second memory location.

Example 21 may include elements of example 17 and may further include writing, by the at least one mutator, the updated object in the second memory location upon detecting the forwarding field logically associated with the first memory location includes data indicative of a third logical state and data indicative of an address of the second memory location.

Example 22 may include elements of example 17 and may further include determining, by the at least one mutator, whether the forwarding field logically associated with the first memory location was previously in the third logic state and concluding the non-transactional slow-path move responsive to determining the forwarding field logically associated with the first memory location was previously in the third logic state.

Example 23 may include elements of example 22 and may further include determining, by the at least one mutator, whether the forwarding field logically associated with the first memory location is currently in the third logic state and updating, by the at least one mutator, the object in the second memory location responsive to determining the forwarding field logically associated with the first memory location is currently in the third logic state.

According to example 24, there is provided a storage device including a first machine-readable instruction set, that, when executed by a circuit, may cause the circuit to operate as a garbage collection circuit. The machine-readable instructions may cause the garbage collection circuit to attempt, via a garbage collection thread, a first number of transactional fast-path moves to copy an object from a first memory location in a transactional memory to a second memory location in the transactional memory. The machine-readable instructions may further cause the garbage collection circuit to abort the respective transactional fast-path move responsive to an interruption of the transactional fast-path move. The machine readable instructions may further cause the garbage collection circuit to attempt, via the garbage collection thread, a non-transactional slow-path move to copy the object from the first memory location to the second memory location responsive to failing to move the object after the first number of transactional fast-path moves. The machine-readable instructions may further cause the garbage collection circuit to repeat the non-transactional slow path-move responsive to a failure of the non-transactional slow-path move.

Example 25 may include elements of example 24 and the first machine-readable instruction set that causes the garbage collection circuit to repeat the non-transactional slow path-move responsive to a failure of the non-transactional slow-path move, may further cause the garbage collection circuit to cause the garbage collection thread to write data representative of a first logic state in a forwarding field logically associated with the first memory location and may further cause the garbage collection thread to perform a handshake operation with at least one mutator.

Example 26 may include elements of example 25 and the first machine-readable instruction set that may cause the garbage collection circuit to repeat the non-transactional slow path-move responsive to a failure of the non-transactional slow-path move, may further cause the garbage collection circuit to atomically set the forwarding field logically associated with the first memory location to a third logic state responsive to the garbage collection thread successfully moving the object from the first memory location to the second memory location.

Example 27 may include elements of example 26 and the first machine-readable instruction set that may cause the garbage collection circuit to repeat the non-transactional slow path-move responsive to a failure of the non-transactional slow-path move, may further cause the garbage collection circuit to abort, via the garbage collection thread, the atomic setting of the forwarding field logically associated with the first memory location to the third logic state responsive to the mutator writing data representative of a second logic state to the forwarding field logically associated with the first memory location during the non-transactional slow-path move and repeat, via the garbage collection thread, the non-transactional slow-path move responsive to aborting the atomic setting of the forwarding field logically associated with the first memory location to the third logic state.

Example 28 may include elements of example 27 and may additionally include a second machine-readable instruction set that may cause the mutator to determine the content of a forwarding field logically associated with the second memory location and update the object in the second memory location responsive to determining the content of the a forwarding field logically associated with the second memory location does not include data indicative of the third logic state.

Example 29 may include elements of example 28 and the second machine-readable instruction set may additionally cause the at least one mutator to read data representative of an address corresponding to a third memory location in the transactional memory from a forwarding field logically associated with the second memory location responsive to the presence of data indicative of a third logic state in the forwarding field logically associated with the second memory location. The second machine-readable instruction set may additionally cause the at least one mutator to write data representative of the address corresponding to the third memory location in the forwarding field logically associated with the first memory location and update the object in the third memory location.

Example 30 may include elements of example 29 and the second machine-readable instruction set may further cause the at least one mutator to read data indicative of a logic state in a forwarding field logically associated with the first memory location and write data indicative of a second logic state in the forwarding field of the object responsive to determining the data presently in the forwarding field logically associated with the first memory location is representative of a first logic state.

Example 31 may include elements of example 30 and the first machine-readable instruction set that causes the garbage collection thread to attempt a non-transactional slow-path move to copy the object from the first memory location to the second memory location responsive to failing to move the object after the first number of transactional fast-path moves, may further cause the garbage collection thread to copy an updated object in the first memory location to the second memory location responsive to the at least one mutator updating the object in the first memory location prior to the garbage collection thread moving the updated object from the first memory location to the second memory location.

Example 32 may include elements of example 30 and the first machine-readable instruction set that causes the garbage collection thread to attempt a non-transactional slow-path move to copy the object from the first memory location to the second memory location responsive to failing to move the object after the first number of transactional fast-path moves, may further cause the garbage collection thread to abort the move of the object in the first memory location to the second memory location responsive to the mutator updating the object in the first memory location contemporaneous with the garbage collection thread moving the updated object from the first memory location to the second memory location.

Example 33 may include elements of example 32 where the first machine-readable instruction set that causes the garbage collection thread to attempt a non-transactional slow-path move to copy the object from the first memory location to the second memory location responsive to failing to move the object after the first number of transactional fast-path moves, may further cause the garbage collection thread to attempt another non-transactional slow-path move to copy the updated object from the first memory location to the second memory location responsive to aborting the move of the object in the first memory location to the second memory location.

Example 34 includes elements of example 28 and the second machine-readable instruction set may further cause the at least one mutator to write the updated object in the second memory location upon detecting the forwarding field logically associated with the first memory location includes data indicative of a third logical state and data indicative of an address of the second memory location.

Example 35 includes elements of example 28 and the second machine-readable instruction set may further cause the at least one mutator to determine whether the forwarding field logically associated with the first memory location was previously in the third logic state and terminate the non-transactional slow-path move responsive to determining the forwarding field logically associated with the first memory location was previously in the third logic state.

Example 36 includes elements of example 35 and the second machine-readable instruction set may further cause the at least one mutator to determine whether the forwarding field logically associated with the first memory location is currently in the third logic state and update the object in the second memory location responsive to determining the forwarding field logically associated with the first memory location is currently in the third logic state.

According to example 37, there is provided an electronic garbage collection system. The electronic garbage collection system may include a means for performing a first number of transactional fast-path move attempts, each of the attempts including an attempted copy of an object from a first memory location in a transactional memory to a second memory location in the transactional memory. The system may further include a means for aborting the respective transactional fast-path move attempt responsive to an interruption of the transactional fast-path move. The system may additionally include a means for attempting a non-transactional slow-path move to copy the object from the first memory location in the transactional memory to the second memory location in the transactional memory responsive to unsuccessfully attempting to move the object after the first number of transactional fast-path moves and a means for repeating the non-transactional slow path-move responsive to an interruption of the non-transactional slow-path move.

Example 38 may include elements of example 37 where the means for attempting a non-transactional slow-path move to copy the object from the first memory location to the second memory location may include a means for writing data representative of a first logic state in a forwarding field logically associated with the first memory location and a means for performing a handshake operation with at least one mutator.

Example 39 may include elements of example 38 where the means for attempting a non-transactional slow-path move to copy the object from the first memory location to the second memory location may include a means for atomically setting the forwarding field logically associated with the first memory location to a third logic state responsive to a garbage collection thread successfully moving the object from the first memory location to the second memory location.

Example 40 may include elements of example 39 where the means for repeating the non-transactional slow path-move responsive to an interruption of the non-transactional slow-path move may include a means for preventing the atomic setting of the forwarding field logically associated with the first memory location to the third logic state responsive to at least one mutator writing data representative of a second logic state to the forwarding field logically associated with the first memory location during the non-transactional slow-path move and a means for repeating the non-transactional slow-path move responsive to failing to atomically set the forwarding field logically associated with the first memory location to the third logic state.

Example 41 may include elements of example 37, and may further include a means for reading data representative of an address corresponding to the second memory location from a forwarding field logically associated with the first memory location, a means for determining the content of a forwarding field logically associated with the second memory location, and a means for updating the object in the second memory location responsive to determining the content of the a forwarding field logically associated with the second memory location does not include data indicative of the third logic state.

Example 42 may include elements of example 41 and may additionally include a means for reading data representative of an address corresponding to a third memory location in the transactional memory from a forwarding field logically associated with the second memory location responsive to the presence of data indicative of a third logic state in the forwarding field logically associated with the second memory location, a means for writing data representative of the address corresponding to the third memory location in the forwarding field logically associated with the first memory location, and a means for updating the object in the third memory location.

Example 43 may include elements of example 42 and may additionally include a means for reading data indicative of a logic state in a forwarding field logically associated with the first memory location and a means for writing data indicative of a second logic state in the forwarding field of the object responsive to determining the data presently in the forwarding field logically associated with the first memory location is representative of a first logic state.

Example 44 may include elements of example 43 where the means for attempting a non-transactional slow-path move to copy the object from the first memory location to the second memory location may include a means for copying an updated object in the first memory location to the second memory location responsive to the at least one mutator updating the object in the first memory location prior to the garbage collection thread moving the updated object from the first memory location to the second memory location.

Example 45 may include elements of example 43 where the means for attempting a non-transactional slow-path move to copy the object from the first memory location to the second memory location may include a means for aborting the move of the object in the first memory location to the second memory location responsive to the mutator updating the object in the first memory location contemporaneous with the garbage collection thread moving the updated object from the first memory location to the second memory location.

Example 46 may include elements of example 31 where the means for attempting a non-transactional slow-path move to copy the object from the first memory location to the second memory location may further include a means for attempting another non-transactional slow-path move to copy the updated object from the first memory location to the second memory location responsive to aborting the move of the object in the first memory location to the second memory location.

Example 47 may include elements of example 43 and may further include a means for writing the updated object in the second memory location upon detecting the forwarding field logically associated with the first memory location includes data indicative of a third logical state and data indicative of an address of the second memory location.

Example 48 may include elements of example 43 and may further include a means for determining whether the forwarding field logically associated with the first memory location was previously in the third logic state and a means for concluding the non-transactional slow-path move responsive to determining the forwarding field logically associated with the first memory location was previously in the third logic state.

Example 49 may include elements of example 48 and may further include a means for determining whether the forwarding field logically associated with the first memory location is currently in the third logic state and a means for updating the object in the second memory location responsive to determining the forwarding field logically associated with the first memory location is currently in the third logic state.

According to example 50, there is provided a system for electronic garbage collection via an electronic garbage collection circuit, a transactional fast-path, and a backup non-transactional slow-path, the system being arranged to perform the method of any of examples 11 through 23.

According to example 51, there is provided a chipset arranged to perform the method of any of examples 11 through 23.

According to example 52, there is provided at least one machine readable medium comprising a plurality of instructions that, in response to be being executed on a computing device, cause the computing device to carry out the method according to any of examples 11 through 23.

According to example 53, there is provided a device configured for electronic garbage collection via an electronic garbage collection circuit, a transactional fast-path, and a backup non-transactional slow-path, the device being arranged to perform the method of any of examples 11 through 23.

As used in any embodiment herein, the terms “system” or “module” may refer to, for example, software, firmware and/or circuitry configured to perform any of the aforementioned operations. Software may be embodied as a software package, code, instructions, instruction sets and/or data recorded on non-transitory computer readable storage mediums. Firmware may be embodied as code, instructions or instruction sets and/or data that are hard-coded (e.g., nonvolatile) in memory devices. “Circuitry”, as used in any embodiment herein, may comprise, for example, singly or in any combination, hardwired circuitry, programmable circuitry such as computer processors comprising one or more individual instruction processing cores, state machine circuitry, and/or firmware that stores instructions executed by programmable circuitry or future computing paradigms including, for example, massive parallelism, analog or quantum computing, hardware embodiments of accelerators such as neural net processors and non-silicon implementations of the above. The modules may, collectively or individually, be embodied as circuitry that forms part of a larger system, for example, an integrated circuit (IC), system on-chip (SoC), desktop computers, laptop computers, tablet computers, servers, smartphones, etc.