Systems and methods for recovering memory

• US 7,343,513 B1
• Filed: 09/23/2004
• Issued: 03/11/2008
• Est. Priority Date: 09/24/2003
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Basu, Debashis, Ofelt, David
• Primary Examiner(s): DUNCAN, MARC M
• Application Number:
  US10/947,314
• Time in Patent Office: 1,265 Days
• Field of Search: 714/5, 714/21, 714/42
• US Class Current: 714/5.1
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 2212/1032 Reliability improvement, data loss prevention, degraded operation etc
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G11C 29/76 using address translation or modifications

Abstract

A system includes a group of devices and a shared memory that is partitioned into blocks that are capable of being allocated to the group of devices using linked lists. The system also includes check logic configured to store a group of bits, where each bit corresponds to one of the blocks, and counter logic configured to count for a predetermined period of time. The system further includes logic configured to clear the group of bits stored in the check logic, cause the counter logic to count for the predetermined period of time, monitor a de-allocation of the blocks in the shared memory, set, for each of the blocks that is de-allocated during the predetermined period of time, the corresponding bit in the check logic, identify, after the predetermined period of time, one or more bits that have not been set, and mark the blocks corresponding to the one or more bits as available for allocation.

Claims

1. A method for recovering blocks of memory, comprising:

setting bits stored in a first device to a first value, each bit corresponding to one of a plurality of blocks in the memory;

retrieving a first tail pointer from a list indicating which of the plurality of blocks is available, the first tail pointer identifying a last available block of the plurality of blocks;

monitoring a de-allocation of each of the plurality of blocks;

setting, for each block of the plurality of blocks that is de-allocated, the corresponding bit in the first device to a second value;

detecting allocation of the last available block of the plurality of blocks;

starting a counter, the counter being configured to count for a predetermined time period;

reading, after the predetermined time period has elapsed, a second tail pointer associated with each of a plurality of second devices to which the plurality of blocks in the memory are capable of being allocated, each second tail pointer identifying one of the plurality of blocks;

setting bits in the first device corresponding to the blocks identified by the second tail pointers to the second value;

determining whether at least one of the bits in the first device has not been set to the second value; and

making, when at least one bit has not been set to the second value, the block corresponding to each of the at least one bit available for allocation to the plurality of second devices.

2. The method of claim 1 wherein the predetermined time period is configurable.

3. The method of claim 1 wherein the setting bits stored in a first device to a first value;

retrieving a first tail pointer from a list indicating which of the plurality of blocks is available;

monitoring a de-allocation of each of the plurality of blocks;

setting, for each block of the plurality of blocks that is de-allocated, the corresponding bit in the first device to a second value;

detecting allocation of the last available block of the plurality of blocks;

starting a counter;

reading, after the predetermined time period has elapsed, a second tail pointer associated with each of a plurality of second devices;

setting bits in the first device corresponding to the blocks identified by the second tail pointers to the second value;

determining whether at least one of the bits in the first device has not been set to the second value; and

making, when at least one bit has not been set to the second value, the block corresponding to each of the at least one bit available for allocation to the plurality of second devices occur at a predetermined interval.

4. The method of claim 1 wherein the retrieving the first tail pointer from a list includes:

retrieving the first tail pointer from an external memory.

5. The method of claim 1 wherein the setting bits stored in a first device to a first value;

retrieving a first tail pointer from a list indicating which of the plurality of blocks is available;

monitoring a de-allocation of each of the plurality of blocks;

setting, for each block of the plurality of blocks that is de-allocated, the corresponding bit in the first device to a second value;

detecting allocation of the last available block of the plurality of blocks;

starting a counter;

reading, after the predetermined time period has elapsed, a second tail pointer associated with each of a plurality of second devices;

setting bits in the first device corresponding to the blocks identified by the second tail pointers to the second value;

determining whether at least one of the bits in the first device has not been set to the second value; and

making, when at least one bit has not been set to the second value, the block corresponding to each of the at least one bit available for allocation to the plurality of second devices are performed continuously.

6. A system that includes a plurality of devices to which blocks in a shared memory are allocated using linked lists, a head/tail pointer memory that stores a head pointer and a tail pointer for each of the plurality of devices, and a free list that identifies available blocks in the shared memory and includes a free list tail pointer that identifies one of the blocks in the shared memory, the system comprising:

check logic configured to store bits corresponding to the blocks in the shared memory;

a counter configured to count for a predetermined period of time; and

control logic configured to;

clear the bits in the check logic,

read the free list tail pointer,

monitor a de-allocation of the blocks in the shared memory,

mark, for each of the blocks that is de-allocated, the corresponding bit in check logic,

detect allocation of the block corresponding to the free list tail pointer,

cause the counter to begin counting,

read, after the predetermined period of time, the tail pointers for each of the plurality of devices from the head/tail pointer memory,

mark, for each of the blocks that correspond to the read tail pointers, the corresponding bit in check logic,

identify one or more bits in check logic that have not been marked, and

