Native Lookup Instruction for File-Access Processor Searching a Three-Level Lookup Cache for Variable-Length Keys

• US 20040117600A1
• Filed: 04/02/2003
• Published: 06/17/2004
• Est. Priority Date: 12/12/2002
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Nexsil Communications Incorporated
• Inventors: Mertoguno, J. Sukarno, Tripathy, Tarun Kumar, Kharidia, Mehul, Mittal, Millind, Bodas, Amod
• Granted Patent: US 7,093,099 B2
• Time in Patent Office: Days
• US Class Current: 712/210
• CPC Class Codes: H04L 69/10 Streamlined, light-weight or high-speed protocols, e.g. express transfer protocol [XTP] or byte stream
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/161 Implementation details of TCP/IP or UDP/IP stack architecture; Specification of modified or new header fields
• CPC Class Codes: H04L 69/165 Combined use of TCP and UDP protocols; selection criteria therefor
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A processor natively executes lookup instructions. The lookup instruction is decoded to determine which general-purpose register (GPR) contains a pointer to a lookup key in a buffer. A variable-length key is read from the buffer and hashed to generate an index into a first-level cache and a hashed tag. An address of a bucket of entries for the index is generated and tags from these entries are read and compared to the hashed tag. When an entry matches the hashed tag, a second-level entry is read. A stored key from the second-level entry is compared to the input key to determine a match. The addresses of the matching second-level and first-level entries are written to GPR'"'"'s specified by operands decoded from the lookup instruction. When the key or entry data is long, the second-level entry also contains a pointer to a key extension or data extension in a third-level cache.

Claims

1. A micro-processor comprising:

an instruction decoder for decoding instructions in a program being executed by the processor, the instructions including a lookup instruction;

a register file containing registers that store operands operated upon by the instructions, the registers being identified by operand fields in the instructions decoded by the instruction decoder;

a memory-access unit for accessing entries of a lookup cache;

an address generator for generating an address to the memory-access unit;

a comparator for comparing stored keys read from the entries to an input key;

wherein the input key is a variable-length operand;

a lookup unit, activated by the instruction decoder when the lookup instruction is decoded, for performing a lookup operation indicated by the lookup instruction, the lookup operation searching the lookup cache for a matching entry that has a stored key that matches the input key,

whereby the lookup instruction is decoded and executed by the processor.

2. A processor comprising:

an instruction decoder for decoding instructions in a program being executed by the processor, the instructions including a lookup instruction;

a register file containing registers that store operands operated upon by the instructions, the registers being identified by operand fields in the instructions decoded by the instruction decoder;

a memory-access unit for accessing first-level entries and second-level entries of a lookup cache;

an address generator for generating a first-level address and a second-level address to the memory-access unit;

a comparator for comparing tags read from the first-level entries to a key derivative and for comparing stored keys read from the second-level entries to an input key;

wherein the input key is a variable-length operand while the key derivative is generated from the input key;

a lookup unit, activated by the instruction decoder when the lookup instruction is decoded, for performing a lookup operation indicated by the lookup instruction, the lookup operation searching the lookup cache for a matching second-level entry that has a stored key that matches the input key,

whereby the lookup instruction is decoded and executed by the processor.

3. The processor of claim 2 wherein the lookup operation comprises:

reading the input key at a location indicated by the pointer operand in the register identified by the operand field in the lookup instruction;

activating the address generator to generate the first-level address from the input key;

activating the memory-access unit to read a plurality of first-level entries at the first-level address;

activating the comparator to compare tags read from the plurality of first-level entries to the key derivative;

activating the address generator to generate the second-level address for a second-level entry that corresponds to a first-level entry that the comparator indicates has a tag that matches the key derivative;

activating the memory-access unit to read a second-level entry at the second-level address;

activating the comparator to compare a stored key read from the second-level entry to the input key to determine a key hit; and

when the key hit is determined, writing the second-level address to a result register and terminating execution of the lookup instruction,

whereby lookup instructions are executed by the processor.

4. The processor of claim 3 further comprising:

