Granted Patent B2

US 7,093,099 · App. 10/249,359 · Granted Aug 15, 2006

Abstract

Claims (84)

1. 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, the lookup cache including at least one 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;

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 hashing engine, receiving the input key, for generating the key derivative from the input key; and

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.

2. The processor of claim 1 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.

3. The processor of claim 2 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 that 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.

4. The processor of claim 3 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.

5. The processor of claim 3 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 from 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.

6. The processor of claim 1 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.

7. The processor of claim 6 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.

8. The processor of claim 1 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.

9. The processor of claim 8 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.

10. The processor of claim 1 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.

11. The processor of claim 1 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.

12. The processor of claim 1 further comprising:

an arithmetic-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.

13. The processor of claim 1 wherein the lookup instruction further comprises a section field that indicates one of the sections of the lookup cache to search;

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

14. The processor of claim 1 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 a third-level of the lookup cache that contains additional data, whereby longer data fields are stored in the second and third levels.

15. 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, wherein the lookup cache includes at least one 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;

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;

utilizing a hash engine to hash the input key and thereby 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.

16. The computerized method of claim 15 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.

17. The computerized method of claim 16 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.

18. The computerized method of claim 15 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.

19. 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.

20. The specialized processor of claim 19 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.

Assignments (7)