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