an execution buffer for storing variable-length operands, wherein operands in the register file include pointer operands that indicate locations of the variable-length operands in the execution buffer;

wherein the register file contains a plurality of fixed-size registers that can each store an operand, a pointer operand, or a result;

wherein the result register is indicated by a result field in the lookup instruction that is decoded to locate the result register in the register file;

wherein the location of the variable-length operand in the execution buffer is indicated by a first operand field that indicates a first register in the register file than contains the operand pointer to a start of the input key;

wherein a length of the input key is indicated by a length value stored in a register in the register file that is indicated by a second operand field in the lookup instruction or indicated as a predetermined offset from the first register.

5. The processor of claim 4 wherein the result field directly indicates a second result register that is written with the first-level address for a matching entry while the second-level address is written to the result register which is indirectly indicated by the result field.

6. The processor of claim 4 wherein the lookup instruction further comprises a section field that indicates a section of the lookup cache to search;

wherein the section field causes the address generator to address a different section of the lookup cache.

7. The processor of claim 6 wherein different sections of the lookup cache include one or more of:

an inode section that contains inode entries and file attributes;

a name cache section that stores file-name entries;

a page cache section that stores page entries; and

an export cache section that stores export entries.

8. The processor of claim 4 further comprising:

a hashing engine, receiving the input key, for generating the key derivative from the input key.

9. The processor of claim 8 wherein the hashing engine generates a fixed-length hash of the input key which is a variable-length operand;

wherein a first portion of the fixed-length hash is an index that is input to the address generator to select a bucket of first-level entries from a plurality of buckets, wherein each bucket is addressed by a different value of the first portion of the fixed-length hash and all entries in a bucket have a same index, whereby a hashed index selects the bucket of first-level entries.

10. The processor of claim 9 wherein a second portion of the fixed-length hash that does not include the first portion is the key derivative that is compared to the tags stored in the first-level entries,

whereby hashed tags are compared.

11. The processor of claim 4 wherein the instruction decoder further comprises a flavor decoder that decodes a flavor field from the lookup instruction, the flavor field being decoded to select a sub-operation performed by the lookup unit when performing the lookup operation.

12. The processor of claim 11 wherein the first-level entries each further comprise a counter that is incremented by execution of a lookup instruction with an increment sub-operation indicated by the flavor field;

wherein the counter is decremented by execution of a lookup instruction with a decrement sub-operation indicated by the flavor field,

whereby the counter in the first-level entry is incremented and decremented.

13. The processor of claim 4 wherein the first-level entries each comprise the tag and a valid bit that indicates validity of the first-level entry, and a least-recently-used LRU field indicating relative age of the first-level entry.

14. The processor of claim 4 wherein the first-level entries each comprise the tag and an update bit that is set by the lookup unit when a first-level entry is being updated and cleared once the first-level entry has been updated.

15. The processor of claim 4 further comprising:

an unit-logic-unit (ALU) for executing add instructions and logic instructions decoded by the instruction decoder;

wherein the comparator and the address generator are part of the ALU that also executes add and logic instructions.

16. The processor of claim 4 wherein the second-level entry comprises:

a length field that indicates a length of the stored key;

a key pointer that points to a key extension in a third-level of the lookup cache;

a key field that contains the stored key or a first portion of the stored key;

wherein the stored key is generated by combining the first portion of the stored key form the key field with the key extension from the third-level of the lookup cache when the length field contains a value greater that a length of the key field,

whereby longer stored keys are stored in the second and third levels.

17. The processor of claim 4 wherein the second-level entry comprises:

a data field that contains data used by an application that looks up the second-level entry; and

a data pointer that points to a data extension in the third-level of the lookup cache that contains additional data,

whereby longer data fields are stored in the second and third levels.

18. A computerized method for executing a lookup instruction comprising:

decoding instructions for execution by a processor including decoding the lookup instruction that contains an opcode that specifies a lookup operation on a lookup cache;

decoding a first operand field in the lookup instruction and a result field in the lookup instruction, the first operand field specifying a first register that contains a key pointer to an input key in a buffer while the result field specifies a result register that a result of the lookup operation is to be written to;

