Re: [PATCH 2/2] cache: Dont linearly scan magazine slots for objects

[Tu Dinh <ngoc-tu.dinh@xxxxxxxxxx>]

On 06/08/2026 09:46, Owen Smith wrote:
> Add an occupancy count to the cache magazine, and use this as an index
> into the magazine slots for the current get/put location.
> This avoids a linear scan of magazine slots when looking for a valid
> slot during CacheGetObjectFromMagazine or CachePutObjectToMagazine,
> reducing the algorithm from O(n) to O(1).
> 
> Signed-off-by: Owen Smith <owen.smith@xxxxxxxxxx>

Reviewed-by: Tu Dinh <ngoc-tu.dinh@xxxxxxxxxx>

> ---
>   src/xenbus/cache.c | 34 +++++++++++++++-------------------
>   1 file changed, 15 insertions(+), 19 deletions(-)
> 
> diff --git a/src/xenbus/cache.c b/src/xenbus/cache.c
> index 81cd3eb..90aea08 100644
> --- a/src/xenbus/cache.c
> +++ b/src/xenbus/cache.c
> @@ -50,6 +50,7 @@ RtlRandomEx (
>   #define XENBUS_CACHE_MAGAZINE_SLOTS   6
>   
>   typedef struct _XENBUS_CACHE_MAGAZINE {
> +    ULONG   Count;
>       PVOID   Slot[XENBUS_CACHE_MAGAZINE_SLOTS];
>   } XENBUS_CACHE_MAGAZINE, *PXENBUS_CACHE_MAGAZINE;
>   
> @@ -167,20 +168,16 @@ CacheGetObjectFromMagazine(
>       _In_ PXENBUS_CACHE_MAGAZINE Magazine
>       )
>   {
> -    ULONG                       Index;
> -
> -    for (Index = 0; Index < XENBUS_CACHE_MAGAZINE_SLOTS; Index++) {
> -        PVOID   Object;
> +    PVOID                       Object;
>   
> -        if (Magazine->Slot[Index] != NULL) {
> -            Object = Magazine->Slot[Index];
> -            Magazine->Slot[Index] = NULL;
> +    if (Magazine->Count == 0)
> +        return NULL;
>   
> -            return Object;
> -        }
> -    }
> +    Object = Magazine->Slot[--Magazine->Count];
> +    Magazine->Slot[Magazine->Count] = NULL;
>   
> -    return NULL;
> +    ASSERT(Object != NULL);
> +    return Object;
>   }
>   
>   static NTSTATUS
> @@ -189,16 +186,15 @@ CachePutObjectToMagazine(
>       _In_ PVOID                  Object
>       )
>   {
> -    ULONG                       Index;
> +    ASSERT(Object != NULL);
>   
> -    for (Index = 0; Index < XENBUS_CACHE_MAGAZINE_SLOTS; Index++) {
> -        if (Magazine->Slot[Index] == NULL) {
> -            Magazine->Slot[Index] = Object;
> -            return STATUS_SUCCESS;
> -        }
> -    }
> +    if (Magazine->Count == XENBUS_CACHE_MAGAZINE_SLOTS)
> +        return STATUS_UNSUCCESSFUL;
> +
> +    ASSERT(Magazine->Slot[Magazine->Count] == NULL);
> +    Magazine->Slot[Magazine->Count++] = Object;
>   
> -    return STATUS_UNSUCCESSFUL;
> +    return STATUS_SUCCESS;
>   }
>   
>   static PXENBUS_CACHE_MASK



--
Ngoc Tu Dinh | Vates XCP-ng Developer

XCP-ng & Xen Orchestra - Vates solutions

web: https://vates.tech