Free list and ring data structure management

• US 7,337,275 B2
• Filed: 08/13/2002
• Issued: 02/26/2008
• Est. Priority Date: 08/13/2002
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Sweeney, John, Bernstein, Debra, Rosenbluth, Mark B., Wolrich, Gilbert, Guilford, James D.
• Primary Examiner(s): Nguyen; Hiep T.
• Application Number:
  US10/218,682
• Publication Number:
  US 20040034743A1
• Time in Patent Office: 2,023 Days
• Field of Search: 711/132, 710/52, 709/213, 709/214
• US Class Current: 711/132
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9031 Wraparound memory, e.g. overrun or underrun detection
• CPC Class Codes: H04L 49/9047 including multiple buffers, e.g. buffer pools

Abstract

A method of managing a free list and ring data structure, which may be used to store journaling information, by storing and modifying information describing a structure of the free list or ring data structure in a cache memory that may also be used to store information describing a structure of a queue of buffers.

Claims

1. A method comprising:

checking a content addressable memory for a tag corresponding to a queue of data buffers associated with a dequeue request;

accessing a queue descriptor, for the queue of data buffers, in a cache memory based on a result of the checking;

removing a data buffer from the queue of data buffers using the queue descriptor from the cache memory;

processing information in the removed data buffer; and

appending the data buffer to a queue of currently unused buffers in response to an enqueue request.

2. The method of claim 1 further comprising storing currently unused buffers using a linked list data structure.

3. The method of claim 1 further comprising storing currently unused buffers using a stack data structure.

4. The method of claim 1 wherein the data buffer comprises a network packet and wherein the network packet comprises a packet received in a network processor.

5. The method of claim 1 further comprising modifying information describing a structure of the queue of currently unused buffers.

6. The method of claim 5 wherein said removing is performed in response to receiving a data packet in a receive pipeline and appending and modifying are performed in response to receiving the enqueue request.

7. A method comprising:

removing a currently unused buffer from a queue of currently unused buffers in response to a dequeue request;

processing a newly received data packet;

storing the newly received data packet in the removed buffer;

checking a content addressable memory for a tag corresponding to a queue of data buffers associated with an enqueue request;

accessing a queue descriptor, for the queue of data buffers, in a cache memory based on a result of the checking;

appending the removed buffer to the queue of data buffers using the queue descriptor from the cache memory.

8. The method of claim 7 further comprising storing currently unused buffers using a linked list data structure.

9. The method of claim 7 further comprising storing currently unused buffers using a stack data structure.

10. The method of claim 7 wherein the data buffer comprises a network packet and wherein the network packet comprises a packet received in a network processor.

11. The method of claim 7 further comprising modifying information describing a structure of the queue of currently unused buffers.

12. The method of claim 11 wherein said removing is performed in response to receiving a data packet in the receive pipeline and storing and modifying are performed in response to receiving the dequeue request.

13. A method comprising:

receiving a request to write data to a memory ring data structure; and

issuing a command, in response to the request, the command specifying a pointer to a memory location in which the data is to be inserted, said pointer describing a structure of the memory ring;

writing data to a memory ring address identified by the information describing a structure of the memory ring;

incrementing a pointer to a memory location in which data is to be inserted, said pointer describing a structure of the memory ring;

incrementing the number of entries in the ring, said number of entries describing a structure of the memory ring; and

storing the modified pointer and number of entries which describe a structure of the memory ring in a cache memory having entries to store information describing a structure of a queue of data buffers or a structure of a queue of currently unused buffers.

14. The method of claim 13 wherein the command specifies a length field and wherein the number of entries in the ring is incremented by the specified length field.

15. The method of claim 13 further comprising:

returning to an issuing programming engine thread, in response to the issued command, the number of entries in the ring, said number of entries describing a structure of the memory ring data structure; and

returning a status bit that indicates whether sufficient memory is available to cause data to be written successfully to the memory ring address identified by a pointer to a memory location where data is to be inserted, said pointer describing a structure of the memory ring.

