From e1c07039ae1ca0bc0e00c31aa5630a88f6a7a025 Mon Sep 17 00:00:00 2001 From: Paul Durrant Date: Thu, 30 May 2019 11:41:10 +0100 Subject: [PATCH] Unconfuse XENBUS_CACHE_SLAB Allocated field The purpose of the the field has become confused. It is actually an allocation mask, but CacheInsertSlab() treats it as if it is an allocation count. This patch renames the allocation mask to 'Mask', the 'Count' field to 'MaximumOccupancy' (to better describe its purpose) and introduces a new 'CurrentOccupancy' counter. This patch also makes sure the allocation mask can cover 'MaximumOccupancy' and, since both CacheGetObjectFromSlab() and CachePutObjectToSlab() must now be called under lock, it swaps the atomic bit-mask operations for non-atomic mask manipulation. Signed-off-by: Paul Durrant --- src/xenbus/cache.c | 130 +++++++++++++++++++++++++++++++++++++-------- 1 file changed, 108 insertions(+), 22 deletions(-) diff --git a/src/xenbus/cache.c b/src/xenbus/cache.c index 877b395..688c3d9 100644 --- a/src/xenbus/cache.c +++ b/src/xenbus/cache.c @@ -59,8 +59,9 @@ typedef struct _XENBUS_CACHE_SLAB { ULONG Magic; PXENBUS_CACHE Cache; LIST_ENTRY ListEntry; - ULONG Count; - ULONG Allocated; + USHORT MaximumOccupancy; + USHORT CurrentOccupancy; + ULONG *Mask; UCHAR Buffer[1]; } XENBUS_CACHE_SLAB, *PXENBUS_CACHE_SLAB; @@ -216,7 +217,7 @@ CacheInsertSlab( Next = CONTAINING_RECORD(Cursor, XENBUS_CACHE_SLAB, ListEntry); - if (Next->Allocated > Slab->Allocated) { + if (Next->CurrentOccupancy > Slab->CurrentOccupancy) { INSERT_BEFORE(Cursor, &Slab->ListEntry); return; } @@ -239,6 +240,7 @@ CacheCreateSlab( LARGE_INTEGER LowAddress; LARGE_INTEGER HighAddress; LARGE_INTEGER Boundary; + ULONG Size; LONG Index; NTSTATUS status; @@ -272,14 +274,21 @@ CacheCreateSlab( Slab->Magic = XENBUS_CACHE_SLAB_MAGIC; Slab->Cache = Cache; - Slab->Count = Count; + Slab->MaximumOccupancy = (USHORT)Count; - for (Index = 0; Index < (LONG)Slab->Count; Index++) { + Size = P2ROUNDUP(Count, BITS_PER_ULONG); + Size /= 8; + + Slab->Mask = __CacheAllocate(Size); + if (Slab->Mask == NULL) + goto fail3; + + for (Index = 0; Index < (LONG)Slab->MaximumOccupancy; Index++) { PVOID Object = (PVOID)&Slab->Buffer[Index * Cache->Size]; status = __CacheCtor(Cache, Object); if (!NT_SUCCESS(status)) - goto fail3; + goto fail4; } CacheInsertSlab(Cache, Slab); @@ -287,8 +296,8 @@ CacheCreateSlab( return Slab; -fail3: - Error("fail3\n"); +fail4: + Error("fail4\n"); while (--Index >= 0) { PVOID Object = (PVOID)&Slab->Buffer[Index * Cache->Size]; @@ -296,6 +305,11 @@ fail3: __CacheDtor(Cache, Object); } + __CacheFree(Slab->Mask); + +fail3: + Error("fail3\n"); + MmFreeContiguousMemory(Slab); fail2: @@ -316,22 +330,85 @@ CacheDestroySlab( { LONG Index; - ASSERT3U(Slab->Allocated, ==, 0); + ASSERT3U(Slab->CurrentOccupancy, ==, 0); - ASSERT3U(Cache->Count, >=, Slab->Count); - Cache->Count -= Slab->Count; + ASSERT3U(Cache->Count, >=, Slab->MaximumOccupancy); + Cache->Count -= Slab->MaximumOccupancy; RemoveEntryList(&Slab->ListEntry); - Index = Slab->Count; + Index = Slab->MaximumOccupancy; while (--Index >= 0) { PVOID Object = (PVOID)&Slab->Buffer[Index * Cache->Size]; __CacheDtor(Cache, Object); } + __CacheFree(Slab->Mask); + MmFreeContiguousMemory(Slab); } +static FORCEINLINE ULONG +__CacheMaskScan( + IN ULONG *Mask, + IN ULONG Maximum + ) +{ + ULONG Size; + ULONG Index; + + Size = P2ROUNDUP(Maximum, BITS_PER_ULONG); + Size /= sizeof (ULONG); + ASSERT(Size != 0); + + for (Index = 0; Index < Size; Index++) { + ULONG Free = ~Mask[Index]; + ULONG Bit; + + if (!_BitScanForward(&Bit, Free)) + continue; + + Bit += Index * BITS_PER_ULONG; + return Bit; + } + + BUG("CACHE SCAN FAILED"); + return ~0u; +} + +static FORCEINLINE VOID +__CacheMaskSet( + IN ULONG *Mask, + IN ULONG Bit + ) +{ + ULONG Index = Bit / BITS_PER_ULONG; + + Mask[Index] |= 1u << (Bit % BITS_PER_ULONG); +} + +static FORCEINLINE BOOLEAN +__CacheMaskTest( + IN ULONG *Mask, + IN ULONG Bit + ) +{ + ULONG Index = Bit / BITS_PER_ULONG; + + return (Mask[Index] & (1u << (Bit % BITS_PER_ULONG))) ? TRUE : FALSE; +} + +static FORCEINLINE VOID +__CacheMaskClear( + IN ULONG *Mask, + IN ULONG Bit + ) +{ + ULONG Index = Bit / BITS_PER_ULONG; + + Mask[Index] &= ~(1u << (Bit % BITS_PER_ULONG)); +} + // Must be called with lock held static PVOID CacheGetObjectFromSlab( @@ -339,20 +416,25 @@ CacheGetObjectFromSlab( ) { PXENBUS_CACHE Cache; - ULONG Free; ULONG Index; - ULONG Set; + PVOID Object; Cache = Slab->Cache; - Free = ~Slab->Allocated; - if (!_BitScanForward(&Index, Free) || Index >= Slab->Count) + ASSERT3U(Slab->CurrentOccupancy, <=, Slab->MaximumOccupancy); + if (Slab->CurrentOccupancy == Slab->MaximumOccupancy) return NULL; - Set = InterlockedBitTestAndSet((LONG *)&Slab->Allocated, Index); - ASSERT(!Set); + Index = __CacheMaskScan(Slab->Mask, Slab->MaximumOccupancy); + + __CacheMaskSet(Slab->Mask, Index); + Slab->CurrentOccupancy++; + + Object = (PVOID)&Slab->Buffer[Index * Cache->Size]; + ASSERT3U(Index, ==, (ULONG)((PUCHAR)Object - &Slab->Buffer[0]) / + Cache->Size); - return (PVOID)&Slab->Buffer[Index * Cache->Size]; + return Object; } // Must be called with lock held @@ -368,9 +450,13 @@ CachePutObjectToSlab( Cache = Slab->Cache; Index = (ULONG)((PUCHAR)Object - &Slab->Buffer[0]) / Cache->Size; - BUG_ON(Index >= Slab->Count); + BUG_ON(Index >= Slab->MaximumOccupancy); + + ASSERT(Slab->CurrentOccupancy != 0); + --Slab->CurrentOccupancy; - (VOID) InterlockedBitTestAndReset((LONG *)&Slab->Allocated, Index); + ASSERT(__CacheMaskTest(Slab->Mask, Index)); + __CacheMaskClear(Slab->Mask, Index); } static PVOID @@ -465,7 +551,7 @@ CachePut( CachePutObjectToSlab(Slab, Object); - if (Slab->Allocated == 0) { + if (Slab->CurrentOccupancy == 0) { CacheDestroySlab(Cache, Slab); } else { /* Re-insert to keep slab list ordered */ -- 2.39.5