reactos/ntoskrnl/ex/lookas.c

   1 /* $Id$
   2  *
   3  * COPYRIGHT:       See COPYING in the top level directory
   4  * PROJECT:         ReactOS kernel
   5  * FILE:            ntoskrnl/ex/lookas.c
   6  * PURPOSE:         Lookaside lists
   7  * PROGRAMMERS:     David Welch (welch@mcmail.com)
   8  *                  Casper S. Hornstrup (chorns@users.sourceforge.net)
   9  * TODO:            Use InterlockedXxxEntrySList for binary compatibility
  10  * UPDATE HISTORY:
  11  *   22-05-1998 DW  Created
  12  *   02-07-2001 CSH Implemented lookaside lists
  13  */
  14
  15 /* INCLUDES *****************************************************************/
  16
  17 #include <ntoskrnl.h>
  18 #define NDEBUG
  19 #include <internal/debug.h>
  20
  21 /* GLOBALS *******************************************************************/
  22
  23 LIST_ENTRY ExpNonPagedLookasideListHead;
  24 KSPIN_LOCK ExpNonPagedLookasideListLock;
  25
  26 LIST_ENTRY ExpPagedLookasideListHead;
  27 KSPIN_LOCK ExpPagedLookasideListLock;
  28
  29 PLOOKASIDE_MINMAX_ROUTINE ExpMinMaxRoutine;
  30
  31 #define LookasideListLock(l)(&(l->Obsoleted))
  32
  33 /* FUNCTIONS *****************************************************************/
  34
  35 static
  36 inline
  37 PSINGLE_LIST_ENTRY
  38  PopEntrySList(
  39         PSLIST_HEADER   ListHead
  40         )
  41 {
  42         PSINGLE_LIST_ENTRY ListEntry;
  43
  44         ListEntry = ListHead->Next.Next;
  45         if (ListEntry!=NULL)
  46         {
  47                 ListHead->Next.Next = ListEntry->Next;
  48     ListHead->Depth++;
  49     ListHead->Sequence++;
  50   }
  51         return ListEntry;
  52 }
  53
  54
  55 static
  56 inline
  57 VOID
  58 PushEntrySList (
  59         PSLIST_HEADER   ListHead,
  60         PSINGLE_LIST_ENTRY      Entry
  61         )
  62 {
  63         Entry->Next = ListHead->Next.Next;
  64         ListHead->Next.Next = Entry;
  65   ListHead->Depth++;
  66   ListHead->Sequence++;
  67 }
  68
  69
  70 VOID ExpDefaultMinMax(
  71   POOL_TYPE PoolType,
  72   ULONG Size,
  73   PUSHORT MinimumDepth,
  74   PUSHORT MaximumDepth)
  75 /*
  76  * FUNCTION: Determines the minimum and maximum depth of a new lookaside list
  77  * ARGUMENTS:
  78  *   Type         = Type of executive pool
  79  *   Size         = Size in bytes of each element in the new lookaside list
  80  *   MinimumDepth = Buffer to store minimum depth of the new lookaside list in
  81  *   MaximumDepth = Buffer to store maximum depth of the new lookaside list in
  82  */
  83 {
  84   /* FIXME: Could probably do some serious computing here */
  85   if ((PoolType == NonPagedPool) ||
  86     (PoolType == NonPagedPoolMustSucceed))
  87   {
  88     *MinimumDepth = 10;
  89     *MaximumDepth = 100;
  90   }
  91   else
  92   {
  93     *MinimumDepth = 20;
  94     *MaximumDepth = 200;
  95   }
  96 }
  97
  98
  99 PVOID STDCALL
 100 ExpDefaultAllocate(POOL_TYPE PoolType,
 101                    ULONG NumberOfBytes,
 102                    ULONG Tag)
 103 /*
 104  * FUNCTION: Default allocate function for lookaside lists
 105  * ARGUMENTS:
 106  *   Type          = Type of executive pool
 107  *   NumberOfBytes = Number of bytes to allocate
 108  *   Tag           = Tag to use
 109  * RETURNS:
 110  *   Pointer to allocated memory, or NULL if there is not enough free resources
 111  */
 112 {
 113   return ExAllocatePoolWithTag(PoolType, NumberOfBytes, Tag);
 114 }
 115
 116
 117 VOID STDCALL
 118 ExpDefaultFree(PVOID Buffer)
 119 /*
 120  * FUNCTION: Default free function for lookaside lists
 121  * ARGUMENTS:
 122  *   Buffer = Pointer to memory to free
 123  */
 124 {
 125   ExFreePool(Buffer);
 126 }
 127
 128
 129 VOID INIT_FUNCTION
 130 ExpInitLookasideLists()
 131 {
 132   InitializeListHead(&ExpNonPagedLookasideListHead);
 133   KeInitializeSpinLock(&ExpNonPagedLookasideListLock);
 134
 135   InitializeListHead(&ExpPagedLookasideListHead);
 136   KeInitializeSpinLock(&ExpPagedLookasideListLock);
 137
 138   /* FIXME: Possibly configure the algorithm using the registry */
 139   ExpMinMaxRoutine = ExpDefaultMinMax;
 140 }
 141
 142
 143 PVOID
 144 FASTCALL
 145 ExiAllocateFromPagedLookasideList (
 146         PPAGED_LOOKASIDE_LIST   Lookaside
 147         )
 148 {
 149   PVOID Entry;
 150
 151   /* Try to obtain an entry from the lookaside list. If that fails, try to
 152      allocate a new entry with the allocate method for the lookaside list */
 153
 154   Lookaside->TotalAllocates++;
 155
 156 //  ExAcquireFastMutex(LookasideListLock(Lookaside));
 157
 158   Entry = PopEntrySList(&Lookaside->ListHead);
 159
 160 //  ExReleaseFastMutex(LookasideListLock(Lookaside));
 161
 162   if (Entry)
 163     return Entry;
 164
 165   Lookaside->AllocateMisses++;
 166
 167   Entry = (*Lookaside->Allocate)(Lookaside->Type,
 168     Lookaside->Size,
 169     Lookaside->Tag);
 170
 171   return Entry;
 172 }
 173
 174
 175 /*
 176  * @implemented
 177  */
 178 VOID
 179 STDCALL
 180 ExDeleteNPagedLookasideList (
 181         PNPAGED_LOOKASIDE_LIST  Lookaside
 182         )
 183 {
 184   KIRQL OldIrql;
 185   PVOID Entry;
 186
 187   /* Pop all entries off the stack and release the resources allocated
 188      for them */
 189   while ((Entry = ExInterlockedPopEntrySList(
 190     &Lookaside->ListHead,
 191     LookasideListLock(Lookaside))) != NULL)
 192   {
 193     (*Lookaside->Free)(Entry);
 194   }
 195
 196   KeAcquireSpinLock(&ExpNonPagedLookasideListLock, &OldIrql);
 197   RemoveEntryList(&Lookaside->ListEntry);
 198   KeReleaseSpinLock(&ExpNonPagedLookasideListLock, OldIrql);
 199 }
 200
 201
 202 /*
 203  * @implemented
 204  */
 205 VOID
 206 STDCALL
 207 ExDeletePagedLookasideList (
 208         PPAGED_LOOKASIDE_LIST   Lookaside
 209         )
 210 {
 211   KIRQL OldIrql;
 212   PVOID Entry;
 213
 214   /* Pop all entries off the stack and release the resources allocated
 215      for them */
 216   for (;;)
 217   {
 218
 219 //  ExAcquireFastMutex(LookasideListLock(Lookaside));
 220
 221     Entry = PopEntrySList(&Lookaside->ListHead);
 222     if (!Entry)
 223       break;
 224
 225 //  ExReleaseFastMutex(LookasideListLock(Lookaside));
 226
 227     (*Lookaside->Free)(Entry);
 228   }
 229
 230   KeAcquireSpinLock(&ExpPagedLookasideListLock, &OldIrql);
 231   RemoveEntryList(&Lookaside->ListEntry);
 232   KeReleaseSpinLock(&ExpPagedLookasideListLock, OldIrql);
 233 }
 234
 235
 236 VOID
 237 STDCALL
 238 ExiFreeToPagedLookasideList (
 239         PPAGED_LOOKASIDE_LIST   Lookaside,
 240         PVOID                   Entry
 241         )
 242 {
 243         Lookaside->TotalFrees++;
 244
 245         if (ExQueryDepthSList(&Lookaside->ListHead) >= Lookaside->Depth)
 246         {
 247                 Lookaside->FreeMisses++;
 248                 (*Lookaside->Free)(Entry);
 249         }
 250         else
 251         {
 252 //  ExAcquireFastMutex(LookasideListLock(Lookaside));
 253     PushEntrySList(&Lookaside->ListHead, (PSINGLE_LIST_ENTRY)Entry);
 254 //  ExReleaseFastMutex(LookasideListLock(Lookaside));
 255         }
 256 }
 257
 258
 259 /*
 260  * @implemented
 261  */
 262 VOID
 263 STDCALL
 264 ExInitializeNPagedLookasideList (
 265         PNPAGED_LOOKASIDE_LIST  Lookaside,
 266         PALLOCATE_FUNCTION      Allocate,
 267         PFREE_FUNCTION          Free,
 268         ULONG                   Flags,
 269         ULONG                   Size,
 270         ULONG                   Tag,
 271         USHORT                  Depth)
 272 {
 273   DPRINT("Initializing nonpaged lookaside list at 0x%X\n", Lookaside);
 274
 275   Lookaside->TotalAllocates = 0;
 276   Lookaside->AllocateMisses = 0;
 277   Lookaside->TotalFrees = 0;
 278   Lookaside->FreeMisses = 0;
 279   Lookaside->Type = NonPagedPool;
 280   Lookaside->Tag = Tag;
 281
 282   /* We use a field of type SINGLE_LIST_ENTRY as a link to the next entry in
 283      the lookaside list so we must allocate at least sizeof(SINGLE_LIST_ENTRY) */
 284   if (Size < sizeof(SINGLE_LIST_ENTRY))
 285     Lookaside->Size = sizeof(SINGLE_LIST_ENTRY);
 286   else
 287     Lookaside->Size = Size;
 288
 289   if (Allocate)
 290     Lookaside->Allocate = Allocate;
 291   else
 292     Lookaside->Allocate = ExpDefaultAllocate;
 293
 294   if (Free)
 295     Lookaside->Free = Free;
 296   else
 297     Lookaside->Free = ExpDefaultFree;
 298
 299   ExInitializeSListHead(&Lookaside->ListHead);
 300   KeInitializeSpinLock(LookasideListLock(Lookaside));
 301
 302   /* Determine minimum and maximum number of entries on the lookaside list
 303      using the configured algorithm */
 304   (*ExpMinMaxRoutine)(
 305     NonPagedPool,
 306     Lookaside->Size,
 307     &Lookaside->Depth,
 308     &Lookaside->MaximumDepth);
 309
 310   ExInterlockedInsertTailList(
 311     &ExpNonPagedLookasideListHead,
 312     &Lookaside->ListEntry,
 313     &ExpNonPagedLookasideListLock);
 314 }
 315
 316
 317 /*
 318  * @implemented
 319  */
 320 VOID
 321 STDCALL
 322 ExInitializePagedLookasideList (
 323         PPAGED_LOOKASIDE_LIST   Lookaside,
 324         PALLOCATE_FUNCTION      Allocate,
 325         PFREE_FUNCTION          Free,
 326         ULONG                   Flags,
 327         ULONG                   Size,
 328         ULONG                   Tag,
 329         USHORT                  Depth
 330         )
 331 {
 332   DPRINT("Initializing paged lookaside list at 0x%X\n", Lookaside);
 333
 334   Lookaside->TotalAllocates = 0;
 335   Lookaside->AllocateMisses = 0;
 336   Lookaside->TotalFrees = 0;
 337   Lookaside->FreeMisses = 0;
 338   Lookaside->Type = PagedPool;
 339   Lookaside->Tag = Tag;
 340
 341   /* We use a field of type SINGLE_LIST_ENTRY as a link to the next entry in
 342      the lookaside list so we must allocate at least sizeof(SINGLE_LIST_ENTRY) */
 343   if (Size < sizeof(SINGLE_LIST_ENTRY))
 344     Lookaside->Size = sizeof(SINGLE_LIST_ENTRY);
 345   else
 346     Lookaside->Size = Size;
 347
 348   if (Allocate)
 349     Lookaside->Allocate = Allocate;
 350   else
 351     Lookaside->Allocate = ExpDefaultAllocate;
 352
 353   if (Free)
 354     Lookaside->Free = Free;
 355   else
 356     Lookaside->Free = ExpDefaultFree;
 357
 358   ExInitializeSListHead(&Lookaside->ListHead);
 359   //ExInitializeFastMutex(LookasideListLock(Lookaside));
 360
 361   /* Determine minimum and maximum number of entries on the lookaside list
 362      using the configured algorithm */
 363   (*ExpMinMaxRoutine)(
 364     PagedPool,
 365     Lookaside->Size,
 366     &Lookaside->Depth,
 367     &Lookaside->MaximumDepth);
 368
 369   ExInterlockedInsertTailList(
 370     &ExpPagedLookasideListHead,
 371     &Lookaside->ListEntry,
 372     &ExpPagedLookasideListLock);
 373 }
 374
 375 /* EOF */