16. The method of claim 13, the command further specifying a memory address from which to obtain data that is to be written to the memory ring.

17. The method of claim 16 wherein the data contains bite representing an output message from an executing program.

18. The method of claim 17 wherein the bits also include a programming engine identification and a context identification.

19. The method of claim 16 wherein the data contains bits representing a command address, said bits also include a programming engine identification and a context identification.

20. The method of claim 16 further comprising:

writing data to a memory ring address identified by the information describing a structure of the memory ring;

incrementing a pointer to the memory location where the data is to be inserted, said pointer describing a structure of the memory ring;

incrementing, by the specified length field, the number of entries in the ring, said number of entries describing a structure of the memory ring; and

storing the modified pointer and number of entries describing a structure of the memory ring in a cache memory having entries to store information describing a structure of a queue of data buffers.

21. The method of claim 20 wherein the cache memory can be used to store information about multiple memory ring data structures.

22. A method comprising:

receiving a request to read data from a memory ring data structure; and

issuing a command, in response to the request, specifying a pointer to a memory location from which the data is to be removed, said pointer describing a structure of the memory ring;

reading data from a memory ring address identified by the information describing a structure of the memory ring;

incrementing a pointer to a memory location from which data is to be removed, said pointer describing a structure of the memory ring;

decrementing the number of entries in the ring, said number of entries describing a structure of the memory ring; and

storing the modified pointer and number of entries which describe a structure of the memory ring in a cache memory having entries to store information describing a structure of a queue of data buffers.

23. The method of claim 22 wherein the command specifies a length field and wherein the number of entries in the ring is decremented by the specified length field.

24. The method of claim 22 further comprising;

returning an identifier to an issuing programming engine context, in response to the issued command, when the number of entries in the ring, said number of entries describing a structure of the memory ring, is less than the specified length field.

25. An apparatus comprising:

a processor providing a queue manager and a content addressable memory to store tags associated with buffer queues;

a first memory coupled to the processor to store a queue of data buffers and at least one of a queue of currently unused buffers or a ring data structure;

a cache memory coupled to the processor to store information describing a structure of the queue of data buffers and information describing at least one of a structure of the queue of currently unused buffers or a structure of the memory ring; and

a second memory to store instructions that, when applied to the processor, cause the processor to;

check the content addressable memory for a tag corresponding to the queue of data buffers;

access the information describing the structure of the queue of data buffers in the cache memory based on a result of the check;

remove a data buffer from the queue of data buffers using the information from the cache memory describing the structure of the queue of data buffers;

process information in the removed data butter; and

append the data buffer to a queue of currently unused buffers in response to an enqueue request.

26. The apparatus of claim 25 wherein the second memory further includes instructions to cause the processor to store currently unused buffers using a linked list data structure.

27. The apparatus of claim 25 wherein the second memory further includes instructions to cause the processor to store currently unused buffers using a stack data structure.

28. The apparatus of claim 25 wherein the second memory further includes instructions to cause the processor to modify information describing a structure of the queue of currently unused buffers.

29. The apparatus of claim 25 wherein the data buffer comprises a network packet and wherein the network packet comprises a packet received in a network processor.

30. An apparatus comprising:

a processor providing a queue manager and a content addressable memory to store tags associated with buffer queues;

a first memory coupled to the processor to store a queue of data buffers and at least one of a queue of currently unused buffers or a ring data structure;

a cache memory coupled to the processor to store information describing a structure of a queue of data buffers and information describing at least one of a structure of the queue of currently unused buffers or a structure of the memory ring; and

a second memory to store instructions that, when applied to the processor, cause the processor to;

remove a currently unused buffer from a queue of currently unused buffers in response to a dequeue request;

process a newly received data packet;

store the newly received data packet in the removed buffer;

check the content addressable memory for a tag corresponding to the queue of data buffers;

access the information describing the structure of the queue of data buffers in the cache memory based on a result of the check; and

append the removed buffer to the queue of data buffers using the queue descriptor from the cache memory.

