CN108804337B - Memory garbage collection method, device and computer storage medium - Google Patents
Memory garbage collection method, device and computer storage mediumInfo
- Publication number
- CN108804337B CN108804337B CN201710306751.XA CN201710306751A CN108804337B CN 108804337 B CN108804337 B CN 108804337B CN 201710306751 A CN201710306751 A CN 201710306751A CN 108804337 B CN108804337 B CN 108804337B
- Authority
- CN
- China
- Prior art keywords
- node
- nodes
- marked
- garbage
- ring
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/0223—User address space allocation, e.g. contiguous or non contiguous base addressing
- G06F12/023—Free address space management
- G06F12/0253—Garbage collection, i.e. reclamation of unreferenced memory
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Processing Of Solid Wastes (AREA)
- Memory System (AREA)
Abstract
本申请提供了一种内存垃圾回收的方法和装置。该方法包括：根据应用程序的标记节点以及标记节点的引用计数值，确定标记节点是否位于垃圾循环引用RC环中，其中，垃圾RC环中的节点均不存在外部引用；在标记节点位于垃圾RC环中时，对垃圾RC环中的节点进行回收。本申请能够实现对垃圾RC环的回收。
This application provides a method and apparatus for memory garbage collection. The method includes: determining, based on an application's marked node and its reference count, whether the marked node is located in a garbage circular reference (RC) ring, where no nodes in the garbage RC ring have any external references; and, if the marked node is located in the garbage RC ring, recycling the nodes in the garbage RC ring. This application can implement garbage RC ring recycling.
Description
Technical Field
The present application relates to the field of computer technology, and more particularly, to a method and apparatus for memory garbage collection, and a computer storage medium.
Background
In recent years, with the rapid development of internet of things (Internet of Things, ioT) technology, a wide variety of IoT devices have emerged. Because of the limited memory resources of IoT devices (FLASH is less than 128KB and ram is less than 64 KB), in order to be able to conveniently deploy applications or services into IoT devices, an effective way is to support JavaScript (hereinafter JS) language in IoT devices, but a lot of garbage objects are generated during JS operation, and an automatic recycling mechanism is needed for garbage recycling (Garbage Collection, GC).
In the prior art, objects which are no longer used by an application program in an IoT device are recycled through a reference counting method, so that automatic recycling of memory resources is realized. Reference counting is implemented by maintaining a reference count for each node (the node may also be referred to as an in-memory object, simply referred to as an "object"), increasing its reference count by 1 when a new reference is directed to the node, decreasing its reference count by 1 when an application directed to the node is destroyed, and reclaiming memory resources occupied by the node when the count returns to zero.
However, the reference counting method cannot recycle the node where the cyclic reference (REFERENCE CYCLE, RC) occurs, as shown in fig. 1, R2 and R3 form an RC loop (ref in the figure represents the reference count value of the corresponding node), R1 has an external reference, the reference count value of R1 is 2, and the reference count values of R2 and R3 are 1. As shown in FIG. 2, when the external references disappear, but the references count of R1, R2 and R3 cannot be cleared due to the mutual references among the nodes in the ring, so that part of the memory cannot be recovered, and the memory resource is wasted.
Disclosure of Invention
The application provides a method, a device and a computer storage medium for recycling memory garbage, which can realize recycling of garbage RC rings.
According to a first aspect, a memory garbage collection method is provided, and the method comprises the steps of determining whether marked nodes are located in a garbage circulation reference RC ring according to marked nodes of an application program and reference count values of the marked nodes, wherein no external reference exists in the nodes in the garbage RC ring, and collecting the nodes in the garbage RC ring when the marked nodes are located in the garbage RC ring.
In the application, whether the marked node is positioned in the garbage RC ring or not can be determined by the marked node and the reference count value of the marked node, and the garbage RC ring can be recycled under the condition that the marked node is positioned in the garbage RC ring.
With reference to the first aspect, in some implementations of the first aspect, the determining whether the marked node is located in the garbage-cycle reference RC ring according to the marked node of the application program and the reference count value of the marked node includes subtracting 1 from the reference count value of the child node of the current node, if a first target child node with a reference count value of 0 appears in the child nodes of the current node, taking the first target child node as the current node, re-executing the step until a target condition is met, and if the first target child node does not appear in the child nodes of the current node, exiting the step, wherein the marked node is an initial value of the current node, the target condition is that the marked node appears in the first target child node of the current node, and if the target condition is met, determining that the marked node is located in the garbage-RC ring.
The above-mentioned reference count value of the child node of the current node is decremented by 1, and in the case where the first target child node appears in the child nodes of the current node, the first target child node can be regarded as the current node, and the reference count value of the current node is continued to be decremented by 1, which may be referred to as a subtraction operation. By the subtraction operation, whether the marked node is located in the garbage RC ring can be conveniently determined, so that the nodes in the garbage RC ring can be recycled after the marked node is determined to be located in the garbage RC ring.
With reference to the first aspect, in certain implementation manners of the first aspect, the method further includes determining that the marked node is located in a non-garbage RC ring if the target condition is not satisfied, and recovering reference count values of the current node and child nodes of the current node.
When the marked node is not in the garbage RC ring, the reference count value of the non-garbage RC exchange can be recovered by recovering the current node and the reference count value of the current node, so that the correctness of the reference relation of other non-garbage RC ring nodes after the recovery operation is executed is ensured.
With reference to the first aspect, in some implementations of the first aspect, the recovering the reference count values of the current node and the child nodes of the current node includes adding 1 to the reference count value of the child node of the current node, if a second target child node with the reference count value of 1 appears in the child nodes of the current node, taking the second target child node as the current node, re-executing the step, and if the second target child node does not appear in the child nodes of the current node, exiting the step.
With reference to the first aspect, in certain implementation manners of the first aspect, the method further includes determining a set of marked nodes, wherein the set of marked nodes includes a plurality of nodes, and the marked nodes are any node in the plurality of nodes.
In a second aspect, there is provided an apparatus for memory garbage collection, the apparatus comprising means for performing the method of the first aspect or various implementations thereof.
In a third aspect, there is provided an apparatus for memory garbage collection, the apparatus comprising a storage medium, and a central processing unit, the storage medium may be a non-volatile storage medium, the storage medium having stored therein a computer executable program, the central processing unit being connected to the non-volatile storage medium and executing the computer executable program to implement the method of the first aspect or various implementations thereof.
In a fourth aspect, a computer readable medium is provided, the computer readable medium storing program code for computer execution, the program code comprising instructions for performing the method of the first aspect or various implementations thereof.
It should be understood that the technical solutions provided in the second to fourth aspects of the present invention are consistent with the technical solutions provided in the first aspect, and the technical beneficial effects are similar, and are not repeated.
Drawings
FIG. 1 is a schematic diagram of an RC loop.
Fig. 2 is a schematic diagram of an RC ring.
FIG. 3 is a schematic flow chart of a method of memory garbage collection according to an embodiment of the present application.
Fig. 4 is a schematic diagram of an RC ring.
Fig. 5 is a schematic diagram of an RC ring.
Fig. 6 is a schematic diagram of an RC ring.
Fig. 7 is a schematic diagram of an RC ring.
Fig. 8 is a schematic diagram of an RC ring.
Fig. 9 is a schematic diagram of an RC ring.
Fig. 10 is a schematic diagram of an RC ring.
Fig. 11 is a schematic diagram of an RC ring.
FIG. 12 is a schematic flow chart of a method of memory garbage collection according to an embodiment of the present application.
Fig. 13 is a schematic diagram of a plurality of nodes according to an embodiment of the present application.
Fig. 14 is a schematic diagram of a plurality of nodes according to an embodiment of the present application.
Fig. 15 is a schematic diagram of a plurality of nodes according to an embodiment of the present application.
Fig. 16 is a schematic diagram of a plurality of nodes according to an embodiment of the present application.
Fig. 17 is a schematic diagram of a plurality of nodes according to an embodiment of the present application.
Fig. 18 is a schematic diagram of a plurality of nodes according to an embodiment of the present application.
Fig. 19 is a schematic diagram of a plurality of nodes according to an embodiment of the present application.
FIG. 20 is a schematic diagram of a plurality of nodes according to an embodiment of the present application.
Fig. 21 is a schematic block diagram of an apparatus for memory garbage collection according to an embodiment of the present application.
Fig. 22 is a schematic block diagram of an apparatus for memory garbage collection according to an embodiment of the present application.
Detailed Description
The technical scheme of the application will be described below with reference to the accompanying drawings.
Fig. 3 is a schematic flow chart of a memory garbage recycling method according to an embodiment of the present application. The method of fig. 3 includes:
110. And determining whether the marked nodes are positioned in the garbage RC ring according to the marked nodes of the application program and the reference count values of the marked nodes, wherein no external reference exists in the nodes in the garbage RC ring.
For example, as shown in FIG. 4, where there are no other external references to node A and node B that refer to each other, A and B form a garbage RC ring.
In addition, as shown in fig. 5, the nodes A, B, C are referenced to each other, and no external reference points to the three nodes, then the three nodes A, B, C also form a garbage RC ring.
As shown in fig. 6, the nodes A, B, C are referenced to each other, and there is an external reference to a, so the three nodes A, B, C form a non-garbage RC ring.
The garbage RC ring described above may be considered a memory node that is not related to the application running, whereas a non-garbage RC ring may be considered some memory node that is related to the application running.
Alternatively, the marking of the node in the application may be implemented by calling a built-in function, for example, by adding the built-in function SETCYCLEHEADER in the JS virtual machine. During the running of the application, this built-in function is executed, the is_root flag bit in the memory header of the node in the RC ring is set to true, and the node is added to the set of flag nodes (which may also be referred to as a set of circular linked lists) to facilitate the next determination of whether each node in the set of flag nodes is located in the RC ring.
120. In the case where the marked node is located in the garbage RC ring, the nodes in the garbage RC ring are reclaimed.
In the application, whether the marked node is positioned in the garbage RC ring or not can be determined by the marked node and the reference count value of the marked node, and the garbage RC ring can be recycled under the condition that the marked node is positioned in the garbage RC ring.
The marking nodes can be obtained by marking the nodes in the possible RC ring, and compared with the mode of recycling the garbage RC ring by marking strong references (strong), weak references (weak) and no main references (unowned) in the prior art, the marking rules are greatly simplified and the method is easy to realize. Specifically, in the prior art, weak references or no main references need to be set in consideration of different conditions, the rule is complicated and strict, and a serious memory problem can be caused by setting errors.
Alternatively, the marking node may be a node obtained by marking a node that may form an RC ring in the application program by the user. Specifically, the user may mark nodes that may be located in the RC ring during the program development stage, add the marked nodes to a marked node set (the marked node set may include a plurality of marked nodes), and then process each marked node by using the method of fig. 3 to determine whether each marked node is located in the garbage RC ring.
It should be appreciated that marking any one node in the RC ring as a marked node may be traversed from that marked node to other nodes in all RC rings.
The program developer marks the nodes in the possible RC ring to obtain marked nodes, so that the detection range of the RC ring node can be reduced, the memory consumption of an algorithm is reduced, and the instantaneity is improved.
Optionally, the method of FIG. 3 further comprises determining a set of marked nodes, wherein the set of marked nodes comprises a plurality of nodes, and the marked nodes are any one of the plurality of nodes. It should be appreciated that multiple marked nodes may be obtained after marking nodes in a possible RC ring, and that combining multiple marked nodes together results in a marked node set.
Optionally, determining whether the marked node is located in the garbage RC ring according to the marked node of the application program and the reference count value of the marked node specifically comprises subtracting 1 from the reference count value of the child node of the current node, if a first target child node with the reference count value of 0 appears in the child nodes of the current node, taking the first target child node as the current node, re-executing the step until a target condition is met, and if the first target child node does not appear in the child nodes of the current node, exiting the step, wherein the marked node is an initial value of the current node, the target condition is that the marked node appears in the first target child node of the current node, and determining that the marked node is located in the garbage RC ring if the target condition is met.
The above-mentioned reference count value of the child node of the current node is decremented by 1, and in the case that the first target child node appears in the child nodes of the current node, the first target child node can be regarded as the current node, and the reference count value of the current node is continued to be decremented by 1, which may be referred to as a subtraction operation (Decrease). By the subtraction operation, whether the marked node is located in the garbage RC ring can be conveniently determined, so that the nodes in the garbage RC ring can be recycled after the marked node is determined to be located in the garbage RC ring.
For a better understanding of the subtraction operation, the principle of the subtraction operation is described below in connection with pseudo-code.
The relevant pseudocode for the subtraction operation is as follows:
Specifically, when the above-mentioned marked nodes are processed by the subtraction operation, first, the marked node set (cycle_ roots) is traversed, and then the decrement operation (Decrease (root)) is performed on the reference count value (ref) of each marked node (root) and its referenced child node
When traversing the marked node set, if the reference count value of a certain marked node is 0, deleting the marked node from the marked node set, starting to process the next marked node in the marked node set, and if the reference count value of the certain marked node is not 0, starting to process the child node of the marked node, and setting the marked node as the node (root. Is_found=true) which has undergone the subtraction operation.
When a child node of a marked node is processed, if ref=ref-1 of the child node of the marked node is set as ref=0, the traversal of the branch of the child node is stopped, if ref=ref-1 of the child node of the marked node is set as ref=0 of the child node and the child node does not belong to a node which has undergone subtraction operation, the subtraction operation needs to be further executed on the direct child node of the child node, and if ref=ref-1 of the child node of the marked node is set as ref=0 of the child node, but the child node belongs to a node which has undergone subtraction operation, the traversal of the branch of the child node is stopped.
The process of the subtraction operation is described in detail below in connection with fig. 7 to 9.
As shown in fig. 7, a is a marking node, and a specific process of determining whether a is located in the garbage RC ring is as follows:
The reference count value of the sub-node B of a is decremented by 1 so that the reference count value of the node B becomes 0, and since the reference count value of B becomes 0 after the decrementing by 1, the reference count value of C becomes 0 after the decrementing by 1, the reference count value of the sub-node a of C becomes 1 after the decrementing by 1, the reference count value of a becomes 0 after the decrementing by 1, the reference count values of these three nodes are shown in fig. 8 after the subtracting operation. As can be seen from fig. 8, after subtracting the reference count values generated by mutual reference between A, B and C, the reference count values of the three nodes are all 0, so a is located in the RC loop, and the RC loop is a garbage RC loop. The trash RC ring where A is located can then be recycled.
As shown in fig. 9, a is a marking node, and a specific process of determining whether a is located in the garbage RC ring is as follows:
The reference count value of the sub-node B of a is decremented by 1 such that the reference count value of B is changed from 2 to 1, and since a has only one sub-node B and the reference count value of B is not equal to 0 after undergoing the subtraction operation, the subtraction operation is not performed on the sub-node of B. The reference count values of these three nodes after subtraction are shown in fig. 10, and A, B and C form an RC ring as shown in fig. 10, but since B has an external reference, the RC ring does not belong to the garbage RC ring, that is, node a is not located in the garbage RC ring but is located in the non-garbage RC ring. Therefore, the non-garbage RC ring where a is located cannot be recovered next.
The reference count value of the nodes in the garbage RC ring is cleared through subtraction operation, that is, after the garbage RC ring is subjected to subtraction operation, the reference count value of all the nodes in the ring is 0, and then the nodes in the garbage RC ring can be recycled.
It should be understood that when marking nodes, for each RC ring, at least one node should be marked, if a plurality of nodes marked with a certain RC ring do not affect the recovery of the memory garbage, and for a certain RC ring, if any node in the RC ring is not marked, the RC ring cannot be recovered, which may cause memory leakage. In addition, in order to improve the efficiency of garbage collection, only one node in the RC ring can be marked as a marking node under the condition of determining the RC ring, and the node is marked under the condition that whether the node is positioned in the RC ring is not determined, so that the mismarking of the node as the node in the RC ring does not influence the collection of the garbage.
For example, when a marked node is a mislabeled non-garbage RC ring node and its reference count value has become 0 before it is processed using the above-described subtraction operation, it may be deleted from the marked node set and the marked node is reclaimed using the normal RC mechanism of the prior art (reclaiming a certain node when its reference count value becomes 0).
It should be understood that in the present application, after subtracting the reference count value of a certain node in the RC ring where the marked node is located by using a subtraction operation, if the reference count value of the node is 0, the method of fig. 3 does not immediately recycle the node, but recycles all nodes in the garbage RC ring after determining that the marked node is in the garbage RC ring, or recovers the reference count value subtracted by the subtraction operation in the marked node and its child nodes when determining that the marked node is not in the garbage RC ring.
Optionally, in some embodiments, the method of FIG. 3 further comprises determining that the marked node is located in a non-garbage RC ring if the above-described target condition is not met, and restoring reference count values for the current node and children of the current node.
When the marked node is not in the garbage RC ring, the reference count value of the non-garbage RC exchange can be recovered by recovering the current node and the reference count value of the current node, so that the correctness of the reference relation of other non-garbage RC ring nodes after the recovery operation is executed is ensured.
For example, the reference count value of each node after subtracting the marked node and its child nodes in fig. 9 is as shown in fig. 10, and the reference count value of B is not 0 after subtracting 1 from the reference count value of B of a, so it is finally determined that a is not located in the RC ring, and next, the reference count value of B needs to be restored to 2 before subtracting.
Optionally, recovering the reference count value of the current node and the sub-node of the current node, specifically comprising adding 1 to the reference count value of the sub-node of the current node, if a second target sub-node with the reference count value of 1 appears in the sub-nodes of the current node, taking the second target sub-node as the current node, re-executing the step, and if the second target sub-node does not appear in the sub-node of the current node, exiting the step.
Optionally, after determining that the marked node is in the garbage RC ring, the garbage RC ring may be added to the garbage node set, then other marked nodes are similarly processed, the garbage RC ring in which other nodes are located is also added to the garbage node set, and then the nodes in the garbage node set are reclaimed.
It should be understood that in the present application, the nodes in the garbage node set may be recovered after the garbage RC rings where all the marked nodes are located are added to the garbage node set, or the nodes in the garbage RC rings may be recovered directly after the garbage RC rings where some marked nodes are located are determined.
For example, as shown in fig. 10, after the subtraction operation, the reference count value of the node B is restored from 2 to 1, and then, the reference count value of the node B needs to be restored. As shown in fig. 11, the specific process of recovering the reference count value of the node B is that, from the marked node a, the reference count value of the sub node B of a is added by 1 so that the reference count value of B becomes 2, and the process of recovering the reference count value ends because the reference count value of B is 1.
It should be appreciated that the above-described adding 1 to the reference count value of a child node of a current node to effect restoration of the reference count value of the node may be referred to as a Restore (Restore) operation. It should be understood that, in order to avoid performing repeated recovery operations when performing recovery operations as described above, the reed_restore flag may be set, and the reed_restore flag of a node may be set to be true after performing recovery operations on a certain node.
In order to better understand the recovery operation, the principle of the subtraction operation is explained below in connection with pseudo code.
The pseudo code associated with the restore operation is as follows:
Specifically, when the above marked nodes are processed by the recovery operation, the marked node set (cycle_ roots) is traversed first, and then the recovery operation is performed on the reference count value of each node whose reference count value is not 0 and its child nodes.
When the recovery operation is executed, after ref=ref+1 of the child node of the marked node (the reference count value of the marked node is not 0), if ref++1 of the child node, the traversal of the branch of the child node is stopped, and after ref=ref+1 of the child node of the marked node, if ref=1 of the child node, that is, 0 is changed to 1, the add 1 operation is further executed on the child node of the child node.
It should be appreciated that the recovery operation corresponds to an inverse operation of the subtraction operation, when the marker node is located in the garbage RC ring, the subtraction operation is performed on the garbage RC ring, and then the recovery operation is not performed on the garbage RC ring, and when the marker node is located in the non-garbage RC ring, the recovery operation is performed on the non-garbage RC ring after the subtraction operation is performed on the non-garbage RC ring, so that the reference count value of the node in the non-garbage RC ring is recovered to the value before the subtraction operation, so as to ensure the correctness of the reference relationship of the non-garbage RC ring after the recovery operation.
After determining that the marked node is in the garbage RC ring, the nodes in the garbage RC ring may be reclaimed. The principles of reclamation operations are described below in connection with pseudo code.
The pseudo code associated with the reclamation operation is as follows:
After traversing the set of marker nodes, the subtraction operation and the recovery operation, only ref of the garbage RC-ring node (including the marker node for marking the garbage RC-ring) is cleared. In order to prevent repeated collection caused by the existence of a plurality of nodes in the same RC ring and the cyclic reference existing in the ring, an is_ collected flag bit is set, the flag bit is set to true when a certain node is collected, and the flag bit is judged to be false before collection and can be added to a garbage node set. Collecting nodes with ref of 0 and sub-nodes with ref of 0, releasing the nodes, deleting the nodes from the record node set, completing the garbage RC ring recovery, clearing the flag bits except the is_root of the rest nodes in the mark node set, and waiting for the next garbage RC ring recovery algorithm call.
Optionally, 4 flag bits may be set in the reserved bits of the memory header (memheader) of each node for use in reclaiming garbage. The meaning of each flag bit of the node is specifically as follows:
The following describes the memory garbage recycling method according to the embodiment of the present application in detail with reference to fig. 12 to 20.
Fig. 12 shows the entire process of reclaiming memory garbage. The process specifically comprises the following steps:
210. and marking the nodes in the application program to obtain marked nodes.
220. A set of marker nodes { R1, R2, R3} is determined.
In fig. 13, R1, R2, R3 are suspected RC ring nodes added to the marker node, a-E are other nodes recursively traversed such as the marker node to make a reference relationship, forming a circular reference relationship of [ R1, B ], [ R1, C, B ], [ R2, R3]. Suppose the order in which the subtraction operations are performed is R1-R2-R3.
230. A subtraction operation is performed:
the specific case of performing the subtraction operation includes sequentially performing the subtraction operation on R1, R2, and R3.
The subtracting operation performed on R1 and its child nodes specifically includes:
(1) Subtracting 1 from the reference count values of child nodes A, B and C of R1 to obtain the result shown in FIG. 14;
(2) Since the reference count value of C becomes 0, the reference count values of the child node B and R2 of C are decremented by 1, resulting in the result shown in fig. 15;
(3) Since the reference count value of B becomes 0, the reference count value of the child node R1 of B is decremented by 1, resulting in the result shown in fig. 16.
Since R1 has already undergone a subtraction operation, the subtraction operation on the R1 node and its child nodes is terminated.
The subtracting operation performed on R2 and its child nodes specifically includes:
(4) Subtracting 1 from the reference count value of the child node R3 of R2 to obtain a result shown in FIG. 17;
(5) Since the reference count value of R3 becomes 0, the reference count values of the child nodes R2, D, and E of R3 are decremented by 1, resulting in the result shown in fig. 18.
Since R2 has already undergone a subtraction operation, the subtraction operation on the R2 node and its child nodes is terminated.
The subtracting operation performed on R3 and its child nodes specifically includes:
Since the subtraction operation has been performed on R3 in step 220 and the reference count value of R3 is 0, the subtraction operation is not performed on R3 and its child nodes, and R3 is deleted from the set of marked nodes, thus completing the subtraction operation.
240. Traversing the marked node set, and recovering the marked nodes and the child nodes thereof with the reference count value not being 0 in the marked set.
Specifically, after the subtraction operation, the marker nodes in the marker node set are traversed, and since the reference count values of R1 and R3 become 0 and the reference count value of R2 becomes 1, only the flag bit of the reed_restore of R2 needs to be set to be wire, so that in the restoration operation, only the restoration operation needs to be performed on the node R2 with the reed_restore flag bit of wire.
The process of recovering R2 is specifically as follows:
(6) Adding 1 to the reference count value of the child node R3 of R2 to obtain a result shown in FIG. 19;
(7) The reference count value for child nodes R2, D, and E of R3 is incremented by 1 to yield the result shown in FIG. 20.
Since the reference count value of R2 is not 1 after 1 is added, the restoration operation for R2 and its child nodes ends.
250. And collecting the garbage RC ring.
260. And recycling the nodes in the garbage RC ring.
As shown in fig. 20, after the subtraction operation and the recovery operation, the reference count value of the marker node R1 becomes 0, so R1 is collected, and the sub-nodes B and C whose reference count value is 0, and the sub-node a has no reference count value of a set to 0 because there is still an external reference, then the nodes in the garbage ring [ R1, C, B ] can be collected and released, and the reference count value is not set to zero in the RC ring [ R2, R3] because there is still an external reference in R2, which is a non-garbage RC ring, and is left to be detected again next time.
The method for recycling memory garbage according to the embodiment of the present application is described in detail above with reference to fig. 3 to 20, and the apparatus for recycling memory garbage according to the embodiment of the present application is described below with reference to fig. 21 to 22, and it should be understood that the apparatus in fig. 21 and 22 can implement each step of the method for recycling memory garbage described above, and duplicate descriptions are omitted below appropriately for brevity.
Fig. 21 is a schematic block diagram of an apparatus for memory garbage collection according to an embodiment of the present application. The apparatus 300 of fig. 21 may perform the method of memory garbage collection described above in fig. 3. The apparatus 300 includes:
A determining module 310, configured to determine, according to a marked node of an application program and a reference count value of the marked node, whether the marked node is located in a garbage-cycle reference RC ring, where no external reference exists in nodes in the garbage RC ring;
And the recycling module 320 is configured to recycle the nodes in the garbage RC ring when the marked nodes are located in the garbage RC ring.
Optionally, as an embodiment, the determining module 310 is specifically configured to subtract 1 from a reference count value of a child node of a current node, if a first target child node with a reference count value of 0 appears in the child nodes of the current node, take the first target child node as the current node, re-execute the step until a target condition is met, and exit the step if the first target child node does not appear in the child nodes of the current node, where the flag node is an initial value of the current node, and the target condition is that the flag node appears in the first target child node of the current node, and determine that the flag node is located in the garbage RC ring if the target condition is met.
Optionally, as an embodiment, the determining module 310 is further configured to determine that the marked node is located in a non-garbage RC ring if the target condition is not satisfied;
the apparatus 300 further comprises:
And a restoration module 320, configured to restore the reference count values of the current node and the child nodes of the current node.
Optionally, as an embodiment, the restoration module 320 is specifically configured to increment a reference count value of a child node of a current node by 1, if a second target child node with a reference count value of 1 appears in the child nodes of the current node, take the second target child node as the current node, re-execute the step, and if the second target child node does not appear in the child nodes of the current node, exit the step.
Optionally, as an embodiment, the determining module 310 is further configured to determine a set of marked nodes, where the set of marked nodes includes a plurality of nodes, and the marked node is any node of the plurality of nodes.
Fig. 22 is a schematic block diagram of an apparatus for memory garbage collection according to an embodiment of the present application. The apparatus 400 of fig. 22 may perform the method of memory garbage collection described above in fig. 3. The apparatus 400 includes:
A memory 410 for storing a program;
the processor 420 is configured to execute a program stored in the memory 410, where the processor 420 is specifically configured to determine, according to a marked node of an application program and a reference count value of the marked node, whether the marked node is located in a garbage-cycle reference RC ring, where no external reference exists in a node in the garbage RC ring, and when the marked node is located in the garbage RC ring, recycle the node in the garbage RC ring.
Optionally, as an embodiment, the processor 420 is specifically configured to subtract 1 from a reference count value of a child node of a current node, if a first target child node with a reference count value of 0 appears in the child nodes of the current node, take the first target child node as the current node, re-execute the step until a target condition is met, and exit the step if the first target child node does not appear in the child nodes of the current node, where the flag node is an initial value of the current node, and the target condition is that the flag node appears in the first target child node of the current node, and determine that the flag node is located in the garbage RC ring if the target condition is met.
Optionally, as an embodiment, the processor 420 is further configured to determine that the marked node is located in a non-garbage RC ring if the target condition is not satisfied, and restore the reference count values of the current node and the child nodes of the current node.
Optionally, as an embodiment, the processor 420 is specifically configured to increment a reference count value of a child node of the current node by 1, if a second target child node with a reference count value of 1 appears in the child nodes of the current node, take the second target child node as the current node, re-execute the step, and if the second target child node does not appear in the child nodes of the current node, exit the step.
Optionally, as an embodiment, the processor 420 is further configured to determine a set of marked nodes, where the set of marked nodes includes a plurality of nodes, and the marked node is any node of the plurality of nodes.
Alternatively, the apparatus 300 and the apparatus 400 may be IoT devices or other devices with limited memory resources.
Those of ordinary skill in the art will appreciate that the various illustrative elements and algorithm steps described in connection with the embodiments disclosed herein may be implemented as electronic hardware, or combinations of computer software and electronic hardware. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the solution. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the present application.
It will be clear to those skilled in the art that, for convenience and brevity of description, specific working procedures of the above-described systems, apparatuses and units may refer to corresponding procedures in the foregoing method embodiments, and are not repeated herein.
In the several embodiments provided by the present application, it should be understood that the disclosed systems, devices, and methods may be implemented in other manners. For example, the apparatus embodiments described above are merely illustrative, e.g., the division of the units is merely a logical function division, and there may be additional divisions when actually implemented, e.g., multiple units or components may be combined or integrated into another system, or some features may be omitted or not performed. Alternatively, the coupling or direct coupling or communication connection shown or discussed with each other may be an indirect coupling or communication connection via some interfaces, devices or units, which may be in electrical, mechanical or other form.
The units described as separate units may or may not be physically separate, and units shown as units may or may not be physical units, may be located in one place, or may be distributed on a plurality of network units. Some or all of the units may be selected according to actual needs to achieve the purpose of the solution of this embodiment.
In addition, each functional unit in the embodiments of the present application may be integrated in one processing unit, or each unit may exist alone physically, or two or more units may be integrated in one unit.
The functions, if implemented in the form of software functional units and sold or used as a stand-alone product, may be stored in a computer-readable storage medium. Based on this understanding, the technical solution of the present application may be embodied essentially or in a part contributing to the prior art or in a part of the technical solution, in the form of a software product stored in a storage medium, comprising several instructions for causing a computer device (which may be a personal computer, a server, a network device, etc.) to perform all or part of the steps of the method according to the embodiments of the present application. The storage medium includes a U disk, a removable hard disk, a Read-Only Memory (ROM), a random access Memory (Random Access Memory, RAM), a magnetic disk, an optical disk, or other various media capable of storing program codes.
The foregoing is merely illustrative of the present application, and the present application is not limited thereto, and any person skilled in the art will readily recognize that variations or substitutions are within the scope of the present application. Therefore, the protection scope of the present application shall be subject to the protection scope of the claims.
Claims (10)
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201710306751.XA CN108804337B (en) | 2017-05-04 | 2017-05-04 | Memory garbage collection method, device and computer storage medium |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201710306751.XA CN108804337B (en) | 2017-05-04 | 2017-05-04 | Memory garbage collection method, device and computer storage medium |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN108804337A CN108804337A (en) | 2018-11-13 |
| CN108804337B true CN108804337B (en) | 2025-10-28 |
Family
ID=64054407
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201710306751.XA Active CN108804337B (en) | 2017-05-04 | 2017-05-04 | Memory garbage collection method, device and computer storage medium |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN108804337B (en) |
Families Citing this family (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111736980B (en) * | 2019-03-25 | 2024-01-16 | 华为技术有限公司 | A memory management method and device |
| CN111736925B (en) * | 2019-03-25 | 2025-05-16 | 华为技术有限公司 | Reference counting implementation method and device |
| CN110489173B (en) * | 2019-07-31 | 2023-10-03 | 广州微算互联信息技术有限公司 | Method, system and storage medium for unloading ceph mirror image block device |
| CN115982060B (en) * | 2021-10-14 | 2024-07-05 | 华为技术有限公司 | A memory recovery method and related device |
| CN117891616B (en) * | 2024-03-15 | 2024-06-28 | 腾讯科技（深圳）有限公司 | Garbage collection method, device and equipment for application program and storage medium |
| CN119718482B (en) * | 2025-02-26 | 2025-08-15 | 广州致远电子股份有限公司 | Object reference management method, device, equipment and storage medium |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101046755A (en) * | 2006-03-28 | 2007-10-03 | 郭明南 | System and method of computer automatic memory management |
| CN103226476A (en) * | 2013-05-20 | 2013-07-31 | 张永强 | Garbage object detecting method and device |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US9053017B2 (en) * | 2011-09-09 | 2015-06-09 | Microsoft Technology Licensing, Llc | Managing object lifetime in a cyclic graph |
| CN102929699B (en) * | 2012-10-10 | 2015-06-10 | 武汉钢铁(集团)公司 | Garbage recycling method for Java virtual machine and monitoring system thereof |
-
2017
- 2017-05-04 CN CN201710306751.XA patent/CN108804337B/en active Active
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101046755A (en) * | 2006-03-28 | 2007-10-03 | 郭明南 | System and method of computer automatic memory management |
| CN103226476A (en) * | 2013-05-20 | 2013-07-31 | 张永强 | Garbage object detecting method and device |
Also Published As
| Publication number | Publication date |
|---|---|
| CN108804337A (en) | 2018-11-13 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN108804337B (en) | Memory garbage collection method, device and computer storage medium | |
| JP6087928B2 (en) | Managing object life in a cyclic graph | |
| JP6110020B2 (en) | Reference counter integrity check | |
| CN108363657B (en) | Method, device and medium for monitoring the integrity of APP client buried point data collection | |
| EP3121723A1 (en) | Information processing device, influence-process extraction method, and recording medium | |
| CN103984609B (en) | A kind of method and apparatus that checkpoint is reclaimed in file system based on copy-on-write | |
| CN111125298A (en) | Method, equipment and storage medium for reconstructing NTFS file directory tree | |
| CN113259176B (en) | Alarm event analysis method and device | |
| JP2016540269A (en) | Method and system for selecting an encoding format for reading a target document | |
| CN109871290B (en) | Call stack tracking method and device applied to Java and storage medium | |
| CN111858146B (en) | Method, apparatus and computer program product for recovering data | |
| CN113572719B (en) | Domain name detection method, device, equipment and readable storage medium | |
| CN114690064B (en) | Unified handling methods, devices, and power modules for different types of faults | |
| CN104021073A (en) | Software vulnerability detection method based on pointer analysis | |
| CN101414299B (en) | Method and apparatus for repairing composite document | |
| CN113296965A (en) | Deadlock processing method and device, electronic equipment and computer storage medium | |
| CN118378288B (en) | A dynamic detection method and system for encryption algorithm based on Pin tool | |
| CN106202251A (en) | A kind of association page method for digging accessed based on user and system | |
| CN111737751B (en) | Method and device for realizing distributed data processing of privacy protection | |
| CN117541385A (en) | Frequent financial transaction mining method and device based on association rule item | |
| CN119583365A (en) | A method and system for computing node network relationship changes in a network range | |
| CN111880942A (en) | Network threat processing method and device | |
| CN112686029A (en) | SQL new sentence identification method and device for database audit system | |
| CN111240956A (en) | Memory leak monitoring method, device, electronic device and computer storage medium | |
| CN112615874B (en) | Network protection method and device |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |