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
21 struct VMPageQueue {
22 public:
23 typedef DoublyLinkedList<vm_page,
24 DoublyLinkedListMemberGetLink<vm_page, &vm_page::queue_link> > PageList;
25 typedef PageList::ConstIterator Iterator;
26
27 public:
28 void Init(const char* name);
29
NameVMPageQueue30 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
CountVMPageQueue52 inline page_num_t Count() const { return fCount; }
53
54 inline Iterator GetIterator() const;
55
GetLockVMPageQueue56 inline spinlock& GetLock() { return fLock; }
57
58 protected:
59 const char* fName;
60 spinlock fLock;
61 page_num_t fCount;
62 PageList fPages;
63 };
64
65
66 // #pragma mark - VMPageQueue
67
68
69 void
Append(vm_page * page)70 VMPageQueue::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
88 void
Prepend(vm_page * page)89 VMPageQueue::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
107 void
InsertAfter(vm_page * insertAfter,vm_page * page)108 VMPageQueue::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
126 void
Remove(vm_page * page)127 VMPageQueue::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
145 vm_page*
RemoveHead()146 VMPageQueue::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
166 void
Requeue(vm_page * page,bool tail)167 VMPageQueue::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
181 void
AppendUnlocked(vm_page * page)182 VMPageQueue::AppendUnlocked(vm_page* page)
183 {
184 InterruptsSpinLocker locker(fLock);
185 Append(page);
186 }
187
188
189 void
AppendUnlocked(PageList & pages,uint32 count)190 VMPageQueue::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
212 void
PrependUnlocked(vm_page * page)213 VMPageQueue::PrependUnlocked(vm_page* page)
214 {
215 InterruptsSpinLocker locker(fLock);
216 Prepend(page);
217 }
218
219
220 void
RemoveUnlocked(vm_page * page)221 VMPageQueue::RemoveUnlocked(vm_page* page)
222 {
223 InterruptsSpinLocker locker(fLock);
224 return Remove(page);
225 }
226
227
228 vm_page*
RemoveHeadUnlocked()229 VMPageQueue::RemoveHeadUnlocked()
230 {
231 InterruptsSpinLocker locker(fLock);
232 return RemoveHead();
233 }
234
235
236 void
RequeueUnlocked(vm_page * page,bool tail)237 VMPageQueue::RequeueUnlocked(vm_page* page, bool tail)
238 {
239 InterruptsSpinLocker locker(fLock);
240 Requeue(page, tail);
241 }
242
243
244 vm_page*
Head()245 VMPageQueue::Head() const
246 {
247 return fPages.Head();
248 }
249
250
251 vm_page*
Tail()252 VMPageQueue::Tail() const
253 {
254 return fPages.Tail();
255 }
256
257
258 vm_page*
Previous(vm_page * page)259 VMPageQueue::Previous(vm_page* page) const
260 {
261 return fPages.GetPrevious(page);
262 }
263
264
265 vm_page*
Next(vm_page * page)266 VMPageQueue::Next(vm_page* page) const
267 {
268 return fPages.GetNext(page);
269 }
270
271
272 VMPageQueue::Iterator
GetIterator()273 VMPageQueue::GetIterator() const
274 {
275 return fPages.GetIterator();
276 }
277
278
279 #endif // VM_PAGE_QUEUE_H
280