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 Flexpage_reserve [label="Flexpage",shape=note]; 184 Pages_reserve [label="Pages"]; 185 Pages_reserve_note [shape=note,style=filled,fillcolor=gold,label="Reserve\nflexpage\nif available"]; 186 187 Pages_queue_note [shape=note,style=filled,fillcolor=gold,label="Queues\nissued\nflexpage"]; 188 Pages_queue [label="Pages"]; 189 Flexpage_queued [label="Flexpage",shape=note]; 190 PageQueue_queued [label="PageQueue"]; 191 192 PageQueue_note -> PageQueue [dir=none,style=dotted]; 193 Pages -> Pages_note [dir=none,style=dotted]; 194 Pages_reserve -> Pages_reserve_note [dir=none,style=dotted]; 195 Pages_queue_note -> Pages_queue [dir=none,style=dotted]; 196 197 Pages_note -> Flexpage_reserve [dir=none,style=invis]; 198 Pages_reserve_note -> Pages_queue_note [dir=none,style=invis]; 199 } 200 201 subgraph { 202 rank=same; 203 204 Flexpage2 [label="Flexpage",shape=note]; 205 Flexpage2_note [shape=note,style=filled,fillcolor=gold,label="Reserved\nwhen obtained"]; 206 207 Flexpage2 -> Flexpage2_note [dir=none,style=dotted]; 208 } 209 210 /* Second page mapper activities. */ 211 212 subgraph { 213 rank=max; 214 215 PageMapper2_note [shape=note,style=filled,fillcolor=gold,label="Obtain\nflexpage"]; 216 PageMapper2 [label="PageMapper"]; 217 218 PageMapper2_note -> PageMapper2 [dir=none,style=dotted]; 219 } 220 221 /* First pager dataflow. */ 222 223 PageMapper1 -> AccessMap1 [label="find"]; 224 AccessMap1 -> Flexpage1 [dir=none]; 225 Flexpage1 -> PageMapper1; 226 227 PageMapper1_reserve -> Flexpage1_reserve [dir=none]; 228 Flexpage1_reserve -> Pages_reserve [label="reserve"]; 229 Pages_reserve -> Flexpage1_reserved [dir=none]; 230 Flexpage1_reserved -> PageMapper1_reserve; 231 232 PageMapper1_queue -> Flexpage1_queue [dir=none]; 233 Flexpage1_queue -> Pages_queue [label="queue"]; 234 235 /* Flexpage queuing. */ 236 237 Pages_queue -> Flexpage_queued [dir=none]; 238 Flexpage_queued -> PageQueue_queued; 239 240 /* Flexpage retrieval from the queue. */ 241 242 Pages -> PageQueue [color="red"]; 243 PageQueue -> Flexpage [color="red",dir=none]; 244 Flexpage -> Pages [color="red"]; 245 Flexpage_reserve -> Pages_reserve; 246 247 /* Flexpage removal from the access map. */ 248 249 Pages -> AccessMap1 [color="red",label="remove"]; 250 251 /* Second pager dataflow. */ 252 253 PageMapper2 -> Pages [color="red"]; 254 Pages -> Flexpage2 [color="red",dir=none]; 255 Flexpage2 -> PageMapper2 [color="red"]; 256 } 257 }}} 258 259 ######## 260 261 == Reclaiming and Recycling Pages == 262 263 When a `PageMapper` requests a page from the `Pages` object and when the 264 `Pages` object needs to reclaim such a previously issued page, the page 265 obtained from the head of the queue is removed from the `AccessMap` that 266 currently owns it. The "owner" of such a page is employing the page to satisfy 267 requests for content in a region of a particular file. If modified, the page's 268 contents may be flushed to the underlying file when it is removed from the 269 owner. As a consequence of its removal, the `AccessMap` will no longer be able 270 to offer this page to satisfy a request for data in the affected region to its 271 `PageMapper`. A reclaimed page is then returned to the `PageMapper` requiring 272 it, and since the page will no longer reside in the `PageQueue`, it will be 273 exclusively available for that `PageMapper`, being populated with data from 274 the underlying file and then issued to its client. 275 276 == Reserving Available Pages == 277 278 When an `AccessMap` is able to satisfy a request for a page providing access 279 to a region in a particular file, the `PageMapper` must secure exclusive 280 access to that page. Otherwise, the possibility exists that the page will be 281 reclaimed and recycled concurrently by another `PageMapper`. Thus, the 282 `PageMapper` must request that the page be reserved by the `Pages` object 283 which in turn removes the page from the `PageQueue`. Since no other party can 284 now obtain the page independently, it can be issued safely. 285 286 == Queuing Issued Pages == 287 288 Once a page has been issued to a client by the `Pager`, regardless of how it 289 was obtained, it must be made available for future reuse. This is achieved by 290 the `PageMapper` requesting the queuing of the page, with it being added to 291 the end of the `PageQueue`.