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