31. The apparatus of claim 30 wherein the second memory further includes instructions to cause the processor to store currently unused buffers using a linked list data structure.

32. The apparatus of claim 30 wherein the second memory further includes instructions to cause the processor to store currently unused buffers using a stack data structure.

33. The apparatus of claim 30 wherein the data buffer comprises a network packet and wherein the network packet comprises a packet received in a network processor.

34. The apparatus of claim 30 wherein the second memory further includes instructions to cause the processor to modify information describing a structure of the queue of currently unused buffers.

35. An apparatus comprising:

a processor providing a queue manager;

a first memory coupled to the processor to store a queue of data buffers and at least one of a queue of currently unused buffers or a ring data structure;

a cache memory coupled to the processor to store information describing a structure of the queue of data buffers and information describing at least one of a structure of the queue of currently unused buffers or a structure of the memory ring; and

a second memory to store instructions that, when applied to the processor, cause the processor to;

receive a request to write data to a memory ring data structure;

issue a command, in response to the request, the command specifying a pointer to a memory location where the data is to be inserted, said pointer describing a structure of the memory ring;

write data to a memory ring address identified by the information describing a structure of the memory ring;

increment a pointer to a memory location where data is to be inserted, said pointer describing a structure of the memory ring;

increment the number of entries in the ring, said number of entries describing a structure of the memory ring; and

store the modified pointer and number of entries which describe a structure of the memory ring in a cache memory having entries to store information describing a structure of a queue of data buffers or a structure of a queue of currently unused buffers.

36. The apparatus of claim 35 wherein the command specifies a length field and wherein the number of entries in the ring is incremented by the specified length field.

37. The apparatus of claim 35 wherein the second memory further includes instructions to cause the processor to:

return to an issuing programming engine thread, in response to the issued command, the number of entries in the ring, said number of entries describing a structure of the memory ring data structure; and

return a status bit that indicates whether sufficient memory is available to cause data to be written successfully to the memory ring address identified by a pointer to a memory location where data is to be inserted, said pointer describing a structure of the memory ring.

38. The apparatus of claim 35 wherein the command further specifies a memory address from which to obtain data that is to be written to the memory ring.

39. The apparatus of claim 38 wherein the data contains bits representing an output message from an executing program.

40. The apparatus of claim 39 wherein the bits also include a programming engine identification and a context identification.

41. The apparatus of claim 38 wherein the data contains bits representing a command address, said bits also include a programming engine identification and a context identification.

42. The apparatus of claim 38 wherein the second memory further includes instructions to cause the processor to:

write data to a memory ring address identified by the information describing a structure of the memory ring;

increment a pointer to the memory location where the data is to be inserted, said pointer describing a structure of the memory ring;

increment, by the specified length field, the number of entries in the ring, said number of entries describing a structure of the memory ring; and

store the modified pointer and number of entries describing a structure of the memory ring in a cache memory having entries to store information describing a structure of a queue of data buffers.

43. The apparatus of claim 38 wherein the cache memory can be used to store information about multiple memory ring data structures.

44. An apparatus comprising:

a processor providing a queue manager;

a first memory coupled to the processor to store a queue of data buffers and at least one of a queue of currently unused buffers or a ring data structure;

a cache memory coupled to the processor to store information describing a structure of the queue of data buffers and information describing at least one of a structure of the queue of currently unused buffers or a structure of the memory ring; and

a second memory to store instructions that, when applied to the processor, cause the processor to;

receive a request to read data from a memory ring data structure; and

issue a command, in response to the request, specifying a pointer to a memory location from which the data is to be removed, said pointer describing a structure of the memory ring;

read data from a memory ring address identified by the information describing a structure of the memory ring;

increment a pointer to a memory location where data is to be removed, said pointer describing a structure of the memory ring;

decrement the number of entries in the ring, said number of entries describing a structure of the memory ring; and

store the modified pointer and number of entries which describe a structure of the memory ring in a cache memory having entries to store information describing a structure of a queue of data buffers.

