Method and apparatus for implementing a statistics counter

Patent metadata

Field	Value
Publication number	US-9817574-B2
Application number	US-201615004615-A
Country	US
Kind code	B2
Filing date	Jan 22, 2016
Priority date	Jan 22, 2016
Publication date	Nov 14, 2017
Grant date	Nov 14, 2017

Abstract

According to one aspect, a method includes determining whether at least one memory storage unit in a first stage of a multi-stage array is available for use by a first counter associated with the first stage, and allocating the at least one memory storage unit for use by the first counter when the at least one memory storage unit is available. When the at least one memory storage unit is not available for use by the first counter, the method includes identifying a second counter stored in a first location in the first stage, the first location including a first memory storage unit and a second memory storage unit, and moving the second counter to a second stage of the multi-stage array, storing a pointer to the second stage in the first memory storage unit, and allocating the second memory storage unit to the first counter.

First claim

What is claimed is:

1. A method comprising:
determining whether at least one memory storage unit in a first stage of a multi-stage array is available for use by a first counter associated with the first stage;
allocating the at least one memory storage unit for use by the first counter when it is determined that the at least one memory storage unit is available for use by the first counter; and
when it is determined that the at least one memory storage unit is not available for use by the first counter:
identifying a second counter, the second counter being stored in a first location in the first stage, the first location including a first memory storage unit and a second memory storage unit;
moving the second counter to a second stage of the multi-stage array;
storing a pointer to the second stage, the pointer being stored in the first memory storage unit and arranged to identify the second counter in the second stage; and
allocating the second memory storage unit to the first counter.

2. The method of claim 1 wherein when it is determined that the at least one memory storage unit is not available for use by the first counter, the method further includes:
updating metadata associated with the first stage to indicate that the pointer is stored in the first memory storage unit; and
updating the metadata associated with the first stage to indicate that the second memory storage unit is allocated to the first counter.

3. The method of claim 2 wherein the first location further includes a third memory storage unit, and the method further includes:
providing an indication arranged to indicate that the third memory storage unit is free.

4. The method of claim 1 wherein the first counter is a new counter to which no bits have previously been allocated, and wherein the method further includes:
determining that the first counter is to be stored in the first stage; and
storing the first counter in the second memory storage unit after allocating the second memory storage unit to the first counter.

5. The method of claim 1 wherein the first counter is an existing counter, and wherein determining whether the at least one memory storage unit in a first stage of a multi-stage array is available for use by the first counter includes determining whether updating the first counter will overflow the first stage.

6. The method of claim 1 wherein identifying the second counter includes identifying the second counter as a largest counter stored in the first stage.

7. Logic encoded in one or more tangible non-transitory, computer-readable media for execution and when executed operable to:
determine whether at least one memory storage unit in a first stage of a multi-stage array is available for use by a first counter associated with the first stage;
allocate the at least one memory storage unit for use by the first counter when it is determined that the at least one memory storage unit is available for use by the first counter; and
when it is determined that the at least one memory storage unit is not available for use by the first counter:
identify a second counter, the second counter being stored in a first location in the first stage, the first location including a first memory storage unit and a second memory storage unit;
move the second counter to a second stage of the multi-stage array;
store a pointer to the second stage, the pointer being stored in the first memory storage unit and arranged to identify the second counter in the second stage; and
allocate the second memory storage unit to the first counter.

8. The logic of claim 7 wherein when it is determined that the at least one memory storage unit is not available for use by the first counter, the logic is further operable to:
update metadata associated with the first stage to indicate that the pointer is stored in the first memory storage unit; and
update the metadata associated with the first stage to indicate that the second memory storage unit is allocated to the first counter.

9. The logic of claim 8 wherein the first location further includes a third memory storage unit, and the logic is further operable to:
provide an indication arranged to indicate that the third memory storage unit is free.

10. The logic of claim 7 wherein the first counter is a new counter to which no bits have previously been allocated, and wherein the logic is further operable to:
determine that the first counter is to be stored in the first stage; and
store the first counter in the second memory storage unit after allocating the second memory storage unit to the first counter.

11. The logic of claim 7 wherein the first counter is an existing counter, and wherein the logic operable to determine whether the at least one memory storage unit in a first stage of a multi-stage array is available for use by the first counter is operable to determine whether updating the first counter will overflow the first stage.

12. The logic of claim 7 wherein the logic operable to identify the second counter is operable to identify the second counter as a largest counter stored in the first stage.

13. An apparatus comprising:
a processor;
a data storage structure, the data storage structure including a multi-stage array, the multi-stage array including at least a first row and a second row; and
a logic module, the logic module including computer program code arranged to be executed by the processor, the logic module including logic configured to determine whether at least one memory unit in the first row is available for use by a first counter and logic configured to move a second counter from a first location in the first row to the second row when it is determined that the at least one memory unit in the first row is not available and to store a pointer to the second row, the pointer being stored in a first memory unit associated with the first location.

14. The apparatus of claim 13 wherein the data storage structure is a static random access memory (SRAM).

15. The apparatus of claim 13 wherein the first location also includes a second memory unit, and where the logic module further includes logic configured to allocate the second memory unit to the first counter.

16. The apparatus of claim 15 wherein the data storage structure includes metadata, and wherein the logic module further includes logic configured to update the metadata to indicate that the pointer is stored in the first memory unit and that the second memory unit is allocated to the first counter.

17. The apparatus of claim 13 wherein the logic configured to move the second counter from the first location in the first row to the second row is configured to identify the second counter as a largest counter in the first row.

18. The apparatus of claim 17 wherein the logic configured to move the second counter from the first location in the first row to the second row is configured to move the second counter to a first free location in the second row.

19. The apparatus of claim 13 wherein the at least one memory unit includes four bits.

20. The apparatus of claim 13 wherein the logic configured to determine whether the at least one memory unit in the first row is available for use by the first counter is configured to allocate the at least one memory unit for use by the first counter when it is determined that the at least one memory unit in the first row is available for use by the first counter.

Assignees

• Cisco Tech Inc

Inventors

• Dharmapurikar Sarang
• Wu Ganlin
• Seibulescu Alex
• Wu Wanli

Classifications

• G06F3/0608

  Saving storage space on storage systems · CPC title

• G06F2212/1044

  Space efficiency improvement · CPC title

• G06F12/023 Primary

  Free address space management · CPC title

• H04L43/08

  Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters · CPC title

• G06F2212/154

  Networked environment · CPC title