Merging independent writes, separating dependent and independent writes, and error roll back

• US 9,430,511 B2
• Filed: 03/13/2014
• Issued: 08/30/2016
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Billa, Satyanarayana Lakshmipathi, Goyal, Rajan
• Primary Examiner(s): McMahon, Daniel
• Application Number:
  US14/207,928
• Publication Number:
  US 20140281809A1
• Time in Patent Office: 901 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1666 where the redundant component is memory or memory area
• CPC Class Codes: G06F 11/167 Error detection by comparing the memory output
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0646 Horizontal data movement in storage systems, i.e. moving data in between storage devices or systems
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

In an embodiment, a method of updating a memory with a plurality of memory lines, the memory storing a tree, a plurality of buckets, and a plurality of rules, includes maintaining a copy of the memory with a plurality of memory lines. The method further includes writing a plurality of changes to at least one of the tree, the plurality of buckets, and the plurality of rules to the copy. The method further includes determining whether each of the plurality of changes is an independent write or a dependent write. The method further includes merging independent writes to the same line of the copy. The method further includes transferring updates from the plurality of lines of the copy to the plurality of lines of the memory.

Claims

1. A method of updating a memory with a plurality of memory lines, the memory storing a tree, a plurality of buckets, and a plurality of rules, the method comprising:

maintaining a copy of the memory with a plurality of memory lines;

writing a plurality of changes to at least one of the tree, the plurality of buckets, and the plurality of rules to the copy;

determining whether each of the plurality of changes is an independent write or a dependent write;

merging independent writes to a same memory line of the copy in a single line write; and

transferring updates from the plurality of memory lines of the copy to the plurality of memory lines of the memory.

2. The method of claim 1, wherein transferring includes:

transferring the merged independent writes from the copy to the memory; and

in an event transferring the merged independent writes from the copy to the memory is successful, transferring the dependent writes from the copy to the memory.

3. The method of claim 1, further comprising:

determining whether writing the plurality of changes to the copy caused an error; and

reversing the plurality of changes to the copy if the plurality of changes caused the error, wherein transferring the updates includes transferring the updates from the copy to the memory if the plurality of changes did not cause the error.

4. The method of claim 3, wherein the error indicates updating the memory requires allocation of more memory than is available at the memory.

5. The method of claim 1, wherein, in a given cycle, a bank of the memory can be accessed by at most one port.

6. The method of claim 1, wherein writing the plurality of changes includes first, writing the plurality of rules corresponding to the plurality of buckets associated with the tree to the copy, second, writing the plurality of buckets to the copy, and third, writing the tree to the copy.

7. The method of claim 1, wherein writing the plurality of changes includes writing a given rule of the plurality of rules and a given bucket of the plurality of buckets to the copy simultaneously if the given bucket points to the given rule.

8. The method of claim 1, further comprising:

determining the plurality of changes based on an updated tree, a plurality of updated buckets, a plurality of updated rules, and lines of the copy of the memory;

modifying the lines of the copy of the memory based on the updated tree, the plurality of updated buckets, and the plurality of updated rules; and

writing the lines to the copy.

9. A system for updating a memory with a plurality of memory lines, the memory storing a tree, a plurality of buckets, and a plurality of rules, the system comprising:

a shadow memory module configured to maintain a copy of the memory with a plurality of memory lines;

a change set module configured to write a plurality of changes to at least one of the tree, the plurality of buckets, and the plurality of rules to the copy;

a dependency testing module configured to determine whether each of the plurality of changes is an independent write or a dependent write;

a merging module configured to merge independent writes to a same memory line of the copy in a single line write; and

an update transfer module configured to transfer updates from the plurality of memory lines of the copy to the plurality of memory lines of the memory.

10. The system of claim 9, wherein the update transfer module is further configured to:

transfer the merged independent writes from the copy to the memory; and

in an event the transfer of the merged independent writes from the copy to the memory is successful, transfer the dependent writes from the copy to the memory.

11. The system of claim 9, further comprising:

an error testing module configured to determine whether writing the plurality of changes to the copy caused an error; and

wherein the update transfer module is further configured to reverse the plurality of changes to the copy if the plurality of changes caused the error and further configured to transfer the updates by transferring the updates from the copy to the memory if the plurality of changes did not cause the error.

12. The system of claim 11, wherein the error indicates updating the memory requires allocation of more memory than is available at the memory.

13. The system of claim 9, wherein, in a given cycle, a bank of the memory can be accessed by at most one port.

14. The system of claim 9, wherein the change set module is configured to write the plurality of changes by first, writing the plurality of rules corresponding to the plurality of buckets associated with the tree to the copy, second, writing the plurality of buckets to the copy, and third, writing the tree to the copy.

15. The system of claim 9, wherein to write the plurality of changes the change set module is further configured to write a given rule of the plurality of rules and a given bucket of the plurality of buckets to the copy simultaneously if the given bucket points to the given rule.

16. The system of claim 9, wherein the change set module is further configured to:

determine the plurality of changes based on an updated tree, a plurality of updated buckets, a plurality of updated rules, and lines of the copy of the memory;

modify the lines of the copy of the memory based on the updated tree, plurality of updated buckets, and plurality of updated rules; and

write the lines to the copy.

17. A non-transitory computer-readable medium configured to store instructions for updating a memory with a plurality of memory lines, the memory storing a tree, a plurality of buckets, and a plurality of rules, the instructions, when loaded and executed by a processor, causes the processor to:

maintain a copy of the memory with a plurality of memory lines;

write a plurality of changes to at least one of the tree, the plurality of buckets, and the plurality of rules to the copy;

determine whether each of the plurality of changes is an independent write or a dependent write;

merge independent writes to a same memory line of the copy in a single line write; and

transfer updates from the plurality of memory lines of the copy to the plurality of memory lines of the memory.

18. The non-transitory computer-readable medium of claim 17, wherein to transfer the updates the instructions further cause the processor to:

transfer the merged independent writes from the copy to the memory; and

in an event the transfer of the merged independent writes from the copy to the memory is successful, transfer the dependent writes to the lines of the memory.

19. The non-transitory computer-readable medium of claim 17, wherein the instructions further cause the processor to:

determine whether writing the plurality of changes to the copy caused an error; and

reverse the plurality of changes to the copy if the plurality of changes caused the error, wherein to transfer the updates the instructions further cause the processor to transfer the updates from the copy to the memory if the plurality of changes did not cause the error.

20. The non-transitory computer-readable medium of claim 19, wherein the error indicates updating the memory requires allocation of more memory than is available at the memory.

21. The non-transitory computer-readable medium of claim 17, wherein the instructions further cause the processor to merge writes to the memory.

22. The non-transitory computer-readable medium of claim 17, wherein, in a given cycle, a bank of the memory can be accessed by at most one port.

23. The non-transitory computer-readable medium of claim 17, wherein the instructions further cause the processor to write the plurality of changes by first, writing the plurality of rules corresponding to the plurality of buckets associated with the tree to the copy, second, writing the plurality of buckets to the copy, and third, writing the tree to the copy.

24. The non-transitory computer-readable medium of claim 17, wherein to write the plurality of changes the instructions further cause the processor to write a given rule of the plurality of rules and a given bucket of the plurality of buckets to the copy simultaneously if the given bucket points to the given rule.

25. The non-transitory computer-readable medium of claim 17, wherein the instructions further cause the processor to:

determine the plurality of changes based on an updated tree, a plurality of updated buckets, a plurality of updated rules, and lines of the copy of the memory;

modify the lines of the copy of the memory based on the updated tree, the plurality of updated buckets, and the plurality of updated rules; and

write the lines to the copy.