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