mark the blocks corresponding to the identified one or more bits as available.

7. The system of claim 6 wherein the predetermined period of time is configurable.

8. The system of claim 6 wherein the control logic performs the clearing the bits in the check logic, reading the free list tail pointer, monitoring a de-allocation of the blocks in the shared memory, marking, for each of the blocks that is de-allocated, the corresponding bit in check logic, detecting allocation of the block corresponding to the free list tail pointer, causing the counter to begin counting, reading, after the predetermined period of time, the tail pointers for each of the plurality of devices from the head/tail pointer memory, marking, for each of the blocks that correspond to the read tail pointers, the corresponding bit in check logic, identifying one or more bits in check logic that have not been set, and marking the blocks corresponding to the identified one or more bits as available at a predetermined interval.

9. The system of claim 8 wherein the predetermined interval is configurable.

10. The system of claim 6 wherein, when marking the blocks corresponding to the identified one or more bits as available, the control logic is configured to:

store information corresponding to each of the marked blocks in the free list.

11. The system of claim 6 wherein the linked lists, free list, and head/tail pointer memory are located on an external memory.

12. The system of claim 6 wherein the plurality of devices includes a plurality of queues.

13. A system that includes a plurality of devices and a shared memory that is partitioned into blocks that are capable of being allocated to the plurality of devices using linked lists, the system comprising:

check logic configured to store a plurality of bits, each bit corresponding to one of the plurality of blocks;

counter logic configured to count for a predetermined period of time; and

logic configured to;

clear the plurality of bits in the check logic,

cause the counter logic to count for the predetermined period of time,

monitor a de-allocation of the plurality of blocks in the shared memory,

set, for each of the plurality of blocks that is de-allocated during the predetermined period of time, the corresponding bit in check logic,

identify, after the predetermined period of time, one or more bits that have not been set, and

mark the blocks corresponding to the one or more bits as candidates for corruption.

14. The system of claim 13 further comprising:

a free list configured to store a tail pointer that identifies one of the blocks that is available for allocation, and

wherein the logic marks the blocks as candidates for corruption after the one block identified by the tail pointer has been allocated.

15. The system of claim 13 wherein the logic performs the clearing, causing, monitoring, setting, identifying, and marking at predetermined time intervals.

16. The system of claim 13 further comprising:

a tail memory configured to store tail pointers for each of the plurality of devices, the tail pointers identifying blocks in the shared memory,

wherein the logic is further configured to;

read the tail pointers from the tail memory,

set the bit in check logic corresponding to each of the blocks that corresponds to the tail pointers,

identify, after setting the bit corresponding to each of the blocks that corresponds to the tail pointers, first bits in the check logic that have not been set, and

making the blocks corresponding to the first bits available for allocation to the plurality of devices.

17. The system of claim 13 wherein the logic performs the clearing, causing, monitoring, setting, identifying, and marking automatically at predetermined intervals.

18. The system of claim 13 wherein the logic performs the clearing, causing, monitoring, setting, identifying, and marking continuously.

19. The system of claim 13 wherein the plurality of devices, check logic, counter logic, and logic are located on a single chip.

20. A method for recovering lost blocks of memory, comprising:

setting bits stored in a first device to a first value, each bit corresponding to one of a plurality of blocks in the memory;

storing a first tail pointer from a list indicating which of the plurality of blocks is available, the first tail pointer identifying one available block of the plurality of blocks;

monitoring a de-allocation of each of the plurality of blocks;

setting, for each block of the plurality of blocks that is de-allocated, the corresponding bit in the first device to a second value;

reading, after the one available block identified by the first tail pointer has been allocated, a second tail pointer associated with each of a plurality of second devices to which the plurality of blocks in the memory are capable of being allocated, each second tail pointer identifying one of the plurality of blocks;

setting bits in the first device corresponding to the blocks identified by the second tail pointers to the second value;

determining whether at least one of the bits in the first device has not been set to the second value; and

making, when at least one bit has not been set to the second value, the block corresponding to each of the at least one bit available for allocation to the plurality of second devices.

21. A network device that includes a plurality of devices to which blocks in a shared memory are allocated using linked lists, a head/tail pointer memory that stores a head pointer and a tail pointer for each of the plurality of devices, and a free list that identifies available blocks in the shared memory and includes a free list tail pointer that identifies one of the blocks in the shared memory, the system comprising:

check logic configured to store bits corresponding to the blocks in the shared memory; and

control logic configured to;

clear the bits in the check logic,

read the free list tail pointer,

monitor a de-allocation of the blocks in the shared memory,

mark, for each of the blocks that is de-allocated, the corresponding bit in check logic,

read, after the one block has been allocated, the tail pointers for each of the plurality of devices from the head/tail pointer memory,

mark, for each of the blocks that correspond to the read tail pointers, the corresponding bit in check logic,

identify one or more bits in check logic that have not been marked, and

mark the blocks corresponding to the identified one or more bits as available.