1 = Paging = 2 3 Within filesystem servers, a number of abstractions are combined to support 4 [[FilesystemAccess|access to filesystem content]] through paging: the delivery 5 of content to clients in mapped memory. The general mechanism used to support 6 paging is depicted below. 7 8 ######## A graph showing the general paging mechanism 9 10 {{{#!graphviz 11 #format svg 12 #transform notugly 13 digraph paging { 14 node [fontsize="12.0",fontname="sans-serif",shape=box]; 15 edge [fontsize="12.0",fontname="sans-serif"]; 16 rankdir=LR; 17 18 subgraph { 19 rank=same; 20 21 Pager_note [shape=note,style=filled,fillcolor=gold,label="Provides\nfilesystem\ncontent"]; 22 Pager; 23 24 Pager_note -> Pager [dir=none,style=dotted]; 25 } 26 27 subgraph { 28 rank=same; 29 30 PageMapper_note [shape=note,style=filled,fillcolor=gold,label="Provides\npopulated\nfile pages"]; 31 PageMapper; 32 33 PageMapper_note -> PageMapper [dir=none,style=dotted]; 34 } 35 36 subgraph { 37 rank=same; 38 39 Accessor_note [shape=note,style=filled,fillcolor=gold,label="Populates\nfile pages"]; 40 Accessor; 41 42 Accessor_note -> Accessor [dir=none,style=dotted]; 43 } 44 45 AccessMap [shape=record,label="<head> AccessMap | 46 { offset-0 |<fp0> flexpage-0 } | ... | 47 { offset-n |<fpn> flexpage-n } | ..."]; 48 49 subgraph { 50 rank=same; 51 52 Pages_note [shape=note,style=filled,fillcolor=gold,label="Provides\nmemory\npages"]; 53 Pages; 54 55 Pages_note -> Pages [dir=none,style=dotted]; 56 } 57 58 PageQueue [shape=record,label="<head> PageQueue | 59 { owner-0 |<fp0> flexpage-0 } | ... | 60 { owner-N |<fpN> flexpage-N } | <end> ..."]; 61 62 Flexpage_offset_n [shape=record,label="<head> Flexpage | 63 offset | size |<r> region"]; 64 65 subgraph { 66 rank=same; 67 68 Memory_note [shape=note,style=filled,fillcolor=gold,label="Allocates\nmemory\nregions"]; 69 Memory; 70 71 Memory_note -> Memory [dir=none,style=dotted]; 72 } 73 74 Region; 75 76 /* Relationships. */ 77 78 PageMapper -> Accessor; 79 PageMapper -> AccessMap:head; 80 Pager -> PageMapper -> Pages; 81 Pages -> Memory; 82 Pages -> PageQueue:head; 83 AccessMap:fpn -> Flexpage_offset_n:head; 84 PageQueue:fpN -> Flexpage_offset_n:head; 85 Flexpage_offset_n:r -> Region; 86 } 87 }}} 88 89 ######## 90 91 A [[ServerLibrary#Pager|`Pager`]], being a resource that provides filesystem 92 content to clients for a particular file, requests pages from the 93 `PageMapper`, itself having the role of supplying populated pages of content 94 from the given file. The `PageMapper` relies on the `AccessMap` to discover 95 existing pages for any accessed region of a file, involving the `Pages` object 96 (or page collection) to obtain new memory pages where existing pages are not 97 available or are no longer valid. It also requests the population of such 98 pages through use of the associated `Accessor` for the file concerned. 99 100 == Obtaining and Queuing Pages == 101 102 The `Pages` object may either obtain new memory pages from a `Memory` object 103 or reclaim (or recycle) existing pages from a `PageQueue`, this recording all 104 pages that have been populated and supplied to clients. Since it may be 105 desirable to limit the number of pages employed to satisfy file access 106 operations, the `PageQueue` provides a kind of lending mechanism: pages are 107 issued to clients and then added to the end of the queue; where no new page 108 can be supplied by a `Memory` object, the issued page at the head of the queue 109 is obtained for recycling; ultimately, an issued page will remain valid for 110 its user (the client accessing its contents) until all pages in front of it in 111 the queue are themselves recycled and it is then removed from the queue for 112 recycling. 113 114 == Satisfying Requests for Pages == 115 116 The general procedure for satisfying requests for pages is as follows: 117 118 1. Attempt to find an existing page for the affected file region. 119 1. With an existing page, attempt to reserve the page for issuing. 120 1. Without an existing or reserved page, obtain a fresh page for populating. 121 1. Queue the page for eventual reuse. 122 123 Since many files are likely to be in use, and since a fixed amount of memory 124 may be shared to provide access to file content, the interaction between 125 different `PageMapper` objects, operating on behalf of different files, must 126 be taken into consideration. The following diagram depicts the principal 127 mechanisms involved in securing access to pages so as to provide access to 128 file content. 129 130 ######## A graph showing concurrency considerations 131 132 {{{#!graphviz 133 #format svg 134 #transform notugly 135 digraph paging_concurrency { 136 node [fontsize="12.0",fontname="sans-serif",shape=box]; 137 edge [fontsize="12.0",fontname="sans-serif"]; 138 rankdir=LR; 139 140 /* First page mapper activities. */ 141 142 subgraph { 143 rank=same; 144 145 PageMapper1_note [shape=note,style=filled,fillcolor=gold,label="Find\nflexpage"]; 146 PageMapper1 [label="PageMapper"]; 147 148 Accessor1 [label="Accessor"]; 149 150 PageMapper1_reserve_note [shape=note,style=filled,fillcolor=gold,label="Reserve\nflexpage"]; 151 PageMapper1_reserve [label="PageMapper"]; 152 153 PageMapper1_queue_note [shape=note,style=filled,fillcolor=gold,label="Queue\nflexpage"]; 154 PageMapper1_queue [label="PageMapper"]; 155 156 PageMapper1_note -> PageMapper1 [dir=none,style=dotted]; 157 PageMapper1_reserve_note -> PageMapper1_reserve [dir=none,style=dotted]; 158 PageMapper1_queue_note -> PageMapper1_queue [dir=none,style=dotted]; 159 } 160 161 /* Access map usage and flexpage acquisition. */ 162 163 subgraph { 164 rank=same; 165 166 AccessMap_note [shape=note,style=filled,fillcolor=gold,label="Provides\nflexpages\ntentatively"]; 167 AccessMap1 [label="AccessMap"]; 168 169 Flexpage1 [label="Flexpage",shape=note,style=dashed]; 170 Flexpage1_note [shape=note,style=filled,fillcolor=gold,label="Needs reservation\nif found\nby mapper"]; 171 172 Flexpage1_reserve [label="Flexpage",shape=note,style=dashed]; 173 Flexpage1_reserved [label="Flexpage",shape=note]; 174 Flexpage1_reserved_note [shape=note,style=filled,fillcolor=gold,label="Claimed if\nstill available"]; 175 176 Flexpage1_queue [label="Flexpage",shape=note]; 177 178 AccessMap_note -> AccessMap1 [dir=none,style=dotted]; 179 Flexpage1_note -> Flexpage1_reserve [dir=none,style=dotted]; 180 Flexpage1_reserved -> Flexpage1_reserved_note [dir=none,style=dotted]; 181 182 Flexpage1_reserve -> Flexpage1_reserved [dir=none,style=invis]; 183 } 184 185 subgraph { 186 rank=same; 187 188 PageQueue_note [shape=note,style=filled,fillcolor=gold,label="Provides\nflexpages\ndefinitively"]; 189 PageQueue [label="PageQueue"]; 190 Flexpage [shape=note]; 191 Pages [label="Pages"]; 192 Pages_note [shape=note,style=filled,fillcolor=gold,label="Reclaim and\nrecycle\nflexpage"]; 193 194 PageQueue_reserve_note [shape=note,style=filled,fillcolor=gold,label="Provides\nreserved\nflexpage"]; 195 PageQueue_reserve [label="PageQueue"]; 196 Flexpage_reserve [label="Flexpage",shape=note]; 197 Pages_reserve [label="Pages"]; 198 Pages_reserve_note [shape=note,style=filled,fillcolor=gold,label="Reserve\nflexpage\nif available"]; 199 200 Pages_queue_note [shape=note,style=filled,fillcolor=gold,label="Queues\nissued\nflexpage"]; 201 Pages_queue [label="Pages"]; 202 Flexpage_queued [label="Flexpage",shape=note]; 203 PageQueue_queued [label="PageQueue"]; 204 205 PageQueue_note -> PageQueue [dir=none,style=dotted]; 206 Pages -> Pages_note [dir=none,style=dotted]; 207 PageQueue_reserve_note -> PageQueue_reserve [dir=none,style=dotted]; 208 Pages_reserve -> Pages_reserve_note [dir=none,style=dotted]; 209 Pages_queue_note -> Pages_queue [dir=none,style=dotted]; 210 211 Pages_note -> PageQueue_reserve_note [dir=none,style=invis]; 212 Pages_reserve_note -> Pages_queue_note [dir=none,style=invis]; 213 } 214 215 subgraph { 216 rank=same; 217 218 Flexpage2 [label="Flexpage",shape=note]; 219 Flexpage2_note [shape=note,style=filled,fillcolor=gold,label="Reserved\nwhen obtained"]; 220 221 Flexpage2_reserved [label="Flexpage",shape=note]; 222 223 AccessMap2 [label="AccessMap"]; 224 AccessMap2_note [shape=note,style=filled,fillcolor=gold,label="Records\nreserved\nflexpage"]; 225 226 Flexpage2_queue [label="Flexpage",shape=note]; 227 228 Flexpage2_note -> Flexpage2 [dir=none,style=dotted]; 229 AccessMap2 -> AccessMap2_note [dir=none,style=dotted]; 230 231 Flexpage2 -> Flexpage2_reserved [dir=none,style=invis]; 232 } 233 234 /* Second page mapper activities. */ 235 236 subgraph { 237 rank=same; 238 239 PageMapper2_note [shape=note,style=filled,fillcolor=gold,label="Obtain\nflexpage"]; 240 PageMapper2 [label="PageMapper"]; 241 242 Accessor2 [label="Accessor"]; 243 244 PageMapper2_record_note [shape=note,style=filled,fillcolor=gold,label="Record\nflexpage"]; 245 PageMapper2_record [label="PageMapper"]; 246 247 PageMapper2_queue_note [shape=note,style=filled,fillcolor=gold,label="Queue\nflexpage"]; 248 PageMapper2_queue [label="PageMapper"]; 249 250 PageMapper2_note -> PageMapper2 [dir=none,style=dotted]; 251 PageMapper2_record_note -> PageMapper2_record [dir=none,style=dotted]; 252 PageMapper2_queue_note -> PageMapper2_queue [dir=none,style=dotted]; 253 } 254 255 /* First pager dataflow. */ 256 257 PageMapper1 -> AccessMap1 [label="find"]; 258 AccessMap1 -> Flexpage1 [dir=none]; 259 Flexpage1 -> PageMapper1; 260 261 PageMapper1_reserve -> Flexpage1_reserve [dir=none]; 262 Flexpage1_reserve -> Pages_reserve [label="reserve"]; 263 Pages_reserve -> Flexpage1_reserved [dir=none]; 264 Flexpage1_reserved -> PageMapper1_reserve; 265 266 PageMapper1_queue -> Flexpage1_queue [dir=none]; 267 Flexpage1_queue -> Pages_queue [label="queue"]; 268 269 /* Flexpage queuing. */ 270 271 Pages_queue -> Flexpage_queued [dir=none]; 272 Flexpage_queued -> PageQueue_queued; 273 274 /* Flexpage retrieval from the queue. */ 275 276 PageQueue -> Flexpage [color="red",dir=none]; 277 Flexpage -> Pages [color="red"]; 278 279 PageQueue_reserve -> Flexpage_reserve [dir=none]; 280 Flexpage_reserve -> Pages_reserve; 281 282 /* Flexpage removal from the access map. */ 283 284 Pages -> AccessMap1 [color="red",label="remove\n(via PageMapper)"]; 285 AccessMap1 -> PageMapper1 [color="red",label="flush"]; 286 PageMapper1 -> Accessor1 [color="red",label="flush"]; 287 288 /* Second pager dataflow. */ 289 290 PageMapper2 -> Pages [color="red",label="flexpage"]; 291 Pages -> Flexpage2 [color="red",dir=none]; 292 Flexpage2 -> PageMapper2 [color="red"]; 293 PageMapper2 -> Accessor2 [label="fill"]; 294 295 PageMapper2_record -> Flexpage2_reserved [dir=none,label="insert"]; 296 Flexpage2_reserved -> AccessMap2; 297 298 PageMapper2_queue -> Flexpage2_queue [dir=none]; 299 Flexpage2_queue -> Pages_queue [label="queue"]; 300 } 301 }}} 302 303 ######## 304 305 == Reclaiming and Recycling Pages == 306 307 When a `PageMapper` requests a page from the `Pages` object and when the 308 `Pages` object needs to reclaim such a previously issued page, the page 309 obtained from the head of the queue is removed from the `AccessMap` employed 310 by the `PageMapper` that currently owns it. The "owner" of such a page is 311 employing the page to satisfy requests for content in a region of a particular 312 file. If modified, the page's contents may be flushed to the underlying file 313 when it is removed from the owner. As a consequence of its removal, the 314 `AccessMap` will no longer be able to offer this page to satisfy a request for 315 data in the affected region to its `PageMapper`. A reclaimed page is then 316 returned to the `PageMapper` requiring it, and since the page will no longer 317 reside in the `PageQueue`, it will be exclusively available for that 318 `PageMapper`, being populated with data from the underlying file and then 319 issued to its client. 320 321 == Reserving Available Pages == 322 323 When an `AccessMap` is able to satisfy a request for a page providing access 324 to a region in a particular file, the `PageMapper` must secure exclusive 325 access to that page. Otherwise, the possibility exists that the page will be 326 reclaimed and recycled concurrently by another `PageMapper`. Thus, the 327 `PageMapper` must request that the page be reserved by the `Pages` object 328 which in turn removes the page from the `PageQueue`. Since no other party can 329 now obtain the page independently, it can be issued safely. 330 331 == Queuing Issued Pages == 332 333 Once a page has been issued to a client by the `Pager`, regardless of how it 334 was obtained, it must be made available for future reuse. This is achieved by 335 the `PageMapper` requesting the queuing of the page, with it being added to 336 the end of the `PageQueue`.