45. The apparatus of claim 44 wherein the command specifies a length field and wherein the number of entries in the ring is decremented by the specified length field.

46. The apparatus of claim 44 wherein the second memory further includes instructions to cause the processor to return an identifier to an issuing programming engine context, in response to the issued command, when the number of entries in the ring, said number of entries describing a structure of the memory ring is less than the specified length field.

47. A system comprising:

a source of data packets;

a destination of data packets; and

a device operating to transfer data packets from the source to the destination comprising;

a processor providing a queue manager;

a first memory coupled to the processor to store a queue of data buffers and at least one of a queue of currently unused buffers or a ring data structure;

a cache memory coupled to the processor to store information describing a structure of the queue of data buffers and information describing at least one of a structure of the queue of currently unused buffers or a structure of the memory ring; and

a second memory to store instructions that, when applied to the processor, cause the processor to;

remove a data buffer from a linked list of data buffers;

process information in the removed data buffer;

append the data buffer to a queue of currently unused buffers;

store information describing a structure of a queue of currently unused buffers and a queue of data buffers; and

modify information describing a structure of the queue of currently unused buffers.

48. The system of claim 47 wherein the storing is performed using the cache memory having entries to store information describing a structure of a queue of data buffers or a structure of a queue of currently unused buffers.

49. The system of claim 47 comprising the second memory storing instructions that, when applied to the processor, further cause the processor to store currently unused buffers using a linked list data structure.

50. The system of claim 47 wherein the data buffer comprises a network packet and wherein the network packet comprises a packet received in a network processor.

51. A system comprising:

a source of data packets;

a destination of data packets; and

a device operating to transfer data packets from the source to the destination comprising;

a processor providing a queue manager;

a first memory coupled to the processor to store a queue of data buffers and at least one of a queue of currently unused buffers or a ring data structure;

a cache memory coupled to the processor to store information describing a structure of a queue of data buffers and information describing at least one of a structure of the queue of currently unused buffers or a structure of the memory ring; and

a second memory to store instructions that, when applied to the processor, cause the processor to;

remove a currently unused buffer from a queue of currently unused buffers;

process a newly received data packet;

store the newly received data packet in the removed buffer;

append the removed buffer to a linked list of data buffers;

store information describing a structure of a queue of currently unused buffers and a queue of data buffers in a cache memory having entries to store information describing a structure of a queue of data buffers or a structure of a queue of currently unused buffers; and

modify information describing a structure of the queue of currently unused buffers.

52. The system of claim 51 comprising the second memory storing instructions that, when applied to the processor, further cause the processor to store currently unused buffers using a linked list data structure.

53. An article comprising a storage medium having stored thereon instructions that, when executed by a machine, cause the machine to:

check a content addressable memory for a tag corresponding to a queue of data buffers associated with a dequeue request;

access a queue descriptor, for the queue of data buffers, in a cache memory based on a result of the check;

remove a data buffer from the queue of data buffers using the queue descriptor from the cache memory

process information in the removed data buffer; and

append the data buffer to a queue of currently unused buffers in response to an enqueue request.

54. The article of claim 53 including instructions that, when executed by a machine, cause the machine to store currently unused buffers using a linked list data structure.

55. The article of claim 53 further including instructions that, when executed by a machine, cause the machine to store currently unused buffers using a stack data structure.

56. The article of claim 53 wherein the data buffer comprises a network packet and wherein the network packet comprises a packet received in a network processor.

57. The article of claim 53 further including instructions that, when executed by a machine, cause the machine to modify information describing a structure of the queue of currently unused buffers.

58. The article of claim 57 wherein the removing is performed in response to receiving a data packet in a receive pipeline appending and modifying are performed in response to receiving the enqueue request.

59. An article comprising a storage medium having stored thereon instructions that, when executed by a machine, cause the machine to:

remove a currently unused buffer from a queue of currently unused buffers in response to a dequeue request;

process a newly received data packet;

store the newly received data packet in the removed buffer;

check a content addressable memory for a tag corresponding to a queue of data buffers associated with an enqueue request;

