paul@359 | 1 | = Directories = |
paul@359 | 2 | |
paul@359 | 3 | Filesystem directories contain collections of files, other directories, along |
paul@359 | 4 | with other filesystem objects. Directories can be listed, permitting |
paul@359 | 5 | filesystem clients to peruse the contents of each directory. However, the act |
paul@359 | 6 | of listing a directory may impose certain constraints on the operations being |
paul@359 | 7 | conducted on the directory during the listing process. |
paul@359 | 8 | |
paul@359 | 9 | Operations that affect directory contents include the following: |
paul@359 | 10 | |
paul@359 | 11 | * Creating a new object |
paul@359 | 12 | * Removing an object |
paul@359 | 13 | * Moving an object out of the directory |
paul@359 | 14 | * Moving an object into the directory |
paul@359 | 15 | |
paul@359 | 16 | It is conceivable that for some filesystems, these operations will not be able |
paul@359 | 17 | to rely on directly modifying the directory since a listing operation may be |
paul@359 | 18 | in progress. Consequently, a number of rules would be imposed for such |
paul@359 | 19 | filesystems. It appears that Ext2-based filesystems accessed via libext2fs do |
paul@359 | 20 | not require such rules to be applied outside the library due to the design of |
paul@359 | 21 | the filesystem structures and the behaviour of the library itself. |
paul@359 | 22 | |
paul@359 | 23 | == Providers == |
paul@359 | 24 | |
paul@359 | 25 | Providers of filesystem objects are created when at least one filesystem |
paul@359 | 26 | client is accessing such an object, with the object regarded as being |
paul@359 | 27 | '''open'''. By definition, a provider will exist until all clients have closed |
paul@359 | 28 | or discarded their means of accessing the object. |
paul@359 | 29 | |
paul@359 | 30 | An object is regarded as '''accessible''' if it can still be opened by |
paul@359 | 31 | filesystem clients. Where an object has been removed, it will no longer be |
paul@359 | 32 | accessible since clients should not be able to see the object in the |
paul@359 | 33 | filesystem any more. (The actual filesystem residing in storage may not have |
paul@359 | 34 | been updated for such a removal, this being the eventual outcome of a removal |
paul@359 | 35 | operation.) |
paul@359 | 36 | |
paul@359 | 37 | Providers can be regarded as '''accessible''' if they maintain access to |
paul@359 | 38 | objects that are open and accessible. Clients opening objects will only gain |
paul@359 | 39 | access to accessible providers. Providers can become inaccessible if an object |
paul@359 | 40 | is removed even if the object (and its provider) is still open. |
paul@359 | 41 | |
paul@359 | 42 | Initially, providers will correspond to objects resident in the stored |
paul@359 | 43 | filesystem. Thus, looking up an object using its path will involve the |
paul@359 | 44 | filesystem, yielding a file identifier that can be used to map to a provider. |
paul@359 | 45 | |
paul@359 | 46 | {{{ |
paul@359 | 47 | def get_provider_from_filesystem(path): |
paul@359 | 48 | fileid = opening.get_fileid(path) |
paul@359 | 49 | |
paul@359 | 50 | if not fileid: |
paul@359 | 51 | return error |
paul@359 | 52 | |
paul@359 | 53 | return find_provider(fileid) |
paul@359 | 54 | }}} |
paul@359 | 55 | |
paul@359 | 56 | However, providers may not always immediately correspond to objects resident |
paul@359 | 57 | in the stored filesystem. Where an object is created but cannot be immediately |
paul@359 | 58 | registered in the contents of a directory, it must be registered separately |
paul@359 | 59 | and attempts to open this object must consult this separate mapping of |
paul@359 | 60 | filenames to providers. |
paul@359 | 61 | |
paul@359 | 62 | {{{ |
paul@359 | 63 | def get_provider(path): |
paul@359 | 64 | provider = find_created_provider(path) |
paul@359 | 65 | |
paul@359 | 66 | if provider: |
paul@359 | 67 | return provider |
paul@359 | 68 | |
paul@359 | 69 | return get_provider_from_filesystem(path) |
paul@359 | 70 | }}} |
paul@359 | 71 | |
paul@359 | 72 | Providers that are inaccessible need to be retained until they are closed. |
paul@359 | 73 | However, since they are no longer accessible, they should not be available to |
paul@359 | 74 | the provider lookup operations. |
paul@359 | 75 | |
paul@359 | 76 | When providers are closed, they are removed from any mapping in which they |
paul@359 | 77 | could be found. Inaccessible providers that have been retained outside the |
paul@359 | 78 | identifier or filename mappings will represent objects that should be removed |
paul@359 | 79 | from their parent directory. Accessible providers retained by the mappings |
paul@359 | 80 | will represent objects that should be created in their parent directory. |
paul@359 | 81 | |
paul@359 | 82 | Whether object removal or creation will occur depends on whether the parent |
paul@359 | 83 | directory is able to safely perform these operations concurrently with other |
paul@359 | 84 | operations (such as servicing a listing operation) or whether such operations |
paul@359 | 85 | will need to be deferred until they can be safely performed. |
paul@359 | 86 | |
paul@359 | 87 | == Object Removal == |
paul@359 | 88 | |
paul@359 | 89 | Filesystem object removal involves obtaining any provider of the object. Where |
paul@359 | 90 | a provider can be obtained, it will be made inaccessible and removal will be |
paul@359 | 91 | requested. The actual object will not be removed at least until it is closed |
paul@359 | 92 | because it may still receive and provide data. (Unlinking open files is a |
paul@359 | 93 | feature of Unix systems.) |
paul@359 | 94 | |
paul@359 | 95 | Where a provider cannot be obtained, an attempt will be made to obtain the |
paul@359 | 96 | parent directory provider, and if this succeeds, it indicates that the |
paul@359 | 97 | directory is being accessed and must therefore be notified of the intention to |
paul@359 | 98 | eventually remove the object concerned. |
paul@359 | 99 | |
paul@359 | 100 | Without any provider of the object, and where no directory provider can be |
paul@359 | 101 | obtained, the object can be immediately removed from the filesystem. |
paul@359 | 102 | |
paul@359 | 103 | {{{ |
paul@359 | 104 | def remove_object(path): |
paul@359 | 105 | provider = get_provider(path) |
paul@359 | 106 | |
paul@359 | 107 | if provider: |
paul@359 | 108 | return make_provider_inaccessible(provider) |
paul@359 | 109 | |
paul@359 | 110 | dirname, basename = split(path) |
paul@359 | 111 | directory_provider = get_provider(dirname) |
paul@359 | 112 | |
paul@359 | 113 | if directory_provider: |
paul@359 | 114 | return directory_provider.remove_pending(basename) |
paul@359 | 115 | |
paul@359 | 116 | return filesystem.remove_object(path) |
paul@359 | 117 | }}} |
paul@359 | 118 | |
paul@359 | 119 | It should be noted that with no accessible provider, any attempt to create a |
paul@359 | 120 | file with the same name as a removed file should cause a new "version" of the |
paul@359 | 121 | file to be created. |
paul@359 | 122 | |
paul@359 | 123 | == Object Creation == |
paul@359 | 124 | |
paul@359 | 125 | Filesystem object creation occurs when no existing provider can be found for a |
paul@359 | 126 | named object and where creation is requested. Any new object will be |
paul@359 | 127 | accessible and remain so until or unless it is removed. |
paul@359 | 128 | |
paul@359 | 129 | Whether an object is created in the filesystem storage depends on whether the |
paul@359 | 130 | parent directory is being used. |
paul@359 | 131 | |
paul@359 | 132 | If a parent directory is not being used, the object can be registered in its |
paul@359 | 133 | proper location in the filesystem itself, yielding a file identifier. |
paul@359 | 134 | |
paul@359 | 135 | If a parent directory is being used, the object cannot be immediately |
paul@359 | 136 | registered in its proper location, but since data may still need to be written |
paul@359 | 137 | to storage, a temporary location is employed, yielding a file identifier. |
paul@359 | 138 | |
paul@359 | 139 | For an object created in a temporary location, a temporary mapping from the |
paul@359 | 140 | path of the object to the provider is established, with the parent directory |
paul@359 | 141 | being notified of the pending object creation. |
paul@359 | 142 | |
paul@359 | 143 | {{{ |
paul@359 | 144 | def create_object(path): |
paul@359 | 145 | provider = get_provider(path) |
paul@359 | 146 | |
paul@359 | 147 | if provider: |
paul@359 | 148 | return error |
paul@359 | 149 | |
paul@359 | 150 | dirname, basename = split(path) |
paul@359 | 151 | directory_provider = get_provider(dirname) |
paul@359 | 152 | |
paul@359 | 153 | if directory_provider: |
paul@359 | 154 | provider = make_provider(get_temporary_location(path)) |
paul@359 | 155 | directory_provider.create_pending(provider) |
paul@359 | 156 | return register_created_provider(path, provider) |
paul@359 | 157 | |
paul@359 | 158 | provider = make_provider(path) |
paul@359 | 159 | return register_provider(provider) |
paul@359 | 160 | }}} |
paul@359 | 161 | |
paul@359 | 162 | == Created Providers == |
paul@359 | 163 | |
paul@359 | 164 | Created providers are retained by the registry until their files can be |
paul@359 | 165 | committed to the filesystem in the desired location. |
paul@359 | 166 | |
paul@359 | 167 | The `register_created_provider` operation establishes a mapping from a path to |
paul@359 | 168 | a provider that can be queried using the `find_created_provider` operation. |
paul@359 | 169 | |
paul@359 | 170 | Created providers are deregistered when they are closed. This will occur when |
paul@359 | 171 | the parent directory of the file to be committed is closed. At that time, the |
paul@359 | 172 | created file will be moved from its temporary location to the desired |
paul@359 | 173 | location. |
paul@359 | 174 | |
paul@359 | 175 | == Inaccessible Providers == |
paul@359 | 176 | |
paul@359 | 177 | Inaccessible providers are retained by the registry until they are closed. |
paul@359 | 178 | |
paul@359 | 179 | Where the provided file resides in a non-temporary location, closure will |
paul@359 | 180 | occur when the parent directory of the provided file is closed, this having |
paul@359 | 181 | obstructed the removal of the file. At that time, the provided file will be |
paul@359 | 182 | removed. |
paul@359 | 183 | |
paul@359 | 184 | Where the provided file resides in a temporary location, closure will not be |
paul@359 | 185 | obstructed by any directory and will cause the file to be removed immediately. |
paul@359 | 186 | |
paul@359 | 187 | == Directory Provider Closure == |
paul@359 | 188 | |
paul@359 | 189 | A critical event that typically initiates housekeeping work for created and |
paul@359 | 190 | removed files is the closure of the parent directory of those files. |
paul@359 | 191 | |
paul@359 | 192 | Directory providers support the `create_pending` and `remove_pending` |
paul@359 | 193 | operations that register the details of affected files. When closure occurs, |
paul@359 | 194 | the provider will contact the registry to initiate the necessary work to |
paul@359 | 195 | relocate created files and to remove files. |
paul@359 | 196 | |
paul@359 | 197 | |
paul@359 | 198 | |
paul@359 | 199 | |
paul@359 | 200 | Where an object provider is notified of pending removal, it will initiate |
paul@359 | 201 | removal of the actual object upon closure, checking for an active parent |
paul@359 | 202 | provider. |
paul@359 | 203 | |
paul@359 | 204 | Where a parent provider is notified of pending removal, it will initiate |
paul@359 | 205 | removal of the actual object upon closure, checking for an active object |
paul@359 | 206 | provider. |
paul@359 | 207 | |
paul@359 | 208 | Object opening logic would need to be adjusted. Consider the case where a |
paul@359 | 209 | file is removed but still open. |
paul@359 | 210 | |
paul@359 | 211 | Any attempt to open a file with the same name must ignore the original and |
paul@359 | 212 | open a new file of that name which would be stored elsewhere until such |
paul@359 | 213 | time as the original is actually removed from its location. |
paul@359 | 214 | |
paul@359 | 215 | This new file might have a different identifier since the original file |
paul@359 | 216 | would still exist and retain the identifier. |
paul@359 | 217 | |
paul@359 | 218 | Any such new, but uncommitted, file must be accessible by other clients |
paul@359 | 219 | attempting to open a file of that name. However, removal operations must |
paul@359 | 220 | also be possible, making this version of the open file also unaccessible |
paul@359 | 221 | to new opening clients. |
paul@359 | 222 | |
paul@359 | 223 | Therefore, any providers used by opening clients must only refer to a |
paul@359 | 224 | version of a file that is pending removal if no other version has been |
paul@359 | 225 | created. Once a new version has been created, any provider pending removal |
paul@359 | 226 | must be relegated to a separate collection. |
paul@359 | 227 | |
paul@359 | 228 | Storage of new versions of files could be confined to special directories |
paul@359 | 229 | that are hidden from clients. |
paul@359 | 230 | |
paul@359 | 231 | The opening logic would be as follows: |
paul@359 | 232 | |
paul@359 | 233 | provider = find_provider(path) |
paul@359 | 234 | |
paul@359 | 235 | if provider: |
paul@359 | 236 | if provider.pending_removal(): |
paul@359 | 237 | relegate(provider) |
paul@359 | 238 | provider = create_provider(path, hidden=True) |
paul@359 | 239 | else: |
paul@359 | 240 | provider = create_provider(path, hidden=False) |
paul@359 | 241 | |
paul@359 | 242 | # Have provider. |
paul@359 | 243 | |
paul@359 | 244 | return provider.make_resource() |
paul@359 | 245 | |
paul@359 | 246 | A provider would normally be obtained by consulting the filesystem |
paul@359 | 247 | implementation. However, new versions of files replacing ones pending |
paul@359 | 248 | removal will reside in locations that are different to the intended |
paul@359 | 249 | location of the file. Consequently, the registry needs to maintain its own |
paul@359 | 250 | mapping of paths to providers for such file versions. |
paul@359 | 251 | |
paul@359 | 252 | The opportunity to remove a file definitively arises when the following |
paul@359 | 253 | conditions are satisfied: |
paul@359 | 254 | |
paul@359 | 255 | * The parent directory is not open in some way |
paul@359 | 256 | * The original provider for the file is no longer open |
paul@359 | 257 | |
paul@359 | 258 | For new versions of a removed file that have themselves been marked as |
paul@359 | 259 | pending removal, their closure is sufficient to remove their filesystem |
paul@359 | 260 | resources. |
paul@359 | 261 | |
paul@359 | 262 | However, the registry must maintain a path entry for any active version |
paul@359 | 263 | of a removed file until that version is closed. Thus, the following |
paul@359 | 264 | conditions apply: |
paul@359 | 265 | |
paul@359 | 266 | * The parent directory (of the original file) is not open in some way |
paul@359 | 267 | * The provider of the new version is no longer open |
paul@359 | 268 | |
paul@359 | 269 | It will not be generally possible to open the hidden directory containing |
paul@359 | 270 | new file versions. Therefore, the transfer of the file to its intended |
paul@359 | 271 | location will not risk interfering with any operations on the hidden |
paul@359 | 272 | directory. |
paul@359 | 273 | |