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 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 uint32 Count() const { return fCount; } 53 54 inline Iterator GetIterator() const; 55 56 inline spinlock& GetLock() { return fLock; } 57 58 protected: 59 const char* fName; 60 spinlock fLock; 61 uint32 fCount; 62 PageList fPages; 63 }; 64 65 66 // #pragma mark - VMPageQueue 67 68 69 void 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 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 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 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* 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 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 182 VMPageQueue::AppendUnlocked(vm_page* page) 183 { 184 InterruptsSpinLocker locker(fLock); 185 Append(page); 186 } 187 188 189 void 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 213 VMPageQueue::PrependUnlocked(vm_page* page) 214 { 215 InterruptsSpinLocker locker(fLock); 216 Prepend(page); 217 } 218 219 220 void 221 VMPageQueue::RemoveUnlocked(vm_page* page) 222 { 223 InterruptsSpinLocker locker(fLock); 224 return Remove(page); 225 } 226 227 228 vm_page* 229 VMPageQueue::RemoveHeadUnlocked() 230 { 231 InterruptsSpinLocker locker(fLock); 232 return RemoveHead(); 233 } 234 235 236 void 237 VMPageQueue::RequeueUnlocked(vm_page* page, bool tail) 238 { 239 InterruptsSpinLocker locker(fLock); 240 Requeue(page, tail); 241 } 242 243 244 vm_page* 245 VMPageQueue::Head() const 246 { 247 return fPages.Head(); 248 } 249 250 251 vm_page* 252 VMPageQueue::Tail() const 253 { 254 return fPages.Tail(); 255 } 256 257 258 vm_page* 259 VMPageQueue::Previous(vm_page* page) const 260 { 261 return fPages.GetPrevious(page); 262 } 263 264 265 vm_page* 266 VMPageQueue::Next(vm_page* page) const 267 { 268 return fPages.GetNext(page); 269 } 270 271 272 VMPageQueue::Iterator 273 VMPageQueue::GetIterator() const 274 { 275 return fPages.GetIterator(); 276 } 277 278 279 #endif // VM_PAGE_QUEUE_H 280