reactos/ntoskrnl/ex/lookas.c

   1 /* $Id: lookas.c,v 1.11 2003/08/14 18:30:28 silverblade Exp $
   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
 147 PVOID
 148 FASTCALL
 149 ExiAllocateFromPagedLookasideList (
 150         PPAGED_LOOKASIDE_LIST   Lookaside
 151         )
 152 {
 153   PVOID Entry;
 154
 155   /* Try to obtain an entry from the lookaside list. If that fails, try to
 156      allocate a new entry with the allocate method for the lookaside list */
 157
 158   Lookaside->TotalAllocates++;
 159
 160 //  ExAcquireFastMutex(LookasideListLock(Lookaside));
 161
 162   Entry = PopEntrySList(&Lookaside->ListHead);
 163
 164 //  ExReleaseFastMutex(LookasideListLock(Lookaside));
 165
 166   if (Entry)
 167     return Entry;
 168
 169   Lookaside->AllocateMisses++;
 170
 171   Entry = (*Lookaside->Allocate)(Lookaside->Type,
 172     Lookaside->Size,
 173     Lookaside->Tag);
 174
 175   return Entry;
 176 }
 177
 178
 179 /*
 180  * @implemented
 181  */
 182 VOID
 183 STDCALL
 184 ExDeleteNPagedLookasideList (
 185         PNPAGED_LOOKASIDE_LIST  Lookaside
 186         )
 187 {
 188   KIRQL OldIrql;
 189   PVOID Entry;
 190
 191   /* Pop all entries off the stack and release the resources allocated
 192      for them */
 193   while ((Entry = ExInterlockedPopEntrySList(
 194     &Lookaside->ListHead,
 195     LookasideListLock(Lookaside))) != NULL)
 196   {
 197     (*Lookaside->Free)(Entry);
 198   }
 199
 200   KeAcquireSpinLock(&ExpNonPagedLookasideListLock, &OldIrql);
 201   RemoveEntryList(&Lookaside->ListEntry);
 202   KeReleaseSpinLock(&ExpNonPagedLookasideListLock, OldIrql);
 203 }
 204
 205
 206 /*
 207  * @implemented
 208  */
 209 VOID
 210 STDCALL
 211 ExDeletePagedLookasideList (
 212         PPAGED_LOOKASIDE_LIST   Lookaside
 213         )
 214 {
 215   KIRQL OldIrql;
 216   PVOID Entry;
 217
 218   /* Pop all entries off the stack and release the resources allocated
 219      for them */
 220   for (;;)
 221   {
 222
 223 //  ExAcquireFastMutex(LookasideListLock(Lookaside));
 224
 225     Entry = PopEntrySList(&Lookaside->ListHead);
 226     if (!Entry)
 227       break;
 228
 229 //  ExReleaseFastMutex(LookasideListLock(Lookaside));
 230
 231     (*Lookaside->Free)(Entry);
 232   }
 233
 234   KeAcquireSpinLock(&ExpPagedLookasideListLock, &OldIrql);
 235   RemoveEntryList(&Lookaside->ListEntry);
 236   KeReleaseSpinLock(&ExpPagedLookasideListLock, OldIrql);
 237 }
 238
 239
 240 VOID
 241 STDCALL
 242 ExiFreeToPagedLookasideList (
 243         PPAGED_LOOKASIDE_LIST   Lookaside,
 244         PVOID                   Entry
 245         )
 246 {
 247         Lookaside->TotalFrees++;
 248
 249         if (ExQueryDepthSList(&Lookaside->ListHead) >= Lookaside->Depth)
 250         {
 251                 Lookaside->FreeMisses++;
 252                 (*Lookaside->Free)(Entry);
 253         }
 254         else
 255         {
 256 //  ExAcquireFastMutex(LookasideListLock(Lookaside));
 257     PushEntrySList(&Lookaside->ListHead, (PSINGLE_LIST_ENTRY)Entry);
 258 //  ExReleaseFastMutex(LookasideListLock(Lookaside));
 259         }
 260 }
 261
 262
 263 /*
 264  * @implemented
 265  */
 266 VOID
 267 STDCALL
 268 ExInitializeNPagedLookasideList (
 269         PNPAGED_LOOKASIDE_LIST  Lookaside,
 270         PALLOCATE_FUNCTION      Allocate,
 271         PFREE_FUNCTION          Free,
 272         ULONG                   Flags,
 273         ULONG                   Size,
 274         ULONG                   Tag,
 275         USHORT                  Depth)
 276 {
 277   DPRINT("Initializing nonpaged lookaside list at 0x%X\n", Lookaside);
 278
 279   Lookaside->TotalAllocates = 0;
 280   Lookaside->AllocateMisses = 0;
 281   Lookaside->TotalFrees = 0;
 282   Lookaside->FreeMisses = 0;
 283   Lookaside->Type = NonPagedPool;
 284   Lookaside->Tag = Tag;
 285
 286   /* We use a field of type SINGLE_LIST_ENTRY as a link to the next entry in
 287      the lookaside list so we must allocate at least sizeof(SINGLE_LIST_ENTRY) */
 288   if (Size < sizeof(SINGLE_LIST_ENTRY))
 289     Lookaside->Size = sizeof(SINGLE_LIST_ENTRY);
 290   else
 291     Lookaside->Size = Size;
 292
 293   if (Allocate)
 294     Lookaside->Allocate = Allocate;
 295   else
 296     Lookaside->Allocate = ExpDefaultAllocate;
 297
 298   if (Free)
 299     Lookaside->Free = Free;
 300   else
 301     Lookaside->Free = ExpDefaultFree;
 302
 303   ExInitializeSListHead(&Lookaside->ListHead);
 304   KeInitializeSpinLock(LookasideListLock(Lookaside));
 305
 306   /* Determine minimum and maximum number of entries on the lookaside list
 307      using the configured algorithm */
 308   (*ExpMinMaxRoutine)(
 309     NonPagedPool,
 310     Lookaside->Size,
 311     &Lookaside->Depth,
 312     &Lookaside->MaximumDepth);
 313
 314   ExInterlockedInsertTailList(
 315     &ExpNonPagedLookasideListHead,
 316     &Lookaside->ListEntry,
 317     &ExpNonPagedLookasideListLock);
 318 }
 319
 320
 321 /*
 322  * @implemented
 323  */
 324 VOID
 325 STDCALL
 326 ExInitializePagedLookasideList (
 327         PPAGED_LOOKASIDE_LIST   Lookaside,
 328         PALLOCATE_FUNCTION      Allocate,
 329         PFREE_FUNCTION          Free,
 330         ULONG                   Flags,
 331         ULONG                   Size,
 332         ULONG                   Tag,
 333         USHORT                  Depth
 334         )
 335 {
 336   DPRINT("Initializing paged lookaside list at 0x%X\n", Lookaside);
 337
 338   Lookaside->TotalAllocates = 0;
 339   Lookaside->AllocateMisses = 0;
 340   Lookaside->TotalFrees = 0;
 341   Lookaside->FreeMisses = 0;
 342   Lookaside->Type = PagedPool;
 343   Lookaside->Tag = Tag;
 344
 345   /* We use a field of type SINGLE_LIST_ENTRY as a link to the next entry in
 346      the lookaside list so we must allocate at least sizeof(SINGLE_LIST_ENTRY) */
 347   if (Size < sizeof(SINGLE_LIST_ENTRY))
 348     Lookaside->Size = sizeof(SINGLE_LIST_ENTRY);
 349   else
 350     Lookaside->Size = Size;
 351
 352   if (Allocate)
 353     Lookaside->Allocate = Allocate;
 354   else
 355     Lookaside->Allocate = ExpDefaultAllocate;
 356
 357   if (Free)
 358     Lookaside->Free = Free;
 359   else
 360     Lookaside->Free = ExpDefaultFree;
 361
 362   ExInitializeSListHead(&Lookaside->ListHead);
 363   //ExInitializeFastMutex(LookasideListLock(Lookaside));
 364
 365   /* Determine minimum and maximum number of entries on the lookaside list
 366      using the configured algorithm */
 367   (*ExpMinMaxRoutine)(
 368     PagedPool,
 369     Lookaside->Size,
 370     &Lookaside->Depth,
 371     &Lookaside->MaximumDepth);
 372
 373   ExInterlockedInsertTailList(
 374     &ExpPagedLookasideListHead,
 375     &Lookaside->ListEntry,
 376     &ExpPagedLookasideListLock);
 377 }
 378
 379 /* EOF */