System and method for removing hash table entries

A data processing system, comprising:

• a memory configured to store a hash table in linear address space defined by a first extreme address and a second extreme address, the hash table having a plurality of hash entry locations;
• a hash table management circuit configured to create hash entries at the hash entry locations, wherein each created hash entry that has a unique hash value is marked as a head entry that is an initial entry of a hash chain, and each created hash entry that has the same hash value as an existing hash chain is linked to the existing hash chain;
• a hash table cleanup circuit configured to, upon receiving a cleanup request, identify each head entry sequentially in linear address order, and to remove all hash entries from the hash chain associated with the currently identified head entry that have been marked for deletion before identifying the next head entry;
• wherein the hash table management circuit is to further lock each entry of a hash chain based upon a lock request of an entity to prevent modification, and the hash table cleanup circuit is to provide the lock request to the hash table management circuit to lock the hash chain prior to removing hash entries from the hash chain, and
• wherein the hash table cleanup circuit is to further provide a request to the hash table management circuit to unlock the hash chain of the identified head entry prior to removing each hash entries from the hash chain, and to request the hash table management circuit to lock the hash chain subsequent to removing each hash entry before identifying a next head entry.

A method, comprising:

• generating a plurality of hash chains at a hash table of a data processor, each hash chain having a unique hash value, including a first hash chain and a second hash chain, each hash chain of the plurality of hash chains having a plurality of hash table entries;
• calculating a hash value, at a memory controller of a data processor system, for a new hash table entry based upon first information;
• sequentially evaluating physical addresses of the hash table to determine if a physical address being evaluated stores a head entry of a hash chain, including locking each physical address, and its associated hash chain entries, prior to determining the head entry is stored;
• in response to determining the physical address being evaluated stores the head entry of a current hash chain:
• unlocking the current hash chain;
• removing, by a cleanup routine, each hash table entry marked for deletion of the current hash chain;
• and
• subsequent to removing each hash table entry marked for deletion, locking the current hash chain.

A method comprising:

• in response to a request to cleanup a hash table of a data processor device, setting a current address to be a first extreme address of the hash table;
• incrementing the current address in linear sequential order from the first extreme address of the hash table to a second extreme address of the hash table to step through a plurality of hash table address entry locations;
• processing each entry location, before each increment of the current address, by:
• requesting that all hash table entries associated with the current address be locked to prevent modification;
• if a head entry is stored at the current address, stepping through each entry of a hash chain associated with the head entry and removing those entries of the hash chain that are marked for deletion, wherein removing an entry comprises requesting that all hash table entries associated with the current address be unlocked to allow modification, removing the entry from the hash chain, and requesting that all hash table entries associated with the current address be locked, otherwise, if the head entry is not stored at the current address, requesting that all hash table entries associated with the current address be unlocked to allow modification.