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

[Owen Smith <owen.smith@xxxxxxxxxx>]

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>
---
 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
-- 
2.51.2.windows.1