3 * Copyright (C) 1998, 1999, 2000, 2001 ReactOS Team
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.
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.
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.
19 /* $Id: slab.c,v 1.7 2002/09/08 10:23:36 chorns Exp $
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)
30 /* INCLUDES *****************************************************************/
32 #include <ddk/ntddk.h>
33 #include <internal/mm.h>
36 #include <internal/debug.h>
38 /* TYPES ********************************************************************/
40 typedef VOID (*SLAB_CACHE_CONSTRUCTOR
)(VOID
*, ULONG
);
41 typedef VOID (*SLAB_CACHE_DESTRUCTOR
)(VOID
*, ULONG
);
43 struct _SLAB_CACHE_PAGE
;
45 typedef struct _SLAB_CACHE
47 SLAB_CACHE_CONSTRUCTOR Constructor
;
48 SLAB_CACHE_DESTRUCTOR Destructor
;
52 LIST_ENTRY PageListHead
;
53 struct _SLAB_CACHE_PAGE
* FirstFreePage
;
55 } SLAB_CACHE
, *PSLAB_CACHE
;
57 typedef struct _SLAB_CACHE_BUFCTL
59 struct _SLAB_CACHE_BUFCTL
* NextFree
;
60 } SLAB_CACHE_BUFCTL
, *PSLAB_CACHE_BUFCTL
;
62 typedef struct _SLAB_CACHE_PAGE
64 LIST_ENTRY PageListEntry
;
65 PSLAB_CACHE_BUFCTL FirstFreeBuffer
;
67 } SLAB_CACHE_PAGE
, *PSLAB_CACHE_PAGE
;
69 /* GLOBALS ******************************************************************/
71 /* FUNCTIONS ****************************************************************/
74 ExCreateSlabCache(PUNICODE_STRING Name
, ULONG Size
, ULONG Align
,
75 SLAB_CACHE_CONSTRUCTOR Constructor
,
76 SLAB_CACHE_DESTRUCTOR Destructor
)
82 Slab
= ExAllocatePool(NonPagedPool
, sizeof(SLAB_CACHE
));
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 (PAGESIZE
- sizeof(SLAB_CACHE_PAGE
)) / Slab
->ObjectSize
;
96 InitializeListHead(&Slab
->PageListHead
);
97 KeInitializeSpinLock(&Slab
->SlabLock
);
103 ExGrowSlabCache(PSLAB_CACHE Slab
)
105 PSLAB_CACHE_PAGE SlabPage
;
106 PHYSICAL_ADDRESS PhysicalPage
;
110 PSLAB_CACHE_BUFCTL BufCtl
;
113 Status
= MmRequestPageMemoryConsumer(MC_NPPOOL
, TRUE
, &PhysicalPage
);
114 if (!NT_SUCCESS(Status
))
119 Page
= ExAllocatePageWithPhysPage(PhysicalPage
);
122 MmReleasePageMemoryConsumer(MC_NPPOOL
, PhysicalPage
);
126 SlabPage
= (PSLAB_CACHE_PAGE
)(Page
+ PAGESIZE
- sizeof(SLAB_CACHE_PAGE
));
127 SlabPage
->ReferenceCount
= 0;
128 SlabPage
->FirstFreeBuffer
= (PSLAB_CACHE_BUFCTL
)Page
;
129 for (i
= 0; i
< Slab
->ObjectsPerPage
; i
++)
131 BufCtl
= (PSLAB_CACHE_BUFCTL
)(Page
+ (i
* Slab
->ObjectSize
));
132 Object
= (PVOID
)(BufCtl
+ 1);
133 if (Slab
->Constructor
!= NULL
)
135 Slab
->Constructor(Object
, Slab
->BaseSize
);
137 if (i
== (Slab
->ObjectsPerPage
- 1))
140 (PSLAB_CACHE_BUFCTL
)(Page
+ ((i
+ 1) * Slab
->ObjectSize
));
144 BufCtl
->NextFree
= NULL
;
152 ExAllocateSlabCache(PSLAB_CACHE Slab
, BOOLEAN MayWait
)
155 PSLAB_CACHE_PAGE Page
;
159 KeAcquireSpinLock(&Slab
->SlabLock
, &oldIrql
);
162 * Check if there is a page with free objects
163 * present, if so allocate from it, if
166 if (Slab
->FirstFreePage
== NULL
)
168 KeReleaseSpinLock(&Slab
->SlabLock
, oldIrql
);
169 Page
= ExGrowSlabCache(Slab
);
171 KeAcquireSpinLock(&Slab
->SlabLock
, &oldIrql
);
175 Page
= Slab
->FirstFreePage
;
180 * We shouldn't have got a page without free buffers.
182 if (Page
->FirstFreeBuffer
== NULL
)
184 DPRINT1("First free page had no free buffers.\n");
189 * Allocate the first free object from the page.
191 Object
= (PVOID
)Page
->FirstFreeBuffer
+ sizeof(SLAB_CACHE_BUFCTL
);
192 Page
->FirstFreeBuffer
= Page
->FirstFreeBuffer
->NextFree
;
193 Page
->ReferenceCount
++;
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
201 if (Page
->ReferenceCount
== Slab
->ObjectsPerPage
&& !NewPage
)
203 if (Page
->PageListEntry
.Flink
== &Slab
->PageListHead
)
205 Slab
->FirstFreePage
= NULL
;
209 PSLAB_CACHE_PAGE NextPage
;
211 NextPage
= CONTAINING_RECORD(Page
->PageListEntry
.Flink
,
214 Slab
->FirstFreePage
= NextPage
;
216 RemoveEntryList(&Page
->PageListEntry
);
217 InsertHeadList(&Slab
->PageListHead
, &Page
->PageListEntry
);
220 * Otherwise if we created a new page then add it to the end of
225 InsertTailList(&Slab
->PageListHead
, &Page
->PageListEntry
);
226 if (Slab
->FirstFreePage
== NULL
)
228 Slab
->FirstFreePage
= Page
;
231 KeReleaseSpinLock(&Slab
->SlabLock
, oldIrql
);
236 ExFreeFromPageSlabCache(PSLAB_CACHE Slab
,
237 PSLAB_CACHE_PAGE Page
,
240 PSLAB_CACHE_BUFCTL BufCtl
;
242 BufCtl
= (PSLAB_CACHE_BUFCTL
)(Object
- sizeof(SLAB_CACHE_BUFCTL
));
243 BufCtl
->NextFree
= Page
->FirstFreeBuffer
;
244 Page
->FirstFreeBuffer
= BufCtl
;
245 Page
->ReferenceCount
--;
249 ExFreeSlabCache(PSLAB_CACHE Slab
, PVOID Object
)
252 PLIST_ENTRY current_entry
;
253 PSLAB_CACHE_PAGE current
;
255 KeAcquireSpinLock(&Slab
->SlabLock
, &oldIrql
);
256 current_entry
= Slab
->PageListHead
.Flink
;
257 while (current_entry
!= &Slab
->PageListHead
)
261 current
= CONTAINING_RECORD(current_entry
,
264 Base
= (PVOID
)current
+ sizeof(SLAB_CACHE_PAGE
) - PAGESIZE
;
265 if (Base
>= Object
&&
266 (Base
+ PAGESIZE
- sizeof(SLAB_CACHE_PAGE
)) >=
267 (Object
+ Slab
->ObjectSize
))
269 ExFreeFromPageSlabCache(Slab
, current
, Object
);
271 * If the page just become free then rearrange things.
273 if (current
->ReferenceCount
== 0)
275 RemoveEntryList(¤t
->PageListEntry
);
276 InsertTailList(&Slab
->PageListHead
, ¤t
->PageListEntry
);
277 if (Slab
->FirstFreePage
== NULL
)
279 Slab
->FirstFreePage
= current
;
282 KeReleaseSpinLock(&Slab
->SlabLock
, oldIrql
);
286 DPRINT1("Tried to free object not in cache.\n");
291 ExDestroySlabCache(PSLAB_CACHE Slab
)
293 PLIST_ENTRY current_entry
;
294 PSLAB_CACHE_PAGE current
;
298 current_entry
= Slab
->PageListHead
.Flink
;
299 while (current_entry
!= &Slab
->PageListHead
)
302 PHYSICAL_ADDRESS PhysicalPage
;
304 current
= CONTAINING_RECORD(current_entry
,
307 Base
= (PVOID
)current
+ sizeof(SLAB_CACHE_PAGE
) - PAGESIZE
;
308 if (Slab
->Destructor
!= NULL
)
310 for (i
= 0; i
< Slab
->ObjectsPerPage
; i
++)
312 Object
= Base
+ (i
* Slab
->ObjectSize
) +
313 sizeof(SLAB_CACHE_BUFCTL
);
314 Slab
->Destructor(Object
, Slab
->BaseSize
);
317 PhysicalPage
= MmGetPhysicalAddressForProcess(NULL
, Base
);
319 MmReleasePageMemoryConsumer(MC_NPPOOL
, PhysicalPage
);