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