Error detection/correction and fault detection/recovery – Pulse or data error handling – Memory testing
Reexamination Certificate
2000-02-09
2003-08-26
Chung, Phung M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Memory testing
C714S055000, C714S054000
Reexamination Certificate
active
06611930
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to linked lists and more particularly but not exclusively to a method and apparatus for improving the reliability of systems that use linked lists.
BACKGROUND OF THE INVENTION
Linked lists are, generally speaking, data structures containing data items arranged with integrally provided pointers to the next data item. They are popular in software applications because they give to the outside world the illusion of continuous data storage blocks whilst in fact allowing use to be made of the next available storage space at any instant in time regardless of its spatial relationship with other storage spaces. Thus, a single memory block can safely store several sets of memory data packed together without risk of confusion.
In an ATM architecture, data cells awaiting transfer along the network are stored in external RAM or memory cache. The addresses of the memory cells may be advantageously stored in a linked list internal to an ASIC or other like chip for quick access. The ASIC may store both the aforesaid linked list and another list, of empty cells, a so-called empty bin, which is used to identify suitable addresses for new incoming cells. As any particular cell is read out for sending along the network, its address is added to the back of the empty bin to await its turn to be filled again. Preferably, the empty bin is also in the form of a linked list so that all newly available cells are made available in turn. Generally, a linked list used in the normal manner has first in first out properties. Alternatively, the empty bin, or any of the other linked lists, can be read out using a statistically based or other algorithm. As a further alternative, the empty bin could be implemented as a FIFO stack, but this restricts the choice of the next cell to be read out to that at the front of the list.
In any given circumstances there may be more than one cell queue, in addition to the empty bin, and more than one delay priority and each queue and each delay priority may have its own separate list, in accordance with the requirements of the system. All the queues however, generally share the same empty bin.
A typical ATM-based system uses cell buffer managers (CBMs), which comprise an input side, a switch and an output side. On the input side of a CBM, each entry in the linked list contains the location, in the external RAM, of the present cell. It also contains the address of the next entry in the present list. A read pointer is typically provided which points to the current location in the linked list, and, in order to read an entry in the linked list, the address of the current cell is retrieved from the linked list as is the address of the next entry. The address of the next entry is then used to update the read pointer so that the next entry itself can be read. In general, the current cell is then sent and the address thereof is sent to the end of the linked list that constitutes the empty bin so that the space can be reused. As mentioned above, the linked lists, including the empty list, need not be read in order. Rather, a scheduler can be used to specify which cell is read out, and statistical algorithms or priority requirements may be incorporated into the scheduler. In that case the linked list has to be reconnected after reading.
In the output side of a CBM, a more complex arrangement of linked lists allows for the same cells to be sent to one or more output ports, for example
12
. A pointer to the same cell in memory is included in the linked list for each of the output ports and the cell is read out and sent to the respective output port at each read operation. A counter is used to keep track of multicast destinations and is decremented each time the cell is sent. The cell location is not added to the empty bin until the counter reaches zero, indicating that the cell has been sent to all required output ports. In an example, three or four linked list RAMs may be provided, each one divided into four destination ports.
As mentioned above, the empty bin may also be implemented as a linked list, for example using 32 k×20 bits. Each row may consist of a parity bit, the empty address and the counter, the empty address occupying 15 bits.
SUMMARY OF THE INVENTION
In accordance with a first aspect of the present invention there is provided a method of determining the integrity of at least one linked list stored in a plurality of cells in a memory block, comprising the steps of
providing independent bit positions,
defining each of said independent bit positions to correspond to one of said plurality of cells,
setting each of said independent bit positions to a predetermined setting,
resetting each of said independent bit positions upon access of its defined corresponding cell,
after a predetermined interval testing said independent bit positions and
if any of said independent bit positions have not been reset, setting an error condition.
Preferably, the predetermined interval is a time within which all of said plurality of cells can be expected to be accessed. This may be calculated as a number of accesses of cells in said memory block.
The independent bit positions may be contained in a separate memory block, and this is referred to herein as the diagnostic block.
Diagnostic testing of the linked list can be further enhanced by adding at least one check digit to an entry or to a data item in the linked lists. The entries in the linked list preferably comprise at least two data items each, namely a pointer to a data cell and a pointer to the next entry in the list.
According to a second aspect of the present invention there is provided apparatus for determining the integrity of a linked list, comprising a memory block for storing linked lists in a plurality of data cells and a series of independent data cell positions arranged to obtain diagnostic data of said data cells. Preferably, said diagnostic data is data indicative of whether a given data cell has been used within a predetermined time interval. Again, preferably said series of independent positions is a series of one-bit data storage positions each one operable to flag use of a different one of said plurality of data cells.
In an embodiment, each of said series of independent positions is operable to be set at the beginning of said predetermined time interval and is operable to be reset by one of a read and a write operation of a corresponding data cell. An embodiment further comprises a logic gate operable to test said series of cells at the end of said predetermined time interval, and to indicate that integrity has been compromised if any one of said series of cells has not been reset.
According to a third aspect of the present invention there is provided apparatus for measuring the integrity of one or more linked lists stored in a series of cells in a RAM, comprising a block of diagnostic bit positions each associated with a different one of the cells of the RAM, the apparatus further comprising a bit set device for setting each diagnostic bit position to a starting state, a bit reset device for resetting each diagnostic bit position from said starting state upon use of the corresponding cell within said RAM, an interval-determining device for determining the duration of an interval within which it may be expected that all cells on said RAM have been used, and an integrity determiner for determining whether all diagnostic bit positions have been reset at the end of said interval and issuing an alarm if any have not.
Preferably the staring state is high, a one, and said integrity determiner comprises a zero detector.
Preferably the integrity determiner comprises a multiple OR-gate.
The interval-determining device may be a timer. Alternatively, it may be a counter. The counter may count read operations of said linked lists. Alternatively, it may count write operations to said linked lists.
REFERENCES:
patent: 5838915 (1998-11-01), Klausmeier et al.
patent: 5845310 (1998-12-01), Brooks
patent: 6157935 (2000-12-01), Tran et al.
patent: 6445680 (2002-09-01), Moyal
pate
Dabby Amir
Ostrowsky Jacob
LandOfFree
Linked lists diagnostics does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Linked lists diagnostics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linked lists diagnostics will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3098864