access a queue descriptor, for the queue of data buffers, in a cache memory based on a result of the check;

append the removed buffer to the queue of data buffers using the queue descriptor from the cache memory.

60. The article of claim 59 further including instructions that, when executed by a machine, cause the machine to store currently unused buffers using a linked list data structure.

61. The article of claim 59 further including instructions that, when executed by a machine, cause the machine to store currently unused buffers using a stack data structure.

62. The article of claim 59 wherein the data buffer comprises a network packet and wherein the network packet comprises a packet received in a network processor.

63. The article of claim 59 further including instructions that, when executed by a machine, cause the machine to modify information describing a structure of the queue of currently unused buffers.

64. The article of claim 63 wherein the removing is performed in response to receiving a data packet in the receive pipeline, and storing and modifying are performed in response to receiving the dequeue request.

65. An article comprising a storage medium having stored thereon instructions that, when executed by a machine, cause the machine to:

receive a request to write data to a memory ring data structure; and

issue a command, in response to the request, the command specifying a pointer to a memory location where the data is to be inserted, said pointer describing a structure of the memory ring;

write data to a memory ring address identified by the information describing a structure of the memory ring;

increment a pointer to a memory location where data is to be inserted, said pointer describing a structure of the memory ring;

increment the number of entries in the ring, said number of entries describing a structure of the memory ring; and

store the modified pointer and number of entries which describe a structure of the memory ring in a cache memory having entries to store information describing a structure of a queue of data buffers or a structure of a queue of currently unused buffers.

66. The article of claim 65 wherein the command specifies a length field and wherein the number of entries in the ring is incremented by the specified length field.

67. The article of claim 65 further including instructions that, when executed by a machine, cause the machine to:

return to an issuing programming engine thread, in response to the issued command the number of entries in the ring, said number of entries describing a structure of the memory ring data structure; and

return a status bit that indicates whether sufficient memory is available to cause data to be written successfully to the memory ring address identified by a pointer to a the memory location where data is to be inserted, said pointer describing a structure of the memory ring.

68. The article of claim 65 wherein the command further specifies a memory address from which to obtain data that is to he written to the memory ring.

69. The article of claim 68 wherein the data contains bits representing an output message from an executing program.

70. The article of claim 69 wherein the bits include a programming engine identification and a context identification.

71. The article of claim 68 wherein the data contains bits representing a command address, said bits also include a programming engine identification and a context identification.

72. The article of claim 68 further including instructions that, when executed by a machine, cause the machine to:

write data to a memory ring address identified by the information describing a structure of the memory ring;

increment a pointer to the memory location where the data is to be inserted, said pointer describing a structure of the memory ring;

increment, by the specified length field, the number of entries in the ring, said number of entries describing a structure of the memory ring; and

store the modified pointer and number of entries describing a structure of the memory ring in a cache memory of which a subset of entries may be used to store information describing a queue of data buffers.

73. The article of claim 68 wherein the cache memory can be used to store information about multiple memory ring data structures.

74. An article comprising a storage medium having stored thereon instructions that, when executed by a machine, cause the machine to:

receive a request to read data from a memory ring data structure; and

issue a command, in response to the request, specifying a pointer to a memory location where the data is to be removed, said pointer describing a structure of the memory ring;

read data from a memory ring address identified by the information describing a structure of the memory ring;

increment a pointer to a memory location where data is to be removed, said pointer describing a structure of the memory ring;

decrement the number of entries in the ring, said number of entries describing a structure of the memory ring; and

store the modified pointer and number of entries describing a structure of the memory ring in a cache memory having entries to store information describing a structure of a queue of data buffers.

75. The article of claim 74 wherein the command specifies a length field and wherein the number of entries in the ring is decremented by the specified length field.

76. The article of claim 74 further including instructions that, when executed by a machine, cause the machine to return an identifier to an issuing programming engine context, in response to the issued command, when the number of entries in the ring, said number of entries describing a structure of the memory ring, is less than the specified length field.