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 The `Pages` object may either obtain new memory pages from a `Memory` object 101 or reclaim (or recycle) existing pages from a `PageQueue`, this recording all 102 pages that have been populated and supplied to clients. Since it may be 103 desirable to limit the number of pages employed to satisfy file access 104 operations, the `PageQueue` provides a kind of lending mechanism: pages are 105 issued to clients and then added to the end of the queue; where no new page 106 can be supplied by a `Memory` object, the issued page at the head of the queue 107 is obtained for recycling; ultimately, an issued page will remain valid for 108 its user (the client accessing its contents) until all pages in front of it in 109 the queue are themselves recycled and it is then removed from the queue for 110 recycling. 111 112 When a `PageMapper` requests a page from the `Pages` object and when the 113 `Pages` object needs to reclaim such a previously issued page, the page 114 obtained from the head of the queue is removed from the `AccessMap` that 115 currently owns it. The "owner" of such a page is employing the page to satisfy 116 requests for content in a region of a particular file. If modified, the page's 117 contents may be flushed to the underlying file when it is removed from the 118 owner. As a consequence of its removal, the `AccessMap` will no longer be able 119 to offer this page to satisfy a request for data in the affected region to its 120 `PageMapper`. A reclaimed page is then returned to the `PageMapper` requiring 121 it, and since the page will no longer reside in the `PageQueue`, it will be 122 exclusively available for that `PageMapper`, being populated with data from 123 the underlying file and then issued to its client. 124 125 When an `AccessMap` is able to satisfy a request for a page providing access 126 to a region in a particular file, the `PageMapper` must secure exclusive 127 access to that page. Otherwise, the possibility exists that the page will be 128 reclaimed and recycled concurrently by another `PageMapper`. Thus, the 129 `PageMapper` must request that the page be reserved by the `Pages` object 130 which in turn removes the page from the `PageQueue`. Since no other party can 131 now obtain the page independently, it can be issued safely. 132 133 Once a page has been issued to a client by the `Pager`, regardless of how it 134 was obtained, it must be made available for future reuse. This is achieved by 135 the `PageMapper` requesting the queuing of the page, with it being added to 136 the end of the `PageQueue`. 137 138 ######## A graph showing concurrency considerations 139 140 {{{#!graphviz 141 #format svg 142 #transform notugly 143 digraph paging_concurrency { 144 node [fontsize="12.0",fontname="sans-serif",shape=box]; 145 edge [fontsize="12.0",fontname="sans-serif"]; 146 rankdir=LR; 147 148 /* First page mapper activities. */ 149 150 subgraph { 151 rank=min; 152 153 PageMapper1_note [shape=note,style=filled,fillcolor=gold,label="Find\nflexpage"]; 154 PageMapper1 [label="PageMapper"]; 155 156 PageMapper1_reserve_note [shape=note,style=filled,fillcolor=gold,label="Reserve\nflexpage"]; 157 PageMapper1_reserve [label="PageMapper"]; 158 159 PageMapper1_queue_note [shape=note,style=filled,fillcolor=gold,label="Queue\nflexpage"]; 160 PageMapper1_queue [label="PageMapper"]; 161 162 PageMapper1_note -> PageMapper1 [dir=none,style=dotted]; 163 PageMapper1_reserve_note -> PageMapper1_reserve [dir=none,style=dotted]; 164 PageMapper1_queue_note -> PageMapper1_queue [dir=none,style=dotted]; 165 } 166 167 /* Access map usage and flexpage acquisition. */ 168 169 subgraph { 170 rank=same; 171 172 AccessMap_note [shape=note,style=filled,fillcolor=gold,label="Provides\nflexpages\ntentatively"]; 173 AccessMap1 [label="AccessMap"]; 174 Flexpage1 [label="Flexpage",shape=note,style=dashed]; 175 Flexpage1_note [shape=note,style=filled,fillcolor=gold,label="Needs reservation\nif found\nby mapper"]; 176 Flexpage1_reserve [label="Flexpage",shape=note,style=dashed]; 177 Flexpage1_reserved [label="Flexpage",shape=note]; 178 Flexpage1_reserved_note [shape=note,style=filled,fillcolor=gold,label="Claimed if\nstill available"]; 179 Flexpage1_queue [label="Flexpage",shape=note]; 180 181 AccessMap_note -> AccessMap1 [dir=none,style=dotted]; 182 Flexpage1 -> Flexpage1_note [dir=none,style=dotted]; 183 Flexpage1_note -> Flexpage1_reserve [dir=none,style=dotted]; 184 Flexpage1_reserved -> Flexpage1_reserved_note [dir=none,style=dotted]; 185 186 Flexpage1_reserve -> Flexpage1_reserved [dir=none,style=invis]; 187 } 188 189 subgraph { 190 rank=same; 191 192 PageQueue_note [shape=note,style=filled,fillcolor=gold,label="Provides\nflexpages\ndefinitively"]; 193 PageQueue [label="PageQueue"]; 194 Flexpage [shape=note]; 195 Pages [label="Pages"]; 196 Pages_note [shape=note,style=filled,fillcolor=gold,label="Claim and\nrecycle\nflexpage"]; 197 198 Flexpage_reserve [label="Flexpage",shape=note]; 199 Pages_reserve [label="Pages"]; 200 Pages_reserve_note [shape=note,style=filled,fillcolor=gold,label="Reserve\nflexpage\nif available"]; 201 202 Pages_queue_note [shape=note,style=filled,fillcolor=gold,label="Queues\nissued\nflexpage"]; 203 Pages_queue [label="Pages"]; 204 Flexpage_queued [label="Flexpage",shape=note]; 205 PageQueue_queued [label="PageQueue"]; 206 207 PageQueue_note -> PageQueue [dir=none,style=dotted]; 208 Pages -> Pages_note [dir=none,style=dotted]; 209 Pages_reserve -> Pages_reserve_note [dir=none,style=dotted]; 210 Pages_queue_note -> Pages_queue [dir=none,style=dotted]; 211 212 Pages_note -> Flexpage_reserve [dir=none,style=invis]; 213 Pages_reserve_note -> Pages_queue_note [dir=none,style=invis]; 214 } 215 216 subgraph { 217 rank=same; 218 219 Flexpage2 [label="Flexpage",shape=note]; 220 Flexpage2_note [shape=note,style=filled,fillcolor=gold,label="Reserved\nwhen obtained"]; 221 222 Flexpage2 -> Flexpage2_note [dir=none,style=dotted]; 223 } 224 225 /* Second page mapper activities. */ 226 227 subgraph { 228 rank=max; 229 230 PageMapper2_note [shape=note,style=filled,fillcolor=gold,label="Obtain\nflexpage"]; 231 PageMapper2 [label="PageMapper"]; 232 233 PageMapper2_note -> PageMapper2 [dir=none,style=dotted]; 234 } 235 236 /* First pager dataflow. */ 237 238 PageMapper1 -> AccessMap1 [label="find"]; 239 AccessMap1 -> Flexpage1 [dir=none]; 240 Flexpage1 -> PageMapper1; 241 242 PageMapper1_reserve -> Flexpage1_reserve [dir=none]; 243 Flexpage1_reserve -> Pages_reserve [label="reserve"]; 244 Pages_reserve -> Flexpage1_reserved [dir=none]; 245 Flexpage1_reserved -> PageMapper1_reserve; 246 247 PageMapper1_queue -> Flexpage1_queue [dir=none]; 248 Flexpage1_queue -> Pages_queue [label="queue"]; 249 250 /* Flexpage queuing. */ 251 252 Pages_queue -> Flexpage_queued [dir=none]; 253 Flexpage_queued -> PageQueue_queued; 254 255 /* Flexpage retrieval from the queue. */ 256 257 Pages -> PageQueue [color="red"]; 258 PageQueue -> Flexpage [color="red",dir=none]; 259 Flexpage -> Pages [color="red"]; 260 Flexpage_reserve -> Pages_reserve; 261 262 /* Flexpage removal from the access map. */ 263 264 Pages -> AccessMap1 [color="red",label="remove"]; 265 266 /* Second pager dataflow. */ 267 268 PageMapper2 -> Pages [color="red"]; 269 Pages -> Flexpage2 [color="red",dir=none]; 270 Flexpage2 -> PageMapper2 [color="red"]; 271 } 272 }}} 273 274 ########