ntoskrnl/mm/slab.c

   1 /*
   2  *  ReactOS kernel
   3  *  Copyright (C) 1998, 1999, 2000, 2001 ReactOS Team
   4  *
   5  *  This program is free software; you can redistribute it and/or modify
   6  *  it under the terms of the GNU General Public License as published by
   7  *  the Free Software Foundation; either version 2 of the License, or
   8  *  (at your option) any later version.
   9  *
  10  *  This program is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  *  GNU General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU General Public License
  16  *  along with this program; if not, write to the Free Software
  17  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18  */
  19 /* $Id$
  20  *
  21  * COPYRIGHT:   See COPYING in the top directory
  22  * PROJECT:     ReactOS kernel
  23  * FILE:        ntoskrnl/mm/slab.c
  24  * PURPOSE:     Slab allocator.
  25  * PROGRAMMER:  David Welch (welch@cwcom.net)
  26  * UPDATE HISTORY:
  27  *              Created 27/12/01
  28  */
  29
  30 /* INCLUDES *****************************************************************/
  31
  32 #include <ddk/ntddk.h>
  33 #include <internal/mm.h>
  34
  35 #define NDEBUG
  36 #include <internal/debug.h>
  37
  38 /* TYPES ********************************************************************/
  39
  40 typedef VOID (*SLAB_CACHE_CONSTRUCTOR)(VOID*, ULONG);
  41 typedef VOID (*SLAB_CACHE_DESTRUCTOR)(VOID*, ULONG);
  42
  43 struct _SLAB_CACHE_PAGE;
  44
  45 typedef struct _SLAB_CACHE
  46 {
  47   SLAB_CACHE_CONSTRUCTOR Constructor;
  48   SLAB_CACHE_DESTRUCTOR Destructor;
  49   ULONG BaseSize;
  50   ULONG ObjectSize;
  51   ULONG ObjectsPerPage;
  52   LIST_ENTRY PageListHead;
  53   struct _SLAB_CACHE_PAGE* FirstFreePage;
  54   KSPIN_LOCK SlabLock;
  55 } SLAB_CACHE, *PSLAB_CACHE;
  56
  57 typedef struct _SLAB_CACHE_BUFCTL
  58 {
  59   struct _SLAB_CACHE_BUFCTL* NextFree;
  60 } SLAB_CACHE_BUFCTL, *PSLAB_CACHE_BUFCTL;
  61
  62 typedef struct _SLAB_CACHE_PAGE
  63 {
  64   LIST_ENTRY PageListEntry;
  65   PSLAB_CACHE_BUFCTL FirstFreeBuffer;
  66   ULONG ReferenceCount;
  67 } SLAB_CACHE_PAGE, *PSLAB_CACHE_PAGE;
  68
  69 /* GLOBALS ******************************************************************/
  70
  71 /* FUNCTIONS ****************************************************************/
  72
  73 PSLAB_CACHE
  74 ExCreateSlabCache(PUNICODE_STRING Name, ULONG Size, ULONG Align,
  75                   SLAB_CACHE_CONSTRUCTOR Constructor,
  76                   SLAB_CACHE_DESTRUCTOR Destructor)
  77 {
  78   PSLAB_CACHE Slab;
  79   ULONG ObjectSize;
  80   ULONG AlignSize;
  81
  82   Slab = ExAllocatePool(NonPagedPool, sizeof(SLAB_CACHE));
  83   if (Slab == NULL)
  84     {
  85       return(NULL);
  86     }
  87
  88   Slab->Constructor = Constructor;
  89   Slab->Destructor = Destructor;
  90   Slab->BaseSize = Size;
  91   ObjectSize = Size + sizeof(SLAB_CACHE_BUFCTL);
  92   AlignSize = Align - (ObjectSize % Align);
  93   Slab->ObjectSize = ObjectSize + AlignSize;
  94   Slab->ObjectsPerPage =
  95     (PAGE_SIZE - sizeof(SLAB_CACHE_PAGE)) / Slab->ObjectSize;
  96   InitializeListHead(&Slab->PageListHead);
  97   KeInitializeSpinLock(&Slab->SlabLock);
  98
  99   return(Slab);
 100 }
 101
 102 PSLAB_CACHE_PAGE
 103 ExGrowSlabCache(PSLAB_CACHE Slab)
 104 {
 105   PSLAB_CACHE_PAGE SlabPage;
 106   PHYSICAL_ADDRESS PhysicalPage;
 107   PVOID Page;
 108   NTSTATUS Status;
 109   ULONG i;
 110   PSLAB_CACHE_BUFCTL BufCtl;
 111   PVOID Object;
 112
 113   Status = MmRequestPageMemoryConsumer(MC_NPPOOL, TRUE, &PhysicalPage);
 114   if (!NT_SUCCESS(Status))
 115     {
 116       return(NULL);
 117     }
 118
 119   Page = ExAllocatePageWithPhysPage(PhysicalPage);
 120   if (Page == NULL)
 121     {
 122       MmReleasePageMemoryConsumer(MC_NPPOOL, PhysicalPage);
 123       return(NULL);
 124     }
 125
 126   SlabPage = (PSLAB_CACHE_PAGE)(Page + PAGE_SIZE - sizeof(SLAB_CACHE_PAGE));
 127   SlabPage->ReferenceCount = 0;
 128   SlabPage->FirstFreeBuffer = (PSLAB_CACHE_BUFCTL)Page;
 129   for (i = 0; i < Slab->ObjectsPerPage; i++)
 130     {
 131       BufCtl = (PSLAB_CACHE_BUFCTL)(Page + (i * Slab->ObjectSize));
 132       Object = (PVOID)(BufCtl + 1);
 133       if (Slab->Constructor != NULL)
 134         {
 135           Slab->Constructor(Object, Slab->BaseSize);
 136         }
 137       if (i == (Slab->ObjectsPerPage - 1))
 138         {
 139           BufCtl->NextFree =
 140             (PSLAB_CACHE_BUFCTL)(Page + ((i + 1) * Slab->ObjectSize));
 141         }
 142       else
 143         {
 144           BufCtl->NextFree = NULL;
 145         }
 146     }
 147
 148   return(SlabPage);
 149 }
 150
 151 PVOID
 152 ExAllocateSlabCache(PSLAB_CACHE Slab, BOOLEAN MayWait)
 153 {
 154   KIRQL oldIrql;
 155   PSLAB_CACHE_PAGE Page;
 156   PVOID Object;
 157   BOOLEAN NewPage;
 158
 159   KeAcquireSpinLock(&Slab->SlabLock, &oldIrql);
 160
 161   /*
 162    * Check if there is a page with free objects
 163    * present, if so allocate from it, if
 164    * not grow the slab.
 165    */
 166   if (Slab->FirstFreePage == NULL)
 167     {
 168       KeReleaseSpinLock(&Slab->SlabLock, oldIrql);
 169       Page = ExGrowSlabCache(Slab);
 170       NewPage = TRUE;
 171       KeAcquireSpinLock(&Slab->SlabLock, &oldIrql);
 172     }
 173   else
 174     {
 175       Page = Slab->FirstFreePage;
 176       NewPage = FALSE;
 177     }
 178
 179   /*
 180    * We shouldn't have got a page without free buffers.
 181    */
 182   if (Page->FirstFreeBuffer == NULL)
 183     {
 184       DPRINT1("First free page had no free buffers.\n");
 185       KeBugCheck(0);
 186     }
 187
 188   /*
 189    * Allocate the first free object from the page.
 190    */
 191   Object = (PVOID)Page->FirstFreeBuffer + sizeof(SLAB_CACHE_BUFCTL);
 192   Page->FirstFreeBuffer = Page->FirstFreeBuffer->NextFree;
 193   Page->ReferenceCount++;
 194
 195   /*
 196    * If we just allocated all the objects from this page
 197    * and it was the first free page then adjust the
 198    * first free page pointer and move the page to the head
 199    * of the list.
 200    */
 201   if (Page->ReferenceCount == Slab->ObjectsPerPage && !NewPage)
 202     {
 203       if (Page->PageListEntry.Flink == &Slab->PageListHead)
 204         {
 205           Slab->FirstFreePage = NULL;
 206         }
 207       else
 208         {
 209           PSLAB_CACHE_PAGE NextPage;
 210
 211           NextPage = CONTAINING_RECORD(Page->PageListEntry.Flink,
 212                                        SLAB_CACHE_PAGE,
 213                                        PageListEntry);
 214           Slab->FirstFreePage = NextPage;
 215         }
 216       RemoveEntryList(&Page->PageListEntry);
 217       InsertHeadList(&Slab->PageListHead, &Page->PageListEntry);
 218     }
 219   /*
 220    * Otherwise if we created a new page then add it to the end of
 221    * the page list.
 222    */
 223   else if (NewPage)
 224     {
 225       InsertTailList(&Slab->PageListHead, &Page->PageListEntry);
 226       if (Slab->FirstFreePage == NULL)
 227         {
 228           Slab->FirstFreePage = Page;
 229         }
 230     }
 231   KeReleaseSpinLock(&Slab->SlabLock, oldIrql);
 232   return(Object);
 233 }
 234
 235 VOID
 236 ExFreeFromPageSlabCache(PSLAB_CACHE Slab,
 237                         PSLAB_CACHE_PAGE Page,
 238                         PVOID Object)
 239 {
 240   PSLAB_CACHE_BUFCTL BufCtl;
 241
 242   BufCtl = (PSLAB_CACHE_BUFCTL)(Object - sizeof(SLAB_CACHE_BUFCTL));
 243   BufCtl->NextFree = Page->FirstFreeBuffer;
 244   Page->FirstFreeBuffer = BufCtl;
 245   Page->ReferenceCount--;
 246 }
 247
 248 VOID
 249 ExFreeSlabCache(PSLAB_CACHE Slab, PVOID Object)
 250 {
 251   KIRQL oldIrql;
 252   PLIST_ENTRY current_entry;
 253   PSLAB_CACHE_PAGE current;
 254
 255   KeAcquireSpinLock(&Slab->SlabLock, &oldIrql);
 256   current_entry = Slab->PageListHead.Flink;
 257   while (current_entry != &Slab->PageListHead)
 258     {
 259       PVOID Base;
 260
 261       current = CONTAINING_RECORD(current_entry,
 262                                   SLAB_CACHE_PAGE,
 263                                   PageListEntry);
 264       Base = (PVOID)current + sizeof(SLAB_CACHE_PAGE) - PAGE_SIZE;
 265       if (Base >= Object &&
 266           (Base + PAGE_SIZE - sizeof(SLAB_CACHE_PAGE)) >=
 267            (Object + Slab->ObjectSize))
 268         {
 269           ExFreeFromPageSlabCache(Slab, current, Object);
 270           /*
 271            * If the page just become free then rearrange things.
 272            */
 273           if (current->ReferenceCount == 0)
 274             {
 275               RemoveEntryList(&current->PageListEntry);
 276               InsertTailList(&Slab->PageListHead, &current->PageListEntry);
 277               if (Slab->FirstFreePage == NULL)
 278                 {
 279                   Slab->FirstFreePage = current;
 280                 }
 281             }
 282           KeReleaseSpinLock(&Slab->SlabLock, oldIrql);
 283           return;
 284         }
 285     }
 286   DPRINT1("Tried to free object not in cache.\n");
 287   KeBugCheck(0);
 288 }
 289
 290 VOID
 291 ExDestroySlabCache(PSLAB_CACHE Slab)
 292 {
 293   PLIST_ENTRY current_entry;
 294   PSLAB_CACHE_PAGE current;
 295   ULONG i;
 296   PVOID Object;
 297
 298   current_entry = Slab->PageListHead.Flink;
 299   while (current_entry != &Slab->PageListHead)
 300     {
 301       PVOID Base;
 302       PHYSICAL_ADDRESS PhysicalPage;
 303
 304       current = CONTAINING_RECORD(current_entry,
 305                                   SLAB_CACHE_PAGE,
 306                                   PageListEntry);
 307       Base = (PVOID)current + sizeof(SLAB_CACHE_PAGE) - PAGE_SIZE;
 308       if (Slab->Destructor != NULL)
 309         {
 310           for (i = 0; i < Slab->ObjectsPerPage; i++)
 311             {
 312               Object = Base + (i * Slab->ObjectSize) +
 313                 sizeof(SLAB_CACHE_BUFCTL);
 314               Slab->Destructor(Object, Slab->BaseSize);
 315             }
 316         }
 317       PhysicalPage = MmGetPhysicalAddressForProcess(NULL, Base);
 318       ExUnmapPage(Base);
 319       MmReleasePageMemoryConsumer(MC_NPPOOL, PhysicalPage);
 320     }
 321   ExFreePool(Slab);
 322 }