reading an input key from a buffer at a location indicated by the key pointer;

hashing the input key to generate a hashed key;

generating an index from a first portion the hashed key and a hashed tag from a second portion of the hashed key;

generating a bucket address of a bucket of first-level entries in a first-level cache of the lookup cache;

reading a plurality of stored tags from first-level entries in the bucket addressed by the bucket address;

comparing the plurality of stored tags from the bucket to the hashed key to find a matching first-level entry in the bucket that has a stored tag that matches the hashed key;

generating a second-level address for a corresponding second-level entry that corresponds to the matching first-level entry;

reading a stored key from the corresponding second-level entry using the second-level address to locate the corresponding second-level entry;

comparing the stored key read from the corresponding second-level entry to the input key to determine a key match; and

when the key match is found, writing the second-level address to the result register or to a second result register predetermined by the result field in the lookup instruction;

whereby the lookup instruction is decoded and executed to find the second-level address for a key match.

19. The computerized method of claim 18 further comprising:

reading a key length from a second register, the second register predetermined by the first operand field or decoded from a second operand field in the lookup instruction;

wherein reading the input key from the buffer comprises reading a number of bits from the buffer determined by the key length from the location indicated by the key pointer;

wherein comparing the stored key comprises comparing a number of bits indicated by the key length or validating a number of compared bits indicated by the key length,

whereby variable-length input keys are read and compared.

20. The computerized method of claim 19 further comprising:

reading a key-extension pointer from the corresponding second-level entry;

when the key-extension pointer has a specified value, reading a third-level key extension at a location indicated by a key-extension pointer;

combining a partial key read from the corresponding second-level entry with the third-level key extension to generate the stored key for comparison to the input key when the key-extension pointer has the specified value,

whereby long keys are stored in a third-level extension.

21. The computerized method of claim 18 further comprising:

decoding a variant field in the lookup instruction that indicates a variant of the lookup instruction that performs a variant operation;

executing the variant operation, the variant operation incrementing or decrementing a counter stored in the first-level entry, invalidating a valid bit in the first-level entry, or copying data to or from the corresponding second-level entry when the key match is found, or performing an update when no key match is found,

whereby variants of the lookup operation are decoded and performed.

22. A specialized processor comprising:

decode means for decoding instructions including decoding a lookup instruction that contains an opcode that specifies a lookup operation on a lookup table;

a register file containing registers accessible by execution of instructions decoded by the decode means;

operand decode means for decoding a first operand field in the lookup instruction and a result field in the lookup instruction, the first operand field specifying a first register in the register file that contains a key pointer to an input key in a buffer and the result field specifying a result register in the register file that a result of the lookup operation is to be written to;

buffer means for storing variable-length operands including an input key that is read from the buffer means at a location indicated by the key pointer;

hash means for hashing the input key to generate a hashed key, the hashed key having an index and a hashed tag;

first address means, receiving the index, for generating a bucket address of a bucket of first-level entries in a first-level cache of the lookup table;

first match means for reading a plurality of stored tags from first-level entries in the bucket addressed by the bucket address and for comparing the plurality of stored tags from the bucket to the hashed key to find a matching first-level entry in the bucket that has a stored tag that matches the hashed key;

second address means for generating a second-level address for a corresponding second-level entry that corresponds to the matching first-level entry;

second match means for reading a stored key from the corresponding second-level entry using the second-level address to locate the corresponding second-level entry, and for comparing the stored key read from the corresponding second-level entry to the input key to determine a key match; and

result means, responsive to the key match, for writing the bucket address to the result register and for writing the second-level address to a register that follows the result register;

whereby the lookup instruction is decoded and executed to find the key match.

23. The specialized processor of claim 22 further comprising:

key combining means, responsive to a key extension field in the corresponding second-level entry, for reading a key extension in a third-level of the lookup table at a location indicated by a key-extension pointer field in the corresponding second-level entry when the stored key is larger than a limited key length for a second-level of the lookup table;

the key combining means forming the stored key by combining the key extension with a partial key read from the corresponding second-level entry.