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 [[FilesystemAccess#Pager|`Pager`]], being a resource that provides 92 filesystem 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 Since many files are likely to be in use, and since a fixed amount of memory 115 may be shared to provide access to file content, the interaction between 116 different `PageMapper` objects, operating on behalf of different files, must 117 be taken into consideration. The following diagram depicts the principal 118 mechanisms involved in securing access to pages so as to provide access to 119 file content. 120 121 ######## A graph showing concurrency considerations 122 123 {{{#!graphviz 124 #format svg 125 #transform notugly 126 digraph paging_concurrency { 127 node [fontsize="12.0",fontname="sans-serif",shape=box]; 128 edge [fontsize="12.0",fontname="sans-serif"]; 129 rankdir=LR; 130 131 /* First page mapper activities. */ 132 133 subgraph { 134 rank=min; 135 136 PageMapper1_note [shape=note,style=filled,fillcolor=gold,label="Find\nflexpage"]; 137 PageMapper1 [label="PageMapper"]; 138 139 PageMapper1_reserve_note [shape=note,style=filled,fillcolor=gold,label="Reserve\nflexpage"]; 140 PageMapper1_reserve [label="PageMapper"]; 141 142 PageMapper1_queue_note [shape=note,style=filled,fillcolor=gold,label="Queue\nflexpage"]; 143 PageMapper1_queue [label="PageMapper"]; 144 145 PageMapper1_note -> PageMapper1 [dir=none,style=dotted]; 146 PageMapper1_reserve_note -> PageMapper1_reserve [dir=none,style=dotted]; 147 PageMapper1_queue_note -> PageMapper1_queue [dir=none,style=dotted]; 148 } 149 150 /* Access map usage and flexpage acquisition. */ 151 152 subgraph { 153 rank=same; 154 155 AccessMap_note [shape=note,style=filled,fillcolor=gold,label="Provides\nflexpages\ntentatively"]; 156 AccessMap1 [label="AccessMap"]; 157 Flexpage1 [label="Flexpage",shape=note,style=dashed]; 158 Flexpage1_note [shape=note,style=filled,fillcolor=gold,label="Needs reservation\nif found\nby mapper"]; 159 160 Flexpage1_reserve [label="Flexpage",shape=note,style=dashed]; 161 Flexpage1_reserved [label="Flexpage",shape=note]; 162 Flexpage1_reserved_note [shape=note,style=filled,fillcolor=gold,label="Claimed if\nstill available"]; 163 164 Flexpage1_queue [label="Flexpage",shape=note]; 165 166 AccessMap_note -> AccessMap1 [dir=none,style=dotted]; 167 Flexpage1 -> Flexpage1_note [dir=none,style=dotted]; 168 Flexpage1_note -> Flexpage1_reserve [dir=none,style=dotted]; 169 Flexpage1_reserved -> Flexpage1_reserved_note [dir=none,style=dotted]; 170 171 Flexpage1_reserve -> Flexpage1_reserved [dir=none,style=invis]; 172 } 173 174 subgraph { 175 rank=same; 176 177 PageQueue_note [shape=note,style=filled,fillcolor=gold,label="Provides\nflexpages\ndefinitively"]; 178 PageQueue [label="PageQueue"]; 179 Flexpage [shape=note]; 180 Pages [label="Pages"]; 181 Pages_note [shape=note,style=filled,fillcolor=gold,label="Reclaim and\nrecycle\nflexpage"]; 182 183 PageQueue_reserve_note [shape=note,style=filled,fillcolor=gold,label="Provides\nreserved\nflexpage"]; 184 PageQueue_reserve [label="PageQueue"]; 185 Flexpage_reserve [label="Flexpage",shape=note]; 186 Pages_reserve [label="Pages"]; 187 Pages_reserve_note [shape=note,style=filled,fillcolor=gold,label="Reserve\nflexpage\nif available"]; 188 189 Pages_queue_note [shape=note,style=filled,fillcolor=gold,label="Queues\nissued\nflexpage"]; 190 Pages_queue [label="Pages"]; 191 Flexpage_queued [label="Flexpage",shape=note]; 192 PageQueue_queued [label="PageQueue"]; 193 194 PageQueue_note -> PageQueue [dir=none,style=dotted]; 195 Pages -> Pages_note [dir=none,style=dotted]; 196 PageQueue_reserve_note -> PageQueue_reserve [dir=none,style=dotted]; 197 Pages_reserve -> Pages_reserve_note [dir=none,style=dotted]; 198 Pages_queue_note -> Pages_queue [dir=none,style=dotted]; 199 200 Pages_note -> PageQueue_reserve_note [dir=none,style=invis]; 201 Pages_reserve_note -> Pages_queue_note [dir=none,style=invis]; 202 } 203 204 subgraph { 205 rank=same; 206 207 Flexpage2 [label="Flexpage",shape=note]; 208 Flexpage2_note [shape=note,style=filled,fillcolor=gold,label="Reserved\nwhen obtained"]; 209 210 Flexpage2_reserved [label="Flexpage",shape=note]; 211 212 AccessMap2 [label="AccessMap"]; 213 AccessMap2_note [shape=note,style=filled,fillcolor=gold,label="Records\nreserved\nflexpage"]; 214 215 Flexpage2_queue [label="Flexpage",shape=note]; 216 217 Flexpage2_note -> Flexpage2 [dir=none,style=dotted]; 218 AccessMap2 -> AccessMap2_note [dir=none,style=dotted]; 219 220 Flexpage2 -> Flexpage2_reserved [dir=none,style=invis]; 221 } 222 223 /* Second page mapper activities. */ 224 225 subgraph { 226 rank=same; 227 228 PageMapper2_note [shape=note,style=filled,fillcolor=gold,label="Obtain\nflexpage"]; 229 PageMapper2 [label="PageMapper"]; 230 231 PageMapper2_record_note [shape=note,style=filled,fillcolor=gold,label="Record\nflexpage"]; 232 PageMapper2_record [label="PageMapper"]; 233 234 PageMapper2_queue_note [shape=note,style=filled,fillcolor=gold,label="Queue\nflexpage"]; 235 PageMapper2_queue [label="PageMapper"]; 236 237 PageMapper2_note -> PageMapper2 [dir=none,style=dotted]; 238 PageMapper2_record_note -> PageMapper2_record [dir=none,style=dotted]; 239 PageMapper2_queue_note -> PageMapper2_queue [dir=none,style=dotted]; 240 } 241 242 /* First pager dataflow. */ 243 244 PageMapper1 -> AccessMap1 [label="find"]; 245 AccessMap1 -> Flexpage1 [dir=none]; 246 Flexpage1 -> PageMapper1; 247 248 PageMapper1_reserve -> Flexpage1_reserve [dir=none]; 249 Flexpage1_reserve -> Pages_reserve [label="reserve"]; 250 Pages_reserve -> Flexpage1_reserved [dir=none]; 251 Flexpage1_reserved -> PageMapper1_reserve; 252 253 PageMapper1_queue -> Flexpage1_queue [dir=none]; 254 Flexpage1_queue -> Pages_queue [label="queue"]; 255 256 /* Flexpage queuing. */ 257 258 Pages_queue -> Flexpage_queued [dir=none]; 259 Flexpage_queued -> PageQueue_queued; 260 261 /* Flexpage retrieval from the queue. */ 262 263 PageQueue -> Flexpage [color="red",dir=none]; 264 Flexpage -> Pages [color="red"]; 265 266 PageQueue_reserve -> Flexpage_reserve [dir=none]; 267 Flexpage_reserve -> Pages_reserve; 268 269 /* Flexpage removal from the access map. */ 270 271 Pages -> AccessMap1 [color="red",label="remove"]; 272 273 /* Second pager dataflow. */ 274 275 PageMapper2 -> Pages [color="red",label="flexpage"]; 276 Pages -> Flexpage2 [color="red",dir=none]; 277 Flexpage2 -> PageMapper2 [color="red"]; 278 279 PageMapper2_record -> Flexpage2_reserved [dir=none,label="insert"]; 280 Flexpage2_reserved -> AccessMap2; 281 282 PageMapper2_queue -> Flexpage2_queue [dir=none]; 283 Flexpage2_queue -> Pages_queue [label="queue"]; 284 } 285 }}} 286 287 ######## 288 289 == Reclaiming and Recycling Pages == 290 291 When a `PageMapper` requests a page from the `Pages` object and when the 292 `Pages` object needs to reclaim such a previously issued page, the page 293 obtained from the head of the queue is removed from the `AccessMap` that 294 currently owns it. The "owner" of such a page is employing the page to satisfy 295 requests for content in a region of a particular file. If modified, the page's 296 contents may be flushed to the underlying file when it is removed from the 297 owner. As a consequence of its removal, the `AccessMap` will no longer be able 298 to offer this page to satisfy a request for data in the affected region to its 299 `PageMapper`. A reclaimed page is then returned to the `PageMapper` requiring 300 it, and since the page will no longer reside in the `PageQueue`, it will be 301 exclusively available for that `PageMapper`, being populated with data from 302 the underlying file and then issued to its client. 303 304 == Reserving Available Pages == 305 306 When an `AccessMap` is able to satisfy a request for a page providing access 307 to a region in a particular file, the `PageMapper` must secure exclusive 308 access to that page. Otherwise, the possibility exists that the page will be 309 reclaimed and recycled concurrently by another `PageMapper`. Thus, the 310 `PageMapper` must request that the page be reserved by the `Pages` object 311 which in turn removes the page from the `PageQueue`. Since no other party can 312 now obtain the page independently, it can be issued safely. 313 314 == Queuing Issued Pages == 315 316 Once a page has been issued to a client by the `Pager`, regardless of how it 317 was obtained, it must be made available for future reuse. This is achieved by 318 the `PageMapper` requesting the queuing of the page, with it being added to 319 the end of the `PageQueue`.