1/*
2 * Copyright 2010, Ingo Weinhold, ingo_weinhold@gmx.de.
3 * Copyright 2002-2008, Axel D��rfler, axeld@pinc-software.de.
4 * Distributed under the terms of the MIT License.
5 *
6 * Copyright 2001-2002, Travis Geiselbrecht. All rights reserved.
7 * Distributed under the terms of the NewOS License.
8 */
9#ifndef VM_PAGE_QUEUE_H
10#define VM_PAGE_QUEUE_H
11
12
13#include <util/DoublyLinkedList.h>
14
15#include <lock.h>
16#include <int.h>
17#include <util/AutoLock.h>
18#include <vm/vm_types.h>
19
20
21struct VMPageQueue {
22public:
23	typedef DoublyLinkedList<vm_page,
24		DoublyLinkedListMemberGetLink<vm_page, &vm_page::queue_link> > PageList;
25	typedef PageList::ConstIterator Iterator;
26
27public:
28			void				Init(const char* name);
29
30			const char*			Name() const	{ return fName; }
31
32	inline	void				Append(vm_page* page);
33	inline	void				Prepend(vm_page* page);
34	inline	void				InsertAfter(vm_page* insertAfter,
35									vm_page* page);
36	inline	void				Remove(vm_page* page);
37	inline	vm_page*			RemoveHead();
38	inline	void				Requeue(vm_page* page, bool tail);
39
40	inline	void				AppendUnlocked(vm_page* page);
41	inline	void				AppendUnlocked(PageList& pages, uint32 count);
42	inline	void				PrependUnlocked(vm_page* page);
43	inline	void				RemoveUnlocked(vm_page* page);
44	inline	vm_page*			RemoveHeadUnlocked();
45	inline	void				RequeueUnlocked(vm_page* page, bool tail);
46
47	inline	vm_page*			Head() const;
48	inline	vm_page*			Tail() const;
49	inline	vm_page*			Previous(vm_page* page) const;
50	inline	vm_page*			Next(vm_page* page) const;
51
52	inline	phys_addr_t			Count() const	{ return fCount; }
53
54	inline	Iterator			GetIterator() const;
55
56	inline	spinlock&			GetLock()	{ return fLock; }
57
58protected:
59			const char*			fName;
60			spinlock			fLock;
61			phys_addr_t			fCount;
62			PageList			fPages;
63};
64
65
66// #pragma mark - VMPageQueue
67
68
69void
70VMPageQueue::Append(vm_page* page)
71{
72#if DEBUG_PAGE_QUEUE
73	if (page->queue != NULL) {
74		panic("%p->VMPageQueue::Append(page: %p): page thinks it is "
75			"already in queue %p", this, page, page->queue);
76	}
77#endif	// DEBUG_PAGE_QUEUE
78
79	fPages.Add(page);
80	fCount++;
81
82#if DEBUG_PAGE_QUEUE
83	page->queue = this;
84#endif
85}
86
87
88void
89VMPageQueue::Prepend(vm_page* page)
90{
91#if DEBUG_PAGE_QUEUE
92	if (page->queue != NULL) {
93		panic("%p->VMPageQueue::Prepend(page: %p): page thinks it is "
94			"already in queue %p", this, page, page->queue);
95	}
96#endif	// DEBUG_PAGE_QUEUE
97
98	fPages.Add(page, false);
99	fCount++;
100
101#if DEBUG_PAGE_QUEUE
102	page->queue = this;
103#endif
104}
105
106
107void
108VMPageQueue::InsertAfter(vm_page* insertAfter, vm_page* page)
109{
110#if DEBUG_PAGE_QUEUE
111	if (page->queue != NULL) {
112		panic("%p->VMPageQueue::InsertAfter(page: %p): page thinks it is "
113			"already in queue %p", this, page, page->queue);
114	}
115#endif	// DEBUG_PAGE_QUEUE
116
117	fPages.InsertAfter(insertAfter, page);
118	fCount++;
119
120#if DEBUG_PAGE_QUEUE
121	page->queue = this;
122#endif
123}
124
125
126void
127VMPageQueue::Remove(vm_page* page)
128{
129#if DEBUG_PAGE_QUEUE
130	if (page->queue != this) {
131		panic("%p->VMPageQueue::Remove(page: %p): page thinks it "
132			"is in queue %p", this, page, page->queue);
133	}
134#endif	// DEBUG_PAGE_QUEUE
135
136	fPages.Remove(page);
137	fCount--;
138
139#if DEBUG_PAGE_QUEUE
140	page->queue = NULL;
141#endif
142}
143
144
145vm_page*
146VMPageQueue::RemoveHead()
147{
148	vm_page* page = fPages.RemoveHead();
149	if (page != NULL) {
150		fCount--;
151
152#if DEBUG_PAGE_QUEUE
153		if (page->queue != this) {
154			panic("%p->VMPageQueue::RemoveHead(): page %p thinks it is in "
155				"queue %p", this, page, page->queue);
156		}
157
158		page->queue = NULL;
159#endif	// DEBUG_PAGE_QUEUE
160	}
161
162	return page;
163}
164
165
166void
167VMPageQueue::Requeue(vm_page* page, bool tail)
168{
169#if DEBUG_PAGE_QUEUE
170	if (page->queue != this) {
171		panic("%p->VMPageQueue::Requeue(): page %p thinks it is in "
172			"queue %p", this, page, page->queue);
173	}
174#endif
175
176	fPages.Remove(page);
177	fPages.Add(page, tail);
178}
179
180
181void
182VMPageQueue::AppendUnlocked(vm_page* page)
183{
184	InterruptsSpinLocker locker(fLock);
185	Append(page);
186}
187
188
189void
190VMPageQueue::AppendUnlocked(PageList& pages, uint32 count)
191{
192#if DEBUG_PAGE_QUEUE
193	for (PageList::Iterator it = pages.GetIterator();
194			vm_page* page = it.Next();) {
195		if (page->queue != NULL) {
196			panic("%p->VMPageQueue::AppendUnlocked(): page %p thinks it is "
197				"already in queue %p", this, page, page->queue);
198		}
199
200		page->queue = this;
201	}
202
203#endif	// DEBUG_PAGE_QUEUE
204
205	InterruptsSpinLocker locker(fLock);
206
207	fPages.MoveFrom(&pages);
208	fCount += count;
209}
210
211
212void
213VMPageQueue::PrependUnlocked(vm_page* page)
214{
215	InterruptsSpinLocker locker(fLock);
216	Prepend(page);
217}
218
219
220void
221VMPageQueue::RemoveUnlocked(vm_page* page)
222{
223	InterruptsSpinLocker locker(fLock);
224	return Remove(page);
225}
226
227
228vm_page*
229VMPageQueue::RemoveHeadUnlocked()
230{
231	InterruptsSpinLocker locker(fLock);
232	return RemoveHead();
233}
234
235
236void
237VMPageQueue::RequeueUnlocked(vm_page* page, bool tail)
238{
239	InterruptsSpinLocker locker(fLock);
240	Requeue(page, tail);
241}
242
243
244vm_page*
245VMPageQueue::Head() const
246{
247	return fPages.Head();
248}
249
250
251vm_page*
252VMPageQueue::Tail() const
253{
254	return fPages.Tail();
255}
256
257
258vm_page*
259VMPageQueue::Previous(vm_page* page) const
260{
261	return fPages.GetPrevious(page);
262}
263
264
265vm_page*
266VMPageQueue::Next(vm_page* page) const
267{
268	return fPages.GetNext(page);
269}
270
271
272VMPageQueue::Iterator
273VMPageQueue::GetIterator() const
274{
275	return fPages.GetIterator();
276}
277
278
279#endif	// VM_PAGE_QUEUE_H
280