Method for efficient buffer tag allocation

Abstract

A method and mechanism for allocating transaction tags. A request queue includes a counter whose value is used to identify a corresponding tag of a plurality of unique tags. The queue is configured to increment the counter and use the current count value to index into a buffer pool. If the tag corresponding to the currently indexed buffer pool entry is available for allocation, a determination is made as to whether the currently identified tag is corresponds to the last tag which has been de-allocated. If the identified available buffer pool entry/tag matches the last tag which was de-allocated, the queue continues the process of counter incrementation and searching of the buffer pool for an available entry to select for allocation. When a request is received, the currently selected tag is allocated. Additional circuitry may be used to identify a fallback tag in the event a request is received while the queue is searching for a tag. In such an event, the fallback tag may be allocated.

1. A method for allocating a tag, said method comprising:
 incrementing a counter responsive to determining a tag of a plurality of unique tags has not been selected for allocation; 
 utilizing a value of said counter to identify a first tag of said tags; 
 determining whether said first tag is available for allocation; 
 repeating said incrementing, utilizing, and determining if said first tag is not available for allocation; and 
 selecting said first tag for allocation if said first tag is available for allocation and said first tag does not correspond to a tag most recently de-allocated. 
 
     
     
       2. The method as recited in  claim 1 , wherein said method further comprises selecting said first tag for allocation in response to detecting said first tag is available for allocation, said first tag corresponds to a tag most recently de-allocated, and said first tag is an only tag of said tags available for allocation. 
     
     
       3. The method as recited in  claim 1 , further comprising repeating said incrementing, utilizing, and determining in response to detecting said first tag is available for allocation, said first tag corresponds to a tag most recently de-allocated, and said first tag is not an only tag of said tags available for allocation. 
     
     
       4. The method as recited in  claim 3 , further comprising storing said first tag as a fallback tag in response to detecting said first tag is available for allocation, said first tag corresponds to a tag most recently de-allocated, and said first tag is not an only tag of said tags available for allocation. 
     
     
       5. The method as recited in  claim 1 , further comprising determining a fallback tag concurrently with said incrementing, utilizing, and determining. 
     
     
       6. The method as recited in  claim 1 , further comprising:
 detecting a received transaction; and 
 allocating a tag for said transaction in response to determining said transaction corresponds to a request. 
 
     
     
       7. The method as recited in  claim 6 , wherein said tag allocated for said request corresponds to said first tag. 
     
     
       8. The method as recited in  claim 7 , wherein in response to detecting a tag has not been selected for allocation, said tag allocated for said request corresponds to a fallback tag. 
     
     
       9. The method as recited in  claim 6 , wherein in response to detecting said transaction corresponds to a completion indication, said method further comprises:
 de-allocating a tag which corresponds to the received transaction; and 
 storing an indication that said de-allocated tag is a tag most recently de-allocated. 
 
     
     
       10. A request queue comprising:
 a buffer pool including a plurality of entries, each said entry being indicative of a unique tag; and 
 a control unit, wherein said control unit is configured to: 
 increment a counter responsive to determining no tag of said entries has been selected for allocation; 
 utilize a value of said counter to identify a first entry of said entries; 
 determine whether a first tag corresponding to said first entry is available for allocation; 
 repeat said incrementing, utilizing, and determining in response to detecting said first tag is not available for allocation; and 
 select said first tag for allocation in response to detecting said first tag is available for allocation and said first tag does not correspond to a tag most recently de-allocated. 
 
     
     
       11. The queue as recited in  claim 10 , wherein said control unit is further configured to select said first tag for allocation in response to detecting said first tag is available for allocation, said first tag corresponds to a tag most recently de-allocated, and said first tag is an only tag of said tags available for allocation. 
     
     
       12. The queue as recited in  claim 10 , wherein said control unit is further configured to repeat said incrementing, utilizing, and determining in response to detecting said first tag is available for allocation, said first tag corresponds to a tag most recently de-allocated, and said first tag is not an only tag corresponding to said entries which is available for allocation. 
     
     
       13. The queue as recited in  claim 12 , wherein said control unit is further configured to store said first tag as a fallback tag in response to detecting said first tag is available for allocation, said first tag corresponds to a tag most recently de-allocated, and said first tag is not an only tag of said tags available for allocation. 
     
     
       14. The queue recited in  claim 10 , wherein said control unit is further configured to determine a fallback tag concurrently with said incrementing, utilizing, and determining. 
     
     
       15. The queue as recited in  claim 10 , wherein said control unit is further configured to:
 detect a received transaction; and 
 allocate a tag for said transaction in response to determining said transaction corresponds to a request. 
 
     
     
       16. The queue as recited in  claim 15 , wherein said tag allocated for said request corresponds to said first tag. 
     
     
       17. The queue as recited in  claim 16 , wherein in response to detecting a tag has not been selected for allocation, said tag allocated for said request corresponds to a fallback tag. 
     
     
       18. The queue as recited in  claim 15 , wherein in response to detecting said transaction corresponds to a completion indication, said control unit is further configured to:
 de-allocate a tag which corresponds to the received transaction; and 
 store an indication that said de-allocated tag is a tag most recently de-allocated. 
 
     
     
       19. The queue as recited in  claim 10 , wherein said queue is coupled to receive requests from one or more bus mastering devices. 
     
     
       20. A system comprising:
 a bus master including a bus interface coupled to a bus; and 
 a request queue coupled to said bus master via said bus; 
 wherein said request queue is configured to: 
 increment a counter responsive to determining no tag of said entries has been selected for allocation; 
 utilize a value of said counter to identify a first entry of said entries; 
 determine whether a first tag corresponding to said first entry is available for allocation; 
 repeat said incrementing, utilizing, and determining in response to detecting said first tag is not available for allocation; and 
 select said first tag for allocation in response to detecting said first tag is available for allocation and said first tag does not correspond to a tag most recently de-allocated. 
 
     
     
       21. The system as recited in  claim 20 , wherein said queue is further configured to select said first tag for allocation in response to detecting said first tag is available for allocation, said first tag corresponds to a tag most recently de-allocated, and said first tag is an only tag of said tags available for allocation. 
     
     
       22. The system as recited in  claim 20 , wherein said queue is further configured to repeat said incrementing, utilizing, and determining in response to detecting said first tag is available for allocation, said first tag corresponds to a tag most recently de-allocated, and said first tag is not an only tag corresponding to said entries which is available for allocation. 
     
     
       23. The system as recited in  claim 22 , wherein said queue is further configured to store said first tag as a fallback tag in response to detecting said first tag is available for allocation, said first tag corresponds to a tag most recently de-allocated, and said first tag is not an only tag of said tags available for allocation. 
     
     
       24. The system as recited in  claim 20 , wherein said queue is further configured to:
 detect a received transaction; and 
 allocate a tag for said transaction in response to determining said transaction corresponds to a request.