Native lookup instruction for file-access processor searching a three-level lookup cache for variable-length keys

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.

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.